1/*
2 * Copyright 2003-2007, Axel Dörfler, axeld@pinc-software.de. All rights reserved.
3 * Distributed under the terms of the MIT License.
4 */
5
6
7#include "runtime_loader_private.h"
8
9#include <syscalls.h>
10#include <util/kernel_cpp.h>
11
12#include <stdio.h>
13#include <stdlib.h>
14#include <string.h>
15
16
17static const size_t kInitialHeapSize = 65536;
18
19
20/* This is a very simple malloc()/free() implementation - it only
21 * manages a free list.
22 * After heap_init() is called, all free memory is contained in one
23 * big chunk, the only entry in the free link list (which is a single
24 * linked list).
25 * When memory is allocated, the smallest free chunk that contains
26 * the requested size is split (or taken as a whole if it can't be
27 * splitted anymore), and it's lower half will be removed from the
28 * free list.
29 * The free list is ordered by size, starting with the smallest
30 * free chunk available. When a chunk is freed, it will be joint
31 * with its predecessor or successor, if possible.
32 * To ease list handling, the list anchor itself is a free chunk with
33 * size 0 that can't be allocated.
34 */
35
36
37struct free_chunk {
38	size_t		size;
39	free_chunk	*next;
40
41	size_t Size() const;
42	free_chunk *Split(size_t splitSize);
43	bool IsTouching(free_chunk *link);
44	free_chunk *Join(free_chunk *link);
45	void Remove(free_chunk *previous = NULL);
46	void Enqueue();
47
48	void *AllocatedAddress() const;
49	static free_chunk *SetToAllocated(void *allocated);
50};
51
52
53static size_t sAvailable;
54static free_chunk sFreeAnchor;
55
56
57/** Returns the amount of bytes that can be allocated
58 *	in this chunk.
59 */
60
61size_t
62free_chunk::Size() const
63{
64	return size - sizeof(size_t);
65}
66
67
68/**	Splits the upper half at the requested location
69 *	and returns it.
70 */
71
72free_chunk *
73free_chunk::Split(size_t splitSize)
74{
75	free_chunk *chunk = (free_chunk *)((uint8 *)this + sizeof(size_t) + splitSize);
76	chunk->size = size - splitSize - sizeof(size_t);
77	chunk->next = next;
78
79	size = splitSize + sizeof(size_t);
80
81	return chunk;
82}
83
84
85/**	Checks if the specified chunk touches this chunk, so
86 *	that they could be joined.
87 */
88
89bool
90free_chunk::IsTouching(free_chunk *chunk)
91{
92	return chunk
93		&& (((uint8 *)this + size == (uint8 *)chunk)
94			|| (uint8 *)chunk + chunk->size == (uint8 *)this);
95}
96
97
98/**	Joins the chunk to this chunk and returns the pointer
99 *	to the new chunk - which will either be one of the
100 *	two chunks.
101 *	Note, the chunks must be joinable, or else this method
102 *	doesn't work correctly. Use free_chunk::IsTouching()
103 *	to check if this method can be applied.
104 */
105
106free_chunk *
107free_chunk::Join(free_chunk *chunk)
108{
109	if (chunk < this) {
110		chunk->size += size;
111		chunk->next = next;
112
113		return chunk;
114	}
115
116	size += chunk->size;
117	next = chunk->next;
118
119	return this;
120}
121
122
123void
124free_chunk::Remove(free_chunk *previous)
125{
126	if (previous == NULL) {
127		// find the previous chunk in the list
128		free_chunk *chunk = sFreeAnchor.next;
129
130		while (chunk != NULL && chunk != this) {
131			previous = chunk;
132			chunk = chunk->next;
133		}
134
135		if (chunk == NULL) {
136			printf("runtime_loader: try to remove chunk that's not in list");
137			return;
138		}
139	}
140
141	previous->next = this->next;
142	this->next = NULL;
143}
144
145
146void
147free_chunk::Enqueue()
148{
149	free_chunk *chunk = sFreeAnchor.next, *last = &sFreeAnchor;
150	while (chunk && chunk->Size() < size) {
151		last = chunk;
152		chunk = chunk->next;
153	}
154
155	this->next = chunk;
156	last->next = this;
157}
158
159
160void *
161free_chunk::AllocatedAddress() const
162{
163	return (void *)&next;
164}
165
166
167free_chunk *
168free_chunk::SetToAllocated(void *allocated)
169{
170	return (free_chunk *)((uint8 *)allocated - sizeof(size_t));
171}
172
173
174//	#pragma mark - private functions
175
176
177static status_t
178add_area(size_t size)
179{
180	void *base;
181	area_id area = _kern_create_area("rld heap", &base, B_ANY_ADDRESS, size,
182		B_NO_LOCK, B_READ_AREA | B_WRITE_AREA);
183	if (area < B_OK)
184		return area;
185
186	sAvailable += size - sizeof(size_t);
187
188	// declare the whole heap as one chunk, and add it
189	// to the free list
190
191	free_chunk *chunk = (free_chunk *)base;
192	chunk->size = size;
193	chunk->next = sFreeAnchor.next;
194
195	sFreeAnchor.next = chunk;
196	return B_OK;
197}
198
199
200static status_t
201grow_heap(size_t bytes)
202{
203	// align the area size to an 32768 bytes boundary
204	bytes = (bytes + 32767) & ~32767;
205	return add_area(bytes);
206}
207
208
209//	#pragma mark - public API
210
211
212status_t
213heap_init(void)
214{
215	status_t status = add_area(kInitialHeapSize);
216	if (status < B_OK)
217		return status;
218
219	sFreeAnchor.size = 0;
220	return B_OK;
221}
222
223
224#ifdef HEAP_TEST
225void
226dump_chunks(void)
227{
228	free_chunk *chunk = sFreeAnchor.next, *last = &sFreeAnchor;
229	while (chunk != NULL) {
230		last = chunk;
231
232		printf("\t%p: chunk size = %ld, end = %p, next = %p\n", chunk, chunk->size, (uint8 *)chunk + chunk->size, chunk->next);
233		chunk = chunk->next;
234	}
235}
236#endif
237
238
239void *
240realloc(void *allocation, size_t newSize)
241{
242	// free, if new size is 0
243	if (newSize == 0) {
244		free(allocation);
245		return NULL;
246	}
247
248	// just malloc(), if no previous allocation
249	if (allocation == NULL)
250		return malloc(newSize);
251
252	// we're lazy and don't shrink allocations
253	free_chunk* chunk = free_chunk::SetToAllocated(allocation);
254	if (chunk->Size() >= newSize)
255		return allocation;
256
257	// the allocation needs to grow -- allocate a new one and memcpy()
258	void* newAllocation = malloc(newSize);
259	if (newAllocation != NULL) {
260		memcpy(newAllocation, allocation, chunk->Size());
261		free(allocation);
262	}
263
264	return newAllocation;
265}
266
267
268void *
269malloc(size_t size)
270{
271	if (size == 0)
272		return NULL;
273
274	// align the size requirement to an 8 bytes boundary
275	size = (size + 7) & ~7;
276
277restart:
278	if (size > sAvailable) {
279		// try to enlarge heap
280		if (grow_heap(size) < B_OK)
281			return NULL;
282	}
283
284	free_chunk *chunk = sFreeAnchor.next, *last = &sFreeAnchor;
285	while (chunk && chunk->Size() < size) {
286		last = chunk;
287		chunk = chunk->next;
288	}
289
290	if (chunk == NULL) {
291		// could not find a free chunk as large as needed
292		if (grow_heap(size) < B_OK)
293			return NULL;
294
295		goto restart;
296	}
297
298	if (chunk->Size() > size + sizeof(free_chunk) + sizeof(size_t)) {
299		// if this chunk is bigger than the requested size,
300		// we split it to form two chunks (with a minimal
301		// size of sizeof(size_t) allocatable bytes).
302
303		free_chunk *freeChunk = chunk->Split(size);
304		last->next = freeChunk;
305
306		// re-enqueue the free chunk at the correct position
307		freeChunk->Remove(last);
308		freeChunk->Enqueue();
309	} else {
310		// remove the chunk from the free list
311
312		last->next = chunk->next;
313	}
314
315	sAvailable -= size + sizeof(size_t);
316
317	return chunk->AllocatedAddress();
318}
319
320
321void
322free(void *allocated)
323{
324	if (allocated == NULL)
325		return;
326
327	free_chunk *freedChunk = free_chunk::SetToAllocated(allocated);
328	sAvailable += freedChunk->size;
329
330	// try to join the new free chunk with an existing one
331	// it may be joined with up to two chunks
332
333	free_chunk *chunk = sFreeAnchor.next, *last = &sFreeAnchor;
334	int32 joinCount = 0;
335
336	while (chunk) {
337		if (chunk->IsTouching(freedChunk)) {
338			// almost "insert" it into the list before joining
339			// because the next pointer is inherited by the chunk
340			freedChunk->next = chunk->next;
341			freedChunk = chunk->Join(freedChunk);
342
343			// remove the joined chunk from the list
344			last->next = freedChunk->next;
345			chunk = last;
346
347			if (++joinCount == 2)
348				break;
349		}
350
351		last = chunk;
352		chunk = chunk->next;
353	}
354
355	// enqueue the link at the right position; the
356	// free link queue is ordered by size
357
358	freedChunk->Enqueue();
359}
360
361