OLD | NEW |
---|---|
(Empty) | |
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | |
2 // for details. All rights reserved. Use of this source code is governed by a | |
3 // BSD-style license that can be found in the LICENSE file. | |
4 | |
5 #include "vm/object_graph.h" | |
6 | |
7 #include "vm/dart.h" | |
8 #include "vm/growable_array.h" | |
9 #include "vm/isolate.h" | |
10 #include "vm/object.h" | |
11 #include "vm/raw_object.h" | |
12 #include "vm/visitor.h" | |
13 | |
14 namespace dart { | |
15 | |
16 // The state of a pre-order, depth-first traversal of an object graph. | |
17 // When a node is visited, *all* its children are pushed to the stack at once. | |
18 // We insert a sentinel between the node and its children on the stack, to | |
19 // remember that the node has been visited. The node is kept on the stack while | |
20 // its children are processed, to give the visitor a complete chain of parents. | |
21 // | |
22 // TODO(koda): Potential optimizations: | |
23 // - Linked chunks instead of std::vector. | |
24 // - Use smi/heap tag bit instead of full-word sentinel. | |
25 // - Extend RawObject with incremental iteration (one child at a time). | |
26 class ObjectGraph::Stack : public ObjectPointerVisitor { | |
27 public: | |
28 explicit Stack(Isolate* isolate) | |
29 : ObjectPointerVisitor(isolate), data_(kInitialCapacity) { } | |
30 | |
31 // Marks and pushes. Used to initialize this stack with roots. | |
32 virtual void VisitPointers(RawObject** first, RawObject** last) { | |
33 for (RawObject** current = first; current <= last; ++current) { | |
34 if ((*current)->IsHeapObject() && !(*current)->IsMarked()) { | |
35 (*current)->SetMarkBit(); | |
36 data_.Add(*current); | |
37 } | |
38 } | |
39 } | |
40 | |
41 // Traverses the object graph from the current state. | |
42 void TraverseGraph(ObjectGraph::Visitor* visitor) { | |
43 while (!data_.is_empty()) { | |
44 RawObject* obj = data_.Last(); | |
45 if (obj == kSentinel) { | |
46 data_.RemoveLast(); | |
47 // The node below the sentinel has already been visited. | |
48 data_.RemoveLast(); | |
49 continue; | |
50 } | |
51 ASSERT(obj->IsHeapObject()); | |
52 data_.Add(kSentinel); | |
53 StackIterator it(this, data_.length() - 2); | |
54 switch (visitor->VisitObject(&it)) { | |
55 case ObjectGraph::Visitor::kProceed: | |
56 obj->VisitPointers(this); | |
57 break; | |
58 case ObjectGraph::Visitor::kBacktrack: | |
59 break; | |
60 case ObjectGraph::Visitor::kAbort: | |
61 return; | |
62 } | |
63 } | |
64 } | |
65 | |
66 private: | |
67 static RawObject* const kSentinel; | |
68 static const intptr_t kInitialCapacity = 1024; | |
69 GrowableArray<RawObject*> data_; | |
70 friend class StackIterator; | |
71 DISALLOW_COPY_AND_ASSIGN(Stack); | |
72 }; | |
73 | |
74 | |
75 // We only visit heap objects, so any Smi works as the sentinel. | |
76 RawObject* const ObjectGraph::Stack::kSentinel = Smi::New(0); | |
77 | |
78 | |
79 RawObject* ObjectGraph::StackIterator::Get() const { | |
80 return stack_->data_[index_]; | |
81 } | |
82 | |
83 | |
84 bool ObjectGraph::StackIterator::MoveToParent() { | |
85 // The parent is just below the next sentinel. | |
86 for (int i = index_; i >= 1; --i) { | |
87 if (stack_->data_[i] == Stack::kSentinel) { | |
88 index_ = i - 1; | |
89 return true; | |
90 } | |
91 } | |
92 return false; | |
93 } | |
94 | |
95 | |
96 class Unmarker : public ObjectVisitor { | |
97 public: | |
98 explicit Unmarker(Isolate* isolate) : ObjectVisitor(isolate) { } | |
99 | |
100 void VisitObject(RawObject* obj) { | |
101 if (obj->IsMarked()) { | |
102 obj->ClearMarkBit(); | |
103 } | |
104 } | |
105 | |
106 static void UnmarkAll(Isolate* isolate) { | |
107 Unmarker unmarker(isolate); | |
108 isolate->heap()->IterateObjects(&unmarker); | |
109 } | |
110 | |
111 private: | |
112 DISALLOW_COPY_AND_ASSIGN(Unmarker); | |
113 }; | |
114 | |
115 | |
116 ObjectGraph::ObjectGraph(Isolate* isolate) : isolate_(isolate) { | |
117 // The VM isolate has all its objects pre-marked, so iterating over it | |
118 // would be a no-op. | |
119 ASSERT(isolate_ != Dart::vm_isolate()); | |
120 isolate_->heap()->WriteProtectCode(false); | |
121 } | |
122 | |
123 | |
124 ObjectGraph::~ObjectGraph() { | |
125 isolate_->heap()->WriteProtectCode(true); | |
Ivan Posva
2014/05/02 22:20:41
To make sure that this destructor is called you ne
koda
2014/05/02 22:45:19
Done in follow-up CL.
| |
126 } | |
127 | |
128 | |
129 void ObjectGraph::IterateObjects(ObjectGraph::Visitor* visitor) { | |
130 NoGCScope no_gc_scope_; | |
131 Stack stack(isolate_); | |
132 isolate_->VisitObjectPointers(&stack, false, false); | |
133 stack.TraverseGraph(visitor); | |
134 Unmarker::UnmarkAll(isolate_); | |
135 } | |
136 | |
137 | |
138 void ObjectGraph::IterateObjectsFrom(const Object& root, | |
139 ObjectGraph::Visitor* visitor) { | |
140 NoGCScope no_gc_scope_; | |
141 Stack stack(isolate_); | |
142 RawObject* root_raw = root.raw(); | |
143 stack.VisitPointer(&root_raw); | |
144 stack.TraverseGraph(visitor); | |
145 // TODO(koda): Optimize if we only visited a small subgraph. | |
146 Unmarker::UnmarkAll(isolate_); | |
147 } | |
148 | |
149 } // namespace dart | |
OLD | NEW |