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

drivers/md/dm-bht.c

  /*
  * Copyright (C) 2010 The Chromium OS Authors <chromium-os-dev@chromium.org>
  *
  * Device-Mapper block hash tree interface.
  * See Documentation/device-mapper/dm-bht.txt for details.
  *
  * This file is released under the GPL.
  */
 
 #include <asm/atomic.h>
@@ skipping 675 matching lines @@
         while (depth > 0) {
                 u8 digest[DM_BHT_MAX_DIGEST_SIZE];
                 struct dm_bht_entry *parent;
                 struct page *page;
                 u8 *node;
                 int state;
 
                 DMDEBUG("verify_path for b=%u on d=%d", block_index, depth);
                 state = atomic_read(&entry->state);
                 if (state == DM_BHT_ENTRY_VERIFIED) {
-                        DMDEBUG("verify_path node %u is verified in parent",
+                        DMDEBUG("verify_path node %u is verified to root",
                                 block_index);
-                        entry = dm_bht_get_entry(bht, --depth, block_index);
-                        continue;
+                        break;

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

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.

                 } else if (state <= DM_BHT_ENTRY_ERROR) {
                         DMCRIT("entry(d=%u,b=%u) is in an error state: %d",
                                depth, block_index, state);
                         DMCRIT("verification is not possible");
                         goto mismatch;
                 } else if (state <= DM_BHT_ENTRY_PENDING) {
                         DMERR("entry not ready for verify: d=%u,b=%u",
                               depth, block_index);
                         goto mismatch;
                 }
 
                 /* We need to check that this entry matches the expected
                  * hash in the parent->nodes.
                  */
                 parent = dm_bht_get_entry(bht, depth - 1, block_index);
                 /* This call is only safe if all nodes along the path
                  * are already populated (i.e. READY) via dm_bht_populate.
                  */
                 BUG_ON(atomic_read(&parent->state) < DM_BHT_ENTRY_READY);

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

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 :)

                 node = dm_bht_get_node(bht, parent, depth, block_index);
                 page = virt_to_page(entry->nodes);
 
                 if (dm_bht_compute_hash(bht, page, digest) ||
                     dm_bht_compare_hash(bht, digest, node)) {
                         DMERR("failed to verify entry's hash against parent "
                               "(d=%u,bi=%u)", depth, block_index);
                         goto mismatch;
                 }
 
-                atomic_cmpxchg(&entry->state,
-                               DM_BHT_ENTRY_READY,
-                               DM_BHT_ENTRY_VERIFIED);
-
                 entry = parent;
                 depth--;
         }
+        /* Mark path to leaf as verified. */
+        for (; depth < bht->depth; depth++) {

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

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 :)

+                entry = dm_bht_get_entry(bht, depth, block_index);
+                atomic_cmpxchg(&entry->state,
+                               DM_BHT_ENTRY_READY,
+                               DM_BHT_ENTRY_VERIFIED);
+        }
 
         return 0;
 
 mismatch:
         return DM_BHT_ENTRY_ERROR_MISMATCH;
 }
 
 /**
  * dm_bht_store_block - sets a given block's hash in the tree
  * @bht:        pointer to a dm_bht_create()d bht
@@ skipping 480 matching lines @@
                 DMERR("no root digest exists to export");
                 if (available > 0)
                         *hexdigest = 0;
                 return -1;
         }
         dm_bht_bin_to_hex(bht->root_digest, hexdigest, bht->digest_size);
         return 0;
 }
 EXPORT_SYMBOL(dm_bht_root_hexdigest);