Add code to compute the root hash for a hash tree

Add code to compute the root hash for a hash tree

BUG=369895
Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=270050

[asargent_no_longer_on_chrome, 2014-05-12 16:17:20]

Oops, sorry, the previous version wasn't actually ready for review. I've fixed a
couple of bugs and added unit tests. 

Now I think it's ready for review.

[Marijn Kruisselbrink, 2014-05-12 17:53:45]

https://codereview.chromium.org/274243004/diff/40001/extensions/browser/conte...
File extensions/browser/content_hash_tree.cc (right):

https://codereview.chromium.org/274243004/diff/40001/extensions/browser/conte...
extensions/browser/content_hash_tree.cc:25: // by using a pointer. So the first
iteration of the loop this points at
You could just use a pair of iterators instead of a pointer to the vector + an
index, but both work equally well of course.

https://codereview.chromium.org/274243004/diff/40001/extensions/browser/conte...
extensions/browser/content_hash_tree.cc:39: int count = 0;
What is count for? You don't seem to ever read its value.

https://codereview.chromium.org/274243004/diff/40001/extensions/browser/conte...
File extensions/browser/content_hash_tree.h (right):

https://codereview.chromium.org/274243004/diff/40001/extensions/browser/conte...
extensions/browser/content_hash_tree.h:16: // block size should be a multiple of
sizeof(sha256hash).
From the code here it isn't entirely clear why you're passing block_size and
calculating the branching factor from that, instead of just passing the
branching factor directly. But I assume that for the way this method will be
used the block_size makes more sense?

https://codereview.chromium.org/274243004/diff/40001/extensions/browser/conte...
extensions/browser/content_hash_tree.h:16: // block size should be a multiple of
sizeof(sha256hash).
You should probably explicitly document how this method deals with
non-power-of-branching_factor leaf counts. Various specs involving binary merkle
trees that I can find all seem to handle this case differently (duplicating
hashes, not hashing hashes, etc), so I'm not sure if what you implemented is
what you intended (although it does seem as a reasonable approach for merkle
trees with arbitrary branching factors).

[asargent_no_longer_on_chrome, 2014-05-12 21:58:58]

PTAL

https://codereview.chromium.org/274243004/diff/40001/extensions/browser/conte...
File extensions/browser/content_hash_tree.cc (right):

https://codereview.chromium.org/274243004/diff/40001/extensions/browser/conte...
extensions/browser/content_hash_tree.cc:25: // by using a pointer. So the first
iteration of the loop this points at
On 2014/05/12 17:53:45, Marijn Kruisselbrink wrote:
> You could just use a pair of iterators instead of a pointer to the vector + an
> index, but both work equally well of course.

I switched to using an iterator instead of an index, but I think I find it more
understandable to still use a pointer for the current vector.

https://codereview.chromium.org/274243004/diff/40001/extensions/browser/conte...
extensions/browser/content_hash_tree.cc:39: int count = 0;
On 2014/05/12 17:53:45, Marijn Kruisselbrink wrote:
> What is count for? You don't seem to ever read its value.

Good catch - probably left over from some printf-style debugging code or
something. Removed.

https://codereview.chromium.org/274243004/diff/40001/extensions/browser/conte...
File extensions/browser/content_hash_tree.h (right):

https://codereview.chromium.org/274243004/diff/40001/extensions/browser/conte...
extensions/browser/content_hash_tree.h:16: // block size should be a multiple of
sizeof(sha256hash).
On 2014/05/12 17:53:45, Marijn Kruisselbrink wrote:
> You should probably explicitly document how this method deals with
> non-power-of-branching_factor leaf counts. Various specs involving binary
merkle
> trees that I can find all seem to handle this case differently (duplicating
> hashes, not hashing hashes, etc), so I'm not sure if what you implemented is
> what you intended (although it does seem as a reasonable approach for merkle
> trees with arbitrary branching factors).

Added documentation about numbers of nodes that are not integral powers of the
branching factor.

https://codereview.chromium.org/274243004/diff/40001/extensions/browser/conte...
extensions/browser/content_hash_tree.h:16: // block size should be a multiple of
sizeof(sha256hash).
On 2014/05/12 17:53:45, Marijn Kruisselbrink wrote:
> From the code here it isn't entirely clear why you're passing block_size and
> calculating the branching factor from that, instead of just passing the
> branching factor directly. But I assume that for the way this method will be
> used the block_size makes more sense?

I refactored this code out from being inline in another method and didn't really
think about it too much. But I think you're right that it makes more sense to
pass in the branching factor, so I switched to doing that.

[Marijn Kruisselbrink, 2014-05-12 22:57:51]

https://codereview.chromium.org/274243004/diff/80001/extensions/browser/conte...
File extensions/browser/content_hash_tree_unittest.cc (right):

https://codereview.chromium.org/274243004/diff/80001/extensions/browser/conte...
extensions/browser/content_hash_tree_unittest.cc:22: int block_size_;
You're not actually using block_size_ (and I'm not sure why nodes_ is a member
variable, instead of just local in each test case, but if you prefer it that way
I have no problems with it).

https://codereview.chromium.org/274243004/diff/80001/extensions/browser/conte...
extensions/browser/content_hash_tree_unittest.cc:32: node1.append('1',
kSHA256Length);
I'm not sure why you're creating an empty string and then using append here,
while further down for expected you just use the std::string constructor that
does the same thing directly. But more importantly I think you swapped the order
of the arguments (actually, I'm not sure which append overload this ends up
resolving to, presumably still the (size_t, char) one, despite that involving
various implicit casts).

https://codereview.chromium.org/274243004/diff/80001/extensions/browser/conte...
extensions/browser/content_hash_tree_unittest.cc:53:
node.append(static_cast<char>((j + i) % 256), 1);
similar here, it seems like this would append X 1-bytes, not 1 X-byte.

[asargent_no_longer_on_chrome, 2014-05-12 23:52:48]

ok, new version up

https://codereview.chromium.org/274243004/diff/80001/extensions/browser/conte...
File extensions/browser/content_hash_tree_unittest.cc (right):

https://codereview.chromium.org/274243004/diff/80001/extensions/browser/conte...
extensions/browser/content_hash_tree_unittest.cc:22: int block_size_;
On 2014/05/12 22:57:51, Marijn Kruisselbrink wrote:
> You're not actually using block_size_ (and I'm not sure why nodes_ is a member
> variable, instead of just local in each test case, but if you prefer it that
way
> I have no problems with it).

Good observations! This is why we have code-review. =)

I've removed block_size_. For nodes_, I think I originally envisioned needing a
richer set of helper methods, so I've switched the whole thing over to not have
a ::testing::Test base class and use TEST() instead of TEST_F.

https://codereview.chromium.org/274243004/diff/80001/extensions/browser/conte...
extensions/browser/content_hash_tree_unittest.cc:32: node1.append('1',
kSHA256Length);
On 2014/05/12 22:57:51, Marijn Kruisselbrink wrote:
> I'm not sure why you're creating an empty string and then using append here,
> while further down for expected you just use the std::string constructor that
> does the same thing directly. But more importantly I think you swapped the
order
> of the arguments (actually, I'm not sure which append overload this ends up
> resolving to, presumably still the (size_t, char) one, despite that involving
> various implicit casts).

Great catch. I definitely did confuse the two versions:

append(const charT* s, size_type n)
append(size_type n, charT c)


I replaced this pattern with a helper function that returns a real signature
based on a seed, and also added a DCHECK in content_hash_tree.cc to help catch
short signatures in the input in the future.

https://codereview.chromium.org/274243004/diff/80001/extensions/browser/conte...
extensions/browser/content_hash_tree_unittest.cc:53:
node.append(static_cast<char>((j + i) % 256), 1);
On 2014/05/12 22:57:51, Marijn Kruisselbrink wrote:
> similar here, it seems like this would append X 1-bytes, not 1 X-byte.

Done.

[Marijn Kruisselbrink, 2014-05-13 00:22:42]

lgtm

[asargent_no_longer_on_chrome, 2014-05-13 03:41:18]

The CQ bit was checked by asargent@chromium.org

[commit-bot: I haz the power, 2014-05-13 03:41:49]

CQ is trying da patch. Follow status at
 https://chromium-status.appspot.com/cq/asargent@chromium.org/274243004/100001

[commit-bot: I haz the power, 2014-05-13 05:41:59]

FYI, CQ is re-trying this CL (attempt #1).
Please consider checking whether the failures are real,
and report flakes to chrome-troopers@google.com.
The failing builders are:
  android_dbg on tryserver.chromium
(http://build.chromium.org/p/tryserver.chromium/builders/android_dbg/builds/18...)
  linux_chromium_chromeos_rel on tryserver.chromium
(http://build.chromium.org/p/tryserver.chromium/builders/linux_chromium_chrome...)
  linux_chromium_rel on tryserver.chromium
(http://build.chromium.org/p/tryserver.chromium/builders/linux_chromium_rel/bu...)

[commit-bot: I haz the power, 2014-05-13 05:49:42]

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

[commit-bot: I haz the power, 2014-05-13 05:49:43]

Try jobs failed on following builders:
  android_dbg on tryserver.chromium
(http://build.chromium.org/p/tryserver.chromium/builders/android_dbg/builds/18...)
  linux_chromium_chromeos_rel on tryserver.chromium
(http://build.chromium.org/p/tryserver.chromium/builders/linux_chromium_chrome...)

[asargent_no_longer_on_chrome, 2014-05-13 05:51:18]

The CQ bit was checked by asargent@chromium.org

[commit-bot: I haz the power, 2014-05-13 05:51:26]

CQ is trying da patch. Follow status at
 https://chromium-status.appspot.com/cq/asargent@chromium.org/274243004/120001

[commit-bot: I haz the power, 2014-05-13 08:26:29]

Change committed as 270050