1/*	$NetBSD: sljitExecAllocator.c,v 1.7 2020/09/05 16:30:11 riastradh Exp $	*/
2
3/*
4 *    Stack-less Just-In-Time compiler
5 *
6 *    Copyright Zoltan Herczeg (hzmester@freemail.hu). All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without modification, are
9 * permitted provided that the following conditions are met:
10 *
11 *   1. Redistributions of source code must retain the above copyright notice, this list of
12 *      conditions and the following disclaimer.
13 *
14 *   2. Redistributions in binary form must reproduce the above copyright notice, this list
15 *      of conditions and the following disclaimer in the documentation and/or other materials
16 *      provided with the distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) AND CONTRIBUTORS ``AS IS'' AND ANY
19 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
21 * SHALL THE COPYRIGHT HOLDER(S) OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
23 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
24 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
26 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/*
30   This file contains a simple executable memory allocator
31
32   It is assumed, that executable code blocks are usually medium (or sometimes
33   large) memory blocks, and the allocator is not too frequently called (less
34   optimized than other allocators). Thus, using it as a generic allocator is
35   not suggested.
36
37   How does it work:
38     Memory is allocated in continuous memory areas called chunks by alloc_chunk()
39     Chunk format:
40     [ block ][ block ] ... [ block ][ block terminator ]
41
42   All blocks and the block terminator is started with block_header. The block
43   header contains the size of the previous and the next block. These sizes
44   can also contain special values.
45     Block size:
46       0 - The block is a free_block, with a different size member.
47       1 - The block is a block terminator.
48       n - The block is used at the moment, and the value contains its size.
49     Previous block size:
50       0 - This is the first block of the memory chunk.
51       n - The size of the previous block.
52
53   Using these size values we can go forward or backward on the block chain.
54   The unused blocks are stored in a chain list pointed by free_blocks. This
55   list is useful if we need to find a suitable memory area when the allocator
56   is called.
57
58   When a block is freed, the new free block is connected to its adjacent free
59   blocks if possible.
60
61     [ free block ][ used block ][ free block ]
62   and "used block" is freed, the three blocks are connected together:
63     [           one big free block           ]
64*/
65
66/* --------------------------------------------------------------------- */
67/*  System (OS) functions                                                */
68/* --------------------------------------------------------------------- */
69
70/* 64 KByte. */
71#define CHUNK_SIZE	0x10000
72
73/*
74   alloc_chunk / free_chunk :
75     * allocate executable system memory chunks
76     * the size is always divisible by CHUNK_SIZE
77   allocator_grab_lock / allocator_release_lock :
78     * make the allocator thread safe
79     * can be empty if the OS (or the application) does not support threading
80     * only the allocator requires this lock, sljit is fully thread safe
81       as it only uses local variables
82*/
83
84#ifdef _WIN32
85
86static SLJIT_INLINE void* alloc_chunk(sljit_uw size)
87{
88	return VirtualAlloc(NULL, size, MEM_COMMIT | MEM_RESERVE, PAGE_EXECUTE_READWRITE);
89}
90
91static SLJIT_INLINE void free_chunk(void *chunk, sljit_uw size)
92{
93	SLJIT_UNUSED_ARG(size);
94	VirtualFree(chunk, 0, MEM_RELEASE);
95}
96
97#else
98
99#ifdef _KERNEL
100#include <sys/param.h>
101#include <sys/module.h> /* for module_map */
102#include <uvm/uvm_extern.h>
103#else
104#include <sys/mman.h>
105#endif
106
107static SLJIT_INLINE void* alloc_chunk(sljit_uw size)
108{
109#ifdef _KERNEL
110	return (void *)uvm_km_alloc(module_map, size,
111	    PAGE_SIZE, UVM_KMF_WIRED | UVM_KMF_ZERO | UVM_KMF_EXEC);
112#else
113	void *retval;
114
115#ifdef MAP_ANON
116	retval = mmap(NULL, size, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE | MAP_ANON, -1, 0);
117#else
118	if (dev_zero < 0) {
119		if (open_dev_zero())
120			return NULL;
121	}
122	retval = mmap(NULL, size, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE, dev_zero, 0);
123#endif
124
125	return (retval != MAP_FAILED) ? retval : NULL;
126#endif
127}
128
129static SLJIT_INLINE void free_chunk(void *chunk, sljit_uw size)
130{
131#ifdef _KERNEL
132	uvm_km_free(module_map, (vaddr_t)chunk, size, UVM_KMF_WIRED);
133#else
134	munmap(chunk, size);
135#endif
136}
137
138#endif
139
140/* --------------------------------------------------------------------- */
141/*  Common functions                                                     */
142/* --------------------------------------------------------------------- */
143
144#define CHUNK_MASK	(~(CHUNK_SIZE - 1))
145
146struct block_header {
147	sljit_uw size;
148	sljit_uw prev_size;
149};
150
151struct free_block {
152	struct block_header header;
153	struct free_block *next;
154	struct free_block *prev;
155	sljit_uw size;
156};
157
158#define AS_BLOCK_HEADER(base, offset) \
159	((struct block_header*)(((sljit_u8*)base) + offset))
160#define AS_FREE_BLOCK(base, offset) \
161	((struct free_block*)(((sljit_u8*)base) + offset))
162#define MEM_START(base)		((void*)(((sljit_u8*)base) + sizeof(struct block_header)))
163#define ALIGN_SIZE(size)	(((size) + sizeof(struct block_header) + 7) & ~7)
164
165static struct free_block* free_blocks;
166static sljit_uw allocated_size;
167static sljit_uw total_size;
168
169static SLJIT_INLINE void sljit_insert_free_block(struct free_block *free_block, sljit_uw size)
170{
171	free_block->header.size = 0;
172	free_block->size = size;
173
174	free_block->next = free_blocks;
175	free_block->prev = NULL;
176	if (free_blocks)
177		free_blocks->prev = free_block;
178	free_blocks = free_block;
179}
180
181static SLJIT_INLINE void sljit_remove_free_block(struct free_block *free_block)
182{
183	if (free_block->next)
184		free_block->next->prev = free_block->prev;
185
186	if (free_block->prev)
187		free_block->prev->next = free_block->next;
188	else {
189		SLJIT_ASSERT(free_blocks == free_block);
190		free_blocks = free_block->next;
191	}
192}
193
194SLJIT_API_FUNC_ATTRIBUTE void* sljit_malloc_exec(sljit_uw size)
195{
196	struct block_header *header;
197	struct block_header *next_header;
198	struct free_block *free_block;
199	sljit_uw chunk_size;
200
201	allocator_grab_lock();
202	if (size < (64 - sizeof(struct block_header)))
203		size = (64 - sizeof(struct block_header));
204	size = ALIGN_SIZE(size);
205
206	free_block = free_blocks;
207	while (free_block) {
208		if (free_block->size >= size) {
209			chunk_size = free_block->size;
210			if (chunk_size > size + 64) {
211				/* We just cut a block from the end of the free block. */
212				chunk_size -= size;
213				free_block->size = chunk_size;
214				header = AS_BLOCK_HEADER(free_block, chunk_size);
215				header->prev_size = chunk_size;
216				AS_BLOCK_HEADER(header, size)->prev_size = size;
217			}
218			else {
219				sljit_remove_free_block(free_block);
220				header = (struct block_header*)free_block;
221				size = chunk_size;
222			}
223			allocated_size += size;
224			header->size = size;
225			allocator_release_lock();
226			return MEM_START(header);
227		}
228		free_block = free_block->next;
229	}
230
231	chunk_size = (size + sizeof(struct block_header) + CHUNK_SIZE - 1) & CHUNK_MASK;
232	header = (struct block_header*)alloc_chunk(chunk_size);
233	if (!header) {
234		allocator_release_lock();
235		return NULL;
236	}
237
238	chunk_size -= sizeof(struct block_header);
239	total_size += chunk_size;
240
241	header->prev_size = 0;
242	if (chunk_size > size + 64) {
243		/* Cut the allocated space into a free and a used block. */
244		allocated_size += size;
245		header->size = size;
246		chunk_size -= size;
247
248		free_block = AS_FREE_BLOCK(header, size);
249		free_block->header.prev_size = size;
250		sljit_insert_free_block(free_block, chunk_size);
251		next_header = AS_BLOCK_HEADER(free_block, chunk_size);
252	}
253	else {
254		/* All space belongs to this allocation. */
255		allocated_size += chunk_size;
256		header->size = chunk_size;
257		next_header = AS_BLOCK_HEADER(header, chunk_size);
258	}
259	next_header->size = 1;
260	next_header->prev_size = chunk_size;
261	allocator_release_lock();
262	return MEM_START(header);
263}
264
265SLJIT_API_FUNC_ATTRIBUTE void sljit_free_exec(void* ptr)
266{
267	struct block_header *header;
268	struct free_block* free_block;
269
270	allocator_grab_lock();
271	header = AS_BLOCK_HEADER(ptr, -(sljit_sw)sizeof(struct block_header));
272	allocated_size -= header->size;
273
274	/* Connecting free blocks together if possible. */
275
276	/* If header->prev_size == 0, free_block will equal to header.
277	   In this case, free_block->header.size will be > 0. */
278	free_block = AS_FREE_BLOCK(header, -(sljit_sw)header->prev_size);
279	if (SLJIT_UNLIKELY(!free_block->header.size)) {
280		free_block->size += header->size;
281		header = AS_BLOCK_HEADER(free_block, free_block->size);
282		header->prev_size = free_block->size;
283	}
284	else {
285		free_block = (struct free_block*)header;
286		sljit_insert_free_block(free_block, header->size);
287	}
288
289	header = AS_BLOCK_HEADER(free_block, free_block->size);
290	if (SLJIT_UNLIKELY(!header->size)) {
291		free_block->size += ((struct free_block*)header)->size;
292		sljit_remove_free_block((struct free_block*)header);
293		header = AS_BLOCK_HEADER(free_block, free_block->size);
294		header->prev_size = free_block->size;
295	}
296
297	/* The whole chunk is free. */
298	if (SLJIT_UNLIKELY(!free_block->header.prev_size && header->size == 1)) {
299		/* If this block is freed, we still have (allocated_size / 2) free space. */
300		if (total_size - free_block->size > (allocated_size * 3 / 2)) {
301			total_size -= free_block->size;
302			sljit_remove_free_block(free_block);
303			free_chunk(free_block, free_block->size + sizeof(struct block_header));
304		}
305	}
306
307	allocator_release_lock();
308}
309
310SLJIT_API_FUNC_ATTRIBUTE void sljit_free_unused_memory_exec(void)
311{
312	struct free_block* free_block;
313	struct free_block* next_free_block;
314
315	allocator_grab_lock();
316
317	free_block = free_blocks;
318	while (free_block) {
319		next_free_block = free_block->next;
320		if (!free_block->header.prev_size &&
321				AS_BLOCK_HEADER(free_block, free_block->size)->size == 1) {
322			total_size -= free_block->size;
323			sljit_remove_free_block(free_block);
324			free_chunk(free_block, free_block->size + sizeof(struct block_header));
325		}
326		free_block = next_free_block;
327	}
328
329	SLJIT_ASSERT((total_size && free_blocks) || (!total_size && !free_blocks));
330	allocator_release_lock();
331}
332