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)
+        markPageUnused(page);
+        if (!--m_numPages) {
+            Heap::removePageMemoryRegion(this);
             delete this;
+        }
+    }
+
+    void markPageUsed(Address page)
+    {
+        ASSERT(!m_inUse[index(page)]);
+        m_inUse[index(page)] = true;
+    }
+
+    void markPageUnused(Address page)
+    {
+        m_inUse[index(page)] = false;
     }
 
     static PageMemoryRegion* allocate(size_t size, unsigned numPages)
     {
         ASSERT(Heap::heapDoesNotContainCacheIsEmpty());
+        ASSERT(numPages == 1 || numPages == blinkPagesPerRegion);
+        ASSERT(numPages == 1 || size % blinkPageSize == numPages);

[haraken, 2014/10/02 02:31:35]

Can we add a comment and mention that 'numPages == 1' means a large object?

Or a slightly better approach might be to introduce helper methods like
PageMemoryRegion::allocateNormalPages() and
PageMemoryRegion::allocateLargeObject().

[zerny-chromium, 2014/10/02 07:48:42]

Done.

 
         // 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_inUse[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_inUse[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_inUse[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(); }
+    WARN_UNUSED_RETURN bool commit()
+    {
+        m_reserved->markPageUsed(writableStart());
+        return m_writable.commit();
+    }
+
+    void decommit()
+    {
+        m_reserved->markPageUnused(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.
         Heap::orphanedPagePool()->addOrphanedPage(m_index, page);
     } else {
         PageMemory* memory = page->storage();
         page->~HeapPage<Header>();
         Heap::freePagePool()->addFreePage(m_index, memory);
     }
 }
 
 template<typename Header>
 void ThreadHeap<Header>::allocatePage(const GCInfo* gcInfo)
 {
     Heap::flushHeapDoesNotContainCache();
     PageMemory* pageMemory = Heap::freePagePool()->takeFreePage(m_index);
-    // 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.
+    // We continue allocating page memory until we succeed in committing one.
     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);
+
         // 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()));
+            PageMemory* memory = PageMemory::setupPageMemoryInRegion(region, offset, blinkPagePayloadSize());
+            // Take the first possible page ensuring that this thread actually
+            // gets a page and add the rest to the page pool.
+            if (!pageMemory) {
+                if (memory->commit())
+                    pageMemory = memory;
+                else
+                    delete memory;
+            } else {
+                Heap::freePagePool()->addFreePage(m_index, memory);
+            }

[haraken, 2014/10/02 02:31:35]

Probably a simpler way to do this would be just to rewrite the previous code to:

Before:
  pageMemory = Heap::freePagePool()->takeFreePage(m_index);

After:
  while (!pageMemory)
    pageMemory = Heap::freePagePool()->takeFreePage(m_index);

[zerny-chromium, 2014/10/02 07:48:42]

That won't eliminate the chance that the ThreadState allocating the
PageMemoryRegion will not actually get committed page on that region. It could
happen that after adding the pages to the pool some other threads grab them
before we get to the takeFreePage call. The new (and slightly more complicated)
code avoids this by not adding the first committed page to the pool at all. 

[haraken, 2014/10/02 07:51:03]

Makes sense!

             offset += blinkPageSize;
         }
-        pageMemory = Heap::freePagePool()->takeFreePage(m_index);
     }
     HeapPage<Header>* page = new (pageMemory->writableStart()) HeapPage<Header>(pageMemory, this, gcInfo);
     // Use a separate list for pages allocated during sweeping to make
     // sure that we do not accidentally sweep objects that have been
     // allocated during sweeping.
     if (m_threadState->isSweepInProgress()) {
         if (!m_lastPageAllocatedDuringSweeping)
             m_lastPageAllocatedDuringSweeping = page;
         page->link(&m_firstPageAllocatedDuringSweeping);
     } else {
@@ skipping 538 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.

[haraken, 2014/10/02 02:31:35]

TODO => FIXME

[zerny-chromium, 2014/10/02 07:48:42]

Done. And removed the first TODO because it is safer to just mark the orphaned
objects (the won't be traced further because they are filtered when popping from
the marking stack).

+        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;
+}
+
+static Mutex& regionTreeMutex()
+{
+    AtomicallyInitializedStatic(Mutex&, mutex = *new Mutex);
+    return mutex;
+}
+
+void Heap::removePageMemoryRegion(PageMemoryRegion* region)
+{
+    // Deletion of large objects (and thus their region) can happen concurrently

[haraken, 2014/10/02 02:31:35]

their region => their regions

[zerny-chromium, 2014/10/02 07:48:42]

Done.

+    // on sweeper threads. Removal can also happen during thread shutdown, but
+    // that case is safe. Regardless, we make all removals mutually exclusive.
+    MutexLocker locker(regionTreeMutex());
+    RegionTree::remove(region, &s_regionTree);
+}
+
+void Heap::addPageMemoryRegion(PageMemoryRegion* region)
+{
+    ASSERT(ThreadState::isAnyThreadInGC());
+    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)
+{
+    ASSERT(newTree);
+    Address base = newTree->m_region->base();
+    for (RegionTree* current = *context; current; current = *context) {
+        ASSERT(!current->m_region->contains(base));
+        context = (base < current->m_region->base()) ? &current->m_left : &current->m_right;
+    }
+    *context = newTree;
+}
+
+void Heap::RegionTree::remove(PageMemoryRegion* region, RegionTree** context)
+{
+    ASSERT(region);
+    ASSERT(context);
+    ASSERT(*context);
+    Address base = region->base();
+    RegionTree* current = *context;
+    for ( ; region != current->m_region; current = *context) {
+        context = (base < current->m_region->base()) ? &current->m_left : &current->m_right;
+        ASSERT(*context);
+    }
+    *context = 0;
+    if (current->m_left) {
+        add(current->m_left, context);
+        current->m_left = 0;
+    }
+    if (current->m_right) {
+        add(current->m_right, context);
+        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;
+
 }