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