OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2014 Google, Inc | 2 * Copyright 2014 Google, Inc |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 | 7 |
8 #ifndef SkSmallAllocator_DEFINED | 8 #ifndef SkSmallAllocator_DEFINED |
9 #define SkSmallAllocator_DEFINED | 9 #define SkSmallAllocator_DEFINED |
10 | 10 |
11 #include "SkTArray.h" | 11 #include "SkTDArray.h" |
12 #include "SkTypes.h" | 12 #include "SkTypes.h" |
13 | 13 |
14 #include <functional> | 14 #include <new> |
15 #include <utility> | 15 #include <utility> |
16 | 16 |
17 | |
18 // max_align_t is needed to calculate the alignment for createWithIniterT when t
he T used is an | |
19 // abstract type. The complication with max_align_t is that it is defined differ
ently for | |
20 // different builds. | |
21 namespace { | |
22 #if defined(SK_BUILD_FOR_WIN32) || defined(SK_BUILD_FOR_MAC) | |
23 // Use std::max_align_t for compiles that follow the standard. | |
24 #include <cstddef> | |
25 using SystemAlignment = std::max_align_t; | |
26 #else | |
27 // Ubuntu compiles don't have std::max_align_t defined, but MSVC does not de
fine max_align_t. | |
28 #include <stddef.h> | |
29 using SystemAlignment = max_align_t; | |
30 #endif | |
31 } | |
32 | |
33 /* | 17 /* |
34 * Template class for allocating small objects without additional heap memory | 18 * Template class for allocating small objects without additional heap memory |
35 * allocations. | 19 * allocations. kMaxObjects is a hard limit on the number of objects that can |
| 20 * be allocated using this class. After that, attempts to create more objects |
| 21 * with this class will assert and return nullptr. |
36 * | 22 * |
37 * kTotalBytes is the total number of bytes provided for storage for all | 23 * kTotalBytes is the total number of bytes provided for storage for all |
38 * objects created by this allocator. If an object to be created is larger | 24 * objects created by this allocator. If an object to be created is larger |
39 * than the storage (minus storage already used), it will be allocated on the | 25 * than the storage (minus storage already used), it will be allocated on the |
40 * heap. This class's destructor will handle calling the destructor for each | 26 * heap. This class's destructor will handle calling the destructor for each |
41 * object it allocated and freeing its memory. | 27 * object it allocated and freeing its memory. |
| 28 * |
| 29 * Current the class always aligns each allocation to 16-bytes to be safe, but
future |
| 30 * may reduce this to only the alignment that is required per alloc. |
42 */ | 31 */ |
43 template<uint32_t kExpectedObjects, size_t kTotalBytes> | 32 template<uint32_t kMaxObjects, size_t kTotalBytes> |
44 class SkSmallAllocator : SkNoncopyable { | 33 class SkSmallAllocator : SkNoncopyable { |
45 public: | 34 public: |
| 35 SkSmallAllocator() |
| 36 : fStorageUsed(0) |
| 37 , fNumObjects(0) |
| 38 {} |
| 39 |
46 ~SkSmallAllocator() { | 40 ~SkSmallAllocator() { |
47 // Destruct in reverse order, in case an earlier object points to a | 41 // Destruct in reverse order, in case an earlier object points to a |
48 // later object. | 42 // later object. |
49 while (fRecs.count() > 0) { | 43 while (fNumObjects > 0) { |
50 this->deleteLast(); | 44 fNumObjects--; |
| 45 Rec* rec = &fRecs[fNumObjects]; |
| 46 rec->fKillProc(rec->fObj); |
| 47 // Safe to do if fObj is in fStorage, since fHeapStorage will |
| 48 // point to nullptr. |
| 49 sk_free(rec->fHeapStorage); |
51 } | 50 } |
52 } | 51 } |
53 | 52 |
54 /* | 53 /* |
55 * Create a new object of type T. Its lifetime will be handled by this | 54 * Create a new object of type T. Its lifetime will be handled by this |
56 * SkSmallAllocator. | 55 * SkSmallAllocator. |
| 56 * Note: If kMaxObjects have been created by this SkSmallAllocator, nullptr |
| 57 * will be returned. |
57 */ | 58 */ |
58 template<typename T, typename... Args> | 59 template<typename T, typename... Args> |
59 T* createT(Args&&... args) { | 60 T* createT(Args&&... args) { |
60 void* buf = this->reserve(sizeof(T), DefaultDestructor<T>); | 61 void* buf = this->reserveT<T>(); |
| 62 if (nullptr == buf) { |
| 63 return nullptr; |
| 64 } |
61 return new (buf) T(std::forward<Args>(args)...); | 65 return new (buf) T(std::forward<Args>(args)...); |
62 } | 66 } |
63 | 67 |
64 /* | 68 /* |
65 * Create a new object of size using initer to initialize the memory. The in
iter function has | 69 * Reserve a specified amount of space (must be enough space for one T). |
66 * the signature T* initer(void* storage). If initer is unable to initialize
the memory it | 70 * The space will be in fStorage if there is room, or on the heap otherwise
. |
67 * should return nullptr where SkSmallAllocator will free the memory. | 71 * Either way, this class will call ~T() in its destructor and free the hea
p |
| 72 * allocation if necessary. |
| 73 * Unlike createT(), this method will not call the constructor of T. |
68 */ | 74 */ |
69 template <typename Initer> | 75 template<typename T> void* reserveT(size_t storageRequired = sizeof(T)) { |
70 auto createWithIniter(size_t size, Initer initer) -> decltype(initer(nullptr
)) { | 76 SkASSERT(fNumObjects < kMaxObjects); |
71 using ReturnType = decltype(initer(nullptr)); | 77 SkASSERT(storageRequired >= sizeof(T)); |
72 SkASSERT(size >= sizeof(ReturnType)); | 78 if (kMaxObjects == fNumObjects) { |
| 79 return nullptr; |
| 80 } |
| 81 const size_t storageRemaining = sizeof(fStorage) - fStorageUsed; |
| 82 Rec* rec = &fRecs[fNumObjects]; |
| 83 if (storageRequired > storageRemaining) { |
| 84 // Allocate on the heap. Ideally we want to avoid this situation. |
73 | 85 |
74 void* storage = this->reserve(size, DefaultDestructor<ReturnType>); | 86 // With the gm composeshader_bitmap2, storage required is 4476 |
75 auto candidate = initer(storage); | 87 // and storage remaining is 3392. Increasing the base storage |
76 if (!candidate) { | 88 // causes google 3 tests to fail. |
77 // Initializing didn't workout so free the memory. | 89 |
78 this->freeLast(); | 90 rec->fStorageSize = 0; |
| 91 rec->fHeapStorage = sk_malloc_throw(storageRequired); |
| 92 rec->fObj = static_cast<void*>(rec->fHeapStorage); |
| 93 } else { |
| 94 // There is space in fStorage. |
| 95 rec->fStorageSize = storageRequired; |
| 96 rec->fHeapStorage = nullptr; |
| 97 rec->fObj = static_cast<void*>(fStorage + fStorageUsed); |
| 98 fStorageUsed += storageRequired; |
79 } | 99 } |
80 | 100 rec->fKillProc = DestroyT<T>; |
81 return candidate; | 101 fNumObjects++; |
| 102 return rec->fObj; |
82 } | 103 } |
83 | 104 |
84 /* | 105 /* |
85 * Free the last object allocated and call its destructor. This can be calle
d multiple times | 106 * Free the memory reserved last without calling the destructor. |
86 * removing objects from the pool in reverse order. | 107 * Can be used in a nested way, i.e. after reserving A and B, calling |
| 108 * freeLast once will free B and calling it again will free A. |
87 */ | 109 */ |
88 void deleteLast() { | 110 void freeLast() { |
89 SkASSERT(fRecs.count() > 0); | 111 SkASSERT(fNumObjects > 0); |
90 Rec& rec = fRecs.back(); | 112 Rec* rec = &fRecs[fNumObjects - 1]; |
91 rec.fDestructor(rec.fObj); | 113 sk_free(rec->fHeapStorage); |
92 this->freeLast(); | 114 fStorageUsed -= rec->fStorageSize; |
| 115 |
| 116 fNumObjects--; |
93 } | 117 } |
94 | 118 |
95 private: | 119 private: |
96 using Destructor = void(*)(void*); | |
97 struct Rec { | 120 struct Rec { |
98 char* fObj; | 121 size_t fStorageSize; // 0 if allocated on heap |
99 Destructor fDestructor; | 122 void* fObj; |
| 123 void* fHeapStorage; |
| 124 void (*fKillProc)(void*); |
100 }; | 125 }; |
101 | 126 |
102 // Used to call the destructor for allocated objects. | 127 // Used to call the destructor for allocated objects. |
103 template<typename T> | 128 template<typename T> |
104 static void DefaultDestructor(void* ptr) { | 129 static void DestroyT(void* ptr) { |
105 static_cast<T*>(ptr)->~T(); | 130 static_cast<T*>(ptr)->~T(); |
106 } | 131 } |
107 | 132 |
108 static constexpr size_t kAlignment = alignof(SystemAlignment); | 133 alignas(16) char fStorage[kTotalBytes]; |
109 | 134 size_t fStorageUsed; // Number of bytes used so far. |
110 static constexpr size_t AlignSize(size_t size) { | 135 uint32_t fNumObjects; |
111 return (size + kAlignment - 1) & ~(kAlignment - 1); | 136 Rec fRecs[kMaxObjects]; |
112 } | |
113 | |
114 // Reserve storageRequired from fStorage if possible otherwise allocate on t
he heap. | |
115 void* reserve(size_t storageRequired, Destructor destructor) { | |
116 // Make sure that all allocations stay aligned by rounding the storageRe
quired up to the | |
117 // aligned value. | |
118 char* objectStart = fStorageEnd; | |
119 char* objectEnd = objectStart + AlignSize(storageRequired); | |
120 Rec& rec = fRecs.push_back(); | |
121 if (objectEnd > &fStorage[kTotalBytes]) { | |
122 // Allocate on the heap. Ideally we want to avoid this situation. | |
123 rec.fObj = new char [storageRequired]; | |
124 } else { | |
125 // There is space in fStorage. | |
126 rec.fObj = objectStart; | |
127 fStorageEnd = objectEnd; | |
128 } | |
129 rec.fDestructor = destructor; | |
130 return rec.fObj; | |
131 } | |
132 | |
133 void freeLast() { | |
134 Rec& rec = fRecs.back(); | |
135 if (std::less<char*>()(rec.fObj, fStorage) | |
136 || !std::less<char*>()(rec.fObj, &fStorage[kTotalBytes])) { | |
137 delete [] rec.fObj; | |
138 } else { | |
139 fStorageEnd = rec.fObj; | |
140 } | |
141 fRecs.pop_back(); | |
142 } | |
143 | |
144 SkSTArray<kExpectedObjects, Rec, true> fRecs; | |
145 char* fStorageEnd {fStorage}; | |
146 // Since char have an alignment of 1, it should be forced onto an alignment
the compiler | |
147 // expects which is the alignment of std::max_align_t. | |
148 alignas (kAlignment) char fStorage[kTotalBytes]; | |
149 }; | 137 }; |
150 | 138 |
151 #endif // SkSmallAllocator_DEFINED | 139 #endif // SkSmallAllocator_DEFINED |
OLD | NEW |