1 /*
2 * Stack-less Just-In-Time compiler
3 *
4 * Copyright Zoltan Herczeg (hzmester@freemail.hu). All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without modification, are
7 * permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright notice, this list of
10 * conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright notice, this list
13 * of conditions and the following disclaimer in the documentation and/or other materials
14 * provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) AND CONTRIBUTORS ``AS IS'' AND ANY
17 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
19 * SHALL THE COPYRIGHT HOLDER(S) OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
21 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
22 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
23 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
24 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27 /*
28 This file contains a simple executable memory allocator
29
30 It is assumed, that executable code blocks are usually medium (or sometimes
31 large) memory blocks, and the allocator is not too frequently called (less
32 optimized than other allocators). Thus, using it as a generic allocator is
33 not suggested.
34
35 How does it work:
36 Memory is allocated in continuous memory areas called chunks by alloc_chunk()
37 Chunk format:
38 [ block ][ block ] ... [ block ][ block terminator ]
39
40 All blocks and the block terminator is started with block_header. The block
41 header contains the size of the previous and the next block. These sizes
42 can also contain special values.
43 Block size:
44 0 - The block is a free_block, with a different size member.
45 1 - The block is a block terminator.
46 n - The block is used at the moment, and the value contains its size.
47 Previous block size:
48 0 - This is the first block of the memory chunk.
49 n - The size of the previous block.
50
51 Using these size values we can go forward or backward on the block chain.
52 The unused blocks are stored in a chain list pointed by free_blocks. This
53 list is useful if we need to find a suitable memory area when the allocator
54 is called.
55
56 When a block is freed, the new free block is connected to its adjacent free
57 blocks if possible.
58
59 [ free block ][ used block ][ free block ]
60 and "used block" is freed, the three blocks are connected together:
61 [ one big free block ]
62 */
63
64 /* --------------------------------------------------------------------- */
65 /* System (OS) functions */
66 /* --------------------------------------------------------------------- */
67
68 /* 64 KByte. */
69 #define CHUNK_SIZE 0x10000
70
71 struct chunk_header {
72 void *executable;
73 };
74
75 /*
76 alloc_chunk / free_chunk :
77 * allocate executable system memory chunks
78 * the size is always divisible by CHUNK_SIZE
79 SLJIT_ALLOCATOR_LOCK / SLJIT_ALLOCATOR_UNLOCK :
80 * provided as part of sljitUtils
81 * only the allocator requires this lock, sljit is fully thread safe
82 as it only uses local variables
83 */
84
85 #ifndef __NetBSD__
86 #include <sys/stat.h>
87 #include <fcntl.h>
88 #include <stdio.h>
89 #include <string.h>
90
91 #ifndef O_NOATIME
92 #define O_NOATIME 0
93 #endif
94
95 /* this is a linux extension available since kernel 3.11 */
96 #ifndef O_TMPFILE
97 #define O_TMPFILE 020200000
98 #endif
99
100 #ifndef _GNU_SOURCE
101 char *secure_getenv(const char *name);
102 int mkostemp(char *template, int flags);
103 #endif
104
create_tempfile(void)105 static SLJIT_INLINE int create_tempfile(void)
106 {
107 int fd;
108 char tmp_name[256];
109 size_t tmp_name_len = 0;
110 char *dir;
111 struct stat st;
112 #if defined(SLJIT_SINGLE_THREADED) && SLJIT_SINGLE_THREADED
113 mode_t mode;
114 #endif
115
116 #ifdef HAVE_MEMFD_CREATE
117 /* this is a GNU extension, make sure to use -D_GNU_SOURCE */
118 fd = memfd_create("sljit", MFD_CLOEXEC);
119 if (fd != -1) {
120 fchmod(fd, 0);
121 return fd;
122 }
123 #endif
124
125 dir = secure_getenv("TMPDIR");
126
127 if (dir) {
128 tmp_name_len = strlen(dir);
129 if (tmp_name_len > 0 && tmp_name_len < sizeof(tmp_name)) {
130 if ((stat(dir, &st) == 0) && S_ISDIR(st.st_mode))
131 strcpy(tmp_name, dir);
132 }
133 }
134
135 #ifdef P_tmpdir
136 if (!tmp_name_len) {
137 tmp_name_len = strlen(P_tmpdir);
138 if (tmp_name_len > 0 && tmp_name_len < sizeof(tmp_name))
139 strcpy(tmp_name, P_tmpdir);
140 }
141 #endif
142 if (!tmp_name_len) {
143 strcpy(tmp_name, "/tmp");
144 tmp_name_len = 4;
145 }
146
147 SLJIT_ASSERT(tmp_name_len > 0 && tmp_name_len < sizeof(tmp_name));
148
149 if (tmp_name[tmp_name_len - 1] == '/')
150 tmp_name[--tmp_name_len] = '\0';
151
152 #ifdef __linux__
153 /*
154 * the previous trimming might had left an empty string if TMPDIR="/"
155 * so work around the problem below
156 */
157 fd = open(tmp_name_len ? tmp_name : "/",
158 O_TMPFILE | O_EXCL | O_RDWR | O_NOATIME | O_CLOEXEC, 0);
159 if (fd != -1)
160 return fd;
161 #endif
162
163 if (tmp_name_len + 7 >= sizeof(tmp_name))
164 return -1;
165
166 strcpy(tmp_name + tmp_name_len, "/XXXXXX");
167 #if defined(SLJIT_SINGLE_THREADED) && SLJIT_SINGLE_THREADED
168 mode = umask(0777);
169 #endif
170 fd = mkostemp(tmp_name, O_CLOEXEC | O_NOATIME);
171 #if defined(SLJIT_SINGLE_THREADED) && SLJIT_SINGLE_THREADED
172 umask(mode);
173 #else
174 fchmod(fd, 0);
175 #endif
176
177 if (fd == -1)
178 return -1;
179
180 if (unlink(tmp_name)) {
181 close(fd);
182 return -1;
183 }
184
185 return fd;
186 }
187
alloc_chunk(sljit_uw size)188 static SLJIT_INLINE struct chunk_header* alloc_chunk(sljit_uw size)
189 {
190 struct chunk_header *retval;
191 int fd;
192
193 fd = create_tempfile();
194 if (fd == -1)
195 return NULL;
196
197 if (ftruncate(fd, size)) {
198 close(fd);
199 return NULL;
200 }
201
202 retval = (struct chunk_header *)mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
203
204 if (retval == MAP_FAILED) {
205 close(fd);
206 return NULL;
207 }
208
209 retval->executable = mmap(NULL, size, PROT_READ | PROT_EXEC, MAP_SHARED, fd, 0);
210
211 if (retval->executable == MAP_FAILED) {
212 munmap((void *)retval, size);
213 close(fd);
214 return NULL;
215 }
216
217 close(fd);
218 return retval;
219 }
220 #else
221 /*
222 * MAP_REMAPDUP is a NetBSD extension available sinde 8.0, make sure to
223 * adjust your feature macros (ex: -D_NETBSD_SOURCE) as needed
224 */
alloc_chunk(sljit_uw size)225 static SLJIT_INLINE struct chunk_header* alloc_chunk(sljit_uw size)
226 {
227 struct chunk_header *retval;
228
229 retval = (struct chunk_header *)mmap(NULL, size,
230 PROT_READ | PROT_WRITE | PROT_MPROTECT(PROT_EXEC),
231 MAP_ANON | MAP_SHARED, -1, 0);
232
233 if (retval == MAP_FAILED)
234 return NULL;
235
236 retval->executable = mremap(retval, size, NULL, size, MAP_REMAPDUP);
237 if (retval->executable == MAP_FAILED) {
238 munmap((void *)retval, size);
239 return NULL;
240 }
241
242 if (mprotect(retval->executable, size, PROT_READ | PROT_EXEC) == -1) {
243 munmap(retval->executable, size);
244 munmap((void *)retval, size);
245 return NULL;
246 }
247
248 return retval;
249 }
250 #endif /* NetBSD */
251
free_chunk(void * chunk,sljit_uw size)252 static SLJIT_INLINE void free_chunk(void *chunk, sljit_uw size)
253 {
254 struct chunk_header *header = ((struct chunk_header *)chunk) - 1;
255
256 munmap(header->executable, size);
257 munmap((void *)header, size);
258 }
259
260 /* --------------------------------------------------------------------- */
261 /* Common functions */
262 /* --------------------------------------------------------------------- */
263
264 #define CHUNK_MASK (~(CHUNK_SIZE - 1))
265
266 struct block_header {
267 sljit_uw size;
268 sljit_uw prev_size;
269 sljit_sw executable_offset;
270 };
271
272 struct free_block {
273 struct block_header header;
274 struct free_block *next;
275 struct free_block *prev;
276 sljit_uw size;
277 };
278
279 #define AS_BLOCK_HEADER(base, offset) \
280 ((struct block_header*)(((sljit_u8*)base) + offset))
281 #define AS_FREE_BLOCK(base, offset) \
282 ((struct free_block*)(((sljit_u8*)base) + offset))
283 #define MEM_START(base) ((void*)((base) + 1))
284 #define ALIGN_SIZE(size) (((size) + sizeof(struct block_header) + 7) & ~7)
285
286 static struct free_block* free_blocks;
287 static sljit_uw allocated_size;
288 static sljit_uw total_size;
289
sljit_insert_free_block(struct free_block * free_block,sljit_uw size)290 static SLJIT_INLINE void sljit_insert_free_block(struct free_block *free_block, sljit_uw size)
291 {
292 free_block->header.size = 0;
293 free_block->size = size;
294
295 free_block->next = free_blocks;
296 free_block->prev = NULL;
297 if (free_blocks)
298 free_blocks->prev = free_block;
299 free_blocks = free_block;
300 }
301
sljit_remove_free_block(struct free_block * free_block)302 static SLJIT_INLINE void sljit_remove_free_block(struct free_block *free_block)
303 {
304 if (free_block->next)
305 free_block->next->prev = free_block->prev;
306
307 if (free_block->prev)
308 free_block->prev->next = free_block->next;
309 else {
310 SLJIT_ASSERT(free_blocks == free_block);
311 free_blocks = free_block->next;
312 }
313 }
314
sljit_malloc_exec(sljit_uw size)315 SLJIT_API_FUNC_ATTRIBUTE void* sljit_malloc_exec(sljit_uw size)
316 {
317 struct chunk_header *chunk_header;
318 struct block_header *header;
319 struct block_header *next_header;
320 struct free_block *free_block;
321 sljit_uw chunk_size;
322 sljit_sw executable_offset;
323
324 SLJIT_ALLOCATOR_LOCK();
325 if (size < (64 - sizeof(struct block_header)))
326 size = (64 - sizeof(struct block_header));
327 size = ALIGN_SIZE(size);
328
329 free_block = free_blocks;
330 while (free_block) {
331 if (free_block->size >= size) {
332 chunk_size = free_block->size;
333 if (chunk_size > size + 64) {
334 /* We just cut a block from the end of the free block. */
335 chunk_size -= size;
336 free_block->size = chunk_size;
337 header = AS_BLOCK_HEADER(free_block, chunk_size);
338 header->prev_size = chunk_size;
339 header->executable_offset = free_block->header.executable_offset;
340 AS_BLOCK_HEADER(header, size)->prev_size = size;
341 }
342 else {
343 sljit_remove_free_block(free_block);
344 header = (struct block_header*)free_block;
345 size = chunk_size;
346 }
347 allocated_size += size;
348 header->size = size;
349 SLJIT_ALLOCATOR_UNLOCK();
350 return MEM_START(header);
351 }
352 free_block = free_block->next;
353 }
354
355 chunk_size = sizeof(struct chunk_header) + sizeof(struct block_header);
356 chunk_size = (chunk_size + size + CHUNK_SIZE - 1) & CHUNK_MASK;
357
358 chunk_header = alloc_chunk(chunk_size);
359 if (!chunk_header) {
360 SLJIT_ALLOCATOR_UNLOCK();
361 return NULL;
362 }
363
364 executable_offset = (sljit_sw)((sljit_u8*)chunk_header->executable - (sljit_u8*)chunk_header);
365
366 chunk_size -= sizeof(struct chunk_header) + sizeof(struct block_header);
367 total_size += chunk_size;
368
369 header = (struct block_header *)(chunk_header + 1);
370
371 header->prev_size = 0;
372 header->executable_offset = executable_offset;
373 if (chunk_size > size + 64) {
374 /* Cut the allocated space into a free and a used block. */
375 allocated_size += size;
376 header->size = size;
377 chunk_size -= size;
378
379 free_block = AS_FREE_BLOCK(header, size);
380 free_block->header.prev_size = size;
381 free_block->header.executable_offset = executable_offset;
382 sljit_insert_free_block(free_block, chunk_size);
383 next_header = AS_BLOCK_HEADER(free_block, chunk_size);
384 }
385 else {
386 /* All space belongs to this allocation. */
387 allocated_size += chunk_size;
388 header->size = chunk_size;
389 next_header = AS_BLOCK_HEADER(header, chunk_size);
390 }
391 next_header->size = 1;
392 next_header->prev_size = chunk_size;
393 next_header->executable_offset = executable_offset;
394 SLJIT_ALLOCATOR_UNLOCK();
395 return MEM_START(header);
396 }
397
sljit_free_exec(void * ptr)398 SLJIT_API_FUNC_ATTRIBUTE void sljit_free_exec(void* ptr)
399 {
400 struct block_header *header;
401 struct free_block* free_block;
402
403 SLJIT_ALLOCATOR_LOCK();
404 header = AS_BLOCK_HEADER(ptr, -(sljit_sw)sizeof(struct block_header));
405 header = AS_BLOCK_HEADER(header, -header->executable_offset);
406 allocated_size -= header->size;
407
408 /* Connecting free blocks together if possible. */
409
410 /* If header->prev_size == 0, free_block will equal to header.
411 In this case, free_block->header.size will be > 0. */
412 free_block = AS_FREE_BLOCK(header, -(sljit_sw)header->prev_size);
413 if (SLJIT_UNLIKELY(!free_block->header.size)) {
414 free_block->size += header->size;
415 header = AS_BLOCK_HEADER(free_block, free_block->size);
416 header->prev_size = free_block->size;
417 }
418 else {
419 free_block = (struct free_block*)header;
420 sljit_insert_free_block(free_block, header->size);
421 }
422
423 header = AS_BLOCK_HEADER(free_block, free_block->size);
424 if (SLJIT_UNLIKELY(!header->size)) {
425 free_block->size += ((struct free_block*)header)->size;
426 sljit_remove_free_block((struct free_block*)header);
427 header = AS_BLOCK_HEADER(free_block, free_block->size);
428 header->prev_size = free_block->size;
429 }
430
431 /* The whole chunk is free. */
432 if (SLJIT_UNLIKELY(!free_block->header.prev_size && header->size == 1)) {
433 /* If this block is freed, we still have (allocated_size / 2) free space. */
434 if (total_size - free_block->size > (allocated_size * 3 / 2)) {
435 total_size -= free_block->size;
436 sljit_remove_free_block(free_block);
437 free_chunk(free_block, free_block->size +
438 sizeof(struct chunk_header) +
439 sizeof(struct block_header));
440 }
441 }
442
443 SLJIT_ALLOCATOR_UNLOCK();
444 }
445
sljit_free_unused_memory_exec(void)446 SLJIT_API_FUNC_ATTRIBUTE void sljit_free_unused_memory_exec(void)
447 {
448 struct free_block* free_block;
449 struct free_block* next_free_block;
450
451 SLJIT_ALLOCATOR_LOCK();
452
453 free_block = free_blocks;
454 while (free_block) {
455 next_free_block = free_block->next;
456 if (!free_block->header.prev_size &&
457 AS_BLOCK_HEADER(free_block, free_block->size)->size == 1) {
458 total_size -= free_block->size;
459 sljit_remove_free_block(free_block);
460 free_chunk(free_block, free_block->size +
461 sizeof(struct chunk_header) +
462 sizeof(struct block_header));
463 }
464 free_block = next_free_block;
465 }
466
467 SLJIT_ASSERT((total_size && free_blocks) || (!total_size && !free_blocks));
468 SLJIT_ALLOCATOR_UNLOCK();
469 }
470
sljit_exec_offset(void * ptr)471 SLJIT_API_FUNC_ATTRIBUTE sljit_sw sljit_exec_offset(void* ptr)
472 {
473 return ((struct block_header *)(ptr))[-1].executable_offset;
474 }
475