Home | History | Annotate | Download | only in sljit
      1 /*
      2  *    Stack-less Just-In-Time compiler
      3  *
      4  *    Copyright 2009-2012 Zoltan Herczeg (hzmester (at) 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 /*
     72    alloc_chunk / free_chunk :
     73      * allocate executable system memory chunks
     74      * the size is always divisible by CHUNK_SIZE
     75    allocator_grab_lock / allocator_release_lock :
     76      * make the allocator thread safe
     77      * can be empty if the OS (or the application) does not support threading
     78      * only the allocator requires this lock, sljit is fully thread safe
     79        as it only uses local variables
     80 */
     81 
     82 #ifdef _WIN32
     83 
     84 static SLJIT_INLINE void* alloc_chunk(sljit_uw size)
     85 {
     86 	return VirtualAlloc(NULL, size, MEM_COMMIT | MEM_RESERVE, PAGE_EXECUTE_READWRITE);
     87 }
     88 
     89 static SLJIT_INLINE void free_chunk(void* chunk, sljit_uw size)
     90 {
     91 	SLJIT_UNUSED_ARG(size);
     92 	VirtualFree(chunk, 0, MEM_RELEASE);
     93 }
     94 
     95 #else
     96 
     97 static SLJIT_INLINE void* alloc_chunk(sljit_uw size)
     98 {
     99 	void* retval;
    100 
    101 #ifdef MAP_ANON
    102 	retval = mmap(NULL, size, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE | MAP_ANON, -1, 0);
    103 #else
    104 	if (dev_zero < 0) {
    105 		if (open_dev_zero())
    106 			return NULL;
    107 	}
    108 	retval = mmap(NULL, size, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE, dev_zero, 0);
    109 #endif
    110 
    111 	return (retval != MAP_FAILED) ? retval : NULL;
    112 }
    113 
    114 static SLJIT_INLINE void free_chunk(void* chunk, sljit_uw size)
    115 {
    116 	munmap(chunk, size);
    117 }
    118 
    119 #endif
    120 
    121 /* --------------------------------------------------------------------- */
    122 /*  Common functions                                                     */
    123 /* --------------------------------------------------------------------- */
    124 
    125 #define CHUNK_MASK	(~(CHUNK_SIZE - 1))
    126 
    127 struct block_header {
    128 	sljit_uw size;
    129 	sljit_uw prev_size;
    130 };
    131 
    132 struct free_block {
    133 	struct block_header header;
    134 	struct free_block *next;
    135 	struct free_block *prev;
    136 	sljit_uw size;
    137 };
    138 
    139 #define AS_BLOCK_HEADER(base, offset) \
    140 	((struct block_header*)(((sljit_ub*)base) + offset))
    141 #define AS_FREE_BLOCK(base, offset) \
    142 	((struct free_block*)(((sljit_ub*)base) + offset))
    143 #define MEM_START(base)		((void*)(((sljit_ub*)base) + sizeof(struct block_header)))
    144 #define ALIGN_SIZE(size)	(((size) + sizeof(struct block_header) + 7) & ~7)
    145 
    146 static struct free_block* free_blocks;
    147 static sljit_uw allocated_size;
    148 static sljit_uw total_size;
    149 
    150 static SLJIT_INLINE void sljit_insert_free_block(struct free_block *free_block, sljit_uw size)
    151 {
    152 	free_block->header.size = 0;
    153 	free_block->size = size;
    154 
    155 	free_block->next = free_blocks;
    156 	free_block->prev = 0;
    157 	if (free_blocks)
    158 		free_blocks->prev = free_block;
    159 	free_blocks = free_block;
    160 }
    161 
    162 static SLJIT_INLINE void sljit_remove_free_block(struct free_block *free_block)
    163 {
    164 	if (free_block->next)
    165 		free_block->next->prev = free_block->prev;
    166 
    167 	if (free_block->prev)
    168 		free_block->prev->next = free_block->next;
    169 	else {
    170 		SLJIT_ASSERT(free_blocks == free_block);
    171 		free_blocks = free_block->next;
    172 	}
    173 }
    174 
    175 SLJIT_API_FUNC_ATTRIBUTE void* sljit_malloc_exec(sljit_uw size)
    176 {
    177 	struct block_header *header;
    178 	struct block_header *next_header;
    179 	struct free_block *free_block;
    180 	sljit_uw chunk_size;
    181 
    182 	allocator_grab_lock();
    183 	if (size < sizeof(struct free_block))
    184 		size = sizeof(struct free_block);
    185 	size = ALIGN_SIZE(size);
    186 
    187 	free_block = free_blocks;
    188 	while (free_block) {
    189 		if (free_block->size >= size) {
    190 			chunk_size = free_block->size;
    191 			if (chunk_size > size + 64) {
    192 				/* We just cut a block from the end of the free block. */
    193 				chunk_size -= size;
    194 				free_block->size = chunk_size;
    195 				header = AS_BLOCK_HEADER(free_block, chunk_size);
    196 				header->prev_size = chunk_size;
    197 				AS_BLOCK_HEADER(header, size)->prev_size = size;
    198 			}
    199 			else {
    200 				sljit_remove_free_block(free_block);
    201 				header = (struct block_header*)free_block;
    202 				size = chunk_size;
    203 			}
    204 			allocated_size += size;
    205 			header->size = size;
    206 			allocator_release_lock();
    207 			return MEM_START(header);
    208 		}
    209 		free_block = free_block->next;
    210 	}
    211 
    212 	chunk_size = (size + sizeof(struct block_header) + CHUNK_SIZE - 1) & CHUNK_MASK;
    213 	header = (struct block_header*)alloc_chunk(chunk_size);
    214 	if (!header) {
    215 		allocator_release_lock();
    216 		return NULL;
    217 	}
    218 
    219 	chunk_size -= sizeof(struct block_header);
    220 	total_size += chunk_size;
    221 
    222 	header->prev_size = 0;
    223 	if (chunk_size > size + 64) {
    224 		/* Cut the allocated space into a free and a used block. */
    225 		allocated_size += size;
    226 		header->size = size;
    227 		chunk_size -= size;
    228 
    229 		free_block = AS_FREE_BLOCK(header, size);
    230 		free_block->header.prev_size = size;
    231 		sljit_insert_free_block(free_block, chunk_size);
    232 		next_header = AS_BLOCK_HEADER(free_block, chunk_size);
    233 	}
    234 	else {
    235 		/* All space belongs to this allocation. */
    236 		allocated_size += chunk_size;
    237 		header->size = chunk_size;
    238 		next_header = AS_BLOCK_HEADER(header, chunk_size);
    239 	}
    240 	next_header->size = 1;
    241 	next_header->prev_size = chunk_size;
    242 	allocator_release_lock();
    243 	return MEM_START(header);
    244 }
    245 
    246 SLJIT_API_FUNC_ATTRIBUTE void sljit_free_exec(void* ptr)
    247 {
    248 	struct block_header *header;
    249 	struct free_block* free_block;
    250 
    251 	allocator_grab_lock();
    252 	header = AS_BLOCK_HEADER(ptr, -(sljit_sw)sizeof(struct block_header));
    253 	allocated_size -= header->size;
    254 
    255 	/* Connecting free blocks together if possible. */
    256 
    257 	/* If header->prev_size == 0, free_block will equal to header.
    258 	   In this case, free_block->header.size will be > 0. */
    259 	free_block = AS_FREE_BLOCK(header, -(sljit_sw)header->prev_size);
    260 	if (SLJIT_UNLIKELY(!free_block->header.size)) {
    261 		free_block->size += header->size;
    262 		header = AS_BLOCK_HEADER(free_block, free_block->size);
    263 		header->prev_size = free_block->size;
    264 	}
    265 	else {
    266 		free_block = (struct free_block*)header;
    267 		sljit_insert_free_block(free_block, header->size);
    268 	}
    269 
    270 	header = AS_BLOCK_HEADER(free_block, free_block->size);
    271 	if (SLJIT_UNLIKELY(!header->size)) {
    272 		free_block->size += ((struct free_block*)header)->size;
    273 		sljit_remove_free_block((struct free_block*)header);
    274 		header = AS_BLOCK_HEADER(free_block, free_block->size);
    275 		header->prev_size = free_block->size;
    276 	}
    277 
    278 	/* The whole chunk is free. */
    279 	if (SLJIT_UNLIKELY(!free_block->header.prev_size && header->size == 1)) {
    280 		/* If this block is freed, we still have (allocated_size / 2) free space. */
    281 		if (total_size - free_block->size > (allocated_size * 3 / 2)) {
    282 			total_size -= free_block->size;
    283 			sljit_remove_free_block(free_block);
    284 			free_chunk(free_block, free_block->size + sizeof(struct block_header));
    285 		}
    286 	}
    287 
    288 	allocator_release_lock();
    289 }
    290 
    291 SLJIT_API_FUNC_ATTRIBUTE void sljit_free_unused_memory_exec(void)
    292 {
    293 	struct free_block* free_block;
    294 	struct free_block* next_free_block;
    295 
    296 	allocator_grab_lock();
    297 
    298 	free_block = free_blocks;
    299 	while (free_block) {
    300 		next_free_block = free_block->next;
    301 		if (!free_block->header.prev_size &&
    302 				AS_BLOCK_HEADER(free_block, free_block->size)->size == 1) {
    303 			total_size -= free_block->size;
    304 			sljit_remove_free_block(free_block);
    305 			free_chunk(free_block, free_block->size + sizeof(struct block_header));
    306 		}
    307 		free_block = next_free_block;
    308 	}
    309 
    310 	SLJIT_ASSERT((total_size && free_blocks) || (!total_size && !free_blocks));
    311 	allocator_release_lock();
    312 }
    313