btrfs: relocation: Refactor build_backref_tree()
cover btrfs: relocation: Refactor build_backref_tree()
This branch can be fetched from github:
https://github.com/adam900710/linux/tree/backref_cache_new
The main objective of this patchset is to refactor build_backref_tree() and get myself more familiar with the backref cache.
The refactor also add quite some comments explaining how the backref cache is built, but I'm also working on crafting a new dev doc for the backref cache.
As some more example would greatly help reader to go through the somewhat weird code.
Patch 1~8 haven already been sent to the mail list. This time they are included for a better review.
There are 3 main structures involved:
- backref_cache
The main cache structure, store all the existing cached map.
- backref_node
Represent one tree block.
It can have multiple parent and multiple children backref_edges related.
- backref_edge
Represent one parent-child relationship between two backref_node. Both parent (upper) and child (lower) backref_node can iterate through their list to locate the edge.
The objective build_backref_cache() is to build a map, starting from specified node, to reach all its parents. E.g:
build_backref_tree() is called on bytenr X, then the following map is added to backref_cache:
Root 257 Root 258
A B
| /
| /
|/
C
|
X We will have backref_nodes for X, A, B, C in the backref_cache, and 3 edges between (X, C), (C, A), (C, B).
The short workflow of build_backref_tree() is:
- Iterate through all parent nodes of the specified node (ITERATION)
Here we go breadth first search. We go through direct parent of current node. The iteration is bottom-up.
For how each backref item is handled, check handle_one_tree_backref() for details.
When a direct parent is found, we check if the direct parent is cached:
* Cached:
Allocate the edge between this node and parent. Call it a day, and process next parent.
* Not cached:
Allocate both edges and nodes. And queue the parent node for iteration.
During this stage, new nodes are only allocated, not yet added to cache, and new edges are only linked to lower nodes.
After this step, we have reached all roots referring to the specified node.
Some root nodes may be useless (reloc tree root), they will be queued for later cleanup.
- Finish the linkage between newly added nodes and edges. (WEAVING)
Since previous step only allocated new nodes, and only linked edges with its lower node, we still need to add the nodes to cache, and finish the linkage.
See finish_upper_links() for details.
- Cleanup the useless trees
(CLEANUP)
For reloc trees, we only cache the backref nodes for higher tree nodes. And don't keep any edges. So such backref nodes are marked detached.
Tree leaves for reloc trees are not cached.
Such behavior is to reduce memory usage for useless trees, but still allow backref cache hit, to avoid unnecessary cache search.
And also mark the useless nodes as processed for relocation.
With the refactor, only the CLEANUP part of build_backref_tree() is coupled with relocation.
And now build_backref_tree() is only 125 lines, it's a pretty good start point for us to reuse backref_cache for other workload, like qgroups.
Qu Wenruo (10):
btrfs: backref: Introduce the skeleton of btrfs_backref_iter
btrfs: backref: Implement btrfs_backref_iter_next()
btrfs: relocation: Use btrfs_backref_iter infrastructure
btrfs: relocation: Rename mark_block_processed() and
__mark_block_processed()
btrfs: relocation: Refactor tree backref processing into its own
function
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
btrfs: relocation: Refactor the finishing part of upper linkage into
finish_upper_links()
btrfs: relocation: Refactor the useless nodes handling into its own
function
fs/btrfs/backref.c | 145 +++++++ fs/btrfs/backref.h | 94 +++++ fs/btrfs/relocation.c | 959 ++++++++++++++++++++++-------------------- 3 files changed, 750 insertions(+), 448 deletions(-)
Signature · 1 line
2.25.1
PATCH 1/10 btrfs: backref: Introduce the skeleton of btrfs_backref_iter
Due to the complex nature of btrfs extent tree, when we want to iterate all backrefs of one extent, it involves quite a lot of work, like searching the EXTENT_ITEM/METADATA_ITEM, iteration through inline and keyed backrefs.
Normally this would result pretty complex code, something like:
btrfs_search_slot()
/* Ensure we are at EXTENT_ITEM/METADATA_ITEM */
while (1) { /* Loop for extent tree items */
while (ptr < end) { /* Loop for inlined items */
/* REAL WORK HERE */
}
next:
ret = btrfs_next_item()
/* Ensure we're still at keyed item for specified bytenr */}
The idea of btrfs_backref_iter is to avoid such complex and hard to read code structure, but something like the following:
iter = btrfs_backref_iter_alloc();
ret = btrfs_backref_iter_start(iter, bytenr);
if (ret < 0)
goto out;
for (; ; ret = btrfs_backref_iter_next(iter)) {
/* REAL WORK HERE */ }
out:
btrfs_backref_iter_free(iter);
This patch is just the skeleton + btrfs_backref_iter_start() code.
--- fs/btrfs/backref.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++ fs/btrfs/backref.h | 60 ++++++++++++++++++++++++++++++++ 2 files changed, 147 insertions(+)
fs/btrfs/backref.c +87 -0
@@ -2252,3 +2252,90 @@ void free_ipath(struct inode_fs_paths *ipath)kvfree (ipath->fspath);kfree (ipath); } + +int btrfs_backref_iter_start (struct btrfs_backref_iter *iter,u64 bytenr) +{ +struct btrfs_fs_info *fs_info = iter->fs_info; +struct btrfs_path *path = iter->path; +struct btrfs_extent_item *ei; +struct btrfs_key key; +int ret; + + key.objectid = bytenr; + key.type =BTRFS_METADATA_ITEM_KEY ; + key.offset = (u64)-1 ; + iter->bytenr = bytenr; + + ret =btrfs_search_slot (NULL , fs_info->extent_root, &key, path,0 ,0 ); +if (ret <0 ) +return ret; +if (ret ==0 ) { + ret = -EUCLEAN ; + goto release; + } +if (path->slots[0 ] ==0 ) { +WARN_ON (IS_ENABLED (CONFIG_BTRFS_DEBUG )); + ret = -EUCLEAN ; + goto release; + } + path->slots[0 ]--; + +btrfs_item_key_to_cpu (path->nodes[0 ], &key, path->slots[0 ]); +if (!(key.type ==BTRFS_EXTENT_ITEM_KEY || + key.type ==BTRFS_METADATA_ITEM_KEY ) || key.objectid != bytenr) { + ret = -ENOENT ; + goto release; + } +memcpy (&iter->cur_key, &key,sizeof (key)); + iter->item_ptr =btrfs_item_ptr_offset (path->nodes[0 ], + path->slots[0 ]); + iter->end_ptr = iter->item_ptr +btrfs_item_size_nr (path->nodes[0 ], + path->slots[0 ]); + ei =btrfs_item_ptr (path->nodes[0 ], path->slots[0 ], + struct btrfs_extent_item); + +/* +* Only support iteration on tree backref yet. +* +* This is extra precaustion for non skinny-metadata, where +* EXTENT_ITEM is also used for tree blocks, that we can only use +* extent flags to determine if it's a tree block. +*/ +if (btrfs_extent_flags (path->nodes[0 ], ei) &BTRFS_EXTENT_FLAG_DATA ) { + ret = -ENOTTY ; + goto release; + } + iter->cur_ptr = iter->item_ptr +sizeof (*ei); + +/* If there is no inline backref, go search for keyed backref */ +if (iter->cur_ptr >= iter->end_ptr) { + ret =btrfs_next_item (fs_info->extent_root, path); + +/* No inline nor keyed ref */ +if (ret >0 ) { + ret = -ENOENT ; + goto release; + } +if (ret <0 ) + goto release; + +btrfs_item_key_to_cpu (path->nodes[0 ], &iter->cur_key, + path->slots[0 ]); +if (iter->cur_key.objectid != bytenr || + (iter->cur_key.type !=BTRFS_SHARED_BLOCK_REF_KEY && + iter->cur_key.type !=BTRFS_TREE_BLOCK_REF_KEY )) { + ret = -ENOENT ; + goto release; + } + iter->cur_ptr =btrfs_item_ptr_offset (path->nodes[0 ], + path->slots[0 ]); + iter->item_ptr = iter->cur_ptr; + iter->end_ptr = iter->item_ptr +btrfs_item_size_nr ( + path->nodes[0 ], path->slots[0 ]); + } + +return 0 ; +release: +btrfs_backref_iter_release (iter); +return ret; +}
fs/btrfs/backref.h +60 -0
64 lines not on this page · raw message
Signature · 1 line
2.25.1
PATCH 2/10 btrfs: backref: Implement btrfs_backref_iter_next()
In reply to Qu WenruoThis function will go next inline/keyed backref for btrfs_backref_iter infrastructure.
--- fs/btrfs/backref.c | 58 ++++++++++++++++++++++++++++++++++++++++++++++ fs/btrfs/backref.h | 34 +++++++++++++++++++++++++++ 2 files changed, 92 insertions(+)
fs/btrfs/backref.c +58 -0
@@ -2339,3 +2339,61 @@ int btrfs_backref_iter_start(struct btrfs_backref_iter *iter, u64 bytenr)btrfs_backref_iter_release (iter);return ret; } + +/* +* Go to next backref item of current bytenr, can be either inlined or keyed. +* +* Caller need to check whether it's inline ref or not by iter->cur_key. +* +* Return 0 if we get next backref without problem. +* Return >0 if there is no extra backref for this bytenr. +* Return <0 if there is something wrong happened. +*/ +int btrfs_backref_iter_next (struct btrfs_backref_iter *iter) +{ +struct extent_buffer *eb =btrfs_backref_get_eb (iter); +struct btrfs_path *path = iter->path; +struct btrfs_extent_inline_ref *iref; +int ret; +u32 size; + +if (btrfs_backref_iter_is_inline_ref (iter)) { +/* We're still inside the inline refs */ +ASSERT (iter->cur_ptr < iter->end_ptr); + +if (btrfs_backref_has_tree_block_info (iter)) { +/* First tree block info */ + size =sizeof (struct btrfs_tree_block_info ); + }else { +/* Use inline ref type to determine the size */ +int type; + + iref = (struct btrfs_extent_inline_ref *) + (iter->cur_ptr); + type =btrfs_extent_inline_ref_type (eb, iref); + + size =btrfs_extent_inline_ref_size (type); + } + iter->cur_ptr += size; +if (iter->cur_ptr < iter->end_ptr) +return 0 ; + +/* All inline items iterated, fall through */ + } +/* We're at keyed items, there is no inline item, just go next item */ + ret =btrfs_next_item (iter->fs_info->extent_root, iter->path); +if (ret) +return ret; + +btrfs_item_key_to_cpu (path->nodes[0 ], &iter->cur_key, path->slots[0 ]); +if (iter->cur_key.objectid != iter->bytenr || + (iter->cur_key.type !=BTRFS_TREE_BLOCK_REF_KEY && + iter->cur_key.type !=BTRFS_SHARED_BLOCK_REF_KEY )) +return 1 ; + iter->item_ptr =btrfs_item_ptr_offset (path->nodes[0 ], + path->slots[0 ]); + iter->cur_ptr = iter->item_ptr; + iter->end_ptr = iter->item_ptr +btrfs_item_size_nr (path->nodes[0 ], + path->slots[0 ]); +return 0 ; +}
fs/btrfs/backref.h +34 -0
@@ -121,8 +121,42 @@ static inline void btrfs_backref_iter_free(struct btrfs_backref_iter *iter)kfree (iter); } +static inline struct extent_buffer * +btrfs_backref_get_eb (struct btrfs_backref_iter *iter) +{ +if (!iter) +return NULL ; +return iter->path->nodes[0 ]; +} + +/* +* For metadata with EXTENT_ITEM key (non-skinny) case, the first inline data +* is btrfs_tree_block_info, without a btrfs_extent_inline_ref header. +* +* This helper is here to determine if that's the case. +*/ +static inline bool btrfs_backref_has_tree_block_info ( +struct btrfs_backref_iter *iter) +{ +if (iter->cur_key.type ==BTRFS_EXTENT_ITEM_KEY && + iter->cur_ptr - iter->item_ptr ==sizeof (struct btrfs_extent_item )) +return true; +return false; +} +int btrfs_backref_iter_start (struct btrfs_backref_iter *iter,u64 bytenr); +int btrfs_backref_iter_next (struct btrfs_backref_iter *iter); + +static inline bool +btrfs_backref_iter_is_inline_ref (struct btrfs_backref_iter *iter) +{ +if (iter->cur_key.type ==BTRFS_EXTENT_ITEM_KEY || + iter->cur_key.type ==BTRFS_METADATA_ITEM_KEY ) +return true; +return false; +} +static inline void btrfs_backref_iter_release (struct btrfs_backref_iter *iter) {
Signature · 1 line
2.25.1
PATCH 3/10 btrfs: relocation: Use btrfs_backref_iter infrastructure
In reply to Qu WenruoIn the core function of relocation, build_backref_tree, it needs to iterate all backref items of one tree block.
We don't really want to spend our code and reviewers' time to going through tons of supportive code just for the backref walk.
Use btrfs_backref_iter infrastructure to do the loop.
The backref items look would be much more easier to read:
ret = btrfs_backref_iter_start(iter, cur->bytenr);
for (; ret == 0; ret = btrfs_backref_iter_next(iter)) {
/* The really important work */
}--- fs/btrfs/relocation.c | 193 ++++++++++++++---------------------------- 1 file changed, 62 insertions(+), 131 deletions(-)
fs/btrfs/relocation.c +62 -131
@@ -22,6 +22,7 @@#include "print-tree.h" #include "delalloc-space.h" #include "block-group.h" +#include "backref.h" /* * backref_node, mapping_node and tree_block start with this
@@ -604,48 +605,6 @@ static struct btrfs_root *read_fs_root(struct btrfs_fs_info *fs_info,return btrfs_get_fs_root (fs_info, &key, false); } -static noinline_for_stack -int find_inline_backref(struct extent_buffer *leaf, int slot, -unsigned long *ptr,unsigned long *end) -{ -struct btrfs_key key; -struct btrfs_extent_item *ei; -struct btrfs_tree_block_info *bi; -u32 item_size; - -btrfs_item_key_to_cpu (leaf, &key, slot); - - item_size =btrfs_item_size_nr (leaf, slot); -if (item_size <sizeof (*ei)) { -btrfs_print_v0_err (leaf->fs_info); -btrfs_handle_fs_error (leaf->fs_info, -EINVAL ,NULL ); -return 1 ; - } - ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item); -WARN_ON (!(btrfs_extent_flags (leaf, ei) & -BTRFS_EXTENT_FLAG_TREE_BLOCK )); - -if (key.type ==BTRFS_EXTENT_ITEM_KEY && - item_size <=sizeof (*ei) +sizeof (*bi)) { -WARN_ON (item_size <sizeof (*ei) +sizeof (*bi)); -return 1 ; - } -if (key.type ==BTRFS_METADATA_ITEM_KEY && - item_size <=sizeof (*ei)) { -WARN_ON (item_size <sizeof (*ei)); -return 1 ; - } - -if (key.type ==BTRFS_EXTENT_ITEM_KEY ) { - bi = (struct btrfs_tree_block_info *)(ei +1 ); - *ptr = (unsigned long )(bi +1 ); - }else { - *ptr = (unsigned long )(ei +1 ); - } - *end = (unsigned long )ei + item_size; -return 0 ; -} -/* * build backref tree for a given tree block. root of the backref tree * corresponds the tree block, leaves of the backref tree correspond
@@ -665,10 +624,9 @@ 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 *path1;/* For searching extent root */ -struct btrfs_path *path2;/* For searching parent of TREE_BLOCK_REF */ -struct extent_buffer *eb; +struct btrfs_path *path;/* For searching parent of TREE_BLOCK_REF */ struct btrfs_root *root;struct backref_node *cur;struct backref_node *upper;
@@ -677,9 +635,6 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,struct backref_node *exist =NULL ;struct backref_edge *edge;struct rb_node *rb_node; -struct btrfs_key key; -unsigned long end; -unsigned long ptr;LIST_HEAD (list);/* Pending edge list, upper node needs to be checked */ LIST_HEAD (useless);int cowonly;
@@ -687,14 +642,15 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,int err =0 ;bool need_check = true; - path1 =btrfs_alloc_path (); - path2 =btrfs_alloc_path (); -if (!path1 || !path2) { + 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; } - path1->reada =READA_FORWARD ; - path2->reada =READA_FORWARD ; + path->reada =READA_FORWARD ; node =alloc_backref_node (cache);if (!node) {
@@ -707,25 +663,28 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, node->lowest =1 ; cur = node; again: - end =0 ; - ptr =0 ; - key.objectid = cur->bytenr; - key.type =BTRFS_METADATA_ITEM_KEY ; - key.offset = (u64)-1 ; - - path1->search_commit_root =1 ; - path1->skip_locking =1 ; - ret =btrfs_search_slot (NULL , rc->extent_root, &key, path1, -0 ,0 ); + ret =btrfs_backref_iter_start (iter, cur->bytenr);if (ret <0 ) { err = ret; goto out; } -ASSERT (ret); -ASSERT (path1->slots[0 ]); - - path1->slots[0 ]--; +/* +* 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 ) { + err = ret; + goto out; + } +/* No extra backref? This means the tree block is corrupted */ +if (ret >0 ) { + err = -EUCLEAN ; + goto out; + } + }WARN_ON (cur->checked);if (!list_empty (&cur->upper)) {/*
@@ -747,42 +706,20 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, exist =NULL ; } -while (1 ) { -cond_resched (); - eb = path1->nodes[0 ]; - -if (ptr >= end) { -if (path1->slots[0 ] >=btrfs_header_nritems (eb)) { - ret =btrfs_next_leaf (rc->extent_root, path1); -if (ret <0 ) { - err = ret; - goto out; - } -if (ret >0 ) -break ; - eb = path1->nodes[0 ]; - } +for (; ret ==0 ; ret =btrfs_backref_iter_next (iter)) { +struct extent_buffer *eb; +struct btrfs_key key; +int type; -btrfs_item_key_to_cpu (eb, &key, path1->slots[0 ]); -if (key.objectid != cur->bytenr) { -WARN_ON (exist); -break ; - } +cond_resched (); + eb =btrfs_backref_get_eb (iter); -if (key.type ==BTRFS_EXTENT_ITEM_KEY || - key.type ==BTRFS_METADATA_ITEM_KEY ) { - ret =find_inline_backref (eb, path1->slots[0 ], - &ptr, &end); -if (ret) - goto next; - } - } + key.objectid = iter->bytenr; +if (btrfs_backref_iter_is_inline_ref (iter)) { +struct btrfs_extent_inline_ref *iref; -if (ptr < end) {/* update key for inline back ref */ -struct btrfs_extent_inline_ref *iref; -int type; - iref = (struct btrfs_extent_inline_ref *)ptr; + 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 ) {
@@ -791,9 +728,9 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, } key.type = type; key.offset =btrfs_extent_inline_ref_offset (eb, iref); - -WARN_ON (key.type !=BTRFS_TREE_BLOCK_REF_KEY && - key.type !=BTRFS_SHARED_BLOCK_REF_KEY ); + }else { + key.type = iter->cur_key.type; + key.offset = iter->cur_key.offset; }/*
@@ -806,7 +743,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, (key.type == BTRFS_SHARED_BLOCK_REF_KEY && exist->bytenr == key.offset))) { exist =NULL ; - goto next; +continue ; }/* SHARED_BLOCK_REF means key.offset is the parent bytenr */
@@ -852,7 +789,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, edge->node[LOWER ] = cur; edge->node[UPPER ] = upper; - goto next; +continue ; }else if (unlikely (key.type ==BTRFS_EXTENT_REF_V0_KEY )) { err = -EINVAL ;btrfs_print_v0_err (rc->extent_root->fs_info);
@@ -860,7 +797,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, NULL); goto out; }else if (key.type !=BTRFS_TREE_BLOCK_REF_KEY ) { - goto next; +continue ; }/*
@@ -891,20 +828,20 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, level = cur->level +1 ;/* Search the tree to find parent blocks referring the block. */ - path2->search_commit_root =1 ; - path2->skip_locking =1 ; - path2->lowest_level = level; - ret =btrfs_search_slot (NULL , root, node_key, path2,0 ,0 ); - path2->lowest_level =0 ; + path->search_commit_root =1 ; + path->skip_locking =1 ; + path->lowest_level = level; + ret =btrfs_search_slot (NULL , root, node_key, path,0 ,0 ); + path->lowest_level =0 ;if (ret <0 ) { err = ret; goto out; } -if (ret >0 && path2->slots[level] >0 ) - path2->slots[level]--; +if (ret >0 && path->slots[level] >0 ) + path->slots[level]--; - eb = path2->nodes[level]; -if (btrfs_node_blockptr (eb, path2->slots[level]) != + eb = path->nodes[level]; +if (btrfs_node_blockptr (eb, path->slots[level]) != cur->bytenr) { btrfs_err(root->fs_info, "couldn't find block (%llu) (level %d) in tree (%llu) with key (%llu %u %llu)",
@@ -920,7 +857,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,/* Add all nodes and edges in the path */ for (; level <BTRFS_MAX_LEVEL ; level++) { -if (!path2->nodes[level]) { +if (!path->nodes[level]) {ASSERT (btrfs_root_bytenr (&root->root_item) == lower->bytenr);if (should_ignore_root (root))
@@ -936,7 +873,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, goto out; } - eb = path2->nodes[level]; + eb = path->nodes[level]; rb_node =tree_search (&cache->rb_root, eb->start);if (!rb_node) { upper =alloc_backref_node (cache);
@@ -993,20 +930,14 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, lower = upper; upper =NULL ; } -btrfs_release_path (path2); -next: -if (ptr < end) { - ptr +=btrfs_extent_inline_ref_size (key.type); -if (ptr >= end) { -WARN_ON (ptr > end); - ptr =0 ; - end =0 ; - } - } -if (ptr >= end) - path1->slots[0 ]++; +btrfs_release_path (path); + } +if (ret <0 ) { + err = ret; + goto out; } -btrfs_release_path (path1); + ret =0 ; +btrfs_backref_iter_release (iter); cur->checked =1 ;WARN_ON (exist);
@@ -1124,8 +1055,8 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, } } out: -btrfs_free_path (path1); -btrfs_free_path (path2); +btrfs_backref_iter_free (iter); +btrfs_free_path (path);if (err) {while (!list_empty (&useless)) { lower = list_entry(useless.next,
Signature · 1 line
2.25.1
PATCH 4/10 btrfs: relocation: Rename mark_block_processed() and __mark_block_processed()
In reply to Qu WenruoThese two functions are weirdly named, mark_block_processed() in fact just mark a range dirty unconditionally, while __mark_block_processed() does extra check before doing the marking.
Rename mark_block_processed() to mark_range_processed(), and rename __mark_block_processed() to mark_block_processed().
Since we're here, also kill the forward declaration.
--- fs/btrfs/relocation.c | 65 +++++++++++++++++++++---------------------- 1 file changed, 32 insertions(+), 33 deletions(-)
fs/btrfs/relocation.c +32 -33
@@ -189,8 +189,34 @@ struct reloc_control {static void remove_backref_node (struct backref_cache *cache,struct backref_node *node); -static void __mark_block_processed (struct reloc_control *rc, -struct backref_node *node); + +static int in_block_group (u64 bytenr,struct btrfs_block_group *block_group) +{ +if (bytenr >= block_group->start && + bytenr < block_group->start + block_group->length) +return 1 ; +return 0 ; +} + +static void mark_range_processed (struct reloc_control *rc, +u64 bytenr,u32 blocksize) +{ +set_extent_bits (&rc->processed_blocks, bytenr, bytenr + blocksize -1 , +EXTENT_DIRTY ); +} + +static void mark_block_processed (struct reloc_control *rc, +struct backref_node *node) +{ +u32 blocksize; +if (node->level ==0 || +in_block_group (node->bytenr, rc->block_group)) { + blocksize = rc->extent_root->fs_info->nodesize; +mark_range_processed (rc, node->bytenr, blocksize); + } + node->processed =1 ; +} +static void mapping_tree_init (struct mapping_tree *tree) {
@@ -1045,7 +1071,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,if (list_empty (&lower->upper))list_add (&lower->list, &useless); } -__mark_block_processed (rc, upper); +mark_block_processed (rc, upper);if (upper->level >0 ) {list_add (&upper->list, &cache->detached); upper->detached =1 ;
@@ -1509,14 +1535,6 @@ static struct inode *find_next_inode(struct btrfs_root *root, u64 objectid)return NULL ; } -static int in_block_group (u64 bytenr,struct btrfs_block_group *block_group) -{ -if (bytenr >= block_group->start && - bytenr < block_group->start + block_group->length) -return 1 ; -return 0 ; -} -/* * get new location of data */
@@ -2537,7 +2555,7 @@ struct btrfs_root *select_reloc_root(struct btrfs_trans_handle *trans, next->root = root;list_add_tail (&next->list, &rc->backref_cache.changed); -__mark_block_processed (rc, next); +mark_block_processed (rc, next);break ; }
@@ -2887,25 +2905,6 @@ static int finish_pending_nodes(struct btrfs_trans_handle *trans,return err; } -static void mark_block_processed (struct reloc_control *rc, -u64 bytenr,u32 blocksize) -{ -set_extent_bits (&rc->processed_blocks, bytenr, bytenr + blocksize -1 , -EXTENT_DIRTY ); -} - -static void __mark_block_processed (struct reloc_control *rc, -struct backref_node *node) -{ -u32 blocksize; -if (node->level ==0 || -in_block_group (node->bytenr, rc->block_group)) { - blocksize = rc->extent_root->fs_info->nodesize; -mark_block_processed (rc, node->bytenr, blocksize); - } - node->processed =1 ; -} -/* * mark a block and all blocks directly/indirectly reference the block * as processed.
@@ -2924,7 +2923,7 @@ static void update_processed_blocks(struct reloc_control *rc,if (next->processed)break ; -__mark_block_processed (rc, next); +mark_block_processed (rc, next);if (list_empty (&next->upper))break ;
@@ -4663,7 +4662,7 @@ int btrfs_reloc_cow_block(struct btrfs_trans_handle *trans, }if (first_cow) -__mark_block_processed (rc, node); +mark_block_processed (rc, node);if (first_cow && level >0 ) rc->nodes_relocated += buf->len;
Signature · 1 line
2.25.1
Re: [PATCH 04/10] btrfs: relocation: Rename mark_block_processed() and __mark_block_processed()
Quoted 22 lines · Qu Wenruo
These two functions are weirdly named,
mark_block_processed()in fact just mark a range dirty unconditionally, while__mark_block_processed()does extra check before doing the marking.Rename
mark_block_processed()tomark_range_processed(), and rename__mark_block_processed()tomark_block_processed().Since we're here, also kill the forward declaration.
Signed-off-by Qu Wenruo <[email protected]>--- fs/btrfs/relocation.c | 65 +++++++++++++++++++++---------------------- 1 file changed, 32 insertions(+), 33 deletions(-)fs/btrfs/relocation.c +0
-0@@ -189,8 +189,34 @@ struct reloc_control {static void remove_backref_node (struct backref_cache *cache,struct backref_node *node);
fs/btrfs/relocation.c struct reloc_control { · line 199
Quoted 10 lines
fs/btrfs/relocation.c +8
-2-static void __mark_block_processed (struct reloc_control *rc, -struct backref_node *node); + +static int in_block_group (u64 bytenr,struct btrfs_block_group *block_group) +{ +if (bytenr >= block_group->start && + bytenr < block_group->start + block_group->length) +return 1 ; +return 0 ; +}
This function can be killed altogether and replaced with the in_range macro defined in fs/btrfs/misc.h . The only difference is you'd have to call it
in_range(bytenr, block_group->start, block_group->length);
Seeing how in_block_group is called in only 2 places I don't think it will be a big loss.
fs/btrfs/relocation.c struct reloc_control { · line 206
Quoted 7 lines
fs/btrfs/relocation.c +7
-0+ +static void mark_range_processed (struct reloc_control *rc, +u64 bytenr,u32 blocksize) +{ +set_extent_bits (&rc->processed_blocks, bytenr, bytenr + blocksize -1 , +EXTENT_DIRTY ); +}
Having a wrapper just for this seems a bit pointless, remove it and open code the set_extent_bit call in mark_block_processed.
<snip>
PATCH 5/10 btrfs: relocation: Refactor tree backref processing into its own function
In reply to Qu Wenruobuild_backref_tree() function is painfully long, as it has 3 big parts:
- Tree backref handling
- Weaving backref nodes
- Useless nodes pruning
This patch will move the tree backref handling into its own function, handle_one_tree_backref().
And inside that function, the main works are determined by the backref key:
- BTRFS_SHARED_BLOCK_REF_KEY
We know the parent node bytenr directly.
If the parent is cached, or it's root, call it a day.
If the parent is not cached, add it pending list.
- BTRFS_TREE_BLOCK_REF_KEY
The most complex work.
We need to grab the fs root, do a tree search to locate all its parent nodes, weaving all needed edges, and put all uncached edges to pending edge list.
--- fs/btrfs/relocation.c | 374 +++++++++++++++++++++--------------------- 1 file changed, 191 insertions(+), 183 deletions(-)
fs/btrfs/relocation.c +191 -183
@@ -631,6 +631,195 @@ 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, +struct list_head *useless_node, +struct list_head *pending_edge, +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 backref_node *upper; +struct backref_node *lower; +struct backref_edge *edge; +struct extent_buffer *eb; +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) { + root =find_reloc_root (rc, cur->bytenr); +if (WARN_ON (!root)) +return -ENOENT ; + cur->root = root; +return 0 ; + } + + edge =alloc_backref_edge (cache); +if (!edge) +return -ENOMEM ; + + rb_node =tree_search (&cache->rb_root, ref_key->offset); +if (!rb_node) { +/* Parent node not yet cached */ + upper =alloc_backref_node (cache); +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 +* 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 ]); + } +list_add_tail (&edge->list[LOWER ], &cur->upper); + edge->node[LOWER ] = cur; + edge->node[UPPER ] = upper; +return 0 ; + } + +/* +* key.type == BTRFS_TREE_BLOCK_REF_KEY case, 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); +if (IS_ERR (root)) +return PTR_ERR (root); +if (!test_bit (BTRFS_ROOT_REF_COWS , &root->state)) + cur->cowonly =1 ; + +/* Tree root */ +if (btrfs_root_level (&root->root_item) == cur->level) { +ASSERT (btrfs_root_bytenr (&root->root_item) == + cur->bytenr); +if (should_ignore_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 ); +if (ret <0 ) +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); + 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_root (root)) +list_add (&lower->list, useless_node); +else + lower->root = root; +break ; + } + edge =alloc_backref_edge (cache); +if (!edge) { + ret = -ENOMEM ; + goto out; + } + + eb = path->nodes[level]; + rb_node =tree_search (&cache->rb_root, eb->start); +if (!rb_node) { + upper =alloc_backref_node (cache); +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 ; + +/* +* 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); + } +list_add_tail (&edge->list[LOWER ], &lower->upper); + edge->node[LOWER ] = lower; + edge->node[UPPER ] = upper; + +if (rb_node) +break ; + lower = upper; + upper =NULL ; + } +out: +btrfs_release_path (path); +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
@@ -653,7 +842,6 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,struct btrfs_backref_iter *iter;struct backref_cache *cache = &rc->backref_cache;struct btrfs_path *path;/* For searching parent of TREE_BLOCK_REF */ -struct btrfs_root *root;struct backref_node *cur;struct backref_node *upper;struct backref_node *lower;
@@ -666,7 +854,6 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,int cowonly;int ret;int err =0 ; -bool need_check = true; iter =btrfs_backref_iter_alloc (rc->extent_root->fs_info,GFP_NOFS );if (!iter)
@@ -772,191 +959,12 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,continue ; } -/* SHARED_BLOCK_REF means key.offset is the parent bytenr */ -if (key.type ==BTRFS_SHARED_BLOCK_REF_KEY ) { -if (key.objectid == key.offset) { -/* -* Only root blocks of reloc trees use backref -* pointing to itself. -*/ - root =find_reloc_root (rc, cur->bytenr); -ASSERT (root); - cur->root = root; -break ; - } - - edge =alloc_backref_edge (cache); -if (!edge) { - err = -ENOMEM ; - goto out; - } - rb_node =tree_search (&cache->rb_root, key.offset); -if (!rb_node) { - upper =alloc_backref_node (cache); -if (!upper) { -free_backref_edge (cache, edge); - err = -ENOMEM ; - goto out; - } - upper->bytenr = key.offset; - upper->level = cur->level +1 ; -/* -* backrefs for the upper level block isn't -* cached, add the block to pending list -*/ -list_add_tail (&edge->list[UPPER ], &list); - }else { - upper = rb_entry(rb_node, struct backref_node, - rb_node); -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; - -continue ; - }else if (unlikely (key.type ==BTRFS_EXTENT_REF_V0_KEY )) { - err = -EINVAL ; -btrfs_print_v0_err (rc->extent_root->fs_info); -btrfs_handle_fs_error (rc->extent_root->fs_info, err, -NULL ); - goto out; - }else if (key.type !=BTRFS_TREE_BLOCK_REF_KEY ) { -continue ; - } - -/* -* key.type == BTRFS_TREE_BLOCK_REF_KEY, inline ref offset -* means the root objectid. We need to search the tree to get -* its parent bytenr. -*/ - root =read_fs_root (rc->extent_root->fs_info, key.offset); -if (IS_ERR (root)) { - err =PTR_ERR (root); - goto out; - } - -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_root (root)) -list_add (&cur->list, &useless); -else - cur->root = root; -break ; - } - - 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, node_key, path,0 ,0 ); - path->lowest_level =0 ; + ret =handle_one_tree_backref (rc, &useless, &list, path, + &key, node_key, cur);if (ret <0 ) { err = ret; goto out; } -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 (root->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, - node_key->objectid, node_key->type, - node_key->offset); - err = -ENOENT ; - goto out; - } - lower = cur; - need_check = true; - -/* 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_root (root)) -list_add (&lower->list, &useless); -else - lower->root = root; -break ; - } - - edge =alloc_backref_edge (cache); -if (!edge) { - err = -ENOMEM ; - goto out; - } - - eb = path->nodes[level]; - rb_node =tree_search (&cache->rb_root, eb->start); -if (!rb_node) { - upper =alloc_backref_node (cache); -if (!upper) { -free_backref_edge (cache, edge); - err = -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 ; - -/* -* 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 ], - &list); - }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); - } -list_add_tail (&edge->list[LOWER ], &lower->upper); - edge->node[LOWER ] = lower; - edge->node[UPPER ] = upper; - -if (rb_node) -break ; - lower = upper; - upper =NULL ; - } -btrfs_release_path (path); }if (ret <0 ) { err = ret;
Signature · 1 line
2.25.1
PATCH 6/10 btrfs: relocation: Use wrapper to replace open-coded edge linking
In reply to Qu WenruoSince 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
PATCH 7/10 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
PATCH 8/10 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
PATCH 9/10 btrfs: relocation: Refactor the finishing part of upper linkage into finish_upper_links()
In reply to Qu WenruoAfter handle_one_tree_backref(), all newly added (not cached) edges and nodes have the following features:
- Only backref_edge::list[LOWER] is linked.
This means, we can only iterate from botton to top, not the other direction.
- Newly added nodes are not added to cache rb_tree yet
So to finish the backref cache, we still need to finish the links and add all nodes into backref cache rb_tree.
This patch will refactor the existing code into finish_upper_links(), add more comments of each branch, and why we need to do all these works.
--- fs/btrfs/relocation.c | 163 +++++++++++++++++++++++++++--------------- 1 file changed, 107 insertions(+), 56 deletions(-)
fs/btrfs/relocation.c +107 -56
@@ -952,6 +952,106 @@ static int handle_one_tree_block(struct reloc_control *rc,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. +*/ +static int finish_upper_links (struct backref_cache *cache, +struct backref_node *start, +struct list_head *useless_node) +{ +struct backref_edge *edge; +LIST_HEAD (pending_edge); + +/* +* 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 =tree_insert (&cache->rb_root, upper->bytenr, + &upper->rb_node); +if (rb_node) { +backref_tree_panic (rb_node, -EEXIST , + upper->bytenr); +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 ; +} +/* * build backref tree for a given tree block. root of the backref tree * corresponds the tree block, leaves of the backref tree correspond
@@ -982,7 +1082,6 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,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 ;
@@ -1028,8 +1127,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,* into the cache. */ ASSERT (node->checked); - cowonly = node->cowonly; -if (!cowonly) { +if (!node->cowonly) { rb_node =tree_insert (&cache->rb_root, node->bytenr, &node->rb_node);if (rb_node)
@@ -1037,60 +1135,13 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,list_add_tail (&node->lower, &cache->leaves); } -list_for_each_entry (edge, &node->upper, list[LOWER ]) -list_add_tail (&edge->list[UPPER ], &list); - -while (!list_empty (&list)) { - edge = list_entry(list.next, struct backref_edge, list[UPPER]); -list_del_init (&edge->list[UPPER ]); - upper = edge->node[UPPER ]; -if (upper->detached) { -list_del (&edge->list[LOWER ]); - lower = edge->node[LOWER ]; -free_backref_edge (cache, edge); -if (list_empty (&lower->upper)) -list_add (&lower->list, &useless); -continue ; - } - -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 ; - } - -if (!upper->checked) { -/* -* Still want to blow up for developers since this is a -* logic bug. -*/ -ASSERT (0 ); - err = -EINVAL ; - goto out; - } -if (cowonly != upper->cowonly) { -ASSERT (0 ); - err = -EINVAL ; - goto out; - } - -if (!cowonly) { - rb_node =tree_insert (&cache->rb_root, upper->bytenr, - &upper->rb_node); -if (rb_node) -backref_tree_panic (rb_node, -EEXIST , - upper->bytenr); - } - -list_add_tail (&edge->list[UPPER ], &upper->lower); - -list_for_each_entry (edge, &upper->upper, list[LOWER ]) -list_add_tail (&edge->list[UPPER ], &list); +/* Finish the upper linkage of newly added edges/nodes */ + ret =finish_upper_links (cache, node, &useless); +if (ret <0 ) { + err = ret; + goto out; } +/* * process useless backref nodes. backref nodes for tree leaves * are deleted from the cache. backref nodes for upper level
Signature · 1 line
2.25.1
PATCH 10/10 btrfs: relocation: Refactor the useless nodes handling into its own function
In reply to Qu WenruoThis patch will also add some comment for the cleanup up.
--- fs/btrfs/relocation.c | 111 ++++++++++++++++++++++++++++-------------- 1 file changed, 75 insertions(+), 36 deletions(-)
fs/btrfs/relocation.c +75 -36
@@ -1052,6 +1052,79 @@ static int finish_upper_links(struct backref_cache *cache,return 0 ; } +/* +* For useless nodes, do two major clean ups: +* - Cleanup the children edges and nodes +* If child node is also orphan (no parent) during cleanup, then the +* child node will also be cleaned up. +* +* - Freeing up leaves (level 0), keeps nodes detached +* For nodes, the node is still cached as "detached" +* +* Return false if @node is not in the @useless_nodes list. +* Return true if @node is in the @useless_nodes list. +*/ +static bool handle_useless_nodes (struct reloc_control *rc, +struct list_head *useless_nodes, +struct backref_node *node) +{ +struct backref_cache *cache = &rc->backref_cache; +bool ret = false; + +while (!list_empty (useless_nodes)) { +struct backref_node *cur; + + cur = list_entry(useless_nodes->next, struct backref_node, + list); +list_del_init (&cur->list); + +/* Only tree root nodes can be added to @useless_nodes */ +ASSERT (list_empty (&cur->upper)); + +if (cur == node) + ret = true; + +/* The node is the lowest node */ +if (cur->lowest) { +list_del_init (&cur->lower); + cur->lowest =0 ; + } + +/* Cleanup the lower edges */ +while (!list_empty (&cur->lower)) { +struct backref_edge *edge; +struct backref_node *lower; + + edge =list_entry (cur->lower.next, + struct backref_edge, list[UPPER]); +list_del (&edge->list[UPPER ]); +list_del (&edge->list[LOWER ]); + lower = edge->node[LOWER ]; +free_backref_edge (cache, edge); + +/* Child node is also orphan, queue for cleanup */ +if (list_empty (&lower->upper)) +list_add (&lower->list, useless_nodes); + } +/* Mark this block processed for relocation */ +mark_block_processed (rc, cur); + +/* +* Backref nodes for tree leaves are deleted from the cache. +* Backref nodes for upper level tree blocks are left in the +* cache to avoid unnecessary backref lookup. +*/ +if (cur->level >0 ) { +list_add (&cur->list, &cache->detached); + cur->detached =1 ; + }else { +rb_erase (&cur->rb_node, &cache->rb_root); +free_backref_node (cache, cur); + } + } +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
@@ -1142,42 +1215,8 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, goto out; } -/* -* process useless backref nodes. backref nodes for tree leaves -* are deleted from the cache. backref nodes for upper level -* tree blocks are left in the cache to avoid unnecessary backref -* lookup. -*/ -while (!list_empty (&useless)) { - upper = list_entry(useless.next, struct backref_node, list); -list_del_init (&upper->list); -ASSERT (list_empty (&upper->upper)); -if (upper == node) - node =NULL ; -if (upper->lowest) { -list_del_init (&upper->lower); - upper->lowest =0 ; - } -while (!list_empty (&upper->lower)) { - edge =list_entry (upper->lower.next, - struct backref_edge, list[UPPER]); -list_del (&edge->list[UPPER ]); -list_del (&edge->list[LOWER ]); - lower = edge->node[LOWER ]; -free_backref_edge (cache, edge); - -if (list_empty (&lower->upper)) -list_add (&lower->list, &useless); - } -mark_block_processed (rc, upper); -if (upper->level >0 ) { -list_add (&upper->list, &cache->detached); - upper->detached =1 ; - }else { -rb_erase (&upper->rb_node, &cache->rb_root); -free_backref_node (cache, upper); - } - } +if (handle_useless_nodes (rc, &useless, node)) + node =NULL ; out:btrfs_backref_iter_free (iter);btrfs_free_path (path);
Signature · 1 line
2.25.1
Quoted 2 lines · Qu Wenruo
This branch can be fetched from github:
https://github.com/adam900710/linux/tree/backref_cache_new
This is based on v5.6-rc1, you should base on something more recent. There are many non-trivial conflicts at patch 5 so I stopped there but if you and I like to get the pathes merged, the branch needs to be in a state where it's not that hard to apply the patches.
Minor conflicts are expected, like obvious differences in context or renames, there are tools that can deal with that automatically (I use wiggle).
The branch also contains unrelated patches to the backref code, some of them either upstream or in misc-next. All of that makes it unnecessarily hard to get the patches to for-next when the time comes (reviews, patch backlog processed).
Quoted 8 lines · David Sterba
Quoted 2 lines · Qu Wenruo
This branch can be fetched from github:
https://github.com/adam900710/linux/tree/backref_cache_newThis is based on v5.6-rc1, you should base on something more recent. There are many non-trivial conflicts at patch 5 so I stopped there but if you and I like to get the pathes merged, the branch needs to be in a state where it's not that hard to apply the patches.
Because it looks like current misc-next is not a good place to do proper testing, and it's undergoing frequent updates.
Thus I choose the latest rc when I started the development.
Currently the branch is only for review and my local testing, I just want to make sure that everything works fine before rebasing them to misc-next.
Anyway, next time I'll mention the basis, and explicitly shows that I'll do the rebase (and retest) if you want to try merge.
Thanks,
Qu
Quoted 10 lines
Minor conflicts are expected, like obvious differences in context or renames, there are tools that can deal with that automatically (I use wiggle).
The branch also contains unrelated patches to the backref code, some of them either upstream or in misc-next. All of that makes it unnecessarily hard to get the patches to for-next when the time comes (reviews, patch backlog processed).
Quoted 7 lines · Qu Wenruo
Quoted 4 lines · David Sterba
Quoted 2 lines · Qu Wenruo
This branch can be fetched from github:
https://github.com/adam900710/linux/tree/backref_cache_new
Quoted 7 lines
Quoted 4 lines
This is based on v5.6-rc1, you should base on something more recent. There are many non-trivial conflicts at patch 5 so I stopped there but if you and I like to get the pathes merged, the branch needs to be in a state where it's not that hard to apply the patches.
Because it looks like current misc-next is not a good place to do proper testing, and it's undergoing frequent updates.
Well yes, that's the point and has been like that for a long time. It's a development base that should be reasonably stable, IOW I add patches there when the branch itself passes fstests and the to-be merged patches pass as well.
For the 'reasonably stable' part, fixups and additional functional updates should be minimal but they happen as this is branch that more people start to test, unlike some random patchsets.
Quoted 1 line
Thus I choose the latest rc when I started the development.
Yes but you should also have rebased each week so the latest rc is still the latest one.
Quoted 3 lines
Currently the branch is only for review and my local testing, I just want to make sure that everything works fine before rebasing them to misc-next.
Maybe I have missed you saying it's for review and independent testing, for cleanups this should make no difference once the branch is ported on top of current devel queue (misc-next).
I still think that rebasing once a week on top of current rc+misc-next is feasible and should save time to all of us in the future.
Quoted 2 lines
Anyway, next time I'll mention the basis, and explicitly shows that I'll do the rebase (and retest) if you want to try merge.
Yes mentioning the patch base helps in case it's not something that others would expect, which in most cases is misc-next.