Annotation of embedaddon/pcre/sljit/sljitExecAllocator.c, revision 1.1.1.3
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.
1.1.1.3 ! misho 55:
1.1 misho 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: {
1.1.1.3 ! misho 86: return VirtualAlloc(NULL, size, MEM_COMMIT | MEM_RESERVE, PAGE_EXECUTE_READWRITE);
1.1 misho 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: {
1.1.1.3 ! misho 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:
1.1 misho 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_ub*)base) + offset))
141: #define AS_FREE_BLOCK(base, offset) \
142: ((struct free_block*)(((sljit_ub*)base) + offset))
143: #define MEM_START(base) ((void*)(((sljit_ub*)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 = 0;
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);
1.1.1.3 ! misho 214: if (!header) {
! 215: allocator_release_lock();
! 216: return NULL;
! 217: }
1.1 misho 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();
1.1.1.3 ! misho 252: header = AS_BLOCK_HEADER(ptr, -(sljit_sw)sizeof(struct block_header));
1.1 misho 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. */
1.1.1.3 ! misho 259: free_block = AS_FREE_BLOCK(header, -(sljit_sw)header->prev_size);
1.1 misho 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:
1.1.1.2 misho 278: /* The whole chunk is free. */
1.1 misho 279: if (SLJIT_UNLIKELY(!free_block->header.prev_size && header->size == 1)) {
1.1.1.2 misho 280: /* If this block is freed, we still have (allocated_size / 2) free space. */
1.1 misho 281: if (total_size - free_block->size > (allocated_size * 3 / 2)) {
1.1.1.2 misho 282: total_size -= free_block->size;
1.1 misho 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: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to sljitExecAllocator.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / pcre / sljit