1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
/*
* Copyright 2016 Google Inc.
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
#pragma once
#include <array>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <limits>
#include <new>
#include <type_traits>
#include <utility>
#include <vector>
#include "include/core/SkTypes.h"
#include "include/private/SkTFitsIn.h"
#include "include/private/SkTo.h"
namespace pk {
// We found allocating strictly doubling amounts of memory from the heap left too
// much unused slop, particularly on Android. Instead we'll follow a Fibonacci-like
// progression.
// SkFibonacci47 is the first 47 Fibonacci numbers. Fib(47) is the largest value less than 2 ^ 32.
extern std::array<const uint32_t, 47> SkFibonacci47;
template<uint32_t kMaxSize>
class SkFibBlockSizes {
public:
// staticBlockSize, and firstAllocationSize are parameters describing the initial memory
// layout. staticBlockSize describes the size of the inlined memory, and firstAllocationSize
// describes the size of the first block to be allocated if the static block is exhausted. By
// convention, firstAllocationSize is the first choice for the block unit size followed by
// staticBlockSize followed by the default of 1024 bytes.
SkFibBlockSizes(uint32_t staticBlockSize, uint32_t firstAllocationSize) : fIndex{0} {
fBlockUnitSize = firstAllocationSize > 0 ? firstAllocationSize :
staticBlockSize > 0 ? staticBlockSize : 1024;
PkASSERT_RELEASE(0 < fBlockUnitSize);
PkASSERT_RELEASE(fBlockUnitSize < std::min(kMaxSize, (1u << 26) - 1));
}
uint32_t nextBlockSize() {
uint32_t result = SkFibonacci47[fIndex] * fBlockUnitSize;
if (SkTo<size_t>(fIndex + 1) < SkFibonacci47.size() &&
SkFibonacci47[fIndex + 1] < kMaxSize / fBlockUnitSize)
{
fIndex += 1;
}
return result;
}
private:
uint32_t fIndex : 6;
uint32_t fBlockUnitSize : 26;
};
// SkArenaAlloc allocates object and destroys the allocated objects when destroyed. It's designed
// to minimize the number of underlying block allocations. SkArenaAlloc allocates first out of an
// (optional) user-provided block of memory, and when that's exhausted it allocates on the heap,
// starting with an allocation of firstHeapAllocation bytes. If your data (plus a small overhead)
// fits in the user-provided block, SkArenaAlloc never uses the heap, and if it fits in
// firstHeapAllocation bytes, it'll use the heap only once. If 0 is specified for
// firstHeapAllocation, then blockSize is used unless that too is 0, then 1024 is used.
//
// Examples:
//
// char block[mostCasesSize];
// SkArenaAlloc arena(block, mostCasesSize);
//
// If mostCasesSize is too large for the stack, you can use the following pattern.
//
// std::unique_ptr<char[]> block{new char[mostCasesSize]};
// SkArenaAlloc arena(block.get(), mostCasesSize, almostAllCasesSize);
//
// If the program only sometimes allocates memory, use the following pattern.
//
// SkArenaAlloc arena(nullptr, 0, almostAllCasesSize);
//
// The storage does not necessarily need to be on the stack. Embedding the storage in a class also
// works.
//
// class Foo {
// char storage[mostCasesSize];
// SkArenaAlloc arena (storage, mostCasesSize);
// };
//
// In addition, the system is optimized to handle POD data including arrays of PODs (where
// POD is really data with no destructors). For POD data it has zero overhead per item, and a
// typical per block overhead of 8 bytes. For non-POD objects there is a per item overhead of 4
// bytes. For arrays of non-POD objects there is a per array overhead of typically 8 bytes. There
// is an addition overhead when switching from POD data to non-POD data of typically 8 bytes.
//
// If additional blocks are needed they are increased exponentially. This strategy bounds the
// recursion of the RunDtorsOnBlock to be limited to O(log size-of-memory). Block size grow using
// the Fibonacci sequence which means that for 2^32 memory there are 48 allocations, and for 2^48
// there are 71 allocations.
class SkArenaAlloc {
public:
SkArenaAlloc(char* block, size_t blockSize, size_t firstHeapAllocation);
explicit SkArenaAlloc(size_t firstHeapAllocation)
: SkArenaAlloc(nullptr, 0, firstHeapAllocation) {}
SkArenaAlloc(const SkArenaAlloc&) = delete;
SkArenaAlloc& operator=(const SkArenaAlloc&) = delete;
SkArenaAlloc(SkArenaAlloc&&) = delete;
SkArenaAlloc& operator=(SkArenaAlloc&&) = delete;
~SkArenaAlloc();
template <typename Ctor>
auto make(Ctor&& ctor) -> decltype(ctor(nullptr)) {
using T = std::remove_pointer_t<decltype(ctor(nullptr))>;
uint32_t size = ToU32(sizeof(T));
uint32_t alignment = ToU32(alignof(T));
char* objStart;
if (std::is_trivially_destructible<T>::value) {
objStart = this->allocObject(size, alignment);
fCursor = objStart + size;
} else {
objStart = this->allocObjectWithFooter(size + sizeof(Footer), alignment);
// Can never be UB because max value is alignof(T).
uint32_t padding = ToU32(objStart - fCursor);
// Advance to end of object to install footer.
fCursor = objStart + size;
FooterAction* releaser = [](char* objEnd) {
char* objStart = objEnd - (sizeof(T) + sizeof(Footer));
((T*)objStart)->~T();
return objStart;
};
this->installFooter(releaser, padding);
}
// This must be last to make objects with nested use of this allocator work.
return ctor(objStart);
}
template <typename T, typename... Args>
T* make(Args&&... args) {
return this->make([&](void* objStart) {
return new(objStart) T(std::forward<Args>(args)...);
});
}
template <typename T>
T* makeArrayDefault(size_t count) {
T* array = this->allocUninitializedArray<T>(count);
for (size_t i = 0; i < count; i++) {
// Default initialization: if T is primitive then the value is left uninitialized.
new (&array[i]) T;
}
return array;
}
private:
static void AssertRelease(bool cond) { if (!cond) { ::abort(); } }
static uint32_t ToU32(size_t v) {
assert(SkTFitsIn<uint32_t>(v));
return (uint32_t)v;
}
using FooterAction = char* (char*);
struct Footer {
uint8_t unaligned_action[sizeof(FooterAction*)];
uint8_t padding;
};
static char* SkipPod(char* footerEnd);
static void RunDtorsOnBlock(char* footerEnd);
static char* NextBlock(char* footerEnd);
template <typename T>
void installRaw(const T& val) {
memcpy(fCursor, &val, sizeof(val));
fCursor += sizeof(val);
}
void installFooter(FooterAction* releaser, uint32_t padding);
void ensureSpace(uint32_t size, uint32_t alignment);
char* allocObject(uint32_t size, uint32_t alignment) {
uintptr_t mask = alignment - 1;
uintptr_t alignedOffset = (~reinterpret_cast<uintptr_t>(fCursor) + 1) & mask;
uintptr_t totalSize = size + alignedOffset;
AssertRelease(totalSize >= size);
if (totalSize > static_cast<uintptr_t>(fEnd - fCursor)) {
this->ensureSpace(size, alignment);
alignedOffset = (~reinterpret_cast<uintptr_t>(fCursor) + 1) & mask;
}
return fCursor + alignedOffset;
}
char* allocObjectWithFooter(uint32_t sizeIncludingFooter, uint32_t alignment);
template <typename T>
T* allocUninitializedArray(size_t countZ) {
AssertRelease(SkTFitsIn<uint32_t>(countZ));
uint32_t count = ToU32(countZ);
char* objStart;
AssertRelease(count <= std::numeric_limits<uint32_t>::max() / sizeof(T));
uint32_t arraySize = ToU32(count * sizeof(T));
uint32_t alignment = ToU32(alignof(T));
if (std::is_trivially_destructible<T>::value) {
objStart = this->allocObject(arraySize, alignment);
fCursor = objStart + arraySize;
} else {
constexpr uint32_t overhead = sizeof(Footer) + sizeof(uint32_t);
AssertRelease(arraySize <= std::numeric_limits<uint32_t>::max() - overhead);
uint32_t totalSize = arraySize + overhead;
objStart = this->allocObjectWithFooter(totalSize, alignment);
// Can never be UB because max value is alignof(T).
uint32_t padding = ToU32(objStart - fCursor);
// Advance to end of array to install footer.
fCursor = objStart + arraySize;
this->installRaw(ToU32(count));
this->installFooter(
[](char* footerEnd) {
char* objEnd = footerEnd - (sizeof(Footer) + sizeof(uint32_t));
uint32_t count;
memmove(&count, objEnd, sizeof(uint32_t));
char* objStart = objEnd - count * sizeof(T);
T* array = (T*) objStart;
for (uint32_t i = 0; i < count; i++) {
array[i].~T();
}
return objStart;
},
padding);
}
return (T*)objStart;
}
char* fDtorCursor;
char* fCursor;
char* fEnd;
SkFibBlockSizes<std::numeric_limits<uint32_t>::max()> fFibonacciProgression;
};
// Helper for defining allocators with inline/reserved storage.
// For argument declarations, stick to the base type (SkArenaAlloc).
// Note: Inheriting from the storage first means the storage will outlive the
// SkArenaAlloc, letting ~SkArenaAlloc read it as it calls destructors.
// (This is mostly only relevant for strict tools like MSAN.)
template <size_t InlineStorageSize>
class SkSTArenaAlloc : private std::array<char, InlineStorageSize>, public SkArenaAlloc {
public:
explicit SkSTArenaAlloc(size_t firstHeapAllocation = InlineStorageSize)
: SkArenaAlloc{this->data(), this->size(), firstHeapAllocation} {}
};
} // namespace pk