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/sample_vector.h"
6
7 #include <limits.h>
8 #include <stddef.h>
9
10 #include <atomic>
11 #include <memory>
12 #include <vector>
13
14 #include "base/metrics/bucket_ranges.h"
15 #include "base/metrics/histogram.h"
16 #include "base/metrics/persistent_memory_allocator.h"
17 #include "base/test/gtest_util.h"
18 #include "testing/gtest/include/gtest/gtest.h"
19
20 namespace base {
21
22 // This framework class has "friend" access to the SampleVector for accessing
23 // non-public methods and fields.
24 class SampleVectorTest : public testing::Test {
25 public:
GetSamplesCounts(const SampleVectorBase & samples)26 const HistogramBase::AtomicCount* GetSamplesCounts(
27 const SampleVectorBase& samples) {
28 return samples.counts();
29 }
30 };
31
TEST_F(SampleVectorTest,Accumulate)32 TEST_F(SampleVectorTest, Accumulate) {
33 // Custom buckets: [1, 5) [5, 10)
34 BucketRanges ranges(3);
35 ranges.set_range(0, 1);
36 ranges.set_range(1, 5);
37 ranges.set_range(2, 10);
38 SampleVector samples(1, &ranges);
39
40 samples.Accumulate(1, 200);
41 samples.Accumulate(2, -300);
42 EXPECT_EQ(-100, samples.GetCountAtIndex(0));
43
44 samples.Accumulate(5, 200);
45 EXPECT_EQ(200, samples.GetCountAtIndex(1));
46
47 EXPECT_EQ(600, samples.sum());
48 EXPECT_EQ(100, samples.redundant_count());
49 EXPECT_EQ(samples.TotalCount(), samples.redundant_count());
50
51 samples.Accumulate(5, -100);
52 EXPECT_EQ(100, samples.GetCountAtIndex(1));
53
54 EXPECT_EQ(100, samples.sum());
55 EXPECT_EQ(0, samples.redundant_count());
56 EXPECT_EQ(samples.TotalCount(), samples.redundant_count());
57 }
58
TEST_F(SampleVectorTest,Accumulate_LargeValuesDontOverflow)59 TEST_F(SampleVectorTest, Accumulate_LargeValuesDontOverflow) {
60 // Custom buckets: [1, 250000000) [250000000, 500000000)
61 BucketRanges ranges(3);
62 ranges.set_range(0, 1);
63 ranges.set_range(1, 250000000);
64 ranges.set_range(2, 500000000);
65 SampleVector samples(1, &ranges);
66
67 samples.Accumulate(240000000, 200);
68 samples.Accumulate(249999999, -300);
69 EXPECT_EQ(-100, samples.GetCountAtIndex(0));
70
71 samples.Accumulate(250000000, 200);
72 EXPECT_EQ(200, samples.GetCountAtIndex(1));
73
74 EXPECT_EQ(23000000300LL, samples.sum());
75 EXPECT_EQ(100, samples.redundant_count());
76 EXPECT_EQ(samples.TotalCount(), samples.redundant_count());
77
78 samples.Accumulate(250000000, -100);
79 EXPECT_EQ(100, samples.GetCountAtIndex(1));
80
81 EXPECT_EQ(-1999999700LL, samples.sum());
82 EXPECT_EQ(0, samples.redundant_count());
83 EXPECT_EQ(samples.TotalCount(), samples.redundant_count());
84 }
85
TEST_F(SampleVectorTest,AddSubtract)86 TEST_F(SampleVectorTest, AddSubtract) {
87 // Custom buckets: [0, 1) [1, 2) [2, 3) [3, INT_MAX)
88 BucketRanges ranges(5);
89 ranges.set_range(0, 0);
90 ranges.set_range(1, 1);
91 ranges.set_range(2, 2);
92 ranges.set_range(3, 3);
93 ranges.set_range(4, INT_MAX);
94
95 SampleVector samples1(1, &ranges);
96 samples1.Accumulate(0, 100);
97 samples1.Accumulate(2, 100);
98 samples1.Accumulate(4, 100);
99 EXPECT_EQ(600, samples1.sum());
100 EXPECT_EQ(300, samples1.TotalCount());
101 EXPECT_EQ(samples1.redundant_count(), samples1.TotalCount());
102
103 SampleVector samples2(2, &ranges);
104 samples2.Accumulate(1, 200);
105 samples2.Accumulate(2, 200);
106 samples2.Accumulate(4, 200);
107 EXPECT_EQ(1400, samples2.sum());
108 EXPECT_EQ(600, samples2.TotalCount());
109 EXPECT_EQ(samples2.redundant_count(), samples2.TotalCount());
110
111 samples1.Add(samples2);
112 EXPECT_EQ(100, samples1.GetCountAtIndex(0));
113 EXPECT_EQ(200, samples1.GetCountAtIndex(1));
114 EXPECT_EQ(300, samples1.GetCountAtIndex(2));
115 EXPECT_EQ(300, samples1.GetCountAtIndex(3));
116 EXPECT_EQ(2000, samples1.sum());
117 EXPECT_EQ(900, samples1.TotalCount());
118 EXPECT_EQ(samples1.redundant_count(), samples1.TotalCount());
119
120 samples1.Subtract(samples2);
121 EXPECT_EQ(100, samples1.GetCountAtIndex(0));
122 EXPECT_EQ(0, samples1.GetCountAtIndex(1));
123 EXPECT_EQ(100, samples1.GetCountAtIndex(2));
124 EXPECT_EQ(100, samples1.GetCountAtIndex(3));
125 EXPECT_EQ(600, samples1.sum());
126 EXPECT_EQ(300, samples1.TotalCount());
127 EXPECT_EQ(samples1.redundant_count(), samples1.TotalCount());
128 }
129
TEST_F(SampleVectorTest,BucketIndexDeath)130 TEST_F(SampleVectorTest, BucketIndexDeath) {
131 // 8 buckets with exponential layout:
132 // [0, 1) [1, 2) [2, 4) [4, 8) [8, 16) [16, 32) [32, 64) [64, INT_MAX)
133 BucketRanges ranges(9);
134 Histogram::InitializeBucketRanges(1, 64, &ranges);
135 SampleVector samples(1, &ranges);
136
137 // Normal case
138 samples.Accumulate(0, 1);
139 samples.Accumulate(3, 2);
140 samples.Accumulate(64, 3);
141 EXPECT_EQ(1, samples.GetCount(0));
142 EXPECT_EQ(2, samples.GetCount(2));
143 EXPECT_EQ(3, samples.GetCount(65));
144
145 // Extreme case.
146 EXPECT_DEATH_IF_SUPPORTED(samples.Accumulate(INT_MIN, 100), "");
147 EXPECT_DEATH_IF_SUPPORTED(samples.Accumulate(-1, 100), "");
148 EXPECT_DEATH_IF_SUPPORTED(samples.Accumulate(INT_MAX, 100), "");
149
150 // Custom buckets: [1, 5) [5, 10)
151 // Note, this is not a valid BucketRanges for Histogram because it does not
152 // have overflow buckets.
153 BucketRanges ranges2(3);
154 ranges2.set_range(0, 1);
155 ranges2.set_range(1, 5);
156 ranges2.set_range(2, 10);
157 SampleVector samples2(2, &ranges2);
158
159 // Normal case.
160 samples2.Accumulate(1, 1);
161 samples2.Accumulate(4, 1);
162 samples2.Accumulate(5, 2);
163 samples2.Accumulate(9, 2);
164 EXPECT_EQ(2, samples2.GetCount(1));
165 EXPECT_EQ(4, samples2.GetCount(5));
166
167 // Extreme case.
168 EXPECT_DEATH_IF_SUPPORTED(samples2.Accumulate(0, 100), "");
169 EXPECT_DEATH_IF_SUPPORTED(samples2.Accumulate(10, 100), "");
170 }
171
TEST_F(SampleVectorTest,AddSubtractBucketNotMatchDeath)172 TEST_F(SampleVectorTest, AddSubtractBucketNotMatchDeath) {
173 // Custom buckets 1: [1, 3) [3, 5)
174 BucketRanges ranges1(3);
175 ranges1.set_range(0, 1);
176 ranges1.set_range(1, 3);
177 ranges1.set_range(2, 5);
178 SampleVector samples1(1, &ranges1);
179
180 // Custom buckets 2: [0, 1) [1, 3) [3, 6) [6, 7)
181 BucketRanges ranges2(5);
182 ranges2.set_range(0, 0);
183 ranges2.set_range(1, 1);
184 ranges2.set_range(2, 3);
185 ranges2.set_range(3, 6);
186 ranges2.set_range(4, 7);
187 SampleVector samples2(2, &ranges2);
188
189 samples2.Accumulate(1, 100);
190 samples1.Add(samples2);
191 EXPECT_EQ(100, samples1.GetCountAtIndex(0));
192
193 // Extra bucket in the beginning. These should CHECK in GetBucketIndex.
194 samples2.Accumulate(0, 100);
195 EXPECT_DEATH_IF_SUPPORTED(samples1.Add(samples2), "");
196 EXPECT_DEATH_IF_SUPPORTED(samples1.Subtract(samples2), "");
197
198 // Extra bucket in the end. These should cause AddSubtractImpl to fail, and
199 // Add to DCHECK as a result.
200 samples2.Accumulate(0, -100);
201 samples2.Accumulate(6, 100);
202 EXPECT_DCHECK_DEATH(samples1.Add(samples2));
203 EXPECT_DCHECK_DEATH(samples1.Subtract(samples2));
204
205 // Bucket not match: [3, 5) VS [3, 6). These should cause AddSubtractImpl to
206 // DCHECK.
207 samples2.Accumulate(6, -100);
208 samples2.Accumulate(3, 100);
209 EXPECT_DCHECK_DEATH(samples1.Add(samples2));
210 EXPECT_DCHECK_DEATH(samples1.Subtract(samples2));
211 }
212
TEST_F(SampleVectorTest,Iterate)213 TEST_F(SampleVectorTest, Iterate) {
214 BucketRanges ranges(5);
215 ranges.set_range(0, 0);
216 ranges.set_range(1, 1);
217 ranges.set_range(2, 2);
218 ranges.set_range(3, 3);
219 ranges.set_range(4, 4);
220
221 std::vector<HistogramBase::Count> counts(3);
222 counts[0] = 1;
223 counts[1] = 0; // Iterator will bypass this empty bucket.
224 counts[2] = 2;
225
226 // BucketRanges can have larger size than counts.
227 SampleVectorIterator it(&counts, &ranges);
228 size_t index;
229
230 HistogramBase::Sample min;
231 int64_t max;
232 HistogramBase::Count count;
233 it.Get(&min, &max, &count);
234 EXPECT_EQ(0, min);
235 EXPECT_EQ(1, max);
236 EXPECT_EQ(1, count);
237 EXPECT_TRUE(it.GetBucketIndex(&index));
238 EXPECT_EQ(0u, index);
239
240 it.Next();
241 it.Get(&min, &max, &count);
242 EXPECT_EQ(2, min);
243 EXPECT_EQ(3, max);
244 EXPECT_EQ(2, count);
245 EXPECT_TRUE(it.GetBucketIndex(&index));
246 EXPECT_EQ(2u, index);
247
248 it.Next();
249 EXPECT_TRUE(it.Done());
250
251 // Create iterator from SampleVector.
252 SampleVector samples(1, &ranges);
253 samples.Accumulate(0, 0);
254 samples.Accumulate(1, 1);
255 samples.Accumulate(2, 2);
256 samples.Accumulate(3, 3);
257 std::unique_ptr<SampleCountIterator> it2 = samples.Iterator();
258
259 int i;
260 for (i = 1; !it2->Done(); i++, it2->Next()) {
261 it2->Get(&min, &max, &count);
262 EXPECT_EQ(i, min);
263 EXPECT_EQ(i + 1, max);
264 EXPECT_EQ(i, count);
265
266 size_t index;
267 EXPECT_TRUE(it2->GetBucketIndex(&index));
268 EXPECT_EQ(static_cast<size_t>(i), index);
269 }
270 EXPECT_EQ(4, i);
271 }
272
TEST_F(SampleVectorTest,IterateDoneDeath)273 TEST_F(SampleVectorTest, IterateDoneDeath) {
274 BucketRanges ranges(5);
275 ranges.set_range(0, 0);
276 ranges.set_range(1, 1);
277 ranges.set_range(2, 2);
278 ranges.set_range(3, 3);
279 ranges.set_range(4, INT_MAX);
280 SampleVector samples(1, &ranges);
281
282 std::unique_ptr<SampleCountIterator> it = samples.Iterator();
283
284 EXPECT_TRUE(it->Done());
285
286 HistogramBase::Sample min;
287 int64_t max;
288 HistogramBase::Count count;
289 EXPECT_DCHECK_DEATH(it->Get(&min, &max, &count));
290
291 EXPECT_DCHECK_DEATH(it->Next());
292
293 samples.Accumulate(2, 100);
294 it = samples.Iterator();
295 EXPECT_FALSE(it->Done());
296 }
297
TEST_F(SampleVectorTest,SingleSample)298 TEST_F(SampleVectorTest, SingleSample) {
299 // Custom buckets: [1, 5) [5, 10)
300 BucketRanges ranges(3);
301 ranges.set_range(0, 1);
302 ranges.set_range(1, 5);
303 ranges.set_range(2, 10);
304 SampleVector samples(&ranges);
305
306 // Ensure that a single value accumulates correctly.
307 EXPECT_FALSE(GetSamplesCounts(samples));
308 samples.Accumulate(3, 200);
309 EXPECT_EQ(200, samples.GetCount(3));
310 EXPECT_FALSE(GetSamplesCounts(samples));
311 samples.Accumulate(3, 400);
312 EXPECT_EQ(600, samples.GetCount(3));
313 EXPECT_FALSE(GetSamplesCounts(samples));
314 EXPECT_EQ(3 * 600, samples.sum());
315 EXPECT_EQ(600, samples.TotalCount());
316 EXPECT_EQ(600, samples.redundant_count());
317
318 // Ensure that the iterator returns only one value.
319 HistogramBase::Sample min;
320 int64_t max;
321 HistogramBase::Count count;
322 std::unique_ptr<SampleCountIterator> it = samples.Iterator();
323 ASSERT_FALSE(it->Done());
324 it->Get(&min, &max, &count);
325 EXPECT_EQ(1, min);
326 EXPECT_EQ(5, max);
327 EXPECT_EQ(600, count);
328 it->Next();
329 EXPECT_TRUE(it->Done());
330
331 // Ensure that it can be merged to another single-sample vector.
332 SampleVector samples_copy(&ranges);
333 samples_copy.Add(samples);
334 EXPECT_FALSE(GetSamplesCounts(samples_copy));
335 EXPECT_EQ(3 * 600, samples_copy.sum());
336 EXPECT_EQ(600, samples_copy.TotalCount());
337 EXPECT_EQ(600, samples_copy.redundant_count());
338
339 // A different value should cause creation of the counts array.
340 samples.Accumulate(8, 100);
341 EXPECT_TRUE(GetSamplesCounts(samples));
342 EXPECT_EQ(600, samples.GetCount(3));
343 EXPECT_EQ(100, samples.GetCount(8));
344 EXPECT_EQ(3 * 600 + 8 * 100, samples.sum());
345 EXPECT_EQ(600 + 100, samples.TotalCount());
346 EXPECT_EQ(600 + 100, samples.redundant_count());
347
348 // The iterator should now return both values.
349 it = samples.Iterator();
350 ASSERT_FALSE(it->Done());
351 it->Get(&min, &max, &count);
352 EXPECT_EQ(1, min);
353 EXPECT_EQ(5, max);
354 EXPECT_EQ(600, count);
355 it->Next();
356 ASSERT_FALSE(it->Done());
357 it->Get(&min, &max, &count);
358 EXPECT_EQ(5, min);
359 EXPECT_EQ(10, max);
360 EXPECT_EQ(100, count);
361 it->Next();
362 EXPECT_TRUE(it->Done());
363
364 // Ensure that it can merged to a single-sample vector.
365 samples_copy.Add(samples);
366 EXPECT_TRUE(GetSamplesCounts(samples_copy));
367 EXPECT_EQ(3 * 1200 + 8 * 100, samples_copy.sum());
368 EXPECT_EQ(1200 + 100, samples_copy.TotalCount());
369 EXPECT_EQ(1200 + 100, samples_copy.redundant_count());
370 }
371
TEST_F(SampleVectorTest,PersistentSampleVector)372 TEST_F(SampleVectorTest, PersistentSampleVector) {
373 LocalPersistentMemoryAllocator allocator(64 << 10, 0, "");
374 std::atomic<PersistentMemoryAllocator::Reference> samples_ref;
375 samples_ref.store(0, std::memory_order_relaxed);
376 HistogramSamples::Metadata samples_meta;
377 memset(&samples_meta, 0, sizeof(samples_meta));
378
379 // Custom buckets: [1, 5) [5, 10)
380 BucketRanges ranges(3);
381 ranges.set_range(0, 1);
382 ranges.set_range(1, 5);
383 ranges.set_range(2, 10);
384
385 // Persistent allocation.
386 const size_t counts_bytes =
387 sizeof(HistogramBase::AtomicCount) * ranges.bucket_count();
388 const DelayedPersistentAllocation allocation(&allocator, &samples_ref, 1,
389 counts_bytes, false);
390
391 PersistentSampleVector samples1(0, &ranges, &samples_meta, allocation);
392 EXPECT_FALSE(GetSamplesCounts(samples1));
393 samples1.Accumulate(3, 200);
394 EXPECT_EQ(200, samples1.GetCount(3));
395 EXPECT_FALSE(GetSamplesCounts(samples1));
396 EXPECT_EQ(0, samples1.GetCount(8));
397 EXPECT_FALSE(GetSamplesCounts(samples1));
398
399 PersistentSampleVector samples2(0, &ranges, &samples_meta, allocation);
400 EXPECT_EQ(200, samples2.GetCount(3));
401 EXPECT_FALSE(GetSamplesCounts(samples2));
402
403 HistogramBase::Sample min;
404 int64_t max;
405 HistogramBase::Count count;
406 std::unique_ptr<SampleCountIterator> it = samples2.Iterator();
407 ASSERT_FALSE(it->Done());
408 it->Get(&min, &max, &count);
409 EXPECT_EQ(1, min);
410 EXPECT_EQ(5, max);
411 EXPECT_EQ(200, count);
412 it->Next();
413 EXPECT_TRUE(it->Done());
414
415 samples1.Accumulate(8, 100);
416 EXPECT_TRUE(GetSamplesCounts(samples1));
417
418 EXPECT_FALSE(GetSamplesCounts(samples2));
419 EXPECT_EQ(200, samples2.GetCount(3));
420 EXPECT_EQ(100, samples2.GetCount(8));
421 EXPECT_TRUE(GetSamplesCounts(samples2));
422 EXPECT_EQ(3 * 200 + 8 * 100, samples2.sum());
423 EXPECT_EQ(300, samples2.TotalCount());
424 EXPECT_EQ(300, samples2.redundant_count());
425
426 it = samples2.Iterator();
427 ASSERT_FALSE(it->Done());
428 it->Get(&min, &max, &count);
429 EXPECT_EQ(1, min);
430 EXPECT_EQ(5, max);
431 EXPECT_EQ(200, count);
432 it->Next();
433 ASSERT_FALSE(it->Done());
434 it->Get(&min, &max, &count);
435 EXPECT_EQ(5, min);
436 EXPECT_EQ(10, max);
437 EXPECT_EQ(100, count);
438 it->Next();
439 EXPECT_TRUE(it->Done());
440
441 PersistentSampleVector samples3(0, &ranges, &samples_meta, allocation);
442 EXPECT_TRUE(GetSamplesCounts(samples2));
443 EXPECT_EQ(200, samples3.GetCount(3));
444 EXPECT_EQ(100, samples3.GetCount(8));
445 EXPECT_EQ(3 * 200 + 8 * 100, samples3.sum());
446 EXPECT_EQ(300, samples3.TotalCount());
447 EXPECT_EQ(300, samples3.redundant_count());
448
449 it = samples3.Iterator();
450 ASSERT_FALSE(it->Done());
451 it->Get(&min, &max, &count);
452 EXPECT_EQ(1, min);
453 EXPECT_EQ(5, max);
454 EXPECT_EQ(200, count);
455 it->Next();
456 ASSERT_FALSE(it->Done());
457 it->Get(&min, &max, &count);
458 EXPECT_EQ(5, min);
459 EXPECT_EQ(10, max);
460 EXPECT_EQ(100, count);
461 it->Next();
462 EXPECT_TRUE(it->Done());
463 }
464
TEST_F(SampleVectorTest,PersistentSampleVectorTestWithOutsideAlloc)465 TEST_F(SampleVectorTest, PersistentSampleVectorTestWithOutsideAlloc) {
466 LocalPersistentMemoryAllocator allocator(64 << 10, 0, "");
467 std::atomic<PersistentMemoryAllocator::Reference> samples_ref;
468 samples_ref.store(0, std::memory_order_relaxed);
469 HistogramSamples::Metadata samples_meta;
470 memset(&samples_meta, 0, sizeof(samples_meta));
471
472 // Custom buckets: [1, 5) [5, 10)
473 BucketRanges ranges(3);
474 ranges.set_range(0, 1);
475 ranges.set_range(1, 5);
476 ranges.set_range(2, 10);
477
478 // Persistent allocation.
479 const size_t counts_bytes =
480 sizeof(HistogramBase::AtomicCount) * ranges.bucket_count();
481 const DelayedPersistentAllocation allocation(&allocator, &samples_ref, 1,
482 counts_bytes, false);
483
484 PersistentSampleVector samples1(0, &ranges, &samples_meta, allocation);
485 EXPECT_FALSE(GetSamplesCounts(samples1));
486 samples1.Accumulate(3, 200);
487 EXPECT_EQ(200, samples1.GetCount(3));
488 EXPECT_FALSE(GetSamplesCounts(samples1));
489
490 // Because the delayed allocation can be shared with other objects (the
491 // |offset| parameter allows concatinating multiple data blocks into the
492 // same allocation), it's possible that the allocation gets realized from
493 // the outside even though the data block being accessed is all zero.
494 allocation.Get();
495 EXPECT_EQ(200, samples1.GetCount(3));
496 EXPECT_FALSE(GetSamplesCounts(samples1));
497
498 HistogramBase::Sample min;
499 int64_t max;
500 HistogramBase::Count count;
501 std::unique_ptr<SampleCountIterator> it = samples1.Iterator();
502 ASSERT_FALSE(it->Done());
503 it->Get(&min, &max, &count);
504 EXPECT_EQ(1, min);
505 EXPECT_EQ(5, max);
506 EXPECT_EQ(200, count);
507 it->Next();
508 EXPECT_TRUE(it->Done());
509
510 // A duplicate samples object should still see the single-sample entry even
511 // when storage is available.
512 PersistentSampleVector samples2(0, &ranges, &samples_meta, allocation);
513 EXPECT_EQ(200, samples2.GetCount(3));
514
515 // New accumulations, in both directions, of the existing value should work.
516 samples1.Accumulate(3, 50);
517 EXPECT_EQ(250, samples1.GetCount(3));
518 EXPECT_EQ(250, samples2.GetCount(3));
519 samples2.Accumulate(3, 50);
520 EXPECT_EQ(300, samples1.GetCount(3));
521 EXPECT_EQ(300, samples2.GetCount(3));
522
523 it = samples1.Iterator();
524 ASSERT_FALSE(it->Done());
525 it->Get(&min, &max, &count);
526 EXPECT_EQ(1, min);
527 EXPECT_EQ(5, max);
528 EXPECT_EQ(300, count);
529 it->Next();
530 EXPECT_TRUE(it->Done());
531
532 samples1.Accumulate(8, 100);
533 EXPECT_TRUE(GetSamplesCounts(samples1));
534 EXPECT_EQ(300, samples1.GetCount(3));
535 EXPECT_EQ(300, samples2.GetCount(3));
536 EXPECT_EQ(100, samples1.GetCount(8));
537 EXPECT_EQ(100, samples2.GetCount(8));
538 samples2.Accumulate(8, 100);
539 EXPECT_EQ(300, samples1.GetCount(3));
540 EXPECT_EQ(300, samples2.GetCount(3));
541 EXPECT_EQ(200, samples1.GetCount(8));
542 EXPECT_EQ(200, samples2.GetCount(8));
543 }
544
545 } // namespace base
546