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

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>;
 };
 
-// A HeapDoesNotContainCache provides a fast way of taking an arbitrary
-// pointer-sized word, and determining whether it cannot be interpreted
+class AddressEntry {
+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)
+    {
+    }
+
+    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. 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
+// 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
-// 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.
+// 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.
 //
-// The HeapDoesNotContainCache is a negative cache, so it must be
-// flushed when memory is added to the heap.
-class HeapDoesNotContainCache {
+// 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:
-    HeapDoesNotContainCache()
-        : m_entries(adoptArrayPtr(new Address[HeapDoesNotContainCache::numberOfEntries]))
-        , m_hasEntries(true)
+    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 false, the argument address was not found in
+    // If lookup returns null/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, the argument address was found in the
-    // cache which means the address is not in the heap.
-    PLATFORM_EXPORT bool lookup(Address);
+    // 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);
 
     // Add an entry to the cache.
-    PLATFORM_EXPORT void addEntry(Address);
+    PLATFORM_EXPORT void addEntry(Address, typename Entry::LookupResult);
 
 private:
     static const int numberOfEntriesLog2 = 12;
     static const int numberOfEntries = 1 << numberOfEntriesLog2;
 
     static size_t hash(Address);
 
-    WTF::OwnPtr<Address[]> m_entries;
+    WTF::OwnPtr<Entry[]> 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