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