On 2020/1/3 下午5:44, ethanwu wrote:
> Btrfs has two types of data backref.
> For BTRFS_EXTENT_DATA_REF_KEY type of backref, we don't have the
> exact block number. Therefore, we need to call resolve_indirect_refs
> which uses btrfs_search_slot to locate the leaf block. After that,
> we need to walk through the leafs to search for the EXTENT_DATA items
> that have disk bytenr matching the extent item(add_all_parents).
>
> The only conditions we'll stop searching are
> 1. We find different object id or type is not EXTENT_DATA
> 2. We've already got all the refs we want(total_refs)
>
> Take the following EXTENT_ITEM as example:
> item 11 key (40831553536 EXTENT_ITEM 4194304) itemoff 15460 itemsize 95
> extent refs 24 gen 7302 flags DATA
> extent data backref root 257 objectid 260 offset 65536 count 5 #backref entry 1
> extent data backref root 258 objectid 265 offset 0 count 9 #backref entry 2
> shared data backref parent 394985472 count 10 #backref entry 3
>
> If we want to search for backref entry 1, total_refs here would be 24 rather
> than its count 5.
>
> The reason to use 24 is because some EXTENT_DATA in backref entry 3 block
> 394985472 also points to EXTENT_ITEM 40831553536, if this block also belongs to
> root 257 and lies between these 5 items of backref entry 1,
> and we use total_refs = 5, we'll end up missing some refs from backref
> entry 1.
Indeed looks like a problem.
>
> But using total_refs=24 is not accurate. We'll never find extent data keys in
> backref entry 2, since we searched root 257 not 258. We'll never reach block
> 394985472 either if this block is not a leaf in root 257.
> As a result, the loop keeps on going until we reach the end of that inode.
>
> Since we're searching for parent block of this backref entry 1,
> we're 100% sure we'll never find any EXTENT_DATA beyond (65536 + 4194304) that
> matching this entry.
Backref offset is always a bug-prone member, thus I hope to double check
on this.
What if the backref offset already underflows?
Like this:
item 10 key (13631488 EXTENT_ITEM 1048576) itemoff 15860 itemsize 111
refs 3 gen 6 flags DATA
extent data backref root FS_TREE objectid 259 offset
18446744073709547520 count 1 <<<
extent data backref root FS_TREE objectid 257 offset 0 count 1
extent data backref root FS_TREE objectid 258 offset 4096 count 1
Since backref offset is not file offset, but file_extent_item::offset -
file_offset, it can be a super large number for reflinked extents.
Current kernel handles this by a very ugly but working hack: resetting
key_for_search.offset to 0 in add_prelim_ref() if it detects such case.
Then this would screw up your check, causing unexpected early exit.
I guess we have to find a new method to solve the problem then.
Thanks,
Qu
> If there's any EXTENT_DATA with offset beyond this range
> using this extent item, its backref must be stored at different backref entry.
> That EXTENT_DATA will be handled when we process that backref entry.
>
> Fix this by breaking from loop if we reach offset + (size of EXTENT_ITEM).
>
> btrfs send use backref to search for clone candidate.
> Without this patch, performance drops when running following script.
> This script creates a 10G file with all of its extent size 64K.
> Then it generates shared backref for each data extent, and
> those backrefs could not be found when doing btrfs_resolve_indirect_refs.
>
> item 87 key (11843469312 EXTENT_ITEM 65536) itemoff 10475 itemsize 66
> refs 3 gen 74 flags DATA
> extent data backref root 256 objectid 260 offset 10289152 count 2
> # This shared backref couldn't be found when resolving
> # indirect ref from snapshot of sub 256
> shared data backref parent 2303049728 count 1
>
> btrfs subvolume create /volume1/sub1
> for i in `seq 1 163840`; do dd if=/dev/zero of=/volume1/sub1/file bs=64K count=1 seek=$((i-1)) conv=notrunc oflag=direct 2>/dev/null; done
> btrfs subvolume snapshot /volume1/sub1 /volume1/sub2
> for i in `seq 1 163840`; do dd if=/dev/zero of=/volume1/sub1/file bs=4K count=1 seek=$(((i-1)*16+10)) conv=notrunc oflag=direct 2>/dev/null; done
> btrfs subvolume snapshot -r /volume1/sub1 /volume1/snap1
> time btrfs send /volume1/snap1 | btrfs receive /volume2
>
> without this patch
> real 69m48.124s
> user 0m50.199s
> sys 70m15.600s
>
> with this patch
> real 1m31.498s
> user 0m35.858s
> sys 2m55.544s
>
> Signed-off-by: ethanwu <ethanwu@xxxxxxxxxxxx>
> ---
> fs/btrfs/backref.c | 21 +++++++++++++++------
> 1 file changed, 15 insertions(+), 6 deletions(-)
>
> diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
> index e5d8531..ae64995 100644
> --- a/fs/btrfs/backref.c
> +++ b/fs/btrfs/backref.c
> @@ -412,7 +412,7 @@ static int add_indirect_ref(const struct btrfs_fs_info *fs_info,
> static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path,
> struct ulist *parents, struct prelim_ref *ref,
> int level, u64 time_seq, const u64 *extent_item_pos,
> - u64 total_refs, bool ignore_offset)
> + u64 total_refs, bool ignore_offset, u64 num_bytes)
> {
> int ret = 0;
> int slot;
> @@ -458,6 +458,9 @@ static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path,
> fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
> disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);
>
> + if (key_for_search->type == BTRFS_EXTENT_DATA_KEY &&
> + key.offset >= key_for_search->offset + num_bytes)
> + break;
> if (disk_byte == wanted_disk_byte) {
> eie = NULL;
> old = NULL;
> @@ -504,7 +507,7 @@ static int resolve_indirect_ref(struct btrfs_fs_info *fs_info,
> struct btrfs_path *path, u64 time_seq,
> struct prelim_ref *ref, struct ulist *parents,
> const u64 *extent_item_pos, u64 total_refs,
> - bool ignore_offset)
> + bool ignore_offset, u64 num_bytes)
> {
> struct btrfs_root *root;
> struct btrfs_key root_key;
> @@ -575,7 +578,8 @@ static int resolve_indirect_ref(struct btrfs_fs_info *fs_info,
> }
>
> ret = add_all_parents(root, path, parents, ref, level, time_seq,
> - extent_item_pos, total_refs, ignore_offset);
> + extent_item_pos, total_refs, ignore_offset,
> + num_bytes);
> out:
> path->lowest_level = 0;
> btrfs_release_path(path);
> @@ -610,7 +614,8 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
> struct btrfs_path *path, u64 time_seq,
> struct preftrees *preftrees,
> const u64 *extent_item_pos, u64 total_refs,
> - struct share_check *sc, bool ignore_offset)
> + struct share_check *sc, bool ignore_offset,
> + u64 num_bytes)
> {
> int err;
> int ret = 0;
> @@ -655,7 +660,7 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
> }
> err = resolve_indirect_ref(fs_info, path, time_seq, ref,
> parents, extent_item_pos,
> - total_refs, ignore_offset);
> + total_refs, ignore_offset, num_bytes);
> /*
> * we can only tolerate ENOENT,otherwise,we should catch error
> * and return directly.
> @@ -1127,6 +1132,7 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
> struct extent_inode_elem *eie = NULL;
> /* total of both direct AND indirect refs! */
> u64 total_refs = 0;
> + u64 num_bytes = SZ_256M;
> struct preftrees preftrees = {
> .direct = PREFTREE_INIT,
> .indirect = PREFTREE_INIT,
> @@ -1194,6 +1200,7 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
> goto again;
> }
> spin_unlock(&delayed_refs->lock);
> + num_bytes = head->num_bytes;
> ret = add_delayed_refs(fs_info, head, time_seq,
> &preftrees, &total_refs, sc);
> mutex_unlock(&head->mutex);
> @@ -1215,6 +1222,7 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
> if (key.objectid == bytenr &&
> (key.type == BTRFS_EXTENT_ITEM_KEY ||
> key.type == BTRFS_METADATA_ITEM_KEY)) {
> + num_bytes = key.offset;
> ret = add_inline_refs(fs_info, path, bytenr,
> &info_level, &preftrees,
> &total_refs, sc);
> @@ -1236,7 +1244,8 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
> WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect_missing_keys.root.rb_root));
>
> ret = resolve_indirect_refs(fs_info, path, time_seq, &preftrees,
> - extent_item_pos, total_refs, sc, ignore_offset);
> + extent_item_pos, total_refs, sc, ignore_offset,
> + num_bytes);
> if (ret)
> goto out;
>
>
Attachment:
signature.asc
Description: OpenPGP digital signature
