Add support for persistent sparse histograms.

base/metrics/sample_map.cc

 // 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/sample_map.h"
 
 #include "base/logging.h"
+#include "base/stl_util.h"
 
 namespace base {
 
 typedef HistogramBase::Count Count;
 typedef HistogramBase::Sample Sample;
 
 SampleMap::SampleMap() : SampleMap(0) {}
 
 SampleMap::SampleMap(uint64_t id) : HistogramSamples(id) {}
 
 SampleMap::~SampleMap() {}
 
 void SampleMap::Accumulate(Sample value, Count count) {
   sample_counts_[value] += count;
   IncreaseSum(static_cast<int64_t>(count) * value);
   IncreaseRedundantCount(count);
 }
 
 Count SampleMap::GetCount(Sample value) const {
   std::map<Sample, Count>::const_iterator it = sample_counts_.find(value);
   if (it == sample_counts_.end())
     return 0;
   return it->second;
 }
 
 Count SampleMap::TotalCount() const {
   Count count = 0;
-  for (const auto& entry : sample_counts_) {
+  for (const auto& entry : sample_counts_)
     count += entry.second;
-  }
   return count;
 }
 
 scoped_ptr<SampleCountIterator> SampleMap::Iterator() const {
-  return scoped_ptr<SampleCountIterator>(new SampleMapIterator(sample_counts_));
+  return make_scoped_ptr(new SampleMapIterator(sample_counts_));
 }
 
-bool SampleMap::AddSubtractImpl(SampleCountIterator* iter,
-                                HistogramSamples::Operator op) {
+bool SampleMap::AddSubtractImpl(SampleCountIterator* iter, Operator op) {
   Sample min;
   Sample max;
   Count count;
   for (; !iter->Done(); iter->Next()) {
     iter->Get(&min, &max, &count);
     if (min + 1 != max)
       return false;  // SparseHistogram only supports bucket with size 1.
 
     sample_counts_[min] += (op == HistogramSamples::ADD) ? count : -count;
   }
@@ skipping 13 matching lines @@
 }
 
 void SampleMapIterator::Next() {
   DCHECK(!Done());
   ++iter_;
   SkipEmptyBuckets();
 }
 
 void SampleMapIterator::Get(Sample* min, Sample* max, Count* count) const {
   DCHECK(!Done());
-  if (min != NULL)
+  if (min)
     *min = iter_->first;
-  if (max != NULL)
+  if (max)
     *max = iter_->first + 1;
-  if (count != NULL)
+  if (count)
     *count = iter_->second;
 }
 
 void SampleMapIterator::SkipEmptyBuckets() {
-  while (!Done() && iter_->second == 0) {
+  while (!Done() && iter_->second == 0)
     ++iter_;
+}
+
+
+// ----- PersistentSampleMap ---------------------------------------------------
+
+namespace {
+
+// This structure holds an entry for a PersistentSampleMap within a persistent
+// memory allocator. The "id" must be unique across all maps held by an
+// allocator or they will get attached to the wrong sample map.
+struct SampleRecord {
+  uint64_t id;   // Unique identifier of owner.
+  Sample value;  // The value for which this record holds a count.
+  Count count;   // The count associated with the above value.
+};
+
+// The type-id used to identify sample records inside an allocator.
+const uint32_t kTypeIdSampleRecord = 0x8FE6A69F + 1;  // SHA1(SampleRecord) v1
+
+}  // namespace
+
+PersistentSampleMap::PersistentSampleMap(
+    uint64_t id,
+    PersistentMemoryAllocator* allocator,
+    Metadata* meta)
+    : HistogramSamples(id, meta),
+      allocator_(allocator) {
+  // This is created once but will continue to return new iterables even when
+  // it has previously reached the end.
+  allocator->CreateIterator(&sample_iter_);
+
+  // Load all existing samples during construction. It's no worse to do it
+  // here than at some point in the future and could be better if construction
+  // takes place on some background thread. New samples could be created at
+  // any time by parallel threads; if so, they'll get loaded when needed.
+  ImportSamples(kAllSamples);
+}
+
+PersistentSampleMap::~PersistentSampleMap() {}
+
+void PersistentSampleMap::Accumulate(Sample value, Count count) {
+  *GetSampleCountStorage(value, /*create=*/true) += count;
+  IncreaseSum(static_cast<int64_t>(count) * value);
+  IncreaseRedundantCount(count);
+}
+
+Count PersistentSampleMap::GetCount(Sample value) const {
+  // Have to override "const" to make sure all samples have been loaded before
+  // being able to know what value to return.
+  Count* count_pointer =
+      const_cast<PersistentSampleMap*>(this)->GetSampleCountStorage(
+          value, /*create=*/false);
+  return count_pointer ? *count_pointer : 0;
+}
+
+Count PersistentSampleMap::TotalCount() const {
+  // Have to override "const" in order to make sure all samples have been
+  // loaded before trying to iterate over the map.
+  const_cast<PersistentSampleMap*>(this)->ImportSamples(kAllSamples);
+
+  Count count = 0;
+  for (const auto& entry : sample_counts_)
+    count += *entry.second;
+  return count;
+}
+
+scoped_ptr<SampleCountIterator> PersistentSampleMap::Iterator() const {
+  // Have to override "const" in order to make sure all samples have been
+  // loaded before trying to iterate over the map.
+  const_cast<PersistentSampleMap*>(this)->ImportSamples(kAllSamples);
+  return make_scoped_ptr(new PersistentSampleMapIterator(sample_counts_));
+}
+
+bool PersistentSampleMap::AddSubtractImpl(SampleCountIterator* iter,
+                                          Operator op) {
+  Sample min;
+  Sample max;
+  Count count;
+  for (; !iter->Done(); iter->Next()) {
+    iter->Get(&min, &max, &count);
+    if (min + 1 != max)
+      return false;  // SparseHistogram only supports bucket with size 1.
+
+    *GetSampleCountStorage(min, /*create=*/true) +=
+        (op == HistogramSamples::ADD) ? count : -count;
   }
+  return true;
+}
+
+Count* PersistentSampleMap::GetSampleCountStorage(Sample value,
+                                                  bool create_if_necessary) {
+  DCHECK_LE(0, value);
+
+  // If |value| is already in the map, just return that.
+  auto it = sample_counts_.find(value);
+  if (it != sample_counts_.end())
+    return it->second;
+
+  // Import any new samples from persistent memory looking for the value.
+  Count* count_pointer = ImportSamples(value);
+  if (count_pointer)
+    return count_pointer;
+
+  // Stop here if no creation of new samples is desired.

[Alexei Svitkine (slow), 2016/03/03 17:43:38]

I prefer these to be separate methods. You can have the GetOrCreate version call
the Get* function first which does the above.

Having them be separate functions avoids you needing to document the second
param in calls.

[bcwhite, 2016/03/07 15:30:39]

Done.

+  if (!create_if_necessary)
+    return nullptr;
+
+  // Create a new record in persistent memory for the value.
+  PersistentMemoryAllocator::Reference ref =
+      allocator_->Allocate(sizeof(SampleRecord), kTypeIdSampleRecord);
+  SampleRecord* record =
+      allocator_->GetAsObject<SampleRecord>(ref, kTypeIdSampleRecord);
+  if (!record) {
+    // If the allocator was unable to create a record then it is full or
+    // corrupt. Instead, allocate the counter from the heap. This sample will
+    // not be persistent, will not be shared, and will leak but it's better
+    // than crashing.
+    NOTREACHED() << "full=" << allocator_->IsFull()
+                 << ", corrupt=" << allocator_->IsCorrupt();
+    count_pointer = new Count(0);
+    sample_counts_[value] = count_pointer;
+    return count_pointer;
+  }
+  record->id = id();
+  record->value = value;
+  // record->count = 0 because allocator guarantees zero'd memory.
+  allocator_->MakeIterable(ref);
+
+  // A race condition could cause two of the above records to be created. The
+  // allocator, however, forces a strict ordering on iterable objects so use
+  // the import method to actually add the just-created record. This ensures
+  // that all PersistentSampleMap objects will always use the same record,
+  // whichever was first made iterable.
+  count_pointer = ImportSamples(value);
+  DCHECK(count_pointer);
+  return count_pointer;
+}
+
+Count* PersistentSampleMap::ImportSamples(Sample until_value) {
+  // TODO(bcwhite): This import operates in O(V+N) total time per sparse
+  // histogram where V is the number of values for this object and N is
+  // the number of other iterable objects in the allocator. This becomes
+  // O(S*(SV+N)) or O(S^2*V + SN) overall where S is the number of sparse
+  // histograms.
+  //
+  // This is actually okay when histograms are expected to exist for the
+  // lifetime of the program, spreading the cost out, and S and V are
+  // relatively small, as is the current case.
+  //
+  // However, it is not so good for objects that are created, detroyed, and
+  // recreated on a periodic basis, such as when making a snapshot of
+  // sparse histograms owned by another, ongoing process. In that case, the
+  // entire cost is compressed into a single sequential operation... on the
+  // UI thread no less.
+  //
+  // This will be addressed in a future CL.
+
+  uint32_t type_id;
+  PersistentMemoryAllocator::Reference ref;
+  while ((ref = allocator_->GetNextIterable(&sample_iter_, &type_id)) != 0) {
+    if (type_id == kTypeIdSampleRecord) {
+      SampleRecord* record =
+          allocator_->GetAsObject<SampleRecord>(ref, kTypeIdSampleRecord);
+      if (!record)
+        continue;
+
+      // A sample record has been found but may not be for this histogram.
+      if (record->id != id())
+        continue;
+
+      // Check if the record's value is already known.
+      if (!ContainsKey(sample_counts_, record->value)) {
+        // No: Add it to map of known values if the value is valid.
+        if (record->value >= 0)
+          sample_counts_[record->value] = &record->count;
+      } else {
+        // Yes: Ignore it; it's a duplicate caused by a race condition.
+        DCHECK_EQ(0, record->count);  // Duplicate record should never be used.
+      }
+
+      // Stop if it's the value being searched for.
+      if (record->value == until_value)
+        return &record->count;
+    }
+  }
+
+  return nullptr;
+}
+
+PersistentSampleMapIterator::PersistentSampleMapIterator(
+    const SampleToCountMap& sample_counts)
+    : iter_(sample_counts.begin()),
+      end_(sample_counts.end()) {
+  SkipEmptyBuckets();
+}
+
+PersistentSampleMapIterator::~PersistentSampleMapIterator() {}
+
+bool PersistentSampleMapIterator::Done() const {
+  return iter_ == end_;
+}
+
+void PersistentSampleMapIterator::Next() {
+  DCHECK(!Done());
+  ++iter_;
+  SkipEmptyBuckets();
+}
+
+void PersistentSampleMapIterator::Get(Sample* min,
+                                      Sample* max,
+                                      Count* count) const {
+  DCHECK(!Done());
+  if (min)
+    *min = iter_->first;
+  if (max)
+    *max = iter_->first + 1;
+  if (count)
+    *count = *iter_->second;
+}
+
+void PersistentSampleMapIterator::SkipEmptyBuckets() {
+  while (!Done() && *iter_->second == 0)
+    ++iter_;
 }
 
 }  // namespace base