Changeset 180701 in webkit

Timestamp:

Feb 26, 2015, 2:24:37 PM (12 years ago)

Author:

ggaren@apple.com

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.

Location:

trunk/Source/bmalloc

Files:

• ChangeLog (modified) (1 diff)
• bmalloc/BoundaryTag.h (modified) (3 diffs)
• bmalloc/FreeList.cpp (modified) (1 diff)
• bmalloc/FreeList.h (modified) (1 diff)
• bmalloc/LargeObject.h (modified) (3 diffs)
• bmalloc/Sizes.h (modified) (1 diff)

trunk/Source/bmalloc/ChangeLog

@@ +1 @@
+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>
 

trunk/Source/bmalloc/bmalloc/BoundaryTag.h

@@ -52 +52 @@
     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; }
@@ -68 +71 @@
 
 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;
@@ -83 +86 @@
     bool m_isEnd: 1;
     bool m_hasPhysicalPages: 1;
+    bool m_isMarked: 1;
     unsigned m_compactBegin: compactBeginBits;
     unsigned m_size: sizeBits;

trunk/Source/bmalloc/bmalloc/FreeList.cpp

@@ -108 +108 @@
 }
 
+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

trunk/Source/bmalloc/bmalloc/FreeList.h

@@ -36 +36 @@
 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());
 }

trunk/Source/bmalloc/bmalloc/LargeObject.h

@@ -56 +56 @@
     void setHasPhysicalPages(bool) const;
     
+    bool isMarked() const;
+    void setMarked(bool) const;
+    
     bool isValidAndFree(size_t) const;
 
@@ -125 +128 @@
     m_beginTag->setHasPhysicalPages(hasPhysicalPages);
     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);
 }
 
@@ -224 +240 @@
     BASSERT(m_beginTag->isFree() == m_endTag->isFree());
     BASSERT(m_beginTag->hasPhysicalPages() == m_endTag->hasPhysicalPages());
+    BASSERT(m_beginTag->isMarked() == m_endTag->isMarked());
 }
 

trunk/Source/bmalloc/bmalloc/Sizes.h

@@ -83 +83 @@
 
     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