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