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 24 namespace v8 { 25 namespace internal { 26 27 28 // Base class for all static visitors. 29 class 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 152 template <typename Callback> 153 class 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 204 template <typename StaticVisitor, typename BodyDescriptor, typename ReturnType> 205 class 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 227 template <typename StaticVisitor, typename BodyDescriptor, typename ReturnType> 228 class 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). 253 template <typename StaticVisitor> 254 class 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 334 template <typename StaticVisitor> 335 VisitorDispatchTable<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. 353 template <typename StaticVisitor> 354 class 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 445 template <typename StaticVisitor> 446 VisitorDispatchTable<typename StaticMarkingVisitor<StaticVisitor>::Callback> 447 StaticMarkingVisitor<StaticVisitor>::table_; 448 449 450 class 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. 458 template <class T> 459 Object* VisitWeakList(Heap* heap, Object* list, WeakObjectRetainer* retainer); 460 } // namespace internal 461 } // namespace v8 462 463 #endif // V8_OBJECTS_VISITING_H_ 464
