../3rdparty/pcre/sljit/sljitExecAllocator.c

Source codeSwitch to Preprocessed file
LineSource CodeCoverage
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 -
84static SLJIT_INLINE void* alloc_chunk(sljit_uw size) -
85{ -
86 return VirtualAlloc(0, size, MEM_COMMIT | MEM_RESERVE, PAGE_EXECUTE_READWRITE); -
87} -
88 -
89static 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 -
99static 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);
executed (the execution status of this line is deduced): void* retval = mmap(0, size, 0x1 | 0x2 | 0x4, 0x02 | 0x20, -1, 0);
-
102 return (retval != MAP_FAILED) ? retval : NULL;
executed: return (retval != ((void *) -1)) ? retval : ((void *)0);
Execution Count:2
2
103} -
104 -
105static SLJIT_INLINE void free_chunk(void* chunk, sljit_uw size) -
106{ -
107 munmap(chunk, size);
never executed (the execution status of this line is deduced): munmap(chunk, size);
-
108}
never executed: }
0
109 -
110#endif -
111 -
112/* --------------------------------------------------------------------- */ -
113/* Common functions */ -
114/* --------------------------------------------------------------------- */ -
115 -
116#define CHUNK_MASK (~(CHUNK_SIZE - 1)) -
117 -
118struct block_header { -
119 sljit_uw size; -
120 sljit_uw prev_size; -
121}; -
122 -
123struct 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 -
137static struct free_block* free_blocks; -
138static sljit_uw allocated_size; -
139static sljit_uw total_size; -
140 -
141static SLJIT_INLINE void sljit_insert_free_block(struct free_block *free_block, sljit_uw size) -
142{ -
143 free_block->header.size = 0;
executed (the execution status of this line is deduced): free_block->header.size = 0;
-
144 free_block->size = size;
executed (the execution status of this line is deduced): free_block->size = size;
-
145 -
146 free_block->next = free_blocks;
executed (the execution status of this line is deduced): free_block->next = free_blocks;
-
147 free_block->prev = 0;
executed (the execution status of this line is deduced): free_block->prev = 0;
-
148 if (free_blocks)
evaluated: free_blocks
TRUEFALSE
yes
Evaluation Count:7
yes
Evaluation Count:2
2-7
149 free_blocks->prev = free_block;
executed: free_blocks->prev = free_block;
Execution Count:7
7
150 free_blocks = free_block;
executed (the execution status of this line is deduced): free_blocks = free_block;
-
151}
executed: }
Execution Count:9
9
152 -
153static SLJIT_INLINE void sljit_remove_free_block(struct free_block *free_block) -
154{ -
155 if (free_block->next)
evaluated: free_block->next
TRUEFALSE
yes
Evaluation Count:5
yes
Evaluation Count:2
2-5
156 free_block->next->prev = free_block->prev;
executed: free_block->next->prev = free_block->prev;
Execution Count:5
5
157 -
158 if (free_block->prev)
evaluated: free_block->prev
TRUEFALSE
yes
Evaluation Count:6
yes
Evaluation Count:1
1-6
159 free_block->prev->next = free_block->next;
executed: free_block->prev->next = free_block->next;
Execution Count:6
6
160 else { -
161 SLJIT_ASSERT(free_blocks == free_block);
executed: }
Execution Count:1
partially evaluated: 0
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:1
0-1
162 free_blocks = free_block->next;
executed (the execution status of this line is deduced): free_blocks = free_block->next;
-
163 }
executed: }
Execution Count:1
1
164} -
165 -
166SLJIT_API_FUNC_ATTRIBUTE void* sljit_malloc_exec(sljit_uw size) -
167{ -
168 struct block_header *header;
executed (the execution status of this line is deduced): struct block_header *header;
-
169 struct block_header *next_header;
executed (the execution status of this line is deduced): struct block_header *next_header;
-
170 struct free_block *free_block;
executed (the execution status of this line is deduced): struct free_block *free_block;
-
171 sljit_uw chunk_size;
executed (the execution status of this line is deduced): sljit_uw chunk_size;
-
172 -
173 allocator_grab_lock();
executed (the execution status of this line is deduced): allocator_grab_lock();
-
174 if (size < sizeof(struct free_block))
partially evaluated: size < sizeof(struct free_block)
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:15
0-15
175 size = sizeof(struct free_block);
never executed: size = sizeof(struct free_block);
0
176 size = ALIGN_SIZE(size);
executed (the execution status of this line is deduced): size = (((size) + sizeof(struct block_header) + 7) & ~7);
-
177 -
178 free_block = free_blocks;
executed (the execution status of this line is deduced): free_block = free_blocks;
-
179 while (free_block) {
evaluated: free_block
TRUEFALSE
yes
Evaluation Count:13
yes
Evaluation Count:2
2-13
180 if (free_block->size >= size) {
partially evaluated: free_block->size >= size
TRUEFALSE
yes
Evaluation Count:13
no
Evaluation Count:0
0-13
181 chunk_size = free_block->size;
executed (the execution status of this line is deduced): chunk_size = free_block->size;
-
182 if (chunk_size > size + 64) {
partially evaluated: chunk_size > size + 64
TRUEFALSE
yes
Evaluation Count:13
no
Evaluation Count:0
0-13
183 /* We just cut a block from the end of the free block. */ -
184 chunk_size -= size;
executed (the execution status of this line is deduced): chunk_size -= size;
-
185 free_block->size = chunk_size;
executed (the execution status of this line is deduced): free_block->size = chunk_size;
-
186 header = AS_BLOCK_HEADER(free_block, chunk_size);
executed (the execution status of this line is deduced): header = ((struct block_header*)(((sljit_ub*)free_block) + chunk_size));
-
187 header->prev_size = chunk_size;
executed (the execution status of this line is deduced): header->prev_size = chunk_size;
-
188 AS_BLOCK_HEADER(header, size)->prev_size = size;
executed (the execution status of this line is deduced): ((struct block_header*)(((sljit_ub*)header) + size))->prev_size = size;
-
189 }
executed: }
Execution Count:13
13
190 else { -
191 sljit_remove_free_block(free_block);
never executed (the execution status of this line is deduced): sljit_remove_free_block(free_block);
-
192 header = (struct block_header*)free_block;
never executed (the execution status of this line is deduced): header = (struct block_header*)free_block;
-
193 size = chunk_size;
never executed (the execution status of this line is deduced): size = chunk_size;
-
194 }
never executed: }
0
195 allocated_size += size;
executed (the execution status of this line is deduced): allocated_size += size;
-
196 header->size = size;
executed (the execution status of this line is deduced): header->size = size;
-
197 allocator_release_lock();
executed (the execution status of this line is deduced): allocator_release_lock();
-
198 return MEM_START(header);
executed: return ((void*)(((sljit_ub*)header) + sizeof(struct block_header)));
Execution Count:13
13
199 } -
200 free_block = free_block->next;
never executed (the execution status of this line is deduced): free_block = free_block->next;
-
201 }
never executed: }
0
202 -
203 chunk_size = (size + sizeof(struct block_header) + CHUNK_SIZE - 1) & CHUNK_MASK;
executed (the execution status of this line is deduced): chunk_size = (size + sizeof(struct block_header) + 0x10000 - 1) & (~(0x10000 - 1));
-
204 header = (struct block_header*)alloc_chunk(chunk_size);
executed (the execution status of this line is deduced): header = (struct block_header*)alloc_chunk(chunk_size);
-
205 PTR_FAIL_IF(!header);
never executed: return ((void *)0);
executed: }
Execution Count:2
partially evaluated: __builtin_expect((!header), 0)
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:2
partially evaluated: 0
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:2
0-2
206 -
207 chunk_size -= sizeof(struct block_header);
executed (the execution status of this line is deduced): chunk_size -= sizeof(struct block_header);
-
208 total_size += chunk_size;
executed (the execution status of this line is deduced): total_size += chunk_size;
-
209 -
210 header->prev_size = 0;
executed (the execution status of this line is deduced): header->prev_size = 0;
-
211 if (chunk_size > size + 64) {
partially evaluated: chunk_size > size + 64
TRUEFALSE
yes
Evaluation Count:2
no
Evaluation Count:0
0-2
212 /* Cut the allocated space into a free and a used block. */ -
213 allocated_size += size;
executed (the execution status of this line is deduced): allocated_size += size;
-
214 header->size = size;
executed (the execution status of this line is deduced): header->size = size;
-
215 chunk_size -= size;
executed (the execution status of this line is deduced): chunk_size -= size;
-
216 -
217 free_block = AS_FREE_BLOCK(header, size);
executed (the execution status of this line is deduced): free_block = ((struct free_block*)(((sljit_ub*)header) + size));
-
218 free_block->header.prev_size = size;
executed (the execution status of this line is deduced): free_block->header.prev_size = size;
-
219 sljit_insert_free_block(free_block, chunk_size);
executed (the execution status of this line is deduced): sljit_insert_free_block(free_block, chunk_size);
-
220 next_header = AS_BLOCK_HEADER(free_block, chunk_size);
executed (the execution status of this line is deduced): next_header = ((struct block_header*)(((sljit_ub*)free_block) + chunk_size));
-
221 }
executed: }
Execution Count:2
2
222 else { -
223 /* All space belongs to this allocation. */ -
224 allocated_size += chunk_size;
never executed (the execution status of this line is deduced): allocated_size += chunk_size;
-
225 header->size = chunk_size;
never executed (the execution status of this line is deduced): header->size = chunk_size;
-
226 next_header = AS_BLOCK_HEADER(header, chunk_size);
never executed (the execution status of this line is deduced): next_header = ((struct block_header*)(((sljit_ub*)header) + chunk_size));
-
227 }
never executed: }
0
228 next_header->size = 1;
executed (the execution status of this line is deduced): next_header->size = 1;
-
229 next_header->prev_size = chunk_size;
executed (the execution status of this line is deduced): next_header->prev_size = chunk_size;
-
230 allocator_release_lock();
executed (the execution status of this line is deduced): allocator_release_lock();
-
231 return MEM_START(header);
executed: return ((void*)(((sljit_ub*)header) + sizeof(struct block_header)));
Execution Count:2
2
232} -
233 -
234SLJIT_API_FUNC_ATTRIBUTE void sljit_free_exec(void* ptr) -
235{ -
236 struct block_header *header;
executed (the execution status of this line is deduced): struct block_header *header;
-
237 struct free_block* free_block;
executed (the execution status of this line is deduced): struct free_block* free_block;
-
238 -
239 allocator_grab_lock();
executed (the execution status of this line is deduced): allocator_grab_lock();
-
240 header = AS_BLOCK_HEADER(ptr, -(sljit_w)sizeof(struct block_header));
executed (the execution status of this line is deduced): header = ((struct block_header*)(((sljit_ub*)ptr) + -(sljit_w)sizeof(struct block_header)));
-
241 allocated_size -= header->size;
executed (the execution status of this line is deduced): 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);
executed (the execution status of this line is deduced): free_block = ((struct free_block*)(((sljit_ub*)header) + -(sljit_w)header->prev_size));
-
248 if (SLJIT_UNLIKELY(!free_block->header.size)) {
evaluated: __builtin_expect((!free_block->header.size), 0)
TRUEFALSE
yes
Evaluation Count:8
yes
Evaluation Count:7
7-8
249 free_block->size += header->size;
executed (the execution status of this line is deduced): free_block->size += header->size;
-
250 header = AS_BLOCK_HEADER(free_block, free_block->size);
executed (the execution status of this line is deduced): header = ((struct block_header*)(((sljit_ub*)free_block) + free_block->size));
-
251 header->prev_size = free_block->size;
executed (the execution status of this line is deduced): header->prev_size = free_block->size;
-
252 }
executed: }
Execution Count:8
8
253 else { -
254 free_block = (struct free_block*)header;
executed (the execution status of this line is deduced): free_block = (struct free_block*)header;
-
255 sljit_insert_free_block(free_block, header->size);
executed (the execution status of this line is deduced): sljit_insert_free_block(free_block, header->size);
-
256 }
executed: }
Execution Count:7
7
257 -
258 header = AS_BLOCK_HEADER(free_block, free_block->size);
executed (the execution status of this line is deduced): header = ((struct block_header*)(((sljit_ub*)free_block) + free_block->size));
-
259 if (SLJIT_UNLIKELY(!header->size)) {
evaluated: __builtin_expect((!header->size), 0)
TRUEFALSE
yes
Evaluation Count:7
yes
Evaluation Count:8
7-8
260 free_block->size += ((struct free_block*)header)->size;
executed (the execution status of this line is deduced): free_block->size += ((struct free_block*)header)->size;
-
261 sljit_remove_free_block((struct free_block*)header);
executed (the execution status of this line is deduced): sljit_remove_free_block((struct free_block*)header);
-
262 header = AS_BLOCK_HEADER(free_block, free_block->size);
executed (the execution status of this line is deduced): header = ((struct block_header*)(((sljit_ub*)free_block) + free_block->size));
-
263 header->prev_size = free_block->size;
executed (the execution status of this line is deduced): header->prev_size = free_block->size;
-
264 }
executed: }
Execution Count:7
7
265 -
266 /* The whole chunk is free. */ -
267 if (SLJIT_UNLIKELY(!free_block->header.prev_size && header->size == 1)) {
evaluated: __builtin_expect((!free_block->header.prev_size && header->size == 1), 0)
TRUEFALSE
yes
Evaluation Count:9
yes
Evaluation Count:6
6-9
268 /* If this block is freed, we still have (allocated_size / 2) free space. */ -
269 if (total_size - free_block->size > (allocated_size * 3 / 2)) {
partially evaluated: total_size - free_block->size > (allocated_size * 3 / 2)
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:9
0-9
270 total_size -= free_block->size;
never executed (the execution status of this line is deduced): total_size -= free_block->size;
-
271 sljit_remove_free_block(free_block);
never executed (the execution status of this line is deduced): sljit_remove_free_block(free_block);
-
272 free_chunk(free_block, free_block->size + sizeof(struct block_header));
never executed (the execution status of this line is deduced): free_chunk(free_block, free_block->size + sizeof(struct block_header));
-
273 }
never executed: }
0
274 }
executed: }
Execution Count:9
9
275 -
276 allocator_release_lock();
executed (the execution status of this line is deduced): allocator_release_lock();
-
277}
executed: }
Execution Count:15
15
278 -
Source codeSwitch to Preprocessed file
Generated by Squish Coco Non-Commercial