bmalloc: Allocation should be more precise
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 23 Sep 2014 18:24:02 +0000 (18:24 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 23 Sep 2014 18:24:02 +0000 (18:24 +0000)
https://bugs.webkit.org/show_bug.cgi?id=136993

Reviewed by Gavin Barraclough.

13% reduction in heap size on the MallocBench *_memory_warning benchmarks.

This patch teaches the allocator to merge adjacent free lines into a
single allocatable range. This allows us to shrink the size of an
individual line without increasing fragmentation or the rate of allocator
slow paths.

We'll only take more slow paths when available memory is sparse, which
is exactly when it's worth it. When available memory is dense, we'll
take fewer slow paths.

* bmalloc.xcodeproj/project.pbxproj:
* bmalloc/Algorithm.h:
(bmalloc::divideRoundingUp):

* bmalloc/Allocator.cpp:
(bmalloc::Allocator::Allocator): Updated for interface changes.

(bmalloc::Allocator::scavenge): Scavenge by object instead of by line.
Now that we merge lines, it's not convenient to scavenge by line.

(bmalloc::Allocator::allocateSmallBumpRange):
(bmalloc::Allocator::allocateMediumBumpRange): Allocate whole ranges
instead of individual lines.

(bmalloc::Allocator::allocateSlowCase):
(bmalloc::Allocator::allocateSmallLine): Deleted.
(bmalloc::Allocator::allocateMediumLine): Deleted.
(bmalloc::Allocator::allocateMedium): Deleted.
* bmalloc/Allocator.h:
(bmalloc::Allocator::allocateFastCase): Folded medium allocations
into the standard fast path with small allocations. Since a BumpAllocator
just allocates out of an arbitrary range, it doesn't need to distinguish
between small and medium lines.

* bmalloc/BumpAllocator.h:
(bmalloc::BumpAllocator::size):
(bmalloc::BumpAllocator::BumpAllocator):
(bmalloc::BumpAllocator::init):
(bmalloc::BumpAllocator::refill):
(bmalloc::BumpAllocator::line): Deleted. No need to track line information
anymore: the heap just gives us a pointer and a pre-computed number of
objects, and we allocate them.

* bmalloc/Deallocator.cpp:
(bmalloc::Deallocator::processObjectLog): Updated for interface changes.

* bmalloc/Heap.cpp:
(bmalloc::Heap::Heap):
(bmalloc::Heap::initializeLineMetadata): Pre-compute precise metadata
detailing where all objects will lie in memory. After we merge two lines,
we might allocate an object that spans from one line to the next. This
metadata details which bits of memory overlap in that way, and how they
overlap.

(bmalloc::Heap::refillSmallBumpRangeCache):
(bmalloc::Heap::refillMediumBumpRangeCache): Scan a whole page at a time,
and merge adjacent free lines into BumpRanges.

(bmalloc::Heap::allocateSmallPage):
(bmalloc::Heap::allocateMediumPage):
(bmalloc::Heap::deallocateSmallLine):
(bmalloc::Heap::deallocateMediumLine): Track pages rather than lines,
since we scan for free memory a page at a time.

(bmalloc::Heap::allocateSmallLineSlowCase): Deleted.
(bmalloc::Heap::allocateMediumLineSlowCase): Deleted. Folded into the
fast path.

* bmalloc/Heap.h:
(bmalloc::Heap::derefSmallLine):
(bmalloc::Heap::derefMediumLine):
(bmalloc::Heap::deallocateSmallLine): Deleted.
(bmalloc::Heap::allocateSmallLine): Deleted.
(bmalloc::Heap::deallocateMediumLine): Deleted.
(bmalloc::Heap::allocateMediumLine): Deleted. Updated for interface changes.

* bmalloc/Line.h:
(bmalloc::Line<Traits>::ref):
(bmalloc::Line<Traits>::deref):
(bmalloc::Line<Traits>::concurrentRef): Deleted. We don't pass a derefCount
anymore, since we only ever deref by 1 now.

* bmalloc/MediumAllocator.h:
(bmalloc::MediumAllocator::isNull): Deleted.
(bmalloc::MediumAllocator::MediumAllocator): Deleted.
(bmalloc::MediumAllocator::line): Deleted.
(bmalloc::MediumAllocator::allocate): Deleted.
(bmalloc::MediumAllocator::derefCount): Deleted.
(bmalloc::MediumAllocator::refill): Deleted.
(bmalloc::MediumAllocator::clear): Deleted. Deleted some code that's
been dead for a while, since it doesn't build anymore with this patch.

* bmalloc/Page.h:
(bmalloc::Page::sizeClass):
(bmalloc::Page::setSizeClass):
(bmalloc::Page::smallSizeClass): Deleted.
(bmalloc::Page::setSmallSizeClass): Deleted. Renamed setSmallSizeClass
to sizeClass, since we use it for medium sizes too.

* bmalloc/Sizes.h:
(bmalloc::Sizes::sizeClass):
(bmalloc::Sizes::objectSize): Shrank line sizes to save memory.

(bmalloc::Sizes::smallSizeClassFor): Deleted.
(bmalloc::Sizes::mediumSizeClassFor): Deleted.

* bmalloc/bmalloc.h:
(bmalloc::api::realloc): Now that we have precise objects sizes, realloc
can be a bit more precise. It also has to be, since we can't guarantee
that an object ends at the end of a line anymore.

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

16 files changed:
Source/bmalloc/ChangeLog
Source/bmalloc/bmalloc.xcodeproj/project.pbxproj
Source/bmalloc/bmalloc/Algorithm.h
Source/bmalloc/bmalloc/Allocator.cpp
Source/bmalloc/bmalloc/Allocator.h
Source/bmalloc/bmalloc/BumpAllocator.h
Source/bmalloc/bmalloc/BumpRange.h [new file with mode: 0644]
Source/bmalloc/bmalloc/Deallocator.cpp
Source/bmalloc/bmalloc/Heap.cpp
Source/bmalloc/bmalloc/Heap.h
Source/bmalloc/bmalloc/Line.h
Source/bmalloc/bmalloc/LineMetadata.h [new file with mode: 0644]
Source/bmalloc/bmalloc/MediumAllocator.h [deleted file]
Source/bmalloc/bmalloc/Page.h
Source/bmalloc/bmalloc/Sizes.h
Source/bmalloc/bmalloc/bmalloc.h

index f304c80..701ebaa 100644 (file)
@@ -1,3 +1,122 @@
+2014-09-23  Geoffrey Garen  <ggaren@apple.com>
+
+        bmalloc: Allocation should be more precise
+        https://bugs.webkit.org/show_bug.cgi?id=136993
+
+        Reviewed by Gavin Barraclough.
+
+        13% reduction in heap size on the MallocBench *_memory_warning benchmarks.
+
+        This patch teaches the allocator to merge adjacent free lines into a
+        single allocatable range. This allows us to shrink the size of an
+        individual line without increasing fragmentation or the rate of allocator
+        slow paths.
+
+        We'll only take more slow paths when available memory is sparse, which
+        is exactly when it's worth it. When available memory is dense, we'll
+        take fewer slow paths.
+
+        * bmalloc.xcodeproj/project.pbxproj:
+        * bmalloc/Algorithm.h:
+        (bmalloc::divideRoundingUp):
+
+        * bmalloc/Allocator.cpp:
+        (bmalloc::Allocator::Allocator): Updated for interface changes.
+
+        (bmalloc::Allocator::scavenge): Scavenge by object instead of by line.
+        Now that we merge lines, it's not convenient to scavenge by line.
+
+        (bmalloc::Allocator::allocateSmallBumpRange):
+        (bmalloc::Allocator::allocateMediumBumpRange): Allocate whole ranges
+        instead of individual lines.
+
+        (bmalloc::Allocator::allocateSlowCase):
+        (bmalloc::Allocator::allocateSmallLine): Deleted.
+        (bmalloc::Allocator::allocateMediumLine): Deleted.
+        (bmalloc::Allocator::allocateMedium): Deleted.
+        * bmalloc/Allocator.h:
+        (bmalloc::Allocator::allocateFastCase): Folded medium allocations
+        into the standard fast path with small allocations. Since a BumpAllocator
+        just allocates out of an arbitrary range, it doesn't need to distinguish
+        between small and medium lines.
+
+        * bmalloc/BumpAllocator.h:
+        (bmalloc::BumpAllocator::size):
+        (bmalloc::BumpAllocator::BumpAllocator):
+        (bmalloc::BumpAllocator::init):
+        (bmalloc::BumpAllocator::refill):
+        (bmalloc::BumpAllocator::line): Deleted. No need to track line information
+        anymore: the heap just gives us a pointer and a pre-computed number of
+        objects, and we allocate them.
+
+        * bmalloc/Deallocator.cpp:
+        (bmalloc::Deallocator::processObjectLog): Updated for interface changes.
+
+        * bmalloc/Heap.cpp:
+        (bmalloc::Heap::Heap):
+        (bmalloc::Heap::initializeLineMetadata): Pre-compute precise metadata
+        detailing where all objects will lie in memory. After we merge two lines,
+        we might allocate an object that spans from one line to the next. This
+        metadata details which bits of memory overlap in that way, and how they
+        overlap.
+
+        (bmalloc::Heap::refillSmallBumpRangeCache):
+        (bmalloc::Heap::refillMediumBumpRangeCache): Scan a whole page at a time,
+        and merge adjacent free lines into BumpRanges.
+
+        (bmalloc::Heap::allocateSmallPage):
+        (bmalloc::Heap::allocateMediumPage):
+        (bmalloc::Heap::deallocateSmallLine):
+        (bmalloc::Heap::deallocateMediumLine): Track pages rather than lines,
+        since we scan for free memory a page at a time.
+
+        (bmalloc::Heap::allocateSmallLineSlowCase): Deleted.
+        (bmalloc::Heap::allocateMediumLineSlowCase): Deleted. Folded into the
+        fast path.
+
+        * bmalloc/Heap.h:
+        (bmalloc::Heap::derefSmallLine):
+        (bmalloc::Heap::derefMediumLine):
+        (bmalloc::Heap::deallocateSmallLine): Deleted.
+        (bmalloc::Heap::allocateSmallLine): Deleted.
+        (bmalloc::Heap::deallocateMediumLine): Deleted.
+        (bmalloc::Heap::allocateMediumLine): Deleted. Updated for interface changes.
+
+        * bmalloc/Line.h:
+        (bmalloc::Line<Traits>::ref):
+        (bmalloc::Line<Traits>::deref):
+        (bmalloc::Line<Traits>::concurrentRef): Deleted. We don't pass a derefCount
+        anymore, since we only ever deref by 1 now.
+
+        * bmalloc/MediumAllocator.h:
+        (bmalloc::MediumAllocator::isNull): Deleted.
+        (bmalloc::MediumAllocator::MediumAllocator): Deleted.
+        (bmalloc::MediumAllocator::line): Deleted.
+        (bmalloc::MediumAllocator::allocate): Deleted.
+        (bmalloc::MediumAllocator::derefCount): Deleted.
+        (bmalloc::MediumAllocator::refill): Deleted.
+        (bmalloc::MediumAllocator::clear): Deleted. Deleted some code that's
+        been dead for a while, since it doesn't build anymore with this patch.
+
+        * bmalloc/Page.h:
+        (bmalloc::Page::sizeClass):
+        (bmalloc::Page::setSizeClass):
+        (bmalloc::Page::smallSizeClass): Deleted.
+        (bmalloc::Page::setSmallSizeClass): Deleted. Renamed setSmallSizeClass
+        to sizeClass, since we use it for medium sizes too.
+
+        * bmalloc/Sizes.h:
+        (bmalloc::Sizes::sizeClass):
+        (bmalloc::Sizes::objectSize): Shrank line sizes to save memory.
+
+        (bmalloc::Sizes::smallSizeClassFor): Deleted.
+        (bmalloc::Sizes::mediumSizeClassFor): Deleted.
+
+        * bmalloc/bmalloc.h:
+        (bmalloc::api::realloc): Now that we have precise objects sizes, realloc
+        can be a bit more precise. It also has to be, since we can't guarantee
+        that an object ends at the end of a line anymore.
+
 2014-09-19  Daniel Bates  <dabates@apple.com>
 
         Always assume internal SDK when building configuration Production
index 0c9485f..58176da 100644 (file)
@@ -11,6 +11,8 @@
                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, ); }; };
                1448C30018F3754600502839 /* mbmalloc.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 1448C2FF18F3754300502839 /* mbmalloc.cpp */; };
@@ -26,7 +28,6 @@
                14DD789818F48D4A00950702 /* Allocator.h in Headers */ = {isa = PBXBuildFile; fileRef = 145F6856179DC8CA00D65598 /* Allocator.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14DD789918F48D4A00950702 /* Cache.h in Headers */ = {isa = PBXBuildFile; fileRef = 144469E517A46BFE00F9EA1D /* Cache.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14DD789A18F48D4A00950702 /* Deallocator.h in Headers */ = {isa = PBXBuildFile; fileRef = 145F685A179DC90200D65598 /* Deallocator.h */; settings = {ATTRIBUTES = (Private, ); }; };
-               14DD789B18F48D4A00950702 /* MediumAllocator.h in Headers */ = {isa = PBXBuildFile; fileRef = 1413E47018A0661700546D68 /* MediumAllocator.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14DD789C18F48D4A00950702 /* BumpAllocator.h in Headers */ = {isa = PBXBuildFile; fileRef = 1413E462189DE1CD00546D68 /* BumpAllocator.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14DD78B418F48D6B00950702 /* Chunk.h in Headers */ = {isa = PBXBuildFile; fileRef = 147AAA9418CE5CA6002201E4 /* Chunk.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14DD78B518F48D6B00950702 /* Line.h in Headers */ = {isa = PBXBuildFile; fileRef = 14DA32071885F9E6007269E0 /* Line.h */; settings = {ATTRIBUTES = (Private, ); }; };
 /* End PBXContainerItemProxy section */
 
 /* 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>"; };
                1413E468189EEDE400546D68 /* BAssert.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = BAssert.h; path = bmalloc/BAssert.h; sourceTree = "<group>"; };
-               1413E47018A0661700546D68 /* MediumAllocator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = MediumAllocator.h; path = bmalloc/MediumAllocator.h; sourceTree = "<group>"; };
                1417F64518B54A700076FA3F /* BeginTag.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = BeginTag.h; path = bmalloc/BeginTag.h; sourceTree = "<group>"; };
                1417F64618B54A700076FA3F /* EndTag.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = EndTag.h; path = bmalloc/EndTag.h; sourceTree = "<group>"; };
                1417F64F18B7280C0076FA3F /* Syscall.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Syscall.h; path = bmalloc/Syscall.h; sourceTree = "<group>"; };
                                144469E517A46BFE00F9EA1D /* Cache.h */,
                                145F6859179DC90200D65598 /* Deallocator.cpp */,
                                145F685A179DC90200D65598 /* Deallocator.h */,
-                               1413E47018A0661700546D68 /* MediumAllocator.h */,
                                1413E462189DE1CD00546D68 /* BumpAllocator.h */,
                        );
                        name = cache;
                14D9DB4E17F2866E00EAAB79 /* heap */ = {
                        isa = PBXGroup;
                        children = (
+                               140FA00219CE429C00FFD3C8 /* BumpRange.h */,
                                14DA320E18875D9F007269E0 /* Heap.cpp */,
                                14DA320C18875B09007269E0 /* Heap.h */,
+                               140FA00419CE4B6800FFD3C8 /* LineMetadata.h */,
                                14105E8318E14374003A106E /* ObjectType.cpp */,
                                1485656018A43DBA00ED6942 /* ObjectType.h */,
                                145F6874179DF84100D65598 /* Sizes.h */,
                                14C919C918FCC59F0028DB43 /* BPlatform.h in Headers */,
                                14DD788C18F48CAE00950702 /* LargeChunk.h in Headers */,
                                14DD789218F48CFC00950702 /* EndTag.h in Headers */,
+                               140FA00519CE4B6800FFD3C8 /* LineMetadata.h in Headers */,
                                14DD78CC18F48D7500950702 /* PerThread.h in Headers */,
                                14DD78B418F48D6B00950702 /* Chunk.h in Headers */,
                                14DD78CA18F48D7500950702 /* Mutex.h in Headers */,
                                14DD78CD18F48D7500950702 /* Range.h in Headers */,
                                14DD789C18F48D4A00950702 /* BumpAllocator.h in Headers */,
                                14DD789918F48D4A00950702 /* Cache.h in Headers */,
-                               14DD789B18F48D4A00950702 /* MediumAllocator.h in Headers */,
                                14DD78BE18F48D6B00950702 /* SmallTraits.h in Headers */,
                                14DD789018F48CEB00950702 /* Sizes.h in Headers */,
                                14DD78C718F48D7500950702 /* BAssert.h in Headers */,
                                1400274A18F89C2300115C97 /* VMHeap.h in Headers */,
                                1400274918F89C1300115C97 /* Heap.h in Headers */,
                                14DD78B818F48D6B00950702 /* MediumPage.h in Headers */,
+                               140FA00319CE429C00FFD3C8 /* BumpRange.h in Headers */,
                                14DD78C518F48D7500950702 /* Algorithm.h in Headers */,
                                14DD78BD18F48D6B00950702 /* SmallPage.h in Headers */,
                                1400274B18F89C3D00115C97 /* BoundaryTagInlines.h in Headers */,
index 2316a85..c6b3912 100644 (file)
@@ -74,6 +74,15 @@ template<size_t divisor, typename T> inline constexpr T roundDownToMultipleOf(T
     return reinterpret_cast<T>(mask(reinterpret_cast<uintptr_t>(x), ~(divisor - 1ul)));
 }
 
+template<typename T> void divideRoundingUp(T numerator, T denominator, T& quotient, T& remainder)
+{
+    // We expect the compiler to emit a single divide instruction to extract both the quotient and the remainder.
+    quotient = numerator / denominator;
+    remainder = numerator % denominator;
+    if (remainder)
+        quotient += 1;
+}
+
 // Version of sizeof that returns 0 for empty classes.
 
 template<typename T> inline constexpr size_t sizeOf()
index 00e33c0..96a6ef7 100644 (file)
@@ -38,11 +38,11 @@ namespace bmalloc {
 Allocator::Allocator(Deallocator& deallocator)
     : m_deallocator(deallocator)
 {
-    for (unsigned short i = alignment; i <= smallMax; i += alignment)
-        m_smallAllocators[smallSizeClassFor(i)].init<SmallLine>(i);
+    for (unsigned short size = alignment; size <= smallMax; size += alignment)
+        m_bumpAllocators[sizeClass(size)].init(size);
 
-    for (unsigned short i = smallMax + alignment; i <= mediumMax; i += alignment)
-        m_mediumAllocators[mediumSizeClassFor(i)].init<MediumLine>(i);
+    for (unsigned short size = smallMax + alignment; size <= mediumMax; size += alignment)
+        m_bumpAllocators[sizeClass(size)].init(size);
 }
 
 Allocator::~Allocator()
@@ -52,54 +52,59 @@ Allocator::~Allocator()
 
 void Allocator::scavenge()
 {
-    for (auto& allocator : m_smallAllocators) {
+    for (unsigned short i = alignment; i <= smallMax; i += alignment) {
+        BumpAllocator& allocator = m_bumpAllocators[sizeClass(i)];
+        SmallBumpRangeCache& bumpRangeCache = m_smallBumpRangeCaches[sizeClass(i)];
+
         while (allocator.canAllocate())
             m_deallocator.deallocate(allocator.allocate());
+
+        while (bumpRangeCache.size()) {
+            allocator.refill(bumpRangeCache.pop());
+            while (allocator.canAllocate())
+                m_deallocator.deallocate(allocator.allocate());
+        }
+
         allocator.clear();
     }
 
-    for (auto& allocator : m_mediumAllocators) {
+    for (unsigned short i = smallMax + alignment; i <= mediumMax; i += alignment) {
+        BumpAllocator& allocator = m_bumpAllocators[sizeClass(i)];
+        MediumBumpRangeCache& bumpRangeCache = m_mediumBumpRangeCaches[sizeClass(i)];
+
         while (allocator.canAllocate())
             m_deallocator.deallocate(allocator.allocate());
-        allocator.clear();
-    }
 
-    std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
-    Heap* heap = PerProcess<Heap>::getFastCase();
-    
-    for (auto& smallLineCache : m_smallLineCaches) {
-        while (smallLineCache.size())
-            heap->deallocateSmallLine(lock, smallLineCache.pop());
+        while (bumpRangeCache.size()) {
+            allocator.refill(bumpRangeCache.pop());
+            while (allocator.canAllocate())
+                m_deallocator.deallocate(allocator.allocate());
+        }
+
+        allocator.clear();
     }
-    while (m_mediumLineCache.size())
-        heap->deallocateMediumLine(lock, m_mediumLineCache.pop());
 }
 
-SmallLine* Allocator::allocateSmallLine(size_t smallSizeClass)
+BumpRange Allocator::allocateSmallBumpRange(size_t sizeClass)
 {
-    SmallLineCache& smallLineCache = m_smallLineCaches[smallSizeClass];
-    if (!smallLineCache.size()) {
+    SmallBumpRangeCache& bumpRangeCache = m_smallBumpRangeCaches[sizeClass];
+    if (!bumpRangeCache.size()) {
         std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
-        Heap* heap = PerProcess<Heap>::getFastCase();
-
-        while (smallLineCache.size() != smallLineCache.capacity())
-            smallLineCache.push(heap->allocateSmallLine(lock, smallSizeClass));
+        PerProcess<Heap>::getFastCase()->refillSmallBumpRangeCache(lock, sizeClass, bumpRangeCache);
     }
 
-    return smallLineCache.pop();
+    return bumpRangeCache.pop();
 }
 
-MediumLine* Allocator::allocateMediumLine()
+BumpRange Allocator::allocateMediumBumpRange(size_t sizeClass)
 {
-    if (!m_mediumLineCache.size()) {
+    MediumBumpRangeCache& bumpRangeCache = m_mediumBumpRangeCaches[sizeClass];
+    if (!bumpRangeCache.size()) {
         std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
-        Heap* heap = PerProcess<Heap>::getFastCase();
-
-        while (m_mediumLineCache.size() != m_mediumLineCache.capacity())
-            m_mediumLineCache.push(heap->allocateMediumLine(lock));
+        PerProcess<Heap>::getFastCase()->refillMediumBumpRangeCache(lock, sizeClass, bumpRangeCache);
     }
 
-    return m_mediumLineCache.pop();
+    return bumpRangeCache.pop();
 }
 
 void* Allocator::allocateLarge(size_t size)
@@ -116,30 +121,27 @@ void* Allocator::allocateXLarge(size_t size)
     return PerProcess<Heap>::getFastCase()->allocateXLarge(lock, size);
 }
 
-void* Allocator::allocateMedium(size_t size)
-{
-    BumpAllocator& allocator = m_mediumAllocators[mediumSizeClassFor(size)];
-
-    if (!allocator.canAllocate())
-        allocator.refill(allocateMediumLine());
-    return allocator.allocate();
-}
-
 void* Allocator::allocateSlowCase(size_t size)
 {
 IF_DEBUG(
     void* dummy;
     BASSERT(!allocateFastCase(size, dummy));
 )
-    if (size <= smallMax) {
-        size_t smallSizeClass = smallSizeClassFor(size);
-        BumpAllocator& allocator = m_smallAllocators[smallSizeClass];
-        allocator.refill(allocateSmallLine(smallSizeClass));
-        return allocator.allocate();
-    }
 
-    if (size <= mediumMax)
-        return allocateMedium(size);
+    if (size <= mediumMax) {
+        size_t sizeClass = bmalloc::sizeClass(size);
+        BumpAllocator& allocator = m_bumpAllocators[sizeClass];
+
+        if (allocator.size() <= smallMax) {
+            allocator.refill(allocateSmallBumpRange(sizeClass));
+            return allocator.allocate();
+        }
+
+        if (allocator.size() <= mediumMax) {
+            allocator.refill(allocateMediumBumpRange(sizeClass));
+            return allocator.allocate();
+        }
+    }
     
     if (size <= largeMax)
         return allocateLarge(size);
index ff23b01..0f807e5 100644 (file)
@@ -28,7 +28,7 @@
 
 #include "BumpAllocator.h"
 #include "FixedVector.h"
-#include "MediumAllocator.h"
+#include "Heap.h"
 #include "Sizes.h"
 #include "SmallLine.h"
 #include <array>
@@ -51,33 +51,29 @@ public:
     void scavenge();
 
 private:
-    typedef FixedVector<SmallLine*, smallLineCacheCapacity> SmallLineCache;
-    typedef FixedVector<MediumLine*, mediumLineCacheCapacity> MediumLineCache;
-
     void* allocateFastCase(BumpAllocator&);
 
     void* allocateMedium(size_t);
     void* allocateLarge(size_t);
     void* allocateXLarge(size_t);
     
-    SmallLine* allocateSmallLine(size_t smallSizeClass);
-    MediumLine* allocateMediumLine();
+    BumpRange allocateSmallBumpRange(size_t sizeClass);
+    BumpRange allocateMediumBumpRange(size_t sizeClass);
     
     Deallocator& m_deallocator;
 
-    std::array<BumpAllocator, smallMax / alignment> m_smallAllocators;
-    std::array<BumpAllocator, mediumMax / alignment> m_mediumAllocators;
+    std::array<BumpAllocator, mediumMax / alignment> m_bumpAllocators;
 
-    std::array<SmallLineCache, smallMax / alignment> m_smallLineCaches;
-    MediumLineCache m_mediumLineCache;
+    std::array<SmallBumpRangeCache, smallMax / alignment> m_smallBumpRangeCaches;
+    std::array<MediumBumpRangeCache, mediumMax / alignment> m_mediumBumpRangeCaches;
 };
 
 inline bool Allocator::allocateFastCase(size_t size, void*& object)
 {
-    if (size > smallMax)
+    if (size > mediumMax)
         return false;
 
-    BumpAllocator& allocator = m_smallAllocators[smallSizeClassFor(size)];
+    BumpAllocator& allocator = m_bumpAllocators[sizeClass(size)];
     if (!allocator.canAllocate())
         return false;
 
index 44d5c96..68f07a5 100644 (file)
@@ -27,6 +27,7 @@
 #define BumpAllocator_h
 
 #include "BAssert.h"
+#include "BumpRange.h"
 #include "ObjectType.h"
 
 namespace bmalloc {
@@ -36,49 +37,38 @@ namespace bmalloc {
 class BumpAllocator {
 public:
     BumpAllocator();
-    template<typename Line> void init(size_t);
+    void init(size_t);
+    
+    size_t size() { return m_size; }
     
     bool isNull() { return !m_ptr; }
-    template<typename Line> Line* line();
+    void clear();
 
     bool canAllocate() { return !!m_remaining; }
     void* allocate();
 
-    template<typename Line> void refill(Line*);
-    void clear();
+    void refill(const BumpRange&);
 
 private:
     void validate(void*);
 
     char* m_ptr;
     unsigned short m_size;
-    unsigned char m_remaining;
-    unsigned char m_maxObjectCount;
+    unsigned short m_remaining;
 };
 
 inline BumpAllocator::BumpAllocator()
     : m_ptr()
     , m_size()
     , m_remaining()
-    , m_maxObjectCount()
 {
 }
 
-template<typename Line>
 inline void BumpAllocator::init(size_t size)
 {
-    BASSERT(size >= Line::minimumObjectSize);
-
     m_ptr = nullptr;
     m_size = size;
     m_remaining = 0;
-    m_maxObjectCount = Line::lineSize / size;
-}
-
-template<typename Line>
-inline Line* BumpAllocator::line()
-{
-    return Line::get(canAllocate() ? m_ptr : m_ptr - 1);
 }
 
 inline void BumpAllocator::validate(void* ptr)
@@ -104,13 +94,11 @@ inline void* BumpAllocator::allocate()
     return result;
 }
 
-template<typename Line>
-inline void BumpAllocator::refill(Line* line)
+inline void BumpAllocator::refill(const BumpRange& bumpRange)
 {
     BASSERT(!canAllocate());
-    line->concurrentRef(m_maxObjectCount);
-    m_ptr = line->begin();
-    m_remaining = m_maxObjectCount;
+    m_ptr = bumpRange.begin;
+    m_remaining = bumpRange.objectCount;
 }
 
 inline void BumpAllocator::clear()
diff --git a/Source/bmalloc/bmalloc/BumpRange.h b/Source/bmalloc/bmalloc/BumpRange.h
new file mode 100644 (file)
index 0000000..a752b40
--- /dev/null
@@ -0,0 +1,45 @@
+/*
+ * Copyright (C) 2014 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. 
+ */
+
+#ifndef BumpRange_h
+#define BumpRange_h
+
+#include "FixedVector.h"
+#include "Range.h"
+#include "Sizes.h"
+
+namespace bmalloc {
+
+struct BumpRange {
+    char* begin;
+    unsigned short objectCount;
+};
+
+typedef FixedVector<BumpRange, smallRangeCacheCapacity> SmallBumpRangeCache;
+typedef FixedVector<BumpRange, mediumRangeCacheCapacity> MediumBumpRangeCache;
+
+} // namespace bmalloc
+
+#endif // BumpRange_h
index b8dae21..1a23af5 100644 (file)
@@ -72,15 +72,11 @@ void Deallocator::processObjectLog()
     for (auto object : m_objectLog) {
         if (isSmall(object)) {
             SmallLine* line = SmallLine::get(object);
-            if (!line->deref(lock))
-                continue;
-            heap->deallocateSmallLine(lock, line);
+            heap->derefSmallLine(lock, line);
         } else {
-            BASSERT(isSmallOrMedium(object));
+            BASSERT(isMedium(object));
             MediumLine* line = MediumLine::get(object);
-            if (!line->deref(lock))
-                continue;
-            heap->deallocateMediumLine(lock, line);
+            heap->derefMediumLine(lock, line);
         }
     }
     
index d4293f0..edb0767 100644 (file)
@@ -50,6 +50,42 @@ Heap::Heap(std::lock_guard<StaticMutex>&)
     : m_isAllocatingPages(false)
     , m_scavenger(*this, &Heap::concurrentScavenge)
 {
+    initializeLineMetadata();
+}
+
+void Heap::initializeLineMetadata()
+{
+    for (unsigned short size = alignment; size <= smallMax; size += alignment) {
+        unsigned short startOffset = 0;
+        for (size_t lineNumber = 0; lineNumber < SmallPage::lineCount - 1; ++lineNumber) {
+            unsigned short objectCount;
+            unsigned short remainder;
+            divideRoundingUp(static_cast<unsigned short>(SmallPage::lineSize - startOffset), size, objectCount, remainder);
+            BASSERT(objectCount);
+            m_smallLineMetadata[sizeClass(size)][lineNumber] = { startOffset, objectCount };
+            startOffset = remainder ? size - remainder : 0;
+        }
+
+        // The last line in the page rounds down instead of up because it's not allowed to overlap into its neighbor.
+        unsigned short objectCount = static_cast<unsigned short>((SmallPage::lineSize - startOffset) / size);
+        m_smallLineMetadata[sizeClass(size)][SmallPage::lineCount - 1] = { startOffset, objectCount };
+    }
+
+    for (unsigned short size = smallMax + alignment; size <= mediumMax; size += alignment) {
+        unsigned short startOffset = 0;
+        for (size_t lineNumber = 0; lineNumber < MediumPage::lineCount - 1; ++lineNumber) {
+            unsigned short objectCount;
+            unsigned short remainder;
+            divideRoundingUp(static_cast<unsigned short>(MediumPage::lineSize - startOffset), size, objectCount, remainder);
+            BASSERT(objectCount);
+            m_mediumLineMetadata[sizeClass(size)][lineNumber] = { startOffset, objectCount };
+            startOffset = remainder ? size - remainder : 0;
+        }
+
+        // The last line in the page rounds down instead of up because it's not allowed to overlap into its neighbor.
+        unsigned short objectCount = static_cast<unsigned short>((MediumPage::lineSize - startOffset) / size);
+        m_mediumLineMetadata[sizeClass(size)][MediumPage::lineCount - 1] = { startOffset, objectCount };
+    }
 }
 
 void Heap::concurrentScavenge()
@@ -116,11 +152,93 @@ void Heap::scavengeLargeRanges(std::unique_lock<StaticMutex>& lock, std::chrono:
     }
 }
 
-SmallLine* Heap::allocateSmallLineSlowCase(std::lock_guard<StaticMutex>& lock, size_t smallSizeClass)
+void Heap::refillSmallBumpRangeCache(std::lock_guard<StaticMutex>& lock, size_t sizeClass, SmallBumpRangeCache& rangeCache)
+{
+    BASSERT(!rangeCache.size());
+    SmallPage* page = allocateSmallPage(lock, sizeClass);
+    SmallLine* lines = page->begin();
+
+    // Due to overlap from the previous line, the last line in the page may not be able to fit any objects.
+    size_t end = SmallPage::lineCount;
+    if (!m_smallLineMetadata[sizeClass][SmallPage::lineCount - 1].objectCount)
+        --end;
+
+    // Find a free line.
+    for (size_t lineNumber = 0; lineNumber < end; ++lineNumber) {
+        if (lines[lineNumber].refCount(lock))
+            continue;
+
+        LineMetadata& lineMetadata = m_smallLineMetadata[sizeClass][lineNumber];
+        char* begin = lines[lineNumber].begin() + lineMetadata.startOffset;
+        unsigned short objectCount = lineMetadata.objectCount;
+        lines[lineNumber].ref(lock, lineMetadata.objectCount);
+        page->ref(lock);
+
+        // Merge with subsequent free lines.
+        while (++lineNumber < end) {
+            if (lines[lineNumber].refCount(lock))
+                break;
+
+            LineMetadata& lineMetadata = m_smallLineMetadata[sizeClass][lineNumber];
+            objectCount += lineMetadata.objectCount;
+            lines[lineNumber].ref(lock, lineMetadata.objectCount);
+            page->ref(lock);
+        }
+
+        rangeCache.push({ begin, objectCount });
+    }
+}
+
+void Heap::refillMediumBumpRangeCache(std::lock_guard<StaticMutex>& lock, size_t sizeClass, MediumBumpRangeCache& rangeCache)
+{
+    MediumPage* page = allocateMediumPage(lock, sizeClass);
+    BASSERT(!rangeCache.size());
+    MediumLine* lines = page->begin();
+
+    // Due to overlap from the previous line, the last line in the page may not be able to fit any objects.
+    size_t end = MediumPage::lineCount;
+    if (!m_mediumLineMetadata[sizeClass][MediumPage::lineCount - 1].objectCount)
+        --end;
+
+    // Find a free line.
+    for (size_t lineNumber = 0; lineNumber < end; ++lineNumber) {
+        if (lines[lineNumber].refCount(lock))
+            continue;
+
+        LineMetadata& lineMetadata = m_mediumLineMetadata[sizeClass][lineNumber];
+        char* begin = lines[lineNumber].begin() + lineMetadata.startOffset;
+        unsigned short objectCount = lineMetadata.objectCount;
+        lines[lineNumber].ref(lock, lineMetadata.objectCount);
+        page->ref(lock);
+        
+        // Merge with subsequent free lines.
+        while (++lineNumber < end) {
+            if (lines[lineNumber].refCount(lock))
+                break;
+
+            LineMetadata& lineMetadata = m_mediumLineMetadata[sizeClass][lineNumber];
+            objectCount += lineMetadata.objectCount;
+            lines[lineNumber].ref(lock, lineMetadata.objectCount);
+            page->ref(lock);
+        }
+
+        rangeCache.push({ begin, objectCount });
+    }
+}
+
+SmallPage* Heap::allocateSmallPage(std::lock_guard<StaticMutex>& lock, size_t sizeClass)
 {
+    Vector<SmallPage*>& smallPagesWithFreeLines = m_smallPagesWithFreeLines[sizeClass];
+    while (smallPagesWithFreeLines.size()) {
+        SmallPage* page = smallPagesWithFreeLines.pop();
+        if (!page->refCount(lock) || page->sizeClass() != sizeClass) // Page was promoted to the pages list.
+            continue;
+        return page;
+    }
+    
     m_isAllocatingPages = true;
 
-    SmallPage* page = [this]() {
+    SmallPage* page = [this, sizeClass]() {
         if (m_smallPages.size())
             return m_smallPages.pop();
         
@@ -129,22 +247,23 @@ SmallLine* Heap::allocateSmallLineSlowCase(std::lock_guard<StaticMutex>& lock, s
         return page;
     }();
 
-    SmallLine* line = page->begin();
-    Vector<SmallLine*>& smallLines = m_smallLines[smallSizeClass];
-    for (auto it = line + 1; it != page->end(); ++it)
-        smallLines.push(it);
-
-    BASSERT(!line->refCount(lock));
-    page->setSmallSizeClass(smallSizeClass);
-    page->ref(lock);
-    return line;
+    page->setSizeClass(sizeClass);
+    return page;
 }
 
-MediumLine* Heap::allocateMediumLineSlowCase(std::lock_guard<StaticMutex>& lock)
+MediumPage* Heap::allocateMediumPage(std::lock_guard<StaticMutex>& lock, size_t sizeClass)
 {
+    Vector<MediumPage*>& mediumPagesWithFreeLines = m_mediumPagesWithFreeLines[sizeClass];
+    while (mediumPagesWithFreeLines.size()) {
+        MediumPage* page = mediumPagesWithFreeLines.pop();
+        if (!page->refCount(lock) || page->sizeClass() != sizeClass) // Page was promoted to the pages list.
+            continue;
+        return page;
+    }
+    
     m_isAllocatingPages = true;
 
-    MediumPage* page = [this]() {
+    MediumPage* page = [this, sizeClass]() {
         if (m_mediumPages.size())
             return m_mediumPages.pop();
         
@@ -153,12 +272,52 @@ MediumLine* Heap::allocateMediumLineSlowCase(std::lock_guard<StaticMutex>& lock)
         return page;
     }();
 
-    MediumLine* line = page->begin();
-    for (auto it = line + 1; it != page->end(); ++it)
-        m_mediumLines.push(it);
+    page->setSizeClass(sizeClass);
+    return page;
+}
 
-    page->ref(lock);
-    return line;
+void Heap::deallocateSmallLine(std::lock_guard<StaticMutex>& lock, SmallLine* line)
+{
+    BASSERT(!line->refCount(lock));
+    SmallPage* page = SmallPage::get(line);
+    size_t refCount = page->refCount(lock);
+    page->deref(lock);
+
+    switch (refCount) {
+    case SmallPage::lineCount: {
+        // First free line in the page.
+        m_smallPagesWithFreeLines[page->sizeClass()].push(page);
+        break;
+    }
+    case 1: {
+        // Last free line in the page.
+        m_smallPages.push(page);
+        m_scavenger.run();
+        break;
+    }
+    }
+}
+
+void Heap::deallocateMediumLine(std::lock_guard<StaticMutex>& lock, MediumLine* line)
+{
+    BASSERT(!line->refCount(lock));
+    MediumPage* page = MediumPage::get(line);
+    size_t refCount = page->refCount(lock);
+    page->deref(lock);
+
+    switch (refCount) {
+    case MediumPage::lineCount: {
+        // First free line in the page.
+        m_mediumPagesWithFreeLines[page->sizeClass()].push(page);
+        break;
+    }
+    case 1: {
+        // Last free line in the page.
+        m_mediumPages.push(page);
+        m_scavenger.run();
+        break;
+    }
+    }
 }
 
 void* Heap::allocateXLarge(std::lock_guard<StaticMutex>&, size_t size)
index 6d160e3..34bffa7 100644 (file)
 #ifndef Heap_h
 #define Heap_h
 
-#include "FixedVector.h"
-#include "VMHeap.h"
-#include "MediumLine.h"
-#include "Mutex.h"
-#include "SmallPage.h"
+#include "BumpRange.h"
+#include "LineMetadata.h"
 #include "MediumChunk.h"
+#include "MediumLine.h"
 #include "MediumPage.h"
+#include "Mutex.h"
 #include "SegregatedFreeList.h"
 #include "SmallChunk.h"
 #include "SmallLine.h"
+#include "SmallPage.h"
+#include "VMHeap.h"
 #include "Vector.h"
 #include <array>
 #include <mutex>
@@ -49,12 +50,12 @@ class Heap {
 public:
     Heap(std::lock_guard<StaticMutex>&);
 
-    SmallLine* allocateSmallLine(std::lock_guard<StaticMutex>&, size_t smallSizeClass);
-    void deallocateSmallLine(std::lock_guard<StaticMutex>&, SmallLine*);
+    void refillSmallBumpRangeCache(std::lock_guard<StaticMutex>&, size_t sizeClass, SmallBumpRangeCache&);
+    void derefSmallLine(std::lock_guard<StaticMutex>&, SmallLine*);
+
+    void refillMediumBumpRangeCache(std::lock_guard<StaticMutex>&, size_t sizeClass, MediumBumpRangeCache&);
+    void derefMediumLine(std::lock_guard<StaticMutex>&, MediumLine*);
 
-    MediumLine* allocateMediumLine(std::lock_guard<StaticMutex>&);
-    void deallocateMediumLine(std::lock_guard<StaticMutex>&, MediumLine*);
-    
     void* allocateLarge(std::lock_guard<StaticMutex>&, size_t);
     void deallocateLarge(std::lock_guard<StaticMutex>&, void*);
 
@@ -68,9 +69,14 @@ public:
 
 private:
     ~Heap() = delete;
+    
+    void initializeLineMetadata();
+
+    SmallPage* allocateSmallPage(std::lock_guard<StaticMutex>&, size_t sizeClass);
+    MediumPage* allocateMediumPage(std::lock_guard<StaticMutex>&, size_t sizeClass);
 
-    SmallLine* allocateSmallLineSlowCase(std::lock_guard<StaticMutex>&, size_t smallSizeClass);
-    MediumLine* allocateMediumLineSlowCase(std::lock_guard<StaticMutex>&);
+    void deallocateSmallLine(std::lock_guard<StaticMutex>&, SmallLine*);
+    void deallocateMediumLine(std::lock_guard<StaticMutex>&, MediumLine*);
 
     void* allocateLarge(Range, size_t);
     Range allocateLargeChunk();
@@ -85,8 +91,11 @@ private:
     void scavengeMediumPages(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
     void scavengeLargeRanges(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
 
-    std::array<Vector<SmallLine*>, smallMax / alignment> m_smallLines;
-    Vector<MediumLine*> m_mediumLines;
+    std::array<std::array<LineMetadata, SmallPage::lineCount>, smallMax / alignment> m_smallLineMetadata;
+    std::array<std::array<LineMetadata, MediumPage::lineCount>, mediumMax / alignment> m_mediumLineMetadata;
+
+    std::array<Vector<SmallPage*>, smallMax / alignment> m_smallPagesWithFreeLines;
+    std::array<Vector<MediumPage*>, mediumMax / alignment> m_mediumPagesWithFreeLines;
 
     Vector<SmallPage*> m_smallPages;
     Vector<MediumPage*> m_mediumPages;
@@ -99,59 +108,18 @@ private:
     AsyncTask<Heap, decltype(&Heap::concurrentScavenge)> m_scavenger;
 };
 
-inline void Heap::deallocateSmallLine(std::lock_guard<StaticMutex>& lock, SmallLine* line)
+inline void Heap::derefSmallLine(std::lock_guard<StaticMutex>& lock, SmallLine* line)
 {
-    BASSERT(!line->refCount(lock));
-    SmallPage* page = SmallPage::get(line);
-    if (page->deref(lock)) {
-        m_smallPages.push(page);
-        m_scavenger.run();
+    if (!line->deref(lock))
         return;
-    }
-    m_smallLines[page->smallSizeClass()].push(line);
+    deallocateSmallLine(lock, line);
 }
 
-inline SmallLine* Heap::allocateSmallLine(std::lock_guard<StaticMutex>& lock, size_t smallSizeClass)
+inline void Heap::derefMediumLine(std::lock_guard<StaticMutex>& lock, MediumLine* line)
 {
-    Vector<SmallLine*>& smallLines = m_smallLines[smallSizeClass];
-    while (smallLines.size()) {
-        SmallLine* line = smallLines.pop();
-        SmallPage* page = SmallPage::get(line);
-        if (!page->refCount(lock) || page->smallSizeClass() != smallSizeClass) // The line was promoted to the small pages list.
-            continue;
-        BASSERT(!line->refCount(lock));
-        page->ref(lock);
-        return line;
-    }
-
-    return allocateSmallLineSlowCase(lock, smallSizeClass);
-}
-
-inline void Heap::deallocateMediumLine(std::lock_guard<StaticMutex>& lock, MediumLine* line)
-{
-    BASSERT(!line->refCount(lock));
-    MediumPage* page = MediumPage::get(line);
-    if (page->deref(lock)) {
-        m_mediumPages.push(page);
-        m_scavenger.run();
+    if (!line->deref(lock))
         return;
-    }
-    m_mediumLines.push(line);
-}
-
-inline MediumLine* Heap::allocateMediumLine(std::lock_guard<StaticMutex>& lock)
-{
-    while (m_mediumLines.size()) {
-        MediumLine* line = m_mediumLines.pop();
-        MediumPage* page = MediumPage::get(line);
-        if (!page->refCount(lock)) // The line was promoted to the medium pages list.
-            continue;
-        BASSERT(!line->refCount(lock));
-        page->ref(lock);
-        return line;
-    }
-
-    return allocateMediumLineSlowCase(lock);
+    deallocateMediumLine(lock, line);
 }
 
 } // namespace bmalloc
index dc00a1e..8a8d71e 100644 (file)
@@ -45,8 +45,8 @@ public:
 
     static Line* get(void*);
 
-    void concurrentRef(unsigned char = 1);
-    bool deref(std::lock_guard<StaticMutex>&, unsigned char = 1);
+    void ref(std::lock_guard<StaticMutex>&, unsigned char);
+    bool deref(std::lock_guard<StaticMutex>&);
     unsigned refCount(std::lock_guard<StaticMutex>&) { return m_refCount; }
     
     char* begin();
@@ -81,18 +81,18 @@ inline char* Line<Traits>::end()
 }
 
 template<class Traits>
-inline void Line<Traits>::concurrentRef(unsigned char count)
+inline void Line<Traits>::ref(std::lock_guard<StaticMutex>&, unsigned char refCount)
 {
-    BASSERT(!m_refCount); // Up-ref from zero can be lock-free because there are no other clients.
-    BASSERT(count <= maxRefCount);
-    m_refCount = count;
+    BASSERT(!m_refCount);
+    BASSERT(refCount <= maxRefCount);
+    m_refCount = refCount;
 }
 
 template<class Traits>
-inline bool Line<Traits>::deref(std::lock_guard<StaticMutex>&, unsigned char count)
+inline bool Line<Traits>::deref(std::lock_guard<StaticMutex>&)
 {
-    BASSERT(count <= m_refCount);
-    m_refCount -= count;
+    BASSERT(m_refCount);
+    --m_refCount;
     return !m_refCount;
 }
 
diff --git a/Source/bmalloc/bmalloc/LineMetadata.h b/Source/bmalloc/bmalloc/LineMetadata.h
new file mode 100644 (file)
index 0000000..1593347
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+ * Copyright (C) 2014 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. 
+ */
+
+#ifndef LineMetadata_h
+#define LineMetadata_h
+
+namespace bmalloc {
+
+struct LineMetadata {
+    unsigned short startOffset;
+    unsigned short objectCount;
+};
+
+} // namespace bmalloc
+
+#endif // LineMetadata_h
diff --git a/Source/bmalloc/bmalloc/MediumAllocator.h b/Source/bmalloc/bmalloc/MediumAllocator.h
deleted file mode 100644 (file)
index 0f6828b..0000000
+++ /dev/null
@@ -1,115 +0,0 @@
-/*
- * Copyright (C) 2014 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. 
- */
-
-#ifndef MediumAllocator_h
-#define MediumAllocator_h
-
-#include "BAssert.h"
-#include "MediumChunk.h"
-#include "MediumLine.h"
-
-namespace bmalloc {
-
-// Helper object for allocating medium objects.
-
-class MediumAllocator {
-public:
-    MediumAllocator();
-
-    bool isNull() { return !m_end; }
-    MediumLine* line();
-
-    void* allocate(size_t);
-    bool allocate(size_t, void*&);
-
-    unsigned char derefCount();
-
-    void refill(MediumLine*);
-    void clear();
-
-private:
-    char* m_end;
-    size_t m_remaining;
-    size_t m_objectCount;
-};
-
-inline MediumAllocator::MediumAllocator()
-    : m_end()
-    , m_remaining()
-    , m_objectCount()
-{
-}
-
-inline MediumLine* MediumAllocator::line()
-{
-    return MediumLine::get(m_end - 1);
-}
-
-inline void* MediumAllocator::allocate(size_t size)
-{
-    BASSERT(size <= m_remaining);
-    BASSERT(size == roundUpToMultipleOf<alignment>(size));
-    BASSERT(size >= MediumLine::minimumObjectSize);
-
-    m_remaining -= size;
-    void* object = m_end - m_remaining - size;
-    BASSERT(isSmallOrMedium(object) && !isSmall(object));
-
-    ++m_objectCount;
-    return object;
-}
-
-inline bool MediumAllocator::allocate(size_t size, void*& object)
-{
-    if (size > m_remaining)
-        return false;
-
-    object = allocate(size);
-    return true;
-}
-
-inline unsigned char MediumAllocator::derefCount()
-{
-    return MediumLine::maxRefCount - m_objectCount;
-}
-
-inline void MediumAllocator::refill(MediumLine* line)
-{
-    line->concurrentRef(MediumLine::maxRefCount);
-    m_end = line->end();
-    m_remaining = mediumLineSize;
-    m_objectCount = 0;
-}
-
-inline void MediumAllocator::clear()
-{
-    m_end = nullptr;
-    m_remaining = 0;
-    m_objectCount = 0;
-}
-
-} // namespace bmalloc
-
-#endif // MediumAllocator_h
index 9e829d6..38140a5 100644 (file)
@@ -39,9 +39,10 @@ public:
     typedef typename Traits::Chunk Chunk;
     typedef typename Traits::Line Line;
     static const size_t lineSize = Traits::lineSize;
+    static const size_t lineCount = vmPageSize / lineSize;
 
     static const unsigned char maxRefCount = std::numeric_limits<unsigned char>::max();
-    static_assert(vmPageSize / lineSize < maxRefCount, "maximum line count must fit in Page");
+    static_assert(lineCount < maxRefCount, "maximum line count must fit in Page");
     
     static Page* get(Line*);
 
@@ -49,15 +50,15 @@ public:
     bool deref(std::lock_guard<StaticMutex>&);
     unsigned refCount(std::lock_guard<StaticMutex>&) { return m_refCount; }
     
-    size_t smallSizeClass() { return m_smallSizeClass; }
-    void setSmallSizeClass(size_t smallSizeClass) { m_smallSizeClass = smallSizeClass; }
+    size_t sizeClass() { return m_sizeClass; }
+    void setSizeClass(size_t sizeClass) { m_sizeClass = sizeClass; }
     
     Line* begin();
     Line* end();
 
 private:
     unsigned char m_refCount;
-    unsigned char m_smallSizeClass;
+    unsigned char m_sizeClass;
 };
 
 template<typename Traits>
@@ -89,14 +90,14 @@ inline auto Page<Traits>::begin() -> Line*
 {
     Chunk* chunk = Chunk::get(this);
     size_t pageNumber = this - chunk->pages();
-    size_t lineNumber = pageNumber * vmPageSize / lineSize;
+    size_t lineNumber = pageNumber * lineCount;
     return &chunk->lines()[lineNumber];
 }
 
 template<typename Traits>
 inline auto Page<Traits>::end() -> Line*
 {
-    return begin() + vmPageSize / lineSize;
+    return begin() + lineCount;
 }
 
 } // namespace bmalloc
index 8f19b93..35e1840 100644 (file)
@@ -56,7 +56,7 @@ namespace Sizes {
     static const size_t superChunkSize = 32 * MB;
 
     static const size_t smallMax = 256;
-    static const size_t smallLineSize = 512;
+    static const size_t smallLineSize = 256;
     static const size_t smallLineMask = ~(smallLineSize - 1ul);
 
     static const size_t smallChunkSize = superChunkSize / 4;
@@ -64,7 +64,7 @@ namespace Sizes {
     static const size_t smallChunkMask = ~(smallChunkSize - 1ul);
 
     static const size_t mediumMax = 1024;
-    static const size_t mediumLineSize = 2048;
+    static const size_t mediumLineSize = 1024;
     static const size_t mediumLineMask = ~(mediumLineSize - 1ul);
 
     static const size_t mediumChunkSize = superChunkSize / 4;
@@ -92,21 +92,20 @@ namespace Sizes {
 
     static const size_t deallocatorLogCapacity = 256;
 
-    static const size_t smallLineCacheCapacity = vmPageSize / smallLineSize;
-    static const size_t mediumLineCacheCapacity = vmPageSize / mediumLineSize;
+    static const size_t smallRangeCacheCapacity = vmPageSize / smallLineSize;
+    static const size_t mediumRangeCacheCapacity = vmPageSize / mediumLineSize;
     
     static const std::chrono::milliseconds scavengeSleepDuration = std::chrono::milliseconds(512);
 
-    inline size_t smallSizeClassFor(size_t size)
+    inline size_t sizeClass(size_t size)
     {
-        static const size_t smallSizeClassMask = (smallMax / alignment) - 1;
-        return mask((size - 1ul) / alignment, smallSizeClassMask);
+        static const size_t sizeClassMask = (mediumMax / alignment) - 1;
+        return mask((size - 1ul) / alignment, sizeClassMask);
     }
 
-    inline size_t mediumSizeClassFor(size_t size)
+    inline size_t objectSize(size_t sizeClass)
     {
-        static const size_t mediumSizeClassMask = (mediumMax / alignment) - 1;
-        return mask((size - 1ul) / alignment, mediumSizeClassMask);
+        return (sizeClass + 1) * alignment;
     }
 };
 
index b1b18c8..9bea914 100644 (file)
@@ -52,15 +52,13 @@ inline void* realloc(void* object, size_t newSize)
     size_t oldSize = 0;
     switch(objectType(object)) {
     case Small: {
-        // We don't have an exact size, but we can calculate a maximum.
-        void* end = roundUpToMultipleOf<smallLineSize>(static_cast<char*>(object) + 1);
-        oldSize = static_cast<char*>(end) - static_cast<char*>(object);
+        SmallPage* page = SmallPage::get(SmallLine::get(object));
+        oldSize = objectSize(page->sizeClass());
         break;
     }
     case Medium: {
-        // We don't have an exact size, but we can calculate a maximum.
-        void* end = roundUpToMultipleOf<mediumLineSize>(static_cast<char*>(object) + 1);
-        oldSize = static_cast<char*>(end) - static_cast<char*>(object);
+        MediumPage* page = MediumPage::get(MediumLine::get(object));
+        oldSize = objectSize(page->sizeClass());
         break;
     }
     case Large: {