Check PrefixSet results for sorting and duplication.

chrome/browser/safe_browsing/safe_browsing_database.cc

 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "chrome/browser/safe_browsing/safe_browsing_database.h"
 
 #include <algorithm>
 
 #include "base/file_util.h"
 #include "base/metrics/histogram.h"
@@ skipping 199 matching lines @@
 // The following is to log actual performance to verify this.
 enum PrefixSetEvent {
   PREFIX_SET_EVENT_HIT,
   PREFIX_SET_EVENT_BLOOM_HIT,
   PREFIX_SET_EVENT_BLOOM_MISS_PREFIX_HIT,
   PREFIX_SET_EVENT_BLOOM_MISS_PREFIX_HIT_INVALID,
   PREFIX_SET_GETPREFIXES_BROKEN,
   PREFIX_SET_GETPREFIXES_BROKEN_SIZE,
   PREFIX_SET_GETPREFIXES_FIRST_BROKEN,
   PREFIX_SET_SBPREFIX_WAS_BROKEN,
+  PREFIX_SET_GETPREFIXES_BROKEN_SORTING,
+  PREFIX_SET_GETPREFIXES_BROKEN_DUPLICATION,
 
   // Memory space for histograms is determined by the max.  ALWAYS ADD
   // NEW VALUES BEFORE THIS ONE.
   PREFIX_SET_EVENT_MAX
 };
 
 void RecordPrefixSetInfo(PrefixSetEvent event_type) {
   UMA_HISTOGRAM_ENUMERATION("SB2.PrefixSetEvent", event_type,
                             PREFIX_SET_EVENT_MAX);
 }
@@ skipping 42 matching lines @@
   if (!logged_broken) {
     RecordPrefixSetInfo(PREFIX_SET_GETPREFIXES_FIRST_BROKEN);
     logged_broken = true;
   }
 
   // This seems so very very unlikely.  But if it ever were true, then
   // it could explain why GetPrefixes() seemed broken.
   if (sizeof(int) != sizeof(int32))
     RecordPrefixSetInfo(PREFIX_SET_SBPREFIX_WAS_BROKEN);
 
+  // Check whether |restored| is unsorted, or has duplication.
+  if (restored.size()) {
+    bool unsorted = false;
+    bool duplicates = false;
+    std::vector<SBPrefix>::const_iterator prev = restored.begin();
+    for (std::vector<SBPrefix>::const_iterator iter = prev + 1;
+         iter != restored.end(); prev = iter, ++iter) {
+      if (*prev > *iter)
+        unsorted = true;
+      if (*prev == *iter)
+        duplicates = true;
+    }
+
+    // Record findings.
+    if (unsorted)
+      RecordPrefixSetInfo(PREFIX_SET_GETPREFIXES_BROKEN_SORTING);
+    if (duplicates)
+      RecordPrefixSetInfo(PREFIX_SET_GETPREFIXES_BROKEN_DUPLICATION);
+
+    // Fix the problems noted.  If |restored| was unsorted, then
+    // |duplicates| may give a false negative.
+    if (unsorted)
+      std::sort(restored.begin(), restored.end());
+    if (unsorted || duplicates)
+      restored.erase(std::unique(restored.begin(), restored.end()),
+                     restored.end());
+  }
+
+  // NOTE(shess): The following could be done using a single
+  // uber-loop, but it's complicated by needing multiple parallel
+  // iterators.  Didn't seem worthwhile for something that will only
+  // live for a short period and only fires for one in a million
+  // updates.
+
+  // Find elements in |restored| which are not in |prefixes|.
+  std::vector<SBPrefix> difference;
+  std::set_difference(restored.begin(), restored.end(),
+                      prefixes.begin(), prefixes.end(),
+                      std::back_inserter(difference));
+  if (difference.size())
+    UMA_HISTOGRAM_COUNTS_100("SB2.PrefixSetRestoredExcess", difference.size());
+
+  // Find elements in |prefixes| which are not in |restored|.
+  difference.clear();
+  std::set_difference(prefixes.begin(), prefixes.end(),
+                      restored.begin(), restored.end(),
+                      std::back_inserter(difference));
+  if (difference.size())
+    UMA_HISTOGRAM_COUNTS_100("SB2.PrefixSetRestoredShortfall",
+                             difference.size());
   return prefix_set.release();
 }
 
 }  // namespace
 
 // The default SafeBrowsingDatabaseFactory.
 class SafeBrowsingDatabaseFactoryImpl : public SafeBrowsingDatabaseFactory {
  public:
   virtual SafeBrowsingDatabase* CreateSafeBrowsingDatabase(
       bool enable_download_protection,
@@ skipping 905 matching lines @@
   if (std::binary_search(new_csd_whitelist.begin(), new_csd_whitelist.end(),
                          kill_switch)) {
     // The kill switch is whitelisted hence we whitelist all URLs.
     CsdWhitelistAllUrls();
   } else {
     base::AutoLock locked(lookup_lock_);
     csd_whitelist_all_urls_ = false;
     csd_whitelist_.swap(new_csd_whitelist);
   }
 }