verity: remove the depth parameter from bht_create

verity: remove the depth parameter from bht_create

We want to only support regular tries with a single root hash block.

BUG=chromium-os9752
TEST=Ran dm-verity.git unit tests. Ran platform_DMVerityCorruption on H/W.

Change-Id: I49a8b74b8343c4cb5aa871a81b45f06025fe1011

R=wad@chromium.org,taysom@chromium.org,ups@chromium.org

Committed: http://chrome-svn/viewvc/chromeos?view=rev&revision=31b3605

[Paul T, 2011-04-07 21:54:33]

LGTM

http://codereview.chromium.org/6811030/diff/1/file_hasher.cc
File file_hasher.cc (right):

http://codereview.chromium.org/6811030/diff/1/file_hasher.cc#newcode121
file_hasher.cc:121: root_end, hash_start, alg_, digest);
Do you need to keep the 0? or should it just be deleted.

[Will Drewry, 2011-04-07 22:45:17]

Looks pretty good to me.  A couple of questions.

I'm also curious about what happens when this lands - e.g., are we going to see
any weirdness in build/postinst/signing?  I think not, but figured I'd ask since
your mind is on this.

http://codereview.chromium.org/6811030/diff/1/dm-bht.c
File dm-bht.c (left):

http://codereview.chromium.org/6811030/diff/1/dm-bht.c#oldcode298
dm-bht.c:298: if (depth * bht->node_count_shift >= sizeof(unsigned int) * 8) {
You'll probably still want this check.  While node_count_shift may divide into
it cleanly, if the depth is too deep, the indexing using shift may
shift-off-into-space.  Or am I missing something obvious?

http://codereview.chromium.org/6811030/diff/1/dm-bht_unittest.cc
File dm-bht_unittest.cc (left):

http://codereview.chromium.org/6811030/diff/1/dm-bht_unittest.cc#oldcode37
dm-bht_unittest.cc:37: EXPECT_EQ(-EINVAL, dm_bht_create(&bht, 32, 1, "sha256"));
Again, might be worth trying a _really_ large block size here :)

http://codereview.chromium.org/6811030/diff/1/dm-bht_unittest.cc#oldcode187
dm-bht_unittest.cc:187: static const unsigned int total_blocks = 16384;
Should this test go away or should it just be changed to use a different block
count which will ensure different depth from other tests?

http://codereview.chromium.org/6811030/diff/1/file_hasher.cc
File file_hasher.cc (right):

http://codereview.chromium.org/6811030/diff/1/file_hasher.cc#newcode121
file_hasher.cc:121: root_end, hash_start, alg_, digest);
On 2011/04/07 21:54:33, Paul T wrote:
> Do you need to keep the 0? or should it just be deleted.

It needs to stay for now until we change the kernel interface and update the
install and post-install scripts, as well as the signer and signer scripts :/

http://codereview.chromium.org/6811030/diff/1/verity_main.cc
File verity_main.cc (right):

http://codereview.chromium.org/6811030/diff/1/verity_main.cc#newcode23
verity_main.cc:23: "- depth:	Deprecated. Must be `0'.\n"
Any reason not to just ignore it?  "Deprecated. Will be ignored\n"

Or is it to help catch integration errors as we roll forward?

[Mandeep Singh Baines, 2011-04-08 14:28:40]

Fixed. PTAL.

We shouldn't see any wierdness. All users of verity have been converted to use
depth=0. If there is any code that is not using depth=0, you'll get an
informative error message.

http://codereview.chromium.org/6811030/diff/1/dm-bht.c
File dm-bht.c (left):

http://codereview.chromium.org/6811030/diff/1/dm-bht.c#oldcode298
dm-bht.c:298: if (depth * bht->node_count_shift >= sizeof(unsigned int) * 8) {
On 2011/04/07 22:45:17, Will Drewry wrote:
> You'll probably still want this check.  While node_count_shift may divide into
> it cleanly, if the depth is too deep, the indexing using shift may
> shift-off-into-space.  Or am I missing something obvious?

You're right. There is a chance. My reasoning was:

1) block_count is an unsigned int
2) block_count <= UINT_MAX
3) log2(block_count) <= log2(UINT_MAX)
4) depth * node_count_shift = log2(block_count)
5) depth * node_count_shift <= log2(UINT_MAX)

But 4) is not exactly true because of the DIV_ROUND_UP. So if block_count was
close to UINT_MAX and the round up didn't work out so well (digest_size not a
power of 2) you could have an overflow in that extreme case.

http://codereview.chromium.org/6811030/diff/1/verity_main.cc
File verity_main.cc (right):

http://codereview.chromium.org/6811030/diff/1/verity_main.cc#newcode23
verity_main.cc:23: "- depth:	Deprecated. Must be `0'.\n"
On 2011/04/07 22:45:17, Will Drewry wrote:
> Any reason not to just ignore it?  "Deprecated. Will be ignored\n"
> 
> Or is it to help catch integration errors as we roll forward?

Ideally I'll do everything in the right order so that this never gets hit but
wanted to leave an error in the off chance that somehow this gets called with a
non-zero depth.

[Mandeep Singh Baines, 2011-04-11 17:23:23]

ping

[Paul T, 2011-04-11 17:58:10]

LGTM

[Will Drewry, 2011-04-12 03:12:32]

LGTM

thanks!

http://codereview.chromium.org/6811030/diff/6001/dm-bht_unittest.cc
File dm-bht_unittest.cc (right):

http://codereview.chromium.org/6811030/diff/6001/dm-bht_unittest.cc#newcode182
dm-bht_unittest.cc:182: TEST_F(MemoryBhtTest, CreateThenVerifySingleLevel) {
Nit: SingleBlock :) 32 blocks will all end up hashed into one block.  It'd be
worth while to do at least 129 blocks I'd think.  But that could be
yet-another-test in a new CL since this is worthwhile too.

http://codereview.chromium.org/6811030/diff/6001/dm-bht_unittest.cc#newcode186
dm-bht_unittest.cc:186:
"2d3a43008286f56536fa24dcdbf14d342f0548827e374210415c7be0b610d2ba";

FWIW, I did manually cross check this hash:
$ rm /tmp/level.1.tmp; i=0; while [[ $i -lt 32 ]]; do head -c 4096 /dev/zero
|openssl sha -sha256 -binary >> /tmp/level.1.tmp; i=$((i+1)); done; head -c 4096
/dev/zero > /tmp/level.1;
# Pad it out to 4k
$ dd if=/tmp/level.1.tmp of=/tmp/level.1 conv=notrunc
# check the hash
$ openssl sha -sha256 /tmp/level.1
SHA256(/tmp/level.1)=
2d3a43008286f56536fa24dcdbf14d342f0548827e374210415c7be0b610d2ba

Once the trie changes are complete - I think it'd be worthwhile to manually
generate a range of expected roots for these (rather than just taking the new
output of verity).  I dunno if you've been doing that, but I know that's how I
tend to do it and only manually check intermittenly.