<!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>[199746] trunk/Source/bmalloc</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/199746">199746</a></dd>
<dt>Author</dt> <dd>ggaren@apple.com</dd>
<dt>Date</dt> <dd>2016-04-19 16:36:20 -0700 (Tue, 19 Apr 2016)</dd>
</dl>
<h3>Log Message</h3>
<pre>bmalloc: Merge the large and xlarge allocators
https://bugs.webkit.org/show_bug.cgi?id=156734
Reviewed by Andreas Kling.
This give us better defense against worst case memory usage:
Baseline Patch Δ
Peak Memory:
nimlang 198,132kB 181,468kB ^ 1.09x smaller
It also eliminates inline metadata for large objects, fixing the
regression introduced in <a href="http://trac.webkit.org/projects/webkit/changeset/198675">r198675</a>, and more:
run-malloc-benchmarks Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/
Baseline Patch Δ
Memory at End:
big 10,880kB 3,328kB ^ 3.27x smaller
facebook 3,112kB 2,868kB ^ 1.09x smaller
fragment --parallel 1,848kB 760kB ^ 2.43x smaller
fragment_iterate --parallel 4,908kB 776kB ^ 6.32x smaller
big --parallel 48,076kB 11,892kB ^ 4.04x smaller
Overall memory use looks OK:
run-malloc-benchmarks --memory_warning Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/
Baseline Patch Δ
Memory at End:
<arithmetic mean> 13,992kB 13,987kB ^ 1.0x smaller
Overall throughput looks OK:
run-malloc-benchmarks Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/
Baseline Patch Δ
Execution Time:
<arithmetic mean> 103ms 104ms ! 1.01x slower
We're a bit slower on the "all-out large allocations on all cores"
benchmark, but I think that's an OK price to pay:
Baseline Patch Δ
Execution Time:
big --parallel 125ms 136ms ! 1.09x slower
This patch net removes 1.5k lines of code. It turns out that large
allocations are rare, and free memory fragments are also rare, so the
combination is super rare, and a simple O(n) algorithm that ensures good
memory behavior is the best option.
Fun fact: In practice, the odds that the old code would save memory
were *worse* than the odds that it would contain a bug that wasted
memory. :)
* bmalloc.xcodeproj/project.pbxproj:
* bmalloc/Allocator.cpp:
(bmalloc::Allocator::tryAllocate): largeMax is the new xLargeMax since
xLargeMax is gone now.
(bmalloc::Allocator::allocate): I moved the rounding code into allocateLarge,
so we don't have to do it here.
(bmalloc::Allocator::reallocate):
(bmalloc::Allocator::allocateSlowCase):
(bmalloc::Allocator::allocateXLarge): Deleted. No more XLarge case.
* bmalloc/Allocator.h:
* bmalloc/BeginTag.h: Removed.
* bmalloc/BoundaryTag.h: Removed.
* bmalloc/Chunk.h:
(bmalloc::ChunkHash::hash): Added a hash function. The best hash function
is a unique and monotonically increasing integer, and that's exactly what
we typically get from the high bits of a Chunk, since the OS allocates
Chunks at unique and increasing addresses.
(bmalloc::Chunk::boundaryTags): Deleted.
(bmalloc::Chunk::objectType): Deleted.
(bmalloc::Chunk::beginTag): Deleted.
(bmalloc::Chunk::endTag): Deleted.
* bmalloc/Deallocator.cpp:
(bmalloc::Deallocator::deallocateSlowCase): We no longer know for sure,
by looking at its bit pattern, whether a pointer is small or large.
Instead, any pointer with large alignment *might* be large, and when
we occasionally encounter such an object, we have to consult a hash
table in the Heap to find out for sure. This turns out to be just as
cheap in practice.
We don't deallocate large objects on the fast path anymore. We can't,
because large objects have out-of-line metadata now.
(bmalloc::Deallocator::deallocateXLarge): Deleted.
* bmalloc/Deallocator.h:
(bmalloc::Deallocator::deallocateFastCase): See deallocateSlowCase.
* bmalloc/EndTag.h: Removed.
* bmalloc/FreeList.cpp: Removed.
* bmalloc/FreeList.h: Removed.
* bmalloc/Heap.cpp:
(bmalloc::Heap::allocateSmallPage): Be sure to track each chunk in
the object type map, so we can distinguish small vs large objects.
(bmalloc::Heap::deallocateSmallLine): No need to check object type
because we know object type now by virtue of being on the small object
path.
(bmalloc::Heap::splitAndAllocate): Be sure to track each chunk in
the object type map, so we can distinguish small vs large objects. Large
objects can split across chunks, so we need to add each large object's
chunk as it is allocated.
(bmalloc::Heap::tryAllocateLarge):
(bmalloc::Heap::allocateLarge):
(bmalloc::Heap::isLarge):
(bmalloc::Heap::largeSize):
(bmalloc::Heap::shrinkLarge):
(bmalloc::Heap::deallocateLarge): Merged in existing XLarge logic for
large objects.
(bmalloc::Heap::scavengeXLargeObjects): Deleted.
(bmalloc::Heap::allocateXLarge): Deleted.
(bmalloc::Heap::tryAllocateXLarge): Deleted.
(bmalloc::Heap::xLargeSize): Deleted.
(bmalloc::Heap::shrinkXLarge): Deleted.
(bmalloc::Heap::deallocateXLarge): Deleted.
* bmalloc/Heap.h:
(bmalloc::Heap::LargeObjectHash::hash):
* bmalloc/LargeObject.h: Removed.
* bmalloc/Map.h: Added.
(bmalloc::Map::size):
(bmalloc::Map::capacity):
(bmalloc::Map::get):
(bmalloc::Map::set):
(bmalloc::Map::remove):
(bmalloc::Map::shouldGrow):
(bmalloc::Map::shouldShrink):
(bmalloc::Map::find):
(bmalloc::Hash>::rehash): Simple hash table.
* bmalloc/Object.h:
* bmalloc/ObjectType.cpp:
(bmalloc::objectType):
* bmalloc/ObjectType.h:
(bmalloc::mightBeLarge): See deallocateSlowCase.
(bmalloc::isXLarge): Deleted.
* bmalloc/SegregatedFreeList.cpp: Removed.
* bmalloc/SegregatedFreeList.h: Removed.
* bmalloc/Sizes.h: Upped smallMax to 64kB. Upping to 32kB is pretty
reasonable, since sizes between 16kB and 32kB share page sizes. I went
all the way up to 64kB because the GC uses 64kB blocks, and also just
for extra padding to ensure that large allocations are indeed rare.
* bmalloc/SortedVector.h: Removed.
* bmalloc/VMHeap.cpp:
(bmalloc::VMHeap::tryAllocateLargeChunk):
(bmalloc::VMHeap::allocateSmallChunk):
(bmalloc::VMHeap::VMHeap): Deleted.
(bmalloc::VMHeap::allocateChunk): Deleted.
* bmalloc/VMHeap.h:
(bmalloc::VMHeap::deallocateSmallPage):
(bmalloc::VMHeap::allocateLargeObject): Deleted.
(bmalloc::VMHeap::deallocateLargeObject): Deleted. Nixed all the boundary
tag logic since metadata is out of line now.
* bmalloc/VMState.h: Removed. Instead of an abstract state, we track
the precise amount of committed physical pages at the head of a VM
range. This allows us to merge aggressively without triggering an madvise
storm most of the time.
* bmalloc/Vector.h:
(bmalloc::Vector<T>::Vector):
(bmalloc::Vector<T>::insert):
(bmalloc::Vector<T>::remove):
(bmalloc::Vector<T>::resize): Filled out some missing helpers.
* bmalloc/XLargeMap.cpp:
(bmalloc::XLargeMap::remove):
(bmalloc::XLargeMap::add):
(bmalloc::XLargeMap::removePhysical):
(bmalloc::XLargeMap::takeFree): Deleted.
(bmalloc::XLargeMap::addFree): Deleted.
(bmalloc::XLargeMap::addAllocated): Deleted.
(bmalloc::XLargeMap::getAllocated): Deleted.
(bmalloc::XLargeMap::takeAllocated): Deleted.
(bmalloc::XLargeMap::shrinkToFit): Deleted.
(bmalloc::XLargeMap::takePhysical): Deleted.
(bmalloc::XLargeMap::addVirtual): Deleted.
* bmalloc/XLargeMap.h:
(bmalloc::XLargeMap::Allocation::operator<): Deleted. We don't track
object sizes anymore -- just free space. (The Heap tracks object sizes.)
We use plain old linear search for free space. (See intro.)
* bmalloc/XLargeRange.h:
(bmalloc::XLargeRange::physicalSize):
(bmalloc::XLargeRange::setPhysicalSize):
(bmalloc::merge):
(bmalloc::XLargeRange::split):
(bmalloc::XLargeRange::vmState): Deleted.
(bmalloc::XLargeRange::setVMState): Deleted. See VMState.h.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourcebmallocCMakeListstxt">trunk/Source/bmalloc/CMakeLists.txt</a></li>
<li><a href="#trunkSourcebmallocChangeLog">trunk/Source/bmalloc/ChangeLog</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="#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="#trunkSourcebmallocbmallocHeapcpp">trunk/Source/bmalloc/bmalloc/Heap.cpp</a></li>
<li><a href="#trunkSourcebmallocbmallocHeaph">trunk/Source/bmalloc/bmalloc/Heap.h</a></li>
<li><a href="#trunkSourcebmallocbmallocObjecth">trunk/Source/bmalloc/bmalloc/Object.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="#trunkSourcebmallocbmallocSizesh">trunk/Source/bmalloc/bmalloc/Sizes.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="#trunkSourcebmallocbmallocXLargeMapcpp">trunk/Source/bmalloc/bmalloc/XLargeMap.cpp</a></li>
<li><a href="#trunkSourcebmallocbmallocXLargeMaph">trunk/Source/bmalloc/bmalloc/XLargeMap.h</a></li>
<li><a href="#trunkSourcebmallocbmallocXLargeRangeh">trunk/Source/bmalloc/bmalloc/XLargeRange.h</a></li>
<li><a href="#trunkSourcebmallocbmallocxcodeprojprojectpbxproj">trunk/Source/bmalloc/bmalloc.xcodeproj/project.pbxproj</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourcebmallocbmallocMaph">trunk/Source/bmalloc/bmalloc/Map.h</a></li>
</ul>
<h3>Removed Paths</h3>
<ul>
<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="#trunkSourcebmallocbmallocEndTagh">trunk/Source/bmalloc/bmalloc/EndTag.h</a></li>
<li><a href="#trunkSourcebmallocbmallocFreeListcpp">trunk/Source/bmalloc/bmalloc/FreeList.cpp</a></li>
<li><a href="#trunkSourcebmallocbmallocFreeListh">trunk/Source/bmalloc/bmalloc/FreeList.h</a></li>
<li><a href="#trunkSourcebmallocbmallocLargeObjecth">trunk/Source/bmalloc/bmalloc/LargeObject.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="#trunkSourcebmallocbmallocSortedVectorh">trunk/Source/bmalloc/bmalloc/SortedVector.h</a></li>
<li><a href="#trunkSourcebmallocbmallocVMStateh">trunk/Source/bmalloc/bmalloc/VMState.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourcebmallocCMakeListstxt"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/CMakeLists.txt (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/CMakeLists.txt 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/CMakeLists.txt 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -9,11 +9,9 @@
</span><span class="cx"> bmalloc/Cache.cpp
</span><span class="cx"> bmalloc/Deallocator.cpp
</span><span class="cx"> bmalloc/Environment.cpp
</span><del>- bmalloc/FreeList.cpp
</del><span class="cx"> bmalloc/Heap.cpp
</span><span class="cx"> bmalloc/Logging.cpp
</span><span class="cx"> bmalloc/ObjectType.cpp
</span><del>- bmalloc/SegregatedFreeList.cpp
</del><span class="cx"> bmalloc/StaticMutex.cpp
</span><span class="cx"> bmalloc/VMHeap.cpp
</span><span class="cx"> bmalloc/XLargeMap.cpp
</span></span></pre></div>
<a id="trunkSourcebmallocChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/ChangeLog (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/ChangeLog 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/ChangeLog 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -1,3 +1,218 @@
</span><ins>+2016-04-19 Geoffrey Garen <ggaren@apple.com>
+
+ bmalloc: Merge the large and xlarge allocators
+ https://bugs.webkit.org/show_bug.cgi?id=156734
+
+ Reviewed by Andreas Kling.
+
+ This give us better defense against worst case memory usage:
+
+ Baseline Patch Δ
+ Peak Memory:
+ nimlang 198,132kB 181,468kB ^ 1.09x smaller
+
+ It also eliminates inline metadata for large objects, fixing the
+ regression introduced in r198675, and more:
+
+ run-malloc-benchmarks Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/
+
+ Baseline Patch Δ
+ Memory at End:
+ big 10,880kB 3,328kB ^ 3.27x smaller
+ facebook 3,112kB 2,868kB ^ 1.09x smaller
+ fragment --parallel 1,848kB 760kB ^ 2.43x smaller
+ fragment_iterate --parallel 4,908kB 776kB ^ 6.32x smaller
+ big --parallel 48,076kB 11,892kB ^ 4.04x smaller
+
+ Overall memory use looks OK:
+
+ run-malloc-benchmarks --memory_warning Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/
+
+ Baseline Patch Δ
+ Memory at End:
+ <arithmetic mean> 13,992kB 13,987kB ^ 1.0x smaller
+
+ Overall throughput looks OK:
+
+ run-malloc-benchmarks Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/
+
+ Baseline Patch Δ
+ Execution Time:
+ <arithmetic mean> 103ms 104ms ! 1.01x slower
+
+ We're a bit slower on the "all-out large allocations on all cores"
+ benchmark, but I think that's an OK price to pay:
+
+ Baseline Patch Δ
+ Execution Time:
+ big --parallel 125ms 136ms ! 1.09x slower
+
+ This patch net removes 1.5k lines of code. It turns out that large
+ allocations are rare, and free memory fragments are also rare, so the
+ combination is super rare, and a simple O(n) algorithm that ensures good
+ memory behavior is the best option.
+
+ Fun fact: In practice, the odds that the old code would save memory
+ were *worse* than the odds that it would contain a bug that wasted
+ memory. :)
+
+ * bmalloc.xcodeproj/project.pbxproj:
+
+ * bmalloc/Allocator.cpp:
+ (bmalloc::Allocator::tryAllocate): largeMax is the new xLargeMax since
+ xLargeMax is gone now.
+
+ (bmalloc::Allocator::allocate): I moved the rounding code into allocateLarge,
+ so we don't have to do it here.
+
+ (bmalloc::Allocator::reallocate):
+ (bmalloc::Allocator::allocateSlowCase):
+ (bmalloc::Allocator::allocateXLarge): Deleted. No more XLarge case.
+
+ * bmalloc/Allocator.h:
+
+ * bmalloc/BeginTag.h: Removed.
+ * bmalloc/BoundaryTag.h: Removed.
+
+ * bmalloc/Chunk.h:
+ (bmalloc::ChunkHash::hash): Added a hash function. The best hash function
+ is a unique and monotonically increasing integer, and that's exactly what
+ we typically get from the high bits of a Chunk, since the OS allocates
+ Chunks at unique and increasing addresses.
+ (bmalloc::Chunk::boundaryTags): Deleted.
+ (bmalloc::Chunk::objectType): Deleted.
+ (bmalloc::Chunk::beginTag): Deleted.
+ (bmalloc::Chunk::endTag): Deleted.
+
+ * bmalloc/Deallocator.cpp:
+ (bmalloc::Deallocator::deallocateSlowCase): We no longer know for sure,
+ by looking at its bit pattern, whether a pointer is small or large.
+ Instead, any pointer with large alignment *might* be large, and when
+ we occasionally encounter such an object, we have to consult a hash
+ table in the Heap to find out for sure. This turns out to be just as
+ cheap in practice.
+
+ We don't deallocate large objects on the fast path anymore. We can't,
+ because large objects have out-of-line metadata now.
+
+ (bmalloc::Deallocator::deallocateXLarge): Deleted.
+
+ * bmalloc/Deallocator.h:
+ (bmalloc::Deallocator::deallocateFastCase): See deallocateSlowCase.
+
+ * bmalloc/EndTag.h: Removed.
+ * bmalloc/FreeList.cpp: Removed.
+ * bmalloc/FreeList.h: Removed.
+
+ * bmalloc/Heap.cpp:
+ (bmalloc::Heap::allocateSmallPage): Be sure to track each chunk in
+ the object type map, so we can distinguish small vs large objects.
+
+ (bmalloc::Heap::deallocateSmallLine): No need to check object type
+ because we know object type now by virtue of being on the small object
+ path.
+
+ (bmalloc::Heap::splitAndAllocate): Be sure to track each chunk in
+ the object type map, so we can distinguish small vs large objects. Large
+ objects can split across chunks, so we need to add each large object's
+ chunk as it is allocated.
+
+ (bmalloc::Heap::tryAllocateLarge):
+ (bmalloc::Heap::allocateLarge):
+ (bmalloc::Heap::isLarge):
+ (bmalloc::Heap::largeSize):
+ (bmalloc::Heap::shrinkLarge):
+ (bmalloc::Heap::deallocateLarge): Merged in existing XLarge logic for
+ large objects.
+
+ (bmalloc::Heap::scavengeXLargeObjects): Deleted.
+ (bmalloc::Heap::allocateXLarge): Deleted.
+ (bmalloc::Heap::tryAllocateXLarge): Deleted.
+ (bmalloc::Heap::xLargeSize): Deleted.
+ (bmalloc::Heap::shrinkXLarge): Deleted.
+ (bmalloc::Heap::deallocateXLarge): Deleted.
+
+ * bmalloc/Heap.h:
+ (bmalloc::Heap::LargeObjectHash::hash):
+
+ * bmalloc/LargeObject.h: Removed.
+
+ * bmalloc/Map.h: Added.
+ (bmalloc::Map::size):
+ (bmalloc::Map::capacity):
+ (bmalloc::Map::get):
+ (bmalloc::Map::set):
+ (bmalloc::Map::remove):
+ (bmalloc::Map::shouldGrow):
+ (bmalloc::Map::shouldShrink):
+ (bmalloc::Map::find):
+ (bmalloc::Hash>::rehash): Simple hash table.
+
+ * bmalloc/Object.h:
+
+ * bmalloc/ObjectType.cpp:
+ (bmalloc::objectType):
+ * bmalloc/ObjectType.h:
+ (bmalloc::mightBeLarge): See deallocateSlowCase.
+ (bmalloc::isXLarge): Deleted.
+
+ * bmalloc/SegregatedFreeList.cpp: Removed.
+ * bmalloc/SegregatedFreeList.h: Removed.
+
+ * bmalloc/Sizes.h: Upped smallMax to 64kB. Upping to 32kB is pretty
+ reasonable, since sizes between 16kB and 32kB share page sizes. I went
+ all the way up to 64kB because the GC uses 64kB blocks, and also just
+ for extra padding to ensure that large allocations are indeed rare.
+
+ * bmalloc/SortedVector.h: Removed.
+
+ * bmalloc/VMHeap.cpp:
+ (bmalloc::VMHeap::tryAllocateLargeChunk):
+ (bmalloc::VMHeap::allocateSmallChunk):
+ (bmalloc::VMHeap::VMHeap): Deleted.
+ (bmalloc::VMHeap::allocateChunk): Deleted.
+ * bmalloc/VMHeap.h:
+ (bmalloc::VMHeap::deallocateSmallPage):
+ (bmalloc::VMHeap::allocateLargeObject): Deleted.
+ (bmalloc::VMHeap::deallocateLargeObject): Deleted. Nixed all the boundary
+ tag logic since metadata is out of line now.
+
+ * bmalloc/VMState.h: Removed. Instead of an abstract state, we track
+ the precise amount of committed physical pages at the head of a VM
+ range. This allows us to merge aggressively without triggering an madvise
+ storm most of the time.
+
+ * bmalloc/Vector.h:
+ (bmalloc::Vector<T>::Vector):
+ (bmalloc::Vector<T>::insert):
+ (bmalloc::Vector<T>::remove):
+ (bmalloc::Vector<T>::resize): Filled out some missing helpers.
+
+ * bmalloc/XLargeMap.cpp:
+ (bmalloc::XLargeMap::remove):
+ (bmalloc::XLargeMap::add):
+ (bmalloc::XLargeMap::removePhysical):
+ (bmalloc::XLargeMap::takeFree): Deleted.
+ (bmalloc::XLargeMap::addFree): Deleted.
+ (bmalloc::XLargeMap::addAllocated): Deleted.
+ (bmalloc::XLargeMap::getAllocated): Deleted.
+ (bmalloc::XLargeMap::takeAllocated): Deleted.
+ (bmalloc::XLargeMap::shrinkToFit): Deleted.
+ (bmalloc::XLargeMap::takePhysical): Deleted.
+ (bmalloc::XLargeMap::addVirtual): Deleted.
+ * bmalloc/XLargeMap.h:
+ (bmalloc::XLargeMap::Allocation::operator<): Deleted. We don't track
+ object sizes anymore -- just free space. (The Heap tracks object sizes.)
+ We use plain old linear search for free space. (See intro.)
+
+ * bmalloc/XLargeRange.h:
+ (bmalloc::XLargeRange::physicalSize):
+ (bmalloc::XLargeRange::setPhysicalSize):
+ (bmalloc::merge):
+ (bmalloc::XLargeRange::split):
+ (bmalloc::XLargeRange::vmState): Deleted.
+ (bmalloc::XLargeRange::setVMState): Deleted. See VMState.h.
+
</ins><span class="cx"> 2016-04-11 Fujii Hironori <Hironori.Fujii@jp.sony.com>
</span><span class="cx">
</span><span class="cx"> [CMake] Make FOLDER property INHERITED
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocAllocatorcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/Allocator.cpp (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Allocator.cpp 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/Allocator.cpp 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -28,7 +28,6 @@
</span><span class="cx"> #include "Chunk.h"
</span><span class="cx"> #include "Deallocator.h"
</span><span class="cx"> #include "Heap.h"
</span><del>-#include "LargeObject.h"
</del><span class="cx"> #include "PerProcess.h"
</span><span class="cx"> #include "Sizes.h"
</span><span class="cx"> #include <algorithm>
</span><span class="lines">@@ -56,12 +55,12 @@
</span><span class="cx"> if (!m_isBmallocEnabled)
</span><span class="cx"> return malloc(size);
</span><span class="cx">
</span><del>- if (size <= largeMax)
</del><ins>+ if (size <= smallMax)
</ins><span class="cx"> return allocate(size);
</span><span class="cx">
</span><del>- if (size <= xLargeMax) {
</del><ins>+ if (size <= largeMax) {
</ins><span class="cx"> std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
</span><del>- return PerProcess<Heap>::getFastCase()->tryAllocateXLarge(lock, alignment, size);
</del><ins>+ return PerProcess<Heap>::getFastCase()->tryAllocateLarge(lock, alignment, size);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> return nullptr;
</span><span class="lines">@@ -84,20 +83,9 @@
</span><span class="cx"> if (size <= smallMax && alignment <= smallMax)
</span><span class="cx"> return allocate(roundUpToMultipleOf(alignment, size));
</span><span class="cx">
</span><del>- if (size <= largeMax && alignment <= largeMax) {
- size = std::max(largeMin, roundUpToMultipleOf<largeAlignment>(size));
- alignment = roundUpToMultipleOf<largeAlignment>(alignment);
- size_t unalignedSize = largeMin + alignment - largeAlignment + size;
- if (unalignedSize <= largeMax && alignment <= chunkSize / 2) {
- std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
- m_deallocator.processObjectLog(lock);
- return PerProcess<Heap>::getFastCase()->allocateLarge(lock, alignment, size, unalignedSize);
- }
- }
-
- if (size <= xLargeMax && alignment <= xLargeMax) {
</del><ins>+ if (size <= largeMax && alignment <= largeMax / 2) {
</ins><span class="cx"> std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
</span><del>- return PerProcess<Heap>::getFastCase()->allocateXLarge(lock, alignment, size);
</del><ins>+ return PerProcess<Heap>::getFastCase()->allocateLarge(lock, alignment, size);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> BCRASH();
</span><span class="lines">@@ -112,35 +100,20 @@
</span><span class="cx"> size_t oldSize = 0;
</span><span class="cx"> switch (objectType(object)) {
</span><span class="cx"> case ObjectType::Small: {
</span><ins>+ BASSERT(objectType(nullptr) == ObjectType::Small);
+ if (!object)
+ break;
+
</ins><span class="cx"> size_t sizeClass = Object(object).page()->sizeClass();
</span><span class="cx"> oldSize = objectSize(sizeClass);
</span><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx"> case ObjectType::Large: {
</span><span class="cx"> std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
</span><ins>+ oldSize = PerProcess<Heap>::getFastCase()->largeSize(lock, object);
</ins><span class="cx">
</span><del>- LargeObject largeObject(object);
- oldSize = largeObject.size();
-
</del><span class="cx"> if (newSize < oldSize && newSize > smallMax) {
</span><del>- if (oldSize - newSize >= largeMin) {
- newSize = roundUpToMultipleOf<largeAlignment>(newSize);
- PerProcess<Heap>::getFastCase()->shrinkLarge(lock, largeObject, newSize);
- return object;
- }
- }
- break;
- }
- case ObjectType::XLarge: {
- BASSERT(objectType(nullptr) == ObjectType::XLarge);
- if (!object)
- break;
-
- std::unique_lock<StaticMutex> lock(PerProcess<Heap>::mutex());
- oldSize = PerProcess<Heap>::getFastCase()->xLargeSize(lock, object);
-
- if (newSize < oldSize && newSize > largeMax) {
- PerProcess<Heap>::getFastCase()->shrinkXLarge(lock, Range(object, oldSize), newSize);
</del><ins>+ PerProcess<Heap>::getFastCase()->shrinkLarge(lock, Range(object, oldSize), newSize);
</ins><span class="cx"> return object;
</span><span class="cx"> }
</span><span class="cx"> break;
</span><span class="lines">@@ -192,19 +165,10 @@
</span><span class="cx">
</span><span class="cx"> NO_INLINE void* Allocator::allocateLarge(size_t size)
</span><span class="cx"> {
</span><del>- size = roundUpToMultipleOf<largeAlignment>(size);
-
</del><span class="cx"> std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
</span><del>- m_deallocator.processObjectLog(lock);
- return PerProcess<Heap>::getFastCase()->allocateLarge(lock, size);
</del><ins>+ return PerProcess<Heap>::getFastCase()->allocateLarge(lock, alignment, size);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-NO_INLINE void* Allocator::allocateXLarge(size_t size)
-{
- std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
- return PerProcess<Heap>::getFastCase()->allocateXLarge(lock, size);
-}
-
</del><span class="cx"> NO_INLINE void* Allocator::allocateLogSizeClass(size_t size)
</span><span class="cx"> {
</span><span class="cx"> size_t sizeClass = bmalloc::sizeClass(size);
</span><span class="lines">@@ -232,9 +196,6 @@
</span><span class="cx"> if (size <= largeMax)
</span><span class="cx"> return allocateLarge(size);
</span><span class="cx">
</span><del>- if (size <= xLargeMax)
- return allocateXLarge(size);
-
</del><span class="cx"> BCRASH();
</span><span class="cx"> return nullptr;
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocAllocatorh"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/Allocator.h (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Allocator.h 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/Allocator.h 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -54,7 +54,6 @@
</span><span class="cx">
</span><span class="cx"> void* allocateLogSizeClass(size_t);
</span><span class="cx"> void* allocateLarge(size_t);
</span><del>- void* allocateXLarge(size_t);
</del><span class="cx">
</span><span class="cx"> void refillAllocator(BumpAllocator&, size_t sizeClass);
</span><span class="cx"> void refillAllocatorSlowCase(BumpAllocator&, size_t sizeClass);
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocBeginTagh"></a>
<div class="delfile"><h4>Deleted: trunk/Source/bmalloc/bmalloc/BeginTag.h (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/BeginTag.h 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/BeginTag.h 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -1,38 +0,0 @@
</span><del>-/*
- * Copyright (C) 2014, 2015 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 {
-};
-
-} // namespace bmalloc
-
-#endif // BeginTag_h
</del></span></pre></div>
<a id="trunkSourcebmallocbmallocBoundaryTagh"></a>
<div class="delfile"><h4>Deleted: trunk/Source/bmalloc/bmalloc/BoundaryTag.h (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/BoundaryTag.h 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/BoundaryTag.h 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -1,130 +0,0 @@
</span><del>-/*
- * Copyright (C) 2014-2016 Apple Inc. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * 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 "Range.h"
-#include "Sizes.h"
-#include "VMState.h"
-#include <cstring>
-
-namespace bmalloc {
-
-class BeginTag;
-class EndTag;
-class Chunk;
-class Range;
-
-class BoundaryTag {
-public:
- static Range init(Chunk*);
- static unsigned compactBegin(void*);
-
- bool isFree() { return m_isFree; }
- void setFree(bool isFree) { m_isFree = isFree; }
-
- bool isEnd() { return m_isEnd; }
- void setEnd(bool isEnd) { m_isEnd = isEnd; }
-
- VMState vmState() { return VMState(m_vmState); }
- void setVMState(VMState vmState) { m_vmState = static_cast<unsigned>(vmState); }
-
- bool isMarked() { return m_isMarked; }
- void setMarked(bool isMarked) { m_isMarked = isMarked; }
-
- bool isNull() { return !m_size; }
- void clear() { std::memset(this, 0, sizeof(*this)); }
-
- size_t size() { return m_size; }
- unsigned compactBegin() { return m_compactBegin; }
-
- void setRange(const Range&);
-
- bool isSentinel() { return !m_compactBegin; }
- void initSentinel();
-
- EndTag* prev();
- BeginTag* next();
-
-private:
- static const size_t flagBits = 5;
- static const size_t compactBeginBits = 4;
- static const size_t sizeBits = bitCount<unsigned>() - flagBits - compactBeginBits;
-
- static_assert(
- (1 << compactBeginBits) - 1 >= (largeMin - 1) / largeAlignment,
- "compactBegin must be encodable in a BoundaryTag.");
-
- static_assert(
- (1 << sizeBits) - 1 >= largeObjectMax,
- "largeObjectMax must be encodable in a BoundaryTag.");
-
- bool m_isFree: 1;
- bool m_isEnd: 1;
- unsigned m_vmState: 2;
- bool m_isMarked: 1;
- unsigned m_compactBegin: compactBeginBits;
- unsigned m_size: sizeBits;
-};
-
-inline unsigned BoundaryTag::compactBegin(void* object)
-{
- return static_cast<unsigned>(
- reinterpret_cast<uintptr_t>(mask(object, largeMin - 1)) / largeAlignment);
-}
-
-inline void BoundaryTag::setRange(const Range& range)
-{
- m_compactBegin = compactBegin(range.begin());
- BASSERT(this->compactBegin() == compactBegin(range.begin()));
-
- m_size = static_cast<unsigned>(range.size());
- BASSERT(this->size() == range.size());
-}
-
-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);
-}
-
-inline void BoundaryTag::initSentinel()
-{
- setRange(Range(nullptr, largeMin));
- setFree(false);
- setVMState(VMState::Virtual);
-}
-
-} // namespace bmalloc
-
-#endif // BoundaryTag_h
</del></span></pre></div>
<a id="trunkSourcebmallocbmallocChunkh"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/Chunk.h (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Chunk.h 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/Chunk.h 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -26,10 +26,7 @@
</span><span class="cx"> #ifndef Chunk_h
</span><span class="cx"> #define Chunk_h
</span><span class="cx">
</span><del>-#include "BeginTag.h"
-#include "EndTag.h"
</del><span class="cx"> #include "Object.h"
</span><del>-#include "ObjectType.h"
</del><span class="cx"> #include "Sizes.h"
</span><span class="cx"> #include "SmallLine.h"
</span><span class="cx"> #include "SmallPage.h"
</span><span class="lines">@@ -39,31 +36,11 @@
</span><span class="cx"> namespace bmalloc {
</span><span class="cx">
</span><span class="cx"> class Chunk {
</span><del>- // 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.
-
- static const size_t boundaryTagCount = chunkSize / largeMin;
- static_assert(boundaryTagCount > 2, "Chunk must have space for two sentinel boundary tags");
-
</del><span class="cx"> public:
</span><span class="cx"> static Chunk* get(void*);
</span><span class="cx">
</span><del>- static BeginTag* beginTag(void*);
- static EndTag* endTag(void*, size_t);
</del><ins>+ Chunk(std::lock_guard<StaticMutex>&);
</ins><span class="cx">
</span><del>- Chunk(std::lock_guard<StaticMutex>&, ObjectType);
-
</del><span class="cx"> size_t offset(void*);
</span><span class="cx">
</span><span class="cx"> char* object(size_t offset);
</span><span class="lines">@@ -73,33 +50,23 @@
</span><span class="cx"> char* bytes() { return reinterpret_cast<char*>(this); }
</span><span class="cx"> SmallLine* lines() { return m_lines.begin(); }
</span><span class="cx"> SmallPage* pages() { return m_pages.begin(); }
</span><del>- std::array<BoundaryTag, boundaryTagCount>& boundaryTags() { return m_boundaryTags; }
</del><span class="cx">
</span><del>- ObjectType objectType() { return m_objectType; }
-
</del><span class="cx"> private:
</span><del>- union {
- // The first few bytes of metadata cover the metadata region, so they're
- // not used. We can steal them to store m_objectType.
- ObjectType m_objectType;
- std::array<SmallLine, chunkSize / smallLineSize> m_lines;
- };
-
- union {
- // A chunk is either small or large for its lifetime, so we can union
- // small and large metadata, and then use one or the other at runtime.
- std::array<SmallPage, chunkSize / smallPageSize> m_pages;
- std::array<BoundaryTag, boundaryTagCount> m_boundaryTags;
- };
</del><ins>+ std::array<SmallLine, chunkSize / smallLineSize> m_lines;
+ std::array<SmallPage, chunkSize / smallPageSize> m_pages;
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> static_assert(sizeof(Chunk) + largeMax <= chunkSize, "largeMax is too big");
</span><span class="cx">
</span><del>-static_assert(sizeof(Chunk) / smallLineSize > sizeof(ObjectType),
- "Chunk::m_objectType overlaps with metadata");
</del><ins>+struct ChunkHash {
+ static unsigned hash(Chunk* key)
+ {
+ return static_cast<unsigned>(
+ reinterpret_cast<uintptr_t>(key) / chunkSize);
+ }
+};
</ins><span class="cx">
</span><del>-inline Chunk::Chunk(std::lock_guard<StaticMutex>&, ObjectType objectType)
- : m_objectType(objectType)
</del><ins>+inline Chunk::Chunk(std::lock_guard<StaticMutex>&)
</ins><span class="cx"> {
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -108,26 +75,6 @@
</span><span class="cx"> return static_cast<Chunk*>(mask(object, chunkMask));
</span><span class="cx"> }
</span><span class="cx">
</span><del>-inline BeginTag* Chunk::beginTag(void* object)
-{
- Chunk* 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* Chunk::endTag(void* object, size_t size)
-{
- Chunk* 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]);
-}
-
</del><span class="cx"> inline size_t Chunk::offset(void* object)
</span><span class="cx"> {
</span><span class="cx"> BASSERT(object >= this);
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocDeallocatorcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/Deallocator.cpp (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Deallocator.cpp 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/Deallocator.cpp 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -59,12 +59,6 @@
</span><span class="cx"> processObjectLog();
</span><span class="cx"> }
</span><span class="cx">
</span><del>-void Deallocator::deallocateXLarge(void* object)
-{
- std::unique_lock<StaticMutex> lock(PerProcess<Heap>::mutex());
- PerProcess<Heap>::getFastCase()->deallocateXLarge(lock, object);
-}
-
</del><span class="cx"> void Deallocator::processObjectLog(std::lock_guard<StaticMutex>& lock)
</span><span class="cx"> {
</span><span class="cx"> Heap* heap = PerProcess<Heap>::getFastCase();
</span><span class="lines">@@ -83,8 +77,6 @@
</span><span class="cx">
</span><span class="cx"> void Deallocator::deallocateSlowCase(void* object)
</span><span class="cx"> {
</span><del>- BASSERT(!deallocateFastCase(object));
-
</del><span class="cx"> if (!m_isBmallocEnabled) {
</span><span class="cx"> free(object);
</span><span class="cx"> return;
</span><span class="lines">@@ -93,11 +85,15 @@
</span><span class="cx"> if (!object)
</span><span class="cx"> return;
</span><span class="cx">
</span><del>- if (isXLarge(object))
- return deallocateXLarge(object);
</del><ins>+ std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
+ if (PerProcess<Heap>::getFastCase()->isLarge(lock, object)) {
+ PerProcess<Heap>::getFastCase()->deallocateLarge(lock, object);
+ return;
+ }
</ins><span class="cx">
</span><del>- BASSERT(m_objectLog.size() == m_objectLog.capacity());
- processObjectLog();
</del><ins>+ if (m_objectLog.size() == m_objectLog.capacity())
+ processObjectLog(lock);
+
</ins><span class="cx"> m_objectLog.push(object);
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocDeallocatorh"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/Deallocator.h (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Deallocator.h 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/Deallocator.h 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -51,16 +51,14 @@
</span><span class="cx"> bool deallocateFastCase(void*);
</span><span class="cx"> void deallocateSlowCase(void*);
</span><span class="cx">
</span><del>- void deallocateXLarge(void*);
-
</del><span class="cx"> FixedVector<void*, deallocatorLogCapacity> m_objectLog;
</span><span class="cx"> bool m_isBmallocEnabled;
</span><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> inline bool Deallocator::deallocateFastCase(void* object)
</span><span class="cx"> {
</span><del>- BASSERT(isXLarge(nullptr));
- if (isXLarge(object))
</del><ins>+ BASSERT(mightBeLarge(nullptr));
+ if (mightBeLarge(object))
</ins><span class="cx"> return false;
</span><span class="cx">
</span><span class="cx"> if (m_objectLog.size() == m_objectLog.capacity())
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocEndTagh"></a>
<div class="delfile"><h4>Deleted: trunk/Source/bmalloc/bmalloc/EndTag.h (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/EndTag.h 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/EndTag.h 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -1,52 +0,0 @@
</span><del>-/*
- * Copyright (C) 2014, 2015 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:
- void init(BeginTag*);
-};
-
-inline void EndTag::init(BeginTag* other)
-{
- // To save space, an object can have only one tag, representing both
- // its begin and its end. In that case, we must avoid initializing the
- // end tag, since there is no end tag.
- if (static_cast<BoundaryTag*>(this) == static_cast<BoundaryTag*>(other))
- return;
-
- std::memcpy(this, other, sizeof(BoundaryTag));
- setEnd(true);
-}
-
-} // namespace bmalloc
-
-#endif // EndTag_h
</del></span></pre></div>
<a id="trunkSourcebmallocbmallocFreeListcpp"></a>
<div class="delfile"><h4>Deleted: trunk/Source/bmalloc/bmalloc/FreeList.cpp (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/FreeList.cpp 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/FreeList.cpp 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -1,140 +0,0 @@
</span><del>-/*
- * Copyright (C) 2014-2016 Apple Inc. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * 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 "FreeList.h"
-#include "Chunk.h"
-#include "Vector.h"
-
-namespace bmalloc {
-
-// We don't eagerly remove invalidated entries from the free list when we merge
-// large objects. This means that the free list can contain invalid and/or
-// duplicate entries. (Repeating a merge-and-then-split produces a duplicate.)
-
-// To avoid infinite growth in invalid entries, we incrementally remove
-// invalid entries as we discover them during allocation, and we also garbage
-// collect the free list as it grows.
-
-LargeObject FreeList::takeGreedy(VMState::HasPhysical hasPhysical)
-{
- for (size_t i = 0; i < m_vector.size(); ++i) {
- LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
- if (!largeObject.isValidAndFree(hasPhysical, m_vector[i].size())) {
- m_vector.pop(i--);
- continue;
- }
-
- m_vector.pop(i--);
- return largeObject;
- }
-
- return LargeObject();
-}
-
-LargeObject FreeList::take(VMState::HasPhysical hasPhysical, size_t size)
-{
- LargeObject candidate;
- size_t candidateIndex;
- size_t begin = m_vector.size() > freeListSearchDepth ? m_vector.size() - freeListSearchDepth : 0;
- for (size_t i = begin; i < m_vector.size(); ++i) {
- LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
- if (!largeObject.isValidAndFree(hasPhysical, m_vector[i].size())) {
- m_vector.pop(i--);
- continue;
- }
-
- if (largeObject.size() < size)
- continue;
-
- if (!!candidate && candidate.begin() < largeObject.begin())
- continue;
-
- candidate = largeObject;
- candidateIndex = i;
- }
-
- if (!!candidate)
- m_vector.pop(candidateIndex);
- return candidate;
-}
-
-LargeObject FreeList::take(VMState::HasPhysical hasPhysical, size_t alignment, size_t size, size_t unalignedSize)
-{
- BASSERT(isPowerOfTwo(alignment));
- size_t alignmentMask = alignment - 1;
-
- LargeObject candidate;
- size_t candidateIndex;
- size_t begin = m_vector.size() > freeListSearchDepth ? m_vector.size() - freeListSearchDepth : 0;
- for (size_t i = begin; i < m_vector.size(); ++i) {
- LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
- if (!largeObject.isValidAndFree(hasPhysical, m_vector[i].size())) {
- m_vector.pop(i--);
- continue;
- }
-
- if (largeObject.size() < size)
- continue;
-
- if (test(largeObject.begin(), alignmentMask) && largeObject.size() < unalignedSize)
- continue;
-
- if (!!candidate && candidate.begin() < largeObject.begin())
- continue;
-
- candidate = largeObject;
- candidateIndex = i;
- }
-
- if (!!candidate)
- m_vector.pop(candidateIndex);
- return candidate;
-}
-
-void FreeList::removeInvalidAndDuplicateEntries(VMState::HasPhysical hasPhysical)
-{
- for (size_t i = 0; i < m_vector.size(); ++i) {
- LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
- if (!largeObject.isValidAndFree(hasPhysical, m_vector[i].size())) {
- m_vector.pop(i--);
- continue;
- }
-
- largeObject.setMarked(false);
- }
-
- for (size_t i = 0; i < m_vector.size(); ++i) {
- LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
- if (largeObject.isMarked()) {
- m_vector.pop(i--);
- continue;
- }
-
- largeObject.setMarked(true);
- }
-}
-
-
-} // namespace bmalloc
</del></span></pre></div>
<a id="trunkSourcebmallocbmallocFreeListh"></a>
<div class="delfile"><h4>Deleted: trunk/Source/bmalloc/bmalloc/FreeList.h (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/FreeList.h 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/FreeList.h 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -1,75 +0,0 @@
</span><del>-/*
- * Copyright (C) 2014-2016 Apple Inc. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * 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 FreeList_h
-#define FreeList_h
-
-#include "LargeObject.h"
-#include "Vector.h"
-
-namespace bmalloc {
-
-// Helper object for SegregatedFreeList.
-
-class FreeList {
-public:
- FreeList();
-
- void push(VMState::HasPhysical, const LargeObject&);
-
- LargeObject take(VMState::HasPhysical, size_t);
- LargeObject take(VMState::HasPhysical, size_t alignment, size_t, size_t unalignedSize);
-
- LargeObject takeGreedy(VMState::HasPhysical);
-
- void removeInvalidAndDuplicateEntries(VMState::HasPhysical);
-
-private:
- Vector<Range> m_vector;
- size_t m_limit;
-};
-
-inline FreeList::FreeList()
- : m_vector()
- , m_limit(freeListSearchDepth)
-{
-}
-
-inline void FreeList::push(VMState::HasPhysical hasPhysical, const LargeObject& largeObject)
-{
- BASSERT(largeObject.isFree());
- BASSERT(largeObject.vmState().hasPhysical() == static_cast<bool>(hasPhysical));
- BASSERT(!largeObject.prevCanMerge());
- BASSERT(!largeObject.nextCanMerge());
- if (m_vector.size() == m_limit) {
- removeInvalidAndDuplicateEntries(hasPhysical);
- m_limit = std::max(m_vector.size() * freeListGrowFactor, freeListSearchDepth);
- }
- m_vector.push(largeObject.range());
-}
-
-} // namespace bmalloc
-
-#endif // FreeList_h
</del></span></pre></div>
<a id="trunkSourcebmallocbmallocHeapcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/Heap.cpp (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Heap.cpp 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/Heap.cpp 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -26,7 +26,6 @@
</span><span class="cx"> #include "Heap.h"
</span><span class="cx"> #include "BumpAllocator.h"
</span><span class="cx"> #include "Chunk.h"
</span><del>-#include "LargeObject.h"
</del><span class="cx"> #include "PerProcess.h"
</span><span class="cx"> #include "SmallLine.h"
</span><span class="cx"> #include "SmallPage.h"
</span><span class="lines">@@ -36,13 +35,11 @@
</span><span class="cx">
</span><span class="cx"> Heap::Heap(std::lock_guard<StaticMutex>&)
</span><span class="cx"> : m_vmPageSizePhysical(vmPageSizePhysical())
</span><del>- , m_largeObjects(VMState::HasPhysical::True)
</del><span class="cx"> , m_isAllocatingPages(false)
</span><span class="cx"> , m_scavenger(*this, &Heap::concurrentScavenge)
</span><span class="cx"> {
</span><span class="cx"> RELEASE_BASSERT(vmPageSizePhysical() >= smallPageSize);
</span><span class="cx"> RELEASE_BASSERT(vmPageSize() >= vmPageSizePhysical());
</span><del>- RELEASE_BASSERT(xLargeAlignment >= vmPageSize());
</del><span class="cx">
</span><span class="cx"> initializeLineMetadata();
</span><span class="cx"> initializePageMetadata();
</span><span class="lines">@@ -91,7 +88,7 @@
</span><span class="cx"> for (size_t pageSize = m_vmPageSizePhysical;
</span><span class="cx"> pageSize < pageSizeMax;
</span><span class="cx"> pageSize += m_vmPageSizePhysical) {
</span><del>- RELEASE_BASSERT(pageSize <= largeObjectMax);
</del><ins>+ RELEASE_BASSERT(pageSize <= chunkSize / 2);
</ins><span class="cx"> size_t waste = pageSize % size;
</span><span class="cx"> if (waste <= pageSize / pageSizeWasteFactor)
</span><span class="cx"> return pageSize;
</span><span class="lines">@@ -116,7 +113,6 @@
</span><span class="cx">
</span><span class="cx"> scavengeSmallPages(lock, sleepDuration);
</span><span class="cx"> scavengeLargeObjects(lock, sleepDuration);
</span><del>- scavengeXLargeObjects(lock, sleepDuration);
</del><span class="cx">
</span><span class="cx"> sleep(lock, sleepDuration);
</span><span class="cx"> }
</span><span class="lines">@@ -135,159 +131,18 @@
</span><span class="cx">
</span><span class="cx"> void Heap::scavengeLargeObjects(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
</span><span class="cx"> {
</span><del>- while (LargeObject largeObject = m_largeObjects.takeGreedy()) {
- m_vmHeap.deallocateLargeObject(lock, largeObject);
- waitUntilFalse(lock, sleepDuration, m_isAllocatingPages);
- }
-}
-
-void Heap::scavengeXLargeObjects(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
-{
- while (XLargeRange range = m_xLargeMap.takePhysical()) {
</del><ins>+ while (XLargeRange range = m_largeFree.removePhysical()) {
</ins><span class="cx"> lock.unlock();
</span><span class="cx"> vmDeallocatePhysicalPagesSloppy(range.begin(), range.size());
</span><span class="cx"> lock.lock();
</span><span class="cx">
</span><del>- range.setVMState(VMState::Virtual);
- m_xLargeMap.addVirtual(range);
</del><ins>+ range.setPhysicalSize(0);
+ m_largeFree.add(range);
</ins><span class="cx">
</span><span class="cx"> waitUntilFalse(lock, sleepDuration, m_isAllocatingPages);
</span><span class="cx"> }
</span><del>-
- m_xLargeMap.shrinkToFit();
</del><span class="cx"> }
</span><span class="cx">
</span><del>-inline LargeObject& Heap::splitAndAllocate(std::lock_guard<StaticMutex>& lock, LargeObject& largeObject, size_t size)
-{
- BASSERT(largeObject.isFree());
-
- LargeObject nextLargeObject;
-
- if (largeObject.size() - size >= largeMin) {
- std::pair<LargeObject, LargeObject> split = largeObject.split(size);
- largeObject = split.first;
- nextLargeObject = split.second;
- }
-
- largeObject.setFree(false);
- Object object(largeObject.begin());
- object.line()->ref(lock);
- BASSERT(object.chunk()->objectType() == ObjectType::Large);
-
- if (nextLargeObject) {
- BASSERT(!nextLargeObject.nextCanMerge());
- m_largeObjects.insert(nextLargeObject);
- }
-
- return largeObject;
-}
-
-inline LargeObject& Heap::splitAndAllocate(std::lock_guard<StaticMutex>& lock, LargeObject& largeObject, size_t alignment, size_t size)
-{
- LargeObject prevLargeObject;
- LargeObject nextLargeObject;
-
- size_t alignmentMask = alignment - 1;
- if (test(largeObject.begin(), alignmentMask)) {
- size_t prefixSize = roundUpToMultipleOf(alignment, largeObject.begin() + largeMin) - largeObject.begin();
- std::pair<LargeObject, LargeObject> pair = largeObject.split(prefixSize);
- prevLargeObject = pair.first;
- largeObject = pair.second;
- }
-
- BASSERT(largeObject.isFree());
-
- if (largeObject.size() - size >= largeMin) {
- std::pair<LargeObject, LargeObject> split = largeObject.split(size);
- largeObject = split.first;
- nextLargeObject = split.second;
- }
-
- largeObject.setFree(false);
- Object object(largeObject.begin());
- object.line()->ref(lock);
- BASSERT(object.chunk()->objectType() == ObjectType::Large);
-
- if (prevLargeObject) {
- LargeObject merged = prevLargeObject.merge();
- m_largeObjects.insert(merged);
- }
-
- if (nextLargeObject) {
- LargeObject merged = nextLargeObject.merge();
- m_largeObjects.insert(merged);
- }
-
- return largeObject;
-}
-
-void* Heap::allocateLarge(std::lock_guard<StaticMutex>& lock, size_t size)
-{
- BASSERT(size <= largeMax);
- BASSERT(size >= largeMin);
- BASSERT(size == roundUpToMultipleOf<largeAlignment>(size));
-
- LargeObject largeObject = m_largeObjects.take(size);
- if (!largeObject)
- largeObject = m_vmHeap.allocateLargeObject(lock, size);
-
- if (largeObject.vmState().hasVirtual()) {
- m_isAllocatingPages = true;
- // We commit before we split in order to avoid split/merge commit/decommit churn.
- vmAllocatePhysicalPagesSloppy(largeObject.begin(), largeObject.size());
- largeObject.setVMState(VMState::Physical);
- }
-
- largeObject = splitAndAllocate(lock, largeObject, size);
-
- return largeObject.begin();
-}
-
-void* Heap::allocateLarge(std::lock_guard<StaticMutex>& lock, size_t alignment, size_t size, size_t unalignedSize)
-{
- BASSERT(size <= largeMax);
- BASSERT(size >= largeMin);
- BASSERT(size == roundUpToMultipleOf<largeAlignment>(size));
- BASSERT(unalignedSize <= largeMax);
- BASSERT(unalignedSize >= largeMin);
- BASSERT(unalignedSize == roundUpToMultipleOf<largeAlignment>(unalignedSize));
- BASSERT(alignment <= chunkSize / 2);
- BASSERT(alignment >= largeAlignment);
- BASSERT(isPowerOfTwo(alignment));
-
- LargeObject largeObject = m_largeObjects.take(alignment, size, unalignedSize);
- if (!largeObject)
- largeObject = m_vmHeap.allocateLargeObject(lock, alignment, size, unalignedSize);
-
- if (largeObject.vmState().hasVirtual()) {
- m_isAllocatingPages = true;
- // We commit before we split in order to avoid split/merge commit/decommit churn.
- vmAllocatePhysicalPagesSloppy(largeObject.begin(), largeObject.size());
- largeObject.setVMState(VMState::Physical);
- }
-
- largeObject = splitAndAllocate(lock, largeObject, alignment, size);
-
- return largeObject.begin();
-}
-
-void Heap::shrinkLarge(std::lock_guard<StaticMutex>& lock, LargeObject& largeObject, size_t newSize)
-{
- std::pair<LargeObject, LargeObject> split = largeObject.split(newSize);
- deallocateLarge(lock, split.second);
-}
-
-void Heap::deallocateLarge(std::lock_guard<StaticMutex>&, const LargeObject& largeObject)
-{
- BASSERT(!largeObject.isFree());
- BASSERT(Object(largeObject.begin()).chunk()->objectType() == ObjectType::Large);
- largeObject.setFree(true);
-
- LargeObject merged = largeObject.merge();
- m_largeObjects.insert(merged);
- m_scavenger.run();
-}
-
</del><span class="cx"> SmallPage* Heap::allocateSmallPage(std::lock_guard<StaticMutex>& lock, size_t sizeClass)
</span><span class="cx"> {
</span><span class="cx"> if (!m_smallPagesWithFreeLines[sizeClass].isEmpty())
</span><span class="lines">@@ -299,7 +154,10 @@
</span><span class="cx"> return m_smallPages[pageClass].pop();
</span><span class="cx">
</span><span class="cx"> m_isAllocatingPages = true;
</span><del>- return m_vmHeap.allocateSmallPage(lock, pageClass);
</del><ins>+
+ SmallPage* page = m_vmHeap.allocateSmallPage(lock, pageClass);
+ m_objectTypes.set(Chunk::get(page), ObjectType::Small);
+ return page;
</ins><span class="cx"> }();
</span><span class="cx">
</span><span class="cx"> page->setSizeClass(sizeClass);
</span><span class="lines">@@ -310,10 +168,8 @@
</span><span class="cx"> {
</span><span class="cx"> BASSERT(!object.line()->refCount(lock));
</span><span class="cx"> SmallPage* page = object.page();
</span><del>- if (object.chunk()->objectType() == ObjectType::Large)
- return deallocateLarge(lock, LargeObject(object.begin()));
-
</del><span class="cx"> page->deref(lock);
</span><ins>+
</ins><span class="cx"> if (!page->hasFreeLines(lock)) {
</span><span class="cx"> page->setHasFreeLines(lock, true);
</span><span class="cx"> m_smallPagesWithFreeLines[page->sizeClass()].push(page);
</span><span class="lines">@@ -446,18 +302,6 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>-void* Heap::allocateXLarge(std::lock_guard<StaticMutex>& lock, size_t alignment, size_t size)
-{
- void* result = tryAllocateXLarge(lock, alignment, size);
- RELEASE_BASSERT(result);
- return result;
-}
-
-void* Heap::allocateXLarge(std::lock_guard<StaticMutex>& lock, size_t size)
-{
- return allocateXLarge(lock, alignment, size);
-}
-
</del><span class="cx"> XLargeRange Heap::splitAndAllocate(XLargeRange& range, size_t alignment, size_t size)
</span><span class="cx"> {
</span><span class="cx"> XLargeRange prev;
</span><span class="lines">@@ -471,76 +315,85 @@
</span><span class="cx"> range = pair.second;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- if (range.size() - size >= xLargeAlignment) {
- size_t alignedSize = roundUpToMultipleOf<xLargeAlignment>(size);
- std::pair<XLargeRange, XLargeRange> pair = range.split(alignedSize);
</del><ins>+ if (range.size() - size > size / pageSizeWasteFactor) {
+ std::pair<XLargeRange, XLargeRange> pair = range.split(size);
</ins><span class="cx"> range = pair.first;
</span><span class="cx"> next = pair.second;
</span><span class="cx"> }
</span><ins>+
+ if (range.physicalSize() < range.size()) {
+ m_isAllocatingPages = true;
</ins><span class="cx">
</span><del>- // At this point our range might contain an unused tail fragment. This is
- // common. We can't allocate the tail fragment because it's aligned to less
- // than xLargeAlignment. So, we pair the allocation with its tail fragment
- // in the allocated list. This is an important optimization because it
- // keeps the free list short, speeding up allocation and merging.
-
- std::pair<XLargeRange, XLargeRange> allocated = range.split(roundUpToMultipleOf(m_vmPageSizePhysical, size));
- if (allocated.first.vmState().hasVirtual()) {
- vmAllocatePhysicalPagesSloppy(allocated.first.begin(), allocated.first.size());
- allocated.first.setVMState(VMState::Physical);
</del><ins>+ vmAllocatePhysicalPagesSloppy(range.begin() + range.physicalSize(), range.size() - range.physicalSize());
+ range.setPhysicalSize(range.size());
</ins><span class="cx"> }
</span><ins>+
+ if (prev)
+ m_largeFree.add(prev);
</ins><span class="cx">
</span><del>- m_xLargeMap.addAllocated(prev, allocated, next);
- return allocated.first;
</del><ins>+ if (next)
+ m_largeFree.add(next);
+
+ m_objectTypes.set(Chunk::get(range.begin()), ObjectType::Large);
+
+ m_largeAllocated.set(range.begin(), range.size());
+ return range;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-void* Heap::tryAllocateXLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t size)
</del><ins>+void* Heap::tryAllocateLarge(std::lock_guard<StaticMutex>& lock, size_t alignment, size_t size)
</ins><span class="cx"> {
</span><ins>+ BASSERT(size <= largeMax);
+ BASSERT(size <= largeMax / 2);
</ins><span class="cx"> BASSERT(isPowerOfTwo(alignment));
</span><del>- BASSERT(alignment < xLargeMax);
</del><span class="cx">
</span><del>- m_isAllocatingPages = true;
</del><ins>+ size = size ? roundUpToMultipleOf(largeAlignment, size) : largeAlignment;
+ alignment = roundUpToMultipleOf<largeAlignment>(alignment);
</ins><span class="cx">
</span><del>- size = std::max(m_vmPageSizePhysical, size);
- alignment = roundUpToMultipleOf<xLargeAlignment>(alignment);
-
- XLargeRange range = m_xLargeMap.takeFree(alignment, size);
</del><ins>+ XLargeRange range = m_largeFree.remove(alignment, size);
</ins><span class="cx"> if (!range) {
</span><del>- // We allocate VM in aligned multiples to increase the chances that
- // the OS will provide contiguous ranges that we can merge.
- size_t alignedSize = roundUpToMultipleOf<xLargeAlignment>(size);
-
- void* begin = tryVMAllocate(alignment, alignedSize);
- if (!begin)
</del><ins>+ range = m_vmHeap.tryAllocateLargeChunk(lock, alignment, size);
+ if (!range)
</ins><span class="cx"> return nullptr;
</span><del>- range = XLargeRange(begin, alignedSize, VMState::Virtual);
</del><ins>+
+ m_largeFree.add(range);
+ range = m_largeFree.remove(alignment, size);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> return splitAndAllocate(range, alignment, size).begin();
</span><span class="cx"> }
</span><span class="cx">
</span><del>-size_t Heap::xLargeSize(std::unique_lock<StaticMutex>&, void* object)
</del><ins>+void* Heap::allocateLarge(std::lock_guard<StaticMutex>& lock, size_t alignment, size_t size)
</ins><span class="cx"> {
</span><del>- return m_xLargeMap.getAllocated(object).size();
</del><ins>+ void* result = tryAllocateLarge(lock, alignment, size);
+ RELEASE_BASSERT(result);
+ return result;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-void Heap::shrinkXLarge(std::unique_lock<StaticMutex>&, const Range& object, size_t newSize)
</del><ins>+bool Heap::isLarge(std::lock_guard<StaticMutex>&, void* object)
</ins><span class="cx"> {
</span><ins>+ return m_objectTypes.get(Object(object).chunk()) == ObjectType::Large;
+}
+
+size_t Heap::largeSize(std::lock_guard<StaticMutex>&, void* object)
+{
+ return m_largeAllocated.get(object);
+}
+
+void Heap::shrinkLarge(std::lock_guard<StaticMutex>&, const Range& object, size_t newSize)
+{
</ins><span class="cx"> BASSERT(object.size() > newSize);
</span><span class="cx">
</span><del>- if (object.size() - newSize < m_vmPageSizePhysical)
- return;
-
- XLargeRange range = m_xLargeMap.takeAllocated(object.begin());
- splitAndAllocate(range, xLargeAlignment, newSize);
</del><ins>+ size_t size = m_largeAllocated.remove(object.begin());
+ XLargeRange range = XLargeRange(object, size);
+ splitAndAllocate(range, alignment, newSize);
</ins><span class="cx">
</span><span class="cx"> m_scavenger.run();
</span><span class="cx"> }
</span><span class="cx">
</span><del>-void Heap::deallocateXLarge(std::unique_lock<StaticMutex>&, void* object)
</del><ins>+void Heap::deallocateLarge(std::lock_guard<StaticMutex>&, void* object)
</ins><span class="cx"> {
</span><del>- XLargeRange range = m_xLargeMap.takeAllocated(object);
- m_xLargeMap.addFree(range);
</del><ins>+ size_t size = m_largeAllocated.remove(object);
+ m_largeFree.add(XLargeRange(object, size, size));
</ins><span class="cx">
</span><span class="cx"> m_scavenger.run();
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocHeaph"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/Heap.h (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Heap.h 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/Heap.h 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -30,9 +30,9 @@
</span><span class="cx"> #include "Environment.h"
</span><span class="cx"> #include "LineMetadata.h"
</span><span class="cx"> #include "List.h"
</span><ins>+#include "Map.h"
</ins><span class="cx"> #include "Mutex.h"
</span><span class="cx"> #include "Object.h"
</span><del>-#include "SegregatedFreeList.h"
</del><span class="cx"> #include "SmallLine.h"
</span><span class="cx"> #include "SmallPage.h"
</span><span class="cx"> #include "VMHeap.h"
</span><span class="lines">@@ -56,20 +56,25 @@
</span><span class="cx"> void allocateSmallBumpRanges(std::lock_guard<StaticMutex>&, size_t sizeClass, BumpAllocator&, BumpRangeCache&);
</span><span class="cx"> void derefSmallLine(std::lock_guard<StaticMutex>&, Object);
</span><span class="cx">
</span><del>- void* allocateLarge(std::lock_guard<StaticMutex>&, size_t);
- void* allocateLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t, size_t unalignedSize);
- void shrinkLarge(std::lock_guard<StaticMutex>&, LargeObject&, size_t);
</del><ins>+ void* allocateLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t);
+ void* tryAllocateLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t);
+ void deallocateLarge(std::lock_guard<StaticMutex>&, void*);
</ins><span class="cx">
</span><del>- void* allocateXLarge(std::lock_guard<StaticMutex>&, size_t);
- void* allocateXLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t);
- void* tryAllocateXLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t);
- size_t xLargeSize(std::unique_lock<StaticMutex>&, void*);
- void shrinkXLarge(std::unique_lock<StaticMutex>&, const Range&, size_t newSize);
- void deallocateXLarge(std::unique_lock<StaticMutex>&, void*);
</del><ins>+ bool isLarge(std::lock_guard<StaticMutex>&, void*);
+ size_t largeSize(std::lock_guard<StaticMutex>&, void*);
+ void shrinkLarge(std::lock_guard<StaticMutex>&, const Range&, size_t);
</ins><span class="cx">
</span><span class="cx"> void scavenge(std::unique_lock<StaticMutex>&, std::chrono::milliseconds sleepDuration);
</span><span class="cx">
</span><span class="cx"> private:
</span><ins>+ struct LargeObjectHash {
+ static unsigned hash(void* key)
+ {
+ return static_cast<unsigned>(
+ reinterpret_cast<uintptr_t>(key) / smallMax);
+ }
+ };
+
</ins><span class="cx"> ~Heap() = delete;
</span><span class="cx">
</span><span class="cx"> void initializeLineMetadata();
</span><span class="lines">@@ -83,10 +88,7 @@
</span><span class="cx"> SmallPage* allocateSmallPage(std::lock_guard<StaticMutex>&, size_t sizeClass);
</span><span class="cx">
</span><span class="cx"> void deallocateSmallLine(std::lock_guard<StaticMutex>&, Object);
</span><del>- void deallocateLarge(std::lock_guard<StaticMutex>&, const LargeObject&);
</del><span class="cx">
</span><del>- LargeObject& splitAndAllocate(std::lock_guard<StaticMutex>&, LargeObject&, size_t);
- LargeObject& splitAndAllocate(std::lock_guard<StaticMutex>&, LargeObject&, size_t, size_t);
</del><span class="cx"> void mergeLarge(BeginTag*&, EndTag*&, Range&);
</span><span class="cx"> void mergeLargeLeft(EndTag*&, BeginTag*&, Range&, bool& inVMHeap);
</span><span class="cx"> void mergeLargeRight(EndTag*&, BeginTag*&, Range&, bool& inVMHeap);
</span><span class="lines">@@ -96,7 +98,6 @@
</span><span class="cx"> void concurrentScavenge();
</span><span class="cx"> void scavengeSmallPages(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
</span><span class="cx"> void scavengeLargeObjects(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
</span><del>- void scavengeXLargeObjects(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
</del><span class="cx">
</span><span class="cx"> size_t m_vmPageSizePhysical;
</span><span class="cx"> Vector<LineMetadata> m_smallLineMetadata;
</span><span class="lines">@@ -105,10 +106,11 @@
</span><span class="cx"> std::array<List<SmallPage>, sizeClassCount> m_smallPagesWithFreeLines;
</span><span class="cx"> std::array<List<SmallPage>, pageClassCount> m_smallPages;
</span><span class="cx">
</span><del>- SegregatedFreeList m_largeObjects;
-
- XLargeMap m_xLargeMap;
</del><ins>+ Map<void*, size_t, LargeObjectHash> m_largeAllocated;
+ XLargeMap m_largeFree;
</ins><span class="cx">
</span><ins>+ Map<Chunk*, ObjectType, ChunkHash> m_objectTypes;
+
</ins><span class="cx"> bool m_isAllocatingPages;
</span><span class="cx"> AsyncTask<Heap, decltype(&Heap::concurrentScavenge)> m_scavenger;
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocLargeObjecth"></a>
<div class="delfile"><h4>Deleted: trunk/Source/bmalloc/bmalloc/LargeObject.h (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/LargeObject.h 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/LargeObject.h 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -1,275 +0,0 @@
</span><del>-/*
- * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * 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 LargeObject_h
-#define LargeObject_h
-
-#include "BeginTag.h"
-#include "Chunk.h"
-#include "EndTag.h"
-#include "Range.h"
-
-namespace bmalloc {
-
-class LargeObject {
-public:
- LargeObject();
- LargeObject(void*);
-
- enum DoNotValidateTag { DoNotValidate };
- LargeObject(DoNotValidateTag, void*);
-
- operator bool() { return !!*this; }
- bool operator!() { return !m_object; }
-
- char* begin() const { return static_cast<char*>(m_object); }
- char* end() const { return begin() + size(); }
- size_t size() const { return m_beginTag->size(); }
- Range range() const { return Range(m_object, size()); }
-
- void setFree(bool) const;
- bool isFree() const;
-
- bool prevCanMerge() const;
- bool nextCanMerge() const;
-
- VMState vmState() const;
- void setVMState(VMState) const;
-
- bool isMarked() const;
- void setMarked(bool) const;
-
- bool isValidAndFree(VMState::HasPhysical, size_t) const;
-
- LargeObject merge() const;
- std::pair<LargeObject, LargeObject> split(size_t) const;
-
-private:
- LargeObject(BeginTag*, EndTag*, void*);
-
- void validate() const;
- void validateSelf() const;
-
- BeginTag* m_beginTag;
- EndTag* m_endTag;
- void* m_object;
-};
-
-inline LargeObject::LargeObject()
- : m_beginTag(nullptr)
- , m_endTag(nullptr)
- , m_object(nullptr)
-{
-}
-
-inline LargeObject::LargeObject(void* object)
- : m_beginTag(Chunk::beginTag(object))
- , m_endTag(Chunk::endTag(object, m_beginTag->size()))
- , m_object(object)
-{
- validate();
-}
-
-inline LargeObject::LargeObject(DoNotValidateTag, void* object)
- : m_beginTag(Chunk::beginTag(object))
- , m_endTag(Chunk::endTag(object, m_beginTag->size()))
- , m_object(object)
-{
-}
-
-inline LargeObject::LargeObject(BeginTag* beginTag, EndTag* endTag, void* object)
- : m_beginTag(beginTag)
- , m_endTag(endTag)
- , m_object(object)
-{
-}
-
-inline void LargeObject::setFree(bool isFree) const
-{
- validate();
- m_beginTag->setFree(isFree);
- m_endTag->setFree(isFree);
-}
-
-inline bool LargeObject::isFree() const
-{
- validate();
- return m_beginTag->isFree();
-}
-
-inline bool LargeObject::prevCanMerge() const
-{
- return m_beginTag->prev()->isFree();
-}
-
-inline bool LargeObject::nextCanMerge() const
-{
- return m_endTag->next()->isFree();
-}
-
-inline VMState LargeObject::vmState() const
-{
- validate();
- return m_beginTag->vmState();
-}
-
-inline void LargeObject::setVMState(VMState vmState) const
-{
- validate();
- m_beginTag->setVMState(vmState);
- m_endTag->setVMState(vmState);
-}
-
-inline bool LargeObject::isMarked() const
-{
- validate();
- return m_beginTag->isMarked();
-}
-
-inline void LargeObject::setMarked(bool isMarked) const
-{
- validate();
- m_beginTag->setMarked(isMarked);
- m_endTag->setMarked(isMarked);
-}
-
-inline bool LargeObject::isValidAndFree(VMState::HasPhysical hasPhysical, size_t expectedSize) const
-{
- if (!m_beginTag->isFree())
- return false;
-
- if (m_beginTag->isEnd())
- return false;
-
- if (m_beginTag->size() != expectedSize)
- return false;
-
- if (m_beginTag->compactBegin() != BoundaryTag::compactBegin(m_object))
- return false;
-
- if (m_beginTag->vmState().hasPhysical() != static_cast<bool>(hasPhysical))
- return false;
-
- return true;
-}
-
-inline LargeObject LargeObject::merge() const
-{
- validate();
- BASSERT(isFree());
-
- BeginTag* beginTag = m_beginTag;
- EndTag* endTag = m_endTag;
- Range range = this->range();
- VMState vmState = this->vmState();
-
- EndTag* prev = beginTag->prev();
- if (prev->isFree()) {
- vmState.merge(prev->vmState());
- Range left(range.begin() - prev->size(), prev->size());
- range = Range(left.begin(), left.size() + range.size());
-
- prev->clear();
- beginTag->clear();
-
- beginTag = Chunk::beginTag(range.begin());
- }
-
- BeginTag* next = endTag->next();
- if (next->isFree()) {
- vmState.merge(next->vmState());
- Range right(range.end(), next->size());
- range = Range(range.begin(), range.size() + right.size());
-
- endTag->clear();
- next->clear();
-
- endTag = Chunk::endTag(range.begin(), range.size());
- }
-
- beginTag->setRange(range);
- beginTag->setFree(true);
- beginTag->setVMState(vmState);
- endTag->init(beginTag);
-
- return LargeObject(beginTag, endTag, range.begin());
-}
-
-inline std::pair<LargeObject, LargeObject> LargeObject::split(size_t size) const
-{
- BASSERT(size <= this->size());
- Range split(begin(), size);
- Range leftover = Range(split.end(), this->size() - size);
- BASSERT(leftover.size() >= largeMin);
-
- BeginTag* splitBeginTag = m_beginTag;
- EndTag* splitEndTag = Chunk::endTag(split.begin(), size);
-
- BeginTag* leftoverBeginTag = Chunk::beginTag(leftover.begin());
- EndTag* leftoverEndTag = m_endTag;
-
- splitBeginTag->setRange(split);
- splitEndTag->init(splitBeginTag);
-
- *leftoverBeginTag = *splitBeginTag;
- leftoverBeginTag->setRange(leftover);
- leftoverEndTag->init(leftoverBeginTag);
-
- return std::make_pair(
- LargeObject(splitBeginTag, splitEndTag, split.begin()),
- LargeObject(leftoverBeginTag, leftoverEndTag, leftover.begin()));
-}
-
-inline void LargeObject::validateSelf() const
-{
- BASSERT(!m_beginTag->isEnd());
- BASSERT(m_endTag->isEnd() || static_cast<BoundaryTag*>(m_endTag) == static_cast<BoundaryTag*>(m_beginTag));
-
- BASSERT(size() >= largeMin);
-
- BASSERT(m_beginTag->size() == m_endTag->size());
- BASSERT(m_beginTag->isFree() == m_endTag->isFree());
- BASSERT(m_beginTag->vmState() == m_endTag->vmState());
- BASSERT(m_beginTag->isMarked() == m_endTag->isMarked());
-}
-
-inline void LargeObject::validate() const
-{
- if (!m_beginTag->prev()->isSentinel()) {
- LargeObject prev(DoNotValidate, begin() - m_beginTag->prev()->size());
- prev.validateSelf();
- }
-
- validateSelf();
-
- if (!m_endTag->next()->isSentinel()) {
- LargeObject next(DoNotValidate, begin() + size());
- next.validateSelf();
- }
-}
-
-} // namespace bmalloc
-
-#endif // LargeObject_h
</del></span></pre></div>
<a id="trunkSourcebmallocbmallocMaph"></a>
<div class="addfile"><h4>Added: trunk/Source/bmalloc/bmalloc/Map.h (0 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Map.h (rev 0)
+++ trunk/Source/bmalloc/bmalloc/Map.h 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -0,0 +1,134 @@
</span><ins>+/*
+ * Copyright (C) 2016 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * 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 Map_h
+#define Map_h
+
+#include "Inline.h"
+#include "Sizes.h"
+#include "Vector.h"
+
+namespace bmalloc {
+
+class SmallPage;
+
+template<typename Key, typename Value, typename Hash> class Map {
+ static_assert(std::is_trivially_destructible<Key>::value, "Map must have a trivial destructor.");
+ static_assert(std::is_trivially_destructible<Value>::value, "Map must have a trivial destructor.");
+public:
+ struct Bucket {
+ Key key;
+ Value value;
+ };
+
+ size_t size() { return m_keyCount; }
+ size_t capacity() { return m_table.size(); }
+
+ // key must be in the map.
+ Value& get(const Key& key)
+ {
+ auto& bucket = find(key, [&](const Bucket& bucket) { return bucket.key == key; });
+ return bucket.value;
+ }
+
+ void set(const Key& key, const Value& value)
+ {
+ if (shouldGrow())
+ rehash();
+
+ auto& bucket = find(key, [&](const Bucket& bucket) { return !bucket.key || bucket.key == key; });
+ if (!bucket.key) {
+ bucket.key = key;
+ ++m_keyCount;
+ }
+ bucket.value = value;
+ }
+
+ // key must be in the map.
+ Value remove(const Key& key)
+ {
+ if (shouldShrink())
+ rehash();
+
+ auto& bucket = find(key, [&](const Bucket& bucket) { return bucket.key == key; });
+ Value value = bucket.value;
+ bucket.key = Key();
+ --m_keyCount;
+ return value;
+ }
+
+private:
+ static const unsigned minCapacity = 16;
+ static const unsigned maxLoad = 2;
+ static const unsigned rehashLoad = 4;
+ static const unsigned minLoad = 8;
+
+ bool shouldGrow() { return m_keyCount * maxLoad >= capacity(); }
+ bool shouldShrink() { return m_keyCount * minLoad <= capacity() && capacity() > minCapacity; }
+
+ void rehash();
+
+ template<typename Predicate>
+ Bucket& find(const Key& key, const Predicate& predicate)
+ {
+ for (unsigned h = Hash::hash(key); ; ++h) {
+ unsigned i = h & m_tableMask;
+
+ Bucket& bucket = m_table[i];
+ if (predicate(bucket))
+ return bucket;
+ }
+ }
+
+ unsigned m_keyCount;
+ unsigned m_tableMask;
+ Vector<Bucket> m_table;
+};
+
+template<typename Key, typename Value, typename Hash>
+void Map<Key, Value, Hash>::rehash()
+{
+ auto oldTable = std::move(m_table);
+
+ size_t newCapacity = std::max(minCapacity, m_keyCount * rehashLoad);
+ m_table.resize(newCapacity);
+
+ m_keyCount = 0;
+ m_tableMask = newCapacity - 1;
+
+ for (auto& bucket : oldTable) {
+ if (!bucket.key)
+ continue;
+
+ BASSERT(!shouldGrow());
+ set(bucket.key, bucket.value);
+ }
+}
+
+template<typename Key, typename Value, typename Hash> const unsigned Map<Key, Value, Hash>::minCapacity;
+
+} // namespace bmalloc
+
+#endif // Map_h
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocObjecth"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/Object.h (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Object.h 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/Object.h 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -26,6 +26,8 @@
</span><span class="cx"> #ifndef Object_h
</span><span class="cx"> #define Object_h
</span><span class="cx">
</span><ins>+#include <cstddef>
+
</ins><span class="cx"> namespace bmalloc {
</span><span class="cx">
</span><span class="cx"> class Chunk;
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocObjectTypecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/ObjectType.cpp (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/ObjectType.cpp 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/ObjectType.cpp 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -26,16 +26,24 @@
</span><span class="cx"> #include "ObjectType.h"
</span><span class="cx">
</span><span class="cx"> #include "Chunk.h"
</span><ins>+#include "Heap.h"
</ins><span class="cx"> #include "Object.h"
</span><ins>+#include "PerProcess.h"
</ins><span class="cx">
</span><span class="cx"> namespace bmalloc {
</span><span class="cx">
</span><span class="cx"> ObjectType objectType(void* object)
</span><span class="cx"> {
</span><del>- if (isXLarge(object))
- return ObjectType::XLarge;
</del><ins>+ if (mightBeLarge(object)) {
+ if (!object)
+ return ObjectType::Small;
+
+ std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
+ if (PerProcess<Heap>::getFastCase()->isLarge(lock, object))
+ return ObjectType::Large;
+ }
</ins><span class="cx">
</span><del>- return Object(object).chunk()->objectType();
</del><ins>+ return ObjectType::Small;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> } // namespace bmalloc
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocObjectTypeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/ObjectType.h (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/ObjectType.h 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/ObjectType.h 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -31,13 +31,13 @@
</span><span class="cx">
</span><span class="cx"> namespace bmalloc {
</span><span class="cx">
</span><del>-enum class ObjectType : unsigned char { Small, Large, XLarge };
</del><ins>+enum class ObjectType : unsigned char { Small, Large };
</ins><span class="cx">
</span><span class="cx"> ObjectType objectType(void*);
</span><span class="cx">
</span><del>-inline bool isXLarge(void* object)
</del><ins>+inline bool mightBeLarge(void* object)
</ins><span class="cx"> {
</span><del>- return !test(object, ~xLargeMask);
</del><ins>+ return !test(object, largeAlignmentMask);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> } // namespace bmalloc
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocSegregatedFreeListcpp"></a>
<div class="delfile"><h4>Deleted: trunk/Source/bmalloc/bmalloc/SegregatedFreeList.cpp (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/SegregatedFreeList.cpp 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/SegregatedFreeList.cpp 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -1,89 +0,0 @@
</span><del>-/*
- * Copyright (C) 2014-2016 Apple Inc. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * 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 "SegregatedFreeList.h"
-
-namespace bmalloc {
-
-SegregatedFreeList::SegregatedFreeList(VMState::HasPhysical hasPhysical)
- : m_hasPhysical(hasPhysical)
-{
- BASSERT(static_cast<size_t>(&select(largeObjectMax) - m_freeLists.begin()) == m_freeLists.size() - 1);
-}
-
-void SegregatedFreeList::insert(const LargeObject& largeObject)
-{
- auto& list = select(largeObject.size());
- list.push(hasPhysical(), largeObject);
-}
-
-LargeObject SegregatedFreeList::takeGreedy()
-{
- for (size_t i = m_freeLists.size(); i-- > 0; ) {
- LargeObject largeObject = m_freeLists[i].takeGreedy(hasPhysical());
- if (!largeObject)
- continue;
-
- return largeObject;
- }
- return LargeObject();
-}
-
-LargeObject SegregatedFreeList::take(size_t size)
-{
- for (auto* list = &select(size); list != m_freeLists.end(); ++list) {
- LargeObject largeObject = list->take(hasPhysical(), size);
- if (!largeObject)
- continue;
-
- return largeObject;
- }
- return LargeObject();
-}
-
-LargeObject SegregatedFreeList::take(size_t alignment, size_t size, size_t unalignedSize)
-{
- for (auto* list = &select(size); list != m_freeLists.end(); ++list) {
- LargeObject largeObject = list->take(hasPhysical(), alignment, size, unalignedSize);
- if (!largeObject)
- continue;
-
- return largeObject;
- }
- return LargeObject();
-}
-
-INLINE auto SegregatedFreeList::select(size_t size) -> FreeList&
-{
- size_t alignCount = (size - largeMin) / largeAlignment;
- size_t result = 0;
- while (alignCount) {
- ++result;
- alignCount >>= 1;
- }
- return m_freeLists[result];
-}
-
-} // namespace bmalloc
</del></span></pre></div>
<a id="trunkSourcebmallocbmallocSegregatedFreeListh"></a>
<div class="delfile"><h4>Deleted: trunk/Source/bmalloc/bmalloc/SegregatedFreeList.h (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/SegregatedFreeList.h 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/SegregatedFreeList.h 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -1,69 +0,0 @@
</span><del>-/*
- * Copyright (C) 2014-2016 Apple Inc. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * 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 "FreeList.h"
-#include <array>
-
-namespace bmalloc {
-
-class SegregatedFreeList {
-public:
- SegregatedFreeList(VMState::HasPhysical);
-
- void insert(const LargeObject&);
-
- // Returns a reasonable fit for the provided size, or LargeObject() if no fit
- // is found. May return LargeObject() spuriously if searching takes too long.
- // Incrementally removes stale items from the free list while searching.
- // Does not eagerly remove the returned object from the free list.
- LargeObject take(size_t);
-
- // Returns a reasonable fit for the provided alignment and size, or
- // a reasonable fit for the provided unaligned size, or LargeObject() if no
- // fit is found. May return LargeObject() spuriously if searching takes too
- // long. Incrementally removes stale items from the free list while
- // searching. Does not eagerly remove the returned object from the free list.
- LargeObject take(size_t alignment, size_t, size_t unalignedSize);
-
- // Returns an unreasonable fit for the provided size, or LargeObject() if no
- // fit is found. Never returns LargeObject() spuriously. Incrementally
- // removes stale items from the free list while searching. Eagerly removes
- // the returned object from the free list.
- LargeObject takeGreedy();
-
- VMState::HasPhysical hasPhysical() const { return m_hasPhysical; }
-private:
- FreeList& select(size_t);
-
- VMState::HasPhysical m_hasPhysical;
- std::array<FreeList, 16> m_freeLists;
-};
-
-} // namespace bmalloc
-
-#endif // SegregatedFreeList_h
</del></span></pre></div>
<a id="trunkSourcebmallocbmallocSizesh"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/Sizes.h (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Sizes.h 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/Sizes.h 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -46,34 +46,26 @@
</span><span class="cx"> static const size_t alignment = 8;
</span><span class="cx"> static const size_t alignmentMask = alignment - 1ul;
</span><span class="cx">
</span><ins>+ static const size_t chunkSize = 2 * MB;
+ static const size_t chunkMask = ~(chunkSize - 1ul);
+
</ins><span class="cx"> static const size_t smallLineSize = 256;
</span><span class="cx"> static const size_t smallPageSize = 4 * kB;
</span><span class="cx"> static const size_t smallPageLineCount = smallPageSize / smallLineSize;
</span><span class="cx">
</span><span class="cx"> static const size_t maskSizeClassMax = 512;
</span><del>- static const size_t smallMax = 16 * kB;
</del><ins>+ static const size_t smallMax = 64 * kB;
</ins><span class="cx">
</span><del>- static const size_t pageSizeMax = 32 * kB;
</del><ins>+ static const size_t pageSizeMax = smallMax * 2;
</ins><span class="cx"> static const size_t pageClassCount = pageSizeMax / smallPageSize;
</span><span class="cx">
</span><span class="cx"> static const size_t pageSizeWasteFactor = 8;
</span><span class="cx"> static const size_t logWasteFactor = 8;
</span><span class="cx">
</span><del>- static const size_t chunkSize = 2 * MB;
- static const size_t chunkMask = ~(chunkSize - 1ul);
</del><ins>+ static const size_t largeAlignment = smallMax / pageSizeWasteFactor;
+ static const size_t largeAlignmentMask = largeAlignment - 1;
+ static const size_t largeMax = std::numeric_limits<size_t>::max() - largeAlignment; // Make sure that rounding up to largeAlignment does not overflow.
</ins><span class="cx">
</span><del>- static const size_t largeAlignment = 64;
- static const size_t largeMin = 1 * kB;
- static const size_t largeObjectMax = chunkSize;
- static const size_t largeMax = largeObjectMax / 2;
-
- static const size_t xLargeAlignment = chunkSize;
- static const size_t xLargeMask = ~(xLargeAlignment - 1);
- static const size_t xLargeMax = std::numeric_limits<size_t>::max() - xLargeAlignment; // Make sure that rounding up to xLargeAlignment does not overflow.
-
- static const size_t freeListSearchDepth = 16;
- static const size_t freeListGrowFactor = 2;
-
</del><span class="cx"> static const size_t deallocatorLogCapacity = 256;
</span><span class="cx"> static const size_t bumpRangeCacheCapacity = 3;
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocSortedVectorh"></a>
<div class="delfile"><h4>Deleted: trunk/Source/bmalloc/bmalloc/SortedVector.h (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/SortedVector.h 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/SortedVector.h 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -1,169 +0,0 @@
</span><del>-/*
- * Copyright (C) 2016 Apple Inc. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * 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 SortedVector_h
-#define SortedVector_h
-
-#include "Vector.h"
-#include <algorithm>
-
-namespace bmalloc {
-
-template<typename T>
-class SortedVector {
- static_assert(std::is_trivially_destructible<T>::value, "SortedVector must have a trivial destructor.");
-
- struct Bucket {
- explicit Bucket(T value)
- : value(value)
- , isDeleted(false)
- {
- }
-
- template<typename U> bool operator<(const U& other) const
- {
- return value < other;
- }
-
- T value;
- bool isDeleted;
- };
-
-public:
- class iterator : public std::iterator<std::forward_iterator_tag, T> {
- public:
- iterator(Bucket* bucket, Bucket* end)
- : m_bucket(bucket)
- , m_end(end)
- {
- skipDeletedBuckets();
- }
-
- iterator(const iterator& other)
- : m_bucket(other.m_bucket)
- , m_end(other.m_end)
- {
- }
-
- iterator& operator++()
- {
- BASSERT(m_bucket != m_end);
- ++m_bucket;
- skipDeletedBuckets();
- return *this;
- }
-
- bool operator!=(const iterator& other)
- {
- return m_bucket != other.m_bucket;
- }
-
- T& operator*()
- {
- BASSERT(m_bucket < m_end);
- BASSERT(!m_bucket->isDeleted);
- return m_bucket->value;
- }
-
- T* operator->() { return &operator*(); }
-
- private:
- friend class SortedVector;
-
- void skipDeletedBuckets()
- {
- while (m_bucket != m_end && m_bucket->isDeleted)
- ++m_bucket;
- }
-
- Bucket* m_bucket;
- Bucket* m_end;
- };
-
- iterator begin() { return iterator(m_vector.begin(), m_vector.end()); }
- iterator end() { return iterator(m_vector.end(), m_vector.end()); }
-
- void insert(const T&);
-
- template<typename U> iterator find(const U&);
- template<typename U> T get(const U&);
- template<typename U> T take(const U&);
-
- void shrinkToFit();
-
-private:
- Vector<Bucket> m_vector;
-};
-
-template<typename T>
-void SortedVector<T>::insert(const T& value)
-{
- auto it = std::lower_bound(m_vector.begin(), m_vector.end(), value);
- if (it != m_vector.end() && it->isDeleted) {
- *it = Bucket(value);
- return;
- }
-
- m_vector.insert(it, Bucket(value));
-}
-
-template<typename T> template<typename U>
-typename SortedVector<T>::iterator SortedVector<T>::find(const U& value)
-{
- auto it = std::lower_bound(m_vector.begin(), m_vector.end(), value);
- return iterator(it, m_vector.end());
-}
-
-template<typename T> template<typename U>
-T SortedVector<T>::get(const U& value)
-{
- return *find(value);
-}
-
-template<typename T> template<typename U>
-T SortedVector<T>::take(const U& value)
-{
- auto it = find(value);
- it.m_bucket->isDeleted = true;
- return it.m_bucket->value;
-}
-
-template<typename T>
-void SortedVector<T>::shrinkToFit()
-{
- auto isDeleted = [](const Bucket& bucket) {
- return bucket.isDeleted;
- };
-
- auto newEnd = std::remove_if(m_vector.begin(), m_vector.end(), isDeleted);
- size_t newSize = newEnd - m_vector.begin();
- m_vector.shrink(newSize);
-
- m_vector.shrinkToFit();
-}
-
-} // namespace bmalloc
-
-#endif // SortedVector_h
</del></span></pre></div>
<a id="trunkSourcebmallocbmallocVMHeapcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/VMHeap.cpp (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/VMHeap.cpp 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/VMHeap.cpp 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -23,62 +23,36 @@
</span><span class="cx"> * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
</span><span class="cx"> */
</span><span class="cx">
</span><del>-#include "LargeObject.h"
</del><span class="cx"> #include "PerProcess.h"
</span><span class="cx"> #include "VMHeap.h"
</span><span class="cx"> #include <thread>
</span><span class="cx">
</span><span class="cx"> namespace bmalloc {
</span><span class="cx">
</span><del>-VMHeap::VMHeap()
- : m_largeObjects(VMState::HasPhysical::False)
</del><ins>+XLargeRange VMHeap::tryAllocateLargeChunk(std::lock_guard<StaticMutex>& lock, size_t alignment, size_t size)
</ins><span class="cx"> {
</span><del>-}
</del><ins>+ // We allocate VM in aligned multiples to increase the chances that
+ // the OS will provide contiguous ranges that we can merge.
+ alignment = roundUpToMultipleOf<chunkSize>(alignment);
+ size = roundUpToMultipleOf<chunkSize>(size);
</ins><span class="cx">
</span><del>-LargeObject VMHeap::allocateChunk(std::lock_guard<StaticMutex>& lock)
-{
- Chunk* chunk =
- new (vmAllocate(chunkSize, chunkSize)) Chunk(lock, ObjectType::Large);
</del><ins>+ void* memory = tryVMAllocate(alignment, size);
+ if (!memory)
+ return XLargeRange();
</ins><span class="cx">
</span><ins>+ Chunk* chunk = new (memory) Chunk(lock);
+
</ins><span class="cx"> #if BOS(DARWIN)
</span><span class="cx"> m_zone.addChunk(chunk);
</span><span class="cx"> #endif
</span><span class="cx">
</span><del>- size_t alignment = largeAlignment;
- size_t metadataSize = roundUpToMultipleOf(alignment, sizeof(Chunk));
-
- Range range(chunk->bytes() + metadataSize, chunkSize - metadataSize);
- BASSERT(range.size() <= largeObjectMax);
-
- BeginTag* beginTag = Chunk::beginTag(range.begin());
- beginTag->setRange(range);
- beginTag->setFree(true);
- beginTag->setVMState(VMState::Virtual);
-
- EndTag* endTag = Chunk::endTag(range.begin(), range.size());
- endTag->init(beginTag);
-
- // Mark the left and right edges of our range as allocated. This naturally
- // prevents merging logic from overflowing left (into metadata) or right
- // (beyond our chunk), without requiring special-case checks.
-
- EndTag* leftSentinel = beginTag->prev();
- BASSERT(leftSentinel >= chunk->boundaryTags().begin());
- BASSERT(leftSentinel < chunk->boundaryTags().end());
- leftSentinel->initSentinel();
-
- BeginTag* rightSentinel = endTag->next();
- BASSERT(rightSentinel >= chunk->boundaryTags().begin());
- BASSERT(rightSentinel < chunk->boundaryTags().end());
- rightSentinel->initSentinel();
-
- return LargeObject(range.begin());
</del><ins>+ return XLargeRange(chunk->bytes(), size, 0);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void VMHeap::allocateSmallChunk(std::lock_guard<StaticMutex>& lock, size_t pageClass)
</span><span class="cx"> {
</span><span class="cx"> Chunk* chunk =
</span><del>- new (vmAllocate(chunkSize, chunkSize)) Chunk(lock, ObjectType::Small);
</del><ins>+ new (vmAllocate(chunkSize, chunkSize)) Chunk(lock);
</ins><span class="cx">
</span><span class="cx"> #if BOS(DARWIN)
</span><span class="cx"> m_zone.addChunk(chunk);
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocVMHeaph"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/VMHeap.h (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/VMHeap.h 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/VMHeap.h 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -29,11 +29,9 @@
</span><span class="cx"> #include "AsyncTask.h"
</span><span class="cx"> #include "Chunk.h"
</span><span class="cx"> #include "FixedVector.h"
</span><del>-#include "LargeObject.h"
-#include "Range.h"
-#include "SegregatedFreeList.h"
-#include "VMState.h"
</del><ins>+#include "Map.h"
</ins><span class="cx"> #include "Vector.h"
</span><ins>+#include "XLargeRange.h"
</ins><span class="cx"> #if BOS(DARWIN)
</span><span class="cx"> #include "Zone.h"
</span><span class="cx"> #endif
</span><span class="lines">@@ -46,23 +44,16 @@
</span><span class="cx">
</span><span class="cx"> class VMHeap {
</span><span class="cx"> public:
</span><del>- VMHeap();
-
</del><span class="cx"> SmallPage* allocateSmallPage(std::lock_guard<StaticMutex>&, size_t);
</span><span class="cx"> void deallocateSmallPage(std::unique_lock<StaticMutex>&, size_t, SmallPage*);
</span><span class="cx">
</span><del>- LargeObject allocateLargeObject(std::lock_guard<StaticMutex>&, size_t);
- LargeObject allocateLargeObject(std::lock_guard<StaticMutex>&, size_t, size_t, size_t);
-
- void deallocateLargeObject(std::unique_lock<StaticMutex>&, LargeObject);
</del><ins>+ XLargeRange tryAllocateLargeChunk(std::lock_guard<StaticMutex>&, size_t alignment, size_t);
</ins><span class="cx">
</span><span class="cx"> private:
</span><del>- LargeObject allocateChunk(std::lock_guard<StaticMutex>&);
</del><span class="cx"> void allocateSmallChunk(std::lock_guard<StaticMutex>&, size_t);
</span><span class="cx">
</span><span class="cx"> std::array<List<SmallPage>, pageClassCount> m_smallPages;
</span><del>- SegregatedFreeList m_largeObjects;
-
</del><ins>+
</ins><span class="cx"> #if BOS(DARWIN)
</span><span class="cx"> Zone m_zone;
</span><span class="cx"> #endif
</span><span class="lines">@@ -87,46 +78,6 @@
</span><span class="cx"> m_smallPages[pageClass].push(page);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-inline LargeObject VMHeap::allocateLargeObject(std::lock_guard<StaticMutex>& lock, size_t size)
-{
- if (LargeObject largeObject = m_largeObjects.take(size))
- return largeObject;
-
- BASSERT(size <= largeMax);
- return allocateChunk(lock);
-}
-
-inline LargeObject VMHeap::allocateLargeObject(std::lock_guard<StaticMutex>& lock, size_t alignment, size_t size, size_t unalignedSize)
-{
- if (LargeObject largeObject = m_largeObjects.take(alignment, size, unalignedSize))
- return largeObject;
-
- BASSERT(unalignedSize <= largeMax);
- return allocateChunk(lock);
-}
-
-inline void VMHeap::deallocateLargeObject(std::unique_lock<StaticMutex>& lock, LargeObject largeObject)
-{
- // Multiple threads might scavenge concurrently, meaning that new merging opportunities
- // become visible after we reacquire the lock. Therefore we loop.
- do {
- largeObject = largeObject.merge();
-
- // Temporarily mark this object as allocated to prevent clients from merging
- // with it or allocating it while we're messing with its physical pages.
- largeObject.setFree(false);
-
- lock.unlock();
- vmDeallocatePhysicalPagesSloppy(largeObject.begin(), largeObject.size());
- lock.lock();
-
- largeObject.setFree(true);
- } while (largeObject.prevCanMerge() || largeObject.nextCanMerge());
-
- largeObject.setVMState(VMState::Virtual);
- m_largeObjects.insert(largeObject);
-}
-
</del><span class="cx"> } // namespace bmalloc
</span><span class="cx">
</span><span class="cx"> #endif // VMHeap_h
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocVMStateh"></a>
<div class="delfile"><h4>Deleted: trunk/Source/bmalloc/bmalloc/VMState.h (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/VMState.h 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/VMState.h 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -1,86 +0,0 @@
</span><del>-/*
- * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * 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 VMState_h
-#define VMState_h
-
-namespace bmalloc {
-
-class VMState {
-public:
- enum class HasPhysical : bool {
- False = false,
- True = true
- };
-
- enum State : unsigned {
- Invalid = 0x0,
- Physical = 0x1,
- Virtual = 0x2,
- Mixed = 0x3
- };
-
- VMState(State vmState)
- : m_state(vmState)
- {
- }
-
- explicit VMState(unsigned vmState)
- : m_state(static_cast<State>(vmState))
- {
- }
-
- inline bool hasPhysical()
- {
- return !!(m_state & VMState::Physical);
- }
-
- inline bool hasVirtual()
- {
- return !!(m_state & VMState::Virtual);
- }
-
- inline void merge(VMState otherVMState)
- {
- m_state = static_cast<State>(m_state | otherVMState.m_state);
- }
-
- bool operator==(VMState other) const { return m_state == other.m_state; }
- explicit operator unsigned() const { return m_state; }
-
-private:
- State m_state;
-};
-
-inline VMState merge(VMState a, VMState b)
-{
- VMState result(a);
- result.merge(b);
- return result;
-}
-
-} // namespace bmalloc
-
-#endif // VMState_h
</del></span></pre></div>
<a id="trunkSourcebmallocbmallocVectorh"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/Vector.h (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Vector.h 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/Vector.h 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -43,10 +43,8 @@
</span><span class="cx"> typedef T* iterator;
</span><span class="cx"> typedef const T* const_iterator;
</span><span class="cx">
</span><del>- Vector(const Vector&) = delete;
- Vector& operator=(const Vector&) = delete;
-
</del><span class="cx"> Vector();
</span><ins>+ Vector(Vector&&);
</ins><span class="cx"> ~Vector();
</span><span class="cx">
</span><span class="cx"> iterator begin() { return m_buffer; }
</span><span class="lines">@@ -65,9 +63,11 @@
</span><span class="cx"> T pop(const_iterator it) { return pop(it - begin()); }
</span><span class="cx">
</span><span class="cx"> void insert(iterator, const T&);
</span><ins>+ T remove(iterator);
</ins><span class="cx">
</span><span class="cx"> void grow(size_t);
</span><span class="cx"> void shrink(size_t);
</span><ins>+ void resize(size_t);
</ins><span class="cx">
</span><span class="cx"> void shrinkToFit();
</span><span class="cx">
</span><span class="lines">@@ -87,13 +87,24 @@
</span><span class="cx">
</span><span class="cx"> template<typename T>
</span><span class="cx"> inline Vector<T>::Vector()
</span><del>- : m_buffer(0)
</del><ins>+ : m_buffer(nullptr)
</ins><span class="cx"> , m_size(0)
</span><span class="cx"> , m_capacity(0)
</span><span class="cx"> {
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> template<typename T>
</span><ins>+inline Vector<T>::Vector(Vector&& other)
+ : m_buffer(other.m_buffer)
+ , m_size(other.m_size)
+ , m_capacity(other.m_capacity)
+{
+ other.m_buffer = nullptr;
+ other.m_size = 0;
+ other.m_capacity = 0;
+}
+
+template<typename T>
</ins><span class="cx"> Vector<T>::~Vector()
</span><span class="cx"> {
</span><span class="cx"> if (m_buffer)
</span><span class="lines">@@ -138,15 +149,27 @@
</span><span class="cx"> size_t index = it - begin();
</span><span class="cx"> size_t moveCount = end() - it;
</span><span class="cx">
</span><del>- if (m_size == m_capacity)
- growCapacity();
</del><ins>+ grow(m_size + 1);
+ std::memmove(&m_buffer[index + 1], &m_buffer[index], moveCount * sizeof(T));
</ins><span class="cx">
</span><del>- std::memmove(&m_buffer[index + 1], &m_buffer[index], moveCount * sizeof(T));
</del><span class="cx"> m_buffer[index] = value;
</span><del>- m_size++;
</del><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> template<typename T>
</span><ins>+T Vector<T>::remove(iterator it)
+{
+ size_t index = it - begin();
+ size_t moveCount = end() - it - 1;
+
+ T result = *it;
+
+ std::memmove(&m_buffer[index], &m_buffer[index + 1], moveCount * sizeof(T));
+ shrink(m_size - 1);
+
+ return result;
+}
+
+template<typename T>
</ins><span class="cx"> inline void Vector<T>::grow(size_t size)
</span><span class="cx"> {
</span><span class="cx"> BASSERT(size >= m_size);
</span><span class="lines">@@ -164,6 +187,15 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> template<typename T>
</span><ins>+inline void Vector<T>::resize(size_t size)
+{
+ if (size <= m_size)
+ shrink(size);
+ else
+ grow(size);
+}
+
+template<typename T>
</ins><span class="cx"> void Vector<T>::reallocateBuffer(size_t newCapacity)
</span><span class="cx"> {
</span><span class="cx"> size_t vmSize = bmalloc::vmSize(newCapacity * sizeof(T));
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocXLargeMapcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/XLargeMap.cpp (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/XLargeMap.cpp 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/XLargeMap.cpp 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -24,10 +24,11 @@
</span><span class="cx"> */
</span><span class="cx">
</span><span class="cx"> #include "XLargeMap.h"
</span><ins>+#include <utility>
</ins><span class="cx">
</span><span class="cx"> namespace bmalloc {
</span><span class="cx">
</span><del>-XLargeRange XLargeMap::takeFree(size_t alignment, size_t size)
</del><ins>+XLargeRange XLargeMap::remove(size_t alignment, size_t size)
</ins><span class="cx"> {
</span><span class="cx"> size_t alignmentMask = alignment - 1;
</span><span class="cx">
</span><span class="lines">@@ -61,14 +62,12 @@
</span><span class="cx"> return m_free.pop(candidate);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-void XLargeMap::addFree(const XLargeRange& range)
</del><ins>+void XLargeMap::add(const XLargeRange& range)
</ins><span class="cx"> {
</span><span class="cx"> XLargeRange merged = range;
</span><span class="cx">
</span><span class="cx"> for (size_t i = 0; i < m_free.size(); ++i) {
</span><del>- auto& other = m_free[i];
-
- if (!canMerge(merged, other))
</del><ins>+ if (!canMerge(merged, m_free[i]))
</ins><span class="cx"> continue;
</span><span class="cx">
</span><span class="cx"> merged = merge(merged, m_free.pop(i--));
</span><span class="lines">@@ -77,75 +76,16 @@
</span><span class="cx"> m_free.push(merged);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-void XLargeMap::addAllocated(const XLargeRange& prev, const std::pair<XLargeRange, XLargeRange>& allocated, const XLargeRange& next)
</del><ins>+XLargeRange XLargeMap::removePhysical()
</ins><span class="cx"> {
</span><del>- if (prev)
- m_free.push(prev);
-
- if (next)
- m_free.push(next);
</del><ins>+ auto it = std::find_if(m_free.begin(), m_free.end(), [](const XLargeRange& range) {
+ return range.physicalSize();
+ });
</ins><span class="cx">
</span><del>- m_allocated.insert({ allocated.first, allocated.second });
-}
</del><ins>+ if (it == m_free.end())
+ return XLargeRange();
</ins><span class="cx">
</span><del>-XLargeRange XLargeMap::getAllocated(void* object)
-{
- return m_allocated.find(object)->object;
</del><ins>+ return m_free.pop(it);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-XLargeRange XLargeMap::takeAllocated(void* object)
-{
- Allocation allocation = m_allocated.take(object);
- return merge(allocation.object, allocation.unused);
-}
-
-void XLargeMap::shrinkToFit()
-{
- m_free.shrinkToFit();
- m_allocated.shrinkToFit();
-}
-
-XLargeRange XLargeMap::takePhysical() {
- auto hasPhysical = [](const XLargeRange& range) {
- return range.vmState().hasPhysical();
- };
-
- auto it = std::find_if(m_free.begin(), m_free.end(), hasPhysical);
- if (it != m_free.end())
- return m_free.pop(it);
-
- auto hasUnused = [](const Allocation& allocation) {
- return allocation.unused && allocation.unused.vmState().hasPhysical();
- };
-
- XLargeRange swapped;
- auto it2 = std::find_if(m_allocated.begin(), m_allocated.end(), hasUnused);
- if (it2 != m_allocated.end())
- std::swap(it2->unused, swapped);
-
- return swapped;
-}
-
-void XLargeMap::addVirtual(const XLargeRange& range)
-{
- auto canMerge = [&range](const Allocation& other) {
- return other.object.end() == range.begin();
- };
-
- if (range.size() < xLargeAlignment) {
- // This is an unused fragment, so it might belong in the allocated list.
- auto it = std::find_if(m_allocated.begin(), m_allocated.end(), canMerge);
- if (it != m_allocated.end()) {
- BASSERT(!it->unused);
- it->unused = range;
- return;
- }
-
- // If we didn't find a neighbor in the allocated list, our neighbor must
- // have been freed. We'll merge with it below.
- }
-
- addFree(range);
-}
-
</del><span class="cx"> } // namespace bmalloc
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocXLargeMaph"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/XLargeMap.h (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/XLargeMap.h 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/XLargeMap.h 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -26,7 +26,6 @@
</span><span class="cx"> #ifndef XLargeMap_h
</span><span class="cx"> #define XLargeMap_h
</span><span class="cx">
</span><del>-#include "SortedVector.h"
</del><span class="cx"> #include "Vector.h"
</span><span class="cx"> #include "XLargeRange.h"
</span><span class="cx"> #include <algorithm>
</span><span class="lines">@@ -35,29 +34,12 @@
</span><span class="cx">
</span><span class="cx"> class XLargeMap {
</span><span class="cx"> public:
</span><del>- void addFree(const XLargeRange&);
- XLargeRange takeFree(size_t alignment, size_t);
</del><ins>+ void add(const XLargeRange&);
+ XLargeRange remove(size_t alignment, size_t);
+ XLargeRange removePhysical();
</ins><span class="cx">
</span><del>- void addAllocated(const XLargeRange& prev, const std::pair<XLargeRange, XLargeRange>&, const XLargeRange& next);
- XLargeRange getAllocated(void*);
- XLargeRange takeAllocated(void*);
-
- XLargeRange takePhysical();
- void addVirtual(const XLargeRange&);
-
- void shrinkToFit();
-
</del><span class="cx"> private:
</span><del>- struct Allocation {
- bool operator<(const Allocation& other) const { return object < other.object; }
- bool operator<(void* ptr) const { return object.begin() < ptr; }
-
- XLargeRange object;
- XLargeRange unused;
- };
-
</del><span class="cx"> Vector<XLargeRange> m_free;
</span><del>- SortedVector<Allocation> m_allocated;
</del><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> } // namespace bmalloc
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocXLargeRangeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/XLargeRange.h (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/XLargeRange.h 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc/XLargeRange.h 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -26,31 +26,38 @@
</span><span class="cx"> #ifndef XLargeRange_h
</span><span class="cx"> #define XLargeRange_h
</span><span class="cx">
</span><del>-#include "VMState.h"
-
</del><span class="cx"> namespace bmalloc {
</span><span class="cx">
</span><span class="cx"> class XLargeRange : public Range {
</span><span class="cx"> public:
</span><span class="cx"> XLargeRange()
</span><span class="cx"> : Range()
</span><del>- , m_vmState(VMState::Virtual)
</del><ins>+ , m_physicalSize(0)
</ins><span class="cx"> {
</span><span class="cx"> }
</span><span class="cx">
</span><del>- XLargeRange(void* begin, size_t size, VMState vmState)
</del><ins>+ XLargeRange(const Range& other, size_t physicalSize)
+ : Range(other)
+ , m_physicalSize(physicalSize)
+ {
+ }
+
+ XLargeRange(void* begin, size_t size, size_t physicalSize)
</ins><span class="cx"> : Range(begin, size)
</span><del>- , m_vmState(vmState)
</del><ins>+ , m_physicalSize(physicalSize)
</ins><span class="cx"> {
</span><span class="cx"> }
</span><del>-
- VMState vmState() const { return m_vmState; }
- void setVMState(VMState vmState) { m_vmState = vmState; }
</del><span class="cx">
</span><ins>+ size_t physicalSize() const { return m_physicalSize; }
+ void setPhysicalSize(size_t physicalSize) { m_physicalSize = physicalSize; }
+
</ins><span class="cx"> std::pair<XLargeRange, XLargeRange> split(size_t) const;
</span><span class="cx">
</span><ins>+ bool operator<(const void* other) const { return begin() < other; }
+ bool operator<(const XLargeRange& other) const { return begin() < other.begin(); }
+
</ins><span class="cx"> private:
</span><del>- VMState m_vmState;
</del><ins>+ size_t m_physicalSize;
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> inline bool canMerge(const XLargeRange& a, const XLargeRange& b)
</span><span class="lines">@@ -66,18 +73,32 @@
</span><span class="cx">
</span><span class="cx"> inline XLargeRange merge(const XLargeRange& a, const XLargeRange& b)
</span><span class="cx"> {
</span><ins>+ const XLargeRange& left = std::min(a, b);
+ if (left.size() == left.physicalSize()) {
+ return XLargeRange(
+ left.begin(),
+ a.size() + b.size(),
+ a.physicalSize() + b.physicalSize());
+ }
+
</ins><span class="cx"> return XLargeRange(
</span><del>- std::min(a.begin(), b.begin()),
</del><ins>+ left.begin(),
</ins><span class="cx"> a.size() + b.size(),
</span><del>- merge(a.vmState(), b.vmState()));
</del><ins>+ left.physicalSize());
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> inline std::pair<XLargeRange, XLargeRange> XLargeRange::split(size_t size) const
</span><span class="cx"> {
</span><span class="cx"> BASSERT(size <= this->size());
</span><ins>+
+ if (size <= physicalSize()) {
+ XLargeRange left(begin(), size, size);
+ XLargeRange right(left.end(), this->size() - size, physicalSize() - size);
+ return std::make_pair(left, right);
+ }
</ins><span class="cx">
</span><del>- XLargeRange left(begin(), size, vmState());
- XLargeRange right(left.end(), this->size() - size, vmState());
</del><ins>+ XLargeRange left(begin(), size, physicalSize());
+ XLargeRange right(left.end(), this->size() - size, 0);
</ins><span class="cx"> return std::make_pair(left, right);
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc.xcodeproj/project.pbxproj (199745 => 199746)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc.xcodeproj/project.pbxproj 2016-04-19 23:31:25 UTC (rev 199745)
+++ trunk/Source/bmalloc/bmalloc.xcodeproj/project.pbxproj 2016-04-19 23:36:20 UTC (rev 199746)
</span><span class="lines">@@ -9,14 +9,11 @@
</span><span class="cx"> /* Begin PBXBuildFile section */
</span><span class="cx"> 1400274918F89C1300115C97 /* Heap.h in Headers */ = {isa = PBXBuildFile; fileRef = 14DA320C18875B09007269E0 /* Heap.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 1400274A18F89C2300115C97 /* VMHeap.h in Headers */ = {isa = PBXBuildFile; fileRef = 144F7BFC18BFC517003537F3 /* VMHeap.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><del>- 1400274C18F89C3D00115C97 /* SegregatedFreeList.h in Headers */ = {isa = PBXBuildFile; fileRef = 146BEE1E18C841C50002D5A2 /* SegregatedFreeList.h */; settings = {ATTRIBUTES = (Private, ); }; };
</del><span class="cx"> 140FA00319CE429C00FFD3C8 /* BumpRange.h in Headers */ = {isa = PBXBuildFile; fileRef = 140FA00219CE429C00FFD3C8 /* BumpRange.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 140FA00519CE4B6800FFD3C8 /* LineMetadata.h in Headers */ = {isa = PBXBuildFile; fileRef = 140FA00419CE4B6800FFD3C8 /* LineMetadata.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 141D9B001C8E51C0000ABBA0 /* List.h in Headers */ = {isa = PBXBuildFile; fileRef = 141D9AFF1C8E51C0000ABBA0 /* List.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 143CB81C19022BC900B16A45 /* StaticMutex.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 143CB81A19022BC900B16A45 /* StaticMutex.cpp */; };
</span><span class="cx"> 143CB81D19022BC900B16A45 /* StaticMutex.h in Headers */ = {isa = PBXBuildFile; fileRef = 143CB81B19022BC900B16A45 /* StaticMutex.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><del>- 143EF9AF1A9FABF6004F5C77 /* FreeList.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 143EF9AD1A9FABF6004F5C77 /* FreeList.cpp */; };
- 143EF9B01A9FABF6004F5C77 /* FreeList.h in Headers */ = {isa = PBXBuildFile; fileRef = 143EF9AE1A9FABF6004F5C77 /* FreeList.h */; settings = {ATTRIBUTES = (Private, ); }; };
</del><span class="cx"> 1440AFCB1A95261100837FAA /* Zone.h in Headers */ = {isa = PBXBuildFile; fileRef = 1440AFCA1A95261100837FAA /* Zone.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 1440AFCD1A9527AF00837FAA /* Zone.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 1440AFCC1A9527AF00837FAA /* Zone.cpp */; };
</span><span class="cx"> 1448C30018F3754600502839 /* mbmalloc.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 1448C2FF18F3754300502839 /* mbmalloc.cpp */; };
</span><span class="lines">@@ -24,18 +21,14 @@
</span><span class="cx"> 144BE11F1CA346520099C8C0 /* Object.h in Headers */ = {isa = PBXBuildFile; fileRef = 144BE11E1CA346520099C8C0 /* Object.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 144C07F41C7B70260051BB6A /* XLargeMap.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 144C07F21C7B70260051BB6A /* XLargeMap.cpp */; };
</span><span class="cx"> 144C07F51C7B70260051BB6A /* XLargeMap.h in Headers */ = {isa = PBXBuildFile; fileRef = 144C07F31C7B70260051BB6A /* XLargeMap.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><del>- 146041E71C7FF2EF00E9F94E /* SortedVector.h in Headers */ = {isa = PBXBuildFile; fileRef = 146041E61C7FF2EF00E9F94E /* SortedVector.h */; settings = {ATTRIBUTES = (Private, ); }; };
</del><span class="cx"> 147DC6E31CA5B70B00724E8D /* Chunk.h in Headers */ = {isa = PBXBuildFile; fileRef = 147DC6E21CA5B70B00724E8D /* Chunk.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 14895D911A3A319C0006235D /* Environment.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14895D8F1A3A319C0006235D /* Environment.cpp */; };
</span><span class="cx"> 14895D921A3A319C0006235D /* Environment.h in Headers */ = {isa = PBXBuildFile; fileRef = 14895D901A3A319C0006235D /* Environment.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><del>- 14C6216F1A9A9A6200E72293 /* LargeObject.h in Headers */ = {isa = PBXBuildFile; fileRef = 14C6216E1A9A9A6200E72293 /* LargeObject.h */; settings = {ATTRIBUTES = (Private, ); }; };
</del><ins>+ 14C8992B1CC485E70027A057 /* Map.h in Headers */ = {isa = PBXBuildFile; fileRef = 14C8992A1CC485E70027A057 /* Map.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ 14C8992D1CC578330027A057 /* XLargeRange.h in Headers */ = {isa = PBXBuildFile; fileRef = 14C8992C1CC578330027A057 /* XLargeRange.h */; settings = {ATTRIBUTES = (Private, ); }; };
</ins><span class="cx"> 14C919C918FCC59F0028DB43 /* BPlatform.h in Headers */ = {isa = PBXBuildFile; fileRef = 14C919C818FCC59F0028DB43 /* BPlatform.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 14CC394C18EA8858004AFE34 /* libbmalloc.a in Frameworks */ = {isa = PBXBuildFile; fileRef = 14F271BE18EA3963008C152F /* libbmalloc.a */; };
</span><del>- 14D2CD9B1AA12CFB00770440 /* VMState.h in Headers */ = {isa = PBXBuildFile; fileRef = 14D2CD9A1AA12CFB00770440 /* VMState.h */; settings = {ATTRIBUTES = (Private, ); }; };
- 14DD788D18F48CC600950702 /* BeginTag.h in Headers */ = {isa = PBXBuildFile; fileRef = 1417F64518B54A700076FA3F /* BeginTag.h */; settings = {ATTRIBUTES = (Private, ); }; };
- 14DD788E18F48CCD00950702 /* BoundaryTag.h in Headers */ = {isa = PBXBuildFile; fileRef = 1485655E18A43AF900ED6942 /* BoundaryTag.h */; settings = {ATTRIBUTES = (Private, ); }; };
</del><span class="cx"> 14DD789018F48CEB00950702 /* Sizes.h in Headers */ = {isa = PBXBuildFile; fileRef = 145F6874179DF84100D65598 /* Sizes.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><del>- 14DD789218F48CFC00950702 /* EndTag.h in Headers */ = {isa = PBXBuildFile; fileRef = 1417F64618B54A700076FA3F /* EndTag.h */; settings = {ATTRIBUTES = (Private, ); }; };
</del><span class="cx"> 14DD789318F48D0F00950702 /* ObjectType.h in Headers */ = {isa = PBXBuildFile; fileRef = 1485656018A43DBA00ED6942 /* ObjectType.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 14DD789818F48D4A00950702 /* Allocator.h in Headers */ = {isa = PBXBuildFile; fileRef = 145F6856179DC8CA00D65598 /* Allocator.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 14DD789918F48D4A00950702 /* Cache.h in Headers */ = {isa = PBXBuildFile; fileRef = 144469E517A46BFE00F9EA1D /* Cache.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="lines">@@ -55,11 +48,9 @@
</span><span class="cx"> 14DD78CE18F48D7500950702 /* Syscall.h in Headers */ = {isa = PBXBuildFile; fileRef = 1417F64F18B7280C0076FA3F /* Syscall.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 14DD78CF18F48D7500950702 /* Vector.h in Headers */ = {isa = PBXBuildFile; fileRef = 1479E21217A1A255006D4E9D /* Vector.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 14DD78D018F48D7500950702 /* VMAllocate.h in Headers */ = {isa = PBXBuildFile; fileRef = 1479E21417A1A63E006D4E9D /* VMAllocate.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><del>- 14EB79EA1C7C1BC4005E834F /* XLargeRange.h in Headers */ = {isa = PBXBuildFile; fileRef = 14EB79E81C7C1BC4005E834F /* XLargeRange.h */; settings = {ATTRIBUTES = (Private, ); }; };
</del><span class="cx"> 14F271C318EA3978008C152F /* Allocator.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 145F6855179DC8CA00D65598 /* Allocator.cpp */; };
</span><span class="cx"> 14F271C418EA397B008C152F /* Cache.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 144469E417A46BFE00F9EA1D /* Cache.cpp */; };
</span><span class="cx"> 14F271C518EA397E008C152F /* Deallocator.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 145F6859179DC90200D65598 /* Deallocator.cpp */; };
</span><del>- 14F271C618EA3983008C152F /* SegregatedFreeList.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 146BEE2118C845AE0002D5A2 /* SegregatedFreeList.cpp */; };
</del><span class="cx"> 14F271C718EA3990008C152F /* Heap.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14DA320E18875D9F007269E0 /* Heap.cpp */; };
</span><span class="cx"> 14F271C818EA3990008C152F /* ObjectType.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14105E8318E14374003A106E /* ObjectType.cpp */; };
</span><span class="cx"> 14F271C918EA3990008C152F /* VMHeap.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 144F7BFB18BFC517003537F3 /* VMHeap.cpp */; };
</span><span class="lines">@@ -85,8 +76,6 @@
</span><span class="cx"> 1413E460189DCE1E00546D68 /* Inline.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Inline.h; path = bmalloc/Inline.h; sourceTree = "<group>"; };
</span><span class="cx"> 1413E462189DE1CD00546D68 /* BumpAllocator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; lineEnding = 0; name = BumpAllocator.h; path = bmalloc/BumpAllocator.h; sourceTree = "<group>"; };
</span><span class="cx"> 1413E468189EEDE400546D68 /* BAssert.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = BAssert.h; path = bmalloc/BAssert.h; sourceTree = "<group>"; };
</span><del>- 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>"; };
</del><span class="cx"> 1417F64F18B7280C0076FA3F /* Syscall.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Syscall.h; path = bmalloc/Syscall.h; sourceTree = "<group>"; };
</span><span class="cx"> 1417F65218BA88A00076FA3F /* AsyncTask.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AsyncTask.h; path = bmalloc/AsyncTask.h; sourceTree = "<group>"; };
</span><span class="cx"> 141D9AFF1C8E51C0000ABBA0 /* List.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = List.h; path = bmalloc/List.h; sourceTree = "<group>"; };
</span><span class="lines">@@ -94,8 +83,6 @@
</span><span class="cx"> 143CB81A19022BC900B16A45 /* StaticMutex.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = StaticMutex.cpp; path = bmalloc/StaticMutex.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 143CB81B19022BC900B16A45 /* StaticMutex.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = StaticMutex.h; path = bmalloc/StaticMutex.h; sourceTree = "<group>"; };
</span><span class="cx"> 143E29ED18CAE90500FE8A0F /* SmallPage.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = SmallPage.h; path = bmalloc/SmallPage.h; sourceTree = "<group>"; };
</span><del>- 143EF9AD1A9FABF6004F5C77 /* FreeList.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = FreeList.cpp; path = bmalloc/FreeList.cpp; sourceTree = "<group>"; };
- 143EF9AE1A9FABF6004F5C77 /* FreeList.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = FreeList.h; path = bmalloc/FreeList.h; sourceTree = "<group>"; };
</del><span class="cx"> 1440AFCA1A95261100837FAA /* Zone.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Zone.h; path = bmalloc/Zone.h; sourceTree = "<group>"; };
</span><span class="cx"> 1440AFCC1A9527AF00837FAA /* Zone.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = Zone.cpp; path = bmalloc/Zone.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 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; };
</span><span class="lines">@@ -117,13 +104,9 @@
</span><span class="cx"> 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; };
</span><span class="cx"> 145F6874179DF84100D65598 /* Sizes.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Sizes.h; path = bmalloc/Sizes.h; sourceTree = "<group>"; };
</span><span class="cx"> 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; };
</span><del>- 146041E61C7FF2EF00E9F94E /* SortedVector.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = SortedVector.h; path = bmalloc/SortedVector.h; sourceTree = "<group>"; };
- 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>"; };
</del><span class="cx"> 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; };
</span><span class="cx"> 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; };
</span><span class="cx"> 147DC6E21CA5B70B00724E8D /* Chunk.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Chunk.h; path = bmalloc/Chunk.h; sourceTree = "<group>"; };
</span><del>- 1485655E18A43AF900ED6942 /* BoundaryTag.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = BoundaryTag.h; path = bmalloc/BoundaryTag.h; sourceTree = "<group>"; };
</del><span class="cx"> 1485656018A43DBA00ED6942 /* ObjectType.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = ObjectType.h; path = bmalloc/ObjectType.h; sourceTree = "<group>"; };
</span><span class="cx"> 14895D8F1A3A319C0006235D /* Environment.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = Environment.cpp; path = bmalloc/Environment.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 14895D901A3A319C0006235D /* Environment.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Environment.h; path = bmalloc/Environment.h; sourceTree = "<group>"; };
</span><span class="lines">@@ -131,14 +114,13 @@
</span><span class="cx"> 14B650C618F39F4800751968 /* bmalloc.xcconfig */ = {isa = PBXFileReference; lastKnownFileType = text.xcconfig; path = bmalloc.xcconfig; sourceTree = "<group>"; };
</span><span class="cx"> 14B650C718F39F4800751968 /* DebugRelease.xcconfig */ = {isa = PBXFileReference; lastKnownFileType = text.xcconfig; path = DebugRelease.xcconfig; sourceTree = "<group>"; };
</span><span class="cx"> 14B650C918F3A04200751968 /* mbmalloc.xcconfig */ = {isa = PBXFileReference; lastKnownFileType = text.xcconfig; path = mbmalloc.xcconfig; sourceTree = "<group>"; };
</span><del>- 14C6216E1A9A9A6200E72293 /* LargeObject.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = LargeObject.h; path = bmalloc/LargeObject.h; sourceTree = "<group>"; };
</del><ins>+ 14C8992A1CC485E70027A057 /* Map.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Map.h; path = bmalloc/Map.h; sourceTree = "<group>"; };
+ 14C8992C1CC578330027A057 /* XLargeRange.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = XLargeRange.h; path = bmalloc/XLargeRange.h; sourceTree = "<group>"; };
</ins><span class="cx"> 14C919C818FCC59F0028DB43 /* BPlatform.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = BPlatform.h; path = bmalloc/BPlatform.h; sourceTree = "<group>"; };
</span><span class="cx"> 14CC394418EA8743004AFE34 /* libmbmalloc.dylib */ = {isa = PBXFileReference; explicitFileType = "compiled.mach-o.dylib"; includeInIndex = 0; path = libmbmalloc.dylib; sourceTree = BUILT_PRODUCTS_DIR; };
</span><del>- 14D2CD9A1AA12CFB00770440 /* VMState.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = VMState.h; path = bmalloc/VMState.h; sourceTree = "<group>"; };
</del><span class="cx"> 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; };
</span><span class="cx"> 14DA320C18875B09007269E0 /* Heap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Heap.h; path = bmalloc/Heap.h; sourceTree = "<group>"; };
</span><span class="cx"> 14DA320E18875D9F007269E0 /* Heap.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = Heap.cpp; path = bmalloc/Heap.cpp; sourceTree = "<group>"; };
</span><del>- 14EB79E81C7C1BC4005E834F /* XLargeRange.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = XLargeRange.h; path = bmalloc/XLargeRange.h; sourceTree = "<group>"; };
</del><span class="cx"> 14F271BE18EA3963008C152F /* libbmalloc.a */ = {isa = PBXFileReference; explicitFileType = archive.ar; includeInIndex = 0; path = libbmalloc.a; sourceTree = BUILT_PRODUCTS_DIR; };
</span><span class="cx"> 4426E27E1C838EE0008EB042 /* Logging.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = Logging.cpp; path = bmalloc/Logging.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 4426E27F1C838EE0008EB042 /* Logging.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Logging.h; path = bmalloc/Logging.h; sourceTree = "<group>"; };
</span><span class="lines">@@ -173,16 +155,6 @@
</span><span class="cx"> name = api;
</span><span class="cx"> sourceTree = "<group>";
</span><span class="cx"> };
</span><del>- 144C07F71C7B707D0051BB6A /* heap: xlarge */ = {
- isa = PBXGroup;
- children = (
- 144C07F21C7B70260051BB6A /* XLargeMap.cpp */,
- 144C07F31C7B70260051BB6A /* XLargeMap.h */,
- 14EB79E81C7C1BC4005E834F /* XLargeRange.h */,
- );
- name = "heap: xlarge";
- sourceTree = "<group>";
- };
</del><span class="cx"> 145F6836179DC45F00D65598 = {
</span><span class="cx"> isa = PBXGroup;
</span><span class="cx"> children = (
</span><span class="lines">@@ -190,7 +162,6 @@
</span><span class="cx"> 14D9DB4D17F2865C00EAAB79 /* cache */,
</span><span class="cx"> 147AAA9C18CE6010002201E4 /* heap: large */,
</span><span class="cx"> 147AAA9A18CE5FD3002201E4 /* heap: small */,
</span><del>- 144C07F71C7B707D0051BB6A /* heap: xlarge */,
</del><span class="cx"> 14D9DB4E17F2866E00EAAB79 /* heap */,
</span><span class="cx"> 14D9DB4F17F2868900EAAB79 /* stdlib */,
</span><span class="cx"> 14B650C418F39F4800751968 /* Configurations */,
</span><span class="lines">@@ -219,15 +190,9 @@
</span><span class="cx"> 147AAA9C18CE6010002201E4 /* heap: large */ = {
</span><span class="cx"> isa = PBXGroup;
</span><span class="cx"> children = (
</span><del>- 1417F64518B54A700076FA3F /* BeginTag.h */,
- 1485655E18A43AF900ED6942 /* BoundaryTag.h */,
- 1417F64618B54A700076FA3F /* EndTag.h */,
- 143EF9AD1A9FABF6004F5C77 /* FreeList.cpp */,
- 143EF9AE1A9FABF6004F5C77 /* FreeList.h */,
- 14C6216E1A9A9A6200E72293 /* LargeObject.h */,
- 146BEE2118C845AE0002D5A2 /* SegregatedFreeList.cpp */,
- 146BEE1E18C841C50002D5A2 /* SegregatedFreeList.h */,
- 14D2CD9A1AA12CFB00770440 /* VMState.h */,
</del><ins>+ 144C07F21C7B70260051BB6A /* XLargeMap.cpp */,
+ 144C07F31C7B70260051BB6A /* XLargeMap.h */,
+ 14C8992C1CC578330027A057 /* XLargeRange.h */,
</ins><span class="cx"> );
</span><span class="cx"> name = "heap: large";
</span><span class="cx"> sourceTree = "<group>";
</span><span class="lines">@@ -292,11 +257,11 @@
</span><span class="cx"> 141D9AFF1C8E51C0000ABBA0 /* List.h */,
</span><span class="cx"> 4426E27E1C838EE0008EB042 /* Logging.cpp */,
</span><span class="cx"> 4426E27F1C838EE0008EB042 /* Logging.h */,
</span><ins>+ 14C8992A1CC485E70027A057 /* Map.h */,
</ins><span class="cx"> 144DCED617A649D90093B2F2 /* Mutex.h */,
</span><span class="cx"> 14446A0717A61FA400F9EA1D /* PerProcess.h */,
</span><span class="cx"> 144469FD17A61F1F00F9EA1D /* PerThread.h */,
</span><span class="cx"> 145F6878179E3A4400D65598 /* Range.h */,
</span><del>- 146041E61C7FF2EF00E9F94E /* SortedVector.h */,
</del><span class="cx"> 143CB81A19022BC900B16A45 /* StaticMutex.cpp */,
</span><span class="cx"> 143CB81B19022BC900B16A45 /* StaticMutex.h */,
</span><span class="cx"> 1417F64F18B7280C0076FA3F /* Syscall.h */,
</span><span class="lines">@@ -330,7 +295,6 @@
</span><span class="cx"> files = (
</span><span class="cx"> 14DD78CF18F48D7500950702 /* Vector.h in Headers */,
</span><span class="cx"> 14C919C918FCC59F0028DB43 /* BPlatform.h in Headers */,
</span><del>- 14DD789218F48CFC00950702 /* EndTag.h in Headers */,
</del><span class="cx"> 1440AFCB1A95261100837FAA /* Zone.h in Headers */,
</span><span class="cx"> 140FA00519CE4B6800FFD3C8 /* LineMetadata.h in Headers */,
</span><span class="cx"> 14DD78CC18F48D7500950702 /* PerThread.h in Headers */,
</span><span class="lines">@@ -338,10 +302,7 @@
</span><span class="cx"> 144BE11F1CA346520099C8C0 /* Object.h in Headers */,
</span><span class="cx"> 143CB81D19022BC900B16A45 /* StaticMutex.h in Headers */,
</span><span class="cx"> 1448C30118F3754C00502839 /* bmalloc.h in Headers */,
</span><del>- 14C6216F1A9A9A6200E72293 /* LargeObject.h in Headers */,
</del><span class="cx"> 14DD789A18F48D4A00950702 /* Deallocator.h in Headers */,
</span><del>- 1400274C18F89C3D00115C97 /* SegregatedFreeList.h in Headers */,
- 14DD788D18F48CC600950702 /* BeginTag.h in Headers */,
</del><span class="cx"> 14DD78CD18F48D7500950702 /* Range.h in Headers */,
</span><span class="cx"> 14DD789C18F48D4A00950702 /* BumpAllocator.h in Headers */,
</span><span class="cx"> 14DD789918F48D4A00950702 /* Cache.h in Headers */,
</span><span class="lines">@@ -349,8 +310,6 @@
</span><span class="cx"> 14DD789018F48CEB00950702 /* Sizes.h in Headers */,
</span><span class="cx"> 14DD78C718F48D7500950702 /* BAssert.h in Headers */,
</span><span class="cx"> 14DD78D018F48D7500950702 /* VMAllocate.h in Headers */,
</span><del>- 14EB79EA1C7C1BC4005E834F /* XLargeRange.h in Headers */,
- 143EF9B01A9FABF6004F5C77 /* FreeList.h in Headers */,
</del><span class="cx"> 14DD78CE18F48D7500950702 /* Syscall.h in Headers */,
</span><span class="cx"> 14DD78C618F48D7500950702 /* AsyncTask.h in Headers */,
</span><span class="cx"> 14DD78C918F48D7500950702 /* Inline.h in Headers */,
</span><span class="lines">@@ -360,12 +319,11 @@
</span><span class="cx"> 140FA00319CE429C00FFD3C8 /* BumpRange.h in Headers */,
</span><span class="cx"> 4426E2811C838EE0008EB042 /* Logging.h in Headers */,
</span><span class="cx"> 14DD78C518F48D7500950702 /* Algorithm.h in Headers */,
</span><ins>+ 14C8992B1CC485E70027A057 /* Map.h in Headers */,
</ins><span class="cx"> 14DD78BD18F48D6B00950702 /* SmallPage.h in Headers */,
</span><del>- 14DD788E18F48CCD00950702 /* BoundaryTag.h in Headers */,
- 146041E71C7FF2EF00E9F94E /* SortedVector.h in Headers */,
</del><span class="cx"> 14DD78C818F48D7500950702 /* FixedVector.h in Headers */,
</span><ins>+ 14C8992D1CC578330027A057 /* XLargeRange.h in Headers */,
</ins><span class="cx"> 144C07F51C7B70260051BB6A /* XLargeMap.h in Headers */,
</span><del>- 14D2CD9B1AA12CFB00770440 /* VMState.h in Headers */,
</del><span class="cx"> 147DC6E31CA5B70B00724E8D /* Chunk.h in Headers */,
</span><span class="cx"> 14DD78BC18F48D6B00950702 /* SmallLine.h in Headers */,
</span><span class="cx"> 14DD789818F48D4A00950702 /* Allocator.h in Headers */,
</span><span class="lines">@@ -454,10 +412,8 @@
</span><span class="cx"> buildActionMask = 2147483647;
</span><span class="cx"> files = (
</span><span class="cx"> 143CB81C19022BC900B16A45 /* StaticMutex.cpp in Sources */,
</span><del>- 14F271C618EA3983008C152F /* SegregatedFreeList.cpp in Sources */,
</del><span class="cx"> 14F271C318EA3978008C152F /* Allocator.cpp in Sources */,
</span><span class="cx"> 14895D911A3A319C0006235D /* Environment.cpp in Sources */,
</span><del>- 143EF9AF1A9FABF6004F5C77 /* FreeList.cpp in Sources */,
</del><span class="cx"> 4426E2801C838EE0008EB042 /* Logging.cpp in Sources */,
</span><span class="cx"> 14F271C718EA3990008C152F /* Heap.cpp in Sources */,
</span><span class="cx"> 14F271C918EA3990008C152F /* VMHeap.cpp in Sources */,
</span></span></pre>
</div>
</div>
</body>
</html>