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 // Only use makeBytesAlignedTo if none of the typed variants are impractical to use. 141 void* makeBytesAlignedTo(size_t size, size_t align) { 142 auto objStart = this->allocObject(SkTo<uint32_t>(size), SkTo<uint32_t>(align)); 143 fCursor = objStart + size; 144 return objStart; 145 } 146 147 // Destroy all allocated objects, free any heap allocations. 148 void reset(); 149 150 private: 151 using Footer = int64_t; 152 using FooterAction = char* (char*); 153 154 static char* SkipPod(char* footerEnd); 155 static void RunDtorsOnBlock(char* footerEnd); 156 static char* NextBlock(char* footerEnd); 157 158 void installFooter(FooterAction* releaser, uint32_t padding); 159 void installUint32Footer(FooterAction* action, uint32_t value, uint32_t padding); 160 void installPtrFooter(FooterAction* action, char* ptr, uint32_t padding); 161 162 void ensureSpace(uint32_t size, uint32_t alignment); 163 164 char* allocObject(uint32_t size, uint32_t alignment) { 165 uintptr_t mask = alignment - 1; 166 uintptr_t alignedOffset = (~reinterpret_cast<uintptr_t>(fCursor) + 1) & mask; 167 uintptr_t totalSize = size + alignedOffset; 168 if (totalSize < size) { 169 SK_ABORT("The total size of allocation overflowed uintptr_t."); 170 } 171 if (totalSize > static_cast<uintptr_t>(fEnd - fCursor)) { 172 this->ensureSpace(size, alignment); 173 alignedOffset = (~reinterpret_cast<uintptr_t>(fCursor) + 1) & mask; 174 } 175 return fCursor + alignedOffset; 176 } 177 178 char* allocObjectWithFooter(uint32_t sizeIncludingFooter, uint32_t alignment); 179 180 template <typename T> 181 char* commonArrayAlloc(uint32_t count) { 182 char* objStart; 183 SkASSERT_RELEASE(count <= std::numeric_limits<uint32_t>::max() / sizeof(T)); 184 uint32_t arraySize = SkTo<uint32_t>(count * sizeof(T)); 185 uint32_t alignment = SkTo<uint32_t>(alignof(T)); 186 187 if (skstd::is_trivially_destructible<T>::value) { 188 objStart = this->allocObject(arraySize, alignment); 189 fCursor = objStart + arraySize; 190 } else { 191 constexpr uint32_t overhead = sizeof(Footer) + sizeof(uint32_t); 192 SkASSERT_RELEASE(arraySize <= std::numeric_limits<uint32_t>::max() - overhead); 193 uint32_t totalSize = arraySize + overhead; 194 objStart = this->allocObjectWithFooter(totalSize, alignment); 195 196 // Can never be UB because max value is alignof(T). 197 uint32_t padding = SkTo<uint32_t>(objStart - fCursor); 198 199 // Advance to end of array to install footer.? 200 fCursor = objStart + arraySize; 201 this->installUint32Footer( 202 [](char* footerEnd) { 203 char* objEnd = footerEnd - (sizeof(Footer) + sizeof(uint32_t)); 204 uint32_t count; 205 memmove(&count, objEnd, sizeof(uint32_t)); 206 char* objStart = objEnd - count * sizeof(T); 207 T* array = (T*) objStart; 208 for (uint32_t i = 0; i < count; i++) { 209 array[i].~T(); 210 } 211 return objStart; 212 }, 213 SkTo<uint32_t>(count), 214 padding); 215 } 216 217 return objStart; 218 } 219 220 char* fDtorCursor; 221 char* fCursor; 222 char* fEnd; 223 char* const fFirstBlock; 224 const uint32_t fFirstSize; 225 const uint32_t fExtraSize; 226 227 // Track some useful stats. Track stats if fTotalSlop is >= 0; 228 uint32_t fTotalAlloc { 0}; 229 int32_t fTotalSlop {-1}; 230 231 // Use the Fibonacci sequence as the growth factor for block size. The size of the block 232 // allocated is fFib0 * fExtraSize. Using 2 ^ n * fExtraSize had too much slop for Android. 233 uint32_t fFib0 {1}, fFib1 {1}; 234 }; 235 236 // Helper for defining allocators with inline/reserved storage. 237 // For argument declarations, stick to the base type (SkArenaAlloc). 238 template <size_t InlineStorageSize> 239 class SkSTArenaAlloc : public SkArenaAlloc { 240 public: 241 explicit SkSTArenaAlloc(size_t extraSize = InlineStorageSize, Tracking tracking = kDontTrack) 242 : INHERITED(fInlineStorage, InlineStorageSize, extraSize, tracking) {} 243 244 private: 245 char fInlineStorage[InlineStorageSize]; 246 247 using INHERITED = SkArenaAlloc; 248 }; 249 250 #endif // SkArenaAlloc_DEFINED 251