Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(4874)

Unified Diff: chrome/browser/safe_browsing/prefix_set.h

Issue 1420143002: Revert of Move prefix_set and parts of s_b_util into a new component safe_browsing_db. (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: Created 5 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « chrome/browser/DEPS ('k') | chrome/browser/safe_browsing/prefix_set.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: chrome/browser/safe_browsing/prefix_set.h
diff --git a/chrome/browser/safe_browsing/prefix_set.h b/chrome/browser/safe_browsing/prefix_set.h
new file mode 100644
index 0000000000000000000000000000000000000000..6efd21973ffbd5928a729755feef40059bc8e603
--- /dev/null
+++ b/chrome/browser/safe_browsing/prefix_set.h
@@ -0,0 +1,186 @@
+// Copyright (c) 2012 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.
+//
+// A read-only set implementation for |SBPrefix| items. Prefixes are
+// sorted and stored as 16-bit deltas from the previous prefix. An
+// index structure provides quick random access, and also handles
+// cases where 16 bits cannot encode a delta.
+//
+// For example, the sequence {20, 25, 41, 65432, 150000, 160000} would
+// be stored as:
+// A pair {20, 0} in |index_|.
+// 5, 16, 65391 in |deltas_|.
+// A pair {150000, 3} in |index_|.
+// 10000 in |deltas_|.
+// |index_.size()| will be 2, |deltas_.size()| will be 4.
+//
+// This structure is intended for storage of sparse uniform sets of
+// prefixes of a certain size. As of this writing, my safe-browsing
+// database contains:
+// 653132 add prefixes
+// 6446 are duplicates (from different chunks)
+// 24301 w/in 2^8 of the prior prefix
+// 622337 w/in 2^16 of the prior prefix
+// 47 further than 2^16 from the prior prefix
+// For this input, the memory usage is approximately 2 bytes per
+// prefix, a bit over 1.2M. The bloom filter used 25 bits per prefix,
+// a bit over 1.9M on this data.
+//
+// Experimenting with random selections of the above data, storage
+// size drops almost linearly as prefix count drops, until the index
+// overhead starts to become a problem a bit under 200k prefixes. The
+// memory footprint gets worse than storing the raw prefix data around
+// 75k prefixes. Fortunately, the actual memory footprint also falls.
+// If the prefix count increases the memory footprint should increase
+// approximately linearly. The worst-case would be 2^16 items all
+// 2^16 apart, which would need 512k (versus 256k to store the raw
+// data).
+//
+// The on-disk format looks like:
+// 4 byte magic number
+// 4 byte version number
+// 4 byte |index_.size()|
+// 4 byte |deltas_.size()|
+// n * 8 byte |&index_[0]..&index_[n]|
+// m * 2 byte |&deltas_[0]..&deltas_[m]|
+// 16 byte digest
+
+#ifndef CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_
+#define CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_
+
+#include <utility>
+#include <vector>
+
+#include "base/gtest_prod_util.h"
+#include "base/memory/scoped_ptr.h"
+#include "chrome/browser/safe_browsing/safe_browsing_util.h"
+
+namespace base {
+class FilePath;
+}
+
+namespace safe_browsing {
+
+class PrefixSet {
+ public:
+ ~PrefixSet();
+
+ // |true| if |hash| is in the hashes passed to the set's builder, or if
+ // |hash.prefix| is one of the prefixes passed to the set's builder.
+ bool Exists(const SBFullHash& hash) const;
+
+ // Persist the set on disk.
+ static scoped_ptr<const PrefixSet> LoadFile(
+ const base::FilePath& filter_name);
+ bool WriteFile(const base::FilePath& filter_name) const;
+
+ private:
+ friend class PrefixSetBuilder;
+
+ friend class PrefixSetTest;
+ FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, AllBig);
+ FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, EdgeCases);
+ FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, Empty);
+ FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, FullHashBuild);
+ FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, IntMinMax);
+ FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, OneElement);
+ FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, ReadWrite);
+ FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, ReadWriteSigned);
+ FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, Version3);
+
+ FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, BasicStore);
+ FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, DeleteChunks);
+ FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, DetectsCorruption);
+ FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Empty);
+ FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, PrefixMinMax);
+ FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, SubKnockout);
+ FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version7);
+ FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version8);
+
+ // Maximum number of consecutive deltas to encode before generating
+ // a new index entry. This helps keep the worst-case performance
+ // for |Exists()| under control.
+ static const size_t kMaxRun = 100;
+
+ // Helpers to make |index_| easier to deal with.
+ typedef std::pair<SBPrefix, uint32> IndexPair;
+ typedef std::vector<IndexPair> IndexVector;
+ static bool PrefixLess(const IndexPair& a, const IndexPair& b);
+
+ // Helper to let |PrefixSetBuilder| add a run of data. |index_prefix| is
+ // added to |index_|, with the other elements added into |deltas_|.
+ void AddRun(SBPrefix index_prefix,
+ const uint16* run_begin, const uint16* run_end);
+
+ // |true| if |prefix| is one of the prefixes passed to the set's builder.
+ // Provided for testing purposes.
+ bool PrefixExists(SBPrefix prefix) const;
+
+ // Regenerate the vector of prefixes passed to the constructor into
+ // |prefixes|. Prefixes will be added in sorted order. Useful for testing.
+ void GetPrefixes(std::vector<SBPrefix>* prefixes) const;
+
+ // Used by |PrefixSetBuilder|.
+ PrefixSet();
+
+ // Helper for |LoadFile()|. Steals vector contents using |swap()|.
+ PrefixSet(IndexVector* index,
+ std::vector<uint16>* deltas,
+ std::vector<SBFullHash>* full_hashes);
+
+ // Top-level index of prefix to offset in |deltas_|. Each pair
+ // indicates a base prefix and where the deltas from that prefix
+ // begin in |deltas_|. The deltas for a pair end at the next pair's
+ // index into |deltas_|.
+ IndexVector index_;
+
+ // Deltas which are added to the prefix in |index_| to generate
+ // prefixes. Deltas are only valid between consecutive items from
+ // |index_|, or the end of |deltas_| for the last |index_| pair.
+ std::vector<uint16> deltas_;
+
+ // Full hashes ordered by SBFullHashLess.
+ std::vector<SBFullHash> full_hashes_;
+
+ DISALLOW_COPY_AND_ASSIGN(PrefixSet);
+};
+
+// Helper to incrementally build a PrefixSet from a stream of sorted prefixes.
+class PrefixSetBuilder {
+ public:
+ PrefixSetBuilder();
+ ~PrefixSetBuilder();
+
+ // Helper for unit tests and format conversion.
+ explicit PrefixSetBuilder(const std::vector<SBPrefix>& prefixes);
+
+ // Add a prefix to the set. Prefixes must arrive in ascending order.
+ // Duplicate prefixes are dropped.
+ void AddPrefix(SBPrefix prefix);
+
+ // Flush any buffered prefixes, and return the final PrefixSet instance.
+ // |hashes| are sorted and stored in |full_hashes_|. Any call other than the
+ // destructor is illegal after this call.
+ scoped_ptr<const PrefixSet> GetPrefixSet(
+ const std::vector<SBFullHash>& hashes);
+
+ // Helper for clients which only track prefixes. Calls GetPrefixSet() with
+ // empty hash vector.
+ scoped_ptr<const PrefixSet> GetPrefixSetNoHashes();
+
+ private:
+ // Encode a run of deltas for |AddRun()|. The run is broken by a too-large
+ // delta, or kMaxRun, whichever comes first.
+ void EmitRun();
+
+ // Buffers prefixes until enough are avaliable to emit a run.
+ std::vector<SBPrefix> buffer_;
+
+ // The PrefixSet being built.
+ scoped_ptr<PrefixSet> prefix_set_;
+};
+
+} // namespace safe_browsing
+
+#endif // CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_
« no previous file with comments | « chrome/browser/DEPS ('k') | chrome/browser/safe_browsing/prefix_set.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698