1///-*-C++-*-//////////////////////////////////////////////////////////////////
2//
3// Hoard: A Fast, Scalable, and Memory-Efficient Allocator
4//        for Shared-Memory Multiprocessors
5// Contact author: Emery Berger, http://www.cs.utexas.edu/users/emery
6//
7// Copyright (c) 1998-2000, The University of Texas at Austin.
8//
9// This library is free software; you can redistribute it and/or modify
10// it under the terms of the GNU Library General Public License as
11// published by the Free Software Foundation, http://www.fsf.org.
12//
13// This library is distributed in the hope that it will be useful, but
14// WITHOUT ANY WARRANTY; without even the implied warranty of
15// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16// Library General Public License for more details.
17//
18//////////////////////////////////////////////////////////////////////////////
19
20#include "arch-specific.h"
21#include "heap.h"
22
23#include <OS.h>
24#include <Debug.h>
25#include <syscalls.h>
26
27#include <libroot_private.h>
28
29#include <stdlib.h>
30#include <unistd.h>
31
32//#define TRACE_CHUNKS
33#ifdef TRACE_CHUNKS
34#	define CTRACE(x) debug_printf x
35#else
36#	define CTRACE(x) ;
37#endif
38
39using namespace BPrivate;
40
41struct free_chunk {
42	free_chunk	*next;
43	size_t		size;
44};
45
46
47static const size_t kInitialHeapSize = 64 * B_PAGE_SIZE;
48	// that's about what hoard allocates anyway (should be kHeapIncrement
49	// aligned)
50
51static const size_t kHeapIncrement = 16 * B_PAGE_SIZE;
52	// the steps in which to increase the heap size (must be a power of 2)
53
54#if B_HAIKU_64_BIT
55static const addr_t kHeapReservationBase = 0x100100000000;
56static const addr_t kHeapReservationSize = 0x1000000000;
57#else
58static const addr_t kHeapReservationBase = 0x18000000;
59static const addr_t kHeapReservationSize = 0x48000000;
60#endif
61
62static area_id sHeapArea;
63static hoardLockType sHeapLock;
64static void *sHeapBase;
65static addr_t sFreeHeapBase;
66static size_t sFreeHeapSize, sHeapAreaSize;
67static free_chunk *sFreeChunks;
68
69
70void
71__init_after_fork(void)
72{
73	// find the heap area
74	sHeapArea = area_for((void*)sFreeHeapBase);
75	if (sHeapArea < 0) {
76		// Where is it gone?
77		debug_printf("hoard: init_after_fork(): thread %" B_PRId32 ", Heap "
78			"area not found! Base address: %p\n", find_thread(NULL),
79			sHeapBase);
80		exit(1);
81	}
82}
83
84
85extern "C" status_t
86__init_heap(void)
87{
88	hoardHeap::initNumProcs();
89
90	// This will locate the heap base at 384 MB and reserve the next 1152 MB
91	// for it. They may get reclaimed by other areas, though, but the maximum
92	// size of the heap is guaranteed until the space is really needed.
93	sHeapBase = (void *)kHeapReservationBase;
94	status_t status = _kern_reserve_address_range((addr_t *)&sHeapBase,
95		B_RANDOMIZED_BASE_ADDRESS, kHeapReservationSize);
96	if (status != B_OK)
97		sHeapBase = NULL;
98
99	uint32 protection = B_READ_AREA | B_WRITE_AREA;
100	if (__gABIVersion < B_HAIKU_ABI_GCC_2_HAIKU)
101		protection |= B_EXECUTE_AREA;
102	sHeapArea = create_area("heap", (void **)&sHeapBase,
103		status == B_OK ? B_EXACT_ADDRESS : B_RANDOMIZED_BASE_ADDRESS,
104		kInitialHeapSize, B_NO_LOCK, protection);
105	if (sHeapArea < B_OK)
106		return sHeapArea;
107
108	sFreeHeapBase = (addr_t)sHeapBase;
109	sHeapAreaSize = kInitialHeapSize;
110
111	hoardLockInit(sHeapLock, "heap");
112
113	return B_OK;
114}
115
116
117extern "C" void
118__heap_terminate_after()
119{
120	// nothing to do
121}
122
123
124static void
125insert_chunk(free_chunk *newChunk)
126{
127	free_chunk *chunk = (free_chunk *)sFreeChunks, *smaller = NULL;
128	for (; chunk != NULL; chunk = chunk->next) {
129		if (chunk->size < newChunk->size)
130			smaller = chunk;
131		else
132			break;
133	}
134
135	if (smaller) {
136		newChunk->next = smaller->next;
137		smaller->next = newChunk;
138	} else {
139		newChunk->next = sFreeChunks;
140		sFreeChunks = newChunk;
141	}
142}
143
144
145namespace BPrivate {
146
147void *
148hoardSbrk(long size)
149{
150	assert(size > 0);
151	CTRACE(("sbrk: size = %ld\n", size));
152
153	// align size request
154	size = (size + hoardHeap::ALIGNMENT - 1) & ~(hoardHeap::ALIGNMENT - 1);
155
156	// choose correct protection flags
157	uint32 protection = B_READ_AREA | B_WRITE_AREA;
158	if (__gABIVersion < B_HAIKU_ABI_GCC_2_HAIKU)
159		protection |= B_EXECUTE_AREA;
160
161	hoardLock(sHeapLock);
162
163	// find chunk in free list
164	free_chunk *chunk = sFreeChunks, *last = NULL;
165	for (; chunk != NULL; chunk = chunk->next) {
166		CTRACE(("  chunk %p (%ld)\n", chunk, chunk->size));
167
168		if (chunk->size < (size_t)size) {
169			last = chunk;
170			continue;
171		}
172
173		// this chunk is large enough to satisfy the request
174
175		SERIAL_PRINT(("HEAP-%" B_PRId32 ": "
176			"found free chunk to hold %ld bytes\n", find_thread(NULL), size));
177
178		void *address = (void *)chunk;
179
180		if (chunk->size > (size_t)size + sizeof(free_chunk)) {
181			// divide this chunk into smaller bits
182			size_t newSize = chunk->size - size;
183			free_chunk *next = chunk->next;
184
185			chunk = (free_chunk *)((addr_t)chunk + size);
186			chunk->next = next;
187			chunk->size = newSize;
188
189			if (last != NULL) {
190				last->next = next;
191				insert_chunk(chunk);
192			} else
193				sFreeChunks = chunk;
194		} else {
195			chunk = chunk->next;
196
197			if (last != NULL)
198				last->next = chunk;
199			else
200				sFreeChunks = chunk;
201		}
202
203		hoardUnlock(sHeapLock);
204		return address;
205	}
206
207	// There was no chunk, let's see if the area is large enough
208
209	size_t oldHeapSize = sFreeHeapSize;
210	sFreeHeapSize += size;
211
212	// round to next heap increment aligned size
213	size_t incrementAlignedSize = (sFreeHeapSize + kHeapIncrement - 1)
214		& ~(kHeapIncrement - 1);
215
216	if (incrementAlignedSize <= sHeapAreaSize) {
217		SERIAL_PRINT(("HEAP-%" B_PRId32 ": heap area large enough for %ld\n",
218			find_thread(NULL), size));
219		// the area is large enough already
220		hoardUnlock(sHeapLock);
221		return (void *)(sFreeHeapBase + oldHeapSize);
222	}
223
224	// We need to grow the area
225
226	SERIAL_PRINT(("HEAP-%" B_PRId32 ": need to resize heap area to %ld "
227		"(%ld requested)\n", find_thread(NULL), incrementAlignedSize, size));
228
229	status_t status = resize_area(sHeapArea, incrementAlignedSize);
230	if (status != B_OK) {
231		// Either the system is out of memory or another area is in the way and
232		// prevents ours from being resized. As a special case of the latter
233		// the user might have mmap()ed something over malloc()ed memory. This
234		// splits the heap area in two, the first one retaining the original
235		// area ID. In either case, if there's still memory, it is a good idea
236		// to try and allocate a new area.
237		sFreeHeapSize = oldHeapSize;
238
239		if (status == B_NO_MEMORY) {
240			hoardUnlock(sHeapLock);
241			return NULL;
242		}
243
244		size_t newHeapSize = (size + kHeapIncrement - 1) / kHeapIncrement
245			* kHeapIncrement;
246
247		// First try at the location directly after the current heap area, if
248		// that is still in the reserved memory region.
249		void* base = (void*)(sFreeHeapBase + sHeapAreaSize);
250		area_id area = -1;
251		if (sHeapBase != NULL
252			&& base >= sHeapBase
253			&& (addr_t)base + newHeapSize
254				<= (addr_t)sHeapBase + kHeapReservationSize) {
255			area = create_area("heap", &base, B_EXACT_ADDRESS, newHeapSize,
256				B_NO_LOCK, protection);
257
258			if (area == B_NO_MEMORY) {
259				hoardUnlock(sHeapLock);
260				return NULL;
261			}
262		}
263
264		// If we don't have an area yet, try again with a free location
265		// allocation.
266		if (area < 0) {
267			base = (void*)(sFreeHeapBase + sHeapAreaSize);
268			area = create_area("heap", &base, B_RANDOMIZED_BASE_ADDRESS,
269				newHeapSize, B_NO_LOCK, protection);
270		}
271
272		if (area < 0) {
273			hoardUnlock(sHeapLock);
274			return NULL;
275		}
276
277		// We have a new area, so make it the new heap area.
278		sHeapArea = area;
279		sFreeHeapBase = (addr_t)base;
280		sHeapAreaSize = newHeapSize;
281		sFreeHeapSize = size;
282		oldHeapSize = 0;
283	} else
284		sHeapAreaSize = incrementAlignedSize;
285
286	hoardUnlock(sHeapLock);
287	return (void *)(sFreeHeapBase + oldHeapSize);
288}
289
290
291void
292hoardUnsbrk(void *ptr, long size)
293{
294	CTRACE(("unsbrk: %p, %ld!\n", ptr, size));
295
296	hoardLock(sHeapLock);
297
298	// TODO: hoard always allocates and frees in typical sizes, so we could
299	//	save a lot of effort if we just had a similar mechanism
300
301	// We add this chunk to our free list - first, try to find an adjacent
302	// chunk, so that we can merge them together
303
304	free_chunk *chunk = (free_chunk *)sFreeChunks, *last = NULL, *smaller = NULL;
305	for (; chunk != NULL; chunk = chunk->next) {
306		if ((addr_t)chunk + chunk->size == (addr_t)ptr
307			|| (addr_t)ptr + size == (addr_t)chunk) {
308			// chunks are adjacent - merge them
309
310			CTRACE(("  found adjacent chunks: %p, %ld\n", chunk, chunk->size));
311			if (last)
312				last->next = chunk->next;
313			else
314				sFreeChunks = chunk->next;
315
316			if ((addr_t)chunk < (addr_t)ptr)
317				chunk->size += size;
318			else {
319				free_chunk *newChunk = (free_chunk *)ptr;
320				newChunk->next = chunk->next;
321				newChunk->size = size + chunk->size;
322				chunk = newChunk;
323			}
324
325			insert_chunk(chunk);
326			hoardUnlock(sHeapLock);
327			return;
328		}
329
330		last = chunk;
331
332		if (chunk->size < (size_t)size)
333			smaller = chunk;
334	}
335
336	// we didn't find an adjacent chunk, so insert the new chunk into the list
337
338	free_chunk *newChunk = (free_chunk *)ptr;
339	newChunk->size = size;
340	if (smaller) {
341		newChunk->next = smaller->next;
342		smaller->next = newChunk;
343	} else {
344		newChunk->next = sFreeChunks;
345		sFreeChunks = newChunk;
346	}
347
348	hoardUnlock(sHeapLock);
349}
350
351
352void
353hoardLockInit(hoardLockType &lock, const char *name)
354{
355	mutex_init_etc(&lock, name, MUTEX_FLAG_ADAPTIVE);
356}
357
358
359void
360hoardLock(hoardLockType &lock)
361{
362	mutex_lock(&lock);
363}
364
365
366void
367hoardUnlock(hoardLockType &lock)
368{
369	mutex_unlock(&lock);
370}
371
372
373void
374hoardYield(void)
375{
376	_kern_thread_yield();
377}
378
379}	// namespace BPrivate
380