bmalloc: Refactored SegregatedFreeList and BoundaryTag::init
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 26 Feb 2015 20:05:14 +0000 (20:05 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 26 Feb 2015 20:05:14 +0000 (20:05 +0000)
https://bugs.webkit.org/show_bug.cgi?id=142049

Reviewed by Anders Carlsson.

Split out a FreeList class from SegregatedFreeList. This will make it
easier to add behaviors on free list insertion and removal -- and it's
probably how I should have designed things at the start.

Moved BoundaryTag::init into LargeObject, since all the related logic
lives in LargeObject now too, and this allows us to remove BoundaryTagInlines.h.

* bmalloc.xcodeproj/project.pbxproj:
* bmalloc/BoundaryTagInlines.h: Removed.
* bmalloc/FreeList.cpp: Copied from Source/bmalloc/bmalloc/SegregatedFreeList.cpp.
(bmalloc::FreeList::takeGreedy):
(bmalloc::FreeList::take):
(bmalloc::SegregatedFreeList::SegregatedFreeList): Deleted.
(bmalloc::SegregatedFreeList::insert): Deleted.
(bmalloc::SegregatedFreeList::takeGreedy): Deleted.
(bmalloc::SegregatedFreeList::take): Deleted.
* bmalloc/FreeList.h: Copied from Source/bmalloc/bmalloc/SegregatedFreeList.h.
(bmalloc::FreeList::push):
* bmalloc/LargeObject.h:
(bmalloc::LargeObject::init):
* bmalloc/SegregatedFreeList.cpp:
(bmalloc::SegregatedFreeList::SegregatedFreeList):
(bmalloc::SegregatedFreeList::insert):
(bmalloc::SegregatedFreeList::takeGreedy):
(bmalloc::SegregatedFreeList::take):
* bmalloc/SegregatedFreeList.h:
* bmalloc/Sizes.h:
* bmalloc/VMHeap.cpp:
(bmalloc::VMHeap::grow):

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

Source/bmalloc/ChangeLog
Source/bmalloc/bmalloc.xcodeproj/project.pbxproj
Source/bmalloc/bmalloc/FreeList.cpp [new file with mode: 0644]
Source/bmalloc/bmalloc/FreeList.h [moved from Source/bmalloc/bmalloc/BoundaryTagInlines.h with 56% similarity]
Source/bmalloc/bmalloc/LargeObject.h
Source/bmalloc/bmalloc/SegregatedFreeList.cpp
Source/bmalloc/bmalloc/SegregatedFreeList.h
Source/bmalloc/bmalloc/Sizes.h
Source/bmalloc/bmalloc/VMHeap.cpp

index 1c75721..4a5be19 100644 (file)
@@ -1,5 +1,42 @@
 2015-02-26  Geoffrey Garen  <ggaren@apple.com>
 
+        bmalloc: Refactored SegregatedFreeList and BoundaryTag::init
+        https://bugs.webkit.org/show_bug.cgi?id=142049
+
+        Reviewed by Anders Carlsson.
+
+        Split out a FreeList class from SegregatedFreeList. This will make it
+        easier to add behaviors on free list insertion and removal -- and it's
+        probably how I should have designed things at the start.
+
+        Moved BoundaryTag::init into LargeObject, since all the related logic
+        lives in LargeObject now too, and this allows us to remove BoundaryTagInlines.h.
+
+        * bmalloc.xcodeproj/project.pbxproj:
+        * bmalloc/BoundaryTagInlines.h: Removed.
+        * bmalloc/FreeList.cpp: Copied from Source/bmalloc/bmalloc/SegregatedFreeList.cpp.
+        (bmalloc::FreeList::takeGreedy):
+        (bmalloc::FreeList::take):
+        (bmalloc::SegregatedFreeList::SegregatedFreeList): Deleted.
+        (bmalloc::SegregatedFreeList::insert): Deleted.
+        (bmalloc::SegregatedFreeList::takeGreedy): Deleted.
+        (bmalloc::SegregatedFreeList::take): Deleted.
+        * bmalloc/FreeList.h: Copied from Source/bmalloc/bmalloc/SegregatedFreeList.h.
+        (bmalloc::FreeList::push):
+        * bmalloc/LargeObject.h:
+        (bmalloc::LargeObject::init):
+        * bmalloc/SegregatedFreeList.cpp:
+        (bmalloc::SegregatedFreeList::SegregatedFreeList):
+        (bmalloc::SegregatedFreeList::insert):
+        (bmalloc::SegregatedFreeList::takeGreedy):
+        (bmalloc::SegregatedFreeList::take):
+        * bmalloc/SegregatedFreeList.h:
+        * bmalloc/Sizes.h:
+        * bmalloc/VMHeap.cpp:
+        (bmalloc::VMHeap::grow):
+
+2015-02-26  Geoffrey Garen  <ggaren@apple.com>
+
         bmalloc: free up a bit in BoundaryTag
         https://bugs.webkit.org/show_bug.cgi?id=142048
 
index f2c61c2..8dbeba9 100644 (file)
@@ -9,12 +9,13 @@
 /* Begin PBXBuildFile section */
                1400274918F89C1300115C97 /* Heap.h in Headers */ = {isa = PBXBuildFile; fileRef = 14DA320C18875B09007269E0 /* Heap.h */; settings = {ATTRIBUTES = (Private, ); }; };
                1400274A18F89C2300115C97 /* VMHeap.h in Headers */ = {isa = PBXBuildFile; fileRef = 144F7BFC18BFC517003537F3 /* VMHeap.h */; settings = {ATTRIBUTES = (Private, ); }; };
-               1400274B18F89C3D00115C97 /* BoundaryTagInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 14105E7B18DBD7AF003A106E /* BoundaryTagInlines.h */; settings = {ATTRIBUTES = (Private, ); }; };
                1400274C18F89C3D00115C97 /* SegregatedFreeList.h in Headers */ = {isa = PBXBuildFile; fileRef = 146BEE1E18C841C50002D5A2 /* SegregatedFreeList.h */; settings = {ATTRIBUTES = (Private, ); }; };
                140FA00319CE429C00FFD3C8 /* BumpRange.h in Headers */ = {isa = PBXBuildFile; fileRef = 140FA00219CE429C00FFD3C8 /* BumpRange.h */; settings = {ATTRIBUTES = (Private, ); }; };
                140FA00519CE4B6800FFD3C8 /* LineMetadata.h in Headers */ = {isa = PBXBuildFile; fileRef = 140FA00419CE4B6800FFD3C8 /* LineMetadata.h */; settings = {ATTRIBUTES = (Private, ); }; };
                143CB81C19022BC900B16A45 /* StaticMutex.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 143CB81A19022BC900B16A45 /* StaticMutex.cpp */; };
                143CB81D19022BC900B16A45 /* StaticMutex.h in Headers */ = {isa = PBXBuildFile; fileRef = 143CB81B19022BC900B16A45 /* StaticMutex.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               143EF9AF1A9FABF6004F5C77 /* FreeList.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 143EF9AD1A9FABF6004F5C77 /* FreeList.cpp */; };
+               143EF9B01A9FABF6004F5C77 /* FreeList.h in Headers */ = {isa = PBXBuildFile; fileRef = 143EF9AE1A9FABF6004F5C77 /* FreeList.h */; };
                1440AFC91A95142400837FAA /* SuperChunk.h in Headers */ = {isa = PBXBuildFile; fileRef = 1440AFC81A95142400837FAA /* SuperChunk.h */; settings = {ATTRIBUTES = (Private, ); }; };
                1440AFCB1A95261100837FAA /* Zone.h in Headers */ = {isa = PBXBuildFile; fileRef = 1440AFCA1A95261100837FAA /* Zone.h */; settings = {ATTRIBUTES = (Private, ); }; };
                1440AFCD1A9527AF00837FAA /* Zone.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 1440AFCC1A9527AF00837FAA /* Zone.cpp */; };
@@ -80,7 +81,6 @@
 /* Begin PBXFileReference section */
                140FA00219CE429C00FFD3C8 /* BumpRange.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = BumpRange.h; path = bmalloc/BumpRange.h; sourceTree = "<group>"; };
                140FA00419CE4B6800FFD3C8 /* LineMetadata.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = LineMetadata.h; path = bmalloc/LineMetadata.h; sourceTree = "<group>"; };
-               14105E7B18DBD7AF003A106E /* BoundaryTagInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = BoundaryTagInlines.h; path = bmalloc/BoundaryTagInlines.h; sourceTree = "<group>"; };
                14105E8318E14374003A106E /* ObjectType.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = ObjectType.cpp; path = bmalloc/ObjectType.cpp; sourceTree = "<group>"; };
                1413E460189DCE1E00546D68 /* Inline.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Inline.h; path = bmalloc/Inline.h; sourceTree = "<group>"; };
                1413E462189DE1CD00546D68 /* BumpAllocator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; lineEnding = 0; name = BumpAllocator.h; path = bmalloc/BumpAllocator.h; sourceTree = "<group>"; };
@@ -94,6 +94,8 @@
                143CB81B19022BC900B16A45 /* StaticMutex.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = StaticMutex.h; path = bmalloc/StaticMutex.h; sourceTree = "<group>"; };
                143E29E918CAE8BE00FE8A0F /* MediumPage.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = MediumPage.h; path = bmalloc/MediumPage.h; sourceTree = "<group>"; };
                143E29ED18CAE90500FE8A0F /* SmallPage.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = SmallPage.h; path = bmalloc/SmallPage.h; sourceTree = "<group>"; };
+               143EF9AD1A9FABF6004F5C77 /* FreeList.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = FreeList.cpp; path = bmalloc/FreeList.cpp; sourceTree = "<group>"; };
+               143EF9AE1A9FABF6004F5C77 /* FreeList.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = FreeList.h; path = bmalloc/FreeList.h; sourceTree = "<group>"; };
                1440AFC81A95142400837FAA /* SuperChunk.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = SuperChunk.h; path = bmalloc/SuperChunk.h; sourceTree = "<group>"; };
                1440AFCA1A95261100837FAA /* Zone.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Zone.h; path = bmalloc/Zone.h; sourceTree = "<group>"; };
                1440AFCC1A9527AF00837FAA /* Zone.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = Zone.cpp; path = bmalloc/Zone.cpp; sourceTree = "<group>"; };
                        children = (
                                1417F64518B54A700076FA3F /* BeginTag.h */,
                                1485655E18A43AF900ED6942 /* BoundaryTag.h */,
-                               14105E7B18DBD7AF003A106E /* BoundaryTagInlines.h */,
                                1417F64618B54A700076FA3F /* EndTag.h */,
+                               143EF9AD1A9FABF6004F5C77 /* FreeList.cpp */,
+                               143EF9AE1A9FABF6004F5C77 /* FreeList.h */,
                                147AAA8818CD17CE002201E4 /* LargeChunk.h */,
                                14C6216E1A9A9A6200E72293 /* LargeObject.h */,
                                146BEE2118C845AE0002D5A2 /* SegregatedFreeList.cpp */,
                                14DD78C718F48D7500950702 /* BAssert.h in Headers */,
                                14DD78D018F48D7500950702 /* VMAllocate.h in Headers */,
                                1440AFC91A95142400837FAA /* SuperChunk.h in Headers */,
+                               143EF9B01A9FABF6004F5C77 /* FreeList.h in Headers */,
                                14DD78CE18F48D7500950702 /* Syscall.h in Headers */,
                                14DD78C618F48D7500950702 /* AsyncTask.h in Headers */,
                                14DD78BA18F48D6B00950702 /* Page.h in Headers */,
                                140FA00319CE429C00FFD3C8 /* BumpRange.h in Headers */,
                                14DD78C518F48D7500950702 /* Algorithm.h in Headers */,
                                14DD78BD18F48D6B00950702 /* SmallPage.h in Headers */,
-                               1400274B18F89C3D00115C97 /* BoundaryTagInlines.h in Headers */,
                                14DD788E18F48CCD00950702 /* BoundaryTag.h in Headers */,
                                14DD78C818F48D7500950702 /* FixedVector.h in Headers */,
                                14DD78B718F48D6B00950702 /* MediumLine.h in Headers */,
                                14F271C618EA3983008C152F /* SegregatedFreeList.cpp in Sources */,
                                14F271C318EA3978008C152F /* Allocator.cpp in Sources */,
                                14895D911A3A319C0006235D /* Environment.cpp in Sources */,
+                               143EF9AF1A9FABF6004F5C77 /* FreeList.cpp in Sources */,
                                14F271C718EA3990008C152F /* Heap.cpp in Sources */,
                                14F271C918EA3990008C152F /* VMHeap.cpp in Sources */,
                                14F271C818EA3990008C152F /* ObjectType.cpp in Sources */,
diff --git a/Source/bmalloc/bmalloc/FreeList.cpp b/Source/bmalloc/bmalloc/FreeList.cpp
new file mode 100644 (file)
index 0000000..bb4f51d
--- /dev/null
@@ -0,0 +1,110 @@
+/*
+ * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "BeginTag.h"
+#include "LargeChunk.h"
+#include "FreeList.h"
+#include "Vector.h"
+
+namespace bmalloc {
+
+LargeObject FreeList::takeGreedy(size_t size)
+{
+    for (size_t i = m_vector.size(); i-- > 0; ) {
+        // 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.
+        LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
+        if (!largeObject.isValidAndFree(m_vector[i].size())) {
+            m_vector.pop(i);
+            continue;
+        }
+
+        if (largeObject.size() < size)
+            continue;
+
+        m_vector.pop(i);
+        return largeObject;
+    }
+
+    return LargeObject();
+}
+
+LargeObject FreeList::take(size_t size)
+{
+    LargeObject first;
+    size_t end = m_vector.size() > freeListSearchDepth ? m_vector.size() - freeListSearchDepth : 0;
+    for (size_t i = m_vector.size(); i-- > end; ) {
+        // 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.
+        LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
+        if (!largeObject.isValidAndFree(m_vector[i].size())) {
+            m_vector.pop(i);
+            continue;
+        }
+
+        if (largeObject.size() < size)
+            continue;
+
+        if (!!first && first.begin() < largeObject.begin())
+            continue;
+
+        first = largeObject;
+    }
+    
+    return first;
+}
+
+LargeObject FreeList::take(size_t alignment, size_t size, size_t unalignedSize)
+{
+    BASSERT(isPowerOfTwo(alignment));
+    size_t alignmentMask = alignment - 1;
+
+    LargeObject first;
+    size_t end = m_vector.size() > freeListSearchDepth ? m_vector.size() - freeListSearchDepth : 0;
+    for (size_t i = m_vector.size(); i-- > end; ) {
+        // 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.
+        LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
+        if (!largeObject.isValidAndFree(m_vector[i].size())) {
+            m_vector.pop(i);
+            continue;
+        }
+
+        if (largeObject.size() < size)
+            continue;
+
+        if (test(largeObject.begin(), alignmentMask) && largeObject.size() < unalignedSize)
+            continue;
+
+        if (!!first && first.begin() < largeObject.begin())
+            continue;
+
+        first = largeObject;
+    }
+    
+    return first;
+}
+
+} // namespace bmalloc
similarity index 56%
rename from Source/bmalloc/bmalloc/BoundaryTagInlines.h
rename to Source/bmalloc/bmalloc/FreeList.h
index 5fa516c..2abaebb 100644 (file)
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
  */
 
-#ifndef BoundaryTagInlines_h
-#define BoundaryTagInlines_h
+#ifndef FreeList_h
+#define FreeList_h
 
-#include "Range.h"
-#include "BeginTag.h"
-#include "EndTag.h"
-#include "Inline.h"
-#include "LargeChunk.h"
+#include "LargeObject.h"
+#include "Vector.h"
 
 namespace bmalloc {
 
-inline Range BoundaryTag::init(LargeChunk* chunk)
-{
-    Range range(chunk->begin(), chunk->end() - chunk->begin());
-
-    BeginTag* beginTag = LargeChunk::beginTag(range.begin());
-    beginTag->setRange(range);
-    beginTag->setFree(true);
-    beginTag->setHasPhysicalPages(false);
+// Helper object for SegregatedFreeList.
 
-    EndTag* endTag = LargeChunk::endTag(range.begin(), range.size());
-    endTag->init(beginTag);
+class FreeList {
+public:
+    void push(const LargeObject&);
 
-    // Mark the left and right edges of our chunk as allocated. This naturally
-    // prevents merging logic from overflowing beyond our chunk, without requiring
-    // special-case checks.
+    LargeObject take(size_t);
+    LargeObject take(size_t alignment, size_t, size_t unalignedSize);
+    LargeObject takeGreedy(size_t);
     
-    EndTag* leftSentinel = beginTag->prev();
-    BASSERT(leftSentinel >= static_cast<void*>(chunk));
-    leftSentinel->initSentinel();
+private:
+    Vector<Range> m_vector;
+};
 
-    BeginTag* rightSentinel = endTag->next();
-    BASSERT(rightSentinel < static_cast<void*>(range.begin()));
-    rightSentinel->initSentinel();
-    
-    return range;
+inline void FreeList::push(const LargeObject& largeObject)
+{
+    BASSERT(largeObject.isFree());
+    m_vector.push(largeObject.range());
 }
 
 } // namespace bmalloc
 
-#endif // BoundaryTagInlines_h
+#endif // FreeList_h
index f4cc963..c63cc47 100644 (file)
 #include "BeginTag.h"
 #include "EndTag.h"
 #include "LargeChunk.h"
+#include "Range.h"
 
 namespace bmalloc {
 
 class LargeObject {
 public:
+    static Range init(LargeChunk*);
+
     LargeObject();
     LargeObject(void*);
 
@@ -237,6 +240,33 @@ inline void LargeObject::validate() const
     }
 }
 
+inline Range LargeObject::init(LargeChunk* chunk)
+{
+    Range range(chunk->begin(), chunk->end() - chunk->begin());
+
+    BeginTag* beginTag = LargeChunk::beginTag(range.begin());
+    beginTag->setRange(range);
+    beginTag->setFree(true);
+    beginTag->setHasPhysicalPages(false);
+
+    EndTag* endTag = LargeChunk::endTag(range.begin(), range.size());
+    endTag->init(beginTag);
+
+    // Mark the left and right edges of our chunk as allocated. This naturally
+    // prevents merging logic from overflowing beyond our chunk, without requiring
+    // special-case checks.
+    
+    EndTag* leftSentinel = beginTag->prev();
+    BASSERT(leftSentinel >= static_cast<void*>(chunk));
+    leftSentinel->initSentinel();
+
+    BeginTag* rightSentinel = endTag->next();
+    BASSERT(rightSentinel < static_cast<void*>(range.begin()));
+    rightSentinel->initSentinel();
+    
+    return range;
+}
+
 } // namespace bmalloc
 
 #endif // LargeObject_h
index acdedcf..a7ba983 100644 (file)
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
  */
 
-#include "BeginTag.h"
-#include "LargeChunk.h"
 #include "SegregatedFreeList.h"
-#include "Vector.h"
 
 namespace bmalloc {
 
 SegregatedFreeList::SegregatedFreeList()
 {
-    BASSERT(static_cast<size_t>(&select(largeMax) - m_lists.begin()) == m_lists.size() - 1);
+    BASSERT(static_cast<size_t>(&select(largeMax) - m_freeLists.begin()) == m_freeLists.size() - 1);
 }
 
 void SegregatedFreeList::insert(const LargeObject& largeObject)
 {
-    BASSERT(largeObject.isFree());
     auto& list = select(largeObject.size());
-    list.push(largeObject.range());
+    list.push(largeObject);
 }
 
 LargeObject SegregatedFreeList::takeGreedy(size_t size)
 {
-    for (size_t i = m_lists.size(); i-- > 0; ) {
-        LargeObject largeObject = takeGreedy(m_lists[i], size);
+    for (size_t i = m_freeLists.size(); i-- > 0; ) {
+        LargeObject largeObject = m_freeLists[i].takeGreedy(size);
         if (!largeObject)
             continue;
 
@@ -54,31 +50,10 @@ LargeObject SegregatedFreeList::takeGreedy(size_t size)
     return LargeObject();
 }
 
-LargeObject SegregatedFreeList::takeGreedy(List& list, size_t size)
-{
-    for (size_t i = list.size(); i-- > 0; ) {
-        // 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.
-        LargeObject largeObject(LargeObject::DoNotValidate, list[i].begin());
-        if (!largeObject.isValidAndFree(list[i].size())) {
-            list.pop(i);
-            continue;
-        }
-
-        if (largeObject.size() < size)
-            continue;
-
-        list.pop(i);
-        return largeObject;
-    }
-
-    return LargeObject();
-}
-
 LargeObject SegregatedFreeList::take(size_t size)
 {
-    for (auto* list = &select(size); list != m_lists.end(); ++list) {
-        LargeObject largeObject = take(*list, size);
+    for (auto* list = &select(size); list != m_freeLists.end(); ++list) {
+        LargeObject largeObject = list->take(size);
         if (!largeObject)
             continue;
 
@@ -89,8 +64,8 @@ LargeObject SegregatedFreeList::take(size_t size)
 
 LargeObject SegregatedFreeList::take(size_t alignment, size_t size, size_t unalignedSize)
 {
-    for (auto* list = &select(size); list != m_lists.end(); ++list) {
-        LargeObject largeObject = take(*list, alignment, size, unalignedSize);
+    for (auto* list = &select(size); list != m_freeLists.end(); ++list) {
+        LargeObject largeObject = list->take(alignment, size, unalignedSize);
         if (!largeObject)
             continue;
 
@@ -99,7 +74,7 @@ LargeObject SegregatedFreeList::take(size_t alignment, size_t size, size_t unali
     return LargeObject();
 }
 
-INLINE auto SegregatedFreeList::select(size_t size) -> List&
+INLINE auto SegregatedFreeList::select(size_t size) -> FreeList&
 {
     size_t alignCount = (size - largeMin) / largeAlignment;
     size_t result = 0;
@@ -107,63 +82,7 @@ INLINE auto SegregatedFreeList::select(size_t size) -> List&
         ++result;
         alignCount >>= 1;
     }
-    return m_lists[result];
-}
-
-INLINE LargeObject SegregatedFreeList::take(List& list, size_t size)
-{
-    LargeObject first;
-    size_t end = list.size() > segregatedFreeListSearchDepth ? list.size() - segregatedFreeListSearchDepth : 0;
-    for (size_t i = list.size(); i-- > end; ) {
-        // 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.
-        LargeObject largeObject(LargeObject::DoNotValidate, list[i].begin());
-        if (!largeObject.isValidAndFree(list[i].size())) {
-            list.pop(i);
-            continue;
-        }
-
-        if (largeObject.size() < size)
-            continue;
-
-        if (!!first && first.begin() < largeObject.begin())
-            continue;
-
-        first = largeObject;
-    }
-    
-    return first;
-}
-
-INLINE LargeObject SegregatedFreeList::take(List& list, size_t alignment, size_t size, size_t unalignedSize)
-{
-    BASSERT(isPowerOfTwo(alignment));
-    size_t alignmentMask = alignment - 1;
-
-    LargeObject first;
-    size_t end = list.size() > segregatedFreeListSearchDepth ? list.size() - segregatedFreeListSearchDepth : 0;
-    for (size_t i = list.size(); i-- > end; ) {
-        // 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.
-        LargeObject largeObject(LargeObject::DoNotValidate, list[i].begin());
-        if (!largeObject.isValidAndFree(list[i].size())) {
-            list.pop(i);
-            continue;
-        }
-
-        if (largeObject.size() < size)
-            continue;
-
-        if (test(largeObject.begin(), alignmentMask) && largeObject.size() < unalignedSize)
-            continue;
-
-        if (!!first && first.begin() < largeObject.begin())
-            continue;
-
-        first = largeObject;
-    }
-    
-    return first;
+    return m_freeLists[result];
 }
 
 } // namespace bmalloc
index e3026e8..752981a 100644 (file)
@@ -26,8 +26,7 @@
 #ifndef SegregatedFreeList_h
 #define SegregatedFreeList_h
 
-#include "LargeObject.h"
-#include "Vector.h"
+#include "FreeList.h"
 #include <array>
 
 namespace bmalloc {
@@ -58,14 +57,9 @@ public:
     LargeObject takeGreedy(size_t);
     
 private:
-    typedef Vector<Range> List;
+    FreeList& select(size_t);
 
-    List& select(size_t);
-    LargeObject take(List&, size_t);
-    LargeObject take(List&, size_t alignment, size_t, size_t unalignedSize);
-    LargeObject takeGreedy(List&, size_t);
-
-    std::array<List, 19> m_lists;
+    std::array<FreeList, 19> m_freeLists;
 };
 
 } // namespace bmalloc
index fadca77..651d076 100644 (file)
@@ -81,7 +81,7 @@ namespace Sizes {
     
     static const size_t xLargeAlignment = vmPageSize;
 
-    static const size_t segregatedFreeListSearchDepth = 16;
+    static const size_t freeListSearchDepth = 16;
 
     static const uintptr_t typeMask = (superChunkSize - 1) & ~((superChunkSize / 4) - 1); // 4 taggable chunks
     static const uintptr_t smallType = (superChunkSize + smallChunkOffset) & typeMask;
index 75de659..2d5136d 100644 (file)
@@ -23,8 +23,7 @@
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
  */
 
-#include "BoundaryTagInlines.h"
-#include "LargeChunk.h"
+#include "LargeObject.h"
 #include "Line.h"
 #include "PerProcess.h"
 #include "SuperChunk.h"
@@ -53,7 +52,7 @@ void VMHeap::grow()
         m_mediumPages.push(it);
 
     LargeChunk* largeChunk = superChunk->largeChunk();
-    m_largeObjects.insert(LargeObject(BoundaryTag::init(largeChunk).begin()));
+    m_largeObjects.insert(LargeObject(LargeObject::init(largeChunk).begin()));
 }
 
 } // namespace bmalloc