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#ifndef SkFixedAlloc_DEFINED
9#define SkFixedAlloc_DEFINED
10
11#include "SkRefCnt.h"
12#include "SkTFitsIn.h"
13#include "SkTypes.h"
14#include <cstddef>
15#include <new>
16#include <type_traits>
17#include <utility>
18#include <vector>
19
20// SkArenaAlloc allocates object and destroys the allocated objects when destroyed. It's designed
21// to minimize the number of underlying block allocations. SkArenaAlloc allocates first out of an
22// (optional) user-provided block of memory, and when that's exhausted it allocates on the heap,
23// starting with an allocation of extraSize bytes.  If your data (plus a small overhead) fits in
24// the user-provided block, SkArenaAlloc never uses the heap, and if it fits in extraSize bytes,
25// it'll use the heap only once.  If you pass extraSize = 0, it allocates blocks for each call to
26// make<T>.
27//
28// Examples:
29//
30//   char block[mostCasesSize];
31//   SkArenaAlloc arena(block, almostAllCasesSize);
32//
33// If mostCasesSize is too large for the stack, you can use the following pattern.
34//
35//   std::unique_ptr<char[]> block{new char[mostCasesSize]};
36//   SkArenaAlloc arena(block.get(), mostCasesSize, almostAllCasesSize);
37//
38// If the program only sometimes allocates memory, use the following.
39//
40//   SkArenaAlloc arena(nullptr, 0, almostAllCasesSize);
41//
42// The storage does not necessarily need to be on the stack. Embedding the storage in a class also
43// works.
44//
45//   class Foo {
46//       char storage[mostCasesSize];
47//       SkArenaAlloc arena (storage, almostAllCasesSize);
48//   };
49//
50// In addition, the system is optimized to handle POD data including arrays of PODs (where
51// POD is really data with no destructors). For POD data it has zero overhead per item, and a
52// typical block overhead of 8 bytes. For non-POD objects there is a per item overhead of 4 bytes.
53// For arrays of non-POD objects there is a per array overhead of typically 8 bytes. There is an
54// addition overhead when switching from POD data to non-POD data of typically 8 bytes.
55//
56// If additional blocks are needed they are increased exponentially. This strategy bounds the
57// recursion of the RunDtorsOnBlock to be limited to O(log size-of-memory). Block size grow using
58// the Fibonacci sequence which means that for 2^32 memory there are 48 allocations, and for 2^48
59// there are 71 allocations.
60class SkArenaAlloc {
61public:
62    SkArenaAlloc(char* block, size_t size, size_t extraSize = 0);
63
64    template <size_t kSize>
65    SkArenaAlloc(char (&block)[kSize], size_t extraSize = kSize)
66        : SkArenaAlloc(block, kSize, extraSize)
67    {}
68
69    SkArenaAlloc(size_t extraSize)
70        : SkArenaAlloc(nullptr, 0, extraSize)
71    {}
72
73    ~SkArenaAlloc();
74
75    template <typename T, typename... Args>
76    T* make(Args&&... args) {
77        uint32_t size      = SkTo<uint32_t>(sizeof(T));
78        uint32_t alignment = SkTo<uint32_t>(alignof(T));
79        char* objStart;
80        if (skstd::is_trivially_destructible<T>::value) {
81            objStart = this->allocObject(size, alignment);
82            fCursor = objStart + size;
83        } else {
84            objStart = this->allocObjectWithFooter(size + sizeof(Footer), alignment);
85            // Can never be UB because max value is alignof(T).
86            uint32_t padding = SkTo<uint32_t>(objStart - fCursor);
87
88            // Advance to end of object to install footer.
89            fCursor = objStart + size;
90            FooterAction* releaser = [](char* objEnd) {
91                char* objStart = objEnd - (sizeof(T) + sizeof(Footer));
92                ((T*)objStart)->~T();
93                return objStart;
94            };
95            this->installFooter(releaser, padding);
96        }
97
98        // This must be last to make objects with nested use of this allocator work.
99        return new(objStart) T(std::forward<Args>(args)...);
100    }
101
102    template <typename T, typename... Args>
103    sk_sp<T> makeSkSp(Args&&... args) {
104        SkASSERT(SkTFitsIn<uint32_t>(sizeof(T)));
105
106        // The arena takes a ref for itself to account for the destructor. The sk_sp count can't
107        // become zero or the sk_sp will try to call free on the pointer.
108        return sk_sp<T>(SkRef(this->make<T>(std::forward<Args>(args)...)));
109    }
110
111    template <typename T>
112    T* makeArrayDefault(size_t count) {
113        uint32_t safeCount = SkTo<uint32_t>(count);
114        T* array = (T*)this->commonArrayAlloc<T>(safeCount);
115
116        // If T is primitive then no initialization takes place.
117        for (size_t i = 0; i < safeCount; i++) {
118            new (&array[i]) T;
119        }
120        return array;
121    }
122
123    template <typename T>
124    T* makeArray(size_t count) {
125        uint32_t safeCount = SkTo<uint32_t>(count);
126        T* array = (T*)this->commonArrayAlloc<T>(safeCount);
127
128        // If T is primitive then the memory is initialized. For example, an array of chars will
129        // be zeroed.
130        for (size_t i = 0; i < safeCount; i++) {
131            new (&array[i]) T();
132        }
133        return array;
134    }
135
136    // Destroy all allocated objects, free any heap allocations.
137    void reset();
138
139private:
140    using Footer = int64_t;
141    using FooterAction = char* (char*);
142
143    static char* SkipPod(char* footerEnd);
144    static void RunDtorsOnBlock(char* footerEnd);
145    static char* NextBlock(char* footerEnd);
146
147    void installFooter(FooterAction* releaser, uint32_t padding);
148    void installUint32Footer(FooterAction* action, uint32_t value, uint32_t padding);
149    void installPtrFooter(FooterAction* action, char* ptr, uint32_t padding);
150
151    void ensureSpace(uint32_t size, uint32_t alignment);
152
153    char* allocObject(uint32_t size, uint32_t alignment);
154
155    char* allocObjectWithFooter(uint32_t sizeIncludingFooter, uint32_t alignment);
156
157    template <typename T>
158    char* commonArrayAlloc(uint32_t count) {
159        char* objStart;
160        uint32_t arraySize = SkTo<uint32_t>(count * sizeof(T));
161        uint32_t alignment = SkTo<uint32_t>(alignof(T));
162
163        if (skstd::is_trivially_destructible<T>::value) {
164            objStart = this->allocObject(arraySize, alignment);
165            fCursor = objStart + arraySize;
166        } else {
167            uint32_t totalSize = arraySize + sizeof(Footer) + sizeof(uint32_t);
168            objStart = this->allocObjectWithFooter(totalSize, alignment);
169
170            // Can never be UB because max value is alignof(T).
171            uint32_t padding = SkTo<uint32_t>(objStart - fCursor);
172
173            // Advance to end of array to install footer.?
174            fCursor = objStart + arraySize;
175            this->installUint32Footer(
176                [](char* footerEnd) {
177                    char* objEnd = footerEnd - (sizeof(Footer) + sizeof(uint32_t));
178                    uint32_t count;
179                    memmove(&count, objEnd, sizeof(uint32_t));
180                    char* objStart = objEnd - count * sizeof(T);
181                    T* array = (T*) objStart;
182                    for (uint32_t i = 0; i < count; i++) {
183                        array[i].~T();
184                    }
185                    return objStart;
186                },
187                SkTo<uint32_t>(count),
188                padding);
189        }
190
191        return objStart;
192    }
193
194    char*          fDtorCursor;
195    char*          fCursor;
196    char*          fEnd;
197    char* const    fFirstBlock;
198    const uint32_t fFirstSize;
199    const uint32_t fExtraSize;
200    // Use the Fibonacci sequence as the growth factor for block size. The size of the block
201    // allocated is fFib0 * fExtraSize. Using 2 ^ n * fExtraSize had too much slop for Android.
202    uint32_t       fFib0 {1}, fFib1 {1};
203};
204
205#endif//SkFixedAlloc_DEFINED
206