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 CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_ |
| 50 #define CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_ |
| 51 |
| 52 #include <utility> |
| 53 #include <vector> |
| 54 |
| 55 #include "base/gtest_prod_util.h" |
| 56 #include "base/memory/scoped_ptr.h" |
| 57 #include "chrome/browser/safe_browsing/safe_browsing_util.h" |
| 58 |
| 59 namespace base { |
| 60 class FilePath; |
| 61 } |
| 62 |
| 63 namespace safe_browsing { |
| 64 |
| 65 class PrefixSet { |
| 66 public: |
| 67 ~PrefixSet(); |
| 68 |
| 69 // |true| if |hash| is in the hashes passed to the set's builder, or if |
| 70 // |hash.prefix| is one of the prefixes passed to the set's builder. |
| 71 bool Exists(const SBFullHash& hash) const; |
| 72 |
| 73 // Persist the set on disk. |
| 74 static scoped_ptr<const PrefixSet> LoadFile( |
| 75 const base::FilePath& filter_name); |
| 76 bool WriteFile(const base::FilePath& filter_name) const; |
| 77 |
| 78 private: |
| 79 friend class PrefixSetBuilder; |
| 80 |
| 81 friend class PrefixSetTest; |
| 82 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, AllBig); |
| 83 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, EdgeCases); |
| 84 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, Empty); |
| 85 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, FullHashBuild); |
| 86 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, IntMinMax); |
| 87 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, OneElement); |
| 88 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, ReadWrite); |
| 89 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, ReadWriteSigned); |
| 90 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, Version3); |
| 91 |
| 92 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, BasicStore); |
| 93 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, DeleteChunks); |
| 94 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, DetectsCorruption); |
| 95 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Empty); |
| 96 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, PrefixMinMax); |
| 97 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, SubKnockout); |
| 98 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version7); |
| 99 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version8); |
| 100 |
| 101 // Maximum number of consecutive deltas to encode before generating |
| 102 // a new index entry. This helps keep the worst-case performance |
| 103 // for |Exists()| under control. |
| 104 static const size_t kMaxRun = 100; |
| 105 |
| 106 // Helpers to make |index_| easier to deal with. |
| 107 typedef std::pair<SBPrefix, uint32> IndexPair; |
| 108 typedef std::vector<IndexPair> IndexVector; |
| 109 static bool PrefixLess(const IndexPair& a, const IndexPair& b); |
| 110 |
| 111 // Helper to let |PrefixSetBuilder| add a run of data. |index_prefix| is |
| 112 // added to |index_|, with the other elements added into |deltas_|. |
| 113 void AddRun(SBPrefix index_prefix, |
| 114 const uint16* run_begin, const uint16* run_end); |
| 115 |
| 116 // |true| if |prefix| is one of the prefixes passed to the set's builder. |
| 117 // Provided for testing purposes. |
| 118 bool PrefixExists(SBPrefix prefix) const; |
| 119 |
| 120 // Regenerate the vector of prefixes passed to the constructor into |
| 121 // |prefixes|. Prefixes will be added in sorted order. Useful for testing. |
| 122 void GetPrefixes(std::vector<SBPrefix>* prefixes) const; |
| 123 |
| 124 // Used by |PrefixSetBuilder|. |
| 125 PrefixSet(); |
| 126 |
| 127 // Helper for |LoadFile()|. Steals vector contents using |swap()|. |
| 128 PrefixSet(IndexVector* index, |
| 129 std::vector<uint16>* deltas, |
| 130 std::vector<SBFullHash>* full_hashes); |
| 131 |
| 132 // Top-level index of prefix to offset in |deltas_|. Each pair |
| 133 // indicates a base prefix and where the deltas from that prefix |
| 134 // begin in |deltas_|. The deltas for a pair end at the next pair's |
| 135 // index into |deltas_|. |
| 136 IndexVector index_; |
| 137 |
| 138 // Deltas which are added to the prefix in |index_| to generate |
| 139 // prefixes. Deltas are only valid between consecutive items from |
| 140 // |index_|, or the end of |deltas_| for the last |index_| pair. |
| 141 std::vector<uint16> deltas_; |
| 142 |
| 143 // Full hashes ordered by SBFullHashLess. |
| 144 std::vector<SBFullHash> full_hashes_; |
| 145 |
| 146 DISALLOW_COPY_AND_ASSIGN(PrefixSet); |
| 147 }; |
| 148 |
| 149 // Helper to incrementally build a PrefixSet from a stream of sorted prefixes. |
| 150 class PrefixSetBuilder { |
| 151 public: |
| 152 PrefixSetBuilder(); |
| 153 ~PrefixSetBuilder(); |
| 154 |
| 155 // Helper for unit tests and format conversion. |
| 156 explicit PrefixSetBuilder(const std::vector<SBPrefix>& prefixes); |
| 157 |
| 158 // Add a prefix to the set. Prefixes must arrive in ascending order. |
| 159 // Duplicate prefixes are dropped. |
| 160 void AddPrefix(SBPrefix prefix); |
| 161 |
| 162 // Flush any buffered prefixes, and return the final PrefixSet instance. |
| 163 // |hashes| are sorted and stored in |full_hashes_|. Any call other than the |
| 164 // destructor is illegal after this call. |
| 165 scoped_ptr<const PrefixSet> GetPrefixSet( |
| 166 const std::vector<SBFullHash>& hashes); |
| 167 |
| 168 // Helper for clients which only track prefixes. Calls GetPrefixSet() with |
| 169 // empty hash vector. |
| 170 scoped_ptr<const PrefixSet> GetPrefixSetNoHashes(); |
| 171 |
| 172 private: |
| 173 // Encode a run of deltas for |AddRun()|. The run is broken by a too-large |
| 174 // delta, or kMaxRun, whichever comes first. |
| 175 void EmitRun(); |
| 176 |
| 177 // Buffers prefixes until enough are avaliable to emit a run. |
| 178 std::vector<SBPrefix> buffer_; |
| 179 |
| 180 // The PrefixSet being built. |
| 181 scoped_ptr<PrefixSet> prefix_set_; |
| 182 }; |
| 183 |
| 184 } // namespace safe_browsing |
| 185 |
| 186 #endif // CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_ |
OLD | NEW |