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/sparse_histogram.h"
6 
7 #include <memory>
8 #include <string>
9 #include <vector>
10 
11 #include "base/logging.h"
12 #include "base/metrics/histogram_base.h"
13 #include "base/metrics/histogram_functions.h"
14 #include "base/metrics/histogram_samples.h"
15 #include "base/metrics/metrics_hashes.h"
16 #include "base/metrics/persistent_histogram_allocator.h"
17 #include "base/metrics/persistent_memory_allocator.h"
18 #include "base/metrics/sample_map.h"
19 #include "base/metrics/statistics_recorder.h"
20 #include "base/pickle.h"
21 #include "base/stl_util.h"
22 #include "base/strings/stringprintf.h"
23 #include "base/values.h"
24 #include "testing/gmock/include/gmock/gmock.h"
25 #include "testing/gtest/include/gtest/gtest.h"
26 
27 namespace base {
28 
29 // Test parameter indicates if a persistent memory allocator should be used
30 // for histogram allocation. False will allocate histograms from the process
31 // heap.
32 class SparseHistogramTest : public testing::TestWithParam<bool> {
33  public:
SparseHistogramTest()34   SparseHistogramTest() : use_persistent_histogram_allocator_(GetParam()) {}
35   SparseHistogramTest(const SparseHistogramTest&) = delete;
36   SparseHistogramTest& operator=(const SparseHistogramTest&) = delete;
37 
38  protected:
39   const int32_t kAllocatorMemorySize = 8 << 20;  // 8 MiB
40 
SetUp()41   void SetUp() override {
42     if (use_persistent_histogram_allocator_)
43       CreatePersistentMemoryAllocator();
44 
45     // Each test will have a clean state (no Histogram / BucketRanges
46     // registered).
47     InitializeStatisticsRecorder();
48   }
49 
TearDown()50   void TearDown() override {
51     if (allocator_) {
52       ASSERT_FALSE(allocator_->IsFull());
53       ASSERT_FALSE(allocator_->IsCorrupt());
54     }
55     UninitializeStatisticsRecorder();
56     DestroyPersistentMemoryAllocator();
57   }
58 
InitializeStatisticsRecorder()59   void InitializeStatisticsRecorder() {
60     DCHECK(!statistics_recorder_);
61     statistics_recorder_ = StatisticsRecorder::CreateTemporaryForTesting();
62   }
63 
UninitializeStatisticsRecorder()64   void UninitializeStatisticsRecorder() {
65     statistics_recorder_.reset();
66   }
67 
CreatePersistentMemoryAllocator()68   void CreatePersistentMemoryAllocator() {
69     GlobalHistogramAllocator::CreateWithLocalMemory(
70         kAllocatorMemorySize, 0, "SparseHistogramAllocatorTest");
71     allocator_ = GlobalHistogramAllocator::Get()->memory_allocator();
72   }
73 
DestroyPersistentMemoryAllocator()74   void DestroyPersistentMemoryAllocator() {
75     allocator_ = nullptr;
76     GlobalHistogramAllocator::ReleaseForTesting();
77   }
78 
NewSparseHistogram(const char * name)79   std::unique_ptr<SparseHistogram> NewSparseHistogram(const char* name) {
80     // std::make_unique can't access protected ctor so do it manually. This
81     // test class is a friend so can access it.
82     return std::unique_ptr<SparseHistogram>(new SparseHistogram(name));
83   }
84 
GetCountAndBucketData(SparseHistogram * histogram,base::Histogram::Count * count,int64_t * sum,base::ListValue * buckets)85   void GetCountAndBucketData(SparseHistogram* histogram,
86                              base::Histogram::Count* count,
87                              int64_t* sum,
88                              base::ListValue* buckets) {
89     // A simple wrapper around |GetCountAndBucketData| to make it visible for
90     // testing.
91     histogram->GetCountAndBucketData(count, sum, buckets);
92   }
93 
94   const bool use_persistent_histogram_allocator_;
95 
96   std::unique_ptr<StatisticsRecorder> statistics_recorder_;
97   PersistentMemoryAllocator* allocator_ = nullptr;
98 };
99 
100 // Run all HistogramTest cases with both heap and persistent memory.
101 INSTANTIATE_TEST_SUITE_P(HeapAndPersistent,
102                          SparseHistogramTest,
103                          testing::Bool());
104 
TEST_P(SparseHistogramTest,BasicTest)105 TEST_P(SparseHistogramTest, BasicTest) {
106   std::unique_ptr<SparseHistogram> histogram(NewSparseHistogram("Sparse"));
107   std::unique_ptr<HistogramSamples> snapshot(histogram->SnapshotSamples());
108   EXPECT_EQ(0, snapshot->TotalCount());
109   EXPECT_EQ(0, snapshot->sum());
110 
111   histogram->Add(100);
112   std::unique_ptr<HistogramSamples> snapshot1(histogram->SnapshotSamples());
113   EXPECT_EQ(1, snapshot1->TotalCount());
114   EXPECT_EQ(1, snapshot1->GetCount(100));
115 
116   histogram->Add(100);
117   histogram->Add(101);
118   std::unique_ptr<HistogramSamples> snapshot2(histogram->SnapshotSamples());
119   EXPECT_EQ(3, snapshot2->TotalCount());
120   EXPECT_EQ(2, snapshot2->GetCount(100));
121   EXPECT_EQ(1, snapshot2->GetCount(101));
122 }
123 
TEST_P(SparseHistogramTest,BasicTestAddCount)124 TEST_P(SparseHistogramTest, BasicTestAddCount) {
125   std::unique_ptr<SparseHistogram> histogram(NewSparseHistogram("Sparse"));
126   std::unique_ptr<HistogramSamples> snapshot(histogram->SnapshotSamples());
127   EXPECT_EQ(0, snapshot->TotalCount());
128   EXPECT_EQ(0, snapshot->sum());
129 
130   histogram->AddCount(100, 15);
131   std::unique_ptr<HistogramSamples> snapshot1(histogram->SnapshotSamples());
132   EXPECT_EQ(15, snapshot1->TotalCount());
133   EXPECT_EQ(15, snapshot1->GetCount(100));
134 
135   histogram->AddCount(100, 15);
136   histogram->AddCount(101, 25);
137   std::unique_ptr<HistogramSamples> snapshot2(histogram->SnapshotSamples());
138   EXPECT_EQ(55, snapshot2->TotalCount());
139   EXPECT_EQ(30, snapshot2->GetCount(100));
140   EXPECT_EQ(25, snapshot2->GetCount(101));
141 }
142 
TEST_P(SparseHistogramTest,AddCount_LargeValuesDontOverflow)143 TEST_P(SparseHistogramTest, AddCount_LargeValuesDontOverflow) {
144   std::unique_ptr<SparseHistogram> histogram(NewSparseHistogram("Sparse"));
145   std::unique_ptr<HistogramSamples> snapshot(histogram->SnapshotSamples());
146   EXPECT_EQ(0, snapshot->TotalCount());
147   EXPECT_EQ(0, snapshot->sum());
148 
149   histogram->AddCount(1000000000, 15);
150   std::unique_ptr<HistogramSamples> snapshot1(histogram->SnapshotSamples());
151   EXPECT_EQ(15, snapshot1->TotalCount());
152   EXPECT_EQ(15, snapshot1->GetCount(1000000000));
153 
154   histogram->AddCount(1000000000, 15);
155   histogram->AddCount(1010000000, 25);
156   std::unique_ptr<HistogramSamples> snapshot2(histogram->SnapshotSamples());
157   EXPECT_EQ(55, snapshot2->TotalCount());
158   EXPECT_EQ(30, snapshot2->GetCount(1000000000));
159   EXPECT_EQ(25, snapshot2->GetCount(1010000000));
160   EXPECT_EQ(55250000000LL, snapshot2->sum());
161 }
162 
163 // Make sure that counts returned by Histogram::SnapshotDelta do not overflow
164 // even when a total count (returned by Histogram::SnapshotSample) does.
TEST_P(SparseHistogramTest,AddCount_LargeCountsDontOverflow)165 TEST_P(SparseHistogramTest, AddCount_LargeCountsDontOverflow) {
166   std::unique_ptr<SparseHistogram> histogram(NewSparseHistogram("Sparse"));
167   std::unique_ptr<HistogramSamples> snapshot(histogram->SnapshotSamples());
168   EXPECT_EQ(0, snapshot->TotalCount());
169   EXPECT_EQ(0, snapshot->sum());
170 
171   const int count = (1 << 30) - 1;
172 
173   // Repeat N times to make sure that there is no internal value overflow.
174   for (int i = 0; i < 10; ++i) {
175     histogram->AddCount(42, count);
176     std::unique_ptr<HistogramSamples> samples = histogram->SnapshotDelta();
177     EXPECT_EQ(count, samples->TotalCount());
178     EXPECT_EQ(count, samples->GetCount(42));
179   }
180 }
181 
TEST_P(SparseHistogramTest,MacroBasicTest)182 TEST_P(SparseHistogramTest, MacroBasicTest) {
183   UmaHistogramSparse("Sparse", 100);
184   UmaHistogramSparse("Sparse", 200);
185   UmaHistogramSparse("Sparse", 100);
186 
187   const StatisticsRecorder::Histograms histograms =
188       StatisticsRecorder::GetHistograms();
189 
190   ASSERT_THAT(histograms, testing::SizeIs(1));
191   const HistogramBase* const sparse_histogram = histograms[0];
192 
193   EXPECT_EQ(SPARSE_HISTOGRAM, sparse_histogram->GetHistogramType());
194   EXPECT_EQ("Sparse", StringPiece(sparse_histogram->histogram_name()));
195   EXPECT_EQ(
196       HistogramBase::kUmaTargetedHistogramFlag |
197           (use_persistent_histogram_allocator_ ? HistogramBase::kIsPersistent
198                                                : 0),
199       sparse_histogram->flags());
200 
201   std::unique_ptr<HistogramSamples> samples =
202       sparse_histogram->SnapshotSamples();
203   EXPECT_EQ(3, samples->TotalCount());
204   EXPECT_EQ(2, samples->GetCount(100));
205   EXPECT_EQ(1, samples->GetCount(200));
206 }
207 
TEST_P(SparseHistogramTest,MacroInLoopTest)208 TEST_P(SparseHistogramTest, MacroInLoopTest) {
209   // Unlike the macros in histogram.h, SparseHistogram macros can have a
210   // variable as histogram name.
211   for (int i = 0; i < 2; i++) {
212     UmaHistogramSparse(StringPrintf("Sparse%d", i), 100);
213   }
214 
215   const StatisticsRecorder::Histograms histograms =
216       StatisticsRecorder::Sort(StatisticsRecorder::GetHistograms());
217   ASSERT_THAT(histograms, testing::SizeIs(2));
218   EXPECT_STREQ(histograms[0]->histogram_name(), "Sparse0");
219   EXPECT_STREQ(histograms[1]->histogram_name(), "Sparse1");
220 }
221 
TEST_P(SparseHistogramTest,Serialize)222 TEST_P(SparseHistogramTest, Serialize) {
223   std::unique_ptr<SparseHistogram> histogram(NewSparseHistogram("Sparse"));
224   histogram->SetFlags(HistogramBase::kIPCSerializationSourceFlag);
225 
226   Pickle pickle;
227   histogram->SerializeInfo(&pickle);
228 
229   PickleIterator iter(pickle);
230 
231   int type;
232   EXPECT_TRUE(iter.ReadInt(&type));
233   EXPECT_EQ(SPARSE_HISTOGRAM, type);
234 
235   std::string name;
236   EXPECT_TRUE(iter.ReadString(&name));
237   EXPECT_EQ("Sparse", name);
238 
239   int flag;
240   EXPECT_TRUE(iter.ReadInt(&flag));
241   EXPECT_EQ(HistogramBase::kIPCSerializationSourceFlag, flag);
242 
243   // No more data in the pickle.
244   EXPECT_FALSE(iter.SkipBytes(1));
245 }
246 
247 // Ensure that race conditions that cause multiple, identical sparse histograms
248 // to be created will safely resolve to a single one.
TEST_P(SparseHistogramTest,DuplicationSafety)249 TEST_P(SparseHistogramTest, DuplicationSafety) {
250   const char histogram_name[] = "Duplicated";
251   size_t histogram_count = StatisticsRecorder::GetHistogramCount();
252 
253   // Create a histogram that we will later duplicate.
254   HistogramBase* original =
255       SparseHistogram::FactoryGet(histogram_name, HistogramBase::kNoFlags);
256   ++histogram_count;
257   DCHECK_EQ(histogram_count, StatisticsRecorder::GetHistogramCount());
258   original->Add(1);
259 
260   // Create a duplicate. This has to happen differently depending on where the
261   // memory is taken from.
262   if (use_persistent_histogram_allocator_) {
263     // To allocate from persistent memory, clear the last_created reference in
264     // the GlobalHistogramAllocator. This will cause an Import to recreate
265     // the just-created histogram which will then be released as a duplicate.
266     GlobalHistogramAllocator::Get()->ClearLastCreatedReferenceForTesting();
267     // Creating a different histogram will first do an Import to ensure it
268     // hasn't been created elsewhere, triggering the duplication and release.
269     SparseHistogram::FactoryGet("something.new", HistogramBase::kNoFlags);
270     ++histogram_count;
271   } else {
272     // To allocate from the heap, just call the (private) constructor directly.
273     // Delete it immediately like would have happened within FactoryGet();
274     std::unique_ptr<SparseHistogram> something =
275         NewSparseHistogram(histogram_name);
276     DCHECK_NE(original, something.get());
277   }
278   DCHECK_EQ(histogram_count, StatisticsRecorder::GetHistogramCount());
279 
280   // Re-creating the histogram via FactoryGet() will return the same one.
281   HistogramBase* duplicate =
282       SparseHistogram::FactoryGet(histogram_name, HistogramBase::kNoFlags);
283   DCHECK_EQ(original, duplicate);
284   DCHECK_EQ(histogram_count, StatisticsRecorder::GetHistogramCount());
285   duplicate->Add(2);
286 
287   // Ensure that original histograms are still cross-functional.
288   original->Add(2);
289   duplicate->Add(1);
290   std::unique_ptr<HistogramSamples> snapshot_orig = original->SnapshotSamples();
291   std::unique_ptr<HistogramSamples> snapshot_dup = duplicate->SnapshotSamples();
292   DCHECK_EQ(2, snapshot_orig->GetCount(2));
293   DCHECK_EQ(2, snapshot_dup->GetCount(1));
294 }
295 
TEST_P(SparseHistogramTest,FactoryTime)296 TEST_P(SparseHistogramTest, FactoryTime) {
297   const int kTestCreateCount = 1 << 10;  // Must be power-of-2.
298   const int kTestLookupCount = 100000;
299   const int kTestAddCount = 100000;
300 
301   // Create all histogram names in advance for accurate timing below.
302   std::vector<std::string> histogram_names;
303   for (int i = 0; i < kTestCreateCount; ++i) {
304     histogram_names.push_back(
305         StringPrintf("TestHistogram.%d", i % kTestCreateCount));
306   }
307 
308   // Calculate cost of creating histograms.
309   TimeTicks create_start = TimeTicks::Now();
310   for (int i = 0; i < kTestCreateCount; ++i)
311     SparseHistogram::FactoryGet(histogram_names[i], HistogramBase::kNoFlags);
312   TimeDelta create_ticks = TimeTicks::Now() - create_start;
313   int64_t create_ms = create_ticks.InMilliseconds();
314 
315   VLOG(1) << kTestCreateCount << " histogram creations took " << create_ms
316           << "ms or about "
317           << (create_ms * 1000000) / kTestCreateCount
318           << "ns each.";
319 
320   // Calculate cost of looking up existing histograms.
321   TimeTicks lookup_start = TimeTicks::Now();
322   for (int i = 0; i < kTestLookupCount; ++i) {
323     // 6007 is co-prime with kTestCreateCount and so will do lookups in an
324     // order less likely to be cacheable (but still hit them all) should the
325     // underlying storage use the exact histogram name as the key.
326     const int i_mult = 6007;
327     static_assert(i_mult < INT_MAX / kTestCreateCount, "Multiplier too big");
328     int index = (i * i_mult) & (kTestCreateCount - 1);
329     SparseHistogram::FactoryGet(histogram_names[index],
330                                 HistogramBase::kNoFlags);
331   }
332   TimeDelta lookup_ticks = TimeTicks::Now() - lookup_start;
333   int64_t lookup_ms = lookup_ticks.InMilliseconds();
334 
335   VLOG(1) << kTestLookupCount << " histogram lookups took " << lookup_ms
336           << "ms or about "
337           << (lookup_ms * 1000000) / kTestLookupCount
338           << "ns each.";
339 
340   // Calculate cost of accessing histograms.
341   HistogramBase* histogram =
342       SparseHistogram::FactoryGet(histogram_names[0], HistogramBase::kNoFlags);
343   ASSERT_TRUE(histogram);
344   TimeTicks add_start = TimeTicks::Now();
345   for (int i = 0; i < kTestAddCount; ++i)
346     histogram->Add(i & 127);
347   TimeDelta add_ticks = TimeTicks::Now() - add_start;
348   int64_t add_ms = add_ticks.InMilliseconds();
349 
350   VLOG(1) << kTestAddCount << " histogram adds took " << add_ms
351           << "ms or about "
352           << (add_ms * 1000000) / kTestAddCount
353           << "ns each.";
354 }
355 
TEST_P(SparseHistogramTest,ExtremeValues)356 TEST_P(SparseHistogramTest, ExtremeValues) {
357   static const struct {
358     Histogram::Sample sample;
359     int64_t expected_max;
360   } cases[] = {
361       // Note: We use -2147483647 - 1 rather than -2147483648 because the later
362       // is interpreted as - operator applied to 2147483648 and the latter can't
363       // be represented as an int32 and causes a warning.
364       {-2147483647 - 1, -2147483647LL},
365       {0, 1},
366       {2147483647, 2147483648LL},
367   };
368 
369   for (size_t i = 0; i < base::size(cases); ++i) {
370     HistogramBase* histogram =
371         SparseHistogram::FactoryGet(StringPrintf("ExtremeValues_%zu", i),
372                                     HistogramBase::kUmaTargetedHistogramFlag);
373     histogram->Add(cases[i].sample);
374 
375     std::unique_ptr<HistogramSamples> snapshot = histogram->SnapshotSamples();
376     std::unique_ptr<SampleCountIterator> it = snapshot->Iterator();
377     ASSERT_FALSE(it->Done());
378 
379     base::Histogram::Sample min;
380     int64_t max;
381     base::Histogram::Count count;
382     it->Get(&min, &max, &count);
383 
384     EXPECT_EQ(1, count);
385     EXPECT_EQ(cases[i].sample, min);
386     EXPECT_EQ(cases[i].expected_max, max);
387 
388     it->Next();
389     EXPECT_TRUE(it->Done());
390   }
391 }
392 
TEST_P(SparseHistogramTest,HistogramNameHash)393 TEST_P(SparseHistogramTest, HistogramNameHash) {
394   const char kName[] = "TestName";
395   HistogramBase* histogram = SparseHistogram::FactoryGet(
396       kName, HistogramBase::kUmaTargetedHistogramFlag);
397   EXPECT_EQ(histogram->name_hash(), HashMetricName(kName));
398 }
399 
TEST_P(SparseHistogramTest,CheckGetCountAndBucketData)400 TEST_P(SparseHistogramTest, CheckGetCountAndBucketData) {
401   std::unique_ptr<SparseHistogram> histogram(NewSparseHistogram("Sparse"));
402   // Add samples in reverse order and make sure the output is in correct order.
403   histogram->AddCount(/*sample=*/200, /*count=*/15);
404   histogram->AddCount(/*sample=*/100, /*count=*/5);
405   // Add samples to the same bucket and make sure they'll be aggregated.
406   histogram->AddCount(/*sample=*/100, /*count=*/5);
407 
408   base::Histogram::Count total_count;
409   int64_t sum;
410   base::ListValue buckets;
411   GetCountAndBucketData(histogram.get(), &total_count, &sum, &buckets);
412   EXPECT_EQ(25, total_count);
413   EXPECT_EQ(4000, sum);
414   EXPECT_EQ(2u, buckets.GetSize());
415 
416   int low, high, count;
417   // Check the first bucket.
418   base::DictionaryValue* bucket1;
419   EXPECT_TRUE(buckets.GetDictionary(0, &bucket1));
420   EXPECT_TRUE(bucket1->GetInteger("low", &low));
421   EXPECT_TRUE(bucket1->GetInteger("high", &high));
422   EXPECT_TRUE(bucket1->GetInteger("count", &count));
423   EXPECT_EQ(100, low);
424   EXPECT_EQ(101, high);
425   EXPECT_EQ(10, count);
426 
427   // Check the second bucket.
428   base::DictionaryValue* bucket2;
429   EXPECT_TRUE(buckets.GetDictionary(1, &bucket2));
430   EXPECT_TRUE(bucket2->GetInteger("low", &low));
431   EXPECT_TRUE(bucket2->GetInteger("high", &high));
432   EXPECT_TRUE(bucket2->GetInteger("count", &count));
433   EXPECT_EQ(200, low);
434   EXPECT_EQ(201, high);
435   EXPECT_EQ(15, count);
436 }
437 
TEST_P(SparseHistogramTest,WriteAscii)438 TEST_P(SparseHistogramTest, WriteAscii) {
439   HistogramBase* histogram =
440       SparseHistogram::FactoryGet("AsciiOut", HistogramBase::kNoFlags);
441   histogram->AddCount(/*sample=*/4, /*count=*/5);
442   histogram->AddCount(/*sample=*/10, /*count=*/15);
443 
444   std::string output;
445   histogram->WriteAscii(&output);
446 
447   const char kOutputFormatRe[] =
448       R"(Histogram: AsciiOut recorded 20 samples.*\n)"
449       R"(4   -+O +\(5 = 25.0%\)\n)"
450       R"(10  -+O +\(15 = 75.0%\)\n)";
451 
452   EXPECT_THAT(output, testing::MatchesRegex(kOutputFormatRe));
453 }
454 
TEST_P(SparseHistogramTest,ToGraphDict)455 TEST_P(SparseHistogramTest, ToGraphDict) {
456   HistogramBase* histogram =
457       SparseHistogram::FactoryGet("HTMLOut", HistogramBase::kNoFlags);
458   histogram->AddCount(/*sample=*/4, /*count=*/5);
459   histogram->AddCount(/*sample=*/10, /*count=*/15);
460 
461   base::DictionaryValue output = histogram->ToGraphDict();
462   std::string* header = output.FindStringKey("header");
463   std::string* body = output.FindStringKey("body");
464 
465   const char kOutputHeaderFormatRe[] =
466       R"(Histogram: HTMLOut recorded 20 samples.*)";
467   const char kOutputBodyFormatRe[] = R"(4   -+O +\(5 = 25.0%\)\n)"
468                                      R"(10  -+O +\(15 = 75.0%\)\n)";
469 
470   EXPECT_THAT(*header, testing::MatchesRegex(kOutputHeaderFormatRe));
471   EXPECT_THAT(*body, testing::MatchesRegex(kOutputBodyFormatRe));
472 }
473 
474 }  // namespace base
475