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