Annotation of embedaddon/pcre/sljit/sljitExecAllocator.c, revision 1.1.1.2

1.1       misho       1: /*
                      2:  *    Stack-less Just-In-Time compiler
                      3:  *
1.1.1.2 ! misho       4:  *    Copyright 2009-2012 Zoltan Herczeg (hzmester@freemail.hu). All rights reserved.
1.1       misho       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(0, 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: #include <sys/mman.h>
                     98: 
                     99: static SLJIT_INLINE void* alloc_chunk(sljit_uw size)
                    100: {
                    101:        void* retval = mmap(0, size, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE | MAP_ANON, -1, 0);
                    102:        return (retval != MAP_FAILED) ? retval : NULL;
                    103: }
                    104: 
                    105: static SLJIT_INLINE void free_chunk(void* chunk, sljit_uw size)
                    106: {
                    107:        munmap(chunk, size);
                    108: }
                    109: 
                    110: #endif
                    111: 
                    112: /* --------------------------------------------------------------------- */
                    113: /*  Common functions                                                     */
                    114: /* --------------------------------------------------------------------- */
                    115: 
                    116: #define CHUNK_MASK     (~(CHUNK_SIZE - 1))
                    117: 
                    118: struct block_header {
                    119:        sljit_uw size;
                    120:        sljit_uw prev_size;
                    121: };
                    122: 
                    123: struct free_block {
                    124:        struct block_header header;
                    125:        struct free_block *next;
                    126:        struct free_block *prev;
                    127:        sljit_uw size;
                    128: };
                    129: 
                    130: #define AS_BLOCK_HEADER(base, offset) \
                    131:        ((struct block_header*)(((sljit_ub*)base) + offset))
                    132: #define AS_FREE_BLOCK(base, offset) \
                    133:        ((struct free_block*)(((sljit_ub*)base) + offset))
                    134: #define MEM_START(base)                ((void*)(((sljit_ub*)base) + sizeof(struct block_header)))
                    135: #define ALIGN_SIZE(size)       (((size) + sizeof(struct block_header) + 7) & ~7)
                    136: 
                    137: static struct free_block* free_blocks;
                    138: static sljit_uw allocated_size;
                    139: static sljit_uw total_size;
                    140: 
                    141: static SLJIT_INLINE void sljit_insert_free_block(struct free_block *free_block, sljit_uw size)
                    142: {
                    143:        free_block->header.size = 0;
                    144:        free_block->size = size;
                    145: 
                    146:        free_block->next = free_blocks;
                    147:        free_block->prev = 0;
                    148:        if (free_blocks)
                    149:                free_blocks->prev = free_block;
                    150:        free_blocks = free_block;
                    151: }
                    152: 
                    153: static SLJIT_INLINE void sljit_remove_free_block(struct free_block *free_block)
                    154: {
                    155:        if (free_block->next)
                    156:                free_block->next->prev = free_block->prev;
                    157: 
                    158:        if (free_block->prev)
                    159:                free_block->prev->next = free_block->next;
                    160:        else {
                    161:                SLJIT_ASSERT(free_blocks == free_block);
                    162:                free_blocks = free_block->next;
                    163:        }
                    164: }
                    165: 
                    166: SLJIT_API_FUNC_ATTRIBUTE void* sljit_malloc_exec(sljit_uw size)
                    167: {
                    168:        struct block_header *header;
                    169:        struct block_header *next_header;
                    170:        struct free_block *free_block;
                    171:        sljit_uw chunk_size;
                    172: 
                    173:        allocator_grab_lock();
                    174:        if (size < sizeof(struct free_block))
                    175:                size = sizeof(struct free_block);
                    176:        size = ALIGN_SIZE(size);
                    177: 
                    178:        free_block = free_blocks;
                    179:        while (free_block) {
                    180:                if (free_block->size >= size) {
                    181:                        chunk_size = free_block->size;
                    182:                        if (chunk_size > size + 64) {
                    183:                                /* We just cut a block from the end of the free block. */
                    184:                                chunk_size -= size;
                    185:                                free_block->size = chunk_size;
                    186:                                header = AS_BLOCK_HEADER(free_block, chunk_size);
                    187:                                header->prev_size = chunk_size;
                    188:                                AS_BLOCK_HEADER(header, size)->prev_size = size;
                    189:                        }
                    190:                        else {
                    191:                                sljit_remove_free_block(free_block);
                    192:                                header = (struct block_header*)free_block;
                    193:                                size = chunk_size;
                    194:                        }
                    195:                        allocated_size += size;
                    196:                        header->size = size;
                    197:                        allocator_release_lock();
                    198:                        return MEM_START(header);
                    199:                }
                    200:                free_block = free_block->next;
                    201:        }
                    202: 
                    203:        chunk_size = (size + sizeof(struct block_header) + CHUNK_SIZE - 1) & CHUNK_MASK;
                    204:        header = (struct block_header*)alloc_chunk(chunk_size);
                    205:        PTR_FAIL_IF(!header);
                    206: 
                    207:        chunk_size -= sizeof(struct block_header);
                    208:        total_size += chunk_size;
                    209: 
                    210:        header->prev_size = 0;
                    211:        if (chunk_size > size + 64) {
                    212:                /* Cut the allocated space into a free and a used block. */
                    213:                allocated_size += size;
                    214:                header->size = size;
                    215:                chunk_size -= size;
                    216: 
                    217:                free_block = AS_FREE_BLOCK(header, size);
                    218:                free_block->header.prev_size = size;
                    219:                sljit_insert_free_block(free_block, chunk_size);
                    220:                next_header = AS_BLOCK_HEADER(free_block, chunk_size);
                    221:        }
                    222:        else {
                    223:                /* All space belongs to this allocation. */
                    224:                allocated_size += chunk_size;
                    225:                header->size = chunk_size;
                    226:                next_header = AS_BLOCK_HEADER(header, chunk_size);
                    227:        }
                    228:        next_header->size = 1;
                    229:        next_header->prev_size = chunk_size;
                    230:        allocator_release_lock();
                    231:        return MEM_START(header);
                    232: }
                    233: 
                    234: SLJIT_API_FUNC_ATTRIBUTE void sljit_free_exec(void* ptr)
                    235: {
                    236:        struct block_header *header;
                    237:        struct free_block* free_block;
                    238: 
                    239:        allocator_grab_lock();
                    240:        header = AS_BLOCK_HEADER(ptr, -(sljit_w)sizeof(struct block_header));
                    241:        allocated_size -= header->size;
                    242: 
                    243:        /* Connecting free blocks together if possible. */
                    244: 
                    245:        /* If header->prev_size == 0, free_block will equal to header.
                    246:           In this case, free_block->header.size will be > 0. */
                    247:        free_block = AS_FREE_BLOCK(header, -(sljit_w)header->prev_size);
                    248:        if (SLJIT_UNLIKELY(!free_block->header.size)) {
                    249:                free_block->size += header->size;
                    250:                header = AS_BLOCK_HEADER(free_block, free_block->size);
                    251:                header->prev_size = free_block->size;
                    252:        }
                    253:        else {
                    254:                free_block = (struct free_block*)header;
                    255:                sljit_insert_free_block(free_block, header->size);
                    256:        }
                    257: 
                    258:        header = AS_BLOCK_HEADER(free_block, free_block->size);
                    259:        if (SLJIT_UNLIKELY(!header->size)) {
                    260:                free_block->size += ((struct free_block*)header)->size;
                    261:                sljit_remove_free_block((struct free_block*)header);
                    262:                header = AS_BLOCK_HEADER(free_block, free_block->size);
                    263:                header->prev_size = free_block->size;
                    264:        }
                    265: 
1.1.1.2 ! misho     266:        /* The whole chunk is free. */
1.1       misho     267:        if (SLJIT_UNLIKELY(!free_block->header.prev_size && header->size == 1)) {
1.1.1.2 ! misho     268:                /* If this block is freed, we still have (allocated_size / 2) free space. */
1.1       misho     269:                if (total_size - free_block->size > (allocated_size * 3 / 2)) {
1.1.1.2 ! misho     270:                        total_size -= free_block->size;
1.1       misho     271:                        sljit_remove_free_block(free_block);
                    272:                        free_chunk(free_block, free_block->size + sizeof(struct block_header));
                    273:                }
                    274:        }
                    275: 
                    276:        allocator_release_lock();
                    277: }

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>