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