Improve efficiency of persistent sparse histograms.

base/metrics/persistent_histogram_allocator.h

Index: base/metrics/persistent_histogram_allocator.h
diff --git a/base/metrics/persistent_histogram_allocator.h b/base/metrics/persistent_histogram_allocator.h
index b2038c4314c704f572771648b76410fdcffd03b0..494ec60b77357734b6edbd539a2f99f5f0fbc3fd 100644
--- a/base/metrics/persistent_histogram_allocator.h
+++ b/base/metrics/persistent_histogram_allocator.h
@@ -10,13 +10,18 @@
 #include "base/atomicops.h"
 #include "base/base_export.h"
 #include "base/feature_list.h"
+#include "base/id_map.h"
 #include "base/memory/shared_memory.h"
 #include "base/metrics/histogram_base.h"
 #include "base/metrics/persistent_memory_allocator.h"
 #include "base/strings/string_piece.h"
+#include "base/synchronization/lock.h"
 
 namespace base {
 
+class PersistentSampleMapRecords;
+class PersistentSparseHistogramHelper;
+
 // Feature definition for enabling histogram persistence.
 BASE_EXPORT extern const Feature kPersistentHistogramsFeature;
 
@@ -101,6 +106,12 @@ class BASE_EXPORT PersistentHistogramAllocator {
   // True, forgetting it otherwise.
   void FinalizeHistogram(Reference ref, bool registered);
 
+  // Returns the object that manages the persistent-sample-map records for a
+  // given |id|. There is only one such object per-allocator-per-id on the
+  // assumption that there is only ever one histogram object at a time that
+  // would use a particular set of records. Ownership stays with this allocator.
+  PersistentSampleMapRecords* GetSampleMapRecords(uint64_t id);
+
   // Create internal histograms for tracking memory use and allocation sizes
   // for allocator of |name| (which can simply be the result of Name()). This
   // is done seperately from construction for situations such as when the
@@ -179,6 +190,9 @@ class BASE_EXPORT PersistentHistogramAllocator {
   // The memory allocator that provides the actual histogram storage.
   std::unique_ptr<PersistentMemoryAllocator> memory_allocator_;
 
+  // The helper used to improve performance of sparse histograms.
+  std::unique_ptr<PersistentSparseHistogramHelper> sparse_histogram_helper_;

[Alexei Svitkine (slow), 2016/04/13 15:53:50]

Why is this a unique_ptr? Can it just be a member?

[bcwhite, 2016/04/13 22:45:03]

I had originally planned to not create it until needed.  Let me see what I can
do.

+
   // A reference to the last-created histogram in the allocator, used to avoid
   // trying to import what was just created.
   // TODO(bcwhite): Change this to std::atomic<PMA::Reference> when available.
@@ -262,6 +276,132 @@ class BASE_EXPORT GlobalHistogramAllocator
   DISALLOW_COPY_AND_ASSIGN(GlobalHistogramAllocator);
 };
 
+
+// A helper-class for sparse histograms so each instance of such doesn't have
+// to separately iterate over the entire memory segment. Though this class
+// will generally be accessed through the PersistentHistogramAllocator above,
+// it can be used independently on any PersistentMemoryAllocator (making it
+// useable for testing). This object supports only one instance of a sparse
+// histogram for a given id. Tests that create multiple identical histograms,
+// perhaps to simulate multiple processes, should create a separate helper
+// for each.
+class BASE_EXPORT PersistentSparseHistogramHelper {

[Alexei Svitkine (slow), 2016/04/13 15:53:50]

Helper is not a very descriptive name. Can this be named more descriptively?
Maybe PersistentSparseHistogramManager?

[bcwhite, 2016/04/13 22:45:04]

Done.

+ public:
+  // Constructs the helper. The allocator must live longer than any helpers
+  // that reference it.
+  PersistentSparseHistogramHelper(PersistentMemoryAllocator* allocator);

[Alexei Svitkine (slow), 2016/04/13 15:53:50]

Nit: explicit

[bcwhite, 2016/04/13 22:45:03]

Done.

+
+  ~PersistentSparseHistogramHelper();
+
+  // Returns the object that manages the persistent-sample-map records for a
+  // given |id|. There is only one such object per-allocator-per-id on the
+  // assumption that there is only ever one histogram object at a time that
+  // would use a particular set of records. Ownership stays with this helper.
+  PersistentSampleMapRecords* GetSampleMapRecords(uint64_t id);
+
+  // Convenience method that gets the object for a given reference so callers
+  // don't have to also keep their own pointer to the appropriate allocator.
+  template <typename T>

[Alexei Svitkine (slow), 2016/04/13 15:53:50]

Does this need to be a template if we know it's managing data for a sparse
histogram? Can it be concrete and named appropriately for what it's querying?

[bcwhite, 2016/04/13 22:45:03]

It's a template because the type on which it's used is private to other files. 
This class doesn't know the format of the record, just that it exists.

The type could be made public but it works better to keep it completely
encapsulated in the PersistentSampleMap and have this class call that one to do
the low-level work.

[Alexei Svitkine (slow), 2016/04/14 19:30:03]

Okay, maybe mention that in the method comment. Otherwise, it's confusing why
it's a template.

[bcwhite, 2016/04/15 02:36:18]

Will do.

+  T* GetAsObject(PersistentMemoryAllocator::Reference ref, uint32_t type_id) {
+    return allocator_->GetAsObject<T>(ref, type_id);
+  }
+
+ private:
+  friend class PersistentSampleMapRecords;
+
+  // Like GetSampleMapRecords() above but operates when the |lock_| has
+  // already been acquired.
+  PersistentSampleMapRecords* GetSampleMapRecordsWhileLocked(uint64_t id);
+
+  // Loads sample-map records looking for those belonging to the specified
+  // |load_id|. Records found for other sample-maps are held for later use
+  // without having to iterate again. This should only be called when the
+  // |lock_| has been acquired.
+  bool LoadRecordsForSampleMapWhileLocked(uint64_t load_id);

[Alexei Svitkine (slow), 2016/04/13 15:53:50]

Nit: Why load_id if Load is already part of the method name? Just id?

Also, not sure you need "ForSampleMap" in the name - I think
LoadRecordsWhileLocked() is easier to digest. If you really want to have the
extra info you can name the param sample_map_id.

[bcwhite, 2016/04/13 22:45:03]

Because parameter names here need to match parameter names in the implementation
and just "id" made for unclear code.
Done.

+
+  // Weak-pointer to the allocator used by the sparse histograms.
+  PersistentMemoryAllocator* allocator_;
+
+  // Iterator within the allocator for finding sample records.
+  PersistentMemoryAllocator::Iterator record_iterator_;
+
+  // Mapping of sample-map IDs to their sample records.
+  IDMap<PersistentSampleMapRecords, IDMapOwnPointer, uint64_t> sample_records_;
+
+  // A lock used for synchronizing changes to sample_records_.
+  base::Lock lock_;
+
+  DISALLOW_COPY_AND_ASSIGN(PersistentSparseHistogramHelper);
+};
+
+
+// This class manages sample-records used by the PersistentSampleMap containers
+// that underlie persistent SparseHistogram objects. It is broken out into a

[Alexei Svitkine (slow), 2016/04/13 15:53:50]

This sentence is confusing since it's using plurals (containers, objects), but
the reality is this corresponds to a single SparseHistogram/PersistentSampleMap.
Can you please re-word?

[bcwhite, 2016/04/13 22:45:03]

Done.

+// top-level class so that it can be forward-declared in other header files
+// rather than include this entire file as would be necessary if it were
+// declared within the PersistentSparseHistogramHelper class above.
+class BASE_EXPORT PersistentSampleMapRecords {
+ public:
+  // Constructs an instance of this class. The helper object must live longer
+  // than all instances of this class that reference it, which is not usually
+  // a problem since these objects are generally managed from within that
+  // helper instance.
+  PersistentSampleMapRecords(PersistentSparseHistogramHelper* helper,
+                             uint64_t sample_map_id);
+
+  ~PersistentSampleMapRecords();
+
+  // Resets the internal state of seen/unseen records for its sample-map.
+  // This should be done when creating a PersistentSampleMap so it does not
+  // mistakenly resume from where a previous instance left off. Multiple,
+  // sequential instances of such are common when reading histograms of
+  // another process for periodic reporting to UMA.
+  void Reset();

[Alexei Svitkine (slow), 2016/04/13 15:53:50]

I don't quite understand the reasoning here. It feels wrong to need this, but
I'm not quite following the scenario.

Can you explain the scenario a bit more?

[bcwhite, 2016/04/13 22:45:03]

Done.

+
+  // Gets the next reference to a persistent sample-map record. The type and
+  // layout of the data being referenced is defined entirely within the
+  // PersistentSampleMap class.
+  PersistentMemoryAllocator::Reference GetNext();
+
+  // Creates a new persistent sample-map record for sample |value| and returns
+  // a reference to it.
+  PersistentMemoryAllocator::Reference CreateNew(HistogramBase::Sample value);
+
+  // Convenience method that gets the object for a given reference so callers
+  // don't have to also keep their own pointer to the appropriate allocator.
+  template <typename T>
+  T* GetAsObject(PersistentMemoryAllocator::Reference ref, uint32_t type_id) {
+    return helper_->GetAsObject<T>(ref, type_id);
+  }
+
+ private:
+  friend PersistentSparseHistogramHelper;
+
+  // Weak-pointer to the parent helper object.
+  PersistentSparseHistogramHelper* helper_;
+
+  // ID of PersistentSampleMap to which these records apply.
+  uint64_t sample_map_id_;

[Alexei Svitkine (slow), 2016/04/13 15:53:50]

Nit: const?

[bcwhite, 2016/04/13 22:45:04]

Done.

+
+  // This is the count of how many "records" have already been read by the
+  // owning sample-map.
+  size_t seen_;
+
+  // This is the set of records previously found for a sample map. Because
+  // there is ever only one object with a given ID (typically a hash of a
+  // histogram name) and because the parent SparseHistogram has acquired
+  // its own lock before accessing the PersistentSampleMap it controls, this
+  // list can be accessed without acquiring any additional lock.
+  std::vector<PersistentMemoryAllocator::Reference> records_;
+
+  // This is the set of records found during iteration through memory. It
+  // is appended in bulk to "records". Access to this vector can be done
+  // only while holding the parent helper's lock.
+  std::vector<PersistentMemoryAllocator::Reference> found_;
+
+  DISALLOW_COPY_AND_ASSIGN(PersistentSampleMapRecords);
+};
+
 }  // namespace base
 
 #endif  // BASE_METRICS_HISTOGRAM_PERSISTENCE_H_