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