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