| /* |
| * Copyright 2020 Google LLC |
| * |
| * Use of this source code is governed by a BSD-style license that can be |
| * found in the LICENSE file. |
| */ |
| |
| #ifndef SkBlockAllocator_DEFINED |
| #define SkBlockAllocator_DEFINED |
| |
| #include "include/private/base/SkAlign.h" |
| #include "include/private/base/SkAssert.h" |
| #include "include/private/base/SkDebug.h" |
| #include "include/private/base/SkMacros.h" |
| #include "include/private/base/SkMath.h" |
| #include "include/private/base/SkNoncopyable.h" |
| #include "src/base/SkASAN.h" |
| |
| #include <algorithm> |
| #include <cstddef> |
| #include <cstdint> |
| #include <limits> |
| #include <new> |
| #include <type_traits> |
| |
| /** |
| * SkBlockAllocator provides low-level support for a block allocated arena with a dynamic tail that |
| * tracks space reservations within each block. Its APIs provide the ability to reserve space, |
| * resize reservations, and release reservations. It will automatically create new blocks if needed |
| * and destroy all remaining blocks when it is destructed. It assumes that anything allocated within |
| * its blocks has its destructors called externally. It is recommended that SkBlockAllocator is |
| * wrapped by a higher-level allocator that uses the low-level APIs to implement a simpler, |
| * purpose-focused API w/o having to worry as much about byte-level concerns. |
| * |
| * SkBlockAllocator has no limit to its total size, but each allocation is limited to 512MB (which |
| * should be sufficient for Skia's use cases). This upper allocation limit allows all internal |
| * operations to be performed using 'int' and avoid many overflow checks. Static asserts are used |
| * to ensure that those operations would not overflow when using the largest possible values. |
| * |
| * Possible use modes: |
| * 1. No upfront allocation, either on the stack or as a field |
| * SkBlockAllocator allocator(policy, heapAllocSize); |
| * |
| * 2. In-place new'd |
| * void* mem = operator new(totalSize); |
| * SkBlockAllocator* allocator = new (mem) SkBlockAllocator(policy, heapAllocSize, |
| * totalSize- sizeof(SkBlockAllocator)); |
| * delete allocator; |
| * |
| * 3. Use SkSBlockAllocator to increase the preallocation size |
| * SkSBlockAllocator<1024> allocator(policy, heapAllocSize); |
| * sizeof(allocator) == 1024; |
| */ |
| // TODO(michaelludwig) - While API is different, this shares similarities to SkArenaAlloc and |
| // SkFibBlockSizes, so we should work to integrate them. |
| class SkBlockAllocator final : SkNoncopyable { |
| public: |
| // Largest size that can be requested from allocate(), chosen because it's the largest pow-2 |
| // that is less than int32_t::max()/2. |
| inline static constexpr int kMaxAllocationSize = 1 << 29; |
| |
| enum class GrowthPolicy : int { |
| kFixed, // Next block size = N |
| kLinear, // = #blocks * N |
| kFibonacci, // = fibonacci(#blocks) * N |
| kExponential, // = 2^#blocks * N |
| kLast = kExponential |
| }; |
| inline static constexpr int kGrowthPolicyCount = static_cast<int>(GrowthPolicy::kLast) + 1; |
| |
| class Block final { |
| public: |
| ~Block(); |
| void operator delete(void* p) { ::operator delete(p); } |
| |
| // Return the maximum allocation size with the given alignment that can fit in this block. |
| template <size_t Align = 1, size_t Padding = 0> |
| int avail() const { return std::max(0, fSize - this->cursor<Align, Padding>()); } |
| |
| // Return the aligned offset of the first allocation, assuming it was made with the |
| // specified Align, and Padding. The returned offset does not mean a valid allocation |
| // starts at that offset, this is a utility function for classes built on top to manage |
| // indexing into a block effectively. |
| template <size_t Align = 1, size_t Padding = 0> |
| int firstAlignedOffset() const { return this->alignedOffset<Align, Padding>(kDataStart); } |
| |
| // Convert an offset into this block's storage into a usable pointer. |
| void* ptr(int offset) { |
| SkASSERT(offset >= kDataStart && offset < fSize); |
| return reinterpret_cast<char*>(this) + offset; |
| } |
| const void* ptr(int offset) const { return const_cast<Block*>(this)->ptr(offset); } |
| |
| // Every block has an extra 'int' for clients to use however they want. It will start |
| // at 0 when a new block is made, or when the head block is reset. |
| int metadata() const { return fMetadata; } |
| void setMetadata(int value) { fMetadata = value; } |
| |
| /** |
| * Release the byte range between offset 'start' (inclusive) and 'end' (exclusive). This |
| * will return true if those bytes were successfully reclaimed, i.e. a subsequent allocation |
| * request could occupy the space. Regardless of return value, the provided byte range that |
| * [start, end) represents should not be used until it's re-allocated with allocate<...>(). |
| */ |
| inline bool release(int start, int end); |
| |
| /** |
| * Resize a previously reserved byte range of offset 'start' (inclusive) to 'end' |
| * (exclusive). 'deltaBytes' is the SIGNED change to length of the reservation. |
| * |
| * When negative this means the reservation is shrunk and the new length is (end - start - |
| * |deltaBytes|). If this new length would be 0, the byte range can no longer be used (as if |
| * it were released instead). Asserts that it would not shrink the reservation below 0. |
| * |
| * If 'deltaBytes' is positive, the allocator attempts to increase the length of the |
| * reservation. If 'deltaBytes' is less than or equal to avail() and it was the last |
| * allocation in the block, it can be resized. If there is not enough available bytes to |
| * accommodate the increase in size, or another allocation is blocking the increase in size, |
| * then false will be returned and the reserved byte range is unmodified. |
| */ |
| inline bool resize(int start, int end, int deltaBytes); |
| |
| private: |
| friend class SkBlockAllocator; |
| |
| Block(Block* prev, int allocationSize); |
| |
| // We poison the unallocated space in a Block to allow ASAN to catch invalid writes. |
| void poisonRange(int start, int end) { |
| sk_asan_poison_memory_region(reinterpret_cast<char*>(this) + start, end - start); |
| } |
| void unpoisonRange(int start, int end) { |
| sk_asan_unpoison_memory_region(reinterpret_cast<char*>(this) + start, end - start); |
| } |
| |
| // Get fCursor, but aligned such that ptr(rval) satisfies Align. |
| template <size_t Align, size_t Padding> |
| int cursor() const { return this->alignedOffset<Align, Padding>(fCursor); } |
| |
| template <size_t Align, size_t Padding> |
| int alignedOffset(int offset) const; |
| |
| bool isScratch() const { return fCursor < 0; } |
| void markAsScratch() { |
| fCursor = -1; |
| this->poisonRange(kDataStart, fSize); |
| } |
| |
| SkDEBUGCODE(uint32_t fSentinel;) // known value to check for bad back pointers to blocks |
| |
| Block* fNext; // doubly-linked list of blocks |
| Block* fPrev; |
| |
| // Each block tracks its own cursor because as later blocks are released, an older block |
| // may become the active tail again. |
| int fSize; // includes the size of the BlockHeader and requested metadata |
| int fCursor; // (this + fCursor) points to next available allocation |
| int fMetadata; |
| |
| // On release builds, a Block's other 2 pointers and 3 int fields leaves 4 bytes of padding |
| // for 8 and 16 aligned systems. Currently this is only manipulated in the head block for |
| // an allocator-level metadata and is explicitly not reset when the head block is "released" |
| // Down the road we could instead choose to offer multiple metadata slots per block. |
| int fAllocatorMetadata; |
| }; |
| |
| // Tuple representing a range of bytes, marking the unaligned start, the first aligned point |
| // after any padding, and the upper limit depending on requested size. |
| struct ByteRange { |
| Block* fBlock; // Owning block |
| int fStart; // Inclusive byte lower limit of byte range |
| int fAlignedOffset; // >= start, matching alignment requirement (i.e. first real byte) |
| int fEnd; // Exclusive upper limit of byte range |
| }; |
| |
| // The size of the head block is determined by 'additionalPreallocBytes'. Subsequent heap blocks |
| // are determined by 'policy' and 'blockIncrementBytes', although 'blockIncrementBytes' will be |
| // aligned to std::max_align_t. |
| // |
| // When 'additionalPreallocBytes' > 0, the allocator assumes that many extra bytes immediately |
| // after the allocator can be used by its inline head block. This is useful when the allocator |
| // is in-place new'ed into a larger block of memory, but it should remain set to 0 if stack |
| // allocated or if the class layout does not guarantee that space is present. |
| SkBlockAllocator(GrowthPolicy policy, size_t blockIncrementBytes, |
| size_t additionalPreallocBytes = 0); |
| |
| ~SkBlockAllocator() { this->reset(); } |
| void operator delete(void* p) { ::operator delete(p); } |
| |
| /** |
| * Helper to calculate the minimum number of bytes needed for heap block size, under the |
| * assumption that Align will be the requested alignment of the first call to allocate(). |
| * Ex. To store N instances of T in a heap block, the 'blockIncrementBytes' should be set to |
| * BlockOverhead<alignof(T)>() + N * sizeof(T) when making the SkBlockAllocator. |
| */ |
| template<size_t Align = 1, size_t Padding = 0> |
| static constexpr size_t BlockOverhead(); |
| |
| /** |
| * Helper to calculate the minimum number of bytes needed for a preallocation, under the |
| * assumption that Align will be the requested alignment of the first call to allocate(). |
| * Ex. To preallocate a SkSBlockAllocator to hold N instances of T, its arge should be |
| * Overhead<alignof(T)>() + N * sizeof(T) |
| */ |
| template<size_t Align = 1, size_t Padding = 0> |
| static constexpr size_t Overhead(); |
| |
| /** |
| * Return the total number of bytes of the allocator, including its instance overhead, per-block |
| * overhead and space used for allocations. |
| */ |
| size_t totalSize() const; |
| /** |
| * Return the total number of bytes usable for allocations. This includes bytes that have |
| * been reserved already by a call to allocate() and bytes that are still available. It is |
| * totalSize() minus all allocator and block-level overhead. |
| */ |
| size_t totalUsableSpace() const; |
| /** |
| * Return the total number of usable bytes that have been reserved by allocations. This will |
| * be less than or equal to totalUsableSpace(). |
| */ |
| size_t totalSpaceInUse() const; |
| |
| /** |
| * Return the total number of bytes that were pre-allocated for the SkBlockAllocator. This will |
| * include 'additionalPreallocBytes' passed to the constructor, and represents what the total |
| * size would become after a call to reset(). |
| */ |
| size_t preallocSize() const { |
| // Don't double count fHead's Block overhead in both sizeof(SkBlockAllocator) and fSize. |
| return sizeof(SkBlockAllocator) + fHead.fSize - BaseHeadBlockSize(); |
| } |
| /** |
| * Return the usable size of the inline head block; this will be equal to |
| * 'additionalPreallocBytes' plus any alignment padding that the system had to add to Block. |
| * The returned value represents what could be allocated before a heap block is be created. |
| */ |
| size_t preallocUsableSpace() const { |
| return fHead.fSize - kDataStart; |
| } |
| |
| /** |
| * Get the current value of the allocator-level metadata (a user-oriented slot). This is |
| * separate from any block-level metadata, but can serve a similar purpose to compactly support |
| * data collections on top of SkBlockAllocator. |
| */ |
| int metadata() const { return fHead.fAllocatorMetadata; } |
| |
| /** |
| * Set the current value of the allocator-level metadata. |
| */ |
| void setMetadata(int value) { fHead.fAllocatorMetadata = value; } |
| |
| /** |
| * Reserve space that will hold 'size' bytes. This will automatically allocate a new block if |
| * there is not enough available space in the current block to provide 'size' bytes. The |
| * returned ByteRange tuple specifies the Block owning the reserved memory, the full byte range, |
| * and the aligned offset within that range to use for the user-facing pointer. The following |
| * invariants hold: |
| * |
| * 1. block->ptr(alignedOffset) is aligned to Align |
| * 2. end - alignedOffset == size |
| * 3. Padding <= alignedOffset - start <= Padding + Align - 1 |
| * |
| * Invariant #3, when Padding > 0, allows intermediate allocators to embed metadata along with |
| * the allocations. If the Padding bytes are used for some 'struct Meta', then |
| * ptr(alignedOffset - sizeof(Meta)) can be safely used as a Meta* if Meta's alignment |
| * requirements are less than or equal to the alignment specified in allocate<>. This can be |
| * easily guaranteed by using the pattern: |
| * |
| * allocate<max(UserAlign, alignof(Meta)), sizeof(Meta)>(userSize); |
| * |
| * This ensures that ptr(alignedOffset) will always satisfy UserAlign and |
| * ptr(alignedOffset - sizeof(Meta)) will always satisfy alignof(Meta). Alternatively, memcpy |
| * can be used to read and write values between start and alignedOffset without worrying about |
| * alignment requirements of the metadata. |
| * |
| * For over-aligned allocations, the alignedOffset (as an int) may not be a multiple of Align, |
| * but the result of ptr(alignedOffset) will be a multiple of Align. |
| */ |
| template <size_t Align, size_t Padding = 0> |
| ByteRange allocate(size_t size); |
| |
| enum ReserveFlags : unsigned { |
| // If provided to reserve(), the input 'size' will be rounded up to the next size determined |
| // by the growth policy of the SkBlockAllocator. If not, 'size' will be aligned to max_align |
| kIgnoreGrowthPolicy_Flag = 0b01, |
| // If provided to reserve(), the number of available bytes of the current block will not |
| // be used to satisfy the reservation (assuming the contiguous range was long enough to |
| // begin with). |
| kIgnoreExistingBytes_Flag = 0b10, |
| |
| kNo_ReserveFlags = 0b00 |
| }; |
| |
| /** |
| * Ensure the block allocator has 'size' contiguous available bytes. After calling this |
| * function, currentBlock()->avail<Align, Padding>() may still report less than 'size' if the |
| * reserved space was added as a scratch block. This is done so that anything remaining in |
| * the current block can still be used if a smaller-than-size allocation is requested. If 'size' |
| * is requested by a subsequent allocation, the scratch block will automatically be activated |
| * and the request will not itself trigger any malloc. |
| * |
| * The optional 'flags' controls how the input size is allocated; by default it will attempt |
| * to use available contiguous bytes in the current block and will respect the growth policy |
| * of the allocator. |
| */ |
| template <size_t Align = 1, size_t Padding = 0> |
| void reserve(size_t size, ReserveFlags flags = kNo_ReserveFlags); |
| |
| /** |
| * Return a pointer to the start of the current block. This will never be null. |
| */ |
| const Block* currentBlock() const { return fTail; } |
| Block* currentBlock() { return fTail; } |
| |
| const Block* headBlock() const { return &fHead; } |
| Block* headBlock() { return &fHead; } |
| |
| /** |
| * Return the block that owns the allocated 'ptr'. Assuming that earlier, an allocation was |
| * returned as {b, start, alignedOffset, end}, and 'p = b->ptr(alignedOffset)', then a call |
| * to 'owningBlock<Align, Padding>(p, start) == b'. |
| * |
| * If calling code has already made a pointer to their metadata, i.e. 'm = p - Padding', then |
| * 'owningBlock<Align, 0>(m, start)' will also return b, allowing you to recover the block from |
| * the metadata pointer. |
| * |
| * If calling code has access to the original alignedOffset, this function should not be used |
| * since the owning block is just 'p - alignedOffset', regardless of original Align or Padding. |
| */ |
| template <size_t Align, size_t Padding = 0> |
| Block* owningBlock(const void* ptr, int start); |
| |
| template <size_t Align, size_t Padding = 0> |
| const Block* owningBlock(const void* ptr, int start) const { |
| return const_cast<SkBlockAllocator*>(this)->owningBlock<Align, Padding>(ptr, start); |
| } |
| |
| /** |
| * Find the owning block of the allocated pointer, 'p'. Without any additional information this |
| * is O(N) on the number of allocated blocks. |
| */ |
| Block* findOwningBlock(const void* ptr); |
| const Block* findOwningBlock(const void* ptr) const { |
| return const_cast<SkBlockAllocator*>(this)->findOwningBlock(ptr); |
| } |
| |
| /** |
| * Explicitly free an entire block, invalidating any remaining allocations from the block. |
| * SkBlockAllocator will release all alive blocks automatically when it is destroyed, but this |
| * function can be used to reclaim memory over the lifetime of the allocator. The provided |
| * 'block' pointer must have previously come from a call to currentBlock() or allocate(). |
| * |
| * If 'block' represents the inline-allocated head block, its cursor and metadata are instead |
| * reset to their defaults. |
| * |
| * If the block is not the head block, it may be kept as a scratch block to be reused for |
| * subsequent allocation requests, instead of making an entirely new block. A scratch block is |
| * not visible when iterating over blocks but is reported in the total size of the allocator. |
| */ |
| void releaseBlock(Block* block); |
| |
| /** |
| * Detach every heap-allocated block owned by 'other' and concatenate them to this allocator's |
| * list of blocks. This memory is now managed by this allocator. Since this only transfers |
| * ownership of a Block, and a Block itself does not move, any previous allocations remain |
| * valid and associated with their original Block instances. SkBlockAllocator-level functions |
| * that accept allocated pointers (e.g. findOwningBlock), must now use this allocator and not |
| * 'other' for these allocations. |
| * |
| * The head block of 'other' cannot be stolen, so higher-level allocators and memory structures |
| * must handle that data differently. |
| */ |
| void stealHeapBlocks(SkBlockAllocator* other); |
| |
| /** |
| * Explicitly free all blocks (invalidating all allocations), and resets the head block to its |
| * default state. The allocator-level metadata is reset to 0 as well. |
| */ |
| void reset(); |
| |
| /** |
| * Remove any reserved scratch space, either from calling reserve() or releaseBlock(). |
| */ |
| void resetScratchSpace(); |
| |
| template <bool Forward, bool Const> class BlockIter; |
| |
| /** |
| * Clients can iterate over all active Blocks in the SkBlockAllocator using for loops: |
| * |
| * Forward iteration from head to tail block (or non-const variant): |
| * for (const Block* b : this->blocks()) { } |
| * Reverse iteration from tail to head block: |
| * for (const Block* b : this->rblocks()) { } |
| * |
| * It is safe to call releaseBlock() on the active block while looping. |
| */ |
| inline BlockIter<true, false> blocks(); |
| inline BlockIter<true, true> blocks() const; |
| inline BlockIter<false, false> rblocks(); |
| inline BlockIter<false, true> rblocks() const; |
| |
| #ifdef SK_DEBUG |
| inline static constexpr uint32_t kAssignedMarker = 0xBEEFFACE; |
| inline static constexpr uint32_t kFreedMarker = 0xCAFEBABE; |
| |
| void validate() const; |
| #endif |
| |
| private: |
| friend class BlockAllocatorTestAccess; |
| friend class TBlockListTestAccess; |
| |
| inline static constexpr int kDataStart = sizeof(Block); |
| #ifdef SK_FORCE_8_BYTE_ALIGNMENT |
| // This is an issue for WASM builds using emscripten, which had std::max_align_t = 16, but |
| // was returning pointers only aligned to 8 bytes. |
| // https://github.com/emscripten-core/emscripten/issues/10072 |
| // |
| // Setting this to 8 will let SkBlockAllocator properly correct for the pointer address if |
| // a 16-byte aligned allocation is requested in wasm (unlikely since we don't use long |
| // doubles). |
| inline static constexpr size_t kAddressAlign = 8; |
| #else |
| // The alignment Block addresses will be at when created using operator new |
| // (spec-compliant is pointers are aligned to max_align_t). |
| inline static constexpr size_t kAddressAlign = alignof(std::max_align_t); |
| #endif |
| |
| // Calculates the size of a new Block required to store a kMaxAllocationSize request for the |
| // given alignment and padding bytes. Also represents maximum valid fCursor value in a Block. |
| template<size_t Align, size_t Padding> |
| static constexpr size_t MaxBlockSize(); |
| |
| static constexpr int BaseHeadBlockSize() { |
| return sizeof(SkBlockAllocator) - offsetof(SkBlockAllocator, fHead); |
| } |
| |
| // Append a new block to the end of the block linked list, updating fTail. 'minSize' must |
| // have enough room for sizeof(Block). 'maxSize' is the upper limit of fSize for the new block |
| // that will preserve the static guarantees SkBlockAllocator makes. |
| void addBlock(int minSize, int maxSize); |
| |
| int scratchBlockSize() const { return fHead.fPrev ? fHead.fPrev->fSize : 0; } |
| |
| Block* fTail; // All non-head blocks are heap allocated; tail will never be null. |
| |
| // All remaining state is packed into 64 bits to keep SkBlockAllocator at 16 bytes + head block |
| // (on a 64-bit system). |
| |
| // Growth of the block size is controlled by four factors: BlockIncrement, N0 and N1, and a |
| // policy defining how N0 is updated. When a new block is needed, we calculate N1' = N0 + N1. |
| // Depending on the policy, N0' = N0 (no growth or linear growth), or N0' = N1 (Fibonacci), or |
| // N0' = N1' (exponential). The size of the new block is N1' * BlockIncrement * MaxAlign, |
| // after which fN0 and fN1 store N0' and N1' clamped into 23 bits. With current bit allocations, |
| // N1' is limited to 2^24, and assuming MaxAlign=16, then BlockIncrement must be '2' in order to |
| // eventually reach the hard 2^29 size limit of SkBlockAllocator. |
| |
| // Next heap block size = (fBlockIncrement * alignof(std::max_align_t) * (fN0 + fN1)) |
| uint64_t fBlockIncrement : 16; |
| uint64_t fGrowthPolicy : 2; // GrowthPolicy |
| uint64_t fN0 : 23; // = 1 for linear/exp.; = 0 for fixed/fibonacci, initially |
| uint64_t fN1 : 23; // = 1 initially |
| |
| // Inline head block, must be at the end so that it can utilize any additional reserved space |
| // from the initial allocation. |
| // The head block's prev pointer may be non-null, which signifies a scratch block that may be |
| // reused instead of allocating an entirely new block (this helps when allocate+release calls |
| // bounce back and forth across the capacity of a block). |
| alignas(kAddressAlign) Block fHead; |
| |
| static_assert(kGrowthPolicyCount <= 4); |
| }; |
| |
| // A wrapper around SkBlockAllocator that includes preallocated storage for the head block. |
| // N will be the preallocSize() reported by the allocator. |
| template<size_t N> |
| class SkSBlockAllocator : SkNoncopyable { |
| public: |
| using GrowthPolicy = SkBlockAllocator::GrowthPolicy; |
| |
| SkSBlockAllocator() { |
| new (fStorage) SkBlockAllocator(GrowthPolicy::kFixed, N, N - sizeof(SkBlockAllocator)); |
| } |
| explicit SkSBlockAllocator(GrowthPolicy policy) { |
| new (fStorage) SkBlockAllocator(policy, N, N - sizeof(SkBlockAllocator)); |
| } |
| |
| SkSBlockAllocator(GrowthPolicy policy, size_t blockIncrementBytes) { |
| new (fStorage) SkBlockAllocator(policy, blockIncrementBytes, N - sizeof(SkBlockAllocator)); |
| } |
| |
| ~SkSBlockAllocator() { |
| this->allocator()->~SkBlockAllocator(); |
| } |
| |
| SkBlockAllocator* operator->() { return this->allocator(); } |
| const SkBlockAllocator* operator->() const { return this->allocator(); } |
| |
| SkBlockAllocator* allocator() { return reinterpret_cast<SkBlockAllocator*>(fStorage); } |
| const SkBlockAllocator* allocator() const { |
| return reinterpret_cast<const SkBlockAllocator*>(fStorage); |
| } |
| |
| private: |
| static_assert(N >= sizeof(SkBlockAllocator)); |
| |
| // Will be used to placement new the allocator |
| alignas(SkBlockAllocator) char fStorage[N]; |
| }; |
| |
| /////////////////////////////////////////////////////////////////////////////////////////////////// |
| // Template and inline implementations |
| |
| SK_MAKE_BITFIELD_OPS(SkBlockAllocator::ReserveFlags) |
| |
| template<size_t Align, size_t Padding> |
| constexpr size_t SkBlockAllocator::BlockOverhead() { |
| static_assert(SkAlignTo(kDataStart + Padding, Align) >= sizeof(Block)); |
| return SkAlignTo(kDataStart + Padding, Align); |
| } |
| |
| template<size_t Align, size_t Padding> |
| constexpr size_t SkBlockAllocator::Overhead() { |
| // NOTE: On most platforms, SkBlockAllocator is packed; this is not the case on debug builds |
| // due to extra fields, or on WASM due to 4byte pointers but 16byte max align. |
| return std::max(sizeof(SkBlockAllocator), |
| offsetof(SkBlockAllocator, fHead) + BlockOverhead<Align, Padding>()); |
| } |
| |
| template<size_t Align, size_t Padding> |
| constexpr size_t SkBlockAllocator::MaxBlockSize() { |
| // Without loss of generality, assumes 'align' will be the largest encountered alignment for the |
| // allocator (if it's not, the largest align will be encountered by the compiler and pass/fail |
| // the same set of static asserts). |
| return BlockOverhead<Align, Padding>() + kMaxAllocationSize; |
| } |
| |
| template<size_t Align, size_t Padding> |
| void SkBlockAllocator::reserve(size_t size, ReserveFlags flags) { |
| if (size > kMaxAllocationSize) { |
| SK_ABORT("Allocation too large (%zu bytes requested)", size); |
| } |
| int iSize = (int) size; |
| if ((flags & kIgnoreExistingBytes_Flag) || |
| this->currentBlock()->avail<Align, Padding>() < iSize) { |
| |
| int blockSize = BlockOverhead<Align, Padding>() + iSize; |
| int maxSize = (flags & kIgnoreGrowthPolicy_Flag) ? blockSize |
| : MaxBlockSize<Align, Padding>(); |
| SkASSERT((size_t) maxSize <= (MaxBlockSize<Align, Padding>())); |
| |
| SkDEBUGCODE(auto oldTail = fTail;) |
| this->addBlock(blockSize, maxSize); |
| SkASSERT(fTail != oldTail); |
| // Releasing the just added block will move it into scratch space, allowing the original |
| // tail's bytes to be used first before the scratch block is activated. |
| this->releaseBlock(fTail); |
| } |
| } |
| |
| template <size_t Align, size_t Padding> |
| SkBlockAllocator::ByteRange SkBlockAllocator::allocate(size_t size) { |
| // Amount of extra space for a new block to make sure the allocation can succeed. |
| static constexpr int kBlockOverhead = (int) BlockOverhead<Align, Padding>(); |
| |
| // Ensures 'offset' and 'end' calculations will be valid |
| static_assert((kMaxAllocationSize + SkAlignTo(MaxBlockSize<Align, Padding>(), Align)) |
| <= (size_t) std::numeric_limits<int32_t>::max()); |
| // Ensures size + blockOverhead + addBlock's alignment operations will be valid |
| static_assert(kMaxAllocationSize + kBlockOverhead + ((1 << 12) - 1) // 4K align for large blocks |
| <= std::numeric_limits<int32_t>::max()); |
| |
| if (size > kMaxAllocationSize) { |
| SK_ABORT("Allocation too large (%zu bytes requested)", size); |
| } |
| |
| int iSize = (int) size; |
| int offset = fTail->cursor<Align, Padding>(); |
| int end = offset + iSize; |
| if (end > fTail->fSize) { |
| this->addBlock(iSize + kBlockOverhead, MaxBlockSize<Align, Padding>()); |
| offset = fTail->cursor<Align, Padding>(); |
| end = offset + iSize; |
| } |
| |
| // Check invariants |
| SkASSERT(end <= fTail->fSize); |
| SkASSERT(end - offset == iSize); |
| SkASSERT(offset - fTail->fCursor >= (int) Padding && |
| offset - fTail->fCursor <= (int) (Padding + Align - 1)); |
| SkASSERT(reinterpret_cast<uintptr_t>(fTail->ptr(offset)) % Align == 0); |
| |
| int start = fTail->fCursor; |
| fTail->fCursor = end; |
| |
| fTail->unpoisonRange(offset - Padding, end); |
| |
| return {fTail, start, offset, end}; |
| } |
| |
| template <size_t Align, size_t Padding> |
| SkBlockAllocator::Block* SkBlockAllocator::owningBlock(const void* p, int start) { |
| // 'p' was originally formed by aligning 'block + start + Padding', producing the inequality: |
| // block + start + Padding <= p <= block + start + Padding + Align-1 |
| // Rearranging this yields: |
| // block <= p - start - Padding <= block + Align-1 |
| // Masking these terms by ~(Align-1) reconstructs 'block' if the alignment of the block is |
| // greater than or equal to Align (since block & ~(Align-1) == (block + Align-1) & ~(Align-1) |
| // in that case). Overalignment does not reduce to inequality unfortunately. |
| if /* constexpr */ (Align <= kAddressAlign) { |
| Block* block = reinterpret_cast<Block*>( |
| (reinterpret_cast<uintptr_t>(p) - start - Padding) & ~(Align - 1)); |
| SkASSERT(block->fSentinel == kAssignedMarker); |
| return block; |
| } else { |
| // There's not a constant-time expression available to reconstruct the block from 'p', |
| // but this is unlikely to happen frequently. |
| return this->findOwningBlock(p); |
| } |
| } |
| |
| template <size_t Align, size_t Padding> |
| int SkBlockAllocator::Block::alignedOffset(int offset) const { |
| static_assert(SkIsPow2(Align)); |
| // Aligning adds (Padding + Align - 1) as an intermediate step, so ensure that can't overflow |
| static_assert(MaxBlockSize<Align, Padding>() + Padding + Align - 1 |
| <= (size_t) std::numeric_limits<int32_t>::max()); |
| |
| if /* constexpr */ (Align <= kAddressAlign) { |
| // Same as SkAlignTo, but operates on ints instead of size_t |
| return (offset + Padding + Align - 1) & ~(Align - 1); |
| } else { |
| // Must take into account that 'this' may be starting at a pointer that doesn't satisfy the |
| // larger alignment request, so must align the entire pointer, not just offset |
| uintptr_t blockPtr = reinterpret_cast<uintptr_t>(this); |
| uintptr_t alignedPtr = (blockPtr + offset + Padding + Align - 1) & ~(Align - 1); |
| SkASSERT(alignedPtr - blockPtr <= (uintptr_t) std::numeric_limits<int32_t>::max()); |
| return (int) (alignedPtr - blockPtr); |
| } |
| } |
| |
| bool SkBlockAllocator::Block::resize(int start, int end, int deltaBytes) { |
| SkASSERT(fSentinel == kAssignedMarker); |
| SkASSERT(start >= kDataStart && end <= fSize && start < end); |
| |
| if (deltaBytes > kMaxAllocationSize || deltaBytes < -kMaxAllocationSize) { |
| // Cannot possibly satisfy the resize and could overflow subsequent math |
| return false; |
| } |
| if (fCursor == end) { |
| int nextCursor = end + deltaBytes; |
| SkASSERT(nextCursor >= start); |
| // We still check nextCursor >= start for release builds that wouldn't assert. |
| if (nextCursor <= fSize && nextCursor >= start) { |
| if (nextCursor < fCursor) { |
| // The allocation got smaller; poison the space that can no longer be used. |
| this->poisonRange(nextCursor + 1, end); |
| } else { |
| // The allocation got larger; unpoison the space that can now be used. |
| this->unpoisonRange(end, nextCursor); |
| } |
| |
| fCursor = nextCursor; |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| // NOTE: release is equivalent to resize(start, end, start - end), and the compiler can optimize |
| // most of the operations away, but it wasn't able to remove the unnecessary branch comparing the |
| // new cursor to the block size or old start, so release() gets a specialization. |
| bool SkBlockAllocator::Block::release(int start, int end) { |
| SkASSERT(fSentinel == kAssignedMarker); |
| SkASSERT(start >= kDataStart && end <= fSize && start < end); |
| |
| this->poisonRange(start, end); |
| |
| if (fCursor == end) { |
| fCursor = start; |
| return true; |
| } else { |
| return false; |
| } |
| } |
| |
| ///////// Block iteration |
| template <bool Forward, bool Const> |
| class SkBlockAllocator::BlockIter { |
| private: |
| using BlockT = typename std::conditional<Const, const Block, Block>::type; |
| using AllocatorT = |
| typename std::conditional<Const, const SkBlockAllocator, SkBlockAllocator>::type; |
| |
| public: |
| BlockIter(AllocatorT* allocator) : fAllocator(allocator) {} |
| |
| class Item { |
| public: |
| bool operator!=(const Item& other) const { return fBlock != other.fBlock; } |
| |
| BlockT* operator*() const { return fBlock; } |
| |
| Item& operator++() { |
| this->advance(fNext); |
| return *this; |
| } |
| |
| private: |
| friend BlockIter; |
| |
| Item(BlockT* block) { this->advance(block); } |
| |
| void advance(BlockT* block) { |
| fBlock = block; |
| fNext = block ? (Forward ? block->fNext : block->fPrev) : nullptr; |
| if (!Forward && fNext && fNext->isScratch()) { |
| // For reverse-iteration only, we need to stop at the head, not the scratch block |
| // possibly stashed in head->prev. |
| fNext = nullptr; |
| } |
| SkASSERT(!fNext || !fNext->isScratch()); |
| } |
| |
| BlockT* fBlock; |
| // Cache this before operator++ so that fBlock can be released during iteration |
| BlockT* fNext; |
| }; |
| |
| Item begin() const { return Item(Forward ? &fAllocator->fHead : fAllocator->fTail); } |
| Item end() const { return Item(nullptr); } |
| |
| private: |
| AllocatorT* fAllocator; |
| }; |
| |
| SkBlockAllocator::BlockIter<true, false> SkBlockAllocator::blocks() { |
| return BlockIter<true, false>(this); |
| } |
| SkBlockAllocator::BlockIter<true, true> SkBlockAllocator::blocks() const { |
| return BlockIter<true, true>(this); |
| } |
| SkBlockAllocator::BlockIter<false, false> SkBlockAllocator::rblocks() { |
| return BlockIter<false, false>(this); |
| } |
| SkBlockAllocator::BlockIter<false, true> SkBlockAllocator::rblocks() const { |
| return BlockIter<false, true>(this); |
| } |
| |
| #endif // SkBlockAllocator_DEFINED |