deps/v8/src/zone.h

   1 // Copyright 2012 the V8 project authors. All rights reserved.
   2 // Redistribution and use in source and binary forms, with or without
   3 // modification, are permitted provided that the following conditions are
   4 // met:
   5 //
   6 //     * Redistributions of source code must retain the above copyright
   7 //       notice, this list of conditions and the following disclaimer.
   8 //     * Redistributions in binary form must reproduce the above
   9 //       copyright notice, this list of conditions and the following
  10 //       disclaimer in the documentation and/or other materials provided
  11 //       with the distribution.
  12 //     * Neither the name of Google Inc. nor the names of its
  13 //       contributors may be used to endorse or promote products derived
  14 //       from this software without specific prior written permission.
  15 //
  16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27
  28 #ifndef V8_ZONE_H_
  29 #define V8_ZONE_H_
  30
  31 #include "allocation.h"
  32 #include "checks.h"
  33 #include "hashmap.h"
  34 #include "globals.h"
  35 #include "list.h"
  36 #include "splay-tree.h"
  37
  38 namespace v8 {
  39 namespace internal {
  40
  41
  42 class Segment;
  43 class Isolate;
  44
  45 // The Zone supports very fast allocation of small chunks of
  46 // memory. The chunks cannot be deallocated individually, but instead
  47 // the Zone supports deallocating all chunks in one fast
  48 // operation. The Zone is used to hold temporary data structures like
  49 // the abstract syntax tree, which is deallocated after compilation.
  50
  51 // Note: There is no need to initialize the Zone; the first time an
  52 // allocation is attempted, a segment of memory will be requested
  53 // through a call to malloc().
  54
  55 // Note: The implementation is inherently not thread safe. Do not use
  56 // from multi-threaded code.
  57
  58 class Zone {
  59  public:
  60   explicit Zone(Isolate* isolate);
  61   ~Zone();
  62   // Allocate 'size' bytes of memory in the Zone; expands the Zone by
  63   // allocating new segments of memory on demand using malloc().
  64   inline void* New(int size);
  65
  66   template <typename T>
  67   inline T* NewArray(int length);
  68
  69   // Deletes all objects and free all memory allocated in the Zone. Keeps one
  70   // small (size <= kMaximumKeptSegmentSize) segment around if it finds one.
  71   void DeleteAll();
  72
  73   // Deletes the last small segment kept around by DeleteAll(). You
  74   // may no longer allocate in the Zone after a call to this method.
  75   void DeleteKeptSegment();
  76
  77   // Returns true if more memory has been allocated in zones than
  78   // the limit allows.
  79   inline bool excess_allocation();
  80
  81   inline void adjust_segment_bytes_allocated(int delta);
  82
  83   inline unsigned allocation_size() { return allocation_size_; }
  84
  85   inline Isolate* isolate() { return isolate_; }
  86
  87  private:
  88   friend class Isolate;
  89
  90   // All pointers returned from New() have this alignment.  In addition, if the
  91   // object being allocated has a size that is divisible by 8 then its alignment
  92   // will be 8.
  93   static const int kAlignment = kPointerSize;
  94
  95   // Never allocate segments smaller than this size in bytes.
  96   static const int kMinimumSegmentSize = 8 * KB;
  97
  98   // Never allocate segments larger than this size in bytes.
  99   static const int kMaximumSegmentSize = 1 * MB;
 100
 101   // Never keep segments larger than this size in bytes around.
 102   static const int kMaximumKeptSegmentSize = 64 * KB;
 103
 104   // Report zone excess when allocation exceeds this limit.
 105   static const int kExcessLimit = 256 * MB;
 106
 107   // The number of bytes allocated in this zone so far.
 108   unsigned allocation_size_;
 109
 110   // The number of bytes allocated in segments.  Note that this number
 111   // includes memory allocated from the OS but not yet allocated from
 112   // the zone.
 113   int segment_bytes_allocated_;
 114
 115   // Expand the Zone to hold at least 'size' more bytes and allocate
 116   // the bytes. Returns the address of the newly allocated chunk of
 117   // memory in the Zone. Should only be called if there isn't enough
 118   // room in the Zone already.
 119   Address NewExpand(int size);
 120
 121   // Creates a new segment, sets it size, and pushes it to the front
 122   // of the segment chain. Returns the new segment.
 123   INLINE(Segment* NewSegment(int size));
 124
 125   // Deletes the given segment. Does not touch the segment chain.
 126   INLINE(void DeleteSegment(Segment* segment, int size));
 127
 128   // The free region in the current (front) segment is represented as
 129   // the half-open interval [position, limit). The 'position' variable
 130   // is guaranteed to be aligned as dictated by kAlignment.
 131   Address position_;
 132   Address limit_;
 133
 134   Segment* segment_head_;
 135   Isolate* isolate_;
 136 };
 137
 138
 139 // ZoneObject is an abstraction that helps define classes of objects
 140 // allocated in the Zone. Use it as a base class; see ast.h.
 141 class ZoneObject {
 142  public:
 143   // Allocate a new ZoneObject of 'size' bytes in the Zone.
 144   INLINE(void* operator new(size_t size, Zone* zone));
 145
 146   // Ideally, the delete operator should be private instead of
 147   // public, but unfortunately the compiler sometimes synthesizes
 148   // (unused) destructors for classes derived from ZoneObject, which
 149   // require the operator to be visible. MSVC requires the delete
 150   // operator to be public.
 151
 152   // ZoneObjects should never be deleted individually; use
 153   // Zone::DeleteAll() to delete all zone objects in one go.
 154   void operator delete(void*, size_t) { UNREACHABLE(); }
 155   void operator delete(void* pointer, Zone* zone) { UNREACHABLE(); }
 156 };
 157
 158
 159 // The ZoneScope is used to automatically call DeleteAll() on a
 160 // Zone when the ZoneScope is destroyed (i.e. goes out of scope)
 161 struct ZoneScope {
 162  public:
 163   explicit ZoneScope(Zone* zone) : zone_(zone) { }
 164   ~ZoneScope() { zone_->DeleteAll(); }
 165
 166   Zone* zone() { return zone_; }
 167
 168  private:
 169   Zone* zone_;
 170 };
 171
 172
 173 // The ZoneAllocationPolicy is used to specialize generic data
 174 // structures to allocate themselves and their elements in the Zone.
 175 struct ZoneAllocationPolicy {
 176  public:
 177   explicit ZoneAllocationPolicy(Zone* zone) : zone_(zone) { }
 178   INLINE(void* New(size_t size));
 179   INLINE(static void Delete(void *pointer)) { }
 180   Zone* zone() { return zone_; }
 181
 182  private:
 183   Zone* zone_;
 184 };
 185
 186
 187 // ZoneLists are growable lists with constant-time access to the
 188 // elements. The list itself and all its elements are allocated in the
 189 // Zone. ZoneLists cannot be deleted individually; you can delete all
 190 // objects in the Zone by calling Zone::DeleteAll().
 191 template<typename T>
 192 class ZoneList: public List<T, ZoneAllocationPolicy> {
 193  public:
 194   // Construct a new ZoneList with the given capacity; the length is
 195   // always zero. The capacity must be non-negative.
 196   ZoneList(int capacity, Zone* zone)
 197       : List<T, ZoneAllocationPolicy>(capacity, ZoneAllocationPolicy(zone)) { }
 198
 199   INLINE(void* operator new(size_t size, Zone* zone));
 200
 201   // Construct a new ZoneList by copying the elements of the given ZoneList.
 202   ZoneList(const ZoneList<T>& other, Zone* zone)
 203       : List<T, ZoneAllocationPolicy>(other.length(),
 204                                       ZoneAllocationPolicy(zone)) {
 205     AddAll(other, zone);
 206   }
 207
 208   // We add some convenience wrappers so that we can pass in a Zone
 209   // instead of a (less convenient) ZoneAllocationPolicy.
 210   INLINE(void Add(const T& element, Zone* zone)) {
 211     List<T, ZoneAllocationPolicy>::Add(element, ZoneAllocationPolicy(zone));
 212   }
 213   INLINE(void AddAll(const List<T, ZoneAllocationPolicy>& other, Zone* zone)) {
 214     List<T, ZoneAllocationPolicy>::AddAll(other, ZoneAllocationPolicy(zone));
 215   }
 216   INLINE(void AddAll(const Vector<T>& other, Zone* zone)) {
 217     List<T, ZoneAllocationPolicy>::AddAll(other, ZoneAllocationPolicy(zone));
 218   }
 219   INLINE(void InsertAt(int index, const T& element, Zone* zone)) {
 220     List<T, ZoneAllocationPolicy>::InsertAt(index, element,
 221                                             ZoneAllocationPolicy(zone));
 222   }
 223   INLINE(Vector<T> AddBlock(T value, int count, Zone* zone)) {
 224     return List<T, ZoneAllocationPolicy>::AddBlock(value, count,
 225                                                    ZoneAllocationPolicy(zone));
 226   }
 227   INLINE(void Allocate(int length, Zone* zone)) {
 228     List<T, ZoneAllocationPolicy>::Allocate(length, ZoneAllocationPolicy(zone));
 229   }
 230   INLINE(void Initialize(int capacity, Zone* zone)) {
 231     List<T, ZoneAllocationPolicy>::Initialize(capacity,
 232                                               ZoneAllocationPolicy(zone));
 233   }
 234
 235   void operator delete(void* pointer) { UNREACHABLE(); }
 236   void operator delete(void* pointer, Zone* zone) { UNREACHABLE(); }
 237 };
 238
 239
 240 // A zone splay tree.  The config type parameter encapsulates the
 241 // different configurations of a concrete splay tree (see splay-tree.h).
 242 // The tree itself and all its elements are allocated in the Zone.
 243 template <typename Config>
 244 class ZoneSplayTree: public SplayTree<Config, ZoneAllocationPolicy> {
 245  public:
 246   explicit ZoneSplayTree(Zone* zone)
 247       : SplayTree<Config, ZoneAllocationPolicy>(ZoneAllocationPolicy(zone)) {}
 248   ~ZoneSplayTree();
 249
 250   INLINE(void* operator new(size_t size, Zone* zone));
 251
 252   void operator delete(void* pointer) { UNREACHABLE(); }
 253   void operator delete(void* pointer, Zone* zone) { UNREACHABLE(); }
 254 };
 255
 256
 257 typedef TemplateHashMapImpl<ZoneAllocationPolicy> ZoneHashMap;
 258
 259 } }  // namespace v8::internal
 260
 261 #endif  // V8_ZONE_H_