OLD | NEW |
---|---|
1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "base/metrics/sample_map.h" | 5 #include "base/metrics/sample_map.h" |
6 | 6 |
7 #include "base/logging.h" | 7 #include "base/logging.h" |
8 | 8 |
9 namespace base { | 9 namespace base { |
10 | 10 |
(...skipping 73 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
84 if (count != NULL) | 84 if (count != NULL) |
85 *count = iter_->second; | 85 *count = iter_->second; |
86 } | 86 } |
87 | 87 |
88 void SampleMapIterator::SkipEmptyBuckets() { | 88 void SampleMapIterator::SkipEmptyBuckets() { |
89 while (!Done() && iter_->second == 0) { | 89 while (!Done() && iter_->second == 0) { |
90 ++iter_; | 90 ++iter_; |
91 } | 91 } |
92 } | 92 } |
93 | 93 |
94 | |
95 // ----- PersistentSampleMap --------------------------------------------------- | |
96 | |
97 namespace { | |
98 | |
99 // This structure holds an entry for a PersistentSampleMap within a persistent | |
100 // memory allocator. The "id" must be unique across all maps held by an | |
101 // allocator or they will get attached to the wrong sample map. | |
102 struct SampleRecord { | |
103 uint64_t id; // Unique identifier of owner. | |
104 Sample value; // The value for which this record holds a count. | |
105 Count count; // The count associated with the above value. | |
106 }; | |
107 | |
108 // The type-id used to identify sample records inside an allocator. | |
109 const uint32_t kTypeIdSampleRecord = 0x8FE6A69F + 1; // SHA1(SampleRecord) v1 | |
110 | |
111 } // namespace | |
112 | |
113 PersistentSampleMap::PersistentSampleMap( | |
114 uint64_t id, | |
115 PersistentMemoryAllocator* allocator, | |
116 Metadata* meta) | |
117 : HistogramSamples(id, meta), | |
118 allocator_(allocator) { | |
119 // This is created once but will continue to return new iterables even when | |
120 // it has previously reached the end. | |
121 allocator->CreateIterator(&sample_iter_); | |
122 | |
123 // Load all existing samples during construction. It's no worse to do it | |
124 // here than at some point in the future and could be better if construction | |
125 // takes place on some background thread. New samples could be created at | |
126 // any time by parallel threads; if so, they'll get loaded when needed. | |
127 ImportSamples(-1); | |
128 } | |
129 | |
130 PersistentSampleMap::~PersistentSampleMap() {} | |
131 | |
132 void PersistentSampleMap::Accumulate(Sample value, Count count) { | |
133 *GetSampleCountPointer(value, /*create=*/true) += count; | |
134 IncreaseSum(static_cast<int64_t>(count) * value); | |
135 IncreaseRedundantCount(count); | |
136 } | |
137 | |
138 Count PersistentSampleMap::GetCount(Sample value) const { | |
139 // Have to override "const" to make sure all samples have been loaded before | |
140 // being able to know what value to return. | |
141 Count* count_pointer = | |
142 const_cast<PersistentSampleMap*>(this)->GetSampleCountPointer( | |
143 value, /*create=*/false); | |
144 if (!count_pointer) | |
grt (UTC plus 2)
2016/03/02 20:00:42
nit: return count_pointer ? *count_pointer : 0;
bcwhite
2016/03/02 22:32:43
Done.
| |
145 return 0; | |
146 return *count_pointer; | |
147 } | |
148 | |
149 Count PersistentSampleMap::TotalCount() const { | |
150 // Have to override "const" in order to make sure all samples have been | |
151 // loaded before trying to iterate over the map. | |
152 const_cast<PersistentSampleMap*>(this)->ImportSamples(-1); | |
153 | |
154 Count count = 0; | |
155 for (const auto& entry : sample_counts_) { | |
grt (UTC plus 2)
2016/03/02 20:00:42
nit: omit braces
bcwhite
2016/03/02 22:32:43
Done. Above, too.
| |
156 count += *entry.second; | |
157 } | |
158 return count; | |
159 } | |
160 | |
161 scoped_ptr<SampleCountIterator> PersistentSampleMap::Iterator() const { | |
162 // Have to override "const" in order to make sure all samples have been | |
163 // loaded before trying to iterate over the map. | |
164 const_cast<PersistentSampleMap*>(this)->ImportSamples(-1); | |
165 | |
166 return scoped_ptr<SampleCountIterator>( | |
grt (UTC plus 2)
2016/03/02 20:00:42
does this work:
return make_scoped_ptr(new Persi
bcwhite
2016/03/02 22:32:43
Done.
| |
167 new PersistentSampleMapIterator(sample_counts_)); | |
168 } | |
169 | |
170 bool PersistentSampleMap::AddSubtractImpl(SampleCountIterator* iter, | |
171 HistogramSamples::Operator op) { | |
grt (UTC plus 2)
2016/03/02 20:00:42
HistogramSamples:: not needed
bcwhite
2016/03/02 22:32:43
Done.
| |
172 Sample min; | |
173 Sample max; | |
174 Count count; | |
175 for (; !iter->Done(); iter->Next()) { | |
176 iter->Get(&min, &max, &count); | |
177 if (min + 1 != max) | |
178 return false; // SparseHistogram only supports bucket with size 1. | |
179 | |
180 *GetSampleCountPointer(min, /*create=*/true) += | |
181 (op == HistogramSamples::ADD) ? count : -count; | |
grt (UTC plus 2)
2016/03/02 20:00:42
HistogramSamples:: not needed. unless ADD is too o
bcwhite
2016/03/02 22:32:43
Done.
| |
182 } | |
183 return true; | |
184 } | |
185 | |
186 Count* PersistentSampleMap::GetSampleCountPointer(HistogramBase::Sample value, | |
grt (UTC plus 2)
2016/03/02 20:00:42
omit HistogramBase:: thanks to typedef at top of f
bcwhite
2016/03/02 22:32:43
Done.
| |
187 bool create_if_necessary) { | |
188 DCHECK_LE(0, value); | |
189 | |
190 // If |value| is already in the map, just return that. | |
191 auto it = sample_counts_.find(value); | |
192 if (it != sample_counts_.end()) | |
193 return it->second; | |
194 | |
195 // Import any new samples from persistent memory looking for the value. | |
196 Count* count_pointer = ImportSamples(value); | |
197 if (count_pointer) | |
198 return count_pointer; | |
199 | |
200 // Stop here if no creation of new samples is desired. | |
201 if (!create_if_necessary) | |
202 return nullptr; | |
203 | |
204 // Create a new record in persistent memory for the value. | |
205 PersistentMemoryAllocator::Reference ref = | |
206 allocator_->Allocate(sizeof(SampleRecord), kTypeIdSampleRecord); | |
207 SampleRecord* record = | |
208 allocator_->GetAsObject<SampleRecord>(ref, kTypeIdSampleRecord); | |
209 if (!record) { | |
210 // If the allocator was unable to create a record then it is full or | |
211 // corrupt. Instead, allocate the counter from the heap. This sample will | |
212 // not be persistent, will not be shared, and will leak but it's better | |
213 // than crashing. | |
214 NOTREACHED() << "full=" << allocator_->IsFull() | |
215 << ", corrupt=" << allocator_->IsCorrupt(); | |
216 count_pointer = new Count(0); | |
217 sample_counts_[value] = count_pointer; | |
218 return count_pointer; | |
219 } | |
220 record->id = id(); | |
221 record->value = value; | |
222 // record->count = 0 because allocator guarantees zero'd memory. | |
223 allocator_->MakeIterable(ref); | |
224 | |
225 // A race condition could cause two of the above records to be created. The | |
226 // allocator, however, forces a strict ordering on iterable objects so use | |
227 // the import method to actually add the just-created record. This ensures | |
228 // that all PersistentSampleMap objects will always use the same record, | |
229 // whichever was first made iterable. | |
230 count_pointer = ImportSamples(value); | |
231 DCHECK(count_pointer); | |
232 return count_pointer; | |
233 } | |
234 | |
235 Count* PersistentSampleMap::ImportSamples(HistogramBase::Sample until_value) { | |
236 // TODO(bcwhite): This import operates in O(V+N) total time per sparse | |
237 // histogram where V is the number of values for this object and N is | |
238 // the number of other iterable objects in the allocator. This becomes | |
239 // O(S*(SV+N)) or O(S^2*V + SN) overall where S is the number of sparse | |
240 // histograms. | |
241 // | |
242 // This is actually okay when histograms are expected to exist for the | |
243 // lifetime of the program, spreading the cost out, and S and V are | |
244 // relatively small, as is the current case. | |
245 // | |
246 // However, it is not so good for objects that are created, detroyed, and | |
247 // recreated on a periodic basis, such as when making a snapshot of | |
248 // sparse histograms owned by another, ongoing process. In that case, the | |
249 // entire cost is compressed into a single sequential operation... on the | |
250 // UI thread no less. | |
251 // | |
252 // This will be addressed in a future CL. | |
253 | |
254 uint32_t type_id; | |
255 PersistentMemoryAllocator::Reference ref; | |
256 while ((ref = allocator_->GetNextIterable(&sample_iter_, &type_id)) != 0) { | |
257 if (type_id == kTypeIdSampleRecord) { | |
258 SampleRecord* record = | |
259 allocator_->GetAsObject<SampleRecord>(ref, kTypeIdSampleRecord); | |
260 if (!record) | |
261 continue; | |
262 | |
263 // A sample record has been found but may not be for this histogram. | |
264 if (record->id != id()) | |
265 continue; | |
266 | |
267 // Check if the record's value is already known. | |
268 if (sample_counts_.find(record->value) == sample_counts_.end()) { | |
grt (UTC plus 2)
2016/03/02 20:00:42
#include "base/stl_util.h"
if (!ContainsKey(sample
bcwhite
2016/03/02 22:32:43
Done.
| |
269 // No: Add it to map of known values if the value is valid. | |
270 if (record->value >= 0) | |
271 sample_counts_[record->value] = &record->count; | |
272 } else { | |
273 // Yes: Ignore it; it's a duplicate caused by a race condition. | |
274 DCHECK_EQ(0, record->count); // Duplicate record should never be used. | |
275 } | |
276 | |
277 // Stop if it's the value being searched for. | |
278 if (record->value == until_value) | |
279 return &record->count; | |
280 } | |
281 } | |
282 | |
283 return nullptr; | |
284 } | |
285 | |
286 PersistentSampleMapIterator::PersistentSampleMapIterator( | |
287 const SampleToCountMap& sample_counts) | |
288 : iter_(sample_counts.begin()), | |
289 end_(sample_counts.end()) { | |
290 SkipEmptyBuckets(); | |
291 } | |
292 | |
293 PersistentSampleMapIterator::~PersistentSampleMapIterator() {} | |
294 | |
295 bool PersistentSampleMapIterator::Done() const { | |
296 return iter_ == end_; | |
297 } | |
298 | |
299 void PersistentSampleMapIterator::Next() { | |
300 DCHECK(!Done()); | |
301 ++iter_; | |
302 SkipEmptyBuckets(); | |
303 } | |
304 | |
305 void PersistentSampleMapIterator::Get(Sample* min, | |
306 Sample* max, | |
307 Count* count) const { | |
308 DCHECK(!Done()); | |
309 if (min != NULL) | |
grt (UTC plus 2)
2016/03/02 20:00:42
if (min)
...
bcwhite
2016/03/02 22:32:43
Done.
| |
310 *min = iter_->first; | |
311 if (max != NULL) | |
312 *max = iter_->first + 1; | |
313 if (count != NULL) | |
314 *count = *iter_->second; | |
315 } | |
316 | |
317 void PersistentSampleMapIterator::SkipEmptyBuckets() { | |
318 while (!Done() && *iter_->second == 0) { | |
grt (UTC plus 2)
2016/03/02 20:00:42
nit: omit braces
bcwhite
2016/03/02 22:32:43
Done.
| |
319 ++iter_; | |
320 } | |
321 } | |
322 | |
94 } // namespace base | 323 } // namespace base |
OLD | NEW |