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 <algorithm>
9 : #include <limits>
10 : #include <vector>
11 :
12 : #include "src/base/hashmap.h"
13 : #include "src/base/logging.h"
14 : #include "src/globals.h"
15 : #include "src/zone/accounting-allocator.h"
16 : #include "src/zone/zone-segment.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 3357330989 : void* New(size_t size) {
51 : #ifdef V8_USE_ADDRESS_SANITIZER
52 : return AsanNew(size);
53 : #else
54 : size = RoundUp(size, kAlignmentInBytes);
55 3456710005 : Address result = position_;
56 3456710005 : if (V8_UNLIKELY(size > limit_ - position_)) {
57 59518796 : result = NewExpand(size);
58 : } else {
59 3397191209 : position_ += size;
60 : }
61 3456741331 : 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 1481741948 : 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 698620109 : size_t extra = segment_head_ ? position_ - segment_head_->start() : 0;
89 443775983 : 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 1302296606 : 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 253049731 : explicit ZoneAllocationPolicy(Zone* zone) : zone_(zone) {}
166 68056931 : void* New(size_t size) { return zone()->New(size); }
167 : static void Delete(void* pointer) {}
168 31084666 : 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 566 : ZoneList(const ZoneList<T>& other, Zone* zone) {
194 : Initialize(other.length(), zone);
195 : AddAll(other, zone);
196 566 : }
197 :
198 1252879 : 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 6404335 : 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 218516642 : return data_[i];
214 : }
215 : inline T& at(int i) const { return operator[](i); }
216 9573142 : 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 619767 : inline iterator end() const { return &data_[length_]; }
222 :
223 7412340 : V8_INLINE bool is_empty() const { return length_ == 0; }
224 124051515 : V8_INLINE int length() const { return length_; }
225 : V8_INLINE int capacity() const { return capacity_; }
226 :
227 806 : Vector<T> ToVector() const { return Vector<T>(data_, length_); }
228 : Vector<T> ToVector(int start, int length) const {
229 : return Vector<T>(data_ + start, std::min(length_ - start, length));
230 : }
231 :
232 : Vector<const T> ToConstVector() const {
233 1903872 : return Vector<const T>(data_, length_);
234 : }
235 :
236 : V8_INLINE void Initialize(int capacity, Zone* zone) {
237 : DCHECK_GE(capacity, 0);
238 78694202 : data_ = (capacity > 0) ? NewData(capacity, ZoneAllocationPolicy(zone))
239 : : nullptr;
240 60373532 : capacity_ = capacity;
241 60373532 : 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 14333 : 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 151651732 : 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 20469069 : 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 : explicit ScopedPtrList(std::vector<void*>* buffer)
333 270975127 : : buffer_(*buffer), start_(buffer->size()), end_(buffer->size()) {}
334 :
335 101915883 : ~ScopedPtrList() { Rewind(); }
336 :
337 : void Rewind() {
338 : DCHECK_EQ(buffer_.size(), end_);
339 104644027 : buffer_.resize(start_);
340 75049223 : end_ = start_;
341 : }
342 :
343 : void MergeInto(ScopedPtrList* parent) {
344 : DCHECK_EQ(parent->end_, start_);
345 1804078 : parent->end_ = end_;
346 1804078 : start_ = end_;
347 : DCHECK_EQ(0, length());
348 : }
349 :
350 79393127 : int length() const { return static_cast<int>(end_ - start_); }
351 : T* at(int i) const {
352 7089492 : size_t index = start_ + i;
353 : DCHECK_LE(start_, index);
354 : DCHECK_LT(index, buffer_.size());
355 7491244 : return reinterpret_cast<T*>(buffer_[index]);
356 : }
357 :
358 24882872 : 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 24882872 : if (length() == 0) return;
362 : target->Initialize(length(), zone);
363 16258704 : T** data = reinterpret_cast<T**>(&buffer_[start_]);
364 32517408 : target->AddAll(Vector<T*>(data, length()), zone);
365 : }
366 :
367 2683887 : Vector<T*> CopyTo(Zone* zone) {
368 : DCHECK_LE(end_, buffer_.size());
369 2683887 : T** data = zone->NewArray<T*>(length());
370 2683900 : if (length() != 0) {
371 101833 : MemCopy(data, &buffer_[start_], length() * sizeof(T*));
372 : }
373 2683900 : return Vector<T*>(data, length());
374 : }
375 :
376 : void Add(T* value) {
377 : DCHECK_EQ(buffer_.size(), end_);
378 235894400 : buffer_.push_back(value);
379 117899984 : ++end_;
380 : }
381 :
382 7195 : void AddAll(const ZonePtrList<T>& list) {
383 : DCHECK_EQ(buffer_.size(), end_);
384 14390 : buffer_.reserve(buffer_.size() + list.length());
385 18379 : for (int i = 0; i < list.length(); i++) {
386 11184 : buffer_.push_back(list.at(i));
387 : }
388 7195 : end_ += list.length();
389 7195 : }
390 :
391 : typedef T** iterator;
392 : inline iterator begin() const {
393 3743994 : return reinterpret_cast<T**>(buffer_.data() + start_);
394 : }
395 : inline iterator end() const {
396 3743994 : return reinterpret_cast<T**>(buffer_.data() + end_);
397 : }
398 :
399 : private:
400 : std::vector<void*>& buffer_;
401 : size_t start_;
402 : size_t end_;
403 : };
404 :
405 : typedef base::PointerTemplateHashMapImpl<ZoneAllocationPolicy> ZoneHashMap;
406 :
407 : typedef base::CustomMatcherTemplateHashMapImpl<ZoneAllocationPolicy>
408 : CustomMatcherZoneHashMap;
409 :
410 : } // namespace internal
411 : } // namespace v8
412 :
413 : // The accidential pattern
414 : // new (zone) SomeObject()
415 : // where SomeObject does not inherit from ZoneObject leads to nasty crashes.
416 : // This triggers a compile-time error instead.
417 : template <class T, typename = typename std::enable_if<std::is_convertible<
418 : T, const v8::internal::Zone*>::value>::type>
419 : void* operator new(size_t size, T zone) {
420 : static_assert(false && sizeof(T),
421 : "Placement new with a zone is only permitted for classes "
422 : "inheriting from ZoneObject");
423 : UNREACHABLE();
424 : }
425 :
426 : #endif // V8_ZONE_ZONE_H_
|
