| 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 |