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