69bab0272a68231051c01f331f35bdf8dc04beb4
[chromiumos/third_party/kernel.git] / 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).