Home | History | Annotate | Download | only in metrics 
      1 // Copyright 2016 The Chromium Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include "base/metrics/persistent_sample_map.h"
      6 
      7 #include "base/logging.h"
      8 #include "base/memory/ptr_util.h"
      9 #include "base/metrics/histogram_macros.h"
     10 #include "base/metrics/persistent_histogram_allocator.h"
     11 #include "base/numerics/safe_conversions.h"
     12 #include "base/stl_util.h"
     13 
     14 namespace base {
     15 
     16 typedef HistogramBase::Count Count;
     17 typedef HistogramBase::Sample Sample;
     18 
     19 namespace {
     20 
     21 // An iterator for going through a PersistentSampleMap. The logic here is
     22 // identical to that of SampleMapIterator but with different data structures.
     23 // Changes here likely need to be duplicated there.
     24 class PersistentSampleMapIterator : public SampleCountIterator {
     25  public:
     26   typedef std::map<HistogramBase::Sample, HistogramBase::Count*>
     27       SampleToCountMap;
     28 
     29   explicit PersistentSampleMapIterator(const SampleToCountMap& sample_counts);
     30   ~PersistentSampleMapIterator() override;
     31 
     32   // SampleCountIterator:
     33   bool Done() const override;
     34   void Next() override;
     35   void Get(HistogramBase::Sample* min,
     36            int64_t* max,
     37            HistogramBase::Count* count) const override;
     38 
     39  private:
     40   void SkipEmptyBuckets();
     41 
     42   SampleToCountMap::const_iterator iter_;
     43   const SampleToCountMap::const_iterator end_;
     44 };
     45 
     46 PersistentSampleMapIterator::PersistentSampleMapIterator(
     47     const SampleToCountMap& sample_counts)
     48     : iter_(sample_counts.begin()),
     49       end_(sample_counts.end()) {
     50   SkipEmptyBuckets();
     51 }
     52 
     53 PersistentSampleMapIterator::~PersistentSampleMapIterator() = default;
     54 
     55 bool PersistentSampleMapIterator::Done() const {
     56   return iter_ == end_;
     57 }
     58 
     59 void PersistentSampleMapIterator::Next() {
     60   DCHECK(!Done());
     61   ++iter_;
     62   SkipEmptyBuckets();
     63 }
     64 
     65 void PersistentSampleMapIterator::Get(Sample* min,
     66                                       int64_t* max,
     67                                       Count* count) const {
     68   DCHECK(!Done());
     69   if (min)
     70     *min = iter_->first;
     71   if (max)
     72     *max = strict_cast<int64_t>(iter_->first) + 1;
     73   if (count)
     74     *count = *iter_->second;
     75 }
     76 
     77 void PersistentSampleMapIterator::SkipEmptyBuckets() {
     78   while (!Done() && *iter_->second == 0) {
     79     ++iter_;
     80   }
     81 }
     82 
     83 // This structure holds an entry for a PersistentSampleMap within a persistent
     84 // memory allocator. The "id" must be unique across all maps held by an
     85 // allocator or they will get attached to the wrong sample map.
     86 struct SampleRecord {
     87   // SHA1(SampleRecord): Increment this if structure changes!
     88   static constexpr uint32_t kPersistentTypeId = 0x8FE6A69F + 1;
     89 
     90   // Expected size for 32/64-bit check.
     91   static constexpr size_t kExpectedInstanceSize = 16;
     92 
     93   uint64_t id;   // Unique identifier of owner.
     94   Sample value;  // The value for which this record holds a count.
     95   Count count;   // The count associated with the above value.
     96 };
     97 
     98 }  // namespace
     99 
    100 PersistentSampleMap::PersistentSampleMap(
    101     uint64_t id,
    102     PersistentHistogramAllocator* allocator,
    103     Metadata* meta)
    104     : HistogramSamples(id, meta), allocator_(allocator) {}
    105 
    106 PersistentSampleMap::~PersistentSampleMap() {
    107   if (records_)
    108     records_->Release(this);
    109 }
    110 
    111 void PersistentSampleMap::Accumulate(Sample value, Count count) {
    112 #if 0  // TODO(bcwhite) Re-enable efficient version after crbug.com/682680.
    113   *GetOrCreateSampleCountStorage(value) += count;
    114 #else
    115   Count* local_count_ptr = GetOrCreateSampleCountStorage(value);
    116   if (count < 0) {
    117     if (*local_count_ptr < -count)
    118       RecordNegativeSample(SAMPLES_ACCUMULATE_WENT_NEGATIVE, -count);
    119     else
    120       RecordNegativeSample(SAMPLES_ACCUMULATE_NEGATIVE_COUNT, -count);
    121     *local_count_ptr += count;
    122   } else {
    123     Sample old_value = *local_count_ptr;
    124     Sample new_value = old_value + count;
    125     *local_count_ptr = new_value;
    126     if ((new_value >= 0) != (old_value >= 0))
    127       RecordNegativeSample(SAMPLES_ACCUMULATE_OVERFLOW, count);
    128   }
    129 #endif
    130   IncreaseSumAndCount(strict_cast<int64_t>(count) * value, count);
    131 }
    132 
    133 Count PersistentSampleMap::GetCount(Sample value) const {
    134   // Have to override "const" to make sure all samples have been loaded before
    135   // being able to know what value to return.
    136   Count* count_pointer =
    137       const_cast<PersistentSampleMap*>(this)->GetSampleCountStorage(value);
    138   return count_pointer ? *count_pointer : 0;
    139 }
    140 
    141 Count PersistentSampleMap::TotalCount() const {
    142   // Have to override "const" in order to make sure all samples have been
    143   // loaded before trying to iterate over the map.
    144   const_cast<PersistentSampleMap*>(this)->ImportSamples(-1, true);
    145 
    146   Count count = 0;
    147   for (const auto& entry : sample_counts_) {
    148     count += *entry.second;
    149   }
    150   return count;
    151 }
    152 
    153 std::unique_ptr<SampleCountIterator> PersistentSampleMap::Iterator() const {
    154   // Have to override "const" in order to make sure all samples have been
    155   // loaded before trying to iterate over the map.
    156   const_cast<PersistentSampleMap*>(this)->ImportSamples(-1, true);
    157   return WrapUnique(new PersistentSampleMapIterator(sample_counts_));
    158 }
    159 
    160 // static
    161 PersistentMemoryAllocator::Reference
    162 PersistentSampleMap::GetNextPersistentRecord(
    163     PersistentMemoryAllocator::Iterator& iterator,
    164     uint64_t* sample_map_id) {
    165   const SampleRecord* record = iterator.GetNextOfObject<SampleRecord>();
    166   if (!record)
    167     return 0;
    168 
    169   *sample_map_id = record->id;
    170   return iterator.GetAsReference(record);
    171 }
    172 
    173 // static
    174 PersistentMemoryAllocator::Reference
    175 PersistentSampleMap::CreatePersistentRecord(
    176     PersistentMemoryAllocator* allocator,
    177     uint64_t sample_map_id,
    178     Sample value) {
    179   SampleRecord* record = allocator->New<SampleRecord>();
    180   if (!record) {
    181     NOTREACHED() << "full=" << allocator->IsFull()
    182                  << ", corrupt=" << allocator->IsCorrupt();
    183     return 0;
    184   }
    185 
    186   record->id = sample_map_id;
    187   record->value = value;
    188   record->count = 0;
    189 
    190   PersistentMemoryAllocator::Reference ref = allocator->GetAsReference(record);
    191   allocator->MakeIterable(ref);
    192   return ref;
    193 }
    194 
    195 bool PersistentSampleMap::AddSubtractImpl(SampleCountIterator* iter,
    196                                           Operator op) {
    197   Sample min;
    198   int64_t max;
    199   Count count;
    200   for (; !iter->Done(); iter->Next()) {
    201     iter->Get(&min, &max, &count);
    202     if (count == 0)
    203       continue;
    204     if (strict_cast<int64_t>(min) + 1 != max)
    205       return false;  // SparseHistogram only supports bucket with size 1.
    206     *GetOrCreateSampleCountStorage(min) +=
    207         (op == HistogramSamples::ADD) ? count : -count;
    208   }
    209   return true;
    210 }
    211 
    212 Count* PersistentSampleMap::GetSampleCountStorage(Sample value) {
    213   // If |value| is already in the map, just return that.
    214   auto it = sample_counts_.find(value);
    215   if (it != sample_counts_.end())
    216     return it->second;
    217 
    218   // Import any new samples from persistent memory looking for the value.
    219   return ImportSamples(value, false);
    220 }
    221 
    222 Count* PersistentSampleMap::GetOrCreateSampleCountStorage(Sample value) {
    223   // Get any existing count storage.
    224   Count* count_pointer = GetSampleCountStorage(value);
    225   if (count_pointer)
    226     return count_pointer;
    227 
    228   // Create a new record in persistent memory for the value. |records_| will
    229   // have been initialized by the GetSampleCountStorage() call above.
    230   DCHECK(records_);
    231   PersistentMemoryAllocator::Reference ref = records_->CreateNew(value);
    232   if (!ref) {
    233     // If a new record could not be created then the underlying allocator is
    234     // full or corrupt. Instead, allocate the counter from the heap. This
    235     // sample will not be persistent, will not be shared, and will leak...
    236     // but it's better than crashing.
    237     count_pointer = new Count(0);
    238     sample_counts_[value] = count_pointer;
    239     return count_pointer;
    240   }
    241 
    242   // A race condition between two independent processes (i.e. two independent
    243   // histogram objects sharing the same sample data) could cause two of the
    244   // above records to be created. The allocator, however, forces a strict
    245   // ordering on iterable objects so use the import method to actually add the
    246   // just-created record. This ensures that all PersistentSampleMap objects
    247   // will always use the same record, whichever was first made iterable.
    248   // Thread-safety within a process where multiple threads use the same
    249   // histogram object is delegated to the controlling histogram object which,
    250   // for sparse histograms, is a lock object.
    251   count_pointer = ImportSamples(value, false);
    252   DCHECK(count_pointer);
    253   return count_pointer;
    254 }
    255 
    256 PersistentSampleMapRecords* PersistentSampleMap::GetRecords() {
    257   // The |records_| pointer is lazily fetched from the |allocator_| only on
    258   // first use. Sometimes duplicate histograms are created by race conditions
    259   // and if both were to grab the records object, there would be a conflict.
    260   // Use of a histogram, and thus a call to this method, won't occur until
    261   // after the histogram has been de-dup'd.
    262   if (!records_)
    263     records_ = allocator_->UseSampleMapRecords(id(), this);
    264   return records_;
    265 }
    266 
    267 Count* PersistentSampleMap::ImportSamples(Sample until_value,
    268                                           bool import_everything) {
    269   Count* found_count = nullptr;
    270   PersistentMemoryAllocator::Reference ref;
    271   PersistentSampleMapRecords* records = GetRecords();
    272   while ((ref = records->GetNext()) != 0) {
    273     SampleRecord* record = records->GetAsObject<SampleRecord>(ref);
    274     if (!record)
    275       continue;
    276 
    277     DCHECK_EQ(id(), record->id);
    278 
    279     // Check if the record's value is already known.
    280     if (!ContainsKey(sample_counts_, record->value)) {
    281       // No: Add it to map of known values.
    282       sample_counts_[record->value] = &record->count;
    283     } else {
    284       // Yes: Ignore it; it's a duplicate caused by a race condition -- see
    285       // code & comment in GetOrCreateSampleCountStorage() for details.
    286       // Check that nothing ever operated on the duplicate record.
    287       DCHECK_EQ(0, record->count);
    288     }
    289 
    290     // Check if it's the value being searched for and, if so, keep a pointer
    291     // to return later. Stop here unless everything is being imported.
    292     // Because race conditions can cause multiple records for a single value,
    293     // be sure to return the first one found.
    294     if (record->value == until_value) {
    295       if (!found_count)
    296         found_count = &record->count;
    297       if (!import_everything)
    298         break;
    299     }
    300   }
    301 
    302   return found_count;
    303 }
    304 
    305 }  // namespace base
    306