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