btrfs: Move generic backref cache build functions to backref.c
cover btrfs: Move generic backref cache build functions to backref.c
The patchset is based on previous backref_cache_refactor branch, which is further based on misc-next.
The whole series can be fetched from github:
https://github.com/adam900710/linux/tree/backref_cache_code_move
All the patches in previous branch is not touched at all, thus they are not re-sent in this patchset.
Currently there are 3 major parts of build_backref_tree():
- ITERATION
This will do a breadth-first search, starts from the target bytenr, and queue all parents into the backref cache.
The result is a temporary map, which is only single-directional, and involved new backref nodes are not yet inserted into the cache.
- WEAVING
Finish the map to make it bi-directional, and insert new nodes into the cache.
- CLEANUP
Cleanup the useless nodes, either remove it completely or add them into the cache as detached.
For the ITERATION part, there are only limited locations coupled with relocation.
And WEAVING part is completely independent from relocation. While the CLEANUP part, although it has some relocation related code, it's not a big hunk of code after all.
So, this patchset will move the ITERATION part, extracted as backref_cache_add_one_tree_block(), and the WEAVING part, extracted as backref_cache_finish_upper_links(), to backref.c, as the basis for later reuse of backref_cache.
Qu Wenruo (19):
btrfs: Move backref node/edge/cache structure to backref.h
btrfs: Rename tree_entry to simple_node and export it
btrfs: relocation: Make reloc root search specific for relocation
backref cache
btrfs: relocation: Add backref_cache::pending_edge and
backref_cache::useless_node members
btrfs: relocation: Add backref_cache::fs_info member
btrfs: Move backref_cache_init() to backref.c
btrfs: Move alloc_backref_node() to backref.c
btrfs: Move alloc_backref_edge() to backref.c
btrfs: Move link_backref_edge() to backref.c
btrfs: Move free_backref_node() and free_backref_edge() to backref.h
btrfs: Move drop_backref_node() and needed facilities to backref.h
btrfs: Rename remove_backref_node() to cleanup_backref_node() and move
it to backref.c
btrfs: Move backref_cache_cleanup() to backref.c
btrfs: Rename backref_tree_panic() to backref_cache_panic(), and move
it to backref.c
btrfs: Rename should_ignore_root() to should_ignore_reloc_root() and
export it
btrfs: relocation: Open-code read_fs_root() for
handle_one_tree_backref()
btrfs: Rename handle_one_tree_block() to
backref_cache_add_one_tree_block() and move it to backref.c
btrfs: relocation: Move the target backref node insert code into
finish_upper_links()
btrfs: Rename finish_upper_links() to
backref_cache_finish_upper_links() and move it to backref.c
fs/btrfs/backref.c | 534 ++++++++++++++++++++++++++ fs/btrfs/backref.h | 226 +++++++++++ fs/btrfs/ctree.h | 3 + fs/btrfs/misc.h | 54 +++ fs/btrfs/relocation.c | 870 ++++-------------------------------------- 5 files changed, 892 insertions(+), 795 deletions(-)
Signature · 1 line
2.25.1
PATCH 1/19 btrfs: Move backref node/edge/cache structure to backref.h
These 3 structures are the main part of backref cache, move them to backref.h to build the basis for later reuse.
--- fs/btrfs/backref.h | 98 +++++++++++++++++++++++++++++++++++++++++++ fs/btrfs/relocation.c | 93 +--------------------------------------- 2 files changed, 100 insertions(+), 91 deletions(-)
fs/btrfs/backref.h +98 -0
@@ -168,4 +168,102 @@ btrfs_backref_iter_release(struct btrfs_backref_iter *iter) memset(&iter->cur_key, 0, sizeof(iter->cur_key)); } +/* +* Backref cache related structures. +* +* The whole objective of backref_cache is to build a bi-directional map +* of tree blocks (represented by backref_node) and all their parents. +*/ + +/* +* present a tree block in the backref cache +*/ +struct backref_node { +struct rb_node rb_node; +u64 bytenr; + +u64 new_bytenr; +/* objectid of tree block owner, can be not uptodate */ +u64 owner; +/* link to pending, changed or detached list */ +struct list_head list; + +/* List of upper level edges, which links this node to its parent(s) */ +struct list_head upper; +/* 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 */ +struct extent_buffer *eb; +/* level of tree block */ +unsigned int level:8 ; +/* is the block in non-reference counted tree */ +unsigned int cowonly:1 ; +/* 1 if no child node in the cache */ +unsigned int lowest:1 ; +/* is the extent buffer locked */ +unsigned int locked:1 ; +/* has the block been processed */ +unsigned int processed:1 ; +/* have backrefs of this block been checked */ +unsigned int checked:1 ; +/* +* 1 if corresponding block has been cowed but some upper +* level block pointers may not point to the new location +*/ +unsigned int pending:1 ; +/* +* 1 if the backref node isn't connected to any other +* backref node. +*/ +unsigned int detached:1 ; +}; + +#define LOWER 0 +#define UPPER 1 + +/* +* 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 ]; +}; + + +struct backref_cache { +/* red black tree of all backref nodes in the cache */ +struct rb_root rb_root; +/* for passing backref nodes to btrfs_reloc_cow_block */ +struct backref_node *path[BTRFS_MAX_LEVEL ]; +/* +* list of blocks that have been cowed but some block +* pointers in upper level blocks may not reflect the +* new location +*/ +struct list_head pending[BTRFS_MAX_LEVEL ]; +/* list of backref nodes with no child node */ +struct list_head leaves; +/* list of blocks that have been cowed in current transaction */ +struct list_head changed; +/* list of detached backref node. */ +struct list_head detached; + +u64 last_trans; + +int nr_nodes; +int nr_edges; +}; +#endif
fs/btrfs/relocation.c +2 -91
105 lines not on this page · raw message
Signature · 1 line
2.25.1
PATCH 2/19 btrfs: Rename tree_entry to simple_node and export it
In reply to Qu WenruoStructure tree_entry provides a very simple rb_tree which only uses bytenr as search index.
That tree_entry is used in 3 structures: backref_node, mapping_node and tree_block.
Since we're going to make backref_node independnt from relocation, it's a good time to extract the tree_entry into simple_node, and export it into misc.h.
--- fs/btrfs/backref.h | 6 ++- fs/btrfs/misc.h | 54 +++++++++++++++++++++ fs/btrfs/relocation.c | 109 ++++++++++++++---------------------------- 3 files changed, 94 insertions(+), 75 deletions(-)
fs/btrfs/backref.h +4 -2
@@ -179,8 +179,10 @@ btrfs_backref_iter_release(struct btrfs_backref_iter *iter)* present a tree block in the backref cache */ struct backref_node { -struct rb_node rb_node; -u64 bytenr; +struct { +struct rb_node rb_node; +u64 bytenr; + };/* Use simple_node for search/insert */ u64 new_bytenr;/* objectid of tree block owner, can be not uptodate */
fs/btrfs/misc.h +54 -0
64 lines not on this page · raw message
fs/btrfs/relocation.c +36 -73
241 lines not on this page · raw message
Signature · 1 line
2.25.1
PATCH 3/19 btrfs: relocation: Make reloc root search specific for relocation backref cache
In reply to Qu Wenruofind_reloc_root() searches reloc_control::reloc_root_tree to find the reloc root.
This behavior is only useful for relocation backref cache.
For the incoming more generic purposed backref cache, we don't care about who owns the reloc root, but only care if it's a reloc root.
So this patch makes the following modifications to make the reloc root search more specific to relocation backref:
- Add backref_node::is_reloc_root
This will be an extra indicator for generic purposed backref cache. User doesn't need to read root key from backref_node::root to determine if it's a reloc root.
- Add backref_cache::is_reloc
This will allow backref cache code to do different behavior for generic purposed backref cache and relocation backref cache.
- Make find_reloc_root() to accept fs_info
Just a personal taste.
- Export find_reloc_root()
So backref.c can utilize this function.
--- fs/btrfs/backref.h | 14 ++++++++++++++ fs/btrfs/ctree.h | 2 ++ fs/btrfs/relocation.c | 23 +++++++++++++++-------- 3 files changed, 31 insertions(+), 8 deletions(-)
fs/btrfs/backref.h +14 -0
@@ -221,6 +221,12 @@ struct backref_node {* backref node. */ unsigned int detached:1; + +/* +* For generic purpose backref cache, where we only care if it's a reloc +* root, doesn't care the source subvolid. +*/ + unsigned int is_reloc_root:1; };#define LOWER 0
@@ -266,6 +272,14 @@ struct backref_cache {int nr_nodes;int nr_edges; + +/* +* Whether this cache is for relocation +* +* Reloction backref cache require more info for reloc root compared +* to generic backref cache. +*/ + unsigned int is_reloc; };#endif
fs/btrfs/ctree.h +2 -0
@@ -3381,6 +3381,8 @@ void btrfs_reloc_pre_snapshot(struct btrfs_pending_snapshot *pending, u64 *bytes_to_reserve);int btrfs_reloc_post_snapshot (struct btrfs_trans_handle *trans,struct btrfs_pending_snapshot *pending); +struct btrfs_root *find_reloc_root (struct btrfs_fs_info *fs_info, +u64 bytenr);/* scrub.c */ int btrfs_scrub_dev(struct btrfs_fs_info *fs_info, u64 devid, u64 start,
fs/btrfs/relocation.c +15 -8
@@ -185,7 +185,7 @@ static void mapping_tree_init(struct mapping_tree *tree)spin_lock_init (&tree->lock); } -static void backref_cache_init (struct backref_cache *cache) +static void backref_cache_init (struct backref_cache *cache,int is_reloc) {int i; cache->rb_root =RB_ROOT ;
@@ -194,6 +194,7 @@ static void backref_cache_init(struct backref_cache *cache)INIT_LIST_HEAD (&cache->changed);INIT_LIST_HEAD (&cache->detached);INIT_LIST_HEAD (&cache->leaves); + cache->is_reloc = is_reloc; }static void backref_cache_cleanup (struct backref_cache *cache)
@@ -543,13 +544,15 @@ static int should_ignore_root(struct btrfs_root *root)/* * find reloc tree by address of tree root */ -static struct btrfs_root *find_reloc_root (struct reloc_control *rc, -u64 bytenr) +struct btrfs_root *find_reloc_root (struct btrfs_fs_info *fs_info, +u64 bytenr) { +struct reloc_control *rc = fs_info->reloc_ctl;struct rb_node *rb_node;struct mapping_node *node;struct btrfs_root *root =NULL ; +ASSERT (rc);spin_lock (&rc->reloc_root_tree.lock); rb_node =simple_search (&rc->reloc_root_tree.rb_root, bytenr);if (rb_node) {
@@ -601,10 +604,14 @@ static int handle_one_tree_backref(struct reloc_control *rc,/* Only reloc root uses backref pointing to itself */ if (ref_key->objectid == ref_key->offset) { - root =find_reloc_root (rc, cur->bytenr); -if (WARN_ON (!root)) -return -ENOENT ; - cur->root = root; + cur->is_reloc_root =1 ; +/* Only reloc backref cache cares exact root */ +if (cache->is_reloc) { + root =find_reloc_root (fs_info, cur->bytenr); +if (WARN_ON (!root)) +return -ENOENT ; + cur->root = root; + }return 0 ; }
@@ -4292,7 +4299,7 @@ static struct reloc_control *alloc_reloc_control(struct btrfs_fs_info *fs_info)INIT_LIST_HEAD (&rc->reloc_roots);INIT_LIST_HEAD (&rc->dirty_subvol_roots); -backref_cache_init (&rc->backref_cache); +backref_cache_init (&rc->backref_cache,1 );mapping_tree_init (&rc->reloc_root_tree);extent_io_tree_init (fs_info, &rc->processed_blocks,IO_TREE_RELOC_BLOCKS ,NULL );
Signature · 1 line
2.25.1
PATCH 4/19 btrfs: relocation: Add backref_cache::pending_edge and backref_cache::useless_node members
In reply to Qu WenruoThese two new members will act the same as the existing local lists, @useless and @list in build_backref_tree().
This would kill two parameters for handle_one_tree_backref(), handle_one_tree_block(), finish_upper_links() and handle_useless_nodes().
Currently build_backref_tree() is only executed serially, thus moving such local list into backref_cache is still safe.
--- fs/btrfs/backref.h | 6 ++++ fs/btrfs/relocation.c | 64 ++++++++++++++++++++++++------------------- 2 files changed, 42 insertions(+), 28 deletions(-)
fs/btrfs/backref.h +6 -0
@@ -280,6 +280,12 @@ struct backref_cache {* to generic backref cache. */ unsigned int is_reloc; + +/* The list of unchecked backref edges during backref cache build */ +struct list_head pending_edge; + +/* The list of useless backref nodes during backref cache build */ + struct list_head useless_node; };#endif
fs/btrfs/relocation.c +36 -28
190 lines not on this page · raw message
Signature · 1 line
2.25.1
PATCH 5/19 btrfs: relocation: Add backref_cache::fs_info member
In reply to Qu WenruoAdd this member so that we can grab fs_info without the help from reloc_control.
--- fs/btrfs/backref.h | 2 ++ fs/btrfs/relocation.c | 18 +++++++++--------- 2 files changed, 11 insertions(+), 9 deletions(-)
fs/btrfs/backref.h +2 -0
@@ -286,6 +286,8 @@ struct backref_cache {/* The list of useless backref nodes during backref cache build */ struct list_head useless_node; + + struct btrfs_fs_info *fs_info; };#endif
fs/btrfs/relocation.c +9 -9
@@ -185,10 +185,12 @@ static void mapping_tree_init(struct mapping_tree *tree)spin_lock_init (&tree->lock); } -static void backref_cache_init (struct backref_cache *cache,int is_reloc) +static void backref_cache_init (struct btrfs_fs_info *fs_info, +struct backref_cache *cache,int is_reloc) {int i; cache->rb_root =RB_ROOT ; + cache->fs_info = fs_info;for (i =0 ; i <BTRFS_MAX_LEVEL ; i++)INIT_LIST_HEAD (&cache->pending[i]);INIT_LIST_HEAD (&cache->changed);
@@ -579,14 +581,13 @@ static struct btrfs_root *read_fs_root(struct btrfs_fs_info *fs_info,return btrfs_get_fs_root (fs_info, &key, false); } -static int handle_one_tree_backref (struct reloc_control *rc, +static int handle_one_tree_backref (struct backref_cache *cache,struct btrfs_path *path,struct btrfs_key *ref_key,struct btrfs_key *tree_key,struct backref_node *cur) { -struct btrfs_fs_info *fs_info = rc->extent_root->fs_info; -struct backref_cache *cache = &rc->backref_cache; +struct btrfs_fs_info *fs_info = cache->fs_info;struct list_head *useless_node = &cache->useless_node;struct list_head *pending_edge = &cache->pending_edge;struct backref_node *upper;
@@ -777,13 +778,12 @@ static int handle_one_tree_backref(struct reloc_control *rc,return ret; } -static int handle_one_tree_block (struct reloc_control *rc, +static int handle_one_tree_block (struct backref_cache *cache,struct btrfs_path *path,struct btrfs_backref_iter *iter,struct btrfs_key *node_key,struct backref_node *cur) { -struct backref_cache *cache = &rc->backref_cache;struct backref_edge *edge;struct backref_node *exist;int ret;
@@ -867,7 +867,7 @@ static int handle_one_tree_block(struct reloc_control *rc,continue ; } - ret =handle_one_tree_backref (rc, path, &key, node_key, cur); + ret =handle_one_tree_backref (cache, path, &key, node_key, cur);if (ret <0 ) goto out; }
@@ -1109,7 +1109,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,/* Breadth-first search to build backref cache */ while (1 ) { - ret =handle_one_tree_block (rc, path, iter, node_key, cur); + ret =handle_one_tree_block (cache, path, iter, node_key, cur);if (ret <0 ) { err = ret; goto out;
@@ -4307,7 +4307,7 @@ static struct reloc_control *alloc_reloc_control(struct btrfs_fs_info *fs_info)INIT_LIST_HEAD (&rc->reloc_roots);INIT_LIST_HEAD (&rc->dirty_subvol_roots); -backref_cache_init (&rc->backref_cache,1 ); +backref_cache_init (fs_info, &rc->backref_cache,1 );mapping_tree_init (&rc->reloc_root_tree);extent_io_tree_init (fs_info, &rc->processed_blocks,IO_TREE_RELOC_BLOCKS ,NULL );
Signature · 1 line
2.25.1
PATCH 6/19 btrfs: Move backref_cache_init() to backref.c
In reply to Qu Wenruo--- fs/btrfs/backref.c | 16 ++++++++++++++++ fs/btrfs/backref.h | 2 ++ fs/btrfs/relocation.c | 16 ---------------- 3 files changed, 18 insertions(+), 16 deletions(-)
fs/btrfs/backref.c +16 -0
@@ -2444,3 +2444,19 @@ int btrfs_backref_iter_next(struct btrfs_backref_iter *iter) path->slots[0]);return 0 ; } + +void backref_cache_init (struct btrfs_fs_info *fs_info, +struct backref_cache *cache,int is_reloc) +{ +int i; + cache->rb_root =RB_ROOT ; + cache->fs_info = fs_info; +for (i =0 ; i <BTRFS_MAX_LEVEL ; i++) +INIT_LIST_HEAD (&cache->pending[i]); +INIT_LIST_HEAD (&cache->changed); +INIT_LIST_HEAD (&cache->detached); +INIT_LIST_HEAD (&cache->leaves); + cache->is_reloc = is_reloc; +INIT_LIST_HEAD (&cache->pending_edge); +INIT_LIST_HEAD (&cache->useless_node); +}
fs/btrfs/backref.h +2 -0
@@ -290,4 +290,6 @@ struct backref_cache { struct btrfs_fs_info *fs_info; }; +void backref_cache_init (struct btrfs_fs_info *fs_info, +struct backref_cache *cache,int is_reloc);#endif
fs/btrfs/relocation.c +0 -16
@@ -185,22 +185,6 @@ static void mapping_tree_init(struct mapping_tree *tree)spin_lock_init (&tree->lock); } -static void backref_cache_init (struct btrfs_fs_info *fs_info, -struct backref_cache *cache,int is_reloc) -{ -int i; - cache->rb_root =RB_ROOT ; - cache->fs_info = fs_info; -for (i =0 ; i <BTRFS_MAX_LEVEL ; i++) -INIT_LIST_HEAD (&cache->pending[i]); -INIT_LIST_HEAD (&cache->changed); -INIT_LIST_HEAD (&cache->detached); -INIT_LIST_HEAD (&cache->leaves); - cache->is_reloc = is_reloc; -INIT_LIST_HEAD (&cache->pending_edge); -INIT_LIST_HEAD (&cache->useless_node); -} -static void backref_cache_cleanup (struct backref_cache *cache) {struct backref_node *node;
Signature · 1 line
2.25.1
PATCH 7/19 btrfs: Move alloc_backref_node() to backref.c
In reply to Qu Wenruo--- fs/btrfs/backref.c | 20 ++++++++++++++++++++ fs/btrfs/backref.h | 2 ++ fs/btrfs/relocation.c | 20 -------------------- 3 files changed, 22 insertions(+), 20 deletions(-)
fs/btrfs/backref.c +20 -0
@@ -2460,3 +2460,23 @@ void backref_cache_init(struct btrfs_fs_info *fs_info,INIT_LIST_HEAD (&cache->pending_edge);INIT_LIST_HEAD (&cache->useless_node); } + +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); +INIT_LIST_HEAD (&node->upper); +INIT_LIST_HEAD (&node->lower); +RB_CLEAR_NODE (&node->rb_node); + cache->nr_nodes++; + + node->level = level; + node->bytenr = bytenr; + } +return node; +}
fs/btrfs/backref.h +2 -0
@@ -292,4 +292,6 @@ struct backref_cache {void backref_cache_init (struct btrfs_fs_info *fs_info,struct backref_cache *cache,int is_reloc); +struct backref_node *alloc_backref_node (struct backref_cache *cache, +u64 bytenr,int level);#endif
fs/btrfs/relocation.c +0 -20
@@ -215,26 +215,6 @@ static void backref_cache_cleanup(struct backref_cache *cache)ASSERT (!cache->nr_edges); } -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); -INIT_LIST_HEAD (&node->upper); -INIT_LIST_HEAD (&node->lower); -RB_CLEAR_NODE (&node->rb_node); - cache->nr_nodes++; - - node->level = level; - node->bytenr = bytenr; - } -return node; -} -static void free_backref_node (struct backref_cache *cache,struct backref_node *node) {
Signature · 1 line
2.25.1
PATCH 8/19 btrfs: Move alloc_backref_edge() to backref.c
In reply to Qu Wenruo--- fs/btrfs/backref.c | 10 ++++++++++ fs/btrfs/backref.h | 1 + fs/btrfs/relocation.c | 10 ---------- 3 files changed, 11 insertions(+), 10 deletions(-)
fs/btrfs/backref.c +10 -0
@@ -2480,3 +2480,13 @@ struct backref_node *alloc_backref_node(struct backref_cache *cache, }return node; } + +struct backref_edge *alloc_backref_edge (struct backref_cache *cache) +{ +struct backref_edge *edge; + + edge =kzalloc (sizeof (*edge),GFP_NOFS ); +if (edge) + cache->nr_edges++; +return edge; +}
fs/btrfs/backref.h +1 -0
@@ -294,4 +294,5 @@ void backref_cache_init(struct btrfs_fs_info *fs_info, struct backref_cache *cache, int is_reloc);struct backref_node *alloc_backref_node (struct backref_cache *cache,u64 bytenr,int level); +struct backref_edge *alloc_backref_edge (struct backref_cache *cache);#endif
fs/btrfs/relocation.c +0 -10
@@ -225,16 +225,6 @@ static void free_backref_node(struct backref_cache *cache, } } -static struct backref_edge *alloc_backref_edge (struct backref_cache *cache) -{ -struct backref_edge *edge; - - edge =kzalloc (sizeof (*edge),GFP_NOFS ); -if (edge) - cache->nr_edges++; -return edge; -} -#define LINK_LOWER (1 << 0)#define LINK_UPPER (1 << 1) static inline void link_backref_edge(struct backref_edge *edge,
Signature · 1 line
2.25.1
PATCH 9/19 btrfs: Move link_backref_edge() to backref.c
In reply to Qu Wenruo--- fs/btrfs/backref.h | 16 ++++++++++++++++ fs/btrfs/relocation.c | 16 ---------------- 2 files changed, 16 insertions(+), 16 deletions(-)
fs/btrfs/backref.h +16 -0
@@ -295,4 +295,20 @@ void backref_cache_init(struct btrfs_fs_info *fs_info,struct backref_node *alloc_backref_node (struct backref_cache *cache,u64 bytenr,int level);struct backref_edge *alloc_backref_edge (struct backref_cache *cache); + +#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); +}#endif
fs/btrfs/relocation.c +0 -16
@@ -225,22 +225,6 @@ static void free_backref_node(struct backref_cache *cache, } } -#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) {
Signature · 1 line
2.25.1
PATCH 10/19 btrfs: Move free_backref_node() and free_backref_edge() to backref.h
In reply to Qu Wenruo--- fs/btrfs/backref.h | 20 ++++++++++++++++++++ fs/btrfs/relocation.c | 19 ------------------- 2 files changed, 20 insertions(+), 19 deletions(-)
fs/btrfs/backref.h +20 -0
@@ -8,6 +8,7 @@#include <linux/btrfs.h> #include "ulist.h" +#include "disk-io.h" #include "extent_io.h" struct inode_fs_paths {
@@ -311,4 +312,23 @@ static inline void link_backref_edge(struct backref_edge *edge,if (link_which &LINK_UPPER ) list_add_tail(&edge->list[UPPER], &upper->lower); } +static inline void free_backref_node (struct backref_cache *cache, +struct backref_node *node) +{ +if (node) { + cache->nr_nodes--; +btrfs_put_root (node->root); +kfree (node); + } +} + +static inline void free_backref_edge (struct backref_cache *cache, +struct backref_edge *edge) +{ +if (edge) { + cache->nr_edges--; +kfree (edge); + } +} +#endif
fs/btrfs/relocation.c +0 -19
@@ -215,25 +215,6 @@ static void backref_cache_cleanup(struct backref_cache *cache)ASSERT (!cache->nr_edges); } -static void free_backref_node (struct backref_cache *cache, -struct backref_node *node) -{ -if (node) { - cache->nr_nodes--; -btrfs_put_root (node->root); -kfree (node); - } -} - -static void free_backref_edge (struct backref_cache *cache, -struct backref_edge *edge) -{ -if (edge) { - cache->nr_edges--; -kfree (edge); - } -} -static void backref_tree_panic (struct rb_node *rb_node,int errno,u64 bytenr) {
Signature · 1 line
2.25.1
PATCH 11/19 btrfs: Move drop_backref_node() and needed facilities to backref.h
In reply to Qu WenruoWith extra comment for drop_backref_node() as it has some similarity with remove_backref_node(), thus we need extra comment explaining the difference.
--- fs/btrfs/backref.h | 37 +++++++++++++++++++++++++++++++++++++ fs/btrfs/relocation.c | 31 ------------------------------- 2 files changed, 37 insertions(+), 31 deletions(-)
fs/btrfs/backref.h +37 -0
@@ -331,4 +331,41 @@ static inline void free_backref_edge(struct backref_cache *cache, } } +static inline void unlock_node_buffer (struct backref_node *node) +{ +if (node->locked) { +btrfs_tree_unlock (node->eb); + node->locked =0 ; + } +} + +static inline void drop_node_buffer (struct backref_node *node) +{ +if (node->eb) { +unlock_node_buffer (node); +free_extent_buffer (node->eb); + node->eb =NULL ; + } +} + +/* +* Drop the backref node from cache without cleaning up its children +* edges. +* +* This can only be called on node without parent edges. +* The children edges are still kept as is. +*/ +static inline void drop_backref_node (struct backref_cache *tree, +struct backref_node *node) +{ +BUG_ON (!list_empty (&node->upper)); + +drop_node_buffer (node); +list_del (&node->list); +list_del (&node->lower); +if (!RB_EMPTY_NODE (&node->rb_node)) +rb_erase (&node->rb_node, &tree->rb_root); +free_backref_node (tree, node); +} +#endif
fs/btrfs/relocation.c +0 -31
@@ -275,37 +275,6 @@ static struct backref_node *walk_down_backref(struct backref_edge *edges[], *index =0 ;return NULL ; } - -static void unlock_node_buffer (struct backref_node *node) -{ -if (node->locked) { -btrfs_tree_unlock (node->eb); - node->locked =0 ; - } -} - -static void drop_node_buffer (struct backref_node *node) -{ -if (node->eb) { -unlock_node_buffer (node); -free_extent_buffer (node->eb); - node->eb =NULL ; - } -} - -static void drop_backref_node (struct backref_cache *tree, -struct backref_node *node) -{ -BUG_ON (!list_empty (&node->upper)); - -drop_node_buffer (node); -list_del (&node->list); -list_del (&node->lower); -if (!RB_EMPTY_NODE (&node->rb_node)) -rb_erase (&node->rb_node, &tree->rb_root); -free_backref_node (tree, node); -} -/* * remove a backref node from the backref cache */
Signature · 1 line
2.25.1
PATCH 12/19 btrfs: Rename remove_backref_node() to cleanup_backref_node() and move it to backref.c
In reply to Qu WenruoAlso add comment explaining the cleanup progress, to differ it from drop_backref_node().
--- fs/btrfs/backref.c | 38 ++++++++++++++++++++++++++++++++ fs/btrfs/backref.h | 9 ++++++++ fs/btrfs/relocation.c | 51 ++++--------------------------------------- 3 files changed, 51 insertions(+), 47 deletions(-)
fs/btrfs/backref.c +38 -0
@@ -2490,3 +2490,41 @@ struct backref_edge *alloc_backref_edge(struct backref_cache *cache) cache->nr_edges++;return edge; } + +void cleanup_backref_node (struct backref_cache *cache, +struct backref_node *node) +{ +struct backref_node *upper; +struct backref_edge *edge; + +if (!node) +return ; + +BUG_ON (!node->lowest && !node->detached); +while (!list_empty (&node->upper)) { + edge = list_entry(node->upper.next, struct backref_edge, + list[LOWER ]); + upper = edge->node[UPPER ]; +list_del (&edge->list[LOWER ]); +list_del (&edge->list[UPPER ]); +free_backref_edge (cache, edge); + +if (RB_EMPTY_NODE (&upper->rb_node)) { +BUG_ON (!list_empty (&node->upper)); +drop_backref_node (cache, node); + node = upper; + node->lowest =1 ; +continue ; + } +/* +* add the node to leaf node list if no other +* child block cached. +*/ +if (list_empty (&upper->lower)) { +list_add_tail (&upper->lower, &cache->leaves); + upper->lowest =1 ; + } + } + +drop_backref_node (cache, node); +}
fs/btrfs/backref.h +9 -0
@@ -368,4 +368,13 @@ static inline void drop_backref_node(struct backref_cache *tree, free_backref_node(tree, node); } +/* +* Drop the backref node from cache, also cleaning up all its +* upper edges and any uncached nodes in the path. +* +* This cleanup happens bottom up, thus the node should either +* be the lowest node in the cache or detached node. +*/ +void cleanup_backref_node (struct backref_cache *cache, +struct backref_node *node);#endif
fs/btrfs/relocation.c +4 -47
86 lines not on this page · raw message
Signature · 1 line
2.25.1
PATCH 13/19 btrfs: Move backref_cache_cleanup() to backref.c
In reply to Qu Wenruo--- fs/btrfs/backref.c | 30 ++++++++++++++++++++++++++++++ fs/btrfs/backref.h | 1 + fs/btrfs/relocation.c | 30 ------------------------------ 3 files changed, 31 insertions(+), 30 deletions(-)
fs/btrfs/backref.c +30 -0
@@ -2528,3 +2528,33 @@ void cleanup_backref_node(struct backref_cache *cache,drop_backref_node (cache, node); } + +void backref_cache_cleanup (struct backref_cache *cache) +{ +struct backref_node *node; +int i; + +while (!list_empty (&cache->detached)) { + node =list_entry (cache->detached.next, + struct backref_node, list); +cleanup_backref_node (cache, node); + } + +while (!list_empty (&cache->leaves)) { + node =list_entry (cache->leaves.next, + struct backref_node, lower); +cleanup_backref_node (cache, node); + } + + cache->last_trans =0 ; + +for (i =0 ; i <BTRFS_MAX_LEVEL ; i++) +ASSERT (list_empty (&cache->pending[i])); +ASSERT (list_empty (&cache->pending_edge)); +ASSERT (list_empty (&cache->useless_node)); +ASSERT (list_empty (&cache->changed)); +ASSERT (list_empty (&cache->detached)); +ASSERT (RB_EMPTY_ROOT (&cache->rb_root)); +ASSERT (!cache->nr_nodes); +ASSERT (!cache->nr_edges); +}
fs/btrfs/backref.h +1 -0
@@ -377,4 +377,5 @@ static inline void drop_backref_node(struct backref_cache *tree,*/ void cleanup_backref_node (struct backref_cache *cache,struct backref_node *node); +void backref_cache_cleanup (struct backref_cache *cache);#endif
fs/btrfs/relocation.c +0 -30
@@ -182,36 +182,6 @@ static void mapping_tree_init(struct mapping_tree *tree)spin_lock_init (&tree->lock); } -static void backref_cache_cleanup (struct backref_cache *cache) -{ -struct backref_node *node; -int i; - -while (!list_empty (&cache->detached)) { - node =list_entry (cache->detached.next, - struct backref_node, list); -cleanup_backref_node (cache, node); - } - -while (!list_empty (&cache->leaves)) { - node =list_entry (cache->leaves.next, - struct backref_node, lower); -cleanup_backref_node (cache, node); - } - - cache->last_trans =0 ; - -for (i =0 ; i <BTRFS_MAX_LEVEL ; i++) -ASSERT (list_empty (&cache->pending[i])); -ASSERT (list_empty (&cache->pending_edge)); -ASSERT (list_empty (&cache->useless_node)); -ASSERT (list_empty (&cache->changed)); -ASSERT (list_empty (&cache->detached)); -ASSERT (RB_EMPTY_ROOT (&cache->rb_root)); -ASSERT (!cache->nr_nodes); -ASSERT (!cache->nr_edges); -} -static void backref_tree_panic (struct rb_node *rb_node,int errno,u64 bytenr) {
Signature · 1 line
2.25.1
PATCH 14/19 btrfs: Rename backref_tree_panic() to backref_cache_panic(), and move it to backref.c
In reply to Qu WenruoAlso change the parameter, since all callers can easily grab an fs_info, there is no need for all the dancing.
--- fs/btrfs/backref.h | 8 ++++++++ fs/btrfs/relocation.c | 33 +++++++++++---------------------- 2 files changed, 19 insertions(+), 22 deletions(-)
fs/btrfs/backref.h +8 -0
@@ -378,4 +378,12 @@ static inline void drop_backref_node(struct backref_cache *tree,void cleanup_backref_node (struct backref_cache *cache,struct backref_node *node);void backref_cache_cleanup (struct backref_cache *cache); + +static inline void backref_cache_panic (struct btrfs_fs_info *fs_info, +u64 bytenr,int errno) +{ +btrfs_panic (fs_info, errno, +"Inconsistency in backref cache found at offset %llu" , + bytenr); +}#endif
fs/btrfs/relocation.c +11 -22
@@ -182,19 +182,6 @@ static void mapping_tree_init(struct mapping_tree *tree)spin_lock_init (&tree->lock); } -static void backref_tree_panic (struct rb_node *rb_node,int errno,u64 bytenr) -{ - -struct btrfs_fs_info *fs_info =NULL ; - struct backref_node *bnode = rb_entry(rb_node, struct backref_node, - rb_node); -if (bnode->root) - fs_info = bnode->root->fs_info; -btrfs_panic (fs_info, errno, -"Inconsistency in backref cache found at offset %llu" , - bytenr); -} -/* * walk up backref nodes until reach node presents tree root */
@@ -251,7 +238,7 @@ static void update_backref_node(struct backref_cache *cache, node->bytenr = bytenr; rb_node =simple_insert (&cache->rb_root, node->bytenr, &node->rb_node);if (rb_node) -backref_tree_panic (rb_node, -EEXIST , bytenr); +backref_cache_panic (cache->fs_info, bytenr, -EEXIST ); }/*
@@ -778,8 +765,8 @@ static int finish_upper_links(struct backref_cache *cache, rb_node =simple_insert (&cache->rb_root, upper->bytenr, &upper->rb_node);if (rb_node) { -backref_tree_panic (rb_node, -EEXIST , - upper->bytenr); +backref_cache_panic (cache->fs_info, + upper->bytenr, -EEXIST );return -EUCLEAN ; } }
@@ -949,7 +936,8 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, rb_node =simple_insert (&cache->rb_root, node->bytenr, &node->rb_node);if (rb_node) -backref_tree_panic (rb_node, -EEXIST , node->bytenr); +backref_cache_panic (cache->fs_info, node->bytenr, + -EEXIST );list_add_tail (&node->lower, &cache->leaves); }
@@ -1087,7 +1075,7 @@ static int clone_backref_node(struct btrfs_trans_handle *trans, rb_node =simple_insert (&cache->rb_root, new_node->bytenr, &new_node->rb_node);if (rb_node) -backref_tree_panic (rb_node, -EEXIST , new_node->bytenr); +backref_cache_panic (trans->fs_info, new_node->bytenr, -EEXIST );if (!new_node->lowest) {list_for_each_entry (new_edge, &new_node->lower, list[UPPER ]) {
@@ -1199,7 +1187,7 @@ static int __update_reloc_root(struct btrfs_root *root, u64 new_bytenr) node->bytenr, &node->rb_node);spin_unlock (&rc->reloc_root_tree.lock);if (rb_node) -backref_tree_panic (rb_node, -EEXIST , node->bytenr); +backref_cache_panic (fs_info, node->bytenr, -EEXIST );return 0 ; }
@@ -3285,7 +3273,8 @@ static int add_tree_block(struct reloc_control *rc, rb_node =simple_insert (blocks, block->bytenr, &block->rb_node);if (rb_node) -backref_tree_panic (rb_node, -EEXIST , block->bytenr); +backref_cache_panic (rc->extent_root->fs_info, block->bytenr, + -EEXIST );return 0 ; }
@@ -3583,8 +3572,8 @@ static int find_data_references(struct reloc_control *rc, rb_node =simple_insert (blocks, block->bytenr, &block->rb_node);if (rb_node) -backref_tree_panic (rb_node, -EEXIST , - block->bytenr); +backref_cache_panic (fs_info, block->bytenr, + -EEXIST ); }if (counted) added =1 ;
Signature · 1 line
2.25.1
PATCH 15/19 btrfs: Rename should_ignore_root() to should_ignore_reloc_root() and export it
In reply to Qu WenruoThis function is mostly single purpose to relocation backref cache, but since we're moving the main part of backref cache to backref.c, we need to export such function.
And to avoid confusing, rename the function to should_ignore_reloc_root() make the name a little more clear.
--- fs/btrfs/ctree.h | 1 + fs/btrfs/relocation.c | 9 +++++---- 2 files changed, 6 insertions(+), 4 deletions(-)
fs/btrfs/ctree.h +1 -0
@@ -3383,6 +3383,7 @@ int btrfs_reloc_post_snapshot(struct btrfs_trans_handle *trans, struct btrfs_pending_snapshot *pending);struct btrfs_root *find_reloc_root (struct btrfs_fs_info *fs_info,u64 bytenr); +int should_ignore_reloc_root (struct btrfs_root *root);/* scrub.c */ int btrfs_scrub_dev(struct btrfs_fs_info *fs_info, u64 devid, u64 start,
fs/btrfs/relocation.c +5 -4
@@ -312,7 +312,7 @@ static bool reloc_root_is_dead(struct btrfs_root *root)* * Reloc tree after swap is considered dead, thus not considered as valid. * This is enough for most callers, as they don't distinguish dead reloc root -* from no reloc root. But should_ignore_root() below is a special case. +* from no reloc root. But should_ignore_reloc_root() below is a special case. */ static bool have_reloc_root (struct btrfs_root *root) {
@@ -323,7 +323,7 @@ static bool have_reloc_root(struct btrfs_root *root)return true; } -static int should_ignore_root (struct btrfs_root *root) +int should_ignore_reloc_root (struct btrfs_root *root) {struct btrfs_root *reloc_root;
@@ -349,6 +349,7 @@ static int should_ignore_root(struct btrfs_root *root)*/ return 1 ; } +/* * find reloc tree by address of tree root */
@@ -465,7 +466,7 @@ static int handle_one_tree_backref(struct backref_cache *cache,/* tree root */ ASSERT (btrfs_root_bytenr (&root->root_item) == cur->bytenr); -if (should_ignore_root (root)) { +if (should_ignore_reloc_root (root)) {btrfs_put_root (root);list_add (&cur->list, useless_node); }else {
@@ -506,7 +507,7 @@ static int handle_one_tree_backref(struct backref_cache *cache,if (!path->nodes[level]) {ASSERT (btrfs_root_bytenr (&root->root_item) == lower->bytenr); -if (should_ignore_root (root)) { +if (should_ignore_reloc_root (root)) {btrfs_put_root (root);list_add (&lower->list, useless_node); }else {
Signature · 1 line
2.25.1
PATCH 16/19 btrfs: relocation: Open-code read_fs_root() for handle_one_tree_backref()
In reply to Qu WenruoThe backref code is going to be moved to backref.c, and read_fs_root() is just a simple wrapper, open-code it to prepare to the incoming code move.
--- fs/btrfs/relocation.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-)
fs/btrfs/relocation.c +5 -1
@@ -397,6 +397,7 @@ static int handle_one_tree_backref(struct backref_cache *cache,struct backref_node *lower;struct backref_edge *edge;struct extent_buffer *eb; +struct btrfs_key root_key;struct btrfs_root *root;struct rb_node *rb_node;bool need_check = true;
@@ -456,7 +457,10 @@ static int handle_one_tree_backref(struct backref_cache *cache,* ref_key.type == BTRFS_TREE_BLOCK_REF_KEY, ref_key->offset means the * root objectid. We need to search the tree to get its parent bytenr. */ - root =read_fs_root (fs_info, ref_key->offset); + root_key.objectid = ref_key->offset; + root_key.type =BTRFS_ROOT_ITEM_KEY ; + root_key.offset = (u64)-1 ; + root =btrfs_get_fs_root (fs_info, &root_key, false);if (IS_ERR (root))return PTR_ERR (root);if (!test_bit (BTRFS_ROOT_REF_COWS , &root->state))
Signature · 1 line
2.25.1
PATCH 17/19 btrfs: Rename handle_one_tree_block() to backref_cache_add_one_tree_block() and move it to backref.c
In reply to Qu WenruoThis function is the major part of backref cache build process, move it to backref.c so we can reuse it later.
--- fs/btrfs/backref.c | 305 +++++++++++++++++++++++++++++++++++++++++ fs/btrfs/backref.h | 6 + fs/btrfs/relocation.c | 307 +----------------------------------------- 3 files changed, 313 insertions(+), 305 deletions(-)
fs/btrfs/backref.c +305 -0
@@ -13,6 +13,7 @@#include "transaction.h" #include "delayed-ref.h" #include "locking.h" +#include "misc.h" /* Just an arbitrary number so we can be sure this happened */ #define BACKREF_FOUND_SHARED 6
@@ -2558,3 +2559,307 @@ void backref_cache_cleanup(struct backref_cache *cache)ASSERT (!cache->nr_nodes);ASSERT (!cache->nr_edges); } + +static int handle_one_tree_backref (struct backref_cache *cache, +struct btrfs_path *path, +struct btrfs_key *ref_key, +struct btrfs_key *tree_key, +struct backref_node *cur) +{ +struct btrfs_fs_info *fs_info = cache->fs_info; +struct list_head *useless_node = &cache->useless_node; +struct list_head *pending_edge = &cache->pending_edge; +struct backref_node *upper; +struct backref_node *lower; +struct backref_edge *edge; +struct extent_buffer *eb; +struct btrfs_key root_key; +struct btrfs_root *root; +struct rb_node *rb_node; +bool need_check = true; +int level; +int ret =0 ; + +if (ref_key->type !=BTRFS_TREE_BLOCK_REF_KEY && + ref_key->type !=BTRFS_SHARED_BLOCK_REF_KEY ) +return -EUCLEAN ; + +/* SHARED_BLOCK_REF means key.offset is the parent bytenr */ +if (ref_key->type ==BTRFS_SHARED_BLOCK_REF_KEY ) { + +/* Only reloc root uses backref pointing to itself */ +if (ref_key->objectid == ref_key->offset) { + cur->is_reloc_root =1 ; +/* Only reloc backref cache cares exact root */ +if (cache->is_reloc) { + root =find_reloc_root (fs_info, cur->bytenr); +if (WARN_ON (!root)) +return -ENOENT ; + cur->root = root; + } +return 0 ; + } + + edge =alloc_backref_edge (cache); +if (!edge) +return -ENOMEM ; + + rb_node =simple_search (&cache->rb_root, ref_key->offset); +if (!rb_node) { +/* Parent node not yet cached */ + upper =alloc_backref_node (cache, ref_key->offset, + cur->level +1 ); +if (!upper) { +free_backref_edge (cache, edge); +return -ENOMEM ; + } + +/* +* backrefs for the upper level block isn't +* cached, add the block to pending list +*/ +list_add_tail (&edge->list[UPPER ], pending_edge); + }else { +/* Parent node already cached */ + upper = rb_entry(rb_node, struct backref_node, + rb_node); +ASSERT (upper->checked); +INIT_LIST_HEAD (&edge->list[UPPER ]); + } +link_backref_edge (edge, cur, upper,LINK_LOWER ); +return 0 ; + } +/* +* ref_key.type == BTRFS_TREE_BLOCK_REF_KEY, ref_key->offset means the +* root objectid. We need to search the tree to get its parent bytenr. +*/ + root_key.objectid = ref_key->offset; + root_key.type =BTRFS_ROOT_ITEM_KEY ; + root_key.offset = (u64)-1 ; + root =btrfs_get_fs_root (fs_info, &root_key, false); +if (IS_ERR (root)) +return PTR_ERR (root); +if (!test_bit (BTRFS_ROOT_REF_COWS , &root->state)) + cur->cowonly =1 ; + +if (btrfs_root_level (&root->root_item) == cur->level) { +/* tree root */ +ASSERT (btrfs_root_bytenr (&root->root_item) == + cur->bytenr); +if (should_ignore_reloc_root (root)) { +btrfs_put_root (root); +list_add (&cur->list, useless_node); + }else { + cur->root = root; + } +return 0 ; + } + + level = cur->level +1 ; + +/* Search the tree to find parent blocks referring the block. */ + path->search_commit_root =1 ; + path->skip_locking =1 ; + path->lowest_level = level; + ret =btrfs_search_slot (NULL , root, tree_key, path,0 ,0 ); + path->lowest_level =0 ; +if (ret <0 ) { +btrfs_put_root (root); +return ret; + } +if (ret >0 && path->slots[level] >0 ) + path->slots[level]--; + + eb = path->nodes[level]; +if (btrfs_node_blockptr (eb, path->slots[level]) != cur->bytenr) { +btrfs_err (fs_info, +"couldn't find block (%llu) (level %d) in tree (%llu) with key (%llu %u %llu)" , + cur->bytenr, level -1 , root->root_key.objectid, + tree_key->objectid, tree_key->type, tree_key->offset); +btrfs_put_root (root); + ret = -ENOENT ; + goto out; + } + lower = cur; + +/* Add all nodes and edges in the path */ +for (; level <BTRFS_MAX_LEVEL ; level++) { +if (!path->nodes[level]) { +ASSERT (btrfs_root_bytenr (&root->root_item) == + lower->bytenr); +if (should_ignore_reloc_root (root)) { +btrfs_put_root (root); +list_add (&lower->list, useless_node); + }else { + lower->root = root; + } +break ; + } + + edge =alloc_backref_edge (cache); +if (!edge) { +btrfs_put_root (root); + ret = -ENOMEM ; + goto out; + } + + eb = path->nodes[level]; + rb_node =simple_search (&cache->rb_root, eb->start); +if (!rb_node) { + upper =alloc_backref_node (cache, eb->start, + lower->level +1 ); +if (!upper) { +btrfs_put_root (root); +free_backref_edge (cache, edge); + ret = -ENOMEM ; + goto out; + } + upper->owner =btrfs_header_owner (eb); +if (!test_bit (BTRFS_ROOT_REF_COWS , &root->state)) + upper->cowonly =1 ; + +/* +* if we know the block isn't shared we can void +* checking its backrefs. +*/ +if (btrfs_block_can_be_shared (root, eb)) + upper->checked =0 ; +else + upper->checked =1 ; + +/* +* add the block to pending list if we need check its +* backrefs, we only do this once while walking up a +* tree as we will catch anything else later on. +*/ +if (!upper->checked && need_check) { + need_check = false; +list_add_tail (&edge->list[UPPER ], pending_edge); + }else { +if (upper->checked) + need_check = true; +INIT_LIST_HEAD (&edge->list[UPPER ]); + } + }else { + upper = rb_entry(rb_node, struct backref_node, rb_node); +ASSERT (upper->checked); +INIT_LIST_HEAD (&edge->list[UPPER ]); +if (!upper->owner) + upper->owner =btrfs_header_owner (eb); + } +link_backref_edge (edge, lower, upper,LINK_LOWER ); + +if (rb_node) { +btrfs_put_root (root); +break ; + } + lower = upper; + upper =NULL ; + } +out: +btrfs_release_path (path); +return ret; +} + +int backref_cache_add_one_tree_block (struct backref_cache *cache, +struct btrfs_path *path, +struct btrfs_backref_iter *iter, +struct btrfs_key *node_key, +struct backref_node *cur) +{ +struct backref_edge *edge; +struct backref_node *exist; +int ret; + + ret =btrfs_backref_iter_start (iter, cur->bytenr); +if (ret <0 ) +return ret; + +/* +* We skip the first btrfs_tree_block_info, as we don't use the key +* stored in it, but fetch it from the tree block. +*/ +if (btrfs_backref_has_tree_block_info (iter)) { + ret =btrfs_backref_iter_next (iter); +if (ret <0 ) + goto out; +/* No extra backref? This means the tree block is corrupted */ +if (ret >0 ) { + ret = -EUCLEAN ; + goto out; + } + } +WARN_ON (cur->checked); +if (!list_empty (&cur->upper)) { +/* +* the backref was added previously when processing +* backref of type BTRFS_TREE_BLOCK_REF_KEY +*/ +ASSERT (list_is_singular (&cur->upper)); + edge = list_entry(cur->upper.next, struct backref_edge, + list[LOWER ]); +ASSERT (list_empty (&edge->list[UPPER ])); + exist = edge->node[UPPER ]; +/* +* add the upper level block to pending list if we need +* check its backrefs +*/ +if (!exist->checked) +list_add_tail (&edge->list[UPPER ], &cache->pending_edge); + }else { + exist =NULL ; + } + +for (; ret ==0 ; ret =btrfs_backref_iter_next (iter)) { +struct extent_buffer *eb; +struct btrfs_key key; +int type; + +cond_resched (); + eb =btrfs_backref_get_eb (iter); + + key.objectid = iter->bytenr; +if (btrfs_backref_iter_is_inline_ref (iter)) { +struct btrfs_extent_inline_ref *iref; + +/* update key for inline back ref */ + iref = (struct btrfs_extent_inline_ref *)iter->cur_ptr; + type =btrfs_get_extent_inline_ref_type (eb, iref, +BTRFS_REF_TYPE_BLOCK ); +if (type ==BTRFS_REF_TYPE_INVALID ) { + ret = -EUCLEAN ; + goto out; + } + key.type = type; + key.offset =btrfs_extent_inline_ref_offset (eb, iref); + }else { + key.type = iter->cur_key.type; + key.offset = iter->cur_key.offset; + } + +/* +* Parent node found and matches current inline ref, no need to +* rebuild this node for this inline ref. +*/ +if (exist && + ((key.type ==BTRFS_TREE_BLOCK_REF_KEY && + exist->owner == key.offset) || + (key.type ==BTRFS_SHARED_BLOCK_REF_KEY && + exist->bytenr == key.offset))) { + exist =NULL ; +continue ; + } + + ret =handle_one_tree_backref (cache, path, &key, node_key, cur); +if (ret <0 ) + goto out; + } +if (ret <0 ) + goto out; + ret =0 ; + cur->checked =1 ; +WARN_ON (exist); +out: +btrfs_backref_iter_release (iter); +return ret; +}
fs/btrfs/backref.h +6 -0
@@ -386,4 +386,10 @@ static inline void backref_cache_panic(struct btrfs_fs_info *fs_info,"Inconsistency in backref cache found at offset %llu" , bytenr); } + +int backref_cache_add_one_tree_block (struct backref_cache *cache, +struct btrfs_path *path, +struct btrfs_backref_iter *iter, +struct btrfs_key *node_key, +struct backref_node *cur);#endif
fs/btrfs/relocation.c +2 -305
319 lines not on this page · raw message
Signature · 1 line
2.25.1
PATCH 18/19 btrfs: relocation: Move the target backref node insert code into finish_upper_links()
In reply to Qu WenruoThe snippet of code can be easily merged into finish_upper_links(), thus make related code more reuseable.
--- fs/btrfs/relocation.c | 30 +++++++++++++++--------------- 1 file changed, 15 insertions(+), 15 deletions(-)
fs/btrfs/relocation.c +15 -15
@@ -400,8 +400,23 @@ static int finish_upper_links(struct backref_cache *cache, {struct list_head *useless_node = &cache->useless_node;struct backref_edge *edge; +struct rb_node *rb_node;LIST_HEAD (pending_edge); +/* +* everything goes well, connect backref nodes and insert backref nodes +* into the cache. +*/ +ASSERT (start->checked); +if (!start->cowonly) { + rb_node =simple_insert (&cache->rb_root, start->bytenr, + &start->rb_node); +if (rb_node) +backref_cache_panic (cache->fs_info, start->bytenr, + -EEXIST ); +list_add_tail (&start->lower, &cache->leaves); + } +/* * Use breadth first search to iterate all related edges. *
@@ -584,7 +599,6 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,struct backref_node *lower;struct backref_node *node =NULL ;struct backref_edge *edge; -struct rb_node *rb_node;int ret;int err =0 ;
@@ -629,20 +643,6 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, } } -/* -* everything goes well, connect backref nodes and insert backref nodes -* into the cache. -*/ -ASSERT (node->checked); -if (!node->cowonly) { - rb_node =simple_insert (&cache->rb_root, node->bytenr, - &node->rb_node); -if (rb_node) -backref_cache_panic (cache->fs_info, node->bytenr, - -EEXIST ); -list_add_tail (&node->lower, &cache->leaves); - } -/* Finish the upper linkage of newly added edges/nodes */ ret =finish_upper_links (cache, node);if (ret <0 ) {
Signature · 1 line
2.25.1
PATCH 19/19 btrfs: Rename finish_upper_links() to backref_cache_finish_upper_links() and move it to backref.c
In reply to Qu WenruoThis the the 2nd major part of generic backref cache. Move it to backref.c so we can reuse it.
--- fs/btrfs/backref.c | 115 +++++++++++++++++++++++++++++++++++++++++ fs/btrfs/backref.h | 2 + fs/btrfs/relocation.c | 117 +----------------------------------------- 3 files changed, 118 insertions(+), 116 deletions(-)
fs/btrfs/backref.c +115 -0
@@ -2863,3 +2863,118 @@ int backref_cache_add_one_tree_block(struct backref_cache *cache,btrfs_backref_iter_release (iter);return ret; } + +/* +* In handle_one_tree_backref(), we have only linked the lower node to the edge, +* but the upper node hasn't been linked to the edge. +* This means we can only iterate through backref_node::upper to reach parent +* edges, but not through backref_node::lower to reach children edges. +* +* This function will finish the backref_node::lower to related edges, so that +* backref cache can be bi-directionally iterated. +* +* Also, this will add the nodes to backref cache for next run. +*/ +int backref_cache_finish_upper_links (struct backref_cache *cache, +struct backref_node *start) +{ +struct list_head *useless_node = &cache->useless_node; +struct backref_edge *edge; +struct rb_node *rb_node; +LIST_HEAD (pending_edge); + +/* +* everything goes well, connect backref nodes and insert backref nodes +* into the cache. +*/ +ASSERT (start->checked); +if (!start->cowonly) { + rb_node =simple_insert (&cache->rb_root, start->bytenr, + &start->rb_node); +if (rb_node) +backref_cache_panic (cache->fs_info, start->bytenr, + -EEXIST ); +list_add_tail (&start->lower, &cache->leaves); + } + +/* +* Use breadth first search to iterate all related edges. +* +* The start point is all the edges of this node +*/ +list_for_each_entry (edge, &start->upper, list[LOWER ]) +list_add_tail (&edge->list[UPPER ], &pending_edge); + +while (!list_empty (&pending_edge)) { +struct backref_node *upper; +struct backref_node *lower; +struct rb_node *rb_node; + + edge = list_entry(pending_edge.next, struct backref_edge, + list[UPPER ]); +list_del_init (&edge->list[UPPER ]); + upper = edge->node[UPPER ]; + lower = edge->node[LOWER ]; + +/* Parent is detached, no need to keep any edges */ +if (upper->detached) { +list_del (&edge->list[LOWER ]); +free_backref_edge (cache, edge); + +/* Lower node is orphan, queue for cleanup */ +if (list_empty (&lower->upper)) +list_add (&lower->list, useless_node); +continue ; + } + +/* +* All new nodes added in current build_backref_tree() haven't +* been linked to the cache rb tree. +* So if we have upper->rb_node populated, this means a cache +* hit. We only need to link the edge, as @upper and all its +* parent have already been linked. +*/ +if (!RB_EMPTY_NODE (&upper->rb_node)) { +if (upper->lowest) { +list_del_init (&upper->lower); + upper->lowest =0 ; + } + +list_add_tail (&edge->list[UPPER ], &upper->lower); +continue ; + } + +/* Sanity check, we shouldn't have any unchecked nodes */ +if (!upper->checked) { +ASSERT (0 ); +return -EUCLEAN ; + } + +/* Sanity check, cowonly node has non-cowonly parent */ +if (start->cowonly != upper->cowonly) { +ASSERT (0 ); +return -EUCLEAN ; + } + +/* Only cache non-cowonly (subvolume trees) tree blocks */ +if (!upper->cowonly) { + rb_node =simple_insert (&cache->rb_root, upper->bytenr, + &upper->rb_node); +if (rb_node) { +backref_cache_panic (cache->fs_info, + upper->bytenr, -EEXIST ); +return -EUCLEAN ; + } + } + +list_add_tail (&edge->list[UPPER ], &upper->lower); + +/* +* Also queue all the parent edges of this uncached node +* to finish the upper linkage +*/ +list_for_each_entry (edge, &upper->upper, list[LOWER ]) +list_add_tail (&edge->list[UPPER ], &pending_edge); + } +return 0 ; +}
fs/btrfs/backref.h +2 -0
@@ -392,4 +392,6 @@ int backref_cache_add_one_tree_block(struct backref_cache *cache,struct btrfs_backref_iter *iter, struct btrfs_key *node_key, struct backref_node *cur); +int backref_cache_finish_upper_links (struct backref_cache *cache, +struct backref_node *start);#endif
fs/btrfs/relocation.c +1 -116
129 lines not on this page · raw message
Signature · 1 line
2.25.1
Quoted 8 lines · Qu Wenruo
The patchset is based on previous
backref_cache_refactorbranch, which is further based on misc-next.The whole series can be fetched from github:
https://github.com/adam900710/linux/tree/backref_cache_code_moveAll the patches in previous branch is not touched at all, thus they are not re-sent in this patchset.
The patches are cleanups and code moving, please fix the coding style issues you find.
* missing lines between declarations and statements
* exported functions need btrfs_ prefix
* comments should start with an upper case letter unless it's an identifier, formatted to 80 columns
As this patchset depends on another one I'm not sure if it's right time to update it now, before the other one is merged as I think the same code is touched and this would cause extra work.
Overall it makes sensed to add more to backref.[hc] and export that as an internal API.
Quoted 7 lines · David Sterba
Quoted 6 lines · Qu Wenruo
The patchset is based on previous
backref_cache_refactorbranch, which is further based on misc-next.The whole series can be fetched from github:
https://github.com/adam900710/linux/tree/backref_cache_code_move
Quoted 8 lines
Quoted 2 lines
All the patches in previous branch is not touched at all, thus they are not re-sent in this patchset.
The patches are cleanups and code moving, please fix the coding style issues you find.
* missing lines between declarations and statements
* exported functions needbtrfs_prefix
I have some question about this.
Sometimes the "btrfs_" prefix requirement looks too mechanical.
Some functions, like backref_cache_init() is very obvious related to backref cache.
I can't see any special benefit from adding a "btrfs_" prefix.
Thanks,
Qu
Quoted 10 lines
* comments should start with an upper case letter unless it's an identifier, formatted to 80 columns
As this patchset depends on another one I'm not sure if it's right time to update it now, before the other one is merged as I think the same code is touched and this would cause extra work.
Overall it makes sensed to add more to backref.[hc] and export that as an internal API.
Quoted 17 lines · Qu Wenruo
The patchset is based on previous
backref_cache_refactorbranch, which is further based on misc-next.The whole series can be fetched from github:
https://github.com/adam900710/linux/tree/backref_cache_code_moveAll the patches in previous branch is not touched at all, thus they are not re-sent in this patchset.
Currently there are 3 major parts of
build_backref_tree():
- ITERATION
This will do a breadth-first search, starts from the target bytenr, and queue all parents into the backref cache.
The result is a temporary map, which is only single-directional, and involved new backref nodes are not yet inserted into the cache.
Quoted 8 lines
- WEAVING
Finish the map to make it bi-directional, and insert new nodes into the cache.- CLEANUP
Cleanup the useless nodes, either remove it completely or add them into the cache as detached.
I've found a bunch of bugs in the backref code while fixing Zygo's problem, you are probably going to want to wait for my patches to go in before you start moving things around, because it's going to conflict a bunch. Thanks,
Josef
Quoted 27 lines · Josef Bacik
Quoted 17 lines · Qu Wenruo
The patchset is based on previous
backref_cache_refactorbranch, which is further based on misc-next.The whole series can be fetched from github:
https://github.com/adam900710/linux/tree/backref_cache_code_moveAll the patches in previous branch is not touched at all, thus they are not re-sent in this patchset.
Currently there are 3 major parts of
build_backref_tree():
- ITERATION
This will do a breadth-first search, starts from the target bytenr, and queue all parents into the backref cache.
The result is a temporary map, which is only single-directional, and involved new backref nodes are not yet inserted into the cache.Quoted 8 lines
- WEAVING
Finish the map to make it bi-directional, and insert new nodes into the cache.- CLEANUP
Cleanup the useless nodes, either remove it completely or add them into the cache as detached.
Quoted 4 lines
I've found a bunch of bugs in the backref code while fixing Zygo's problem, you are probably going to want to wait for my patches to go in before you start moving things around, because it's going to conflict a bunch. Thanks,
No problem, it's expected to have some comments even for previous patchset.
So rebasing is expected.
Thanks,
Qu
Quoted 2 lines
Josef
Quoted 30 lines · Qu Wenruo
Quoted 27 lines · Josef Bacik
Quoted 25 lines · Qu Wenruo
The patchset is based on previous
backref_cache_refactorbranch, which is further based on misc-next.The whole series can be fetched from github:
https://github.com/adam900710/linux/tree/backref_cache_code_moveAll the patches in previous branch is not touched at all, thus they are not re-sent in this patchset.
Currently there are 3 major parts of
build_backref_tree():
- ITERATION
This will do a breadth-first search, starts from the target bytenr, and queue all parents into the backref cache.
The result is a temporary map, which is only single-directional, and involved new backref nodes are not yet inserted into the cache.- WEAVING
Finish the map to make it bi-directional, and insert new nodes into the cache.- CLEANUP
Cleanup the useless nodes, either remove it completely or add them into the cache as detached.
Quoted 8 lines
Quoted 4 lines
I've found a bunch of bugs in the backref code while fixing Zygo's problem, you are probably going to want to wait for my patches to go in before you start moving things around, because it's going to conflict a bunch. Thanks,
No problem, it's expected to have some comments even for previous patchset.
So rebasing is expected.
The fixes get merged first so they can be applied to older stable trees, the cleanups that move code are best done as the last thing in the patch queue. So this depends on timing and the amount of conflicts but we have like 2 rcs to go.