CHROMIUM: verity: remove special-case logic for the root node

CHROMIUM: verity: remove special-case logic for the root node

Now that the root-node is the same width as the interior nodes
of the hash tree, we no longer need to make it a special case.

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

Change-Id: I5faf43b2ec6e563f77966c7b8b62eb64cfc73198
Signed-off-by: Mandeep Singh Baines <msb@chromium.org>;

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

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

[Mandeep Singh Baines, 2011-04-25 16:26:03]

ping

[Will Drewry, 2011-04-25 16:26:44]

On 2011/04/25 16:26:03, Mandeep Singh Baines wrote:
> ping

pong

[Will Drewry, 2011-04-25 16:40:42]

Very exciting!  A few nits and questions.

thanks!
will

http://codereview.chromium.org/6896044/diff/1/drivers/md/dm-bht.c
File drivers/md/dm-bht.c (right):

http://codereview.chromium.org/6896044/diff/1/drivers/md/dm-bht.c#newcode566
drivers/md/dm-bht.c:566: if (depth == 0 && state != DM_BHT_ENTRY_VERIFIED) {
This is a much more succinct special case :)

http://codereview.chromium.org/6896044/diff/1/drivers/md/dm-bht.c#newcode570
drivers/md/dm-bht.c:570: depth--;
I know unsigned underflow is defined, but it stil makes me squirm a bit.  Could
we do something like:
  if (depth == 0 && ...) {
  } else {
    depth++;
  }
  for ( ; depth < bht->depth; ..) {

?

The other option is to just add the one atomic_set call into the special case:

if (depth == 0 && ...) {
  if (dm_bht_compute...)
    goto mismatch;
  atomic_set(&entry->state, DM_BHT_ENTRY_VERIFIED)
}

then let the loop iterate from there?

http://codereview.chromium.org/6896044/diff/1/drivers/md/dm-bht.c#newcode586
drivers/md/dm-bht.c:586: DMERR("verify_path: failed to verify hash against
parent (d=%u,bi=%u)",
nit: This should probably be a  DMERR_LIMIT().

http://codereview.chromium.org/6896044/diff/1/drivers/md/dm-bht.c#newcode588
drivers/md/dm-bht.c:588: dm_bht_log_mismatch(bht, node, digest);
Unless the caller is going to do it (which the caller should go away :), we
should go ahead and do:
  atomic_set(&entry->state, DM_BHT_ENTRY_ERROR);
...
Actually, let's leave this for a later discussion.  If we ever change the state
on a node to < READY while there are requests on a caller's verify queue, we
will hit the BUG_ON up above.  Ugh.

I'll leave this in here as a note to us for later :/

http://codereview.chromium.org/6896044/diff/1/drivers/md/dm-bht.c#newcode821
drivers/md/dm-bht.c:821: for (depth = bht->depth - 1; (int)depth >= 0; depth--)
{
Why not just walk up the tree since ordering doesn't matter (like in
dm_bht_populate)?

unsigned int depth;
for (depth = 0; depth < bht->depth; ++depth) {
  struct dm_bht_entry *entry = dm_bht_get_entry(bht, depth, block_index);
  if (atomic_read(&entry->state) < DM_BHT_ENTRY_READY)
    return false;
}
return true;

?

http://codereview.chromium.org/6896044/diff/1/drivers/md/dm-bht.c#newcode846
drivers/md/dm-bht.c:846: BUG_ON(block_index >= bht->block_count);
hrm I was going to say that I prefer return -EIO (or better, -EINVAL), here to
allow the caller to take evasive action (like changing kernels :), but I don't
see a way for dm-verity to get the wrong block_index fed in based solely on
malicious hash or block data.

[If we did ship with this as a programming bug, though, it might still be nice
to have the user fall back over to the old kernel.  As is, this will just leave
them panic'ing and rebooting wily nily.]

What do you think?  As you know, I'm nervous about using BUG_ON anywhere in this
code versus giving dm-verity a chance to decide., so feel free to tell me I'm
being too paranoid.

http://codereview.chromium.org/6896044/diff/1/drivers/md/dm-bht.c#newcode891
drivers/md/dm-bht.c:891: DMERR_LIMIT("Failed to verify block: %u (%d)",
block_index, r);
Since there is a DMERR in the verify_path call, it'd make sense to me to further
gut this:
  return dm_bht_verify_path(bht, block_index, pg, offset);

Then the next step can be to just kill it ... finally!

[Mandeep Singh Baines, 2011-04-25 17:44:21]

PTAL. Fixed. Re-tested.

http://codereview.chromium.org/6896044/diff/1/drivers/md/dm-bht.c
File drivers/md/dm-bht.c (right):

http://codereview.chromium.org/6896044/diff/1/drivers/md/dm-bht.c#newcode566
drivers/md/dm-bht.c:566: if (depth == 0 && state != DM_BHT_ENTRY_VERIFIED) {
On 2011/04/25 16:40:42, Will Drewry wrote:
> This is a much more succinct special case :)

I plan to make even this go away.

http://codereview.chromium.org/6896044/diff/1/drivers/md/dm-bht.c#newcode570
drivers/md/dm-bht.c:570: depth--;
On 2011/04/25 16:40:42, Will Drewry wrote:
> I know unsigned underflow is defined, but it stil makes me squirm a bit. 
Could
> we do something like:
>   if (depth == 0 && ...) {
>   } else {
>     depth++;
>   }
>   for ( ; depth < bht->depth; ..) {
> 
> ?
> 
> The other option is to just add the one atomic_set call into the special case:
> 
> if (depth == 0 && ...) {
>   if (dm_bht_compute...)
>     goto mismatch;
>   atomic_set(&entry->state, DM_BHT_ENTRY_VERIFIED)
> }
> 
> then let the loop iterate from there?
>   

Yeah, that's much cleaner. Fixed.

http://codereview.chromium.org/6896044/diff/1/drivers/md/dm-bht.c#newcode586
drivers/md/dm-bht.c:586: DMERR("verify_path: failed to verify hash against
parent (d=%u,bi=%u)",
On 2011/04/25 16:40:42, Will Drewry wrote:
> nit: This should probably be a  DMERR_LIMIT().

Fixed.

http://codereview.chromium.org/6896044/diff/1/drivers/md/dm-bht.c#newcode821
drivers/md/dm-bht.c:821: for (depth = bht->depth - 1; (int)depth >= 0; depth--)
{
On 2011/04/25 16:40:42, Will Drewry wrote:
> Why not just walk up the tree since ordering doesn't matter (like in
> dm_bht_populate)?
> 
> unsigned int depth;
> for (depth = 0; depth < bht->depth; ++depth) {
>   struct dm_bht_entry *entry = dm_bht_get_entry(bht, depth, block_index);
>   if (atomic_read(&entry->state) < DM_BHT_ENTRY_READY)
>     return false;
> }
> return true;
> 
> ?

I have a cl in my queue to make populate also walk up. The benefit of going from
the leaves to the root is that you can short-circuit faster.

http://codereview.chromium.org/6896044/diff/1/drivers/md/dm-bht.c#newcode846
drivers/md/dm-bht.c:846: BUG_ON(block_index >= bht->block_count);
On 2011/04/25 16:40:42, Will Drewry wrote:
> hrm I was going to say that I prefer return -EIO (or better, -EINVAL), here to
> allow the caller to take evasive action (like changing kernels :), but I don't
> see a way for dm-verity to get the wrong block_index fed in based solely on
> malicious hash or block data.
> 
> [If we did ship with this as a programming bug, though, it might still be nice
> to have the user fall back over to the old kernel.  As is, this will just
leave
> them panic'ing and rebooting wily nily.]
> 
> What do you think?  As you know, I'm nervous about using BUG_ON anywhere in
this
> code versus giving dm-verity a chance to decide., so feel free to tell me I'm
> being too paranoid.

I like BUG_ON for coding errors because panics are the one thing that are on my
radar. If we ever hit this case there is a bug in the code which I'll see
quickly and then be able to fix. In all likelihood we'll hit the BUG_ON well
before the code ever gets out to users.

It also makes the code easier to read since you don't have to implement any sort
of recovery logic.

http://codereview.chromium.org/6896044/diff/1/drivers/md/dm-bht.c#newcode891
drivers/md/dm-bht.c:891: DMERR_LIMIT("Failed to verify block: %u (%d)",
block_index, r);
On 2011/04/25 16:40:42, Will Drewry wrote:
> Since there is a DMERR in the verify_path call, it'd make sense to me to
further
> gut this:
>   return dm_bht_verify_path(bht, block_index, pg, offset);
> 
> Then the next step can be to just kill it ... finally!

Fixed.

[Will Drewry, 2011-04-25 19:50:39]

LGTM with an open question about how we can short-circuit populate. (Do we
bundle all related request-block bios with barriers? Add extra, in-bht state for
all requests? ...)

thanks!

http://codereview.chromium.org/6896044/diff/1/drivers/md/dm-bht.c
File drivers/md/dm-bht.c (right):

http://codereview.chromium.org/6896044/diff/1/drivers/md/dm-bht.c#newcode821
drivers/md/dm-bht.c:821: for (depth = bht->depth - 1; (int)depth >= 0; depth--)
{
On 2011/04/25 17:44:21, Mandeep Singh Baines wrote:
> On 2011/04/25 16:40:42, Will Drewry wrote:
> > Why not just walk up the tree since ordering doesn't matter (like in
> > dm_bht_populate)?
> > 
> > unsigned int depth;
> > for (depth = 0; depth < bht->depth; ++depth) {
> >   struct dm_bht_entry *entry = dm_bht_get_entry(bht, depth, block_index);
> >   if (atomic_read(&entry->state) < DM_BHT_ENTRY_READY)
> >     return false;
> > }
> > return true;
> > 
> > ?
> 
> I have a cl in my queue to make populate also walk up. The benefit of going
from
> the leaves to the root is that you can short-circuit faster.

Does that help here?  Entries are not necessarily populated in a serial order. 
The calls are async to the block layer and if for some reason one request gets
serviced before another, we could end up inconsistent if we short-circuit.

Is there any sort of way we can guarantee the read-response ordering short of
relying on barriers or changing the underlying block device scheduling
algorithm?

http://codereview.chromium.org/6896044/diff/1/drivers/md/dm-bht.c#newcode846
drivers/md/dm-bht.c:846: BUG_ON(block_index >= bht->block_count);
On 2011/04/25 17:44:21, Mandeep Singh Baines wrote:
> On 2011/04/25 16:40:42, Will Drewry wrote:
> > hrm I was going to say that I prefer return -EIO (or better, -EINVAL), here
to
> > allow the caller to take evasive action (like changing kernels :), but I
don't
> > see a way for dm-verity to get the wrong block_index fed in based solely on
> > malicious hash or block data.
> > 
> > [If we did ship with this as a programming bug, though, it might still be
nice
> > to have the user fall back over to the old kernel.  As is, this will just
> leave
> > them panic'ing and rebooting wily nily.]
> > 
> > What do you think?  As you know, I'm nervous about using BUG_ON anywhere in
> this
> > code versus giving dm-verity a chance to decide., so feel free to tell me
I'm
> > being too paranoid.
> 
> I like BUG_ON for coding errors because panics are the one thing that are on
my
> radar. If we ever hit this case there is a bug in the code which I'll see
> quickly and then be able to fix. In all likelihood we'll hit the BUG_ON well
> before the code ever gets out to users.
> 
> It also makes the code easier to read since you don't have to implement any
sort
> of recovery logic.

Well that latter bit was kind of my point, but as long as we test the recovery
flow, we should always walk every available block since it does a dd over the
/dev/dm-0.  It might be worth adding an autotest for this.

[Mandeep Singh Baines, 2011-04-25 20:42:39]

wad@chromium.org (wad@chromium.org) wrote:
> LGTM with an open question about how we can short-circuit populate. (Do we
> bundle all related request-block bios with barriers? Add extra,
> in-bht state for
> all requests? ...)
> 

In the CL, populate is down leave to root and stops as soon as
a VERIFIED node is reached.

> thanks!
> 
> 
> http://codereview.chromium.org/6896044/diff/1/drivers/md/dm-bht.c
> File drivers/md/dm-bht.c (right):
> 
> http://codereview.chromium.org/6896044/diff/1/drivers/md/dm-bht.c#newcode821
> drivers/md/dm-bht.c:821: for (depth = bht->depth - 1; (int)depth >= 0;
> depth--) {
> On 2011/04/25 17:44:21, Mandeep Singh Baines wrote:
> >On 2011/04/25 16:40:42, Will Drewry wrote:
> >> Why not just walk up the tree since ordering doesn't matter (like in
> >> dm_bht_populate)?
> >>
> >> unsigned int depth;
> >> for (depth = 0; depth < bht->depth; ++depth) {
> >>   struct dm_bht_entry *entry = dm_bht_get_entry(bht, depth,
> block_index);
> >>   if (atomic_read(&entry->state) < DM_BHT_ENTRY_READY)
> >>     return false;
> >> }
> >> return true;
> >>
> >> ?
> 
> >I have a cl in my queue to make populate also walk up. The benefit of
> going from
> >the leaves to the root is that you can short-circuit faster.
> 
> Does that help here?  Entries are not necessarily populated in a serial
> order.  The calls are async to the block layer and if for some reason
> one request gets serviced before another, we could end up inconsistent
> if we short-circuit.
> 

They aren't populated but they are verified in order.

> Is there any sort of way we can guarantee the read-response ordering
> short of relying on barriers or changing the underlying block device
> scheduling algorithm?
> 
> http://codereview.chromium.org/6896044/diff/1/drivers/md/dm-bht.c#newcode846
> drivers/md/dm-bht.c:846: BUG_ON(block_index >= bht->block_count);
> On 2011/04/25 17:44:21, Mandeep Singh Baines wrote:
> >On 2011/04/25 16:40:42, Will Drewry wrote:
> >> hrm I was going to say that I prefer return -EIO (or better,
> -EINVAL), here to
> >> allow the caller to take evasive action (like changing kernels :),
> but I don't
> >> see a way for dm-verity to get the wrong block_index fed in based
> solely on
> >> malicious hash or block data.
> >>
> >> [If we did ship with this as a programming bug, though, it might
> still be nice
> >> to have the user fall back over to the old kernel.  As is, this will
> just
> >leave
> >> them panic'ing and rebooting wily nily.]
> >>
> >> What do you think?  As you know, I'm nervous about using BUG_ON
> anywhere in
> >this
> >> code versus giving dm-verity a chance to decide., so feel free to
> tell me I'm
> >> being too paranoid.
> 
> >I like BUG_ON for coding errors because panics are the one thing that
> are on my
> >radar. If we ever hit this case there is a bug in the code which I'll
> see
> >quickly and then be able to fix. In all likelihood we'll hit the
> BUG_ON well
> >before the code ever gets out to users.
> 
> >It also makes the code easier to read since you don't have to
> implement any sort
> >of recovery logic.
> 
> Well that latter bit was kind of my point, but as long as we test the
> recovery flow, we should always walk every available block since it does
> a dd over the /dev/dm-0.  It might be worth adding an autotest for this.
> 
> http://codereview.chromium.org/6896044/

[Paul T, 2011-04-26 18:29:54]

LGTM - remarkable reduction in complexity.

http://codereview.chromium.org/6896044/diff/5001/drivers/md/dm-bht.c
File drivers/md/dm-bht.c (right):

http://codereview.chromium.org/6896044/diff/5001/drivers/md/dm-bht.c#newcode887
drivers/md/dm-bht.c:887: return  dm_bht_verify_path(bht, block_index, pg,
offset);
Can dm_bht_verify_block go away and be replaced to calls to dm_bht_verity_path?

[Mandeep Singh Baines, 2011-04-26 23:45:22]

taysom@chromium.org (taysom@chromium.org) wrote:
> LGTM - remarkable reduction in complexity.
> 
> 
> http://codereview.chromium.org/6896044/diff/5001/drivers/md/dm-bht.c
> File drivers/md/dm-bht.c (right):
> 
>
http://codereview.chromium.org/6896044/diff/5001/drivers/md/dm-bht.c#newcode887
> drivers/md/dm-bht.c:887: return  dm_bht_verify_path(bht, block_index,
> pg, offset);
> Can dm_bht_verify_block go away and be replaced to calls to
> dm_bht_verity_path?
> 

Yes it can. I plan to do this is a future CL. Didn't want to do too
much in one CL.

> http://codereview.chromium.org/6896044/