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