Chromium Code Reviews| OLD | NEW |
|---|---|
| 1 /* | 1 /* |
| 2 * Copyright (C) 2010 The Chromium OS Authors <chromium-os-dev@chromium.org> | 2 * Copyright (C) 2010 The Chromium OS Authors <chromium-os-dev@chromium.org> |
| 3 * | 3 * |
| 4 * Device-Mapper block hash tree interface. | 4 * Device-Mapper block hash tree interface. |
| 5 * See Documentation/device-mapper/dm-bht.txt for details. | 5 * See Documentation/device-mapper/dm-bht.txt for details. |
| 6 * | 6 * |
| 7 * This file is released under the GPL. | 7 * This file is released under the GPL. |
| 8 */ | 8 */ |
| 9 | 9 |
| 10 #include <asm/atomic.h> | 10 #include <asm/atomic.h> |
| (...skipping 77 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 88 dm_bht_bin_to_hex(computed, computed_hex, bht->digest_size); | 88 dm_bht_bin_to_hex(computed, computed_hex, bht->digest_size); |
| 89 DMERR_LIMIT("%s != %s", given_hex, computed_hex); | 89 DMERR_LIMIT("%s != %s", given_hex, computed_hex); |
| 90 } | 90 } |
| 91 | 91 |
| 92 /* Used for turning verifiers into computers */ | 92 /* Used for turning verifiers into computers */ |
| 93 typedef int (*dm_bht_compare_cb)(struct dm_bht *, u8 *, u8 *); | 93 typedef int (*dm_bht_compare_cb)(struct dm_bht *, u8 *, u8 *); |
| 94 | 94 |
| 95 /** | 95 /** |
| 96 * dm_bht_compute_hash: hashes a page of data | 96 * dm_bht_compute_hash: hashes a page of data |
| 97 */ | 97 */ |
| 98 static int dm_bht_compute_hash(struct dm_bht *bht, struct page *page, | 98 static int dm_bht_compute_hash(struct dm_bht *bht, const void *block, |
| 99 u8 *digest) | 99 u8 *digest) |
| 100 { | 100 { |
| 101 struct hash_desc *hash_desc = &bht->hash_desc[smp_processor_id()]; | 101 struct hash_desc *hash_desc = &bht->hash_desc[smp_processor_id()]; |
| 102 struct scatterlist sg; | 102 struct scatterlist sg; |
| 103 | 103 |
| 104 /* TODO(msb): Once we supporting block_size < PAGE_SIZE, change this to: | |
| 105 * offset_into_page + length < page_size | |
| 106 * For now just check that block is page-aligned. | |
| 107 */ | |
| 108 BUG_ON((uintptr_t)block % PAGE_SIZE); | |
|
Will Drewry
2011/03/11 21:32:29
IS_ALIGNED(block, PAGE_SIZE)?
| |
| 109 | |
| 104 sg_init_table(&sg, 1); | 110 sg_init_table(&sg, 1); |
| 105 » sg_set_page(&sg, page, PAGE_SIZE, 0); | 111 » sg_set_buf(&sg, block, PAGE_SIZE); |
| 106 /* Note, this is synchronous. */ | 112 /* Note, this is synchronous. */ |
| 107 if (crypto_hash_init(hash_desc)) { | 113 if (crypto_hash_init(hash_desc)) { |
| 108 DMCRIT("failed to reinitialize crypto hash (proc:%d)", | 114 DMCRIT("failed to reinitialize crypto hash (proc:%d)", |
| 109 smp_processor_id()); | 115 smp_processor_id()); |
| 110 return -EINVAL; | 116 return -EINVAL; |
| 111 } | 117 } |
| 112 if (crypto_hash_digest(hash_desc, &sg, PAGE_SIZE, digest)) { | 118 if (crypto_hash_digest(hash_desc, &sg, PAGE_SIZE, digest)) { |
| 113 DMCRIT("crypto_hash_digest failed"); | 119 DMCRIT("crypto_hash_digest failed"); |
| 114 return -EINVAL; | 120 return -EINVAL; |
| 115 } | 121 } |
| (...skipping 478 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 594 block_index); | 600 block_index); |
| 595 u8 digest[DM_BHT_MAX_DIGEST_SIZE]; | 601 u8 digest[DM_BHT_MAX_DIGEST_SIZE]; |
| 596 u8 *node; | 602 u8 *node; |
| 597 | 603 |
| 598 /* This call is only safe if all nodes along the path | 604 /* This call is only safe if all nodes along the path |
| 599 * are already populated (i.e. READY) via dm_bht_populate. | 605 * are already populated (i.e. READY) via dm_bht_populate. |
| 600 */ | 606 */ |
| 601 BUG_ON(atomic_read(&parent->state) < DM_BHT_ENTRY_READY); | 607 BUG_ON(atomic_read(&parent->state) < DM_BHT_ENTRY_READY); |
| 602 | 608 |
| 603 node = dm_bht_get_node(bht, parent, depth, block_index); | 609 node = dm_bht_get_node(bht, parent, depth, block_index); |
| 604 » if (dm_bht_compute_hash(bht, virt_to_page(block), digest) || | 610 » if (dm_bht_compute_hash(bht, block, digest) || |
| 605 dm_bht_compare_hash(bht, digest, node)) { | 611 dm_bht_compare_hash(bht, digest, node)) { |
| 606 DMERR("failed to verify entry's hash against parent " | 612 DMERR("failed to verify entry's hash against parent " |
| 607 "(d=%u,bi=%u)", depth, block_index); | 613 "(d=%u,bi=%u)", depth, block_index); |
| 608 return DM_BHT_ENTRY_ERROR_MISMATCH; | 614 return DM_BHT_ENTRY_ERROR_MISMATCH; |
| 609 } | 615 } |
| 610 return 0; | 616 return 0; |
| 611 } | 617 } |
| 612 | 618 |
| 613 /* Walk all entries at level 0 to compute the root digest. | 619 /* Walk all entries at level 0 to compute the root digest. |
| 614 * 0 on success. | 620 * 0 on success. |
| (...skipping 14 matching lines...) Expand all Loading... | |
| 629 } | 635 } |
| 630 | 636 |
| 631 /* Point the scatterlist to the entries, then compute the digest */ | 637 /* Point the scatterlist to the entries, then compute the digest */ |
| 632 for (count = 0; count < bht->levels[0].count; ++count, ++entry) { | 638 for (count = 0; count < bht->levels[0].count; ++count, ++entry) { |
| 633 if (atomic_read(&entry->state) <= DM_BHT_ENTRY_PENDING) { | 639 if (atomic_read(&entry->state) <= DM_BHT_ENTRY_PENDING) { |
| 634 DMCRIT("data not ready to compute root: %u", | 640 DMCRIT("data not ready to compute root: %u", |
| 635 count); | 641 count); |
| 636 return 1; | 642 return 1; |
| 637 } | 643 } |
| 638 sg_init_table(&sg, 1); | 644 sg_init_table(&sg, 1); |
| 639 » » sg_set_page(&sg, virt_to_page(entry->nodes), PAGE_SIZE, 0); | 645 » » sg_set_buf(&sg, entry->nodes, PAGE_SIZE); |
| 640 if (crypto_hash_update(hash_desc, &sg, PAGE_SIZE)) { | 646 if (crypto_hash_update(hash_desc, &sg, PAGE_SIZE)) { |
| 641 DMCRIT("Failed to update crypto hash"); | 647 DMCRIT("Failed to update crypto hash"); |
| 642 return -EINVAL; | 648 return -EINVAL; |
| 643 } | 649 } |
| 644 } | 650 } |
| 645 | 651 |
| 646 if (crypto_hash_final(hash_desc, digest)) { | 652 if (crypto_hash_final(hash_desc, digest)) { |
| 647 DMCRIT("Failed to compute final digest"); | 653 DMCRIT("Failed to compute final digest"); |
| 648 return -EINVAL; | 654 return -EINVAL; |
| 649 } | 655 } |
| (...skipping 29 matching lines...) Expand all Loading... | |
| 679 * Verifies the path from block_index to depth=0. Returns 0 on ok. | 685 * Verifies the path from block_index to depth=0. Returns 0 on ok. |
| 680 */ | 686 */ |
| 681 static int dm_bht_verify_path(struct dm_bht *bht, unsigned int block_index) | 687 static int dm_bht_verify_path(struct dm_bht *bht, unsigned int block_index) |
| 682 { | 688 { |
| 683 unsigned int depth = bht->depth - 1; | 689 unsigned int depth = bht->depth - 1; |
| 684 struct dm_bht_entry *entry = dm_bht_get_entry(bht, depth, block_index); | 690 struct dm_bht_entry *entry = dm_bht_get_entry(bht, depth, block_index); |
| 685 | 691 |
| 686 while (depth > 0) { | 692 while (depth > 0) { |
| 687 u8 digest[DM_BHT_MAX_DIGEST_SIZE]; | 693 u8 digest[DM_BHT_MAX_DIGEST_SIZE]; |
| 688 struct dm_bht_entry *parent; | 694 struct dm_bht_entry *parent; |
| 689 struct page *page; | |
| 690 u8 *node; | 695 u8 *node; |
| 691 int state; | 696 int state; |
| 692 | 697 |
| 693 DMDEBUG("verify_path for b=%u on d=%d", block_index, depth); | 698 DMDEBUG("verify_path for b=%u on d=%d", block_index, depth); |
| 694 /* TODO(msb,wad): would be nice to avoid two atomic reads */ | 699 /* TODO(msb,wad): would be nice to avoid two atomic reads */ |
| 695 state = atomic_read(&entry->state); | 700 state = atomic_read(&entry->state); |
| 696 if (state == DM_BHT_ENTRY_VERIFIED) { | 701 if (state == DM_BHT_ENTRY_VERIFIED) { |
| 697 DMDEBUG("verify_path node %u is verified to root", | 702 DMDEBUG("verify_path node %u is verified to root", |
| 698 block_index); | 703 block_index); |
| 699 depth++; /* avoid an extra cmpxchg */ | 704 depth++; /* avoid an extra cmpxchg */ |
| (...skipping 11 matching lines...) Expand all Loading... | |
| 711 | 716 |
| 712 /* We need to check that this entry matches the expected | 717 /* We need to check that this entry matches the expected |
| 713 * hash in the parent->nodes. | 718 * hash in the parent->nodes. |
| 714 */ | 719 */ |
| 715 parent = dm_bht_get_entry(bht, depth - 1, block_index); | 720 parent = dm_bht_get_entry(bht, depth - 1, block_index); |
| 716 /* This call is only safe if all nodes along the path | 721 /* This call is only safe if all nodes along the path |
| 717 * are already populated (i.e. READY) via dm_bht_populate. | 722 * are already populated (i.e. READY) via dm_bht_populate. |
| 718 */ | 723 */ |
| 719 BUG_ON(atomic_read(&parent->state) < DM_BHT_ENTRY_READY); | 724 BUG_ON(atomic_read(&parent->state) < DM_BHT_ENTRY_READY); |
| 720 node = dm_bht_get_node(bht, parent, depth, block_index); | 725 node = dm_bht_get_node(bht, parent, depth, block_index); |
| 721 page = virt_to_page(entry->nodes); | |
| 722 | 726 |
| 723 » » if (dm_bht_compute_hash(bht, page, digest) || | 727 » » if (dm_bht_compute_hash(bht, entry->nodes, digest) || |
| 724 dm_bht_compare_hash(bht, digest, node)) { | 728 dm_bht_compare_hash(bht, digest, node)) { |
| 725 DMERR("failed to verify entry's hash against parent " | 729 DMERR("failed to verify entry's hash against parent " |
| 726 "(d=%u,bi=%u)", depth, block_index); | 730 "(d=%u,bi=%u)", depth, block_index); |
| 727 goto mismatch; | 731 goto mismatch; |
| 728 } | 732 } |
| 729 | 733 |
| 730 entry = parent; | 734 entry = parent; |
| 731 depth--; | 735 depth--; |
| 732 } | 736 } |
| 733 /* Mark path to leaf as verified. */ | 737 /* Mark path to leaf as verified. */ |
| (...skipping 76 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 810 atomic_set(&entry->state, DM_BHT_ENTRY_READY); | 814 atomic_set(&entry->state, DM_BHT_ENTRY_READY); |
| 811 } else if (state <= DM_BHT_ENTRY_ERROR) { | 815 } else if (state <= DM_BHT_ENTRY_ERROR) { |
| 812 DMCRIT("leaf entry for block %u is invalid", | 816 DMCRIT("leaf entry for block %u is invalid", |
| 813 block_index); | 817 block_index); |
| 814 return state; | 818 return state; |
| 815 } else if (state == DM_BHT_ENTRY_PENDING) { | 819 } else if (state == DM_BHT_ENTRY_PENDING) { |
| 816 DMERR("leaf data is pending for block %u", block_index); | 820 DMERR("leaf data is pending for block %u", block_index); |
| 817 return 1; | 821 return 1; |
| 818 } | 822 } |
| 819 | 823 |
| 820 » dm_bht_compute_hash(bht, virt_to_page(block_data), | 824 » dm_bht_compute_hash(bht, block_data, |
| 821 dm_bht_node(bht, entry, node_index)); | 825 dm_bht_node(bht, entry, node_index)); |
| 822 return 0; | 826 return 0; |
| 823 } | 827 } |
| 824 EXPORT_SYMBOL(dm_bht_store_block); | 828 EXPORT_SYMBOL(dm_bht_store_block); |
| 825 | 829 |
| 826 /** | 830 /** |
| 827 * dm_bht_zeroread_callback - read callback which always returns 0s | 831 * dm_bht_zeroread_callback - read callback which always returns 0s |
| 828 * @ctx: ignored | 832 * @ctx: ignored |
| 829 * @start: ignored | 833 * @start: ignored |
| 830 * @data: buffer to write 0s to | 834 * @data: buffer to write 0s to |
| (...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 876 | 880 |
| 877 r = dm_bht_maybe_read_entries(bht, read_cb_ctx, depth, | 881 r = dm_bht_maybe_read_entries(bht, read_cb_ctx, depth, |
| 878 0, level->count, true); | 882 0, level->count, true); |
| 879 if (r < 0) { | 883 if (r < 0) { |
| 880 DMCRIT("an error occurred while reading entry"); | 884 DMCRIT("an error occurred while reading entry"); |
| 881 goto out; | 885 goto out; |
| 882 } | 886 } |
| 883 | 887 |
| 884 for (i = 0; i < level->count; i++, entry++) { | 888 for (i = 0; i < level->count; i++, entry++) { |
| 885 for (j = 0; j < count; j++, child++) { | 889 for (j = 0; j < count; j++, child++) { |
| 886 » » » » struct page *pg = virt_to_page(child->nodes); | 890 » » » » u8 *block = child->nodes; |
| 887 » » » » u8 *node = dm_bht_node(bht, entry, j); | 891 » » » » u8 *digest = dm_bht_node(bht, entry, j); |
| 888 | 892 |
| 889 » » » » r = dm_bht_compute_hash(bht, pg, node); | 893 » » » » r = dm_bht_compute_hash(bht, block, digest); |
| 890 if (r) { | 894 if (r) { |
| 891 DMERR("Failed to update (d=%u,i=%u)", | 895 DMERR("Failed to update (d=%u,i=%u)", |
| 892 depth, i); | 896 depth, i); |
| 893 goto out; | 897 goto out; |
| 894 } | 898 } |
| 895 } | 899 } |
| 896 } | 900 } |
| 897 } | 901 } |
| 898 /* Don't forget the root digest! */ | 902 /* Don't forget the root digest! */ |
| 899 DMDEBUG("Calling verify_root with update_hash"); | 903 DMDEBUG("Calling verify_root with update_hash"); |
| (...skipping 142 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 1042 return populated; | 1046 return populated; |
| 1043 } | 1047 } |
| 1044 EXPORT_SYMBOL(dm_bht_populate); | 1048 EXPORT_SYMBOL(dm_bht_populate); |
| 1045 | 1049 |
| 1046 | 1050 |
| 1047 /** | 1051 /** |
| 1048 * dm_bht_verify_block - checks that all nodes in the path for @block are valid | 1052 * dm_bht_verify_block - checks that all nodes in the path for @block are valid |
| 1049 * @bht: pointer to a dm_bht_create()d bht | 1053 * @bht: pointer to a dm_bht_create()d bht |
| 1050 * @block_index:specific block data is expected from | 1054 * @block_index:specific block data is expected from |
| 1051 * @block: virtual address of the block data in memory | 1055 * @block: virtual address of the block data in memory |
| 1056 * (must be aligned to block size) | |
| 1052 * | 1057 * |
| 1053 * Returns 0 on success, 1 on missing data, and a negative error | 1058 * Returns 0 on success, 1 on missing data, and a negative error |
| 1054 * code on verification failure. All supporting functions called | 1059 * code on verification failure. All supporting functions called |
| 1055 * should return similarly. | 1060 * should return similarly. |
| 1056 */ | 1061 */ |
| 1057 int dm_bht_verify_block(struct dm_bht *bht, unsigned int block_index, | 1062 int dm_bht_verify_block(struct dm_bht *bht, unsigned int block_index, |
| 1058 const void *block) | 1063 const void *block) |
| 1059 { | 1064 { |
| 1060 int unverified = 0; | 1065 int unverified = 0; |
| 1061 | 1066 |
| (...skipping 168 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 1230 DMERR("no root digest exists to export"); | 1235 DMERR("no root digest exists to export"); |
| 1231 if (available > 0) | 1236 if (available > 0) |
| 1232 *hexdigest = 0; | 1237 *hexdigest = 0; |
| 1233 return -1; | 1238 return -1; |
| 1234 } | 1239 } |
| 1235 dm_bht_bin_to_hex(bht->root_digest, hexdigest, bht->digest_size); | 1240 dm_bht_bin_to_hex(bht->root_digest, hexdigest, bht->digest_size); |
| 1236 return 0; | 1241 return 0; |
| 1237 } | 1242 } |
| 1238 EXPORT_SYMBOL(dm_bht_root_hexdigest); | 1243 EXPORT_SYMBOL(dm_bht_root_hexdigest); |
| 1239 | 1244 |
| OLD | NEW |