1/* 2 * Copyright 2011, Michael Lotz <mmlr@mlotz.ch>. 3 * Distributed under the terms of the MIT License. 4 */ 5 6#include "malloc_debug_api.h" 7 8 9#include <malloc.h> 10#include <stdio.h> 11#include <stdlib.h> 12#include <string.h> 13 14#include <signal.h> 15#include <sys/mman.h> 16 17#include <locks.h> 18 19#include <libroot_private.h> 20#include <runtime_loader.h> 21 22#include <TLS.h> 23 24 25// #pragma mark - Debug Helpers 26 27static const size_t kMaxStackTraceDepth = 50; 28 29 30static bool sDebuggerCalls = true; 31static bool sDumpAllocationsOnExit = false; 32static size_t sStackTraceDepth = 0; 33static int32 sStackBaseTLSIndex = -1; 34static int32 sStackEndTLSIndex = -1; 35 36#if __cplusplus >= 201103L 37#include <cstddef> 38using namespace std; 39static size_t sDefaultAlignment = alignof(max_align_t); 40#else 41static size_t sDefaultAlignment = 8; 42#endif 43 44 45static void 46panic(const char* format, ...) 47{ 48 char buffer[1024]; 49 50 va_list args; 51 va_start(args, format); 52 vsnprintf(buffer, sizeof(buffer), format, args); 53 va_end(args); 54 55 if (sDebuggerCalls) 56 debugger(buffer); 57 else 58 debug_printf("%s", buffer); 59} 60 61 62static void 63print_stdout(const char* format, ...) 64{ 65 // To avoid any allocations due to dynamic memory need by printf() we use a 66 // stack buffer and vsnprintf(). Otherwise this does the same as printf(). 67 char buffer[1024]; 68 69 va_list args; 70 va_start(args, format); 71 vsnprintf(buffer, sizeof(buffer), format, args); 72 va_end(args); 73 74 write(STDOUT_FILENO, buffer, strlen(buffer)); 75} 76 77 78// #pragma mark - Linked List 79 80 81#define GET_ITEM(list, item) ((void *)((uint8 *)item - list->offset)) 82#define GET_LINK(list, item) ((list_link *)((uint8 *)item + list->offset)) 83 84 85struct list_link { 86 list_link* next; 87 list_link* prev; 88}; 89 90struct list { 91 list_link link; 92 int32 offset; 93}; 94 95 96static inline void 97list_remove_item(struct list* list, void* item) 98{ 99 list_link* link = GET_LINK(list, item); 100 101 link->next->prev = link->prev; 102 link->prev->next = link->next; 103} 104 105 106static inline void 107list_add_item(struct list* list, void* item) 108{ 109 list_link* link = GET_LINK(list, item); 110 111 link->next = &list->link; 112 link->prev = list->link.prev; 113 114 list->link.prev->next = link; 115 list->link.prev = link; 116} 117 118 119static inline void* 120list_get_next_item(struct list* list, void* item) 121{ 122 if (item == NULL) { 123 if (list->link.next == (list_link *)list) 124 return NULL; 125 126 return GET_ITEM(list, list->link.next); 127 } 128 129 list_link* link = GET_LINK(list, item); 130 if (link->next == &list->link) 131 return NULL; 132 133 return GET_ITEM(list, link->next); 134} 135 136 137static inline void 138list_init_etc(struct list* list, int32 offset) 139{ 140 list->link.next = list->link.prev = &list->link; 141 list->offset = offset; 142} 143 144 145// #pragma mark - Guarded Heap 146 147 148#define GUARDED_HEAP_PAGE_FLAG_USED 0x01 149#define GUARDED_HEAP_PAGE_FLAG_FIRST 0x02 150#define GUARDED_HEAP_PAGE_FLAG_GUARD 0x04 151#define GUARDED_HEAP_PAGE_FLAG_DEAD 0x08 152#define GUARDED_HEAP_PAGE_FLAG_AREA 0x10 153 154#define GUARDED_HEAP_INITIAL_SIZE 1 * 1024 * 1024 155#define GUARDED_HEAP_GROW_SIZE 2 * 1024 * 1024 156#define GUARDED_HEAP_AREA_USE_THRESHOLD 1 * 1024 * 1024 157 158 159struct guarded_heap; 160 161struct guarded_heap_page { 162 uint8 flags; 163 size_t allocation_size; 164 void* allocation_base; 165 size_t alignment; 166 thread_id allocating_thread; 167 thread_id freeing_thread; 168 list_link free_list_link; 169 size_t alloc_stack_trace_depth; 170 size_t free_stack_trace_depth; 171 addr_t stack_trace[kMaxStackTraceDepth]; 172}; 173 174struct guarded_heap_area { 175 guarded_heap* heap; 176 guarded_heap_area* next; 177 area_id area; 178 addr_t base; 179 size_t size; 180 size_t page_count; 181 size_t used_pages; 182 mutex lock; 183 struct list free_list; 184 guarded_heap_page pages[0]; 185}; 186 187struct guarded_heap { 188 rw_lock lock; 189 size_t page_count; 190 size_t used_pages; 191 uint32 area_creation_counter; 192 bool reuse_memory; 193 guarded_heap_area* areas; 194}; 195 196 197static guarded_heap sGuardedHeap = { 198 RW_LOCK_INITIALIZER("guarded heap lock"), 199 0, 0, 0, true, NULL 200}; 201 202 203static void dump_guarded_heap_page(void* address, bool doPanic = false); 204 205 206static void 207guarded_heap_segfault_handler(int signal, siginfo_t* signalInfo, void* vregs) 208{ 209 if (signal != SIGSEGV) 210 return; 211 212 if (signalInfo->si_code != SEGV_ACCERR) { 213 // Not ours. 214 panic("generic segfault"); 215 return; 216 } 217 218 dump_guarded_heap_page(signalInfo->si_addr, true); 219 220 exit(-1); 221} 222 223 224static void 225guarded_heap_page_protect(guarded_heap_area& area, size_t pageIndex, 226 uint32 protection) 227{ 228 addr_t address = area.base + pageIndex * B_PAGE_SIZE; 229 mprotect((void*)address, B_PAGE_SIZE, protection); 230} 231 232 233static void 234guarded_heap_print_stack_trace(addr_t stackTrace[], size_t depth) 235{ 236 char* imageName; 237 char* symbolName; 238 void* location; 239 bool exactMatch; 240 241 for (size_t i = 0; i < depth; i++) { 242 addr_t address = stackTrace[i]; 243 244 status_t status = __gRuntimeLoader->get_nearest_symbol_at_address( 245 (void*)address, NULL, NULL, &imageName, &symbolName, NULL, 246 &location, &exactMatch); 247 if (status != B_OK) { 248 print_stdout("\t%#" B_PRIxADDR " (lookup failed: %s)\n", address, 249 strerror(status)); 250 continue; 251 } 252 253 print_stdout("\t<%s> %s + %#" B_PRIxADDR "%s\n", imageName, symbolName, 254 address - (addr_t)location, exactMatch ? "" : " (nearest)"); 255 } 256} 257 258 259static void 260guarded_heap_print_stack_traces(guarded_heap_page& page) 261{ 262 if (page.alloc_stack_trace_depth > 0) { 263 print_stdout("alloc stack trace (%" B_PRIuSIZE "):\n", 264 page.alloc_stack_trace_depth); 265 guarded_heap_print_stack_trace(page.stack_trace, 266 page.alloc_stack_trace_depth); 267 } 268 269 if (page.free_stack_trace_depth > 0) { 270 print_stdout("free stack trace (%" B_PRIuSIZE "):\n", 271 page.free_stack_trace_depth); 272 guarded_heap_print_stack_trace( 273 &page.stack_trace[page.alloc_stack_trace_depth], 274 page.free_stack_trace_depth); 275 } 276} 277 278 279static size_t 280guarded_heap_fill_stack_trace(addr_t stackTrace[], size_t maxDepth, 281 size_t skipFrames) 282{ 283 if (maxDepth == 0) 284 return 0; 285 286 void** stackBase = tls_address(sStackBaseTLSIndex); 287 void** stackEnd = tls_address(sStackEndTLSIndex); 288 if (*stackBase == NULL || *stackEnd == NULL) { 289 thread_info threadInfo; 290 status_t result = get_thread_info(find_thread(NULL), &threadInfo); 291 if (result != B_OK) 292 return 0; 293 294 *stackBase = (void*)threadInfo.stack_base; 295 *stackEnd = (void*)threadInfo.stack_end; 296 } 297 298 int32 traceDepth = __arch_get_stack_trace(stackTrace, maxDepth, skipFrames, 299 (addr_t)*stackBase, (addr_t)*stackEnd); 300 301 return traceDepth < 0 ? 0 : traceDepth; 302} 303 304 305static void 306guarded_heap_page_allocate(guarded_heap_area& area, size_t startPageIndex, 307 size_t pagesNeeded, size_t allocationSize, size_t alignment, 308 void* allocationBase) 309{ 310 if (pagesNeeded < 2) { 311 panic("need to allocate at least 2 pages, one for guard\n"); 312 return; 313 } 314 315 guarded_heap_page* firstPage = NULL; 316 for (size_t i = 0; i < pagesNeeded; i++) { 317 guarded_heap_page& page = area.pages[startPageIndex + i]; 318 page.flags = GUARDED_HEAP_PAGE_FLAG_USED; 319 if (i == 0) { 320 page.allocating_thread = find_thread(NULL); 321 page.freeing_thread = -1; 322 page.allocation_size = allocationSize; 323 page.allocation_base = allocationBase; 324 page.alignment = alignment; 325 page.flags |= GUARDED_HEAP_PAGE_FLAG_FIRST; 326 page.alloc_stack_trace_depth = guarded_heap_fill_stack_trace( 327 page.stack_trace, sStackTraceDepth, 2); 328 page.free_stack_trace_depth = 0; 329 firstPage = &page; 330 } else { 331 page.allocating_thread = firstPage->allocating_thread; 332 page.freeing_thread = -1; 333 page.allocation_size = allocationSize; 334 page.allocation_base = allocationBase; 335 page.alignment = alignment; 336 page.alloc_stack_trace_depth = 0; 337 page.free_stack_trace_depth = 0; 338 } 339 340 list_remove_item(&area.free_list, &page); 341 342 if (i == pagesNeeded - 1) { 343 page.flags |= GUARDED_HEAP_PAGE_FLAG_GUARD; 344 guarded_heap_page_protect(area, startPageIndex + i, 0); 345 } else { 346 guarded_heap_page_protect(area, startPageIndex + i, 347 B_READ_AREA | B_WRITE_AREA); 348 } 349 } 350} 351 352 353static void 354guarded_heap_free_page(guarded_heap_area& area, size_t pageIndex, 355 bool force = false) 356{ 357 guarded_heap_page& page = area.pages[pageIndex]; 358 359 if (area.heap->reuse_memory || force) 360 page.flags = 0; 361 else 362 page.flags |= GUARDED_HEAP_PAGE_FLAG_DEAD; 363 364 page.freeing_thread = find_thread(NULL); 365 366 list_add_item(&area.free_list, &page); 367 368 guarded_heap_page_protect(area, pageIndex, 0); 369} 370 371 372static void 373guarded_heap_pages_allocated(guarded_heap& heap, size_t pagesAllocated) 374{ 375 atomic_add((int32*)&heap.used_pages, pagesAllocated); 376} 377 378 379static void* 380guarded_heap_area_allocate(guarded_heap_area& area, size_t pagesNeeded, 381 size_t size, size_t alignment) 382{ 383 if (pagesNeeded > area.page_count - area.used_pages) 384 return NULL; 385 386 // We use the free list this way so that the page that has been free for 387 // the longest time is allocated. This keeps immediate re-use (that may 388 // hide bugs) to a minimum. 389 guarded_heap_page* page 390 = (guarded_heap_page*)list_get_next_item(&area.free_list, NULL); 391 392 for (; page != NULL; 393 page = (guarded_heap_page*)list_get_next_item(&area.free_list, page)) { 394 395 if ((page->flags & GUARDED_HEAP_PAGE_FLAG_USED) != 0) 396 continue; 397 398 size_t pageIndex = page - area.pages; 399 if (pageIndex > area.page_count - pagesNeeded) 400 continue; 401 402 // Candidate, check if we have enough pages going forward 403 // (including the guard page). 404 bool candidate = true; 405 for (size_t j = 1; j < pagesNeeded; j++) { 406 if ((area.pages[pageIndex + j].flags & GUARDED_HEAP_PAGE_FLAG_USED) 407 != 0) { 408 candidate = false; 409 break; 410 } 411 } 412 413 if (!candidate) 414 continue; 415 416 size_t offset = size & (B_PAGE_SIZE - 1); 417 void* result = (void*)((area.base + pageIndex * B_PAGE_SIZE 418 + (offset > 0 ? B_PAGE_SIZE - offset : 0)) & ~(alignment - 1)); 419 420 guarded_heap_page_allocate(area, pageIndex, pagesNeeded, size, 421 alignment, result); 422 423 area.used_pages += pagesNeeded; 424 guarded_heap_pages_allocated(*area.heap, pagesNeeded); 425 return result; 426 } 427 428 return NULL; 429} 430 431 432static bool 433guarded_heap_area_init(guarded_heap& heap, area_id id, void* baseAddress, 434 size_t size) 435{ 436 guarded_heap_area* area = (guarded_heap_area*)baseAddress; 437 area->heap = &heap; 438 area->area = id; 439 area->size = size; 440 area->page_count = area->size / B_PAGE_SIZE; 441 area->used_pages = 0; 442 443 size_t pagesNeeded = (sizeof(guarded_heap_area) 444 + area->page_count * sizeof(guarded_heap_page) 445 + B_PAGE_SIZE - 1) / B_PAGE_SIZE; 446 447 area->page_count -= pagesNeeded; 448 area->size = area->page_count * B_PAGE_SIZE; 449 area->base = (addr_t)baseAddress + pagesNeeded * B_PAGE_SIZE; 450 451 mutex_init(&area->lock, "guarded_heap_area_lock"); 452 453 list_init_etc(&area->free_list, 454 offsetof(guarded_heap_page, free_list_link)); 455 456 for (size_t i = 0; i < area->page_count; i++) 457 guarded_heap_free_page(*area, i, true); 458 459 area->next = heap.areas; 460 heap.areas = area; 461 heap.page_count += area->page_count; 462 463 return true; 464} 465 466 467static bool 468guarded_heap_area_create(guarded_heap& heap, size_t size) 469{ 470 for (size_t trySize = size; trySize >= 1 * 1024 * 1024; 471 trySize /= 2) { 472 473 void* baseAddress = NULL; 474 area_id id = create_area("guarded_heap_area", &baseAddress, 475 B_ANY_ADDRESS, trySize, B_NO_LOCK, B_READ_AREA | B_WRITE_AREA); 476 477 if (id < 0) 478 continue; 479 480 if (guarded_heap_area_init(heap, id, baseAddress, trySize)) 481 return true; 482 483 delete_area(id); 484 } 485 486 panic("failed to allocate a new heap area"); 487 return false; 488} 489 490 491static bool 492guarded_heap_add_area(guarded_heap& heap, uint32 counter) 493{ 494 WriteLocker areaListWriteLocker(heap.lock); 495 if (heap.area_creation_counter != counter) 496 return false; 497 498 return guarded_heap_area_create(heap, GUARDED_HEAP_GROW_SIZE); 499} 500 501 502static void* 503guarded_heap_allocate_with_area(size_t size, size_t alignment) 504{ 505 size_t infoSpace = alignment >= B_PAGE_SIZE ? B_PAGE_SIZE 506 : (sizeof(guarded_heap_page) + alignment - 1) & ~(alignment - 1); 507 508 size_t pagesNeeded = (size + infoSpace + B_PAGE_SIZE - 1) / B_PAGE_SIZE; 509 510 if (alignment > B_PAGE_SIZE) 511 pagesNeeded += alignment / B_PAGE_SIZE - 1; 512 513 void* address = NULL; 514 area_id area = create_area("guarded_heap_huge_allocation", &address, 515 B_ANY_ADDRESS, (pagesNeeded + 1) * B_PAGE_SIZE, B_NO_LOCK, 516 B_READ_AREA | B_WRITE_AREA); 517 if (area < 0) { 518 panic("failed to create area for allocation of %" B_PRIuSIZE " pages", 519 pagesNeeded); 520 return NULL; 521 } 522 523 // We just use a page object 524 guarded_heap_page* page = (guarded_heap_page*)address; 525 page->flags = GUARDED_HEAP_PAGE_FLAG_USED | GUARDED_HEAP_PAGE_FLAG_FIRST 526 | GUARDED_HEAP_PAGE_FLAG_AREA; 527 page->allocation_size = size; 528 page->allocation_base = (void*)(((addr_t)address 529 + pagesNeeded * B_PAGE_SIZE - size) & ~(alignment - 1)); 530 page->alignment = alignment; 531 page->allocating_thread = find_thread(NULL); 532 page->freeing_thread = -1; 533 page->alloc_stack_trace_depth = guarded_heap_fill_stack_trace( 534 page->stack_trace, sStackTraceDepth, 2); 535 page->free_stack_trace_depth = 0; 536 537 if (alignment <= B_PAGE_SIZE) { 538 // Protect just the guard page. 539 mprotect((void*)((addr_t)address + pagesNeeded * B_PAGE_SIZE), 540 B_PAGE_SIZE, 0); 541 } else { 542 // Protect empty pages before the allocation start... 543 addr_t protectedStart = (addr_t)address + B_PAGE_SIZE; 544 size_t protectedSize = (addr_t)page->allocation_base - protectedStart; 545 if (protectedSize > 0) 546 mprotect((void*)protectedStart, protectedSize, 0); 547 548 // ... and after allocation end. 549 size_t allocatedPages = (size + B_PAGE_SIZE - 1) / B_PAGE_SIZE; 550 protectedStart = (addr_t)page->allocation_base 551 + allocatedPages * B_PAGE_SIZE; 552 protectedSize = (addr_t)address + (pagesNeeded + 1) * B_PAGE_SIZE 553 - protectedStart; 554 555 // There is at least the guard page. 556 mprotect((void*)protectedStart, protectedSize, 0); 557 } 558 559 return page->allocation_base; 560} 561 562 563static void* 564guarded_heap_allocate(guarded_heap& heap, size_t size, size_t alignment) 565{ 566 if (alignment == 0) 567 alignment = 1; 568 569 size_t pagesNeeded = (size + B_PAGE_SIZE - 1) / B_PAGE_SIZE + 1; 570 if (alignment > B_PAGE_SIZE 571 || pagesNeeded * B_PAGE_SIZE >= GUARDED_HEAP_AREA_USE_THRESHOLD) { 572 // Don't bother, use an area directly. Since it will also fault once 573 // it is deleted, that fits our model quite nicely. 574 return guarded_heap_allocate_with_area(size, alignment); 575 } 576 577 void* result = NULL; 578 579 ReadLocker areaListReadLocker(heap.lock); 580 for (guarded_heap_area* area = heap.areas; area != NULL; 581 area = area->next) { 582 583 MutexLocker locker(area->lock); 584 result = guarded_heap_area_allocate(*area, pagesNeeded, size, 585 alignment); 586 if (result != NULL) 587 break; 588 } 589 590 uint32 counter = heap.area_creation_counter; 591 areaListReadLocker.Unlock(); 592 593 if (result == NULL) { 594 guarded_heap_add_area(heap, counter); 595 return guarded_heap_allocate(heap, size, alignment); 596 } 597 598 if (result == NULL) 599 panic("ran out of memory"); 600 601 return result; 602} 603 604 605static guarded_heap_area* 606guarded_heap_get_locked_area_for(guarded_heap& heap, void* address) 607{ 608 ReadLocker areaListReadLocker(heap.lock); 609 for (guarded_heap_area* area = heap.areas; area != NULL; 610 area = area->next) { 611 if ((addr_t)address < area->base) 612 continue; 613 614 if ((addr_t)address >= area->base + area->size) 615 continue; 616 617 mutex_lock(&area->lock); 618 return area; 619 } 620 621 return NULL; 622} 623 624 625static size_t 626guarded_heap_area_page_index_for(guarded_heap_area& area, void* address) 627{ 628 size_t pageIndex = ((addr_t)address - area.base) / B_PAGE_SIZE; 629 guarded_heap_page& page = area.pages[pageIndex]; 630 if ((page.flags & GUARDED_HEAP_PAGE_FLAG_USED) == 0) { 631 panic("tried to free %p which points at page %" B_PRIuSIZE 632 " which is not marked in use", address, pageIndex); 633 return area.page_count; 634 } 635 636 if ((page.flags & GUARDED_HEAP_PAGE_FLAG_GUARD) != 0) { 637 panic("tried to free %p which points at page %" B_PRIuSIZE 638 " which is a guard page", address, pageIndex); 639 return area.page_count; 640 } 641 642 if ((page.flags & GUARDED_HEAP_PAGE_FLAG_FIRST) == 0) { 643 panic("tried to free %p which points at page %" B_PRIuSIZE 644 " which is not an allocation first page", address, pageIndex); 645 return area.page_count; 646 } 647 648 if ((page.flags & GUARDED_HEAP_PAGE_FLAG_DEAD) != 0) { 649 panic("tried to free %p which points at page %" B_PRIuSIZE 650 " which is a dead page", address, pageIndex); 651 return area.page_count; 652 } 653 654 return pageIndex; 655} 656 657 658static bool 659guarded_heap_area_free(guarded_heap_area& area, void* address) 660{ 661 size_t pageIndex = guarded_heap_area_page_index_for(area, address); 662 if (pageIndex >= area.page_count) 663 return false; 664 665 size_t pagesFreed = 0; 666 guarded_heap_page* page = &area.pages[pageIndex]; 667 while ((page->flags & GUARDED_HEAP_PAGE_FLAG_GUARD) == 0) { 668 // Mark the allocation page as free. 669 guarded_heap_free_page(area, pageIndex); 670 if (pagesFreed == 0 && sStackTraceDepth > 0) { 671 size_t freeEntries 672 = kMaxStackTraceDepth - page->alloc_stack_trace_depth; 673 674 page->free_stack_trace_depth = guarded_heap_fill_stack_trace( 675 &page->stack_trace[page->alloc_stack_trace_depth], 676 min_c(freeEntries, sStackTraceDepth), 2); 677 } 678 679 pagesFreed++; 680 pageIndex++; 681 page = &area.pages[pageIndex]; 682 } 683 684 // Mark the guard page as free as well. 685 guarded_heap_free_page(area, pageIndex); 686 pagesFreed++; 687 688 if (area.heap->reuse_memory) { 689 area.used_pages -= pagesFreed; 690 atomic_add((int32*)&area.heap->used_pages, -pagesFreed); 691 } 692 693 return true; 694} 695 696 697static guarded_heap_page* 698guarded_heap_area_allocation_for(void* address, area_id& allocationArea) 699{ 700 allocationArea = area_for(address); 701 if (allocationArea < 0) 702 return NULL; 703 704 area_info areaInfo; 705 if (get_area_info(allocationArea, &areaInfo) != B_OK) 706 return NULL; 707 708 guarded_heap_page* page = (guarded_heap_page*)areaInfo.address; 709 if (page->flags != (GUARDED_HEAP_PAGE_FLAG_USED 710 | GUARDED_HEAP_PAGE_FLAG_FIRST | GUARDED_HEAP_PAGE_FLAG_AREA)) { 711 return NULL; 712 } 713 714 if (page->allocation_base != address) 715 return NULL; 716 if (page->allocation_size >= areaInfo.size) 717 return NULL; 718 719 return page; 720} 721 722 723static bool 724guarded_heap_free_area_allocation(void* address) 725{ 726 area_id allocationArea; 727 if (guarded_heap_area_allocation_for(address, allocationArea) == NULL) 728 return false; 729 730 delete_area(allocationArea); 731 return true; 732} 733 734 735static bool 736guarded_heap_free(void* address) 737{ 738 if (address == NULL) 739 return true; 740 741 guarded_heap_area* area = guarded_heap_get_locked_area_for(sGuardedHeap, 742 address); 743 if (area == NULL) 744 return guarded_heap_free_area_allocation(address); 745 746 MutexLocker locker(area->lock, true); 747 return guarded_heap_area_free(*area, address); 748} 749 750 751static void* 752guarded_heap_realloc(void* address, size_t newSize) 753{ 754 guarded_heap_area* area = guarded_heap_get_locked_area_for(sGuardedHeap, 755 address); 756 757 size_t oldSize; 758 area_id allocationArea = -1; 759 if (area != NULL) { 760 MutexLocker locker(area->lock, true); 761 size_t pageIndex = guarded_heap_area_page_index_for(*area, address); 762 if (pageIndex >= area->page_count) 763 return NULL; 764 765 guarded_heap_page& page = area->pages[pageIndex]; 766 oldSize = page.allocation_size; 767 locker.Unlock(); 768 } else { 769 guarded_heap_page* page = guarded_heap_area_allocation_for(address, 770 allocationArea); 771 if (page == NULL) 772 return NULL; 773 774 oldSize = page->allocation_size; 775 } 776 777 if (oldSize == newSize) 778 return address; 779 780 void* newBlock = guarded_heap_allocate(sGuardedHeap, newSize, 781 sDefaultAlignment); 782 if (newBlock == NULL) 783 return NULL; 784 785 memcpy(newBlock, address, min_c(oldSize, newSize)); 786 787 if (allocationArea >= 0) 788 delete_area(allocationArea); 789 else { 790 MutexLocker locker(area->lock); 791 guarded_heap_area_free(*area, address); 792 } 793 794 return newBlock; 795} 796 797 798// #pragma mark - Debugger commands 799 800 801static void 802dump_guarded_heap_page(guarded_heap_page& page) 803{ 804 printf("flags:"); 805 if ((page.flags & GUARDED_HEAP_PAGE_FLAG_USED) != 0) 806 printf(" used"); 807 if ((page.flags & GUARDED_HEAP_PAGE_FLAG_FIRST) != 0) 808 printf(" first"); 809 if ((page.flags & GUARDED_HEAP_PAGE_FLAG_GUARD) != 0) 810 printf(" guard"); 811 if ((page.flags & GUARDED_HEAP_PAGE_FLAG_DEAD) != 0) 812 printf(" dead"); 813 printf("\n"); 814 815 printf("allocation size: %" B_PRIuSIZE "\n", page.allocation_size); 816 printf("allocation base: %p\n", page.allocation_base); 817 printf("alignment: %" B_PRIuSIZE "\n", page.alignment); 818 printf("allocating thread: %" B_PRId32 "\n", page.allocating_thread); 819 printf("freeing thread: %" B_PRId32 "\n", page.freeing_thread); 820} 821 822 823static void 824dump_guarded_heap_page(void* address, bool doPanic) 825{ 826 // Find the area that contains this page. 827 guarded_heap_area* area = NULL; 828 for (guarded_heap_area* candidate = sGuardedHeap.areas; candidate != NULL; 829 candidate = candidate->next) { 830 831 if ((addr_t)address < candidate->base) 832 continue; 833 if ((addr_t)address >= candidate->base + candidate->size) 834 continue; 835 836 area = candidate; 837 break; 838 } 839 840 if (area == NULL) { 841 panic("didn't find area for address %p\n", address); 842 return; 843 } 844 845 size_t pageIndex = ((addr_t)address - area->base) / B_PAGE_SIZE; 846 guarded_heap_page& page = area->pages[pageIndex]; 847 dump_guarded_heap_page(page); 848 849 // Find the first page and dump the stack traces. 850 for (ssize_t candidateIndex = (ssize_t)pageIndex; 851 sStackTraceDepth > 0 && candidateIndex >= 0; candidateIndex--) { 852 guarded_heap_page& candidate = area->pages[candidateIndex]; 853 if ((candidate.flags & GUARDED_HEAP_PAGE_FLAG_FIRST) == 0) 854 continue; 855 856 guarded_heap_print_stack_traces(candidate); 857 break; 858 } 859 860 if (doPanic) { 861 // Note: we do this the complicated way because we absolutely don't 862 // want any character conversion to happen that might provoke other 863 // segfaults in the locale backend. Therefore we avoid using any string 864 // formats, resulting in the mess below. 865 866 #define DO_PANIC(state) \ 867 panic("thread %" B_PRId32 " tried accessing address %p which is " \ 868 state " (base: 0x%" B_PRIxADDR ", size: %" B_PRIuSIZE \ 869 ", alignment: %" B_PRIuSIZE ", allocated by thread: %" \ 870 B_PRId32 ", freed by thread: %" B_PRId32 ")", \ 871 find_thread(NULL), address, page.allocation_base, \ 872 page.allocation_size, page.alignment, page.allocating_thread, \ 873 page.freeing_thread) 874 875 if ((page.flags & GUARDED_HEAP_PAGE_FLAG_USED) == 0) 876 DO_PANIC("not allocated"); 877 else if ((page.flags & GUARDED_HEAP_PAGE_FLAG_GUARD) != 0) 878 DO_PANIC("a guard page"); 879 else if ((page.flags & GUARDED_HEAP_PAGE_FLAG_DEAD) != 0) 880 DO_PANIC("a dead page"); 881 else 882 DO_PANIC("in an unknown state"); 883 884 #undef DO_PANIC 885 } 886} 887 888 889static void 890dump_guarded_heap_area(guarded_heap_area& area) 891{ 892 printf("guarded heap area: %p\n", &area); 893 printf("next heap area: %p\n", area.next); 894 printf("guarded heap: %p\n", area.heap); 895 printf("area id: %" B_PRId32 "\n", area.area); 896 printf("base: 0x%" B_PRIxADDR "\n", area.base); 897 printf("size: %" B_PRIuSIZE "\n", area.size); 898 printf("page count: %" B_PRIuSIZE "\n", area.page_count); 899 printf("used pages: %" B_PRIuSIZE "\n", area.used_pages); 900 printf("lock: %p\n", &area.lock); 901 902 size_t freeCount = 0; 903 void* item = list_get_next_item(&area.free_list, NULL); 904 while (item != NULL) { 905 freeCount++; 906 907 if ((((guarded_heap_page*)item)->flags & GUARDED_HEAP_PAGE_FLAG_USED) 908 != 0) { 909 printf("free list broken, page %p not actually free\n", item); 910 } 911 912 item = list_get_next_item(&area.free_list, item); 913 } 914 915 printf("free_list: %p (%" B_PRIuSIZE " free)\n", &area.free_list, 916 freeCount); 917 918 freeCount = 0; 919 size_t runLength = 0; 920 size_t longestRun = 0; 921 for (size_t i = 0; i <= area.page_count; i++) { 922 guarded_heap_page& page = area.pages[i]; 923 if (i == area.page_count 924 || (page.flags & GUARDED_HEAP_PAGE_FLAG_USED) != 0) { 925 freeCount += runLength; 926 if (runLength > longestRun) 927 longestRun = runLength; 928 runLength = 0; 929 continue; 930 } 931 932 runLength = 1; 933 for (size_t j = 1; j < area.page_count - i; j++) { 934 if ((area.pages[i + j].flags & GUARDED_HEAP_PAGE_FLAG_USED) != 0) 935 break; 936 937 runLength++; 938 } 939 940 i += runLength - 1; 941 } 942 943 printf("longest free run: %" B_PRIuSIZE " (%" B_PRIuSIZE " free)\n", 944 longestRun, freeCount); 945 946 printf("pages: %p\n", area.pages); 947} 948 949 950static void 951dump_guarded_heap(guarded_heap& heap) 952{ 953 printf("guarded heap: %p\n", &heap); 954 printf("rw lock: %p\n", &heap.lock); 955 printf("page count: %" B_PRIuSIZE "\n", heap.page_count); 956 printf("used pages: %" B_PRIuSIZE "\n", heap.used_pages); 957 printf("area creation counter: %" B_PRIu32 "\n", 958 heap.area_creation_counter); 959 960 size_t areaCount = 0; 961 guarded_heap_area* area = heap.areas; 962 while (area != NULL) { 963 areaCount++; 964 area = area->next; 965 } 966 967 printf("areas: %p (%" B_PRIuSIZE ")\n", heap.areas, areaCount); 968} 969 970 971static void 972dump_allocations(guarded_heap& heap, bool statsOnly, thread_id thread) 973{ 974 WriteLocker heapLocker(heap.lock); 975 976 size_t allocationCount = 0; 977 size_t allocationSize = 0; 978 for (guarded_heap_area* area = heap.areas; area != NULL; 979 area = area->next) { 980 981 MutexLocker areaLocker(area->lock); 982 for (size_t i = 0; i < area->page_count; i++) { 983 guarded_heap_page& page = area->pages[i]; 984 if ((page.flags & GUARDED_HEAP_PAGE_FLAG_FIRST) == 0 985 || (page.flags & GUARDED_HEAP_PAGE_FLAG_DEAD) != 0) { 986 continue; 987 } 988 989 if (thread >= 0 && thread != page.allocating_thread) 990 continue; 991 992 allocationCount++; 993 allocationSize += page.allocation_size; 994 995 if (statsOnly) 996 continue; 997 998 print_stdout("allocation: base: %p; size: %" B_PRIuSIZE 999 "; thread: %" B_PRId32 "; alignment: %" B_PRIuSIZE "\n", 1000 page.allocation_base, page.allocation_size, 1001 page.allocating_thread, page.alignment); 1002 1003 guarded_heap_print_stack_trace(page.stack_trace, 1004 page.alloc_stack_trace_depth); 1005 } 1006 } 1007 1008 print_stdout("total allocations: %" B_PRIuSIZE ", %" B_PRIuSIZE " bytes\n", 1009 allocationCount, allocationSize); 1010} 1011 1012 1013static void 1014dump_allocations_full() 1015{ 1016 dump_allocations(sGuardedHeap, false, -1); 1017} 1018 1019 1020// #pragma mark - Heap Debug API 1021 1022 1023static void 1024guarded_heap_set_memory_reuse(bool enabled) 1025{ 1026 sGuardedHeap.reuse_memory = enabled; 1027} 1028 1029 1030static void 1031guarded_heap_set_debugger_calls(bool enabled) 1032{ 1033 sDebuggerCalls = enabled; 1034} 1035 1036 1037static void 1038guarded_heap_set_default_alignment(size_t defaultAlignment) 1039{ 1040 sDefaultAlignment = defaultAlignment; 1041} 1042 1043 1044static void 1045guarded_heap_dump_allocations(bool statsOnly, thread_id thread) 1046{ 1047 dump_allocations(sGuardedHeap, statsOnly, thread); 1048} 1049 1050 1051static void 1052guarded_heap_dump_heaps(bool dumpAreas, bool dumpBins) 1053{ 1054 WriteLocker heapLocker(sGuardedHeap.lock); 1055 dump_guarded_heap(sGuardedHeap); 1056 if (!dumpAreas) 1057 return; 1058 1059 for (guarded_heap_area* area = sGuardedHeap.areas; area != NULL; 1060 area = area->next) { 1061 MutexLocker areaLocker(area->lock); 1062 dump_guarded_heap_area(*area); 1063 1064 if (!dumpBins) 1065 continue; 1066 1067 for (size_t i = 0; i < area->page_count; i++) { 1068 dump_guarded_heap_page(area->pages[i]); 1069 if ((area->pages[i].flags & GUARDED_HEAP_PAGE_FLAG_FIRST) != 0) 1070 guarded_heap_print_stack_traces(area->pages[i]); 1071 } 1072 } 1073} 1074 1075 1076static status_t 1077guarded_heap_set_dump_allocations_on_exit(bool enabled) 1078{ 1079 sDumpAllocationsOnExit = enabled; 1080 return B_OK; 1081} 1082 1083 1084static status_t 1085guarded_heap_set_stack_trace_depth(size_t stackTraceDepth) 1086{ 1087 if (stackTraceDepth == 0) { 1088 sStackTraceDepth = 0; 1089 return B_OK; 1090 } 1091 1092 // This is rather wasteful, but these are going to be filled lazily by each 1093 // thread on alloc/free. Therefore we cannot use a dynamic allocation and 1094 // just store a pointer to. Since we only need to store two addresses, we 1095 // use two TLS slots and set them to point at the stack base/end. 1096 if (sStackBaseTLSIndex < 0) { 1097 sStackBaseTLSIndex = tls_allocate(); 1098 if (sStackBaseTLSIndex < 0) 1099 return sStackBaseTLSIndex; 1100 } 1101 1102 if (sStackEndTLSIndex < 0) { 1103 sStackEndTLSIndex = tls_allocate(); 1104 if (sStackEndTLSIndex < 0) 1105 return sStackEndTLSIndex; 1106 } 1107 1108 sStackTraceDepth = min_c(stackTraceDepth, kMaxStackTraceDepth); 1109 return B_OK; 1110} 1111 1112 1113// #pragma mark - Init 1114 1115 1116static void 1117init_after_fork() 1118{ 1119 // The memory has actually been copied (or is in a copy on write state) but 1120 // but the area ids have changed. 1121 for (guarded_heap_area* area = sGuardedHeap.areas; area != NULL; 1122 area = area->next) { 1123 area->area = area_for(area); 1124 if (area->area < 0) 1125 panic("failed to find area for heap area %p after fork", area); 1126 } 1127} 1128 1129 1130static status_t 1131guarded_heap_init(void) 1132{ 1133 if (!guarded_heap_area_create(sGuardedHeap, GUARDED_HEAP_INITIAL_SIZE)) 1134 return B_ERROR; 1135 1136 // Install a segfault handler so we can print some info before going down. 1137 struct sigaction action; 1138 action.sa_handler = (__sighandler_t)guarded_heap_segfault_handler; 1139 action.sa_flags = SA_SIGINFO; 1140 action.sa_userdata = NULL; 1141 sigemptyset(&action.sa_mask); 1142 sigaction(SIGSEGV, &action, NULL); 1143 1144 atfork(&init_after_fork); 1145 // Note: Needs malloc(). Hence we need to be fully initialized. 1146 // TODO: We should actually also install a hook that is called before 1147 // fork() is being executed. In a multithreaded app it would need to 1148 // acquire *all* allocator locks, so that we don't fork() an 1149 // inconsistent state. 1150 1151 return B_OK; 1152} 1153 1154 1155static void 1156guarded_heap_terminate_after() 1157{ 1158 if (sDumpAllocationsOnExit) 1159 dump_allocations_full(); 1160} 1161 1162 1163// #pragma mark - Public API 1164 1165 1166static void* 1167heap_memalign(size_t alignment, size_t size) 1168{ 1169 if (size == 0) 1170 size = 1; 1171 1172 return guarded_heap_allocate(sGuardedHeap, size, alignment); 1173} 1174 1175 1176static void* 1177heap_malloc(size_t size) 1178{ 1179 return heap_memalign(sDefaultAlignment, size); 1180} 1181 1182 1183static void 1184heap_free(void* address) 1185{ 1186 if (!guarded_heap_free(address)) 1187 panic("free failed for address %p", address); 1188} 1189 1190 1191static void* 1192heap_realloc(void* address, size_t newSize) 1193{ 1194 if (newSize == 0) { 1195 free(address); 1196 return NULL; 1197 } 1198 1199 if (address == NULL) 1200 return heap_memalign(sDefaultAlignment, newSize); 1201 1202 return guarded_heap_realloc(address, newSize); 1203} 1204 1205 1206heap_implementation __mallocGuardedHeap = { 1207 guarded_heap_init, 1208 guarded_heap_terminate_after, 1209 1210 heap_memalign, 1211 heap_malloc, 1212 heap_free, 1213 heap_realloc, 1214 1215 NULL, // calloc 1216 NULL, // valloc 1217 NULL, // posix_memalign 1218 1219 NULL, // start_wall_checking 1220 NULL, // stop_wall_checking 1221 NULL, // set_paranoid_validation 1222 1223 guarded_heap_set_memory_reuse, 1224 guarded_heap_set_debugger_calls, 1225 guarded_heap_set_default_alignment, 1226 1227 NULL, // validate_heaps 1228 NULL, // validate_walls 1229 1230 guarded_heap_dump_allocations, 1231 guarded_heap_dump_heaps, 1232 heap_malloc, 1233 1234 NULL, // get_allocation_info 1235 1236 guarded_heap_set_dump_allocations_on_exit, 1237 guarded_heap_set_stack_trace_depth 1238}; 1239