CHROMIUM: verity: Cleanup dm_bht_verify_path.

CHROMIUM: verity: Cleanup dm_bht_verify_path.

The whole function now fits inside my emacs window at one time!

BUG=n0ne
TEST=Unit tests pass. Booted.

Change-Id: I6f186c179021faac62e6e8fc5ea2eb560a22c18c

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

[Will Drewry, 2010-11-29 17:13:13]

There's some breakage in here from my last change (not horrible, but not great)
and there's a new short-circuiting that could be better.

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

http://codereview.chromium.org/5361004/diff/1/dm-bht.c#newcode164
dm-bht.c:164: 
I'd like to bring back the BUG_ON(index >= level->count) as it has caught bugs
in the past.  What do you think?

(Note, dm_bht_get_level doesn't do a BUG_ON for depth, but that had so far not
been a problem, though we could consider it later if needed.)

http://codereview.chromium.org/5361004/diff/1/dm-bht.c#newcode174
dm-bht.c:174: 
Same here!

http://codereview.chromium.org/5361004/diff/1/dm-bht.c#newcode722
dm-bht.c:722: struct dm_bht_entry *parent;
In the past, I used to avoid setting up scoped variables inside loops to avoid
the associated overhead.  I don't know if that's still a problem with modern
gcc, but it'd be worth checking what the performance numbers and generated
assembly look like with this change (in general :)

http://codereview.chromium.org/5361004/diff/1/dm-bht.c#newcode732
dm-bht.c:732: break;
Why is this a break and not a continue now?  Just because this node is verified
doesn't mean the whole path was.

For instance, this could pass the point here, then verify below, then in the
next level it could see DM_BHT_ENTRY_PENDING and bail out.  While that shouldn't
happen, dm-bht can't guarantee the state will always be valid.  If it bails on
VERIFIED, than an error or pending further up the tree will be ignored (after
the first error occurs).

Ideally, it shouldn't matter, but I'm not sure I've fully thought through the
impact of short-circuiting at the first verified level.  (For instances, any
parallel verifications will pass immediately even if this one is still verifying
up the tree.)

http://codereview.chromium.org/5361004/diff/1/dm-bht.c#newcode753
dm-bht.c:753: parent = dm_bht_get_entry(bht, depth - 1, block_index);
So I just noticed a problem with the last change I landed and continued here. 
We don't check the parent state.  The parent needs to be check if it is ERROR or
PENDING prior to attempting the verification.  If not, it could read in to an
unallocated node, an error node, or a half copied node.

That was why I had the verify_path reversed before. It was so I could reuse the
state= checks without needing to duplicate them.  We'll now need to check at
least that parent_state >= READY I think.

Or just pad the tree to not do the parent check and start at depth=0 like ti was
before :p

Is there a cleaner way to do this while avoiding more code duplication?

[Mandeep Singh Baines, 2010-11-29 20:20:38]

Fixed. PTAL.

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

http://codereview.chromium.org/5361004/diff/1/dm-bht.c#newcode164
dm-bht.c:164: 
On 2010/11/29 17:13:13, Will Drewry wrote:
> I'd like to bring back the BUG_ON(index >= level->count) as it has caught bugs
> in the past.  What do you think?
> 
> (Note, dm_bht_get_level doesn't do a BUG_ON for depth, but that had so far not
> been a problem, though we could consider it later if needed.)

Fixed.

http://codereview.chromium.org/5361004/diff/1/dm-bht.c#newcode174
dm-bht.c:174: 
On 2010/11/29 17:13:13, Will Drewry wrote:
> Same here!

Fixed.

http://codereview.chromium.org/5361004/diff/1/dm-bht.c#newcode722
dm-bht.c:722: struct dm_bht_entry *parent;
On 2010/11/29 17:13:13, Will Drewry wrote:
> In the past, I used to avoid setting up scoped variables inside loops to avoid
> the associated overhead.  I don't know if that's still a problem with modern
> gcc, but it'd be worth checking what the performance numbers and generated
> assembly look like with this change (in general :)
http://stackoverflow.com/questions/982963/is-there-any-overhead-to-declaring-...

http://codereview.chromium.org/5361004/diff/1/dm-bht.c#newcode732
dm-bht.c:732: break;
On 2010/11/29 17:13:13, Will Drewry wrote:
> Why is this a break and not a continue now?  Just because this node is
verified
> doesn't mean the whole path was.
> 
> For instance, this could pass the point here, then verify below, then in the
> next level it could see DM_BHT_ENTRY_PENDING and bail out.  While that
shouldn't
> happen, dm-bht can't guarantee the state will always be valid.  If it bails on
> VERIFIED, than an error or pending further up the tree will be ignored (after
> the first error occurs).
> 
> Ideally, it shouldn't matter, but I'm not sure I've fully thought through the
> impact of short-circuiting at the first verified level.  (For instances, any
> parallel verifications will pass immediately even if this one is still
verifying
> up the tree.)

Fixed.

http://codereview.chromium.org/5361004/diff/1/dm-bht.c#newcode753
dm-bht.c:753: parent = dm_bht_get_entry(bht, depth - 1, block_index);
On 2010/11/29 17:13:13, Will Drewry wrote:
> So I just noticed a problem with the last change I landed and continued here. 
> We don't check the parent state.  The parent needs to be check if it is ERROR
or
> PENDING prior to attempting the verification.  If not, it could read in to an
> unallocated node, an error node, or a half copied node.
> 
> That was why I had the verify_path reversed before. It was so I could reuse
the
> state= checks without needing to duplicate them.  We'll now need to check at
> least that parent_state >= READY I think.
> 
> Or just pad the tree to not do the parent check and start at depth=0 like ti
was
> before :p
> 
> Is there a cleaner way to do this while avoiding more code duplication?

Fixed per discussion over chat.

[Will Drewry, 2010-11-30 19:30:27]

A few style and naming nits (and some future ideas).

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

http://codereview.chromium.org/5361004/diff/5001/dm-bht.c#newcode171
dm-bht.c:171: struct dm_bht_entry *parent,
does it make sense to call this 'parent' and not just 'entry' since all this
does is give the node from a given entry.  I worry using the variable named
parent makes it slightly more confusing.

http://codereview.chromium.org/5361004/diff/5001/dm-bht.c#newcode743
dm-bht.c:743: return 1;
This is counter to the current kernel style guidelines.  At present, it is
highly recommended to never exit a function from the body but to use gotos or
breaks in a loop.  That's the only reason for ret = 1; break; in the original
version.

If you'd like to not need a ret variable, the postscript could look like:

  }  // end while loop 
  return !(depth == 0);
mismatch:
  return DM_BHT_ENTRY_ERROR_MISMATCH;

http://codereview.chromium.org/5361004/diff/5001/dm-bht.c#newcode760
dm-bht.c:760: BUG_ON(atomic_read(&parent->state) < DM_BHT_ENTRY_READY);
It'd be worth updating the comment above the function. I know it is sparse as
is, but it'd be good to indicate that this is only safe to call when the path to
be verified is fully populated (as per dm_bht_populate).

http://codereview.chromium.org/5361004/diff/5001/dm-bht.c#newcode767
dm-bht.c:767: "(d=%u,bi=%u)", depth, block_index);
Not a huge fan of losing the debugging insight, but I think it's okay.  I've had
to use d, ei, p, and pnode in the past, but hopefully that level of debugging is
in the past :)

http://codereview.chromium.org/5361004/diff/5001/dm-bht.c#newcode768
dm-bht.c:768: return DM_BHT_ENTRY_ERROR_MISMATCH;
As per the comment on the return earlier, this could just be
  goto mismatch;

http://codereview.chromium.org/5361004/diff/5001/dm-bht.c#newcode771
dm-bht.c:771: if (bht->verify_mode != DM_BHT_FULL_REVERIFY)
We could also make this a single call too:

void dm_bht_mark_verified(struct dm_bht_entry *entry) {
  if (bht->verify_mode != DM_BHT_FULL_REVERIFY)
    atomic_cmpxchg(...);
}

(And could even return the cmpxchg value to know if it worked or if something
changed while we were operting on the tree :)

[Mandeep Singh Baines, 2010-11-30 23:11:51]

Fixed. PTAL.

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

http://codereview.chromium.org/5361004/diff/5001/dm-bht.c#newcode171
dm-bht.c:171: struct dm_bht_entry *parent,
On 2010/11/30 19:30:27, Will Drewry wrote:
> does it make sense to call this 'parent' and not just 'entry' since all this
> does is give the node from a given entry.  I worry using the variable named
> parent makes it slightly more confusing.

Agree. Fixed.

http://codereview.chromium.org/5361004/diff/5001/dm-bht.c#newcode767
dm-bht.c:767: "(d=%u,bi=%u)", depth, block_index);
On 2010/11/30 19:30:27, Will Drewry wrote:
> Not a huge fan of losing the debugging insight, but I think it's okay.  I've
had
> to use d, ei, p, and pnode in the past, but hopefully that level of debugging
is
> in the past :)

Its not totally lost. You should be able to derive the rest from depth and
block_index.

http://codereview.chromium.org/5361004/diff/5001/dm-bht.c#newcode771
dm-bht.c:771: if (bht->verify_mode != DM_BHT_FULL_REVERIFY)
On 2010/11/30 19:30:27, Will Drewry wrote:
> We could also make this a single call too:
> 
> void dm_bht_mark_verified(struct dm_bht_entry *entry) {
>   if (bht->verify_mode != DM_BHT_FULL_REVERIFY)
>     atomic_cmpxchg(...);
> }
> 
> (And could even return the cmpxchg value to know if it worked or if something
> changed while we were operting on the tree :) 

Could we now just:

BUG_ON(atomic_read(&entry->state) < DM_BHT_ENTRY_READY);
atomic_set(&entry->state, DM_BHT_ENTRY_VERIFIED);

But is it OK if I defer changing this till a future CL?

[Mandeep Singh Baines, 2010-12-01 21:14:58]

ping

[Will Drewry, 2010-12-01 21:45:59]

LGTM with one optional nit.

http://codereview.chromium.org/5361004/diff/9001/dm-bht.c
File dm-bht.c (right):

http://codereview.chromium.org/5361004/diff/9001/dm-bht.c#newcode731
dm-bht.c:731: DMDEBUG("verify_path for bi=%u on d=%d", block_index, depth);
nit: want to change bi to just b to match your other debug message chnges below?