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. 60class SkArenaAlloc { 61public: 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 139private: 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