OLD | NEW |
| (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_ | |
OLD | NEW |