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

Source/platform/heap/Heap.cpp

 /*
  * 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 113 matching lines @@
         int err = munmap(m_base, m_size);
         RELEASE_ASSERT(!err);
 #else
         bool success = VirtualFree(m_base, 0, MEM_RELEASE);
         RELEASE_ASSERT(success);
 #endif
     }
 
     WARN_UNUSED_RETURN bool commit()
     {
+        ASSERT(Heap::heapDoesNotContainCacheIsEmpty());
 #if OS(POSIX)
         int err = mprotect(m_base, m_size, PROT_READ | PROT_WRITE);
         if (!err) {
             madvise(m_base, m_size, MADV_NORMAL);
             return true;
         }
         return false;
 #else
         void* result = VirtualAlloc(m_base, m_size, MEM_COMMIT, PAGE_READWRITE);
         return !!result;
@@ skipping 53 matching lines @@
         // Virtual memory allocation routines operate in OS page sizes.
         // Round up the requested size to nearest os page size.
         payloadSize = roundToOsPageSize(payloadSize);
 
         // Overallocate by blinkPageSize and 2 times OS page size to
         // ensure a chunk of memory which is blinkPageSize aligned and
         // has a system page before and after to use for guarding. We
         // unmap the excess memory before returning.
         size_t allocationSize = payloadSize + 2 * osPageSize() + blinkPageSize;
 
+        ASSERT(Heap::heapDoesNotContainCacheIsEmpty());
 #if OS(POSIX)
         Address base = static_cast<Address>(mmap(0, allocationSize, PROT_READ | PROT_WRITE, MAP_ANON | MAP_PRIVATE, -1, 0));
         RELEASE_ASSERT(base != MAP_FAILED);
 
         Address end = base + allocationSize;
         Address alignedBase = roundToBlinkPageBoundary(base);
         Address payloadBase = alignedBase + osPageSize();
         Address payloadEnd = payloadBase + payloadSize;
         Address blinkPageEnd = payloadEnd + osPageSize();
 
@@ skipping 202 matching lines @@
     return heapObjectHeader()->unmark();
 }
 
 template<typename Header>
 bool LargeHeapObject<Header>::isMarked()
 {
     return heapObjectHeader()->isMarked();
 }
 
 template<typename Header>
-bool LargeHeapObject<Header>::checkAndMarkPointer(Visitor* visitor, Address address)
+void LargeHeapObject<Header>::checkAndMarkPointer(Visitor* visitor, Address address)
 {
-    if (contains(address)) {
+    ASSERT(contains(address));
+    if (!objectContains(address))
+        return;
 #if ENABLE(GC_TRACING)
-        visitor->setHostInfo(&address, "stack");
+    visitor->setHostInfo(&address, "stack");
 #endif
-        mark(visitor);
-        return true;
-    }
-    return false;
+    mark(visitor);
 }
 
 template<>
 void LargeHeapObject<FinalizedHeapObjectHeader>::mark(Visitor* visitor)
 {
     if (heapObjectHeader()->hasVTable() && !vTableInitialized(payload()))
         visitor->markConservatively(heapObjectHeader());
     else
         visitor->mark(heapObjectHeader(), heapObjectHeader()->traceCallback());
 }
@@ skipping 102 matching lines @@
     RELEASE_ASSERT(success);
 }
 
 template<typename Header>
 BaseHeapPage* ThreadHeap<Header>::heapPageFromAddress(Address address)
 {
     for (HeapPage<Header>* page = m_firstPage; page; page = page->next()) {
         if (page->contains(address))
             return page;
     }
-    return 0;
-}
-
-template<typename Header>
-BaseHeapPage* ThreadHeap<Header>::largeHeapObjectFromAddress(Address address)
-{
     for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current; current = current->next()) {
+        // Check that large pages are blinkPageSize aligned (modulo the
+        // osPageSize for the guard page).
+        ASSERT(reinterpret_cast<Address>(current) - osPageSize() == roundToBlinkPageStart(reinterpret_cast<Address>(current)));
         if (current->contains(address))
             return current;
     }
     return 0;
 }
 
 #if ENABLE(GC_TRACING)
 template<typename Header>
 const GCInfo* ThreadHeap<Header>::findGCInfoOfLargeHeapObject(Address address)
 {
     for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current; current = current->next()) {
         if (current->contains(address))
             return current->gcInfo();
     }
     return 0;
 }
 #endif
 
 template<typename Header>
-bool ThreadHeap<Header>::checkAndMarkLargeHeapObject(Visitor* visitor, Address address)
-{
-    for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current; current = current->next()) {
-        if (current->checkAndMarkPointer(visitor, address))
-            return true;
-    }
-    return false;
-}
-
-template<typename Header>
 void ThreadHeap<Header>::addToFreeList(Address address, size_t size)
 {
     ASSERT(heapPageFromAddress(address));
     ASSERT(heapPageFromAddress(address + size - 1));
     ASSERT(size < blinkPagePayloadSize());
     // The free list entries are only pointer aligned (but when we allocate
     // from them we are 8 byte aligned due to the header size).
     ASSERT(!((reinterpret_cast<uintptr_t>(address) + sizeof(Header)) & allocationMask));
     ASSERT(!(size & allocationMask));
     ASAN_POISON_MEMORY_REGION(address, size);
@@ skipping 33 matching lines @@
     // headerPadding<Header> bytes to ensure it 8 byte aligned.
     allocationSize += headerPadding<Header>();
 
     // If ASAN is supported we add allocationGranularity bytes to the allocated space and
     // poison that to detect overflows
 #if defined(ADDRESS_SANITIZER)
     allocationSize += allocationGranularity;
 #endif
     if (threadState()->shouldGC())
         threadState()->setGCRequested();
+    Heap::flushHeapDoesNotContainCache();
     PageMemory* pageMemory = PageMemory::allocate(allocationSize);
     Address largeObjectAddress = pageMemory->writableStart();
     Address headerAddress = largeObjectAddress + sizeof(LargeHeapObject<Header>) + headerPadding<Header>();
     memset(headerAddress, 0, size);
     Header* header = new (NotNull, headerAddress) Header(size, gcInfo);
     Address result = headerAddress + sizeof(*header);
     ASSERT(!(reinterpret_cast<uintptr_t>(result) & allocationMask));
     LargeHeapObject<Header>* largeObject = new (largeObjectAddress) LargeHeapObject<Header>(pageMemory, gcInfo, threadState());
 
     // Poison the object header and allocationGranularity bytes after the object
     ASAN_POISON_MEMORY_REGION(header, sizeof(*header));
     ASAN_POISON_MEMORY_REGION(largeObject->address() + largeObject->size(), allocationGranularity);
     largeObject->link(&m_firstLargeHeapObject);
     stats().increaseAllocatedSpace(largeObject->size());
     stats().increaseObjectSpace(largeObject->payloadSize());
     return result;
 }
 
 template<typename Header>
 void ThreadHeap<Header>::freeLargeObject(LargeHeapObject<Header>* object, LargeHeapObject<Header>** previousNext)
 {
+    flushHeapContainsCache();
     object->unlink(previousNext);
     object->finalize();
 
     // Unpoison the object header and allocationGranularity bytes after the
     // object before freeing.
     ASAN_UNPOISON_MEMORY_REGION(object->heapObjectHeader(), sizeof(Header));
     ASAN_UNPOISON_MEMORY_REGION(object->address() + object->size(), allocationGranularity);
     delete object->storage();
 }
 
@@ skipping 16 matching lines @@
 
 template<typename Header>
 void ThreadHeap<Header>::clearPagePool()
 {
     while (takePageFromPool()) { }
 }
 
 template<typename Header>
 PageMemory* ThreadHeap<Header>::takePageFromPool()
 {
+    Heap::flushHeapDoesNotContainCache();
     while (PagePoolEntry* entry = m_pagePool) {
         m_pagePool = entry->next();
         PageMemory* storage = entry->storage();
         delete entry;
 
         if (storage->commit())
             return storage;
 
         // Failed to commit pooled storage. Release it.
         delete storage;
     }
 
     return 0;
 }
 
 template<typename Header>
 void ThreadHeap<Header>::addPageToPool(HeapPage<Header>* unused)
 {
+    flushHeapContainsCache();
     PageMemory* storage = unused->storage();
     PagePoolEntry* entry = new PagePoolEntry(storage, m_pagePool);
     m_pagePool = entry;
     storage->decommit();
 }
 
 template<typename Header>
 void ThreadHeap<Header>::allocatePage(const GCInfo* gcInfo)
 {
-    heapContainsCache()->flush();
+    Heap::flushHeapDoesNotContainCache();
     PageMemory* pageMemory = takePageFromPool();
     if (!pageMemory) {
         pageMemory = PageMemory::allocate(blinkPagePayloadSize());
         RELEASE_ASSERT(pageMemory);
     }
     HeapPage<Header>* page = new (pageMemory->writableStart()) HeapPage<Header>(pageMemory, this, gcInfo);
     // FIXME: Oilpan: Linking new pages into the front of the list is
     // crucial when performing allocations during finalization because
     // it ensures that those pages are not swept in the current GC
     // round. We should create a separate page list for that to
@@ skipping 30 matching lines @@
     // calling their finalizer methods. This can catch the cases where one objects
     // finalizer tries to modify another object as part of finalization.
     for (HeapPage<Header>* page = m_firstPage; page; page = page->next())
         page->poisonUnmarkedObjects();
 #endif
     HeapPage<Header>* page = m_firstPage;
     HeapPage<Header>** previous = &m_firstPage;
     bool pagesRemoved = false;
     while (page) {
         if (page->isEmpty()) {
+            flushHeapContainsCache();
             HeapPage<Header>* unused = page;
             page = page->next();
             HeapPage<Header>::unlink(unused, previous);
             pagesRemoved = true;
         } else {
             page->sweep();
             previous = &page->m_next;
             page = page->next();
         }
     }
     if (pagesRemoved)
-        heapContainsCache()->flush();
+        flushHeapContainsCache();
 
     LargeHeapObject<Header>** previousNext = &m_firstLargeHeapObject;
     for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current;) {
         if (current->isMarked()) {
             stats().increaseAllocatedSpace(current->size());
             stats().increaseObjectSpace(current->payloadSize());
             current->unmark();
             previousNext = &current->m_next;
             current = current->next();
         } else {
@@ skipping 53 matching lines @@
     ASSERT(isConsistentForGC());
     for (HeapPage<Header>* page = m_firstPage; page; page = page->next())
         page->clearMarks();
     for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current; current = current->next())
         current->unmark();
 }
 
 template<typename Header>
 void ThreadHeap<Header>::deletePages()
 {
-    heapContainsCache()->flush();
+    flushHeapContainsCache();
     // Add all pages in the pool to the heap's list of pages before deleting
     clearPagePool();
 
     for (HeapPage<Header>* page = m_firstPage; page; ) {
         HeapPage<Header>* dead = page;
         page = page->next();
         PageMemory* storage = dead->storage();
         dead->~HeapPage();
         delete storage;
     }
@@ skipping 191 matching lines @@
     objectStartNumber = (mapIndex * 8) + 7 - leadingZeroes;
     objectOffset = objectStartNumber * allocationGranularity;
     Address objectAddress = objectOffset + payload();
     Header* header = reinterpret_cast<Header*>(objectAddress);
     if (header->isFree())
         return 0;
     return header;
 }
 
 template<typename Header>
-bool HeapPage<Header>::checkAndMarkPointer(Visitor* visitor, Address address)
+void HeapPage<Header>::checkAndMarkPointer(Visitor* visitor, Address address)
 {
+    ASSERT(contains(address));
     Header* header = findHeaderFromAddress(address);
     if (!header)
-        return false;
+        return;
 
 #if ENABLE(GC_TRACING)
     visitor->setHostInfo(&address, "stack");
 #endif
     if (hasVTable(header) && !vTableInitialized(header->payload()))
         visitor->markConservatively(header);
     else
         visitor->mark(header, traceCallback(header));
-    return true;
 }
 
 #if ENABLE(GC_TRACING)
 template<typename Header>
 const GCInfo* HeapPage<Header>::findGCInfo(Address address)
 {
     if (address < payload())
         return 0;
 
     if (gcInfo()) // for non FinalizedObjectHeader
@@ skipping 61 matching lines @@
     return header->hasVTable();
 }
 
 template<typename Header>
 void LargeHeapObject<Header>::getStats(HeapStats& stats)
 {
     stats.increaseAllocatedSpace(size());
     stats.increaseObjectSpace(payloadSize());
 }
 
-HeapContainsCache::HeapContainsCache()
-    : m_entries(adoptArrayPtr(new Entry[HeapContainsCache::numberOfEntries]))
+template<typename Entry>
+void HeapExtentCache<Entry>::flush()
 {
+    if (m_hasEntries) {
+        for (int i = 0; i < numberOfEntries; i++)
+            m_entries[i] = Entry();
+        m_hasEntries = false;
+    }
 }
 
-void HeapContainsCache::flush()
-{
-    for (int i = 0; i < numberOfEntries; i++)
-        m_entries[i] = Entry();
-}
-
-size_t HeapContainsCache::hash(Address address)
+template<typename Entry>
+size_t HeapExtentCache<Entry>::hash(Address address)
 {
     size_t value = (reinterpret_cast<size_t>(address) >> blinkPageSizeLog2);
     value ^= value >> numberOfEntriesLog2;
     value ^= value >> (numberOfEntriesLog2 * 2);
     value &= numberOfEntries - 1;
     return value & ~1; // Returns only even number.
 }
 
-bool HeapContainsCache::lookup(Address address, BaseHeapPage** page)
-{
-    ASSERT(page);
-    size_t index = hash(address);
-    ASSERT(!(index & 1));
-    Address cachePage = roundToBlinkPageStart(address);
-    if (m_entries[index].address() == cachePage) {
-        *page = m_entries[index].containingPage();
-        return true;
-    }
-    if (m_entries[index + 1].address() == cachePage) {
-        *page = m_entries[index + 1].containingPage();
-        return true;
-    }
-    *page = 0;
-    return false;
-}
-
-void HeapContainsCache::addEntry(Address address, BaseHeapPage* page)
+template<typename Entry>
+typename Entry::LookupResult HeapExtentCache<Entry>::lookup(Address address)
 {
     size_t index = hash(address);
     ASSERT(!(index & 1));
     Address cachePage = roundToBlinkPageStart(address);
+    if (m_entries[index].address() == cachePage)
+        return m_entries[index].result();
+    if (m_entries[index + 1].address() == cachePage)
+        return m_entries[index + 1].result();
+    return 0;
+}
+
+template<typename Entry>
+void HeapExtentCache<Entry>::addEntry(Address address, typename Entry::LookupResult entry)
+{
+    m_hasEntries = true;
+    size_t index = hash(address);
+    ASSERT(!(index & 1));
+    Address cachePage = roundToBlinkPageStart(address);
     m_entries[index + 1] = m_entries[index];
-    m_entries[index] = Entry(cachePage, page);
+    m_entries[index] = Entry(cachePage, entry);
+}
+
+// These should not be needed, but it seems impossible to persuade clang to
+// instantiate the template functions and export them from a shared library, so
+// we add these in the non-templated subclass, which does not have that issue.
+void HeapContainsCache::addEntry(Address address, BaseHeapPage* page)
+{
+    HeapExtentCache<PositiveEntry>::addEntry(address, page);
+}
+
+BaseHeapPage* HeapContainsCache::lookup(Address address)
+{
+    return HeapExtentCache<PositiveEntry>::lookup(address);
+}
+
+void Heap::flushHeapDoesNotContainCache()
+{
+    s_heapDoesNotContainCache->flush();
 }
 
 void CallbackStack::init(CallbackStack** first)
 {
     // The stacks are chained, so we start by setting this to null as terminator.
     *first = 0;
     *first = new CallbackStack(first);
 }
 
 void CallbackStack::shutdown(CallbackStack** first)
@@ skipping 253 matching lines @@
     {
         Heap::pushWeakCellPointerCallback(cell, callback);
     }
 };
 
 void Heap::init()
 {
     ThreadState::init();
     CallbackStack::init(&s_markingStack);
     CallbackStack::init(&s_weakCallbackStack);
+    s_heapDoesNotContainCache = new HeapDoesNotContainCache();
     s_markingVisitor = new MarkingVisitor();
 }
 
 void Heap::shutdown()
 {
     s_shutdownCalled = true;
     ThreadState::shutdownHeapIfNecessary();
 }
 
 void Heap::doShutdown()
 {
     // We don't want to call doShutdown() twice.
     if (!s_markingVisitor)
         return;
 
     ASSERT(!ThreadState::isAnyThreadInGC());
     ASSERT(!ThreadState::attachedThreads().size());
     delete s_markingVisitor;
     s_markingVisitor = 0;
+    delete s_heapDoesNotContainCache;
+    s_heapDoesNotContainCache = 0;
     CallbackStack::shutdown(&s_weakCallbackStack);
     CallbackStack::shutdown(&s_markingStack);
     ThreadState::shutdown();
 }
 
 BaseHeapPage* Heap::contains(Address address)
 {
     ASSERT(ThreadState::isAnyThreadInGC());
     ThreadState::AttachedThreadStateSet& threads = ThreadState::attachedThreads();
     for (ThreadState::AttachedThreadStateSet::iterator it = threads.begin(), end = threads.end(); it != end; ++it) {
         BaseHeapPage* page = (*it)->contains(address);
         if (page)
             return page;
     }
     return 0;
 }
 
 Address Heap::checkAndMarkPointer(Visitor* visitor, Address address)
 {
     ASSERT(ThreadState::isAnyThreadInGC());
-    if (!address)
+
+#ifdef NDEBUG
+    if (s_heapDoesNotContainCache->lookup(address))
         return 0;
+#endif
 
     ThreadState::AttachedThreadStateSet& threads = ThreadState::attachedThreads();
     for (ThreadState::AttachedThreadStateSet::iterator it = threads.begin(), end = threads.end(); it != end; ++it) {
         if ((*it)->checkAndMarkPointer(visitor, address)) {
-            // Pointer found and marked.
+            // Pointer was in a page of that thread. If it actually pointed
+            // into an object then that object was found and marked.
+            ASSERT(!s_heapDoesNotContainCache->lookup(address));
             return address;
         }
     }
+
+#ifdef NDEBUG
+    s_heapDoesNotContainCache->addEntry(address, true);
+#else
+    if (!s_heapDoesNotContainCache->lookup(address))
+        s_heapDoesNotContainCache->addEntry(address, true);
+#endif
     return 0;
 }
 
 #if ENABLE(GC_TRACING)
 const GCInfo* Heap::findGCInfo(Address address)
 {
     ThreadState::AttachedThreadStateSet& threads = ThreadState::attachedThreads();
     for (ThreadState::AttachedThreadStateSet::iterator it = threads.begin(), end = threads.end(); it != end; ++it) {
         if (const GCInfo* gcInfo = (*it)->findGCInfo(address)) {
             return gcInfo;
@@ skipping 140 matching lines @@
 
 // Force template instantiations for the types that we need.
 template class HeapPage<FinalizedHeapObjectHeader>;
 template class HeapPage<HeapObjectHeader>;
 template class ThreadHeap<FinalizedHeapObjectHeader>;
 template class ThreadHeap<HeapObjectHeader>;
 
 Visitor* Heap::s_markingVisitor;
 CallbackStack* Heap::s_markingStack;
 CallbackStack* Heap::s_weakCallbackStack;
+HeapDoesNotContainCache* Heap::s_heapDoesNotContainCache;
 bool Heap::s_shutdownCalled = false;
 }