| /* |
| * Copyright (C) 2014-2017 Apple 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: |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * |
| * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY |
| * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
| * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR |
| * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
| * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
| * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY |
| * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| #include "Heap.h" |
| |
| #include "AvailableMemory.h" |
| #include "BumpAllocator.h" |
| #include "Chunk.h" |
| #include "Environment.h" |
| #include "Gigacage.h" |
| #include "DebugHeap.h" |
| #include "PerProcess.h" |
| #include "Scavenger.h" |
| #include "SmallLine.h" |
| #include "SmallPage.h" |
| #include "VMHeap.h" |
| #include "bmalloc.h" |
| #include <thread> |
| |
| namespace bmalloc { |
| |
| Heap::Heap(HeapKind kind, std::lock_guard<StaticMutex>&) |
| : m_kind(kind) |
| , m_vmPageSizePhysical(vmPageSizePhysical()) |
| , m_scavenger(*this, &Heap::concurrentScavenge) |
| , m_debugHeap(nullptr) |
| { |
| RELEASE_BASSERT(vmPageSizePhysical() >= smallPageSize); |
| RELEASE_BASSERT(vmPageSize() >= vmPageSizePhysical()); |
| |
| initializeLineMetadata(); |
| initializePageMetadata(); |
| |
| if (PerProcess<Environment>::get()->isDebugHeapEnabled()) |
| m_debugHeap = PerProcess<DebugHeap>::get(); |
| else { |
| Gigacage::ensureGigacage(); |
| #if GIGACAGE_ENABLED |
| if (usingGigacage()) { |
| RELEASE_BASSERT(g_gigacageBasePtr); |
| m_largeFree.add(LargeRange(g_gigacageBasePtr, GIGACAGE_SIZE, 0)); |
| } |
| #endif |
| } |
| |
| PerProcess<Scavenger>::get(); |
| } |
| |
| bool Heap::usingGigacage() |
| { |
| return m_kind == HeapKind::Gigacage && g_gigacageBasePtr; |
| } |
| |
| void Heap::initializeLineMetadata() |
| { |
| size_t sizeClassCount = bmalloc::sizeClass(smallLineSize); |
| size_t smallLineCount = m_vmPageSizePhysical / smallLineSize; |
| m_smallLineMetadata.grow(sizeClassCount * smallLineCount); |
| |
| for (size_t sizeClass = 0; sizeClass < sizeClassCount; ++sizeClass) { |
| size_t size = objectSize(sizeClass); |
| LineMetadata* pageMetadata = &m_smallLineMetadata[sizeClass * smallLineCount]; |
| |
| size_t object = 0; |
| size_t line = 0; |
| while (object < m_vmPageSizePhysical) { |
| line = object / smallLineSize; |
| size_t leftover = object % smallLineSize; |
| |
| size_t objectCount; |
| size_t remainder; |
| divideRoundingUp(smallLineSize - leftover, size, objectCount, remainder); |
| |
| pageMetadata[line] = { static_cast<unsigned char>(leftover), static_cast<unsigned char>(objectCount) }; |
| |
| object += objectCount * size; |
| } |
| |
| // Don't allow the last object in a page to escape the page. |
| if (object > m_vmPageSizePhysical) { |
| BASSERT(pageMetadata[line].objectCount); |
| --pageMetadata[line].objectCount; |
| } |
| } |
| } |
| |
| void Heap::initializePageMetadata() |
| { |
| auto computePageSize = [&](size_t sizeClass) { |
| size_t size = objectSize(sizeClass); |
| if (sizeClass < bmalloc::sizeClass(smallLineSize)) |
| return m_vmPageSizePhysical; |
| |
| for (size_t pageSize = m_vmPageSizePhysical; |
| pageSize < pageSizeMax; |
| pageSize += m_vmPageSizePhysical) { |
| RELEASE_BASSERT(pageSize <= chunkSize / 2); |
| size_t waste = pageSize % size; |
| if (waste <= pageSize / pageSizeWasteFactor) |
| return pageSize; |
| } |
| |
| return pageSizeMax; |
| }; |
| |
| for (size_t i = 0; i < sizeClassCount; ++i) |
| m_pageClasses[i] = (computePageSize(i) - 1) / smallPageSize; |
| } |
| |
| void Heap::concurrentScavenge() |
| { |
| std::lock_guard<StaticMutex> lock(mutex()); |
| |
| #if BOS(DARWIN) |
| pthread_set_qos_class_self_np(PerProcess<Scavenger>::getFastCase()->requestedScavengerThreadQOSClass(), 0); |
| #endif |
| |
| if (m_isGrowing && !isUnderMemoryPressure()) { |
| m_isGrowing = false; |
| m_scavenger.runSoon(); |
| return; |
| } |
| |
| scavenge(lock); |
| } |
| |
| void Heap::scavenge(std::lock_guard<StaticMutex>&) |
| { |
| for (auto& list : m_freePages) { |
| for (auto* chunk : list) { |
| for (auto* page : chunk->freePages()) { |
| if (!page->hasPhysicalPages()) |
| continue; |
| |
| vmDeallocatePhysicalPagesSloppy(page->begin()->begin(), pageSize(&list - &m_freePages[0])); |
| |
| page->setHasPhysicalPages(false); |
| } |
| } |
| } |
| |
| for (auto& list : m_chunkCache) { |
| while (!list.isEmpty()) |
| deallocateSmallChunk(list.pop(), &list - &m_chunkCache[0]); |
| } |
| |
| for (auto& range : m_largeFree) { |
| vmDeallocatePhysicalPagesSloppy(range.begin(), range.size()); |
| |
| range.setPhysicalSize(0); |
| } |
| } |
| |
| void Heap::scheduleScavengerIfUnderMemoryPressure(size_t bytes) |
| { |
| m_scavengerBytes += bytes; |
| if (m_scavengerBytes < scavengerBytesPerMemoryPressureCheck) |
| return; |
| |
| m_scavengerBytes = 0; |
| |
| if (m_scavenger.willRun()) |
| return; |
| |
| if (!isUnderMemoryPressure()) |
| return; |
| |
| m_isGrowing = false; |
| m_scavenger.run(); |
| } |
| |
| void Heap::scheduleScavenger(size_t bytes) |
| { |
| scheduleScavengerIfUnderMemoryPressure(bytes); |
| |
| if (m_scavenger.willRunSoon()) |
| return; |
| |
| m_isGrowing = false; |
| m_scavenger.runSoon(); |
| } |
| |
| void Heap::deallocateLineCache(std::lock_guard<StaticMutex>&, LineCache& lineCache) |
| { |
| for (auto& list : lineCache) { |
| while (!list.isEmpty()) { |
| size_t sizeClass = &list - &lineCache[0]; |
| m_lineCache[sizeClass].push(list.popFront()); |
| } |
| } |
| } |
| |
| void Heap::allocateSmallChunk(std::lock_guard<StaticMutex>& lock, size_t pageClass) |
| { |
| size_t pageSize = bmalloc::pageSize(pageClass); |
| |
| Chunk* chunk = [&]() { |
| if (!m_chunkCache[pageClass].isEmpty()) |
| return m_chunkCache[pageClass].pop(); |
| |
| void* memory = allocateLarge(lock, chunkSize, chunkSize); |
| |
| Chunk* chunk = new (memory) Chunk(pageSize); |
| |
| m_objectTypes.set(chunk, ObjectType::Small); |
| |
| forEachPage(chunk, pageSize, [&](SmallPage* page) { |
| page->setHasPhysicalPages(true); |
| page->setHasFreeLines(lock, true); |
| chunk->freePages().push(page); |
| }); |
| |
| scheduleScavenger(0); |
| |
| return chunk; |
| }(); |
| |
| m_freePages[pageClass].push(chunk); |
| } |
| |
| void Heap::deallocateSmallChunk(Chunk* chunk, size_t pageClass) |
| { |
| m_objectTypes.set(chunk, ObjectType::Large); |
| |
| size_t size = m_largeAllocated.remove(chunk); |
| |
| bool hasPhysicalPages = true; |
| forEachPage(chunk, pageSize(pageClass), [&](SmallPage* page) { |
| if (!page->hasPhysicalPages()) |
| hasPhysicalPages = false; |
| }); |
| size_t physicalSize = hasPhysicalPages ? size : 0; |
| |
| m_largeFree.add(LargeRange(chunk, size, physicalSize)); |
| } |
| |
| SmallPage* Heap::allocateSmallPage(std::lock_guard<StaticMutex>& lock, size_t sizeClass, LineCache& lineCache) |
| { |
| if (!lineCache[sizeClass].isEmpty()) |
| return lineCache[sizeClass].popFront(); |
| |
| if (!m_lineCache[sizeClass].isEmpty()) |
| return m_lineCache[sizeClass].popFront(); |
| |
| m_isGrowing = true; |
| |
| SmallPage* page = [&]() { |
| size_t pageClass = m_pageClasses[sizeClass]; |
| |
| if (m_freePages[pageClass].isEmpty()) |
| allocateSmallChunk(lock, pageClass); |
| |
| Chunk* chunk = m_freePages[pageClass].tail(); |
| |
| chunk->ref(); |
| |
| SmallPage* page = chunk->freePages().pop(); |
| if (chunk->freePages().isEmpty()) |
| m_freePages[pageClass].remove(chunk); |
| |
| if (!page->hasPhysicalPages()) { |
| scheduleScavengerIfUnderMemoryPressure(pageSize(pageClass)); |
| |
| vmAllocatePhysicalPagesSloppy(page->begin()->begin(), pageSize(pageClass)); |
| page->setHasPhysicalPages(true); |
| } |
| |
| return page; |
| }(); |
| |
| page->setSizeClass(sizeClass); |
| return page; |
| } |
| |
| void Heap::deallocateSmallLine(std::lock_guard<StaticMutex>& lock, Object object, LineCache& lineCache) |
| { |
| BASSERT(!object.line()->refCount(lock)); |
| SmallPage* page = object.page(); |
| page->deref(lock); |
| |
| if (!page->hasFreeLines(lock)) { |
| page->setHasFreeLines(lock, true); |
| lineCache[page->sizeClass()].push(page); |
| } |
| |
| if (page->refCount(lock)) |
| return; |
| |
| size_t sizeClass = page->sizeClass(); |
| size_t pageClass = m_pageClasses[sizeClass]; |
| |
| List<SmallPage>::remove(page); // 'page' may be in any thread's line cache. |
| |
| Chunk* chunk = Chunk::get(page); |
| if (chunk->freePages().isEmpty()) |
| m_freePages[pageClass].push(chunk); |
| chunk->freePages().push(page); |
| |
| chunk->deref(); |
| |
| if (!chunk->refCount()) { |
| m_freePages[pageClass].remove(chunk); |
| |
| if (!m_chunkCache[pageClass].isEmpty()) |
| deallocateSmallChunk(m_chunkCache[pageClass].pop(), pageClass); |
| |
| m_chunkCache[pageClass].push(chunk); |
| } |
| |
| scheduleScavenger(pageSize(pageClass)); |
| } |
| |
| void Heap::allocateSmallBumpRangesByMetadata( |
| std::lock_guard<StaticMutex>& lock, size_t sizeClass, |
| BumpAllocator& allocator, BumpRangeCache& rangeCache, |
| LineCache& lineCache) |
| { |
| SmallPage* page = allocateSmallPage(lock, sizeClass, lineCache); |
| SmallLine* lines = page->begin(); |
| BASSERT(page->hasFreeLines(lock)); |
| size_t smallLineCount = m_vmPageSizePhysical / smallLineSize; |
| LineMetadata* pageMetadata = &m_smallLineMetadata[sizeClass * smallLineCount]; |
| |
| auto findSmallBumpRange = [&](size_t& lineNumber) { |
| for ( ; lineNumber < smallLineCount; ++lineNumber) { |
| if (!lines[lineNumber].refCount(lock)) { |
| if (pageMetadata[lineNumber].objectCount) |
| return true; |
| } |
| } |
| return false; |
| }; |
| |
| auto allocateSmallBumpRange = [&](size_t& lineNumber) -> BumpRange { |
| char* begin = lines[lineNumber].begin() + pageMetadata[lineNumber].startOffset; |
| unsigned short objectCount = 0; |
| |
| for ( ; lineNumber < smallLineCount; ++lineNumber) { |
| if (lines[lineNumber].refCount(lock)) |
| break; |
| |
| if (!pageMetadata[lineNumber].objectCount) |
| continue; |
| |
| objectCount += pageMetadata[lineNumber].objectCount; |
| lines[lineNumber].ref(lock, pageMetadata[lineNumber].objectCount); |
| page->ref(lock); |
| } |
| return { begin, objectCount }; |
| }; |
| |
| size_t lineNumber = 0; |
| for (;;) { |
| if (!findSmallBumpRange(lineNumber)) { |
| page->setHasFreeLines(lock, false); |
| BASSERT(allocator.canAllocate()); |
| return; |
| } |
| |
| // In a fragmented page, some free ranges might not fit in the cache. |
| if (rangeCache.size() == rangeCache.capacity()) { |
| lineCache[sizeClass].push(page); |
| BASSERT(allocator.canAllocate()); |
| return; |
| } |
| |
| BumpRange bumpRange = allocateSmallBumpRange(lineNumber); |
| if (allocator.canAllocate()) |
| rangeCache.push(bumpRange); |
| else |
| allocator.refill(bumpRange); |
| } |
| } |
| |
| void Heap::allocateSmallBumpRangesByObject( |
| std::lock_guard<StaticMutex>& lock, size_t sizeClass, |
| BumpAllocator& allocator, BumpRangeCache& rangeCache, |
| LineCache& lineCache) |
| { |
| size_t size = allocator.size(); |
| SmallPage* page = allocateSmallPage(lock, sizeClass, lineCache); |
| BASSERT(page->hasFreeLines(lock)); |
| |
| auto findSmallBumpRange = [&](Object& it, Object& end) { |
| for ( ; it + size <= end; it = it + size) { |
| if (!it.line()->refCount(lock)) |
| return true; |
| } |
| return false; |
| }; |
| |
| auto allocateSmallBumpRange = [&](Object& it, Object& end) -> BumpRange { |
| char* begin = it.address(); |
| unsigned short objectCount = 0; |
| for ( ; it + size <= end; it = it + size) { |
| if (it.line()->refCount(lock)) |
| break; |
| |
| ++objectCount; |
| it.line()->ref(lock); |
| it.page()->ref(lock); |
| } |
| return { begin, objectCount }; |
| }; |
| |
| Object it(page->begin()->begin()); |
| Object end(it + pageSize(m_pageClasses[sizeClass])); |
| for (;;) { |
| if (!findSmallBumpRange(it, end)) { |
| page->setHasFreeLines(lock, false); |
| BASSERT(allocator.canAllocate()); |
| return; |
| } |
| |
| // In a fragmented page, some free ranges might not fit in the cache. |
| if (rangeCache.size() == rangeCache.capacity()) { |
| lineCache[sizeClass].push(page); |
| BASSERT(allocator.canAllocate()); |
| return; |
| } |
| |
| BumpRange bumpRange = allocateSmallBumpRange(it, end); |
| if (allocator.canAllocate()) |
| rangeCache.push(bumpRange); |
| else |
| allocator.refill(bumpRange); |
| } |
| } |
| |
| LargeRange Heap::splitAndAllocate(LargeRange& range, size_t alignment, size_t size, AllocationKind allocationKind) |
| { |
| LargeRange prev; |
| LargeRange next; |
| |
| size_t alignmentMask = alignment - 1; |
| if (test(range.begin(), alignmentMask)) { |
| size_t prefixSize = roundUpToMultipleOf(alignment, range.begin()) - range.begin(); |
| std::pair<LargeRange, LargeRange> pair = range.split(prefixSize); |
| prev = pair.first; |
| range = pair.second; |
| } |
| |
| if (range.size() - size > size / pageSizeWasteFactor) { |
| std::pair<LargeRange, LargeRange> pair = range.split(size); |
| range = pair.first; |
| next = pair.second; |
| } |
| |
| switch (allocationKind) { |
| case AllocationKind::Virtual: |
| if (range.physicalSize()) |
| vmDeallocatePhysicalPagesSloppy(range.begin(), range.size()); |
| break; |
| |
| case AllocationKind::Physical: |
| if (range.physicalSize() < range.size()) { |
| scheduleScavengerIfUnderMemoryPressure(range.size()); |
| |
| vmAllocatePhysicalPagesSloppy(range.begin() + range.physicalSize(), range.size() - range.physicalSize()); |
| range.setPhysicalSize(range.size()); |
| } |
| break; |
| } |
| |
| if (prev) |
| m_largeFree.add(prev); |
| |
| if (next) |
| m_largeFree.add(next); |
| |
| m_objectTypes.set(Chunk::get(range.begin()), ObjectType::Large); |
| |
| m_largeAllocated.set(range.begin(), range.size()); |
| return range; |
| } |
| |
| void* Heap::tryAllocateLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t size, AllocationKind allocationKind) |
| { |
| BASSERT(isPowerOfTwo(alignment)); |
| |
| m_isGrowing = true; |
| |
| size_t roundedSize = size ? roundUpToMultipleOf(largeAlignment, size) : largeAlignment; |
| if (roundedSize < size) // Check for overflow |
| return nullptr; |
| size = roundedSize; |
| |
| size_t roundedAlignment = roundUpToMultipleOf<largeAlignment>(alignment); |
| if (roundedAlignment < alignment) // Check for overflow |
| return nullptr; |
| alignment = roundedAlignment; |
| |
| LargeRange range = m_largeFree.remove(alignment, size); |
| if (!range) { |
| if (usingGigacage()) |
| return nullptr; |
| |
| range = PerProcess<VMHeap>::get()->tryAllocateLargeChunk(alignment, size, allocationKind); |
| if (!range) |
| return nullptr; |
| |
| m_largeFree.add(range); |
| |
| range = m_largeFree.remove(alignment, size); |
| } |
| |
| return splitAndAllocate(range, alignment, size, allocationKind).begin(); |
| } |
| |
| void* Heap::allocateLarge(std::lock_guard<StaticMutex>& lock, size_t alignment, size_t size, AllocationKind allocationKind) |
| { |
| void* result = tryAllocateLarge(lock, alignment, size, allocationKind); |
| RELEASE_BASSERT(result); |
| return result; |
| } |
| |
| bool Heap::isLarge(std::lock_guard<StaticMutex>&, void* object) |
| { |
| return m_objectTypes.get(Object(object).chunk()) == ObjectType::Large; |
| } |
| |
| size_t Heap::largeSize(std::lock_guard<StaticMutex>&, void* object) |
| { |
| return m_largeAllocated.get(object); |
| } |
| |
| void Heap::shrinkLarge(std::lock_guard<StaticMutex>&, const Range& object, size_t newSize) |
| { |
| BASSERT(object.size() > newSize); |
| |
| size_t size = m_largeAllocated.remove(object.begin()); |
| LargeRange range = LargeRange(object, size); |
| splitAndAllocate(range, alignment, newSize, AllocationKind::Physical); |
| |
| scheduleScavenger(size); |
| } |
| |
| void Heap::deallocateLarge(std::lock_guard<StaticMutex>&, void* object, AllocationKind allocationKind) |
| { |
| size_t size = m_largeAllocated.remove(object); |
| m_largeFree.add(LargeRange(object, size, allocationKind == AllocationKind::Physical ? size : 0)); |
| scheduleScavenger(size); |
| } |
| |
| } // namespace bmalloc |
