"Fossies" - the Fresh Open Source Software Archive

Member "pcre-8.42/sljit/sljitExecAllocator.c" (1 Feb 2017, 10131 Bytes) of package /linux/misc/pcre-8.42.tar.bz2:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "sljitExecAllocator.c" see the Fossies "Dox" file reference documentation and the last Fossies "Diffs" side-by-side code changes report: 8.40_vs_8.41.

    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 /*
   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_u8*)base) + offset))
  141 #define AS_FREE_BLOCK(base, offset) \
  142     ((struct free_block*)(((sljit_u8*)base) + offset))
  143 #define MEM_START(base)     ((void*)(((sljit_u8*)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 = NULL;
  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 < (64 - sizeof(struct block_header)))
  184         size = (64 - sizeof(struct block_header));
  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 }