1// Copyright 2011 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6//     * Redistributions of source code must retain the above copyright
7//       notice, this list of conditions and the following disclaimer.
8//     * Redistributions in binary form must reproduce the above
9//       copyright notice, this list of conditions and the following
10//       disclaimer in the documentation and/or other materials provided
11//       with the distribution.
12//     * Neither the name of Google Inc. nor the names of its
13//       contributors may be used to endorse or promote products derived
14//       from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28#ifndef V8_OBJECTS_VISITING_H_
29#define V8_OBJECTS_VISITING_H_
30
31#include "allocation.h"
32
33// This file provides base classes and auxiliary methods for defining
34// static object visitors used during GC.
35// Visiting HeapObject body with a normal ObjectVisitor requires performing
36// two switches on object's instance type to determine object size and layout
37// and one or more virtual method calls on visitor itself.
38// Static visitor is different: it provides a dispatch table which contains
39// pointers to specialized visit functions. Each map has the visitor_id
40// field which contains an index of specialized visitor to use.
41
42namespace v8 {
43namespace internal {
44
45
46// Base class for all static visitors.
47class StaticVisitorBase : public AllStatic {
48 public:
49  enum VisitorId {
50    kVisitSeqAsciiString = 0,
51    kVisitSeqTwoByteString,
52    kVisitShortcutCandidate,
53    kVisitByteArray,
54    kVisitFreeSpace,
55    kVisitFixedArray,
56    kVisitFixedDoubleArray,
57    kVisitGlobalContext,
58
59    // For data objects, JS objects and structs along with generic visitor which
60    // can visit object of any size we provide visitors specialized by
61    // object size in words.
62    // Ids of specialized visitors are declared in a linear order (without
63    // holes) starting from the id of visitor specialized for 2 words objects
64    // (base visitor id) and ending with the id of generic visitor.
65    // Method GetVisitorIdForSize depends on this ordering to calculate visitor
66    // id of specialized visitor from given instance size, base visitor id and
67    // generic visitor's id.
68
69    kVisitDataObject,
70    kVisitDataObject2 = kVisitDataObject,
71    kVisitDataObject3,
72    kVisitDataObject4,
73    kVisitDataObject5,
74    kVisitDataObject6,
75    kVisitDataObject7,
76    kVisitDataObject8,
77    kVisitDataObject9,
78    kVisitDataObjectGeneric,
79
80    kVisitJSObject,
81    kVisitJSObject2 = kVisitJSObject,
82    kVisitJSObject3,
83    kVisitJSObject4,
84    kVisitJSObject5,
85    kVisitJSObject6,
86    kVisitJSObject7,
87    kVisitJSObject8,
88    kVisitJSObject9,
89    kVisitJSObjectGeneric,
90
91    kVisitStruct,
92    kVisitStruct2 = kVisitStruct,
93    kVisitStruct3,
94    kVisitStruct4,
95    kVisitStruct5,
96    kVisitStruct6,
97    kVisitStruct7,
98    kVisitStruct8,
99    kVisitStruct9,
100    kVisitStructGeneric,
101
102    kVisitConsString,
103    kVisitSlicedString,
104    kVisitOddball,
105    kVisitCode,
106    kVisitMap,
107    kVisitPropertyCell,
108    kVisitSharedFunctionInfo,
109    kVisitJSFunction,
110    kVisitJSWeakMap,
111    kVisitJSRegExp,
112
113    kVisitorIdCount,
114    kMinObjectSizeInWords = 2
115  };
116
117  // Visitor ID should fit in one byte.
118  STATIC_ASSERT(kVisitorIdCount <= 256);
119
120  // Determine which specialized visitor should be used for given instance type
121  // and instance type.
122  static VisitorId GetVisitorId(int instance_type, int instance_size);
123
124  static VisitorId GetVisitorId(Map* map) {
125    return GetVisitorId(map->instance_type(), map->instance_size());
126  }
127
128  // For visitors that allow specialization by size calculate VisitorId based
129  // on size, base visitor id and generic visitor id.
130  static VisitorId GetVisitorIdForSize(VisitorId base,
131                                       VisitorId generic,
132                                       int object_size) {
133    ASSERT((base == kVisitDataObject) ||
134           (base == kVisitStruct) ||
135           (base == kVisitJSObject));
136    ASSERT(IsAligned(object_size, kPointerSize));
137    ASSERT(kMinObjectSizeInWords * kPointerSize <= object_size);
138    ASSERT(object_size < Page::kMaxNonCodeHeapObjectSize);
139
140    const VisitorId specialization = static_cast<VisitorId>(
141        base + (object_size >> kPointerSizeLog2) - kMinObjectSizeInWords);
142
143    return Min(specialization, generic);
144  }
145};
146
147
148template<typename Callback>
149class VisitorDispatchTable {
150 public:
151  void CopyFrom(VisitorDispatchTable* other) {
152    // We are not using memcpy to guarantee that during update
153    // every element of callbacks_ array will remain correct
154    // pointer (memcpy might be implemented as a byte copying loop).
155    for (int i = 0; i < StaticVisitorBase::kVisitorIdCount; i++) {
156      NoBarrier_Store(&callbacks_[i], other->callbacks_[i]);
157    }
158  }
159
160  inline Callback GetVisitorById(StaticVisitorBase::VisitorId id) {
161    return reinterpret_cast<Callback>(callbacks_[id]);
162  }
163
164  inline Callback GetVisitor(Map* map) {
165    return reinterpret_cast<Callback>(callbacks_[map->visitor_id()]);
166  }
167
168  void Register(StaticVisitorBase::VisitorId id, Callback callback) {
169    ASSERT(id < StaticVisitorBase::kVisitorIdCount);  // id is unsigned.
170    callbacks_[id] = reinterpret_cast<AtomicWord>(callback);
171  }
172
173  template<typename Visitor,
174           StaticVisitorBase::VisitorId base,
175           StaticVisitorBase::VisitorId generic,
176           int object_size_in_words>
177  void RegisterSpecialization() {
178    static const int size = object_size_in_words * kPointerSize;
179    Register(StaticVisitorBase::GetVisitorIdForSize(base, generic, size),
180             &Visitor::template VisitSpecialized<size>);
181  }
182
183
184  template<typename Visitor,
185           StaticVisitorBase::VisitorId base,
186           StaticVisitorBase::VisitorId generic>
187  void RegisterSpecializations() {
188    STATIC_ASSERT(
189        (generic - base + StaticVisitorBase::kMinObjectSizeInWords) == 10);
190    RegisterSpecialization<Visitor, base, generic, 2>();
191    RegisterSpecialization<Visitor, base, generic, 3>();
192    RegisterSpecialization<Visitor, base, generic, 4>();
193    RegisterSpecialization<Visitor, base, generic, 5>();
194    RegisterSpecialization<Visitor, base, generic, 6>();
195    RegisterSpecialization<Visitor, base, generic, 7>();
196    RegisterSpecialization<Visitor, base, generic, 8>();
197    RegisterSpecialization<Visitor, base, generic, 9>();
198    Register(generic, &Visitor::Visit);
199  }
200
201 private:
202  AtomicWord callbacks_[StaticVisitorBase::kVisitorIdCount];
203};
204
205
206template<typename StaticVisitor>
207class BodyVisitorBase : public AllStatic {
208 public:
209  INLINE(static void IteratePointers(Heap* heap,
210                                     HeapObject* object,
211                                     int start_offset,
212                                     int end_offset)) {
213    Object** start_slot = reinterpret_cast<Object**>(object->address() +
214                                                     start_offset);
215    Object** end_slot = reinterpret_cast<Object**>(object->address() +
216                                                   end_offset);
217    StaticVisitor::VisitPointers(heap, start_slot, end_slot);
218  }
219};
220
221
222template<typename StaticVisitor, typename BodyDescriptor, typename ReturnType>
223class FlexibleBodyVisitor : public BodyVisitorBase<StaticVisitor> {
224 public:
225  static inline ReturnType Visit(Map* map, HeapObject* object) {
226    int object_size = BodyDescriptor::SizeOf(map, object);
227    BodyVisitorBase<StaticVisitor>::IteratePointers(
228        map->GetHeap(),
229        object,
230        BodyDescriptor::kStartOffset,
231        object_size);
232    return static_cast<ReturnType>(object_size);
233  }
234
235  template<int object_size>
236  static inline ReturnType VisitSpecialized(Map* map, HeapObject* object) {
237    ASSERT(BodyDescriptor::SizeOf(map, object) == object_size);
238    BodyVisitorBase<StaticVisitor>::IteratePointers(
239        map->GetHeap(),
240        object,
241        BodyDescriptor::kStartOffset,
242        object_size);
243    return static_cast<ReturnType>(object_size);
244  }
245};
246
247
248template<typename StaticVisitor, typename BodyDescriptor, typename ReturnType>
249class FixedBodyVisitor : public BodyVisitorBase<StaticVisitor> {
250 public:
251  static inline ReturnType Visit(Map* map, HeapObject* object) {
252    BodyVisitorBase<StaticVisitor>::IteratePointers(
253        map->GetHeap(),
254        object,
255        BodyDescriptor::kStartOffset,
256        BodyDescriptor::kEndOffset);
257    return static_cast<ReturnType>(BodyDescriptor::kSize);
258  }
259};
260
261
262// Base class for visitors used for a linear new space iteration.
263// IterateBody returns size of visited object.
264// Certain types of objects (i.e. Code objects) are not handled
265// by dispatch table of this visitor because they cannot appear
266// in the new space.
267//
268// This class is intended to be used in the following way:
269//
270//   class SomeVisitor : public StaticNewSpaceVisitor<SomeVisitor> {
271//     ...
272//   }
273//
274// This is an example of Curiously recurring template pattern
275// (see http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern).
276// We use CRTP to guarantee aggressive compile time optimizations (i.e.
277// inlining and specialization of StaticVisitor::VisitPointers methods).
278template<typename StaticVisitor>
279class StaticNewSpaceVisitor : public StaticVisitorBase {
280 public:
281  static void Initialize();
282
283  static inline int IterateBody(Map* map, HeapObject* obj) {
284    return table_.GetVisitor(map)(map, obj);
285  }
286
287  static inline void VisitPointers(Heap* heap, Object** start, Object** end) {
288    for (Object** p = start; p < end; p++) StaticVisitor::VisitPointer(heap, p);
289  }
290
291 private:
292  static inline int VisitByteArray(Map* map, HeapObject* object) {
293    return reinterpret_cast<ByteArray*>(object)->ByteArraySize();
294  }
295
296  static inline int VisitFixedDoubleArray(Map* map, HeapObject* object) {
297    int length = reinterpret_cast<FixedDoubleArray*>(object)->length();
298    return FixedDoubleArray::SizeFor(length);
299  }
300
301  static inline int VisitJSObject(Map* map, HeapObject* object) {
302    return JSObjectVisitor::Visit(map, object);
303  }
304
305  static inline int VisitSeqAsciiString(Map* map, HeapObject* object) {
306    return SeqAsciiString::cast(object)->
307        SeqAsciiStringSize(map->instance_type());
308  }
309
310  static inline int VisitSeqTwoByteString(Map* map, HeapObject* object) {
311    return SeqTwoByteString::cast(object)->
312        SeqTwoByteStringSize(map->instance_type());
313  }
314
315  static inline int VisitFreeSpace(Map* map, HeapObject* object) {
316    return FreeSpace::cast(object)->Size();
317  }
318
319  class DataObjectVisitor {
320   public:
321    template<int object_size>
322    static inline int VisitSpecialized(Map* map, HeapObject* object) {
323      return object_size;
324    }
325
326    static inline int Visit(Map* map, HeapObject* object) {
327      return map->instance_size();
328    }
329  };
330
331  typedef FlexibleBodyVisitor<StaticVisitor,
332                              StructBodyDescriptor,
333                              int> StructVisitor;
334
335  typedef FlexibleBodyVisitor<StaticVisitor,
336                              JSObject::BodyDescriptor,
337                              int> JSObjectVisitor;
338
339  typedef int (*Callback)(Map* map, HeapObject* object);
340
341  static VisitorDispatchTable<Callback> table_;
342};
343
344
345template<typename StaticVisitor>
346VisitorDispatchTable<typename StaticNewSpaceVisitor<StaticVisitor>::Callback>
347  StaticNewSpaceVisitor<StaticVisitor>::table_;
348
349
350} }  // namespace v8::internal
351
352#endif  // V8_OBJECTS_VISITING_H_
353