Improve efficiency of persistent sparse histograms.

base/metrics/persistent_sample_map.cc

 // Copyright 2016 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/persistent_sample_map.h"
 
 #include "base/logging.h"
 #include "base/memory/ptr_util.h"
+#include "base/metrics/persistent_histogram_allocator.h"
 #include "base/stl_util.h"
 
 namespace base {
 
 typedef HistogramBase::Count Count;
 typedef HistogramBase::Sample Sample;
 
 namespace {
 
 // An iterator for going through a PersistentSampleMap. The logic here is
@@ skipping 67 matching lines @@
   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,
+    PersistentHistogramAllocator* allocator,
     Metadata* meta)
-    : HistogramSamples(id, meta),
-      allocator_(allocator),
-      sample_iter_(allocator) {
-  // 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(id, allocator->UseSampleMapRecords(id, this), meta) {}
+
+PersistentSampleMap::PersistentSampleMap(
+    uint64_t id,
+    PersistentSparseHistogramDataManager* manager,
+    Metadata* meta)
+    : PersistentSampleMap(id, manager->UseSampleMapRecords(id, this), meta) {}
+
+PersistentSampleMap::PersistentSampleMap(
+    uint64_t id,
+    PersistentSampleMapRecords* records,
+    Metadata* meta)
+    : HistogramSamples(id, meta), records_(records) {}
+
+PersistentSampleMap::~PersistentSampleMap() {
+  records_->Release(this);
 }
 
-PersistentSampleMap::~PersistentSampleMap() {}
-
 void PersistentSampleMap::Accumulate(Sample value, Count count) {
   *GetOrCreateSampleCountStorage(value) += 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 =
@@ skipping 13 matching lines @@
   return count;
 }
 
 std::unique_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 WrapUnique(new PersistentSampleMapIterator(sample_counts_));
 }
 
+// static
+PersistentMemoryAllocator::Reference
+PersistentSampleMap::GetNextPersistentRecord(
+    PersistentMemoryAllocator::Iterator& iterator,
+    uint64_t* sample_map_id) {
+  PersistentMemoryAllocator::Reference ref =
+      iterator.GetNextOfType(kTypeIdSampleRecord);
+  const SampleRecord* record =
+      iterator.GetAsObject<SampleRecord>(ref, kTypeIdSampleRecord);
+  if (!record)
+    return 0;
+
+  *sample_map_id = record->id;
+  return ref;
+}
+
+// static
+PersistentMemoryAllocator::Reference
+PersistentSampleMap::CreatePersistentRecord(
+    PersistentMemoryAllocator* allocator,
+    uint64_t sample_map_id,
+    Sample value) {
+  PersistentMemoryAllocator::Reference ref =
+      allocator->Allocate(sizeof(SampleRecord), kTypeIdSampleRecord);
+  SampleRecord* record =
+      allocator->GetAsObject<SampleRecord>(ref, kTypeIdSampleRecord);
+
+  if (!record) {
+    NOTREACHED() << "full=" << allocator->IsFull()
+                 << ", corrupt=" << allocator->IsCorrupt();
+    return 0;
+  }
+
+  record->id = sample_map_id;
+  record->value = value;
+  record->count = 0;
+  allocator->MakeIterable(ref);
+  return ref;
+}
+
 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.
 
@@ skipping 15 matching lines @@
   return ImportSamples(value);
 }
 
 Count* PersistentSampleMap::GetOrCreateSampleCountStorage(Sample value) {
   // Get any existing count storage.
   Count* count_pointer = GetSampleCountStorage(value);
   if (count_pointer)
     return count_pointer;
 
   // 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();
+  PersistentMemoryAllocator::Reference ref = records_->CreateNew(value);
+  if (!ref) {
+    // If a new record could not be created then the underlying allocator 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.
     count_pointer = new Count(0);
     sample_counts_[value] = count_pointer;
     return count_pointer;
   }
-  record->id = id();
-  record->value = value;
-  record->count = 0;  // Should already be zero but don't trust other processes.
-  allocator_->MakeIterable(ref);
 
   // A race condition between two independent processes (i.e. two independent
   // histogram objects sharing the same sample data) 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.
   // Thread-safety within a process where multiple threads use the same
   // histogram object is delegated to the controlling histogram object which,
   // for sparse histograms, is a lock object.
   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.
-
   PersistentMemoryAllocator::Reference ref;
-  while ((ref = sample_iter_.GetNextOfType(kTypeIdSampleRecord)) != 0) {
+  while ((ref = records_->GetNext()) != 0) {
     SampleRecord* record =
-        allocator_->GetAsObject<SampleRecord>(ref, kTypeIdSampleRecord);
+        records_->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;
+    DCHECK_EQ(id(), record->id);
 
     // 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 -- see
       // code & comment in GetOrCreateSampleCountStorage() for details.
       // Check that nothing ever operated on the duplicate record.
       DCHECK_EQ(0, record->count);
     }
 
     // Stop if it's the value being searched for.
     if (record->value == until_value)
       return &record->count;
   }
 
   return nullptr;
 }
 
 }  // namespace base