+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
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 */,
#include "reddit.h"
#include "realloc.h"
#include "stress.h"
+#include "stress_aligned.h"
#include "theverge.h"
#include "tree.h"
#include <dispatch/dispatch.h>
{ "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 },
#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);
}
--- /dev/null
+/*
+ * 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);
+}
--- /dev/null
+/*
+ * 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
+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
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)
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; }
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;
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)
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;
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());
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();
}
}
-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) {
}
}
-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)
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*);
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&);
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;
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;
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)
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.
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;
// 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);
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*);
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();
git://git.webkit.org / WebKit-https.git / commitdiff