[PATCH 01/13] btrfs: update btrfs_insert_inode_defrag to to use rb helper

[PATCH 01/13] btrfs: update btrfs_insert_inode_defrag to to use rb helper

[Yangtao Li]

Update btrfs_insert_inode_defrag() to use rb_find_add().

Suggested-by: David Sterba <dsterba@suse.com>
Signed-off-by: Yangtao Li <frank.li@vivo.com>
---
 fs/btrfs/defrag.c | 52 +++++++++++++++++++++++------------------------
 1 file changed, 25 insertions(+), 27 deletions(-)

diff --git a/fs/btrfs/defrag.c b/fs/btrfs/defrag.c
index d4310d93f532..d908bce0b8a1 100644
--- a/fs/btrfs/defrag.c
+++ b/fs/btrfs/defrag.c
@@ -60,6 +60,16 @@ static int compare_inode_defrag(const struct inode_defrag *defrag1,
 		return 0;
 }
 
+static int inode_defrag_cmp(struct rb_node *new, const struct rb_node *exist)
+{
+	const struct inode_defrag *new_defrag =
+		rb_entry(new, struct inode_defrag, rb_node);
+	const struct inode_defrag *exist_defrag =
+		rb_entry(exist, struct inode_defrag, rb_node);
+
+	return compare_inode_defrag(new_defrag, exist_defrag);
+}
+
 /*
  * Insert a record for an inode into the defrag tree.  The lock must be held
  * already.
@@ -71,37 +81,25 @@ static int btrfs_insert_inode_defrag(struct btrfs_inode *inode,
 				     struct inode_defrag *defrag)
 {
 	struct btrfs_fs_info *fs_info = inode->root->fs_info;
-	struct inode_defrag *entry;
-	struct rb_node **p;
-	struct rb_node *parent = NULL;
-	int ret;
+	struct rb_node *exist;
 
-	p = &fs_info->defrag_inodes.rb_node;
-	while (*p) {
-		parent = *p;
-		entry = rb_entry(parent, struct inode_defrag, rb_node);
+	exist = rb_find_add(&defrag->rb_node, &fs_info->defrag_inodes, inode_defrag_cmp);
+	if (exist) {
+		struct inode_defrag *entry;
 
-		ret = compare_inode_defrag(defrag, entry);
-		if (ret < 0)
-			p = &parent->rb_left;
-		else if (ret > 0)
-			p = &parent->rb_right;
-		else {
-			/*
-			 * If we're reinserting an entry for an old defrag run,
-			 * make sure to lower the transid of our existing
-			 * record.
-			 */
-			if (defrag->transid < entry->transid)
-				entry->transid = defrag->transid;
-			entry->extent_thresh = min(defrag->extent_thresh,
-						   entry->extent_thresh);
-			return -EEXIST;
-		}
+		entry = rb_entry(exist, struct inode_defrag, rb_node);
+		/*
+		 * If we're reinserting an entry for an old defrag run,
+		 * make sure to lower the transid of our existing
+		 * record.
+		 */
+		if (defrag->transid < entry->transid)
+			entry->transid = defrag->transid;
+		entry->extent_thresh = min(defrag->extent_thresh,
+					   entry->extent_thresh);
+		return -EEXIST;
 	}
 	set_bit(BTRFS_INODE_IN_DEFRAG, &inode->runtime_flags);
-	rb_link_node(&defrag->rb_node, parent, p);
-	rb_insert_color(&defrag->rb_node, &fs_info->defrag_inodes);
 	return 0;
 }
 
-- 
2.39.0

[PATCH 02/13] btrfs: update __btrfs_lookup_delayed_item to to use rb helper

[Yangtao Li]

Update __btrfs_lookup_delayed_item() to use rb_find().

Suggested-by: David Sterba <dsterba@suse.com>
Signed-off-by: Yangtao Li <frank.li@vivo.com>
---
 fs/btrfs/delayed-inode.c | 39 ++++++++++++++++++---------------------
 1 file changed, 18 insertions(+), 21 deletions(-)

diff --git a/fs/btrfs/delayed-inode.c b/fs/btrfs/delayed-inode.c
index 3f1551d8a5c6..dbc1bc1cdf20 100644
--- a/fs/btrfs/delayed-inode.c
+++ b/fs/btrfs/delayed-inode.c
@@ -336,6 +336,20 @@ static struct btrfs_delayed_item *btrfs_alloc_delayed_item(u16 data_len,
 	return item;
 }
 
+static int btrfs_delayed_item_key_cmp(const void *k, const struct rb_node *node)
+{
+	const u64 *index = k;
+	const struct btrfs_delayed_item *delayed_item =
+		rb_entry(node, struct btrfs_delayed_item, rb_node);
+
+	if (delayed_item->index < *index)
+		return 1;
+	else if (delayed_item->index > *index)
+		return -1;
+
+	return 0;
+}
+
 /*
  * Look up the delayed item by key.
  *
@@ -349,21 +363,10 @@ static struct btrfs_delayed_item *__btrfs_lookup_delayed_item(
 				struct rb_root *root,
 				u64 index)
 {
-	struct rb_node *node = root->rb_node;
-	struct btrfs_delayed_item *delayed_item = NULL;
-
-	while (node) {
-		delayed_item = rb_entry(node, struct btrfs_delayed_item,
-					rb_node);
-		if (delayed_item->index < index)
-			node = node->rb_right;
-		else if (delayed_item->index > index)
-			node = node->rb_left;
-		else
-			return delayed_item;
-	}
+	struct rb_node *node;
 
-	return NULL;
+	node = rb_find(&index, root, btrfs_delayed_item_key_cmp);
+	return rb_entry_safe(node, struct btrfs_delayed_item, rb_node);
 }
 
 static int btrfs_delayed_item_cmp(const struct rb_node *new,
@@ -371,14 +374,8 @@ static int btrfs_delayed_item_cmp(const struct rb_node *new,
 {
 	const struct btrfs_delayed_item *new_item =
 		rb_entry(new, struct btrfs_delayed_item, rb_node);
-	const struct btrfs_delayed_item *exist_item =
-		rb_entry(exist, struct btrfs_delayed_item, rb_node);
 
-	if (new_item->index < exist_item->index)
-		return -1;
-	if (new_item->index > exist_item->index)
-		return 1;
-	return 0;
+	return btrfs_delayed_item_key_cmp(&new_item->index, exist);
 }
 
 static int __btrfs_add_delayed_item(struct btrfs_delayed_node *delayed_node,
-- 
2.39.0

Re: [PATCH 02/13] btrfs: update __btrfs_lookup_delayed_item to to use rb helper

[David Sterba]

On Tue, Apr 22, 2025 at 02:14:53AM -0600, Yangtao Li wrote:
> Update __btrfs_lookup_delayed_item() to use rb_find().
> 
> Suggested-by: David Sterba <dsterba@suse.com>
> Signed-off-by: Yangtao Li <frank.li@vivo.com>
> ---
>  fs/btrfs/delayed-inode.c | 39 ++++++++++++++++++---------------------
>  1 file changed, 18 insertions(+), 21 deletions(-)
> 
> diff --git a/fs/btrfs/delayed-inode.c b/fs/btrfs/delayed-inode.c
> index 3f1551d8a5c6..dbc1bc1cdf20 100644
> --- a/fs/btrfs/delayed-inode.c
> +++ b/fs/btrfs/delayed-inode.c
> @@ -336,6 +336,20 @@ static struct btrfs_delayed_item *btrfs_alloc_delayed_item(u16 data_len,
>  	return item;
>  }
>  
> +static int btrfs_delayed_item_key_cmp(const void *k, const struct rb_node *node)

Please don't use single letter variables, here you can use 'key'

The function name should be something like 'delayed_item_index_cmp' so
it's clear what object and what its member it compares. This applies to
other patches too.

> +{
> +	const u64 *index = k;
> +	const struct btrfs_delayed_item *delayed_item =
> +		rb_entry(node, struct btrfs_delayed_item, rb_node);
> +
> +	if (delayed_item->index < *index)
> +		return 1;
> +	else if (delayed_item->index > *index)
> +		return -1;
> +
> +	return 0;
> +}
> +
>  /*
>   * Look up the delayed item by key.
>   *

[PATCH 03/13] btrfs: update ulist_rbtree_search to to use rb helper

[Yangtao Li]

Update ulist_rbtree_search() to use rb_find().

Suggested-by: David Sterba <dsterba@suse.com>
Signed-off-by: Yangtao Li <frank.li@vivo.com>
---
 fs/btrfs/ulist.c | 30 +++++++++++++++++-------------
 1 file changed, 17 insertions(+), 13 deletions(-)

diff --git a/fs/btrfs/ulist.c b/fs/btrfs/ulist.c
index fc59b57257d6..9cdf0b47772c 100644
--- a/fs/btrfs/ulist.c
+++ b/fs/btrfs/ulist.c
@@ -129,21 +129,25 @@ void ulist_free(struct ulist *ulist)
 	kfree(ulist);
 }
 
+static int ulist_node_key_cmp(const void *k, const struct rb_node *node)
+{
+	const u64 *val = k;
+	const struct ulist_node *u = rb_entry(node, struct ulist_node, rb_node);
+
+	if (u->val < *val)
+		return 1;
+	else if (u->val > *val)
+		return -1;
+
+	return 0;
+}
+
 static struct ulist_node *ulist_rbtree_search(struct ulist *ulist, u64 val)
 {
-	struct rb_node *n = ulist->root.rb_node;
-	struct ulist_node *u = NULL;
-
-	while (n) {
-		u = rb_entry(n, struct ulist_node, rb_node);
-		if (u->val < val)
-			n = n->rb_right;
-		else if (u->val > val)
-			n = n->rb_left;
-		else
-			return u;
-	}
-	return NULL;
+	struct rb_node *node;
+
+	node = rb_find(&val, &ulist->root, ulist_node_key_cmp);
+	return rb_entry_safe(node, struct ulist_node, rb_node);
 }
 
 static void ulist_rbtree_erase(struct ulist *ulist, struct ulist_node *node)
-- 
2.39.0

[PATCH 04/13] btrfs: update ulist_rbtree_insert to to use rb helper

[Yangtao Li]

Update ulist_rbtree_insert() to use rb_find_add().

Suggested-by: David Sterba <dsterba@suse.com>
Signed-off-by: Yangtao Li <frank.li@vivo.com>
---
 fs/btrfs/ulist.c | 30 +++++++++++++-----------------
 1 file changed, 13 insertions(+), 17 deletions(-)

diff --git a/fs/btrfs/ulist.c b/fs/btrfs/ulist.c
index 9cdf0b47772c..cef652986c67 100644
--- a/fs/btrfs/ulist.c
+++ b/fs/btrfs/ulist.c
@@ -159,25 +159,21 @@ static void ulist_rbtree_erase(struct ulist *ulist, struct ulist_node *node)
 	ulist->nnodes--;
 }
 
+static int ulist_node_cmp(struct rb_node *new, const struct rb_node *exist)
+{
+	const struct ulist_node *u = rb_entry(new, struct ulist_node, rb_node);
+
+	return ulist_node_key_cmp(&u->val, exist);
+}
+
+
 static int ulist_rbtree_insert(struct ulist *ulist, struct ulist_node *ins)
 {
-	struct rb_node **p = &ulist->root.rb_node;
-	struct rb_node *parent = NULL;
-	struct ulist_node *cur = NULL;
-
-	while (*p) {
-		parent = *p;
-		cur = rb_entry(parent, struct ulist_node, rb_node);
-
-		if (cur->val < ins->val)
-			p = &(*p)->rb_right;
-		else if (cur->val > ins->val)
-			p = &(*p)->rb_left;
-		else
-			return -EEXIST;
-	}
-	rb_link_node(&ins->rb_node, parent, p);
-	rb_insert_color(&ins->rb_node, &ulist->root);
+	struct rb_node *exist;
+
+	exist = rb_find_add(&ins->rb_node, &ulist->root, ulist_node_cmp);
+	if (exist)
+		return -EEXIST;
 	return 0;
 }
 
-- 
2.39.0

[PATCH 05/13] btrfs: update lookup_block_entry to to use rb helper

[Yangtao Li]

Update lookup_block_entry() to use rb_find().

Suggested-by: David Sterba <dsterba@suse.com>
Signed-off-by: Yangtao Li <frank.li@vivo.com>
---
 fs/btrfs/ref-verify.c | 30 +++++++++++++++++-------------
 1 file changed, 17 insertions(+), 13 deletions(-)

diff --git a/fs/btrfs/ref-verify.c b/fs/btrfs/ref-verify.c
index 2928abf7eb82..6445c7d9a7b1 100644
--- a/fs/btrfs/ref-verify.c
+++ b/fs/btrfs/ref-verify.c
@@ -75,6 +75,20 @@ struct block_entry {
 	struct list_head actions;
 };
 
+static int block_entry_key_cmp(const void *k, const struct rb_node *node)
+{
+	const u64 *bytenr = k;
+	const struct block_entry *entry =
+		rb_entry(node, struct block_entry, node);
+
+	if (entry->bytenr < *bytenr)
+		return 1;
+	else if (entry->bytenr > *bytenr)
+		return -1;
+
+	return 0;
+}
+
 static struct block_entry *insert_block_entry(struct rb_root *root,
 					      struct block_entry *be)
 {
@@ -100,20 +114,10 @@ static struct block_entry *insert_block_entry(struct rb_root *root,
 
 static struct block_entry *lookup_block_entry(struct rb_root *root, u64 bytenr)
 {
-	struct rb_node *n;
-	struct block_entry *entry = NULL;
+	struct rb_node *node;
 
-	n = root->rb_node;
-	while (n) {
-		entry = rb_entry(n, struct block_entry, node);
-		if (entry->bytenr < bytenr)
-			n = n->rb_right;
-		else if (entry->bytenr > bytenr)
-			n = n->rb_left;
-		else
-			return entry;
-	}
-	return NULL;
+	node = rb_find(&bytenr, root, block_entry_key_cmp);
+	return rb_entry_safe(node, struct block_entry, node);
 }
 
 static struct root_entry *insert_root_entry(struct rb_root *root,
-- 
2.39.0

[PATCH 06/13] btrfs: update insert_block_entry to to use rb helper

[Yangtao Li]

Update insert_block_entry() to use rb_find_add().

Suggested-by: David Sterba <dsterba@suse.com>
Signed-off-by: Yangtao Li <frank.li@vivo.com>
---
 fs/btrfs/ref-verify.c | 28 +++++++++++-----------------
 1 file changed, 11 insertions(+), 17 deletions(-)

diff --git a/fs/btrfs/ref-verify.c b/fs/btrfs/ref-verify.c
index 6445c7d9a7b1..6113f325df82 100644
--- a/fs/btrfs/ref-verify.c
+++ b/fs/btrfs/ref-verify.c
@@ -89,27 +89,21 @@ static int block_entry_key_cmp(const void *k, const struct rb_node *node)
 	return 0;
 }
 
+static int block_entry_cmp(struct rb_node *new, const struct rb_node *exist)
+{
+	const struct block_entry *new_entry =
+		rb_entry(new, struct block_entry, node);
+
+	return block_entry_key_cmp(&new_entry->bytenr, exist);
+}
+
 static struct block_entry *insert_block_entry(struct rb_root *root,
 					      struct block_entry *be)
 {
-	struct rb_node **p = &root->rb_node;
-	struct rb_node *parent_node = NULL;
-	struct block_entry *entry;
+	struct rb_node *exist;
 
-	while (*p) {
-		parent_node = *p;
-		entry = rb_entry(parent_node, struct block_entry, node);
-		if (entry->bytenr > be->bytenr)
-			p = &(*p)->rb_left;
-		else if (entry->bytenr < be->bytenr)
-			p = &(*p)->rb_right;
-		else
-			return entry;
-	}
-
-	rb_link_node(&be->node, parent_node, p);
-	rb_insert_color(&be->node, root);
-	return NULL;
+	exist = rb_find_add(&be->node, root, block_entry_cmp);
+	return rb_entry_safe(exist, struct block_entry, node);
 }
 
 static struct block_entry *lookup_block_entry(struct rb_root *root, u64 bytenr)
-- 
2.39.0

[PATCH 07/13] btrfs: update lookup_root_entry to to use rb helper

[Yangtao Li]

Update lookup_root_entry() to use rb_find().

Suggested-by: David Sterba <dsterba@suse.com>
Signed-off-by: Yangtao Li <frank.li@vivo.com>
---
 fs/btrfs/ref-verify.c | 30 +++++++++++++++++-------------
 1 file changed, 17 insertions(+), 13 deletions(-)

diff --git a/fs/btrfs/ref-verify.c b/fs/btrfs/ref-verify.c
index 6113f325df82..67e999262137 100644
--- a/fs/btrfs/ref-verify.c
+++ b/fs/btrfs/ref-verify.c
@@ -114,6 +114,20 @@ static struct block_entry *lookup_block_entry(struct rb_root *root, u64 bytenr)
 	return rb_entry_safe(node, struct block_entry, node);
 }
 
+static int root_entry_key_cmp(const void *k, const struct rb_node *node)
+{
+	const u64 *objectid = k;
+	const struct root_entry *entry =
+		rb_entry(node, struct root_entry, node);
+
+	if (entry->root_objectid < *objectid)
+		return 1;
+	else if (entry->root_objectid > *objectid)
+		return -1;
+
+	return 0;
+}
+
 static struct root_entry *insert_root_entry(struct rb_root *root,
 					    struct root_entry *re)
 {
@@ -187,20 +201,10 @@ static struct ref_entry *insert_ref_entry(struct rb_root *root,
 
 static struct root_entry *lookup_root_entry(struct rb_root *root, u64 objectid)
 {
-	struct rb_node *n;
-	struct root_entry *entry = NULL;
+	struct rb_node *node;
 
-	n = root->rb_node;
-	while (n) {
-		entry = rb_entry(n, struct root_entry, node);
-		if (entry->root_objectid < objectid)
-			n = n->rb_right;
-		else if (entry->root_objectid > objectid)
-			n = n->rb_left;
-		else
-			return entry;
-	}
-	return NULL;
+	node = rb_find(&objectid, root, root_entry_key_cmp);
+	return rb_entry_safe(node, struct root_entry, node);
 }
 
 #ifdef CONFIG_STACKTRACE
-- 
2.39.0

[PATCH 08/13] btrfs: update insert_root_entry to to use rb helper

[Yangtao Li]

Update insert_root_entry() to use rb_find_add().

Suggested-by: David Sterba <dsterba@suse.com>
Signed-off-by: Yangtao Li <frank.li@vivo.com>
---
 fs/btrfs/ref-verify.c | 28 ++++++++++------------------
 1 file changed, 10 insertions(+), 18 deletions(-)

diff --git a/fs/btrfs/ref-verify.c b/fs/btrfs/ref-verify.c
index 67e999262137..140b036b5c80 100644
--- a/fs/btrfs/ref-verify.c
+++ b/fs/btrfs/ref-verify.c
@@ -128,28 +128,20 @@ static int root_entry_key_cmp(const void *k, const struct rb_node *node)
 	return 0;
 }
 
-static struct root_entry *insert_root_entry(struct rb_root *root,
-					    struct root_entry *re)
+static int root_entry_cmp(struct rb_node *new, const struct rb_node *exist)
 {
-	struct rb_node **p = &root->rb_node;
-	struct rb_node *parent_node = NULL;
-	struct root_entry *entry;
+	const struct root_entry *new_entry = rb_entry(new, struct root_entry, node);
 
-	while (*p) {
-		parent_node = *p;
-		entry = rb_entry(parent_node, struct root_entry, node);
-		if (entry->root_objectid > re->root_objectid)
-			p = &(*p)->rb_left;
-		else if (entry->root_objectid < re->root_objectid)
-			p = &(*p)->rb_right;
-		else
-			return entry;
-	}
+	return root_entry_key_cmp(&new_entry->root_objectid, exist);
+}
 
-	rb_link_node(&re->node, parent_node, p);
-	rb_insert_color(&re->node, root);
-	return NULL;
+static struct root_entry *insert_root_entry(struct rb_root *root,
+					    struct root_entry *re)
+{
+	struct rb_node *exist;
 
+	exist = rb_find_add(&re->node, root, root_entry_cmp);
+	return rb_entry_safe(exist, struct root_entry, node);
 }
 
 static int comp_refs(struct ref_entry *ref1, struct ref_entry *ref2)
-- 
2.39.0

[PATCH 09/13] btrfs: update insert_ref_entry to to use rb helper

[Yangtao Li]

Update insert_ref_entry() to use rb_find_add().

Suggested-by: David Sterba <dsterba@suse.com>
Signed-off-by: Yangtao Li <frank.li@vivo.com>
---
 fs/btrfs/ref-verify.c | 31 +++++++++++--------------------
 1 file changed, 11 insertions(+), 20 deletions(-)

diff --git a/fs/btrfs/ref-verify.c b/fs/btrfs/ref-verify.c
index 140b036b5c80..1de15586ecc2 100644
--- a/fs/btrfs/ref-verify.c
+++ b/fs/btrfs/ref-verify.c
@@ -165,30 +165,21 @@ static int comp_refs(struct ref_entry *ref1, struct ref_entry *ref2)
 	return 0;
 }
 
+static int ref_entry_cmp(struct rb_node *new, const struct rb_node *exist)
+{
+	struct ref_entry *new_entry = rb_entry(new, struct ref_entry, node);
+	struct ref_entry *exist_entry = rb_entry(exist, struct ref_entry, node);
+
+	return comp_refs(new_entry, exist_entry);
+}
+
 static struct ref_entry *insert_ref_entry(struct rb_root *root,
 					  struct ref_entry *ref)
 {
-	struct rb_node **p = &root->rb_node;
-	struct rb_node *parent_node = NULL;
-	struct ref_entry *entry;
-	int cmp;
-
-	while (*p) {
-		parent_node = *p;
-		entry = rb_entry(parent_node, struct ref_entry, node);
-		cmp = comp_refs(entry, ref);
-		if (cmp > 0)
-			p = &(*p)->rb_left;
-		else if (cmp < 0)
-			p = &(*p)->rb_right;
-		else
-			return entry;
-	}
-
-	rb_link_node(&ref->node, parent_node, p);
-	rb_insert_color(&ref->node, root);
-	return NULL;
+	struct rb_node *exist;
 
+	exist = rb_find_add(&ref->node, root, ref_entry_cmp);
+	return rb_entry_safe(exist, struct ref_entry, node);
 }
 
 static struct root_entry *lookup_root_entry(struct rb_root *root, u64 objectid)
-- 
2.39.0

[PATCH 10/13] btrfs: update find_qgroup_rb to to use rb helper

[Yangtao Li]

Update find_qgroup_rb() to use rb_find().

Suggested-by: David Sterba <dsterba@suse.com>
Signed-off-by: Yangtao Li <frank.li@vivo.com>
---
 fs/btrfs/qgroup.c | 28 ++++++++++++++++------------
 1 file changed, 16 insertions(+), 12 deletions(-)

diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index d6fa36674270..7325dbb16e38 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -160,23 +160,27 @@ qgroup_rescan_init(struct btrfs_fs_info *fs_info, u64 progress_objectid,
 		   int init_flags);
 static void qgroup_rescan_zero_tracking(struct btrfs_fs_info *fs_info);
 
+static int btrfs_qgroup_key_cmp(const void *k, const struct rb_node *node)
+{
+	const u64 *qgroupid = k;
+	const struct btrfs_qgroup *qgroup = rb_entry(node, struct btrfs_qgroup, node);
+
+	if (qgroup->qgroupid < *qgroupid)
+		return -1;
+	else if (qgroup->qgroupid > *qgroupid)
+		return 1;
+
+	return 0;
+}
+
 /* must be called with qgroup_ioctl_lock held */
 static struct btrfs_qgroup *find_qgroup_rb(const struct btrfs_fs_info *fs_info,
 					   u64 qgroupid)
 {
-	struct rb_node *n = fs_info->qgroup_tree.rb_node;
-	struct btrfs_qgroup *qgroup;
+	struct rb_node *node;
 
-	while (n) {
-		qgroup = rb_entry(n, struct btrfs_qgroup, node);
-		if (qgroup->qgroupid < qgroupid)
-			n = n->rb_left;
-		else if (qgroup->qgroupid > qgroupid)
-			n = n->rb_right;
-		else
-			return qgroup;
-	}
-	return NULL;
+	node = rb_find(&qgroupid, &fs_info->qgroup_tree, btrfs_qgroup_key_cmp);
+	return rb_entry_safe(node, struct btrfs_qgroup, node);
 }
 
 /*
-- 
2.39.0

[PATCH 11/13] btrfs: update add_qgroup_rb to to use rb helper

[Yangtao Li]

Update add_qgroup_rb() to use rb_find_add().

Suggested-by: David Sterba <dsterba@suse.com>
Signed-off-by: Yangtao Li <frank.li@vivo.com>
---
 fs/btrfs/qgroup.c | 46 ++++++++++++++++++++--------------------------
 1 file changed, 20 insertions(+), 26 deletions(-)

diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index 7325dbb16e38..989386311834 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -183,6 +183,14 @@ static struct btrfs_qgroup *find_qgroup_rb(const struct btrfs_fs_info *fs_info,
 	return rb_entry_safe(node, struct btrfs_qgroup, node);
 }
 
+static int btrfs_qgroup_cmp(struct rb_node *new, const struct rb_node *exist)
+{
+	const struct btrfs_qgroup *new_qgroup =
+		rb_entry(new, struct btrfs_qgroup, node);
+
+	return btrfs_qgroup_key_cmp(&new_qgroup->qgroupid, exist);
+}
+
 /*
  * Add qgroup to the filesystem's qgroup tree.
  *
@@ -195,39 +203,25 @@ static struct btrfs_qgroup *add_qgroup_rb(struct btrfs_fs_info *fs_info,
 					  struct btrfs_qgroup *prealloc,
 					  u64 qgroupid)
 {
-	struct rb_node **p = &fs_info->qgroup_tree.rb_node;
-	struct rb_node *parent = NULL;
-	struct btrfs_qgroup *qgroup;
+	struct rb_node *exist;
 
 	/* Caller must have pre-allocated @prealloc. */
 	ASSERT(prealloc);
 
-	while (*p) {
-		parent = *p;
-		qgroup = rb_entry(parent, struct btrfs_qgroup, node);
-
-		if (qgroup->qgroupid < qgroupid) {
-			p = &(*p)->rb_left;
-		} else if (qgroup->qgroupid > qgroupid) {
-			p = &(*p)->rb_right;
-		} else {
-			kfree(prealloc);
-			return qgroup;
-		}
+	prealloc->qgroupid = qgroupid;
+	exist = rb_find_add(&prealloc->node, &fs_info->qgroup_tree, btrfs_qgroup_cmp);
+	if (exist) {
+		kfree(prealloc);
+		return rb_entry(exist, struct btrfs_qgroup, node);
 	}
 
-	qgroup = prealloc;
-	qgroup->qgroupid = qgroupid;
-	INIT_LIST_HEAD(&qgroup->groups);
-	INIT_LIST_HEAD(&qgroup->members);
-	INIT_LIST_HEAD(&qgroup->dirty);
-	INIT_LIST_HEAD(&qgroup->iterator);
-	INIT_LIST_HEAD(&qgroup->nested_iterator);
-
-	rb_link_node(&qgroup->node, parent, p);
-	rb_insert_color(&qgroup->node, &fs_info->qgroup_tree);
+	INIT_LIST_HEAD(&prealloc->groups);
+	INIT_LIST_HEAD(&prealloc->members);
+	INIT_LIST_HEAD(&prealloc->dirty);
+	INIT_LIST_HEAD(&prealloc->iterator);
+	INIT_LIST_HEAD(&prealloc->nested_iterator);
 
-	return qgroup;
+	return prealloc;
 }
 
 static void __del_qgroup_rb(struct btrfs_qgroup *qgroup)
-- 
2.39.0

[PATCH 12/13] btrfs: update btrfs_qgroup_trace_subtree_after_cow to to use rb helper

[Yangtao Li]

Update btrfs_qgroup_trace_subtree_after_cow() to use rb_find().

Suggested-by: David Sterba <dsterba@suse.com>
Signed-off-by: Yangtao Li <frank.li@vivo.com>
---
 fs/btrfs/qgroup.c | 34 +++++++++++++++++++---------------
 1 file changed, 19 insertions(+), 15 deletions(-)

diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index 989386311834..5b862470fd67 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -4670,6 +4670,20 @@ void btrfs_qgroup_clean_swapped_blocks(struct btrfs_root *root)
 	spin_unlock(&swapped_blocks->lock);
 }
 
+static int btrfs_qgroup_swapped_block_key_cmp(const void *k, const struct rb_node *node)
+{
+	const u64 *bytenr = k;
+	const struct btrfs_qgroup_swapped_block *block =
+		rb_entry(node, struct btrfs_qgroup_swapped_block, node);
+
+	if (block->subvol_bytenr < *bytenr)
+		return -1;
+	else if (block->subvol_bytenr > *bytenr)
+		return 1;
+
+	return 0;
+}
+
 /*
  * Add subtree roots record into @subvol_root.
  *
@@ -4798,7 +4812,6 @@ int btrfs_qgroup_trace_subtree_after_cow(struct btrfs_trans_handle *trans,
 	struct btrfs_qgroup_swapped_block *block;
 	struct extent_buffer *reloc_eb = NULL;
 	struct rb_node *node;
-	bool found = false;
 	bool swapped = false;
 	int level = btrfs_header_level(subvol_eb);
 	int ret = 0;
@@ -4814,23 +4827,14 @@ int btrfs_qgroup_trace_subtree_after_cow(struct btrfs_trans_handle *trans,
 		spin_unlock(&blocks->lock);
 		return 0;
 	}
-	node = blocks->blocks[level].rb_node;
-
-	while (node) {
-		block = rb_entry(node, struct btrfs_qgroup_swapped_block, node);
-		if (block->subvol_bytenr < subvol_eb->start) {
-			node = node->rb_left;
-		} else if (block->subvol_bytenr > subvol_eb->start) {
-			node = node->rb_right;
-		} else {
-			found = true;
-			break;
-		}
-	}
-	if (!found) {
+	node = rb_find(&subvol_eb->start, &blocks->blocks[level],
+			btrfs_qgroup_swapped_block_key_cmp);
+	if (!node) {
 		spin_unlock(&blocks->lock);
 		goto out;
 	}
+	block = rb_entry(node, struct btrfs_qgroup_swapped_block, node);
+
 	/* Found one, remove it from @blocks first and update blocks->swapped */
 	rb_erase(&block->node, &blocks->blocks[level]);
 	for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
-- 
2.39.0

[PATCH 13/13] btrfs: update btrfs_qgroup_add_swapped_blocks to to use rb helper

[Yangtao Li]

Update btrfs_qgroup_add_swapped_blocks() to use rb_find_add().

Suggested-by: David Sterba <dsterba@suse.com>
Signed-off-by: Yangtao Li <frank.li@vivo.com>
---
 fs/btrfs/qgroup.c | 60 +++++++++++++++++++++++------------------------
 1 file changed, 29 insertions(+), 31 deletions(-)

diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index 5b862470fd67..669c3160573a 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -4684,6 +4684,14 @@ static int btrfs_qgroup_swapped_block_key_cmp(const void *k, const struct rb_nod
 	return 0;
 }
 
+static int btrfs_qgroup_swapped_block_cmp(struct rb_node *new, const struct rb_node *exist)
+{
+	const struct btrfs_qgroup_swapped_block *new_block =
+		rb_entry(new, struct btrfs_qgroup_swapped_block, node);
+
+	return btrfs_qgroup_swapped_block_key_cmp(&new_block->subvol_bytenr, exist);
+}
+
 /*
  * Add subtree roots record into @subvol_root.
  *
@@ -4703,8 +4711,7 @@ int btrfs_qgroup_add_swapped_blocks(struct btrfs_root *subvol_root,
 	struct btrfs_fs_info *fs_info = subvol_root->fs_info;
 	struct btrfs_qgroup_swapped_blocks *blocks = &subvol_root->swapped_blocks;
 	struct btrfs_qgroup_swapped_block *block;
-	struct rb_node **cur;
-	struct rb_node *parent = NULL;
+	struct rb_node *exist;
 	int level = btrfs_header_level(subvol_parent) - 1;
 	int ret = 0;
 
@@ -4753,40 +4760,31 @@ int btrfs_qgroup_add_swapped_blocks(struct btrfs_root *subvol_root,
 
 	/* Insert @block into @blocks */
 	spin_lock(&blocks->lock);
-	cur = &blocks->blocks[level].rb_node;
-	while (*cur) {
+	exist = rb_find_add(&block->node, &blocks->blocks[level],
+				btrfs_qgroup_swapped_block_cmp);
+	if (exist) {
 		struct btrfs_qgroup_swapped_block *entry;
 
-		parent = *cur;
-		entry = rb_entry(parent, struct btrfs_qgroup_swapped_block,
+		entry = rb_entry(exist, struct btrfs_qgroup_swapped_block,
 				 node);
-
-		if (entry->subvol_bytenr < block->subvol_bytenr) {
-			cur = &(*cur)->rb_left;
-		} else if (entry->subvol_bytenr > block->subvol_bytenr) {
-			cur = &(*cur)->rb_right;
-		} else {
-			if (entry->subvol_generation !=
-					block->subvol_generation ||
-			    entry->reloc_bytenr != block->reloc_bytenr ||
-			    entry->reloc_generation !=
-					block->reloc_generation) {
-				/*
-				 * Duplicated but mismatch entry found.
-				 * Shouldn't happen.
-				 *
-				 * Marking qgroup inconsistent should be enough
-				 * for end users.
-				 */
-				WARN_ON(IS_ENABLED(CONFIG_BTRFS_DEBUG));
-				ret = -EEXIST;
-			}
-			kfree(block);
-			goto out_unlock;
+		if (entry->subvol_generation !=
+				block->subvol_generation ||
+		    entry->reloc_bytenr != block->reloc_bytenr ||
+		    entry->reloc_generation !=
+				block->reloc_generation) {
+			/*
+			 * Duplicated but mismatch entry found.
+			 * Shouldn't happen.
+			 *
+			 * Marking qgroup inconsistent should be enough
+			 * for end users.
+			 */
+			WARN_ON(IS_ENABLED(CONFIG_BTRFS_DEBUG));
+			ret = -EEXIST;
 		}
+		kfree(block);
+		goto out_unlock;
 	}
-	rb_link_node(&block->node, parent, cur);
-	rb_insert_color(&block->node, &blocks->blocks[level]);
 	blocks->swapped = true;
 out_unlock:
 	spin_unlock(&blocks->lock);
-- 
2.39.0

Re: [PATCH 01/13] btrfs: update btrfs_insert_inode_defrag to to use rb helper

[David Sterba]

Please post the series with a cover letter so comments that apply to the
whole series can be posted there.

The series looks good, tests are running OK so far, I have mostly coding
style comments.

- rephrase the subject line to

"btrfs: use rb_find_add() in btrfs_insert_inode_defrag(I)

here mentioning the rb helper also suggests what the patch does and is
obvious so it does not need a long description.

On Tue, Apr 22, 2025 at 02:14:52AM -0600, Yangtao Li wrote:
> Update btrfs_insert_inode_defrag() to use rb_find_add().

The following text can be used in most patches (adjusted accordingly)

"Use the rb-tree helper so we don't open code the search and insert
code."
> 
> Suggested-by: David Sterba <dsterba@suse.com>

Please drop this tag.

> Signed-off-by: Yangtao Li <frank.li@vivo.com>
> ---
>  fs/btrfs/defrag.c | 52 +++++++++++++++++++++++------------------------
>  1 file changed, 25 insertions(+), 27 deletions(-)
> 
> diff --git a/fs/btrfs/defrag.c b/fs/btrfs/defrag.c
> index d4310d93f532..d908bce0b8a1 100644
> --- a/fs/btrfs/defrag.c
> +++ b/fs/btrfs/defrag.c
> @@ -60,6 +60,16 @@ static int compare_inode_defrag(const struct inode_defrag *defrag1,
>  		return 0;
>  }
>  
> +static int inode_defrag_cmp(struct rb_node *new, const struct rb_node *exist)

This is a bit confusing name because there's also compare_inode_defrag()
but I don't have a better suggestion.

> +{
> +	const struct inode_defrag *new_defrag =
> +		rb_entry(new, struct inode_defrag, rb_node);
> +	const struct inode_defrag *exist_defrag =
> +		rb_entry(exist, struct inode_defrag, rb_node);
> +
> +	return compare_inode_defrag(new_defrag, exist_defrag);
> +}
> +
>  /*
>   * Insert a record for an inode into the defrag tree.  The lock must be held
>   * already.
> @@ -71,37 +81,25 @@ static int btrfs_insert_inode_defrag(struct btrfs_inode *inode,
>  				     struct inode_defrag *defrag)
>  {
>  	struct btrfs_fs_info *fs_info = inode->root->fs_info;
> -	struct inode_defrag *entry;
> -	struct rb_node **p;
> -	struct rb_node *parent = NULL;
> -	int ret;
> +	struct rb_node *exist;

Please use 'node' for the rb_nodes.

>  
> -	p = &fs_info->defrag_inodes.rb_node;
> -	while (*p) {
> -		parent = *p;
> -		entry = rb_entry(parent, struct inode_defrag, rb_node);
> +	exist = rb_find_add(&defrag->rb_node, &fs_info->defrag_inodes, inode_defrag_cmp);
> +	if (exist) {
> +		struct inode_defrag *entry;
>  
> -		ret = compare_inode_defrag(defrag, entry);
> -		if (ret < 0)
> -			p = &parent->rb_left;
> -		else if (ret > 0)
> -			p = &parent->rb_right;
> -		else {
> -			/*
> -			 * If we're reinserting an entry for an old defrag run,
> -			 * make sure to lower the transid of our existing
> -			 * record.
> -			 */
> -			if (defrag->transid < entry->transid)
> -				entry->transid = defrag->transid;
> -			entry->extent_thresh = min(defrag->extent_thresh,
> -						   entry->extent_thresh);
> -			return -EEXIST;
> -		}
> +		entry = rb_entry(exist, struct inode_defrag, rb_node);
> +		/*
> +		 * If we're reinserting an entry for an old defrag run,
> +		 * make sure to lower the transid of our existing
> +		 * record.

Please reformat the comment to 80 columns.

> +		 */
> +		if (defrag->transid < entry->transid)
> +			entry->transid = defrag->transid;
> +		entry->extent_thresh = min(defrag->extent_thresh,
> +					   entry->extent_thresh);
> +		return -EEXIST;
>  	}
>  	set_bit(BTRFS_INODE_IN_DEFRAG, &inode->runtime_flags);
> -	rb_link_node(&defrag->rb_node, parent, p);
> -	rb_insert_color(&defrag->rb_node, &fs_info->defrag_inodes);
>  	return 0;
>  }
>  
> -- 
> 2.39.0
> 

Re: [PATCH 01/13] btrfs: update btrfs_insert_inode_defrag to to use rb helper

[Yangtao Li]

Hi David，


The new patchset has been send. Could you please consider taking a look？

https://lore.kernel.org/all/20250516030333.3758-1-panchuang@vivo.com/

Thx，
Yangtao

Re: [PATCH 01/13] btrfs: update btrfs_insert_inode_defrag to to use rb helper

[David Sterba]

On Tue, May 20, 2025 at 01:14:00PM +0800, Yangtao Li wrote:
> Hi David，
> 
> The new patchset has been send. Could you please consider taking a look？

Yes, next week once the merge window opens.