OLD | NEW |
---|---|
1 // Copyright 2015 The Chromium Authors. All rights reserved. | 1 // Copyright 2015 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "base/trace_event/heap_profiler_stack_frame_deduplicator.h" | 5 #include "base/trace_event/heap_profiler_stack_frame_deduplicator.h" |
6 | 6 |
7 #include <iterator> | 7 #include <iterator> |
8 #include <memory> | 8 #include <memory> |
9 | 9 |
10 #include "base/macros.h" | 10 #include "base/macros.h" |
11 #include "base/memory/ptr_util.h" | |
11 #include "base/trace_event/heap_profiler_allocation_context.h" | 12 #include "base/trace_event/heap_profiler_allocation_context.h" |
13 #include "base/trace_event/heap_profiler_string_deduplicator.h" | |
14 #include "base/trace_event/trace_event_argument.h" | |
15 #include "base/values.h" | |
12 #include "testing/gtest/include/gtest/gtest.h" | 16 #include "testing/gtest/include/gtest/gtest.h" |
13 | 17 |
14 namespace base { | 18 namespace base { |
15 namespace trace_event { | 19 namespace trace_event { |
16 | 20 |
21 namespace { | |
22 | |
23 // Calls StackFrameDeduplicator::ExportIncrementally() and returns ListValue | |
24 // with exported entries. | |
25 std::unique_ptr<ListValue> ExportEntriesIncrementally( | |
26 StackFrameDeduplicator* dedup) { | |
27 TracedValue traced_value; | |
28 traced_value.BeginArray(""); | |
29 dedup->ExportIncrementally(&traced_value); | |
30 traced_value.EndArray(); | |
31 | |
32 auto base_value = traced_value.ToBaseValue(); | |
33 const DictionaryValue* dictionary; | |
34 const ListValue* entries; | |
35 if (!base_value->GetAsDictionary(&dictionary) || | |
36 !dictionary->GetList("", &entries)) { | |
Primiano Tucci (use gerrit)
2017/03/09 11:47:45
Minor thing: I think that if instead of GetList yo
DmitrySkiba
2017/03/14 22:12:47
Done.
| |
37 return nullptr; | |
38 } | |
39 | |
40 return WrapUnique(entries->DeepCopy()); | |
41 } | |
42 | |
43 struct StackFrameMapping { | |
44 StackFrameMapping(int id, StackFrame frame, int parent_id = -1) | |
45 : id(id), parent_id(parent_id) { | |
46 EXPECT_EQ(StackFrame::Type::TRACE_EVENT_NAME, frame.type); | |
47 name = static_cast<const char*>(frame.value); | |
48 } | |
49 | |
50 int id; | |
51 const char* name; | |
52 int parent_id; | |
53 }; | |
54 | |
55 std::unique_ptr<ListValue> ConvertMappingsToExportedEntries( | |
56 StringDeduplicator* string_dedup, | |
57 std::initializer_list<StackFrameMapping> mappings) { | |
58 auto entries = MakeUnique<ListValue>(); | |
59 for (const auto& mapping : mappings) { | |
60 auto entry = MakeUnique<DictionaryValue>(); | |
61 entry->SetInteger("id", mapping.id); | |
62 entry->SetInteger("name_sid", string_dedup->Insert(mapping.name)); | |
63 if (mapping.parent_id != -1) { | |
64 entry->SetInteger("parent", mapping.parent_id); | |
65 } | |
66 entries->Append(std::move(entry)); | |
67 } | |
68 return entries; | |
69 } | |
70 | |
71 void ExpectIncrementalEntries( | |
72 StackFrameDeduplicator* dedup, | |
73 StringDeduplicator* string_dedup, | |
74 std::initializer_list<StackFrameMapping> mappings) { | |
75 auto entries = ExportEntriesIncrementally(dedup); | |
76 ASSERT_TRUE(entries); | |
77 | |
78 auto expected_entries = | |
79 ConvertMappingsToExportedEntries(string_dedup, mappings); | |
80 ASSERT_TRUE(expected_entries->Equals(entries.get())) | |
81 << "expected_entries = " << *expected_entries << "entries = " << *entries; | |
82 } | |
83 | |
84 } // namespace | |
85 | |
17 // Define all strings once, because the deduplicator requires pointer equality, | 86 // Define all strings once, because the deduplicator requires pointer equality, |
18 // and string interning is unreliable. | 87 // and string interning is unreliable. |
19 StackFrame kBrowserMain = StackFrame::FromTraceEventName("BrowserMain"); | 88 StackFrame kBrowserMain = StackFrame::FromTraceEventName("BrowserMain"); |
20 StackFrame kRendererMain = StackFrame::FromTraceEventName("RendererMain"); | 89 StackFrame kRendererMain = StackFrame::FromTraceEventName("RendererMain"); |
21 StackFrame kCreateWidget = StackFrame::FromTraceEventName("CreateWidget"); | 90 StackFrame kCreateWidget = StackFrame::FromTraceEventName("CreateWidget"); |
22 StackFrame kInitialize = StackFrame::FromTraceEventName("Initialize"); | 91 StackFrame kInitialize = StackFrame::FromTraceEventName("Initialize"); |
23 StackFrame kMalloc = StackFrame::FromTraceEventName("malloc"); | 92 StackFrame kMalloc = StackFrame::FromTraceEventName("malloc"); |
93 StackFrame kNull = StackFrame::FromTraceEventName(nullptr); | |
94 | |
95 TEST(StackFrameDeduplicatorTest, ImplicitId0) { | |
96 StackFrame null_bt[] = {kNull}; | |
97 | |
98 // Empty backtraces (begin == end) are mapped to an implicitly added | |
99 // node #0. However, backtrace with a single null frame is not empty, | |
100 // and should be mapped to some other id. | |
101 | |
102 StringDeduplicator string_dedup; | |
103 StackFrameDeduplicator dedup(&string_dedup); | |
104 | |
105 // Node #0 is added implicitly and corresponds to an empty backtrace. | |
106 ASSERT_EQ(dedup.begin() + 1, dedup.end()); | |
107 ASSERT_EQ(0, dedup.Insert(std::begin(null_bt), std::begin(null_bt))); | |
108 | |
109 // Placeholder entry for ID 0 is a frame with NULL name and no parent. | |
110 // However inserting such a frame should yield a different ID. | |
111 ExpectIncrementalEntries(&dedup, &string_dedup, {{0, kNull}}); | |
112 ASSERT_EQ(1, dedup.Insert(std::begin(null_bt), std::end(null_bt))); | |
113 } | |
24 | 114 |
25 TEST(StackFrameDeduplicatorTest, SingleBacktrace) { | 115 TEST(StackFrameDeduplicatorTest, SingleBacktrace) { |
26 StackFrame bt[] = {kBrowserMain, kCreateWidget, kMalloc}; | 116 StackFrame bt[] = {kBrowserMain, kCreateWidget, kMalloc}; |
27 | 117 |
28 // The call tree should look like this (index in brackets). | 118 // The call tree should look like this (index in brackets). |
29 // | 119 // |
30 // BrowserMain [0] | 120 // BrowserMain [1] |
31 // CreateWidget [1] | 121 // CreateWidget [2] |
32 // malloc [2] | 122 // malloc [3] |
33 | 123 |
34 std::unique_ptr<StackFrameDeduplicator> dedup(new StackFrameDeduplicator); | 124 StringDeduplicator string_dedup; |
35 ASSERT_EQ(2, dedup->Insert(std::begin(bt), std::end(bt))); | 125 StackFrameDeduplicator dedup(&string_dedup); |
126 ASSERT_EQ(3, dedup.Insert(std::begin(bt), std::end(bt))); | |
36 | 127 |
37 auto iter = dedup->begin(); | 128 auto iter = dedup.begin() + 1; // skip implicit node #0 |
38 ASSERT_EQ(kBrowserMain, (iter + 0)->frame); | 129 ASSERT_EQ(kBrowserMain, (iter + 0)->frame); |
39 ASSERT_EQ(-1, (iter + 0)->parent_frame_index); | 130 ASSERT_EQ(-1, (iter + 0)->parent_frame_index); |
40 | 131 |
41 ASSERT_EQ(kCreateWidget, (iter + 1)->frame); | 132 ASSERT_EQ(kCreateWidget, (iter + 1)->frame); |
42 ASSERT_EQ(0, (iter + 1)->parent_frame_index); | 133 ASSERT_EQ(1, (iter + 1)->parent_frame_index); |
43 | 134 |
44 ASSERT_EQ(kMalloc, (iter + 2)->frame); | 135 ASSERT_EQ(kMalloc, (iter + 2)->frame); |
45 ASSERT_EQ(1, (iter + 2)->parent_frame_index); | 136 ASSERT_EQ(2, (iter + 2)->parent_frame_index); |
46 | 137 |
47 ASSERT_EQ(iter + 3, dedup->end()); | 138 ASSERT_EQ(iter + 3, dedup.end()); |
48 } | 139 } |
49 | 140 |
50 TEST(StackFrameDeduplicatorTest, SingleBacktraceWithNull) { | 141 TEST(StackFrameDeduplicatorTest, SingleBacktraceWithNull) { |
51 StackFrame null_frame = StackFrame::FromTraceEventName(nullptr); | 142 StackFrame null_frame = StackFrame::FromTraceEventName(nullptr); |
52 StackFrame bt[] = {kBrowserMain, null_frame, kMalloc}; | 143 StackFrame bt[] = {kBrowserMain, null_frame, kMalloc}; |
53 | 144 |
54 // Deduplicator doesn't care about what's inside StackFrames, | 145 // Deduplicator doesn't care about what's inside StackFrames, |
55 // and handles nullptr StackFrame values as any other. | 146 // and handles nullptr StackFrame values as any other. |
56 // | 147 // |
57 // So the call tree should look like this (index in brackets). | 148 // So the call tree should look like this (index in brackets). |
58 // | 149 // |
59 // BrowserMain [0] | 150 // BrowserMain [1] |
60 // (null) [1] | 151 // (null) [2] |
61 // malloc [2] | 152 // malloc [3] |
62 | 153 |
63 std::unique_ptr<StackFrameDeduplicator> dedup(new StackFrameDeduplicator); | 154 StringDeduplicator string_dedup; |
64 ASSERT_EQ(2, dedup->Insert(std::begin(bt), std::end(bt))); | 155 StackFrameDeduplicator dedup(&string_dedup); |
156 ASSERT_EQ(3, dedup.Insert(std::begin(bt), std::end(bt))); | |
65 | 157 |
66 auto iter = dedup->begin(); | 158 auto iter = dedup.begin() + 1; // skip implicit node #0 |
67 ASSERT_EQ(kBrowserMain, (iter + 0)->frame); | 159 ASSERT_EQ(kBrowserMain, (iter + 0)->frame); |
68 ASSERT_EQ(-1, (iter + 0)->parent_frame_index); | 160 ASSERT_EQ(-1, (iter + 0)->parent_frame_index); |
69 | 161 |
70 ASSERT_EQ(null_frame, (iter + 1)->frame); | 162 ASSERT_EQ(null_frame, (iter + 1)->frame); |
71 ASSERT_EQ(0, (iter + 1)->parent_frame_index); | 163 ASSERT_EQ(1, (iter + 1)->parent_frame_index); |
72 | 164 |
73 ASSERT_EQ(kMalloc, (iter + 2)->frame); | 165 ASSERT_EQ(kMalloc, (iter + 2)->frame); |
74 ASSERT_EQ(1, (iter + 2)->parent_frame_index); | 166 ASSERT_EQ(2, (iter + 2)->parent_frame_index); |
75 | 167 |
76 ASSERT_EQ(iter + 3, dedup->end()); | 168 ASSERT_EQ(iter + 3, dedup.end()); |
77 } | 169 } |
78 | 170 |
79 // Test that there can be different call trees (there can be multiple bottom | 171 // Test that there can be different call trees (there can be multiple bottom |
80 // frames). Also verify that frames with the same name but a different caller | 172 // frames). Also verify that frames with the same name but a different caller |
81 // are represented as distinct nodes. | 173 // are represented as distinct nodes. |
82 TEST(StackFrameDeduplicatorTest, MultipleRoots) { | 174 TEST(StackFrameDeduplicatorTest, MultipleRoots) { |
83 StackFrame bt0[] = {kBrowserMain, kCreateWidget}; | 175 StackFrame bt0[] = {kBrowserMain, kCreateWidget}; |
84 StackFrame bt1[] = {kRendererMain, kCreateWidget}; | 176 StackFrame bt1[] = {kRendererMain, kCreateWidget}; |
85 | 177 |
86 // The call tree should look like this (index in brackets). | 178 // The call tree should look like this (index in brackets). |
87 // | 179 // |
88 // BrowserMain [0] | 180 // BrowserMain [1] |
89 // CreateWidget [1] | 181 // CreateWidget [2] |
90 // RendererMain [2] | 182 // RendererMain [3] |
91 // CreateWidget [3] | 183 // CreateWidget [4] |
92 // | 184 // |
93 // Note that there will be two instances of CreateWidget, | 185 // Note that there will be two instances of CreateWidget, |
94 // with different parents. | 186 // with different parents. |
95 | 187 |
96 std::unique_ptr<StackFrameDeduplicator> dedup(new StackFrameDeduplicator); | 188 StringDeduplicator string_dedup; |
97 ASSERT_EQ(1, dedup->Insert(std::begin(bt0), std::end(bt0))); | 189 StackFrameDeduplicator dedup(&string_dedup); |
98 ASSERT_EQ(3, dedup->Insert(std::begin(bt1), std::end(bt1))); | 190 ASSERT_EQ(2, dedup.Insert(std::begin(bt0), std::end(bt0))); |
191 ASSERT_EQ(4, dedup.Insert(std::begin(bt1), std::end(bt1))); | |
99 | 192 |
100 auto iter = dedup->begin(); | 193 auto iter = dedup.begin() + 1; // skip implicit node #0 |
101 ASSERT_EQ(kBrowserMain, (iter + 0)->frame); | 194 ASSERT_EQ(kBrowserMain, (iter + 0)->frame); |
102 ASSERT_EQ(-1, (iter + 0)->parent_frame_index); | 195 ASSERT_EQ(-1, (iter + 0)->parent_frame_index); |
103 | 196 |
104 ASSERT_EQ(kCreateWidget, (iter + 1)->frame); | 197 ASSERT_EQ(kCreateWidget, (iter + 1)->frame); |
105 ASSERT_EQ(0, (iter + 1)->parent_frame_index); | 198 ASSERT_EQ(1, (iter + 1)->parent_frame_index); |
106 | 199 |
107 ASSERT_EQ(kRendererMain, (iter + 2)->frame); | 200 ASSERT_EQ(kRendererMain, (iter + 2)->frame); |
108 ASSERT_EQ(-1, (iter + 2)->parent_frame_index); | 201 ASSERT_EQ(-1, (iter + 2)->parent_frame_index); |
109 | 202 |
110 ASSERT_EQ(kCreateWidget, (iter + 3)->frame); | 203 ASSERT_EQ(kCreateWidget, (iter + 3)->frame); |
111 ASSERT_EQ(2, (iter + 3)->parent_frame_index); | 204 ASSERT_EQ(3, (iter + 3)->parent_frame_index); |
112 | 205 |
113 ASSERT_EQ(iter + 4, dedup->end()); | 206 ASSERT_EQ(iter + 4, dedup.end()); |
114 } | 207 } |
115 | 208 |
116 TEST(StackFrameDeduplicatorTest, Deduplication) { | 209 TEST(StackFrameDeduplicatorTest, Deduplication) { |
117 StackFrame bt0[] = {kBrowserMain, kCreateWidget}; | 210 StackFrame bt0[] = {kBrowserMain, kCreateWidget}; |
118 StackFrame bt1[] = {kBrowserMain, kInitialize}; | 211 StackFrame bt1[] = {kBrowserMain, kInitialize}; |
119 | 212 |
120 // The call tree should look like this (index in brackets). | 213 // The call tree should look like this (index in brackets). |
121 // | 214 // |
122 // BrowserMain [0] | 215 // BrowserMain [1] |
123 // CreateWidget [1] | 216 // CreateWidget [2] |
124 // Initialize [2] | 217 // Initialize [3] |
125 // | 218 // |
126 // Note that BrowserMain will be re-used. | 219 // Note that BrowserMain will be re-used. |
127 | 220 |
128 std::unique_ptr<StackFrameDeduplicator> dedup(new StackFrameDeduplicator); | 221 StringDeduplicator string_dedup; |
129 ASSERT_EQ(1, dedup->Insert(std::begin(bt0), std::end(bt0))); | 222 StackFrameDeduplicator dedup(&string_dedup); |
130 ASSERT_EQ(2, dedup->Insert(std::begin(bt1), std::end(bt1))); | 223 ASSERT_EQ(2, dedup.Insert(std::begin(bt0), std::end(bt0))); |
224 ASSERT_EQ(3, dedup.Insert(std::begin(bt1), std::end(bt1))); | |
131 | 225 |
132 auto iter = dedup->begin(); | 226 auto iter = dedup.begin() + 1; // skip implicit node #0 |
133 ASSERT_EQ(kBrowserMain, (iter + 0)->frame); | 227 ASSERT_EQ(kBrowserMain, (iter + 0)->frame); |
134 ASSERT_EQ(-1, (iter + 0)->parent_frame_index); | 228 ASSERT_EQ(-1, (iter + 0)->parent_frame_index); |
135 | 229 |
136 ASSERT_EQ(kCreateWidget, (iter + 1)->frame); | 230 ASSERT_EQ(kCreateWidget, (iter + 1)->frame); |
137 ASSERT_EQ(0, (iter + 1)->parent_frame_index); | 231 ASSERT_EQ(1, (iter + 1)->parent_frame_index); |
138 | 232 |
139 ASSERT_EQ(kInitialize, (iter + 2)->frame); | 233 ASSERT_EQ(kInitialize, (iter + 2)->frame); |
140 ASSERT_EQ(0, (iter + 2)->parent_frame_index); | 234 ASSERT_EQ(1, (iter + 2)->parent_frame_index); |
141 | 235 |
142 ASSERT_EQ(iter + 3, dedup->end()); | 236 ASSERT_EQ(iter + 3, dedup.end()); |
143 | 237 |
144 // Inserting the same backtrace again should return the index of the existing | 238 // Inserting the same backtrace again should return the index of the existing |
145 // node. | 239 // node. |
146 ASSERT_EQ(1, dedup->Insert(std::begin(bt0), std::end(bt0))); | 240 ASSERT_EQ(2, dedup.Insert(std::begin(bt0), std::end(bt0))); |
147 ASSERT_EQ(2, dedup->Insert(std::begin(bt1), std::end(bt1))); | 241 ASSERT_EQ(3, dedup.Insert(std::begin(bt1), std::end(bt1))); |
148 ASSERT_EQ(dedup->begin() + 3, dedup->end()); | 242 ASSERT_EQ(4 /* 1 implicit + 3 added */, dedup.end() - dedup.begin()); |
243 } | |
244 | |
245 TEST(StackFrameDeduplicatorTest, ExportIncrementally) { | |
246 StringDeduplicator string_dedup; | |
247 StackFrameDeduplicator dedup(&string_dedup); | |
248 | |
249 StackFrame bt0[] = {kBrowserMain, kCreateWidget}; | |
250 ASSERT_EQ(2, dedup.Insert(std::begin(bt0), std::end(bt0))); | |
251 | |
252 ExpectIncrementalEntries( | |
253 &dedup, &string_dedup, | |
254 {{0, kNull}, {1, kBrowserMain}, {2, kCreateWidget, 1}}); | |
255 | |
256 StackFrame bt1[] = {kBrowserMain, kInitialize}; | |
257 ASSERT_EQ(3, dedup.Insert(std::begin(bt1), std::end(bt1))); | |
258 | |
259 ExpectIncrementalEntries(&dedup, &string_dedup, {{3, kInitialize, 1}}); | |
260 | |
261 ExpectIncrementalEntries(&dedup, &string_dedup, {}); | |
149 } | 262 } |
150 | 263 |
151 } // namespace trace_event | 264 } // namespace trace_event |
152 } // namespace base | 265 } // namespace base |
OLD | NEW |