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