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