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