Unreviewed, rolling in r197174.
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 4 Mar 2016 04:02:25 +0000 (04:02 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 4 Mar 2016 04:02:25 +0000 (04:02 +0000)
https://bugs.webkit.org/show_bug.cgi?id=154762

The right calculation for alignment is actually:

    vmAlignment - getpagesize() + vmSize

instead of:

    vmAlignment - vmPageSize + vmSize

The vmPageSize might be larger than getpagesize().

Restored changeset:

"bmalloc: Added a fast XLarge allocator"
https://bugs.webkit.org/show_bug.cgi?id=154720
http://trac.webkit.org/changeset/197174

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@197545 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 fd797cb..ff2935e 100644 (file)
@@ -1,3 +1,24 @@
+2016-03-03  Geoffrey Garen  <ggaren@apple.com>
+
+        Unreviewed, rolling in r197174.
+        https://bugs.webkit.org/show_bug.cgi?id=154762
+
+        The right calculation for alignment is actually:
+
+            vmAlignment - getpagesize() + vmSize
+
+        instead of:
+
+            vmAlignment - vmPageSize + vmSize
+
+        The vmPageSize might be larger than getpagesize().
+
+        Restored changeset:
+
+        "bmalloc: Added a fast XLarge allocator"
+        https://bugs.webkit.org/show_bug.cgi?id=154720
+        http://trac.webkit.org/changeset/197174
+
 2016-02-26  Commit Queue  <commit-queue@webkit.org>
 
         Unreviewed, rolling out r197174.
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..34ac395 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,10 @@ inline void* tryVMAllocate(size_t vmAlignment, size_t vmSize)
     vmValidate(vmSize);
     vmValidate(vmAlignment);
 
-    size_t mappedSize = std::max(vmSize, vmAlignment) + vmAlignment;
+    // We use getpagesize() here instead of vmPageSize because vmPageSize is
+    // allowed to be larger than the OS's true page size.
+
+    size_t mappedSize = vmAlignment - getpagesize() + vmSize;
     char* mapped = static_cast<char*>(tryVMAllocate(mappedSize));
     if (!mapped)
         return nullptr;
@@ -135,6 +115,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