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