// Copyright (c) 2012 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "base/metrics/sparse_histogram.h"

#include <memory>
#include <string>

#include "base/metrics/histogram_base.h"
#include "base/metrics/histogram_macros.h"
#include "base/metrics/histogram_samples.h"
#include "base/metrics/persistent_histogram_allocator.h"
#include "base/metrics/persistent_memory_allocator.h"
#include "base/metrics/sample_map.h"
#include "base/metrics/statistics_recorder.h"
#include "base/pickle.h"
#include "base/strings/stringprintf.h"
#include "testing/gtest/include/gtest/gtest.h"

namespace base {

// Test parameter indicates if a persistent memory allocator should be used
// for histogram allocation. False will allocate histograms from the process
// heap.
class SparseHistogramTest : public testing::TestWithParam<bool> {
 protected:
  const int32_t kAllocatorMemorySize = 8 << 20;  // 8 MiB

  SparseHistogramTest() : use_persistent_histogram_allocator_(GetParam()) {}

  void SetUp() override {
    if (use_persistent_histogram_allocator_)
      CreatePersistentMemoryAllocator();

    // Each test will have a clean state (no Histogram / BucketRanges
    // registered).
    InitializeStatisticsRecorder();
  }

  void TearDown() override {
    if (allocator_) {
      ASSERT_FALSE(allocator_->IsFull());
      ASSERT_FALSE(allocator_->IsCorrupt());
    }
    UninitializeStatisticsRecorder();
    DestroyPersistentMemoryAllocator();
  }

  void InitializeStatisticsRecorder() {
    DCHECK(!statistics_recorder_);
    statistics_recorder_ = StatisticsRecorder::CreateTemporaryForTesting();
  }

  void UninitializeStatisticsRecorder() {
    statistics_recorder_.reset();
  }

  void CreatePersistentMemoryAllocator() {
    // By getting the results-histogram before any persistent allocator
    // is attached, that histogram is guaranteed not to be stored in
    // any persistent memory segment (which simplifies some tests).
    GlobalHistogramAllocator::GetCreateHistogramResultHistogram();

    GlobalHistogramAllocator::CreateWithLocalMemory(
        kAllocatorMemorySize, 0, "SparseHistogramAllocatorTest");
    allocator_ = GlobalHistogramAllocator::Get()->memory_allocator();
  }

  void DestroyPersistentMemoryAllocator() {
    allocator_ = nullptr;
    GlobalHistogramAllocator::ReleaseForTesting();
  }

  std::unique_ptr<SparseHistogram> NewSparseHistogram(const std::string& name) {
    return std::unique_ptr<SparseHistogram>(new SparseHistogram(name));
  }

  const bool use_persistent_histogram_allocator_;

  std::unique_ptr<StatisticsRecorder> statistics_recorder_;
  PersistentMemoryAllocator* allocator_ = nullptr;

 private:
  DISALLOW_COPY_AND_ASSIGN(SparseHistogramTest);
};

// Run all HistogramTest cases with both heap and persistent memory.
INSTANTIATE_TEST_CASE_P(HeapAndPersistent,
                        SparseHistogramTest,
                        testing::Bool());


TEST_P(SparseHistogramTest, BasicTest) {
  std::unique_ptr<SparseHistogram> histogram(NewSparseHistogram("Sparse"));
  std::unique_ptr<HistogramSamples> snapshot(histogram->SnapshotSamples());
  EXPECT_EQ(0, snapshot->TotalCount());
  EXPECT_EQ(0, snapshot->sum());

  histogram->Add(100);
  std::unique_ptr<HistogramSamples> snapshot1(histogram->SnapshotSamples());
  EXPECT_EQ(1, snapshot1->TotalCount());
  EXPECT_EQ(1, snapshot1->GetCount(100));

  histogram->Add(100);
  histogram->Add(101);
  std::unique_ptr<HistogramSamples> snapshot2(histogram->SnapshotSamples());
  EXPECT_EQ(3, snapshot2->TotalCount());
  EXPECT_EQ(2, snapshot2->GetCount(100));
  EXPECT_EQ(1, snapshot2->GetCount(101));
}

TEST_P(SparseHistogramTest, BasicTestAddCount) {
  std::unique_ptr<SparseHistogram> histogram(NewSparseHistogram("Sparse"));
  std::unique_ptr<HistogramSamples> snapshot(histogram->SnapshotSamples());
  EXPECT_EQ(0, snapshot->TotalCount());
  EXPECT_EQ(0, snapshot->sum());

  histogram->AddCount(100, 15);
  std::unique_ptr<HistogramSamples> snapshot1(histogram->SnapshotSamples());
  EXPECT_EQ(15, snapshot1->TotalCount());
  EXPECT_EQ(15, snapshot1->GetCount(100));

  histogram->AddCount(100, 15);
  histogram->AddCount(101, 25);
  std::unique_ptr<HistogramSamples> snapshot2(histogram->SnapshotSamples());
  EXPECT_EQ(55, snapshot2->TotalCount());
  EXPECT_EQ(30, snapshot2->GetCount(100));
  EXPECT_EQ(25, snapshot2->GetCount(101));
}

TEST_P(SparseHistogramTest, AddCount_LargeValuesDontOverflow) {
  std::unique_ptr<SparseHistogram> histogram(NewSparseHistogram("Sparse"));
  std::unique_ptr<HistogramSamples> snapshot(histogram->SnapshotSamples());
  EXPECT_EQ(0, snapshot->TotalCount());
  EXPECT_EQ(0, snapshot->sum());

  histogram->AddCount(1000000000, 15);
  std::unique_ptr<HistogramSamples> snapshot1(histogram->SnapshotSamples());
  EXPECT_EQ(15, snapshot1->TotalCount());
  EXPECT_EQ(15, snapshot1->GetCount(1000000000));

  histogram->AddCount(1000000000, 15);
  histogram->AddCount(1010000000, 25);
  std::unique_ptr<HistogramSamples> snapshot2(histogram->SnapshotSamples());
  EXPECT_EQ(55, snapshot2->TotalCount());
  EXPECT_EQ(30, snapshot2->GetCount(1000000000));
  EXPECT_EQ(25, snapshot2->GetCount(1010000000));
  EXPECT_EQ(55250000000LL, snapshot2->sum());
}

TEST_P(SparseHistogramTest, MacroBasicTest) {
  UMA_HISTOGRAM_SPARSE_SLOWLY("Sparse", 100);
  UMA_HISTOGRAM_SPARSE_SLOWLY("Sparse", 200);
  UMA_HISTOGRAM_SPARSE_SLOWLY("Sparse", 100);

  StatisticsRecorder::Histograms histograms;
  StatisticsRecorder::GetHistograms(&histograms);

  ASSERT_EQ(1U, histograms.size());
  HistogramBase* sparse_histogram = histograms[0];

  EXPECT_EQ(SPARSE_HISTOGRAM, sparse_histogram->GetHistogramType());
  EXPECT_EQ("Sparse", sparse_histogram->histogram_name());
  EXPECT_EQ(
      HistogramBase::kUmaTargetedHistogramFlag |
          (use_persistent_histogram_allocator_ ? HistogramBase::kIsPersistent
                                               : 0),
      sparse_histogram->flags());

  std::unique_ptr<HistogramSamples> samples =
      sparse_histogram->SnapshotSamples();
  EXPECT_EQ(3, samples->TotalCount());
  EXPECT_EQ(2, samples->GetCount(100));
  EXPECT_EQ(1, samples->GetCount(200));
}

TEST_P(SparseHistogramTest, MacroInLoopTest) {
  // Unlike the macros in histogram.h, SparseHistogram macros can have a
  // variable as histogram name.
  for (int i = 0; i < 2; i++) {
    std::string name = StringPrintf("Sparse%d", i + 1);
    UMA_HISTOGRAM_SPARSE_SLOWLY(name, 100);
  }

  StatisticsRecorder::Histograms histograms;
  StatisticsRecorder::GetHistograms(&histograms);
  ASSERT_EQ(2U, histograms.size());

  std::string name1 = histograms[0]->histogram_name();
  std::string name2 = histograms[1]->histogram_name();
  EXPECT_TRUE(("Sparse1" == name1 && "Sparse2" == name2) ||
              ("Sparse2" == name1 && "Sparse1" == name2));
}

TEST_P(SparseHistogramTest, Serialize) {
  std::unique_ptr<SparseHistogram> histogram(NewSparseHistogram("Sparse"));
  histogram->SetFlags(HistogramBase::kIPCSerializationSourceFlag);

  Pickle pickle;
  histogram->SerializeInfo(&pickle);

  PickleIterator iter(pickle);

  int type;
  EXPECT_TRUE(iter.ReadInt(&type));
  EXPECT_EQ(SPARSE_HISTOGRAM, type);

  std::string name;
  EXPECT_TRUE(iter.ReadString(&name));
  EXPECT_EQ("Sparse", name);

  int flag;
  EXPECT_TRUE(iter.ReadInt(&flag));
  EXPECT_EQ(HistogramBase::kIPCSerializationSourceFlag, flag);

  // No more data in the pickle.
  EXPECT_FALSE(iter.SkipBytes(1));
}

// Ensure that race conditions that cause multiple, identical sparse histograms
// to be created will safely resolve to a single one.
TEST_P(SparseHistogramTest, DuplicationSafety) {
  const char histogram_name[] = "Duplicated";
  size_t histogram_count = StatisticsRecorder::GetHistogramCount();

  // Create a histogram that we will later duplicate.
  HistogramBase* original =
      SparseHistogram::FactoryGet(histogram_name, HistogramBase::kNoFlags);
  ++histogram_count;
  DCHECK_EQ(histogram_count, StatisticsRecorder::GetHistogramCount());
  original->Add(1);

  // Create a duplicate. This has to happen differently depending on where the
  // memory is taken from.
  if (use_persistent_histogram_allocator_) {
    // To allocate from persistent memory, clear the last_created reference in
    // the GlobalHistogramAllocator. This will cause an Import to recreate
    // the just-created histogram which will then be released as a duplicate.
    GlobalHistogramAllocator::Get()->ClearLastCreatedReferenceForTesting();
    // Creating a different histogram will first do an Import to ensure it
    // hasn't been created elsewhere, triggering the duplication and release.
    SparseHistogram::FactoryGet("something.new", HistogramBase::kNoFlags);
    ++histogram_count;
  } else {
    // To allocate from the heap, just call the (private) constructor directly.
    // Delete it immediately like would have happened within FactoryGet();
    std::unique_ptr<SparseHistogram> something =
        NewSparseHistogram(histogram_name);
    DCHECK_NE(original, something.get());
  }
  DCHECK_EQ(histogram_count, StatisticsRecorder::GetHistogramCount());

  // Re-creating the histogram via FactoryGet() will return the same one.
  HistogramBase* duplicate =
      SparseHistogram::FactoryGet(histogram_name, HistogramBase::kNoFlags);
  DCHECK_EQ(original, duplicate);
  DCHECK_EQ(histogram_count, StatisticsRecorder::GetHistogramCount());
  duplicate->Add(2);

  // Ensure that original histograms are still cross-functional.
  original->Add(2);
  duplicate->Add(1);
  std::unique_ptr<HistogramSamples> snapshot_orig = original->SnapshotSamples();
  std::unique_ptr<HistogramSamples> snapshot_dup = duplicate->SnapshotSamples();
  DCHECK_EQ(2, snapshot_orig->GetCount(2));
  DCHECK_EQ(2, snapshot_dup->GetCount(1));
}

TEST_P(SparseHistogramTest, FactoryTime) {
  const int kTestCreateCount = 1 << 10;  // Must be power-of-2.
  const int kTestLookupCount = 100000;
  const int kTestAddCount = 100000;

  // Create all histogram names in advance for accurate timing below.
  std::vector<std::string> histogram_names;
  for (int i = 0; i < kTestCreateCount; ++i) {
    histogram_names.push_back(
        StringPrintf("TestHistogram.%d", i % kTestCreateCount));
  }

  // Calculate cost of creating histograms.
  TimeTicks create_start = TimeTicks::Now();
  for (int i = 0; i < kTestCreateCount; ++i)
    SparseHistogram::FactoryGet(histogram_names[i], HistogramBase::kNoFlags);
  TimeDelta create_ticks = TimeTicks::Now() - create_start;
  int64_t create_ms = create_ticks.InMilliseconds();

  VLOG(1) << kTestCreateCount << " histogram creations took " << create_ms
          << "ms or about "
          << (create_ms * 1000000) / kTestCreateCount
          << "ns each.";

  // Calculate cost of looking up existing histograms.
  TimeTicks lookup_start = TimeTicks::Now();
  for (int i = 0; i < kTestLookupCount; ++i) {
    // 6007 is co-prime with kTestCreateCount and so will do lookups in an
    // order less likely to be cacheable (but still hit them all) should the
    // underlying storage use the exact histogram name as the key.
    const int i_mult = 6007;
    static_assert(i_mult < INT_MAX / kTestCreateCount, "Multiplier too big");
    int index = (i * i_mult) & (kTestCreateCount - 1);
    SparseHistogram::FactoryGet(histogram_names[index],
                                HistogramBase::kNoFlags);
  }
  TimeDelta lookup_ticks = TimeTicks::Now() - lookup_start;
  int64_t lookup_ms = lookup_ticks.InMilliseconds();

  VLOG(1) << kTestLookupCount << " histogram lookups took " << lookup_ms
          << "ms or about "
          << (lookup_ms * 1000000) / kTestLookupCount
          << "ns each.";

  // Calculate cost of accessing histograms.
  HistogramBase* histogram =
      SparseHistogram::FactoryGet(histogram_names[0], HistogramBase::kNoFlags);
  ASSERT_TRUE(histogram);
  TimeTicks add_start = TimeTicks::Now();
  for (int i = 0; i < kTestAddCount; ++i)
    histogram->Add(i & 127);
  TimeDelta add_ticks = TimeTicks::Now() - add_start;
  int64_t add_ms = add_ticks.InMilliseconds();

  VLOG(1) << kTestAddCount << " histogram adds took " << add_ms
          << "ms or about "
          << (add_ms * 1000000) / kTestAddCount
          << "ns each.";
}

}  // namespace base