Safe-browsing PrefixSet cleanups.

Make sure SBPrefix is a fixed size.
PrefixSet tests for single-element set, set with large deltas, and
  int32 space edge cases.
PrefixSet::GetPrefixes() can be const.
Consolidate the SafeBrowsingDatabase GetPrefixes() checking code.
Check whether deltas fit by directly checking whether the delta fit.
Add a histogram for checking if SBPrefix really was crazy.

BUG=71832
TEST=none

Review URL: http://codereview.chromium.org/6711021

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@78667 0039d316-1c4b-4281-b951-d872f2087c98

5 files changed, 123 insertions, 36 deletions

diff --git a/chrome/browser/safe_browsing/prefix_set.cc b/chrome/browser/safe_browsing/prefix_set.cc
index 72ceb6f..e72eb57 100644
--- a/chrome/browser/safe_browsing/prefix_set.cc
+++ b/chrome/browser/safe_browsing/prefix_set.cc
@@ -54,17 +54,18 @@ PrefixSet::PrefixSet(const std::vector<SBPrefix>& sorted_prefixes) {
       // Calculate the delta.  |unsigned| is mandatory, because the
       // sorted_prefixes could be more than INT_MAX apart.
       DCHECK_GT(sorted_prefixes[i], prev_prefix);
-      unsigned delta = sorted_prefixes[i] - prev_prefix;
+      const unsigned delta = sorted_prefixes[i] - prev_prefix;
+      const uint16 delta16 = static_cast<uint16>(delta);
 
-      // New index ref if the delta is too wide, or if too many
-      // consecutive deltas have been encoded.  Note that
-      // |kMaxDelta| cannot itself be encoded.
-      if (delta >= kMaxDelta || run_length >= kMaxRun) {
+      // New index ref if the delta doesn't fit, or if too many
+      // consecutive deltas have been encoded.
+      if (delta != static_cast<unsigned>(delta16) || run_length >= kMaxRun) {
         index_.push_back(std::make_pair(sorted_prefixes[i], deltas_.size()));
         run_length = 0;
       } else {
         // Continue the run of deltas.
-        deltas_.push_back(static_cast<uint16>(delta));
+        deltas_.push_back(delta16);
+        DCHECK_EQ(static_cast<unsigned>(deltas_.back()), delta);
         ++run_length;
       }
 
@@ -125,7 +126,7 @@ bool PrefixSet::Exists(SBPrefix prefix) const {
   return current == prefix;
 }
 
-void PrefixSet::GetPrefixes(std::vector<SBPrefix>* prefixes) {
+void PrefixSet::GetPrefixes(std::vector<SBPrefix>* prefixes) const {
   for (size_t ii = 0; ii < index_.size(); ++ii) {
     // The deltas for this |index_| entry run to the next index entry,
     // or the end of the deltas.
diff --git a/chrome/browser/safe_browsing/prefix_set.h b/chrome/browser/safe_browsing/prefix_set.h
index 246beea..025b163 100644
--- a/chrome/browser/safe_browsing/prefix_set.h
+++ b/chrome/browser/safe_browsing/prefix_set.h
@@ -72,12 +72,9 @@ class PrefixSet {
 
   // Regenerate the vector of prefixes passed to the constructor into
   // |prefixes|.  Prefixes will be added in sorted order.
-  void GetPrefixes(std::vector<SBPrefix>* prefixes);
+  void GetPrefixes(std::vector<SBPrefix>* prefixes) const;
 
  private:
-  // Maximum delta that can be encoded in a 16-bit unsigned.
-  static const unsigned kMaxDelta = 256 * 256;
-
   // Maximum number of consecutive deltas to encode before generating
   // a new index entry.  This helps keep the worst-case performance
   // for |Exists()| under control.
diff --git a/chrome/browser/safe_browsing/prefix_set_unittest.cc b/chrome/browser/safe_browsing/prefix_set_unittest.cc
index 1547117..2dbdd4d 100644
--- a/chrome/browser/safe_browsing/prefix_set_unittest.cc
+++ b/chrome/browser/safe_browsing/prefix_set_unittest.cc
@@ -164,6 +164,75 @@ TEST_F(PrefixSetTest, Empty) {
   }
 }
 
+// Single-element set should work fine.
+TEST_F(PrefixSetTest, OneElement) {
+  const std::vector<SBPrefix> prefixes(100, 0);
+  safe_browsing::PrefixSet prefix_set(prefixes);
+  EXPECT_FALSE(prefix_set.Exists(-1));
+  EXPECT_TRUE(prefix_set.Exists(prefixes[0]));
+  EXPECT_FALSE(prefix_set.Exists(1));
+
+  // Check that |GetPrefixes()| returns the same set of prefixes as
+  // was passed in.
+  std::vector<SBPrefix> prefixes_copy;
+  prefix_set.GetPrefixes(&prefixes_copy);
+  EXPECT_EQ(1U, prefixes_copy.size());
+  EXPECT_EQ(prefixes[0], prefixes_copy[0]);
+}
+
+// Edges of the 32-bit integer range.
+TEST_F(PrefixSetTest, IntMinMax) {
+  std::vector<SBPrefix> prefixes;
+
+  // Using bit patterns rather than portable constants because this
+  // really is testing how the entire 32-bit integer range is handled.
+  prefixes.push_back(0x00000000);
+  prefixes.push_back(0x0000FFFF);
+  prefixes.push_back(0x7FFF0000);
+  prefixes.push_back(0x7FFFFFFF);
+  prefixes.push_back(0x80000000);
+  prefixes.push_back(0x8000FFFF);
+  prefixes.push_back(0xFFFF0000);
+  prefixes.push_back(0xFFFFFFFF);
+
+  std::sort(prefixes.begin(), prefixes.end());
+  safe_browsing::PrefixSet prefix_set(prefixes);
+
+  // Check that |GetPrefixes()| returns the same set of prefixes as
+  // was passed in.
+  std::vector<SBPrefix> prefixes_copy;
+  prefix_set.GetPrefixes(&prefixes_copy);
+  ASSERT_EQ(prefixes_copy.size(), prefixes.size());
+  EXPECT_TRUE(std::equal(prefixes.begin(), prefixes.end(),
+                         prefixes_copy.begin()));
+}
+
+// A range with only large deltas.
+TEST_F(PrefixSetTest, AllBig) {
+  std::vector<SBPrefix> prefixes;
+
+  const SBPrefix kVeryPositive = 1000 * 1000 * 1000;
+  const SBPrefix kVeryNegative = -kVeryPositive;
+  const unsigned kDelta = 10 * 1000 * 1000;
+
+  for (SBPrefix prefix = kVeryNegative;
+       prefix < kVeryPositive; prefix += kDelta) {
+    prefixes.push_back(prefix);
+  }
+
+  std::sort(prefixes.begin(), prefixes.end());
+  safe_browsing::PrefixSet prefix_set(prefixes);
+
+  // Check that |GetPrefixes()| returns the same set of prefixes as
+  // was passed in.
+  std::vector<SBPrefix> prefixes_copy;
+  prefix_set.GetPrefixes(&prefixes_copy);
+  prefixes.erase(std::unique(prefixes.begin(), prefixes.end()), prefixes.end());
+  EXPECT_EQ(prefixes_copy.size(), prefixes.size());
+  EXPECT_TRUE(std::equal(prefixes.begin(), prefixes.end(),
+                         prefixes_copy.begin()));
+}
+
 // Use artificial inputs to test various edge cases in Exists().
 // Items before the lowest item aren't present.  Items after the
 // largest item aren't present.  Create a sequence of items with
diff --git a/chrome/browser/safe_browsing/safe_browsing_database.cc b/chrome/browser/safe_browsing/safe_browsing_database.cc
index e432ede..9186440 100644
--- a/chrome/browser/safe_browsing/safe_browsing_database.cc
+++ b/chrome/browser/safe_browsing/safe_browsing_database.cc
@@ -1,4 +1,4 @@
-// Copyright (c) 2010 The Chromium Authors. All rights reserved.
+// 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.
 
@@ -214,6 +214,9 @@ enum PrefixSetEvent {
   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,
 
   // Memory space for histograms is determined by the max.  ALWAYS ADD
   // NEW VALUES BEFORE THIS ONE.
@@ -225,6 +228,43 @@ void RecordPrefixSetInfo(PrefixSetEvent event_type) {
                             PREFIX_SET_EVENT_MAX);
 }
 
+// Verify that |GetPrefixes()| returns the same set of prefixes as
+// |prefixes|.  This is necessary so that the
+// PREFIX_SET_EVENT_BLOOM_MISS_PREFIX_HIT_INVALID histogram in
+// ContainsBrowseUrl() can be trustworthy.
+void CheckPrefixSet(const safe_browsing::PrefixSet& prefix_set,
+                    const std::vector<SBPrefix>& prefixes) {
+  std::vector<SBPrefix> restored;
+  prefix_set.GetPrefixes(&restored);
+
+  const std::set<SBPrefix> unique(prefixes.begin(), prefixes.end());
+
+  // Expect them to be equal.
+  if (restored.size() == unique.size() &&
+      std::equal(unique.begin(), unique.end(), restored.begin()))
+    return;
+
+  // Log BROKEN for continuity with previous release, and SIZE to
+  // distinguish which test failed.
+  NOTREACHED();
+  RecordPrefixSetInfo(PREFIX_SET_GETPREFIXES_BROKEN);
+  if (restored.size() != unique.size())
+    RecordPrefixSetInfo(PREFIX_SET_GETPREFIXES_BROKEN_SIZE);
+
+  // Try to distinguish between updates from one broken user and a
+  // distributed problem.
+  static bool logged_broken = false;
+  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);
+}
+
 }  // namespace
 
 // The default SafeBrowsingDatabaseFactory.
@@ -973,16 +1013,7 @@ void SafeBrowsingDatabaseNew::UpdateBrowseStore() {
   scoped_ptr<safe_browsing::PrefixSet>
       prefix_set(new safe_browsing::PrefixSet(prefixes));
 
-  // Verify that |GetPrefixes()| returns the same set of prefixes as
-  // was passed to the constructor.
-  std::vector<SBPrefix> restored;
-  prefix_set->GetPrefixes(&restored);
-  prefixes.erase(std::unique(prefixes.begin(), prefixes.end()), prefixes.end());
-  if (restored.size() != prefixes.size() ||
-      !std::equal(prefixes.begin(), prefixes.end(), restored.begin())) {
-    NOTREACHED();
-    RecordPrefixSetInfo(PREFIX_SET_GETPREFIXES_BROKEN);
-  }
+  CheckPrefixSet(*(prefix_set.get()), prefixes);
 
   // This needs to be in sorted order by prefix for efficient access.
   std::sort(add_full_hashes.begin(), add_full_hashes.end(),
@@ -1096,18 +1127,7 @@ void SafeBrowsingDatabaseNew::LoadBloomFilter() {
   }
   std::sort(prefixes.begin(), prefixes.end());
   prefix_set_.reset(new safe_browsing::PrefixSet(prefixes));
-
-  // Double-check the prefixes so that the
-  // PREFIX_SET_EVENT_BLOOM_MISS_PREFIX_HIT_INVALID histogram in
-  // ContainsBrowseUrl() can be trustworthy.
-  std::vector<SBPrefix> restored;
-  prefix_set_->GetPrefixes(&restored);
-  std::set<SBPrefix> unique(prefixes.begin(), prefixes.end());
-  if (restored.size() != unique.size() ||
-      !std::equal(unique.begin(), unique.end(), restored.begin())) {
-    NOTREACHED();
-    RecordPrefixSetInfo(PREFIX_SET_GETPREFIXES_BROKEN);
-  }
+  CheckPrefixSet(*(prefix_set_.get()), prefixes);
 }
 
 bool SafeBrowsingDatabaseNew::Delete() {
diff --git a/chrome/browser/safe_browsing/safe_browsing_util.h b/chrome/browser/safe_browsing/safe_browsing_util.h
index 45dd00b..d2e9204 100644
--- a/chrome/browser/safe_browsing/safe_browsing_util.h
+++ b/chrome/browser/safe_browsing/safe_browsing_util.h
@@ -1,4 +1,4 @@
-// Copyright (c) 2010 The Chromium Authors. All rights reserved.
+// 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.
 //
@@ -21,7 +21,7 @@ class GURL;
 class SBEntry;
 
 // A truncated hash's type.
-typedef int SBPrefix;
+typedef int32 SBPrefix;
 
 // Container for holding a chunk URL and the MAC of the contents of the URL.
 struct ChunkUrl {