src/devices/block/drivers/block-verity/geometry.h

// 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.

#ifndef SRC_DEVICES_BLOCK_DRIVERS_BLOCK_VERITY_GEOMETRY_H_
#define SRC_DEVICES_BLOCK_DRIVERS_BLOCK_VERITY_GEOMETRY_H_

#include <stdint.h>

namespace block_verity {

// A block_verity partition is composed of three sections:
// * superblock
// * integrity section
// * data section
//
// The amount of space allocated to each section varies by virtual block size (in
// bytes), hash function output length (in bytes), and block device size (in
// virtual blocks).

struct IntegrityShape {
  uint64_t integrity_block_count;
  uint32_t tree_depth;  // number of tiers of integrity blocks
};

// Given a number of data blocks, a block size, and a hash output size, compute
// how many integrity blocks will be needed to provide integrity data for them,
// and how deep the hash tree would need to be to cover it.
IntegrityShape IntegrityShapeFor(uint32_t block_size, uint32_t hash_size,
                                 uint64_t data_block_count);

struct BlockAllocation {
  // Number of blocks allocated for metadata/superblock.  This is 1.
  uint64_t superblock_count;

  // Number of blocks allocated to the "integrity section", including unusable
  // blocks.
  uint64_t padded_integrity_block_count;

  // Number of blocks allocated to the "data section"
  uint64_t data_block_count;

  IntegrityShape integrity_shape;
};

BlockAllocation BestSplitFor(uint32_t block_size, uint32_t hash_size, uint64_t total_blocks);

typedef uint64_t IntegrityBlockIndex;
typedef uint64_t DataBlockIndex;
typedef uint32_t HashIndex;

// A representation of where, within the integrity section, the hash of a
// particular block can be found.
struct HashLocation {
  // The index (in virtual blocks) into the integrity section of the block we are consulting.
  IntegrityBlockIndex integrity_block;

  // The index of the hash within that block.  To get a byte offset, multiply hash_in_block by
  // hash_size.
  HashIndex hash_in_block;
};

class Geometry {
 public:
  Geometry(uint32_t block_size, uint32_t hash_size, uint64_t total_blocks);

  // Given a data block index, return the location in the integrity section that
  // contains the hash of the literal data in that block.  This is used in the
  // verified read logic.
  HashLocation IntegrityDataLocationForDataBlock(DataBlockIndex data_block_index) const;

  // Given a block index into the integrity data, return the integrity data
  // block index and intra-block hash offset that covers that indirect block.
  // This is used on the verified read path -- after authenticating a data
  // block by checking the hash value at the location specified by
  // `IntegrityDataLocationForDataBlock`, we need to chain hash verification up
  // the merkle tree to the root.  This function tells us where to find the next
  // block up in the merkle tree.
  HashLocation NextIntegrityBlockUp(uint32_t distance_from_leaf,
                                    IntegrityBlockIndex integrity_block_index) const;

  // Returns the device block offset (in virtual blocks) for the `index`th integrity block.
  uint64_t AbsoluteLocationForIntegrity(IntegrityBlockIndex index) const;

  // Returns the device block offset (in virtual blocks) for the `index`th data block.
  uint64_t AbsoluteLocationForData(DataBlockIndex index) const;

  uint64_t total_blocks_;
  uint32_t hash_size_;
  uint32_t block_size_;
  uint32_t hashes_per_block_;
  BlockAllocation allocation_;
};

}  // namespace block_verity

#endif  // SRC_DEVICES_BLOCK_DRIVERS_BLOCK_VERITY_GEOMETRY_H_