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 13static char* end_chain(char*) { return nullptr; } 14 15SkArenaAlloc::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 39SkArenaAlloc::~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 49void SkArenaAlloc::reset() { 50 this->~SkArenaAlloc(); 51 new (this) SkArenaAlloc{fFirstBlock, fFirstSize, fExtraSize, 52 fTotalSlop < 0 ? kDontTrack : kTrack}; 53} 54 55void 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 67void 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 73char* 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 80void 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 92char* 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 101void 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 107void 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 155char* SkArenaAlloc::allocObjectWithFooter(uint32_t sizeIncludingFooter, uint32_t alignment) { 156 uintptr_t mask = alignment - 1; 157 158restart: 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