1 /*
2 * Copyright 2016 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8 #include "src/core/SkArenaAlloc.h"
9 #include <algorithm>
10 #include <new>
11
end_chain(char*)12 static char* end_chain(char*) { return nullptr; }
13
SkArenaAlloc(char* block, size_t size, size_t firstHeapAllocation)14 SkArenaAlloc::SkArenaAlloc(char* block, size_t size, size_t firstHeapAllocation)
15 : fDtorCursor {block}
16 , fCursor {block}
17 , fEnd {block + SkToU32(size)}
18 , fFibonacciProgression{SkToU32(size), SkToU32(firstHeapAllocation)}
19 {
20 if (size < sizeof(Footer)) {
21 fEnd = fCursor = fDtorCursor = nullptr;
22 }
23
24 if (fCursor != nullptr) {
25 this->installFooter(end_chain, 0);
26 }
27 }
28
~SkArenaAlloc()29 SkArenaAlloc::~SkArenaAlloc() {
30 RunDtorsOnBlock(fDtorCursor);
31 }
32
installFooter(FooterAction* action, uint32_t padding)33 void SkArenaAlloc::installFooter(FooterAction* action, uint32_t padding) {
34 assert(SkTFitsIn<uint8_t>(padding));
35 this->installRaw(action);
36 this->installRaw((uint8_t)padding);
37 fDtorCursor = fCursor;
38 }
39
SkipPod(char* footerEnd)40 char* SkArenaAlloc::SkipPod(char* footerEnd) {
41 char* objEnd = footerEnd - (sizeof(Footer) + sizeof(int32_t));
42 int32_t skip;
43 memmove(&skip, objEnd, sizeof(int32_t));
44 return objEnd - skip;
45 }
46
RunDtorsOnBlock(char* footerEnd)47 void SkArenaAlloc::RunDtorsOnBlock(char* footerEnd) {
48 while (footerEnd != nullptr) {
49 FooterAction* action;
50 uint8_t padding;
51
52 memcpy(&action, footerEnd - sizeof( Footer), sizeof( action));
53 memcpy(&padding, footerEnd - sizeof(padding), sizeof(padding));
54
55 footerEnd = action(footerEnd) - (ptrdiff_t)padding;
56 }
57 }
58
NextBlock(char* footerEnd)59 char* SkArenaAlloc::NextBlock(char* footerEnd) {
60 char* objEnd = footerEnd - (sizeof(char*) + sizeof(Footer));
61 char* next;
62 memmove(&next, objEnd, sizeof(char*));
63 RunDtorsOnBlock(next);
64 delete [] objEnd;
65 return nullptr;
66 }
67
68
ensureSpace(uint32_t size, uint32_t alignment)69 void SkArenaAlloc::ensureSpace(uint32_t size, uint32_t alignment) {
70 constexpr uint32_t headerSize = sizeof(Footer) + sizeof(ptrdiff_t);
71 constexpr uint32_t maxSize = std::numeric_limits<uint32_t>::max();
72 constexpr uint32_t overhead = headerSize + sizeof(Footer);
73 AssertRelease(size <= maxSize - overhead);
74 uint32_t objSizeAndOverhead = size + overhead;
75
76 const uint32_t alignmentOverhead = alignment - 1;
77 AssertRelease(objSizeAndOverhead <= maxSize - alignmentOverhead);
78 objSizeAndOverhead += alignmentOverhead;
79
80 uint32_t minAllocationSize = fFibonacciProgression.nextBlockSize();
81 uint32_t allocationSize = std::max(objSizeAndOverhead, minAllocationSize);
82
83 // Round up to a nice size. If > 32K align to 4K boundary else up to max_align_t. The > 32K
84 // heuristic is from the JEMalloc behavior.
85 {
86 uint32_t mask = allocationSize > (1 << 15) ? (1 << 12) - 1 : 16 - 1;
87 AssertRelease(allocationSize <= maxSize - mask);
88 allocationSize = (allocationSize + mask) & ~mask;
89 }
90
91 char* newBlock = new char[allocationSize];
92
93 auto previousDtor = fDtorCursor;
94 fCursor = newBlock;
95 fDtorCursor = newBlock;
96 fEnd = fCursor + allocationSize;
97 this->installRaw(previousDtor);
98 this->installFooter(NextBlock, 0);
99 }
100
allocObjectWithFooter(uint32_t sizeIncludingFooter, uint32_t alignment)101 char* SkArenaAlloc::allocObjectWithFooter(uint32_t sizeIncludingFooter, uint32_t alignment) {
102 uintptr_t mask = alignment - 1;
103
104 restart:
105 uint32_t skipOverhead = 0;
106 const bool needsSkipFooter = fCursor != fDtorCursor;
107 if (needsSkipFooter) {
108 skipOverhead = sizeof(Footer) + sizeof(uint32_t);
109 }
110 const uint32_t totalSize = sizeIncludingFooter + skipOverhead;
111
112 // Math on null fCursor/fEnd is undefined behavior, so explicitly check for first alloc.
113 if (!fCursor) {
114 this->ensureSpace(totalSize, alignment);
115 goto restart;
116 }
117
118 assert(fEnd);
119 // This test alone would be enough nullptr were defined to be 0, but it's not.
120 char* objStart = (char*)((uintptr_t)(fCursor + skipOverhead + mask) & ~mask);
121 if ((ptrdiff_t)totalSize > fEnd - objStart) {
122 this->ensureSpace(totalSize, alignment);
123 goto restart;
124 }
125
126 AssertRelease((ptrdiff_t)totalSize <= fEnd - objStart);
127
128 // Install a skip footer if needed, thus terminating a run of POD data. The calling code is
129 // responsible for installing the footer after the object.
130 if (needsSkipFooter) {
131 this->installRaw(SkToU32(fCursor - fDtorCursor));
132 this->installFooter(SkipPod, 0);
133 }
134
135 return objStart;
136 }
137
SkArenaAllocWithReset(char* block, size_t size, size_t firstHeapAllocation)138 SkArenaAllocWithReset::SkArenaAllocWithReset(char* block,
139 size_t size,
140 size_t firstHeapAllocation)
141 : SkArenaAlloc(block, size, firstHeapAllocation)
142 , fFirstBlock{block}
143 , fFirstSize{SkToU32(size)}
144 , fFirstHeapAllocationSize{SkToU32(firstHeapAllocation)} {}
145
reset()146 void SkArenaAllocWithReset::reset() {
147 this->~SkArenaAllocWithReset();
148 new (this) SkArenaAllocWithReset{fFirstBlock, fFirstSize, fFirstHeapAllocationSize};
149 }
150
151 // SkFibonacci47 is the first 47 Fibonacci numbers. Fib(47) is the largest value less than 2 ^ 32.
152 // Used by SkFibBlockSizes.
153 std::array<const uint32_t, 47> SkFibonacci47 {
154 1, 1, 2, 3, 5, 8,
155 13, 21, 34, 55, 89, 144,
156 233, 377, 610, 987, 1597, 2584,
157 4181, 6765, 10946, 17711, 28657, 46368,
158 75025, 121393, 196418, 317811, 514229, 832040,
159 1346269, 2178309, 3524578, 5702887, 9227465, 14930352,
160 24157817, 39088169, 63245986, 102334155, 165580141, 267914296,
161 433494437, 701408733, 1134903170, 1836311903, 2971215073,
162 };
163