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_OBJECTS_VISITING_H_
6#define V8_OBJECTS_VISITING_H_
7
8#include "src/allocation.h"
9#include "src/heap/embedder-tracing.h"
10#include "src/heap/heap.h"
11#include "src/heap/spaces.h"
12#include "src/layout-descriptor.h"
13#include "src/objects-body-descriptors.h"
14
15// This file provides base classes and auxiliary methods for defining
16// static object visitors used during GC.
17// Visiting HeapObject body with a normal ObjectVisitor requires performing
18// two switches on object's instance type to determine object size and layout
19// and one or more virtual method calls on visitor itself.
20// Static visitor is different: it provides a dispatch table which contains
21// pointers to specialized visit functions. Each map has the visitor_id
22// field which contains an index of specialized visitor to use.
23
24namespace v8 {
25namespace internal {
26
27
28// Base class for all static visitors.
29class StaticVisitorBase : public AllStatic {
30 public:
31#define VISITOR_ID_LIST(V) \
32  V(SeqOneByteString)      \
33  V(SeqTwoByteString)      \
34  V(ShortcutCandidate)     \
35  V(ByteArray)             \
36  V(BytecodeArray)         \
37  V(FreeSpace)             \
38  V(FixedArray)            \
39  V(FixedDoubleArray)      \
40  V(FixedTypedArray)       \
41  V(FixedFloat64Array)     \
42  V(NativeContext)         \
43  V(AllocationSite)        \
44  V(DataObject2)           \
45  V(DataObject3)           \
46  V(DataObject4)           \
47  V(DataObject5)           \
48  V(DataObject6)           \
49  V(DataObject7)           \
50  V(DataObject8)           \
51  V(DataObject9)           \
52  V(DataObjectGeneric)     \
53  V(JSObject2)             \
54  V(JSObject3)             \
55  V(JSObject4)             \
56  V(JSObject5)             \
57  V(JSObject6)             \
58  V(JSObject7)             \
59  V(JSObject8)             \
60  V(JSObject9)             \
61  V(JSObjectGeneric)       \
62  V(JSApiObject2)          \
63  V(JSApiObject3)          \
64  V(JSApiObject4)          \
65  V(JSApiObject5)          \
66  V(JSApiObject6)          \
67  V(JSApiObject7)          \
68  V(JSApiObject8)          \
69  V(JSApiObject9)          \
70  V(JSApiObjectGeneric)    \
71  V(Struct2)               \
72  V(Struct3)               \
73  V(Struct4)               \
74  V(Struct5)               \
75  V(Struct6)               \
76  V(Struct7)               \
77  V(Struct8)               \
78  V(Struct9)               \
79  V(StructGeneric)         \
80  V(ConsString)            \
81  V(SlicedString)          \
82  V(ThinString)            \
83  V(Symbol)                \
84  V(Oddball)               \
85  V(Code)                  \
86  V(Map)                   \
87  V(Cell)                  \
88  V(PropertyCell)          \
89  V(WeakCell)              \
90  V(TransitionArray)       \
91  V(SharedFunctionInfo)    \
92  V(JSFunction)            \
93  V(JSWeakCollection)      \
94  V(JSArrayBuffer)         \
95  V(JSRegExp)
96
97  // For data objects, JS objects and structs along with generic visitor which
98  // can visit object of any size we provide visitors specialized by
99  // object size in words.
100  // Ids of specialized visitors are declared in a linear order (without
101  // holes) starting from the id of visitor specialized for 2 words objects
102  // (base visitor id) and ending with the id of generic visitor.
103  // Method GetVisitorIdForSize depends on this ordering to calculate visitor
104  // id of specialized visitor from given instance size, base visitor id and
105  // generic visitor's id.
106  enum VisitorId {
107#define VISITOR_ID_ENUM_DECL(id) kVisit##id,
108    VISITOR_ID_LIST(VISITOR_ID_ENUM_DECL)
109#undef VISITOR_ID_ENUM_DECL
110        kVisitorIdCount,
111    kVisitDataObject = kVisitDataObject2,
112    kVisitJSObject = kVisitJSObject2,
113    kVisitJSApiObject = kVisitJSApiObject2,
114    kVisitStruct = kVisitStruct2,
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                                bool has_unboxed_fields);
124
125  // Determine which specialized visitor should be used for given map.
126  static VisitorId GetVisitorId(Map* map);
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, VisitorId generic,
131                                       int object_size,
132                                       bool has_unboxed_fields) {
133    DCHECK((base == kVisitDataObject) || (base == kVisitStruct) ||
134           (base == kVisitJSObject) || (base == kVisitJSApiObject));
135    DCHECK(IsAligned(object_size, kPointerSize));
136    DCHECK(Heap::kMinObjectSizeInWords * kPointerSize <= object_size);
137    DCHECK(object_size <= kMaxRegularHeapObjectSize);
138    DCHECK(!has_unboxed_fields || (base == kVisitJSObject) ||
139           (base == kVisitJSApiObject));
140
141    if (has_unboxed_fields) return generic;
142
143    int visitor_id = Min(
144        base + (object_size >> kPointerSizeLog2) - Heap::kMinObjectSizeInWords,
145        static_cast<int>(generic));
146
147    return static_cast<VisitorId>(visitor_id);
148  }
149};
150
151
152template <typename Callback>
153class VisitorDispatchTable {
154 public:
155  void CopyFrom(VisitorDispatchTable* other) {
156    // We are not using memcpy to guarantee that during update
157    // every element of callbacks_ array will remain correct
158    // pointer (memcpy might be implemented as a byte copying loop).
159    for (int i = 0; i < StaticVisitorBase::kVisitorIdCount; i++) {
160      base::NoBarrier_Store(&callbacks_[i], other->callbacks_[i]);
161    }
162  }
163
164  inline Callback GetVisitor(Map* map);
165
166  inline Callback GetVisitorById(StaticVisitorBase::VisitorId id) {
167    return reinterpret_cast<Callback>(callbacks_[id]);
168  }
169
170  void Register(StaticVisitorBase::VisitorId id, Callback callback) {
171    DCHECK(id < StaticVisitorBase::kVisitorIdCount);  // id is unsigned.
172    callbacks_[id] = reinterpret_cast<base::AtomicWord>(callback);
173  }
174
175  template <typename Visitor, StaticVisitorBase::VisitorId base,
176            StaticVisitorBase::VisitorId generic, 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, false),
180             &Visitor::template VisitSpecialized<size>);
181  }
182
183
184  template <typename Visitor, StaticVisitorBase::VisitorId base,
185            StaticVisitorBase::VisitorId generic>
186  void RegisterSpecializations() {
187    STATIC_ASSERT((generic - base + Heap::kMinObjectSizeInWords) == 10);
188    RegisterSpecialization<Visitor, base, generic, 2>();
189    RegisterSpecialization<Visitor, base, generic, 3>();
190    RegisterSpecialization<Visitor, base, generic, 4>();
191    RegisterSpecialization<Visitor, base, generic, 5>();
192    RegisterSpecialization<Visitor, base, generic, 6>();
193    RegisterSpecialization<Visitor, base, generic, 7>();
194    RegisterSpecialization<Visitor, base, generic, 8>();
195    RegisterSpecialization<Visitor, base, generic, 9>();
196    Register(generic, &Visitor::Visit);
197  }
198
199 private:
200  base::AtomicWord callbacks_[StaticVisitorBase::kVisitorIdCount];
201};
202
203
204template <typename StaticVisitor, typename BodyDescriptor, typename ReturnType>
205class FlexibleBodyVisitor : public AllStatic {
206 public:
207  INLINE(static ReturnType Visit(Map* map, HeapObject* object)) {
208    int object_size = BodyDescriptor::SizeOf(map, object);
209    BodyDescriptor::template IterateBody<StaticVisitor>(object, object_size);
210    return static_cast<ReturnType>(object_size);
211  }
212
213  // This specialization is only suitable for objects containing pointer fields.
214  template <int object_size>
215  static inline ReturnType VisitSpecialized(Map* map, HeapObject* object) {
216    DCHECK(BodyDescriptor::SizeOf(map, object) == object_size);
217    DCHECK(!FLAG_unbox_double_fields || map->HasFastPointerLayout());
218    StaticVisitor::VisitPointers(
219        object->GetHeap(), object,
220        HeapObject::RawField(object, BodyDescriptor::kStartOffset),
221        HeapObject::RawField(object, object_size));
222    return static_cast<ReturnType>(object_size);
223  }
224};
225
226
227template <typename StaticVisitor, typename BodyDescriptor, typename ReturnType>
228class FixedBodyVisitor : public AllStatic {
229 public:
230  INLINE(static ReturnType Visit(Map* map, HeapObject* object)) {
231    BodyDescriptor::template IterateBody<StaticVisitor>(object);
232    return static_cast<ReturnType>(BodyDescriptor::kSize);
233  }
234};
235
236
237// Base class for visitors used for a linear new space iteration.
238// IterateBody returns size of visited object.
239// Certain types of objects (i.e. Code objects) are not handled
240// by dispatch table of this visitor because they cannot appear
241// in the new space.
242//
243// This class is intended to be used in the following way:
244//
245//   class SomeVisitor : public StaticNewSpaceVisitor<SomeVisitor> {
246//     ...
247//   }
248//
249// This is an example of Curiously recurring template pattern
250// (see http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern).
251// We use CRTP to guarantee aggressive compile time optimizations (i.e.
252// inlining and specialization of StaticVisitor::VisitPointers methods).
253template <typename StaticVisitor>
254class StaticNewSpaceVisitor : public StaticVisitorBase {
255 public:
256  static void Initialize();
257
258  INLINE(static int IterateBody(Map* map, HeapObject* obj)) {
259    return table_.GetVisitor(map)(map, obj);
260  }
261
262  INLINE(static void VisitPointers(Heap* heap, HeapObject* object,
263                                   Object** start, Object** end)) {
264    for (Object** p = start; p < end; p++) {
265      StaticVisitor::VisitPointer(heap, object, p);
266    }
267  }
268
269  // Although we are using the JSFunction body descriptor which does not
270  // visit the code entry, compiler wants it to be accessible.
271  // See JSFunction::BodyDescriptorImpl.
272  inline static void VisitCodeEntry(Heap* heap, HeapObject* object,
273                                    Address entry_address) {
274    UNREACHABLE();
275  }
276
277 private:
278  inline static int UnreachableVisitor(Map* map, HeapObject* object) {
279    UNREACHABLE();
280    return 0;
281  }
282
283  INLINE(static int VisitByteArray(Map* map, HeapObject* object)) {
284    return reinterpret_cast<ByteArray*>(object)->ByteArraySize();
285  }
286
287  INLINE(static int VisitFixedDoubleArray(Map* map, HeapObject* object)) {
288    int length = reinterpret_cast<FixedDoubleArray*>(object)->length();
289    return FixedDoubleArray::SizeFor(length);
290  }
291
292  INLINE(static int VisitJSObject(Map* map, HeapObject* object)) {
293    return JSObjectVisitor::Visit(map, object);
294  }
295
296  INLINE(static int VisitSeqOneByteString(Map* map, HeapObject* object)) {
297    return SeqOneByteString::cast(object)
298        ->SeqOneByteStringSize(map->instance_type());
299  }
300
301  INLINE(static int VisitSeqTwoByteString(Map* map, HeapObject* object)) {
302    return SeqTwoByteString::cast(object)
303        ->SeqTwoByteStringSize(map->instance_type());
304  }
305
306  INLINE(static int VisitFreeSpace(Map* map, HeapObject* object)) {
307    return FreeSpace::cast(object)->size();
308  }
309
310  class DataObjectVisitor {
311   public:
312    template <int object_size>
313    static inline int VisitSpecialized(Map* map, HeapObject* object) {
314      return object_size;
315    }
316
317    INLINE(static int Visit(Map* map, HeapObject* object)) {
318      return map->instance_size();
319    }
320  };
321
322  typedef FlexibleBodyVisitor<StaticVisitor, StructBodyDescriptor, int>
323      StructVisitor;
324
325  typedef FlexibleBodyVisitor<StaticVisitor, JSObject::BodyDescriptor, int>
326      JSObjectVisitor;
327
328  typedef int (*Callback)(Map* map, HeapObject* object);
329
330  static VisitorDispatchTable<Callback> table_;
331};
332
333
334template <typename StaticVisitor>
335VisitorDispatchTable<typename StaticNewSpaceVisitor<StaticVisitor>::Callback>
336    StaticNewSpaceVisitor<StaticVisitor>::table_;
337
338
339// Base class for visitors used to transitively mark the entire heap.
340// IterateBody returns nothing.
341// Certain types of objects might not be handled by this base class and
342// no visitor function is registered by the generic initialization. A
343// specialized visitor function needs to be provided by the inheriting
344// class itself for those cases.
345//
346// This class is intended to be used in the following way:
347//
348//   class SomeVisitor : public StaticMarkingVisitor<SomeVisitor> {
349//     ...
350//   }
351//
352// This is an example of Curiously recurring template pattern.
353template <typename StaticVisitor>
354class StaticMarkingVisitor : public StaticVisitorBase {
355 public:
356  static void Initialize();
357
358  INLINE(static void IterateBody(Map* map, HeapObject* obj)) {
359    table_.GetVisitor(map)(map, obj);
360  }
361
362  INLINE(static void VisitWeakCell(Map* map, HeapObject* object));
363  INLINE(static void VisitTransitionArray(Map* map, HeapObject* object));
364  INLINE(static void VisitCodeEntry(Heap* heap, HeapObject* object,
365                                    Address entry_address));
366  INLINE(static void VisitEmbeddedPointer(Heap* heap, RelocInfo* rinfo));
367  INLINE(static void VisitCell(Heap* heap, RelocInfo* rinfo));
368  INLINE(static void VisitDebugTarget(Heap* heap, RelocInfo* rinfo));
369  INLINE(static void VisitCodeTarget(Heap* heap, RelocInfo* rinfo));
370  INLINE(static void VisitCodeAgeSequence(Heap* heap, RelocInfo* rinfo));
371  INLINE(static void VisitExternalReference(RelocInfo* rinfo)) {}
372  INLINE(static void VisitInternalReference(RelocInfo* rinfo)) {}
373  INLINE(static void VisitRuntimeEntry(RelocInfo* rinfo)) {}
374  // Skip the weak next code link in a code object.
375  INLINE(static void VisitNextCodeLink(Heap* heap, Object** slot)) {}
376
377 protected:
378  INLINE(static void VisitMap(Map* map, HeapObject* object));
379  INLINE(static void VisitCode(Map* map, HeapObject* object));
380  INLINE(static void VisitBytecodeArray(Map* map, HeapObject* object));
381  INLINE(static void VisitSharedFunctionInfo(Map* map, HeapObject* object));
382  INLINE(static void VisitWeakCollection(Map* map, HeapObject* object));
383  INLINE(static void VisitJSFunction(Map* map, HeapObject* object));
384  INLINE(static void VisitNativeContext(Map* map, HeapObject* object));
385
386  // Mark pointers in a Map treating some elements of the descriptor array weak.
387  static void MarkMapContents(Heap* heap, Map* map);
388
389  // Code flushing support.
390  INLINE(static bool IsFlushable(Heap* heap, JSFunction* function));
391  INLINE(static bool IsFlushable(Heap* heap, SharedFunctionInfo* shared_info));
392
393  // Helpers used by code flushing support that visit pointer fields and treat
394  // references to code objects either strongly or weakly.
395  static void VisitSharedFunctionInfoStrongCode(Map* map, HeapObject* object);
396  static void VisitSharedFunctionInfoWeakCode(Map* map, HeapObject* object);
397  static void VisitJSFunctionStrongCode(Map* map, HeapObject* object);
398  static void VisitJSFunctionWeakCode(Map* map, HeapObject* object);
399
400  class DataObjectVisitor {
401   public:
402    template <int size>
403    static inline void VisitSpecialized(Map* map, HeapObject* object) {}
404
405    INLINE(static void Visit(Map* map, HeapObject* object)) {}
406  };
407
408  typedef FlexibleBodyVisitor<StaticVisitor, FixedArray::BodyDescriptor, void>
409      FixedArrayVisitor;
410
411  typedef FlexibleBodyVisitor<StaticVisitor, JSObject::BodyDescriptor, void>
412      JSObjectVisitor;
413
414  class JSApiObjectVisitor : AllStatic {
415   public:
416    template <int size>
417    static inline void VisitSpecialized(Map* map, HeapObject* object) {
418      TracePossibleWrapper(object);
419      JSObjectVisitor::template VisitSpecialized<size>(map, object);
420    }
421
422    INLINE(static void Visit(Map* map, HeapObject* object)) {
423      TracePossibleWrapper(object);
424      JSObjectVisitor::Visit(map, object);
425    }
426
427   private:
428    INLINE(static void TracePossibleWrapper(HeapObject* object)) {
429      if (object->GetHeap()->local_embedder_heap_tracer()->InUse()) {
430        DCHECK(object->IsJSObject());
431        object->GetHeap()->TracePossibleWrapper(JSObject::cast(object));
432      }
433    }
434  };
435
436  typedef FlexibleBodyVisitor<StaticVisitor, StructBodyDescriptor, void>
437      StructObjectVisitor;
438
439  typedef void (*Callback)(Map* map, HeapObject* object);
440
441  static VisitorDispatchTable<Callback> table_;
442};
443
444
445template <typename StaticVisitor>
446VisitorDispatchTable<typename StaticMarkingVisitor<StaticVisitor>::Callback>
447    StaticMarkingVisitor<StaticVisitor>::table_;
448
449
450class WeakObjectRetainer;
451
452
453// A weak list is single linked list where each element has a weak pointer to
454// the next element. Given the head of the list, this function removes dead
455// elements from the list and if requested records slots for next-element
456// pointers. The template parameter T is a WeakListVisitor that defines how to
457// access the next-element pointers.
458template <class T>
459Object* VisitWeakList(Heap* heap, Object* list, WeakObjectRetainer* retainer);
460}  // namespace internal
461}  // namespace v8
462
463#endif  // V8_OBJECTS_VISITING_H_
464