[PATCHi 0/6] reduce boilerplate code within btrfs

[PATCHi 0/6] reduce boilerplate code within btrfs

[Roger L. Beckermeyer III]

The goal of this patch series is to reduce boilerplate code
within btrfs. To accomplish this rb_find_add_cached() was added
to linux/include/rbtree.h. Any replaceable functions were then 
replaced within btrfs.

Roger L. Beckermeyer III (6):
  rbtree: add rb_find_add_cached() to rbtree.h
  btrfs: edit btrfs_add_block_group_cache() to use rb helper
  btrfs: edit prelim_ref_insert() to use rb helpers
  btrfs: edit __btrfs_add_delayed_item() to use rb helper
  btrfs: edit btrfs_add_chunk_map() to use rb helpers
  btrfs: edits tree_insert() to use rb helpers

 fs/btrfs/backref.c       | 71 ++++++++++++++++++++--------------------
 fs/btrfs/block-group.c   | 40 ++++++++++------------
 fs/btrfs/delayed-inode.c | 40 +++++++++-------------
 fs/btrfs/delayed-ref.c   | 43 ++++++++++++------------
 fs/btrfs/volumes.c       | 39 ++++++++++------------
 include/linux/rbtree.h   | 37 +++++++++++++++++++++
 6 files changed, 145 insertions(+), 125 deletions(-)

-- 
2.45.2

[PATCH] rbtree: add rb_find_add_cached() to rbtree.h

[Roger L. Beckermeyer III]

Adds rb_find_add_cached() as a helper function for use with
red-black trees. This will be used in btrfs to reduce boilerplate code.

Reviewed-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
Tested-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
Suggested-by: Josef Bacik <josef@toxicpanda.com>
Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
---
 include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++
 1 file changed, 37 insertions(+)

diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 7c173aa64e1e..0d4444c0cfb3 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -210,6 +210,43 @@ rb_add(struct rb_node *node, struct rb_root *tree,
 	rb_insert_color(node, tree);
 }
 
+/**
+ * rb_find_add_cached() - find equivalent @node in @tree, or add @node
+ * @node: node to look-for / insert
+ * @tree: tree to search / modify
+ * @cmp: operator defining the node order
+ *
+ * Returns the rb_node matching @node, or NULL when no match is found and @node
+ * is inserted.
+ */
+static __always_inline struct rb_node *
+rb_find_add_cached(struct rb_node *node, struct rb_root_cached *tree,
+	    int (*cmp)(struct rb_node *, const struct rb_node *))
+{
+	bool leftmost = true;
+	struct rb_node **link = &tree->rb_root.rb_node;
+	struct rb_node *parent = NULL;
+	int c;
+
+	while (*link) {
+		parent = *link;
+		c = cmp(node, parent);
+
+		if (c < 0) {
+			link = &parent->rb_left;
+		} else if (c > 0) {
+			link = &parent->rb_right;
+			leftmost = false;
+		} else {
+			return parent;
+		}
+	}
+
+	rb_link_node(node, parent, link);
+	rb_insert_color_cached(node, tree, leftmost);
+	return NULL;
+}
+
 /**
  * rb_find_add() - find equivalent @node in @tree, or add @node
  * @node: node to look-for / insert
-- 
2.45.2

[PATCH] btrfs: edit btrfs_add_block_group_cache() to use rb helper

[Roger L. Beckermeyer III]

Edits fs/btrfs/block-group.c to use rb_find_add_cached(),
also adds a comparison function, btrfs_add_block_blkgrp_cmp(),
for use with rb_find_add_cached().

Tested-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
Suggested-by: Josef Bacik <josef@toxicpanda.com>
Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
Reviewed-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
---
 fs/btrfs/block-group.c | 40 +++++++++++++++++-----------------------
 1 file changed, 17 insertions(+), 23 deletions(-)

diff --git a/fs/btrfs/block-group.c b/fs/btrfs/block-group.c
index 5be029734cfa..ccff051de43a 100644
--- a/fs/btrfs/block-group.c
+++ b/fs/btrfs/block-group.c
@@ -173,40 +173,34 @@ void btrfs_put_block_group(struct btrfs_block_group *cache)
 	}
 }
 
+static int btrfs_add_blkgrp_cmp(struct rb_node *new, const struct rb_node *exist)
+{
+	struct btrfs_block_group *cmp1 = rb_entry(new, struct btrfs_block_group, cache_node);
+	struct btrfs_block_group *cmp2 = rb_entry(exist, struct btrfs_block_group, cache_node);
+
+	if (cmp1->start < cmp2->start)
+		return -1;
+	if (cmp1->start > cmp2->start)
+		return 1;
+	return 0;
+}
+
 /*
  * This adds the block group to the fs_info rb tree for the block group cache
  */
 static int btrfs_add_block_group_cache(struct btrfs_fs_info *info,
 				       struct btrfs_block_group *block_group)
 {
-	struct rb_node **p;
-	struct rb_node *parent = NULL;
-	struct btrfs_block_group *cache;
-	bool leftmost = true;
+	struct rb_node *exist;
 
 	ASSERT(block_group->length != 0);
 
 	write_lock(&info->block_group_cache_lock);
-	p = &info->block_group_cache_tree.rb_root.rb_node;
-
-	while (*p) {
-		parent = *p;
-		cache = rb_entry(parent, struct btrfs_block_group, cache_node);
-		if (block_group->start < cache->start) {
-			p = &(*p)->rb_left;
-		} else if (block_group->start > cache->start) {
-			p = &(*p)->rb_right;
-			leftmost = false;
-		} else {
-			write_unlock(&info->block_group_cache_lock);
-			return -EEXIST;
-		}
-	}
-
-	rb_link_node(&block_group->cache_node, parent, p);
-	rb_insert_color_cached(&block_group->cache_node,
-			       &info->block_group_cache_tree, leftmost);
 
+	exist = rb_find_add_cached(&block_group->cache_node,
+			&info->block_group_cache_tree, btrfs_add_blkgrp_cmp);
+	if (exist != NULL)
+		return -EEXIST;
 	write_unlock(&info->block_group_cache_lock);
 
 	return 0;
-- 
2.45.2

Re: [PATCH] btrfs: edit btrfs_add_block_group_cache() to use rb helper

[kernel test robot]

Hi Roger,

kernel test robot noticed the following build errors:

[auto build test ERROR on kdave/for-next]
[also build test ERROR on linus/master v6.13-rc2 next-20241206]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Roger-L-Beckermeyer-III/btrfs-edit-btrfs_add_block_group_cache-to-use-rb-helper/20241209-064300
base:   https://git.kernel.org/pub/scm/linux/kernel/git/kdave/linux.git for-next
patch link:    https://lore.kernel.org/r/4d8d468cc1240adf03fd23fd4b80582f57a5b28f.1733695544.git.beckerlee3%40gmail.com
patch subject: [PATCH] btrfs: edit btrfs_add_block_group_cache() to use rb helper
config: arc-randconfig-002-20241209 (https://download.01.org/0day-ci/archive/20241209/202412090910.F5gin2Tv-lkp@intel.com/config)
compiler: arc-elf-gcc (GCC) 13.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20241209/202412090910.F5gin2Tv-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202412090910.F5gin2Tv-lkp@intel.com/

All error/warnings (new ones prefixed by >>):

   fs/btrfs/block-group.c: In function 'btrfs_add_block_group_cache':
>> fs/btrfs/block-group.c:200:17: error: implicit declaration of function 'rb_find_add_cached'; did you mean 'rb_find_add_rcu'? [-Werror=implicit-function-declaration]
     200 |         exist = rb_find_add_cached(&block_group->cache_node,
         |                 ^~~~~~~~~~~~~~~~~~
         |                 rb_find_add_rcu
>> fs/btrfs/block-group.c:200:15: warning: assignment to 'struct rb_node *' from 'int' makes pointer from integer without a cast [-Wint-conversion]
     200 |         exist = rb_find_add_cached(&block_group->cache_node,
         |               ^
   cc1: some warnings being treated as errors


vim +200 fs/btrfs/block-group.c

   187	
   188	/*
   189	 * This adds the block group to the fs_info rb tree for the block group cache
   190	 */
   191	static int btrfs_add_block_group_cache(struct btrfs_fs_info *info,
   192					       struct btrfs_block_group *block_group)
   193	{
   194		struct rb_node *exist;
   195	
   196		ASSERT(block_group->length != 0);
   197	
   198		write_lock(&info->block_group_cache_lock);
   199	
 > 200		exist = rb_find_add_cached(&block_group->cache_node,
   201				&info->block_group_cache_tree, btrfs_add_blkgrp_cmp);
   202		if (exist != NULL)
   203			return -EEXIST;
   204		write_unlock(&info->block_group_cache_lock);
   205	
   206		return 0;
   207	}
   208	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

[PATCH] btrfs: edit prelim_ref_insert() to use rb helpers

[Roger L. Beckermeyer III]

This commit edits prelim_ref_insert() in fs/btrfs/backref.c to use
rb_find_add_cached(). It also adds a comparison function for use with
rb_find_add_cached().

Reviewed-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
Tested-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
---
 fs/btrfs/backref.c | 71 +++++++++++++++++++++++-----------------------
 1 file changed, 36 insertions(+), 35 deletions(-)

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 6d9f39c1d89c..fcbcfce0f93a 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -250,6 +250,17 @@ static int prelim_ref_compare(const struct prelim_ref *ref1,
 	return 0;
 }
 
+static int prelim_ref_cmp(struct rb_node *node, const struct rb_node *exist)
+{
+	int result;
+	struct prelim_ref *ref1 = rb_entry(node, struct prelim_ref, rbnode);
+	struct prelim_ref *ref2 = rb_entry(exist, struct prelim_ref, rbnode);
+
+	result = prelim_ref_compare(ref1, ref2);
+
+	return result;
+}
+
 static void update_share_count(struct share_check *sc, int oldcount,
 			       int newcount, const struct prelim_ref *newref)
 {
@@ -281,52 +292,42 @@ static void prelim_ref_insert(const struct btrfs_fs_info *fs_info,
 	struct rb_node **p;
 	struct rb_node *parent = NULL;
 	struct prelim_ref *ref;
-	int result;
-	bool leftmost = true;
+	struct rb_node *exist;
 
 	root = &preftree->root;
 	p = &root->rb_root.rb_node;
+	parent = *p;
+	ref = rb_entry(parent, struct prelim_ref, rbnode);
 
-	while (*p) {
-		parent = *p;
-		ref = rb_entry(parent, struct prelim_ref, rbnode);
-		result = prelim_ref_compare(ref, newref);
-		if (result < 0) {
-			p = &(*p)->rb_left;
-		} else if (result > 0) {
-			p = &(*p)->rb_right;
-			leftmost = false;
-		} else {
-			/* Identical refs, merge them and free @newref */
-			struct extent_inode_elem *eie = ref->inode_list;
+	exist = rb_find_add_cached(&newref->rbnode, root, prelim_ref_cmp);
+	if (exist != NULL) {
+		/* Identical refs, merge them and free @newref */
+		struct extent_inode_elem *eie = ref->inode_list;
 
-			while (eie && eie->next)
-				eie = eie->next;
+		while (eie && eie->next)
+			eie = eie->next;
 
-			if (!eie)
-				ref->inode_list = newref->inode_list;
-			else
-				eie->next = newref->inode_list;
-			trace_btrfs_prelim_ref_merge(fs_info, ref, newref,
-						     preftree->count);
-			/*
-			 * A delayed ref can have newref->count < 0.
-			 * The ref->count is updated to follow any
-			 * BTRFS_[ADD|DROP]_DELAYED_REF actions.
-			 */
-			update_share_count(sc, ref->count,
-					   ref->count + newref->count, newref);
-			ref->count += newref->count;
-			free_pref(newref);
-			return;
-		}
+		if (!eie)
+			ref->inode_list = newref->inode_list;
+		else
+			eie->next = newref->inode_list;
+		trace_btrfs_prelim_ref_merge(fs_info, ref, newref,
+							preftree->count);
+		/*
+		 * A delayed ref can have newref->count < 0.
+		 * The ref->count is updated to follow any
+		 * BTRFS_[ADD|DROP]_DELAYED_REF actions.
+		 */
+		update_share_count(sc, ref->count,
+					ref->count + newref->count, newref);
+		ref->count += newref->count;
+		free_pref(newref);
+		return;
 	}
 
 	update_share_count(sc, 0, newref->count, newref);
 	preftree->count++;
 	trace_btrfs_prelim_ref_insert(fs_info, newref, NULL, preftree->count);
-	rb_link_node(&newref->rbnode, parent, p);
-	rb_insert_color_cached(&newref->rbnode, root, leftmost);
 }
 
 /*
-- 
2.45.2

Re: [PATCH] btrfs: edit prelim_ref_insert() to use rb helpers

[kernel test robot]

Hi Roger,

kernel test robot noticed the following build errors:

[auto build test ERROR on kdave/for-next]
[also build test ERROR on linus/master v6.13-rc2 next-20241206]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Roger-L-Beckermeyer-III/btrfs-edit-prelim_ref_insert-to-use-rb-helpers/20241209-064043
base:   https://git.kernel.org/pub/scm/linux/kernel/git/kdave/linux.git for-next
patch link:    https://lore.kernel.org/r/8201f6ae724c5dbc7c82f2ed294d457db208b2fa.1733695544.git.beckerlee3%40gmail.com
patch subject: [PATCH] btrfs: edit prelim_ref_insert() to use rb helpers
config: arc-randconfig-002-20241209 (https://download.01.org/0day-ci/archive/20241209/202412090922.Cg7LuOhS-lkp@intel.com/config)
compiler: arc-elf-gcc (GCC) 13.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20241209/202412090922.Cg7LuOhS-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202412090922.Cg7LuOhS-lkp@intel.com/

All error/warnings (new ones prefixed by >>):

   fs/btrfs/backref.c: In function 'prelim_ref_insert':
>> fs/btrfs/backref.c:302:17: error: implicit declaration of function 'rb_find_add_cached'; did you mean 'rb_find_add_rcu'? [-Werror=implicit-function-declaration]
     302 |         exist = rb_find_add_cached(&newref->rbnode, root, prelim_ref_cmp);
         |                 ^~~~~~~~~~~~~~~~~~
         |                 rb_find_add_rcu
>> fs/btrfs/backref.c:302:15: warning: assignment to 'struct rb_node *' from 'int' makes pointer from integer without a cast [-Wint-conversion]
     302 |         exist = rb_find_add_cached(&newref->rbnode, root, prelim_ref_cmp);
         |               ^
   cc1: some warnings being treated as errors


vim +302 fs/btrfs/backref.c

   280	
   281	/*
   282	 * Add @newref to the @root rbtree, merging identical refs.
   283	 *
   284	 * Callers should assume that newref has been freed after calling.
   285	 */
   286	static void prelim_ref_insert(const struct btrfs_fs_info *fs_info,
   287				      struct preftree *preftree,
   288				      struct prelim_ref *newref,
   289				      struct share_check *sc)
   290	{
   291		struct rb_root_cached *root;
   292		struct rb_node **p;
   293		struct rb_node *parent = NULL;
   294		struct prelim_ref *ref;
   295		struct rb_node *exist;
   296	
   297		root = &preftree->root;
   298		p = &root->rb_root.rb_node;
   299		parent = *p;
   300		ref = rb_entry(parent, struct prelim_ref, rbnode);
   301	
 > 302		exist = rb_find_add_cached(&newref->rbnode, root, prelim_ref_cmp);
   303		if (exist != NULL) {
   304			/* Identical refs, merge them and free @newref */
   305			struct extent_inode_elem *eie = ref->inode_list;
   306	
   307			while (eie && eie->next)
   308				eie = eie->next;
   309	
   310			if (!eie)
   311				ref->inode_list = newref->inode_list;
   312			else
   313				eie->next = newref->inode_list;
   314			trace_btrfs_prelim_ref_merge(fs_info, ref, newref,
   315								preftree->count);
   316			/*
   317			 * A delayed ref can have newref->count < 0.
   318			 * The ref->count is updated to follow any
   319			 * BTRFS_[ADD|DROP]_DELAYED_REF actions.
   320			 */
   321			update_share_count(sc, ref->count,
   322						ref->count + newref->count, newref);
   323			ref->count += newref->count;
   324			free_pref(newref);
   325			return;
   326		}
   327	
   328		update_share_count(sc, 0, newref->count, newref);
   329		preftree->count++;
   330		trace_btrfs_prelim_ref_insert(fs_info, newref, NULL, preftree->count);
   331	}
   332	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

Re: [PATCH] btrfs: edit prelim_ref_insert() to use rb helpers

[kernel test robot]

Hi Roger,

kernel test robot noticed the following build errors:

[auto build test ERROR on kdave/for-next]
[also build test ERROR on linus/master v6.13-rc2 next-20241206]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Roger-L-Beckermeyer-III/btrfs-edit-prelim_ref_insert-to-use-rb-helpers/20241209-064043
base:   https://git.kernel.org/pub/scm/linux/kernel/git/kdave/linux.git for-next
patch link:    https://lore.kernel.org/r/8201f6ae724c5dbc7c82f2ed294d457db208b2fa.1733695544.git.beckerlee3%40gmail.com
patch subject: [PATCH] btrfs: edit prelim_ref_insert() to use rb helpers
config: arm-randconfig-001-20241209 (https://download.01.org/0day-ci/archive/20241209/202412090958.CtUdYRwP-lkp@intel.com/config)
compiler: clang version 20.0.0git (https://github.com/llvm/llvm-project 592c0fe55f6d9a811028b5f3507be91458ab2713)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20241209/202412090958.CtUdYRwP-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202412090958.CtUdYRwP-lkp@intel.com/

All errors (new ones prefixed by >>):

   In file included from fs/btrfs/backref.c:6:
   In file included from include/linux/mm.h:2223:
   include/linux/vmstat.h:518:36: warning: arithmetic between different enumeration types ('enum node_stat_item' and 'enum lru_list') [-Wenum-enum-conversion]
     518 |         return node_stat_name(NR_LRU_BASE + lru) + 3; // skip "nr_"
         |                               ~~~~~~~~~~~ ^ ~~~
>> fs/btrfs/backref.c:302:10: error: call to undeclared function 'rb_find_add_cached'; ISO C99 and later do not support implicit function declarations [-Wimplicit-function-declaration]
     302 |         exist = rb_find_add_cached(&newref->rbnode, root, prelim_ref_cmp);
         |                 ^
>> fs/btrfs/backref.c:302:8: error: incompatible integer to pointer conversion assigning to 'struct rb_node *' from 'int' [-Wint-conversion]
     302 |         exist = rb_find_add_cached(&newref->rbnode, root, prelim_ref_cmp);
         |               ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   1 warning and 2 errors generated.


vim +/rb_find_add_cached +302 fs/btrfs/backref.c

   280	
   281	/*
   282	 * Add @newref to the @root rbtree, merging identical refs.
   283	 *
   284	 * Callers should assume that newref has been freed after calling.
   285	 */
   286	static void prelim_ref_insert(const struct btrfs_fs_info *fs_info,
   287				      struct preftree *preftree,
   288				      struct prelim_ref *newref,
   289				      struct share_check *sc)
   290	{
   291		struct rb_root_cached *root;
   292		struct rb_node **p;
   293		struct rb_node *parent = NULL;
   294		struct prelim_ref *ref;
   295		struct rb_node *exist;
   296	
   297		root = &preftree->root;
   298		p = &root->rb_root.rb_node;
   299		parent = *p;
   300		ref = rb_entry(parent, struct prelim_ref, rbnode);
   301	
 > 302		exist = rb_find_add_cached(&newref->rbnode, root, prelim_ref_cmp);
   303		if (exist != NULL) {
   304			/* Identical refs, merge them and free @newref */
   305			struct extent_inode_elem *eie = ref->inode_list;
   306	
   307			while (eie && eie->next)
   308				eie = eie->next;
   309	
   310			if (!eie)
   311				ref->inode_list = newref->inode_list;
   312			else
   313				eie->next = newref->inode_list;
   314			trace_btrfs_prelim_ref_merge(fs_info, ref, newref,
   315								preftree->count);
   316			/*
   317			 * A delayed ref can have newref->count < 0.
   318			 * The ref->count is updated to follow any
   319			 * BTRFS_[ADD|DROP]_DELAYED_REF actions.
   320			 */
   321			update_share_count(sc, ref->count,
   322						ref->count + newref->count, newref);
   323			ref->count += newref->count;
   324			free_pref(newref);
   325			return;
   326		}
   327	
   328		update_share_count(sc, 0, newref->count, newref);
   329		preftree->count++;
   330		trace_btrfs_prelim_ref_insert(fs_info, newref, NULL, preftree->count);
   331	}
   332	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

[PATCH] btrfs: edit __btrfs_add_delayed_item() to use rb helper

[Roger L. Beckermeyer III]

This commit edits __btrfs_add_delayed_item() to use rb_find_add_cached().
It also adds a helper function to use with rb_find_add_cached().

Reviewed-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
Tested-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
---
 fs/btrfs/delayed-inode.c | 40 ++++++++++++++++------------------------
 1 file changed, 16 insertions(+), 24 deletions(-)

diff --git a/fs/btrfs/delayed-inode.c b/fs/btrfs/delayed-inode.c
index 508bdbae29a0..7d62224bc49c 100644
--- a/fs/btrfs/delayed-inode.c
+++ b/fs/btrfs/delayed-inode.c
@@ -366,40 +366,32 @@ static struct btrfs_delayed_item *__btrfs_lookup_delayed_item(
 	return NULL;
 }
 
+static int btrfs_add_delayed_item_cmp(struct rb_node *rb_node, const struct rb_node *exist_node)
+{
+	struct btrfs_delayed_item *item = rb_entry(rb_node, struct btrfs_delayed_item, rb_node);
+	struct btrfs_delayed_item *exist = rb_entry(exist_node, struct btrfs_delayed_item, rb_node);
+
+	if (item->index < exist->index)
+		return -1;
+	if (item->index > exist->index)
+		return 1;
+	return 0;
+}
+
 static int __btrfs_add_delayed_item(struct btrfs_delayed_node *delayed_node,
 				    struct btrfs_delayed_item *ins)
 {
-	struct rb_node **p, *node;
-	struct rb_node *parent_node = NULL;
 	struct rb_root_cached *root;
-	struct btrfs_delayed_item *item;
-	bool leftmost = true;
+	struct rb_node *exist;
 
 	if (ins->type == BTRFS_DELAYED_INSERTION_ITEM)
 		root = &delayed_node->ins_root;
 	else
 		root = &delayed_node->del_root;
 
-	p = &root->rb_root.rb_node;
-	node = &ins->rb_node;
-
-	while (*p) {
-		parent_node = *p;
-		item = rb_entry(parent_node, struct btrfs_delayed_item,
-				 rb_node);
-
-		if (item->index < ins->index) {
-			p = &(*p)->rb_right;
-			leftmost = false;
-		} else if (item->index > ins->index) {
-			p = &(*p)->rb_left;
-		} else {
-			return -EEXIST;
-		}
-	}
-
-	rb_link_node(node, parent_node, p);
-	rb_insert_color_cached(node, root, leftmost);
+	exist = rb_find_add_cached(&ins->rb_node, root, btrfs_add_delayed_item_cmp);
+	if (exist != NULL)
+		return -EEXIST;
 
 	if (ins->type == BTRFS_DELAYED_INSERTION_ITEM &&
 	    ins->index >= delayed_node->index_cnt)
-- 
2.45.2

Re: [PATCH] btrfs: edit __btrfs_add_delayed_item() to use rb helper

[kernel test robot]

Hi Roger,

kernel test robot noticed the following build errors:

[auto build test ERROR on kdave/for-next]
[also build test ERROR on linus/master v6.13-rc2 next-20241206]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Roger-L-Beckermeyer-III/btrfs-edit-__btrfs_add_delayed_item-to-use-rb-helper/20241209-064154
base:   https://git.kernel.org/pub/scm/linux/kernel/git/kdave/linux.git for-next
patch link:    https://lore.kernel.org/r/9b85bdbc269d20886590f0a70de66c602d72aa9d.1733695544.git.beckerlee3%40gmail.com
patch subject: [PATCH] btrfs: edit __btrfs_add_delayed_item() to use rb helper
config: arc-randconfig-002-20241209 (https://download.01.org/0day-ci/archive/20241209/202412090921.E0n0Ioce-lkp@intel.com/config)
compiler: arc-elf-gcc (GCC) 13.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20241209/202412090921.E0n0Ioce-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202412090921.E0n0Ioce-lkp@intel.com/

All error/warnings (new ones prefixed by >>):

   fs/btrfs/delayed-inode.c: In function '__btrfs_add_delayed_item':
>> fs/btrfs/delayed-inode.c:392:17: error: implicit declaration of function 'rb_find_add_cached'; did you mean 'rb_find_add_rcu'? [-Werror=implicit-function-declaration]
     392 |         exist = rb_find_add_cached(&ins->rb_node, root, btrfs_add_delayed_item_cmp);
         |                 ^~~~~~~~~~~~~~~~~~
         |                 rb_find_add_rcu
>> fs/btrfs/delayed-inode.c:392:15: warning: assignment to 'struct rb_node *' from 'int' makes pointer from integer without a cast [-Wint-conversion]
     392 |         exist = rb_find_add_cached(&ins->rb_node, root, btrfs_add_delayed_item_cmp);
         |               ^
   cc1: some warnings being treated as errors


vim +392 fs/btrfs/delayed-inode.c

   380	
   381	static int __btrfs_add_delayed_item(struct btrfs_delayed_node *delayed_node,
   382					    struct btrfs_delayed_item *ins)
   383	{
   384		struct rb_root_cached *root;
   385		struct rb_node *exist;
   386	
   387		if (ins->type == BTRFS_DELAYED_INSERTION_ITEM)
   388			root = &delayed_node->ins_root;
   389		else
   390			root = &delayed_node->del_root;
   391	
 > 392		exist = rb_find_add_cached(&ins->rb_node, root, btrfs_add_delayed_item_cmp);
   393		if (exist != NULL)
   394			return -EEXIST;
   395	
   396		if (ins->type == BTRFS_DELAYED_INSERTION_ITEM &&
   397		    ins->index >= delayed_node->index_cnt)
   398			delayed_node->index_cnt = ins->index + 1;
   399	
   400		delayed_node->count++;
   401		atomic_inc(&delayed_node->root->fs_info->delayed_root->items);
   402		return 0;
   403	}
   404	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

Re: [PATCH] btrfs: edit __btrfs_add_delayed_item() to use rb helper

[kernel test robot]

Hi Roger,

kernel test robot noticed the following build errors:

[auto build test ERROR on kdave/for-next]
[also build test ERROR on linus/master v6.13-rc2 next-20241206]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Roger-L-Beckermeyer-III/btrfs-edit-__btrfs_add_delayed_item-to-use-rb-helper/20241209-064154
base:   https://git.kernel.org/pub/scm/linux/kernel/git/kdave/linux.git for-next
patch link:    https://lore.kernel.org/r/9b85bdbc269d20886590f0a70de66c602d72aa9d.1733695544.git.beckerlee3%40gmail.com
patch subject: [PATCH] btrfs: edit __btrfs_add_delayed_item() to use rb helper
config: arm-randconfig-001-20241209 (https://download.01.org/0day-ci/archive/20241209/202412091036.JGaCqbvL-lkp@intel.com/config)
compiler: clang version 20.0.0git (https://github.com/llvm/llvm-project 592c0fe55f6d9a811028b5f3507be91458ab2713)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20241209/202412091036.JGaCqbvL-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202412091036.JGaCqbvL-lkp@intel.com/

All errors (new ones prefixed by >>):

   In file included from fs/btrfs/delayed-inode.c:9:
   In file included from fs/btrfs/ctree.h:10:
   In file included from include/linux/pagemap.h:8:
   In file included from include/linux/mm.h:2223:
   include/linux/vmstat.h:518:36: warning: arithmetic between different enumeration types ('enum node_stat_item' and 'enum lru_list') [-Wenum-enum-conversion]
     518 |         return node_stat_name(NR_LRU_BASE + lru) + 3; // skip "nr_"
         |                               ~~~~~~~~~~~ ^ ~~~
>> fs/btrfs/delayed-inode.c:392:10: error: call to undeclared function 'rb_find_add_cached'; ISO C99 and later do not support implicit function declarations [-Wimplicit-function-declaration]
     392 |         exist = rb_find_add_cached(&ins->rb_node, root, btrfs_add_delayed_item_cmp);
         |                 ^
>> fs/btrfs/delayed-inode.c:392:8: error: incompatible integer to pointer conversion assigning to 'struct rb_node *' from 'int' [-Wint-conversion]
     392 |         exist = rb_find_add_cached(&ins->rb_node, root, btrfs_add_delayed_item_cmp);
         |               ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   1 warning and 2 errors generated.


vim +/rb_find_add_cached +392 fs/btrfs/delayed-inode.c

   380	
   381	static int __btrfs_add_delayed_item(struct btrfs_delayed_node *delayed_node,
   382					    struct btrfs_delayed_item *ins)
   383	{
   384		struct rb_root_cached *root;
   385		struct rb_node *exist;
   386	
   387		if (ins->type == BTRFS_DELAYED_INSERTION_ITEM)
   388			root = &delayed_node->ins_root;
   389		else
   390			root = &delayed_node->del_root;
   391	
 > 392		exist = rb_find_add_cached(&ins->rb_node, root, btrfs_add_delayed_item_cmp);
   393		if (exist != NULL)
   394			return -EEXIST;
   395	
   396		if (ins->type == BTRFS_DELAYED_INSERTION_ITEM &&
   397		    ins->index >= delayed_node->index_cnt)
   398			delayed_node->index_cnt = ins->index + 1;
   399	
   400		delayed_node->count++;
   401		atomic_inc(&delayed_node->root->fs_info->delayed_root->items);
   402		return 0;
   403	}
   404	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

Re: [PATCH] btrfs: edit __btrfs_add_delayed_item() to use rb helper

[kernel test robot]

Hi Roger,

kernel test robot noticed the following build errors:

[auto build test ERROR on kdave/for-next]
[also build test ERROR on linus/master v6.13-rc2 next-20241211]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Roger-L-Beckermeyer-III/btrfs-edit-__btrfs_add_delayed_item-to-use-rb-helper/20241209-104443
base:   https://git.kernel.org/pub/scm/linux/kernel/git/kdave/linux.git for-next
patch link:    https://lore.kernel.org/r/9b85bdbc269d20886590f0a70de66c602d72aa9d.1733695544.git.beckerlee3%40gmail.com
patch subject: [PATCH] btrfs: edit __btrfs_add_delayed_item() to use rb helper
config: s390-defconfig (https://download.01.org/0day-ci/archive/20241212/202412120959.0utuK69J-lkp@intel.com/config)
compiler: clang version 15.0.7 (https://github.com/llvm/llvm-project 8dfdcc7b7bf66834a761bd8de445840ef68e4d1a)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20241212/202412120959.0utuK69J-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202412120959.0utuK69J-lkp@intel.com/

All errors (new ones prefixed by >>):

>> fs/btrfs/delayed-inode.c:392:10: error: call to undeclared function 'rb_find_add_cached'; ISO C99 and later do not support implicit function declarations [-Werror,-Wimplicit-function-declaration]
           exist = rb_find_add_cached(&ins->rb_node, root, btrfs_add_delayed_item_cmp);
                   ^
   fs/btrfs/delayed-inode.c:392:8: error: incompatible integer to pointer conversion assigning to 'struct rb_node *' from 'int' [-Wint-conversion]
           exist = rb_find_add_cached(&ins->rb_node, root, btrfs_add_delayed_item_cmp);
                 ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   2 errors generated.


vim +/rb_find_add_cached +392 fs/btrfs/delayed-inode.c

   380	
   381	static int __btrfs_add_delayed_item(struct btrfs_delayed_node *delayed_node,
   382					    struct btrfs_delayed_item *ins)
   383	{
   384		struct rb_root_cached *root;
   385		struct rb_node *exist;
   386	
   387		if (ins->type == BTRFS_DELAYED_INSERTION_ITEM)
   388			root = &delayed_node->ins_root;
   389		else
   390			root = &delayed_node->del_root;
   391	
 > 392		exist = rb_find_add_cached(&ins->rb_node, root, btrfs_add_delayed_item_cmp);
   393		if (exist != NULL)
   394			return -EEXIST;
   395	
   396		if (ins->type == BTRFS_DELAYED_INSERTION_ITEM &&
   397		    ins->index >= delayed_node->index_cnt)
   398			delayed_node->index_cnt = ins->index + 1;
   399	
   400		delayed_node->count++;
   401		atomic_inc(&delayed_node->root->fs_info->delayed_root->items);
   402		return 0;
   403	}
   404	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

[PATCH] btrfs: edit btrfs_add_chunk_map() to use rb helpers

[Roger L. Beckermeyer III]

Edits btrfs_add_chunk_map() to use rb_find_add_cached(). Also adds a
comparison function to use with rb_find_add_cached().

Reviewed-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
Tested-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
---
 fs/btrfs/volumes.c | 39 ++++++++++++++++++---------------------
 1 file changed, 18 insertions(+), 21 deletions(-)

diff --git a/fs/btrfs/volumes.c b/fs/btrfs/volumes.c
index 1cccaf9c2b0d..4837761a56c9 100644
--- a/fs/btrfs/volumes.c
+++ b/fs/btrfs/volumes.c
@@ -5513,33 +5513,30 @@ void btrfs_remove_chunk_map(struct btrfs_fs_info *fs_info, struct btrfs_chunk_ma
 	btrfs_free_chunk_map(map);
 }
 
+static int btrfs_chunk_map_cmp(struct rb_node *rb_node, const struct rb_node *exist_node)
+{
+	struct btrfs_chunk_map *map = rb_entry(rb_node, struct btrfs_chunk_map, rb_node);
+	struct btrfs_chunk_map *exist = rb_entry(exist_node, struct btrfs_chunk_map, rb_node);
+
+	if (map->start == exist->start)
+		return 0;
+	if (map->start < exist->start)
+		return -1;
+	return 1;
+}
+
 EXPORT_FOR_TESTS
 int btrfs_add_chunk_map(struct btrfs_fs_info *fs_info, struct btrfs_chunk_map *map)
 {
-	struct rb_node **p;
-	struct rb_node *parent = NULL;
-	bool leftmost = true;
+	struct rb_node *exist;
 
 	write_lock(&fs_info->mapping_tree_lock);
-	p = &fs_info->mapping_tree.rb_root.rb_node;
-	while (*p) {
-		struct btrfs_chunk_map *entry;
-
-		parent = *p;
-		entry = rb_entry(parent, struct btrfs_chunk_map, rb_node);
-
-		if (map->start < entry->start) {
-			p = &(*p)->rb_left;
-		} else if (map->start > entry->start) {
-			p = &(*p)->rb_right;
-			leftmost = false;
-		} else {
-			write_unlock(&fs_info->mapping_tree_lock);
-			return -EEXIST;
-		}
+	exist = rb_find_add_cached(&map->rb_node, &fs_info->mapping_tree, btrfs_chunk_map_cmp);
+
+	if (exist != NULL) {
+		write_unlock(&fs_info->mapping_tree_lock);
+		return -EEXIST;
 	}
-	rb_link_node(&map->rb_node, parent, p);
-	rb_insert_color_cached(&map->rb_node, &fs_info->mapping_tree, leftmost);
 	chunk_map_device_set_bits(map, CHUNK_ALLOCATED);
 	chunk_map_device_clear_bits(map, CHUNK_TRIMMED);
 	write_unlock(&fs_info->mapping_tree_lock);
-- 
2.45.2

Re: [PATCH] btrfs: edit btrfs_add_chunk_map() to use rb helpers

[kernel test robot]

Hi Roger,

kernel test robot noticed the following build errors:

[auto build test ERROR on kdave/for-next]
[also build test ERROR on linus/master v6.13-rc2 next-20241206]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Roger-L-Beckermeyer-III/btrfs-edit-btrfs_add_chunk_map-to-use-rb-helpers/20241209-064330
base:   https://git.kernel.org/pub/scm/linux/kernel/git/kdave/linux.git for-next
patch link:    https://lore.kernel.org/r/3d4e17f44bafeb7e83d2fdfb50ac4e0c3ce2d23e.1733695544.git.beckerlee3%40gmail.com
patch subject: [PATCH] btrfs: edit btrfs_add_chunk_map() to use rb helpers
config: arm-randconfig-001-20241209 (https://download.01.org/0day-ci/archive/20241209/202412090922.LHCgRc17-lkp@intel.com/config)
compiler: clang version 20.0.0git (https://github.com/llvm/llvm-project 592c0fe55f6d9a811028b5f3507be91458ab2713)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20241209/202412090922.LHCgRc17-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202412090922.LHCgRc17-lkp@intel.com/

All errors (new ones prefixed by >>):

   In file included from fs/btrfs/volumes.c:16:
   In file included from fs/btrfs/ctree.h:10:
   In file included from include/linux/pagemap.h:8:
   In file included from include/linux/mm.h:2223:
   include/linux/vmstat.h:518:36: warning: arithmetic between different enumeration types ('enum node_stat_item' and 'enum lru_list') [-Wenum-enum-conversion]
     518 |         return node_stat_name(NR_LRU_BASE + lru) + 3; // skip "nr_"
         |                               ~~~~~~~~~~~ ^ ~~~
>> fs/btrfs/volumes.c:5534:10: error: call to undeclared function 'rb_find_add_cached'; ISO C99 and later do not support implicit function declarations [-Wimplicit-function-declaration]
    5534 |         exist = rb_find_add_cached(&map->rb_node, &fs_info->mapping_tree, btrfs_chunk_map_cmp);
         |                 ^
>> fs/btrfs/volumes.c:5534:8: error: incompatible integer to pointer conversion assigning to 'struct rb_node *' from 'int' [-Wint-conversion]
    5534 |         exist = rb_find_add_cached(&map->rb_node, &fs_info->mapping_tree, btrfs_chunk_map_cmp);
         |               ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   1 warning and 2 errors generated.


vim +/rb_find_add_cached +5534 fs/btrfs/volumes.c

  5527	
  5528	EXPORT_FOR_TESTS
  5529	int btrfs_add_chunk_map(struct btrfs_fs_info *fs_info, struct btrfs_chunk_map *map)
  5530	{
  5531		struct rb_node *exist;
  5532	
  5533		write_lock(&fs_info->mapping_tree_lock);
> 5534		exist = rb_find_add_cached(&map->rb_node, &fs_info->mapping_tree, btrfs_chunk_map_cmp);
  5535	
  5536		if (exist != NULL) {
  5537			write_unlock(&fs_info->mapping_tree_lock);
  5538			return -EEXIST;
  5539		}
  5540		chunk_map_device_set_bits(map, CHUNK_ALLOCATED);
  5541		chunk_map_device_clear_bits(map, CHUNK_TRIMMED);
  5542		write_unlock(&fs_info->mapping_tree_lock);
  5543	
  5544		return 0;
  5545	}
  5546	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

Re: [PATCH] btrfs: edit btrfs_add_chunk_map() to use rb helpers

[kernel test robot]

Hi Roger,

kernel test robot noticed the following build errors:

[auto build test ERROR on kdave/for-next]
[also build test ERROR on linus/master v6.13-rc2 next-20241206]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Roger-L-Beckermeyer-III/btrfs-edit-btrfs_add_chunk_map-to-use-rb-helpers/20241209-064330
base:   https://git.kernel.org/pub/scm/linux/kernel/git/kdave/linux.git for-next
patch link:    https://lore.kernel.org/r/3d4e17f44bafeb7e83d2fdfb50ac4e0c3ce2d23e.1733695544.git.beckerlee3%40gmail.com
patch subject: [PATCH] btrfs: edit btrfs_add_chunk_map() to use rb helpers
config: arc-randconfig-002-20241209 (https://download.01.org/0day-ci/archive/20241209/202412090919.RdI1OMQg-lkp@intel.com/config)
compiler: arc-elf-gcc (GCC) 13.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20241209/202412090919.RdI1OMQg-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202412090919.RdI1OMQg-lkp@intel.com/

All error/warnings (new ones prefixed by >>):

   fs/btrfs/volumes.c: In function 'btrfs_add_chunk_map':
>> fs/btrfs/volumes.c:5534:17: error: implicit declaration of function 'rb_find_add_cached'; did you mean 'rb_find_add_rcu'? [-Werror=implicit-function-declaration]
    5534 |         exist = rb_find_add_cached(&map->rb_node, &fs_info->mapping_tree, btrfs_chunk_map_cmp);
         |                 ^~~~~~~~~~~~~~~~~~
         |                 rb_find_add_rcu
>> fs/btrfs/volumes.c:5534:15: warning: assignment to 'struct rb_node *' from 'int' makes pointer from integer without a cast [-Wint-conversion]
    5534 |         exist = rb_find_add_cached(&map->rb_node, &fs_info->mapping_tree, btrfs_chunk_map_cmp);
         |               ^
   cc1: some warnings being treated as errors


vim +5534 fs/btrfs/volumes.c

  5527	
  5528	EXPORT_FOR_TESTS
  5529	int btrfs_add_chunk_map(struct btrfs_fs_info *fs_info, struct btrfs_chunk_map *map)
  5530	{
  5531		struct rb_node *exist;
  5532	
  5533		write_lock(&fs_info->mapping_tree_lock);
> 5534		exist = rb_find_add_cached(&map->rb_node, &fs_info->mapping_tree, btrfs_chunk_map_cmp);
  5535	
  5536		if (exist != NULL) {
  5537			write_unlock(&fs_info->mapping_tree_lock);
  5538			return -EEXIST;
  5539		}
  5540		chunk_map_device_set_bits(map, CHUNK_ALLOCATED);
  5541		chunk_map_device_clear_bits(map, CHUNK_TRIMMED);
  5542		write_unlock(&fs_info->mapping_tree_lock);
  5543	
  5544		return 0;
  5545	}
  5546	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

[PATCH] btrfs: edits tree_insert() to use rb helpers

[Roger L. Beckermeyer III]

Edits tree_insert() to use rb_find_add_cached(). Also adds a
comparison function for use in rb_find_add_cached() to compare.

Reviewed-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
Tested-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
---
 fs/btrfs/delayed-ref.c | 43 +++++++++++++++++++++---------------------
 1 file changed, 21 insertions(+), 22 deletions(-)

diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c
index 30f7079fa28e..d77ac8d05b2a 100644
--- a/fs/btrfs/delayed-ref.c
+++ b/fs/btrfs/delayed-ref.c
@@ -317,34 +317,33 @@ static int comp_refs(struct btrfs_delayed_ref_node *ref1,
 	return 0;
 }
 
+static int comp_refs_node(struct rb_node *node, const struct rb_node *node2)
+{
+	struct btrfs_delayed_ref_node *ref1;
+	struct btrfs_delayed_ref_node *ref2;
+
+	ref1 = rb_entry(node, struct btrfs_delayed_ref_node, ref_node);
+	ref2 = rb_entry(node2, struct btrfs_delayed_ref_node, ref_node);
+
+	bool check_seq = true;
+	int ret;
+
+	ret = comp_refs(ref1, ref2, check_seq);
+	return ret;
+}
+
 static struct btrfs_delayed_ref_node* tree_insert(struct rb_root_cached *root,
 		struct btrfs_delayed_ref_node *ins)
 {
-	struct rb_node **p = &root->rb_root.rb_node;
 	struct rb_node *node = &ins->ref_node;
-	struct rb_node *parent_node = NULL;
+	struct rb_node *exist;
 	struct btrfs_delayed_ref_node *entry;
-	bool leftmost = true;
-
-	while (*p) {
-		int comp;
-
-		parent_node = *p;
-		entry = rb_entry(parent_node, struct btrfs_delayed_ref_node,
-				 ref_node);
-		comp = comp_refs(ins, entry, true);
-		if (comp < 0) {
-			p = &(*p)->rb_left;
-		} else if (comp > 0) {
-			p = &(*p)->rb_right;
-			leftmost = false;
-		} else {
-			return entry;
-		}
-	}
 
-	rb_link_node(node, parent_node, p);
-	rb_insert_color_cached(node, root, leftmost);
+	exist = rb_find_add_cached(node, root, comp_refs_node);
+	if (exist != NULL) {
+		entry = rb_entry(exist, struct btrfs_delayed_ref_node, ref_node);
+		return entry;
+	}
 	return NULL;
 }
 
-- 
2.45.2

Re: [PATCH] btrfs: edits tree_insert() to use rb helpers

[kernel test robot]

Hi Roger,

kernel test robot noticed the following build errors:

[auto build test ERROR on kdave/for-next]
[also build test ERROR on linus/master v6.13-rc2 next-20241206]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Roger-L-Beckermeyer-III/btrfs-edits-tree_insert-to-use-rb-helpers/20241209-064230
base:   https://git.kernel.org/pub/scm/linux/kernel/git/kdave/linux.git for-next
patch link:    https://lore.kernel.org/r/5e023dcf8f086296da987f8ba2b43be0aca15b86.1733695544.git.beckerlee3%40gmail.com
patch subject: [PATCH] btrfs: edits tree_insert() to use rb helpers
config: arc-randconfig-002-20241209 (https://download.01.org/0day-ci/archive/20241209/202412090944.g3jpT1Cz-lkp@intel.com/config)
compiler: arc-elf-gcc (GCC) 13.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20241209/202412090944.g3jpT1Cz-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202412090944.g3jpT1Cz-lkp@intel.com/

All error/warnings (new ones prefixed by >>):

   fs/btrfs/delayed-ref.c: In function 'tree_insert':
>> fs/btrfs/delayed-ref.c:342:17: error: implicit declaration of function 'rb_find_add_cached'; did you mean 'rb_find_add_rcu'? [-Werror=implicit-function-declaration]
     342 |         exist = rb_find_add_cached(node, root, comp_refs_node);
         |                 ^~~~~~~~~~~~~~~~~~
         |                 rb_find_add_rcu
>> fs/btrfs/delayed-ref.c:342:15: warning: assignment to 'struct rb_node *' from 'int' makes pointer from integer without a cast [-Wint-conversion]
     342 |         exist = rb_find_add_cached(node, root, comp_refs_node);
         |               ^
   cc1: some warnings being treated as errors


vim +342 fs/btrfs/delayed-ref.c

   334	
   335	static struct btrfs_delayed_ref_node* tree_insert(struct rb_root_cached *root,
   336			struct btrfs_delayed_ref_node *ins)
   337	{
   338		struct rb_node *node = &ins->ref_node;
   339		struct rb_node *exist;
   340		struct btrfs_delayed_ref_node *entry;
   341	
 > 342		exist = rb_find_add_cached(node, root, comp_refs_node);
   343		if (exist != NULL) {
   344			entry = rb_entry(exist, struct btrfs_delayed_ref_node, ref_node);
   345			return entry;
   346		}
   347		return NULL;
   348	}
   349	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

Re: [PATCH] btrfs: edits tree_insert() to use rb helpers

[kernel test robot]

Hi Roger,

kernel test robot noticed the following build errors:

[auto build test ERROR on kdave/for-next]
[also build test ERROR on linus/master v6.13-rc2 next-20241206]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Roger-L-Beckermeyer-III/btrfs-edits-tree_insert-to-use-rb-helpers/20241209-064230
base:   https://git.kernel.org/pub/scm/linux/kernel/git/kdave/linux.git for-next
patch link:    https://lore.kernel.org/r/5e023dcf8f086296da987f8ba2b43be0aca15b86.1733695544.git.beckerlee3%40gmail.com
patch subject: [PATCH] btrfs: edits tree_insert() to use rb helpers
config: i386-buildonly-randconfig-003-20241209 (https://download.01.org/0day-ci/archive/20241209/202412091004.4vQ7P5Kl-lkp@intel.com/config)
compiler: clang version 19.1.3 (https://github.com/llvm/llvm-project ab51eccf88f5321e7c60591c5546b254b6afab99)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20241209/202412091004.4vQ7P5Kl-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202412091004.4vQ7P5Kl-lkp@intel.com/

All errors (new ones prefixed by >>):

   In file included from fs/btrfs/delayed-ref.c:10:
   In file included from fs/btrfs/ctree.h:10:
   In file included from include/linux/pagemap.h:8:
   In file included from include/linux/mm.h:2223:
   include/linux/vmstat.h:518:36: warning: arithmetic between different enumeration types ('enum node_stat_item' and 'enum lru_list') [-Wenum-enum-conversion]
     518 |         return node_stat_name(NR_LRU_BASE + lru) + 3; // skip "nr_"
         |                               ~~~~~~~~~~~ ^ ~~~
>> fs/btrfs/delayed-ref.c:342:10: error: call to undeclared function 'rb_find_add_cached'; ISO C99 and later do not support implicit function declarations [-Wimplicit-function-declaration]
     342 |         exist = rb_find_add_cached(node, root, comp_refs_node);
         |                 ^
>> fs/btrfs/delayed-ref.c:342:8: error: incompatible integer to pointer conversion assigning to 'struct rb_node *' from 'int' [-Wint-conversion]
     342 |         exist = rb_find_add_cached(node, root, comp_refs_node);
         |               ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   1 warning and 2 errors generated.


vim +/rb_find_add_cached +342 fs/btrfs/delayed-ref.c

   334	
   335	static struct btrfs_delayed_ref_node* tree_insert(struct rb_root_cached *root,
   336			struct btrfs_delayed_ref_node *ins)
   337	{
   338		struct rb_node *node = &ins->ref_node;
   339		struct rb_node *exist;
   340		struct btrfs_delayed_ref_node *entry;
   341	
 > 342		exist = rb_find_add_cached(node, root, comp_refs_node);
   343		if (exist != NULL) {
   344			entry = rb_entry(exist, struct btrfs_delayed_ref_node, ref_node);
   345			return entry;
   346		}
   347		return NULL;
   348	}
   349	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

Re: [PATCH] btrfs: edits tree_insert() to use rb helpers

[kernel test robot]

Hi Roger,

kernel test robot noticed the following build errors:

[auto build test ERROR on kdave/for-next]
[also build test ERROR on linus/master v6.13-rc2 next-20241209]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Roger-L-Beckermeyer-III/btrfs-edits-tree_insert-to-use-rb-helpers/20241209-104108
base:   https://git.kernel.org/pub/scm/linux/kernel/git/kdave/linux.git for-next
patch link:    https://lore.kernel.org/r/5e023dcf8f086296da987f8ba2b43be0aca15b86.1733695544.git.beckerlee3%40gmail.com
patch subject: [PATCH] btrfs: edits tree_insert() to use rb helpers
config: x86_64-buildonly-randconfig-001-20241209 (https://download.01.org/0day-ci/archive/20241209/202412092033.josUXvY4-lkp@intel.com/config)
compiler: gcc-12 (Debian 12.2.0-14) 12.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20241209/202412092033.josUXvY4-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202412092033.josUXvY4-lkp@intel.com/

All errors (new ones prefixed by >>):

   fs/btrfs/delayed-ref.c: In function 'tree_insert':
>> fs/btrfs/delayed-ref.c:342:17: error: implicit declaration of function 'rb_find_add_cached'; did you mean 'rb_find_add_rcu'? [-Werror=implicit-function-declaration]
     342 |         exist = rb_find_add_cached(node, root, comp_refs_node);
         |                 ^~~~~~~~~~~~~~~~~~
         |                 rb_find_add_rcu
   fs/btrfs/delayed-ref.c:342:15: warning: assignment to 'struct rb_node *' from 'int' makes pointer from integer without a cast [-Wint-conversion]
     342 |         exist = rb_find_add_cached(node, root, comp_refs_node);
         |               ^
   cc1: some warnings being treated as errors


vim +342 fs/btrfs/delayed-ref.c

   334	
   335	static struct btrfs_delayed_ref_node* tree_insert(struct rb_root_cached *root,
   336			struct btrfs_delayed_ref_node *ins)
   337	{
   338		struct rb_node *node = &ins->ref_node;
   339		struct rb_node *exist;
   340		struct btrfs_delayed_ref_node *entry;
   341	
 > 342		exist = rb_find_add_cached(node, root, comp_refs_node);
   343		if (exist != NULL) {
   344			entry = rb_entry(exist, struct btrfs_delayed_ref_node, ref_node);
   345			return entry;
   346		}
   347		return NULL;
   348	}
   349	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

Re: [PATCH] btrfs: edits tree_insert() to use rb helpers

[Filipe Manana]

On Sun, Dec 8, 2024 at 10:39 PM Roger L. Beckermeyer III
<beckerlee3@gmail.com> wrote:
>
> Edits tree_insert() to use rb_find_add_cached(). Also adds a
> comparison function for use in rb_find_add_cached() to compare.
>
> Reviewed-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
> Tested-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
> Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
> ---
>  fs/btrfs/delayed-ref.c | 43 +++++++++++++++++++++---------------------
>  1 file changed, 21 insertions(+), 22 deletions(-)
>
> diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c
> index 30f7079fa28e..d77ac8d05b2a 100644
> --- a/fs/btrfs/delayed-ref.c
> +++ b/fs/btrfs/delayed-ref.c
> @@ -317,34 +317,33 @@ static int comp_refs(struct btrfs_delayed_ref_node *ref1,
>         return 0;
>  }
>
> +static int comp_refs_node(struct rb_node *node, const struct rb_node *node2)
> +{
> +       struct btrfs_delayed_ref_node *ref1;
> +       struct btrfs_delayed_ref_node *ref2;
> +
> +       ref1 = rb_entry(node, struct btrfs_delayed_ref_node, ref_node);
> +       ref2 = rb_entry(node2, struct btrfs_delayed_ref_node, ref_node);
> +
> +       bool check_seq = true;
> +       int ret;

Please don't use this style of declaring variables in the middle of the code.
The style we use is to declare them at the top of a scope.

> +
> +       ret = comp_refs(ref1, ref2, check_seq);
> +       return ret;

For this just do:

return comp_refs(ref1, ref2, check_seq);

> +}
> +
>  static struct btrfs_delayed_ref_node* tree_insert(struct rb_root_cached *root,
>                 struct btrfs_delayed_ref_node *ins)
>  {
> -       struct rb_node **p = &root->rb_root.rb_node;
>         struct rb_node *node = &ins->ref_node;
> -       struct rb_node *parent_node = NULL;
> +       struct rb_node *exist;
>         struct btrfs_delayed_ref_node *entry;
> -       bool leftmost = true;
> -
> -       while (*p) {
> -               int comp;
> -
> -               parent_node = *p;
> -               entry = rb_entry(parent_node, struct btrfs_delayed_ref_node,
> -                                ref_node);
> -               comp = comp_refs(ins, entry, true);
> -               if (comp < 0) {
> -                       p = &(*p)->rb_left;
> -               } else if (comp > 0) {
> -                       p = &(*p)->rb_right;
> -                       leftmost = false;
> -               } else {
> -                       return entry;
> -               }
> -       }
>
> -       rb_link_node(node, parent_node, p);
> -       rb_insert_color_cached(node, root, leftmost);
> +       exist = rb_find_add_cached(node, root, comp_refs_node);
> +       if (exist != NULL) {
> +               entry = rb_entry(exist, struct btrfs_delayed_ref_node, ref_node);
> +               return entry;

return rb_entry(exist, struct btrfs_delayed_ref_node, ref_node);

Thanks.

> +       }
>         return NULL;
>  }
>
> --
> 2.45.2
>
>

Re: [PATCH] btrfs: edits tree_insert() to use rb helpers

[kernel test robot]

Hi Roger,

kernel test robot noticed the following build errors:

[auto build test ERROR on kdave/for-next]
[also build test ERROR on linus/master v6.13-rc2 next-20241211]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Roger-L-Beckermeyer-III/btrfs-edits-tree_insert-to-use-rb-helpers/20241209-104108
base:   https://git.kernel.org/pub/scm/linux/kernel/git/kdave/linux.git for-next
patch link:    https://lore.kernel.org/r/5e023dcf8f086296da987f8ba2b43be0aca15b86.1733695544.git.beckerlee3%40gmail.com
patch subject: [PATCH] btrfs: edits tree_insert() to use rb helpers
config: s390-defconfig (https://download.01.org/0day-ci/archive/20241212/202412120640.485KsaTz-lkp@intel.com/config)
compiler: clang version 15.0.7 (https://github.com/llvm/llvm-project 8dfdcc7b7bf66834a761bd8de445840ef68e4d1a)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20241212/202412120640.485KsaTz-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202412120640.485KsaTz-lkp@intel.com/

All errors (new ones prefixed by >>):

>> fs/btrfs/delayed-ref.c:342:10: error: call to undeclared function 'rb_find_add_cached'; ISO C99 and later do not support implicit function declarations [-Werror,-Wimplicit-function-declaration]
           exist = rb_find_add_cached(node, root, comp_refs_node);
                   ^
   fs/btrfs/delayed-ref.c:342:8: error: incompatible integer to pointer conversion assigning to 'struct rb_node *' from 'int' [-Wint-conversion]
           exist = rb_find_add_cached(node, root, comp_refs_node);
                 ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   2 errors generated.


vim +/rb_find_add_cached +342 fs/btrfs/delayed-ref.c

   334	
   335	static struct btrfs_delayed_ref_node* tree_insert(struct rb_root_cached *root,
   336			struct btrfs_delayed_ref_node *ins)
   337	{
   338		struct rb_node *node = &ins->ref_node;
   339		struct rb_node *exist;
   340		struct btrfs_delayed_ref_node *entry;
   341	
 > 342		exist = rb_find_add_cached(node, root, comp_refs_node);
   343		if (exist != NULL) {
   344			entry = rb_entry(exist, struct btrfs_delayed_ref_node, ref_node);
   345			return entry;
   346		}
   347		return NULL;
   348	}
   349	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

Re: [PATCHi 0/6] reduce boilerplate code within btrfs

[Qu Wenruo]

在 2024/12/9 09:07, Roger L. Beckermeyer III 写道:
> The goal of this patch series is to reduce boilerplate code
> within btrfs. To accomplish this rb_find_add_cached() was added
> to linux/include/rbtree.h. Any replaceable functions were then
> replaced within btrfs.

Please format the patchset into a series.
By default git-format-patch will make them into a series.

Your current way makes every patch into a dedicate one without proper
sequence, thus LKP is reporting tons of errors.


And I'm not sure if you're the one submitting PR in the btrfs/linux project.
If so, please do not, currently the PR is mostly for CI purposes.

Please check the btrfs workflow project to get familiar with the btrfs
workflow:

https://github.com/btrfs/btrfs-workflow


Finally, if you're the author, please drop your self-reviewed-by, it
makes no sense, nor the tested-by tags.
Every patch submitted to the ML should be at least tested with a fstests
run.

Thanks,
Qu

>
> Roger L. Beckermeyer III (6):
>    rbtree: add rb_find_add_cached() to rbtree.h
>    btrfs: edit btrfs_add_block_group_cache() to use rb helper
>    btrfs: edit prelim_ref_insert() to use rb helpers
>    btrfs: edit __btrfs_add_delayed_item() to use rb helper
>    btrfs: edit btrfs_add_chunk_map() to use rb helpers
>    btrfs: edits tree_insert() to use rb helpers
>
>   fs/btrfs/backref.c       | 71 ++++++++++++++++++++--------------------
>   fs/btrfs/block-group.c   | 40 ++++++++++------------
>   fs/btrfs/delayed-inode.c | 40 +++++++++-------------
>   fs/btrfs/delayed-ref.c   | 43 ++++++++++++------------
>   fs/btrfs/volumes.c       | 39 ++++++++++------------
>   include/linux/rbtree.h   | 37 +++++++++++++++++++++
>   6 files changed, 145 insertions(+), 125 deletions(-)
>

Re: [PATCHi 0/6] reduce boilerplate code within btrfs

[Josef Bacik]

On Sun, Dec 08, 2024 at 04:37:59PM -0600, Roger L. Beckermeyer III wrote:
> The goal of this patch series is to reduce boilerplate code
> within btrfs. To accomplish this rb_find_add_cached() was added
> to linux/include/rbtree.h. Any replaceable functions were then 
> replaced within btrfs.
> 

Just a few overall comments on the whole series:

1) Make sure you fix up all the kbuilder test bot things.
2) Don't add "Reviewed-by" or "Tested-by" tags to your own patches, that's for
   other people to do.  Generally we use "Tested-by" for people who have tested
   a specific bug fix.

Thanks,

Josef

[PATCH 0/6] reduce boilerplate code within btrfs

[Roger L. Beckermeyer III]

The goal of this patch series is to reduce boilerplate code
within btrfs. To accomplish this rb_find_add_cached() was added
to linux/include/rbtree.h. Any replaceable functions were then 
replaced within btrfs.

Roger L. Beckermeyer III (6):
  rbtree: add rb_find_add_cached() to rbtree.h
  btrfs: edit btrfs_add_block_group_cache() to use rb helper
  btrfs: edit prelim_ref_insert() to use rb helpers
  btrfs: edit __btrfs_add_delayed_item() to use rb helper
  btrfs: edit btrfs_add_chunk_map() to use rb helpers
  btrfs: edit tree_insert() to use rb helpers

 fs/btrfs/backref.c       | 71 ++++++++++++++++++++--------------------
 fs/btrfs/block-group.c   | 40 ++++++++++------------
 fs/btrfs/delayed-inode.c | 40 +++++++++-------------
 fs/btrfs/delayed-ref.c   | 39 +++++++++-------------
 fs/btrfs/volumes.c       | 39 ++++++++++------------
 include/linux/rbtree.h   | 37 +++++++++++++++++++++
 6 files changed, 140 insertions(+), 126 deletions(-)

-- 
2.45.2

[PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h

[Roger L. Beckermeyer III]

Adds rb_find_add_cached() as a helper function for use with
red-black trees. Used in btrfs to reduce boilerplate code.

Reported-by: kernel test robot <lkp@intel.com>
Closes: https://lore.kernel.org/oe-kbuild-all/202412092033.josUXvY4-lkp@intel.com/
Closes: https://lore.kernel.org/oe-kbuild-all/202412091004.4vQ7P5Kl-lkp@intel.com/
Closes: https://lore.kernel.org/oe-kbuild-all/202412090944.g3jpT1Cz-lkp@intel.com/
Closes: https://lore.kernel.org/oe-kbuild-all/202412090919.RdI1OMQg-lkp@intel.com/
Closes: https://lore.kernel.org/oe-kbuild-all/202412090922.LHCgRc17-lkp@intel.com/
Closes: https://lore.kernel.org/oe-kbuild-all/202412091036.JGaCqbvL-lkp@intel.com/
Closes: https://lore.kernel.org/oe-kbuild-all/202412090921.E0n0Ioce-lkp@intel.com/
Closes: https://lore.kernel.org/oe-kbuild-all/202412090958.CtUdYRwP-lkp@intel.com/
Closes: https://lore.kernel.org/oe-kbuild-all/202412090922.Cg7LuOhS-lkp@intel.com/
Closes: https://lore.kernel.org/oe-kbuild-all/202412090910.F5gin2Tv-lkp@intel.com/
Suggested-by: Josef Bacik <josef@toxicpanda.com>
Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
---
 include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++
 1 file changed, 37 insertions(+)

diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 7c173aa64e1e..0d4444c0cfb3 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -210,6 +210,43 @@ rb_add(struct rb_node *node, struct rb_root *tree,
 	rb_insert_color(node, tree);
 }
 
+/**
+ * rb_find_add_cached() - find equivalent @node in @tree, or add @node
+ * @node: node to look-for / insert
+ * @tree: tree to search / modify
+ * @cmp: operator defining the node order
+ *
+ * Returns the rb_node matching @node, or NULL when no match is found and @node
+ * is inserted.
+ */
+static __always_inline struct rb_node *
+rb_find_add_cached(struct rb_node *node, struct rb_root_cached *tree,
+	    int (*cmp)(struct rb_node *, const struct rb_node *))
+{
+	bool leftmost = true;
+	struct rb_node **link = &tree->rb_root.rb_node;
+	struct rb_node *parent = NULL;
+	int c;
+
+	while (*link) {
+		parent = *link;
+		c = cmp(node, parent);
+
+		if (c < 0) {
+			link = &parent->rb_left;
+		} else if (c > 0) {
+			link = &parent->rb_right;
+			leftmost = false;
+		} else {
+			return parent;
+		}
+	}
+
+	rb_link_node(node, parent, link);
+	rb_insert_color_cached(node, tree, leftmost);
+	return NULL;
+}
+
 /**
  * rb_find_add() - find equivalent @node in @tree, or add @node
  * @node: node to look-for / insert
-- 
2.45.2

Re: [PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h

[Johannes Thumshirn]

On 10.12.24 20:07, Roger L. Beckermeyer III wrote:
> Adds rb_find_add_cached() as a helper function for use with
> red-black trees. Used in btrfs to reduce boilerplate code.
> 
> Reported-by: kernel test robot <lkp@intel.com>
> Closes: https://lore.kernel.org/oe-kbuild-all/202412092033.josUXvY4-lkp@intel.com/
> Closes: https://lore.kernel.org/oe-kbuild-all/202412091004.4vQ7P5Kl-lkp@intel.com/
> Closes: https://lore.kernel.org/oe-kbuild-all/202412090944.g3jpT1Cz-lkp@intel.com/
> Closes: https://lore.kernel.org/oe-kbuild-all/202412090919.RdI1OMQg-lkp@intel.com/
> Closes: https://lore.kernel.org/oe-kbuild-all/202412090922.LHCgRc17-lkp@intel.com/
> Closes: https://lore.kernel.org/oe-kbuild-all/202412091036.JGaCqbvL-lkp@intel.com/
> Closes: https://lore.kernel.org/oe-kbuild-all/202412090921.E0n0Ioce-lkp@intel.com/
> Closes: https://lore.kernel.org/oe-kbuild-all/202412090958.CtUdYRwP-lkp@intel.com/
> Closes: https://lore.kernel.org/oe-kbuild-all/202412090922.Cg7LuOhS-lkp@intel.com/
> Closes: https://lore.kernel.org/oe-kbuild-all/202412090910.F5gin2Tv-lkp@intel.com/

Don't add the Closes: tag here. It's a change between v1 and v2 which 
does not need to go to the git history.

> Suggested-by: Josef Bacik <josef@toxicpanda.com>
> Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>

[PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h

[Roger L. Beckermeyer III]

Adds rb_find_add_cached() as a helper function for use with
red-black trees. Used in btrfs to reduce boilerplate code.

Suggested-by: Josef Bacik <josef@toxicpanda.com>
Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
---
 include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++
 1 file changed, 37 insertions(+)

diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 7c173aa64e1e..0d4444c0cfb3 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -210,6 +210,43 @@ rb_add(struct rb_node *node, struct rb_root *tree,
 	rb_insert_color(node, tree);
 }
 
+/**
+ * rb_find_add_cached() - find equivalent @node in @tree, or add @node
+ * @node: node to look-for / insert
+ * @tree: tree to search / modify
+ * @cmp: operator defining the node order
+ *
+ * Returns the rb_node matching @node, or NULL when no match is found and @node
+ * is inserted.
+ */
+static __always_inline struct rb_node *
+rb_find_add_cached(struct rb_node *node, struct rb_root_cached *tree,
+	    int (*cmp)(struct rb_node *, const struct rb_node *))
+{
+	bool leftmost = true;
+	struct rb_node **link = &tree->rb_root.rb_node;
+	struct rb_node *parent = NULL;
+	int c;
+
+	while (*link) {
+		parent = *link;
+		c = cmp(node, parent);
+
+		if (c < 0) {
+			link = &parent->rb_left;
+		} else if (c > 0) {
+			link = &parent->rb_right;
+			leftmost = false;
+		} else {
+			return parent;
+		}
+	}
+
+	rb_link_node(node, parent, link);
+	rb_insert_color_cached(node, tree, leftmost);
+	return NULL;
+}
+
 /**
  * rb_find_add() - find equivalent @node in @tree, or add @node
  * @node: node to look-for / insert
-- 
2.45.2

Re: [PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h

[David Sterba]

On Tue, Dec 10, 2024 at 01:06:07PM -0600, Roger L. Beckermeyer III wrote:
> Adds rb_find_add_cached() as a helper function for use with
> red-black trees. Used in btrfs to reduce boilerplate code.
> 
> Reported-by: kernel test robot <lkp@intel.com>
> Closes: https://lore.kernel.org/oe-kbuild-all/202412092033.josUXvY4-lkp@intel.com/
> Closes: https://lore.kernel.org/oe-kbuild-all/202412091004.4vQ7P5Kl-lkp@intel.com/
> Closes: https://lore.kernel.org/oe-kbuild-all/202412090944.g3jpT1Cz-lkp@intel.com/
> Closes: https://lore.kernel.org/oe-kbuild-all/202412090919.RdI1OMQg-lkp@intel.com/
> Closes: https://lore.kernel.org/oe-kbuild-all/202412090922.LHCgRc17-lkp@intel.com/
> Closes: https://lore.kernel.org/oe-kbuild-all/202412091036.JGaCqbvL-lkp@intel.com/
> Closes: https://lore.kernel.org/oe-kbuild-all/202412090921.E0n0Ioce-lkp@intel.com/
> Closes: https://lore.kernel.org/oe-kbuild-all/202412090958.CtUdYRwP-lkp@intel.com/
> Closes: https://lore.kernel.org/oe-kbuild-all/202412090922.Cg7LuOhS-lkp@intel.com/
> Closes: https://lore.kernel.org/oe-kbuild-all/202412090910.F5gin2Tv-lkp@intel.com/
> Suggested-by: Josef Bacik <josef@toxicpanda.com>
> Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
> ---
>  include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++

This is generic code and you need to CC the right people to get their
ack and reviewed-by. Alternatively we can have our own copy in
fs/btrfs/misc.h and then move it to the generic code.

[PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h

[Roger L. Beckermeyer III]

Adds rb_find_add_cached() as a helper function for use with
red-black trees. Used in btrfs to reduce boilerplate code.

Suggested-by: Josef Bacik <josef@toxicpanda.com>
Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
---
 include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++
 1 file changed, 37 insertions(+)

diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 7c173aa64e1e..0d4444c0cfb3 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -210,6 +210,43 @@ rb_add(struct rb_node *node, struct rb_root *tree,
 	rb_insert_color(node, tree);
 }
 
+/**
+ * rb_find_add_cached() - find equivalent @node in @tree, or add @node
+ * @node: node to look-for / insert
+ * @tree: tree to search / modify
+ * @cmp: operator defining the node order
+ *
+ * Returns the rb_node matching @node, or NULL when no match is found and @node
+ * is inserted.
+ */
+static __always_inline struct rb_node *
+rb_find_add_cached(struct rb_node *node, struct rb_root_cached *tree,
+	    int (*cmp)(struct rb_node *, const struct rb_node *))
+{
+	bool leftmost = true;
+	struct rb_node **link = &tree->rb_root.rb_node;
+	struct rb_node *parent = NULL;
+	int c;
+
+	while (*link) {
+		parent = *link;
+		c = cmp(node, parent);
+
+		if (c < 0) {
+			link = &parent->rb_left;
+		} else if (c > 0) {
+			link = &parent->rb_right;
+			leftmost = false;
+		} else {
+			return parent;
+		}
+	}
+
+	rb_link_node(node, parent, link);
+	rb_insert_color_cached(node, tree, leftmost);
+	return NULL;
+}
+
 /**
  * rb_find_add() - find equivalent @node in @tree, or add @node
  * @node: node to look-for / insert
-- 
2.45.2

Re: [PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h

[Qu Wenruo]

在 2024/12/13 03:16, Roger L. Beckermeyer III 写道:
> Adds rb_find_add_cached() as a helper function for use with
> red-black trees. Used in btrfs to reduce boilerplate code.

I won't call it boilerplate code though, it's just to utilize the cached
rb tree feature as an optimization.

And since rbtree is a tree-wide infrastructure, you need to be more
persuasive to add a new interface.

Yes, btrfs is utilizing this cached rb tree, but since you're adding a
new tree-wide interface, it will be much better to find another
driver/subsystem that can benefit from the new interface.

>
> Suggested-by: Josef Bacik <josef@toxicpanda.com>
> Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
> ---
>   include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++
>   1 file changed, 37 insertions(+)
>
> diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
> index 7c173aa64e1e..0d4444c0cfb3 100644
> --- a/include/linux/rbtree.h
> +++ b/include/linux/rbtree.h
> @@ -210,6 +210,43 @@ rb_add(struct rb_node *node, struct rb_root *tree,
>   	rb_insert_color(node, tree);
>   }
>
> +/**
> + * rb_find_add_cached() - find equivalent @node in @tree, or add @node
> + * @node: node to look-for / insert
> + * @tree: tree to search / modify
> + * @cmp: operator defining the node order
> + *
> + * Returns the rb_node matching @node, or NULL when no match is found and @node
> + * is inserted.
> + */
> +static __always_inline struct rb_node *
> +rb_find_add_cached(struct rb_node *node, struct rb_root_cached *tree,
> +	    int (*cmp)(struct rb_node *, const struct rb_node *))

This function is almost the same as rb_add_cached(), the only difference
is the extra handling for the cmp function returning 0.

So I'm wondering if it's possible to enhance rb_add_cached(), or even
refactor it so there can be a shared core function and rb_add_cached()
and rb_find_add_cached() can reuse the same function.

Thanks,
Qu

> +{
> +	bool leftmost = true;
> +	struct rb_node **link = &tree->rb_root.rb_node;
> +	struct rb_node *parent = NULL;
> +	int c;
> +
> +	while (*link) {
> +		parent = *link;
> +		c = cmp(node, parent);
> +
> +		if (c < 0) {
> +			link = &parent->rb_left;
> +		} else if (c > 0) {
> +			link = &parent->rb_right;
> +			leftmost = false;
> +		} else {
> +			return parent;
> +		}
> +	}
> +
> +	rb_link_node(node, parent, link);
> +	rb_insert_color_cached(node, tree, leftmost);
> +	return NULL;
> +}
> +
>   /**
>    * rb_find_add() - find equivalent @node in @tree, or add @node
>    * @node: node to look-for / insert

Re: [PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h

[Peter Zijlstra]

On Fri, Dec 13, 2024 at 05:51:44PM +1030, Qu Wenruo wrote:
> 
> 
> 在 2024/12/13 03:16, Roger L. Beckermeyer III 写道:
> > Adds rb_find_add_cached() as a helper function for use with
> > red-black trees. Used in btrfs to reduce boilerplate code.
> 
> I won't call it boilerplate code though, it's just to utilize the cached
> rb tree feature as an optimization.

Nah, all this is boilerplate :-)

> > 
> > Suggested-by: Josef Bacik <josef@toxicpanda.com>
> > Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
> > ---
> >   include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++
> >   1 file changed, 37 insertions(+)
> > 
> > diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
> > index 7c173aa64e1e..0d4444c0cfb3 100644
> > --- a/include/linux/rbtree.h
> > +++ b/include/linux/rbtree.h
> > @@ -210,6 +210,43 @@ rb_add(struct rb_node *node, struct rb_root *tree,
> >   	rb_insert_color(node, tree);
> >   }
> > 
> > +/**
> > + * rb_find_add_cached() - find equivalent @node in @tree, or add @node
> > + * @node: node to look-for / insert
> > + * @tree: tree to search / modify
> > + * @cmp: operator defining the node order
> > + *
> > + * Returns the rb_node matching @node, or NULL when no match is found and @node
> > + * is inserted.
> > + */
> > +static __always_inline struct rb_node *
> > +rb_find_add_cached(struct rb_node *node, struct rb_root_cached *tree,
> > +	    int (*cmp)(struct rb_node *, const struct rb_node *))
> 
> This function is almost the same as rb_add_cached(), the only difference
> is the extra handling for the cmp function returning 0.
> 
> So I'm wondering if it's possible to enhance rb_add_cached(), or even
> refactor it so there can be a shared core function and rb_add_cached()
> and rb_find_add_cached() can reuse the same function.

Nope, rb_add_cached() can add multiple entries with the same key,
rb_find_add() cannot.

Also, note that all these things are effectively 'templates', they
generate code at the call site. The cmp() function as required for
find_add() is a tri-state return and generates more logic than the
binary less() required for add().

Re: [PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h

[Peter Zijlstra]

On Thu, Dec 12, 2024 at 10:46:18AM -0600, Roger L. Beckermeyer III wrote:
> Adds rb_find_add_cached() as a helper function for use with
> red-black trees. Used in btrfs to reduce boilerplate code.
> 
> Suggested-by: Josef Bacik <josef@toxicpanda.com>
> Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>

Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>

> ---
>  include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++
>  1 file changed, 37 insertions(+)
> 
> diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
> index 7c173aa64e1e..0d4444c0cfb3 100644
> --- a/include/linux/rbtree.h
> +++ b/include/linux/rbtree.h
> @@ -210,6 +210,43 @@ rb_add(struct rb_node *node, struct rb_root *tree,
>  	rb_insert_color(node, tree);
>  }
>  
> +/**
> + * rb_find_add_cached() - find equivalent @node in @tree, or add @node
> + * @node: node to look-for / insert
> + * @tree: tree to search / modify
> + * @cmp: operator defining the node order
> + *
> + * Returns the rb_node matching @node, or NULL when no match is found and @node
> + * is inserted.
> + */
> +static __always_inline struct rb_node *
> +rb_find_add_cached(struct rb_node *node, struct rb_root_cached *tree,
> +	    int (*cmp)(struct rb_node *, const struct rb_node *))
> +{
> +	bool leftmost = true;
> +	struct rb_node **link = &tree->rb_root.rb_node;
> +	struct rb_node *parent = NULL;
> +	int c;
> +
> +	while (*link) {
> +		parent = *link;
> +		c = cmp(node, parent);
> +
> +		if (c < 0) {
> +			link = &parent->rb_left;
> +		} else if (c > 0) {
> +			link = &parent->rb_right;
> +			leftmost = false;
> +		} else {
> +			return parent;
> +		}
> +	}
> +
> +	rb_link_node(node, parent, link);
> +	rb_insert_color_cached(node, tree, leftmost);
> +	return NULL;
> +}
> +
>  /**
>   * rb_find_add() - find equivalent @node in @tree, or add @node
>   * @node: node to look-for / insert
> -- 
> 2.45.2
> 

Re: [PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h

[Qu Wenruo]

在 2024/12/13 19:36, Peter Zijlstra 写道:
> On Thu, Dec 12, 2024 at 10:46:18AM -0600, Roger L. Beckermeyer III wrote:
>> Adds rb_find_add_cached() as a helper function for use with
>> red-black trees. Used in btrfs to reduce boilerplate code.
>>
>> Suggested-by: Josef Bacik <josef@toxicpanda.com>
>> Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
>
> Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>

I guess it's fine to merge this change through btrfs tree?


Just curious about the existing cmp() and less() functions, as they only
accept the exist node as const.

I'm wondering if this is intentional to allow the less/cmp() functions
to modify the new node if needed.
As I normally assume such cmp()/less() should never touch any node nor
its entries.

Thanks,
Qu

>
>> ---
>>   include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++
>>   1 file changed, 37 insertions(+)
>>
>> diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
>> index 7c173aa64e1e..0d4444c0cfb3 100644
>> --- a/include/linux/rbtree.h
>> +++ b/include/linux/rbtree.h
>> @@ -210,6 +210,43 @@ rb_add(struct rb_node *node, struct rb_root *tree,
>>   	rb_insert_color(node, tree);
>>   }
>>
>> +/**
>> + * rb_find_add_cached() - find equivalent @node in @tree, or add @node
>> + * @node: node to look-for / insert
>> + * @tree: tree to search / modify
>> + * @cmp: operator defining the node order
>> + *
>> + * Returns the rb_node matching @node, or NULL when no match is found and @node
>> + * is inserted.
>> + */
>> +static __always_inline struct rb_node *
>> +rb_find_add_cached(struct rb_node *node, struct rb_root_cached *tree,
>> +	    int (*cmp)(struct rb_node *, const struct rb_node *))
>> +{
>> +	bool leftmost = true;
>> +	struct rb_node **link = &tree->rb_root.rb_node;
>> +	struct rb_node *parent = NULL;
>> +	int c;
>> +
>> +	while (*link) {
>> +		parent = *link;
>> +		c = cmp(node, parent);
>> +
>> +		if (c < 0) {
>> +			link = &parent->rb_left;
>> +		} else if (c > 0) {
>> +			link = &parent->rb_right;
>> +			leftmost = false;
>> +		} else {
>> +			return parent;
>> +		}
>> +	}
>> +
>> +	rb_link_node(node, parent, link);
>> +	rb_insert_color_cached(node, tree, leftmost);
>> +	return NULL;
>> +}
>> +
>>   /**
>>    * rb_find_add() - find equivalent @node in @tree, or add @node
>>    * @node: node to look-for / insert
>> --
>> 2.45.2
>>
>

Re: [PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h

[Peter Zijlstra]

On Tue, Dec 17, 2024 at 08:43:26AM +1030, Qu Wenruo wrote:
> 
> 
> 在 2024/12/13 19:36, Peter Zijlstra 写道:
> > On Thu, Dec 12, 2024 at 10:46:18AM -0600, Roger L. Beckermeyer III wrote:
> > > Adds rb_find_add_cached() as a helper function for use with
> > > red-black trees. Used in btrfs to reduce boilerplate code.
> > > 
> > > Suggested-by: Josef Bacik <josef@toxicpanda.com>
> > > Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
> > 
> > Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> 
> I guess it's fine to merge this change through btrfs tree?

Yeah, I think so. I don't think there's anything else pending for this
file -- its not touched much.

> 
> Just curious about the existing cmp() and less() functions, as they only
> accept the exist node as const.
> 
> I'm wondering if this is intentional to allow the less/cmp() functions
> to modify the new node if needed.
> As I normally assume such cmp()/less() should never touch any node nor
> its entries.

Oh yeah, they probably should not. I think it's just because the
callchain as a whole does not have const on the new node (for obvious
raisins), and I failed to put it on for the comparators.

You could add it (and fix up the whole tree) and see if anything comes
apart.

Re: [PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h

[Qu Wenruo]

在 2024/12/17 08:52, Peter Zijlstra 写道:
> On Tue, Dec 17, 2024 at 08:43:26AM +1030, Qu Wenruo wrote:
>>
>>
>> 在 2024/12/13 19:36, Peter Zijlstra 写道:
>>> On Thu, Dec 12, 2024 at 10:46:18AM -0600, Roger L. Beckermeyer III wrote:
>>>> Adds rb_find_add_cached() as a helper function for use with
>>>> red-black trees. Used in btrfs to reduce boilerplate code.
>>>>
>>>> Suggested-by: Josef Bacik <josef@toxicpanda.com>
>>>> Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
>>>
>>> Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
>>
>> I guess it's fine to merge this change through btrfs tree?
> 
> Yeah, I think so. I don't think there's anything else pending for this
> file -- its not touched much.
> 
>>
>> Just curious about the existing cmp() and less() functions, as they only
>> accept the exist node as const.
>>
>> I'm wondering if this is intentional to allow the less/cmp() functions
>> to modify the new node if needed.
>> As I normally assume such cmp()/less() should never touch any node nor
>> its entries.
> 
> Oh yeah, they probably should not. I think it's just because the
> callchain as a whole does not have const on the new node (for obvious
> raisins), and I failed to put it on for the comparators.
> 
> You could add it (and fix up the whole tree) and see if anything comes
> apart.
> 
Thanks for confirming this.

I'll make the cmp() for the new helper to accept all const parameter, 
and give a try to do a tree-wide cleanup to make existing cmp/less() to 
accept all const parameters. (pretty sure a lot of things will fall 
apart though).

Thanks,
Qu

[PATCH 2/6] btrfs: edit btrfs_add_block_group_cache() to use rb helper

[Roger L. Beckermeyer III]

Edits fs/btrfs/block-group.c to use rb_find_add_cached(),
also adds a comparison function, btrfs_add_block_blkgrp_cmp(),
for use with rb_find_add_cached().

Suggested-by: Josef Bacik <josef@toxicpanda.com>
Reviewed-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
---
 fs/btrfs/block-group.c | 40 +++++++++++++++++-----------------------
 1 file changed, 17 insertions(+), 23 deletions(-)

diff --git a/fs/btrfs/block-group.c b/fs/btrfs/block-group.c
index 5be029734cfa..ccff051de43a 100644
--- a/fs/btrfs/block-group.c
+++ b/fs/btrfs/block-group.c
@@ -173,40 +173,34 @@ void btrfs_put_block_group(struct btrfs_block_group *cache)
 	}
 }
 
+static int btrfs_add_blkgrp_cmp(struct rb_node *new, const struct rb_node *exist)
+{
+	struct btrfs_block_group *cmp1 = rb_entry(new, struct btrfs_block_group, cache_node);
+	struct btrfs_block_group *cmp2 = rb_entry(exist, struct btrfs_block_group, cache_node);
+
+	if (cmp1->start < cmp2->start)
+		return -1;
+	if (cmp1->start > cmp2->start)
+		return 1;
+	return 0;
+}
+
 /*
  * This adds the block group to the fs_info rb tree for the block group cache
  */
 static int btrfs_add_block_group_cache(struct btrfs_fs_info *info,
 				       struct btrfs_block_group *block_group)
 {
-	struct rb_node **p;
-	struct rb_node *parent = NULL;
-	struct btrfs_block_group *cache;
-	bool leftmost = true;
+	struct rb_node *exist;
 
 	ASSERT(block_group->length != 0);
 
 	write_lock(&info->block_group_cache_lock);
-	p = &info->block_group_cache_tree.rb_root.rb_node;
-
-	while (*p) {
-		parent = *p;
-		cache = rb_entry(parent, struct btrfs_block_group, cache_node);
-		if (block_group->start < cache->start) {
-			p = &(*p)->rb_left;
-		} else if (block_group->start > cache->start) {
-			p = &(*p)->rb_right;
-			leftmost = false;
-		} else {
-			write_unlock(&info->block_group_cache_lock);
-			return -EEXIST;
-		}
-	}
-
-	rb_link_node(&block_group->cache_node, parent, p);
-	rb_insert_color_cached(&block_group->cache_node,
-			       &info->block_group_cache_tree, leftmost);
 
+	exist = rb_find_add_cached(&block_group->cache_node,
+			&info->block_group_cache_tree, btrfs_add_blkgrp_cmp);
+	if (exist != NULL)
+		return -EEXIST;
 	write_unlock(&info->block_group_cache_lock);
 
 	return 0;
-- 
2.45.2

Re: [PATCH 2/6] btrfs: edit btrfs_add_block_group_cache() to use rb helper

[David Sterba]

On Tue, Dec 10, 2024 at 01:06:08PM -0600, Roger L. Beckermeyer III wrote:
> Edits fs/btrfs/block-group.c to use rb_find_add_cached(),

Please don't use 'edit' for changelogs, 'update to use' or 'use'
describes it better.

> also adds a comparison function, btrfs_add_block_blkgrp_cmp(),
> for use with rb_find_add_cached().
> 
> Suggested-by: Josef Bacik <josef@toxicpanda.com>
> Reviewed-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
> Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
> ---
>  fs/btrfs/block-group.c | 40 +++++++++++++++++-----------------------
>  1 file changed, 17 insertions(+), 23 deletions(-)
> 
> diff --git a/fs/btrfs/block-group.c b/fs/btrfs/block-group.c
> index 5be029734cfa..ccff051de43a 100644
> --- a/fs/btrfs/block-group.c
> +++ b/fs/btrfs/block-group.c
> @@ -173,40 +173,34 @@ void btrfs_put_block_group(struct btrfs_block_group *cache)
>  	}
>  }
>  
> +static int btrfs_add_blkgrp_cmp(struct rb_node *new, const struct rb_node *exist)

This is a comparator so 'add' is confusing here, so 'btrfs_bg_start_cmp'
for exmample.

> +{
> +	struct btrfs_block_group *cmp1 = rb_entry(new, struct btrfs_block_group, cache_node);
> +	struct btrfs_block_group *cmp2 = rb_entry(exist, struct btrfs_block_group, cache_node);

The types don't match, 'exist' is const.

> +
> +	if (cmp1->start < cmp2->start)
> +		return -1;
> +	if (cmp1->start > cmp2->start)
> +		return 1;
> +	return 0;
> +}

Re: [PATCH 2/6] btrfs: edit btrfs_add_block_group_cache() to use rb helper

[David Sterba]

On Tue, Dec 10, 2024 at 01:06:08PM -0600, Roger L. Beckermeyer III wrote:
> +	exist = rb_find_add_cached(&block_group->cache_node,
> +			&info->block_group_cache_tree, btrfs_add_blkgrp_cmp);
> +	if (exist != NULL)

For pointer checks you can use the shorter form 'if (exist)'

> +		return -EEXIST;
>  	write_unlock(&info->block_group_cache_lock);
>  
>  	return 0;
> -- 
> 2.45.2
> 

[PATCH 3/6] btrfs: edit prelim_ref_insert() to use rb helpers

[Roger L. Beckermeyer III]

This commit edits prelim_ref_insert() in fs/btrfs/backref.c to use
rb_find_add_cached(). It also adds a comparison function for use with
rb_find_add_cached().

Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
---
 fs/btrfs/backref.c | 71 +++++++++++++++++++++++-----------------------
 1 file changed, 36 insertions(+), 35 deletions(-)

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 6d9f39c1d89c..fcbcfce0f93a 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -250,6 +250,17 @@ static int prelim_ref_compare(const struct prelim_ref *ref1,
 	return 0;
 }
 
+static int prelim_ref_cmp(struct rb_node *node, const struct rb_node *exist)
+{
+	int result;
+	struct prelim_ref *ref1 = rb_entry(node, struct prelim_ref, rbnode);
+	struct prelim_ref *ref2 = rb_entry(exist, struct prelim_ref, rbnode);
+
+	result = prelim_ref_compare(ref1, ref2);
+
+	return result;
+}
+
 static void update_share_count(struct share_check *sc, int oldcount,
 			       int newcount, const struct prelim_ref *newref)
 {
@@ -281,52 +292,42 @@ static void prelim_ref_insert(const struct btrfs_fs_info *fs_info,
 	struct rb_node **p;
 	struct rb_node *parent = NULL;
 	struct prelim_ref *ref;
-	int result;
-	bool leftmost = true;
+	struct rb_node *exist;
 
 	root = &preftree->root;
 	p = &root->rb_root.rb_node;
+	parent = *p;
+	ref = rb_entry(parent, struct prelim_ref, rbnode);
 
-	while (*p) {
-		parent = *p;
-		ref = rb_entry(parent, struct prelim_ref, rbnode);
-		result = prelim_ref_compare(ref, newref);
-		if (result < 0) {
-			p = &(*p)->rb_left;
-		} else if (result > 0) {
-			p = &(*p)->rb_right;
-			leftmost = false;
-		} else {
-			/* Identical refs, merge them and free @newref */
-			struct extent_inode_elem *eie = ref->inode_list;
+	exist = rb_find_add_cached(&newref->rbnode, root, prelim_ref_cmp);
+	if (exist != NULL) {
+		/* Identical refs, merge them and free @newref */
+		struct extent_inode_elem *eie = ref->inode_list;
 
-			while (eie && eie->next)
-				eie = eie->next;
+		while (eie && eie->next)
+			eie = eie->next;
 
-			if (!eie)
-				ref->inode_list = newref->inode_list;
-			else
-				eie->next = newref->inode_list;
-			trace_btrfs_prelim_ref_merge(fs_info, ref, newref,
-						     preftree->count);
-			/*
-			 * A delayed ref can have newref->count < 0.
-			 * The ref->count is updated to follow any
-			 * BTRFS_[ADD|DROP]_DELAYED_REF actions.
-			 */
-			update_share_count(sc, ref->count,
-					   ref->count + newref->count, newref);
-			ref->count += newref->count;
-			free_pref(newref);
-			return;
-		}
+		if (!eie)
+			ref->inode_list = newref->inode_list;
+		else
+			eie->next = newref->inode_list;
+		trace_btrfs_prelim_ref_merge(fs_info, ref, newref,
+							preftree->count);
+		/*
+		 * A delayed ref can have newref->count < 0.
+		 * The ref->count is updated to follow any
+		 * BTRFS_[ADD|DROP]_DELAYED_REF actions.
+		 */
+		update_share_count(sc, ref->count,
+					ref->count + newref->count, newref);
+		ref->count += newref->count;
+		free_pref(newref);
+		return;
 	}
 
 	update_share_count(sc, 0, newref->count, newref);
 	preftree->count++;
 	trace_btrfs_prelim_ref_insert(fs_info, newref, NULL, preftree->count);
-	rb_link_node(&newref->rbnode, parent, p);
-	rb_insert_color_cached(&newref->rbnode, root, leftmost);
 }
 
 /*
-- 
2.45.2

Re: [PATCH 3/6] btrfs: edit prelim_ref_insert() to use rb helpers

[David Sterba]

On Tue, Dec 10, 2024 at 01:06:09PM -0600, Roger L. Beckermeyer III wrote:
> This commit edits prelim_ref_insert() in fs/btrfs/backref.c to use
> rb_find_add_cached(). It also adds a comparison function for use with
> rb_find_add_cached().
> 
> Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
> ---
>  fs/btrfs/backref.c | 71 +++++++++++++++++++++++-----------------------
>  1 file changed, 36 insertions(+), 35 deletions(-)
> 
> diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
> index 6d9f39c1d89c..fcbcfce0f93a 100644
> --- a/fs/btrfs/backref.c
> +++ b/fs/btrfs/backref.c
> @@ -250,6 +250,17 @@ static int prelim_ref_compare(const struct prelim_ref *ref1,
>  	return 0;
>  }
>  
> +static int prelim_ref_cmp(struct rb_node *node, const struct rb_node *exist)
> +{
> +	int result;
> +	struct prelim_ref *ref1 = rb_entry(node, struct prelim_ref, rbnode);
> +	struct prelim_ref *ref2 = rb_entry(exist, struct prelim_ref, rbnode);

Same type mismatch, missing const.
> +
> +	result = prelim_ref_compare(ref1, ref2);

You don't need the temporary variable 'result'.

> +
> +	return result;
> +}
> +

[PATCH 4/6] btrfs: edit __btrfs_add_delayed_item() to use rb helper

[Roger L. Beckermeyer III]

This commit edits __btrfs_add_delayed_item() to use rb_find_add_cached().
It also adds a helper function to use with rb_find_add_cached().

Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
---
 fs/btrfs/delayed-inode.c | 40 ++++++++++++++++------------------------
 1 file changed, 16 insertions(+), 24 deletions(-)

diff --git a/fs/btrfs/delayed-inode.c b/fs/btrfs/delayed-inode.c
index 508bdbae29a0..7d62224bc49c 100644
--- a/fs/btrfs/delayed-inode.c
+++ b/fs/btrfs/delayed-inode.c
@@ -366,40 +366,32 @@ static struct btrfs_delayed_item *__btrfs_lookup_delayed_item(
 	return NULL;
 }
 
+static int btrfs_add_delayed_item_cmp(struct rb_node *rb_node, const struct rb_node *exist_node)
+{
+	struct btrfs_delayed_item *item = rb_entry(rb_node, struct btrfs_delayed_item, rb_node);
+	struct btrfs_delayed_item *exist = rb_entry(exist_node, struct btrfs_delayed_item, rb_node);
+
+	if (item->index < exist->index)
+		return -1;
+	if (item->index > exist->index)
+		return 1;
+	return 0;
+}
+
 static int __btrfs_add_delayed_item(struct btrfs_delayed_node *delayed_node,
 				    struct btrfs_delayed_item *ins)
 {
-	struct rb_node **p, *node;
-	struct rb_node *parent_node = NULL;
 	struct rb_root_cached *root;
-	struct btrfs_delayed_item *item;
-	bool leftmost = true;
+	struct rb_node *exist;
 
 	if (ins->type == BTRFS_DELAYED_INSERTION_ITEM)
 		root = &delayed_node->ins_root;
 	else
 		root = &delayed_node->del_root;
 
-	p = &root->rb_root.rb_node;
-	node = &ins->rb_node;
-
-	while (*p) {
-		parent_node = *p;
-		item = rb_entry(parent_node, struct btrfs_delayed_item,
-				 rb_node);
-
-		if (item->index < ins->index) {
-			p = &(*p)->rb_right;
-			leftmost = false;
-		} else if (item->index > ins->index) {
-			p = &(*p)->rb_left;
-		} else {
-			return -EEXIST;
-		}
-	}
-
-	rb_link_node(node, parent_node, p);
-	rb_insert_color_cached(node, root, leftmost);
+	exist = rb_find_add_cached(&ins->rb_node, root, btrfs_add_delayed_item_cmp);
+	if (exist != NULL)
+		return -EEXIST;
 
 	if (ins->type == BTRFS_DELAYED_INSERTION_ITEM &&
 	    ins->index >= delayed_node->index_cnt)
-- 
2.45.2

[PATCH 5/6] btrfs: edit btrfs_add_chunk_map() to use rb helpers

[Roger L. Beckermeyer III]

Edits btrfs_add_chunk_map() to use rb_find_add_cached(). Also adds a
comparison function to use with rb_find_add_cached().

Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
---
 fs/btrfs/volumes.c | 39 ++++++++++++++++++---------------------
 1 file changed, 18 insertions(+), 21 deletions(-)

diff --git a/fs/btrfs/volumes.c b/fs/btrfs/volumes.c
index 1cccaf9c2b0d..4837761a56c9 100644
--- a/fs/btrfs/volumes.c
+++ b/fs/btrfs/volumes.c
@@ -5513,33 +5513,30 @@ void btrfs_remove_chunk_map(struct btrfs_fs_info *fs_info, struct btrfs_chunk_ma
 	btrfs_free_chunk_map(map);
 }
 
+static int btrfs_chunk_map_cmp(struct rb_node *rb_node, const struct rb_node *exist_node)
+{
+	struct btrfs_chunk_map *map = rb_entry(rb_node, struct btrfs_chunk_map, rb_node);
+	struct btrfs_chunk_map *exist = rb_entry(exist_node, struct btrfs_chunk_map, rb_node);
+
+	if (map->start == exist->start)
+		return 0;
+	if (map->start < exist->start)
+		return -1;
+	return 1;
+}
+
 EXPORT_FOR_TESTS
 int btrfs_add_chunk_map(struct btrfs_fs_info *fs_info, struct btrfs_chunk_map *map)
 {
-	struct rb_node **p;
-	struct rb_node *parent = NULL;
-	bool leftmost = true;
+	struct rb_node *exist;
 
 	write_lock(&fs_info->mapping_tree_lock);
-	p = &fs_info->mapping_tree.rb_root.rb_node;
-	while (*p) {
-		struct btrfs_chunk_map *entry;
-
-		parent = *p;
-		entry = rb_entry(parent, struct btrfs_chunk_map, rb_node);
-
-		if (map->start < entry->start) {
-			p = &(*p)->rb_left;
-		} else if (map->start > entry->start) {
-			p = &(*p)->rb_right;
-			leftmost = false;
-		} else {
-			write_unlock(&fs_info->mapping_tree_lock);
-			return -EEXIST;
-		}
+	exist = rb_find_add_cached(&map->rb_node, &fs_info->mapping_tree, btrfs_chunk_map_cmp);
+
+	if (exist != NULL) {
+		write_unlock(&fs_info->mapping_tree_lock);
+		return -EEXIST;
 	}
-	rb_link_node(&map->rb_node, parent, p);
-	rb_insert_color_cached(&map->rb_node, &fs_info->mapping_tree, leftmost);
 	chunk_map_device_set_bits(map, CHUNK_ALLOCATED);
 	chunk_map_device_clear_bits(map, CHUNK_TRIMMED);
 	write_unlock(&fs_info->mapping_tree_lock);
-- 
2.45.2

[PATCH 6/6] btrfs: edit tree_insert() to use rb helpers

[Roger L. Beckermeyer III]

Edits tree_insert() to use rb_find_add_cached(). Also adds a
comparison function for use in rb_find_add_cached() to compare.

V2: incorporated changes from Filipe Manana

Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
---
 fs/btrfs/delayed-ref.c | 39 ++++++++++++++++-----------------------
 1 file changed, 16 insertions(+), 23 deletions(-)

diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c
index 30f7079fa28e..e288058f5c3c 100644
--- a/fs/btrfs/delayed-ref.c
+++ b/fs/btrfs/delayed-ref.c
@@ -317,34 +317,27 @@ static int comp_refs(struct btrfs_delayed_ref_node *ref1,
 	return 0;
 }
 
+static int comp_refs_node(struct rb_node *node, const struct rb_node *node2)
+{
+	struct btrfs_delayed_ref_node *ref1;
+	struct btrfs_delayed_ref_node *ref2;
+	bool check_seq = true;
+
+	ref1 = rb_entry(node, struct btrfs_delayed_ref_node, ref_node);
+	ref2 = rb_entry(node2, struct btrfs_delayed_ref_node, ref_node);
+
+	return comp_refs(ref1, ref2, check_seq);
+}
+
 static struct btrfs_delayed_ref_node* tree_insert(struct rb_root_cached *root,
 		struct btrfs_delayed_ref_node *ins)
 {
-	struct rb_node **p = &root->rb_root.rb_node;
 	struct rb_node *node = &ins->ref_node;
-	struct rb_node *parent_node = NULL;
-	struct btrfs_delayed_ref_node *entry;
-	bool leftmost = true;
-
-	while (*p) {
-		int comp;
-
-		parent_node = *p;
-		entry = rb_entry(parent_node, struct btrfs_delayed_ref_node,
-				 ref_node);
-		comp = comp_refs(ins, entry, true);
-		if (comp < 0) {
-			p = &(*p)->rb_left;
-		} else if (comp > 0) {
-			p = &(*p)->rb_right;
-			leftmost = false;
-		} else {
-			return entry;
-		}
-	}
+	struct rb_node *exist;
 
-	rb_link_node(node, parent_node, p);
-	rb_insert_color_cached(node, root, leftmost);
+	exist = rb_find_add_cached(node, root, comp_refs_node);
+	if (exist != NULL)
+		return rb_entry(exist, struct btrfs_delayed_ref_node, ref_node);
 	return NULL;
 }
 
-- 
2.45.2

[PATCH 0/6] reduce boilerplate code within btrfs

[Roger L. Beckermeyer III]

The goal of this patch series is to reduce boilerplate code
within btrfs. To accomplish this rb_find_add_cached() was added
to linux/include/rbtree.h. Any replaceable functions were then 
replaced within btrfs.

Roger L. Beckermeyer III (6):
  rbtree: add rb_find_add_cached() to rbtree.h
  btrfs: update btrfs_add_block_group_cache() to use rb helpers
  btrfs: update prelim_ref_insert() to use rb helpers
  btrfs: update __btrfs_add_delayed_item() to use rb helpers
  btrfs: update btrfs_add_chunk_map() to use rb helpers
  btrfs: update tree_insert() to use rb helpers

 fs/btrfs/backref.c       | 71 ++++++++++++++++++++--------------------
 fs/btrfs/block-group.c   | 40 ++++++++++------------
 fs/btrfs/delayed-inode.c | 40 +++++++++-------------
 fs/btrfs/delayed-ref.c   | 39 +++++++++-------------
 fs/btrfs/volumes.c       | 39 ++++++++++------------
 include/linux/rbtree.h   | 37 +++++++++++++++++++++
 6 files changed, 140 insertions(+), 126 deletions(-)

-- 
2.45.2

[PATCH 2/6] btrfs: update btrfs_add_block_group_cache() to use rb helpers

[Roger L. Beckermeyer III]

update fs/btrfs/block-group.c to use rb_find_add_cached()
implement btrfs_bg_start_cmp() for use with rb_find_add_cached().

Suggested-by: Josef Bacik <josef@toxicpanda.com>
Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
---
 fs/btrfs/block-group.c | 40 +++++++++++++++++-----------------------
 1 file changed, 17 insertions(+), 23 deletions(-)

diff --git a/fs/btrfs/block-group.c b/fs/btrfs/block-group.c
index 5be029734cfa..6001b78e9ea9 100644
--- a/fs/btrfs/block-group.c
+++ b/fs/btrfs/block-group.c
@@ -173,40 +173,34 @@ void btrfs_put_block_group(struct btrfs_block_group *cache)
 	}
 }
 
+static int btrfs_bg_start_cmp(struct rb_node *new, const struct rb_node *exist)
+{
+	struct btrfs_block_group *cmp1 = rb_entry(new, struct btrfs_block_group, cache_node);
+	const struct btrfs_block_group *cmp2 = rb_entry(exist, struct btrfs_block_group, cache_node);
+
+	if (cmp1->start < cmp2->start)
+		return -1;
+	if (cmp1->start > cmp2->start)
+		return 1;
+	return 0;
+}
+
 /*
  * This adds the block group to the fs_info rb tree for the block group cache
  */
 static int btrfs_add_block_group_cache(struct btrfs_fs_info *info,
 				       struct btrfs_block_group *block_group)
 {
-	struct rb_node **p;
-	struct rb_node *parent = NULL;
-	struct btrfs_block_group *cache;
-	bool leftmost = true;
+	struct rb_node *exist;
 
 	ASSERT(block_group->length != 0);
 
 	write_lock(&info->block_group_cache_lock);
-	p = &info->block_group_cache_tree.rb_root.rb_node;
-
-	while (*p) {
-		parent = *p;
-		cache = rb_entry(parent, struct btrfs_block_group, cache_node);
-		if (block_group->start < cache->start) {
-			p = &(*p)->rb_left;
-		} else if (block_group->start > cache->start) {
-			p = &(*p)->rb_right;
-			leftmost = false;
-		} else {
-			write_unlock(&info->block_group_cache_lock);
-			return -EEXIST;
-		}
-	}
-
-	rb_link_node(&block_group->cache_node, parent, p);
-	rb_insert_color_cached(&block_group->cache_node,
-			       &info->block_group_cache_tree, leftmost);
 
+	exist = rb_find_add_cached(&block_group->cache_node,
+			&info->block_group_cache_tree, btrfs_bg_start_cmp);
+	if (exist != NULL)
+		return -EEXIST;
 	write_unlock(&info->block_group_cache_lock);
 
 	return 0;
-- 
2.45.2

Re: [PATCH 2/6] btrfs: update btrfs_add_block_group_cache() to use rb helpers

[Qu Wenruo]

在 2024/12/13 06:59, Roger L. Beckermeyer III 写道:
> update fs/btrfs/block-group.c to use rb_find_add_cached()
> implement btrfs_bg_start_cmp() for use with rb_find_add_cached().
>
> Suggested-by: Josef Bacik <josef@toxicpanda.com>
> Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
> ---
>   fs/btrfs/block-group.c | 40 +++++++++++++++++-----------------------
>   1 file changed, 17 insertions(+), 23 deletions(-)
>
> diff --git a/fs/btrfs/block-group.c b/fs/btrfs/block-group.c
> index 5be029734cfa..6001b78e9ea9 100644
> --- a/fs/btrfs/block-group.c
> +++ b/fs/btrfs/block-group.c
> @@ -173,40 +173,34 @@ void btrfs_put_block_group(struct btrfs_block_group *cache)
>   	}
>   }
>
> +static int btrfs_bg_start_cmp(struct rb_node *new, const struct rb_node *exist)
> +{
> +	struct btrfs_block_group *cmp1 = rb_entry(new, struct btrfs_block_group, cache_node);
> +	const struct btrfs_block_group *cmp2 = rb_entry(exist, struct btrfs_block_group, cache_node);
> +
> +	if (cmp1->start < cmp2->start)
> +		return -1;
> +	if (cmp1->start > cmp2->start)
> +		return 1;
> +	return 0;
> +}
> +
>   /*
>    * This adds the block group to the fs_info rb tree for the block group cache
>    */
>   static int btrfs_add_block_group_cache(struct btrfs_fs_info *info,
>   				       struct btrfs_block_group *block_group)
>   {
> -	struct rb_node **p;
> -	struct rb_node *parent = NULL;
> -	struct btrfs_block_group *cache;
> -	bool leftmost = true;
> +	struct rb_node *exist;
>
>   	ASSERT(block_group->length != 0);
>
>   	write_lock(&info->block_group_cache_lock);
> -	p = &info->block_group_cache_tree.rb_root.rb_node;
> -
> -	while (*p) {
> -		parent = *p;
> -		cache = rb_entry(parent, struct btrfs_block_group, cache_node);
> -		if (block_group->start < cache->start) {
> -			p = &(*p)->rb_left;
> -		} else if (block_group->start > cache->start) {
> -			p = &(*p)->rb_right;
> -			leftmost = false;
> -		} else {
> -			write_unlock(&info->block_group_cache_lock);
> -			return -EEXIST;
> -		}
> -	}
> -
> -	rb_link_node(&block_group->cache_node, parent, p);
> -	rb_insert_color_cached(&block_group->cache_node,
> -			       &info->block_group_cache_tree, leftmost);
>
> +	exist = rb_find_add_cached(&block_group->cache_node,
> +			&info->block_group_cache_tree, btrfs_bg_start_cmp);
> +	if (exist != NULL)
> +		return -EEXIST;

If we hit -EEXIST, the block_group_cache_lock is never unlocked.

>   	write_unlock(&info->block_group_cache_lock);
>
>   	return 0;

[PATCH 3/6] btrfs: update prelim_ref_insert() to use rb helpers

[Roger L. Beckermeyer III]

update prelim_ref_insert() to use rb_find_add_cached()
adds prelim_ref_cmp for use with rb_find_add_cached()

Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
---
 fs/btrfs/backref.c | 71 +++++++++++++++++++++++-----------------------
 1 file changed, 36 insertions(+), 35 deletions(-)

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 6d9f39c1d89c..fcbcfce0f93a 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -250,6 +250,17 @@ static int prelim_ref_compare(const struct prelim_ref *ref1,
 	return 0;
 }
 
+static int prelim_ref_cmp(struct rb_node *node, const struct rb_node *exist)
+{
+	int result;
+	struct prelim_ref *ref1 = rb_entry(node, struct prelim_ref, rbnode);
+	struct prelim_ref *ref2 = rb_entry(exist, struct prelim_ref, rbnode);
+
+	result = prelim_ref_compare(ref1, ref2);
+
+	return result;
+}
+
 static void update_share_count(struct share_check *sc, int oldcount,
 			       int newcount, const struct prelim_ref *newref)
 {
@@ -281,52 +292,42 @@ static void prelim_ref_insert(const struct btrfs_fs_info *fs_info,
 	struct rb_node **p;
 	struct rb_node *parent = NULL;
 	struct prelim_ref *ref;
-	int result;
-	bool leftmost = true;
+	struct rb_node *exist;
 
 	root = &preftree->root;
 	p = &root->rb_root.rb_node;
+	parent = *p;
+	ref = rb_entry(parent, struct prelim_ref, rbnode);
 
-	while (*p) {
-		parent = *p;
-		ref = rb_entry(parent, struct prelim_ref, rbnode);
-		result = prelim_ref_compare(ref, newref);
-		if (result < 0) {
-			p = &(*p)->rb_left;
-		} else if (result > 0) {
-			p = &(*p)->rb_right;
-			leftmost = false;
-		} else {
-			/* Identical refs, merge them and free @newref */
-			struct extent_inode_elem *eie = ref->inode_list;
+	exist = rb_find_add_cached(&newref->rbnode, root, prelim_ref_cmp);
+	if (exist != NULL) {
+		/* Identical refs, merge them and free @newref */
+		struct extent_inode_elem *eie = ref->inode_list;
 
-			while (eie && eie->next)
-				eie = eie->next;
+		while (eie && eie->next)
+			eie = eie->next;
 
-			if (!eie)
-				ref->inode_list = newref->inode_list;
-			else
-				eie->next = newref->inode_list;
-			trace_btrfs_prelim_ref_merge(fs_info, ref, newref,
-						     preftree->count);
-			/*
-			 * A delayed ref can have newref->count < 0.
-			 * The ref->count is updated to follow any
-			 * BTRFS_[ADD|DROP]_DELAYED_REF actions.
-			 */
-			update_share_count(sc, ref->count,
-					   ref->count + newref->count, newref);
-			ref->count += newref->count;
-			free_pref(newref);
-			return;
-		}
+		if (!eie)
+			ref->inode_list = newref->inode_list;
+		else
+			eie->next = newref->inode_list;
+		trace_btrfs_prelim_ref_merge(fs_info, ref, newref,
+							preftree->count);
+		/*
+		 * A delayed ref can have newref->count < 0.
+		 * The ref->count is updated to follow any
+		 * BTRFS_[ADD|DROP]_DELAYED_REF actions.
+		 */
+		update_share_count(sc, ref->count,
+					ref->count + newref->count, newref);
+		ref->count += newref->count;
+		free_pref(newref);
+		return;
 	}
 
 	update_share_count(sc, 0, newref->count, newref);
 	preftree->count++;
 	trace_btrfs_prelim_ref_insert(fs_info, newref, NULL, preftree->count);
-	rb_link_node(&newref->rbnode, parent, p);
-	rb_insert_color_cached(&newref->rbnode, root, leftmost);
 }
 
 /*
-- 
2.45.2

[PATCH 4/6] btrfs: update __btrfs_add_delayed_item() to use rb helpers

[Roger L. Beckermeyer III]

update __btrfs_add_delayed_item() to use rb_find_add_cached()
add btrfs_delayed_item_cmp() to use with rb_find_add_cached()

Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
---
 fs/btrfs/delayed-inode.c | 40 ++++++++++++++++------------------------
 1 file changed, 16 insertions(+), 24 deletions(-)

diff --git a/fs/btrfs/delayed-inode.c b/fs/btrfs/delayed-inode.c
index 508bdbae29a0..d705049fb381 100644
--- a/fs/btrfs/delayed-inode.c
+++ b/fs/btrfs/delayed-inode.c
@@ -366,40 +366,32 @@ static struct btrfs_delayed_item *__btrfs_lookup_delayed_item(
 	return NULL;
 }
 
+static int btrfs_delayed_item_cmp(struct rb_node *rb_node, const struct rb_node *exist_node)
+{
+	struct btrfs_delayed_item *item = rb_entry(rb_node, struct btrfs_delayed_item, rb_node);
+	const struct btrfs_delayed_item *exist = rb_entry(exist_node, struct btrfs_delayed_item, rb_node);
+
+	if (item->index < exist->index)
+		return -1;
+	if (item->index > exist->index)
+		return 1;
+	return 0;
+}
+
 static int __btrfs_add_delayed_item(struct btrfs_delayed_node *delayed_node,
 				    struct btrfs_delayed_item *ins)
 {
-	struct rb_node **p, *node;
-	struct rb_node *parent_node = NULL;
 	struct rb_root_cached *root;
-	struct btrfs_delayed_item *item;
-	bool leftmost = true;
+	struct rb_node *exist;
 
 	if (ins->type == BTRFS_DELAYED_INSERTION_ITEM)
 		root = &delayed_node->ins_root;
 	else
 		root = &delayed_node->del_root;
 
-	p = &root->rb_root.rb_node;
-	node = &ins->rb_node;
-
-	while (*p) {
-		parent_node = *p;
-		item = rb_entry(parent_node, struct btrfs_delayed_item,
-				 rb_node);
-
-		if (item->index < ins->index) {
-			p = &(*p)->rb_right;
-			leftmost = false;
-		} else if (item->index > ins->index) {
-			p = &(*p)->rb_left;
-		} else {
-			return -EEXIST;
-		}
-	}
-
-	rb_link_node(node, parent_node, p);
-	rb_insert_color_cached(node, root, leftmost);
+	exist = rb_find_add_cached(&ins->rb_node, root, btrfs_delayed_item_cmp);
+	if (exist != NULL)
+		return -EEXIST;
 
 	if (ins->type == BTRFS_DELAYED_INSERTION_ITEM &&
 	    ins->index >= delayed_node->index_cnt)
-- 
2.45.2

[PATCH 5/6] btrfs: update btrfs_add_chunk_map() to use rb helpers

[Roger L. Beckermeyer III]

update btrfs_add_chunk_map() to use rb_find_add_cached(). add
btrfs_chunk_map_cmp to use with rb_find_add_cached().

Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
---
 fs/btrfs/volumes.c | 39 ++++++++++++++++++---------------------
 1 file changed, 18 insertions(+), 21 deletions(-)

diff --git a/fs/btrfs/volumes.c b/fs/btrfs/volumes.c
index 1cccaf9c2b0d..b39723a95f26 100644
--- a/fs/btrfs/volumes.c
+++ b/fs/btrfs/volumes.c
@@ -5513,33 +5513,30 @@ void btrfs_remove_chunk_map(struct btrfs_fs_info *fs_info, struct btrfs_chunk_ma
 	btrfs_free_chunk_map(map);
 }
 
+static int btrfs_chunk_map_cmp(struct rb_node *rb_node, const struct rb_node *exist_node)
+{
+	struct btrfs_chunk_map *map = rb_entry(rb_node, struct btrfs_chunk_map, rb_node);
+	const struct btrfs_chunk_map *exist = rb_entry(exist_node, struct btrfs_chunk_map, rb_node);
+
+	if (map->start == exist->start)
+		return 0;
+	if (map->start < exist->start)
+		return -1;
+	return 1;
+}
+
 EXPORT_FOR_TESTS
 int btrfs_add_chunk_map(struct btrfs_fs_info *fs_info, struct btrfs_chunk_map *map)
 {
-	struct rb_node **p;
-	struct rb_node *parent = NULL;
-	bool leftmost = true;
+	struct rb_node *exist;
 
 	write_lock(&fs_info->mapping_tree_lock);
-	p = &fs_info->mapping_tree.rb_root.rb_node;
-	while (*p) {
-		struct btrfs_chunk_map *entry;
-
-		parent = *p;
-		entry = rb_entry(parent, struct btrfs_chunk_map, rb_node);
-
-		if (map->start < entry->start) {
-			p = &(*p)->rb_left;
-		} else if (map->start > entry->start) {
-			p = &(*p)->rb_right;
-			leftmost = false;
-		} else {
-			write_unlock(&fs_info->mapping_tree_lock);
-			return -EEXIST;
-		}
+	exist = rb_find_add_cached(&map->rb_node, &fs_info->mapping_tree, btrfs_chunk_map_cmp);
+
+	if (exist != NULL) {
+		write_unlock(&fs_info->mapping_tree_lock);
+		return -EEXIST;
 	}
-	rb_link_node(&map->rb_node, parent, p);
-	rb_insert_color_cached(&map->rb_node, &fs_info->mapping_tree, leftmost);
 	chunk_map_device_set_bits(map, CHUNK_ALLOCATED);
 	chunk_map_device_clear_bits(map, CHUNK_TRIMMED);
 	write_unlock(&fs_info->mapping_tree_lock);
-- 
2.45.2

[PATCH 6/6] btrfs: update tree_insert() to use rb helpers

[Roger L. Beckermeyer III]

update tree_insert() to use rb_find_add_cached().
add cmp_refs_node in rb_find_add_cached() to compare.

note: I think some of comparison functions could be further refined.

V2: incorporated changes from Filipe Manana

Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
---
 fs/btrfs/delayed-ref.c | 39 ++++++++++++++++-----------------------
 1 file changed, 16 insertions(+), 23 deletions(-)

diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c
index 30f7079fa28e..3cd122c899cc 100644
--- a/fs/btrfs/delayed-ref.c
+++ b/fs/btrfs/delayed-ref.c
@@ -317,34 +317,27 @@ static int comp_refs(struct btrfs_delayed_ref_node *ref1,
 	return 0;
 }
 
+static int cmp_refs_node(struct rb_node *node, const struct rb_node *node2)
+{
+	struct btrfs_delayed_ref_node *ref1;
+	const struct btrfs_delayed_ref_node *ref2;
+	bool check_seq = true;
+
+	ref1 = rb_entry(node, struct btrfs_delayed_ref_node, ref_node);
+	ref2 = rb_entry(node2, struct btrfs_delayed_ref_node, ref_node);
+
+	return comp_refs(ref1, ref2, check_seq);
+}
+
 static struct btrfs_delayed_ref_node* tree_insert(struct rb_root_cached *root,
 		struct btrfs_delayed_ref_node *ins)
 {
-	struct rb_node **p = &root->rb_root.rb_node;
 	struct rb_node *node = &ins->ref_node;
-	struct rb_node *parent_node = NULL;
-	struct btrfs_delayed_ref_node *entry;
-	bool leftmost = true;
-
-	while (*p) {
-		int comp;
-
-		parent_node = *p;
-		entry = rb_entry(parent_node, struct btrfs_delayed_ref_node,
-				 ref_node);
-		comp = comp_refs(ins, entry, true);
-		if (comp < 0) {
-			p = &(*p)->rb_left;
-		} else if (comp > 0) {
-			p = &(*p)->rb_right;
-			leftmost = false;
-		} else {
-			return entry;
-		}
-	}
+	struct rb_node *exist;
 
-	rb_link_node(node, parent_node, p);
-	rb_insert_color_cached(node, root, leftmost);
+	exist = rb_find_add_cached(node, root, cmp_refs_node);
+	if (exist != NULL)
+		return rb_entry(exist, struct btrfs_delayed_ref_node, ref_node);
 	return NULL;
 }
 
-- 
2.45.2

Re: [PATCH 6/6] btrfs: update tree_insert() to use rb helpers

[Qu Wenruo]

在 2024/12/13 06:59, Roger L. Beckermeyer III 写道:
> update tree_insert() to use rb_find_add_cached().
> add cmp_refs_node in rb_find_add_cached() to compare.
> 
> note: I think some of comparison functions could be further refined.
> 
> V2: incorporated changes from Filipe Manana

Firstly changelog should not be part of the commit message. It should be 
after the "---" line so that git-am will drop it when applying.

Secondly if you're updating a series of patches, please resend the whole 
series and put the change log into the cover letter to explain all the 
changes.
Updating one patch of a series is only going to make it much harder to 
follow/apply.

And put a version number for the whole series. It can be done by 
git-formatpatch with `--subject="PATCH v2"` option.

Lastly, please do not split your patches and send differently, the last 
send attempt split the first and the remaining patches, just do not do that.
Always send the whole series with "git send-email *.patch", that will 
easily mess up the Message-Id (which is already messed up as you put two 
message ids for your new series, meanwhile you should use a new 
message-id for each updated series)

If you want separate Cc, you can put it into the commit message and 
git-sendemail will pick it up.

Thanks,
Qu

> 
> Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
> ---
>   fs/btrfs/delayed-ref.c | 39 ++++++++++++++++-----------------------
>   1 file changed, 16 insertions(+), 23 deletions(-)
> 
> diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c
> index 30f7079fa28e..3cd122c899cc 100644
> --- a/fs/btrfs/delayed-ref.c
> +++ b/fs/btrfs/delayed-ref.c
> @@ -317,34 +317,27 @@ static int comp_refs(struct btrfs_delayed_ref_node *ref1,
>   	return 0;
>   }
>   
> +static int cmp_refs_node(struct rb_node *node, const struct rb_node *node2)
> +{
> +	struct btrfs_delayed_ref_node *ref1;
> +	const struct btrfs_delayed_ref_node *ref2;
> +	bool check_seq = true;
> +
> +	ref1 = rb_entry(node, struct btrfs_delayed_ref_node, ref_node);
> +	ref2 = rb_entry(node2, struct btrfs_delayed_ref_node, ref_node);
> +
> +	return comp_refs(ref1, ref2, check_seq);
> +}
> +
>   static struct btrfs_delayed_ref_node* tree_insert(struct rb_root_cached *root,
>   		struct btrfs_delayed_ref_node *ins)
>   {
> -	struct rb_node **p = &root->rb_root.rb_node;
>   	struct rb_node *node = &ins->ref_node;
> -	struct rb_node *parent_node = NULL;
> -	struct btrfs_delayed_ref_node *entry;
> -	bool leftmost = true;
> -
> -	while (*p) {
> -		int comp;
> -
> -		parent_node = *p;
> -		entry = rb_entry(parent_node, struct btrfs_delayed_ref_node,
> -				 ref_node);
> -		comp = comp_refs(ins, entry, true);
> -		if (comp < 0) {
> -			p = &(*p)->rb_left;
> -		} else if (comp > 0) {
> -			p = &(*p)->rb_right;
> -			leftmost = false;
> -		} else {
> -			return entry;
> -		}
> -	}
> +	struct rb_node *exist;
>   
> -	rb_link_node(node, parent_node, p);
> -	rb_insert_color_cached(node, root, leftmost);
> +	exist = rb_find_add_cached(node, root, cmp_refs_node);
> +	if (exist != NULL)
> +		return rb_entry(exist, struct btrfs_delayed_ref_node, ref_node);
>   	return NULL;
>   }
>   

Re: [PATCH 6/6] btrfs: update tree_insert() to use rb helpers

[Johannes Thumshirn]

On 13.12.24 07:19, Qu Wenruo wrote:
> 
> 
> 在 2024/12/13 06:59, Roger L. Beckermeyer III 写道:
>> update tree_insert() to use rb_find_add_cached().
>> add cmp_refs_node in rb_find_add_cached() to compare.
>>
>> note: I think some of comparison functions could be further refined.
>>
>> V2: incorporated changes from Filipe Manana
> 
> Firstly changelog should not be part of the commit message. It should be
> after the "---" line so that git-am will drop it when applying.
> 
> Secondly if you're updating a series of patches, please resend the whole
> series and put the change log into the cover letter to explain all the
> changes.
> Updating one patch of a series is only going to make it much harder to
> follow/apply.
> 
> And put a version number for the whole series. It can be done by
> git-formatpatch with `--subject="PATCH v2"` option.

Nit: git format-patch -v 2 also gives you a nice v2-XXX.patch prefix for 
the files as well as "PATCH v2" for the subject.

Re: [PATCH 6/6] btrfs: update tree_insert() to use rb helpers

[Qu Wenruo]

在 2024/12/13 18:00, Johannes Thumshirn 写道:
> On 13.12.24 07:19, Qu Wenruo wrote:
>>
>>
>> 在 2024/12/13 06:59, Roger L. Beckermeyer III 写道:
>>> update tree_insert() to use rb_find_add_cached().
>>> add cmp_refs_node in rb_find_add_cached() to compare.
>>>
>>> note: I think some of comparison functions could be further refined.
>>>
>>> V2: incorporated changes from Filipe Manana
>>
>> Firstly changelog should not be part of the commit message. It should be
>> after the "---" line so that git-am will drop it when applying.
>>
>> Secondly if you're updating a series of patches, please resend the whole
>> series and put the change log into the cover letter to explain all the
>> changes.
>> Updating one patch of a series is only going to make it much harder to
>> follow/apply.
>>
>> And put a version number for the whole series. It can be done by
>> git-formatpatch with `--subject="PATCH v2"` option.
> 
> Nit: git format-patch -v 2 also gives you a nice v2-XXX.patch prefix for
> the files as well as "PATCH v2" for the subject.

Thanks a lot! It saves quite a lot of key strikes, and even added the 
"v2-" prefix.

Never too old to learn.

Thanks,
Qu

Re: [PATCH 6/6] btrfs: update tree_insert() to use rb helpers

[Lee Beckermeyer]

On Fri, Dec 13, 2024 at 1:32 AM Qu Wenruo <wqu@suse.com> wrote:
>
>
>
> 在 2024/12/13 18:00, Johannes Thumshirn 写道:
> > On 13.12.24 07:19, Qu Wenruo wrote:
> >>
> >>
> >> 在 2024/12/13 06:59, Roger L. Beckermeyer III 写道:
> >>> update tree_insert() to use rb_find_add_cached().
> >>> add cmp_refs_node in rb_find_add_cached() to compare.
> >>>
> >>> note: I think some of comparison functions could be further refined.
> >>>
> >>> V2: incorporated changes from Filipe Manana
> >>
> >> Firstly changelog should not be part of the commit message. It should be
> >> after the "---" line so that git-am will drop it when applying.
added it to the cover letter this time, also was more thorough in
documenting the changes.
> >>
> >> Secondly if you're updating a series of patches, please resend the whole
> >> series and put the change log into the cover letter to explain all the
> >> changes.
> >> Updating one patch of a series is only going to make it much harder to
> >> follow/apply.
Roger (pun intended) I'll resend the whole patch series once I get a
reply on this, I've been utilizing the help message on the first
message I sent so it all stays the same more or less. Should I not be
doing that when I send a new patch series?
> >>
> >> And put a version number for the whole series. It can be done by
> >> git-formatpatch with `--subject="PATCH v2"` option.
> >
> > Nit: git format-patch -v 2 also gives you a nice v2-XXX.patch prefix for
> > the files as well as "PATCH v2" for the subject.
>
> Thanks a lot! It saves quite a lot of key strikes, and even added the
> "v2-" prefix.
>
> Never too old to learn.
>
> Thanks,
> Qu

Re: [PATCH 6/6] btrfs: update tree_insert() to use rb helpers

[Qu Wenruo]

在 2024/12/14 03:44, Lee Beckermeyer 写道:
> On Fri, Dec 13, 2024 at 1:32 AM Qu Wenruo <wqu@suse.com> wrote:
>>
>>
>>
>> 在 2024/12/13 18:00, Johannes Thumshirn 写道:
>>> On 13.12.24 07:19, Qu Wenruo wrote:
>>>>
>>>>
>>>> 在 2024/12/13 06:59, Roger L. Beckermeyer III 写道:
>>>>> update tree_insert() to use rb_find_add_cached().
>>>>> add cmp_refs_node in rb_find_add_cached() to compare.
>>>>>
>>>>> note: I think some of comparison functions could be further refined.
>>>>>
>>>>> V2: incorporated changes from Filipe Manana
>>>>
>>>> Firstly changelog should not be part of the commit message. It should be
>>>> after the "---" line so that git-am will drop it when applying.
> added it to the cover letter this time, also was more thorough in
> documenting the changes.
>>>>
>>>> Secondly if you're updating a series of patches, please resend the whole
>>>> series and put the change log into the cover letter to explain all the
>>>> changes.
>>>> Updating one patch of a series is only going to make it much harder to
>>>> follow/apply.
> Roger (pun intended) I'll resend the whole patch series once I get a
> reply on this, I've been utilizing the help message on the first
> message I sent so it all stays the same more or less.

What do you mean by the "help message"?

> Should I not be
> doing that when I send a new patch series?
>>>>
>>>> And put a version number for the whole series. It can be done by
>>>> git-formatpatch with `--subject="PATCH v2"` option.
>>>
>>> Nit: git format-patch -v 2 also gives you a nice v2-XXX.patch prefix for
>>> the files as well as "PATCH v2" for the subject.
>>
>> Thanks a lot! It saves quite a lot of key strikes, and even added the
>> "v2-" prefix.
>>
>> Never too old to learn.
>>
>> Thanks,
>> Qu
>