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