| /* |
| * Copyright 2016 Google Inc. |
| * |
| * Use of this source code is governed by a BSD-style license that can be |
| * found in the LICENSE file. |
| */ |
| |
| #include "src/base/SkArenaAlloc.h" |
| |
| #include "include/private/base/SkMalloc.h" |
| |
| #include <algorithm> |
| #include <cassert> |
| #include <cstddef> |
| |
| static char* end_chain(char*) { return nullptr; } |
| |
| SkArenaAlloc::SkArenaAlloc(char* block, size_t size, size_t firstHeapAllocation) |
| : fDtorCursor {block} |
| , fCursor {block} |
| , fEnd {block + SkToU32(size)} |
| , fFibonacciProgression{SkToU32(size), SkToU32(firstHeapAllocation)} |
| { |
| if (size < sizeof(Footer)) { |
| fEnd = fCursor = fDtorCursor = nullptr; |
| } |
| |
| if (fCursor != nullptr) { |
| this->installFooter(end_chain, 0); |
| sk_asan_poison_memory_region(fCursor, fEnd - fCursor); |
| } |
| } |
| |
| SkArenaAlloc::~SkArenaAlloc() { |
| RunDtorsOnBlock(fDtorCursor); |
| } |
| |
| void SkArenaAlloc::installFooter(FooterAction* action, uint32_t padding) { |
| assert(SkTFitsIn<uint8_t>(padding)); |
| this->installRaw(action); |
| this->installRaw((uint8_t)padding); |
| fDtorCursor = fCursor; |
| } |
| |
| char* SkArenaAlloc::SkipPod(char* footerEnd) { |
| char* objEnd = footerEnd - (sizeof(Footer) + sizeof(uint32_t)); |
| uint32_t skip; |
| memmove(&skip, objEnd, sizeof(uint32_t)); |
| return objEnd - (ptrdiff_t) skip; |
| } |
| |
| void SkArenaAlloc::RunDtorsOnBlock(char* footerEnd) { |
| while (footerEnd != nullptr) { |
| FooterAction* action; |
| uint8_t padding; |
| |
| memcpy(&action, footerEnd - sizeof( Footer), sizeof( action)); |
| memcpy(&padding, footerEnd - sizeof(padding), sizeof(padding)); |
| |
| footerEnd = action(footerEnd) - (ptrdiff_t)padding; |
| } |
| } |
| |
| char* SkArenaAlloc::NextBlock(char* footerEnd) { |
| char* objEnd = footerEnd - (sizeof(char*) + sizeof(Footer)); |
| char* next; |
| memmove(&next, objEnd, sizeof(char*)); |
| RunDtorsOnBlock(next); |
| sk_free(objEnd); |
| return nullptr; |
| } |
| |
| void SkArenaAlloc::ensureSpace(uint32_t size, uint32_t alignment) { |
| constexpr uint32_t headerSize = sizeof(Footer) + sizeof(ptrdiff_t); |
| constexpr uint32_t maxSize = std::numeric_limits<uint32_t>::max(); |
| constexpr uint32_t overhead = headerSize + sizeof(Footer); |
| AssertRelease(size <= maxSize - overhead); |
| uint32_t objSizeAndOverhead = size + overhead; |
| |
| const uint32_t alignmentOverhead = alignment - 1; |
| AssertRelease(objSizeAndOverhead <= maxSize - alignmentOverhead); |
| objSizeAndOverhead += alignmentOverhead; |
| |
| uint32_t minAllocationSize = fFibonacciProgression.nextBlockSize(); |
| uint32_t allocationSize = std::max(objSizeAndOverhead, minAllocationSize); |
| |
| // Round up to a nice size. If > 32K align to 4K boundary else up to max_align_t. The > 32K |
| // heuristic is from the JEMalloc behavior. |
| { |
| uint32_t mask = allocationSize > (1 << 15) ? (1 << 12) - 1 : 16 - 1; |
| AssertRelease(allocationSize <= maxSize - mask); |
| allocationSize = (allocationSize + mask) & ~mask; |
| } |
| |
| char* newBlock = static_cast<char*>(sk_malloc_throw(allocationSize)); |
| |
| auto previousDtor = fDtorCursor; |
| fCursor = newBlock; |
| fDtorCursor = newBlock; |
| fEnd = fCursor + allocationSize; |
| |
| // poison the unused bytes in the block. |
| sk_asan_poison_memory_region(fCursor, fEnd - fCursor); |
| |
| this->installRaw(previousDtor); |
| this->installFooter(NextBlock, 0); |
| } |
| |
| char* SkArenaAlloc::allocObjectWithFooter(uint32_t sizeIncludingFooter, uint32_t alignment) { |
| uintptr_t mask = alignment - 1; |
| |
| restart: |
| uint32_t skipOverhead = 0; |
| const bool needsSkipFooter = fCursor != fDtorCursor; |
| if (needsSkipFooter) { |
| skipOverhead = sizeof(Footer) + sizeof(uint32_t); |
| } |
| const uint32_t totalSize = sizeIncludingFooter + skipOverhead; |
| |
| // Math on null fCursor/fEnd is undefined behavior, so explicitly check for first alloc. |
| if (!fCursor) { |
| this->ensureSpace(totalSize, alignment); |
| goto restart; |
| } |
| |
| assert(fEnd); |
| // This test alone would be enough nullptr were defined to be 0, but it's not. |
| char* objStart = (char*)((uintptr_t)(fCursor + skipOverhead + mask) & ~mask); |
| if ((ptrdiff_t)totalSize > fEnd - objStart) { |
| this->ensureSpace(totalSize, alignment); |
| goto restart; |
| } |
| |
| AssertRelease((ptrdiff_t)totalSize <= fEnd - objStart); |
| |
| // Install a skip footer if needed, thus terminating a run of POD data. The calling code is |
| // responsible for installing the footer after the object. |
| if (needsSkipFooter) { |
| this->installRaw(SkToU32(fCursor - fDtorCursor)); |
| this->installFooter(SkipPod, 0); |
| } |
| |
| return objStart; |
| } |
| |
| SkArenaAllocWithReset::SkArenaAllocWithReset(char* block, |
| size_t size, |
| size_t firstHeapAllocation) |
| : SkArenaAlloc(block, size, firstHeapAllocation) |
| , fFirstBlock{block} |
| , fFirstSize{SkToU32(size)} |
| , fFirstHeapAllocationSize{SkToU32(firstHeapAllocation)} {} |
| |
| void SkArenaAllocWithReset::reset() { |
| char* const firstBlock = fFirstBlock; |
| const uint32_t firstSize = fFirstSize; |
| const uint32_t firstHeapAllocationSize = fFirstHeapAllocationSize; |
| this->~SkArenaAllocWithReset(); |
| new (this) SkArenaAllocWithReset{firstBlock, firstSize, firstHeapAllocationSize}; |
| } |
| |
| // SkFibonacci47 is the first 47 Fibonacci numbers. Fib(47) is the largest value less than 2 ^ 32. |
| // Used by SkFibBlockSizes. |
| std::array<const uint32_t, 47> SkFibonacci47 { |
| 1, 1, 2, 3, 5, 8, |
| 13, 21, 34, 55, 89, 144, |
| 233, 377, 610, 987, 1597, 2584, |
| 4181, 6765, 10946, 17711, 28657, 46368, |
| 75025, 121393, 196418, 317811, 514229, 832040, |
| 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, |
| 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, |
| 433494437, 701408733, 1134903170, 1836311903, 2971215073, |
| }; |