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
13static char* end_chain(char*) { return nullptr; }
14
15SkArenaAlloc::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
39SkArenaAlloc::~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
49void SkArenaAlloc::reset() {
50    this->~SkArenaAlloc();
51    new (this) SkArenaAlloc{fFirstBlock, fFirstSize, fExtraSize,
52                            fTotalSlop < 0 ? kDontTrack : kTrack};
53}
54
55void 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
67void 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
73char* 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
80void 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
92char* 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
101void 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
107void 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
155char* SkArenaAlloc::allocObjectWithFooter(uint32_t sizeIncludingFooter, uint32_t alignment) {
156    uintptr_t mask = alignment - 1;
157
158restart:
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