1 /* 2 * Copyright 2021 Google LLC 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 GrSubRunAllocator_DEFINED 9 #define GrSubRunAllocator_DEFINED 10 11 #include "include/core/SkSpan.h" 12 #include "src/core/SkArenaAlloc.h" 13 14 #include <algorithm> 15 #include <memory> 16 17 // GrBagOfBytes parcels out bytes with a given size and alignment. 18 class GrBagOfBytes { 19 public: 20 GrBagOfBytes(char* block, size_t blockSize, size_t firstHeapAllocation); 21 explicit GrBagOfBytes(size_t firstHeapAllocation = 0); 22 ~GrBagOfBytes(); 23 24 // Given a requestedSize round up to the smallest size that accounts for all the per block 25 // overhead and alignment. It crashes if requestedSize is negative or too big. PlatformMinimumSizeWithOverhead(int requestedSize,int assumedAlignment)26 static constexpr int PlatformMinimumSizeWithOverhead(int requestedSize, int assumedAlignment) { 27 return MinimumSizeWithOverhead( 28 requestedSize, assumedAlignment, sizeof(Block), kMaxAlignment); 29 } 30 MinimumSizeWithOverhead(int requestedSize,int assumedAlignment,int blockSize,int maxAlignment)31 static constexpr int MinimumSizeWithOverhead( 32 int requestedSize, int assumedAlignment, int blockSize, int maxAlignment) { 33 SkASSERT_RELEASE(0 <= requestedSize && requestedSize < kMaxByteSize); 34 SkASSERT_RELEASE(SkIsPow2(assumedAlignment) && SkIsPow2(maxAlignment)); 35 36 auto alignUp = [](int size, int alignment) {return (size + (alignment - 1)) & -alignment;}; 37 38 const int minAlignment = std::min(maxAlignment, assumedAlignment); 39 // There are two cases, one easy and one subtle. The easy case is when minAlignment == 40 // maxAlignment. When that happens, the term maxAlignment - minAlignment is zero, and the 41 // block will be placed at the proper alignment because alignUp is properly 42 // aligned. 43 // The subtle case is where minAlignment < maxAlignment. Because 44 // minAlignment < maxAlignment, alignUp(requestedSize, minAlignment) + blockSize does not 45 // guarantee that block can be placed at a maxAlignment address. Block can be placed at 46 // maxAlignment/minAlignment different address to achieve alignment, so we need 47 // to add memory to allow the block to be placed on a maxAlignment address. 48 // For example, if assumedAlignment = 4 and maxAlignment = 16 then block can be placed at 49 // the following address offsets at the end of minimumSize bytes. 50 // 0 * minAlignment = 0 51 // 1 * minAlignment = 4 52 // 2 * minAlignment = 8 53 // 3 * minAlignment = 12 54 // Following this logic, the equation for the additional bytes is 55 // (maxAlignment/minAlignment - 1) * minAlignment 56 // = maxAlignment - minAlignment. 57 int minimumSize = alignUp(requestedSize, minAlignment) 58 + blockSize 59 + maxAlignment - minAlignment; 60 61 // If minimumSize is > 32k then round to a 4K boundary unless it is too close to the 62 // maximum int. The > 32K heuristic is from the JEMalloc behavior. 63 constexpr int k32K = (1 << 15); 64 if (minimumSize >= k32K && minimumSize < std::numeric_limits<int>::max() - k4K) { 65 minimumSize = alignUp(minimumSize, k4K); 66 } 67 68 return minimumSize; 69 } 70 71 template <int size> 72 using Storage = std::array<char, PlatformMinimumSizeWithOverhead(size, 1)>; 73 74 // Returns a pointer to memory suitable for holding n Ts. 75 template <typename T> char* allocateBytesFor(int n = 1) { 76 static_assert(alignof(T) <= kMaxAlignment, "Alignment is too big for arena"); 77 static_assert(sizeof(T) < kMaxByteSize, "Size is too big for arena"); 78 constexpr int kMaxN = kMaxByteSize / sizeof(T); 79 SkASSERT_RELEASE(0 <= n && n < kMaxN); 80 81 int size = n ? n * sizeof(T) : 1; 82 return this->allocateBytes(size, alignof(T)); 83 } 84 85 void* alignedBytes(int unsafeSize, int unsafeAlignment); 86 87 private: 88 // 16 seems to be a good number for alignment. If a use case for larger alignments is found, 89 // we can turn this into a template parameter. 90 static constexpr int kMaxAlignment = std::max(16, (int)alignof(max_align_t)); 91 // The largest size that can be allocated. In larger sizes, the block is rounded up to 4K 92 // chunks. Leave a 4K of slop. 93 static constexpr int k4K = (1 << 12); 94 // This should never overflow with the calculations done on the code. 95 static constexpr int kMaxByteSize = std::numeric_limits<int>::max() - k4K; 96 97 // The Block starts at the location pointed to by fEndByte. 98 // Beware. Order is important here. The destructor for fPrevious must be called first because 99 // the Block is embedded in fBlockStart. Destructors are run in reverse order. 100 struct Block { 101 Block(char* previous, char* startOfBlock); 102 // The start of the originally allocated bytes. This is the thing that must be deleted. 103 char* const fBlockStart; 104 Block* const fPrevious; 105 }; 106 107 // Note: fCapacity is the number of bytes remaining, and is subtracted from fEndByte to 108 // generate the location of the object. allocateBytes(int size,int alignment)109 char* allocateBytes(int size, int alignment) { 110 fCapacity = fCapacity & -alignment; 111 if (fCapacity < size) { 112 this->needMoreBytes(size, alignment); 113 } 114 char* const ptr = fEndByte - fCapacity; 115 SkASSERT(((intptr_t)ptr & (alignment - 1)) == 0); 116 SkASSERT(fCapacity >= size); 117 fCapacity -= size; 118 return ptr; 119 } 120 121 // Adjust fEndByte and fCapacity give a new block starting at bytes with size. 122 void setupBytesAndCapacity(char* bytes, int size); 123 124 // Adjust fEndByte and fCapacity to satisfy the size and alignment request. 125 void needMoreBytes(int size, int alignment); 126 127 // This points to the highest kMaxAlignment address in the allocated block. The address of 128 // the current end of allocated data is given by fEndByte - fCapacity. While the negative side 129 // of this pointer are the bytes to be allocated. The positive side points to the Block for 130 // this memory. In other words, the pointer to the Block structure for these bytes is 131 // reinterpret_cast<Block*>(fEndByte). 132 char* fEndByte{nullptr}; 133 134 // The number of bytes remaining in this block. 135 int fCapacity{0}; 136 137 SkFibBlockSizes<kMaxByteSize> fFibProgression; 138 }; 139 140 // GrSubRunAllocator provides fast allocation where the user takes care of calling the destructors 141 // of the returned pointers, and GrSubRunAllocator takes care of deleting the storage. The 142 // unique_ptrs returned, are to assist in assuring the object's destructor is called. 143 // A note on zero length arrays: according to the standard a pointer must be returned, and it 144 // can't be a nullptr. In such a case, SkArena allocates one byte, but does not initialize it. 145 class GrSubRunAllocator { 146 public: 147 struct Destroyer { 148 template <typename T> operatorDestroyer149 void operator()(T* ptr) { ptr->~T(); } 150 }; 151 152 struct ArrayDestroyer { 153 int n; 154 template <typename T> operatorArrayDestroyer155 void operator()(T* ptr) { 156 for (int i = 0; i < n; i++) { ptr[i].~T(); } 157 } 158 }; 159 160 template<class T> 161 inline static constexpr bool HasNoDestructor = std::is_trivially_destructible<T>::value; 162 163 GrSubRunAllocator(char* block, int blockSize, int firstHeapAllocation); 164 explicit GrSubRunAllocator(int firstHeapAllocation = 0); 165 makePOD(Args &&...args)166 template <typename T, typename... Args> T* makePOD(Args&&... args) { 167 static_assert(HasNoDestructor<T>, "This is not POD. Use makeUnique."); 168 char* bytes = fAlloc.template allocateBytesFor<T>(); 169 return new (bytes) T(std::forward<Args>(args)...); 170 } 171 172 template <typename T, typename... Args> makeUnique(Args &&...args)173 std::unique_ptr<T, Destroyer> makeUnique(Args&&... args) { 174 static_assert(!HasNoDestructor<T>, "This is POD. Use makePOD."); 175 char* bytes = fAlloc.template allocateBytesFor<T>(); 176 return std::unique_ptr<T, Destroyer>{new (bytes) T(std::forward<Args>(args)...)}; 177 } 178 makePODArray(int n)179 template<typename T> T* makePODArray(int n) { 180 static_assert(HasNoDestructor<T>, "This is not POD. Use makeUniqueArray."); 181 return reinterpret_cast<T*>(fAlloc.template allocateBytesFor<T>(n)); 182 } 183 184 template<typename T, typename Src, typename Map> makePODArray(const Src & src,Map map)185 SkSpan<T> makePODArray(const Src& src, Map map) { 186 static_assert(HasNoDestructor<T>, "This is not POD. Use makeUniqueArray."); 187 int size = SkTo<int>(src.size()); 188 T* result = this->template makePODArray<T>(size); 189 for (int i = 0; i < size; i++) { 190 new (&result[i]) T(map(src[i])); 191 } 192 return {result, src.size()}; 193 } 194 195 template<typename T> makeUniqueArray(int n)196 std::unique_ptr<T[], ArrayDestroyer> makeUniqueArray(int n) { 197 static_assert(!HasNoDestructor<T>, "This is POD. Use makePODArray."); 198 T* array = reinterpret_cast<T*>(fAlloc.template allocateBytesFor<T>(n)); 199 for (int i = 0; i < n; i++) { 200 new (&array[i]) T{}; 201 } 202 return std::unique_ptr<T[], ArrayDestroyer>{array, ArrayDestroyer{n}}; 203 } 204 205 template<typename T, typename I> makeUniqueArray(int n,I initializer)206 std::unique_ptr<T[], ArrayDestroyer> makeUniqueArray(int n, I initializer) { 207 static_assert(!HasNoDestructor<T>, "This is POD. Use makePODArray."); 208 T* array = reinterpret_cast<T*>(fAlloc.template allocateBytesFor<T>(n)); 209 for (int i = 0; i < n; i++) { 210 new (&array[i]) T(initializer(i)); 211 } 212 return std::unique_ptr<T[], ArrayDestroyer>{array, ArrayDestroyer{n}}; 213 } 214 215 void* alignedBytes(int size, int alignment); 216 217 private: 218 GrBagOfBytes fAlloc; 219 }; 220 #endif // GrSubRunAllocator_DEFINED 221