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   483690641 :   explicit ZoneAllocator(Zone* zone) throw() : zone_(zone) {}
      34             :   explicit ZoneAllocator(const ZoneAllocator& other) throw()
      35   128401420 :       : ZoneAllocator<T>(other.zone_) {}
      36             :   template <typename U>
      37             :   ZoneAllocator(const ZoneAllocator<U>& other) throw()
      38    45567967 :       : ZoneAllocator<T>(other.zone_) {}
      39             :   template <typename U>
      40             :   friend class ZoneAllocator;
      41             : 
      42             :   T* address(T& x) const { return &x; }
      43             :   const T* address(const T& x) const { return &x; }
      44             : 
      45             :   T* allocate(size_t n, const void* hint = 0) {
      46   540217315 :     return static_cast<T*>(zone_->NewArray<T>(static_cast<int>(n)));
      47             :   }
      48             :   void deallocate(T* p, size_t) { /* noop for Zones */
      49             :   }
      50             : 
      51             :   size_t max_size() const throw() {
      52             :     return std::numeric_limits<int>::max() / sizeof(T);
      53             :   }
      54             :   template <typename U, typename... Args>
      55     1452585 :   void construct(U* p, Args&&... args) {
      56             :     void* v_p = const_cast<void*>(static_cast<const void*>(p));
      57  5546329591 :     new (v_p) U(std::forward<Args>(args)...);
      58     1452585 :   }
      59             :   template <typename U>
      60             :   void destroy(U* p) {
      61       28129 :     p->~U();
      62             :   }
      63             : 
      64             :   bool operator==(ZoneAllocator const& other) const {
      65             :     return zone_ == other.zone_;
      66             :   }
      67             :   bool operator!=(ZoneAllocator const& other) const {
      68     5207890 :     return zone_ != other.zone_;
      69             :   }
      70             : 
      71             :   Zone* zone() { return zone_; }
      72             : 
      73             :  private:
      74             :   Zone* zone_;
      75             : };
      76             : 
      77             : // A recycling zone allocator maintains a free list of deallocated chunks
      78             : // to reuse on subsiquent allocations. The free list management is purposely
      79             : // very simple and works best for data-structures which regularly allocate and
      80             : // free blocks of similar sized memory (such as std::deque).
      81             : template <typename T>
      82             : class RecyclingZoneAllocator : public ZoneAllocator<T> {
      83             :  public:
      84             :   template <class O>
      85             :   struct rebind {
      86             :     typedef RecyclingZoneAllocator<O> other;
      87             :   };
      88             : 
      89             : #ifdef V8_CC_MSVC
      90             :   // MSVS unfortunately requires the default constructor to be defined.
      91             :   RecyclingZoneAllocator()
      92             :       : ZoneAllocator(nullptr, nullptr), free_list_(nullptr) {
      93             :     UNREACHABLE();
      94             :   }
      95             : #endif
      96             :   explicit RecyclingZoneAllocator(Zone* zone) throw()
      97    23135725 :       : ZoneAllocator<T>(zone), free_list_(nullptr) {}
      98             :   explicit RecyclingZoneAllocator(const RecyclingZoneAllocator& other) throw()
      99    40065488 :       : ZoneAllocator<T>(other), free_list_(nullptr) {}
     100             :   template <typename U>
     101             :   RecyclingZoneAllocator(const RecyclingZoneAllocator<U>& other) throw()
     102    40142280 :       : ZoneAllocator<T>(other), free_list_(nullptr) {}
     103             :   template <typename U>
     104             :   friend class RecyclingZoneAllocator;
     105             : 
     106    88292700 :   T* allocate(size_t n, const void* hint = 0) {
     107             :     // Only check top block in free list, since this will be equal to or larger
     108             :     // than the other blocks in the free list.
     109    88292700 :     if (free_list_ && free_list_->size >= n) {
     110             :       T* return_val = reinterpret_cast<T*>(free_list_);
     111     5761707 :       free_list_ = free_list_->next;
     112             :       return return_val;
     113             :     } else {
     114             :       return ZoneAllocator<T>::allocate(n, hint);
     115             :     }
     116             :   }
     117             : 
     118             :   void deallocate(T* p, size_t n) {
     119    37341156 :     if ((sizeof(T) * n < sizeof(FreeBlock))) return;
     120             : 
     121             :     // Only add block to free_list if it is equal or larger than previous block
     122             :     // so that allocation stays O(1) only having to look at the top block.
     123    45002179 :     if (!free_list_ || free_list_->size <= n) {
     124             :       // Store the free-list within the block being deallocated.
     125             :       DCHECK((sizeof(T) * n >= sizeof(FreeBlock)));
     126             :       FreeBlock* new_free_block = reinterpret_cast<FreeBlock*>(p);
     127             : 
     128    82343174 :       new_free_block->size = n;
     129    82343174 :       new_free_block->next = free_list_;
     130    45002101 :       free_list_ = new_free_block;
     131             :     }
     132             :   }
     133             : 
     134             :  private:
     135             :   struct FreeBlock {
     136             :     FreeBlock* next;
     137             :     size_t size;
     138             :   };
     139             : 
     140             :   FreeBlock* free_list_;
     141             : };
     142             : 
     143             : typedef ZoneAllocator<bool> ZoneBoolAllocator;
     144             : typedef ZoneAllocator<int> ZoneIntAllocator;
     145             : 
     146             : }  // namespace internal
     147             : }  // namespace v8
     148             : 
     149             : #endif  // V8_ZONE_ZONE_ALLOCATOR_H_