1 // Copyright (c) 2011 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 #pragma once 52 53 #include <vector> 54 55 #include "chrome/browser/safe_browsing/safe_browsing_util.h" 56 57 class FilePath; 58 59 namespace safe_browsing { 60 61 class PrefixSet { 62 public: 63 explicit PrefixSet(const std::vector<SBPrefix>& sorted_prefixes); 64 ~PrefixSet(); 65 66 // |true| if |prefix| was in |prefixes| passed to the constructor. 67 bool Exists(SBPrefix prefix) const; 68 69 // Persist the set on disk. 70 static PrefixSet* LoadFile(const FilePath& filter_name); 71 bool WriteFile(const FilePath& filter_name) const; 72 73 // Regenerate the vector of prefixes passed to the constructor into 74 // |prefixes|. Prefixes will be added in sorted order. 75 void GetPrefixes(std::vector<SBPrefix>* prefixes) const; 76 77 // TODO(shess): The following are debugging accessors. Delete once 78 // the encoding problem is figured out. 79 80 size_t IndexBinFor(size_t target_index) const; 81 82 // The number of prefixes represented. 83 size_t GetSize() const; 84 85 // Returns |true| if the element at |target_index| is between items in the 86 // |index_| array. 87 bool IsDeltaAt(size_t target_index) const; 88 89 // Returns the delta used to calculate the element at 90 // |target_index|. Only call if |IsDeltaAt()| returned |true|. 91 uint16 DeltaAt(size_t target_index) const; 92 93 // Check whether |index_| and |deltas_| still match the CRC 94 // generated during construction. 95 bool CheckChecksum() const; 96 97 private: 98 // Maximum number of consecutive deltas to encode before generating 99 // a new index entry. This helps keep the worst-case performance 100 // for |Exists()| under control. 101 static const size_t kMaxRun = 100; 102 103 // Helper for |LoadFile()|. Steals the contents of |index| and 104 // |deltas| using |swap()|. 105 PrefixSet(std::vector<std::pair<SBPrefix,size_t> > *index, 106 std::vector<uint16> *deltas); 107 108 // Top-level index of prefix to offset in |deltas_|. Each pair 109 // indicates a base prefix and where the deltas from that prefix 110 // begin in |deltas_|. The deltas for a pair end at the next pair's 111 // index into |deltas_|. 112 std::vector<std::pair<SBPrefix,size_t> > index_; 113 114 // Deltas which are added to the prefix in |index_| to generate 115 // prefixes. Deltas are only valid between consecutive items from 116 // |index_|, or the end of |deltas_| for the last |index_| pair. 117 std::vector<uint16> deltas_; 118 119 // For debugging, used to verify that |index_| and |deltas| were not 120 // changed after generation during construction. |checksum_| is 121 // calculated from the data used to construct those vectors. 122 uint32 checksum_; 123 124 DISALLOW_COPY_AND_ASSIGN(PrefixSet); 125 }; 126 127 } // namespace safe_browsing 128 129 #endif // CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_ 130