1 // Copyright (c) 2012 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/metrics/histogram_samples.h"
6
7 #include <limits>
8
9 #include "base/compiler_specific.h"
10 #include "base/metrics/histogram_functions.h"
11 #include "base/metrics/histogram_macros.h"
12 #include "base/numerics/safe_conversions.h"
13 #include "base/numerics/safe_math.h"
14 #include "base/pickle.h"
15
16 namespace base {
17
18 namespace {
19
20 // A shorthand constant for the max value of size_t.
21 constexpr size_t kSizeMax = std::numeric_limits<size_t>::max();
22
23 // A constant stored in an AtomicSingleSample (as_atomic) to indicate that the
24 // sample is "disabled" and no further accumulation should be done with it. The
25 // value is chosen such that it will be MAX_UINT16 for both |bucket| & |count|,
26 // and thus less likely to conflict with real use. Conflicts are explicitly
27 // handled in the code but it's worth making them as unlikely as possible.
28 constexpr int32_t kDisabledSingleSample = -1;
29
30 class SampleCountPickleIterator : public SampleCountIterator {
31 public:
32 explicit SampleCountPickleIterator(PickleIterator* iter);
33
34 bool Done() const override;
35 void Next() override;
36 void Get(HistogramBase::Sample* min,
37 int64_t* max,
38 HistogramBase::Count* count) const override;
39
40 private:
41 PickleIterator* const iter_;
42
43 HistogramBase::Sample min_;
44 int64_t max_;
45 HistogramBase::Count count_;
46 bool is_done_;
47 };
48
SampleCountPickleIterator(PickleIterator * iter)49 SampleCountPickleIterator::SampleCountPickleIterator(PickleIterator* iter)
50 : iter_(iter),
51 is_done_(false) {
52 Next();
53 }
54
Done() const55 bool SampleCountPickleIterator::Done() const {
56 return is_done_;
57 }
58
Next()59 void SampleCountPickleIterator::Next() {
60 DCHECK(!Done());
61 if (!iter_->ReadInt(&min_) || !iter_->ReadInt64(&max_) ||
62 !iter_->ReadInt(&count_)) {
63 is_done_ = true;
64 }
65 }
66
Get(HistogramBase::Sample * min,int64_t * max,HistogramBase::Count * count) const67 void SampleCountPickleIterator::Get(HistogramBase::Sample* min,
68 int64_t* max,
69 HistogramBase::Count* count) const {
70 DCHECK(!Done());
71 *min = min_;
72 *max = max_;
73 *count = count_;
74 }
75
76 } // namespace
77
78 static_assert(sizeof(HistogramSamples::AtomicSingleSample) ==
79 sizeof(subtle::Atomic32),
80 "AtomicSingleSample isn't 32 bits");
81
Load() const82 HistogramSamples::SingleSample HistogramSamples::AtomicSingleSample::Load()
83 const {
84 AtomicSingleSample single_sample = subtle::Acquire_Load(&as_atomic);
85
86 // If the sample was extracted/disabled, it's still zero to the outside.
87 if (single_sample.as_atomic == kDisabledSingleSample)
88 single_sample.as_atomic = 0;
89
90 return single_sample.as_parts;
91 }
92
Extract(bool disable)93 HistogramSamples::SingleSample HistogramSamples::AtomicSingleSample::Extract(
94 bool disable) {
95 AtomicSingleSample single_sample = subtle::NoBarrier_AtomicExchange(
96 &as_atomic, disable ? kDisabledSingleSample : 0);
97 if (single_sample.as_atomic == kDisabledSingleSample)
98 single_sample.as_atomic = 0;
99 return single_sample.as_parts;
100 }
101
Accumulate(size_t bucket,HistogramBase::Count count)102 bool HistogramSamples::AtomicSingleSample::Accumulate(
103 size_t bucket,
104 HistogramBase::Count count) {
105 if (count == 0)
106 return true;
107
108 // Convert the parameters to 16-bit variables because it's all 16-bit below.
109 // To support decrements/subtractions, divide the |count| into sign/value and
110 // do the proper operation below. The alternative is to change the single-
111 // sample's count to be a signed integer (int16_t) and just add an int16_t
112 // |count16| but that is somewhat wasteful given that the single-sample is
113 // never expected to have a count less than zero.
114 if (count < -std::numeric_limits<uint16_t>::max() ||
115 count > std::numeric_limits<uint16_t>::max() ||
116 bucket > std::numeric_limits<uint16_t>::max()) {
117 return false;
118 }
119 bool count_is_negative = count < 0;
120 uint16_t count16 = static_cast<uint16_t>(count_is_negative ? -count : count);
121 uint16_t bucket16 = static_cast<uint16_t>(bucket);
122
123 // A local, unshared copy of the single-sample is necessary so the parts
124 // can be manipulated without worrying about atomicity.
125 AtomicSingleSample single_sample;
126
127 bool sample_updated;
128 do {
129 subtle::Atomic32 original = subtle::Acquire_Load(&as_atomic);
130 if (original == kDisabledSingleSample)
131 return false;
132 single_sample.as_atomic = original;
133 if (single_sample.as_atomic != 0) {
134 // Only the same bucket (parameter and stored) can be counted multiple
135 // times.
136 if (single_sample.as_parts.bucket != bucket16)
137 return false;
138 } else {
139 // The |single_ sample| was zero so becomes the |bucket| parameter, the
140 // contents of which were checked above to fit in 16 bits.
141 single_sample.as_parts.bucket = bucket16;
142 }
143
144 // Update count, making sure that it doesn't overflow.
145 CheckedNumeric<uint16_t> new_count(single_sample.as_parts.count);
146 if (count_is_negative)
147 new_count -= count16;
148 else
149 new_count += count16;
150 if (!new_count.AssignIfValid(&single_sample.as_parts.count))
151 return false;
152
153 // Don't let this become equivalent to the "disabled" value.
154 if (single_sample.as_atomic == kDisabledSingleSample)
155 return false;
156
157 // Store the updated single-sample back into memory. |existing| is what
158 // was in that memory location at the time of the call; if it doesn't
159 // match |original| then the swap didn't happen so loop again.
160 subtle::Atomic32 existing = subtle::Release_CompareAndSwap(
161 &as_atomic, original, single_sample.as_atomic);
162 sample_updated = (existing == original);
163 } while (!sample_updated);
164
165 return true;
166 }
167
IsDisabled() const168 bool HistogramSamples::AtomicSingleSample::IsDisabled() const {
169 return subtle::Acquire_Load(&as_atomic) == kDisabledSingleSample;
170 }
171
LocalMetadata()172 HistogramSamples::LocalMetadata::LocalMetadata() {
173 // This is the same way it's done for persistent metadata since no ctor
174 // is called for the data members in that case.
175 memset(this, 0, sizeof(*this));
176 }
177
HistogramSamples(uint64_t id,Metadata * meta)178 HistogramSamples::HistogramSamples(uint64_t id, Metadata* meta)
179 : meta_(meta) {
180 DCHECK(meta_->id == 0 || meta_->id == id);
181
182 // It's possible that |meta| is contained in initialized, read-only memory
183 // so it's essential that no write be done in that case.
184 if (!meta_->id)
185 meta_->id = id;
186 }
187
188 // This mustn't do anything with |meta_|. It was passed to the ctor and may
189 // be invalid by the time this dtor gets called.
190 HistogramSamples::~HistogramSamples() = default;
191
Add(const HistogramSamples & other)192 void HistogramSamples::Add(const HistogramSamples& other) {
193 IncreaseSumAndCount(other.sum(), other.redundant_count());
194 std::unique_ptr<SampleCountIterator> it = other.Iterator();
195 bool success = AddSubtractImpl(it.get(), ADD);
196 DCHECK(success);
197 }
198
AddFromPickle(PickleIterator * iter)199 bool HistogramSamples::AddFromPickle(PickleIterator* iter) {
200 int64_t sum;
201 HistogramBase::Count redundant_count;
202
203 if (!iter->ReadInt64(&sum) || !iter->ReadInt(&redundant_count))
204 return false;
205
206 IncreaseSumAndCount(sum, redundant_count);
207
208 SampleCountPickleIterator pickle_iter(iter);
209 return AddSubtractImpl(&pickle_iter, ADD);
210 }
211
Subtract(const HistogramSamples & other)212 void HistogramSamples::Subtract(const HistogramSamples& other) {
213 IncreaseSumAndCount(-other.sum(), -other.redundant_count());
214 std::unique_ptr<SampleCountIterator> it = other.Iterator();
215 bool success = AddSubtractImpl(it.get(), SUBTRACT);
216 DCHECK(success);
217 }
218
Serialize(Pickle * pickle) const219 void HistogramSamples::Serialize(Pickle* pickle) const {
220 pickle->WriteInt64(sum());
221 pickle->WriteInt(redundant_count());
222
223 HistogramBase::Sample min;
224 int64_t max;
225 HistogramBase::Count count;
226 for (std::unique_ptr<SampleCountIterator> it = Iterator(); !it->Done();
227 it->Next()) {
228 it->Get(&min, &max, &count);
229 pickle->WriteInt(min);
230 pickle->WriteInt64(max);
231 pickle->WriteInt(count);
232 }
233 }
234
AccumulateSingleSample(HistogramBase::Sample value,HistogramBase::Count count,size_t bucket)235 bool HistogramSamples::AccumulateSingleSample(HistogramBase::Sample value,
236 HistogramBase::Count count,
237 size_t bucket) {
238 if (single_sample().Accumulate(bucket, count)) {
239 // Success. Update the (separate) sum and redundant-count.
240 IncreaseSumAndCount(strict_cast<int64_t>(value) * count, count);
241 return true;
242 }
243 return false;
244 }
245
IncreaseSumAndCount(int64_t sum,HistogramBase::Count count)246 void HistogramSamples::IncreaseSumAndCount(int64_t sum,
247 HistogramBase::Count count) {
248 #ifdef ARCH_CPU_64_BITS
249 subtle::NoBarrier_AtomicIncrement(&meta_->sum, sum);
250 #else
251 meta_->sum += sum;
252 #endif
253 subtle::NoBarrier_AtomicIncrement(&meta_->redundant_count, count);
254 }
255
RecordNegativeSample(NegativeSampleReason reason,HistogramBase::Count increment)256 void HistogramSamples::RecordNegativeSample(NegativeSampleReason reason,
257 HistogramBase::Count increment) {
258 UMA_HISTOGRAM_ENUMERATION("UMA.NegativeSamples.Reason", reason,
259 MAX_NEGATIVE_SAMPLE_REASONS);
260 UMA_HISTOGRAM_CUSTOM_COUNTS("UMA.NegativeSamples.Increment", increment, 1,
261 1 << 30, 100);
262 UmaHistogramSparse("UMA.NegativeSamples.Histogram",
263 static_cast<int32_t>(id()));
264 }
265
266 SampleCountIterator::~SampleCountIterator() = default;
267
GetBucketIndex(size_t * index) const268 bool SampleCountIterator::GetBucketIndex(size_t* index) const {
269 DCHECK(!Done());
270 return false;
271 }
272
SingleSampleIterator(HistogramBase::Sample min,int64_t max,HistogramBase::Count count)273 SingleSampleIterator::SingleSampleIterator(HistogramBase::Sample min,
274 int64_t max,
275 HistogramBase::Count count)
276 : SingleSampleIterator(min, max, count, kSizeMax) {}
277
SingleSampleIterator(HistogramBase::Sample min,int64_t max,HistogramBase::Count count,size_t bucket_index)278 SingleSampleIterator::SingleSampleIterator(HistogramBase::Sample min,
279 int64_t max,
280 HistogramBase::Count count,
281 size_t bucket_index)
282 : min_(min), max_(max), bucket_index_(bucket_index), count_(count) {}
283
284 SingleSampleIterator::~SingleSampleIterator() = default;
285
Done() const286 bool SingleSampleIterator::Done() const {
287 return count_ == 0;
288 }
289
Next()290 void SingleSampleIterator::Next() {
291 DCHECK(!Done());
292 count_ = 0;
293 }
294
Get(HistogramBase::Sample * min,int64_t * max,HistogramBase::Count * count) const295 void SingleSampleIterator::Get(HistogramBase::Sample* min,
296 int64_t* max,
297 HistogramBase::Count* count) const {
298 DCHECK(!Done());
299 if (min != nullptr)
300 *min = min_;
301 if (max != nullptr)
302 *max = max_;
303 if (count != nullptr)
304 *count = count_;
305 }
306
GetBucketIndex(size_t * index) const307 bool SingleSampleIterator::GetBucketIndex(size_t* index) const {
308 DCHECK(!Done());
309 if (bucket_index_ == kSizeMax)
310 return false;
311 *index = bucket_index_;
312 return true;
313 }
314
315 } // namespace base
316