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 560737ec3f8bd2c9c32b64c34bb7881f24f36c7e..f6a4929eabc4dc4f32d474aec77a3dfb601c167d 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 ecfc371a2d079dfa174cbe380c96939748b08f05..3ec0b82d4557a656dfef5b5fcdcb70cb7437c8cb 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 fab5af8c3234e3f38795520985a1df7877f3c3de..81670f1c662a42747ccadbe98ce4e3bb7e6b2bc2 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 269866c5584bb43b491e4b7ee3c61c8f9a7e3f8e..30ed1412535be9de6ca8d4ebc3e8e90cfbd7aead 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 ca8cb26758b422a45340a049a06242aa8b8c4b8f..23514ebb06dbf019db9194ee4049db99d05fc08d 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 7349d25b403f6842bc35abde7592d058bdc8e67f..3003ffa55600a5cfcb874bd8ffdb1e0d2030e43f 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 1b2bee3267ff8e54e94e2a2cb5ff77004a7f77e5..1007784dc4f58488ccc640491a3bc265c8aa1407 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 08a4b141a84a323009b196884812c4a656f790c8..cc0bdb7d7e2bce6d62263142f2dff78df32fcd0b 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 42093bf68145288b726b98d6c5f44315a9d421d9..3b5d6928a11bdf4698dc6f1c0eeffa6244a44380 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 1ee6411776d89c92ae19dd80bed43c6e26b2877d..7d446f7ee5e9e2cbf76e2b74321432ec709d5e78 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 6b7701def80f9c3410628fbbf4c55010994e8c75..c59f381833f3d5fa831d6eb26859064fe5b97b5b 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 0273a0de603c36411bf45250a532d9c167bdba50..5bbb067800ec6d3c6fd8a0bc3121efea4f5507ce 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 cd673c0b12f8c646d258be63d470171e77667464..0f9f4dd6394ac676a16f4a87bd89f8cd5c7ef536 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 abc8c625e22d2e21275027964d467d40a633ffb0..649e493681581fc6e4273a2d5daa8c9eea196414 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 3c85367f1304b0049e32b5323de59c1fb48b0742..b87aefec646daa86af40282fccb5d795e208ac72 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 2cda0dda2e7ebf75f0270a23008dd8242274b4b0..0959e45cd31a2be956a1d398a0cdb3b535e233de 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,20 +110,10 @@ 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()
 {
@@ -134,6 +131,20 @@ inline T Vector<T>::pop(size_t i)
     return pop();
 }
 
+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)
 {
@@ -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