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
3// found in the LICENSE file.
4
5#include "base/trace_event/heap_profiler_stack_frame_deduplicator.h"
6
7#include <iterator>
8#include <memory>
9
10#include "base/macros.h"
11#include "base/trace_event/heap_profiler_allocation_context.h"
12#include "testing/gtest/include/gtest/gtest.h"
13
14namespace base {
15namespace trace_event {
16
17// Define all strings once, because the deduplicator requires pointer equality,
18// and string interning is unreliable.
19StackFrame kBrowserMain = StackFrame::FromTraceEventName("BrowserMain");
20StackFrame kRendererMain = StackFrame::FromTraceEventName("RendererMain");
21StackFrame kCreateWidget = StackFrame::FromTraceEventName("CreateWidget");
22StackFrame kInitialize = StackFrame::FromTraceEventName("Initialize");
23StackFrame kMalloc = StackFrame::FromTraceEventName("malloc");
24
25TEST(StackFrameDeduplicatorTest, SingleBacktrace) {
26  StackFrame bt[] = {kBrowserMain, kCreateWidget, kMalloc};
27
28  // The call tree should look like this (index in brackets).
29  //
30  // BrowserMain [0]
31  //   CreateWidget [1]
32  //     malloc [2]
33
34  std::unique_ptr<StackFrameDeduplicator> dedup(new StackFrameDeduplicator);
35  ASSERT_EQ(2, dedup->Insert(std::begin(bt), std::end(bt)));
36
37  auto iter = dedup->begin();
38  ASSERT_EQ(kBrowserMain, (iter + 0)->frame);
39  ASSERT_EQ(-1, (iter + 0)->parent_frame_index);
40
41  ASSERT_EQ(kCreateWidget, (iter + 1)->frame);
42  ASSERT_EQ(0, (iter + 1)->parent_frame_index);
43
44  ASSERT_EQ(kMalloc, (iter + 2)->frame);
45  ASSERT_EQ(1, (iter + 2)->parent_frame_index);
46
47  ASSERT_EQ(iter + 3, dedup->end());
48}
49
50TEST(StackFrameDeduplicatorTest, SingleBacktraceWithNull) {
51  StackFrame null_frame = StackFrame::FromTraceEventName(nullptr);
52  StackFrame bt[] = {kBrowserMain, null_frame, kMalloc};
53
54  // Deduplicator doesn't care about what's inside StackFrames,
55  // and handles nullptr StackFrame values as any other.
56  //
57  // So the call tree should look like this (index in brackets).
58  //
59  // BrowserMain [0]
60  //   (null) [1]
61  //     malloc [2]
62
63  std::unique_ptr<StackFrameDeduplicator> dedup(new StackFrameDeduplicator);
64  ASSERT_EQ(2, dedup->Insert(std::begin(bt), std::end(bt)));
65
66  auto iter = dedup->begin();
67  ASSERT_EQ(kBrowserMain, (iter + 0)->frame);
68  ASSERT_EQ(-1, (iter + 0)->parent_frame_index);
69
70  ASSERT_EQ(null_frame, (iter + 1)->frame);
71  ASSERT_EQ(0, (iter + 1)->parent_frame_index);
72
73  ASSERT_EQ(kMalloc, (iter + 2)->frame);
74  ASSERT_EQ(1, (iter + 2)->parent_frame_index);
75
76  ASSERT_EQ(iter + 3, dedup->end());
77}
78
79// 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
81// are represented as distinct nodes.
82TEST(StackFrameDeduplicatorTest, MultipleRoots) {
83  StackFrame bt0[] = {kBrowserMain, kCreateWidget};
84  StackFrame bt1[] = {kRendererMain, kCreateWidget};
85
86  // The call tree should look like this (index in brackets).
87  //
88  // BrowserMain [0]
89  //   CreateWidget [1]
90  // RendererMain [2]
91  //   CreateWidget [3]
92  //
93  // Note that there will be two instances of CreateWidget,
94  // with different parents.
95
96  std::unique_ptr<StackFrameDeduplicator> dedup(new StackFrameDeduplicator);
97  ASSERT_EQ(1, dedup->Insert(std::begin(bt0), std::end(bt0)));
98  ASSERT_EQ(3, dedup->Insert(std::begin(bt1), std::end(bt1)));
99
100  auto iter = dedup->begin();
101  ASSERT_EQ(kBrowserMain, (iter + 0)->frame);
102  ASSERT_EQ(-1, (iter + 0)->parent_frame_index);
103
104  ASSERT_EQ(kCreateWidget, (iter + 1)->frame);
105  ASSERT_EQ(0, (iter + 1)->parent_frame_index);
106
107  ASSERT_EQ(kRendererMain, (iter + 2)->frame);
108  ASSERT_EQ(-1, (iter + 2)->parent_frame_index);
109
110  ASSERT_EQ(kCreateWidget, (iter + 3)->frame);
111  ASSERT_EQ(2, (iter + 3)->parent_frame_index);
112
113  ASSERT_EQ(iter + 4, dedup->end());
114}
115
116TEST(StackFrameDeduplicatorTest, Deduplication) {
117  StackFrame bt0[] = {kBrowserMain, kCreateWidget};
118  StackFrame bt1[] = {kBrowserMain, kInitialize};
119
120  // The call tree should look like this (index in brackets).
121  //
122  // BrowserMain [0]
123  //   CreateWidget [1]
124  //   Initialize [2]
125  //
126  // Note that BrowserMain will be re-used.
127
128  std::unique_ptr<StackFrameDeduplicator> dedup(new StackFrameDeduplicator);
129  ASSERT_EQ(1, dedup->Insert(std::begin(bt0), std::end(bt0)));
130  ASSERT_EQ(2, dedup->Insert(std::begin(bt1), std::end(bt1)));
131
132  auto iter = dedup->begin();
133  ASSERT_EQ(kBrowserMain, (iter + 0)->frame);
134  ASSERT_EQ(-1, (iter + 0)->parent_frame_index);
135
136  ASSERT_EQ(kCreateWidget, (iter + 1)->frame);
137  ASSERT_EQ(0, (iter + 1)->parent_frame_index);
138
139  ASSERT_EQ(kInitialize, (iter + 2)->frame);
140  ASSERT_EQ(0, (iter + 2)->parent_frame_index);
141
142  ASSERT_EQ(iter + 3, dedup->end());
143
144  // Inserting the same backtrace again should return the index of the existing
145  // node.
146  ASSERT_EQ(1, dedup->Insert(std::begin(bt0), std::end(bt0)));
147  ASSERT_EQ(2, dedup->Insert(std::begin(bt1), std::end(bt1)));
148  ASSERT_EQ(dedup->begin() + 3, dedup->end());
149}
150
151}  // namespace trace_event
152}  // namespace base
153