[PATCH 0/4] btrfs-progs: check: fix and refactor load_quota_info()

[PATCH 0/4] btrfs-progs: check: fix and refactor load_quota_info()

[Qu Wenruo]

The btrfs-check code of qgroup verification is pretty old, and there is
a long existing bug from day 1 that causes incorrect initial search
condition.

The first patch is to fix that bug.

Then the second one to reduce the memory usage of qgroup_count
structure.

The third one is to refactor load_quota_info() to follow the modern
standard and practice.

Finally add a test case as a regression test.

Qu Wenruo (4):
  btrfs-progs: check: fix the inverted condition to load qgroups
  btrfs-progs: check: remove unused qgroup_count::key
  btrfs-progs: check: refactor load_quota_info()
  btrfs-progs: fsck-tests: add a new test case for qgroup tree check

 check/qgroup-verify.c                         | 155 +++++++++---------
 tests/fsck-tests/076-large-quota-tree/test.sh |  28 ++++
 2 files changed, 103 insertions(+), 80 deletions(-)
 create mode 100644 tests/fsck-tests/076-large-quota-tree/test.sh

--
2.55.0

[PATCH 1/4] btrfs-progs: check: fix the inverted condition to load qgroups

[Qu Wenruo]

[BUG]
When a qgroup tree is higher than level 0 and has a qgroup relation
between the first subvolume and a higher level qgroup, the btrfs check
can failed to load qgroup tree.

A minimal reproducer looks like the following:

  mkfs.btrfs -f -K -n 4k $dev > /dev/null
  mount $dev $mnt
  btrfs quota enable "$mnt"
  btrfs quota rescan -w $mnt
  for i in $(seq 1 32); do
          btrfs subvolume create "$mnt/s$i" >/dev/null
  done
  id=$(btrfs subvolume list "$mnt" | awk 'NR==1 {print $2}')
  btrfs qgroup create 1/1 "$mnt"
  btrfs qgroup assign "0/$id" 1/1 "$mnt"
  umount $mnt
  btrfs check -Q $dev

The failure looks like:

 Opening filesystem to check...
 Checking filesystem on /dev/test/scratch1
 UUID: fbe3bc62-168a-4fec-8ef5-ba5f92d8c22c
 Print quota groups report for /dev/test/scratch1
 UUID: fbe3bc62-168a-4fec-8ef5-ba5f92d8c22c
 ERROR: failed to add qgroup relation, member=256 parent=281474976710657: No such file or directory
 ERROR: loading qgroups from disk: -2
 extent buffer leak: start 30789632 len 4096
 extent buffer leak: start 30793728 len 4096

[CAUSE]
With extra debug output, the following one line shows the problem pretty
well:

 load_quota_info: search_relations=0 search_key=(246 0 0)

That's for the first loop of load_quota_info(), which should start from
the first leaf and load all qgroups into memory.

However the search key is not (0 0 0), it's the inverted condition
initializing the search key cause btrfs-check to grab the leaf with
qgroup relation items, not the first leaf.

Thus btrfs-check failed to load the qgroups in earlier leaves, causing
the above failure.

[FIX]
The code is not that well written, but as a hot fix just revert the
condition to fix the bug.

Issues: #1180
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 check/qgroup-verify.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/check/qgroup-verify.c b/check/qgroup-verify.c
index 68002ec2e2ae..7993cd22a213 100644
--- a/check/qgroup-verify.c
+++ b/check/qgroup-verify.c
@@ -953,7 +953,7 @@ loop:
 	 * items. The 2nd pass picks up relation items and glues them to their
 	 * respective count structures.
 	 */
-	key.objectid = search_relations ? 0 : BTRFS_QGROUP_RELATION_KEY;
+	key.objectid = search_relations ? BTRFS_QGROUP_RELATION_KEY : 0;
 	key.type = 0;
 	key.offset = 0;
 
-- 
2.55.0

[PATCH 2/4] btrfs-progs: check: remove unused qgroup_count::key

[Qu Wenruo]

That member is only set during insert, but never read again.
And it's against the common practice to use btrfs_key structure for
in-memory structures.

Just remove the member to save some space for qgroup_count::key.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 check/qgroup-verify.c | 2 --
 1 file changed, 2 deletions(-)

diff --git a/check/qgroup-verify.c b/check/qgroup-verify.c
index 7993cd22a213..433d89b47d3a 100644
--- a/check/qgroup-verify.c
+++ b/check/qgroup-verify.c
@@ -60,7 +60,6 @@ struct qgroup_count {
 	u64 qgroupid;
 	int subvol_exists;
 
-	struct btrfs_disk_key key;
 	struct qgroup_info diskinfo;
 
 	struct qgroup_info info;
@@ -863,7 +862,6 @@ static struct qgroup_count *alloc_count(struct btrfs_disk_key *key,
 
 	if (c) {
 		c->qgroupid = btrfs_disk_key_offset(key);
-		c->key = *key;
 
 		item = &c->diskinfo;
 		item->referenced = btrfs_qgroup_info_rfer(leaf, disk);
-- 
2.55.0

[PATCH 3/4] btrfs-progs: check: refactor load_quota_info()

[Qu Wenruo]

Modernize that function by:

- Use btrfs_key when possible
  The structure btrfs_disk_key is only for on-disk usage, every
  in-memory operation is based on btrfs_key.

  This includes the function alloc_count(), which now also accepts
  btrfs_key as a parameter.

- Enhance the error handling
  The path is not released when we hit an error.

- Use an dedicated helper to scan one leaf
  Instead of nested loops, which is bug-prone for continue/break calls.

- Remove the unnecessary double loop
  There is a local variable @search_relations, which has caused a long
  existing bug before.

  The idea is to skip all the QGROUP_LIMIT items, but we can skip them
  very quickly, and it's way better for one's mental health just to do a
  full tree iteration.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 check/qgroup-verify.c | 153 +++++++++++++++++++++---------------------
 1 file changed, 75 insertions(+), 78 deletions(-)

diff --git a/check/qgroup-verify.c b/check/qgroup-verify.c
index 433d89b47d3a..63902ffa6f5b 100644
--- a/check/qgroup-verify.c
+++ b/check/qgroup-verify.c
@@ -853,7 +853,7 @@ static struct qgroup_count *find_count(u64 qgroupid)
 	return NULL;
 }
 
-static struct qgroup_count *alloc_count(struct btrfs_disk_key *key,
+static struct qgroup_count *alloc_count(struct btrfs_key *key,
 					struct extent_buffer *leaf,
 					struct btrfs_qgroup_info_item *disk)
 {
@@ -861,7 +861,7 @@ static struct qgroup_count *alloc_count(struct btrfs_disk_key *key,
 	struct qgroup_info *item;
 
 	if (c) {
-		c->qgroupid = btrfs_disk_key_offset(key);
+		c->qgroupid = key->offset;
 
 		item = &c->diskinfo;
 		item->referenced = btrfs_qgroup_info_rfer(leaf, disk);
@@ -928,30 +928,80 @@ static void read_qgroup_status(struct btrfs_fs_info *info, struct extent_buffer
 	ct->scan_progress = btrfs_qgroup_status_rescan(eb, status_item);
 }
 
+static int load_one_quota_leaf(struct extent_buffer *leaf)
+{
+	struct btrfs_fs_info *fs_info = leaf->fs_info;
+	const u32 nr_items = btrfs_header_nritems(leaf);
+
+	for (int i = 0; i < nr_items; i++) {
+		struct qgroup_count *qc;
+		struct btrfs_qgroup_info_item *qii;
+		struct btrfs_key key;
+		struct btrfs_key root_key;
+		struct btrfs_root *subv_root;
+		int ret;
+
+		btrfs_item_key_to_cpu(leaf, &key, i);
+
+		if (key.type == BTRFS_QGROUP_RELATION_KEY) {
+			ret = add_qgroup_relation(key.objectid,
+						  key.offset);
+			if (ret) {
+				errno = -ret;
+				error(
+	"failed to add qgroup relation, member=%llu parent=%llu: %m",
+				      key.objectid, key.offset);
+				return ret;
+			}
+			continue;
+		}
+
+		if (key.type == BTRFS_QGROUP_STATUS_KEY) {
+			read_qgroup_status(fs_info, leaf, i, &counts);
+			continue;
+		}
+
+		/*
+		 * At this point, we can ignore anything that
+		 * isn't a qgroup info.
+		 */
+		if (key.type != BTRFS_QGROUP_INFO_KEY)
+			continue;
+
+		qii = btrfs_item_ptr(leaf, i, struct btrfs_qgroup_info_item);
+
+		qc = alloc_count(&key, leaf, qii);
+		if (!qc) {
+			ret = ENOMEM;
+			error_mem(NULL);
+			return ret;
+		}
+
+		root_key.objectid = key.offset;
+		root_key.type = BTRFS_ROOT_ITEM_KEY;
+		root_key.offset = (u64)-1;
+		subv_root = btrfs_read_fs_root_no_cache(fs_info, &root_key);
+		if (!IS_ERR(subv_root)) {
+			qc->subvol_exists = 1;
+			btrfs_free_fs_root(subv_root);
+		}
+	}
+	return 0;
+}
+
 static int load_quota_info(struct btrfs_fs_info *info)
 {
 	int ret;
 	struct btrfs_root *root = info->quota_root;
-	struct btrfs_root *tmproot;
 	struct btrfs_path path = { 0 };
 	struct btrfs_key key;
-	struct btrfs_key root_key;
-	struct btrfs_disk_key disk_key;
 	struct extent_buffer *leaf;
-	struct btrfs_qgroup_info_item *item;
-	struct qgroup_count *count;
-	int i, nr;
-	int search_relations = 0;
 
 	if (btrfs_fs_incompat(info, SIMPLE_QUOTA))
 		counts.simple = 1;
-loop:
-	/*
-	 * Do 2 passes, the first allocates group counts and reads status
-	 * items. The 2nd pass picks up relation items and glues them to their
-	 * respective count structures.
-	 */
-	key.objectid = search_relations ? BTRFS_QGROUP_RELATION_KEY : 0;
+
+	/* Go through all qgroup leaves, and load qgroups and relationship items. */
+	key.objectid = 0;
 	key.type = 0;
 	key.offset = 0;
 
@@ -964,72 +1014,19 @@ loop:
 	while (1) {
 		leaf = path.nodes[0];
 
-		nr = btrfs_header_nritems(leaf);
-		for(i = 0; i < nr; i++) {
-			btrfs_item_key(leaf, &disk_key, i);
-			btrfs_disk_key_to_cpu(&key, &disk_key);
-
-			if (search_relations) {
-				if (key.type == BTRFS_QGROUP_RELATION_KEY) {
-					ret = add_qgroup_relation(key.objectid,
-								  key.offset);
-					if (ret) {
-						errno = -ret;
-						error(
-		"failed to add qgroup relation, member=%llu parent=%llu: %m",
-						      key.objectid, key.offset);
-						goto out;
-					}
-				}
-				continue;
-			}
-
-			if (key.type == BTRFS_QGROUP_STATUS_KEY) {
-				read_qgroup_status(info, leaf, i, &counts);
-				continue;
-			}
-
-			/*
-			 * At this point, we can ignore anything that
-			 * isn't a qgroup info.
-			 */
-			if (key.type != BTRFS_QGROUP_INFO_KEY)
-				continue;
-
-			item = btrfs_item_ptr(leaf, i,
-					      struct btrfs_qgroup_info_item);
-
-			count = alloc_count(&disk_key, leaf, item);
-			if (!count) {
-				ret = ENOMEM;
-				error_mem(NULL);
-				goto out;
-			}
-
-			root_key.objectid = key.offset;
-			root_key.type = BTRFS_ROOT_ITEM_KEY;
-			root_key.offset = (u64)-1;
-			tmproot = btrfs_read_fs_root_no_cache(info, &root_key);
-			if (tmproot && !IS_ERR(tmproot)) {
-				count->subvol_exists = 1;
-				btrfs_free_fs_root(tmproot);
-			}
-		}
-
+		ret = load_one_quota_leaf(leaf);
+		if (ret < 0)
+			goto out;
 		ret = btrfs_next_leaf(root, &path);
-		if (ret != 0)
+		if (ret < 0)
+			goto out;
+		if (ret > 0) {
+			ret = 0;
 			break;
+		}
 	}
-
-	ret = 0;
-	btrfs_release_path(&path);
-
-	if (!search_relations) {
-		search_relations = 1;
-		goto loop;
-	}
-
 out:
+	btrfs_release_path(&path);
 	return ret;
 }
 
-- 
2.55.0

[PATCH 4/4] btrfs-progs: fsck-tests: add a new test case for qgroup tree check

[Qu Wenruo]

The workload is straight forward:

- Create a btrfs with qgroup full mode

- Create 512 subvolumes
  This should cause at least 2 leaves, even using 64K nodesize.

- Create qgroup 1/1 and assign 0/5 to it

- Run btrfs-check on the fs
  Unpatched progs will load the last leaf first, add the qgroup relation
  item without loading the qgroups in the previous leaf.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 tests/fsck-tests/076-large-quota-tree/test.sh | 28 +++++++++++++++++++
 1 file changed, 28 insertions(+)
 create mode 100644 tests/fsck-tests/076-large-quota-tree/test.sh

diff --git a/tests/fsck-tests/076-large-quota-tree/test.sh b/tests/fsck-tests/076-large-quota-tree/test.sh
new file mode 100644
index 000000000000..0697fa06795b
--- /dev/null
+++ b/tests/fsck-tests/076-large-quota-tree/test.sh
@@ -0,0 +1,28 @@
+#!/bin/bash
+#
+# Make sure "btrfs check" can properly handle a quota tree whose level
+# is larger than 0.
+
+source "$TEST_TOP/common" || exit
+
+check_prereq btrfs
+check_prereq mkfs.btrfs
+
+setup_root_helper
+prepare_test_dev
+
+run_check_mkfs_test_dev -O quota
+run_check_mount_test_dev
+# Create 512 subvolumes, which should cause at least 2 leaves even for 64K nodesize.
+for ((i = 0; i < 512; i++)); do
+	run_check $SUDO_HELPER "$TOP/btrfs" subvolume create "$TEST_MNT/subv_$i"
+done
+
+# Create qgroup 1/1 and add 0/5 to it, which should cause unpatched
+# btrfs-check to only load the last leaf for relation items, without
+# loading the involved qgroups.
+run_check $SUDO_HELPER "$TOP/btrfs" qgroup create 1/1 "$TEST_MNT"
+run_check $SUDO_HELPER "$TOP/btrfs" qgroup assign 0/5 1/1 "$TEST_MNT"
+run_check_umount_test_dev
+
+run_check $SUDO_HELPER "$TOP/btrfs" check "$TEST_DEV"
-- 
2.55.0