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

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 70 matching lines @@
 }
 
 // Blink heap pages are aligned to the Blink heap page size.
 // Therefore, the start of a Blink page can be obtained by
 // rounding down to the Blink page size.
 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>
 inline size_t headerPadding()
 {
     return (allocationGranularity - (sizeof(Header) % allocationGranularity)) % allocationGranularity;
 }
 
 // Masks an address down to the enclosing blink page base address.
 inline Address blinkPageAddress(Address address)
@@ skipping 26 matching lines @@
 public:
     BaseHeapPage(PageMemory* storage, const GCInfo* gcInfo, ThreadState* state)
         : m_storage(storage)
         , m_gcInfo(gcInfo)
         , m_threadState(state)
         , m_padding(0)
     {
         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;
 #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; }
 
 private:
     // Accessor to silence unused warnings.
     void* padding() const { return m_padding; }
 
     PageMemory* m_storage;
     const GCInfo* m_gcInfo;
     ThreadState* m_threadState;
     // Free word only needed to ensure proper alignment of the
     // HeapPage header.
@@ skipping 11 matching lines @@
 //
 // | BaseHeapPage | next pointer | FinalizedHeapObjectHeader or HeapObjectHeader | payload |
 template<typename Header>
 class LargeHeapObject : public BaseHeapPage {
 public:
     LargeHeapObject(PageMemory* storage, const GCInfo* gcInfo, ThreadState* state) : BaseHeapPage(storage, gcInfo, state)
     {
         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
 
     void link(LargeHeapObject<Header>** previousNext)
     {
         m_next = *previousNext;
         *previousNext = this;
     }
 
     void unlink(LargeHeapObject<Header>** previousNext)
     {
         *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()
     {
         return m_next;
     }
 
     size_t size()
     {
         return heapObjectHeader()->size() + sizeof(LargeHeapObject<Header>) + headerPadding<Header>();
     }
 
     Address payload() { return heapObjectHeader()->payload(); }
     size_t payloadSize() { return heapObjectHeader()->payloadSize(); }
 
     Header* heapObjectHeader()
     {
         Address headerAddress = address() + sizeof(LargeHeapObject<Header>) + headerPadding<Header>();
         return reinterpret_cast<Header*>(headerAddress);
     }
 
     bool isMarked();
     void unmark();
     void getStats(HeapStats&);
     void mark(Visitor*);
     void finalize();
 
 private:
-    friend class Heap;
     friend class ThreadHeap<Header>;
 
     LargeHeapObject<Header>* m_next;
 };
 
 // The BasicObjectHeader is the minimal object header. It is used when
 // encountering heap space of size allocationGranularity to mark it as
 // as freelist entry.
 class PLATFORM_EXPORT BasicObjectHeader {
 public:
@@ skipping 182 matching lines @@
 template<typename Header>
 class HeapPage : public BaseHeapPage {
 public:
     HeapPage(PageMemory*, ThreadHeap<Header>*, const GCInfo*);
 
     void link(HeapPage**);
     static void unlink(HeapPage*, HeapPage**);
 
     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; }
 
     Address payload()
     {
         return address() + sizeof(*this) + headerPadding<Header>();
     }
 
     static size_t payloadSize()
     {
         return (blinkPagePayloadSize() - sizeof(HeapPage) - headerPadding<Header>()) & ~allocationMask;
     }
 
     Address end() { return payload() + payloadSize(); }
 
     void getStats(HeapStats&);
     void clearMarks();
     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
     ThreadHeap<Header>* heap() { return m_heap; }
 #if defined(ADDRESS_SANITIZER)
     void poisonUnmarkedObjects();
 #endif
 
 protected:
     Header* findHeaderFromAddress(Address);
     void populateObjectStartBitMap();
     bool isObjectStartBitMapComputed() { return m_objectStartBitMapComputed; }
     TraceCallback traceCallback(Header*);
     bool hasVTable(Header*);
 
     HeapPage<Header>* m_next;
     ThreadHeap<Header>* m_heap;
     bool m_objectStartBitMapComputed;
     uint8_t m_objectStartBitMap[reservedForObjectBitMap];
 
     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**);
+    // 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. Use a 0 base heap page pointer to
-    // add a negative entry.
-    void addEntry(Address, BaseHeapPage*);
+    // Add an entry to the cache.
+    PLATFORM_EXPORT void addEntry(Address, typename Entry::LookupResult);
 
 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; }
-
-    private:
-        Address m_address;
-        BaseHeapPage* m_containingPage;
-    };
-
     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
 // together with the former instance. I.e. a logical CallbackStack can be made of
 // multiple chained CallbackStack object instances.
 // There are two logical callback stacks. One containing all the marking callbacks and
 // one containing the weak pointer callbacks.
 class CallbackStack {
 public:
     CallbackStack(CallbackStack** first)
@@ skipping 50 matching lines @@
 // Non-template super class used to pass a heap around to other classes.
 class BaseHeap {
 public:
     virtual ~BaseHeap() { }
 
     // Find the page 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* 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;
 
     // Forcefully finalize all objects in this part of the Blink heap
     // (potentially with the exception of one object). This is used
     // during thread termination to make sure that all objects for the
     // dying thread are finalized.
     virtual void assertEmpty() = 0;
 
@@ skipping 22 matching lines @@
 // (potentially adding new pages to the heap), to find and mark
 // objects during conservative stack scanning and to sweep the set of
 // pages after a GC.
 template<typename Header>
 class ThreadHeap : public BaseHeap {
 public:
     ThreadHeap(ThreadState*);
     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();
     virtual void clearMarks();
 #ifndef NDEBUG
     virtual void getScannedStats(HeapStats&);
 #endif
 
     virtual void makeConsistentForGC();
     virtual bool isConsistentForGC();
 
     ThreadState* threadState() { return m_threadState; }
     HeapStats& stats() { return m_threadState->stats(); }
-    HeapContainsCache* heapContainsCache() { return m_threadState->heapContainsCache(); }
+    void flushHeapContainsCache()
+    {
+        m_threadState->heapContainsCache()->flush();
+    }
 
     inline Address allocate(size_t, const GCInfo*);
     void addToFreeList(Address, size_t);
     void addPageToPool(HeapPage<Header>*);
     inline static size_t roundedAllocationSize(size_t size)
     {
         return allocationSizeFromSize(size) - sizeof(Header);
     }
 
 private:
@@ skipping 123 matching lines @@
 #endif
 
     // Collect heap stats for all threads attached to the Blink
     // garbage collector. Should only be called during garbage
     // collection where threads are known to be at safe points.
     static void getStats(HeapStats*);
 
     static bool isConsistentForGC();
     static void makeConsistentForGC();
 
+    static void flushHeapDoesNotContainCache();
+    static bool heapDoesNotContainCacheIsEmpty() { return s_heapDoesNotContainCache->isEmpty(); }
+
+private:
     static Visitor* s_markingVisitor;
 
     static CallbackStack* s_markingStack;
     static CallbackStack* s_weakCallbackStack;
+    static HeapDoesNotContainCache* s_heapDoesNotContainCache;
     static bool s_shutdownCalled;
+    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(); }
 
     explicit NoAllocationScope(bool active) : m_active(active) { enter(); }
@@ skipping 1331 matching lines @@
 // to export. This forces it to export all the methods from ThreadHeap.
 template<> void ThreadHeap<FinalizedHeapObjectHeader>::addPageToHeap(const GCInfo*);
 template<> void ThreadHeap<HeapObjectHeader>::addPageToHeap(const GCInfo*);
 extern template class PLATFORM_EXPORT ThreadHeap<FinalizedHeapObjectHeader>;
 extern template class PLATFORM_EXPORT ThreadHeap<HeapObjectHeader>;
 #endif
 
 }
 
 #endif // Heap_h