OLD | NEW |
(Empty) | |
| 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/stl_util.h" |
| 9 |
| 10 namespace base { |
| 11 |
| 12 typedef HistogramBase::Count Count; |
| 13 typedef HistogramBase::Sample Sample; |
| 14 |
| 15 namespace { |
| 16 |
| 17 // An iterator for going through a PersistentSampleMap. The logic here is |
| 18 // identical to that of SampleMapIterator but with different data structures. |
| 19 // Changes here likely need to be duplicated there. |
| 20 class PersistentSampleMapIterator : public SampleCountIterator { |
| 21 public: |
| 22 typedef std::map<HistogramBase::Sample, HistogramBase::Count*> |
| 23 SampleToCountMap; |
| 24 |
| 25 explicit PersistentSampleMapIterator(const SampleToCountMap& sample_counts); |
| 26 ~PersistentSampleMapIterator() override; |
| 27 |
| 28 // SampleCountIterator: |
| 29 bool Done() const override; |
| 30 void Next() override; |
| 31 void Get(HistogramBase::Sample* min, |
| 32 HistogramBase::Sample* max, |
| 33 HistogramBase::Count* count) const override; |
| 34 |
| 35 private: |
| 36 void SkipEmptyBuckets(); |
| 37 |
| 38 SampleToCountMap::const_iterator iter_; |
| 39 const SampleToCountMap::const_iterator end_; |
| 40 }; |
| 41 |
| 42 PersistentSampleMapIterator::PersistentSampleMapIterator( |
| 43 const SampleToCountMap& sample_counts) |
| 44 : iter_(sample_counts.begin()), |
| 45 end_(sample_counts.end()) { |
| 46 SkipEmptyBuckets(); |
| 47 } |
| 48 |
| 49 PersistentSampleMapIterator::~PersistentSampleMapIterator() {} |
| 50 |
| 51 bool PersistentSampleMapIterator::Done() const { |
| 52 return iter_ == end_; |
| 53 } |
| 54 |
| 55 void PersistentSampleMapIterator::Next() { |
| 56 DCHECK(!Done()); |
| 57 ++iter_; |
| 58 SkipEmptyBuckets(); |
| 59 } |
| 60 |
| 61 void PersistentSampleMapIterator::Get(Sample* min, |
| 62 Sample* max, |
| 63 Count* count) const { |
| 64 DCHECK(!Done()); |
| 65 if (min) |
| 66 *min = iter_->first; |
| 67 if (max) |
| 68 *max = iter_->first + 1; |
| 69 if (count) |
| 70 *count = *iter_->second; |
| 71 } |
| 72 |
| 73 void PersistentSampleMapIterator::SkipEmptyBuckets() { |
| 74 while (!Done() && *iter_->second == 0) { |
| 75 ++iter_; |
| 76 } |
| 77 } |
| 78 |
| 79 // This structure holds an entry for a PersistentSampleMap within a persistent |
| 80 // memory allocator. The "id" must be unique across all maps held by an |
| 81 // allocator or they will get attached to the wrong sample map. |
| 82 struct SampleRecord { |
| 83 uint64_t id; // Unique identifier of owner. |
| 84 Sample value; // The value for which this record holds a count. |
| 85 Count count; // The count associated with the above value. |
| 86 }; |
| 87 |
| 88 // The type-id used to identify sample records inside an allocator. |
| 89 const uint32_t kTypeIdSampleRecord = 0x8FE6A69F + 1; // SHA1(SampleRecord) v1 |
| 90 |
| 91 } // namespace |
| 92 |
| 93 PersistentSampleMap::PersistentSampleMap( |
| 94 uint64_t id, |
| 95 PersistentMemoryAllocator* allocator, |
| 96 Metadata* meta) |
| 97 : HistogramSamples(id, meta), |
| 98 allocator_(allocator) { |
| 99 // This is created once but will continue to return new iterables even when |
| 100 // it has previously reached the end. |
| 101 allocator->CreateIterator(&sample_iter_); |
| 102 |
| 103 // Load all existing samples during construction. It's no worse to do it |
| 104 // here than at some point in the future and could be better if construction |
| 105 // takes place on some background thread. New samples could be created at |
| 106 // any time by parallel threads; if so, they'll get loaded when needed. |
| 107 ImportSamples(kAllSamples); |
| 108 } |
| 109 |
| 110 PersistentSampleMap::~PersistentSampleMap() {} |
| 111 |
| 112 void PersistentSampleMap::Accumulate(Sample value, Count count) { |
| 113 *GetOrCreateSampleCountStorage(value) += count; |
| 114 IncreaseSum(static_cast<int64_t>(count) * value); |
| 115 IncreaseRedundantCount(count); |
| 116 } |
| 117 |
| 118 Count PersistentSampleMap::GetCount(Sample value) const { |
| 119 // Have to override "const" to make sure all samples have been loaded before |
| 120 // being able to know what value to return. |
| 121 Count* count_pointer = |
| 122 const_cast<PersistentSampleMap*>(this)->GetSampleCountStorage(value); |
| 123 return count_pointer ? *count_pointer : 0; |
| 124 } |
| 125 |
| 126 Count PersistentSampleMap::TotalCount() const { |
| 127 // Have to override "const" in order to make sure all samples have been |
| 128 // loaded before trying to iterate over the map. |
| 129 const_cast<PersistentSampleMap*>(this)->ImportSamples(kAllSamples); |
| 130 |
| 131 Count count = 0; |
| 132 for (const auto& entry : sample_counts_) { |
| 133 count += *entry.second; |
| 134 } |
| 135 return count; |
| 136 } |
| 137 |
| 138 scoped_ptr<SampleCountIterator> PersistentSampleMap::Iterator() const { |
| 139 // Have to override "const" in order to make sure all samples have been |
| 140 // loaded before trying to iterate over the map. |
| 141 const_cast<PersistentSampleMap*>(this)->ImportSamples(kAllSamples); |
| 142 return make_scoped_ptr(new PersistentSampleMapIterator(sample_counts_)); |
| 143 } |
| 144 |
| 145 bool PersistentSampleMap::AddSubtractImpl(SampleCountIterator* iter, |
| 146 Operator op) { |
| 147 Sample min; |
| 148 Sample max; |
| 149 Count count; |
| 150 for (; !iter->Done(); iter->Next()) { |
| 151 iter->Get(&min, &max, &count); |
| 152 if (min + 1 != max) |
| 153 return false; // SparseHistogram only supports bucket with size 1. |
| 154 |
| 155 *GetOrCreateSampleCountStorage(min) += |
| 156 (op == HistogramSamples::ADD) ? count : -count; |
| 157 } |
| 158 return true; |
| 159 } |
| 160 |
| 161 Count* PersistentSampleMap::GetSampleCountStorage(Sample value) { |
| 162 DCHECK_LE(0, value); |
| 163 |
| 164 // If |value| is already in the map, just return that. |
| 165 auto it = sample_counts_.find(value); |
| 166 if (it != sample_counts_.end()) |
| 167 return it->second; |
| 168 |
| 169 // Import any new samples from persistent memory looking for the value. |
| 170 return ImportSamples(value); |
| 171 } |
| 172 |
| 173 Count* PersistentSampleMap::GetOrCreateSampleCountStorage(Sample value) { |
| 174 // Get any existing count storage. |
| 175 Count* count_pointer = GetSampleCountStorage(value); |
| 176 if (count_pointer) |
| 177 return count_pointer; |
| 178 |
| 179 // Create a new record in persistent memory for the value. |
| 180 PersistentMemoryAllocator::Reference ref = |
| 181 allocator_->Allocate(sizeof(SampleRecord), kTypeIdSampleRecord); |
| 182 SampleRecord* record = |
| 183 allocator_->GetAsObject<SampleRecord>(ref, kTypeIdSampleRecord); |
| 184 if (!record) { |
| 185 // If the allocator was unable to create a record then it is full or |
| 186 // corrupt. Instead, allocate the counter from the heap. This sample will |
| 187 // not be persistent, will not be shared, and will leak but it's better |
| 188 // than crashing. |
| 189 NOTREACHED() << "full=" << allocator_->IsFull() |
| 190 << ", corrupt=" << allocator_->IsCorrupt(); |
| 191 count_pointer = new Count(0); |
| 192 sample_counts_[value] = count_pointer; |
| 193 return count_pointer; |
| 194 } |
| 195 record->id = id(); |
| 196 record->value = value; |
| 197 record->count = 0; // Should already be zero but don't trust other processes. |
| 198 allocator_->MakeIterable(ref); |
| 199 |
| 200 // A race condition between two independent processes (i.e. two independent |
| 201 // histogram objects sharing the same sample data) could cause two of the |
| 202 // above records to be created. The allocator, however, forces a strict |
| 203 // ordering on iterable objects so use the import method to actually add the |
| 204 // just-created record. This ensures that all PersistentSampleMap objects |
| 205 // will always use the same record, whichever was first made iterable. |
| 206 // Thread-safety within a process where multiple threads use the same |
| 207 // histogram object is delegated to the controlling histogram object which, |
| 208 // for sparse histograms, is a lock object. |
| 209 count_pointer = ImportSamples(value); |
| 210 DCHECK(count_pointer); |
| 211 return count_pointer; |
| 212 } |
| 213 |
| 214 Count* PersistentSampleMap::ImportSamples(Sample until_value) { |
| 215 // TODO(bcwhite): This import operates in O(V+N) total time per sparse |
| 216 // histogram where V is the number of values for this object and N is |
| 217 // the number of other iterable objects in the allocator. This becomes |
| 218 // O(S*(SV+N)) or O(S^2*V + SN) overall where S is the number of sparse |
| 219 // histograms. |
| 220 // |
| 221 // This is actually okay when histograms are expected to exist for the |
| 222 // lifetime of the program, spreading the cost out, and S and V are |
| 223 // relatively small, as is the current case. |
| 224 // |
| 225 // However, it is not so good for objects that are created, detroyed, and |
| 226 // recreated on a periodic basis, such as when making a snapshot of |
| 227 // sparse histograms owned by another, ongoing process. In that case, the |
| 228 // entire cost is compressed into a single sequential operation... on the |
| 229 // UI thread no less. |
| 230 // |
| 231 // This will be addressed in a future CL. |
| 232 |
| 233 uint32_t type_id; |
| 234 PersistentMemoryAllocator::Reference ref; |
| 235 while ((ref = allocator_->GetNextIterable(&sample_iter_, &type_id)) != 0) { |
| 236 if (type_id == kTypeIdSampleRecord) { |
| 237 SampleRecord* record = |
| 238 allocator_->GetAsObject<SampleRecord>(ref, kTypeIdSampleRecord); |
| 239 if (!record) |
| 240 continue; |
| 241 |
| 242 // A sample record has been found but may not be for this histogram. |
| 243 if (record->id != id()) |
| 244 continue; |
| 245 |
| 246 // Check if the record's value is already known. |
| 247 if (!ContainsKey(sample_counts_, record->value)) { |
| 248 // No: Add it to map of known values if the value is valid. |
| 249 if (record->value >= 0) |
| 250 sample_counts_[record->value] = &record->count; |
| 251 } else { |
| 252 // Yes: Ignore it; it's a duplicate caused by a race condition -- see |
| 253 // code & comment in GetOrCreateSampleCountStorage() for details. |
| 254 // Check that nothing ever operated on the duplicate record. |
| 255 DCHECK_EQ(0, record->count); |
| 256 } |
| 257 |
| 258 // Stop if it's the value being searched for. |
| 259 if (record->value == until_value) |
| 260 return &record->count; |
| 261 } |
| 262 } |
| 263 |
| 264 return nullptr; |
| 265 } |
| 266 |
| 267 } // namespace base |
OLD | NEW |