btrfs: qgroup: Use backref cache based backref walk for commit roots
cover btrfs: qgroup: Use backref cache based backref walk for commit roots
This patchset is based on an OLD misc-next branch, please inform me before trying to merge, so I can rebase it to latest misc-next. (There will be tons of conflicts)
The branch can be fetched from github for review/testing.
https://github.com/adam900710/linux/tree/backref_cache_all
The patchset survives all the existing qgroup tests.
=== BACKGROUND ===
One of the biggest problem for qgroup is its performance impact. Although we have improved it in since v5.0 kernel, there is still something slowing down qgroup, the backref walk.
Before this patchset, we use btrfs_find_all_roots() to iterate all roots referring to one extent.
That function is doing a pretty good job, but it doesn't has any cache, which means even we're looking up the same extent, we still need to do the full backref walk.
On the other hand, relocation is doing its own backref cache, and provides a much faster backref walk.
So the patchset is mostly trying to make qgroup backref walk (at least commit root backref walk) to use the same mechanism provided by relocation.
=== BENCHMARK ===
For the performance improvement, the last patch has a benchmark. The following content is completely copied from that patch:
------
Here is a small script to test it:
mkfs.btrfs -f $dev
mount $dev -o space_cache=v2 $mnt
btrfs subvolume create $mnt/src
for ((i = 0; i < 64; i++)); do
for (( j = 0; j < 16; j++)); do
xfs_io -f -c "pwrite 0 2k" $mnt/src/file_inline_$(($i * 16 + $j)) > /dev/null
done
xfs_io -f -c "pwrite 0 1M" $mnt/src/file_reg_$i > /dev/null
sync
btrfs subvol snapshot $mnt/src $mnt/snapshot_$i
done
sync btrfs quota enable $mnt
btrfs quota rescan -w $mnt
Here is the benchmark for above small tests.
The performance material is the total execution time of get_old_roots() for patched kernel (*), and find_all_roots() for original kernel.
*: With CONFIG_BTRFS_FS_CHECK_INTEGRITY disabled, as get_old_roots()
will call find_all_roots() to verify the result if that config is enabled.
| Number of calls | Total exec time |
------------------------------------------------------
find_all_roots()| 732 | 529991034ns get_old_roots() | 732 | 127998312ns
------------------------------------------------------
diff | 0.00 % | -75.8 %
------
=== PATCHSET STRUCTURE ===
Patch 01~14 are refactors of relocation backref. Patch 15~31 are code move.
Patch 32 is the patch that is already in misc-next. Patch 33 is the final preparation for qgroup backref. Patch 34~40 are the qgroup backref cache implementation.
=== CHANGELOG ===
v1:
- Use btrfs_backref_ prefix for exported structure/function
- Add one extra patch to rename backref_(node/edge/cache) The renaming itself is not small, thus better to do the rename first then move them to backref.[ch].
- Add extra Reviewed-by tags.
Qu Wenruo (40):
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: Add backref_cache::pending_edge and
backref_cache::useless_node members
btrfs: relocation: Add backref_cache::fs_info member
btrfs: relocation: Make reloc root search specific for relocation
backref cache
btrfs: relocation: Refactor direct tree backref processing into its
own function
btrfs: relocation: Refactor indirect 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
btrfs: relocation: Add btrfs_ prefix for backref_node/edge/cache
btrfs: Move btrfs_backref_(node|edge|cache) structures to backref.h
btrfs: Rename tree_entry to simple_node and export it
btrfs: Rename backref_cache_init() to btrfs_backref_cache_init() and
move it to backref.c
btrfs: Rename alloc_backref_node() to btrfs_backref_alloc_node() and
move it backref.c
btrfs: Rename alloc_backref_edge() to btrfs_backref_alloc_edge() and
move it backref.c
btrfs: Rename link_backref_edge() to btrfs_backref_link_edge() and
move it backref.h
btrfs: Rename free_backref_(node|edge) to
btrfs_backref_free_(node|edge) and move them to backref.h
btrfs: Rename drop_backref_node() to btrfs_backref_drop_node() and
move its needed facilities to backref.h
btrfs: Rename remove_backref_node() to btrfs_backref_cleanup_node()
and move it to backref.c
btrfs: Rename backref_cache_cleanup() to btrfs_backref_release_cache()
and move it to backref.c
btrfs: Rename backref_tree_panic() to btrfs_backref_panic(), and move
it to backref.c
btrfs: Rename should_ignore_root() to btrfs_should_ignore_reloc_root()
and export it
btrfs: relocation: Open-code read_fs_root() for
handle_indirect_tree_backref()
btrfs: Rename handle_one_tree_block() to btrfs_backref_add_tree_node()
and move it to backref.c
btrfs: Rename finish_upper_links() to
btrfs_backref_finish_upper_links() and move it to backref.c
btrfs: relocation: Move error handling of build_backref_tree() to
backref.c
btrfs: relocation: Use btrfs_find_all_leaves() to locate parent tree
leaves of a data extent
btrfs: backref: Only ignore reloc roots for indrect backref resolve if
the backref cache is for reloction purpose
btrfs: qgroup: Introduce qgroup backref cache
btrfs: qgroup: Introduce qgroup_backref_cache_build() function
btrfs: qgroup: Introduce a function to iterate through backref_cache
to find all parents for specified node
btrfs: qgroup: Introduce helpers to get needed tree block info
btrfs: qgroup: Introduce verification for function to ensure old roots
ulist matches btrfs_find_all_roots() result
btrfs: qgroup: Introduce a new function to get old_roots ulist using
backref cache
btrfs: qgroup: Use backref cache to speed up old_roots search
fs/btrfs/backref.c | 817 +++++++++++++++++++++- fs/btrfs/backref.h | 323 +++++++++ fs/btrfs/ctree.h | 5 + fs/btrfs/disk-io.c | 1 + fs/btrfs/misc.h | 54 ++ fs/btrfs/qgroup.c | 516 +++++++++++++- fs/btrfs/relocation.c | 1499 ++++++++--------------------------------- 7 files changed, 1991 insertions(+), 1224 deletions(-)
Signature · 1 line
2.25.2
PATCH 1/40 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 | 110 +++++++++++++++++++++++++++++++++++++++++++++ fs/btrfs/backref.h | 39 ++++++++++++++++ 2 files changed, 149 insertions(+)
fs/btrfs/backref.c +110 -0
@@ -2299,3 +2299,113 @@ void free_ipath(struct inode_fs_paths *ipath)kvfree (ipath->fspath);kfree (ipath); } + +struct btrfs_backref_iter *btrfs_backref_iter_alloc ( +struct btrfs_fs_info *fs_info,gfp_t gfp_flag) +{ +struct btrfs_backref_iter *ret; + + ret =kzalloc (sizeof (*ret), gfp_flag); +if (!ret) +return NULL ; + + ret->path =btrfs_alloc_path (); +if (!ret) { +kfree (ret); +return NULL ; + } + +/* Current backref iterator only supports iteration in commit root */ + ret->path->search_commit_root =1 ; + ret->path->skip_locking =1 ; + ret->fs_info = fs_info; + +return ret; +} + +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 = (u32 )btrfs_item_ptr_offset (path->nodes[0 ], + path->slots[0 ]); + iter->end_ptr = (u32)(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 precaution 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 = -ENOTSUPP ; + goto release; + } + iter->cur_ptr = (u32)(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 = (u32 )btrfs_item_ptr_offset (path->nodes[0 ], + path->slots[0 ]); + iter->item_ptr = iter->cur_ptr; + iter->end_ptr = (u32)(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 +39 -0
@@ -74,4 +74,43 @@ struct prelim_ref {u64 wanted_disk_byte; }; +/* +* Helper structure to help iterate backrefs of one extent. +* +* Now it only supports iteration for tree block in commit root. +*/ +struct btrfs_backref_iter { +u64 bytenr; +struct btrfs_path *path; +struct btrfs_fs_info *fs_info; +struct btrfs_key cur_key; +u32 item_ptr; +u32 cur_ptr; +u32 end_ptr; +}; + +struct btrfs_backref_iter *btrfs_backref_iter_alloc ( +struct btrfs_fs_info *fs_info,gfp_t gfp_flag); + +static inline void btrfs_backref_iter_free (struct btrfs_backref_iter *iter) +{ +if (!iter) +return ; +btrfs_free_path (iter->path); +kfree (iter); +} + +int btrfs_backref_iter_start (struct btrfs_backref_iter *iter,u64 bytenr); + +static inline void +btrfs_backref_iter_release (struct btrfs_backref_iter *iter) +{ + iter->bytenr =0 ; + iter->item_ptr =0 ; + iter->cur_ptr =0 ; + iter->end_ptr =0 ; +btrfs_release_path (iter->path); +memset (&iter->cur_key,0 ,sizeof (iter->cur_key)); +} +#endif
Signature · 1 line
2.25.2
PATCH 2/40 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
@@ -2409,3 +2409,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 *) + ((unsigned long )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 = (u32 )btrfs_item_ptr_offset (path->nodes[0 ], + path->slots[0 ]); + iter->cur_ptr = iter->item_ptr; + iter->end_ptr = iter->item_ptr + (u32 )btrfs_item_size_nr (path->nodes[0 ], + path->slots[0 ]); +return 0 ; +}
fs/btrfs/backref.h +34 -0
@@ -100,8 +100,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.2
PATCH 3/40 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 | 194 ++++++++++++++---------------------------- 1 file changed, 63 insertions(+), 131 deletions(-)
fs/btrfs/relocation.c +63 -131
@@ -22,6 +22,7 @@#include "print-tree.h" #include "delalloc-space.h" #include "block-group.h" +#include "backref.h" /* * Relocation overview
@@ -652,48 +653,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
@@ -713,10 +672,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;
@@ -725,9 +683,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;
@@ -735,14 +690,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) {
@@ -755,25 +711,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)) {/*
@@ -795,42 +754,21 @@ 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 *) + ((unsigned long )iter->cur_ptr); type =btrfs_get_extent_inline_ref_type (eb, iref,BTRFS_REF_TYPE_BLOCK );if (type ==BTRFS_REF_TYPE_INVALID ) {
@@ -839,9 +777,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; }/*
@@ -854,7 +792,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 */
@@ -900,7 +838,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);
@@ -908,7 +846,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 ; }/*
@@ -941,21 +879,21 @@ 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 ) {btrfs_put_root (root); 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)",
@@ -972,7 +910,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)) {
@@ -991,7 +929,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);
@@ -1051,20 +989,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);
@@ -1182,8 +1114,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.2
PATCH 4/40 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.
This patch will open code old mark_block_processed, and rename __mark_block_processed() to remove the "__" prefix.
Since we're here, also kill the forward declaration, which could also kill in_block_group() with in_range() macro.
--- fs/btrfs/relocation.c | 56 +++++++++++++++++-------------------------- 1 file changed, 22 insertions(+), 34 deletions(-)
fs/btrfs/relocation.c +22 -34
@@ -236,8 +236,22 @@ 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 void mark_block_processed (struct reloc_control *rc, +struct backref_node *node) +{ +u32 blocksize; + +if (node->level ==0 || +in_range (node->bytenr, rc->block_group->start, + rc->block_group->length)) { + blocksize = rc->extent_root->fs_info->nodesize; +set_extent_bits (&rc->processed_blocks, node->bytenr, + node->bytenr + blocksize -1 ,EXTENT_DIRTY ); + } + node->processed =1 ; +} +static void mapping_tree_init (struct mapping_tree *tree) {
@@ -1104,7 +1118,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 ;
@@ -1570,14 +1584,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 */
@@ -1675,7 +1681,8 @@ int replace_file_extents(struct btrfs_trans_handle *trans, num_bytes =btrfs_file_extent_disk_num_bytes (leaf, fi);if (bytenr ==0 )continue ; -if (!in_block_group (bytenr, rc->block_group)) +if (!in_range (bytenr, rc->block_group->start, + rc->block_group->length))continue ;/*
@@ -2605,7 +2612,7 @@ struct btrfs_root *select_reloc_root(struct btrfs_trans_handle *trans,ASSERT (next->root);list_add_tail (&next->list, &rc->backref_cache.changed); -__mark_block_processed (rc, next); +mark_block_processed (rc, next);break ; }
@@ -2955,25 +2962,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.
@@ -2992,7 +2980,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 ;
@@ -4744,7 +4732,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.2
PATCH 6/40 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/relocation.c | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-)
fs/btrfs/relocation.c +6 -2
@@ -163,6 +163,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; };/*
@@ -265,7 +267,8 @@ 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 btrfs_fs_info *fs_info, +struct backref_cache *cache) {int i; cache->rb_root =RB_ROOT ;
@@ -276,6 +279,7 @@ static void backref_cache_init(struct backref_cache *cache)INIT_LIST_HEAD (&cache->leaves);INIT_LIST_HEAD (&cache->pending_edge);INIT_LIST_HEAD (&cache->useless_node); + cache->fs_info = fs_info; }static void backref_cache_cleanup (struct backref_cache *cache)
@@ -4304,7 +4308,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 (fs_info, &rc->backref_cache);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.2
PATCH 5/40 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().
Currently build_backref_tree() is only executed serially, thus moving such local list into backref_cache is still safe.
Also since we're here, use list_first_entry() to replace a lot of list_entry() calls after !list_empty().
--- fs/btrfs/relocation.c | 74 +++++++++++++++++++++++++++---------------- 1 file changed, 46 insertions(+), 28 deletions(-)
fs/btrfs/relocation.c +46 -28
@@ -157,6 +157,12 @@ struct backref_cache {int nr_nodes;int nr_edges; + +/* 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; };/*
@@ -268,6 +274,8 @@ static void backref_cache_init(struct backref_cache *cache)INIT_LIST_HEAD (&cache->changed);INIT_LIST_HEAD (&cache->detached);INIT_LIST_HEAD (&cache->leaves); +INIT_LIST_HEAD (&cache->pending_edge); +INIT_LIST_HEAD (&cache->useless_node); }static void backref_cache_cleanup (struct backref_cache *cache)
@@ -291,6 +299,8 @@ static void backref_cache_cleanup(struct backref_cache *cache)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));
@@ -697,8 +707,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; -LIST_HEAD (list);/* Pending edge list, upper node needs to be checked */ -LIST_HEAD (useless);int cowonly;int ret;int err =0 ;
@@ -763,7 +771,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 ], &cache->pending_edge); }else { exist =NULL ; }
@@ -841,7 +849,8 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,* backrefs for the upper level block isn't * cached, add the block to pending list */ -list_add_tail (&edge->list[UPPER ], &list); +list_add_tail (&edge->list[UPPER ], + &cache->pending_edge); }else { upper = rb_entry(rb_node, struct backref_node, rb_node);
@@ -883,7 +892,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, cur->bytenr);if (should_ignore_root (root)) {btrfs_put_root (root); -list_add (&cur->list, &useless); +list_add (&cur->list, &cache->useless_node); }else { cur->root = root; }
@@ -929,7 +938,8 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, lower->bytenr);if (should_ignore_root (root)) {btrfs_put_root (root); -list_add (&lower->list, &useless); +list_add (&lower->list, + &cache->useless_node); }else { lower->root = root; }
@@ -978,7 +988,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,if (!upper->checked && need_check) { need_check = false;list_add_tail (&edge->list[UPPER ], - &list); + &cache->pending_edge); }else {if (upper->checked) need_check = true;
@@ -1016,8 +1026,9 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,WARN_ON (exist);/* 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]); +if (!list_empty (&cache->pending_edge)) { + edge =list_entry (cache->pending_edge.next, + struct backref_edge, list[UPPER]);list_del_init (&edge->list[UPPER ]); cur = edge->node[UPPER ]; goto again;
@@ -1038,10 +1049,11 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, }list_for_each_entry (edge, &node->upper, list[LOWER ]) -list_add_tail (&edge->list[UPPER ], &list); +list_add_tail (&edge->list[UPPER ], &cache->pending_edge); -while (!list_empty (&list)) { - edge = list_entry(list.next, struct backref_edge, list[UPPER]); +while (!list_empty (&cache->pending_edge)) { + edge =list_first_entry (&cache->pending_edge, + struct backref_edge, list[UPPER]);list_del_init (&edge->list[UPPER ]); upper = edge->node[UPPER ];if (upper->detached) {
@@ -1049,7 +1061,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, lower = edge->node[LOWER ];free_backref_edge (cache, edge);if (list_empty (&lower->upper)) -list_add (&lower->list, &useless); +list_add (&lower->list, &cache->useless_node);continue ; }
@@ -1089,7 +1101,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,list_add_tail (&edge->list[UPPER ], &upper->lower);list_for_each_entry (edge, &upper->upper, list[LOWER ]) -list_add_tail (&edge->list[UPPER ], &list); +list_add_tail (&edge->list[UPPER ], &cache->pending_edge); }/* * process useless backref nodes. backref nodes for tree leaves
@@ -1097,8 +1109,9 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,* 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); +while (!list_empty (&cache->useless_node)) { + upper =list_first_entry (&cache->useless_node, + struct backref_node, list);list_del_init (&upper->list);ASSERT (list_empty (&upper->upper));if (upper == node)
@@ -1108,7 +1121,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, upper->lowest =0 ; }while (!list_empty (&upper->lower)) { - edge =list_entry (upper->lower.next, + edge =list_first_entry (&upper->lower, struct backref_edge, list[UPPER]);list_del (&edge->list[UPPER ]);list_del (&edge->list[LOWER ]);
@@ -1116,7 +1129,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,free_backref_edge (cache, edge);if (list_empty (&lower->upper)) -list_add (&lower->list, &useless); +list_add (&lower->list, &cache->useless_node); }mark_block_processed (rc, upper);if (upper->level >0 ) {
@@ -1131,14 +1144,14 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,btrfs_backref_iter_free (iter);btrfs_free_path (path);if (err) { -while (!list_empty (&useless)) { - lower =list_entry (useless.next, +while (!list_empty (&cache->useless_node)) { + lower =list_first_entry (&cache->useless_node, struct backref_node, list);list_del_init (&lower->list); } -while (!list_empty (&list)) { - edge = list_first_entry(&list, struct backref_edge, - list[UPPER ]); +while (!list_empty (&cache->pending_edge)) { + edge =list_first_entry (&cache->pending_edge, + struct backref_edge, list[UPPER]);list_del (&edge->list[UPPER ]);list_del (&edge->list[LOWER ]); lower = edge->node[LOWER ];
@@ -1151,20 +1164,21 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,*/ if (list_empty (&lower->upper) &&RB_EMPTY_NODE (&lower->rb_node)) -list_add (&lower->list, &useless); +list_add (&lower->list, &cache->useless_node);if (!RB_EMPTY_NODE (&upper->rb_node))continue ;/* Add this guy's upper edges to the list to process */ list_for_each_entry (edge, &upper->upper, list[LOWER ]) -list_add_tail (&edge->list[UPPER ], &list); +list_add_tail (&edge->list[UPPER ], + &cache->pending_edge);if (list_empty (&upper->upper)) -list_add (&upper->list, &useless); +list_add (&upper->list, &cache->useless_node); } -while (!list_empty (&useless)) { - lower =list_entry (useless.next, +while (!list_empty (&cache->useless_node)) { + lower =list_first_entry (&cache->useless_node, struct backref_node, list);list_del_init (&lower->list);if (lower == node)
@@ -1173,9 +1187,13 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, }free_backref_node (cache, node); +ASSERT (list_empty (&cache->useless_node) && +list_empty (&cache->pending_edge));return ERR_PTR (err); }ASSERT (!node || !node->detached); +ASSERT (list_empty (&cache->useless_node) && +list_empty (&cache->pending_edge));return node; }
Signature · 1 line
2.25.2
PATCH 7/40 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.
Also for reloc tree root, it's useless and will be queued to useless list.
- 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/ctree.h | 2 ++ fs/btrfs/relocation.c | 50 +++++++++++++++++++++++++++++++++---------- 2 files changed, 41 insertions(+), 11 deletions(-)
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 +39 -11
103 lines not on this page · raw message
Signature · 1 line
2.25.2
PATCH 8/40 btrfs: relocation: Refactor direct tree backref processing into its own function
In reply to Qu WenruoFor BTRFS_SHARED_BLOCK_REF_KEY, its processing is straightforward, as we now the parent node bytenr directly.
If the parent is already cached, or a root, call it a day. If the parent is not cached, add it pending list.
This patch will just refactor this part into its own function, handle_direct_tree_backref() and add some comment explaining the @ref_key parameter.
--- fs/btrfs/relocation.c | 131 +++++++++++++++++++++++++----------------- 1 file changed, 79 insertions(+), 52 deletions(-)
fs/btrfs/relocation.c +79 -52
@@ -697,6 +697,82 @@ static struct btrfs_root *read_fs_root(struct btrfs_fs_info *fs_info,return btrfs_get_fs_root (fs_info, &key, false); } +/* +* Handle direct tree backref. +* +* Direct tree backref means, the backref item shows its parent bytenr +* directly. This is for SHARED_BLOCK_REF backref (keyed or inlined). +* +* @ref_key: The converted backref key. +* For keyed backref, it's the item key. +* For inlined backref, objectid is the bytenr, +* type is btrfs_inline_ref_type, offset is +* btrfs_inline_ref_offset. +*/ +static int handle_direct_tree_backref (struct backref_cache *cache, +struct btrfs_key *ref_key, +struct backref_node *cur) +{ +struct backref_edge *edge; +struct backref_node *upper; +struct rb_node *rb_node; + +ASSERT (ref_key->type ==BTRFS_SHARED_BLOCK_REF_KEY ); + +/* Only reloc root uses backref pointing to itself */ +if (ref_key->objectid == ref_key->offset) { +struct btrfs_root *root; + + cur->is_reloc_root =1 ; +/* Only reloc backref cache cares exact root */ +if (cache->is_reloc) { + root =find_reloc_root (cache->fs_info, cur->bytenr); +if (WARN_ON (!root)) +return -ENOENT ; + cur->root = root; + }else { +/* +* For generic purpose backref cache, reloc root node +* is useless. +*/ +list_add (&cur->list, &cache->useless_node); + } +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 ], &cache->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 ; +} +/* * build backref tree for a given tree block. root of the backref tree * corresponds the tree block, leaves of the backref tree correspond
@@ -718,7 +794,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_fs_info *fs_info = cache->fs_info;struct btrfs_path *path;/* For searching parent of TREE_BLOCK_REF */ struct btrfs_root *root;struct backref_node *cur;
@@ -840,59 +915,11 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,/* SHARED_BLOCK_REF means key.offset is the parent bytenr */ if (key.type ==BTRFS_SHARED_BLOCK_REF_KEY ) { -if (key.objectid == 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)) { - err = -ENOENT ; - goto out; - } - cur->root = root; - }else { -/* -* For generic purpose backref cache, -* reloc root node is useless. -*/ -list_add (&cur->list, - &cache->useless_node); - } -break ; - } - - edge =alloc_backref_edge (cache); -if (!edge) { - err = -ENOMEM ; + ret =handle_direct_tree_backref (cache, &key, cur); +if (ret <0 ) { + err = ret; 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 ], - &cache->pending_edge); - }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 ;
Signature · 1 line
2.25.2
PATCH 9/40 btrfs: relocation: Refactor indirect tree backref processing into its own function
In reply to Qu WenruoThe processing of indirect tree backref (TREE_BLOCK_REF) is the most complex work.
We need to grab the fs root, do a tree search to locate all its parent nodes, linking all needed edges, and put all uncached edges to pending edge list.
This is definitely worthy a helper function.
--- fs/btrfs/relocation.c | 295 +++++++++++++++++++++++------------------- 1 file changed, 160 insertions(+), 135 deletions(-)
fs/btrfs/relocation.c +160 -135
@@ -773,6 +773,164 @@ static int handle_direct_tree_backref(struct backref_cache *cache,return 0 ; } +/* +* Handle indirect tree backref. +* +* Indirect tree backref means, we only know which tree the node belongs to. +* Need to do a tree search to find out parents. This is for TREE_BLOCK_REF +* backref (keyed or inlined). +* +* @ref_key: The same as @ref_key in handle_direct_tree_backref() +* @tree_key: The first key of this tree block. +* @path: A clean (released) path, to avoid allocating path everytime +* the function get called. +*/ +static int handle_indirect_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 backref_node *upper; +struct backref_node *lower; +struct backref_edge *edge; +struct extent_buffer *eb; +struct btrfs_root *root; +struct rb_node *rb_node; +int level; +bool need_check = true; +int ret; + + 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 ; + +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)) { +btrfs_put_root (root); +list_add (&cur->list, &cache->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_root (root)) { +btrfs_put_root (root); +list_add (&lower->list, &cache->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 =tree_search (&cache->rb_root, eb->start); +if (!rb_node) { + upper =alloc_backref_node (cache); +if (!upper) { +btrfs_put_root (root); +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 ], + &cache->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) { +btrfs_put_root (root); +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
@@ -795,7 +953,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;
@@ -806,7 +963,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)
@@ -936,143 +1092,12 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,* 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)) { -btrfs_put_root (root); -list_add (&cur->list, &cache->useless_node); - }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_indirect_tree_backref (cache, path, &key, node_key, + cur);if (ret <0 ) { -btrfs_put_root (root); 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); -btrfs_put_root (root); - 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)) { -btrfs_put_root (root); -list_add (&lower->list, - &cache->useless_node); - }else { - lower->root = root; - } -break ; - } - - edge =alloc_backref_edge (cache); -if (!edge) { -btrfs_put_root (root); - 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) { -btrfs_put_root (root); -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 ], - &cache->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) { -btrfs_put_root (root); -break ; - } - lower = upper; - upper =NULL ; - } -btrfs_release_path (path); }if (ret <0 ) { err = ret;
Signature · 1 line
2.25.2
PATCH 10/40 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
@@ -91,10 +91,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 */
@@ -129,17 +131,26 @@ struct backref_node { unsigned int is_reloc_root: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 */
@@ -362,6 +373,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 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) {
@@ -767,9 +794,7 @@ static int handle_direct_tree_backref(struct backref_cache *cache,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 ; }
@@ -915,9 +940,7 @@ static int handle_indirect_tree_backref(struct backref_cache *cache,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) {btrfs_put_root (root);
@@ -1341,10 +1364,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.2
PATCH 11/40 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 | 39 +++++++++++++++++++-------------------- 1 file changed, 19 insertions(+), 20 deletions(-)
fs/btrfs/relocation.c +19 -20
@@ -338,18 +338,23 @@ 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); -INIT_LIST_HEAD (&node->upper); -INIT_LIST_HEAD (&node->lower); -RB_CLEAR_NODE (&node->rb_node); - cache->nr_nodes++; - } +if (!node) +return 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; }
@@ -774,13 +779,12 @@ static int handle_direct_tree_backref(struct backref_cache *cache, 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
@@ -897,16 +901,15 @@ static int handle_indirect_tree_backref(struct backref_cache *cache, 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) {btrfs_put_root (root);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 ;
@@ -997,14 +1000,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:
@@ -1347,12 +1348,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 =btrfs_grab_root (dest);
Signature · 1 line
2.25.2
PATCH 12/40 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 do {} while() loop to implement the same thing.
--- fs/btrfs/relocation.c | 170 ++++++++++++++++++++++-------------------- 1 file changed, 89 insertions(+), 81 deletions(-)
fs/btrfs/relocation.c +89 -81
@@ -957,77 +957,31 @@ static int handle_indirect_tree_backref(struct backref_cache *cache,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 backref_cache *cache, +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 btrfs_fs_info *fs_info = cache->fs_info;struct backref_edge *edge; -struct rb_node *rb_node; -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 * 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; +if (ret <0 ) goto out; - }/* No extra backref? This means the tree block is corrupted */ if (ret >0 ) { - err = -EUCLEAN ; + ret = -EUCLEAN ; goto out; } }
@@ -1070,7 +1024,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;
@@ -1096,16 +1050,13 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,/* SHARED_BLOCK_REF means key.offset is the parent bytenr */ if (key.type ==BTRFS_SHARED_BLOCK_REF_KEY ) { ret =handle_direct_tree_backref (cache, &key, cur); -if (ret <0 ) { - err = ret; +if (ret <0 ) goto out; - }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 ); + ret = -EINVAL ; +btrfs_print_v0_err (fs_info); +btrfs_handle_fs_error (fs_info, ret,NULL ); goto out; }else if (key.type !=BTRFS_TREE_BLOCK_REF_KEY ) {continue ;
@@ -1118,30 +1069,87 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,*/ ret =handle_indirect_tree_backref (cache, path, &key, node_key, cur); -if (ret <0 ) { - err = ret; +if (ret <0 ) goto out; - } - } -if (ret <0 ) { - err = ret; - 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 (&cache->pending_edge)) { - edge =list_entry (cache->pending_edge.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; +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 */ +do { + ret =handle_one_tree_block (cache, path, iter, node_key, cur); +if (ret <0 ) { + err = ret; + goto out; + } + edge =list_first_entry_or_null (&cache->pending_edge, + struct backref_edge, list[UPPER]); +/* +* the pending list isn't empty, take the first block to +* process +*/ +if (edge) { +list_del_init (&edge->list[UPPER ]); + cur = edge->node[UPPER ]; + } + }while (edge); +/* * everything goes well, connect backref nodes and insert backref nodes * into the cache.
Signature · 1 line
2.25.2
PATCH 13/40 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 | 186 ++++++++++++++++++++++++++---------------- 1 file changed, 117 insertions(+), 69 deletions(-)
fs/btrfs/relocation.c +117 -69
@@ -1080,6 +1080,118 @@ static int handle_one_tree_block(struct backref_cache *cache,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 = &cache->useless_node; +struct backref_edge *edge; +struct rb_node *rb_node; +LIST_HEAD (pending_edge); + +ASSERT (start->checked); + +/* Insert this node to cache if it's not cowonly */ +if (!start->cowonly) { + rb_node =tree_insert (&cache->rb_root, start->bytenr, + &start->rb_node); +if (rb_node) +backref_tree_panic (rb_node, -EEXIST , start->bytenr); +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_first_entry(&pending_edge, 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
@@ -1107,8 +1219,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 cowonly;int ret;int err =0 ;
@@ -1150,75 +1260,13 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, } }while (edge); -/* -* everything goes well, connect backref nodes and insert backref nodes -* into the cache. -*/ -ASSERT (node->checked); - cowonly = node->cowonly; -if (!cowonly) { - rb_node =tree_insert (&cache->rb_root, node->bytenr, - &node->rb_node); -if (rb_node) -backref_tree_panic (rb_node, -EEXIST , node->bytenr); -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 ) { + err = ret; + goto out; } -list_for_each_entry (edge, &node->upper, list[LOWER ]) -list_add_tail (&edge->list[UPPER ], &cache->pending_edge); - -while (!list_empty (&cache->pending_edge)) { - edge =list_first_entry (&cache->pending_edge, - 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, &cache->useless_node); -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 ], &cache->pending_edge); - }/* * process useless backref nodes. backref nodes for tree leaves * are deleted from the cache. backref nodes for upper level
Signature · 1 line
2.25.2
PATCH 14/40 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 | 112 ++++++++++++++++++++++++++++-------------- 1 file changed, 75 insertions(+), 37 deletions(-)
fs/btrfs/relocation.c +75 -37
@@ -1192,6 +1192,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 backref_node *node) +{ +struct backref_cache *cache = &rc->backref_cache; +struct list_head *useless_node = &cache->useless_node; +bool ret = false; + +while (!list_empty (useless_node)) { +struct backref_node *cur; + + cur = list_first_entry(useless_node, 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_node); + } +/* 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
@@ -1267,43 +1340,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 (&cache->useless_node)) { - upper =list_first_entry (&cache->useless_node, - 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_first_entry (&upper->lower, - 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, &cache->useless_node); - } -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, node)) + node =NULL ; out:btrfs_backref_iter_free (iter);btrfs_free_path (path);
Signature · 1 line
2.25.2
PATCH 15/40 btrfs: relocation: Add btrfs_ prefix for backref_node/edge/cache
In reply to Qu WenruoThose three structures are the main elements of backref cache. Add the "btrfs_" prefix for later export.
--- fs/btrfs/relocation.c | 282 +++++++++++++++++++++--------------------- 1 file changed, 143 insertions(+), 139 deletions(-)
fs/btrfs/relocation.c +143 -139
@@ -72,7 +72,7 @@*/ /* -* backref_node, mapping_node and tree_block start with this +* btrfs_backref_node, mapping_node and tree_block start with this */ struct tree_entry {struct rb_node rb_node;
@@ -82,7 +82,7 @@ struct tree_entry {/* * present a tree block in the backref cache */ -struct backref_node { +struct btrfs_backref_node {struct rb_node rb_node;u64 bytenr;
@@ -137,10 +137,11 @@ struct backref_node {/* * present an edge connecting upper and lower backref nodes. */ -struct backref_edge { +struct btrfs_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. +* list[LOWER] is linked to btrfs_backref_node::upper of lower level +* node, and list[UPPER] is linked to btrfs_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.
@@ -148,15 +149,15 @@ struct backref_edge {struct list_head list[2 ];/* Two related nodes */ -struct backref_node *node[2 ]; +struct btrfs_backref_node *node[2 ]; }; -struct backref_cache { +struct btrfs_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 ]; +struct btrfs_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
@@ -236,7 +237,7 @@ struct reloc_control {struct btrfs_block_rsv *block_rsv; -struct backref_cache backref_cache; +struct btrfs_backref_cache backref_cache;struct file_extent_cluster cluster;/* tree blocks have been processed */
@@ -267,11 +268,11 @@ struct reloc_control {#define MOVE_DATA_EXTENTS 0#define UPDATE_DATA_PTRS 1 -static void remove_backref_node (struct backref_cache *cache, -struct backref_node *node); +static void remove_backref_node (struct btrfs_backref_cache *cache, +struct btrfs_backref_node *node);static void mark_block_processed (struct reloc_control *rc, -struct backref_node *node) +struct btrfs_backref_node *node) {u32 blocksize;
@@ -293,7 +294,7 @@ static void mapping_tree_init(struct mapping_tree *tree) }static void backref_cache_init (struct btrfs_fs_info *fs_info, -struct backref_cache *cache,int is_reloc) +struct btrfs_backref_cache *cache,int is_reloc) {int i; cache->rb_root =RB_ROOT ;
@@ -308,20 +309,20 @@ static void backref_cache_init(struct btrfs_fs_info *fs_info, cache->is_reloc = is_reloc; } -static void backref_cache_cleanup (struct backref_cache *cache) +static void backref_cache_cleanup (struct btrfs_backref_cache *cache) { -struct backref_node *node; +struct btrfs_backref_node *node;int i;while (!list_empty (&cache->detached)) { node =list_entry (cache->detached.next, - struct backref_node, list); + struct btrfs_backref_node, list);remove_backref_node (cache, node); }while (!list_empty (&cache->leaves)) { node =list_entry (cache->leaves.next, - struct backref_node, lower); + struct btrfs_backref_node, lower);remove_backref_node (cache, node); }
@@ -338,10 +339,10 @@ 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) +static struct btrfs_backref_node *alloc_backref_node ( +struct btrfs_backref_cache *cache,u64 bytenr,int level) { -struct backref_node *node; +struct btrfs_backref_node *node;ASSERT (level >=0 && level <BTRFS_MAX_LEVEL ); node =kzalloc (sizeof (*node),GFP_NOFS );
@@ -358,8 +359,8 @@ static struct backref_node *alloc_backref_node(struct backref_cache *cache,return node; } -static void free_backref_node (struct backref_cache *cache, -struct backref_node *node) +static void free_backref_node (struct btrfs_backref_cache *cache, +struct btrfs_backref_node *node) {if (node) { cache->nr_nodes--;
@@ -368,9 +369,10 @@ static void free_backref_node(struct backref_cache *cache, } } -static struct backref_edge *alloc_backref_edge (struct backref_cache *cache) +static struct btrfs_backref_edge *alloc_backref_edge ( +struct btrfs_backref_cache *cache) { -struct backref_edge *edge; +struct btrfs_backref_edge *edge; edge =kzalloc (sizeof (*edge),GFP_NOFS );if (edge)
@@ -380,9 +382,9 @@ static struct backref_edge *alloc_backref_edge(struct backref_cache *cache)#define LINK_LOWER (1 << 0)#define LINK_UPPER (1 << 1) -static void link_backref_edge (struct backref_edge *edge, -struct backref_node *lower, -struct backref_node *upper, +static void link_backref_edge (struct btrfs_backref_edge *edge, +struct btrfs_backref_node *lower, +struct btrfs_backref_node *upper,int link_which) {ASSERT (upper && lower && upper->level == lower->level +1 );
@@ -394,8 +396,8 @@ static void link_backref_edge(struct backref_edge *edge,list_add_tail (&edge->list[UPPER ], &upper->lower); } -static void free_backref_edge (struct backref_cache *cache, -struct backref_edge *edge) +static void free_backref_edge (struct btrfs_backref_cache *cache, +struct btrfs_backref_edge *edge) {if (edge) { cache->nr_edges--;
@@ -449,8 +451,8 @@ 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); +struct btrfs_backref_node *bnode =rb_entry (rb_node, + struct btrfs_backref_node, rb_node);if (bnode->root) fs_info = bnode->root->fs_info; btrfs_panic(fs_info, errno,
@@ -461,16 +463,16 @@ static void backref_tree_panic(struct rb_node *rb_node, int errno, u64 bytenr)/* * walk up backref nodes until reach node presents tree root */ -static struct backref_node *walk_up_backref (struct backref_node *node, -struct backref_edge *edges[], -int *index) +static struct btrfs_backref_node *walk_up_backref ( +struct btrfs_backref_node *node, +struct btrfs_backref_edge *edges[],int *index) { -struct backref_edge *edge; +struct btrfs_backref_edge *edge;int idx = *index;while (!list_empty (&node->upper)) { edge =list_entry (node->upper.next, - struct backref_edge, list[LOWER]); + struct btrfs_backref_edge, list[LOWER]); edges[idx++] = edge; node = edge->node[UPPER ]; }
@@ -482,11 +484,11 @@ static struct backref_node *walk_up_backref(struct backref_node *node,/* * walk down backref nodes to find start of next reference path */ -static struct backref_node *walk_down_backref (struct backref_edge *edges[], -int *index) +static struct btrfs_backref_node *walk_down_backref ( +struct btrfs_backref_edge *edges[],int *index) { -struct backref_edge *edge; -struct backref_node *lower; +struct btrfs_backref_edge *edge; +struct btrfs_backref_node *lower;int idx = *index;while (idx >0 ) {
@@ -497,7 +499,7 @@ static struct backref_node *walk_down_backref(struct backref_edge *edges[],continue ; } edge =list_entry (edge->list[LOWER ].next, - struct backref_edge, list[LOWER]); + struct btrfs_backref_edge, list[LOWER]); edges[idx -1 ] = edge; *index = idx;return edge->node[UPPER ];
@@ -506,7 +508,7 @@ static struct backref_node *walk_down_backref(struct backref_edge *edges[],return NULL ; } -static void unlock_node_buffer (struct backref_node *node) +static void unlock_node_buffer (struct btrfs_backref_node *node) {if (node->locked) {btrfs_tree_unlock (node->eb);
@@ -514,7 +516,7 @@ static void unlock_node_buffer(struct backref_node *node) } } -static void drop_node_buffer (struct backref_node *node) +static void drop_node_buffer (struct btrfs_backref_node *node) {if (node->eb) {unlock_node_buffer (node);
@@ -523,8 +525,8 @@ static void drop_node_buffer(struct backref_node *node) } } -static void drop_backref_node (struct backref_cache *tree, -struct backref_node *node) +static void drop_backref_node (struct btrfs_backref_cache *tree, +struct btrfs_backref_node *node) {BUG_ON (!list_empty (&node->upper));
@@ -539,18 +541,18 @@ static void drop_backref_node(struct backref_cache *tree,/* * remove a backref node from the backref cache */ -static void remove_backref_node (struct backref_cache *cache, -struct backref_node *node) +static void remove_backref_node (struct btrfs_backref_cache *cache, +struct btrfs_backref_node *node) { -struct backref_node *upper; -struct backref_edge *edge; +struct btrfs_backref_node *upper; +struct btrfs_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, + edge = list_entry(node->upper.next, struct btrfs_backref_edge, list[LOWER ]); upper = edge->node[UPPER ];list_del (&edge->list[LOWER ]);
@@ -577,8 +579,8 @@ static void remove_backref_node(struct backref_cache *cache,drop_backref_node (cache, node); } -static void update_backref_node (struct backref_cache *cache, -struct backref_node *node,u64 bytenr) +static void update_backref_node (struct btrfs_backref_cache *cache, +struct btrfs_backref_node *node,u64 bytenr) {struct rb_node *rb_node;rb_erase (&node->rb_node, &cache->rb_root);
@@ -592,9 +594,9 @@ static void update_backref_node(struct backref_cache *cache,* update backref cache after a transaction commit */ static int update_backref_cache (struct btrfs_trans_handle *trans, -struct backref_cache *cache) +struct btrfs_backref_cache *cache) { -struct backref_node *node; +struct btrfs_backref_node *node;int level =0 ;if (cache->last_trans ==0 ) {
@@ -612,13 +614,13 @@ static int update_backref_cache(struct btrfs_trans_handle *trans,*/ while (!list_empty (&cache->detached)) { node =list_entry (cache->detached.next, - struct backref_node, list); + struct btrfs_backref_node, list);remove_backref_node (cache, node); }while (!list_empty (&cache->changed)) { node =list_entry (cache->changed.next, - struct backref_node, list); + struct btrfs_backref_node, list);list_del_init (&node->list);BUG_ON (node->pending);update_backref_node (cache, node, node->new_bytenr);
@@ -741,12 +743,12 @@ static struct btrfs_root *read_fs_root(struct btrfs_fs_info *fs_info,* type is btrfs_inline_ref_type, offset is * btrfs_inline_ref_offset. */ -static int handle_direct_tree_backref (struct backref_cache *cache, +static int handle_direct_tree_backref (struct btrfs_backref_cache *cache,struct btrfs_key *ref_key, -struct backref_node *cur) +struct btrfs_backref_node *cur) { -struct backref_edge *edge; -struct backref_node *upper; +struct btrfs_backref_edge *edge; +struct btrfs_backref_node *upper;struct rb_node *rb_node;ASSERT (ref_key->type ==BTRFS_SHARED_BLOCK_REF_KEY );
@@ -793,7 +795,7 @@ static int handle_direct_tree_backref(struct backref_cache *cache,list_add_tail (&edge->list[UPPER ], &cache->pending_edge); }else {/* Parent node already cached */ - upper = rb_entry(rb_node, struct backref_node, + upper = rb_entry(rb_node, struct btrfs_backref_node, rb_node);ASSERT (upper->checked);INIT_LIST_HEAD (&edge->list[UPPER ]);
@@ -814,16 +816,16 @@ static int handle_direct_tree_backref(struct backref_cache *cache,* @path: A clean (released) path, to avoid allocating path everytime * the function get called. */ -static int handle_indirect_tree_backref (struct backref_cache *cache, +static int handle_indirect_tree_backref (struct btrfs_backref_cache *cache,struct btrfs_path *path,struct btrfs_key *ref_key,struct btrfs_key *tree_key, -struct backref_node *cur) +struct btrfs_backref_node *cur) {struct btrfs_fs_info *fs_info = cache->fs_info; -struct backref_node *upper; -struct backref_node *lower; -struct backref_edge *edge; +struct btrfs_backref_node *upper; +struct btrfs_backref_node *lower; +struct btrfs_backref_edge *edge;struct extent_buffer *eb;struct btrfs_root *root;struct rb_node *rb_node;
@@ -937,7 +939,8 @@ static int handle_indirect_tree_backref(struct backref_cache *cache,INIT_LIST_HEAD (&edge->list[UPPER ]); } }else { - upper = rb_entry(rb_node, struct backref_node, rb_node); + upper = rb_entry(rb_node, struct btrfs_backref_node, + rb_node);ASSERT (upper->checked);INIT_LIST_HEAD (&edge->list[UPPER ]);if (!upper->owner)
@@ -957,15 +960,15 @@ static int handle_indirect_tree_backref(struct backref_cache *cache,return ret; } -static int handle_one_tree_block (struct backref_cache *cache, +static int handle_one_tree_block (struct btrfs_backref_cache *cache,struct btrfs_path *path,struct btrfs_backref_iter *iter,struct btrfs_key *node_key, -struct backref_node *cur) +struct btrfs_backref_node *cur) {struct btrfs_fs_info *fs_info = cache->fs_info; -struct backref_edge *edge; -struct backref_node *exist; +struct btrfs_backref_edge *edge; +struct btrfs_backref_node *exist;int ret; ret =btrfs_backref_iter_start (iter, cur->bytenr);
@@ -992,7 +995,7 @@ static int handle_one_tree_block(struct backref_cache *cache,* backref of type BTRFS_TREE_BLOCK_REF_KEY */ ASSERT (list_is_singular (&cur->upper)); - edge = list_entry(cur->upper.next, struct backref_edge, + edge = list_entry(cur->upper.next, struct btrfs_backref_edge, list[LOWER ]);ASSERT (list_empty (&edge->list[UPPER ])); exist = edge->node[UPPER ];
@@ -1083,19 +1086,20 @@ static int handle_one_tree_block(struct backref_cache *cache,/* * 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 means we can only iterate through btrfs_backref_node::upper to reach +* parent edges, but not through btrfs_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. +* This function will finish the btrfs_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) +static int finish_upper_links (struct btrfs_backref_cache *cache, +struct btrfs_backref_node *start) {struct list_head *useless_node = &cache->useless_node; -struct backref_edge *edge; +struct btrfs_backref_edge *edge;struct rb_node *rb_node;LIST_HEAD (pending_edge);
@@ -1119,12 +1123,12 @@ static int finish_upper_links(struct backref_cache *cache,list_add_tail (&edge->list[UPPER ], &pending_edge);while (!list_empty (&pending_edge)) { -struct backref_node *upper; -struct backref_node *lower; +struct btrfs_backref_node *upper; +struct btrfs_backref_node *lower;struct rb_node *rb_node; - edge = list_first_entry(&pending_edge, struct backref_edge, - list[UPPER ]); + edge =list_first_entry (&pending_edge, + struct btrfs_backref_edge, list[UPPER]);list_del_init (&edge->list[UPPER ]); upper = edge->node[UPPER ]; lower = edge->node[LOWER ];
@@ -1205,16 +1209,16 @@ static int finish_upper_links(struct backref_cache *cache,* Return true if @node is in the @useless_nodes list. */ static bool handle_useless_nodes (struct reloc_control *rc, -struct backref_node *node) +struct btrfs_backref_node *node) { -struct backref_cache *cache = &rc->backref_cache; +struct btrfs_backref_cache *cache = &rc->backref_cache;struct list_head *useless_node = &cache->useless_node;bool ret = false;while (!list_empty (useless_node)) { -struct backref_node *cur; +struct btrfs_backref_node *cur; - cur = list_first_entry(useless_node, struct backref_node, + cur = list_first_entry(useless_node, struct btrfs_backref_node, list);list_del_init (&cur->list);
@@ -1232,11 +1236,11 @@ static bool handle_useless_nodes(struct reloc_control *rc,/* Cleanup the lower edges */ while (!list_empty (&cur->lower)) { -struct backref_edge *edge; -struct backref_node *lower; +struct btrfs_backref_edge *edge; +struct btrfs_backref_node *lower; edge =list_entry (cur->lower.next, - struct backref_edge, list[UPPER]); + struct btrfs_backref_edge, list[UPPER]);list_del (&edge->list[UPPER ]);list_del (&edge->list[LOWER ]); lower = edge->node[LOWER ];
@@ -1280,18 +1284,18 @@ static bool handle_useless_nodes(struct reloc_control *rc,* 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_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_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 btrfs_backref_node *cur; +struct btrfs_backref_node *upper; +struct btrfs_backref_node *lower; +struct btrfs_backref_node *node =NULL ; +struct btrfs_backref_edge *edge;int ret;int err =0 ;
@@ -1322,7 +1326,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, goto out; } edge =list_first_entry_or_null (&cache->pending_edge, - struct backref_edge, list[UPPER]); + struct btrfs_backref_edge, list[UPPER]);/* * the pending list isn't empty, take the first block to * process
@@ -1348,12 +1352,12 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,if (err) {while (!list_empty (&cache->useless_node)) { lower =list_first_entry (&cache->useless_node, - struct backref_node, list); + struct btrfs_backref_node, list);list_del_init (&lower->list); }while (!list_empty (&cache->pending_edge)) { edge =list_first_entry (&cache->pending_edge, - struct backref_edge, list[UPPER]); + struct btrfs_backref_edge, list[UPPER]);list_del (&edge->list[UPPER ]);list_del (&edge->list[LOWER ]); lower = edge->node[LOWER ];
@@ -1381,7 +1385,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,while (!list_empty (&cache->useless_node)) { lower =list_first_entry (&cache->useless_node, - struct backref_node, list); + struct btrfs_backref_node, list);list_del_init (&lower->list);if (lower == node) node =NULL ;
@@ -1410,11 +1414,11 @@ static int clone_backref_node(struct btrfs_trans_handle *trans, struct btrfs_root *dest) {struct btrfs_root *reloc_root = src->reloc_root; -struct backref_cache *cache = &rc->backref_cache; -struct backref_node *node =NULL ; -struct backref_node *new_node; -struct backref_edge *edge; -struct backref_edge *new_edge; +struct btrfs_backref_cache *cache = &rc->backref_cache; +struct btrfs_backref_node *node =NULL ; +struct btrfs_backref_node *new_node; +struct btrfs_backref_edge *edge; +struct btrfs_backref_edge *new_edge;struct rb_node *rb_node;if (cache->last_trans >0 )
@@ -1422,7 +1426,7 @@ static int clone_backref_node(struct btrfs_trans_handle *trans, rb_node =tree_search (&cache->rb_root, src->commit_root->start);if (rb_node) { - node = rb_entry(rb_node, struct backref_node, rb_node); + node = rb_entry(rb_node, struct btrfs_backref_node, rb_node);if (node->detached) node =NULL ;else
@@ -1433,7 +1437,7 @@ static int clone_backref_node(struct btrfs_trans_handle *trans, rb_node =tree_search (&cache->rb_root, reloc_root->commit_root->start);if (rb_node) { - node = rb_entry(rb_node, struct backref_node, + node = rb_entry(rb_node, struct btrfs_backref_node, rb_node);BUG_ON (node->detached); }
@@ -1479,7 +1483,7 @@ static int clone_backref_node(struct btrfs_trans_handle *trans, fail:while (!list_empty (&new_node->lower)) { new_edge =list_entry (new_node->lower.next, - struct backref_edge, list[UPPER]); + struct btrfs_backref_edge, list[UPPER]);list_del (&new_edge->list[UPPER ]);free_backref_edge (cache, new_edge); }
@@ -2796,10 +2800,10 @@ static int record_reloc_root_in_trans(struct btrfs_trans_handle *trans,static noinline_for_stack struct btrfs_root *select_reloc_root(struct btrfs_trans_handle *trans,struct reloc_control *rc, -struct backref_node *node, -struct backref_edge *edges[]) +struct btrfs_backref_node *node, +struct btrfs_backref_edge *edges[]) { -struct backref_node *next; +struct btrfs_backref_node *next;struct btrfs_root *root;int index =0 ;
@@ -2859,12 +2863,12 @@ struct btrfs_root *select_reloc_root(struct btrfs_trans_handle *trans,* counted. return -ENOENT if the block is root of reloc tree. */ static noinline_for_stack -struct btrfs_root *select_one_root(struct backref_node *node) +struct btrfs_root *select_one_root(struct btrfs_backref_node *node) { -struct backref_node *next; +struct btrfs_backref_node *next;struct btrfs_root *root;struct btrfs_root *fs_root =NULL ; -struct backref_edge *edges[BTRFS_MAX_LEVEL -1 ]; +struct btrfs_backref_edge *edges[BTRFS_MAX_LEVEL -1 ];int index =0 ; next = node;
@@ -2896,12 +2900,12 @@ struct btrfs_root *select_one_root(struct backref_node *node)static noinline_for_stack u64 calcu_metadata_size(struct reloc_control *rc, -struct backref_node *node,int reserve) +struct btrfs_backref_node *node,int reserve) {struct btrfs_fs_info *fs_info = rc->extent_root->fs_info; -struct backref_node *next = node; -struct backref_edge *edge; -struct backref_edge *edges[BTRFS_MAX_LEVEL -1 ]; +struct btrfs_backref_node *next = node; +struct btrfs_backref_edge *edge; +struct btrfs_backref_edge *edges[BTRFS_MAX_LEVEL -1 ];u64 num_bytes =0 ;int index =0 ;
@@ -2919,7 +2923,7 @@ u64 calcu_metadata_size(struct reloc_control *rc,break ; edge =list_entry (next->upper.next, - struct backref_edge, list[LOWER]); + struct btrfs_backref_edge, list[LOWER]); edges[index++] = edge; next = edge->node[UPPER ]; }
@@ -2930,7 +2934,7 @@ u64 calcu_metadata_size(struct reloc_control *rc,static int reserve_metadata_space (struct btrfs_trans_handle *trans,struct reloc_control *rc, -struct backref_node *node) +struct btrfs_backref_node *node) {struct btrfs_root *root = rc->extent_root;struct btrfs_fs_info *fs_info = root->fs_info;
@@ -2978,14 +2982,14 @@ static int reserve_metadata_space(struct btrfs_trans_handle *trans,*/ static int do_relocation (struct btrfs_trans_handle *trans,struct reloc_control *rc, -struct backref_node *node, +struct btrfs_backref_node *node,struct btrfs_key *key,struct btrfs_path *path,int lowest) {struct btrfs_fs_info *fs_info = rc->extent_root->fs_info; -struct backref_node *upper; -struct backref_edge *edge; -struct backref_edge *edges[BTRFS_MAX_LEVEL -1 ]; +struct btrfs_backref_node *upper; +struct btrfs_backref_edge *edge; +struct btrfs_backref_edge *edges[BTRFS_MAX_LEVEL -1 ];struct btrfs_root *root;struct extent_buffer *eb;u32 blocksize;
@@ -3141,7 +3145,7 @@ static int do_relocation(struct btrfs_trans_handle *trans,static int link_to_upper (struct btrfs_trans_handle *trans,struct reloc_control *rc, -struct backref_node *node, +struct btrfs_backref_node *node,struct btrfs_path *path) {struct btrfs_key key;
@@ -3155,15 +3159,15 @@ static int finish_pending_nodes(struct btrfs_trans_handle *trans, struct btrfs_path *path, int err) {LIST_HEAD (list ); -struct backref_cache *cache = &rc->backref_cache; -struct backref_node *node; +struct btrfs_backref_cache *cache = &rc->backref_cache; +struct btrfs_backref_node *node;int level;int ret;for (level =0 ; level <BTRFS_MAX_LEVEL ; level++) {while (!list_empty (&cache->pending[level])) { node =list_entry (cache->pending[level].next, - struct backref_node, list); + struct btrfs_backref_node, list);list_move_tail (&node->list, &list);BUG_ON (!node->pending);
@@ -3183,11 +3187,11 @@ static int finish_pending_nodes(struct btrfs_trans_handle *trans,* as processed. */ static void update_processed_blocks (struct reloc_control *rc, -struct backref_node *node) +struct btrfs_backref_node *node) { -struct backref_node *next = node; -struct backref_edge *edge; -struct backref_edge *edges[BTRFS_MAX_LEVEL -1 ]; +struct btrfs_backref_node *next = node; +struct btrfs_backref_edge *edge; +struct btrfs_backref_edge *edges[BTRFS_MAX_LEVEL -1 ];int index =0 ;while (next) {
@@ -3202,7 +3206,7 @@ static void update_processed_blocks(struct reloc_control *rc,break ; edge =list_entry (next->upper.next, - struct backref_edge, list[LOWER]); + struct btrfs_backref_edge, list[LOWER]); edges[index++] = edge; next = edge->node[UPPER ]; }
@@ -3248,7 +3252,7 @@ static int get_tree_block_key(struct btrfs_fs_info *fs_info,*/ static int relocate_tree_block (struct btrfs_trans_handle *trans,struct reloc_control *rc, -struct backref_node *node, +struct btrfs_backref_node *node,struct btrfs_key *key,struct btrfs_path *path) {
@@ -3308,7 +3312,7 @@ int relocate_tree_blocks(struct btrfs_trans_handle *trans, struct reloc_control *rc, struct rb_root *blocks) { struct btrfs_fs_info *fs_info = rc->extent_root->fs_info; -struct backref_node *node; +struct btrfs_backref_node *node;struct btrfs_path *path;struct tree_block *block;struct tree_block *next;
@@ -4906,7 +4910,7 @@ int btrfs_reloc_cow_block(struct btrfs_trans_handle *trans, {struct btrfs_fs_info *fs_info = root->fs_info;struct reloc_control *rc; -struct backref_node *node; +struct btrfs_backref_node *node;int first_cow =0 ;int level;int ret =0 ;
Signature · 1 line
2.25.2
PATCH 16/40 btrfs: Move btrfs_backref_(node|edge|cache) structures to backref.h
In reply to Qu WenruoThese 3 structures are the main part of btrfs backref cache, move them to backref.h to build the basis for later reuse.
--- fs/btrfs/backref.h | 119 ++++++++++++++++++++++++++++++++++++++++++ fs/btrfs/relocation.c | 113 --------------------------------------- 2 files changed, 119 insertions(+), 113 deletions(-)
fs/btrfs/backref.h +119 -0
@@ -147,4 +147,123 @@ 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 btrfs_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 ; + +/* +* 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 +#define UPPER 1 +/* +* present an edge connecting upper and lower backref nodes. +*/ +struct btrfs_backref_edge { +/* +* list[LOWER] is linked to btrfs_backref_node::upper of lower level +* node, and list[UPPER] is linked to btrfs_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 btrfs_backref_node *node[2 ]; +}; + +struct btrfs_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 btrfs_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; + +/* 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; + +struct btrfs_fs_info *fs_info; + +/* +* 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/relocation.c +0 -113
120 lines not on this page · raw message
Signature · 1 line
2.25.2
PATCH 17/40 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
@@ -158,8 +158,10 @@ btrfs_backref_iter_release(struct btrfs_backref_iter *iter)* present a tree block in the backref cache */ struct btrfs_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.2
PATCH 18/40 btrfs: Rename backref_cache_init() to btrfs_backref_cache_init() and move it to backref.c
In reply to Qu Wenruo--- fs/btrfs/backref.c | 17 +++++++++++++++++ fs/btrfs/backref.h | 2 ++ fs/btrfs/relocation.c | 18 +----------------- 3 files changed, 20 insertions(+), 17 deletions(-)
fs/btrfs/backref.c +17 -0
@@ -2467,3 +2467,20 @@ int btrfs_backref_iter_next(struct btrfs_backref_iter *iter) path->slots[0]);return 0 ; } + +void btrfs_backref_init_cache (struct btrfs_fs_info *fs_info, +struct btrfs_backref_cache *cache,int is_reloc) +{ +int i; + + cache->rb_root =RB_ROOT ; +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); +INIT_LIST_HEAD (&cache->pending_edge); +INIT_LIST_HEAD (&cache->useless_node); + cache->fs_info = fs_info; + cache->is_reloc = is_reloc; +}
fs/btrfs/backref.h +2 -0
@@ -268,4 +268,6 @@ struct btrfs_backref_cache { unsigned int is_reloc; }; +void btrfs_backref_init_cache (struct btrfs_fs_info *fs_info, +struct btrfs_backref_cache *cache,int is_reloc);#endif
fs/btrfs/relocation.c +1 -17
@@ -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 btrfs_backref_cache *cache,int is_reloc) -{ -int i; - cache->rb_root =RB_ROOT ; -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); -INIT_LIST_HEAD (&cache->pending_edge); -INIT_LIST_HEAD (&cache->useless_node); - cache->fs_info = fs_info; - cache->is_reloc = is_reloc; -} -static void backref_cache_cleanup (struct btrfs_backref_cache *cache) {struct btrfs_backref_node *node;
@@ -4356,7 +4340,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 (fs_info, &rc->backref_cache,1 ); +btrfs_backref_init_cache (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.2
PATCH 19/40 btrfs: Rename alloc_backref_node() to btrfs_backref_alloc_node() and move it backref.c
In reply to Qu Wenruo--- fs/btrfs/backref.c | 20 ++++++++++++++++++++ fs/btrfs/backref.h | 2 ++ fs/btrfs/relocation.c | 31 ++++++------------------------- 3 files changed, 28 insertions(+), 25 deletions(-)
fs/btrfs/backref.c +20 -0
@@ -2484,3 +2484,23 @@ void btrfs_backref_init_cache(struct btrfs_fs_info *fs_info, cache->fs_info = fs_info; cache->is_reloc = is_reloc; } + +struct btrfs_backref_node *btrfs_backref_alloc_node ( +struct btrfs_backref_cache *cache,u64 bytenr,int level) +{ +struct btrfs_backref_node *node; + +ASSERT (level >=0 && level <BTRFS_MAX_LEVEL ); + node =kzalloc (sizeof (*node),GFP_NOFS ); +if (!node) +return 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
@@ -270,4 +270,6 @@ struct btrfs_backref_cache {void btrfs_backref_init_cache (struct btrfs_fs_info *fs_info,struct btrfs_backref_cache *cache,int is_reloc); +struct btrfs_backref_node *btrfs_backref_alloc_node ( +struct btrfs_backref_cache *cache,u64 bytenr,int level);#endif
fs/btrfs/relocation.c +6 -25
@@ -215,26 +215,6 @@ static void backref_cache_cleanup(struct btrfs_backref_cache *cache)ASSERT (!cache->nr_edges); } -static struct btrfs_backref_node *alloc_backref_node ( -struct btrfs_backref_cache *cache,u64 bytenr,int level) -{ -struct btrfs_backref_node *node; - -ASSERT (level >=0 && level <BTRFS_MAX_LEVEL ); - node =kzalloc (sizeof (*node),GFP_NOFS ); -if (!node) -return 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 btrfs_backref_cache *cache,struct btrfs_backref_node *node) {
@@ -615,7 +595,7 @@ static int handle_direct_tree_backref(struct btrfs_backref_cache *cache, 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, + upper =btrfs_backref_alloc_node (cache, ref_key->offset, cur->level +1 );if (!upper) {free_backref_edge (cache, edge);
@@ -737,8 +717,8 @@ static int handle_indirect_tree_backref(struct btrfs_backref_cache *cache, 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 ); + upper =btrfs_backref_alloc_node (cache, eb->start, + lower->level +1 );if (!upper) {btrfs_put_root (root);free_backref_edge (cache, edge);
@@ -1143,7 +1123,7 @@ struct btrfs_backref_node *build_backref_tree(struct reloc_control *rc, } path->reada =READA_FORWARD ; - node =alloc_backref_node (cache, bytenr, level); + node =btrfs_backref_alloc_node (cache, bytenr, level);if (!node) { err = -ENOMEM ; goto out;
@@ -1280,7 +1260,8 @@ static int clone_backref_node(struct btrfs_trans_handle *trans,if (!node)return 0 ; - new_node =alloc_backref_node (cache, dest->node->start, node->level); + new_node =btrfs_backref_alloc_node (cache, dest->node->start, + node->level);if (!new_node)return -ENOMEM ;
Signature · 1 line
2.25.2
PATCH 20/40 btrfs: Rename alloc_backref_edge() to btrfs_backref_alloc_edge() and move it backref.c
In reply to Qu Wenruo--- fs/btrfs/backref.c | 11 +++++++++++ fs/btrfs/backref.h | 2 ++ fs/btrfs/relocation.c | 17 +++-------------- 3 files changed, 16 insertions(+), 14 deletions(-)
fs/btrfs/backref.c +11 -0
@@ -2504,3 +2504,14 @@ struct btrfs_backref_node *btrfs_backref_alloc_node( node->bytenr = bytenr;return node; } + +struct btrfs_backref_edge *btrfs_backref_alloc_edge ( +struct btrfs_backref_cache *cache) +{ +struct btrfs_backref_edge *edge; + + edge =kzalloc (sizeof (*edge),GFP_NOFS ); +if (edge) + cache->nr_edges++; +return edge; +}
fs/btrfs/backref.h +2 -0
@@ -272,4 +272,6 @@ void btrfs_backref_init_cache(struct btrfs_fs_info *fs_info, struct btrfs_backref_cache *cache, int is_reloc);struct btrfs_backref_node *btrfs_backref_alloc_node (struct btrfs_backref_cache *cache,u64 bytenr,int level); +struct btrfs_backref_edge *btrfs_backref_alloc_edge ( +struct btrfs_backref_cache *cache);#endif
fs/btrfs/relocation.c +3 -14
@@ -225,17 +225,6 @@ static void free_backref_node(struct btrfs_backref_cache *cache, } } -static struct btrfs_backref_edge *alloc_backref_edge ( -struct btrfs_backref_cache *cache) -{ -struct btrfs_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 void link_backref_edge(struct btrfs_backref_edge *edge,
@@ -588,7 +577,7 @@ static int handle_direct_tree_backref(struct btrfs_backref_cache *cache,return 0 ; } - edge =alloc_backref_edge (cache); + edge =btrfs_backref_alloc_edge (cache);if (!edge)return -ENOMEM ;
@@ -707,7 +696,7 @@ static int handle_indirect_tree_backref(struct btrfs_backref_cache *cache,break ; } - edge =alloc_backref_edge (cache); + edge =btrfs_backref_alloc_edge (cache);if (!edge) {btrfs_put_root (root); ret = -ENOMEM ;
@@ -1272,7 +1261,7 @@ static int clone_backref_node(struct btrfs_trans_handle *trans,if (!node->lowest) {list_for_each_entry (edge, &node->lower, list[UPPER ]) { - new_edge =alloc_backref_edge (cache); + new_edge =btrfs_backref_alloc_edge (cache);if (!new_edge) goto fail;
Signature · 1 line
2.25.2
PATCH 21/40 btrfs: Rename link_backref_edge() to btrfs_backref_link_edge() and move it backref.h
In reply to Qu Wenruo--- fs/btrfs/backref.h | 16 ++++++++++++++++ fs/btrfs/relocation.c | 23 ++++------------------- 2 files changed, 20 insertions(+), 19 deletions(-)
fs/btrfs/backref.h +16 -0
@@ -274,4 +274,20 @@ struct btrfs_backref_node *btrfs_backref_alloc_node( struct btrfs_backref_cache *cache, u64 bytenr, int level);struct btrfs_backref_edge *btrfs_backref_alloc_edge (struct btrfs_backref_cache *cache); + +#define LINK_LOWER (1 << 0) +#define LINK_UPPER (1 << 1) +static inline void btrfs_backref_link_edge (struct btrfs_backref_edge *edge, +struct btrfs_backref_node *lower, +struct btrfs_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 +4 -19
@@ -225,21 +225,6 @@ static void free_backref_node(struct btrfs_backref_cache *cache, } } -#define LINK_LOWER (1 << 0) -#define LINK_UPPER (1 << 1) -static void link_backref_edge (struct btrfs_backref_edge *edge, -struct btrfs_backref_node *lower, -struct btrfs_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 btrfs_backref_cache *cache,struct btrfs_backref_edge *edge)
@@ -603,7 +588,7 @@ static int handle_direct_tree_backref(struct btrfs_backref_cache *cache,ASSERT (upper->checked);INIT_LIST_HEAD (&edge->list[UPPER ]); } -link_backref_edge (edge, cur, upper,LINK_LOWER ); +btrfs_backref_link_edge (edge, cur, upper,LINK_LOWER );return 0 ; }
@@ -749,7 +734,7 @@ static int handle_indirect_tree_backref(struct btrfs_backref_cache *cache,if (!upper->owner) upper->owner =btrfs_header_owner (eb); } -link_backref_edge (edge, lower, upper,LINK_LOWER ); +btrfs_backref_link_edge (edge, lower, upper,LINK_LOWER );if (rb_node) {btrfs_put_root (root);
@@ -1265,8 +1250,8 @@ static int clone_backref_node(struct btrfs_trans_handle *trans,if (!new_edge) goto fail; -link_backref_edge (new_edge, edge->node[LOWER ], new_node, -LINK_UPPER ); +btrfs_backref_link_edge (new_edge, edge->node[LOWER ], + new_node,LINK_UPPER ); } }else {list_add_tail (&new_node->lower, &cache->leaves);
Signature · 1 line
2.25.2
PATCH 22/40 btrfs: Rename free_backref_(node|edge) to btrfs_backref_free_(node|edge) and move them to backref.h
In reply to Qu Wenruo--- fs/btrfs/backref.h | 20 ++++++++++++++++++++ fs/btrfs/relocation.c | 44 ++++++++++++------------------------------- 2 files changed, 32 insertions(+), 32 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 {
@@ -290,4 +291,23 @@ static inline void btrfs_backref_link_edge(struct btrfs_backref_edge *edge,if (link_which &LINK_UPPER ) list_add_tail(&edge->list[UPPER], &upper->lower); } +static inline void btrfs_backref_free_node (struct btrfs_backref_cache *cache, +struct btrfs_backref_node *node) +{ +if (node) { + cache->nr_nodes--; +btrfs_put_root (node->root); +kfree (node); + } +} + +static inline void btrfs_backref_free_edge (struct btrfs_backref_cache *cache, +struct btrfs_backref_edge *edge) +{ +if (edge) { + cache->nr_edges--; +kfree (edge); + } +} +#endif
fs/btrfs/relocation.c +12 -32
113 lines not on this page · raw message
Signature · 1 line
2.25.2
PATCH 23/40 btrfs: Rename drop_backref_node() to btrfs_backref_drop_node() and move its 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 | 39 +++++++++++++++++++++++++++++++++++++ fs/btrfs/relocation.c | 45 +++++++------------------------------------ 2 files changed, 46 insertions(+), 38 deletions(-)
fs/btrfs/backref.h +39 -0
@@ -310,4 +310,43 @@ static inline void btrfs_backref_free_edge(struct btrfs_backref_cache *cache, } } +static inline void btrfs_backref_unlock_node_buffer ( +struct btrfs_backref_node *node) +{ +if (node->locked) { +btrfs_tree_unlock (node->eb); + node->locked =0 ; + } +} + +static inline void btrfs_backref_drop_node_buffer ( +struct btrfs_backref_node *node) +{ +if (node->eb) { +btrfs_backref_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 btrfs_backref_drop_node (struct btrfs_backref_cache *tree, +struct btrfs_backref_node *node) +{ +BUG_ON (!list_empty (&node->upper)); + +btrfs_backref_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); +btrfs_backref_free_node (tree, node); +} +#endif
fs/btrfs/relocation.c +7 -38
87 lines not on this page · raw message
Signature · 1 line
2.25.2
PATCH 24/40 btrfs: Rename remove_backref_node() to btrfs_backref_cleanup_node() and move it to backref.c
In reply to Qu WenruoAlso add comment explaining the cleanup progress, to differ it from btrfs_backref_drop_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
@@ -2515,3 +2515,41 @@ struct btrfs_backref_edge *btrfs_backref_alloc_edge( cache->nr_edges++;return edge; } + +void btrfs_backref_cleanup_node (struct btrfs_backref_cache *cache, +struct btrfs_backref_node *node) +{ +struct btrfs_backref_node *upper; +struct btrfs_backref_edge *edge; + +if (!node) +return ; + +BUG_ON (!node->lowest && !node->detached); +while (!list_empty (&node->upper)) { + edge = list_entry(node->upper.next, struct btrfs_backref_edge, + list[LOWER ]); + upper = edge->node[UPPER ]; +list_del (&edge->list[LOWER ]); +list_del (&edge->list[UPPER ]); +btrfs_backref_free_edge (cache, edge); + +if (RB_EMPTY_NODE (&upper->rb_node)) { +BUG_ON (!list_empty (&node->upper)); +btrfs_backref_drop_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 ; + } + } + +btrfs_backref_drop_node (cache, node); +}
fs/btrfs/backref.h +9 -0
@@ -349,4 +349,13 @@ static inline void btrfs_backref_drop_node(struct btrfs_backref_cache *tree, btrfs_backref_free_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 btrfs_backref_cleanup_node (struct btrfs_backref_cache *cache, +struct btrfs_backref_node *node);#endif
fs/btrfs/relocation.c +4 -47
86 lines not on this page · raw message
Signature · 1 line
2.25.2
PATCH 25/40 btrfs: Rename backref_cache_cleanup() to btrfs_backref_release_cache() and move it to backref.c
In reply to Qu WenruoSince we're releasing all existing nodes/edges, other than cleanup the mess after error, "release" is a more proper naming here.
--- fs/btrfs/backref.c | 30 ++++++++++++++++++++++++++++++ fs/btrfs/backref.h | 3 +++ fs/btrfs/relocation.c | 32 +------------------------------- 3 files changed, 34 insertions(+), 31 deletions(-)
fs/btrfs/backref.c +30 -0
@@ -2553,3 +2553,33 @@ void btrfs_backref_cleanup_node(struct btrfs_backref_cache *cache,btrfs_backref_drop_node (cache, node); } + +void btrfs_backref_release_cache (struct btrfs_backref_cache *cache) +{ +struct btrfs_backref_node *node; +int i; + +while (!list_empty (&cache->detached)) { + node =list_entry (cache->detached.next, + struct btrfs_backref_node, list); +btrfs_backref_cleanup_node (cache, node); + } + +while (!list_empty (&cache->leaves)) { + node =list_entry (cache->leaves.next, + struct btrfs_backref_node, lower); +btrfs_backref_cleanup_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 +3 -0
@@ -358,4 +358,7 @@ static inline void btrfs_backref_drop_node(struct btrfs_backref_cache *tree,*/ void btrfs_backref_cleanup_node (struct btrfs_backref_cache *cache,struct btrfs_backref_node *node); + +/* Release all nodes/edges from current cache */ +void btrfs_backref_release_cache (struct btrfs_backref_cache *cache);#endif
fs/btrfs/relocation.c +1 -31
@@ -182,36 +182,6 @@ static void mapping_tree_init(struct mapping_tree *tree)spin_lock_init (&tree->lock); } -static void backref_cache_cleanup (struct btrfs_backref_cache *cache) -{ -struct btrfs_backref_node *node; -int i; - -while (!list_empty (&cache->detached)) { - node =list_entry (cache->detached.next, - struct btrfs_backref_node, list); -btrfs_backref_cleanup_node (cache, node); - } - -while (!list_empty (&cache->leaves)) { - node =list_entry (cache->leaves.next, - struct btrfs_backref_node, lower); -btrfs_backref_cleanup_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) {
@@ -4082,7 +4052,7 @@ static noinline_for_stack int relocate_block_group(struct reloc_control *rc) rc->create_reloc_tree =0 ;set_reloc_control (rc); -backref_cache_cleanup (&rc->backref_cache); +btrfs_backref_release_cache (&rc->backref_cache);btrfs_block_rsv_release (fs_info, rc->block_rsv, (u64)-1 ); err =prepare_to_merge (rc, err);
Signature · 1 line
2.25.2
PATCH 27/40 btrfs: Rename should_ignore_root() to btrfs_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 btrfs_should_ignore_reloc_root() make the name a little more clear.
--- fs/btrfs/ctree.h | 1 + fs/btrfs/relocation.c | 10 ++++++---- 2 files changed, 7 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 btrfs_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 +6 -4
@@ -312,7 +312,8 @@ 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 btrfs_should_ignore_reloc_root() below is a +* special case. */ static bool have_reloc_root (struct btrfs_root *root) {
@@ -323,7 +324,7 @@ static bool have_reloc_root(struct btrfs_root *root)return true; } -static int should_ignore_root (struct btrfs_root *root) +int btrfs_should_ignore_reloc_root (struct btrfs_root *root) {struct btrfs_root *reloc_root;
@@ -349,6 +350,7 @@ static int should_ignore_root(struct btrfs_root *root)*/ return 1 ; } +/* * find reloc tree by address of tree root */
@@ -494,7 +496,7 @@ static int handle_indirect_tree_backref(struct btrfs_backref_cache *cache,/* tree root */ ASSERT (btrfs_root_bytenr (&root->root_item) == cur->bytenr); -if (should_ignore_root (root)) { +if (btrfs_should_ignore_reloc_root (root)) {btrfs_put_root (root);list_add (&cur->list, &cache->useless_node); }else {
@@ -535,7 +537,7 @@ static int handle_indirect_tree_backref(struct btrfs_backref_cache *cache,if (!path->nodes[level]) {ASSERT (btrfs_root_bytenr (&root->root_item) == lower->bytenr); -if (should_ignore_root (root)) { +if (btrfs_should_ignore_reloc_root (root)) {btrfs_put_root (root);list_add (&lower->list, &cache->useless_node); }else {
Signature · 1 line
2.25.2
PATCH 26/40 btrfs: Rename backref_tree_panic() to btrfs_backref_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
@@ -361,4 +361,12 @@ void btrfs_backref_cleanup_node(struct btrfs_backref_cache *cache,/* Release all nodes/edges from current cache */ void btrfs_backref_release_cache (struct btrfs_backref_cache *cache); + +static inline void btrfs_backref_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 btrfs_backref_node *bnode =rb_entry (rb_node, - struct btrfs_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 btrfs_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); +btrfs_backref_panic (cache->fs_info, bytenr, -EEXIST ); }/*
@@ -774,7 +761,8 @@ static int finish_upper_links(struct btrfs_backref_cache *cache, rb_node =simple_insert (&cache->rb_root, start->bytenr, &start->rb_node);if (rb_node) -backref_tree_panic (rb_node, -EEXIST , start->bytenr); +btrfs_backref_panic (cache->fs_info, start->bytenr, + -EEXIST );list_add_tail (&start->lower, &cache->leaves); }
@@ -842,8 +830,8 @@ static int finish_upper_links(struct btrfs_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); +btrfs_backref_panic (cache->fs_info, + upper->bytenr, -EEXIST );return -EUCLEAN ; } }
@@ -1136,7 +1124,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); +btrfs_backref_panic (trans->fs_info, new_node->bytenr, -EEXIST );if (!new_node->lowest) {list_for_each_entry (new_edge, &new_node->lower, list[UPPER ]) {
@@ -1248,7 +1236,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); +btrfs_backref_panic (fs_info, node->bytenr, -EEXIST );return 0 ; }
@@ -3334,7 +3322,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); +btrfs_backref_panic (rc->extent_root->fs_info, block->bytenr, + -EEXIST );return 0 ; }
@@ -3632,8 +3621,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); +btrfs_backref_panic (fs_info, block->bytenr, + -EEXIST ); }if (counted) added =1 ;
Signature · 1 line
2.25.2
PATCH 28/40 btrfs: relocation: Open-code read_fs_root() for handle_indirect_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
@@ -481,12 +481,16 @@ static int handle_indirect_tree_backref(struct btrfs_backref_cache *cache,struct btrfs_backref_edge *edge;struct extent_buffer *eb;struct btrfs_root *root; +struct btrfs_key root_key;struct rb_node *rb_node;int level;bool need_check = true;int ret; - 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.2
PATCH 29/40 btrfs: Rename handle_one_tree_block() to btrfs_backref_add_tree_node() 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 | 357 +++++++++++++++++++++++++++++++++++++++++ fs/btrfs/backref.h | 16 ++ fs/btrfs/relocation.c | 359 +----------------------------------------- 3 files changed, 375 insertions(+), 357 deletions(-)
fs/btrfs/backref.c +357 -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
@@ -2583,3 +2584,359 @@ void btrfs_backref_release_cache(struct btrfs_backref_cache *cache)ASSERT (!cache->nr_nodes);ASSERT (!cache->nr_edges); } + +/* +* Handle direct tree backref. +* +* Direct tree backref means, the backref item shows its parent bytenr +* directly. This is for SHARED_BLOCK_REF backref (keyed or inlined). +* +* @ref_key: The converted backref key. +* For keyed backref, it's the item key. +* For inlined backref, objectid is the bytenr, +* type is btrfs_inline_ref_type, offset is +* btrfs_inline_ref_offset. +*/ +static int handle_direct_tree_backref (struct btrfs_backref_cache *cache, +struct btrfs_key *ref_key, +struct btrfs_backref_node *cur) +{ +struct btrfs_backref_edge *edge; +struct btrfs_backref_node *upper; +struct rb_node *rb_node; + +ASSERT (ref_key->type ==BTRFS_SHARED_BLOCK_REF_KEY ); + +/* Only reloc root uses backref pointing to itself */ +if (ref_key->objectid == ref_key->offset) { +struct btrfs_root *root; + + cur->is_reloc_root =1 ; +/* Only reloc backref cache cares exact root */ +if (cache->is_reloc) { + root =find_reloc_root (cache->fs_info, cur->bytenr); +if (WARN_ON (!root)) +return -ENOENT ; + cur->root = root; + }else { +/* +* For generic purpose backref cache, reloc root node +* is useless. +*/ +list_add (&cur->list, &cache->useless_node); + } +return 0 ; + } + + edge =btrfs_backref_alloc_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 =btrfs_backref_alloc_node (cache, ref_key->offset, + cur->level +1 ); +if (!upper) { +btrfs_backref_free_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 ], &cache->pending_edge); + }else { +/* Parent node already cached */ + upper = rb_entry(rb_node, struct btrfs_backref_node, + rb_node); +ASSERT (upper->checked); +INIT_LIST_HEAD (&edge->list[UPPER ]); + } +btrfs_backref_link_edge (edge, cur, upper,LINK_LOWER ); +return 0 ; +} + +/* +* Handle indirect tree backref. +* +* Indirect tree backref means, we only know which tree the node belongs to. +* Need to do a tree search to find out parents. This is for TREE_BLOCK_REF +* backref (keyed or inlined). +* +* @ref_key: The same as @ref_key in handle_direct_tree_backref() +* @tree_key: The first key of this tree block. +* @path: A clean (released) path, to avoid allocating path everytime +* the function get called. +*/ +static int handle_indirect_tree_backref (struct btrfs_backref_cache *cache, +struct btrfs_path *path, +struct btrfs_key *ref_key, +struct btrfs_key *tree_key, +struct btrfs_backref_node *cur) +{ +struct btrfs_fs_info *fs_info = cache->fs_info; +struct btrfs_backref_node *upper; +struct btrfs_backref_node *lower; +struct btrfs_backref_edge *edge; +struct extent_buffer *eb; +struct btrfs_root *root; +struct btrfs_key root_key; +struct rb_node *rb_node; +int level; +bool need_check = true; +int ret; + + 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 (btrfs_should_ignore_reloc_root (root)) { +btrfs_put_root (root); +list_add (&cur->list, &cache->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 (btrfs_should_ignore_reloc_root (root)) { +btrfs_put_root (root); +list_add (&lower->list, &cache->useless_node); + }else { + lower->root = root; + } +break ; + } + + edge =btrfs_backref_alloc_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 =btrfs_backref_alloc_node (cache, eb->start, + lower->level +1 ); +if (!upper) { +btrfs_put_root (root); +btrfs_backref_free_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 ], + &cache->pending_edge); + }else { +if (upper->checked) + need_check = true; +INIT_LIST_HEAD (&edge->list[UPPER ]); + } + }else { + upper = rb_entry(rb_node, struct btrfs_backref_node, + rb_node); +ASSERT (upper->checked); +INIT_LIST_HEAD (&edge->list[UPPER ]); +if (!upper->owner) + upper->owner =btrfs_header_owner (eb); + } +btrfs_backref_link_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 btrfs_backref_add_tree_node (struct btrfs_backref_cache *cache, +struct btrfs_path *path, +struct btrfs_backref_iter *iter, +struct btrfs_key *node_key, +struct btrfs_backref_node *cur) +{ +struct btrfs_fs_info *fs_info = cache->fs_info; +struct btrfs_backref_edge *edge; +struct btrfs_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 btrfs_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 *) + ((unsigned long )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 ; + } + +/* SHARED_BLOCK_REF means key.offset is the parent bytenr */ +if (key.type ==BTRFS_SHARED_BLOCK_REF_KEY ) { + ret =handle_direct_tree_backref (cache, &key, cur); +if (ret <0 ) + goto out; +continue ; + }else if (unlikely (key.type ==BTRFS_EXTENT_REF_V0_KEY )) { + ret = -EINVAL ; +btrfs_print_v0_err (fs_info); +btrfs_handle_fs_error (fs_info, ret,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. +*/ + ret =handle_indirect_tree_backref (cache, path, &key, node_key, + cur); +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 +16 -0
@@ -369,4 +369,20 @@ static inline void btrfs_backref_panic(struct btrfs_fs_info *fs_info,"Inconsistency in backref cache found at offset %llu" , bytenr); } + +/* +* Add backref node @cur into @cache. +* +* NOTE: Even if the function returned 0, @cur is not yet cached as its upper +* links aren't yet bi-directional. Needs to finish such links. +* +* @path: Released path for indirect tree backref lookup +* @iter: Released backref iter for extent tree search +* @node_key: The first key of the tree block +*/ +int btrfs_backref_add_tree_node (struct btrfs_backref_cache *cache, +struct btrfs_path *path, +struct btrfs_backref_iter *iter, +struct btrfs_key *node_key, +struct btrfs_backref_node *cur);#endif
fs/btrfs/relocation.c +2 -357
371 lines not on this page · raw message
Signature · 1 line
2.25.2
PATCH 30/40 btrfs: Rename finish_upper_links() to btrfs_backref_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 | 102 +++++++++++++++++++++++++++++++++++++ fs/btrfs/backref.h | 5 ++ fs/btrfs/relocation.c | 116 +----------------------------------------- 3 files changed, 108 insertions(+), 115 deletions(-)
fs/btrfs/backref.c +102 -0
@@ -2940,3 +2940,105 @@ int btrfs_backref_add_tree_node(struct btrfs_backref_cache *cache,btrfs_backref_iter_release (iter);return ret; } + +int btrfs_backref_finish_upper_links (struct btrfs_backref_cache *cache, +struct btrfs_backref_node *start) +{ +struct list_head *useless_node = &cache->useless_node; +struct btrfs_backref_edge *edge; +struct rb_node *rb_node; +LIST_HEAD (pending_edge); + +ASSERT (start->checked); + +/* Insert this node to cache if it's not cowonly */ +if (!start->cowonly) { + rb_node =simple_insert (&cache->rb_root, start->bytenr, + &start->rb_node); +if (rb_node) +btrfs_backref_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 btrfs_backref_node *upper; +struct btrfs_backref_node *lower; +struct rb_node *rb_node; + + edge =list_first_entry (&pending_edge, + struct btrfs_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 ]); +btrfs_backref_free_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) { +btrfs_backref_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 +5 -0
@@ -375,6 +375,7 @@ static inline void btrfs_backref_panic(struct btrfs_fs_info *fs_info,* * NOTE: Even if the function returned 0, @cur is not yet cached as its upper * links aren't yet bi-directional. Needs to finish such links. +* Use btrfs_backref_finish_upper_links() to finish such linkage. * * @path: Released path for indirect tree backref lookup * @iter: Released backref iter for extent tree search
@@ -385,4 +386,8 @@ int btrfs_backref_add_tree_node(struct btrfs_backref_cache *cache,struct btrfs_backref_iter *iter, struct btrfs_key *node_key, struct btrfs_backref_node *cur); + +/* Finish the upwards linkage created by btrfs_backref_add_tree_node(). */ +int btrfs_backref_finish_upper_links (struct btrfs_backref_cache *cache, +struct btrfs_backref_node *start);#endif
fs/btrfs/relocation.c +1 -115
128 lines not on this page · raw message
Signature · 1 line
2.25.2
PATCH 31/40 btrfs: relocation: Move error handling of build_backref_tree() to backref.c
In reply to Qu WenruoThe error cleanup will be extracted as a new function, btrfs_backref_error_cleanup(), and moved to backref.c and exported for later usage.
--- fs/btrfs/backref.c | 54 +++++++++++++++++++++++++++++++++++++++++++ fs/btrfs/backref.h | 3 +++ fs/btrfs/relocation.c | 48 +------------------------------------- 3 files changed, 58 insertions(+), 47 deletions(-)
fs/btrfs/backref.c +54 -0
@@ -3042,3 +3042,57 @@ int btrfs_backref_finish_upper_links(struct btrfs_backref_cache *cache, }return 0 ; } + +void btrfs_backref_error_cleanup (struct btrfs_backref_cache *cache, +struct btrfs_backref_node *node) +{ +struct btrfs_backref_node *lower; +struct btrfs_backref_node *upper; +struct btrfs_backref_edge *edge; + +while (!list_empty (&cache->useless_node)) { + lower =list_first_entry (&cache->useless_node, + struct btrfs_backref_node, list); +list_del_init (&lower->list); + } +while (!list_empty (&cache->pending_edge)) { + edge =list_first_entry (&cache->pending_edge, + struct btrfs_backref_edge, list[UPPER]); +list_del (&edge->list[UPPER ]); +list_del (&edge->list[LOWER ]); + lower = edge->node[LOWER ]; + upper = edge->node[UPPER ]; +btrfs_backref_free_edge (cache, edge); + +/* +* Lower is no longer linked to any upper backref nodes +* and isn't in the cache, we can free it ourselves. +*/ +if (list_empty (&lower->upper) && +RB_EMPTY_NODE (&lower->rb_node)) +list_add (&lower->list, &cache->useless_node); + +if (!RB_EMPTY_NODE (&upper->rb_node)) +continue ; + +/* Add this guy's upper edges to the list to process */ +list_for_each_entry (edge, &upper->upper, list[LOWER ]) +list_add_tail (&edge->list[UPPER ], + &cache->pending_edge); +if (list_empty (&upper->upper)) +list_add (&upper->list, &cache->useless_node); + } + +while (!list_empty (&cache->useless_node)) { + lower =list_first_entry (&cache->useless_node, + struct btrfs_backref_node, list); +list_del_init (&lower->list); +if (lower == node) + node =NULL ; +btrfs_backref_free_node (cache, lower); + } + +btrfs_backref_free_node (cache, node); +ASSERT (list_empty (&cache->useless_node) && +list_empty (&cache->pending_edge)); +}
fs/btrfs/backref.h +3 -0
@@ -390,4 +390,7 @@ int btrfs_backref_add_tree_node(struct btrfs_backref_cache *cache,/* Finish the upwards linkage created by btrfs_backref_add_tree_node(). */ int btrfs_backref_finish_upper_links (struct btrfs_backref_cache *cache,struct btrfs_backref_node *start); + +void btrfs_backref_error_cleanup (struct btrfs_backref_cache *cache, +struct btrfs_backref_node *node);#endif
fs/btrfs/relocation.c +1 -47
60 lines not on this page · raw message
Signature · 1 line
2.25.2
PATCH 33/40 btrfs: backref: Only ignore reloc roots for indrect backref resolve if the backref cache is for reloction purpose
In reply to Qu WenruoFor relocation tree detection, relocation backref cache uses should_ignore_reloc_root() which uses relocation specific checks like checking the DEAD_RELOC_ROOT bit.
However for generic purposed backref cache, we can rely on that check, as it's possible that relocation is also running.
For generic purposed backref cache, we detect reloc root by SHARED_BLOCK_REF item.
Only reloc root node has its parent bytenr pointing back to itself.
And in that case, backref cache will mark the reloc root node useless, dropping any child orphan nodes.
So only call should_ignore_reloc_root() if the backref cache is for relocation.
--- fs/btrfs/backref.c | 16 ++++++++++++++-- 1 file changed, 14 insertions(+), 2 deletions(-)
fs/btrfs/backref.c +14 -2
@@ -2701,7 +2701,17 @@ static int handle_indirect_tree_backref(struct btrfs_backref_cache *cache,/* tree root */ ASSERT (btrfs_root_bytenr (&root->root_item) == cur->bytenr); -if (btrfs_should_ignore_reloc_root (root)) { +/* +* For reloc backref cache, we may ignore reloc root. +* But for generic purposed backref cache, we can't rely +* on btrfs_should_ignore_reloc_root() as it may conflict with +* current running relocation and lead to missing root. +* +* For generic purposed backref cache, reloc root detection +* is completely relying on direct backref (key->offset is +* parent bytenr), thus only do such check for reloc cache. +*/ +if (btrfs_should_ignore_reloc_root (root) && cache->is_reloc) {btrfs_put_root (root);list_add (&cur->list, &cache->useless_node); }else {
@@ -2742,7 +2752,9 @@ static int handle_indirect_tree_backref(struct btrfs_backref_cache *cache,if (!path->nodes[level]) {ASSERT (btrfs_root_bytenr (&root->root_item) == lower->bytenr); -if (btrfs_should_ignore_reloc_root (root)) { +/* Same as previous should_ignore_reloc_root() call */ +if (btrfs_should_ignore_reloc_root (root) && + cache->is_reloc) {btrfs_put_root (root);list_add (&lower->list, &cache->useless_node); }else {
Signature · 1 line
2.25.2
PATCH 32/40 btrfs: relocation: Use btrfs_find_all_leaves() to locate parent tree leaves of a data extent
In reply to Qu WenruoIn relocation, we need to locate all parent tree leaves referring one data extent, thus we have a complex mechanism to iterate through extent tree and subvolume trees to locate related leaves.
However this is already done in backref.c, we have btrfs_find_all_leaves(), which can return a ulist containing all leaves referring to that data extent.
Use btrfs_find_all_leaves() to replace find_data_references().
There is a special handling for v1 space cache data extents, where we need to delete the v1 space cache data extents, to avoid those data extents to hang the data relocation.
In this patch, the special handling is done by re-iterating the root tree leaf.
Although it's a little less efficient than the old handling, considering we can reuse a lot of code, it should be acceptable.
--- fs/btrfs/backref.c | 8 +- fs/btrfs/backref.h | 4 + fs/btrfs/relocation.c | 314 ++++++++---------------------------------- 3 files changed, 62 insertions(+), 264 deletions(-)
fs/btrfs/backref.c +4 -4
@@ -1410,10 +1410,10 @@ static void free_leaf_list(struct ulist *blocks)* * returns 0 on success, <0 on error */ -static int btrfs_find_all_leafs (struct btrfs_trans_handle *trans, -struct btrfs_fs_info *fs_info,u64 bytenr, -u64 time_seq,struct ulist **leafs, -const u64 *extent_item_pos,bool ignore_offset) +int btrfs_find_all_leafs (struct btrfs_trans_handle *trans, +struct btrfs_fs_info *fs_info,u64 bytenr, +u64 time_seq,struct ulist **leafs, +const u64 *extent_item_pos,bool ignore_offset) {int ret;
fs/btrfs/backref.h +4 -0
@@ -41,6 +41,10 @@ int iterate_inodes_from_logical(u64 logical, struct btrfs_fs_info *fs_info,int paths_from_inode (u64 inum,struct inode_fs_paths *ipath); +int btrfs_find_all_leafs (struct btrfs_trans_handle *trans, +struct btrfs_fs_info *fs_info,u64 bytenr, +u64 time_seq,struct ulist **leafs, +const u64 *extent_item_pos,bool ignore_offset);int btrfs_find_all_roots (struct btrfs_trans_handle *trans,struct btrfs_fs_info *fs_info,u64 bytenr,u64 time_seq,struct ulist **roots,bool ignore_offset);
fs/btrfs/relocation.c +54 -260
350 lines not on this page · raw message
Signature · 1 line
2.25.2
PATCH 34/40 btrfs: qgroup: Introduce qgroup backref cache
In reply to Qu WenruoThis adds two new members for btrfs_fs_info:
- struct btrfs_backref_cache *qgroup_backref_cache Only get initialized at qgroup enable time. This is to avoid further bloating up fs_info structure.
- struct mutex qgroup_backref_lock
This is initialized at fs_info initial time.
This patch only introduces the skeleton, just initialization and cleanup for these newly introduced members, no usage of them yet.
--- fs/btrfs/ctree.h | 2 ++ fs/btrfs/disk-io.c | 1 + fs/btrfs/qgroup.c | 53 ++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 56 insertions(+)
fs/btrfs/ctree.h +2 -0
@@ -889,6 +889,8 @@ struct btrfs_fs_info {struct btrfs_workqueue *qgroup_rescan_workers;struct completion qgroup_rescan_completion;struct btrfs_work qgroup_rescan_work; +struct mutex qgroup_backref_lock; +struct btrfs_backref_cache *qgroup_backref_cache;bool qgroup_rescan_running;/* protected by qgroup_rescan_lock */ /* filesystem state */
fs/btrfs/disk-io.c +1 -0
@@ -2123,6 +2123,7 @@ static void btrfs_init_qgroup(struct btrfs_fs_info *fs_info) fs_info->qgroup_ulist =NULL ; fs_info->qgroup_rescan_running = false;mutex_init (&fs_info->qgroup_rescan_lock); +mutex_init (&fs_info->qgroup_backref_lock); } static int btrfs_init_workqueues(struct btrfs_fs_info *fs_info,
fs/btrfs/qgroup.c +53 -0
83 lines not on this page · raw message
Signature · 1 line
2.25.2
PATCH 35/40 btrfs: qgroup: Introduce qgroup_backref_cache_build() function
In reply to Qu WenruoThis function is the main function to build the generic purposed backref cache for qgroup.
The major difference from relocation purposed backref cache is:
- No processed extent_io_tree
As we don't need to bother the relocation progress
- Don't care reloc root
Since reloc root doesn't contribute to qgroup accounting, reloc roots are queued to useless list
- Always populate backref_node::owner
This is the main index for qgroup backref cache to find out the owner of one tree block.
The @owner parameter is from tree block header owner, which doesn't reflect reloc tree. But backref cache mechanism will detect reloc tree and remove them from backref cache, thus the header owner is very accruate for qgroup usage.
This function will be utlized in incoming patches.
--- fs/btrfs/qgroup.c | 154 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 154 insertions(+)
fs/btrfs/qgroup.c +154 -0
@@ -22,6 +22,7 @@#include "extent_io.h" #include "qgroup.h" #include "block-group.h" +#include "misc.h" /* TODO XXX FIXME * - subvol delete -> delete when ref goes to 0? delete limits also?
@@ -1611,6 +1612,159 @@ int btrfs_qgroup_trace_extent_nolock(struct btrfs_fs_info *fs_info,return 0 ; } +static bool handle_useless_nodes (struct btrfs_backref_cache *cache, +struct btrfs_backref_node *node) +{ +struct list_head *useless_node = &cache->useless_node; +bool ret = false; + +while (!list_empty (useless_node)) { +struct btrfs_backref_node *cur; + + cur = list_first_entry(useless_node, struct btrfs_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 btrfs_backref_edge *edge; +struct btrfs_backref_node *lower; + + edge =list_entry (cur->lower.next, + struct btrfs_backref_edge, list[UPPER]); +list_del (&edge->list[UPPER ]); +list_del (&edge->list[LOWER ]); + lower = edge->node[LOWER ]; +btrfs_backref_free_edge (cache, edge); + +/* Child node is also orphan, queue for cleanup */ +if (list_empty (&lower->upper)) +list_add (&lower->list, useless_node); + } + +/* +* 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); +btrfs_backref_free_node (cache, cur); + } + } +return ret; +} + +/* +* Build backref cache for one tree block. +* +* @node_key: The first key of the tree block. +* @level: Tree level +* @bytenr: The bytenr of the tree block. +* @owner: The owner from btrfs_header. +* +* Caller must ensure the tree block belongs to a subvolume tree. +* +* Return the cached backref_node if the tree block is useful for owner +* iteration. +* +* Return NULL if the tree block doesn't make sense for owner iteration. +* (E.g. the tree block belongs to a reloc tree) +* +* Return ERR_PTR() if something wrong happened. +*/ +static struct btrfs_backref_node *qgroup_backref_cache_build ( +struct btrfs_fs_info *fs_info, +struct btrfs_key *node_key, +int level,u64 bytenr,u64 owner) +{ +struct btrfs_backref_iter *iter; +struct btrfs_backref_cache *cache = fs_info->qgroup_backref_cache; +struct btrfs_path *path; +struct btrfs_backref_node *cur; +struct btrfs_backref_node *node =NULL ; +struct btrfs_backref_edge *edge; +struct rb_node *rb_node; +int ret; + +ASSERT (is_fstree (owner)); + + rb_node =simple_search (&cache->rb_root, bytenr); +/* Already cached, return the cached node directly */ +if (rb_node) + return rb_entry(rb_node, struct btrfs_backref_node, rb_node); + + iter =btrfs_backref_iter_alloc (fs_info,GFP_NOFS ); +if (!iter) +return ERR_PTR (-ENOMEM ); + path =btrfs_alloc_path (); +if (!path) { + ret = -ENOMEM ; + goto out; + } + + node =btrfs_backref_alloc_node (cache, bytenr, level); +if (!node) { + ret = -ENOMEM ; + goto out; + } + node->owner = owner; + node->lowest =1 ; + cur = node; + +/* Breadth-first search to build backref cache */ +do { + ret =btrfs_backref_add_tree_node (cache, path, iter, node_key, + cur); +if (ret <0 ) + goto out; + edge =list_first_entry_or_null (&cache->pending_edge, + struct btrfs_backref_edge, list[UPPER]); +/* +* the pending list isn't empty, take the first block to +* process. +*/ +if (edge) { +list_del_init (&edge->list[UPPER ]); + cur = edge->node[UPPER ]; + } + }while (edge); + +/* Finish the upper linkage of newly added edges/nodes */ + ret =btrfs_backref_finish_upper_links (cache, node); +if (ret <0 ) + goto out; + +if (handle_useless_nodes (cache, node)) + node =NULL ; +out: +btrfs_backref_iter_free (iter); +btrfs_free_path (path); +if (ret <0 ) { +btrfs_backref_error_cleanup (cache, node); +return ERR_PTR (ret); + } +ASSERT (!node || !node->detached); +ASSERT (list_empty (&cache->useless_node) && +list_empty (&cache->pending_edge)); +return node; +} +int btrfs_qgroup_trace_extent_post (struct btrfs_fs_info *fs_info,struct btrfs_qgroup_extent_record *qrecord) {
Signature · 1 line
2.25.2
PATCH 36/40 btrfs: qgroup: Introduce a function to iterate through backref_cache to find all parents for specified node
In reply to Qu WenruoIntroduce a new static function, iterate_all_roots(), to find all roots for specified backref node.
This function will do iterative depth-first search, and queue hit root objectid to the result ulist.
--- fs/btrfs/qgroup.c | 40 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+)
fs/btrfs/qgroup.c +40 -0
@@ -1765,6 +1765,46 @@ static struct btrfs_backref_node *qgroup_backref_cache_build(return node; } +/* Iterate all roots in the backref_cache, and add root objectid into @roots */ +static int iterate_all_roots (struct btrfs_backref_node *node, +struct ulist *roots) +{ +struct btrfs_backref_edge *edge; +struct btrfs_backref_node *upper; +int ret =0 ; + +ASSERT (node->level <BTRFS_MAX_LEVEL ); + +/* Useless node, exit directly */ +if (node->detached || node->is_reloc_root || node->cowonly) + goto out; + +/* Find a root, queue to @roots ulist */ +if (list_empty (&node->upper)) { +ASSERT (is_fstree (node->owner)); + ret =ulist_add (roots, node->owner,0 ,GFP_NOFS ); + goto out; + } + +/* Go upper level */ +list_for_each_entry (edge, &node->upper, list[LOWER ]) { + upper = edge->node[UPPER ]; + +if (upper->level != node->level +1 || + upper->level >=BTRFS_MAX_LEVEL ) { + ret = -EUCLEAN ; + goto out; + } + ret =iterate_all_roots (upper, roots); +if (ret <0 ) + goto out; + } +out: +if (ret <0 ) +ulist_release (roots); +return ret; +} +int btrfs_qgroup_trace_extent_post (struct btrfs_fs_info *fs_info,struct btrfs_qgroup_extent_record *qrecord) {
Signature · 1 line
2.25.2
PATCH 37/40 btrfs: qgroup: Introduce helpers to get needed tree block info
In reply to Qu WenruoIntroduce two helpers, get_tree_key() and get_tree_info(), to grab needed tree block info (level, first key and owner) for qgroup backref cache.
--- fs/btrfs/qgroup.c | 66 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 66 insertions(+)
fs/btrfs/qgroup.c +66 -0
@@ -1765,6 +1765,72 @@ static struct btrfs_backref_node *qgroup_backref_cache_build(return node; } +static int get_tree_key (struct btrfs_fs_info *fs_info,u64 bytenr,int level, +struct btrfs_key *node_key,u64 *owner) +{ +struct extent_buffer *eb; + + eb =read_tree_block (fs_info, bytenr,0 , level,NULL ); +if (IS_ERR (eb)) +return PTR_ERR (eb); +if (btrfs_header_level (eb)) +btrfs_node_key_to_cpu (eb, node_key,0 ); +else +btrfs_item_key_to_cpu (eb, node_key,0 ); + *owner =btrfs_header_owner (eb); +free_extent_buffer (eb); +return 0 ; +} + +/* +* Helper to get tree level, first key and the first owner for +* qgroup_backref_cache_build(). +* +* Caller should have done one extent_from_logical() call to ensure the +* extent exists and it's a tree block. +*/ +static int get_tree_info (struct btrfs_fs_info *fs_info, +struct btrfs_path *path,u64 bytenr, +struct btrfs_key *node_key,u64 *owner,u8 *level) +{ +struct btrfs_extent_item *ei; +struct btrfs_key key; +unsigned long ptr =0 ; +u64 extent_flag; +u64 tmp; +u32 item_size; +int ret; + + path->search_commit_root =1 ; + path->skip_locking =1 ; + + ret =extent_from_logical (fs_info, bytenr, path, &key, &extent_flag); +if (ret <0 ) + goto out; +ASSERT (extent_flag &BTRFS_EXTENT_FLAG_TREE_BLOCK ); + + ei =btrfs_item_ptr (path->nodes[0 ], path->slots[0 ], + struct btrfs_extent_item); + item_size =btrfs_item_size_nr (path->nodes[0 ], path->slots[0 ]); + +/* +* Don't trust the owner get from tree_backref_for_extent(), as for +* SHARED_BLOCK type, the return owner is just the parent tree block. +*/ + ret =tree_backref_for_extent (&ptr, path->nodes[0 ], &key, + ei, item_size, &tmp, level); +if (ret <0 ) + goto out; + +/* Instead, get the owner from btrfs header */ + ret =get_tree_key (fs_info, bytenr, *level, node_key, owner); +if (ret <0 ) + goto out; +out: +btrfs_release_path (path); +return ret; +} +/* Iterate all roots in the backref_cache, and add root objectid into @roots */ static int iterate_all_roots (struct btrfs_backref_node *node,struct ulist *roots)
Signature · 1 line
2.25.2
PATCH 38/40 btrfs: qgroup: Introduce verification for function to ensure old roots ulist matches btrfs_find_all_roots() result
In reply to Qu WenruoThis patch will introduce a new function, verify_old_roots(), for qgroup to verify the backref cache based result and old btrfs_find_all_roots() result.
Since it will impact performance heavily as we are doing two different backref walk, this verification will only be enabled for CONFIG_BTRFS_FS_CHECK_INTEGRITY.
--- fs/btrfs/qgroup.c | 72 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 72 insertions(+)
fs/btrfs/qgroup.c +72 -0
@@ -1831,6 +1831,78 @@ static int get_tree_info(struct btrfs_fs_info *fs_info,return ret; } +#ifdef CONFIG_BTRFS_FS_CHECK_INTEGRITY +/* +* Compare the result with old btrfs_find_all_roots() to ensure the new backref +* cache based result is correct. +*/ +static int verify_old_roots (struct btrfs_fs_info *fs_info, +struct ulist *result,u64 bytenr) +{ +struct ulist *old; +struct ulist_iterator uiter; +struct ulist_node *unode; +bool not_fstree = false; +int ret =0 ; + + ret =btrfs_find_all_roots (NULL , fs_info, bytenr,0 , &old, true); +if (ret <0 ) +return ret; + +/* +* Check the first node, as find_all_roots() will also return +* non-subvolume tree owner. +* Since subvolume tree block won't be shared with non-subvolume +* trees, if we find a non-subolume tree root, we don't need +* to verify at all. +*/ +ULIST_ITER_INIT (&uiter); +while ((unode =ulist_next (old, &uiter))) { +if (!is_fstree (unode->val)) + not_fstree = true; +break ; + } + +if (not_fstree && result->nnodes !=0 ) { +btrfs_err (fs_info, +"qgroup backref cached error, bytenr=%llu found cached node for non-fs tree" , + bytenr); + ret = -EUCLEAN ; + goto out; + } +if (not_fstree) + goto out; + +if (result->nnodes != old->nnodes) { +btrfs_err (fs_info, +"qgroup backref cache error, bytenr=%llu nr nodes mismatch, old method=%lu cache method=%lu" , + bytenr, old->nnodes, result->nnodes); + ret = -EUCLEAN ; + goto out; + } +ULIST_ITER_INIT (&uiter); +while ((unode =ulist_next (result, &uiter))) { +/* +* @result and @old have the same amount of nodes, so if we +* delete each @result node from @old, we either delete all +* nodes from @old (verification pass), or we will hit +* a missing node (verification failure). +*/ + ret =ulist_del (old, unode->val,0 ); +if (ret) { +btrfs_err (fs_info, +"qgroup backref cache error, bytenr=%llu root %llu not found in cached result" , + bytenr, unode->val); + ret = -EUCLEAN ; + goto out; + } + } +out: +ulist_free (old); +return ret; +} +#endif +/* Iterate all roots in the backref_cache, and add root objectid into @roots */ static int iterate_all_roots (struct btrfs_backref_node *node,struct ulist *roots)
Signature · 1 line
2.25.2
PATCH 39/40 btrfs: qgroup: Introduce a new function to get old_roots ulist using backref cache
In reply to Qu WenruoThe new function, get_old_roots() will replace the old btrfs_find_all_roots() to do a backref cache based search for all referring roots.
The workflow includes:
- Search the extent tree to get basic tree info
Including: first key, level and owner (from btrfs_header).
- Skip all non-subvolume tree blocks
Since non-subvolume tree blocks will never be shared with subvolume trees, skipping them would speed up the procedure.
- Build backref cache for the tree block
Either we get the backref_node inserted into the cache, or it's referred exclusively by reloc tree which doesn't contribute to qgroup.
- Find all roots using the return backref_node
It's a simple iterative depth-first search. The result will be stored into a ulist, just like old btrfs_find_all_roots().
- Verify the cached result with old btrfs_find_all_roots() for DEBUG build
If we enabled CONFIG_BTRFS_FS_CHECK_INTEGRITY, we again call btrfs_find_all_roots() just as what we used to do.
Then verify the result against the result from backref cache.
This is very performance heavy as it kills all the benefit we get from backref cache, thus should only be enabled for DEBUG build.
--- fs/btrfs/qgroup.c | 109 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 109 insertions(+)
fs/btrfs/qgroup.c +109 -0
@@ -1943,6 +1943,115 @@ static int iterate_all_roots(struct btrfs_backref_node *node,return ret; } +static struct ulist *get_old_roots (struct btrfs_fs_info *fs_info,u64 bytenr) +{ +struct ulist *tree_blocks =NULL ; +struct btrfs_path *path =NULL ; +struct btrfs_key key; +struct ulist_iterator uiter; +struct ulist_node *unode; +struct ulist *ret_ulist; +u64 extent_flag; +int ret; + + ret_ulist =ulist_alloc (GFP_NOFS ); +if (!ret_ulist) +return ERR_PTR (-ENOMEM ); + + path =btrfs_alloc_path (); +if (!path) { + ret = -ENOMEM ; + goto out; + } + path->search_commit_root =1 ; + path->skip_locking =1 ; + + ret =extent_from_logical (fs_info, bytenr, path, &key, &extent_flag); +if (ret == -ENOENT ) { +/* No backref for this extent, returning empty old_root */ + ret =0 ; + goto out; + } +if (ret <0 ) + goto out; + +if (extent_flag &BTRFS_EXTENT_FLAG_TREE_BLOCK ) { + tree_blocks =ulist_alloc (GFP_NOFS ); +if (!tree_blocks) { + ret = -ENOMEM ; + goto out; + } + + ret =ulist_add (tree_blocks, bytenr,0 ,GFP_NOFS ); +if (ret <0 ) + goto out; + }else { + ret =btrfs_find_all_leafs (NULL , fs_info, bytenr,0 , + &tree_blocks,NULL , true); +if (ret <0 ) + goto out; + } +btrfs_release_path (path); + +/* +* Add all related tree blocks to backref cache and get all roots +* from each iteration +*/ +ULIST_ITER_INIT (&uiter); +while ((unode =ulist_next (tree_blocks, &uiter))) { +struct btrfs_backref_node *node; +struct btrfs_key node_key; +u64 owner; +u8 tree_level; + + ret =get_tree_info (fs_info, path, unode->val, + &node_key, &owner, &tree_level); +if (ret <0 ) + goto out; + +/* Isn't a subvolume tree, direct exist */ +if (!is_fstree (owner)) + goto out; + +mutex_lock (&fs_info->qgroup_backref_lock); +/* +* This can happen when rescan worker is running while qgroup +* is being disabled. +* Just exit without verification, qgroup will cleanup itself. +*/ +if (!fs_info->qgroup_backref_cache) { +mutex_unlock (&fs_info->qgroup_backref_lock); + goto out_no_verify; + } + + node =qgroup_backref_cache_build (fs_info, &node_key, + tree_level, unode->val, owner); +if (IS_ERR (node)) { + ret =PTR_ERR (node); +mutex_unlock (&fs_info->qgroup_backref_lock); + goto out; + } +if (node) + ret =iterate_all_roots (node, ret_ulist); +mutex_unlock (&fs_info->qgroup_backref_lock); +if (ret <0 ) + goto out; + } +out: +if (IS_ENABLED (CONFIG_BTRFS_FS_CHECK_INTEGRITY ) && !ret) { + ret =verify_old_roots (fs_info, ret_ulist, bytenr); +WARN_ON (ret <0 ); + } +out_no_verify: +btrfs_free_path (path); +ulist_free (tree_blocks); +if (ret <0 ) { +ulist_free (ret_ulist); +return ERR_PTR (ret); + } +return ret_ulist; +} +int btrfs_qgroup_trace_extent_post (struct btrfs_fs_info *fs_info,struct btrfs_qgroup_extent_record *qrecord) {
Signature · 1 line
2.25.2
PATCH 40/40 btrfs: qgroup: Use backref cache to speed up old_roots search
In reply to Qu WenruoNow use the backref cache backed backref walk mechanism.
This mechanism is trading memory usage for faster, and more qgroup specific backref walk.
Compared to original btrfs_find_all_roots(), it has the extra behavior difference:
- Skip non-subvolume tress from the very beginning
Since only subvolume trees contribute to qgroup numbers, skipping them would save us time.
- Skip reloc trees earlier
Reloc trees doesn't contribute to qgroup, and btrfs_find_all_roots() also doesn't account them, thus we don't need to account them. Here we use the detached nodes in backref cache to skip them faster and earlier.
- Cached results
Well, backref cache is obviously cached, right.
The major performance improvement happens for backref walk in commit tree, one of the most obvious user is qgroup rescan.
Here is a small script to test it:
mkfs.btrfs -f $dev
mount $dev -o space_cache=v2 $mnt
btrfs subvolume create $mnt/src
for ((i = 0; i < 64; i++)); do
for (( j = 0; j < 16; j++)); do
xfs_io -f -c "pwrite 0 2k" \
$mnt/src/file_inline_$(($i * 16 + $j)) > /dev/null
done
xfs_io -f -c "pwrite 0 1M" $mnt/src/file_reg_$i > /dev/null
sync
btrfs subvol snapshot $mnt/src $mnt/snapshot_$i done
sync
btrfs quota enable $mnt
btrfs quota rescan -w $mnt
Here is the benchmark for above small tests.
The performance material is the total execution time of get_old_roots() for patched kernel (*), and find_all_roots() for original kernel.
*: With CONFIG_BTRFS_FS_CHECK_INTEGRITY disabled, as get_old_roots()
will call find_all_roots() to verify the result if that config is enabled.
| Number of calls | Total exec time |
------------------------------------------------------
find_all_roots()| 732 | 529991034ns get_old_roots() | 732 | 127998312ns
------------------------------------------------------
diff | 0.00 % | -75.8 %
--- fs/btrfs/qgroup.c | 22 ++++++++++++---------- 1 file changed, 12 insertions(+), 10 deletions(-)
fs/btrfs/qgroup.c +12 -10
@@ -2059,8 +2059,9 @@ int btrfs_qgroup_trace_extent_post(struct btrfs_fs_info *fs_info,u64 bytenr = qrecord->bytenr;int ret; - ret =btrfs_find_all_roots (NULL , fs_info, bytenr,0 , &old_root, false); -if (ret <0 ) { + old_root =get_old_roots (fs_info, bytenr); +if (IS_ERR (old_root)) { + ret =PTR_ERR (old_root); fs_info->qgroup_flags |=BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT ; btrfs_warn(fs_info, "error accounting new delayed refs extent (err code: %d), quota inconsistent",
@@ -3006,12 +3007,12 @@ int btrfs_qgroup_account_extents(struct btrfs_trans_handle *trans)* extent record */ if (WARN_ON (!record->old_roots)) { -/* Search commit root to find old_roots */ - ret =btrfs_find_all_roots (NULL , fs_info, - record->bytenr,0 , - &record->old_roots, false); -if (ret <0 ) + record->old_roots =get_old_roots (fs_info, + record->bytenr); +if (IS_ERR (record->old_roots)) { + ret =PTR_ERR (record->old_roots); goto cleanup; + } }/* Free the reserved data space */
@@ -3590,10 +3591,11 @@ static int qgroup_rescan_leaf(struct btrfs_trans_handle *trans,else num_bytes = found.offset; - ret =btrfs_find_all_roots (NULL , fs_info, found.objectid,0 , - &roots, false); -if (ret <0 ) + roots =get_old_roots (fs_info, found.objectid); +if (IS_ERR (roots)) { + ret =PTR_ERR (roots); goto out; + }/* For rescan, just pass old_roots as NULL */ ret =btrfs_qgroup_account_extent (trans, found.objectid, num_bytes,NULL , roots);
Signature · 1 line
2.25.2
Re: [PATCH 01/40] btrfs: backref: Introduce the skeleton of btrfs_backref_iter
In reply to Qu WenruoQuoted 30 lines · Qu Wenruo
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_iteris 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);
Quoted 4 lines
This patch is just the skeleton +
btrfs_backref_iter_start()code.Signed-off-by Qu Wenruo <[email protected]>Reviewed-by Johannes Thumshirn <[email protected]>
Thanks,
Josef