OLD | NEW |
---|---|
1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "base/metrics/sample_vector.h" | 5 #include "base/metrics/sample_vector.h" |
6 | 6 |
7 #include "base/lazy_instance.h" | |
7 #include "base/logging.h" | 8 #include "base/logging.h" |
9 #include "base/memory/ptr_util.h" | |
8 #include "base/metrics/bucket_ranges.h" | 10 #include "base/metrics/bucket_ranges.h" |
11 #include "base/metrics/persistent_memory_allocator.h" | |
12 #include "base/synchronization/lock.h" | |
13 #include "base/threading/platform_thread.h" | |
14 | |
15 // This SampleVector makes use of the single-sample embedded in the base | |
16 // HistogramSamples class. If the count is non-zero then there is guaranteed | |
17 // (within the bounds of "eventual consistency") to be no allocated external | |
18 // storage. Once the full counts storage is allocated, the single-sample must | |
19 // be extracted and disabled. | |
9 | 20 |
10 namespace base { | 21 namespace base { |
11 | 22 |
12 typedef HistogramBase::Count Count; | 23 typedef HistogramBase::Count Count; |
13 typedef HistogramBase::Sample Sample; | 24 typedef HistogramBase::Sample Sample; |
14 | 25 |
15 SampleVector::SampleVector(const BucketRanges* bucket_ranges) | 26 SampleVectorBase::SampleVectorBase(uint64_t id, |
16 : SampleVector(0, bucket_ranges) {} | 27 const BucketRanges* bucket_ranges) |
17 | |
18 SampleVector::SampleVector(uint64_t id, const BucketRanges* bucket_ranges) | |
19 : HistogramSamples(id), | 28 : HistogramSamples(id), |
20 local_counts_(bucket_ranges->bucket_count()), | 29 counts_size_(bucket_ranges->bucket_count()), |
21 counts_(&local_counts_[0]), | |
22 counts_size_(local_counts_.size()), | |
23 bucket_ranges_(bucket_ranges) { | 30 bucket_ranges_(bucket_ranges) { |
24 CHECK_GE(bucket_ranges_->bucket_count(), 1u); | 31 CHECK_GE(bucket_ranges_->bucket_count(), 1u); |
25 } | 32 } |
26 | 33 |
27 SampleVector::SampleVector(uint64_t id, | 34 SampleVectorBase::SampleVectorBase(uint64_t id, |
28 HistogramBase::AtomicCount* counts, | 35 Metadata* meta, |
29 size_t counts_size, | 36 const BucketRanges* bucket_ranges) |
30 Metadata* meta, | |
31 const BucketRanges* bucket_ranges) | |
32 : HistogramSamples(id, meta), | 37 : HistogramSamples(id, meta), |
33 counts_(counts), | |
34 counts_size_(bucket_ranges->bucket_count()), | 38 counts_size_(bucket_ranges->bucket_count()), |
35 bucket_ranges_(bucket_ranges) { | 39 bucket_ranges_(bucket_ranges) { |
36 CHECK_LE(bucket_ranges_->bucket_count(), counts_size_); | |
37 CHECK_GE(bucket_ranges_->bucket_count(), 1u); | 40 CHECK_GE(bucket_ranges_->bucket_count(), 1u); |
38 } | 41 } |
39 | 42 |
40 SampleVector::~SampleVector() {} | 43 SampleVectorBase::~SampleVectorBase() {} |
41 | 44 |
42 void SampleVector::Accumulate(Sample value, Count count) { | 45 void SampleVectorBase::Accumulate(Sample value, Count count) { |
46 // Handle the single-sample case. | |
47 if (!counts()) { | |
Alexei Svitkine (slow)
2017/04/18 20:52:20
Nit: The multi-sample case is less code - so rever
bcwhite
2017/04/19 18:13:02
This case falls through to the multi-sample case i
| |
48 // Try to accumulate the parameters into the single-count entry. | |
49 if (AccumulateSingleSample(value, count)) { | |
50 // A race condition could lead to a new single-sample being accumulated | |
51 // above just after another thread executed the MountCountsStorage() | |
52 // below. Since it is mounted, it could be mounted elsewhere and have | |
53 // values written to it. It's not allowed to have both a single-sample | |
54 // and entries in the counts array so move the single-sample. | |
55 if (counts()) | |
56 MoveSingleSampleToCounts(); | |
57 | |
58 return; | |
59 } | |
60 | |
61 // Need real storage to store both what was in the single-sample plus the | |
62 // parameter information. | |
63 MountCountsStorage(); | |
Alexei Svitkine (slow)
2017/04/18 20:52:21
Can the name of this function be changed so it's c
bcwhite
2017/04/19 18:13:02
Sure.
| |
64 } | |
65 | |
66 // Handle the multi-sample case. | |
43 size_t bucket_index = GetBucketIndex(value); | 67 size_t bucket_index = GetBucketIndex(value); |
44 subtle::NoBarrier_AtomicIncrement(&counts_[bucket_index], count); | 68 subtle::NoBarrier_AtomicIncrement(&counts()[bucket_index], count); |
45 IncreaseSum(static_cast<int64_t>(count) * value); | 69 IncreaseSumAndCount(static_cast<int64_t>(count) * value, count); |
46 IncreaseRedundantCount(count); | 70 } |
47 } | 71 |
48 | 72 Count SampleVectorBase::GetCount(Sample value) const { |
49 Count SampleVector::GetCount(Sample value) const { | 73 return GetCountAtIndex(GetBucketIndex(value)); |
50 size_t bucket_index = GetBucketIndex(value); | 74 } |
51 return subtle::NoBarrier_Load(&counts_[bucket_index]); | 75 |
52 } | 76 Count SampleVectorBase::TotalCount() const { |
53 | 77 // Handle the single-sample case. |
54 Count SampleVector::TotalCount() const { | 78 SingleSample sample = single_sample().Load(); |
55 Count count = 0; | 79 if (sample.count) |
56 for (size_t i = 0; i < counts_size_; i++) { | 80 return sample.count; |
57 count += subtle::NoBarrier_Load(&counts_[i]); | 81 |
58 } | 82 // Handle the multi-sample case. |
59 return count; | 83 if (counts() || MountExistingCountsStorage()) { |
60 } | 84 Count count = 0; |
61 | 85 const HistogramBase::AtomicCount* counts_array = counts(); |
62 Count SampleVector::GetCountAtIndex(size_t bucket_index) const { | 86 for (size_t i = 0; i < counts_size_; i++) { |
87 count += subtle::NoBarrier_Load(&counts_array[i]); | |
88 } | |
89 return count; | |
90 } | |
91 | |
92 // And the no-value case. | |
93 return 0; | |
94 } | |
95 | |
96 Count SampleVectorBase::GetCountAtIndex(size_t bucket_index) const { | |
63 DCHECK(bucket_index < counts_size_); | 97 DCHECK(bucket_index < counts_size_); |
64 return subtle::NoBarrier_Load(&counts_[bucket_index]); | 98 |
65 } | 99 // Handle the single-sample case. |
66 | 100 SingleSample sample = single_sample().Load(); |
67 std::unique_ptr<SampleCountIterator> SampleVector::Iterator() const { | 101 if (sample.count != 0) { |
68 return std::unique_ptr<SampleCountIterator>( | 102 if (sample.value >= bucket_ranges_->range(bucket_index) && |
69 new SampleVectorIterator(counts_, counts_size_, bucket_ranges_)); | 103 sample.value < bucket_ranges_->range(bucket_index + 1)) { |
70 } | 104 return sample.count; |
71 | 105 } |
72 bool SampleVector::AddSubtractImpl(SampleCountIterator* iter, | 106 return 0; |
73 HistogramSamples::Operator op) { | 107 } |
108 | |
109 // Handle the multi-sample case. | |
110 if (counts() || MountExistingCountsStorage()) | |
111 return subtle::NoBarrier_Load(&counts()[bucket_index]); | |
112 | |
113 // And the no-value case. | |
114 return 0; | |
115 } | |
116 | |
117 std::unique_ptr<SampleCountIterator> SampleVectorBase::Iterator() const { | |
118 // Handle the single-sample case. | |
119 SingleSample sample = single_sample().Load(); | |
120 if (sample.count != 0) { | |
121 size_t index = GetBucketIndex(sample.value); | |
122 return MakeUnique<SingleSampleIterator>(bucket_ranges_->range(index), | |
123 bucket_ranges_->range(index + 1), | |
124 sample.count, index); | |
125 } | |
126 | |
127 // Handle the multi-sample case. | |
128 if (counts() || MountExistingCountsStorage()) { | |
129 return MakeUnique<SampleVectorIterator>(counts(), counts_size_, | |
130 bucket_ranges_); | |
131 } | |
132 | |
133 // And the no-value case. | |
134 return MakeUnique<SampleVectorIterator>(nullptr, 0, bucket_ranges_); | |
135 } | |
136 | |
137 bool SampleVectorBase::AddSubtractImpl(SampleCountIterator* iter, | |
138 HistogramSamples::Operator op) { | |
74 HistogramBase::Sample min; | 139 HistogramBase::Sample min; |
75 HistogramBase::Sample max; | 140 HistogramBase::Sample max; |
76 HistogramBase::Count count; | 141 HistogramBase::Count count; |
77 | 142 |
143 // Stop now if there's nothing to do. | |
144 if (iter->Done()) | |
145 return true; | |
146 | |
147 // Get the first value. Single-value storage is possible if there is no | |
148 // counts storage and the retrieved entry is the only one in the iterator. | |
149 iter->Get(&min, &max, &count); | |
150 iter->Next(); | |
151 if (!counts()) { | |
152 if (iter->Done()) { | |
153 // Don't call AccumulateSingleSample because that udpates sum and count | |
Alexei Svitkine (slow)
2017/04/18 20:52:20
updates
bcwhite
2017/04/19 18:13:02
Done.
| |
154 // which was already done by the caller of this method. | |
155 if (single_sample().Accumulate( | |
156 min, op == HistogramSamples::ADD ? count : -count)) { | |
157 if (!counts()) | |
158 return true; | |
159 | |
160 // Handle race-condition creating counts during the accumulate. | |
161 MoveSingleSampleToCounts(); | |
162 | |
163 // This will fall through to MountCountsStorage which is sub-optimal | |
164 // (since we just detected that such has already been done) but it's | |
165 // not worth optimizing because of the extreme rarity of this execution | |
166 // path. | |
167 } | |
168 } | |
169 | |
170 // Definitely need the counts storage for what is to follow. | |
171 MountCountsStorage(); | |
172 } | |
173 | |
78 // Go through the iterator and add the counts into correct bucket. | 174 // Go through the iterator and add the counts into correct bucket. |
79 size_t index = 0; | 175 size_t index = 0; |
80 while (index < counts_size_ && !iter->Done()) { | 176 while (true) { |
177 while (index < counts_size_) { | |
Alexei Svitkine (slow)
2017/04/18 20:52:20
Nested loops make this hard to follow.
I suggest
bcwhite
2017/04/19 18:13:02
Could do though there is state (index) that is pre
| |
178 if (min == bucket_ranges_->range(index) && | |
179 max == bucket_ranges_->range(index + 1)) { | |
180 subtle::NoBarrier_AtomicIncrement( | |
181 &counts()[index], op == HistogramSamples::ADD ? count : -count); | |
182 break; | |
183 } else if (min > bucket_ranges_->range(index)) { | |
184 // Sample is larger than current bucket range. Try next. | |
185 index++; | |
186 } else { | |
187 // Sample is smaller than current bucket range. We scan buckets from | |
188 // smallest to largest, so the sample value must be invalid. | |
189 return false; | |
190 } | |
191 } | |
192 if (index == counts_size_) | |
Alexei Svitkine (slow)
2017/04/18 20:52:20
Add a comment about this case.
bcwhite
2017/04/19 18:13:02
Done.
| |
193 return false; | |
194 | |
195 if (iter->Done()) | |
196 return true; | |
81 iter->Get(&min, &max, &count); | 197 iter->Get(&min, &max, &count); |
82 if (min == bucket_ranges_->range(index) && | 198 iter->Next(); |
83 max == bucket_ranges_->range(index + 1)) { | 199 } |
84 // Sample matches this bucket! | |
85 subtle::NoBarrier_AtomicIncrement( | |
86 &counts_[index], op == HistogramSamples::ADD ? count : -count); | |
87 iter->Next(); | |
88 } else if (min > bucket_ranges_->range(index)) { | |
89 // Sample is larger than current bucket range. Try next. | |
90 index++; | |
91 } else { | |
92 // Sample is smaller than current bucket range. We scan buckets from | |
93 // smallest to largest, so the sample value must be invalid. | |
94 return false; | |
95 } | |
96 } | |
97 | |
98 return iter->Done(); | |
99 } | 200 } |
100 | 201 |
101 // Use simple binary search. This is very general, but there are better | 202 // Use simple binary search. This is very general, but there are better |
102 // approaches if we knew that the buckets were linearly distributed. | 203 // approaches if we knew that the buckets were linearly distributed. |
103 size_t SampleVector::GetBucketIndex(Sample value) const { | 204 size_t SampleVectorBase::GetBucketIndex(Sample value) const { |
104 size_t bucket_count = bucket_ranges_->bucket_count(); | 205 size_t bucket_count = bucket_ranges_->bucket_count(); |
105 CHECK_GE(bucket_count, 1u); | 206 CHECK_GE(bucket_count, 1u); |
106 CHECK_GE(value, bucket_ranges_->range(0)); | 207 CHECK_GE(value, bucket_ranges_->range(0)); |
107 CHECK_LT(value, bucket_ranges_->range(bucket_count)); | 208 CHECK_LT(value, bucket_ranges_->range(bucket_count)); |
108 | 209 |
109 size_t under = 0; | 210 size_t under = 0; |
110 size_t over = bucket_count; | 211 size_t over = bucket_count; |
111 size_t mid; | 212 size_t mid; |
112 do { | 213 do { |
113 DCHECK_GE(over, under); | 214 DCHECK_GE(over, under); |
114 mid = under + (over - under)/2; | 215 mid = under + (over - under)/2; |
115 if (mid == under) | 216 if (mid == under) |
116 break; | 217 break; |
117 if (bucket_ranges_->range(mid) <= value) | 218 if (bucket_ranges_->range(mid) <= value) |
118 under = mid; | 219 under = mid; |
119 else | 220 else |
120 over = mid; | 221 over = mid; |
121 } while (true); | 222 } while (true); |
122 | 223 |
123 DCHECK_LE(bucket_ranges_->range(mid), value); | 224 DCHECK_LE(bucket_ranges_->range(mid), value); |
124 CHECK_GT(bucket_ranges_->range(mid + 1), value); | 225 CHECK_GT(bucket_ranges_->range(mid + 1), value); |
125 return mid; | 226 return mid; |
126 } | 227 } |
127 | 228 |
229 void SampleVectorBase::MoveSingleSampleToCounts() { | |
230 DCHECK(counts()); | |
231 // Disable the single-sample since there is now counts storage for the data. | |
232 SingleSample sample = single_sample().Extract(/*disable=*/true); | |
233 | |
234 // Stop here if there is no "count" as trying to find the bucket index of | |
235 // a invalid (including zero) "value" will crash. | |
Alexei Svitkine (slow)
2017/04/18 20:52:20
Nit: an invalid
bcwhite
2017/04/19 18:13:02
Done.
| |
236 if (sample.count == 0) | |
237 return; | |
238 | |
239 // Move the value into storage. Sum and redundant-count already account | |
240 // for this entry so no need to call IncreaseSumAndCount(). | |
241 size_t bucket_index = GetBucketIndex(sample.value); | |
242 subtle::NoBarrier_AtomicIncrement(&counts()[bucket_index], sample.count); | |
243 } | |
244 | |
245 void SampleVectorBase::MountCountsStorage() { | |
246 // There are many of SampleVector objects and the lock is needed very | |
Alexei Svitkine (slow)
2017/04/18 20:52:21
Nit: remove "of"
bcwhite
2017/04/19 18:13:02
Done.
| |
247 // infrequently (just when advancing from single-sample to multi-sample) so | |
248 // define a single, global lock that all can use. This lock only prevents | |
249 // concurrent entry into the code below; access and updates to |counts_| | |
250 // still requires atomic operations. | |
251 static LazyInstance<Lock>::Leaky counts_lock = LAZY_INSTANCE_INITIALIZER; | |
252 { | |
253 AutoLock lock(counts_lock.Get()); | |
254 if (subtle::NoBarrier_Load(&counts_) == 0) { | |
255 // Create the actual counts storage while the above lock is acquired. | |
256 HistogramBase::Count* counts = CreateCountsStorageWhileLocked(); | |
257 DCHECK(counts); | |
258 | |
259 // Point |counts_| to the newly created storage. This is done while | |
260 // locked to prevent possible concurrent calls to CreateCountsStorage | |
261 // but, between that call and here, other threads could notice the | |
262 // existance of the storage and race with this to set_counts(). That's | |
263 // okay because (a) it's atomic and (b) it always writes the same value. | |
264 set_counts(counts); | |
265 } | |
266 } | |
267 | |
268 // Move any single-sample into the newly mounted storage. | |
269 MoveSingleSampleToCounts(); | |
270 } | |
271 | |
272 SampleVector::SampleVector(const BucketRanges* bucket_ranges) | |
273 : SampleVector(0, bucket_ranges) {} | |
274 | |
275 SampleVector::SampleVector(uint64_t id, const BucketRanges* bucket_ranges) | |
276 : SampleVectorBase(id, bucket_ranges) {} | |
277 | |
278 SampleVector::~SampleVector() {} | |
279 | |
280 bool SampleVector::MountExistingCountsStorage() const { | |
281 // There is never any existing storage other than what is already in use. | |
282 return counts() != nullptr; | |
283 } | |
284 | |
285 HistogramBase::AtomicCount* SampleVector::CreateCountsStorageWhileLocked() { | |
286 local_counts_.resize(counts_size()); | |
287 return &local_counts_[0]; | |
288 } | |
289 | |
290 PersistentSampleVector::PersistentSampleVector( | |
291 uint64_t id, | |
292 const BucketRanges* bucket_ranges, | |
293 Metadata* meta, | |
294 const DelayedPersistentAllocation& counts) | |
295 : SampleVectorBase(id, meta, bucket_ranges), persistent_counts_(counts) { | |
296 // If the "counts" array has already been created, mount it now. | |
297 if (persistent_counts_.reference()) | |
Alexei Svitkine (slow)
2017/04/18 20:52:20
Nit: {}
Should this just call MountExistingCounts
bcwhite
2017/04/19 18:13:02
Done.
| |
298 set_counts( | |
299 static_cast<HistogramBase::AtomicCount*>(persistent_counts_.Get())); | |
300 } | |
301 | |
302 PersistentSampleVector::~PersistentSampleVector() {} | |
303 | |
304 bool PersistentSampleVector::MountExistingCountsStorage() const { | |
305 // There is no check that counts is not yet mounted because, given that this | |
306 // is a virtual function, it's more efficient to do that at the call-site. | |
307 // There is no danger, however, because at worst the counts value would be | |
308 // overwritten (in an atomic manner) with the exact same address. | |
309 | |
310 if (!persistent_counts_.reference()) | |
311 return false; // Nothing to mount. | |
312 | |
313 // Mount the counts array in position. | |
314 set_counts( | |
315 static_cast<HistogramBase::AtomicCount*>(persistent_counts_.Get())); | |
316 return true; | |
317 } | |
318 | |
319 HistogramBase::AtomicCount* | |
320 PersistentSampleVector::CreateCountsStorageWhileLocked() { | |
321 void* mem = persistent_counts_.Get(); | |
322 if (!mem) { | |
323 // The above shouldn't fail but can if Bad Things(tm) are occurring in the | |
324 // persistent allocator. Crashing isn't a good option so instead just | |
325 // allocate something from the heap and return that. There will be no | |
326 // sharing or persistence but worse things are already happening. | |
327 return new HistogramBase::AtomicCount[counts_size()]; | |
328 } | |
329 | |
330 return static_cast<HistogramBase::AtomicCount*>(mem); | |
331 } | |
332 | |
128 SampleVectorIterator::SampleVectorIterator( | 333 SampleVectorIterator::SampleVectorIterator( |
129 const std::vector<HistogramBase::AtomicCount>* counts, | 334 const std::vector<HistogramBase::AtomicCount>* counts, |
130 const BucketRanges* bucket_ranges) | 335 const BucketRanges* bucket_ranges) |
131 : counts_(&(*counts)[0]), | 336 : counts_(&(*counts)[0]), |
132 counts_size_(counts->size()), | 337 counts_size_(counts->size()), |
133 bucket_ranges_(bucket_ranges), | 338 bucket_ranges_(bucket_ranges), |
134 index_(0) { | 339 index_(0) { |
135 CHECK_GE(bucket_ranges_->bucket_count(), counts_size_); | 340 CHECK_GE(bucket_ranges_->bucket_count(), counts_size_); |
136 SkipEmptyBuckets(); | 341 SkipEmptyBuckets(); |
137 } | 342 } |
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
184 return; | 389 return; |
185 | 390 |
186 while (index_ < counts_size_) { | 391 while (index_ < counts_size_) { |
187 if (subtle::NoBarrier_Load(&counts_[index_]) != 0) | 392 if (subtle::NoBarrier_Load(&counts_[index_]) != 0) |
188 return; | 393 return; |
189 index_++; | 394 index_++; |
190 } | 395 } |
191 } | 396 } |
192 | 397 |
193 } // namespace base | 398 } // namespace base |
OLD | NEW |