chiark / gitweb /
Commit upstream pcre-8.39.tar.bz2
[pcre3.git] / 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_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 < 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 }