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