10d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko// Copyright 2015 The Chromium Authors. All rights reserved. 20d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko// Use of this source code is governed by a BSD-style license that can be 30d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko// found in the LICENSE file. 40d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 594ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez#include "base/trace_event/heap_profiler_stack_frame_deduplicator.h" 694ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez 70d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko#include <iterator> 894ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez#include <memory> 90d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 100d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko#include "base/macros.h" 110d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko#include "base/trace_event/heap_profiler_allocation_context.h" 120d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko#include "testing/gtest/include/gtest/gtest.h" 130d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 140d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenkonamespace base { 150d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenkonamespace trace_event { 160d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 170d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko// Define all strings once, because the deduplicator requires pointer equality, 180d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko// and string interning is unreliable. 1994ffa55491333f3dcc701befd0d2652922916d99Luis Hector ChavezStackFrame kBrowserMain = StackFrame::FromTraceEventName("BrowserMain"); 2094ffa55491333f3dcc701befd0d2652922916d99Luis Hector ChavezStackFrame kRendererMain = StackFrame::FromTraceEventName("RendererMain"); 2194ffa55491333f3dcc701befd0d2652922916d99Luis Hector ChavezStackFrame kCreateWidget = StackFrame::FromTraceEventName("CreateWidget"); 2294ffa55491333f3dcc701befd0d2652922916d99Luis Hector ChavezStackFrame kInitialize = StackFrame::FromTraceEventName("Initialize"); 2394ffa55491333f3dcc701befd0d2652922916d99Luis Hector ChavezStackFrame kMalloc = StackFrame::FromTraceEventName("malloc"); 240d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 250d205d712abd16eeed2f5d5b1052a367d23a223fAlex VakulenkoTEST(StackFrameDeduplicatorTest, SingleBacktrace) { 260d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko StackFrame bt[] = {kBrowserMain, kCreateWidget, kMalloc}; 270d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 280d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // The call tree should look like this (index in brackets). 290d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // 300d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // BrowserMain [0] 310d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // CreateWidget [1] 320d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // malloc [2] 330d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 3494ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez std::unique_ptr<StackFrameDeduplicator> dedup(new StackFrameDeduplicator); 350d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(2, dedup->Insert(std::begin(bt), std::end(bt))); 360d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 370d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko auto iter = dedup->begin(); 380d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(kBrowserMain, (iter + 0)->frame); 390d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(-1, (iter + 0)->parent_frame_index); 400d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 410d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(kCreateWidget, (iter + 1)->frame); 420d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(0, (iter + 1)->parent_frame_index); 430d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 440d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(kMalloc, (iter + 2)->frame); 450d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(1, (iter + 2)->parent_frame_index); 460d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 470d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(iter + 3, dedup->end()); 480d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko} 490d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 5094ffa55491333f3dcc701befd0d2652922916d99Luis Hector ChavezTEST(StackFrameDeduplicatorTest, SingleBacktraceWithNull) { 5194ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez StackFrame null_frame = StackFrame::FromTraceEventName(nullptr); 5294ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez StackFrame bt[] = {kBrowserMain, null_frame, kMalloc}; 5394ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez 5494ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez // Deduplicator doesn't care about what's inside StackFrames, 5594ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez // and handles nullptr StackFrame values as any other. 5694ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez // 5794ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez // So the call tree should look like this (index in brackets). 5894ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez // 5994ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez // BrowserMain [0] 6094ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez // (null) [1] 6194ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez // malloc [2] 6294ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez 6394ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez std::unique_ptr<StackFrameDeduplicator> dedup(new StackFrameDeduplicator); 6494ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez ASSERT_EQ(2, dedup->Insert(std::begin(bt), std::end(bt))); 6594ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez 6694ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez auto iter = dedup->begin(); 6794ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez ASSERT_EQ(kBrowserMain, (iter + 0)->frame); 6894ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez ASSERT_EQ(-1, (iter + 0)->parent_frame_index); 6994ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez 7094ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez ASSERT_EQ(null_frame, (iter + 1)->frame); 7194ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez ASSERT_EQ(0, (iter + 1)->parent_frame_index); 7294ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez 7394ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez ASSERT_EQ(kMalloc, (iter + 2)->frame); 7494ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez ASSERT_EQ(1, (iter + 2)->parent_frame_index); 7594ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez 7694ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez ASSERT_EQ(iter + 3, dedup->end()); 7794ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez} 7894ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez 790d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko// Test that there can be different call trees (there can be multiple bottom 800d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko// frames). Also verify that frames with the same name but a different caller 810d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko// are represented as distinct nodes. 820d205d712abd16eeed2f5d5b1052a367d23a223fAlex VakulenkoTEST(StackFrameDeduplicatorTest, MultipleRoots) { 830d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko StackFrame bt0[] = {kBrowserMain, kCreateWidget}; 840d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko StackFrame bt1[] = {kRendererMain, kCreateWidget}; 850d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 860d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // The call tree should look like this (index in brackets). 870d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // 880d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // BrowserMain [0] 890d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // CreateWidget [1] 900d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // RendererMain [2] 910d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // CreateWidget [3] 920d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // 930d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // Note that there will be two instances of CreateWidget, 940d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // with different parents. 950d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 9694ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez std::unique_ptr<StackFrameDeduplicator> dedup(new StackFrameDeduplicator); 970d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(1, dedup->Insert(std::begin(bt0), std::end(bt0))); 980d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(3, dedup->Insert(std::begin(bt1), std::end(bt1))); 990d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 1000d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko auto iter = dedup->begin(); 1010d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(kBrowserMain, (iter + 0)->frame); 1020d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(-1, (iter + 0)->parent_frame_index); 1030d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 1040d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(kCreateWidget, (iter + 1)->frame); 1050d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(0, (iter + 1)->parent_frame_index); 1060d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 1070d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(kRendererMain, (iter + 2)->frame); 1080d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(-1, (iter + 2)->parent_frame_index); 1090d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 1100d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(kCreateWidget, (iter + 3)->frame); 1110d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(2, (iter + 3)->parent_frame_index); 1120d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 1130d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(iter + 4, dedup->end()); 1140d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko} 1150d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 1160d205d712abd16eeed2f5d5b1052a367d23a223fAlex VakulenkoTEST(StackFrameDeduplicatorTest, Deduplication) { 1170d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko StackFrame bt0[] = {kBrowserMain, kCreateWidget}; 1180d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko StackFrame bt1[] = {kBrowserMain, kInitialize}; 1190d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 1200d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // The call tree should look like this (index in brackets). 1210d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // 1220d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // BrowserMain [0] 1230d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // CreateWidget [1] 1240d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // Initialize [2] 1250d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // 1260d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // Note that BrowserMain will be re-used. 1270d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 12894ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez std::unique_ptr<StackFrameDeduplicator> dedup(new StackFrameDeduplicator); 1290d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(1, dedup->Insert(std::begin(bt0), std::end(bt0))); 1300d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(2, dedup->Insert(std::begin(bt1), std::end(bt1))); 1310d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 1320d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko auto iter = dedup->begin(); 1330d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(kBrowserMain, (iter + 0)->frame); 1340d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(-1, (iter + 0)->parent_frame_index); 1350d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 1360d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(kCreateWidget, (iter + 1)->frame); 1370d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(0, (iter + 1)->parent_frame_index); 1380d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 1390d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(kInitialize, (iter + 2)->frame); 1400d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(0, (iter + 2)->parent_frame_index); 1410d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 1420d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(iter + 3, dedup->end()); 1430d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 1440d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // Inserting the same backtrace again should return the index of the existing 1450d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // node. 1460d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(1, dedup->Insert(std::begin(bt0), std::end(bt0))); 1470d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(2, dedup->Insert(std::begin(bt1), std::end(bt1))); 1480d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko ASSERT_EQ(dedup->begin() + 3, dedup->end()); 1490d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko} 1500d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 1510d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko} // namespace trace_event 1520d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko} // namespace base 153