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#ifndef BASE_TRACE_EVENT_HEAP_PROFILER_STACK_FRAME_DEDUPLICATOR_H_
6#define BASE_TRACE_EVENT_HEAP_PROFILER_STACK_FRAME_DEDUPLICATOR_H_
7
8#include <map>
9#include <string>
10#include <vector>
11
12#include "base/base_export.h"
13#include "base/macros.h"
14#include "base/trace_event/heap_profiler_allocation_context.h"
15#include "base/trace_event/trace_event_impl.h"
16
17namespace base {
18namespace trace_event {
19
20class TraceEventMemoryOverhead;
21
22// A data structure that allows grouping a set of backtraces in a space-
23// efficient manner by creating a call tree and writing it as a set of (node,
24// parent) pairs. The tree nodes reference both parent and children. The parent
25// is referenced by index into |frames_|. The children are referenced via a map
26// of |StackFrame|s to index into |frames_|. So there is a trie for bottum-up
27// lookup of a backtrace for deduplication, and a tree for compact storage in
28// the trace log.
29class BASE_EXPORT StackFrameDeduplicator : public ConvertableToTraceFormat {
30 public:
31  // A node in the call tree.
32  struct FrameNode {
33    FrameNode(StackFrame frame, int parent_frame_index);
34    FrameNode(const FrameNode& other);
35    ~FrameNode();
36
37    StackFrame frame;
38
39    // The index of the parent stack frame in |frames_|, or -1 if there is no
40    // parent frame (when it is at the bottom of the call stack).
41    int parent_frame_index;
42
43    // Indices into |frames_| of frames called from the current frame.
44    std::map<StackFrame, int> children;
45  };
46
47  using ConstIterator = std::vector<FrameNode>::const_iterator;
48
49  StackFrameDeduplicator();
50  ~StackFrameDeduplicator() override;
51
52  // Inserts a backtrace where |beginFrame| is a pointer to the bottom frame
53  // (e.g. main) and |endFrame| is a pointer past the top frame (most recently
54  // called function), and returns the index of its leaf node in |frames_|.
55  // Returns -1 if the backtrace is empty.
56  int Insert(const StackFrame* beginFrame, const StackFrame* endFrame);
57
58  // Iterators over the frame nodes in the call tree.
59  ConstIterator begin() const { return frames_.begin(); }
60  ConstIterator end() const { return frames_.end(); }
61
62  // Writes the |stackFrames| dictionary as defined in https://goo.gl/GerkV8 to
63  // the trace log.
64  void AppendAsTraceFormat(std::string* out) const override;
65
66  // Estimates memory overhead including |sizeof(StackFrameDeduplicator)|.
67  void EstimateTraceMemoryOverhead(TraceEventMemoryOverhead* overhead) override;
68
69 private:
70  std::map<StackFrame, int> roots_;
71  std::vector<FrameNode> frames_;
72
73  DISALLOW_COPY_AND_ASSIGN(StackFrameDeduplicator);
74};
75
76}  // namespace trace_event
77}  // namespace base
78
79#endif  // BASE_TRACE_EVENT_HEAP_PROFILER_STACK_FRAME_DEDUPLICATOR_H_
80