btrfs: relocation: build_backref_cache() refactor part 2
cover btrfs: relocation: build_backref_cache() refactor part 2
This patchset can be fetched from:
https://github.com/adam900710/linux/tree/backref_cache_new
Since it is based on previous btrfs_backref_iter facility, it's recommended to fetch from above repo.
This patchset mostly refactors the backref handling code out of the bit loop in build_backref_cache().
Now build_backref_tree() can be easily divided into 4 small parts:
- Basic structure allocation
- Breadth-first search for backrefs
- Handling edges of upper nodes
- Removing useless nodes
Qu Wenruo (3):
btrfs: relocation: Use wrapper to replace open-coded edge linking
btrfs: relocation: Specify essential members for alloc_backref_node()
btrfs: relocation: Remove the open-coded goto loop for breadth-first
search
fs/btrfs/relocation.c | 241 ++++++++++++++++++++++++------------------ 1 file changed, 138 insertions(+), 103 deletions(-)
Signature · 1 line
2.25.1
PATCH 1/3 btrfs: relocation: Use wrapper to replace open-coded edge linking
Since backref_edge is used to connect upper and lower backref nodes, and need to access both nodes, some code can look pretty nasty:
list_add_tail(&edge->list[LOWER], &cur->upper);
The above code will link @cur to the LOWER side of the edge, while both "LOWER" and "upper" words show up.
This can sometimes be very confusing for reader to grasp.
This patch introduce a new wrapper, link_backref_edge(), to handle the linking behavior.
Which also has extra ASSERT() to ensure caller won't pass wrong nodes in.
Also, this updates the comment of related lists of backref_node and backref_edge, to make it more clear that each list points to what.
--- fs/btrfs/relocation.c | 53 ++++++++++++++++++++++++++++++------------- 1 file changed, 37 insertions(+), 16 deletions(-)
fs/btrfs/relocation.c +37 -16
@@ -44,10 +44,12 @@ struct backref_node {u64 owner;/* link to pending, changed or detached list */ struct list_head list; -/* list of upper level blocks reference this block */ + +/* List of upper level edges, which links this node to its parent(s) */ struct list_head upper; -/* list of child blocks in the cache */ +/* List of lower level edges, which links this node to its child(ren) */ struct list_head lower; +/* NULL if this node is not tree root */ struct btrfs_root *root;/* extent buffer got by COW the block */
@@ -76,17 +78,26 @@ struct backref_node { unsigned int detached:1; }; +#define LOWER 0 +#define UPPER 1 +#define RELOCATION_RESERVED_NODES 256/* -* present a block pointer in the backref cache +* present an edge connecting upper and lower backref nodes. */ struct backref_edge { +/* +* list[LOWER] is linked to backref_node::upper of lower level node, +* and list[UPPER] is linked to backref_node::lower of upper level node. +* +* Also, build_backref_tree() uses list[UPPER] for pending edges, before +* linking list[UPPER] to its upper level nodes. +*/ struct list_head list[2 ]; + +/* Two related nodes */ struct backref_node *node[2 ]; }; -#define LOWER 0 -#define UPPER 1 -#define RELOCATION_RESERVED_NODES 256struct backref_cache {/* red black tree of all backref nodes in the cache */
@@ -297,6 +308,22 @@ static struct backref_edge *alloc_backref_edge(struct backref_cache *cache)return edge; } +#define LINK_LOWER (1 << 0) +#define LINK_UPPER (1 << 1) +static inline void link_backref_edge (struct backref_edge *edge, +struct backref_node *lower, +struct backref_node *upper, +int link_which) +{ +ASSERT (upper && lower && upper->level == lower->level +1 ); + edge->node[LOWER ] = lower; + edge->node[UPPER ] = upper; +if (link_which &LINK_LOWER ) +list_add_tail (&edge->list[LOWER ], &lower->upper); +if (link_which &LINK_UPPER ) +list_add_tail (&edge->list[UPPER ], &upper->lower); +} +static void free_backref_edge (struct backref_cache *cache,struct backref_edge *edge) {
@@ -693,9 +720,7 @@ static int handle_one_tree_backref(struct reloc_control *rc,ASSERT (upper->checked);INIT_LIST_HEAD (&edge->list[UPPER ]); } -list_add_tail (&edge->list[LOWER ], &cur->upper); - edge->node[LOWER ] = cur; - edge->node[UPPER ] = upper; +link_backref_edge (edge, cur, upper,LINK_LOWER );return 0 ; }
@@ -806,9 +831,7 @@ static int handle_one_tree_backref(struct reloc_control *rc,if (!upper->owner) upper->owner =btrfs_header_owner (eb); } -list_add_tail (&edge->list[LOWER ], &lower->upper); - edge->node[LOWER ] = lower; - edge->node[UPPER ] = upper; +link_backref_edge (edge, lower, upper,LINK_LOWER );if (rb_node)break ;
@@ -1199,10 +1222,8 @@ static int clone_backref_node(struct btrfs_trans_handle *trans,if (!new_edge) goto fail; - new_edge->node[UPPER ] = new_node; - new_edge->node[LOWER ] = edge->node[LOWER ]; -list_add_tail (&new_edge->list[UPPER ], - &new_node->lower); +link_backref_edge (new_edge, edge->node[LOWER ], new_node, +LINK_UPPER ); } }else {list_add_tail (&new_node->lower, &cache->leaves);
Signature · 1 line
2.25.1
Re: [PATCH 1/3] btrfs: relocation: Use wrapper to replace open-coded edge linking
Quoted 14 lines · Qu Wenruo
Since
backref_edgeis used to connect upper and lower backref nodes, and need to access both nodes, some code can look pretty nasty:list_add_tail(&edge->list[LOWER], &cur->upper);The above code will link @cur to the LOWER side of the edge, while both "LOWER" and "upper" words show up.
This can sometimes be very confusing for reader to grasp.This patch introduce a new wrapper,
link_backref_edge(), to handle the linking behavior.
Which also has extraASSERT()to ensure caller won't pass wrong nodes in.
Quoted 4 lines
Also, this updates the comment of related lists of
backref_nodeandbackref_edge, to make it more clear that each list points to what.Signed-off-by Qu Wenruo <[email protected]>
Thanks,
Josef
PATCH 2/3 btrfs: relocation: Specify essential members for alloc_backref_node()
In reply to Qu WenruoBytenr and level are essential parameters for backref_node, thus it makes sense to initial them at alloc time.
--- fs/btrfs/relocation.c | 25 ++++++++++++------------- 1 file changed, 12 insertions(+), 13 deletions(-)
fs/btrfs/relocation.c +12 -13
@@ -274,10 +274,12 @@ static void backref_cache_cleanup(struct backref_cache *cache)ASSERT (!cache->nr_edges); } -static struct backref_node *alloc_backref_node (struct backref_cache *cache) +static struct backref_node *alloc_backref_node (struct backref_cache *cache, +u64 bytenr,int level) {struct backref_node *node; +ASSERT (level >=0 && level <BTRFS_MAX_LEVEL ); node =kzalloc (sizeof (*node),GFP_NOFS );if (node) {INIT_LIST_HEAD (&node->list);
@@ -285,6 +287,9 @@ static struct backref_node *alloc_backref_node(struct backref_cache *cache)INIT_LIST_HEAD (&node->lower);RB_CLEAR_NODE (&node->rb_node); cache->nr_nodes++; + + node->level = level; + node->bytenr = bytenr; }return node; }
@@ -701,13 +706,12 @@ static int handle_one_tree_backref(struct reloc_control *rc, rb_node =tree_search (&cache->rb_root, ref_key->offset);if (!rb_node) {/* Parent node not yet cached */ - upper =alloc_backref_node (cache); + upper =alloc_backref_node (cache, ref_key->offset, + cur->level +1 );if (!upper) {free_backref_edge (cache, edge);return -ENOMEM ; } - upper->bytenr = ref_key->offset; - upper->level = cur->level +1 ;/* * backrefs for the upper level block isn't
@@ -788,15 +792,14 @@ static int handle_one_tree_backref(struct reloc_control *rc, eb = path->nodes[level]; rb_node =tree_search (&cache->rb_root, eb->start);if (!rb_node) { - upper =alloc_backref_node (cache); + upper =alloc_backref_node (cache, eb->start, + lower->level +1 );if (!upper) {free_backref_edge (cache, edge); ret = -ENOMEM ; goto out; } - upper->bytenr = eb->start; upper->owner =btrfs_header_owner (eb); - upper->level = lower->level +1 ;if (!test_bit (BTRFS_ROOT_REF_COWS , &root->state)) upper->cowonly =1 ;
@@ -888,14 +891,12 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, } path->reada =READA_FORWARD ; - node =alloc_backref_node (cache); + node =alloc_backref_node (cache, bytenr, level);if (!node) { err = -ENOMEM ; goto out; } - node->bytenr = bytenr; - node->level = level; node->lowest =1 ; cur = node; again:
@@ -1206,12 +1207,10 @@ static int clone_backref_node(struct btrfs_trans_handle *trans,if (!node)return 0 ; - new_node =alloc_backref_node (cache); + new_node =alloc_backref_node (cache, dest->node->start, node->level);if (!new_node)return -ENOMEM ; - new_node->bytenr = dest->node->start; - new_node->level = node->level; new_node->lowest = node->lowest; new_node->checked =1 ; new_node->root = dest;
Signature · 1 line
2.25.1
Re: [PATCH 2/3] btrfs: relocation: Specify essential members for alloc_backref_node()
Quoted 4 lines · Qu Wenruo
Bytenr and level are essential parameters for
backref_node, thus it makes sense to initial them at alloc time.Signed-off-by Qu Wenruo <[email protected]>
Thanks,
Josef
PATCH 3/3 btrfs: relocation: Remove the open-coded goto loop for breadth-first search
In reply to Qu Wenruobuild_backref_tree() uses "goto again;" to implement a breadth-first search to build backref cache.
This patch will extract most of its work into a wrapper, handle_one_tree_block(), and use a while() loop to implement the same thing.
--- fs/btrfs/relocation.c | 165 +++++++++++++++++++++++------------------- 1 file changed, 90 insertions(+), 75 deletions(-)
fs/btrfs/relocation.c +90 -75
@@ -846,65 +846,21 @@ static int handle_one_tree_backref(struct reloc_control *rc,return ret; } -/* -* build backref tree for a given tree block. root of the backref tree -* corresponds the tree block, leaves of the backref tree correspond -* roots of b-trees that reference the tree block. -* -* the basic idea of this function is check backrefs of a given block -* to find upper level blocks that reference the block, and then check -* backrefs of these upper level blocks recursively. the recursion stop -* when tree root is reached or backrefs for the block is cached. -* -* NOTE: if we find backrefs for a block are cached, we know backrefs -* for all upper level blocks that directly/indirectly reference the -* block are also cached. -*/ -static noinline_for_stack -struct backref_node *build_backref_tree(struct reloc_control *rc, -struct btrfs_key *node_key, -int level,u64 bytenr) +static int handle_one_tree_block (struct reloc_control *rc, +struct list_head *useless_node, +struct list_head *pending_edge, +struct btrfs_path *path, +struct btrfs_backref_iter *iter, +struct btrfs_key *node_key, +struct backref_node *cur) { -struct btrfs_backref_iter *iter; -struct backref_cache *cache = &rc->backref_cache; -struct btrfs_path *path;/* For searching parent of TREE_BLOCK_REF */ -struct backref_node *cur; -struct backref_node *upper; -struct backref_node *lower; -struct backref_node *node =NULL ; -struct backref_node *exist =NULL ;struct backref_edge *edge; -struct rb_node *rb_node; -LIST_HEAD (list);/* Pending edge list, upper node needs to be checked */ -LIST_HEAD (useless); -int cowonly; +struct backref_node *exist;int ret; -int err =0 ; - - iter =btrfs_backref_iter_alloc (rc->extent_root->fs_info,GFP_NOFS ); -if (!iter) -return ERR_PTR (-ENOMEM ); - path =btrfs_alloc_path (); -if (!path) { - err = -ENOMEM ; - goto out; - } - path->reada =READA_FORWARD ; - - node =alloc_backref_node (cache, bytenr, level); -if (!node) { - err = -ENOMEM ; - goto out; - } - node->lowest =1 ; - cur = node; -again: ret =btrfs_backref_iter_start (iter, cur->bytenr); -if (ret <0 ) { - err = ret; - goto out; - } +if (ret <0 ) +return ret;/* * We skip the first btrfs_tree_block_info, as we don't use the key
@@ -912,13 +868,11 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,*/ if (btrfs_backref_has_tree_block_info (iter)) { ret =btrfs_backref_iter_next (iter); -if (ret <0 ) { - err = ret; +if (ret <0 ) goto out; - }/* No extra backref? This means the tree block is corrupted */ if (ret >0 ) { - err = -EUCLEAN ; + ret = -EUCLEAN ; goto out; } }
@@ -938,7 +892,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,* check its backrefs */ if (!exist->checked) -list_add_tail (&edge->list[UPPER ], &list); +list_add_tail (&edge->list[UPPER ], pending_edge); }else { exist =NULL ; }
@@ -960,7 +914,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, type =btrfs_get_extent_inline_ref_type (eb, iref,BTRFS_REF_TYPE_BLOCK );if (type ==BTRFS_REF_TYPE_INVALID ) { - err = -EUCLEAN ; + ret = -EUCLEAN ; goto out; } key.type = type;
@@ -983,29 +937,90 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,continue ; } - ret =handle_one_tree_backref (rc, &useless, &list, path, + ret =handle_one_tree_backref (rc, useless_node, pending_edge, path, &key, node_key, cur); -if (ret <0 ) { - err = ret; +if (ret <0 ) goto out; - } } -if (ret <0 ) { - err = ret; +if (ret <0 ) goto out; - } ret =0 ; -btrfs_backref_iter_release (iter); - cur->checked =1 ;WARN_ON (exist); +out: +btrfs_backref_iter_release (iter); +return ret; +} -/* the pending list isn't empty, take the first block to process */ -if (!list_empty (&list)) { - edge = list_entry(list.next, struct backref_edge, list[UPPER]); -list_del_init (&edge->list[UPPER ]); - cur = edge->node[UPPER ]; - goto again; +/* +* build backref tree for a given tree block. root of the backref tree +* corresponds the tree block, leaves of the backref tree correspond +* roots of b-trees that reference the tree block. +* +* the basic idea of this function is check backrefs of a given block +* to find upper level blocks that reference the block, and then check +* backrefs of these upper level blocks recursively. the recursion stop +* when tree root is reached or backrefs for the block is cached. +* +* NOTE: if we find backrefs for a block are cached, we know backrefs +* for all upper level blocks that directly/indirectly reference the +* block are also cached. +*/ +static noinline_for_stack +struct backref_node *build_backref_tree(struct reloc_control *rc, +struct btrfs_key *node_key, +int level,u64 bytenr) +{ +struct btrfs_backref_iter *iter; +struct backref_cache *cache = &rc->backref_cache; +struct btrfs_path *path;/* For searching parent of TREE_BLOCK_REF */ +struct backref_node *cur; +struct backref_node *upper; +struct backref_node *lower; +struct backref_node *node =NULL ; +struct backref_edge *edge; +struct rb_node *rb_node; +LIST_HEAD (list);/* Pending edge list, upper node needs to be checked */ +LIST_HEAD (useless); +int cowonly; +int ret; +int err =0 ; + + iter =btrfs_backref_iter_alloc (rc->extent_root->fs_info,GFP_NOFS ); +if (!iter) +return ERR_PTR (-ENOMEM ); + path =btrfs_alloc_path (); +if (!path) { + err = -ENOMEM ; + goto out; + } + path->reada =READA_FORWARD ; + + node =alloc_backref_node (cache, bytenr, level); +if (!node) { + err = -ENOMEM ; + goto out; + } + + node->lowest =1 ; + cur = node; + +/* Breadth-first search to build backref cache */ +while (1 ) { + ret =handle_one_tree_block (rc, &useless, &list, path, iter, + node_key, cur); +if (ret <0 ) { + err = ret; + goto out; + } +/* the pending list isn't empty, take the first block to process */ +if (!list_empty (&list)) { + edge = list_entry(list.next, struct backref_edge, list[UPPER]); +list_del_init (&edge->list[UPPER ]); + cur = edge->node[UPPER ]; + }else { +break ; + } }/*
Signature · 1 line
2.25.1
Re: [PATCH 3/3] btrfs: relocation: Remove the open-coded goto loop for breadth-first search
Quoted 8 lines · Qu Wenruo
build_backref_tree()uses "goto again;" to implement a breadth-first search to build backref cache.This patch will extract most of its work into a wrapper,
handle_one_tree_block(), and use awhile()loop to implement the same thing.Signed-off-by Qu Wenruo <[email protected]>
Do you have this in a tree somewhere that I can look at it? I tried applying these but they don't apply cleanly to anything I have, and it's hard to review this one without seeing how the code ends up after your diff. Thanks,
Josef
Re: [PATCH 3/3] btrfs: relocation: Remove the open-coded goto loop for breadth-first search
Quoted 8 lines · Josef Bacik
Quoted 7 lines · Qu Wenruo
build_backref_tree()uses "goto again;" to implement a breadth-first search to build backref cache.This patch will extract most of its work into a wrapper,
handle_one_tree_block(), and use awhile()loop to implement the same thing.
Quoted 6 lines
Quoted 1 line
Signed-off-by Qu Wenruo <[email protected]>Do you have this in a tree somewhere that I can look at it? I tried applying these but they don't apply cleanly to anything I have, and it's hard to review this one without seeing how the code ends up after your diff. Thanks,
Sure, here you go:
https://github.com/adam900710/linux/tree/backref_cache_new
But please ignore the latest 1 or 2 commits, as they are still under development.
Every submitted patches will not undergo any extra modification in that branch.
Thanks,
Qu
Quoted 2 lines
Josef
Re: [PATCH 3/3] btrfs: relocation: Remove the open-coded goto loop for breadth-first search
Quoted 18 lines · Qu Wenruo
Quoted 8 lines · Josef Bacik
Quoted 7 lines · Qu Wenruo
build_backref_tree()uses "goto again;" to implement a breadth-first search to build backref cache.This patch will extract most of its work into a wrapper,
handle_one_tree_block(), and use awhile()loop to implement the same thing.Quoted 6 lines
Quoted 1 line
Signed-off-by Qu Wenruo <[email protected]>Do you have this in a tree somewhere that I can look at it? I tried applying these but they don't apply cleanly to anything I have, and it's hard to review this one without seeing how the code ends up after your diff. Thanks,
Quoted 8 lines
Sure, here you go:
https://github.com/adam900710/linux/tree/backref_cache_newBut please ignore the latest 1 or 2 commits, as they are still under development.
Every submitted patches will not undergo any extra modification in that branch.
Except this commit, "btrfs: relocation: Rename mark_block_processed() and __mark_block_processed()", Nikolay had some pretty good advice on it, and it's updated to address his comment.
Thanks,
Qu
Quoted 7 lines
Thanks,
QuQuoted 2 lines
Josef