reduce boilerplate code within btrfs
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
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
@@ -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
PATCH 1/1 btrfs: edit btrfs_add_block_group_cache() to use rb helper
In reply to Roger L. Beckermeyer IIIEdits 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
@@ -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
PATCH 1/1 btrfs: edit prelim_ref_insert() to use rb helpers
In reply to Roger L. Beckermeyer IIIThis 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
@@ -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
PATCH 1/1 btrfs: edit __btrfs_add_delayed_item() to use rb helper
In reply to Roger L. Beckermeyer IIIThis 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
@@ -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
PATCH 1/1 btrfs: edit btrfs_add_chunk_map() to use rb helpers
In reply to Roger L. Beckermeyer IIIEdits 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
@@ -5513,33 +5513,30 @@ void btrfs_remove_chunk_map(struct btrfs_fs_info *fs_info, struct btrfs_chunk_mabtrfs_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
PATCH 1/1 btrfs: edits tree_insert() to use rb helpers
In reply to Roger L. Beckermeyer IIIEdits 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
@@ -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
kernel test robot
build botRe: [PATCH] btrfs: edit __btrfs_add_delayed_item() to use rb helper
In reply to Roger L. Beckermeyer IIIkernel 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
kernel test robot
build botRe: [PATCH] btrfs: edit prelim_ref_insert() to use rb helpers
In reply to Roger L. Beckermeyer IIIkernel 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
kernel test robot
build botRe: [PATCH] btrfs: edits tree_insert() to use rb helpers
In reply to Roger L. Beckermeyer IIIkernel 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
kernel test robot
build botRe: [PATCH] btrfs: edit btrfs_add_chunk_map() to use rb helpers
In reply to Roger L. Beckermeyer IIIkernel 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
kernel test robot
build botRe: [PATCH] btrfs: edit btrfs_add_block_group_cache() to use rb helper
In reply to Roger L. Beckermeyer IIIkernel 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
kernel test robot
build botRe: [PATCH] btrfs: edit prelim_ref_insert() to use rb helpers
In reply to Roger L. Beckermeyer IIIkernel 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
kernel test robot
build botRe: [PATCH] btrfs: edit __btrfs_add_delayed_item() to use rb helper
In reply to Roger L. Beckermeyer IIIkernel 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
kernel test robot
build botRe: [PATCH] btrfs: edit btrfs_add_chunk_map() to use rb helpers
In reply to Roger L. Beckermeyer IIIkernel 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
kernel test robot
build botRe: [PATCH] btrfs: edits tree_insert() to use rb helpers
In reply to Roger L. Beckermeyer IIIkernel 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
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 tolinux/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: addrb_find_add_cached()torbtree.h
btrfs: editbtrfs_add_block_group_cache()to use rb helper
btrfs: editprelim_ref_insert()to use rb helpers
btrfs: edit__btrfs_add_delayed_item()to use rb helper
btrfs: editbtrfs_add_chunk_map()to use rb helpers
btrfs: editstree_insert()to use rb helpersfs/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(-)
kernel test robot
build botRe: [PATCH] btrfs: edits tree_insert() to use rb helpers
In reply to Roger L. Beckermeyer IIIkernel 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
Re: [PATCH] btrfs: edits tree_insert() to use rb helpers
In reply to Roger L. Beckermeyer IIIQuoted 19 lines · Roger L. Beckermeyer III
Edits
tree_insert()to userb_find_add_cached(). Also adds a comparison function for use inrb_find_add_cached()to compare.Reviewed-by Roger L. Beckermeyer III <[email protected]>Signed-off-by Roger L. Beckermeyer III <[email protected]>--- fs/btrfs/delayed-ref.c | 43 +++++++++++++++++++++--------------------- 1 file changed, 21 insertions(+), 22 deletions(-)fs/btrfs/delayed-ref.c +0
-0@@ -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
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 tolinux/include/rbtree.h. Any replaceable functions were then replaced within btrfs.
Just a few overall comments on the whole series:
1) Make sure you fix up all the kbuilder test bot things.
2) Don't add "Reviewed-by" or "Tested-by" tags to your own patches, that's for other people to do. Generally we use "Tested-by" for people who have tested a specific bug fix.
Thanks,
Josef
PATCH 1/6 rbtree: add rb_find_add_cached() to rbtree.h
In reply to Roger L. Beckermeyer IIIAdds 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
@@ -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
PATCH 2/6 btrfs: edit btrfs_add_block_group_cache() to use rb helper
In reply to Roger L. Beckermeyer IIIEdits 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
@@ -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
PATCH 3/6 btrfs: edit prelim_ref_insert() to use rb helpers
In reply to Roger L. Beckermeyer IIIThis 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
@@ -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
PATCH 4/6 btrfs: edit __btrfs_add_delayed_item() to use rb helper
In reply to Roger L. Beckermeyer IIIThis 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
@@ -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
PATCH 5/6 btrfs: edit btrfs_add_chunk_map() to use rb helpers
In reply to Roger L. Beckermeyer IIIEdits 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
@@ -5513,33 +5513,30 @@ void btrfs_remove_chunk_map(struct btrfs_fs_info *fs_info, struct btrfs_chunk_mabtrfs_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
PATCH 6/6 btrfs: edit tree_insert() to use rb helpers
In reply to Roger L. Beckermeyer IIIEdits 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
@@ -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
cover reduce boilerplate code within btrfs
In reply to Roger L. Beckermeyer IIIThe 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
Re: [PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h
In reply to Roger L. Beckermeyer IIIQuoted 14 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.Reported-by kernel test robot <[email protected]>
Don't add the Closes: tag here. It's a change between v1 and v2 which does not need to go to the git history.
Quoted 2 lines
Suggested-by Josef Bacik <[email protected]>Signed-off-by Roger L. Beckermeyer III <[email protected]>
Re: [PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h
In reply to Roger L. Beckermeyer IIIQuoted 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.Reported-by kernel test robot <[email protected]>Suggested-by Josef Bacik <[email protected]>Signed-off-by Roger L. Beckermeyer III <[email protected]>
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.
Re: [PATCH 2/6] btrfs: edit btrfs_add_block_group_cache() to use rb helper
In reply to Roger L. Beckermeyer IIIQuoted 1 line · Roger L. Beckermeyer III
Edits
fs/btrfs/block-group.cto userb_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 withrb_find_add_cached().Suggested-by Josef Bacik <[email protected]>Reviewed-by Roger L. Beckermeyer III <[email protected]>Signed-off-by Roger L. Beckermeyer III <[email protected]>--- fs/btrfs/block-group.c | 40 +++++++++++++++++----------------------- 1 file changed, 17 insertions(+), 23 deletions(-)fs/btrfs/block-group.c +0
-0
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 ; +}
Re: [PATCH 3/6] btrfs: edit prelim_ref_insert() to use rb helpers
In reply to Roger L. Beckermeyer IIIQuoted 14 lines · Roger L. Beckermeyer III
This commit edits
prelim_ref_insert()infs/btrfs/backref.cto userb_find_add_cached(). It also adds a comparison function for use withrb_find_add_cached().Signed-off-by Roger L. Beckermeyer III <[email protected]>--- fs/btrfs/backref.c | 71 +++++++++++++++++++++++----------------------- 1 file changed, 36 insertions(+), 35 deletions(-)fs/btrfs/backref.c +0
-0
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; +} +
Re: [PATCH 2/6] btrfs: edit btrfs_add_block_group_cache() to use rb helper
In reply to Roger L. Beckermeyer IIIfs/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
kernel test robot
build botRe: [PATCH] btrfs: edits tree_insert() to use rb helpers
In reply to Roger L. Beckermeyer IIIkernel 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
kernel test robot
build botRe: [PATCH] btrfs: edit __btrfs_add_delayed_item() to use rb helper
In reply to Roger L. Beckermeyer IIIkernel 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
cover reduce boilerplate code within btrfs
In reply to Roger L. Beckermeyer IIIThe 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
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
@@ -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
PATCH 3/6 btrfs: update prelim_ref_insert() to use rb helpers
In reply to Roger L. Beckermeyer IIIupdate 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
@@ -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
PATCH 4/6 btrfs: update __btrfs_add_delayed_item() to use rb helpers
In reply to Roger L. Beckermeyer IIIupdate __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
@@ -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
PATCH 5/6 btrfs: update btrfs_add_chunk_map() to use rb helpers
In reply to Roger L. Beckermeyer IIIupdate 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
@@ -5513,33 +5513,30 @@ void btrfs_remove_chunk_map(struct btrfs_fs_info *fs_info, struct btrfs_chunk_mabtrfs_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
PATCH 6/6 btrfs: update tree_insert() to use rb helpers
In reply to Roger L. Beckermeyer IIIupdate 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
@@ -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
Re: [PATCH 6/6] btrfs: update tree_insert() to use rb helpers
Quoted 6 lines · Roger L. Beckermeyer III
update
tree_insert()to userb_find_add_cached(). addcmp_refs_nodeinrb_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
Signed-off-by Roger L. Beckermeyer III <[email protected]>--- fs/btrfs/delayed-ref.c | 39 ++++++++++++++++----------------------- 1 file changed, 16 insertions(+), 23 deletions(-)fs/btrfs/delayed-ref.c +16
-23@@ -317,34 +317,27 @@ static int comp_refs(struct btrfs_delayed_ref_node *ref1,return 0 ; } +static int cmp_refs_node (struct rb_node *node,const struct rb_node *node2) +{ +struct btrfs_delayed_ref_node *ref1; +const struct btrfs_delayed_ref_node *ref2; +bool check_seq = true; + + ref1 = rb_entry(node, struct btrfs_delayed_ref_node, ref_node); + ref2 = rb_entry(node2, struct btrfs_delayed_ref_node, ref_node); + +return comp_refs (ref1, ref2, check_seq); +} +static struct btrfs_delayed_ref_node *tree_insert (struct rb_root_cached *root,struct btrfs_delayed_ref_node *ins) { -struct rb_node **p = &root->rb_root.rb_node;struct rb_node *node = &ins->ref_node; -struct rb_node *parent_node =NULL ; -struct btrfs_delayed_ref_node *entry; -bool leftmost = true; - -while (*p) { -int comp; - - parent_node = *p; - entry = rb_entry(parent_node, struct btrfs_delayed_ref_node, - ref_node); - comp =comp_refs (ins, entry, true); -if (comp <0 ) { - p = &(*p)->rb_left; - }else if (comp >0 ) { - p = &(*p)->rb_right; - leftmost = false; - }else { -return entry; - } - } +struct rb_node *exist; -rb_link_node (node, parent_node, p); -rb_insert_color_cached (node, root, leftmost); + exist =rb_find_add_cached (node, root, cmp_refs_node); +if (exist !=NULL ) + return rb_entry(exist, struct btrfs_delayed_ref_node, ref_node);return NULL ; }
Re: [PATCH 2/6] btrfs: update btrfs_add_block_group_cache() to use rb helpers
In reply to Roger L. Beckermeyer IIIQuoted 58 lines · Roger L. Beckermeyer III
update
fs/btrfs/block-group.cto userb_find_add_cached()implementbtrfs_bg_start_cmp()for use withrb_find_add_cached().Suggested-by Josef Bacik <[email protected]>Signed-off-by Roger L. Beckermeyer III <[email protected]>--- fs/btrfs/block-group.c | 40 +++++++++++++++++----------------------- 1 file changed, 17 insertions(+), 23 deletions(-)fs/btrfs/block-group.c +13
-18@@ -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
-0write_unlock (&info->block_group_cache_lock);return 0 ;
Re: [PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h
In reply to Roger L. Beckermeyer IIIQuoted 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
Suggested-by Josef Bacik <[email protected]>Signed-off-by Roger L. Beckermeyer III <[email protected]>--- include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+)include/linux/rbtree.h +2
-0@@ -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
Re: [PATCH 6/6] btrfs: update tree_insert() to use rb helpers
In reply to Qu WenruoQuoted 13 lines · Qu Wenruo
Quoted 6 lines · Roger L. Beckermeyer III
update
tree_insert()to userb_find_add_cached(). addcmp_refs_nodeinrb_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.
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 userb_find_add_cached(). addcmp_refs_nodeinrb_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
Re: [PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h
In reply to Qu WenruoQuoted 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
Suggested-by Josef Bacik <[email protected]>Signed-off-by Roger L. Beckermeyer III <[email protected]>--- include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+)include/linux/rbtree.h +2
-0@@ -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 andrb_add_cached()andrb_find_add_cached()can reuse the same function.
Nope, rb_add_cached() can add multiple entries with the same key, rb_find_add() cannot.
Also, note that all these things are effectively 'templates', they generate code at the call site. The cmp() function as required for find_add() is a tri-state return and generates more logic than the binary less() required for add().
Re: [PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h
In reply to Roger L. Beckermeyer IIIQuoted 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.Suggested-by Josef Bacik <[email protected]>Signed-off-by Roger L. Beckermeyer III <[email protected]>
Quoted 55 lines
--- include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+)include/linux/rbtree.h +37
-0@@ -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
Re: [PATCH 6/6] btrfs: update tree_insert() to use rb helpers
In reply to Qu WenruoQuoted 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 userb_find_add_cached(). addcmp_refs_nodeinrb_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
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 userb_find_add_cached(). addcmp_refs_nodeinrb_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
Re: [PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h
In reply to Peter ZijlstraQuoted 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.Suggested-by Josef Bacik <[email protected]>Signed-off-by Roger L. Beckermeyer III <[email protected]>
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@@ -210,6 +210,43 @@ rb_add(struct rb_node *node, struct rb_root *tree,rb_insert_color (node, tree); } +/** +* rb_find_add_cached() - find equivalent @node in @tree, or add @node +* @node: node to look-for / insert +* @tree: tree to search / modify +* @cmp: operator defining the node order +* +* Returns the rb_node matching @node, or NULL when no match is found and @node +* is inserted. +*/ +static __always_inline struct rb_node * +rb_find_add_cached (struct rb_node *node,struct rb_root_cached *tree, +int (*cmp)(struct rb_node *,const struct rb_node *)) +{ +bool leftmost = true; +struct rb_node **link = &tree->rb_root.rb_node; +struct rb_node *parent =NULL ; +int c; + +while (*link) { + parent = *link; + c =cmp (node, parent); + +if (c <0 ) { + link = &parent->rb_left; + }else if (c >0 ) { + link = &parent->rb_right; + leftmost = false; + }else { +return parent; + } + } + +rb_link_node (node, parent, link); +rb_insert_color_cached (node, tree, leftmost); +return NULL ; +} +/** * rb_find_add() - find equivalent @node in @tree, or add @node * @node: node to look-for / insert -- 2.45.2
Re: [PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h
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
Suggested-by Josef Bacik <[email protected]>Signed-off-by Roger L. Beckermeyer III <[email protected]>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()andless()functions, as they only accept the exist node as const.I'm wondering if this is intentional to allow the less/cmp() functions to modify the new node if needed.
As I normally assume such cmp()/less() should never touch any node nor its entries.
Oh yeah, they probably should not. I think it's just because the callchain as a whole does not have const on the new node (for obvious raisins), and I failed to put it on for the comparators.
You could add it (and fix up the whole tree) and see if anything comes apart.
Re: [PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h
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
Suggested-by Josef Bacik <[email protected]>Signed-off-by Roger L. Beckermeyer III <[email protected]>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()andless()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