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