Home | History | Annotate | Download | only in zone 
      1 // Copyright 2012 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_H_
      6 #define V8_ZONE_ZONE_H_
      7 
      8 #include <limits>
      9 
     10 #include "src/base/hashmap.h"
     11 #include "src/base/logging.h"
     12 #include "src/globals.h"
     13 #include "src/list.h"
     14 #include "src/splay-tree.h"
     15 #include "src/zone/accounting-allocator.h"
     16 
     17 #ifndef ZONE_NAME
     18 #define STRINGIFY(x) #x
     19 #define TOSTRING(x) STRINGIFY(x)
     20 #define ZONE_NAME __FILE__ ":" TOSTRING(__LINE__)
     21 #endif
     22 
     23 namespace v8 {
     24 namespace internal {
     25 
     26 // The Zone supports very fast allocation of small chunks of
     27 // memory. The chunks cannot be deallocated individually, but instead
     28 // the Zone supports deallocating all chunks in one fast
     29 // operation. The Zone is used to hold temporary data structures like
     30 // the abstract syntax tree, which is deallocated after compilation.
     31 //
     32 // Note: There is no need to initialize the Zone; the first time an
     33 // allocation is attempted, a segment of memory will be requested
     34 // through the allocator.
     35 //
     36 // Note: The implementation is inherently not thread safe. Do not use
     37 // from multi-threaded code.
     38 class V8_EXPORT_PRIVATE Zone final {
     39  public:
     40   Zone(AccountingAllocator* allocator, const char* name);
     41   ~Zone();
     42 
     43   // Allocate 'size' bytes of memory in the Zone; expands the Zone by
     44   // allocating new segments of memory on demand using malloc().
     45   void* New(size_t size);
     46 
     47   template <typename T>
     48   T* NewArray(size_t length) {
     49     DCHECK_LT(length, std::numeric_limits<size_t>::max() / sizeof(T));
     50     return static_cast<T*>(New(length * sizeof(T)));
     51   }
     52 
     53   // Seals the zone to prevent any further allocation.
     54   void Seal() { sealed_ = true; }
     55 
     56   // Returns true if more memory has been allocated in zones than
     57   // the limit allows.
     58   bool excess_allocation() const {
     59     return segment_bytes_allocated_ > kExcessLimit;
     60   }
     61 
     62   const char* name() const { return name_; }
     63 
     64   size_t allocation_size() const { return allocation_size_; }
     65 
     66   AccountingAllocator* allocator() const { return allocator_; }
     67 
     68  private:
     69   // All pointers returned from New() are 8-byte aligned.
     70   static const size_t kAlignmentInBytes = 8;
     71 
     72   // Never allocate segments smaller than this size in bytes.
     73   static const size_t kMinimumSegmentSize = 8 * KB;
     74 
     75   // Never allocate segments larger than this size in bytes.
     76   static const size_t kMaximumSegmentSize = 1 * MB;
     77 
     78   // Report zone excess when allocation exceeds this limit.
     79   static const size_t kExcessLimit = 256 * MB;
     80 
     81   // Deletes all objects and free all memory allocated in the Zone.
     82   void DeleteAll();
     83 
     84   // The number of bytes allocated in this zone so far.
     85   size_t allocation_size_;
     86 
     87   // The number of bytes allocated in segments.  Note that this number
     88   // includes memory allocated from the OS but not yet allocated from
     89   // the zone.
     90   size_t segment_bytes_allocated_;
     91 
     92   // Expand the Zone to hold at least 'size' more bytes and allocate
     93   // the bytes. Returns the address of the newly allocated chunk of
     94   // memory in the Zone. Should only be called if there isn't enough
     95   // room in the Zone already.
     96   Address NewExpand(size_t size);
     97 
     98   // Creates a new segment, sets it size, and pushes it to the front
     99   // of the segment chain. Returns the new segment.
    100   inline Segment* NewSegment(size_t requested_size);
    101 
    102   // The free region in the current (front) segment is represented as
    103   // the half-open interval [position, limit). The 'position' variable
    104   // is guaranteed to be aligned as dictated by kAlignment.
    105   Address position_;
    106   Address limit_;
    107 
    108   AccountingAllocator* allocator_;
    109 
    110   Segment* segment_head_;
    111   const char* name_;
    112   bool sealed_;
    113 };
    114 
    115 // ZoneObject is an abstraction that helps define classes of objects
    116 // allocated in the Zone. Use it as a base class; see ast.h.
    117 class ZoneObject {
    118  public:
    119   // Allocate a new ZoneObject of 'size' bytes in the Zone.
    120   void* operator new(size_t size, Zone* zone) { return zone->New(size); }
    121 
    122   // Ideally, the delete operator should be private instead of
    123   // public, but unfortunately the compiler sometimes synthesizes
    124   // (unused) destructors for classes derived from ZoneObject, which
    125   // require the operator to be visible. MSVC requires the delete
    126   // operator to be public.
    127 
    128   // ZoneObjects should never be deleted individually; use
    129   // Zone::DeleteAll() to delete all zone objects in one go.
    130   void operator delete(void*, size_t) { UNREACHABLE(); }
    131   void operator delete(void* pointer, Zone* zone) { UNREACHABLE(); }
    132 };
    133 
    134 // The ZoneAllocationPolicy is used to specialize generic data
    135 // structures to allocate themselves and their elements in the Zone.
    136 class ZoneAllocationPolicy final {
    137  public:
    138   explicit ZoneAllocationPolicy(Zone* zone) : zone_(zone) {}
    139   void* New(size_t size) { return zone()->New(size); }
    140   static void Delete(void* pointer) {}
    141   Zone* zone() const { return zone_; }
    142 
    143  private:
    144   Zone* zone_;
    145 };
    146 
    147 // ZoneLists are growable lists with constant-time access to the
    148 // elements. The list itself and all its elements are allocated in the
    149 // Zone. ZoneLists cannot be deleted individually; you can delete all
    150 // objects in the Zone by calling Zone::DeleteAll().
    151 template <typename T>
    152 class ZoneList final : public List<T, ZoneAllocationPolicy> {
    153  public:
    154   // Construct a new ZoneList with the given capacity; the length is
    155   // always zero. The capacity must be non-negative.
    156   ZoneList(int capacity, Zone* zone)
    157       : List<T, ZoneAllocationPolicy>(capacity, ZoneAllocationPolicy(zone)) {}
    158 
    159   // Construct a new ZoneList from a std::initializer_list
    160   ZoneList(std::initializer_list<T> list, Zone* zone)
    161       : List<T, ZoneAllocationPolicy>(static_cast<int>(list.size()),
    162                                       ZoneAllocationPolicy(zone)) {
    163     for (auto& i : list) Add(i, zone);
    164   }
    165 
    166   void* operator new(size_t size, Zone* zone) { return zone->New(size); }
    167 
    168   // Construct a new ZoneList by copying the elements of the given ZoneList.
    169   ZoneList(const ZoneList<T>& other, Zone* zone)
    170       : List<T, ZoneAllocationPolicy>(other.length(),
    171                                       ZoneAllocationPolicy(zone)) {
    172     AddAll(other, zone);
    173   }
    174 
    175   // We add some convenience wrappers so that we can pass in a Zone
    176   // instead of a (less convenient) ZoneAllocationPolicy.
    177   void Add(const T& element, Zone* zone) {
    178     List<T, ZoneAllocationPolicy>::Add(element, ZoneAllocationPolicy(zone));
    179   }
    180   void AddAll(const List<T, ZoneAllocationPolicy>& other, Zone* zone) {
    181     List<T, ZoneAllocationPolicy>::AddAll(other, ZoneAllocationPolicy(zone));
    182   }
    183   void AddAll(const Vector<T>& other, Zone* zone) {
    184     List<T, ZoneAllocationPolicy>::AddAll(other, ZoneAllocationPolicy(zone));
    185   }
    186   void InsertAt(int index, const T& element, Zone* zone) {
    187     List<T, ZoneAllocationPolicy>::InsertAt(index, element,
    188                                             ZoneAllocationPolicy(zone));
    189   }
    190   Vector<T> AddBlock(T value, int count, Zone* zone) {
    191     return List<T, ZoneAllocationPolicy>::AddBlock(value, count,
    192                                                    ZoneAllocationPolicy(zone));
    193   }
    194   void Allocate(int length, Zone* zone) {
    195     List<T, ZoneAllocationPolicy>::Allocate(length, ZoneAllocationPolicy(zone));
    196   }
    197   void Initialize(int capacity, Zone* zone) {
    198     List<T, ZoneAllocationPolicy>::Initialize(capacity,
    199                                               ZoneAllocationPolicy(zone));
    200   }
    201 
    202   void operator delete(void* pointer) { UNREACHABLE(); }
    203   void operator delete(void* pointer, Zone* zone) { UNREACHABLE(); }
    204 };
    205 
    206 // A zone splay tree.  The config type parameter encapsulates the
    207 // different configurations of a concrete splay tree (see splay-tree.h).
    208 // The tree itself and all its elements are allocated in the Zone.
    209 template <typename Config>
    210 class ZoneSplayTree final : public SplayTree<Config, ZoneAllocationPolicy> {
    211  public:
    212   explicit ZoneSplayTree(Zone* zone)
    213       : SplayTree<Config, ZoneAllocationPolicy>(ZoneAllocationPolicy(zone)) {}
    214   ~ZoneSplayTree() {
    215     // Reset the root to avoid unneeded iteration over all tree nodes
    216     // in the destructor.  For a zone-allocated tree, nodes will be
    217     // freed by the Zone.
    218     SplayTree<Config, ZoneAllocationPolicy>::ResetRoot();
    219   }
    220 
    221   void* operator new(size_t size, Zone* zone) { return zone->New(size); }
    222 
    223   void operator delete(void* pointer) { UNREACHABLE(); }
    224   void operator delete(void* pointer, Zone* zone) { UNREACHABLE(); }
    225 };
    226 
    227 typedef base::PointerTemplateHashMapImpl<ZoneAllocationPolicy> ZoneHashMap;
    228 
    229 typedef base::CustomMatcherTemplateHashMapImpl<ZoneAllocationPolicy>
    230     CustomMatcherZoneHashMap;
    231 
    232 }  // namespace internal
    233 }  // namespace v8
    234 
    235 #endif  // V8_ZONE_ZONE_H_
    236