src/third_party/WebKit/Source/platform/heap/Heap.cpp

   1 /*
   2  * Copyright (C) 2013 Google Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  *     * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *     * Redistributions in binary form must reproduce the above
  11  * copyright notice, this list of conditions and the following disclaimer
  12  * in the documentation and/or other materials provided with the
  13  * distribution.
  14  *     * Neither the name of Google Inc. nor the names of its
  15  * contributors may be used to endorse or promote products derived from
  16  * this software without specific prior written permission.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 #include "config.h"
  32 #include "platform/heap/Heap.h"
  33
  34 #include "platform/ScriptForbiddenScope.h"
  35 #include "platform/Task.h"
  36 #include "platform/TraceEvent.h"
  37 #include "platform/heap/CallbackStack.h"
  38 #include "platform/heap/ThreadState.h"
  39 #include "public/platform/Platform.h"
  40 #include "wtf/AddressSpaceRandomization.h"
  41 #include "wtf/Assertions.h"
  42 #include "wtf/LeakAnnotations.h"
  43 #include "wtf/PassOwnPtr.h"
  44 #if ENABLE(GC_PROFILE_MARKING)
  45 #include "wtf/HashMap.h"
  46 #include "wtf/HashSet.h"
  47 #include "wtf/text/StringBuilder.h"
  48 #include "wtf/text/StringHash.h"
  49 #include <stdio.h>
  50 #include <utility>
  51 #endif
  52 #if ENABLE(GC_PROFILE_HEAP)
  53 #include "platform/TracedValue.h"
  54 #endif
  55
  56 #if OS(POSIX)
  57 #include <sys/mman.h>
  58 #include <unistd.h>
  59 #elif OS(WIN)
  60 #include <windows.h>
  61 #endif
  62
  63 namespace blink {
  64
  65 #if ENABLE(GC_PROFILE_MARKING)
  66 static String classOf(const void* object)
  67 {
  68     const GCInfo* gcInfo = Heap::findGCInfo(reinterpret_cast<Address>(const_cast<void*>(object)));
  69     if (gcInfo)
  70         return gcInfo->m_className;
  71
  72     return "unknown";
  73 }
  74 #endif
  75
  76 static bool vTableInitialized(void* objectPointer)
  77 {
  78     return !!(*reinterpret_cast<Address*>(objectPointer));
  79 }
  80
  81 #if OS(WIN)
  82 static bool IsPowerOf2(size_t power)
  83 {
  84     return !((power - 1) & power);
  85 }
  86 #endif
  87
  88 static Address roundToBlinkPageBoundary(void* base)
  89 {
  90     return reinterpret_cast<Address>((reinterpret_cast<uintptr_t>(base) + blinkPageOffsetMask) & blinkPageBaseMask);
  91 }
  92
  93 static size_t roundToOsPageSize(size_t size)
  94 {
  95     return (size + osPageSize() - 1) & ~(osPageSize() - 1);
  96 }
  97
  98 size_t osPageSize()
  99 {
 100 #if OS(POSIX)
 101     static const size_t pageSize = getpagesize();
 102 #else
 103     static size_t pageSize = 0;
 104     if (!pageSize) {
 105         SYSTEM_INFO info;
 106         GetSystemInfo(&info);
 107         pageSize = info.dwPageSize;
 108         ASSERT(IsPowerOf2(pageSize));
 109     }
 110 #endif
 111     return pageSize;
 112 }
 113
 114 class MemoryRegion {
 115 public:
 116     MemoryRegion(Address base, size_t size)
 117         : m_base(base)
 118         , m_size(size)
 119     {
 120         ASSERT(size > 0);
 121     }
 122
 123     bool contains(Address addr) const
 124     {
 125         return m_base <= addr && addr < (m_base + m_size);
 126     }
 127
 128
 129     bool contains(const MemoryRegion& other) const
 130     {
 131         return contains(other.m_base) && contains(other.m_base + other.m_size - 1);
 132     }
 133
 134     void release()
 135     {
 136 #if OS(POSIX)
 137         int err = munmap(m_base, m_size);
 138         RELEASE_ASSERT(!err);
 139 #else
 140         bool success = VirtualFree(m_base, 0, MEM_RELEASE);
 141         RELEASE_ASSERT(success);
 142 #endif
 143     }
 144
 145     WARN_UNUSED_RETURN bool commit()
 146     {
 147         ASSERT(Heap::heapDoesNotContainCacheIsEmpty());
 148 #if OS(POSIX)
 149         int err = mprotect(m_base, m_size, PROT_READ | PROT_WRITE);
 150         if (!err) {
 151             madvise(m_base, m_size, MADV_NORMAL);
 152             return true;
 153         }
 154         return false;
 155 #else
 156         void* result = VirtualAlloc(m_base, m_size, MEM_COMMIT, PAGE_READWRITE);
 157         return !!result;
 158 #endif
 159     }
 160
 161     void decommit()
 162     {
 163 #if OS(POSIX)
 164         int err = mprotect(m_base, m_size, PROT_NONE);
 165         RELEASE_ASSERT(!err);
 166         // FIXME: Consider using MADV_FREE on MacOS.
 167         madvise(m_base, m_size, MADV_DONTNEED);
 168 #else
 169         bool success = VirtualFree(m_base, m_size, MEM_DECOMMIT);
 170         RELEASE_ASSERT(success);
 171 #endif
 172     }
 173
 174     Address base() const { return m_base; }
 175     size_t size() const { return m_size; }
 176
 177 private:
 178     Address m_base;
 179     size_t m_size;
 180 };
 181
 182 // A PageMemoryRegion represents a chunk of reserved virtual address
 183 // space containing a number of blink heap pages. On Windows, reserved
 184 // virtual address space can only be given back to the system as a
 185 // whole. The PageMemoryRegion allows us to do that by keeping track
 186 // of the number of pages using it in order to be able to release all
 187 // of the virtual address space when there are no more pages using it.
 188 class PageMemoryRegion : public MemoryRegion {
 189 public:
 190     ~PageMemoryRegion()
 191     {
 192         release();
 193     }
 194
 195     void pageRemoved()
 196     {
 197         if (!--m_numPages)
 198             delete this;
 199     }
 200
 201     static PageMemoryRegion* allocate(size_t size, unsigned numPages)
 202     {
 203         ASSERT(Heap::heapDoesNotContainCacheIsEmpty());
 204
 205         // Compute a random blink page aligned address for the page memory
 206         // region and attempt to get the memory there.
 207         Address randomAddress = reinterpret_cast<Address>(WTF::getRandomPageBase());
 208         Address alignedRandomAddress = roundToBlinkPageBoundary(randomAddress);
 209
 210 #if OS(POSIX)
 211         Address base = static_cast<Address>(mmap(alignedRandomAddress, size, PROT_NONE, MAP_ANON | MAP_PRIVATE, -1, 0));
 212         RELEASE_ASSERT(base != MAP_FAILED);
 213         if (base == roundToBlinkPageBoundary(base))
 214             return new PageMemoryRegion(base, size, numPages);
 215
 216         // We failed to get a blink page aligned chunk of
 217         // memory. Unmap the chunk that we got and fall back to
 218         // overallocating and selecting an aligned sub part of what
 219         // we allocate.
 220         int error = munmap(base, size);
 221         RELEASE_ASSERT(!error);
 222         size_t allocationSize = size + blinkPageSize;
 223         base = static_cast<Address>(mmap(alignedRandomAddress, allocationSize, PROT_NONE, MAP_ANON | MAP_PRIVATE, -1, 0));
 224         RELEASE_ASSERT(base != MAP_FAILED);
 225
 226         Address end = base + allocationSize;
 227         Address alignedBase = roundToBlinkPageBoundary(base);
 228         Address regionEnd = alignedBase + size;
 229
 230         // If the allocated memory was not blink page aligned release
 231         // the memory before the aligned address.
 232         if (alignedBase != base)
 233             MemoryRegion(base, alignedBase - base).release();
 234
 235         // Free the additional memory at the end of the page if any.
 236         if (regionEnd < end)
 237             MemoryRegion(regionEnd, end - regionEnd).release();
 238
 239         return new PageMemoryRegion(alignedBase, size, numPages);
 240 #else
 241         Address base = static_cast<Address>(VirtualAlloc(alignedRandomAddress, size, MEM_RESERVE, PAGE_NOACCESS));
 242         if (base) {
 243             ASSERT(base == alignedRandomAddress);
 244             return new PageMemoryRegion(base, size, numPages);
 245         }
 246
 247         // We failed to get the random aligned address that we asked
 248         // for. Fall back to overallocating. On Windows it is
 249         // impossible to partially release a region of memory
 250         // allocated by VirtualAlloc. To avoid wasting virtual address
 251         // space we attempt to release a large region of memory
 252         // returned as a whole and then allocate an aligned region
 253         // inside this larger region.
 254         size_t allocationSize = size + blinkPageSize;
 255         for (int attempt = 0; attempt < 3; attempt++) {
 256             base = static_cast<Address>(VirtualAlloc(0, allocationSize, MEM_RESERVE, PAGE_NOACCESS));
 257             RELEASE_ASSERT(base);
 258             VirtualFree(base, 0, MEM_RELEASE);
 259
 260             Address alignedBase = roundToBlinkPageBoundary(base);
 261             base = static_cast<Address>(VirtualAlloc(alignedBase, size, MEM_RESERVE, PAGE_NOACCESS));
 262             if (base) {
 263                 ASSERT(base == alignedBase);
 264                 return new PageMemoryRegion(alignedBase, size, numPages);
 265             }
 266         }
 267
 268         // We failed to avoid wasting virtual address space after
 269         // several attempts.
 270         base = static_cast<Address>(VirtualAlloc(0, allocationSize, MEM_RESERVE, PAGE_NOACCESS));
 271         RELEASE_ASSERT(base);
 272
 273         // FIXME: If base is by accident blink page size aligned
 274         // here then we can create two pages out of reserved
 275         // space. Do this.
 276         Address alignedBase = roundToBlinkPageBoundary(base);
 277
 278         return new PageMemoryRegion(alignedBase, size, numPages);
 279 #endif
 280     }
 281
 282 private:
 283     PageMemoryRegion(Address base, size_t size, unsigned numPages)
 284         : MemoryRegion(base, size)
 285         , m_numPages(numPages)
 286     {
 287     }
 288
 289     unsigned m_numPages;
 290 };
 291
 292 // Representation of the memory used for a Blink heap page.
 293 //
 294 // The representation keeps track of two memory regions:
 295 //
 296 // 1. The virtual memory reserved from the system in order to be able
 297 //    to free all the virtual memory reserved. Multiple PageMemory
 298 //    instances can share the same reserved memory region and
 299 //    therefore notify the reserved memory region on destruction so
 300 //    that the system memory can be given back when all PageMemory
 301 //    instances for that memory are gone.
 302 //
 303 // 2. The writable memory (a sub-region of the reserved virtual
 304 //    memory region) that is used for the actual heap page payload.
 305 //
 306 // Guard pages are created before and after the writable memory.
 307 class PageMemory {
 308 public:
 309     ~PageMemory()
 310     {
 311         __lsan_unregister_root_region(m_writable.base(), m_writable.size());
 312         m_reserved->pageRemoved();
 313     }
 314
 315     bool commit() WARN_UNUSED_RETURN { return m_writable.commit(); }
 316     void decommit() { m_writable.decommit(); }
 317
 318     Address writableStart() { return m_writable.base(); }
 319
 320     static PageMemory* setupPageMemoryInRegion(PageMemoryRegion* region, size_t pageOffset, size_t payloadSize)
 321     {
 322         // Setup the payload one OS page into the page memory. The
 323         // first os page is the guard page.
 324         Address payloadAddress = region->base() + pageOffset + osPageSize();
 325         return new PageMemory(region, MemoryRegion(payloadAddress, payloadSize));
 326     }
 327
 328     // Allocate a virtual address space for one blink page with the
 329     // following layout:
 330     //
 331     //    [ guard os page | ... payload ... | guard os page ]
 332     //    ^---{ aligned to blink page size }
 333     //
 334     static PageMemory* allocate(size_t payloadSize)
 335     {
 336         ASSERT(payloadSize > 0);
 337
 338         // Virtual memory allocation routines operate in OS page sizes.
 339         // Round up the requested size to nearest os page size.
 340         payloadSize = roundToOsPageSize(payloadSize);
 341
 342         // Overallocate by 2 times OS page size to have space for a
 343         // guard page at the beginning and end of blink heap page.
 344         size_t allocationSize = payloadSize + 2 * osPageSize();
 345         PageMemoryRegion* pageMemoryRegion = PageMemoryRegion::allocate(allocationSize, 1);
 346         PageMemory* storage = setupPageMemoryInRegion(pageMemoryRegion, 0, payloadSize);
 347         RELEASE_ASSERT(storage->commit());
 348         return storage;
 349     }
 350
 351 private:
 352     PageMemory(PageMemoryRegion* reserved, const MemoryRegion& writable)
 353         : m_reserved(reserved)
 354         , m_writable(writable)
 355     {
 356         ASSERT(reserved->contains(writable));
 357
 358         // Register the writable area of the memory as part of the LSan root set.
 359         // Only the writable area is mapped and can contain C++ objects. Those
 360         // C++ objects can contain pointers to objects outside of the heap and
 361         // should therefore be part of the LSan root set.
 362         __lsan_register_root_region(m_writable.base(), m_writable.size());
 363     }
 364
 365
 366     PageMemoryRegion* m_reserved;
 367     MemoryRegion m_writable;
 368 };
 369
 370 class GCScope {
 371 public:
 372     explicit GCScope(ThreadState::StackState stackState)
 373         : m_state(ThreadState::current())
 374         , m_safePointScope(stackState)
 375         , m_parkedAllThreads(false)
 376     {
 377         TRACE_EVENT0("blink_gc", "Heap::GCScope");
 378         const char* samplingState = TRACE_EVENT_GET_SAMPLING_STATE();
 379         if (m_state->isMainThread())
 380             TRACE_EVENT_SET_SAMPLING_STATE("blink_gc", "BlinkGCWaiting");
 381
 382         m_state->checkThread();
 383
 384         // FIXME: in an unlikely coincidence that two threads decide
 385         // to collect garbage at the same time, avoid doing two GCs in
 386         // a row.
 387         RELEASE_ASSERT(!m_state->isInGC());
 388         RELEASE_ASSERT(!m_state->isSweepInProgress());
 389         if (LIKELY(ThreadState::stopThreads())) {
 390             m_parkedAllThreads = true;
 391             m_state->enterGC();
 392         }
 393         if (m_state->isMainThread())
 394             TRACE_EVENT_SET_NONCONST_SAMPLING_STATE(samplingState);
 395     }
 396
 397     bool allThreadsParked() { return m_parkedAllThreads; }
 398
 399     ~GCScope()
 400     {
 401         // Only cleanup if we parked all threads in which case the GC happened
 402         // and we need to resume the other threads.
 403         if (LIKELY(m_parkedAllThreads)) {
 404             m_state->leaveGC();
 405             ASSERT(!m_state->isInGC());
 406             ThreadState::resumeThreads();
 407         }
 408     }
 409
 410 private:
 411     ThreadState* m_state;
 412     ThreadState::SafePointScope m_safePointScope;
 413     bool m_parkedAllThreads; // False if we fail to park all threads
 414 };
 415
 416 NO_SANITIZE_ADDRESS
 417 bool HeapObjectHeader::isMarked() const
 418 {
 419     checkHeader();
 420     unsigned size = asanUnsafeAcquireLoad(&m_size);
 421     return size & markBitMask;
 422 }
 423
 424 NO_SANITIZE_ADDRESS
 425 void HeapObjectHeader::unmark()
 426 {
 427     checkHeader();
 428     m_size &= ~markBitMask;
 429 }
 430
 431 NO_SANITIZE_ADDRESS
 432 bool HeapObjectHeader::hasDeadMark() const
 433 {
 434     checkHeader();
 435     return m_size & deadBitMask;
 436 }
 437
 438 NO_SANITIZE_ADDRESS
 439 void HeapObjectHeader::clearDeadMark()
 440 {
 441     checkHeader();
 442     m_size &= ~deadBitMask;
 443 }
 444
 445 NO_SANITIZE_ADDRESS
 446 void HeapObjectHeader::setDeadMark()
 447 {
 448     ASSERT(!isMarked());
 449     checkHeader();
 450     m_size |= deadBitMask;
 451 }
 452
 453 #if ENABLE(ASSERT)
 454 NO_SANITIZE_ADDRESS
 455 void HeapObjectHeader::zapMagic()
 456 {
 457     m_magic = zappedMagic;
 458 }
 459 #endif
 460
 461 HeapObjectHeader* HeapObjectHeader::fromPayload(const void* payload)
 462 {
 463     Address addr = reinterpret_cast<Address>(const_cast<void*>(payload));
 464     HeapObjectHeader* header =
 465         reinterpret_cast<HeapObjectHeader*>(addr - objectHeaderSize);
 466     return header;
 467 }
 468
 469 void HeapObjectHeader::finalize(const GCInfo* gcInfo, Address object, size_t objectSize)
 470 {
 471     ASSERT(gcInfo);
 472     if (gcInfo->hasFinalizer()) {
 473         gcInfo->m_finalize(object);
 474     }
 475
 476 #if ENABLE(ASSERT) || defined(LEAK_SANITIZER) || defined(ADDRESS_SANITIZER)
 477     // In Debug builds, memory is zapped when it's freed, and the zapped memory is
 478     // zeroed out when the memory is reused. Memory is also zapped when using Leak
 479     // Sanitizer because the heap is used as a root region for LSan and therefore
 480     // pointers in unreachable memory could hide leaks.
 481     for (size_t i = 0; i < objectSize; i++)
 482         object[i] = finalizedZapValue;
 483
 484     // Zap the primary vTable entry (secondary vTable entries are not zapped).
 485     if (gcInfo->hasVTable()) {
 486         *(reinterpret_cast<uintptr_t*>(object)) = zappedVTable;
 487     }
 488 #endif
 489     // In Release builds, the entire object is zeroed out when it is added to the free list.
 490     // This happens right after sweeping the page and before the thread commences execution.
 491 }
 492
 493 NO_SANITIZE_ADDRESS
 494 void FinalizedHeapObjectHeader::finalize()
 495 {
 496     HeapObjectHeader::finalize(m_gcInfo, payload(), payloadSize());
 497 }
 498
 499 template<typename Header>
 500 void LargeHeapObject<Header>::unmark()
 501 {
 502     return heapObjectHeader()->unmark();
 503 }
 504
 505 template<typename Header>
 506 bool LargeHeapObject<Header>::isMarked()
 507 {
 508     return heapObjectHeader()->isMarked();
 509 }
 510
 511 template<typename Header>
 512 void LargeHeapObject<Header>::setDeadMark()
 513 {
 514     heapObjectHeader()->setDeadMark();
 515 }
 516
 517 template<typename Header>
 518 void LargeHeapObject<Header>::checkAndMarkPointer(Visitor* visitor, Address address)
 519 {
 520     ASSERT(contains(address));
 521     if (!objectContains(address) || heapObjectHeader()->hasDeadMark())
 522         return;
 523 #if ENABLE(GC_PROFILE_MARKING)
 524     visitor->setHostInfo(&address, "stack");
 525 #endif
 526     mark(visitor);
 527 }
 528
 529 #if ENABLE(ASSERT)
 530 static bool isUninitializedMemory(void* objectPointer, size_t objectSize)
 531 {
 532     // Scan through the object's fields and check that they are all zero.
 533     Address* objectFields = reinterpret_cast<Address*>(objectPointer);
 534     for (size_t i = 0; i < objectSize / sizeof(Address); ++i) {
 535         if (objectFields[i] != 0)
 536             return false;
 537     }
 538     return true;
 539 }
 540 #endif
 541
 542 template<>
 543 void LargeHeapObject<FinalizedHeapObjectHeader>::mark(Visitor* visitor)
 544 {
 545     if (heapObjectHeader()->hasVTable() && !vTableInitialized(payload())) {
 546         FinalizedHeapObjectHeader* header = heapObjectHeader();
 547         visitor->markNoTracing(header);
 548         ASSERT(isUninitializedMemory(header->payload(), header->payloadSize()));
 549     } else {
 550         visitor->mark(heapObjectHeader(), heapObjectHeader()->traceCallback());
 551     }
 552 }
 553
 554 template<>
 555 void LargeHeapObject<HeapObjectHeader>::mark(Visitor* visitor)
 556 {
 557     ASSERT(gcInfo());
 558     if (gcInfo()->hasVTable() && !vTableInitialized(payload())) {
 559         HeapObjectHeader* header = heapObjectHeader();
 560         visitor->markNoTracing(header);
 561         ASSERT(isUninitializedMemory(header->payload(), header->payloadSize()));
 562     } else {
 563         visitor->mark(heapObjectHeader(), gcInfo()->m_trace);
 564     }
 565 }
 566
 567 template<>
 568 void LargeHeapObject<FinalizedHeapObjectHeader>::finalize()
 569 {
 570     heapObjectHeader()->finalize();
 571 }
 572
 573 template<>
 574 void LargeHeapObject<HeapObjectHeader>::finalize()
 575 {
 576     ASSERT(gcInfo());
 577     HeapObjectHeader::finalize(gcInfo(), payload(), payloadSize());
 578 }
 579
 580 FinalizedHeapObjectHeader* FinalizedHeapObjectHeader::fromPayload(const void* payload)
 581 {
 582     Address addr = reinterpret_cast<Address>(const_cast<void*>(payload));
 583     FinalizedHeapObjectHeader* header =
 584         reinterpret_cast<FinalizedHeapObjectHeader*>(addr - finalizedHeaderSize);
 585     return header;
 586 }
 587
 588 template<typename Header>
 589 ThreadHeap<Header>::ThreadHeap(ThreadState* state, int index)
 590     : m_currentAllocationPoint(0)
 591     , m_remainingAllocationSize(0)
 592     , m_firstPage(0)
 593     , m_firstLargeHeapObject(0)
 594     , m_firstPageAllocatedDuringSweeping(0)
 595     , m_lastPageAllocatedDuringSweeping(0)
 596     , m_mergePoint(0)
 597     , m_biggestFreeListIndex(0)
 598     , m_threadState(state)
 599     , m_index(index)
 600     , m_numberOfNormalPages(0)
 601     , m_promptlyFreedCount(0)
 602 {
 603     clearFreeLists();
 604 }
 605
 606 template<typename Header>
 607 ThreadHeap<Header>::~ThreadHeap()
 608 {
 609     ASSERT(!m_firstPage);
 610     ASSERT(!m_firstLargeHeapObject);
 611 }
 612
 613 template<typename Header>
 614 void ThreadHeap<Header>::cleanupPages()
 615 {
 616     clearFreeLists();
 617     flushHeapContainsCache();
 618
 619     // Add the ThreadHeap's pages to the orphanedPagePool.
 620     for (HeapPage<Header>* page = m_firstPage; page; page = page->m_next)
 621         Heap::orphanedPagePool()->addOrphanedPage(m_index, page);
 622     m_firstPage = 0;
 623
 624     for (LargeHeapObject<Header>* largeObject = m_firstLargeHeapObject; largeObject; largeObject = largeObject->m_next)
 625         Heap::orphanedPagePool()->addOrphanedPage(m_index, largeObject);
 626     m_firstLargeHeapObject = 0;
 627 }
 628
 629 template<typename Header>
 630 Address ThreadHeap<Header>::outOfLineAllocate(size_t size, const GCInfo* gcInfo)
 631 {
 632     size_t allocationSize = allocationSizeFromSize(size);
 633     if (threadState()->shouldGC()) {
 634         if (threadState()->shouldForceConservativeGC())
 635             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
 636         else
 637             threadState()->setGCRequested();
 638     }
 639     ensureCurrentAllocation(allocationSize, gcInfo);
 640     return allocate(size, gcInfo);
 641 }
 642
 643 template<typename Header>
 644 bool ThreadHeap<Header>::allocateFromFreeList(size_t minSize)
 645 {
 646     size_t bucketSize = 1 << m_biggestFreeListIndex;
 647     int i = m_biggestFreeListIndex;
 648     for (; i > 0; i--, bucketSize >>= 1) {
 649         if (bucketSize < minSize)
 650             break;
 651         FreeListEntry* entry = m_freeLists[i];
 652         if (entry) {
 653             m_biggestFreeListIndex = i;
 654             entry->unlink(&m_freeLists[i]);
 655             setAllocationPoint(entry->address(), entry->size());
 656             ASSERT(currentAllocationPoint() && remainingAllocationSize() >= minSize);
 657             return true;
 658         }
 659     }
 660     m_biggestFreeListIndex = i;
 661     return false;
 662 }
 663
 664 template<typename Header>
 665 void ThreadHeap<Header>::ensureCurrentAllocation(size_t minSize, const GCInfo* gcInfo)
 666 {
 667     ASSERT(minSize >= allocationGranularity);
 668     if (remainingAllocationSize() >= minSize)
 669         return;
 670
 671     if (remainingAllocationSize() > 0) {
 672         addToFreeList(currentAllocationPoint(), remainingAllocationSize());
 673         setAllocationPoint(0, 0);
 674     }
 675     if (allocateFromFreeList(minSize))
 676         return;
 677     if (coalesce(minSize) && allocateFromFreeList(minSize))
 678         return;
 679     addPageToHeap(gcInfo);
 680     bool success = allocateFromFreeList(minSize);
 681     RELEASE_ASSERT(success);
 682 }
 683
 684 template<typename Header>
 685 BaseHeapPage* ThreadHeap<Header>::heapPageFromAddress(Address address)
 686 {
 687     for (HeapPage<Header>* page = m_firstPage; page; page = page->next()) {
 688         if (page->contains(address))
 689             return page;
 690     }
 691     for (HeapPage<Header>* page = m_firstPageAllocatedDuringSweeping; page; page = page->next()) {
 692         if (page->contains(address))
 693             return page;
 694     }
 695     for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current; current = current->next()) {
 696         // Check that large pages are blinkPageSize aligned (modulo the
 697         // osPageSize for the guard page).
 698         ASSERT(reinterpret_cast<Address>(current) - osPageSize() == roundToBlinkPageStart(reinterpret_cast<Address>(current)));
 699         if (current->contains(address))
 700             return current;
 701     }
 702     return 0;
 703 }
 704
 705 #if ENABLE(GC_PROFILE_MARKING)
 706 template<typename Header>
 707 const GCInfo* ThreadHeap<Header>::findGCInfoOfLargeHeapObject(Address address)
 708 {
 709     for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current; current = current->next()) {
 710         if (current->contains(address))
 711             return current->gcInfo();
 712     }
 713     return 0;
 714 }
 715 #endif
 716
 717 #if ENABLE(GC_PROFILE_HEAP)
 718 #define GC_PROFILE_HEAP_PAGE_SNAPSHOT_THRESHOLD 0
 719 template<typename Header>
 720 void ThreadHeap<Header>::snapshot(TracedValue* json, ThreadState::SnapshotInfo* info)
 721 {
 722     size_t previousPageCount = info->pageCount;
 723
 724     json->beginArray("pages");
 725     for (HeapPage<Header>* page = m_firstPage; page; page = page->next(), ++info->pageCount) {
 726         // FIXME: To limit the size of the snapshot we only output "threshold" many page snapshots.
 727         if (info->pageCount < GC_PROFILE_HEAP_PAGE_SNAPSHOT_THRESHOLD) {
 728             json->beginArray();
 729             json->pushInteger(reinterpret_cast<intptr_t>(page));
 730             page->snapshot(json, info);
 731             json->endArray();
 732         } else {
 733             page->snapshot(0, info);
 734         }
 735     }
 736     json->endArray();
 737
 738     json->beginArray("largeObjects");
 739     for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current; current = current->next()) {
 740         json->beginDictionary();
 741         current->snapshot(json, info);
 742         json->endDictionary();
 743     }
 744     json->endArray();
 745
 746     json->setInteger("pageCount", info->pageCount - previousPageCount);
 747 }
 748 #endif
 749
 750 template<typename Header>
 751 void ThreadHeap<Header>::addToFreeList(Address address, size_t size)
 752 {
 753     ASSERT(heapPageFromAddress(address));
 754     ASSERT(heapPageFromAddress(address + size - 1));
 755     ASSERT(size < blinkPagePayloadSize());
 756     // The free list entries are only pointer aligned (but when we allocate
 757     // from them we are 8 byte aligned due to the header size).
 758     ASSERT(!((reinterpret_cast<uintptr_t>(address) + sizeof(Header)) & allocationMask));
 759     ASSERT(!(size & allocationMask));
 760     ASAN_POISON_MEMORY_REGION(address, size);
 761     FreeListEntry* entry;
 762     if (size < sizeof(*entry)) {
 763         // Create a dummy header with only a size and freelist bit set.
 764         ASSERT(size >= sizeof(BasicObjectHeader));
 765         // Free list encode the size to mark the lost memory as freelist memory.
 766         new (NotNull, address) BasicObjectHeader(BasicObjectHeader::freeListEncodedSize(size));
 767         // This memory gets lost. Sweeping can reclaim it.
 768         return;
 769     }
 770     entry = new (NotNull, address) FreeListEntry(size);
 771 #if defined(ADDRESS_SANITIZER)
 772     // For ASan we don't add the entry to the free lists until the asanDeferMemoryReuseCount
 773     // reaches zero. However we always add entire pages to ensure that adding a new page will
 774     // increase the allocation space.
 775     if (HeapPage<Header>::payloadSize() != size && !entry->shouldAddToFreeList())
 776         return;
 777 #endif
 778     int index = bucketIndexForSize(size);
 779     entry->link(&m_freeLists[index]);
 780     if (!m_lastFreeListEntries[index])
 781         m_lastFreeListEntries[index] = entry;
 782     if (index > m_biggestFreeListIndex)
 783         m_biggestFreeListIndex = index;
 784 }
 785
 786 template<typename Header>
 787 void ThreadHeap<Header>::promptlyFreeObject(Header* header)
 788 {
 789     ASSERT(!m_threadState->isSweepInProgress());
 790     header->checkHeader();
 791     Address address = reinterpret_cast<Address>(header);
 792     Address payload = header->payload();
 793     size_t size = header->size();
 794     size_t payloadSize = header->payloadSize();
 795     BaseHeapPage* page = pageHeaderFromObject(address);
 796     ASSERT(size > 0);
 797     ASSERT(page == heapPageFromAddress(address));
 798
 799     {
 800         ThreadState::NoSweepScope scope(m_threadState);
 801         HeapObjectHeader::finalize(header->gcInfo(), payload, payloadSize);
 802 #if !ENABLE(ASSERT) && !defined(LEAK_SANITIZER) && !defined(ADDRESS_SANITIZER)
 803         memset(payload, 0, payloadSize);
 804 #endif
 805         header->markPromptlyFreed();
 806     }
 807
 808     page->addToPromptlyFreedSize(size);
 809     m_promptlyFreedCount++;
 810 }
 811
 812 template<typename Header>
 813 bool ThreadHeap<Header>::coalesce(size_t minSize)
 814 {
 815     if (m_threadState->isSweepInProgress())
 816         return false;
 817
 818     if (m_promptlyFreedCount < 256)
 819         return false;
 820
 821     // The smallest bucket able to satisfy an allocation request for minSize is
 822     // the bucket where all free-list entries are guarantied to be larger than
 823     // minSize. That bucket is one larger than the bucket minSize would go into.
 824     size_t neededBucketIndex = bucketIndexForSize(minSize) + 1;
 825     size_t neededFreeEntrySize = 1 << neededBucketIndex;
 826     size_t neededPromptlyFreedSize = neededFreeEntrySize * 3;
 827     size_t foundFreeEntrySize = 0;
 828
 829     // Bailout early on large requests because it is unlikely we will find a free-list entry.
 830     if (neededPromptlyFreedSize >= blinkPageSize)
 831         return false;
 832
 833     TRACE_EVENT_BEGIN2("blink_gc", "ThreadHeap::coalesce" , "requestedSize", (unsigned)minSize , "neededSize", (unsigned)neededFreeEntrySize);
 834
 835     // Search for a coalescing candidate.
 836     ASSERT(!ownsNonEmptyAllocationArea());
 837     size_t pageCount = 0;
 838     HeapPage<Header>* page = m_firstPage;
 839     while (page) {
 840         // Only consider one of the first 'n' pages. A "younger" page is more likely to have freed backings.
 841         if (++pageCount > numberOfPagesToConsiderForCoalescing) {
 842             page = 0;
 843             break;
 844         }
 845         // Only coalesce pages with "sufficient" promptly freed space.
 846         if (page->promptlyFreedSize() >= neededPromptlyFreedSize) {
 847             break;
 848         }
 849         page = page->next();
 850     }
 851
 852     // If we found a likely candidate, fully coalesce all its promptly-freed entries.
 853     if (page) {
 854         page->clearObjectStartBitMap();
 855         page->resetPromptlyFreedSize();
 856         size_t freedCount = 0;
 857         Address startOfGap = page->payload();
 858         for (Address headerAddress = startOfGap; headerAddress < page->end(); ) {
 859             BasicObjectHeader* basicHeader = reinterpret_cast<BasicObjectHeader*>(headerAddress);
 860             ASSERT(basicHeader->size() > 0);
 861             ASSERT(basicHeader->size() < blinkPagePayloadSize());
 862
 863             if (basicHeader->isPromptlyFreed()) {
 864                 stats().decreaseObjectSpace(reinterpret_cast<Header*>(basicHeader)->payloadSize());
 865                 size_t size = basicHeader->size();
 866                 ASSERT(size >= sizeof(Header));
 867 #if !ENABLE(ASSERT) && !defined(LEAK_SANITIZER) && !defined(ADDRESS_SANITIZER)
 868                 memset(headerAddress, 0, sizeof(Header));
 869 #endif
 870                 ++freedCount;
 871                 headerAddress += size;
 872                 continue;
 873             }
 874
 875             if (startOfGap != headerAddress) {
 876                 size_t size = headerAddress - startOfGap;
 877                 addToFreeList(startOfGap, size);
 878                 if (size > foundFreeEntrySize)
 879                     foundFreeEntrySize = size;
 880             }
 881
 882             headerAddress += basicHeader->size();
 883             startOfGap = headerAddress;
 884         }
 885
 886         if (startOfGap != page->end()) {
 887             size_t size = page->end() - startOfGap;
 888             addToFreeList(startOfGap, size);
 889             if (size > foundFreeEntrySize)
 890                 foundFreeEntrySize = size;
 891         }
 892
 893         // Check before subtracting because freedCount might not be balanced with freed entries.
 894         if (freedCount < m_promptlyFreedCount)
 895             m_promptlyFreedCount -= freedCount;
 896         else
 897             m_promptlyFreedCount = 0;
 898     }
 899
 900     TRACE_EVENT_END1("blink_gc", "ThreadHeap::coalesce", "foundFreeEntrySize", (unsigned)foundFreeEntrySize);
 901
 902     if (foundFreeEntrySize < neededFreeEntrySize) {
 903         // If coalescing failed, reset the freed count to delay coalescing again.
 904         m_promptlyFreedCount = 0;
 905         return false;
 906     }
 907
 908     return true;
 909 }
 910
 911 template<typename Header>
 912 Address ThreadHeap<Header>::allocateLargeObject(size_t size, const GCInfo* gcInfo)
 913 {
 914     // Caller already added space for object header and rounded up to allocation alignment
 915     ASSERT(!(size & allocationMask));
 916
 917     size_t allocationSize = sizeof(LargeHeapObject<Header>) + size;
 918
 919     // Ensure that there is enough space for alignment. If the header
 920     // is not a multiple of 8 bytes we will allocate an extra
 921     // headerPadding<Header> bytes to ensure it 8 byte aligned.
 922     allocationSize += headerPadding<Header>();
 923
 924     // If ASan is supported we add allocationGranularity bytes to the allocated space and
 925     // poison that to detect overflows
 926 #if defined(ADDRESS_SANITIZER)
 927     allocationSize += allocationGranularity;
 928 #endif
 929     if (threadState()->shouldGC())
 930         threadState()->setGCRequested();
 931     Heap::flushHeapDoesNotContainCache();
 932     PageMemory* pageMemory = PageMemory::allocate(allocationSize);
 933     Address largeObjectAddress = pageMemory->writableStart();
 934     Address headerAddress = largeObjectAddress + sizeof(LargeHeapObject<Header>) + headerPadding<Header>();
 935     memset(headerAddress, 0, size);
 936     Header* header = new (NotNull, headerAddress) Header(size, gcInfo);
 937     Address result = headerAddress + sizeof(*header);
 938     ASSERT(!(reinterpret_cast<uintptr_t>(result) & allocationMask));
 939     LargeHeapObject<Header>* largeObject = new (largeObjectAddress) LargeHeapObject<Header>(pageMemory, gcInfo, threadState());
 940
 941     // Poison the object header and allocationGranularity bytes after the object
 942     ASAN_POISON_MEMORY_REGION(header, sizeof(*header));
 943     ASAN_POISON_MEMORY_REGION(largeObject->address() + largeObject->size(), allocationGranularity);
 944     largeObject->link(&m_firstLargeHeapObject);
 945     stats().increaseAllocatedSpace(largeObject->size());
 946     stats().increaseObjectSpace(largeObject->payloadSize());
 947     return result;
 948 }
 949
 950 template<typename Header>
 951 void ThreadHeap<Header>::freeLargeObject(LargeHeapObject<Header>* object, LargeHeapObject<Header>** previousNext)
 952 {
 953     flushHeapContainsCache();
 954     object->unlink(previousNext);
 955     object->finalize();
 956
 957     // Unpoison the object header and allocationGranularity bytes after the
 958     // object before freeing.
 959     ASAN_UNPOISON_MEMORY_REGION(object->heapObjectHeader(), sizeof(Header));
 960     ASAN_UNPOISON_MEMORY_REGION(object->address() + object->size(), allocationGranularity);
 961
 962     if (object->terminating()) {
 963         ASSERT(ThreadState::current()->isTerminating());
 964         // The thread is shutting down so this object is being removed as part
 965         // of a thread local GC. In that case the object could be traced in the
 966         // next global GC either due to a dead object being traced via a
 967         // conservative pointer or due to a programming error where an object
 968         // in another thread heap keeps a dangling pointer to this object.
 969         // To guard against this we put the large object memory in the
 970         // orphanedPagePool to ensure it is still reachable. After the next global
 971         // GC it can be released assuming no rogue/dangling pointers refer to
 972         // it.
 973         // NOTE: large objects are not moved to the free page pool as it is
 974         // unlikely they can be reused due to their individual sizes.
 975         Heap::orphanedPagePool()->addOrphanedPage(m_index, object);
 976     } else {
 977         ASSERT(!ThreadState::current()->isTerminating());
 978         PageMemory* memory = object->storage();
 979         object->~LargeHeapObject<Header>();
 980         delete memory;
 981     }
 982 }
 983
 984 template<typename DataType>
 985 PagePool<DataType>::PagePool()
 986 {
 987     for (int i = 0; i < NumberOfHeaps; ++i) {
 988         m_pool[i] = 0;
 989     }
 990 }
 991
 992 FreePagePool::~FreePagePool()
 993 {
 994     for (int index = 0; index < NumberOfHeaps; ++index) {
 995         while (PoolEntry* entry = m_pool[index]) {
 996             m_pool[index] = entry->next;
 997             PageMemory* memory = entry->data;
 998             ASSERT(memory);
 999             delete memory;
1000             delete entry;
1001         }
1002     }
1003 }
1004
1005 void FreePagePool::addFreePage(int index, PageMemory* memory)
1006 {
1007     // When adding a page to the pool we decommit it to ensure it is unused
1008     // while in the pool. This also allows the physical memory, backing the
1009     // page, to be given back to the OS.
1010     memory->decommit();
1011     MutexLocker locker(m_mutex[index]);
1012     PoolEntry* entry = new PoolEntry(memory, m_pool[index]);
1013     m_pool[index] = entry;
1014 }
1015
1016 PageMemory* FreePagePool::takeFreePage(int index)
1017 {
1018     MutexLocker locker(m_mutex[index]);
1019     while (PoolEntry* entry = m_pool[index]) {
1020         m_pool[index] = entry->next;
1021         PageMemory* memory = entry->data;
1022         ASSERT(memory);
1023         delete entry;
1024         if (memory->commit())
1025             return memory;
1026
1027         // We got some memory, but failed to commit it, try again.
1028         delete memory;
1029     }
1030     return 0;
1031 }
1032
1033 OrphanedPagePool::~OrphanedPagePool()
1034 {
1035     for (int index = 0; index < NumberOfHeaps; ++index) {
1036         while (PoolEntry* entry = m_pool[index]) {
1037             m_pool[index] = entry->next;
1038             BaseHeapPage* page = entry->data;
1039             delete entry;
1040             PageMemory* memory = page->storage();
1041             ASSERT(memory);
1042             page->~BaseHeapPage();
1043             delete memory;
1044         }
1045     }
1046 }
1047
1048 void OrphanedPagePool::addOrphanedPage(int index, BaseHeapPage* page)
1049 {
1050     page->markOrphaned();
1051     PoolEntry* entry = new PoolEntry(page, m_pool[index]);
1052     m_pool[index] = entry;
1053 }
1054
1055 NO_SANITIZE_ADDRESS
1056 void OrphanedPagePool::decommitOrphanedPages()
1057 {
1058 #if ENABLE(ASSERT)
1059     // No locking needed as all threads are at safepoints at this point in time.
1060     ThreadState::AttachedThreadStateSet& threads = ThreadState::attachedThreads();
1061     for (ThreadState::AttachedThreadStateSet::iterator it = threads.begin(), end = threads.end(); it != end; ++it)
1062         ASSERT((*it)->isAtSafePoint());
1063 #endif
1064
1065     for (int index = 0; index < NumberOfHeaps; ++index) {
1066         PoolEntry* entry = m_pool[index];
1067         PoolEntry** prevNext = &m_pool[index];
1068         while (entry) {
1069             BaseHeapPage* page = entry->data;
1070             if (page->tracedAfterOrphaned()) {
1071                 // If the orphaned page was traced in the last GC it is not
1072                 // decommited. We only decommit a page, ie. put it in the
1073                 // memory pool, when the page has no objects pointing to it.
1074                 // We remark the page as orphaned to clear the tracedAfterOrphaned
1075                 // flag and any object trace bits that were set during tracing.
1076                 page->markOrphaned();
1077                 prevNext = &entry->next;
1078                 entry = entry->next;
1079                 continue;
1080             }
1081
1082             // Page was not traced. Check if we should reuse the memory or just
1083             // free it. Large object memory is not reused, but freed, normal
1084             // blink heap pages are reused.
1085             // NOTE: We call the destructor before freeing or adding to the
1086             // free page pool.
1087             PageMemory* memory = page->storage();
1088             if (page->isLargeObject()) {
1089                 page->~BaseHeapPage();
1090                 delete memory;
1091             } else {
1092                 page->~BaseHeapPage();
1093                 // Clear out the page's memory before adding it to the free page
1094                 // pool to ensure it is zero filled when being reused.
1095                 clearMemory(memory);
1096                 Heap::freePagePool()->addFreePage(index, memory);
1097             }
1098
1099             PoolEntry* deadEntry = entry;
1100             entry = entry->next;
1101             *prevNext = entry;
1102             delete deadEntry;
1103         }
1104     }
1105 }
1106
1107 NO_SANITIZE_ADDRESS
1108 void OrphanedPagePool::clearMemory(PageMemory* memory)
1109 {
1110 #if defined(ADDRESS_SANITIZER)
1111     // Don't use memset when running with ASan since this needs to zap
1112     // poisoned memory as well and the NO_SANITIZE_ADDRESS annotation
1113     // only works for code in this method and not for calls to memset.
1114     Address base = memory->writableStart();
1115     for (Address current = base; current < base + blinkPagePayloadSize(); ++current)
1116         *current = 0;
1117 #else
1118     memset(memory->writableStart(), 0, blinkPagePayloadSize());
1119 #endif
1120 }
1121
1122 #if ENABLE(ASSERT)
1123 bool OrphanedPagePool::contains(void* object)
1124 {
1125     for (int index = 0; index < NumberOfHeaps; ++index) {
1126         for (PoolEntry* entry = m_pool[index]; entry; entry = entry->next) {
1127             BaseHeapPage* page = entry->data;
1128             if (page->contains(reinterpret_cast<Address>(object)))
1129                 return true;
1130         }
1131     }
1132     return false;
1133 }
1134 #endif
1135
1136 template<>
1137 void ThreadHeap<FinalizedHeapObjectHeader>::addPageToHeap(const GCInfo* gcInfo)
1138 {
1139     // When adding a page to the ThreadHeap using FinalizedHeapObjectHeaders the GCInfo on
1140     // the heap should be unused (ie. 0).
1141     allocatePage(0);
1142 }
1143
1144 template<>
1145 void ThreadHeap<HeapObjectHeader>::addPageToHeap(const GCInfo* gcInfo)
1146 {
1147     // When adding a page to the ThreadHeap using HeapObjectHeaders store the GCInfo on the heap
1148     // since it is the same for all objects
1149     ASSERT(gcInfo);
1150     allocatePage(gcInfo);
1151 }
1152
1153 template <typename Header>
1154 void ThreadHeap<Header>::removePageFromHeap(HeapPage<Header>* page)
1155 {
1156     MutexLocker locker(m_threadState->sweepMutex());
1157     flushHeapContainsCache();
1158     if (page->terminating()) {
1159         // The thread is shutting down so this page is being removed as part
1160         // of a thread local GC. In that case the page could be accessed in the
1161         // next global GC either due to a dead object being traced via a
1162         // conservative pointer or due to a programming error where an object
1163         // in another thread heap keeps a dangling pointer to this object.
1164         // To guard against this we put the page in the orphanedPagePool to
1165         // ensure it is still reachable. After the next global GC it can be
1166         // decommitted and moved to the page pool assuming no rogue/dangling
1167         // pointers refer to it.
1168         Heap::orphanedPagePool()->addOrphanedPage(m_index, page);
1169     } else {
1170         PageMemory* memory = page->storage();
1171         page->~HeapPage<Header>();
1172         Heap::freePagePool()->addFreePage(m_index, memory);
1173     }
1174 }
1175
1176 template<typename Header>
1177 void ThreadHeap<Header>::allocatePage(const GCInfo* gcInfo)
1178 {
1179     Heap::flushHeapDoesNotContainCache();
1180     PageMemory* pageMemory = Heap::freePagePool()->takeFreePage(m_index);
1181     // We continue allocating page memory until we succeed in getting one.
1182     // Since the FreePagePool is global other threads could use all the
1183     // newly allocated page memory before this thread calls takeFreePage.
1184     while (!pageMemory) {
1185         // Allocate a memory region for blinkPagesPerRegion pages that
1186         // will each have the following layout.
1187         //
1188         //    [ guard os page | ... payload ... | guard os page ]
1189         //    ^---{ aligned to blink page size }
1190         PageMemoryRegion* region = PageMemoryRegion::allocate(blinkPageSize * blinkPagesPerRegion, blinkPagesPerRegion);
1191         // Setup the PageMemory object for each of the pages in the
1192         // region.
1193         size_t offset = 0;
1194         for (size_t i = 0; i < blinkPagesPerRegion; i++) {
1195             Heap::freePagePool()->addFreePage(m_index, PageMemory::setupPageMemoryInRegion(region, offset, blinkPagePayloadSize()));
1196             offset += blinkPageSize;
1197         }
1198         pageMemory = Heap::freePagePool()->takeFreePage(m_index);
1199     }
1200     HeapPage<Header>* page = new (pageMemory->writableStart()) HeapPage<Header>(pageMemory, this, gcInfo);
1201     // Use a separate list for pages allocated during sweeping to make
1202     // sure that we do not accidentally sweep objects that have been
1203     // allocated during sweeping.
1204     if (m_threadState->isSweepInProgress()) {
1205         if (!m_lastPageAllocatedDuringSweeping)
1206             m_lastPageAllocatedDuringSweeping = page;
1207         page->link(&m_firstPageAllocatedDuringSweeping);
1208     } else {
1209         page->link(&m_firstPage);
1210     }
1211     ++m_numberOfNormalPages;
1212     addToFreeList(page->payload(), HeapPage<Header>::payloadSize());
1213 }
1214
1215 #if ENABLE(ASSERT)
1216 template<typename Header>
1217 bool ThreadHeap<Header>::pagesToBeSweptContains(Address address)
1218 {
1219     for (HeapPage<Header>* page = m_firstPage; page; page = page->next()) {
1220         if (page->contains(address))
1221             return true;
1222     }
1223     return false;
1224 }
1225
1226 template<typename Header>
1227 bool ThreadHeap<Header>::pagesAllocatedDuringSweepingContains(Address address)
1228 {
1229     for (HeapPage<Header>* page = m_firstPageAllocatedDuringSweeping; page; page = page->next()) {
1230         if (page->contains(address))
1231             return true;
1232     }
1233     return false;
1234 }
1235
1236 template<typename Header>
1237 void ThreadHeap<Header>::getScannedStats(HeapStats& scannedStats)
1238 {
1239     ASSERT(!m_firstPageAllocatedDuringSweeping);
1240     for (HeapPage<Header>* page = m_firstPage; page; page = page->next())
1241         page->getStats(scannedStats);
1242     for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current; current = current->next())
1243         current->getStats(scannedStats);
1244 }
1245 #endif
1246
1247 template<typename Header>
1248 void ThreadHeap<Header>::sweepNormalPages(HeapStats* stats)
1249 {
1250     TRACE_EVENT0("blink_gc", "ThreadHeap::sweepNormalPages");
1251     HeapPage<Header>* page = m_firstPage;
1252     HeapPage<Header>** previousNext = &m_firstPage;
1253     HeapPage<Header>* previous = 0;
1254     while (page) {
1255         page->resetPromptlyFreedSize();
1256         if (page->isEmpty()) {
1257             HeapPage<Header>* unused = page;
1258             if (unused == m_mergePoint)
1259                 m_mergePoint = previous;
1260             page = page->next();
1261             HeapPage<Header>::unlink(this, unused, previousNext);
1262             --m_numberOfNormalPages;
1263         } else {
1264             page->sweep(stats, this);
1265             previousNext = &page->m_next;
1266             previous = page;
1267             page = page->next();
1268         }
1269     }
1270 }
1271
1272 template<typename Header>
1273 void ThreadHeap<Header>::sweepLargePages(HeapStats* stats)
1274 {
1275     TRACE_EVENT0("blink_gc", "ThreadHeap::sweepLargePages");
1276     LargeHeapObject<Header>** previousNext = &m_firstLargeHeapObject;
1277     for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current;) {
1278         if (current->isMarked()) {
1279             stats->increaseAllocatedSpace(current->size());
1280             stats->increaseObjectSpace(current->payloadSize());
1281             current->unmark();
1282             previousNext = &current->m_next;
1283             current = current->next();
1284         } else {
1285             LargeHeapObject<Header>* next = current->next();
1286             freeLargeObject(current, previousNext);
1287             current = next;
1288         }
1289     }
1290 }
1291
1292
1293 // STRICT_ASAN_FINALIZATION_CHECKING turns on poisoning of all objects during
1294 // sweeping to catch cases where dead objects touch each other. This is not
1295 // turned on by default because it also triggers for cases that are safe.
1296 // Examples of such safe cases are context life cycle observers and timers
1297 // embedded in garbage collected objects.
1298 #define STRICT_ASAN_FINALIZATION_CHECKING 0
1299
1300 template<typename Header>
1301 void ThreadHeap<Header>::sweep(HeapStats* stats)
1302 {
1303     ASSERT(isConsistentForSweeping());
1304 #if defined(ADDRESS_SANITIZER) && STRICT_ASAN_FINALIZATION_CHECKING
1305     // When using ASan do a pre-sweep where all unmarked objects are
1306     // poisoned before calling their finalizer methods. This can catch
1307     // the case where the finalizer of an object tries to modify
1308     // another object as part of finalization.
1309     for (HeapPage<Header>* page = m_firstPage; page; page = page->next())
1310         page->poisonUnmarkedObjects();
1311 #endif
1312     sweepNormalPages(stats);
1313     sweepLargePages(stats);
1314 }
1315
1316 template<typename Header>
1317 void ThreadHeap<Header>::postSweepProcessing()
1318 {
1319     // If pages have been allocated during sweeping, link them into
1320     // the list of pages.
1321     if (m_firstPageAllocatedDuringSweeping) {
1322         m_lastPageAllocatedDuringSweeping->m_next = m_firstPage;
1323         m_firstPage = m_firstPageAllocatedDuringSweeping;
1324         m_lastPageAllocatedDuringSweeping = 0;
1325         m_firstPageAllocatedDuringSweeping = 0;
1326     }
1327 }
1328
1329 #if ENABLE(ASSERT)
1330 template<typename Header>
1331 bool ThreadHeap<Header>::isConsistentForSweeping()
1332 {
1333     // A thread heap is consistent for sweeping if none of the pages to
1334     // be swept contain a freelist block or the current allocation
1335     // point.
1336     for (size_t i = 0; i < blinkPageSizeLog2; i++) {
1337         for (FreeListEntry* freeListEntry = m_freeLists[i]; freeListEntry; freeListEntry = freeListEntry->next()) {
1338             if (pagesToBeSweptContains(freeListEntry->address())) {
1339                 return false;
1340             }
1341             ASSERT(pagesAllocatedDuringSweepingContains(freeListEntry->address()));
1342         }
1343     }
1344     if (ownsNonEmptyAllocationArea()) {
1345         ASSERT(pagesToBeSweptContains(currentAllocationPoint())
1346             || pagesAllocatedDuringSweepingContains(currentAllocationPoint()));
1347         return !pagesToBeSweptContains(currentAllocationPoint());
1348     }
1349     return true;
1350 }
1351 #endif
1352
1353 template<typename Header>
1354 void ThreadHeap<Header>::makeConsistentForSweeping()
1355 {
1356     if (ownsNonEmptyAllocationArea())
1357         addToFreeList(currentAllocationPoint(), remainingAllocationSize());
1358     setAllocationPoint(0, 0);
1359     clearFreeLists();
1360 }
1361
1362 template<typename Header>
1363 void ThreadHeap<Header>::clearLiveAndMarkDead()
1364 {
1365     ASSERT(isConsistentForSweeping());
1366     for (HeapPage<Header>* page = m_firstPage; page; page = page->next())
1367         page->clearLiveAndMarkDead();
1368     for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current; current = current->next()) {
1369         if (current->isMarked())
1370             current->unmark();
1371         else
1372             current->setDeadMark();
1373     }
1374 }
1375
1376 template<typename Header>
1377 void ThreadHeap<Header>::clearFreeLists()
1378 {
1379     m_promptlyFreedCount = 0;
1380     for (size_t i = 0; i < blinkPageSizeLog2; i++) {
1381         m_freeLists[i] = 0;
1382         m_lastFreeListEntries[i] = 0;
1383     }
1384 }
1385
1386 int BaseHeap::bucketIndexForSize(size_t size)
1387 {
1388     ASSERT(size > 0);
1389     int index = -1;
1390     while (size) {
1391         size >>= 1;
1392         index++;
1393     }
1394     return index;
1395 }
1396
1397 template<typename Header>
1398 HeapPage<Header>::HeapPage(PageMemory* storage, ThreadHeap<Header>* heap, const GCInfo* gcInfo)
1399     : BaseHeapPage(storage, gcInfo, heap->threadState())
1400     , m_next(0)
1401 {
1402     COMPILE_ASSERT(!(sizeof(HeapPage<Header>) & allocationMask), page_header_incorrectly_aligned);
1403     m_objectStartBitMapComputed = false;
1404     ASSERT(isPageHeaderAddress(reinterpret_cast<Address>(this)));
1405     heap->stats().increaseAllocatedSpace(blinkPageSize);
1406 }
1407
1408 template<typename Header>
1409 void HeapPage<Header>::link(HeapPage** prevNext)
1410 {
1411     m_next = *prevNext;
1412     *prevNext = this;
1413 }
1414
1415 template<typename Header>
1416 void HeapPage<Header>::unlink(ThreadHeap<Header>* heap, HeapPage* unused, HeapPage** prevNext)
1417 {
1418     *prevNext = unused->m_next;
1419     heap->removePageFromHeap(unused);
1420 }
1421
1422 template<typename Header>
1423 void HeapPage<Header>::getStats(HeapStats& stats)
1424 {
1425     stats.increaseAllocatedSpace(blinkPageSize);
1426     Address headerAddress = payload();
1427     ASSERT(headerAddress != end());
1428     do {
1429         Header* header = reinterpret_cast<Header*>(headerAddress);
1430         if (!header->isFree())
1431             stats.increaseObjectSpace(header->payloadSize());
1432         ASSERT(header->size() < blinkPagePayloadSize());
1433         headerAddress += header->size();
1434         ASSERT(headerAddress <= end());
1435     } while (headerAddress < end());
1436 }
1437
1438 template<typename Header>
1439 bool HeapPage<Header>::isEmpty()
1440 {
1441     BasicObjectHeader* header = reinterpret_cast<BasicObjectHeader*>(payload());
1442     return header->isFree() && (header->size() == payloadSize());
1443 }
1444
1445 template<typename Header>
1446 void HeapPage<Header>::sweep(HeapStats* stats, ThreadHeap<Header>* heap)
1447 {
1448     clearObjectStartBitMap();
1449     stats->increaseAllocatedSpace(blinkPageSize);
1450     Address startOfGap = payload();
1451     for (Address headerAddress = startOfGap; headerAddress < end(); ) {
1452         BasicObjectHeader* basicHeader = reinterpret_cast<BasicObjectHeader*>(headerAddress);
1453         ASSERT(basicHeader->size() > 0);
1454         ASSERT(basicHeader->size() < blinkPagePayloadSize());
1455
1456         if (basicHeader->isFree()) {
1457             size_t size = basicHeader->size();
1458 #if !ENABLE(ASSERT) && !defined(LEAK_SANITIZER) && !defined(ADDRESS_SANITIZER)
1459             // Zero the memory in the free list header to maintain the
1460             // invariant that memory on the free list is zero filled.
1461             // The rest of the memory is already on the free list and is
1462             // therefore already zero filled.
1463             if (size < sizeof(FreeListEntry))
1464                 memset(headerAddress, 0, size);
1465             else
1466                 memset(headerAddress, 0, sizeof(FreeListEntry));
1467 #endif
1468             headerAddress += size;
1469             continue;
1470         }
1471         // At this point we know this is a valid object of type Header
1472         Header* header = static_cast<Header*>(basicHeader);
1473
1474         if (!header->isMarked()) {
1475             // For ASan we unpoison the specific object when calling the finalizer and
1476             // poison it again when done to allow the object's own finalizer to operate
1477             // on the object, but not have other finalizers be allowed to access it.
1478             ASAN_UNPOISON_MEMORY_REGION(header->payload(), header->payloadSize());
1479             finalize(header);
1480             size_t size = header->size();
1481 #if !ENABLE(ASSERT) && !defined(LEAK_SANITIZER) && !defined(ADDRESS_SANITIZER)
1482             // This memory will be added to the freelist. Maintain the invariant
1483             // that memory on the freelist is zero filled.
1484             memset(headerAddress, 0, size);
1485 #endif
1486             ASAN_POISON_MEMORY_REGION(header->payload(), header->payloadSize());
1487             headerAddress += size;
1488             continue;
1489         }
1490
1491         if (startOfGap != headerAddress)
1492             heap->addToFreeList(startOfGap, headerAddress - startOfGap);
1493         header->unmark();
1494         headerAddress += header->size();
1495         stats->increaseObjectSpace(header->payloadSize());
1496         startOfGap = headerAddress;
1497     }
1498     if (startOfGap != end())
1499         heap->addToFreeList(startOfGap, end() - startOfGap);
1500 }
1501
1502 template<typename Header>
1503 void HeapPage<Header>::clearLiveAndMarkDead()
1504 {
1505     for (Address headerAddress = payload(); headerAddress < end();) {
1506         Header* header = reinterpret_cast<Header*>(headerAddress);
1507         ASSERT(header->size() < blinkPagePayloadSize());
1508         // Check if a free list entry first since we cannot call
1509         // isMarked on a free list entry.
1510         if (header->isFree()) {
1511             headerAddress += header->size();
1512             continue;
1513         }
1514         if (header->isMarked())
1515             header->unmark();
1516         else
1517             header->setDeadMark();
1518         headerAddress += header->size();
1519     }
1520 }
1521
1522 template<typename Header>
1523 void HeapPage<Header>::populateObjectStartBitMap()
1524 {
1525     memset(&m_objectStartBitMap, 0, objectStartBitMapSize);
1526     Address start = payload();
1527     for (Address headerAddress = start; headerAddress < end();) {
1528         Header* header = reinterpret_cast<Header*>(headerAddress);
1529         size_t objectOffset = headerAddress - start;
1530         ASSERT(!(objectOffset & allocationMask));
1531         size_t objectStartNumber = objectOffset / allocationGranularity;
1532         size_t mapIndex = objectStartNumber / 8;
1533         ASSERT(mapIndex < objectStartBitMapSize);
1534         m_objectStartBitMap[mapIndex] |= (1 << (objectStartNumber & 7));
1535         headerAddress += header->size();
1536         ASSERT(headerAddress <= end());
1537     }
1538     m_objectStartBitMapComputed = true;
1539 }
1540
1541 template<typename Header>
1542 void HeapPage<Header>::clearObjectStartBitMap()
1543 {
1544     m_objectStartBitMapComputed = false;
1545 }
1546
1547 static int numberOfLeadingZeroes(uint8_t byte)
1548 {
1549     if (!byte)
1550         return 8;
1551     int result = 0;
1552     if (byte <= 0x0F) {
1553         result += 4;
1554         byte = byte << 4;
1555     }
1556     if (byte <= 0x3F) {
1557         result += 2;
1558         byte = byte << 2;
1559     }
1560     if (byte <= 0x7F)
1561         result++;
1562     return result;
1563 }
1564
1565 template<typename Header>
1566 Header* HeapPage<Header>::findHeaderFromAddress(Address address)
1567 {
1568     if (address < payload())
1569         return 0;
1570     if (!isObjectStartBitMapComputed())
1571         populateObjectStartBitMap();
1572     size_t objectOffset = address - payload();
1573     size_t objectStartNumber = objectOffset / allocationGranularity;
1574     size_t mapIndex = objectStartNumber / 8;
1575     ASSERT(mapIndex < objectStartBitMapSize);
1576     size_t bit = objectStartNumber & 7;
1577     uint8_t byte = m_objectStartBitMap[mapIndex] & ((1 << (bit + 1)) - 1);
1578     while (!byte) {
1579         ASSERT(mapIndex > 0);
1580         byte = m_objectStartBitMap[--mapIndex];
1581     }
1582     int leadingZeroes = numberOfLeadingZeroes(byte);
1583     objectStartNumber = (mapIndex * 8) + 7 - leadingZeroes;
1584     objectOffset = objectStartNumber * allocationGranularity;
1585     Address objectAddress = objectOffset + payload();
1586     Header* header = reinterpret_cast<Header*>(objectAddress);
1587     if (header->isFree())
1588         return 0;
1589     return header;
1590 }
1591
1592 template<typename Header>
1593 void HeapPage<Header>::checkAndMarkPointer(Visitor* visitor, Address address)
1594 {
1595     ASSERT(contains(address));
1596     Header* header = findHeaderFromAddress(address);
1597     if (!header || header->hasDeadMark())
1598         return;
1599
1600 #if ENABLE(GC_PROFILE_MARKING)
1601     visitor->setHostInfo(&address, "stack");
1602 #endif
1603     if (hasVTable(header) && !vTableInitialized(header->payload())) {
1604         visitor->markNoTracing(header);
1605         ASSERT(isUninitializedMemory(header->payload(), header->payloadSize()));
1606     } else {
1607         visitor->mark(header, traceCallback(header));
1608     }
1609 }
1610
1611 #if ENABLE(GC_PROFILE_MARKING)
1612 template<typename Header>
1613 const GCInfo* HeapPage<Header>::findGCInfo(Address address)
1614 {
1615     if (address < payload())
1616         return 0;
1617
1618     if (gcInfo()) // for non FinalizedObjectHeader
1619         return gcInfo();
1620
1621     Header* header = findHeaderFromAddress(address);
1622     if (!header)
1623         return 0;
1624
1625     return header->gcInfo();
1626 }
1627 #endif
1628
1629 #if ENABLE(GC_PROFILE_HEAP)
1630 template<typename Header>
1631 void HeapPage<Header>::snapshot(TracedValue* json, ThreadState::SnapshotInfo* info)
1632 {
1633     Header* header = 0;
1634     for (Address addr = payload(); addr < end(); addr += header->size()) {
1635         header = reinterpret_cast<Header*>(addr);
1636         if (json)
1637             json->pushInteger(header->encodedSize());
1638         if (header->isFree()) {
1639             info->freeSize += header->size();
1640             continue;
1641         }
1642
1643         const GCInfo* gcinfo = header->gcInfo() ? header->gcInfo() : gcInfo();
1644         size_t tag = info->getClassTag(gcinfo);
1645         size_t age = header->age();
1646         if (json)
1647             json->pushInteger(tag);
1648         if (header->isMarked()) {
1649             info->liveCount[tag] += 1;
1650             info->liveSize[tag] += header->size();
1651             // Count objects that are live when promoted to the final generation.
1652             if (age == maxHeapObjectAge - 1)
1653                 info->generations[tag][maxHeapObjectAge] += 1;
1654             header->incAge();
1655         } else {
1656             info->deadCount[tag] += 1;
1657             info->deadSize[tag] += header->size();
1658             // Count objects that are dead before the final generation.
1659             if (age < maxHeapObjectAge)
1660                 info->generations[tag][age] += 1;
1661         }
1662     }
1663 }
1664 #endif
1665
1666 #if defined(ADDRESS_SANITIZER)
1667 template<typename Header>
1668 void HeapPage<Header>::poisonUnmarkedObjects()
1669 {
1670     for (Address headerAddress = payload(); headerAddress < end(); ) {
1671         Header* header = reinterpret_cast<Header*>(headerAddress);
1672         ASSERT(header->size() < blinkPagePayloadSize());
1673
1674         if (!header->isFree() && !header->isMarked())
1675             ASAN_POISON_MEMORY_REGION(header->payload(), header->payloadSize());
1676         headerAddress += header->size();
1677     }
1678 }
1679 #endif
1680
1681 template<>
1682 inline void HeapPage<FinalizedHeapObjectHeader>::finalize(FinalizedHeapObjectHeader* header)
1683 {
1684     header->finalize();
1685 }
1686
1687 template<>
1688 inline void HeapPage<HeapObjectHeader>::finalize(HeapObjectHeader* header)
1689 {
1690     ASSERT(gcInfo());
1691     HeapObjectHeader::finalize(gcInfo(), header->payload(), header->payloadSize());
1692 }
1693
1694 template<>
1695 inline TraceCallback HeapPage<HeapObjectHeader>::traceCallback(HeapObjectHeader* header)
1696 {
1697     ASSERT(gcInfo());
1698     return gcInfo()->m_trace;
1699 }
1700
1701 template<>
1702 inline TraceCallback HeapPage<FinalizedHeapObjectHeader>::traceCallback(FinalizedHeapObjectHeader* header)
1703 {
1704     return header->traceCallback();
1705 }
1706
1707 template<>
1708 inline bool HeapPage<HeapObjectHeader>::hasVTable(HeapObjectHeader* header)
1709 {
1710     ASSERT(gcInfo());
1711     return gcInfo()->hasVTable();
1712 }
1713
1714 template<>
1715 inline bool HeapPage<FinalizedHeapObjectHeader>::hasVTable(FinalizedHeapObjectHeader* header)
1716 {
1717     return header->hasVTable();
1718 }
1719
1720 template<typename Header>
1721 void LargeHeapObject<Header>::getStats(HeapStats& stats)
1722 {
1723     stats.increaseAllocatedSpace(size());
1724     stats.increaseObjectSpace(payloadSize());
1725 }
1726
1727 #if ENABLE(GC_PROFILE_HEAP)
1728 template<typename Header>
1729 void LargeHeapObject<Header>::snapshot(TracedValue* json, ThreadState::SnapshotInfo* info)
1730 {
1731     Header* header = heapObjectHeader();
1732     size_t tag = info->getClassTag(header->gcInfo());
1733     size_t age = header->age();
1734     if (isMarked()) {
1735         info->liveCount[tag] += 1;
1736         info->liveSize[tag] += header->size();
1737         // Count objects that are live when promoted to the final generation.
1738         if (age == maxHeapObjectAge - 1)
1739             info->generations[tag][maxHeapObjectAge] += 1;
1740         header->incAge();
1741     } else {
1742         info->deadCount[tag] += 1;
1743         info->deadSize[tag] += header->size();
1744         // Count objects that are dead before the final generation.
1745         if (age < maxHeapObjectAge)
1746             info->generations[tag][age] += 1;
1747     }
1748
1749     if (json) {
1750         json->setInteger("class", tag);
1751         json->setInteger("size", header->size());
1752         json->setInteger("isMarked", isMarked());
1753     }
1754 }
1755 #endif
1756
1757 template<typename Entry>
1758 void HeapExtentCache<Entry>::flush()
1759 {
1760     if (m_hasEntries) {
1761         for (int i = 0; i < numberOfEntries; i++)
1762             m_entries[i] = Entry();
1763         m_hasEntries = false;
1764     }
1765 }
1766
1767 template<typename Entry>
1768 size_t HeapExtentCache<Entry>::hash(Address address)
1769 {
1770     size_t value = (reinterpret_cast<size_t>(address) >> blinkPageSizeLog2);
1771     value ^= value >> numberOfEntriesLog2;
1772     value ^= value >> (numberOfEntriesLog2 * 2);
1773     value &= numberOfEntries - 1;
1774     return value & ~1; // Returns only even number.
1775 }
1776
1777 template<typename Entry>
1778 typename Entry::LookupResult HeapExtentCache<Entry>::lookup(Address address)
1779 {
1780     size_t index = hash(address);
1781     ASSERT(!(index & 1));
1782     Address cachePage = roundToBlinkPageStart(address);
1783     if (m_entries[index].address() == cachePage)
1784         return m_entries[index].result();
1785     if (m_entries[index + 1].address() == cachePage)
1786         return m_entries[index + 1].result();
1787     return 0;
1788 }
1789
1790 template<typename Entry>
1791 void HeapExtentCache<Entry>::addEntry(Address address, typename Entry::LookupResult entry)
1792 {
1793     m_hasEntries = true;
1794     size_t index = hash(address);
1795     ASSERT(!(index & 1));
1796     Address cachePage = roundToBlinkPageStart(address);
1797     m_entries[index + 1] = m_entries[index];
1798     m_entries[index] = Entry(cachePage, entry);
1799 }
1800
1801 // These should not be needed, but it seems impossible to persuade clang to
1802 // instantiate the template functions and export them from a shared library, so
1803 // we add these in the non-templated subclass, which does not have that issue.
1804 void HeapContainsCache::addEntry(Address address, BaseHeapPage* page)
1805 {
1806     HeapExtentCache<PositiveEntry>::addEntry(address, page);
1807 }
1808
1809 BaseHeapPage* HeapContainsCache::lookup(Address address)
1810 {
1811     return HeapExtentCache<PositiveEntry>::lookup(address);
1812 }
1813
1814 void Heap::flushHeapDoesNotContainCache()
1815 {
1816     s_heapDoesNotContainCache->flush();
1817 }
1818
1819 // The marking mutex is used to ensure sequential access to data
1820 // structures during marking. The marking mutex needs to be acquired
1821 // during marking when elements are taken from the global marking
1822 // stack or when elements are added to the global ephemeron,
1823 // post-marking, and weak processing stacks. In debug mode the mutex
1824 // also needs to be acquired when asserts use the heap contains
1825 // caches.
1826 static Mutex& markingMutex()
1827 {
1828     AtomicallyInitializedStatic(Mutex&, mutex = *new Mutex);
1829     return mutex;
1830 }
1831
1832 static ThreadCondition& markingCondition()
1833 {
1834     AtomicallyInitializedStatic(ThreadCondition&, condition = *new ThreadCondition);
1835     return condition;
1836 }
1837
1838 static void markNoTracingCallback(Visitor* visitor, void* object)
1839 {
1840     visitor->markNoTracing(object);
1841 }
1842
1843 class MarkingVisitor : public Visitor {
1844 public:
1845 #if ENABLE(GC_PROFILE_MARKING)
1846     typedef HashSet<uintptr_t> LiveObjectSet;
1847     typedef HashMap<String, LiveObjectSet> LiveObjectMap;
1848     typedef HashMap<uintptr_t, std::pair<uintptr_t, String> > ObjectGraph;
1849 #endif
1850
1851     MarkingVisitor(CallbackStack* markingStack) : m_markingStack(markingStack)
1852     {
1853     }
1854
1855     inline void visitHeader(HeapObjectHeader* header, const void* objectPointer, TraceCallback callback)
1856     {
1857         ASSERT(header);
1858 #if ENABLE(ASSERT)
1859         {
1860             // Check that we are not marking objects that are outside
1861             // the heap by calling Heap::contains. However we cannot
1862             // call Heap::contains when outside a GC and we call mark
1863             // when doing weakness for ephemerons. Hence we only check
1864             // when called within.
1865             MutexLocker locker(markingMutex());
1866             ASSERT(!ThreadState::isAnyThreadInGC() || Heap::containedInHeapOrOrphanedPage(header));
1867         }
1868 #endif
1869         ASSERT(objectPointer);
1870         if (header->isMarked())
1871             return;
1872         header->mark();
1873 #if ENABLE(GC_PROFILE_MARKING)
1874         MutexLocker locker(objectGraphMutex());
1875         String className(classOf(objectPointer));
1876         {
1877             LiveObjectMap::AddResult result = currentlyLive().add(className, LiveObjectSet());
1878             result.storedValue->value.add(reinterpret_cast<uintptr_t>(objectPointer));
1879         }
1880         ObjectGraph::AddResult result = objectGraph().add(reinterpret_cast<uintptr_t>(objectPointer), std::make_pair(reinterpret_cast<uintptr_t>(m_hostObject), m_hostName));
1881         ASSERT(result.isNewEntry);
1882         // fprintf(stderr, "%s[%p] -> %s[%p]\n", m_hostName.ascii().data(), m_hostObject, className.ascii().data(), objectPointer);
1883 #endif
1884         if (callback)
1885             Heap::pushTraceCallback(m_markingStack, const_cast<void*>(objectPointer), callback);
1886     }
1887
1888     virtual void mark(HeapObjectHeader* header, TraceCallback callback) OVERRIDE
1889     {
1890         // We need both the HeapObjectHeader and FinalizedHeapObjectHeader
1891         // version to correctly find the payload.
1892         visitHeader(header, header->payload(), callback);
1893     }
1894
1895     virtual void mark(FinalizedHeapObjectHeader* header, TraceCallback callback) OVERRIDE
1896     {
1897         // We need both the HeapObjectHeader and FinalizedHeapObjectHeader
1898         // version to correctly find the payload.
1899         visitHeader(header, header->payload(), callback);
1900     }
1901
1902     virtual void mark(const void* objectPointer, TraceCallback callback) OVERRIDE
1903     {
1904         if (!objectPointer)
1905             return;
1906         FinalizedHeapObjectHeader* header = FinalizedHeapObjectHeader::fromPayload(objectPointer);
1907         visitHeader(header, header->payload(), callback);
1908     }
1909
1910     virtual void registerDelayedMarkNoTracing(const void* object) OVERRIDE
1911     {
1912         Heap::pushPostMarkingCallback(const_cast<void*>(object), markNoTracingCallback);
1913     }
1914
1915     virtual void registerWeakMembers(const void* closure, const void* containingObject, WeakPointerCallback callback) OVERRIDE
1916     {
1917         Heap::pushWeakObjectPointerCallback(const_cast<void*>(closure), const_cast<void*>(containingObject), callback);
1918     }
1919
1920     virtual void registerWeakTable(const void* closure, EphemeronCallback iterationCallback, EphemeronCallback iterationDoneCallback)
1921     {
1922         Heap::registerWeakTable(const_cast<void*>(closure), iterationCallback, iterationDoneCallback);
1923     }
1924
1925 #if ENABLE(ASSERT)
1926     virtual bool weakTableRegistered(const void* closure)
1927     {
1928         return Heap::weakTableRegistered(closure);
1929     }
1930 #endif
1931
1932     virtual bool isMarked(const void* objectPointer) OVERRIDE
1933     {
1934         return FinalizedHeapObjectHeader::fromPayload(objectPointer)->isMarked();
1935     }
1936
1937     // This macro defines the necessary visitor methods for typed heaps
1938 #define DEFINE_VISITOR_METHODS(Type)                                              \
1939     virtual void mark(const Type* objectPointer, TraceCallback callback) OVERRIDE \
1940     {                                                                             \
1941         if (!objectPointer)                                                       \
1942             return;                                                               \
1943         HeapObjectHeader* header =                                                \
1944             HeapObjectHeader::fromPayload(objectPointer);                         \
1945         visitHeader(header, header->payload(), callback);                         \
1946     }                                                                             \
1947     virtual bool isMarked(const Type* objectPointer) OVERRIDE                     \
1948     {                                                                             \
1949         return HeapObjectHeader::fromPayload(objectPointer)->isMarked();          \
1950     }
1951
1952     FOR_EACH_TYPED_HEAP(DEFINE_VISITOR_METHODS)
1953 #undef DEFINE_VISITOR_METHODS
1954
1955 #if ENABLE(GC_PROFILE_MARKING)
1956     void reportStats()
1957     {
1958         fprintf(stderr, "\n---------- AFTER MARKING -------------------\n");
1959         for (LiveObjectMap::iterator it = currentlyLive().begin(), end = currentlyLive().end(); it != end; ++it) {
1960             fprintf(stderr, "%s %u", it->key.ascii().data(), it->value.size());
1961
1962             if (it->key == "blink::Document")
1963                 reportStillAlive(it->value, previouslyLive().get(it->key));
1964
1965             fprintf(stderr, "\n");
1966         }
1967
1968         previouslyLive().swap(currentlyLive());
1969         currentlyLive().clear();
1970
1971         for (HashSet<uintptr_t>::iterator it = objectsToFindPath().begin(), end = objectsToFindPath().end(); it != end; ++it) {
1972             dumpPathToObjectFromObjectGraph(objectGraph(), *it);
1973         }
1974     }
1975
1976     static void reportStillAlive(LiveObjectSet current, LiveObjectSet previous)
1977     {
1978         int count = 0;
1979
1980         fprintf(stderr, " [previously %u]", previous.size());
1981         for (LiveObjectSet::iterator it = current.begin(), end = current.end(); it != end; ++it) {
1982             if (previous.find(*it) == previous.end())
1983                 continue;
1984             count++;
1985         }
1986
1987         if (!count)
1988             return;
1989
1990         fprintf(stderr, " {survived 2GCs %d: ", count);
1991         for (LiveObjectSet::iterator it = current.begin(), end = current.end(); it != end; ++it) {
1992             if (previous.find(*it) == previous.end())
1993                 continue;
1994             fprintf(stderr, "%ld", *it);
1995             if (--count)
1996                 fprintf(stderr, ", ");
1997         }
1998         ASSERT(!count);
1999         fprintf(stderr, "}");
2000     }
2001
2002     static void dumpPathToObjectFromObjectGraph(const ObjectGraph& graph, uintptr_t target)
2003     {
2004         ObjectGraph::const_iterator it = graph.find(target);
2005         if (it == graph.end())
2006             return;
2007         fprintf(stderr, "Path to %lx of %s\n", target, classOf(reinterpret_cast<const void*>(target)).ascii().data());
2008         while (it != graph.end()) {
2009             fprintf(stderr, "<- %lx of %s\n", it->value.first, it->value.second.utf8().data());
2010             it = graph.find(it->value.first);
2011         }
2012         fprintf(stderr, "\n");
2013     }
2014
2015     static void dumpPathToObjectOnNextGC(void* p)
2016     {
2017         objectsToFindPath().add(reinterpret_cast<uintptr_t>(p));
2018     }
2019
2020     static Mutex& objectGraphMutex()
2021     {
2022         AtomicallyInitializedStatic(Mutex&, mutex = *new Mutex);
2023         return mutex;
2024     }
2025
2026     static LiveObjectMap& previouslyLive()
2027     {
2028         DEFINE_STATIC_LOCAL(LiveObjectMap, map, ());
2029         return map;
2030     }
2031
2032     static LiveObjectMap& currentlyLive()
2033     {
2034         DEFINE_STATIC_LOCAL(LiveObjectMap, map, ());
2035         return map;
2036     }
2037
2038     static ObjectGraph& objectGraph()
2039     {
2040         DEFINE_STATIC_LOCAL(ObjectGraph, graph, ());
2041         return graph;
2042     }
2043
2044     static HashSet<uintptr_t>& objectsToFindPath()
2045     {
2046         DEFINE_STATIC_LOCAL(HashSet<uintptr_t>, set, ());
2047         return set;
2048     }
2049 #endif
2050
2051 protected:
2052     virtual void registerWeakCell(void** cell, WeakPointerCallback callback) OVERRIDE
2053     {
2054         Heap::pushWeakCellPointerCallback(cell, callback);
2055     }
2056
2057 private:
2058     CallbackStack* m_markingStack;
2059 };
2060
2061 void Heap::init()
2062 {
2063     ThreadState::init();
2064     s_markingStack = new CallbackStack();
2065     s_postMarkingCallbackStack = new CallbackStack();
2066     s_weakCallbackStack = new CallbackStack();
2067     s_ephemeronStack = new CallbackStack();
2068     s_heapDoesNotContainCache = new HeapDoesNotContainCache();
2069     s_markingVisitor = new MarkingVisitor(s_markingStack);
2070     s_freePagePool = new FreePagePool();
2071     s_orphanedPagePool = new OrphanedPagePool();
2072     s_markingThreads = new Vector<OwnPtr<blink::WebThread> >();
2073     if (blink::Platform::current()) {
2074         // FIXME: We should let the amount of threads scale with the
2075         // amount of processors in the system instead of hardcoding
2076         // it.
2077         for (int i = 0; i < numberOfMarkingThreads; i++)
2078             s_markingThreads->append(adoptPtr(blink::Platform::current()->createThread("Blink Heap Marker Thread")));
2079     }
2080 }
2081
2082 void Heap::shutdown()
2083 {
2084     s_shutdownCalled = true;
2085     ThreadState::shutdownHeapIfNecessary();
2086 }
2087
2088 void Heap::doShutdown()
2089 {
2090     // We don't want to call doShutdown() twice.
2091     if (!s_markingVisitor)
2092         return;
2093
2094     ASSERT(!ThreadState::isAnyThreadInGC());
2095     ASSERT(!ThreadState::attachedThreads().size());
2096     delete s_markingThreads;
2097     s_markingThreads = 0;
2098     delete s_markingVisitor;
2099     s_markingVisitor = 0;
2100     delete s_heapDoesNotContainCache;
2101     s_heapDoesNotContainCache = 0;
2102     delete s_freePagePool;
2103     s_freePagePool = 0;
2104     delete s_orphanedPagePool;
2105     s_orphanedPagePool = 0;
2106     delete s_weakCallbackStack;
2107     s_weakCallbackStack = 0;
2108     delete s_postMarkingCallbackStack;
2109     s_postMarkingCallbackStack = 0;
2110     delete s_markingStack;
2111     s_markingStack = 0;
2112     delete s_ephemeronStack;
2113     s_ephemeronStack = 0;
2114     ThreadState::shutdown();
2115 }
2116
2117 BaseHeapPage* Heap::contains(Address address)
2118 {
2119     ASSERT(ThreadState::isAnyThreadInGC());
2120     ThreadState::AttachedThreadStateSet& threads = ThreadState::attachedThreads();
2121     for (ThreadState::AttachedThreadStateSet::iterator it = threads.begin(), end = threads.end(); it != end; ++it) {
2122         BaseHeapPage* page = (*it)->contains(address);
2123         if (page)
2124             return page;
2125     }
2126     return 0;
2127 }
2128
2129 #if ENABLE(ASSERT)
2130 bool Heap::containedInHeapOrOrphanedPage(void* object)
2131 {
2132     return contains(object) || orphanedPagePool()->contains(object);
2133 }
2134 #endif
2135
2136 Address Heap::checkAndMarkPointer(Visitor* visitor, Address address)
2137 {
2138     ASSERT(ThreadState::isAnyThreadInGC());
2139
2140 #if !ENABLE(ASSERT)
2141     if (s_heapDoesNotContainCache->lookup(address))
2142         return 0;
2143 #endif
2144
2145     ThreadState::AttachedThreadStateSet& threads = ThreadState::attachedThreads();
2146     for (ThreadState::AttachedThreadStateSet::iterator it = threads.begin(), end = threads.end(); it != end; ++it) {
2147         if ((*it)->checkAndMarkPointer(visitor, address)) {
2148             // Pointer was in a page of that thread. If it actually pointed
2149             // into an object then that object was found and marked.
2150             ASSERT(!s_heapDoesNotContainCache->lookup(address));
2151             s_lastGCWasConservative = true;
2152             return address;
2153         }
2154     }
2155
2156 #if !ENABLE(ASSERT)
2157     s_heapDoesNotContainCache->addEntry(address, true);
2158 #else
2159     if (!s_heapDoesNotContainCache->lookup(address))
2160         s_heapDoesNotContainCache->addEntry(address, true);
2161 #endif
2162     return 0;
2163 }
2164
2165 #if ENABLE(GC_PROFILE_MARKING)
2166 const GCInfo* Heap::findGCInfo(Address address)
2167 {
2168     return ThreadState::findGCInfoFromAllThreads(address);
2169 }
2170 #endif
2171
2172 #if ENABLE(GC_PROFILE_MARKING)
2173 void Heap::dumpPathToObjectOnNextGC(void* p)
2174 {
2175     static_cast<MarkingVisitor*>(s_markingVisitor)->dumpPathToObjectOnNextGC(p);
2176 }
2177
2178 String Heap::createBacktraceString()
2179 {
2180     int framesToShow = 3;
2181     int stackFrameSize = 16;
2182     ASSERT(stackFrameSize >= framesToShow);
2183     typedef void* FramePointer;
2184     FramePointer* stackFrame = static_cast<FramePointer*>(alloca(sizeof(FramePointer) * stackFrameSize));
2185     WTFGetBacktrace(stackFrame, &stackFrameSize);
2186
2187     StringBuilder builder;
2188     builder.append("Persistent");
2189     bool didAppendFirstName = false;
2190     // Skip frames before/including "blink::Persistent".
2191     bool didSeePersistent = false;
2192     for (int i = 0; i < stackFrameSize && framesToShow > 0; ++i) {
2193         FrameToNameScope frameToName(stackFrame[i]);
2194         if (!frameToName.nullableName())
2195             continue;
2196         if (strstr(frameToName.nullableName(), "blink::Persistent")) {
2197             didSeePersistent = true;
2198             continue;
2199         }
2200         if (!didSeePersistent)
2201             continue;
2202         if (!didAppendFirstName) {
2203             didAppendFirstName = true;
2204             builder.append(" ... Backtrace:");
2205         }
2206         builder.append("\n\t");
2207         builder.append(frameToName.nullableName());
2208         --framesToShow;
2209     }
2210     return builder.toString().replace("blink::", "");
2211 }
2212 #endif
2213
2214 void Heap::pushTraceCallback(CallbackStack* stack, void* object, TraceCallback callback)
2215 {
2216 #if ENABLE(ASSERT)
2217     {
2218         MutexLocker locker(markingMutex());
2219         ASSERT(Heap::containedInHeapOrOrphanedPage(object));
2220     }
2221 #endif
2222     CallbackStack::Item* slot = stack->allocateEntry();
2223     *slot = CallbackStack::Item(object, callback);
2224 }
2225
2226 template<CallbackInvocationMode Mode>
2227 bool Heap::popAndInvokeTraceCallback(CallbackStack* stack, Visitor* visitor)
2228 {
2229     CallbackStack::Item* item = stack->pop();
2230     if (!item)
2231         return false;
2232     // If the object being traced is located on a page which is dead don't
2233     // trace it. This can happen when a conservative GC kept a dead object
2234     // alive which pointed to a (now gone) object on the cleaned up page.
2235     // Also, if doing a thread local GC, don't trace objects that are located
2236     // on other thread's heaps, ie, pages where the terminating flag is not set.
2237     BaseHeapPage* heapPage = pageHeaderFromObject(item->object());
2238     if (Mode == GlobalMarking && heapPage->orphaned()) {
2239         // When doing a global GC we should only get a trace callback to an orphaned
2240         // page if the GC is conservative. If it is not conservative there is
2241         // a bug in the code where we have a dangling pointer to a page
2242         // on the dead thread.
2243         RELEASE_ASSERT(Heap::lastGCWasConservative());
2244         heapPage->setTracedAfterOrphaned();
2245         return true;
2246     }
2247     if (Mode == ThreadLocalMarking && (heapPage->orphaned() || !heapPage->terminating()))
2248         return true;
2249
2250 #if ENABLE(GC_PROFILE_MARKING)
2251     visitor->setHostInfo(item->object(), classOf(item->object()));
2252 #endif
2253     item->call(visitor);
2254     return true;
2255 }
2256
2257 void Heap::pushPostMarkingCallback(void* object, TraceCallback callback)
2258 {
2259     MutexLocker locker(markingMutex());
2260     ASSERT(!Heap::orphanedPagePool()->contains(object));
2261     CallbackStack::Item* slot = s_postMarkingCallbackStack->allocateEntry();
2262     *slot = CallbackStack::Item(object, callback);
2263 }
2264
2265 bool Heap::popAndInvokePostMarkingCallback(Visitor* visitor)
2266 {
2267     if (CallbackStack::Item* item = s_postMarkingCallbackStack->pop()) {
2268         item->call(visitor);
2269         return true;
2270     }
2271     return false;
2272 }
2273
2274 void Heap::pushWeakCellPointerCallback(void** cell, WeakPointerCallback callback)
2275 {
2276     MutexLocker locker(markingMutex());
2277     ASSERT(!Heap::orphanedPagePool()->contains(cell));
2278     CallbackStack::Item* slot = s_weakCallbackStack->allocateEntry();
2279     *slot = CallbackStack::Item(cell, callback);
2280 }
2281
2282 void Heap::pushWeakObjectPointerCallback(void* closure, void* object, WeakPointerCallback callback)
2283 {
2284     MutexLocker locker(markingMutex());
2285     ASSERT(Heap::contains(object));
2286     BaseHeapPage* heapPageForObject = pageHeaderFromObject(object);
2287     ASSERT(!heapPageForObject->orphaned());
2288     ASSERT(Heap::contains(object) == heapPageForObject);
2289     ThreadState* state = heapPageForObject->threadState();
2290     state->pushWeakObjectPointerCallback(closure, callback);
2291 }
2292
2293 bool Heap::popAndInvokeWeakPointerCallback(Visitor* visitor)
2294 {
2295     // For weak processing we should never reach orphaned pages since orphaned
2296     // pages are not traced and thus objects on those pages are never be
2297     // registered as objects on orphaned pages. We cannot assert this here since
2298     // we might have an off-heap collection. We assert it in
2299     // Heap::pushWeakObjectPointerCallback.
2300     if (CallbackStack::Item* item = s_weakCallbackStack->pop()) {
2301         item->call(visitor);
2302         return true;
2303     }
2304     return false;
2305 }
2306
2307 void Heap::registerWeakTable(void* table, EphemeronCallback iterationCallback, EphemeronCallback iterationDoneCallback)
2308 {
2309     {
2310         MutexLocker locker(markingMutex());
2311         // Check that the ephemeron table being pushed onto the stack is not on an
2312         // orphaned page.
2313         ASSERT(!Heap::orphanedPagePool()->contains(table));
2314         CallbackStack::Item* slot = s_ephemeronStack->allocateEntry();
2315         *slot = CallbackStack::Item(table, iterationCallback);
2316     }
2317
2318     // Register a post-marking callback to tell the tables that
2319     // ephemeron iteration is complete.
2320     pushPostMarkingCallback(table, iterationDoneCallback);
2321 }
2322
2323 #if ENABLE(ASSERT)
2324 bool Heap::weakTableRegistered(const void* table)
2325 {
2326     MutexLocker locker(markingMutex());
2327     ASSERT(s_ephemeronStack);
2328     return s_ephemeronStack->hasCallbackForObject(table);
2329 }
2330 #endif
2331
2332 void Heap::prepareForGC()
2333 {
2334     ASSERT(ThreadState::isAnyThreadInGC());
2335     ThreadState::AttachedThreadStateSet& threads = ThreadState::attachedThreads();
2336     for (ThreadState::AttachedThreadStateSet::iterator it = threads.begin(), end = threads.end(); it != end; ++it)
2337         (*it)->prepareForGC();
2338 }
2339
2340 void Heap::collectGarbage(ThreadState::StackState stackState, ThreadState::CauseOfGC cause)
2341 {
2342     ThreadState* state = ThreadState::current();
2343     state->clearGCRequested();
2344
2345     GCScope gcScope(stackState);
2346     // Check if we successfully parked the other threads. If not we bail out of the GC.
2347     if (!gcScope.allThreadsParked()) {
2348         ThreadState::current()->setGCRequested();
2349         return;
2350     }
2351
2352     if (state->isMainThread())
2353         ScriptForbiddenScope::enter();
2354
2355     s_lastGCWasConservative = false;
2356
2357     TRACE_EVENT2("blink_gc", "Heap::collectGarbage",
2358         "precise", stackState == ThreadState::NoHeapPointersOnStack,
2359         "forced", cause == ThreadState::ForcedGC);
2360     TRACE_EVENT_SCOPED_SAMPLING_STATE("blink_gc", "BlinkGC");
2361     double timeStamp = WTF::currentTimeMS();
2362 #if ENABLE(GC_PROFILE_MARKING)
2363     static_cast<MarkingVisitor*>(s_markingVisitor)->objectGraph().clear();
2364 #endif
2365
2366     // Disallow allocation during garbage collection (but not
2367     // during the finalization that happens when the gcScope is
2368     // torn down).
2369     NoAllocationScope<AnyThread> noAllocationScope;
2370
2371     prepareForGC();
2372
2373     // 1. trace persistent roots.
2374     ThreadState::visitPersistentRoots(s_markingVisitor);
2375
2376     // 2. trace objects reachable from the persistent roots including ephemerons.
2377     processMarkingStackInParallel();
2378
2379     // 3. trace objects reachable from the stack. We do this independent of the
2380     // given stackState since other threads might have a different stack state.
2381     ThreadState::visitStackRoots(s_markingVisitor);
2382
2383     // 4. trace objects reachable from the stack "roots" including ephemerons.
2384     // Only do the processing if we found a pointer to an object on one of the
2385     // thread stacks.
2386     if (lastGCWasConservative())
2387         processMarkingStackInParallel();
2388
2389     postMarkingProcessing();
2390     globalWeakProcessing();
2391
2392     // After a global marking we know that any orphaned page that was not reached
2393     // cannot be reached in a subsequent GC. This is due to a thread either having
2394     // swept its heap or having done a "poor mans sweep" in prepareForGC which marks
2395     // objects that are dead, but not swept in the previous GC as dead. In this GC's
2396     // marking we check that any object marked as dead is not traced. E.g. via a
2397     // conservatively found pointer or a programming error with an object containing
2398     // a dangling pointer.
2399     orphanedPagePool()->decommitOrphanedPages();
2400
2401 #if ENABLE(GC_PROFILE_MARKING)
2402     static_cast<MarkingVisitor*>(s_markingVisitor)->reportStats();
2403 #endif
2404
2405     if (blink::Platform::current()) {
2406         uint64_t objectSpaceSize;
2407         uint64_t allocatedSpaceSize;
2408         getHeapSpaceSize(&objectSpaceSize, &allocatedSpaceSize);
2409         blink::Platform::current()->histogramCustomCounts("BlinkGC.CollectGarbage", WTF::currentTimeMS() - timeStamp, 0, 10 * 1000, 50);
2410         blink::Platform::current()->histogramCustomCounts("BlinkGC.TotalObjectSpace", objectSpaceSize / 1024, 0, 4 * 1024 * 1024, 50);
2411         blink::Platform::current()->histogramCustomCounts("BlinkGC.TotalAllocatedSpace", allocatedSpaceSize / 1024, 0, 4 * 1024 * 1024, 50);
2412     }
2413
2414     if (state->isMainThread())
2415         ScriptForbiddenScope::exit();
2416 }
2417
2418 void Heap::collectGarbageForTerminatingThread(ThreadState* state)
2419 {
2420     // We explicitly do not enter a safepoint while doing thread specific
2421     // garbage collection since we don't want to allow a global GC at the
2422     // same time as a thread local GC.
2423
2424     {
2425         NoAllocationScope<AnyThread> noAllocationScope;
2426
2427         state->enterGC();
2428         state->prepareForGC();
2429
2430         // 1. trace the thread local persistent roots. For thread local GCs we
2431         // don't trace the stack (ie. no conservative scanning) since this is
2432         // only called during thread shutdown where there should be no objects
2433         // on the stack.
2434         // We also assume that orphaned pages have no objects reachable from
2435         // persistent handles on other threads or CrossThreadPersistents. The
2436         // only cases where this could happen is if a subsequent conservative
2437         // global GC finds a "pointer" on the stack or due to a programming
2438         // error where an object has a dangling cross-thread pointer to an
2439         // object on this heap.
2440         state->visitPersistents(s_markingVisitor);
2441
2442         // 2. trace objects reachable from the thread's persistent roots
2443         // including ephemerons.
2444         processMarkingStack<ThreadLocalMarking>();
2445
2446         postMarkingProcessing();
2447         globalWeakProcessing();
2448
2449         state->leaveGC();
2450     }
2451     state->performPendingSweep();
2452 }
2453
2454 void Heap::processMarkingStackEntries(int* runningMarkingThreads)
2455 {
2456     TRACE_EVENT0("blink_gc", "Heap::processMarkingStackEntries");
2457     CallbackStack stack;
2458     MarkingVisitor visitor(&stack);
2459     {
2460         MutexLocker locker(markingMutex());
2461         stack.takeBlockFrom(s_markingStack);
2462     }
2463     while (!stack.isEmpty()) {
2464         while (popAndInvokeTraceCallback<GlobalMarking>(&stack, &visitor)) { }
2465         {
2466             MutexLocker locker(markingMutex());
2467             stack.takeBlockFrom(s_markingStack);
2468         }
2469     }
2470     {
2471         MutexLocker locker(markingMutex());
2472         if (!--(*runningMarkingThreads))
2473             markingCondition().signal();
2474     }
2475 }
2476
2477 void Heap::processMarkingStackOnMultipleThreads()
2478 {
2479     int runningMarkingThreads = s_markingThreads->size() + 1;
2480
2481     for (size_t i = 0; i < s_markingThreads->size(); ++i)
2482         s_markingThreads->at(i)->postTask(new Task(WTF::bind(Heap::processMarkingStackEntries, &runningMarkingThreads)));
2483
2484     processMarkingStackEntries(&runningMarkingThreads);
2485
2486     // Wait for the other threads to finish their part of marking.
2487     MutexLocker locker(markingMutex());
2488     while (runningMarkingThreads)
2489         markingCondition().wait(markingMutex());
2490 }
2491
2492 void Heap::processMarkingStackInParallel()
2493 {
2494     static const size_t sizeOfStackForParallelMarking = 2 * CallbackStack::blockSize;
2495     // Ephemeron fixed point loop run on the garbage collecting thread.
2496     do {
2497         // Iteratively mark all objects that are reachable from the objects
2498         // currently pushed onto the marking stack. Do so in parallel if there
2499         // are multiple blocks on the global marking stack.
2500         if (s_markingStack->sizeExceeds(sizeOfStackForParallelMarking)) {
2501             processMarkingStackOnMultipleThreads();
2502         } else {
2503             TRACE_EVENT0("blink_gc", "Heap::processMarkingStackSingleThreaded");
2504             while (popAndInvokeTraceCallback<GlobalMarking>(s_markingStack, s_markingVisitor)) { }
2505         }
2506
2507         // Mark any strong pointers that have now become reachable in ephemeron
2508         // maps.
2509         TRACE_EVENT0("blink_gc", "Heap::processEphemeronStack");
2510         s_ephemeronStack->invokeEphemeronCallbacks(s_markingVisitor);
2511
2512         // Rerun loop if ephemeron processing queued more objects for tracing.
2513     } while (!s_markingStack->isEmpty());
2514 }
2515
2516 template<CallbackInvocationMode Mode>
2517 void Heap::processMarkingStack()
2518 {
2519     // Ephemeron fixed point loop.
2520     do {
2521         // Iteratively mark all objects that are reachable from the objects
2522         // currently pushed onto the marking stack. If Mode is ThreadLocalMarking
2523         // don't continue tracing if the trace hits an object on another thread's
2524         // heap.
2525         TRACE_EVENT0("blink_gc", "Heap::processMarkingStackSingleThreaded");
2526         while (popAndInvokeTraceCallback<Mode>(s_markingStack, s_markingVisitor)) { }
2527
2528         // Mark any strong pointers that have now become reachable in ephemeron
2529         // maps.
2530         TRACE_EVENT0("blink_gc", "Heap::processEphemeronStack");
2531         s_ephemeronStack->invokeEphemeronCallbacks(s_markingVisitor);
2532
2533         // Rerun loop if ephemeron processing queued more objects for tracing.
2534     } while (!s_markingStack->isEmpty());
2535 }
2536
2537 void Heap::postMarkingProcessing()
2538 {
2539     TRACE_EVENT0("blink_gc", "Heap::postMarkingProcessing");
2540     // Call post-marking callbacks including:
2541     // 1. the ephemeronIterationDone callbacks on weak tables to do cleanup
2542     //    (specifically to clear the queued bits for weak hash tables), and
2543     // 2. the markNoTracing callbacks on collection backings to mark them
2544     //    if they are only reachable from their front objects.
2545     while (popAndInvokePostMarkingCallback(s_markingVisitor)) { }
2546
2547     s_ephemeronStack->clear();
2548
2549     // Post-marking callbacks should not trace any objects and
2550     // therefore the marking stack should be empty after the
2551     // post-marking callbacks.
2552     ASSERT(s_markingStack->isEmpty());
2553 }
2554
2555 void Heap::globalWeakProcessing()
2556 {
2557     TRACE_EVENT0("blink_gc", "Heap::globalWeakProcessing");
2558     // Call weak callbacks on objects that may now be pointing to dead
2559     // objects.
2560     while (popAndInvokeWeakPointerCallback(s_markingVisitor)) { }
2561
2562     // It is not permitted to trace pointers of live objects in the weak
2563     // callback phase, so the marking stack should still be empty here.
2564     ASSERT(s_markingStack->isEmpty());
2565 }
2566
2567 void Heap::collectAllGarbage()
2568 {
2569     // FIXME: oilpan: we should perform a single GC and everything
2570     // should die. Unfortunately it is not the case for all objects
2571     // because the hierarchy was not completely moved to the heap and
2572     // some heap allocated objects own objects that contain persistents
2573     // pointing to other heap allocated objects.
2574     for (int i = 0; i < 5; i++)
2575         collectGarbage(ThreadState::NoHeapPointersOnStack, ThreadState::ForcedGC);
2576 }
2577
2578 void Heap::setForcePreciseGCForTesting()
2579 {
2580     ThreadState::current()->setForcePreciseGCForTesting(true);
2581 }
2582
2583 template<typename Header>
2584 void ThreadHeap<Header>::prepareHeapForTermination()
2585 {
2586     for (HeapPage<Header>* page = m_firstPage; page; page = page->next()) {
2587         page->setTerminating();
2588     }
2589     for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current; current = current->next()) {
2590         current->setTerminating();
2591     }
2592 }
2593
2594 template<typename Header>
2595 BaseHeap* ThreadHeap<Header>::split(int numberOfNormalPages)
2596 {
2597     // Create a new split off thread heap containing
2598     // |numberOfNormalPages| of the pages of this ThreadHeap for
2599     // parallel sweeping. The split off thread heap will be merged
2600     // with this heap at the end of sweeping and the temporary
2601     // ThreadHeap object will be deallocated after the merge.
2602     ASSERT(numberOfNormalPages > 0);
2603     ThreadHeap<Header>* splitOff = new ThreadHeap(m_threadState, m_index);
2604     HeapPage<Header>* splitPoint = m_firstPage;
2605     for (int i = 1; i < numberOfNormalPages; i++)
2606         splitPoint = splitPoint->next();
2607     splitOff->m_firstPage = m_firstPage;
2608     m_firstPage = splitPoint->m_next;
2609     splitOff->m_mergePoint = splitPoint;
2610     splitOff->m_numberOfNormalPages = numberOfNormalPages;
2611     m_numberOfNormalPages -= numberOfNormalPages;
2612     splitPoint->m_next = 0;
2613     return splitOff;
2614 }
2615
2616 template<typename Header>
2617 void ThreadHeap<Header>::merge(BaseHeap* splitOffBase)
2618 {
2619     ThreadHeap<Header>* splitOff = static_cast<ThreadHeap<Header>*>(splitOffBase);
2620     // If the mergePoint is zero all split off pages became empty in
2621     // this round and we don't have to merge. There are no pages and
2622     // nothing on the freelists.
2623     ASSERT(splitOff->m_mergePoint || splitOff->m_numberOfNormalPages == 0);
2624     if (splitOff->m_mergePoint) {
2625         // Link the split off pages into the beginning of the list again.
2626         splitOff->m_mergePoint->m_next = m_firstPage;
2627         m_firstPage = splitOff->m_firstPage;
2628         m_numberOfNormalPages += splitOff->m_numberOfNormalPages;
2629         splitOff->m_firstPage = 0;
2630         // Merge free lists.
2631         for (size_t i = 0; i < blinkPageSizeLog2; i++) {
2632             if (!m_freeLists[i]) {
2633                 m_freeLists[i] = splitOff->m_freeLists[i];
2634             } else if (splitOff->m_freeLists[i]) {
2635                 m_lastFreeListEntries[i]->append(splitOff->m_freeLists[i]);
2636                 m_lastFreeListEntries[i] = splitOff->m_lastFreeListEntries[i];
2637             }
2638         }
2639     }
2640     delete splitOffBase;
2641 }
2642
2643 void Heap::getHeapSpaceSize(uint64_t* objectSpaceSize, uint64_t* allocatedSpaceSize)
2644 {
2645     *objectSpaceSize = 0;
2646     *allocatedSpaceSize = 0;
2647     ASSERT(ThreadState::isAnyThreadInGC());
2648     ThreadState::AttachedThreadStateSet& threads = ThreadState::attachedThreads();
2649     typedef ThreadState::AttachedThreadStateSet::iterator ThreadStateIterator;
2650     for (ThreadStateIterator it = threads.begin(), end = threads.end(); it != end; ++it) {
2651         *objectSpaceSize += (*it)->stats().totalObjectSpace();
2652         *allocatedSpaceSize += (*it)->stats().totalAllocatedSpace();
2653     }
2654 }
2655
2656 void Heap::getStats(HeapStats* stats)
2657 {
2658     stats->clear();
2659     ASSERT(ThreadState::isAnyThreadInGC());
2660     ThreadState::AttachedThreadStateSet& threads = ThreadState::attachedThreads();
2661     typedef ThreadState::AttachedThreadStateSet::iterator ThreadStateIterator;
2662     for (ThreadStateIterator it = threads.begin(), end = threads.end(); it != end; ++it) {
2663         HeapStats temp;
2664         (*it)->getStats(temp);
2665         stats->add(&temp);
2666     }
2667 }
2668
2669 #if ENABLE(ASSERT)
2670 bool Heap::isConsistentForSweeping()
2671 {
2672     ASSERT(ThreadState::isAnyThreadInGC());
2673     ThreadState::AttachedThreadStateSet& threads = ThreadState::attachedThreads();
2674     for (ThreadState::AttachedThreadStateSet::iterator it = threads.begin(), end = threads.end(); it != end; ++it) {
2675         if (!(*it)->isConsistentForSweeping())
2676             return false;
2677     }
2678     return true;
2679 }
2680 #endif
2681
2682 void Heap::makeConsistentForSweeping()
2683 {
2684     ASSERT(ThreadState::isAnyThreadInGC());
2685     ThreadState::AttachedThreadStateSet& threads = ThreadState::attachedThreads();
2686     for (ThreadState::AttachedThreadStateSet::iterator it = threads.begin(), end = threads.end(); it != end; ++it)
2687         (*it)->makeConsistentForSweeping();
2688 }
2689
2690 void HeapAllocator::backingFree(void* address)
2691 {
2692     if (!address || ThreadState::isAnyThreadInGC())
2693         return;
2694
2695     ThreadState* state = ThreadState::current();
2696     if (state->isSweepInProgress())
2697         return;
2698
2699     // Don't promptly free large objects because their page is never reused
2700     // and don't free backings allocated on other threads.
2701     BaseHeapPage* page = pageHeaderFromObject(address);
2702     if (page->isLargeObject() || page->threadState() != state)
2703         return;
2704
2705     typedef HeapIndexTrait<CollectionBackingHeap> HeapTraits;
2706     typedef HeapTraits::HeapType HeapType;
2707     typedef HeapTraits::HeaderType HeaderType;
2708
2709     HeaderType* header = HeaderType::fromPayload(address);
2710     header->checkHeader();
2711
2712     const GCInfo* gcInfo = header->gcInfo();
2713     int heapIndex = HeapTraits::index(gcInfo->hasFinalizer());
2714     HeapType* heap = static_cast<HeapType*>(state->heap(heapIndex));
2715     heap->promptlyFreeObject(header);
2716 }
2717
2718 // Force template instantiations for the types that we need.
2719 template class HeapPage<FinalizedHeapObjectHeader>;
2720 template class HeapPage<HeapObjectHeader>;
2721 template class ThreadHeap<FinalizedHeapObjectHeader>;
2722 template class ThreadHeap<HeapObjectHeader>;
2723
2724 Visitor* Heap::s_markingVisitor;
2725 Vector<OwnPtr<blink::WebThread> >* Heap::s_markingThreads;
2726 CallbackStack* Heap::s_markingStack;
2727 CallbackStack* Heap::s_postMarkingCallbackStack;
2728 CallbackStack* Heap::s_weakCallbackStack;
2729 CallbackStack* Heap::s_ephemeronStack;
2730 HeapDoesNotContainCache* Heap::s_heapDoesNotContainCache;
2731 bool Heap::s_shutdownCalled = false;
2732 bool Heap::s_lastGCWasConservative = false;
2733 FreePagePool* Heap::s_freePagePool;
2734 OrphanedPagePool* Heap::s_orphanedPagePool;
2735 }