Line data Source code
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 3261785356 : void* New(size_t size) {
51 : #ifdef V8_USE_ADDRESS_SANITIZER
52 : return AsanNew(size);
53 : #else
54 0 : size = RoundUp(size, kAlignmentInBytes);
55 3261785356 : Address result = position_;
56 3261785356 : if (V8_UNLIKELY(size > limit_ - position_)) {
57 52055863 : result = NewExpand(size);
58 : } else {
59 3209729493 : position_ += size;
60 : }
61 3261789738 : return reinterpret_cast<void*>(result);
62 : #endif
63 : }
64 : void* AsanNew(size_t size);
65 :
66 : template <typename T>
67 63096 : T* NewArray(size_t length) {
68 : DCHECK_LT(length, std::numeric_limits<size_t>::max() / sizeof(T));
69 1392130970 : 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 566478182 : size_t extra = segment_head_ ? position_ - segment_head_->start() : 0;
89 360839237 : 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 1220913746 : 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 0 : 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 279478196 : explicit ZoneAllocationPolicy(Zone* zone) : zone_(zone) {}
166 103012364 : void* New(size_t size) { return zone()->New(size); }
167 : static void Delete(void* pointer) {}
168 66667594 : 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 86874774 : 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 566 : ZoneList(const ZoneList<T>& other, Zone* zone) {
194 : Initialize(other.length(), zone);
195 : AddAll(other, zone);
196 566 : }
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 6352398 : 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 2467847 : inline T& operator[](int i) const {
211 : DCHECK_LE(0, i);
212 : DCHECK_GT(static_cast<unsigned>(length_), static_cast<unsigned>(i));
213 218409878 : return data_[i];
214 : }
215 196558191 : inline T& at(int i) const { return operator[](i); }
216 9488243 : inline T& last() const { return at(length_ - 1); }
217 : inline T& first() const { return at(0); }
218 :
219 : typedef T* iterator;
220 86328 : inline iterator begin() const { return &data_[0]; }
221 457056 : inline iterator end() const { return &data_[length_]; }
222 :
223 356393 : 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 9433 : 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 1863550 : return Vector<const T>(data_, length_);
234 : }
235 :
236 : V8_INLINE void Initialize(int capacity, Zone* zone) {
237 : DCHECK_GE(capacity, 0);
238 118731218 : data_ = (capacity > 0) ? NewData(capacity, ZoneAllocationPolicy(zone))
239 : : nullptr;
240 59365713 : capacity_ = capacity;
241 59365713 : 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 1176804 : void Add(const T& element, Zone* zone);
247 : // Add all the elements from the argument list to this list.
248 806 : void AddAll(const ZoneList<T>& other, Zone* zone);
249 : // Add all the elements from the vector to this list.
250 80520389 : 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 14142 : 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 67492148 : for (int i = 0; i < length_; i++) {
282 67816782 : if (data_[i] == elm) return true;
283 : }
284 : return false;
285 : }
286 :
287 : // Iterate through all list entries, starting at index 0.
288 : template <class Visitor>
289 : void Iterate(Visitor* visitor);
290 :
291 : // Sort all list entries (using QuickSort)
292 : template <typename CompareFunction>
293 : void Sort(CompareFunction cmp);
294 : template <typename CompareFunction>
295 : void StableSort(CompareFunction cmp, size_t start, size_t length);
296 :
297 : void operator delete(void* pointer) { UNREACHABLE(); }
298 : void operator delete(void* pointer, Zone* zone) { UNREACHABLE(); }
299 :
300 : private:
301 : T* data_;
302 : int capacity_;
303 : int length_;
304 :
305 : V8_INLINE T* NewData(int n, ZoneAllocationPolicy allocator) {
306 36088409 : return static_cast<T*>(allocator.New(n * sizeof(T)));
307 : }
308 : V8_INLINE void DeleteData(T* data) { ZoneAllocationPolicy::Delete(data); }
309 :
310 : // Increase the capacity of a full list, and add an element.
311 : // List must be full already.
312 : void ResizeAdd(const T& element, ZoneAllocationPolicy allocator);
313 :
314 : // Inlined implementation of ResizeAdd, shared by inlined and
315 : // non-inlined versions of ResizeAdd.
316 : void ResizeAddInternal(const T& element, ZoneAllocationPolicy allocator);
317 :
318 : // Resize the list.
319 : void Resize(int new_capacity, ZoneAllocationPolicy allocator);
320 :
321 : DISALLOW_COPY_AND_ASSIGN(ZoneList);
322 : };
323 :
324 : // ZonePtrList is a ZoneList of pointers to ZoneObjects allocated in the same
325 : // zone as the list object.
326 : template <typename T>
327 : using ZonePtrList = ZoneList<T*>;
328 :
329 : template <typename T>
330 : class ScopedPtrList final {
331 : public:
332 163992975 : explicit ScopedPtrList(std::vector<void*>* buffer)
333 266867942 : : buffer_(*buffer), start_(buffer->size()), end_(buffer->size()) {}
334 :
335 181923 : ~ScopedPtrList() { Rewind(); }
336 :
337 : void Rewind() {
338 : DCHECK_EQ(buffer_.size(), end_);
339 102979505 : buffer_.resize(start_);
340 73886399 : end_ = start_;
341 : }
342 :
343 : void MergeInto(ScopedPtrList* parent) {
344 : DCHECK_EQ(parent->end_, start_);
345 1773171 : parent->end_ = end_;
346 1773171 : start_ = end_;
347 : DCHECK_EQ(0, length());
348 : }
349 :
350 105817912 : int length() const { return static_cast<int>(end_ - start_); }
351 : T* at(int i) const {
352 10850966 : size_t index = start_ + i;
353 : DCHECK_LE(start_, index);
354 : DCHECK_LT(index, buffer_.size());
355 22449303 : return reinterpret_cast<T*>(buffer_[index]);
356 : }
357 :
358 40341561 : void CopyTo(ZonePtrList<T>* target, Zone* zone) const {
359 : DCHECK_LE(end_, buffer_.size());
360 : // Make sure we don't reference absent elements below.
361 48827829 : if (length() == 0) return;
362 : target->Initialize(length(), zone);
363 15927744 : T** data = reinterpret_cast<T**>(&buffer_[start_]);
364 31855488 : target->AddAll(Vector<T*>(data, length()), zone);
365 : }
366 :
367 7880319 : Vector<T*> CopyTo(Zone* zone) {
368 : DCHECK_LE(end_, buffer_.size());
369 2626679 : T** data = zone->NewArray<T*>(length());
370 2626820 : MemCopy(data, &buffer_[start_], length() * sizeof(T*));
371 2626820 : return Vector<T*>(data, length());
372 : }
373 :
374 18959521 : void Add(T* value) {
375 : DCHECK_EQ(buffer_.size(), end_);
376 233936566 : buffer_.push_back(value);
377 116967803 : ++end_;
378 18959485 : }
379 :
380 27101 : void AddAll(const ZonePtrList<T>& list) {
381 : DCHECK_EQ(buffer_.size(), end_);
382 14352 : buffer_.reserve(buffer_.size() + list.length());
383 18322 : for (int i = 0; i < list.length(); i++) {
384 11146 : buffer_.push_back(list.at(i));
385 : }
386 7176 : end_ += list.length();
387 7176 : }
388 :
389 : private:
390 : std::vector<void*>& buffer_;
391 : size_t start_;
392 : size_t end_;
393 : };
394 :
395 : // ZoneThreadedList is a special variant of the ThreadedList that can be put
396 : // into a Zone.
397 : template <typename T, typename TLTraits = base::ThreadedListTraits<T>>
398 : using ZoneThreadedList = base::ThreadedListBase<T, ZoneObject, TLTraits>;
399 :
400 : // A zone splay tree. The config type parameter encapsulates the
401 : // different configurations of a concrete splay tree (see splay-tree.h).
402 : // The tree itself and all its elements are allocated in the Zone.
403 : template <typename Config>
404 : class ZoneSplayTree final : public SplayTree<Config, ZoneAllocationPolicy> {
405 : public:
406 : explicit ZoneSplayTree(Zone* zone)
407 : : SplayTree<Config, ZoneAllocationPolicy>(ZoneAllocationPolicy(zone)) {}
408 : ~ZoneSplayTree() {
409 : // Reset the root to avoid unneeded iteration over all tree nodes
410 : // in the destructor. For a zone-allocated tree, nodes will be
411 : // freed by the Zone.
412 : SplayTree<Config, ZoneAllocationPolicy>::ResetRoot();
413 : }
414 :
415 : void* operator new(size_t size, Zone* zone) { return zone->New(size); }
416 :
417 : void operator delete(void* pointer) { UNREACHABLE(); }
418 : void operator delete(void* pointer, Zone* zone) { UNREACHABLE(); }
419 : };
420 :
421 : typedef base::PointerTemplateHashMapImpl<ZoneAllocationPolicy> ZoneHashMap;
422 :
423 : typedef base::CustomMatcherTemplateHashMapImpl<ZoneAllocationPolicy>
424 : CustomMatcherZoneHashMap;
425 :
426 : } // namespace internal
427 : } // namespace v8
428 :
429 : // The accidential pattern
430 : // new (zone) SomeObject()
431 : // where SomeObject does not inherit from ZoneObject leads to nasty crashes.
432 : // This triggers a compile-time error instead.
433 : template <class T, typename = typename std::enable_if<std::is_convertible<
434 : T, const v8::internal::Zone*>::value>::type>
435 : void* operator new(size_t size, T zone) {
436 : static_assert(false && sizeof(T),
437 : "Placement new with a zone is only permitted for classes "
438 : "inheriting from ZoneObject");
439 : UNREACHABLE();
440 : }
441 :
442 : #endif // V8_ZONE_ZONE_H_
|
