src/system/libroot/posix/malloc_debug/guarded_heap.cpp

   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
  27 static const size_t kMaxStackTraceDepth = 50;
  28
  29
  30 static bool sDebuggerCalls = true;
  31 static bool sDumpAllocationsOnExit = false;
  32 static size_t sStackTraceDepth = 0;
  33 static int32 sStackBaseTLSIndex = -1;
  34 static int32 sStackEndTLSIndex = -1;
  35
  36 #if __cplusplus >= 201103L
  37 #include <cstddef>
  38 using namespace std;
  39 static size_t sDefaultAlignment = alignof(max_align_t);
  40 #else
  41 static size_t sDefaultAlignment = 8;
  42 #endif
  43
  44
  45 static void
  46 panic(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(buffer);
  59 }
  60
  61
  62 static void
  63 print_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
  85 struct list_link {
  86         list_link*      next;
  87         list_link*      prev;
  88 };
  89
  90 struct list {
  91         list_link       link;
  92         int32           offset;
  93 };
  94
  95
  96 static inline void
  97 list_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
 106 static inline void
 107 list_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
 119 static inline void*
 120 list_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
 137 static inline void
 138 list_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
 159 struct guarded_heap;
 160
 161 struct 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
 174 struct 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
 187 struct 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
 197 static guarded_heap sGuardedHeap = {
 198         RW_LOCK_INITIALIZER("guarded heap lock"),
 199         0, 0, 0, true, NULL
 200 };
 201
 202
 203 static void dump_guarded_heap_page(void* address, bool doPanic = false);
 204
 205
 206 static void
 207 guarded_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
 224 static void
 225 guarded_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
 233 static void
 234 guarded_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
 259 static void
 260 guarded_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
 279 static size_t
 280 guarded_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
 305 static void
 306 guarded_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
 353 static void
 354 guarded_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
 372 static void
 373 guarded_heap_pages_allocated(guarded_heap& heap, size_t pagesAllocated)
 374 {
 375         atomic_add((int32*)&heap.used_pages, pagesAllocated);
 376 }
 377
 378
 379 static void*
 380 guarded_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
 432 static bool
 433 guarded_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
 467 static bool
 468 guarded_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
 491 static bool
 492 guarded_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
 502 static void*
 503 guarded_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
 563 static void*
 564 guarded_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
 605 static guarded_heap_area*
 606 guarded_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
 625 static size_t
 626 guarded_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
 658 static bool
 659 guarded_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
 697 static guarded_heap_page*
 698 guarded_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
 723 static bool
 724 guarded_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
 735 static bool
 736 guarded_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
 751 static void*
 752 guarded_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
 801 static void
 802 dump_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
 823 static void
 824 dump_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
 889 static void
 890 dump_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
 950 static void
 951 dump_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
 971 static void
 972 dump_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
1013 static void
1014 dump_allocations_full()
1015 {
1016         dump_allocations(sGuardedHeap, false, -1);
1017 }
1018
1019
1020 // #pragma mark - Heap Debug API
1021
1022
1023 static void
1024 guarded_heap_set_memory_reuse(bool enabled)
1025 {
1026         sGuardedHeap.reuse_memory = enabled;
1027 }
1028
1029
1030 static void
1031 guarded_heap_set_debugger_calls(bool enabled)
1032 {
1033         sDebuggerCalls = enabled;
1034 }
1035
1036
1037 static void
1038 guarded_heap_set_default_alignment(size_t defaultAlignment)
1039 {
1040         sDefaultAlignment = defaultAlignment;
1041 }
1042
1043
1044 static void
1045 guarded_heap_dump_allocations(bool statsOnly, thread_id thread)
1046 {
1047         dump_allocations(sGuardedHeap, statsOnly, thread);
1048 }
1049
1050
1051 static void
1052 guarded_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
1076 static status_t
1077 guarded_heap_set_dump_allocations_on_exit(bool enabled)
1078 {
1079         sDumpAllocationsOnExit = enabled;
1080         return B_OK;
1081 }
1082
1083
1084 static status_t
1085 guarded_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
1116 static void
1117 init_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
1130 static status_t
1131 guarded_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
1155 static void
1156 guarded_heap_terminate_after()
1157 {
1158         if (sDumpAllocationsOnExit)
1159                 dump_allocations_full();
1160 }
1161
1162
1163 // #pragma mark - Public API
1164
1165
1166 static void*
1167 heap_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
1176 static void*
1177 heap_malloc(size_t size)
1178 {
1179         return heap_memalign(sDefaultAlignment, size);
1180 }
1181
1182
1183 static void
1184 heap_free(void* address)
1185 {
1186         if (!guarded_heap_free(address))
1187                 panic("free failed for address %p", address);
1188 }
1189
1190
1191 static void*
1192 heap_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
1206 heap_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 };