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