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

drivers/md/dm-bht.c

Index: drivers/md/dm-bht.c
diff --git a/drivers/md/dm-bht.c b/drivers/md/dm-bht.c
index 46b03c09702bd31ad8319228c24112164c31cac7..e83985e6de714a3c84d5ad0d78541813632cb929 100644
--- a/drivers/md/dm-bht.c
+++ b/drivers/md/dm-bht.c
@@ -693,10 +693,9 @@ static int dm_bht_verify_path(struct dm_bht *bht, unsigned int block_index)
 		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);
@@ -726,12 +725,15 @@ static int dm_bht_verify_path(struct dm_bht *bht, unsigned int block_index)
 			goto mismatch;
 		}
 
+		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);
-
-		entry = parent;
-		depth--;
 	}
 
 	return 0;