1 /* 2 * Copyright 2008, Michael Lotz, mmlr@mlotz.ch. 3 * Distributed under the terms of the MIT License. 4 * 5 * Copyright 2002-2006, Axel Dörfler, axeld@pinc-software.de. 6 * Distributed under the terms of the MIT License. 7 * 8 * Copyright 2001, Travis Geiselbrecht. All rights reserved. 9 * Distributed under the terms of the NewOS License. 10 */ 11 #include <debug.h> 12 #include <heap.h> 13 #include <int.h> 14 #include <kernel.h> 15 #include <lock.h> 16 #include <malloc.h> 17 #include <signal.h> 18 #include <string.h> 19 #include <team.h> 20 #include <thread.h> 21 #include <tracing.h> 22 #include <util/AutoLock.h> 23 #include <util/DoublyLinkedList.h> 24 #include <vm.h> 25 26 //#define TRACE_HEAP 27 #ifdef TRACE_HEAP 28 # define TRACE(x) dprintf x 29 #else 30 # define TRACE(x) ; 31 #endif 32 33 // initialize newly allocated memory with something non zero 34 #define PARANOID_KMALLOC 1 35 // check for double free, and fill freed memory with 0xdeadbeef 36 #define PARANOID_KFREE 1 37 // validate sanity of the heap after each operation (slow!) 38 #define PARANOID_VALIDATION 0 39 // store size, thread and team info at the end of each allocation block 40 #define KERNEL_HEAP_LEAK_CHECK 0 41 42 #if KERNEL_HEAP_LEAK_CHECK 43 typedef struct heap_leak_check_info_s { 44 size_t size; 45 thread_id thread; 46 team_id team; 47 } heap_leak_check_info; 48 #endif 49 50 typedef struct heap_page_s { 51 uint16 index; 52 uint16 bin_index : 5; 53 uint16 free_count : 10; 54 uint16 in_use : 1; 55 heap_page_s * next; 56 heap_page_s * prev; 57 union { 58 uint16 empty_index; 59 uint16 allocation_id; // used for bin == bin_count allocations 60 }; 61 addr_t * free_list; 62 } heap_page; 63 64 typedef struct heap_bin_s { 65 uint32 element_size; 66 uint16 max_free_count; 67 heap_page * page_list; // sorted so that the desired page is always first 68 } heap_bin; 69 70 typedef struct heap_allocator_s { 71 addr_t base; 72 size_t size; 73 mutex lock; 74 75 uint32 bin_count; 76 uint32 page_count; 77 heap_page * free_pages; 78 79 heap_bin * bins; 80 heap_page * page_table; 81 82 heap_allocator_s * next; 83 } heap_allocator; 84 85 struct DeferredFreeListEntry : DoublyLinkedListLinkImpl<DeferredFreeListEntry> { 86 }; 87 typedef DoublyLinkedList<DeferredFreeListEntry> DeferredFreeList; 88 89 static heap_allocator *sHeapList = NULL; 90 static heap_allocator *sLastGrowRequest = NULL; 91 static heap_allocator *sGrowHeap = NULL; 92 static thread_id sHeapGrowThread = -1; 93 static sem_id sHeapGrowSem = -1; 94 static sem_id sHeapGrownNotify = -1; 95 96 static DeferredFreeList sDeferredFreeList; 97 static spinlock sDeferredFreeListLock; 98 99 100 101 // #pragma mark - Tracing 102 103 #ifdef KERNEL_HEAP_TRACING 104 namespace KernelHeapTracing { 105 106 class Allocate : public AbstractTraceEntry { 107 public: 108 Allocate(addr_t address, size_t size) 109 : fAddress(address), 110 fSize(size) 111 { 112 Initialized(); 113 } 114 115 virtual void AddDump(TraceOutput &out) 116 { 117 out.Print("heap allocate: 0x%08lx (%lu bytes)", fAddress, fSize); 118 } 119 120 private: 121 addr_t fAddress; 122 size_t fSize; 123 }; 124 125 126 class Reallocate : public AbstractTraceEntry { 127 public: 128 Reallocate(addr_t oldAddress, addr_t newAddress, size_t newSize) 129 : fOldAddress(oldAddress), 130 fNewAddress(newAddress), 131 fNewSize(newSize) 132 { 133 Initialized(); 134 }; 135 136 virtual void AddDump(TraceOutput &out) 137 { 138 out.Print("heap reallocate: 0x%08lx -> 0x%08lx (%lu bytes)", 139 fOldAddress, fNewAddress, fNewSize); 140 } 141 142 private: 143 addr_t fOldAddress; 144 addr_t fNewAddress; 145 size_t fNewSize; 146 }; 147 148 149 class Free : public AbstractTraceEntry { 150 public: 151 Free(addr_t address) 152 : fAddress(address) 153 { 154 Initialized(); 155 }; 156 157 virtual void AddDump(TraceOutput &out) 158 { 159 out.Print("heap free: 0x%08lx", fAddress); 160 } 161 162 private: 163 addr_t fAddress; 164 }; 165 166 167 } // namespace KernelHeapTracing 168 169 # define T(x) if (!kernel_startup) new(std::nothrow) KernelHeapTracing::x; 170 #else 171 # define T(x) ; 172 #endif 173 174 175 // #pragma mark - Debug functions 176 177 178 static void 179 dump_page(heap_page *page) 180 { 181 uint32 count = 0; 182 for (addr_t *temp = page->free_list; temp != NULL; temp = (addr_t *)*temp) 183 count++; 184 185 dprintf("\t\tpage %p: bin_index: %u; free_count: %u; empty_index: %u; free_list %p (%lu entr%s)\n", 186 page, page->bin_index, page->free_count, page->empty_index, 187 page->free_list, count, count == 1 ? "y" : "ies"); 188 } 189 190 191 static void 192 dump_bin(heap_bin *bin) 193 { 194 dprintf("\telement_size: %lu; max_free_count: %u; page_list %p;\n", 195 bin->element_size, bin->max_free_count, bin->page_list); 196 197 for (heap_page *temp = bin->page_list; temp != NULL; temp = temp->next) 198 dump_page(temp); 199 } 200 201 202 static void 203 dump_allocator(heap_allocator *heap) 204 { 205 uint32 count = 0; 206 for (heap_page *page = heap->free_pages; page != NULL; page = page->next) 207 count++; 208 209 dprintf("allocator %p: base: 0x%08lx; size: %lu; bin_count: %lu; free_pages: %p (%lu entr%s)\n", heap, 210 heap->base, heap->size, heap->bin_count, heap->free_pages, count, 211 count == 1 ? "y" : "ies"); 212 213 for (uint32 i = 0; i < heap->bin_count; i++) 214 dump_bin(&heap->bins[i]); 215 216 dprintf("\n"); 217 } 218 219 220 static int 221 dump_heap_list(int argc, char **argv) 222 { 223 if (argc == 2) { 224 if (strcmp(argv[1], "grow") == 0) { 225 // only dump dedicated grow heap info 226 dprintf("dedicated grow heap:\n"); 227 dump_allocator(sGrowHeap); 228 } else if (strcmp(argv[1], "stats") == 0) { 229 uint32 heapCount = 0; 230 heap_allocator *heap = sHeapList; 231 while (heap) { 232 heapCount++; 233 heap = heap->next; 234 } 235 236 dprintf("current heap count: %ld\n", heapCount); 237 } else 238 print_debugger_command_usage(argv[0]); 239 240 return 0; 241 } 242 243 heap_allocator *heap = sHeapList; 244 while (heap) { 245 dump_allocator(heap); 246 heap = heap->next; 247 } 248 249 return 0; 250 } 251 252 253 #if KERNEL_HEAP_LEAK_CHECK 254 static int 255 dump_allocations(int argc, char **argv) 256 { 257 team_id team = -1; 258 thread_id thread = -1; 259 bool statsOnly = false; 260 for (int32 i = 1; i < argc; i++) { 261 if (strcmp(argv[i], "team") == 0) 262 team = strtoul(argv[++i], NULL, 0); 263 else if (strcmp(argv[i], "thread") == 0) 264 thread = strtoul(argv[++i], NULL, 0); 265 else if (strcmp(argv[i], "stats") == 0) 266 statsOnly = true; 267 else { 268 print_debugger_command_usage(argv[0]); 269 return 0; 270 } 271 } 272 273 size_t totalSize = 0; 274 uint32 totalCount = 0; 275 heap_allocator *heap = sHeapList; 276 while (heap) { 277 // go through all the pages 278 heap_leak_check_info *info = NULL; 279 for (uint32 i = 0; i < heap->page_count; i++) { 280 heap_page *page = &heap->page_table[i]; 281 if (!page->in_use) 282 continue; 283 284 addr_t base = heap->base + i * B_PAGE_SIZE; 285 if (page->bin_index < heap->bin_count) { 286 // page is used by a small allocation bin 287 uint32 elementCount = page->empty_index; 288 size_t elementSize = heap->bins[page->bin_index].element_size; 289 for (uint32 j = 0; j < elementCount; j++, base += elementSize) { 290 // walk the free list to see if this element is in use 291 bool elementInUse = true; 292 for (addr_t *temp = page->free_list; temp != NULL; temp = (addr_t *)*temp) { 293 if ((addr_t)temp == base) { 294 elementInUse = false; 295 break; 296 } 297 } 298 299 if (!elementInUse) 300 continue; 301 302 info = (heap_leak_check_info *)(base + elementSize 303 - sizeof(heap_leak_check_info)); 304 305 if ((team == -1 && thread == -1) 306 || (team == -1 && info->thread == thread) 307 || (thread == -1 && info->team == team)) { 308 // interesting... 309 if (!statsOnly) { 310 dprintf("team: % 6ld; thread: % 6ld; address: 0x%08lx; size: %lu bytes\n", 311 info->team, info->thread, base, info->size); 312 } 313 314 totalSize += info->size; 315 totalCount++; 316 } 317 } 318 } else { 319 // page is used by a big allocation, find the page count 320 uint32 pageCount = 1; 321 while (i + pageCount < heap->page_count 322 && heap->page_table[i + pageCount].in_use 323 && heap->page_table[i + pageCount].bin_index == heap->bin_count 324 && heap->page_table[i + pageCount].allocation_id == page->allocation_id) 325 pageCount++; 326 327 info = (heap_leak_check_info *)(base + pageCount * B_PAGE_SIZE 328 - sizeof(heap_leak_check_info)); 329 330 if ((team == -1 && thread == -1) 331 || (team == -1 && info->thread == thread) 332 || (thread == -1 && info->team == team)) { 333 // interesting... 334 if (!statsOnly) { 335 dprintf("team: % 6ld; thread: % 6ld; address: 0x%08lx; size: %lu bytes\n", 336 info->team, info->thread, base, info->size); 337 } 338 339 totalSize += info->size; 340 totalCount++; 341 } 342 343 // skip the allocated pages 344 i += pageCount - 1; 345 } 346 } 347 348 heap = heap->next; 349 } 350 351 dprintf("total allocations: %lu; total bytes: %lu\n", totalCount, totalSize); 352 return 0; 353 } 354 #endif // KERNEL_HEAP_LEAK_CHECK 355 356 357 #if PARANOID_VALIDATION 358 static void 359 heap_validate_heap(heap_allocator *heap) 360 { 361 mutex_lock(&heap->lock); 362 363 // validate the free pages list 364 uint32 freePageCount = 0; 365 heap_page *lastPage = NULL; 366 heap_page *page = heap->free_pages; 367 while (page) { 368 if ((addr_t)page < (addr_t)&heap->page_table[0] 369 || (addr_t)page >= (addr_t)&heap->page_table[heap->page_count]) 370 panic("free page is not part of the page table\n"); 371 372 if (page->index >= heap->page_count) 373 panic("free page has invalid index\n"); 374 375 if ((addr_t)&heap->page_table[page->index] != (addr_t)page) 376 panic("free page index does not lead to target page\n"); 377 378 if (page->prev != lastPage) 379 panic("free page entry has invalid prev link\n"); 380 381 if (page->in_use) 382 panic("free page marked as in use\n"); 383 384 lastPage = page; 385 page = page->next; 386 freePageCount++; 387 } 388 389 // validate the page table 390 uint32 usedPageCount = 0; 391 for (uint32 i = 0; i < heap->page_count; i++) { 392 if (heap->page_table[i].in_use) 393 usedPageCount++; 394 } 395 396 if (freePageCount + usedPageCount != heap->page_count) { 397 panic("free pages and used pages do not add up (%lu + %lu != %lu)\n", 398 freePageCount, usedPageCount, heap->page_count); 399 } 400 401 // validate the bins 402 for (uint32 i = 0; i < heap->bin_count; i++) { 403 heap_bin *bin = &heap->bins[i]; 404 405 lastPage = NULL; 406 page = bin->page_list; 407 int32 lastFreeCount = 0; 408 while (page) { 409 if ((addr_t)page < (addr_t)&heap->page_table[0] 410 || (addr_t)page >= (addr_t)&heap->page_table[heap->page_count]) 411 panic("used page is not part of the page table\n"); 412 413 if (page->index >= heap->page_count) 414 panic("used page has invalid index\n"); 415 416 if ((addr_t)&heap->page_table[page->index] != (addr_t)page) 417 panic("used page index does not lead to target page\n"); 418 419 if (page->prev != lastPage) 420 panic("used page entry has invalid prev link (%p vs %p bin %lu)\n", 421 page->prev, lastPage, i); 422 423 if (!page->in_use) 424 panic("used page marked as not in use\n"); 425 426 if (page->bin_index != i) 427 panic("used page with bin index %u in page list of bin %lu\n", 428 page->bin_index, i); 429 430 if (page->free_count < lastFreeCount) 431 panic("ordering of bin page list broken\n"); 432 433 // validate the free list 434 uint32 freeSlotsCount = 0; 435 addr_t *element = page->free_list; 436 addr_t pageBase = heap->base + page->index * B_PAGE_SIZE; 437 while (element) { 438 if ((addr_t)element < pageBase 439 || (addr_t)element >= pageBase + B_PAGE_SIZE) 440 panic("free list entry out of page range\n"); 441 442 if (((addr_t)element - pageBase) % bin->element_size != 0) 443 panic("free list entry not on a element boundary\n"); 444 445 element = (addr_t *)*element; 446 freeSlotsCount++; 447 } 448 449 uint32 slotCount = bin->max_free_count; 450 if (page->empty_index > slotCount) 451 panic("empty index beyond slot count (%u with %lu slots)\n", 452 page->empty_index, slotCount); 453 454 freeSlotsCount += (slotCount - page->empty_index); 455 if (freeSlotsCount > slotCount) 456 panic("more free slots than fit into the page\n"); 457 458 lastPage = page; 459 lastFreeCount = page->free_count; 460 page = page->next; 461 } 462 } 463 464 mutex_unlock(&heap->lock); 465 } 466 #endif // PARANOID_VALIDATION 467 468 469 // #pragma mark - Heap functions 470 471 472 heap_allocator * 473 heap_attach(addr_t base, size_t size, bool postSem) 474 { 475 heap_allocator *heap = (heap_allocator *)base; 476 base += sizeof(heap_allocator); 477 size -= sizeof(heap_allocator); 478 479 size_t binSizes[] = { 8, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512, 1024, 2048, B_PAGE_SIZE }; 480 uint32 binCount = sizeof(binSizes) / sizeof(binSizes[0]); 481 heap->bin_count = binCount; 482 heap->bins = (heap_bin *)base; 483 base += binCount * sizeof(heap_bin); 484 size -= binCount * sizeof(heap_bin); 485 486 for (uint32 i = 0; i < binCount; i++) { 487 heap_bin *bin = &heap->bins[i]; 488 bin->element_size = binSizes[i]; 489 bin->max_free_count = B_PAGE_SIZE / binSizes[i]; 490 bin->page_list = NULL; 491 } 492 493 uint32 pageCount = size / B_PAGE_SIZE; 494 size_t pageTableSize = pageCount * sizeof(heap_page); 495 heap->page_table = (heap_page *)base; 496 base += pageTableSize; 497 size -= pageTableSize; 498 499 // the rest is now actually usable memory (rounded to the next page) 500 heap->base = (addr_t)(base + B_PAGE_SIZE - 1) / B_PAGE_SIZE * B_PAGE_SIZE; 501 heap->size = (size_t)(size / B_PAGE_SIZE) * B_PAGE_SIZE; 502 503 // now we know the real page count 504 pageCount = heap->size / B_PAGE_SIZE; 505 heap->page_count = pageCount; 506 507 // zero out the heap alloc table at the base of the heap 508 memset((void *)heap->page_table, 0, pageTableSize); 509 for (uint32 i = 0; i < pageCount; i++) 510 heap->page_table[i].index = i; 511 512 // add all pages up into the free pages list 513 for (uint32 i = 1; i < pageCount; i++) { 514 heap->page_table[i - 1].next = &heap->page_table[i]; 515 heap->page_table[i].prev = &heap->page_table[i - 1]; 516 } 517 heap->free_pages = &heap->page_table[0]; 518 heap->page_table[0].prev = NULL; 519 520 if (postSem) { 521 if (mutex_init(&heap->lock, "heap_mutex") < 0) { 522 panic("heap_attach(): error creating heap mutex\n"); 523 return NULL; 524 } 525 } else { 526 // pre-init the mutex to at least fall through any semaphore calls 527 heap->lock.sem = -1; 528 heap->lock.holder = -1; 529 } 530 531 heap->next = NULL; 532 dprintf("heap_attach: attached to %p - usable range 0x%08lx - 0x%08lx\n", 533 heap, heap->base, heap->base + heap->size); 534 return heap; 535 } 536 537 538 static inline void 539 heap_link_page(heap_page *page, heap_page **list) 540 { 541 page->prev = NULL; 542 page->next = *list; 543 if (page->next) 544 page->next->prev = page; 545 *list = page; 546 } 547 548 549 static inline void 550 heap_unlink_page(heap_page *page, heap_page **list) 551 { 552 if (page->prev) 553 page->prev->next = page->next; 554 if (page->next) 555 page->next->prev = page->prev; 556 if (list && *list == page) { 557 *list = page->next; 558 if (page->next) 559 page->next->prev = NULL; 560 } 561 } 562 563 564 static void * 565 heap_raw_alloc(heap_allocator *heap, size_t size, uint32 binIndex) 566 { 567 heap_bin *bin = NULL; 568 if (binIndex < heap->bin_count) 569 bin = &heap->bins[binIndex]; 570 571 if (bin && bin->page_list != NULL) { 572 // we have a page where we have a free slot 573 void *address = NULL; 574 heap_page *page = bin->page_list; 575 if (page->free_list) { 576 // there's a previously freed entry we can use 577 address = page->free_list; 578 page->free_list = (addr_t *)*page->free_list; 579 } else { 580 // the page hasn't been fully allocated so use the next empty_index 581 address = (void *)(heap->base + page->index * B_PAGE_SIZE 582 + page->empty_index * bin->element_size); 583 page->empty_index++; 584 } 585 586 page->free_count--; 587 if (page->free_count == 0) { 588 // the page is now full so we remove it from the page_list 589 bin->page_list = page->next; 590 if (page->next) 591 page->next->prev = NULL; 592 page->next = page->prev = NULL; 593 } 594 595 #if KERNEL_HEAP_LEAK_CHECK 596 heap_leak_check_info *info = (heap_leak_check_info *)((addr_t)address 597 + bin->element_size - sizeof(heap_leak_check_info)); 598 info->size = size - sizeof(heap_leak_check_info); 599 info->thread = (kernel_startup ? 0 : thread_get_current_thread_id()); 600 info->team = (kernel_startup ? 0 : team_get_current_team_id()); 601 #endif 602 return address; 603 } 604 605 // we don't have anything free right away, we must allocate a new page 606 if (heap->free_pages == NULL) { 607 // there are no free pages anymore, we ran out of memory 608 TRACE(("heap %p: no free pages to allocate %lu bytes\n", heap, size)); 609 return NULL; 610 } 611 612 if (bin) { 613 // small allocation, just grab the next free page 614 heap_page *page = heap->free_pages; 615 heap->free_pages = page->next; 616 if (page->next) 617 page->next->prev = NULL; 618 619 page->in_use = 1; 620 page->bin_index = binIndex; 621 page->free_count = bin->max_free_count - 1; 622 page->empty_index = 1; 623 page->free_list = NULL; 624 page->next = page->prev = NULL; 625 626 if (page->free_count > 0) { 627 // by design there are no other pages in the bins page list 628 bin->page_list = page; 629 } 630 631 #if KERNEL_HEAP_LEAK_CHECK 632 heap_leak_check_info *info = (heap_leak_check_info *)(heap->base 633 + page->index * B_PAGE_SIZE + bin->element_size 634 - sizeof(heap_leak_check_info)); 635 info->size = size - sizeof(heap_leak_check_info); 636 info->thread = (kernel_startup ? 0 : thread_get_current_thread_id()); 637 info->team = (kernel_startup ? 0 : team_get_current_team_id()); 638 #endif 639 640 // we return the first slot in this page 641 return (void *)(heap->base + page->index * B_PAGE_SIZE); 642 } 643 644 // large allocation, we must search for contiguous slots 645 bool found = false; 646 int32 first = -1; 647 for (uint32 i = 0; i < heap->page_count; i++) { 648 if (heap->page_table[i].in_use) { 649 first = -1; 650 continue; 651 } 652 653 if (first > 0) { 654 if ((1 + i - first) * B_PAGE_SIZE >= size) { 655 found = true; 656 break; 657 } 658 } else 659 first = i; 660 } 661 662 if (!found) { 663 TRACE(("heap %p: found no contiguous pages to allocate %ld bytes\n", heap, size)); 664 return NULL; 665 } 666 667 uint32 pageCount = (size + B_PAGE_SIZE - 1) / B_PAGE_SIZE; 668 for (uint32 i = first; i < first + pageCount; i++) { 669 heap_page *page = &heap->page_table[i]; 670 page->in_use = 1; 671 page->bin_index = binIndex; 672 673 heap_unlink_page(page, &heap->free_pages); 674 675 page->next = page->prev = NULL; 676 page->free_list = NULL; 677 page->allocation_id = (uint16)first; 678 } 679 680 #if KERNEL_HEAP_LEAK_CHECK 681 heap_leak_check_info *info = (heap_leak_check_info *)(heap->base 682 + (first + pageCount) * B_PAGE_SIZE - sizeof(heap_leak_check_info)); 683 info->size = size - sizeof(heap_leak_check_info); 684 info->thread = (kernel_startup ? 0 : thread_get_current_thread_id()); 685 info->team = (kernel_startup ? 0 : team_get_current_team_id()); 686 #endif 687 return (void *)(heap->base + first * B_PAGE_SIZE); 688 } 689 690 691 #if DEBUG 692 static bool 693 is_valid_alignment(size_t number) 694 { 695 // this cryptic line accepts zero and all powers of two 696 return ((~number + 1) | ((number << 1) - 1)) == ~0UL; 697 } 698 #endif 699 700 701 static void * 702 heap_memalign(heap_allocator *heap, size_t alignment, size_t size, 703 bool *shouldGrow) 704 { 705 TRACE(("memalign(alignment = %lu, size = %lu)\n", alignment, size)); 706 707 #if DEBUG 708 if (!is_valid_alignment(alignment)) 709 panic("memalign() with an alignment which is not a power of 2\n"); 710 #endif 711 712 mutex_lock(&heap->lock); 713 714 #if KERNEL_HEAP_LEAK_CHECK 715 size += sizeof(heap_leak_check_info); 716 #endif 717 718 // ToDo: that code "aligns" the buffer because the bins are always 719 // aligned on their bin size 720 if (size < alignment) 721 size = alignment; 722 723 uint32 binIndex; 724 for (binIndex = 0; binIndex < heap->bin_count; binIndex++) { 725 if (size <= heap->bins[binIndex].element_size) 726 break; 727 } 728 729 void *address = heap_raw_alloc(heap, size, binIndex); 730 731 TRACE(("memalign(): asked to allocate %lu bytes, returning pointer %p\n", size, address)); 732 733 if (heap->next == NULL && shouldGrow) { 734 // suggest growing if we are the last heap and we have 735 // less than three free pages left 736 *shouldGrow = (heap->free_pages == NULL 737 || heap->free_pages->next == NULL 738 || heap->free_pages->next->next == NULL); 739 } 740 741 #if KERNEL_HEAP_LEAK_CHECK 742 size -= sizeof(heap_leak_check_info); 743 #endif 744 745 T(Allocate((addr_t)address, size)); 746 mutex_unlock(&heap->lock); 747 if (address == NULL) 748 return address; 749 750 #if PARANOID_KFREE 751 // make sure 0xdeadbeef is cleared if we do not overwrite the memory 752 // and the user does not clear it 753 if (((uint32 *)address)[1] == 0xdeadbeef) 754 ((uint32 *)address)[1] = 0xcccccccc; 755 #endif 756 757 #if PARANOID_KMALLOC 758 memset(address, 0xcc, size); 759 #endif 760 761 return address; 762 } 763 764 765 static status_t 766 heap_free(heap_allocator *heap, void *address) 767 { 768 if (address == NULL) 769 return B_OK; 770 771 if ((addr_t)address < heap->base 772 || (addr_t)address >= heap->base + heap->size) { 773 // this address does not belong to us 774 return B_ENTRY_NOT_FOUND; 775 } 776 777 mutex_lock(&heap->lock); 778 779 TRACE(("free(): asked to free at ptr = %p\n", address)); 780 781 heap_page *page = &heap->page_table[((addr_t)address - heap->base) / B_PAGE_SIZE]; 782 783 TRACE(("free(): page %p: bin_index %d, free_count %d\n", page, page->bin_index, page->free_count)); 784 785 if (page->bin_index > heap->bin_count) { 786 panic("free(): page %p: invalid bin_index %d\n", page, page->bin_index); 787 mutex_unlock(&heap->lock); 788 return B_ERROR; 789 } 790 791 if (page->bin_index < heap->bin_count) { 792 // small allocation 793 heap_bin *bin = &heap->bins[page->bin_index]; 794 if (((addr_t)address - heap->base - page->index * B_PAGE_SIZE) % bin->element_size != 0) { 795 panic("free(): passed invalid pointer %p supposed to be in bin for element size %ld\n", address, bin->element_size); 796 mutex_unlock(&heap->lock); 797 return B_ERROR; 798 } 799 800 #if PARANOID_KFREE 801 if (((uint32 *)address)[1] == 0xdeadbeef) { 802 // This block looks like it was freed already, walk the free list 803 // on this page to make sure this address doesn't exist. 804 for (addr_t *temp = page->free_list; temp != NULL; temp = (addr_t *)*temp) { 805 if (temp == address) { 806 panic("free(): address %p already exists in page free list\n", address); 807 mutex_unlock(&heap->lock); 808 return B_ERROR; 809 } 810 } 811 } 812 813 uint32 *dead = (uint32 *)address; 814 if (bin->element_size % 4 != 0) { 815 panic("free(): didn't expect a bin element size that is not a multiple of 4\n"); 816 mutex_unlock(&heap->lock); 817 return B_ERROR; 818 } 819 820 // the first 4 bytes are overwritten with the next free list pointer later 821 for (uint32 i = 1; i < bin->element_size / sizeof(uint32); i++) 822 dead[i] = 0xdeadbeef; 823 #endif 824 825 // add the address to the page free list 826 *(addr_t *)address = (addr_t)page->free_list; 827 page->free_list = (addr_t *)address; 828 page->free_count++; 829 830 if (page->free_count == bin->max_free_count) { 831 // we are now empty, remove the page from the bin list 832 heap_unlink_page(page, &bin->page_list); 833 page->in_use = 0; 834 heap_link_page(page, &heap->free_pages); 835 } else if (page->free_count == 1) { 836 // we need to add ourselfs to the page list of the bin 837 heap_link_page(page, &bin->page_list); 838 } else { 839 // we might need to move back in the free pages list 840 if (page->next && page->next->free_count < page->free_count) { 841 // move ourselfs so the list stays ordered 842 heap_page *insert = page->next; 843 while (insert->next 844 && insert->next->free_count < page->free_count) 845 insert = insert->next; 846 847 heap_unlink_page(page, &bin->page_list); 848 849 page->prev = insert; 850 page->next = insert->next; 851 if (page->next) 852 page->next->prev = page; 853 insert->next = page; 854 } 855 } 856 } else { 857 // large allocation, just return the pages to the page free list 858 uint32 allocationID = page->allocation_id; 859 uint32 maxPages = heap->page_count - page->index; 860 for (uint32 i = 0; i < maxPages; i++) { 861 // loop until we find the end of this allocation 862 if (!page[i].in_use || page[i].bin_index != heap->bin_count 863 || page[i].allocation_id != allocationID) 864 break; 865 866 // this page still belongs to the same allocation 867 page[i].in_use = 0; 868 page[i].allocation_id = 0; 869 870 // return it to the free list 871 heap_link_page(&page[i], &heap->free_pages); 872 } 873 } 874 875 T(Free((addr_t)address)); 876 mutex_unlock(&heap->lock); 877 return B_OK; 878 } 879 880 881 static status_t 882 heap_realloc(heap_allocator *heap, void *address, void **newAddress, 883 size_t newSize) 884 { 885 if ((addr_t)address < heap->base 886 || (addr_t)address >= heap->base + heap->size) { 887 // this address does not belong to us 888 return B_ENTRY_NOT_FOUND; 889 } 890 891 mutex_lock(&heap->lock); 892 TRACE(("realloc(address = %p, newSize = %lu)\n", address, newSize)); 893 894 heap_page *page = &heap->page_table[((addr_t)address - heap->base) / B_PAGE_SIZE]; 895 if (page->bin_index > heap->bin_count) { 896 panic("realloc(): page %p: invalid bin_index %d\n", page, page->bin_index); 897 mutex_unlock(&heap->lock); 898 return B_ERROR; 899 } 900 901 // find out the size of the old allocation first 902 size_t minSize = 0; 903 size_t maxSize = 0; 904 if (page->bin_index < heap->bin_count) { 905 // this was a small allocation 906 heap_bin *bin = &heap->bins[page->bin_index]; 907 maxSize = bin->element_size; 908 if (page->bin_index > 0) 909 minSize = heap->bins[page->bin_index - 1].element_size + 1; 910 } else { 911 // this was a large allocation 912 uint32 allocationID = page->allocation_id; 913 uint32 maxPages = heap->page_count - page->index; 914 maxSize = B_PAGE_SIZE; 915 for (uint32 i = 1; i < maxPages; i++) { 916 if (!page[i].in_use || page[i].bin_index != heap->bin_count 917 || page[i].allocation_id != allocationID) 918 break; 919 920 minSize += B_PAGE_SIZE; 921 maxSize += B_PAGE_SIZE; 922 } 923 } 924 925 mutex_unlock(&heap->lock); 926 927 #if KERNEL_HEAP_LEAK_CHECK 928 newSize += sizeof(heap_leak_check_info); 929 #endif 930 931 // does the new allocation simply fit in the old allocation? 932 if (newSize > minSize && newSize <= maxSize) { 933 #if KERNEL_HEAP_LEAK_CHECK 934 // update the size info (the info is at the end so stays where it is) 935 heap_leak_check_info *info = (heap_leak_check_info *)((addr_t)address 936 + maxSize - sizeof(heap_leak_check_info)); 937 info->size = newSize - sizeof(heap_leak_check_info); 938 newSize -= sizeof(heap_leak_check_info); 939 #endif 940 941 T(Reallocate((addr_t)address, (addr_t)address, newSize)); 942 *newAddress = address; 943 return B_OK; 944 } 945 946 #if KERNEL_HEAP_LEAK_CHECK 947 // new leak check info will be created with the malloc below 948 newSize -= sizeof(heap_leak_check_info); 949 #endif 950 951 // if not, allocate a new chunk of memory 952 *newAddress = malloc(newSize); 953 T(Reallocate((addr_t)address, (addr_t)*newAddress, newSize)); 954 if (*newAddress == NULL) { 955 // we tried but it didn't work out, but still the operation is done 956 return B_OK; 957 } 958 959 // copy the old data and free the old allocation 960 memcpy(*newAddress, address, min_c(maxSize, newSize)); 961 free(address); 962 return B_OK; 963 } 964 965 966 static void 967 deferred_deleter(void *arg, int iteration) 968 { 969 // move entries to on-stack list 970 InterruptsSpinLocker locker(sDeferredFreeListLock); 971 if (sDeferredFreeList.IsEmpty()) 972 return; 973 974 DeferredFreeList entries; 975 entries.MoveFrom(&sDeferredFreeList); 976 977 locker.Unlock(); 978 979 // free the entries 980 while (DeferredFreeListEntry* entry = entries.RemoveHead()) 981 free(entry); 982 } 983 984 985 // #pragma mark - 986 987 988 static int32 989 heap_grow_thread(void *) 990 { 991 heap_allocator *heap = sHeapList; 992 while (true) { 993 // wait for a request to grow the heap list 994 if (acquire_sem(sHeapGrowSem) < B_OK) 995 continue; 996 997 // find the last heap 998 while (heap->next) 999 heap = heap->next; 1000 1001 if (sLastGrowRequest != heap) { 1002 // we have already grown since the latest request, just ignore 1003 continue; 1004 } 1005 1006 TRACE(("heap_grower: kernel heap will run out of memory soon, allocating new one\n")); 1007 void *heapAddress = NULL; 1008 area_id heapArea = create_area("additional heap", &heapAddress, 1009 B_ANY_KERNEL_BLOCK_ADDRESS, HEAP_GROW_SIZE, B_FULL_LOCK, 1010 B_KERNEL_READ_AREA | B_KERNEL_WRITE_AREA); 1011 if (heapArea < B_OK) { 1012 panic("heap_grower: couldn't allocate additional heap area\n"); 1013 continue; 1014 } 1015 1016 heap_allocator *newHeap = heap_attach((addr_t)heapAddress, 1017 HEAP_GROW_SIZE, true); 1018 if (newHeap == NULL) { 1019 panic("heap_grower: could not attach additional heap!\n"); 1020 delete_area(heapArea); 1021 continue; 1022 } 1023 1024 #if PARANOID_VALIDATION 1025 heap_validate_heap(newHeap); 1026 #endif 1027 heap->next = newHeap; 1028 TRACE(("heap_grower: new heap linked in\n")); 1029 1030 // notify anyone waiting for this request 1031 release_sem_etc(sHeapGrownNotify, -1, B_RELEASE_ALL); 1032 } 1033 1034 return 0; 1035 } 1036 1037 1038 status_t 1039 heap_init(addr_t base, size_t size) 1040 { 1041 sHeapList = heap_attach(base, size, false); 1042 1043 // set up some debug commands 1044 add_debugger_command_etc("heap", &dump_heap_list, 1045 "Dump infos about the kernel heap(s)", "[(\"grow\" | \"stats\")]\n" 1046 "Dump infos about the kernel heap(s). If \"grow\" is specified, only\n" 1047 "infos about the dedicated grow heap are printed. If \"stats\" is\n" 1048 "given as the argument, currently only the heap count is printed\n", 0); 1049 #if KERNEL_HEAP_LEAK_CHECK 1050 add_debugger_command_etc("allocations", &dump_allocations, 1051 "Dump current allocations", "[(\"team\" | \"thread\") <id>] [\"stats\"]\n" 1052 "If no parameters are given, all current alloactions are dumped.\n" 1053 "If either \"team\" or \"thread\" is specified as the first argument,\n" 1054 "only allocations matching the team or thread id given in the second\n" 1055 "argument are printed.\n" 1056 "If the optional argument \"stats\" is specified, only the allocation\n" 1057 "counts and no individual allocations are printed\n", 0); 1058 #endif 1059 return B_OK; 1060 } 1061 1062 1063 status_t 1064 heap_init_post_sem() 1065 { 1066 // create the lock for the initial heap 1067 if (mutex_init(&sHeapList->lock, "heap_mutex") < B_OK) { 1068 panic("heap_init_post_sem(): error creating heap mutex\n"); 1069 return B_ERROR; 1070 } 1071 1072 sHeapGrowSem = create_sem(0, "heap_grow_sem"); 1073 if (sHeapGrowSem < 0) { 1074 panic("heap_init_post_sem(): failed to create heap grow sem\n"); 1075 return B_ERROR; 1076 } 1077 1078 sHeapGrownNotify = create_sem(0, "heap_grown_notify"); 1079 if (sHeapGrownNotify < 0) { 1080 panic("heap_init_post_sem(): failed to create heap grown notify sem\n"); 1081 return B_ERROR; 1082 } 1083 1084 return B_OK; 1085 } 1086 1087 1088 status_t 1089 heap_init_post_thread() 1090 { 1091 void *dedicated = NULL; 1092 area_id area = create_area("heap dedicated grow", &dedicated, 1093 B_ANY_KERNEL_BLOCK_ADDRESS, HEAP_DEDICATED_GROW_SIZE, B_FULL_LOCK, 1094 B_KERNEL_READ_AREA | B_KERNEL_WRITE_AREA); 1095 if (area < 0) { 1096 panic("heap_init_post_thread(): cannot allocate dedicated grow memory\n"); 1097 return area; 1098 } 1099 1100 sGrowHeap = heap_attach((addr_t)dedicated, HEAP_DEDICATED_GROW_SIZE, true); 1101 if (sGrowHeap == NULL) { 1102 panic("heap_init_post_thread(): failed to attach dedicated grow heap\n"); 1103 delete_area(area); 1104 return B_ERROR; 1105 } 1106 1107 sHeapGrowThread = spawn_kernel_thread(heap_grow_thread, "heap grower", 1108 B_URGENT_PRIORITY, NULL); 1109 if (sHeapGrowThread < 0) { 1110 panic("heap_init_post_thread(): cannot create heap grow thread\n"); 1111 delete_area(area); 1112 return sHeapGrowThread; 1113 } 1114 1115 if (register_kernel_daemon(deferred_deleter, NULL, 50) != B_OK) 1116 panic("heap_init_post_thread(): failed to init deferred deleter"); 1117 1118 send_signal_etc(sHeapGrowThread, SIGCONT, B_DO_NOT_RESCHEDULE); 1119 return B_OK; 1120 } 1121 1122 1123 // #pragma mark - Public API 1124 1125 1126 void * 1127 memalign(size_t alignment, size_t size) 1128 { 1129 if (!kernel_startup && !are_interrupts_enabled()) { 1130 panic("memalign(): called with interrupts disabled\n"); 1131 return NULL; 1132 } 1133 1134 if (size > (HEAP_GROW_SIZE * 3) / 4) { 1135 // don't even attempt such a huge allocation 1136 panic("heap: huge allocation of %lu bytes asked!\n", size); 1137 return NULL; 1138 } 1139 1140 if (thread_get_current_thread_id() == sHeapGrowThread) { 1141 // this is the grower thread, allocate from our dedicated memory 1142 void *result = heap_memalign(sGrowHeap, alignment, size, NULL); 1143 if (result == NULL) { 1144 panic("heap: grow thread ran out of dedicated memory!\n"); 1145 return NULL; 1146 } 1147 1148 return result; 1149 } 1150 1151 heap_allocator *heap = sHeapList; 1152 while (heap) { 1153 bool shouldGrow = false; 1154 void *result = heap_memalign(heap, alignment, size, &shouldGrow); 1155 if (heap->next == NULL && (shouldGrow || result == NULL)) { 1156 // the last heap will or has run out of memory, notify the grower 1157 sLastGrowRequest = heap; 1158 if (result == NULL) { 1159 // urgent request, do the request and wait 1160 switch_sem(sHeapGrowSem, sHeapGrownNotify); 1161 } else { 1162 // not so urgent, just notify the grower 1163 release_sem_etc(sHeapGrowSem, 1, B_DO_NOT_RESCHEDULE); 1164 } 1165 } 1166 1167 if (result == NULL) { 1168 heap = heap->next; 1169 continue; 1170 } 1171 1172 #if PARANOID_VALIDATION 1173 heap_validate_heap(heap); 1174 #endif 1175 1176 return result; 1177 } 1178 1179 panic("heap: kernel heap has run out of memory\n"); 1180 return NULL; 1181 } 1182 1183 1184 void * 1185 malloc(size_t size) 1186 { 1187 return memalign(0, size); 1188 } 1189 1190 1191 void 1192 free(void *address) 1193 { 1194 if (!kernel_startup && !are_interrupts_enabled()) { 1195 panic("free(): called with interrupts disabled\n"); 1196 return; 1197 } 1198 1199 heap_allocator *heap = sHeapList; 1200 while (heap) { 1201 if (heap_free(heap, address) == B_OK) { 1202 #if PARANOID_VALIDATION 1203 heap_validate_heap(heap); 1204 #endif 1205 return; 1206 } 1207 1208 heap = heap->next; 1209 } 1210 1211 // maybe it was allocated from the dedicated grow heap 1212 if (heap_free(sGrowHeap, address) == B_OK) 1213 return; 1214 1215 panic("free(): free failed for address %p\n", address); 1216 } 1217 1218 1219 void * 1220 realloc(void *address, size_t newSize) 1221 { 1222 if (!kernel_startup && !are_interrupts_enabled()) { 1223 panic("realloc(): called with interrupts disabled\n"); 1224 return NULL; 1225 } 1226 1227 if (address == NULL) 1228 return malloc(newSize); 1229 1230 if (newSize == 0) { 1231 free(address); 1232 return NULL; 1233 } 1234 1235 heap_allocator *heap = sHeapList; 1236 while (heap) { 1237 void *newAddress = NULL; 1238 if (heap_realloc(heap, address, &newAddress, newSize) == B_OK) { 1239 #if PARANOID_VALIDATION 1240 heap_validate_heap(heap); 1241 #endif 1242 return newAddress; 1243 } 1244 1245 heap = heap->next; 1246 } 1247 1248 panic("realloc(): failed to realloc address %p to size %lu\n", address, newSize); 1249 return NULL; 1250 } 1251 1252 1253 void * 1254 calloc(size_t numElements, size_t size) 1255 { 1256 void *address = memalign(0, numElements * size); 1257 if (address != NULL) 1258 memset(address, 0, numElements * size); 1259 1260 return address; 1261 } 1262 1263 1264 void 1265 deferred_free(void* block) 1266 { 1267 if (block == NULL) 1268 return; 1269 1270 // TODO: Use SinglyLinkedList, so that we only need sizeof(void*). 1271 DeferredFreeListEntry* entry = new(block) DeferredFreeListEntry; 1272 1273 InterruptsSpinLocker _(sDeferredFreeListLock); 1274 sDeferredFreeList.Add(entry); 1275 } 1276 1277 1278 void* 1279 malloc_referenced(size_t size) 1280 { 1281 int32* referencedData = (int32*)malloc(size + 4); 1282 if (referencedData == NULL) 1283 return NULL; 1284 1285 *referencedData = 1; 1286 1287 return referencedData + 1; 1288 } 1289 1290 1291 void* 1292 malloc_referenced_acquire(void* data) 1293 { 1294 if (data != NULL) { 1295 int32* referencedData = (int32*)data - 1; 1296 atomic_add(referencedData, 1); 1297 } 1298 1299 return data; 1300 } 1301 1302 1303 void 1304 malloc_referenced_release(void* data) 1305 { 1306 if (data == NULL) 1307 return; 1308 1309 int32* referencedData = (int32*)data - 1; 1310 if (atomic_add(referencedData, -1) < 1) 1311 free(referencedData); 1312 } 1313