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 333 matching lines @@
     void leaveGC()
     {
         m_inGC = false;
         s_inGC = false;
     }
 
     // Is the thread corresponding to this thread state currently
     // sweeping?
     bool isSweepInProgress() const { return m_sweepInProgress; }
 
+    void prepareRegionTree();
     void prepareForGC();
 
     // Safepoint related functionality.
     //
     // When a thread attempts to perform GC it needs to stop all other threads
     // that use the heap or at least guarantee that they will not touch any
     // heap allocated object until GC is complete.
     //
     // We say that a thread is at a safepoint if this thread is guaranteed to
     // not touch any heap allocated object or any heap related functionality until
@@ skipping 113 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 80 matching lines @@
 
 #if ENABLE(GC_PROFILE_MARKING)
     virtual const GCInfo* findGCInfo(Address) = 0;
 #endif
 
     Address address() { return reinterpret_cast<Address>(this); }
     PageMemory* storage() const { return m_storage; }
     ThreadState* threadState() const { return m_threadState; }
     const GCInfo* gcInfo() { return m_gcInfo; }
     virtual bool isLargeObject() { return false; }
-    virtual void markOrphaned()
-    {
-        m_threadState = 0;
-        m_gcInfo = 0;
-        m_terminating = false;
-        m_tracedAfterOrphaned = false;
-    }
+    virtual void markOrphaned();
     bool orphaned() { return !m_threadState; }
     bool terminating() { return m_terminating; }
     void setTerminating() { m_terminating = true; }
     bool tracedAfterOrphaned() { return m_tracedAfterOrphaned; }
     void setTracedAfterOrphaned() { m_tracedAfterOrphaned = true; }
     size_t promptlyFreedSize() { return m_promptlyFreedSize; }
     void resetPromptlyFreedSize() { m_promptlyFreedSize = 0; }
     void addToPromptlyFreedSize(size_t size) { m_promptlyFreedSize += size; }
 
 private:
     PageMemory* m_storage;
     const GCInfo* m_gcInfo;
     ThreadState* m_threadState;
     // Pointer sized integer to ensure proper alignment of the
     // HeapPage header. We use some of the bits to determine
     // 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