1 // Copyright 2019 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/profiler/metadata_recorder.h"
6
7 #include "base/metrics/histogram_macros.h"
8
9 namespace base {
10
11 const size_t MetadataRecorder::MAX_METADATA_COUNT;
12
Item(uint64_t name_hash,Optional<int64_t> key,int64_t value)13 MetadataRecorder::Item::Item(uint64_t name_hash,
14 Optional<int64_t> key,
15 int64_t value)
16 : name_hash(name_hash), key(key), value(value) {}
17
Item()18 MetadataRecorder::Item::Item() : name_hash(0), value(0) {}
19
20 MetadataRecorder::Item::Item(const Item& other) = default;
21
22 MetadataRecorder::Item& MetadataRecorder::Item::Item::operator=(
23 const Item& other) = default;
24
25 MetadataRecorder::ItemInternal::ItemInternal() = default;
26
27 MetadataRecorder::ItemInternal::~ItemInternal() = default;
28
MetadataRecorder()29 MetadataRecorder::MetadataRecorder() {
30 // Ensure that we have necessary atomic support.
31 DCHECK(items_[0].is_active.is_lock_free());
32 DCHECK(items_[0].value.is_lock_free());
33 }
34
35 MetadataRecorder::~MetadataRecorder() = default;
36
Set(uint64_t name_hash,Optional<int64_t> key,int64_t value)37 void MetadataRecorder::Set(uint64_t name_hash,
38 Optional<int64_t> key,
39 int64_t value) {
40 AutoLock lock(write_lock_);
41
42 // Acquiring the |write_lock_| ensures that:
43 //
44 // - We don't try to write into the same new slot at the same time as
45 // another thread
46 // - We see all writes by other threads (acquiring a mutex implies acquire
47 // semantics)
48 size_t item_slots_used = item_slots_used_.load(std::memory_order_relaxed);
49 for (size_t i = 0; i < item_slots_used; ++i) {
50 auto& item = items_[i];
51 if (item.name_hash == name_hash && item.key == key) {
52 item.value.store(value, std::memory_order_relaxed);
53
54 const bool was_active =
55 item.is_active.exchange(true, std::memory_order_release);
56 if (!was_active)
57 inactive_item_count_--;
58
59 UMA_HISTOGRAM_COUNTS_10000("StackSamplingProfiler.MetadataSlotsUsed",
60 item_slots_used);
61
62 return;
63 }
64 }
65
66 item_slots_used = TryReclaimInactiveSlots(item_slots_used);
67
68 UMA_HISTOGRAM_COUNTS_10000("StackSamplingProfiler.MetadataSlotsUsed",
69 item_slots_used + 1);
70
71 if (item_slots_used == items_.size()) {
72 // The metadata recorder is full, forcing us to drop this metadata. The
73 // above UMA histogram counting occupied metadata slots should help us set a
74 // max size that avoids this condition during normal Chrome use.
75 return;
76 }
77
78 // Wait until the item is fully created before setting |is_active| to true and
79 // incrementing |item_slots_used_|, which will signal to readers that the item
80 // is ready.
81 auto& item = items_[item_slots_used];
82 item.name_hash = name_hash;
83 item.key = key;
84 item.value.store(value, std::memory_order_relaxed);
85 item.is_active.store(true, std::memory_order_release);
86 item_slots_used_.fetch_add(1, std::memory_order_release);
87 }
88
Remove(uint64_t name_hash,Optional<int64_t> key)89 void MetadataRecorder::Remove(uint64_t name_hash, Optional<int64_t> key) {
90 AutoLock lock(write_lock_);
91
92 size_t item_slots_used = item_slots_used_.load(std::memory_order_relaxed);
93 for (size_t i = 0; i < item_slots_used; ++i) {
94 auto& item = items_[i];
95 if (item.name_hash == name_hash && item.key == key) {
96 // A removed item will occupy its slot until that slot is reclaimed.
97 const bool was_active =
98 item.is_active.exchange(false, std::memory_order_relaxed);
99 if (was_active)
100 inactive_item_count_++;
101
102 return;
103 }
104 }
105 }
106
MetadataProvider(MetadataRecorder * metadata_recorder)107 MetadataRecorder::MetadataProvider::MetadataProvider(
108 MetadataRecorder* metadata_recorder)
109 : metadata_recorder_(metadata_recorder),
110 auto_lock_(metadata_recorder->read_lock_) {}
111
112 MetadataRecorder::MetadataProvider::~MetadataProvider() = default;
113
GetItems(ItemArray * const items) const114 size_t MetadataRecorder::MetadataProvider::GetItems(
115 ItemArray* const items) const {
116 return metadata_recorder_->GetItems(items);
117 }
118
GetItems(ItemArray * const items) const119 size_t MetadataRecorder::GetItems(ItemArray* const items) const {
120 // If a writer adds a new item after this load, it will be ignored. We do
121 // this instead of calling item_slots_used_.load() explicitly in the for loop
122 // bounds checking, which would be expensive.
123 //
124 // Also note that items are snapshotted sequentially and that items can be
125 // modified mid-snapshot by non-suspended threads. This means that there's a
126 // small chance that some items, especially those that occur later in the
127 // array, may have values slightly "in the future" from when the sample was
128 // actually collected. It also means that the array as returned may have never
129 // existed in its entirety, although each name/value pair represents a
130 // consistent item that existed very shortly after the thread was supended.
131 size_t item_slots_used = item_slots_used_.load(std::memory_order_acquire);
132 size_t write_index = 0;
133 for (size_t read_index = 0; read_index < item_slots_used; ++read_index) {
134 const auto& item = items_[read_index];
135 // Because we wait until |is_active| is set to consider an item active and
136 // that field is always set last, we ignore half-created items.
137 if (item.is_active.load(std::memory_order_acquire)) {
138 (*items)[write_index++] = Item{
139 item.name_hash, item.key, item.value.load(std::memory_order_relaxed)};
140 }
141 }
142
143 return write_index;
144 }
145
TryReclaimInactiveSlots(size_t item_slots_used)146 size_t MetadataRecorder::TryReclaimInactiveSlots(size_t item_slots_used) {
147 const size_t remaining_slots = MAX_METADATA_COUNT - item_slots_used;
148
149 if (inactive_item_count_ == 0 || inactive_item_count_ < remaining_slots) {
150 // This reclaiming threshold has a few nice properties:
151 //
152 // - It avoids reclaiming when no items have been removed
153 // - It makes doing so more likely as free slots become more scarce
154 // - It makes doing so less likely when the benefits are lower
155 return item_slots_used;
156 }
157
158 if (read_lock_.Try()) {
159 // The lock isn't already held by a reader or another thread reclaiming
160 // slots.
161 item_slots_used = ReclaimInactiveSlots(item_slots_used);
162 read_lock_.Release();
163 }
164
165 return item_slots_used;
166 }
167
ReclaimInactiveSlots(size_t item_slots_used)168 size_t MetadataRecorder::ReclaimInactiveSlots(size_t item_slots_used) {
169 // From here until the end of the reclamation, we can safely use
170 // memory_order_relaxed for all reads and writes. We don't need
171 // memory_order_acquire because acquiring the write mutex gives acquire
172 // semantics and no other threads can write after we hold that mutex. We don't
173 // need memory_order_release because no readers can read until we release the
174 // read mutex, which itself has release semantics.
175 size_t first_inactive_item_idx = 0;
176 size_t last_active_item_idx = item_slots_used - 1;
177 while (first_inactive_item_idx < last_active_item_idx) {
178 ItemInternal& inactive_item = items_[first_inactive_item_idx];
179 ItemInternal& active_item = items_[last_active_item_idx];
180
181 if (inactive_item.is_active.load(std::memory_order_relaxed)) {
182 // Keep seeking forward to an inactive item.
183 ++first_inactive_item_idx;
184 continue;
185 }
186
187 if (!active_item.is_active.load(std::memory_order_relaxed)) {
188 // Keep seeking backward to an active item. Skipping over this item
189 // indicates that we're freeing the slot at this index.
190 --last_active_item_idx;
191 item_slots_used--;
192 continue;
193 }
194
195 inactive_item.name_hash = active_item.name_hash;
196 inactive_item.value.store(active_item.value.load(std::memory_order_relaxed),
197 std::memory_order_relaxed);
198 inactive_item.is_active.store(true, std::memory_order_relaxed);
199
200 ++first_inactive_item_idx;
201 --last_active_item_idx;
202 item_slots_used--;
203 }
204
205 item_slots_used_.store(item_slots_used, std::memory_order_relaxed);
206 return item_slots_used;
207 }
208 } // namespace base
209