* [PATCH 0/3] btrfs: tree-checker: Add extent items check @ 2019-07-29 7:43 Qu Wenruo 2019-07-29 7:43 ` [PATCH 1/3] btrfs: tree-checker: Add EXTENT_ITEM and METADATA_ITEM check Qu Wenruo ` (2 more replies) 0 siblings, 3 replies; 6+ messages in thread From: Qu Wenruo @ 2019-07-29 7:43 UTC (permalink / raw) To: linux-btrfs Finally, we are going to add tree-checker support for extent items, which includes: - EXTENT_ITEM/METADATA_ITEM Which futher contains inline backrefs of: * TREE_BLOCK_REF * SHARED_BLOCK_REF * EXETNT_DATA_REF * SHARED_DATA_REF - TREE_BLOCK_REF - SHARED_BLOCK_REF - EXTENT_DATA_REF - SHARED_DATA_REF Keyed version of the above types The complexity of the on-disk format can be found in the first patch, which contains a basic introduction as comment. Hidden pitfalls are everywhere, e.g. inlined EXTENT_DATA_REF don't use iref->offset, but put its own data at iref->offset. But SHARED_DATA_REF uses iref->offset, and put extra data after iref. Such on-disk layout makes sense, but definitely a mess to read. Thankfully we at least have print-tree code from btrfs-progs as a reference. Qu Wenruo (3): btrfs: tree-checker: Add EXTENT_ITEM and METADATA_ITEM check btrfs: tree-checker: Add simple keyed refs check btrfs: tree-checker: Add EXTENT_DATA_REF check fs/btrfs/ctree.h | 1 + fs/btrfs/extent-tree.c | 2 +- fs/btrfs/tree-checker.c | 335 ++++++++++++++++++++++++++++++++++++++++ 3 files changed, 337 insertions(+), 1 deletion(-) -- 2.22.0 ^ permalink raw reply [flat|nested] 6+ messages in thread
* [PATCH 1/3] btrfs: tree-checker: Add EXTENT_ITEM and METADATA_ITEM check 2019-07-29 7:43 [PATCH 0/3] btrfs: tree-checker: Add extent items check Qu Wenruo @ 2019-07-29 7:43 ` Qu Wenruo 2019-07-29 13:42 ` Nikolay Borisov 2019-07-29 7:43 ` [PATCH 2/3] btrfs: tree-checker: Add simple keyed refs check Qu Wenruo 2019-07-29 7:43 ` [PATCH 3/3] btrfs: tree-checker: Add EXTENT_DATA_REF check Qu Wenruo 2 siblings, 1 reply; 6+ messages in thread From: Qu Wenruo @ 2019-07-29 7:43 UTC (permalink / raw) To: linux-btrfs This patch introduces the ability to check extent items. This check involves: - key->objectid check Basic alignment check. - key->type check Against btrfs_extent_item::type and SKINNY_METADATA feature. - key->offset alignment check for EXTENT_ITEM - key->offset check for METADATA_ITEM - item size check Both against minimal size and stepping check. - btrfs_extent_item check Checks its flags and generation. - btrfs_extent_inline_ref checks Against 4 types inline ref. Checks bytenr alignment and tree level. - btrfs_extent_item::refs check Check against total refs found in inline refs. This check would be the most complex single item check due to its nature of inlined items. Signed-off-by: Qu Wenruo <wqu@suse.com> --- fs/btrfs/tree-checker.c | 249 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 249 insertions(+) diff --git a/fs/btrfs/tree-checker.c b/fs/btrfs/tree-checker.c index 71bbbce3076d..1e97bb127893 100644 --- a/fs/btrfs/tree-checker.c +++ b/fs/btrfs/tree-checker.c @@ -899,6 +899,251 @@ static int check_root_item(struct extent_buffer *leaf, struct btrfs_key *key, return 0; } +__printf(3,4) +__cold +static void extent_err(const struct extent_buffer *eb, int slot, + const char *fmt, ...) +{ + struct btrfs_key key; + struct va_format vaf; + va_list args; + u64 bytenr; + u64 len; + + btrfs_item_key_to_cpu(eb, &key, slot); + bytenr = key.objectid; + if (key.type == BTRFS_METADATA_ITEM_KEY) + len = eb->fs_info->nodesize; + else + len = key.offset; + va_start(args, fmt); + + vaf.fmt = fmt; + vaf.va = &args; + + btrfs_crit(eb->fs_info, + "corrupt %s: block=%llu slot=%d extent bytenr=%llu len=%llu %pV", + btrfs_header_level(eb) == 0 ? "leaf" : "node", + eb->start, slot, bytenr, len, &vaf); + va_end(args); +} + +static int check_extent_item(struct extent_buffer *leaf, + struct btrfs_key *key, int slot) +{ + struct btrfs_fs_info *fs_info = leaf->fs_info; + struct btrfs_extent_item *ei; + bool is_tree_block = false; + u64 ptr; /* Current pointer inside inline refs */ + u64 end; /* Extent item end */ + u32 item_size = btrfs_item_size_nr(leaf, slot); + u64 flags; + u64 generation; + u64 total_refs; /* Total refs in btrfs_extent_item */ + u64 inline_refs = 0; /* found total inline refs */ + + if (key->type == BTRFS_METADATA_ITEM_KEY && + !btrfs_fs_incompat(fs_info, SKINNY_METADATA)) { + generic_err(leaf, slot, +"invalid key type, METADATA_ITEM type invalid when SKINNY_METADATA feature disabled"); + return -EUCLEAN; + } + /* key->objectid is the bytenr for both key types */ + if (!IS_ALIGNED(key->objectid, fs_info->sectorsize)) { + generic_err(leaf, slot, +"invalid key objectid, have %llu expect to be aligned to %u", + key->objectid, fs_info->sectorsize); + return -EUCLEAN; + } + + /* key->offset is tree level for METADATA_ITEM_KEY */ + if (key->type == BTRFS_METADATA_ITEM_KEY) { + if (key->offset >= BTRFS_MAX_LEVEL) { + extent_err(leaf, slot, + "invalid tree level, have %llu expect [0, %u]", + key->offset, BTRFS_MAX_LEVEL - 1); + return -EUCLEAN; + } + } + + /* + * EXTENT/METADATA_ITEM is consistent of: + * 1) One btrfs_extent_item + * Records the total refs, type and generation of the extent. + * + * 2) One btrfs_tree_block_info (for EXTENT_ITEM and tree backref only) + * Records the first key and level of the tree block. + * + * 2) *Zero* or more btrfs_extent_inline_ref(s) + * Each inline ref has one btrfs_extent_inline_ref shows: + * 2.1) The ref type, one of the 4 + * TREE_BLOCK_REF Tree block only + * SHARED_BLOCK_REF Tree block only + * EXTENT_DATA_REF Data only + * SHARED_DATA_REF Data only + * 2.2) Ref type specific data + * Either using btrfs_extent_inline_ref::offset, or specific + * data structure. + */ + if (item_size < sizeof(*ei)) { + extent_err(leaf, slot, + "invalid item size, have %u expect >= %lu", + item_size, sizeof(*ei)); + return -EUCLEAN; + } + end = item_size + btrfs_item_ptr_offset(leaf, slot); + + /* Checks against extent_item */ + ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item); + flags = btrfs_extent_flags(leaf, ei); + total_refs = btrfs_extent_refs(leaf, ei); + generation = btrfs_extent_generation(leaf, ei); + if (generation > btrfs_super_generation(fs_info->super_copy) + 1) { + extent_err(leaf, slot, + "invalid generation, have %llu expect <= %llu", + generation, + btrfs_super_generation(fs_info->super_copy) + 1); + return -EUCLEAN; + } + if (!is_power_of_2(flags & (BTRFS_EXTENT_FLAG_DATA | + BTRFS_EXTENT_FLAG_TREE_BLOCK))) { + extent_err(leaf, slot, + "invalid extent flag, have 0x%llx expect 1 bit set in 0x%llx", + flags, BTRFS_EXTENT_FLAG_DATA | + BTRFS_EXTENT_FLAG_TREE_BLOCK); + return -EUCLEAN; + } + is_tree_block = !!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK); + if (is_tree_block && key->type == BTRFS_EXTENT_ITEM_KEY && + key->offset != fs_info->nodesize) { + extent_err(leaf, slot, + "invalid extent length, have %llu expect %u", + key->offset, fs_info->nodesize); + return -EUCLEAN; + } + if (!is_tree_block) { + if (key->type != BTRFS_EXTENT_ITEM_KEY) { + extent_err(leaf, slot, + "invalid key type, have %u expect %u for data backref", + key->type, BTRFS_EXTENT_ITEM_KEY); + return -EUCLEAN; + } + if (!IS_ALIGNED(key->offset, fs_info->sectorsize)) { + extent_err(leaf, slot, + "invalid extent length, have %llu expect aliged to %u", + key->offset, fs_info->sectorsize); + return -EUCLEAN; + } + } + ptr = (u64)(struct btrfs_extent_item *)(ei + 1); + + /* Check the special case of btrfs_tree_block_info */ + if (is_tree_block && key->type != BTRFS_METADATA_ITEM_KEY) { + struct btrfs_tree_block_info *info; + + info = (struct btrfs_tree_block_info *)ptr; + if (btrfs_tree_block_level(leaf, info) >= BTRFS_MAX_LEVEL) { + extent_err(leaf, slot, + "invalid tree block info level, have %u expect [0, %u)", + btrfs_tree_block_level(leaf, info), + BTRFS_MAX_LEVEL - 1); + return -EUCLEAN; + } + ptr = (u64)(struct btrfs_tree_block_info *)(info + 1); + } + + /* Check inline refs */ + while (ptr < end) { + struct btrfs_extent_inline_ref *iref; + struct btrfs_extent_data_ref *dref; + struct btrfs_shared_data_ref *sref; + u64 dref_offset; + u64 inline_offset; + u8 inline_type; + + if (ptr + sizeof(*iref) > end) { + extent_err(leaf, slot, + "invalid item size, size too small, ptr %llu end %llu", + ptr, end); + goto err; + } + iref = (struct btrfs_extent_inline_ref *)ptr; + inline_type = btrfs_extent_inline_ref_type(leaf, iref); + inline_offset = btrfs_extent_inline_ref_offset(leaf, iref); + if (ptr + btrfs_extent_inline_ref_size(inline_type) > end) { + extent_err(leaf, slot, + "invalid item size, size too small, ptr %llu end %llu", + ptr, end); + goto err; + } + + switch (inline_type) { + /* inline_offset is subvolid of the owner, no need to check */ + case BTRFS_TREE_BLOCK_REF_KEY: + inline_refs++; + break; + /* contains parent bytenr */ + case BTRFS_SHARED_BLOCK_REF_KEY: + if (!IS_ALIGNED(inline_offset, fs_info->sectorsize)) { + extent_err(leaf, slot, + "invalid tree parent bytenr, have %llu expect aligned to %u", + inline_offset, fs_info->sectorsize); + goto err; + } + inline_refs++; + break; + /* + * contains owner subvolid, owner key objectid, adjusted offset. + * the only obvious corruption can happen in that offset. + */ + case BTRFS_EXTENT_DATA_REF_KEY: + dref = (struct btrfs_extent_data_ref *)(&iref->offset); + dref_offset = btrfs_extent_data_ref_offset(leaf, dref); + if (!IS_ALIGNED(dref_offset, fs_info->sectorsize)) { + extent_err(leaf, slot, + "invalid data ref offset, have %llu expect aligned to %u", + dref_offset, fs_info->sectorsize); + goto err; + } + inline_refs += btrfs_extent_data_ref_count(leaf, dref); + break; + /* contains parent bytenr and ref count */ + case BTRFS_SHARED_DATA_REF_KEY: + sref = (struct btrfs_shared_data_ref *)(iref + 1); + if (!IS_ALIGNED(inline_offset, fs_info->sectorsize)) { + extent_err(leaf, slot, + "invalid data parent bytenr, have %llu expect aligned to %u", + inline_offset, fs_info->sectorsize); + goto err; + } + inline_refs += btrfs_shared_data_ref_count(leaf, sref); + break; + default: + extent_err(leaf, slot, "unknown inline ref type: %u", + inline_type); + goto err; + } + ptr += btrfs_extent_inline_ref_size(inline_type); + } + /* No padding is allowed */ + if (ptr != end) { + extent_err(leaf, slot, + "invalid extent item size, padding bytes found"); + goto err; + } + + /* Finally, check the inline refs against total refs */ + if (total_refs < inline_refs) { + extent_err(leaf, slot, + "invalid extent refs, have %llu expect >= %llu", + total_refs, inline_refs); + goto err; + } + return 0; +err: + return -EUCLEAN; +} + /* * Common point to switch the item-specific validation. */ @@ -937,6 +1182,10 @@ static int check_leaf_item(struct extent_buffer *leaf, case BTRFS_ROOT_ITEM_KEY: ret = check_root_item(leaf, key, slot); break; + case BTRFS_EXTENT_ITEM_KEY: + case BTRFS_METADATA_ITEM_KEY: + ret = check_extent_item(leaf, key, slot); + break; } return ret; } -- 2.22.0 ^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [PATCH 1/3] btrfs: tree-checker: Add EXTENT_ITEM and METADATA_ITEM check 2019-07-29 7:43 ` [PATCH 1/3] btrfs: tree-checker: Add EXTENT_ITEM and METADATA_ITEM check Qu Wenruo @ 2019-07-29 13:42 ` Nikolay Borisov 2019-07-29 13:53 ` Qu Wenruo 0 siblings, 1 reply; 6+ messages in thread From: Nikolay Borisov @ 2019-07-29 13:42 UTC (permalink / raw) To: Qu Wenruo, linux-btrfs On 29.07.19 г. 10:43 ч., Qu Wenruo wrote: > This patch introduces the ability to check extent items. > > This check involves: > - key->objectid check > Basic alignment check. > > - key->type check > Against btrfs_extent_item::type and SKINNY_METADATA feature. > > - key->offset alignment check for EXTENT_ITEM > > - key->offset check for METADATA_ITEM > > - item size check > Both against minimal size and stepping check. > > - btrfs_extent_item check > Checks its flags and generation. > > - btrfs_extent_inline_ref checks > Against 4 types inline ref. > Checks bytenr alignment and tree level. > > - btrfs_extent_item::refs check > Check against total refs found in inline refs. > > This check would be the most complex single item check due to its nature > of inlined items. > > Signed-off-by: Qu Wenruo <wqu@suse.com> > --- > fs/btrfs/tree-checker.c | 249 ++++++++++++++++++++++++++++++++++++++++ > 1 file changed, 249 insertions(+) > > diff --git a/fs/btrfs/tree-checker.c b/fs/btrfs/tree-checker.c > index 71bbbce3076d..1e97bb127893 100644 > --- a/fs/btrfs/tree-checker.c > +++ b/fs/btrfs/tree-checker.c > @@ -899,6 +899,251 @@ static int check_root_item(struct extent_buffer *leaf, struct btrfs_key *key, > return 0; > } > > +__printf(3,4) > +__cold > +static void extent_err(const struct extent_buffer *eb, int slot, > + const char *fmt, ...) > +{ > + struct btrfs_key key; > + struct va_format vaf; > + va_list args; > + u64 bytenr; > + u64 len; > + > + btrfs_item_key_to_cpu(eb, &key, slot); > + bytenr = key.objectid; > + if (key.type == BTRFS_METADATA_ITEM_KEY) > + len = eb->fs_info->nodesize; > + else > + len = key.offset; > + va_start(args, fmt); > + > + vaf.fmt = fmt; > + vaf.va = &args; > + > + btrfs_crit(eb->fs_info, > + "corrupt %s: block=%llu slot=%d extent bytenr=%llu len=%llu %pV", > + btrfs_header_level(eb) == 0 ? "leaf" : "node", > + eb->start, slot, bytenr, len, &vaf); > + va_end(args); > +} > + > +static int check_extent_item(struct extent_buffer *leaf, > + struct btrfs_key *key, int slot) > +{ > + struct btrfs_fs_info *fs_info = leaf->fs_info; > + struct btrfs_extent_item *ei; > + bool is_tree_block = false; > + u64 ptr; /* Current pointer inside inline refs */ > + u64 end; /* Extent item end */ > + u32 item_size = btrfs_item_size_nr(leaf, slot); > + u64 flags; > + u64 generation; > + u64 total_refs; /* Total refs in btrfs_extent_item */ > + u64 inline_refs = 0; /* found total inline refs */ > + > + if (key->type == BTRFS_METADATA_ITEM_KEY && > + !btrfs_fs_incompat(fs_info, SKINNY_METADATA)) { > + generic_err(leaf, slot, > +"invalid key type, METADATA_ITEM type invalid when SKINNY_METADATA feature disabled"); > + return -EUCLEAN; > + } > + /* key->objectid is the bytenr for both key types */ > + if (!IS_ALIGNED(key->objectid, fs_info->sectorsize)) { > + generic_err(leaf, slot, > +"invalid key objectid, have %llu expect to be aligned to %u", > + key->objectid, fs_info->sectorsize); > + return -EUCLEAN; > + } > + > + /* key->offset is tree level for METADATA_ITEM_KEY */ > + if (key->type == BTRFS_METADATA_ITEM_KEY) { > + if (key->offset >= BTRFS_MAX_LEVEL) { make it a compound statement: if key->type && key->offset. The extra if doesn't bring anything... > + extent_err(leaf, slot, > + "invalid tree level, have %llu expect [0, %u]", > + key->offset, BTRFS_MAX_LEVEL - 1); > + return -EUCLEAN; > + } > + } > + > + /* > + * EXTENT/METADATA_ITEM is consistent of: > + * 1) One btrfs_extent_item > + * Records the total refs, type and generation of the extent. > + * > + * 2) One btrfs_tree_block_info (for EXTENT_ITEM and tree backref only) > + * Records the first key and level of the tree block. > + * > + * 2) *Zero* or more btrfs_extent_inline_ref(s) > + * Each inline ref has one btrfs_extent_inline_ref shows: > + * 2.1) The ref type, one of the 4 > + * TREE_BLOCK_REF Tree block only > + * SHARED_BLOCK_REF Tree block only > + * EXTENT_DATA_REF Data only > + * SHARED_DATA_REF Data only > + * 2.2) Ref type specific data > + * Either using btrfs_extent_inline_ref::offset, or specific > + * data structure. > + */ > + if (item_size < sizeof(*ei)) { > + extent_err(leaf, slot, > + "invalid item size, have %u expect >= %lu", > + item_size, sizeof(*ei)); > + return -EUCLEAN; > + } > + end = item_size + btrfs_item_ptr_offset(leaf, slot); > + > + /* Checks against extent_item */ > + ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item); > + flags = btrfs_extent_flags(leaf, ei); > + total_refs = btrfs_extent_refs(leaf, ei); > + generation = btrfs_extent_generation(leaf, ei); > + if (generation > btrfs_super_generation(fs_info->super_copy) + 1) { > + extent_err(leaf, slot, > + "invalid generation, have %llu expect <= %llu", nit: I find the '<= [number]' somewhat confusing, wouldn't it be better if it's spelled our e.g 'expecting less than or equal than [number]'. Might be just me. > + generation, > + btrfs_super_generation(fs_info->super_copy) + 1); > + return -EUCLEAN; > + } > + if (!is_power_of_2(flags & (BTRFS_EXTENT_FLAG_DATA | > + BTRFS_EXTENT_FLAG_TREE_BLOCK))) { > + extent_err(leaf, slot, > + "invalid extent flag, have 0x%llx expect 1 bit set in 0x%llx", > + flags, BTRFS_EXTENT_FLAG_DATA | > + BTRFS_EXTENT_FLAG_TREE_BLOCK); > + return -EUCLEAN; > + } > + is_tree_block = !!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK); > + if (is_tree_block && key->type == BTRFS_EXTENT_ITEM_KEY && > + key->offset != fs_info->nodesize) { > + extent_err(leaf, slot, > + "invalid extent length, have %llu expect %u", > + key->offset, fs_info->nodesize); > + return -EUCLEAN; > + } > + if (!is_tree_block) { > + if (key->type != BTRFS_EXTENT_ITEM_KEY) { > + extent_err(leaf, slot, > + "invalid key type, have %u expect %u for data backref", > + key->type, BTRFS_EXTENT_ITEM_KEY); > + return -EUCLEAN; > + } > + if (!IS_ALIGNED(key->offset, fs_info->sectorsize)) { > + extent_err(leaf, slot, > + "invalid extent length, have %llu expect aliged to %u", > + key->offset, fs_info->sectorsize); > + return -EUCLEAN; > + } > + } unify the two is_tree_block/!is_tree_block either in: if (is_tree_block) { if (keypt->type = EXTENT_ITEM_KEY && offset != nodesize { foo; } } else { bar; } or if (is_tree_block && key->type == BTRFS_EXTENT_ITEM_KEY ..) { } else if (!is_tree_block) { bar } > + ptr = (u64)(struct btrfs_extent_item *)(ei + 1); > + > + /* Check the special case of btrfs_tree_block_info */ > + if (is_tree_block && key->type != BTRFS_METADATA_ITEM_KEY) { > + struct btrfs_tree_block_info *info; > + > + info = (struct btrfs_tree_block_info *)ptr; > + if (btrfs_tree_block_level(leaf, info) >= BTRFS_MAX_LEVEL) { > + extent_err(leaf, slot, > + "invalid tree block info level, have %u expect [0, %u)", nit: Strictly speaking using [0, 7) is wrong, because ')' already implies an open interval. Since we have 8 levels 0/7 inclusive this means the correct way to print it would be [0, 7] or [0, 8). > + btrfs_tree_block_level(leaf, info), > + BTRFS_MAX_LEVEL - 1); > + return -EUCLEAN; > + } > + ptr = (u64)(struct btrfs_tree_block_info *)(info + 1); > + } > + > + /* Check inline refs */ > + while (ptr < end) { > + struct btrfs_extent_inline_ref *iref; > + struct btrfs_extent_data_ref *dref; > + struct btrfs_shared_data_ref *sref; > + u64 dref_offset; > + u64 inline_offset; > + u8 inline_type; > + > + if (ptr + sizeof(*iref) > end) { > + extent_err(leaf, slot, > + "invalid item size, size too small, ptr %llu end %llu", > + ptr, end); > + goto err; > + } > + iref = (struct btrfs_extent_inline_ref *)ptr; > + inline_type = btrfs_extent_inline_ref_type(leaf, iref); > + inline_offset = btrfs_extent_inline_ref_offset(leaf, iref); > + if (ptr + btrfs_extent_inline_ref_size(inline_type) > end) { > + extent_err(leaf, slot, > + "invalid item size, size too small, ptr %llu end %llu", Make that text explicit: "inline ref item overflows extent item" or some such. > + ptr, end); > + goto err; > + } > + > + switch (inline_type) { > + /* inline_offset is subvolid of the owner, no need to check */ > + case BTRFS_TREE_BLOCK_REF_KEY: > + inline_refs++; > + break; > + /* contains parent bytenr */ > + case BTRFS_SHARED_BLOCK_REF_KEY: > + if (!IS_ALIGNED(inline_offset, fs_info->sectorsize)) { > + extent_err(leaf, slot, > + "invalid tree parent bytenr, have %llu expect aligned to %u", > + inline_offset, fs_info->sectorsize); > + goto err; > + } > + inline_refs++; > + break; > + /* > + * contains owner subvolid, owner key objectid, adjusted offset. > + * the only obvious corruption can happen in that offset. > + */ > + case BTRFS_EXTENT_DATA_REF_KEY: > + dref = (struct btrfs_extent_data_ref *)(&iref->offset); > + dref_offset = btrfs_extent_data_ref_offset(leaf, dref); > + if (!IS_ALIGNED(dref_offset, fs_info->sectorsize)) { > + extent_err(leaf, slot, > + "invalid data ref offset, have %llu expect aligned to %u", > + dref_offset, fs_info->sectorsize); > + goto err; > + } > + inline_refs += btrfs_extent_data_ref_count(leaf, dref); > + break; > + /* contains parent bytenr and ref count */ > + case BTRFS_SHARED_DATA_REF_KEY: > + sref = (struct btrfs_shared_data_ref *)(iref + 1); > + if (!IS_ALIGNED(inline_offset, fs_info->sectorsize)) { > + extent_err(leaf, slot, > + "invalid data parent bytenr, have %llu expect aligned to %u", > + inline_offset, fs_info->sectorsize); > + goto err; > + } > + inline_refs += btrfs_shared_data_ref_count(leaf, sref); > + break; > + default: > + extent_err(leaf, slot, "unknown inline ref type: %u", > + inline_type); > + goto err; > + } > + ptr += btrfs_extent_inline_ref_size(inline_type); > + } > + /* No padding is allowed */ > + if (ptr != end) { > + extent_err(leaf, slot, > + "invalid extent item size, padding bytes found"); > + goto err; > + } > + > + /* Finally, check the inline refs against total refs */ > + if (total_refs < inline_refs) { nit: if (inline_refs > total_refs) {} looks saner to me. > + extent_err(leaf, slot, > + "invalid extent refs, have %llu expect >= %llu", > + total_refs, inline_refs); > + goto err; > + } > + return 0; > +err: > + return -EUCLEAN; > +} > + > /* > * Common point to switch the item-specific validation. > */ > @@ -937,6 +1182,10 @@ static int check_leaf_item(struct extent_buffer *leaf, > case BTRFS_ROOT_ITEM_KEY: > ret = check_root_item(leaf, key, slot); > break; > + case BTRFS_EXTENT_ITEM_KEY: > + case BTRFS_METADATA_ITEM_KEY: > + ret = check_extent_item(leaf, key, slot); > + break; > } > return ret; > } > ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH 1/3] btrfs: tree-checker: Add EXTENT_ITEM and METADATA_ITEM check 2019-07-29 13:42 ` Nikolay Borisov @ 2019-07-29 13:53 ` Qu Wenruo 0 siblings, 0 replies; 6+ messages in thread From: Qu Wenruo @ 2019-07-29 13:53 UTC (permalink / raw) To: Nikolay Borisov, Qu Wenruo, linux-btrfs On 2019/7/29 下午9:42, Nikolay Borisov wrote: [...] >> + >> + /* key->offset is tree level for METADATA_ITEM_KEY */ >> + if (key->type == BTRFS_METADATA_ITEM_KEY) { >> + if (key->offset >= BTRFS_MAX_LEVEL) { > > make it a compound statement: > > if key->type && key->offset. The extra if doesn't bring anything... Right, that's the case. I though there would be more checks, but turns out there is only one check. > >> + extent_err(leaf, slot, >> + "invalid tree level, have %llu expect [0, %u]", >> + key->offset, BTRFS_MAX_LEVEL - 1); >> + return -EUCLEAN; >> + } >> + } >> + >> + /* >> + * EXTENT/METADATA_ITEM is consistent of: >> + * 1) One btrfs_extent_item >> + * Records the total refs, type and generation of the extent. >> + * >> + * 2) One btrfs_tree_block_info (for EXTENT_ITEM and tree backref only) >> + * Records the first key and level of the tree block. >> + * >> + * 2) *Zero* or more btrfs_extent_inline_ref(s) >> + * Each inline ref has one btrfs_extent_inline_ref shows: >> + * 2.1) The ref type, one of the 4 >> + * TREE_BLOCK_REF Tree block only >> + * SHARED_BLOCK_REF Tree block only >> + * EXTENT_DATA_REF Data only >> + * SHARED_DATA_REF Data only >> + * 2.2) Ref type specific data >> + * Either using btrfs_extent_inline_ref::offset, or specific >> + * data structure. >> + */ >> + if (item_size < sizeof(*ei)) { >> + extent_err(leaf, slot, >> + "invalid item size, have %u expect >= %lu", >> + item_size, sizeof(*ei)); >> + return -EUCLEAN; >> + } >> + end = item_size + btrfs_item_ptr_offset(leaf, slot); >> + >> + /* Checks against extent_item */ >> + ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item); >> + flags = btrfs_extent_flags(leaf, ei); >> + total_refs = btrfs_extent_refs(leaf, ei); >> + generation = btrfs_extent_generation(leaf, ei); >> + if (generation > btrfs_super_generation(fs_info->super_copy) + 1) { >> + extent_err(leaf, slot, >> + "invalid generation, have %llu expect <= %llu", > > nit: I find the '<= [number]' somewhat confusing, wouldn't it be better > if it's spelled our e.g 'expecting less than or equal than [number]'. > Might be just me. I normally prefer the "[start, end]" notion, but sometimes even myself can't always keep the format the same. Furthermore, I can't find a minimal value to use [start, end] notion. Maybe (0, end] would be more suitable here? > >> + generation, >> + btrfs_super_generation(fs_info->super_copy) + 1); >> + return -EUCLEAN; >> + } >> + if (!is_power_of_2(flags & (BTRFS_EXTENT_FLAG_DATA | >> + BTRFS_EXTENT_FLAG_TREE_BLOCK))) { >> + extent_err(leaf, slot, >> + "invalid extent flag, have 0x%llx expect 1 bit set in 0x%llx", >> + flags, BTRFS_EXTENT_FLAG_DATA | >> + BTRFS_EXTENT_FLAG_TREE_BLOCK); >> + return -EUCLEAN; >> + } >> + is_tree_block = !!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK); >> + if (is_tree_block && key->type == BTRFS_EXTENT_ITEM_KEY && >> + key->offset != fs_info->nodesize) { >> + extent_err(leaf, slot, >> + "invalid extent length, have %llu expect %u", >> + key->offset, fs_info->nodesize); >> + return -EUCLEAN; >> + } >> + if (!is_tree_block) { >> + if (key->type != BTRFS_EXTENT_ITEM_KEY) { >> + extent_err(leaf, slot, >> + "invalid key type, have %u expect %u for data backref", >> + key->type, BTRFS_EXTENT_ITEM_KEY); >> + return -EUCLEAN; >> + } >> + if (!IS_ALIGNED(key->offset, fs_info->sectorsize)) { >> + extent_err(leaf, slot, >> + "invalid extent length, have %llu expect aliged to %u", >> + key->offset, fs_info->sectorsize); >> + return -EUCLEAN; >> + } >> + } > > unify the two is_tree_block/!is_tree_block either in: > > if (is_tree_block) { > if (keypt->type = EXTENT_ITEM_KEY && offset != nodesize { > foo; > } > } else { > bar; > } > Right, that's better. > or > > if (is_tree_block && key->type == BTRFS_EXTENT_ITEM_KEY ..) { > > } else if (!is_tree_block) { > bar > } > >> + ptr = (u64)(struct btrfs_extent_item *)(ei + 1); >> + >> + /* Check the special case of btrfs_tree_block_info */ >> + if (is_tree_block && key->type != BTRFS_METADATA_ITEM_KEY) { >> + struct btrfs_tree_block_info *info; >> + >> + info = (struct btrfs_tree_block_info *)ptr; >> + if (btrfs_tree_block_level(leaf, info) >= BTRFS_MAX_LEVEL) { >> + extent_err(leaf, slot, >> + "invalid tree block info level, have %u expect [0, %u)", > > nit: Strictly speaking using [0, 7) is wrong, because ')' already > implies an open interval. Since we have 8 levels 0/7 inclusive this > means the correct way to print it would be [0, 7] or [0, 8). It's not that rare I misuses such notion. [0, 7] would be the case. > > >> + btrfs_tree_block_level(leaf, info), >> + BTRFS_MAX_LEVEL - 1); >> + return -EUCLEAN; >> + } >> + ptr = (u64)(struct btrfs_tree_block_info *)(info + 1); >> + } >> + >> + /* Check inline refs */ >> + while (ptr < end) { >> + struct btrfs_extent_inline_ref *iref; >> + struct btrfs_extent_data_ref *dref; >> + struct btrfs_shared_data_ref *sref; >> + u64 dref_offset; >> + u64 inline_offset; >> + u8 inline_type; >> + >> + if (ptr + sizeof(*iref) > end) { >> + extent_err(leaf, slot, >> + "invalid item size, size too small, ptr %llu end %llu", >> + ptr, end); >> + goto err; >> + } >> + iref = (struct btrfs_extent_inline_ref *)ptr; >> + inline_type = btrfs_extent_inline_ref_type(leaf, iref); >> + inline_offset = btrfs_extent_inline_ref_offset(leaf, iref); >> + if (ptr + btrfs_extent_inline_ref_size(inline_type) > end) { >> + extent_err(leaf, slot, >> + "invalid item size, size too small, ptr %llu end %llu", > > Make that text explicit: > > "inline ref item overflows extent item" or some such. OK, I'll use this expression. Thanks, Qu [...] >> + >> + /* Finally, check the inline refs against total refs */ >> + if (total_refs < inline_refs) { > > nit: if (inline_refs > total_refs) {} looks saner to me. > > > >> + extent_err(leaf, slot, >> + "invalid extent refs, have %llu expect >= %llu", >> + total_refs, inline_refs); >> + goto err; >> + } >> + return 0; >> +err: >> + return -EUCLEAN; >> +} >> + >> /* >> * Common point to switch the item-specific validation. >> */ >> @@ -937,6 +1182,10 @@ static int check_leaf_item(struct extent_buffer *leaf, >> case BTRFS_ROOT_ITEM_KEY: >> ret = check_root_item(leaf, key, slot); >> break; >> + case BTRFS_EXTENT_ITEM_KEY: >> + case BTRFS_METADATA_ITEM_KEY: >> + ret = check_extent_item(leaf, key, slot); >> + break; >> } >> return ret; >> } >> ^ permalink raw reply [flat|nested] 6+ messages in thread
* [PATCH 2/3] btrfs: tree-checker: Add simple keyed refs check 2019-07-29 7:43 [PATCH 0/3] btrfs: tree-checker: Add extent items check Qu Wenruo 2019-07-29 7:43 ` [PATCH 1/3] btrfs: tree-checker: Add EXTENT_ITEM and METADATA_ITEM check Qu Wenruo @ 2019-07-29 7:43 ` Qu Wenruo 2019-07-29 7:43 ` [PATCH 3/3] btrfs: tree-checker: Add EXTENT_DATA_REF check Qu Wenruo 2 siblings, 0 replies; 6+ messages in thread From: Qu Wenruo @ 2019-07-29 7:43 UTC (permalink / raw) To: linux-btrfs For TREE_BLOCK_REF, SHARED_DATA_REF and SHARED_BLOCK_REF we need to check: | TREE_BLOCK_REF | SHARED_BLOCK_REF | SHARED_BLOCK_REF --------------+----------------+-----------------+------------------ key->objectid | Alignment | Alignment | Alignment key->offset | Any value | Alignment | Alignment item_size | 0 | 0 | sizeof(le32) (*) *: sizeof(struct btrfs_shared_data_ref) So introduce a check to check all these 3 key types together. Signed-off-by: Qu Wenruo <wqu@suse.com> --- fs/btrfs/tree-checker.c | 40 +++++++++++++++++++++++++++++++++++++++- 1 file changed, 39 insertions(+), 1 deletion(-) diff --git a/fs/btrfs/tree-checker.c b/fs/btrfs/tree-checker.c index 1e97bb127893..6ef174c7fb05 100644 --- a/fs/btrfs/tree-checker.c +++ b/fs/btrfs/tree-checker.c @@ -912,7 +912,9 @@ static void extent_err(const struct extent_buffer *eb, int slot, btrfs_item_key_to_cpu(eb, &key, slot); bytenr = key.objectid; - if (key.type == BTRFS_METADATA_ITEM_KEY) + if (key.type == BTRFS_METADATA_ITEM_KEY || + key.type == BTRFS_TREE_BLOCK_REF_KEY || + key.type == BTRFS_SHARED_BLOCK_REF_KEY) len = eb->fs_info->nodesize; else len = key.offset; @@ -1144,6 +1146,37 @@ static int check_extent_item(struct extent_buffer *leaf, return -EUCLEAN; } +static int check_simple_keyed_refs(struct extent_buffer *leaf, + struct btrfs_key *key, int slot) +{ + u32 expect_item_size = 0; + + if (key->type == BTRFS_SHARED_DATA_REF_KEY) + expect_item_size = sizeof(struct btrfs_shared_data_ref); + + if (btrfs_item_size_nr(leaf, slot) != expect_item_size) { + generic_err(leaf, slot, + "invalid item size, have %u expect %u for key type %u", + btrfs_item_size_nr(leaf, slot), + expect_item_size, key->type); + return -EUCLEAN; + } + if (!IS_ALIGNED(key->objectid, leaf->fs_info->sectorsize)) { + generic_err(leaf, slot, +"invalid key objectid for shared block ref, have %llu expect aligned to %u", + key->objectid, leaf->fs_info->sectorsize); + return -EUCLEAN; + } + if (key->type != BTRFS_TREE_BLOCK_REF_KEY && + !IS_ALIGNED(key->offset, leaf->fs_info->sectorsize)) { + extent_err(leaf, slot, + "invalid tree parent bytenr, have %llu expect aligned to %u", + key->offset, leaf->fs_info->sectorsize); + return -EUCLEAN; + } + return 0; +} + /* * Common point to switch the item-specific validation. */ @@ -1186,6 +1219,11 @@ static int check_leaf_item(struct extent_buffer *leaf, case BTRFS_METADATA_ITEM_KEY: ret = check_extent_item(leaf, key, slot); break; + case BTRFS_TREE_BLOCK_REF_KEY: + case BTRFS_SHARED_DATA_REF_KEY: + case BTRFS_SHARED_BLOCK_REF_KEY: + ret = check_simple_keyed_refs(leaf, key, slot); + break; } return ret; } -- 2.22.0 ^ permalink raw reply related [flat|nested] 6+ messages in thread
* [PATCH 3/3] btrfs: tree-checker: Add EXTENT_DATA_REF check 2019-07-29 7:43 [PATCH 0/3] btrfs: tree-checker: Add extent items check Qu Wenruo 2019-07-29 7:43 ` [PATCH 1/3] btrfs: tree-checker: Add EXTENT_ITEM and METADATA_ITEM check Qu Wenruo 2019-07-29 7:43 ` [PATCH 2/3] btrfs: tree-checker: Add simple keyed refs check Qu Wenruo @ 2019-07-29 7:43 ` Qu Wenruo 2 siblings, 0 replies; 6+ messages in thread From: Qu Wenruo @ 2019-07-29 7:43 UTC (permalink / raw) To: linux-btrfs EXTENT_DATA_REF is a little like DIR_ITEM which contains hash in its key->offset. This patch will check the following contents: - Key->objectid Basic alignment check. - Hash Hash of each extent_data_ref item must match key->offset. - Offset Basic alignment check. Signed-off-by: Qu Wenruo <wqu@suse.com> --- fs/btrfs/ctree.h | 1 + fs/btrfs/extent-tree.c | 2 +- fs/btrfs/tree-checker.c | 48 +++++++++++++++++++++++++++++++++++++++++ 3 files changed, 50 insertions(+), 1 deletion(-) diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h index 0a61dff27f57..710ea3a6608c 100644 --- a/fs/btrfs/ctree.h +++ b/fs/btrfs/ctree.h @@ -2679,6 +2679,7 @@ enum btrfs_inline_ref_type { int btrfs_get_extent_inline_ref_type(const struct extent_buffer *eb, struct btrfs_extent_inline_ref *iref, enum btrfs_inline_ref_type is_data); +u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset); u64 btrfs_csum_bytes_to_leaves(struct btrfs_fs_info *fs_info, u64 csum_bytes); diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c index b4e9e36b65f1..c0888ed503df 100644 --- a/fs/btrfs/extent-tree.c +++ b/fs/btrfs/extent-tree.c @@ -1114,7 +1114,7 @@ int btrfs_get_extent_inline_ref_type(const struct extent_buffer *eb, return BTRFS_REF_TYPE_INVALID; } -static u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset) +u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset) { u32 high_crc = ~(u32)0; u32 low_crc = ~(u32)0; diff --git a/fs/btrfs/tree-checker.c b/fs/btrfs/tree-checker.c index 6ef174c7fb05..115725f742c2 100644 --- a/fs/btrfs/tree-checker.c +++ b/fs/btrfs/tree-checker.c @@ -1177,6 +1177,51 @@ static int check_simple_keyed_refs(struct extent_buffer *leaf, return 0; } +static int check_extent_data_ref(struct extent_buffer *leaf, + struct btrfs_key *key, int slot) +{ + struct btrfs_extent_data_ref *dref; + u64 ptr = btrfs_item_ptr_offset(leaf, slot); + u64 end = ptr + btrfs_item_size_nr(leaf, slot); + + if (btrfs_item_size_nr(leaf, slot) % sizeof(*dref) != 0) { + generic_err(leaf, slot, + "invalid item size, have %u expect aligned to %lu for key type %u", + btrfs_item_size_nr(leaf, slot), + sizeof(*dref), key->type); + } + if (!IS_ALIGNED(key->objectid, leaf->fs_info->sectorsize)) { + generic_err(leaf, slot, +"invalid key objectid for shared block ref, have %llu expect aligned to %u", + key->objectid, leaf->fs_info->sectorsize); + return -EUCLEAN; + } + for (; ptr < end; ptr += sizeof(*dref)) { + u64 root_objectid; + u64 owner; + u64 offset; + u64 hash; + + dref = (struct btrfs_extent_data_ref *)ptr; + root_objectid = btrfs_extent_data_ref_root(leaf, dref); + owner = btrfs_extent_data_ref_objectid(leaf, dref); + offset = btrfs_extent_data_ref_offset(leaf, dref); + hash = hash_extent_data_ref(root_objectid, owner, offset); + if (hash != key->offset) { + extent_err(leaf, slot, + "invalid extent data ref hash, item have 0x%016llx key have 0x%016llx", + hash, key->offset); + return -EUCLEAN; + } + if (!IS_ALIGNED(offset, leaf->fs_info->sectorsize)) { + extent_err(leaf, slot, + "invalid extent data backref offset, have %llu expect aligned to %u", + offset, leaf->fs_info->sectorsize); + } + } + return 0; +} + /* * Common point to switch the item-specific validation. */ @@ -1224,6 +1269,9 @@ static int check_leaf_item(struct extent_buffer *leaf, case BTRFS_SHARED_BLOCK_REF_KEY: ret = check_simple_keyed_refs(leaf, key, slot); break; + case BTRFS_EXTENT_DATA_REF_KEY: + ret = check_extent_data_ref(leaf, key, slot); + break; } return ret; } -- 2.22.0 ^ permalink raw reply related [flat|nested] 6+ messages in thread
end of thread, other threads:[~2019-07-29 13:53 UTC | newest] Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2019-07-29 7:43 [PATCH 0/3] btrfs: tree-checker: Add extent items check Qu Wenruo 2019-07-29 7:43 ` [PATCH 1/3] btrfs: tree-checker: Add EXTENT_ITEM and METADATA_ITEM check Qu Wenruo 2019-07-29 13:42 ` Nikolay Borisov 2019-07-29 13:53 ` Qu Wenruo 2019-07-29 7:43 ` [PATCH 2/3] btrfs: tree-checker: Add simple keyed refs check Qu Wenruo 2019-07-29 7:43 ` [PATCH 3/3] btrfs: tree-checker: Add EXTENT_DATA_REF check Qu Wenruo
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).