<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[166893] trunk/Source</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/166893">166893</a></dd>
<dt>Author</dt> <dd>ggaren@apple.com</dd>
<dt>Date</dt> <dd>2014-04-07 16:54:11 -0700 (Mon, 07 Apr 2014)</dd>
</dl>
<h3>Log Message</h3>
<pre>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.</pre>
<h3>Added Paths</h3>
<ul>
<li>trunk/Source/bmalloc/</li>
<li><a href="#trunkSourcebmallocChangeLog">trunk/Source/bmalloc/ChangeLog</a></li>
<li>trunk/Source/bmalloc/bmalloc/</li>
<li><a href="#trunkSourcebmallocbmallocAlgorithmh">trunk/Source/bmalloc/bmalloc/Algorithm.h</a></li>
<li><a href="#trunkSourcebmallocbmallocAllocatorcpp">trunk/Source/bmalloc/bmalloc/Allocator.cpp</a></li>
<li><a href="#trunkSourcebmallocbmallocAllocatorh">trunk/Source/bmalloc/bmalloc/Allocator.h</a></li>
<li><a href="#trunkSourcebmallocbmallocAsyncTaskcpp">trunk/Source/bmalloc/bmalloc/AsyncTask.cpp</a></li>
<li><a href="#trunkSourcebmallocbmallocAsyncTaskh">trunk/Source/bmalloc/bmalloc/AsyncTask.h</a></li>
<li><a href="#trunkSourcebmallocbmallocBAsserth">trunk/Source/bmalloc/bmalloc/BAssert.h</a></li>
<li><a href="#trunkSourcebmallocbmallocBeginTagh">trunk/Source/bmalloc/bmalloc/BeginTag.h</a></li>
<li><a href="#trunkSourcebmallocbmallocBoundaryTagh">trunk/Source/bmalloc/bmalloc/BoundaryTag.h</a></li>
<li><a href="#trunkSourcebmallocbmallocBoundaryTagInlinesh">trunk/Source/bmalloc/bmalloc/BoundaryTagInlines.h</a></li>
<li><a href="#trunkSourcebmallocbmallocCachecpp">trunk/Source/bmalloc/bmalloc/Cache.cpp</a></li>
<li><a href="#trunkSourcebmallocbmallocCacheh">trunk/Source/bmalloc/bmalloc/Cache.h</a></li>
<li><a href="#trunkSourcebmallocbmallocChunkh">trunk/Source/bmalloc/bmalloc/Chunk.h</a></li>
<li><a href="#trunkSourcebmallocbmallocDeallocatorcpp">trunk/Source/bmalloc/bmalloc/Deallocator.cpp</a></li>
<li><a href="#trunkSourcebmallocbmallocDeallocatorh">trunk/Source/bmalloc/bmalloc/Deallocator.h</a></li>
<li><a href="#trunkSourcebmallocbmallocEndTagh">trunk/Source/bmalloc/bmalloc/EndTag.h</a></li>
<li><a href="#trunkSourcebmallocbmallocFixedVectorh">trunk/Source/bmalloc/bmalloc/FixedVector.h</a></li>
<li><a href="#trunkSourcebmallocbmallocHeapcpp">trunk/Source/bmalloc/bmalloc/Heap.cpp</a></li>
<li><a href="#trunkSourcebmallocbmallocHeaph">trunk/Source/bmalloc/bmalloc/Heap.h</a></li>
<li><a href="#trunkSourcebmallocbmallocInlineh">trunk/Source/bmalloc/bmalloc/Inline.h</a></li>
<li><a href="#trunkSourcebmallocbmallocLargeChunkh">trunk/Source/bmalloc/bmalloc/LargeChunk.h</a></li>
<li><a href="#trunkSourcebmallocbmallocLineh">trunk/Source/bmalloc/bmalloc/Line.h</a></li>
<li><a href="#trunkSourcebmallocbmallocMediumAllocatorh">trunk/Source/bmalloc/bmalloc/MediumAllocator.h</a></li>
<li><a href="#trunkSourcebmallocbmallocMediumChunkh">trunk/Source/bmalloc/bmalloc/MediumChunk.h</a></li>
<li><a href="#trunkSourcebmallocbmallocMediumLineh">trunk/Source/bmalloc/bmalloc/MediumLine.h</a></li>
<li><a href="#trunkSourcebmallocbmallocMediumPageh">trunk/Source/bmalloc/bmalloc/MediumPage.h</a></li>
<li><a href="#trunkSourcebmallocbmallocMediumTraitsh">trunk/Source/bmalloc/bmalloc/MediumTraits.h</a></li>
<li><a href="#trunkSourcebmallocbmallocMutexcpp">trunk/Source/bmalloc/bmalloc/Mutex.cpp</a></li>
<li><a href="#trunkSourcebmallocbmallocMutexh">trunk/Source/bmalloc/bmalloc/Mutex.h</a></li>
<li><a href="#trunkSourcebmallocbmallocObjectTypecpp">trunk/Source/bmalloc/bmalloc/ObjectType.cpp</a></li>
<li><a href="#trunkSourcebmallocbmallocObjectTypeh">trunk/Source/bmalloc/bmalloc/ObjectType.h</a></li>
<li><a href="#trunkSourcebmallocbmallocPageh">trunk/Source/bmalloc/bmalloc/Page.h</a></li>
<li><a href="#trunkSourcebmallocbmallocPerProcessh">trunk/Source/bmalloc/bmalloc/PerProcess.h</a></li>
<li><a href="#trunkSourcebmallocbmallocPerThreadh">trunk/Source/bmalloc/bmalloc/PerThread.h</a></li>
<li><a href="#trunkSourcebmallocbmallocRangeh">trunk/Source/bmalloc/bmalloc/Range.h</a></li>
<li><a href="#trunkSourcebmallocbmallocSegregatedFreeListcpp">trunk/Source/bmalloc/bmalloc/SegregatedFreeList.cpp</a></li>
<li><a href="#trunkSourcebmallocbmallocSegregatedFreeListh">trunk/Source/bmalloc/bmalloc/SegregatedFreeList.h</a></li>
<li><a href="#trunkSourcebmallocbmallocSizesh">trunk/Source/bmalloc/bmalloc/Sizes.h</a></li>
<li><a href="#trunkSourcebmallocbmallocSmallAllocatorh">trunk/Source/bmalloc/bmalloc/SmallAllocator.h</a></li>
<li><a href="#trunkSourcebmallocbmallocSmallChunkh">trunk/Source/bmalloc/bmalloc/SmallChunk.h</a></li>
<li><a href="#trunkSourcebmallocbmallocSmallLineh">trunk/Source/bmalloc/bmalloc/SmallLine.h</a></li>
<li><a href="#trunkSourcebmallocbmallocSmallPageh">trunk/Source/bmalloc/bmalloc/SmallPage.h</a></li>
<li><a href="#trunkSourcebmallocbmallocSmallTraitsh">trunk/Source/bmalloc/bmalloc/SmallTraits.h</a></li>
<li><a href="#trunkSourcebmallocbmallocSyscallh">trunk/Source/bmalloc/bmalloc/Syscall.h</a></li>
<li><a href="#trunkSourcebmallocbmallocVMAllocateh">trunk/Source/bmalloc/bmalloc/VMAllocate.h</a></li>
<li><a href="#trunkSourcebmallocbmallocVMHeapcpp">trunk/Source/bmalloc/bmalloc/VMHeap.cpp</a></li>
<li><a href="#trunkSourcebmallocbmallocVMHeaph">trunk/Source/bmalloc/bmalloc/VMHeap.h</a></li>
<li><a href="#trunkSourcebmallocbmallocVectorh">trunk/Source/bmalloc/bmalloc/Vector.h</a></li>
<li><a href="#trunkSourcebmallocbmallocXLargeChunkh">trunk/Source/bmalloc/bmalloc/XLargeChunk.h</a></li>
<li><a href="#trunkSourcebmallocbmallocbmalloch">trunk/Source/bmalloc/bmalloc/bmalloc.h</a></li>
<li><a href="#trunkSourcebmallocbmallocmbmalloccpp">trunk/Source/bmalloc/bmalloc/mbmalloc.cpp</a></li>
<li>trunk/Source/bmalloc/bmalloc.xcodeproj/</li>
<li><a href="#trunkSourcebmallocbmallocxcodeprojprojectpbxproj">trunk/Source/bmalloc/bmalloc.xcodeproj/project.pbxproj</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourcebmallocChangeLog"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/ChangeLog (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/ChangeLog         (rev 0)
+++ trunk/Source/bmalloc/ChangeLog        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,275 @@
</span><ins>+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.
+
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocAlgorithmh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/Algorithm.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Algorithm.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/Algorithm.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,91 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocAllocatorcpp"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/Allocator.cpp (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Allocator.cpp         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/Allocator.cpp        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,158 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocAllocatorh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/Allocator.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Allocator.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/Allocator.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,102 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocAsyncTaskcpp"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/AsyncTask.cpp (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/AsyncTask.cpp         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/AsyncTask.cpp        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,55 @@
</span><ins>+#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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocAsyncTaskh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/AsyncTask.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/AsyncTask.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/AsyncTask.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,146 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocBAsserth"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/BAssert.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/BAssert.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/BAssert.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,57 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocBeginTagh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/BeginTag.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/BeginTag.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/BeginTag.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,45 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocBoundaryTagh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/BoundaryTag.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/BoundaryTag.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/BoundaryTag.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,106 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocBoundaryTagInlinesh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/BoundaryTagInlines.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/BoundaryTagInlines.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/BoundaryTagInlines.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,221 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocCachecpp"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/Cache.cpp (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Cache.cpp         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/Cache.cpp        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,77 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocCacheh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/Cache.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Cache.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/Cache.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,95 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocChunkh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/Chunk.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Chunk.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/Chunk.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,86 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocDeallocatorcpp"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/Deallocator.cpp (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Deallocator.cpp         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/Deallocator.cpp        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,158 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocDeallocatorh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/Deallocator.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Deallocator.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/Deallocator.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,85 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocEndTagh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/EndTag.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/EndTag.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/EndTag.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,47 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocFixedVectorh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/FixedVector.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/FixedVector.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/FixedVector.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,119 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocHeapcpp"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/Heap.cpp (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Heap.cpp         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/Heap.cpp        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,202 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocHeaph"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/Heap.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Heap.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/Heap.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,149 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocInlineh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/Inline.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Inline.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/Inline.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,33 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocLargeChunkh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/LargeChunk.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/LargeChunk.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/LargeChunk.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,107 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocLineh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/Line.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Line.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/Line.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,100 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocMediumAllocatorh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/MediumAllocator.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/MediumAllocator.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/MediumAllocator.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,106 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocMediumChunkh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/MediumChunk.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/MediumChunk.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/MediumChunk.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,40 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocMediumLineh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/MediumLine.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/MediumLine.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/MediumLine.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,38 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocMediumPageh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/MediumPage.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/MediumPage.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/MediumPage.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,38 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocMediumTraitsh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/MediumTraits.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/MediumTraits.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/MediumTraits.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,52 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocMutexcpp"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/Mutex.cpp (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Mutex.cpp         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/Mutex.cpp        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,37 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocMutexh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/Mutex.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Mutex.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/Mutex.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,72 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocObjectTypecpp"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/ObjectType.cpp (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/ObjectType.cpp         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/ObjectType.cpp        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,45 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocObjectTypeh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/ObjectType.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/ObjectType.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/ObjectType.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,51 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocPageh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/Page.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Page.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/Page.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,106 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocPerProcessh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/PerProcess.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/PerProcess.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/PerProcess.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,110 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocPerThreadh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/PerThread.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/PerThread.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/PerThread.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,128 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocRangeh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/Range.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Range.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/Range.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,61 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocSegregatedFreeListcpp"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/SegregatedFreeList.cpp (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/SegregatedFreeList.cpp         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/SegregatedFreeList.cpp        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,134 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocSegregatedFreeListh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/SegregatedFreeList.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/SegregatedFreeList.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/SegregatedFreeList.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,66 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocSizesh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/Sizes.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Sizes.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/Sizes.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,98 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocSmallAllocatorh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/SmallAllocator.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/SmallAllocator.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/SmallAllocator.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,112 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocSmallChunkh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/SmallChunk.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/SmallChunk.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/SmallChunk.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,40 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocSmallLineh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/SmallLine.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/SmallLine.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/SmallLine.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,38 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocSmallPageh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/SmallPage.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/SmallPage.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/SmallPage.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,38 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocSmallTraitsh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/SmallTraits.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/SmallTraits.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/SmallTraits.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,51 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocSyscallh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/Syscall.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Syscall.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/Syscall.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,36 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocVMAllocateh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/VMAllocate.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/VMAllocate.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/VMAllocate.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,144 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocVMHeapcpp"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/VMHeap.cpp (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/VMHeap.cpp         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/VMHeap.cpp        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,60 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocVMHeaph"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/VMHeap.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/VMHeap.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/VMHeap.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,133 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocVectorh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/Vector.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Vector.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/Vector.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,175 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocXLargeChunkh"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/XLargeChunk.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/XLargeChunk.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/XLargeChunk.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,89 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocbmalloch"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/bmalloc.h (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/bmalloc.h         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/bmalloc.h        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,83 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocmbmalloccpp"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/mbmalloc.cpp (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/mbmalloc.cpp         (rev 0)
+++ trunk/Source/bmalloc/bmalloc/mbmalloc.cpp        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,45 @@
</span><ins>+/*
+ * 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"
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocxcodeproj"></a>
<div class="propset"><h4>Property changes: trunk/Source/bmalloc/bmalloc.xcodeproj</h4>
<pre class="diff"><span>
</span></pre></div>
<a id="svnignore"></a>
<div class="addfile"><h4>Added: svn:ignore</h4></div>
<span class="cx"> *.pbxuser
</span><span class="cx"> *.perspective*
</span><span class="cx"> project.xcworkspace
</span><span class="cx"> xcuserdata
</span><a id="trunkSourcebmallocbmallocxcodeprojprojectpbxproj"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc.xcodeproj/project.pbxproj (0 => 166893)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc.xcodeproj/project.pbxproj         (rev 0)
+++ trunk/Source/bmalloc/bmalloc.xcodeproj/project.pbxproj        2014-04-07 23:54:11 UTC (rev 166893)
</span><span class="lines">@@ -0,0 +1,498 @@
</span><ins>+// !$*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 */;
+}
</ins></span></pre>
</div>
</div>
</body>
</html>