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

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 5b702342bc246f69acd99c5af796ea64a2648cc7..86f046683fba9925a085b29444ba897744e23c57 100644
--- a/Source/platform/heap/Heap.cpp
+++ b/Source/platform/heap/Heap.cpp
@@ -409,16 +409,15 @@ bool LargeHeapObject<Header>::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<>
@@ -541,13 +540,8 @@ BaseHeapPage* ThreadHeap<Header>::heapPageFromAddress(Address address)
         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;
     }
@@ -567,16 +561,6 @@ const GCInfo* ThreadHeap<Header>::findGCInfoOfLargeHeapObject(Address address)
 #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));
@@ -714,7 +698,7 @@ void ThreadHeap<Header>::addPageToPool(HeapPage<Header>* unused)
 template<typename Header>
 void ThreadHeap<Header>::allocatePage(const GCInfo* gcInfo)
 {
-    heapContainsCache()->flush();
+    Heap::flushNotInHeapCache();
     PageMemory* pageMemory = takePageFromPool();
     if (!pageMemory) {
         pageMemory = PageMemory::allocate(blinkPagePayloadSize());
@@ -1062,11 +1046,12 @@ Header* HeapPage<Header>::findHeaderFromAddress(Address address)
 }
 
 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");
@@ -1075,7 +1060,6 @@ bool HeapPage<Header>::checkAndMarkPointer(Visitor* visitor, Address address)
         visitor->markConservatively(header);
     else
         visitor->mark(header, traceCallback(header));
-    return true;
 }
 
 #if ENABLE(GC_TRACING)
@@ -1157,18 +1141,18 @@ void LargeHeapObject<Header>::getStats(HeapStats& stats)
     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;
@@ -1177,31 +1161,56 @@ size_t HeapContainsCache::hash(Address address)
     return value & ~1; // Returns only even number.
 }
 
-bool HeapContainsCache::lookup(Address address, BaseHeapPage** page)
+template<typename Entry>
+typename Entry::LookupResult HeapExtentCache<Entry>::lookup(Address address)
 {
-    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;
+    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;
 }
 
-void HeapContainsCache::addEntry(Address address, BaseHeapPage* page)
+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)
@@ -1475,6 +1484,7 @@ void Heap::init()
     ThreadState::init();
     CallbackStack::init(&s_markingStack);
     CallbackStack::init(&s_weakCallbackStack);
+    s_notInHeapCache = new HeapDoesNotContainCache();
     s_markingVisitor = new MarkingVisitor();
 }
 
@@ -1494,6 +1504,8 @@ void Heap::doShutdown()
     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();
@@ -1514,7 +1526,7 @@ BaseHeapPage* Heap::contains(Address address)
 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();
@@ -1681,5 +1693,6 @@ 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;
 }