123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649 |
- /*
- * Copyright (C) Qu Wenruo 2017. All rights reserved.
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public
- * License v2 as published by the Free Software Foundation.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * General Public License for more details.
- *
- * You should have received a copy of the GNU General Public
- * License along with this program.
- */
- /*
- * The module is used to catch unexpected/corrupted tree block data.
- * Such behavior can be caused either by a fuzzed image or bugs.
- *
- * The objective is to do leaf/node validation checks when tree block is read
- * from disk, and check *every* possible member, so other code won't
- * need to checking them again.
- *
- * Due to the potential and unwanted damage, every checker needs to be
- * carefully reviewed otherwise so it does not prevent mount of valid images.
- */
- #include "ctree.h"
- #include "tree-checker.h"
- #include "disk-io.h"
- #include "compression.h"
- #include "hash.h"
- #include "volumes.h"
- #define CORRUPT(reason, eb, root, slot) \
- btrfs_crit(root->fs_info, \
- "corrupt %s, %s: block=%llu, root=%llu, slot=%d", \
- btrfs_header_level(eb) == 0 ? "leaf" : "node", \
- reason, btrfs_header_bytenr(eb), root->objectid, slot)
- /*
- * Error message should follow the following format:
- * corrupt <type>: <identifier>, <reason>[, <bad_value>]
- *
- * @type: leaf or node
- * @identifier: the necessary info to locate the leaf/node.
- * It's recommened to decode key.objecitd/offset if it's
- * meaningful.
- * @reason: describe the error
- * @bad_value: optional, it's recommened to output bad value and its
- * expected value (range).
- *
- * Since comma is used to separate the components, only space is allowed
- * inside each component.
- */
- /*
- * Append generic "corrupt leaf/node root=%llu block=%llu slot=%d: " to @fmt.
- * Allows callers to customize the output.
- */
- __printf(4, 5)
- static void generic_err(const struct btrfs_root *root,
- const struct extent_buffer *eb, int slot,
- const char *fmt, ...)
- {
- struct va_format vaf;
- va_list args;
- va_start(args, fmt);
- vaf.fmt = fmt;
- vaf.va = &args;
- btrfs_crit(root->fs_info,
- "corrupt %s: root=%llu block=%llu slot=%d, %pV",
- btrfs_header_level(eb) == 0 ? "leaf" : "node",
- root->objectid, btrfs_header_bytenr(eb), slot, &vaf);
- va_end(args);
- }
- static int check_extent_data_item(struct btrfs_root *root,
- struct extent_buffer *leaf,
- struct btrfs_key *key, int slot)
- {
- struct btrfs_file_extent_item *fi;
- u32 sectorsize = root->sectorsize;
- u32 item_size = btrfs_item_size_nr(leaf, slot);
- if (!IS_ALIGNED(key->offset, sectorsize)) {
- CORRUPT("unaligned key offset for file extent",
- leaf, root, slot);
- return -EUCLEAN;
- }
- fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);
- if (btrfs_file_extent_type(leaf, fi) > BTRFS_FILE_EXTENT_TYPES) {
- CORRUPT("invalid file extent type", leaf, root, slot);
- return -EUCLEAN;
- }
- /*
- * Support for new compression/encrption must introduce incompat flag,
- * and must be caught in open_ctree().
- */
- if (btrfs_file_extent_compression(leaf, fi) > BTRFS_COMPRESS_TYPES) {
- CORRUPT("invalid file extent compression", leaf, root, slot);
- return -EUCLEAN;
- }
- if (btrfs_file_extent_encryption(leaf, fi)) {
- CORRUPT("invalid file extent encryption", leaf, root, slot);
- return -EUCLEAN;
- }
- if (btrfs_file_extent_type(leaf, fi) == BTRFS_FILE_EXTENT_INLINE) {
- /* Inline extent must have 0 as key offset */
- if (key->offset) {
- CORRUPT("inline extent has non-zero key offset",
- leaf, root, slot);
- return -EUCLEAN;
- }
- /* Compressed inline extent has no on-disk size, skip it */
- if (btrfs_file_extent_compression(leaf, fi) !=
- BTRFS_COMPRESS_NONE)
- return 0;
- /* Uncompressed inline extent size must match item size */
- if (item_size != BTRFS_FILE_EXTENT_INLINE_DATA_START +
- btrfs_file_extent_ram_bytes(leaf, fi)) {
- CORRUPT("plaintext inline extent has invalid size",
- leaf, root, slot);
- return -EUCLEAN;
- }
- return 0;
- }
- /* Regular or preallocated extent has fixed item size */
- if (item_size != sizeof(*fi)) {
- CORRUPT(
- "regluar or preallocated extent data item size is invalid",
- leaf, root, slot);
- return -EUCLEAN;
- }
- if (!IS_ALIGNED(btrfs_file_extent_ram_bytes(leaf, fi), sectorsize) ||
- !IS_ALIGNED(btrfs_file_extent_disk_bytenr(leaf, fi), sectorsize) ||
- !IS_ALIGNED(btrfs_file_extent_disk_num_bytes(leaf, fi), sectorsize) ||
- !IS_ALIGNED(btrfs_file_extent_offset(leaf, fi), sectorsize) ||
- !IS_ALIGNED(btrfs_file_extent_num_bytes(leaf, fi), sectorsize)) {
- CORRUPT(
- "regular or preallocated extent data item has unaligned value",
- leaf, root, slot);
- return -EUCLEAN;
- }
- return 0;
- }
- static int check_csum_item(struct btrfs_root *root, struct extent_buffer *leaf,
- struct btrfs_key *key, int slot)
- {
- u32 sectorsize = root->sectorsize;
- u32 csumsize = btrfs_super_csum_size(root->fs_info->super_copy);
- if (key->objectid != BTRFS_EXTENT_CSUM_OBJECTID) {
- CORRUPT("invalid objectid for csum item", leaf, root, slot);
- return -EUCLEAN;
- }
- if (!IS_ALIGNED(key->offset, sectorsize)) {
- CORRUPT("unaligned key offset for csum item", leaf, root, slot);
- return -EUCLEAN;
- }
- if (!IS_ALIGNED(btrfs_item_size_nr(leaf, slot), csumsize)) {
- CORRUPT("unaligned csum item size", leaf, root, slot);
- return -EUCLEAN;
- }
- return 0;
- }
- /*
- * Customized reported for dir_item, only important new info is key->objectid,
- * which represents inode number
- */
- __printf(4, 5)
- static void dir_item_err(const struct btrfs_root *root,
- const struct extent_buffer *eb, int slot,
- const char *fmt, ...)
- {
- struct btrfs_key key;
- struct va_format vaf;
- va_list args;
- btrfs_item_key_to_cpu(eb, &key, slot);
- va_start(args, fmt);
- vaf.fmt = fmt;
- vaf.va = &args;
- btrfs_crit(root->fs_info,
- "corrupt %s: root=%llu block=%llu slot=%d ino=%llu, %pV",
- btrfs_header_level(eb) == 0 ? "leaf" : "node", root->objectid,
- btrfs_header_bytenr(eb), slot, key.objectid, &vaf);
- va_end(args);
- }
- static int check_dir_item(struct btrfs_root *root,
- struct extent_buffer *leaf,
- struct btrfs_key *key, int slot)
- {
- struct btrfs_dir_item *di;
- u32 item_size = btrfs_item_size_nr(leaf, slot);
- u32 cur = 0;
- di = btrfs_item_ptr(leaf, slot, struct btrfs_dir_item);
- while (cur < item_size) {
- u32 name_len;
- u32 data_len;
- u32 max_name_len;
- u32 total_size;
- u32 name_hash;
- u8 dir_type;
- /* header itself should not cross item boundary */
- if (cur + sizeof(*di) > item_size) {
- dir_item_err(root, leaf, slot,
- "dir item header crosses item boundary, have %zu boundary %u",
- cur + sizeof(*di), item_size);
- return -EUCLEAN;
- }
- /* dir type check */
- dir_type = btrfs_dir_type(leaf, di);
- if (dir_type >= BTRFS_FT_MAX) {
- dir_item_err(root, leaf, slot,
- "invalid dir item type, have %u expect [0, %u)",
- dir_type, BTRFS_FT_MAX);
- return -EUCLEAN;
- }
- if (key->type == BTRFS_XATTR_ITEM_KEY &&
- dir_type != BTRFS_FT_XATTR) {
- dir_item_err(root, leaf, slot,
- "invalid dir item type for XATTR key, have %u expect %u",
- dir_type, BTRFS_FT_XATTR);
- return -EUCLEAN;
- }
- if (dir_type == BTRFS_FT_XATTR &&
- key->type != BTRFS_XATTR_ITEM_KEY) {
- dir_item_err(root, leaf, slot,
- "xattr dir type found for non-XATTR key");
- return -EUCLEAN;
- }
- if (dir_type == BTRFS_FT_XATTR)
- max_name_len = XATTR_NAME_MAX;
- else
- max_name_len = BTRFS_NAME_LEN;
- /* Name/data length check */
- name_len = btrfs_dir_name_len(leaf, di);
- data_len = btrfs_dir_data_len(leaf, di);
- if (name_len > max_name_len) {
- dir_item_err(root, leaf, slot,
- "dir item name len too long, have %u max %u",
- name_len, max_name_len);
- return -EUCLEAN;
- }
- if (name_len + data_len > BTRFS_MAX_XATTR_SIZE(root)) {
- dir_item_err(root, leaf, slot,
- "dir item name and data len too long, have %u max %zu",
- name_len + data_len,
- BTRFS_MAX_XATTR_SIZE(root));
- return -EUCLEAN;
- }
- if (data_len && dir_type != BTRFS_FT_XATTR) {
- dir_item_err(root, leaf, slot,
- "dir item with invalid data len, have %u expect 0",
- data_len);
- return -EUCLEAN;
- }
- total_size = sizeof(*di) + name_len + data_len;
- /* header and name/data should not cross item boundary */
- if (cur + total_size > item_size) {
- dir_item_err(root, leaf, slot,
- "dir item data crosses item boundary, have %u boundary %u",
- cur + total_size, item_size);
- return -EUCLEAN;
- }
- /*
- * Special check for XATTR/DIR_ITEM, as key->offset is name
- * hash, should match its name
- */
- if (key->type == BTRFS_DIR_ITEM_KEY ||
- key->type == BTRFS_XATTR_ITEM_KEY) {
- char namebuf[max(BTRFS_NAME_LEN, XATTR_NAME_MAX)];
- read_extent_buffer(leaf, namebuf,
- (unsigned long)(di + 1), name_len);
- name_hash = btrfs_name_hash(namebuf, name_len);
- if (key->offset != name_hash) {
- dir_item_err(root, leaf, slot,
- "name hash mismatch with key, have 0x%016x expect 0x%016llx",
- name_hash, key->offset);
- return -EUCLEAN;
- }
- }
- cur += total_size;
- di = (struct btrfs_dir_item *)((void *)di + total_size);
- }
- return 0;
- }
- __printf(4, 5)
- __cold
- static void block_group_err(const struct btrfs_fs_info *fs_info,
- const struct extent_buffer *eb, int slot,
- const char *fmt, ...)
- {
- struct btrfs_key key;
- struct va_format vaf;
- va_list args;
- btrfs_item_key_to_cpu(eb, &key, slot);
- va_start(args, fmt);
- vaf.fmt = fmt;
- vaf.va = &args;
- btrfs_crit(fs_info,
- "corrupt %s: root=%llu block=%llu slot=%d bg_start=%llu bg_len=%llu, %pV",
- btrfs_header_level(eb) == 0 ? "leaf" : "node",
- btrfs_header_owner(eb), btrfs_header_bytenr(eb), slot,
- key.objectid, key.offset, &vaf);
- va_end(args);
- }
- static int check_block_group_item(struct btrfs_fs_info *fs_info,
- struct extent_buffer *leaf,
- struct btrfs_key *key, int slot)
- {
- struct btrfs_block_group_item bgi;
- u32 item_size = btrfs_item_size_nr(leaf, slot);
- u64 flags;
- u64 type;
- /*
- * Here we don't really care about alignment since extent allocator can
- * handle it. We care more about the size, as if one block group is
- * larger than maximum size, it's must be some obvious corruption.
- */
- if (key->offset > BTRFS_MAX_DATA_CHUNK_SIZE || key->offset == 0) {
- block_group_err(fs_info, leaf, slot,
- "invalid block group size, have %llu expect (0, %llu]",
- key->offset, BTRFS_MAX_DATA_CHUNK_SIZE);
- return -EUCLEAN;
- }
- if (item_size != sizeof(bgi)) {
- block_group_err(fs_info, leaf, slot,
- "invalid item size, have %u expect %zu",
- item_size, sizeof(bgi));
- return -EUCLEAN;
- }
- read_extent_buffer(leaf, &bgi, btrfs_item_ptr_offset(leaf, slot),
- sizeof(bgi));
- if (btrfs_block_group_chunk_objectid(&bgi) !=
- BTRFS_FIRST_CHUNK_TREE_OBJECTID) {
- block_group_err(fs_info, leaf, slot,
- "invalid block group chunk objectid, have %llu expect %llu",
- btrfs_block_group_chunk_objectid(&bgi),
- BTRFS_FIRST_CHUNK_TREE_OBJECTID);
- return -EUCLEAN;
- }
- if (btrfs_block_group_used(&bgi) > key->offset) {
- block_group_err(fs_info, leaf, slot,
- "invalid block group used, have %llu expect [0, %llu)",
- btrfs_block_group_used(&bgi), key->offset);
- return -EUCLEAN;
- }
- flags = btrfs_block_group_flags(&bgi);
- if (hweight64(flags & BTRFS_BLOCK_GROUP_PROFILE_MASK) > 1) {
- block_group_err(fs_info, leaf, slot,
- "invalid profile flags, have 0x%llx (%lu bits set) expect no more than 1 bit set",
- flags & BTRFS_BLOCK_GROUP_PROFILE_MASK,
- hweight64(flags & BTRFS_BLOCK_GROUP_PROFILE_MASK));
- return -EUCLEAN;
- }
- type = flags & BTRFS_BLOCK_GROUP_TYPE_MASK;
- if (type != BTRFS_BLOCK_GROUP_DATA &&
- type != BTRFS_BLOCK_GROUP_METADATA &&
- type != BTRFS_BLOCK_GROUP_SYSTEM &&
- type != (BTRFS_BLOCK_GROUP_METADATA |
- BTRFS_BLOCK_GROUP_DATA)) {
- block_group_err(fs_info, leaf, slot,
- "invalid type, have 0x%llx (%lu bits set) expect either 0x%llx, 0x%llx, 0x%llx or 0x%llx",
- type, hweight64(type),
- BTRFS_BLOCK_GROUP_DATA, BTRFS_BLOCK_GROUP_METADATA,
- BTRFS_BLOCK_GROUP_SYSTEM,
- BTRFS_BLOCK_GROUP_METADATA | BTRFS_BLOCK_GROUP_DATA);
- return -EUCLEAN;
- }
- return 0;
- }
- /*
- * Common point to switch the item-specific validation.
- */
- static int check_leaf_item(struct btrfs_root *root,
- struct extent_buffer *leaf,
- struct btrfs_key *key, int slot)
- {
- int ret = 0;
- switch (key->type) {
- case BTRFS_EXTENT_DATA_KEY:
- ret = check_extent_data_item(root, leaf, key, slot);
- break;
- case BTRFS_EXTENT_CSUM_KEY:
- ret = check_csum_item(root, leaf, key, slot);
- break;
- case BTRFS_DIR_ITEM_KEY:
- case BTRFS_DIR_INDEX_KEY:
- case BTRFS_XATTR_ITEM_KEY:
- ret = check_dir_item(root, leaf, key, slot);
- break;
- case BTRFS_BLOCK_GROUP_ITEM_KEY:
- ret = check_block_group_item(root->fs_info, leaf, key, slot);
- break;
- }
- return ret;
- }
- static int check_leaf(struct btrfs_root *root, struct extent_buffer *leaf,
- bool check_item_data)
- {
- struct btrfs_fs_info *fs_info = root->fs_info;
- /* No valid key type is 0, so all key should be larger than this key */
- struct btrfs_key prev_key = {0, 0, 0};
- struct btrfs_key key;
- u32 nritems = btrfs_header_nritems(leaf);
- int slot;
- if (btrfs_header_level(leaf) != 0) {
- generic_err(root, leaf, 0,
- "invalid level for leaf, have %d expect 0",
- btrfs_header_level(leaf));
- return -EUCLEAN;
- }
- /*
- * Extent buffers from a relocation tree have a owner field that
- * corresponds to the subvolume tree they are based on. So just from an
- * extent buffer alone we can not find out what is the id of the
- * corresponding subvolume tree, so we can not figure out if the extent
- * buffer corresponds to the root of the relocation tree or not. So
- * skip this check for relocation trees.
- */
- if (nritems == 0 && !btrfs_header_flag(leaf, BTRFS_HEADER_FLAG_RELOC)) {
- u64 owner = btrfs_header_owner(leaf);
- struct btrfs_root *check_root;
- /* These trees must never be empty */
- if (owner == BTRFS_ROOT_TREE_OBJECTID ||
- owner == BTRFS_CHUNK_TREE_OBJECTID ||
- owner == BTRFS_EXTENT_TREE_OBJECTID ||
- owner == BTRFS_DEV_TREE_OBJECTID ||
- owner == BTRFS_FS_TREE_OBJECTID ||
- owner == BTRFS_DATA_RELOC_TREE_OBJECTID) {
- generic_err(root, leaf, 0,
- "invalid root, root %llu must never be empty",
- owner);
- return -EUCLEAN;
- }
- key.objectid = owner;
- key.type = BTRFS_ROOT_ITEM_KEY;
- key.offset = (u64)-1;
- check_root = btrfs_get_fs_root(fs_info, &key, false);
- /*
- * The only reason we also check NULL here is that during
- * open_ctree() some roots has not yet been set up.
- */
- if (!IS_ERR_OR_NULL(check_root)) {
- struct extent_buffer *eb;
- eb = btrfs_root_node(check_root);
- /* if leaf is the root, then it's fine */
- if (leaf != eb) {
- CORRUPT("non-root leaf's nritems is 0",
- leaf, check_root, 0);
- free_extent_buffer(eb);
- return -EUCLEAN;
- }
- free_extent_buffer(eb);
- }
- return 0;
- }
- if (nritems == 0)
- return 0;
- /*
- * Check the following things to make sure this is a good leaf, and
- * leaf users won't need to bother with similar sanity checks:
- *
- * 1) key ordering
- * 2) item offset and size
- * No overlap, no hole, all inside the leaf.
- * 3) item content
- * If possible, do comprehensive sanity check.
- * NOTE: All checks must only rely on the item data itself.
- */
- for (slot = 0; slot < nritems; slot++) {
- u32 item_end_expected;
- int ret;
- btrfs_item_key_to_cpu(leaf, &key, slot);
- /* Make sure the keys are in the right order */
- if (btrfs_comp_cpu_keys(&prev_key, &key) >= 0) {
- CORRUPT("bad key order", leaf, root, slot);
- return -EUCLEAN;
- }
- /*
- * Make sure the offset and ends are right, remember that the
- * item data starts at the end of the leaf and grows towards the
- * front.
- */
- if (slot == 0)
- item_end_expected = BTRFS_LEAF_DATA_SIZE(root);
- else
- item_end_expected = btrfs_item_offset_nr(leaf,
- slot - 1);
- if (btrfs_item_end_nr(leaf, slot) != item_end_expected) {
- CORRUPT("slot offset bad", leaf, root, slot);
- return -EUCLEAN;
- }
- /*
- * Check to make sure that we don't point outside of the leaf,
- * just in case all the items are consistent to each other, but
- * all point outside of the leaf.
- */
- if (btrfs_item_end_nr(leaf, slot) >
- BTRFS_LEAF_DATA_SIZE(root)) {
- CORRUPT("slot end outside of leaf", leaf, root, slot);
- return -EUCLEAN;
- }
- /* Also check if the item pointer overlaps with btrfs item. */
- if (btrfs_item_nr_offset(slot) + sizeof(struct btrfs_item) >
- btrfs_item_ptr_offset(leaf, slot)) {
- CORRUPT("slot overlap with its data", leaf, root, slot);
- return -EUCLEAN;
- }
- if (check_item_data) {
- /*
- * Check if the item size and content meet other
- * criteria
- */
- ret = check_leaf_item(root, leaf, &key, slot);
- if (ret < 0)
- return ret;
- }
- prev_key.objectid = key.objectid;
- prev_key.type = key.type;
- prev_key.offset = key.offset;
- }
- return 0;
- }
- int btrfs_check_leaf_full(struct btrfs_root *root, struct extent_buffer *leaf)
- {
- return check_leaf(root, leaf, true);
- }
- int btrfs_check_leaf_relaxed(struct btrfs_root *root,
- struct extent_buffer *leaf)
- {
- return check_leaf(root, leaf, false);
- }
- int btrfs_check_node(struct btrfs_root *root, struct extent_buffer *node)
- {
- unsigned long nr = btrfs_header_nritems(node);
- struct btrfs_key key, next_key;
- int slot;
- int level = btrfs_header_level(node);
- u64 bytenr;
- int ret = 0;
- if (level <= 0 || level >= BTRFS_MAX_LEVEL) {
- generic_err(root, node, 0,
- "invalid level for node, have %d expect [1, %d]",
- level, BTRFS_MAX_LEVEL - 1);
- return -EUCLEAN;
- }
- if (nr == 0 || nr > BTRFS_NODEPTRS_PER_BLOCK(root)) {
- btrfs_crit(root->fs_info,
- "corrupt node: root=%llu block=%llu, nritems too %s, have %lu expect range [1,%zu]",
- root->objectid, node->start,
- nr == 0 ? "small" : "large", nr,
- BTRFS_NODEPTRS_PER_BLOCK(root));
- return -EUCLEAN;
- }
- for (slot = 0; slot < nr - 1; slot++) {
- bytenr = btrfs_node_blockptr(node, slot);
- btrfs_node_key_to_cpu(node, &key, slot);
- btrfs_node_key_to_cpu(node, &next_key, slot + 1);
- if (!bytenr) {
- generic_err(root, node, slot,
- "invalid NULL node pointer");
- ret = -EUCLEAN;
- goto out;
- }
- if (!IS_ALIGNED(bytenr, root->sectorsize)) {
- generic_err(root, node, slot,
- "unaligned pointer, have %llu should be aligned to %u",
- bytenr, root->sectorsize);
- ret = -EUCLEAN;
- goto out;
- }
- if (btrfs_comp_cpu_keys(&key, &next_key) >= 0) {
- generic_err(root, node, slot,
- "bad key order, current (%llu %u %llu) next (%llu %u %llu)",
- key.objectid, key.type, key.offset,
- next_key.objectid, next_key.type,
- next_key.offset);
- ret = -EUCLEAN;
- goto out;
- }
- }
- out:
- return ret;
- }
|