bmalloc
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 7 Apr 2014 23:54:11 +0000 (23:54 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 7 Apr 2014 23:54:11 +0000 (23:54 +0000)
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.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@166893 268f45cc-cd09-0410-ab3c-d52691b4dbfc

52 files changed:
Source/bmalloc/ChangeLog [new file with mode: 0644]
Source/bmalloc/bmalloc.xcodeproj/project.pbxproj [new file with mode: 0644]
Source/bmalloc/bmalloc/Algorithm.h [new file with mode: 0644]
Source/bmalloc/bmalloc/Allocator.cpp [new file with mode: 0644]
Source/bmalloc/bmalloc/Allocator.h [new file with mode: 0644]
Source/bmalloc/bmalloc/AsyncTask.cpp [new file with mode: 0644]
Source/bmalloc/bmalloc/AsyncTask.h [new file with mode: 0644]
Source/bmalloc/bmalloc/BAssert.h [new file with mode: 0644]
Source/bmalloc/bmalloc/BeginTag.h [new file with mode: 0644]
Source/bmalloc/bmalloc/BoundaryTag.h [new file with mode: 0644]
Source/bmalloc/bmalloc/BoundaryTagInlines.h [new file with mode: 0644]
Source/bmalloc/bmalloc/Cache.cpp [new file with mode: 0644]
Source/bmalloc/bmalloc/Cache.h [new file with mode: 0644]
Source/bmalloc/bmalloc/Chunk.h [new file with mode: 0644]
Source/bmalloc/bmalloc/Deallocator.cpp [new file with mode: 0644]
Source/bmalloc/bmalloc/Deallocator.h [new file with mode: 0644]
Source/bmalloc/bmalloc/EndTag.h [new file with mode: 0644]
Source/bmalloc/bmalloc/FixedVector.h [new file with mode: 0644]
Source/bmalloc/bmalloc/Heap.cpp [new file with mode: 0644]
Source/bmalloc/bmalloc/Heap.h [new file with mode: 0644]
Source/bmalloc/bmalloc/Inline.h [new file with mode: 0644]
Source/bmalloc/bmalloc/LargeChunk.h [new file with mode: 0644]
Source/bmalloc/bmalloc/Line.h [new file with mode: 0644]
Source/bmalloc/bmalloc/MediumAllocator.h [new file with mode: 0644]
Source/bmalloc/bmalloc/MediumChunk.h [new file with mode: 0644]
Source/bmalloc/bmalloc/MediumLine.h [new file with mode: 0644]
Source/bmalloc/bmalloc/MediumPage.h [new file with mode: 0644]
Source/bmalloc/bmalloc/MediumTraits.h [new file with mode: 0644]
Source/bmalloc/bmalloc/Mutex.cpp [new file with mode: 0644]
Source/bmalloc/bmalloc/Mutex.h [new file with mode: 0644]
Source/bmalloc/bmalloc/ObjectType.cpp [new file with mode: 0644]
Source/bmalloc/bmalloc/ObjectType.h [new file with mode: 0644]
Source/bmalloc/bmalloc/Page.h [new file with mode: 0644]
Source/bmalloc/bmalloc/PerProcess.h [new file with mode: 0644]
Source/bmalloc/bmalloc/PerThread.h [new file with mode: 0644]
Source/bmalloc/bmalloc/Range.h [new file with mode: 0644]
Source/bmalloc/bmalloc/SegregatedFreeList.cpp [new file with mode: 0644]
Source/bmalloc/bmalloc/SegregatedFreeList.h [new file with mode: 0644]
Source/bmalloc/bmalloc/Sizes.h [new file with mode: 0644]
Source/bmalloc/bmalloc/SmallAllocator.h [new file with mode: 0644]
Source/bmalloc/bmalloc/SmallChunk.h [new file with mode: 0644]
Source/bmalloc/bmalloc/SmallLine.h [new file with mode: 0644]
Source/bmalloc/bmalloc/SmallPage.h [new file with mode: 0644]
Source/bmalloc/bmalloc/SmallTraits.h [new file with mode: 0644]
Source/bmalloc/bmalloc/Syscall.h [new file with mode: 0644]
Source/bmalloc/bmalloc/VMAllocate.h [new file with mode: 0644]
Source/bmalloc/bmalloc/VMHeap.cpp [new file with mode: 0644]
Source/bmalloc/bmalloc/VMHeap.h [new file with mode: 0644]
Source/bmalloc/bmalloc/Vector.h [new file with mode: 0644]
Source/bmalloc/bmalloc/XLargeChunk.h [new file with mode: 0644]
Source/bmalloc/bmalloc/bmalloc.h [new file with mode: 0644]
Source/bmalloc/bmalloc/mbmalloc.cpp [new file with mode: 0644]

diff --git a/Source/bmalloc/ChangeLog b/Source/bmalloc/ChangeLog
new file mode 100644 (file)
index 0000000..a758227
--- /dev/null
@@ -0,0 +1,275 @@
+2014-04-07  Geoffrey Garen  <ggaren@apple.com>
+
+        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.
+
diff --git a/Source/bmalloc/bmalloc.xcodeproj/project.pbxproj b/Source/bmalloc/bmalloc.xcodeproj/project.pbxproj
new file mode 100644 (file)
index 0000000..3e537be
--- /dev/null
@@ -0,0 +1,498 @@
+// !$*UTF8*$!
+{
+       archiveVersion = 1;
+       classes = {
+       };
+       objectVersion = 46;
+       objects = {
+
+/* Begin PBXBuildFile section */
+               14CC390518EA627D004AFE34 /* bmalloc.h in Headers */ = {isa = PBXBuildFile; fileRef = 14CC390418EA627D004AFE34 /* bmalloc.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               14CC394C18EA8858004AFE34 /* libbmalloc.a in Frameworks */ = {isa = PBXBuildFile; fileRef = 14F271BE18EA3963008C152F /* libbmalloc.a */; };
+               14D2868918EB759A0012420E /* mbmalloc.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14D2868818EB759A0012420E /* mbmalloc.cpp */; };
+               14F271C318EA3978008C152F /* Allocator.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 145F6855179DC8CA00D65598 /* Allocator.cpp */; };
+               14F271C418EA397B008C152F /* Cache.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 144469E417A46BFE00F9EA1D /* Cache.cpp */; };
+               14F271C518EA397E008C152F /* Deallocator.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 145F6859179DC90200D65598 /* Deallocator.cpp */; };
+               14F271C618EA3983008C152F /* SegregatedFreeList.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 146BEE2118C845AE0002D5A2 /* SegregatedFreeList.cpp */; };
+               14F271C718EA3990008C152F /* Heap.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14DA320E18875D9F007269E0 /* Heap.cpp */; };
+               14F271C818EA3990008C152F /* ObjectType.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14105E8318E14374003A106E /* ObjectType.cpp */; };
+               14F271C918EA3990008C152F /* VMHeap.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 144F7BFB18BFC517003537F3 /* VMHeap.cpp */; };
+               14F271CA18EA3990008C152F /* Mutex.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 144DCED817A728570093B2F2 /* Mutex.cpp */; };
+/* End PBXBuildFile section */
+
+/* Begin PBXContainerItemProxy section */
+               14CC394D18EA8861004AFE34 /* PBXContainerItemProxy */ = {
+                       isa = PBXContainerItemProxy;
+                       containerPortal = 145F6837179DC45F00D65598 /* Project object */;
+                       proxyType = 1;
+                       remoteGlobalIDString = 14F271BD18EA3963008C152F;
+                       remoteInfo = bmalloc;
+               };
+/* End PBXContainerItemProxy section */
+
+/* Begin PBXFileReference section */
+               14105E7B18DBD7AF003A106E /* BoundaryTagInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = BoundaryTagInlines.h; path = bmalloc/BoundaryTagInlines.h; sourceTree = "<group>"; };
+               14105E8318E14374003A106E /* ObjectType.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = ObjectType.cpp; path = bmalloc/ObjectType.cpp; sourceTree = "<group>"; };
+               1413E460189DCE1E00546D68 /* Inline.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Inline.h; path = bmalloc/Inline.h; sourceTree = "<group>"; };
+               1413E462189DE1CD00546D68 /* SmallAllocator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; lineEnding = 0; name = SmallAllocator.h; path = bmalloc/SmallAllocator.h; sourceTree = "<group>"; };
+               1413E468189EEDE400546D68 /* BAssert.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = BAssert.h; path = bmalloc/BAssert.h; sourceTree = "<group>"; };
+               1413E47018A0661700546D68 /* MediumAllocator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = MediumAllocator.h; path = bmalloc/MediumAllocator.h; sourceTree = "<group>"; };
+               1417F64518B54A700076FA3F /* BeginTag.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = BeginTag.h; path = bmalloc/BeginTag.h; sourceTree = "<group>"; };
+               1417F64618B54A700076FA3F /* EndTag.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = EndTag.h; path = bmalloc/EndTag.h; sourceTree = "<group>"; };
+               1417F64F18B7280C0076FA3F /* Syscall.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Syscall.h; path = bmalloc/Syscall.h; sourceTree = "<group>"; };
+               1417F65218BA88A00076FA3F /* AsyncTask.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AsyncTask.h; path = bmalloc/AsyncTask.h; sourceTree = "<group>"; };
+               1421A87718EE462A00B4DD68 /* Algorithm.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; name = Algorithm.h; path = bmalloc/Algorithm.h; sourceTree = "<group>"; };
+               143E29E918CAE8BE00FE8A0F /* MediumPage.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = MediumPage.h; path = bmalloc/MediumPage.h; sourceTree = "<group>"; };
+               143E29ED18CAE90500FE8A0F /* SmallPage.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = SmallPage.h; path = bmalloc/SmallPage.h; sourceTree = "<group>"; };
+               144469E417A46BFE00F9EA1D /* Cache.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; lineEnding = 0; name = Cache.cpp; path = bmalloc/Cache.cpp; sourceTree = "<group>"; xcLanguageSpecificationIdentifier = xcode.lang.cpp; };
+               144469E517A46BFE00F9EA1D /* Cache.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; lineEnding = 0; name = Cache.h; path = bmalloc/Cache.h; sourceTree = "<group>"; xcLanguageSpecificationIdentifier = xcode.lang.objcpp; };
+               144469FD17A61F1F00F9EA1D /* PerThread.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; lineEnding = 0; name = PerThread.h; path = bmalloc/PerThread.h; sourceTree = "<group>"; xcLanguageSpecificationIdentifier = xcode.lang.objcpp; };
+               14446A0717A61FA400F9EA1D /* PerProcess.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = PerProcess.h; path = bmalloc/PerProcess.h; sourceTree = "<group>"; };
+               144DCED617A649D90093B2F2 /* Mutex.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Mutex.h; path = bmalloc/Mutex.h; sourceTree = "<group>"; };
+               144DCED817A728570093B2F2 /* Mutex.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = Mutex.cpp; path = bmalloc/Mutex.cpp; sourceTree = "<group>"; };
+               144F7BFB18BFC517003537F3 /* VMHeap.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = VMHeap.cpp; path = bmalloc/VMHeap.cpp; sourceTree = "<group>"; };
+               144F7BFC18BFC517003537F3 /* VMHeap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = VMHeap.h; path = bmalloc/VMHeap.h; sourceTree = "<group>"; };
+               1452478518BC757C00F80098 /* MediumLine.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = MediumLine.h; path = bmalloc/MediumLine.h; sourceTree = "<group>"; };
+               1452478618BC757C00F80098 /* SmallLine.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = SmallLine.h; path = bmalloc/SmallLine.h; sourceTree = "<group>"; };
+               145F6855179DC8CA00D65598 /* Allocator.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; lineEnding = 0; name = Allocator.cpp; path = bmalloc/Allocator.cpp; sourceTree = "<group>"; xcLanguageSpecificationIdentifier = xcode.lang.cpp; };
+               145F6856179DC8CA00D65598 /* Allocator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; lineEnding = 0; name = Allocator.h; path = bmalloc/Allocator.h; sourceTree = "<group>"; xcLanguageSpecificationIdentifier = xcode.lang.objcpp; };
+               145F6859179DC90200D65598 /* Deallocator.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; lineEnding = 0; name = Deallocator.cpp; path = bmalloc/Deallocator.cpp; sourceTree = "<group>"; xcLanguageSpecificationIdentifier = xcode.lang.cpp; };
+               145F685A179DC90200D65598 /* Deallocator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; lineEnding = 0; name = Deallocator.h; path = bmalloc/Deallocator.h; sourceTree = "<group>"; xcLanguageSpecificationIdentifier = xcode.lang.objcpp; };
+               145F6874179DF84100D65598 /* Sizes.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Sizes.h; path = bmalloc/Sizes.h; sourceTree = "<group>"; };
+               145F6878179E3A4400D65598 /* Range.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; lineEnding = 0; name = Range.h; path = bmalloc/Range.h; sourceTree = "<group>"; xcLanguageSpecificationIdentifier = xcode.lang.objcpp; };
+               146BEE1E18C841C50002D5A2 /* SegregatedFreeList.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = SegregatedFreeList.h; path = bmalloc/SegregatedFreeList.h; sourceTree = "<group>"; };
+               146BEE2118C845AE0002D5A2 /* SegregatedFreeList.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = SegregatedFreeList.cpp; path = bmalloc/SegregatedFreeList.cpp; sourceTree = "<group>"; };
+               146BEE2318C980D60002D5A2 /* Page.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Page.h; path = bmalloc/Page.h; sourceTree = "<group>"; };
+               1479E21217A1A255006D4E9D /* Vector.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; lineEnding = 0; name = Vector.h; path = bmalloc/Vector.h; sourceTree = "<group>"; xcLanguageSpecificationIdentifier = xcode.lang.objcpp; };
+               1479E21417A1A63E006D4E9D /* VMAllocate.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; lineEnding = 0; name = VMAllocate.h; path = bmalloc/VMAllocate.h; sourceTree = "<group>"; xcLanguageSpecificationIdentifier = xcode.lang.objcpp; };
+               147AAA8818CD17CE002201E4 /* LargeChunk.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = LargeChunk.h; path = bmalloc/LargeChunk.h; sourceTree = "<group>"; };
+               147AAA8918CD17CE002201E4 /* XLargeChunk.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = XLargeChunk.h; path = bmalloc/XLargeChunk.h; sourceTree = "<group>"; };
+               147AAA8C18CD36A7002201E4 /* SmallChunk.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = SmallChunk.h; path = bmalloc/SmallChunk.h; sourceTree = "<group>"; };
+               147AAA8E18CD89E3002201E4 /* MediumChunk.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = MediumChunk.h; path = bmalloc/MediumChunk.h; sourceTree = "<group>"; };
+               147AAA9418CE5CA6002201E4 /* Chunk.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Chunk.h; path = bmalloc/Chunk.h; sourceTree = "<group>"; };
+               147AAA9618CE5FB6002201E4 /* MediumTraits.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = MediumTraits.h; path = bmalloc/MediumTraits.h; sourceTree = "<group>"; };
+               147AAA9718CE5FB6002201E4 /* SmallTraits.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = SmallTraits.h; path = bmalloc/SmallTraits.h; sourceTree = "<group>"; };
+               1485655E18A43AF900ED6942 /* BoundaryTag.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = BoundaryTag.h; path = bmalloc/BoundaryTag.h; sourceTree = "<group>"; };
+               1485656018A43DBA00ED6942 /* ObjectType.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = ObjectType.h; path = bmalloc/ObjectType.h; sourceTree = "<group>"; };
+               14CC390418EA627D004AFE34 /* bmalloc.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = bmalloc.h; path = bmalloc/bmalloc.h; sourceTree = SOURCE_ROOT; };
+               14CC394418EA8743004AFE34 /* libmbmalloc.dylib */ = {isa = PBXFileReference; explicitFileType = "compiled.mach-o.dylib"; includeInIndex = 0; path = libmbmalloc.dylib; sourceTree = BUILT_PRODUCTS_DIR; };
+               14D2868818EB759A0012420E /* mbmalloc.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = mbmalloc.cpp; path = bmalloc/mbmalloc.cpp; sourceTree = SOURCE_ROOT; };
+               14D9DB4517F2447100EAAB79 /* FixedVector.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; lineEnding = 0; name = FixedVector.h; path = bmalloc/FixedVector.h; sourceTree = "<group>"; xcLanguageSpecificationIdentifier = xcode.lang.objcpp; };
+               14DA32071885F9E6007269E0 /* Line.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; lineEnding = 0; name = Line.h; path = bmalloc/Line.h; sourceTree = "<group>"; xcLanguageSpecificationIdentifier = xcode.lang.objcpp; };
+               14DA320C18875B09007269E0 /* Heap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Heap.h; path = bmalloc/Heap.h; sourceTree = "<group>"; };
+               14DA320E18875D9F007269E0 /* Heap.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = Heap.cpp; path = bmalloc/Heap.cpp; sourceTree = "<group>"; };
+               14F271BE18EA3963008C152F /* libbmalloc.a */ = {isa = PBXFileReference; explicitFileType = archive.ar; includeInIndex = 0; path = libbmalloc.a; sourceTree = BUILT_PRODUCTS_DIR; };
+/* End PBXFileReference section */
+
+/* Begin PBXFrameworksBuildPhase section */
+               14CC394118EA8743004AFE34 /* Frameworks */ = {
+                       isa = PBXFrameworksBuildPhase;
+                       buildActionMask = 2147483647;
+                       files = (
+                               14CC394C18EA8858004AFE34 /* libbmalloc.a in Frameworks */,
+                       );
+                       runOnlyForDeploymentPostprocessing = 0;
+               };
+               14F271BB18EA3963008C152F /* Frameworks */ = {
+                       isa = PBXFrameworksBuildPhase;
+                       buildActionMask = 2147483647;
+                       files = (
+                       );
+                       runOnlyForDeploymentPostprocessing = 0;
+               };
+/* End PBXFrameworksBuildPhase section */
+
+/* Begin PBXGroup section */
+               145F6836179DC45F00D65598 = {
+                       isa = PBXGroup;
+                       children = (
+                               14F271B718EA285B008C152F /* api */,
+                               14D9DB4D17F2865C00EAAB79 /* cache */,
+                               147AAA9C18CE6010002201E4 /* heap: large | xlarge */,
+                               147AAA9A18CE5FD3002201E4 /* heap: small | medium */,
+                               14D9DB4E17F2866E00EAAB79 /* heap */,
+                               14D9DB4F17F2868900EAAB79 /* stdlib */,
+                               145F6840179DC45F00D65598 /* Products */,
+                       );
+                       sourceTree = "<group>";
+               };
+               145F6840179DC45F00D65598 /* Products */ = {
+                       isa = PBXGroup;
+                       children = (
+                               14F271BE18EA3963008C152F /* libbmalloc.a */,
+                               14CC394418EA8743004AFE34 /* libmbmalloc.dylib */,
+                       );
+                       name = Products;
+                       sourceTree = "<group>";
+               };
+               147AAA9A18CE5FD3002201E4 /* heap: small | medium */ = {
+                       isa = PBXGroup;
+                       children = (
+                               147AAA9418CE5CA6002201E4 /* Chunk.h */,
+                               14DA32071885F9E6007269E0 /* Line.h */,
+                               147AAA8E18CD89E3002201E4 /* MediumChunk.h */,
+                               1452478518BC757C00F80098 /* MediumLine.h */,
+                               143E29E918CAE8BE00FE8A0F /* MediumPage.h */,
+                               147AAA9618CE5FB6002201E4 /* MediumTraits.h */,
+                               146BEE2318C980D60002D5A2 /* Page.h */,
+                               147AAA8C18CD36A7002201E4 /* SmallChunk.h */,
+                               1452478618BC757C00F80098 /* SmallLine.h */,
+                               143E29ED18CAE90500FE8A0F /* SmallPage.h */,
+                               147AAA9718CE5FB6002201E4 /* SmallTraits.h */,
+                       );
+                       name = "heap: small | medium";
+                       sourceTree = "<group>";
+               };
+               147AAA9C18CE6010002201E4 /* heap: large | xlarge */ = {
+                       isa = PBXGroup;
+                       children = (
+                               1417F64518B54A700076FA3F /* BeginTag.h */,
+                               1485655E18A43AF900ED6942 /* BoundaryTag.h */,
+                               14105E7B18DBD7AF003A106E /* BoundaryTagInlines.h */,
+                               1417F64618B54A700076FA3F /* EndTag.h */,
+                               147AAA8818CD17CE002201E4 /* LargeChunk.h */,
+                               146BEE2118C845AE0002D5A2 /* SegregatedFreeList.cpp */,
+                               146BEE1E18C841C50002D5A2 /* SegregatedFreeList.h */,
+                               147AAA8918CD17CE002201E4 /* XLargeChunk.h */,
+                       );
+                       name = "heap: large | xlarge";
+                       sourceTree = "<group>";
+               };
+               14D9DB4D17F2865C00EAAB79 /* cache */ = {
+                       isa = PBXGroup;
+                       children = (
+                               145F6855179DC8CA00D65598 /* Allocator.cpp */,
+                               145F6856179DC8CA00D65598 /* Allocator.h */,
+                               144469E417A46BFE00F9EA1D /* Cache.cpp */,
+                               144469E517A46BFE00F9EA1D /* Cache.h */,
+                               145F6859179DC90200D65598 /* Deallocator.cpp */,
+                               145F685A179DC90200D65598 /* Deallocator.h */,
+                               1413E47018A0661700546D68 /* MediumAllocator.h */,
+                               1413E462189DE1CD00546D68 /* SmallAllocator.h */,
+                       );
+                       name = cache;
+                       sourceTree = "<group>";
+               };
+               14D9DB4E17F2866E00EAAB79 /* heap */ = {
+                       isa = PBXGroup;
+                       children = (
+                               14DA320E18875D9F007269E0 /* Heap.cpp */,
+                               14DA320C18875B09007269E0 /* Heap.h */,
+                               14105E8318E14374003A106E /* ObjectType.cpp */,
+                               1485656018A43DBA00ED6942 /* ObjectType.h */,
+                               145F6874179DF84100D65598 /* Sizes.h */,
+                               144F7BFB18BFC517003537F3 /* VMHeap.cpp */,
+                               144F7BFC18BFC517003537F3 /* VMHeap.h */,
+                       );
+                       name = heap;
+                       sourceTree = "<group>";
+               };
+               14D9DB4F17F2868900EAAB79 /* stdlib */ = {
+                       isa = PBXGroup;
+                       children = (
+                               1421A87718EE462A00B4DD68 /* Algorithm.h */,
+                               1417F65218BA88A00076FA3F /* AsyncTask.h */,
+                               1413E468189EEDE400546D68 /* BAssert.h */,
+                               14D9DB4517F2447100EAAB79 /* FixedVector.h */,
+                               1413E460189DCE1E00546D68 /* Inline.h */,
+                               144DCED817A728570093B2F2 /* Mutex.cpp */,
+                               144DCED617A649D90093B2F2 /* Mutex.h */,
+                               14446A0717A61FA400F9EA1D /* PerProcess.h */,
+                               144469FD17A61F1F00F9EA1D /* PerThread.h */,
+                               145F6878179E3A4400D65598 /* Range.h */,
+                               1417F64F18B7280C0076FA3F /* Syscall.h */,
+                               1479E21217A1A255006D4E9D /* Vector.h */,
+                               1479E21417A1A63E006D4E9D /* VMAllocate.h */,
+                       );
+                       name = stdlib;
+                       sourceTree = "<group>";
+               };
+               14F271B718EA285B008C152F /* api */ = {
+                       isa = PBXGroup;
+                       children = (
+                               14CC390418EA627D004AFE34 /* bmalloc.h */,
+                               14D2868818EB759A0012420E /* mbmalloc.cpp */,
+                       );
+                       name = api;
+                       path = imalloc;
+                       sourceTree = "<group>";
+               };
+/* End PBXGroup section */
+
+/* Begin PBXHeadersBuildPhase section */
+               14CC394218EA8743004AFE34 /* Headers */ = {
+                       isa = PBXHeadersBuildPhase;
+                       buildActionMask = 2147483647;
+                       files = (
+                       );
+                       runOnlyForDeploymentPostprocessing = 0;
+               };
+               14F271BC18EA3963008C152F /* Headers */ = {
+                       isa = PBXHeadersBuildPhase;
+                       buildActionMask = 2147483647;
+                       files = (
+                               14CC390518EA627D004AFE34 /* bmalloc.h in Headers */,
+                       );
+                       runOnlyForDeploymentPostprocessing = 0;
+               };
+/* End PBXHeadersBuildPhase section */
+
+/* Begin PBXNativeTarget section */
+               14CC394318EA8743004AFE34 /* mbmalloc */ = {
+                       isa = PBXNativeTarget;
+                       buildConfigurationList = 14CC394518EA8743004AFE34 /* Build configuration list for PBXNativeTarget "mbmalloc" */;
+                       buildPhases = (
+                               14CC394018EA8743004AFE34 /* Sources */,
+                               14CC394118EA8743004AFE34 /* Frameworks */,
+                               14CC394218EA8743004AFE34 /* Headers */,
+                       );
+                       buildRules = (
+                       );
+                       dependencies = (
+                               14CC394E18EA8861004AFE34 /* PBXTargetDependency */,
+                       );
+                       name = mbmalloc;
+                       productName = mbmalloc;
+                       productReference = 14CC394418EA8743004AFE34 /* libmbmalloc.dylib */;
+                       productType = "com.apple.product-type.library.dynamic";
+               };
+               14F271BD18EA3963008C152F /* bmalloc */ = {
+                       isa = PBXNativeTarget;
+                       buildConfigurationList = 14F271BF18EA3963008C152F /* Build configuration list for PBXNativeTarget "bmalloc" */;
+                       buildPhases = (
+                               14F271BA18EA3963008C152F /* Sources */,
+                               14F271BB18EA3963008C152F /* Frameworks */,
+                               14F271BC18EA3963008C152F /* Headers */,
+                       );
+                       buildRules = (
+                       );
+                       dependencies = (
+                       );
+                       name = bmalloc;
+                       productName = bmalloc;
+                       productReference = 14F271BE18EA3963008C152F /* libbmalloc.a */;
+                       productType = "com.apple.product-type.library.static";
+               };
+/* End PBXNativeTarget section */
+
+/* Begin PBXProject section */
+               145F6837179DC45F00D65598 /* Project object */ = {
+                       isa = PBXProject;
+                       attributes = {
+                               LastUpgradeCheck = 0600;
+                               ORGANIZATIONNAME = "Geoffrey Garen";
+                       };
+                       buildConfigurationList = 145F683A179DC45F00D65598 /* Build configuration list for PBXProject "bmalloc" */;
+                       compatibilityVersion = "Xcode 3.2";
+                       developmentRegion = English;
+                       hasScannedForEncodings = 0;
+                       knownRegions = (
+                               en,
+                       );
+                       mainGroup = 145F6836179DC45F00D65598;
+                       productRefGroup = 145F6840179DC45F00D65598 /* Products */;
+                       projectDirPath = "";
+                       projectRoot = "";
+                       targets = (
+                               14F271BD18EA3963008C152F /* bmalloc */,
+                               14CC394318EA8743004AFE34 /* mbmalloc */,
+                       );
+               };
+/* End PBXProject section */
+
+/* Begin PBXSourcesBuildPhase section */
+               14CC394018EA8743004AFE34 /* Sources */ = {
+                       isa = PBXSourcesBuildPhase;
+                       buildActionMask = 2147483647;
+                       files = (
+                               14D2868918EB759A0012420E /* mbmalloc.cpp in Sources */,
+                       );
+                       runOnlyForDeploymentPostprocessing = 0;
+               };
+               14F271BA18EA3963008C152F /* Sources */ = {
+                       isa = PBXSourcesBuildPhase;
+                       buildActionMask = 2147483647;
+                       files = (
+                               14F271CA18EA3990008C152F /* Mutex.cpp in Sources */,
+                               14F271C618EA3983008C152F /* SegregatedFreeList.cpp in Sources */,
+                               14F271C318EA3978008C152F /* Allocator.cpp in Sources */,
+                               14F271C718EA3990008C152F /* Heap.cpp in Sources */,
+                               14F271C918EA3990008C152F /* VMHeap.cpp in Sources */,
+                               14F271C818EA3990008C152F /* ObjectType.cpp in Sources */,
+                               14F271C518EA397E008C152F /* Deallocator.cpp in Sources */,
+                               14F271C418EA397B008C152F /* Cache.cpp in Sources */,
+                       );
+                       runOnlyForDeploymentPostprocessing = 0;
+               };
+/* End PBXSourcesBuildPhase section */
+
+/* Begin PBXTargetDependency section */
+               14CC394E18EA8861004AFE34 /* PBXTargetDependency */ = {
+                       isa = PBXTargetDependency;
+                       target = 14F271BD18EA3963008C152F /* bmalloc */;
+                       targetProxy = 14CC394D18EA8861004AFE34 /* PBXContainerItemProxy */;
+               };
+/* End PBXTargetDependency section */
+
+/* Begin XCBuildConfiguration section */
+               145F684A179DC45F00D65598 /* Debug */ = {
+                       isa = XCBuildConfiguration;
+                       buildSettings = {
+                               ALWAYS_SEARCH_USER_PATHS = NO;
+                               CLANG_CXX_LANGUAGE_STANDARD = "gnu++0x";
+                               CLANG_CXX_LIBRARY = "libc++";
+                               CLANG_ENABLE_MODULES = YES;
+                               CLANG_ENABLE_OBJC_ARC = YES;
+                               CLANG_WARN_BOOL_CONVERSION = YES;
+                               CLANG_WARN_CONSTANT_CONVERSION = YES;
+                               CLANG_WARN_DIRECT_OBJC_ISA_USAGE = YES_ERROR;
+                               CLANG_WARN_EMPTY_BODY = YES;
+                               CLANG_WARN_ENUM_CONVERSION = YES;
+                               CLANG_WARN_INT_CONVERSION = YES;
+                               CLANG_WARN_OBJC_ROOT_CLASS = YES_ERROR;
+                               CLANG_WARN__DUPLICATE_METHOD_MATCH = YES;
+                               COPY_PHASE_STRIP = NO;
+                               GCC_C_LANGUAGE_STANDARD = gnu99;
+                               GCC_DYNAMIC_NO_PIC = NO;
+                               GCC_ENABLE_CPP_EXCEPTIONS = NO;
+                               GCC_ENABLE_CPP_RTTI = NO;
+                               GCC_ENABLE_OBJC_EXCEPTIONS = YES;
+                               GCC_OPTIMIZATION_LEVEL = 0;
+                               GCC_PREPROCESSOR_DEFINITIONS = (
+                                       "DEBUG=1",
+                                       "$(inherited)",
+                               );
+                               GCC_SYMBOLS_PRIVATE_EXTERN = NO;
+                               GCC_WARN_64_TO_32_BIT_CONVERSION = YES;
+                               GCC_WARN_ABOUT_RETURN_TYPE = YES_ERROR;
+                               GCC_WARN_UNDECLARED_SELECTOR = YES;
+                               GCC_WARN_UNINITIALIZED_AUTOS = YES;
+                               GCC_WARN_UNUSED_FUNCTION = YES;
+                               GCC_WARN_UNUSED_VARIABLE = YES;
+                               MACOSX_DEPLOYMENT_TARGET = 10.9;
+                               ONLY_ACTIVE_ARCH = YES;
+                               SDKROOT = macosx;
+                       };
+                       name = Debug;
+               };
+               145F684B179DC45F00D65598 /* Release */ = {
+                       isa = XCBuildConfiguration;
+                       buildSettings = {
+                               ALWAYS_SEARCH_USER_PATHS = NO;
+                               CLANG_CXX_LANGUAGE_STANDARD = "gnu++0x";
+                               CLANG_CXX_LIBRARY = "libc++";
+                               CLANG_ENABLE_MODULES = YES;
+                               CLANG_ENABLE_OBJC_ARC = YES;
+                               CLANG_WARN_BOOL_CONVERSION = YES;
+                               CLANG_WARN_CONSTANT_CONVERSION = YES;
+                               CLANG_WARN_DIRECT_OBJC_ISA_USAGE = YES_ERROR;
+                               CLANG_WARN_EMPTY_BODY = YES;
+                               CLANG_WARN_ENUM_CONVERSION = YES;
+                               CLANG_WARN_INT_CONVERSION = YES;
+                               CLANG_WARN_OBJC_ROOT_CLASS = YES_ERROR;
+                               CLANG_WARN__DUPLICATE_METHOD_MATCH = YES;
+                               COPY_PHASE_STRIP = YES;
+                               DEBUG_INFORMATION_FORMAT = "dwarf-with-dsym";
+                               ENABLE_NS_ASSERTIONS = NO;
+                               GCC_C_LANGUAGE_STANDARD = gnu99;
+                               GCC_ENABLE_CPP_EXCEPTIONS = NO;
+                               GCC_ENABLE_CPP_RTTI = NO;
+                               GCC_ENABLE_OBJC_EXCEPTIONS = YES;
+                               GCC_WARN_64_TO_32_BIT_CONVERSION = YES;
+                               GCC_WARN_ABOUT_RETURN_TYPE = YES_ERROR;
+                               GCC_WARN_UNDECLARED_SELECTOR = YES;
+                               GCC_WARN_UNINITIALIZED_AUTOS = YES;
+                               GCC_WARN_UNUSED_FUNCTION = YES;
+                               GCC_WARN_UNUSED_VARIABLE = YES;
+                               MACOSX_DEPLOYMENT_TARGET = 10.9;
+                               SDKROOT = macosx;
+                       };
+                       name = Release;
+               };
+               14CC394618EA8743004AFE34 /* Debug */ = {
+                       isa = XCBuildConfiguration;
+                       buildSettings = {
+                               COMBINE_HIDPI_IMAGES = YES;
+                               EXECUTABLE_PREFIX = lib;
+                               GCC_WARN_UNINITIALIZED_AUTOS = YES_AGGRESSIVE;
+                               PRODUCT_NAME = "$(TARGET_NAME)";
+                               SDKROOT = macosx.internal;
+                       };
+                       name = Debug;
+               };
+               14CC394718EA8743004AFE34 /* Release */ = {
+                       isa = XCBuildConfiguration;
+                       buildSettings = {
+                               COMBINE_HIDPI_IMAGES = YES;
+                               EXECUTABLE_PREFIX = lib;
+                               GCC_PREPROCESSOR_DEFINITIONS = "NDEBUG=1";
+                               GCC_WARN_UNINITIALIZED_AUTOS = YES_AGGRESSIVE;
+                               PRODUCT_NAME = "$(TARGET_NAME)";
+                               SDKROOT = macosx.internal;
+                       };
+                       name = Release;
+               };
+               14F271C018EA3963008C152F /* Debug */ = {
+                       isa = XCBuildConfiguration;
+                       buildSettings = {
+                               COMBINE_HIDPI_IMAGES = YES;
+                               DEBUG_INFORMATION_FORMAT = dwarf;
+                               EXECUTABLE_PREFIX = lib;
+                               GCC_ENABLE_OBJC_EXCEPTIONS = NO;
+                               GCC_SYMBOLS_PRIVATE_EXTERN = YES;
+                               GCC_THREADSAFE_STATICS = NO;
+                               GCC_WARN_UNINITIALIZED_AUTOS = YES_AGGRESSIVE;
+                               PRODUCT_NAME = "$(TARGET_NAME)";
+                               SDKROOT = macosx.internal;
+                       };
+                       name = Debug;
+               };
+               14F271C118EA3963008C152F /* Release */ = {
+                       isa = XCBuildConfiguration;
+                       buildSettings = {
+                               COMBINE_HIDPI_IMAGES = YES;
+                               EXECUTABLE_PREFIX = lib;
+                               GCC_ENABLE_OBJC_EXCEPTIONS = NO;
+                               GCC_PREPROCESSOR_DEFINITIONS = "NDEBUG=1";
+                               GCC_SYMBOLS_PRIVATE_EXTERN = YES;
+                               GCC_THREADSAFE_STATICS = NO;
+                               GCC_WARN_UNINITIALIZED_AUTOS = YES_AGGRESSIVE;
+                               PRODUCT_NAME = "$(TARGET_NAME)";
+                               SDKROOT = macosx.internal;
+                       };
+                       name = Release;
+               };
+/* End XCBuildConfiguration section */
+
+/* Begin XCConfigurationList section */
+               145F683A179DC45F00D65598 /* Build configuration list for PBXProject "bmalloc" */ = {
+                       isa = XCConfigurationList;
+                       buildConfigurations = (
+                               145F684A179DC45F00D65598 /* Debug */,
+                               145F684B179DC45F00D65598 /* Release */,
+                       );
+                       defaultConfigurationIsVisible = 0;
+                       defaultConfigurationName = Release;
+               };
+               14CC394518EA8743004AFE34 /* Build configuration list for PBXNativeTarget "mbmalloc" */ = {
+                       isa = XCConfigurationList;
+                       buildConfigurations = (
+                               14CC394618EA8743004AFE34 /* Debug */,
+                               14CC394718EA8743004AFE34 /* Release */,
+                       );
+                       defaultConfigurationIsVisible = 0;
+                       defaultConfigurationName = Release;
+               };
+               14F271BF18EA3963008C152F /* Build configuration list for PBXNativeTarget "bmalloc" */ = {
+                       isa = XCConfigurationList;
+                       buildConfigurations = (
+                               14F271C018EA3963008C152F /* Debug */,
+                               14F271C118EA3963008C152F /* Release */,
+                       );
+                       defaultConfigurationIsVisible = 0;
+                       defaultConfigurationName = Release;
+               };
+/* End XCConfigurationList section */
+       };
+       rootObject = 145F6837179DC45F00D65598 /* Project object */;
+}
diff --git a/Source/bmalloc/bmalloc/Algorithm.h b/Source/bmalloc/bmalloc/Algorithm.h
new file mode 100644 (file)
index 0000000..298e5f6
--- /dev/null
@@ -0,0 +1,91 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef Algorithm_h
+#define Algorithm_h
+
+#include "Algorithm.h"
+#include <algorithm>
+#include <cstdint>
+#include <cstddef>
+#include <limits>
+#include <type_traits>
+#include <chrono>
+
+namespace bmalloc {
+
+// Versions of min and max that are compatible with compile-time constants.
+template<typename T> inline constexpr T max(T a, T b)
+{
+    return a > b ? a : b;
+}
+    
+template<typename T> inline constexpr T min(T a, T b)
+{
+    return a < b ? a : b;
+}
+    
+template<typename T> inline constexpr T mask(T value, uintptr_t mask)
+{
+    return reinterpret_cast<T>(reinterpret_cast<uintptr_t>(value) & mask);
+}
+
+template<typename T> inline constexpr bool test(T value, uintptr_t mask)
+{
+    return !!(reinterpret_cast<uintptr_t>(value) & mask);
+}
+
+template<size_t divisor, typename T> inline constexpr T roundUpToMultipleOf(T x)
+{
+    static_assert(divisor && !(divisor & (divisor - 1)), "'divisor' must be a power of two.");
+    return reinterpret_cast<T>((reinterpret_cast<uintptr_t>(x) + (divisor - 1ul)) & ~(divisor - 1ul));
+}
+
+template<size_t divisor, typename T> inline constexpr T roundDownToMultipleOf(T x)
+{
+    static_assert(divisor && !(divisor & (divisor - 1)), "'divisor' must be a power of two.");
+    return reinterpret_cast<T>(mask(reinterpret_cast<uintptr_t>(x), ~(divisor - 1ul)));
+}
+
+// Version of sizeof that returns 0 for empty classes.
+
+template<typename T> inline constexpr size_t sizeOf()
+{
+    return std::is_empty<T>::value ? 0 : sizeof(T);
+}
+
+template<typename T> inline constexpr size_t bitCount()
+{
+    return sizeof(T) * 8;
+}
+
+inline constexpr bool isPowerOfTwo(size_t size)
+{
+    return !(size & (size - 1));
+}
+
+} // namespace bmalloc
+
+#endif // Algorithm_h
diff --git a/Source/bmalloc/bmalloc/Allocator.cpp b/Source/bmalloc/bmalloc/Allocator.cpp
new file mode 100644 (file)
index 0000000..fb43a58
--- /dev/null
@@ -0,0 +1,158 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "Allocator.h"
+#include "BAssert.h"
+#include "Deallocator.h"
+#include "Heap.h"
+#include "PerProcess.h"
+#include "Sizes.h"
+#include <algorithm>
+
+using namespace std;
+
+namespace bmalloc {
+
+Allocator::Allocator(Deallocator& deallocator)
+    : m_deallocator(deallocator)
+    , m_smallAllocators()
+    , m_mediumAllocator()
+    , m_smallAllocatorLog()
+    , m_mediumAllocatorLog()
+{
+    unsigned short size = alignment;
+    for (auto& allocator : m_smallAllocators) {
+        allocator = SmallAllocator(size);
+        size += alignment;
+    }
+}
+
+Allocator::~Allocator()
+{
+    for (auto& allocator : m_smallAllocators)
+        log(allocator);
+    processSmallAllocatorLog();
+
+    log(m_mediumAllocator);
+    processMediumAllocatorLog();
+}
+
+void Allocator::log(SmallAllocator& allocator)
+{
+    if (m_smallAllocatorLog.size() == m_smallAllocatorLog.capacity())
+        processSmallAllocatorLog();
+    
+    if (allocator.isNull())
+        return;
+
+    m_smallAllocatorLog.push(std::make_pair(allocator.line(), allocator.derefCount()));
+}
+
+void Allocator::processSmallAllocatorLog()
+{
+    std::lock_guard<Mutex> lock(PerProcess<Heap>::mutex());
+
+    for (auto& logEntry : m_smallAllocatorLog) {
+        if (!logEntry.first->deref(logEntry.second))
+            continue;
+        m_deallocator.deallocateSmallLine(logEntry.first);
+    }
+    m_smallAllocatorLog.clear();
+}
+
+void Allocator::log(MediumAllocator& allocator)
+{
+    if (m_mediumAllocatorLog.size() == m_mediumAllocatorLog.capacity())
+        processMediumAllocatorLog();
+
+    if (allocator.isNull())
+        return;
+
+    m_mediumAllocatorLog.push(std::make_pair(allocator.line(), allocator.derefCount()));
+}
+
+void Allocator::processMediumAllocatorLog()
+{
+    std::lock_guard<Mutex> lock(PerProcess<Heap>::mutex());
+
+    for (auto& logEntry : m_mediumAllocatorLog) {
+        if (!logEntry.first->deref(logEntry.second))
+            continue;
+        m_deallocator.deallocateMediumLine(logEntry.first);
+    }
+    m_mediumAllocatorLog.clear();
+}
+
+void* Allocator::allocateLarge(size_t size)
+{
+    size = roundUpToMultipleOf<largeAlignment>(size);
+    std::lock_guard<Mutex> lock(PerProcess<Heap>::mutex());
+    return PerProcess<Heap>::getFastCase()->allocateLarge(lock, size);
+}
+
+void* Allocator::allocateXLarge(size_t size)
+{
+    size = roundUpToMultipleOf<largeAlignment>(size);
+    std::lock_guard<Mutex> lock(PerProcess<Heap>::mutex());
+    return PerProcess<Heap>::getFastCase()->allocateXLarge(lock, size);
+}
+
+void* Allocator::allocateMedium(size_t size)
+{
+    MediumAllocator& allocator = m_mediumAllocator;
+    size = roundUpToMultipleOf<alignment>(size);
+
+    void* object;
+    if (allocator.allocate(size, object))
+        return object;
+
+    log(allocator);
+    allocator.refill(m_deallocator.allocateMediumLine());
+    return allocator.allocate(size);
+}
+
+void* Allocator::allocateSlowCase(size_t size)
+{
+IF_DEBUG(
+    void* dummy;
+    ASSERT(!allocateFastCase(size, dummy));
+)
+    if (size <= smallMax) {
+        SmallAllocator& allocator = smallAllocatorFor(size);
+        log(allocator);
+        allocator.refill(m_deallocator.allocateSmallLine());
+        return allocator.allocate();
+    }
+
+    if (size <= mediumMax)
+        return allocateMedium(size);
+    
+    if (size <= largeMax)
+        return allocateLarge(size);
+
+    return allocateXLarge(size);
+}
+
+} // namespace bmalloc
diff --git a/Source/bmalloc/bmalloc/Allocator.h b/Source/bmalloc/bmalloc/Allocator.h
new file mode 100644 (file)
index 0000000..fa76d10
--- /dev/null
@@ -0,0 +1,102 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef Allocator_h
+#define Allocator_h
+
+#include "FixedVector.h"
+#include "MediumAllocator.h"
+#include "Sizes.h"
+#include "SmallAllocator.h"
+#include <array>
+
+namespace bmalloc {
+
+class Deallocator;
+
+// Per-cache object allocator.
+
+class Allocator {
+public:
+    Allocator(Deallocator&);
+    ~Allocator();
+
+    void* allocate(size_t);
+    bool allocateFastCase(size_t, void*&);
+    void* allocateSlowCase(size_t);
+
+private:
+    SmallAllocator& smallAllocatorFor(size_t);
+    void* allocateFastCase(SmallAllocator&);
+
+    void* allocateMedium(size_t);
+    void* allocateLarge(size_t);
+    void* allocateXLarge(size_t);
+    
+    void log(SmallAllocator&);
+    void log(MediumAllocator&);
+
+    void processSmallAllocatorLog();
+    void processMediumAllocatorLog();
+
+    Deallocator& m_deallocator;
+
+    std::array<SmallAllocator, smallMax / alignment> m_smallAllocators;
+    MediumAllocator m_mediumAllocator;
+
+    FixedVector<std::pair<SmallLine*, unsigned char>, smallAllocatorLogCapacity> m_smallAllocatorLog;
+    FixedVector<std::pair<MediumLine*, unsigned char>, mediumAllocatorLogCapacity> m_mediumAllocatorLog;
+};
+
+inline SmallAllocator& Allocator::smallAllocatorFor(size_t size)
+{
+    size_t index = mask((size - 1ul) / alignment, m_smallAllocators.size() - 1);
+    return m_smallAllocators[index];
+}
+
+inline bool Allocator::allocateFastCase(size_t size, void*& object)
+{
+    if (size > smallMax)
+        return false;
+
+    SmallAllocator& allocator = smallAllocatorFor(size);
+    if (!allocator.canAllocate())
+        return false;
+
+    object = allocator.allocate();
+    return true;
+}
+
+inline void* Allocator::allocate(size_t size)
+{
+    void* object;
+    if (!allocateFastCase(size, object))
+        return allocateSlowCase(size);
+    return object;
+}
+
+} // namespace bmalloc
+
+#endif // Allocator_h
diff --git a/Source/bmalloc/bmalloc/AsyncTask.cpp b/Source/bmalloc/bmalloc/AsyncTask.cpp
new file mode 100644 (file)
index 0000000..afa3fe6
--- /dev/null
@@ -0,0 +1,55 @@
+#include "AsyncTask.h"
+#include "NoInline.h"
+
+namespace bmalloc {
+
+template<typename Function>
+NO_INLINE void AsyncTask<Function>::runSlowCase()
+{
+    State oldState = m_state.exchange(Signaled);
+    if (oldState == Signaled || oldState == Running)
+        return;
+
+    if (oldState == Sleeping) {
+        m_condition.notify_one();
+        return;
+    }
+
+    ASSERT(oldState == Exited);
+    pthread_create(&m_thread, nullptr, &pthreadEntryPoint, this);
+    pthread_detach(m_thread);
+}
+
+template<typename Function>
+void* AsyncTask<Function>::pthreadEntryPoint(void* asyncTask)
+{
+    static_cast<AsyncTask*>(asyncTask)->entryPoint();
+    return nullptr;
+}
+
+template<typename Function>
+void AsyncTask<Function>::entryPoint()
+{
+    State expectedState;
+    while (1) {
+        expectedState = Signaled;
+        if (m_state.compare_exchange_weak(expectedState, Running)) {
+            m_function();
+            continue;
+        }
+
+        expectedState = Running;
+        if (m_state.compare_exchange_weak(expectedState, Sleeping)) {
+            std::mutex dummy; // No need for a real mutex because there's only one waiting thread.
+            std::unique_lock<std::mutex> lock(dummy);
+            m_condition.wait_for(lock, std::chrono::milliseconds(2), [=]() { return this->m_state != Sleeping; });
+            continue;
+        }
+
+        expectedState = Sleeping;
+        if (m_state.compare_exchange_weak(expectedState, Exited))
+            break;
+    }
+}
+
+} // namespace bmalloc
diff --git a/Source/bmalloc/bmalloc/AsyncTask.h b/Source/bmalloc/bmalloc/AsyncTask.h
new file mode 100644 (file)
index 0000000..dd8fbd5
--- /dev/null
@@ -0,0 +1,146 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef AsyncTask_h
+#define AsyncTask_h
+
+#include "BAssert.h"
+#include "Inline.h"
+#include <atomic>
+#include <condition_variable>
+#include <pthread.h>
+#include <thread>
+
+namespace bmalloc {
+
+template<typename Object, typename Function>
+class AsyncTask {
+public:
+    AsyncTask(Object&, const Function&);
+
+    void run();
+    void join();
+
+private:
+    enum State { Exited, Sleeping, Running, Signaled };
+
+    static const constexpr std::chrono::seconds exitDelay = std::chrono::seconds(1);
+
+    void runSlowCase();
+
+    static void* pthreadEntryPoint(void*);
+    void entryPoint();
+
+    std::atomic<State> m_state;
+
+    std::mutex m_conditionMutex;
+    std::condition_variable m_condition;
+    pthread_t m_thread;
+
+    Object& m_object;
+    Function m_function;
+};
+
+template<typename Object, typename Function> const std::chrono::seconds AsyncTask<Object, Function>::exitDelay;
+
+template<typename Object, typename Function>
+AsyncTask<Object, Function>::AsyncTask(Object& object, const Function& function)
+    : m_state(Exited)
+    , m_thread()
+    , m_condition()
+    , m_object(object)
+    , m_function(function)
+{
+}
+
+template<typename Object, typename Function>
+void AsyncTask<Object, Function>::join()
+{
+    if (m_state == Exited)
+        return;
+
+    { std::lock_guard<std::mutex> lock(m_conditionMutex); }
+    m_condition.notify_one();
+
+    while (m_state != Exited)
+        std::this_thread::yield();
+}
+
+template<typename Object, typename Function>
+inline void AsyncTask<Object, Function>::run()
+{
+    if (m_state == Signaled)
+        return;
+    runSlowCase();
+}
+
+template<typename Object, typename Function>
+NO_INLINE void AsyncTask<Object, Function>::runSlowCase()
+{
+    State oldState = m_state.exchange(Signaled);
+    if (oldState == Signaled || oldState == Running)
+        return;
+
+    if (oldState == Sleeping) {
+        { std::lock_guard<std::mutex> lock(m_conditionMutex); }
+        m_condition.notify_one();
+        return;
+    }
+
+    ASSERT(oldState == Exited);
+    pthread_create(&m_thread, nullptr, &pthreadEntryPoint, this);
+    pthread_detach(m_thread);
+}
+
+template<typename Object, typename Function>
+void* AsyncTask<Object, Function>::pthreadEntryPoint(void* asyncTask)
+{
+    static_cast<AsyncTask*>(asyncTask)->entryPoint();
+    return nullptr;
+}
+
+template<typename Object, typename Function>
+void AsyncTask<Object, Function>::entryPoint()
+{
+    while (1) {
+        State expectedState = Signaled;
+        if (m_state.compare_exchange_weak(expectedState, Running))
+            (m_object.*m_function)();
+
+        expectedState = Running;
+        if (m_state.compare_exchange_weak(expectedState, Sleeping)) {
+            std::unique_lock<std::mutex> lock(m_conditionMutex);
+            m_condition.wait_for(lock, exitDelay, [=]() { return this->m_state != Sleeping; });
+        }
+
+        expectedState = Sleeping;
+        if (m_state.compare_exchange_weak(expectedState, Exited))
+            return;
+    }
+}
+
+} // namespace bmalloc
+
+#endif // AsyncTask_h
diff --git a/Source/bmalloc/bmalloc/BAssert.h b/Source/bmalloc/bmalloc/BAssert.h
new file mode 100644 (file)
index 0000000..94998c7
--- /dev/null
@@ -0,0 +1,57 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef BAssert_h
+#define BAssert_h
+
+#define ASSERT_IMPL(x) do { \
+    if (!(x)) \
+        *(int*)0xbbadbeef = 0; \
+} while(0);
+
+#define RELEASE_ASSERT(x) ASSERT_IMPL(x)
+
+// ===== Release build =====
+
+#if defined(NDEBUG)
+
+#define ASSERT(x)
+
+#define IF_DEBUG(x...)
+
+#endif // defined(NDEBUG)
+
+
+// ===== Debug build =====
+
+#if !defined(NDEBUG)
+
+#define ASSERT(x) ASSERT_IMPL(x)
+
+#define IF_DEBUG(x...) x
+
+#endif // !defined(NDEBUG)
+
+#endif // BAssert_h
diff --git a/Source/bmalloc/bmalloc/BeginTag.h b/Source/bmalloc/bmalloc/BeginTag.h
new file mode 100644 (file)
index 0000000..394d49d
--- /dev/null
@@ -0,0 +1,45 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef BeginTag_h
+#define BeginTag_h
+
+#include "BoundaryTag.h"
+
+namespace bmalloc {
+
+class BeginTag : public BoundaryTag {
+public:
+    bool isInFreeList(size_t);
+};
+
+inline bool BeginTag::isInFreeList(size_t size)
+{
+    return isFree() && !isEnd() && this->size() == size;
+}
+
+} // namespace bmalloc
+
+#endif // BeginTag_h
diff --git a/Source/bmalloc/bmalloc/BoundaryTag.h b/Source/bmalloc/bmalloc/BoundaryTag.h
new file mode 100644 (file)
index 0000000..9f46b33
--- /dev/null
@@ -0,0 +1,106 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef BoundaryTag_h
+#define BoundaryTag_h
+
+#include "BAssert.h"
+#include "Sizes.h"
+
+namespace bmalloc {
+
+class BeginTag;
+class EndTag;
+class LargeChunk;
+class Range;
+
+class BoundaryTag {
+public:
+    static Range init(LargeChunk*);
+    static Range deallocate(void*);
+    static void allocate(size_t, Range&, Range& leftover, bool& hasPhysicalPages);
+
+    bool isXLarge() { return m_size == xLargeMarker; }
+    void setXLarge() { m_size = xLargeMarker; }
+
+    bool isFree() { return m_isFree; }
+    void setFree(bool isFree) { m_isFree = isFree; }
+    
+    bool isEnd() { return m_isEnd; }
+    void setEnd(bool isEnd) { m_isEnd = isEnd; }
+
+    bool hasPhysicalPages() { return m_hasPhysicalPages; }
+    void setHasPhysicalPages(bool hasPhysicalPages) { m_hasPhysicalPages = hasPhysicalPages; }
+
+    bool isNull() { return !m_size; }
+    void clear() { memset(this, 0, sizeof(*this)); }
+    
+    size_t size() { return m_size; }
+    void setSize(size_t);
+    
+    EndTag* prev();
+    BeginTag* next();
+
+private:
+    static const size_t flagBits = 3;
+    static const size_t sizeBits = bitCount<unsigned>() - flagBits;
+    static const size_t xLargeMarker = 1; // This size is unused because our minimum object size is greater than it.
+
+    static_assert(largeMin > xLargeMarker, "largeMin must provide enough umbrella to fit xLargeMarker.");
+    static_assert((1 << sizeBits) - 1 >= largeMax, "largeMax must be encodable in a BoundaryTag.");
+
+    static void splitLarge(BeginTag*, size_t size, EndTag*& endTag, Range&, Range& leftover);
+    static void mergeLargeLeft(EndTag*& prev, BeginTag*& beginTag, Range&, bool& hasPhysicalPages);
+    static void mergeLargeRight(EndTag*&, BeginTag*& next, Range&, bool& hasPhysicalPages);
+    static void mergeLarge(BeginTag*&, EndTag*&, Range&);
+
+    bool m_isFree: 1;
+    bool m_isEnd: 1;
+    bool m_hasPhysicalPages: 1;
+    unsigned m_size: sizeBits;
+};
+
+inline void BoundaryTag::setSize(size_t size)
+{
+    m_size = static_cast<unsigned>(size);
+    ASSERT(this->size() == size);
+    ASSERT(!isXLarge());
+}
+
+inline EndTag* BoundaryTag::prev()
+{
+    BoundaryTag* prev = this - 1;
+    return reinterpret_cast<EndTag*>(prev);
+}
+
+inline BeginTag* BoundaryTag::next()
+{
+    BoundaryTag* next = this + 1;
+    return reinterpret_cast<BeginTag*>(next);
+}
+
+} // namespace bmalloc
+
+#endif // BoundaryTag_h
diff --git a/Source/bmalloc/bmalloc/BoundaryTagInlines.h b/Source/bmalloc/bmalloc/BoundaryTagInlines.h
new file mode 100644 (file)
index 0000000..2881042
--- /dev/null
@@ -0,0 +1,221 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef BoundaryTagInlines_h
+#define BoundaryTagInlines_h
+
+#include "Range.h"
+#include "BeginTag.h"
+#include "EndTag.h"
+#include "Inline.h"
+#include "LargeChunk.h"
+
+namespace bmalloc {
+
+static inline void validate(const Range& range)
+{
+IF_DEBUG(
+    BeginTag* beginTag = LargeChunk::beginTag(range.begin());
+    EndTag* endTag = LargeChunk::endTag(range.begin(), range.size());
+
+    ASSERT(!beginTag->isEnd());
+    if (beginTag->isXLarge())
+        return;
+)
+    ASSERT(range.size() >= largeMin);
+    ASSERT(beginTag->size() == range.size());
+
+    ASSERT(beginTag->size() == endTag->size());
+    ASSERT(beginTag->isFree() == endTag->isFree());
+    ASSERT(beginTag->hasPhysicalPages() == endTag->hasPhysicalPages());
+    ASSERT(beginTag->isXLarge() == endTag->isXLarge());
+    ASSERT(static_cast<BoundaryTag*>(endTag) == static_cast<BoundaryTag*>(beginTag) || endTag->isEnd());
+}
+
+static inline void validatePrev(EndTag* prev, void* object)
+{
+    size_t prevSize = prev->size();
+    void* prevObject = static_cast<char*>(object) - prevSize;
+    validate(Range(prevObject, prevSize));
+}
+
+static inline void validateNext(BeginTag* next, const Range& range)
+{
+    if (next->size() == largeMin && !next->isFree()) // Right sentinel tag.
+        return;
+
+    void* nextObject = range.end();
+    size_t nextSize = next->size();
+    validate(Range(nextObject, nextSize));
+}
+
+static inline void validate(EndTag* prev, const Range& range, BeginTag* next)
+{
+    validatePrev(prev, range.begin());
+    validate(range);
+    validateNext(next, range);
+}
+
+inline Range BoundaryTag::init(LargeChunk* chunk)
+{
+    Range range(chunk->begin(), chunk->end() - chunk->begin());
+
+    BeginTag* beginTag = LargeChunk::beginTag(range.begin());
+    beginTag->setSize(range.size());
+    beginTag->setFree(true);
+    beginTag->setHasPhysicalPages(false);
+
+    EndTag* endTag = LargeChunk::endTag(range.begin(), range.size());
+    *endTag = *beginTag;
+
+    // Mark the left and right edges of our chunk as allocated. This naturally
+    // prevents merging logic from overflowing beyond our chunk, without requiring
+    // special-case checks.
+    
+    EndTag* leftSentinel = beginTag->prev();
+    ASSERT(leftSentinel >= static_cast<void*>(chunk));
+    leftSentinel->setSize(largeMin);
+    leftSentinel->setFree(false);
+
+    BeginTag* rightSentinel = endTag->next();
+    ASSERT(rightSentinel < static_cast<void*>(range.begin()));
+    rightSentinel->setSize(largeMin);
+    rightSentinel->setFree(false);
+    
+    return range;
+}
+
+inline void BoundaryTag::mergeLargeLeft(EndTag*& prev, BeginTag*& beginTag, Range& range, bool& hasPhysicalPages)
+{
+    Range left(range.begin() - prev->size(), prev->size());
+
+    hasPhysicalPages &= prev->hasPhysicalPages();
+
+    range = Range(left.begin(), left.size() + range.size());
+
+    prev->clear();
+    beginTag->clear();
+
+    beginTag = LargeChunk::beginTag(range.begin());
+}
+
+inline void BoundaryTag::mergeLargeRight(EndTag*& endTag, BeginTag*& next, Range& range, bool& hasPhysicalPages)
+{
+    Range right(range.end(), next->size());
+
+    hasPhysicalPages &= next->hasPhysicalPages();
+
+    range = Range(range.begin(), range.size() + right.size());
+
+    endTag->clear();
+    next->clear();
+
+    endTag = LargeChunk::endTag(range.begin(), range.size());
+}
+
+INLINE void BoundaryTag::mergeLarge(BeginTag*& beginTag, EndTag*& endTag, Range& range)
+{
+    EndTag* prev = beginTag->prev();
+    BeginTag* next = endTag->next();
+    bool hasPhysicalPages = beginTag->hasPhysicalPages();
+
+    validate(prev, range, next);
+
+    if (prev->isFree())
+        mergeLargeLeft(prev, beginTag, range, hasPhysicalPages);
+
+    if (next->isFree())
+        mergeLargeRight(endTag, next, range, hasPhysicalPages);
+
+    beginTag->setSize(range.size());
+    beginTag->setFree(true);
+    beginTag->setHasPhysicalPages(hasPhysicalPages);
+
+    if (endTag != static_cast<BoundaryTag*>(beginTag))
+        *endTag = *beginTag;
+
+    validate(beginTag->prev(), range, endTag->next());
+}
+
+inline Range BoundaryTag::deallocate(void* object)
+{
+    BeginTag* beginTag = LargeChunk::beginTag(object);
+    ASSERT(!beginTag->isFree());
+    ASSERT(!beginTag->isXLarge())
+
+    Range range(object, beginTag->size());
+    EndTag* endTag = LargeChunk::endTag(range.begin(), range.size());
+    mergeLarge(beginTag, endTag, range);
+    
+    return range;
+}
+
+INLINE void BoundaryTag::splitLarge(BeginTag* beginTag, size_t size, EndTag*& endTag, Range& range, Range& leftover)
+{
+    beginTag->setSize(size);
+
+    EndTag* splitEndTag = LargeChunk::endTag(range.begin(), size);
+    if (splitEndTag != static_cast<BoundaryTag*>(beginTag))
+        *splitEndTag = *beginTag;
+
+    leftover = Range(range.begin() + size, range.size() - size);
+    ASSERT(leftover.size() >= largeMin);
+    BeginTag* leftoverBeginTag = LargeChunk::beginTag(leftover.begin());
+    *leftoverBeginTag = *beginTag;
+    leftoverBeginTag->setSize(leftover.size());
+
+    if (leftoverBeginTag != static_cast<BoundaryTag*>(endTag))
+        *endTag = *leftoverBeginTag;
+
+    validate(beginTag->prev(), Range(range.begin(), size), leftoverBeginTag);
+    validate(leftoverBeginTag->prev(), leftover, endTag->next());
+
+    range = Range(range.begin(), size);
+    endTag = splitEndTag;
+}
+
+INLINE void BoundaryTag::allocate(size_t size, Range& range, Range& leftover, bool& hasPhysicalPages)
+{
+    BeginTag* beginTag = LargeChunk::beginTag(range.begin());
+    EndTag* endTag = LargeChunk::endTag(range.begin(), range.size());
+
+    ASSERT(beginTag->isFree());
+    validate(beginTag->prev(), range, endTag->next());
+
+    if (range.size() - size > largeMin)
+        splitLarge(beginTag, size, endTag, range, leftover);
+
+    hasPhysicalPages = beginTag->hasPhysicalPages();
+
+    beginTag->setHasPhysicalPages(true);
+    beginTag->setFree(false);
+
+    endTag->setHasPhysicalPages(true);
+    endTag->setFree(false);
+}
+
+} // namespace bmalloc
+
+#endif // BoundaryTagInlines_h
diff --git a/Source/bmalloc/bmalloc/Cache.cpp b/Source/bmalloc/bmalloc/Cache.cpp
new file mode 100644 (file)
index 0000000..722393e
--- /dev/null
@@ -0,0 +1,77 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "Cache.h"
+#include "Heap.h"
+#include "Inline.h"
+#include "PerProcess.h"
+
+namespace bmalloc {
+
+inline void* Cache::operator new(size_t size)
+{
+    return vmAllocate(vmSize(size));
+}
+
+inline void Cache::operator delete(void* p, size_t size)
+{
+    vmDeallocate(p, vmSize(size));
+}
+
+inline Cache::Cache()
+    : m_deallocator()
+    , m_allocator(m_deallocator)
+{
+    // Ensure that the heap exists, so Allocator and Deallocator can assume it does.
+    PerProcess<Heap>::get();
+}
+
+NO_INLINE void* Cache::allocateSlowCase(size_t size)
+{
+    Cache* cache = PerThread<Cache>::getFastCase();
+    if (!cache)
+        return allocateSlowCaseNullCache(size);
+    return cache->allocator().allocateSlowCase(size);
+}
+
+NO_INLINE void* Cache::allocateSlowCaseNullCache(size_t size)
+{
+    return PerThread<Cache>::getSlowCase()->allocator().allocate(size);
+}
+
+NO_INLINE void Cache::deallocateSlowCase(void* object)
+{
+    Cache* cache = PerThread<Cache>::getFastCase();
+    if (!cache)
+        return deallocateSlowCaseNullCache(object);
+    cache->deallocator().deallocateSlowCase(object);
+}
+
+NO_INLINE void Cache::deallocateSlowCaseNullCache(void* object)
+{
+    PerThread<Cache>::getSlowCase()->deallocator().deallocate(object);
+}
+
+} // namespace bmalloc
diff --git a/Source/bmalloc/bmalloc/Cache.h b/Source/bmalloc/bmalloc/Cache.h
new file mode 100644 (file)
index 0000000..d1178ea
--- /dev/null
@@ -0,0 +1,95 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef Cache_h
+#define Cache_h
+
+#include "Allocator.h"
+#include "Deallocator.h"
+#include "PerThread.h"
+
+namespace bmalloc {
+
+// Per-thread allocation / deallocation cache, backed by a per-process Heap.
+
+class Cache {
+public:
+    void* operator new(size_t);
+    void operator delete(void*, size_t);
+
+    static void* allocate(size_t);
+    static void deallocate(void*);
+
+    Cache();
+
+    Allocator& allocator() { return m_allocator; }
+    Deallocator& deallocator() { return m_deallocator; }
+
+private:
+    static bool allocateFastCase(size_t, void*&);
+    static void* allocateSlowCase(size_t);
+    static void* allocateSlowCaseNullCache(size_t);
+
+    static bool deallocateFastCase(void*);
+    static void deallocateSlowCase(void*);
+    static void deallocateSlowCaseNullCache(void*);
+
+    Deallocator m_deallocator;
+    Allocator m_allocator;
+};
+
+inline bool Cache::allocateFastCase(size_t size, void*& object)
+{
+    Cache* cache = PerThread<Cache>::getFastCase();
+    if (!cache)
+        return false;
+    return cache->allocator().allocateFastCase(size, object);
+}
+
+inline bool Cache::deallocateFastCase(void* object)
+{
+    Cache* cache = PerThread<Cache>::getFastCase();
+    if (!cache)
+        return false;
+    return cache->deallocator().deallocateFastCase(object);
+}
+
+inline void* Cache::allocate(size_t size)
+{
+    void* object;
+    if (!allocateFastCase(size, object))
+        return allocateSlowCase(size);
+    return object;
+}
+
+inline void Cache::deallocate(void* object)
+{
+    if (!deallocateFastCase(object))
+        deallocateSlowCase(object);
+}
+
+} // namespace bmalloc
+
+#endif // Cache_h
diff --git a/Source/bmalloc/bmalloc/Chunk.h b/Source/bmalloc/bmalloc/Chunk.h
new file mode 100644 (file)
index 0000000..c1202d7
--- /dev/null
@@ -0,0 +1,86 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef Chunk_h
+#define Chunk_h
+
+#include "ObjectType.h"
+#include "Sizes.h"
+#include "VMAllocate.h"
+
+namespace bmalloc {
+
+template<class Traits>
+class Chunk {
+public:
+    typedef typename Traits::Page Page;
+    typedef typename Traits::Line Line;
+    static const size_t lineSize = Traits::lineSize;
+    static const size_t chunkSize = Traits::chunkSize;
+    static const size_t chunkOffset = Traits::chunkOffset;
+    static const uintptr_t chunkMask = Traits::chunkMask;
+
+    static Chunk* create();
+    static Chunk* get(void*);
+
+    Page* begin() { return Page::get(Line::get(m_memory)); }
+    Page* end() { return &m_pages[pageCount]; }
+    
+    Line* lines() { return m_lines; }
+    Page* pages() { return m_pages; }
+
+private:
+    static_assert(!(vmPageSize % lineSize), "vmPageSize must be an even multiple of line size");
+    static_assert(!(chunkSize % lineSize), "chunk size must be an even multiple of line size");
+
+    static const size_t lineCount = chunkSize / lineSize;
+    static const size_t pageCount = chunkSize / vmPageSize;
+
+    Line m_lines[lineCount];
+    Page m_pages[pageCount];
+
+    // Align to vmPageSize to avoid sharing physical pages with metadata.
+    // Otherwise, we'll confuse the scavenger into scavenging metadata.
+     alignas(vmPageSize) char m_memory[];
+};
+
+template<class Traits>
+inline auto Chunk<Traits>::create() -> Chunk*
+{
+    size_t vmSize = bmalloc::vmSize(chunkSize);
+    std::pair<void*, Range> result = vmAllocate(vmSize, superChunkSize, chunkOffset);
+    return new (result.first) Chunk;
+}
+
+template<class Traits>
+inline auto Chunk<Traits>::get(void* object) -> Chunk*
+{
+    ASSERT(isSmallOrMedium(object));
+    return static_cast<Chunk*>(mask(object, chunkMask));
+}
+
+}; // namespace bmalloc
+
+#endif // Chunk
diff --git a/Source/bmalloc/bmalloc/Deallocator.cpp b/Source/bmalloc/bmalloc/Deallocator.cpp
new file mode 100644 (file)
index 0000000..3c16493
--- /dev/null
@@ -0,0 +1,158 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "BAssert.h"
+#include "BeginTag.h"
+#include "LargeChunk.h"
+#include "Deallocator.h"
+#include "Heap.h"
+#include "Inline.h"
+#include "PerProcess.h"
+#include "SmallChunk.h"
+#include <algorithm>
+#include <sys/mman.h>
+
+using namespace std;
+
+namespace bmalloc {
+
+Deallocator::Deallocator()
+    : m_objectLog()
+    , m_smallLineCache()
+    , m_mediumLineCache()
+{
+}
+
+Deallocator::~Deallocator()
+{
+    std::lock_guard<Mutex> lock(PerProcess<Heap>::mutex());
+    processObjectLog();
+}
+
+void Deallocator::deallocateLarge(void* object)
+{
+    std::lock_guard<Mutex> lock(PerProcess<Heap>::mutex());
+    PerProcess<Heap>::getFastCase()->deallocateLarge(lock, object);
+}
+
+void Deallocator::deallocateXLarge(void* object)
+{
+    std::lock_guard<Mutex> lock(PerProcess<Heap>::mutex());
+    PerProcess<Heap>::getFastCase()->deallocateXLarge(lock, object);
+}
+
+void Deallocator::processObjectLog()
+{
+    for (auto object : m_objectLog) {
+        if (isSmall(object)) {
+            SmallLine* line = SmallLine::get(object);
+            if (!line->deref())
+                continue;
+            deallocateSmallLine(line);
+        } else {
+            ASSERT(isSmallOrMedium(object));
+            MediumLine* line = MediumLine::get(object);
+            if (!line->deref())
+                continue;
+            deallocateMediumLine(line);
+        }
+    }
+    
+    m_objectLog.clear();
+}
+
+void Deallocator::deallocateSlowCase(void* object)
+{
+    ASSERT(!deallocateFastCase(object));
+
+    if (!object)
+        return;
+
+    if (isSmallOrMedium(object)) {
+        std::unique_lock<Mutex> lock(PerProcess<Heap>::mutex(), std::defer_lock);
+        bool didLock;
+        if (m_objectLog.size() == m_objectLog.capacity()) {
+            didLock = true;
+            lock.lock();
+        } else
+            didLock = lock.try_lock();
+        
+        if (didLock)
+            processObjectLog();
+        
+        m_objectLog.push(object);
+        return;
+    }
+
+    BeginTag* beginTag = LargeChunk::beginTag(object);
+    if (!beginTag->isXLarge())
+        return deallocateLarge(object);
+    
+    return deallocateXLarge(object);
+}
+
+void Deallocator::deallocateSmallLine(SmallLine* line)
+{
+    if (m_smallLineCache.size() == m_smallLineCache.capacity())
+        return PerProcess<Heap>::getFastCase()->deallocateSmallLine(line);
+
+    m_smallLineCache.push(line);
+}
+
+SmallLine* Deallocator::allocateSmallLine()
+{
+    if (!m_smallLineCache.size()) {
+        std::lock_guard<Mutex> lock(PerProcess<Heap>::mutex());
+        Heap* heap = PerProcess<Heap>::getFastCase();
+
+        while (m_smallLineCache.size() != m_smallLineCache.capacity())
+            m_smallLineCache.push(heap->allocateSmallLine(lock));
+    }
+
+    return m_smallLineCache.pop();
+}
+
+void Deallocator::deallocateMediumLine(MediumLine* line)
+{
+    if (m_mediumLineCache.size() == m_mediumLineCache.capacity())
+        return PerProcess<Heap>::getFastCase()->deallocateMediumLine(line);
+
+    m_mediumLineCache.push(line);
+}
+
+MediumLine* Deallocator::allocateMediumLine()
+{
+    if (!m_mediumLineCache.size()) {
+        std::lock_guard<Mutex> lock(PerProcess<Heap>::mutex());
+        Heap* heap = PerProcess<Heap>::getFastCase();
+
+        while (m_mediumLineCache.size() != m_mediumLineCache.capacity())
+            m_mediumLineCache.push(heap->allocateMediumLine(lock));
+    }
+
+    return m_mediumLineCache.pop();
+}
+
+} // namespace bmalloc
diff --git a/Source/bmalloc/bmalloc/Deallocator.h b/Source/bmalloc/bmalloc/Deallocator.h
new file mode 100644 (file)
index 0000000..9887f81
--- /dev/null
@@ -0,0 +1,85 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef Deallocator_h
+#define Deallocator_h
+
+#include "FixedVector.h"
+#include "MediumLine.h"
+#include "Sizes.h"
+#include "SmallLine.h"
+
+namespace bmalloc {
+
+// Per-cache object deallocator.
+
+class Deallocator {
+public:
+    Deallocator();
+    ~Deallocator();
+
+    void deallocate(void*);
+    bool deallocateFastCase(void*);
+    void deallocateSlowCase(void*);
+
+    void deallocateSmallLine(SmallLine*);
+    SmallLine* allocateSmallLine();
+
+    void deallocateMediumLine(MediumLine*);
+    MediumLine* allocateMediumLine();
+
+private:
+    void deallocateLarge(void*);
+    void deallocateXLarge(void*);
+    void processObjectLog();
+
+    FixedVector<void*, deallocatorLogCapacity> m_objectLog;
+    FixedVector<SmallLine*, smallLineCacheCapacity> m_smallLineCache;
+    FixedVector<MediumLine*, mediumLineCacheCapacity> m_mediumLineCache;
+};
+
+inline bool Deallocator::deallocateFastCase(void* object)
+{
+    if (!isSmallOrMedium(object))
+        return false;
+
+    ASSERT(object);
+
+    if (!(m_objectLog.size() % (m_objectLog.capacity() / 4)))
+        return false;
+
+    m_objectLog.push(object);
+    return true;
+}
+
+inline void Deallocator::deallocate(void* object)
+{
+    if (!deallocateFastCase(object))
+        deallocateSlowCase(object);
+}
+
+} // namespace bmalloc
+
+#endif // Deallocator_h
diff --git a/Source/bmalloc/bmalloc/EndTag.h b/Source/bmalloc/bmalloc/EndTag.h
new file mode 100644 (file)
index 0000000..9eae997
--- /dev/null
@@ -0,0 +1,47 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef EndTag_h
+#define EndTag_h
+
+#include "BoundaryTag.h"
+
+namespace bmalloc {
+
+class EndTag : public BoundaryTag {
+public:
+    EndTag& operator=(const BeginTag&);
+};
+
+inline EndTag& EndTag::operator=(const BeginTag& other)
+{
+    memcpy(this, &other, sizeof(BoundaryTag));
+    setEnd(true);
+    return *this;
+}
+
+} // namespace bmalloc
+
+#endif // EndTag_h
diff --git a/Source/bmalloc/bmalloc/FixedVector.h b/Source/bmalloc/bmalloc/FixedVector.h
new file mode 100644 (file)
index 0000000..b6ef049
--- /dev/null
@@ -0,0 +1,119 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef FixedVector_h
+#define FixedVector_h
+
+#include "BAssert.h"
+#include <array>
+#include <cstddef>
+#include <type_traits>
+
+namespace bmalloc {
+
+// A replacement for std::vector that uses a fixed-sized inline backing store.
+
+template<typename T, size_t Capacity>
+class FixedVector {
+    static_assert(std::is_trivially_destructible<T>::value, "FixedVector must have a trivial destructor.");
+public:
+    FixedVector(const FixedVector&) = delete;
+    FixedVector& operator=(const FixedVector&) = delete;
+
+    FixedVector();
+
+    const T* begin() const { return m_buffer.begin(); }
+    const T* end() const { return begin() + size(); }
+
+    size_t size() const { return m_size; }
+    size_t capacity() const { return Capacity; }
+    
+    T& operator[](size_t);
+
+    void push(const T&);
+    void push(const T*, const T*);
+    T pop();
+
+    void shrink(T*);
+    void shrink(size_t);
+
+    void clear() { shrink(0ul); }
+    bool isEmpty() { return !m_size; }
+
+private:
+    size_t m_size;
+    std::array<T, Capacity> m_buffer;
+};
+
+template<typename T, size_t Capacity>
+inline FixedVector<T, Capacity>::FixedVector()
+    : m_size(0)
+{
+}
+
+template<typename T, size_t Capacity>
+inline T& FixedVector<T, Capacity>::operator[](size_t i)
+{
+    ASSERT(i < m_size);
+    return m_buffer[i];
+}
+
+template<typename T, size_t Capacity>
+inline void FixedVector<T, Capacity>::push(const T& value)
+{
+    ASSERT(m_size < Capacity);
+    m_buffer[m_size++] = value;
+}
+
+template<typename T, size_t Capacity>
+inline void FixedVector<T, Capacity>::push(const T* begin, const T* end)
+{
+    for (const T* it = begin; it != end; ++it)
+        push(*it);
+}
+
+template<typename T, size_t Capacity>
+inline T FixedVector<T, Capacity>::pop()
+{
+    ASSERT(m_size);
+    return m_buffer[--m_size];
+}
+
+template<typename T, size_t Capacity>
+inline void FixedVector<T, Capacity>::shrink(size_t size)
+{
+    ASSERT(size <= m_size);
+    m_size = size;
+}
+
+template<typename T, size_t Capacity>
+inline void FixedVector<T, Capacity>::shrink(T* end)
+{
+    shrink(end - begin());
+}
+
+} // namespace bmalloc
+
+#endif // FixedVector_h
diff --git a/Source/bmalloc/bmalloc/Heap.cpp b/Source/bmalloc/bmalloc/Heap.cpp
new file mode 100644 (file)
index 0000000..85884c2
--- /dev/null
@@ -0,0 +1,202 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "BoundaryTagInlines.h"
+#include "Heap.h"
+#include "LargeChunk.h"
+#include "Line.h"
+#include "MediumChunk.h"
+#include "Page.h"
+#include "PerProcess.h"
+#include "SmallChunk.h"
+#include "XLargeChunk.h"
+#include <thread>
+
+namespace bmalloc {
+
+static inline void sleep(std::unique_lock<Mutex>& lock, std::chrono::milliseconds duration)
+{
+    lock.unlock();
+    std::this_thread::sleep_for(duration);
+    lock.lock();
+}
+
+Heap::Heap(std::lock_guard<Mutex>&)
+    : m_scavenger(*this, &Heap::concurrentScavenge)
+    , m_isAllocatingPages(false)
+{
+}
+
+void Heap::concurrentScavenge()
+{
+    std::unique_lock<Mutex> lock(PerProcess<Heap>::mutex());
+    scavengeSmallPages(lock);
+    scavengeMediumPages(lock);
+    scavengeLargeRanges(lock);
+
+    sleep(lock, scavengeSleepDuration);
+}
+
+void Heap::scavengeSmallPages(std::unique_lock<Mutex>& lock)
+{
+    while (1) {
+        if (m_isAllocatingPages) {
+            m_isAllocatingPages = false;
+
+            sleep(lock, scavengeSleepDuration);
+            continue;
+        }
+
+        if (!m_smallPages.size())
+            return;
+        m_vmHeap.deallocateSmallPage(lock, m_smallPages.pop());
+    }
+}
+
+void Heap::scavengeMediumPages(std::unique_lock<Mutex>& lock)
+{
+    while (1) {
+        if (m_isAllocatingPages) {
+            m_isAllocatingPages = false;
+
+            sleep(lock, scavengeSleepDuration);
+            continue;
+        }
+
+        if (!m_mediumPages.size())
+            return;
+        m_vmHeap.deallocateMediumPage(lock, m_mediumPages.pop());
+    }
+}
+
+void Heap::scavengeLargeRanges(std::unique_lock<Mutex>& lock)
+{
+    while (1) {
+        if (m_isAllocatingPages) {
+            m_isAllocatingPages = false;
+
+            sleep(lock, scavengeSleepDuration);
+            continue;
+        }
+
+        Range range = m_largeRanges.takeGreedy(vmPageSize);
+        if (!range)
+            return;
+        m_vmHeap.deallocateLargeRange(lock, range);
+    }
+}
+
+SmallLine* Heap::allocateSmallLineSlowCase(std::lock_guard<Mutex>& lock)
+{
+    m_isAllocatingPages = true;
+
+    SmallPage* page = [this]() {
+        if (m_smallPages.size())
+            return m_smallPages.pop();
+        
+        SmallPage* page = m_vmHeap.allocateSmallPage();
+        vmAllocatePhysicalPages(page->begin()->begin(), vmPageSize);
+        return page;
+    }();
+
+    SmallLine* line = page->begin();
+    for (auto it = line + 1; it != page->end(); ++it)
+        m_smallLines.push(it);
+
+    page->ref(lock);
+    return line;
+}
+
+MediumLine* Heap::allocateMediumLineSlowCase(std::lock_guard<Mutex>& lock)
+{
+    m_isAllocatingPages = true;
+
+    MediumPage* page = [this]() {
+        if (m_mediumPages.size())
+            return m_mediumPages.pop();
+        
+        MediumPage* page = m_vmHeap.allocateMediumPage();
+        vmAllocatePhysicalPages(page->begin()->begin(), vmPageSize);
+        return page;
+    }();
+
+    MediumLine* line = page->begin();
+    for (auto it = line + 1; it != page->end(); ++it)
+        m_mediumLines.push(it);
+
+    page->ref(lock);
+    return line;
+}
+
+void* Heap::allocateXLarge(std::lock_guard<Mutex>&, size_t size)
+{
+    XLargeChunk* chunk = XLargeChunk::create(size);
+
+    BeginTag* beginTag = LargeChunk::beginTag(chunk->begin());
+    beginTag->setXLarge();
+    beginTag->setFree(false);
+    beginTag->setHasPhysicalPages(true);
+    
+    return chunk->begin();
+}
+
+void Heap::deallocateXLarge(std::lock_guard<Mutex>&, void* object)
+{
+    XLargeChunk* chunk = XLargeChunk::get(object);
+    XLargeChunk::destroy(chunk);
+}
+
+void* Heap::allocateLarge(std::lock_guard<Mutex>& lock, size_t size)
+{
+    ASSERT(size <= largeMax);
+    ASSERT(size >= largeMin);
+    
+    m_isAllocatingPages = true;
+
+    Range range = m_largeRanges.take(size);
+    if (!range)
+        range = m_vmHeap.allocateLargeRange(size);
+    
+    Range leftover;
+    bool hasPhysicalPages;
+    BoundaryTag::allocate(size, range, leftover, hasPhysicalPages);
+
+    if (!!leftover)
+        m_largeRanges.insert(leftover);
+    
+    if (!hasPhysicalPages)
+        vmAllocatePhysicalPagesSloppy(range.begin(), range.size());
+
+    return range.begin();
+}
+
+void Heap::deallocateLarge(std::lock_guard<Mutex>& lock, void* object)
+{
+    Range range = BoundaryTag::deallocate(object);
+    m_largeRanges.insert(range);
+    m_scavenger.run();
+}
+
+} // namespace bmalloc
diff --git a/Source/bmalloc/bmalloc/Heap.h b/Source/bmalloc/bmalloc/Heap.h
new file mode 100644 (file)
index 0000000..ec79674
--- /dev/null
@@ -0,0 +1,149 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef Heap_h
+#define Heap_h
+
+#include "FixedVector.h"
+#include "VMHeap.h"
+#include "MediumLine.h"
+#include "Mutex.h"
+#include "SmallPage.h"
+#include "MediumChunk.h"
+#include "MediumPage.h"
+#include "SegregatedFreeList.h"
+#include "SmallChunk.h"
+#include "SmallLine.h"
+#include "Vector.h"
+#include <array>
+#include <mutex>
+
+namespace bmalloc {
+
+class BeginTag;
+class EndTag;
+
+class Heap {
+public:
+    Heap(std::lock_guard<Mutex>&);
+    
+    SmallLine* allocateSmallLine(std::lock_guard<Mutex>&);
+    void deallocateSmallLine(SmallLine*);
+
+    MediumLine* allocateMediumLine(std::lock_guard<Mutex>&);
+    void deallocateMediumLine(MediumLine*);
+    
+    void* allocateLarge(std::lock_guard<Mutex>&, size_t);
+    void deallocateLarge(std::lock_guard<Mutex>&, void*);
+
+    void* allocateXLarge(std::lock_guard<Mutex>&, size_t);
+    void deallocateXLarge(std::lock_guard<Mutex>&, void*);
+
+private:
+    ~Heap() = delete;
+
+    SmallLine* allocateSmallLineSlowCase(std::lock_guard<Mutex>&);
+    MediumLine* allocateMediumLineSlowCase(std::lock_guard<Mutex>&);
+
+    void* allocateLarge(Range, size_t);
+    Range allocateLargeChunk();
+
+    void splitLarge(BeginTag*, size_t, EndTag*&, Range&);
+    void mergeLarge(BeginTag*&, EndTag*&, Range&);
+    void mergeLargeLeft(EndTag*&, BeginTag*&, Range&, bool& hasPhysicalPages);
+    void mergeLargeRight(EndTag*&, BeginTag*&, Range&, bool& hasPhysicalPages);
+    
+    void concurrentScavenge();
+    void scavengeSmallPages(std::unique_lock<Mutex>&);
+    void scavengeMediumPages(std::unique_lock<Mutex>&);
+    void scavengeLargeRanges(std::unique_lock<Mutex>&);
+
+    Vector<SmallLine*> m_smallLines;
+    Vector<MediumLine*> m_mediumLines;
+
+    Vector<SmallPage*> m_smallPages;
+    Vector<MediumPage*> m_mediumPages;
+
+    SegregatedFreeList m_largeRanges;
+
+    bool m_isAllocatingPages;
+
+    VMHeap m_vmHeap;
+    AsyncTask<Heap, decltype(&Heap::concurrentScavenge)> m_scavenger;
+};
+
+inline void Heap::deallocateSmallLine(SmallLine* line)
+{
+    SmallPage* page = SmallPage::get(line);
+    if (page->deref()) {
+        m_smallPages.push(page);
+        m_scavenger.run();
+        return;
+    }
+    m_smallLines.push(line);
+}
+
+inline SmallLine* Heap::allocateSmallLine(std::lock_guard<Mutex>& lock)
+{
+    while (m_smallLines.size()) {
+        SmallLine* line = m_smallLines.pop();
+        SmallPage* page = SmallPage::get(line);
+        if (!page->refCount(lock)) // The line was promoted to the small pages list.
+            continue;
+        page->ref(lock);
+        return line;
+    }
+
+    return allocateSmallLineSlowCase(lock);
+}
+
+inline void Heap::deallocateMediumLine(MediumLine* line)
+{
+    MediumPage* page = MediumPage::get(line);
+    if (page->deref()) {
+        m_mediumPages.push(page);
+        m_scavenger.run();
+        return;
+    }
+    m_mediumLines.push(line);
+}
+
+inline MediumLine* Heap::allocateMediumLine(std::lock_guard<Mutex>& lock)
+{
+    while (m_mediumLines.size()) {
+        MediumLine* line = m_mediumLines.pop();
+        MediumPage* page = MediumPage::get(line);
+        if (!page->refCount(lock)) // The line was promoted to the medium pages list.
+            continue;
+        page->ref(lock);
+        return line;
+    }
+
+    return allocateMediumLineSlowCase(lock);
+}
+
+} // namespace bmalloc
+
+#endif // Heap_h
diff --git a/Source/bmalloc/bmalloc/Inline.h b/Source/bmalloc/bmalloc/Inline.h
new file mode 100644 (file)
index 0000000..c005417
--- /dev/null
@@ -0,0 +1,33 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef Inline_h
+#define Inline_h
+
+#define INLINE __attribute__((always_inline)) inline
+
+#define NO_INLINE __attribute__((noinline))
+
+#endif // Inline_h
diff --git a/Source/bmalloc/bmalloc/LargeChunk.h b/Source/bmalloc/bmalloc/LargeChunk.h
new file mode 100644 (file)
index 0000000..4b01d1a
--- /dev/null
@@ -0,0 +1,107 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef LargeChunk_h
+#define LargeChunk_h
+
+#include "BeginTag.h"
+#include "EndTag.h"
+#include "ObjectType.h"
+#include "Sizes.h"
+#include "VMAllocate.h"
+
+namespace bmalloc {
+
+class LargeChunk {
+public:
+    static LargeChunk* create();
+    static LargeChunk* get(void*);
+
+    static BeginTag* beginTag(void*);
+    static EndTag* endTag(void*, size_t);
+
+    char* begin() { return m_memory; }
+    char* end() { return reinterpret_cast<char*>(this) + largeChunkSize; }
+
+private:
+     // Round up to ensure 2 dummy boundary tags -- for the left and right sentinels.
+     static const size_t boundaryTagCount = max(2 * largeMin / sizeof(BoundaryTag), largeChunkSize / largeMin); 
+
+    // Our metadata layout includes a left and right edge sentinel.
+    // Metadata takes up enough space to leave at least the first two
+    // boundary tag slots unused.
+    //
+    //      So, boundary tag space looks like this:
+    //
+    //          [OOXXXXX...]
+    //
+    //      And BoundaryTag::get subtracts one, producing:
+    //
+    //          [OXXXXX...O].
+    //
+    // We use the X's for boundary tags and the O's for edge sentinels.
+
+    BoundaryTag m_boundaryTags[boundaryTagCount];
+    alignas(largeAlignment) char m_memory[];
+};
+
+inline LargeChunk* LargeChunk::create()
+{
+    size_t vmSize = bmalloc::vmSize(largeChunkSize);
+    std::pair<void*, Range> result = vmAllocate(vmSize, superChunkSize, largeChunkOffset);
+    return new (result.first) LargeChunk;
+}
+
+inline LargeChunk* LargeChunk::get(void* object)
+{
+    ASSERT(!isSmallOrMedium(object));
+    return static_cast<LargeChunk*>(mask(object, largeChunkMask));
+}
+
+inline BeginTag* LargeChunk::beginTag(void* object)
+{
+    LargeChunk* chunk = get(object);
+    size_t boundaryTagNumber = (static_cast<char*>(object) - reinterpret_cast<char*>(chunk)) / largeMin - 1; // - 1 to offset from the right sentinel.
+    return static_cast<BeginTag*>(&chunk->m_boundaryTags[boundaryTagNumber]);
+}
+
+inline EndTag* LargeChunk::endTag(void* object, size_t size)
+{
+    ASSERT(!isSmallOrMedium(object));
+
+    LargeChunk* chunk = get(object);
+    char* end = static_cast<char*>(object) + size;
+
+    // We subtract largeMin before computing the end pointer's boundary tag. An
+    // object's size need not be an even multiple of largeMin. Subtracting
+    // largeMin rounds down to the last boundary tag prior to our neighbor.
+
+    size_t boundaryTagNumber = (end - largeMin - reinterpret_cast<char*>(chunk)) / largeMin - 1; // - 1 to offset from the right sentinel.
+    return static_cast<EndTag*>(&chunk->m_boundaryTags[boundaryTagNumber]);
+}
+
+}; // namespace bmalloc
+
+#endif // LargeChunk
diff --git a/Source/bmalloc/bmalloc/Line.h b/Source/bmalloc/bmalloc/Line.h
new file mode 100644 (file)
index 0000000..bd1a70d
--- /dev/null
@@ -0,0 +1,100 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef Line_h
+#define Line_h
+
+#include "BAssert.h"
+#include "Mutex.h"
+#include "ObjectType.h"
+#include <mutex>
+
+namespace bmalloc {
+
+template<class Traits>
+class Line {
+public:
+    typedef typename Traits::Chunk Chunk;
+    static const size_t minimumObjectSize = Traits::minimumObjectSize;
+    static const size_t lineSize = Traits::lineSize;
+    
+    static const unsigned char maxRefCount = std::numeric_limits<unsigned char>::max();
+    static_assert(lineSize / minimumObjectSize < maxRefCount, "maximum object count must fit in Line");
+
+    static Line* get(void*);
+
+    void concurrentRef(unsigned char = 1);
+    bool deref(unsigned char = 1);
+    
+    char* begin();
+    char* end();
+
+private:
+    unsigned char m_refCount;
+};
+
+template<class Traits>
+inline auto Line<Traits>::get(void* object) -> Line*
+{
+    ASSERT(isSmallOrMedium(object));
+    Chunk* chunk = Chunk::get(object);
+    size_t lineNumber = (reinterpret_cast<char*>(object) - reinterpret_cast<char*>(chunk)) / lineSize;
+    return &chunk->lines()[lineNumber];
+}
+
+template<class Traits>
+inline char* Line<Traits>::begin()
+{
+    Chunk* chunk = Chunk::get(this);
+    size_t lineNumber = this - chunk->lines();
+    size_t offset = lineNumber * lineSize;
+    return &reinterpret_cast<char*>(chunk)[offset];
+}
+
+template<class Traits>
+inline char* Line<Traits>::end()
+{
+    return begin() + lineSize;
+}
+
+template<class Traits>
+inline void Line<Traits>::concurrentRef(unsigned char count)
+{
+    ASSERT(!m_refCount); // Up-ref from zero can be lock-free because there are no other clients.
+    ASSERT(count <= maxRefCount);
+    m_refCount = count;
+}
+
+template<class Traits>
+inline bool Line<Traits>::deref(unsigned char count)
+{
+    ASSERT(count <= m_refCount);
+    m_refCount -= count;
+    return !m_refCount;
+}
+
+} // namespace bmalloc
+
+#endif // Line_h
diff --git a/Source/bmalloc/bmalloc/MediumAllocator.h b/Source/bmalloc/bmalloc/MediumAllocator.h
new file mode 100644 (file)
index 0000000..a47b1ed
--- /dev/null
@@ -0,0 +1,106 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef MediumAllocator_h
+#define MediumAllocator_h
+
+#include "BAssert.h"
+#include "MediumChunk.h"
+#include "MediumLine.h"
+
+namespace bmalloc {
+
+// Helper object for allocating medium objects.
+
+class MediumAllocator {
+public:
+    MediumAllocator();
+
+    bool isNull() { return !m_end; }
+    MediumLine* line();
+
+    void* allocate(size_t);
+    bool allocate(size_t, void*&);
+
+    unsigned char derefCount();
+    void refill(MediumLine*);
+
+private:
+    char* m_end;
+    size_t m_remaining;
+    size_t m_objectCount;
+};
+
+inline MediumAllocator::MediumAllocator()
+    : m_end()
+    , m_remaining()
+    , m_objectCount()
+{
+}
+
+inline MediumLine* MediumAllocator::line()
+{
+    return MediumLine::get(m_end - 1);
+}
+
+inline void* MediumAllocator::allocate(size_t size)
+{
+    ASSERT(size <= m_remaining);
+    ASSERT(size == roundUpToMultipleOf<alignment>(size));
+    ASSERT(size >= MediumLine::minimumObjectSize);
+
+    m_remaining -= size;
+    void* object = m_end - m_remaining - size;
+    ASSERT(isSmallOrMedium(object) && !isSmall(object));
+
+    ++m_objectCount;
+    return object;
+}
+
+inline bool MediumAllocator::allocate(size_t size, void*& object)
+{
+    if (size > m_remaining)
+        return false;
+
+    object = allocate(size);
+    return true;
+}
+
+inline unsigned char MediumAllocator::derefCount()
+{
+    return MediumLine::maxRefCount - m_objectCount;
+}
+
+inline void MediumAllocator::refill(MediumLine* line)
+{
+    line->concurrentRef(MediumLine::maxRefCount);
+    m_end = line->end();
+    m_remaining = mediumLineSize;
+    m_objectCount = 0;
+}
+
+} // namespace bmalloc
+
+#endif // MediumAllocator_h
diff --git a/Source/bmalloc/bmalloc/MediumChunk.h b/Source/bmalloc/bmalloc/MediumChunk.h
new file mode 100644 (file)
index 0000000..b165e57
--- /dev/null
@@ -0,0 +1,40 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef MediumChunk_h
+#define MediumChunk_h
+
+#include "Chunk.h"
+#include "MediumLine.h"
+#include "MediumPage.h"
+#include "MediumTraits.h"
+
+namespace bmalloc {
+
+typedef Chunk<MediumTraits> MediumChunk;
+
+}; // namespace bmalloc
+
+#endif // MediumChunk
diff --git a/Source/bmalloc/bmalloc/MediumLine.h b/Source/bmalloc/bmalloc/MediumLine.h
new file mode 100644 (file)
index 0000000..cb20d43
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef MediumLine_h
+#define MediumLine_h
+
+#include "Line.h"
+#include "MediumTraits.h"
+
+namespace bmalloc {
+
+typedef Line<MediumTraits> MediumLine;
+
+} // namespace bmalloc
+
+#endif // MediumLine_h
diff --git a/Source/bmalloc/bmalloc/MediumPage.h b/Source/bmalloc/bmalloc/MediumPage.h
new file mode 100644 (file)
index 0000000..893cfe6
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef MediumPage_h
+#define MediumPage_h
+
+#include "MediumTraits.h"
+#include "Page.h"
+
+namespace bmalloc {
+
+typedef Page<MediumTraits> MediumPage;
+
+} // namespace bmalloc
+
+#endif // MediumPage_h
diff --git a/Source/bmalloc/bmalloc/MediumTraits.h b/Source/bmalloc/bmalloc/MediumTraits.h
new file mode 100644 (file)
index 0000000..bbce01a
--- /dev/null
@@ -0,0 +1,52 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef MediumTraits_h
+#define MediumTraits_h
+
+#include "Sizes.h"
+#include "VMAllocate.h"
+
+namespace bmalloc {
+
+template<class Traits> class Chunk;
+template<class Traits> class Line;
+template<class Traits> class Page;
+
+struct MediumTraits {
+    typedef Chunk<MediumTraits> Chunk;
+    typedef Line<MediumTraits> Line;
+    typedef Page<MediumTraits> Page;
+
+    static const size_t lineSize = mediumLineSize;
+    static const size_t minimumObjectSize = smallMax + alignment;
+    static const size_t chunkSize = mediumChunkSize;
+    static const size_t chunkOffset = mediumChunkOffset;
+    static const uintptr_t chunkMask = mediumChunkMask;
+};
+
+} // namespace bmalloc
+
+#endif // MediumTraits_h
diff --git a/Source/bmalloc/bmalloc/Mutex.cpp b/Source/bmalloc/bmalloc/Mutex.cpp
new file mode 100644 (file)
index 0000000..0a4f153
--- /dev/null
@@ -0,0 +1,37 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "Mutex.h"
+#include <thread>
+
+namespace bmalloc {
+
+void Mutex::lockSlowCase()
+{
+    while (!try_lock())
+        std::this_thread::yield();
+}
+
+} // namespace bmalloc
diff --git a/Source/bmalloc/bmalloc/Mutex.h b/Source/bmalloc/bmalloc/Mutex.h
new file mode 100644 (file)
index 0000000..2fef5b9
--- /dev/null
@@ -0,0 +1,72 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef Mutex_h
+#define Mutex_h
+
+#include <atomic>
+
+// A replacement for std::mutex that does not require an exit-time destructor.
+
+namespace bmalloc {
+
+class Mutex {
+public:
+    Mutex();
+
+    void lock();
+    bool try_lock();
+    void unlock();
+    
+private:
+    void lockSlowCase();
+
+    std::atomic_flag m_flag;
+};
+
+inline Mutex::Mutex()
+    : m_flag(ATOMIC_FLAG_INIT)
+{
+}
+
+inline bool Mutex::try_lock()
+{
+    return !m_flag.test_and_set(std::memory_order_acquire);
+}
+
+inline void Mutex::lock()
+{
+    if (!try_lock())
+        lockSlowCase();
+}
+
+inline void Mutex::unlock()
+{
+    m_flag.clear(std::memory_order_release);
+}
+
+} // namespace bmalloc
+
+#endif // Mutex_h
diff --git a/Source/bmalloc/bmalloc/ObjectType.cpp b/Source/bmalloc/bmalloc/ObjectType.cpp
new file mode 100644 (file)
index 0000000..df8c900
--- /dev/null
@@ -0,0 +1,45 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "LargeChunk.h"
+#include "ObjectType.h"
+
+namespace bmalloc {
+
+ObjectType objectType(void* object)
+{
+    if (isSmallOrMedium(object)) {
+        if (isSmall(object))
+            return Small;
+        return Medium;
+    }
+    
+    BeginTag* beginTag = LargeChunk::beginTag(object);
+    if (!beginTag->isXLarge())
+        return Large;
+    return XLarge;
+}
+
+} // namespace bmalloc
diff --git a/Source/bmalloc/bmalloc/ObjectType.h b/Source/bmalloc/bmalloc/ObjectType.h
new file mode 100644 (file)
index 0000000..bce8aee
--- /dev/null
@@ -0,0 +1,51 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef ObjectType_h
+#define ObjectType_h
+
+#include "BAssert.h"
+#include "Sizes.h"
+
+namespace bmalloc {
+
+enum ObjectType { Small, Medium, Large, XLarge };
+
+ObjectType objectType(void*);
+
+inline bool isSmallOrMedium(void* object)
+{
+    return test(object, smallOrMediumTypeMask);
+}
+
+inline bool isSmall(void* smallOrMedium)
+{
+    ASSERT(isSmallOrMedium(smallOrMedium));
+    return test(smallOrMedium, smallOrMediumSmallTypeMask);
+}
+
+} // namespace bmalloc
+
+#endif // ObjectType_h
diff --git a/Source/bmalloc/bmalloc/Page.h b/Source/bmalloc/bmalloc/Page.h
new file mode 100644 (file)
index 0000000..485ad01
--- /dev/null
@@ -0,0 +1,106 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef Page_h
+#define Page_h
+
+#include "BAssert.h"
+#include "Mutex.h"
+#include "VMAllocate.h"
+#include <mutex>
+
+namespace bmalloc {
+
+template<typename Traits>
+class Page {
+public:
+    typedef typename Traits::Chunk Chunk;
+    typedef typename Traits::Line Line;
+    static const size_t lineSize = Traits::lineSize;
+
+    static const unsigned char maxRefCount = std::numeric_limits<unsigned char>::max();
+    static_assert(vmPageSize / lineSize < maxRefCount, "maximum line count must fit in Page");
+    
+    static Page* get(Line*);
+
+    void ref(std::lock_guard<Mutex>&);
+    bool deref();
+    unsigned refCount(std::lock_guard<Mutex>&);
+    
+    Line* begin();
+    Line* end();
+
+private:
+    unsigned char m_refCount;
+};
+
+template<typename Traits>
+inline void Page<Traits>::ref(std::lock_guard<Mutex>&)
+{
+    ASSERT(m_refCount < maxRefCount);
+    ++m_refCount;
+}
+
+template<typename Traits>
+inline bool Page<Traits>::deref()
+{
+    ASSERT(m_refCount);
+    --m_refCount;
+    return !m_refCount;
+}
+
+template<typename Traits>
+inline unsigned Page<Traits>::refCount(std::lock_guard<Mutex>&)
+{
+    return m_refCount;
+}
+
+template<typename Traits>
+inline auto Page<Traits>::get(Line* line) -> Page*
+{
+    Chunk* chunk = Chunk::get(line);
+    size_t lineNumber = line - chunk->lines();
+    size_t pageNumber = lineNumber * lineSize / vmPageSize;
+    return &chunk->pages()[pageNumber];
+}
+
+template<typename Traits>
+inline auto Page<Traits>::begin() -> Line*
+{
+    Chunk* chunk = Chunk::get(this);
+    size_t pageNumber = this - chunk->pages();
+    size_t lineNumber = pageNumber * vmPageSize / lineSize;
+    return &chunk->lines()[lineNumber];
+}
+
+template<typename Traits>
+inline auto Page<Traits>::end() -> Line*
+{
+    return begin() + vmPageSize / lineSize;
+}
+
+} // namespace bmalloc
+
+#endif // Page_h
diff --git a/Source/bmalloc/bmalloc/PerProcess.h b/Source/bmalloc/bmalloc/PerProcess.h
new file mode 100644 (file)
index 0000000..295706c
--- /dev/null
@@ -0,0 +1,110 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef PerProcess_h
+#define PerProcess_h
+
+#include "Inline.h"
+#include "Mutex.h"
+#include "Sizes.h"
+#include <mutex>
+
+namespace bmalloc {
+
+// Usage:
+//     Object* object = PerProcess<Object>::get();
+//     x = object->field->field;
+//
+// Object will be instantiated only once, even in the face of concurrency.
+//
+// NOTE: If you observe global side-effects of the Object constructor, be
+// sure to lock the Object mutex. For example:
+//
+// Object() : m_field(...) { globalFlag = true }
+//
+// Object* object = PerProcess<Object>::get();
+// x = object->m_field; // OK
+// if (gobalFlag) { ... } // Undefined behavior.
+//
+// std::lock_guard<Mutex> lock(PerProcess<Object>::mutex());
+// Object* object = PerProcess<Object>::get(lock);
+// if (gobalFlag) { ... } // OK.
+
+template<typename T>
+class PerProcess {
+public:
+    static T* get();
+    static T* getFastCase();
+    
+    static Mutex& mutex() { return s_mutex; }
+
+private:
+    static T* getSlowCase();
+
+    static std::atomic<T*> s_object;
+    static Mutex s_mutex;
+
+    typedef typename std::aligned_storage<sizeof(T), std::alignment_of<T>::value>::type Memory;
+    static Memory s_memory;
+};
+
+template<typename T>
+INLINE T* PerProcess<T>::getFastCase()
+{
+    return s_object.load(std::memory_order_consume);
+}
+
+template<typename T>
+INLINE T* PerProcess<T>::get()
+{
+    T* object = getFastCase();
+    if (!object)
+        return getSlowCase();
+    return object;
+}
+
+template<typename T>
+NO_INLINE T* PerProcess<T>::getSlowCase()
+{
+    std::lock_guard<Mutex> lock(s_mutex);
+    if (!s_object.load(std::memory_order_consume)) {
+        T* t = new (&s_memory) T(lock);
+        s_object.store(t, std::memory_order_release);
+    }
+    return s_object.load(std::memory_order_consume);
+}
+
+template<typename T>
+std::atomic<T*> PerProcess<T>::s_object;
+
+template<typename T>
+Mutex PerProcess<T>::s_mutex;
+
+template<typename T>
+typename PerProcess<T>::Memory PerProcess<T>::s_memory;
+
+} // namespace bmalloc
+
+#endif // PerProcess_h
diff --git a/Source/bmalloc/bmalloc/PerThread.h b/Source/bmalloc/bmalloc/PerThread.h
new file mode 100644 (file)
index 0000000..7079fd1
--- /dev/null
@@ -0,0 +1,128 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef PerThread_h
+#define PerThread_h
+
+#include "Inline.h"
+#include <mutex>
+#include <pthread.h>
+#if defined(__has_include) && __has_include(<System/pthread_machdep.h>)
+#include <System/pthread_machdep.h>
+#endif
+
+namespace bmalloc {
+
+// Usage:
+//     Object* object = PerThread<Object>::get();
+
+template<typename T>
+class PerThread {
+public:
+    static T* get();
+    static T* getFastCase();
+    static T* getSlowCase();
+
+private:
+    static void destructor(void*);
+};
+
+class Cache;
+
+template<typename T> struct PerThreadStorage;
+
+#if defined(__has_include) && __has_include(<System/pthread_machdep.h>)
+
+// For now, we only support PerThread<Cache>. We can expand to other types by
+// using more keys.
+
+template<> struct PerThreadStorage<Cache> {
+    static const pthread_key_t key = __PTK_FRAMEWORK_JAVASCRIPTCORE_KEY0;
+    static void* get() { return _pthread_getspecific_direct(key); }
+    static void init(void* object, void (*destructor)(void*))
+    {
+        _pthread_setspecific_direct(key, object);
+        pthread_key_init_np(key, destructor);
+    }
+};
+
+#else
+
+template<typename T> struct PerThreadStorage {
+    static __thread void* object;
+    static pthread_key_t key;
+    static std::once_flag onceFlag;
+
+    static void* get() { return object; }
+    static void init(void* object, void (*destructor)(void*))
+    {
+        std::call_once(onceFlag, [destructor]() {
+            pthread_key_create(&key, destructor);
+        });
+        pthread_setspecific(key, object);
+        PerThreadStorage<Cache>::object = object;
+    }
+};
+
+template<typename T> __thread void* PerThreadStorage<T>::object;
+template<typename T> pthread_key_t PerThreadStorage<T>::key;
+template<typename T> std::once_flag PerThreadStorage<T>::onceFlag;
+
+#endif // defined(__has_include) && __has_include(<System/pthread_machdep.h>)
+
+template<typename T>
+INLINE T* PerThread<T>::getFastCase()
+{
+    return static_cast<T*>(PerThreadStorage<T>::get());
+}
+
+template<typename T>
+inline T* PerThread<T>::get()
+{
+    T* t = getFastCase();
+    if (!t)
+        return getSlowCase();
+    return t;
+}
+
+template<typename T>
+void PerThread<T>::destructor(void* p)
+{
+    T* t = static_cast<T*>(p);
+    delete t;
+}
+
+template<typename T>
+T* PerThread<T>::getSlowCase()
+{
+    ASSERT(!getFastCase());
+    T* t = new T;
+    PerThreadStorage<T>::init(t, destructor);
+    return t;
+}
+
+} // namespace bmalloc
+
+#endif // PerThread_h
diff --git a/Source/bmalloc/bmalloc/Range.h b/Source/bmalloc/bmalloc/Range.h
new file mode 100644 (file)
index 0000000..83d14da
--- /dev/null
@@ -0,0 +1,61 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef Range_h
+#define Range_h
+
+#include <stddef.h>
+
+namespace bmalloc {
+
+class Range {
+public:
+    Range()
+        : m_begin(0)
+        , m_size(0)
+    {
+    }
+
+    Range(void* start, size_t size)
+        : m_begin(static_cast<char*>(start))
+        , m_size(size)
+    {
+    }
+
+    char* begin() const { return m_begin; }
+    char* end() const { return m_begin + m_size; }
+    size_t size() const { return m_size; }
+    
+    bool operator!() const { return !m_size; }
+    bool operator<(const Range& other) const { return m_begin < other.m_begin; }
+
+private:
+    char* m_begin;
+    size_t m_size;
+};
+
+} // namespace bmalloc
+
+#endif // Range_h
diff --git a/Source/bmalloc/bmalloc/SegregatedFreeList.cpp b/Source/bmalloc/bmalloc/SegregatedFreeList.cpp
new file mode 100644 (file)
index 0000000..fe0ec85
--- /dev/null
@@ -0,0 +1,134 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "BeginTag.h"
+#include "LargeChunk.h"
+#include "SegregatedFreeList.h"
+#include "Vector.h"
+
+namespace bmalloc {
+
+SegregatedFreeList::SegregatedFreeList()
+{
+    ASSERT(&select(largeMax) - m_lists.begin() == m_lists.size() - 1);
+}
+
+void SegregatedFreeList::insert(const Range& range)
+{
+IF_DEBUG(
+    BeginTag* beginTag = LargeChunk::beginTag(range.begin());
+    ASSERT(beginTag->isInFreeList(range.size()));
+)
+
+    auto& list = select(range.size());
+    list.push(range);
+}
+
+Range SegregatedFreeList::takeGreedy(size_t minimum)
+{
+    for (size_t i = m_lists.size(); i-- > 0; ) {
+        Range range = takeGreedy(m_lists[i], minimum);
+        if (!range)
+            continue;
+
+        return range;
+    }
+    return Range();
+}
+
+Range SegregatedFreeList::takeGreedy(List& list, size_t minimum)
+{
+    for (size_t i = list.size(); i-- > 0; ) {
+        Range range = list[i];
+
+        // We don't eagerly remove items when we merge and/or split ranges,
+        // so we need to validate each free list entry before using it.
+        BeginTag* beginTag = LargeChunk::beginTag(range.begin());
+        if (!beginTag->isInFreeList(range.size())) {
+            list.pop(i);
+            continue;
+        }
+
+        if (range.size() < minimum)
+            continue;
+
+        list.pop(i);
+        return range;
+    }
+
+    return Range();
+}
+
+Range SegregatedFreeList::take(size_t minimum)
+{
+    for (auto* list = &select(minimum); list != m_lists.end(); ++list) {
+        Range range = take(*list, minimum);
+        if (!range)
+            continue;
+
+        return range;
+    }
+    return Range();
+}
+
+INLINE auto SegregatedFreeList::select(size_t size) -> List&
+{
+    size_t alignCount = (size - largeMin) / largeAlignment;
+    size_t result = 0;
+    while (alignCount) {
+        ++result;
+        alignCount >>= 1;
+    }
+    return m_lists[result];
+}
+
+INLINE Range SegregatedFreeList::take(List& list, size_t minimum)
+{
+    Range first;
+    size_t end = list.size() > segregatedFreeListSearchDepth ? list.size() - segregatedFreeListSearchDepth : 0;
+    for (size_t i = list.size(); i-- > end; ) {
+        Range range = list[i];
+
+        // We don't eagerly remove items when we merge and/or split ranges, so
+        // we need to validate each free list entry before using it.
+        BeginTag* beginTag = LargeChunk::beginTag(range.begin());
+        if (!beginTag->isInFreeList(range.size())) {
+            list.pop(i);
+            continue;
+        }
+
+        if (range.size() < minimum)
+            continue;
+
+        if (!!first && first < range)
+            continue;
+
+        first = range;
+    }
+    
+    return first;
+}
+
+} // namespace bmalloc
diff --git a/Source/bmalloc/bmalloc/SegregatedFreeList.h b/Source/bmalloc/bmalloc/SegregatedFreeList.h
new file mode 100644 (file)
index 0000000..be8ef95
--- /dev/null
@@ -0,0 +1,66 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef SegregatedFreeList_h
+#define SegregatedFreeList_h
+
+#include "Range.h"
+#include "Vector.h"
+#include <array>
+
+namespace bmalloc {
+
+class SegregatedFreeList {
+public:
+    SegregatedFreeList();
+
+    void insert(const Range&);
+
+    // Returns a reasonable fit for the provided size, or Range() if no fit
+    // is found. May return Range() spuriously if searching takes too long.
+    // Incrementally removes stale items from the free list while searching.
+    // Does not eagerly remove the returned range from the free list.
+    Range take(size_t);
+
+    // Returns an unreasonable fit for the provided size, or Range() if no fit
+    // is found. Never returns Range() spuriously.
+    // Incrementally removes stale items from the free list while searching.
+    // Eagerly removes the returned range from the free list.
+    Range takeGreedy(size_t);
+    
+private:
+    typedef Vector<Range> List;
+
+    List& select(size_t);
+
+    Range take(List&, size_t);
+    Range takeGreedy(List&, size_t);
+
+    std::array<List, 19> m_lists;
+};
+
+} // namespace bmalloc
+
+#endif // SegregatedFreeList_h
diff --git a/Source/bmalloc/bmalloc/Sizes.h b/Source/bmalloc/bmalloc/Sizes.h
new file mode 100644 (file)
index 0000000..035da50
--- /dev/null
@@ -0,0 +1,98 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef Sizes_h
+#define Sizes_h
+
+#include "Algorithm.h"
+#include <algorithm>
+#include <cstdint>
+#include <cstddef>
+#include <limits>
+#include <type_traits>
+#include <chrono>
+
+namespace bmalloc {
+
+// Repository for malloc sizing constants and calculations.
+
+namespace Sizes {
+    static const size_t kB = 1024;
+    static const size_t MB = kB * kB;
+
+    static const size_t alignment = 8;
+    static const size_t alignmentMask = alignment - 1ul;
+
+    static const size_t superChunkSize = 32 * MB;
+
+    static const size_t smallMax = 256;
+    static const size_t smallLineSize = 512;
+    static const size_t smallLineMask = ~(smallLineSize - 1ul);
+
+    static const size_t smallChunkSize = superChunkSize / 4;
+    static const size_t smallChunkOffset = superChunkSize * 3 / 4;
+    static const size_t smallChunkMask = ~(smallChunkSize - 1ul);
+
+    static const size_t mediumMax = 1024;
+    static const size_t mediumLineSize = 2048;
+    static const size_t mediumLineMask = ~(mediumLineSize - 1ul);
+
+    static const size_t mediumChunkSize = superChunkSize / 4;
+    static const size_t mediumChunkOffset = superChunkSize * 2 / 4;
+    static const size_t mediumChunkMask = ~(mediumChunkSize - 1ul);
+
+    static const size_t largeChunkSize = superChunkSize / 2;
+    static const size_t largeChunkOffset = 0;
+    static const size_t largeChunkMask = ~(largeChunkSize - 1ul);
+
+    static const size_t largeAlignment = 64;
+    static const size_t largeMax = largeChunkSize * 99 / 100; // Plenty of room for metadata.
+    static const size_t largeMin = 1024;
+
+    static const size_t segregatedFreeListSearchDepth = 16;
+
+    static const uintptr_t typeMask = (superChunkSize - 1) & ~((superChunkSize / 4) - 1); // 4 taggable chunks
+    static const uintptr_t smallType = (superChunkSize + smallChunkOffset) & typeMask;
+    static const uintptr_t mediumType = (superChunkSize + mediumChunkOffset) & typeMask;
+    static const uintptr_t largeTypeMask = ~(mediumType & smallType);
+    static const uintptr_t smallOrMediumTypeMask = mediumType & smallType;
+    static const uintptr_t smallOrMediumSmallTypeMask = smallType ^ mediumType; // Only valid if object is known to be small or medium.
+
+    static const size_t deallocatorLogCapacity = 256;
+
+    static const size_t smallLineCacheCapacity = 16;
+    static const size_t mediumLineCacheCapacity = 8;
+
+    static const size_t smallAllocatorLogCapacity = 16;
+    static const size_t mediumAllocatorLogCapacity = 8;
+    
+    static const std::chrono::milliseconds scavengeSleepDuration = std::chrono::milliseconds(512);
+};
+
+using namespace Sizes;
+
+} // namespace bmalloc
+
+#endif // Sizes_h
diff --git a/Source/bmalloc/bmalloc/SmallAllocator.h b/Source/bmalloc/bmalloc/SmallAllocator.h
new file mode 100644 (file)
index 0000000..ccd2abb
--- /dev/null
@@ -0,0 +1,112 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef SmallAllocator_h
+#define SmallAllocator_h
+
+#include "BAssert.h"
+#include "SmallChunk.h"
+#include "SmallLine.h"
+
+namespace bmalloc {
+
+// Helper object for allocating small objects.
+
+class SmallAllocator {
+public:
+    SmallAllocator();
+    SmallAllocator(size_t);
+    
+    bool isNull() { return !m_ptr; }
+    SmallLine* line();
+
+    bool canAllocate() { return !!m_remaining; }
+    void* allocate();
+
+    unsigned short objectCount();
+    unsigned char derefCount();
+    void refill(SmallLine*);
+
+private:
+    char* m_ptr;
+    unsigned short m_size;
+    unsigned char m_remaining;
+    unsigned char m_maxObjectCount;
+};
+
+inline SmallAllocator::SmallAllocator()
+    : m_ptr()
+    , m_size()
+    , m_remaining()
+    , m_maxObjectCount()
+{
+}
+
+inline SmallAllocator::SmallAllocator(size_t size)
+    : m_ptr()
+    , m_size(size)
+    , m_remaining()
+    , m_maxObjectCount(smallLineSize / size)
+{
+}
+
+inline SmallLine* SmallAllocator::line()
+{
+    return SmallLine::get(canAllocate() ? m_ptr : m_ptr - 1);
+}
+
+inline void* SmallAllocator::allocate()
+{
+    ASSERT(m_remaining);
+    ASSERT(m_size >= SmallLine::minimumObjectSize);
+
+    --m_remaining;
+    char* result = m_ptr;
+    m_ptr += m_size;
+    ASSERT(isSmall(result));
+    return result;
+}
+
+inline unsigned short SmallAllocator::objectCount()
+{
+    return m_maxObjectCount - m_remaining;
+}
+
+inline unsigned char SmallAllocator::derefCount()
+{
+    return SmallLine::maxRefCount - objectCount();
+}
+
+inline void SmallAllocator::refill(SmallLine* line)
+{
+    ASSERT(!canAllocate());
+    line->concurrentRef(SmallLine::maxRefCount);
+    m_ptr = line->begin();
+    m_remaining = m_maxObjectCount;
+}
+
+} // namespace bmalloc
+
+#endif // SmallAllocator_h
diff --git a/Source/bmalloc/bmalloc/SmallChunk.h b/Source/bmalloc/bmalloc/SmallChunk.h
new file mode 100644 (file)
index 0000000..689e342
--- /dev/null
@@ -0,0 +1,40 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef SmallChunk_h
+#define SmallChunk_h
+
+#include "Chunk.h"
+#include "SmallLine.h"
+#include "SmallPage.h"
+#include "SmallTraits.h"
+
+namespace bmalloc {
+
+typedef Chunk<SmallTraits> SmallChunk;
+
+}; // namespace bmalloc
+
+#endif // SmallChunk
diff --git a/Source/bmalloc/bmalloc/SmallLine.h b/Source/bmalloc/bmalloc/SmallLine.h
new file mode 100644 (file)
index 0000000..cdcaec9
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef SmallLine_h
+#define SmallLine_h
+
+#include "Line.h"
+#include "SmallTraits.h"
+
+namespace bmalloc {
+
+typedef Line<SmallTraits> SmallLine;
+
+} // namespace bmalloc
+
+#endif // SmallLine_h
diff --git a/Source/bmalloc/bmalloc/SmallPage.h b/Source/bmalloc/bmalloc/SmallPage.h
new file mode 100644 (file)
index 0000000..5f495ff
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef SmallPage_h
+#define SmallPage_h
+
+#include "SmallTraits.h"
+#include "Page.h"
+
+namespace bmalloc {
+
+typedef Page<SmallTraits> SmallPage;
+
+} // namespace bmalloc
+
+#endif // SmallPage_h
diff --git a/Source/bmalloc/bmalloc/SmallTraits.h b/Source/bmalloc/bmalloc/SmallTraits.h
new file mode 100644 (file)
index 0000000..e40c166
--- /dev/null
@@ -0,0 +1,51 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef SmallTraits_h
+#define SmallTraits_h
+
+#include "Sizes.h"
+
+namespace bmalloc {
+
+template<class Traits> class Chunk;
+template<class Traits> class Line;
+template<class Traits> class Page;
+
+struct SmallTraits {
+    typedef Chunk<SmallTraits> Chunk;
+    typedef Line<SmallTraits> Line;
+    typedef Page<SmallTraits> Page;
+
+    static const size_t lineSize = smallLineSize;
+    static const size_t minimumObjectSize = alignment;
+    static const size_t chunkSize = smallChunkSize;
+    static const size_t chunkOffset = smallChunkOffset;
+    static const uintptr_t chunkMask = smallChunkMask;
+};
+
+} // namespace bmalloc
+
+#endif // SmallTraits_h
diff --git a/Source/bmalloc/bmalloc/Syscall.h b/Source/bmalloc/bmalloc/Syscall.h
new file mode 100644 (file)
index 0000000..6462bfb
--- /dev/null
@@ -0,0 +1,36 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef Syscall_h
+#define Syscall_h
+
+#include <errno.h>
+
+#define SYSCALL(x) do { \
+    while ((x) == -1) \
+        RELEASE_ASSERT(errno == EAGAIN); \
+} while (0);
+
+#endif // Syscall_h
diff --git a/Source/bmalloc/bmalloc/VMAllocate.h b/Source/bmalloc/bmalloc/VMAllocate.h
new file mode 100644 (file)
index 0000000..9c03357
--- /dev/null
@@ -0,0 +1,144 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef VMAllocate_h
+#define VMAllocate_h
+
+#include "BAssert.h"
+#include "Range.h"
+#include "Sizes.h"
+#include "Syscall.h"
+#include <algorithm>
+#include <mach/vm_statistics.h>
+#include <sys/mman.h>
+#include <unistd.h>
+
+namespace bmalloc {
+
+#define BMALLOC_VM_TAG VM_MAKE_TAG(VM_MEMORY_TCMALLOC)
+    
+static const size_t vmPageSize = 16 * kB; // Least upper bound of the OS's we support.
+static const size_t vmPageMask = ~(vmPageSize - 1);
+    
+inline size_t vmSize(size_t size)
+{
+    return roundUpToMultipleOf<vmPageSize>(size);
+}
+    
+inline void vmValidate(size_t vmSize)
+{
+    ASSERT(vmSize);
+    ASSERT(vmSize == bmalloc::vmSize(vmSize));
+}
+
+inline void vmValidate(void* p, size_t vmSize)
+{
+    vmValidate(vmSize);
+    
+    // We use getpagesize() here instead of vmPageSize because vmPageSize is
+    // allowed to be larger than the OS's true page size.
+    ASSERT(p);
+    ASSERT(p == mask(p, ~(getpagesize() - 1)));
+}
+
+inline void* vmAllocate(size_t vmSize)
+{
+    vmValidate(vmSize);
+    return mmap(0, vmSize, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, BMALLOC_VM_TAG, 0);
+}
+
+inline void vmDeallocate(void* p, size_t vmSize)
+{
+    vmValidate(p, vmSize);
+    munmap(p, vmSize);
+}
+
+// Allocates vmSize bytes at a specified offset from a power-of-two alignment.
+// Use this function to create pointer masks that aren't simple powers of two.
+
+inline std::pair<void*, Range> vmAllocate(size_t vmSize, size_t alignment, size_t offset)
+{
+    vmValidate(vmSize);
+    ASSERT(isPowerOfTwo(alignment));
+
+    size_t mappedSize = std::max(vmSize, alignment) + alignment;
+    char* mapped = static_cast<char*>(vmAllocate(mappedSize));
+    
+    uintptr_t alignmentMask = alignment - 1;
+    if (!test(mapped, alignmentMask) && offset + vmSize <= alignment) {
+        // We got two perfectly aligned regions. Give one back to avoid wasting
+        // VM unnecessarily. This isn't costly because we aren't making holes.
+        vmDeallocate(mapped + alignment, alignment);
+        return std::make_pair(mapped + offset, Range(mapped, alignment));
+    }
+
+    // We got an unaligned region. Keep the whole thing to avoid creating holes,
+    // and hopefully realign the VM allocator for future allocations. On Darwin,
+    // VM holes trigger O(N^2) behavior in mmap, so we want to minimize them.
+    char* mappedAligned = mask(mapped, ~alignmentMask) + alignment;
+    return std::make_pair(mappedAligned + offset, Range(mapped, mappedSize));
+}
+
+inline void vmDeallocatePhysicalPages(void* p, size_t vmSize)
+{
+    vmValidate(p, vmSize);
+    SYSCALL(madvise(p, vmSize, MADV_FREE_REUSABLE));
+}
+
+inline void vmAllocatePhysicalPages(void* p, size_t vmSize)
+{
+    vmValidate(p, vmSize);
+    SYSCALL(madvise(p, vmSize, MADV_FREE_REUSE));
+}
+
+// Trims requests that are un-page-aligned. NOTE: size must be at least a page.
+inline void vmDeallocatePhysicalPagesSloppy(void* p, size_t size)
+{
+    ASSERT(size >= vmPageSize);
+
+    char* begin = roundUpToMultipleOf<vmPageSize>(static_cast<char*>(p));
+    char* end = roundDownToMultipleOf<vmPageSize>(static_cast<char*>(p) + size);
+
+    Range range(begin, end - begin);
+    if (!range)
+        return;
+    vmDeallocatePhysicalPages(range.begin(), range.size());
+}
+
+// Expands requests that are un-page-aligned. NOTE: Allocation must proceed left-to-right.
+inline void vmAllocatePhysicalPagesSloppy(void* p, size_t size)
+{
+    char* begin = roundUpToMultipleOf<vmPageSize>(static_cast<char*>(p));
+    char* end = roundUpToMultipleOf<vmPageSize>(static_cast<char*>(p) + size);
+
+    Range range(begin, end - begin);
+    if (!range)
+        return;
+    vmAllocatePhysicalPages(range.begin(), range.size());
+}
+
+} // namespace bmalloc
+
+#endif // VMAllocate_h
diff --git a/Source/bmalloc/bmalloc/VMHeap.cpp b/Source/bmalloc/bmalloc/VMHeap.cpp
new file mode 100644 (file)
index 0000000..4464bd1
--- /dev/null
@@ -0,0 +1,60 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "BoundaryTagInlines.h"
+#include "Heap.h"
+#include "LargeChunk.h"
+#include "Line.h"
+#include "PerProcess.h"
+#include <thread>
+
+namespace bmalloc {
+
+VMHeap::VMHeap()
+{
+}
+
+void VMHeap::allocateSmallChunk()
+{
+    SmallChunk* chunk = SmallChunk::create();
+    for (auto* it = chunk->begin(); it != chunk->end(); ++it)
+        m_smallPages.push(it);
+}
+
+void VMHeap::allocateMediumChunk()
+{
+    MediumChunk* chunk = MediumChunk::create();
+    for (auto* it = chunk->begin(); it != chunk->end(); ++it)
+        m_mediumPages.push(it);
+}
+
+Range VMHeap::allocateLargeChunk()
+{
+    LargeChunk* chunk = LargeChunk::create();
+    Range result = BoundaryTag::init(chunk);
+    return result;
+}
+
+} // namespace bmalloc
diff --git a/Source/bmalloc/bmalloc/VMHeap.h b/Source/bmalloc/bmalloc/VMHeap.h
new file mode 100644 (file)
index 0000000..f6f6f73
--- /dev/null
@@ -0,0 +1,133 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef VMHeap_h
+#define VMHeap_h
+
+#include "AsyncTask.h"
+#include "FixedVector.h"
+#include "LargeChunk.h"
+#include "MediumChunk.h"
+#include "Range.h"
+#include "SegregatedFreeList.h"
+#include "SmallChunk.h"
+#include "Vector.h"
+
+namespace bmalloc {
+
+class BeginTag;
+class EndTag;
+class Heap;
+
+class VMHeap {
+public:
+    VMHeap();
+
+    SmallPage* allocateSmallPage();
+    MediumPage* allocateMediumPage();
+    Range allocateLargeRange(size_t);
+
+    void deallocateSmallPage(std::unique_lock<Mutex>&, SmallPage*);
+    void deallocateMediumPage(std::unique_lock<Mutex>&, MediumPage*);
+    void deallocateLargeRange(std::unique_lock<Mutex>&, Range);
+
+private:
+    void allocateSmallChunk();
+    void allocateMediumChunk();
+    Range allocateLargeChunk();
+    
+    Vector<SmallPage*> m_smallPages;
+    Vector<MediumPage*> m_mediumPages;
+    SegregatedFreeList m_largeRanges;
+};
+
+inline SmallPage* VMHeap::allocateSmallPage()
+{
+    if (!m_smallPages.size())
+        allocateSmallChunk();
+
+    return m_smallPages.pop();
+}
+
+inline MediumPage* VMHeap::allocateMediumPage()
+{
+    if (!m_mediumPages.size())
+        allocateMediumChunk();
+
+    return m_mediumPages.pop();
+}
+
+inline Range VMHeap::allocateLargeRange(size_t size)
+{
+    Range range = m_largeRanges.take(size);
+    if (!range)
+        range = allocateLargeChunk();
+    return range;
+}
+
+inline void VMHeap::deallocateSmallPage(std::unique_lock<Mutex>& lock, SmallPage* page)
+{
+    lock.unlock();
+    vmDeallocatePhysicalPages(page->begin()->begin(), vmPageSize);
+    lock.lock();
+    
+    m_smallPages.push(page);
+}
+
+inline void VMHeap::deallocateMediumPage(std::unique_lock<Mutex>& lock, MediumPage* page)
+{
+    lock.unlock();
+    vmDeallocatePhysicalPages(page->begin()->begin(), vmPageSize);
+    lock.lock();
+    
+    m_mediumPages.push(page);
+}
+
+inline void VMHeap::deallocateLargeRange(std::unique_lock<Mutex>& lock, Range range)
+{
+    BeginTag* beginTag = LargeChunk::beginTag(range.begin());
+    EndTag* endTag = LargeChunk::endTag(range.begin(), range.size());
+    
+    // Temporarily mark this range as allocated to prevent clients from merging
+    // with it and then reallocating it while we're messing with its physical pages.
+    beginTag->setFree(false);
+    endTag->setFree(false);
+
+    lock.unlock();
+    vmDeallocatePhysicalPagesSloppy(range.begin(), range.size());
+    lock.lock();
+
+    beginTag->setFree(true);
+    endTag->setFree(true);
+
+    beginTag->setHasPhysicalPages(false);
+    endTag->setHasPhysicalPages(false);
+
+    m_largeRanges.insert(range);
+}
+
+} // namespace bmalloc
+
+#endif // VMHeap_h
diff --git a/Source/bmalloc/bmalloc/Vector.h b/Source/bmalloc/bmalloc/Vector.h
new file mode 100644 (file)
index 0000000..a3d1666
--- /dev/null
@@ -0,0 +1,175 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef Vector_h
+#define Vector_h
+
+#include "Inline.h"
+#include "VMAllocate.h"
+#include <cstddef>
+#include <string>
+
+namespace bmalloc {
+
+// A replacement for std::vector that allocates using vmAllocate instead of
+// malloc, shrinks automatically, and supports "popping" from the middle.
+
+template<typename T>
+class Vector {
+    static_assert(std::is_trivially_destructible<T>::value, "Vector must have a trivial destructor.");
+public:
+    Vector(const Vector&) = delete;
+    Vector& operator=(const Vector&) = delete;
+
+    Vector();
+    ~Vector();
+
+    T* begin() { return m_buffer; }
+    T* end() { return m_buffer + m_size; }
+
+    size_t size() { return m_size; }
+    size_t capacity() { return m_capacity; }
+    
+    T& operator[](size_t);
+    T& last() { return m_buffer[m_size - 1]; }
+
+    void push(const T&);
+    void push(const T*, const T*);
+    T pop();
+    T pop(size_t);
+    T pop(const T* it) { return pop(it - begin()); }
+
+    void shrink(size_t);
+
+private:
+    static const size_t growFactor = 2;
+    static const size_t shrinkFactor = 4;
+    static const size_t initialCapacity = vmPageSize;
+
+    void growCapacity(size_t size);
+    void shrinkCapacity();
+    void reallocateBuffer(size_t);
+
+    T* m_buffer;
+    size_t m_size;
+    size_t m_capacity;
+};
+
+template<typename T>
+inline Vector<T>::Vector()
+    : m_buffer(0)
+    , m_size(0)
+    , m_capacity(0)
+{
+}
+
+template<typename T>
+Vector<T>::~Vector()
+{
+    vmDeallocate(m_buffer, vmSize(m_capacity * sizeof(T)));
+}
+
+template<typename T>
+inline T& Vector<T>::operator[](size_t i)
+{
+    ASSERT(i < m_size);
+    return m_buffer[i];
+}
+
+template<typename T>
+INLINE void Vector<T>::push(const T& value)
+{
+    if (m_size == m_capacity)
+        growCapacity(m_size);
+    m_buffer[m_size++] = value;
+}
+
+template<typename T>
+void Vector<T>::push(const T* begin, const T* end)
+{
+    size_t newSize = m_size + (end - begin);
+    if (newSize > m_capacity)
+        growCapacity(newSize);
+    memcpy(this->end(), begin, (end - begin) * sizeof(T));
+    m_size = newSize;
+}
+
+template<typename T>
+inline T Vector<T>::pop()
+{
+    ASSERT(m_size);
+    T value = m_buffer[m_size - 1];
+    shrink(m_size - 1);
+    return value;
+}
+
+template<typename T>
+inline T Vector<T>::pop(size_t i)
+{
+    ASSERT(i < m_size);
+    std::swap(m_buffer[i], last());
+    return pop();
+}
+
+template<typename T>
+inline void Vector<T>::shrink(size_t size)
+{
+    ASSERT(size <= m_size);
+    m_size = size;
+    if (m_capacity > initialCapacity && m_size < m_capacity / shrinkFactor)
+        shrinkCapacity();
+}
+
+template<typename T>
+void Vector<T>::reallocateBuffer(size_t newCapacity)
+{
+    size_t vmSize = bmalloc::vmSize(newCapacity * sizeof(T));
+    T* newBuffer = static_cast<T*>(vmAllocate(vmSize));
+    if (m_buffer) {
+        memcpy(newBuffer, m_buffer, m_size * sizeof(T));
+        vmDeallocate(m_buffer, bmalloc::vmSize(m_capacity * sizeof(T)));
+    }
+
+    m_buffer = newBuffer;
+    m_capacity = vmSize / sizeof(T);
+}
+
+template<typename T>
+NO_INLINE void Vector<T>::shrinkCapacity()
+{
+    size_t newCapacity = max(initialCapacity, m_capacity / shrinkFactor);
+    reallocateBuffer(newCapacity);
+}
+
+template<typename T>
+NO_INLINE void Vector<T>::growCapacity(size_t size)
+{
+    size_t newCapacity = max(initialCapacity, size * growFactor);
+    reallocateBuffer(newCapacity);
+}
+
+} // namespace bmalloc
+
+#endif // Vector_h
diff --git a/Source/bmalloc/bmalloc/XLargeChunk.h b/Source/bmalloc/bmalloc/XLargeChunk.h
new file mode 100644 (file)
index 0000000..a56877f
--- /dev/null
@@ -0,0 +1,89 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef XLargeChunk_h
+#define XLargeChunk_h
+
+#include "Sizes.h"
+
+namespace bmalloc {
+
+class XLargeChunk {
+public:
+    static XLargeChunk* create(size_t);
+    static void destroy(XLargeChunk*);
+    
+    static XLargeChunk* get(void* object) { return reinterpret_cast<XLargeChunk*>(LargeChunk::get(object)); }
+
+    char* begin() { return m_largeChunk.begin(); }
+    size_t& size();
+
+private:
+    XLargeChunk(const Range&, size_t);
+    Range& range();
+    
+    LargeChunk m_largeChunk;
+};
+
+inline XLargeChunk::XLargeChunk(const Range& range, size_t size)
+{
+    this->range() = range;
+    this->size() = size;
+}
+
+inline XLargeChunk* XLargeChunk::create(size_t size)
+{
+    size_t vmSize = bmalloc::vmSize(sizeof(XLargeChunk) + size);
+    std::pair<void*, Range> result = vmAllocate(vmSize, superChunkSize, largeChunkOffset);
+    return new (result.first) XLargeChunk(result.second, size);
+}
+
+inline void XLargeChunk::destroy(XLargeChunk* chunk)
+{
+    const Range& range = chunk->range();
+    vmDeallocate(range.begin(), range.size());
+}
+
+inline Range& XLargeChunk::range()
+{
+    // Since we hold only one object, we only use our first BoundaryTag. So, we
+    // can stuff our range into the remaining metadata.
+    Range& result = *reinterpret_cast<Range*>(roundUpToMultipleOf<alignment>(LargeChunk::beginTag(begin()) + 1));
+    ASSERT(static_cast<void*>(&result) < static_cast<void*>(begin()));
+    return result;
+}
+
+inline size_t& XLargeChunk::size()
+{
+    // Since we hold only one object, we only use our first BoundaryTag. So, we
+    // can stuff our size into the remaining metadata.
+    size_t& result = *reinterpret_cast<size_t*>(roundUpToMultipleOf<alignment>(&range() + 1));
+    ASSERT(static_cast<void*>(&result) < static_cast<void*>(begin()));
+    return result;
+}
+
+}; // namespace bmalloc
+
+#endif // XLargeChunk
diff --git a/Source/bmalloc/bmalloc/bmalloc.h b/Source/bmalloc/bmalloc/bmalloc.h
new file mode 100644 (file)
index 0000000..98c4a4a
--- /dev/null
@@ -0,0 +1,83 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "Cache.h"
+#include "LargeChunk.h"
+#include "XLargeChunk.h"
+#include "Sizes.h"
+
+namespace bmalloc {
+namespace api {
+
+inline void* malloc(size_t size)
+{
+    return Cache::allocate(size);
+}
+
+inline void free(void* object)
+{
+    return Cache::deallocate(object);
+}
+
+inline void* realloc(void* object, size_t newSize)
+{
+    void* result = Cache::allocate(newSize);
+    if (!object)
+        return result;
+
+    size_t oldSize = 0;
+    switch(objectType(object)) {
+    case Small: {
+        // We don't have an exact size, but we can calculate a maximum.
+        void* end = roundUpToMultipleOf<smallLineSize>(static_cast<char*>(object) + 1);
+        oldSize = static_cast<char*>(end) - static_cast<char*>(object);
+        break;
+    }
+    case Medium: {
+        // We don't have an exact size, but we can calculate a maximum.
+        void* end = roundUpToMultipleOf<mediumLineSize>(static_cast<char*>(object) + 1);
+        oldSize = static_cast<char*>(end) - static_cast<char*>(object);
+        break;
+    }
+    case Large: {
+        BeginTag* beginTag = LargeChunk::beginTag(object);
+        oldSize = beginTag->size();
+        break;
+    }
+    case XLarge: {
+        XLargeChunk* chunk = XLargeChunk::get(object);
+        oldSize = chunk->size();
+        break;
+    }
+    }
+
+    size_t copySize = std::min(oldSize, newSize);
+    memcpy(result, object, copySize);
+    Cache::deallocate(object);
+    return result;
+}
+
+} // namespace api
+} // namespace bmalloc
diff --git a/Source/bmalloc/bmalloc/mbmalloc.cpp b/Source/bmalloc/bmalloc/mbmalloc.cpp
new file mode 100644 (file)
index 0000000..4651adc
--- /dev/null
@@ -0,0 +1,45 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "bmalloc.h"
+
+extern "C" {
+
+void* mbmalloc(size_t size)
+{
+    return bmalloc::api::malloc(size);
+}
+
+void mbfree(void* p, size_t)
+{
+    bmalloc::api::free(p);
+}
+
+void* mbrealloc(void* p, size_t, size_t size)
+{
+    return bmalloc::api::realloc(p, size);
+}
+
+} // extern "C"