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#include "platform/assert.h"
7#include "vm/unit_test.h"
8
9namespace dart {
10
11#if !defined(PRODUCT)
12
13class CounterVisitor : public ObjectGraph::Visitor {
14 public:
15 // Records the number of objects and total size visited, excluding 'skip'
16 // and any objects only reachable through 'skip'.
17 CounterVisitor(ObjectPtr skip, ObjectPtr expected_parent)
18 : count_(0), size_(0), skip_(skip), expected_parent_(expected_parent) {}
19
20 virtual Direction VisitObject(ObjectGraph::StackIterator* it) {
21 ObjectPtr obj = it->Get();
22 if (obj == skip_) {
23 EXPECT(it->MoveToParent());
24 EXPECT_EQ(expected_parent_, it->Get());
25 return kBacktrack;
26 }
27 ++count_;
28 size_ += obj->untag()->HeapSize();
29 return kProceed;
30 }
31
32 int count() const { return count_; }
33 int size() const { return size_; }
34
35 private:
36 int count_;
37 intptr_t size_;
38 ObjectPtr skip_;
39 ObjectPtr expected_parent_;
40};
41
42ISOLATE_UNIT_TEST_CASE(ObjectGraph) {
43 auto heap = thread->isolate_group()->heap();
44
45 // Create a simple object graph with objects a, b, c, d:
46 // a+->b+->c
47 // +   +
48 // |   v
49 // +-->d
50 Array& a = Array::Handle(ptr: Array::New(len: 12, space: Heap::kNew));
51 Array& b = Array::Handle(ptr: Array::New(len: 2, space: Heap::kOld));
52 Array& c = Array::Handle(ptr: Array::New(len: 0, space: Heap::kOld));
53 Array& d = Array::Handle(ptr: Array::New(len: 0, space: Heap::kOld));
54 a.SetAt(10, b);
55 b.SetAt(0, c);
56 b.SetAt(1, d);
57 a.SetAt(11, d);
58 intptr_t a_size = a.ptr()->untag()->HeapSize();
59 intptr_t b_size = b.ptr()->untag()->HeapSize();
60 intptr_t c_size = c.ptr()->untag()->HeapSize();
61 intptr_t d_size = d.ptr()->untag()->HeapSize();
62 {
63 // No more allocation; raw pointers ahead.
64 GcSafepointOperationScope safepoint(thread);
65 ObjectPtr b_raw = b.ptr();
66 // Clear handles to cut unintended retained paths.
67 b = Array::null();
68 c = Array::null();
69 d = Array::null();
70 ObjectGraph graph(thread);
71 {
72 HeapIterationScope iteration_scope(thread, true);
73 {
74 // Compare count and size when 'b' is/isn't skipped.
75 CounterVisitor with(Object::null(), Object::null());
76 graph.IterateObjectsFrom(root: a, visitor: &with);
77 CounterVisitor without(b_raw, a.ptr());
78 graph.IterateObjectsFrom(root: a, visitor: &without);
79 // Only 'b' and 'c' were cut off.
80 EXPECT_EQ(2, with.count() - without.count());
81 EXPECT_EQ(b_size + c_size, with.size() - without.size());
82 }
83 {
84 // Like above, but iterate over the entire isolate. The counts and sizes
85 // are thus larger, but the difference should still be just 'b' and 'c'.
86 CounterVisitor with(Object::null(), Object::null());
87 graph.IterateObjects(visitor: &with);
88 CounterVisitor without(b_raw, a.ptr());
89 graph.IterateObjects(visitor: &without);
90 EXPECT_EQ(2, with.count() - without.count());
91 EXPECT_EQ(b_size + c_size, with.size() - without.size());
92 }
93 }
94 EXPECT_EQ(a_size + b_size + c_size + d_size,
95 graph.SizeRetainedByInstance(a));
96 }
97 {
98 // Get hold of c again.
99 b ^= a.At(10);
100 c ^= b.At(0);
101 b = Array::null();
102 ObjectGraph graph(thread);
103 // A retaining path should end like this: c <- b <- a <- ...
104 {
105 HANDLESCOPE(thread);
106 // Test null, empty, and length 1 array.
107 intptr_t null_length =
108 graph.RetainingPath(obj: &c, path: Object::null_array()).length;
109 intptr_t empty_length =
110 graph.RetainingPath(obj: &c, path: Object::empty_array()).length;
111 Array& path = Array::Handle(ptr: Array::New(len: 1, space: Heap::kNew));
112 intptr_t one_length = graph.RetainingPath(obj: &c, path).length;
113 EXPECT_EQ(null_length, empty_length);
114 EXPECT_EQ(null_length, one_length);
115 EXPECT_LE(3, null_length);
116 }
117 {
118 HANDLESCOPE(thread);
119 Array& path = Array::Handle(ptr: Array::New(len: 6, space: Heap::kNew));
120 // Trigger a full GC to increase probability of concurrent tasks.
121 heap->CollectAllGarbage();
122 intptr_t length = graph.RetainingPath(obj: &c, path).length;
123 EXPECT_LE(3, length);
124 Array& expected_c = Array::Handle();
125 expected_c ^= path.At(0);
126 // c is the first element in b.
127 Smi& offset_from_parent = Smi::Handle();
128 offset_from_parent ^= path.At(1);
129 EXPECT_EQ(Array::element_offset(0), offset_from_parent.Value());
130 Array& expected_b = Array::Handle();
131 expected_b ^= path.At(2);
132 // b is the element with index 10 in a.
133 offset_from_parent ^= path.At(3);
134 EXPECT_EQ(Array::element_offset(10), offset_from_parent.Value());
135 Array& expected_a = Array::Handle();
136 expected_a ^= path.At(4);
137 EXPECT(expected_c.ptr() == c.ptr());
138 EXPECT(expected_b.ptr() == a.At(10));
139 EXPECT(expected_a.ptr() == a.ptr());
140 }
141 }
142}
143
144static void WeakHandleFinalizer(void* isolate_callback_data, void* peer) {}
145
146ISOLATE_UNIT_TEST_CASE(RetainingPathGCRoot) {
147 Dart_PersistentHandle persistent_handle;
148 Dart_WeakPersistentHandle weak_persistent_handle;
149 Array& path = Array::Handle(ptr: Array::New(len: 1, space: Heap::kNew));
150 ObjectGraph graph(thread);
151 Dart_Handle handle = Api::NewHandle(thread, raw: path.ptr());
152
153 // GC root should be a local handle
154 auto result = graph.RetainingPath(obj: &path, path);
155 EXPECT_STREQ(result.gc_root_type, "local handle");
156
157 // GC root should now be a weak persistent handle
158 {
159 TransitionVMToNative transition(thread);
160 weak_persistent_handle = Dart_NewWeakPersistentHandle(
161 object: handle, peer: reinterpret_cast<void*>(0xdeadbeef), external_allocation_size: 128, callback: WeakHandleFinalizer);
162 }
163 result = graph.RetainingPath(obj: &path, path);
164 EXPECT_STREQ(result.gc_root_type, "weak persistent handle");
165
166 // GC root should now be a persistent handle
167 {
168 TransitionVMToNative transition(thread);
169 persistent_handle = Dart_NewPersistentHandle(object: handle);
170 }
171 result = graph.RetainingPath(obj: &path, path);
172 EXPECT_STREQ(result.gc_root_type, "persistent handle");
173
174 // Delete the persistent handle. GC root should now be weak persistent handle
175 {
176 TransitionVMToNative transition(thread);
177 Dart_DeletePersistentHandle(object: persistent_handle);
178 persistent_handle = nullptr;
179 }
180 result = graph.RetainingPath(obj: &path, path);
181 EXPECT_STREQ(result.gc_root_type, "weak persistent handle");
182
183 // Delete the weak persistent handle. GC root should now be local handle.
184 {
185 TransitionVMToNative transition(thread);
186 Dart_DeleteWeakPersistentHandle(object: weak_persistent_handle);
187 weak_persistent_handle = nullptr;
188 }
189 result = graph.RetainingPath(obj: &path, path);
190 EXPECT_STREQ(result.gc_root_type, "local handle");
191}
192
193#endif // !defined(PRODUCT)
194
195} // namespace dart
196

source code of dart_sdk/runtime/vm/object_graph_test.cc