Unreviewed, rolling out r197955.
[WebKit-https.git] / Source / bmalloc / bmalloc / Heap.cpp
index 0802d54..c6cc510 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
  */
 
-#include "BoundaryTagInlines.h"
 #include "Heap.h"
+#include "BumpAllocator.h"
 #include "LargeChunk.h"
-#include "Line.h"
-#include "MediumChunk.h"
-#include "Page.h"
+#include "LargeObject.h"
 #include "PerProcess.h"
 #include "SmallChunk.h"
-#include "XLargeChunk.h"
-#include "XSmallChunk.h"
+#include "SmallLine.h"
+#include "SmallPage.h"
 #include <thread>
 
 namespace bmalloc {
 
-static inline void sleep(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds duration)
+Heap::Heap(std::lock_guard<StaticMutex>&)
+    : m_largeObjects(VMState::HasPhysical::True)
+    , m_isAllocatingPages(false)
+    , m_scavenger(*this, &Heap::concurrentScavenge)
 {
-    if (duration == std::chrono::milliseconds(0))
-        return;
-    
-    lock.unlock();
-    std::this_thread::sleep_for(duration);
-    lock.lock();
+    initializeLineMetadata();
 }
 
-Heap::Heap(std::lock_guard<StaticMutex>&)
-    : m_isAllocatingPages(false)
-    , m_scavenger(*this, &Heap::concurrentScavenge)
+void Heap::initializeLineMetadata()
 {
+    // We assume that m_smallLineMetadata is zero-filled.
+
+    for (size_t size = alignment; size <= smallMax; size += alignment) {
+        size_t sizeClass = bmalloc::sizeClass(size);
+        auto& metadata = m_smallLineMetadata[sizeClass];
+
+        size_t object = 0;
+        size_t line = 0;
+        while (object < vmPageSize) {
+            line = object / smallLineSize;
+            size_t leftover = object % smallLineSize;
+
+            size_t objectCount;
+            size_t remainder;
+            divideRoundingUp(smallLineSize - leftover, size, objectCount, remainder);
+
+            metadata[line] = { static_cast<unsigned short>(leftover), static_cast<unsigned short>(objectCount) };
+
+            object += objectCount * size;
+        }
+
+        // Don't allow the last object in a page to escape the page.
+        if (object > vmPageSize) {
+            BASSERT(metadata[line].objectCount);
+            --metadata[line].objectCount;
+        }
+    }
 }
 
 void Heap::concurrentScavenge()
@@ -58,191 +79,361 @@ void Heap::concurrentScavenge()
     std::unique_lock<StaticMutex> lock(PerProcess<Heap>::mutex());
     scavenge(lock, scavengeSleepDuration);
 }
-    
+
 void Heap::scavenge(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
 {
-    scavengeXSmallPages(lock, sleepDuration);
+    waitUntilFalse(lock, sleepDuration, m_isAllocatingPages);
+
     scavengeSmallPages(lock, sleepDuration);
-    scavengeMediumPages(lock, sleepDuration);
-    scavengeLargeRanges(lock, sleepDuration);
+    scavengeLargeObjects(lock, sleepDuration);
+    scavengeXLargeObjects(lock, sleepDuration);
 
     sleep(lock, sleepDuration);
 }
 
 void Heap::scavengeSmallPages(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
 {
-    while (1) {
-        if (m_isAllocatingPages) {
-            m_isAllocatingPages = false;
-
-            sleep(lock, sleepDuration);
-            continue;
-        }
-
-        if (!m_smallPages.size())
-            return;
+    while (!m_smallPages.isEmpty()) {
         m_vmHeap.deallocateSmallPage(lock, m_smallPages.pop());
+        waitUntilFalse(lock, sleepDuration, m_isAllocatingPages);
     }
 }
 
-void Heap::scavengeXSmallPages(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
+void Heap::scavengeLargeObjects(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
 {
-    while (1) {
-        if (m_isAllocatingPages) {
-            m_isAllocatingPages = false;
+    while (LargeObject largeObject = m_largeObjects.takeGreedy()) {
+        m_vmHeap.deallocateLargeObject(lock, largeObject);
+        waitUntilFalse(lock, sleepDuration, m_isAllocatingPages);
+    }
+}
 
-            sleep(lock, sleepDuration);
-            continue;
-        }
+void Heap::scavengeXLargeObjects(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
+{
+    while (XLargeRange range = m_xLargeMap.takePhysical()) {
+        lock.unlock();
+        vmDeallocatePhysicalPagesSloppy(range.begin(), range.size());
+        lock.lock();
+        
+        range.setVMState(VMState::Virtual);
+        m_xLargeMap.addVirtual(range);
 
-        if (!m_xSmallPages.size())
-            return;
-        m_vmHeap.deallocateXSmallPage(lock, m_xSmallPages.pop());
+        waitUntilFalse(lock, sleepDuration, m_isAllocatingPages);
     }
+
+    m_xLargeMap.shrinkToFit();
 }
 
-void Heap::scavengeMediumPages(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
+void Heap::allocateSmallBumpRanges(std::lock_guard<StaticMutex>& lock, size_t sizeClass, BumpAllocator& allocator, BumpRangeCache& rangeCache)
 {
-    while (1) {
-        if (m_isAllocatingPages) {
-            m_isAllocatingPages = false;
+    BASSERT(!rangeCache.size());
+    SmallPage* page = allocateSmallPage(lock, sizeClass);
+    SmallLine* lines = page->begin();
+    BASSERT(page->hasFreeLines(lock));
+
+    // Find a free line.
+    for (size_t lineNumber = 0; lineNumber < smallLineCount; ++lineNumber) {
+        if (lines[lineNumber].refCount(lock))
+            continue;
 
-            sleep(lock, sleepDuration);
+        LineMetadata& lineMetadata = m_smallLineMetadata[sizeClass][lineNumber];
+        if (!lineMetadata.objectCount)
             continue;
-        }
 
-        if (!m_mediumPages.size())
+        // In a fragmented page, some free ranges might not fit in the cache.
+        if (rangeCache.size() == rangeCache.capacity()) {
+            m_smallPagesWithFreeLines[sizeClass].push(page);
+            BASSERT(allocator.canAllocate());
             return;
-        m_vmHeap.deallocateMediumPage(lock, m_mediumPages.pop());
-    }
-}
+        }
 
-void Heap::scavengeLargeRanges(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
-{
-    while (1) {
-        if (m_isAllocatingPages) {
-            m_isAllocatingPages = false;
+        char* begin = lines[lineNumber].begin() + lineMetadata.startOffset;
+        unsigned short objectCount = lineMetadata.objectCount;
+        lines[lineNumber].ref(lock, lineMetadata.objectCount);
+        page->ref(lock);
 
-            sleep(lock, sleepDuration);
-            continue;
+        // Merge with subsequent free lines.
+        while (++lineNumber < smallLineCount) {
+            if (lines[lineNumber].refCount(lock))
+                break;
+
+            LineMetadata& lineMetadata = m_smallLineMetadata[sizeClass][lineNumber];
+            if (!lineMetadata.objectCount)
+                continue;
+
+            objectCount += lineMetadata.objectCount;
+            lines[lineNumber].ref(lock, lineMetadata.objectCount);
+            page->ref(lock);
         }
 
-        Range range = m_largeRanges.takeGreedy(vmPageSize);
-        if (!range)
-            return;
-        m_vmHeap.deallocateLargeRange(lock, range);
+        if (!allocator.canAllocate())
+            allocator.refill({ begin, objectCount });
+        else
+            rangeCache.push({ begin, objectCount });
     }
+
+    BASSERT(allocator.canAllocate());
+    page->setHasFreeLines(lock, false);
 }
 
-XSmallLine* Heap::allocateXSmallLineSlowCase(std::lock_guard<StaticMutex>& lock)
+SmallPage* Heap::allocateSmallPage(std::lock_guard<StaticMutex>& lock, size_t sizeClass)
 {
-    m_isAllocatingPages = true;
+    if (!m_smallPagesWithFreeLines[sizeClass].isEmpty())
+        return m_smallPagesWithFreeLines[sizeClass].pop();
 
-    XSmallPage* page = [this]() {
-        if (m_xSmallPages.size())
-            return m_xSmallPages.pop();
-        
-        XSmallPage* page = m_vmHeap.allocateXSmallPage();
-        vmAllocatePhysicalPages(page->begin()->begin(), vmPageSize);
+    SmallPage* page = [this, &lock]() {
+        if (!m_smallPages.isEmpty())
+            return m_smallPages.pop();
+
+        m_isAllocatingPages = true;
+        SmallPage* page = m_vmHeap.allocateSmallPage(lock);
         return page;
     }();
 
-    XSmallLine* line = page->begin();
-    for (auto it = line + 1; it != page->end(); ++it)
-        m_xSmallLines.push(it);
-
-    page->ref(lock);
-    return line;
+    page->setSizeClass(sizeClass);
+    return page;
 }
 
-SmallLine* Heap::allocateSmallLineSlowCase(std::lock_guard<StaticMutex>& lock)
+void Heap::deallocateSmallLine(std::lock_guard<StaticMutex>& lock, SmallLine* line)
 {
-    m_isAllocatingPages = true;
+    BASSERT(!line->refCount(lock));
+    SmallPage* page = SmallPage::get(line);
+    page->deref(lock);
 
-    SmallPage* page = [this]() {
-        if (m_smallPages.size())
-            return m_smallPages.pop();
-        
-        SmallPage* page = m_vmHeap.allocateSmallPage();
-        vmAllocatePhysicalPages(page->begin()->begin(), vmPageSize);
-        return page;
-    }();
+    if (!page->hasFreeLines(lock)) {
+        page->setHasFreeLines(lock, true);
+        m_smallPagesWithFreeLines[page->sizeClass()].push(page);
 
-    SmallLine* line = page->begin();
-    for (auto it = line + 1; it != page->end(); ++it)
-        m_smallLines.push(it);
+        BASSERT(page->refCount(lock));
+        return;
+    }
+
+    if (page->refCount(lock))
+        return;
 
-    page->ref(lock);
-    return line;
+    m_smallPagesWithFreeLines[page->sizeClass()].remove(page);
+    m_smallPages.push(page);
+    m_scavenger.run();
 }
 
-MediumLine* Heap::allocateMediumLineSlowCase(std::lock_guard<StaticMutex>& lock)
+inline LargeObject& Heap::splitAndAllocate(LargeObject& largeObject, size_t size)
 {
-    m_isAllocatingPages = true;
+    BASSERT(largeObject.isFree());
 
-    MediumPage* page = [this]() {
-        if (m_mediumPages.size())
-            return m_mediumPages.pop();
-        
-        MediumPage* page = m_vmHeap.allocateMediumPage();
-        vmAllocatePhysicalPages(page->begin()->begin(), vmPageSize);
-        return page;
-    }();
+    LargeObject nextLargeObject;
+
+    if (largeObject.size() - size > largeMin) {
+        std::pair<LargeObject, LargeObject> split = largeObject.split(size);
+        largeObject = split.first;
+        nextLargeObject = split.second;
+    }
 
-    MediumLine* line = page->begin();
-    for (auto it = line + 1; it != page->end(); ++it)
-        m_mediumLines.push(it);
+    largeObject.setFree(false);
 
-    page->ref(lock);
-    return line;
+    if (nextLargeObject) {
+        BASSERT(!nextLargeObject.nextCanMerge());
+        m_largeObjects.insert(nextLargeObject);
+    }
+
+    return largeObject;
 }
 
-void* Heap::allocateXLarge(std::lock_guard<StaticMutex>&, size_t size)
+inline LargeObject& Heap::splitAndAllocate(LargeObject& largeObject, size_t alignment, size_t size)
 {
-    XLargeChunk* chunk = XLargeChunk::create(size);
+    LargeObject prevLargeObject;
+    LargeObject nextLargeObject;
+
+    size_t alignmentMask = alignment - 1;
+    if (test(largeObject.begin(), alignmentMask)) {
+        size_t prefixSize = roundUpToMultipleOf(alignment, largeObject.begin() + largeMin) - largeObject.begin();
+        std::pair<LargeObject, LargeObject> pair = largeObject.split(prefixSize);
+        prevLargeObject = pair.first;
+        largeObject = pair.second;
+    }
 
-    BeginTag* beginTag = LargeChunk::beginTag(chunk->begin());
-    beginTag->setXLarge();
-    beginTag->setFree(false);
-    beginTag->setHasPhysicalPages(true);
-    
-    return chunk->begin();
+    BASSERT(largeObject.isFree());
+
+    if (largeObject.size() - size > largeMin) {
+        std::pair<LargeObject, LargeObject> split = largeObject.split(size);
+        largeObject = split.first;
+        nextLargeObject = split.second;
+    }
+
+    largeObject.setFree(false);
+
+    if (prevLargeObject) {
+        LargeObject merged = prevLargeObject.merge();
+        m_largeObjects.insert(merged);
+    }
+
+    if (nextLargeObject) {
+        LargeObject merged = nextLargeObject.merge();
+        m_largeObjects.insert(merged);
+    }
+
+    return largeObject;
 }
 
-void Heap::deallocateXLarge(std::lock_guard<StaticMutex>&, void* object)
+void* Heap::allocateLarge(std::lock_guard<StaticMutex>& lock, size_t size)
 {
-    XLargeChunk* chunk = XLargeChunk::get(object);
-    XLargeChunk::destroy(chunk);
+    BASSERT(size <= largeMax);
+    BASSERT(size >= largeMin);
+    BASSERT(size == roundUpToMultipleOf<largeAlignment>(size));
+
+    LargeObject largeObject = m_largeObjects.take(size);
+    if (!largeObject)
+        largeObject = m_vmHeap.allocateLargeObject(lock, size);
+
+    if (largeObject.vmState().hasVirtual()) {
+        m_isAllocatingPages = true;
+        // We commit before we split in order to avoid split/merge commit/decommit churn.
+        vmAllocatePhysicalPagesSloppy(largeObject.begin(), largeObject.size());
+        largeObject.setVMState(VMState::Physical);
+    }
+
+    largeObject = splitAndAllocate(largeObject, size);
+
+    return largeObject.begin();
 }
 
-void* Heap::allocateLarge(std::lock_guard<StaticMutex>&, size_t size)
+void* Heap::allocateLarge(std::lock_guard<StaticMutex>& lock, size_t alignment, size_t size, size_t unalignedSize)
 {
     BASSERT(size <= largeMax);
     BASSERT(size >= largeMin);
+    BASSERT(size == roundUpToMultipleOf<largeAlignment>(size));
+    BASSERT(unalignedSize <= largeMax);
+    BASSERT(unalignedSize >= largeMin);
+    BASSERT(unalignedSize == roundUpToMultipleOf<largeAlignment>(unalignedSize));
+    BASSERT(alignment <= largeChunkSize / 2);
+    BASSERT(alignment >= largeAlignment);
+    BASSERT(isPowerOfTwo(alignment));
+
+    LargeObject largeObject = m_largeObjects.take(alignment, size, unalignedSize);
+    if (!largeObject)
+        largeObject = m_vmHeap.allocateLargeObject(lock, alignment, size, unalignedSize);
+
+    if (largeObject.vmState().hasVirtual()) {
+        m_isAllocatingPages = true;
+        // We commit before we split in order to avoid split/merge commit/decommit churn.
+        vmAllocatePhysicalPagesSloppy(largeObject.begin(), largeObject.size());
+        largeObject.setVMState(VMState::Physical);
+    }
+
+    largeObject = splitAndAllocate(largeObject, alignment, size);
+
+    return largeObject.begin();
+}
+
+void Heap::deallocateLarge(std::lock_guard<StaticMutex>&, const LargeObject& largeObject)
+{
+    BASSERT(!largeObject.isFree());
+    largeObject.setFree(true);
     
+    LargeObject merged = largeObject.merge();
+    m_largeObjects.insert(merged);
+    m_scavenger.run();
+}
+
+void Heap::deallocateLarge(std::lock_guard<StaticMutex>& lock, void* object)
+{
+    LargeObject largeObject(object);
+    deallocateLarge(lock, largeObject);
+}
+
+void* Heap::allocateXLarge(std::lock_guard<StaticMutex>& lock, size_t alignment, size_t size)
+{
+    void* result = tryAllocateXLarge(lock, alignment, size);
+    RELEASE_BASSERT(result);
+    return result;
+}
+
+void* Heap::allocateXLarge(std::lock_guard<StaticMutex>& lock, size_t size)
+{
+    return allocateXLarge(lock, alignment, size);
+}
+
+XLargeRange Heap::splitAndAllocate(XLargeRange& range, size_t alignment, size_t size)
+{
+    XLargeRange prev;
+    XLargeRange next;
+
+    size_t alignmentMask = alignment - 1;
+    if (test(range.begin(), alignmentMask)) {
+        size_t prefixSize = roundUpToMultipleOf(alignment, range.begin()) - range.begin();
+        std::pair<XLargeRange, XLargeRange> pair = range.split(prefixSize);
+        prev = pair.first;
+        range = pair.second;
+    }
+
+    if (range.size() - size >= xLargeAlignment) {
+        size_t alignedSize = roundUpToMultipleOf<xLargeAlignment>(size);
+        std::pair<XLargeRange, XLargeRange> pair = range.split(alignedSize);
+        range = pair.first;
+        next = pair.second;
+    }
+
+    // At this point our range might contain an unused tail fragment. This is
+    // common. We can't allocate the tail fragment because it's aligned to less
+    // than xLargeAlignment. So, we pair the allocation with its tail fragment
+    // in the allocated list. This is an important optimization because it
+    // keeps the free list short, speeding up allocation and merging.
+
+    std::pair<XLargeRange, XLargeRange> allocated = range.split(roundUpToMultipleOf<vmPageSize>(size));
+    if (allocated.first.vmState().hasVirtual()) {
+        vmAllocatePhysicalPagesSloppy(allocated.first.begin(), allocated.first.size());
+        allocated.first.setVMState(VMState::Physical);
+    }
+
+    m_xLargeMap.addAllocated(prev, allocated, next);
+    return allocated.first;
+}
+
+void* Heap::tryAllocateXLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t size)
+{
+    BASSERT(isPowerOfTwo(alignment));
+    BASSERT(alignment < xLargeMax);
+
     m_isAllocatingPages = true;
 
-    Range range = m_largeRanges.take(size);
-    if (!range)
-        range = m_vmHeap.allocateLargeRange(size);
-    
-    Range leftover;
-    bool hasPhysicalPages;
-    BoundaryTag::allocate(size, range, leftover, hasPhysicalPages);
+    alignment = roundUpToMultipleOf<xLargeAlignment>(alignment);
+
+    XLargeRange range = m_xLargeMap.takeFree(alignment, size);
+    if (!range) {
+        // We allocate VM in aligned multiples to increase the chances that
+        // the OS will provide contiguous ranges that we can merge.
+        size_t alignedSize = roundUpToMultipleOf<xLargeAlignment>(size);
+
+        void* begin = tryVMAllocate(alignment, alignedSize);
+        if (!begin)
+            return nullptr;
+        range = XLargeRange(begin, alignedSize, VMState::Virtual);
+    }
+
+    return splitAndAllocate(range, alignment, size).begin();
+}
 
-    if (!!leftover)
-        m_largeRanges.insert(leftover);
+size_t Heap::xLargeSize(std::unique_lock<StaticMutex>&, void* object)
+{
+    return m_xLargeMap.getAllocated(object).size();
+}
+
+void Heap::shrinkXLarge(std::unique_lock<StaticMutex>&, const Range& object, size_t newSize)
+{
+    BASSERT(object.size() > newSize);
+
+    if (object.size() - newSize < vmPageSize)
+        return;
     
-    if (!hasPhysicalPages)
-        vmAllocatePhysicalPagesSloppy(range.begin(), range.size());
+    XLargeRange range = m_xLargeMap.takeAllocated(object.begin());
+    splitAndAllocate(range, xLargeAlignment, newSize);
 
-    return range.begin();
+    m_scavenger.run();
 }
 
-void Heap::deallocateLarge(std::lock_guard<StaticMutex>&, void* object)
+void Heap::deallocateXLarge(std::unique_lock<StaticMutex>&, void* object)
 {
-    Range range = BoundaryTag::deallocate(object);
-    m_largeRanges.insert(range);
+    XLargeRange range = m_xLargeMap.takeAllocated(object);
+    m_xLargeMap.addFree(range);
+    
     m_scavenger.run();
 }