submodule/skia/src/text/gpu/SubRunAllocator.h

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