sljit/sljitExecAllocator.c

   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
  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 }