Oilpan: Replace the positive heap-contains cache with a binary search tree of memory regions.

Source/platform/heap/ThreadState.cpp

Index: Source/platform/heap/ThreadState.cpp
diff --git a/Source/platform/heap/ThreadState.cpp b/Source/platform/heap/ThreadState.cpp
index d3bc5cf73f62b1ae1a609758caa3d729b47f007e..55fe5ba893ddeec96071a86f031bf24d5c9bf836 100644
--- a/Source/platform/heap/ThreadState.cpp
+++ b/Source/platform/heap/ThreadState.cpp
@@ -269,16 +269,6 @@ private:
     ThreadCondition m_resume;
 };
 
-BaseHeapPage::BaseHeapPage(PageMemory* storage, const GCInfo* gcInfo, ThreadState* state)
-    : m_storage(storage)
-    , m_gcInfo(gcInfo)
-    , m_threadState(state)
-    , m_terminating(false)
-    , m_tracedAfterOrphaned(false)
-{
-    ASSERT(isPageHeaderAddress(reinterpret_cast<Address>(this)));
-}
-
 // Statically unfold the heap initialization loop so the compiler statically
 // knows the heap index when using HeapIndexTrait.
 template<int num> struct InitializeHeaps {
@@ -310,7 +300,6 @@ ThreadState::ThreadState()
     , m_sweepInProgress(false)
     , m_noAllocationCount(0)
     , m_inGC(false)
-    , m_heapContainsCache(adoptPtr(new HeapContainsCache()))
     , m_isTerminating(false)
     , m_lowCollectionRate(false)
     , m_numberOfSweeperTasks(0)
@@ -581,27 +570,6 @@ void ThreadState::visitPersistents(Visitor* visitor)
     WrapperPersistentRegion::trace(m_liveWrapperPersistents, visitor);
 }
 
-bool ThreadState::checkAndMarkPointer(Visitor* visitor, Address address)
-{
-    // If thread is terminating ignore conservative pointers.
-    if (m_isTerminating)
-        return false;
-
-    // This checks for normal pages and for large objects which span the extent
-    // of several normal pages.
-    BaseHeapPage* page = heapPageFromAddress(address);
-    if (page) {
-        page->checkAndMarkPointer(visitor, address);
-        // Whether or not the pointer was within an object it was certainly
-        // within a page that is part of the heap, so we don't want to ask the
-        // other other heaps or put this address in the
-        // HeapDoesNotContainCache.
-        return true;
-    }
-
-    return false;
-}
-
 #if ENABLE(GC_PROFILE_MARKING)
 const GCInfo* ThreadState::findGCInfo(Address address)
 {
@@ -870,6 +838,14 @@ bool ThreadState::isConsistentForSweeping()
 }
 #endif
 
+void ThreadState::prepareRegionTree()
+{
+    // Add the regions allocated by this thread to the region search tree.
+    for (size_t i = 0; i < m_allocatedRegionsSinceLastGC.size(); ++i)
+        Heap::addPageMemoryRegion(m_allocatedRegionsSinceLastGC[i]);
+    m_allocatedRegionsSinceLastGC.clear();
+}
+
 void ThreadState::prepareForGC()
 {
     for (int i = 0; i < NumberOfHeaps; i++) {
@@ -884,6 +860,7 @@ void ThreadState::prepareForGC()
         if (sweepRequested())
             heap->clearLiveAndMarkDead();
     }
+    prepareRegionTree();
     setSweepRequested();
 }
 
@@ -895,28 +872,10 @@ void ThreadState::setupHeapsForTermination()
 
 BaseHeapPage* ThreadState::heapPageFromAddress(Address address)
 {
-    BaseHeapPage* cachedPage = heapContainsCache()->lookup(address);
-#if !ENABLE(ASSERT)
-    if (cachedPage)
-        return cachedPage;
-#endif
-
     for (int i = 0; i < NumberOfHeaps; i++) {
-        BaseHeapPage* page = m_heaps[i]->heapPageFromAddress(address);
-        if (page) {
-            // Asserts that make sure heapPageFromAddress takes addresses from
-            // the whole aligned blinkPageSize memory area. This is necessary
-            // for the negative cache to work.
-            ASSERT(page->isLargeObject() || page == m_heaps[i]->heapPageFromAddress(roundToBlinkPageStart(address)));
-            if (roundToBlinkPageStart(address) != roundToBlinkPageEnd(address))
-                ASSERT(page->isLargeObject() || page == m_heaps[i]->heapPageFromAddress(roundToBlinkPageEnd(address) - 1));
-            ASSERT(!cachedPage || page == cachedPage);
-            if (!cachedPage)
-                heapContainsCache()->addEntry(address, page);
+        if (BaseHeapPage* page = m_heaps[i]->heapPageFromAddress(address))
             return page;
-        }
     }
-    ASSERT(!cachedPage);
     return 0;
 }