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