Skip to contentSkip to conversation

btrfs-progs: follow-ups for issue #622

PATCH In review Qu Wenruo 4 participants 9 messages Oct 22, 2023 – Oct 24, 2023 Btrfs file system

lore
Share & tools
lore

Qu Wenruo

author
#0 lore raw

cover btrfs-progs: follow-ups for issue #622

Issue #622 is a very interesting bug report, that ntfs2btrfs has a fixed bug that it can generate out-of-order inline backref items.

This leads to kernel transaction abort, but btrfs-check failed to detect it at all.

Although the fix for btrfs-progs is already merged in the latest v6.5.3 release, we still lacks the following thing:

- Better dump-tree support to show the weird inline backref order This is very weird, as we have the inline type in ascending order, but for the sequence number (hash for EXTENT_DATA_REF, offset for all other types) it is descending inside the same type.

That's why the following output of one data extent item looks out-of-order:

item 0 key (13631488 EXTENT_ITEM 4096) itemoff 16143 itemsize 140
refs 4 gen 7 flags DATA
extent data backref root FS_TREE objectid 258 offset 0 count 1 extent data backref root FS_TREE objectid 257 offset 0 count 1 extent data backref root FS_TREE objectid 260 offset 0 count 1 extent data backref root FS_TREE objectid 259 offset 0 count 1

- Lowmem mode support to detect the error

- Test case to make sure we can detect the error

This series would address all the three points above.

Qu Wenruo (3):
btrfs-progs: dump-tree: output the sequence number for inline
references
btrfs-progs: check/lowmem: verify the sequence of inline backref items
btrfs-progs: fsck-tests: add test image of out-of-order inline backref
items

 check/mode-lowmem.c                           |  31 ++++++++++++++++++
 check/mode-lowmem.h                           |   1 +
 kernel-shared/print-tree.c                    |  31 +++++++++++-------
 .../btrfs_image.xz                            | Bin 0 -> 2264 bytes
 .../061-out-of-order-inline-backref/test.sh   |  19 +++++++++++
 5 files changed, 70 insertions(+), 12 deletions(-)
 create mode 100644 tests/fsck-tests/061-out-of-order-inline-backref/btrfs_image.xz
 create mode 100755 tests/fsck-tests/061-out-of-order-inline-backref/test.sh

--
2.42.0

author
#1 lore raw

PATCH 1/3 btrfs-progs: dump-tree: output the sequence number for inline references

Commit 6cf11f3e3815 ("btrfs-progs: check: check order of inline extent refs") fixes a problem that btrfs check never properly verify the sequence of inline references.

It's not obvious because by default kernel handles EXTENT_DATA_REF_KEY using its own hash, resulting some seemingly out-of-order result:

item 0 key (13631488 EXTENT_ITEM 4096) itemoff 16143 itemsize 140
refs 4 gen 7 flags DATA
extent data backref root FS_TREE objectid 258 offset 0 count 1 extent data backref root FS_TREE objectid 257 offset 0 count 1 extent data backref root FS_TREE objectid 260 offset 0 count 1 extent data backref root FS_TREE objectid 259 offset 0 count 1

By a quick glance, no one can see the above inline backref items are in any order.

To make such sequence more obvious, let dump-tree to output a new prefix to indicate the type and the internal sequence number:

For above case, the new output would look like this:

        item 0 key (13631488 EXTENT_ITEM 4096) itemoff 16143 itemsize 140
                refs 4 gen 7 flags DATA
                (178 0xdfb591fbbf5f519) extent data backref root FS_TREE objectid 258 offset 0 count 1
                (178 0xdfb591fa80d95ea) extent data backref root FS_TREE objectid 257 offset 0 count 1
                (178 0xdfb591f9c0534ff) extent data backref root FS_TREE objectid 260 offset 0 count 1
                (178 0xdfb591f49f9f8e7) extent data backref root FS_TREE objectid 259 offset 0 count 1

Although still not that obvious, it should show the inline data backrefs has descending sequence number.

For the type part, it's anti-instinctive in ascending order, which is not that easy to produce.

---
 kernel-shared/print-tree.c | 31 +++++++++++++++++++------------
 1 file changed, 19 insertions(+), 12 deletions(-)
kernel-shared/print-tree.c +19 -12
index f6e7539eb191..9e3ebddb97b3 100644
@@ -487,38 +487,45 @@ void print_extent_item(struct extent_buffer *eb, int slot, int metadata)
 	ptr = (unsigned long)iref;
 	end = (unsigned long)ei + item_size;
 	while (ptr < end) {
+		u64 seq;
+
 		iref = (struct btrfs_extent_inline_ref *)ptr;
 		type = btrfs_extent_inline_ref_type(eb, iref);
 		offset = btrfs_extent_inline_ref_offset(eb, iref);
+		seq = offset;
 		switch (type) {
 		case BTRFS_TREE_BLOCK_REF_KEY:
-			printf("\t\ttree block backref root ");
+			printf("\t\t(%u 0x%llx) tree block backref root ",
+			       type, seq);
 			print_objectid(stdout, offset, 0);
 			printf("\n");
 			break;
 		case BTRFS_SHARED_BLOCK_REF_KEY:
-			printf("\t\tshared block backref parent %llu\n",
-			       (unsigned long long)offset);
+			printf("\t\t(%u 0x%llx) shared block backref parent %llu\n",
+			       type, seq, offset);
 			break;
 		case BTRFS_EXTENT_DATA_REF_KEY:
 			dref = (struct btrfs_extent_data_ref *)(&iref->offset);
-			printf("\t\textent data backref root ");
-			print_objectid(stdout,
-		(unsigned long long)btrfs_extent_data_ref_root(eb, dref), 0);
+			seq = hash_extent_data_ref(
+					btrfs_extent_data_ref_root(eb, dref),
+					btrfs_extent_data_ref_objectid(eb, dref),
+					btrfs_extent_data_ref_offset(eb, dref));
+			printf("\t\t(%u 0x%llx) extent data backref root ",
+			       type, seq);
+			print_objectid(stdout, btrfs_extent_data_ref_root(eb, dref), 0);
 			printf(" objectid %llu offset %llu count %u\n",
-			       (unsigned long long)btrfs_extent_data_ref_objectid(eb, dref),
+			       btrfs_extent_data_ref_objectid(eb, dref),
 			       btrfs_extent_data_ref_offset(eb, dref),
 			       btrfs_extent_data_ref_count(eb, dref));
 			break;
 		case BTRFS_SHARED_DATA_REF_KEY:
 			sref = (struct btrfs_shared_data_ref *)(iref + 1);
-			printf("\t\tshared data backref parent %llu count %u\n",
-			       (unsigned long long)offset,
-			       btrfs_shared_data_ref_count(eb, sref));
+			printf("\t\t(%u 0x%llx) shared data backref parent %llu count %u\n",
+			       type, seq, offset, btrfs_shared_data_ref_count(eb, sref));
 			break;
 		case BTRFS_EXTENT_OWNER_REF_KEY:
-			printf("\t\textent owner root %llu\n",
-			       (unsigned long long)offset);
+			printf("\t\(%u 0x%llx) textent owner root %llu\n",
+			       type, seq, offset);
 			break;
 		default:
 			return;
Signature · 1 line
2.42.0
author
#2 lore raw

PATCH 2/3 btrfs-progs: check/lowmem: verify the sequence of inline backref items

In reply to Qu Wenruo

Commit 6cf11f3e3815 ("btrfs-progs: check: check order of inline extent refs") added the ability to detect out-of-order inline extent backref items.

Meanwhile there is no such ability in lowmem mode, this patch would introduce such ability to lowmem mode.

---
 check/mode-lowmem.c | 31 +++++++++++++++++++++++++++++++
 check/mode-lowmem.h |  1 +
 2 files changed, 32 insertions(+)
check/mode-lowmem.c +31 -0
index 3b2807cc5de9..19b7b1a72a1f 100644
@@ -4234,6 +4234,7 @@ static int check_extent_item(struct btrfs_path *path)
 	unsigned long ptr;
 	int slot = path->slots[0];
 	int type;
+	int last_type = 0;
 	u32 nodesize = btrfs_super_nodesize(gfs_info->super_copy);
 	u32 item_size = btrfs_item_size(eb, slot);
 	u64 flags;
@@ -4245,6 +4246,8 @@ static int check_extent_item(struct btrfs_path *path)
 	u64 owner;
 	u64 owner_offset;
 	u64 super_gen;
+	u64 seq;
+	u64 last_seq = U64_MAX;
 	int metadata = 0;
 	/* To handle corrupted values in skinny backref */
 	u64 level;
@@ -4342,6 +4345,32 @@ next:
 	iref = (struct btrfs_extent_inline_ref *)ptr;
 	type = btrfs_extent_inline_ref_type(eb, iref);
 	offset = btrfs_extent_inline_ref_offset(eb, iref);
+	if (type == BTRFS_EXTENT_DATA_REF_KEY) {
+		dref = (struct btrfs_extent_data_ref *)(&iref->offset);
+		seq = hash_extent_data_ref(
+				btrfs_extent_data_ref_root(eb, dref),
+				btrfs_extent_data_ref_objectid(eb, dref),
+				btrfs_extent_data_ref_offset(eb, dref));
+	} else {
+		seq = offset;
+	}
+	/*
+	 * The @type should be ascending, while inside the same type, the
+	 * @seq should be descending.
+	 */
+	if (type < last_type)
+		tmp_err |= BACKREF_OUT_OF_ORDER;
+	else if (type > last_type)
+		last_seq = U64_MAX;
+
+	if (seq > last_seq)
+		tmp_err |= BACKREF_OUT_OF_ORDER;
+
+	if (tmp_err & BACKREF_OUT_OF_ORDER)
+		error(
+"inline extent backref (type %u seq 0x%llx) of extent [%llu %u %llu] is out of order",
+		      type, seq, key.objectid, key.type, key.offset);
+
 	switch (type) {
 	case BTRFS_TREE_BLOCK_REF_KEY:
 		root_objectid = offset;
@@ -4420,6 +4449,8 @@ next:
 
 	err |= tmp_err;
 	ptr_offset += btrfs_extent_inline_ref_size(type);
+	last_type = type;
+	last_seq = seq;
 	goto next;
 
 out:
check/mode-lowmem.h +1 -0
index c3cf0878147f..3f84280a89f7 100644
@@ -64,6 +64,7 @@
 #define UNKNOWN_TYPE		(1 << 6) /* Unknown type */
 #define ACCOUNTING_MISMATCH	(1 << 7) /* Used space accounting error */
 #define CHUNK_TYPE_MISMATCH	(1 << 8)
+#define BACKREF_OUT_OF_ORDER	(1 << 9)
 
 int check_fs_roots_lowmem(void);
 int check_chunks_and_extents_lowmem(void);
Signature · 1 line
2.42.0
author
#3 lore raw

PATCH 3/3 btrfs-progs: fsck-tests: add test image of out-of-order inline backref items

In reply to Qu Wenruo

Issue #622 reported a case where ntfs2btrfs can generate out-of-order inline backref items, which can lead to kernel transaction abort, but not detected by btrfs-check.

This patch would add such image, whose extent tree looks like this for the only data extent:

        item 0 key (13631488 EXTENT_ITEM 4096) itemoff 16172 itemsize 111
                refs 3 gen 7 flags DATA
                (178 0xdfb591fa80d95ea) extent data backref root FS_TREE objectid 257 offset 0 count 1
                (178 0xdfb591fbbf5f519) extent data backref root FS_TREE objectid 258 offset 0 count 1
                (178 0xdfb591f49f9f8e7) extent data backref root FS_TREE objectid 259 offset 0 count 1

While the original good base image has the following backrefs for the same data extent:

        item 0 key (13631488 EXTENT_ITEM 4096) itemoff 16172 itemsize 111
                refs 3 gen 7 flags DATA
                (178 0xdfb591fbbf5f519) extent data backref root FS_TREE objectid 258 offset 0 count 1
                (178 0xdfb591fa80d95ea) extent data backref root FS_TREE objectid 257 offset 0 count 1
                (178 0xdfb591f49f9f8e7) extent data backref root FS_TREE objectid 259 offset 0 count 1

Notice the sequence (the 2nd number in the round brackets) should be descending.
(Meanwhie type should be ascending, but it's way harder to create)

For now we don't have a way to fix it, but at least we should detect it.

---
 .../btrfs_image.xz                            | Bin 0 -> 2264 bytes
 .../061-out-of-order-inline-backref/test.sh   |  19 ++++++++++++++++++
 2 files changed, 19 insertions(+)
 create mode 100644 tests/fsck-tests/061-out-of-order-inline-backref/btrfs_image.xz
 create mode 100755 tests/fsck-tests/061-out-of-order-inline-backref/test.sh
tests/fsck-tests/061-out-of-order-inline-backref/btrfs_image.xz new file binary +0 -0
new file mode 100644
index 0000000000000000000000000000000000000000..65c10617bc250edce2affb3ed91c359041119345
GIT binary patch
tests/fsck-tests/061-out-of-order-inline-backref/test.sh new file +19 -0
new file mode 100755
index 000000000000..f80d58f416f0
@@ -0,0 +1,19 @@
+#!/bin/bash
+#
+# Verify that check can detect out-of-order inline backref items.
+#
+# There is a report that one ntfs2btrfs generated some out-of-order inline
+# backref items, while btrfs-check failed to detect it at all.
+#
+# Make sure btrfs check can at least detect such error.
+
+source "$TEST_TOP/common"
+
+check_prereq btrfs
+
+check_image() {
+	run_mustfail "out-of-order inline backref items not detected" \
+		"$TOP/btrfs" check "$1"
+}
+
+check_all_images
Signature · 1 line
2.42.0
#4 lore raw

Re: [PATCH 3/3] btrfs-progs: fsck-tests: add test image of out-of-order inline backref items

Quoted 4 lines


  .../btrfs_image.xz                            | Bin 0 -> 2264 bytes

check_all_images() won't find btrfs_image.xz image.

        for image in $(find "$dir" \( -iname '*.img' -o \
                                -iname '*.img.xz' -o    \
                                -iname '*.raw' -o       \
                                -iname '*.raw.xz' \) | sort)

What's your plan to test lomem mode?

Thanks, Anand

#5 lore raw

Re: [PATCH 3/3] btrfs-progs: fsck-tests: add test image of out-of-order inline backref items

Quoted 6 lines · Anand Jain
Quoted 4 lines

  .../btrfs_image.xz                            | Bin 0 -> 2264 bytes

check_all_images() won't find  btrfs_image.xz image.

My bad, the filename should be default.img.xz.

David, mind to change that?

Quoted 11 lines

        for image in $(find "$dir" \( -iname '*.img' -o \
                                -iname '*.img.xz' -o    \
                                -iname '*.raw' -o       \
                                -iname '*.raw.xz' \) | sort)

Quoted 1 line

What's your plan to test lomem mode?

The usual way, you can check tests/common.local to see how lowmem mode should be utilized.

Thanks,
Qu

Quoted 5 lines

Thanks, Anand

#6 lore raw

Re: [PATCH 3/3] btrfs-progs: fsck-tests: add test image of out-of-order inline backref items

Quoted 6 lines · Qu Wenruo
Quoted 3 lines · Anand Jain
Quoted 7 lines
Quoted 3 lines
Quoted 1 line

  .../btrfs_image.xz                            | Bin 0 -> 2264 bytes

check_all_images() won't find  btrfs_image.xz image.

My bad, the filename should be default.img.xz.

David, mind to change that?

Renamed and pushed.

Quoted 11 lines
Quoted 11 lines

        for image in $(find "$dir" \( -iname '*.img' -o \
                                -iname '*.img.xz' -o    \
                                -iname '*.raw' -o       \
                                -iname '*.raw.xz' \) | sort)

Quoted 4 lines
Quoted 1 line

What's your plan to test lomem mode?

The usual way, you can check tests/common.local to see how lowmem mode should be utilized.

There are more ways how to run the lowmem mode tests, e.g. 'make test-check-lowmem' that sets up the variables s needed.

#7 lore raw
In reply to Qu Wenruo
Quoted 28 lines · Qu Wenruo

Issue #622 is a very interesting bug report, that ntfs2btrfs has a fixed bug that it can generate out-of-order inline backref items.

This leads to kernel transaction abort, but btrfs-check failed to detect it at all.

Although the fix for btrfs-progs is already merged in the latest v6.5.3 release, we still lacks the following thing:

- Better dump-tree support to show the weird inline backref order This is very weird, as we have the inline type in ascending order, but for the sequence number (hash for EXTENT_DATA_REF, offset for all other types) it is descending inside the same type.

That's why the following output of one data extent item looks out-of-order:

item 0 key (13631488 EXTENT_ITEM 4096) itemoff 16143 itemsize 140
refs 4 gen 7 flags DATA
extent data backref root FS_TREE objectid 258 offset 0 count 1 extent data backref root FS_TREE objectid 257 offset 0 count 1 extent data backref root FS_TREE objectid 260 offset 0 count 1 extent data backref root FS_TREE objectid 259 offset 0 count 1

- Lowmem mode support to detect the error

- Test case to make sure we can detect the error

Quoted 8 lines

This series would address all the three points above.

Qu Wenruo (3):
btrfs-progs: dump-tree: output the sequence number for inline
references
btrfs-progs: check/lowmem: verify the sequence of inline backref items
btrfs-progs: fsck-tests: add test image of out-of-order inline backref
items

Thanks, added to misc-next. We can add ntfs2btrfs conversion tests to btrfs-progs, either with the external utility or on-demand build from git.