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