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