Line data Source code
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.
60 : class SkArenaAlloc {
61 : public:
62 : SkArenaAlloc(char* block, size_t size, size_t extraSize = 0);
63 :
64 : template <size_t kSize>
65 708 : SkArenaAlloc(char (&block)[kSize], size_t extraSize = kSize)
66 708 : : SkArenaAlloc(block, kSize, extraSize)
67 708 : {}
68 :
69 228 : SkArenaAlloc(size_t extraSize)
70 228 : : SkArenaAlloc(nullptr, 0, extraSize)
71 228 : {}
72 :
73 : ~SkArenaAlloc();
74 :
75 : template <typename T, typename... Args>
76 1895 : T* make(Args&&... args) {
77 1895 : uint32_t size = SkTo<uint32_t>(sizeof(T));
78 1895 : uint32_t alignment = SkTo<uint32_t>(alignof(T));
79 : char* objStart;
80 : if (skstd::is_trivially_destructible<T>::value) {
81 848 : objStart = this->allocObject(size, alignment);
82 848 : fCursor = objStart + size;
83 : } else {
84 1047 : objStart = this->allocObjectWithFooter(size + sizeof(Footer), alignment);
85 : // Can never be UB because max value is alignof(T).
86 1047 : uint32_t padding = SkTo<uint32_t>(objStart - fCursor);
87 :
88 : // Advance to end of object to install footer.
89 1047 : fCursor = objStart + size;
90 3141 : FooterAction* releaser = [](char* objEnd) {
91 1047 : char* objStart = objEnd - (sizeof(T) + sizeof(Footer));
92 1047 : ((T*)objStart)->~T();
93 1047 : return objStart;
94 1047 : };
95 1047 : this->installFooter(releaser, padding);
96 : }
97 :
98 : // This must be last to make objects with nested use of this allocator work.
99 1895 : return new(objStart) T(std::forward<Args>(args)...);
100 : }
101 :
102 : template <typename T, typename... Args>
103 0 : sk_sp<T> makeSkSp(Args&&... args) {
104 0 : 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 0 : return sk_sp<T>(SkRef(this->make<T>(std::forward<Args>(args)...)));
109 : }
110 :
111 : template <typename T>
112 378 : T* makeArrayDefault(size_t count) {
113 378 : uint32_t safeCount = SkTo<uint32_t>(count);
114 378 : T* array = (T*)this->commonArrayAlloc<T>(safeCount);
115 :
116 : // If T is primitive then no initialization takes place.
117 20308 : for (size_t i = 0; i < safeCount; i++) {
118 19930 : new (&array[i]) T;
119 : }
120 378 : 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 :
139 : private:
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 378 : char* commonArrayAlloc(uint32_t count) {
159 : char* objStart;
160 378 : uint32_t arraySize = SkTo<uint32_t>(count * sizeof(T));
161 378 : uint32_t alignment = SkTo<uint32_t>(alignof(T));
162 :
163 : if (skstd::is_trivially_destructible<T>::value) {
164 378 : objStart = this->allocObject(arraySize, alignment);
165 378 : 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 378 : 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
|
