btrfs: relocation: Refactor build_backref_tree()
v2 cover btrfs: relocation: Refactor build_backref_tree()
This branch can be fetched from github:
https://github.com/adam900710/linux/tree/backref_cache_refactor
The basis is:10f3586f65b0d0 (david/misc-next) btrfs: fix btrfs_calc_reclaim_metadata_size calculation
The main objective of this patchset is to refactor build_backref_tree() and get myself more familiar with the backref cache.
The refactor also add quite some comments explaining how the backref cache is built, but I'm also working on crafting a new dev doc for the backref cache.
As some more example would greatly help reader to go through the somewhat weird code.
Patch 1~8 haven already been sent to the mail list. This time they are included for a better review.
There are 3 main structures involved:
- backref_cache
The main cache structure, store all the existing cached map.
- backref_node
Represent one tree block.
It can have multiple parent and multiple children backref_edges related.
- backref_edge
Represent one parent-child relationship between two backref_node. Both parent (upper) and child (lower) backref_node can iterate through their list to locate the edge.
The objective build_backref_cache() is to build a map, starting from specified node, to reach all its parents. E.g:
build_backref_tree() is called on bytenr X, then the following map is added to backref_cache:
Root 257 Root 258
A B
| /
| /
|/
C
|
X We will have backref_nodes for X, A, B, C in the backref_cache, and 3 edges between (X, C), (C, A), (C, B).
The short workflow of build_backref_tree() is:
- Iterate through all parent nodes of the specified node (ITERATION)
Here we go breadth first search. We go through direct parent of current node. The iteration is bottom-up.
For how each backref item is handled, check handle_one_tree_backref() for details.
When a direct parent is found, we check if the direct parent is cached:
* Cached:
Allocate the edge between this node and parent. Call it a day, and process next parent.
* Not cached:
Allocate both edges and nodes. And queue the parent node for iteration.
During this stage, new nodes are only allocated, not yet added to cache, and new edges are only linked to lower nodes.
After this step, we have reached all roots referring to the specified node.
Some root nodes may be useless (reloc tree root), they will be queued for later cleanup.
- Finish the linkage between newly added nodes and edges. (WEAVING)
Since previous step only allocated new nodes, and only linked edges with its lower node, we still need to add the nodes to cache, and finish the linkage.
See finish_upper_links() for details.
- Cleanup the useless trees
(CLEANUP)
For reloc trees, we only cache the backref nodes for higher tree nodes. And don't keep any edges. So such backref nodes are marked detached.
Tree leaves for reloc trees are not cached.
Such behavior is to reduce memory usage for useless trees, but still allow backref cache hit, to avoid unnecessary cache search.
And also mark the useless nodes as processed for relocation.
With the refactor, only the CLEANUP part of build_backref_tree() is really coupled with relocation.
And now build_backref_tree() is only 125 lines, it's a pretty good start point for us to reuse backref_cache for other workload, like qgroups.
Changelog:
v2:
- Rebased to misc-next branch
There are some small conflicts due to Josef's root ref count patches. To make sure everything is fine, the main code move part is re-written from scratch to ensure no btrfs_put_fs_root() is missing
- Better handling mark_block_processed()
Now uses in_range() macro, and remove the set_extent_bit() wrapper which only get called in one location.
Qu Wenruo (10):
btrfs: backref: Introduce the skeleton of btrfs_backref_iter
btrfs: backref: Implement btrfs_backref_iter_next()
btrfs: relocation: Use btrfs_backref_iter infrastructure
btrfs: relocation: Rename mark_block_processed() and
__mark_block_processed()
btrfs: relocation: Refactor tree backref processing into its own
function
btrfs: relocation: Use wrapper to replace open-coded edge linking
btrfs: relocation: Specify essential members for alloc_backref_node()
btrfs: relocation: Remove the open-coded goto loop for breadth-first
search
btrfs: relocation: Refactor the finishing part of upper linkage into
finish_upper_links()
btrfs: relocation: Refactor the useless nodes handling into its own
function
fs/btrfs/backref.c | 145 +++++++ fs/btrfs/backref.h | 94 ++++ fs/btrfs/relocation.c | 968 ++++++++++++++++++++++-------------------- 3 files changed, 749 insertions(+), 458 deletions(-)
Signature · 1 line
2.25.1
PATCH v2 1/10 btrfs: backref: Introduce the skeleton of btrfs_backref_iter
Due to the complex nature of btrfs extent tree, when we want to iterate all backrefs of one extent, it involves quite a lot of work, like searching the EXTENT_ITEM/METADATA_ITEM, iteration through inline and keyed backrefs.
Normally this would result pretty complex code, something like:
btrfs_search_slot()
/* Ensure we are at EXTENT_ITEM/METADATA_ITEM */
while (1) { /* Loop for extent tree items */
while (ptr < end) { /* Loop for inlined items */
/* REAL WORK HERE */
}
next:
ret = btrfs_next_item()
/* Ensure we're still at keyed item for specified bytenr */}
The idea of btrfs_backref_iter is to avoid such complex and hard to read code structure, but something like the following:
iter = btrfs_backref_iter_alloc();
ret = btrfs_backref_iter_start(iter, bytenr);
if (ret < 0)
goto out;
for (; ; ret = btrfs_backref_iter_next(iter)) {
/* REAL WORK HERE */ }
out:
btrfs_backref_iter_free(iter);
This patch is just the skeleton + btrfs_backref_iter_start() code.
--- fs/btrfs/backref.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++ fs/btrfs/backref.h | 60 ++++++++++++++++++++++++++++++++ 2 files changed, 147 insertions(+)
fs/btrfs/backref.c +87 -0
@@ -2299,3 +2299,90 @@ void free_ipath(struct inode_fs_paths *ipath)kvfree (ipath->fspath);kfree (ipath); } + +int btrfs_backref_iter_start (struct btrfs_backref_iter *iter,u64 bytenr) +{ +struct btrfs_fs_info *fs_info = iter->fs_info; +struct btrfs_path *path = iter->path; +struct btrfs_extent_item *ei; +struct btrfs_key key; +int ret; + + key.objectid = bytenr; + key.type =BTRFS_METADATA_ITEM_KEY ; + key.offset = (u64)-1 ; + iter->bytenr = bytenr; + + ret =btrfs_search_slot (NULL , fs_info->extent_root, &key, path,0 ,0 ); +if (ret <0 ) +return ret; +if (ret ==0 ) { + ret = -EUCLEAN ; + goto release; + } +if (path->slots[0 ] ==0 ) { +WARN_ON (IS_ENABLED (CONFIG_BTRFS_DEBUG )); + ret = -EUCLEAN ; + goto release; + } + path->slots[0 ]--; + +btrfs_item_key_to_cpu (path->nodes[0 ], &key, path->slots[0 ]); +if (!(key.type ==BTRFS_EXTENT_ITEM_KEY || + key.type ==BTRFS_METADATA_ITEM_KEY ) || key.objectid != bytenr) { + ret = -ENOENT ; + goto release; + } +memcpy (&iter->cur_key, &key,sizeof (key)); + iter->item_ptr =btrfs_item_ptr_offset (path->nodes[0 ], + path->slots[0 ]); + iter->end_ptr = iter->item_ptr +btrfs_item_size_nr (path->nodes[0 ], + path->slots[0 ]); + ei =btrfs_item_ptr (path->nodes[0 ], path->slots[0 ], + struct btrfs_extent_item); + +/* +* Only support iteration on tree backref yet. +* +* This is extra precaustion for non skinny-metadata, where +* EXTENT_ITEM is also used for tree blocks, that we can only use +* extent flags to determine if it's a tree block. +*/ +if (btrfs_extent_flags (path->nodes[0 ], ei) &BTRFS_EXTENT_FLAG_DATA ) { + ret = -ENOTTY ; + goto release; + } + iter->cur_ptr = iter->item_ptr +sizeof (*ei); + +/* If there is no inline backref, go search for keyed backref */ +if (iter->cur_ptr >= iter->end_ptr) { + ret =btrfs_next_item (fs_info->extent_root, path); + +/* No inline nor keyed ref */ +if (ret >0 ) { + ret = -ENOENT ; + goto release; + } +if (ret <0 ) + goto release; + +btrfs_item_key_to_cpu (path->nodes[0 ], &iter->cur_key, + path->slots[0 ]); +if (iter->cur_key.objectid != bytenr || + (iter->cur_key.type !=BTRFS_SHARED_BLOCK_REF_KEY && + iter->cur_key.type !=BTRFS_TREE_BLOCK_REF_KEY )) { + ret = -ENOENT ; + goto release; + } + iter->cur_ptr =btrfs_item_ptr_offset (path->nodes[0 ], + path->slots[0 ]); + iter->item_ptr = iter->cur_ptr; + iter->end_ptr = iter->item_ptr +btrfs_item_size_nr ( + path->nodes[0 ], path->slots[0 ]); + } + +return 0 ; +release: +btrfs_backref_iter_release (iter); +return ret; +}
fs/btrfs/backref.h +60 -0
64 lines not on this page · raw message
Signature · 1 line
2.25.1
Re: [PATCH v2 01/10] btrfs: backref: Introduce the skeleton of btrfs_backref_iter
Quoted 88 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);This patch is just the skeleton +
btrfs_backref_iter_start()code.Signed-off-by Qu Wenruo <[email protected]>Reviewed-by Johannes Thumshirn <[email protected]>--- fs/btrfs/backref.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++ fs/btrfs/backref.h | 60 ++++++++++++++++++++++++++++++++ 2 files changed, 147 insertions(+)fs/btrfs/backref.c +41
-0@@ -2299,3 +2299,90 @@ void free_ipath(struct inode_fs_paths *ipath)kvfree (ipath->fspath);kfree (ipath); } + +int btrfs_backref_iter_start (struct btrfs_backref_iter *iter,u64 bytenr) +{ +struct btrfs_fs_info *fs_info = iter->fs_info; +struct btrfs_path *path = iter->path; +struct btrfs_extent_item *ei; +struct btrfs_key key; +int ret; + + key.objectid = bytenr; + key.type =BTRFS_METADATA_ITEM_KEY ; + key.offset = (u64)-1 ; + iter->bytenr = bytenr; + + ret =btrfs_search_slot (NULL , fs_info->extent_root, &key, path,0 ,0 ); +if (ret <0 ) +return ret; +if (ret ==0 ) { + ret = -EUCLEAN ; + goto release; + } +if (path->slots[0 ] ==0 ) { +WARN_ON (IS_ENABLED (CONFIG_BTRFS_DEBUG )); + ret = -EUCLEAN ; + goto release; + } + path->slots[0 ]--; + +btrfs_item_key_to_cpu (path->nodes[0 ], &key, path->slots[0 ]); +if (!(key.type ==BTRFS_EXTENT_ITEM_KEY || + key.type ==BTRFS_METADATA_ITEM_KEY ) || key.objectid != bytenr) { + ret = -ENOENT ; + goto release; + } +memcpy (&iter->cur_key, &key,sizeof (key)); + iter->item_ptr =btrfs_item_ptr_offset (path->nodes[0 ], + path->slots[0 ]); + iter->end_ptr = iter->item_ptr +btrfs_item_size_nr (path->nodes[0 ], + path->slots[0 ]); + ei =btrfs_item_ptr (path->nodes[0 ], path->slots[0 ], + struct btrfs_extent_item);
fs/btrfs/backref.c void free_ipath(struct inode_fs_paths *ipath) · line 2352
Quoted 10 lines
fs/btrfs/backref.c +10
-0+ +/* +* Only support iteration on tree backref yet. +* +* This is extra precaustion for non skinny-metadata, where +* EXTENT_ITEM is also used for tree blocks, that we can only use +* extent flags to determine if it's a tree block. +*/ +if (btrfs_extent_flags (path->nodes[0 ], ei) &BTRFS_EXTENT_FLAG_DATA ) { + ret = -ENOTTY ;
What's the reason for ENOTTY?
Quoted 51 lines
fs/btrfs/backref.c +36
-0+ goto release; + } + iter->cur_ptr = iter->item_ptr +sizeof (*ei); + +/* If there is no inline backref, go search for keyed backref */ +if (iter->cur_ptr >= iter->end_ptr) { + ret =btrfs_next_item (fs_info->extent_root, path); + +/* No inline nor keyed ref */ +if (ret >0 ) { + ret = -ENOENT ; + goto release; + } +if (ret <0 ) + goto release; + +btrfs_item_key_to_cpu (path->nodes[0 ], &iter->cur_key, + path->slots[0 ]); +if (iter->cur_key.objectid != bytenr || + (iter->cur_key.type !=BTRFS_SHARED_BLOCK_REF_KEY && + iter->cur_key.type !=BTRFS_TREE_BLOCK_REF_KEY )) { + ret = -ENOENT ; + goto release; + } + iter->cur_ptr =btrfs_item_ptr_offset (path->nodes[0 ], + path->slots[0 ]); + iter->item_ptr = iter->cur_ptr; + iter->end_ptr = iter->item_ptr +btrfs_item_size_nr ( + path->nodes[0 ], path->slots[0 ]); + } + +return 0 ; +release: +btrfs_backref_iter_release (iter); +return ret; +}fs/btrfs/backref.h +7
-0@@ -74,4 +74,64 @@ 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;
fs/btrfs/backref.h struct prelim_ref { · line 93
Quoted 10 lines
fs/btrfs/backref.h +10
-0+struct btrfs_path *path; +struct btrfs_fs_info *fs_info; +struct btrfs_key cur_key; +unsigned long item_ptr; +unsigned long cur_ptr; +unsigned long end_ptr; +}; + +static inline struct btrfs_backref_iter * +btrfs_backref_iter_alloc (struct btrfs_fs_info *fs_info,gfp_t gfp_flag)
This does not need to be static inline, and please keep the type and function name on the same line.
Quoted 21 lines
fs/btrfs/backref.h +21
-0+{ +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->path->reada =READA_FORWARD ; + ret->fs_info = fs_info; + +return ret; +}
Re: [PATCH v2 01/10] btrfs: backref: Introduce the skeleton of btrfs_backref_iter
Quoted 93 lines · David Sterba
Quoted 92 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);This patch is just the skeleton +
btrfs_backref_iter_start()code.Signed-off-by Qu Wenruo <[email protected]>Reviewed-by Johannes Thumshirn <[email protected]>--- fs/btrfs/backref.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++ fs/btrfs/backref.h | 60 ++++++++++++++++++++++++++++++++ 2 files changed, 147 insertions(+)fs/btrfs/backref.c +45
-0@@ -2299,3 +2299,90 @@ void free_ipath(struct inode_fs_paths *ipath)kvfree (ipath->fspath);kfree (ipath); } + +int btrfs_backref_iter_start (struct btrfs_backref_iter *iter,u64 bytenr) +{ +struct btrfs_fs_info *fs_info = iter->fs_info; +struct btrfs_path *path = iter->path; +struct btrfs_extent_item *ei; +struct btrfs_key key; +int ret; + + key.objectid = bytenr; + key.type =BTRFS_METADATA_ITEM_KEY ; + key.offset = (u64)-1 ; + iter->bytenr = bytenr; + + ret =btrfs_search_slot (NULL , fs_info->extent_root, &key, path,0 ,0 ); +if (ret <0 ) +return ret; +if (ret ==0 ) { + ret = -EUCLEAN ; + goto release; + } +if (path->slots[0 ] ==0 ) { +WARN_ON (IS_ENABLED (CONFIG_BTRFS_DEBUG )); + ret = -EUCLEAN ; + goto release; + } + path->slots[0 ]--; + +btrfs_item_key_to_cpu (path->nodes[0 ], &key, path->slots[0 ]); +if (!(key.type ==BTRFS_EXTENT_ITEM_KEY || + key.type ==BTRFS_METADATA_ITEM_KEY ) || key.objectid != bytenr) { + ret = -ENOENT ; + goto release; + } +memcpy (&iter->cur_key, &key,sizeof (key)); + iter->item_ptr =btrfs_item_ptr_offset (path->nodes[0 ], + path->slots[0 ]); + iter->end_ptr = iter->item_ptr +btrfs_item_size_nr (path->nodes[0 ], + path->slots[0 ]); + ei =btrfs_item_ptr (path->nodes[0 ], path->slots[0 ], + struct btrfs_extent_item); + +/* +* Only support iteration on tree backref yet. +*
Quoted 8 lines
fs/btrfs/backref.c void free_ipath(struct inode_fs_paths *ipath) · line 2352
Quoted 6 lines
fs/btrfs/backref.c +6
-0+* This is extra precaustion for non skinny-metadata, where +* EXTENT_ITEM is also used for tree blocks, that we can only use +* extent flags to determine if it's a tree block. +*/ +if (btrfs_extent_flags (path->nodes[0 ], ei) &BTRFS_EXTENT_FLAG_DATA ) { + ret = -ENOTTY ;What's the reason for ENOTTY?
Because it's not supported yet.
Quoted 57 lines
Quoted 57 lines
fs/btrfs/backref.c +36
-0+ goto release; + } + iter->cur_ptr = iter->item_ptr +sizeof (*ei); + +/* If there is no inline backref, go search for keyed backref */ +if (iter->cur_ptr >= iter->end_ptr) { + ret =btrfs_next_item (fs_info->extent_root, path); + +/* No inline nor keyed ref */ +if (ret >0 ) { + ret = -ENOENT ; + goto release; + } +if (ret <0 ) + goto release; + +btrfs_item_key_to_cpu (path->nodes[0 ], &iter->cur_key, + path->slots[0 ]); +if (iter->cur_key.objectid != bytenr || + (iter->cur_key.type !=BTRFS_SHARED_BLOCK_REF_KEY && + iter->cur_key.type !=BTRFS_TREE_BLOCK_REF_KEY )) { + ret = -ENOENT ; + goto release; + } + iter->cur_ptr =btrfs_item_ptr_offset (path->nodes[0 ], + path->slots[0 ]); + iter->item_ptr = iter->cur_ptr; + iter->end_ptr = iter->item_ptr +btrfs_item_size_nr ( + path->nodes[0 ], path->slots[0 ]); + } + +return 0 ; +release: +btrfs_backref_iter_release (iter); +return ret; +}fs/btrfs/backref.h +12
-0@@ -74,4 +74,64 @@ 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; +unsigned long item_ptr; +unsigned long cur_ptr;
Quoted 8 lines
fs/btrfs/backref.h struct prelim_ref { · line 93
Quoted 5 lines
fs/btrfs/backref.h +5
-0+unsigned long end_ptr; +}; + +static inline struct btrfs_backref_iter * +btrfs_backref_iter_alloc (struct btrfs_fs_info *fs_info,gfp_t gfp_flag)This does not need to be static inline, and please keep the type and function name on the same line.
OK, that makes sense.
Thanks,
Qu
Quoted 22 lines
Quoted 22 lines
fs/btrfs/backref.h +21
-0+{ +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->path->reada =READA_FORWARD ; + ret->fs_info = fs_info; + +return ret; +}
Re: [PATCH v2 01/10] btrfs: backref: Introduce the skeleton of btrfs_backref_iter
In reply to Qu Wenruofs/btrfs/backref.h struct prelim_ref { · line 89
Quoted 9 lines · Qu Wenruo
fs/btrfs/backref.h +8
-0+struct btrfs_backref_iter { +u64 bytenr; +struct btrfs_path *path; +struct btrfs_fs_info *fs_info; +struct btrfs_key cur_key; +unsigned long item_ptr; +unsigned long cur_ptr; +unsigned long end_ptr;
I think these can be u32, only processing the leaf data, this would save some stack space consumed by the iterators.
Re: [PATCH v2 01/10] btrfs: backref: Introduce the skeleton of btrfs_backref_iter
Quoted 7 lines · David Sterba
Quoted 5 lines · Qu Wenruo
fs/btrfs/backref.h +5
-0+struct btrfs_backref_iter { +u64 bytenr; +struct btrfs_path *path; +struct btrfs_fs_info *fs_info; +struct btrfs_key cur_key;
Quoted 7 lines
fs/btrfs/backref.h struct prelim_ref { · line 89
Quoted 3 lines
fs/btrfs/backref.h +3
-0+unsigned long item_ptr; +unsigned long cur_ptr; +unsigned long end_ptr;I think these can be u32, only processing the leaf data, this would save some stack space consumed by the iterators.
The only reason is we need to do force type convert, as it needs to be converted to pointer.
But since it's all used inside backref iter functions, it shouldn't cause much trouble for callers.
So I'll update it to u32 in next version.
Thanks,
Qu
Re: [PATCH v2 01/10] btrfs: backref: Introduce the skeleton of btrfs_backref_iter
In reply to Qu WenruoQuoted 71 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);This patch is just the skeleton +
btrfs_backref_iter_start()code.Signed-off-by Qu Wenruo <[email protected]>Reviewed-by Johannes Thumshirn <[email protected]>--- fs/btrfs/backref.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++ fs/btrfs/backref.h | 60 ++++++++++++++++++++++++++++++++ 2 files changed, 147 insertions(+)fs/btrfs/backref.c +24
-0@@ -2299,3 +2299,90 @@ void free_ipath(struct inode_fs_paths *ipath)kvfree (ipath->fspath);kfree (ipath); } + +int btrfs_backref_iter_start (struct btrfs_backref_iter *iter,u64 bytenr) +{ +struct btrfs_fs_info *fs_info = iter->fs_info; +struct btrfs_path *path = iter->path; +struct btrfs_extent_item *ei; +struct btrfs_key key; +int ret; + + key.objectid = bytenr; + key.type =BTRFS_METADATA_ITEM_KEY ; + key.offset = (u64)-1 ; + iter->bytenr = bytenr; + + ret =btrfs_search_slot (NULL , fs_info->extent_root, &key, path,0 ,0 ); +if (ret <0 ) +return ret; +if (ret ==0 ) { + ret = -EUCLEAN ; + goto release; + } +if (path->slots[0 ] ==0 ) { +WARN_ON (IS_ENABLED (CONFIG_BTRFS_DEBUG )); + ret = -EUCLEAN ;
fs/btrfs/backref.c void free_ipath(struct inode_fs_paths *ipath) · line 2335
Quoted 10 lines
fs/btrfs/backref.c +10
-0+ 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; + }
nit: Please keep the logic of the checks identical as it makes comprehending the code easier. What I mean is here you do !(type == COND1 || type == COND2) which really translates to type != COND && type != COND2. However, when checking for keyed items you use the second style. Yes, they are both identical in terms of semantics but one might wonder "why is this done in 2 different ways for no apparent reason" ?
Quoted 7 lines
fs/btrfs/backref.c +7
-0+memcpy (&iter->cur_key, &key,sizeof (key)); + iter->item_ptr =btrfs_item_ptr_offset (path->nodes[0 ], + path->slots[0 ]); + iter->end_ptr = iter->item_ptr +btrfs_item_size_nr (path->nodes[0 ], + path->slots[0 ]); + ei =btrfs_item_ptr (path->nodes[0 ], path->slots[0 ], + struct btrfs_extent_item);
fs/btrfs/backref.c void free_ipath(struct inode_fs_paths *ipath) · line 2352
Quoted 10 lines
fs/btrfs/backref.c +10
-0+ +/* +* Only support iteration on tree backref yet. +* +* This is extra precaustion for non skinny-metadata, where +* EXTENT_ITEM is also used for tree blocks, that we can only use +* extent flags to determine if it's a tree block. +*/ +if (btrfs_extent_flags (path->nodes[0 ], ei) &BTRFS_EXTENT_FLAG_DATA ) { + ret = -ENOTTY ;
why not simply -ENOSUPP
Quoted 2 lines
fs/btrfs/backref.c +2
-0+ goto release; + }
<snip>
PATCH v2 2/10 btrfs: backref: Implement btrfs_backref_iter_next()
In reply to Qu WenruoThis function will go next inline/keyed backref for btrfs_backref_iter infrastructure.
--- fs/btrfs/backref.c | 58 ++++++++++++++++++++++++++++++++++++++++++++++ fs/btrfs/backref.h | 34 +++++++++++++++++++++++++++ 2 files changed, 92 insertions(+)
fs/btrfs/backref.c +58 -0
@@ -2386,3 +2386,61 @@ int btrfs_backref_iter_start(struct btrfs_backref_iter *iter, u64 bytenr)btrfs_backref_iter_release (iter);return ret; } + +/* +* Go to next backref item of current bytenr, can be either inlined or keyed. +* +* Caller need to check whether it's inline ref or not by iter->cur_key. +* +* Return 0 if we get next backref without problem. +* Return >0 if there is no extra backref for this bytenr. +* Return <0 if there is something wrong happened. +*/ +int btrfs_backref_iter_next (struct btrfs_backref_iter *iter) +{ +struct extent_buffer *eb =btrfs_backref_get_eb (iter); +struct btrfs_path *path = iter->path; +struct btrfs_extent_inline_ref *iref; +int ret; +u32 size; + +if (btrfs_backref_iter_is_inline_ref (iter)) { +/* We're still inside the inline refs */ +ASSERT (iter->cur_ptr < iter->end_ptr); + +if (btrfs_backref_has_tree_block_info (iter)) { +/* First tree block info */ + size =sizeof (struct btrfs_tree_block_info ); + }else { +/* Use inline ref type to determine the size */ +int type; + + iref = (struct btrfs_extent_inline_ref *) + (iter->cur_ptr); + type =btrfs_extent_inline_ref_type (eb, iref); + + size =btrfs_extent_inline_ref_size (type); + } + iter->cur_ptr += size; +if (iter->cur_ptr < iter->end_ptr) +return 0 ; + +/* All inline items iterated, fall through */ + } +/* We're at keyed items, there is no inline item, just go next item */ + ret =btrfs_next_item (iter->fs_info->extent_root, iter->path); +if (ret) +return ret; + +btrfs_item_key_to_cpu (path->nodes[0 ], &iter->cur_key, path->slots[0 ]); +if (iter->cur_key.objectid != iter->bytenr || + (iter->cur_key.type !=BTRFS_TREE_BLOCK_REF_KEY && + iter->cur_key.type !=BTRFS_SHARED_BLOCK_REF_KEY )) +return 1 ; + iter->item_ptr =btrfs_item_ptr_offset (path->nodes[0 ], + path->slots[0 ]); + iter->cur_ptr = iter->item_ptr; + iter->end_ptr = iter->item_ptr +btrfs_item_size_nr (path->nodes[0 ], + path->slots[0 ]); +return 0 ; +}
fs/btrfs/backref.h +34 -0
@@ -121,8 +121,42 @@ static inline void btrfs_backref_iter_free(struct btrfs_backref_iter *iter)kfree (iter); } +static inline struct extent_buffer * +btrfs_backref_get_eb (struct btrfs_backref_iter *iter) +{ +if (!iter) +return NULL ; +return iter->path->nodes[0 ]; +} + +/* +* For metadata with EXTENT_ITEM key (non-skinny) case, the first inline data +* is btrfs_tree_block_info, without a btrfs_extent_inline_ref header. +* +* This helper is here to determine if that's the case. +*/ +static inline bool btrfs_backref_has_tree_block_info ( +struct btrfs_backref_iter *iter) +{ +if (iter->cur_key.type ==BTRFS_EXTENT_ITEM_KEY && + iter->cur_ptr - iter->item_ptr ==sizeof (struct btrfs_extent_item )) +return true; +return false; +} +int btrfs_backref_iter_start (struct btrfs_backref_iter *iter,u64 bytenr); +int btrfs_backref_iter_next (struct btrfs_backref_iter *iter); + +static inline bool +btrfs_backref_iter_is_inline_ref (struct btrfs_backref_iter *iter) +{ +if (iter->cur_key.type ==BTRFS_EXTENT_ITEM_KEY || + iter->cur_key.type ==BTRFS_METADATA_ITEM_KEY ) +return true; +return false; +} +static inline void btrfs_backref_iter_release (struct btrfs_backref_iter *iter) {
Signature · 1 line
2.25.1
PATCH v2 3/10 btrfs: relocation: Use btrfs_backref_iter infrastructure
In reply to Qu WenruoIn the core function of relocation, build_backref_tree, it needs to iterate all backref items of one tree block.
We don't really want to spend our code and reviewers' time to going through tons of supportive code just for the backref walk.
Use btrfs_backref_iter infrastructure to do the loop.
The backref items look would be much more easier to read:
ret = btrfs_backref_iter_start(iter, cur->bytenr);
for (; ret == 0; ret = btrfs_backref_iter_next(iter)) {
/* The really important work */
}--- fs/btrfs/relocation.c | 193 ++++++++++++++---------------------------- 1 file changed, 62 insertions(+), 131 deletions(-)
fs/btrfs/relocation.c +62 -131
@@ -22,6 +22,7 @@#include "print-tree.h" #include "delalloc-space.h" #include "block-group.h" +#include "backref.h" /* * 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,20 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, exist =NULL ; } -while (1 ) { -cond_resched (); - eb = path1->nodes[0 ]; - -if (ptr >= end) { -if (path1->slots[0 ] >=btrfs_header_nritems (eb)) { - ret =btrfs_next_leaf (rc->extent_root, path1); -if (ret <0 ) { - err = ret; - goto out; - } -if (ret >0 ) -break ; - eb = path1->nodes[0 ]; - } +for (; ret ==0 ; ret =btrfs_backref_iter_next (iter)) { +struct extent_buffer *eb; +struct btrfs_key key; +int type; -btrfs_item_key_to_cpu (eb, &key, path1->slots[0 ]); -if (key.objectid != cur->bytenr) { -WARN_ON (exist); -break ; - } +cond_resched (); + eb =btrfs_backref_get_eb (iter); -if (key.type ==BTRFS_EXTENT_ITEM_KEY || - key.type ==BTRFS_METADATA_ITEM_KEY ) { - ret =find_inline_backref (eb, path1->slots[0 ], - &ptr, &end); -if (ret) - goto next; - } - } + key.objectid = iter->bytenr; +if (btrfs_backref_iter_is_inline_ref (iter)) { +struct btrfs_extent_inline_ref *iref; -if (ptr < end) {/* update key for inline back ref */ -struct btrfs_extent_inline_ref *iref; -int type; - iref = (struct btrfs_extent_inline_ref *)ptr; + iref = (struct btrfs_extent_inline_ref *)iter->cur_ptr; type =btrfs_get_extent_inline_ref_type (eb, iref,BTRFS_REF_TYPE_BLOCK );if (type ==BTRFS_REF_TYPE_INVALID ) {
@@ -839,9 +776,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 +791,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 +837,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 +845,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 +878,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 +909,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 +928,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 +988,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 +1113,8 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, } } out: -btrfs_free_path (path1); -btrfs_free_path (path2); +btrfs_backref_iter_free (iter); +btrfs_free_path (path);if (err) {while (!list_empty (&useless)) { lower = list_entry(useless.next,
Signature · 1 line
2.25.1
PATCH v2 4/10 btrfs: relocation: Rename mark_block_processed() and __mark_block_processed()
In reply to Qu WenruoThese two functions are weirdly named, mark_block_processed() in fact just mark a range dirty unconditionally, while __mark_block_processed() does extra check before doing the marking.
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 | 55 +++++++++++++++++-------------------------- 1 file changed, 21 insertions(+), 34 deletions(-)
fs/btrfs/relocation.c +21 -34
@@ -236,8 +236,21 @@ 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) {
@@ -1103,7 +1116,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 ;
@@ -1569,14 +1582,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 */
@@ -1674,7 +1679,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 ;/*
@@ -2604,7 +2610,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 ; }
@@ -2954,25 +2960,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.
@@ -2991,7 +2978,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 ;
@@ -4743,7 +4730,7 @@ int btrfs_reloc_cow_block(struct btrfs_trans_handle *trans, }if (first_cow) -__mark_block_processed (rc, node); +mark_block_processed (rc, node);if (first_cow && level >0 ) rc->nodes_relocated += buf->len;
Signature · 1 line
2.25.1
Re: [PATCH v2 04/10] btrfs: relocation: Rename mark_block_processed() and __mark_block_processed()
Quoted 11 lines · Qu Wenruo
These two functions are weirdly named,
mark_block_processed()in fact just mark a range dirty unconditionally, while__mark_block_processed()does extra check before doing the marking.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()within_range()macro.Signed-off-by Qu Wenruo <[email protected]>
PATCH v2 5/10 btrfs: relocation: Refactor tree backref processing into its own function
In reply to Qu Wenruobuild_backref_tree() function is painfully long, as it has 3 big parts:
- Tree backref handling
- Weaving backref nodes
- Useless nodes pruning
This patch will move the tree backref handling into its own function, handle_one_tree_backref().
And inside that function, the main works are determined by the backref key:
- BTRFS_SHARED_BLOCK_REF_KEY
We know the parent node bytenr directly.
If the parent is cached, or it's root, call it a day.
If the parent is not cached, add it pending list.
- BTRFS_TREE_BLOCK_REF_KEY
The most complex work.
We need to grab the fs root, do a tree search to locate all its parent nodes, weaving all needed edges, and put all uncached edges to pending edge list.
--- fs/btrfs/relocation.c | 395 +++++++++++++++++++++--------------------- 1 file changed, 202 insertions(+), 193 deletions(-)
fs/btrfs/relocation.c +202 -193
@@ -666,6 +666,206 @@ static struct btrfs_root *read_fs_root(struct btrfs_fs_info *fs_info,return btrfs_get_fs_root (fs_info, &key, false); } +static int handle_one_tree_backref (struct reloc_control *rc, +struct list_head *useless_node, +struct list_head *pending_edge, +struct btrfs_path *path, +struct btrfs_key *ref_key, +struct btrfs_key *tree_key, +struct backref_node *cur) +{ +struct btrfs_fs_info *fs_info = rc->extent_root->fs_info; +struct backref_cache *cache = &rc->backref_cache; +struct backref_node *upper; +struct backref_node *lower; +struct backref_edge *edge; +struct extent_buffer *eb; +struct btrfs_root *root; +struct rb_node *rb_node; +bool need_check = true; +int level; +int ret =0 ; + +if (ref_key->type !=BTRFS_TREE_BLOCK_REF_KEY && + ref_key->type !=BTRFS_SHARED_BLOCK_REF_KEY ) +return -EUCLEAN ; + +/* SHARED_BLOCK_REF means key.offset is the parent bytenr */ +if (ref_key->type ==BTRFS_SHARED_BLOCK_REF_KEY ) { + +/* Only reloc root uses backref pointing to itself */ +if (ref_key->objectid == ref_key->offset) { + root =find_reloc_root (rc, cur->bytenr); +if (WARN_ON (!root)) +return -ENOENT ; + cur->root = root; +return 0 ; + } + + edge =alloc_backref_edge (cache); +if (!edge) +return -ENOMEM ; + + rb_node =tree_search (&cache->rb_root, ref_key->offset); +if (!rb_node) { +/* Parent node not yet cached */ + upper =alloc_backref_node (cache); +if (!upper) { +free_backref_edge (cache, edge); +return -ENOMEM ; + } + upper->bytenr = ref_key->offset; + upper->level = cur->level +1 ; + +/* +* backrefs for the upper level block isn't +* cached, add the block to pending list +*/ +list_add_tail (&edge->list[UPPER ], pending_edge); + }else { +/* Parent node already cached */ + upper = rb_entry(rb_node, struct backref_node, + rb_node); +ASSERT (upper->checked); +INIT_LIST_HEAD (&edge->list[UPPER ]); + } +list_add_tail (&edge->list[LOWER ], &cur->upper); + edge->node[LOWER ] = cur; + edge->node[UPPER ] = upper; +return 0 ; + } +/* +* ref_key.type == BTRFS_TREE_BLOCK_REF_KEY, ref_key->offset means the +* root objectid. We need to search the tree to get its parent bytenr. +*/ + root =read_fs_root (fs_info, ref_key->offset); +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, 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, 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 ], 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
@@ -688,7 +888,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;
@@ -701,7 +900,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)
@@ -807,201 +1005,12 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,continue ; } -/* SHARED_BLOCK_REF means key.offset is the parent bytenr */ -if (key.type ==BTRFS_SHARED_BLOCK_REF_KEY ) { -if (key.objectid == key.offset) { -/* -* Only root blocks of reloc trees use backref -* pointing to itself. -*/ - root =find_reloc_root (rc, cur->bytenr); -ASSERT (root); - cur->root = root; -break ; - } - - edge =alloc_backref_edge (cache); -if (!edge) { - err = -ENOMEM ; - goto out; - } - rb_node =tree_search (&cache->rb_root, key.offset); -if (!rb_node) { - upper =alloc_backref_node (cache); -if (!upper) { -free_backref_edge (cache, edge); - err = -ENOMEM ; - goto out; - } - upper->bytenr = key.offset; - upper->level = cur->level +1 ; -/* -* backrefs for the upper level block isn't -* cached, add the block to pending list -*/ -list_add_tail (&edge->list[UPPER ], &list); - }else { - upper = rb_entry(rb_node, struct backref_node, - rb_node); -ASSERT (upper->checked); -INIT_LIST_HEAD (&edge->list[UPPER ]); - } -list_add_tail (&edge->list[LOWER ], &cur->upper); - edge->node[LOWER ] = cur; - edge->node[UPPER ] = upper; - -continue ; - }else if (unlikely (key.type ==BTRFS_EXTENT_REF_V0_KEY )) { - err = -EINVAL ; -btrfs_print_v0_err (rc->extent_root->fs_info); -btrfs_handle_fs_error (rc->extent_root->fs_info, err, -NULL ); - goto out; - }else if (key.type !=BTRFS_TREE_BLOCK_REF_KEY ) { -continue ; - } - -/* -* key.type == BTRFS_TREE_BLOCK_REF_KEY, inline ref offset -* means the root objectid. We need to search the tree to get -* its parent bytenr. -*/ - root =read_fs_root (rc->extent_root->fs_info, key.offset); -if (IS_ERR (root)) { - err =PTR_ERR (root); - goto out; - } - -if (!test_bit (BTRFS_ROOT_REF_COWS , &root->state)) - cur->cowonly =1 ; - -if (btrfs_root_level (&root->root_item) == cur->level) { -/* tree root */ -ASSERT (btrfs_root_bytenr (&root->root_item) == - cur->bytenr); -if (should_ignore_root (root)) { -btrfs_put_root (root); -list_add (&cur->list, &useless); - }else { - cur->root = root; - } -break ; - } - - level = cur->level +1 ; - -/* Search the tree to find parent blocks referring the block. */ - path->search_commit_root =1 ; - path->skip_locking =1 ; - path->lowest_level = level; - ret =btrfs_search_slot (NULL , root, node_key, path,0 ,0 ); - path->lowest_level =0 ; + ret =handle_one_tree_backref (rc, &useless, &list, path, &key, + node_key, cur);if (ret <0 ) { -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, &useless); - }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 ], - &list); - }else { -if (upper->checked) - need_check = true; -INIT_LIST_HEAD (&edge->list[UPPER ]); - } - }else { - upper = rb_entry(rb_node, struct backref_node, - rb_node); -ASSERT (upper->checked); -INIT_LIST_HEAD (&edge->list[UPPER ]); -if (!upper->owner) - upper->owner =btrfs_header_owner (eb); - } -list_add_tail (&edge->list[LOWER ], &lower->upper); - edge->node[LOWER ] = lower; - edge->node[UPPER ] = upper; - -if (rb_node) { -btrfs_put_root (root); -break ; - } - lower = upper; - upper =NULL ; - } -btrfs_release_path (path); }if (ret <0 ) { err = ret;
Signature · 1 line
2.25.1
Re: [PATCH v2 05/10] btrfs: relocation: Refactor tree backref processing into its own function
Quoted 4 lines · Qu Wenruo
build_backref_tree()function is painfully long, as it has 3 big parts:
- Tree backref handling
- Weaving backref nodes
- Useless nodes pruning
So this is the first patch that mentions the 'useless' nodes. This seems like a misnomer or confusing at best but I haven't read enough code to see if it's really the right name.
Also the term 'weaving', that seems to be added by you. Did you mean splicing or merging?
Re: [PATCH v2 05/10] btrfs: relocation: Refactor tree backref processing into its own function
Quoted 9 lines · David Sterba
Quoted 4 lines · Qu Wenruo
build_backref_tree()function is painfully long, as it has 3 big parts:
- Tree backref handling
- Weaving backref nodes
- Useless nodes pruningSo this is the first patch that mentions the 'useless' nodes. This seems like a misnomer or confusing at best but I haven't read enough code to see if it's really the right name.
The 'useless' is from the original code, there is a list called 'useless'.
It's not that useless, those nodes are just ignored, but still cached to prevent extra lookup.
Hopes there would be a better name.
Quoted 4 lines
Also the term 'weaving', that seems to be added by you. Did you mean splicing or merging?
It's complex, but definitely not splicing or merge.
The overall workflow looks like this:
1) Iteration works build a map like this: (start point is X)
A B
^ ^
\ /
C
^
|
X At this stage, it's single directional, means we can only go X->C, C->A, C->B
2) Weaving part makes the map bi-directional
A B
^ ^
\ /
v v
C
^
|
v
X That's the weaving part.
Any better naming is welcomed.
Thanks,
Qu
Re: [PATCH v2 05/10] btrfs: relocation: Refactor tree backref processing into its own function
In reply to Qu WenruoQuoted 31 lines · Qu Wenruo
build_backref_tree()function is painfully long, as it has 3 big parts:
- Tree backref handling
- Weaving backref nodes
- Useless nodes pruningThis patch will move the tree backref handling into its own function,
handle_one_tree_backref().And inside that function, the main works are determined by the backref key:
-BTRFS_SHARED_BLOCK_REF_KEY
We know the parent node bytenr directly.
If the parent is cached, or it's root, call it a day.
If the parent is not cached, add it pending list.-
BTRFS_TREE_BLOCK_REF_KEY
The most complex work.
We need to grab the fs root, do a tree search to locate all its parent nodes, weaving all needed edges, and put all uncached edges to pending edge list.Signed-off-by Qu Wenruo <[email protected]>--- fs/btrfs/relocation.c | 395 +++++++++++++++++++++--------------------- 1 file changed, 202 insertions(+), 193 deletions(-)fs/btrfs/relocation.c +0
-0
fs/btrfs/relocation.c static struct btrfs_root *read_fs_root(struct btrfs_fs_info *fs_info, · line 675
Quoted 10 lines
fs/btrfs/relocation.c +7
-0@@ -666,6 +666,206 @@ static struct btrfs_root *read_fs_root(struct btrfs_fs_info *fs_info,return btrfs_get_fs_root (fs_info, &key, false); } +static int handle_one_tree_backref (struct reloc_control *rc, +struct list_head *useless_node, +struct list_head *pending_edge, +struct btrfs_path *path, +struct btrfs_key *ref_key, +struct btrfs_key *tree_key, +struct backref_node *cur)
That function has 7 parameters and while @rc and @path are somewhat self-explanatory others are not. Also it's really doing 2 distinct things which, in my opinion, would be much better split across 2 functions - 1 handling BTRFS_SHARED_BLOCK_REF_KEY and the other handling BTRFS_TREE_BLOCK_REF_KEY. For example the @tree_key,@useless_node and @path are not used in BTRFS_SHARED_BLOCK_REF_KEY case. You'd have two functions named:
handle_(in)?direct_tree_backref
One will take only 4 parameters the other will have to, unfortunately, take all 7.
Re: [PATCH v2 05/10] btrfs: relocation: Refactor tree backref processing into its own function
Quoted 37 lines · Nikolay Borisov
Quoted 34 lines · Qu Wenruo
build_backref_tree()function is painfully long, as it has 3 big parts:
- Tree backref handling
- Weaving backref nodes
- Useless nodes pruningThis patch will move the tree backref handling into its own function,
handle_one_tree_backref().And inside that function, the main works are determined by the backref key:
-BTRFS_SHARED_BLOCK_REF_KEY
We know the parent node bytenr directly.
If the parent is cached, or it's root, call it a day.
If the parent is not cached, add it pending list.-
BTRFS_TREE_BLOCK_REF_KEY
The most complex work.
We need to grab the fs root, do a tree search to locate all its parent nodes, weaving all needed edges, and put all uncached edges to pending edge list.Signed-off-by Qu Wenruo <[email protected]>--- fs/btrfs/relocation.c | 395 +++++++++++++++++++++--------------------- 1 file changed, 202 insertions(+), 193 deletions(-)fs/btrfs/relocation.c +0
-0@@ -666,6 +666,206 @@ static struct btrfs_root *read_fs_root(struct btrfs_fs_info *fs_info,return btrfs_get_fs_root (fs_info, &key, false); }
Quoted 10 lines
fs/btrfs/relocation.c static struct btrfs_root *read_fs_root(struct btrfs_fs_info *fs_info, · line 675
Quoted 7 lines
fs/btrfs/relocation.c +7
-0+static int handle_one_tree_backref (struct reloc_control *rc, +struct list_head *useless_node, +struct list_head *pending_edge, +struct btrfs_path *path, +struct btrfs_key *ref_key, +struct btrfs_key *tree_key, +struct backref_node *cur)That function has 7 parameters and while @rc and @path are somewhat self-explanatory others are not.
That's exactly what I'm fixing in the 2nd patchset.
To kill 2 parameters by moving @useless_node and @pending_edge into backref_cache.
Since you're complaining about this, it looks like I'd better put that patch earlier.
Quoted 7 lines
Also it's really doing 2 distinct
things which, in my opinion, would be much better split across 2 functions - 1 handlingBTRFS_SHARED_BLOCK_REF_KEYand the other handlingBTRFS_TREE_BLOCK_REF_KEY. For example the @tree_key,@useless_node and @path are not used inBTRFS_SHARED_BLOCK_REF_KEYcase. You'd have two functions named:
Quoted 5 lines
handle_(in)?direct_tree_backref
One will take only 4 parameters the other will have to, unfortunately, take all 7.
That looks reasonable.
I'll split them into two functions, and move the two lists into backref_cache in next version.
Thanks,
Qu
PATCH v2 6/10 btrfs: relocation: Use wrapper to replace open-coded edge linking
In reply to Qu WenruoSince backref_edge is used to connect upper and lower backref nodes, and need to access both nodes, some code can look pretty nasty:
list_add_tail(&edge->list[LOWER], &cur->upper);
The above code will link @cur to the LOWER side of the edge, while both "LOWER" and "upper" words show up.
This can sometimes be very confusing for reader to grasp.
This patch introduce a new wrapper, link_backref_edge(), to handle the linking behavior.
Which also has extra ASSERT() to ensure caller won't pass wrong nodes in.
Also, this updates the comment of related lists of backref_node and backref_edge, to make it more clear that each list points to what.
--- fs/btrfs/relocation.c | 53 ++++++++++++++++++++++++++++++------------- 1 file changed, 37 insertions(+), 16 deletions(-)
fs/btrfs/relocation.c +37 -16
@@ -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 */
@@ -123,17 +125,26 @@ struct backref_node { unsigned int detached:1; }; +#define LOWER 0 +#define UPPER 1 +#define RELOCATION_RESERVED_NODES 256/* -* present a block pointer in the backref cache +* present an edge connecting upper and lower backref nodes. */ struct backref_edge { +/* +* list[LOWER] is linked to backref_node::upper of lower level node, +* and list[UPPER] is linked to backref_node::lower of upper level node. +* +* Also, build_backref_tree() uses list[UPPER] for pending edges, before +* linking list[UPPER] to its upper level nodes. +*/ struct list_head list[2 ]; + +/* Two related nodes */ struct backref_node *node[2 ]; }; -#define LOWER 0 -#define UPPER 1 -#define RELOCATION_RESERVED_NODES 256struct backref_cache {/* red black tree of all backref nodes in the cache */
@@ -332,6 +343,22 @@ static struct backref_edge *alloc_backref_edge(struct backref_cache *cache)return edge; } +#define LINK_LOWER (1 << 0) +#define LINK_UPPER (1 << 1) +static inline void link_backref_edge (struct backref_edge *edge, +struct backref_node *lower, +struct backref_node *upper, +int link_which) +{ +ASSERT (upper && lower && upper->level == lower->level +1 ); + edge->node[LOWER ] = lower; + edge->node[UPPER ] = upper; +if (link_which &LINK_LOWER ) +list_add_tail (&edge->list[LOWER ], &lower->upper); +if (link_which &LINK_UPPER ) +list_add_tail (&edge->list[UPPER ], &upper->lower); +} +static void free_backref_edge (struct backref_cache *cache,struct backref_edge *edge) {
@@ -729,9 +756,7 @@ static int handle_one_tree_backref(struct reloc_control *rc,ASSERT (upper->checked);INIT_LIST_HEAD (&edge->list[UPPER ]); } -list_add_tail (&edge->list[LOWER ], &cur->upper); - edge->node[LOWER ] = cur; - edge->node[UPPER ] = upper; +link_backref_edge (edge, cur, upper,LINK_LOWER );return 0 ; }/*
@@ -850,9 +875,7 @@ static int handle_one_tree_backref(struct reloc_control *rc,if (!upper->owner) upper->owner =btrfs_header_owner (eb); } -list_add_tail (&edge->list[LOWER ], &lower->upper); - edge->node[LOWER ] = lower; - edge->node[UPPER ] = upper; +link_backref_edge (edge, lower, upper,LINK_LOWER );if (rb_node) {btrfs_put_root (root);
@@ -1246,10 +1269,8 @@ static int clone_backref_node(struct btrfs_trans_handle *trans,if (!new_edge) goto fail; - new_edge->node[UPPER ] = new_node; - new_edge->node[LOWER ] = edge->node[LOWER ]; -list_add_tail (&new_edge->list[UPPER ], - &new_node->lower); +link_backref_edge (new_edge, edge->node[LOWER ], new_node, +LINK_UPPER ); } }else {list_add_tail (&new_node->lower, &cache->leaves);
Signature · 1 line
2.25.1
Re: [PATCH v2 06/10] btrfs: relocation: Use wrapper to replace open-coded edge linking
Quoted 73 lines · Qu Wenruo
Since
backref_edgeis used to connect upper and lower backref nodes, and need to access both nodes, some code can look pretty nasty:list_add_tail(&edge->list[LOWER], &cur->upper);The above code will link @cur to the LOWER side of the edge, while both "LOWER" and "upper" words show up.
This can sometimes be very confusing for reader to grasp.This patch introduce a new wrapper,
link_backref_edge(), to handle the linking behavior.
Which also has extraASSERT()to ensure caller won't pass wrong nodes in.Also, this updates the comment of related lists of
backref_nodeandbackref_edge, to make it more clear that each list points to what.Signed-off-by Qu Wenruo <[email protected]>--- fs/btrfs/relocation.c | 53 ++++++++++++++++++++++++++++++------------- 1 file changed, 37 insertions(+), 16 deletions(-)fs/btrfs/relocation.c +17
-6@@ -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 */ @@ -123,17 +125,26 @@ struct backref_node { unsigned int detached:1; }; +#define LOWER 0 +#define UPPER 1 +#define RELOCATION_RESERVED_NODES 256/* -* present a block pointer in the backref cache +* present an edge connecting upper and lower backref nodes. */ struct backref_edge { +/* +* list[LOWER] is linked to backref_node::upper of lower level node, +* and list[UPPER] is linked to backref_node::lower of upper level node. +* +* Also, build_backref_tree() uses list[UPPER] for pending edges, before +* linking list[UPPER] to its upper level nodes. +*/ struct list_head list[2 ]; + +/* Two related nodes */ struct backref_node *node[2 ]; }; -#define LOWER 0 -#define UPPER 1 -#define RELOCATION_RESERVED_NODES 256struct backref_cache {/* red black tree of all backref nodes in the cache */
fs/btrfs/relocation.c static struct backref_edge *alloc_backref_edge(struct backref_cache *cache) · line 351
Quoted 9 lines
fs/btrfs/relocation.c +6
-0@@ -332,6 +343,22 @@ static struct backref_edge *alloc_backref_edge(struct backref_cache *cache)return edge; } +#define LINK_LOWER (1 << 0) +#define LINK_UPPER (1 << 1) +static inline void link_backref_edge (struct backref_edge *edge, +struct backref_node *lower, +struct backref_node *upper, +int link_which)
Again not a static inline, but plain static function.
Quoted 9 lines
fs/btrfs/relocation.c +9
-0+{ +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); +}
Re: [PATCH v2 06/10] btrfs: relocation: Use wrapper to replace open-coded edge linking
Quoted 77 lines · David Sterba
Quoted 76 lines · Qu Wenruo
Since
backref_edgeis used to connect upper and lower backref nodes, and need to access both nodes, some code can look pretty nasty:list_add_tail(&edge->list[LOWER], &cur->upper);The above code will link @cur to the LOWER side of the edge, while both "LOWER" and "upper" words show up.
This can sometimes be very confusing for reader to grasp.This patch introduce a new wrapper,
link_backref_edge(), to handle the linking behavior.
Which also has extraASSERT()to ensure caller won't pass wrong nodes in.Also, this updates the comment of related lists of
backref_nodeandbackref_edge, to make it more clear that each list points to what.Signed-off-by Qu Wenruo <[email protected]>--- fs/btrfs/relocation.c | 53 ++++++++++++++++++++++++++++++------------- 1 file changed, 37 insertions(+), 16 deletions(-)fs/btrfs/relocation.c +17
-6@@ -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 */ @@ -123,17 +125,26 @@ struct backref_node { unsigned int detached:1; }; +#define LOWER 0 +#define UPPER 1 +#define RELOCATION_RESERVED_NODES 256/* -* present a block pointer in the backref cache +* present an edge connecting upper and lower backref nodes. */ struct backref_edge { +/* +* list[LOWER] is linked to backref_node::upper of lower level node, +* and list[UPPER] is linked to backref_node::lower of upper level node. +* +* Also, build_backref_tree() uses list[UPPER] for pending edges, before +* linking list[UPPER] to its upper level nodes. +*/ struct list_head list[2 ]; + +/* Two related nodes */ struct backref_node *node[2 ]; }; -#define LOWER 0 -#define UPPER 1 -#define RELOCATION_RESERVED_NODES 256struct backref_cache {/* red black tree of all backref nodes in the cache */ @@ -332,6 +343,22 @@ static struct backref_edge *alloc_backref_edge(struct backref_cache *cache)return edge; }
Quoted 8 lines
fs/btrfs/relocation.c static struct backref_edge *alloc_backref_edge(struct backref_cache *cache) · line 351
Quoted 6 lines
fs/btrfs/relocation.c +6
-0+#define LINK_LOWER (1 << 0) +#define LINK_UPPER (1 << 1) +static inline void link_backref_edge (struct backref_edge *edge, +struct backref_node *lower, +struct backref_node *upper, +int link_which)Again not a static inline, but plain static function.
Oh, I mixed my further plan with my current code...
It would be moved to backref.h, which have to be static inline.
Will remove the inline prefix in next version.
Thanks,
Qu
Quoted 10 lines
Quoted 10 lines
fs/btrfs/relocation.c +9
-0+{ +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); +}
Re: [PATCH v2 06/10] btrfs: relocation: Use wrapper to replace open-coded edge linking
In reply to Qu WenruoQuoted 14 lines · Qu Wenruo
Since
backref_edgeis used to connect upper and lower backref nodes, and need to access both nodes, some code can look pretty nasty:list_add_tail(&edge->list[LOWER], &cur->upper);The above code will link @cur to the LOWER side of the edge, while both "LOWER" and "upper" words show up.
This can sometimes be very confusing for reader to grasp.This patch introduce a new wrapper,
link_backref_edge(), to handle the linking behavior.
Which also has extraASSERT()to ensure caller won't pass wrong nodes in.
Quoted 4 lines
Also, this updates the comment of related lists of
backref_nodeandbackref_edge, to make it more clear that each list points to what.Signed-off-by Qu Wenruo <[email protected]>
Apart from David's comment I don't have anything else to add and also the code is functionally the same so:
PATCH v2 7/10 btrfs: relocation: Specify essential members for alloc_backref_node()
In reply to Qu WenruoBytenr and level are essential parameters for backref_node, thus it makes sense to initial them at alloc time.
--- fs/btrfs/relocation.c | 25 ++++++++++++------------- 1 file changed, 12 insertions(+), 13 deletions(-)
fs/btrfs/relocation.c +12 -13
@@ -308,10 +308,12 @@ static void backref_cache_cleanup(struct backref_cache *cache)ASSERT (!cache->nr_edges); } -static struct backref_node *alloc_backref_node (struct backref_cache *cache) +static struct backref_node *alloc_backref_node (struct backref_cache *cache, +u64 bytenr,int level) {struct backref_node *node; +ASSERT (level >=0 && level <BTRFS_MAX_LEVEL ); node =kzalloc (sizeof (*node),GFP_NOFS );if (node) {INIT_LIST_HEAD (&node->list);
@@ -319,6 +321,9 @@ static struct backref_node *alloc_backref_node(struct backref_cache *cache)INIT_LIST_HEAD (&node->lower);RB_CLEAR_NODE (&node->rb_node); cache->nr_nodes++; + + node->level = level; + node->bytenr = bytenr; }return node; }
@@ -736,13 +741,12 @@ static int handle_one_tree_backref(struct reloc_control *rc, rb_node =tree_search (&cache->rb_root, ref_key->offset);if (!rb_node) {/* Parent node not yet cached */ - upper =alloc_backref_node (cache); + upper =alloc_backref_node (cache, ref_key->offset, + cur->level +1 );if (!upper) {free_backref_edge (cache, edge);return -ENOMEM ; } - upper->bytenr = ref_key->offset; - upper->level = cur->level +1 ;/* * backrefs for the upper level block isn't
@@ -833,16 +837,15 @@ static int handle_one_tree_backref(struct reloc_control *rc, eb = path->nodes[level]; rb_node =tree_search (&cache->rb_root, eb->start);if (!rb_node) { - upper =alloc_backref_node (cache); + upper =alloc_backref_node (cache, eb->start, + lower->level +1 );if (!upper) {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 ;
@@ -934,14 +937,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:
@@ -1252,12 +1253,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.1
Re: [PATCH v2 07/10] btrfs: relocation: Specify essential members for alloc_backref_node()
Quoted 4 lines · Qu Wenruo
Bytenr and level are essential parameters for
backref_node, thus it makes sense to initial them at alloc time.Signed-off-by Qu Wenruo <[email protected]>
Quoted 23 lines
--- fs/btrfs/relocation.c | 25 ++++++++++++------------- 1 file changed, 12 insertions(+), 13 deletions(-)fs/btrfs/relocation.c +3
-1@@ -308,10 +308,12 @@ static void backref_cache_cleanup(struct backref_cache *cache)ASSERT (!cache->nr_edges); } -static struct backref_node *alloc_backref_node (struct backref_cache *cache) +static struct backref_node *alloc_backref_node (struct backref_cache *cache, +u64 bytenr,int level) {struct backref_node *node; +ASSERT (level >=0 && level <BTRFS_MAX_LEVEL ); node =kzalloc (sizeof (*node),GFP_NOFS );if (node) {INIT_LIST_HEAD (&node->list);
fs/btrfs/relocation.c static struct backref_node *alloc_backref_node(struct backref_cache *cache) · line 327
Quoted 7 lines
fs/btrfs/relocation.c +3
-0@@ -319,6 +321,9 @@ static struct backref_node *alloc_backref_node(struct backref_cache *cache)INIT_LIST_HEAD (&node->lower);RB_CLEAR_NODE (&node->rb_node); cache->nr_nodes++; + + node->level = level; + node->bytenr = bytenr; }
nit: One suggestion for this function, feel free to ignore:
What if you do it:
if (!node)
return NULL
and then have the initialization happen with just 1 level of nesting inside the function and not 2. That function is short and easy to understand but it might be a good time to refactor like that. If you think it's redundant then don't bother.
Quoted 2 lines
fs/btrfs/relocation.c +0
-0return node; }
<snip>
Re: [PATCH v2 07/10] btrfs: relocation: Specify essential members for alloc_backref_node()
Quoted 43 lines · Nikolay Borisov
Quoted 4 lines · Qu Wenruo
Bytenr and level are essential parameters for
backref_node, thus it makes sense to initial them at alloc time.Signed-off-by Qu Wenruo <[email protected]>Reviewed-by Nikolay Borisov <[email protected]>Quoted 23 lines
--- fs/btrfs/relocation.c | 25 ++++++++++++------------- 1 file changed, 12 insertions(+), 13 deletions(-)fs/btrfs/relocation.c +3
-1@@ -308,10 +308,12 @@ static void backref_cache_cleanup(struct backref_cache *cache)ASSERT (!cache->nr_edges); } -static struct backref_node *alloc_backref_node (struct backref_cache *cache) +static struct backref_node *alloc_backref_node (struct backref_cache *cache, +u64 bytenr,int level) {struct backref_node *node; +ASSERT (level >=0 && level <BTRFS_MAX_LEVEL ); node =kzalloc (sizeof (*node),GFP_NOFS );if (node) {INIT_LIST_HEAD (&node->list);fs/btrfs/relocation.c static struct backref_node *alloc_backref_node(struct backref_cache *cache) · line 327
Quoted 7 lines
fs/btrfs/relocation.c +3
-0@@ -319,6 +321,9 @@ static struct backref_node *alloc_backref_node(struct backref_cache *cache)INIT_LIST_HEAD (&node->lower);RB_CLEAR_NODE (&node->rb_node); cache->nr_nodes++; + + node->level = level; + node->bytenr = bytenr; }nit: One suggestion for this function, feel free to ignore:
Quoted 3 lines
What if you do it:
if (!node)
return NULL
I didn't notice we can do that.
Looks like the style I prefer too.
I'll use that style in next version.
Thanks,
Qu
Quoted 11 lines
and then have the initialization happen with just 1 level of nesting inside the function and not 2. That function is short and easy to understand but it might be a good time to refactor like that. If you think it's redundant then don't bother.
Quoted 2 lines
fs/btrfs/relocation.c +0
-0return node; }<snip>
PATCH v2 8/10 btrfs: relocation: Remove the open-coded goto loop for breadth-first search
In reply to Qu Wenruobuild_backref_tree() uses "goto again;" to implement a breadth-first search to build backref cache.
This patch will extract most of its work into a wrapper, handle_one_tree_block(), and use a while() loop to implement the same thing.
--- fs/btrfs/relocation.c | 167 +++++++++++++++++++++++------------------- 1 file changed, 91 insertions(+), 76 deletions(-)
fs/btrfs/relocation.c +91 -76
@@ -892,65 +892,21 @@ static int handle_one_tree_backref(struct reloc_control *rc,return ret; } -/* -* build backref tree for a given tree block. root of the backref tree -* corresponds the tree block, leaves of the backref tree correspond -* roots of b-trees that reference the tree block. -* -* the basic idea of this function is check backrefs of a given block -* to find upper level blocks that reference the block, and then check -* backrefs of these upper level blocks recursively. the recursion stop -* when tree root is reached or backrefs for the block is cached. -* -* NOTE: if we find backrefs for a block are cached, we know backrefs -* for all upper level blocks that directly/indirectly reference the -* block are also cached. -*/ -static noinline_for_stack -struct backref_node *build_backref_tree(struct reloc_control *rc, -struct btrfs_key *node_key, -int level,u64 bytenr) +static int handle_one_tree_block (struct reloc_control *rc, +struct list_head *useless_node, +struct list_head *pending_edge, +struct btrfs_path *path, +struct btrfs_backref_iter *iter, +struct btrfs_key *node_key, +struct backref_node *cur) { -struct btrfs_backref_iter *iter; -struct backref_cache *cache = &rc->backref_cache; -struct btrfs_path *path;/* For searching parent of TREE_BLOCK_REF */ -struct backref_node *cur; -struct backref_node *upper; -struct backref_node *lower; -struct backref_node *node =NULL ; -struct backref_node *exist =NULL ;struct backref_edge *edge; -struct rb_node *rb_node; -LIST_HEAD (list);/* Pending edge list, upper node needs to be checked */ -LIST_HEAD (useless); -int cowonly; +struct backref_node *exist;int ret; -int err =0 ; - - iter =btrfs_backref_iter_alloc (rc->extent_root->fs_info,GFP_NOFS ); -if (!iter) -return ERR_PTR (-ENOMEM ); - path =btrfs_alloc_path (); -if (!path) { - err = -ENOMEM ; - goto out; - } - path->reada =READA_FORWARD ; - - node =alloc_backref_node (cache, bytenr, level); -if (!node) { - err = -ENOMEM ; - goto out; - } - node->lowest =1 ; - cur = node; -again: ret =btrfs_backref_iter_start (iter, cur->bytenr); -if (ret <0 ) { - err = ret; - goto out; - } +if (ret <0 ) +return ret;/* * We skip the first btrfs_tree_block_info, as we don't use the key
@@ -958,13 +914,11 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,*/ if (btrfs_backref_has_tree_block_info (iter)) { ret =btrfs_backref_iter_next (iter); -if (ret <0 ) { - err = ret; +if (ret <0 ) goto out; - }/* No extra backref? This means the tree block is corrupted */ if (ret >0 ) { - err = -EUCLEAN ; + ret = -EUCLEAN ; goto out; } }
@@ -984,7 +938,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,* check its backrefs */ if (!exist->checked) -list_add_tail (&edge->list[UPPER ], &list); +list_add_tail (&edge->list[UPPER ], pending_edge); }else { exist =NULL ; }
@@ -1006,7 +960,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;
@@ -1029,29 +983,90 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,continue ; } - ret =handle_one_tree_backref (rc, &useless, &list, path, &key, - node_key, cur); -if (ret <0 ) { - err = ret; + ret =handle_one_tree_backref (rc, useless_node, pending_edge, path, + &key, node_key, cur); +if (ret <0 ) goto out; - } } -if (ret <0 ) { - err = ret; +if (ret <0 ) goto out; - } ret =0 ; -btrfs_backref_iter_release (iter); - cur->checked =1 ;WARN_ON (exist); +out: +btrfs_backref_iter_release (iter); +return ret; +} -/* the pending list isn't empty, take the first block to process */ -if (!list_empty (&list)) { - edge = list_entry(list.next, struct backref_edge, list[UPPER]); -list_del_init (&edge->list[UPPER ]); - cur = edge->node[UPPER ]; - goto again; +/* +* build backref tree for a given tree block. root of the backref tree +* corresponds the tree block, leaves of the backref tree correspond +* roots of b-trees that reference the tree block. +* +* the basic idea of this function is check backrefs of a given block +* to find upper level blocks that reference the block, and then check +* backrefs of these upper level blocks recursively. the recursion stop +* when tree root is reached or backrefs for the block is cached. +* +* NOTE: if we find backrefs for a block are cached, we know backrefs +* for all upper level blocks that directly/indirectly reference the +* block are also cached. +*/ +static noinline_for_stack +struct backref_node *build_backref_tree(struct reloc_control *rc, +struct btrfs_key *node_key, +int level,u64 bytenr) +{ +struct btrfs_backref_iter *iter; +struct backref_cache *cache = &rc->backref_cache; +struct btrfs_path *path;/* For searching parent of TREE_BLOCK_REF */ +struct backref_node *cur; +struct backref_node *upper; +struct backref_node *lower; +struct backref_node *node =NULL ; +struct backref_edge *edge; +struct rb_node *rb_node; +LIST_HEAD (list);/* Pending edge list, upper node needs to be checked */ +LIST_HEAD (useless); +int cowonly; +int ret; +int err =0 ; + + iter =btrfs_backref_iter_alloc (rc->extent_root->fs_info,GFP_NOFS ); +if (!iter) +return ERR_PTR (-ENOMEM ); + path =btrfs_alloc_path (); +if (!path) { + err = -ENOMEM ; + goto out; + } + path->reada =READA_FORWARD ; + + node =alloc_backref_node (cache, bytenr, level); +if (!node) { + err = -ENOMEM ; + goto out; + } + + node->lowest =1 ; + cur = node; + +/* Breadth-first search to build backref cache */ +while (1 ) { + ret =handle_one_tree_block (rc, &useless, &list, path, iter, + node_key, cur); +if (ret <0 ) { + err = ret; + goto out; + } +/* the pending list isn't empty, take the first block to process */ +if (!list_empty (&list)) { + edge = list_entry(list.next, struct backref_edge, list[UPPER]); +list_del_init (&edge->list[UPPER ]); + cur = edge->node[UPPER ]; + }else { +break ; + } }/*
Signature · 1 line
2.25.1
Re: [PATCH v2 08/10] btrfs: relocation: Remove the open-coded goto loop for breadth-first search
Quoted 188 lines · Qu Wenruo
build_backref_tree()uses "goto again;" to implement a breadth-first search to build backref cache.This patch will extract most of its work into a wrapper,
handle_one_tree_block(), and use awhile()loop to implement the same thing.Signed-off-by Qu Wenruo <[email protected]>--- fs/btrfs/relocation.c | 167 +++++++++++++++++++++++------------------- 1 file changed, 91 insertions(+), 76 deletions(-)fs/btrfs/relocation.c +49
-76@@ -892,65 +892,21 @@ static int handle_one_tree_backref(struct reloc_control *rc,return ret; } -/* -* build backref tree for a given tree block. root of the backref tree -* corresponds the tree block, leaves of the backref tree correspond -* roots of b-trees that reference the tree block. -* -* the basic idea of this function is check backrefs of a given block -* to find upper level blocks that reference the block, and then check -* backrefs of these upper level blocks recursively. the recursion stop -* when tree root is reached or backrefs for the block is cached. -* -* NOTE: if we find backrefs for a block are cached, we know backrefs -* for all upper level blocks that directly/indirectly reference the -* block are also cached. -*/ -static noinline_for_stack -struct backref_node *build_backref_tree(struct reloc_control *rc, -struct btrfs_key *node_key, -int level,u64 bytenr) +static int handle_one_tree_block (struct reloc_control *rc, +struct list_head *useless_node, +struct list_head *pending_edge, +struct btrfs_path *path, +struct btrfs_backref_iter *iter, +struct btrfs_key *node_key, +struct backref_node *cur) { -struct btrfs_backref_iter *iter; -struct backref_cache *cache = &rc->backref_cache; -struct btrfs_path *path;/* For searching parent of TREE_BLOCK_REF */ -struct backref_node *cur; -struct backref_node *upper; -struct backref_node *lower; -struct backref_node *node =NULL ; -struct backref_node *exist =NULL ;struct backref_edge *edge; -struct rb_node *rb_node; -LIST_HEAD (list);/* Pending edge list, upper node needs to be checked */ -LIST_HEAD (useless); -int cowonly; +struct backref_node *exist;int ret; -int err =0 ; - - iter =btrfs_backref_iter_alloc (rc->extent_root->fs_info,GFP_NOFS ); -if (!iter) -return ERR_PTR (-ENOMEM ); - path =btrfs_alloc_path (); -if (!path) { - err = -ENOMEM ; - goto out; - } - path->reada =READA_FORWARD ; - - node =alloc_backref_node (cache, bytenr, level); -if (!node) { - err = -ENOMEM ; - goto out; - } - node->lowest =1 ; - cur = node; -again: ret =btrfs_backref_iter_start (iter, cur->bytenr); -if (ret <0 ) { - err = ret; - goto out; - } +if (ret <0 ) +return ret;/* * We skip the first btrfs_tree_block_info, as we don't use the key @@ -958,13 +914,11 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,*/ if (btrfs_backref_has_tree_block_info (iter)) { ret =btrfs_backref_iter_next (iter); -if (ret <0 ) { - err = ret; +if (ret <0 ) goto out; - }/* No extra backref? This means the tree block is corrupted */ if (ret >0 ) { - err = -EUCLEAN ; + ret = -EUCLEAN ; goto out; } }@@ -984,7 +938,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,* check its backrefs */ if (!exist->checked) -list_add_tail (&edge->list[UPPER ], &list); +list_add_tail (&edge->list[UPPER ], pending_edge); }else { exist =NULL ; }@@ -1006,7 +960,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;@@ -1029,29 +983,90 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,continue ; } - ret =handle_one_tree_backref (rc, &useless, &list, path, &key, - node_key, cur); -if (ret <0 ) { - err = ret; + ret =handle_one_tree_backref (rc, useless_node, pending_edge, path, + &key, node_key, cur); +if (ret <0 ) goto out; - } } -if (ret <0 ) { - err = ret; +if (ret <0 ) goto out; - } ret =0 ; -btrfs_backref_iter_release (iter); - cur->checked =1 ;WARN_ON (exist); +out: +btrfs_backref_iter_release (iter); +return ret; +} -/* the pending list isn't empty, take the first block to process */ -if (!list_empty (&list)) { - edge = list_entry(list.next, struct backref_edge, list[UPPER]); -list_del_init (&edge->list[UPPER ]); - cur = edge->node[UPPER ]; - goto again; +/* +* build backref tree for a given tree block. root of the backref tree +* corresponds the tree block, leaves of the backref tree correspond +* roots of b-trees that reference the tree block. +* +* the basic idea of this function is check backrefs of a given block +* to find upper level blocks that reference the block, and then check +* backrefs of these upper level blocks recursively. the recursion stop +* when tree root is reached or backrefs for the block is cached. +* +* NOTE: if we find backrefs for a block are cached, we know backrefs +* for all upper level blocks that directly/indirectly reference the +* block are also cached. +*/ +static noinline_for_stack +struct backref_node *build_backref_tree(struct reloc_control *rc, +struct btrfs_key *node_key, +int level,u64 bytenr) +{ +struct btrfs_backref_iter *iter; +struct backref_cache *cache = &rc->backref_cache; +struct btrfs_path *path;/* For searching parent of TREE_BLOCK_REF */ +struct backref_node *cur; +struct backref_node *upper; +struct backref_node *lower; +struct backref_node *node =NULL ; +struct backref_edge *edge;
fs/btrfs/relocation.c struct backref_node *build_backref_tree(struct reloc_control *rc, · line 1037
Quoted 10 lines
fs/btrfs/relocation.c +10
-0+struct rb_node *rb_node; +LIST_HEAD (list);/* Pending edge list, upper node needs to be checked */ +LIST_HEAD (useless); +int cowonly; +int ret; +int err =0 ; + + iter =btrfs_backref_iter_alloc (rc->extent_root->fs_info,GFP_NOFS ); +if (!iter) +return ERR_PTR (-ENOMEM );
This iterator can be made private to handle_one_tree_block as I don't see it being used outside of that function.
fs/btrfs/relocation.c struct backref_node *build_backref_tree(struct reloc_control *rc, · line 1042
Quoted 5 lines
fs/btrfs/relocation.c +5
-0+ path =btrfs_alloc_path (); +if (!path) { + err = -ENOMEM ; + goto out; + }
Same thing with this path. Overall this will reduce the argument to handle_one_tree_block by 2.
Quoted 12 lines
fs/btrfs/relocation.c +12
-0+ 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 */
fs/btrfs/relocation.c struct backref_node *build_backref_tree(struct reloc_control *rc, · line 1064
Quoted 10 lines
fs/btrfs/relocation.c +10
-0+while (1 ) { + ret =handle_one_tree_block (rc, &useless, &list, path, iter, + node_key, cur); +if (ret <0 ) { + err = ret; + goto out; + } +/* the pending list isn't empty, take the first block to process */ +if (!list_empty (&list)) { + edge = list_entry(list.next, struct backref_edge, list[UPPER]);
Use list_first_entry_or_null or it would become:
edge = list_first_entry_or_null();
if (edge) {list_del_init(&edge->list[UPPER]);
cur = edge->node[UPPER]
} else {
breakl
}
or simply if (!edge)
break;
Also this loop can be rewritten as a do {} while() and it will look:
/* Breadth-first search to build backref cache */
do {
ret = handle_one_tree_block(rc, &useless, &list, path, iter,
node_key, cur);
if (ret < 0) {
err = ret;
goto out;
}
edge = list_first_entry_or_null(&list, 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)IMO this is shorter than the original version and it's very expicit about it's terminating conditions:
a). handle_one_tree_block returns an error
b) list becomes empty.
Alternatively list being empty is really a proxy for "is cur a valid inode". We know it's always valid on the first iteration since it's passed form the caller, subsequent iterations assign cur to edge->node[UPPER] so it could even be
while(cur) {}
In my opinion reducing while(1) loops where it makes sense (as in this case) is preferable.
NB: I've only compile-tested it.
Quoted 9 lines
fs/btrfs/relocation.c +5
-0+list_del_init (&edge->list[UPPER ]); + cur = edge->node[UPPER ]; + }else { +break ; + } }/*
Re: [PATCH v2 08/10] btrfs: relocation: Remove the open-coded goto loop for breadth-first search
Quoted 1 line · Nikolay Borisov
[...]
Quoted 7 lines
fs/btrfs/relocation.c struct backref_node *build_backref_tree(struct reloc_control *rc, · line 1037
Quoted 5 lines
fs/btrfs/relocation.c +5
-0+int err =0 ; + + iter =btrfs_backref_iter_alloc (rc->extent_root->fs_info,GFP_NOFS ); +if (!iter) +return ERR_PTR (-ENOMEM );This iterator can be made private to
handle_one_tree_blockas I don't see it being used outside of that function.
It's kinda a performance optimization.
Instead of allocating memory for each loop, we allocate the memory just once, and reuse it until the whole backref map for the bytenr is built.
Quoted 8 lines
fs/btrfs/relocation.c struct backref_node *build_backref_tree(struct reloc_control *rc, · line 1042
Quoted 6 lines
fs/btrfs/relocation.c +5
-0+ path =btrfs_alloc_path (); +if (!path) { + err = -ENOMEM ; + goto out; + }Same thing with this path. Overall this will reduce the argument to
handle_one_tree_blockby 2.
Same performance optimization here.
Quoted 26 lines
Quoted 13 lines
fs/btrfs/relocation.c +12
-0+ 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 */ fs/btrfs/relocation.c struct backref_node *build_backref_tree(struct reloc_control *rc, · line 1064
Quoted 10 lines
fs/btrfs/relocation.c +10
-0+while (1 ) { + ret =handle_one_tree_block (rc, &useless, &list, path, iter, + node_key, cur); +if (ret <0 ) { + err = ret; + goto out; + } +/* the pending list isn't empty, take the first block to process */ +if (!list_empty (&list)) { + edge = list_entry(list.next, struct backref_edge, list[UPPER]);Use
list_first_entry_or_nullor it would become:
Quoted 7 lines
edge =
list_first_entry_or_null();
if (edge) {list_del_init(&edge->list[UPPER]);
cur = edge->node[UPPER]
} else {
breakl
}
That's an interesting wrapper. Would go that way.
Quoted 5 lines
or simply if (!edge)
break;Also this loop can be rewritten as a do {}
while()and it will look:
Yep, but I'm not sure if such do {} while() loop is preferred. IIRC there are some docs saying to avoid such loop?
If there is no such restriction, I would be pretty happy to go that way.
Thanks,
Qu
Quoted 41 lines
/* Breadth-first search to build backref cache */ do { ret = handle_one_tree_block(rc, &useless, &list, path, iter, node_key, cur); if (ret < 0) { err = ret; goto out; } edge = list_first_entry_or_null(&list, 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)IMO this is shorter than the original version and it's very expicit about it's terminating conditions:
a).handle_one_tree_blockreturns an error
b) list becomes empty.Alternatively list being empty is really a proxy for "is cur a valid inode". We know it's always valid on the first iteration since it's passed form the caller, subsequent iterations assign cur to edge->node[UPPER] so it could even be
while(cur) {}
In my opinion reducing while(1) loops where it makes sense (as in this case) is preferable.
NB: I've only compile-tested it.
Quoted 9 lines
fs/btrfs/relocation.c +5
-0+list_del_init (&edge->list[UPPER ]); + cur = edge->node[UPPER ]; + }else { +break ; + } }/*
Re: [PATCH v2 08/10] btrfs: relocation: Remove the open-coded goto loop for breadth-first search
Quoted 26 lines · Qu Wenruo
Quoted 1 line · Nikolay Borisov
[...]
Quoted 7 lines
fs/btrfs/relocation.c struct backref_node *build_backref_tree(struct reloc_control *rc, · line 1037
Quoted 5 lines
fs/btrfs/relocation.c +5
-0+int err =0 ; + + iter =btrfs_backref_iter_alloc (rc->extent_root->fs_info,GFP_NOFS ); +if (!iter) +return ERR_PTR (-ENOMEM );This iterator can be made private to
handle_one_tree_blockas I don't see it being used outside of that function.It's kinda a performance optimization.
Instead of allocating memory for each loop, we allocate the memory just once, and reuse it until the whole backref map for the bytenr is built.
Quoted 8 lines
fs/btrfs/relocation.c struct backref_node *build_backref_tree(struct reloc_control *rc, · line 1042
Quoted 6 lines
fs/btrfs/relocation.c +5
-0+ path =btrfs_alloc_path (); +if (!path) { + err = -ENOMEM ; + goto out; + }Same thing with this path. Overall this will reduce the argument to
handle_one_tree_blockby 2.
Quoted 1 line
Same performance optimization here.
Ok, fair point.
Quoted 2 lines
Quoted 2 lines
<snip>
Quoted 8 lines
Quoted 5 lines
or simply if (!edge)
break;Also this loop can be rewritten as a do {}
while()and it will look:Yep, but I'm not sure if such do {}
while()loop is preferred. IIRC there are some docs saying to avoid such loop?
I'm not aware of any such docs, can you point me to them?
Quoted 6 lines
If there is no such restriction, I would be pretty happy to go that way.
Thanks,
Qu
<snip>
Re: [PATCH v2 08/10] btrfs: relocation: Remove the open-coded goto loop for breadth-first search
Quoted 41 lines · Nikolay Borisov
Quoted 26 lines · Qu Wenruo
Quoted 1 line · Nikolay Borisov
[...]
Quoted 7 lines
fs/btrfs/relocation.c struct backref_node *build_backref_tree(struct reloc_control *rc, · line 1037
Quoted 5 lines
fs/btrfs/relocation.c +5
-0+int err =0 ; + + iter =btrfs_backref_iter_alloc (rc->extent_root->fs_info,GFP_NOFS ); +if (!iter) +return ERR_PTR (-ENOMEM );This iterator can be made private to
handle_one_tree_blockas I don't see it being used outside of that function.It's kinda a performance optimization.
Instead of allocating memory for each loop, we allocate the memory just once, and reuse it until the whole backref map for the bytenr is built.
Quoted 8 lines
fs/btrfs/relocation.c struct backref_node *build_backref_tree(struct reloc_control *rc, · line 1042
Quoted 6 lines
fs/btrfs/relocation.c +5
-0+ path =btrfs_alloc_path (); +if (!path) { + err = -ENOMEM ; + goto out; + }Same thing with this path. Overall this will reduce the argument to
handle_one_tree_blockby 2.Quoted 1 line
Same performance optimization here.
Ok, fair point.
Quoted 2 lines
Quoted 2 lines
<snip>
Quoted 4 lines
Quoted 4 lines
or simply if (!edge)
break;
Quoted 6 lines
Quoted 4 lines
Quoted 1 line
Also this loop can be rewritten as a do {}
while()and it will look:Yep, but I'm not sure if such do {}
while()loop is preferred. IIRC there are some docs saying to avoid such loop?I'm not aware of any such docs, can you point me to them?
Then I guess it's not a problem. Pretty happy to utilize do {} while () loop in the future.
Thanks,
Qu
Quoted 10 lines
Quoted 7 lines
If there is no such restriction, I would be pretty happy to go that way.
Thanks,
Qu<snip>
PATCH v2 9/10 btrfs: relocation: Refactor the finishing part of upper linkage into finish_upper_links()
In reply to Qu WenruoAfter handle_one_tree_backref(), all newly added (not cached) edges and nodes have the following features:
- Only backref_edge::list[LOWER] is linked.
This means, we can only iterate from botton to top, not the other direction.
- Newly added nodes are not added to cache rb_tree yet
So to finish the backref cache, we still need to finish the links and add all nodes into backref cache rb_tree.
This patch will refactor the existing code into finish_upper_links(), add more comments of each branch, and why we need to do all these works.
--- fs/btrfs/relocation.c | 163 +++++++++++++++++++++++++++--------------- 1 file changed, 107 insertions(+), 56 deletions(-)
fs/btrfs/relocation.c +107 -56
@@ -998,6 +998,106 @@ static int handle_one_tree_block(struct reloc_control *rc,return ret; } +/* +* In handle_one_tree_backref(), we have only linked the lower node to the edge, +* but the upper node hasn't been linked to the edge. +* This means we can only iterate through backref_node::upper to reach parent +* edges, but not through backref_node::lower to reach children edges. +* +* This function will finish the backref_node::lower to related edges, so that +* backref cache can be bi-directionally iterated. +* +* Also, this will add the nodes to backref cache for next run. +*/ +static int finish_upper_links (struct backref_cache *cache, +struct backref_node *start, +struct list_head *useless_node) +{ +struct backref_edge *edge; +LIST_HEAD (pending_edge); + +/* +* Use breadth first search to iterate all related edges. +* +* The start point is all the edges of this node +*/ +list_for_each_entry (edge, &start->upper, list[LOWER ]) +list_add_tail (&edge->list[UPPER ], &pending_edge); + +while (!list_empty (&pending_edge)) { +struct backref_node *upper; +struct backref_node *lower; +struct rb_node *rb_node; + + edge = list_entry(pending_edge.next, struct backref_edge, + list[UPPER ]); +list_del_init (&edge->list[UPPER ]); + upper = edge->node[UPPER ]; + lower = edge->node[LOWER ]; + +/* Parent is detached, no need to keep any edges */ +if (upper->detached) { +list_del (&edge->list[LOWER ]); +free_backref_edge (cache, edge); + +/* Lower node is orphan, queue for cleanup */ +if (list_empty (&lower->upper)) +list_add (&lower->list, useless_node); +continue ; + } + +/* +* All new nodes added in current build_backref_tree() haven't +* been linked to the cache rb tree. +* So if we have upper->rb_node populated, this means a cache +* hit. We only need to link the edge, as @upper and all its +* parent have already been linked. +*/ +if (!RB_EMPTY_NODE (&upper->rb_node)) { +if (upper->lowest) { +list_del_init (&upper->lower); + upper->lowest =0 ; + } + +list_add_tail (&edge->list[UPPER ], &upper->lower); +continue ; + } + +/* Sanity check, we shouldn't have any unchecked nodes */ +if (!upper->checked) { +ASSERT (0 ); +return -EUCLEAN ; + } + +/* Sanity check, cowonly node has non-cowonly parent */ +if (start->cowonly != upper->cowonly) { +ASSERT (0 ); +return -EUCLEAN ; + } + +/* Only cache non-cowonly (subvolume trees) tree blocks */ +if (!upper->cowonly) { + rb_node =tree_insert (&cache->rb_root, upper->bytenr, + &upper->rb_node); +if (rb_node) { +backref_tree_panic (rb_node, -EEXIST , + upper->bytenr); +return -EUCLEAN ; + } + } + +list_add_tail (&edge->list[UPPER ], &upper->lower); + +/* +* Also queue all the parent edges of this uncached node +* to finish the upper linkage +*/ +list_for_each_entry (edge, &upper->upper, list[LOWER ]) +list_add_tail (&edge->list[UPPER ], &pending_edge); + } +return 0 ; +} +/* * build backref tree for a given tree block. root of the backref tree * corresponds the tree block, leaves of the backref tree correspond
@@ -1028,7 +1128,6 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,struct rb_node *rb_node;LIST_HEAD (list);/* Pending edge list, upper node needs to be checked */ LIST_HEAD (useless); -int cowonly;int ret;int err =0 ;
@@ -1074,8 +1173,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,* into the cache. */ ASSERT (node->checked); - cowonly = node->cowonly; -if (!cowonly) { +if (!node->cowonly) { rb_node =tree_insert (&cache->rb_root, node->bytenr, &node->rb_node);if (rb_node)
@@ -1083,60 +1181,13 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,list_add_tail (&node->lower, &cache->leaves); } -list_for_each_entry (edge, &node->upper, list[LOWER ]) -list_add_tail (&edge->list[UPPER ], &list); - -while (!list_empty (&list)) { - edge = list_entry(list.next, struct backref_edge, list[UPPER]); -list_del_init (&edge->list[UPPER ]); - upper = edge->node[UPPER ]; -if (upper->detached) { -list_del (&edge->list[LOWER ]); - lower = edge->node[LOWER ]; -free_backref_edge (cache, edge); -if (list_empty (&lower->upper)) -list_add (&lower->list, &useless); -continue ; - } - -if (!RB_EMPTY_NODE (&upper->rb_node)) { -if (upper->lowest) { -list_del_init (&upper->lower); - upper->lowest =0 ; - } - -list_add_tail (&edge->list[UPPER ], &upper->lower); -continue ; - } - -if (!upper->checked) { -/* -* Still want to blow up for developers since this is a -* logic bug. -*/ -ASSERT (0 ); - err = -EINVAL ; - goto out; - } -if (cowonly != upper->cowonly) { -ASSERT (0 ); - err = -EINVAL ; - goto out; - } - -if (!cowonly) { - rb_node =tree_insert (&cache->rb_root, upper->bytenr, - &upper->rb_node); -if (rb_node) -backref_tree_panic (rb_node, -EEXIST , - upper->bytenr); - } - -list_add_tail (&edge->list[UPPER ], &upper->lower); - -list_for_each_entry (edge, &upper->upper, list[LOWER ]) -list_add_tail (&edge->list[UPPER ], &list); +/* Finish the upper linkage of newly added edges/nodes */ + ret =finish_upper_links (cache, node, &useless); +if (ret <0 ) { + err = ret; + goto out; } +/* * process useless backref nodes. backref nodes for tree leaves * are deleted from the cache. backref nodes for upper level
Signature · 1 line
2.25.1
PATCH v2 10/10 btrfs: relocation: Refactor the useless nodes handling into its own function
In reply to Qu WenruoThis patch will also add some comment for the cleanup up.
--- fs/btrfs/relocation.c | 111 ++++++++++++++++++++++++++++-------------- 1 file changed, 75 insertions(+), 36 deletions(-)
fs/btrfs/relocation.c +75 -36
@@ -1098,6 +1098,79 @@ static int finish_upper_links(struct backref_cache *cache,return 0 ; } +/* +* For useless nodes, do two major clean ups: +* - Cleanup the children edges and nodes +* If child node is also orphan (no parent) during cleanup, then the +* child node will also be cleaned up. +* +* - Freeing up leaves (level 0), keeps nodes detached +* For nodes, the node is still cached as "detached" +* +* Return false if @node is not in the @useless_nodes list. +* Return true if @node is in the @useless_nodes list. +*/ +static bool handle_useless_nodes (struct reloc_control *rc, +struct list_head *useless_nodes, +struct backref_node *node) +{ +struct backref_cache *cache = &rc->backref_cache; +bool ret = false; + +while (!list_empty (useless_nodes)) { +struct backref_node *cur; + + cur = list_entry(useless_nodes->next, struct backref_node, + list); +list_del_init (&cur->list); + +/* Only tree root nodes can be added to @useless_nodes */ +ASSERT (list_empty (&cur->upper)); + +if (cur == node) + ret = true; + +/* The node is the lowest node */ +if (cur->lowest) { +list_del_init (&cur->lower); + cur->lowest =0 ; + } + +/* Cleanup the lower edges */ +while (!list_empty (&cur->lower)) { +struct backref_edge *edge; +struct backref_node *lower; + + edge =list_entry (cur->lower.next, + struct backref_edge, list[UPPER]); +list_del (&edge->list[UPPER ]); +list_del (&edge->list[LOWER ]); + lower = edge->node[LOWER ]; +free_backref_edge (cache, edge); + +/* Child node is also orphan, queue for cleanup */ +if (list_empty (&lower->upper)) +list_add (&lower->list, useless_nodes); + } +/* Mark this block processed for relocation */ +mark_block_processed (rc, cur); + +/* +* Backref nodes for tree leaves are deleted from the cache. +* Backref nodes for upper level tree blocks are left in the +* cache to avoid unnecessary backref lookup. +*/ +if (cur->level >0 ) { +list_add (&cur->list, &cache->detached); + cur->detached =1 ; + }else { +rb_erase (&cur->rb_node, &cache->rb_root); +free_backref_node (cache, cur); + } + } +return ret; +} +/* * build backref tree for a given tree block. root of the backref tree * corresponds the tree block, leaves of the backref tree correspond
@@ -1188,42 +1261,8 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, goto out; } -/* -* process useless backref nodes. backref nodes for tree leaves -* are deleted from the cache. backref nodes for upper level -* tree blocks are left in the cache to avoid unnecessary backref -* lookup. -*/ -while (!list_empty (&useless)) { - upper = list_entry(useless.next, struct backref_node, list); -list_del_init (&upper->list); -ASSERT (list_empty (&upper->upper)); -if (upper == node) - node =NULL ; -if (upper->lowest) { -list_del_init (&upper->lower); - upper->lowest =0 ; - } -while (!list_empty (&upper->lower)) { - edge =list_entry (upper->lower.next, - struct backref_edge, list[UPPER]); -list_del (&edge->list[UPPER ]); -list_del (&edge->list[LOWER ]); - lower = edge->node[LOWER ]; -free_backref_edge (cache, edge); - -if (list_empty (&lower->upper)) -list_add (&lower->list, &useless); - } -mark_block_processed (rc, upper); -if (upper->level >0 ) { -list_add (&upper->list, &cache->detached); - upper->detached =1 ; - }else { -rb_erase (&upper->rb_node, &cache->rb_root); -free_backref_node (cache, upper); - } - } +if (handle_useless_nodes (rc, &useless, node)) + node =NULL ; out:btrfs_backref_iter_free (iter);btrfs_free_path (path);
Signature · 1 line
2.25.1