<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[178861] trunk</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/178861">178861</a></dd>
<dt>Author</dt> <dd>ggaren@apple.com</dd>
<dt>Date</dt> <dd>2015-01-21 14:49:45 -0800 (Wed, 21 Jan 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>bmalloc: support aligned allocation
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.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkPerformanceTestsChangeLog">trunk/PerformanceTests/ChangeLog</a></li>
<li><a href="#trunkPerformanceTestsMallocBenchMallocBenchBenchmarkcpp">trunk/PerformanceTests/MallocBench/MallocBench/Benchmark.cpp</a></li>
<li><a href="#trunkPerformanceTestsMallocBenchMallocBenchmemaligncpp">trunk/PerformanceTests/MallocBench/MallocBench/memalign.cpp</a></li>
<li><a href="#trunkPerformanceTestsMallocBenchMallocBenchxcodeprojprojectpbxproj">trunk/PerformanceTests/MallocBench/MallocBench.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourcebmallocChangeLog">trunk/Source/bmalloc/ChangeLog</a></li>
<li><a href="#trunkSourcebmallocbmallocAllocatorcpp">trunk/Source/bmalloc/bmalloc/Allocator.cpp</a></li>
<li><a href="#trunkSourcebmallocbmallocBoundaryTagh">trunk/Source/bmalloc/bmalloc/BoundaryTag.h</a></li>
<li><a href="#trunkSourcebmallocbmallocBoundaryTagInlinesh">trunk/Source/bmalloc/bmalloc/BoundaryTagInlines.h</a></li>
<li><a href="#trunkSourcebmallocbmallocHeapcpp">trunk/Source/bmalloc/bmalloc/Heap.cpp</a></li>
<li><a href="#trunkSourcebmallocbmallocHeaph">trunk/Source/bmalloc/bmalloc/Heap.h</a></li>
<li><a href="#trunkSourcebmallocbmallocSegregatedFreeListcpp">trunk/Source/bmalloc/bmalloc/SegregatedFreeList.cpp</a></li>
<li><a href="#trunkSourcebmallocbmallocSegregatedFreeListh">trunk/Source/bmalloc/bmalloc/SegregatedFreeList.h</a></li>
<li><a href="#trunkSourcebmallocbmallocVMAllocateh">trunk/Source/bmalloc/bmalloc/VMAllocate.h</a></li>
<li><a href="#trunkSourcebmallocbmallocVMHeaph">trunk/Source/bmalloc/bmalloc/VMHeap.h</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkPerformanceTestsMallocBenchMallocBenchstress_alignedcpp">trunk/PerformanceTests/MallocBench/MallocBench/stress_aligned.cpp</a></li>
<li><a href="#trunkPerformanceTestsMallocBenchMallocBenchstress_alignedh">trunk/PerformanceTests/MallocBench/MallocBench/stress_aligned.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkPerformanceTestsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/PerformanceTests/ChangeLog (178860 => 178861)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/PerformanceTests/ChangeLog 2015-01-21 22:43:05 UTC (rev 178860)
+++ trunk/PerformanceTests/ChangeLog 2015-01-21 22:49:45 UTC (rev 178861)
</span><span class="lines">@@ -1,3 +1,21 @@
</span><ins>+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.
+
</ins><span class="cx"> 2015-01-16 Geoffrey Garen <ggaren@apple.com>
</span><span class="cx">
</span><span class="cx"> bmalloc: added the tiniest bit of testing for aligned allocation
</span></span></pre></div>
<a id="trunkPerformanceTestsMallocBenchMallocBenchBenchmarkcpp"></a>
<div class="modfile"><h4>Modified: trunk/PerformanceTests/MallocBench/MallocBench/Benchmark.cpp (178860 => 178861)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/PerformanceTests/MallocBench/MallocBench/Benchmark.cpp 2015-01-21 22:43:05 UTC (rev 178860)
+++ trunk/PerformanceTests/MallocBench/MallocBench/Benchmark.cpp 2015-01-21 22:49:45 UTC (rev 178861)
</span><span class="lines">@@ -38,6 +38,7 @@
</span><span class="cx"> #include "reddit.h"
</span><span class="cx"> #include "realloc.h"
</span><span class="cx"> #include "stress.h"
</span><ins>+#include "stress_aligned.h"
</ins><span class="cx"> #include "theverge.h"
</span><span class="cx"> #include "tree.h"
</span><span class="cx"> #include <dispatch/dispatch.h>
</span><span class="lines">@@ -78,6 +79,7 @@
</span><span class="cx"> { "reddit", benchmark_reddit },
</span><span class="cx"> { "reddit_memory_warning", benchmark_reddit_memory_warning },
</span><span class="cx"> { "stress", benchmark_stress },
</span><ins>+ { "stress_aligned", benchmark_stress_aligned },
</ins><span class="cx"> { "theverge", benchmark_theverge },
</span><span class="cx"> { "theverge_memory_warning", benchmark_theverge_memory_warning },
</span><span class="cx"> { "tree_allocate", benchmark_tree_allocate },
</span></span></pre></div>
<a id="trunkPerformanceTestsMallocBenchMallocBenchmemaligncpp"></a>
<div class="modfile"><h4>Modified: trunk/PerformanceTests/MallocBench/MallocBench/memalign.cpp (178860 => 178861)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/PerformanceTests/MallocBench/MallocBench/memalign.cpp 2015-01-21 22:43:05 UTC (rev 178860)
+++ trunk/PerformanceTests/MallocBench/MallocBench/memalign.cpp 2015-01-21 22:49:45 UTC (rev 178861)
</span><span class="lines">@@ -30,27 +30,27 @@
</span><span class="cx">
</span><span class="cx"> #include "mbmalloc.h"
</span><span class="cx">
</span><del>-void benchmark_memalign(bool isParallel)
</del><ins>+void test(size_t alignment, size_t size)
</ins><span class="cx"> {
</span><del>- {
- size_t alignment = 128;
- size_t size = 8;
- void* result = mbmemalign(alignment, size);
</del><ins>+ void* result = mbmemalign(alignment, size);
</ins><span class="cx">
</span><del>- assert(result);
- assert(((uintptr_t)result & (alignment - 1)) == 0);
-
- mbfree(result, size);
- }
</del><ins>+ assert(result);
+ assert(!((uintptr_t)result & (alignment - 1)));
</ins><span class="cx">
</span><del>- {
- size_t alignment = 2048 * 1024 * 1024;
- size_t size = 8;
- void* result = mbmemalign(alignment, size);
</del><ins>+ mbfree(result, size);
+}
</ins><span class="cx">
</span><del>- assert(result);
- assert(((uintptr_t)result & (alignment - 1)) == 0);
-
- mbfree(result, size);
</del><ins>+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);
</ins><span class="cx"> }
</span><ins>+
+ 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);
</ins><span class="cx"> }
</span></span></pre></div>
<a id="trunkPerformanceTestsMallocBenchMallocBenchstress_alignedcpp"></a>
<div class="addfile"><h4>Added: trunk/PerformanceTests/MallocBench/MallocBench/stress_aligned.cpp (0 => 178861)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/PerformanceTests/MallocBench/MallocBench/stress_aligned.cpp (rev 0)
+++ trunk/PerformanceTests/MallocBench/MallocBench/stress_aligned.cpp 2015-01-21 22:49:45 UTC (rev 178861)
</span><span class="lines">@@ -0,0 +1,177 @@
</span><ins>+/*
+ * 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);
+}
</ins></span></pre></div>
<a id="trunkPerformanceTestsMallocBenchMallocBenchstress_alignedh"></a>
<div class="addfile"><h4>Added: trunk/PerformanceTests/MallocBench/MallocBench/stress_aligned.h (0 => 178861)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/PerformanceTests/MallocBench/MallocBench/stress_aligned.h (rev 0)
+++ trunk/PerformanceTests/MallocBench/MallocBench/stress_aligned.h 2015-01-21 22:49:45 UTC (rev 178861)
</span><span class="lines">@@ -0,0 +1,31 @@
</span><ins>+/*
+ * 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
</ins></span></pre></div>
<a id="trunkPerformanceTestsMallocBenchMallocBenchxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/PerformanceTests/MallocBench/MallocBench.xcodeproj/project.pbxproj (178860 => 178861)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/PerformanceTests/MallocBench/MallocBench.xcodeproj/project.pbxproj 2015-01-21 22:43:05 UTC (rev 178860)
+++ trunk/PerformanceTests/MallocBench/MallocBench.xcodeproj/project.pbxproj 2015-01-21 22:49:45 UTC (rev 178861)
</span><span class="lines">@@ -34,6 +34,7 @@
</span><span class="cx"> 14CC393C18EA812B004AFE34 /* libmbmalloc.dylib in Frameworks */ = {isa = PBXBuildFile; fileRef = 14CC393818EA811F004AFE34 /* libmbmalloc.dylib */; settings = {ATTRIBUTES = (Required, ); }; };
</span><span class="cx"> 14CC393F18EA8184004AFE34 /* mbmalloc.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14CC391C18EA6759004AFE34 /* mbmalloc.cpp */; };
</span><span class="cx"> 14CE4A6017BD355800288DAA /* big.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14CE4A5E17BD355800288DAA /* big.cpp */; };
</span><ins>+ 14D0BFF31A6F4D3B00109F31 /* stress_aligned.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14D0BFF11A6F4D3B00109F31 /* stress_aligned.cpp */; };
</ins><span class="cx"> 14D6322E1A69BE0B00A8F84F /* memalign.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14D6322C1A69BE0B00A8F84F /* memalign.cpp */; };
</span><span class="cx"> 14E11932177ECC8B003A8D15 /* CPUCount.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14E11930177ECC8B003A8D15 /* CPUCount.cpp */; };
</span><span class="cx"> 14FCA36119A7C917001CFDA9 /* stress.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14FCA35F19A7C917001CFDA9 /* stress.cpp */; };
</span><span class="lines">@@ -104,6 +105,8 @@
</span><span class="cx"> 14CC393818EA811F004AFE34 /* libmbmalloc.dylib */ = {isa = PBXFileReference; explicitFileType = "compiled.mach-o.dylib"; includeInIndex = 0; path = libmbmalloc.dylib; sourceTree = BUILT_PRODUCTS_DIR; };
</span><span class="cx"> 14CE4A5E17BD355800288DAA /* big.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = big.cpp; path = MallocBench/big.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 14CE4A5F17BD355800288DAA /* big.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = big.h; path = MallocBench/big.h; sourceTree = "<group>"; };
</span><ins>+ 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>"; };
</ins><span class="cx"> 14D6322C1A69BE0B00A8F84F /* memalign.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = memalign.cpp; path = MallocBench/memalign.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 14D6322D1A69BE0B00A8F84F /* memalign.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = memalign.h; path = MallocBench/memalign.h; sourceTree = "<group>"; };
</span><span class="cx"> 14E11930177ECC8B003A8D15 /* CPUCount.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CPUCount.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -220,6 +223,8 @@
</span><span class="cx"> 1447AE8C18FB584200B3D7FF /* reddit.ops */,
</span><span class="cx"> 14FCA35F19A7C917001CFDA9 /* stress.cpp */,
</span><span class="cx"> 14FCA36019A7C917001CFDA9 /* stress.h */,
</span><ins>+ 14D0BFF11A6F4D3B00109F31 /* stress_aligned.cpp */,
+ 14D0BFF21A6F4D3B00109F31 /* stress_aligned.h */,
</ins><span class="cx"> 1447AE9818FB59D900B3D7FF /* theverge_memory_warning.ops */,
</span><span class="cx"> 1447AE8D18FB584200B3D7FF /* theverge.cpp */,
</span><span class="cx"> 1447AE8E18FB584200B3D7FF /* theverge.h */,
</span><span class="lines">@@ -320,6 +325,7 @@
</span><span class="cx"> 14976EC8177E3649006B819A /* list.cpp in Sources */,
</span><span class="cx"> 14976ECC177E3C87006B819A /* CommandLine.cpp in Sources */,
</span><span class="cx"> 1447AE9218FB584200B3D7FF /* theverge.cpp in Sources */,
</span><ins>+ 14D0BFF31A6F4D3B00109F31 /* stress_aligned.cpp in Sources */,
</ins><span class="cx"> 1451FAED18B14B7100DB6D47 /* medium.cpp in Sources */,
</span><span class="cx"> 14C5009318403DA0007A531D /* Interpreter.cpp in Sources */,
</span><span class="cx"> 1447AE9118FB584200B3D7FF /* reddit.cpp in Sources */,
</span></span></pre></div>
<a id="trunkSourcebmallocChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/ChangeLog (178860 => 178861)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/ChangeLog 2015-01-21 22:43:05 UTC (rev 178860)
+++ trunk/Source/bmalloc/ChangeLog 2015-01-21 22:49:45 UTC (rev 178861)
</span><span class="lines">@@ -1,3 +1,59 @@
</span><ins>+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.
+
</ins><span class="cx"> 2015-01-20 Geoffrey Garen <ggaren@apple.com>
</span><span class="cx">
</span><span class="cx"> bmalloc: a little bit of cleanup
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocAllocatorcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/Allocator.cpp (178860 => 178861)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Allocator.cpp 2015-01-21 22:43:05 UTC (rev 178860)
+++ trunk/Source/bmalloc/bmalloc/Allocator.cpp 2015-01-21 22:49:45 UTC (rev 178861)
</span><span class="lines">@@ -52,14 +52,45 @@
</span><span class="cx">
</span><span class="cx"> void* Allocator::allocate(size_t alignment, size_t size)
</span><span class="cx"> {
</span><ins>+ BASSERT(isPowerOfTwo(alignment));
+
</ins><span class="cx"> if (!m_isBmallocEnabled) {
</span><span class="cx"> void* result = nullptr;
</span><span class="cx"> posix_memalign(&result, alignment, size);
</span><span class="cx"> return result;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- BASSERT(isPowerOfTwo(alignment));
- return nullptr;
</del><ins>+ 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);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void* Allocator::reallocate(void* object, size_t newSize)
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocBoundaryTagh"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/BoundaryTag.h (178860 => 178861)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/BoundaryTag.h 2015-01-21 22:43:05 UTC (rev 178860)
+++ trunk/Source/bmalloc/bmalloc/BoundaryTag.h 2015-01-21 22:49:45 UTC (rev 178861)
</span><span class="lines">@@ -41,7 +41,7 @@
</span><span class="cx"> public:
</span><span class="cx"> static Range init(LargeChunk*);
</span><span class="cx"> static Range deallocate(void*);
</span><del>- static void allocate(size_t, Range&, Range& leftover, bool& hasPhysicalPages);
</del><ins>+ static void allocate(const Range&, size_t, Range& leftover, bool& hasPhysicalPages);
</ins><span class="cx"> static unsigned compactBegin(const Range&);
</span><span class="cx">
</span><span class="cx"> bool isFree() { return m_isFree; }
</span><span class="lines">@@ -72,10 +72,10 @@
</span><span class="cx"> static_assert((1 << compactBeginBits) - 1 >= largeMin / largeAlignment, "compactBegin must be encodable in a BoundaryTag.");
</span><span class="cx"> static_assert((1 << sizeBits) - 1 >= largeMax, "largeMax must be encodable in a BoundaryTag.");
</span><span class="cx">
</span><del>- 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&);
</del><ins>+ 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*&);
</ins><span class="cx">
</span><span class="cx"> bool m_isFree: 1;
</span><span class="cx"> bool m_isEnd: 1;
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocBoundaryTagInlinesh"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/BoundaryTagInlines.h (178860 => 178861)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/BoundaryTagInlines.h 2015-01-21 22:43:05 UTC (rev 178860)
+++ trunk/Source/bmalloc/bmalloc/BoundaryTagInlines.h 2015-01-21 22:49:45 UTC (rev 178861)
</span><span class="lines">@@ -105,56 +105,59 @@
</span><span class="cx"> return range;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-inline void BoundaryTag::mergeLeft(EndTag*& prev, BeginTag*& beginTag, Range& range, bool& hasPhysicalPages)
</del><ins>+inline Range BoundaryTag::mergeLeft(const Range& range, BeginTag*& beginTag, EndTag* prev, bool& hasPhysicalPages)
</ins><span class="cx"> {
</span><span class="cx"> Range left(range.begin() - prev->size(), prev->size());
</span><ins>+ Range merged(left.begin(), left.size() + range.size());
</ins><span class="cx">
</span><span class="cx"> hasPhysicalPages &= prev->hasPhysicalPages();
</span><span class="cx">
</span><del>- range = Range(left.begin(), left.size() + range.size());
-
</del><span class="cx"> prev->clear();
</span><span class="cx"> beginTag->clear();
</span><span class="cx">
</span><del>- beginTag = LargeChunk::beginTag(range.begin());
</del><ins>+ beginTag = LargeChunk::beginTag(merged.begin());
+ return merged;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-inline void BoundaryTag::mergeRight(EndTag*& endTag, BeginTag*& next, Range& range, bool& hasPhysicalPages)
</del><ins>+inline Range BoundaryTag::mergeRight(const Range& range, EndTag*& endTag, BeginTag* next, bool& hasPhysicalPages)
</ins><span class="cx"> {
</span><span class="cx"> Range right(range.end(), next->size());
</span><ins>+ Range merged(range.begin(), range.size() + right.size());
</ins><span class="cx">
</span><span class="cx"> hasPhysicalPages &= next->hasPhysicalPages();
</span><span class="cx">
</span><del>- range = Range(range.begin(), range.size() + right.size());
-
</del><span class="cx"> endTag->clear();
</span><span class="cx"> next->clear();
</span><span class="cx">
</span><del>- endTag = LargeChunk::endTag(range.begin(), range.size());
</del><ins>+ endTag = LargeChunk::endTag(merged.begin(), merged.size());
+ return merged;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-INLINE void BoundaryTag::merge(BeginTag*& beginTag, EndTag*& endTag, Range& range)
</del><ins>+INLINE Range BoundaryTag::merge(const Range& range, BeginTag*& beginTag, EndTag*& endTag)
</ins><span class="cx"> {
</span><span class="cx"> EndTag* prev = beginTag->prev();
</span><span class="cx"> BeginTag* next = endTag->next();
</span><span class="cx"> bool hasPhysicalPages = beginTag->hasPhysicalPages();
</span><span class="cx">
</span><span class="cx"> validate(prev, range, next);
</span><ins>+
+ Range merged = range;
</ins><span class="cx">
</span><span class="cx"> if (prev->isFree())
</span><del>- mergeLeft(prev, beginTag, range, hasPhysicalPages);
</del><ins>+ merged = mergeLeft(merged, beginTag, prev, hasPhysicalPages);
</ins><span class="cx">
</span><span class="cx"> if (next->isFree())
</span><del>- mergeRight(endTag, next, range, hasPhysicalPages);
</del><ins>+ merged = mergeRight(merged, endTag, next, hasPhysicalPages);
</ins><span class="cx">
</span><del>- beginTag->setRange(range);
</del><ins>+ beginTag->setRange(merged);
</ins><span class="cx"> beginTag->setFree(true);
</span><span class="cx"> beginTag->setHasPhysicalPages(hasPhysicalPages);
</span><span class="cx">
</span><span class="cx"> if (endTag != static_cast<BoundaryTag*>(beginTag))
</span><span class="cx"> *endTag = *beginTag;
</span><span class="cx">
</span><del>- validate(beginTag->prev(), range, endTag->next());
</del><ins>+ validate(beginTag->prev(), merged, endTag->next());
+ return merged;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> inline Range BoundaryTag::deallocate(void* object)
</span><span class="lines">@@ -164,19 +167,17 @@
</span><span class="cx">
</span><span class="cx"> Range range(object, beginTag->size());
</span><span class="cx"> EndTag* endTag = LargeChunk::endTag(range.begin(), range.size());
</span><del>- merge(beginTag, endTag, range);
-
- return range;
</del><ins>+ return merge(range, beginTag, endTag);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-INLINE void BoundaryTag::split(BeginTag* beginTag, size_t size, EndTag*& endTag, Range& range, Range& leftover)
</del><ins>+INLINE void BoundaryTag::split(const Range& range, size_t size, BeginTag* beginTag, EndTag*& endTag, Range& leftover)
</ins><span class="cx"> {
</span><span class="cx"> leftover = Range(range.begin() + size, range.size() - size);
</span><del>- range = Range(range.begin(), size);
</del><ins>+ Range split(range.begin(), size);
</ins><span class="cx">
</span><del>- beginTag->setRange(range);
</del><ins>+ beginTag->setRange(split);
</ins><span class="cx">
</span><del>- EndTag* splitEndTag = LargeChunk::endTag(range.begin(), size);
</del><ins>+ EndTag* splitEndTag = LargeChunk::endTag(split.begin(), size);
</ins><span class="cx"> if (splitEndTag != static_cast<BoundaryTag*>(beginTag))
</span><span class="cx"> *splitEndTag = *beginTag;
</span><span class="cx">
</span><span class="lines">@@ -188,13 +189,13 @@
</span><span class="cx"> if (leftoverBeginTag != static_cast<BoundaryTag*>(endTag))
</span><span class="cx"> *endTag = *leftoverBeginTag;
</span><span class="cx">
</span><del>- validate(beginTag->prev(), range, leftoverBeginTag);
</del><ins>+ validate(beginTag->prev(), split, leftoverBeginTag);
</ins><span class="cx"> validate(leftoverBeginTag->prev(), leftover, endTag->next());
</span><span class="cx">
</span><span class="cx"> endTag = splitEndTag;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-INLINE void BoundaryTag::allocate(size_t size, Range& range, Range& leftover, bool& hasPhysicalPages)
</del><ins>+INLINE void BoundaryTag::allocate(const Range& range, size_t size, Range& leftover, bool& hasPhysicalPages)
</ins><span class="cx"> {
</span><span class="cx"> BeginTag* beginTag = LargeChunk::beginTag(range.begin());
</span><span class="cx"> EndTag* endTag = LargeChunk::endTag(range.begin(), range.size());
</span><span class="lines">@@ -203,7 +204,7 @@
</span><span class="cx"> validate(beginTag->prev(), range, endTag->next());
</span><span class="cx">
</span><span class="cx"> if (range.size() - size > largeMin)
</span><del>- split(beginTag, size, endTag, range, leftover);
</del><ins>+ split(range, size, beginTag, endTag, leftover);
</ins><span class="cx">
</span><span class="cx"> hasPhysicalPages = beginTag->hasPhysicalPages();
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocHeapcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/Heap.cpp (178860 => 178861)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Heap.cpp 2015-01-21 22:43:05 UTC (rev 178860)
+++ trunk/Source/bmalloc/bmalloc/Heap.cpp 2015-01-21 22:49:45 UTC (rev 178861)
</span><span class="lines">@@ -319,15 +319,24 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>-void* Heap::allocateXLarge(std::lock_guard<StaticMutex>&, size_t size)
</del><ins>+void* Heap::allocateXLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t size)
</ins><span class="cx"> {
</span><ins>+ BASSERT(isPowerOfTwo(alignment));
+ BASSERT(alignment >= xLargeAlignment);
+ BASSERT(size == roundUpToMultipleOf<xLargeAlignment>(size));
+
</ins><span class="cx"> m_isAllocatingPages = true;
</span><span class="cx">
</span><del>- void* result = vmAllocate(size, superChunkSize);
</del><ins>+ void* result = vmAllocate(alignment, size);
</ins><span class="cx"> m_xLargeRanges.push(Range(result, size));
</span><span class="cx"> return result;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+void* Heap::allocateXLarge(std::lock_guard<StaticMutex>& lock, size_t size)
+{
+ return allocateXLarge(lock, superChunkSize, size);
+}
+
</ins><span class="cx"> Range Heap::findXLarge(std::lock_guard<StaticMutex>&, void* object)
</span><span class="cx"> {
</span><span class="cx"> for (auto& range : m_xLargeRanges) {
</span><span class="lines">@@ -355,28 +364,73 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>-void* Heap::allocateLarge(std::lock_guard<StaticMutex>&, size_t size)
</del><ins>+void Heap::allocateLarge(std::lock_guard<StaticMutex>&, const Range& range, size_t size, Range& leftover)
</ins><span class="cx"> {
</span><ins>+ 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)
+{
</ins><span class="cx"> BASSERT(size <= largeMax);
</span><span class="cx"> BASSERT(size >= largeMin);
</span><ins>+ BASSERT(size == roundUpToMultipleOf<largeAlignment>(size));
</ins><span class="cx">
</span><span class="cx"> m_isAllocatingPages = true;
</span><span class="cx">
</span><span class="cx"> Range range = m_largeRanges.take(size);
</span><span class="cx"> if (!range)
</span><span class="cx"> range = m_vmHeap.allocateLargeRange(size);
</span><del>-
- Range leftover;
- bool hasPhysicalPages;
- BoundaryTag::allocate(size, range, leftover, hasPhysicalPages);
</del><span class="cx">
</span><del>- if (!!leftover)
- m_largeRanges.insert(leftover);
-
- if (!hasPhysicalPages)
- vmAllocatePhysicalPagesSloppy(range.begin(), range.size());
</del><ins>+ return allocateLarge(lock, range, size);
+}
</ins><span class="cx">
</span><del>- return range.begin();
</del><ins>+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);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void Heap::deallocateLarge(std::lock_guard<StaticMutex>&, void* object)
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocHeaph"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/Heap.h (178860 => 178861)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/Heap.h 2015-01-21 22:43:05 UTC (rev 178860)
+++ trunk/Source/bmalloc/bmalloc/Heap.h 2015-01-21 22:49:45 UTC (rev 178861)
</span><span class="lines">@@ -60,9 +60,11 @@
</span><span class="cx"> void derefMediumLine(std::lock_guard<StaticMutex>&, MediumLine*);
</span><span class="cx">
</span><span class="cx"> void* allocateLarge(std::lock_guard<StaticMutex>&, size_t);
</span><ins>+ void* allocateLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t, size_t unalignedSize);
</ins><span class="cx"> void deallocateLarge(std::lock_guard<StaticMutex>&, void*);
</span><span class="cx">
</span><span class="cx"> void* allocateXLarge(std::lock_guard<StaticMutex>&, size_t);
</span><ins>+ void* allocateXLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t);
</ins><span class="cx"> Range findXLarge(std::lock_guard<StaticMutex>&, void*);
</span><span class="cx"> void deallocateXLarge(std::unique_lock<StaticMutex>&, void*);
</span><span class="cx">
</span><span class="lines">@@ -79,7 +81,8 @@
</span><span class="cx"> void deallocateSmallLine(std::lock_guard<StaticMutex>&, SmallLine*);
</span><span class="cx"> void deallocateMediumLine(std::lock_guard<StaticMutex>&, MediumLine*);
</span><span class="cx">
</span><del>- void* allocateLarge(Range, size_t);
</del><ins>+ void* allocateLarge(std::lock_guard<StaticMutex>&, const Range&, size_t);
+ void allocateLarge(std::lock_guard<StaticMutex>&, const Range&, size_t, Range& leftover);
</ins><span class="cx"> Range allocateLargeChunk();
</span><span class="cx">
</span><span class="cx"> void splitLarge(BeginTag*, size_t, EndTag*&, Range&);
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocSegregatedFreeListcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/SegregatedFreeList.cpp (178860 => 178861)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/SegregatedFreeList.cpp 2015-01-21 22:43:05 UTC (rev 178860)
+++ trunk/Source/bmalloc/bmalloc/SegregatedFreeList.cpp 2015-01-21 22:49:45 UTC (rev 178861)
</span><span class="lines">@@ -81,10 +81,10 @@
</span><span class="cx"> return Range();
</span><span class="cx"> }
</span><span class="cx">
</span><del>-Range SegregatedFreeList::take(size_t size, size_t alignmentMask)
</del><ins>+Range SegregatedFreeList::take(size_t size)
</ins><span class="cx"> {
</span><span class="cx"> for (auto* list = &select(size); list != m_lists.end(); ++list) {
</span><del>- Range range = take(*list, size, alignmentMask);
</del><ins>+ Range range = take(*list, size);
</ins><span class="cx"> if (!range)
</span><span class="cx"> continue;
</span><span class="cx">
</span><span class="lines">@@ -93,6 +93,18 @@
</span><span class="cx"> return Range();
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+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 range;
+ }
+ return Range();
+}
+
</ins><span class="cx"> INLINE auto SegregatedFreeList::select(size_t size) -> List&
</span><span class="cx"> {
</span><span class="cx"> size_t alignCount = (size - largeMin) / largeAlignment;
</span><span class="lines">@@ -104,7 +116,7 @@
</span><span class="cx"> return m_lists[result];
</span><span class="cx"> }
</span><span class="cx">
</span><del>-INLINE Range SegregatedFreeList::take(List& list, size_t size, size_t alignmentMask)
</del><ins>+INLINE Range SegregatedFreeList::take(List& list, size_t size)
</ins><span class="cx"> {
</span><span class="cx"> Range first;
</span><span class="cx"> size_t end = list.size() > segregatedFreeListSearchDepth ? list.size() - segregatedFreeListSearchDepth : 0;
</span><span class="lines">@@ -122,9 +134,39 @@
</span><span class="cx"> if (range.size() < size)
</span><span class="cx"> continue;
</span><span class="cx">
</span><del>- if (test(range.begin(), alignmentMask))
</del><ins>+ if (!!first && first < range)
</ins><span class="cx"> continue;
</span><span class="cx">
</span><ins>+ 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;
+
</ins><span class="cx"> if (!!first && first < range)
</span><span class="cx"> continue;
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocSegregatedFreeListh"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/SegregatedFreeList.h (178860 => 178861)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/SegregatedFreeList.h 2015-01-21 22:43:05 UTC (rev 178860)
+++ trunk/Source/bmalloc/bmalloc/SegregatedFreeList.h 2015-01-21 22:49:45 UTC (rev 178861)
</span><span class="lines">@@ -38,13 +38,19 @@
</span><span class="cx">
</span><span class="cx"> void insert(const Range&);
</span><span class="cx">
</span><del>- // 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);
</del><ins>+ // 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);
</ins><span class="cx">
</span><ins>+ // 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);
+
</ins><span class="cx"> // Returns an unreasonable fit for the provided size, or Range() if no fit
</span><span class="cx"> // is found. Never returns Range() spuriously.
</span><span class="cx"> // Incrementally removes stale items from the free list while searching.
</span><span class="lines">@@ -55,7 +61,8 @@
</span><span class="cx"> typedef Vector<Range> List;
</span><span class="cx">
</span><span class="cx"> List& select(size_t);
</span><del>- Range take(List&, size_t, size_t alignmentMask);
</del><ins>+ Range take(List&, size_t);
+ Range take(List&, size_t alignment, size_t, size_t unalignedSize);
</ins><span class="cx"> Range takeGreedy(List&, size_t);
</span><span class="cx">
</span><span class="cx"> std::array<List, 19> m_lists;
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocVMAllocateh"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/VMAllocate.h (178860 => 178861)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/VMAllocate.h 2015-01-21 22:43:05 UTC (rev 178860)
+++ trunk/Source/bmalloc/bmalloc/VMAllocate.h 2015-01-21 22:49:45 UTC (rev 178861)
</span><span class="lines">@@ -83,7 +83,7 @@
</span><span class="cx"> // Allocates vmSize bytes at a specified power-of-two alignment.
</span><span class="cx"> // Use this function to create maskable memory regions.
</span><span class="cx">
</span><del>-inline void* vmAllocate(size_t vmSize, size_t vmAlignment)
</del><ins>+inline void* vmAllocate(size_t vmAlignment, size_t vmSize)
</ins><span class="cx"> {
</span><span class="cx"> vmValidate(vmSize);
</span><span class="cx"> vmValidate(vmAlignment);
</span></span></pre></div>
<a id="trunkSourcebmallocbmallocVMHeaph"></a>
<div class="modfile"><h4>Modified: trunk/Source/bmalloc/bmalloc/VMHeap.h (178860 => 178861)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/bmalloc/bmalloc/VMHeap.h 2015-01-21 22:43:05 UTC (rev 178860)
+++ trunk/Source/bmalloc/bmalloc/VMHeap.h 2015-01-21 22:49:45 UTC (rev 178861)
</span><span class="lines">@@ -48,6 +48,7 @@
</span><span class="cx"> SmallPage* allocateSmallPage();
</span><span class="cx"> MediumPage* allocateMediumPage();
</span><span class="cx"> Range allocateLargeRange(size_t);
</span><ins>+ Range allocateLargeRange(size_t alignment, size_t, size_t unalignedSize);
</ins><span class="cx">
</span><span class="cx"> void deallocateSmallPage(std::unique_lock<StaticMutex>&, SmallPage*);
</span><span class="cx"> void deallocateMediumPage(std::unique_lock<StaticMutex>&, MediumPage*);
</span><span class="lines">@@ -88,6 +89,17 @@
</span><span class="cx"> return range;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+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;
+}
+
</ins><span class="cx"> inline void VMHeap::deallocateSmallPage(std::unique_lock<StaticMutex>& lock, SmallPage* page)
</span><span class="cx"> {
</span><span class="cx"> lock.unlock();
</span></span></pre>
</div>
</div>
</body>
</html>