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

Side by Side Diff: components/safe_browsing_db/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 unified diff | Download patch
« no previous file with comments | « components/safe_browsing_db/README ('k') | components/safe_browsing_db/prefix_set.cc » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 //
5 // A read-only set implementation for |SBPrefix| items. Prefixes are
6 // sorted and stored as 16-bit deltas from the previous prefix. An
7 // index structure provides quick random access, and also handles
8 // cases where 16 bits cannot encode a delta.
9 //
10 // For example, the sequence {20, 25, 41, 65432, 150000, 160000} would
11 // be stored as:
12 // A pair {20, 0} in |index_|.
13 // 5, 16, 65391 in |deltas_|.
14 // A pair {150000, 3} in |index_|.
15 // 10000 in |deltas_|.
16 // |index_.size()| will be 2, |deltas_.size()| will be 4.
17 //
18 // This structure is intended for storage of sparse uniform sets of
19 // prefixes of a certain size. As of this writing, my safe-browsing
20 // database contains:
21 // 653132 add prefixes
22 // 6446 are duplicates (from different chunks)
23 // 24301 w/in 2^8 of the prior prefix
24 // 622337 w/in 2^16 of the prior prefix
25 // 47 further than 2^16 from the prior prefix
26 // For this input, the memory usage is approximately 2 bytes per
27 // prefix, a bit over 1.2M. The bloom filter used 25 bits per prefix,
28 // a bit over 1.9M on this data.
29 //
30 // Experimenting with random selections of the above data, storage
31 // size drops almost linearly as prefix count drops, until the index
32 // overhead starts to become a problem a bit under 200k prefixes. The
33 // memory footprint gets worse than storing the raw prefix data around
34 // 75k prefixes. Fortunately, the actual memory footprint also falls.
35 // If the prefix count increases the memory footprint should increase
36 // approximately linearly. The worst-case would be 2^16 items all
37 // 2^16 apart, which would need 512k (versus 256k to store the raw
38 // data).
39 //
40 // The on-disk format looks like:
41 // 4 byte magic number
42 // 4 byte version number
43 // 4 byte |index_.size()|
44 // 4 byte |deltas_.size()|
45 // n * 8 byte |&index_[0]..&index_[n]|
46 // m * 2 byte |&deltas_[0]..&deltas_[m]|
47 // 16 byte digest
48
49 #ifndef COMPONENTS_SAFE_BROWSING_DB_PREFIX_SET_H_
50 #define COMPONENTS_SAFE_BROWSING_DB_PREFIX_SET_H_
51
52 #include <utility>
53 #include <vector>
54
55 #include "base/gtest_prod_util.h"
56 #include "base/macros.h"
57 #include "base/memory/scoped_ptr.h"
58 #include "components/safe_browsing_db/safe_browsing_db_util.h"
59
60 namespace base {
61 class FilePath;
62 }
63
64 namespace safe_browsing {
65
66 class PrefixSet {
67 public:
68 ~PrefixSet();
69
70 // |true| if |hash| is in the hashes passed to the set's builder, or if
71 // |hash.prefix| is one of the prefixes passed to the set's builder.
72 bool Exists(const SBFullHash& hash) const;
73
74 // Persist the set on disk.
75 static scoped_ptr<const PrefixSet> LoadFile(
76 const base::FilePath& filter_name);
77 bool WriteFile(const base::FilePath& filter_name) const;
78
79 private:
80 friend class PrefixSetBuilder;
81
82 friend class PrefixSetTest;
83 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, AllBig);
84 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, EdgeCases);
85 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, Empty);
86 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, FullHashBuild);
87 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, IntMinMax);
88 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, OneElement);
89 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, ReadWrite);
90 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, ReadWriteSigned);
91 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, Version3);
92
93 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, BasicStore);
94 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, DeleteChunks);
95 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, DetectsCorruption);
96 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Empty);
97 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, PrefixMinMax);
98 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, SubKnockout);
99 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version7);
100 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version8);
101
102 // Maximum number of consecutive deltas to encode before generating
103 // a new index entry. This helps keep the worst-case performance
104 // for |Exists()| under control.
105 static const size_t kMaxRun = 100;
106
107 // Helpers to make |index_| easier to deal with.
108 typedef std::pair<SBPrefix, uint32> IndexPair;
109 typedef std::vector<IndexPair> IndexVector;
110 static bool PrefixLess(const IndexPair& a, const IndexPair& b);
111
112 // Helper to let |PrefixSetBuilder| add a run of data. |index_prefix| is
113 // added to |index_|, with the other elements added into |deltas_|.
114 void AddRun(SBPrefix index_prefix,
115 const uint16* run_begin, const uint16* run_end);
116
117 // |true| if |prefix| is one of the prefixes passed to the set's builder.
118 // Provided for testing purposes.
119 bool PrefixExists(SBPrefix prefix) const;
120
121 // Regenerate the vector of prefixes passed to the constructor into
122 // |prefixes|. Prefixes will be added in sorted order. Useful for testing.
123 void GetPrefixes(std::vector<SBPrefix>* prefixes) const;
124
125 // Used by |PrefixSetBuilder|.
126 PrefixSet();
127
128 // Helper for |LoadFile()|. Steals vector contents using |swap()|.
129 PrefixSet(IndexVector* index,
130 std::vector<uint16>* deltas,
131 std::vector<SBFullHash>* full_hashes);
132
133 // Top-level index of prefix to offset in |deltas_|. Each pair
134 // indicates a base prefix and where the deltas from that prefix
135 // begin in |deltas_|. The deltas for a pair end at the next pair's
136 // index into |deltas_|.
137 IndexVector index_;
138
139 // Deltas which are added to the prefix in |index_| to generate
140 // prefixes. Deltas are only valid between consecutive items from
141 // |index_|, or the end of |deltas_| for the last |index_| pair.
142 std::vector<uint16> deltas_;
143
144 // Full hashes ordered by SBFullHashLess.
145 std::vector<SBFullHash> full_hashes_;
146
147 DISALLOW_COPY_AND_ASSIGN(PrefixSet);
148 };
149
150 // Helper to incrementally build a PrefixSet from a stream of sorted prefixes.
151 class PrefixSetBuilder {
152 public:
153 PrefixSetBuilder();
154 ~PrefixSetBuilder();
155
156 // Helper for unit tests and format conversion.
157 explicit PrefixSetBuilder(const std::vector<SBPrefix>& prefixes);
158
159 // Add a prefix to the set. Prefixes must arrive in ascending order.
160 // Duplicate prefixes are dropped.
161 void AddPrefix(SBPrefix prefix);
162
163 // Flush any buffered prefixes, and return the final PrefixSet instance.
164 // |hashes| are sorted and stored in |full_hashes_|. Any call other than the
165 // destructor is illegal after this call.
166 scoped_ptr<const PrefixSet> GetPrefixSet(
167 const std::vector<SBFullHash>& hashes);
168
169 // Helper for clients which only track prefixes. Calls GetPrefixSet() with
170 // empty hash vector.
171 scoped_ptr<const PrefixSet> GetPrefixSetNoHashes();
172
173 private:
174 // Encode a run of deltas for |AddRun()|. The run is broken by a too-large
175 // delta, or kMaxRun, whichever comes first.
176 void EmitRun();
177
178 // Buffers prefixes until enough are avaliable to emit a run.
179 std::vector<SBPrefix> buffer_;
180
181 // The PrefixSet being built.
182 scoped_ptr<PrefixSet> prefix_set_;
183 };
184
185 } // namespace safe_browsing
186
187 #endif // COMPONENTS_SAFE_BROWSING_DB_PREFIX_SET_H_
OLDNEW
« no previous file with comments | « components/safe_browsing_db/README ('k') | components/safe_browsing_db/prefix_set.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698