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)) { |
| 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 |