File: call_stack_profile_metadata.cc

package info (click to toggle)
chromium 120.0.6099.224-1~deb11u1
  • links: PTS, VCS
  • area: main
  • in suites: bullseye
  • size: 6,112,112 kB
  • sloc: cpp: 32,907,025; ansic: 8,148,123; javascript: 3,679,536; python: 2,031,248; asm: 959,718; java: 804,675; xml: 617,256; sh: 111,417; objc: 100,835; perl: 88,443; cs: 53,032; makefile: 29,579; fortran: 24,137; php: 21,162; tcl: 21,147; sql: 20,809; ruby: 17,735; pascal: 12,864; yacc: 8,045; lisp: 3,388; lex: 1,323; ada: 727; awk: 329; jsp: 267; csh: 117; exp: 43; sed: 37
file content (331 lines) | stat: -rw-r--r-- 13,483 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
// Copyright 2019 The Chromium Authors
// 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 <iterator>
#include <tuple>

#include "base/ranges/algorithm.h"

namespace metrics {

namespace {

class MatchesNameHashIndexAndKey {
 public:
  MatchesNameHashIndexAndKey(int name_hash_index, absl::optional<int64_t> key)
      : name_hash_index_(name_hash_index), key_(key) {}

  bool operator()(const CallStackProfile::MetadataItem& item) const {
    absl::optional<int64_t> item_key_as_optional =
        item.has_key() ? item.key() : absl::optional<int64_t>();
    return item.name_hash_index() == name_hash_index_ &&
           key_ == item_key_as_optional;
  }

 private:
  int name_hash_index_;
  absl::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.
absl::optional<int64_t> FindLastOpenEndedMetadataValue(
    int name_hash_index,
    absl::optional<int64_t> key,
    google::protobuf::RepeatedPtrField<CallStackProfile::StackSample>::iterator
        begin,
    google::protobuf::RepeatedPtrField<CallStackProfile::StackSample>::iterator
        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 = base::ranges::find_if(
        it->metadata(), MatchesNameHashIndexAndKey(name_hash_index, key));

    if (item == it->metadata().end()) {
      // The sample does not contain a matching item.
      continue;
    }

    if (!item->has_value()) {
      // A matching item was previously applied, but stopped being applied
      // before the last sample in the range.
      return absl::nullopt;
    }

    // Else, a matching item was applied at this sample.
    return item->value();
  }

  // No matching items were previously applied.
  return absl::nullopt;
}

// Clears any existing metadata changes between |begin| and |end|.
void ClearExistingMetadata(
    const int name_hash_index,
    absl::optional<int64_t> key,
    google::protobuf::RepeatedPtrField<CallStackProfile::StackSample>::iterator
        begin,
    google::protobuf::RepeatedPtrField<CallStackProfile::StackSample>::iterator
        end) {
  for (auto it = begin; it != end; ++it) {
    google::protobuf::RepeatedPtrField<CallStackProfile::MetadataItem>*
        metadata = it->mutable_metadata();
    metadata->erase(
        std::remove_if(metadata->begin(), metadata->end(),
                       MatchesNameHashIndexAndKey(name_hash_index, key)),
        metadata->end());
  }
}

// Sets the state of |item| to the provided values.
void SetMetadataItem(int name_hash_index,
                     absl::optional<int64_t> key,
                     absl::optional<int64_t> value,
                     CallStackProfile::MetadataItem* item) {
  item->set_name_hash_index(name_hash_index);
  if (key.has_value())
    item->set_key(*key);
  if (value.has_value())
    item->set_value(*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::RepeatedPtrField<CallStackProfile::MetadataItem>
CallStackProfileMetadata::CreateSampleMetadata(
    google::protobuf::RepeatedField<uint64_t>* metadata_name_hashes) {
  DCHECK_EQ(metadata_hashes_cache_.size(),
            static_cast<size_t>(metadata_name_hashes->size()));

  google::protobuf::RepeatedPtrField<CallStackProfile::MetadataItem>
      metadata_items;
  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();
    profile_item->set_name_hash_index(name_hash_index);
    if (item.first.key.has_value())
      profile_item->set_key(*item.first.key);
    profile_item->set_value(item.second);
  }

  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();
    profile_item->set_name_hash_index(name_hash_index);
    if (item.first.key.has_value())
      profile_item->set_key(*item.first.key);
    // 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::RepeatedPtrField<CallStackProfile::StackSample>::iterator
        begin,
    google::protobuf::RepeatedPtrField<CallStackProfile::StackSample>::iterator
        end,
    google::protobuf::RepeatedPtrField<CallStackProfile::StackSample>*
        stack_samples,
    google::protobuf::RepeatedField<uint64_t>* metadata_name_hashes) {
  if (begin == end)
    return;

  // 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 absl::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 absl::optional<int64_t> previous_value_at_end =
      FindLastOpenEndedMetadataValue(
          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,
                    begin->mutable_metadata()->Add());
  }

  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.has_value()
                        ? *previous_value_at_end
                        : absl::optional<int64_t>(),
                    end->mutable_metadata()->Add());
  }
}

void CallStackProfileMetadata::SetMetadata(
    const base::MetadataRecorder::Item& src_item,
    CallStackProfile::MetadataItem* dest_item,
    google::protobuf::RepeatedField<uint64_t>* metadata_name_hashes) {
  const size_t name_hash_index =
      MaybeAppendNameHash(src_item.name_hash, metadata_name_hashes);

  SetMetadataItem(name_hash_index, src_item.key, src_item.value, dest_item);
}

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,
                                                   absl::optional<int64_t> key)
    : name_hash(name_hash), key(key) {}

CallStackProfileMetadata::MetadataKey::MetadataKey(const MetadataKey& other) =
    default;
CallStackProfileMetadata::MetadataKey& CallStackProfileMetadata::MetadataKey::
operator=(const MetadataKey& other) = default;

CallStackProfileMetadata::MetadataMap
CallStackProfileMetadata::CreateMetadataMap(
    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;
}

CallStackProfileMetadata::MetadataMap
CallStackProfileMetadata::GetNewOrModifiedMetadataItems(
    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);
  };
  std::set_difference(
      current_items.begin(), current_items.end(), previous_items.begin(),
      previous_items.end(),
      std::inserter(new_or_modified_items, new_or_modified_items.begin()),
      key_and_value_comparator);
  return new_or_modified_items;
}

CallStackProfileMetadata::MetadataMap
CallStackProfileMetadata::GetDeletedMetadataItems(
    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()),
                      key_comparator);
  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)
    metadata_name_hashes->Add(name_hash);

  return it->second;
}

}  // namespace metrics