bmalloc: Large object free list can grow infinitely
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 26 Feb 2015 22:24:37 +0000 (22:24 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 26 Feb 2015 22:24:37 +0000 (22:24 +0000)
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.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@180701 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/bmalloc/ChangeLog
Source/bmalloc/bmalloc/BoundaryTag.h
Source/bmalloc/bmalloc/FreeList.cpp
Source/bmalloc/bmalloc/FreeList.h
Source/bmalloc/bmalloc/LargeObject.h
Source/bmalloc/bmalloc/Sizes.h

index 4261d5f..58d92a7 100644 (file)
@@ -1,3 +1,49 @@
+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.
+
 2015-02-26  Csaba Osztrogon√°c  <ossy@webkit.org>
 
         URTBF after r180693.
index c51c956..99c4c50 100644 (file)
@@ -51,6 +51,9 @@ public:
 
     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 @@ public:
     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 @@ private:
     bool m_isFree: 1;
     bool m_isEnd: 1;
     bool m_hasPhysicalPages: 1;
+    bool m_isMarked: 1;
     unsigned m_compactBegin: compactBeginBits;
     unsigned m_size: sizeBits;
 };
index bb4f51d..d2dca87 100644 (file)
@@ -107,4 +107,28 @@ LargeObject FreeList::take(size_t alignment, size_t size, size_t unalignedSize)
     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
index 2abaebb..914da2d 100644 (file)
@@ -35,19 +35,35 @@ namespace bmalloc {
 
 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());
 }
 
index c63cc47..9d883cb 100644 (file)
@@ -55,6 +55,9 @@ public:
     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 @@ inline void LargeObject::setHasPhysicalPages(bool hasPhysicalPages) const
     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 @@ inline void LargeObject::validateSelf() const
     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
index 651d076..44e07d5 100644 (file)
@@ -82,6 +82,7 @@ namespace Sizes {
     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;