Skip to contentSkip to conversation

btrfs: tree-checker: Add extent items check

PATCH In review Qu Wenruo 3 participants 6 messages Jul 29, 2019 Btrfs file system

lore
Share & tools
lore

Qu Wenruo

author
#0 lore raw

cover btrfs: tree-checker: Add extent items check

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(-)
Signature · 1 line
2.22.0
author
#1 lore raw

PATCH 1/3 btrfs: tree-checker: Add EXTENT_ITEM and METADATA_ITEM check

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 <[email protected]>
---
 fs/btrfs/tree-checker.c | 249 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 249 insertions(+)
fs/btrfs/tree-checker.c +249 -0
index 71bbbce3076d..1e97bb127893 100644
@@ -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;
 }
Signature · 1 line
2.22.0
#2 lore raw

Re: [PATCH 1/3] btrfs: tree-checker: Add EXTENT_ITEM and METADATA_ITEM check

Quoted 92 lines · Qu Wenruo

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 <[email protected]>
---
 fs/btrfs/tree-checker.c | 249 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 249 insertions(+)
fs/btrfs/tree-checker.c +50 -0
index 71bbbce3076d..1e97bb127893 100644
@@ -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 */

fs/btrfs/tree-checker.c static int check_root_item(struct extent_buffer *leaf, struct btrfs_key *key, · line 961

Quoted 10 lines
fs/btrfs/tree-checker.c +10 -0
+	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...

Quoted 32 lines
fs/btrfs/tree-checker.c +32 -0
+			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;
+	}

fs/btrfs/tree-checker.c static int check_root_item(struct extent_buffer *leaf, struct btrfs_key *key, · line 1003

Quoted 10 lines
fs/btrfs/tree-checker.c +10 -0
+	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.

Quoted 24 lines
fs/btrfs/tree-checker.c +24 -0
+			   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",

fs/btrfs/tree-checker.c static int check_root_item(struct extent_buffer *leaf, struct btrfs_key *key, · line 1037

Quoted 10 lines
fs/btrfs/tree-checker.c +10 -0
+				   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
}

fs/btrfs/tree-checker.c static int check_root_item(struct extent_buffer *leaf, struct btrfs_key *key, · line 1047

Quoted 10 lines
fs/btrfs/tree-checker.c +10 -0
+	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).

Quoted 18 lines
fs/btrfs/tree-checker.c +18 -0
+				   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,

fs/btrfs/tree-checker.c static int check_root_item(struct extent_buffer *leaf, struct btrfs_key *key, · line 1075

Quoted 10 lines
fs/btrfs/tree-checker.c +10 -0
+	"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.

Quoted 51 lines
fs/btrfs/tree-checker.c +51 -0
+				   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);

fs/btrfs/tree-checker.c static int check_root_item(struct extent_buffer *leaf, struct btrfs_key *key, · line 1136

Quoted 10 lines
fs/btrfs/tree-checker.c +10 -0
+	}
+	/* 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.

Quoted 25 lines
fs/btrfs/tree-checker.c +14 -0
+		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;
 }
#3 lore raw

Re: [PATCH 1/3] btrfs: tree-checker: Add EXTENT_ITEM and METADATA_ITEM check

On 2019/7/29 下午9:42, Nikolay Borisov wrote:
[...]

Quoted 8 lines

fs/btrfs/tree-checker.c static int check_root_item(struct extent_buffer *leaf, struct btrfs_key *key, · line 961

Quoted 4 lines
fs/btrfs/tree-checker.c +4 -0
+
+	/* 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.

Quoted 39 lines
Quoted 39 lines
fs/btrfs/tree-checker.c +38 -0
+			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);
Quoted 8 lines

fs/btrfs/tree-checker.c static int check_root_item(struct extent_buffer *leaf, struct btrfs_key *key, · line 1003

Quoted 4 lines
fs/btrfs/tree-checker.c +4 -0
+	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?

Quoted 38 lines
Quoted 25 lines
fs/btrfs/tree-checker.c +24 -0
+			   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",

fs/btrfs/tree-checker.c static int check_root_item(struct extent_buffer *leaf, struct btrfs_key *key, · line 1037

Quoted 10 lines
fs/btrfs/tree-checker.c +10 -0
+				   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:

Quoted 8 lines
if (is_tree_block) {
	if (keypt->type = EXTENT_ITEM_KEY && offset != nodesize {
		foo;
	}
} else {
	bar;
}

Right, that's better.

Quoted 8 lines

or

if (is_tree_block && key->type == BTRFS_EXTENT_ITEM_KEY ..) {

} else if (!is_tree_block) {
bar
}

Quoted 14 lines

fs/btrfs/tree-checker.c static int check_root_item(struct extent_buffer *leaf, struct btrfs_key *key, · line 1047

Quoted 10 lines
fs/btrfs/tree-checker.c +10 -0
+	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.

Quoted 33 lines
Quoted 20 lines
fs/btrfs/tree-checker.c +18 -0
+				   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,

fs/btrfs/tree-checker.c static int check_root_item(struct extent_buffer *leaf, struct btrfs_key *key, · line 1075

Quoted 10 lines
fs/btrfs/tree-checker.c +10 -0
+	"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:

Quoted 1 line

"inline ref item overflows extent item" or some such.

OK, I'll use this expression.

Thanks,
Qu

[...]

Quoted 33 lines

fs/btrfs/tree-checker.c static int check_root_item(struct extent_buffer *leaf, struct btrfs_key *key, · line 1136

Quoted 3 lines
fs/btrfs/tree-checker.c +3 -0
+
+	/* Finally, check the inline refs against total refs */
+	if (total_refs < inline_refs) {

nit: if (inline_refs > total_refs) {} looks saner to me.

Quoted 25 lines
fs/btrfs/tree-checker.c +14 -0
+		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;
 }
author
#4 lore raw

PATCH 2/3 btrfs: tree-checker: Add simple keyed refs check

In reply to Qu Wenruo

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 <[email protected]>
---
 fs/btrfs/tree-checker.c | 40 +++++++++++++++++++++++++++++++++++++++-
 1 file changed, 39 insertions(+), 1 deletion(-)
fs/btrfs/tree-checker.c +39 -1
index 1e97bb127893..6ef174c7fb05 100644
@@ -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;
 }
Signature · 1 line
2.22.0
author
#5 lore raw

PATCH 3/3 btrfs: tree-checker: Add EXTENT_DATA_REF check

In reply to Qu Wenruo

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 <[email protected]>
---
 fs/btrfs/ctree.h        |  1 +
 fs/btrfs/extent-tree.c  |  2 +-
 fs/btrfs/tree-checker.c | 48 +++++++++++++++++++++++++++++++++++++++++
 3 files changed, 50 insertions(+), 1 deletion(-)
fs/btrfs/ctree.h +1 -0
index 0a61dff27f57..710ea3a6608c 100644
@@ -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);
fs/btrfs/extent-tree.c +1 -1
index b4e9e36b65f1..c0888ed503df 100644
@@ -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;
fs/btrfs/tree-checker.c +48 -0

60 lines not on this page · raw message

Signature · 1 line
2.22.0