CHROMIUM: verity: Cleanup dm_bht_verify_path.

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 137 matching lines @@
         return leaf >> dm_bht_get_level_shift(bht, depth);
 }
 
 static __always_inline u8 *dm_bht_node(struct dm_bht *bht,
                                        struct dm_bht_entry *entry,
                                        unsigned int node_index)
 {
         return &entry->nodes[node_index * bht->digest_size];
 }
 
+static inline struct dm_bht_entry *dm_bht_get_entry(struct dm_bht *bht,
+                                                    unsigned int depth,
+                                                    unsigned int block_index)
+{
+        unsigned int index = dm_bht_index_at_level(bht, depth, block_index);
+        struct dm_bht_level *level = dm_bht_get_level(bht, depth);
+

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

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

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

Fixed.

+        return &level->entries[index];
+}
+
+static inline u8 *dm_bht_get_node(struct dm_bht *bht,
+                                  struct dm_bht_entry *parent,
+                                  unsigned int depth,
+                                  unsigned int block_index)
+{
+        unsigned int index = dm_bht_index_at_level(bht, depth, block_index);
+

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

Same here!

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

Fixed.

+        return dm_bht_node(bht, parent, index % bht->node_count);
+}
+
 
 /*-----------------------------------------------
  * Implementation functions
  *-----------------------------------------------*/
 
 static int dm_bht_initialize_entries(struct dm_bht *bht);
 
 static int dm_bht_read_callback_stub(void *ctx, sector_t start, u8 *dst,
                                      sector_t count,
                                      struct dm_bht_entry *entry);
@@ skipping 519 matching lines @@
         atomic_set(&bht->root_state, DM_BHT_ENTRY_VERIFIED);
         return 0;
 }
 
 /* dm_bht_verify_path
  * Verifies the path from block_index to depth=0. Returns 0 on ok.
  */
 static int dm_bht_verify_path(struct dm_bht *bht, unsigned int block_index,
                               dm_bht_compare_cb compare_cb)
 {
-        unsigned int depth = bht->depth;
-        struct dm_bht_level *level;
-        struct dm_bht_entry *entry;
-        struct dm_bht_entry *parent = NULL;
-        u8 *node;
-        unsigned int node_index;
-        unsigned int entry_index;
-        unsigned int parent_index = 0;  /* for logging */
-        struct hash_desc *hash_desc;
-        int state;
-        int ret = 0;
+        unsigned int depth = bht->depth - 1;
+        struct dm_bht_entry *entry = dm_bht_get_entry(bht, depth, block_index);
+        struct hash_desc *hash_desc = &bht->hash_desc[smp_processor_id()];
 
-        hash_desc = &bht->hash_desc[smp_processor_id()];
-        while (depth-- > 0) {
-                level = dm_bht_get_level(bht, depth);
-                entry_index = dm_bht_index_at_level(bht, depth, block_index);
-                DMDEBUG("verify_path for bi=%u on d=%d ei=%u (max=%u)",
-                        block_index, depth, entry_index, level->count);
-                BUG_ON(entry_index >= level->count);
-                entry = &level->entries[entry_index];
+        while (depth > 0) {
+                struct dm_bht_entry *parent;

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

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

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

http://stackoverflow.com/questions/982963/is-there-any-overhead-to-declaring-...

+                u8 *node;
+                int state;
 
-                /* Catch any existing errors */
+                DMDEBUG("verify_path for bi=%u on d=%d", block_index, depth);
+
                 state = atomic_read(&entry->state);
-                if (state <= DM_BHT_ENTRY_ERROR) {
-                        DMCRIT("entry(d=%u,idx=%u) is in an error state: %d",
-                               depth, entry_index, state);
+                if (state == DM_BHT_ENTRY_VERIFIED) {
+                        DMDEBUG("verify_path node %u is verified in parent",
+                                block_index);
+                        break;

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

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

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

Fixed.

+                } 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");
-                        ret = 1;
-                        break;
+                        return 1;
                 } else if (state <= DM_BHT_ENTRY_PENDING) {
-                        DMERR("entry not ready for verify: d=%u,e=%u",
-                              depth, entry_index);
-                        ret = 1;
-                        break;
+                        DMERR("entry not ready for verify: d=%u,b=%u",
+                              depth, block_index);
+                        return 1;
                 }
 
                 /* At depth 0, we're at the page underneath the root node and
                  * leave its validation to a separate path.
                  */
                 if (depth == 0)
                         break;
 
-                /* Grab the parent entry where the current entry hash is. */
-                parent_index = dm_bht_index_at_level(bht, depth - 1,
-                                                     block_index);
-                level = dm_bht_get_level(bht, depth - 1);
-                BUG_ON(parent_index >= level->count);
-                parent = &level->entries[parent_index];
-
-                /* Because we are one level down, the node_index into the
-                 * the parent's node list modulo the number of nodes.
-                 */
-                node_index = entry_index % bht->node_count;
-
-                /* If the nodes in entry have already been checked against the
-                 * parent, then we're done.
-                 */
-                if (state == DM_BHT_ENTRY_VERIFIED) {
-                        DMDEBUG("verify_path node %u is verified in parent %u",
-                                node_index, parent_index);
-                        /* If this entry has been checked, move along. */
-                        continue;
-                }
-
                 /* We need to check that this entry matches the expected
                  * hash in the parent->nodes.
                  */
-                node = dm_bht_node(bht, parent, node_index);
-                DMDEBUG("verify_path: node is not verified in parent "
-                        "(d=%u,ei=%u,p=%u,pnode=%u)",
-                        depth, entry_index, parent_index, node_index);
+                parent = dm_bht_get_entry(bht, depth - 1, block_index);

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

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 per discussion over chat.

+                node = dm_bht_get_node(bht, parent, depth, block_index);
 
                 if (dm_bht_compute_and_compare(bht, hash_desc,
                                                virt_to_page(entry->nodes),
                                                node, compare_cb)) {
                         DMERR("failed to verify entry's hash against parent "
-                              "(d=%u,ei=%u,p=%u,pnode=%u)",
-                              depth, entry_index, parent_index, node_index);
-                        ret = DM_BHT_ENTRY_ERROR_MISMATCH;
-                        break;
+                              "(d=%u,bi=%u)", depth, block_index);
+                        return DM_BHT_ENTRY_ERROR_MISMATCH;
                 }
 
-                /* Instead of keeping a bitmap of which children have been
-                 * checked, this data is kept in the child state. If full
-                 * reverifies have been set, then no intermediate entry/node is
-                 * ever marked as verified.
-                 */
                 if (bht->verify_mode != DM_BHT_FULL_REVERIFY)
                         atomic_cmpxchg(&entry->state,
                                        DM_BHT_ENTRY_READY,
                                        DM_BHT_ENTRY_VERIFIED);
+
+                entry = parent;
+                depth--;
         }
-        return ret;
+
+        return 0;
 }
 
 /**
  * dm_bht_store_block - sets a given block's hash in the tree
  * @bht:        pointer to a dm_bht_create()d bht
  * @block_index:numeric index of the block in the tree
  * @digest:     array of u8s containing the digest of length @bht->digest_size
  *
  * Returns 0 on success, >0 when data is pending, and <0 when a IO or other
  * error has occurred.
@@ skipping 502 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);