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

Source/platform/heap/Heap.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 555 matching lines @@
     intptr_t padding() const { return m_padding; }
 
     HeapPage<Header>* m_next;
     intptr_t m_padding; // Preserve 8-byte alignment on 32-bit systems.
     bool m_objectStartBitMapComputed;
     uint8_t m_objectStartBitMap[reservedForObjectBitMap];
 
     friend class ThreadHeap<Header>;
 };
 
-class AddressEntry {
+// A HeapDoesNotContainCache provides a fast way of taking an arbitrary
+// pointer-sized word, and determining whether it cannot be interpreted
+// as a pointer to an area that is managed by the garbage collected
+// Blink heap. This is a cache of 'pages' that have previously been
+// determined to be wholly outside of the heap. The size of these pages must be
+// smaller than the allocation alignment of the heap pages. We determine
+// off-heap-ness by rounding down the pointer to the nearest page and looking up
+// the page in the cache. If there is a miss in the cache we can determine the
+// status of the pointer precisely using the heap RegionTree.
+//
+// The HeapDoesNotContainCache is a negative cache, so it must be
+// flushed when memory is added to the heap.
+class HeapDoesNotContainCache {
 public:
-    AddressEntry() : m_address(0) { }
-
-    explicit AddressEntry(Address address) : m_address(address) { }
-
-    Address address() const { return m_address; }
-
-private:
-    Address m_address;
-};
-
-class PositiveEntry : public AddressEntry {
-public:
-    PositiveEntry()
-        : AddressEntry()
-        , m_containingPage(0)
+    HeapDoesNotContainCache()
+        : m_entries(adoptArrayPtr(new Address[HeapDoesNotContainCache::numberOfEntries]))
+        , m_hasEntries(true)
     {
-    }
-
-    PositiveEntry(Address address, BaseHeapPage* containingPage)
-        : AddressEntry(address)
-        , m_containingPage(containingPage)
-    {
-    }
-
-    BaseHeapPage* result() const { return m_containingPage; }
-
-    typedef BaseHeapPage* LookupResult;
-
-private:
-    BaseHeapPage* m_containingPage;
-};
-
-class NegativeEntry : public AddressEntry {
-public:
-    NegativeEntry() : AddressEntry() { }
-
-    NegativeEntry(Address address, bool) : AddressEntry(address) { }
-
-    bool result() const { return true; }
-
-    typedef bool LookupResult;
-};
-
-// A HeapExtentCache provides a fast way of taking an arbitrary
-// pointer-sized word, and determining whether it can be interpreted
-// as a pointer to an area that is managed by the garbage collected
-// Blink heap. There is a cache of 'pages' that have previously been
-// determined to be wholly inside the heap. The size of these pages must be
-// smaller than the allocation alignment of the heap pages. We determine
-// on-heap-ness by rounding down the pointer to the nearest page and looking up
-// the page in the cache. If there is a miss in the cache we can ask the heap
-// to determine the status of the pointer by iterating over all of the heap.
-// The result is then cached in the two-way associative page cache.
-//
-// A HeapContainsCache is a positive cache. Therefore, it must be flushed when
-// memory is removed from the Blink heap. The HeapDoesNotContainCache is a
-// negative cache, so it must be flushed when memory is added to the heap.
-template<typename Entry>
-class HeapExtentCache {
-public:
-    HeapExtentCache()
-        : m_entries(adoptArrayPtr(new Entry[HeapExtentCache::numberOfEntries]))
-        , m_hasEntries(false)
-    {
+        // Start by flushing the cache in a non-empty state to initialize all the cache entries.
+        flush();
     }
 
     void flush();
-    bool contains(Address);
     bool isEmpty() { return !m_hasEntries; }
 
     // Perform a lookup in the cache.
     //
-    // If lookup returns null/false the argument address was not found in
+    // If lookup returns false, the argument address was not found in
     // the cache and it is unknown if the address is in the Blink
     // heap.
     //
-    // If lookup returns true/a page, the argument address was found in the
-    // cache. For the HeapContainsCache this means the address is in the heap.
-    // For the HeapDoesNotContainCache this means the address is not in the
-    // heap.
-    PLATFORM_EXPORT typename Entry::LookupResult lookup(Address);
+    // If lookup returns true, the argument address was found in the
+    // cache which means the address is not in the heap.
+    PLATFORM_EXPORT bool lookup(Address);
 
     // Add an entry to the cache.
-    PLATFORM_EXPORT void addEntry(Address, typename Entry::LookupResult);
+    PLATFORM_EXPORT void addEntry(Address);
 
 private:
     static const int numberOfEntriesLog2 = 12;
     static const int numberOfEntries = 1 << numberOfEntriesLog2;
 
     static size_t hash(Address);
 
-    WTF::OwnPtr<Entry[]> m_entries;
+    WTF::OwnPtr<Address[]> m_entries;
     bool m_hasEntries;
-
-    friend class ThreadState;
 };
 
-// Normally these would be typedefs instead of subclasses, but that makes them
-// very hard to forward declare.
-class HeapContainsCache : public HeapExtentCache<PositiveEntry> {
-public:
-    BaseHeapPage* lookup(Address);
-    void addEntry(Address, BaseHeapPage*);
-};
-
-class HeapDoesNotContainCache : public HeapExtentCache<NegativeEntry> { };
-
 // FIXME: This is currently used by the WebAudio code.
 // We should attempt to restructure the WebAudio code so that the main thread
 // alone determines life-time and receives messages about life-time from the
 // audio thread.
 template<typename T>
 class ThreadSafeRefCountedGarbageCollected : public GarbageCollectedFinalized<T>, public WTF::ThreadSafeRefCountedBase {
     WTF_MAKE_NONCOPYABLE(ThreadSafeRefCountedGarbageCollected);
 
 public:
     ThreadSafeRefCountedGarbageCollected()
@@ skipping 173 matching lines @@
     virtual void makeConsistentForSweeping();
 
 #if ENABLE(ASSERT)
     virtual bool isConsistentForSweeping();
 
     virtual void getScannedStats(HeapStats&);
 #endif
 
     ThreadState* threadState() { return m_threadState; }
     HeapStats& stats() { return m_threadState->stats(); }
-    void flushHeapContainsCache()
-    {
-        m_threadState->heapContainsCache()->flush();
-    }
 
     inline Address allocate(size_t, const GCInfo*);
     void addToFreeList(Address, size_t);
     inline static size_t roundedAllocationSize(size_t size)
     {
         return allocationSizeFromSize(size) - sizeof(Header);
     }
 
     virtual void prepareHeapForTermination();
 
@@ skipping 173 matching lines @@
     static void flushHeapDoesNotContainCache();
     static bool heapDoesNotContainCacheIsEmpty() { return s_heapDoesNotContainCache->isEmpty(); }
 
     // Return true if the last GC found a pointer into a heap page
     // during conservative scanning.
     static bool lastGCWasConservative() { return s_lastGCWasConservative; }
 
     static FreePagePool* freePagePool() { return s_freePagePool; }
     static OrphanedPagePool* orphanedPagePool() { return s_orphanedPagePool; }
 
+    // This look-up uses the region search tree and a negative contains cache to
+    // provide an efficient mapping from arbitrary addresses to the containing
+    // heap-page if one exists.
+    static BaseHeapPage* lookup(Address);
+    static void addPageMemoryRegion(PageMemoryRegion*);
+    static void removePageMemoryRegion(PageMemoryRegion*);
+
 private:
+    // A RegionTree is a simple binary search tree of PageMemoryRegions sorted
+    // by base addresses.
+    class RegionTree {
+    public:
+        explicit RegionTree(PageMemoryRegion* region) : m_region(region), m_left(0), m_right(0) { }
+        ~RegionTree()
+        {
+            delete m_left;
+            delete m_right;
+        }
+        PageMemoryRegion* lookup(Address);
+        static void add(RegionTree*, RegionTree**);
+        static void remove(PageMemoryRegion*, RegionTree**);
+    private:
+        PageMemoryRegion* m_region;
+        RegionTree* m_left;
+        RegionTree* m_right;
+    };
+
     static Visitor* s_markingVisitor;
     static Vector<OwnPtr<blink::WebThread> >* s_markingThreads;
     static CallbackStack* s_markingStack;
     static CallbackStack* s_postMarkingCallbackStack;
     static CallbackStack* s_weakCallbackStack;
     static CallbackStack* s_ephemeronStack;
     static HeapDoesNotContainCache* s_heapDoesNotContainCache;
     static bool s_shutdownCalled;
     static bool s_lastGCWasConservative;
     static FreePagePool* s_freePagePool;
     static OrphanedPagePool* s_orphanedPagePool;
+    static RegionTree* s_regionTree;
     friend class ThreadState;
 };
 
 // The NoAllocationScope class is used in debug mode to catch unwanted
 // allocations. E.g. allocations during GC.
 template<ThreadAffinity Affinity>
 class NoAllocationScope {
 public:
     NoAllocationScope() : m_active(true) { enter(); }
 
@@ skipping 1391 matching lines @@
 };
 
 template<typename T>
 struct IfWeakMember<WeakMember<T> > {
     static bool isDead(Visitor* visitor, const WeakMember<T>& t) { return !visitor->isAlive(t.get()); }
 };
 
 }
 
 #endif // Heap_h