Remove safe-browsing code to fix up injected prefixes.

An older implementation of the safe-browsing database code injected
prefixes when receiving full hashes, due to an incorrect reading of how
full-hash matches should happen.  Current code checks the full hashes
and prefixes independently, so the duplicate prefixes are no longer
generated.  This code removed duplicate prefixes found in existing
databases.  99.99% of runs over the past two weeks have not removed any
such duplicate prefixes.

In the current code hitting a full hash has the same end result as
hitting a prefix, so the primary downside of removing this code is
slight excess storage.  Insofar as full hashes are deleted by sub, there
may be stale prefixes left behind.  The stale prefixes will be deleted
when the chunk in question is deleted.  The result may be a small number
of unexpected gethash requests which will return misses (and thus not
affect the browsing experience other than adding a little latency).

BUG=361248

Review URL: https://codereview.chromium.org/507653003

Cr-Commit-Position: refs/heads/master@{#292019}

5 files changed, 5 insertions, 191 deletions

diff --git a/chrome/browser/safe_browsing/prefix_set.h b/chrome/browser/safe_browsing/prefix_set.h
index 7fbf9b4..c093726 100644
--- a/chrome/browser/safe_browsing/prefix_set.h
+++ b/chrome/browser/safe_browsing/prefix_set.h
@@ -92,7 +92,6 @@ class PrefixSet {
   FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, DeleteChunks);
   FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, DetectsCorruption);
   FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Empty);
-  FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, KnockoutPrefixVolunteers);
   FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, PrefixMinMax);
   FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, SubKnockout);
   FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version7);
diff --git a/chrome/browser/safe_browsing/safe_browsing_store.cc b/chrome/browser/safe_browsing/safe_browsing_store.cc
index b0f6a2a..e4c15e7 100644
--- a/chrome/browser/safe_browsing/safe_browsing_store.cc
+++ b/chrome/browser/safe_browsing/safe_browsing_store.cc
@@ -7,7 +7,6 @@
 #include <algorithm>
 
 #include "base/logging.h"
-#include "base/metrics/histogram.h"
 
 namespace {
 
@@ -89,48 +88,6 @@ void RemoveDeleted(ItemsT* items, const base::hash_set<int32>& del_set) {
   items->erase(end_iter, items->end());
 }
 
-// Remove prefixes which are in the same chunk as their fullhash.  This was a
-// mistake in earlier implementations.
-template <typename HashesT, typename PrefixesT>
-size_t KnockoutPrefixVolunteers(const HashesT& full_hashes,
-                                PrefixesT* prefixes) {
-  typename PrefixesT::iterator prefixes_process = prefixes->begin();
-  typename PrefixesT::iterator prefixes_out = prefixes->begin();
-  typename HashesT::const_iterator hashes_process = full_hashes.begin();
-
-  size_t skipped_count = 0;
-
-  while (hashes_process != full_hashes.end()) {
-    // Scan prefixes forward until an item is not less than the current hash.
-    while (prefixes_process != prefixes->end() &&
-           SBAddPrefixLess(*prefixes_process, *hashes_process)) {
-      if (prefixes_process != prefixes_out) {
-        *prefixes_out = *prefixes_process;
-      }
-      prefixes_out++;
-      prefixes_process++;
-    }
-
-    // If the current hash is also not less than the prefix, that implies they
-    // are equal.  Skip the prefix.
-    if (prefixes_process != prefixes->end() &&
-        !SBAddPrefixLess(*hashes_process, *prefixes_process)) {
-      skipped_count++;
-      prefixes_process++;
-    }
-
-    hashes_process++;
-  }
-
-  // If any prefixes were skipped, copy over the tail and erase the excess.
-  if (prefixes_process != prefixes_out) {
-    prefixes_out = std::copy(prefixes_process, prefixes->end(), prefixes_out);
-    prefixes->erase(prefixes_out, prefixes->end());
-  }
-
-  return skipped_count;
-}
-
 }  // namespace
 
 void SBProcessSubs(SBAddPrefixes* add_prefixes,
@@ -154,17 +111,6 @@ void SBProcessSubs(SBAddPrefixes* add_prefixes,
   DCHECK(sorted(sub_full_hashes->begin(), sub_full_hashes->end(),
                 SBAddPrefixHashLess<SBSubFullHash,SBSubFullHash>));
 
-  // Earlier database code added prefixes when it saw fullhashes.  The protocol
-  // should never send a chunk of mixed prefixes and fullhashes, the following
-  // removes any such cases which are seen.
-  // TODO(shess): Remove this code once most databases have been processed.
-  // Chunk churn should clean up anyone left over.  This only takes a few ms to
-  // run through my current database, so it doesn't seem worthwhile to do much
-  // more than that.
-  size_t skipped = KnockoutPrefixVolunteers(*add_full_hashes, add_prefixes);
-  skipped += KnockoutPrefixVolunteers(*sub_full_hashes, sub_prefixes);
-  UMA_HISTOGRAM_COUNTS("SB2.VolunteerPrefixesRemoved", skipped);
-
   // Factor out the prefix subs.
   KnockoutSubs(sub_prefixes, add_prefixes,
                SBAddPrefixLess<SBAddPrefix,SBSubPrefix>,
diff --git a/chrome/browser/safe_browsing/safe_browsing_store_file_unittest.cc b/chrome/browser/safe_browsing/safe_browsing_store_file_unittest.cc
index 2766e55..310f634 100644
--- a/chrome/browser/safe_browsing/safe_browsing_store_file_unittest.cc
+++ b/chrome/browser/safe_browsing/safe_browsing_store_file_unittest.cc
@@ -818,6 +818,8 @@ TEST_F(SafeBrowsingStoreFileTest, Version8) {
   EXPECT_TRUE(store_->CheckSubChunk(kSubChunk1));
 
   // Sub chunk kAddChunk1 hash kHash2.
+  // NOTE(shess): Having full hashes and prefixes in the same chunk is no longer
+  // supported, though it was when this code was written.
   store_->SetSubChunk(kSubChunk2);
   EXPECT_TRUE(store_->CheckSubChunk(kSubChunk1));
   EXPECT_TRUE(store_->WriteSubPrefix(kSubChunk1, kAddChunk1, kHash2.prefix));
@@ -839,77 +841,4 @@ TEST_F(SafeBrowsingStoreFileTest, Version8) {
 }
 #endif
 
-// Test that when the v8 golden file is updated, the add prefix injected from
-// the full hash is removed.  All platforms generating v8 files are
-// little-endian, so there is no point to testing this transition if/when a
-// big-endian port is added.
-#if defined(ARCH_CPU_LITTLE_ENDIAN)
-TEST_F(SafeBrowsingStoreFileTest, KnockoutPrefixVolunteers) {
-  store_.reset();
-
-  // Copy the golden file into temporary storage.  The golden file contains:
-  // - Add chunk kAddChunk1 containing kHash1.prefix and kHash2.
-  // - Sub chunk kSubChunk1 containing kHash3.
-  const char kBasename[] = "FileStoreVersion8";
-  base::FilePath golden_path;
-  ASSERT_TRUE(PathService::Get(chrome::DIR_TEST_DATA, &golden_path));
-  golden_path = golden_path.AppendASCII("SafeBrowsing");
-  golden_path = golden_path.AppendASCII(kBasename);
-  ASSERT_TRUE(base::CopyFile(golden_path, filename_));
-
-  // Reset the store to make sure it re-reads the file.
-  store_.reset(new SafeBrowsingStoreFile());
-  store_->Init(filename_,
-               base::Bind(&SafeBrowsingStoreFileTest::OnCorruptionDetected,
-                          base::Unretained(this)));
-
-  // Check that the expected prefixes and hashes are in place.
-  {
-    SBAddPrefixes add_prefixes;
-    EXPECT_TRUE(store_->GetAddPrefixes(&add_prefixes));
-    ASSERT_EQ(2U, add_prefixes.size());
-    EXPECT_EQ(kAddChunk1, add_prefixes[0].chunk_id);
-    EXPECT_EQ(kHash1.prefix, add_prefixes[0].prefix);
-    EXPECT_EQ(kAddChunk1, add_prefixes[1].chunk_id);
-    EXPECT_EQ(kHash2.prefix, add_prefixes[1].prefix);
-
-    std::vector<SBAddFullHash> add_hashes;
-    EXPECT_TRUE(store_->GetAddFullHashes(&add_hashes));
-    ASSERT_EQ(1U, add_hashes.size());
-    EXPECT_EQ(kAddChunk1, add_hashes[0].chunk_id);
-    EXPECT_TRUE(SBFullHashEqual(kHash2, add_hashes[0].full_hash));
-  }
-
-  // Update the store.
-  {
-    EXPECT_TRUE(store_->BeginUpdate());
-
-    safe_browsing::PrefixSetBuilder builder;
-    std::vector<SBAddFullHash> add_full_hashes_result;
-    ASSERT_TRUE(store_->FinishUpdate(&builder, &add_full_hashes_result));
-  }
-
-  // Reset the store to make sure it re-reads the file.
-  store_.reset(new SafeBrowsingStoreFile());
-  store_->Init(filename_,
-               base::Bind(&SafeBrowsingStoreFileTest::OnCorruptionDetected,
-                          base::Unretained(this)));
-
-  // |kHash2.prefix| should have dropped.
-  {
-    SBAddPrefixes add_prefixes;
-    EXPECT_TRUE(store_->GetAddPrefixes(&add_prefixes));
-    ASSERT_EQ(1U, add_prefixes.size());
-    EXPECT_EQ(kAddChunk1, add_prefixes[0].chunk_id);
-    EXPECT_EQ(kHash1.prefix, add_prefixes[0].prefix);
-
-    std::vector<SBAddFullHash> add_hashes;
-    EXPECT_TRUE(store_->GetAddFullHashes(&add_hashes));
-    ASSERT_EQ(1U, add_hashes.size());
-    EXPECT_EQ(kAddChunk1, add_hashes[0].chunk_id);
-    EXPECT_TRUE(SBFullHashEqual(kHash2, add_hashes[0].full_hash));
-  }
-}
-#endif
-
 }  // namespace safe_browsing
diff --git a/chrome/browser/safe_browsing/safe_browsing_store_unittest.cc b/chrome/browser/safe_browsing/safe_browsing_store_unittest.cc
index 2c336ab..0475105 100644
--- a/chrome/browser/safe_browsing/safe_browsing_store_unittest.cc
+++ b/chrome/browser/safe_browsing/safe_browsing_store_unittest.cc
@@ -300,67 +300,4 @@ TEST(SafeBrowsingStoreTest, Y2K38) {
     << " (int32)time_t is running out.";
 }
 
-// Test that prefixes which were injected from full hashes are being removed.
-// This was a mistake in earlier versions of the code.
-TEST(SafeBrowsingStoreTest, KnockoutPrefixVolunteers) {
-  // Construct some full hashes which share prefix with another.
-  const SBFullHash kHash1mod1 = ModifyHashAfterPrefix(kHash1, 1);
-  const SBFullHash kHash2mod1 = ModifyHashAfterPrefix(kHash2, 1);
-
-  SBAddPrefixes add_prefixes;
-  std::vector<SBAddFullHash> add_hashes;
-  SBSubPrefixes sub_prefixes;
-  std::vector<SBSubFullHash> sub_hashes;
-
-  // Full hashes for an add chunk will have had the prefix injected.
-  add_hashes.push_back(SBAddFullHash(kAddChunk1, kHash1));
-  add_hashes.push_back(SBAddFullHash(kAddChunk1, kHash1mod1));
-  add_prefixes.push_back(SBAddPrefix(kAddChunk1, kHash1.prefix));
-
-  // Other full hashes or prefixes are not affected.
-  add_hashes.push_back(SBAddFullHash(kAddChunk1, kHash3));
-  add_prefixes.push_back(SBAddPrefix(kAddChunk2, kHash4.prefix));
-
-  // Full hashes for a sub chunk will have had the prefix injected.
-  sub_hashes.push_back(SBSubFullHash(kSubChunk1, kAddChunk1, kHash2));
-  sub_hashes.push_back(SBSubFullHash(kSubChunk1, kAddChunk1, kHash2mod1));
-  sub_prefixes.push_back(SBSubPrefix(kSubChunk1, kAddChunk1, kHash2.prefix));
-
-  // Other full hashes or prefixes are not affected.
-  sub_hashes.push_back(SBSubFullHash(kSubChunk1, kAddChunk1, kHash5));
-  sub_prefixes.push_back(SBSubPrefix(kSubChunk2, kAddChunk2, kHash6.prefix));
-
-  const base::hash_set<int32> no_deletions;
-  ProcessHelper(&add_prefixes, &sub_prefixes, &add_hashes, &sub_hashes,
-                no_deletions, no_deletions);
-
-  ASSERT_EQ(1U, add_prefixes.size());
-  EXPECT_EQ(kAddChunk2, add_prefixes[0].chunk_id);
-  EXPECT_EQ(kHash4.prefix, add_prefixes[0].prefix);
-
-  ASSERT_EQ(3U, add_hashes.size());
-  EXPECT_EQ(kAddChunk1, add_hashes[0].chunk_id);
-  EXPECT_TRUE(SBFullHashEqual(kHash1mod1, add_hashes[0].full_hash));
-  EXPECT_EQ(kAddChunk1, add_hashes[1].chunk_id);
-  EXPECT_TRUE(SBFullHashEqual(kHash1, add_hashes[1].full_hash));
-  EXPECT_EQ(kAddChunk1, add_hashes[2].chunk_id);
-  EXPECT_TRUE(SBFullHashEqual(kHash3, add_hashes[2].full_hash));
-
-  ASSERT_EQ(1U, sub_prefixes.size());
-  EXPECT_EQ(kSubChunk2, sub_prefixes[0].chunk_id);
-  EXPECT_EQ(kAddChunk2, sub_prefixes[0].add_chunk_id);
-  EXPECT_EQ(kHash6.prefix, sub_prefixes[0].add_prefix);
-
-  ASSERT_EQ(3U, sub_hashes.size());
-  EXPECT_EQ(kSubChunk1, sub_hashes[0].chunk_id);
-  EXPECT_EQ(kAddChunk1, sub_hashes[0].add_chunk_id);
-  EXPECT_TRUE(SBFullHashEqual(kHash5, sub_hashes[0].full_hash));
-  EXPECT_EQ(kSubChunk1, sub_hashes[1].chunk_id);
-  EXPECT_EQ(kAddChunk1, sub_hashes[1].add_chunk_id);
-  EXPECT_TRUE(SBFullHashEqual(kHash2mod1, sub_hashes[1].full_hash));
-  EXPECT_EQ(kSubChunk1, sub_hashes[2].chunk_id);
-  EXPECT_EQ(kAddChunk1, sub_hashes[2].add_chunk_id);
-  EXPECT_TRUE(SBFullHashEqual(kHash2, sub_hashes[2].full_hash));
-}
-
 }  // namespace
diff --git a/tools/metrics/histograms/histograms.xml b/tools/metrics/histograms/histograms.xml
index 335ca07..84086149 100644
--- a/tools/metrics/histograms/histograms.xml
+++ b/tools/metrics/histograms/histograms.xml
@@ -27351,6 +27351,9 @@ Therefore, the affected-histogram name has to have at least one dot in it.
 
 <histogram name="SB2.VolunteerPrefixesRemoved">
   <owner>shess@chromium.org</owner>
+  <obsolete>
+    The operation this is tracking has been deleted as of 09/2014.
+  </obsolete>
   <summary>
     Older versions of the safe-browsing code incorrectly added additional
     SBPrefix items when receiving full hashes.  This caused errors when