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