chrome/browser/safe_browsing/prefix_set.h

   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_