bmalloc: support aligned allocation
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 21 Jan 2015 22:49:45 +0000 (22:49 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 21 Jan 2015 22:49:45 +0000 (22:49 +0000)
https://bugs.webkit.org/show_bug.cgi?id=140732

Reviewed by Andreas Kling.

PerformanceTests:

* MallocBench/MallocBench.xcodeproj/project.pbxproj:
* MallocBench/MallocBench/Benchmark.cpp:
* MallocBench/MallocBench/memalign.cpp:
(test):
(benchmark_memalign): Added a test for specific interesting memalign values.

* MallocBench/MallocBench/stress_aligned.cpp: Added.
(benchmark_stress_aligned):
* MallocBench/MallocBench/stress_aligned.h: Added. Added a stress test
for arbitrary memalign values.

Source/bmalloc:

* bmalloc/Allocator.cpp:
(bmalloc::Allocator::allocate): New function for aligned allocation.

Small and medium requests just allocate and free until they find an
aligned pointer. This is slightly inefficient in the worst case, but
still constant-time with little-to-no space overhead.

Large requests use a new API that requires the client to specify both
its ideal size and alignment, and the worst-case size you would have to
allocate in order to produce some interior pointer of the requested size
and alignment. We put the burden of this calculation on the client
because it simplifies things if we guarantee that allocation won't fail.

XLarge requests are easy: we just forward them to vmAllocate, which
already supported aligned requests.

* bmalloc/BoundaryTag.h:
* bmalloc/BoundaryTagInlines.h:
(bmalloc::BoundaryTag::mergeLeft):
(bmalloc::BoundaryTag::mergeRight):
(bmalloc::BoundaryTag::merge):
(bmalloc::BoundaryTag::deallocate):
(bmalloc::BoundaryTag::split):
(bmalloc::BoundaryTag::allocate): No behavior change here. I just
refactored the interface to remove some reference out parameters in
order to clarify what changes and what doesn't.

* bmalloc/Heap.cpp:
(bmalloc::Heap::allocateXLarge): Added an alignment API.

(bmalloc::Heap::allocateLarge):
* bmalloc/Heap.h: Added an alignment API. I split out allocateLarge into
a few variants, so aligned and unaligned allocation could share some code.

* bmalloc/SegregatedFreeList.cpp:
(bmalloc::SegregatedFreeList::take):
* bmalloc/SegregatedFreeList.h: Changed to use a separate, explicit API
for aligned allocation. It turns out that the aligned path is pretty
different, since it ends up searching for two potential ways to satisfy
an allocation: either large enough and aligned, or large enough to split
into something not aligned and something large enough and aligned.

* bmalloc/VMAllocate.h:
(bmalloc::vmAllocate): Switched alignment to come before size because
that's how the memalign API specifies it.

* bmalloc/VMHeap.h:
(bmalloc::VMHeap::allocateLargeRange): Added an alignment API.

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

16 files changed:
PerformanceTests/ChangeLog
PerformanceTests/MallocBench/MallocBench.xcodeproj/project.pbxproj
PerformanceTests/MallocBench/MallocBench/Benchmark.cpp
PerformanceTests/MallocBench/MallocBench/memalign.cpp
PerformanceTests/MallocBench/MallocBench/stress_aligned.cpp [new file with mode: 0644]
PerformanceTests/MallocBench/MallocBench/stress_aligned.h [new file with mode: 0644]
Source/bmalloc/ChangeLog
Source/bmalloc/bmalloc/Allocator.cpp
Source/bmalloc/bmalloc/BoundaryTag.h
Source/bmalloc/bmalloc/BoundaryTagInlines.h
Source/bmalloc/bmalloc/Heap.cpp
Source/bmalloc/bmalloc/Heap.h
Source/bmalloc/bmalloc/SegregatedFreeList.cpp
Source/bmalloc/bmalloc/SegregatedFreeList.h
Source/bmalloc/bmalloc/VMAllocate.h
Source/bmalloc/bmalloc/VMHeap.h

index 38ad3f1..978963b 100644 (file)
@@ -1,3 +1,21 @@
+2015-01-21  Geoffrey Garen  <ggaren@apple.com>
+
+        bmalloc: support aligned allocation
+        https://bugs.webkit.org/show_bug.cgi?id=140732
+
+        Reviewed by Andreas Kling.
+
+        * MallocBench/MallocBench.xcodeproj/project.pbxproj:
+        * MallocBench/MallocBench/Benchmark.cpp:
+        * MallocBench/MallocBench/memalign.cpp:
+        (test):
+        (benchmark_memalign): Added a test for specific interesting memalign values.
+
+        * MallocBench/MallocBench/stress_aligned.cpp: Added.
+        (benchmark_stress_aligned):
+        * MallocBench/MallocBench/stress_aligned.h: Added. Added a stress test
+        for arbitrary memalign values.
+
 2015-01-16  Geoffrey Garen  <ggaren@apple.com>
 
         bmalloc: added the tiniest bit of testing for aligned allocation
index a6ad2a7..e6f8980 100644 (file)
@@ -34,6 +34,7 @@
                14CC393C18EA812B004AFE34 /* libmbmalloc.dylib in Frameworks */ = {isa = PBXBuildFile; fileRef = 14CC393818EA811F004AFE34 /* libmbmalloc.dylib */; settings = {ATTRIBUTES = (Required, ); }; };
                14CC393F18EA8184004AFE34 /* mbmalloc.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14CC391C18EA6759004AFE34 /* mbmalloc.cpp */; };
                14CE4A6017BD355800288DAA /* big.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14CE4A5E17BD355800288DAA /* big.cpp */; };
+               14D0BFF31A6F4D3B00109F31 /* stress_aligned.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14D0BFF11A6F4D3B00109F31 /* stress_aligned.cpp */; };
                14D6322E1A69BE0B00A8F84F /* memalign.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14D6322C1A69BE0B00A8F84F /* memalign.cpp */; };
                14E11932177ECC8B003A8D15 /* CPUCount.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14E11930177ECC8B003A8D15 /* CPUCount.cpp */; };
                14FCA36119A7C917001CFDA9 /* stress.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14FCA35F19A7C917001CFDA9 /* stress.cpp */; };
                14CC393818EA811F004AFE34 /* libmbmalloc.dylib */ = {isa = PBXFileReference; explicitFileType = "compiled.mach-o.dylib"; includeInIndex = 0; path = libmbmalloc.dylib; sourceTree = BUILT_PRODUCTS_DIR; };
                14CE4A5E17BD355800288DAA /* big.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = big.cpp; path = MallocBench/big.cpp; sourceTree = "<group>"; };
                14CE4A5F17BD355800288DAA /* big.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = big.h; path = MallocBench/big.h; sourceTree = "<group>"; };
+               14D0BFF11A6F4D3B00109F31 /* stress_aligned.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = stress_aligned.cpp; path = MallocBench/stress_aligned.cpp; sourceTree = "<group>"; };
+               14D0BFF21A6F4D3B00109F31 /* stress_aligned.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = stress_aligned.h; path = MallocBench/stress_aligned.h; sourceTree = "<group>"; };
                14D6322C1A69BE0B00A8F84F /* memalign.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = memalign.cpp; path = MallocBench/memalign.cpp; sourceTree = "<group>"; };
                14D6322D1A69BE0B00A8F84F /* memalign.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = memalign.h; path = MallocBench/memalign.h; sourceTree = "<group>"; };
                14E11930177ECC8B003A8D15 /* CPUCount.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CPUCount.cpp; sourceTree = "<group>"; };
                                1447AE8C18FB584200B3D7FF /* reddit.ops */,
                                14FCA35F19A7C917001CFDA9 /* stress.cpp */,
                                14FCA36019A7C917001CFDA9 /* stress.h */,
+                               14D0BFF11A6F4D3B00109F31 /* stress_aligned.cpp */,
+                               14D0BFF21A6F4D3B00109F31 /* stress_aligned.h */,
                                1447AE9818FB59D900B3D7FF /* theverge_memory_warning.ops */,
                                1447AE8D18FB584200B3D7FF /* theverge.cpp */,
                                1447AE8E18FB584200B3D7FF /* theverge.h */,
                                14976EC8177E3649006B819A /* list.cpp in Sources */,
                                14976ECC177E3C87006B819A /* CommandLine.cpp in Sources */,
                                1447AE9218FB584200B3D7FF /* theverge.cpp in Sources */,
+                               14D0BFF31A6F4D3B00109F31 /* stress_aligned.cpp in Sources */,
                                1451FAED18B14B7100DB6D47 /* medium.cpp in Sources */,
                                14C5009318403DA0007A531D /* Interpreter.cpp in Sources */,
                                1447AE9118FB584200B3D7FF /* reddit.cpp in Sources */,
index 2b7eb8d..701c3b0 100644 (file)
@@ -38,6 +38,7 @@
 #include "reddit.h"
 #include "realloc.h"
 #include "stress.h"
+#include "stress_aligned.h"
 #include "theverge.h"
 #include "tree.h"
 #include <dispatch/dispatch.h>
@@ -78,6 +79,7 @@ static const BenchmarkPair benchmarkPairs[] = {
     { "reddit", benchmark_reddit },
     { "reddit_memory_warning", benchmark_reddit_memory_warning },
     { "stress", benchmark_stress },
+    { "stress_aligned", benchmark_stress_aligned },
     { "theverge", benchmark_theverge },
     { "theverge_memory_warning", benchmark_theverge_memory_warning },
     { "tree_allocate", benchmark_tree_allocate },
index 8a4ee35..74835c5 100644 (file)
 
 #include "mbmalloc.h"
 
-void benchmark_memalign(bool isParallel)
+void test(size_t alignment, size_t size)
 {
-    {
-        size_t alignment = 128;
-        size_t size = 8;
-        void* result = mbmemalign(alignment, size);
+    void* result = mbmemalign(alignment, size);
 
-        assert(result);
-        assert(((uintptr_t)result & (alignment - 1)) == 0);
-        
-        mbfree(result, size);
-    }
+    assert(result);
+    assert(!((uintptr_t)result & (alignment - 1)));
     
-    {
-        size_t alignment = 2048 * 1024 * 1024;
-        size_t size = 8;
-        void* result = mbmemalign(alignment, size);
+    mbfree(result, size);
+}
 
-        assert(result);
-        assert(((uintptr_t)result & (alignment - 1)) == 0);
-        
-        mbfree(result, size);
+void benchmark_memalign(bool isParallel)
+{
+    for (size_t alignment = 2; alignment < 4096; alignment *= 2) {
+        for (size_t size = 0; size < 4096; ++size)
+            test(alignment, size);
     }
+
+    test(1 * 1024 * 1024, 8);
+    test(8 * 1024 * 1024, 8);
+    test(32 * 1024 * 1024, 8);
+    test(64 * 1024 * 1024, 8);
+    test(1 * 1024 * 1024, 8 * 1024 * 1024);
+    test(1 * 1024 * 1024, 16 * 1024 * 1024);
 }
diff --git a/PerformanceTests/MallocBench/MallocBench/stress_aligned.cpp b/PerformanceTests/MallocBench/MallocBench/stress_aligned.cpp
new file mode 100644 (file)
index 0000000..c896952
--- /dev/null
@@ -0,0 +1,177 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "Benchmark.h"
+#include "CPUCount.h"
+#include "stress_aligned.h"
+#include <array>
+#include <chrono>
+#include <cmath>
+#include <cstdlib>
+#include <memory>
+#include <stddef.h>
+#include <vector>
+
+#include "mbmalloc.h"
+
+namespace {
+
+static const size_t kB = 1024;
+static const size_t MB = kB * kB;
+
+struct Object {
+    Object(void* pointer, size_t size, long uuid)
+        : pointer(pointer)
+        , size(size)
+        , uuid(uuid)
+    {
+    }
+
+    void* pointer;
+    size_t size;
+    long uuid;
+};
+
+class SizeStream {
+public:
+    SizeStream()
+        : m_state(Small)
+        , m_count(0)
+    {
+    }
+
+    size_t next()
+    {
+        switch (m_state) {
+        case Small: {
+            if (++m_count == smallCount) {
+                m_state = Medium;
+                m_count = 0;
+            }
+            return random() % smallMax;
+        }
+
+        case Medium: {
+            if (++m_count == mediumCount) {
+                m_state = Large;
+                m_count = 0;
+            }
+            return random() % mediumMax;
+        }
+
+        case Large: {
+            if (++m_count == largeCount) {
+                m_state = Small;
+                m_count = 0;
+            }
+            return random() % largeMax;
+        }
+        }
+    }
+
+private:
+    static const size_t smallCount = 1000;
+    static const size_t smallMax = 16 * kB;
+
+    static const size_t mediumCount = 100;
+    static const size_t mediumMax = 512 * kB;
+    
+    static const size_t largeCount = 10;
+    static const size_t largeMax = 4 * MB;
+
+    enum { Small, Medium, Large } m_state;
+    size_t m_count;
+};
+
+Object allocate(size_t alignment, size_t size)
+{
+    Object object(mbmemalign(alignment, size), size, random());
+    if ((uintptr_t)object.pointer & (alignment - 1))
+        abort();
+    for (size_t i = 0; i < size / sizeof(long); ++i)
+        (static_cast<long*>(object.pointer))[i] = object.uuid;
+    return object;
+}
+
+void deallocate(const Object& object)
+{
+    for (size_t i = 0; i < object.size / sizeof(long); ++i) {
+        if ((static_cast<long*>(object.pointer))[i] != object.uuid)
+            abort();
+    }
+
+    mbfree(object.pointer, object.size);
+}
+
+size_t randomAlignment()
+{
+    switch (random() % 32) {
+    case 0:
+        return pow(2, random() % 26);
+    default:
+        return pow(2, random() % 14);
+    }
+}
+
+}
+
+void benchmark_stress_aligned(bool isParallel)
+{
+    const size_t heapSize = 100 * MB;
+    const size_t churnSize = .05 * heapSize;
+    const size_t churnCount = 100;
+    
+    srandom(1); // For consistency between runs.
+
+    std::vector<Object> objects;
+    
+    SizeStream sizeStream;
+    
+    size_t size = 0;
+    for (size_t remaining = heapSize; remaining; remaining -= std::min(remaining, size)) {
+        size = sizeStream.next();
+        objects.push_back(allocate(randomAlignment(), size));
+    }
+    
+    for (size_t i = 0; i < churnCount; ++i) {
+        std::vector<Object> objectsToFree;
+        for (size_t remaining = churnSize; remaining; remaining -= std::min(remaining, size)) {
+            size = sizeStream.next();
+            Object object = allocate(randomAlignment(), size);
+
+            size_t index = random() % objects.size();
+            objectsToFree.push_back(objects[index]);
+            objects[index] = object;
+        }
+
+        for (auto& object : objectsToFree)
+            deallocate(object);
+        
+        mbscavenge();
+    }
+    
+    for (auto& object : objects)
+        mbfree(object.pointer, object.size);
+}
diff --git a/PerformanceTests/MallocBench/MallocBench/stress_aligned.h b/PerformanceTests/MallocBench/MallocBench/stress_aligned.h
new file mode 100644 (file)
index 0000000..c064750
--- /dev/null
@@ -0,0 +1,31 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef stress_aligned_h
+#define stress_aligned_h
+
+void benchmark_stress_aligned(bool isParallel);
+
+#endif // stress_aligned_h
index 9b59ca1..c9f2e5f 100644 (file)
@@ -1,3 +1,59 @@
+2015-01-21  Geoffrey Garen  <ggaren@apple.com>
+
+        bmalloc: support aligned allocation
+        https://bugs.webkit.org/show_bug.cgi?id=140732
+
+        Reviewed by Andreas Kling.
+
+        * bmalloc/Allocator.cpp:
+        (bmalloc::Allocator::allocate): New function for aligned allocation.
+
+        Small and medium requests just allocate and free until they find an
+        aligned pointer. This is slightly inefficient in the worst case, but
+        still constant-time with little-to-no space overhead.
+
+        Large requests use a new API that requires the client to specify both
+        its ideal size and alignment, and the worst-case size you would have to
+        allocate in order to produce some interior pointer of the requested size
+        and alignment. We put the burden of this calculation on the client
+        because it simplifies things if we guarantee that allocation won't fail.
+
+        XLarge requests are easy: we just forward them to vmAllocate, which
+        already supported aligned requests.
+
+        * bmalloc/BoundaryTag.h:
+        * bmalloc/BoundaryTagInlines.h:
+        (bmalloc::BoundaryTag::mergeLeft):
+        (bmalloc::BoundaryTag::mergeRight):
+        (bmalloc::BoundaryTag::merge):
+        (bmalloc::BoundaryTag::deallocate):
+        (bmalloc::BoundaryTag::split):
+        (bmalloc::BoundaryTag::allocate): No behavior change here. I just
+        refactored the interface to remove some reference out parameters in
+        order to clarify what changes and what doesn't.
+
+        * bmalloc/Heap.cpp:
+        (bmalloc::Heap::allocateXLarge): Added an alignment API.
+
+        (bmalloc::Heap::allocateLarge):
+        * bmalloc/Heap.h: Added an alignment API. I split out allocateLarge into
+        a few variants, so aligned and unaligned allocation could share some code.
+
+        * bmalloc/SegregatedFreeList.cpp:
+        (bmalloc::SegregatedFreeList::take):
+        * bmalloc/SegregatedFreeList.h: Changed to use a separate, explicit API
+        for aligned allocation. It turns out that the aligned path is pretty
+        different, since it ends up searching for two potential ways to satisfy
+        an allocation: either large enough and aligned, or large enough to split
+        into something not aligned and something large enough and aligned.
+
+        * bmalloc/VMAllocate.h:
+        (bmalloc::vmAllocate): Switched alignment to come before size because
+        that's how the memalign API specifies it.
+
+        * bmalloc/VMHeap.h:
+        (bmalloc::VMHeap::allocateLargeRange): Added an alignment API.
+
 2015-01-20  Geoffrey Garen  <ggaren@apple.com>
 
         bmalloc: a little bit of cleanup
index 9ea3b3c..ed573dc 100644 (file)
@@ -52,14 +52,45 @@ Allocator::~Allocator()
 
 void* Allocator::allocate(size_t alignment, size_t size)
 {
+    BASSERT(isPowerOfTwo(alignment));
+
     if (!m_isBmallocEnabled) {
         void* result = nullptr;
         posix_memalign(&result, alignment, size);
         return result;
     }
     
-    BASSERT(isPowerOfTwo(alignment));
-    return nullptr;
+    if (size <= smallMax && alignment <= smallLineSize) {
+        size_t alignmentMask = alignment - 1;
+        while (void* p = allocate(size)) {
+            if (!test(p, alignmentMask))
+                return p;
+            m_deallocator.deallocate(p);
+        }
+    }
+
+    if (size <= mediumMax && alignment <= mediumLineSize) {
+        size = std::max(size, smallMax + Sizes::alignment);
+        size_t alignmentMask = alignment - 1;
+        while (void* p = allocate(size)) {
+            if (!test(p, alignmentMask))
+                return p;
+            m_deallocator.deallocate(p);
+        }
+    }
+
+    size = std::max(largeMin, roundUpToMultipleOf<largeAlignment>(size));
+    alignment = roundUpToMultipleOf<largeAlignment>(alignment);
+    size_t unalignedSize = largeMin + alignment + size;
+    if (unalignedSize <= largeMax && alignment <= largeChunkSize / 2) {
+        std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
+        return PerProcess<Heap>::getFastCase()->allocateLarge(lock, alignment, size, unalignedSize);
+    }
+
+    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);
 }
 
 void* Allocator::reallocate(void* object, size_t newSize)
index 8d1bd92..761fd3f 100644 (file)
@@ -41,7 +41,7 @@ class BoundaryTag {
 public:
     static Range init(LargeChunk*);
     static Range deallocate(void*);
-    static void allocate(size_t, Range&, Range& leftover, bool& hasPhysicalPages);
+    static void allocate(const Range&, size_t, Range& leftover, bool& hasPhysicalPages);
     static unsigned compactBegin(const Range&);
 
     bool isFree() { return m_isFree; }
@@ -72,10 +72,10 @@ private:
     static_assert((1 << compactBeginBits) - 1 >= largeMin / largeAlignment, "compactBegin must be encodable in a BoundaryTag.");
     static_assert((1 << sizeBits) - 1 >= largeMax, "largeMax must be encodable in a BoundaryTag.");
 
-    static void split(BeginTag*, size_t, EndTag*&, Range&, Range& leftover);
-    static void mergeLeft(EndTag*& prev, BeginTag*&, Range&, bool& hasPhysicalPages);
-    static void mergeRight(EndTag*&, BeginTag*& next, Range&, bool& hasPhysicalPages);
-    static void merge(BeginTag*&, EndTag*&, Range&);
+    static void split(const Range&, size_t, BeginTag*, EndTag*&, Range& leftover);
+    static Range mergeLeft(const Range&, BeginTag*&, EndTag* prev, bool& hasPhysicalPages);
+    static Range mergeRight(const Range&, EndTag*&, BeginTag* next, bool& hasPhysicalPages);
+    static Range merge(const Range&, BeginTag*&, EndTag*&);
 
     bool m_isFree: 1;
     bool m_isEnd: 1;
index a10cf78..5ddf9f0 100644 (file)
@@ -105,56 +105,59 @@ inline Range BoundaryTag::init(LargeChunk* chunk)
     return range;
 }
 
-inline void BoundaryTag::mergeLeft(EndTag*& prev, BeginTag*& beginTag, Range& range, bool& hasPhysicalPages)
+inline Range BoundaryTag::mergeLeft(const Range& range, BeginTag*& beginTag, EndTag* prev, bool& hasPhysicalPages)
 {
     Range left(range.begin() - prev->size(), prev->size());
+    Range merged(left.begin(), left.size() + range.size());
 
     hasPhysicalPages &= prev->hasPhysicalPages();
 
-    range = Range(left.begin(), left.size() + range.size());
-
     prev->clear();
     beginTag->clear();
 
-    beginTag = LargeChunk::beginTag(range.begin());
+    beginTag = LargeChunk::beginTag(merged.begin());
+    return merged;
 }
 
-inline void BoundaryTag::mergeRight(EndTag*& endTag, BeginTag*& next, Range& range, bool& hasPhysicalPages)
+inline Range BoundaryTag::mergeRight(const Range& range, EndTag*& endTag, BeginTag* next, bool& hasPhysicalPages)
 {
     Range right(range.end(), next->size());
+    Range merged(range.begin(), range.size() + right.size());
 
     hasPhysicalPages &= next->hasPhysicalPages();
 
-    range = Range(range.begin(), range.size() + right.size());
-
     endTag->clear();
     next->clear();
 
-    endTag = LargeChunk::endTag(range.begin(), range.size());
+    endTag = LargeChunk::endTag(merged.begin(), merged.size());
+    return merged;
 }
 
-INLINE void BoundaryTag::merge(BeginTag*& beginTag, EndTag*& endTag, Range& range)
+INLINE Range BoundaryTag::merge(const Range& range, BeginTag*& beginTag, EndTag*& endTag)
 {
     EndTag* prev = beginTag->prev();
     BeginTag* next = endTag->next();
     bool hasPhysicalPages = beginTag->hasPhysicalPages();
 
     validate(prev, range, next);
+    
+    Range merged = range;
 
     if (prev->isFree())
-        mergeLeft(prev, beginTag, range, hasPhysicalPages);
+        merged = mergeLeft(merged, beginTag, prev, hasPhysicalPages);
 
     if (next->isFree())
-        mergeRight(endTag, next, range, hasPhysicalPages);
+        merged = mergeRight(merged, endTag, next, hasPhysicalPages);
 
-    beginTag->setRange(range);
+    beginTag->setRange(merged);
     beginTag->setFree(true);
     beginTag->setHasPhysicalPages(hasPhysicalPages);
 
     if (endTag != static_cast<BoundaryTag*>(beginTag))
         *endTag = *beginTag;
 
-    validate(beginTag->prev(), range, endTag->next());
+    validate(beginTag->prev(), merged, endTag->next());
+    return merged;
 }
 
 inline Range BoundaryTag::deallocate(void* object)
@@ -164,19 +167,17 @@ inline Range BoundaryTag::deallocate(void* object)
 
     Range range(object, beginTag->size());
     EndTag* endTag = LargeChunk::endTag(range.begin(), range.size());
-    merge(beginTag, endTag, range);
-    
-    return range;
+    return merge(range, beginTag, endTag);
 }
 
-INLINE void BoundaryTag::split(BeginTag* beginTag, size_t size, EndTag*& endTag, Range& range, Range& leftover)
+INLINE void BoundaryTag::split(const Range& range, size_t size, BeginTag* beginTag, EndTag*& endTag, Range& leftover)
 {
     leftover = Range(range.begin() + size, range.size() - size);
-    range = Range(range.begin(), size);
+    Range split(range.begin(), size);
 
-    beginTag->setRange(range);
+    beginTag->setRange(split);
 
-    EndTag* splitEndTag = LargeChunk::endTag(range.begin(), size);
+    EndTag* splitEndTag = LargeChunk::endTag(split.begin(), size);
     if (splitEndTag != static_cast<BoundaryTag*>(beginTag))
         *splitEndTag = *beginTag;
 
@@ -188,13 +189,13 @@ INLINE void BoundaryTag::split(BeginTag* beginTag, size_t size, EndTag*& endTag,
     if (leftoverBeginTag != static_cast<BoundaryTag*>(endTag))
         *endTag = *leftoverBeginTag;
 
-    validate(beginTag->prev(), range, leftoverBeginTag);
+    validate(beginTag->prev(), split, leftoverBeginTag);
     validate(leftoverBeginTag->prev(), leftover, endTag->next());
 
     endTag = splitEndTag;
 }
 
-INLINE void BoundaryTag::allocate(size_t size, Range& range, Range& leftover, bool& hasPhysicalPages)
+INLINE void BoundaryTag::allocate(const Range& range, size_t size, Range& leftover, bool& hasPhysicalPages)
 {
     BeginTag* beginTag = LargeChunk::beginTag(range.begin());
     EndTag* endTag = LargeChunk::endTag(range.begin(), range.size());
@@ -203,7 +204,7 @@ INLINE void BoundaryTag::allocate(size_t size, Range& range, Range& leftover, bo
     validate(beginTag->prev(), range, endTag->next());
 
     if (range.size() - size > largeMin)
-        split(beginTag, size, endTag, range, leftover);
+        split(range, size, beginTag, endTag, leftover);
 
     hasPhysicalPages = beginTag->hasPhysicalPages();
 
index df8c4d3..95022cd 100644 (file)
@@ -319,15 +319,24 @@ void Heap::deallocateMediumLine(std::lock_guard<StaticMutex>& lock, MediumLine*
     }
 }
 
-void* Heap::allocateXLarge(std::lock_guard<StaticMutex>&, size_t size)
+void* Heap::allocateXLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t size)
 {
+    BASSERT(isPowerOfTwo(alignment));
+    BASSERT(alignment >= xLargeAlignment);
+    BASSERT(size == roundUpToMultipleOf<xLargeAlignment>(size));
+
     m_isAllocatingPages = true;
 
-    void* result = vmAllocate(size, superChunkSize);
+    void* result = vmAllocate(alignment, size);
     m_xLargeRanges.push(Range(result, size));
     return result;
 }
 
+void* Heap::allocateXLarge(std::lock_guard<StaticMutex>& lock, size_t size)
+{
+    return allocateXLarge(lock, superChunkSize, size);
+}
+
 Range Heap::findXLarge(std::lock_guard<StaticMutex>&, void* object)
 {
     for (auto& range : m_xLargeRanges) {
@@ -355,28 +364,73 @@ void Heap::deallocateXLarge(std::unique_lock<StaticMutex>& lock, void* object)
     }
 }
 
-void* Heap::allocateLarge(std::lock_guard<StaticMutex>&, size_t size)
+void Heap::allocateLarge(std::lock_guard<StaticMutex>&, const Range& range, size_t size, Range& leftover)
+{
+    bool hasPhysicalPages;
+    BoundaryTag::allocate(range, size, leftover, hasPhysicalPages);
+
+    if (!hasPhysicalPages)
+        vmAllocatePhysicalPagesSloppy(range.begin(), range.size());
+}
+
+void* Heap::allocateLarge(std::lock_guard<StaticMutex>& lock, const Range& range, size_t size)
+{
+    Range leftover;
+    allocateLarge(lock, range, size, leftover);
+
+    if (!!leftover)
+        m_largeRanges.insert(leftover);
+    
+    return range.begin();
+}
+
+void* Heap::allocateLarge(std::lock_guard<StaticMutex>& lock, size_t size)
 {
     BASSERT(size <= largeMax);
     BASSERT(size >= largeMin);
+    BASSERT(size == roundUpToMultipleOf<largeAlignment>(size));
     
     m_isAllocatingPages = true;
 
     Range range = m_largeRanges.take(size);
     if (!range)
         range = m_vmHeap.allocateLargeRange(size);
-    
-    Range leftover;
-    bool hasPhysicalPages;
-    BoundaryTag::allocate(size, range, leftover, hasPhysicalPages);
 
-    if (!!leftover)
-        m_largeRanges.insert(leftover);
-    
-    if (!hasPhysicalPages)
-        vmAllocatePhysicalPagesSloppy(range.begin(), range.size());
+    return allocateLarge(lock, range, size);
+}
 
-    return range.begin();
+void* Heap::allocateLarge(std::lock_guard<StaticMutex>& lock, size_t alignment, size_t size, size_t unalignedSize)
+{
+    BASSERT(size <= largeMax);
+    BASSERT(size >= largeMin);
+    BASSERT(size == roundUpToMultipleOf<largeAlignment>(size));
+    BASSERT(unalignedSize <= largeMax);
+    BASSERT(unalignedSize >= largeMin);
+    BASSERT(unalignedSize == roundUpToMultipleOf<largeAlignment>(unalignedSize));
+    BASSERT(alignment <= largeChunkSize / 2);
+    BASSERT(alignment >= largeAlignment);
+    BASSERT(isPowerOfTwo(alignment));
+
+    m_isAllocatingPages = true;
+
+    Range range = m_largeRanges.take(alignment, size, unalignedSize);
+    if (!range)
+        range = m_vmHeap.allocateLargeRange(alignment, size, unalignedSize);
+
+    size_t alignmentMask = alignment - 1;
+    if (test(range.begin(), alignmentMask)) {
+        // Because we allocate left-to-right, we must explicitly allocate the
+        // unaligned space on the left in order to break off the aligned space
+        // we want in the middle.
+        Range aligned;
+        size_t unalignedSize = roundUpToMultipleOf(alignment, range.begin() + largeMin) - range.begin();
+        allocateLarge(lock, range, unalignedSize, aligned);
+        allocateLarge(lock, aligned, size);
+        deallocateLarge(lock, range.begin());
+        return aligned.begin();
+    }
+
+    return allocateLarge(lock, range, size);
 }
 
 void Heap::deallocateLarge(std::lock_guard<StaticMutex>&, void* object)
index 6dfedd8..614d63c 100644 (file)
@@ -60,9 +60,11 @@ public:
     void derefMediumLine(std::lock_guard<StaticMutex>&, MediumLine*);
 
     void* allocateLarge(std::lock_guard<StaticMutex>&, size_t);
+    void* allocateLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t, size_t unalignedSize);
     void deallocateLarge(std::lock_guard<StaticMutex>&, void*);
 
     void* allocateXLarge(std::lock_guard<StaticMutex>&, size_t);
+    void* allocateXLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t);
     Range findXLarge(std::lock_guard<StaticMutex>&, void*);
     void deallocateXLarge(std::unique_lock<StaticMutex>&, void*);
 
@@ -79,7 +81,8 @@ private:
     void deallocateSmallLine(std::lock_guard<StaticMutex>&, SmallLine*);
     void deallocateMediumLine(std::lock_guard<StaticMutex>&, MediumLine*);
 
-    void* allocateLarge(Range, size_t);
+    void* allocateLarge(std::lock_guard<StaticMutex>&, const Range&, size_t);
+    void allocateLarge(std::lock_guard<StaticMutex>&, const Range&, size_t, Range& leftover);
     Range allocateLargeChunk();
 
     void splitLarge(BeginTag*, size_t, EndTag*&, Range&);
index 8827803..3a74045 100644 (file)
@@ -81,10 +81,22 @@ Range SegregatedFreeList::takeGreedy(List& list, size_t size)
     return Range();
 }
 
-Range SegregatedFreeList::take(size_t size, size_t alignmentMask)
+Range SegregatedFreeList::take(size_t size)
 {
     for (auto* list = &select(size); list != m_lists.end(); ++list) {
-        Range range = take(*list, size, alignmentMask);
+        Range range = take(*list, size);
+        if (!range)
+            continue;
+
+        return range;
+    }
+    return Range();
+}
+
+Range SegregatedFreeList::take(size_t alignment, size_t size, size_t unalignedSize)
+{
+    for (auto* list = &select(size); list != m_lists.end(); ++list) {
+        Range range = take(*list, alignment, size, unalignedSize);
         if (!range)
             continue;
 
@@ -104,7 +116,7 @@ INLINE auto SegregatedFreeList::select(size_t size) -> List&
     return m_lists[result];
 }
 
-INLINE Range SegregatedFreeList::take(List& list, size_t size, size_t alignmentMask)
+INLINE Range SegregatedFreeList::take(List& list, size_t size)
 {
     Range first;
     size_t end = list.size() > segregatedFreeListSearchDepth ? list.size() - segregatedFreeListSearchDepth : 0;
@@ -122,7 +134,37 @@ INLINE Range SegregatedFreeList::take(List& list, size_t size, size_t alignmentM
         if (range.size() < size)
             continue;
 
-        if (test(range.begin(), alignmentMask))
+        if (!!first && first < range)
+            continue;
+
+        first = range;
+    }
+    
+    return first;
+}
+
+INLINE Range SegregatedFreeList::take(List& list, size_t alignment, size_t size, size_t unalignedSize)
+{
+    BASSERT(isPowerOfTwo(alignment));
+    size_t alignmentMask = alignment - 1;
+
+    Range first;
+    size_t end = list.size() > segregatedFreeListSearchDepth ? list.size() - segregatedFreeListSearchDepth : 0;
+    for (size_t i = list.size(); i-- > end; ) {
+        Range range = list[i];
+
+        // We don't eagerly remove items when we merge and/or split ranges, so
+        // we need to validate each free list entry before using it.
+        BeginTag* beginTag = LargeChunk::beginTag(range.begin());
+        if (!beginTag->isInFreeList(range)) {
+            list.pop(i);
+            continue;
+        }
+
+        if (range.size() < size)
+            continue;
+
+        if (test(range.begin(), alignmentMask) && range.size() < unalignedSize)
             continue;
 
         if (!!first && first < range)
index f3f3f6c..203e257 100644 (file)
@@ -38,12 +38,18 @@ public:
 
     void insert(const Range&);
 
-    // Returns a reasonable fit for the provided size and optional alignment
-    // mask, or Range() if no fit is found. May return Range() spuriously if
-    // searching takes too long. Incrementally removes stale items from the
-    // free list while searching. Does not eagerly remove the returned range
-    // from the free list.
-    Range take(size_t, size_t alignmentMask = 0);
+    // Returns a reasonable fit for the provided size, or Range() if no fit
+    // is found. May return Range() spuriously if searching takes too long.
+    // Incrementally removes stale items from the free list while searching.
+    // Does not eagerly remove the returned range from the free list.
+    Range take(size_t);
+
+    // Returns a reasonable fit for the provided alignment and size, or
+    // a reasonable fit for the provided unaligned size, or Range() if no fit
+    // is found. May return Range() spuriously if searching takes too long.
+    // Incrementally removes stale items from the free list while searching.
+    // Does not eagerly remove the returned range from the free list.
+    Range take(size_t alignment, size_t, size_t unalignedSize);
 
     // Returns an unreasonable fit for the provided size, or Range() if no fit
     // is found. Never returns Range() spuriously.
@@ -55,7 +61,8 @@ private:
     typedef Vector<Range> List;
 
     List& select(size_t);
-    Range take(List&, size_t, size_t alignmentMask);
+    Range take(List&, size_t);
+    Range take(List&, size_t alignment, size_t, size_t unalignedSize);
     Range takeGreedy(List&, size_t);
 
     std::array<List, 19> m_lists;
index 8016931..9406358 100644 (file)
@@ -83,7 +83,7 @@ inline void vmDeallocate(void* p, size_t vmSize)
 // Allocates vmSize bytes at a specified power-of-two alignment.
 // Use this function to create maskable memory regions.
 
-inline void* vmAllocate(size_t vmSize, size_t vmAlignment)
+inline void* vmAllocate(size_t vmAlignment, size_t vmSize)
 {
     vmValidate(vmSize);
     vmValidate(vmAlignment);
index 99f1a24..1d90e1c 100644 (file)
@@ -48,6 +48,7 @@ public:
     SmallPage* allocateSmallPage();
     MediumPage* allocateMediumPage();
     Range allocateLargeRange(size_t);
+    Range allocateLargeRange(size_t alignment, size_t, size_t unalignedSize);
 
     void deallocateSmallPage(std::unique_lock<StaticMutex>&, SmallPage*);
     void deallocateMediumPage(std::unique_lock<StaticMutex>&, MediumPage*);
@@ -88,6 +89,17 @@ inline Range VMHeap::allocateLargeRange(size_t size)
     return range;
 }
 
+inline Range VMHeap::allocateLargeRange(size_t alignment, size_t size, size_t unalignedSize)
+{
+    Range range = m_largeRanges.take(alignment, size, unalignedSize);
+    if (!range) {
+        allocateSuperChunk();
+        range = m_largeRanges.take(alignment, size, unalignedSize);
+        BASSERT(range);
+    }
+    return range;
+}
+
 inline void VMHeap::deallocateSmallPage(std::unique_lock<StaticMutex>& lock, SmallPage* page)
 {
     lock.unlock();