Home | History | Annotate | Download | only in src 
      1 // Copyright 2011 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   enum VisitorId {
     50     kVisitSeqAsciiString = 0,
     51     kVisitSeqTwoByteString,
     52     kVisitShortcutCandidate,
     53     kVisitByteArray,
     54     kVisitFreeSpace,
     55     kVisitFixedArray,
     56     kVisitFixedDoubleArray,
     57     kVisitGlobalContext,
     58 
     59     // For data objects, JS objects and structs along with generic visitor which
     60     // can visit object of any size we provide visitors specialized by
     61     // object size in words.
     62     // Ids of specialized visitors are declared in a linear order (without
     63     // holes) starting from the id of visitor specialized for 2 words objects
     64     // (base visitor id) and ending with the id of generic visitor.
     65     // Method GetVisitorIdForSize depends on this ordering to calculate visitor
     66     // id of specialized visitor from given instance size, base visitor id and
     67     // generic visitor's id.
     68 
     69     kVisitDataObject,
     70     kVisitDataObject2 = kVisitDataObject,
     71     kVisitDataObject3,
     72     kVisitDataObject4,
     73     kVisitDataObject5,
     74     kVisitDataObject6,
     75     kVisitDataObject7,
     76     kVisitDataObject8,
     77     kVisitDataObject9,
     78     kVisitDataObjectGeneric,
     79 
     80     kVisitJSObject,
     81     kVisitJSObject2 = kVisitJSObject,
     82     kVisitJSObject3,
     83     kVisitJSObject4,
     84     kVisitJSObject5,
     85     kVisitJSObject6,
     86     kVisitJSObject7,
     87     kVisitJSObject8,
     88     kVisitJSObject9,
     89     kVisitJSObjectGeneric,
     90 
     91     kVisitStruct,
     92     kVisitStruct2 = kVisitStruct,
     93     kVisitStruct3,
     94     kVisitStruct4,
     95     kVisitStruct5,
     96     kVisitStruct6,
     97     kVisitStruct7,
     98     kVisitStruct8,
     99     kVisitStruct9,
    100     kVisitStructGeneric,
    101 
    102     kVisitConsString,
    103     kVisitSlicedString,
    104     kVisitOddball,
    105     kVisitCode,
    106     kVisitMap,
    107     kVisitPropertyCell,
    108     kVisitSharedFunctionInfo,
    109     kVisitJSFunction,
    110     kVisitJSWeakMap,
    111     kVisitJSRegExp,
    112 
    113     kVisitorIdCount,
    114     kMinObjectSizeInWords = 2
    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 
    124   static VisitorId GetVisitorId(Map* map) {
    125     return GetVisitorId(map->instance_type(), map->instance_size());
    126   }
    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,
    131                                        VisitorId generic,
    132                                        int object_size) {
    133     ASSERT((base == kVisitDataObject) ||
    134            (base == kVisitStruct) ||
    135            (base == kVisitJSObject));
    136     ASSERT(IsAligned(object_size, kPointerSize));
    137     ASSERT(kMinObjectSizeInWords * kPointerSize <= object_size);
    138     ASSERT(object_size < Page::kMaxNonCodeHeapObjectSize);
    139 
    140     const VisitorId specialization = static_cast<VisitorId>(
    141         base + (object_size >> kPointerSizeLog2) - kMinObjectSizeInWords);
    142 
    143     return Min(specialization, generic);
    144   }
    145 };
    146 
    147 
    148 template<typename Callback>
    149 class VisitorDispatchTable {
    150  public:
    151   void CopyFrom(VisitorDispatchTable* other) {
    152     // We are not using memcpy to guarantee that during update
    153     // every element of callbacks_ array will remain correct
    154     // pointer (memcpy might be implemented as a byte copying loop).
    155     for (int i = 0; i < StaticVisitorBase::kVisitorIdCount; i++) {
    156       NoBarrier_Store(&callbacks_[i], other->callbacks_[i]);
    157     }
    158   }
    159 
    160   inline Callback GetVisitorById(StaticVisitorBase::VisitorId id) {
    161     return reinterpret_cast<Callback>(callbacks_[id]);
    162   }
    163 
    164   inline Callback GetVisitor(Map* map) {
    165     return reinterpret_cast<Callback>(callbacks_[map->visitor_id()]);
    166   }
    167 
    168   void Register(StaticVisitorBase::VisitorId id, Callback callback) {
    169     ASSERT(id < StaticVisitorBase::kVisitorIdCount);  // id is unsigned.
    170     callbacks_[id] = reinterpret_cast<AtomicWord>(callback);
    171   }
    172 
    173   template<typename Visitor,
    174            StaticVisitorBase::VisitorId base,
    175            StaticVisitorBase::VisitorId generic,
    176            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),
    180              &Visitor::template VisitSpecialized<size>);
    181   }
    182 
    183 
    184   template<typename Visitor,
    185            StaticVisitorBase::VisitorId base,
    186            StaticVisitorBase::VisitorId generic>
    187   void RegisterSpecializations() {
    188     STATIC_ASSERT(
    189         (generic - base + StaticVisitorBase::kMinObjectSizeInWords) == 10);
    190     RegisterSpecialization<Visitor, base, generic, 2>();
    191     RegisterSpecialization<Visitor, base, generic, 3>();
    192     RegisterSpecialization<Visitor, base, generic, 4>();
    193     RegisterSpecialization<Visitor, base, generic, 5>();
    194     RegisterSpecialization<Visitor, base, generic, 6>();
    195     RegisterSpecialization<Visitor, base, generic, 7>();
    196     RegisterSpecialization<Visitor, base, generic, 8>();
    197     RegisterSpecialization<Visitor, base, generic, 9>();
    198     Register(generic, &Visitor::Visit);
    199   }
    200 
    201  private:
    202   AtomicWord callbacks_[StaticVisitorBase::kVisitorIdCount];
    203 };
    204 
    205 
    206 template<typename StaticVisitor>
    207 class BodyVisitorBase : public AllStatic {
    208  public:
    209   INLINE(static void IteratePointers(Heap* heap,
    210                                      HeapObject* object,
    211                                      int start_offset,
    212                                      int end_offset)) {
    213     Object** start_slot = reinterpret_cast<Object**>(object->address() +
    214                                                      start_offset);
    215     Object** end_slot = reinterpret_cast<Object**>(object->address() +
    216                                                    end_offset);
    217     StaticVisitor::VisitPointers(heap, start_slot, end_slot);
    218   }
    219 };
    220 
    221 
    222 template<typename StaticVisitor, typename BodyDescriptor, typename ReturnType>
    223 class FlexibleBodyVisitor : public BodyVisitorBase<StaticVisitor> {
    224  public:
    225   static inline ReturnType Visit(Map* map, HeapObject* object) {
    226     int object_size = BodyDescriptor::SizeOf(map, object);
    227     BodyVisitorBase<StaticVisitor>::IteratePointers(
    228         map->GetHeap(),
    229         object,
    230         BodyDescriptor::kStartOffset,
    231         object_size);
    232     return static_cast<ReturnType>(object_size);
    233   }
    234 
    235   template<int object_size>
    236   static inline ReturnType VisitSpecialized(Map* map, HeapObject* object) {
    237     ASSERT(BodyDescriptor::SizeOf(map, object) == object_size);
    238     BodyVisitorBase<StaticVisitor>::IteratePointers(
    239         map->GetHeap(),
    240         object,
    241         BodyDescriptor::kStartOffset,
    242         object_size);
    243     return static_cast<ReturnType>(object_size);
    244   }
    245 };
    246 
    247 
    248 template<typename StaticVisitor, typename BodyDescriptor, typename ReturnType>
    249 class FixedBodyVisitor : public BodyVisitorBase<StaticVisitor> {
    250  public:
    251   static inline ReturnType Visit(Map* map, HeapObject* object) {
    252     BodyVisitorBase<StaticVisitor>::IteratePointers(
    253         map->GetHeap(),
    254         object,
    255         BodyDescriptor::kStartOffset,
    256         BodyDescriptor::kEndOffset);
    257     return static_cast<ReturnType>(BodyDescriptor::kSize);
    258   }
    259 };
    260 
    261 
    262 // Base class for visitors used for a linear new space iteration.
    263 // IterateBody returns size of visited object.
    264 // Certain types of objects (i.e. Code objects) are not handled
    265 // by dispatch table of this visitor because they cannot appear
    266 // in the new space.
    267 //
    268 // This class is intended to be used in the following way:
    269 //
    270 //   class SomeVisitor : public StaticNewSpaceVisitor<SomeVisitor> {
    271 //     ...
    272 //   }
    273 //
    274 // This is an example of Curiously recurring template pattern
    275 // (see http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern).
    276 // We use CRTP to guarantee aggressive compile time optimizations (i.e.
    277 // inlining and specialization of StaticVisitor::VisitPointers methods).
    278 template<typename StaticVisitor>
    279 class StaticNewSpaceVisitor : public StaticVisitorBase {
    280  public:
    281   static void Initialize();
    282 
    283   static inline int IterateBody(Map* map, HeapObject* obj) {
    284     return table_.GetVisitor(map)(map, obj);
    285   }
    286 
    287   static inline void VisitPointers(Heap* heap, Object** start, Object** end) {
    288     for (Object** p = start; p < end; p++) StaticVisitor::VisitPointer(heap, p);
    289   }
    290 
    291  private:
    292   static inline int VisitByteArray(Map* map, HeapObject* object) {
    293     return reinterpret_cast<ByteArray*>(object)->ByteArraySize();
    294   }
    295 
    296   static inline int VisitFixedDoubleArray(Map* map, HeapObject* object) {
    297     int length = reinterpret_cast<FixedDoubleArray*>(object)->length();
    298     return FixedDoubleArray::SizeFor(length);
    299   }
    300 
    301   static inline int VisitJSObject(Map* map, HeapObject* object) {
    302     return JSObjectVisitor::Visit(map, object);
    303   }
    304 
    305   static inline int VisitSeqAsciiString(Map* map, HeapObject* object) {
    306     return SeqAsciiString::cast(object)->
    307         SeqAsciiStringSize(map->instance_type());
    308   }
    309 
    310   static inline int VisitSeqTwoByteString(Map* map, HeapObject* object) {
    311     return SeqTwoByteString::cast(object)->
    312         SeqTwoByteStringSize(map->instance_type());
    313   }
    314 
    315   static inline int VisitFreeSpace(Map* map, HeapObject* object) {
    316     return FreeSpace::cast(object)->Size();
    317   }
    318 
    319   class DataObjectVisitor {
    320    public:
    321     template<int object_size>
    322     static inline int VisitSpecialized(Map* map, HeapObject* object) {
    323       return object_size;
    324     }
    325 
    326     static inline int Visit(Map* map, HeapObject* object) {
    327       return map->instance_size();
    328     }
    329   };
    330 
    331   typedef FlexibleBodyVisitor<StaticVisitor,
    332                               StructBodyDescriptor,
    333                               int> StructVisitor;
    334 
    335   typedef FlexibleBodyVisitor<StaticVisitor,
    336                               JSObject::BodyDescriptor,
    337                               int> JSObjectVisitor;
    338 
    339   typedef int (*Callback)(Map* map, HeapObject* object);
    340 
    341   static VisitorDispatchTable<Callback> table_;
    342 };
    343 
    344 
    345 template<typename StaticVisitor>
    346 VisitorDispatchTable<typename StaticNewSpaceVisitor<StaticVisitor>::Callback>
    347   StaticNewSpaceVisitor<StaticVisitor>::table_;
    348 
    349 
    350 } }  // namespace v8::internal
    351 
    352 #endif  // V8_OBJECTS_VISITING_H_
    353