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