OLD | NEW |
1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2011 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 "chrome/browser/safe_browsing/safe_browsing_store.h" | 5 #include "chrome/browser/safe_browsing/safe_browsing_store.h" |
6 | 6 |
7 #include <algorithm> | 7 #include <algorithm> |
8 | 8 |
9 #include "base/metrics/histogram.h" | 9 #include "base/logging.h" |
10 | 10 |
11 namespace { | 11 namespace { |
12 | 12 |
13 // Find items matching between |subs| and |adds|, and remove them, | 13 // Find items matching between |subs| and |adds|, and remove them, |
14 // recording the item from |adds| in |adds_removed|. To minimize | 14 // recording the item from |adds| in |adds_removed|. To minimize |
15 // copies, the inputs are processing in parallel, so |subs| and |adds| | 15 // copies, the inputs are processing in parallel, so |subs| and |adds| |
16 // should be compatibly ordered (either by SBAddPrefixLess or | 16 // should be compatibly ordered (either by SBAddPrefixLess or |
17 // SBAddPrefixHashLess). | 17 // SBAddPrefixHashLess). |
18 // | 18 // |
19 // |predAddSub| provides add < sub, |predSubAdd| provides sub < add, | 19 // |predAddSub| provides add < sub, |predSubAdd| provides sub < add, |
(...skipping 93 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
113 for (typename ItemsT::iterator iter = end_iter; | 113 for (typename ItemsT::iterator iter = end_iter; |
114 iter != items->end(); ++iter) { | 114 iter != items->end(); ++iter) { |
115 if (del_set.count(iter->chunk_id) == 0) { | 115 if (del_set.count(iter->chunk_id) == 0) { |
116 *end_iter = *iter; | 116 *end_iter = *iter; |
117 ++end_iter; | 117 ++end_iter; |
118 } | 118 } |
119 } | 119 } |
120 items->erase(end_iter, items->end()); | 120 items->erase(end_iter, items->end()); |
121 } | 121 } |
122 | 122 |
123 enum MissTypes { | |
124 MISS_TYPE_ALL, | |
125 MISS_TYPE_FALSE, | |
126 | |
127 // Always at the end. | |
128 MISS_TYPE_MAX | |
129 }; | |
130 | |
131 } // namespace | 123 } // namespace |
132 | 124 |
133 void SBCheckPrefixMisses(const SBAddPrefixes& add_prefixes, | |
134 const std::set<SBPrefix>& prefix_misses) { | |
135 if (prefix_misses.empty()) | |
136 return; | |
137 | |
138 // Record a hit for all prefixes which missed when sent to the | |
139 // server. | |
140 for (size_t i = 0; i < prefix_misses.size(); ++i) { | |
141 UMA_HISTOGRAM_ENUMERATION("SB2.BloomFilterFalsePositives", | |
142 MISS_TYPE_ALL, MISS_TYPE_MAX); | |
143 } | |
144 | |
145 // Collect the misses which are not present in |add_prefixes|. | |
146 // Since |add_prefixes| can contain multiple copies of the same | |
147 // prefix, it is not sufficient to count the number of elements | |
148 // present in both collections. | |
149 std::set<SBPrefix> false_misses(prefix_misses.begin(), prefix_misses.end()); | |
150 for (SBAddPrefixes::const_iterator iter = add_prefixes.begin(); | |
151 iter != add_prefixes.end(); ++iter) { | |
152 // |erase()| on an absent element should cost like |find()|. | |
153 false_misses.erase(iter->prefix); | |
154 } | |
155 | |
156 // Record a hit for prefixes which we shouldn't have sent in the | |
157 // first place. | |
158 for (size_t i = 0; i < false_misses.size(); ++i) { | |
159 UMA_HISTOGRAM_ENUMERATION("SB2.BloomFilterFalsePositives", | |
160 MISS_TYPE_FALSE, MISS_TYPE_MAX); | |
161 } | |
162 | |
163 // Divide |MISS_TYPE_FALSE| by |MISS_TYPE_ALL| to get the | |
164 // bloom-filter false-positive rate. | |
165 } | |
166 | |
167 void SBProcessSubs(SBAddPrefixes* add_prefixes, | 125 void SBProcessSubs(SBAddPrefixes* add_prefixes, |
168 SBSubPrefixes* sub_prefixes, | 126 SBSubPrefixes* sub_prefixes, |
169 std::vector<SBAddFullHash>* add_full_hashes, | 127 std::vector<SBAddFullHash>* add_full_hashes, |
170 std::vector<SBSubFullHash>* sub_full_hashes, | 128 std::vector<SBSubFullHash>* sub_full_hashes, |
171 const base::hash_set<int32>& add_chunks_deleted, | 129 const base::hash_set<int32>& add_chunks_deleted, |
172 const base::hash_set<int32>& sub_chunks_deleted) { | 130 const base::hash_set<int32>& sub_chunks_deleted) { |
173 // It is possible to structure templates and template | 131 // It is possible to structure templates and template |
174 // specializations such that the following calls work without having | 132 // specializations such that the following calls work without having |
175 // to qualify things. It becomes very arbitrary, though, and less | 133 // to qualify things. It becomes very arbitrary, though, and less |
176 // clear how things are working. | 134 // clear how things are working. |
(...skipping 30 matching lines...) Expand all Loading... |
207 &removed_full_adds); | 165 &removed_full_adds); |
208 | 166 |
209 // Remove items from the deleted chunks. This is done after other | 167 // Remove items from the deleted chunks. This is done after other |
210 // processing to allow subs to knock out adds (and be removed) even | 168 // processing to allow subs to knock out adds (and be removed) even |
211 // if the add's chunk is deleted. | 169 // if the add's chunk is deleted. |
212 RemoveDeleted(add_prefixes, add_chunks_deleted); | 170 RemoveDeleted(add_prefixes, add_chunks_deleted); |
213 RemoveDeleted(sub_prefixes, sub_chunks_deleted); | 171 RemoveDeleted(sub_prefixes, sub_chunks_deleted); |
214 RemoveDeleted(add_full_hashes, add_chunks_deleted); | 172 RemoveDeleted(add_full_hashes, add_chunks_deleted); |
215 RemoveDeleted(sub_full_hashes, sub_chunks_deleted); | 173 RemoveDeleted(sub_full_hashes, sub_chunks_deleted); |
216 } | 174 } |
OLD | NEW |