src/v8/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
  10 // This file provides base classes and auxiliary methods for defining
  11 // static object visitors used during GC.
  12 // Visiting HeapObject body with a normal ObjectVisitor requires performing
  13 // two switches on object's instance type to determine object size and layout
  14 // and one or more virtual method calls on visitor itself.
  15 // Static visitor is different: it provides a dispatch table which contains
  16 // pointers to specialized visit functions. Each map has the visitor_id
  17 // field which contains an index of specialized visitor to use.
  18
  19 namespace v8 {
  20 namespace internal {
  21
  22
  23 // Base class for all static visitors.
  24 class StaticVisitorBase : public AllStatic {
  25  public:
  26 #define VISITOR_ID_LIST(V) \
  27   V(SeqOneByteString)      \
  28   V(SeqTwoByteString)      \
  29   V(ShortcutCandidate)     \
  30   V(ByteArray)             \
  31   V(FreeSpace)             \
  32   V(FixedArray)            \
  33   V(FixedDoubleArray)      \
  34   V(FixedTypedArray)       \
  35   V(FixedFloat64Array)     \
  36   V(ConstantPoolArray)     \
  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
 110   static VisitorId GetVisitorId(Map* map) {
 111     return GetVisitorId(map->instance_type(), map->instance_size());
 112   }
 113
 114   // For visitors that allow specialization by size calculate VisitorId based
 115   // on size, base visitor id and generic visitor id.
 116   static VisitorId GetVisitorIdForSize(VisitorId base, VisitorId generic,
 117                                        int object_size) {
 118     DCHECK((base == kVisitDataObject) || (base == kVisitStruct) ||
 119            (base == kVisitJSObject));
 120     DCHECK(IsAligned(object_size, kPointerSize));
 121     DCHECK(kMinObjectSizeInWords * kPointerSize <= object_size);
 122     DCHECK(object_size <= Page::kMaxRegularHeapObjectSize);
 123
 124     const VisitorId specialization = static_cast<VisitorId>(
 125         base + (object_size >> kPointerSizeLog2) - kMinObjectSizeInWords);
 126
 127     return Min(specialization, generic);
 128   }
 129 };
 130
 131
 132 template <typename Callback>
 133 class VisitorDispatchTable {
 134  public:
 135   void CopyFrom(VisitorDispatchTable* other) {
 136     // We are not using memcpy to guarantee that during update
 137     // every element of callbacks_ array will remain correct
 138     // pointer (memcpy might be implemented as a byte copying loop).
 139     for (int i = 0; i < StaticVisitorBase::kVisitorIdCount; i++) {
 140       base::NoBarrier_Store(&callbacks_[i], other->callbacks_[i]);
 141     }
 142   }
 143
 144   inline Callback GetVisitorById(StaticVisitorBase::VisitorId id) {
 145     return reinterpret_cast<Callback>(callbacks_[id]);
 146   }
 147
 148   inline Callback GetVisitor(Map* map) {
 149     return reinterpret_cast<Callback>(callbacks_[map->visitor_id()]);
 150   }
 151
 152   void Register(StaticVisitorBase::VisitorId id, Callback callback) {
 153     DCHECK(id < StaticVisitorBase::kVisitorIdCount);  // id is unsigned.
 154     callbacks_[id] = reinterpret_cast<base::AtomicWord>(callback);
 155   }
 156
 157   template <typename Visitor, StaticVisitorBase::VisitorId base,
 158             StaticVisitorBase::VisitorId generic, int object_size_in_words>
 159   void RegisterSpecialization() {
 160     static const int size = object_size_in_words * kPointerSize;
 161     Register(StaticVisitorBase::GetVisitorIdForSize(base, generic, size),
 162              &Visitor::template VisitSpecialized<size>);
 163   }
 164
 165
 166   template <typename Visitor, StaticVisitorBase::VisitorId base,
 167             StaticVisitorBase::VisitorId generic>
 168   void RegisterSpecializations() {
 169     STATIC_ASSERT((generic - base + StaticVisitorBase::kMinObjectSizeInWords) ==
 170                   10);
 171     RegisterSpecialization<Visitor, base, generic, 2>();
 172     RegisterSpecialization<Visitor, base, generic, 3>();
 173     RegisterSpecialization<Visitor, base, generic, 4>();
 174     RegisterSpecialization<Visitor, base, generic, 5>();
 175     RegisterSpecialization<Visitor, base, generic, 6>();
 176     RegisterSpecialization<Visitor, base, generic, 7>();
 177     RegisterSpecialization<Visitor, base, generic, 8>();
 178     RegisterSpecialization<Visitor, base, generic, 9>();
 179     Register(generic, &Visitor::Visit);
 180   }
 181
 182  private:
 183   base::AtomicWord callbacks_[StaticVisitorBase::kVisitorIdCount];
 184 };
 185
 186
 187 template <typename StaticVisitor>
 188 class BodyVisitorBase : public AllStatic {
 189  public:
 190   INLINE(static void IteratePointers(Heap* heap, HeapObject* object,
 191                                      int start_offset, int end_offset)) {
 192     Object** start_slot =
 193         reinterpret_cast<Object**>(object->address() + start_offset);
 194     Object** end_slot =
 195         reinterpret_cast<Object**>(object->address() + end_offset);
 196     StaticVisitor::VisitPointers(heap, start_slot, end_slot);
 197   }
 198 };
 199
 200
 201 template <typename StaticVisitor, typename BodyDescriptor, typename ReturnType>
 202 class FlexibleBodyVisitor : public BodyVisitorBase<StaticVisitor> {
 203  public:
 204   INLINE(static ReturnType Visit(Map* map, HeapObject* object)) {
 205     int object_size = BodyDescriptor::SizeOf(map, object);
 206     BodyVisitorBase<StaticVisitor>::IteratePointers(
 207         map->GetHeap(), object, BodyDescriptor::kStartOffset, object_size);
 208     return static_cast<ReturnType>(object_size);
 209   }
 210
 211   template <int object_size>
 212   static inline ReturnType VisitSpecialized(Map* map, HeapObject* object) {
 213     DCHECK(BodyDescriptor::SizeOf(map, object) == object_size);
 214     BodyVisitorBase<StaticVisitor>::IteratePointers(
 215         map->GetHeap(), object, BodyDescriptor::kStartOffset, object_size);
 216     return static_cast<ReturnType>(object_size);
 217   }
 218 };
 219
 220
 221 template <typename StaticVisitor, typename BodyDescriptor, typename ReturnType>
 222 class FixedBodyVisitor : public BodyVisitorBase<StaticVisitor> {
 223  public:
 224   INLINE(static ReturnType Visit(Map* map, HeapObject* object)) {
 225     BodyVisitorBase<StaticVisitor>::IteratePointers(
 226         map->GetHeap(), object, BodyDescriptor::kStartOffset,
 227         BodyDescriptor::kEndOffset);
 228     return static_cast<ReturnType>(BodyDescriptor::kSize);
 229   }
 230 };
 231
 232
 233 // Base class for visitors used for a linear new space iteration.
 234 // IterateBody returns size of visited object.
 235 // Certain types of objects (i.e. Code objects) are not handled
 236 // by dispatch table of this visitor because they cannot appear
 237 // in the new space.
 238 //
 239 // This class is intended to be used in the following way:
 240 //
 241 //   class SomeVisitor : public StaticNewSpaceVisitor<SomeVisitor> {
 242 //     ...
 243 //   }
 244 //
 245 // This is an example of Curiously recurring template pattern
 246 // (see http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern).
 247 // We use CRTP to guarantee aggressive compile time optimizations (i.e.
 248 // inlining and specialization of StaticVisitor::VisitPointers methods).
 249 template <typename StaticVisitor>
 250 class StaticNewSpaceVisitor : public StaticVisitorBase {
 251  public:
 252   static void Initialize();
 253
 254   INLINE(static int IterateBody(Map* map, HeapObject* obj)) {
 255     return table_.GetVisitor(map)(map, obj);
 256   }
 257
 258   INLINE(static void VisitPointers(Heap* heap, Object** start, Object** end)) {
 259     for (Object** p = start; p < end; p++) StaticVisitor::VisitPointer(heap, p);
 260   }
 261
 262  private:
 263   INLINE(static int VisitJSFunction(Map* map, HeapObject* object)) {
 264     Heap* heap = map->GetHeap();
 265     VisitPointers(heap,
 266                   HeapObject::RawField(object, JSFunction::kPropertiesOffset),
 267                   HeapObject::RawField(object, JSFunction::kCodeEntryOffset));
 268
 269     // Don't visit code entry. We are using this visitor only during scavenges.
 270
 271     VisitPointers(
 272         heap, HeapObject::RawField(object,
 273                                    JSFunction::kCodeEntryOffset + kPointerSize),
 274         HeapObject::RawField(object, JSFunction::kNonWeakFieldsEndOffset));
 275     return JSFunction::kSize;
 276   }
 277
 278   INLINE(static int VisitByteArray(Map* map, HeapObject* object)) {
 279     return reinterpret_cast<ByteArray*>(object)->ByteArraySize();
 280   }
 281
 282   INLINE(static int VisitFixedDoubleArray(Map* map, HeapObject* object)) {
 283     int length = reinterpret_cast<FixedDoubleArray*>(object)->length();
 284     return FixedDoubleArray::SizeFor(length);
 285   }
 286
 287   INLINE(static int VisitFixedTypedArray(Map* map, HeapObject* object)) {
 288     return reinterpret_cast<FixedTypedArrayBase*>(object)->size();
 289   }
 290
 291   INLINE(static int VisitJSObject(Map* map, HeapObject* object)) {
 292     return JSObjectVisitor::Visit(map, object);
 293   }
 294
 295   INLINE(static int VisitSeqOneByteString(Map* map, HeapObject* object)) {
 296     return SeqOneByteString::cast(object)
 297         ->SeqOneByteStringSize(map->instance_type());
 298   }
 299
 300   INLINE(static int VisitSeqTwoByteString(Map* map, HeapObject* object)) {
 301     return SeqTwoByteString::cast(object)
 302         ->SeqTwoByteStringSize(map->instance_type());
 303   }
 304
 305   INLINE(static int VisitFreeSpace(Map* map, HeapObject* object)) {
 306     return FreeSpace::cast(object)->Size();
 307   }
 308
 309   INLINE(static int VisitJSArrayBuffer(Map* map, HeapObject* object));
 310   INLINE(static int VisitJSTypedArray(Map* map, HeapObject* object));
 311   INLINE(static int VisitJSDataView(Map* map, HeapObject* object));
 312
 313   class DataObjectVisitor {
 314    public:
 315     template <int object_size>
 316     static inline int VisitSpecialized(Map* map, HeapObject* object) {
 317       return object_size;
 318     }
 319
 320     INLINE(static int Visit(Map* map, HeapObject* object)) {
 321       return map->instance_size();
 322     }
 323   };
 324
 325   typedef FlexibleBodyVisitor<StaticVisitor, StructBodyDescriptor, int>
 326       StructVisitor;
 327
 328   typedef FlexibleBodyVisitor<StaticVisitor, JSObject::BodyDescriptor, int>
 329       JSObjectVisitor;
 330
 331   typedef int (*Callback)(Map* map, HeapObject* object);
 332
 333   static VisitorDispatchTable<Callback> table_;
 334 };
 335
 336
 337 template <typename StaticVisitor>
 338 VisitorDispatchTable<typename StaticNewSpaceVisitor<StaticVisitor>::Callback>
 339     StaticNewSpaceVisitor<StaticVisitor>::table_;
 340
 341
 342 // Base class for visitors used to transitively mark the entire heap.
 343 // IterateBody returns nothing.
 344 // Certain types of objects might not be handled by this base class and
 345 // no visitor function is registered by the generic initialization. A
 346 // specialized visitor function needs to be provided by the inheriting
 347 // class itself for those cases.
 348 //
 349 // This class is intended to be used in the following way:
 350 //
 351 //   class SomeVisitor : public StaticMarkingVisitor<SomeVisitor> {
 352 //     ...
 353 //   }
 354 //
 355 // This is an example of Curiously recurring template pattern.
 356 template <typename StaticVisitor>
 357 class StaticMarkingVisitor : public StaticVisitorBase {
 358  public:
 359   static void Initialize();
 360
 361   INLINE(static void IterateBody(Map* map, HeapObject* obj)) {
 362     table_.GetVisitor(map)(map, obj);
 363   }
 364
 365   INLINE(static void VisitPropertyCell(Map* map, HeapObject* object));
 366   INLINE(static void VisitWeakCell(Map* map, HeapObject* object));
 367   INLINE(static void VisitCodeEntry(Heap* heap, Address entry_address));
 368   INLINE(static void VisitEmbeddedPointer(Heap* heap, RelocInfo* rinfo));
 369   INLINE(static void VisitCell(Heap* heap, RelocInfo* rinfo));
 370   INLINE(static void VisitDebugTarget(Heap* heap, RelocInfo* rinfo));
 371   INLINE(static void VisitCodeTarget(Heap* heap, RelocInfo* rinfo));
 372   INLINE(static void VisitCodeAgeSequence(Heap* heap, RelocInfo* rinfo));
 373   INLINE(static void VisitExternalReference(RelocInfo* rinfo)) {}
 374   INLINE(static void VisitRuntimeEntry(RelocInfo* rinfo)) {}
 375   // Skip the weak next code link in a code object.
 376   INLINE(static void VisitNextCodeLink(Heap* heap, Object** slot)) {}
 377
 378   // TODO(mstarzinger): This should be made protected once refactoring is done.
 379   // Mark non-optimize code for functions inlined into the given optimized
 380   // code. This will prevent it from being flushed.
 381   static void MarkInlinedFunctionsCode(Heap* heap, Code* code);
 382
 383  protected:
 384   INLINE(static void VisitMap(Map* map, HeapObject* object));
 385   INLINE(static void VisitCode(Map* map, HeapObject* object));
 386   INLINE(static void VisitSharedFunctionInfo(Map* map, HeapObject* object));
 387   INLINE(static void VisitConstantPoolArray(Map* map, HeapObject* object));
 388   INLINE(static void VisitAllocationSite(Map* map, HeapObject* object));
 389   INLINE(static void VisitWeakCollection(Map* map, HeapObject* object));
 390   INLINE(static void VisitJSFunction(Map* map, HeapObject* object));
 391   INLINE(static void VisitJSRegExp(Map* map, HeapObject* object));
 392   INLINE(static void VisitJSArrayBuffer(Map* map, HeapObject* object));
 393   INLINE(static void VisitJSTypedArray(Map* map, HeapObject* object));
 394   INLINE(static void VisitJSDataView(Map* map, HeapObject* object));
 395   INLINE(static void VisitNativeContext(Map* map, HeapObject* object));
 396
 397   // Mark pointers in a Map and its TransitionArray together, possibly
 398   // treating transitions or back pointers weak.
 399   static void MarkMapContents(Heap* heap, Map* map);
 400   static void MarkTransitionArray(Heap* heap, TransitionArray* transitions);
 401
 402   // Code flushing support.
 403   INLINE(static bool IsFlushable(Heap* heap, JSFunction* function));
 404   INLINE(static bool IsFlushable(Heap* heap, SharedFunctionInfo* shared_info));
 405
 406   // Helpers used by code flushing support that visit pointer fields and treat
 407   // references to code objects either strongly or weakly.
 408   static void VisitSharedFunctionInfoStrongCode(Heap* heap, HeapObject* object);
 409   static void VisitSharedFunctionInfoWeakCode(Heap* heap, HeapObject* object);
 410   static void VisitJSFunctionStrongCode(Heap* heap, HeapObject* object);
 411   static void VisitJSFunctionWeakCode(Heap* heap, HeapObject* object);
 412
 413   class DataObjectVisitor {
 414    public:
 415     template <int size>
 416     static inline void VisitSpecialized(Map* map, HeapObject* object) {}
 417
 418     INLINE(static void Visit(Map* map, HeapObject* object)) {}
 419   };
 420
 421   typedef FlexibleBodyVisitor<StaticVisitor, FixedArray::BodyDescriptor, void>
 422       FixedArrayVisitor;
 423
 424   typedef FlexibleBodyVisitor<StaticVisitor, JSObject::BodyDescriptor, void>
 425       JSObjectVisitor;
 426
 427   typedef FlexibleBodyVisitor<StaticVisitor, StructBodyDescriptor, void>
 428       StructObjectVisitor;
 429
 430   typedef void (*Callback)(Map* map, HeapObject* object);
 431
 432   static VisitorDispatchTable<Callback> table_;
 433 };
 434
 435
 436 template <typename StaticVisitor>
 437 VisitorDispatchTable<typename StaticMarkingVisitor<StaticVisitor>::Callback>
 438     StaticMarkingVisitor<StaticVisitor>::table_;
 439
 440
 441 class WeakObjectRetainer;
 442
 443
 444 // A weak list is single linked list where each element has a weak pointer to
 445 // the next element. Given the head of the list, this function removes dead
 446 // elements from the list and if requested records slots for next-element
 447 // pointers. The template parameter T is a WeakListVisitor that defines how to
 448 // access the next-element pointers.
 449 template <class T>
 450 Object* VisitWeakList(Heap* heap, Object* list, WeakObjectRetainer* retainer);
 451 }
 452 }  // namespace v8::internal
 453
 454 #endif  // V8_OBJECTS_VISITING_H_