bmalloc crashes on the EWS bots (due to bad large object allocation)
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 3 Sep 2014 21:00:33 +0000 (21:00 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 3 Sep 2014 21:00:33 +0000 (21:00 +0000)
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:

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

Source/bmalloc/ChangeLog
Source/bmalloc/bmalloc/Algorithm.h
Source/bmalloc/bmalloc/BeginTag.h
Source/bmalloc/bmalloc/BoundaryTag.h
Source/bmalloc/bmalloc/BoundaryTagInlines.h
Source/bmalloc/bmalloc/SegregatedFreeList.cpp
Source/bmalloc/bmalloc/Sizes.h

index 54a963d..27d4c89 100644 (file)
@@ -1,3 +1,60 @@
+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>
 
         Fixed a bmalloc crash seen on the EWS bot
index 298e5f6..2316a85 100644 (file)
@@ -46,12 +46,17 @@ template<typename T> inline constexpr T min(T a, T b)
 {
     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);
+}
+
 template<typename T> inline constexpr bool test(T value, uintptr_t mask)
 {
     return !!(reinterpret_cast<uintptr_t>(value) & mask);
index 394d49d..ffc6048 100644 (file)
@@ -32,12 +32,12 @@ namespace bmalloc {
 
 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);
 }
 
 } // namespace bmalloc
index 0b251b2..f4a5054 100644 (file)
@@ -27,6 +27,7 @@
 #define BoundaryTag_h
 
 #include "BAssert.h"
+#include "Range.h"
 #include "Sizes.h"
 
 namespace bmalloc {
@@ -41,6 +42,7 @@ public:
     static Range init(LargeChunk*);
     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; }
     void setXLarge() { m_size = xLargeMarker; }
@@ -58,17 +60,21 @@ public:
     void clear() { memset(this, 0, sizeof(*this)); }
     
     size_t size() { return m_size; }
-    void setSize(size_t);
+    unsigned compactBegin() { return m_compactBegin; }
+
+    void setRange(const Range&);
     
     EndTag* prev();
     BeginTag* next();
 
 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.");
 
     static void splitLarge(BeginTag*, size_t size, EndTag*& endTag, Range&, Range& leftover);
@@ -79,13 +85,23 @@ private:
     bool m_isFree: 1;
     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)
+{
+    return static_cast<unsigned>(
+        reinterpret_cast<uintptr_t>(
+            rightShift(
+                mask(range.begin(), largeMin - 1), largeAlignmentShift)));
+}
+
+inline void BoundaryTag::setRange(const Range& range)
 {
-    m_size = static_cast<unsigned>(size);
-    BASSERT(this->size() == size);
+    m_compactBegin = compactBegin(range);
+    m_size = static_cast<unsigned>(range.size());
+    BASSERT(this->size() == range.size());
     BASSERT(!isXLarge());
 }
 
index 4686a8a..5120467 100644 (file)
@@ -64,7 +64,7 @@ static inline void validatePrev(EndTag* prev, void* object)
 
 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;
 
     void* nextObject = range.end();
@@ -84,7 +84,7 @@ inline Range BoundaryTag::init(LargeChunk* chunk)
     Range range(chunk->begin(), chunk->end() - chunk->begin());
 
     BeginTag* beginTag = LargeChunk::beginTag(range.begin());
-    beginTag->setSize(range.size());
+    beginTag->setRange(range);
     beginTag->setFree(true);
     beginTag->setHasPhysicalPages(false);
 
@@ -97,12 +97,12 @@ inline Range BoundaryTag::init(LargeChunk* chunk)
     
     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);
     
     return range;
@@ -150,7 +150,7 @@ INLINE void BoundaryTag::mergeLarge(BeginTag*& beginTag, EndTag*& endTag, Range&
     if (next->isFree())
         mergeLargeRight(endTag, next, range, hasPhysicalPages);
 
-    beginTag->setSize(range.size());
+    beginTag->setRange(range);
     beginTag->setFree(true);
     beginTag->setHasPhysicalPages(hasPhysicalPages);
 
@@ -175,25 +175,26 @@ inline Range BoundaryTag::deallocate(void* object)
 
 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);
     if (splitEndTag != static_cast<BoundaryTag*>(beginTag))
         *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;
 }
 
index b8fc6fd..96d0e84 100644 (file)
@@ -39,7 +39,7 @@ void SegregatedFreeList::insert(const Range& range)
 {
 IF_DEBUG(
     BeginTag* beginTag = LargeChunk::beginTag(range.begin());
-    BASSERT(beginTag->isInFreeList(range.size()));
+    BASSERT(beginTag->isInFreeList(range));
 )
 
     auto& list = select(range.size());
@@ -66,7 +66,7 @@ Range SegregatedFreeList::takeGreedy(List& list, size_t minimum)
         // We don't eagerly remove items when we merge and/or split ranges,
         // 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;
         }
@@ -114,7 +114,7 @@ INLINE Range SegregatedFreeList::take(List& list, size_t minimum)
         // We don't eagerly remove items when we merge and/or split ranges, 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;
         }
index dbedb76..b3bde56 100644 (file)
@@ -68,6 +68,8 @@ namespace Sizes {
     static const size_t largeChunkMask = ~(largeChunkSize - 1ul);
 
     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;