CHROMIUM: verity: short circuit once you hit a verified node

CHROMIUM: verity: short circuit once you hit a verified node

Since we set the VERIFIED bits top-down we can short circuit once
we hit a VERIFIED node.

BUG=9752
TEST=Ran tests in verity.git. Ran platform_DMVerityCorruption on H/W.

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

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

[Will Drewry, 2011-03-10 22:42:50]

Awesome.  I think only one tweak and it'll be good to go.

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

http://codereview.chromium.org/6670008/diff/1/drivers/md/dm-bht.c#newcode698
drivers/md/dm-bht.c:698: break;
Nice! I *think* this works :)

You're going to want to increment depth here though. E.g., 
 depth++;
 break;

If not, you'll always do one extra atomic_cmpxchg on the already verified node
in the for loop at the bottom.

http://codereview.chromium.org/6670008/diff/1/drivers/md/dm-bht.c#newcode717
drivers/md/dm-bht.c:717: BUG_ON(atomic_read(&parent->state) <
DM_BHT_ENTRY_READY);
unrelated note for either of us later :)

we can probably do:
  state = atomic_read(&parent->state);
  BUG_ON(state < DM_BHT_ENTRY_READY);

then before entering the while loop:
  struct dm_bht_entry *entry = dm_bht_get_entry(bht, depth, block_index);
+   int state = atomic_read(&entry->state);

Then remove like 694 and 691.  It'll mean one atomic_read per entry which would
be good :)

http://codereview.chromium.org/6670008/diff/1/drivers/md/dm-bht.c#newcode732
drivers/md/dm-bht.c:732: for (; depth < bht->depth; depth++) {
Interesting tradeoffs here.  If we did root-to-leaf verification, then we could
potentially get benefits from parallel verifiers.  However, we'd not get the
benefit of being able to short-circuit _anywhere_ in a tree like we do with
leaf-to-root.  With this, we can short-circuit at any common node in the tree
(awesome), but we have to do the extra downward traversal from that common
point.

 Seems like the little bit of extra math and memory dereferencing is worth it
even though two back to back loops makes me cringe :)

At least a volatile read on our platform isn't that expensive :)

[Paul T, 2011-03-11 00:13:42]

LGTM

[Mandeep Singh Baines, 2011-03-11 01:00:32]

Fixed. Re-tested. PTAL.

[Will Drewry, 2011-03-11 02:51:35]

LGTM

Thanks!