CHROMIUM: verity: remove short-circuiting of verify_path

CHROMIUM: verity: remove short-circuiting of verify_path

This removes the optimization which short-circuited verify_path. The net
result is the addition of a few cycles and the removal of a few so zero
or negligible cycles added.

The main benefit is the removal of the one of the larget comments in the
code. Ran BootPerfServer to verify no noticable overhead added.

Before:

  seconds_power_on_to_login                                       8.44

After:

  seconds_power_on_to_login                                       8.4

This result is within variance.

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

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

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

[Will Drewry, 2011-03-09 19:51:47]

nack

That test isn't representative of general behavior.  In particular, our existing
dm-bht tree is not deep.  So the short-circuiting gets us no benefit.  However,
a direct side effect of the goal you are moving toward is to require a deeper
tree.  Each level in the tree will now require an atomic_read() and more stack
frame setup and teardown depending on what gcc is doing.

When this short-circuit was first added and I was testing with variable depth
trees, I did see significant improvements.  However, with the current code, that
may not be the case.  We can remove it if the benefit with a 3 to 5 depth tree
is really inconsequential, but I'd want that in TEST=, not just a test of what
we do on the active system -- especially since we're already talking about
changing it so soon.

thanks!
will

[Paul T, 2011-03-09 20:44:34]

LGTM

[Mandeep Singh Baines, 2011-03-09 21:30:08]

PTAL (comments below)

On 2011/03/09 19:51:47, Will Drewry wrote:
> nack
> 
> That test isn't representative of general behavior.  In particular, our
existing
> dm-bht tree is not deep.  So the short-circuiting gets us no benefit. 
However,
> a direct side effect of the goal you are moving toward is to require a deeper
> tree.  Each level in the tree will now require an atomic_read() and more stack
> frame setup and teardown depending on what gcc is doing.
> 
> When this short-circuit was first added and I was testing with variable depth
> trees, I did see significant improvements.  However, with the current code,
that
> may not be the case.  We can remove it if the benefit with a 3 to 5 depth tree
> is really inconsequential, but I'd want that in TEST=, not just a test of what
> we do on the active system -- especially since we're already talking about
> changing it so soon.
> 

D'oh. You're comments here are right on. I misinterpreted what was going on with
the code. For some reason, I kept thinking that the code was a short-circuit for
the bht->depth == 1 case. Its not.

I was seeing:

if (entry_state == DM_BHT_ENTRY_VERIFIED && bht->depth == 1) 

When the code is actually:

if (entry_state == DM_BHT_ENTRY_VERIFIED || bht->depth == 1) 

That being case. The existing code and comment are actually incorrect unless I'm
missing something. The tree is verified bottom up so there is no guarantee that
the entire path has been verified. Verification could have failed on the way up
somewhere.

This can actually never happen if you panic on error, error_behavior =
BEHAVIOR_PANIC but dm-bht.c has no way of knowing that. We could fix that by
propagating the error behaviour down.

You actually pointed this out to me in an earlier review when I tried to
short-circuit in verify_path;)

http://codereview.chromium.org/5361004/diff/1/dm-bht.c#newcode732

"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.) "

So I'd like to propose removing it now and adding it back later (in verify_path)
if we need it for bht->depth > 0 performance. That would mean propagating the
error_behaviour at create() time.

What do you think?

> thanks!
> will

[Will Drewry, 2011-03-09 21:38:35]

On 2011/03/09 21:30:08, Mandeep Singh Baines wrote:
> PTAL (comments below)
> 
> On 2011/03/09 19:51:47, Will Drewry wrote:
> > nack
> > 
> > That test isn't representative of general behavior.  In particular, our
> existing
> > dm-bht tree is not deep.  So the short-circuiting gets us no benefit. 
> However,
> > a direct side effect of the goal you are moving toward is to require a
deeper
> > tree.  Each level in the tree will now require an atomic_read() and more
stack
> > frame setup and teardown depending on what gcc is doing.
> > 
> > When this short-circuit was first added and I was testing with variable
depth
> > trees, I did see significant improvements.  However, with the current code,
> that
> > may not be the case.  We can remove it if the benefit with a 3 to 5 depth
tree
> > is really inconsequential, but I'd want that in TEST=, not just a test of
what
> > we do on the active system -- especially since we're already talking about
> > changing it so soon.
> > 
> 
> D'oh. You're comments here are right on. I misinterpreted what was going on
with
> the code. For some reason, I kept thinking that the code was a short-circuit
for
> the bht->depth == 1 case. Its not.
> 
> I was seeing:
> 
> if (entry_state == DM_BHT_ENTRY_VERIFIED && bht->depth == 1) 
> 
> When the code is actually:
> 
> if (entry_state == DM_BHT_ENTRY_VERIFIED || bht->depth == 1) 
> 
> That being case. The existing code and comment are actually incorrect unless
I'm
> missing something. The tree is verified bottom up so there is no guarantee
that
> the entire path has been verified. Verification could have failed on the way
up
> somewhere.
> 
> This can actually never happen if you panic on error, error_behavior =
> BEHAVIOR_PANIC but dm-bht.c has no way of knowing that. We could fix that by
> propagating the error behaviour down.
> 
> You actually pointed this out to me in an earlier review when I tried to
> short-circuit in verify_path;)
> 
> http://codereview.chromium.org/5361004/diff/1/dm-bht.c#newcode732
> 
> "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.) "
> 
> So I'd like to propose removing it now and adding it back later (in
verify_path)
> if we need it for bht->depth > 0 performance. That would mean propagating the
> error_behaviour at create() time.
> 
> What do you think?

Ouch. Yeah we should remove it right now since

http://git.chromium.org/gitweb/?p=kernel.git;a=commitdiff;h=b6489dceeea2e4034...

introduced races in the short-circuit logic because the inverted verify_path
provided transitive guarantees which we've since lost :/

> 
> > thanks!
> > will

[Will Drewry, 2011-03-09 22:52:02]

For clarity, LGTM. Then we need to fix this up after the fact :)