[PATCH v1.2 0/3] btrfs: tree-checker: Add extent items check

[PATCH v1.2 0/3] btrfs: tree-checker: Add extent items check

[Qu Wenruo]

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.

Changelog:
v1.1:
- If branches optimization
  Make some if branches more readable.

- Range notion update
  Use regular set notion ([],[),(],()) to show possible value range.

- Fix a wrong range notion
  The valid range for tree level is [0, MAX_LEVEL - 1], not
  [0, MAX_LEVEL -1)

v1.2:
- Use "unsigned long" for pointer convertion

- Use "%zu" format for sizeof() in the 3rd patch

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 | 336 ++++++++++++++++++++++++++++++++++++++++
 3 files changed, 338 insertions(+), 1 deletion(-)

-- 
2.22.0

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

[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 <wqu@suse.com>
---
 fs/btrfs/tree-checker.c | 250 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 250 insertions(+)

diff --git a/fs/btrfs/tree-checker.c b/fs/btrfs/tree-checker.c
index 71bbbce3076d..836f5d8a8ebe 100644
--- a/fs/btrfs/tree-checker.c
+++ b/fs/btrfs/tree-checker.c
@@ -899,6 +899,252 @@ 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;
+	unsigned long ptr;	/* Current pointer inside inline refs */
+	unsigned long 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 &&
+	    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 [%zu, %u)",
+			   item_size, sizeof(*ei),
+			   BTRFS_LEAF_DATA_SIZE(fs_info));
+		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 (0, %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) {
+		if (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;
+		}
+	} else {
+		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 aligned to %u",
+				   key->offset, fs_info->sectorsize);
+			return -EUCLEAN;
+		}
+	}
+	ptr = (unsigned long)(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 = (unsigned long)(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,
+"inline ref item overflows extent item, ptr %lu iref size %zu end %lu",
+				   ptr, sizeof(*iref), 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,
+"inline ref item overflows extent item, ptr %lu iref size %u end %lu",
+				   ptr, inline_type, 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 (inline_refs > total_refs) {
+		extent_err(leaf, slot,
+			"invalid extent refs, have %llu expect >= inline %llu",
+			   total_refs, inline_refs);
+		goto err;
+	}
+	return 0;
+err:
+	return -EUCLEAN;
+}
+
 /*
  * Common point to switch the item-specific validation.
  */
@@ -937,6 +1183,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

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

[David Sterba]

On Fri, Aug 09, 2019 at 09:24:22AM +0800, Qu Wenruo wrote:
> +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;
> +	unsigned long ptr;	/* Current pointer inside inline refs */
> +	unsigned long 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 &&
> +	    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 [%zu, %u)",
> +			   item_size, sizeof(*ei),
> +			   BTRFS_LEAF_DATA_SIZE(fs_info));
> +		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 (0, %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) {
> +		if (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;
> +		}
> +	} else {
> +		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 aligned to %u",
> +				   key->offset, fs_info->sectorsize);
> +			return -EUCLEAN;
> +		}
> +	}
> +	ptr = (unsigned long)(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 = (unsigned long)(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,
> +"inline ref item overflows extent item, ptr %lu iref size %zu end %lu",
> +				   ptr, sizeof(*iref), end);
> +			goto err;

Half of the function does return -EUCLEAN and the other goto err, that
does return -EUCLEAN without any other code. Is there a reason you don't
use the return consistently?

> +		}
> +		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,
> +"inline ref item overflows extent item, ptr %lu iref size %u end %lu",
> +				   ptr, inline_type, 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 */

Comments should start with a capital letter unless it's an identifier.

> +		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");

The other messages are detailed which is good, this one lacks the amount
of padding found.

> +		goto err;
> +	}
> +
> +	/* Finally, check the inline refs against total refs */
> +	if (inline_refs > total_refs) {
> +		extent_err(leaf, slot,
> +			"invalid extent refs, have %llu expect >= inline %llu",
> +			   total_refs, inline_refs);
> +		goto err;
> +	}
> +	return 0;
> +err:
> +	return -EUCLEAN;
> +}

[PATCH v1.2 2/3] btrfs: tree-checker: Add simple keyed refs check

[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 <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 836f5d8a8ebe..39d10b553c5f 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;
@@ -1145,6 +1147,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.
  */
@@ -1187,6 +1220,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

Deletion on BTRFS - how does it work

[Alex Shashkov]

I'm trying to understand how deletion works on BTRFS. Let's say
directory containing files and other directories gets deleted. What is
essentially happening during this action, what strucutres get updated,
what artifacts remain after the deletion, is it possible to find them
and recover deleted objects, if yes, then how? Thanks in advance!
-- 
Alex Shashkov

Re: Deletion on BTRFS - how does it work

[Nikolay Borisov]

On 9.08.19 г. 7:25 ч., Alex Shashkov wrote:
> I'm trying to understand how deletion works on BTRFS. Let's say
> directory containing files and other directories gets deleted. What is
> essentially happening during this action, what strucutres get updated,
> what artifacts remain after the deletion, is it possible to find them
> and recover deleted objects, if yes, then how? Thanks in advance!

You want to look into btrfs_unlink_inode to see how unlinking works in
bttrfs.

> 

Re: [PATCH v1.2 2/3] btrfs: tree-checker: Add simple keyed refs check

[David Sterba]

On Fri, Aug 09, 2019 at 09:24:23AM +0800, Qu Wenruo wrote:
> 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>

Reviewed-by: David Sterba <dsterba@suse.com>

[PATCH v1.2 3/3] btrfs: tree-checker: Add EXTENT_DATA_REF check

[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 <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 39d10b553c5f..2a0624bf7789 100644
--- a/fs/btrfs/tree-checker.c
+++ b/fs/btrfs/tree-checker.c
@@ -1178,6 +1178,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;
+	unsigned long ptr = btrfs_item_ptr_offset(leaf, slot);
+	unsigned long 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 %zu 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.
  */
@@ -1225,6 +1270,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

Re: [PATCH v1.2 0/3] btrfs: tree-checker: Add extent items check

[David Sterba]

On Fri, Aug 09, 2019 at 09:24:21AM +0800, Qu Wenruo wrote:
> 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

Great, thanks.

> v1.2:
  ^^^^

Please use integers for patchsets, ie. this is v3 for me.

> - Use "unsigned long" for pointer convertion
> 
> - Use "%zu" format for sizeof() in the 3rd patch
> 
> 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

I'll update patch 1 with the goto -> return and fix the comments, no
need to resend. V2 has been in for-next, there were no significant
changes since so I'll add v3 to misc-next. Thanks.