Oilpan: Replace the positive heap-contains cache with a binary search tree of memory regions.

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 107 matching lines @@
         , m_size(size)
     {
         ASSERT(size > 0);
     }
 
     bool contains(Address addr) const
     {
         return m_base <= addr && addr < (m_base + m_size);
     }
 
-
     bool contains(const MemoryRegion& other) const
     {
         return contains(other.m_base) && contains(other.m_base + other.m_size - 1);
     }
 
     void release()
     {
 #if OS(POSIX)
         int err = munmap(m_base, m_size);
         RELEASE_ASSERT(!err);
@@ skipping 41 matching lines @@
 // whole. The PageMemoryRegion allows us to do that by keeping track
 // of the number of pages using it in order to be able to release all
 // of the virtual address space when there are no more pages using it.
 class PageMemoryRegion : public MemoryRegion {
 public:
     ~PageMemoryRegion()
     {
         release();
     }
 
-    void pageRemoved()
+    void pageDeleted(Address page)
     {
-        if (!--m_numPages)
+        decommitPage(page);
+        if (!--m_numPages) {
+            Heap::removePageMemoryRegion(this);
             delete this;
+        }
+    }
+
+    void commitPage(Address page)
+    {
+        ASSERT(!m_committed[index(page)]);
+        m_committed[index(page)] = true;
+    }
+
+    void decommitPage(Address page)
+    {
+        m_committed[index(page)] = false;
     }
 
     static PageMemoryRegion* allocate(size_t size, unsigned numPages)
     {
         ASSERT(Heap::heapDoesNotContainCacheIsEmpty());

[wibling-chromium, 2014/10/01 13:12:16]

NIT: It would be nice with an ASSERT here checking that size is divisible by
numPages and also that numPages is <= blinkPagesPerRegion since we don't support
anymore.

[zerny-chromium, 2014/10/01 14:19:55]

Sure. Added the slightly tighter:
        ASSERT(numPages == 1 || numPages == blinkPagesPerRegion);
        ASSERT(numPages == 1 || size % blinkPageSize == numPages);

 
         // Compute a random blink page aligned address for the page memory
         // region and attempt to get the memory there.
         Address randomAddress = reinterpret_cast<Address>(WTF::getRandomPageBase());
         Address alignedRandomAddress = roundToBlinkPageBoundary(randomAddress);
 
 #if OS(POSIX)
         Address base = static_cast<Address>(mmap(alignedRandomAddress, size, PROT_NONE, MAP_ANON | MAP_PRIVATE, -1, 0));
         RELEASE_ASSERT(base != MAP_FAILED);
         if (base == roundToBlinkPageBoundary(base))
@@ skipping 58 matching lines @@
 
         // FIXME: If base is by accident blink page size aligned
         // here then we can create two pages out of reserved
         // space. Do this.
         Address alignedBase = roundToBlinkPageBoundary(base);
 
         return new PageMemoryRegion(alignedBase, size, numPages);
 #endif
     }
 
+    BaseHeapPage* pageFromAddress(Address address)
+    {
+        ASSERT(contains(address));
+        if (!m_committed[index(address)])
+            return 0;
+        if (m_isLargePage)
+            return pageHeaderFromObject(base());
+        return pageHeaderFromObject(address);
+    }
+
 private:
     PageMemoryRegion(Address base, size_t size, unsigned numPages)
         : MemoryRegion(base, size)
+        , m_isLargePage(numPages == 1)
         , m_numPages(numPages)
     {
+        for (size_t i = 0; i < blinkPagesPerRegion; ++i)
+            m_committed[i] = false;
     }
 
+    unsigned index(Address address)
+    {
+        ASSERT(contains(address));
+        if (m_isLargePage)
+            return 0;
+        size_t offset = blinkPageAddress(address) - base();
+        ASSERT(offset % blinkPageSize == 0);
+        return offset / blinkPageSize;
+    }
+
+    bool m_isLargePage;
+    bool m_committed[blinkPagesPerRegion];
     unsigned m_numPages;
 };
 
 // Representation of the memory used for a Blink heap page.
 //
 // The representation keeps track of two memory regions:
 //
 // 1. The virtual memory reserved from the system in order to be able
 //    to free all the virtual memory reserved. Multiple PageMemory
 //    instances can share the same reserved memory region and
 //    therefore notify the reserved memory region on destruction so
 //    that the system memory can be given back when all PageMemory
 //    instances for that memory are gone.
 //
 // 2. The writable memory (a sub-region of the reserved virtual
 //    memory region) that is used for the actual heap page payload.
 //
 // Guard pages are created before and after the writable memory.
 class PageMemory {
 public:
     ~PageMemory()
     {
         __lsan_unregister_root_region(m_writable.base(), m_writable.size());
-        m_reserved->pageRemoved();
+        m_reserved->pageDeleted(writableStart());
     }
 
-    bool commit() WARN_UNUSED_RETURN { return m_writable.commit(); }
-    void decommit() { m_writable.decommit(); }
+    bool commit() WARN_UNUSED_RETURN
+    {
+        m_reserved->commitPage(writableStart());
+        return m_writable.commit();
+    }
+
+    void decommit()
+    {
+        m_reserved->decommitPage(writableStart());
+        m_writable.decommit();
+    }
+
+    PageMemoryRegion* region() { return m_reserved; }
 
     Address writableStart() { return m_writable.base(); }
 
     static PageMemory* setupPageMemoryInRegion(PageMemoryRegion* region, size_t pageOffset, size_t payloadSize)
     {
         // Setup the payload one OS page into the page memory. The
         // first os page is the guard page.
         Address payloadAddress = region->base() + pageOffset + osPageSize();
         return new PageMemory(region, MemoryRegion(payloadAddress, payloadSize));
     }
@@ skipping 280 matching lines @@
 ThreadHeap<Header>::~ThreadHeap()
 {
     ASSERT(!m_firstPage);
     ASSERT(!m_firstLargeHeapObject);
 }
 
 template<typename Header>
 void ThreadHeap<Header>::cleanupPages()
 {
     clearFreeLists();
-    flushHeapContainsCache();
 
     // Add the ThreadHeap's pages to the orphanedPagePool.
     for (HeapPage<Header>* page = m_firstPage; page; page = page->m_next)
         Heap::orphanedPagePool()->addOrphanedPage(m_index, page);
     m_firstPage = 0;
 
     for (LargeHeapObject<Header>* largeObject = m_firstLargeHeapObject; largeObject; largeObject = largeObject->m_next)
         Heap::orphanedPagePool()->addOrphanedPage(m_index, largeObject);
     m_firstLargeHeapObject = 0;
 }
@@ skipping 295 matching lines @@
 
     // 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);
+    m_threadState->allocatedRegionsSinceLastGC().append(pageMemory->region());
     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);
 
     if (object->terminating()) {
         ASSERT(ThreadState::current()->isTerminating());
@@ skipping 183 matching lines @@
     // When adding a page to the ThreadHeap using HeapObjectHeaders store the GCInfo on the heap
     // since it is the same for all objects
     ASSERT(gcInfo);
     allocatePage(gcInfo);
 }
 
 template <typename Header>
 void ThreadHeap<Header>::removePageFromHeap(HeapPage<Header>* page)
 {
     MutexLocker locker(m_threadState->sweepMutex());
-    flushHeapContainsCache();
     if (page->terminating()) {
         // The thread is shutting down so this page is being removed as part
         // of a thread local GC. In that case the page could be accessed in the
         // next global GC either due to a dead object being traced via a
         // conservative pointer or due to a programming error where an object
         // in another thread heap keeps a dangling pointer to this object.
         // To guard against this we put the page in the orphanedPagePool to
         // ensure it is still reachable. After the next global GC it can be
         // decommitted and moved to the page pool assuming no rogue/dangling
         // pointers refer to it.
@@ skipping 13 matching lines @@
     // We continue allocating page memory until we succeed in getting one.
     // Since the FreePagePool is global other threads could use all the
     // newly allocated page memory before this thread calls takeFreePage.
     while (!pageMemory) {
         // Allocate a memory region for blinkPagesPerRegion pages that
         // will each have the following layout.
         //
         //    [ guard os page | ... payload ... | guard os page ]
         //    ^---{ aligned to blink page size }
         PageMemoryRegion* region = PageMemoryRegion::allocate(blinkPageSize * blinkPagesPerRegion, blinkPagesPerRegion);
+        m_threadState->allocatedRegionsSinceLastGC().append(region);

[wibling-chromium, 2014/10/01 13:12:16]

NIT: Perhaps add a comment about the race we discussed where a thread steals all
the pages and subsequently terminates before a GC has propagated this region to
the tree.

[zerny-chromium, 2014/10/01 14:19:55]

Mads suggested rewriting so we always take at least one page and only then add
to the pool. This way the (probably purely theoretic) race is eliminated.

         // Setup the PageMemory object for each of the pages in the
         // region.
         size_t offset = 0;
         for (size_t i = 0; i < blinkPagesPerRegion; i++) {
             Heap::freePagePool()->addFreePage(m_index, PageMemory::setupPageMemoryInRegion(region, offset, blinkPagePayloadSize()));
             offset += blinkPageSize;
         }
         pageMemory = Heap::freePagePool()->takeFreePage(m_index);
     }
     HeapPage<Header>* page = new (pageMemory->writableStart()) HeapPage<Header>(pageMemory, this, gcInfo);
@@ skipping 546 matching lines @@
     }
 
     if (json) {
         json->setInteger("class", tag);
         json->setInteger("size", header->size());
         json->setInteger("isMarked", isMarked());
     }
 }
 #endif
 
-template<typename Entry>
-void HeapExtentCache<Entry>::flush()
+void HeapDoesNotContainCache::flush()
 {
     if (m_hasEntries) {
         for (int i = 0; i < numberOfEntries; i++)
-            m_entries[i] = Entry();
+            m_entries[i] = 0;
         m_hasEntries = false;
     }
 }
 
-template<typename Entry>
-size_t HeapExtentCache<Entry>::hash(Address address)
+size_t HeapDoesNotContainCache::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.
 }
 
-template<typename Entry>
-typename Entry::LookupResult HeapExtentCache<Entry>::lookup(Address address)
+bool HeapDoesNotContainCache::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();
+    if (m_entries[index] == cachePage)
+        return m_entries[index];
+    if (m_entries[index + 1] == cachePage)
+        return m_entries[index + 1];
     return 0;
 }
 
-template<typename Entry>
-void HeapExtentCache<Entry>::addEntry(Address address, typename Entry::LookupResult entry)
+void HeapDoesNotContainCache::addEntry(Address address)
 {
     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, 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);
+    m_entries[index] = cachePage;
 }
 
 void Heap::flushHeapDoesNotContainCache()
 {
     s_heapDoesNotContainCache->flush();
 }
 
 // The marking mutex is used to ensure sequential access to data
 // structures during marking. The marking mutex needs to be acquired
 // during marking when elements are taken from the global marking
@@ skipping 282 matching lines @@
     delete s_orphanedPagePool;
     s_orphanedPagePool = 0;
     delete s_weakCallbackStack;
     s_weakCallbackStack = 0;
     delete s_postMarkingCallbackStack;
     s_postMarkingCallbackStack = 0;
     delete s_markingStack;
     s_markingStack = 0;
     delete s_ephemeronStack;
     s_ephemeronStack = 0;
+    delete s_regionTree;
+    s_regionTree = 0;
     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)
@@ skipping 11 matching lines @@
 
 Address Heap::checkAndMarkPointer(Visitor* visitor, Address address)
 {
     ASSERT(ThreadState::isAnyThreadInGC());
 
 #if !ENABLE(ASSERT)
     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 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));
-            s_lastGCWasConservative = true;
-            return address;
-        }
+    if (BaseHeapPage* page = lookup(address)) {
+        ASSERT(page->contains(address));
+        ASSERT(!s_heapDoesNotContainCache->lookup(address));
+        // TODO: What if the thread owning this page is terminating?
+        page->checkAndMarkPointer(visitor, address);
+        // TODO: We only need to set the conservative flag if checkAndMarkPointer actually marked the pointer.
+        s_lastGCWasConservative = true;
+        return address;
     }
 
 #if !ENABLE(ASSERT)
-    s_heapDoesNotContainCache->addEntry(address, true);
+    s_heapDoesNotContainCache->addEntry(address);
 #else
     if (!s_heapDoesNotContainCache->lookup(address))
-        s_heapDoesNotContainCache->addEntry(address, true);
+        s_heapDoesNotContainCache->addEntry(address);
 #endif
     return 0;
 }
 
 #if ENABLE(GC_PROFILE_MARKING)
 const GCInfo* Heap::findGCInfo(Address address)
 {
     return ThreadState::findGCInfoFromAllThreads(address);
 }
 #endif
@@ skipping 537 matching lines @@
 
     HeaderType* header = HeaderType::fromPayload(address);
     header->checkHeader();
 
     const GCInfo* gcInfo = header->gcInfo();
     int heapIndex = HeapTraits::index(gcInfo->hasFinalizer());
     HeapType* heap = static_cast<HeapType*>(state->heap(heapIndex));
     heap->promptlyFreeObject(header);
 }
 
+BaseHeapPage* Heap::lookup(Address address)
+{
+    if (!s_regionTree)
+        return 0;
+    if (PageMemoryRegion* region = s_regionTree->lookup(address))
+        return region->pageFromAddress(address);
+    return 0;
+}
+
+void Heap::removePageMemoryRegion(PageMemoryRegion* region)
+{
+    // Deletion of large objects (and thus their region) can happen concurrently
+    // on sweeper threads. Removal can also happen during thread shutdown, but
+    // that case is safe. Regardless, we make removal mutually exclusive and
+    // reuse the marking mutex which is not in use during any of the two cases.
+    MutexLocker locker(markingMutex());
+    RegionTree::remove(region, &s_regionTree);
+}
+
+void Heap::addPageMemoryRegion(PageMemoryRegion* region)
+{
+    // No locking because regions are only added in ThreadState::prepareForGC which is in a GCScope.
+    RegionTree::add(new RegionTree(region), &s_regionTree);
+}
+
+PageMemoryRegion* Heap::RegionTree::lookup(Address address)
+{
+    RegionTree* current = s_regionTree;
+    while (current) {
+        Address base = current->m_region->base();
+        if (address < base) {
+            current = current->m_left;
+            continue;
+        }
+        if (address >= base + current->m_region->size()) {
+            current = current->m_right;
+            continue;
+        }
+        ASSERT(current->m_region->contains(address));
+        return current->m_region;
+    }
+    return 0;
+}
+
+void Heap::RegionTree::add(RegionTree* newTree, RegionTree** context)
+{
+    if (!newTree)
+        return;
+    Address base = newTree->m_region->base();
+    for (RegionTree* current = *context; current; current = *context) {
+        context = (base < current->m_region->base()) ? &current->m_left : &current->m_right;

[wibling-chromium, 2014/10/01 13:12:16]

You could make this a real if and add an assert in the else case to check "base"
is not contained in current.

[zerny-chromium, 2014/10/01 14:19:55]

Are you OK with keeping the if-expr and unconditionally asserting
!current->m_region->contains(base) ?

+    }
+    *context = newTree;
+}
+
+void Heap::RegionTree::remove(PageMemoryRegion* region, RegionTree** context)
+{
+    ASSERT(region);
+    ASSERT(context);
+    Address base = region->base();
+    RegionTree* current = *context;
+    ASSERT(current);
+    while (region != current->m_region) {

[wibling-chromium, 2014/10/01 13:12:16]

NIT: Why the "while" here instead of the for loop used above?

[zerny-chromium, 2014/10/01 14:19:55]

current is needed outside and the assert structure is asserting on current. I've
rewritten to a for-loop with an empty init (preferring to initialize the
variable immediately) and let the assert be on *context.

Better?

+        context = (base < current->m_region->base()) ? &current->m_left : &current->m_right;
+        current = *context;
+        ASSERT(current);
+    }
+    *context = 0;
+    add(current->m_left, context);
+    add(current->m_right, context);
+    current->m_left = 0;
+    current->m_right = 0;
+    delete current;
+}
+
 // 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;
 Vector<OwnPtr<blink::WebThread> >* Heap::s_markingThreads;
 CallbackStack* Heap::s_markingStack;
 CallbackStack* Heap::s_postMarkingCallbackStack;
 CallbackStack* Heap::s_weakCallbackStack;
 CallbackStack* Heap::s_ephemeronStack;
 HeapDoesNotContainCache* Heap::s_heapDoesNotContainCache;
 bool Heap::s_shutdownCalled = false;
 bool Heap::s_lastGCWasConservative = false;
 FreePagePool* Heap::s_freePagePool;
 OrphanedPagePool* Heap::s_orphanedPagePool;
+Heap::RegionTree* Heap::s_regionTree = 0;
+
 }