Home | History | Annotate | Download | only in base 
      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