verity: handle trees with an odd node count correctly
This fixes a bug we were seeing when setting root_depth=3.
BUG=none
TEST=Ran unittests.
Change-Id: I7241ccd97102638e9f003a694280ca0b53f317b9
R=wad@chromium.org
Review URL: http://codereview.chromium.org/6742001
diff --git a/dm-bht.c b/dm-bht.c
index dd57e12..8a5e33f 100644
--- a/dm-bht.c
+++ b/dm-bht.c
@@ -834,7 +834,6 @@
struct dm_bht_level *child_level = level + 1;
struct dm_bht_entry *entry = level->entries;
struct dm_bht_entry *child = child_level->entries;
- unsigned int count = min(bht->node_count, child_level->count);
unsigned int i, j;
r = dm_bht_maybe_read_entries(bht, read_cb_ctx, depth,
@@ -845,6 +844,11 @@
}
for (i = 0; i < level->count; i++, entry++) {
+ unsigned int count = bht->node_count;
+ if (i == (level->count - 1))
+ count = child_level->count % bht->node_count;
+ if (count == 0)
+ count = bht->node_count;
for (j = 0; j < count; j++, child++) {
u8 *block = child->nodes;
u8 *digest = dm_bht_node(bht, entry, j);
diff --git a/dm-bht_unittest.cc b/dm-bht_unittest.cc
index 4ab2faf..2eb2297 100644
--- a/dm-bht_unittest.cc
+++ b/dm-bht_unittest.cc
@@ -206,7 +206,30 @@
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 @@
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