text: // 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/numerics/safe_conversions.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.
  
  namespace base {
  
  typedef HistogramBase::Count Count;
  typedef HistogramBase::Sample Sample;
  
  SampleVectorBase::SampleVectorBase(uint64_t id,
                                     Metadata* meta,
                                     const BucketRanges* bucket_ranges)
      : HistogramSamples(id, meta), bucket_ranges_(bucket_ranges) {
    CHECK_GE(bucket_ranges_->bucket_count(), 1u);
  }
  
  SampleVectorBase::~SampleVectorBase() {}
  
  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(strict_cast<int64_t>(count) * value, count);
  }
  
  Count SampleVectorBase::GetCount(Sample value) const {
    return GetCountAtIndex(GetBucketIndex(value));
  }
  
  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;
    }
  
    // And the no-value case.
    return 0;
  }
  
  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;
  }
  
  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_);
  }
  
  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.
    HistogramBase::Sample min;
    int64_t 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;
        }
      }
  
      // 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();
    }
  }
  
  // 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 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
        // existence 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, new LocalMetadata(), bucket_ranges) {}
  
  SampleVector::~SampleVector() {
    delete static_cast<LocalMetadata*>(meta());
  }
  
  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()));
  
    // The above shouldn't fail but can if the data is corrupt or incomplete.
    return counts() != nullptr;
  }
  
  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();
  }
  
  SampleVectorIterator::SampleVectorIterator(
      const HistogramBase::AtomicCount* counts,
      size_t counts_size,
      const BucketRanges* bucket_ranges)
      : counts_(counts),
        counts_size_(counts_size),
        bucket_ranges_(bucket_ranges),
        index_(0) {
    CHECK_GE(bucket_ranges_->bucket_count(), counts_size_);
    SkipEmptyBuckets();
  }
  
  SampleVectorIterator::~SampleVectorIterator() {}
  
  bool SampleVectorIterator::Done() const {
    return index_ >= counts_size_;
  }
  
  void SampleVectorIterator::Next() {
    DCHECK(!Done());
    index_++;
    SkipEmptyBuckets();
  }
  
  void SampleVectorIterator::Get(HistogramBase::Sample* min,
                                 int64_t* max,
                                 HistogramBase::Count* count) const {
    DCHECK(!Done());
    if (min != NULL)
      *min = bucket_ranges_->range(index_);
    if (max != NULL)
      *max = strict_cast<int64_t>(bucket_ranges_->range(index_ + 1));
    if (count != NULL)
      *count = subtle::NoBarrier_Load(&counts_[index_]);
  }
  
  bool SampleVectorIterator::GetBucketIndex(size_t* index) const {
    DCHECK(!Done());
    if (index != NULL)
      *index = index_;
    return true;
  }
  
  void SampleVectorIterator::SkipEmptyBuckets() {
    if (Done())
      return;
  
    while (index_ < counts_size_) {
      if (subtle::NoBarrier_Load(&counts_[index_]) != 0)
        return;
      index_++;
    }
  }
  
  }  // namespace base
  