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 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 = std::hash<T>, 70 typename Pred = std::equal_to<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 = std::hash<Key>, 77 typename Pred = std::equal_to<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 // Implementation details below. 90 91 template <> 92 class 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 130 template <typename T> 131 class 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 207 template <typename T> 208 inline bool operator==(const ScopedArenaAllocatorAdapter<T>& lhs, 209 const ScopedArenaAllocatorAdapter<T>& rhs) { 210 return lhs.arena_stack_ == rhs.arena_stack_; 211 } 212 213 template <typename T> 214 inline bool operator!=(const ScopedArenaAllocatorAdapter<T>& lhs, 215 const ScopedArenaAllocatorAdapter<T>& rhs) { 216 return !(lhs == rhs); 217 } 218 219 inline 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. 224 template <typename T> 225 class 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. 259 template <typename T> 260 class 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. 270 template <typename T> 271 using ArenaUniquePtr = std::unique_ptr<T, ArenaDelete<T>>; 272 273 } // namespace art 274 275 #endif // ART_RUNTIME_BASE_SCOPED_ARENA_CONTAINERS_H_ 276