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 + ToU32(size)}
18 , fFibonacciProgression{ToU32(size), ToU32(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(ToU32(fCursor - fDtorCursor));
132 this->installFooter(SkipPod, 0);
133 }
134
135 return objStart;
136 }
137
to_uint32_t(size_t v)138 static uint32_t to_uint32_t(size_t v) {
139 assert(SkTFitsIn<uint32_t>(v));
140 return (uint32_t)v;
141 }
142
SkArenaAllocWithReset(char * block,size_t size,size_t firstHeapAllocation)143 SkArenaAllocWithReset::SkArenaAllocWithReset(char* block,
144 size_t size,
145 size_t firstHeapAllocation)
146 : SkArenaAlloc(block, size, firstHeapAllocation)
147 , fFirstBlock{block}
148 , fFirstSize{to_uint32_t(size)}
149 , fFirstHeapAllocationSize{to_uint32_t(firstHeapAllocation)} {}
150
reset()151 void SkArenaAllocWithReset::reset() {
152 this->~SkArenaAllocWithReset();
153 new (this) SkArenaAllocWithReset{fFirstBlock, fFirstSize, fFirstHeapAllocationSize};
154 }
155
156 // SkFibonacci47 is the first 47 Fibonacci numbers. Fib(47) is the largest value less than 2 ^ 32.
157 // Used by SkFibBlockSizes.
158 std::array<const uint32_t, 47> SkFibonacci47 {
159 1, 1, 2, 3, 5, 8,
160 13, 21, 34, 55, 89, 144,
161 233, 377, 610, 987, 1597, 2584,
162 4181, 6765, 10946, 17711, 28657, 46368,
163 75025, 121393, 196418, 317811, 514229, 832040,
164 1346269, 2178309, 3524578, 5702887, 9227465, 14930352,
165 24157817, 39088169, 63245986, 102334155, 165580141, 267914296,
166 433494437, 701408733, 1134903170, 1836311903, 2971215073,
167 };
168