1// Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_VM_ZONE_H_
6#define RUNTIME_VM_ZONE_H_
7
8#include "platform/utils.h"
9#include "vm/allocation.h"
10#include "vm/handles.h"
11#include "vm/memory_region.h"
12#include "vm/thread_state.h"
13
14namespace dart {
15
16// Zones support very fast allocation of small chunks of memory. The
17// chunks cannot be deallocated individually, but instead zones
18// support deallocating all chunks in one fast operation.
19
20class Zone {
21 public:
22 // Allocate an array sized to hold 'len' elements of type
23 // 'ElementType'. Checks for integer overflow when performing the
24 // size computation.
25 template <class ElementType>
26 inline ElementType* Alloc(intptr_t len);
27
28 // Allocates an array sized to hold 'len' elements of type
29 // 'ElementType'. The new array is initialized from the memory of
30 // 'old_array' up to 'old_len'.
31 template <class ElementType>
32 inline ElementType* Realloc(ElementType* old_array,
33 intptr_t old_len,
34 intptr_t new_len);
35
36 // Allocates 'size' bytes of memory in the zone; expands the zone by
37 // allocating new segments of memory on demand using 'new'.
38 //
39 // It is preferred to use Alloc<T>() instead, as that function can
40 // check for integer overflow. If you use AllocUnsafe, you are
41 // responsible for avoiding integer overflow yourself.
42 inline uword AllocUnsafe(intptr_t size);
43
44 // Make a copy of the string in the zone allocated area.
45 char* MakeCopyOfString(const char* str);
46
47 // Make a copy of the first n characters of a string in the zone
48 // allocated area.
49 char* MakeCopyOfStringN(const char* str, intptr_t len);
50
51 // Concatenate strings |a| and |b|. |a| may be NULL. If |a| is not NULL,
52 // |join| will be inserted between |a| and |b|.
53 char* ConcatStrings(const char* a, const char* b, char join = ',');
54
55 // TODO(zra): Remove these calls and replace them with calls to OS::SCreate
56 // and OS::VSCreate.
57 // These calls are deprecated. Do not add further calls to these functions.
58 // instead use OS::SCreate and OS::VSCreate.
59 // Make a zone-allocated string based on printf format and args.
60 char* PrintToString(const char* format, ...) PRINTF_ATTRIBUTE(2, 3);
61 char* VPrint(const char* format, va_list args);
62
63 // Compute the total size of this zone. This includes wasted space that is
64 // due to internal fragmentation in the segments.
65 uintptr_t SizeInBytes() const;
66
67 // Computes the amount of space used in the zone.
68 uintptr_t CapacityInBytes() const;
69
70 // Structure for managing handles allocation.
71 VMHandles* handles() { return &handles_; }
72
73 void VisitObjectPointers(ObjectPointerVisitor* visitor);
74
75 Zone* previous() const { return previous_; }
76
77 bool ContainsNestedZone(Zone* other) const {
78 while (other != NULL) {
79 if (this == other) return true;
80 other = other->previous_;
81 }
82 return false;
83 }
84
85 // All pointers returned from AllocateUnsafe() and New() have this alignment.
86 static const intptr_t kAlignment = kDoubleSize;
87
88 static void Init();
89 static void Cleanup();
90
91 static intptr_t Size() { return total_size_; }
92
93 private:
94 Zone();
95 ~Zone(); // Delete all memory associated with the zone.
96
97 // Default initial chunk size.
98 static const intptr_t kInitialChunkSize = 1 * KB;
99
100 // Default segment size.
101 static const intptr_t kSegmentSize = 64 * KB;
102
103 // Zap value used to indicate deleted zone area (debug purposes).
104 static const unsigned char kZapDeletedByte = 0x42;
105
106 // Zap value used to indicate uninitialized zone area (debug purposes).
107 static const unsigned char kZapUninitializedByte = 0xab;
108
109 // Total size of current zone segments.
110 static RelaxedAtomic<intptr_t> total_size_;
111
112 // Expand the zone to accommodate an allocation of 'size' bytes.
113 uword AllocateExpand(intptr_t size);
114
115 // Allocate a large segment.
116 uword AllocateLargeSegment(intptr_t size);
117
118 // Insert zone into zone chain, after current_zone.
119 void Link(Zone* current_zone) { previous_ = current_zone; }
120
121 // Delete all objects and free all memory allocated in the zone.
122 void DeleteAll();
123
124 // Does not actually free any memory. Enables templated containers like
125 // BaseGrowableArray to use different allocators.
126 template <class ElementType>
127 void Free(ElementType* old_array, intptr_t len) {
128#ifdef DEBUG
129 if (len > 0) {
130 ASSERT(old_array != nullptr);
131 memset(static_cast<void*>(old_array), kZapUninitializedByte,
132 len * sizeof(ElementType));
133 }
134#endif
135 }
136
137 // Dump the current allocated sizes in the zone object.
138 void DumpZoneSizes();
139
140 // Overflow check (FATAL) for array length.
141 template <class ElementType>
142 static inline void CheckLength(intptr_t len);
143
144 // This buffer is used for allocation before any segments.
145 // This would act as the initial stack allocated chunk so that we don't
146 // end up calling malloc/free on zone scopes that allocate less than
147 // kChunkSize
148 COMPILE_ASSERT(kAlignment <= 8);
149 ALIGN8 uint8_t buffer_[kInitialChunkSize];
150 MemoryRegion initial_buffer_;
151
152 // The free region in the current (head) segment or the initial buffer is
153 // represented as the half-open interval [position, limit). The 'position'
154 // variable is guaranteed to be aligned as dictated by kAlignment.
155 uword position_;
156 uword limit_;
157
158 // Zone segments are internal data structures used to hold information
159 // about the memory segmentations that constitute a zone. The entire
160 // implementation is in zone.cc.
161 class Segment;
162
163 // Total size of all segments in [head_].
164 intptr_t small_segment_capacity_ = 0;
165
166 // The current head segment; may be NULL.
167 Segment* head_;
168
169 // List of large segments allocated in this zone; may be NULL.
170 Segment* large_segments_;
171
172 // Structure for managing handles allocation.
173 VMHandles handles_;
174
175 // Used for chaining zones in order to allow unwinding of stacks.
176 Zone* previous_;
177
178 friend class StackZone;
179 friend class ApiZone;
180 template <typename T, typename B, typename Allocator>
181 friend class BaseGrowableArray;
182 template <typename T, typename B, typename Allocator>
183 friend class BaseDirectChainedHashMap;
184 DISALLOW_COPY_AND_ASSIGN(Zone);
185};
186
187class StackZone : public StackResource {
188 public:
189 // Create an empty zone and set is at the current zone for the Thread.
190 explicit StackZone(ThreadState* thread);
191
192 // Delete all memory associated with the zone.
193 virtual ~StackZone();
194
195 // Compute the total size of this zone. This includes wasted space that is
196 // due to internal fragmentation in the segments.
197 uintptr_t SizeInBytes() const { return zone_->SizeInBytes(); }
198
199 // Computes the used space in the zone.
200 intptr_t CapacityInBytes() const { return zone_->CapacityInBytes(); }
201
202 Zone* GetZone() { return zone_; }
203
204 private:
205 Zone* zone_;
206
207 template <typename T>
208 friend class GrowableArray;
209 template <typename T>
210 friend class ZoneGrowableArray;
211
212 DISALLOW_IMPLICIT_CONSTRUCTORS(StackZone);
213};
214
215inline uword Zone::AllocUnsafe(intptr_t size) {
216 ASSERT(size >= 0);
217 // Round up the requested size to fit the alignment.
218 if (size > (kIntptrMax - kAlignment)) {
219 FATAL1("Zone::Alloc: 'size' is too large: size=%" Pd "", size);
220 }
221 size = Utils::RoundUp(size, kAlignment);
222
223 // Check if the requested size is available without expanding.
224 uword result;
225 intptr_t free_size = (limit_ - position_);
226 if (free_size >= size) {
227 result = position_;
228 position_ += size;
229 } else {
230 result = AllocateExpand(size);
231 }
232
233 // Check that the result has the proper alignment and return it.
234 ASSERT(Utils::IsAligned(result, kAlignment));
235 return result;
236}
237
238template <class ElementType>
239inline void Zone::CheckLength(intptr_t len) {
240 const intptr_t kElementSize = sizeof(ElementType);
241 if (len > (kIntptrMax / kElementSize)) {
242 FATAL2("Zone::Alloc: 'len' is too large: len=%" Pd ", kElementSize=%" Pd,
243 len, kElementSize);
244 }
245}
246
247template <class ElementType>
248inline ElementType* Zone::Alloc(intptr_t len) {
249 CheckLength<ElementType>(len);
250 return reinterpret_cast<ElementType*>(AllocUnsafe(len * sizeof(ElementType)));
251}
252
253template <class ElementType>
254inline ElementType* Zone::Realloc(ElementType* old_data,
255 intptr_t old_len,
256 intptr_t new_len) {
257 CheckLength<ElementType>(new_len);
258 const intptr_t kElementSize = sizeof(ElementType);
259 uword old_end = reinterpret_cast<uword>(old_data) + (old_len * kElementSize);
260 // Resize existing allocation if nothing was allocated in between...
261 if (Utils::RoundUp(old_end, kAlignment) == position_) {
262 uword new_end =
263 reinterpret_cast<uword>(old_data) + (new_len * kElementSize);
264 // ...and there is sufficient space.
265 if (new_end <= limit_) {
266 ASSERT(new_len >= old_len);
267 position_ = Utils::RoundUp(new_end, kAlignment);
268 return old_data;
269 }
270 }
271 if (new_len <= old_len) {
272 return old_data;
273 }
274 ElementType* new_data = Alloc<ElementType>(new_len);
275 if (old_data != 0) {
276 memmove(reinterpret_cast<void*>(new_data),
277 reinterpret_cast<void*>(old_data), old_len * kElementSize);
278 }
279 return new_data;
280}
281
282} // namespace dart
283
284#endif // RUNTIME_VM_ZONE_H_
285