sljitExecAllocator.c revision 1.3
1/* 2 * Stack-less Just-In-Time compiler 3 * 4 * Copyright 2009-2012 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/* 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 84static SLJIT_INLINE void* alloc_chunk(sljit_uw size) 85{ 86 return VirtualAlloc(NULL, size, MEM_COMMIT | MEM_RESERVE, PAGE_EXECUTE_READWRITE); 87} 88 89static 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#ifdef _KERNEL 98#include <sys/param.h> 99#include <sys/module.h> /* for module_map */ 100#include <uvm/uvm.h> 101#else 102#include <sys/mman.h> 103#endif 104 105static SLJIT_INLINE void* alloc_chunk(sljit_uw size) 106{ 107#ifdef _KERNEL 108 return (void *)uvm_km_alloc(module_map, size, 109 PAGE_SIZE, UVM_KMF_WIRED | UVM_KMF_ZERO | UVM_KMF_EXEC); 110#else 111 void* retval = mmap(NULL, size, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE | MAP_ANON, -1, 0); 112 return (retval != MAP_FAILED) ? retval : NULL; 113#endif 114} 115 116static SLJIT_INLINE void free_chunk(void* chunk, sljit_uw size) 117{ 118#ifdef _KERNEL 119 uvm_km_free(module_map, (vaddr_t)chunk, size, UVM_KMF_WIRED); 120#else 121 munmap(chunk, size); 122#endif 123} 124 125#endif 126 127/* --------------------------------------------------------------------- */ 128/* Common functions */ 129/* --------------------------------------------------------------------- */ 130 131#define CHUNK_MASK (~(CHUNK_SIZE - 1)) 132 133struct block_header { 134 sljit_uw size; 135 sljit_uw prev_size; 136}; 137 138struct free_block { 139 struct block_header header; 140 struct free_block *next; 141 struct free_block *prev; 142 sljit_uw size; 143}; 144 145#define AS_BLOCK_HEADER(base, offset) \ 146 ((struct block_header*)(((sljit_ub*)base) + offset)) 147#define AS_FREE_BLOCK(base, offset) \ 148 ((struct free_block*)(((sljit_ub*)base) + offset)) 149#define MEM_START(base) ((void*)(((sljit_ub*)base) + sizeof(struct block_header))) 150#define ALIGN_SIZE(size) (((size) + sizeof(struct block_header) + 7) & ~7) 151 152static struct free_block* free_blocks; 153static sljit_uw allocated_size; 154static sljit_uw total_size; 155 156static SLJIT_INLINE void sljit_insert_free_block(struct free_block *free_block, sljit_uw size) 157{ 158 free_block->header.size = 0; 159 free_block->size = size; 160 161 free_block->next = free_blocks; 162 free_block->prev = 0; 163 if (free_blocks) 164 free_blocks->prev = free_block; 165 free_blocks = free_block; 166} 167 168static SLJIT_INLINE void sljit_remove_free_block(struct free_block *free_block) 169{ 170 if (free_block->next) 171 free_block->next->prev = free_block->prev; 172 173 if (free_block->prev) 174 free_block->prev->next = free_block->next; 175 else { 176 SLJIT_ASSERT(free_blocks == free_block); 177 free_blocks = free_block->next; 178 } 179} 180 181SLJIT_API_FUNC_ATTRIBUTE void* sljit_malloc_exec(sljit_uw size) 182{ 183 struct block_header *header; 184 struct block_header *next_header; 185 struct free_block *free_block; 186 sljit_uw chunk_size; 187 188 allocator_grab_lock(); 189 if (size < sizeof(struct free_block)) 190 size = sizeof(struct free_block); 191 size = ALIGN_SIZE(size); 192 193 free_block = free_blocks; 194 while (free_block) { 195 if (free_block->size >= size) { 196 chunk_size = free_block->size; 197 if (chunk_size > size + 64) { 198 /* We just cut a block from the end of the free block. */ 199 chunk_size -= size; 200 free_block->size = chunk_size; 201 header = AS_BLOCK_HEADER(free_block, chunk_size); 202 header->prev_size = chunk_size; 203 AS_BLOCK_HEADER(header, size)->prev_size = size; 204 } 205 else { 206 sljit_remove_free_block(free_block); 207 header = (struct block_header*)free_block; 208 size = chunk_size; 209 } 210 allocated_size += size; 211 header->size = size; 212 allocator_release_lock(); 213 return MEM_START(header); 214 } 215 free_block = free_block->next; 216 } 217 218 chunk_size = (size + sizeof(struct block_header) + CHUNK_SIZE - 1) & CHUNK_MASK; 219 header = (struct block_header*)alloc_chunk(chunk_size); 220 if (!header) { 221 allocator_release_lock(); 222 return NULL; 223 } 224 225 chunk_size -= sizeof(struct block_header); 226 total_size += chunk_size; 227 228 header->prev_size = 0; 229 if (chunk_size > size + 64) { 230 /* Cut the allocated space into a free and a used block. */ 231 allocated_size += size; 232 header->size = size; 233 chunk_size -= size; 234 235 free_block = AS_FREE_BLOCK(header, size); 236 free_block->header.prev_size = size; 237 sljit_insert_free_block(free_block, chunk_size); 238 next_header = AS_BLOCK_HEADER(free_block, chunk_size); 239 } 240 else { 241 /* All space belongs to this allocation. */ 242 allocated_size += chunk_size; 243 header->size = chunk_size; 244 next_header = AS_BLOCK_HEADER(header, chunk_size); 245 } 246 next_header->size = 1; 247 next_header->prev_size = chunk_size; 248 allocator_release_lock(); 249 return MEM_START(header); 250} 251 252SLJIT_API_FUNC_ATTRIBUTE void sljit_free_exec(void* ptr) 253{ 254 struct block_header *header; 255 struct free_block* free_block; 256 257 allocator_grab_lock(); 258 header = AS_BLOCK_HEADER(ptr, -(sljit_sw)sizeof(struct block_header)); 259 allocated_size -= header->size; 260 261 /* Connecting free blocks together if possible. */ 262 263 /* If header->prev_size == 0, free_block will equal to header. 264 In this case, free_block->header.size will be > 0. */ 265 free_block = AS_FREE_BLOCK(header, -(sljit_sw)header->prev_size); 266 if (SLJIT_UNLIKELY(!free_block->header.size)) { 267 free_block->size += header->size; 268 header = AS_BLOCK_HEADER(free_block, free_block->size); 269 header->prev_size = free_block->size; 270 } 271 else { 272 free_block = (struct free_block*)header; 273 sljit_insert_free_block(free_block, header->size); 274 } 275 276 header = AS_BLOCK_HEADER(free_block, free_block->size); 277 if (SLJIT_UNLIKELY(!header->size)) { 278 free_block->size += ((struct free_block*)header)->size; 279 sljit_remove_free_block((struct free_block*)header); 280 header = AS_BLOCK_HEADER(free_block, free_block->size); 281 header->prev_size = free_block->size; 282 } 283 284 /* The whole chunk is free. */ 285 if (SLJIT_UNLIKELY(!free_block->header.prev_size && header->size == 1)) { 286 /* If this block is freed, we still have (allocated_size / 2) free space. */ 287 if (total_size - free_block->size > (allocated_size * 3 / 2)) { 288 total_size -= free_block->size; 289 sljit_remove_free_block(free_block); 290 free_chunk(free_block, free_block->size + sizeof(struct block_header)); 291 } 292 } 293 294 allocator_release_lock(); 295} 296 297SLJIT_API_FUNC_ATTRIBUTE void sljit_free_unused_memory_exec(void) 298{ 299 struct free_block* free_block; 300 struct free_block* next_free_block; 301 302 allocator_grab_lock(); 303 304 free_block = free_blocks; 305 while (free_block) { 306 next_free_block = free_block->next; 307 if (!free_block->header.prev_size && 308 AS_BLOCK_HEADER(free_block, free_block->size)->size == 1) { 309 total_size -= free_block->size; 310 sljit_remove_free_block(free_block); 311 free_chunk(free_block, free_block->size + sizeof(struct block_header)); 312 } 313 free_block = next_free_block; 314 } 315 316 SLJIT_ASSERT((total_size && free_blocks) || (!total_size && !free_blocks)); 317 allocator_release_lock(); 318} 319