src/devices/block/drivers/block-verity/geometry.cc - fuchsia - Git at Google

 // Copyright 2020 The Fuchsia Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.

 #include "src/devices/block/drivers/block-verity/geometry.h"

 #include <zircon/assert.h>

 #include <cstdio>
 #include <utility>

 namespace block_verity {

 IntegrityShape IntegrityShapeFor(uint32_t block_size, uint32_t hash_size,
                                  uint64_t data_block_count) {
   ZX_ASSERT(block_size % hash_size == 0);
   uint32_t hashes_per_block = block_size / hash_size;
   uint64_t direct_hash_blocks_needed_floored = data_block_count / hashes_per_block;
   uint32_t remainder = data_block_count % hashes_per_block;
   uint64_t direct_hash_blocks_needed = direct_hash_blocks_needed_floored + (remainder != 0 ? 1 : 0);
   if (direct_hash_blocks_needed == 1) {
     // Base case - fits in a block, which goes at the root
     return IntegrityShape{1, 1};
   }

   IntegrityShape indirect = IntegrityShapeFor(block_size, hash_size, direct_hash_blocks_needed);
   uint64_t total_blocks_needed = direct_hash_blocks_needed + indirect.integrity_block_count;
   uint32_t tree_depth = 1 + indirect.tree_depth;
   return IntegrityShape{total_blocks_needed, tree_depth};
 }

 BlockAllocation BestSplitFor(uint32_t block_size, uint32_t hash_size, uint64_t total_blocks) {
   // Block_size must be a multiple of hash_size, because we don't want to deal
   // with padding and both are almost always powers of two anyway.
   ZX_ASSERT(block_size % hash_size == 0);
   // must have at least three blocks to split - one superblock, one data block, one integrity block.
   ZX_ASSERT(total_blocks >= 3);

   uint64_t superblocks = 1;
   uint64_t largest_possible_data_blocks = 1;
   uint64_t smallest_impossible_data_blocks = total_blocks - 2;
   IntegrityShape best_integrity_shape_yet;

   while (largest_possible_data_blocks + 1 < smallest_impossible_data_blocks) {
     // Binary search to find most data blocks we can support.
     uint64_t test_data_blocks =
         largest_possible_data_blocks +
         ((smallest_impossible_data_blocks - largest_possible_data_blocks) / 2);
     IntegrityShape i = IntegrityShapeFor(block_size, hash_size, test_data_blocks);
     if (test_data_blocks + i.integrity_block_count + superblocks <= total_blocks) {
       // Having test_data_blocks is satisfiable.
       largest_possible_data_blocks = test_data_blocks;
       best_integrity_shape_yet = i;
     } else {
       smallest_impossible_data_blocks = test_data_blocks;
     }
   }

   // It's possible at the margins that we can't make use of the entirety of the
   // block device -- if we were to add a data block, we'd need an additional
   // integrity block, because we're at the edge of an integrity block boundary
   // too, but we have none left to allocate.  In this case we allocate the
   // additional block (or blocks) to the end of the integrity section, where it
   // will sit unused.  That is: those blocks contribute to
   // padded_integrity_block_count in `BlockAllocation` here, but not to
   // IntegrityShape's `integrity_block_count`.
   uint64_t padded_integrity_blocks = total_blocks - superblocks - largest_possible_data_blocks;
   return BlockAllocation{superblocks, padded_integrity_blocks, largest_possible_data_blocks,
                          best_integrity_shape_yet};
 }

 Geometry::Geometry(uint32_t block_size, uint32_t hash_size, uint64_t total_blocks)
     : total_blocks_(total_blocks),
       hash_size_(hash_size),
       block_size_(block_size),
       hashes_per_block_(block_size / hash_size),
       allocation_(BestSplitFor(block_size, hash_size, total_blocks)) {}

 HashLocation Geometry::IntegrityDataLocationForDataBlock(DataBlockIndex data_block_index) const {
   uint64_t to_pass = data_block_index / hashes_per_block_;

 uint64_t block_offset = 0;

   while (to_pass > 0) {
     // Skipping `to_pass` blocks
     block_offset += to_pass;
     to_pass = to_pass / hashes_per_block_;
   }

   uint32_t hash_offset = data_block_index % hashes_per_block_;
   return HashLocation{block_offset, hash_offset};
 }

 HashLocation Geometry::NextIntegrityBlockUp(uint32_t distance_from_leaf,
                                             IntegrityBlockIndex integrity_block_index) const {
   //
   // If, for example hashes_per_block_ were 128, the integrity data would look
   // like this, where reading blocks left to right (and the contents of the
   // boxes) indicates the block offset within the integrity section, and each
   // block in tier N+1 contains the hashes of the `hashes_per_block_` preceding
   // blocks from tier N (and blocks in tier 0 contain hashes of blocks from the
   // data section.
   //
   // tier 2                                                                      |16512|         ...
   // tier 1                        |128|                       |257| ... |16511|                 ...
   // tier 0  |0| |1| |2| ... |127|       |129| |130| ... |256|       ...                 |16513| ...
   //
   // The integrity block number for a given index is the first block to the
   // right of it in the next tier up.  So 2 -> 128, and 128 -> 16512.
   //
   // So, in this hypothetical example, if you passed distance_from_leaf = 0 and
   // integrity_block_index 2, you'd expect to get back a hash location with
   // integrity_block 128 and hash_in_block 2.
   //
   // Note: `distance_from_leaf` is inferrable from integrity_block_number, and
   // what its value in base (hashes_per_block_+1) is, but that involves test
   // division which is slow.  Better to track the distance and save some integer
   // division/modular arithmetic.
   //
   // If integrity_block_index is a leaf node, distance_from_leaf should be 0.

   // TODO: clean up these printfs once verified read is implemented/tested
   // printf("                                       NextIntegrityBlockUp(block: %lu, tier %u)\n",
   //       integrity_block_index, distance_from_leaf);

   uint64_t one_indexed_integrity_block_index = integrity_block_index + 1;
   // Convert to one-indexed arithmetic for the next bit.  It's simpler for some
   // of the modular arithmetic around tier strides.

   // The "stride" of a tier is the difference in (physical) block index between
   // two blocks within the same tier, if the tier were to be completely full.
   // So tier 0 always has stride 1, tier 1 has stride (hashes_per_block_ + 1),
   // and so on.
   uint64_t current_tier_stride = 1;
   for (uint32_t i = 0; i < distance_from_leaf; i++) {
     current_tier_stride *= hashes_per_block_;
     current_tier_stride += 1;
   }
   uint64_t next_tier_stride = current_tier_stride * hashes_per_block_ + 1;

   // TODO: clean up these printfs once verified read is implemented/tested
   // printf("                                       current tier stride %lu, next tier stride
   // %lu\n",
   //       current_tier_stride, next_tier_stride);

   // Compute which hash in the containing integrity block (which sits up one
   // tier from `integrity_block_index`) contains the hash of the integrity data
   // at `integrity_block_index`.
   // We can achieve this by operating modulo the next larger tier stride,
   // by dividing by the current tier stride (which we know from above our current index is an
   // exact multiple of, unless it is in the last block of this tier).
   //
   // `block_in_tier_chunk` represents the block offset within the bounds of
   // one next-tier-up-stride.
   uint64_t block_in_tier_chunk = one_indexed_integrity_block_index % next_tier_stride;
   // `unadjusted_offset_within_block` represents "If I'm scanning blocks within
   // the current next-tier-up stride, how many `current_tier_stride`s in the
   // next-tier-up stride do I pass over before I reach this block?".  It's the
   // relative offset within that block.  It's guaranteed not to overflow
   // uint32_t because we cap total block count at (2**20 - 1), so we'll never
   // even get close to having an integrity block offset of 2**32.
   uint32_t unadjusted_offset_within_block =
       static_cast<uint32_t>(block_in_tier_chunk / current_tier_stride);

   // The last block at each tier in a non-full tree (which the vast majority of
   // trees will be) might be placed earlier than it would in a full tree.  We
   // fill the tree from left to right so that only the last block in each tier
   // may require padding.
   //
   // To see how this might happen, consider a tree where hashes_per_block_ is
   // 128, we have (129 * 128) = 16512 data blocks and 131 integrity blocks:
   //
   // tier 2:                          131
   // tier 1:              128     130
   // tier 0: 0 1 2 ...127     129
   //
   // Integrity block 129 is full of hashes of data blocks.
   // Integrity block 130 contains the hash of block 129 and zeroes padding it
   // out to the block size.
   // Integrity block 131 contains (hash of block 128), (hash of block 130), and
   // zeroes padding it out to the block size.
   // The hash of block 131 is stored in the superblock.
   // The hash of the superblock is the seal produced by CloseAndGenerateSeal.

   // `block_in_tier_chunk` should be a perfect multiple of `current_tier_stride`,
   // *unless* it is in the last block of this tier *and* that tier is not full,
   // which would cause the value of `unadjusted_offset_within_block` to truncate
   // when dividing.  We'd like to round that truncated bit up.
   //
   // In the former case, we need to subtract one to return to zero-indexing.
   // In the latter case, we need to subtract one to return to zero-indexing and
   // we need to add one to compensate for the truncating division, which means
   // we can just take the value as-is.
   uint32_t offset_within_block =
       (unadjusted_offset_within_block * current_tier_stride == block_in_tier_chunk)
           ? unadjusted_offset_within_block - 1
           : unadjusted_offset_within_block;

   // Round up to the next multiple of the next tier size, by shaving off the
   // residue mod next_tier_stride, then adding in the full next_tier_stride.
   // There's probably another way to compute this in closed form that's faster
   // and uses smaller numbers by reusing offset_within_block.
   uint64_t one_indexed_containing_block_index =
       (one_indexed_integrity_block_index - (one_indexed_integrity_block_index % next_tier_stride) +
        next_tier_stride);

   uint64_t zero_indexed_containing_block_index = one_indexed_containing_block_index - 1;

   // Just as we applied adjustments to `unadjusted_offset_within_block` to
   // account for incomplete trees, we need to adjust the block index itself.
   // The only blocks that need this sort of adjustment are ones which were
   // padded with zeroes because the tree is not full, and those will only ever
   // be the last block within a tier.
   //
   // So we can clamp the block index to the total number of populated integrity
   // blocks, and solve backwards from the end of the integrity section what the
   // last block at that tier's maximum index could be.
   uint64_t max_block_index_at_tier =
       allocation_.integrity_shape.integrity_block_count -
       (allocation_.integrity_shape.tree_depth - 1 - distance_from_leaf);

   uint64_t clamped_containing_block_index = zero_indexed_containing_block_index;
   if (zero_indexed_containing_block_index > max_block_index_at_tier) {
     // Don't reach too far
     clamped_containing_block_index = max_block_index_at_tier;
     // TODO: clean up these printfs once verified read is implemented/tested
     // printf("clamped %u to %u\n", zero_indexed_containing_block_index, max_block_index_at_tier);
   }
   return HashLocation{clamped_containing_block_index, offset_within_block};
 }

 uint64_t Geometry::AbsoluteLocationForIntegrity(IntegrityBlockIndex index) const {
   return allocation_.superblock_count + index;
 }

 uint64_t Geometry::AbsoluteLocationForData(DataBlockIndex index) const {
   return allocation_.superblock_count + allocation_.padded_integrity_block_count + index;
 }

 }  // namespace block_verity
	// Copyright 2020 The Fuchsia Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style license that can be
	// found in the LICENSE file.

	#include "src/devices/block/drivers/block-verity/geometry.h"

	#include <zircon/assert.h>

	#include <cstdio>
	#include <utility>

	namespace block_verity {

	IntegrityShape IntegrityShapeFor(uint32_t block_size, uint32_t hash_size,
	uint64_t data_block_count) {
	ZX_ASSERT(block_size % hash_size == 0);
	uint32_t hashes_per_block = block_size / hash_size;
	uint64_t direct_hash_blocks_needed_floored = data_block_count / hashes_per_block;
	uint32_t remainder = data_block_count % hashes_per_block;
	uint64_t direct_hash_blocks_needed = direct_hash_blocks_needed_floored + (remainder != 0 ? 1 : 0);
	if (direct_hash_blocks_needed == 1) {
	// Base case - fits in a block, which goes at the root
	return IntegrityShape{1, 1};
	}

	IntegrityShape indirect = IntegrityShapeFor(block_size, hash_size, direct_hash_blocks_needed);
	uint64_t total_blocks_needed = direct_hash_blocks_needed + indirect.integrity_block_count;
	uint32_t tree_depth = 1 + indirect.tree_depth;
	return IntegrityShape{total_blocks_needed, tree_depth};
	}

	BlockAllocation BestSplitFor(uint32_t block_size, uint32_t hash_size, uint64_t total_blocks) {
	// Block_size must be a multiple of hash_size, because we don't want to deal
	// with padding and both are almost always powers of two anyway.
	ZX_ASSERT(block_size % hash_size == 0);
	// must have at least three blocks to split - one superblock, one data block, one integrity block.
	ZX_ASSERT(total_blocks >= 3);

	uint64_t superblocks = 1;
	uint64_t largest_possible_data_blocks = 1;
	uint64_t smallest_impossible_data_blocks = total_blocks - 2;
	IntegrityShape best_integrity_shape_yet;

	while (largest_possible_data_blocks + 1 < smallest_impossible_data_blocks) {
	// Binary search to find most data blocks we can support.
	uint64_t test_data_blocks =
	largest_possible_data_blocks +
	((smallest_impossible_data_blocks - largest_possible_data_blocks) / 2);
	IntegrityShape i = IntegrityShapeFor(block_size, hash_size, test_data_blocks);
	if (test_data_blocks + i.integrity_block_count + superblocks <= total_blocks) {
	// Having test_data_blocks is satisfiable.
	largest_possible_data_blocks = test_data_blocks;
	best_integrity_shape_yet = i;
	} else {
	smallest_impossible_data_blocks = test_data_blocks;
	}
	}

	// It's possible at the margins that we can't make use of the entirety of the
	// block device -- if we were to add a data block, we'd need an additional
	// integrity block, because we're at the edge of an integrity block boundary
	// too, but we have none left to allocate. In this case we allocate the
	// additional block (or blocks) to the end of the integrity section, where it
	// will sit unused. That is: those blocks contribute to
	// padded_integrity_block_count in `BlockAllocation` here, but not to
	// IntegrityShape's `integrity_block_count`.
	uint64_t padded_integrity_blocks = total_blocks - superblocks - largest_possible_data_blocks;
	return BlockAllocation{superblocks, padded_integrity_blocks, largest_possible_data_blocks,
	best_integrity_shape_yet};
	}

	Geometry::Geometry(uint32_t block_size, uint32_t hash_size, uint64_t total_blocks)
	: total_blocks_(total_blocks),
	hash_size_(hash_size),
	block_size_(block_size),
	hashes_per_block_(block_size / hash_size),
	allocation_(BestSplitFor(block_size, hash_size, total_blocks)) {}

	HashLocation Geometry::IntegrityDataLocationForDataBlock(DataBlockIndex data_block_index) const {
	uint64_t to_pass = data_block_index / hashes_per_block_;

	uint64_t block_offset = 0;

	while (to_pass > 0) {
	// Skipping `to_pass` blocks
	block_offset += to_pass;
	to_pass = to_pass / hashes_per_block_;
	}

	uint32_t hash_offset = data_block_index % hashes_per_block_;
	return HashLocation{block_offset, hash_offset};
	}

	HashLocation Geometry::NextIntegrityBlockUp(uint32_t distance_from_leaf,
	IntegrityBlockIndex integrity_block_index) const {
	//
	// If, for example hashes_per_block_ were 128, the integrity data would look
	// like this, where reading blocks left to right (and the contents of the
	// boxes) indicates the block offset within the integrity section, and each
	// block in tier N+1 contains the hashes of the `hashes_per_block_` preceding
	// blocks from tier N (and blocks in tier 0 contain hashes of blocks from the
	// data section.
	//
	// tier 2 \|16512\| ...
	// tier 1 \|128\| \|257\| ... \|16511\| ...
	// tier 0 \|0\| \|1\| \|2\| ... \|127\| \|129\| \|130\| ... \|256\| ... \|16513\| ...
	//
	// The integrity block number for a given index is the first block to the
	// right of it in the next tier up. So 2 -> 128, and 128 -> 16512.
	//
	// So, in this hypothetical example, if you passed distance_from_leaf = 0 and
	// integrity_block_index 2, you'd expect to get back a hash location with
	// integrity_block 128 and hash_in_block 2.
	//
	// Note: `distance_from_leaf` is inferrable from integrity_block_number, and
	// what its value in base (hashes_per_block_+1) is, but that involves test
	// division which is slow. Better to track the distance and save some integer
	// division/modular arithmetic.
	//
	// If integrity_block_index is a leaf node, distance_from_leaf should be 0.

	// TODO: clean up these printfs once verified read is implemented/tested
	// printf(" NextIntegrityBlockUp(block: %lu, tier %u)\n",
	// integrity_block_index, distance_from_leaf);

	uint64_t one_indexed_integrity_block_index = integrity_block_index + 1;
	// Convert to one-indexed arithmetic for the next bit. It's simpler for some
	// of the modular arithmetic around tier strides.

	// The "stride" of a tier is the difference in (physical) block index between
	// two blocks within the same tier, if the tier were to be completely full.
	// So tier 0 always has stride 1, tier 1 has stride (hashes_per_block_ + 1),
	// and so on.
	uint64_t current_tier_stride = 1;
	for (uint32_t i = 0; i < distance_from_leaf; i++) {
	current_tier_stride *= hashes_per_block_;
	current_tier_stride += 1;
	}
	uint64_t next_tier_stride = current_tier_stride * hashes_per_block_ + 1;

	// TODO: clean up these printfs once verified read is implemented/tested
	// printf(" current tier stride %lu, next tier stride
	// %lu\n",
	// current_tier_stride, next_tier_stride);

	// Compute which hash in the containing integrity block (which sits up one
	// tier from `integrity_block_index`) contains the hash of the integrity data
	// at `integrity_block_index`.
	// We can achieve this by operating modulo the next larger tier stride,
	// by dividing by the current tier stride (which we know from above our current index is an
	// exact multiple of, unless it is in the last block of this tier).
	//
	// `block_in_tier_chunk` represents the block offset within the bounds of
	// one next-tier-up-stride.
	uint64_t block_in_tier_chunk = one_indexed_integrity_block_index % next_tier_stride;
	// `unadjusted_offset_within_block` represents "If I'm scanning blocks within
	// the current next-tier-up stride, how many `current_tier_stride`s in the
	// next-tier-up stride do I pass over before I reach this block?". It's the
	// relative offset within that block. It's guaranteed not to overflow
	// uint32_t because we cap total block count at (2**20 - 1), so we'll never
	// even get close to having an integrity block offset of 2**32.
	uint32_t unadjusted_offset_within_block =
	static_cast<uint32_t>(block_in_tier_chunk / current_tier_stride);

	// The last block at each tier in a non-full tree (which the vast majority of
	// trees will be) might be placed earlier than it would in a full tree. We
	// fill the tree from left to right so that only the last block in each tier
	// may require padding.
	//
	// To see how this might happen, consider a tree where hashes_per_block_ is
	// 128, we have (129 * 128) = 16512 data blocks and 131 integrity blocks:
	//
	// tier 2: 131
	// tier 1: 128 130
	// tier 0: 0 1 2 ...127 129
	//
	// Integrity block 129 is full of hashes of data blocks.
	// Integrity block 130 contains the hash of block 129 and zeroes padding it
	// out to the block size.
	// Integrity block 131 contains (hash of block 128), (hash of block 130), and
	// zeroes padding it out to the block size.
	// The hash of block 131 is stored in the superblock.
	// The hash of the superblock is the seal produced by CloseAndGenerateSeal.

	// `block_in_tier_chunk` should be a perfect multiple of `current_tier_stride`,
	// unless it is in the last block of this tier and that tier is not full,
	// which would cause the value of `unadjusted_offset_within_block` to truncate
	// when dividing. We'd like to round that truncated bit up.
	//
	// In the former case, we need to subtract one to return to zero-indexing.
	// In the latter case, we need to subtract one to return to zero-indexing and
	// we need to add one to compensate for the truncating division, which means
	// we can just take the value as-is.
	uint32_t offset_within_block =
	(unadjusted_offset_within_block * current_tier_stride == block_in_tier_chunk)
	? unadjusted_offset_within_block - 1
	: unadjusted_offset_within_block;

	// Round up to the next multiple of the next tier size, by shaving off the
	// residue mod next_tier_stride, then adding in the full next_tier_stride.
	// There's probably another way to compute this in closed form that's faster
	// and uses smaller numbers by reusing offset_within_block.
	uint64_t one_indexed_containing_block_index =
	(one_indexed_integrity_block_index - (one_indexed_integrity_block_index % next_tier_stride) +
	next_tier_stride);

	uint64_t zero_indexed_containing_block_index = one_indexed_containing_block_index - 1;

	// Just as we applied adjustments to `unadjusted_offset_within_block` to
	// account for incomplete trees, we need to adjust the block index itself.
	// The only blocks that need this sort of adjustment are ones which were
	// padded with zeroes because the tree is not full, and those will only ever
	// be the last block within a tier.
	//
	// So we can clamp the block index to the total number of populated integrity
	// blocks, and solve backwards from the end of the integrity section what the
	// last block at that tier's maximum index could be.
	uint64_t max_block_index_at_tier =
	allocation_.integrity_shape.integrity_block_count -
	(allocation_.integrity_shape.tree_depth - 1 - distance_from_leaf);

	uint64_t clamped_containing_block_index = zero_indexed_containing_block_index;
	if (zero_indexed_containing_block_index > max_block_index_at_tier) {
	// Don't reach too far
	clamped_containing_block_index = max_block_index_at_tier;
	// TODO: clean up these printfs once verified read is implemented/tested
	// printf("clamped %u to %u\n", zero_indexed_containing_block_index, max_block_index_at_tier);
	}
	return HashLocation{clamped_containing_block_index, offset_within_block};
	}

	uint64_t Geometry::AbsoluteLocationForIntegrity(IntegrityBlockIndex index) const {
	return allocation_.superblock_count + index;
	}

	uint64_t Geometry::AbsoluteLocationForData(DataBlockIndex index) const {
	return allocation_.superblock_count + allocation_.padded_integrity_block_count + index;
	}

	} // namespace block_verity