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