verity: short circuit once you hit a verified node

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 673 matching lines @@
         struct dm_bht_entry *entry = dm_bht_get_entry(bht, depth, block_index);
 
         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);
+                /* TODO(msb,wad): would be nice to avoid two atomic reads */

[Paul T, 2011/03/23 17:19:28]

I'd like to understand this comment better. From what I understand, atomic read
is just a volatile read. So once the value is in cache, the second read should
be fast or is something else going on?

                 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;
+                        depth++; /* avoid an extra cmpxchg */
+                        break;
                 } 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);
                 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++) {
+                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);