Documentation/device-mapper/dm-bht.txt

   1 dm-bht
   2 ======
   3
   4 dm-bht provides a block hash tree implementation.  The use of dm-bht allows
   5 for integrity checking of a given block device without reading the entire
   6 set of blocks into memory before use.
   7
   8 In particular, dm-bht supplies an interface for creating and verifying a tree
   9 of cryptographic digests with any algorithm supported by the kernel crypto API.
  10
  11 The code is meant to be usable from user-space for creation and verification as
  12 well as directly from a Device-Mapper target.  The `verity' target is the
  13 motivating example.
  14
  15
  16 Theory of operation
  17 ===================
  18
  19 dm-bht is logically comprised of multiple nodes organized in a tree-like
  20 structure.  Each node in the tree is a cryptographic hash.  If it is a leaf
  21 node, the hash is of some block data on disk.  If it is an intermediary node,
  22 then the hash is of a number of child nodes.
  23
  24 dm-bht has a given depth starting at 1 (ignoring the root node).  Each level in
  25 the tree is concretely made up of dm_bht_entry structs.  Each entry in the tree
  26 is a collection of neighboring nodes that fit in one page-sized block.  The
  27 number is determined based on PAGE_SIZE and the size of the selected
  28 cryptographic digest algorithm.  The hashes are linearly ordered in this entry
  29 and any unaligned trailing space is ignored but included when calculating the
  30 parent node.
  31
  32 The tree looks something like:
  33
  34 depth = 2, alg= sha256, num_blocks = 32767
  35                                  [   root    ]
  36                                 /    . . .    \
  37                      [entry_0]                 [entry_1]
  38                     /  . . .  \                 . . .   \
  39          [entry_0_0]   . . .  [entry_0_127]    . . . .  [entry_1_127]
  40            / ... \             /   . . .  \             /           \
  41      blk_0 ... blk_127  blk_16256   blk_16383      blk_32640 . . . blk_32767
  42
  43 root is treated independently from the depth and the blocks are expected to
  44 be hashed and supplied to the dm-bht.  hash blocks that make up the entry
  45 contents are expected to be read from disk.
  46
  47 dm-bht does not handle I/O directly but instead expects the consumer to
  48 supply callbacks.  The read callback will always receive a page-align value
  49 to pass to the block device layer to read in a hash value.
  50
  51 Usage
  52 =====
  53
  54 The API provides mechanisms for reading and verifying a tree as well as
  55 creating and modifying the tree.  These two code paths were not meant to be
  56 used in parallel and modify the atomic entry values in incompatible ways.
  57 Where possible, tree creation and modification should be handled independently
  58 from tree verification.
  59
  60 When reading, all required data for the hash tree should be populated for a
  61 block before attempting a verify.  This can be done by calling
  62 dm_bht_populate().  When all data is ready, a call to dm_bht_verify_block()
  63 with the expected hash value will perform both the direct block hash check and
  64 the hashes of the parent and neighboring nodes where needed to ensure validity
  65 up to the root hash.  Note, dm_bht_set_root_hexdigest() should be called before
  66 any verification attempts occur.
  67
  68 When updating the tree, all block hashes should be stored with
  69 dm_bht_store_block().  Once all hashes are stored, a call to dm_bht_compute()
  70 will initiate a full tree update by walking all of the blocks of hashes
  71 starting at the leaf nodes and computing upward to the root node.  On
  72 completion, dm_bht_sync() may be called to write the tree to disk (or wherever
  73 the callback writes to).