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

Source/platform/heap/ThreadState.h

 /*
  * 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 34 matching lines @@
 #if ENABLE(GC_PROFILE_HEAP)
 #include "wtf/HashMap.h"
 #endif
 
 namespace blink {
 
 class BaseHeap;
 class BaseHeapPage;
 class FinalizedHeapObjectHeader;
 struct GCInfo;
-class HeapContainsCache;
 class HeapObjectHeader;
 class PageMemory;
 class PersistentNode;
 class WrapperPersistentRegion;
 class Visitor;
 class SafePointBarrier;
 class SafePointAwareMutexLocker;
 template<typename Header> class ThreadHeap;
 class CallbackStack;
+class PageMemoryRegion;
 
 typedef uint8_t* Address;
 
 typedef void (*FinalizationCallback)(void*);
 typedef void (*VisitorCallback)(Visitor*, void* self);
 typedef VisitorCallback TraceCallback;
 typedef VisitorCallback WeakPointerCallback;
 typedef VisitorCallback EphemeronCallback;
 
 // ThreadAffinity indicates which threads objects can be used on. We
@@ skipping 466 matching lines @@
     // Get one of the heap structures for this thread.
     //
     // The heap is split into multiple heap parts based on object
     // types. To get the index for a given type, use
     // HeapTypeTrait<Type>::index.
     BaseHeap* heap(int index) const { return m_heaps[index]; }
 
     // Infrastructure to determine if an address is within one of the
     // address ranges for the Blink heap. If the address is in the Blink
     // heap the containing heap page is returned.
-    HeapContainsCache* heapContainsCache() { return m_heapContainsCache.get(); }
     BaseHeapPage* contains(Address address) { return heapPageFromAddress(address); }
     BaseHeapPage* contains(void* pointer) { return contains(reinterpret_cast<Address>(pointer)); }
     BaseHeapPage* contains(const void* pointer) { return contains(const_cast<void*>(pointer)); }
 
     WrapperPersistentRegion* wrapperRoots() const
     {
         ASSERT(m_liveWrapperPersistents);
         return m_liveWrapperPersistents;
     }
     WrapperPersistentRegion* takeWrapperPersistentRegion();
@@ skipping 10 matching lines @@
     // Visit local thread stack and trace all pointers conservatively.
     void visitStack(Visitor*);
 
     // Visit the asan fake stack frame corresponding to a slot on the
     // real machine stack if there is one.
     void visitAsanFakeStackForPointer(Visitor*, Address);
 
     // Visit all persistents allocated on this thread.
     void visitPersistents(Visitor*);
 
-    // Checks a given address and if a pointer into the oilpan heap marks
-    // the object to which it points.
-    bool checkAndMarkPointer(Visitor*, Address);
-
 #if ENABLE(GC_PROFILE_MARKING)
     const GCInfo* findGCInfo(Address);
     static const GCInfo* findGCInfoFromAllThreads(Address);
 #endif
 
 #if ENABLE(GC_PROFILE_HEAP)
     struct SnapshotInfo {
         ThreadState* state;
 
         size_t freeSize;
@@ skipping 28 matching lines @@
     HeapStats& stats() { return m_stats; }
     HeapStats& statsAfterLastGC() { return m_statsAfterLastGC; }
 
     void setupHeapsForTermination();
 
     void registerSweepingTask();
     void unregisterSweepingTask();
 
     Mutex& sweepMutex() { return m_sweepMutex; }
 
+    Vector<PageMemoryRegion*>& allocatedRegionsSinceLastGC() { return m_allocatedRegionsSinceLastGC; }
+
 private:
     explicit ThreadState();
     ~ThreadState();
 
     friend class SafePointBarrier;
     friend class SafePointAwareMutexLocker;
 
     void enterSafePoint(StackState, void*);
     NO_SANITIZE_ADDRESS void copyStackUntilSafePointScope();
     void clearSafePointScopeMarker()
@@ skipping 52 matching lines @@
     Vector<Address> m_safePointStackCopy;
     bool m_atSafePoint;
     Vector<Interruptor*> m_interruptors;
     bool m_gcRequested;
     bool m_forcePreciseGCForTesting;
     volatile int m_sweepRequested;
     bool m_sweepInProgress;
     size_t m_noAllocationCount;
     bool m_inGC;
     BaseHeap* m_heaps[NumberOfHeaps];
-    OwnPtr<HeapContainsCache> m_heapContainsCache;
     HeapStats m_stats;
     HeapStats m_statsAfterLastGC;
 
     Vector<OwnPtr<CleanupTask> > m_cleanupTasks;
     bool m_isTerminating;
 
     bool m_lowCollectionRate;
 
     OwnPtr<blink::WebThread> m_sweeperThread;
     int m_numberOfSweeperTasks;
     Mutex m_sweepMutex;
     ThreadCondition m_sweepThreadCondition;
 
     CallbackStack* m_weakCallbackStack;
 
 #if defined(ADDRESS_SANITIZER)
     void* m_asanFakeStack;
 #endif
+
+    Vector<PageMemoryRegion*> m_allocatedRegionsSinceLastGC;
 };
 
 template<ThreadAffinity affinity> class ThreadStateFor;
 
 template<> class ThreadStateFor<MainThreadOnly> {
 public:
     static ThreadState* state()
     {
         // This specialization must only be used from the main thread.
         ASSERT(ThreadState::current()->isMainThread());
@@ skipping 112 matching lines @@
     // whether the page is part of a terminting thread or
     // if the page is traced after being terminated (orphaned).
     uintptr_t m_terminating : 1;
     uintptr_t m_tracedAfterOrphaned : 1;
     uintptr_t m_promptlyFreedSize : 17; // == blinkPageSizeLog2
 };
 
 }
 
 #endif // ThreadState_h