123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240 |
- /*
- * Copyright 2016 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
- #ifndef SkArenaAlloc_DEFINED
- #define SkArenaAlloc_DEFINED
- #include "include/private/SkTFitsIn.h"
- #include <cassert>
- #include <cstddef>
- #include <cstdint>
- #include <cstdlib>
- #include <cstring>
- #include <limits>
- #include <new>
- #include <type_traits>
- #include <utility>
- #include <vector>
- // SkArenaAlloc allocates object and destroys the allocated objects when destroyed. It's designed
- // to minimize the number of underlying block allocations. SkArenaAlloc allocates first out of an
- // (optional) user-provided block of memory, and when that's exhausted it allocates on the heap,
- // starting with an allocation of firstHeapAllocation bytes. If your data (plus a small overhead)
- // fits in the user-provided block, SkArenaAlloc never uses the heap, and if it fits in
- // firstHeapAllocation bytes, it'll use the heap only once. If 0 is specified for
- // firstHeapAllocation, then blockSize is used unless that too is 0, then 1024 is used.
- //
- // Examples:
- //
- // char block[mostCasesSize];
- // SkArenaAlloc arena(block, mostCasesSize);
- //
- // If mostCasesSize is too large for the stack, you can use the following pattern.
- //
- // std::unique_ptr<char[]> block{new char[mostCasesSize]};
- // SkArenaAlloc arena(block.get(), mostCasesSize, almostAllCasesSize);
- //
- // If the program only sometimes allocates memory, use the following pattern.
- //
- // SkArenaAlloc arena(nullptr, 0, almostAllCasesSize);
- //
- // The storage does not necessarily need to be on the stack. Embedding the storage in a class also
- // works.
- //
- // class Foo {
- // char storage[mostCasesSize];
- // SkArenaAlloc arena (storage, mostCasesSize);
- // };
- //
- // In addition, the system is optimized to handle POD data including arrays of PODs (where
- // POD is really data with no destructors). For POD data it has zero overhead per item, and a
- // typical per block overhead of 8 bytes. For non-POD objects there is a per item overhead of 4
- // bytes. For arrays of non-POD objects there is a per array overhead of typically 8 bytes. There
- // is an addition overhead when switching from POD data to non-POD data of typically 8 bytes.
- //
- // If additional blocks are needed they are increased exponentially. This strategy bounds the
- // recursion of the RunDtorsOnBlock to be limited to O(log size-of-memory). Block size grow using
- // the Fibonacci sequence which means that for 2^32 memory there are 48 allocations, and for 2^48
- // there are 71 allocations.
- class SkArenaAlloc {
- public:
- SkArenaAlloc(char* block, size_t blockSize, size_t firstHeapAllocation);
- explicit SkArenaAlloc(size_t firstHeapAllocation)
- : SkArenaAlloc(nullptr, 0, firstHeapAllocation)
- {}
- ~SkArenaAlloc();
- template <typename T, typename... Args>
- T* make(Args&&... args) {
- uint32_t size = ToU32(sizeof(T));
- uint32_t alignment = ToU32(alignof(T));
- char* objStart;
- if (std::is_trivially_destructible<T>::value) {
- objStart = this->allocObject(size, alignment);
- fCursor = objStart + size;
- } else {
- objStart = this->allocObjectWithFooter(size + sizeof(Footer), alignment);
- // Can never be UB because max value is alignof(T).
- uint32_t padding = ToU32(objStart - fCursor);
- // Advance to end of object to install footer.
- fCursor = objStart + size;
- FooterAction* releaser = [](char* objEnd) {
- char* objStart = objEnd - (sizeof(T) + sizeof(Footer));
- ((T*)objStart)->~T();
- return objStart;
- };
- this->installFooter(releaser, padding);
- }
- // This must be last to make objects with nested use of this allocator work.
- return new(objStart) T(std::forward<Args>(args)...);
- }
- template <typename T>
- T* makeArrayDefault(size_t count) {
- AssertRelease(SkTFitsIn<uint32_t>(count));
- uint32_t safeCount = ToU32(count);
- T* array = (T*)this->commonArrayAlloc<T>(safeCount);
- // If T is primitive then no initialization takes place.
- for (size_t i = 0; i < safeCount; i++) {
- new (&array[i]) T;
- }
- return array;
- }
- template <typename T>
- T* makeArray(size_t count) {
- AssertRelease(SkTFitsIn<uint32_t>(count));
- uint32_t safeCount = ToU32(count);
- T* array = (T*)this->commonArrayAlloc<T>(safeCount);
- // If T is primitive then the memory is initialized. For example, an array of chars will
- // be zeroed.
- for (size_t i = 0; i < safeCount; i++) {
- new (&array[i]) T();
- }
- return array;
- }
- // Only use makeBytesAlignedTo if none of the typed variants are impractical to use.
- void* makeBytesAlignedTo(size_t size, size_t align) {
- AssertRelease(SkTFitsIn<uint32_t>(size));
- auto objStart = this->allocObject(ToU32(size), ToU32(align));
- fCursor = objStart + size;
- return objStart;
- }
- // Destroy all allocated objects, free any heap allocations.
- void reset();
- private:
- static void AssertRelease(bool cond) { if (!cond) { ::abort(); } }
- static uint32_t ToU32(size_t v) {
- assert(SkTFitsIn<uint32_t>(v));
- return (uint32_t)v;
- }
- using Footer = int64_t;
- using FooterAction = char* (char*);
- static char* SkipPod(char* footerEnd);
- static void RunDtorsOnBlock(char* footerEnd);
- static char* NextBlock(char* footerEnd);
- void installFooter(FooterAction* releaser, uint32_t padding);
- void installUint32Footer(FooterAction* action, uint32_t value, uint32_t padding);
- void installPtrFooter(FooterAction* action, char* ptr, uint32_t padding);
- void ensureSpace(uint32_t size, uint32_t alignment);
- char* allocObject(uint32_t size, uint32_t alignment) {
- uintptr_t mask = alignment - 1;
- uintptr_t alignedOffset = (~reinterpret_cast<uintptr_t>(fCursor) + 1) & mask;
- uintptr_t totalSize = size + alignedOffset;
- AssertRelease(totalSize >= size);
- if (totalSize > static_cast<uintptr_t>(fEnd - fCursor)) {
- this->ensureSpace(size, alignment);
- alignedOffset = (~reinterpret_cast<uintptr_t>(fCursor) + 1) & mask;
- }
- return fCursor + alignedOffset;
- }
- char* allocObjectWithFooter(uint32_t sizeIncludingFooter, uint32_t alignment);
- template <typename T>
- char* commonArrayAlloc(uint32_t count) {
- char* objStart;
- AssertRelease(count <= std::numeric_limits<uint32_t>::max() / sizeof(T));
- uint32_t arraySize = ToU32(count * sizeof(T));
- uint32_t alignment = ToU32(alignof(T));
- if (std::is_trivially_destructible<T>::value) {
- objStart = this->allocObject(arraySize, alignment);
- fCursor = objStart + arraySize;
- } else {
- constexpr uint32_t overhead = sizeof(Footer) + sizeof(uint32_t);
- AssertRelease(arraySize <= std::numeric_limits<uint32_t>::max() - overhead);
- uint32_t totalSize = arraySize + overhead;
- objStart = this->allocObjectWithFooter(totalSize, alignment);
- // Can never be UB because max value is alignof(T).
- uint32_t padding = ToU32(objStart - fCursor);
- // Advance to end of array to install footer.?
- fCursor = objStart + arraySize;
- this->installUint32Footer(
- [](char* footerEnd) {
- char* objEnd = footerEnd - (sizeof(Footer) + sizeof(uint32_t));
- uint32_t count;
- memmove(&count, objEnd, sizeof(uint32_t));
- char* objStart = objEnd - count * sizeof(T);
- T* array = (T*) objStart;
- for (uint32_t i = 0; i < count; i++) {
- array[i].~T();
- }
- return objStart;
- },
- ToU32(count),
- padding);
- }
- return objStart;
- }
- char* fDtorCursor;
- char* fCursor;
- char* fEnd;
- char* const fFirstBlock;
- const uint32_t fFirstSize;
- const uint32_t fFirstHeapAllocationSize;
- // Use the Fibonacci sequence as the growth factor for block size. The size of the block
- // allocated is fFib0 * fFirstHeapAllocationSize. Using 2 ^ n * fFirstHeapAllocationSize
- // had too much slop for Android.
- uint32_t fFib0 {1}, fFib1 {1};
- };
- // Helper for defining allocators with inline/reserved storage.
- // For argument declarations, stick to the base type (SkArenaAlloc).
- template <size_t InlineStorageSize>
- class SkSTArenaAlloc : public SkArenaAlloc {
- public:
- explicit SkSTArenaAlloc(size_t firstHeapAllocation = InlineStorageSize)
- : INHERITED(fInlineStorage, InlineStorageSize, firstHeapAllocation) {}
- private:
- char fInlineStorage[InlineStorageSize];
- using INHERITED = SkArenaAlloc;
- };
- #endif // SkArenaAlloc_DEFINED
|