Simplify and speed up address-to-page cache for conservative stack scanning.

Source/platform/heap/Heap.h

Index: Source/platform/heap/Heap.h
diff --git a/Source/platform/heap/Heap.h b/Source/platform/heap/Heap.h
index e464e89dcfb4c2596f1cc1f532ebc3f2c16f394c..58a7f2cd7f65c64023039c86cdd51800094d7970 100644
--- a/Source/platform/heap/Heap.h
+++ b/Source/platform/heap/Heap.h
@@ -88,6 +88,11 @@ inline Address roundToBlinkPageStart(Address address)
     return reinterpret_cast<Address>(reinterpret_cast<uintptr_t>(address) & blinkPageBaseMask);
 }
 
+inline Address roundToBlinkPageEnd(Address address)
+{
+    return reinterpret_cast<Address>(reinterpret_cast<uintptr_t>(address - 1) & blinkPageBaseMask) + blinkPageSize;
+}
+
 // Compute the amount of padding we have to add to a header to make
 // the size of the header plus the padding a multiple of 8 bytes.
 template<typename Header>
@@ -136,15 +141,12 @@ public:
 
     // Check if the given address could point to an object in this
     // heap page. If so, find the start of that object and mark it
-    // using the given Visitor.
-    //
-    // Returns true if the object was found and marked, returns false
-    // otherwise.
+    // using the given Visitor. Otherwise does nothing.
     //
     // This is used during conservative stack scanning to
     // conservatively mark all objects that could be referenced from
     // the stack.
-    virtual bool checkAndMarkPointer(Visitor*, Address) = 0;
+    virtual void checkAndMarkPointer(Visitor*, Address) = 0;
 
 #if ENABLE(GC_TRACING)
     virtual const GCInfo* findGCInfo(Address) = 0;
@@ -154,6 +156,7 @@ public:
     PageMemory* storage() const { return m_storage; }
     ThreadState* threadState() const { return m_threadState; }
     const GCInfo* gcInfo() { return m_gcInfo; }
+    virtual bool isLargeObject() { return false; }
 
 private:
     // Accessor to silence unused warnings.
@@ -185,11 +188,14 @@ public:
         COMPILE_ASSERT(!(sizeof(LargeHeapObject<Header>) & allocationMask), large_heap_object_header_misaligned);
     }
 
-    virtual bool checkAndMarkPointer(Visitor*, Address);
+    virtual void checkAndMarkPointer(Visitor*, Address);
+    virtual bool isLargeObject() { return true; }

[haraken, 2014/05/08 05:44:58]

Add OVERRIDE.

[Erik Corry, 2014/05/08 09:26:08]

Done.

 
 #if ENABLE(GC_TRACING)
-    virtual const GCInfo* findGCInfo(Address)
+    virtual const GCInfo* findGCInfo(Address address)
     {
+        if (!objectContains(address))
+            return 0;
         return gcInfo();
     }
 #endif
@@ -205,9 +211,19 @@ public:
         *previousNext = m_next;
     }
 
+    // The LargeHeapObject pseudo-page contains one actual object. Determine
+    // whether the pointer is within that object.
+    bool objectContains(Address object)
+    {
+        return (payload() <= object) && (object < address() + size());
+    }
+
+    // Returns true for any address that is on one of the pages that this
+    // large object uses. That ensures that we can use a negative result to
+    // populate the negative page cache.
     bool contains(Address object)
     {
-        return (address() <= object) && (object <= (address() + size()));
+        return address() <= object && object < roundToBlinkPageEnd(address() + size());
     }
 
     LargeHeapObject<Header>* next()
@@ -220,6 +236,11 @@ public:
         return heapObjectHeader()->size() + sizeof(LargeHeapObject<Header>) + headerPadding<Header>();
     }
 
+    size_t sizeRoundedUpToPage()
+    {
+        return ((size() - 1) & blinkPageBaseMask) + blinkPageSize;

[haraken, 2014/05/08 05:44:58]

Can we use roundToBlinkPageEnd? If you use roundToBlinkPageEnd in the caller
site, you can remove sizeRoundedUpToPage.

[Erik Corry, 2014/05/08 09:26:08]

Removed

+    }
+
     Address payload() { return heapObjectHeader()->payload(); }
     size_t payloadSize() { return heapObjectHeader()->payloadSize(); }
 
@@ -236,7 +257,6 @@ public:
     void finalize();
 
 private:
-    friend class Heap;
     friend class ThreadHeap<Header>;
 
     LargeHeapObject<Header>* m_next;
@@ -439,9 +459,13 @@ public:
 
     bool isEmpty();
 
+    // Returns true for the whole blinkPageSize page that the page is on, even
+    // for the header. That ensures the result can be used to populate the negative
+    // page cache.
     bool contains(Address addr)
     {
-        Address blinkPageStart = roundToBlinkPageStart(address());
+        ASSERT(address() == roundToBlinkPageStart(address()));
+        Address blinkPageStart = address();
         return blinkPageStart <= addr && (blinkPageStart + blinkPageSize) > addr;
     }
 
@@ -464,7 +488,7 @@ public:
     void sweep();
     void clearObjectStartBitMap();
     void finalize(Header*);
-    virtual bool checkAndMarkPointer(Visitor*, Address);
+    virtual void checkAndMarkPointer(Visitor*, Address);
 #if ENABLE(GC_TRACING)
     const GCInfo* findGCInfo(Address) OVERRIDE;
 #endif
@@ -488,77 +512,114 @@ protected:
     friend class ThreadHeap<Header>;
 };
 
-// A HeapContainsCache provides a fast way of taking an arbitrary
+class AddressEntry {
+public:
+    AddressEntry() : m_address(0) { }
+
+    AddressEntry(Address address) : m_address(address) { }

[haraken, 2014/05/08 05:44:58]

Add explicit.

[Erik Corry, 2014/05/08 09:26:08]

Done.

+
+    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) { }

[haraken, 2014/05/08 05:44:58]

Do we need the bool parameter? NegativeEntry should just contain a list of
negative entries, and boolean parameters won't need to be associated.

[Erik Corry, 2014/05/08 09:26:08]

The addEntry method of HeapExtentCache expects to use two arguments.

+
+    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 either wholly inside or wholly outside 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 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.
+// 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 both a positive and negative
-// cache. Therefore, it must be flushed both when new memory is added
-// and when memory is removed from the Blink heap.
-class HeapContainsCache {
+// 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:
-    HeapContainsCache();
+    HeapExtentCache()
+        : m_entries(adoptArrayPtr(new Entry[HeapExtentCache::numberOfEntries]))
+        , m_hasEntries(false)
+    {
+    }
 
     void flush();
     bool contains(Address);
 
     // 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. In that case, the address is in the heap if the base
-    // heap page out parameter is different from 0 and is not in the
-    // heap if the base heap page out parameter is 0.
-    bool lookup(Address, BaseHeapPage**);
-
-    // Add an entry to the cache. Use a 0 base heap page pointer to
-    // add a negative entry.
-    void addEntry(Address, BaseHeapPage*);
-
-private:
-    class Entry {
-    public:
-        Entry()
-            : m_address(0)
-            , m_containingPage(0)
-        {
-        }
-
-        Entry(Address address, BaseHeapPage* containingPage)
-            : m_address(address)
-            , m_containingPage(containingPage)
-        {
-        }
-
-        BaseHeapPage* containingPage() { return m_containingPage; }
-        Address address() { return m_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);
 
-    private:
-        Address m_address;
-        BaseHeapPage* m_containingPage;
-    };
+    // Add an entry to the cache.
+    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<HeapContainsCache::Entry[]> 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> { };
+
 // The CallbackStack contains all the visitor callbacks used to trace and mark
 // objects. A specific CallbackStack instance contains at most bufferSize elements.
 // If more space is needed a new CallbackStack instance is created and chained
@@ -629,27 +690,10 @@ public:
     // page in this thread heap.
     virtual BaseHeapPage* heapPageFromAddress(Address) = 0;
 
-    // Find the large object in this thread heap containing the given
-    // address. Returns 0 if the address is not contained in any
-    // page in this thread heap.
-    virtual BaseHeapPage* largeHeapObjectFromAddress(Address) = 0;
-
 #if ENABLE(GC_TRACING)
     virtual const GCInfo* findGCInfoOfLargeHeapObject(Address) = 0;
 #endif
 
-    // Check if the given address could point to an object in this
-    // heap. If so, find the start of that object and mark it using
-    // the given Visitor.
-    //
-    // Returns true if the object was found and marked, returns false
-    // otherwise.
-    //
-    // This is used during conservative stack scanning to
-    // conservatively mark all objects that could be referenced from
-    // the stack.
-    virtual bool checkAndMarkLargeHeapObject(Visitor*, Address) = 0;
-
     // Sweep this part of the Blink heap. This finalizes dead objects
     // and builds freelists for all the unused memory.
     virtual void sweep() = 0;
@@ -692,11 +736,9 @@ public:
     virtual ~ThreadHeap();
 
     virtual BaseHeapPage* heapPageFromAddress(Address);
-    virtual BaseHeapPage* largeHeapObjectFromAddress(Address);
 #if ENABLE(GC_TRACING)
     virtual const GCInfo* findGCInfoOfLargeHeapObject(Address);
 #endif
-    virtual bool checkAndMarkLargeHeapObject(Visitor*, Address);
     virtual void sweep();
     virtual void assertEmpty();
     virtual void clearFreeLists();
@@ -854,11 +896,18 @@ public:
     static bool isConsistentForGC();
     static void makeConsistentForGC();
 
+    static bool notInHeap(Address);
+    static void addressIsNotInHeap(Address);

[Mads Ager (chromium), 2014/05/08 06:52:37]

I would remove these methods and just inline the one liners. I find that easier
to read (being explicit about the cache) and it doesn't clutter the header file.


Are they added because ThreadState needs to use this? ThreadState is a friend
and has access to the cache directly. You could add a private getter if you
want.

[Erik Corry, 2014/05/08 09:26:08]

Done.

+    static void flushNotInHeapCache();

[haraken, 2014/05/08 05:44:58]

flushHeapDoesNotContainCache

It's confusing to have two names for one thing.

[Erik Corry, 2014/05/08 09:26:08]

Done.

+
+private:
     static Visitor* s_markingVisitor;
 
     static CallbackStack* s_markingStack;
     static CallbackStack* s_weakCallbackStack;
+    static HeapDoesNotContainCache* s_notInHeapCache;

[haraken, 2014/05/08 05:44:58]

s_notInHeapCache => s_heapDoesNotContainCache

[Erik Corry, 2014/05/08 09:26:08]

Done.

     static bool s_shutdownCalled;
+    friend class ThreadState;
 };
 
 // The NoAllocationScope class is used in debug mode to catch unwanted