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 SkFixedAlloc_DEFINED 9 #define SkFixedAlloc_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 char* objStart = (char*)((uintptr_t)(fCursor + mask) & ~mask); 160 if ((ptrdiff_t)size > fEnd - objStart) { 161 this->ensureSpace(size, alignment); 162 objStart = (char*)((uintptr_t)(fCursor + mask) & ~mask); 163 } 164 return objStart; 165 } 166 167 char* allocObjectWithFooter(uint32_t sizeIncludingFooter, uint32_t alignment); 168 169 template <typename T> 170 char* commonArrayAlloc(uint32_t count) { 171 char* objStart; 172 uint32_t arraySize = SkTo<uint32_t>(count * sizeof(T)); 173 uint32_t alignment = SkTo<uint32_t>(alignof(T)); 174 175 if (skstd::is_trivially_destructible<T>::value) { 176 objStart = this->allocObject(arraySize, alignment); 177 fCursor = objStart + arraySize; 178 } else { 179 uint32_t totalSize = arraySize + sizeof(Footer) + sizeof(uint32_t); 180 objStart = this->allocObjectWithFooter(totalSize, alignment); 181 182 // Can never be UB because max value is alignof(T). 183 uint32_t padding = SkTo<uint32_t>(objStart - fCursor); 184 185 // Advance to end of array to install footer.? 186 fCursor = objStart + arraySize; 187 this->installUint32Footer( 188 [](char* footerEnd) { 189 char* objEnd = footerEnd - (sizeof(Footer) + sizeof(uint32_t)); 190 uint32_t count; 191 memmove(&count, objEnd, sizeof(uint32_t)); 192 char* objStart = objEnd - count * sizeof(T); 193 T* array = (T*) objStart; 194 for (uint32_t i = 0; i < count; i++) { 195 array[i].~T(); 196 } 197 return objStart; 198 }, 199 SkTo<uint32_t>(count), 200 padding); 201 } 202 203 return objStart; 204 } 205 206 char* fDtorCursor; 207 char* fCursor; 208 char* fEnd; 209 char* const fFirstBlock; 210 const uint32_t fFirstSize; 211 const uint32_t fExtraSize; 212 213 // Track some useful stats. Track stats if fTotalSlop is >= 0; 214 uint32_t fTotalAlloc { 0}; 215 int32_t fTotalSlop {-1}; 216 217 // Use the Fibonacci sequence as the growth factor for block size. The size of the block 218 // allocated is fFib0 * fExtraSize. Using 2 ^ n * fExtraSize had too much slop for Android. 219 uint32_t fFib0 {1}, fFib1 {1}; 220 }; 221 222 // Helper for defining allocators with inline/reserved storage. 223 // For argument declarations, stick to the base type (SkArenaAlloc). 224 template <size_t InlineStorageSize> 225 class SkSTArenaAlloc : public SkArenaAlloc { 226 public: 227 explicit SkSTArenaAlloc(size_t extraSize = InlineStorageSize, Tracking tracking = kDontTrack) 228 : INHERITED(fInlineStorage, InlineStorageSize, extraSize, tracking) {} 229 230 private: 231 char fInlineStorage[InlineStorageSize]; 232 233 using INHERITED = SkArenaAlloc; 234 }; 235 236 #endif//SkFixedAlloc_DEFINED 237