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#ifndef SkArenaAlloc_DEFINED 9#define SkArenaAlloc_DEFINED 10 11#include "SkRefCnt.h" 12#include "SkTFitsIn.h" 13#include "SkTypes.h" 14#include <cstddef> 15#include <new> 16#include <type_traits> 17#include <utility> 18#include <vector> 19 20// SkArenaAlloc allocates object and destroys the allocated objects when destroyed. It's designed 21// to minimize the number of underlying block allocations. SkArenaAlloc allocates first out of an 22// (optional) user-provided block of memory, and when that's exhausted it allocates on the heap, 23// starting with an allocation of extraSize bytes. If your data (plus a small overhead) fits in 24// the user-provided block, SkArenaAlloc never uses the heap, and if it fits in extraSize bytes, 25// it'll use the heap only once. If you pass extraSize = 0, it allocates blocks for each call to 26// make<T>. 27// 28// Examples: 29// 30// char block[mostCasesSize]; 31// SkArenaAlloc arena(block, almostAllCasesSize); 32// 33// If mostCasesSize is too large for the stack, you can use the following pattern. 34// 35// std::unique_ptr<char[]> block{new char[mostCasesSize]}; 36// SkArenaAlloc arena(block.get(), mostCasesSize, almostAllCasesSize); 37// 38// If the program only sometimes allocates memory, use the following. 39// 40// SkArenaAlloc arena(nullptr, 0, almostAllCasesSize); 41// 42// The storage does not necessarily need to be on the stack. Embedding the storage in a class also 43// works. 44// 45// class Foo { 46// char storage[mostCasesSize]; 47// SkArenaAlloc arena (storage, almostAllCasesSize); 48// }; 49// 50// In addition, the system is optimized to handle POD data including arrays of PODs (where 51// POD is really data with no destructors). For POD data it has zero overhead per item, and a 52// typical block overhead of 8 bytes. For non-POD objects there is a per item overhead of 4 bytes. 53// For arrays of non-POD objects there is a per array overhead of typically 8 bytes. There is an 54// addition overhead when switching from POD data to non-POD data of typically 8 bytes. 55// 56// You can track memory use by adding SkArenaAlloc::kTrack as the last parameter to any constructor. 57// 58// char storage[someNumber]; 59// SkArenaAlloc alloc{storage, SkArenaAlloc::kTrack}; 60// 61// This will print out a line for every destructor or reset call that has the total memory 62// allocated, the total slop (the unused portion of a block), and the slop of the last block. 63// 64// If additional blocks are needed they are increased exponentially. This strategy bounds the 65// recursion of the RunDtorsOnBlock to be limited to O(log size-of-memory). Block size grow using 66// the Fibonacci sequence which means that for 2^32 memory there are 48 allocations, and for 2^48 67// there are 71 allocations. 68class SkArenaAlloc { 69public: 70 enum Tracking {kDontTrack, kTrack}; 71 SkArenaAlloc(char* block, size_t size, size_t, Tracking tracking = kDontTrack); 72 73 SkArenaAlloc(size_t extraSize, Tracking tracking = kDontTrack) 74 : SkArenaAlloc(nullptr, 0, extraSize, tracking) 75 {} 76 77 ~SkArenaAlloc(); 78 79 template <typename T, typename... Args> 80 T* make(Args&&... args) { 81 uint32_t size = SkTo<uint32_t>(sizeof(T)); 82 uint32_t alignment = SkTo<uint32_t>(alignof(T)); 83 char* objStart; 84 if (skstd::is_trivially_destructible<T>::value) { 85 objStart = this->allocObject(size, alignment); 86 fCursor = objStart + size; 87 } else { 88 objStart = this->allocObjectWithFooter(size + sizeof(Footer), alignment); 89 // Can never be UB because max value is alignof(T). 90 uint32_t padding = SkTo<uint32_t>(objStart - fCursor); 91 92 // Advance to end of object to install footer. 93 fCursor = objStart + size; 94 FooterAction* releaser = [](char* objEnd) { 95 char* objStart = objEnd - (sizeof(T) + sizeof(Footer)); 96 ((T*)objStart)->~T(); 97 return objStart; 98 }; 99 this->installFooter(releaser, padding); 100 } 101 102 // This must be last to make objects with nested use of this allocator work. 103 return new(objStart) T(std::forward<Args>(args)...); 104 } 105 106 template <typename T, typename... Args> 107 sk_sp<T> makeSkSp(Args&&... args) { 108 SkASSERT(SkTFitsIn<uint32_t>(sizeof(T))); 109 110 // The arena takes a ref for itself to account for the destructor. The sk_sp count can't 111 // become zero or the sk_sp will try to call free on the pointer. 112 return sk_sp<T>(SkRef(this->make<T>(std::forward<Args>(args)...))); 113 } 114 115 template <typename T> 116 T* makeArrayDefault(size_t count) { 117 uint32_t safeCount = SkTo<uint32_t>(count); 118 T* array = (T*)this->commonArrayAlloc<T>(safeCount); 119 120 // If T is primitive then no initialization takes place. 121 for (size_t i = 0; i < safeCount; i++) { 122 new (&array[i]) T; 123 } 124 return array; 125 } 126 127 template <typename T> 128 T* makeArray(size_t count) { 129 uint32_t safeCount = SkTo<uint32_t>(count); 130 T* array = (T*)this->commonArrayAlloc<T>(safeCount); 131 132 // If T is primitive then the memory is initialized. For example, an array of chars will 133 // be zeroed. 134 for (size_t i = 0; i < safeCount; i++) { 135 new (&array[i]) T(); 136 } 137 return array; 138 } 139 140 // Destroy all allocated objects, free any heap allocations. 141 void reset(); 142 143private: 144 using Footer = int64_t; 145 using FooterAction = char* (char*); 146 147 static char* SkipPod(char* footerEnd); 148 static void RunDtorsOnBlock(char* footerEnd); 149 static char* NextBlock(char* footerEnd); 150 151 void installFooter(FooterAction* releaser, uint32_t padding); 152 void installUint32Footer(FooterAction* action, uint32_t value, uint32_t padding); 153 void installPtrFooter(FooterAction* action, char* ptr, uint32_t padding); 154 155 void ensureSpace(uint32_t size, uint32_t alignment); 156 157 char* allocObject(uint32_t size, uint32_t alignment) { 158 uintptr_t mask = alignment - 1; 159 uintptr_t alignedOffset = (~reinterpret_cast<uintptr_t>(fCursor) + 1) & mask; 160 uintptr_t totalSize = size + alignedOffset; 161 if (totalSize < size) { 162 SK_ABORT("The total size of allocation overflowed uintptr_t."); 163 } 164 if (totalSize > static_cast<uintptr_t>(fEnd - fCursor)) { 165 this->ensureSpace(size, alignment); 166 alignedOffset = (~reinterpret_cast<uintptr_t>(fCursor) + 1) & mask; 167 } 168 return fCursor + alignedOffset; 169 } 170 171 char* allocObjectWithFooter(uint32_t sizeIncludingFooter, uint32_t alignment); 172 173 template <typename T> 174 char* commonArrayAlloc(uint32_t count) { 175 char* objStart; 176 SkASSERT_RELEASE(count <= std::numeric_limits<uint32_t>::max() / sizeof(T)); 177 uint32_t arraySize = SkTo<uint32_t>(count * sizeof(T)); 178 uint32_t alignment = SkTo<uint32_t>(alignof(T)); 179 180 if (skstd::is_trivially_destructible<T>::value) { 181 objStart = this->allocObject(arraySize, alignment); 182 fCursor = objStart + arraySize; 183 } else { 184 constexpr uint32_t overhead = sizeof(Footer) + sizeof(uint32_t); 185 SkASSERT_RELEASE(arraySize <= std::numeric_limits<uint32_t>::max() - overhead); 186 uint32_t totalSize = arraySize + overhead; 187 objStart = this->allocObjectWithFooter(totalSize, alignment); 188 189 // Can never be UB because max value is alignof(T). 190 uint32_t padding = SkTo<uint32_t>(objStart - fCursor); 191 192 // Advance to end of array to install footer.? 193 fCursor = objStart + arraySize; 194 this->installUint32Footer( 195 [](char* footerEnd) { 196 char* objEnd = footerEnd - (sizeof(Footer) + sizeof(uint32_t)); 197 uint32_t count; 198 memmove(&count, objEnd, sizeof(uint32_t)); 199 char* objStart = objEnd - count * sizeof(T); 200 T* array = (T*) objStart; 201 for (uint32_t i = 0; i < count; i++) { 202 array[i].~T(); 203 } 204 return objStart; 205 }, 206 SkTo<uint32_t>(count), 207 padding); 208 } 209 210 return objStart; 211 } 212 213 char* fDtorCursor; 214 char* fCursor; 215 char* fEnd; 216 char* const fFirstBlock; 217 const uint32_t fFirstSize; 218 const uint32_t fExtraSize; 219 220 // Track some useful stats. Track stats if fTotalSlop is >= 0; 221 uint32_t fTotalAlloc { 0}; 222 int32_t fTotalSlop {-1}; 223 224 // Use the Fibonacci sequence as the growth factor for block size. The size of the block 225 // allocated is fFib0 * fExtraSize. Using 2 ^ n * fExtraSize had too much slop for Android. 226 uint32_t fFib0 {1}, fFib1 {1}; 227}; 228 229// Helper for defining allocators with inline/reserved storage. 230// For argument declarations, stick to the base type (SkArenaAlloc). 231template <size_t InlineStorageSize> 232class SkSTArenaAlloc : public SkArenaAlloc { 233public: 234 explicit SkSTArenaAlloc(size_t extraSize = InlineStorageSize, Tracking tracking = kDontTrack) 235 : INHERITED(fInlineStorage, InlineStorageSize, extraSize, tracking) {} 236 237private: 238 char fInlineStorage[InlineStorageSize]; 239 240 using INHERITED = SkArenaAlloc; 241}; 242 243#endif // SkArenaAlloc_DEFINED 244