src/external/pcre2-10.32/src/sljit/sljitExecAllocator.c

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