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