trunk/sljit/sljitExecAllocator.c

/*
 *    Stack-less Just-In-Time compiler
 *
 *    Copyright 2009-2010 Zoltan Herczeg (hzmester@freemail.hu). All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without modification, are
 * permitted provided that the following conditions are met:
 *
 *   1. Redistributions of source code must retain the above copyright notice, this list of
 *      conditions and the following disclaimer.
 *
 *   2. Redistributions in binary form must reproduce the above copyright notice, this list
 *      of conditions and the following disclaimer in the documentation and/or other materials
 *      provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) AND CONTRIBUTORS ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
 * SHALL THE COPYRIGHT HOLDER(S) OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/*
   This file contains a simple executable memory allocator

   It is assumed, that executable code blocks are usually medium (or sometimes
   large) memory blocks, and the allocator is not too frequently called (less
   optimized than other allocators). Thus, using it as a generic allocator is
   not suggested.

   How does it work:
     Memory is allocated in continuous memory areas called chunks by alloc_chunk()
     Chunk format:
     [ block ][ block ] ... [ block ][ block terminator ]

   All blocks and the block terminator is started with block_header. The block
   header contains the size of the previous and the next block. These sizes
   can also contain special values.
     Block size:
       0 - The block is a free_block, with a different size member.
       1 - The block is a block terminator.
       n - The block is used at the moment, and the value contains its size.
     Previous block size:
       0 - This is the first block of the memory chunk.
       n - The size of the previous block.

   Using these size values we can go forward or backward on the block chain.
   The unused blocks are stored in a chain list pointed by free_blocks. This
   list is useful if we need to find a suitable memory area when the allocator
   is called.
 
   When a block is freed, the new free block is connected to its adjacent free
   blocks if possible.

     [ free block ][ used block ][ free block ]
   and "used block" is freed, the three blocks are connected together:
     [           one big free block           ]
*/

/* --------------------------------------------------------------------- */
/*  System (OS) functions                                                */
/* --------------------------------------------------------------------- */

/* 64 KByte. */
#define CHUNK_SIZE      0x10000

/*
   alloc_chunk / free_chunk :
     * allocate executable system memory chunks
     * the size is always divisible by CHUNK_SIZE
   allocator_grab_lock / allocator_release_lock :
     * make the allocator thread safe
     * can be empty if the OS (or the application) does not support threading
     * only the allocator requires this lock, sljit is fully thread safe
       as it only uses local variables
*/

#ifdef _WIN32

static SLJIT_INLINE void* alloc_chunk(sljit_uw size)
{
        return VirtualAlloc(0, size, MEM_COMMIT | MEM_RESERVE, PAGE_EXECUTE_READWRITE);
}

static SLJIT_INLINE void free_chunk(void* chunk, sljit_uw size)
{
        SLJIT_UNUSED_ARG(size);
        VirtualFree(chunk, 0, MEM_RELEASE);
}

#else

#include <sys/mman.h>

static SLJIT_INLINE void* alloc_chunk(sljit_uw size)
{
        void* retval = mmap(0, size, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE | MAP_ANON, -1, 0);
        return (retval != MAP_FAILED) ? retval : NULL;
}

static SLJIT_INLINE void free_chunk(void* chunk, sljit_uw size)
{
        munmap(chunk, size);
}

#endif

/* --------------------------------------------------------------------- */
/*  Common functions                                                     */
/* --------------------------------------------------------------------- */

#define CHUNK_MASK      (~(CHUNK_SIZE - 1))

struct block_header {
        sljit_uw size;
        sljit_uw prev_size;
};

struct free_block {
        struct block_header header;
        struct free_block *next;
        struct free_block *prev;
        sljit_uw size;
};

#define AS_BLOCK_HEADER(base, offset) \
        ((struct block_header*)(((sljit_ub*)base) + offset))
#define AS_FREE_BLOCK(base, offset) \
        ((struct free_block*)(((sljit_ub*)base) + offset))
#define MEM_START(base)         ((void*)(((sljit_ub*)base) + sizeof(struct block_header)))
#define ALIGN_SIZE(size)        (((size) + sizeof(struct block_header) + 7) & ~7)

static struct free_block* free_blocks;
static sljit_uw allocated_size;
static sljit_uw total_size;

static SLJIT_INLINE void sljit_insert_free_block(struct free_block *free_block, sljit_uw size)
{
        free_block->header.size = 0;
        free_block->size = size;

        free_block->next = free_blocks;
        free_block->prev = 0;
        if (free_blocks)
                free_blocks->prev = free_block;
        free_blocks = free_block;
}

static SLJIT_INLINE void sljit_remove_free_block(struct free_block *free_block)
{
        if (free_block->next)
                free_block->next->prev = free_block->prev;

        if (free_block->prev)
                free_block->prev->next = free_block->next;
        else {
                SLJIT_ASSERT(free_blocks == free_block);
                free_blocks = free_block->next;
        }
}

void* sljit_malloc_exec(sljit_uw size)
{
        struct block_header *header;
        struct block_header *next_header;
        struct free_block *free_block;
        sljit_uw chunk_size;

        allocator_grab_lock();
        if (size < sizeof(struct free_block))
                size = sizeof(struct free_block);
        size = ALIGN_SIZE(size);

        free_block = free_blocks;
        while (free_block) {
                if (free_block->size >= size) {
                        chunk_size = free_block->size;
                        if (chunk_size > size + 64) {
                                /* We just cut a block from the end of the free block. */
                                chunk_size -= size;
                                free_block->size = chunk_size;
                                header = AS_BLOCK_HEADER(free_block, chunk_size);
                                header->prev_size = chunk_size;
                                AS_BLOCK_HEADER(header, size)->prev_size = size;
                        }
                        else {
                                sljit_remove_free_block(free_block);
                                header = (struct block_header*)free_block;
                                size = chunk_size;
                        }
                        allocated_size += size;
                        header->size = size;
                        allocator_release_lock();
                        return MEM_START(header);
                }
                free_block = free_block->next;
        }

        chunk_size = (size + sizeof(struct block_header) + CHUNK_SIZE - 1) & CHUNK_MASK;
        header = (struct block_header*)alloc_chunk(chunk_size);
        PTR_FAIL_IF(!header);

        chunk_size -= sizeof(struct block_header);
        total_size += chunk_size;

        header->prev_size = 0;
        if (chunk_size > size + 64) {
                /* Cut the allocated space into a free and a used block. */
                allocated_size += size;
                header->size = size;
                chunk_size -= size;

                free_block = AS_FREE_BLOCK(header, size);
                free_block->header.prev_size = size;
                sljit_insert_free_block(free_block, chunk_size);
                next_header = AS_BLOCK_HEADER(free_block, chunk_size);
        }
        else {
                /* All space belongs to this allocation. */
                allocated_size += chunk_size;
                header->size = chunk_size;
                next_header = AS_BLOCK_HEADER(header, chunk_size);
        }
        next_header->size = 1;
        next_header->prev_size = chunk_size;
        allocator_release_lock();
        return MEM_START(header);
}

void sljit_free_exec(void* ptr)
{
        struct block_header *header;
        struct free_block* free_block;

        allocator_grab_lock();
        header = AS_BLOCK_HEADER(ptr, -(sljit_w)sizeof(struct block_header));
        allocated_size -= header->size;

        /* Connecting free blocks together if possible. */

        /* If header->prev_size == 0, free_block will equal to header.
           In this case, free_block->header.size will be > 0. */
        free_block = AS_FREE_BLOCK(header, -(sljit_w)header->prev_size);
        if (SLJIT_UNLIKELY(!free_block->header.size)) {
                free_block->size += header->size;
                header = AS_BLOCK_HEADER(free_block, free_block->size);
                header->prev_size = free_block->size;
        }
        else {
                free_block = (struct free_block*)header;
                sljit_insert_free_block(free_block, header->size);
        }

        header = AS_BLOCK_HEADER(free_block, free_block->size);
        if (SLJIT_UNLIKELY(!header->size)) {
                free_block->size += ((struct free_block*)header)->size;
                sljit_remove_free_block((struct free_block*)header);
                header = AS_BLOCK_HEADER(free_block, free_block->size);
                header->prev_size = free_block->size;
        }

        if (SLJIT_UNLIKELY(!free_block->header.prev_size && header->size == 1)) {
                if (total_size - free_block->size > (allocated_size * 3 / 2)) {
                        sljit_remove_free_block(free_block);
                        free_chunk(free_block, free_block->size + sizeof(struct block_header));
                }
        }

        allocator_release_lock();
}
1	ph10	662	/*
2			* Stack-less Just-In-Time compiler
3			*
4			* Copyright 2009-2010 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(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			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			void sljit_free_exec(void* ptr)
235			{
236			struct block_header *header;
237			struct free_block* free_block;
238
239			allocator_grab_lock();
240	zherczeg	715	header = AS_BLOCK_HEADER(ptr, -(sljit_w)sizeof(struct block_header));
241	ph10	662	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	zherczeg	715	free_block = AS_FREE_BLOCK(header, -(sljit_w)header->prev_size);
248	ph10	662	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
266			if (SLJIT_UNLIKELY(!free_block->header.prev_size && header->size == 1)) {
267			if (total_size - free_block->size > (allocated_size * 3 / 2)) {
268			sljit_remove_free_block(free_block);
269			free_chunk(free_block, free_block->size + sizeof(struct block_header));
270			}
271			}
272
273			allocator_release_lock();
274			}