[PATCH 0/3] btrfs-progs: fsck: detect obviously invalid metadata backref level

[PATCH 0/3] btrfs-progs: fsck: detect obviously invalid metadata backref level

[Qu Wenruo]

There is a report that kernel tree-checker rejects a tree block of
extent tree, as it contains an obvious corrupted level (which is an
obvious bit flip).

But btrfs check, at least original mode, doesn't detect it at all.
While with my crafted image, lowmem mode would just crash due to the
large level value overflowing path->nodes[level].

Lowmem is enhanced to reject such level, and the existing code will
verify the level and report errors.

Original mode is more tricky, as it doesn't have level check at all.
I don't have a good idea to implement full level check at original mode,
so here I just introduced a basic check for tree level and reject it.

Finally introduce a test case for this.

Qu Wenruo (3):
  btrfs-progs: check/lowmem: fix crash when METADATA_ITEM has invalid
    level
  btrfs: check/original: reject bad metadata backref with invalid level
  btrfs-progs: tests/fsck: add test image with invalid metadata backref
    level

 check/main.c                                  |  19 ++++++++++++++++++
 check/mode-lowmem.c                           |  12 ++++++++++-
 .../053-bad-metadata-level/default.img.xz     | Bin 0 -> 2084 bytes
 .../fsck-tests/053-bad-metadata-level/test.sh |  19 ++++++++++++++++++
 4 files changed, 49 insertions(+), 1 deletion(-)
 create mode 100644 tests/fsck-tests/053-bad-metadata-level/default.img.xz
 create mode 100755 tests/fsck-tests/053-bad-metadata-level/test.sh

-- 
2.34.1

[PATCH 1/3] btrfs-progs: check/lowmem: fix crash when METADATA_ITEM has invalid level

[Qu Wenruo]

[BUG]
When running lowmem mode with METADATA_ITEM which has invalid level, it
will crash with the following backtrace:

 (gdb) bt
 #0  0x0000555555616b0b in btrfs_header_bytenr (eb=0x4)
     at ./kernel-shared/ctree.h:2134
 #1  0x0000555555620c78 in check_tree_block_backref (root_id=5,
     bytenr=30457856, level=256) at check/mode-lowmem.c:3818
 #2  0x0000555555621f6c in check_extent_item (path=0x7fffffffd9c0)
     at check/mode-lowmem.c:4334
 #3  0x00005555556235a5 in check_leaf_items (root=0x555555688e10,
     path=0x7fffffffd9c0, nrefs=0x7fffffffda30, account_bytes=1)
     at check/mode-lowmem.c:4835
 #4  0x0000555555623c6d in walk_down_tree (root=0x555555688e10,
     path=0x7fffffffd9c0, level=0x7fffffffd984, nrefs=0x7fffffffda30,
     check_all=1) at check/mode-lowmem.c:4967
 #5  0x000055555562494f in check_btrfs_root (root=0x555555688e10, check_all=1)
     at check/mode-lowmem.c:5266
 #6  0x00005555556254ee in check_chunks_and_extents_lowmem ()
     at check/mode-lowmem.c:5556
 #7  0x00005555555f0b82 in do_check_chunks_and_extents () at check/main.c:9114
 #8  0x00005555555f50ea in cmd_check (cmd=0x55555567c640 <cmd_struct_check>,
     argc=3, argv=0x7fffffffdec0) at check/main.c:10892
 #9  0x000055555556b2b1 in cmd_execute (argv=0x7fffffffdec0, argc=3,
     cmd=0x55555567c640 <cmd_struct_check>) at cmds/commands.h:125

[CAUSE]
For function check_extent_item() it will go through inline extent items
and then check their backrefs.

But for METADATA_ITEM, it doesn't really validate key.offset, which is
u64 and can contain value way larger than BTRFS_MAX_LEVEL (mostly caused
by bit flip).

In that case, if we have a larger value like 256 in key.offset, then
later check_tree_block_backref() will use 256 as level, and overflow
path->nodes[level] and crash.

[FIX]
Just verify the level, no matter if it's from btrfs_tree_block_level()
(which is just u8), or it's from key.offset (which is u64).

To do the check properly and detect higher bits corruption, also change
the type of @level from u8 to u64.

Now lowmem mode can detect the problem properly:

 ...
 [2/7] checking extents
 ERROR: tree block 30457856 has bad backref level, has 256 expect [0, 7]
 ERROR: extent[30457856 16384] level mismatch, wanted: 0, have: 256
 ERROR: errors found in extent allocation tree or chunk allocation
 [3/7] checking free space tree
 ...

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 check/mode-lowmem.c | 12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)

diff --git a/check/mode-lowmem.c b/check/mode-lowmem.c
index cc6773cd4d0c..99f519631a50 100644
--- a/check/mode-lowmem.c
+++ b/check/mode-lowmem.c
@@ -4242,7 +4242,7 @@ static int check_extent_item(struct btrfs_path *path)
 	u64 owner_offset;
 	u64 super_gen;
 	int metadata = 0;
-	int level;
+	u64 level;	/* To handle corrupted values in skinny backref */
 	struct btrfs_key key;
 	int ret;
 	int err = 0;
@@ -4303,6 +4303,16 @@ static int check_extent_item(struct btrfs_path *path)
 		/* New METADATA_ITEM */
 		level = key.offset;
 	}
+
+	if (metadata && level >= BTRFS_MAX_LEVEL) {
+		error(
+	"tree block %llu has bad backref level, has %llu expect [0, %u]",
+		      key.objectid, level, BTRFS_MAX_LEVEL - 1);
+		err |= BACKREF_MISMATCH;
+		/* This is a critical error, exit right now */
+		goto out;
+	}
+
 	ptr_offset = ptr - (unsigned long)ei;
 
 next:
-- 
2.34.1

[PATCH 2/3] btrfs: check/original: reject bad metadata backref with invalid level

[Qu Wenruo]

[BUG]
There is a bug report that kernel tree-checker rejected an invalid
metadata item:

 corrupt leaf: block=934474399744 slot=68 extent bytenr=425173254144 len=16384 invalid tree level, have 33554432 expect [0, 7]

But original mode btrfs-check reports nothing wrong.
(BTW, lowmem mode will just crash, and fixed in previous patch).

[CAUSE]
For original mode it doesn't really check tree level, thus didn't find
the problem.

[FIX]
I don't have a good idea to completely make original mode to verify the
level in backref and in the tree block (while lowmem does that).

But at least we can detect obviouly corrupted level just like kernel.

Now original mode will detect such problem:

 ...
 [2/7] checking extents
 ERROR: tree block 30457856 has bad backref level, has 256 expect [0, 7]
 ref mismatch on [30457856 16384] extent item 0, found 1
 tree backref 30457856 root 5 not found in extent tree
 backpointer mismatch on [30457856 16384]
 ERROR: errors found in extent allocation tree or chunk allocation
 [3/7] checking free space tree
 ...

Reported-by: Stickstoff <stickstoff@posteo.de>
Link: https://lore.kernel.org/linux-btrfs/6ed4cd5a-7430-f326-4056-25ae7eb44416@posteo.de/
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 check/main.c | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)

diff --git a/check/main.c b/check/main.c
index 540130b8e223..2dea2acf5104 100644
--- a/check/main.c
+++ b/check/main.c
@@ -5447,6 +5447,25 @@ static int process_extent_item(struct btrfs_root *root,
 	if (metadata)
 		btrfs_check_subpage_eb_alignment(gfs_info, key.objectid, num_bytes);
 
+	ptr = (unsigned long)(ei + 1);
+	if (metadata) {
+		u64 level;
+
+		if (key.type == BTRFS_EXTENT_ITEM_KEY) {
+			struct btrfs_tree_block_info *info;
+
+			info = (struct btrfs_tree_block_info *)ptr;
+			level = btrfs_tree_block_level(eb, info);
+		} else {
+			level = key.offset;
+		}
+		if (level >= BTRFS_MAX_LEVEL) {
+			error(
+	"tree block %llu has bad backref level, has %llu expect [0, %u]",
+			      key.objectid, level, BTRFS_MAX_LEVEL - 1);
+			return -EIO;
+		}
+	}
 	memset(&tmpl, 0, sizeof(tmpl));
 	tmpl.start = key.objectid;
 	tmpl.nr = num_bytes;
-- 
2.34.1

[PATCH 3/3] btrfs-progs: tests/fsck: add test image with invalid metadata backref level

[Qu Wenruo]

The image has a key in extent tree, (30457856 METADATA_ITEM 256), which
has invalid level (256 > BTRFS_MAX_LEVEL).

Make sure check can at least detect such problem.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 .../053-bad-metadata-level/default.img.xz     | Bin 0 -> 2084 bytes
 .../fsck-tests/053-bad-metadata-level/test.sh |  19 ++++++++++++++++++
 2 files changed, 19 insertions(+)
 create mode 100644 tests/fsck-tests/053-bad-metadata-level/default.img.xz
 create mode 100755 tests/fsck-tests/053-bad-metadata-level/test.sh

diff --git a/tests/fsck-tests/053-bad-metadata-level/default.img.xz b/tests/fsck-tests/053-bad-metadata-level/default.img.xz
new file mode 100644
index 0000000000000000000000000000000000000000..d7debee7b7c2bb457dbe734da2429859245770ae
GIT binary patch
literal 2084
zcmV+<2;2AlH+ooF000E$*0e?f03iV!0000G&sfah5B~?`T>wRyj;C3^v%$$4d1r37
zhA1?^)Fb!kgA6~+!%84I;Io073Dhl?^BD<@UPMs(i~SGmBKxebUa%|NH;s2ul#JQO
zdsro>jHw^5Bn(Nv<#H=CdIZ2*)=~SDhF_~|WjY(kiko@U%p+|l?;k=gV%ewSRP-|S
z?BE&UdM?8uB<oUlOWhq~3N~<O&loyUj}<x_M>)@>{L_lap2__bX+WIXj=6NJFb{;4
zz#!|S8#)thnJ#~l-e*7Y-goW)P>h<WF5=7&8??VwCXnAp2%G`cJ>7W+=mEq$8A&?H
zH>VhM_aZ&@;FbBmPB)>)g2mb2qvObjw*ZeQ9)7yHYRr5WjlBO9>59Fq0p&tpKru@f
zSnEL^6r~r?Q_<^#k1o6r6Qzl`u*m{O2d7%B%MAdye)uA;xUv)+*U`Fk07{dZ5O<cY
z3nEA02)fFshDUaHKrTrVP6vAO;t~0Lu9Mhvb2o_Oe@o7FC#$#y2}hOVBl<=l?47-V
z&8Ks>7~4J0&dbG@d!q__B~HGD_X)Nv#wiD)Z5|8b&4_OaJnzjnRrFBkva0eP7wOc=
z9k|7%(g#V`NW1Yi2V~W3!(t@viUZ*Y_iFH`KUC%2OEwQ6$={D1p1d65*#NER76#u*
zgsH_K<65`&3IG6h4A%8}wFXo05T9<k7tZ_iYp8?MPP0*1V!13b+f6t0fY9EF{<k<k
zT&9FN3l(g7c?6fV7O6p>he*zt#n*H9FO=hsSeD4fzE;WgeYeB_%zTX@?MOlFZaH@3
zI%GQWE;MkNPz71gKM_W~U0t!fQ-{at1TNwRQ4i|{OdG)~_*bKSP=&d$1zd}qW*SR#
z8q@ZC5v4ikhRx}8h4Z@KW~W^8`|Dc(BQ<X<mVzWFs?Fp^r;dvr9(LCWxtLU(6EsKH
zTt``BD{pq8c$Wvb!GwMtbM796WJ<#Apwt7+5P0_}rw3JjJYW}`R5ONUjr}mqc5N4*
z1V>&imQC^XD^pA_<S=3S<CF86%ut&-MC6sPF+XjspmM;py~|+-qv!a5R#QeMSdJv%
zh(pT=jc2QY;JC=-@8(OIZJZK{qp9;1s)w8W51?tuY@$Zs$Rh2TKpe$oy_!ispVf}1
z0#yUKBe6on&Q*SS2P`O`#zO+<gGlxpa^#a5_VdIup@~CZ>sb27?**w9h4LDiyT6zs
z$C0D}$-5kC8oeqIo;M<Xf(A^;SQ-fCC2(98+^-RyHFrSA<*x1VUa3=-f|tG#ld9;e
zAp{5eoJZY$8XAl;pirahB%GYf;>V#&vuU-B`5#)f%>2om20q;Dn;r3Ji6}ZIT@_-v
zIS3=;d+Rh>!B23HzAV4L$7!Zr2~-2UWHQ0dk2FH1@348;K)W#-HvM@@ezYHYNk@6E
zE&RDrfhVCeC723bkql?L;kaIlTfG^@U}4=2-}cV6^786|O}-Rm9!|#r1-AP?alt@)
zTFzMkQ!-r9Px?BT;z;cuhFym;wCCgi*4))ktG1sCu^};%Dly@;lan_JgcqIWR!>j*
zt-j)o!F!kEFkG(zHyU)4X7vS*iYcb}b@uwEwxU#O7&UDG5=*OragqG=LE=$K3Vhz_
z?s7>&LbeHzY56VlOAK#0+jQ3#JkO!!kC`U%lX<~u6EEUAO~nEvvhM2`nmZ?Ni>Ssh
zXl<Q{Hr3y8zp%nDF!u^<;fM7(IvEL#&zaH$YwH4=VL{ui{H<yJL?9#Kj+J^{pyL9m
zwb{+OMB=^VuL-9&Yr$!1o&QT6m8ex9R0&Tv*qsw2JSF2LtgS0xE9r8PhkVf9-g^b)
zu;#6V>4AfSGHqPE${F-{1dcftvT7I)=J_P^<p{<7_v8V)rcEt1%ve5=oDil}RD8!y
zuP!=YklbXH_6NO$9XeOT!O2H^d>3txD=pdjO+O`BKTE!g+~;@5&|*P7N13Gur4<F<
ztF|ygJ4wH2=z&i^0ERyt>J>M|CJp+4f;Uq1(P<_mj6a$?QF4yO(`dA*mo97#v<1R7
zKo$1kosEdTYu6&fB;Py?WHf)LvqsK0@Xb+e$$ZUJ+;+^V7)F@llgX|5+fRqc-vK_-
z^ao9u&DXIEeC?JNQ}N2I{`Z6-g`?FyY?}>`2kIv=lFS5K*@25Q%AKE8LT(W3rv$Fk
zAQan19()zdNpcFLnX!5FSVYICYOCjrd1yW;i2&NAHM_bTFo(#t+s94>&yAZJFxb)^
z@On%Gmj%SRW&otTkqfvh4Yp9Bs+?7IZ(|Ns4PQ}pKRD7vMRfQ_LuK1zQ~E!6WF3l7
zq(b!*XZh5WPV3ptP<uEUEgdFsoa!n){G}K0&<{Q57kt(trYBjkf9$1g-!JO2S>^};
zS0Yze#s$ezKolT}@-a#CN{(3zs^b<7JtV?}-gg({DJSFzG0)SHMTQspmtd0P3-IOD
zp)D^?z^Yff_S;;5O8?0xps49sGvmgT#QXG#*C`lb0hF7-5m$P<x-0u?vOU0Q;xgdA
zR6kI*n4XC+pAD$iWuZ%`k&Cx|2I&Xx_ObN4SPdacg|<t4Op(vpAt6QYteN&Ju=Euy
zX7y?pi%W>j9_5$iIr(*ABrqHPM>KGPB<X9Cqhq)efWg}#>eVjxBy${Sg}ssw3uEf@
ze$O}l^tEbM-B&v2(o%T6BVHOLU$;pf#aIHdQ2+o8$#zZUQHkUL0e}#IAOHYdrx9qe
O#Ao{g000001X)_pOZyN2

literal 0
HcmV?d00001

diff --git a/tests/fsck-tests/053-bad-metadata-level/test.sh b/tests/fsck-tests/053-bad-metadata-level/test.sh
new file mode 100755
index 000000000000..0ffd7bdf34a1
--- /dev/null
+++ b/tests/fsck-tests/053-bad-metadata-level/test.sh
@@ -0,0 +1,19 @@
+#!/bin/bash
+#
+# Verify that check can detect invalid metadata backref level.
+#
+# There is a report that btrfs-check original mode doesn't report invalid
+# metadata backref level, and lowmem mode would just crash.
+#
+# Make sure btrfs check can at least detect such error.
+
+source "$TEST_TOP/common"
+
+check_prereq btrfs
+
+check_image() {
+	run_mustfail "invalid metadata backref level not detected" \
+		"$TOP/btrfs" check "$1"
+}
+
+check_all_images
-- 
2.34.1

Re: [PATCH 1/3] btrfs-progs: check/lowmem: fix crash when METADATA_ITEM has invalid level

[Su Yue]

On Mon 17 Jan 2022 at 10:38, Qu Wenruo <wqu@suse.com> wrote:

> [BUG]
> When running lowmem mode with METADATA_ITEM which has invalid 
> level, it
> will crash with the following backtrace:
>
>  (gdb) bt
>  #0  0x0000555555616b0b in btrfs_header_bytenr (eb=0x4)
>      at ./kernel-shared/ctree.h:2134
>  #1  0x0000555555620c78 in check_tree_block_backref (root_id=5,
>      bytenr=30457856, level=256) at check/mode-lowmem.c:3818
>  #2  0x0000555555621f6c in check_extent_item 
>  (path=0x7fffffffd9c0)
>      at check/mode-lowmem.c:4334
>  #3  0x00005555556235a5 in check_leaf_items 
>  (root=0x555555688e10,
>      path=0x7fffffffd9c0, nrefs=0x7fffffffda30, account_bytes=1)
>      at check/mode-lowmem.c:4835
>  #4  0x0000555555623c6d in walk_down_tree (root=0x555555688e10,
>      path=0x7fffffffd9c0, level=0x7fffffffd984, 
>      nrefs=0x7fffffffda30,
>      check_all=1) at check/mode-lowmem.c:4967
>  #5  0x000055555562494f in check_btrfs_root 
>  (root=0x555555688e10, check_all=1)
>      at check/mode-lowmem.c:5266
>  #6  0x00005555556254ee in check_chunks_and_extents_lowmem ()
>      at check/mode-lowmem.c:5556
>  #7  0x00005555555f0b82 in do_check_chunks_and_extents () at 
>  check/main.c:9114
>  #8  0x00005555555f50ea in cmd_check (cmd=0x55555567c640 
>  <cmd_struct_check>,
>      argc=3, argv=0x7fffffffdec0) at check/main.c:10892
>  #9  0x000055555556b2b1 in cmd_execute (argv=0x7fffffffdec0, 
>  argc=3,
>      cmd=0x55555567c640 <cmd_struct_check>) at 
>      cmds/commands.h:125
>
> [CAUSE]
> For function check_extent_item() it will go through inline 
> extent items
> and then check their backrefs.
>
> But for METADATA_ITEM, it doesn't really validate key.offset, 
> which is
> u64 and can contain value way larger than BTRFS_MAX_LEVEL 
> (mostly caused
> by bit flip).
>
> In that case, if we have a larger value like 256 in key.offset, 
> then
> later check_tree_block_backref() will use 256 as level, and 
> overflow
> path->nodes[level] and crash.
>
> [FIX]
> Just verify the level, no matter if it's from 
> btrfs_tree_block_level()
> (which is just u8), or it's from key.offset (which is u64).
>
> To do the check properly and detect higher bits corruption, also 
> change
> the type of @level from u8 to u64.
>
> Now lowmem mode can detect the problem properly:
>
>  ...
>  [2/7] checking extents
>  ERROR: tree block 30457856 has bad backref level, has 256 
>  expect [0, 7]
>  ERROR: extent[30457856 16384] level mismatch, wanted: 0, have: 
>  256
>  ERROR: errors found in extent allocation tree or chunk 
>  allocation
>  [3/7] checking free space tree
>  ...
>
> Signed-off-by: Qu Wenruo <wqu@suse.com>
>
Reviewed-by: Su Yue <l@damenly.su>

--
Su
> ---
>  check/mode-lowmem.c | 12 +++++++++++-
>  1 file changed, 11 insertions(+), 1 deletion(-)
>
> diff --git a/check/mode-lowmem.c b/check/mode-lowmem.c
> index cc6773cd4d0c..99f519631a50 100644
> --- a/check/mode-lowmem.c
> +++ b/check/mode-lowmem.c
> @@ -4242,7 +4242,7 @@ static int check_extent_item(struct 
> btrfs_path *path)
>  	u64 owner_offset;
>  	u64 super_gen;
>  	int metadata = 0;
> -	int level;
> +	u64 level;	/* To handle corrupted values in skinny 
> backref */
>  	struct btrfs_key key;
>  	int ret;
>  	int err = 0;
> @@ -4303,6 +4303,16 @@ static int check_extent_item(struct 
> btrfs_path *path)
>  		/* New METADATA_ITEM */
>  		level = key.offset;
>  	}
> +
> +	if (metadata && level >= BTRFS_MAX_LEVEL) {
> +		error(
> +	"tree block %llu has bad backref level, has %llu expect 
> [0, %u]",
> +		      key.objectid, level, BTRFS_MAX_LEVEL - 1);
> +		err |= BACKREF_MISMATCH;
> +		/* This is a critical error, exit right now */
> +		goto out;
> +	}
> +
>  	ptr_offset = ptr - (unsigned long)ei;
>
>  next:

Re: [PATCH 2/3] btrfs: check/original: reject bad metadata backref with invalid level

[Su Yue]

On Mon 17 Jan 2022 at 10:38, Qu Wenruo <wqu@suse.com> wrote:

> [BUG]
> There is a bug report that kernel tree-checker rejected an 
> invalid
> metadata item:
>
>  corrupt leaf: block=934474399744 slot=68 extent 
>  bytenr=425173254144 len=16384 invalid tree level, have 33554432 
>  expect [0, 7]
>
> But original mode btrfs-check reports nothing wrong.
> (BTW, lowmem mode will just crash, and fixed in previous patch).
>
> [CAUSE]
> For original mode it doesn't really check tree level, thus 
> didn't find
> the problem.
>
> [FIX]
> I don't have a good idea to completely make original mode to 
> verify the
> level in backref and in the tree block (while lowmem does that).
>
> But at least we can detect obviouly corrupted level just like 
> kernel.
>
> Now original mode will detect such problem:
>
>  ...
>  [2/7] checking extents
>  ERROR: tree block 30457856 has bad backref level, has 256 
>  expect [0, 7]
>  ref mismatch on [30457856 16384] extent item 0, found 1
>  tree backref 30457856 root 5 not found in extent tree
>  backpointer mismatch on [30457856 16384]
>  ERROR: errors found in extent allocation tree or chunk 
>  allocation
>  [3/7] checking free space tree
>  ...
>
> Reported-by: Stickstoff <stickstoff@posteo.de>
> Link: 
> https://lore.kernel.org/linux-btrfs/6ed4cd5a-7430-f326-4056-25ae7eb44416@posteo.de/
> Signed-off-by: Qu Wenruo <wqu@suse.com>
> ---
>  check/main.c | 19 +++++++++++++++++++
>  1 file changed, 19 insertions(+)
>
> diff --git a/check/main.c b/check/main.c
> index 540130b8e223..2dea2acf5104 100644
> --- a/check/main.c
> +++ b/check/main.c
> @@ -5447,6 +5447,25 @@ static int process_extent_item(struct 
> btrfs_root *root,
>  	if (metadata)
>  		btrfs_check_subpage_eb_alignment(gfs_info, 
>  key.objectid, num_bytes);
>
> +	ptr = (unsigned long)(ei + 1);
> +	if (metadata) {
> +		u64 level;
> +
> +		if (key.type == BTRFS_EXTENT_ITEM_KEY) {
> +			struct btrfs_tree_block_info *info;
> +
> +			info = (struct btrfs_tree_block_info 
> *)ptr;
> +			level = btrfs_tree_block_level(eb, info);
> +		} else {
> +			level = key.offset;
> +		}
> +		if (level >= BTRFS_MAX_LEVEL) {
> +			error(
> +	"tree block %llu has bad backref level, has %llu expect 
> [0, %u]",
> +			      key.objectid, level, BTRFS_MAX_LEVEL 
> - 1);
> +			return -EIO;
>
-EUCLEAN is better?

Reviewed-by: Su Yue <l@damenly.su>
--
Su
> +		}
> +	}
>  	memset(&tmpl, 0, sizeof(tmpl));
>  	tmpl.start = key.objectid;
>  	tmpl.nr = num_bytes;

Re: [PATCH 2/3] btrfs: check/original: reject bad metadata backref with invalid level

[David Sterba]

On Mon, Jan 17, 2022 at 10:48:29AM +0800, Su Yue wrote:
> 
> On Mon 17 Jan 2022 at 10:38, Qu Wenruo <wqu@suse.com> wrote:
> 
> > [BUG]
> > There is a bug report that kernel tree-checker rejected an 
> > invalid
> > metadata item:
> >
> >  corrupt leaf: block=934474399744 slot=68 extent 
> >  bytenr=425173254144 len=16384 invalid tree level, have 33554432 
> >  expect [0, 7]
> >
> > But original mode btrfs-check reports nothing wrong.
> > (BTW, lowmem mode will just crash, and fixed in previous patch).
> >
> > [CAUSE]
> > For original mode it doesn't really check tree level, thus 
> > didn't find
> > the problem.
> >
> > [FIX]
> > I don't have a good idea to completely make original mode to 
> > verify the
> > level in backref and in the tree block (while lowmem does that).
> >
> > But at least we can detect obviouly corrupted level just like 
> > kernel.
> >
> > Now original mode will detect such problem:
> >
> >  ...
> >  [2/7] checking extents
> >  ERROR: tree block 30457856 has bad backref level, has 256 
> >  expect [0, 7]
> >  ref mismatch on [30457856 16384] extent item 0, found 1
> >  tree backref 30457856 root 5 not found in extent tree
> >  backpointer mismatch on [30457856 16384]
> >  ERROR: errors found in extent allocation tree or chunk 
> >  allocation
> >  [3/7] checking free space tree
> >  ...
> >
> > Reported-by: Stickstoff <stickstoff@posteo.de>
> > Link: 
> > https://lore.kernel.org/linux-btrfs/6ed4cd5a-7430-f326-4056-25ae7eb44416@posteo.de/
> > Signed-off-by: Qu Wenruo <wqu@suse.com>
> > ---
> >  check/main.c | 19 +++++++++++++++++++
> >  1 file changed, 19 insertions(+)
> >
> > diff --git a/check/main.c b/check/main.c
> > index 540130b8e223..2dea2acf5104 100644
> > --- a/check/main.c
> > +++ b/check/main.c
> > @@ -5447,6 +5447,25 @@ static int process_extent_item(struct 
> > btrfs_root *root,
> >  	if (metadata)
> >  		btrfs_check_subpage_eb_alignment(gfs_info, 
> >  key.objectid, num_bytes);
> >
> > +	ptr = (unsigned long)(ei + 1);
> > +	if (metadata) {
> > +		u64 level;
> > +
> > +		if (key.type == BTRFS_EXTENT_ITEM_KEY) {
> > +			struct btrfs_tree_block_info *info;
> > +
> > +			info = (struct btrfs_tree_block_info 
> > *)ptr;
> > +			level = btrfs_tree_block_level(eb, info);
> > +		} else {
> > +			level = key.offset;
> > +		}
> > +		if (level >= BTRFS_MAX_LEVEL) {
> > +			error(
> > +	"tree block %llu has bad backref level, has %llu expect 
> > [0, %u]",
> > +			      key.objectid, level, BTRFS_MAX_LEVEL 
> > - 1);
> > +			return -EIO;
> >
> -EUCLEAN is better?

Yes, updated in patch, thanks.

Re: [PATCH 0/3] btrfs-progs: fsck: detect obviously invalid metadata backref level

[David Sterba]

On Mon, Jan 17, 2022 at 10:38:47AM +0800, Qu Wenruo wrote:
> There is a report that kernel tree-checker rejects a tree block of
> extent tree, as it contains an obvious corrupted level (which is an
> obvious bit flip).
> 
> But btrfs check, at least original mode, doesn't detect it at all.
> While with my crafted image, lowmem mode would just crash due to the
> large level value overflowing path->nodes[level].
> 
> Lowmem is enhanced to reject such level, and the existing code will
> verify the level and report errors.
> 
> Original mode is more tricky, as it doesn't have level check at all.
> I don't have a good idea to implement full level check at original mode,
> so here I just introduced a basic check for tree level and reject it.
> 
> Finally introduce a test case for this.
> 
> Qu Wenruo (3):
>   btrfs-progs: check/lowmem: fix crash when METADATA_ITEM has invalid
>     level
>   btrfs: check/original: reject bad metadata backref with invalid level
>   btrfs-progs: tests/fsck: add test image with invalid metadata backref
>     level

Added to devel, thanks.