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. 68 class SkArenaAlloc { 69 public: 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 143 private: 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). 231 template <size_t InlineStorageSize> 232 class SkSTArenaAlloc : public SkArenaAlloc { 233 public: 234 explicit SkSTArenaAlloc(size_t extraSize = InlineStorageSize, Tracking tracking = kDontTrack) 235 : INHERITED(fInlineStorage, InlineStorageSize, extraSize, tracking) {} 236 237 private: 238 char fInlineStorage[InlineStorageSize]; 239 240 using INHERITED = SkArenaAlloc; 241 }; 242 243 #endif // SkArenaAlloc_DEFINED 244