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 allocator_grab_lock / allocator_release_lock :
80 * make the allocator thread safe
81 * can be empty if the OS (or the application) does not support threading
82 * only the allocator requires this lock, sljit is fully thread safe
83 as it only uses local variables
84 */
85
86 #include <fcntl.h>
87
88 #ifndef O_NOATIME
89 #define O_NOATIME 0
90 #endif
91
92 #ifdef __O_TMPFILE
93 #ifndef O_TMPFILE
94 #define O_TMPFILE (__O_TMPFILE | O_DIRECTORY)
95 #endif
96 #endif
97
98 #if !(defined(__NetBSD__) && defined(MAP_REMAPDUP))
99 int mkostemp(char *template, int flags);
100
101 #ifdef __NetBSD__
102 /*
103 * this is a workaround for NetBSD < 8 that lacks a system provided
104 * secure_getenv function.
105 * ideally this should never be used, as the standard allocator is
106 * a preferred option for those systems and should be used instead.
107 */
108 #define secure_getenv(name) issetugid() ? NULL : getenv(name)
109 #else
110 char *secure_getenv(const char *name);
111 #endif
112
create_tempfile(void)113 static SLJIT_INLINE int create_tempfile(void)
114 {
115 int fd;
116
117 char tmp_name[256];
118 size_t tmp_name_len;
119 char *dir;
120 size_t len;
121
122 #ifdef HAVE_MEMFD_CREATE
123 /* this is a GNU extension, make sure to use -D_GNU_SOURCE */
124 fd = memfd_create("sljit", MFD_CLOEXEC);
125 if (fd != -1)
126 return fd;
127 #endif
128
129 #ifdef P_tmpdir
130 len = (P_tmpdir != NULL) ? strlen(P_tmpdir) : 0;
131
132 if (len > 0 && len < sizeof(tmp_name)) {
133 strcpy(tmp_name, P_tmpdir);
134 tmp_name_len = len;
135 }
136 else {
137 strcpy(tmp_name, "/tmp");
138 tmp_name_len = 4;
139 }
140 #else
141 strcpy(tmp_name, "/tmp");
142 tmp_name_len = 4;
143 #endif
144
145 dir = secure_getenv("TMPDIR");
146
147 if (dir) {
148 len = strlen(dir);
149 if (len > 0 && len < sizeof(tmp_name)) {
150 strcpy(tmp_name, dir);
151 tmp_name_len = len;
152 }
153 }
154
155 SLJIT_ASSERT(tmp_name_len > 0 && tmp_name_len < sizeof(tmp_name));
156
157 while (tmp_name_len > 0 && tmp_name[tmp_name_len - 1] == '/') {
158 tmp_name_len--;
159 tmp_name[tmp_name_len] = '\0';
160 }
161
162 #ifdef O_TMPFILE
163 fd = open(tmp_name, O_TMPFILE | O_EXCL | O_RDWR | O_NOATIME | O_CLOEXEC, S_IRUSR | S_IWUSR);
164 if (fd != -1)
165 return fd;
166 #endif
167
168 if (tmp_name_len + 7 >= sizeof(tmp_name))
169 {
170 return -1;
171 }
172
173 strcpy(tmp_name + tmp_name_len, "/XXXXXX");
174 fd = mkostemp(tmp_name, O_CLOEXEC | O_NOATIME);
175
176 if (fd == -1)
177 return fd;
178
179 if (unlink(tmp_name)) {
180 close(fd);
181 return -1;
182 }
183
184 return fd;
185 }
186
alloc_chunk(sljit_uw size)187 static SLJIT_INLINE struct chunk_header* alloc_chunk(sljit_uw size)
188 {
189 struct chunk_header *retval;
190 int fd;
191
192 fd = create_tempfile();
193 if (fd == -1)
194 return NULL;
195
196 if (ftruncate(fd, size)) {
197 close(fd);
198 return NULL;
199 }
200
201 retval = (struct chunk_header *)mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
202
203 if (retval == MAP_FAILED) {
204 close(fd);
205 return NULL;
206 }
207
208 retval->executable = mmap(NULL, size, PROT_READ | PROT_EXEC, MAP_SHARED, fd, 0);
209
210 if (retval->executable == MAP_FAILED) {
211 munmap((void *)retval, size);
212 close(fd);
213 return NULL;
214 }
215
216 close(fd);
217 return retval;
218 }
219 #else
alloc_chunk(sljit_uw size)220 static SLJIT_INLINE struct chunk_header* alloc_chunk(sljit_uw size)
221 {
222 struct chunk_header *retval;
223 void *maprx;
224
225 retval = (struct chunk_header *)mmap(NULL, size,
226 PROT_MPROTECT(PROT_EXEC|PROT_WRITE|PROT_READ),
227 MAP_ANON, -1, 0);
228
229 if (retval == MAP_FAILED)
230 return NULL;
231
232 maprx = mremap(retval, size, NULL, size, MAP_REMAPDUP);
233 if (maprx == MAP_FAILED) {
234 munmap((void *)retval, size);
235 return NULL;
236 }
237
238 if (mprotect(retval, size, PROT_READ | PROT_WRITE) == -1 ||
239 mprotect(maprx, size, PROT_READ | PROT_EXEC) == -1) {
240 munmap(maprx, size);
241 munmap((void *)retval, size);
242 return NULL;
243 }
244 retval->executable = maprx;
245 return retval;
246 }
247 #endif /* NetBSD >= 8 */
248
free_chunk(void * chunk,sljit_uw size)249 static SLJIT_INLINE void free_chunk(void *chunk, sljit_uw size)
250 {
251 struct chunk_header *header = ((struct chunk_header *)chunk) - 1;
252
253 munmap(header->executable, size);
254 munmap((void *)header, size);
255 }
256
257 /* --------------------------------------------------------------------- */
258 /* Common functions */
259 /* --------------------------------------------------------------------- */
260
261 #define CHUNK_MASK (~(CHUNK_SIZE - 1))
262
263 struct block_header {
264 sljit_uw size;
265 sljit_uw prev_size;
266 sljit_sw executable_offset;
267 };
268
269 struct free_block {
270 struct block_header header;
271 struct free_block *next;
272 struct free_block *prev;
273 sljit_uw size;
274 };
275
276 #define AS_BLOCK_HEADER(base, offset) \
277 ((struct block_header*)(((sljit_u8*)base) + offset))
278 #define AS_FREE_BLOCK(base, offset) \
279 ((struct free_block*)(((sljit_u8*)base) + offset))
280 #define MEM_START(base) ((void*)((base) + 1))
281 #define ALIGN_SIZE(size) (((size) + sizeof(struct block_header) + 7) & ~7)
282
283 static struct free_block* free_blocks;
284 static sljit_uw allocated_size;
285 static sljit_uw total_size;
286
sljit_insert_free_block(struct free_block * free_block,sljit_uw size)287 static SLJIT_INLINE void sljit_insert_free_block(struct free_block *free_block, sljit_uw size)
288 {
289 free_block->header.size = 0;
290 free_block->size = size;
291
292 free_block->next = free_blocks;
293 free_block->prev = NULL;
294 if (free_blocks)
295 free_blocks->prev = free_block;
296 free_blocks = free_block;
297 }
298
sljit_remove_free_block(struct free_block * free_block)299 static SLJIT_INLINE void sljit_remove_free_block(struct free_block *free_block)
300 {
301 if (free_block->next)
302 free_block->next->prev = free_block->prev;
303
304 if (free_block->prev)
305 free_block->prev->next = free_block->next;
306 else {
307 SLJIT_ASSERT(free_blocks == free_block);
308 free_blocks = free_block->next;
309 }
310 }
311
sljit_malloc_exec(sljit_uw size)312 SLJIT_API_FUNC_ATTRIBUTE void* sljit_malloc_exec(sljit_uw size)
313 {
314 struct chunk_header *chunk_header;
315 struct block_header *header;
316 struct block_header *next_header;
317 struct free_block *free_block;
318 sljit_uw chunk_size;
319 sljit_sw executable_offset;
320
321 allocator_grab_lock();
322 if (size < (64 - sizeof(struct block_header)))
323 size = (64 - sizeof(struct block_header));
324 size = ALIGN_SIZE(size);
325
326 free_block = free_blocks;
327 while (free_block) {
328 if (free_block->size >= size) {
329 chunk_size = free_block->size;
330 if (chunk_size > size + 64) {
331 /* We just cut a block from the end of the free block. */
332 chunk_size -= size;
333 free_block->size = chunk_size;
334 header = AS_BLOCK_HEADER(free_block, chunk_size);
335 header->prev_size = chunk_size;
336 header->executable_offset = free_block->header.executable_offset;
337 AS_BLOCK_HEADER(header, size)->prev_size = size;
338 }
339 else {
340 sljit_remove_free_block(free_block);
341 header = (struct block_header*)free_block;
342 size = chunk_size;
343 }
344 allocated_size += size;
345 header->size = size;
346 allocator_release_lock();
347 return MEM_START(header);
348 }
349 free_block = free_block->next;
350 }
351
352 chunk_size = sizeof(struct chunk_header) + sizeof(struct block_header);
353 chunk_size = (chunk_size + size + CHUNK_SIZE - 1) & CHUNK_MASK;
354
355 chunk_header = alloc_chunk(chunk_size);
356 if (!chunk_header) {
357 allocator_release_lock();
358 return NULL;
359 }
360
361 executable_offset = (sljit_sw)((sljit_u8*)chunk_header->executable - (sljit_u8*)chunk_header);
362
363 chunk_size -= sizeof(struct chunk_header) + sizeof(struct block_header);
364 total_size += chunk_size;
365
366 header = (struct block_header *)(chunk_header + 1);
367
368 header->prev_size = 0;
369 header->executable_offset = executable_offset;
370 if (chunk_size > size + 64) {
371 /* Cut the allocated space into a free and a used block. */
372 allocated_size += size;
373 header->size = size;
374 chunk_size -= size;
375
376 free_block = AS_FREE_BLOCK(header, size);
377 free_block->header.prev_size = size;
378 free_block->header.executable_offset = executable_offset;
379 sljit_insert_free_block(free_block, chunk_size);
380 next_header = AS_BLOCK_HEADER(free_block, chunk_size);
381 }
382 else {
383 /* All space belongs to this allocation. */
384 allocated_size += chunk_size;
385 header->size = chunk_size;
386 next_header = AS_BLOCK_HEADER(header, chunk_size);
387 }
388 next_header->size = 1;
389 next_header->prev_size = chunk_size;
390 next_header->executable_offset = executable_offset;
391 allocator_release_lock();
392 return MEM_START(header);
393 }
394
sljit_free_exec(void * ptr)395 SLJIT_API_FUNC_ATTRIBUTE void sljit_free_exec(void* ptr)
396 {
397 struct block_header *header;
398 struct free_block* free_block;
399
400 allocator_grab_lock();
401 header = AS_BLOCK_HEADER(ptr, -(sljit_sw)sizeof(struct block_header));
402 header = AS_BLOCK_HEADER(header, -header->executable_offset);
403 allocated_size -= header->size;
404
405 /* Connecting free blocks together if possible. */
406
407 /* If header->prev_size == 0, free_block will equal to header.
408 In this case, free_block->header.size will be > 0. */
409 free_block = AS_FREE_BLOCK(header, -(sljit_sw)header->prev_size);
410 if (SLJIT_UNLIKELY(!free_block->header.size)) {
411 free_block->size += header->size;
412 header = AS_BLOCK_HEADER(free_block, free_block->size);
413 header->prev_size = free_block->size;
414 }
415 else {
416 free_block = (struct free_block*)header;
417 sljit_insert_free_block(free_block, header->size);
418 }
419
420 header = AS_BLOCK_HEADER(free_block, free_block->size);
421 if (SLJIT_UNLIKELY(!header->size)) {
422 free_block->size += ((struct free_block*)header)->size;
423 sljit_remove_free_block((struct free_block*)header);
424 header = AS_BLOCK_HEADER(free_block, free_block->size);
425 header->prev_size = free_block->size;
426 }
427
428 /* The whole chunk is free. */
429 if (SLJIT_UNLIKELY(!free_block->header.prev_size && header->size == 1)) {
430 /* If this block is freed, we still have (allocated_size / 2) free space. */
431 if (total_size - free_block->size > (allocated_size * 3 / 2)) {
432 total_size -= free_block->size;
433 sljit_remove_free_block(free_block);
434 free_chunk(free_block, free_block->size +
435 sizeof(struct chunk_header) +
436 sizeof(struct block_header));
437 }
438 }
439
440 allocator_release_lock();
441 }
442
sljit_free_unused_memory_exec(void)443 SLJIT_API_FUNC_ATTRIBUTE void sljit_free_unused_memory_exec(void)
444 {
445 struct free_block* free_block;
446 struct free_block* next_free_block;
447
448 allocator_grab_lock();
449
450 free_block = free_blocks;
451 while (free_block) {
452 next_free_block = free_block->next;
453 if (!free_block->header.prev_size &&
454 AS_BLOCK_HEADER(free_block, free_block->size)->size == 1) {
455 total_size -= free_block->size;
456 sljit_remove_free_block(free_block);
457 free_chunk(free_block, free_block->size +
458 sizeof(struct chunk_header) +
459 sizeof(struct block_header));
460 }
461 free_block = next_free_block;
462 }
463
464 SLJIT_ASSERT((total_size && free_blocks) || (!total_size && !free_blocks));
465 allocator_release_lock();
466 }
467
sljit_exec_offset(void * ptr)468 SLJIT_API_FUNC_ATTRIBUTE sljit_sw sljit_exec_offset(void* ptr)
469 {
470 return ((struct block_header *)(ptr))[-1].executable_offset;
471 }
472
