reduce boilerplate code within btrfs
v3 cover reduce boilerplate code within btrfs
[Changelog]
v3:
- Fix the error handling in the 2nd patch
- Fix the backref walk failure
There are two bugs in the 3rd patch:
* Bad parent/ref pointer update
Which only get updated once at the beginning, meanwhile they should be updated only when we found an existing node.
* Order change for prelim_ref
The prelim_ref_compare() require the first parameter to be the existing ref, and the second parameter to be the new one. This is different from the new rb_find_add_cached() order
Fix both and remove unnecessary variables.
- Add named parameters for cmp() function used in rb_find_add_cached() To give a more explicit distinguish on which one should be the newer node and which should be the existing node.
This should reduce the confusion on the order.
- Unify the parameters for cmp() functions
And all internal entry structure will have corresponding "new_/exist_" prefix.
- Make all parameters of cmp() to be const
v2: By Roger L
- Fix error handing in the 2nd patch
Which is still not done correctly
- Add Acked-by tag from Peter
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.
changelog:
updated if() statements to utilize newer error checking resolved lock error on 0002
edited title of patches to utilize update instead of edit added Acked-by from Peter Zijlstra to 0001 eliminated extra variables throughout the patch series
Roger L. Beckermeyer III (6):
rbtree: add rb_find_add_cached() to rbtree.h
btrfs: update btrfs_add_block_group_cache() to use rb helper
btrfs: update prelim_ref_insert() to use rb helpers
btrfs: update __btrfs_add_delayed_item() to use rb helper
btrfs: update btrfs_add_chunk_map() to use rb helpers
btrfs: update tree_insert() to use rb helpers
fs/btrfs/backref.c | 79 ++++++++++++++++++++-------------------- fs/btrfs/block-group.c | 46 +++++++++++------------ fs/btrfs/delayed-inode.c | 43 ++++++++++------------ fs/btrfs/delayed-ref.c | 45 +++++++++-------------- fs/btrfs/volumes.c | 41 +++++++++++---------- include/linux/rbtree.h | 37 +++++++++++++++++++ 6 files changed, 156 insertions(+), 135 deletions(-)
Signature · 1 line
2.47.1
PATCH v3 1/6 rbtree: add rb_find_add_cached() to rbtree.h
From: "Roger L. Beckermeyer III" <[email protected]>
Adds rb_find_add_cached() as a helper function for use with red-black trees. Used in btrfs to reduce boilerplate code.
And since it's a new helper, the cmp() function will require both parameter to be const rb_node pointers.
--- 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)(const struct rb_node *new,const struct rb_node *exist)) +{ +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.47.1
PATCH v3 4/6 btrfs: update __btrfs_add_delayed_item() to use rb helper
In reply to Qu WenruoFrom: "Roger L. Beckermeyer III" <[email protected]>
Update __btrfs_add_delayed_item() to use rb_find_add_cached().
--- fs/btrfs/delayed-inode.c | 43 ++++++++++++++++++---------------------- 1 file changed, 19 insertions(+), 24 deletions(-)
fs/btrfs/delayed-inode.c +19 -24
@@ -366,40 +366,35 @@ static struct btrfs_delayed_item *__btrfs_lookup_delayed_item(return NULL ; } +static int btrfs_delayed_item_cmp (const struct rb_node *new, +const struct rb_node *exist) +{ +const struct btrfs_delayed_item *new_item = + rb_entry(new, struct btrfs_delayed_item, rb_node); +const struct btrfs_delayed_item *exist_item = + rb_entry(exist, struct btrfs_delayed_item, rb_node); + +if (new_item->index < exist_item->index) +return -1 ; +if (new_item->index > exist_item->index) +return 1 ; +return 0 ; +} +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) +return -EEXIST ;if (ins->type ==BTRFS_DELAYED_INSERTION_ITEM && ins->index >= delayed_node->index_cnt)
Signature · 1 line
2.47.1
PATCH v3 2/6 btrfs: update btrfs_add_block_group_cache() to use rb helper
In reply to Qu WenruoFrom: "Roger L. Beckermeyer III" <[email protected]>
Update fs/btrfs/block-group.c to use rb_find_add_cached().
--- fs/btrfs/block-group.c | 46 ++++++++++++++++++++---------------------- 1 file changed, 22 insertions(+), 24 deletions(-)
fs/btrfs/block-group.c +22 -24
@@ -173,43 +173,41 @@ void btrfs_put_block_group(struct btrfs_block_group *cache) } } +static int btrfs_bg_start_cmp (const struct rb_node *new, +const struct rb_node *exist) +{ +const struct btrfs_block_group *new_bg = + rb_entry(new, struct btrfs_block_group, cache_node); +const struct btrfs_block_group *exist_bg = + rb_entry(exist, struct btrfs_block_group, cache_node); + +if (new_bg->start < exist_bg->start) +return -1 ; +if (new_bg->start > exist_bg->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; +int ret =0 ;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) + ret = -EEXIST ;write_unlock (&info->block_group_cache_lock); -return 0 ; +return ret; }/*
Signature · 1 line
2.47.1
PATCH v3 6/6 btrfs: update tree_insert() to use rb helpers
In reply to Qu WenruoFrom: "Roger L. Beckermeyer III" <[email protected]>
Update tree_insert() to use rb_find_add_cached(). add cmp_refs_node in rb_find_add_cached() to compare.
Since we're here, also make comp_data_refs() and comp_refs() accept both parameters as const.
--- fs/btrfs/delayed-ref.c | 45 +++++++++++++++++------------------------- 1 file changed, 18 insertions(+), 27 deletions(-)
fs/btrfs/delayed-ref.c +18 -27
@@ -268,8 +268,8 @@ int btrfs_delayed_refs_rsv_refill(struct btrfs_fs_info *fs_info,/* * compare two delayed data backrefs with same bytenr and type */ -static int comp_data_refs (struct btrfs_delayed_ref_node *ref1, -struct btrfs_delayed_ref_node *ref2) +static int comp_data_refs (const struct btrfs_delayed_ref_node *ref1, +const struct btrfs_delayed_ref_node *ref2) {if (ref1->data_ref.objectid < ref2->data_ref.objectid)return -1 ;
@@ -282,8 +282,8 @@ static int comp_data_refs(struct btrfs_delayed_ref_node *ref1,return 0 ; } -static int comp_refs (struct btrfs_delayed_ref_node *ref1, -struct btrfs_delayed_ref_node *ref2, +static int comp_refs (const struct btrfs_delayed_ref_node *ref1, +const struct btrfs_delayed_ref_node *ref2,bool check_seq) {int ret =0 ;
@@ -317,34 +317,25 @@ static int comp_refs(struct btrfs_delayed_ref_node *ref1,return 0 ; } +static int cmp_refs_node (const struct rb_node *new,const struct rb_node *exist) +{ +const struct btrfs_delayed_ref_node *new_node = + rb_entry(new, struct btrfs_delayed_ref_node, ref_node); +const struct btrfs_delayed_ref_node *exist_node = + rb_entry(exist, struct btrfs_delayed_ref_node, ref_node); + +return comp_refs (new_node, exist_node, true); +} +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; +struct rb_node *exist; -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, cmp_refs_node); +if (exist) + return rb_entry(exist, struct btrfs_delayed_ref_node, ref_node);return NULL ; }
Signature · 1 line
2.47.1
PATCH v3 3/6 btrfs: update prelim_ref_insert() to use rb helpers
In reply to Qu WenruoFrom: "Roger L. Beckermeyer III" <[email protected]>
Update prelim_ref_insert() to use rb_find_add_cached().
There is a special change that the existing prelim_ref_compare() is called with the first parameter as the existing ref in the rbtree.
But the newer rb_find_add_cached() expects the cmp() function to have the first parameter as the to-be-added node, thus the new helper prelim_ref_rb_add_cmp() need to adapt this new order.
--- fs/btrfs/backref.c | 79 +++++++++++++++++++++++----------------------- 1 file changed, 39 insertions(+), 40 deletions(-)
fs/btrfs/backref.c +39 -40
@@ -250,6 +250,21 @@ static int prelim_ref_compare(const struct prelim_ref *ref1,return 0 ; } +static int prelim_ref_rb_add_cmp (const struct rb_node *new, +const struct rb_node *exist) +{ +const struct prelim_ref *ref_new = + rb_entry(new, struct prelim_ref, rbnode); +const struct prelim_ref *ref_exist = + rb_entry(exist, struct prelim_ref, rbnode); + +/* +* prelim_ref_compare() expects the first parameter as the existing one, +* different from the rb_find_add_cached() order. +*/ +return prelim_ref_compare (ref_exist, ref_new); +} +static void update_share_count (struct share_check *sc,int oldcount,int newcount,const struct prelim_ref *newref) {
@@ -278,55 +293,39 @@ static void prelim_ref_insert(const struct btrfs_fs_info *fs_info, struct share_check *sc) {struct rb_root_cached *root; -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; + exist =rb_find_add_cached (&newref->rbnode, root, prelim_ref_rb_add_cmp); +if (exist) { + struct prelim_ref *ref = rb_entry(exist, struct prelim_ref, rbnode); +/* Identical refs, merge them and free @newref */ +struct extent_inode_elem *eie = ref->inode_list; -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; +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.47.1
PATCH v3 5/6 btrfs: update btrfs_add_chunk_map() to use rb helpers
In reply to Qu WenruoFrom: "Roger L. Beckermeyer III" <[email protected]>
Update btrfs_add_chunk_map() to use rb_find_add_cached().
--- fs/btrfs/volumes.c | 41 +++++++++++++++++++++-------------------- 1 file changed, 21 insertions(+), 20 deletions(-)
fs/btrfs/volumes.c +21 -20
@@ -5514,33 +5514,34 @@ 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 (const struct rb_node *new, +const struct rb_node *exist) +{ +const struct btrfs_chunk_map *new_map = + rb_entry(new, struct btrfs_chunk_map, rb_node); +const struct btrfs_chunk_map *exist_map = + rb_entry(exist, struct btrfs_chunk_map, rb_node); + +if (new_map->start == exist_map->start) +return 0 ; +if (new_map->start < exist_map->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; + exist =rb_find_add_cached (&map->rb_node, &fs_info->mapping_tree, + btrfs_chunk_map_cmp); - 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 ; - } +if (exist) { +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.47.1
Quoted 44 lines · Qu Wenruo
[Changelog]
v3:
- Fix the error handling in the 2nd patch- Fix the backref walk failure
There are two bugs in the 3rd patch:
* Bad parent/ref pointer update
Which only get updated once at the beginning, meanwhile they should be updated only when we found an existing node.
* Order change forprelim_ref
Theprelim_ref_compare()require the first parameter to be the existing ref, and the second parameter to be the new one. This is different from the newrb_find_add_cached()order
Fix both and remove unnecessary variables.- Add named parameters for
cmp()function used inrb_find_add_cached()To give a more explicit distinguish on which one should be the newer node and which should be the existing node.
This should reduce the confusion on the order.- Unify the parameters for
cmp()functions
And all internal entry structure will have corresponding "new_/exist_" prefix.- Make all parameters of
cmp()to be constv2: By Roger L
- Fix error handing in the 2nd patch
Which is still not done correctly- Add Acked-by tag from Peter
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.changelog:
updatedif()statements to utilize newer error checking resolved lock error on 0002
edited title of patches to utilize update instead of edit added Acked-by from Peter Zijlstra to 0001 eliminated extra variables throughout the patch series
Quoted 7 lines
Roger L. Beckermeyer III (6):
rbtree: addrb_find_add_cached()torbtree.h
btrfs: updatebtrfs_add_block_group_cache()to use rb helper
btrfs: updateprelim_ref_insert()to use rb helpers
btrfs: update__btrfs_add_delayed_item()to use rb helper
btrfs: updatebtrfs_add_chunk_map()to use rb helpers
btrfs: updatetree_insert()to use rb helpers