Title: [180701] trunk/Source/bmalloc
- Revision
- 180701
- Author
- [email protected]
- Date
- 2015-02-26 14:24:37 -0800 (Thu, 26 Feb 2015)
Log Message
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.
Modified Paths
Diff
Modified: trunk/Source/bmalloc/ChangeLog (180700 => 180701)
--- 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)
@@ -1,3 +1,49 @@
+2015-02-26 Geoffrey Garen <[email protected]>
+
+ 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.
+
2015-02-26 Csaba Osztrogonác <[email protected]>
URTBF after r180693.
Modified: trunk/Source/bmalloc/bmalloc/BoundaryTag.h (180700 => 180701)
--- 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)
@@ -51,6 +51,9 @@
bool hasPhysicalPages() { return m_hasPhysicalPages; }
void setHasPhysicalPages(bool hasPhysicalPages) { m_hasPhysicalPages = hasPhysicalPages; }
+
+ 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)); }
@@ -67,7 +70,7 @@
BeginTag* next();
private:
- static const size_t flagBits = 3;
+ static const size_t flagBits = 4;
static const size_t compactBeginBits = 4;
static const size_t sizeBits = bitCount<unsigned>() - flagBits - compactBeginBits;
@@ -82,6 +85,7 @@
bool m_isFree: 1;
bool m_isEnd: 1;
bool m_hasPhysicalPages: 1;
+ bool m_isMarked: 1;
unsigned m_compactBegin: compactBeginBits;
unsigned m_size: sizeBits;
};
Modified: trunk/Source/bmalloc/bmalloc/FreeList.cpp (180700 => 180701)
--- 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)
@@ -107,4 +107,28 @@
return first;
}
+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);
+ }
+}
+
+
} // namespace bmalloc
Modified: trunk/Source/bmalloc/bmalloc/FreeList.h (180700 => 180701)
--- 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)
@@ -35,19 +35,35 @@
class FreeList {
public:
+ FreeList();
+
void push(const LargeObject&);
LargeObject take(size_t);
LargeObject take(size_t alignment, size_t, size_t unalignedSize);
+
LargeObject takeGreedy(size_t);
+
+ void removeInvalidAndDuplicateEntries();
private:
Vector<Range> m_vector;
+ size_t m_limit;
};
+inline FreeList::FreeList()
+ : m_vector()
+ , m_limit(freeListSearchDepth)
+{
+}
+
inline void FreeList::push(const LargeObject& largeObject)
{
BASSERT(largeObject.isFree());
+ if (m_vector.size() == m_limit) {
+ removeInvalidAndDuplicateEntries();
+ m_limit = std::max(m_vector.size() * freeListGrowFactor, freeListSearchDepth);
+ }
m_vector.push(largeObject.range());
}
Modified: trunk/Source/bmalloc/bmalloc/LargeObject.h (180700 => 180701)
--- 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)
@@ -55,6 +55,9 @@
bool hasPhysicalPages() const;
void setHasPhysicalPages(bool) const;
+ bool isMarked() const;
+ void setMarked(bool) const;
+
bool isValidAndFree(size_t) const;
LargeObject merge() const;
@@ -126,6 +129,19 @@
m_endTag->setHasPhysicalPages(hasPhysicalPages);
}
+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(size_t expectedSize) const
{
if (!m_beginTag->isFree())
@@ -223,6 +239,7 @@
BASSERT(m_beginTag->size() == m_endTag->size());
BASSERT(m_beginTag->isFree() == m_endTag->isFree());
BASSERT(m_beginTag->hasPhysicalPages() == m_endTag->hasPhysicalPages());
+ BASSERT(m_beginTag->isMarked() == m_endTag->isMarked());
}
inline void LargeObject::validate() const
Modified: trunk/Source/bmalloc/bmalloc/Sizes.h (180700 => 180701)
--- 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)
@@ -82,6 +82,7 @@
static const size_t xLargeAlignment = vmPageSize;
static const size_t freeListSearchDepth = 16;
+ static const size_t freeListGrowFactor = 2;
static const uintptr_t typeMask = (superChunkSize - 1) & ~((superChunkSize / 4) - 1); // 4 taggable chunks
static const uintptr_t smallType = (superChunkSize + smallChunkOffset) & typeMask;
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes
