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

Source/platform/heap/ThreadState.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 251 matching lines @@
         barrier->doEnterSafePoint(state, stackEnd);
     }
 
     volatile int m_canResume;
     volatile int m_unparkedThreadCount;
     Mutex m_mutex;
     ThreadCondition m_parked;
     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 {
     static const int index = num - 1;
     static void init(BaseHeap** heaps, ThreadState* state)
     {
         InitializeHeaps<index>::init(heaps, state);
         heaps[index] = new typename HeapIndexTrait<index>::HeapType(state, index);
     }
 };
@@ skipping 11 matching lines @@
     , m_endOfStack(reinterpret_cast<intptr_t*>(getStackStart()))
     , m_safePointScopeMarker(0)
     , m_atSafePoint(false)
     , m_interruptors()
     , m_gcRequested(false)
     , m_forcePreciseGCForTesting(false)
     , m_sweepRequested(0)
     , m_sweepInProgress(false)
     , m_noAllocationCount(0)
     , m_inGC(false)
-    , m_heapContainsCache(adoptPtr(new HeapContainsCache()))
     , m_isTerminating(false)
     , m_lowCollectionRate(false)
     , m_numberOfSweeperTasks(0)
 #if defined(ADDRESS_SANITIZER)
     , m_asanFakeStack(__asan_get_current_fake_stack())
 #endif
 {
     ASSERT(!**s_threadSpecific);
     **s_threadSpecific = this;
 
@@ skipping 250 matching lines @@
         visitAsanFakeStackForPointer(visitor, ptr);
     }
 }
 
 void ThreadState::visitPersistents(Visitor* visitor)
 {
     m_persistents->trace(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)
 {
     BaseHeapPage* page = heapPageFromAddress(address);
     if (page) {
         return page->findGCInfo(address);
     }
     return 0;
 }
 #endif
@@ skipping 248 matching lines @@
 bool ThreadState::isConsistentForSweeping()
 {
     for (int i = 0; i < NumberOfHeaps; i++) {
         if (!m_heaps[i]->isConsistentForSweeping())
             return false;
     }
     return true;
 }
 #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++) {
         BaseHeap* heap = m_heaps[i];
         heap->makeConsistentForSweeping();
         // If a new GC is requested before this thread got around to sweep, ie. due to the
         // thread doing a long running operation, we clear the mark bits and mark any of
         // the dead objects as dead. The latter is used to ensure the next GC marking does
         // not trace already dead objects. If we trace a dead object we could end up tracing
         // into garbage or the middle of another object via the newly conservatively found
         // object.
         if (sweepRequested())
             heap->clearLiveAndMarkDead();
     }
+    prepareRegionTree();
     setSweepRequested();
 }
 
 void ThreadState::setupHeapsForTermination()
 {
     for (int i = 0; i < NumberOfHeaps; i++)
         m_heaps[i]->prepareHeapForTermination();
 }
 
 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;
 }
 
 void ThreadState::getStats(HeapStats& stats)
 {
     stats = m_stats;
 #if ENABLE(ASSERT)
     if (isConsistentForSweeping()) {
         HeapStats scannedStats;
         for (int i = 0; i < NumberOfHeaps; i++)
@@ skipping 332 matching lines @@
             return gcInfo;
         }
     }
     if (needLockForIteration)
         threadAttachMutex().unlock();
     return 0;
 }
 #endif
 
 }