verity: remove the depth parameter from bht_create

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 11 matching lines @@
 #endif
 }
 
 void *my_memalign(size_t boundary, size_t size) {
   void * memptr;
   if (posix_memalign(&memptr, boundary, size))
     return NULL;
   return memptr;
 }
 
-
-
 TEST(DmBht, CreateFailOnOverflow) {
   struct dm_bht bht;
   // This should fail.
-  EXPECT_EQ(-EINVAL, dm_bht_create(&bht, 32, 1, "sha256"));
+  EXPECT_EQ(-EINVAL, dm_bht_create(&bht, UINT_MAX, "sha1"));
 }
 
 // Simple test to help valgrind/tcmalloc catch bad mem management
 TEST(DmBht, CreateZeroPopulateDestroy) {
   struct dm_bht bht;
   // This should fail.
   unsigned int blocks = 16384;
   u8 *data = (u8 *)my_memalign(PAGE_SIZE, PAGE_SIZE);
 
   // Store all the block hashes of blocks of 0.
   memset(reinterpret_cast<void *>(data), 0, sizeof(data));
-  EXPECT_EQ(0, dm_bht_create(&bht, 2, blocks, "sha256"));
+  EXPECT_EQ(0, dm_bht_create(&bht, blocks, "sha256"));
   dm_bht_set_read_cb(&bht, dm_bht_zeroread_callback);
   do {
     EXPECT_EQ(dm_bht_store_block(&bht, blocks - 1, data), 0);
   } while (--blocks > 0);
   EXPECT_EQ(0, dm_bht_compute(&bht, NULL));
   EXPECT_EQ(0, dm_bht_destroy(&bht));
   free(data);
 }
 
 class MemoryBhtTest : public ::testing::Test {
@@ skipping 34 matching lines @@
                           sector_t count,
                           struct dm_bht_entry *entry) {
     MemoryBhtTest *mbht = reinterpret_cast<MemoryBhtTest *>(mbht_instance);
     mbht->Read(start, dst, count);
     dm_bht_read_completed(entry, 0);
     return 0;
   }
 
  protected:
   // Creates a new dm_bht and sets it in the existing MemoryBht.
-  void NewBht(const unsigned int depth,
-              const unsigned int total_blocks,
+  void NewBht(const unsigned int total_blocks,
               const char *digest_algorithm) {
     bht_.reset(new dm_bht());
-    EXPECT_EQ(0, dm_bht_create(bht_.get(),depth, total_blocks,
+    EXPECT_EQ(0, dm_bht_create(bht_.get(), total_blocks,
                                digest_algorithm));
     if (hash_data_.get() == NULL) {
       sectors_ = dm_bht_sectors(bht_.get());
       hash_data_.reset(new u8[to_bytes(sectors_)]);
     }
     dm_bht_set_write_cb(bht_.get(), MemoryBhtTest::WriteCallback);
     dm_bht_set_read_cb(bht_.get(), MemoryBhtTest::ReadCallback);
   }
-  void SetupBht(const unsigned int depth,
-                const unsigned int total_blocks,
+  void SetupBht(const unsigned int total_blocks,
                 const char *digest_algorithm) {
-    NewBht(depth, total_blocks, digest_algorithm);
+    NewBht(total_blocks, digest_algorithm);
 
     u8 *data = (u8 *)my_memalign(PAGE_SIZE, PAGE_SIZE);
 
     memset(data, 0, PAGE_SIZE);
 
     unsigned int blocks = total_blocks;
     do {
       EXPECT_EQ(dm_bht_store_block(bht_.get(), blocks - 1, data), 0);
     } while (--blocks > 0);
 
     dm_bht_set_read_cb(bht_.get(), dm_bht_zeroread_callback);
     EXPECT_EQ(0, dm_bht_compute(bht_.get(), NULL));
     EXPECT_EQ(0, dm_bht_sync(bht_.get(), reinterpret_cast<void *>(this)));
     u8 digest[1024];
     dm_bht_root_hexdigest(bht_.get(), digest, sizeof(digest));
     LOG(INFO) << "MemoryBhtTest root is " << digest;
     EXPECT_EQ(0, dm_bht_destroy(bht_.get()));
     // bht is now dead and mbht_ is a prepared hash image
 
-    NewBht(depth, total_blocks, digest_algorithm);
+    NewBht(total_blocks, digest_algorithm);
 
     // Load the tree from the pre-populated hash data
     for (blocks = 0; blocks < total_blocks; blocks += bht_->node_count) {
       EXPECT_GE(dm_bht_populate(bht_.get(),
                                 reinterpret_cast<void *>(this),
                                 blocks),
                 DM_BHT_ENTRY_REQUESTED);
       // Since we're testing synchronously, a second run through should yield
       // READY.
       EXPECT_GE(dm_bht_populate(bht_.get(),
@@ skipping 12 matching lines @@
 TEST_F(MemoryBhtTest, CreateThenVerifyOk) {
   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);
 
-  SetupBht(2, total_blocks, "sha256");
+  SetupBht(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, CreateThenVerifyMultipleLevels) {
-  static const unsigned int total_blocks = 16384;
-  // Set the root hash for a 0-filled image
-  static const char kRootDigest[] =
-    "c86619624d3456f711dbb94d4ad79a4b029f6fd3b5a4a90b155c856bf5b3409b";
-  // 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, CreateThenVerifyZeroDepth) {
-  static const unsigned int total_blocks = 16384;
+TEST_F(MemoryBhtTest, CreateThenVerifySingleLevel) {

[Will Drewry, 2011/04/12 03:12:32]

Nit: SingleBlock :) 32 blocks will all end up hashed into one block.  It'd be
worth while to do at least 129 blocks I'd think.  But that could be
yet-another-test in a new CL since this is worthwhile too.

+  static const unsigned int total_blocks = 32;
   // Set the root hash for a 0-filled image
   static const char kRootDigest[] =
-    "45d65d6f9e5a962f4d80b5f1bd7a918152251c27bdad8c5f52b590c129833372";
+    "2d3a43008286f56536fa24dcdbf14d342f0548827e374210415c7be0b610d2ba";

[Will Drewry, 2011/04/12 03:12:32]

FWIW, I did manually cross check this hash:
$ rm /tmp/level.1.tmp; i=0; while [[ $i -lt 32 ]]; do head -c 4096 /dev/zero
|openssl sha -sha256 -binary >> /tmp/level.1.tmp; i=$((i+1)); done; head -c 4096
/dev/zero > /tmp/level.1;
# Pad it out to 4k
$ dd if=/tmp/level.1.tmp of=/tmp/level.1 conv=notrunc
# check the hash
$ openssl sha -sha256 /tmp/level.1
SHA256(/tmp/level.1)=
2d3a43008286f56536fa24dcdbf14d342f0548827e374210415c7be0b610d2ba

Once the trie changes are complete - I think it'd be worthwhile to manually
generate a range of expected roots for these (rather than just taking the new
output of verity).  I dunno if you've been doing that, but I know that's how I
tend to do it and only manually check intermittenly.

   // A page of all zeros
   u8 *zero_page = (u8 *)my_memalign(PAGE_SIZE, PAGE_SIZE);
 
   memset(zero_page, 0, PAGE_SIZE);
 
-  SetupBht(0, total_blocks, "sha256");
+  SetupBht(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, 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");
+  SetupBht(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";
+    "dc8cec4220d388b05ba75c853f858bb8cc25edfb1d5d2f3be6bdf9edfa66dc6a";
   // 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");
+  SetupBht(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";
+    "10832dd62c427bcf68c56c8de0d1f9c32b61d9e5ddf43c77c56a97b372ad4b07";
   // 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");
+  SetupBht(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);
 
-  SetupBht(2, total_blocks, "sha256");
+  SetupBht(total_blocks, "sha256");
 
   dm_bht_set_root_hexdigest(bht_.get(),
                             reinterpret_cast<const u8 *>(kRootDigest));
 
   // TODO(wad) add tests for partial tree validity/verification
 
   // Corrupt one has hblock
   static const unsigned int kBadBlock = 256;
   u8 *bad_hash_block= (u8 *)my_memalign(PAGE_SIZE, PAGE_SIZE);
   memset(bad_hash_block, 'A', PAGE_SIZE);
@@ skipping 18 matching lines @@
                                 zero_page),
             0);
 
   EXPECT_EQ(0, dm_bht_destroy(bht_.get()));
   free(bad_hash_block);
   free(zero_page);
 }
 
 TEST_F(MemoryBhtTest, CreateThenVerifyBadDataBlock) {
   static const unsigned int total_blocks = 384;
-  SetupBht(2, total_blocks, "sha256");
+  SetupBht(total_blocks, "sha256");
   // Set the root hash for a 0-filled image
   static const char kRootDigest[] =
     "45d65d6f9e5a962f4d80b5f1bd7a918152251c27bdad8c5f52b590c129833372";
   dm_bht_set_root_hexdigest(bht_.get(),
                             reinterpret_cast<const u8 *>(kRootDigest));
   // A corrupt page
   u8 *bad_page = (u8 *)my_memalign(PAGE_SIZE, PAGE_SIZE);
 
   memset(bad_page, 'A', PAGE_SIZE);
 
 
   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);
 }