Revert "Oilpan: Replace the positive heap-contains cache with a binary search tree of memory region…

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 262 matching lines @@
         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();
     }
-    // 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();
     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++) {
-        if (BaseHeapPage* page = m_heaps[i]->heapPageFromAddress(address))
+        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);
             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
 
 }