bmalloc: Added a fast XLarge allocator
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 26 Feb 2016 17:57:37 +0000 (17:57 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 26 Feb 2016 17:57:37 +0000 (17:57 +0000)
https://bugs.webkit.org/show_bug.cgi?id=154720

Reviewed by Andreas Kling.

This is a big speedup for XLarge allocations because it avoids mmap
and page fault churn. It also enables future design changes to handle
a smaller size range on the fast path.

* bmalloc.xcodeproj/project.pbxproj:

* bmalloc/Algorithm.h:
(bmalloc::roundUpToMultipleOf):
(bmalloc::roundDownToMultipleOf): Added a non-constant round down.

* bmalloc/Allocator.cpp:
(bmalloc::Allocator::tryAllocate): XLarge no longer requires the caller
to align things.

(bmalloc::Allocator::allocate): Tweaked the alignment calculation for
clarity. When alignment and largeAlignment are equal, no adjustment
is necessary since all allocations guarantee largeAlignment.

(bmalloc::Allocator::reallocate): Updated for interface change.

Note that the new interface fixes some concurrency bugs. The old code
kept an iterator into the XLarge allocator across lock drop and acquisition,
which is not cool.

(bmalloc::Allocator::allocateXLarge): XLarge no longer requires the caller
to align things.

* bmalloc/Heap.cpp:
(bmalloc::Heap::scavengeXLargeObjects): Added scavenging for XLarge.

(bmalloc::Heap::allocateXLarge):

(bmalloc::Heap::splitAndAllocate): Split XLarge objects to xLargeAlignment.

(bmalloc::Heap::tryAllocateXLarge):
(bmalloc::Heap::xLargeSize):
(bmalloc::Heap::shrinkXLarge):
(bmalloc::Heap::deallocateXLarge): Allocate from our map before going
to the OS.

(bmalloc::Heap::findXLarge): Deleted.

* bmalloc/Heap.h:

* bmalloc/LargeObject.h:
(bmalloc::LargeObject::split):

* bmalloc/ObjectType.h:
(bmalloc::isXLarge): Give XLarge objects an explicit alignment for clarity.

* bmalloc/Range.h:
(bmalloc::Range::size):
(bmalloc::Range::operator!):
(bmalloc::Range::operator bool):
(bmalloc::Range::operator<):
(bmalloc::canMerge):
(bmalloc::merge): Some helpers that were useful in writing this patch.

* bmalloc/Sizes.h:

* bmalloc/SortedVector.h: Added.
(bmalloc::SortedVector::Bucket::Bucket):
(bmalloc::SortedVector::Bucket::operator<):
(bmalloc::SortedVector::iterator::iterator):
(bmalloc::SortedVector::iterator::operator++):
(bmalloc::SortedVector::iterator::operator!=):
(bmalloc::SortedVector::iterator::operator*):
(bmalloc::SortedVector::iterator::operator->):
(bmalloc::SortedVector::iterator::skipDeletedBuckets):
(bmalloc::SortedVector::begin):
(bmalloc::SortedVector::end):
(bmalloc::SortedVector<T>::insert):
(bmalloc::SortedVector<T>::find):
(bmalloc::SortedVector<T>::get):
(bmalloc::SortedVector<T>::take):
(bmalloc::SortedVector<T>::shrinkToFit): A simple abstraction for keeping
a sorted vector. Insertion is average amortized log(n) because we keep
deleted buckets that we can reuse.

This is better than a tree because we get better locality, less memory
use, and simpler code. Also, trees require a node memory allocator, and
implementing a memory allocator in a memory allocator is no fun.

Arguably we should use a hash table instead. But that's more code, and
sorted vector has other nice properties that we might want to take
adavantage of in the future.

* bmalloc/VMAllocate.h:
(bmalloc::tryVMAllocate): Fixed an inaccuracy in the alignment calculation
here. This code was sort of trying to enforce the alignment that the
XLarge allocator enforces -- but it's better to enforce that alignment
there.

The right calculation is:

    vmAlignment - vmPageSize + vmSize

because the worst case is when you are aligned to 0 + vmPageSize, and
you must walk forward vmAlignment - vmPageSize to reach the next
vmAlignment.

(bmalloc::tryVMExtend): Deleted. No need to go back to the OS for VM
since we manage our own.

* bmalloc/VMHeap.cpp:
(bmalloc::VMHeap::allocateLargeChunk): Updated for clarity. When we
grow the large heap we know that grown region is where the next allocation
will take place, so we return it directly instead of pushing it to the
free list.

This fixes a subtle bug where an overly conservative aligned allocation
algorithm can fail to allocate at all when it grows the heap.

* bmalloc/VMHeap.h:
(bmalloc::VMHeap::allocateLargeObject): Ditto.
(bmalloc::VMHeap::allocateLargeObject): Ditto.

* bmalloc/VMState.h:
(bmalloc::merge): Added a helper.

* bmalloc/Vector.h:
(bmalloc::Vector::begin):
(bmalloc::Vector::end):
(bmalloc::Vector::size):
(bmalloc::Vector::capacity):
(bmalloc::Vector::last):
(bmalloc::Vector::pop):
(bmalloc::Vector<T>::push):
(bmalloc::Vector<T>::pop):
(bmalloc::Vector<T>::shrink): Use a proper iterator API to play nice
with std algorithms.

(bmalloc::Vector<T>::insert): New function required by SortedVector.

(bmalloc::Vector<T>::reallocateBuffer):
(bmalloc::Vector<T>::shrinkCapacity): Allow for shrinking back all the way
to 0 because that's what shrinkToFit wants.
(bmalloc::Vector<T>::growCapacity):
(bmalloc::Vector<T>::shrinkToFit):

* bmalloc/XLargeMap.cpp: Added. Helper data structure for managing XLarge
objects. We have enough granularity in our metadata to represent any
kind of address range.

We store free ranges in a flat vector because most programs have very
few individual free XLarge ranges. (They usually merge.)

We store allocated ranges in a sorted vector because programs might
allocate lots of XLarge ranges. For example, if the XLarge minimum is
128kB, and you have a 1GB process, that's 8192 ranges. Linear scan would
examine 8192 items but binary search only 13.

Empirically, this is 1.5X faster than our current large allocator if you
modify MallocBench/big to allocate XLarge objects and not to initialize
objects and you allocate 128kB-256kB objects in a 1GB address space.

(bmalloc::XLargeMap::takeFree): Be careful about overflow in this function
because we support super huge pointers, alignments, and sizes.

(bmalloc::XLargeMap::addFree): Merge eagerly on free because the cost
of missing an XLarge opportunity is catastrophic. Also, I discovered
by experiment that any allocator that doesn't merge eagerly can create
lots of subtle opportunities for snowballing fragmentation, as
fragmentation in range A forces you to chop up range B, and so on.

We allocate "first fit" (allocating the lowest address) because someone
wrote a paper once that said that it's the best algorithm to combat
fragmentation (even though worst case fragmentation is unavoidable
regardless of algorithm).

(bmalloc::XLargeMap::addAllocated):
(bmalloc::XLargeMap::getAllocated):
(bmalloc::XLargeMap::takeAllocated):
(bmalloc::XLargeMap::shrinkToFit):
(bmalloc::XLargeMap::takePhysical):
(bmalloc::XLargeMap::addVirtual):
* bmalloc/XLargeMap.h: Added.
(bmalloc::XLargeMap::Allocation::operator<):

* bmalloc/XLargeRange.h: Added.
(bmalloc::XLargeRange::XLargeRange):
(bmalloc::XLargeRange::vmState):
(bmalloc::XLargeRange::setVMState):
(bmalloc::canMerge):
(bmalloc::merge):
(bmalloc::XLargeRange::split): Helper for tracking VMState in a range.

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

20 files changed:
Source/bmalloc/CMakeLists.txt
Source/bmalloc/ChangeLog
Source/bmalloc/bmalloc.xcodeproj/project.pbxproj
Source/bmalloc/bmalloc/Algorithm.h
Source/bmalloc/bmalloc/Allocator.cpp
Source/bmalloc/bmalloc/Heap.cpp
Source/bmalloc/bmalloc/Heap.h
Source/bmalloc/bmalloc/LargeObject.h
Source/bmalloc/bmalloc/ObjectType.h
Source/bmalloc/bmalloc/Range.h
Source/bmalloc/bmalloc/Sizes.h
Source/bmalloc/bmalloc/SortedVector.h [new file with mode: 0644]
Source/bmalloc/bmalloc/VMAllocate.h
Source/bmalloc/bmalloc/VMHeap.cpp
Source/bmalloc/bmalloc/VMHeap.h
Source/bmalloc/bmalloc/VMState.h
Source/bmalloc/bmalloc/Vector.h
Source/bmalloc/bmalloc/XLargeMap.cpp [new file with mode: 0644]
Source/bmalloc/bmalloc/XLargeMap.h [new file with mode: 0644]
Source/bmalloc/bmalloc/XLargeRange.h [new file with mode: 0644]

index 560737e..f6a4929 100644 (file)
@@ -13,6 +13,7 @@ set(bmalloc_SOURCES
     bmalloc/SegregatedFreeList.cpp
     bmalloc/StaticMutex.cpp
     bmalloc/VMHeap.cpp
+    bmalloc/XLargeMap.cpp
     bmalloc/mbmalloc.cpp
 )
 
index ecfc371..3ec0b82 100644 (file)
@@ -1,3 +1,197 @@
+2016-02-25  Geoffrey Garen  <ggaren@apple.com>
+
+        bmalloc: Added a fast XLarge allocator
+        https://bugs.webkit.org/show_bug.cgi?id=154720
+
+        Reviewed by Andreas Kling.
+
+        This is a big speedup for XLarge allocations because it avoids mmap
+        and page fault churn. It also enables future design changes to handle
+        a smaller size range on the fast path.
+
+        * bmalloc.xcodeproj/project.pbxproj:
+
+        * bmalloc/Algorithm.h:
+        (bmalloc::roundUpToMultipleOf):
+        (bmalloc::roundDownToMultipleOf): Added a non-constant round down.
+
+        * bmalloc/Allocator.cpp:
+        (bmalloc::Allocator::tryAllocate): XLarge no longer requires the caller
+        to align things.
+
+        (bmalloc::Allocator::allocate): Tweaked the alignment calculation for
+        clarity. When alignment and largeAlignment are equal, no adjustment
+        is necessary since all allocations guarantee largeAlignment.
+
+        (bmalloc::Allocator::reallocate): Updated for interface change.
+
+        Note that the new interface fixes some concurrency bugs. The old code
+        kept an iterator into the XLarge allocator across lock drop and acquisition,
+        which is not cool.
+
+        (bmalloc::Allocator::allocateXLarge): XLarge no longer requires the caller
+        to align things.
+
+        * bmalloc/Heap.cpp:
+        (bmalloc::Heap::scavengeXLargeObjects): Added scavenging for XLarge.
+
+        (bmalloc::Heap::allocateXLarge):
+
+        (bmalloc::Heap::splitAndAllocate): Split XLarge objects to xLargeAlignment.
+
+        (bmalloc::Heap::tryAllocateXLarge):
+        (bmalloc::Heap::xLargeSize):
+        (bmalloc::Heap::shrinkXLarge):
+        (bmalloc::Heap::deallocateXLarge): Allocate from our map before going
+        to the OS.
+
+        (bmalloc::Heap::findXLarge): Deleted.
+
+        * bmalloc/Heap.h:
+
+        * bmalloc/LargeObject.h:
+        (bmalloc::LargeObject::split):
+
+        * bmalloc/ObjectType.h:
+        (bmalloc::isXLarge): Give XLarge objects an explicit alignment for clarity.
+
+        * bmalloc/Range.h:
+        (bmalloc::Range::size):
+        (bmalloc::Range::operator!):
+        (bmalloc::Range::operator bool):
+        (bmalloc::Range::operator<):
+        (bmalloc::canMerge):
+        (bmalloc::merge): Some helpers that were useful in writing this patch.
+
+        * bmalloc/Sizes.h:
+
+        * bmalloc/SortedVector.h: Added.
+        (bmalloc::SortedVector::Bucket::Bucket):
+        (bmalloc::SortedVector::Bucket::operator<):
+        (bmalloc::SortedVector::iterator::iterator):
+        (bmalloc::SortedVector::iterator::operator++):
+        (bmalloc::SortedVector::iterator::operator!=):
+        (bmalloc::SortedVector::iterator::operator*):
+        (bmalloc::SortedVector::iterator::operator->):
+        (bmalloc::SortedVector::iterator::skipDeletedBuckets):
+        (bmalloc::SortedVector::begin):
+        (bmalloc::SortedVector::end):
+        (bmalloc::SortedVector<T>::insert):
+        (bmalloc::SortedVector<T>::find):
+        (bmalloc::SortedVector<T>::get):
+        (bmalloc::SortedVector<T>::take):
+        (bmalloc::SortedVector<T>::shrinkToFit): A simple abstraction for keeping
+        a sorted vector. Insertion is average amortized log(n) because we keep
+        deleted buckets that we can reuse.
+
+        This is better than a tree because we get better locality, less memory
+        use, and simpler code. Also, trees require a node memory allocator, and
+        implementing a memory allocator in a memory allocator is no fun.
+
+        Arguably we should use a hash table instead. But that's more code, and
+        sorted vector has other nice properties that we might want to take
+        adavantage of in the future.
+
+        * bmalloc/VMAllocate.h:
+        (bmalloc::tryVMAllocate): Fixed an inaccuracy in the alignment calculation
+        here. This code was sort of trying to enforce the alignment that the
+        XLarge allocator enforces -- but it's better to enforce that alignment
+        there.
+
+        The right calculation is:
+
+            vmAlignment - vmPageSize + vmSize
+
+        because the worst case is when you are aligned to 0 + vmPageSize, and
+        you must walk forward vmAlignment - vmPageSize to reach the next
+        vmAlignment.
+
+        (bmalloc::tryVMExtend): Deleted. No need to go back to the OS for VM
+        since we manage our own.
+
+        * bmalloc/VMHeap.cpp:
+        (bmalloc::VMHeap::allocateLargeChunk): Updated for clarity. When we
+        grow the large heap we know that grown region is where the next allocation
+        will take place, so we return it directly instead of pushing it to the
+        free list.
+
+        This fixes a subtle bug where an overly conservative aligned allocation
+        algorithm can fail to allocate at all when it grows the heap.
+
+        * bmalloc/VMHeap.h:
+        (bmalloc::VMHeap::allocateLargeObject): Ditto.
+        (bmalloc::VMHeap::allocateLargeObject): Ditto.
+
+        * bmalloc/VMState.h:
+        (bmalloc::merge): Added a helper.
+
+        * bmalloc/Vector.h:
+        (bmalloc::Vector::begin):
+        (bmalloc::Vector::end):
+        (bmalloc::Vector::size):
+        (bmalloc::Vector::capacity):
+        (bmalloc::Vector::last):
+        (bmalloc::Vector::pop):
+        (bmalloc::Vector<T>::push):
+        (bmalloc::Vector<T>::pop):
+        (bmalloc::Vector<T>::shrink): Use a proper iterator API to play nice
+        with std algorithms.
+
+        (bmalloc::Vector<T>::insert): New function required by SortedVector.
+
+        (bmalloc::Vector<T>::reallocateBuffer):
+        (bmalloc::Vector<T>::shrinkCapacity): Allow for shrinking back all the way
+        to 0 because that's what shrinkToFit wants.
+        (bmalloc::Vector<T>::growCapacity):
+        (bmalloc::Vector<T>::shrinkToFit):
+
+        * bmalloc/XLargeMap.cpp: Added. Helper data structure for managing XLarge
+        objects. We have enough granularity in our metadata to represent any
+        kind of address range.
+
+        We store free ranges in a flat vector because most programs have very
+        few individual free XLarge ranges. (They usually merge.)
+
+        We store allocated ranges in a sorted vector because programs might
+        allocate lots of XLarge ranges. For example, if the XLarge minimum is
+        128kB, and you have a 1GB process, that's 8192 ranges. Linear scan would
+        examine 8192 items but binary search only 13.
+
+        Empirically, this is 1.5X faster than our current large allocator if you
+        modify MallocBench/big to allocate XLarge objects and not to initialize
+        objects and you allocate 128kB-256kB objects in a 1GB address space.
+
+        (bmalloc::XLargeMap::takeFree): Be careful about overflow in this function
+        because we support super huge pointers, alignments, and sizes.
+
+        (bmalloc::XLargeMap::addFree): Merge eagerly on free because the cost
+        of missing an XLarge opportunity is catastrophic. Also, I discovered
+        by experiment that any allocator that doesn't merge eagerly can create
+        lots of subtle opportunities for snowballing fragmentation, as
+        fragmentation in range A forces you to chop up range B, and so on.
+
+        We allocate "first fit" (allocating the lowest address) because someone
+        wrote a paper once that said that it's the best algorithm to combat
+        fragmentation (even though worst case fragmentation is unavoidable
+        regardless of algorithm).
+
+        (bmalloc::XLargeMap::addAllocated):
+        (bmalloc::XLargeMap::getAllocated):
+        (bmalloc::XLargeMap::takeAllocated):
+        (bmalloc::XLargeMap::shrinkToFit):
+        (bmalloc::XLargeMap::takePhysical):
+        (bmalloc::XLargeMap::addVirtual):
+        * bmalloc/XLargeMap.h: Added.
+        (bmalloc::XLargeMap::Allocation::operator<):
+
+        * bmalloc/XLargeRange.h: Added.
+        (bmalloc::XLargeRange::XLargeRange):
+        (bmalloc::XLargeRange::vmState):
+        (bmalloc::XLargeRange::setVMState):
+        (bmalloc::canMerge):
+        (bmalloc::merge):
+        (bmalloc::XLargeRange::split): Helper for tracking VMState in a range.
+
 2016-02-23  Dan Bernstein  <mitz@apple.com>
 
         [Xcode] Linker errors display mangled names, but no longer should
index fab5af8..81670f1 100644 (file)
@@ -21,6 +21,9 @@
                1440AFCD1A9527AF00837FAA /* Zone.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 1440AFCC1A9527AF00837FAA /* Zone.cpp */; };
                1448C30018F3754600502839 /* mbmalloc.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 1448C2FF18F3754300502839 /* mbmalloc.cpp */; };
                1448C30118F3754C00502839 /* bmalloc.h in Headers */ = {isa = PBXBuildFile; fileRef = 1448C2FE18F3754300502839 /* bmalloc.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               144C07F41C7B70260051BB6A /* XLargeMap.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 144C07F21C7B70260051BB6A /* XLargeMap.cpp */; };
+               144C07F51C7B70260051BB6A /* XLargeMap.h in Headers */ = {isa = PBXBuildFile; fileRef = 144C07F31C7B70260051BB6A /* XLargeMap.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               146041E71C7FF2EF00E9F94E /* SortedVector.h in Headers */ = {isa = PBXBuildFile; fileRef = 146041E61C7FF2EF00E9F94E /* SortedVector.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14895D911A3A319C0006235D /* Environment.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14895D8F1A3A319C0006235D /* Environment.cpp */; };
                14895D921A3A319C0006235D /* Environment.h in Headers */ = {isa = PBXBuildFile; fileRef = 14895D901A3A319C0006235D /* Environment.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14C6216F1A9A9A6200E72293 /* LargeObject.h in Headers */ = {isa = PBXBuildFile; fileRef = 14C6216E1A9A9A6200E72293 /* LargeObject.h */; settings = {ATTRIBUTES = (Private, ); }; };
@@ -52,6 +55,7 @@
                14DD78CE18F48D7500950702 /* Syscall.h in Headers */ = {isa = PBXBuildFile; fileRef = 1417F64F18B7280C0076FA3F /* Syscall.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14DD78CF18F48D7500950702 /* Vector.h in Headers */ = {isa = PBXBuildFile; fileRef = 1479E21217A1A255006D4E9D /* Vector.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14DD78D018F48D7500950702 /* VMAllocate.h in Headers */ = {isa = PBXBuildFile; fileRef = 1479E21417A1A63E006D4E9D /* VMAllocate.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               14EB79EA1C7C1BC4005E834F /* XLargeRange.h in Headers */ = {isa = PBXBuildFile; fileRef = 14EB79E81C7C1BC4005E834F /* XLargeRange.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14F271C318EA3978008C152F /* Allocator.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 145F6855179DC8CA00D65598 /* Allocator.cpp */; };
                14F271C418EA397B008C152F /* Cache.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 144469E417A46BFE00F9EA1D /* Cache.cpp */; };
                14F271C518EA397E008C152F /* Deallocator.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 145F6859179DC90200D65598 /* Deallocator.cpp */; };
                14446A0717A61FA400F9EA1D /* PerProcess.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = PerProcess.h; path = bmalloc/PerProcess.h; sourceTree = "<group>"; };
                1448C2FE18F3754300502839 /* bmalloc.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; name = bmalloc.h; path = bmalloc/bmalloc.h; sourceTree = "<group>"; };
                1448C2FF18F3754300502839 /* mbmalloc.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; name = mbmalloc.cpp; path = bmalloc/mbmalloc.cpp; sourceTree = "<group>"; };
+               144C07F21C7B70260051BB6A /* XLargeMap.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = XLargeMap.cpp; path = bmalloc/XLargeMap.cpp; sourceTree = "<group>"; };
+               144C07F31C7B70260051BB6A /* XLargeMap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = XLargeMap.h; path = bmalloc/XLargeMap.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>"; };
                145F685A179DC90200D65598 /* Deallocator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; lineEnding = 0; name = Deallocator.h; path = bmalloc/Deallocator.h; sourceTree = "<group>"; xcLanguageSpecificationIdentifier = xcode.lang.objcpp; };
                145F6874179DF84100D65598 /* Sizes.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Sizes.h; path = bmalloc/Sizes.h; sourceTree = "<group>"; };
                145F6878179E3A4400D65598 /* Range.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; lineEnding = 0; name = Range.h; path = bmalloc/Range.h; sourceTree = "<group>"; xcLanguageSpecificationIdentifier = xcode.lang.objcpp; };
+               146041E61C7FF2EF00E9F94E /* SortedVector.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = SortedVector.h; path = bmalloc/SortedVector.h; sourceTree = "<group>"; };
                146BEE1E18C841C50002D5A2 /* SegregatedFreeList.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = SegregatedFreeList.h; path = bmalloc/SegregatedFreeList.h; sourceTree = "<group>"; };
                146BEE2118C845AE0002D5A2 /* SegregatedFreeList.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = SegregatedFreeList.cpp; path = bmalloc/SegregatedFreeList.cpp; sourceTree = "<group>"; };
                1479E21217A1A255006D4E9D /* Vector.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; lineEnding = 0; name = Vector.h; path = bmalloc/Vector.h; sourceTree = "<group>"; xcLanguageSpecificationIdentifier = xcode.lang.objcpp; };
                14D9DB4517F2447100EAAB79 /* FixedVector.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; lineEnding = 0; name = FixedVector.h; path = bmalloc/FixedVector.h; sourceTree = "<group>"; xcLanguageSpecificationIdentifier = xcode.lang.objcpp; };
                14DA320C18875B09007269E0 /* Heap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Heap.h; path = bmalloc/Heap.h; sourceTree = "<group>"; };
                14DA320E18875D9F007269E0 /* Heap.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = Heap.cpp; path = bmalloc/Heap.cpp; sourceTree = "<group>"; };
+               14EB79E81C7C1BC4005E834F /* XLargeRange.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = XLargeRange.h; path = bmalloc/XLargeRange.h; sourceTree = "<group>"; };
                14F271BE18EA3963008C152F /* libbmalloc.a */ = {isa = PBXFileReference; explicitFileType = archive.ar; includeInIndex = 0; path = libbmalloc.a; sourceTree = BUILT_PRODUCTS_DIR; };
 /* End PBXFileReference section */
 
                        name = api;
                        sourceTree = "<group>";
                };
+               144C07F71C7B707D0051BB6A /* heap: xlarge */ = {
+                       isa = PBXGroup;
+                       children = (
+                               144C07F21C7B70260051BB6A /* XLargeMap.cpp */,
+                               144C07F31C7B70260051BB6A /* XLargeMap.h */,
+                               14EB79E81C7C1BC4005E834F /* XLargeRange.h */,
+                       );
+                       name = "heap: xlarge";
+                       sourceTree = "<group>";
+               };
                145F6836179DC45F00D65598 = {
                        isa = PBXGroup;
                        children = (
                                14D9DB4D17F2865C00EAAB79 /* cache */,
                                147AAA9C18CE6010002201E4 /* heap: large */,
                                147AAA9A18CE5FD3002201E4 /* heap: small */,
+                               144C07F71C7B707D0051BB6A /* heap: xlarge */,
                                14D9DB4E17F2866E00EAAB79 /* heap */,
                                14D9DB4F17F2868900EAAB79 /* stdlib */,
                                14B650C418F39F4800751968 /* Configurations */,
                                14446A0717A61FA400F9EA1D /* PerProcess.h */,
                                144469FD17A61F1F00F9EA1D /* PerThread.h */,
                                145F6878179E3A4400D65598 /* Range.h */,
+                               146041E61C7FF2EF00E9F94E /* SortedVector.h */,
                                143CB81A19022BC900B16A45 /* StaticMutex.cpp */,
                                143CB81B19022BC900B16A45 /* StaticMutex.h */,
                                1417F64F18B7280C0076FA3F /* Syscall.h */,
                                14DD789018F48CEB00950702 /* Sizes.h in Headers */,
                                14DD78C718F48D7500950702 /* BAssert.h in Headers */,
                                14DD78D018F48D7500950702 /* VMAllocate.h in Headers */,
+                               14EB79EA1C7C1BC4005E834F /* XLargeRange.h in Headers */,
                                1440AFC91A95142400837FAA /* SuperChunk.h in Headers */,
                                143EF9B01A9FABF6004F5C77 /* FreeList.h in Headers */,
                                14DD78CE18F48D7500950702 /* Syscall.h in Headers */,
                                14DD78C518F48D7500950702 /* Algorithm.h in Headers */,
                                14DD78BD18F48D6B00950702 /* SmallPage.h in Headers */,
                                14DD788E18F48CCD00950702 /* BoundaryTag.h in Headers */,
+                               146041E71C7FF2EF00E9F94E /* SortedVector.h in Headers */,
                                14DD78C818F48D7500950702 /* FixedVector.h in Headers */,
+                               144C07F51C7B70260051BB6A /* XLargeMap.h in Headers */,
                                14D2CD9B1AA12CFB00770440 /* VMState.h in Headers */,
                                14DD78BC18F48D6B00950702 /* SmallLine.h in Headers */,
                                14DD789818F48D4A00950702 /* Allocator.h in Headers */,
                                143EF9AF1A9FABF6004F5C77 /* FreeList.cpp in Sources */,
                                14F271C718EA3990008C152F /* Heap.cpp in Sources */,
                                14F271C918EA3990008C152F /* VMHeap.cpp in Sources */,
+                               144C07F41C7B70260051BB6A /* XLargeMap.cpp in Sources */,
                                14F271C818EA3990008C152F /* ObjectType.cpp in Sources */,
                                14F271C518EA397E008C152F /* Deallocator.cpp in Sources */,
                                14F271C418EA397B008C152F /* Cache.cpp in Sources */,
index 269866c..30ed141 100644 (file)
@@ -75,10 +75,16 @@ template<size_t divisor, typename T> inline constexpr T roundUpToMultipleOf(T x)
     return roundUpToMultipleOf(divisor, x);
 }
 
+template<typename T> inline T roundDownToMultipleOf(size_t divisor, T x)
+{
+    BASSERT(isPowerOfTwo(divisor));
+    return reinterpret_cast<T>(mask(reinterpret_cast<uintptr_t>(x), ~(divisor - 1ul)));
+}
+
 template<size_t divisor, typename T> inline constexpr T roundDownToMultipleOf(T x)
 {
     static_assert(isPowerOfTwo(divisor), "'divisor' must be a power of two.");
-    return reinterpret_cast<T>(mask(reinterpret_cast<uintptr_t>(x), ~(divisor - 1ul)));
+    return roundDownToMultipleOf(divisor, x);
 }
 
 template<typename T> void divideRoundingUp(T numerator, T denominator, T& quotient, T& remainder)
index ca8cb26..23514eb 100644 (file)
@@ -61,7 +61,7 @@ void* Allocator::tryAllocate(size_t size)
 
     if (size <= xLargeMax) {
         std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
-        return PerProcess<Heap>::getFastCase()->tryAllocateXLarge(lock, superChunkSize, roundUpToMultipleOf<xLargeAlignment>(size));
+        return PerProcess<Heap>::getFastCase()->tryAllocateXLarge(lock, alignment, size);
     }
 
     return nullptr;
@@ -90,7 +90,7 @@ void* Allocator::allocate(size_t alignment, size_t size)
     if (size <= largeMax && alignment <= largeMax) {
         size = std::max(largeMin, roundUpToMultipleOf<largeAlignment>(size));
         alignment = roundUpToMultipleOf<largeAlignment>(alignment);
-        size_t unalignedSize = largeMin + alignment + size;
+        size_t unalignedSize = largeMin + alignment - largeAlignment + size;
         if (unalignedSize <= largeMax && alignment <= largeChunkSize / 2) {
             std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
             return PerProcess<Heap>::getFastCase()->allocateLarge(lock, alignment, size, unalignedSize);
@@ -98,8 +98,6 @@ void* Allocator::allocate(size_t alignment, size_t size)
     }
 
     if (size <= xLargeMax && alignment <= xLargeMax) {
-        size = roundUpToMultipleOf<xLargeAlignment>(size);
-        alignment = std::max(superChunkSize, alignment);
         std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
         return PerProcess<Heap>::getFastCase()->allocateXLarge(lock, alignment, size);
     }
@@ -144,36 +142,15 @@ void* Allocator::reallocate(void* object, size_t newSize)
             break;
 
         std::unique_lock<StaticMutex> lock(PerProcess<Heap>::mutex());
-        Range& range = PerProcess<Heap>::getFastCase()->findXLarge(lock, object);
-        oldSize = range.size();
-
-        newSize = roundUpToMultipleOf<xLargeAlignment>(newSize);
+        oldSize = PerProcess<Heap>::getFastCase()->xLargeSize(lock, object);
 
         if (newSize == oldSize)
             return object;
 
         if (newSize < oldSize && newSize > largeMax) {
-            newSize = roundUpToMultipleOf<xLargeAlignment>(newSize);
-            if (oldSize - newSize >= xLargeAlignment) {
-                lock.unlock();
-                vmDeallocate(static_cast<char*>(object) + newSize, oldSize - newSize);
-                lock.lock();
-
-                range = Range(object, newSize);
-            }
+            PerProcess<Heap>::getFastCase()->shrinkXLarge(lock, Range(object, oldSize), newSize);
             return object;
         }
-
-        if (newSize > oldSize) {
-            lock.unlock();
-            bool wasExtended = tryVMExtend(object, oldSize, newSize);
-            lock.lock();
-
-            if (wasExtended) {
-                range = Range(object, newSize);
-                return object;
-            }
-        }
         break;
     }
     }
@@ -229,7 +206,6 @@ NO_INLINE void* Allocator::allocateLarge(size_t size)
 
 NO_INLINE void* Allocator::allocateXLarge(size_t size)
 {
-    size = roundUpToMultipleOf<xLargeAlignment>(size);
     std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
     return PerProcess<Heap>::getFastCase()->allocateXLarge(lock, size);
 }
index 7349d25..3003ffa 100644 (file)
@@ -86,6 +86,7 @@ void Heap::scavenge(std::unique_lock<StaticMutex>& lock, std::chrono::millisecon
 
     scavengeSmallPages(lock, sleepDuration);
     scavengeLargeObjects(lock, sleepDuration);
+    scavengeXLargeObjects(lock, sleepDuration);
 
     sleep(lock, sleepDuration);
 }
@@ -106,6 +107,22 @@ void Heap::scavengeLargeObjects(std::unique_lock<StaticMutex>& lock, std::chrono
     }
 }
 
+void Heap::scavengeXLargeObjects(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
+{
+    while (XLargeRange range = m_xLargeMap.takePhysical()) {
+        lock.unlock();
+        vmDeallocatePhysicalPagesSloppy(range.begin(), range.size());
+        lock.lock();
+        
+        range.setVMState(VMState::Virtual);
+        m_xLargeMap.addVirtual(range);
+
+        waitUntilFalse(lock, sleepDuration, m_isAllocatingPages);
+    }
+
+    m_xLargeMap.shrinkToFit();
+}
+
 void Heap::allocateSmallBumpRanges(std::lock_guard<StaticMutex>& lock, size_t sizeClass, BumpAllocator& allocator, BumpRangeCache& rangeCache)
 {
     BASSERT(!rangeCache.size());
@@ -202,52 +219,6 @@ void Heap::deallocateSmallLine(std::lock_guard<StaticMutex>& lock, SmallLine* li
     m_scavenger.run();
 }
 
-void* Heap::allocateXLarge(std::lock_guard<StaticMutex>& lock, size_t alignment, size_t size)
-{
-    void* result = tryAllocateXLarge(lock, alignment, size);
-    RELEASE_BASSERT(result);
-    return result;
-}
-
-void* Heap::allocateXLarge(std::lock_guard<StaticMutex>& lock, size_t size)
-{
-    return allocateXLarge(lock, superChunkSize, size);
-}
-
-void* Heap::tryAllocateXLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t size)
-{
-    BASSERT(isPowerOfTwo(alignment));
-    BASSERT(alignment >= superChunkSize);
-    BASSERT(size == roundUpToMultipleOf<xLargeAlignment>(size));
-
-    void* result = tryVMAllocate(alignment, size);
-    if (!result)
-        return nullptr;
-    m_xLargeObjects.push(Range(result, size));
-    return result;
-}
-
-Range& Heap::findXLarge(std::unique_lock<StaticMutex>&, void* object)
-{
-    for (auto& range : m_xLargeObjects) {
-        if (range.begin() != object)
-            continue;
-        return range;
-    }
-
-    RELEASE_BASSERT(false);
-    return *static_cast<Range*>(nullptr); // Silence compiler error.
-}
-
-void Heap::deallocateXLarge(std::unique_lock<StaticMutex>& lock, void* object)
-{
-    Range toDeallocate = m_xLargeObjects.pop(&findXLarge(lock, object));
-
-    lock.unlock();
-    vmDeallocate(toDeallocate.begin(), toDeallocate.size());
-    lock.lock();
-}
-
 inline LargeObject& Heap::splitAndAllocate(LargeObject& largeObject, size_t size)
 {
     BASSERT(largeObject.isFree());
@@ -372,4 +343,102 @@ void Heap::deallocateLarge(std::lock_guard<StaticMutex>& lock, void* object)
     deallocateLarge(lock, largeObject);
 }
 
+void* Heap::allocateXLarge(std::lock_guard<StaticMutex>& lock, size_t alignment, size_t size)
+{
+    void* result = tryAllocateXLarge(lock, alignment, size);
+    RELEASE_BASSERT(result);
+    return result;
+}
+
+void* Heap::allocateXLarge(std::lock_guard<StaticMutex>& lock, size_t size)
+{
+    return allocateXLarge(lock, alignment, size);
+}
+
+XLargeRange Heap::splitAndAllocate(XLargeRange& range, size_t alignment, size_t size)
+{
+    XLargeRange prev;
+    XLargeRange next;
+
+    size_t alignmentMask = alignment - 1;
+    if (test(range.begin(), alignmentMask)) {
+        size_t prefixSize = roundUpToMultipleOf(alignment, range.begin()) - range.begin();
+        std::pair<XLargeRange, XLargeRange> pair = range.split(prefixSize);
+        prev = pair.first;
+        range = pair.second;
+    }
+
+    if (range.size() - size >= xLargeAlignment) {
+        size_t alignedSize = roundUpToMultipleOf<xLargeAlignment>(size);
+        std::pair<XLargeRange, XLargeRange> pair = range.split(alignedSize);
+        range = pair.first;
+        next = pair.second;
+    }
+
+    // At this point our range might contain an unused tail fragment. This is
+    // common. We can't allocate the tail fragment because it's aligned to less
+    // than xLargeAlignment. So, we pair the allocation with its tail fragment
+    // in the allocated list. This is an important optimization because it
+    // keeps the free list short, speeding up allocation and merging.
+
+    std::pair<XLargeRange, XLargeRange> allocated = range.split(roundUpToMultipleOf<vmPageSize>(size));
+    if (allocated.first.vmState().hasVirtual()) {
+        vmAllocatePhysicalPagesSloppy(allocated.first.begin(), allocated.first.size());
+        allocated.first.setVMState(VMState::Physical);
+    }
+
+    m_xLargeMap.addAllocated(prev, allocated, next);
+    return allocated.first;
+}
+
+void* Heap::tryAllocateXLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t size)
+{
+    BASSERT(isPowerOfTwo(alignment));
+    BASSERT(alignment < xLargeMax);
+
+    m_isAllocatingPages = true;
+
+    alignment = roundUpToMultipleOf<xLargeAlignment>(alignment);
+
+    XLargeRange range = m_xLargeMap.takeFree(alignment, size);
+    if (!range) {
+        // We allocate VM in aligned multiples to increase the chances that
+        // the OS will provide contiguous ranges that we can merge.
+        size_t alignedSize = roundUpToMultipleOf<xLargeAlignment>(size);
+
+        void* begin = tryVMAllocate(alignment, alignedSize);
+        if (!begin)
+            return nullptr;
+        range = XLargeRange(begin, alignedSize, VMState::Virtual);
+    }
+
+    return splitAndAllocate(range, alignment, size).begin();
+}
+
+size_t Heap::xLargeSize(std::unique_lock<StaticMutex>&, void* object)
+{
+    return m_xLargeMap.getAllocated(object).size();
+}
+
+void Heap::shrinkXLarge(std::unique_lock<StaticMutex>&, const Range& object, size_t newSize)
+{
+    BASSERT(object.size() > newSize);
+
+    if (object.size() - newSize < vmPageSize)
+        return;
+    
+    XLargeRange range = m_xLargeMap.takeAllocated(object.begin());
+    splitAndAllocate(range, xLargeAlignment, newSize);
+
+    m_scavenger.run();
+}
+
+void Heap::deallocateXLarge(std::unique_lock<StaticMutex>&, void* object)
+{
+    XLargeRange range = m_xLargeMap.takeAllocated(object);
+    m_xLargeMap.addFree(range);
+    
+    m_scavenger.run();
+}
+
 } // namespace bmalloc
index 1b2bee3..1007784 100644 (file)
@@ -36,6 +36,7 @@
 #include "SmallPage.h"
 #include "VMHeap.h"
 #include "Vector.h"
+#include "XLargeMap.h"
 #include <array>
 #include <mutex>
 
@@ -61,7 +62,8 @@ public:
     void* allocateXLarge(std::lock_guard<StaticMutex>&, size_t);
     void* allocateXLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t);
     void* tryAllocateXLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t);
-    Range& findXLarge(std::unique_lock<StaticMutex>&, void*);
+    size_t xLargeSize(std::unique_lock<StaticMutex>&, void*);
+    void shrinkXLarge(std::unique_lock<StaticMutex>&, const Range&, size_t newSize);
     void deallocateXLarge(std::unique_lock<StaticMutex>&, void*);
 
     void scavenge(std::unique_lock<StaticMutex>&, std::chrono::milliseconds sleepDuration);
@@ -81,10 +83,13 @@ private:
     void mergeLarge(BeginTag*&, EndTag*&, Range&);
     void mergeLargeLeft(EndTag*&, BeginTag*&, Range&, bool& inVMHeap);
     void mergeLargeRight(EndTag*&, BeginTag*&, Range&, bool& inVMHeap);
-    
+
+    XLargeRange splitAndAllocate(XLargeRange&, size_t alignment, size_t);
+
     void concurrentScavenge();
     void scavengeSmallPages(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
     void scavengeLargeObjects(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
+    void scavengeXLargeObjects(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
 
     std::array<std::array<LineMetadata, smallLineCount>, smallMax / alignment> m_smallLineMetadata;
 
@@ -93,7 +98,8 @@ private:
     Vector<SmallPage*> m_smallPages;
 
     SegregatedFreeList m_largeObjects;
-    Vector<Range> m_xLargeObjects;
+    
+    XLargeMap m_xLargeMap;
 
     bool m_isAllocatingPages;
     AsyncTask<Heap, decltype(&Heap::concurrentScavenge)> m_scavenger;
index 08a4b14..cc0bdb7 100644 (file)
@@ -219,6 +219,7 @@ inline LargeObject LargeObject::merge() const
 
 inline std::pair<LargeObject, LargeObject> LargeObject::split(size_t size) const
 {
+    BASSERT(size <= this->size());
     Range split(begin(), size);
     Range leftover = Range(split.end(), this->size() - size);
     BASSERT(leftover.size() >= largeMin);
index 42093bf..3b5d692 100644 (file)
@@ -42,7 +42,7 @@ inline bool isSmall(void* object)
 
 inline bool isXLarge(void* object)
 {
-    return !test(object, ~superChunkMask);
+    return !test(object, ~xLargeMask);
 }
 
 } // namespace bmalloc
index 1ee6411..7d446f7 100644 (file)
@@ -26,6 +26,7 @@
 #ifndef Range_h
 #define Range_h
 
+#include <algorithm>
 #include <cstddef>
 
 namespace bmalloc {
@@ -49,6 +50,7 @@ public:
     size_t size() const { return m_size; }
     
     bool operator!() const { return !m_size; }
+    explicit operator bool() const { return !!*this; }
     bool operator<(const Range& other) const { return m_begin < other.m_begin; }
 
 private:
@@ -56,6 +58,16 @@ private:
     size_t m_size;
 };
 
+inline bool canMerge(const Range& a, const Range& b)
+{
+    return a.begin() == b.end() || a.end() == b.begin();
+}
+
+inline Range merge(const Range& a, const Range& b)
+{
+    return Range(std::min(a.begin(), b.begin()), a.size() + b.size());
+}
+
 } // namespace bmalloc
 
 #endif // Range_h
index 6b7701d..c59f381 100644 (file)
@@ -73,7 +73,8 @@ namespace Sizes {
     static const size_t largeChunkMetadataSize = 4 * kB; // sizeof(LargeChunk)
     static const size_t largeMax = largeChunkSize - largeChunkMetadataSize;
 
-    static const size_t xLargeAlignment = vmPageSize;
+    static const size_t xLargeAlignment = superChunkSize;
+    static const size_t xLargeMask = ~(xLargeAlignment - 1);
     static const size_t xLargeMax = std::numeric_limits<size_t>::max() - xLargeAlignment; // Make sure that rounding up to xLargeAlignment does not overflow.
 
     static const size_t freeListSearchDepth = 16;
diff --git a/Source/bmalloc/bmalloc/SortedVector.h b/Source/bmalloc/bmalloc/SortedVector.h
new file mode 100644 (file)
index 0000000..bd4c4b7
--- /dev/null
@@ -0,0 +1,169 @@
+/*
+ * Copyright (C) 2016 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 SortedVector_h
+#define SortedVector_h
+
+#include "Vector.h"
+#include <algorithm>
+
+namespace bmalloc {
+
+template<typename T>
+class SortedVector {
+    static_assert(std::is_trivially_destructible<T>::value, "SortedVector must have a trivial destructor.");
+
+    struct Bucket {
+        explicit Bucket(T value)
+            : value(value)
+            , isDeleted(false)
+        {
+        }
+        
+        template<typename U> bool operator<(const U& other) const
+        {
+            return value < other;
+        }
+
+        T value;
+        bool isDeleted;
+    };
+
+public:
+    class iterator : public std::iterator<std::forward_iterator_tag, T> {
+    public:
+        iterator(Bucket* bucket, Bucket* end)
+            : m_bucket(bucket)
+            , m_end(end)
+        {
+            skipDeletedBuckets();
+        }
+        
+        iterator(const iterator& other)
+            : m_bucket(other.m_bucket)
+            , m_end(other.m_end)
+        {
+        }
+
+        iterator& operator++()
+        {
+            BASSERT(m_bucket != m_end);
+            ++m_bucket;
+            skipDeletedBuckets();
+            return *this;
+        }
+
+        bool operator!=(const iterator& other)
+        {
+            return m_bucket != other.m_bucket;
+        }
+
+        T& operator*()
+        {
+            BASSERT(m_bucket < m_end);
+            BASSERT(!m_bucket->isDeleted);
+            return m_bucket->value;
+        }
+
+        T* operator->()  { return &operator*(); }
+
+    private:
+        friend class SortedVector;
+
+        void skipDeletedBuckets()
+        {
+            while (m_bucket != m_end && m_bucket->isDeleted)
+                ++m_bucket;
+        }
+
+        Bucket* m_bucket;
+        Bucket* m_end;
+    };
+
+    iterator begin() { return iterator(m_vector.begin(), m_vector.end()); }
+    iterator end() { return iterator(m_vector.end(), m_vector.end()); }
+
+    void insert(const T&);
+
+    template<typename U> iterator find(const U&);
+    template<typename U> T get(const U&);
+    template<typename U> T take(const U&);
+
+    void shrinkToFit();
+
+private:
+    Vector<Bucket> m_vector;
+};
+
+template<typename T>
+void SortedVector<T>::insert(const T& value)
+{
+    auto it = std::lower_bound(m_vector.begin(), m_vector.end(), value);
+    if (it != m_vector.end() && it->isDeleted) {
+        *it = Bucket(value);
+        return;
+    }
+
+    m_vector.insert(it, Bucket(value));
+}
+
+template<typename T> template<typename U>
+typename SortedVector<T>::iterator SortedVector<T>::find(const U& value)
+{
+    auto it = std::lower_bound(m_vector.begin(), m_vector.end(), value);
+    return iterator(it, m_vector.end());
+}
+
+template<typename T> template<typename U>
+T SortedVector<T>::get(const U& value)
+{
+    return *find(value);
+}
+
+template<typename T> template<typename U>
+T SortedVector<T>::take(const U& value)
+{
+    auto it = find(value);
+    it.m_bucket->isDeleted = true;
+    return it.m_bucket->value;
+}
+
+template<typename T>
+void SortedVector<T>::shrinkToFit()
+{
+    auto isDeleted = [](const Bucket& bucket) {
+        return bucket.isDeleted;
+    };
+
+    auto newEnd = std::remove_if(m_vector.begin(), m_vector.end(), isDeleted);
+    size_t newSize = newEnd - m_vector.begin();
+    m_vector.shrink(newSize);
+
+    m_vector.shrinkToFit();
+}
+
+} // namespace bmalloc
+
+#endif // SortedVector_h
index 0273a0d..5bbb067 100644 (file)
@@ -82,29 +82,6 @@ inline void* tryVMAllocate(size_t vmSize)
     return result;
 }
 
-inline bool tryVMExtend(void* p, size_t vmOldSize, size_t vmNewSize)
-{
-    vmValidate(vmOldSize);
-    vmValidate(vmNewSize);
-    
-    BASSERT(vmOldSize < vmNewSize);
-
-    void* nextAddress = static_cast<char*>(p) + vmOldSize;
-    size_t extentionSize = vmNewSize - vmOldSize;
-
-    void* result = mmap(nextAddress, extentionSize, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, BMALLOC_VM_TAG, 0);
-
-    if (result == MAP_FAILED)
-        return false;
-
-    if (result != nextAddress) {
-        munmap(result, extentionSize);
-        return false;
-    }
-    
-    return true;
-}
-
 inline void* vmAllocate(size_t vmSize)
 {
     void* result = tryVMAllocate(vmSize);
@@ -126,7 +103,7 @@ inline void* tryVMAllocate(size_t vmAlignment, size_t vmSize)
     vmValidate(vmSize);
     vmValidate(vmAlignment);
 
-    size_t mappedSize = std::max(vmSize, vmAlignment) + vmAlignment;
+    size_t mappedSize = vmAlignment - vmPageSize + vmSize;
     char* mapped = static_cast<char*>(tryVMAllocate(mappedSize));
     if (!mapped)
         return nullptr;
@@ -135,6 +112,8 @@ inline void* tryVMAllocate(size_t vmAlignment, size_t vmSize)
     char* aligned = roundUpToMultipleOf(vmAlignment, mapped);
     char* alignedEnd = aligned + vmSize;
     
+    RELEASE_BASSERT(alignedEnd <= mappedEnd);
+    
     if (size_t leftExtra = aligned - mapped)
         vmDeallocate(mapped, leftExtra);
     
index cd673c0..0f9f4dd 100644 (file)
@@ -47,15 +47,14 @@ void VMHeap::allocateSmallChunk(std::lock_guard<StaticMutex>& lock)
         m_smallPages.push(it);
 }
 
-void VMHeap::allocateLargeChunk(std::lock_guard<StaticMutex>& lock)
+LargeObject VMHeap::allocateLargeChunk(std::lock_guard<StaticMutex>& lock)
 {
     if (!m_largeChunks.size())
         allocateSuperChunk(lock);
 
     // We initialize chunks lazily to avoid dirtying their metadata pages.
     LargeChunk* largeChunk = new (m_largeChunks.pop()->largeChunk()) LargeChunk;
-    LargeObject largeObject(largeChunk->begin());
-    m_largeObjects.insert(largeObject);
+    return LargeObject(largeChunk->begin());
 }
 
 void VMHeap::allocateSuperChunk(std::lock_guard<StaticMutex>&)
index abc8c62..649e493 100644 (file)
@@ -59,7 +59,7 @@ public:
     
 private:
     void allocateSmallChunk(std::lock_guard<StaticMutex>&);
-    void allocateLargeChunk(std::lock_guard<StaticMutex>&);
+    LargeObject allocateLargeChunk(std::lock_guard<StaticMutex>&);
     void allocateSuperChunk(std::lock_guard<StaticMutex>&);
 
     Vector<SmallPage*> m_smallPages;
@@ -85,26 +85,20 @@ inline SmallPage* VMHeap::allocateSmallPage(std::lock_guard<StaticMutex>& lock)
 
 inline LargeObject VMHeap::allocateLargeObject(std::lock_guard<StaticMutex>& lock, size_t size)
 {
-    LargeObject largeObject = m_largeObjects.take(size);
-    if (!largeObject) {
-        allocateLargeChunk(lock);
-        largeObject = m_largeObjects.take(size);
-        BASSERT(largeObject);
-    }
-
-    return largeObject;
+    if (LargeObject largeObject = m_largeObjects.take(size))
+        return largeObject;
+
+    BASSERT(size <= largeMax);
+    return allocateLargeChunk(lock);
 }
 
 inline LargeObject VMHeap::allocateLargeObject(std::lock_guard<StaticMutex>& lock, size_t alignment, size_t size, size_t unalignedSize)
 {
-    LargeObject largeObject = m_largeObjects.take(alignment, size, unalignedSize);
-    if (!largeObject) {
-        allocateLargeChunk(lock);
-        largeObject = m_largeObjects.take(alignment, size, unalignedSize);
-        BASSERT(largeObject);
-    }
-
-    return largeObject;
+    if (LargeObject largeObject = m_largeObjects.take(alignment, size, unalignedSize))
+        return largeObject;
+
+    BASSERT(unalignedSize <= largeMax);
+    return allocateLargeChunk(lock);
 }
 
 inline void VMHeap::deallocateSmallPage(std::unique_lock<StaticMutex>& lock, SmallPage* page)
index 3c85367..b87aefe 100644 (file)
@@ -74,6 +74,13 @@ private:
     State m_state;
 };
 
+inline VMState merge(VMState a, VMState b)
+{
+    VMState result(a);
+    result.merge(b);
+    return result;
+}
+
 } // namespace bmalloc
 
 #endif // VMState_h
index 2cda0dd..0959e45 100644 (file)
@@ -40,14 +40,17 @@ template<typename T>
 class Vector {
     static_assert(std::is_trivially_destructible<T>::value, "Vector must have a trivial destructor.");
 public:
+    typedef T* iterator;
+    typedef const T* const_iterator;
+
     Vector(const Vector&) = delete;
     Vector& operator=(const Vector&) = delete;
 
     Vector();
     ~Vector();
 
-    T* begin() { return m_buffer; }
-    T* end() { return m_buffer + m_size; }
+    iterator begin() { return m_buffer; }
+    iterator end() { return m_buffer + m_size; }
 
     size_t size() { return m_size; }
     size_t capacity() { return m_capacity; }
@@ -56,19 +59,23 @@ public:
     T& last() { return m_buffer[m_size - 1]; }
 
     void push(const T&);
-    void push(const T*, const T*);
+
     T pop();
     T pop(size_t);
-    T pop(const T* it) { return pop(it - begin()); }
+    T pop(const_iterator it) { return pop(it - begin()); }
+    
+    void insert(iterator, const T&);
 
     void shrink(size_t);
 
+    void shrinkToFit();
+
 private:
     static const size_t growFactor = 2;
     static const size_t shrinkFactor = 4;
     static const size_t initialCapacity = vmPageSize / sizeof(T);
 
-    void growCapacity(size_t size);
+    void growCapacity();
     void shrinkCapacity();
     void reallocateBuffer(size_t);
 
@@ -103,21 +110,11 @@ template<typename T>
 INLINE void Vector<T>::push(const T& value)
 {
     if (m_size == m_capacity)
-        growCapacity(m_size);
+        growCapacity();
     m_buffer[m_size++] = value;
 }
 
 template<typename T>
-void Vector<T>::push(const T* begin, const T* end)
-{
-    size_t newSize = m_size + (end - begin);
-    if (newSize > m_capacity)
-        growCapacity(newSize);
-    std::memcpy(this->end(), begin, (end - begin) * sizeof(T));
-    m_size = newSize;
-}
-
-template<typename T>
 inline T Vector<T>::pop()
 {
     BASSERT(m_size);
@@ -135,6 +132,20 @@ inline T Vector<T>::pop(size_t i)
 }
 
 template<typename T>
+void Vector<T>::insert(iterator it, const T& value)
+{
+    size_t index = it - begin();
+    size_t moveCount = end() - it;
+
+    if (m_size == m_capacity)
+        growCapacity();
+
+    std::memmove(&m_buffer[index + 1], &m_buffer[index], moveCount * sizeof(T));
+    m_buffer[index] = value;
+    m_size++;
+}
+
+template<typename T>
 inline void Vector<T>::shrink(size_t size)
 {
     BASSERT(size <= m_size);
@@ -147,7 +158,7 @@ template<typename T>
 void Vector<T>::reallocateBuffer(size_t newCapacity)
 {
     size_t vmSize = bmalloc::vmSize(newCapacity * sizeof(T));
-    T* newBuffer = static_cast<T*>(vmAllocate(vmSize));
+    T* newBuffer = vmSize ? static_cast<T*>(vmAllocate(vmSize)) : nullptr;
     if (m_buffer) {
         std::memcpy(newBuffer, m_buffer, m_size * sizeof(T));
         vmDeallocate(m_buffer, bmalloc::vmSize(m_capacity * sizeof(T)));
@@ -165,12 +176,19 @@ NO_INLINE void Vector<T>::shrinkCapacity()
 }
 
 template<typename T>
-NO_INLINE void Vector<T>::growCapacity(size_t size)
+NO_INLINE void Vector<T>::growCapacity()
 {
-    size_t newCapacity = max(initialCapacity, size * growFactor);
+    size_t newCapacity = max(initialCapacity, m_size * growFactor);
     reallocateBuffer(newCapacity);
 }
 
+template<typename T>
+void Vector<T>::shrinkToFit()
+{
+    if (m_size < m_capacity)
+        reallocateBuffer(m_size);
+}
+
 } // namespace bmalloc
 
 #endif // Vector_h
diff --git a/Source/bmalloc/bmalloc/XLargeMap.cpp b/Source/bmalloc/bmalloc/XLargeMap.cpp
new file mode 100644 (file)
index 0000000..a82a04a
--- /dev/null
@@ -0,0 +1,151 @@
+/*
+ * Copyright (C) 2016 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "XLargeMap.h"
+
+namespace bmalloc {
+
+XLargeRange XLargeMap::takeFree(size_t alignment, size_t size)
+{
+    size_t alignmentMask = alignment - 1;
+
+    XLargeRange* candidate = m_free.end();
+    for (XLargeRange* it = m_free.begin(); it != m_free.end(); ++it) {
+        if (it->size() < size)
+            continue;
+
+        if (candidate != m_free.end() && candidate->begin() < it->begin())
+            continue;
+
+        if (test(it->begin(), alignmentMask)) {
+            char* aligned = roundUpToMultipleOf(alignment, it->begin());
+            if (aligned < it->begin()) // Check for overflow.
+                continue;
+
+            char* alignedEnd = aligned + size;
+            if (alignedEnd < aligned) // Check for overflow.
+                continue;
+
+            if (alignedEnd > it->end())
+                continue;
+        }
+
+        candidate = it;
+    }
+    
+    if (candidate == m_free.end())
+        return XLargeRange();
+
+    return m_free.pop(candidate);
+}
+
+void XLargeMap::addFree(const XLargeRange& range)
+{
+    XLargeRange merged = range;
+
+    for (size_t i = 0; i < m_free.size(); ++i) {
+        auto& other = m_free[i];
+
+        if (!canMerge(merged, other))
+            continue;
+
+        merged = merge(merged, m_free.pop(i--));
+    }
+    
+    m_free.push(merged);
+}
+
+void XLargeMap::addAllocated(const XLargeRange& prev, const std::pair<XLargeRange, XLargeRange>& allocated, const XLargeRange& next)
+{
+    if (prev)
+        m_free.push(prev);
+    
+    if (next)
+        m_free.push(next);
+
+    m_allocated.insert({ allocated.first, allocated.second });
+}
+
+XLargeRange XLargeMap::getAllocated(void* object)
+{
+    return m_allocated.find(object)->object;
+}
+
+XLargeRange XLargeMap::takeAllocated(void* object)
+{
+    Allocation allocation = m_allocated.take(object);
+    return merge(allocation.object, allocation.unused);
+}
+
+void XLargeMap::shrinkToFit()
+{
+    m_free.shrinkToFit();
+    m_allocated.shrinkToFit();
+}
+
+XLargeRange XLargeMap::takePhysical() {
+    auto hasPhysical = [](const XLargeRange& range) {
+        return range.vmState().hasPhysical();
+    };
+
+    auto it = std::find_if(m_free.begin(), m_free.end(), hasPhysical);
+    if (it != m_free.end())
+        return m_free.pop(it);
+
+    auto hasUnused = [](const Allocation& allocation) {
+        return allocation.unused && allocation.unused.vmState().hasPhysical();
+    };
+    
+    XLargeRange swapped;
+    auto it2 = std::find_if(m_allocated.begin(), m_allocated.end(), hasUnused);
+    if (it2 != m_allocated.end())
+        std::swap(it2->unused, swapped);
+    
+    return swapped;
+}
+
+void XLargeMap::addVirtual(const XLargeRange& range)
+{
+    auto canMerge = [&range](const Allocation& other) {
+        return other.object.end() == range.begin();
+    };
+
+    if (range.size() < xLargeAlignment) {
+        // This is an unused fragment, so it might belong in the allocated list.
+        auto it = std::find_if(m_allocated.begin(), m_allocated.end(), canMerge);
+        if (it != m_allocated.end()) {
+            BASSERT(!it->unused);
+            it->unused = range;
+            return;
+        }
+
+        // If we didn't find a neighbor in the allocated list, our neighbor must
+        // have been freed. We'll merge with it below.
+    }
+
+    addFree(range);
+}
+
+} // namespace bmalloc
diff --git a/Source/bmalloc/bmalloc/XLargeMap.h b/Source/bmalloc/bmalloc/XLargeMap.h
new file mode 100644 (file)
index 0000000..7a88509
--- /dev/null
@@ -0,0 +1,65 @@
+/*
+ * Copyright (C) 2016 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 XLargeMap_h
+#define XLargeMap_h
+
+#include "SortedVector.h"
+#include "Vector.h"
+#include "XLargeRange.h"
+#include <algorithm>
+
+namespace bmalloc {
+
+class XLargeMap {
+public:
+    void addFree(const XLargeRange&);
+    XLargeRange takeFree(size_t alignment, size_t);
+
+    void addAllocated(const XLargeRange& prev, const std::pair<XLargeRange, XLargeRange>&, const XLargeRange& next);
+    XLargeRange getAllocated(void*);
+    XLargeRange takeAllocated(void*);
+
+    XLargeRange takePhysical();
+    void addVirtual(const XLargeRange&);
+    
+    void shrinkToFit();
+
+private:
+    struct Allocation {
+        bool operator<(const Allocation& other) const { return object < other.object; }
+        bool operator<(void* ptr) const { return object.begin() < ptr; }
+
+        XLargeRange object;
+        XLargeRange unused;
+    };
+
+    Vector<XLargeRange> m_free;
+    SortedVector<Allocation> m_allocated;
+};
+
+} // namespace bmalloc
+
+#endif // XLargeMap_h
diff --git a/Source/bmalloc/bmalloc/XLargeRange.h b/Source/bmalloc/bmalloc/XLargeRange.h
new file mode 100644 (file)
index 0000000..ed7f831
--- /dev/null
@@ -0,0 +1,86 @@
+/*
+ * Copyright (C) 2016 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 XLargeRange_h
+#define XLargeRange_h
+
+#include "VMState.h"
+
+namespace bmalloc {
+
+class XLargeRange : public Range {
+public:
+    XLargeRange()
+        : Range()
+        , m_vmState(VMState::Virtual)
+    {
+    }
+
+    XLargeRange(void* begin, size_t size, VMState vmState)
+        : Range(begin, size)
+        , m_vmState(vmState)
+    {
+    }
+    
+    VMState vmState() const { return m_vmState; }
+    void setVMState(VMState vmState) { m_vmState = vmState; }
+
+    std::pair<XLargeRange, XLargeRange> split(size_t) const;
+
+private:
+    VMState m_vmState;
+};
+
+inline bool canMerge(const XLargeRange& a, const XLargeRange& b)
+{
+    if (a.end() == b.begin())
+        return true;
+    
+    if (b.end() == a.begin())
+        return true;
+    
+    return false;
+}
+
+inline XLargeRange merge(const XLargeRange& a, const XLargeRange& b)
+{
+    return XLargeRange(
+        std::min(a.begin(), b.begin()),
+        a.size() + b.size(),
+        merge(a.vmState(), b.vmState()));
+}
+
+inline std::pair<XLargeRange, XLargeRange> XLargeRange::split(size_t size) const
+{
+    BASSERT(size <= this->size());
+
+    XLargeRange left(begin(), size, vmState());
+    XLargeRange right(left.end(), this->size() - size, vmState());
+    return std::make_pair(left, right);
+}
+
+} // namespace bmalloc
+
+#endif // XLargeRange_h