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
12static char* end_chain(char*) { return nullptr; }
13
14static uint32_t first_allocated_block(uint32_t blockSize, uint32_t firstHeapAllocation) {
15 return firstHeapAllocation > 0 ? firstHeapAllocation :
16 blockSize > 0 ? blockSize : 1024;
17}
18
19SkArenaAlloc::SkArenaAlloc(char* block, size_t size, size_t firstHeapAllocation)
20 : fDtorCursor {block}
21 , fCursor {block}
22 , fEnd {block + ToU32(size)}
23 , fNextHeapAlloc{first_allocated_block(ToU32(size), ToU32(firstHeapAllocation))}
24 , fYetNextHeapAlloc{fNextHeapAlloc}
25{
26 if (size < sizeof(Footer)) {
27 fEnd = fCursor = fDtorCursor = nullptr;
28 }
29
30 if (fCursor != nullptr) {
31 this->installFooter(end_chain, 0);
32 }
33}
34
35SkArenaAlloc::~SkArenaAlloc() {
36 RunDtorsOnBlock(fDtorCursor);
37}
38
39void SkArenaAlloc::installFooter(FooterAction* action, uint32_t padding) {
40 assert(padding < 64);
41 int64_t actionInt = (int64_t)(intptr_t)action;
42
43 // The top 14 bits should be either all 0s or all 1s. Check this.
44 assert((actionInt << 6) >> 6 == actionInt);
45 Footer encodedFooter = (actionInt << 6) | padding;
46 memmove(fCursor, &encodedFooter, sizeof(Footer));
47 fCursor += sizeof(Footer);
48 fDtorCursor = fCursor;
49}
50
51void SkArenaAlloc::installPtrFooter(FooterAction* action, char* ptr, uint32_t padding) {
52 memmove(fCursor, &ptr, sizeof(char*));
53 fCursor += sizeof(char*);
54 this->installFooter(action, padding);
55}
56
57char* SkArenaAlloc::SkipPod(char* footerEnd) {
58 char* objEnd = footerEnd - (sizeof(Footer) + sizeof(int32_t));
59 int32_t skip;
60 memmove(&skip, objEnd, sizeof(int32_t));
61 return objEnd - skip;
62}
63
64void SkArenaAlloc::RunDtorsOnBlock(char* footerEnd) {
65 while (footerEnd != nullptr) {
66 Footer footer;
67 memcpy(&footer, footerEnd - sizeof(Footer), sizeof(Footer));
68
69 FooterAction* action = (FooterAction*)(footer >> 6);
70 ptrdiff_t padding = footer & 63;
71
72 footerEnd = action(footerEnd) - padding;
73 }
74}
75
76char* SkArenaAlloc::NextBlock(char* footerEnd) {
77 char* objEnd = footerEnd - (sizeof(Footer) + sizeof(char*));
78 char* next;
79 memmove(&next, objEnd, sizeof(char*));
80 RunDtorsOnBlock(next);
81 delete [] objEnd;
82 return nullptr;
83}
84
85void SkArenaAlloc::installUint32Footer(FooterAction* action, uint32_t value, uint32_t padding) {
86 memmove(fCursor, &value, sizeof(uint32_t));
87 fCursor += sizeof(uint32_t);
88 this->installFooter(action, padding);
89}
90
91void SkArenaAlloc::ensureSpace(uint32_t size, uint32_t alignment) {
92 constexpr uint32_t headerSize = sizeof(Footer) + sizeof(ptrdiff_t);
93 // The chrome c++ library we use does not define std::max_align_t.
94 // This must be conservative to add the right amount of extra memory to handle the alignment
95 // padding.
96 constexpr uint32_t alignof_max_align_t = 8;
97 constexpr uint32_t maxSize = std::numeric_limits<uint32_t>::max();
98 constexpr uint32_t overhead = headerSize + sizeof(Footer);
99 AssertRelease(size <= maxSize - overhead);
100 uint32_t objSizeAndOverhead = size + overhead;
101 if (alignment > alignof_max_align_t) {
102 uint32_t alignmentOverhead = alignment - 1;
103 AssertRelease(objSizeAndOverhead <= maxSize - alignmentOverhead);
104 objSizeAndOverhead += alignmentOverhead;
105 }
106
107 uint32_t minAllocationSize = fNextHeapAlloc;
108
109 // Calculate the next heap alloc that won't overflow.
110 if (fYetNextHeapAlloc <= maxSize - fNextHeapAlloc) {
111 fNextHeapAlloc += fYetNextHeapAlloc;
112 std::swap(fNextHeapAlloc, fYetNextHeapAlloc);
113 } else {
114 fNextHeapAlloc = maxSize;
115 }
116 uint32_t allocationSize = std::max(objSizeAndOverhead, minAllocationSize);
117
118 // Round up to a nice size. If > 32K align to 4K boundary else up to max_align_t. The > 32K
119 // heuristic is from the JEMalloc behavior.
120 {
121 uint32_t mask = allocationSize > (1 << 15) ? (1 << 12) - 1 : 16 - 1;
122 AssertRelease(allocationSize <= maxSize - mask);
123 allocationSize = (allocationSize + mask) & ~mask;
124 }
125
126 char* newBlock = new char[allocationSize];
127
128 auto previousDtor = fDtorCursor;
129 fCursor = newBlock;
130 fDtorCursor = newBlock;
131 fEnd = fCursor + allocationSize;
132 this->installPtrFooter(NextBlock, previousDtor, 0);
133}
134
135char* SkArenaAlloc::allocObjectWithFooter(uint32_t sizeIncludingFooter, uint32_t alignment) {
136 uintptr_t mask = alignment - 1;
137
138restart:
139 uint32_t skipOverhead = 0;
140 const bool needsSkipFooter = fCursor != fDtorCursor;
141 if (needsSkipFooter) {
142 skipOverhead = sizeof(Footer) + sizeof(uint32_t);
143 }
144 const uint32_t totalSize = sizeIncludingFooter + skipOverhead;
145
146 // Math on null fCursor/fEnd is undefined behavior, so explicitly check for first alloc.
147 if (!fCursor) {
148 this->ensureSpace(totalSize, alignment);
149 goto restart;
150 }
151
152 assert(fEnd);
153 // This test alone would be enough nullptr were defined to be 0, but it's not.
154 char* objStart = (char*)((uintptr_t)(fCursor + skipOverhead + mask) & ~mask);
155 if ((ptrdiff_t)totalSize > fEnd - objStart) {
156 this->ensureSpace(totalSize, alignment);
157 goto restart;
158 }
159
160 AssertRelease((ptrdiff_t)totalSize <= fEnd - objStart);
161
162 // Install a skip footer if needed, thus terminating a run of POD data. The calling code is
163 // responsible for installing the footer after the object.
164 if (needsSkipFooter) {
165 this->installUint32Footer(SkipPod, ToU32(fCursor - fDtorCursor), 0);
166 }
167
168 return objStart;
169}
170
171static uint32_t to_uint32_t(size_t v) {
172 assert(SkTFitsIn<uint32_t>(v));
173 return (uint32_t)v;
174}
175
176SkArenaAllocWithReset::SkArenaAllocWithReset(char* block,
177 size_t size,
178 size_t firstHeapAllocation)
179 : SkArenaAlloc(block, size, firstHeapAllocation)
180 , fFirstBlock{block}
181 , fFirstSize{to_uint32_t(size)}
182 , fFirstHeapAllocationSize{to_uint32_t(firstHeapAllocation)} {}
183
184void SkArenaAllocWithReset::reset() {
185 this->~SkArenaAllocWithReset();
186 new (this) SkArenaAllocWithReset{fFirstBlock, fFirstSize, fFirstHeapAllocationSize};
187}
188