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