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