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
17 static char sInitialHeap[INITIAL_DEBUG_HEAP_SIZE] __attribute__ ((aligned (8)));
18 static void* sHeapBase = sInitialHeap;
19 static size_t sHeapSize = INITIAL_DEBUG_HEAP_SIZE;
20
21 const kdebug_alloc_t kdebug_alloc = {};
22
23
24 struct allocation_header {
25 uint32 size : 31; // size in allocation_header units
26 bool free : 1;
27 uint32 previous;
28 };
29
30 struct free_entry : allocation_header {
31 uint32 previous_free;
32 uint32 next_free;
33 };
34
35
36 struct DebugAllocPool {
InitDebugAllocPool37 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
CreateChildPoolDebugAllocPool54 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
DestroyDebugAllocPool81 void Destroy()
82 {
83 if (fParent != NULL) {
84 fParent->fChild = NULL;
85 fParent->Free(fBase + 1);
86 }
87 }
88
ParentDebugAllocPool89 DebugAllocPool* Parent() const
90 {
91 return fParent;
92 }
93
AllocateDebugAllocPool94 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
FreeDebugAllocPool122 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
167 private:
_InsertFreeEntryDebugAllocPool168 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
_RemoveFreeEntryDebugAllocPool197 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
215 private:
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
226 static DebugAllocPool* sCurrentPool;
227 static DebugAllocPool sInitialPool;
228
229
230 debug_alloc_pool*
create_debug_alloc_pool()231 create_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
248 void
delete_debug_alloc_pool(debug_alloc_pool * pool)249 delete_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
271 void*
debug_malloc(size_t size)272 debug_malloc(size_t size)
273 {
274 if (sCurrentPool == NULL)
275 return NULL;
276
277 return sCurrentPool->Allocate(size);
278 }
279
280
281 void*
debug_calloc(size_t num,size_t size)282 debug_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
294 void
debug_free(void * address)295 debug_free(void* address)
296 {
297 if (address != NULL && sCurrentPool != NULL)
298 sCurrentPool->Free(address);
299 }
300
301
302 void
debug_heap_init()303 debug_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