[oilpan]: Make thread shutdown more robust.

Source/platform/heap/Heap.cpp

Index: Source/platform/heap/Heap.cpp
diff --git a/Source/platform/heap/Heap.cpp b/Source/platform/heap/Heap.cpp
index 1198ebc454c71df7b1ef6ad5164375343cfd68a1..f2d932a3cedabd044c7065884f869c7445a2e730 100644
--- a/Source/platform/heap/Heap.cpp
+++ b/Source/platform/heap/Heap.cpp
@@ -423,24 +423,25 @@ void HeapObjectHeader::unmark()
 }
 
 NO_SANITIZE_ADDRESS
-bool HeapObjectHeader::hasDebugMark() const
+bool HeapObjectHeader::hasDeadMark() const
 {
     checkHeader();
-    return m_size & debugBitMask;
+    return m_size & deadBitMask;
 }
 
 NO_SANITIZE_ADDRESS
-void HeapObjectHeader::clearDebugMark()
+void HeapObjectHeader::clearDeadMark()
 {
     checkHeader();
-    m_size &= ~debugBitMask;
+    m_size &= ~deadBitMask;
 }
 
 NO_SANITIZE_ADDRESS
-void HeapObjectHeader::setDebugMark()
+void HeapObjectHeader::setDeadMark()
 {
+    ASSERT(!isMarked());
     checkHeader();
-    m_size |= debugBitMask;
+    m_size |= deadBitMask;
 }
 
 #ifndef NDEBUG
@@ -500,10 +501,16 @@ bool LargeHeapObject<Header>::isMarked()
 }
 
 template<typename Header>
+void LargeHeapObject<Header>::setDeadMark()
+{
+    heapObjectHeader()->setDeadMark();
+}
+
+template<typename Header>
 void LargeHeapObject<Header>::checkAndMarkPointer(Visitor* visitor, Address address)
 {
     ASSERT(contains(address));
-    if (!objectContains(address))
+    if (!objectContains(address) || heapObjectHeader()->hasDeadMark())
         return;
 #if ENABLE(GC_TRACING)
     visitor->setHostInfo(&address, "stack");
@@ -552,14 +559,14 @@ FinalizedHeapObjectHeader* FinalizedHeapObjectHeader::fromPayload(const void* pa
 }
 
 template<typename Header>
-ThreadHeap<Header>::ThreadHeap(ThreadState* state)
+ThreadHeap<Header>::ThreadHeap(ThreadState* state, int index)
     : m_currentAllocationPoint(0)
     , m_remainingAllocationSize(0)
     , m_firstPage(0)
     , m_firstLargeHeapObject(0)
     , m_biggestFreeListIndex(0)
     , m_threadState(state)
-    , m_pagePool(0)
+    , m_index(index)
 {
     clearFreeLists();
 }
@@ -568,9 +575,18 @@ template<typename Header>
 ThreadHeap<Header>::~ThreadHeap()
 {
     clearFreeLists();
-    if (!ThreadState::current()->isMainThread())
-        assertEmpty();
-    deletePages();
+    flushHeapContainsCache();
+
+    // Add the ThreadHeap's pages to the orphanedPagePool.
+    Vector<BaseHeapPage*> pages;
+    for (HeapPage<Header>* page = m_firstPage; page; page = page->m_next)
+        pages.append(page);

[Mads Ager (chromium), 2014/07/09 09:31:40]

I think we might as well just add the pages directly to the orphanedPagePool
here instead of first building up a temporary vector backing of all the pointers
and then adding them all to the pool?

[wibling-chromium, 2014/07/09 10:32:30]

Done. I previously had a lock on the orphanedPagePool however that is now gone
so will get rid of addOrphanedPages.

+    m_firstPage = 0;
+
+    for (LargeHeapObject<Header>* largeObject = m_firstLargeHeapObject; largeObject; largeObject = largeObject->m_next)
+        pages.append(largeObject);
+    m_firstLargeHeapObject = 0;
+    Heap::orphanedPagePool()->addOrphanedPages(m_index, pages);
 }
 
 template<typename Header>
@@ -740,73 +756,212 @@ void ThreadHeap<Header>::freeLargeObject(LargeHeapObject<Header>* object, LargeH
     // object before freeing.
     ASAN_UNPOISON_MEMORY_REGION(object->heapObjectHeader(), sizeof(Header));
     ASAN_UNPOISON_MEMORY_REGION(object->address() + object->size(), allocationGranularity);
-    delete object->storage();
+
+    if (object->shuttingDown()) {
+        ASSERT(ThreadState::current()->isCleaningUp());
+        // The thread is shutting down so this object is being removed as part
+        // of a thread local GC. In that case the object could be traced in the
+        // next global GC either due to a dead object being traced via a
+        // conservative pointer or due to a programming error where an object
+        // in another thread heap keeps a dangling pointer to this object.
+        // To guard against this we put the large object memory in the
+        // orphanedPagePool to ensure it is still reachable. After the next global
+        // GC it can be released assuming no rogue/dangling pointers refer to
+        // it.
+        // NOTE: large objects are not moved to the memory pool as it is unlikely

[Mads Ager (chromium), 2014/07/09 09:31:40]

memory pool -> free page pool.

[wibling-chromium, 2014/07/09 10:32:30]

Done.

+        // they can be reused due to their individual sizes.
+        Heap::orphanedPagePool()->addOrphanedPage(m_index, object);
+    } else {
+        PageMemory* memory = object->storage();
+        object->~LargeHeapObject<Header>();
+        delete memory;
+    }
 }
 
-template<>
-void ThreadHeap<FinalizedHeapObjectHeader>::addPageToHeap(const GCInfo* gcInfo)
+template<typename DataType>
+PagePool<DataType>::PagePool()
 {
-    // When adding a page to the ThreadHeap using FinalizedHeapObjectHeaders the GCInfo on
-    // the heap should be unused (ie. 0).
-    allocatePage(0);
+    for (int i = 0; i < NumberOfHeaps; ++i) {
+        m_pool[i] = 0;
+    }
 }
 
-template<>
-void ThreadHeap<HeapObjectHeader>::addPageToHeap(const GCInfo* gcInfo)
+FreePagePool::~FreePagePool()
 {
-    // When adding a page to the ThreadHeap using HeapObjectHeaders store the GCInfo on the heap
-    // since it is the same for all objects
-    ASSERT(gcInfo);
-    allocatePage(gcInfo);
+    for (int index = 0; index < NumberOfHeaps; ++index) {
+        while (PoolEntry* entry = m_pool[index]) {
+            m_pool[index] = entry->next;
+            PageMemory* memory = entry->data;
+            ASSERT(memory);
+            delete memory;
+            delete entry;
+        }
+    }
 }
 
-template<typename Header>
-void ThreadHeap<Header>::clearPagePool()
+void FreePagePool::addFreePage(int index, PageMemory* memory)
 {
-    while (takePageFromPool()) { }
+    // When adding a page to the pool we decommit it to ensure it is unused
+    // while in the pool. This also allows the physical memory, backing the
+    // page, to be given back to the OS.
+    memory->decommit();
+    MutexLocker locker(m_mutex[index]);

[haraken, 2014/07/09 08:01:59]

Just to confirm: Doesn't this need to be SafePointAwareMutexLocker? I think
addFreePage() can be called from Heap::allocate() (which can be called from
everywhere).

[wibling-chromium, 2014/07/09 10:32:30]

No, we are not at a safepoint here since this can be called via destructors,
during sweep, etc. So the heap is not in a consistent state at this point. 

+    PoolEntry* entry = new PoolEntry(memory, m_pool[index]);
+    m_pool[index] = entry;
 }
 
-template<typename Header>
-PageMemory* ThreadHeap<Header>::takePageFromPool()
+PageMemory* FreePagePool::takeFreePage(int index)
 {
-    Heap::flushHeapDoesNotContainCache();
-    while (PagePoolEntry* entry = m_pagePool) {
-        m_pagePool = entry->next();
-        PageMemory* storage = entry->storage();
+    MutexLocker locker(m_mutex[index]);

[haraken, 2014/07/09 08:01:59]

Ditto.

+    while (PoolEntry* entry = m_pool[index]) {
+        m_pool[index] = entry->next;
+        PageMemory* memory = entry->data;
+        ASSERT(memory);
         delete entry;
+        if (memory->commit())
+            return memory;
 
-        if (storage->commit())
-            return storage;
+        // We got some memory, but failed to commit it, try again.
+        delete memory;
+    }
+    return 0;
+}
 
-        // Failed to commit pooled storage. Release it.
-        delete storage;
+OrphanedPagePool::~OrphanedPagePool()
+{
+    for (int index = 0; index < NumberOfHeaps; ++index) {
+        while (PoolEntry* entry = m_pool[index]) {
+            m_pool[index] = entry->next;
+            BaseHeapPage* page = entry->data;
+            delete entry;
+            PageMemory* memory = page->storage();
+            ASSERT(memory);
+            page->~BaseHeapPage();
+            delete memory;
+        }
     }
+}
 
-    return 0;
+void OrphanedPagePool::addOrphanedPage(int index, BaseHeapPage* page)
+{
+    page->markOrphaned();
+    PoolEntry* entry = new PoolEntry(page, m_pool[index]);
+    m_pool[index] = entry;
 }
 
-template<typename Header>
-void ThreadHeap<Header>::addPageMemoryToPool(PageMemory* storage)
+void OrphanedPagePool::addOrphanedPages(int index, Vector<BaseHeapPage*>& pages)
 {
-    flushHeapContainsCache();
-    PagePoolEntry* entry = new PagePoolEntry(storage, m_pagePool);
-    m_pagePool = entry;
+    for (Vector<BaseHeapPage*>::const_iterator it = pages.begin(); it != pages.end(); ++it) {
+        addOrphanedPage(index, *it);
+    }
+}
+
+void OrphanedPagePool::decommitOrphanedPages()
+{
+#ifndef NDEBUG
+    // No locking needed as all threads are at safepoints at this point in time.
+    ThreadState::AttachedThreadStateSet& threads = ThreadState::attachedThreads();
+    for (ThreadState::AttachedThreadStateSet::iterator it = threads.begin(), end = threads.end(); it != end; ++it)
+        ASSERT((*it)->isAtSafePoint());
+#endif
+
+    for (int index = 0; index < NumberOfHeaps; ++index) {
+        PoolEntry* entry = m_pool[index];
+        PoolEntry** prevNext = &m_pool[index];
+        while (entry) {
+            BaseHeapPage* page = entry->data;
+            if (page->traced()) {
+                // If the page was traced in the last GC it is not decommited.
+                // We only decommit a page, ie. put it in the memory pool,
+                // when the page has no objects pointing to it.
+                // We mark the page as orphaned. This clears the traced flag
+                // and any object trace bits that were set during tracing.
+                page->markOrphaned();

[haraken, 2014/07/09 08:01:59]

Do we need to call markOrphaned()? I guess the page is already marked as
orphaned.

[wibling-chromium, 2014/07/09 10:32:31]

Yes, we need to call it to clear the trace bits, both on the page and on the
objects.

+                prevNext = &entry->next;
+                entry = entry->next;
+                continue;
+            }
+
+            // Page was not traced. Check if we should reuse the memory or just
+            // free it. Large object memory is not reused, but freed, normal
+            // blink heap pages are reused.
+            // NOTE: We call the destructor before freeing or adding to the
+            // free page pool.
+            PageMemory* memory = page->storage();
+            if (page->isLargeObject()) {
+                page->~BaseHeapPage();
+                delete memory;
+            } else {
+                page->~BaseHeapPage();
+                Heap::freePagePool()->addFreePage(index, memory);
+            }
+
+            PoolEntry* deadEntry = entry;
+            entry = entry->next;
+            *prevNext = entry;
+            delete deadEntry;
+        }
+    }
+}
+
+bool OrphanedPagePool::contains(void* object)

[haraken, 2014/07/09 08:01:59]

Shall we add #ifndef NDEBUG ?

[wibling-chromium, 2014/07/09 10:32:30]

Done.

+{
+    for (int index = 0; index < NumberOfHeaps; ++index) {
+        for (PoolEntry* entry = m_pool[index]; entry; entry = entry->next) {
+            BaseHeapPage* page = entry->data;
+            if (page->contains(reinterpret_cast<Address>(object)))
+                return true;
+        }
+    }
+    return false;
+}
+
+template<>
+void ThreadHeap<FinalizedHeapObjectHeader>::addPageToHeap(const GCInfo* gcInfo)
+{
+    // When adding a page to the ThreadHeap using FinalizedHeapObjectHeaders the GCInfo on
+    // the heap should be unused (ie. 0).
+    allocatePage(0);
+}
+
+template<>
+void ThreadHeap<HeapObjectHeader>::addPageToHeap(const GCInfo* gcInfo)
+{
+    // When adding a page to the ThreadHeap using HeapObjectHeaders store the GCInfo on the heap
+    // since it is the same for all objects
+    ASSERT(gcInfo);
+    allocatePage(gcInfo);
 }
 
 template <typename Header>
-void ThreadHeap<Header>::addPageToPool(HeapPage<Header>* page)
+void ThreadHeap<Header>::removePageFromHeap(HeapPage<Header>* page)
 {
-    PageMemory* storage = page->storage();
-    storage->decommit();
-    addPageMemoryToPool(storage);
+    flushHeapContainsCache();
+    if (page->shuttingDown()) {
+        ASSERT(ThreadState::current()->isCleaningUp());
+        // The thread is shutting down so this page is being removed as part
+        // of a thread local GC. In that case the page could be accessed in the
+        // next global GC either due to a dead object being traced via a
+        // conservative pointer or due to a programming error where an object
+        // in another thread heap keeps a dangling pointer to this object.
+        // To guard against this we put the page in the orphanedPagePool to
+        // ensure it is still reachable. After the next global GC it can be
+        // decommitted and moved to the page pool assuming no rogue/dangling
+        // pointers refer to it.
+        Heap::orphanedPagePool()->addOrphanedPage(m_index, page);
+    } else {
+        PageMemory* memory = page->storage();
+        page->~HeapPage<Header>();
+        Heap::freePagePool()->addFreePage(m_index, memory);
+    }
 }
 
 template<typename Header>
 void ThreadHeap<Header>::allocatePage(const GCInfo* gcInfo)
 {
     Heap::flushHeapDoesNotContainCache();
-    PageMemory* pageMemory = takePageFromPool();
-    if (!pageMemory) {
+    PageMemory* pageMemory = Heap::freePagePool()->takeFreePage(m_index);
+    while (!pageMemory) {

[haraken, 2014/07/09 08:01:59]

Let's add a comment why this needs to be 'while'.

[wibling-chromium, 2014/07/09 10:32:31]

Done.

         // Allocate a memory region for blinkPagesPerRegion pages that
         // will each have the following layout.
         //
@@ -817,11 +972,10 @@ void ThreadHeap<Header>::allocatePage(const GCInfo* gcInfo)
         // region.
         size_t offset = 0;
         for (size_t i = 0; i < blinkPagesPerRegion; i++) {
-            addPageMemoryToPool(PageMemory::setupPageMemoryInRegion(region, offset, blinkPagePayloadSize()));
+            Heap::freePagePool()->addFreePage(m_index, PageMemory::setupPageMemoryInRegion(region, offset, blinkPagePayloadSize()));
             offset += blinkPageSize;
         }
-        pageMemory = takePageFromPool();
-        RELEASE_ASSERT(pageMemory);
+        pageMemory = Heap::freePagePool()->takeFreePage(m_index);
     }
     HeapPage<Header>* page = new (pageMemory->writableStart()) HeapPage<Header>(pageMemory, this, gcInfo);
     // FIXME: Oilpan: Linking new pages into the front of the list is
@@ -865,22 +1019,17 @@ void ThreadHeap<Header>::sweep()
 #endif
     HeapPage<Header>* page = m_firstPage;
     HeapPage<Header>** previous = &m_firstPage;
-    bool pagesRemoved = false;
     while (page) {
         if (page->isEmpty()) {
-            flushHeapContainsCache();
             HeapPage<Header>* unused = page;
             page = page->next();
             HeapPage<Header>::unlink(unused, previous);
-            pagesRemoved = true;
         } else {
             page->sweep();
             previous = &page->m_next;
             page = page->next();
         }
     }
-    if (pagesRemoved)
-        flushHeapContainsCache();
 
     LargeHeapObject<Header>** previousNext = &m_firstLargeHeapObject;
     for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current;) {
@@ -899,43 +1048,6 @@ void ThreadHeap<Header>::sweep()
 }
 
 template<typename Header>
-void ThreadHeap<Header>::assertEmpty()
-{
-    // No allocations are permitted. The thread is exiting.
-    NoAllocationScope<AnyThread> noAllocation;
-    makeConsistentForGC();
-    for (HeapPage<Header>* page = m_firstPage; page; page = page->next()) {
-        Address end = page->end();
-        Address headerAddress;
-        for (headerAddress = page->payload(); headerAddress < end; ) {
-            BasicObjectHeader* basicHeader = reinterpret_cast<BasicObjectHeader*>(headerAddress);
-            ASSERT(basicHeader->size() < blinkPagePayloadSize());
-            // A live object is potentially a dangling pointer from
-            // some root. Treat that as a bug. Unfortunately, it is
-            // hard to reliably check in the presence of conservative
-            // stack scanning. Something could be conservatively kept
-            // alive because a non-pointer on another thread's stack
-            // is treated as a pointer into the heap.
-            //
-            // FIXME: This assert can currently trigger in cases where
-            // worker shutdown does not get enough precise GCs to get
-            // all objects removed from the worker heap. There are two
-            // issues: 1) conservative GCs keeping objects alive, and
-            // 2) long chains of RefPtrs/Persistents that require more
-            // GCs to get everything cleaned up. Maybe we can keep
-            // threads alive until their heaps become empty instead of
-            // forcing the threads to die immediately?
-            ASSERT(Heap::lastGCWasConservative() || basicHeader->isFree());
-            headerAddress += basicHeader->size();
-        }
-        ASSERT(headerAddress == end);
-        addToFreeList(page->payload(), end - page->payload());
-    }
-
-    ASSERT(Heap::lastGCWasConservative() || !m_firstLargeHeapObject);
-}
-
-template<typename Header>
 bool ThreadHeap<Header>::isConsistentForGC()
 {
     for (size_t i = 0; i < blinkPageSizeLog2; i++) {
@@ -955,39 +1067,17 @@ void ThreadHeap<Header>::makeConsistentForGC()
 }
 
 template<typename Header>
-void ThreadHeap<Header>::clearMarks()
+void ThreadHeap<Header>::clearLiveAndMarkDead()
 {
     ASSERT(isConsistentForGC());
     for (HeapPage<Header>* page = m_firstPage; page; page = page->next())
-        page->clearMarks();
-    for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current; current = current->next())
-        current->unmark();
-}
-
-template<typename Header>
-void ThreadHeap<Header>::deletePages()
-{
-    flushHeapContainsCache();
-    // Add all pages in the pool to the heap's list of pages before deleting
-    clearPagePool();
-
-    for (HeapPage<Header>* page = m_firstPage; page; ) {
-        HeapPage<Header>* dead = page;
-        page = page->next();
-        PageMemory* storage = dead->storage();
-        dead->~HeapPage();
-        delete storage;
-    }
-    m_firstPage = 0;
-
-    for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current;) {
-        LargeHeapObject<Header>* dead = current;
-        current = current->next();
-        PageMemory* storage = dead->storage();
-        dead->~LargeHeapObject();
-        delete storage;
+        page->clearLiveAndMarkDead();
+    for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current; current = current->next()) {
+        if (current->isMarked())
+            current->unmark();
+        else
+            current->setDeadMark();
     }
-    m_firstLargeHeapObject = 0;
 }
 
 template<typename Header>
@@ -1031,7 +1121,7 @@ template<typename Header>
 void HeapPage<Header>::unlink(HeapPage* unused, HeapPage** prevNext)
 {
     *prevNext = unused->m_next;
-    unused->heap()->addPageToPool(unused);
+    unused->heap()->removePageFromHeap(unused);
 }
 
 template<typename Header>
@@ -1097,13 +1187,21 @@ void HeapPage<Header>::sweep()
 }
 
 template<typename Header>
-void HeapPage<Header>::clearMarks()
+void HeapPage<Header>::clearLiveAndMarkDead()
 {
     for (Address headerAddress = payload(); headerAddress < end();) {
         Header* header = reinterpret_cast<Header*>(headerAddress);
         ASSERT(header->size() < blinkPagePayloadSize());
-        if (!header->isFree())
+        // Check if a free list entry first since we cannot call
+        // isMarked on a free list entry.
+        if (header->isFree()) {
+            headerAddress += header->size();
+            continue;
+        }
+        if (header->isMarked())
             header->unmark();
+        else
+            header->setDeadMark();
         headerAddress += header->size();
     }
 }
@@ -1183,7 +1281,7 @@ void HeapPage<Header>::checkAndMarkPointer(Visitor* visitor, Address address)
 {
     ASSERT(contains(address));
     Header* header = findHeaderFromAddress(address);
-    if (!header)
+    if (!header || header->hasDeadMark())
         return;
 
 #if ENABLE(GC_TRACING)
@@ -1371,6 +1469,7 @@ bool CallbackStack::isEmpty()
     return m_current == &(m_buffer[0]) && !m_next;
 }
 
+template<GCMode Mode>
 bool CallbackStack::popAndInvokeCallback(CallbackStack** first, Visitor* visitor)
 {
     if (m_current == &(m_buffer[0])) {
@@ -1383,10 +1482,31 @@ bool CallbackStack::popAndInvokeCallback(CallbackStack** first, Visitor* visitor
         CallbackStack* nextStack = m_next;
         *first = nextStack;
         delete this;
-        return nextStack->popAndInvokeCallback(first, visitor);
+        return nextStack->popAndInvokeCallback<Mode>(first, visitor);
     }
     Item* item = --m_current;
 
+    // If the object being traced is located on a page which is dead don't
+    // trace it. This can happen when a conservative GC kept a dead object
+    // alive which pointed to a (now gone) object on the cleaned up page.
+    // Also if doing a thread local GC don't trace objects that are located
+    // on other thread's heaps, ie. pages where the shuttingDown flag is not
+    // set.
+    BaseHeapPage* heapPage = pageHeaderFromObject(item->object());
+    if (heapPage->orphaned() || (Mode == ThreadLocalGC && !heapPage->shuttingDown())) {
+        // When doing a GC we should only get a trace callback to an orphaned
+        // page if the GC is conservative. If it is not conservative there is
+        // a bug in the code where we have a dangling pointer to a page
+        // on the dead thread.
+        RELEASE_ASSERT(!heapPage->orphaned() || Heap::lastGCWasConservative());
+
+        if (Mode == GlobalGC) {
+            // If tracing this from a global GC set the traced bit.
+            heapPage->setTraced();

[haraken, 2014/07/09 08:01:59]

We'll need the tracing flag only on orphaned pages. Can we change the condition
to:

  if (Mode == GlobalGC && heapPage->orphaned())

?

Slightly better:

// Comment
RELEASE_ASSERT(!heapPage->orphaned() || Heap::lastGCWasConservative());

// Comment
if (Mode == ThreadLocalGC && !heapPage->shuttingDown())
  return true;

// Comment
if (Mode == GlobalGC && heapPage->orphaned()) {
  heapPage->setTraced();
  retun true;
}

[wibling-chromium, 2014/07/09 10:32:31]

We also need to ignore the traceCallback when doing a thread local GC for
orphaned pages. Ie. the case where Mode == ThreadLocalGC &&
heapPage->orphaned(). This can happen when a previous ThreadLocal GC add an
empty page to the orphaned page pool.

We could change it to:

if (Mode == GlobalGC && heapPage->orphaned()) {
   heapPage->setTraced();
   return true;
}
if (Mode == ThreadLocalGC && (heapPage->orphaned || !heapPage->shuttingDown()))
   return true;

I would also prefer to keep the release assert under the ifs since we don't want
to do additional checks in release mode if not needed. I am not confident the
above is better, but it might be slightly simpler to reason about.

+        }
+        return true;
+    }
+
     VisitorCallback callback = item->callback();
 #if ENABLE(GC_TRACING)
     if (ThreadState::isAnyThreadInGC()) // weak-processing will also use popAndInvokeCallback
@@ -1397,6 +1517,7 @@ bool CallbackStack::popAndInvokeCallback(CallbackStack** first, Visitor* visitor
     return true;
 }
 
+template<GCMode Mode>
 void CallbackStack::invokeCallbacks(CallbackStack** first, Visitor* visitor)
 {
     CallbackStack* stack = 0;
@@ -1409,21 +1530,35 @@ void CallbackStack::invokeCallbacks(CallbackStack** first, Visitor* visitor)
     // a second time.
     while (stack != *first) {
         stack = *first;
-        stack->invokeOldestCallbacks(visitor);
+        stack->invokeOldestCallbacks<Mode>(visitor);
     }
 }
 
+template<GCMode Mode>
 void CallbackStack::invokeOldestCallbacks(Visitor* visitor)
 {
     // Recurse first (bufferSize at a time) so we get to the newly added entries
     // last.
     if (m_next)
-        m_next->invokeOldestCallbacks(visitor);
+        m_next->invokeOldestCallbacks<Mode>(visitor);
 
     // This loop can tolerate entries being added by the callbacks after
     // iteration starts.
     for (unsigned i = 0; m_buffer + i < m_current; i++) {
         Item& item = m_buffer[i];
+
+        BaseHeapPage* heapPage = pageHeaderFromObject(item.object());
+        if (heapPage->orphaned() || (Mode == ThreadLocalGC && !heapPage->shuttingDown())) {
+            // We should only get a trace callback to an orphaned page if doing
+            // a conservative GC. If not conservative there is a bug in the code
+            // where we have a dangling pointer to a page on the dead thread.
+            RELEASE_ASSERT(Heap::lastGCWasConservative());
+
+            // If tracing this from a global GC set the traced bit.
+            if (Mode == GlobalGC)
+                heapPage->setTraced();

[haraken, 2014/07/09 08:01:59]

Ditto. We might want to restructure the branches as suggested above.

+            continue;
+        }
         item.callback()(visitor, item.object());
     }
 }
@@ -1676,6 +1811,8 @@ void Heap::init()
     CallbackStack::init(&s_ephemeronStack);
     s_heapDoesNotContainCache = new HeapDoesNotContainCache();
     s_markingVisitor = new MarkingVisitor();
+    s_freePagePool = new FreePagePool();
+    s_orphanedPagePool = new OrphanedPagePool();
 }
 
 void Heap::shutdown()
@@ -1696,6 +1833,10 @@ void Heap::doShutdown()
     s_markingVisitor = 0;
     delete s_heapDoesNotContainCache;
     s_heapDoesNotContainCache = 0;
+    delete s_freePagePool;
+    s_freePagePool = 0;
+    delete s_orphanedPagePool;
+    s_orphanedPagePool = 0;
     CallbackStack::shutdown(&s_weakCallbackStack);
     CallbackStack::shutdown(&s_markingStack);
     CallbackStack::shutdown(&s_ephemeronStack);
@@ -1714,6 +1855,13 @@ BaseHeapPage* Heap::contains(Address address)
     return 0;
 }
 
+#ifndef NDEBUG
+bool Heap::containedInHeapOrOrphanedPage(void* object)
+{
+    return contains(object) || orphanedPagePool()->contains(object);
+}
+#endif
+
 Address Heap::checkAndMarkPointer(Visitor* visitor, Address address)
 {
     ASSERT(ThreadState::isAnyThreadInGC());
@@ -1792,14 +1940,15 @@ String Heap::createBacktraceString()
 
 void Heap::pushTraceCallback(void* object, TraceCallback callback)
 {
-    ASSERT(Heap::contains(object));
+    ASSERT(Heap::containedInHeapOrOrphanedPage(object));
     CallbackStack::Item* slot = s_markingStack->allocateEntry(&s_markingStack);
     *slot = CallbackStack::Item(object, callback);
 }
 
+template<GCMode Mode>
 bool Heap::popAndInvokeTraceCallback(Visitor* visitor)
 {
-    return s_markingStack->popAndInvokeCallback(&s_markingStack, visitor);
+    return s_markingStack->popAndInvokeCallback<Mode>(&s_markingStack, visitor);
 }
 
 void Heap::pushWeakCellPointerCallback(void** cell, WeakPointerCallback callback)
@@ -1812,7 +1961,7 @@ void Heap::pushWeakCellPointerCallback(void** cell, WeakPointerCallback callback
 void Heap::pushWeakObjectPointerCallback(void* closure, void* object, WeakPointerCallback callback)
 {
     ASSERT(Heap::contains(object));
-    BaseHeapPage* heapPageForObject = reinterpret_cast<BaseHeapPage*>(pageHeaderAddress(reinterpret_cast<Address>(object)));
+    BaseHeapPage* heapPageForObject = pageHeaderFromObject(object);
     ASSERT(Heap::contains(object) == heapPageForObject);
     ThreadState* state = heapPageForObject->threadState();
     state->pushWeakObjectPointerCallback(closure, callback);
@@ -1820,7 +1969,7 @@ void Heap::pushWeakObjectPointerCallback(void* closure, void* object, WeakPointe
 
 bool Heap::popAndInvokeWeakPointerCallback(Visitor* visitor)
 {
-    return s_weakCallbackStack->popAndInvokeCallback(&s_weakCallbackStack, visitor);
+    return s_weakCallbackStack->popAndInvokeCallback<GlobalGC>(&s_weakCallbackStack, visitor);
 }
 
 void Heap::registerWeakTable(void* table, EphemeronCallback iterationCallback, EphemeronCallback iterationDoneCallback)
@@ -1879,16 +2028,67 @@ void Heap::collectGarbage(ThreadState::StackState stackState)
 
     prepareForGC();
 
-    ThreadState::visitRoots(s_markingVisitor);
+    traceRootsAndPerformGlobalWeakProcessing<GlobalGC>();
+
+    // After a global marking we know that any orphaned page that was not reached
+    // cannot be reached in a subsequent GC. This is due to a thread either having
+    // swept its heap or having done a "poor mans sweep" in prepareForGC which marks
+    // objects that are dead, but not swept in the previous GC as dead. In this GC's
+    // marking we check that any object marked as dead is not traced. E.g. via a
+    // conservatively found pointer or a programming error with an object containing
+    // a dangling pointer.
+    orphanedPagePool()->decommitOrphanedPages();
+
+#if ENABLE(GC_TRACING)
+    static_cast<MarkingVisitor*>(s_markingVisitor)->reportStats();
+#endif
+
+    if (blink::Platform::current()) {
+        uint64_t objectSpaceSize;
+        uint64_t allocatedSpaceSize;
+        getHeapSpaceSize(&objectSpaceSize, &allocatedSpaceSize);
+        blink::Platform::current()->histogramCustomCounts("BlinkGC.CollectGarbage", WTF::currentTimeMS() - timeStamp, 0, 10 * 1000, 50);
+        blink::Platform::current()->histogramCustomCounts("BlinkGC.TotalObjectSpace", objectSpaceSize / 1024, 0, 4 * 1024 * 1024, 50);
+        blink::Platform::current()->histogramCustomCounts("BlinkGC.TotalAllocatedSpace", allocatedSpaceSize / 1024, 0, 4 * 1024 * 1024, 50);
+    }
+}
+
+void Heap::collectGarbageForTerminatingThread(ThreadState* state)
+{
+    // We explicitly do not enter a safepoint while doing thread specific
+    // garbage collection since we don't want to allow a global GC at the
+    // same time as a thread local GC.
+
+    {
+        NoAllocationScope<AnyThread> noAllocationScope;
+
+        state->enterGC();
+        state->prepareForGC();
+
+        traceRootsAndPerformGlobalWeakProcessing<ThreadLocalGC>();

[haraken, 2014/07/09 08:01:59]

traceRootsAndPerform"Global"WeakProcessing sounds a bit confusing with a global
GC. traceRootsAndPerformBuiltInWeakProcessing ?

[wibling-chromium, 2014/07/09 10:32:31]

I agree GlobalWeakProcessing is a bit confusing, but I actually prefer it over
BuiltInWeakProcessing since BuiltIn is not a term we have used elsewhere to
describe the global weak processing.

+
+        state->leaveGC();
+    }
+    state->performPendingSweep();
+}
+
+template<GCMode Mode>
+void Heap::traceRootsAndPerformGlobalWeakProcessing()
+{
+    if (Mode == ThreadLocalGC)
+        ThreadState::current()->visitLocalRoots(s_markingVisitor);
+    else
+        ThreadState::visitRoots(s_markingVisitor);
 
     // Ephemeron fixed point loop.
     do {
-        // Recursively mark all objects that are reachable from the roots.
-        while (popAndInvokeTraceCallback(s_markingVisitor)) { }
+        // Recursively mark all objects that are reachable from the roots for this thread.
+        // Also don't continue tracing if the trace hits an object on another thread's heap.
+        while (popAndInvokeTraceCallback<Mode>(s_markingVisitor)) { }
 
         // Mark any strong pointers that have now become reachable in ephemeron
         // maps.
-        CallbackStack::invokeCallbacks(&s_ephemeronStack, s_markingVisitor);
+        CallbackStack::invokeCallbacks<Mode>(&s_ephemeronStack, s_markingVisitor);
 
         // Rerun loop if ephemeron processing queued more objects for tracing.
     } while (!s_markingStack->isEmpty());
@@ -1904,19 +2104,6 @@ void Heap::collectGarbage(ThreadState::StackState stackState)
     // It is not permitted to trace pointers of live objects in the weak
     // callback phase, so the marking stack should still be empty here.
     ASSERT(s_markingStack->isEmpty());
-
-#if ENABLE(GC_TRACING)
-    static_cast<MarkingVisitor*>(s_markingVisitor)->reportStats();
-#endif
-
-    if (blink::Platform::current()) {
-        uint64_t objectSpaceSize;
-        uint64_t allocatedSpaceSize;
-        getHeapSpaceSize(&objectSpaceSize, &allocatedSpaceSize);
-        blink::Platform::current()->histogramCustomCounts("BlinkGC.CollectGarbage", WTF::currentTimeMS() - timeStamp, 0, 10 * 1000, 50);
-        blink::Platform::current()->histogramCustomCounts("BlinkGC.TotalObjectSpace", objectSpaceSize / 1024, 0, 4 * 1024 * 1024, 50);
-        blink::Platform::current()->histogramCustomCounts("BlinkGC.TotalAllocatedSpace", allocatedSpaceSize / 1024, 0, 4 * 1024 * 1024, 50);
-    }
 }
 
 void Heap::collectAllGarbage()
@@ -1935,6 +2122,17 @@ void Heap::setForcePreciseGCForTesting()
     ThreadState::current()->setForcePreciseGCForTesting(true);
 }
 
+template<typename Header>
+void ThreadHeap<Header>::prepareHeapForShutdown()
+{
+    for (HeapPage<Header>* page = m_firstPage; page; page = page->next()) {
+        page->setShutdown();
+    }
+    for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current; current = current->next()) {
+        current->setShutdown();
+    }
+}
+
 void Heap::getHeapSpaceSize(uint64_t* objectSpaceSize, uint64_t* allocatedSpaceSize)
 {
     *objectSpaceSize = 0;
@@ -1985,6 +2183,8 @@ template class HeapPage<FinalizedHeapObjectHeader>;
 template class HeapPage<HeapObjectHeader>;
 template class ThreadHeap<FinalizedHeapObjectHeader>;
 template class ThreadHeap<HeapObjectHeader>;
+template bool CallbackStack::popAndInvokeCallback<GlobalGC>(CallbackStack**, Visitor*);
+template bool CallbackStack::popAndInvokeCallback<ThreadLocalGC>(CallbackStack**, Visitor*);
 
 Visitor* Heap::s_markingVisitor;
 CallbackStack* Heap::s_markingStack;
@@ -1993,4 +2193,6 @@ CallbackStack* Heap::s_ephemeronStack;
 HeapDoesNotContainCache* Heap::s_heapDoesNotContainCache;
 bool Heap::s_shutdownCalled = false;
 bool Heap::s_lastGCWasConservative = false;
+FreePagePool* Heap::s_freePagePool;
+OrphanedPagePool* Heap::s_orphanedPagePool;
 }