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