| /* |
| * Copyright 2021 Google LLC |
| * |
| * Use of this source code is governed by a BSD-style license that can be |
| * found in the LICENSE file. |
| */ |
| |
| #ifndef GrSubRunAllocator_DEFINED |
| #define GrSubRunAllocator_DEFINED |
| |
| #include "include/core/SkSpan.h" |
| #include "src/core/SkArenaAlloc.h" |
| |
| #include <algorithm> |
| #include <memory> |
| |
| // GrBagOfBytes parcels out bytes with a given size and alignment. |
| class GrBagOfBytes { |
| public: |
| GrBagOfBytes(char* block, size_t blockSize, size_t firstHeapAllocation); |
| explicit GrBagOfBytes(size_t firstHeapAllocation = 0); |
| ~GrBagOfBytes(); |
| |
| // Given a requestedSize round up to the smallest size that accounts for all the per block |
| // overhead and alignment. It crashes if requestedSize is negative or too big. |
| static constexpr int PlatformMinimumSizeWithOverhead(int requestedSize, int assumedAlignment) { |
| return MinimumSizeWithOverhead( |
| requestedSize, assumedAlignment, sizeof(Block), kMaxAlignment); |
| } |
| |
| static constexpr int MinimumSizeWithOverhead( |
| int requestedSize, int assumedAlignment, int blockSize, int maxAlignment) { |
| SkASSERT_RELEASE(0 <= requestedSize && requestedSize < kMaxByteSize); |
| SkASSERT_RELEASE(SkIsPow2(assumedAlignment) && SkIsPow2(maxAlignment)); |
| |
| auto alignUp = [](int size, int alignment) {return (size + (alignment - 1)) & -alignment;}; |
| |
| const int minAlignment = std::min(maxAlignment, assumedAlignment); |
| // There are two cases, one easy and one subtle. The easy case is when minAlignment == |
| // maxAlignment. When that happens, the term maxAlignment - minAlignment is zero, and the |
| // block will be placed at the proper alignment because alignUp is properly |
| // aligned. |
| // The subtle case is where minAlignment < maxAlignment. Because |
| // minAlignment < maxAlignment, alignUp(requestedSize, minAlignment) + blockSize does not |
| // guarantee that block can be placed at a maxAlignment address. Block can be placed at |
| // maxAlignment/minAlignment different address to achieve alignment, so we need |
| // to add memory to allow the block to be placed on a maxAlignment address. |
| // For example, if assumedAlignment = 4 and maxAlignment = 16 then block can be placed at |
| // the following address offsets at the end of minimumSize bytes. |
| // 0 * minAlignment = 0 |
| // 1 * minAlignment = 4 |
| // 2 * minAlignment = 8 |
| // 3 * minAlignment = 12 |
| // Following this logic, the equation for the additional bytes is |
| // (maxAlignment/minAlignment - 1) * minAlignment |
| // = maxAlignment - minAlignment. |
| int minimumSize = alignUp(requestedSize, minAlignment) |
| + blockSize |
| + maxAlignment - minAlignment; |
| |
| // If minimumSize is > 32k then round to a 4K boundary unless it is too close to the |
| // maximum int. The > 32K heuristic is from the JEMalloc behavior. |
| constexpr int k32K = (1 << 15); |
| if (minimumSize >= k32K && minimumSize < std::numeric_limits<int>::max() - k4K) { |
| minimumSize = alignUp(minimumSize, k4K); |
| } |
| |
| return minimumSize; |
| } |
| |
| template <int size> |
| using Storage = std::array<char, PlatformMinimumSizeWithOverhead(size, 1)>; |
| |
| // Returns a pointer to memory suitable for holding n Ts. |
| template <typename T> char* allocateBytesFor(int n = 1) { |
| static_assert(alignof(T) <= kMaxAlignment, "Alignment is too big for arena"); |
| static_assert(sizeof(T) < kMaxByteSize, "Size is too big for arena"); |
| constexpr int kMaxN = kMaxByteSize / sizeof(T); |
| SkASSERT_RELEASE(0 <= n && n < kMaxN); |
| |
| int size = n ? n * sizeof(T) : 1; |
| return this->allocateBytes(size, alignof(T)); |
| } |
| |
| void* alignedBytes(int unsafeSize, int unsafeAlignment); |
| |
| private: |
| // The maximum alignment supported by GrBagOfBytes. 16 seems to be a good number for alignment. |
| // If a use case for larger alignments is found, we can turn this into a template parameter. |
| static constexpr int kMaxAlignment = std::max(16, (int)alignof(std::max_align_t)); |
| // The largest size that can be allocated. In larger sizes, the block is rounded up to 4K |
| // chunks. Leave a 4K of slop. |
| static constexpr int k4K = (1 << 12); |
| // This should never overflow with the calculations done on the code. |
| static constexpr int kMaxByteSize = std::numeric_limits<int>::max() - k4K; |
| // The assumed alignment of new char[] given the platform. |
| // There is a bug in Emscripten's allocator that make alignment different than max_align_t. |
| // kAllocationAlignment accounts for this difference. For more information see: |
| // https://github.com/emscripten-core/emscripten/issues/10072 |
| #if !defined(SK_FORCE_8_BYTE_ALIGNMENT) |
| static constexpr int kAllocationAlignment = alignof(std::max_align_t); |
| #else |
| static constexpr int kAllocationAlignment = 8; |
| #endif |
| |
| // The Block starts at the location pointed to by fEndByte. |
| // Beware. Order is important here. The destructor for fPrevious must be called first because |
| // the Block is embedded in fBlockStart. Destructors are run in reverse order. |
| struct Block { |
| Block(char* previous, char* startOfBlock); |
| // The start of the originally allocated bytes. This is the thing that must be deleted. |
| char* const fBlockStart; |
| Block* const fPrevious; |
| }; |
| |
| // Note: fCapacity is the number of bytes remaining, and is subtracted from fEndByte to |
| // generate the location of the object. |
| char* allocateBytes(int size, int alignment) { |
| fCapacity = fCapacity & -alignment; |
| if (fCapacity < size) { |
| this->needMoreBytes(size, alignment); |
| } |
| char* const ptr = fEndByte - fCapacity; |
| SkASSERT(((intptr_t)ptr & (alignment - 1)) == 0); |
| SkASSERT(fCapacity >= size); |
| fCapacity -= size; |
| return ptr; |
| } |
| |
| // Adjust fEndByte and fCapacity give a new block starting at bytes with size. |
| void setupBytesAndCapacity(char* bytes, int size); |
| |
| // Adjust fEndByte and fCapacity to satisfy the size and alignment request. |
| void needMoreBytes(int size, int alignment); |
| |
| // This points to the highest kMaxAlignment address in the allocated block. The address of |
| // the current end of allocated data is given by fEndByte - fCapacity. While the negative side |
| // of this pointer are the bytes to be allocated. The positive side points to the Block for |
| // this memory. In other words, the pointer to the Block structure for these bytes is |
| // reinterpret_cast<Block*>(fEndByte). |
| char* fEndByte{nullptr}; |
| |
| // The number of bytes remaining in this block. |
| int fCapacity{0}; |
| |
| SkFibBlockSizes<kMaxByteSize> fFibProgression; |
| }; |
| |
| // GrSubRunAllocator provides fast allocation where the user takes care of calling the destructors |
| // of the returned pointers, and GrSubRunAllocator takes care of deleting the storage. The |
| // unique_ptrs returned, are to assist in assuring the object's destructor is called. |
| // A note on zero length arrays: according to the standard a pointer must be returned, and it |
| // can't be a nullptr. In such a case, SkArena allocates one byte, but does not initialize it. |
| class GrSubRunAllocator { |
| public: |
| struct Destroyer { |
| template <typename T> |
| void operator()(T* ptr) { ptr->~T(); } |
| }; |
| |
| struct ArrayDestroyer { |
| int n; |
| template <typename T> |
| void operator()(T* ptr) { |
| for (int i = 0; i < n; i++) { ptr[i].~T(); } |
| } |
| }; |
| |
| template<class T> |
| inline static constexpr bool HasNoDestructor = std::is_trivially_destructible<T>::value; |
| |
| GrSubRunAllocator(char* block, int blockSize, int firstHeapAllocation); |
| explicit GrSubRunAllocator(int firstHeapAllocation = 0); |
| |
| template <typename T, typename... Args> T* makePOD(Args&&... args) { |
| static_assert(HasNoDestructor<T>, "This is not POD. Use makeUnique."); |
| char* bytes = fAlloc.template allocateBytesFor<T>(); |
| return new (bytes) T(std::forward<Args>(args)...); |
| } |
| |
| template <typename T, typename... Args> |
| std::unique_ptr<T, Destroyer> makeUnique(Args&&... args) { |
| static_assert(!HasNoDestructor<T>, "This is POD. Use makePOD."); |
| char* bytes = fAlloc.template allocateBytesFor<T>(); |
| return std::unique_ptr<T, Destroyer>{new (bytes) T(std::forward<Args>(args)...)}; |
| } |
| |
| template<typename T> T* makePODArray(int n) { |
| static_assert(HasNoDestructor<T>, "This is not POD. Use makeUniqueArray."); |
| return reinterpret_cast<T*>(fAlloc.template allocateBytesFor<T>(n)); |
| } |
| |
| template<typename T, typename Src, typename Map> |
| SkSpan<T> makePODArray(const Src& src, Map map) { |
| static_assert(HasNoDestructor<T>, "This is not POD. Use makeUniqueArray."); |
| int size = SkTo<int>(src.size()); |
| T* result = this->template makePODArray<T>(size); |
| for (int i = 0; i < size; i++) { |
| new (&result[i]) T(map(src[i])); |
| } |
| return {result, src.size()}; |
| } |
| |
| template<typename T> |
| std::unique_ptr<T[], ArrayDestroyer> makeUniqueArray(int n) { |
| static_assert(!HasNoDestructor<T>, "This is POD. Use makePODArray."); |
| T* array = reinterpret_cast<T*>(fAlloc.template allocateBytesFor<T>(n)); |
| for (int i = 0; i < n; i++) { |
| new (&array[i]) T{}; |
| } |
| return std::unique_ptr<T[], ArrayDestroyer>{array, ArrayDestroyer{n}}; |
| } |
| |
| template<typename T, typename I> |
| std::unique_ptr<T[], ArrayDestroyer> makeUniqueArray(int n, I initializer) { |
| static_assert(!HasNoDestructor<T>, "This is POD. Use makePODArray."); |
| T* array = reinterpret_cast<T*>(fAlloc.template allocateBytesFor<T>(n)); |
| for (int i = 0; i < n; i++) { |
| new (&array[i]) T(initializer(i)); |
| } |
| return std::unique_ptr<T[], ArrayDestroyer>{array, ArrayDestroyer{n}}; |
| } |
| |
| void* alignedBytes(int size, int alignment); |
| |
| private: |
| GrBagOfBytes fAlloc; |
| }; |
| #endif // GrSubRunAllocator_DEFINED |