V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
zone.h
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/base/threaded-list.h"
13 #include "src/globals.h"
14 #include "src/splay-tree.h"
15 #include "src/utils.h"
16 #include "src/zone/accounting-allocator.h"
17 
18 #ifndef ZONE_NAME
19 #define STRINGIFY(x) #x
20 #define TOSTRING(x) STRINGIFY(x)
21 #define ZONE_NAME __FILE__ ":" TOSTRING(__LINE__)
22 #endif
23 
24 namespace v8 {
25 namespace internal {
26 
27 // The Zone supports very fast allocation of small chunks of
28 // memory. The chunks cannot be deallocated individually, but instead
29 // the Zone supports deallocating all chunks in one fast
30 // operation. The Zone is used to hold temporary data structures like
31 // the abstract syntax tree, which is deallocated after compilation.
32 //
33 // Note: There is no need to initialize the Zone; the first time an
34 // allocation is attempted, a segment of memory will be requested
35 // through the allocator.
36 //
37 // Note: The implementation is inherently not thread safe. Do not use
38 // from multi-threaded code.
39 
40 enum class SegmentSize { kLarge, kDefault };
41 
42 class V8_EXPORT_PRIVATE Zone final {
43  public:
44  Zone(AccountingAllocator* allocator, const char* name,
45  SegmentSize segment_size = SegmentSize::kDefault);
46  ~Zone();
47 
48  // Allocate 'size' bytes of memory in the Zone; expands the Zone by
49  // allocating new segments of memory on demand using malloc().
50  void* New(size_t size) {
51 #ifdef V8_USE_ADDRESS_SANITIZER
52  return AsanNew(size);
53 #else
54  size = RoundUp(size, kAlignmentInBytes);
55  Address result = position_;
56  if (V8_UNLIKELY(size > limit_ - position_)) {
57  result = NewExpand(size);
58  } else {
59  position_ += size;
60  }
61  return reinterpret_cast<void*>(result);
62 #endif
63  }
64  void* AsanNew(size_t size);
65 
66  template <typename T>
67  T* NewArray(size_t length) {
68  DCHECK_LT(length, std::numeric_limits<size_t>::max() / sizeof(T));
69  return static_cast<T*>(New(length * sizeof(T)));
70  }
71 
72  // Seals the zone to prevent any further allocation.
73  void Seal() { sealed_ = true; }
74 
75  // Allows the zone to be safely reused. Releases the memory and fires zone
76  // destruction and creation events for the accounting allocator.
77  void ReleaseMemory();
78 
79  // Returns true if more memory has been allocated in zones than
80  // the limit allows.
81  bool excess_allocation() const {
82  return segment_bytes_allocated_ > kExcessLimit;
83  }
84 
85  const char* name() const { return name_; }
86 
87  size_t allocation_size() const {
88  size_t extra = segment_head_ ? position_ - segment_head_->start() : 0;
89  return allocation_size_ + extra;
90  }
91 
92  AccountingAllocator* allocator() const { return allocator_; }
93 
94  private:
95  // Deletes all objects and free all memory allocated in the Zone.
96  void DeleteAll();
97 
98  // All pointers returned from New() are 8-byte aligned.
99  static const size_t kAlignmentInBytes = 8;
100 
101  // Never allocate segments smaller than this size in bytes.
102  static const size_t kMinimumSegmentSize = 8 * KB;
103 
104  // Never allocate segments larger than this size in bytes.
105  static const size_t kMaximumSegmentSize = 1 * MB;
106 
107  // Report zone excess when allocation exceeds this limit.
108  static const size_t kExcessLimit = 256 * MB;
109 
110  // The number of bytes allocated in this zone so far.
111  size_t allocation_size_;
112 
113  // The number of bytes allocated in segments. Note that this number
114  // includes memory allocated from the OS but not yet allocated from
115  // the zone.
116  size_t segment_bytes_allocated_;
117 
118  // Expand the Zone to hold at least 'size' more bytes and allocate
119  // the bytes. Returns the address of the newly allocated chunk of
120  // memory in the Zone. Should only be called if there isn't enough
121  // room in the Zone already.
122  Address NewExpand(size_t size);
123 
124  // Creates a new segment, sets it size, and pushes it to the front
125  // of the segment chain. Returns the new segment.
126  inline Segment* NewSegment(size_t requested_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  AccountingAllocator* allocator_;
135 
136  Segment* segment_head_;
137  const char* name_;
138  bool sealed_;
139  SegmentSize segment_size_;
140 };
141 
142 // ZoneObject is an abstraction that helps define classes of objects
143 // allocated in the Zone. Use it as a base class; see ast.h.
144 class ZoneObject {
145  public:
146  // Allocate a new ZoneObject of 'size' bytes in the Zone.
147  void* operator new(size_t size, Zone* zone) { return zone->New(size); }
148 
149  // Ideally, the delete operator should be private instead of
150  // public, but unfortunately the compiler sometimes synthesizes
151  // (unused) destructors for classes derived from ZoneObject, which
152  // require the operator to be visible. MSVC requires the delete
153  // operator to be public.
154 
155  // ZoneObjects should never be deleted individually; use
156  // Zone::DeleteAll() to delete all zone objects in one go.
157  void operator delete(void*, size_t) { UNREACHABLE(); }
158  void operator delete(void* pointer, Zone* zone) { UNREACHABLE(); }
159 };
160 
161 // The ZoneAllocationPolicy is used to specialize generic data
162 // structures to allocate themselves and their elements in the Zone.
163 class ZoneAllocationPolicy final {
164  public:
165  explicit ZoneAllocationPolicy(Zone* zone) : zone_(zone) {}
166  void* New(size_t size) { return zone()->New(size); }
167  static void Delete(void* pointer) {}
168  Zone* zone() const { return zone_; }
169 
170  private:
171  Zone* zone_;
172 };
173 
174 template <typename T>
175 class Vector;
176 
177 // ZoneLists are growable lists with constant-time access to the
178 // elements. The list itself and all its elements are allocated in the
179 // Zone. ZoneLists cannot be deleted individually; you can delete all
180 // objects in the Zone by calling Zone::DeleteAll().
181 template <typename T>
182 class ZoneList final {
183  public:
184  // Construct a new ZoneList with the given capacity; the length is
185  // always zero. The capacity must be non-negative.
186  ZoneList(int capacity, Zone* zone) { Initialize(capacity, zone); }
187  // Construct a new ZoneList from a std::initializer_list
188  ZoneList(std::initializer_list<T> list, Zone* zone) {
189  Initialize(static_cast<int>(list.size()), zone);
190  for (auto& i : list) Add(i, zone);
191  }
192  // Construct a new ZoneList by copying the elements of the given ZoneList.
193  ZoneList(const ZoneList<T>& other, Zone* zone) {
194  Initialize(other.length(), zone);
195  AddAll(other, zone);
196  }
197 
198  V8_INLINE ~ZoneList() { DeleteData(data_); }
199 
200  // Please the MSVC compiler. We should never have to execute this.
201  V8_INLINE void operator delete(void* p, ZoneAllocationPolicy allocator) {
202  UNREACHABLE();
203  }
204 
205  void* operator new(size_t size, Zone* zone) { return zone->New(size); }
206 
207  // Returns a reference to the element at index i. This reference is not safe
208  // to use after operations that can change the list's backing store
209  // (e.g. Add).
210  inline T& operator[](int i) const {
211  DCHECK_LE(0, i);
212  DCHECK_GT(static_cast<unsigned>(length_), static_cast<unsigned>(i));
213  return data_[i];
214  }
215  inline T& at(int i) const { return operator[](i); }
216  inline T& last() const { return at(length_ - 1); }
217  inline T& first() const { return at(0); }
218 
219  typedef T* iterator;
220  inline iterator begin() const { return &data_[0]; }
221  inline iterator end() const { return &data_[length_]; }
222 
223  V8_INLINE bool is_empty() const { return length_ == 0; }
224  V8_INLINE int length() const { return length_; }
225  V8_INLINE int capacity() const { return capacity_; }
226 
227  Vector<T> ToVector() const { return Vector<T>(data_, length_); }
228  Vector<T> ToVector(int start, int length) const {
229  return Vector<T>(data_ + start, Min(length_ - start, length));
230  }
231 
232  Vector<const T> ToConstVector() const {
233  return Vector<const T>(data_, length_);
234  }
235 
236  V8_INLINE void Initialize(int capacity, Zone* zone) {
237  DCHECK_GE(capacity, 0);
238  data_ = (capacity > 0) ? NewData(capacity, ZoneAllocationPolicy(zone))
239  : nullptr;
240  capacity_ = capacity;
241  length_ = 0;
242  }
243 
244  // Adds a copy of the given 'element' to the end of the list,
245  // expanding the list if necessary.
246  void Add(const T& element, Zone* zone);
247  // Add all the elements from the argument list to this list.
248  void AddAll(const ZoneList<T>& other, Zone* zone);
249  // Add all the elements from the vector to this list.
250  void AddAll(const Vector<T>& other, Zone* zone);
251  // Inserts the element at the specific index.
252  void InsertAt(int index, const T& element, Zone* zone);
253 
254  // Added 'count' elements with the value 'value' and returns a
255  // vector that allows access to the elements. The vector is valid
256  // until the next change is made to this list.
257  Vector<T> AddBlock(T value, int count, Zone* zone);
258 
259  // Overwrites the element at the specific index.
260  void Set(int index, const T& element);
261 
262  // Removes the i'th element without deleting it even if T is a
263  // pointer type; moves all elements above i "down". Returns the
264  // removed element. This function's complexity is linear in the
265  // size of the list.
266  T Remove(int i);
267 
268  // Removes the last element without deleting it even if T is a
269  // pointer type. Returns the removed element.
270  V8_INLINE T RemoveLast() { return Remove(length_ - 1); }
271 
272  // Clears the list by freeing the storage memory. If you want to keep the
273  // memory, use Rewind(0) instead. Be aware, that even if T is a
274  // pointer type, clearing the list doesn't delete the entries.
275  V8_INLINE void Clear();
276 
277  // Drops all but the first 'pos' elements from the list.
278  V8_INLINE void Rewind(int pos);
279 
280  inline bool Contains(const T& elm) const;
281 
282  // Iterate through all list entries, starting at index 0.
283  template <class Visitor>
284  void Iterate(Visitor* visitor);
285 
286  // Sort all list entries (using QuickSort)
287  template <typename CompareFunction>
288  void Sort(CompareFunction cmp);
289  template <typename CompareFunction>
290  void StableSort(CompareFunction cmp, size_t start, size_t length);
291 
292  void operator delete(void* pointer) { UNREACHABLE(); }
293  void operator delete(void* pointer, Zone* zone) { UNREACHABLE(); }
294 
295  private:
296  T* data_;
297  int capacity_;
298  int length_;
299 
300  V8_INLINE T* NewData(int n, ZoneAllocationPolicy allocator) {
301  return static_cast<T*>(allocator.New(n * sizeof(T)));
302  }
303  V8_INLINE void DeleteData(T* data) { ZoneAllocationPolicy::Delete(data); }
304 
305  // Increase the capacity of a full list, and add an element.
306  // List must be full already.
307  void ResizeAdd(const T& element, ZoneAllocationPolicy allocator);
308 
309  // Inlined implementation of ResizeAdd, shared by inlined and
310  // non-inlined versions of ResizeAdd.
311  void ResizeAddInternal(const T& element, ZoneAllocationPolicy allocator);
312 
313  // Resize the list.
314  void Resize(int new_capacity, ZoneAllocationPolicy allocator);
315 
316  DISALLOW_COPY_AND_ASSIGN(ZoneList);
317 };
318 
319 // ZonePtrList is a ZoneList of pointers to ZoneObjects allocated in the same
320 // zone as the list object.
321 template <typename T>
322 using ZonePtrList = ZoneList<T*>;
323 
324 template <typename T>
325 class ScopedPtrList final {
326  public:
327  explicit ScopedPtrList(std::vector<void*>* buffer)
328  : buffer_(*buffer), start_(buffer->size()), end_(buffer->size()) {}
329 
330  ~ScopedPtrList() { Rewind(); }
331 
332  void Rewind() {
333  DCHECK_EQ(buffer_.size(), end_);
334  buffer_.resize(start_);
335  end_ = start_;
336  }
337 
338  int length() const { return static_cast<int>(end_ - start_); }
339  T* at(int i) const {
340  size_t index = start_ + i;
341  DCHECK_LT(index, buffer_.size());
342  return reinterpret_cast<T*>(buffer_[index]);
343  }
344 
345  void CopyTo(ZonePtrList<T>* target, Zone* zone) const {
346  DCHECK_LE(end_, buffer_.size());
347  // Make sure we don't reference absent elements below.
348  if (length() == 0) return;
349  target->Initialize(length(), zone);
350  T** data = reinterpret_cast<T**>(&buffer_[start_]);
351  target->AddAll(Vector<T*>(data, length()), zone);
352  }
353 
354  void Add(T* value) {
355  DCHECK_EQ(buffer_.size(), end_);
356  buffer_.push_back(value);
357  ++end_;
358  }
359 
360  void AddAll(const ZonePtrList<T>& list) {
361  DCHECK_EQ(buffer_.size(), end_);
362  buffer_.reserve(buffer_.size() + list.length());
363  for (int i = 0; i < list.length(); i++) {
364  buffer_.push_back(list.at(i));
365  }
366  end_ += list.length();
367  }
368 
369  private:
370  std::vector<void*>& buffer_;
371  size_t start_;
372  size_t end_;
373 };
374 
375 // ZoneThreadedList is a special variant of the ThreadedList that can be put
376 // into a Zone.
377 template <typename T, typename TLTraits = base::ThreadedListTraits<T>>
379 
380 // A zone splay tree. The config type parameter encapsulates the
381 // different configurations of a concrete splay tree (see splay-tree.h).
382 // The tree itself and all its elements are allocated in the Zone.
383 template <typename Config>
384 class ZoneSplayTree final : public SplayTree<Config, ZoneAllocationPolicy> {
385  public:
386  explicit ZoneSplayTree(Zone* zone)
388  ~ZoneSplayTree() {
389  // Reset the root to avoid unneeded iteration over all tree nodes
390  // in the destructor. For a zone-allocated tree, nodes will be
391  // freed by the Zone.
393  }
394 
395  void* operator new(size_t size, Zone* zone) { return zone->New(size); }
396 
397  void operator delete(void* pointer) { UNREACHABLE(); }
398  void operator delete(void* pointer, Zone* zone) { UNREACHABLE(); }
399 };
400 
402 
405 
406 } // namespace internal
407 } // namespace v8
408 
409 // The accidential pattern
410 // new (zone) SomeObject()
411 // where SomeObject does not inherit from ZoneObject leads to nasty crashes.
412 // This triggers a compile-time error instead.
413 template <class T, typename = typename std::enable_if<std::is_convertible<
414  T, const v8::internal::Zone*>::value>::type>
415 void* operator new(size_t size, T zone) {
416  static_assert(false && sizeof(T),
417  "Placement new with a zone is only permitted for classes "
418  "inheriting from ZoneObject");
419  UNREACHABLE();
420 }
421 
422 #endif // V8_ZONE_ZONE_H_
Definition: libplatform.h:13