Merge the hash prefixes from the old store and the additions in the partial

components/safe_browsing_db/v4_store.h

Index: components/safe_browsing_db/v4_store.h
diff --git a/components/safe_browsing_db/v4_store.h b/components/safe_browsing_db/v4_store.h
index bbafbe73dfafe2f8f6957bceed821acc46e0101e..27b179875bb98eda0d3d90b79b8751b5e6a6edaf 100644
--- a/components/safe_browsing_db/v4_store.h
+++ b/components/safe_browsing_db/v4_store.h
@@ -18,6 +18,25 @@ class V4Store;
 typedef base::Callback<void(std::unique_ptr<V4Store>)>
     UpdatedStoreReadyCallback;
 
+// The size of the hash prefix, in bytes. It should be between 4 to 32 (full
+// hash).
+typedef size_t PrefixSize;
+
+// A hash prefix sent by the SafeBrowsing PVer4 service.
+typedef std::unique_ptr<char> HashPrefix;

[Nathan Parker, 2016/07/11 18:09:58]

I think we talked about this already, but keeping a pointer to each 4-byte hash
will triple the memory requirement.

To keep one contiguous block, you could make a container, say VarHashArray, with
a ctor like
  VarHashArray(size_t hash_length);

You could make a () operator that'd return a char* ptr to the x*hash_length'th
byte. You could write a VarHashArray::compare(other) that'd take into account
the potentially different hash lengths for the two arrays. You'd probably need
an append method, and an iterator (or just use ints).  Hmm, seems like this must
exist. It's almost covered by std::valarray.

[vakh (use Gerrit instead), 2016/07/12 07:34:19]

As discussed offline, using a std::string instead. This will keep the design
simple.
If, at a later time, we feel the need to use a valarray of objects later, we'll
do so then.

+
+// The sorted list of hash prefixes.
+typedef std::vector<HashPrefix> HashPrefixes;
+
+// Stores the list of sorted hash prefixes, by size.
+// For instance: {4: ["abcd", "bcde", "cdef", "gggg"], 5: ["fffff"]}
+typedef base::hash_map<PrefixSize, HashPrefixes> HashPrefixMap;

[Nathan Parker, 2016/07/11 18:09:58]

I was going to say you should think about using a vector<HashPrefixes>, indexed
by PrefixSize since that'd be faster to iterate through -- it wouldn't have to
hash the size before looking it up.  We have the advantage that we know the
index is bounded 4-32.

But.. it wouldn't be much faster.  The hash function for a size_t is a noop (I
looked it up), and then to find the hash bucket it'd have to do a few pointer
de-ref's.  So for now I'd say the readability of this outweighs the potential
perf gain.  We'll measure it later.

[vakh (use Gerrit instead), 2016/07/12 07:34:19]

Acknowledged.

+
+// Stores the index of the last element merged from the HashPrefixMap for a
+// given prefix size. For instance: {4:3, 5:1} means that we have already merged
+// 3 hash prefixes of length 4, and 1 hash prefix of length 5.
+typedef base::hash_map<PrefixSize, size_t> CounterMap;
+
 // Enumerate different failure events while parsing the file read from disk for
 // histogramming purposes.  DO NOT CHANGE THE ORDERING OF THESE VALUES.
 enum StoreReadResult {
@@ -79,6 +98,24 @@ enum StoreWriteResult {
   STORE_WRITE_RESULT_MAX
 };
 
+// Enumerate different events while merging the update fetched fom the server
+// for histogramming purposes.
+// DO NOT CHANGE THE ORDERING OF THESE VALUES.
+enum MergeUpdateResult {
+  // No errors.
+  MERGE_SUCCESS = 0,
+
+  // Reserved for errors in parsing this enum.
+  UNEXPECTED_MERGE_FAILURE = 1,
+
+  // The number of bytes in additions isn't a multiple of prefix size.
+  ADDITIONS_SIZE_UNEXPECTED_FAILURE = 2,
+
+  // Memory space for histograms is determined by the max.  ALWAYS
+  // ADD NEW VALUES BEFORE THIS ONE.
+  MERGE_UPDATE_RESULT_MAX
+};
+
 // Factory for creating V4Store. Tests implement this factory to create fake
 // stores for testing.
 class V4StoreFactory {
@@ -127,6 +164,48 @@ class V4Store {
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestWritePartialResponseType);
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestWriteFullResponseType);
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestReadFromFileWithUnknownProto);
+  FRIEND_TEST_ALL_PREFIXES(V4StoreTest,
+                           TestAddUnlumpedHashesWithInvalidAddition);
+  FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestAddUnlumpedHashes);
+  FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestAddUnlumpedHashesWithEmptyString);
+  FRIEND_TEST_ALL_PREFIXES(V4StoreTest,
+                           TestGetNextSmallestPrefixSizeWithEmptyPrefixMap);
+  FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestGetNextSmallestPrefixSize);
+  FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestGetNextUnmergedPrefix);
+  FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestMergeUpdates);
+
+  // Breaks down the |lumped_hashes|, which is a single string, into hash
+  // prefixes, each of size |prefix_size|. These prefixes are stored in a
+  // |prefix_map| as a vector, with |prefix_size| as key.
+  static MergeUpdateResult AddUnlumpedHashes(PrefixSize prefix_size,
+                                             const std::string& lumped_hashes,
+                                             HashPrefixMap* prefix_map);
+
+  // Returns the next hash prefix of length |prefix_size| from |hash_prefix_map|
+  // that hasn't been merged already. |counter_map| is used to determine the
+  // index of the next prefix of size |prefix_size| to merge.
+  static HashPrefix& GetNextUnmergedPrefixForSize(
+      PrefixSize prefix_size,
+      HashPrefixMap& hash_prefix_map,

[Nathan Parker, 2016/07/11 18:09:58]

I think the style guide says output-args should be pointers rather than
references.

[vakh (use Gerrit instead), 2016/07/12 07:34:19]

Done.

+      const CounterMap& counter_map);
+
+  // Generates the HashPrefixMap for the additions received in the partial
+  // update from the seriver.
+  static HashPrefixMap GetHashPrefixMapFromAdditions(

[Nathan Parker, 2016/07/11 18:09:58]

Make HashPrefixMap a ptr output-arg.  Same below.  Otherwise it makes temp
copies of them on the stack.

[vakh (use Gerrit instead), 2016/07/12 07:34:19]

Done.

+      const ::google::protobuf::RepeatedPtrField<ThreatEntrySet>& additions);
+
+  static CounterMap GetInitializedCounterMap(
+      const HashPrefixMap& hash_prefix_map);
+
+  static bool GetNextSmallestPrefixSize(const HashPrefixMap& hash_prefix_map,
+                                        const CounterMap& counter_map,
+                                        PrefixSize* smallest_prefix_size);
+
+  // Merges the prefix map from the old store and the update to populate the
+  // prefix map for the current store.
+  // TODO(vakh): Process removals also.
+  void MergeUpdate(HashPrefixMap& old_hash_prefix_map,
+                   HashPrefixMap& additions_map);
 
   // Reads the state of the store from the file on disk and returns the reason
   // for the failure or reports success.
@@ -140,6 +219,7 @@ class V4Store {
   // update response.
   std::string state_;
   const base::FilePath store_path_;
+  HashPrefixMap hash_prefix_map_;
   const scoped_refptr<base::SequencedTaskRunner> task_runner_;
 };