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

Issue 271703002: Simplify and speed up address-to-page cache for conservative stack scanning. (Closed)

Created:
6 years, 7 months ago by Erik Corry

Modified:
6 years, 7 months ago

Reviewers:
haraken, wibling-chromium, zerny-chromium, Mads Ager (chromium)

CC:
blink-reviews, haraken, kouhei+heap_chromium.org, Mads Ager (chromium)

Base URL:
svn://svn.chromium.org/blink/trunk

Visibility:
Public.

More Reviews

Description

Simplify and speed up address-to-page cache for conservative stack scanning. This change makes the per-heap address-to-page cache positive only and handles large pages more naturally. There is now a separate whole-process negative cache that keeps track of pages that are not in any of the heaps. This speeds up my microbenchmark from ~87 to ~65. R=ager@chromium.org, haraken@chromium.org, wibling@chromium.org, zerny@chromium.org BUG= Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=173749

Patch Set 1 #

Total comments: 34

Patch Set 2 : Revert GC heuristic change and CL feedback #

Patch Set 3 : There were some missing cache flushes. Strengthened asserts #

Total comments: 7

Patch Set 4 : Merge up #

Created: 6 years, 7 months ago

Download [raw] [tar.bz2]

	Unified diffs	Side-by-side diffs	Delta from patch set	Stats (+241 lines, -171 lines)			Patch
M	Source/platform/heap/Heap.h	View	1 2 3	13 chunks	+126 lines, -78 lines	0 comments	Download
M	Source/platform/heap/Heap.cpp	View	1 2 3	21 chunks	+78 lines, -54 lines	0 comments	Download
M	Source/platform/heap/HeapTest.cpp	View	1 2 3	1 chunk	+9 lines, -0 lines	0 comments	Download
M	Source/platform/heap/ThreadState.h	View	1 2 3	1 chunk	+1 line, -1 line	0 comments	Download
M	Source/platform/heap/ThreadState.cpp	View	1 2 3	3 chunks	+27 lines, -38 lines	0 comments	Download

Messages

Total messages: 17 (0 generated)

Expand Messages | Collapse Messages

haraken

LGTM with comments. This is a nice change! https://codereview.chromium.org/271703002/diff/1/Source/platform/heap/Heap.cpp File Source/platform/heap/Heap.cpp (right): https://codereview.chromium.org/271703002/diff/1/Source/platform/heap/Heap.cpp#newcode763 Source/platform/heap/Heap.cpp:763: heapContainsCache()->flush(); ...

6 years, 7 months ago (2014-05-08 05:44:57 UTC) #2

Mads Ager (chromium)

LGTM https://codereview.chromium.org/271703002/diff/1/Source/platform/heap/Heap.cpp File Source/platform/heap/Heap.cpp (right): https://codereview.chromium.org/271703002/diff/1/Source/platform/heap/Heap.cpp#newcode1529 Source/platform/heap/Heap.cpp:1529: if (reinterpret_cast<uintptr_t>(address) < blinkPageSize) This is an optimization ...

6 years, 7 months ago (2014-05-08 06:52:37 UTC) #4

wibling-chromium

lgtm https://codereview.chromium.org/271703002/diff/1/Source/platform/heap/ThreadState.cpp File Source/platform/heap/ThreadState.cpp (right): https://codereview.chromium.org/271703002/diff/1/Source/platform/heap/ThreadState.cpp#newcode475 Source/platform/heap/ThreadState.cpp:475: BaseHeapPage* page = heapPageFromAddress(address); NIT: Perhaps add a ...

6 years, 7 months ago (2014-05-08 07:43:41 UTC) #5

Erik Corry

https://codereview.chromium.org/271703002/diff/1/Source/platform/heap/Heap.cpp File Source/platform/heap/Heap.cpp (right): https://codereview.chromium.org/271703002/diff/1/Source/platform/heap/Heap.cpp#newcode763 Source/platform/heap/Heap.cpp:763: heapContainsCache()->flush(); On 2014/05/08 05:44:58, haraken wrote: > > For ...

6 years, 7 months ago (2014-05-08 09:26:08 UTC) #6

wibling-chromium

https://codereview.chromium.org/271703002/diff/40001/Source/platform/heap/Heap.cpp File Source/platform/heap/Heap.cpp (right): https://codereview.chromium.org/271703002/diff/40001/Source/platform/heap/Heap.cpp#newcode1529 Source/platform/heap/Heap.cpp:1529: #ifdef NDEBUG Why not do this optimization in release ...

6 years, 7 months ago (2014-05-09 10:25:20 UTC) #7

Erik Corry

6 years, 7 months ago (2014-05-09 10:31:54 UTC) #9

wibling-chromium

lgtm https://codereview.chromium.org/271703002/diff/40001/Source/platform/heap/Heap.cpp File Source/platform/heap/Heap.cpp (right): https://codereview.chromium.org/271703002/diff/40001/Source/platform/heap/Heap.cpp#newcode1529 Source/platform/heap/Heap.cpp:1529: #ifdef NDEBUG On 2014/05/09 10:31:54, Erik Corry wrote: ...

6 years, 7 months ago (2014-05-09 10:40:21 UTC) #10

commit-bot: I haz the power

CQ is trying da patch. Follow status at https://chromium-status.appspot.com/cq/erik.corry@gmail.com/271703002/40001

6 years, 7 months ago (2014-05-09 11:17:15 UTC) #12

commit-bot: I haz the power

The CQ bit was unchecked by commit-bot@chromium.org

6 years, 7 months ago (2014-05-09 11:17:28 UTC) #13

commit-bot: I haz the power

Failed to apply patch for Source/platform/heap/Heap.h: While running patch -p1 --forward --force --no-backup-if-mismatch; patching file ...

6 years, 7 months ago (2014-05-09 11:17:30 UTC) #14

Failed to apply patch for Source/platform/heap/Heap.h:
While running patch -p1 --forward --force --no-backup-if-mismatch;
  patching file Source/platform/heap/Heap.h
  Hunk #1 succeeded at 90 (offset 2 lines).
  Hunk #2 succeeded at 141 (offset 2 lines).
  Hunk #3 succeeded at 159 (offset 2 lines).
  Hunk #4 succeeded at 191 (offset 2 lines).
  Hunk #5 succeeded at 214 (offset 2 lines).
  Hunk #6 succeeded at 255 (offset 2 lines).
  Hunk #7 succeeded at 457 (offset 2 lines).
  Hunk #8 succeeded at 486 (offset 2 lines).
  Hunk #9 FAILED at 508.
  Hunk #10 succeeded at 701 (offset 52 lines).
  Hunk #11 succeeded at 747 (offset 52 lines).
  Hunk #12 succeeded at 763 (offset 52 lines).
  Hunk #13 succeeded at 910 (offset 52 lines).
  1 out of 13 hunks FAILED -- saving rejects to file
Source/platform/heap/Heap.h.rej

Patch:       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..3ed53923db6c589f346a340efd17fc424803eea7
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>
@@ -134,17 +139,15 @@ public:
         ASSERT(isPageHeaderAddress(reinterpret_cast<Address>(this)));
     }
 
-    // Check if the given address could point to an object in this
+    // Check if the given address points 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 do nothing. The pointer must
+    // be within the same aligned blinkPageSize as the this-pointer.
     //
     // 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 +157,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 +189,14 @@ public:
         COMPILE_ASSERT(!(sizeof(LargeHeapObject<Header>) & allocationMask),
large_heap_object_header_misaligned);
     }
 
-    virtual bool checkAndMarkPointer(Visitor*, Address);
+    virtual void checkAndMarkPointer(Visitor*, Address) OVERRIDE;
+    virtual bool isLargeObject() OVERRIDE { return true; }
 
 #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 +212,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 roundToBlinkPageStart(address()) <= object && object <
roundToBlinkPageEnd(address() + size());
     }
 
     LargeHeapObject<Header>* next()
@@ -236,7 +253,6 @@ public:
     void finalize();
 
 private:
-    friend class Heap;
     friend class ThreadHeap<Header>;
 
     LargeHeapObject<Header>* m_next;
@@ -439,10 +455,14 @@ public:
 
     bool isEmpty();
 
+    // Returns true for the whole blinkPageSize page that the page is on, even
+    // for the header, and the unmapped guard page at the start. That ensures
+    // the result can be used to populate the negative page cache.
     bool contains(Address addr)
     {
         Address blinkPageStart = roundToBlinkPageStart(address());
-        return blinkPageStart <= addr && (blinkPageStart + blinkPageSize) >
addr;
+        ASSERT(blinkPageStart = address() - osPageSize()); // Page is at
aligned address plus guard page size.
+        return blinkPageStart <= addr && addr < blinkPageStart + blinkPageSize;
     }
 
     HeapPage* next() { return m_next; }
@@ -464,7 +484,7 @@ public:
     void sweep();
     void clearObjectStartBitMap();
     void finalize(Header*);
-    virtual bool checkAndMarkPointer(Visitor*, Address);
+    virtual void checkAndMarkPointer(Visitor*, Address) OVERRIDE;
 #if ENABLE(GC_TRACING)
     const GCInfo* findGCInfo(Address) OVERRIDE;
 #endif
@@ -488,77 +508,115 @@ protected:
     friend class ThreadHeap<Header>;
 };
 
-// A HeapContainsCache provides a fast way of taking an arbitrary
+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. 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);
+    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. 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.
+   …
(message too large)

commit-bot: I haz the power

CQ is trying da patch. Follow status at https://chromium-status.appspot.com/cq/erik.corry@gmail.com/271703002/60001

6 years, 7 months ago (2014-05-09 11:27:27 UTC) #16

Message was sent while issue was closed.

Change committed as 173749

Expand Messages | Collapse Messages