[PATCH 0/3] btrfs-progs: add repair support to delete orphan

[PATCH 0/3] btrfs-progs: add repair support to delete orphan

[Qu Wenruo]

This is the same PR in github:
https://github.com/kdave/btrfs-progs/pull/1083

The mail thread is mostly for tracking and review purposes.

Since v6.16.1 btrfs check adds the ability to detect orphan free space
entries, and older mkfs.btrfs forgot to delete free space entries of
temporary chunks, which can be detected by newer btrfs-progs now.

Although we're already pushing for a kernel auto fix, the kernel fix
will take some time to reach upstream, and more time to reach distros.

So there is still some value to have the repair ability in btrfs-check.

Furthermore, the new repair ability is more flex than the kernel one,
which can handle orphan free space info key, not only the ones exposed
by the recent btrfs-check.
Although only the recent exposed one is tested.

Qu Wenruo (3):
  btrfs-progs: check: report all orphan free space info keys
  btrfs-progs: check: add repair support for orphan fst entry
  btrfs-progs: fsck-tests: add a new test case for deleting orphan fst
    entries

 common/clear-cache.c                          | 141 +++++++++++++++++-
 .../071-orphan-fst-entry/.lowmem_repairable   |   0
 .../orphan_fst_entries.img.xz                 | Bin 0 -> 1864 bytes
 3 files changed, 137 insertions(+), 4 deletions(-)
 create mode 100644 tests/fsck-tests/071-orphan-fst-entry/.lowmem_repairable
 create mode 100644 tests/fsck-tests/071-orphan-fst-entry/orphan_fst_entries.img.xz

--
2.52.0

[PATCH 1/3] btrfs-progs: check: report all orphan free space info keys

[Qu Wenruo]

And also output the logical and length for the orphan space info key.

Now the new reports will looks like this:

 [4/8] checking free space tree
 Space key logical 1048576 length 4194304 has no corresponding block group
 Space key logical 5242880 length 8388608 has no corresponding block group

This shouldn't affect end users that much, but provide much better debug
info for developers who want to fix those bad free space tree entries.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 common/clear-cache.c | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)

diff --git a/common/clear-cache.c b/common/clear-cache.c
index 75cd8d50d25a..47d5751ff2c9 100644
--- a/common/clear-cache.c
+++ b/common/clear-cache.c
@@ -138,6 +138,7 @@ static int check_free_space_tree(struct btrfs_root *root)
 	struct btrfs_key key = { 0 };
 	struct btrfs_path path = { 0 };
 	int ret = 0;
+	bool found_orphan = false;
 
 	while (1) {
 		struct btrfs_block_group *bg;
@@ -167,16 +168,19 @@ static int check_free_space_tree(struct btrfs_root *root)
 		bg = btrfs_lookup_block_group(fs_info, key.objectid);
 		if (!bg) {
 			fprintf(stderr,
-		"We have a space info key for a block group that doesn't exist\n");
-			ret = -EINVAL;
-			goto out;
+"Space key logical %llu length %llu has no corresponding block group\n",
+				key.objectid, key.offset);
+			found_orphan = true;
 		}
 
 		btrfs_release_path(&path);
 		key.objectid += key.offset;
 		key.offset = 0;
 	}
-	ret = 0;
+	if (found_orphan)
+		ret = -EINVAL;
+	else
+		ret = 0;
 out:
 	btrfs_release_path(&path);
 	return ret;
-- 
2.52.0

[PATCH 2/3] btrfs-progs: check: add repair support for orphan fst entry

[Qu Wenruo]

Although we're pushing for the kernel auto fix, it may still take some
time.
Meanwhile having a proper way to fix it in progs will never hurt.

The repair itself is a little more complex than the kernel one, which
only needs to bother the entries before the first block group.

This progs version in theory is able to handle orphan entries at any
location, but for now it's only for the entries before the first bg.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 common/clear-cache.c | 131 ++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 130 insertions(+), 1 deletion(-)

diff --git a/common/clear-cache.c b/common/clear-cache.c
index 47d5751ff2c9..69e91e5e7796 100644
--- a/common/clear-cache.c
+++ b/common/clear-cache.c
@@ -29,6 +29,7 @@
 #include "kernel-shared/volumes.h"
 #include "kernel-shared/transaction.h"
 #include "kernel-shared/file-item.h"
+#include "kernel-shared/print-tree.h"
 #include "common/internal.h"
 #include "common/messages.h"
 #include "common/clear-cache.h"
@@ -132,6 +133,128 @@ close_out:
 	return ret;
 }
 
+/*
+ * Return 0 if we found an fst entry in range [start, start + length), @path will
+ * be updated to pointing to that entry.
+ *
+ * Return >0 if we found no more fst entry in range [start, start + length).
+ *
+ * Return <0 for error.
+ */
+static int find_first_fst_entry(struct btrfs_root *root, struct btrfs_path *path,
+				u64 start, u64 length)
+{
+	struct btrfs_key key = { .objectid = start };
+	int ret;
+
+	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
+	if (unlikely(ret < 0))
+		goto out;
+	if (unlikely(ret == 0)) {
+		ret = -EUCLEAN;
+		error("unexpected key found in slot %u\n", path->slots[0]);
+		btrfs_print_leaf(path->nodes[0]);
+		goto out;
+	}
+	while (true) {
+		if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
+			ret = btrfs_next_leaf(root, path);
+			if (ret)
+				goto out;
+		}
+		btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
+		/* Beyond the range. No more entry. */
+		if (key.objectid >= start + length) {
+			ret = 1;
+			goto out;
+		}
+		/* In the range, return this one. */
+		if (key.objectid >= start && key.objectid < start + length)
+			break;
+
+		/* The current key is small than our range, continue searching. */
+		path->slots[0]++;
+	}
+
+	/* We found a key in our range. */
+	UASSERT(path->nodes[0]);
+	return 0;
+out:
+	UASSERT(ret != 0);
+	btrfs_release_path(path);
+	return ret;
+}
+
+static int remove_free_space_entries(struct btrfs_root *root, struct btrfs_path *path,
+				     const struct btrfs_key *space_info_key)
+{
+	struct btrfs_trans_handle *trans = NULL;
+	u64 start = space_info_key->objectid;
+	const u64 end = start + space_info_key->offset - 1;
+	u64 cur = start;
+	int ret;
+
+	while (cur <= end) {
+		struct btrfs_key found_key;
+		int found_slot;
+		int last_slot;
+
+		ret = find_first_fst_entry(root, path, cur, end + 1 - cur);
+		if (ret < 0)
+			goto error;
+		if (ret > 0)
+			break;
+
+		btrfs_item_key_to_cpu(path->nodes[0], &found_key, path->slots[0]);
+		btrfs_release_path(path);
+
+		trans = btrfs_start_transaction(root, 1);
+		if (IS_ERR(trans)) {
+			error_msg(ERROR_MSG_START_TRANS, "remove orphan fst entry");
+			return PTR_ERR(trans);
+		}
+		ret = btrfs_search_slot(trans, root, &found_key, path, -1, 1);
+		if (ret > 0)
+			ret = -ENOENT;
+		if (ret < 0)
+			goto error;
+
+		found_slot = path->slots[0];
+
+		/*
+		 * @last_slot will be the next slot of the last item which matches
+		 * our range.
+		 */
+		for (last_slot = found_slot + 1;
+		     last_slot < btrfs_header_nritems(path->nodes[0]); last_slot++){
+			btrfs_item_key_to_cpu(path->nodes[0], &found_key, last_slot);
+			if (found_key.objectid >= start && found_key.objectid <= end)
+				cur = found_key.objectid;
+			else
+				break;
+		}
+		ret = btrfs_del_items(trans, root, path, found_slot,
+				      last_slot - found_slot);
+		if (ret < 0)
+			goto error;
+		btrfs_release_path(path);
+		ret = btrfs_commit_transaction(trans, root);
+		trans = NULL;
+		if (ret < 0) {
+			error_msg(ERROR_MSG_START_TRANS, "remove orphan fst entry");
+			goto error;
+		}
+	}
+	printf("deleted orphan fst entries for range [%llu, %llu)\n",
+		start, end + 1);
+	return 0;
+error:
+	btrfs_release_path(path);
+	if (trans)
+		btrfs_abort_transaction(trans, ret);
+	return ret;
+}
+
 static int check_free_space_tree(struct btrfs_root *root)
 {
 	struct btrfs_fs_info *fs_info = root->fs_info;
@@ -167,10 +290,16 @@ static int check_free_space_tree(struct btrfs_root *root)
 
 		bg = btrfs_lookup_block_group(fs_info, key.objectid);
 		if (!bg) {
+			btrfs_release_path(&path);
 			fprintf(stderr,
 "Space key logical %llu length %llu has no corresponding block group\n",
 				key.objectid, key.offset);
-			found_orphan = true;
+			if (opt_check_repair)
+				ret = remove_free_space_entries(root, &path, &key);
+			else
+				ret = -EINVAL;
+			if (ret < 0)
+				found_orphan = true;
 		}
 
 		btrfs_release_path(&path);
-- 
2.52.0

[PATCH 3/3] btrfs-progs: fsck-tests: add a new test case for deleting orphan fst entries

[Qu Wenruo]

The image is created by creating an empty btrfs with older v6.16 btrfs-progs.
Which has free space tree entries for two temporary block groups.

And the test itself is going through the common repair test procedure.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 .../071-orphan-fst-entry/.lowmem_repairable      |   0
 .../orphan_fst_entries.img.xz                    | Bin 0 -> 1864 bytes
 2 files changed, 0 insertions(+), 0 deletions(-)
 create mode 100644 tests/fsck-tests/071-orphan-fst-entry/.lowmem_repairable
 create mode 100644 tests/fsck-tests/071-orphan-fst-entry/orphan_fst_entries.img.xz

diff --git a/tests/fsck-tests/071-orphan-fst-entry/.lowmem_repairable b/tests/fsck-tests/071-orphan-fst-entry/.lowmem_repairable
new file mode 100644
index 000000000000..e69de29bb2d1
diff --git a/tests/fsck-tests/071-orphan-fst-entry/orphan_fst_entries.img.xz b/tests/fsck-tests/071-orphan-fst-entry/orphan_fst_entries.img.xz
new file mode 100644
index 0000000000000000000000000000000000000000..bc68661b1e1917da5266c50747e6c7f14cfecf49
GIT binary patch
literal 1864
zcmexsUKJ6=z`*kC+7>sK18sZ_5{is63=j}*w)pA;?*DB6Vi{a#_AQUxxB1{nsmk=c
z?QI$+2U=UjA7?I^>+#4wGrpwg{sgWdYqyx(!Z$xB?eM-~oiyKSi?@c_zic6+d;j?)
zIBt|JnZPL&A^y?8>#4y~#jcVb)_I2?dmjsOuDAIfeRJc{zh~y1J)0`hu<qo!k24SL
zzJ7gS$iBP#%yRqtjpm7Q%bP`hI{ohLmnDU9-urC-MtlgK?VokD$fN0qB+D-wPwyRi
zZ5!Qw1wDEEa@t7;SIvuF^OJXH%>KMAuE1*hX}y^z^LML%Hz;8V^GMrqBUSN|VE{``
z$*fCJLL0X2e`Wfk>Ps`vsYTi*>AQBwS$;h%Wd5x0{-v$Q8)wV9>npC#i<xj_wch`I
z&s`rb<=fD9xBrUrw6IC1e(syR`Uq3`gN$z{j&{wxvt90W@D=M*^_j~1p6BPE+PlcH
zDRGL$vc0Rgi)PJQ_{3NG)Cn2?!pr<2d`ouv)P4_jW>M%-dt$QdW}Mh6+xUZjJ+C`g
zNtmnMkiM^Q(`k#lykGpm(^F$xU+m*8oORqZ@AvC0xqJWYCjRP|WA8Ie50hcrs+*iw
z{fKAAk;e{+j*-uT)xT9=HTmMmRv7p9Khq8CD8Am}(+Z6S%lk?Sjy#_I<l=ARMJN7j
zi0in(lx}(a(XD88yC>=EvbfGEOh2}{U*FU*@8CVn-VgWpZV#KyJ2Ni!Z0PA~o!<fv
z_-pyM{@&l9^YZnB6Spe=b^Z^iRei5qQM>c+eCr*jCRQ_VcqQ1M&BnOU@{{i$2G;Jg
zF$aVTJ|8&Q+41?O*XI3Pr&xdg-J7-e>(2n+!}rouO1ynvtTHs#?J``M>%cE{r?)QW
z&bc=lukXw{{4DvBxar;xa&?g${yMLh?lzq#>?Y@aY|iQKqHmm{VFC8PE2Ou5cYLqt
zm0&IO<ioe8&VkBVssSp(6T`h8?7up}>*3Eu%u@Hh99lC~N~Ugi^NF`#R2T#oGyYpI
z{&d5!45iS3l#J|G#dGFK_N67KBu|fQsJuJv%vLMGxl5yMrg)U(-D>G)T=IWgclxda
zH#|4Qf0oYT?=>?^+{S-3QGoA)soH1G+(Oke&QaQ1CKqRK(F~}Q{v;rf&gr&f=Jgth
z8GQH82kfn5&0eC%tLn=<^@HRpHdmpIYQB@cyxFIE@v)<FwZG%BtLq=9n<bq4^h0>s
ztRIs%Mci&H4t(@l=xbDJ=!dG)lWsVje66SGw&kcq-3-RHZy0W~Tw2I`;mzu$s*fd0
z>z1$gU#t9NkK92E(YI$)xOXQUVO@IXuwe0|)nUo(hL86gkIJ)NB=p$t-xd2@p}N2)
zaWS_wSswi@?sAxR{gK^@4`zLdA3|r82fi<!xglc#!*97=X7lFrpX^b2rnTe!WSPKa
z^O=PI^Gd`P{kK#XTXZgxCAziwjnK*Gg$etGyiP{EPJVVuC2i%IH8M9APM-eYe*A+A
z*MiS~v16{>@lQGKmD2^i^p27XKX-7eKbfL&*Ne3|>cO21YnJ$u^@V}Yj#hnoJ>mCC
zjrTK``<}Sv7u>~Jd3Vb>{S|SHNnIYPjax2y#~cY;HGj{sz5O3{hTh}as+B$S(JiyA
zy^G=nH5{aVZY|)KQ@oM=|8M20CvLAL8A{lv$(tk`(6@dc{^|S&_QMK`#bY0oO_BH%
z`uE8rexc^qXS|o(*!y6AvWEMu6BFZ8f6quOf7kHp#P783UAqO}WmqhItbF23B)1Rm
z>SJ8{^5WNgE6De|oS*dBckgD~oOxRw{`xb&^m-xVIc>$v`~&kemmk<vC*c3|fW?Q*
zn;N1j4Pk3O>&%@QdnI!->uWm|_Gil`JMr=MCDgvj;&``jv5;Au%i+j74BGor9o`xT
zTX21dtlRQvd5Ueh^4xDCTS^6uqt9(vW|t69rY?1C>e^qYtBOr)a$^djviIbL&3C$#
zQFM~usr6H!`Oz2E2RCmyw0&;G?c~!J=DgMuwlCe$7_d8A$n&WNf6_G1C9^9F1T<oe
zXDZzBTJ5m$Y-d<t;0&hg+s=e(T;SVV#J1bvYK+1h#d#83rN;Y@NAH#^<+6WO=%N?F
zxZ_PrMa8;X$MZXWDQvP^-LYG*%A@c7T=5h8df%;RR2QuBubTFKfp@}*t?{eZt)1qy
ztKq{&@w5LzBpx2UtiM)WU~yY~*ox`X7$fKL<XGIbk$WV<#2v_7@-^b#ihHu#ZP(W~
z{CvUbaC@P>zNPaQ*W#KThkATkJtbIft6BWr@tINK-lY3m?L}Q|jRlQcJA#fau>N2o
zeB3(W&rEZ_0|m2I`@d>ePwccmd$M$^>+TajT{)tve!Uf*)Sfu`@0rb+I~-FP4xW_s
zZmN{ub+Z4SL-`U<_SoJg(RPFPu{QexEgC)l%vaodM$!9k=N|izlggf+D?B)FSUYTE
z*t@^~gvj4r8etz3j=j5M{`>N}#hQ$-w_Z&<7=C%isk0#+&-Rzs7H-i=+F5z6R<x|n
qIXk%lR2#nR+i6~X>O4OK<08HW2?mB$^X^{XcqIKd6G)OJG711;I-)lK

literal 0
HcmV?d00001

-- 
2.52.0