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