Simplify and speed up address-to-page cache for conservative stack scanning.

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 391 matching lines @@
     return heapObjectHeader()->unmark();
 }
 
 template<typename Header>
 bool LargeHeapObject<Header>::isMarked()
 {
     return heapObjectHeader()->isMarked();
 }
 
 template<typename Header>
-bool LargeHeapObject<Header>::checkAndMarkPointer(Visitor* visitor, Address address)
+void LargeHeapObject<Header>::checkAndMarkPointer(Visitor* visitor, Address address)
 {
-    if (contains(address)) {
+    ASSERT(contains(address));
+    if (objectContains(address)) {
 #if ENABLE(GC_TRACING)
         visitor->setHostInfo(&address, "stack");
 #endif
         mark(visitor);
-        return true;
     }
-    return false;
 }
 
 template<>
 void LargeHeapObject<FinalizedHeapObjectHeader>::mark(Visitor* visitor)
 {
     if (heapObjectHeader()->hasVTable() && !vTableInitialized(payload()))
         visitor->markConservatively(heapObjectHeader());
     else
         visitor->mark(heapObjectHeader(), heapObjectHeader()->traceCallback());
 }
@@ skipping 102 matching lines @@
     RELEASE_ASSERT(success);
 }
 
 template<typename Header>
 BaseHeapPage* ThreadHeap<Header>::heapPageFromAddress(Address address)
 {
     for (HeapPage<Header>* page = m_firstPage; page; page = page->next()) {
         if (page->contains(address))
             return page;
     }
-    return 0;
-}
-
-template<typename Header>
-BaseHeapPage* ThreadHeap<Header>::largeHeapObjectFromAddress(Address address)
-{
     for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current; current = current->next()) {
+        ASSERT(reinterpret_cast<Address>(current) == roundToBlinkPageStart(reinterpret_cast<Address>(current)));
         if (current->contains(address))
             return current;
     }
     return 0;
 }
 
 #if ENABLE(GC_TRACING)
 template<typename Header>
 const GCInfo* ThreadHeap<Header>::findGCInfoOfLargeHeapObject(Address address)
 {
     for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current; current = current->next()) {
         if (current->contains(address))
             return current->gcInfo();
     }
     return 0;
 }
 #endif
 
 template<typename Header>
-bool ThreadHeap<Header>::checkAndMarkLargeHeapObject(Visitor* visitor, Address address)
-{
-    for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current; current = current->next()) {
-        if (current->checkAndMarkPointer(visitor, address))
-            return true;
-    }
-    return false;
-}
-
-template<typename Header>
 void ThreadHeap<Header>::addToFreeList(Address address, size_t size)
 {
     ASSERT(heapPageFromAddress(address));
     ASSERT(heapPageFromAddress(address + size - 1));
     ASSERT(size < blinkPagePayloadSize());
     // The free list entries are only pointer aligned (but when we allocate
     // from them we are 8 byte aligned due to the header size).
     ASSERT(!((reinterpret_cast<uintptr_t>(address) + sizeof(Header)) & allocationMask));
     ASSERT(!(size & allocationMask));
     ASAN_POISON_MEMORY_REGION(address, size);
@@ skipping 117 matching lines @@
 {
     PageMemory* storage = unused->storage();
     PagePoolEntry* entry = new PagePoolEntry(storage, m_pagePool);
     m_pagePool = entry;
     storage->decommit();
 }
 
 template<typename Header>
 void ThreadHeap<Header>::allocatePage(const GCInfo* gcInfo)
 {
-    heapContainsCache()->flush();
+    Heap::flushNotInHeapCache();
     PageMemory* pageMemory = takePageFromPool();
     if (!pageMemory) {
         pageMemory = PageMemory::allocate(blinkPagePayloadSize());
         RELEASE_ASSERT(pageMemory);
     }
     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
@@ skipping 41 matching lines @@
             page = page->next();
             HeapPage<Header>::unlink(unused, previous);
             pagesRemoved = true;
         } else {
             page->sweep();
             previous = &page->m_next;
             page = page->next();
         }
     }
     if (pagesRemoved)
         heapContainsCache()->flush();

[haraken, 2014/05/08 05:44:58]

For consistency, let's define flushHeapContainsCache().

[Erik Corry, 2014/05/08 09:26:08]

Done, but it doesn't make it very consistent with flushNotInHeapCache. 
flushNotInHeapCache is a static method on Heap, whereas flushHeapContainsCache
is an instance method on ThreadHeap.

 
     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 53 matching lines @@
     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()
 {
     heapContainsCache()->flush();

[haraken, 2014/05/08 05:44:58]

flushHeapContainsCache()

[Erik Corry, 2014/05/08 09:26:08]

Done.

     // 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;
     }
@@ skipping 191 matching lines @@
     objectStartNumber = (mapIndex * 8) + 7 - leadingZeroes;
     objectOffset = objectStartNumber * allocationGranularity;
     Address objectAddress = objectOffset + payload();
     Header* header = reinterpret_cast<Header*>(objectAddress);
     if (header->isFree())
         return 0;
     return header;
 }
 
 template<typename Header>
-bool HeapPage<Header>::checkAndMarkPointer(Visitor* visitor, Address address)
+void HeapPage<Header>::checkAndMarkPointer(Visitor* visitor, Address address)
 {
+    ASSERT(contains(address));
     Header* header = findHeaderFromAddress(address);
     if (!header)
-        return false;
+        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));
-    return true;
 }
 
 #if ENABLE(GC_TRACING)
 template<typename Header>
 const GCInfo* HeapPage<Header>::findGCInfo(Address address)
 {
     if (address < payload())
         return 0;
 
     if (gcInfo()) // for non FinalizedObjectHeader
@@ skipping 61 matching lines @@
     return header->hasVTable();
 }
 
 template<typename Header>
 void LargeHeapObject<Header>::getStats(HeapStats& stats)
 {
     stats.increaseAllocatedSpace(size());
     stats.increaseObjectSpace(payloadSize());
 }
 
-HeapContainsCache::HeapContainsCache()
-    : m_entries(adoptArrayPtr(new Entry[HeapContainsCache::numberOfEntries]))
+template<typename Entry>
+void HeapExtentCache<Entry>::flush()
 {
+    if (m_hasEntries) {
+        for (int i = 0; i < numberOfEntries; i++)
+            m_entries[i] = Entry();
+        m_hasEntries = false;
+    }
 }
 
-void HeapContainsCache::flush()
-{
-    for (int i = 0; i < numberOfEntries; i++)
-        m_entries[i] = Entry();
-}
-
-size_t HeapContainsCache::hash(Address address)
+template<typename Entry>
+size_t HeapExtentCache<Entry>::hash(Address address)
 {
     size_t value = (reinterpret_cast<size_t>(address) >> blinkPageSizeLog2);
     value ^= value >> numberOfEntriesLog2;
     value ^= value >> (numberOfEntriesLog2 * 2);
     value &= numberOfEntries - 1;
     return value & ~1; // Returns only even number.
 }
 
-bool HeapContainsCache::lookup(Address address, BaseHeapPage** page)
-{
-    ASSERT(page);
-    size_t index = hash(address);
-    ASSERT(!(index & 1));
-    Address cachePage = roundToBlinkPageStart(address);
-    if (m_entries[index].address() == cachePage) {
-        *page = m_entries[index].containingPage();
-        return true;
-    }
-    if (m_entries[index + 1].address() == cachePage) {
-        *page = m_entries[index + 1].containingPage();
-        return true;
-    }
-    *page = 0;
-    return false;
-}
-
-void HeapContainsCache::addEntry(Address address, BaseHeapPage* page)
+template<typename Entry>
+typename Entry::LookupResult HeapExtentCache<Entry>::lookup(Address address)
 {
     size_t index = hash(address);
     ASSERT(!(index & 1));
     Address cachePage = roundToBlinkPageStart(address);
+    if (m_entries[index].address() == cachePage)
+        return m_entries[index].result();
+    if (m_entries[index + 1].address() == cachePage)
+        return m_entries[index + 1].result();
+    return 0;
+}
+
+template<typename Entry>
+void HeapExtentCache<Entry>::addEntry(Address address, typename Entry::LookupResult entry)
+{
+    m_hasEntries = true;
+    size_t index = hash(address);
+    ASSERT(!(index & 1));
+    Address cachePage = roundToBlinkPageStart(address);
     m_entries[index + 1] = m_entries[index];
-    m_entries[index] = Entry(cachePage, page);
+    m_entries[index] = Entry(cachePage, entry);
+}
+
+// These should not be needed, but it seems impossible to persuade clang to
+// instantiate the template functions and export them from a shared library, so
+// we add these in the non-templated subclass, which does not have that issue.
+void HeapContainsCache::addEntry(Address address, BaseHeapPage* page)
+{
+    HeapExtentCache<PositiveEntry>::addEntry(address, page);
+}
+
+BaseHeapPage* HeapContainsCache::lookup(Address address)
+{
+    return HeapExtentCache<PositiveEntry>::lookup(address);
+}
+
+bool Heap::notInHeap(Address address)
+{
+    return s_notInHeapCache->lookup(address);
+}
+
+void Heap::addressIsNotInHeap(Address address)
+{
+    s_notInHeapCache->addEntry(address, true);
+}
+
+void Heap::flushNotInHeapCache()
+{
+    s_notInHeapCache->flush();
 }
 
 void CallbackStack::init(CallbackStack** first)
 {
     // The stacks are chained, so we start by setting this to null as terminator.
     *first = 0;
     *first = new CallbackStack(first);
 }
 
 void CallbackStack::shutdown(CallbackStack** first)
@@ skipping 253 matching lines @@
     {
         Heap::pushWeakCellPointerCallback(cell, callback);
     }
 };
 
 void Heap::init()
 {
     ThreadState::init();
     CallbackStack::init(&s_markingStack);
     CallbackStack::init(&s_weakCallbackStack);
+    s_notInHeapCache = new HeapDoesNotContainCache();
     s_markingVisitor = new MarkingVisitor();
 }
 
 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_notInHeapCache;
+    s_notInHeapCache = 0;
     CallbackStack::shutdown(&s_weakCallbackStack);
     CallbackStack::shutdown(&s_markingStack);
     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;
 }
 
 Address Heap::checkAndMarkPointer(Visitor* visitor, Address address)
 {
     ASSERT(ThreadState::isAnyThreadInGC());
-    if (!address)
+    if (reinterpret_cast<uintptr_t>(address) < blinkPageSize)

[haraken, 2014/05/08 05:44:58]

What is this change for?

[Mads Ager (chromium), 2014/05/08 06:52:37]

This is an optimization to quickly filter out small integers (which occur pretty
frequently in stack frames). Could you add a comment stating that?

[Erik Corry, 2014/05/08 09:26:08]

You can't allocate at address 0, so no allocation can take place in the first
page (pages are aligned).

I moved the negative cache lookup here instead of having it in the ThreadState. 
That makes this test unnecessary.

[Erik Corry, 2014/05/08 09:26:08]

Removed instead.

         return 0;
 
     ThreadState::AttachedThreadStateSet& threads = ThreadState::attachedThreads();
     for (ThreadState::AttachedThreadStateSet::iterator it = threads.begin(), end = threads.end(); it != end; ++it) {
         if ((*it)->checkAndMarkPointer(visitor, address)) {
             // Pointer found and marked.
             return address;
         }
     }
     return 0;
@@ skipping 146 matching lines @@
 
 // Force template instantiations for the types that we need.
 template class HeapPage<FinalizedHeapObjectHeader>;
 template class HeapPage<HeapObjectHeader>;
 template class ThreadHeap<FinalizedHeapObjectHeader>;
 template class ThreadHeap<HeapObjectHeader>;
 
 Visitor* Heap::s_markingVisitor;
 CallbackStack* Heap::s_markingStack;
 CallbackStack* Heap::s_weakCallbackStack;
+HeapDoesNotContainCache* Heap::s_notInHeapCache;
 bool Heap::s_shutdownCalled = false;
 }