PVer4: Verify checksum for downloaded updates

Verify checksum for downloaded updates and discard the update if the checks fails to match.

BUG=543161
Committed: https://crrev.com/0facbb7c1aea0831a5b0ce159844bdf674f10852
Cr-Commit-Position: refs/heads/master@{#411225}

[vakh (use Gerrit instead), 2016-08-04 00:10:28]

The CQ bit was checked by vakh@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-04 00:10:44]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-08-04 00:19:56]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-08-04 00:19:57]

Dry run: Try jobs failed on following builders:
  chromium_presubmit on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/chromium_presub...)

[vakh (use Gerrit instead), 2016-08-04 00:28:13]

Tiny: Remove a temporary test that I added for debugging

[vakh (use Gerrit instead), 2016-08-04 00:28:16]

The CQ bit was checked by vakh@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-04 00:28:51]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[vakh (use Gerrit instead), 2016-08-04 00:36:55]

Tiny: Remove extra logging

[vakh (use Gerrit instead), 2016-08-04 00:36:57]

The CQ bit was checked by vakh@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-04 00:37:13]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[vakh (use Gerrit instead), 2016-08-04 00:37:17]

Patchset #2 (id:20001) has been deleted

[vakh (use Gerrit instead), 2016-08-04 00:39:54]

Tiny: Depend on //crypto

[vakh (use Gerrit instead), 2016-08-04 00:39:56]

The CQ bit was checked by vakh@chromium.org to run a CQ dry run

[vakh (use Gerrit instead), 2016-08-04 00:40:12]

Patchset #2 (id:40001) has been deleted

[commit-bot: I haz the power, 2016-08-04 00:40:37]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[vakh (use Gerrit instead), 2016-08-04 00:41:13]

Patchset #2 (id:60001) has been deleted

[commit-bot: I haz the power, 2016-08-04 02:16:44]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-08-04 02:16:45]

Dry run: Try jobs failed on following builders:
  linux_chromium_asan_rel_ng on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[vakh (use Gerrit instead), 2016-08-04 22:26:11]

The CQ bit was checked by vakh@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-04 22:26:45]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[vakh (use Gerrit instead), 2016-08-04 23:50:02]

a

[vakh (use Gerrit instead), 2016-08-04 23:50:05]

The CQ bit was checked by vakh@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-04 23:50:16]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[vakh (use Gerrit instead), 2016-08-04 23:50:17]

Patchset #2 (id:80001) has been deleted

[vakh (use Gerrit instead), 2016-08-04 23:55:39]

Description was changed from

==========
Checksum

BUG=543161
==========

to

==========
Verify checksum for downloaded updates and discard the update if the checks
fails to match.

BUG=543161
==========

[vakh (use Gerrit instead), 2016-08-04 23:55:40]

vakh@chromium.org changed reviewers:
+ awoz@chromium.org, noelutz@chromium.org, nparker@chromium.org

[commit-bot: I haz the power, 2016-08-05 00:23:02]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-08-05 00:23:03]

Dry run: Try jobs failed on following builders:
  linux_chromium_chromeos_rel_ng on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)
  mac_chromium_rel_ng on master.tryserver.chromium.mac (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.mac/builders/mac_chromium_rel_...)

[vakh (use Gerrit instead), 2016-08-05 02:00:17]

Tiny: Ensure that response_type is set. And set it in tests

[vakh (use Gerrit instead), 2016-08-05 02:00:22]

The CQ bit was checked by vakh@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-05 02:00:45]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[vakh (use Gerrit instead), 2016-08-05 02:02:21]

Tiny: Update enum in histograms.xml

[vakh (use Gerrit instead), 2016-08-05 02:02:24]

The CQ bit was checked by vakh@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-05 02:02:31]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-08-05 03:22:50]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-08-05 03:22:51]

Dry run: Try jobs failed on following builders:
  linux_chromium_asan_rel_ng on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[vakh (use Gerrit instead), 2016-08-05 17:22:50]

Patchset #4 (id:140001) has been deleted

[vakh (use Gerrit instead), 2016-08-05 17:30:04]

Review from here

[vakh (use Gerrit instead), 2016-08-05 17:30:08]

The CQ bit was checked by vakh@chromium.org to run a CQ dry run

[vakh (use Gerrit instead), 2016-08-05 17:30:21]

Patchset #4 (id:150001) has been deleted

[commit-bot: I haz the power, 2016-08-05 17:30:40]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[vakh (use Gerrit instead), 2016-08-05 17:31:04]

Patchset #3 (id:120001) has been deleted

[vakh (use Gerrit instead), 2016-08-05 17:31:19]

Patchset #2 (id:100001) has been deleted

[commit-bot: I haz the power, 2016-08-05 18:18:09]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-08-05 18:18:10]

Dry run: Try jobs failed on following builders:
  linux_chromium_chromeos_ozone_rel_ng on master.tryserver.chromium.linux
(JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[vakh (use Gerrit instead), 2016-08-05 18:42:00]

XXS: Added a DCHECK for PARTIAL_UPDATE in ProcessPartialUpdate

[vakh (use Gerrit instead), 2016-08-05 18:42:03]

The CQ bit was checked by vakh@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-05 18:42:34]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-08-05 19:47:47]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-08-05 19:47:48]

Dry run: This issue passed the CQ dry run.

[Nathan Parker, 2016-08-08 21:17:20]

https://codereview.chromium.org/2206733002/diff/190001/components/safe_browsi...
File components/safe_browsing_db/v4_rice.cc (right):

https://codereview.chromium.org/2206733002/diff/190001/components/safe_browsi...
components/safe_browsing_db/v4_rice.cc:266: std::string
V4RiceDecoder::DebugString() const {
Are there constants describing what 4 and 8 are?  It isn't clear to me what this
equation represents.

https://codereview.chromium.org/2206733002/diff/190001/components/safe_browsi...
File components/safe_browsing_db/v4_store.cc (right):

https://codereview.chromium.org/2206733002/diff/190001/components/safe_browsi...
components/safe_browsing_db/v4_store.cc:126: ProcessUpdate(hash_prefix_map_old,
response, new_store.get());
This change removes the nicely optimized short-cut you had for full-updates. 
Before, we'd just copy the whole thing in one motion. Now we have to iterate
through the whole map and append hashes one at a time in lex-order.  It looks
like you do need to iterate in lex order to compute the checksum, but we could
save some copying time by copying in large blocks rather than many small ones.

I think that'd save some CPU, but it shouldn't change memory usage.  So I'd be
OK with a TODO here suggesting we could optimize the full updates if needed but
leave the work till we have some measurements.

https://codereview.chromium.org/2206733002/diff/190001/components/safe_browsi...
components/safe_browsing_db/v4_store.cc:234: DVLOG(1) << "ApplyUpdate failed: "
<< *this;
Make it a single DVLOG.

https://codereview.chromium.org/2206733002/diff/190001/components/safe_browsi...
components/safe_browsing_db/v4_store.cc:427: all_prefixes_concatenated +=
next_smallest_prefix_old;
Rather than building up another whole copy of the hashes in memory, you should
be able to compute the SHA256 incrementally.

https://codereview.chromium.org/2206733002/diff/190001/components/safe_browsi...
components/safe_browsing_db/v4_store.cc:468: DVLOG(1) << "calculated checksum: "
<< checksum_base64;
How about making it a single DVLOG, with an error message ("Checksum failed...")

https://codereview.chromium.org/2206733002/diff/190001/components/safe_browsi...
components/safe_browsing_db/v4_store.cc:474: return (!raw_removals ||
removals_iter == raw_removals->end())
It might be useful to check (!raw_removals || removals_iter ==
raw_removals->end()) BEFORE checking the checksum, since if the removals weren't
processed correctly it'll just show up as a checksum failure otherwise.

https://codereview.chromium.org/2206733002/diff/190001/components/safe_browsi...
File components/safe_browsing_db/v4_store.h (right):

https://codereview.chromium.org/2206733002/diff/190001/components/safe_browsi...
components/safe_browsing_db/v4_store.h:301: V4Store* new_store);
To consider:

It starts to get a bit murky when you have static functions within the class
that take a V4Store* -- they're basically a non-static function since they have
access to all the private members of V4Store (it's like new_store is "this"). 
You could consider making these non-static, or pulling them from the class and
putting them in a "namespace internal {...}" if they don't really need to access
private members.

[vakh (use Gerrit instead), 2016-08-08 22:44:19]

nparker@ feedback: non-static methods, check removals before checksum, ...

[vakh (use Gerrit instead), 2016-08-08 22:44:25]

The CQ bit was checked by vakh@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-08 22:45:19]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[vakh (use Gerrit instead), 2016-08-08 22:46:47]

https://codereview.chromium.org/2206733002/diff/190001/components/safe_browsi...
File components/safe_browsing_db/v4_rice.cc (right):

https://codereview.chromium.org/2206733002/diff/190001/components/safe_browsi...
components/safe_browsing_db/v4_rice.cc:266: std::string
V4RiceDecoder::DebugString() const {
On 2016/08/08 21:17:19, Nathan Parker wrote:
> Are there constants describing what 4 and 8 are?  It isn't clear to me what
this
> equation represents.

Now using constants and added a comment describing that calculation.

https://codereview.chromium.org/2206733002/diff/190001/components/safe_browsi...
File components/safe_browsing_db/v4_store.cc (right):

https://codereview.chromium.org/2206733002/diff/190001/components/safe_browsi...
components/safe_browsing_db/v4_store.cc:126: ProcessUpdate(hash_prefix_map_old,
response, new_store.get());
On 2016/08/08 21:17:19, Nathan Parker wrote:
> This change removes the nicely optimized short-cut you had for full-updates. 
> Before, we'd just copy the whole thing in one motion. Now we have to iterate
> through the whole map and append hashes one at a time in lex-order.  It looks
> like you do need to iterate in lex order to compute the checksum, but we could
> save some copying time by copying in large blocks rather than many small ones.
> 
> I think that'd save some CPU, but it shouldn't change memory usage.  So I'd be
> OK with a TODO here suggesting we could optimize the full updates if needed
but
> leave the work till we have some measurements.

Done.

https://codereview.chromium.org/2206733002/diff/190001/components/safe_browsi...
components/safe_browsing_db/v4_store.cc:234: DVLOG(1) << "ApplyUpdate failed: "
<< *this;
On 2016/08/08 21:17:19, Nathan Parker wrote:
> Make it a single DVLOG.

Done.

https://codereview.chromium.org/2206733002/diff/190001/components/safe_browsi...
components/safe_browsing_db/v4_store.cc:427: all_prefixes_concatenated +=
next_smallest_prefix_old;
On 2016/08/08 21:17:19, Nathan Parker wrote:
> Rather than building up another whole copy of the hashes in memory, you should
> be able to compute the SHA256 incrementally.

Done.

https://codereview.chromium.org/2206733002/diff/190001/components/safe_browsi...
components/safe_browsing_db/v4_store.cc:468: DVLOG(1) << "calculated checksum: "
<< checksum_base64;
On 2016/08/08 21:17:19, Nathan Parker wrote:
> How about making it a single DVLOG, with an error message ("Checksum
failed...")

Done.

https://codereview.chromium.org/2206733002/diff/190001/components/safe_browsi...
components/safe_browsing_db/v4_store.cc:474: return (!raw_removals ||
removals_iter == raw_removals->end())
On 2016/08/08 21:17:19, Nathan Parker wrote:
> It might be useful to check (!raw_removals || removals_iter ==
> raw_removals->end()) BEFORE checking the checksum, since if the removals
weren't
> processed correctly it'll just show up as a checksum failure otherwise.

Done.

https://codereview.chromium.org/2206733002/diff/190001/components/safe_browsi...
File components/safe_browsing_db/v4_store.h (right):

https://codereview.chromium.org/2206733002/diff/190001/components/safe_browsi...
components/safe_browsing_db/v4_store.h:301: V4Store* new_store);
On 2016/08/08 21:17:19, Nathan Parker wrote:
> To consider:
> 
> It starts to get a bit murky when you have static functions within the class
> that take a V4Store* -- they're basically a non-static function since they
have
> access to all the private members of V4Store (it's like new_store is "this"). 
> You could consider making these non-static, or pulling them from the class and
> putting them in a "namespace internal {...}" if they don't really need to
access
> private members.

Agree. Made them non-static.

[vakh (use Gerrit instead), 2016-08-08 22:48:01]

rkaplow@: Please review the minor changes in
tools/metrics/histograms/histograms.xml

[vakh (use Gerrit instead), 2016-08-08 23:58:49]

git

[vakh (use Gerrit instead), 2016-08-08 23:58:52]

The CQ bit was checked by vakh@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-08 23:59:11]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[Nathan Parker, 2016-08-09 00:10:19]

lgtm

https://codereview.chromium.org/2206733002/diff/230001/components/safe_browsi...
File components/safe_browsing_db/v4_database.cc (right):

https://codereview.chromium.org/2206733002/diff/230001/components/safe_browsi...
components/safe_browsing_db/v4_database.cc:143: DVLOG(1) << "Store update
discarded: " << *(*store_map_)[identifier];
nit: I suspect this is redundant with the "ApplyUpdate failed" vlog in
v4_store.cc

https://codereview.chromium.org/2206733002/diff/230001/components/safe_browsi...
File components/safe_browsing_db/v4_store.cc (right):

https://codereview.chromium.org/2206733002/diff/230001/components/safe_browsi...
components/safe_browsing_db/v4_store.cc:384: std::unique_ptr<crypto::SecureHash>
ctx(
nit: maybe call ctx "checksum" or "checksum_ctx" so it's more clear what its
doing.

https://codereview.chromium.org/2206733002/diff/230001/components/safe_browsi...
File components/safe_browsing_db/v4_store_unittest.cc (right):

https://codereview.chromium.org/2206733002/diff/230001/components/safe_browsi...
components/safe_browsing_db/v4_store_unittest.cc:615:
EXPECT_EQ(HASH_PREFIX_MAP_GENERATION_FAILURE, read_store.ReadFromDisk());
Is the state and map no longer empty?  Seems like it would be.

[commit-bot: I haz the power, 2016-08-09 01:05:52]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-08-09 01:05:53]

Dry run: This issue passed the CQ dry run.

[vakh (use Gerrit instead), 2016-08-10 20:21:22]

Minor: nparker@'s CR feedback

[vakh (use Gerrit instead), 2016-08-10 20:21:29]

The CQ bit was checked by vakh@chromium.org to run a CQ dry run

[vakh (use Gerrit instead), 2016-08-10 20:21:48]

The CQ bit was checked by vakh@chromium.org

[vakh (use Gerrit instead), 2016-08-10 20:21:51]

The patchset sent to the CQ was uploaded after l-g-t-m from nparker@chromium.org
Link to the patchset: https://codereview.chromium.org/2206733002/#ps250001
(title: "Minor: nparker@'s CR feedback")

[commit-bot: I haz the power, 2016-08-10 20:22:18]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-08-10 20:31:24]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-08-10 20:31:26]

Try jobs failed on following builders:
  chromium_presubmit on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/chromium_presub...)

[vakh (use Gerrit instead), 2016-08-10 20:33:42]

vakh@chromium.org changed reviewers:
+ rkaplow@chromium.org
- awoz@chromium.org, noelutz@chromium.org

[vakh (use Gerrit instead), 2016-08-10 20:33:43]

rkaplow@chromium.org: Please review the change in histograms.xml

[rkaplow, 2016-08-10 20:39:48]

lgtm

[vakh (use Gerrit instead), 2016-08-10 20:40:21]

The CQ bit was checked by vakh@chromium.org

[commit-bot: I haz the power, 2016-08-10 20:41:30]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-08-10 21:26:44]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-08-10 21:26:46]

Try jobs failed on following builders:
  win_chromium_rel_ng on master.tryserver.chromium.win (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_rel_...)

[vakh (use Gerrit instead), 2016-08-10 21:30:11]

The CQ bit was checked by vakh@chromium.org

[commit-bot: I haz the power, 2016-08-10 21:30:56]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-08-10 22:54:46]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-08-10 22:54:47]

Try jobs failed on following builders:
  mac_chromium_rel_ng on master.tryserver.chromium.mac (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.mac/builders/mac_chromium_rel_...)

[vakh (use Gerrit instead), 2016-08-11 00:25:09]

The CQ bit was checked by vakh@chromium.org

[commit-bot: I haz the power, 2016-08-11 00:26:14]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-08-11 02:15:30]

Description was changed from

==========
Verify checksum for downloaded updates and discard the update if the checks
fails to match.

BUG=543161
==========

to

==========
Verify checksum for downloaded updates and discard the update if the checks
fails to match.

BUG=543161
==========

[commit-bot: I haz the power, 2016-08-11 02:15:31]

Committed patchset #6 (id:250001)

[commit-bot: I haz the power, 2016-08-11 02:16:47]

Description was changed from

==========
Verify checksum for downloaded updates and discard the update if the checks
fails to match.

BUG=543161
==========

to

==========
Verify checksum for downloaded updates and discard the update if the checks
fails to match.

BUG=543161

Committed: https://crrev.com/0facbb7c1aea0831a5b0ce159844bdf674f10852
Cr-Commit-Position: refs/heads/master@{#411225}
==========

[commit-bot: I haz the power, 2016-08-11 02:16:49]

Patchset 6 (id:??) landed as
https://crrev.com/0facbb7c1aea0831a5b0ce159844bdf674f10852
Cr-Commit-Position: refs/heads/master@{#411225}

[noé, 2016-08-11 08:15:24]

noelutz@chromium.org changed reviewers:
+ noelutz@chromium.org

[noé, 2016-08-11 08:15:25]

https://codereview.chromium.org/2206733002/diff/250001/components/safe_browsi...
File components/safe_browsing_db/v4_store.cc (right):

https://codereview.chromium.org/2206733002/diff/250001/components/safe_browsi...
components/safe_browsing_db/v4_store.cc:147: // lexographical order to store it,
but we do need to do that for calculating
I believe the right spelling is lexicographical :). Here and below.

https://codereview.chromium.org/2206733002/diff/250001/components/safe_browsi...
components/safe_browsing_db/v4_store.cc:393: while (old_has_unmerged ||
additions_has_unmerged) {
This is quite complicated code. Have you considered putting all the prefixes
into a set<string> and then applying additions and removals. At the end
converting it back to a HashPrefixMap?

[vakh (use Gerrit instead), 2016-08-11 08:31:20]

Thanks for the review, Noe. Please see my comments below.

https://codereview.chromium.org/2206733002/diff/250001/components/safe_browsi...
File components/safe_browsing_db/v4_store.cc (right):

https://codereview.chromium.org/2206733002/diff/250001/components/safe_browsi...
components/safe_browsing_db/v4_store.cc:147: // lexographical order to store it,
but we do need to do that for calculating
On 2016/08/11 08:15:25, noé wrote:
> I believe the right spelling is lexicographical :). Here and below.

Thanks. I'll fix that in the next CL.

https://codereview.chromium.org/2206733002/diff/250001/components/safe_browsi...
components/safe_browsing_db/v4_store.cc:393: while (old_has_unmerged ||
additions_has_unmerged) {
On 2016/08/11 08:15:25, noé wrote:
> This is quite complicated code. Have you considered putting all the prefixes
> into a set<string> and then applying additions and removals. At the end
> converting it back to a HashPrefixMap?

Yes, it would simplify the code but at the cost of increasing time complexity.
Using a set would cost O(N*log(N)) time, whereas the current implementation
costs O(N).

[vakh (use Gerrit instead), 2016-08-11 17:05:59]

https://codereview.chromium.org/2206733002/diff/250001/components/safe_browsi...
File components/safe_browsing_db/v4_store.cc (right):

https://codereview.chromium.org/2206733002/diff/250001/components/safe_browsi...
components/safe_browsing_db/v4_store.cc:393: while (old_has_unmerged ||
additions_has_unmerged) {
On 2016/08/11 08:31:20, vakh wrote:
> On 2016/08/11 08:15:25, noé wrote:
> > This is quite complicated code. Have you considered putting all the prefixes
> > into a set<string> and then applying additions and removals. At the end
> > converting it back to a HashPrefixMap?
> 
> Yes, it would simplify the code but at the cost of increasing time complexity.
> Using a set would cost O(N*log(N)) time, whereas the current implementation
> costs O(N).

Sorry, I take that back. I think the time complexity is probably the same.

However, creating a set means creating a 32 byte string object for each of the
hash prefixes, most of which are 4-bytes long. This would end up taking 8 times
more memory, even though it would be for a small duration. That's what I was
trying to avoid.