1/*
2 * Copyright 2009-2010, Ingo Weinhold, ingo_weinhold@gmx.de
3 * Distributed under the terms of the MIT License.
4 */
5
6
7#include <debug_heap.h>
8
9#include <new>
10
11#include <util/AutoLock.h>
12#include <vm/vm.h>
13
14
15#define INITIAL_DEBUG_HEAP_SIZE	B_PAGE_SIZE
16
17static char sInitialHeap[INITIAL_DEBUG_HEAP_SIZE] __attribute__ ((aligned (8)));
18static void* sHeapBase = sInitialHeap;
19static size_t sHeapSize = INITIAL_DEBUG_HEAP_SIZE;
20
21const kdebug_alloc_t kdebug_alloc = {};
22
23
24struct allocation_header {
25	uint32	size : 31;	// size in allocation_header units
26	bool	free : 1;
27	uint32	previous;
28};
29
30struct free_entry : allocation_header {
31	uint32	previous_free;
32	uint32	next_free;
33};
34
35
36struct DebugAllocPool {
37	void Init(void* heap, size_t heapSize)
38	{
39		fParent = NULL;
40		fChild = NULL;
41
42		uint32 size = heapSize / 8;
43		fBase = (allocation_header*)heap - 1;
44		fEnd = size + 1;
45		fFirstFree = 0;
46		fLastFree = 0;
47
48		// add free entry spanning the whole area
49		fBase[1].size = size - 1;
50		fBase[1].previous = 0;
51		_InsertFreeEntry(1);
52	}
53
54	DebugAllocPool* CreateChildPool()
55	{
56		// do we already have a child pool?
57		if (fChild != NULL)
58			return NULL;
59
60		// create the pool object
61		DebugAllocPool* pool
62			= (DebugAllocPool*)Allocate(sizeof(DebugAllocPool));
63		if (pool == NULL)
64			return NULL;
65
66		// do we have enough free space?
67		if (fLastFree == 0 || fBase[fLastFree].size < 2) {
68			Free(pool);
69			return NULL;
70		}
71
72		allocation_header* header = &fBase[fLastFree];
73		_RemoveFreeEntry(fLastFree);
74
75		pool->Init(header + 1, header->size * 8);
76		pool->fParent = this;
77
78		return fChild = pool;
79	}
80
81	void Destroy()
82	{
83		if (fParent != NULL) {
84			fParent->fChild = NULL;
85			fParent->Free(fBase + 1);
86		}
87	}
88
89	DebugAllocPool* Parent() const
90	{
91		return fParent;
92	}
93
94	void* Allocate(size_t size)
95	{
96		size = (size + 7) / 8;
97		uint32 index = fFirstFree;
98		while (index != 0 && fBase[index].size < size)
99			index = ((free_entry*)&fBase[index])->next_free;
100
101		if (index == 0)
102			return NULL;
103
104		_RemoveFreeEntry(index);
105
106		// if the entry is big enough, we split it
107		if (fBase[index].size - size >= 2) {
108			uint32 next = index + 1 + size;
109			uint32 nextNext = index + 1 + fBase[index].size;
110			fBase[next].size = fBase[index].size - size - 1;
111			fBase[next].previous = index;
112			fBase[index].size = size;
113			_InsertFreeEntry(next);
114
115			if (nextNext < fEnd)
116				fBase[nextNext].previous = next;
117		}
118
119		return &fBase[index + 1];
120	}
121
122	void Free(void* address)
123	{
124		// check address
125		if (((addr_t)address & 7) != 0 || address <= fBase + 1
126			|| address >= fBase + fEnd) {
127			kprintf("DebugAllocPool::Free(%p): bad address\n", address);
128			return;
129		}
130
131		// get header
132		allocation_header* header = (allocation_header*)address - 1;
133		uint32 index = header - fBase;
134		if (header->free) {
135			kprintf("DebugAllocPool::Free(%p): double free\n", address);
136			return;
137		}
138
139		uint32 next = index + 1 + header->size;
140
141		// join with previous, if possible
142		if (index > 1 && fBase[header->previous].free) {
143			uint32 previous = header->previous;
144			_RemoveFreeEntry(previous);
145
146			fBase[previous].size += 1 + header->size;
147			fBase[next].previous = previous;
148
149			index = previous;
150			header = fBase + index;
151		}
152
153		// join with next, if possible
154		if (next < fEnd && fBase[next].free) {
155			_RemoveFreeEntry(next);
156
157			header->size += 1 + fBase[next].size;
158
159			uint32 nextNext = index + 1 + header->size;
160			if (nextNext < fEnd)
161				fBase[nextNext].previous = index;
162		}
163
164		_InsertFreeEntry(index);
165	}
166
167private:
168	void _InsertFreeEntry(uint32 index)
169	{
170		// find the insertion point -- list is sorted by ascending size
171		uint32 size = fBase[index].size;
172		uint32 next = fFirstFree;
173		while (next != 0 && size > fBase[next].size)
174			next = ((free_entry*)&fBase[next])->next_free;
175
176		// insert
177		uint32 previous;
178		if (next != 0) {
179			previous = ((free_entry*)&fBase[next])->previous_free;
180			((free_entry*)&fBase[next])->previous_free = index;
181		} else {
182			previous = fLastFree;
183			fLastFree = index;
184		}
185
186		if (previous != 0)
187			((free_entry*)&fBase[previous])->next_free = index;
188		else
189			fFirstFree = index;
190
191		((free_entry*)&fBase[index])->previous_free = previous;
192		((free_entry*)&fBase[index])->next_free = next;
193
194		fBase[index].free = true;
195	}
196
197	void _RemoveFreeEntry(uint32 index)
198	{
199		uint32 previous = ((free_entry*)&fBase[index])->previous_free;
200		uint32 next = ((free_entry*)&fBase[index])->next_free;
201
202		if (previous != 0)
203			((free_entry*)&fBase[previous])->next_free = next;
204		else
205			fFirstFree = next;
206
207		if (next != 0)
208			((free_entry*)&fBase[next])->previous_free = previous;
209		else
210			fLastFree = previous;
211
212		fBase[index].free = false;
213	}
214
215private:
216	DebugAllocPool*		fParent;
217	DebugAllocPool*		fChild;
218	allocation_header*	fBase;		// actually base - 1, so that index 0 is
219									// invalid
220	uint32				fEnd;
221	uint32				fFirstFree;
222	uint32				fLastFree;
223};
224
225
226static DebugAllocPool* sCurrentPool;
227static DebugAllocPool sInitialPool;
228
229
230debug_alloc_pool*
231create_debug_alloc_pool()
232{
233	if (sCurrentPool == NULL) {
234		sInitialPool.Init(sHeapBase, sHeapSize);
235		sCurrentPool = &sInitialPool;
236		return sCurrentPool;
237	}
238
239	DebugAllocPool* pool = sCurrentPool->CreateChildPool();
240	if (pool == NULL)
241		return NULL;
242
243	sCurrentPool = pool;
244	return sCurrentPool;
245}
246
247
248void
249delete_debug_alloc_pool(debug_alloc_pool* pool)
250{
251	if (pool == NULL || sCurrentPool == NULL)
252		return;
253
254	// find the pool in the hierarchy
255	DebugAllocPool* otherPool = sCurrentPool;
256	while (otherPool != NULL && otherPool != pool)
257		otherPool = otherPool->Parent();
258
259	if (otherPool == NULL)
260		return;
261
262	// destroy the pool
263	sCurrentPool = pool->Parent();
264	pool->Destroy();
265
266	if (pool != &sInitialPool)
267		debug_free(pool);
268}
269
270
271void*
272debug_malloc(size_t size)
273{
274	if (sCurrentPool == NULL)
275		return NULL;
276
277	return sCurrentPool->Allocate(size);
278}
279
280
281void*
282debug_calloc(size_t num, size_t size)
283{
284	size_t allocationSize = num * size;
285	void* allocation = debug_malloc(allocationSize);
286	if (allocation == NULL)
287		return NULL;
288
289	memset(allocation, 0, allocationSize);
290	return allocation;
291}
292
293
294void
295debug_free(void* address)
296{
297	if (address != NULL && sCurrentPool != NULL)
298		sCurrentPool->Free(address);
299}
300
301
302void
303debug_heap_init()
304{
305	// create the heap area
306	void* base;
307	virtual_address_restrictions virtualRestrictions = {};
308	virtualRestrictions.address_specification = B_ANY_KERNEL_ADDRESS;
309	physical_address_restrictions physicalRestrictions = {};
310	area_id area = create_area_etc(B_SYSTEM_TEAM, "kdebug heap", KDEBUG_HEAP,
311		B_FULL_LOCK, B_KERNEL_READ_AREA | B_KERNEL_WRITE_AREA,
312		CREATE_AREA_DONT_WAIT, 0, &virtualRestrictions, &physicalRestrictions,
313		(void**)&base);
314	if (area < 0)
315		return;
316
317	// switch from the small static buffer to the area
318	InterruptsLocker locker;
319	sHeapBase = base;
320	sHeapSize = KDEBUG_HEAP;
321}
322