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);
+
+        BUG_ON(index >= level->count);
+
+        return &level->entries[index];
+}
+
+static inline u8 *dm_bht_get_node(struct dm_bht *bht,
+                                  struct dm_bht_entry *parent,

[Will Drewry, 2010/11/30 19:30:27]

does it make sense to call this 'parent' and not just 'entry' since all this
does is give the node from a given entry.  I worry using the variable named
parent makes it slightly more confusing.

[Mandeep Singh Baines, 2010/11/30 23:11:51]

Agree. Fixed.

+                                  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);
+
+        BUG_ON(index >= level->count);
+
+        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;
+                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);
+                        entry = dm_bht_get_entry(bht, --depth, block_index);
+                        continue;
+                } 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;

[Will Drewry, 2010/11/30 19:30:27]

This is counter to the current kernel style guidelines.  At present, it is
highly recommended to never exit a function from the body but to use gotos or
breaks in a loop.  That's the only reason for ret = 1; break; in the original
version.

If you'd like to not need a ret variable, the postscript could look like:

  }  // end while loop 
  return !(depth == 0);
mismatch:
  return DM_BHT_ENTRY_ERROR_MISMATCH;

                 } 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);
+                BUG_ON(atomic_read(&parent->state) < DM_BHT_ENTRY_READY);

[Will Drewry, 2010/11/30 19:30:27]

It'd be worth updating the comment above the function. I know it is sparse as
is, but it'd be good to indicate that this is only safe to call when the path to
be verified is fully populated (as per dm_bht_populate).

+                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);

[Will Drewry, 2010/11/30 19:30:27]

Not a huge fan of losing the debugging insight, but I think it's okay.  I've had
to use d, ei, p, and pnode in the past, but hopefully that level of debugging is
in the past :)

[Mandeep Singh Baines, 2010/11/30 23:11:51]

Its not totally lost. You should be able to derive the rest from depth and
block_index.

+                        return DM_BHT_ENTRY_ERROR_MISMATCH;

[Will Drewry, 2010/11/30 19:30:27]

As per the comment on the return earlier, this could just be
  goto 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)

[Will Drewry, 2010/11/30 19:30:27]

We could also make this a single call too:

void dm_bht_mark_verified(struct dm_bht_entry *entry) {
  if (bht->verify_mode != DM_BHT_FULL_REVERIFY)
    atomic_cmpxchg(...);
}

(And could even return the cmpxchg value to know if it worked or if something
changed while we were operting on the tree :) 

[Mandeep Singh Baines, 2010/11/30 23:11:51]

Could we now just:

BUG_ON(atomic_read(&entry->state) < DM_BHT_ENTRY_READY);
atomic_set(&entry->state, DM_BHT_ENTRY_VERIFIED);

But is it OK if I defer changing this till a future CL?

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