<!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>[180701] 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/180701">180701</a></dd>
<dt>Author</dt> <dd>ggaren@apple.com</dd>
<dt>Date</dt> <dd>2015-02-26 14:24:37 -0800 (Thu, 26 Feb 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>bmalloc: Large object free list can grow infinitely
https://bugs.webkit.org/show_bug.cgi?id=142055
Reviewed by Andreas Kling.
By design, we don't eagerly remove large objects from the free list.
This creates two simple pathologies:
(1) If you free and then allocate the same object repeatedly, it will
duplicate itself in the free list repeatedly. Since it is never
invalid at the time of allocation, it will never be removed.
(2) If you split and then merge the same object repeatedly, it will
duplicate its split sibling in the free list repeatedly. If its
sibling is in a separate free list size class, it will never be
consulted at the time of allocation, so it will never be removed.
So, a simple "while (1) { free(malloc(x)); }" causes infinite memory
use in the free list.
The solution in this patch is a simple helper to remove garbage from the
free list if it grows too large. This pathology is not common, so the
cost is OK.
Long-term, perhaps we should rethink the laziness of these free lists.
* bmalloc/BoundaryTag.h:
(bmalloc::BoundaryTag::isMarked):
(bmalloc::BoundaryTag::setMarked): New bit, used by free list GC.
* bmalloc/FreeList.cpp:
(bmalloc::FreeList::removeInvalidAndDuplicateEntries): The GC algorithm.
* bmalloc/FreeList.h:
(bmalloc::FreeList::FreeList):
(bmalloc::FreeList::push): Invoke the GC if we're getting huge.
* bmalloc/LargeObject.h:
(bmalloc::LargeObject::isMarked):
(bmalloc::LargeObject::setMarked):
(bmalloc::LargeObject::validateSelf): Expose the new bit.
* bmalloc/Sizes.h: New constant to control GC frequency.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourcebmallocChangeLog">trunk/Source/bmalloc/ChangeLog</a></li>
<li><a href="#trunkSourcebmallocbmallocBoundaryTagh">trunk/Source/bmalloc/bmalloc/BoundaryTag.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="#trunkSourcebmallocbmallocSizesh">trunk/Source/bmalloc/bmalloc/Sizes.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourcebmallocChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/ChangeLog (180700 => 180701)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/ChangeLog 2015-02-26 22:22:55 UTC (rev 180700)
+++ trunk/Source/bmalloc/ChangeLog 2015-02-26 22:24:37 UTC (rev 180701)
</span><span class="lines">@@ -1,3 +1,49 @@
</span><ins>+2015-02-26 Geoffrey Garen <ggaren@apple.com>
+
+ bmalloc: Large object free list can grow infinitely
+ https://bugs.webkit.org/show_bug.cgi?id=142055
+
+ Reviewed by Andreas Kling.
+
+ By design, we don't eagerly remove large objects from the free list.
+ This creates two simple pathologies:
+
+ (1) If you free and then allocate the same object repeatedly, it will
+ duplicate itself in the free list repeatedly. Since it is never
+ invalid at the time of allocation, it will never be removed.
+
+ (2) If you split and then merge the same object repeatedly, it will
+ duplicate its split sibling in the free list repeatedly. If its
+ sibling is in a separate free list size class, it will never be
+ consulted at the time of allocation, so it will never be removed.
+
+ So, a simple "while (1) { free(malloc(x)); }" causes infinite memory
+ use in the free list.
+
+ The solution in this patch is a simple helper to remove garbage from the
+ free list if it grows too large. This pathology is not common, so the
+ cost is OK.
+
+ Long-term, perhaps we should rethink the laziness of these free lists.
+
+ * bmalloc/BoundaryTag.h:
+ (bmalloc::BoundaryTag::isMarked):
+ (bmalloc::BoundaryTag::setMarked): New bit, used by free list GC.
+
+ * bmalloc/FreeList.cpp:
+ (bmalloc::FreeList::removeInvalidAndDuplicateEntries): The GC algorithm.
+
+ * bmalloc/FreeList.h:
+ (bmalloc::FreeList::FreeList):
+ (bmalloc::FreeList::push): Invoke the GC if we're getting huge.
+
+ * bmalloc/LargeObject.h:
+ (bmalloc::LargeObject::isMarked):
+ (bmalloc::LargeObject::setMarked):
+ (bmalloc::LargeObject::validateSelf): Expose the new bit.
+
+ * bmalloc/Sizes.h: New constant to control GC frequency.
+
</ins><span class="cx"> 2015-02-26 Csaba Osztrogonác <ossy@webkit.org>
</span><span class="cx">
</span><span class="cx"> URTBF after r180693.
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocBoundaryTagh"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/BoundaryTag.h (180700 => 180701)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/BoundaryTag.h 2015-02-26 22:22:55 UTC (rev 180700)
+++ trunk/Source/bmalloc/bmalloc/BoundaryTag.h 2015-02-26 22:24:37 UTC (rev 180701)
</span><span class="lines">@@ -51,6 +51,9 @@
</span><span class="cx">
</span><span class="cx"> bool hasPhysicalPages() { return m_hasPhysicalPages; }
</span><span class="cx"> void setHasPhysicalPages(bool hasPhysicalPages) { m_hasPhysicalPages = hasPhysicalPages; }
</span><ins>+
+ bool isMarked() { return m_isMarked; }
+ void setMarked(bool isMarked) { m_isMarked = isMarked; }
</ins><span class="cx">
</span><span class="cx"> bool isNull() { return !m_size; }
</span><span class="cx"> void clear() { std::memset(this, 0, sizeof(*this)); }
</span><span class="lines">@@ -67,7 +70,7 @@
</span><span class="cx"> BeginTag* next();
</span><span class="cx">
</span><span class="cx"> private:
</span><del>- static const size_t flagBits = 3;
</del><ins>+ static const size_t flagBits = 4;
</ins><span class="cx"> static const size_t compactBeginBits = 4;
</span><span class="cx"> static const size_t sizeBits = bitCount<unsigned>() - flagBits - compactBeginBits;
</span><span class="cx">
</span><span class="lines">@@ -82,6 +85,7 @@
</span><span class="cx"> bool m_isFree: 1;
</span><span class="cx"> bool m_isEnd: 1;
</span><span class="cx"> bool m_hasPhysicalPages: 1;
</span><ins>+ bool m_isMarked: 1;
</ins><span class="cx"> unsigned m_compactBegin: compactBeginBits;
</span><span class="cx"> unsigned m_size: sizeBits;
</span><span class="cx"> };
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocFreeListcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/FreeList.cpp (180700 => 180701)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/FreeList.cpp 2015-02-26 22:22:55 UTC (rev 180700)
+++ trunk/Source/bmalloc/bmalloc/FreeList.cpp 2015-02-26 22:24:37 UTC (rev 180701)
</span><span class="lines">@@ -107,4 +107,28 @@
</span><span class="cx"> return first;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+void FreeList::removeInvalidAndDuplicateEntries()
+{
+ for (size_t i = m_vector.size(); i-- > 0; ) {
+ LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
+ if (!largeObject.isValidAndFree(m_vector[i].size())) {
+ m_vector.pop(i);
+ continue;
+ }
+
+ largeObject.setMarked(false);
+ }
+
+ for (size_t i = m_vector.size(); i-- > 0; ) {
+ LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
+ if (largeObject.isMarked()) {
+ m_vector.pop(i);
+ continue;
+ }
+
+ largeObject.setMarked(true);
+ }
+}
+
+
</ins><span class="cx"> } // namespace bmalloc
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocFreeListh"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/FreeList.h (180700 => 180701)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/FreeList.h 2015-02-26 22:22:55 UTC (rev 180700)
+++ trunk/Source/bmalloc/bmalloc/FreeList.h 2015-02-26 22:24:37 UTC (rev 180701)
</span><span class="lines">@@ -35,19 +35,35 @@
</span><span class="cx">
</span><span class="cx"> class FreeList {
</span><span class="cx"> public:
</span><ins>+ FreeList();
+
</ins><span class="cx"> void push(const LargeObject&);
</span><span class="cx">
</span><span class="cx"> LargeObject take(size_t);
</span><span class="cx"> LargeObject take(size_t alignment, size_t, size_t unalignedSize);
</span><ins>+
</ins><span class="cx"> LargeObject takeGreedy(size_t);
</span><ins>+
+ void removeInvalidAndDuplicateEntries();
</ins><span class="cx">
</span><span class="cx"> private:
</span><span class="cx"> Vector<Range> m_vector;
</span><ins>+ size_t m_limit;
</ins><span class="cx"> };
</span><span class="cx">
</span><ins>+inline FreeList::FreeList()
+ : m_vector()
+ , m_limit(freeListSearchDepth)
+{
+}
+
</ins><span class="cx"> inline void FreeList::push(const LargeObject& largeObject)
</span><span class="cx"> {
</span><span class="cx"> BASSERT(largeObject.isFree());
</span><ins>+ if (m_vector.size() == m_limit) {
+ removeInvalidAndDuplicateEntries();
+ m_limit = std::max(m_vector.size() * freeListGrowFactor, freeListSearchDepth);
+ }
</ins><span class="cx"> m_vector.push(largeObject.range());
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocLargeObjecth"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/LargeObject.h (180700 => 180701)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/LargeObject.h 2015-02-26 22:22:55 UTC (rev 180700)
+++ trunk/Source/bmalloc/bmalloc/LargeObject.h 2015-02-26 22:24:37 UTC (rev 180701)
</span><span class="lines">@@ -55,6 +55,9 @@
</span><span class="cx"> bool hasPhysicalPages() const;
</span><span class="cx"> void setHasPhysicalPages(bool) const;
</span><span class="cx">
</span><ins>+ bool isMarked() const;
+ void setMarked(bool) const;
+
</ins><span class="cx"> bool isValidAndFree(size_t) const;
</span><span class="cx">
</span><span class="cx"> LargeObject merge() const;
</span><span class="lines">@@ -126,6 +129,19 @@
</span><span class="cx"> m_endTag->setHasPhysicalPages(hasPhysicalPages);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+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);
+}
+
</ins><span class="cx"> inline bool LargeObject::isValidAndFree(size_t expectedSize) const
</span><span class="cx"> {
</span><span class="cx"> if (!m_beginTag->isFree())
</span><span class="lines">@@ -223,6 +239,7 @@
</span><span class="cx"> BASSERT(m_beginTag->size() == m_endTag->size());
</span><span class="cx"> BASSERT(m_beginTag->isFree() == m_endTag->isFree());
</span><span class="cx"> BASSERT(m_beginTag->hasPhysicalPages() == m_endTag->hasPhysicalPages());
</span><ins>+ BASSERT(m_beginTag->isMarked() == m_endTag->isMarked());
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> inline void LargeObject::validate() const
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocSizesh"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/Sizes.h (180700 => 180701)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Sizes.h 2015-02-26 22:22:55 UTC (rev 180700)
+++ trunk/Source/bmalloc/bmalloc/Sizes.h 2015-02-26 22:24:37 UTC (rev 180701)
</span><span class="lines">@@ -82,6 +82,7 @@
</span><span class="cx"> static const size_t xLargeAlignment = vmPageSize;
</span><span class="cx">
</span><span class="cx"> static const size_t freeListSearchDepth = 16;
</span><ins>+ static const size_t freeListGrowFactor = 2;
</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>
</div>
</body>
</html>