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 // If additional blocks are needed they are increased exponentially. This strategy bounds the 57 // recursion of the RunDtorsOnBlock to be limited to O(log size-of-memory). Block size grow using 58 // the Fibonacci sequence which means that for 2^32 memory there are 48 allocations, and for 2^48 59 // there are 71 allocations. 60 class SkArenaAlloc { 61 public: 62 SkArenaAlloc(char* block, size_t size, size_t extraSize = 0); 63 64 template <size_t kSize> 65 SkArenaAlloc(char (&block)[kSize], size_t extraSize = kSize) 66 : SkArenaAlloc(block, kSize, extraSize) 67 {} 68 69 SkArenaAlloc(size_t extraSize) 70 : SkArenaAlloc(nullptr, 0, extraSize) 71 {} 72 73 ~SkArenaAlloc(); 74 75 template <typename T, typename... Args> 76 T* make(Args&&... args) { 77 uint32_t size = SkTo<uint32_t>(sizeof(T)); 78 uint32_t alignment = SkTo<uint32_t>(alignof(T)); 79 char* objStart; 80 if (skstd::is_trivially_destructible<T>::value) { 81 objStart = this->allocObject(size, alignment); 82 fCursor = objStart + size; 83 } else { 84 objStart = this->allocObjectWithFooter(size + sizeof(Footer), alignment); 85 // Can never be UB because max value is alignof(T). 86 uint32_t padding = SkTo<uint32_t>(objStart - fCursor); 87 88 // Advance to end of object to install footer. 89 fCursor = objStart + size; 90 FooterAction* releaser = [](char* objEnd) { 91 char* objStart = objEnd - (sizeof(T) + sizeof(Footer)); 92 ((T*)objStart)->~T(); 93 return objStart; 94 }; 95 this->installFooter(releaser, padding); 96 } 97 98 // This must be last to make objects with nested use of this allocator work. 99 return new(objStart) T(std::forward<Args>(args)...); 100 } 101 102 template <typename T, typename... Args> 103 sk_sp<T> makeSkSp(Args&&... args) { 104 SkASSERT(SkTFitsIn<uint32_t>(sizeof(T))); 105 106 // The arena takes a ref for itself to account for the destructor. The sk_sp count can't 107 // become zero or the sk_sp will try to call free on the pointer. 108 return sk_sp<T>(SkRef(this->make<T>(std::forward<Args>(args)...))); 109 } 110 111 template <typename T> 112 T* makeArrayDefault(size_t count) { 113 uint32_t safeCount = SkTo<uint32_t>(count); 114 T* array = (T*)this->commonArrayAlloc<T>(safeCount); 115 116 // If T is primitive then no initialization takes place. 117 for (size_t i = 0; i < safeCount; i++) { 118 new (&array[i]) T; 119 } 120 return array; 121 } 122 123 template <typename T> 124 T* makeArray(size_t count) { 125 uint32_t safeCount = SkTo<uint32_t>(count); 126 T* array = (T*)this->commonArrayAlloc<T>(safeCount); 127 128 // If T is primitive then the memory is initialized. For example, an array of chars will 129 // be zeroed. 130 for (size_t i = 0; i < safeCount; i++) { 131 new (&array[i]) T(); 132 } 133 return array; 134 } 135 136 // Destroy all allocated objects, free any heap allocations. 137 void reset(); 138 139 private: 140 using Footer = int64_t; 141 using FooterAction = char* (char*); 142 143 static char* SkipPod(char* footerEnd); 144 static void RunDtorsOnBlock(char* footerEnd); 145 static char* NextBlock(char* footerEnd); 146 147 void installFooter(FooterAction* releaser, uint32_t padding); 148 void installUint32Footer(FooterAction* action, uint32_t value, uint32_t padding); 149 void installPtrFooter(FooterAction* action, char* ptr, uint32_t padding); 150 151 void ensureSpace(uint32_t size, uint32_t alignment); 152 153 char* allocObject(uint32_t size, uint32_t alignment); 154 155 char* allocObjectWithFooter(uint32_t sizeIncludingFooter, uint32_t alignment); 156 157 template <typename T> 158 char* commonArrayAlloc(uint32_t count) { 159 char* objStart; 160 uint32_t arraySize = SkTo<uint32_t>(count * sizeof(T)); 161 uint32_t alignment = SkTo<uint32_t>(alignof(T)); 162 163 if (skstd::is_trivially_destructible<T>::value) { 164 objStart = this->allocObject(arraySize, alignment); 165 fCursor = objStart + arraySize; 166 } else { 167 uint32_t totalSize = arraySize + sizeof(Footer) + sizeof(uint32_t); 168 objStart = this->allocObjectWithFooter(totalSize, alignment); 169 170 // Can never be UB because max value is alignof(T). 171 uint32_t padding = SkTo<uint32_t>(objStart - fCursor); 172 173 // Advance to end of array to install footer.? 174 fCursor = objStart + arraySize; 175 this->installUint32Footer( 176 [](char* footerEnd) { 177 char* objEnd = footerEnd - (sizeof(Footer) + sizeof(uint32_t)); 178 uint32_t count; 179 memmove(&count, objEnd, sizeof(uint32_t)); 180 char* objStart = objEnd - count * sizeof(T); 181 T* array = (T*) objStart; 182 for (uint32_t i = 0; i < count; i++) { 183 array[i].~T(); 184 } 185 return objStart; 186 }, 187 SkTo<uint32_t>(count), 188 padding); 189 } 190 191 return objStart; 192 } 193 194 char* fDtorCursor; 195 char* fCursor; 196 char* fEnd; 197 char* const fFirstBlock; 198 const uint32_t fFirstSize; 199 const uint32_t fExtraSize; 200 // Use the Fibonacci sequence as the growth factor for block size. The size of the block 201 // allocated is fFib0 * fExtraSize. Using 2 ^ n * fExtraSize had too much slop for Android. 202 uint32_t fFib0 {1}, fFib1 {1}; 203 }; 204 205 #endif//SkFixedAlloc_DEFINED 206
