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 
alloc_chunk(sljit_uw size)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 
free_chunk(void * chunk,sljit_uw size)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 
alloc_chunk(sljit_uw size)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 
free_chunk(void * chunk,sljit_uw size)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 
sljit_insert_free_block(struct free_block * free_block,sljit_uw size)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 
sljit_remove_free_block(struct free_block * free_block)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 
sljit_malloc_exec(sljit_uw size)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 < (64 - sizeof(struct block_header)))
184 		size = (64 - sizeof(struct block_header));
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 
sljit_free_exec(void * ptr)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 
sljit_free_unused_memory_exec(void)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 }
313