1 // Copyright 2014 The Chromium 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 TOOLS_BLINK_GC_PLUGIN_EDGE_H_ 6 #define TOOLS_BLINK_GC_PLUGIN_EDGE_H_ 7 8 #include <cassert> 9 #include <deque> 10 #include <vector> 11 12 #include "TracingStatus.h" 13 14 class RecordInfo; 15 16 class Edge; 17 class Collection; 18 class CrossThreadPersistent; 19 class Iterator; 20 class Member; 21 class Persistent; 22 class RawPtr; 23 class RefPtr; 24 class UniquePtr; 25 class Value; 26 class WeakMember; 27 class TraceWrapperV8Reference; 28 29 // Bare-bones visitor. 30 class EdgeVisitor { 31 public: ~EdgeVisitor()32 virtual ~EdgeVisitor() {} VisitValue(Value *)33 virtual void VisitValue(Value*) {} VisitRawPtr(RawPtr *)34 virtual void VisitRawPtr(RawPtr*) {} VisitRefPtr(RefPtr *)35 virtual void VisitRefPtr(RefPtr*) {} VisitUniquePtr(UniquePtr *)36 virtual void VisitUniquePtr(UniquePtr*) {} VisitMember(Member *)37 virtual void VisitMember(Member*) {} VisitWeakMember(WeakMember *)38 virtual void VisitWeakMember(WeakMember*) {} VisitPersistent(Persistent *)39 virtual void VisitPersistent(Persistent*) {} VisitCrossThreadPersistent(CrossThreadPersistent *)40 virtual void VisitCrossThreadPersistent(CrossThreadPersistent*) {} VisitCollection(Collection *)41 virtual void VisitCollection(Collection*) {} VisitIterator(Iterator *)42 virtual void VisitIterator(Iterator*) {} VisitTraceWrapperV8Reference(TraceWrapperV8Reference *)43 virtual void VisitTraceWrapperV8Reference(TraceWrapperV8Reference*) {} 44 }; 45 46 // Recursive edge visitor. The traversed path is accessible in context. 47 class RecursiveEdgeVisitor : public EdgeVisitor { 48 public: 49 // Overrides that recursively walk the edges and record the path. 50 void VisitValue(Value*) override; 51 void VisitRawPtr(RawPtr*) override; 52 void VisitRefPtr(RefPtr*) override; 53 void VisitUniquePtr(UniquePtr*) override; 54 void VisitMember(Member*) override; 55 void VisitWeakMember(WeakMember*) override; 56 void VisitPersistent(Persistent*) override; 57 void VisitCrossThreadPersistent(CrossThreadPersistent*) override; 58 void VisitCollection(Collection*) override; 59 void VisitIterator(Iterator*) override; 60 void VisitTraceWrapperV8Reference(TraceWrapperV8Reference*) override; 61 62 protected: 63 typedef std::deque<Edge*> Context; context()64 Context& context() { return context_; } Parent()65 Edge* Parent() { return context_.empty() ? 0 : context_.front(); } GrandParent()66 Edge* GrandParent() { 67 return Parent() ? (context_.size() > 1 ? context_[1] : nullptr) : nullptr; 68 } Enter(Edge * e)69 void Enter(Edge* e) { return context_.push_front(e); } Leave()70 void Leave() { context_.pop_front(); } 71 72 // Default callback to overwrite in visitor subclass. 73 virtual void AtValue(Value*); 74 virtual void AtRawPtr(RawPtr*); 75 virtual void AtRefPtr(RefPtr*); 76 virtual void AtUniquePtr(UniquePtr*); 77 virtual void AtMember(Member*); 78 virtual void AtWeakMember(WeakMember*); 79 virtual void AtTraceWrapperV8Reference(TraceWrapperV8Reference*); 80 virtual void AtPersistent(Persistent*); 81 virtual void AtCrossThreadPersistent(CrossThreadPersistent*); 82 virtual void AtCollection(Collection*); 83 virtual void AtIterator(Iterator*); 84 85 private: 86 Context context_; 87 }; 88 89 // Base class for all edges. 90 class Edge { 91 public: 92 enum NeedsTracingOption { kRecursive, kNonRecursive }; 93 enum LivenessKind { kWeak, kStrong, kRoot }; 94 ~Edge()95 virtual ~Edge() {} 96 virtual LivenessKind Kind() = 0; 97 virtual void Accept(EdgeVisitor*) = 0; 98 virtual bool NeedsFinalization() = 0; NeedsTracing(NeedsTracingOption)99 virtual TracingStatus NeedsTracing(NeedsTracingOption) { 100 return TracingStatus::Unknown(); 101 } 102 IsValue()103 virtual bool IsValue() { return false; } IsRawPtr()104 virtual bool IsRawPtr() { return false; } IsRefPtr()105 virtual bool IsRefPtr() { return false; } IsUniquePtr()106 virtual bool IsUniquePtr() { return false; } IsMember()107 virtual bool IsMember() { return false; } IsWeakMember()108 virtual bool IsWeakMember() { return false; } IsCollection()109 virtual bool IsCollection() { return false; } IsTraceWrapperV8Reference()110 virtual bool IsTraceWrapperV8Reference() { return false; } 111 }; 112 113 // A value edge is a direct edge to some type, eg, part-object edges. 114 class Value : public Edge { 115 public: Value(RecordInfo * value)116 explicit Value(RecordInfo* value) : value_(value) {}; IsValue()117 bool IsValue() override { return true; } Kind()118 LivenessKind Kind() override { return kStrong; } 119 bool NeedsFinalization() override; 120 TracingStatus NeedsTracing(NeedsTracingOption) override; Accept(EdgeVisitor * visitor)121 void Accept(EdgeVisitor* visitor) override { visitor->VisitValue(this); } value()122 RecordInfo* value() { return value_; } 123 124 private: 125 RecordInfo* value_; 126 }; 127 128 // Shared base for smart-pointer edges. 129 class PtrEdge : public Edge { 130 public: ~PtrEdge()131 ~PtrEdge() { delete ptr_; } ptr()132 Edge* ptr() { return ptr_; } 133 protected: PtrEdge(Edge * ptr)134 PtrEdge(Edge* ptr) : ptr_(ptr) { 135 assert(ptr && "EdgePtr pointer must be non-null"); 136 } 137 private: 138 Edge* ptr_; 139 }; 140 141 class RawPtr : public PtrEdge { 142 public: RawPtr(Edge * ptr,bool is_ref_type)143 RawPtr(Edge* ptr, bool is_ref_type) 144 : PtrEdge(ptr) 145 , is_ref_type_(is_ref_type) 146 { 147 } 148 IsRawPtr()149 bool IsRawPtr() override { return true; } Kind()150 LivenessKind Kind() override { return kWeak; } NeedsFinalization()151 bool NeedsFinalization() override { return false; } NeedsTracing(NeedsTracingOption)152 TracingStatus NeedsTracing(NeedsTracingOption) override { 153 return TracingStatus::Illegal(); 154 } Accept(EdgeVisitor * visitor)155 void Accept(EdgeVisitor* visitor) override { visitor->VisitRawPtr(this); } 156 HasReferenceType()157 bool HasReferenceType() { return is_ref_type_; } 158 private: 159 bool is_ref_type_; 160 }; 161 162 class RefPtr : public PtrEdge { 163 public: RefPtr(Edge * ptr,LivenessKind kind)164 RefPtr(Edge* ptr, LivenessKind kind) : PtrEdge(ptr), kind_(kind) {} IsRefPtr()165 bool IsRefPtr() override { return true; } Kind()166 LivenessKind Kind() override { return kind_; } NeedsFinalization()167 bool NeedsFinalization() override { return true; } NeedsTracing(NeedsTracingOption)168 TracingStatus NeedsTracing(NeedsTracingOption) override { 169 return TracingStatus::Illegal(); 170 } Accept(EdgeVisitor * visitor)171 void Accept(EdgeVisitor* visitor) override { visitor->VisitRefPtr(this); } 172 173 private: 174 LivenessKind kind_; 175 }; 176 177 class UniquePtr : public PtrEdge { 178 public: UniquePtr(Edge * ptr)179 explicit UniquePtr(Edge* ptr) : PtrEdge(ptr) { } IsUniquePtr()180 bool IsUniquePtr() override { return true; } Kind()181 LivenessKind Kind() override { return kStrong; } NeedsFinalization()182 bool NeedsFinalization() override { return true; } NeedsTracing(NeedsTracingOption)183 TracingStatus NeedsTracing(NeedsTracingOption) override { 184 return TracingStatus::Illegal(); 185 } Accept(EdgeVisitor * visitor)186 void Accept(EdgeVisitor* visitor) override { visitor->VisitUniquePtr(this); } 187 }; 188 189 class Member : public PtrEdge { 190 public: Member(Edge * ptr)191 explicit Member(Edge* ptr) : PtrEdge(ptr) { } IsMember()192 bool IsMember() override { return true; } Kind()193 LivenessKind Kind() override { return kStrong; } NeedsFinalization()194 bool NeedsFinalization() override { return false; } NeedsTracing(NeedsTracingOption)195 TracingStatus NeedsTracing(NeedsTracingOption) override { 196 return TracingStatus::Needed(); 197 } Accept(EdgeVisitor * visitor)198 void Accept(EdgeVisitor* visitor) override { visitor->VisitMember(this); } 199 }; 200 201 class WeakMember : public PtrEdge { 202 public: WeakMember(Edge * ptr)203 explicit WeakMember(Edge* ptr) : PtrEdge(ptr) { } IsWeakMember()204 bool IsWeakMember() override { return true; } Kind()205 LivenessKind Kind() override { return kWeak; } NeedsFinalization()206 bool NeedsFinalization() override { return false; } NeedsTracing(NeedsTracingOption)207 TracingStatus NeedsTracing(NeedsTracingOption) override { 208 return TracingStatus::Needed(); 209 } Accept(EdgeVisitor * visitor)210 void Accept(EdgeVisitor* visitor) override { visitor->VisitWeakMember(this); } 211 }; 212 213 class Persistent : public PtrEdge { 214 public: Persistent(Edge * ptr)215 explicit Persistent(Edge* ptr) : PtrEdge(ptr) { } Kind()216 LivenessKind Kind() override { return kRoot; } NeedsFinalization()217 bool NeedsFinalization() override { return true; } NeedsTracing(NeedsTracingOption)218 TracingStatus NeedsTracing(NeedsTracingOption) override { 219 return TracingStatus::Illegal(); 220 } Accept(EdgeVisitor * visitor)221 void Accept(EdgeVisitor* visitor) override { visitor->VisitPersistent(this); } 222 }; 223 224 class CrossThreadPersistent : public PtrEdge { 225 public: CrossThreadPersistent(Edge * ptr)226 explicit CrossThreadPersistent(Edge* ptr) : PtrEdge(ptr) { } Kind()227 LivenessKind Kind() override { return kRoot; } NeedsFinalization()228 bool NeedsFinalization() override { return true; } NeedsTracing(NeedsTracingOption)229 TracingStatus NeedsTracing(NeedsTracingOption) override { 230 return TracingStatus::Illegal(); 231 } Accept(EdgeVisitor * visitor)232 void Accept(EdgeVisitor* visitor) override { 233 visitor->VisitCrossThreadPersistent(this); 234 } 235 }; 236 237 class TraceWrapperV8Reference : public PtrEdge { 238 public: TraceWrapperV8Reference(Edge * ptr)239 explicit TraceWrapperV8Reference(Edge* ptr) : PtrEdge(ptr) {} IsTraceWrapperV8Reference()240 bool IsTraceWrapperV8Reference() override { return true; } Kind()241 LivenessKind Kind() override { return kStrong; } NeedsFinalization()242 bool NeedsFinalization() override { return true; } NeedsTracing(NeedsTracingOption)243 TracingStatus NeedsTracing(NeedsTracingOption) override { 244 return TracingStatus::Needed(); 245 } Accept(EdgeVisitor * visitor)246 void Accept(EdgeVisitor* visitor) override { 247 visitor->VisitTraceWrapperV8Reference(this); 248 } 249 }; 250 251 class Collection : public Edge { 252 public: 253 typedef std::vector<Edge*> Members; Collection(RecordInfo * info,bool on_heap)254 Collection(RecordInfo* info, bool on_heap) : info_(info), on_heap_(on_heap) {} ~Collection()255 ~Collection() { 256 for (Members::iterator it = members_.begin(); it != members_.end(); ++it) { 257 assert(*it && "Collection-edge members must be non-null"); 258 delete *it; 259 } 260 } IsCollection()261 bool IsCollection() override { return true; } Kind()262 LivenessKind Kind() override { return kStrong; } on_heap()263 bool on_heap() { return on_heap_; } members()264 Members& members() { return members_; } Accept(EdgeVisitor * visitor)265 void Accept(EdgeVisitor* visitor) override { visitor->VisitCollection(this); } AcceptMembers(EdgeVisitor * visitor)266 void AcceptMembers(EdgeVisitor* visitor) { 267 for (Members::iterator it = members_.begin(); it != members_.end(); ++it) 268 (*it)->Accept(visitor); 269 } 270 bool NeedsFinalization() override; NeedsTracing(NeedsTracingOption)271 TracingStatus NeedsTracing(NeedsTracingOption) override { 272 if (on_heap_) 273 return TracingStatus::Needed(); 274 // For off-heap collections, determine tracing status of members. 275 TracingStatus status = TracingStatus::Unneeded(); 276 for (Members::iterator it = members_.begin(); it != members_.end(); ++it) { 277 // Do a non-recursive test here since members could equal the holder. 278 status = status.LUB((*it)->NeedsTracing(kNonRecursive)); 279 } 280 return status; 281 } 282 283 private: 284 RecordInfo* info_; 285 Members members_; 286 bool on_heap_; 287 }; 288 289 // An iterator edge is a direct edge to some iterator type. 290 class Iterator : public Edge { 291 public: Iterator(RecordInfo * info,bool on_heap)292 Iterator(RecordInfo* info, bool on_heap) : info_(info), on_heap_(on_heap) {} ~Iterator()293 ~Iterator() {} 294 Accept(EdgeVisitor * visitor)295 void Accept(EdgeVisitor* visitor) override { visitor->VisitIterator(this); } Kind()296 LivenessKind Kind() override { return kStrong; } NeedsFinalization()297 bool NeedsFinalization() override { return false; } NeedsTracing(NeedsTracingOption)298 TracingStatus NeedsTracing(NeedsTracingOption) override { 299 if (on_heap_) 300 return TracingStatus::Illegal(); 301 return TracingStatus::Unneeded(); 302 } 303 info()304 RecordInfo* info() const { return info_; } 305 on_heap()306 bool on_heap() const { return on_heap_; } 307 308 private: 309 RecordInfo* info_; 310 bool on_heap_; 311 }; 312 313 #endif // TOOLS_BLINK_GC_PLUGIN_EDGE_H_ 314