Home | History | Annotate | Download | only in core 
      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 "SkArenaAlloc.h"
      9 #include <algorithm>
     10 #include <new>
     11 
     12 static char* end_chain(char*) { return nullptr; }
     13 
     14 static uint32_t first_allocated_block(uint32_t blockSize, uint32_t firstHeapAllocation) {
     15     return firstHeapAllocation > 0 ? firstHeapAllocation :
     16            blockSize           > 0 ? blockSize           : 1024;
     17 }
     18 
     19 SkArenaAlloc::SkArenaAlloc(char* block, size_t size, size_t firstHeapAllocation)
     20     : fDtorCursor {block}
     21     , fCursor     {block}
     22     , fEnd        {block + ToU32(size)}
     23     , fFirstBlock {block}
     24     , fFirstSize  {ToU32(size)}
     25     , fFirstHeapAllocationSize  {first_allocated_block(ToU32(size), ToU32(firstHeapAllocation))}
     26 {
     27     if (size < sizeof(Footer)) {
     28         fEnd = fCursor = fDtorCursor = nullptr;
     29     }
     30 
     31     if (fCursor != nullptr) {
     32         this->installFooter(end_chain, 0);
     33     }
     34 }
     35 
     36 SkArenaAlloc::~SkArenaAlloc() {
     37     RunDtorsOnBlock(fDtorCursor);
     38 }
     39 
     40 void SkArenaAlloc::reset() {
     41     this->~SkArenaAlloc();
     42     new (this) SkArenaAlloc{fFirstBlock, fFirstSize, fFirstHeapAllocationSize};
     43 }
     44 
     45 void SkArenaAlloc::installFooter(FooterAction* action, uint32_t padding) {
     46     assert(padding < 64);
     47     int64_t actionInt = (int64_t)(intptr_t)action;
     48 
     49     // The top 14 bits should be either all 0s or all 1s. Check this.
     50     assert((actionInt << 6) >> 6 == actionInt);
     51     Footer encodedFooter = (actionInt << 6) | padding;
     52     memmove(fCursor, &encodedFooter, sizeof(Footer));
     53     fCursor += sizeof(Footer);
     54     fDtorCursor = fCursor;
     55 }
     56 
     57 void SkArenaAlloc::installPtrFooter(FooterAction* action, char* ptr, uint32_t padding) {
     58     memmove(fCursor, &ptr, sizeof(char*));
     59     fCursor += sizeof(char*);
     60     this->installFooter(action, padding);
     61 }
     62 
     63 char* SkArenaAlloc::SkipPod(char* footerEnd) {
     64     char* objEnd = footerEnd - (sizeof(Footer) + sizeof(int32_t));
     65     int32_t skip;
     66     memmove(&skip, objEnd, sizeof(int32_t));
     67     return objEnd - skip;
     68 }
     69 
     70 void SkArenaAlloc::RunDtorsOnBlock(char* footerEnd) {
     71     while (footerEnd != nullptr) {
     72         Footer footer;
     73         memcpy(&footer, footerEnd - sizeof(Footer), sizeof(Footer));
     74 
     75         FooterAction* action = (FooterAction*)(footer >> 6);
     76         ptrdiff_t padding = footer & 63;
     77 
     78         footerEnd = action(footerEnd) - padding;
     79     }
     80 }
     81 
     82 char* SkArenaAlloc::NextBlock(char* footerEnd) {
     83     char* objEnd = footerEnd - (sizeof(Footer) + sizeof(char*));
     84     char* next;
     85     memmove(&next, objEnd, sizeof(char*));
     86     RunDtorsOnBlock(next);
     87     delete [] objEnd;
     88     return nullptr;
     89 }
     90 
     91 void SkArenaAlloc::installUint32Footer(FooterAction* action, uint32_t value, uint32_t padding) {
     92     memmove(fCursor, &value, sizeof(uint32_t));
     93     fCursor += sizeof(uint32_t);
     94     this->installFooter(action, padding);
     95 }
     96 
     97 void SkArenaAlloc::ensureSpace(uint32_t size, uint32_t alignment) {
     98     constexpr uint32_t headerSize = sizeof(Footer) + sizeof(ptrdiff_t);
     99     // The chrome c++ library we use does not define std::max_align_t.
    100     // This must be conservative to add the right amount of extra memory to handle the alignment
    101     // padding.
    102     constexpr uint32_t alignof_max_align_t = 8;
    103     constexpr uint32_t maxSize = std::numeric_limits<uint32_t>::max();
    104     constexpr uint32_t overhead = headerSize + sizeof(Footer);
    105     AssertRelease(size <= maxSize - overhead);
    106     uint32_t objSizeAndOverhead = size + overhead;
    107     if (alignment > alignof_max_align_t) {
    108         uint32_t alignmentOverhead = alignment - 1;
    109         AssertRelease(objSizeAndOverhead <= maxSize - alignmentOverhead);
    110         objSizeAndOverhead += alignmentOverhead;
    111     }
    112 
    113     uint32_t minAllocationSize;
    114     if (fFirstHeapAllocationSize <= maxSize / fFib0) {
    115         minAllocationSize = fFirstHeapAllocationSize * fFib0;
    116         fFib0 += fFib1;
    117         std::swap(fFib0, fFib1);
    118     } else {
    119         minAllocationSize = maxSize;
    120     }
    121     uint32_t allocationSize = std::max(objSizeAndOverhead, minAllocationSize);
    122 
    123     // Round up to a nice size. If > 32K align to 4K boundary else up to max_align_t. The > 32K
    124     // heuristic is from the JEMalloc behavior.
    125     {
    126         uint32_t mask = allocationSize > (1 << 15) ? (1 << 12) - 1 : 16 - 1;
    127         AssertRelease(allocationSize <= maxSize - mask);
    128         allocationSize = (allocationSize + mask) & ~mask;
    129     }
    130 
    131     char* newBlock = new char[allocationSize];
    132 
    133     auto previousDtor = fDtorCursor;
    134     fCursor = newBlock;
    135     fDtorCursor = newBlock;
    136     fEnd = fCursor + allocationSize;
    137     this->installPtrFooter(NextBlock, previousDtor, 0);
    138 }
    139 
    140 char* SkArenaAlloc::allocObjectWithFooter(uint32_t sizeIncludingFooter, uint32_t alignment) {
    141     uintptr_t mask = alignment - 1;
    142 
    143 restart:
    144     uint32_t skipOverhead = 0;
    145     bool needsSkipFooter = fCursor != fDtorCursor;
    146     if (needsSkipFooter) {
    147         skipOverhead = sizeof(Footer) + sizeof(uint32_t);
    148     }
    149     char* objStart = (char*)((uintptr_t)(fCursor + skipOverhead + mask) & ~mask);
    150     uint32_t totalSize = sizeIncludingFooter + skipOverhead;
    151 
    152     if ((ptrdiff_t)totalSize > fEnd - objStart) {
    153         this->ensureSpace(totalSize, alignment);
    154         goto restart;
    155     }
    156 
    157     AssertRelease((ptrdiff_t)totalSize <= fEnd - objStart);
    158 
    159     // Install a skip footer if needed, thus terminating a run of POD data. The calling code is
    160     // responsible for installing the footer after the object.
    161     if (needsSkipFooter) {
    162         this->installUint32Footer(SkipPod, ToU32(fCursor - fDtorCursor), 0);
    163     }
    164 
    165     return objStart;
    166 }
    167