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