blob: 351117f14f76888061cd57cb338c31ae2ac0fc69 [file] [log] [blame]
// 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.
#include "base/trace_event/heap_profiler_stack_frame_deduplicator.h"
#include <inttypes.h>
#include <stddef.h>
#include <algorithm>
#include <string>
#include <utility>
#include "base/hash.h"
#include "base/strings/stringprintf.h"
#include "base/trace_event/memory_usage_estimator.h"
#include "base/trace_event/trace_event.h"
#include "base/trace_event/trace_event_argument.h"
#include "base/trace_event/trace_event_memory_overhead.h"
namespace base {
namespace trace_event {
namespace {
// Dumb hash function that nevertheless works surprisingly well and
// produces ~0 collisions on real backtraces.
size_t HashBacktrace(const StackFrame* begin, const StackFrame* end) {
size_t hash = 0;
for (; begin != end; begin++) {
hash += reinterpret_cast<uintptr_t>(begin->value);
}
return hash;
}
} // namespace
StackFrameDeduplicator::FrameNode::FrameNode(StackFrame frame,
int parent_frame_index)
: frame(frame), parent_frame_index(parent_frame_index) {}
StackFrameDeduplicator::FrameNode::FrameNode(const FrameNode& other) = default;
StackFrameDeduplicator::FrameNode::~FrameNode() {}
size_t StackFrameDeduplicator::FrameNode::EstimateMemoryUsage() const {
return base::trace_event::EstimateMemoryUsage(children);
}
StackFrameDeduplicator::StackFrameDeduplicator() {}
StackFrameDeduplicator::~StackFrameDeduplicator() {}
bool StackFrameDeduplicator::Match(int frame_index,
const StackFrame* begin_frame,
const StackFrame* end_frame) const {
// |frame_index| identifies the bottom frame, i.e. we need to walk
// backtrace backwards.
const StackFrame* current_frame = end_frame - 1;
for (; current_frame >= begin_frame; --current_frame) {
const FrameNode& node = frames_[frame_index];
if (node.frame != *current_frame) {
break;
}
frame_index = node.parent_frame_index;
if (frame_index == FrameNode::kInvalidFrameIndex) {
if (current_frame == begin_frame) {
// We're at the top node and we matched all backtrace frames,
// i.e. we successfully matched the backtrace.
return true;
}
break;
}
}
return false;
}
int StackFrameDeduplicator::Insert(const StackFrame* begin_frame,
const StackFrame* end_frame) {
if (begin_frame == end_frame) {
return FrameNode::kInvalidFrameIndex;
}
size_t backtrace_hash = HashBacktrace(begin_frame, end_frame);
// Check if we know about this backtrace.
auto backtrace_it = backtrace_lookup_table_.find(backtrace_hash);
if (backtrace_it != backtrace_lookup_table_.end()) {
int backtrace_index = backtrace_it->second;
if (Match(backtrace_index, begin_frame, end_frame)) {
return backtrace_index;
}
}
int frame_index = FrameNode::kInvalidFrameIndex;
base::flat_map<StackFrame, int>* nodes = &roots_;
// Loop through the frames, early out when a frame is null.
for (const StackFrame* it = begin_frame; it != end_frame; it++) {
StackFrame frame = *it;
auto node = nodes->find(frame);
if (node == nodes->end()) {
// There is no tree node for this frame yet, create it. The parent node
// is the node associated with the previous frame.
FrameNode frame_node(frame, frame_index);
// The new frame node will be appended, so its index is the current size
// of the vector.
frame_index = static_cast<int>(frames_.size());
// Add the node to the trie so it will be found next time.
nodes->insert(std::make_pair(frame, frame_index));
// Append the node after modifying |nodes|, because the |frames_| vector
// might need to resize, and this invalidates the |nodes| pointer.
frames_.push_back(frame_node);
} else {
// A tree node for this frame exists. Look for the next one.
frame_index = node->second;
}
nodes = &frames_[frame_index].children;
}
// Remember the backtrace.
backtrace_lookup_table_[backtrace_hash] = frame_index;
return frame_index;
}
void StackFrameDeduplicator::AppendAsTraceFormat(std::string* out) const {
TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("memory-infra"),
"StackFrameDeduplicator::AppendAsTraceFormat");
out->append("{"); // Begin the |stackFrames| dictionary.
int i = 0;
auto frame_node = begin();
auto it_end = end();
std::string stringify_buffer;
while (frame_node != it_end) {
// The |stackFrames| format is a dictionary, not an array, so the
// keys are stringified indices. Write the index manually, then use
// |TracedValue| to format the object. This is to avoid building the
// entire dictionary as a |TracedValue| in memory.
SStringPrintf(&stringify_buffer, "\"%d\":", i);
out->append(stringify_buffer);
std::unique_ptr<TracedValue> frame_node_value(new TracedValue);
const StackFrame& frame = frame_node->frame;
switch (frame.type) {
case StackFrame::Type::TRACE_EVENT_NAME:
frame_node_value->SetString("name",
static_cast<const char*>(frame.value));
break;
case StackFrame::Type::THREAD_NAME:
SStringPrintf(&stringify_buffer,
"[Thread: %s]",
static_cast<const char*>(frame.value));
frame_node_value->SetString("name", stringify_buffer);
break;
case StackFrame::Type::PROGRAM_COUNTER:
SStringPrintf(&stringify_buffer,
"pc:%" PRIxPTR,
reinterpret_cast<uintptr_t>(frame.value));
frame_node_value->SetString("name", stringify_buffer);
break;
}
if (frame_node->parent_frame_index != FrameNode::kInvalidFrameIndex) {
SStringPrintf(&stringify_buffer, "%d", frame_node->parent_frame_index);
frame_node_value->SetString("parent", stringify_buffer);
}
frame_node_value->AppendAsTraceFormat(out);
i++;
frame_node++;
if (frame_node != it_end)
out->append(",");
}
out->append("}"); // End the |stackFrames| dictionary.
}
void StackFrameDeduplicator::EstimateTraceMemoryOverhead(
TraceEventMemoryOverhead* overhead) {
size_t memory_usage = EstimateMemoryUsage(frames_) +
EstimateMemoryUsage(roots_) +
EstimateMemoryUsage(backtrace_lookup_table_);
overhead->Add(TraceEventMemoryOverhead::kHeapProfilerStackFrameDeduplicator,
sizeof(StackFrameDeduplicator) + memory_usage);
}
} // namespace trace_event
} // namespace base