submodule/skia/src/core/SkArenaAlloc.cpp

   1 /*
   2  * Copyright 2016 Google Inc.
   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 #include "src/core/SkArenaAlloc.h"
   9 #include <algorithm>
  10 #include <new>
  11
  12 static char* end_chain(char*) { return nullptr; }
  13
  14 SkArenaAlloc::SkArenaAlloc(char* block, size_t size, size_t firstHeapAllocation)
  15     : fDtorCursor {block}
  16     , fCursor     {block}
  17     , fEnd        {block + SkToU32(size)}
  18     , fFibonacciProgression{SkToU32(size), SkToU32(firstHeapAllocation)}
  19 {
  20     if (size < sizeof(Footer)) {
  21         fEnd = fCursor = fDtorCursor = nullptr;
  22     }
  23
  24     if (fCursor != nullptr) {
  25         this->installFooter(end_chain, 0);
  26     }
  27 }
  28
  29 SkArenaAlloc::~SkArenaAlloc() {
  30     RunDtorsOnBlock(fDtorCursor);
  31 }
  32
  33 void SkArenaAlloc::installFooter(FooterAction* action, uint32_t padding) {
  34     assert(SkTFitsIn<uint8_t>(padding));
  35     this->installRaw(action);
  36     this->installRaw((uint8_t)padding);
  37     fDtorCursor = fCursor;
  38 }
  39
  40 char* SkArenaAlloc::SkipPod(char* footerEnd) {
  41     char* objEnd = footerEnd - (sizeof(Footer) + sizeof(uint32_t));
  42     uint32_t skip;
  43     memmove(&skip, objEnd, sizeof(uint32_t));
  44     return objEnd - (ptrdiff_t) skip;
  45 }
  46
  47 void SkArenaAlloc::RunDtorsOnBlock(char* footerEnd) {
  48     while (footerEnd != nullptr) {
  49         FooterAction* action;
  50         uint8_t       padding;
  51
  52         memcpy(&action,  footerEnd - sizeof( Footer), sizeof( action));
  53         memcpy(&padding, footerEnd - sizeof(padding), sizeof(padding));
  54
  55         footerEnd = action(footerEnd) - (ptrdiff_t)padding;
  56     }
  57 }
  58
  59 char* SkArenaAlloc::NextBlock(char* footerEnd) {
  60     char* objEnd = footerEnd - (sizeof(char*) + sizeof(Footer));
  61     char* next;
  62     memmove(&next, objEnd, sizeof(char*));
  63     RunDtorsOnBlock(next);
  64     delete [] objEnd;
  65     return nullptr;
  66 }
  67
  68
  69 void SkArenaAlloc::ensureSpace(uint32_t size, uint32_t alignment) {
  70     constexpr uint32_t headerSize = sizeof(Footer) + sizeof(ptrdiff_t);
  71     constexpr uint32_t maxSize = std::numeric_limits<uint32_t>::max();
  72     constexpr uint32_t overhead = headerSize + sizeof(Footer);
  73     AssertRelease(size <= maxSize - overhead);
  74     uint32_t objSizeAndOverhead = size + overhead;
  75
  76     const uint32_t alignmentOverhead = alignment - 1;
  77     AssertRelease(objSizeAndOverhead <= maxSize - alignmentOverhead);
  78     objSizeAndOverhead += alignmentOverhead;
  79
  80     uint32_t minAllocationSize = fFibonacciProgression.nextBlockSize();
  81     uint32_t allocationSize = std::max(objSizeAndOverhead, minAllocationSize);
  82
  83     // Round up to a nice size. If > 32K align to 4K boundary else up to max_align_t. The > 32K
  84     // heuristic is from the JEMalloc behavior.
  85     {
  86         uint32_t mask = allocationSize > (1 << 15) ? (1 << 12) - 1 : 16 - 1;
  87         AssertRelease(allocationSize <= maxSize - mask);
  88         allocationSize = (allocationSize + mask) & ~mask;
  89     }
  90
  91     char* newBlock = new char[allocationSize];
  92
  93     auto previousDtor = fDtorCursor;
  94     fCursor = newBlock;
  95     fDtorCursor = newBlock;
  96     fEnd = fCursor + allocationSize;
  97     this->installRaw(previousDtor);
  98     this->installFooter(NextBlock, 0);
  99 }
 100
 101 char* SkArenaAlloc::allocObjectWithFooter(uint32_t sizeIncludingFooter, uint32_t alignment) {
 102     uintptr_t mask = alignment - 1;
 103
 104 restart:
 105     uint32_t skipOverhead = 0;
 106     const bool needsSkipFooter = fCursor != fDtorCursor;
 107     if (needsSkipFooter) {
 108         skipOverhead = sizeof(Footer) + sizeof(uint32_t);
 109     }
 110     const uint32_t totalSize = sizeIncludingFooter + skipOverhead;
 111
 112     // Math on null fCursor/fEnd is undefined behavior, so explicitly check for first alloc.
 113     if (!fCursor) {
 114         this->ensureSpace(totalSize, alignment);
 115         goto restart;
 116     }
 117
 118     assert(fEnd);
 119     // This test alone would be enough nullptr were defined to be 0, but it's not.
 120     char* objStart = (char*)((uintptr_t)(fCursor + skipOverhead + mask) & ~mask);
 121     if ((ptrdiff_t)totalSize > fEnd - objStart) {
 122         this->ensureSpace(totalSize, alignment);
 123         goto restart;
 124     }
 125
 126     AssertRelease((ptrdiff_t)totalSize <= fEnd - objStart);
 127
 128     // Install a skip footer if needed, thus terminating a run of POD data. The calling code is
 129     // responsible for installing the footer after the object.
 130     if (needsSkipFooter) {
 131         this->installRaw(SkToU32(fCursor - fDtorCursor));
 132         this->installFooter(SkipPod, 0);
 133     }
 134
 135     return objStart;
 136 }
 137
 138 SkArenaAllocWithReset::SkArenaAllocWithReset(char* block,
 139                                              size_t size,
 140                                              size_t firstHeapAllocation)
 141         : SkArenaAlloc(block, size, firstHeapAllocation)
 142         , fFirstBlock{block}
 143         , fFirstSize{SkToU32(size)}
 144         , fFirstHeapAllocationSize{SkToU32(firstHeapAllocation)} {}
 145
 146 void SkArenaAllocWithReset::reset() {
 147     char* const    firstBlock              = fFirstBlock;
 148     const uint32_t firstSize               = fFirstSize;
 149     const uint32_t firstHeapAllocationSize = fFirstHeapAllocationSize;
 150     this->~SkArenaAllocWithReset();
 151     new (this) SkArenaAllocWithReset{firstBlock, firstSize, firstHeapAllocationSize};
 152 }
 153
 154 // SkFibonacci47 is the first 47 Fibonacci numbers. Fib(47) is the largest value less than 2 ^ 32.
 155 // Used by SkFibBlockSizes.
 156 std::array<const uint32_t, 47> SkFibonacci47 {
 157                 1,         1,          2,          3,          5,          8,
 158                13,        21,         34,         55,         89,        144,
 159               233,       377,        610,        987,       1597,       2584,
 160              4181,      6765,      10946,      17711,      28657,      46368,
 161             75025,    121393,     196418,     317811,     514229,     832040,
 162           1346269,   2178309,    3524578,    5702887,    9227465,   14930352,
 163          24157817,  39088169,   63245986,  102334155,  165580141,  267914296,
 164         433494437, 701408733, 1134903170, 1836311903, 2971215073,
 165 };