verity: handle trees with an odd node count correctly

dm-bht_unittest.cc

 // Copyright (C) 2010 The Chromium OS Authors. All rights reserved.
 // Use of this source code is governed by the GPL v2 license that can
 // be found in the LICENSE file.
 //
 // Basic unittesting of dm-bht using google-gtest.
 
 #include <base/basictypes.h>
 #include <base/logging.h>
 #include <base/scoped_ptr.h>
 #include <gtest/gtest.h>
@@ skipping 188 matching lines @@
 
   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, 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[] =
     "c78d187c430465bd7831fe4908247b6ab5107e3a826d933b71e85aa9a932e03c";
   // 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, 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
   static const char kRootDigest[] =
     "45d65d6f9e5a962f4d80b5f1bd7a918152251c27bdad8c5f52b590c129833372";
   // A page of all zeros
   u8 *zero_page = (u8 *)my_memalign(PAGE_SIZE, PAGE_SIZE);
 
   memset(zero_page, 0, PAGE_SIZE);
 
@@ skipping 51 matching lines @@
   EXPECT_LT(dm_bht_verify_block(bht_.get(), 0, bad_page), 0);
   EXPECT_LT(dm_bht_verify_block(bht_.get(), 127, bad_page), 0);
   EXPECT_LT(dm_bht_verify_block(bht_.get(), 128, bad_page), 0);
   EXPECT_LT(dm_bht_verify_block(bht_.get(), 255, bad_page), 0);
   EXPECT_LT(dm_bht_verify_block(bht_.get(), 256, bad_page), 0);
   EXPECT_LT(dm_bht_verify_block(bht_.get(), 383, bad_page), 0);
 
   EXPECT_EQ(0, dm_bht_destroy(bht_.get()));
   free(bad_page);
 }