Line data    Source code

       1             : // Copyright 2014 the V8 project authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : #ifndef V8_ZONE_ZONE_ALLOCATOR_H_
       6             : #define V8_ZONE_ZONE_ALLOCATOR_H_
       7             : #include <limits>
       8             : 
       9             : #include "src/zone/zone.h"
      10             : 
      11             : namespace v8 {
      12             : namespace internal {
      13             : 
      14             : template <typename T>
      15             : class ZoneAllocator {
      16             :  public:
      17             :   typedef T* pointer;
      18             :   typedef const T* const_pointer;
      19             :   typedef T& reference;
      20             :   typedef const T& const_reference;
      21             :   typedef T value_type;
      22             :   typedef size_t size_type;
      23             :   typedef ptrdiff_t difference_type;
      24             :   template <class O>
      25             :   struct rebind {
      26             :     typedef ZoneAllocator<O> other;
      27             :   };
      28             : 
      29             : #ifdef V8_CC_MSVC
      30             :   // MSVS unfortunately requires the default constructor to be defined.
      31             :   ZoneAllocator() : ZoneAllocator(nullptr) { UNREACHABLE(); }
      32             : #endif
      33   144878019 :   explicit ZoneAllocator(Zone* zone) : zone_(zone) {}
      34             :   template <typename U>
      35             :   ZoneAllocator(const ZoneAllocator<U>& other) V8_NOEXCEPT
      36   111282812 :       : ZoneAllocator<T>(other.zone_) {}
      37             :   template <typename U>
      38             :   friend class ZoneAllocator;
      39             : 
      40             :   T* address(T& x) const { return &x; }
      41             :   const T* address(const T& x) const { return &x; }
      42             : 
      43       60408 :   T* allocate(size_t n, const void* hint = nullptr) {
      44  1299875276 :     return static_cast<T*>(zone_->NewArray<T>(static_cast<int>(n)));
      45             :   }
      46       60408 :   void deallocate(T* p, size_t) { /* noop for Zones */
      47       60408 :   }
      48             : 
      49       71880 :   size_t max_size() const {
      50       71880 :     return std::numeric_limits<int>::max() / sizeof(T);
      51             :   }
      52             :   template <typename U, typename... Args>
      53     1246115 :   void construct(U* p, Args&&... args) {
      54      116968 :     void* v_p = const_cast<void*>(static_cast<const void*>(p));
      55  7869752749 :     new (v_p) U(std::forward<Args>(args)...);
      56     1246115 :   }
      57             :   template <typename U>
      58      116968 :   void destroy(U* p) {
      59      910531 :     p->~U();
      60      116968 :   }
      61             : 
      62             :   bool operator==(ZoneAllocator const& other) const {
      63             :     return zone_ == other.zone_;
      64             :   }
      65             :   bool operator!=(ZoneAllocator const& other) const {
      66      154152 :     return zone_ != other.zone_;
      67             :   }
      68             : 
      69             :   Zone* zone() { return zone_; }
      70             : 
      71             :  private:
      72             :   Zone* zone_;
      73             : };
      74             : 
      75             : // A recycling zone allocator maintains a free list of deallocated chunks
      76             : // to reuse on subsiquent allocations. The free list management is purposely
      77             : // very simple and works best for data-structures which regularly allocate and
      78             : // free blocks of similar sized memory (such as std::deque).
      79             : template <typename T>
      80             : class RecyclingZoneAllocator : public ZoneAllocator<T> {
      81             :  public:
      82             :   template <class O>
      83             :   struct rebind {
      84             :     typedef RecyclingZoneAllocator<O> other;
      85             :   };
      86             : 
      87             : #ifdef V8_CC_MSVC
      88             :   // MSVS unfortunately requires the default constructor to be defined.
      89             :   RecyclingZoneAllocator()
      90             :       : ZoneAllocator(nullptr, nullptr), free_list_(nullptr) {
      91             :     UNREACHABLE();
      92             :   }
      93             : #endif
      94             :   explicit RecyclingZoneAllocator(Zone* zone)
      95    44586726 :       : ZoneAllocator<T>(zone), free_list_(nullptr) {}
      96             :   template <typename U>
      97             :   RecyclingZoneAllocator(const RecyclingZoneAllocator<U>& other) V8_NOEXCEPT
      98             :       : ZoneAllocator<T>(other),
      99             :         free_list_(nullptr) {}
     100             :   template <typename U>
     101             :   friend class RecyclingZoneAllocator;
     102             : 
     103   158124552 :   T* allocate(size_t n, const void* hint = nullptr) {
     104             :     // Only check top block in free list, since this will be equal to or larger
     105             :     // than the other blocks in the free list.
     106   158124552 :     if (free_list_ && free_list_->size >= n) {
     107             :       T* return_val = reinterpret_cast<T*>(free_list_);
     108     8810198 :       free_list_ = free_list_->next;
     109             :       return return_val;
     110             :     } else {
     111             :       return ZoneAllocator<T>::allocate(n, hint);
     112             :     }
     113             :   }
     114             : 
     115             :   void deallocate(T* p, size_t n) {
     116    64031366 :     if ((sizeof(T) * n < sizeof(FreeBlock))) return;
     117             : 
     118             :     // Only add block to free_list if it is equal or larger than previous block
     119             :     // so that allocation stays O(1) only having to look at the top block.
     120    75349678 :     if (!free_list_ || free_list_->size <= n) {
     121             :       // Store the free-list within the block being deallocated.
     122             :       DCHECK((sizeof(T) * n >= sizeof(FreeBlock)));
     123             :       FreeBlock* new_free_block = reinterpret_cast<FreeBlock*>(p);
     124             : 
     125   139380567 :       new_free_block->size = n;
     126   139380567 :       new_free_block->next = free_list_;
     127    75349419 :       free_list_ = new_free_block;
     128             :     }
     129             :   }
     130             : 
     131             :  private:
     132             :   struct FreeBlock {
     133             :     FreeBlock* next;
     134             :     size_t size;
     135             :   };
     136             : 
     137             :   FreeBlock* free_list_;
     138             : };
     139             : 
     140             : typedef ZoneAllocator<bool> ZoneBoolAllocator;
     141             : typedef ZoneAllocator<int> ZoneIntAllocator;
     142             : 
     143             : }  // namespace internal
     144             : }  // namespace v8
     145             : 
     146             : #endif  // V8_ZONE_ZONE_ALLOCATOR_H_