2 * Copyright (C) 2013 Google Inc. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are
8 * * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above
11 * copyright notice, this list of conditions and the following disclaimer
12 * in the documentation and/or other materials provided with the
14 * * Neither the name of Google Inc. nor the names of its
15 * contributors may be used to endorse or promote products derived from
16 * this software without specific prior written permission.
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 #include "platform/PlatformExport.h"
35 #include "platform/heap/ThreadState.h"
36 #include "wtf/Assertions.h"
37 #include "wtf/Deque.h"
38 #include "wtf/Forward.h"
39 #include "wtf/HashMap.h"
40 #include "wtf/HashTraits.h"
41 #include "wtf/InstanceCounter.h"
42 #include "wtf/OwnPtr.h"
43 #include "wtf/RefPtr.h"
44 #include "wtf/TypeTraits.h"
45 #include "wtf/WeakPtr.h"
46 #if ENABLE(GC_PROFILING)
47 #include "wtf/text/WTFString.h"
51 #define DEBUG_ONLY(x) x
58 class FinalizedHeapObjectHeader;
59 template<typename T> class GarbageCollectedFinalized;
60 class HeapObjectHeader;
61 template<typename T> class Member;
62 template<typename T> class WeakMember;
65 template<bool needsTracing, WTF::WeakHandlingFlag weakHandlingFlag, WTF::ShouldWeakPointersBeMarkedStrongly strongify, typename T, typename Traits> struct CollectionBackingTraceTrait;
67 // The TraceMethodDelegate is used to convert a trace method for type T to a TraceCallback.
68 // This allows us to pass a type's trace method as a parameter to the PersistentNode
69 // constructor. The PersistentNode constructor needs the specific trace method due an issue
70 // with the Windows compiler which instantiates even unused variables. This causes problems
71 // in header files where we have only forward declarations of classes.
72 template<typename T, void (T::*method)(Visitor*)>
73 struct TraceMethodDelegate {
74 static void trampoline(Visitor* visitor, void* self) { (reinterpret_cast<T*>(self)->*method)(visitor); }
77 // GCInfo contains meta-data associated with objects allocated in the
78 // Blink heap. This meta-data consists of a function pointer used to
79 // trace the pointers in the object during garbage collection, an
80 // indication of whether or not the object needs a finalization
81 // callback, and a function pointer used to finalize the object when
82 // the garbage collector determines that the object is no longer
83 // reachable. There is a GCInfo struct for each class that directly
84 // inherits from GarbageCollected or GarbageCollectedFinalized.
86 bool hasFinalizer() const { return m_nonTrivialFinalizer; }
87 bool hasVTable() const { return m_hasVTable; }
88 TraceCallback m_trace;
89 FinalizationCallback m_finalize;
90 bool m_nonTrivialFinalizer;
92 #if ENABLE(GC_PROFILING)
93 // |m_className| is held as a reference to prevent dtor being called at exit.
94 const String& m_className;
98 // The FinalizerTraitImpl specifies how to finalize objects. Object
99 // that inherit from GarbageCollectedFinalized are finalized by
100 // calling their 'finalize' method which by default will call the
101 // destructor on the object.
102 template<typename T, bool isGarbageCollectedFinalized>
103 struct FinalizerTraitImpl;
106 struct FinalizerTraitImpl<T, true> {
107 static void finalize(void* obj) { static_cast<T*>(obj)->finalizeGarbageCollectedObject(); };
111 struct FinalizerTraitImpl<T, false> {
112 static void finalize(void* obj) { };
115 // The FinalizerTrait is used to determine if a type requires
116 // finalization and what finalization means.
118 // By default classes that inherit from GarbageCollectedFinalized need
119 // finalization and finalization means calling the 'finalize' method
120 // of the object. The FinalizerTrait can be specialized if the default
121 // behavior is not desired.
123 struct FinalizerTrait {
124 static const bool nonTrivialFinalizer = WTF::IsSubclassOfTemplate<typename WTF::RemoveConst<T>::Type, GarbageCollectedFinalized>::value;
125 static void finalize(void* obj) { FinalizerTraitImpl<T, nonTrivialFinalizer>::finalize(obj); }
128 // Trait to get the GCInfo structure for types that have their
129 // instances allocated in the Blink garbage-collected heap.
130 template<typename T> struct GCInfoTrait;
132 template<typename T> class GarbageCollected;
133 class GarbageCollectedMixin;
134 template<typename T, bool = WTF::IsSubclassOfTemplate<typename WTF::RemoveConst<T>::Type, GarbageCollected>::value> class NeedsAdjustAndMark;
137 class NeedsAdjustAndMark<T, true> {
139 static const bool value = false;
142 template <typename T> const bool NeedsAdjustAndMark<T, true>::value;
145 class NeedsAdjustAndMark<T, false> {
147 static const bool value = WTF::IsSubclass<typename WTF::RemoveConst<T>::Type, GarbageCollectedMixin>::value;
150 template <typename T> const bool NeedsAdjustAndMark<T, false>::value;
152 template<typename T, bool = NeedsAdjustAndMark<T>::value> class DefaultTraceTrait;
154 // The TraceTrait is used to specify how to mark an object pointer and
155 // how to trace all of the pointers in the object.
157 // By default, the 'trace' method implemented on an object itself is
158 // used to trace the pointers to other heap objects inside the object.
160 // However, the TraceTrait can be specialized to use a different
161 // implementation. A common case where a TraceTrait specialization is
162 // needed is when multiple inheritance leads to pointers that are not
163 // to the start of the object in the Blink garbage-collected heap. In
164 // that case the pointer has to be adjusted before marking.
168 // Default implementation of TraceTrait<T>::trace just statically
169 // dispatches to the trace method of the class T.
170 static void trace(Visitor* visitor, void* self)
172 static_cast<T*>(self)->trace(visitor);
175 static void mark(Visitor* visitor, const T* t)
177 DefaultTraceTrait<T>::mark(visitor, t);
181 static void checkGCInfo(Visitor* visitor, const T* t)
183 DefaultTraceTrait<T>::checkGCInfo(visitor, t);
188 template<typename T> class TraceTrait<const T> : public TraceTrait<T> { };
190 template<typename Collection>
191 struct OffHeapCollectionTraceTrait;
194 struct ObjectAliveTrait {
195 static bool isAlive(Visitor*, T*);
198 // Visitor is used to traverse the Blink object graph. Used for the
199 // marking phase of the mark-sweep garbage collector.
201 // Pointers are marked and pushed on the marking stack by calling the
202 // |mark| method with the pointer as an argument.
204 // Pointers within objects are traced by calling the |trace| methods
205 // with the object as an argument. Tracing objects will mark all of the
206 // contained pointers and push them on the marking stack.
207 class PLATFORM_EXPORT Visitor {
209 virtual ~Visitor() { }
212 static void verifyGarbageCollectedIfMember(T*)
217 static void verifyGarbageCollectedIfMember(Member<T>* t)
219 t->verifyTypeIsGarbageCollected();
222 // One-argument templated mark method. This uses the static type of
223 // the argument to get the TraceTrait. By default, the mark method
224 // of the TraceTrait just calls the virtual two-argument mark method on this
225 // visitor, where the second argument is the static trace method of the trait.
232 TraceTrait<T>::checkGCInfo(this, t);
234 TraceTrait<T>::mark(this, t);
236 reinterpret_cast<const Member<T>*>(0)->verifyTypeIsGarbageCollected();
239 // Member version of the one-argument templated trace method.
241 void trace(const Member<T>& t)
246 // Fallback method used only when we need to trace raw pointers of T.
247 // This is the case when a member is a union where we do not support members.
249 void trace(const T* t)
251 mark(const_cast<T*>(t));
260 // WeakMember version of the templated trace method. It doesn't keep
261 // the traced thing alive, but will write null to the WeakMember later
262 // if the pointed-to object is dead. It's lying for this to be const,
263 // but the overloading resolver prioritizes constness too high when
264 // picking the correct overload, so all these trace methods have to have
265 // the same constness on their argument to allow the type to decide.
267 void trace(const WeakMember<T>& t)
269 // Check that we actually know the definition of T when tracing.
270 COMPILE_ASSERT(sizeof(T), WeNeedToKnowTheDefinitionOfTheTypeWeAreTracing);
271 registerWeakCell(const_cast<WeakMember<T>&>(t).cell());
272 reinterpret_cast<const Member<T>*>(0)->verifyTypeIsGarbageCollected();
276 void traceInCollection(T& t, WTF::ShouldWeakPointersBeMarkedStrongly strongify)
278 HashTraits<T>::traceInCollection(this, t, strongify);
281 // Fallback trace method for part objects to allow individual trace methods
282 // to trace through a part object with visitor->trace(m_partObject). This
283 // takes a const argument, because otherwise it will match too eagerly: a
284 // non-const argument would match a non-const Vector<T>& argument better
285 // than the specialization that takes const Vector<T>&. For a similar reason,
286 // the other specializations take a const argument even though they are
287 // usually used with non-const arguments, otherwise this function would match
290 void trace(const T& t)
292 if (WTF::IsPolymorphic<T>::value) {
293 intptr_t vtable = *reinterpret_cast<const intptr_t*>(&t);
297 const_cast<T&>(t).trace(this);
300 // The following trace methods are for off-heap collections.
301 template<typename T, size_t inlineCapacity>
302 void trace(const Vector<T, inlineCapacity>& vector)
304 OffHeapCollectionTraceTrait<Vector<T, inlineCapacity, WTF::DefaultAllocator> >::trace(this, vector);
307 template<typename T, size_t N>
308 void trace(const Deque<T, N>& deque)
310 OffHeapCollectionTraceTrait<Deque<T, N> >::trace(this, deque);
314 // These trace methods are needed to allow compiling and calling trace on
315 // transition types. We need to support calls in the non-oilpan build
316 // because a fully transitioned type (which will have its trace method
317 // called) might trace a field that is in transition. Once transition types
318 // are removed these can be removed.
319 template<typename T> void trace(const OwnPtr<T>&) { }
320 template<typename T> void trace(const RefPtr<T>&) { }
321 template<typename T> void trace(const RawPtr<T>&) { }
322 template<typename T> void trace(const WeakPtr<T>&) { }
325 // This method marks an object and adds it to the set of objects
326 // that should have their trace method called. Since not all
327 // objects have vtables we have to have the callback as an
328 // explicit argument, but we can use the templated one-argument
329 // mark method above to automatically provide the callback
331 virtual void mark(const void*, TraceCallback) = 0;
332 virtual void markNoTracing(const void* pointer) { mark(pointer, reinterpret_cast<TraceCallback>(0)); }
333 virtual void markNoTracing(HeapObjectHeader* header) { mark(header, reinterpret_cast<TraceCallback>(0)); }
334 virtual void markNoTracing(FinalizedHeapObjectHeader* header) { mark(header, reinterpret_cast<TraceCallback>(0)); }
336 // Used to mark objects during conservative scanning.
337 virtual void mark(HeapObjectHeader*, TraceCallback) = 0;
338 virtual void mark(FinalizedHeapObjectHeader*, TraceCallback) = 0;
340 // Used to delay the marking of objects until the usual marking
341 // including emphemeron iteration is done. This is used to delay
342 // the marking of collection backing stores until we know if they
343 // are reachable from locations other than the collection front
344 // object. If collection backings are reachable from other
345 // locations we strongify them to avoid issues with iterators and
347 virtual void registerDelayedMarkNoTracing(const void*) = 0;
349 // If the object calls this during the regular trace callback, then the
350 // WeakPointerCallback argument may be called later, when the strong roots
351 // have all been found. The WeakPointerCallback will normally use isAlive
352 // to find out whether some pointers are pointing to dying objects. When
353 // the WeakPointerCallback is done the object must have purged all pointers
354 // to objects where isAlive returned false. In the weak callback it is not
355 // allowed to touch other objects (except using isAlive) or to allocate on
356 // the GC heap. Note that even removing things from HeapHashSet or
357 // HeapHashMap can cause an allocation if the backing store resizes, but
358 // these collections know to remove WeakMember elements safely.
360 // The weak pointer callbacks are run on the thread that owns the
361 // object and other threads are not stopped during the
362 // callbacks. Since isAlive is used in the callback to determine
363 // if objects pointed to are alive it is crucial that the object
364 // pointed to belong to the same thread as the object receiving
365 // the weak callback. Since other threads have been resumed the
366 // mark bits are not valid for objects from other threads.
367 virtual void registerWeakMembers(const void* object, WeakPointerCallback callback) { registerWeakMembers(object, object, callback); }
368 virtual void registerWeakMembers(const void*, const void*, WeakPointerCallback) = 0;
370 template<typename T, void (T::*method)(Visitor*)>
371 void registerWeakMembers(const T* obj)
373 registerWeakMembers(obj, &TraceMethodDelegate<T, method>::trampoline);
376 // For simple cases where you just want to zero out a cell when the thing
377 // it is pointing at is garbage, you can use this. This will register a
378 // callback for each cell that needs to be zeroed, so if you have a lot of
379 // weak cells in your object you should still consider using
380 // registerWeakMembers above.
382 // In contrast to registerWeakMembers, the weak cell callbacks are
383 // run on the thread performing garbage collection. Therefore, all
384 // threads are stopped during weak cell callbacks.
386 void registerWeakCell(T** cell)
388 registerWeakCell(reinterpret_cast<void**>(cell), &handleWeakCell<T>);
391 virtual void registerWeakTable(const void*, EphemeronCallback, EphemeronCallback) = 0;
393 virtual bool weakTableRegistered(const void*) = 0;
396 virtual bool isMarked(const void*) = 0;
398 template<typename T> inline bool isAlive(T* obj)
400 // Check that we actually know the definition of T when tracing.
401 COMPILE_ASSERT(sizeof(T), WeNeedToKnowTheDefinitionOfTheTypeWeAreTracing);
402 // The strongification of collections relies on the fact that once a
403 // collection has been strongified, there is no way that it can contain
404 // non-live entries, so no entries will be removed. Since you can't set
405 // the mark bit on a null pointer, that means that null pointers are
409 return ObjectAliveTrait<T>::isAlive(this, obj);
411 template<typename T> inline bool isAlive(const Member<T>& member)
413 return isAlive(member.get());
415 template<typename T> inline bool isAlive(RawPtr<T> ptr)
417 return isAlive(ptr.get());
421 void checkGCInfo(const void*, const GCInfo*);
424 // Macro to declare methods needed for each typed heap.
425 #define DECLARE_VISITOR_METHODS(Type) \
426 DEBUG_ONLY(void checkGCInfo(const Type*, const GCInfo*);) \
427 virtual void mark(const Type*, TraceCallback) = 0; \
428 virtual bool isMarked(const Type*) = 0;
430 FOR_EACH_TYPED_HEAP(DECLARE_VISITOR_METHODS)
431 #undef DECLARE_VISITOR_METHODS
433 #if ENABLE(GC_PROFILE_MARKING)
434 void setHostInfo(void* object, const String& name)
436 m_hostObject = object;
442 virtual void registerWeakCell(void**, WeakPointerCallback) = 0;
443 #if ENABLE(GC_PROFILE_MARKING)
450 static void handleWeakCell(Visitor* self, void* obj)
452 T** cell = reinterpret_cast<T**>(obj);
453 if (*cell && !self->isAlive(*cell))
458 // We trace vectors by using the trace trait on each element, which means you
459 // can have vectors of general objects (not just pointers to objects) that can
461 template<typename T, size_t N>
462 struct OffHeapCollectionTraceTrait<WTF::Vector<T, N, WTF::DefaultAllocator> > {
463 typedef WTF::Vector<T, N, WTF::DefaultAllocator> Vector;
465 static void trace(Visitor* visitor, const Vector& vector)
467 if (vector.isEmpty())
469 for (typename Vector::const_iterator it = vector.begin(), end = vector.end(); it != end; ++it)
470 TraceTrait<T>::trace(visitor, const_cast<T*>(it));
474 template<typename T, size_t N>
475 struct OffHeapCollectionTraceTrait<WTF::Deque<T, N> > {
476 typedef WTF::Deque<T, N> Deque;
478 static void trace(Visitor* visitor, const Deque& deque)
482 for (typename Deque::const_iterator it = deque.begin(), end = deque.end(); it != end; ++it)
483 TraceTrait<T>::trace(visitor, const_cast<T*>(&(*it)));
487 template<typename T, typename Traits = WTF::VectorTraits<T> >
488 class HeapVectorBacking;
490 template<typename Table>
491 class HeapHashTableBacking {
493 static void finalize(void* pointer);
497 class DefaultTraceTrait<T, false> {
499 static void mark(Visitor* visitor, const T* t)
501 // Default mark method of the trait just calls the two-argument mark
502 // method on the visitor. The second argument is the static trace method
503 // of the trait, which by default calls the instance method
504 // trace(Visitor*) on the object.
505 visitor->mark(const_cast<T*>(t), &TraceTrait<T>::trace);
509 static void checkGCInfo(Visitor* visitor, const T* t)
511 visitor->checkGCInfo(const_cast<T*>(t), GCInfoTrait<T>::get());
517 class DefaultTraceTrait<T, true> {
519 static void mark(Visitor* visitor, const T* self)
524 // Before doing adjustAndMark we need to check if the page is orphaned
525 // since we cannot call adjustAndMark if so, as there will be no vtable.
526 // If orphaned just mark the page as traced.
527 BaseHeapPage* heapPage = pageHeaderFromObject(self);
528 if (heapPage->orphaned()) {
529 heapPage->setTracedAfterOrphaned();
532 self->adjustAndMark(visitor);
536 static void checkGCInfo(Visitor*, const T*) { }
540 template<typename T, bool = NeedsAdjustAndMark<T>::value> class DefaultObjectAliveTrait;
543 class DefaultObjectAliveTrait<T, false> {
545 static bool isAlive(Visitor* visitor, T* obj)
547 return visitor->isMarked(obj);
552 class DefaultObjectAliveTrait<T, true> {
554 static bool isAlive(Visitor* visitor, T* obj)
556 return obj->isAlive(visitor);
560 template<typename T> bool ObjectAliveTrait<T>::isAlive(Visitor* visitor, T* obj)
562 return DefaultObjectAliveTrait<T>::isAlive(visitor, obj);
565 // The GarbageCollectedMixin interface and helper macro
566 // USING_GARBAGE_COLLECTED_MIXIN can be used to automatically define
567 // TraceTrait/ObjectAliveTrait on non-leftmost deriving classes
568 // which need to be garbage collected.
570 // Consider the following case:
572 // class A : public GarbageCollected, public B {};
574 // We can't correctly handle "Member<B> p = &a" as we can't compute addr of
575 // object header statically. This can be solved by using GarbageCollectedMixin:
576 // class B : public GarbageCollectedMixin {};
577 // class A : public GarbageCollected, public B {
578 // USING_GARBAGE_COLLECTED_MIXIN(A)
581 // With the helper, as long as we are using Member<B>, TypeTrait<B> will
582 // dispatch adjustAndMark dynamically to find collect addr of the object header.
583 // Note that this is only enabled for Member<B>. For Member<A> which we can
584 // compute the object header addr statically, this dynamic dispatch is not used.
586 class PLATFORM_EXPORT GarbageCollectedMixin {
588 virtual void adjustAndMark(Visitor*) const { };
589 virtual bool isAlive(Visitor*) const { return true; };
590 virtual void trace(Visitor*) { }
593 #define USING_GARBAGE_COLLECTED_MIXIN(TYPE) \
595 virtual void adjustAndMark(blink::Visitor* visitor) const OVERRIDE \
597 typedef WTF::IsSubclassOfTemplate<typename WTF::RemoveConst<TYPE>::Type, blink::GarbageCollected> IsSubclassOfGarbageCollected; \
598 COMPILE_ASSERT(IsSubclassOfGarbageCollected::value, OnlyGarbageCollectedObjectsCanHaveGarbageCollectedMixins); \
599 visitor->mark(static_cast<const TYPE*>(this), &blink::TraceTrait<TYPE>::trace); \
601 virtual bool isAlive(blink::Visitor* visitor) const OVERRIDE \
603 return visitor->isAlive(this); \
608 #define WILL_BE_USING_GARBAGE_COLLECTED_MIXIN(TYPE) USING_GARBAGE_COLLECTED_MIXIN(TYPE)
610 #define WILL_BE_USING_GARBAGE_COLLECTED_MIXIN(TYPE)
613 #if ENABLE(GC_PROFILING)
615 struct TypenameStringTrait {
616 static const String& get()
618 DEFINE_STATIC_LOCAL(String, typenameString, (WTF::extractTypeNameFromFunctionName(WTF::extractNameFunction<T>())));
619 return typenameString;
625 struct GCInfoAtBase {
626 static const GCInfo* get()
628 static const GCInfo gcInfo = {
629 TraceTrait<T>::trace,
630 FinalizerTrait<T>::finalize,
631 FinalizerTrait<T>::nonTrivialFinalizer,
632 WTF::IsPolymorphic<T>::value,
633 #if ENABLE(GC_PROFILING)
634 TypenameStringTrait<T>::get()
641 template<typename T> class GarbageCollected;
642 template<typename T, bool = WTF::IsSubclassOfTemplate<typename WTF::RemoveConst<T>::Type, GarbageCollected>::value> struct GetGarbageCollectedBase;
645 struct GetGarbageCollectedBase<T, true> {
646 typedef typename T::GarbageCollectedBase type;
650 struct GetGarbageCollectedBase<T, false> {
656 static const GCInfo* get()
658 return GCInfoAtBase<typename GetGarbageCollectedBase<T>::type>::get();