<!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>[180693] 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/180693">180693</a></dd>
<dt>Author</dt> <dd>ggaren@apple.com</dd>
<dt>Date</dt> <dd>2015-02-26 12:05:14 -0800 (Thu, 26 Feb 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>bmalloc: Refactored SegregatedFreeList and BoundaryTag::init
https://bugs.webkit.org/show_bug.cgi?id=142049
Reviewed by Anders Carlsson.
Split out a FreeList class from SegregatedFreeList. This will make it
easier to add behaviors on free list insertion and removal -- and it's
probably how I should have designed things at the start.
Moved BoundaryTag::init into LargeObject, since all the related logic
lives in LargeObject now too, and this allows us to remove BoundaryTagInlines.h.
* bmalloc.xcodeproj/project.pbxproj:
* bmalloc/BoundaryTagInlines.h: Removed.
* bmalloc/FreeList.cpp: Copied from Source/bmalloc/bmalloc/SegregatedFreeList.cpp.
(bmalloc::FreeList::takeGreedy):
(bmalloc::FreeList::take):
(bmalloc::SegregatedFreeList::SegregatedFreeList): Deleted.
(bmalloc::SegregatedFreeList::insert): Deleted.
(bmalloc::SegregatedFreeList::takeGreedy): Deleted.
(bmalloc::SegregatedFreeList::take): Deleted.
* bmalloc/FreeList.h: Copied from Source/bmalloc/bmalloc/SegregatedFreeList.h.
(bmalloc::FreeList::push):
* bmalloc/LargeObject.h:
(bmalloc::LargeObject::init):
* bmalloc/SegregatedFreeList.cpp:
(bmalloc::SegregatedFreeList::SegregatedFreeList):
(bmalloc::SegregatedFreeList::insert):
(bmalloc::SegregatedFreeList::takeGreedy):
(bmalloc::SegregatedFreeList::take):
* bmalloc/SegregatedFreeList.h:
* bmalloc/Sizes.h:
* bmalloc/VMHeap.cpp:
(bmalloc::VMHeap::grow):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourcebmallocChangeLog">trunk/Source/bmalloc/ChangeLog</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="#trunkSourcebmallocbmallocSizesh">trunk/Source/bmalloc/bmalloc/Sizes.h</a></li>
<li><a href="#trunkSourcebmallocbmallocVMHeapcpp">trunk/Source/bmalloc/bmalloc/VMHeap.cpp</a></li>
<li><a href="#trunkSourcebmallocbmallocxcodeprojprojectpbxproj">trunk/Source/bmalloc/bmalloc.xcodeproj/project.pbxproj</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourcebmallocbmallocFreeListcpp">trunk/Source/bmalloc/bmalloc/FreeList.cpp</a></li>
<li><a href="#trunkSourcebmallocbmallocFreeListh">trunk/Source/bmalloc/bmalloc/FreeList.h</a></li>
</ul>
<h3>Removed Paths</h3>
<ul>
<li><a href="#trunkSourcebmallocbmallocBoundaryTagInlinesh">trunk/Source/bmalloc/bmalloc/BoundaryTagInlines.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourcebmallocChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/ChangeLog (180692 => 180693)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/ChangeLog 2015-02-26 19:56:49 UTC (rev 180692)
+++ trunk/Source/bmalloc/ChangeLog 2015-02-26 20:05:14 UTC (rev 180693)
</span><span class="lines">@@ -1,5 +1,42 @@
</span><span class="cx"> 2015-02-26 Geoffrey Garen <ggaren@apple.com>
</span><span class="cx">
</span><ins>+ bmalloc: Refactored SegregatedFreeList and BoundaryTag::init
+ https://bugs.webkit.org/show_bug.cgi?id=142049
+
+ Reviewed by Anders Carlsson.
+
+ Split out a FreeList class from SegregatedFreeList. This will make it
+ easier to add behaviors on free list insertion and removal -- and it's
+ probably how I should have designed things at the start.
+
+ Moved BoundaryTag::init into LargeObject, since all the related logic
+ lives in LargeObject now too, and this allows us to remove BoundaryTagInlines.h.
+
+ * bmalloc.xcodeproj/project.pbxproj:
+ * bmalloc/BoundaryTagInlines.h: Removed.
+ * bmalloc/FreeList.cpp: Copied from Source/bmalloc/bmalloc/SegregatedFreeList.cpp.
+ (bmalloc::FreeList::takeGreedy):
+ (bmalloc::FreeList::take):
+ (bmalloc::SegregatedFreeList::SegregatedFreeList): Deleted.
+ (bmalloc::SegregatedFreeList::insert): Deleted.
+ (bmalloc::SegregatedFreeList::takeGreedy): Deleted.
+ (bmalloc::SegregatedFreeList::take): Deleted.
+ * bmalloc/FreeList.h: Copied from Source/bmalloc/bmalloc/SegregatedFreeList.h.
+ (bmalloc::FreeList::push):
+ * bmalloc/LargeObject.h:
+ (bmalloc::LargeObject::init):
+ * bmalloc/SegregatedFreeList.cpp:
+ (bmalloc::SegregatedFreeList::SegregatedFreeList):
+ (bmalloc::SegregatedFreeList::insert):
+ (bmalloc::SegregatedFreeList::takeGreedy):
+ (bmalloc::SegregatedFreeList::take):
+ * bmalloc/SegregatedFreeList.h:
+ * bmalloc/Sizes.h:
+ * bmalloc/VMHeap.cpp:
+ (bmalloc::VMHeap::grow):
+
+2015-02-26 Geoffrey Garen <ggaren@apple.com>
+
</ins><span class="cx"> bmalloc: free up a bit in BoundaryTag
</span><span class="cx"> https://bugs.webkit.org/show_bug.cgi?id=142048
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocBoundaryTagInlinesh"></a>
<div class="delfile"><h4>Deleted: trunk/Source/bmalloc/bmalloc/BoundaryTagInlines.h (180692 => 180693)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/BoundaryTagInlines.h 2015-02-26 19:56:49 UTC (rev 180692)
+++ trunk/Source/bmalloc/bmalloc/BoundaryTagInlines.h 2015-02-26 20:05:14 UTC (rev 180693)
</span><span class="lines">@@ -1,66 +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 BoundaryTagInlines_h
-#define BoundaryTagInlines_h
-
-#include "Range.h"
-#include "BeginTag.h"
-#include "EndTag.h"
-#include "Inline.h"
-#include "LargeChunk.h"
-
-namespace bmalloc {
-
-inline Range BoundaryTag::init(LargeChunk* chunk)
-{
- Range range(chunk->begin(), chunk->end() - chunk->begin());
-
- BeginTag* beginTag = LargeChunk::beginTag(range.begin());
- beginTag->setRange(range);
- beginTag->setFree(true);
- beginTag->setHasPhysicalPages(false);
-
- EndTag* endTag = LargeChunk::endTag(range.begin(), range.size());
- endTag->init(beginTag);
-
- // Mark the left and right edges of our chunk as allocated. This naturally
- // prevents merging logic from overflowing beyond our chunk, without requiring
- // special-case checks.
-
- EndTag* leftSentinel = beginTag->prev();
- BASSERT(leftSentinel >= static_cast<void*>(chunk));
- leftSentinel->initSentinel();
-
- BeginTag* rightSentinel = endTag->next();
- BASSERT(rightSentinel < static_cast<void*>(range.begin()));
- rightSentinel->initSentinel();
-
- return range;
-}
-
-} // namespace bmalloc
-
-#endif // BoundaryTagInlines_h
</del></span></pre></div>
<a id="trunkSourcebmallocbmallocFreeListcppfromrev180686trunkSourcebmallocbmallocSegregatedFreeListcpp"></a>
<div class="copfile"><h4>Copied: trunk/Source/bmalloc/bmalloc/FreeList.cpp (from rev 180686, trunk/Source/bmalloc/bmalloc/SegregatedFreeList.cpp) (0 => 180693)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/FreeList.cpp (rev 0)
+++ trunk/Source/bmalloc/bmalloc/FreeList.cpp 2015-02-26 20:05:14 UTC (rev 180693)
</span><span class="lines">@@ -0,0 +1,110 @@
</span><ins>+/*
+ * 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.
+ */
+
+#include "BeginTag.h"
+#include "LargeChunk.h"
+#include "FreeList.h"
+#include "Vector.h"
+
+namespace bmalloc {
+
+LargeObject FreeList::takeGreedy(size_t size)
+{
+ for (size_t i = m_vector.size(); i-- > 0; ) {
+ // We don't eagerly remove items when we merge and/or split ranges,
+ // so we need to validate each free list entry before using it.
+ LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
+ if (!largeObject.isValidAndFree(m_vector[i].size())) {
+ m_vector.pop(i);
+ continue;
+ }
+
+ if (largeObject.size() < size)
+ continue;
+
+ m_vector.pop(i);
+ return largeObject;
+ }
+
+ return LargeObject();
+}
+
+LargeObject FreeList::take(size_t size)
+{
+ LargeObject first;
+ size_t end = m_vector.size() > freeListSearchDepth ? m_vector.size() - freeListSearchDepth : 0;
+ for (size_t i = m_vector.size(); i-- > end; ) {
+ // We don't eagerly remove items when we merge and/or split ranges, so
+ // we need to validate each free list entry before using it.
+ LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
+ if (!largeObject.isValidAndFree(m_vector[i].size())) {
+ m_vector.pop(i);
+ continue;
+ }
+
+ if (largeObject.size() < size)
+ continue;
+
+ if (!!first && first.begin() < largeObject.begin())
+ continue;
+
+ first = largeObject;
+ }
+
+ return first;
+}
+
+LargeObject FreeList::take(size_t alignment, size_t size, size_t unalignedSize)
+{
+ BASSERT(isPowerOfTwo(alignment));
+ size_t alignmentMask = alignment - 1;
+
+ LargeObject first;
+ size_t end = m_vector.size() > freeListSearchDepth ? m_vector.size() - freeListSearchDepth : 0;
+ for (size_t i = m_vector.size(); i-- > end; ) {
+ // We don't eagerly remove items when we merge and/or split ranges, so
+ // we need to validate each free list entry before using it.
+ LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
+ if (!largeObject.isValidAndFree(m_vector[i].size())) {
+ m_vector.pop(i);
+ continue;
+ }
+
+ if (largeObject.size() < size)
+ continue;
+
+ if (test(largeObject.begin(), alignmentMask) && largeObject.size() < unalignedSize)
+ continue;
+
+ if (!!first && first.begin() < largeObject.begin())
+ continue;
+
+ first = largeObject;
+ }
+
+ return first;
+}
+
+} // namespace bmalloc
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocFreeListhfromrev180686trunkSourcebmallocbmallocSegregatedFreeListh"></a>
<div class="copfile"><h4>Copied: trunk/Source/bmalloc/bmalloc/FreeList.h (from rev 180686, trunk/Source/bmalloc/bmalloc/SegregatedFreeList.h) (0 => 180693)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/FreeList.h (rev 0)
+++ trunk/Source/bmalloc/bmalloc/FreeList.h 2015-02-26 20:05:14 UTC (rev 180693)
</span><span class="lines">@@ -0,0 +1,56 @@
</span><ins>+/*
+ * 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 FreeList_h
+#define FreeList_h
+
+#include "LargeObject.h"
+#include "Vector.h"
+
+namespace bmalloc {
+
+// Helper object for SegregatedFreeList.
+
+class FreeList {
+public:
+ void push(const LargeObject&);
+
+ LargeObject take(size_t);
+ LargeObject take(size_t alignment, size_t, size_t unalignedSize);
+ LargeObject takeGreedy(size_t);
+
+private:
+ Vector<Range> m_vector;
+};
+
+inline void FreeList::push(const LargeObject& largeObject)
+{
+ BASSERT(largeObject.isFree());
+ m_vector.push(largeObject.range());
+}
+
+} // namespace bmalloc
+
+#endif // FreeList_h
</ins></span></pre></div>
<a id="trunkSourcebmallocbmallocLargeObjecth"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/LargeObject.h (180692 => 180693)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/LargeObject.h 2015-02-26 19:56:49 UTC (rev 180692)
+++ trunk/Source/bmalloc/bmalloc/LargeObject.h 2015-02-26 20:05:14 UTC (rev 180693)
</span><span class="lines">@@ -29,11 +29,14 @@
</span><span class="cx"> #include "BeginTag.h"
</span><span class="cx"> #include "EndTag.h"
</span><span class="cx"> #include "LargeChunk.h"
</span><ins>+#include "Range.h"
</ins><span class="cx">
</span><span class="cx"> namespace bmalloc {
</span><span class="cx">
</span><span class="cx"> class LargeObject {
</span><span class="cx"> public:
</span><ins>+ static Range init(LargeChunk*);
+
</ins><span class="cx"> LargeObject();
</span><span class="cx"> LargeObject(void*);
</span><span class="cx">
</span><span class="lines">@@ -237,6 +240,33 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+inline Range LargeObject::init(LargeChunk* chunk)
+{
+ Range range(chunk->begin(), chunk->end() - chunk->begin());
+
+ BeginTag* beginTag = LargeChunk::beginTag(range.begin());
+ beginTag->setRange(range);
+ beginTag->setFree(true);
+ beginTag->setHasPhysicalPages(false);
+
+ EndTag* endTag = LargeChunk::endTag(range.begin(), range.size());
+ endTag->init(beginTag);
+
+ // Mark the left and right edges of our chunk as allocated. This naturally
+ // prevents merging logic from overflowing beyond our chunk, without requiring
+ // special-case checks.
+
+ EndTag* leftSentinel = beginTag->prev();
+ BASSERT(leftSentinel >= static_cast<void*>(chunk));
+ leftSentinel->initSentinel();
+
+ BeginTag* rightSentinel = endTag->next();
+ BASSERT(rightSentinel < static_cast<void*>(range.begin()));
+ rightSentinel->initSentinel();
+
+ return range;
+}
+
</ins><span class="cx"> } // namespace bmalloc
</span><span class="cx">
</span><span class="cx"> #endif // LargeObject_h
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocSegregatedFreeListcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/SegregatedFreeList.cpp (180692 => 180693)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/SegregatedFreeList.cpp 2015-02-26 19:56:49 UTC (rev 180692)
+++ trunk/Source/bmalloc/bmalloc/SegregatedFreeList.cpp 2015-02-26 20:05:14 UTC (rev 180693)
</span><span class="lines">@@ -23,29 +23,25 @@
</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 "BeginTag.h"
-#include "LargeChunk.h"
</del><span class="cx"> #include "SegregatedFreeList.h"
</span><del>-#include "Vector.h"
</del><span class="cx">
</span><span class="cx"> namespace bmalloc {
</span><span class="cx">
</span><span class="cx"> SegregatedFreeList::SegregatedFreeList()
</span><span class="cx"> {
</span><del>- BASSERT(static_cast<size_t>(&select(largeMax) - m_lists.begin()) == m_lists.size() - 1);
</del><ins>+ BASSERT(static_cast<size_t>(&select(largeMax) - m_freeLists.begin()) == m_freeLists.size() - 1);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void SegregatedFreeList::insert(const LargeObject& largeObject)
</span><span class="cx"> {
</span><del>- BASSERT(largeObject.isFree());
</del><span class="cx"> auto& list = select(largeObject.size());
</span><del>- list.push(largeObject.range());
</del><ins>+ list.push(largeObject);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> LargeObject SegregatedFreeList::takeGreedy(size_t size)
</span><span class="cx"> {
</span><del>- for (size_t i = m_lists.size(); i-- > 0; ) {
- LargeObject largeObject = takeGreedy(m_lists[i], size);
</del><ins>+ for (size_t i = m_freeLists.size(); i-- > 0; ) {
+ LargeObject largeObject = m_freeLists[i].takeGreedy(size);
</ins><span class="cx"> if (!largeObject)
</span><span class="cx"> continue;
</span><span class="cx">
</span><span class="lines">@@ -54,31 +50,10 @@
</span><span class="cx"> return LargeObject();
</span><span class="cx"> }
</span><span class="cx">
</span><del>-LargeObject SegregatedFreeList::takeGreedy(List& list, size_t size)
-{
- for (size_t i = list.size(); i-- > 0; ) {
- // We don't eagerly remove items when we merge and/or split ranges,
- // so we need to validate each free list entry before using it.
- LargeObject largeObject(LargeObject::DoNotValidate, list[i].begin());
- if (!largeObject.isValidAndFree(list[i].size())) {
- list.pop(i);
- continue;
- }
-
- if (largeObject.size() < size)
- continue;
-
- list.pop(i);
- return largeObject;
- }
-
- return LargeObject();
-}
-
</del><span class="cx"> LargeObject SegregatedFreeList::take(size_t size)
</span><span class="cx"> {
</span><del>- for (auto* list = &select(size); list != m_lists.end(); ++list) {
- LargeObject largeObject = take(*list, size);
</del><ins>+ for (auto* list = &select(size); list != m_freeLists.end(); ++list) {
+ LargeObject largeObject = list->take(size);
</ins><span class="cx"> if (!largeObject)
</span><span class="cx"> continue;
</span><span class="cx">
</span><span class="lines">@@ -89,8 +64,8 @@
</span><span class="cx">
</span><span class="cx"> LargeObject SegregatedFreeList::take(size_t alignment, size_t size, size_t unalignedSize)
</span><span class="cx"> {
</span><del>- for (auto* list = &select(size); list != m_lists.end(); ++list) {
- LargeObject largeObject = take(*list, alignment, size, unalignedSize);
</del><ins>+ for (auto* list = &select(size); list != m_freeLists.end(); ++list) {
+ LargeObject largeObject = list->take(alignment, size, unalignedSize);
</ins><span class="cx"> if (!largeObject)
</span><span class="cx"> continue;
</span><span class="cx">
</span><span class="lines">@@ -99,7 +74,7 @@
</span><span class="cx"> return LargeObject();
</span><span class="cx"> }
</span><span class="cx">
</span><del>-INLINE auto SegregatedFreeList::select(size_t size) -> List&
</del><ins>+INLINE auto SegregatedFreeList::select(size_t size) -> FreeList&
</ins><span class="cx"> {
</span><span class="cx"> size_t alignCount = (size - largeMin) / largeAlignment;
</span><span class="cx"> size_t result = 0;
</span><span class="lines">@@ -107,63 +82,7 @@
</span><span class="cx"> ++result;
</span><span class="cx"> alignCount >>= 1;
</span><span class="cx"> }
</span><del>- return m_lists[result];
</del><ins>+ return m_freeLists[result];
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-INLINE LargeObject SegregatedFreeList::take(List& list, size_t size)
-{
- LargeObject first;
- size_t end = list.size() > segregatedFreeListSearchDepth ? list.size() - segregatedFreeListSearchDepth : 0;
- for (size_t i = list.size(); i-- > end; ) {
- // We don't eagerly remove items when we merge and/or split ranges, so
- // we need to validate each free list entry before using it.
- LargeObject largeObject(LargeObject::DoNotValidate, list[i].begin());
- if (!largeObject.isValidAndFree(list[i].size())) {
- list.pop(i);
- continue;
- }
-
- if (largeObject.size() < size)
- continue;
-
- if (!!first && first.begin() < largeObject.begin())
- continue;
-
- first = largeObject;
- }
-
- return first;
-}
-
-INLINE LargeObject SegregatedFreeList::take(List& list, size_t alignment, size_t size, size_t unalignedSize)
-{
- BASSERT(isPowerOfTwo(alignment));
- size_t alignmentMask = alignment - 1;
-
- LargeObject first;
- size_t end = list.size() > segregatedFreeListSearchDepth ? list.size() - segregatedFreeListSearchDepth : 0;
- for (size_t i = list.size(); i-- > end; ) {
- // We don't eagerly remove items when we merge and/or split ranges, so
- // we need to validate each free list entry before using it.
- LargeObject largeObject(LargeObject::DoNotValidate, list[i].begin());
- if (!largeObject.isValidAndFree(list[i].size())) {
- list.pop(i);
- continue;
- }
-
- if (largeObject.size() < size)
- continue;
-
- if (test(largeObject.begin(), alignmentMask) && largeObject.size() < unalignedSize)
- continue;
-
- if (!!first && first.begin() < largeObject.begin())
- continue;
-
- first = largeObject;
- }
-
- return first;
-}
-
</del><span class="cx"> } // namespace bmalloc
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocSegregatedFreeListh"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/SegregatedFreeList.h (180692 => 180693)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/SegregatedFreeList.h 2015-02-26 19:56:49 UTC (rev 180692)
+++ trunk/Source/bmalloc/bmalloc/SegregatedFreeList.h 2015-02-26 20:05:14 UTC (rev 180693)
</span><span class="lines">@@ -26,8 +26,7 @@
</span><span class="cx"> #ifndef SegregatedFreeList_h
</span><span class="cx"> #define SegregatedFreeList_h
</span><span class="cx">
</span><del>-#include "LargeObject.h"
-#include "Vector.h"
</del><ins>+#include "FreeList.h"
</ins><span class="cx"> #include <array>
</span><span class="cx">
</span><span class="cx"> namespace bmalloc {
</span><span class="lines">@@ -58,14 +57,9 @@
</span><span class="cx"> LargeObject takeGreedy(size_t);
</span><span class="cx">
</span><span class="cx"> private:
</span><del>- typedef Vector<Range> List;
</del><ins>+ FreeList& select(size_t);
</ins><span class="cx">
</span><del>- List& select(size_t);
- LargeObject take(List&, size_t);
- LargeObject take(List&, size_t alignment, size_t, size_t unalignedSize);
- LargeObject takeGreedy(List&, size_t);
-
- std::array<List, 19> m_lists;
</del><ins>+ std::array<FreeList, 19> m_freeLists;
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> } // namespace bmalloc
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocSizesh"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/Sizes.h (180692 => 180693)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Sizes.h 2015-02-26 19:56:49 UTC (rev 180692)
+++ trunk/Source/bmalloc/bmalloc/Sizes.h 2015-02-26 20:05:14 UTC (rev 180693)
</span><span class="lines">@@ -81,7 +81,7 @@
</span><span class="cx">
</span><span class="cx"> static const size_t xLargeAlignment = vmPageSize;
</span><span class="cx">
</span><del>- static const size_t segregatedFreeListSearchDepth = 16;
</del><ins>+ static const size_t freeListSearchDepth = 16;
</ins><span class="cx">
</span><span class="cx"> static const uintptr_t typeMask = (superChunkSize - 1) & ~((superChunkSize / 4) - 1); // 4 taggable chunks
</span><span class="cx"> static const uintptr_t smallType = (superChunkSize + smallChunkOffset) & typeMask;
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocVMHeapcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/VMHeap.cpp (180692 => 180693)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/VMHeap.cpp 2015-02-26 19:56:49 UTC (rev 180692)
+++ trunk/Source/bmalloc/bmalloc/VMHeap.cpp 2015-02-26 20:05:14 UTC (rev 180693)
</span><span class="lines">@@ -23,8 +23,7 @@
</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 "BoundaryTagInlines.h"
-#include "LargeChunk.h"
</del><ins>+#include "LargeObject.h"
</ins><span class="cx"> #include "Line.h"
</span><span class="cx"> #include "PerProcess.h"
</span><span class="cx"> #include "SuperChunk.h"
</span><span class="lines">@@ -53,7 +52,7 @@
</span><span class="cx"> m_mediumPages.push(it);
</span><span class="cx">
</span><span class="cx"> LargeChunk* largeChunk = superChunk->largeChunk();
</span><del>- m_largeObjects.insert(LargeObject(BoundaryTag::init(largeChunk).begin()));
</del><ins>+ m_largeObjects.insert(LargeObject(LargeObject::init(largeChunk).begin()));
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> } // namespace bmalloc
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc.xcodeproj/project.pbxproj (180692 => 180693)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc.xcodeproj/project.pbxproj 2015-02-26 19:56:49 UTC (rev 180692)
+++ trunk/Source/bmalloc/bmalloc.xcodeproj/project.pbxproj 2015-02-26 20:05:14 UTC (rev 180693)
</span><span class="lines">@@ -9,12 +9,13 @@
</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>- 1400274B18F89C3D00115C97 /* BoundaryTagInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 14105E7B18DBD7AF003A106E /* BoundaryTagInlines.h */; settings = {ATTRIBUTES = (Private, ); }; };
</del><span class="cx"> 1400274C18F89C3D00115C97 /* SegregatedFreeList.h in Headers */ = {isa = PBXBuildFile; fileRef = 146BEE1E18C841C50002D5A2 /* SegregatedFreeList.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><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"> 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><ins>+ 143EF9AF1A9FABF6004F5C77 /* FreeList.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 143EF9AD1A9FABF6004F5C77 /* FreeList.cpp */; };
+ 143EF9B01A9FABF6004F5C77 /* FreeList.h in Headers */ = {isa = PBXBuildFile; fileRef = 143EF9AE1A9FABF6004F5C77 /* FreeList.h */; };
</ins><span class="cx"> 1440AFC91A95142400837FAA /* SuperChunk.h in Headers */ = {isa = PBXBuildFile; fileRef = 1440AFC81A95142400837FAA /* SuperChunk.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><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="lines">@@ -80,7 +81,6 @@
</span><span class="cx"> /* Begin PBXFileReference section */
</span><span class="cx"> 140FA00219CE429C00FFD3C8 /* BumpRange.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = BumpRange.h; path = bmalloc/BumpRange.h; sourceTree = "<group>"; };
</span><span class="cx"> 140FA00419CE4B6800FFD3C8 /* LineMetadata.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = LineMetadata.h; path = bmalloc/LineMetadata.h; sourceTree = "<group>"; };
</span><del>- 14105E7B18DBD7AF003A106E /* BoundaryTagInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = BoundaryTagInlines.h; path = bmalloc/BoundaryTagInlines.h; sourceTree = "<group>"; };
</del><span class="cx"> 14105E8318E14374003A106E /* ObjectType.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = ObjectType.cpp; path = bmalloc/ObjectType.cpp; sourceTree = "<group>"; };
</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="lines">@@ -94,6 +94,8 @@
</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"> 143E29E918CAE8BE00FE8A0F /* MediumPage.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = MediumPage.h; path = bmalloc/MediumPage.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><ins>+ 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>"; };
</ins><span class="cx"> 1440AFC81A95142400837FAA /* SuperChunk.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = SuperChunk.h; path = bmalloc/SuperChunk.h; sourceTree = "<group>"; };
</span><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="lines">@@ -217,8 +219,9 @@
</span><span class="cx"> children = (
</span><span class="cx"> 1417F64518B54A700076FA3F /* BeginTag.h */,
</span><span class="cx"> 1485655E18A43AF900ED6942 /* BoundaryTag.h */,
</span><del>- 14105E7B18DBD7AF003A106E /* BoundaryTagInlines.h */,
</del><span class="cx"> 1417F64618B54A700076FA3F /* EndTag.h */,
</span><ins>+ 143EF9AD1A9FABF6004F5C77 /* FreeList.cpp */,
+ 143EF9AE1A9FABF6004F5C77 /* FreeList.h */,
</ins><span class="cx"> 147AAA8818CD17CE002201E4 /* LargeChunk.h */,
</span><span class="cx"> 14C6216E1A9A9A6200E72293 /* LargeObject.h */,
</span><span class="cx"> 146BEE2118C845AE0002D5A2 /* SegregatedFreeList.cpp */,
</span><span class="lines">@@ -334,6 +337,7 @@
</span><span class="cx"> 14DD78C718F48D7500950702 /* BAssert.h in Headers */,
</span><span class="cx"> 14DD78D018F48D7500950702 /* VMAllocate.h in Headers */,
</span><span class="cx"> 1440AFC91A95142400837FAA /* SuperChunk.h in Headers */,
</span><ins>+ 143EF9B01A9FABF6004F5C77 /* FreeList.h in Headers */,
</ins><span class="cx"> 14DD78CE18F48D7500950702 /* Syscall.h in Headers */,
</span><span class="cx"> 14DD78C618F48D7500950702 /* AsyncTask.h in Headers */,
</span><span class="cx"> 14DD78BA18F48D6B00950702 /* Page.h in Headers */,
</span><span class="lines">@@ -346,7 +350,6 @@
</span><span class="cx"> 140FA00319CE429C00FFD3C8 /* BumpRange.h in Headers */,
</span><span class="cx"> 14DD78C518F48D7500950702 /* Algorithm.h in Headers */,
</span><span class="cx"> 14DD78BD18F48D6B00950702 /* SmallPage.h in Headers */,
</span><del>- 1400274B18F89C3D00115C97 /* BoundaryTagInlines.h in Headers */,
</del><span class="cx"> 14DD788E18F48CCD00950702 /* BoundaryTag.h in Headers */,
</span><span class="cx"> 14DD78C818F48D7500950702 /* FixedVector.h in Headers */,
</span><span class="cx"> 14DD78B718F48D6B00950702 /* MediumLine.h in Headers */,
</span><span class="lines">@@ -439,6 +442,7 @@
</span><span class="cx"> 14F271C618EA3983008C152F /* SegregatedFreeList.cpp in Sources */,
</span><span class="cx"> 14F271C318EA3978008C152F /* Allocator.cpp in Sources */,
</span><span class="cx"> 14895D911A3A319C0006235D /* Environment.cpp in Sources */,
</span><ins>+ 143EF9AF1A9FABF6004F5C77 /* FreeList.cpp in Sources */,
</ins><span class="cx"> 14F271C718EA3990008C152F /* Heap.cpp in Sources */,
</span><span class="cx"> 14F271C918EA3990008C152F /* VMHeap.cpp in Sources */,
</span><span class="cx"> 14F271C818EA3990008C152F /* ObjectType.cpp in Sources */,
</span></span></pre>
</div>
</div>
</body>
</html>