Revert of Embed a single sample in histogram metadata.

base/metrics/sample_vector.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_vector.h"
 
-#include "base/lazy_instance.h"
 #include "base/logging.h"
-#include "base/memory/ptr_util.h"
-#include "base/metrics/persistent_memory_allocator.h"
-#include "base/synchronization/lock.h"
-#include "base/threading/platform_thread.h"
-
-// This SampleVector makes use of the single-sample embedded in the base
-// HistogramSamples class. If the count is non-zero then there is guaranteed
-// (within the bounds of "eventual consistency") to be no allocated external
-// storage. Once the full counts storage is allocated, the single-sample must
-// be extracted and disabled.
+#include "base/metrics/bucket_ranges.h"
 
 namespace base {
 
 typedef HistogramBase::Count Count;
 typedef HistogramBase::Sample Sample;
 
-SampleVectorBase::SampleVectorBase(uint64_t id,
-                                   const BucketRanges* bucket_ranges)
-    : HistogramSamples(id), bucket_ranges_(bucket_ranges) {
+SampleVector::SampleVector(const BucketRanges* bucket_ranges)
+    : SampleVector(0, bucket_ranges) {}
+
+SampleVector::SampleVector(uint64_t id, const BucketRanges* bucket_ranges)
+    : HistogramSamples(id),
+      local_counts_(bucket_ranges->bucket_count()),
+      counts_(&local_counts_[0]),
+      counts_size_(local_counts_.size()),
+      bucket_ranges_(bucket_ranges) {
   CHECK_GE(bucket_ranges_->bucket_count(), 1u);
 }
 
-SampleVectorBase::SampleVectorBase(uint64_t id,
-                                   Metadata* meta,
-                                   const BucketRanges* bucket_ranges)
-    : HistogramSamples(id, meta), bucket_ranges_(bucket_ranges) {
+SampleVector::SampleVector(uint64_t id,
+                           HistogramBase::AtomicCount* counts,
+                           size_t counts_size,
+                           Metadata* meta,
+                           const BucketRanges* bucket_ranges)
+    : HistogramSamples(id, meta),
+      counts_(counts),
+      counts_size_(bucket_ranges->bucket_count()),
+      bucket_ranges_(bucket_ranges) {
+  CHECK_LE(bucket_ranges_->bucket_count(), counts_size_);
   CHECK_GE(bucket_ranges_->bucket_count(), 1u);
 }
 
-SampleVectorBase::~SampleVectorBase() {}
+SampleVector::~SampleVector() {}
 
-void SampleVectorBase::Accumulate(Sample value, Count count) {
-  const size_t bucket_index = GetBucketIndex(value);
-
-  // Handle the single-sample case.
-  if (!counts()) {
-    // Try to accumulate the parameters into the single-count entry.
-    if (AccumulateSingleSample(value, count, bucket_index)) {
-      // A race condition could lead to a new single-sample being accumulated
-      // above just after another thread executed the MountCountsStorage below.
-      // Since it is mounted, it could be mounted elsewhere and have values
-      // written to it. It's not allowed to have both a single-sample and
-      // entries in the counts array so move the single-sample.
-      if (counts())
-        MoveSingleSampleToCounts();
-      return;
-    }
-
-    // Need real storage to store both what was in the single-sample plus the
-    // parameter information.
-    MountCountsStorageAndMoveSingleSample();
-  }
-
-  // Handle the multi-sample case.
-  subtle::NoBarrier_AtomicIncrement(&counts()[bucket_index], count);
-  IncreaseSumAndCount(static_cast<int64_t>(count) * value, count);
+void SampleVector::Accumulate(Sample value, Count count) {
+  size_t bucket_index = GetBucketIndex(value);
+  subtle::NoBarrier_AtomicIncrement(&counts_[bucket_index], count);
+  IncreaseSum(static_cast<int64_t>(count) * value);
+  IncreaseRedundantCount(count);
 }
 
-Count SampleVectorBase::GetCount(Sample value) const {
-  return GetCountAtIndex(GetBucketIndex(value));
+Count SampleVector::GetCount(Sample value) const {
+  size_t bucket_index = GetBucketIndex(value);
+  return subtle::NoBarrier_Load(&counts_[bucket_index]);
 }
 
-Count SampleVectorBase::TotalCount() const {
-  // Handle the single-sample case.
-  SingleSample sample = single_sample().Load();
-  if (sample.count != 0)
-    return sample.count;
-
-  // Handle the multi-sample case.
-  if (counts() || MountExistingCountsStorage()) {
-    Count count = 0;
-    size_t size = counts_size();
-    const HistogramBase::AtomicCount* counts_array = counts();
-    for (size_t i = 0; i < size; ++i) {
-      count += subtle::NoBarrier_Load(&counts_array[i]);
-    }
-    return count;
+Count SampleVector::TotalCount() const {
+  Count count = 0;
+  for (size_t i = 0; i < counts_size_; i++) {
+    count += subtle::NoBarrier_Load(&counts_[i]);
   }
-
-  // And the no-value case.
-  return 0;
+  return count;
 }
 
-Count SampleVectorBase::GetCountAtIndex(size_t bucket_index) const {
-  DCHECK(bucket_index < counts_size());
-
-  // Handle the single-sample case.
-  SingleSample sample = single_sample().Load();
-  if (sample.count != 0)
-    return sample.bucket == bucket_index ? sample.count : 0;
-
-  // Handle the multi-sample case.
-  if (counts() || MountExistingCountsStorage())
-    return subtle::NoBarrier_Load(&counts()[bucket_index]);
-
-  // And the no-value case.
-  return 0;
+Count SampleVector::GetCountAtIndex(size_t bucket_index) const {
+  DCHECK(bucket_index < counts_size_);
+  return subtle::NoBarrier_Load(&counts_[bucket_index]);
 }
 
-std::unique_ptr<SampleCountIterator> SampleVectorBase::Iterator() const {
-  // Handle the single-sample case.
-  SingleSample sample = single_sample().Load();
-  if (sample.count != 0) {
-    return MakeUnique<SingleSampleIterator>(
-        bucket_ranges_->range(sample.bucket),
-        bucket_ranges_->range(sample.bucket + 1), sample.count, sample.bucket);
-  }
-
-  // Handle the multi-sample case.
-  if (counts() || MountExistingCountsStorage()) {
-    return MakeUnique<SampleVectorIterator>(counts(), counts_size(),
-                                            bucket_ranges_);
-  }
-
-  // And the no-value case.
-  return MakeUnique<SampleVectorIterator>(nullptr, 0, bucket_ranges_);
+std::unique_ptr<SampleCountIterator> SampleVector::Iterator() const {
+  return std::unique_ptr<SampleCountIterator>(
+      new SampleVectorIterator(counts_, counts_size_, bucket_ranges_));
 }
 
-bool SampleVectorBase::AddSubtractImpl(SampleCountIterator* iter,
-                                       HistogramSamples::Operator op) {
-  // Stop now if there's nothing to do.
-  if (iter->Done())
-    return true;
-
-  // Get the first value and its index.
+bool SampleVector::AddSubtractImpl(SampleCountIterator* iter,
+                                   HistogramSamples::Operator op) {
   HistogramBase::Sample min;
   HistogramBase::Sample max;
   HistogramBase::Count count;
-  iter->Get(&min, &max, &count);
-  size_t dest_index = GetBucketIndex(min);
 
-  // The destination must be a superset of the source meaning that though the
-  // incoming ranges will find an exact match, the incoming bucket-index, if
-  // it exists, may be offset from the destination bucket-index. Calculate
-  // that offset of the passed iterator; there are are no overflow checks
-  // because 2's compliment math will work it out in the end.
-  //
-  // Because GetBucketIndex() always returns the same true or false result for
-  // a given iterator object, |index_offset| is either set here and used below,
-  // or never set and never used. The compiler doesn't know this, though, which
-  // is why it's necessary to initialize it to something.
-  size_t index_offset = 0;
-  size_t iter_index;
-  if (iter->GetBucketIndex(&iter_index))
-    index_offset = dest_index - iter_index;
-  if (dest_index >= counts_size())
-    return false;
-
-  // Post-increment. Information about the current sample is not available
-  // after this point.
-  iter->Next();
-
-  // Single-value storage is possible if there is no counts storage and the
-  // retrieved entry is the only one in the iterator.
-  if (!counts()) {
-    if (iter->Done()) {
-      // Don't call AccumulateSingleSample because that updates sum and count
-      // which was already done by the caller of this method.
-      if (single_sample().Accumulate(
-              dest_index, op == HistogramSamples::ADD ? count : -count)) {
-        // Handle race-condition that mounted counts storage between above and
-        // here.
-        if (counts())
-          MoveSingleSampleToCounts();
-        return true;
-      }
+  // Go through the iterator and add the counts into correct bucket.
+  size_t index = 0;
+  while (index < counts_size_ && !iter->Done()) {
+    iter->Get(&min, &max, &count);
+    if (min == bucket_ranges_->range(index) &&
+        max == bucket_ranges_->range(index + 1)) {
+      // Sample matches this bucket!
+      subtle::NoBarrier_AtomicIncrement(
+          &counts_[index], op == HistogramSamples::ADD ? count : -count);
+      iter->Next();
+    } else if (min > bucket_ranges_->range(index)) {
+      // Sample is larger than current bucket range. Try next.
+      index++;
+    } else {
+      // Sample is smaller than current bucket range. We scan buckets from
+      // smallest to largest, so the sample value must be invalid.
+      return false;
     }
-
-    // The counts storage will be needed to hold the multiple incoming values.
-    MountCountsStorageAndMoveSingleSample();
   }
 
-  // Go through the iterator and add the counts into correct bucket.
-  while (true) {
-    // Ensure that the sample's min/max match the ranges min/max.
-    if (min != bucket_ranges_->range(dest_index) ||
-        max != bucket_ranges_->range(dest_index + 1)) {
-      NOTREACHED() << "sample=" << min << "," << max
-                   << "; range=" << bucket_ranges_->range(dest_index) << ","
-                   << bucket_ranges_->range(dest_index + 1);
-      return false;
-    }
-
-    // Sample's bucket matches exactly. Adjust count.
-    subtle::NoBarrier_AtomicIncrement(
-        &counts()[dest_index], op == HistogramSamples::ADD ? count : -count);
-
-    // Advance to the next iterable sample. See comments above for how
-    // everything works.
-    if (iter->Done())
-      return true;
-    iter->Get(&min, &max, &count);
-    if (iter->GetBucketIndex(&iter_index)) {
-      // Destination bucket is a known offset from the source bucket.
-      dest_index = iter_index + index_offset;
-    } else {
-      // Destination bucket has to be determined anew each time.
-      dest_index = GetBucketIndex(min);
-    }
-    if (dest_index >= counts_size())
-      return false;
-    iter->Next();
-  }
+  return iter->Done();
 }
 
 // Use simple binary search.  This is very general, but there are better
 // approaches if we knew that the buckets were linearly distributed.
-size_t SampleVectorBase::GetBucketIndex(Sample value) const {
+size_t SampleVector::GetBucketIndex(Sample value) const {
   size_t bucket_count = bucket_ranges_->bucket_count();
   CHECK_GE(bucket_count, 1u);
   CHECK_GE(value, bucket_ranges_->range(0));
   CHECK_LT(value, bucket_ranges_->range(bucket_count));
 
   size_t under = 0;
   size_t over = bucket_count;
   size_t mid;
   do {
     DCHECK_GE(over, under);
     mid = under + (over - under)/2;
     if (mid == under)
       break;
     if (bucket_ranges_->range(mid) <= value)
       under = mid;
     else
       over = mid;
   } while (true);
 
   DCHECK_LE(bucket_ranges_->range(mid), value);
   CHECK_GT(bucket_ranges_->range(mid + 1), value);
   return mid;
 }
 
-void SampleVectorBase::MoveSingleSampleToCounts() {
-  DCHECK(counts());
-
-  // Disable the single-sample since there is now counts storage for the data.
-  SingleSample sample = single_sample().Extract(/*disable=*/true);
-
-  // Stop here if there is no "count" as trying to find the bucket index of
-  // an invalid (including zero) "value" will crash.
-  if (sample.count == 0)
-    return;
-
-  // Move the value into storage. Sum and redundant-count already account
-  // for this entry so no need to call IncreaseSumAndCount().
-  subtle::NoBarrier_AtomicIncrement(&counts()[sample.bucket], sample.count);
-}
-
-void SampleVectorBase::MountCountsStorageAndMoveSingleSample() {
-  // There are many SampleVector objects and the lock is needed very
-  // infrequently (just when advancing from single-sample to multi-sample) so
-  // define a single, global lock that all can use. This lock only prevents
-  // concurrent entry into the code below; access and updates to |counts_|
-  // still requires atomic operations.
-  static LazyInstance<Lock>::Leaky counts_lock = LAZY_INSTANCE_INITIALIZER;
-  if (subtle::NoBarrier_Load(&counts_) == 0) {
-    AutoLock lock(counts_lock.Get());
-    if (subtle::NoBarrier_Load(&counts_) == 0) {
-      // Create the actual counts storage while the above lock is acquired.
-      HistogramBase::Count* counts = CreateCountsStorageWhileLocked();
-      DCHECK(counts);
-
-      // Point |counts_| to the newly created storage. This is done while
-      // locked to prevent possible concurrent calls to CreateCountsStorage
-      // but, between that call and here, other threads could notice the
-      // existance of the storage and race with this to set_counts(). That's
-      // okay because (a) it's atomic and (b) it always writes the same value.
-      set_counts(counts);
-    }
-  }
-
-  // Move any single-sample into the newly mounted storage.
-  MoveSingleSampleToCounts();
-}
-
-SampleVector::SampleVector(const BucketRanges* bucket_ranges)
-    : SampleVector(0, bucket_ranges) {}
-
-SampleVector::SampleVector(uint64_t id, const BucketRanges* bucket_ranges)
-    : SampleVectorBase(id, bucket_ranges) {}
-
-SampleVector::~SampleVector() {}
-
-bool SampleVector::MountExistingCountsStorage() const {
-  // There is never any existing storage other than what is already in use.
-  return counts() != nullptr;
-}
-
-HistogramBase::AtomicCount* SampleVector::CreateCountsStorageWhileLocked() {
-  local_counts_.resize(counts_size());
-  return &local_counts_[0];
-}
-
-PersistentSampleVector::PersistentSampleVector(
-    uint64_t id,
-    const BucketRanges* bucket_ranges,
-    Metadata* meta,
-    const DelayedPersistentAllocation& counts)
-    : SampleVectorBase(id, meta, bucket_ranges), persistent_counts_(counts) {
-  // Only mount the full storage if the single-sample has been disabled.
-  // Otherwise, it is possible for this object instance to start using (empty)
-  // storage that was created incidentally while another instance continues to
-  // update to the single sample. This "incidental creation" can happen because
-  // the memory is a DelayedPersistentAllocation which allows multiple memory
-  // blocks within it and applies an all-or-nothing approach to the allocation.
-  // Thus, a request elsewhere for one of the _other_ blocks would make _this_
-  // block available even though nothing has explicitly requested it.
-  //
-  // Note that it's not possible for the ctor to mount existing storage and
-  // move any single-sample to it because sometimes the persistent memory is
-  // read-only. Only non-const methods (which assume that memory is read/write)
-  // can do that.
-  if (single_sample().IsDisabled()) {
-    bool success = MountExistingCountsStorage();
-    DCHECK(success);
-  }
-}
-
-PersistentSampleVector::~PersistentSampleVector() {}
-
-bool PersistentSampleVector::MountExistingCountsStorage() const {
-  // There is no early exit if counts is not yet mounted because, given that
-  // this is a virtual function, it's more efficient to do that at the call-
-  // site. There is no danger, however, should this get called anyway (perhaps
-  // because of a race condition) because at worst the |counts_| value would
-  // be over-written (in an atomic manner) with the exact same address.
-
-  if (!persistent_counts_.reference())
-    return false;  // Nothing to mount.
-
-  // Mount the counts array in position.
-  set_counts(
-      static_cast<HistogramBase::AtomicCount*>(persistent_counts_.Get()));
-  return true;
-}
-
-HistogramBase::AtomicCount*
-PersistentSampleVector::CreateCountsStorageWhileLocked() {
-  void* mem = persistent_counts_.Get();
-  if (!mem) {
-    // The above shouldn't fail but can if Bad Things(tm) are occurring in the
-    // persistent allocator. Crashing isn't a good option so instead just
-    // allocate something from the heap and return that. There will be no
-    // sharing or persistence but worse things are already happening.
-    return new HistogramBase::AtomicCount[counts_size()];
-  }
-
-  return static_cast<HistogramBase::AtomicCount*>(mem);
-}
-
 SampleVectorIterator::SampleVectorIterator(
     const std::vector<HistogramBase::AtomicCount>* counts,
     const BucketRanges* bucket_ranges)
     : counts_(&(*counts)[0]),
       counts_size_(counts->size()),
       bucket_ranges_(bucket_ranges),
       index_(0) {
   CHECK_GE(bucket_ranges_->bucket_count(), counts_size_);
   SkipEmptyBuckets();
 }
@@ skipping 46 matching lines @@
     return;
 
   while (index_ < counts_size_) {
     if (subtle::NoBarrier_Load(&counts_[index_]) != 0)
       return;
     index_++;
   }
 }
 
 }  // namespace base