verity: handle trees with an odd node count correctly

dm-bht_unittest.cc

Index: dm-bht_unittest.cc
diff --git a/dm-bht_unittest.cc b/dm-bht_unittest.cc
index 4ab2faf217a801ea369bc1aec6c564693c39d6fd..2eb2297ee8b43abfc6b8bd2baa1eddca2bd1a2a8 100644
--- a/dm-bht_unittest.cc
+++ b/dm-bht_unittest.cc
@@ -206,7 +206,30 @@ TEST_F(MemoryBhtTest, CreateThenVerifyMultipleLevels) {
   free(zero_page);
 }
 
-TEST_F(MemoryBhtTest, CreateThenVerifyOddCount) {
+TEST_F(MemoryBhtTest, CreateThenVerifyRealParameters) {
+  static const unsigned int total_blocks = 217600;
+  // Set the root hash for a 0-filled image
+  static const char kRootDigest[] =
+    "15d5a180b5080a1d43e3fbd1f2cd021d0fc3ea91a8e330bad468b980c2fd4d8b";
+  // A page of all zeros
+  u8 *zero_page = (u8 *)my_memalign(PAGE_SIZE, PAGE_SIZE);
+
+  memset(zero_page, 0, PAGE_SIZE);
+
+  SetupBht(3, total_blocks, "sha256");
+  dm_bht_set_root_hexdigest(bht_.get(),
+                            reinterpret_cast<const u8 *>(kRootDigest));
+
+  for (unsigned int blocks = 0; blocks < total_blocks; ++blocks) {
+    DLOG(INFO) << "verifying block: " << blocks;
+    EXPECT_EQ(0, dm_bht_verify_block(bht_.get(), blocks, zero_page));
+  }
+
+  EXPECT_EQ(0, dm_bht_destroy(bht_.get()));
+  free(zero_page);
+}
+
+TEST_F(MemoryBhtTest, CreateThenVerifyOddLeafCount) {
   static const unsigned int total_blocks = 16383;
   // Set the root hash for a 0-filled image
   static const char kRootDigest[] =
@@ -229,6 +252,29 @@ TEST_F(MemoryBhtTest, CreateThenVerifyOddCount) {
   free(zero_page);
 }
 
+TEST_F(MemoryBhtTest, CreateThenVerifyOddNodeCount) {
+  static const unsigned int total_blocks = 16000;
+  // Set the root hash for a 0-filled image
+  static const char kRootDigest[] =
+    "13e04b6aa410187b900834aa23e45f3e5240b0c4d2fadb2d8836a357c33499f0";
+  // A page of all zeros
+  u8 *zero_page = (u8 *)my_memalign(PAGE_SIZE, PAGE_SIZE);
+
+  memset(zero_page, 0, PAGE_SIZE);
+
+  SetupBht(4, total_blocks, "sha256");
+  dm_bht_set_root_hexdigest(bht_.get(),
+                            reinterpret_cast<const u8 *>(kRootDigest));
+
+  for (unsigned int blocks = 0; blocks < total_blocks; ++blocks) {
+    DLOG(INFO) << "verifying block: " << blocks;
+    EXPECT_EQ(0, dm_bht_verify_block(bht_.get(), blocks, zero_page));
+  }
+
+  EXPECT_EQ(0, dm_bht_destroy(bht_.get()));
+  free(zero_page);
+}
+
 TEST_F(MemoryBhtTest, CreateThenVerifyBadHashBlock) {
   static const unsigned int total_blocks = 16384;
   // Set the root hash for a 0-filled image