bmalloc: Remove the concept of medium objects
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 20 Feb 2016 00:03:56 +0000 (00:03 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 20 Feb 2016 00:03:56 +0000 (00:03 +0000)
https://bugs.webkit.org/show_bug.cgi?id=154436

Reviewed by Sam Weinig.

There's no need to distinguish medium objects from small: Small object
metadata works naturally for both as long as we allow an object to
span more than two small lines. (We already allow an object to span
more than one small line.)

This change reduces memory use because it eliminates the 1kB line size,
so we don't have to hold down 1kB lines for individual 264+ byte objects.

1kB lines were always a bit of a compromise. The main point of bump
allocation is to take advantage of cache lines. Cache lines are usually
64 bytes, so line sizes above 256 bytes are a bit of a stretch.

This change speeds up small object benchmarks because it eliminates the
branch to detect medium objects in deallocation log processing.

This change reduces virtual memory use from worst cast 4X to worst case
2X because the medium chunk is gone. iOS cares about virtual memory use
and terminates apps above ~1GB, so this change gives us more breathing room.

This change slows down medium benchmarks a bit because we end up doing
more work to recycle fragmented medium objects. Overall, the tradeoff
seems justified, since we have a net speedup and a memory use savings.

* bmalloc.xcodeproj/project.pbxproj: Removed all the medium files. We
can simplify even further in a follow-up patch, removing the base class
templates for Chunk, Page, and Line as well.

* bmalloc/Allocator.cpp:
(bmalloc::Allocator::Allocator):
(bmalloc::Allocator::allocate):
(bmalloc::Allocator::reallocate):
(bmalloc::Allocator::scavenge):
(bmalloc::Allocator::refillAllocatorSlowCase):
(bmalloc::Allocator::refillAllocator):
(bmalloc::Allocator::allocateSlowCase): Medium is gone. Small max is the
new medium max.

* bmalloc/Allocator.h:
(bmalloc::Allocator::allocateFastCase): Ditto.

* bmalloc/BumpAllocator.h:
(bmalloc::BumpAllocator::validate):
(bmalloc::BumpAllocator::allocate): No more medium.

* bmalloc/Chunk.h: No more medium.

* bmalloc/Deallocator.cpp:
(bmalloc::Deallocator::processObjectLog): No check for medium. This is
a speedup.

(bmalloc::Deallocator::deallocateSlowCase): No more medium.

* bmalloc/Deallocator.h:
(bmalloc::Deallocator::deallocateFastCase): Ditto.

* bmalloc/Heap.cpp:
(bmalloc::Heap::initializeLineMetadata): The algorithm here changed from
iterating each line to iterating each object. This helps us accomodate
objects that might span more than two lines -- i.e., all objects between
(512 bytes, 1024 bytes].

(bmalloc::Heap::scavenge):
(bmalloc::Heap::scavengeSmallPages):
(bmalloc::Heap::scavengeLargeObjects): Medium is gone.

(bmalloc::Heap::allocateSmallBumpRanges): Allow for lines that allocate
zero objects. This happens when an object spans more than two lines --
the middle lines allocate zero objects.

Also set the "has free lines" bit to false if we consume the last free
line. This needs to be a bit now because not all pages agree on their
maximum refcount anymore, so we need an explicit signal for the transition
from maximum to maximum - 1.

(bmalloc::Heap::allocateSmallPage): This code didn't change; I just removed
the medium code.

(bmalloc::Heap::deallocateSmallLine): Changed the algorithm to check
hasFreeLines. See allocateSmallBumpRanges.

(bmalloc::Heap::scavengeMediumPages): Deleted.
(bmalloc::Heap::allocateMediumBumpRanges): Deleted.
(bmalloc::Heap::allocateMediumPage): Deleted.
(bmalloc::Heap::deallocateMediumLine): Deleted.
* bmalloc/Heap.h:
(bmalloc::Heap::derefMediumLine): Deleted.

* bmalloc/LargeChunk.h:
(bmalloc::LargeChunk::get):
(bmalloc::LargeChunk::endTag):
* bmalloc/Line.h: No more medium.

* bmalloc/MediumChunk.h: Removed.
* bmalloc/MediumLine.h: Removed.
* bmalloc/MediumPage.h: Removed.
* bmalloc/MediumTraits.h: Removed.

* bmalloc/ObjectType.cpp:
(bmalloc::objectType):
* bmalloc/ObjectType.h:
(bmalloc::isSmall):
(bmalloc::isXLarge):
(bmalloc::isSmallOrMedium): Deleted.
(bmalloc::isMedium): Deleted. No more medium.

* bmalloc/Page.h:
(bmalloc::Page::sizeClass):
(bmalloc::Page::setSizeClass):
(bmalloc::Page::hasFreeLines):
(bmalloc::Page::setHasFreeLines): Add the free lines bit. You get better
codegen if you make it the low bit, since ref / deref can then add / sub
2. So do that.

* bmalloc/Sizes.h:
(bmalloc::Sizes::sizeClass): Expand the small size class to include the
medium size class.

* bmalloc/SuperChunk.h:
(bmalloc::SuperChunk::SuperChunk):
(bmalloc::SuperChunk::smallChunk):
(bmalloc::SuperChunk::largeChunk):
(bmalloc::SuperChunk::mediumChunk): Deleted. No more medium.

* bmalloc/VMHeap.cpp:
(bmalloc::VMHeap::grow):
* bmalloc/VMHeap.h:
(bmalloc::VMHeap::allocateSmallPage): Set the has free lines bit before
returning a Page to the Heap since this is the correct default state
when we first allocate a page.

(bmalloc::VMHeap::allocateMediumPage): Deleted.
(bmalloc::VMHeap::deallocateMediumPage): Deleted.

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

23 files changed:
Source/bmalloc/ChangeLog
Source/bmalloc/bmalloc.xcodeproj/project.pbxproj
Source/bmalloc/bmalloc/Allocator.cpp
Source/bmalloc/bmalloc/Allocator.h
Source/bmalloc/bmalloc/BumpAllocator.h
Source/bmalloc/bmalloc/Chunk.h
Source/bmalloc/bmalloc/Deallocator.cpp
Source/bmalloc/bmalloc/Deallocator.h
Source/bmalloc/bmalloc/Heap.cpp
Source/bmalloc/bmalloc/Heap.h
Source/bmalloc/bmalloc/LargeChunk.h
Source/bmalloc/bmalloc/Line.h
Source/bmalloc/bmalloc/MediumChunk.h [deleted file]
Source/bmalloc/bmalloc/MediumLine.h [deleted file]
Source/bmalloc/bmalloc/MediumPage.h [deleted file]
Source/bmalloc/bmalloc/MediumTraits.h [deleted file]
Source/bmalloc/bmalloc/ObjectType.cpp
Source/bmalloc/bmalloc/ObjectType.h
Source/bmalloc/bmalloc/Page.h
Source/bmalloc/bmalloc/Sizes.h
Source/bmalloc/bmalloc/SuperChunk.h
Source/bmalloc/bmalloc/VMHeap.cpp
Source/bmalloc/bmalloc/VMHeap.h

index 5cc351c..013ea22 100644 (file)
@@ -1,3 +1,143 @@
+2016-02-18  Geoffrey Garen  <ggaren@apple.com>
+
+        bmalloc: Remove the concept of medium objects
+        https://bugs.webkit.org/show_bug.cgi?id=154436
+
+        Reviewed by Sam Weinig.
+
+        There's no need to distinguish medium objects from small: Small object
+        metadata works naturally for both as long as we allow an object to
+        span more than two small lines. (We already allow an object to span
+        more than one small line.)
+
+        This change reduces memory use because it eliminates the 1kB line size,
+        so we don't have to hold down 1kB lines for individual 264+ byte objects.
+
+        1kB lines were always a bit of a compromise. The main point of bump
+        allocation is to take advantage of cache lines. Cache lines are usually
+        64 bytes, so line sizes above 256 bytes are a bit of a stretch.
+
+        This change speeds up small object benchmarks because it eliminates the
+        branch to detect medium objects in deallocation log processing.
+
+        This change reduces virtual memory use from worst cast 4X to worst case
+        2X because the medium chunk is gone. iOS cares about virtual memory use
+        and terminates apps above ~1GB, so this change gives us more breathing room.
+
+        This change slows down medium benchmarks a bit because we end up doing
+        more work to recycle fragmented medium objects. Overall, the tradeoff
+        seems justified, since we have a net speedup and a memory use savings.
+
+        * bmalloc.xcodeproj/project.pbxproj: Removed all the medium files. We
+        can simplify even further in a follow-up patch, removing the base class
+        templates for Chunk, Page, and Line as well.
+
+        * bmalloc/Allocator.cpp:
+        (bmalloc::Allocator::Allocator):
+        (bmalloc::Allocator::allocate):
+        (bmalloc::Allocator::reallocate):
+        (bmalloc::Allocator::scavenge):
+        (bmalloc::Allocator::refillAllocatorSlowCase):
+        (bmalloc::Allocator::refillAllocator):
+        (bmalloc::Allocator::allocateSlowCase): Medium is gone. Small max is the
+        new medium max.
+
+        * bmalloc/Allocator.h:
+        (bmalloc::Allocator::allocateFastCase): Ditto.
+
+        * bmalloc/BumpAllocator.h:
+        (bmalloc::BumpAllocator::validate):
+        (bmalloc::BumpAllocator::allocate): No more medium.
+
+        * bmalloc/Chunk.h: No more medium.
+
+        * bmalloc/Deallocator.cpp:
+        (bmalloc::Deallocator::processObjectLog): No check for medium. This is
+        a speedup.
+
+        (bmalloc::Deallocator::deallocateSlowCase): No more medium.
+
+        * bmalloc/Deallocator.h:
+        (bmalloc::Deallocator::deallocateFastCase): Ditto.
+
+        * bmalloc/Heap.cpp:
+        (bmalloc::Heap::initializeLineMetadata): The algorithm here changed from
+        iterating each line to iterating each object. This helps us accomodate
+        objects that might span more than two lines -- i.e., all objects between
+        (512 bytes, 1024 bytes].
+
+        (bmalloc::Heap::scavenge):
+        (bmalloc::Heap::scavengeSmallPages):
+        (bmalloc::Heap::scavengeLargeObjects): Medium is gone.
+
+        (bmalloc::Heap::allocateSmallBumpRanges): Allow for lines that allocate
+        zero objects. This happens when an object spans more than two lines --
+        the middle lines allocate zero objects.
+
+        Also set the "has free lines" bit to false if we consume the last free
+        line. This needs to be a bit now because not all pages agree on their
+        maximum refcount anymore, so we need an explicit signal for the transition
+        from maximum to maximum - 1.
+
+        (bmalloc::Heap::allocateSmallPage): This code didn't change; I just removed
+        the medium code.
+
+        (bmalloc::Heap::deallocateSmallLine): Changed the algorithm to check
+        hasFreeLines. See allocateSmallBumpRanges.
+
+        (bmalloc::Heap::scavengeMediumPages): Deleted.
+        (bmalloc::Heap::allocateMediumBumpRanges): Deleted.
+        (bmalloc::Heap::allocateMediumPage): Deleted.
+        (bmalloc::Heap::deallocateMediumLine): Deleted.
+        * bmalloc/Heap.h:
+        (bmalloc::Heap::derefMediumLine): Deleted.
+
+        * bmalloc/LargeChunk.h:
+        (bmalloc::LargeChunk::get):
+        (bmalloc::LargeChunk::endTag):
+        * bmalloc/Line.h: No more medium.
+
+        * bmalloc/MediumChunk.h: Removed.
+        * bmalloc/MediumLine.h: Removed.
+        * bmalloc/MediumPage.h: Removed.
+        * bmalloc/MediumTraits.h: Removed.
+
+        * bmalloc/ObjectType.cpp:
+        (bmalloc::objectType):
+        * bmalloc/ObjectType.h:
+        (bmalloc::isSmall):
+        (bmalloc::isXLarge):
+        (bmalloc::isSmallOrMedium): Deleted.
+        (bmalloc::isMedium): Deleted. No more medium.
+
+        * bmalloc/Page.h:
+        (bmalloc::Page::sizeClass):
+        (bmalloc::Page::setSizeClass):
+        (bmalloc::Page::hasFreeLines):
+        (bmalloc::Page::setHasFreeLines): Add the free lines bit. You get better
+        codegen if you make it the low bit, since ref / deref can then add / sub
+        2. So do that.
+
+        * bmalloc/Sizes.h:
+        (bmalloc::Sizes::sizeClass): Expand the small size class to include the
+        medium size class.
+
+        * bmalloc/SuperChunk.h:
+        (bmalloc::SuperChunk::SuperChunk):
+        (bmalloc::SuperChunk::smallChunk):
+        (bmalloc::SuperChunk::largeChunk):
+        (bmalloc::SuperChunk::mediumChunk): Deleted. No more medium.
+
+        * bmalloc/VMHeap.cpp:
+        (bmalloc::VMHeap::grow):
+        * bmalloc/VMHeap.h:
+        (bmalloc::VMHeap::allocateSmallPage): Set the has free lines bit before
+        returning a Page to the Heap since this is the correct default state
+        when we first allocate a page.
+
+        (bmalloc::VMHeap::allocateMediumPage): Deleted.
+        (bmalloc::VMHeap::deallocateMediumPage): Deleted.
+
 2016-02-19  Michael Saboff  <msaboff@apple.com>
 
         bmalloc: Unify VMHeap and Heap LargeObjects free lists to reduce fragmentation
index 3574186..90b80ef 100644 (file)
                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, ); }; };
-               14DD78B618F48D6B00950702 /* MediumChunk.h in Headers */ = {isa = PBXBuildFile; fileRef = 147AAA8E18CD89E3002201E4 /* MediumChunk.h */; settings = {ATTRIBUTES = (Private, ); }; };
-               14DD78B718F48D6B00950702 /* MediumLine.h in Headers */ = {isa = PBXBuildFile; fileRef = 1452478518BC757C00F80098 /* MediumLine.h */; settings = {ATTRIBUTES = (Private, ); }; };
-               14DD78B818F48D6B00950702 /* MediumPage.h in Headers */ = {isa = PBXBuildFile; fileRef = 143E29E918CAE8BE00FE8A0F /* MediumPage.h */; settings = {ATTRIBUTES = (Private, ); }; };
-               14DD78B918F48D6B00950702 /* MediumTraits.h in Headers */ = {isa = PBXBuildFile; fileRef = 147AAA9618CE5FB6002201E4 /* MediumTraits.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14DD78BA18F48D6B00950702 /* Page.h in Headers */ = {isa = PBXBuildFile; fileRef = 146BEE2318C980D60002D5A2 /* Page.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14DD78BB18F48D6B00950702 /* SmallChunk.h in Headers */ = {isa = PBXBuildFile; fileRef = 147AAA8C18CD36A7002201E4 /* SmallChunk.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14DD78BC18F48D6B00950702 /* SmallLine.h in Headers */ = {isa = PBXBuildFile; fileRef = 1452478618BC757C00F80098 /* SmallLine.h */; settings = {ATTRIBUTES = (Private, ); }; };
@@ -93,7 +89,6 @@
                1421A87718EE462A00B4DD68 /* Algorithm.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; name = Algorithm.h; path = bmalloc/Algorithm.h; sourceTree = "<group>"; };
                143CB81A19022BC900B16A45 /* StaticMutex.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = StaticMutex.cpp; path = bmalloc/StaticMutex.cpp; sourceTree = "<group>"; };
                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>"; };
                144DCED617A649D90093B2F2 /* Mutex.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Mutex.h; path = bmalloc/Mutex.h; sourceTree = "<group>"; };
                144F7BFB18BFC517003537F3 /* VMHeap.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = VMHeap.cpp; path = bmalloc/VMHeap.cpp; sourceTree = "<group>"; };
                144F7BFC18BFC517003537F3 /* VMHeap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = VMHeap.h; path = bmalloc/VMHeap.h; sourceTree = "<group>"; };
-               1452478518BC757C00F80098 /* MediumLine.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = MediumLine.h; path = bmalloc/MediumLine.h; sourceTree = "<group>"; };
                1452478618BC757C00F80098 /* SmallLine.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = SmallLine.h; path = bmalloc/SmallLine.h; sourceTree = "<group>"; };
                145F6855179DC8CA00D65598 /* Allocator.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; lineEnding = 0; name = Allocator.cpp; path = bmalloc/Allocator.cpp; sourceTree = "<group>"; xcLanguageSpecificationIdentifier = xcode.lang.cpp; };
                145F6856179DC8CA00D65598 /* Allocator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; lineEnding = 0; name = Allocator.h; path = bmalloc/Allocator.h; sourceTree = "<group>"; xcLanguageSpecificationIdentifier = xcode.lang.objcpp; };
                1479E21417A1A63E006D4E9D /* VMAllocate.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; lineEnding = 0; name = VMAllocate.h; path = bmalloc/VMAllocate.h; sourceTree = "<group>"; xcLanguageSpecificationIdentifier = xcode.lang.objcpp; };
                147AAA8818CD17CE002201E4 /* LargeChunk.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = LargeChunk.h; path = bmalloc/LargeChunk.h; sourceTree = "<group>"; };
                147AAA8C18CD36A7002201E4 /* SmallChunk.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = SmallChunk.h; path = bmalloc/SmallChunk.h; sourceTree = "<group>"; };
-               147AAA8E18CD89E3002201E4 /* MediumChunk.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = MediumChunk.h; path = bmalloc/MediumChunk.h; sourceTree = "<group>"; };
                147AAA9418CE5CA6002201E4 /* Chunk.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Chunk.h; path = bmalloc/Chunk.h; sourceTree = "<group>"; };
-               147AAA9618CE5FB6002201E4 /* MediumTraits.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = MediumTraits.h; path = bmalloc/MediumTraits.h; sourceTree = "<group>"; };
                147AAA9718CE5FB6002201E4 /* SmallTraits.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = SmallTraits.h; path = bmalloc/SmallTraits.h; sourceTree = "<group>"; };
                1485655E18A43AF900ED6942 /* BoundaryTag.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = BoundaryTag.h; path = bmalloc/BoundaryTag.h; sourceTree = "<group>"; };
                1485656018A43DBA00ED6942 /* ObjectType.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = ObjectType.h; path = bmalloc/ObjectType.h; sourceTree = "<group>"; };
                        children = (
                                1448C2FD18F3752B00502839 /* api */,
                                14D9DB4D17F2865C00EAAB79 /* cache */,
-                               147AAA9C18CE6010002201E4 /* heap: large | xlarge */,
+                               147AAA9C18CE6010002201E4 /* heap: large */,
                                147AAA9A18CE5FD3002201E4 /* heap: small | medium */,
                                14D9DB4E17F2866E00EAAB79 /* heap */,
                                14D9DB4F17F2868900EAAB79 /* stdlib */,
                        children = (
                                147AAA9418CE5CA6002201E4 /* Chunk.h */,
                                14DA32071885F9E6007269E0 /* Line.h */,
-                               147AAA8E18CD89E3002201E4 /* MediumChunk.h */,
-                               1452478518BC757C00F80098 /* MediumLine.h */,
-                               143E29E918CAE8BE00FE8A0F /* MediumPage.h */,
-                               147AAA9618CE5FB6002201E4 /* MediumTraits.h */,
                                146BEE2318C980D60002D5A2 /* Page.h */,
                                147AAA8C18CD36A7002201E4 /* SmallChunk.h */,
                                1452478618BC757C00F80098 /* SmallLine.h */,
                        name = "heap: small | medium";
                        sourceTree = "<group>";
                };
-               147AAA9C18CE6010002201E4 /* heap: large | xlarge */ = {
+               147AAA9C18CE6010002201E4 /* heap: large */ = {
                        isa = PBXGroup;
                        children = (
                                1417F64518B54A700076FA3F /* BeginTag.h */,
                                146BEE1E18C841C50002D5A2 /* SegregatedFreeList.h */,
                                14D2CD9A1AA12CFB00770440 /* VMState.h */,
                        );
-                       name = "heap: large | xlarge";
+                       name = "heap: large";
                        sourceTree = "<group>";
                };
                14B650C418F39F4800751968 /* Configurations */ = {
                                14DD78B418F48D6B00950702 /* Chunk.h in Headers */,
                                14DD78CA18F48D7500950702 /* Mutex.h in Headers */,
                                143CB81D19022BC900B16A45 /* StaticMutex.h in Headers */,
-                               14DD78B918F48D6B00950702 /* MediumTraits.h in Headers */,
                                1448C30118F3754C00502839 /* bmalloc.h in Headers */,
                                14C6216F1A9A9A6200E72293 /* LargeObject.h in Headers */,
                                14DD789A18F48D4A00950702 /* Deallocator.h in Headers */,
                                14895D921A3A319C0006235D /* Environment.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 */,
                                14DD788E18F48CCD00950702 /* BoundaryTag.h in Headers */,
                                14DD78C818F48D7500950702 /* FixedVector.h in Headers */,
-                               14DD78B718F48D6B00950702 /* MediumLine.h in Headers */,
                                14D2CD9B1AA12CFB00770440 /* VMState.h in Headers */,
-                               14DD78B618F48D6B00950702 /* MediumChunk.h in Headers */,
                                14DD78BC18F48D6B00950702 /* SmallLine.h in Headers */,
                                14DD789818F48D4A00950702 /* Allocator.h in Headers */,
                                14DD78CB18F48D7500950702 /* PerProcess.h in Headers */,
index cef4e99..ca8cb26 100644 (file)
@@ -42,7 +42,7 @@ Allocator::Allocator(Heap* heap, Deallocator& deallocator)
     : m_isBmallocEnabled(heap->environment().isBmallocEnabled())
     , m_deallocator(deallocator)
 {
-    for (unsigned short size = alignment; size <= mediumMax; size += alignment)
+    for (unsigned short size = alignment; size <= smallMax; size += alignment)
         m_bumpAllocators[sizeClass(size)].init(size);
 }
 
@@ -87,16 +87,6 @@ void* Allocator::allocate(size_t alignment, size_t size)
         }
     }
 
-    if (size <= mediumMax && alignment <= mediumLineSize) {
-        size = std::max(size, smallMax + Sizes::alignment);
-        size_t alignmentMask = alignment - 1;
-        while (void* p = allocate(size)) {
-            if (!test(p, alignmentMask))
-                return p;
-            m_deallocator.deallocate(p);
-        }
-    }
-
     if (size <= largeMax && alignment <= largeMax) {
         size = std::max(largeMin, roundUpToMultipleOf<largeAlignment>(size));
         alignment = roundUpToMultipleOf<largeAlignment>(alignment);
@@ -130,17 +120,12 @@ void* Allocator::reallocate(void* object, size_t newSize)
         oldSize = objectSize(page->sizeClass());
         break;
     }
-    case Medium: {
-        MediumPage* page = MediumPage::get(MediumLine::get(object));
-        oldSize = objectSize(page->sizeClass());
-        break;
-    }
     case Large: {
         std::unique_lock<StaticMutex> lock(PerProcess<Heap>::mutex());
         LargeObject largeObject(object);
         oldSize = largeObject.size();
 
-        if (newSize < oldSize && newSize > mediumMax) {
+        if (newSize < oldSize && newSize > smallMax) {
             newSize = roundUpToMultipleOf<largeAlignment>(newSize);
             if (oldSize - newSize >= largeMin) {
                 std::pair<LargeObject, LargeObject> split = largeObject.split(newSize);
@@ -202,7 +187,7 @@ void* Allocator::reallocate(void* object, size_t newSize)
 
 void Allocator::scavenge()
 {
-    for (unsigned short i = alignment; i <= mediumMax; i += alignment) {
+    for (unsigned short i = alignment; i <= smallMax; i += alignment) {
         BumpAllocator& allocator = m_bumpAllocators[sizeClass(i)];
         BumpRangeCache& bumpRangeCache = m_bumpRangeCaches[sizeClass(i)];
 
@@ -224,10 +209,7 @@ NO_INLINE void Allocator::refillAllocatorSlowCase(BumpAllocator& allocator, size
     BumpRangeCache& bumpRangeCache = m_bumpRangeCaches[sizeClass];
 
     std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
-    if (sizeClass <= bmalloc::sizeClass(smallMax))
-        PerProcess<Heap>::getFastCase()->allocateSmallBumpRanges(lock, sizeClass, allocator, bumpRangeCache);
-    else
-        PerProcess<Heap>::getFastCase()->allocateMediumBumpRanges(lock, sizeClass, allocator, bumpRangeCache);
+    PerProcess<Heap>::getFastCase()->allocateSmallBumpRanges(lock, sizeClass, allocator, bumpRangeCache);
 }
 
 INLINE void Allocator::refillAllocator(BumpAllocator& allocator, size_t sizeClass)
@@ -257,7 +239,7 @@ void* Allocator::allocateSlowCase(size_t size)
     if (!m_isBmallocEnabled)
         return malloc(size);
 
-    if (size <= mediumMax) {
+    if (size <= smallMax) {
         size_t sizeClass = bmalloc::sizeClass(size);
         BumpAllocator& allocator = m_bumpAllocators[sizeClass];
         refillAllocator(allocator, sizeClass);
index eb16457..5731837 100644 (file)
@@ -52,15 +52,14 @@ private:
     bool allocateFastCase(size_t, void*&);
     void* allocateSlowCase(size_t);
     
-    void* allocateMedium(size_t);
     void* allocateLarge(size_t);
     void* allocateXLarge(size_t);
     
     void refillAllocator(BumpAllocator&, size_t sizeClass);
     void refillAllocatorSlowCase(BumpAllocator&, size_t sizeClass);
     
-    std::array<BumpAllocator, mediumMax / alignment> m_bumpAllocators;
-    std::array<BumpRangeCache, mediumMax / alignment> m_bumpRangeCaches;
+    std::array<BumpAllocator, smallMax / alignment> m_bumpAllocators;
+    std::array<BumpRangeCache, smallMax / alignment> m_bumpRangeCaches;
 
     bool m_isBmallocEnabled;
     Deallocator& m_deallocator;
@@ -68,7 +67,7 @@ private:
 
 inline bool Allocator::allocateFastCase(size_t size, void*& object)
 {
-    if (size > mediumMax)
+    if (size > smallMax)
         return false;
 
     BumpAllocator& allocator = m_bumpAllocators[sizeClass(size)];
index 68f07a5..e61f443 100644 (file)
@@ -32,7 +32,7 @@
 
 namespace bmalloc {
 
-// Helper object for allocating small and medium objects.
+// Helper object for allocating small objects.
 
 class BumpAllocator {
 public:
@@ -79,8 +79,8 @@ inline void BumpAllocator::validate(void* ptr)
         return;
     }
     
-    BASSERT(m_size <= mediumMax);
-    BASSERT(isMedium(ptr));
+    BASSERT(m_size <= smallMax);
+    BASSERT(isSmall(ptr));
 }
 
 inline void* BumpAllocator::allocate()
index 145c9fa..f76d151 100644 (file)
@@ -77,7 +77,7 @@ private:
 template<class Traits>
 inline auto Chunk<Traits>::get(void* object) -> Chunk*
 {
-    BASSERT(isSmallOrMedium(object));
+    BASSERT(isSmall(object));
     return static_cast<Chunk*>(mask(object, chunkMask));
 }
 
index cfc0f72..592fe0d 100644 (file)
@@ -77,14 +77,8 @@ void Deallocator::processObjectLog()
     Heap* heap = PerProcess<Heap>::getFastCase();
     
     for (auto* object : m_objectLog) {
-        if (isSmall(object)) {
-            SmallLine* line = SmallLine::get(object);
-            heap->derefSmallLine(lock, line);
-        } else {
-            BASSERT(isMedium(object));
-            MediumLine* line = MediumLine::get(object);
-            heap->derefMediumLine(lock, line);
-        }
+        SmallLine* line = SmallLine::get(object);
+        heap->derefSmallLine(lock, line);
     }
     
     m_objectLog.clear();
@@ -103,7 +97,7 @@ void Deallocator::deallocateSlowCase(void* object)
     if (!object)
         return;
 
-    if (isSmallOrMedium(object)) {
+    if (isSmall(object)) {
         processObjectLog();
         m_objectLog.push(object);
         return;
index 7caa41c..d0663cc 100644 (file)
@@ -56,7 +56,7 @@ private:
 
 inline bool Deallocator::deallocateFastCase(void* object)
 {
-    if (!isSmallOrMedium(object))
+    if (!isSmall(object))
         return false;
 
     BASSERT(object);
index bcd5310..a13cbe1 100644 (file)
@@ -28,7 +28,6 @@
 #include "LargeChunk.h"
 #include "LargeObject.h"
 #include "Line.h"
-#include "MediumChunk.h"
 #include "Page.h"
 #include "PerProcess.h"
 #include "SmallChunk.h"
@@ -46,36 +45,32 @@ Heap::Heap(std::lock_guard<StaticMutex>&)
 
 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;
-        }
+    // We assume that m_smallLineMetadata is zero-filled.
 
-        // 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 (size_t size = alignment; size <= smallMax; size += alignment) {
+        size_t sizeClass = bmalloc::sizeClass(size);
+        auto& metadata = m_smallLineMetadata[sizeClass];
+
+        size_t object = 0;
+        size_t line = 0;
+        while (object < vmPageSize) {
+            line = object / SmallPage::lineSize;
+            size_t leftover = object % SmallPage::lineSize;
+
+            size_t objectCount;
+            size_t remainder;
+            divideRoundingUp(SmallPage::lineSize - leftover, size, objectCount, remainder);
+
+            metadata[line] = { static_cast<unsigned short>(leftover), static_cast<unsigned short>(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;
+            object += objectCount * size;
         }
 
-        // 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 };
+        // Don't allow the last object in a page to escape the page.
+        if (object > vmPageSize) {
+            BASSERT(metadata[line].objectCount);
+            --metadata[line].objectCount;
+        }
     }
 }
 
@@ -90,7 +85,6 @@ void Heap::scavenge(std::unique_lock<StaticMutex>& lock, std::chrono::millisecon
     waitUntilFalse(lock, sleepDuration, m_isAllocatingPages);
 
     scavengeSmallPages(lock, sleepDuration);
-    scavengeMediumPages(lock, sleepDuration);
     scavengeLargeObjects(lock, sleepDuration);
 
     sleep(lock, sleepDuration);
@@ -104,14 +98,6 @@ void Heap::scavengeSmallPages(std::unique_lock<StaticMutex>& lock, std::chrono::
     }
 }
 
-void Heap::scavengeMediumPages(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
-{
-    while (m_mediumPages.size()) {
-        m_vmHeap.deallocateMediumPage(lock, m_mediumPages.pop());
-        waitUntilFalse(lock, sleepDuration, m_isAllocatingPages);
-    }
-}
-
 void Heap::scavengeLargeObjects(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
 {
     while (LargeObject largeObject = m_largeObjects.takeGreedy()) {
@@ -125,81 +111,37 @@ void Heap::allocateSmallBumpRanges(std::lock_guard<StaticMutex>& lock, size_t si
     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;
+    BASSERT(page->hasFreeLines(lock));
 
     // Find a free line.
-    for (size_t lineNumber = 0; lineNumber < end; ++lineNumber) {
+    for (size_t lineNumber = 0; lineNumber < SmallPage::lineCount; ++lineNumber) {
         if (lines[lineNumber].refCount(lock))
             continue;
 
+        LineMetadata& lineMetadata = m_smallLineMetadata[sizeClass][lineNumber];
+        if (!lineMetadata.objectCount)
+            continue;
+
         // In a fragmented page, some free ranges might not fit in the cache.
         if (rangeCache.size() == rangeCache.capacity()) {
             m_smallPagesWithFreeLines[sizeClass].push(page);
             return;
         }
 
-        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) {
+        while (++lineNumber < SmallPage::lineCount) {
             if (lines[lineNumber].refCount(lock))
                 break;
 
             LineMetadata& lineMetadata = m_smallLineMetadata[sizeClass][lineNumber];
-            objectCount += lineMetadata.objectCount;
-            lines[lineNumber].ref(lock, lineMetadata.objectCount);
-            page->ref(lock);
-        }
-
-        if (!allocator.canAllocate())
-            allocator.refill({ begin, objectCount });
-        else
-            rangeCache.push({ begin, objectCount });
-    }
-}
-
-void Heap::allocateMediumBumpRanges(std::lock_guard<StaticMutex>& lock, size_t sizeClass, BumpAllocator& allocator, BumpRangeCache& 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;
+            if (!lineMetadata.objectCount)
+                continue;
 
-    // Find a free line.
-    for (size_t lineNumber = 0; lineNumber < end; ++lineNumber) {
-        if (lines[lineNumber].refCount(lock))
-            continue;
-
-        // In a fragmented page, some free ranges might not fit in the cache.
-        if (rangeCache.size() == rangeCache.capacity()) {
-            m_mediumPagesWithFreeLines[sizeClass].push(page);
-            return;
-        }
-
-        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);
@@ -210,6 +152,8 @@ void Heap::allocateMediumBumpRanges(std::lock_guard<StaticMutex>& lock, size_t s
         else
             rangeCache.push({ begin, objectCount });
     }
+
+    page->setHasFreeLines(lock, false);
 }
 
 SmallPage* Heap::allocateSmallPage(std::lock_guard<StaticMutex>& lock, size_t sizeClass)
@@ -222,34 +166,13 @@ SmallPage* Heap::allocateSmallPage(std::lock_guard<StaticMutex>& lock, size_t si
         return page;
     }
 
-    SmallPage* page = [this, sizeClass]() {
+    SmallPage* page = [this, &lock]() {
         if (m_smallPages.size())
             return m_smallPages.pop();
 
         m_isAllocatingPages = true;
-        return m_vmHeap.allocateSmallPage();
-    }();
-
-    page->setSizeClass(sizeClass);
-    return page;
-}
-
-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;
+        SmallPage* page = m_vmHeap.allocateSmallPage(lock);
         return page;
-    }
-
-    MediumPage* page = [this, sizeClass]() {
-        if (m_mediumPages.size())
-            return m_mediumPages.pop();
-
-        m_isAllocatingPages = true;
-        return m_vmHeap.allocateMediumPage();
     }();
 
     page->setSizeClass(sizeClass);
@@ -260,44 +183,21 @@ void Heap::deallocateSmallLine(std::lock_guard<StaticMutex>& lock, SmallLine* li
 {
     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.
+    if (!page->hasFreeLines(lock)) {
+        page->setHasFreeLines(lock, true);
         m_smallPagesWithFreeLines[page->sizeClass()].push(page);
-        break;
-    }
-    case 1: {
-        // Last free line in the page.
-        m_smallPages.push(page);
-        m_scavenger.run();
-        break;
-    }
+
+        BASSERT(page->refCount(lock));
+        return;
     }
-}
 
-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);
+    if (page->refCount(lock))
+        return;
 
-    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;
-    }
-    }
+    m_smallPages.push(page);
+    m_scavenger.run();
 }
 
 void* Heap::allocateXLarge(std::lock_guard<StaticMutex>& lock, size_t alignment, size_t size)
index 726e27f..1d108fd 100644 (file)
@@ -29,9 +29,6 @@
 #include "BumpRange.h"
 #include "Environment.h"
 #include "LineMetadata.h"
-#include "MediumChunk.h"
-#include "MediumLine.h"
-#include "MediumPage.h"
 #include "Mutex.h"
 #include "SegregatedFreeList.h"
 #include "SmallChunk.h"
@@ -57,9 +54,6 @@ public:
     void allocateSmallBumpRanges(std::lock_guard<StaticMutex>&, size_t sizeClass, BumpAllocator&, BumpRangeCache&);
     void derefSmallLine(std::lock_guard<StaticMutex>&, SmallLine*);
 
-    void allocateMediumBumpRanges(std::lock_guard<StaticMutex>&, size_t sizeClass, BumpAllocator&, BumpRangeCache&);
-    void derefMediumLine(std::lock_guard<StaticMutex>&, MediumLine*);
-
     void* allocateLarge(std::lock_guard<StaticMutex>&, size_t);
     void* allocateLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t, size_t unalignedSize);
     void deallocateLarge(std::lock_guard<StaticMutex>&, void*);
@@ -78,11 +72,8 @@ private:
     void initializeLineMetadata();
 
     SmallPage* allocateSmallPage(std::lock_guard<StaticMutex>&, size_t sizeClass);
-    MediumPage* allocateMediumPage(std::lock_guard<StaticMutex>&, size_t sizeClass);
 
     void deallocateSmallLine(std::lock_guard<StaticMutex>&, SmallLine*);
-    void deallocateMediumLine(std::lock_guard<StaticMutex>&, MediumLine*);
-
     void deallocateLarge(std::lock_guard<StaticMutex>&, const LargeObject&);
 
     LargeObject& splitAndAllocate(LargeObject&, size_t);
@@ -93,17 +84,13 @@ private:
     
     void concurrentScavenge();
     void scavengeSmallPages(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
-    void scavengeMediumPages(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
     void scavengeLargeObjects(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
 
     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;
 
     SegregatedFreeList m_largeObjects;
     Vector<Range> m_xLargeObjects;
@@ -123,13 +110,6 @@ inline void Heap::derefSmallLine(std::lock_guard<StaticMutex>& lock, SmallLine*
     deallocateSmallLine(lock, line);
 }
 
-inline void Heap::derefMediumLine(std::lock_guard<StaticMutex>& lock, MediumLine* line)
-{
-    if (!line->deref(lock))
-        return;
-    deallocateMediumLine(lock, line);
-}
-
 } // namespace bmalloc
 
 #endif // Heap_h
index 4701a4c..22ed5bc 100644 (file)
@@ -83,7 +83,7 @@ static_assert(largeChunkMetadataSize + largeMax <= largeChunkSize, "We will thin
 
 inline LargeChunk* LargeChunk::get(void* object)
 {
-    BASSERT(!isSmallOrMedium(object));
+    BASSERT(!isSmall(object));
     return static_cast<LargeChunk*>(mask(object, largeChunkMask));
 }
 
@@ -96,7 +96,7 @@ inline BeginTag* LargeChunk::beginTag(void* object)
 
 inline EndTag* LargeChunk::endTag(void* object, size_t size)
 {
-    BASSERT(!isSmallOrMedium(object));
+    BASSERT(!isSmall(object));
 
     LargeChunk* chunk = get(object);
     char* end = static_cast<char*>(object) + size;
index 8af83ef..4975237 100644 (file)
@@ -60,7 +60,7 @@ private:
 template<class Traits>
 inline auto Line<Traits>::get(void* object) -> Line*
 {
-    BASSERT(isSmallOrMedium(object));
+    BASSERT(isSmall(object));
     Chunk* chunk = Chunk::get(object);
     size_t lineNumber = (reinterpret_cast<char*>(object) - reinterpret_cast<char*>(chunk)) / lineSize;
     return &chunk->lines()[lineNumber];
diff --git a/Source/bmalloc/bmalloc/MediumChunk.h b/Source/bmalloc/bmalloc/MediumChunk.h
deleted file mode 100644 (file)
index b165e57..0000000
+++ /dev/null
@@ -1,40 +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 MediumChunk_h
-#define MediumChunk_h
-
-#include "Chunk.h"
-#include "MediumLine.h"
-#include "MediumPage.h"
-#include "MediumTraits.h"
-
-namespace bmalloc {
-
-typedef Chunk<MediumTraits> MediumChunk;
-
-}; // namespace bmalloc
-
-#endif // MediumChunk
diff --git a/Source/bmalloc/bmalloc/MediumLine.h b/Source/bmalloc/bmalloc/MediumLine.h
deleted file mode 100644 (file)
index cb20d43..0000000
+++ /dev/null
@@ -1,38 +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 MediumLine_h
-#define MediumLine_h
-
-#include "Line.h"
-#include "MediumTraits.h"
-
-namespace bmalloc {
-
-typedef Line<MediumTraits> MediumLine;
-
-} // namespace bmalloc
-
-#endif // MediumLine_h
diff --git a/Source/bmalloc/bmalloc/MediumPage.h b/Source/bmalloc/bmalloc/MediumPage.h
deleted file mode 100644 (file)
index 893cfe6..0000000
+++ /dev/null
@@ -1,38 +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 MediumPage_h
-#define MediumPage_h
-
-#include "MediumTraits.h"
-#include "Page.h"
-
-namespace bmalloc {
-
-typedef Page<MediumTraits> MediumPage;
-
-} // namespace bmalloc
-
-#endif // MediumPage_h
diff --git a/Source/bmalloc/bmalloc/MediumTraits.h b/Source/bmalloc/bmalloc/MediumTraits.h
deleted file mode 100644 (file)
index 59d78f5..0000000
+++ /dev/null
@@ -1,52 +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 MediumTraits_h
-#define MediumTraits_h
-
-#include "Sizes.h"
-#include "VMAllocate.h"
-
-namespace bmalloc {
-
-template<class Traits> class Chunk;
-template<class Traits> class Line;
-template<class Traits> class Page;
-
-struct MediumTraits {
-    typedef Chunk<MediumTraits> ChunkType;
-    typedef Line<MediumTraits> LineType;
-    typedef Page<MediumTraits> PageType;
-
-    static const size_t lineSize = mediumLineSize;
-    static const size_t minimumObjectSize = smallMax + alignment;
-    static const size_t chunkSize = mediumChunkSize;
-    static const size_t chunkOffset = mediumChunkOffset;
-    static const uintptr_t chunkMask = mediumChunkMask;
-};
-
-} // namespace bmalloc
-
-#endif // MediumTraits_h
index 7e167c9..47f14e1 100644 (file)
@@ -30,11 +30,8 @@ namespace bmalloc {
 
 ObjectType objectType(void* object)
 {
-    if (isSmallOrMedium(object)) {
-        if (isSmall(object))
-            return Small;
-        return Medium;
-    }
+    if (isSmall(object))
+        return Small;
     
     if (!isXLarge(object))
         return Large;
index 4ec08a2..42093bf 100644 (file)
 
 namespace bmalloc {
 
-enum ObjectType { Small, Medium, Large, XLarge };
+enum ObjectType { Small, Large, XLarge };
 
 ObjectType objectType(void*);
 
-inline bool isSmallOrMedium(void* object)
+inline bool isSmall(void* object)
 {
-    return test(object, smallOrMediumTypeMask);
-}
-
-inline bool isSmall(void* smallOrMedium)
-{
-    BASSERT(isSmallOrMedium(smallOrMedium));
-    return test(smallOrMedium, smallOrMediumSmallTypeMask);
-}
-
-inline bool isMedium(void* smallOrMedium)
-{
-    return !isSmall(smallOrMedium);
+    return test(object, smallMask);
 }
 
 inline bool isXLarge(void* object)
 {
-    return !test(object, superChunkSize - 1);
+    return !test(object, ~superChunkMask);
 }
 
 } // namespace bmalloc
index fdfa158..edc77ef 100644 (file)
@@ -54,11 +54,15 @@ public:
     size_t sizeClass() { return m_sizeClass; }
     void setSizeClass(size_t sizeClass) { m_sizeClass = sizeClass; }
     
+    bool hasFreeLines(std::lock_guard<StaticMutex>&) const { return m_hasFreeLines; }
+    void setHasFreeLines(std::lock_guard<StaticMutex>&, bool hasFreeLines) { m_hasFreeLines = hasFreeLines; }
+    
     Line* begin();
     Line* end();
 
 private:
-    unsigned char m_refCount;
+    unsigned char m_hasFreeLines: 1;
+    unsigned char m_refCount: 7;
     unsigned char m_sizeClass;
 };
 
index 5888d17..fd6fb60 100644 (file)
@@ -54,23 +54,16 @@ namespace Sizes {
     static const size_t vmPageMask = ~(vmPageSize - 1);
     
     static const size_t superChunkSize = 2 * MB;
+    static const size_t superChunkMask = ~(superChunkSize - 1);
 
-    static const size_t smallMax = 256;
+    static const size_t smallMax = 1024;
     static const size_t smallLineSize = 256;
     static const size_t smallLineMask = ~(smallLineSize - 1ul);
 
-    static const size_t smallChunkSize = superChunkSize / 4;
-    static const size_t smallChunkOffset = superChunkSize * 3 / 4;
+    static const size_t smallChunkSize = superChunkSize / 2;
+    static const size_t smallChunkOffset = superChunkSize / 2;
     static const size_t smallChunkMask = ~(smallChunkSize - 1ul);
 
-    static const size_t mediumMax = 1024;
-    static const size_t mediumLineSize = 1024;
-    static const size_t mediumLineMask = ~(mediumLineSize - 1ul);
-
-    static const size_t mediumChunkSize = superChunkSize / 4;
-    static const size_t mediumChunkOffset = superChunkSize * 2 / 4;
-    static const size_t mediumChunkMask = ~(mediumChunkSize - 1ul);
-
     static const size_t largeChunkSize = superChunkSize / 2;
 #if BPLATFORM(IOS)
     static const size_t largeChunkMetadataSize = 16 * kB;
@@ -82,7 +75,7 @@ namespace Sizes {
 
     static const size_t largeAlignment = 64;
     static const size_t largeMax = largeChunkSize - largeChunkMetadataSize;
-    static const size_t largeMin = mediumMax;
+    static const size_t largeMin = smallMax;
     
     static const size_t xLargeAlignment = vmPageSize;
     static const size_t xLargeMax = std::numeric_limits<size_t>::max() - xLargeAlignment; // Make sure that rounding up to xLargeAlignment does not overflow.
@@ -90,12 +83,9 @@ namespace Sizes {
     static const size_t freeListSearchDepth = 16;
     static const size_t freeListGrowFactor = 2;
 
-    static const uintptr_t typeMask = (superChunkSize - 1) & ~((superChunkSize / 4) - 1); // 4 taggable chunks
-    static const uintptr_t smallType = (superChunkSize + smallChunkOffset) & typeMask;
-    static const uintptr_t mediumType = (superChunkSize + mediumChunkOffset) & typeMask;
-    static const uintptr_t largeTypeMask = ~(mediumType & smallType);
-    static const uintptr_t smallOrMediumTypeMask = mediumType & smallType;
-    static const uintptr_t smallOrMediumSmallTypeMask = smallType ^ mediumType; // Only valid if object is known to be small or medium.
+    static const uintptr_t typeMask = (superChunkSize - 1) & ~((superChunkSize / 2) - 1); // 2 taggable chunks
+    static const uintptr_t largeMask = typeMask & (superChunkSize + largeChunkOffset);
+    static const uintptr_t smallMask = typeMask & (superChunkSize + smallChunkOffset);
 
     static const size_t deallocatorLogCapacity = 256;
     static const size_t bumpRangeCacheCapacity = 3;
@@ -104,7 +94,7 @@ namespace Sizes {
 
     inline size_t sizeClass(size_t size)
     {
-        static const size_t sizeClassMask = (mediumMax / alignment) - 1;
+        static const size_t sizeClassMask = (smallMax / alignment) - 1;
         return mask((size - 1) / alignment, sizeClassMask);
     }
 
index 5f8fa4b..2222c0d 100644 (file)
@@ -27,7 +27,6 @@
 #define SuperChunk_h
 
 #include "LargeChunk.h"
-#include "MediumChunk.h"
 #include "SmallChunk.h"
 
 namespace bmalloc {
@@ -37,7 +36,6 @@ public:
     static SuperChunk* create();
 
     SmallChunk* smallChunk();
-    MediumChunk* mediumChunk();
     LargeChunk* largeChunk();
 
 private:
@@ -53,7 +51,6 @@ inline SuperChunk* SuperChunk::create()
 inline SuperChunk::SuperChunk()
 {
     new (smallChunk()) SmallChunk;
-    new (mediumChunk()) MediumChunk;
     new (largeChunk()) LargeChunk;
 }
 
@@ -63,12 +60,6 @@ inline SmallChunk* SuperChunk::smallChunk()
         reinterpret_cast<char*>(this) + smallChunkOffset);
 }
 
-inline MediumChunk* SuperChunk::mediumChunk()
-{
-    return reinterpret_cast<MediumChunk*>(
-        reinterpret_cast<char*>(this) + mediumChunkOffset);
-}
-
 inline LargeChunk* SuperChunk::largeChunk()
 {
     return reinterpret_cast<LargeChunk*>(
index 6d7aabe..b3dfea5 100644 (file)
@@ -24,7 +24,6 @@
  */
 
 #include "LargeObject.h"
-#include "Line.h"
 #include "PerProcess.h"
 #include "SuperChunk.h"
 #include "VMHeap.h"
@@ -48,10 +47,6 @@ void VMHeap::grow()
     for (auto* it = smallChunk->begin(); it != smallChunk->end(); ++it)
         m_smallPages.push(it);
 
-    MediumChunk* mediumChunk = superChunk->mediumChunk();
-    for (auto* it = mediumChunk->begin(); it != mediumChunk->end(); ++it)
-        m_mediumPages.push(it);
-
     LargeChunk* largeChunk = superChunk->largeChunk();
     LargeObject result(LargeObject::init(largeChunk).begin());
     BASSERT(result.size() == largeMax);
index 7e5d420..7fb8cf8 100644 (file)
@@ -30,7 +30,6 @@
 #include "FixedVector.h"
 #include "LargeChunk.h"
 #include "LargeObject.h"
-#include "MediumChunk.h"
 #include "Range.h"
 #include "SegregatedFreeList.h"
 #include "SmallChunk.h"
@@ -51,42 +50,30 @@ class VMHeap {
 public:
     VMHeap();
 
-    SmallPage* allocateSmallPage();
-    MediumPage* allocateMediumPage();
+    SmallPage* allocateSmallPage(std::lock_guard<StaticMutex>&);
     LargeObject allocateLargeObject(size_t);
     LargeObject allocateLargeObject(size_t, size_t, size_t);
 
     void deallocateSmallPage(std::unique_lock<StaticMutex>&, SmallPage*);
-    void deallocateMediumPage(std::unique_lock<StaticMutex>&, MediumPage*);
     void deallocateLargeObject(std::unique_lock<StaticMutex>&, LargeObject);
 
 private:
     void grow();
 
     Vector<SmallPage*> m_smallPages;
-    Vector<MediumPage*> m_mediumPages;
     SegregatedFreeList m_largeObjects;
 #if BOS(DARWIN)
     Zone m_zone;
 #endif
 };
 
-inline SmallPage* VMHeap::allocateSmallPage()
+inline SmallPage* VMHeap::allocateSmallPage(std::lock_guard<StaticMutex>& lock)
 {
     if (!m_smallPages.size())
         grow();
 
     SmallPage* page = m_smallPages.pop();
-    vmAllocatePhysicalPages(page->begin()->begin(), vmPageSize);
-    return page;
-}
-
-inline MediumPage* VMHeap::allocateMediumPage()
-{
-    if (!m_mediumPages.size())
-        grow();
-
-    MediumPage* page = m_mediumPages.pop();
+    page->setHasFreeLines(lock, true);
     vmAllocatePhysicalPages(page->begin()->begin(), vmPageSize);
     return page;
 }
@@ -124,15 +111,6 @@ inline void VMHeap::deallocateSmallPage(std::unique_lock<StaticMutex>& lock, Sma
     m_smallPages.push(page);
 }
 
-inline void VMHeap::deallocateMediumPage(std::unique_lock<StaticMutex>& lock, MediumPage* page)
-{
-    lock.unlock();
-    vmDeallocatePhysicalPages(page->begin()->begin(), vmPageSize);
-    lock.lock();
-    
-    m_mediumPages.push(page);
-}
-
 inline void VMHeap::deallocateLargeObject(std::unique_lock<StaticMutex>& lock, LargeObject largeObject)
 {
     // Multiple threads might scavenge concurrently, meaning that new merging opportunities