blob: b7780495c65a7ec0e639f18f73423fd6494ac127 [file] [log] [blame]
// Copyright 2017 Google Inc. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#include "cobalt/browser/memory_tracker/tool/leak_finder_tool.h"
#include <algorithm>
#include <iomanip>
#include <map>
#include <utility>
#include "base/timer.h"
#include "cobalt/browser/memory_tracker/tool/params.h"
#include "cobalt/browser/memory_tracker/tool/tool_impl.h"
#include "cobalt/browser/memory_tracker/tool/util.h"
#include "cobalt/script/util/stack_trace_helpers.h"
#include "nb/memory_scope.h"
#include "starboard/string.h"
namespace cobalt {
namespace browser {
namespace memory_tracker {
LeakFinderTool::LeakFinderTool(StackTraceMode mode)
: string_pool_(128),
frame_map_(128),
callframe_map_(128),
stack_trace_mode_(mode) {
default_callframe_str_ = &string_pool_.Intern("<Unknown>");
}
LeakFinderTool::~LeakFinderTool() {
frame_map_.Clear();
callframe_map_.Clear();
}
bool LeakFinderTool::IsJavascriptScope(
const nb::analytics::CallStack& callstack) {
// March through all MemoryScopes in the callstack and check if any of them
// contains a javascript scope. If it does return true.
for (nb::analytics::CallStack::const_iterator it = callstack.begin();
it != callstack.end(); ++it) {
const NbMemoryScopeInfo* memory_scope = *it;
const bool is_javascript_scope =
SbStringFindString(memory_scope->memory_scope_name_, "Javascript");
if (is_javascript_scope) {
return true;
}
}
return false;
}
void LeakFinderTool::OnMemoryAllocation(
const void* memory_block, const nb::analytics::AllocationRecord& record,
const nb::analytics::CallStack& callstack) {
// When in javascript mode, filter only allocations with "Javascript" in
// the memory scope name.
if (stack_trace_mode_ == kJavascript) {
if (!IsJavascriptScope(callstack)) {
return;
}
}
// symbol_str can be used as a unique key. The same value of callstack will
// always produce the same string pointer.
const std::string* symbol_str = GetOrCreateSymbol(callstack);
// Track the allocation.
if (!callframe_map_.SetIfMissing(memory_block, symbol_str)) {
CallFrameMap::EntryHandle entry_handle;
callframe_map_.Get(memory_block, &entry_handle);
const void* ptr = entry_handle.Valid() ? entry_handle.Key() : NULL;
entry_handle.ReleaseLockAndInvalidate();
DCHECK(false) << "Unexpected memory block at " << memory_block
<< " already existed as: " << ptr;
}
AllocationFrameMap::EntryHandle entry_handle;
frame_map_.GetOrCreate(symbol_str, &entry_handle);
// While this entry_handle is in use, no other threads
// can modify this entry.
AllocRec& alloc_rec = entry_handle.ValueMutable();
alloc_rec.total_bytes += record.size;
alloc_rec.num_allocs++;
}
void LeakFinderTool::OnMemoryDeallocation(
const void* memory_block, const nb::analytics::AllocationRecord& record,
const nb::analytics::CallStack& callstack) {
UNREFERENCED_PARAMETER(callstack);
const std::string* symbol_str = NULL;
{
CallFrameMap::EntryHandle entry_handle;
if (!callframe_map_.Get(memory_block, &entry_handle)) {
// This happens if the allocation happened before this tool attached
// to the memory tracker or if the memory allocation was filtered and
// therefore isn't being tracked.
return;
}
symbol_str = entry_handle.Value();
callframe_map_.Remove(&entry_handle);
}
// This case can happen if the memory tracker attaches after the allocation.
if (!symbol_str) {
return;
}
AllocationFrameMap::EntryHandle entry_handle;
frame_map_.GetOrCreate(symbol_str, &entry_handle);
// While entry_handle is in use, no other element can modify
// this element.
AllocRec& alloc_rec = entry_handle.ValueMutable();
alloc_rec.total_bytes -= record.size;
alloc_rec.num_allocs--;
}
std::string LeakFinderTool::tool_name() const {
return "MemoryTrackerLeakFinder";
}
void LeakFinderTool::Run(Params* params) {
// Run function does almost nothing.
params->logger()->Output("MemoryTrackerLeakFinder running...");
static const size_t kMaxSamples = 400;
// This value will decay whenever the buffer fills up and is compressed via
// sample elimination.
SbTime sample_time = 50; // 50 microseconds.
std::vector<base::TimeDelta> time_values;
std::map<const std::string*, std::vector<AllocRec> > map_allocations;
SbTime start_time = SbTimeGetMonotonicNow();
Timer output_trigger(base::TimeDelta::FromMinutes(1));
const double recording_delay_mins = 5.0;
// Controls how often an update status message is sent to output.
Timer output_status_timer(base::TimeDelta::FromSeconds(1));
while (true) {
if (params->wait_for_finish_signal(sample_time)) {
break; // Finish received, break.
}
SbTime now_time = SbTimeGetMonotonicNow();
const base::TimeDelta time_since_start =
base::Time::FromSbTime(now_time) - base::Time::FromSbTime(start_time);
// DELAY RECORDING AS STARTUP MEMORY IS INITIALIZED
// Cleaner graphs if we wait until after startup.
//
const double times_since_start_mins = time_since_start.InSecondsF() / 60.0;
if (times_since_start_mins < recording_delay_mins) {
if (output_status_timer.UpdateAndIsExpired()) {
double remaining_time_mins =
(recording_delay_mins - times_since_start_mins);
std::stringstream ss;
ss << "MemoryTrackerLeakFinder starting in " << remaining_time_mins
<< " minutes.\n";
params->logger()->Output(ss.str().c_str());
}
continue;
}
time_values.push_back(time_since_start);
// To improve performance, make a copy of the values to a vector on
// the stack.
std::vector<std::pair<const std::string*, AllocRec> > samples;
SampleSnapshot(&samples);
// Take a snapshot.
for (size_t i = 0; i < samples.size(); ++i) {
std::pair<const std::string*, AllocRec> sample = samples[i];
std::vector<AllocRec>& sample_history = map_allocations[sample.first];
sample_history.resize(time_values.size());
sample_history.back() = sample.second;
}
if (output_trigger.UpdateAndIsExpired() && time_values.size() > 10) {
// Timer expired so dump the current information output.
std::vector<AllocationProfile> alloc_profiles;
GenerateTopLeakingAllocationProfiles(time_values, map_allocations,
&alloc_profiles);
if (alloc_profiles.empty()) {
params->logger()->Output(
"MemoryTrackerLeakFinder: alloc_profiles was "
"empty and nothing is written.");
} else {
if (alloc_profiles.size() > 20) {
alloc_profiles.resize(20);
}
std::string csv_str = GenerateCSV(time_values, alloc_profiles);
params->logger()->Output(csv_str.c_str());
}
}
// Compress the buffer, and modify sample_time so that it's twice as slow.
if (time_values.size() >= kMaxSamples) {
sample_time *= 2; // Double the time that it takes to trigger a sample.
// Remove every other element in time_values.
RemoveOddElements(&time_values);
// Remove every other element in the samples.
for (size_t i = 0; i < samples.size(); ++i) {
std::pair<const std::string*, AllocRec> sample = samples[i];
std::vector<AllocRec>& sample_history = map_allocations[sample.first];
RemoveOddElements(&sample_history);
}
}
}
}
const std::string* LeakFinderTool::GetOrCreateSymbol(
const nb::analytics::CallStack& callstack) {
const std::string* symbol_str = NULL;
// In javascript mode we try and get the javascript symbol. Otherwise
// fallback to C++ symbol.
if (stack_trace_mode_ == kJavascript) {
symbol_str = TryGetJavascriptSymbol();
if (symbol_str) {
return symbol_str;
}
}
symbol_str = GetOrCreateCplusPlusSymbol(callstack);
return symbol_str;
}
const std::string* LeakFinderTool::GetOrCreateCplusPlusSymbol(
const nb::analytics::CallStack& callstack) {
if (callstack.empty()) {
return default_callframe_str_;
} else {
const NbMemoryScopeInfo* memory_scope = callstack.back();
const bool skip =
SbStringFindString(memory_scope->function_name_, "js_malloc") ||
SbStringFindString(memory_scope->function_name_, "js_realloc") ||
SbStringFindString(memory_scope->function_name_, "new_");
// Skip up one callstack because we don't want to track calls to
// allocation functions.
if (skip && callstack.size() > 1) {
memory_scope = callstack[callstack.size() - 2];
}
const char* file_name = BaseNameFast(memory_scope->file_name_);
// Generates a symbol.
// Example:
// "Javascript:Interpreter.cpp(415):RunScript()"
char symbol_buff[128];
SbStringFormatF(symbol_buff, sizeof(symbol_buff), "%s:%s(%d)::%s()",
memory_scope->memory_scope_name_, file_name,
memory_scope->line_number_, memory_scope->function_name_);
// Get's a unique pointer to a string containing the symbol. If the symbol
// was previously generated then the previous symbol is returned.
return &string_pool_.Intern(symbol_buff);
}
}
const std::string* LeakFinderTool::TryGetJavascriptSymbol() {
auto* js_stack_gen = script::util::GetThreadLocalStackTraceGenerator();
if (!js_stack_gen || !js_stack_gen->Valid()) {
return NULL;
}
// Only get one symbol.
char buffer[256];
if (!js_stack_gen->GenerateStackTraceString(1, buffer, sizeof(buffer))) {
return NULL;
}
const char* file_name = BaseNameFast(buffer);
return &string_pool_.Intern(file_name);
}
void LeakFinderTool::SampleSnapshot(
std::vector<std::pair<const std::string*, AllocRec> >* destination) {
destination->erase(destination->begin(), destination->end());
const size_t sample_size = frame_map_.GetSize();
// Do this locally.
destination->reserve(sample_size + 10);
frame_map_.CopyToStdVector(destination);
}
std::string LeakFinderTool::GenerateCSV(
const std::vector<base::TimeDelta>& time_values,
const std::vector<AllocationProfile>& data) {
std::stringstream ss;
ss << std::fixed; // Turn off scientific notation for CSV values.
ss << std::setprecision(3);
ss << kNewLine << kNewLine;
// HEADER
ss << "// Allocation in megabytes." << kNewLine;
ss << kQuote << "Time(min)" << kQuote << kDelimiter;
for (size_t i = 0; i < data.size(); ++i) {
const AllocationProfile& alloc_profile = data[i];
const std::string& name = *alloc_profile.name_;
ss << kQuote << name << kQuote << kDelimiter;
}
ss << kNewLine;
// BODY
for (size_t i = 0; i < time_values.size(); ++i) {
for (size_t j = 0; j < data.size(); ++j) {
if (j == 0) {
double mins = time_values[i].InSecondsF() / 60.f;
if (mins < .001) {
mins = 0;
}
ss << mins << kDelimiter;
}
const AllocationProfile& alloc_profile = data[j];
const std::vector<AllocRec>& alloc_history =
*alloc_profile.alloc_history_;
double megabytes = static_cast<double>(alloc_history[i].total_bytes) /
static_cast<double>(1024 * 1024);
DCHECK_EQ(alloc_history.size(), time_values.size());
ss << megabytes << kDelimiter;
}
ss << kNewLine;
}
ss << kNewLine << kNewLine;
ss << "// Object counts." << kNewLine;
ss << kQuote << "Time(min)" << kQuote << kDelimiter;
for (size_t i = 0; i < data.size(); ++i) {
const AllocationProfile& alloc_profile = data[i];
const std::string& name = *alloc_profile.name_;
ss << kQuote << name << kQuote << kDelimiter;
}
ss << kNewLine;
for (size_t i = 0; i < time_values.size(); ++i) {
for (size_t j = 0; j < data.size(); ++j) {
if (j == 0) {
double mins = time_values[i].InSecondsF() / 60.f;
if (mins < .001) {
mins = 0;
}
ss << mins << kDelimiter;
}
const AllocationProfile& alloc_profile = data[j];
const std::vector<AllocRec>& alloc_history =
*alloc_profile.alloc_history_;
DCHECK_EQ(alloc_history.size(), time_values.size());
ss << alloc_history[i].num_allocs << kDelimiter;
}
ss << kNewLine;
}
ss << kNewLine << kNewLine;
return ss.str();
}
void LeakFinderTool::GenerateTopLeakingAllocationProfiles(
const std::vector<base::TimeDelta>& time_values, const MapSamples& samples,
std::vector<AllocationProfile>* destination) {
// GENERATE LINEAR REGRESSION LINE
// first value is time in microseconds.
// second value is total_bytes.
std::vector<std::pair<int64_t, int64_t> > sample_data;
typedef std::map<const std::string*, SlopeYIntercept> LinearRegressionMap;
LinearRegressionMap linear_regression_map;
std::vector<AllocationProfile> allocation_profiles;
for (MapSamples::const_iterator it = samples.begin(); it != samples.end();
++it) {
const std::string* allocation_name = it->first;
const std::vector<AllocRec>& allocation_samples = it->second;
if (allocation_samples.empty()) {
continue;
}
// Filter out allocations records that have low number of allocations.
if (allocation_samples.back().num_allocs < 10) {
continue;
}
// Filter out allocations that are insignificant.
int64_t largest_allocation_sample = 0;
const int64_t kMinAllocationSize = 1024 * 64;
for (size_t i = 0; i < allocation_samples.size(); ++i) {
int64_t bytes = allocation_samples[i].total_bytes;
largest_allocation_sample = std::max(largest_allocation_sample, bytes);
}
if (largest_allocation_sample < kMinAllocationSize) {
continue;
}
// Filter out allocations where there is no growth between first quartile
// and final output.
const AllocRec& first_quartile_sample =
allocation_samples[allocation_samples.size() / 4];
const AllocRec& final_sample = allocation_samples.back();
const double increase_ratio =
static_cast<double>(final_sample.total_bytes) /
static_cast<double>(first_quartile_sample.total_bytes);
// 5% threshold of increase to be qualified as a lead.
static const double kMinIncreaseThreshold = .05;
// If the increase between first quartile and final sample less than 5%
// then skip.
if (increase_ratio < kMinIncreaseThreshold) {
continue;
}
sample_data.clear(); // Recycle.
for (size_t i = 0; i < time_values.size(); ++i) {
std::pair<int64_t, int64_t> datum(time_values[i].InMicroseconds(),
allocation_samples[i].total_bytes);
sample_data.push_back(datum);
}
double slope = 0;
double y_intercept = 0;
bool valid = GetLinearFit(sample_data.begin(), sample_data.end(), &slope,
&y_intercept);
DCHECK(valid);
linear_regression_map[allocation_name] =
SlopeYIntercept(slope, y_intercept);
AllocationProfile alloc_profile(allocation_name, &allocation_samples, slope,
y_intercept);
alloc_profile.leak_potential_ =
allocation_samples.back().total_bytes * slope;
allocation_profiles.push_back(alloc_profile);
}
std::sort(allocation_profiles.begin(), allocation_profiles.end(),
AllocationProfile::CompareLeakPotential);
// Biggest one first.
std::reverse(allocation_profiles.begin(), allocation_profiles.end());
*destination = allocation_profiles;
}
} // namespace memory_tracker
} // namespace browser
} // namespace cobalt