1 /*
2 * Copyright (C) 2014 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #ifndef ART_LIBARTBASE_BASE_ARENA_CONTAINERS_H_
18 #define ART_LIBARTBASE_BASE_ARENA_CONTAINERS_H_
19
20 #include <deque>
21 #include <forward_list>
22 #include <queue>
23 #include <set>
24 #include <stack>
25 #include <unordered_map>
26 #include <utility>
27
28 #include "arena_allocator.h"
29 #include "dchecked_vector.h"
30 #include "hash_map.h"
31 #include "hash_set.h"
32 #include "safe_map.h"
33
34 namespace art {
35
36 // Adapter for use of ArenaAllocator in STL containers.
37 // Use ArenaAllocator::Adapter() to create an adapter to pass to container constructors.
38 // For example,
39 // struct Foo {
40 // explicit Foo(ArenaAllocator* allocator)
41 // : foo_vector(allocator->Adapter(kArenaAllocMisc)),
42 // foo_map(std::less<int>(), allocator->Adapter()) {
43 // }
44 // ArenaVector<int> foo_vector;
45 // ArenaSafeMap<int, int> foo_map;
46 // };
47 template <typename T>
48 class ArenaAllocatorAdapter;
49
50 template <typename T>
51 using ArenaDeque = std::deque<T, ArenaAllocatorAdapter<T>>;
52
53 template <typename T>
54 using ArenaForwardList = std::forward_list<T, ArenaAllocatorAdapter<T>>;
55
56 template <typename T>
57 using ArenaQueue = std::queue<T, ArenaDeque<T>>;
58
59 template <typename T>
60 using ArenaVector = dchecked_vector<T, ArenaAllocatorAdapter<T>>;
61
62 template <typename T, typename Comparator = std::less<T>>
63 using ArenaPriorityQueue = std::priority_queue<T, ArenaVector<T>, Comparator>;
64
65 template <typename T>
66 using ArenaStdStack = std::stack<T, ArenaDeque<T>>;
67
68 template <typename T, typename Comparator = std::less<T>>
69 using ArenaSet = std::set<T, Comparator, ArenaAllocatorAdapter<T>>;
70
71 template <typename K, typename V, typename Comparator = std::less<K>>
72 using ArenaSafeMap =
73 SafeMap<K, V, Comparator, ArenaAllocatorAdapter<std::pair<const K, V>>>;
74
75 template <typename T,
76 typename EmptyFn = DefaultEmptyFn<T>,
77 typename HashFn = DefaultHashFn<T>,
78 typename Pred = DefaultPred<T>>
79 using ArenaHashSet = HashSet<T, EmptyFn, HashFn, Pred, ArenaAllocatorAdapter<T>>;
80
81 template <typename Key,
82 typename Value,
83 typename EmptyFn = DefaultEmptyFn<std::pair<Key, Value>>,
84 typename HashFn = DefaultHashFn<Key>,
85 typename Pred = DefaultPred<Key>>
86 using ArenaHashMap = HashMap<Key,
87 Value,
88 EmptyFn,
89 HashFn,
90 Pred,
91 ArenaAllocatorAdapter<std::pair<Key, Value>>>;
92
93 template <typename Key,
94 typename Value,
95 typename Hash = std::hash<Key>,
96 typename Pred = std::equal_to<Key>>
97 using ArenaUnorderedMap = std::unordered_map<Key,
98 Value,
99 Hash,
100 Pred,
101 ArenaAllocatorAdapter<std::pair<const Key, Value>>>;
102
103 // Implementation details below.
104
105 template <bool kCount>
106 class ArenaAllocatorAdapterKindImpl;
107
108 template <>
109 class ArenaAllocatorAdapterKindImpl<false> {
110 public:
111 // Not tracking allocations, ignore the supplied kind and arbitrarily provide kArenaAllocSTL.
ArenaAllocatorAdapterKindImpl(ArenaAllocKind kind)112 explicit ArenaAllocatorAdapterKindImpl([[maybe_unused]] ArenaAllocKind kind) {}
113 ArenaAllocatorAdapterKindImpl(const ArenaAllocatorAdapterKindImpl&) = default;
114 ArenaAllocatorAdapterKindImpl& operator=(const ArenaAllocatorAdapterKindImpl&) = default;
Kind()115 ArenaAllocKind Kind() { return kArenaAllocSTL; }
116 };
117
118 template <bool kCount>
119 class ArenaAllocatorAdapterKindImpl {
120 public:
ArenaAllocatorAdapterKindImpl(ArenaAllocKind kind)121 explicit ArenaAllocatorAdapterKindImpl(ArenaAllocKind kind) : kind_(kind) { }
122 ArenaAllocatorAdapterKindImpl(const ArenaAllocatorAdapterKindImpl&) = default;
123 ArenaAllocatorAdapterKindImpl& operator=(const ArenaAllocatorAdapterKindImpl&) = default;
Kind()124 ArenaAllocKind Kind() { return kind_; }
125
126 private:
127 ArenaAllocKind kind_;
128 };
129
130 using ArenaAllocatorAdapterKind = ArenaAllocatorAdapterKindImpl<kArenaAllocatorCountAllocations>;
131
132 template <>
133 class ArenaAllocatorAdapter<void> : private ArenaAllocatorAdapterKind {
134 public:
135 using value_type = void;
136 using pointer = void*;
137 using const_pointer = const void*;
138
139 template <typename U>
140 struct rebind {
141 using other = ArenaAllocatorAdapter<U>;
142 };
143
144 explicit ArenaAllocatorAdapter(ArenaAllocator* allocator,
145 ArenaAllocKind kind = kArenaAllocSTL)
ArenaAllocatorAdapterKind(kind)146 : ArenaAllocatorAdapterKind(kind),
147 allocator_(allocator) {
148 }
149 template <typename U>
ArenaAllocatorAdapter(const ArenaAllocatorAdapter<U> & other)150 ArenaAllocatorAdapter(const ArenaAllocatorAdapter<U>& other)
151 : ArenaAllocatorAdapterKind(other),
152 allocator_(other.allocator_) {
153 }
154 ArenaAllocatorAdapter(const ArenaAllocatorAdapter&) = default;
155 ArenaAllocatorAdapter& operator=(const ArenaAllocatorAdapter&) = default;
156 ~ArenaAllocatorAdapter() = default;
157
158 private:
159 ArenaAllocator* allocator_;
160
161 template <typename U>
162 friend class ArenaAllocatorAdapter;
163 };
164
165 template <typename T>
166 class ArenaAllocatorAdapter : private ArenaAllocatorAdapterKind {
167 public:
168 using value_type = T;
169 using pointer = T*;
170 using reference = T&;
171 using const_pointer = const T*;
172 using const_reference = const T&;
173 using size_type = size_t;
174 using difference_type = ptrdiff_t;
175
176 template <typename U>
177 struct rebind {
178 using other = ArenaAllocatorAdapter<U>;
179 };
180
ArenaAllocatorAdapter(ArenaAllocator * allocator,ArenaAllocKind kind)181 ArenaAllocatorAdapter(ArenaAllocator* allocator, ArenaAllocKind kind)
182 : ArenaAllocatorAdapterKind(kind),
183 allocator_(allocator) {
184 }
185 template <typename U>
ArenaAllocatorAdapter(const ArenaAllocatorAdapter<U> & other)186 ArenaAllocatorAdapter(const ArenaAllocatorAdapter<U>& other)
187 : ArenaAllocatorAdapterKind(other),
188 allocator_(other.allocator_) {
189 }
190 ArenaAllocatorAdapter(const ArenaAllocatorAdapter&) = default;
191 ArenaAllocatorAdapter& operator=(const ArenaAllocatorAdapter&) = default;
192 ~ArenaAllocatorAdapter() = default;
193
max_size()194 size_type max_size() const {
195 return static_cast<size_type>(-1) / sizeof(T);
196 }
197
address(reference x)198 pointer address(reference x) const { return &x; }
address(const_reference x)199 const_pointer address(const_reference x) const { return &x; }
200
201 pointer allocate(size_type n,
202 [[maybe_unused]] ArenaAllocatorAdapter<void>::pointer hint = nullptr) {
203 DCHECK_LE(n, max_size());
204 return allocator_->AllocArray<T>(n, ArenaAllocatorAdapterKind::Kind());
205 }
deallocate(pointer p,size_type n)206 void deallocate(pointer p, size_type n) {
207 allocator_->MakeInaccessible(p, sizeof(T) * n);
208 }
209
210 template <typename U, typename... Args>
construct(U * p,Args &&...args)211 void construct(U* p, Args&&... args) {
212 ::new (static_cast<void*>(p)) U(std::forward<Args>(args)...);
213 }
214 template <typename U>
destroy(U * p)215 void destroy(U* p) {
216 p->~U();
217 }
218
219 private:
220 ArenaAllocator* allocator_;
221
222 template <typename U>
223 friend class ArenaAllocatorAdapter;
224
225 template <typename U>
226 friend bool operator==(const ArenaAllocatorAdapter<U>& lhs,
227 const ArenaAllocatorAdapter<U>& rhs);
228 };
229
230 template <typename T>
231 inline bool operator==(const ArenaAllocatorAdapter<T>& lhs,
232 const ArenaAllocatorAdapter<T>& rhs) {
233 return lhs.allocator_ == rhs.allocator_;
234 }
235
236 template <typename T>
237 inline bool operator!=(const ArenaAllocatorAdapter<T>& lhs,
238 const ArenaAllocatorAdapter<T>& rhs) {
239 return !(lhs == rhs);
240 }
241
Adapter(ArenaAllocKind kind)242 inline ArenaAllocatorAdapter<void> ArenaAllocator::Adapter(ArenaAllocKind kind) {
243 return ArenaAllocatorAdapter<void>(this, kind);
244 }
245
246 // Special deleter that only calls the destructor. Also checks for double free errors.
247 template <typename T>
248 class ArenaDelete {
249 static constexpr uint8_t kMagicFill = 0xCE;
250
251 protected:
252 // Used for variable sized objects such as RegisterLine.
ProtectMemory(T * ptr,size_t size)253 ALWAYS_INLINE void ProtectMemory(T* ptr, size_t size) const {
254 if (kRunningOnMemoryTool) {
255 memset(ptr, kMagicFill, size);
256 MEMORY_TOOL_MAKE_NOACCESS(ptr, size);
257 } else if (kIsDebugBuild) {
258 // Write a magic value to try and catch use after free errors.
259 memset(ptr, kMagicFill, size);
260 }
261 }
262
263 public:
operator()264 void operator()(T* ptr) const {
265 if (ptr != nullptr) {
266 ptr->~T();
267 ProtectMemory(ptr, sizeof(T));
268 }
269 }
270 };
271
272 // In general we lack support for arrays. We would need to call the destructor on each element,
273 // which requires access to the array size. Support for that is future work.
274 //
275 // However, we can support trivially destructible component types, as then a destructor doesn't
276 // need to be called.
277 template <typename T>
278 class ArenaDelete<T[]> {
279 public:
operator()280 void operator()([[maybe_unused]] T* ptr) const {
281 static_assert(std::is_trivially_destructible_v<T>,
282 "ArenaUniquePtr does not support non-trivially-destructible arrays.");
283 // TODO: Implement debug checks, and MEMORY_TOOL support.
284 }
285 };
286
287 // Arena unique ptr that only calls the destructor of the element.
288 template <typename T>
289 using ArenaUniquePtr = std::unique_ptr<T, ArenaDelete<T>>;
290
291 } // namespace art
292
293 #endif // ART_LIBARTBASE_BASE_ARENA_CONTAINERS_H_
294