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);

[Mads Ager (chromium), 2014/10/01 11:29:01]

Can we use another name than decommit/commit here? markUnused/markUsed?

Reading this I was getting confused and was looking through to see where in this
call path we actually decommit.

[zerny-chromium, 2014/10/01 12:05:34]

Done.

+        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());
 
         // 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);
@@ skipping 63 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;
+        return (address - base()) / blinkPageSize;

[zerny-chromium, 2014/10/01 10:34:59]

This was incorrect. Forgot to add the guard page to the base. Uploaded a new
patch.

[zerny-chromium, 2014/10/01 11:06:33]

No, it is correct. The first guard page is part of the first page. Sorry for the
noise. Reverted that but kept the modulo assert for good measure.

+    }
+
+    bool m_isLargePage;
+    bool m_committed[blinkPagesPerRegion];

[zerny-chromium, 2014/10/01 09:28:54]

Regarding PageMemory state in the region, it seems like we should restructure
the PageMemoryRegion/PageMemory relationship so that the region owns the page
memory and sets it up on allocation instead of this happening from the outside
via setupPageMemoryInRegion. For now, this seems like the smallest change that
provides the necessary state to lookup the pages of a region.

[Mads Ager (chromium), 2014/10/01 11:29:01]

Should we use slightly different terminology here? m_inUse?

[zerny-chromium, 2014/10/01 12:05:34]

Done.

     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);
         // 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?

[zerny-chromium, 2014/10/01 09:28:54]

This issue changes the objects which might be marked in a conservative scan.
Right now a conservatively found pointer to a terminated thread will be marked
(in the orphan pool) whereas it would not be before. It seems that it is better
to just mark the object thereby retaining the page in the orphan pool, but we
could get the previous behavior by checking if
page->threadState()->isTerminating()

[Mads Ager (chromium), 2014/10/01 11:29:01]

My gut reaction is that it would be best to filter them out. We don't want to
keep pages around and mapped just because they are hit by what looks like
pointers on the stack. I don't think it actually matters much though. In
practice we get a precise GC often in any case which will free up the pages kept
alive by conservative stack scanning.

[zerny-chromium, 2014/10/01 12:05:34]

As discussed offline, we will mark the pointer on a orphaned page since it will
still be reclaimed on the next precise GC and could prevent a (far fetched
programming error induced) use-after-free possibility.

+        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());

[Mads Ager (chromium), 2014/10/01 11:29:00]

Nit: Maybe just introduced a regionTreeMutex that is only ever taken on access
to the region tree? It is easier to reason about a mutex that is only used for
one thing.

[zerny-chromium, 2014/10/01 12:05:34]

Done.

+    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.

[Mads Ager (chromium), 2014/10/01 11:29:01]

Can we add an assert here to trigger if we ever attempt to add a page memory
region when all other threads are not stopped? Something like
ASSERT(ThreadState::isAnyThreadInGC()).

[zerny-chromium, 2014/10/01 12:05:34]

Done.

+    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)

[Mads Ager (chromium), 2014/10/01 11:29:01]

ASSERT(newTree) instead? Do we ever actually want to call this with a null
pointer? If 'new' fails we are out of memory and cannot continue anyway and will
get a null pointer crash on the next line.

[zerny-chromium, 2014/10/01 12:05:34]

I use the possibility of adding a null in RegionTree::remove when adding the
possibly empty left and right children of a removed node. I'll move the null
check back there and assert non-null here instead. 

+        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;
+    }
+    *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) {
+        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;
+
 }