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/globals.h"
13 : #include "src/splay-tree.h"
14 : #include "src/zone/accounting-allocator.h"
15 :
16 : #ifndef ZONE_NAME
17 : #define STRINGIFY(x) #x
18 : #define TOSTRING(x) STRINGIFY(x)
19 : #define ZONE_NAME __FILE__ ":" TOSTRING(__LINE__)
20 : #endif
21 :
22 : namespace v8 {
23 : namespace internal {
24 :
25 : // The Zone supports very fast allocation of small chunks of
26 : // memory. The chunks cannot be deallocated individually, but instead
27 : // the Zone supports deallocating all chunks in one fast
28 : // operation. The Zone is used to hold temporary data structures like
29 : // the abstract syntax tree, which is deallocated after compilation.
30 : //
31 : // Note: There is no need to initialize the Zone; the first time an
32 : // allocation is attempted, a segment of memory will be requested
33 : // through the allocator.
34 : //
35 : // Note: The implementation is inherently not thread safe. Do not use
36 : // from multi-threaded code.
37 : class V8_EXPORT_PRIVATE Zone final {
38 : public:
39 : Zone(AccountingAllocator* allocator, const char* name);
40 : ~Zone();
41 :
42 : // Allocate 'size' bytes of memory in the Zone; expands the Zone by
43 : // allocating new segments of memory on demand using malloc().
44 : void* New(size_t size);
45 :
46 : template <typename T>
47 : T* NewArray(size_t length) {
48 : DCHECK_LT(length, std::numeric_limits<size_t>::max() / sizeof(T));
49 680871644 : return static_cast<T*>(New(length * sizeof(T)));
50 : }
51 :
52 : // Seals the zone to prevent any further allocation.
53 : void Seal() { sealed_ = true; }
54 :
55 : // Returns true if more memory has been allocated in zones than
56 : // the limit allows.
57 : bool excess_allocation() const {
58 : return segment_bytes_allocated_ > kExcessLimit;
59 : }
60 :
61 : const char* name() const { return name_; }
62 :
63 : size_t allocation_size() const { return allocation_size_; }
64 :
65 : AccountingAllocator* allocator() const { return allocator_; }
66 :
67 : private:
68 : // All pointers returned from New() are 8-byte aligned.
69 : static const size_t kAlignmentInBytes = 8;
70 :
71 : // Never allocate segments smaller than this size in bytes.
72 : static const size_t kMinimumSegmentSize = 8 * KB;
73 :
74 : // Never allocate segments larger than this size in bytes.
75 : static const size_t kMaximumSegmentSize = 1 * MB;
76 :
77 : // Report zone excess when allocation exceeds this limit.
78 : static const size_t kExcessLimit = 256 * MB;
79 :
80 : // Deletes all objects and free all memory allocated in the Zone.
81 : void DeleteAll();
82 :
83 : // The number of bytes allocated in this zone so far.
84 : size_t allocation_size_;
85 :
86 : // The number of bytes allocated in segments. Note that this number
87 : // includes memory allocated from the OS but not yet allocated from
88 : // the zone.
89 : size_t segment_bytes_allocated_;
90 :
91 : // Expand the Zone to hold at least 'size' more bytes and allocate
92 : // the bytes. Returns the address of the newly allocated chunk of
93 : // memory in the Zone. Should only be called if there isn't enough
94 : // room in the Zone already.
95 : Address NewExpand(size_t size);
96 :
97 : // Creates a new segment, sets it size, and pushes it to the front
98 : // of the segment chain. Returns the new segment.
99 : inline Segment* NewSegment(size_t requested_size);
100 :
101 : // The free region in the current (front) segment is represented as
102 : // the half-open interval [position, limit). The 'position' variable
103 : // is guaranteed to be aligned as dictated by kAlignment.
104 : Address position_;
105 : Address limit_;
106 :
107 : AccountingAllocator* allocator_;
108 :
109 : Segment* segment_head_;
110 : const char* name_;
111 : bool sealed_;
112 : };
113 :
114 : // ZoneObject is an abstraction that helps define classes of objects
115 : // allocated in the Zone. Use it as a base class; see ast.h.
116 : class ZoneObject {
117 : public:
118 : // Allocate a new ZoneObject of 'size' bytes in the Zone.
119 924697302 : void* operator new(size_t size, Zone* zone) { return zone->New(size); }
120 :
121 : // Ideally, the delete operator should be private instead of
122 : // public, but unfortunately the compiler sometimes synthesizes
123 : // (unused) destructors for classes derived from ZoneObject, which
124 : // require the operator to be visible. MSVC requires the delete
125 : // operator to be public.
126 :
127 : // ZoneObjects should never be deleted individually; use
128 : // Zone::DeleteAll() to delete all zone objects in one go.
129 0 : void operator delete(void*, size_t) { UNREACHABLE(); }
130 : void operator delete(void* pointer, Zone* zone) { UNREACHABLE(); }
131 : };
132 :
133 : // The ZoneAllocationPolicy is used to specialize generic data
134 : // structures to allocate themselves and their elements in the Zone.
135 : class ZoneAllocationPolicy final {
136 : public:
137 189710347 : explicit ZoneAllocationPolicy(Zone* zone) : zone_(zone) {}
138 380365628 : void* New(size_t size) { return zone()->New(size); }
139 : static void Delete(void* pointer) {}
140 205067322 : Zone* zone() const { return zone_; }
141 :
142 : private:
143 : Zone* zone_;
144 : };
145 :
146 : template <typename T>
147 : class Vector;
148 :
149 : // ZoneLists are growable lists with constant-time access to the
150 : // elements. The list itself and all its elements are allocated in the
151 : // Zone. ZoneLists cannot be deleted individually; you can delete all
152 : // objects in the Zone by calling Zone::DeleteAll().
153 : template <typename T>
154 : class ZoneList final {
155 : public:
156 : // Construct a new ZoneList with the given capacity; the length is
157 : // always zero. The capacity must be non-negative.
158 349222410 : ZoneList(int capacity, Zone* zone) { Initialize(capacity, zone); }
159 : // Construct a new ZoneList from a std::initializer_list
160 9632 : ZoneList(std::initializer_list<T> list, Zone* zone) {
161 9632 : Initialize(static_cast<int>(list.size()), zone);
162 9632 : for (auto& i : list) Add(i, zone);
163 9632 : }
164 : // Construct a new ZoneList by copying the elements of the given ZoneList.
165 17811 : ZoneList(const ZoneList<T>& other, Zone* zone) {
166 : Initialize(other.length(), zone);
167 : AddAll(other, zone);
168 17811 : }
169 :
170 : INLINE(~ZoneList()) { DeleteData(data_); }
171 :
172 : // Please the MSVC compiler. We should never have to execute this.
173 : INLINE(void operator delete(void* p, ZoneAllocationPolicy allocator)) {
174 : UNREACHABLE();
175 : }
176 :
177 73352146 : void* operator new(size_t size, Zone* zone) { return zone->New(size); }
178 :
179 : // Returns a reference to the element at index i. This reference is not safe
180 : // to use after operations that can change the list's backing store
181 : // (e.g. Add).
182 : inline T& operator[](int i) const {
183 : DCHECK_LE(0, i);
184 : DCHECK_GT(static_cast<unsigned>(length_), static_cast<unsigned>(i));
185 792269272 : return data_[i];
186 : }
187 753596300 : inline T& at(int i) const { return operator[](i); }
188 26113886 : inline T& last() const { return at(length_ - 1); }
189 : inline T& first() const { return at(0); }
190 :
191 : typedef T* iterator;
192 5702108 : inline iterator begin() const { return &data_[0]; }
193 15018483 : inline iterator end() const { return &data_[length_]; }
194 :
195 : INLINE(bool is_empty() const) { return length_ == 0; }
196 : INLINE(int length() const) { return length_; }
197 : INLINE(int capacity() const) { return capacity_; }
198 :
199 35038 : Vector<T> ToVector() const { return Vector<T>(data_, length_); }
200 :
201 : Vector<const T> ToConstVector() const {
202 2054807 : return Vector<const T>(data_, length_);
203 : }
204 :
205 : INLINE(void Initialize(int capacity, Zone* zone)) {
206 : DCHECK_GE(capacity, 0);
207 349277296 : data_ = (capacity > 0) ? NewData(capacity, ZoneAllocationPolicy(zone))
208 : : nullptr;
209 174638683 : capacity_ = capacity;
210 174638683 : length_ = 0;
211 : }
212 :
213 : // Adds a copy of the given 'element' to the end of the list,
214 : // expanding the list if necessary.
215 1974618 : void Add(const T& element, Zone* zone);
216 : // Add all the elements from the argument list to this list.
217 24721 : void AddAll(const ZoneList<T>& other, Zone* zone);
218 : // Add all the elements from the vector to this list.
219 66469 : void AddAll(const Vector<T>& other, Zone* zone);
220 : // Inserts the element at the specific index.
221 : void InsertAt(int index, const T& element, Zone* zone);
222 :
223 : // Added 'count' elements with the value 'value' and returns a
224 : // vector that allows access to the elements. The vector is valid
225 : // until the next change is made to this list.
226 : Vector<T> AddBlock(T value, int count, Zone* zone);
227 :
228 : // Overwrites the element at the specific index.
229 : void Set(int index, const T& element);
230 :
231 : // Removes the i'th element without deleting it even if T is a
232 : // pointer type; moves all elements above i "down". Returns the
233 : // removed element. This function's complexity is linear in the
234 : // size of the list.
235 : T Remove(int i);
236 :
237 : // Removes the last element without deleting it even if T is a
238 : // pointer type. Returns the removed element.
239 74888423 : INLINE(T RemoveLast()) { return Remove(length_ - 1); }
240 :
241 : // Clears the list by freeing the storage memory. If you want to keep the
242 : // memory, use Rewind(0) instead. Be aware, that even if T is a
243 : // pointer type, clearing the list doesn't delete the entries.
244 : INLINE(void Clear());
245 :
246 : // Drops all but the first 'pos' elements from the list.
247 : INLINE(void Rewind(int pos));
248 :
249 : inline bool Contains(const T& elm) const;
250 :
251 : // Iterate through all list entries, starting at index 0.
252 : template <class Visitor>
253 : void Iterate(Visitor* visitor);
254 :
255 : // Sort all list entries (using QuickSort)
256 : template <typename CompareFunction>
257 : void Sort(CompareFunction cmp);
258 : template <typename CompareFunction>
259 : void StableSort(CompareFunction cmp, size_t start, size_t length);
260 :
261 : void operator delete(void* pointer) { UNREACHABLE(); }
262 : void operator delete(void* pointer, Zone* zone) { UNREACHABLE(); }
263 :
264 : private:
265 : T* data_;
266 : int capacity_;
267 : int length_;
268 :
269 : INLINE(T* NewData(int n, ZoneAllocationPolicy allocator)) {
270 175143343 : return static_cast<T*>(allocator.New(n * sizeof(T)));
271 : }
272 : INLINE(void DeleteData(T* data)) { ZoneAllocationPolicy::Delete(data); }
273 :
274 : // Increase the capacity of a full list, and add an element.
275 : // List must be full already.
276 : void ResizeAdd(const T& element, ZoneAllocationPolicy allocator);
277 :
278 : // Inlined implementation of ResizeAdd, shared by inlined and
279 : // non-inlined versions of ResizeAdd.
280 : void ResizeAddInternal(const T& element, ZoneAllocationPolicy allocator);
281 :
282 : // Resize the list.
283 : void Resize(int new_capacity, ZoneAllocationPolicy allocator);
284 :
285 : DISALLOW_COPY_AND_ASSIGN(ZoneList);
286 : };
287 :
288 : // A zone splay tree. The config type parameter encapsulates the
289 : // different configurations of a concrete splay tree (see splay-tree.h).
290 : // The tree itself and all its elements are allocated in the Zone.
291 : template <typename Config>
292 : class ZoneSplayTree final : public SplayTree<Config, ZoneAllocationPolicy> {
293 : public:
294 : explicit ZoneSplayTree(Zone* zone)
295 : : SplayTree<Config, ZoneAllocationPolicy>(ZoneAllocationPolicy(zone)) {}
296 : ~ZoneSplayTree() {
297 : // Reset the root to avoid unneeded iteration over all tree nodes
298 : // in the destructor. For a zone-allocated tree, nodes will be
299 : // freed by the Zone.
300 : SplayTree<Config, ZoneAllocationPolicy>::ResetRoot();
301 : }
302 :
303 : void* operator new(size_t size, Zone* zone) { return zone->New(size); }
304 :
305 : void operator delete(void* pointer) { UNREACHABLE(); }
306 : void operator delete(void* pointer, Zone* zone) { UNREACHABLE(); }
307 : };
308 :
309 : typedef base::PointerTemplateHashMapImpl<ZoneAllocationPolicy> ZoneHashMap;
310 :
311 : typedef base::CustomMatcherTemplateHashMapImpl<ZoneAllocationPolicy>
312 : CustomMatcherZoneHashMap;
313 :
314 : } // namespace internal
315 : } // namespace v8
316 :
317 : #endif // V8_ZONE_ZONE_H_
|
