[oilpan]: Make thread shutdown more robust.

Source/platform/heap/Heap.cpp

 /*
  * Copyright (C) 2013 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
  * met:
  *
  *     * Redistributions of source code must retain the above copyright
  * notice, this list of conditions and the following disclaimer.
  *     * Redistributions in binary form must reproduce the above
@@ skipping 404 matching lines @@
 }
 
 NO_SANITIZE_ADDRESS
 void HeapObjectHeader::unmark()
 {
     checkHeader();
     m_size &= ~markBitMask;
 }
 
 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
 NO_SANITIZE_ADDRESS
 void HeapObjectHeader::zapMagic()
 {
     m_magic = zappedMagic;
 }
 #endif
 
@@ skipping 39 matching lines @@
     return heapObjectHeader()->unmark();
 }
 
 template<typename Header>
 bool LargeHeapObject<Header>::isMarked()
 {
     return heapObjectHeader()->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");
 #endif
     mark(visitor);
 }
 
 template<>
 void LargeHeapObject<FinalizedHeapObjectHeader>::mark(Visitor* visitor)
 {
@@ skipping 28 matching lines @@
 
 FinalizedHeapObjectHeader* FinalizedHeapObjectHeader::fromPayload(const void* payload)
 {
     Address addr = reinterpret_cast<Address>(const_cast<void*>(payload));
     FinalizedHeapObjectHeader* header =
         reinterpret_cast<FinalizedHeapObjectHeader*>(addr - finalizedHeaderSize);
     return header;
 }
 
 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();
 }
 
 template<typename Header>
 ThreadHeap<Header>::~ThreadHeap()
 {
     clearFreeLists();
-    if (!ThreadState::current()->isMainThread())
-        assertEmpty();
-    deletePages();
+    flushHeapContainsCache();

[haraken, 2014/07/08 05:44:51]

Don't you need to flush HeapDoesNotContainCache as well?

[wibling-chromium, 2014/07/08 13:39:45]

No, we only need to flush the HeapDoesNotContainCache when adding pages to a
heap. Removing a page only means we have something that is removed and not in
the cache. It will then be added to cache if we try looking it up.
The reverse is the case for the HeapContainsCache. Here we only need to flush
when removing a page from a heap, ie. during shutdown.

+
+    // 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);
+    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>
 Address ThreadHeap<Header>::outOfLineAllocate(size_t size, const GCInfo* gcInfo)
 {
     size_t allocationSize = allocationSizeFromSize(size);
     if (threadState()->shouldGC()) {
         if (threadState()->shouldForceConservativeGC())
             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
         else
@@ skipping 149 matching lines @@
 void ThreadHeap<Header>::freeLargeObject(LargeHeapObject<Header>* object, LargeHeapObject<Header>** previousNext)
 {
     flushHeapContainsCache();
     object->unlink(previousNext);
     object->finalize();
 
     // Unpoison the object header and allocationGranularity bytes after the
     // 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()) {
+        // 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 revived in the

[Mads Ager (chromium), 2014/07/08 08:24:56]

revived -> traced

[wibling-chromium, 2014/07/08 13:39:46]

Done.

+        // next global GC either due to a dead object being revived via a

[Mads Ager (chromium), 2014/07/08 08:24:55]

revived -> traced

[wibling-chromium, 2014/07/08 13:39:46]

Done.

+        // conservative pointer or due to a programming error where an object
+        // in another thread heap keeps a dangling pointer to the this object.

[haraken, 2014/07/08 05:44:50]

the this object => this object

[wibling-chromium, 2014/07/08 13:39:45]

Done.

+        // To guard agains this we put the large object memory in the

[haraken, 2014/07/08 05:44:50]

against

[wibling-chromium, 2014/07/08 13:39:46]

Done.

+        // orphanedPagePool to ensure it is still reachable. After the next full
+        // GC it can be released assuming no rogue/dangling pointers refer to

[haraken, 2014/07/08 05:44:51]

full GC => global GC

[wibling-chromium, 2014/07/08 13:39:46]

Done.

+        // it.
+        // NOTE: large objects are not moved to the memory pool as it is unlikely
+        // 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<typename DataType>
+HeapPool<DataType>::HeapPool()
+{
+    for (int i = 0; i < NumberOfHeaps; ++i) {
+        m_pool[i] = 0;
+    }
+}
+
+HeapMemoryPool::~HeapMemoryPool()
+{
+    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;
+        }
+    }
+}
+
+void HeapMemoryPool::addMemory(int index, PageMemory* memory)
+{
+    // When adding memory 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/08 05:44:51]

Just help me understand: Why do we need a mutex here? I was thinking that
HeapMemoryPool is per-thread to guarantee that virtual memory address is not
shared among threads.

[wibling-chromium, 2014/07/08 13:39:46]

I have changed the page pool to be global. The reason being that we could not
reuse any orphaned pages if not and it also guarantees that no virtual address
space will be reused for another object type even after a thread shuts down. See
my reply to Mads on this as well for some more details.

+    PoolEntry* entry = new PoolEntry(memory, m_pool[index]);
+    m_pool[index] = entry;
+}
+
+PageMemory* HeapMemoryPool::takeMemory(int index)
+{
+    MutexLocker locker(m_mutex[index]);
+    while (PoolEntry* entry = m_pool[index]) {
+        m_pool[index] = entry->next;
+        PageMemory* memory = entry->data;
+        ASSERT(memory);
+        delete entry;
+        if (memory->commit())
+            return memory;
+
+        // We got some memory, but failed to commit it, try again.
+        delete memory;
+    }
+    return 0;
+}
+
+HeapOrphanedPagePool::~HeapOrphanedPagePool()
+{
+    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;
+        }
+    }
+}
+
+void HeapOrphanedPagePool::addOrphanedPage(int index, BaseHeapPage* page)

[Mads Ager (chromium), 2014/07/08 08:24:56]

For these methods we know that some mutex is already held so that only one
thread can modify the orphaned page pool at a time, right?

[wibling-chromium, 2014/07/08 13:39:46]

Yes, basically we only add pages to the orphaned page pool during a thread local
GC which there can only be one of at a time and we also guarantee that no global
GC is currently decommiting any orphaned pages at this point since there can be
no global GC when doing a thread local GC.

+{
+    page->markOrphaned();
+    PoolEntry* entry = new PoolEntry(page, m_pool[index]);
+    m_pool[index] = entry;
+}
+
+void HeapOrphanedPagePool::addOrphanedPages(int index, Vector<BaseHeapPage*>& pages)
+{
+    for (Vector<BaseHeapPage*>::const_iterator it = pages.begin(); it != pages.end(); ++it) {
+        addOrphanedPage(index, *it);
+    }
+}
+
+void HeapOrphanedPagePool::decommitOrphanedPages()
+{
+    // No locking needed as all threads are at safepoints at this point in time.

[haraken, 2014/07/08 05:44:51]

Can we add an ASSERT about this?

[wibling-chromium, 2014/07/08 13:39:46]

Done.

+    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();
+                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.
+            PageMemory* memory = page->storage();
+
+            // Call the destructor before freeing or adding to the memory pool.

[haraken, 2014/07/08 05:44:50]

Just help me understand: Why does this order matter?

[wibling-chromium, 2014/07/08 13:39:46]

We cannot call the destructor after adding the memory to the page pool (or
deleting it) since in the former case the memory backing the BaseHeapPage is
decommited and in the latter it is freed.
That said we right now don't do anything in the page destructor, but it seemed
like the right thing to ensure it is called in case we add something that needs
destruction in the future.

+            if (page->reuseMemory()) {

[haraken, 2014/07/08 05:44:50]

reuseMemory => shouldReuseMemory ?

[Mads Ager (chromium), 2014/07/08 08:24:56]

!page->isLargeObject()

[wibling-chromium, 2014/07/08 13:39:45]

Done.

+                page->~BaseHeapPage();
+                Heap::memoryPool()->addMemory(index, memory);

[Mads Ager (chromium), 2014/07/08 08:24:55]

So this is where we use that the page pool is now global. We could keep the page
pool thread local and then always delete the pages here. That would avoid the
mutex when you want to add pages to the page pool and get pages from the page
pool.

[wibling-chromium, 2014/07/08 13:39:45]

Yes, I would like to keep it global for now and in the case it becomes a
performance issue we can make it local to the threads and get rid of the lock.

+            } else {
+                page->~BaseHeapPage();
+                delete memory;
+            }
+
+            PoolEntry* deadEntry = entry;
+            entry = entry->next;
+            *prevNext = entry;
+            delete deadEntry;
+        }
+    }
+}
+
+bool HeapOrphanedPagePool::contains(void* object)

[haraken, 2014/07/08 05:44:50]

Just to confirm: HeapOrphanedPagePool::contains() is not called in a hot call
path, right? If it's called from a hot call path, we might want to put the
result into HeapContainsCache.

[wibling-chromium, 2014/07/08 13:39:46]

No, it is only called inside an ASSERT. I will wrap it in #ifndef NDEBUG.

+{
+    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>::clearPagePool()
-{
-    while (takePageFromPool()) { }
-}
-
-template<typename Header>
-PageMemory* ThreadHeap<Header>::takePageFromPool()
-{
-    Heap::flushHeapDoesNotContainCache();
-    while (PagePoolEntry* entry = m_pagePool) {
-        m_pagePool = entry->next();
-        PageMemory* storage = entry->storage();
-        delete entry;
-
-        if (storage->commit())
-            return storage;
-
-        // Failed to commit pooled storage. Release it.
-        delete storage;
-    }
-
-    return 0;
-}
-
-template<typename Header>
-void ThreadHeap<Header>::addPageMemoryToPool(PageMemory* storage)
+template <typename Header>
+void ThreadHeap<Header>::removePageFromHeap(HeapPage<Header>* page)
 {
     flushHeapContainsCache();
-    PagePoolEntry* entry = new PagePoolEntry(storage, m_pagePool);
-    m_pagePool = entry;
-}
-
-template <typename Header>
-void ThreadHeap<Header>::addPageToPool(HeapPage<Header>* page)
-{
-    PageMemory* storage = page->storage();
-    storage->decommit();
-    addPageMemoryToPool(storage);
+    if (page->shuttingDown()) {
+        // 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 revived in the

[Mads Ager (chromium), 2014/07/08 08:24:55]

revived -> accessed

[wibling-chromium, 2014/07/08 13:39:45]

Done.

+        // next global GC either due to a dead object being revived via a

[Mads Ager (chromium), 2014/07/08 08:24:56]

revived -> traced

[wibling-chromium, 2014/07/08 13:39:46]

Done.

+        // conservative pointer or due to a programming error where an object
+        // in another thread heap keeps a dangling pointer to the this object.

[haraken, 2014/07/08 05:44:51]

the this object => this object

[wibling-chromium, 2014/07/08 13:39:46]

Done.

+        // To guard agains this we put the page in the orphanedPagePool to

[haraken, 2014/07/08 05:44:50]

against

[wibling-chromium, 2014/07/08 13:39:45]

Done.

+        // ensure it is still reachable. After the next full GC it can be

[haraken, 2014/07/08 05:44:51]

full GC => global GC

[wibling-chromium, 2014/07/08 13:39:45]

Done.

+        // decommitted and moved to the memory pool assuming no rogue/dangling
+        // pointers refer to it.
+        Heap::orphanedPagePool()->addOrphanedPage(m_index, page);
+    } else {
+        PageMemory* memory = page->storage();
+        page->~HeapPage<Header>();
+        Heap::memoryPool()->addMemory(m_index, memory);
+    }
 }
 
 template<typename Header>
 void ThreadHeap<Header>::allocatePage(const GCInfo* gcInfo)
 {
     Heap::flushHeapDoesNotContainCache();
-    PageMemory* pageMemory = takePageFromPool();
-    if (!pageMemory) {
+    PageMemory* pageMemory = Heap::memoryPool()->takeMemory(m_index);
+    while (!pageMemory) {

[haraken, 2014/07/08 05:44:50]

I'm curious why we need change 'if' to 'while'?

[Mads Ager (chromium), 2014/07/08 08:24:55]

Because the page pool is not global and other threads could have stolen the
pages that we just added. I think we might want to keep the page pool thread
local. It is simpler and it will not require us to acquire a mutex to add and
retrieve pages to the pool.

         // Allocate a memory region for blinkPagesPerRegion pages that
         // will each have the following layout.
         //
         //    [ guard os page | ... payload ... | guard os page ]
         //    ^---{ aligned to blink page size }
         PageMemoryRegion* region = PageMemoryRegion::allocate(blinkPageSize * blinkPagesPerRegion, blinkPagesPerRegion);
         // Setup the PageMemory object for each of the pages in the
         // region.
         size_t offset = 0;
         for (size_t i = 0; i < blinkPagesPerRegion; i++) {
-            addPageMemoryToPool(PageMemory::setupPageMemoryInRegion(region, offset, blinkPagePayloadSize()));
+            Heap::memoryPool()->addMemory(m_index, PageMemory::setupPageMemoryInRegion(region, offset, blinkPagePayloadSize()));
             offset += blinkPageSize;
         }
-        pageMemory = takePageFromPool();
-        RELEASE_ASSERT(pageMemory);
+        pageMemory = Heap::memoryPool()->takeMemory(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
     // crucial when performing allocations during finalization because
     // it ensures that those pages are not swept in the current GC
     // round. We should create a separate page list for that to
     // separate out the pages allocated during finalization clearly
     // from the pages currently being swept.
     page->link(&m_firstPage);
     addToFreeList(page->payload(), HeapPage<Header>::payloadSize());
@@ skipping 23 matching lines @@
     ASSERT(isConsistentForGC());
 #if defined(ADDRESS_SANITIZER) && STRICT_ASAN_FINALIZATION_CHECKING
     // When using ASan do a pre-sweep where all unmarked objects are poisoned before
     // calling their finalizer methods. This can catch the cases where one objects
     // finalizer tries to modify another object as part of finalization.
     for (HeapPage<Header>* page = m_firstPage; page; page = page->next())
         page->poisonUnmarkedObjects();
 #endif
     HeapPage<Header>* page = m_firstPage;
     HeapPage<Header>** previous = &m_firstPage;
-    bool pagesRemoved = false;
     while (page) {
         if (page->isEmpty()) {
-            flushHeapContainsCache();

[haraken, 2014/07/08 05:44:50]

Just help me understand: Why can we drop flushHeapContainsCache()?

[Mads Ager (chromium), 2014/07/08 08:24:56]

Because unlink now calls removePageFromHeap which does this.

[wibling-chromium, 2014/07/08 13:39:45]

Yes, it seemed like we did this a bit too many times before. Also having the
flushing happen at the points where we either add (in the
HeapDoesNotContainsCache) or remove (in the HeapContainsCache) seems simpler to
reason about.

             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;) {
         if (current->isMarked()) {
             stats().increaseAllocatedSpace(current->size());
             stats().increaseObjectSpace(current->payloadSize());
             current->unmark();
             previousNext = &current->m_next;
             current = current->next();
         } else {
@@ skipping 54 matching lines @@
 template<typename Header>
 void ThreadHeap<Header>::makeConsistentForGC()
 {
     if (ownsNonEmptyAllocationArea())
         addToFreeList(currentAllocationPoint(), remainingAllocationSize());
     setAllocationPoint(0, 0);
     clearFreeLists();
 }
 
 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();
+        page->clearLiveAndMarkDead();
+    for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current; current = current->next()) {
+        if (current->isMarked())
+            current->unmark();
+        else
+            current->setDeadMark();
+    }
 }
 
 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;
-    }
-    m_firstLargeHeapObject = 0;
-}
-
-template<typename Header>
 void ThreadHeap<Header>::clearFreeLists()
 {
     for (size_t i = 0; i < blinkPageSizeLog2; i++)
         m_freeLists[i] = 0;
 }
 
 int BaseHeap::bucketIndexForSize(size_t size)
 {
     ASSERT(size > 0);
     int index = -1;
@@ skipping 20 matching lines @@
 void HeapPage<Header>::link(HeapPage** prevNext)
 {
     m_next = *prevNext;
     *prevNext = this;
 }
 
 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>
 void HeapPage<Header>::getStats(HeapStats& stats)
 {
     stats.increaseAllocatedSpace(blinkPageSize);
     Address headerAddress = payload();
     ASSERT(headerAddress != end());
     do {
         Header* header = reinterpret_cast<Header*>(headerAddress);
@@ skipping 45 matching lines @@
         header->unmark();
         headerAddress += header->size();
         heap()->stats().increaseObjectSpace(header->payloadSize());
         startOfGap = headerAddress;
     }
     if (startOfGap != end())
         heap()->addToFreeList(startOfGap, end() - startOfGap);
 }
 
 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())
+        // Skip freelist entries.
+        if (header->isFree()) {
+            headerAddress += header->size();
+            continue;
+        }
+        if (header->isMarked())
             header->unmark();
+        else
+            header->setDeadMark();

[haraken, 2014/07/08 05:44:50]

Slightly better:

if (header->isMarked())
  header->unmark();
else if (!header->isFree())
  header->setDeadMark()
headerAddress += header->size();

[wibling-chromium, 2014/07/08 13:39:45]

Done.

         headerAddress += header->size();
     }
 }
 
 template<typename Header>
 void HeapPage<Header>::populateObjectStartBitMap()
 {
     memset(&m_objectStartBitMap, 0, objectStartBitMapSize);
     Address start = payload();
     for (Address headerAddress = start; headerAddress < end();) {
@@ skipping 59 matching lines @@
     if (header->isFree())
         return 0;
     return header;
 }
 
 template<typename Header>
 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)
     visitor->setHostInfo(&address, "stack");
 #endif
     if (hasVTable(header) && !vTableInitialized(header->payload()))
         visitor->markConservatively(header);
     else
         visitor->mark(header, traceCallback(header));
 }
@@ skipping 167 matching lines @@
 {
     for (size_t i = 0; i < bufferSize; i++)
         m_buffer[i] = Item(0, 0);
 }
 
 bool CallbackStack::isEmpty()
 {
     return m_current == &(m_buffer[0]) && !m_next;
 }
 
-bool CallbackStack::popAndInvokeCallback(CallbackStack** first, Visitor* visitor)
-{
-    if (m_current == &(m_buffer[0])) {
-        if (!m_next) {
-#ifndef NDEBUG
-            clearUnused();
-#endif
-            return false;
-        }
-        CallbackStack* nextStack = m_next;
-        *first = nextStack;
-        delete this;
-        return nextStack->popAndInvokeCallback(first, visitor);
-    }
-    Item* item = --m_current;
-
-    VisitorCallback callback = item->callback();
-#if ENABLE(GC_TRACING)
-    if (ThreadState::isAnyThreadInGC()) // weak-processing will also use popAndInvokeCallback
-        visitor->setHostInfo(item->object(), classOf(item->object()));
-#endif
-    callback(visitor, item->object());
-
-    return true;
-}
-
+template<bool ThreadLocal>
 void CallbackStack::invokeCallbacks(CallbackStack** first, Visitor* visitor)
 {
     CallbackStack* stack = 0;
     // The first block is the only one where new ephemerons are added, so we
     // call the callbacks on that last, to catch any new ephemerons discovered
     // in the callbacks.
     // However, if enough ephemerons were added, we may have a new block that
     // has been prepended to the chain. This will be very rare, but we can
     // handle the situation by starting again and calling all the callbacks
     // a second time.
     while (stack != *first) {
         stack = *first;
-        stack->invokeOldestCallbacks(visitor);
+        stack->invokeOldestCallbacks<ThreadLocal>(visitor);
     }
 }
 
+template<bool ThreadLocal>
 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<ThreadLocal>(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 (ThreadLocal ? (heapPage->orphaned() || !heapPage->shuttingDown()) : heapPage->orphaned()) {
+            // If tracing this from a global GC set the traced bit.
+            if (!ThreadLocal)
+                heapPage->setTraced();
+            continue;
+        }
         item.callback()(visitor, item.object());
     }
 }
 
 #ifndef NDEBUG
 bool CallbackStack::hasCallbackForObject(const void* object)
 {
     for (unsigned i = 0; m_buffer + i < m_current; i++) {
         Item* item = &m_buffer[i];
         if (item->object() == object) {
@@ skipping 232 matching lines @@
 };
 
 void Heap::init()
 {
     ThreadState::init();
     CallbackStack::init(&s_markingStack);
     CallbackStack::init(&s_weakCallbackStack);
     CallbackStack::init(&s_ephemeronStack);
     s_heapDoesNotContainCache = new HeapDoesNotContainCache();
     s_markingVisitor = new MarkingVisitor();
+    s_memoryPool = new HeapMemoryPool();
+    s_orphanedPagePool = new HeapOrphanedPagePool();
 }
 
 void Heap::shutdown()
 {
     s_shutdownCalled = true;
     ThreadState::shutdownHeapIfNecessary();
 }
 
 void Heap::doShutdown()
 {
     // We don't want to call doShutdown() twice.
     if (!s_markingVisitor)
         return;
 
     ASSERT(!ThreadState::isAnyThreadInGC());
     ASSERT(!ThreadState::attachedThreads().size());
     delete s_markingVisitor;
     s_markingVisitor = 0;
     delete s_heapDoesNotContainCache;
     s_heapDoesNotContainCache = 0;
+    delete s_memoryPool;
+    s_memoryPool = 0;
+    delete s_orphanedPagePool;
+    s_orphanedPagePool = 0;
     CallbackStack::shutdown(&s_weakCallbackStack);
     CallbackStack::shutdown(&s_markingStack);
     CallbackStack::shutdown(&s_ephemeronStack);
     ThreadState::shutdown();
 }
 
 BaseHeapPage* Heap::contains(Address address)
 {
     ASSERT(ThreadState::isAnyThreadInGC());
     ThreadState::AttachedThreadStateSet& threads = ThreadState::attachedThreads();
     for (ThreadState::AttachedThreadStateSet::iterator it = threads.begin(), end = threads.end(); it != end; ++it) {
         BaseHeapPage* page = (*it)->contains(address);
         if (page)
             return page;
     }
     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());
 
 #ifdef NDEBUG
     if (s_heapDoesNotContainCache->lookup(address))
         return 0;
 #endif
 
     ThreadState::AttachedThreadStateSet& threads = ThreadState::attachedThreads();
@@ skipping 58 matching lines @@
         builder.append("\n\t");
         builder.append(frameToName.nullableName());
         --framesToShow;
     }
     return builder.toString().replace("WebCore::", "");
 }
 #endif
 
 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<bool ThreadLocal>
 bool Heap::popAndInvokeTraceCallback(Visitor* visitor)
 {
-    return s_markingStack->popAndInvokeCallback(&s_markingStack, visitor);
+    return s_markingStack->popAndInvokeCallback<ThreadLocal>(&s_markingStack, visitor);
 }
 
 void Heap::pushWeakCellPointerCallback(void** cell, WeakPointerCallback callback)
 {
     ASSERT(Heap::contains(cell));
     CallbackStack::Item* slot = s_weakCallbackStack->allocateEntry(&s_weakCallbackStack);
     *slot = CallbackStack::Item(cell, 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);
 }
 
 bool Heap::popAndInvokeWeakPointerCallback(Visitor* visitor)
 {
-    return s_weakCallbackStack->popAndInvokeCallback(&s_weakCallbackStack, visitor);
+    return s_weakCallbackStack->popAndInvokeCallback<false>(&s_weakCallbackStack, visitor);

[haraken, 2014/07/08 05:44:51]

We prefer enum than true/false.

[wibling-chromium, 2014/07/08 13:39:45]

Done.

 }
 
 void Heap::registerWeakTable(void* table, EphemeronCallback iterationCallback, EphemeronCallback iterationDoneCallback)
 {
     CallbackStack::Item* slot = s_ephemeronStack->allocateEntry(&s_ephemeronStack);
     *slot = CallbackStack::Item(table, iterationCallback);
 
     // We use the callback stack of weak cell pointers for the ephemeronIterationDone callbacks.
     // These callbacks are called right after marking and before any thread commences execution
     // so it suits our needs for telling the ephemerons that the iteration is done.
@@ skipping 37 matching lines @@
     static_cast<MarkingVisitor*>(s_markingVisitor)->objectGraph().clear();
 #endif
 
     // Disallow allocation during garbage collection (but not
     // during the finalization that happens when the gcScope is
     // torn down).
     NoAllocationScope<AnyThread> noAllocationScope;
 
     prepareForGC();
 
-    ThreadState::visitRoots(s_markingVisitor);
+    tracingAndGlobalWeakProcessing<false>();
+
+    // After a global marking we know that any orphaned page that was not reached
+    // cannot be revived in a subsequent GC. This is due to a thread either having

[Mads Ager (chromium), 2014/07/08 08:24:56]

revived -> reached

[wibling-chromium, 2014/07/08 13:39:46]

Done.

+    // 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 revived. E.g. via a

[Mads Ager (chromium), 2014/07/08 08:24:55]

revived -> traced

[wibling-chromium, 2014/07/08 13:39:46]

Done.

+    // conservatively found pointer or a programming error with an object containing
+    // a dangling pointer.

[haraken, 2014/07/08 05:44:50]

In my understanding, if we're performing a precise GC, orphaned pages must not
be traced. Can we add a RELEASE_ASSERT about the fact? I think the
RELEASE_ASSERT will give us stack traces of the code where we should fix.

[wibling-chromium, 2014/07/08 13:39:45]

That is correct. I will try to add a
RELEASE_ASSERT(Heap::s_lastGCWasConservative) under the orphaned page check,
when popping trace callbacks.

+    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::collectGarbageForThread(ThreadState* state, bool sweepOnly)
+{
+    // 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;

[Mads Ager (chromium), 2014/07/08 08:24:55]

This no allocation scope covers the sweep as well. It shouldn't since we allow
allocation during finalization. While sweeping allocations always succeed so we
will not enter a safe point when allocating during sweeping.

[wibling-chromium, 2014/07/08 13:39:45]

Good point. Fixed.

+
+    state->enterGC();
+    state->prepareForGC();
+
+    if (!sweepOnly)
+        tracingAndGlobalWeakProcessing<true>();
+
+    state->leaveGC();
+    state->performPendingSweep();
+}
+
+template<bool ThreadLocal>
+void Heap::tracingAndGlobalWeakProcessing()
+{
+    if (ThreadLocal)
+        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<ThreadLocal>(s_markingVisitor)) { }
 
         // Mark any strong pointers that have now become reachable in ephemeron
         // maps.
-        CallbackStack::invokeCallbacks(&s_ephemeronStack, s_markingVisitor);
+        CallbackStack::invokeCallbacks<ThreadLocal>(&s_ephemeronStack, s_markingVisitor);
 
         // Rerun loop if ephemeron processing queued more objects for tracing.
     } while (!s_markingStack->isEmpty());
 
     // Call weak callbacks on objects that may now be pointing to dead
     // objects and call ephemeronIterationDone callbacks on weak tables
     // to do cleanup (specifically clear the queued bits for weak hash
     // tables).
     while (popAndInvokeWeakPointerCallback(s_markingVisitor)) { }
 
     CallbackStack::clear(&s_ephemeronStack);
 
     // 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()
 {
     // FIXME: oilpan: we should perform a single GC and everything
     // should die. Unfortunately it is not the case for all objects
     // because the hierarchy was not completely moved to the heap and
     // some heap allocated objects own objects that contain persistents
     // pointing to other heap allocated objects.
     for (int i = 0; i < 5; i++)
         collectGarbage(ThreadState::NoHeapPointersOnStack);
 }
 
 void Heap::setForcePreciseGCForTesting()
 {
     ThreadState::current()->setForcePreciseGCForTesting(true);
 }
 
+template<typename Header>
+void ThreadHeap<Header>::setShutdown()
+{
+    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;
     *allocatedSpaceSize = 0;
     ASSERT(ThreadState::isAnyThreadInGC());
     ThreadState::AttachedThreadStateSet& threads = ThreadState::attachedThreads();
     typedef ThreadState::AttachedThreadStateSet::iterator ThreadStateIterator;
     for (ThreadStateIterator it = threads.begin(), end = threads.end(); it != end; ++it) {
         *objectSpaceSize += (*it)->stats().totalObjectSpace();
         *allocatedSpaceSize += (*it)->stats().totalAllocatedSpace();
@@ skipping 38 matching lines @@
 template class ThreadHeap<FinalizedHeapObjectHeader>;
 template class ThreadHeap<HeapObjectHeader>;
 
 Visitor* Heap::s_markingVisitor;
 CallbackStack* Heap::s_markingStack;
 CallbackStack* Heap::s_weakCallbackStack;
 CallbackStack* Heap::s_ephemeronStack;
 HeapDoesNotContainCache* Heap::s_heapDoesNotContainCache;
 bool Heap::s_shutdownCalled = false;
 bool Heap::s_lastGCWasConservative = false;
+HeapMemoryPool* Heap::s_memoryPool;
+HeapOrphanedPagePool* Heap::s_orphanedPagePool;
 }