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
PersistentSampleMapIterator(const SampleToCountMap & sample_counts)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
Done() const55 bool PersistentSampleMapIterator::Done() const {
56 return iter_ == end_;
57 }
58
Next()59 void PersistentSampleMapIterator::Next() {
60 DCHECK(!Done());
61 ++iter_;
62 SkipEmptyBuckets();
63 }
64
Get(Sample * min,int64_t * max,Count * count) const65 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
SkipEmptyBuckets()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
PersistentSampleMap(uint64_t id,PersistentHistogramAllocator * allocator,Metadata * meta)100 PersistentSampleMap::PersistentSampleMap(
101 uint64_t id,
102 PersistentHistogramAllocator* allocator,
103 Metadata* meta)
104 : HistogramSamples(id, meta), allocator_(allocator) {}
105
~PersistentSampleMap()106 PersistentSampleMap::~PersistentSampleMap() {
107 if (records_)
108 records_->Release(this);
109 }
110
Accumulate(Sample value,Count count)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
GetCount(Sample value) const133 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
TotalCount() const141 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
Iterator() const153 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
GetNextPersistentRecord(PersistentMemoryAllocator::Iterator & iterator,uint64_t * sample_map_id)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
CreatePersistentRecord(PersistentMemoryAllocator * allocator,uint64_t sample_map_id,Sample value)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
AddSubtractImpl(SampleCountIterator * iter,Operator op)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
GetSampleCountStorage(Sample value)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
GetOrCreateSampleCountStorage(Sample value)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
GetRecords()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
ImportSamples(Sample until_value,bool import_everything)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