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* allocateLargePage(size_t size)
+    {
+        return allocate(size, 1);
+    }
+
+    static PageMemoryRegion* allocateNormalPages()
+    {
+        return allocate(blinkPageSize * blinkPagesPerRegion, blinkPagesPerRegion);
+    }
+
+    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;
     }
 
     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
     }
 
-private:
-    PageMemoryRegion(Address base, size_t size, unsigned numPages)
-        : MemoryRegion(base, size)
-        , m_numPages(numPages)
-    {
-    }
-
+    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();
+    }
+
+    void markUnused() { m_reserved->markPageUnused(writableStart()); }
+
+    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));
     }
 
     // Allocate a virtual address space for one blink page with the
     // following layout:
     //
     //    [ guard os page | ... payload ... | guard os page ]
     //    ^---{ aligned to blink page size }
     //
     static PageMemory* allocate(size_t payloadSize)
     {
         ASSERT(payloadSize > 0);
 
         // Virtual memory allocation routines operate in OS page sizes.
         // Round up the requested size to nearest os page size.
         payloadSize = roundToOsPageSize(payloadSize);
 
         // Overallocate by 2 times OS page size to have space for a
         // guard page at the beginning and end of blink heap page.
         size_t allocationSize = payloadSize + 2 * osPageSize();
-        PageMemoryRegion* pageMemoryRegion = PageMemoryRegion::allocate(allocationSize, 1);
+        PageMemoryRegion* pageMemoryRegion = PageMemoryRegion::allocateLargePage(allocationSize);
         PageMemory* storage = setupPageMemoryInRegion(pageMemoryRegion, 0, payloadSize);
         RELEASE_ASSERT(storage->commit());
         return storage;
     }
 
 private:
     PageMemory(PageMemoryRegion* reserved, const MemoryRegion& writable)
         : m_reserved(reserved)
         , m_writable(writable)
     {
@@ skipping 251 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 59 matching lines @@
         delete entry;
         if (memory->commit())
             return memory;
 
         // We got some memory, but failed to commit it, try again.
         delete memory;
     }
     return 0;
 }
 
+BaseHeapPage::BaseHeapPage(PageMemory* storage, const GCInfo* gcInfo, ThreadState* state)
+    : m_storage(storage)
+    , m_gcInfo(gcInfo)
+    , m_threadState(state)
+    , m_terminating(false)
+    , m_tracedAfterOrphaned(false)
+{
+    ASSERT(isPageHeaderAddress(reinterpret_cast<Address>(this)));
+}
+
+void BaseHeapPage::markOrphaned()
+{
+    m_threadState = 0;
+    m_gcInfo = 0;
+    m_terminating = false;
+    m_tracedAfterOrphaned = false;
+    // Since we zap the page payload for orphaned pages we need to mark it as
+    // unused so a conservative pointer won't interpret the object headers.
+    storage()->markUnused();
+}
+
 OrphanedPagePool::~OrphanedPagePool()
 {
     for (int index = 0; index < NumberOfHeaps; ++index) {
         while (PoolEntry* entry = m_pool[index]) {
             m_pool[index] = entry->next;
             BaseHeapPage* page = entry->data;
             delete entry;
             PageMemory* memory = page->storage();
             ASSERT(memory);
             page->~BaseHeapPage();
@@ skipping 104 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);
+        PageMemoryRegion* region = PageMemoryRegion::allocateNormalPages();
+        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);
+            }
             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));
+        page->checkAndMarkPointer(visitor, address);
+        // FIXME: 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 543 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)
+{
+    ASSERT(ThreadState::isAnyThreadInGC());
+    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 regions) can happen concurrently
+    // 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);
+    Address base = region->base();
+    RegionTree* current = *context;
+    for ( ; current; current = *context) {
+        if (region == current->m_region)
+            break;
+        context = (base < current->m_region->base()) ? &current->m_left : &current->m_right;
+    }
+
+    // Shutdown via detachMainThread might not have populated the region tree.
+    if (!current)
+        return;
+
+    *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;
+
 }