haikuwebkit/Source/bmalloc/bmalloc/ObjectType.cpp

49 lines
1.7 KiB
C++
Raw Permalink Normal View History

bmalloc https://bugs.webkit.org/show_bug.cgi?id=131170 Reviewed by Andreas Kling. Initial commit. * bmalloc: Added. * bmalloc.xcodeproj: Added. * bmalloc.xcodeproj/project.pbxproj: Added. * bmalloc/Algorithm.h: Added. (bmalloc::max): (bmalloc::min): (bmalloc::mask): (bmalloc::test): (bmalloc::roundUpToMultipleOf): (bmalloc::roundDownToMultipleOf): (bmalloc::sizeOf): (bmalloc::bitCount): (bmalloc::isPowerOfTwo): * bmalloc/Allocator.cpp: Added. (bmalloc::Allocator::Allocator): (bmalloc::Allocator::~Allocator): (bmalloc::Allocator::log): (bmalloc::Allocator::processSmallAllocatorLog): (bmalloc::Allocator::processMediumAllocatorLog): (bmalloc::Allocator::allocateLarge): (bmalloc::Allocator::allocateXLarge): (bmalloc::Allocator::allocateMedium): (bmalloc::Allocator::allocateSlowCase): * bmalloc/Allocator.h: Added. (bmalloc::Allocator::smallAllocatorFor): (bmalloc::Allocator::allocateFastCase): (bmalloc::Allocator::allocate): * bmalloc/AsyncTask.cpp: Added. (bmalloc::AsyncTask<Function>::runSlowCase): (bmalloc::AsyncTask<Function>::pthreadEntryPoint): (bmalloc::AsyncTask<Function>::entryPoint): * bmalloc/AsyncTask.h: Added. (bmalloc::Function>::AsyncTask): (bmalloc::Function>::join): (bmalloc::Function>::run): (bmalloc::Function>::runSlowCase): (bmalloc::Function>::pthreadEntryPoint): (bmalloc::Function>::entryPoint): * bmalloc/BAssert.h: Added. * bmalloc/BeginTag.h: Added. (bmalloc::BeginTag::isInFreeList): * bmalloc/BoundaryTag.h: Added. (bmalloc::BoundaryTag::isXLarge): (bmalloc::BoundaryTag::setXLarge): (bmalloc::BoundaryTag::isFree): (bmalloc::BoundaryTag::setFree): (bmalloc::BoundaryTag::isEnd): (bmalloc::BoundaryTag::setEnd): (bmalloc::BoundaryTag::hasPhysicalPages): (bmalloc::BoundaryTag::setHasPhysicalPages): (bmalloc::BoundaryTag::isNull): (bmalloc::BoundaryTag::clear): (bmalloc::BoundaryTag::size): (bmalloc::BoundaryTag::setSize): (bmalloc::BoundaryTag::prev): (bmalloc::BoundaryTag::next): * bmalloc/BoundaryTagInlines.h: Added. (bmalloc::validate): (bmalloc::validatePrev): (bmalloc::validateNext): (bmalloc::BoundaryTag::init): (bmalloc::BoundaryTag::mergeLargeLeft): (bmalloc::BoundaryTag::mergeLargeRight): (bmalloc::BoundaryTag::mergeLarge): (bmalloc::BoundaryTag::deallocate): (bmalloc::BoundaryTag::splitLarge): (bmalloc::BoundaryTag::allocate): * bmalloc/Cache.cpp: Added. (bmalloc::Cache::operator new): (bmalloc::Cache::operator delete): (bmalloc::Cache::Cache): (bmalloc::Cache::allocateSlowCase): (bmalloc::Cache::allocateSlowCaseNullCache): (bmalloc::Cache::deallocateSlowCase): (bmalloc::Cache::deallocateSlowCaseNullCache): * bmalloc/Cache.h: Added. (bmalloc::Cache::allocator): (bmalloc::Cache::deallocator): (bmalloc::Cache::allocateFastCase): (bmalloc::Cache::deallocateFastCase): (bmalloc::Cache::allocate): (bmalloc::Cache::deallocate): * bmalloc/Chunk.h: Added. (bmalloc::Chunk::begin): (bmalloc::Chunk::end): (bmalloc::Chunk::lines): (bmalloc::Chunk::pages): * bmalloc/Deallocator.cpp: Added. (bmalloc::Deallocator::Deallocator): (bmalloc::Deallocator::~Deallocator): (bmalloc::Deallocator::deallocateLarge): (bmalloc::Deallocator::deallocateXLarge): (bmalloc::Deallocator::processObjectLog): (bmalloc::Deallocator::deallocateSlowCase): (bmalloc::Deallocator::deallocateSmallLine): (bmalloc::Deallocator::allocateSmallLine): (bmalloc::Deallocator::deallocateMediumLine): (bmalloc::Deallocator::allocateMediumLine): * bmalloc/Deallocator.h: Added. (bmalloc::Deallocator::deallocateFastCase): (bmalloc::Deallocator::deallocate): * bmalloc/EndTag.h: Added. (bmalloc::EndTag::operator=): * bmalloc/FixedVector.h: Added. (bmalloc::FixedVector::begin): (bmalloc::FixedVector::end): (bmalloc::FixedVector::size): (bmalloc::FixedVector::capacity): (bmalloc::FixedVector::clear): (bmalloc::FixedVector::isEmpty): (bmalloc::Capacity>::FixedVector): (bmalloc::Capacity>::operator): (bmalloc::Capacity>::push): (bmalloc::Capacity>::pop): (bmalloc::Capacity>::shrink): * bmalloc/Heap.cpp: Added. (bmalloc::sleep): (bmalloc::Heap::Heap): (bmalloc::Heap::concurrentScavenge): (bmalloc::Heap::scavengeSmallPages): (bmalloc::Heap::scavengeMediumPages): (bmalloc::Heap::scavengeLargeRanges): (bmalloc::Heap::allocateSmallLineSlowCase): (bmalloc::Heap::allocateMediumLineSlowCase): (bmalloc::Heap::allocateXLarge): (bmalloc::Heap::deallocateXLarge): (bmalloc::Heap::allocateLarge): (bmalloc::Heap::deallocateLarge): * bmalloc/Heap.h: Added. (bmalloc::Heap::deallocateSmallLine): (bmalloc::Heap::allocateSmallLine): (bmalloc::Heap::deallocateMediumLine): (bmalloc::Heap::allocateMediumLine): * bmalloc/Inline.h: Added. * bmalloc/LargeChunk.h: Added. (bmalloc::LargeChunk::begin): (bmalloc::LargeChunk::end): (bmalloc::LargeChunk::create): (bmalloc::LargeChunk::get): (bmalloc::LargeChunk::beginTag): (bmalloc::LargeChunk::endTag): * bmalloc/Line.h: Added. (bmalloc::Line<Traits>::begin): (bmalloc::Line<Traits>::end): (bmalloc::Line<Traits>::concurrentRef): (bmalloc::Line<Traits>::deref): * bmalloc/MediumAllocator.h: Added. (bmalloc::MediumAllocator::isNull): (bmalloc::MediumAllocator::MediumAllocator): (bmalloc::MediumAllocator::line): (bmalloc::MediumAllocator::allocate): (bmalloc::MediumAllocator::derefCount): (bmalloc::MediumAllocator::refill): * bmalloc/MediumChunk.h: Added. * bmalloc/MediumLine.h: Added. * bmalloc/MediumPage.h: Added. * bmalloc/MediumTraits.h: Added. * bmalloc/Mutex.cpp: Added. (bmalloc::Mutex::lockSlowCase): * bmalloc/Mutex.h: Added. (bmalloc::Mutex::Mutex): (bmalloc::Mutex::try_lock): (bmalloc::Mutex::lock): (bmalloc::Mutex::unlock): * bmalloc/ObjectType.cpp: Added. (bmalloc::objectType): * bmalloc/ObjectType.h: Added. (bmalloc::isSmallOrMedium): (bmalloc::isSmall): * bmalloc/Page.h: Added. (bmalloc::Page<Traits>::ref): (bmalloc::Page<Traits>::deref): (bmalloc::Page<Traits>::refCount): * bmalloc/PerProcess.h: Added. (bmalloc::PerProcess::mutex): (bmalloc::PerProcess<T>::getFastCase): (bmalloc::PerProcess<T>::get): (bmalloc::PerProcess<T>::getSlowCase): * bmalloc/PerThread.h: Added. (bmalloc::PerThreadStorage<Cache>::get): (bmalloc::PerThreadStorage<Cache>::init): (bmalloc::PerThreadStorage::get): (bmalloc::PerThreadStorage::init): (bmalloc::PerThread<T>::getFastCase): (bmalloc::PerThread<T>::get): (bmalloc::PerThread<T>::destructor): (bmalloc::PerThread<T>::getSlowCase): * bmalloc/Range.h: Added. (bmalloc::Range::Range): (bmalloc::Range::begin): (bmalloc::Range::end): (bmalloc::Range::size): (bmalloc::Range::operator!): (bmalloc::Range::operator<): * bmalloc/SegregatedFreeList.cpp: Added. (bmalloc::SegregatedFreeList::SegregatedFreeList): (bmalloc::SegregatedFreeList::insert): (bmalloc::SegregatedFreeList::takeGreedy): (bmalloc::SegregatedFreeList::take): * bmalloc/SegregatedFreeList.h: Added. * bmalloc/Sizes.h: Added. * bmalloc/SmallAllocator.h: Added. (bmalloc::SmallAllocator::isNull): (bmalloc::SmallAllocator::canAllocate): (bmalloc::SmallAllocator::SmallAllocator): (bmalloc::SmallAllocator::line): (bmalloc::SmallAllocator::allocate): (bmalloc::SmallAllocator::objectCount): (bmalloc::SmallAllocator::derefCount): (bmalloc::SmallAllocator::refill): * bmalloc/SmallChunk.h: Added. * bmalloc/SmallLine.h: Added. * bmalloc/SmallPage.h: Added. * bmalloc/SmallTraits.h: Added. * bmalloc/Syscall.h: Added. * bmalloc/VMAllocate.h: Added. (bmalloc::vmSize): (bmalloc::vmValidate): (bmalloc::vmAllocate): (bmalloc::vmDeallocate): (bmalloc::vmDeallocatePhysicalPages): (bmalloc::vmAllocatePhysicalPages): (bmalloc::vmDeallocatePhysicalPagesSloppy): (bmalloc::vmAllocatePhysicalPagesSloppy): * bmalloc/VMHeap.cpp: Added. (bmalloc::VMHeap::VMHeap): (bmalloc::VMHeap::allocateSmallChunk): (bmalloc::VMHeap::allocateMediumChunk): (bmalloc::VMHeap::allocateLargeChunk): * bmalloc/VMHeap.h: Added. (bmalloc::VMHeap::allocateSmallPage): (bmalloc::VMHeap::allocateMediumPage): (bmalloc::VMHeap::allocateLargeRange): (bmalloc::VMHeap::deallocateSmallPage): (bmalloc::VMHeap::deallocateMediumPage): (bmalloc::VMHeap::deallocateLargeRange): * bmalloc/Vector.h: Added. (bmalloc::Vector::begin): (bmalloc::Vector::end): (bmalloc::Vector::size): (bmalloc::Vector::capacity): (bmalloc::Vector::last): (bmalloc::Vector::pop): (bmalloc::Vector<T>::Vector): (bmalloc::Vector<T>::~Vector): (bmalloc::Vector<T>::operator): (bmalloc::Vector<T>::push): (bmalloc::Vector<T>::pop): (bmalloc::Vector<T>::shrink): (bmalloc::Vector<T>::reallocateBuffer): (bmalloc::Vector<T>::shrinkCapacity): (bmalloc::Vector<T>::growCapacity): * bmalloc/XLargeChunk.h: Added. (bmalloc::XLargeChunk::get): (bmalloc::XLargeChunk::begin): (bmalloc::XLargeChunk::XLargeChunk): (bmalloc::XLargeChunk::create): (bmalloc::XLargeChunk::destroy): (bmalloc::XLargeChunk::range): (bmalloc::XLargeChunk::size): * bmalloc/bmalloc.h: Added. (bmalloc::api::malloc): (bmalloc::api::free): (bmalloc::api::realloc): * bmalloc/mbmalloc.cpp: Added. Canonical link: https://commits.webkit.org/149378@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@166893 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2014-04-07 23:54:11 +00:00
/*
bmalloc should do partial scavenges more frequently https://bugs.webkit.org/show_bug.cgi?id=184176 Reviewed by Filip Pizlo. This patch adds the ability for bmalloc to do a partial scavenge. bmalloc will now do a partial scavenge with some frequency even when the heap is growing. For Heap, this means tracking the high water mark of where the Heap has allocated since the last scavenge. Partial scavenging is just decommitting entries in the LargeMap that are past this high water mark. Because we allocate in first fit order out of LargeMap, tracking the high water mark is a good heuristic of how much memory a partial scavenge should decommit. For IsoHeaps, each IsoDirectory also keeps track of its high water mark for the furthest page it allocates into. Similar to Heap, we scavenge pages past that high water mark. IsoHeapImpl then tracks the high water mark for the IsoDirectory it allocates into. We then scavenge all directories including and past the directory high water mark. This includes scavenging the inline directory when its the only thing we allocate out of since the last scavenge. This patch also adds some other capabilities to bmalloc: Heaps and IsoHeaps now track how much memory is freeable. Querying this number is now cheap. Heaps no longer hold the global lock when decommitting large ranges. Instead, that range is just marked as non eligible to be allocated. Then, without the lock held, the scavenger will decommit those ranges. Once this is done, the scavenger will then reacquire the lock and mark these ranges as eligible. This lessens lock contention between the scavenger and the allocation slow path since threads that are taking an allocation slow path can now allocate concurrently to the scavenger's decommits. The main consideration in adding this functionality is that a large allocation may fail while the scavenger is in the process of decommitting memory. When the Heap fails to allocate a large range when the scavenger is in the middle of a decommit, Heap will wait for the Scavenger to finish and then it will try to allocate a large range again. Decommitting from Heap now aggregates the ranges to decommit and tries to merge them together to lower the number of calls to vmDeallocatePhysicalPages. This is analogous to what IsoHeaps already do. * bmalloc.xcodeproj/project.pbxproj: * bmalloc/Allocator.cpp: (bmalloc::Allocator::tryAllocate): (bmalloc::Allocator::allocateImpl): (bmalloc::Allocator::reallocate): (bmalloc::Allocator::refillAllocatorSlowCase): (bmalloc::Allocator::allocateLarge): * bmalloc/BulkDecommit.h: Added. (bmalloc::BulkDecommit::addEager): (bmalloc::BulkDecommit::addLazy): (bmalloc::BulkDecommit::processEager): (bmalloc::BulkDecommit::processLazy): (bmalloc::BulkDecommit::add): (bmalloc::BulkDecommit::process): * bmalloc/Deallocator.cpp: (bmalloc::Deallocator::scavenge): (bmalloc::Deallocator::processObjectLog): (bmalloc::Deallocator::deallocateSlowCase): * bmalloc/Deallocator.h: (bmalloc::Deallocator::lineCache): * bmalloc/Heap.cpp: (bmalloc::Heap::freeableMemory): (bmalloc::Heap::markAllLargeAsEligibile): (bmalloc::Heap::decommitLargeRange): (bmalloc::Heap::scavenge): (bmalloc::Heap::scavengeToHighWatermark): (bmalloc::Heap::deallocateLineCache): (bmalloc::Heap::allocateSmallChunk): (bmalloc::Heap::deallocateSmallChunk): (bmalloc::Heap::allocateSmallPage): (bmalloc::Heap::deallocateSmallLine): (bmalloc::Heap::allocateSmallBumpRangesByMetadata): (bmalloc::Heap::allocateSmallBumpRangesByObject): (bmalloc::Heap::splitAndAllocate): (bmalloc::Heap::tryAllocateLarge): (bmalloc::Heap::allocateLarge): (bmalloc::Heap::isLarge): (bmalloc::Heap::largeSize): (bmalloc::Heap::shrinkLarge): (bmalloc::Heap::deallocateLarge): (bmalloc::Heap::externalCommit): (bmalloc::Heap::externalDecommit): * bmalloc/Heap.h: (bmalloc::Heap::allocateSmallBumpRanges): (bmalloc::Heap::derefSmallLine): * bmalloc/IsoDirectory.h: * bmalloc/IsoDirectoryInlines.h: (bmalloc::passedNumPages>::takeFirstEligible): (bmalloc::passedNumPages>::didBecome): (bmalloc::passedNumPages>::didDecommit): (bmalloc::passedNumPages>::scavengePage): (bmalloc::passedNumPages>::scavenge): (bmalloc::passedNumPages>::scavengeToHighWatermark): (bmalloc::passedNumPages>::freeableMemory): Deleted. * bmalloc/IsoHeapImpl.h: * bmalloc/IsoHeapImplInlines.h: (bmalloc::IsoHeapImpl<Config>::takeFirstEligible): (bmalloc::IsoHeapImpl<Config>::scavenge): (bmalloc::IsoHeapImpl<Config>::scavengeToHighWatermark): (bmalloc::IsoHeapImpl<Config>::freeableMemory): (bmalloc::IsoHeapImpl<Config>::isNowFreeable): (bmalloc::IsoHeapImpl<Config>::isNoLongerFreeable): * bmalloc/LargeMap.cpp: (bmalloc::LargeMap::remove): (bmalloc::LargeMap::markAllAsEligibile): * bmalloc/LargeMap.h: (bmalloc::LargeMap::size): (bmalloc::LargeMap::at): * bmalloc/LargeRange.h: (bmalloc::LargeRange::setEligible): (bmalloc::LargeRange::isEligibile const): (bmalloc::canMerge): * bmalloc/ObjectType.cpp: (bmalloc::objectType): * bmalloc/Scavenger.cpp: (bmalloc::PrintTime::PrintTime): (bmalloc::PrintTime::~PrintTime): (bmalloc::PrintTime::print): (bmalloc::Scavenger::timeSinceLastFullScavenge): (bmalloc::Scavenger::timeSinceLastPartialScavenge): (bmalloc::Scavenger::scavenge): (bmalloc::Scavenger::partialScavenge): (bmalloc::Scavenger::freeableMemory): (bmalloc::Scavenger::threadRunLoop): * bmalloc/Scavenger.h: * bmalloc/SmallLine.h: (bmalloc::SmallLine::refCount): (bmalloc::SmallLine::ref): (bmalloc::SmallLine::deref): * bmalloc/SmallPage.h: (bmalloc::SmallPage::refCount): (bmalloc::SmallPage::hasFreeLines const): (bmalloc::SmallPage::setHasFreeLines): (bmalloc::SmallPage::ref): (bmalloc::SmallPage::deref): * bmalloc/bmalloc.cpp: (bmalloc::api::tryLargeZeroedMemalignVirtual): (bmalloc::api::freeLargeVirtual): Canonical link: https://commits.webkit.org/200026@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@230501 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2018-04-10 23:34:42 +00:00
* Copyright (C) 2014-2018 Apple Inc. All rights reserved.
bmalloc https://bugs.webkit.org/show_bug.cgi?id=131170 Reviewed by Andreas Kling. Initial commit. * bmalloc: Added. * bmalloc.xcodeproj: Added. * bmalloc.xcodeproj/project.pbxproj: Added. * bmalloc/Algorithm.h: Added. (bmalloc::max): (bmalloc::min): (bmalloc::mask): (bmalloc::test): (bmalloc::roundUpToMultipleOf): (bmalloc::roundDownToMultipleOf): (bmalloc::sizeOf): (bmalloc::bitCount): (bmalloc::isPowerOfTwo): * bmalloc/Allocator.cpp: Added. (bmalloc::Allocator::Allocator): (bmalloc::Allocator::~Allocator): (bmalloc::Allocator::log): (bmalloc::Allocator::processSmallAllocatorLog): (bmalloc::Allocator::processMediumAllocatorLog): (bmalloc::Allocator::allocateLarge): (bmalloc::Allocator::allocateXLarge): (bmalloc::Allocator::allocateMedium): (bmalloc::Allocator::allocateSlowCase): * bmalloc/Allocator.h: Added. (bmalloc::Allocator::smallAllocatorFor): (bmalloc::Allocator::allocateFastCase): (bmalloc::Allocator::allocate): * bmalloc/AsyncTask.cpp: Added. (bmalloc::AsyncTask<Function>::runSlowCase): (bmalloc::AsyncTask<Function>::pthreadEntryPoint): (bmalloc::AsyncTask<Function>::entryPoint): * bmalloc/AsyncTask.h: Added. (bmalloc::Function>::AsyncTask): (bmalloc::Function>::join): (bmalloc::Function>::run): (bmalloc::Function>::runSlowCase): (bmalloc::Function>::pthreadEntryPoint): (bmalloc::Function>::entryPoint): * bmalloc/BAssert.h: Added. * bmalloc/BeginTag.h: Added. (bmalloc::BeginTag::isInFreeList): * bmalloc/BoundaryTag.h: Added. (bmalloc::BoundaryTag::isXLarge): (bmalloc::BoundaryTag::setXLarge): (bmalloc::BoundaryTag::isFree): (bmalloc::BoundaryTag::setFree): (bmalloc::BoundaryTag::isEnd): (bmalloc::BoundaryTag::setEnd): (bmalloc::BoundaryTag::hasPhysicalPages): (bmalloc::BoundaryTag::setHasPhysicalPages): (bmalloc::BoundaryTag::isNull): (bmalloc::BoundaryTag::clear): (bmalloc::BoundaryTag::size): (bmalloc::BoundaryTag::setSize): (bmalloc::BoundaryTag::prev): (bmalloc::BoundaryTag::next): * bmalloc/BoundaryTagInlines.h: Added. (bmalloc::validate): (bmalloc::validatePrev): (bmalloc::validateNext): (bmalloc::BoundaryTag::init): (bmalloc::BoundaryTag::mergeLargeLeft): (bmalloc::BoundaryTag::mergeLargeRight): (bmalloc::BoundaryTag::mergeLarge): (bmalloc::BoundaryTag::deallocate): (bmalloc::BoundaryTag::splitLarge): (bmalloc::BoundaryTag::allocate): * bmalloc/Cache.cpp: Added. (bmalloc::Cache::operator new): (bmalloc::Cache::operator delete): (bmalloc::Cache::Cache): (bmalloc::Cache::allocateSlowCase): (bmalloc::Cache::allocateSlowCaseNullCache): (bmalloc::Cache::deallocateSlowCase): (bmalloc::Cache::deallocateSlowCaseNullCache): * bmalloc/Cache.h: Added. (bmalloc::Cache::allocator): (bmalloc::Cache::deallocator): (bmalloc::Cache::allocateFastCase): (bmalloc::Cache::deallocateFastCase): (bmalloc::Cache::allocate): (bmalloc::Cache::deallocate): * bmalloc/Chunk.h: Added. (bmalloc::Chunk::begin): (bmalloc::Chunk::end): (bmalloc::Chunk::lines): (bmalloc::Chunk::pages): * bmalloc/Deallocator.cpp: Added. (bmalloc::Deallocator::Deallocator): (bmalloc::Deallocator::~Deallocator): (bmalloc::Deallocator::deallocateLarge): (bmalloc::Deallocator::deallocateXLarge): (bmalloc::Deallocator::processObjectLog): (bmalloc::Deallocator::deallocateSlowCase): (bmalloc::Deallocator::deallocateSmallLine): (bmalloc::Deallocator::allocateSmallLine): (bmalloc::Deallocator::deallocateMediumLine): (bmalloc::Deallocator::allocateMediumLine): * bmalloc/Deallocator.h: Added. (bmalloc::Deallocator::deallocateFastCase): (bmalloc::Deallocator::deallocate): * bmalloc/EndTag.h: Added. (bmalloc::EndTag::operator=): * bmalloc/FixedVector.h: Added. (bmalloc::FixedVector::begin): (bmalloc::FixedVector::end): (bmalloc::FixedVector::size): (bmalloc::FixedVector::capacity): (bmalloc::FixedVector::clear): (bmalloc::FixedVector::isEmpty): (bmalloc::Capacity>::FixedVector): (bmalloc::Capacity>::operator): (bmalloc::Capacity>::push): (bmalloc::Capacity>::pop): (bmalloc::Capacity>::shrink): * bmalloc/Heap.cpp: Added. (bmalloc::sleep): (bmalloc::Heap::Heap): (bmalloc::Heap::concurrentScavenge): (bmalloc::Heap::scavengeSmallPages): (bmalloc::Heap::scavengeMediumPages): (bmalloc::Heap::scavengeLargeRanges): (bmalloc::Heap::allocateSmallLineSlowCase): (bmalloc::Heap::allocateMediumLineSlowCase): (bmalloc::Heap::allocateXLarge): (bmalloc::Heap::deallocateXLarge): (bmalloc::Heap::allocateLarge): (bmalloc::Heap::deallocateLarge): * bmalloc/Heap.h: Added. (bmalloc::Heap::deallocateSmallLine): (bmalloc::Heap::allocateSmallLine): (bmalloc::Heap::deallocateMediumLine): (bmalloc::Heap::allocateMediumLine): * bmalloc/Inline.h: Added. * bmalloc/LargeChunk.h: Added. (bmalloc::LargeChunk::begin): (bmalloc::LargeChunk::end): (bmalloc::LargeChunk::create): (bmalloc::LargeChunk::get): (bmalloc::LargeChunk::beginTag): (bmalloc::LargeChunk::endTag): * bmalloc/Line.h: Added. (bmalloc::Line<Traits>::begin): (bmalloc::Line<Traits>::end): (bmalloc::Line<Traits>::concurrentRef): (bmalloc::Line<Traits>::deref): * bmalloc/MediumAllocator.h: Added. (bmalloc::MediumAllocator::isNull): (bmalloc::MediumAllocator::MediumAllocator): (bmalloc::MediumAllocator::line): (bmalloc::MediumAllocator::allocate): (bmalloc::MediumAllocator::derefCount): (bmalloc::MediumAllocator::refill): * bmalloc/MediumChunk.h: Added. * bmalloc/MediumLine.h: Added. * bmalloc/MediumPage.h: Added. * bmalloc/MediumTraits.h: Added. * bmalloc/Mutex.cpp: Added. (bmalloc::Mutex::lockSlowCase): * bmalloc/Mutex.h: Added. (bmalloc::Mutex::Mutex): (bmalloc::Mutex::try_lock): (bmalloc::Mutex::lock): (bmalloc::Mutex::unlock): * bmalloc/ObjectType.cpp: Added. (bmalloc::objectType): * bmalloc/ObjectType.h: Added. (bmalloc::isSmallOrMedium): (bmalloc::isSmall): * bmalloc/Page.h: Added. (bmalloc::Page<Traits>::ref): (bmalloc::Page<Traits>::deref): (bmalloc::Page<Traits>::refCount): * bmalloc/PerProcess.h: Added. (bmalloc::PerProcess::mutex): (bmalloc::PerProcess<T>::getFastCase): (bmalloc::PerProcess<T>::get): (bmalloc::PerProcess<T>::getSlowCase): * bmalloc/PerThread.h: Added. (bmalloc::PerThreadStorage<Cache>::get): (bmalloc::PerThreadStorage<Cache>::init): (bmalloc::PerThreadStorage::get): (bmalloc::PerThreadStorage::init): (bmalloc::PerThread<T>::getFastCase): (bmalloc::PerThread<T>::get): (bmalloc::PerThread<T>::destructor): (bmalloc::PerThread<T>::getSlowCase): * bmalloc/Range.h: Added. (bmalloc::Range::Range): (bmalloc::Range::begin): (bmalloc::Range::end): (bmalloc::Range::size): (bmalloc::Range::operator!): (bmalloc::Range::operator<): * bmalloc/SegregatedFreeList.cpp: Added. (bmalloc::SegregatedFreeList::SegregatedFreeList): (bmalloc::SegregatedFreeList::insert): (bmalloc::SegregatedFreeList::takeGreedy): (bmalloc::SegregatedFreeList::take): * bmalloc/SegregatedFreeList.h: Added. * bmalloc/Sizes.h: Added. * bmalloc/SmallAllocator.h: Added. (bmalloc::SmallAllocator::isNull): (bmalloc::SmallAllocator::canAllocate): (bmalloc::SmallAllocator::SmallAllocator): (bmalloc::SmallAllocator::line): (bmalloc::SmallAllocator::allocate): (bmalloc::SmallAllocator::objectCount): (bmalloc::SmallAllocator::derefCount): (bmalloc::SmallAllocator::refill): * bmalloc/SmallChunk.h: Added. * bmalloc/SmallLine.h: Added. * bmalloc/SmallPage.h: Added. * bmalloc/SmallTraits.h: Added. * bmalloc/Syscall.h: Added. * bmalloc/VMAllocate.h: Added. (bmalloc::vmSize): (bmalloc::vmValidate): (bmalloc::vmAllocate): (bmalloc::vmDeallocate): (bmalloc::vmDeallocatePhysicalPages): (bmalloc::vmAllocatePhysicalPages): (bmalloc::vmDeallocatePhysicalPagesSloppy): (bmalloc::vmAllocatePhysicalPagesSloppy): * bmalloc/VMHeap.cpp: Added. (bmalloc::VMHeap::VMHeap): (bmalloc::VMHeap::allocateSmallChunk): (bmalloc::VMHeap::allocateMediumChunk): (bmalloc::VMHeap::allocateLargeChunk): * bmalloc/VMHeap.h: Added. (bmalloc::VMHeap::allocateSmallPage): (bmalloc::VMHeap::allocateMediumPage): (bmalloc::VMHeap::allocateLargeRange): (bmalloc::VMHeap::deallocateSmallPage): (bmalloc::VMHeap::deallocateMediumPage): (bmalloc::VMHeap::deallocateLargeRange): * bmalloc/Vector.h: Added. (bmalloc::Vector::begin): (bmalloc::Vector::end): (bmalloc::Vector::size): (bmalloc::Vector::capacity): (bmalloc::Vector::last): (bmalloc::Vector::pop): (bmalloc::Vector<T>::Vector): (bmalloc::Vector<T>::~Vector): (bmalloc::Vector<T>::operator): (bmalloc::Vector<T>::push): (bmalloc::Vector<T>::pop): (bmalloc::Vector<T>::shrink): (bmalloc::Vector<T>::reallocateBuffer): (bmalloc::Vector<T>::shrinkCapacity): (bmalloc::Vector<T>::growCapacity): * bmalloc/XLargeChunk.h: Added. (bmalloc::XLargeChunk::get): (bmalloc::XLargeChunk::begin): (bmalloc::XLargeChunk::XLargeChunk): (bmalloc::XLargeChunk::create): (bmalloc::XLargeChunk::destroy): (bmalloc::XLargeChunk::range): (bmalloc::XLargeChunk::size): * bmalloc/bmalloc.h: Added. (bmalloc::api::malloc): (bmalloc::api::free): (bmalloc::api::realloc): * bmalloc/mbmalloc.cpp: Added. Canonical link: https://commits.webkit.org/149378@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@166893 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2014-04-07 23:54:11 +00:00
*
* 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 "ObjectType.h"
#include "Chunk.h"
bmalloc: Merge the large and xlarge allocators https://bugs.webkit.org/show_bug.cgi?id=156734 Reviewed by Andreas Kling. This give us better defense against worst case memory usage: Baseline Patch Δ Peak Memory: nimlang 198,132kB 181,468kB ^ 1.09x smaller It also eliminates inline metadata for large objects, fixing the regression introduced in r198675, and more: run-malloc-benchmarks Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/ Baseline Patch Δ Memory at End: big 10,880kB 3,328kB ^ 3.27x smaller facebook 3,112kB 2,868kB ^ 1.09x smaller fragment --parallel 1,848kB 760kB ^ 2.43x smaller fragment_iterate --parallel 4,908kB 776kB ^ 6.32x smaller big --parallel 48,076kB 11,892kB ^ 4.04x smaller Overall memory use looks OK: run-malloc-benchmarks --memory_warning Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/ Baseline Patch Δ Memory at End: <arithmetic mean> 13,992kB 13,987kB ^ 1.0x smaller Overall throughput looks OK: run-malloc-benchmarks Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/ Baseline Patch Δ Execution Time: <arithmetic mean> 103ms 104ms ! 1.01x slower We're a bit slower on the "all-out large allocations on all cores" benchmark, but I think that's an OK price to pay: Baseline Patch Δ Execution Time: big --parallel 125ms 136ms ! 1.09x slower This patch net removes 1.5k lines of code. It turns out that large allocations are rare, and free memory fragments are also rare, so the combination is super rare, and a simple O(n) algorithm that ensures good memory behavior is the best option. Fun fact: In practice, the odds that the old code would save memory were *worse* than the odds that it would contain a bug that wasted memory. :) * bmalloc.xcodeproj/project.pbxproj: * bmalloc/Allocator.cpp: (bmalloc::Allocator::tryAllocate): largeMax is the new xLargeMax since xLargeMax is gone now. (bmalloc::Allocator::allocate): I moved the rounding code into allocateLarge, so we don't have to do it here. (bmalloc::Allocator::reallocate): (bmalloc::Allocator::allocateSlowCase): (bmalloc::Allocator::allocateXLarge): Deleted. No more XLarge case. * bmalloc/Allocator.h: * bmalloc/BeginTag.h: Removed. * bmalloc/BoundaryTag.h: Removed. * bmalloc/Chunk.h: (bmalloc::ChunkHash::hash): Added a hash function. The best hash function is a unique and monotonically increasing integer, and that's exactly what we typically get from the high bits of a Chunk, since the OS allocates Chunks at unique and increasing addresses. (bmalloc::Chunk::boundaryTags): Deleted. (bmalloc::Chunk::objectType): Deleted. (bmalloc::Chunk::beginTag): Deleted. (bmalloc::Chunk::endTag): Deleted. * bmalloc/Deallocator.cpp: (bmalloc::Deallocator::deallocateSlowCase): We no longer know for sure, by looking at its bit pattern, whether a pointer is small or large. Instead, any pointer with large alignment *might* be large, and when we occasionally encounter such an object, we have to consult a hash table in the Heap to find out for sure. This turns out to be just as cheap in practice. We don't deallocate large objects on the fast path anymore. We can't, because large objects have out-of-line metadata now. (bmalloc::Deallocator::deallocateXLarge): Deleted. * bmalloc/Deallocator.h: (bmalloc::Deallocator::deallocateFastCase): See deallocateSlowCase. * bmalloc/EndTag.h: Removed. * bmalloc/FreeList.cpp: Removed. * bmalloc/FreeList.h: Removed. * bmalloc/Heap.cpp: (bmalloc::Heap::allocateSmallPage): Be sure to track each chunk in the object type map, so we can distinguish small vs large objects. (bmalloc::Heap::deallocateSmallLine): No need to check object type because we know object type now by virtue of being on the small object path. (bmalloc::Heap::splitAndAllocate): Be sure to track each chunk in the object type map, so we can distinguish small vs large objects. Large objects can split across chunks, so we need to add each large object's chunk as it is allocated. (bmalloc::Heap::tryAllocateLarge): (bmalloc::Heap::allocateLarge): (bmalloc::Heap::isLarge): (bmalloc::Heap::largeSize): (bmalloc::Heap::shrinkLarge): (bmalloc::Heap::deallocateLarge): Merged in existing XLarge logic for large objects. (bmalloc::Heap::scavengeXLargeObjects): Deleted. (bmalloc::Heap::allocateXLarge): Deleted. (bmalloc::Heap::tryAllocateXLarge): Deleted. (bmalloc::Heap::xLargeSize): Deleted. (bmalloc::Heap::shrinkXLarge): Deleted. (bmalloc::Heap::deallocateXLarge): Deleted. * bmalloc/Heap.h: (bmalloc::Heap::LargeObjectHash::hash): * bmalloc/LargeObject.h: Removed. * bmalloc/Map.h: Added. (bmalloc::Map::size): (bmalloc::Map::capacity): (bmalloc::Map::get): (bmalloc::Map::set): (bmalloc::Map::remove): (bmalloc::Map::shouldGrow): (bmalloc::Map::shouldShrink): (bmalloc::Map::find): (bmalloc::Hash>::rehash): Simple hash table. * bmalloc/Object.h: * bmalloc/ObjectType.cpp: (bmalloc::objectType): * bmalloc/ObjectType.h: (bmalloc::mightBeLarge): See deallocateSlowCase. (bmalloc::isXLarge): Deleted. * bmalloc/SegregatedFreeList.cpp: Removed. * bmalloc/SegregatedFreeList.h: Removed. * bmalloc/Sizes.h: Upped smallMax to 64kB. Upping to 32kB is pretty reasonable, since sizes between 16kB and 32kB share page sizes. I went all the way up to 64kB because the GC uses 64kB blocks, and also just for extra padding to ensure that large allocations are indeed rare. * bmalloc/SortedVector.h: Removed. * bmalloc/VMHeap.cpp: (bmalloc::VMHeap::tryAllocateLargeChunk): (bmalloc::VMHeap::allocateSmallChunk): (bmalloc::VMHeap::VMHeap): Deleted. (bmalloc::VMHeap::allocateChunk): Deleted. * bmalloc/VMHeap.h: (bmalloc::VMHeap::deallocateSmallPage): (bmalloc::VMHeap::allocateLargeObject): Deleted. (bmalloc::VMHeap::deallocateLargeObject): Deleted. Nixed all the boundary tag logic since metadata is out of line now. * bmalloc/VMState.h: Removed. Instead of an abstract state, we track the precise amount of committed physical pages at the head of a VM range. This allows us to merge aggressively without triggering an madvise storm most of the time. * bmalloc/Vector.h: (bmalloc::Vector<T>::Vector): (bmalloc::Vector<T>::insert): (bmalloc::Vector<T>::remove): (bmalloc::Vector<T>::resize): Filled out some missing helpers. * bmalloc/XLargeMap.cpp: (bmalloc::XLargeMap::remove): (bmalloc::XLargeMap::add): (bmalloc::XLargeMap::removePhysical): (bmalloc::XLargeMap::takeFree): Deleted. (bmalloc::XLargeMap::addFree): Deleted. (bmalloc::XLargeMap::addAllocated): Deleted. (bmalloc::XLargeMap::getAllocated): Deleted. (bmalloc::XLargeMap::takeAllocated): Deleted. (bmalloc::XLargeMap::shrinkToFit): Deleted. (bmalloc::XLargeMap::takePhysical): Deleted. (bmalloc::XLargeMap::addVirtual): Deleted. * bmalloc/XLargeMap.h: (bmalloc::XLargeMap::Allocation::operator<): Deleted. We don't track object sizes anymore -- just free space. (The Heap tracks object sizes.) We use plain old linear search for free space. (See intro.) * bmalloc/XLargeRange.h: (bmalloc::XLargeRange::physicalSize): (bmalloc::XLargeRange::setPhysicalSize): (bmalloc::merge): (bmalloc::XLargeRange::split): (bmalloc::XLargeRange::vmState): Deleted. (bmalloc::XLargeRange::setVMState): Deleted. See VMState.h. Canonical link: https://commits.webkit.org/174881@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@199746 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2016-04-19 23:36:20 +00:00
#include "Heap.h"
bmalloc: small and large objects should share memory https://bugs.webkit.org/show_bug.cgi?id=155866 Reviewed by Andreas Kling. This patch cuts our VM footprint in half. (VM footprint usually doesn't matter, but on iOS there's an artificial VM limit around 700MB, and if you hit it you jetsam / crash.) It's also a step toward honoring the hardware page size at runtime, which will reduce memory usage on iOS. This patch is a small improvement in peak memory usage because it allows small and large objects to recycle each other's memory. The tradeoff is that we require more metadata, which causes more memory usage after shrinking down from peak memory usage. In the end, we have some memory wins and some losses, and a small win in the mean on our standard memory benchmarks. * bmalloc.xcodeproj/project.pbxproj: Removed SuperChunk. * bmalloc/Allocator.cpp: (bmalloc::Allocator::reallocate): Adopt a new Heap API for shrinking large objects because it's a little more complicated than it used to be. Don't check for equality in the XLarge case because we don't do it in other cases, and it's unlikely that we'll be called for no reason. * bmalloc/BumpAllocator.h: (bmalloc::BumpAllocator::allocate): Don't ASSERT isSmall because that's an old concept from when small and large objects were in distinct memory regions. * bmalloc/Deallocator.cpp: (bmalloc::Deallocator::deallocateSlowCase): Large objects are not segregated anymore. (bmalloc::Deallocator::deallocateLarge): Deleted. * bmalloc/Deallocator.h: (bmalloc::Deallocator::deallocateFastCase): Don't ASSERT isSmall(). See above. * bmalloc/Heap.cpp: (bmalloc::Heap::scavenge): (bmalloc::Heap::scavengeSmallPage): (bmalloc::Heap::scavengeSmallPages): New helpers for returning cached small pages to the large object heap. (bmalloc::Heap::allocateSmallPage): Allocate small pages from the large object heap. This is how we accomplish sharing. (bmalloc::Heap::deallocateSmallLine): Handle large objects since we can encounter them on this code path now. (bmalloc::Heap::splitAndAllocate): Fixed a bug where we would sometimes not split even though we could. Allocating a large object also requires ref'ing its small line so that we can alias memory between small and large objects. (bmalloc::Heap::allocateLarge): Return cached small pages before allocating a large object that would fit in a cached small page. This allows some large allocations to reuse small object memory. (bmalloc::Heap::shrinkLarge): New helper. (bmalloc::Heap::deallocateLarge): Deleted. * bmalloc/Heap.h: * bmalloc/LargeChunk.h: (bmalloc::LargeChunk::pageBegin): (bmalloc::LargeChunk::pageEnd): (bmalloc::LargeChunk::lines): (bmalloc::LargeChunk::pages): (bmalloc::LargeChunk::begin): (bmalloc::LargeChunk::end): (bmalloc::LargeChunk::LargeChunk): (bmalloc::LargeChunk::get): (bmalloc::LargeChunk::endTag): (bmalloc::LargeChunk::offset): (bmalloc::LargeChunk::object): (bmalloc::LargeChunk::page): (bmalloc::LargeChunk::line): (bmalloc::SmallLine::begin): (bmalloc::SmallLine::end): (bmalloc::SmallPage::begin): (bmalloc::SmallPage::end): (bmalloc::Object::Object): (bmalloc::Object::begin): (bmalloc::Object::pageBegin): (bmalloc::Object::line): (bmalloc::Object::page): I merged all the SmallChunk metadata and code into LargeChunk. Now we use a single class to track both small and large metadata, so we can share memory between small and large objects. I'm going to rename this class to Chunk in a follow-up patch. * bmalloc/Object.h: (bmalloc::Object::chunk): Updated for LargeChunk transition. * bmalloc/ObjectType.cpp: (bmalloc::objectType): * bmalloc/ObjectType.h: (bmalloc::isXLarge): (bmalloc::isSmall): Deleted. The difference between small and large objects is now stored in metadata and is not a property of their virtual address range. * bmalloc/SegregatedFreeList.h: One more entry because we cover all of what used to be the super chunk in a large chunk now. * bmalloc/Sizes.h: Removed bit masking helpers because we don't use address masks to distinguish small vs large object type anymore. * bmalloc/SmallChunk.h: Removed. * bmalloc/SmallPage.h: (bmalloc::SmallPage::SmallPage): Store object type per page because any given page can be used for large objects or small objects. * bmalloc/SuperChunk.h: Removed. * bmalloc/VMHeap.cpp: (bmalloc::VMHeap::VMHeap): (bmalloc::VMHeap::allocateLargeChunk): (bmalloc::VMHeap::allocateSmallChunk): Deleted. (bmalloc::VMHeap::allocateSuperChunk): Deleted. * bmalloc/VMHeap.h: (bmalloc::VMHeap::allocateLargeObject): (bmalloc::VMHeap::deallocateLargeObject): (bmalloc::VMHeap::allocateSmallPage): Deleted. (bmalloc::VMHeap::deallocateSmallPage): Deleted. Removed super chunk and small chunk support. * bmalloc/Zone.cpp: (bmalloc::enumerator): * bmalloc/Zone.h: (bmalloc::Zone::largeChunks): (bmalloc::Zone::addLargeChunk): (bmalloc::Zone::superChunks): Deleted. (bmalloc::Zone::addSuperChunk): Deleted. Removed super chunk and small chunk support. Canonical link: https://commits.webkit.org/173983@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@198675 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2016-03-25 18:07:31 +00:00
#include "Object.h"
bmalloc: Merge the large and xlarge allocators https://bugs.webkit.org/show_bug.cgi?id=156734 Reviewed by Andreas Kling. This give us better defense against worst case memory usage: Baseline Patch Δ Peak Memory: nimlang 198,132kB 181,468kB ^ 1.09x smaller It also eliminates inline metadata for large objects, fixing the regression introduced in r198675, and more: run-malloc-benchmarks Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/ Baseline Patch Δ Memory at End: big 10,880kB 3,328kB ^ 3.27x smaller facebook 3,112kB 2,868kB ^ 1.09x smaller fragment --parallel 1,848kB 760kB ^ 2.43x smaller fragment_iterate --parallel 4,908kB 776kB ^ 6.32x smaller big --parallel 48,076kB 11,892kB ^ 4.04x smaller Overall memory use looks OK: run-malloc-benchmarks --memory_warning Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/ Baseline Patch Δ Memory at End: <arithmetic mean> 13,992kB 13,987kB ^ 1.0x smaller Overall throughput looks OK: run-malloc-benchmarks Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/ Baseline Patch Δ Execution Time: <arithmetic mean> 103ms 104ms ! 1.01x slower We're a bit slower on the "all-out large allocations on all cores" benchmark, but I think that's an OK price to pay: Baseline Patch Δ Execution Time: big --parallel 125ms 136ms ! 1.09x slower This patch net removes 1.5k lines of code. It turns out that large allocations are rare, and free memory fragments are also rare, so the combination is super rare, and a simple O(n) algorithm that ensures good memory behavior is the best option. Fun fact: In practice, the odds that the old code would save memory were *worse* than the odds that it would contain a bug that wasted memory. :) * bmalloc.xcodeproj/project.pbxproj: * bmalloc/Allocator.cpp: (bmalloc::Allocator::tryAllocate): largeMax is the new xLargeMax since xLargeMax is gone now. (bmalloc::Allocator::allocate): I moved the rounding code into allocateLarge, so we don't have to do it here. (bmalloc::Allocator::reallocate): (bmalloc::Allocator::allocateSlowCase): (bmalloc::Allocator::allocateXLarge): Deleted. No more XLarge case. * bmalloc/Allocator.h: * bmalloc/BeginTag.h: Removed. * bmalloc/BoundaryTag.h: Removed. * bmalloc/Chunk.h: (bmalloc::ChunkHash::hash): Added a hash function. The best hash function is a unique and monotonically increasing integer, and that's exactly what we typically get from the high bits of a Chunk, since the OS allocates Chunks at unique and increasing addresses. (bmalloc::Chunk::boundaryTags): Deleted. (bmalloc::Chunk::objectType): Deleted. (bmalloc::Chunk::beginTag): Deleted. (bmalloc::Chunk::endTag): Deleted. * bmalloc/Deallocator.cpp: (bmalloc::Deallocator::deallocateSlowCase): We no longer know for sure, by looking at its bit pattern, whether a pointer is small or large. Instead, any pointer with large alignment *might* be large, and when we occasionally encounter such an object, we have to consult a hash table in the Heap to find out for sure. This turns out to be just as cheap in practice. We don't deallocate large objects on the fast path anymore. We can't, because large objects have out-of-line metadata now. (bmalloc::Deallocator::deallocateXLarge): Deleted. * bmalloc/Deallocator.h: (bmalloc::Deallocator::deallocateFastCase): See deallocateSlowCase. * bmalloc/EndTag.h: Removed. * bmalloc/FreeList.cpp: Removed. * bmalloc/FreeList.h: Removed. * bmalloc/Heap.cpp: (bmalloc::Heap::allocateSmallPage): Be sure to track each chunk in the object type map, so we can distinguish small vs large objects. (bmalloc::Heap::deallocateSmallLine): No need to check object type because we know object type now by virtue of being on the small object path. (bmalloc::Heap::splitAndAllocate): Be sure to track each chunk in the object type map, so we can distinguish small vs large objects. Large objects can split across chunks, so we need to add each large object's chunk as it is allocated. (bmalloc::Heap::tryAllocateLarge): (bmalloc::Heap::allocateLarge): (bmalloc::Heap::isLarge): (bmalloc::Heap::largeSize): (bmalloc::Heap::shrinkLarge): (bmalloc::Heap::deallocateLarge): Merged in existing XLarge logic for large objects. (bmalloc::Heap::scavengeXLargeObjects): Deleted. (bmalloc::Heap::allocateXLarge): Deleted. (bmalloc::Heap::tryAllocateXLarge): Deleted. (bmalloc::Heap::xLargeSize): Deleted. (bmalloc::Heap::shrinkXLarge): Deleted. (bmalloc::Heap::deallocateXLarge): Deleted. * bmalloc/Heap.h: (bmalloc::Heap::LargeObjectHash::hash): * bmalloc/LargeObject.h: Removed. * bmalloc/Map.h: Added. (bmalloc::Map::size): (bmalloc::Map::capacity): (bmalloc::Map::get): (bmalloc::Map::set): (bmalloc::Map::remove): (bmalloc::Map::shouldGrow): (bmalloc::Map::shouldShrink): (bmalloc::Map::find): (bmalloc::Hash>::rehash): Simple hash table. * bmalloc/Object.h: * bmalloc/ObjectType.cpp: (bmalloc::objectType): * bmalloc/ObjectType.h: (bmalloc::mightBeLarge): See deallocateSlowCase. (bmalloc::isXLarge): Deleted. * bmalloc/SegregatedFreeList.cpp: Removed. * bmalloc/SegregatedFreeList.h: Removed. * bmalloc/Sizes.h: Upped smallMax to 64kB. Upping to 32kB is pretty reasonable, since sizes between 16kB and 32kB share page sizes. I went all the way up to 64kB because the GC uses 64kB blocks, and also just for extra padding to ensure that large allocations are indeed rare. * bmalloc/SortedVector.h: Removed. * bmalloc/VMHeap.cpp: (bmalloc::VMHeap::tryAllocateLargeChunk): (bmalloc::VMHeap::allocateSmallChunk): (bmalloc::VMHeap::VMHeap): Deleted. (bmalloc::VMHeap::allocateChunk): Deleted. * bmalloc/VMHeap.h: (bmalloc::VMHeap::deallocateSmallPage): (bmalloc::VMHeap::allocateLargeObject): Deleted. (bmalloc::VMHeap::deallocateLargeObject): Deleted. Nixed all the boundary tag logic since metadata is out of line now. * bmalloc/VMState.h: Removed. Instead of an abstract state, we track the precise amount of committed physical pages at the head of a VM range. This allows us to merge aggressively without triggering an madvise storm most of the time. * bmalloc/Vector.h: (bmalloc::Vector<T>::Vector): (bmalloc::Vector<T>::insert): (bmalloc::Vector<T>::remove): (bmalloc::Vector<T>::resize): Filled out some missing helpers. * bmalloc/XLargeMap.cpp: (bmalloc::XLargeMap::remove): (bmalloc::XLargeMap::add): (bmalloc::XLargeMap::removePhysical): (bmalloc::XLargeMap::takeFree): Deleted. (bmalloc::XLargeMap::addFree): Deleted. (bmalloc::XLargeMap::addAllocated): Deleted. (bmalloc::XLargeMap::getAllocated): Deleted. (bmalloc::XLargeMap::takeAllocated): Deleted. (bmalloc::XLargeMap::shrinkToFit): Deleted. (bmalloc::XLargeMap::takePhysical): Deleted. (bmalloc::XLargeMap::addVirtual): Deleted. * bmalloc/XLargeMap.h: (bmalloc::XLargeMap::Allocation::operator<): Deleted. We don't track object sizes anymore -- just free space. (The Heap tracks object sizes.) We use plain old linear search for free space. (See intro.) * bmalloc/XLargeRange.h: (bmalloc::XLargeRange::physicalSize): (bmalloc::XLargeRange::setPhysicalSize): (bmalloc::merge): (bmalloc::XLargeRange::split): (bmalloc::XLargeRange::vmState): Deleted. (bmalloc::XLargeRange::setVMState): Deleted. See VMState.h. Canonical link: https://commits.webkit.org/174881@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@199746 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2016-04-19 23:36:20 +00:00
#include "PerProcess.h"
bmalloc: small and large objects should share memory https://bugs.webkit.org/show_bug.cgi?id=155866 Reviewed by Andreas Kling. This patch cuts our VM footprint in half. (VM footprint usually doesn't matter, but on iOS there's an artificial VM limit around 700MB, and if you hit it you jetsam / crash.) It's also a step toward honoring the hardware page size at runtime, which will reduce memory usage on iOS. This patch is a small improvement in peak memory usage because it allows small and large objects to recycle each other's memory. The tradeoff is that we require more metadata, which causes more memory usage after shrinking down from peak memory usage. In the end, we have some memory wins and some losses, and a small win in the mean on our standard memory benchmarks. * bmalloc.xcodeproj/project.pbxproj: Removed SuperChunk. * bmalloc/Allocator.cpp: (bmalloc::Allocator::reallocate): Adopt a new Heap API for shrinking large objects because it's a little more complicated than it used to be. Don't check for equality in the XLarge case because we don't do it in other cases, and it's unlikely that we'll be called for no reason. * bmalloc/BumpAllocator.h: (bmalloc::BumpAllocator::allocate): Don't ASSERT isSmall because that's an old concept from when small and large objects were in distinct memory regions. * bmalloc/Deallocator.cpp: (bmalloc::Deallocator::deallocateSlowCase): Large objects are not segregated anymore. (bmalloc::Deallocator::deallocateLarge): Deleted. * bmalloc/Deallocator.h: (bmalloc::Deallocator::deallocateFastCase): Don't ASSERT isSmall(). See above. * bmalloc/Heap.cpp: (bmalloc::Heap::scavenge): (bmalloc::Heap::scavengeSmallPage): (bmalloc::Heap::scavengeSmallPages): New helpers for returning cached small pages to the large object heap. (bmalloc::Heap::allocateSmallPage): Allocate small pages from the large object heap. This is how we accomplish sharing. (bmalloc::Heap::deallocateSmallLine): Handle large objects since we can encounter them on this code path now. (bmalloc::Heap::splitAndAllocate): Fixed a bug where we would sometimes not split even though we could. Allocating a large object also requires ref'ing its small line so that we can alias memory between small and large objects. (bmalloc::Heap::allocateLarge): Return cached small pages before allocating a large object that would fit in a cached small page. This allows some large allocations to reuse small object memory. (bmalloc::Heap::shrinkLarge): New helper. (bmalloc::Heap::deallocateLarge): Deleted. * bmalloc/Heap.h: * bmalloc/LargeChunk.h: (bmalloc::LargeChunk::pageBegin): (bmalloc::LargeChunk::pageEnd): (bmalloc::LargeChunk::lines): (bmalloc::LargeChunk::pages): (bmalloc::LargeChunk::begin): (bmalloc::LargeChunk::end): (bmalloc::LargeChunk::LargeChunk): (bmalloc::LargeChunk::get): (bmalloc::LargeChunk::endTag): (bmalloc::LargeChunk::offset): (bmalloc::LargeChunk::object): (bmalloc::LargeChunk::page): (bmalloc::LargeChunk::line): (bmalloc::SmallLine::begin): (bmalloc::SmallLine::end): (bmalloc::SmallPage::begin): (bmalloc::SmallPage::end): (bmalloc::Object::Object): (bmalloc::Object::begin): (bmalloc::Object::pageBegin): (bmalloc::Object::line): (bmalloc::Object::page): I merged all the SmallChunk metadata and code into LargeChunk. Now we use a single class to track both small and large metadata, so we can share memory between small and large objects. I'm going to rename this class to Chunk in a follow-up patch. * bmalloc/Object.h: (bmalloc::Object::chunk): Updated for LargeChunk transition. * bmalloc/ObjectType.cpp: (bmalloc::objectType): * bmalloc/ObjectType.h: (bmalloc::isXLarge): (bmalloc::isSmall): Deleted. The difference between small and large objects is now stored in metadata and is not a property of their virtual address range. * bmalloc/SegregatedFreeList.h: One more entry because we cover all of what used to be the super chunk in a large chunk now. * bmalloc/Sizes.h: Removed bit masking helpers because we don't use address masks to distinguish small vs large object type anymore. * bmalloc/SmallChunk.h: Removed. * bmalloc/SmallPage.h: (bmalloc::SmallPage::SmallPage): Store object type per page because any given page can be used for large objects or small objects. * bmalloc/SuperChunk.h: Removed. * bmalloc/VMHeap.cpp: (bmalloc::VMHeap::VMHeap): (bmalloc::VMHeap::allocateLargeChunk): (bmalloc::VMHeap::allocateSmallChunk): Deleted. (bmalloc::VMHeap::allocateSuperChunk): Deleted. * bmalloc/VMHeap.h: (bmalloc::VMHeap::allocateLargeObject): (bmalloc::VMHeap::deallocateLargeObject): (bmalloc::VMHeap::allocateSmallPage): Deleted. (bmalloc::VMHeap::deallocateSmallPage): Deleted. Removed super chunk and small chunk support. * bmalloc/Zone.cpp: (bmalloc::enumerator): * bmalloc/Zone.h: (bmalloc::Zone::largeChunks): (bmalloc::Zone::addLargeChunk): (bmalloc::Zone::superChunks): Deleted. (bmalloc::Zone::addSuperChunk): Deleted. Removed super chunk and small chunk support. Canonical link: https://commits.webkit.org/173983@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@198675 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2016-03-25 18:07:31 +00:00
bmalloc https://bugs.webkit.org/show_bug.cgi?id=131170 Reviewed by Andreas Kling. Initial commit. * bmalloc: Added. * bmalloc.xcodeproj: Added. * bmalloc.xcodeproj/project.pbxproj: Added. * bmalloc/Algorithm.h: Added. (bmalloc::max): (bmalloc::min): (bmalloc::mask): (bmalloc::test): (bmalloc::roundUpToMultipleOf): (bmalloc::roundDownToMultipleOf): (bmalloc::sizeOf): (bmalloc::bitCount): (bmalloc::isPowerOfTwo): * bmalloc/Allocator.cpp: Added. (bmalloc::Allocator::Allocator): (bmalloc::Allocator::~Allocator): (bmalloc::Allocator::log): (bmalloc::Allocator::processSmallAllocatorLog): (bmalloc::Allocator::processMediumAllocatorLog): (bmalloc::Allocator::allocateLarge): (bmalloc::Allocator::allocateXLarge): (bmalloc::Allocator::allocateMedium): (bmalloc::Allocator::allocateSlowCase): * bmalloc/Allocator.h: Added. (bmalloc::Allocator::smallAllocatorFor): (bmalloc::Allocator::allocateFastCase): (bmalloc::Allocator::allocate): * bmalloc/AsyncTask.cpp: Added. (bmalloc::AsyncTask<Function>::runSlowCase): (bmalloc::AsyncTask<Function>::pthreadEntryPoint): (bmalloc::AsyncTask<Function>::entryPoint): * bmalloc/AsyncTask.h: Added. (bmalloc::Function>::AsyncTask): (bmalloc::Function>::join): (bmalloc::Function>::run): (bmalloc::Function>::runSlowCase): (bmalloc::Function>::pthreadEntryPoint): (bmalloc::Function>::entryPoint): * bmalloc/BAssert.h: Added. * bmalloc/BeginTag.h: Added. (bmalloc::BeginTag::isInFreeList): * bmalloc/BoundaryTag.h: Added. (bmalloc::BoundaryTag::isXLarge): (bmalloc::BoundaryTag::setXLarge): (bmalloc::BoundaryTag::isFree): (bmalloc::BoundaryTag::setFree): (bmalloc::BoundaryTag::isEnd): (bmalloc::BoundaryTag::setEnd): (bmalloc::BoundaryTag::hasPhysicalPages): (bmalloc::BoundaryTag::setHasPhysicalPages): (bmalloc::BoundaryTag::isNull): (bmalloc::BoundaryTag::clear): (bmalloc::BoundaryTag::size): (bmalloc::BoundaryTag::setSize): (bmalloc::BoundaryTag::prev): (bmalloc::BoundaryTag::next): * bmalloc/BoundaryTagInlines.h: Added. (bmalloc::validate): (bmalloc::validatePrev): (bmalloc::validateNext): (bmalloc::BoundaryTag::init): (bmalloc::BoundaryTag::mergeLargeLeft): (bmalloc::BoundaryTag::mergeLargeRight): (bmalloc::BoundaryTag::mergeLarge): (bmalloc::BoundaryTag::deallocate): (bmalloc::BoundaryTag::splitLarge): (bmalloc::BoundaryTag::allocate): * bmalloc/Cache.cpp: Added. (bmalloc::Cache::operator new): (bmalloc::Cache::operator delete): (bmalloc::Cache::Cache): (bmalloc::Cache::allocateSlowCase): (bmalloc::Cache::allocateSlowCaseNullCache): (bmalloc::Cache::deallocateSlowCase): (bmalloc::Cache::deallocateSlowCaseNullCache): * bmalloc/Cache.h: Added. (bmalloc::Cache::allocator): (bmalloc::Cache::deallocator): (bmalloc::Cache::allocateFastCase): (bmalloc::Cache::deallocateFastCase): (bmalloc::Cache::allocate): (bmalloc::Cache::deallocate): * bmalloc/Chunk.h: Added. (bmalloc::Chunk::begin): (bmalloc::Chunk::end): (bmalloc::Chunk::lines): (bmalloc::Chunk::pages): * bmalloc/Deallocator.cpp: Added. (bmalloc::Deallocator::Deallocator): (bmalloc::Deallocator::~Deallocator): (bmalloc::Deallocator::deallocateLarge): (bmalloc::Deallocator::deallocateXLarge): (bmalloc::Deallocator::processObjectLog): (bmalloc::Deallocator::deallocateSlowCase): (bmalloc::Deallocator::deallocateSmallLine): (bmalloc::Deallocator::allocateSmallLine): (bmalloc::Deallocator::deallocateMediumLine): (bmalloc::Deallocator::allocateMediumLine): * bmalloc/Deallocator.h: Added. (bmalloc::Deallocator::deallocateFastCase): (bmalloc::Deallocator::deallocate): * bmalloc/EndTag.h: Added. (bmalloc::EndTag::operator=): * bmalloc/FixedVector.h: Added. (bmalloc::FixedVector::begin): (bmalloc::FixedVector::end): (bmalloc::FixedVector::size): (bmalloc::FixedVector::capacity): (bmalloc::FixedVector::clear): (bmalloc::FixedVector::isEmpty): (bmalloc::Capacity>::FixedVector): (bmalloc::Capacity>::operator): (bmalloc::Capacity>::push): (bmalloc::Capacity>::pop): (bmalloc::Capacity>::shrink): * bmalloc/Heap.cpp: Added. (bmalloc::sleep): (bmalloc::Heap::Heap): (bmalloc::Heap::concurrentScavenge): (bmalloc::Heap::scavengeSmallPages): (bmalloc::Heap::scavengeMediumPages): (bmalloc::Heap::scavengeLargeRanges): (bmalloc::Heap::allocateSmallLineSlowCase): (bmalloc::Heap::allocateMediumLineSlowCase): (bmalloc::Heap::allocateXLarge): (bmalloc::Heap::deallocateXLarge): (bmalloc::Heap::allocateLarge): (bmalloc::Heap::deallocateLarge): * bmalloc/Heap.h: Added. (bmalloc::Heap::deallocateSmallLine): (bmalloc::Heap::allocateSmallLine): (bmalloc::Heap::deallocateMediumLine): (bmalloc::Heap::allocateMediumLine): * bmalloc/Inline.h: Added. * bmalloc/LargeChunk.h: Added. (bmalloc::LargeChunk::begin): (bmalloc::LargeChunk::end): (bmalloc::LargeChunk::create): (bmalloc::LargeChunk::get): (bmalloc::LargeChunk::beginTag): (bmalloc::LargeChunk::endTag): * bmalloc/Line.h: Added. (bmalloc::Line<Traits>::begin): (bmalloc::Line<Traits>::end): (bmalloc::Line<Traits>::concurrentRef): (bmalloc::Line<Traits>::deref): * bmalloc/MediumAllocator.h: Added. (bmalloc::MediumAllocator::isNull): (bmalloc::MediumAllocator::MediumAllocator): (bmalloc::MediumAllocator::line): (bmalloc::MediumAllocator::allocate): (bmalloc::MediumAllocator::derefCount): (bmalloc::MediumAllocator::refill): * bmalloc/MediumChunk.h: Added. * bmalloc/MediumLine.h: Added. * bmalloc/MediumPage.h: Added. * bmalloc/MediumTraits.h: Added. * bmalloc/Mutex.cpp: Added. (bmalloc::Mutex::lockSlowCase): * bmalloc/Mutex.h: Added. (bmalloc::Mutex::Mutex): (bmalloc::Mutex::try_lock): (bmalloc::Mutex::lock): (bmalloc::Mutex::unlock): * bmalloc/ObjectType.cpp: Added. (bmalloc::objectType): * bmalloc/ObjectType.h: Added. (bmalloc::isSmallOrMedium): (bmalloc::isSmall): * bmalloc/Page.h: Added. (bmalloc::Page<Traits>::ref): (bmalloc::Page<Traits>::deref): (bmalloc::Page<Traits>::refCount): * bmalloc/PerProcess.h: Added. (bmalloc::PerProcess::mutex): (bmalloc::PerProcess<T>::getFastCase): (bmalloc::PerProcess<T>::get): (bmalloc::PerProcess<T>::getSlowCase): * bmalloc/PerThread.h: Added. (bmalloc::PerThreadStorage<Cache>::get): (bmalloc::PerThreadStorage<Cache>::init): (bmalloc::PerThreadStorage::get): (bmalloc::PerThreadStorage::init): (bmalloc::PerThread<T>::getFastCase): (bmalloc::PerThread<T>::get): (bmalloc::PerThread<T>::destructor): (bmalloc::PerThread<T>::getSlowCase): * bmalloc/Range.h: Added. (bmalloc::Range::Range): (bmalloc::Range::begin): (bmalloc::Range::end): (bmalloc::Range::size): (bmalloc::Range::operator!): (bmalloc::Range::operator<): * bmalloc/SegregatedFreeList.cpp: Added. (bmalloc::SegregatedFreeList::SegregatedFreeList): (bmalloc::SegregatedFreeList::insert): (bmalloc::SegregatedFreeList::takeGreedy): (bmalloc::SegregatedFreeList::take): * bmalloc/SegregatedFreeList.h: Added. * bmalloc/Sizes.h: Added. * bmalloc/SmallAllocator.h: Added. (bmalloc::SmallAllocator::isNull): (bmalloc::SmallAllocator::canAllocate): (bmalloc::SmallAllocator::SmallAllocator): (bmalloc::SmallAllocator::line): (bmalloc::SmallAllocator::allocate): (bmalloc::SmallAllocator::objectCount): (bmalloc::SmallAllocator::derefCount): (bmalloc::SmallAllocator::refill): * bmalloc/SmallChunk.h: Added. * bmalloc/SmallLine.h: Added. * bmalloc/SmallPage.h: Added. * bmalloc/SmallTraits.h: Added. * bmalloc/Syscall.h: Added. * bmalloc/VMAllocate.h: Added. (bmalloc::vmSize): (bmalloc::vmValidate): (bmalloc::vmAllocate): (bmalloc::vmDeallocate): (bmalloc::vmDeallocatePhysicalPages): (bmalloc::vmAllocatePhysicalPages): (bmalloc::vmDeallocatePhysicalPagesSloppy): (bmalloc::vmAllocatePhysicalPagesSloppy): * bmalloc/VMHeap.cpp: Added. (bmalloc::VMHeap::VMHeap): (bmalloc::VMHeap::allocateSmallChunk): (bmalloc::VMHeap::allocateMediumChunk): (bmalloc::VMHeap::allocateLargeChunk): * bmalloc/VMHeap.h: Added. (bmalloc::VMHeap::allocateSmallPage): (bmalloc::VMHeap::allocateMediumPage): (bmalloc::VMHeap::allocateLargeRange): (bmalloc::VMHeap::deallocateSmallPage): (bmalloc::VMHeap::deallocateMediumPage): (bmalloc::VMHeap::deallocateLargeRange): * bmalloc/Vector.h: Added. (bmalloc::Vector::begin): (bmalloc::Vector::end): (bmalloc::Vector::size): (bmalloc::Vector::capacity): (bmalloc::Vector::last): (bmalloc::Vector::pop): (bmalloc::Vector<T>::Vector): (bmalloc::Vector<T>::~Vector): (bmalloc::Vector<T>::operator): (bmalloc::Vector<T>::push): (bmalloc::Vector<T>::pop): (bmalloc::Vector<T>::shrink): (bmalloc::Vector<T>::reallocateBuffer): (bmalloc::Vector<T>::shrinkCapacity): (bmalloc::Vector<T>::growCapacity): * bmalloc/XLargeChunk.h: Added. (bmalloc::XLargeChunk::get): (bmalloc::XLargeChunk::begin): (bmalloc::XLargeChunk::XLargeChunk): (bmalloc::XLargeChunk::create): (bmalloc::XLargeChunk::destroy): (bmalloc::XLargeChunk::range): (bmalloc::XLargeChunk::size): * bmalloc/bmalloc.h: Added. (bmalloc::api::malloc): (bmalloc::api::free): (bmalloc::api::realloc): * bmalloc/mbmalloc.cpp: Added. Canonical link: https://commits.webkit.org/149378@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@166893 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2014-04-07 23:54:11 +00:00
namespace bmalloc {
[bmalloc] bmalloc::Heap is allocated even though we use system malloc mode https://bugs.webkit.org/show_bug.cgi?id=194836 Reviewed by Mark Lam. Previously, bmalloc::Heap holds DebugHeap, and delegates allocation and deallocation to debug heap. However, bmalloc::Heap is large. We would like to avoid initialization of bmalloc::Heap under the system malloc mode. This patch extracts out DebugHeap from bmalloc::Heap, and logically puts this in a boundary of bmalloc::api. bmalloc::api delegates allocation and deallocation to DebugHeap if DebugHeap is enabled. Otherwise, using bmalloc's usual mechanism. The challenge is that we would like to keep bmalloc fast path fast. 1. For IsoHeaps, we use the similar techniques done in Cache. If the debug mode is enabled, we always go to the slow path of the IsoHeap allocation, and keep IsoTLS::get() returning nullptr. In the slow path, we just fallback to the usual bmalloc::api::tryMalloc implementation. This is efficient because bmalloc continues using the fast path. 2. For the other APIs, like freeLargeVirtual, we just put DebugHeap check because this API itself takes fair amount of time. Then debug heap check does not matter. * bmalloc/Allocator.cpp: (bmalloc::Allocator::reallocateImpl): * bmalloc/Cache.cpp: (bmalloc::Cache::tryAllocateSlowCaseNullCache): (bmalloc::Cache::allocateSlowCaseNullCache): (bmalloc::Cache::deallocateSlowCaseNullCache): (bmalloc::Cache::tryReallocateSlowCaseNullCache): (bmalloc::Cache::reallocateSlowCaseNullCache): (): Deleted. (bmalloc::debugHeap): Deleted. * bmalloc/DebugHeap.cpp: * bmalloc/DebugHeap.h: (bmalloc::DebugHeap::tryGet): * bmalloc/Heap.cpp: (bmalloc::Heap::Heap): (bmalloc::Heap::footprint): (bmalloc::Heap::tryAllocateLarge): (bmalloc::Heap::deallocateLarge): * bmalloc/Heap.h: (bmalloc::Heap::debugHeap): Deleted. * bmalloc/IsoTLS.cpp: (bmalloc::IsoTLS::IsoTLS): (bmalloc::IsoTLS::isUsingDebugHeap): Deleted. (bmalloc::IsoTLS::debugMalloc): Deleted. (bmalloc::IsoTLS::debugFree): Deleted. * bmalloc/IsoTLS.h: * bmalloc/IsoTLSInlines.h: (bmalloc::IsoTLS::allocateSlow): (bmalloc::IsoTLS::deallocateSlow): * bmalloc/ObjectType.cpp: (bmalloc::objectType): * bmalloc/ObjectType.h: * bmalloc/Scavenger.cpp: (bmalloc::Scavenger::Scavenger): * bmalloc/bmalloc.cpp: (bmalloc::api::tryLargeZeroedMemalignVirtual): (bmalloc::api::freeLargeVirtual): (bmalloc::api::scavenge): (bmalloc::api::isEnabled): (bmalloc::api::setScavengerThreadQOSClass): (bmalloc::api::commitAlignedPhysical): (bmalloc::api::decommitAlignedPhysical): (bmalloc::api::enableMiniMode): Canonical link: https://commits.webkit.org/209247@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@241847 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2019-02-21 00:03:17 +00:00
ObjectType objectType(Heap& heap, void* object)
bmalloc https://bugs.webkit.org/show_bug.cgi?id=131170 Reviewed by Andreas Kling. Initial commit. * bmalloc: Added. * bmalloc.xcodeproj: Added. * bmalloc.xcodeproj/project.pbxproj: Added. * bmalloc/Algorithm.h: Added. (bmalloc::max): (bmalloc::min): (bmalloc::mask): (bmalloc::test): (bmalloc::roundUpToMultipleOf): (bmalloc::roundDownToMultipleOf): (bmalloc::sizeOf): (bmalloc::bitCount): (bmalloc::isPowerOfTwo): * bmalloc/Allocator.cpp: Added. (bmalloc::Allocator::Allocator): (bmalloc::Allocator::~Allocator): (bmalloc::Allocator::log): (bmalloc::Allocator::processSmallAllocatorLog): (bmalloc::Allocator::processMediumAllocatorLog): (bmalloc::Allocator::allocateLarge): (bmalloc::Allocator::allocateXLarge): (bmalloc::Allocator::allocateMedium): (bmalloc::Allocator::allocateSlowCase): * bmalloc/Allocator.h: Added. (bmalloc::Allocator::smallAllocatorFor): (bmalloc::Allocator::allocateFastCase): (bmalloc::Allocator::allocate): * bmalloc/AsyncTask.cpp: Added. (bmalloc::AsyncTask<Function>::runSlowCase): (bmalloc::AsyncTask<Function>::pthreadEntryPoint): (bmalloc::AsyncTask<Function>::entryPoint): * bmalloc/AsyncTask.h: Added. (bmalloc::Function>::AsyncTask): (bmalloc::Function>::join): (bmalloc::Function>::run): (bmalloc::Function>::runSlowCase): (bmalloc::Function>::pthreadEntryPoint): (bmalloc::Function>::entryPoint): * bmalloc/BAssert.h: Added. * bmalloc/BeginTag.h: Added. (bmalloc::BeginTag::isInFreeList): * bmalloc/BoundaryTag.h: Added. (bmalloc::BoundaryTag::isXLarge): (bmalloc::BoundaryTag::setXLarge): (bmalloc::BoundaryTag::isFree): (bmalloc::BoundaryTag::setFree): (bmalloc::BoundaryTag::isEnd): (bmalloc::BoundaryTag::setEnd): (bmalloc::BoundaryTag::hasPhysicalPages): (bmalloc::BoundaryTag::setHasPhysicalPages): (bmalloc::BoundaryTag::isNull): (bmalloc::BoundaryTag::clear): (bmalloc::BoundaryTag::size): (bmalloc::BoundaryTag::setSize): (bmalloc::BoundaryTag::prev): (bmalloc::BoundaryTag::next): * bmalloc/BoundaryTagInlines.h: Added. (bmalloc::validate): (bmalloc::validatePrev): (bmalloc::validateNext): (bmalloc::BoundaryTag::init): (bmalloc::BoundaryTag::mergeLargeLeft): (bmalloc::BoundaryTag::mergeLargeRight): (bmalloc::BoundaryTag::mergeLarge): (bmalloc::BoundaryTag::deallocate): (bmalloc::BoundaryTag::splitLarge): (bmalloc::BoundaryTag::allocate): * bmalloc/Cache.cpp: Added. (bmalloc::Cache::operator new): (bmalloc::Cache::operator delete): (bmalloc::Cache::Cache): (bmalloc::Cache::allocateSlowCase): (bmalloc::Cache::allocateSlowCaseNullCache): (bmalloc::Cache::deallocateSlowCase): (bmalloc::Cache::deallocateSlowCaseNullCache): * bmalloc/Cache.h: Added. (bmalloc::Cache::allocator): (bmalloc::Cache::deallocator): (bmalloc::Cache::allocateFastCase): (bmalloc::Cache::deallocateFastCase): (bmalloc::Cache::allocate): (bmalloc::Cache::deallocate): * bmalloc/Chunk.h: Added. (bmalloc::Chunk::begin): (bmalloc::Chunk::end): (bmalloc::Chunk::lines): (bmalloc::Chunk::pages): * bmalloc/Deallocator.cpp: Added. (bmalloc::Deallocator::Deallocator): (bmalloc::Deallocator::~Deallocator): (bmalloc::Deallocator::deallocateLarge): (bmalloc::Deallocator::deallocateXLarge): (bmalloc::Deallocator::processObjectLog): (bmalloc::Deallocator::deallocateSlowCase): (bmalloc::Deallocator::deallocateSmallLine): (bmalloc::Deallocator::allocateSmallLine): (bmalloc::Deallocator::deallocateMediumLine): (bmalloc::Deallocator::allocateMediumLine): * bmalloc/Deallocator.h: Added. (bmalloc::Deallocator::deallocateFastCase): (bmalloc::Deallocator::deallocate): * bmalloc/EndTag.h: Added. (bmalloc::EndTag::operator=): * bmalloc/FixedVector.h: Added. (bmalloc::FixedVector::begin): (bmalloc::FixedVector::end): (bmalloc::FixedVector::size): (bmalloc::FixedVector::capacity): (bmalloc::FixedVector::clear): (bmalloc::FixedVector::isEmpty): (bmalloc::Capacity>::FixedVector): (bmalloc::Capacity>::operator): (bmalloc::Capacity>::push): (bmalloc::Capacity>::pop): (bmalloc::Capacity>::shrink): * bmalloc/Heap.cpp: Added. (bmalloc::sleep): (bmalloc::Heap::Heap): (bmalloc::Heap::concurrentScavenge): (bmalloc::Heap::scavengeSmallPages): (bmalloc::Heap::scavengeMediumPages): (bmalloc::Heap::scavengeLargeRanges): (bmalloc::Heap::allocateSmallLineSlowCase): (bmalloc::Heap::allocateMediumLineSlowCase): (bmalloc::Heap::allocateXLarge): (bmalloc::Heap::deallocateXLarge): (bmalloc::Heap::allocateLarge): (bmalloc::Heap::deallocateLarge): * bmalloc/Heap.h: Added. (bmalloc::Heap::deallocateSmallLine): (bmalloc::Heap::allocateSmallLine): (bmalloc::Heap::deallocateMediumLine): (bmalloc::Heap::allocateMediumLine): * bmalloc/Inline.h: Added. * bmalloc/LargeChunk.h: Added. (bmalloc::LargeChunk::begin): (bmalloc::LargeChunk::end): (bmalloc::LargeChunk::create): (bmalloc::LargeChunk::get): (bmalloc::LargeChunk::beginTag): (bmalloc::LargeChunk::endTag): * bmalloc/Line.h: Added. (bmalloc::Line<Traits>::begin): (bmalloc::Line<Traits>::end): (bmalloc::Line<Traits>::concurrentRef): (bmalloc::Line<Traits>::deref): * bmalloc/MediumAllocator.h: Added. (bmalloc::MediumAllocator::isNull): (bmalloc::MediumAllocator::MediumAllocator): (bmalloc::MediumAllocator::line): (bmalloc::MediumAllocator::allocate): (bmalloc::MediumAllocator::derefCount): (bmalloc::MediumAllocator::refill): * bmalloc/MediumChunk.h: Added. * bmalloc/MediumLine.h: Added. * bmalloc/MediumPage.h: Added. * bmalloc/MediumTraits.h: Added. * bmalloc/Mutex.cpp: Added. (bmalloc::Mutex::lockSlowCase): * bmalloc/Mutex.h: Added. (bmalloc::Mutex::Mutex): (bmalloc::Mutex::try_lock): (bmalloc::Mutex::lock): (bmalloc::Mutex::unlock): * bmalloc/ObjectType.cpp: Added. (bmalloc::objectType): * bmalloc/ObjectType.h: Added. (bmalloc::isSmallOrMedium): (bmalloc::isSmall): * bmalloc/Page.h: Added. (bmalloc::Page<Traits>::ref): (bmalloc::Page<Traits>::deref): (bmalloc::Page<Traits>::refCount): * bmalloc/PerProcess.h: Added. (bmalloc::PerProcess::mutex): (bmalloc::PerProcess<T>::getFastCase): (bmalloc::PerProcess<T>::get): (bmalloc::PerProcess<T>::getSlowCase): * bmalloc/PerThread.h: Added. (bmalloc::PerThreadStorage<Cache>::get): (bmalloc::PerThreadStorage<Cache>::init): (bmalloc::PerThreadStorage::get): (bmalloc::PerThreadStorage::init): (bmalloc::PerThread<T>::getFastCase): (bmalloc::PerThread<T>::get): (bmalloc::PerThread<T>::destructor): (bmalloc::PerThread<T>::getSlowCase): * bmalloc/Range.h: Added. (bmalloc::Range::Range): (bmalloc::Range::begin): (bmalloc::Range::end): (bmalloc::Range::size): (bmalloc::Range::operator!): (bmalloc::Range::operator<): * bmalloc/SegregatedFreeList.cpp: Added. (bmalloc::SegregatedFreeList::SegregatedFreeList): (bmalloc::SegregatedFreeList::insert): (bmalloc::SegregatedFreeList::takeGreedy): (bmalloc::SegregatedFreeList::take): * bmalloc/SegregatedFreeList.h: Added. * bmalloc/Sizes.h: Added. * bmalloc/SmallAllocator.h: Added. (bmalloc::SmallAllocator::isNull): (bmalloc::SmallAllocator::canAllocate): (bmalloc::SmallAllocator::SmallAllocator): (bmalloc::SmallAllocator::line): (bmalloc::SmallAllocator::allocate): (bmalloc::SmallAllocator::objectCount): (bmalloc::SmallAllocator::derefCount): (bmalloc::SmallAllocator::refill): * bmalloc/SmallChunk.h: Added. * bmalloc/SmallLine.h: Added. * bmalloc/SmallPage.h: Added. * bmalloc/SmallTraits.h: Added. * bmalloc/Syscall.h: Added. * bmalloc/VMAllocate.h: Added. (bmalloc::vmSize): (bmalloc::vmValidate): (bmalloc::vmAllocate): (bmalloc::vmDeallocate): (bmalloc::vmDeallocatePhysicalPages): (bmalloc::vmAllocatePhysicalPages): (bmalloc::vmDeallocatePhysicalPagesSloppy): (bmalloc::vmAllocatePhysicalPagesSloppy): * bmalloc/VMHeap.cpp: Added. (bmalloc::VMHeap::VMHeap): (bmalloc::VMHeap::allocateSmallChunk): (bmalloc::VMHeap::allocateMediumChunk): (bmalloc::VMHeap::allocateLargeChunk): * bmalloc/VMHeap.h: Added. (bmalloc::VMHeap::allocateSmallPage): (bmalloc::VMHeap::allocateMediumPage): (bmalloc::VMHeap::allocateLargeRange): (bmalloc::VMHeap::deallocateSmallPage): (bmalloc::VMHeap::deallocateMediumPage): (bmalloc::VMHeap::deallocateLargeRange): * bmalloc/Vector.h: Added. (bmalloc::Vector::begin): (bmalloc::Vector::end): (bmalloc::Vector::size): (bmalloc::Vector::capacity): (bmalloc::Vector::last): (bmalloc::Vector::pop): (bmalloc::Vector<T>::Vector): (bmalloc::Vector<T>::~Vector): (bmalloc::Vector<T>::operator): (bmalloc::Vector<T>::push): (bmalloc::Vector<T>::pop): (bmalloc::Vector<T>::shrink): (bmalloc::Vector<T>::reallocateBuffer): (bmalloc::Vector<T>::shrinkCapacity): (bmalloc::Vector<T>::growCapacity): * bmalloc/XLargeChunk.h: Added. (bmalloc::XLargeChunk::get): (bmalloc::XLargeChunk::begin): (bmalloc::XLargeChunk::XLargeChunk): (bmalloc::XLargeChunk::create): (bmalloc::XLargeChunk::destroy): (bmalloc::XLargeChunk::range): (bmalloc::XLargeChunk::size): * bmalloc/bmalloc.h: Added. (bmalloc::api::malloc): (bmalloc::api::free): (bmalloc::api::realloc): * bmalloc/mbmalloc.cpp: Added. Canonical link: https://commits.webkit.org/149378@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@166893 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2014-04-07 23:54:11 +00:00
{
bmalloc: Merge the large and xlarge allocators https://bugs.webkit.org/show_bug.cgi?id=156734 Reviewed by Andreas Kling. This give us better defense against worst case memory usage: Baseline Patch Δ Peak Memory: nimlang 198,132kB 181,468kB ^ 1.09x smaller It also eliminates inline metadata for large objects, fixing the regression introduced in r198675, and more: run-malloc-benchmarks Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/ Baseline Patch Δ Memory at End: big 10,880kB 3,328kB ^ 3.27x smaller facebook 3,112kB 2,868kB ^ 1.09x smaller fragment --parallel 1,848kB 760kB ^ 2.43x smaller fragment_iterate --parallel 4,908kB 776kB ^ 6.32x smaller big --parallel 48,076kB 11,892kB ^ 4.04x smaller Overall memory use looks OK: run-malloc-benchmarks --memory_warning Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/ Baseline Patch Δ Memory at End: <arithmetic mean> 13,992kB 13,987kB ^ 1.0x smaller Overall throughput looks OK: run-malloc-benchmarks Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/ Baseline Patch Δ Execution Time: <arithmetic mean> 103ms 104ms ! 1.01x slower We're a bit slower on the "all-out large allocations on all cores" benchmark, but I think that's an OK price to pay: Baseline Patch Δ Execution Time: big --parallel 125ms 136ms ! 1.09x slower This patch net removes 1.5k lines of code. It turns out that large allocations are rare, and free memory fragments are also rare, so the combination is super rare, and a simple O(n) algorithm that ensures good memory behavior is the best option. Fun fact: In practice, the odds that the old code would save memory were *worse* than the odds that it would contain a bug that wasted memory. :) * bmalloc.xcodeproj/project.pbxproj: * bmalloc/Allocator.cpp: (bmalloc::Allocator::tryAllocate): largeMax is the new xLargeMax since xLargeMax is gone now. (bmalloc::Allocator::allocate): I moved the rounding code into allocateLarge, so we don't have to do it here. (bmalloc::Allocator::reallocate): (bmalloc::Allocator::allocateSlowCase): (bmalloc::Allocator::allocateXLarge): Deleted. No more XLarge case. * bmalloc/Allocator.h: * bmalloc/BeginTag.h: Removed. * bmalloc/BoundaryTag.h: Removed. * bmalloc/Chunk.h: (bmalloc::ChunkHash::hash): Added a hash function. The best hash function is a unique and monotonically increasing integer, and that's exactly what we typically get from the high bits of a Chunk, since the OS allocates Chunks at unique and increasing addresses. (bmalloc::Chunk::boundaryTags): Deleted. (bmalloc::Chunk::objectType): Deleted. (bmalloc::Chunk::beginTag): Deleted. (bmalloc::Chunk::endTag): Deleted. * bmalloc/Deallocator.cpp: (bmalloc::Deallocator::deallocateSlowCase): We no longer know for sure, by looking at its bit pattern, whether a pointer is small or large. Instead, any pointer with large alignment *might* be large, and when we occasionally encounter such an object, we have to consult a hash table in the Heap to find out for sure. This turns out to be just as cheap in practice. We don't deallocate large objects on the fast path anymore. We can't, because large objects have out-of-line metadata now. (bmalloc::Deallocator::deallocateXLarge): Deleted. * bmalloc/Deallocator.h: (bmalloc::Deallocator::deallocateFastCase): See deallocateSlowCase. * bmalloc/EndTag.h: Removed. * bmalloc/FreeList.cpp: Removed. * bmalloc/FreeList.h: Removed. * bmalloc/Heap.cpp: (bmalloc::Heap::allocateSmallPage): Be sure to track each chunk in the object type map, so we can distinguish small vs large objects. (bmalloc::Heap::deallocateSmallLine): No need to check object type because we know object type now by virtue of being on the small object path. (bmalloc::Heap::splitAndAllocate): Be sure to track each chunk in the object type map, so we can distinguish small vs large objects. Large objects can split across chunks, so we need to add each large object's chunk as it is allocated. (bmalloc::Heap::tryAllocateLarge): (bmalloc::Heap::allocateLarge): (bmalloc::Heap::isLarge): (bmalloc::Heap::largeSize): (bmalloc::Heap::shrinkLarge): (bmalloc::Heap::deallocateLarge): Merged in existing XLarge logic for large objects. (bmalloc::Heap::scavengeXLargeObjects): Deleted. (bmalloc::Heap::allocateXLarge): Deleted. (bmalloc::Heap::tryAllocateXLarge): Deleted. (bmalloc::Heap::xLargeSize): Deleted. (bmalloc::Heap::shrinkXLarge): Deleted. (bmalloc::Heap::deallocateXLarge): Deleted. * bmalloc/Heap.h: (bmalloc::Heap::LargeObjectHash::hash): * bmalloc/LargeObject.h: Removed. * bmalloc/Map.h: Added. (bmalloc::Map::size): (bmalloc::Map::capacity): (bmalloc::Map::get): (bmalloc::Map::set): (bmalloc::Map::remove): (bmalloc::Map::shouldGrow): (bmalloc::Map::shouldShrink): (bmalloc::Map::find): (bmalloc::Hash>::rehash): Simple hash table. * bmalloc/Object.h: * bmalloc/ObjectType.cpp: (bmalloc::objectType): * bmalloc/ObjectType.h: (bmalloc::mightBeLarge): See deallocateSlowCase. (bmalloc::isXLarge): Deleted. * bmalloc/SegregatedFreeList.cpp: Removed. * bmalloc/SegregatedFreeList.h: Removed. * bmalloc/Sizes.h: Upped smallMax to 64kB. Upping to 32kB is pretty reasonable, since sizes between 16kB and 32kB share page sizes. I went all the way up to 64kB because the GC uses 64kB blocks, and also just for extra padding to ensure that large allocations are indeed rare. * bmalloc/SortedVector.h: Removed. * bmalloc/VMHeap.cpp: (bmalloc::VMHeap::tryAllocateLargeChunk): (bmalloc::VMHeap::allocateSmallChunk): (bmalloc::VMHeap::VMHeap): Deleted. (bmalloc::VMHeap::allocateChunk): Deleted. * bmalloc/VMHeap.h: (bmalloc::VMHeap::deallocateSmallPage): (bmalloc::VMHeap::allocateLargeObject): Deleted. (bmalloc::VMHeap::deallocateLargeObject): Deleted. Nixed all the boundary tag logic since metadata is out of line now. * bmalloc/VMState.h: Removed. Instead of an abstract state, we track the precise amount of committed physical pages at the head of a VM range. This allows us to merge aggressively without triggering an madvise storm most of the time. * bmalloc/Vector.h: (bmalloc::Vector<T>::Vector): (bmalloc::Vector<T>::insert): (bmalloc::Vector<T>::remove): (bmalloc::Vector<T>::resize): Filled out some missing helpers. * bmalloc/XLargeMap.cpp: (bmalloc::XLargeMap::remove): (bmalloc::XLargeMap::add): (bmalloc::XLargeMap::removePhysical): (bmalloc::XLargeMap::takeFree): Deleted. (bmalloc::XLargeMap::addFree): Deleted. (bmalloc::XLargeMap::addAllocated): Deleted. (bmalloc::XLargeMap::getAllocated): Deleted. (bmalloc::XLargeMap::takeAllocated): Deleted. (bmalloc::XLargeMap::shrinkToFit): Deleted. (bmalloc::XLargeMap::takePhysical): Deleted. (bmalloc::XLargeMap::addVirtual): Deleted. * bmalloc/XLargeMap.h: (bmalloc::XLargeMap::Allocation::operator<): Deleted. We don't track object sizes anymore -- just free space. (The Heap tracks object sizes.) We use plain old linear search for free space. (See intro.) * bmalloc/XLargeRange.h: (bmalloc::XLargeRange::physicalSize): (bmalloc::XLargeRange::setPhysicalSize): (bmalloc::merge): (bmalloc::XLargeRange::split): (bmalloc::XLargeRange::vmState): Deleted. (bmalloc::XLargeRange::setVMState): Deleted. See VMState.h. Canonical link: https://commits.webkit.org/174881@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@199746 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2016-04-19 23:36:20 +00:00
if (mightBeLarge(object)) {
if (!object)
return ObjectType::Small;
[bmalloc] Introduce lock-less ObjectType query https://bugs.webkit.org/show_bug.cgi?id=211809 Reviewed by Mark Lam. This patch introduces ObjectTypeTable, which allows lock-less ObjectType query for Chunk*. It has bit-vector to store ObjectType per address. And each bit represents 1MB of VA region since Chunk*'s size is at least 1MB and ObjectType is 1bit data. Every time we extend this bit-vector to support larger VA region, we do not free the old bit-vector. Since we always allocate power-of-2 sized bit-vector, # of extension is limited and it does not waste much memory because Chunk's size is enough large (1MB). Since each 4KB page on macOS can represent a bit-vector for 32GB VA region, in practice, this extension almost never happens. I verified that 4KB page can handle memory allocations in JetStream2 and Gmail. * CMakeLists.txt: * bmalloc.xcodeproj/project.pbxproj: * bmalloc/Algorithm.h: (bmalloc::roundUpToPowerOfTwo): * bmalloc/Deallocator.cpp: (bmalloc::Deallocator::deallocateSlowCase): * bmalloc/Heap.cpp: (bmalloc::Heap::freeableMemory): (bmalloc::Heap::decommitLargeRange): (bmalloc::Heap::scavenge): (bmalloc::Heap::scavengeToHighWatermark): (bmalloc::Heap::allocateSmallChunk): (bmalloc::Heap::deallocateSmallChunk): (bmalloc::Heap::deallocateSmallLine): (bmalloc::Heap::splitAndAllocate): (bmalloc::Heap::isLarge): Deleted. * bmalloc/Heap.h: (bmalloc::Heap::isLarge): * bmalloc/ObjectType.cpp: (bmalloc::objectType): * bmalloc/ObjectTypeTable.cpp: Added. (bmalloc::ObjectTypeTable::set): * bmalloc/ObjectTypeTable.h: Added. (bmalloc::ObjectTypeTable::convertToIndex): (bmalloc::ObjectTypeTable::Bits::Bits): (bmalloc::ObjectTypeTable::Bits::previous const): (bmalloc::ObjectTypeTable::Bits::begin const): (bmalloc::ObjectTypeTable::Bits::end const): (bmalloc::ObjectTypeTable::Bits::count const): (bmalloc::ObjectTypeTable::Bits::sizeInBytes const): (bmalloc::ObjectTypeTable::Bits::words const): (bmalloc::ObjectTypeTable::Bits::words): (bmalloc::ObjectTypeTable::ObjectTypeTable): (bmalloc::ObjectTypeTable::get): (bmalloc::ObjectTypeTable::Bits::get): (bmalloc::ObjectTypeTable::Bits::set): (bmalloc::ObjectTypeTable::Bits::wordForIndex): * bmalloc/Scavenger.cpp: (bmalloc::Scavenger::scavenge): (bmalloc::Scavenger::partialScavenge): (bmalloc::Scavenger::freeableMemory): Canonical link: https://commits.webkit.org/224764@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@261667 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2020-05-14 01:09:19 +00:00
if (heap.isLarge(object))
bmalloc: Merge the large and xlarge allocators https://bugs.webkit.org/show_bug.cgi?id=156734 Reviewed by Andreas Kling. This give us better defense against worst case memory usage: Baseline Patch Δ Peak Memory: nimlang 198,132kB 181,468kB ^ 1.09x smaller It also eliminates inline metadata for large objects, fixing the regression introduced in r198675, and more: run-malloc-benchmarks Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/ Baseline Patch Δ Memory at End: big 10,880kB 3,328kB ^ 3.27x smaller facebook 3,112kB 2,868kB ^ 1.09x smaller fragment --parallel 1,848kB 760kB ^ 2.43x smaller fragment_iterate --parallel 4,908kB 776kB ^ 6.32x smaller big --parallel 48,076kB 11,892kB ^ 4.04x smaller Overall memory use looks OK: run-malloc-benchmarks --memory_warning Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/ Baseline Patch Δ Memory at End: <arithmetic mean> 13,992kB 13,987kB ^ 1.0x smaller Overall throughput looks OK: run-malloc-benchmarks Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/ Baseline Patch Δ Execution Time: <arithmetic mean> 103ms 104ms ! 1.01x slower We're a bit slower on the "all-out large allocations on all cores" benchmark, but I think that's an OK price to pay: Baseline Patch Δ Execution Time: big --parallel 125ms 136ms ! 1.09x slower This patch net removes 1.5k lines of code. It turns out that large allocations are rare, and free memory fragments are also rare, so the combination is super rare, and a simple O(n) algorithm that ensures good memory behavior is the best option. Fun fact: In practice, the odds that the old code would save memory were *worse* than the odds that it would contain a bug that wasted memory. :) * bmalloc.xcodeproj/project.pbxproj: * bmalloc/Allocator.cpp: (bmalloc::Allocator::tryAllocate): largeMax is the new xLargeMax since xLargeMax is gone now. (bmalloc::Allocator::allocate): I moved the rounding code into allocateLarge, so we don't have to do it here. (bmalloc::Allocator::reallocate): (bmalloc::Allocator::allocateSlowCase): (bmalloc::Allocator::allocateXLarge): Deleted. No more XLarge case. * bmalloc/Allocator.h: * bmalloc/BeginTag.h: Removed. * bmalloc/BoundaryTag.h: Removed. * bmalloc/Chunk.h: (bmalloc::ChunkHash::hash): Added a hash function. The best hash function is a unique and monotonically increasing integer, and that's exactly what we typically get from the high bits of a Chunk, since the OS allocates Chunks at unique and increasing addresses. (bmalloc::Chunk::boundaryTags): Deleted. (bmalloc::Chunk::objectType): Deleted. (bmalloc::Chunk::beginTag): Deleted. (bmalloc::Chunk::endTag): Deleted. * bmalloc/Deallocator.cpp: (bmalloc::Deallocator::deallocateSlowCase): We no longer know for sure, by looking at its bit pattern, whether a pointer is small or large. Instead, any pointer with large alignment *might* be large, and when we occasionally encounter such an object, we have to consult a hash table in the Heap to find out for sure. This turns out to be just as cheap in practice. We don't deallocate large objects on the fast path anymore. We can't, because large objects have out-of-line metadata now. (bmalloc::Deallocator::deallocateXLarge): Deleted. * bmalloc/Deallocator.h: (bmalloc::Deallocator::deallocateFastCase): See deallocateSlowCase. * bmalloc/EndTag.h: Removed. * bmalloc/FreeList.cpp: Removed. * bmalloc/FreeList.h: Removed. * bmalloc/Heap.cpp: (bmalloc::Heap::allocateSmallPage): Be sure to track each chunk in the object type map, so we can distinguish small vs large objects. (bmalloc::Heap::deallocateSmallLine): No need to check object type because we know object type now by virtue of being on the small object path. (bmalloc::Heap::splitAndAllocate): Be sure to track each chunk in the object type map, so we can distinguish small vs large objects. Large objects can split across chunks, so we need to add each large object's chunk as it is allocated. (bmalloc::Heap::tryAllocateLarge): (bmalloc::Heap::allocateLarge): (bmalloc::Heap::isLarge): (bmalloc::Heap::largeSize): (bmalloc::Heap::shrinkLarge): (bmalloc::Heap::deallocateLarge): Merged in existing XLarge logic for large objects. (bmalloc::Heap::scavengeXLargeObjects): Deleted. (bmalloc::Heap::allocateXLarge): Deleted. (bmalloc::Heap::tryAllocateXLarge): Deleted. (bmalloc::Heap::xLargeSize): Deleted. (bmalloc::Heap::shrinkXLarge): Deleted. (bmalloc::Heap::deallocateXLarge): Deleted. * bmalloc/Heap.h: (bmalloc::Heap::LargeObjectHash::hash): * bmalloc/LargeObject.h: Removed. * bmalloc/Map.h: Added. (bmalloc::Map::size): (bmalloc::Map::capacity): (bmalloc::Map::get): (bmalloc::Map::set): (bmalloc::Map::remove): (bmalloc::Map::shouldGrow): (bmalloc::Map::shouldShrink): (bmalloc::Map::find): (bmalloc::Hash>::rehash): Simple hash table. * bmalloc/Object.h: * bmalloc/ObjectType.cpp: (bmalloc::objectType): * bmalloc/ObjectType.h: (bmalloc::mightBeLarge): See deallocateSlowCase. (bmalloc::isXLarge): Deleted. * bmalloc/SegregatedFreeList.cpp: Removed. * bmalloc/SegregatedFreeList.h: Removed. * bmalloc/Sizes.h: Upped smallMax to 64kB. Upping to 32kB is pretty reasonable, since sizes between 16kB and 32kB share page sizes. I went all the way up to 64kB because the GC uses 64kB blocks, and also just for extra padding to ensure that large allocations are indeed rare. * bmalloc/SortedVector.h: Removed. * bmalloc/VMHeap.cpp: (bmalloc::VMHeap::tryAllocateLargeChunk): (bmalloc::VMHeap::allocateSmallChunk): (bmalloc::VMHeap::VMHeap): Deleted. (bmalloc::VMHeap::allocateChunk): Deleted. * bmalloc/VMHeap.h: (bmalloc::VMHeap::deallocateSmallPage): (bmalloc::VMHeap::allocateLargeObject): Deleted. (bmalloc::VMHeap::deallocateLargeObject): Deleted. Nixed all the boundary tag logic since metadata is out of line now. * bmalloc/VMState.h: Removed. Instead of an abstract state, we track the precise amount of committed physical pages at the head of a VM range. This allows us to merge aggressively without triggering an madvise storm most of the time. * bmalloc/Vector.h: (bmalloc::Vector<T>::Vector): (bmalloc::Vector<T>::insert): (bmalloc::Vector<T>::remove): (bmalloc::Vector<T>::resize): Filled out some missing helpers. * bmalloc/XLargeMap.cpp: (bmalloc::XLargeMap::remove): (bmalloc::XLargeMap::add): (bmalloc::XLargeMap::removePhysical): (bmalloc::XLargeMap::takeFree): Deleted. (bmalloc::XLargeMap::addFree): Deleted. (bmalloc::XLargeMap::addAllocated): Deleted. (bmalloc::XLargeMap::getAllocated): Deleted. (bmalloc::XLargeMap::takeAllocated): Deleted. (bmalloc::XLargeMap::shrinkToFit): Deleted. (bmalloc::XLargeMap::takePhysical): Deleted. (bmalloc::XLargeMap::addVirtual): Deleted. * bmalloc/XLargeMap.h: (bmalloc::XLargeMap::Allocation::operator<): Deleted. We don't track object sizes anymore -- just free space. (The Heap tracks object sizes.) We use plain old linear search for free space. (See intro.) * bmalloc/XLargeRange.h: (bmalloc::XLargeRange::physicalSize): (bmalloc::XLargeRange::setPhysicalSize): (bmalloc::merge): (bmalloc::XLargeRange::split): (bmalloc::XLargeRange::vmState): Deleted. (bmalloc::XLargeRange::setVMState): Deleted. See VMState.h. Canonical link: https://commits.webkit.org/174881@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@199746 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2016-04-19 23:36:20 +00:00
return ObjectType::Large;
}
bmalloc: refactored XLarge allocation for better alignment https://bugs.webkit.org/show_bug.cgi?id=140582 Reviewed by Andreas Kling. XLarge objects used to be Large objects with an extra bit of metadata that said "actually, I'm not large -- I'm extra large". The metadata header in an XLarge allocation made it impossible for the XLarge object to honor a very large alignment request. The solution is to stop using a metadata header for XLarge objects, and instead to store explicit metadata on the side. This is a bit less astonishing, which is also nice. Finding XLarge metadata is now a linear search. That's probably OK, since it was always so in TCMalloc, and the usual number of XLarge allocations in a process is 0. This design makes it possible for the heap to cache XLarge allocations with and/or without physical pages. I haven't actually done that yet because the tradeoffs are subtle, so I don't want to do anything without a motivating test case. * bmalloc.xcodeproj/project.pbxproj: * bmalloc/Allocator.cpp: (bmalloc::Allocator::reallocate): Removed the concept of an XLargeChunk, since an XLarge allocation is now just a naked buffer without a header. (bmalloc::Allocator::allocateXLarge): Added an explicit qualifier for XLarge alignment, since XLargeChunk won't give this to us implicitly anymore. * bmalloc/BoundaryTag.h: (bmalloc::BoundaryTag::setRange): (bmalloc::BoundaryTag::isXLarge): Deleted. (bmalloc::BoundaryTag::setXLarge): Deleted. * bmalloc/BoundaryTagInlines.h: (bmalloc::validate): (bmalloc::BoundaryTag::deallocate): Removed the XLarge hacks from Large allocations. * bmalloc/Deallocator.cpp: (bmalloc::Deallocator::deallocateXLarge): (bmalloc::Deallocator::deallocateSlowCase): * bmalloc/Heap.cpp: (bmalloc::Heap::findXLarge): (bmalloc::Heap::allocateXLarge): (bmalloc::Heap::deallocateXLarge): * bmalloc/Heap.h: Updated for interface changes. * bmalloc/ObjectType.cpp: (bmalloc::objectType): * bmalloc/ObjectType.h: (bmalloc::isXLarge): We can now tell if a pointer is XLarge just by examining its bit pattern -- just like we do for other kinds of allocations -- which is nice. * bmalloc/Sizes.h: * bmalloc/VMHeap.h: (bmalloc::VMHeap::allocateXLarge): (bmalloc::VMHeap::findXLarge): (bmalloc::VMHeap::deallocateXLarge): Keep an explicit vector of metadata for XLarge allocations. * bmalloc/XLargeChunk.h: Removed. Canonical link: https://commits.webkit.org/158554@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@178621 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2015-01-17 02:53:28 +00:00
bmalloc: Merge the large and xlarge allocators https://bugs.webkit.org/show_bug.cgi?id=156734 Reviewed by Andreas Kling. This give us better defense against worst case memory usage: Baseline Patch Δ Peak Memory: nimlang 198,132kB 181,468kB ^ 1.09x smaller It also eliminates inline metadata for large objects, fixing the regression introduced in r198675, and more: run-malloc-benchmarks Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/ Baseline Patch Δ Memory at End: big 10,880kB 3,328kB ^ 3.27x smaller facebook 3,112kB 2,868kB ^ 1.09x smaller fragment --parallel 1,848kB 760kB ^ 2.43x smaller fragment_iterate --parallel 4,908kB 776kB ^ 6.32x smaller big --parallel 48,076kB 11,892kB ^ 4.04x smaller Overall memory use looks OK: run-malloc-benchmarks --memory_warning Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/ Baseline Patch Δ Memory at End: <arithmetic mean> 13,992kB 13,987kB ^ 1.0x smaller Overall throughput looks OK: run-malloc-benchmarks Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/ Baseline Patch Δ Execution Time: <arithmetic mean> 103ms 104ms ! 1.01x slower We're a bit slower on the "all-out large allocations on all cores" benchmark, but I think that's an OK price to pay: Baseline Patch Δ Execution Time: big --parallel 125ms 136ms ! 1.09x slower This patch net removes 1.5k lines of code. It turns out that large allocations are rare, and free memory fragments are also rare, so the combination is super rare, and a simple O(n) algorithm that ensures good memory behavior is the best option. Fun fact: In practice, the odds that the old code would save memory were *worse* than the odds that it would contain a bug that wasted memory. :) * bmalloc.xcodeproj/project.pbxproj: * bmalloc/Allocator.cpp: (bmalloc::Allocator::tryAllocate): largeMax is the new xLargeMax since xLargeMax is gone now. (bmalloc::Allocator::allocate): I moved the rounding code into allocateLarge, so we don't have to do it here. (bmalloc::Allocator::reallocate): (bmalloc::Allocator::allocateSlowCase): (bmalloc::Allocator::allocateXLarge): Deleted. No more XLarge case. * bmalloc/Allocator.h: * bmalloc/BeginTag.h: Removed. * bmalloc/BoundaryTag.h: Removed. * bmalloc/Chunk.h: (bmalloc::ChunkHash::hash): Added a hash function. The best hash function is a unique and monotonically increasing integer, and that's exactly what we typically get from the high bits of a Chunk, since the OS allocates Chunks at unique and increasing addresses. (bmalloc::Chunk::boundaryTags): Deleted. (bmalloc::Chunk::objectType): Deleted. (bmalloc::Chunk::beginTag): Deleted. (bmalloc::Chunk::endTag): Deleted. * bmalloc/Deallocator.cpp: (bmalloc::Deallocator::deallocateSlowCase): We no longer know for sure, by looking at its bit pattern, whether a pointer is small or large. Instead, any pointer with large alignment *might* be large, and when we occasionally encounter such an object, we have to consult a hash table in the Heap to find out for sure. This turns out to be just as cheap in practice. We don't deallocate large objects on the fast path anymore. We can't, because large objects have out-of-line metadata now. (bmalloc::Deallocator::deallocateXLarge): Deleted. * bmalloc/Deallocator.h: (bmalloc::Deallocator::deallocateFastCase): See deallocateSlowCase. * bmalloc/EndTag.h: Removed. * bmalloc/FreeList.cpp: Removed. * bmalloc/FreeList.h: Removed. * bmalloc/Heap.cpp: (bmalloc::Heap::allocateSmallPage): Be sure to track each chunk in the object type map, so we can distinguish small vs large objects. (bmalloc::Heap::deallocateSmallLine): No need to check object type because we know object type now by virtue of being on the small object path. (bmalloc::Heap::splitAndAllocate): Be sure to track each chunk in the object type map, so we can distinguish small vs large objects. Large objects can split across chunks, so we need to add each large object's chunk as it is allocated. (bmalloc::Heap::tryAllocateLarge): (bmalloc::Heap::allocateLarge): (bmalloc::Heap::isLarge): (bmalloc::Heap::largeSize): (bmalloc::Heap::shrinkLarge): (bmalloc::Heap::deallocateLarge): Merged in existing XLarge logic for large objects. (bmalloc::Heap::scavengeXLargeObjects): Deleted. (bmalloc::Heap::allocateXLarge): Deleted. (bmalloc::Heap::tryAllocateXLarge): Deleted. (bmalloc::Heap::xLargeSize): Deleted. (bmalloc::Heap::shrinkXLarge): Deleted. (bmalloc::Heap::deallocateXLarge): Deleted. * bmalloc/Heap.h: (bmalloc::Heap::LargeObjectHash::hash): * bmalloc/LargeObject.h: Removed. * bmalloc/Map.h: Added. (bmalloc::Map::size): (bmalloc::Map::capacity): (bmalloc::Map::get): (bmalloc::Map::set): (bmalloc::Map::remove): (bmalloc::Map::shouldGrow): (bmalloc::Map::shouldShrink): (bmalloc::Map::find): (bmalloc::Hash>::rehash): Simple hash table. * bmalloc/Object.h: * bmalloc/ObjectType.cpp: (bmalloc::objectType): * bmalloc/ObjectType.h: (bmalloc::mightBeLarge): See deallocateSlowCase. (bmalloc::isXLarge): Deleted. * bmalloc/SegregatedFreeList.cpp: Removed. * bmalloc/SegregatedFreeList.h: Removed. * bmalloc/Sizes.h: Upped smallMax to 64kB. Upping to 32kB is pretty reasonable, since sizes between 16kB and 32kB share page sizes. I went all the way up to 64kB because the GC uses 64kB blocks, and also just for extra padding to ensure that large allocations are indeed rare. * bmalloc/SortedVector.h: Removed. * bmalloc/VMHeap.cpp: (bmalloc::VMHeap::tryAllocateLargeChunk): (bmalloc::VMHeap::allocateSmallChunk): (bmalloc::VMHeap::VMHeap): Deleted. (bmalloc::VMHeap::allocateChunk): Deleted. * bmalloc/VMHeap.h: (bmalloc::VMHeap::deallocateSmallPage): (bmalloc::VMHeap::allocateLargeObject): Deleted. (bmalloc::VMHeap::deallocateLargeObject): Deleted. Nixed all the boundary tag logic since metadata is out of line now. * bmalloc/VMState.h: Removed. Instead of an abstract state, we track the precise amount of committed physical pages at the head of a VM range. This allows us to merge aggressively without triggering an madvise storm most of the time. * bmalloc/Vector.h: (bmalloc::Vector<T>::Vector): (bmalloc::Vector<T>::insert): (bmalloc::Vector<T>::remove): (bmalloc::Vector<T>::resize): Filled out some missing helpers. * bmalloc/XLargeMap.cpp: (bmalloc::XLargeMap::remove): (bmalloc::XLargeMap::add): (bmalloc::XLargeMap::removePhysical): (bmalloc::XLargeMap::takeFree): Deleted. (bmalloc::XLargeMap::addFree): Deleted. (bmalloc::XLargeMap::addAllocated): Deleted. (bmalloc::XLargeMap::getAllocated): Deleted. (bmalloc::XLargeMap::takeAllocated): Deleted. (bmalloc::XLargeMap::shrinkToFit): Deleted. (bmalloc::XLargeMap::takePhysical): Deleted. (bmalloc::XLargeMap::addVirtual): Deleted. * bmalloc/XLargeMap.h: (bmalloc::XLargeMap::Allocation::operator<): Deleted. We don't track object sizes anymore -- just free space. (The Heap tracks object sizes.) We use plain old linear search for free space. (See intro.) * bmalloc/XLargeRange.h: (bmalloc::XLargeRange::physicalSize): (bmalloc::XLargeRange::setPhysicalSize): (bmalloc::merge): (bmalloc::XLargeRange::split): (bmalloc::XLargeRange::vmState): Deleted. (bmalloc::XLargeRange::setVMState): Deleted. See VMState.h. Canonical link: https://commits.webkit.org/174881@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@199746 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2016-04-19 23:36:20 +00:00
return ObjectType::Small;
bmalloc https://bugs.webkit.org/show_bug.cgi?id=131170 Reviewed by Andreas Kling. Initial commit. * bmalloc: Added. * bmalloc.xcodeproj: Added. * bmalloc.xcodeproj/project.pbxproj: Added. * bmalloc/Algorithm.h: Added. (bmalloc::max): (bmalloc::min): (bmalloc::mask): (bmalloc::test): (bmalloc::roundUpToMultipleOf): (bmalloc::roundDownToMultipleOf): (bmalloc::sizeOf): (bmalloc::bitCount): (bmalloc::isPowerOfTwo): * bmalloc/Allocator.cpp: Added. (bmalloc::Allocator::Allocator): (bmalloc::Allocator::~Allocator): (bmalloc::Allocator::log): (bmalloc::Allocator::processSmallAllocatorLog): (bmalloc::Allocator::processMediumAllocatorLog): (bmalloc::Allocator::allocateLarge): (bmalloc::Allocator::allocateXLarge): (bmalloc::Allocator::allocateMedium): (bmalloc::Allocator::allocateSlowCase): * bmalloc/Allocator.h: Added. (bmalloc::Allocator::smallAllocatorFor): (bmalloc::Allocator::allocateFastCase): (bmalloc::Allocator::allocate): * bmalloc/AsyncTask.cpp: Added. (bmalloc::AsyncTask<Function>::runSlowCase): (bmalloc::AsyncTask<Function>::pthreadEntryPoint): (bmalloc::AsyncTask<Function>::entryPoint): * bmalloc/AsyncTask.h: Added. (bmalloc::Function>::AsyncTask): (bmalloc::Function>::join): (bmalloc::Function>::run): (bmalloc::Function>::runSlowCase): (bmalloc::Function>::pthreadEntryPoint): (bmalloc::Function>::entryPoint): * bmalloc/BAssert.h: Added. * bmalloc/BeginTag.h: Added. (bmalloc::BeginTag::isInFreeList): * bmalloc/BoundaryTag.h: Added. (bmalloc::BoundaryTag::isXLarge): (bmalloc::BoundaryTag::setXLarge): (bmalloc::BoundaryTag::isFree): (bmalloc::BoundaryTag::setFree): (bmalloc::BoundaryTag::isEnd): (bmalloc::BoundaryTag::setEnd): (bmalloc::BoundaryTag::hasPhysicalPages): (bmalloc::BoundaryTag::setHasPhysicalPages): (bmalloc::BoundaryTag::isNull): (bmalloc::BoundaryTag::clear): (bmalloc::BoundaryTag::size): (bmalloc::BoundaryTag::setSize): (bmalloc::BoundaryTag::prev): (bmalloc::BoundaryTag::next): * bmalloc/BoundaryTagInlines.h: Added. (bmalloc::validate): (bmalloc::validatePrev): (bmalloc::validateNext): (bmalloc::BoundaryTag::init): (bmalloc::BoundaryTag::mergeLargeLeft): (bmalloc::BoundaryTag::mergeLargeRight): (bmalloc::BoundaryTag::mergeLarge): (bmalloc::BoundaryTag::deallocate): (bmalloc::BoundaryTag::splitLarge): (bmalloc::BoundaryTag::allocate): * bmalloc/Cache.cpp: Added. (bmalloc::Cache::operator new): (bmalloc::Cache::operator delete): (bmalloc::Cache::Cache): (bmalloc::Cache::allocateSlowCase): (bmalloc::Cache::allocateSlowCaseNullCache): (bmalloc::Cache::deallocateSlowCase): (bmalloc::Cache::deallocateSlowCaseNullCache): * bmalloc/Cache.h: Added. (bmalloc::Cache::allocator): (bmalloc::Cache::deallocator): (bmalloc::Cache::allocateFastCase): (bmalloc::Cache::deallocateFastCase): (bmalloc::Cache::allocate): (bmalloc::Cache::deallocate): * bmalloc/Chunk.h: Added. (bmalloc::Chunk::begin): (bmalloc::Chunk::end): (bmalloc::Chunk::lines): (bmalloc::Chunk::pages): * bmalloc/Deallocator.cpp: Added. (bmalloc::Deallocator::Deallocator): (bmalloc::Deallocator::~Deallocator): (bmalloc::Deallocator::deallocateLarge): (bmalloc::Deallocator::deallocateXLarge): (bmalloc::Deallocator::processObjectLog): (bmalloc::Deallocator::deallocateSlowCase): (bmalloc::Deallocator::deallocateSmallLine): (bmalloc::Deallocator::allocateSmallLine): (bmalloc::Deallocator::deallocateMediumLine): (bmalloc::Deallocator::allocateMediumLine): * bmalloc/Deallocator.h: Added. (bmalloc::Deallocator::deallocateFastCase): (bmalloc::Deallocator::deallocate): * bmalloc/EndTag.h: Added. (bmalloc::EndTag::operator=): * bmalloc/FixedVector.h: Added. (bmalloc::FixedVector::begin): (bmalloc::FixedVector::end): (bmalloc::FixedVector::size): (bmalloc::FixedVector::capacity): (bmalloc::FixedVector::clear): (bmalloc::FixedVector::isEmpty): (bmalloc::Capacity>::FixedVector): (bmalloc::Capacity>::operator): (bmalloc::Capacity>::push): (bmalloc::Capacity>::pop): (bmalloc::Capacity>::shrink): * bmalloc/Heap.cpp: Added. (bmalloc::sleep): (bmalloc::Heap::Heap): (bmalloc::Heap::concurrentScavenge): (bmalloc::Heap::scavengeSmallPages): (bmalloc::Heap::scavengeMediumPages): (bmalloc::Heap::scavengeLargeRanges): (bmalloc::Heap::allocateSmallLineSlowCase): (bmalloc::Heap::allocateMediumLineSlowCase): (bmalloc::Heap::allocateXLarge): (bmalloc::Heap::deallocateXLarge): (bmalloc::Heap::allocateLarge): (bmalloc::Heap::deallocateLarge): * bmalloc/Heap.h: Added. (bmalloc::Heap::deallocateSmallLine): (bmalloc::Heap::allocateSmallLine): (bmalloc::Heap::deallocateMediumLine): (bmalloc::Heap::allocateMediumLine): * bmalloc/Inline.h: Added. * bmalloc/LargeChunk.h: Added. (bmalloc::LargeChunk::begin): (bmalloc::LargeChunk::end): (bmalloc::LargeChunk::create): (bmalloc::LargeChunk::get): (bmalloc::LargeChunk::beginTag): (bmalloc::LargeChunk::endTag): * bmalloc/Line.h: Added. (bmalloc::Line<Traits>::begin): (bmalloc::Line<Traits>::end): (bmalloc::Line<Traits>::concurrentRef): (bmalloc::Line<Traits>::deref): * bmalloc/MediumAllocator.h: Added. (bmalloc::MediumAllocator::isNull): (bmalloc::MediumAllocator::MediumAllocator): (bmalloc::MediumAllocator::line): (bmalloc::MediumAllocator::allocate): (bmalloc::MediumAllocator::derefCount): (bmalloc::MediumAllocator::refill): * bmalloc/MediumChunk.h: Added. * bmalloc/MediumLine.h: Added. * bmalloc/MediumPage.h: Added. * bmalloc/MediumTraits.h: Added. * bmalloc/Mutex.cpp: Added. (bmalloc::Mutex::lockSlowCase): * bmalloc/Mutex.h: Added. (bmalloc::Mutex::Mutex): (bmalloc::Mutex::try_lock): (bmalloc::Mutex::lock): (bmalloc::Mutex::unlock): * bmalloc/ObjectType.cpp: Added. (bmalloc::objectType): * bmalloc/ObjectType.h: Added. (bmalloc::isSmallOrMedium): (bmalloc::isSmall): * bmalloc/Page.h: Added. (bmalloc::Page<Traits>::ref): (bmalloc::Page<Traits>::deref): (bmalloc::Page<Traits>::refCount): * bmalloc/PerProcess.h: Added. (bmalloc::PerProcess::mutex): (bmalloc::PerProcess<T>::getFastCase): (bmalloc::PerProcess<T>::get): (bmalloc::PerProcess<T>::getSlowCase): * bmalloc/PerThread.h: Added. (bmalloc::PerThreadStorage<Cache>::get): (bmalloc::PerThreadStorage<Cache>::init): (bmalloc::PerThreadStorage::get): (bmalloc::PerThreadStorage::init): (bmalloc::PerThread<T>::getFastCase): (bmalloc::PerThread<T>::get): (bmalloc::PerThread<T>::destructor): (bmalloc::PerThread<T>::getSlowCase): * bmalloc/Range.h: Added. (bmalloc::Range::Range): (bmalloc::Range::begin): (bmalloc::Range::end): (bmalloc::Range::size): (bmalloc::Range::operator!): (bmalloc::Range::operator<): * bmalloc/SegregatedFreeList.cpp: Added. (bmalloc::SegregatedFreeList::SegregatedFreeList): (bmalloc::SegregatedFreeList::insert): (bmalloc::SegregatedFreeList::takeGreedy): (bmalloc::SegregatedFreeList::take): * bmalloc/SegregatedFreeList.h: Added. * bmalloc/Sizes.h: Added. * bmalloc/SmallAllocator.h: Added. (bmalloc::SmallAllocator::isNull): (bmalloc::SmallAllocator::canAllocate): (bmalloc::SmallAllocator::SmallAllocator): (bmalloc::SmallAllocator::line): (bmalloc::SmallAllocator::allocate): (bmalloc::SmallAllocator::objectCount): (bmalloc::SmallAllocator::derefCount): (bmalloc::SmallAllocator::refill): * bmalloc/SmallChunk.h: Added. * bmalloc/SmallLine.h: Added. * bmalloc/SmallPage.h: Added. * bmalloc/SmallTraits.h: Added. * bmalloc/Syscall.h: Added. * bmalloc/VMAllocate.h: Added. (bmalloc::vmSize): (bmalloc::vmValidate): (bmalloc::vmAllocate): (bmalloc::vmDeallocate): (bmalloc::vmDeallocatePhysicalPages): (bmalloc::vmAllocatePhysicalPages): (bmalloc::vmDeallocatePhysicalPagesSloppy): (bmalloc::vmAllocatePhysicalPagesSloppy): * bmalloc/VMHeap.cpp: Added. (bmalloc::VMHeap::VMHeap): (bmalloc::VMHeap::allocateSmallChunk): (bmalloc::VMHeap::allocateMediumChunk): (bmalloc::VMHeap::allocateLargeChunk): * bmalloc/VMHeap.h: Added. (bmalloc::VMHeap::allocateSmallPage): (bmalloc::VMHeap::allocateMediumPage): (bmalloc::VMHeap::allocateLargeRange): (bmalloc::VMHeap::deallocateSmallPage): (bmalloc::VMHeap::deallocateMediumPage): (bmalloc::VMHeap::deallocateLargeRange): * bmalloc/Vector.h: Added. (bmalloc::Vector::begin): (bmalloc::Vector::end): (bmalloc::Vector::size): (bmalloc::Vector::capacity): (bmalloc::Vector::last): (bmalloc::Vector::pop): (bmalloc::Vector<T>::Vector): (bmalloc::Vector<T>::~Vector): (bmalloc::Vector<T>::operator): (bmalloc::Vector<T>::push): (bmalloc::Vector<T>::pop): (bmalloc::Vector<T>::shrink): (bmalloc::Vector<T>::reallocateBuffer): (bmalloc::Vector<T>::shrinkCapacity): (bmalloc::Vector<T>::growCapacity): * bmalloc/XLargeChunk.h: Added. (bmalloc::XLargeChunk::get): (bmalloc::XLargeChunk::begin): (bmalloc::XLargeChunk::XLargeChunk): (bmalloc::XLargeChunk::create): (bmalloc::XLargeChunk::destroy): (bmalloc::XLargeChunk::range): (bmalloc::XLargeChunk::size): * bmalloc/bmalloc.h: Added. (bmalloc::api::malloc): (bmalloc::api::free): (bmalloc::api::realloc): * bmalloc/mbmalloc.cpp: Added. Canonical link: https://commits.webkit.org/149378@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@166893 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2014-04-07 23:54:11 +00:00
}
} // namespace bmalloc