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