Skip to contentSkip to conversation

reduce boilerplate code within btrfs

PATCH In review Roger L. Beckermeyer III 9 participants 52 messages Dec 8, 2024 – Dec 16, 2024 Btrfs file system

lore
Share & tools
lore
#0 lore raw

cover reduce boilerplate code within btrfs

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(-)
Signature · 1 line
2.45.2
#1 lore raw

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

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.

---
 include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++
 1 file changed, 37 insertions(+)
include/linux/rbtree.h +37 -0
index 7c173aa64e1e..0d4444c0cfb3 100644
@@ -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
Signature · 1 line
2.45.2
#2 lore raw

PATCH 1/1 btrfs: edit btrfs_add_block_group_cache() to use rb helper

In reply to 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().

---
 fs/btrfs/block-group.c | 40 +++++++++++++++++-----------------------
 1 file changed, 17 insertions(+), 23 deletions(-)
fs/btrfs/block-group.c +17 -23
index 5be029734cfa..ccff051de43a 100644
@@ -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;
Signature · 1 line
2.45.2
#3 lore raw

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

kernel test robot noticed the following build errors:

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/[email protected]/config)
compiler: arc-elf-gcc (GCC) 13.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20241209/[email protected]/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 <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

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

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#4 lore raw

PATCH 1/1 btrfs: edit prelim_ref_insert() to use rb helpers

In reply to 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().

---
 fs/btrfs/backref.c | 71 +++++++++++++++++++++++-----------------------
 1 file changed, 36 insertions(+), 35 deletions(-)
fs/btrfs/backref.c +36 -35
index 6d9f39c1d89c..fcbcfce0f93a 100644
@@ -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);
 }
 
 /*
Signature · 1 line
2.45.2
#5 lore raw

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

kernel test robot noticed the following build errors:

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/[email protected]/config)
compiler: arc-elf-gcc (GCC) 13.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20241209/[email protected]/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 <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

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

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#6 lore raw

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

In reply to Roger L. Beckermeyer III
kernel test robot noticed the following build errors:

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/[email protected]/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/[email protected]/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 <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

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

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#7 lore raw

PATCH 1/1 btrfs: edit __btrfs_add_delayed_item() to use rb helper

In reply to 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().

---
 fs/btrfs/delayed-inode.c | 40 ++++++++++++++++------------------------
 1 file changed, 16 insertions(+), 24 deletions(-)
fs/btrfs/delayed-inode.c +16 -24
index 508bdbae29a0..7d62224bc49c 100644
@@ -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)
Signature · 1 line
2.45.2
#8 lore raw

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

kernel test robot noticed the following build errors:

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/[email protected]/config)
compiler: arc-elf-gcc (GCC) 13.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20241209/[email protected]/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 <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

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

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#9 lore raw

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

In reply to Roger L. Beckermeyer III
kernel test robot noticed the following build errors:

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/[email protected]/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/[email protected]/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 <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

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

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#10 lore raw

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

In reply to Roger L. Beckermeyer III
kernel test robot noticed the following build errors:

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/[email protected]/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/[email protected]/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 <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

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

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#11 lore raw

PATCH 1/1 btrfs: edit btrfs_add_chunk_map() to use rb helpers

In reply to 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().

---
 fs/btrfs/volumes.c | 39 ++++++++++++++++++---------------------
 1 file changed, 18 insertions(+), 21 deletions(-)
fs/btrfs/volumes.c +18 -21
index 1cccaf9c2b0d..4837761a56c9 100644
@@ -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);
Signature · 1 line
2.45.2
#12 lore raw

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

kernel test robot noticed the following build errors:

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/[email protected]/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/[email protected]/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 <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

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

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#13 lore raw

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

In reply to Roger L. Beckermeyer III
kernel test robot noticed the following build errors:

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/[email protected]/config)
compiler: arc-elf-gcc (GCC) 13.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20241209/[email protected]/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 <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

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

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#14 lore raw

PATCH 1/1 btrfs: edits tree_insert() to use rb helpers

In reply to 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.

---
 fs/btrfs/delayed-ref.c | 43 +++++++++++++++++++++---------------------
 1 file changed, 21 insertions(+), 22 deletions(-)
fs/btrfs/delayed-ref.c +21 -22
index 30f7079fa28e..d77ac8d05b2a 100644
@@ -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;
 }
 
Signature · 1 line
2.45.2
#15 lore raw

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

kernel test robot noticed the following build errors:

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/[email protected]/config)
compiler: arc-elf-gcc (GCC) 13.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20241209/[email protected]/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 <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

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

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#16 lore raw

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

In reply to Roger L. Beckermeyer III
kernel test robot noticed the following build errors:

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/[email protected]/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/[email protected]/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 <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

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

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#17 lore raw

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

In reply to Roger L. Beckermeyer III
kernel test robot noticed the following build errors:

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/[email protected]/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/[email protected]/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 <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

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

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#18 lore raw

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

In reply to Roger L. Beckermeyer III
Quoted 19 lines · 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.

---
 fs/btrfs/delayed-ref.c | 43 +++++++++++++++++++++---------------------
 1 file changed, 21 insertions(+), 22 deletions(-)
fs/btrfs/delayed-ref.c +0 -0
index 30f7079fa28e..d77ac8d05b2a 100644
@@ -317,34 +317,33 @@ static int comp_refs(struct btrfs_delayed_ref_node *ref1,
        return 0;
 }
 

fs/btrfs/delayed-ref.c static int comp_refs(struct btrfs_delayed_ref_node *ref1, · line 329

Quoted 10 lines
fs/btrfs/delayed-ref.c +10 -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.

fs/btrfs/delayed-ref.c static int comp_refs(struct btrfs_delayed_ref_node *ref1, · line 332

Quoted 3 lines
fs/btrfs/delayed-ref.c +3 -0
+
+       ret = comp_refs(ref1, ref2, check_seq);
+       return ret;

For this just do:

return comp_refs(ref1, ref2, check_seq);

Quoted 25 lines
fs/btrfs/delayed-ref.c +3 -17
+}
+
 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 {

fs/btrfs/delayed-ref.c static int comp_refs(struct btrfs_delayed_ref_node *ref1, · line 345

Quoted 10 lines
fs/btrfs/delayed-ref.c +4 -5
-                       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.

Quoted 8 lines
fs/btrfs/delayed-ref.c +1 -1
+       }
        return NULL;
 }
 
--

2.45.2

#19 lore raw

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

In reply to Roger L. Beckermeyer III
kernel test robot noticed the following build errors:

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/[email protected]/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/[email protected]/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 <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

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

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#20 lore raw
In reply to Roger L. Beckermeyer III
Quoted 4 lines · 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

Quoted 17 lines

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(-)
#21 lore raw
In reply to Roger L. Beckermeyer III
Quoted 5 lines · 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.

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

#22 lore raw

cover reduce boilerplate code within btrfs

In reply to 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(-)
Signature · 1 line
2.45.2
#23 lore raw

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

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

---
 include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++
 1 file changed, 37 insertions(+)
include/linux/rbtree.h +37 -0
index 7c173aa64e1e..0d4444c0cfb3 100644
@@ -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
Signature · 1 line
2.45.2
#24 lore raw

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

#25 lore raw

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

In reply to Roger L. Beckermeyer III
Quoted 16 lines · 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.

Quoted 2 lines
---
 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.

#26 lore raw

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

In reply to Roger L. Beckermeyer III
Quoted 2 lines · 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.

Quoted 17 lines
---
  include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++
  1 file changed, 37 insertions(+)
include/linux/rbtree.h +2 -0
index 7c173aa64e1e..0d4444c0cfb3 100644
@@ -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

include/linux/rbtree.h rb_add(struct rb_node *node, struct rb_root *tree, · line 224

Quoted 10 lines
include/linux/rbtree.h +10 -0
+ * @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

Quoted 28 lines
include/linux/rbtree.h +25 -0
+{
+	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
#27 lore raw

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

Quoted 8 lines · Qu Wenruo
Quoted 2 lines · 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 :-)

Quoted 31 lines
Quoted 17 lines
---
  include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++
  1 file changed, 37 insertions(+)
include/linux/rbtree.h +2 -0
index 7c173aa64e1e..0d4444c0cfb3 100644
@@ -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

include/linux/rbtree.h rb_add(struct rb_node *node, struct rb_root *tree, · line 224

Quoted 10 lines
include/linux/rbtree.h +10 -0
+ * @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.

Quoted 3 lines

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().

Acked-by on v1 1/6
#28 lore raw

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

In reply to Roger L. Beckermeyer III
Quoted 5 lines · 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.

Quoted 55 lines
---
 include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++
 1 file changed, 37 insertions(+)
include/linux/rbtree.h +37 -0
index 7c173aa64e1e..0d4444c0cfb3 100644
@@ -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
Signature · 1 line
2.45.2
#29 lore raw

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

Quoted 8 lines · Peter Zijlstra
Quoted 5 lines · 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 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

Quoted 57 lines
Quoted 56 lines
---
  include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++
  1 file changed, 37 insertions(+)
include/linux/rbtree.h +37 -1
index 7c173aa64e1e..0d4444c0cfb3 100644
@@ -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

#30 lore raw

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

Quoted 7 lines · Qu Wenruo
Quoted 4 lines · Peter Zijlstra
Quoted 3 lines · 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.

Quoted 6 lines
Quoted 4 lines
Quoted 2 lines

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.

Quoted 8 lines

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.

#31 lore raw

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

Quoted 27 lines · Peter Zijlstra
Quoted 7 lines · Qu Wenruo
Quoted 4 lines · Peter Zijlstra
Quoted 3 lines · 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.

Quoted 6 lines
Quoted 4 lines
Quoted 2 lines

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.

Quoted 8 lines

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.

Quoted 7 lines

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

#32 lore raw

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

In reply to 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().

---
 fs/btrfs/block-group.c | 40 +++++++++++++++++-----------------------
 1 file changed, 17 insertions(+), 23 deletions(-)
fs/btrfs/block-group.c +17 -23
index 5be029734cfa..ccff051de43a 100644
@@ -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;
Signature · 1 line
2.45.2
#33 lore raw

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

Quoted 1 line · Roger L. Beckermeyer III

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.

Quoted 15 lines

also adds a comparison function, btrfs_add_block_blkgrp_cmp(), for use with rb_find_add_cached().

---
 fs/btrfs/block-group.c | 40 +++++++++++++++++-----------------------
 1 file changed, 17 insertions(+), 23 deletions(-)
fs/btrfs/block-group.c +0 -0
index 5be029734cfa..ccff051de43a 100644

fs/btrfs/block-group.c void btrfs_put_block_group(struct btrfs_block_group *cache) · line 176

Quoted 4 lines
fs/btrfs/block-group.c +1 -0
@@ -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.

fs/btrfs/block-group.c void btrfs_put_block_group(struct btrfs_block_group *cache) · line 179

Quoted 3 lines
fs/btrfs/block-group.c +3 -0
+{
+	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.

Quoted 7 lines
fs/btrfs/block-group.c +7 -0
+
+	if (cmp1->start < cmp2->start)
+		return -1;
+	if (cmp1->start > cmp2->start)
+		return 1;
+	return 0;
+}
#34 lore raw

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

In reply to Roger L. Beckermeyer III

fs/btrfs/block-group.c void btrfs_put_block_group(struct btrfs_block_group *cache) · line 202

Quoted 3 lines · Roger L. Beckermeyer III
fs/btrfs/block-group.c +3 -0
+	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)'

Quoted 7 lines
fs/btrfs/block-group.c +1 -0
+		return -EEXIST;
 	write_unlock(&info->block_group_cache_lock);
 
 	return 0;
Signature · 1 line
2.45.2
#35 lore raw

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

In reply to 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().

---
 fs/btrfs/backref.c | 71 +++++++++++++++++++++++-----------------------
 1 file changed, 36 insertions(+), 35 deletions(-)
fs/btrfs/backref.c +36 -35
index 6d9f39c1d89c..fcbcfce0f93a 100644
@@ -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);
 }
 
 /*
Signature · 1 line
2.45.2
#36 lore raw

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

Quoted 14 lines · 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().

---
 fs/btrfs/backref.c | 71 +++++++++++++++++++++++-----------------------
 1 file changed, 36 insertions(+), 35 deletions(-)
fs/btrfs/backref.c +0 -0
index 6d9f39c1d89c..fcbcfce0f93a 100644

fs/btrfs/backref.c static int prelim_ref_compare(const struct prelim_ref *ref1, · line 257

Quoted 8 lines
fs/btrfs/backref.c +5 -0
@@ -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.

fs/btrfs/backref.c static int prelim_ref_compare(const struct prelim_ref *ref1, · line 259

Quoted 2 lines
fs/btrfs/backref.c +2 -0
+
+	result = prelim_ref_compare(ref1, ref2);

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

Quoted 4 lines
fs/btrfs/backref.c +4 -0
+
+	return result;
+}
+
#37 lore raw

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

In reply to 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().

---
 fs/btrfs/delayed-inode.c | 40 ++++++++++++++++------------------------
 1 file changed, 16 insertions(+), 24 deletions(-)
fs/btrfs/delayed-inode.c +16 -24
index 508bdbae29a0..7d62224bc49c 100644
@@ -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)
Signature · 1 line
2.45.2
#38 lore raw

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

In reply to 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().

---
 fs/btrfs/volumes.c | 39 ++++++++++++++++++---------------------
 1 file changed, 18 insertions(+), 21 deletions(-)
fs/btrfs/volumes.c +18 -21
index 1cccaf9c2b0d..4837761a56c9 100644
@@ -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);
Signature · 1 line
2.45.2
#39 lore raw

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

In reply to 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

---
 fs/btrfs/delayed-ref.c | 39 ++++++++++++++++-----------------------
 1 file changed, 16 insertions(+), 23 deletions(-)
fs/btrfs/delayed-ref.c +16 -23
index 30f7079fa28e..e288058f5c3c 100644
@@ -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;
 }
 
Signature · 1 line
2.45.2
#40 lore raw

cover reduce boilerplate code within btrfs

In reply to 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(-)
Signature · 1 line
2.45.2
#41 lore raw

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

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

---
 fs/btrfs/block-group.c | 40 +++++++++++++++++-----------------------
 1 file changed, 17 insertions(+), 23 deletions(-)
fs/btrfs/block-group.c +17 -23
index 5be029734cfa..6001b78e9ea9 100644
@@ -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;
Signature · 1 line
2.45.2
#42 lore raw

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

Quoted 58 lines · 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().

---
  fs/btrfs/block-group.c | 40 +++++++++++++++++-----------------------
  1 file changed, 17 insertions(+), 23 deletions(-)
fs/btrfs/block-group.c +13 -18
index 5be029734cfa..6001b78e9ea9 100644
@@ -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;
-		}

fs/btrfs/block-group.c void btrfs_put_block_group(struct btrfs_block_group *cache) · line 203

Quoted 10 lines
fs/btrfs/block-group.c +4 -5
-	}
-
-	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.

Quoted 3 lines
fs/btrfs/block-group.c +0 -0
  	write_unlock(&info->block_group_cache_lock);
 
  	return 0;
#43 lore raw

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

In reply to 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()

---
 fs/btrfs/backref.c | 71 +++++++++++++++++++++++-----------------------
 1 file changed, 36 insertions(+), 35 deletions(-)
fs/btrfs/backref.c +36 -35
index 6d9f39c1d89c..fcbcfce0f93a 100644
@@ -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);
 }
 
 /*
Signature · 1 line
2.45.2
#44 lore raw

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

In reply to 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()

---
 fs/btrfs/delayed-inode.c | 40 ++++++++++++++++------------------------
 1 file changed, 16 insertions(+), 24 deletions(-)
fs/btrfs/delayed-inode.c +16 -24
index 508bdbae29a0..d705049fb381 100644
@@ -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)
Signature · 1 line
2.45.2
#45 lore raw

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

In reply to 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().

---
 fs/btrfs/volumes.c | 39 ++++++++++++++++++---------------------
 1 file changed, 18 insertions(+), 21 deletions(-)
fs/btrfs/volumes.c +18 -21
index 1cccaf9c2b0d..b39723a95f26 100644
@@ -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);
Signature · 1 line
2.45.2
#46 lore raw

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

In reply to 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

---
 fs/btrfs/delayed-ref.c | 39 ++++++++++++++++-----------------------
 1 file changed, 16 insertions(+), 23 deletions(-)
fs/btrfs/delayed-ref.c +16 -23
index 30f7079fa28e..3cd122c899cc 100644
@@ -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;
 }
 
Signature · 1 line
2.45.2
#47 lore raw

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

Quoted 6 lines · 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

Quoted 61 lines
---
  fs/btrfs/delayed-ref.c | 39 ++++++++++++++++-----------------------
  1 file changed, 16 insertions(+), 23 deletions(-)
fs/btrfs/delayed-ref.c +16 -23
index 30f7079fa28e..3cd122c899cc 100644
@@ -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;
  }
 
#48 lore raw

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

Quoted 13 lines · Qu Wenruo
Quoted 6 lines · 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.

Quoted 8 lines

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.

#49 lore raw

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

Quoted 20 lines · Johannes Thumshirn
Quoted 19 lines · Qu Wenruo
Quoted 6 lines · 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.

Quoted 5 lines
Quoted 2 lines

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

#50 lore raw

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

Quoted 11 lines · Qu Wenruo
Quoted 7 lines · Johannes Thumshirn
Quoted 6 lines · Qu Wenruo
Quoted 3 lines · Roger L. Beckermeyer III

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

Quoted 6 lines
Quoted 6 lines
Quoted 6 lines
Quoted 3 lines

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.

Quoted 6 lines
Quoted 6 lines
Quoted 6 lines

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?

Quoted 14 lines
Quoted 6 lines
Quoted 3 lines

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

#51 lore raw

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

Quoted 21 lines · Lee Beckermeyer
Quoted 11 lines · Qu Wenruo
Quoted 7 lines · Johannes Thumshirn
Quoted 6 lines · Qu Wenruo
Quoted 3 lines · Roger L. Beckermeyer III

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

Quoted 6 lines
Quoted 6 lines
Quoted 6 lines
Quoted 3 lines

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.

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 8 lines
Quoted 5 lines
Quoted 5 lines
Quoted 5 lines

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"?

Quoted 17 lines

Should I not be
doing that when I send a new patch series?

Quoted 14 lines
Quoted 6 lines
Quoted 3 lines

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