• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
GetVisitorId(Map * map)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.
GetVisitorIdForSize(VisitorId base,VisitorId generic,int object_size)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:
CopyFrom(VisitorDispatchTable * other)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 
GetVisitorById(StaticVisitorBase::VisitorId id)160   inline Callback GetVisitorById(StaticVisitorBase::VisitorId id) {
161     return reinterpret_cast<Callback>(callbacks_[id]);
162   }
163 
GetVisitor(Map * map)164   inline Callback GetVisitor(Map* map) {
165     return reinterpret_cast<Callback>(callbacks_[map->visitor_id()]);
166   }
167 
Register(StaticVisitorBase::VisitorId id,Callback callback)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>
RegisterSpecialization()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>
RegisterSpecializations()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:
INLINE(static void IteratePointers (Heap * heap,HeapObject * object,int start_offset,int end_offset))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:
Visit(Map * map,HeapObject * object)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>
VisitSpecialized(Map * map,HeapObject * object)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:
Visit(Map * map,HeapObject * object)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 
IterateBody(Map * map,HeapObject * obj)283   static inline int IterateBody(Map* map, HeapObject* obj) {
284     return table_.GetVisitor(map)(map, obj);
285   }
286 
VisitPointers(Heap * heap,Object ** start,Object ** end)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:
VisitByteArray(Map * map,HeapObject * object)292   static inline int VisitByteArray(Map* map, HeapObject* object) {
293     return reinterpret_cast<ByteArray*>(object)->ByteArraySize();
294   }
295 
VisitFixedDoubleArray(Map * map,HeapObject * object)296   static inline int VisitFixedDoubleArray(Map* map, HeapObject* object) {
297     int length = reinterpret_cast<FixedDoubleArray*>(object)->length();
298     return FixedDoubleArray::SizeFor(length);
299   }
300 
VisitJSObject(Map * map,HeapObject * object)301   static inline int VisitJSObject(Map* map, HeapObject* object) {
302     return JSObjectVisitor::Visit(map, object);
303   }
304 
VisitSeqAsciiString(Map * map,HeapObject * object)305   static inline int VisitSeqAsciiString(Map* map, HeapObject* object) {
306     return SeqAsciiString::cast(object)->
307         SeqAsciiStringSize(map->instance_type());
308   }
309 
VisitSeqTwoByteString(Map * map,HeapObject * object)310   static inline int VisitSeqTwoByteString(Map* map, HeapObject* object) {
311     return SeqTwoByteString::cast(object)->
312         SeqTwoByteStringSize(map->instance_type());
313   }
314 
VisitFreeSpace(Map * map,HeapObject * object)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>
VisitSpecialized(Map * map,HeapObject * object)322     static inline int VisitSpecialized(Map* map, HeapObject* object) {
323       return object_size;
324     }
325 
Visit(Map * map,HeapObject * object)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