Changeset 173224 in webkit

Timestamp:

Sep 3, 2014 2:00:33 PM (10 years ago)

Author:

ggaren@apple.com

Message:

bmalloc crashes on the EWS bots (due to bad large object allocation)
​https://bugs.webkit.org/show_bug.cgi?id=136469

Reviewed by Andreas Kling.

It's possible to convince bmalloc to perform a bad large object allocation,
through these steps:

(1) Insert object A into freelist F0.

(2) Split, merge and split again A's neighbors such that object B is
inserted into freelist F0, with boundary tag and size equal to object A,
but pointer not completely equal to object A. Put object B at the head of F0.

(3) Allocate some other object from F0, swapping its position in the
freelist with object B, such that object A is now ahead of object B.

--> Now, the next allocation for size A/B will allocate object A, which
has a slightly wrong idea about where the object actually begins.
Immediately, you'll corrupt a little memory, and over time, you'll also
corrupt boundary tag metadata.

The solution is to store the begin pointer in the boundary tag. Luckily,
this doesn't make the tag any bigger, and it's not a noticeable slowdown
on MallocBench.

• bmalloc/Algorithm.h:

(bmalloc::rightShift):

• bmalloc/BeginTag.h:

(bmalloc::BeginTag::isInFreeList): This is the bug fix. Make sure to
validate the start pointer when popping off the free list. Through a
very uncommon set of steps, it is possible to have an item in the free
list that is valid by all accounts except for its start pointer.

• bmalloc/BoundaryTag.h:

(bmalloc::BoundaryTag::compactBegin):
(bmalloc::BoundaryTag::setRange):
(bmalloc::BoundaryTag::setSize): Deleted. Record a compact version of the
start pointer. We don't need the whole pointer -- just the offset, in
largeAlignment increments, into the relevant boundary tag bucket.

• bmalloc/BoundaryTagInlines.h:

(bmalloc::validateNext):
(bmalloc::BoundaryTag::init):
(bmalloc::BoundaryTag::mergeLarge):
(bmalloc::BoundaryTag::splitLarge):

• bmalloc/SegregatedFreeList.cpp:

(bmalloc::SegregatedFreeList::insert):
(bmalloc::SegregatedFreeList::takeGreedy):
(bmalloc::SegregatedFreeList::take): Provide the whole range instead of
the size when establishing a boundary tag, as required by the new
interface.

• bmalloc/Sizes.h:

Location:

trunk/Source/bmalloc

Files:

• ChangeLog (modified) (1 diff)
• bmalloc/Algorithm.h (modified) (1 diff)
• bmalloc/BeginTag.h (modified) (1 diff)
• bmalloc/BoundaryTag.h (modified) (5 diffs)
• bmalloc/BoundaryTagInlines.h (modified) (6 diffs)
• bmalloc/SegregatedFreeList.cpp (modified) (3 diffs)
• bmalloc/Sizes.h (modified) (1 diff)

trunk/Source/bmalloc/ChangeLog

@@ +1 @@
+2014-09-02  Geoffrey Garen  <ggaren@apple.com>
+
+        bmalloc crashes on the EWS bots (due to bad large object allocation)
+        https://bugs.webkit.org/show_bug.cgi?id=136469
+
+        Reviewed by Andreas Kling.
+
+        It's possible to convince bmalloc to perform a bad large object allocation,
+        through these steps:
+
+        (1) Insert object A into freelist F0.
+
+        (2) Split, merge and split again A's neighbors such that object B is
+        inserted into freelist F0, with boundary tag and size equal to object A,
+        but pointer not completely equal to object A. Put object B at the head of F0.
+
+        (3) Allocate some other object from F0, swapping its position in the
+        freelist with object B, such that object A is now ahead of object B.
+
+        --> Now, the next allocation for size A/B will allocate object A, which
+        has a slightly wrong idea about where the object actually begins.
+        Immediately, you'll corrupt a little memory, and over time, you'll also
+        corrupt boundary tag metadata.
+
+        The solution is to store the begin pointer in the boundary tag. Luckily,
+        this doesn't make the tag any bigger, and it's not a noticeable slowdown
+        on MallocBench.
+
+        * bmalloc/Algorithm.h:
+        (bmalloc::rightShift):
+        * bmalloc/BeginTag.h:
+        (bmalloc::BeginTag::isInFreeList): This is the bug fix. Make sure to
+        validate the start pointer when popping off the free list. Through a
+        very uncommon set of steps, it is possible to have an item in the free
+        list that is valid by all accounts except for its start pointer.
+
+        * bmalloc/BoundaryTag.h:
+        (bmalloc::BoundaryTag::compactBegin):
+        (bmalloc::BoundaryTag::setRange):
+        (bmalloc::BoundaryTag::setSize): Deleted. Record a compact version of the
+        start pointer. We don't need the whole pointer -- just the offset, in
+        largeAlignment increments, into the relevant boundary tag bucket.
+
+        * bmalloc/BoundaryTagInlines.h:
+        (bmalloc::validateNext):
+        (bmalloc::BoundaryTag::init):
+        (bmalloc::BoundaryTag::mergeLarge):
+        (bmalloc::BoundaryTag::splitLarge):
+        * bmalloc/SegregatedFreeList.cpp:
+        (bmalloc::SegregatedFreeList::insert):
+        (bmalloc::SegregatedFreeList::takeGreedy):
+        (bmalloc::SegregatedFreeList::take): Provide the whole range instead of
+        the size when establishing a boundary tag, as required by the new
+        interface.
+
+        * bmalloc/Sizes.h:
+
 2014-08-14  Geoffrey Garen  <ggaren@apple.com>
 

trunk/Source/bmalloc/bmalloc/Algorithm.h

@@ -47 +47 @@
     return a < b ? a : b;
 }
-    
+
 template<typename T> inline constexpr T mask(T value, uintptr_t mask)
 {
     return reinterpret_cast<T>(reinterpret_cast<uintptr_t>(value) & mask);
+}
+
+template<typename T> inline constexpr T rightShift(T value, uintptr_t shift)
+{
+    return reinterpret_cast<T>(reinterpret_cast<uintptr_t>(value) >> shift);
 }
 

trunk/Source/bmalloc/bmalloc/BeginTag.h

@@ -33 +33 @@
 class BeginTag : public BoundaryTag {
 public:
-    bool isInFreeList(size_t);
+    bool isInFreeList(const Range&);
 };
 
-inline bool BeginTag::isInFreeList(size_t size)
+inline bool BeginTag::isInFreeList(const Range& range)
 {
-    return isFree() && !isEnd() && this->size() == size;
+    return isFree() && !isEnd() && this->size() == range.size() && this->compactBegin() == compactBegin(range);
 }
 

trunk/Source/bmalloc/bmalloc/BoundaryTag.h

@@ -28 +28 @@
 
 #include "BAssert.h"
+#include "Range.h"
 #include "Sizes.h"
 
@@ -42 +43 @@
     static Range deallocate(void*);
     static void allocate(size_t, Range&, Range& leftover, bool& hasPhysicalPages);
+    static unsigned compactBegin(const Range&);
 
     bool isXLarge() { return m_size == xLargeMarker; }
@@ -59 +61 @@
     
     size_t size() { return m_size; }
-    void setSize(size_t);
+    unsigned compactBegin() { return m_compactBegin; }
+
+    void setRange(const Range&);
     
     EndTag* prev();
@@ -66 +70 @@
 private:
     static const size_t flagBits = 3;
-    static const size_t sizeBits = bitCount<unsigned>() - flagBits;
+    static const size_t compactBeginBits = 5;
+    static const size_t sizeBits = bitCount<unsigned>() - flagBits - compactBeginBits;
     static const size_t xLargeMarker = 1; // This size is unused because our minimum object size is greater than it.
 
     static_assert(largeMin > xLargeMarker, "largeMin must provide enough umbrella to fit xLargeMarker.");
+    static_assert((1 << compactBeginBits) - 1 >= largeMin / largeAlignment, "compactBegin must be encodable in a BoundaryTag.");
     static_assert((1 << sizeBits) - 1 >= largeMax, "largeMax must be encodable in a BoundaryTag.");
 
@@ -80 +86 @@
     bool m_isEnd: 1;
     bool m_hasPhysicalPages: 1;
+    unsigned m_compactBegin: compactBeginBits;
     unsigned m_size: sizeBits;
 };
 
-inline void BoundaryTag::setSize(size_t size)
+inline unsigned BoundaryTag::compactBegin(const Range& range)
 {
-    m_size = static_cast<unsigned>(size);
-    BASSERT(this->size() == size);
+    return static_cast<unsigned>(
+        reinterpret_cast<uintptr_t>(
+            rightShift(
+                mask(range.begin(), largeMin - 1), largeAlignmentShift)));
+}
+
+inline void BoundaryTag::setRange(const Range& range)
+{
+    m_compactBegin = compactBegin(range);
+    m_size = static_cast<unsigned>(range.size());
+    BASSERT(this->size() == range.size());
     BASSERT(!isXLarge());
 }

trunk/Source/bmalloc/bmalloc/BoundaryTagInlines.h

@@ -65 +65 @@
 static inline void validateNext(BeginTag* next, const Range& range)
 {
-    if (next->size() == largeMin && !next->isFree()) // Right sentinel tag.
+    if (next->size() == largeMin && !next->compactBegin() && !next->isFree()) // Right sentinel tag.
         return;
 
@@ -85 +85 @@
 
     BeginTag* beginTag = LargeChunk::beginTag(range.begin());
-    beginTag->setSize(range.size());
+    beginTag->setRange(range);
     beginTag->setFree(true);
     beginTag->setHasPhysicalPages(false);
@@ -98 +98 @@
     EndTag* leftSentinel = beginTag->prev();
     BASSERT(leftSentinel >= static_cast<void*>(chunk));
-    leftSentinel->setSize(largeMin);
+    leftSentinel->setRange(Range(nullptr, largeMin));
     leftSentinel->setFree(false);
 
     BeginTag* rightSentinel = endTag->next();
     BASSERT(rightSentinel < static_cast<void*>(range.begin()));
-    rightSentinel->setSize(largeMin);
+    rightSentinel->setRange(Range(nullptr, largeMin));
     rightSentinel->setFree(false);
     
@@ -151 +151 @@
         mergeLargeRight(endTag, next, range, hasPhysicalPages);
 
-    beginTag->setSize(range.size());
+    beginTag->setRange(range);
     beginTag->setFree(true);
     beginTag->setHasPhysicalPages(hasPhysicalPages);
@@ -176 +176 @@
 INLINE void BoundaryTag::splitLarge(BeginTag* beginTag, size_t size, EndTag*& endTag, Range& range, Range& leftover)
 {
-    beginTag->setSize(size);
+    leftover = Range(range.begin() + size, range.size() - size);
+    range = Range(range.begin(), size);
+
+    beginTag->setRange(range);
 
     EndTag* splitEndTag = LargeChunk::endTag(range.begin(), size);
@@ -182 +185 @@
         *splitEndTag = *beginTag;
 
-    leftover = Range(range.begin() + size, range.size() - size);
     BASSERT(leftover.size() >= largeMin);
     BeginTag* leftoverBeginTag = LargeChunk::beginTag(leftover.begin());
     *leftoverBeginTag = *beginTag;
-    leftoverBeginTag->setSize(leftover.size());
+    leftoverBeginTag->setRange(leftover);
 
     if (leftoverBeginTag != static_cast<BoundaryTag*>(endTag))
         *endTag = *leftoverBeginTag;
 
-    validate(beginTag->prev(), Range(range.begin(), size), leftoverBeginTag);
+    validate(beginTag->prev(), range, leftoverBeginTag);
     validate(leftoverBeginTag->prev(), leftover, endTag->next());
 
-    range = Range(range.begin(), size);
     endTag = splitEndTag;
 }

trunk/Source/bmalloc/bmalloc/SegregatedFreeList.cpp

@@ -40 +40 @@
 IF_DEBUG(
     BeginTag* beginTag = LargeChunk::beginTag(range.begin());
-    BASSERT(beginTag->isInFreeList(range.size()));
+    BASSERT(beginTag->isInFreeList(range));
 )
 
@@ -67 +67 @@
         // so we need to validate each free list entry before using it.
         BeginTag* beginTag = LargeChunk::beginTag(range.begin());
-        if (!beginTag->isInFreeList(range.size())) {
+        if (!beginTag->isInFreeList(range)) {
             list.pop(i);
             continue;
@@ -115 +115 @@
         // we need to validate each free list entry before using it.
         BeginTag* beginTag = LargeChunk::beginTag(range.begin());
-        if (!beginTag->isInFreeList(range.size())) {
+        if (!beginTag->isInFreeList(range)) {
             list.pop(i);
             continue;

trunk/Source/bmalloc/bmalloc/Sizes.h

@@ -69 +69 @@
 
     static const size_t largeAlignment = 64;
+    static const size_t largeAlignmentShift = 6;
+    static_assert(1 << largeAlignmentShift == largeAlignment, "largeAlignmentShift be log2(largeAlignment).");
     static const size_t largeMax = largeChunkSize * 99 / 100; // Plenty of room for metadata.
     static const size_t largeMin = 1024;