blob: ecf03649515cea0cc2fbdc33ee4c0c416b62b099 [file] [log] [blame]
// Copyright 2019 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 "components/metrics/call_stack_profile_metadata.h"
#include <algorithm>
#include <iterator>
#include <tuple>
namespace metrics {
namespace {
class MatchesNameHashIndexAndKey {
MatchesNameHashIndexAndKey(int name_hash_index, base::Optional<int64_t> key)
: name_hash_index_(name_hash_index), key_(key) {}
bool operator()(const CallStackProfile::MetadataItem& item) const {
base::Optional<int64_t> item_key_as_optional =
item.has_key() ? item.key() : base::Optional<int64_t>();
return item.name_hash_index() == name_hash_index_ &&
key_ == item_key_as_optional;
int name_hash_index_;
base::Optional<int64_t> key_;
// Finds the last value for a prior metadata application with |name_hash_index|
// and |key| from |begin| that was still active at |end|. Returns nullopt if no
// such application exists.
base::Optional<int64_t> FindLastOpenEndedMetadataValue(
int name_hash_index,
base::Optional<int64_t> key,
end) {
// Search the samples backward from the end of the range, looking for an
// application of the same metadata name hash/key that doesn't have a
// corresponding removal.
const auto rbegin = std::make_reverse_iterator(end);
const auto rend = std::make_reverse_iterator(begin);
for (auto it = rbegin; it != rend; ++it) {
auto item = std::find_if(it->metadata().begin(), it->metadata().end(),
MatchesNameHashIndexAndKey(name_hash_index, key));
if (item == it->metadata().end()) {
// The sample does not contain a matching item.
if (!item->has_value()) {
// A matching item was previously applied, but stopped being applied
// before the last sample in the range.
return base::nullopt;
// Else, a matching item was applied at this sample.
return item->value();
// No matching items were previously applied.
return base::nullopt;
// Clears any existing metadata changes between |begin| and |end|.
void ClearExistingMetadata(
const int name_hash_index,
base::Optional<int64_t> key,
end) {
for (auto it = begin; it != end; ++it) {
metadata = it->mutable_metadata();
std::remove_if(metadata->begin(), metadata->end(),
MatchesNameHashIndexAndKey(name_hash_index, key)),
// Sets the state of |item| to the provided values.
void SetMetadataItem(int name_hash_index,
base::Optional<int64_t> key,
base::Optional<int64_t> value,
CallStackProfile::MetadataItem* item) {
if (key.has_value())
if (value.has_value())
} // namespace
CallStackProfileMetadata::CallStackProfileMetadata() = default;
CallStackProfileMetadata::~CallStackProfileMetadata() = default;
// This function is invoked on the profiler thread while the target thread is
// suspended so must not take any locks, including indirectly through use of
// heap allocation, LOG, CHECK, or DCHECK.
void CallStackProfileMetadata::RecordMetadata(
const base::MetadataRecorder::MetadataProvider& metadata_provider) {
metadata_item_count_ = metadata_provider.GetItems(&metadata_items_);
google::protobuf::RepeatedField<uint64_t>* metadata_name_hashes) {
MetadataMap current_items =
CreateMetadataMap(metadata_items_, metadata_item_count_);
for (auto item :
GetNewOrModifiedMetadataItems(current_items, previous_items_)) {
size_t name_hash_index =
MaybeAppendNameHash(item.first.name_hash, metadata_name_hashes);
CallStackProfile::MetadataItem* profile_item = metadata_items.Add();
if (item.first.key.has_value())
for (auto item : GetDeletedMetadataItems(current_items, previous_items_)) {
size_t name_hash_index =
MaybeAppendNameHash(item.first.name_hash, metadata_name_hashes);
CallStackProfile::MetadataItem* profile_item = metadata_items.Add();
if (item.first.key.has_value())
// Leave the value empty to indicate that the item was deleted.
previous_items_ = std::move(current_items);
metadata_item_count_ = 0;
return metadata_items;
void CallStackProfileMetadata::ApplyMetadata(
const base::MetadataRecorder::Item& item,
google::protobuf::RepeatedField<uint64_t>* metadata_name_hashes) {
if (begin == end)
// This function works by finding the previously effective metadata values
// with the same name hash and key at the begin and end of the range. The
// range is then cleared of any metadata changes (with the same name hash and
// key) in preparation for recording the metadata application at the start of
// the range and the removal at the end of the range.
// We expect this function to be called at most a few times per collection, so
// it's written to be readable rather than optimally performant. If
// performance becomes a concern, the two FindLastOpenEndedMetadataValue()
// calls can be merged into one to avoid one loop over the samples, or a more
// efficient representation of when metadata is set/unset could be used to
// avoid the looping entirely.
const size_t name_hash_index =
MaybeAppendNameHash(item.name_hash, metadata_name_hashes);
// The previously set metadata value immediately prior to begin, or nullopt if
// none.
const base::Optional<int64_t> previous_value_before_begin =
FindLastOpenEndedMetadataValue(name_hash_index, item.key,
stack_samples->begin(), begin);
// The end of the range will be in one of two states: terminating before the
// last recorded sample, or terminating at the last recorded sample. If it
// terminates before the last recorded sample then we are able to record the
// removal of the metadata on the sample following the end of the
// range. Otherwise we have to wait for the next recorded sample to record the
// removal of the metadata.
const bool range_terminates_at_last_sample = end == stack_samples->end();
// The previously set metadata value at *end (or the one to be set on the next
// sample if range_terminates_at_last_sample).
const base::Optional<int64_t> previous_value_at_end =
name_hash_index, item.key, stack_samples->begin(),
// If a sample past the end exists check its value as well, since
// we'll be overwriting that sample's metadata below.
(range_terminates_at_last_sample ? end : end + 1));
ClearExistingMetadata(name_hash_index, item.key, begin,
(range_terminates_at_last_sample ? end : end + 1));
// Enable the metadata on the initial sample if different than the previous
// state.
if (!previous_value_before_begin.has_value() ||
*previous_value_before_begin != item.value) {
SetMetadataItem(name_hash_index, item.key, item.value,
if (range_terminates_at_last_sample) {
// We note that the metadata item that was set for the last sample in
// previous_items_ to enable computing the appropriate deltas from it on
// the next recorded sample.
previous_items_[MetadataKey(item.name_hash, item.key)] = item.value;
} else if (!previous_value_at_end.has_value() ||
*previous_value_at_end != item.value) {
// A sample exists past the end of the range so we can use that sample to
// record the end of the metadata application. We do so if there was no
// previous value at the end or it was different than what we set at begin.
SetMetadataItem(name_hash_index, item.key,
// If we had a previously set item at the end of the range,
// set its value. Otherwise leave the value empty to denote
// that it is being unset.
? *previous_value_at_end
: base::Optional<int64_t>(),
bool CallStackProfileMetadata::MetadataKeyCompare::operator()(
const MetadataKey& a,
const MetadataKey& b) const {
return std::tie(a.name_hash, a.key) < std::tie(b.name_hash, b.key);
CallStackProfileMetadata::MetadataKey::MetadataKey(uint64_t name_hash,
base::Optional<int64_t> key)
: name_hash(name_hash), key(key) {}
CallStackProfileMetadata::MetadataKey::MetadataKey(const MetadataKey& other) =
CallStackProfileMetadata::MetadataKey& CallStackProfileMetadata::MetadataKey::
operator=(const MetadataKey& other) = default;
base::MetadataRecorder::ItemArray items,
size_t item_count) {
MetadataMap item_map;
for (size_t i = 0; i < item_count; ++i)
item_map[MetadataKey{items[i].name_hash, items[i].key}] = items[i].value;
return item_map;
const MetadataMap& current_items,
const MetadataMap& previous_items) {
MetadataMap new_or_modified_items;
// Find the new or modified items by subtracting any previous items that are
// exactly the same as the current items (i.e. equal in key *and* value).
auto key_and_value_comparator = [](const std::pair<MetadataKey, int64_t>& a,
const std::pair<MetadataKey, int64_t>& b) {
return std::tie(a.first.name_hash, a.first.key, a.second) <
std::tie(b.first.name_hash, b.first.key, b.second);
current_items.begin(), current_items.end(), previous_items.begin(),
std::inserter(new_or_modified_items, new_or_modified_items.begin()),
return new_or_modified_items;
const MetadataMap& current_items,
const MetadataMap& previous_items) {
MetadataMap deleted_items;
// Find the deleted metadata items by subtracting the current items from the
// previous items, comparing items solely map key (as opposed to map key and
// value as in GetNewOrModifiedMetadataItems()). Comparing by key is necessary
// to distinguish modified items from deleted items: subtraction of modified
// items, which have the same key but different values, should produce the
// empty set. Deleted items have a key only in |previous_items| so should be
// retained in the result.
auto key_comparator = [](const std::pair<MetadataKey, int64_t>& lhs,
const std::pair<MetadataKey, int64_t>& rhs) {
return MetadataKeyCompare()(lhs.first, rhs.first);
std::set_difference(previous_items.begin(), previous_items.end(),
current_items.begin(), current_items.end(),
std::inserter(deleted_items, deleted_items.begin()),
return deleted_items;
size_t CallStackProfileMetadata::MaybeAppendNameHash(
uint64_t name_hash,
google::protobuf::RepeatedField<uint64_t>* metadata_name_hashes) {
std::unordered_map<uint64_t, int>::iterator it;
bool inserted;
int next_item_index = metadata_name_hashes->size();
std::tie(it, inserted) =
metadata_hashes_cache_.emplace(name_hash, next_item_index);
if (inserted)
return it->second;
} // namespace metrics