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 <stddef.h>
8
9 #include <string>
10 #include <utility>
11
12 #include "base/strings/stringprintf.h"
13 #include "base/trace_event/trace_event_argument.h"
14 #include "base/trace_event/trace_event_memory_overhead.h"
15
16 namespace base {
17 namespace trace_event {
18
FrameNode(StackFrame frame,int parent_frame_index)19 StackFrameDeduplicator::FrameNode::FrameNode(StackFrame frame,
20 int parent_frame_index)
21 : frame(frame), parent_frame_index(parent_frame_index) {}
~FrameNode()22 StackFrameDeduplicator::FrameNode::~FrameNode() {}
23
StackFrameDeduplicator()24 StackFrameDeduplicator::StackFrameDeduplicator() {}
~StackFrameDeduplicator()25 StackFrameDeduplicator::~StackFrameDeduplicator() {}
26
Insert(const StackFrame * beginFrame,const StackFrame * endFrame)27 int StackFrameDeduplicator::Insert(const StackFrame* beginFrame,
28 const StackFrame* endFrame) {
29 int frame_index = -1;
30 std::map<StackFrame, int>* nodes = &roots_;
31
32 // Loop through the frames, early out when a frame is null.
33 for (const StackFrame* it = beginFrame; it != endFrame && *it; it++) {
34 StackFrame frame = *it;
35
36 auto node = nodes->find(frame);
37 if (node == nodes->end()) {
38 // There is no tree node for this frame yet, create it. The parent node
39 // is the node associated with the previous frame.
40 FrameNode frame_node(frame, frame_index);
41
42 // The new frame node will be appended, so its index is the current size
43 // of the vector.
44 frame_index = static_cast<int>(frames_.size());
45
46 // Add the node to the trie so it will be found next time.
47 nodes->insert(std::make_pair(frame, frame_index));
48
49 // Append the node after modifying |nodes|, because the |frames_| vector
50 // might need to resize, and this invalidates the |nodes| pointer.
51 frames_.push_back(frame_node);
52 } else {
53 // A tree node for this frame exists. Look for the next one.
54 frame_index = node->second;
55 }
56
57 nodes = &frames_[frame_index].children;
58 }
59
60 return frame_index;
61 }
62
AppendAsTraceFormat(std::string * out) const63 void StackFrameDeduplicator::AppendAsTraceFormat(std::string* out) const {
64 out->append("{"); // Begin the |stackFrames| dictionary.
65
66 int i = 0;
67 auto frame_node = begin();
68 auto it_end = end();
69 std::string stringify_buffer;
70
71 while (frame_node != it_end) {
72 // The |stackFrames| format is a dictionary, not an array, so the
73 // keys are stringified indices. Write the index manually, then use
74 // |TracedValue| to format the object. This is to avoid building the
75 // entire dictionary as a |TracedValue| in memory.
76 SStringPrintf(&stringify_buffer, "\"%d\":", i);
77 out->append(stringify_buffer);
78
79 scoped_refptr<TracedValue> frame_node_value = new TracedValue;
80 frame_node_value->SetString("name", frame_node->frame);
81 if (frame_node->parent_frame_index >= 0) {
82 SStringPrintf(&stringify_buffer, "%d", frame_node->parent_frame_index);
83 frame_node_value->SetString("parent", stringify_buffer);
84 }
85 frame_node_value->AppendAsTraceFormat(out);
86
87 i++;
88 frame_node++;
89
90 if (frame_node != it_end)
91 out->append(",");
92 }
93
94 out->append("}"); // End the |stackFrames| dictionary.
95 }
96
EstimateTraceMemoryOverhead(TraceEventMemoryOverhead * overhead)97 void StackFrameDeduplicator::EstimateTraceMemoryOverhead(
98 TraceEventMemoryOverhead* overhead) {
99 // The sizes here are only estimates; they fail to take into account the
100 // overhead of the tree nodes for the map, but as an estimate this should be
101 // fine.
102 size_t maps_size = roots_.size() * sizeof(std::pair<StackFrame, int>);
103 size_t frames_allocated = frames_.capacity() * sizeof(FrameNode);
104 size_t frames_resident = frames_.size() * sizeof(FrameNode);
105
106 for (const FrameNode& node : frames_)
107 maps_size += node.children.size() * sizeof(std::pair<StackFrame, int>);
108
109 overhead->Add("StackFrameDeduplicator",
110 sizeof(StackFrameDeduplicator) + maps_size + frames_allocated,
111 sizeof(StackFrameDeduplicator) + maps_size + frames_resident);
112 }
113
114 } // namespace trace_event
115 } // namespace base
116