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 <algorithm>
9 #include <cstddef>
10 #include "SkArenaAlloc.h"
11
end_chain(char *)12 static char* end_chain(char*) { return nullptr; }
13
SkipPod(char * footerEnd)14 char* SkArenaAlloc::SkipPod(char* footerEnd) {
15 char* objEnd = footerEnd - (sizeof(Footer) + sizeof(int32_t));
16 int32_t skip;
17 memmove(&skip, objEnd, sizeof(int32_t));
18 return objEnd - skip;
19 }
20
RunDtorsOnBlock(char * footerEnd)21 void SkArenaAlloc::RunDtorsOnBlock(char* footerEnd) {
22 while (footerEnd != nullptr) {
23 Footer footer;
24 memcpy(&footer, footerEnd - sizeof(Footer), sizeof(Footer));
25
26 FooterAction* action = (FooterAction*)(footer >> 6);
27 ptrdiff_t padding = footer & 63;
28
29 footerEnd = action(footerEnd) - padding;
30 }
31 }
32
NextBlock(char * footerEnd)33 char* SkArenaAlloc::NextBlock(char* footerEnd) {
34 char* objEnd = footerEnd - (sizeof(Footer) + sizeof(char*));
35 char* next;
36 memmove(&next, objEnd, sizeof(char*));
37 RunDtorsOnBlock(next);
38 delete [] objEnd;
39 return nullptr;
40 }
41
SkArenaAlloc(char * block,size_t size,size_t extraSize)42 SkArenaAlloc::SkArenaAlloc(char* block, size_t size, size_t extraSize)
43 : fDtorCursor {block}
44 , fCursor {block}
45 , fEnd {block + SkTo<uint32_t>(size)}
46 , fFirstBlock {block}
47 , fFirstSize {SkTo<uint32_t>(size)}
48 , fExtraSize {SkTo<uint32_t>(extraSize)}
49 {
50 if (size < sizeof(Footer)) {
51 fEnd = fCursor = fDtorCursor = nullptr;
52 }
53
54 if (fCursor != nullptr) {
55 this->installFooter(end_chain, 0);
56 }
57 }
58
~SkArenaAlloc()59 SkArenaAlloc::~SkArenaAlloc() {
60 RunDtorsOnBlock(fDtorCursor);
61 }
62
reset()63 void SkArenaAlloc::reset() {
64 this->~SkArenaAlloc();
65 new (this) SkArenaAlloc{fFirstBlock, fFirstSize, fExtraSize};
66 }
67
installFooter(FooterAction * action,uint32_t padding)68 void SkArenaAlloc::installFooter(FooterAction* action, uint32_t padding) {
69 SkASSERT(padding < 64);
70 int64_t actionInt = (int64_t)(intptr_t)action;
71
72 // The top 14 bits should be either all 0s or all 1s. Check this.
73 SkASSERT((actionInt << 6) >> 6 == actionInt);
74 Footer encodedFooter = (actionInt << 6) | padding;
75 memmove(fCursor, &encodedFooter, sizeof(Footer));
76 fCursor += sizeof(Footer);
77 fDtorCursor = fCursor;
78 }
79
installPtrFooter(FooterAction * action,char * ptr,uint32_t padding)80 void SkArenaAlloc::installPtrFooter(FooterAction* action, char* ptr, uint32_t padding) {
81 memmove(fCursor, &ptr, sizeof(char*));
82 fCursor += sizeof(char*);
83 this->installFooter(action, padding);
84 }
85
installUint32Footer(FooterAction * action,uint32_t value,uint32_t padding)86 void SkArenaAlloc::installUint32Footer(FooterAction* action, uint32_t value, uint32_t padding) {
87 memmove(fCursor, &value, sizeof(uint32_t));
88 fCursor += sizeof(uint32_t);
89 this->installFooter(action, padding);
90 }
91
ensureSpace(uint32_t size,uint32_t alignment)92 void SkArenaAlloc::ensureSpace(uint32_t size, uint32_t alignment) {
93 constexpr uint32_t headerSize = sizeof(Footer) + sizeof(ptrdiff_t);
94 // The chrome c++ library we use does not define std::max_align_t.
95 // This must be conservative to add the right amount of extra memory to handle the alignment
96 // padding.
97 constexpr uint32_t alignof_max_align_t = 8;
98 uint32_t objSizeAndOverhead = size + headerSize + sizeof(Footer);
99 if (alignment > alignof_max_align_t) {
100 objSizeAndOverhead += alignment - 1;
101 }
102
103 uint32_t allocationSize = std::max(objSizeAndOverhead, fExtraSize * fFib0);
104 fFib0 += fFib1;
105 std::swap(fFib0, fFib1);
106
107 // Round up to a nice size. If > 32K align to 4K boundary else up to max_align_t. The > 32K
108 // heuristic is from the JEMalloc behavior.
109 {
110 uint32_t mask = allocationSize > (1 << 15) ? (1 << 12) - 1 : 16 - 1;
111 allocationSize = (allocationSize + mask) & ~mask;
112 }
113
114 char* newBlock = new char[allocationSize];
115
116 auto previousDtor = fDtorCursor;
117 fCursor = newBlock;
118 fDtorCursor = newBlock;
119 fEnd = fCursor + allocationSize;
120 this->installPtrFooter(NextBlock, previousDtor, 0);
121 }
122
allocObject(uint32_t size,uint32_t alignment)123 char* SkArenaAlloc::allocObject(uint32_t size, uint32_t alignment) {
124 uintptr_t mask = alignment - 1;
125 char* objStart = (char*)((uintptr_t)(fCursor + mask) & ~mask);
126 if ((ptrdiff_t)size > fEnd - objStart) {
127 this->ensureSpace(size, alignment);
128 objStart = (char*)((uintptr_t)(fCursor + mask) & ~mask);
129 }
130 return objStart;
131 }
132
allocObjectWithFooter(uint32_t sizeIncludingFooter,uint32_t alignment)133 char* SkArenaAlloc::allocObjectWithFooter(uint32_t sizeIncludingFooter, uint32_t alignment) {
134 uintptr_t mask = alignment - 1;
135
136 restart:
137 uint32_t skipOverhead = 0;
138 bool needsSkipFooter = fCursor != fDtorCursor;
139 if (needsSkipFooter) {
140 skipOverhead = sizeof(Footer) + sizeof(uint32_t);
141 }
142 char* objStart = (char*)((uintptr_t)(fCursor + skipOverhead + mask) & ~mask);
143 uint32_t totalSize = sizeIncludingFooter + skipOverhead;
144
145 if ((ptrdiff_t)totalSize > fEnd - objStart) {
146 this->ensureSpace(totalSize, alignment);
147 goto restart;
148 }
149
150 SkASSERT((ptrdiff_t)totalSize <= fEnd - objStart);
151
152 // Install a skip footer if needed, thus terminating a run of POD data. The calling code is
153 // responsible for installing the footer after the object.
154 if (needsSkipFooter) {
155 this->installUint32Footer(SkipPod, SkTo<uint32_t>(fCursor - fDtorCursor), 0);
156 }
157
158 return objStart;
159 }
160
161