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