Re: [PATCH v2 2/2] btrfs: send: fix sending link commands for existing file paths

[David Sterba <dsterba@suse.cz>]

On Tue, Jul 12, 2022 at 09:36:32AM +0800, bingjingc wrote:
> From: BingJing Chang <bingjingc@synology.com>
> 
> There is a bug sending link commands for existing file paths. When we're
> processing an inode, we go over all references. All the new file paths are
> added to the "new_refs" list. And all the deleted file paths are added to
> the "deleted_refs" list. In the end, when we finish processing the inode,
> we iterate over all the items in the "new_refs" list and send link commands
> for those file paths. After that, we go over all the items in the
> "deleted_refs" list and send unlink commands for them. If there are
> duplicated file paths in both lists, we will try to create them before we
> remove them. Then the receiver gets an -EEXIST error when trying the link
> operations.
> 
> Example for having duplicated file paths in both list:
> 
>   $ btrfs subvolume create vol
> 
>   # create a file and 2000 hard links to the same inode
>   $ touch vol/foo
>   $ for i in {1..2000}; do link vol/foo vol/$i ; done
> 
>   # take a snapshot for a parent snapshot
>   $ btrfs subvolume snapshot -r vol snap1
> 
>   # remove 2000 hard links and re-create the last 1000 links
>   $ for i in {1..2000}; do rm vol/$i; done;
>   $ for i in {1001..2000}; do link vol/foo vol/$i; done
> 
>   # take another one for a send snapshot
>   $ btrfs subvolume snapshot -r vol snap2
> 
>   $ mkdir receive_dir
>   $ btrfs send snap2 -p snap1 | btrfs receive receive_dir/
>   At subvol snap2
>   link 1238 -> foo
>   ERROR: link 1238 -> foo failed: File exists
> 
> In this case, we will have the same file paths added to both lists. In the
> parent snapshot, reference paths {1..1237} are stored in inode references,
> but reference paths {1238..2000} are stored in inode extended references.
> In the send snapshot, all reference paths {1001..2000} are stored in inode
> references. During the incremental send, we process their inode references
> first. In record_changed_ref(), we iterate all its inode references in the
> send/parent snapshot. For every inode reference, we also use find_iref() to
> check whether the same file path also appears in the parent/send snapshot
> or not. Inode references {1238..2000} which appear in the send snapshot but
> not in the parent snapshot are added to the "new_refs" list. On the other
> hand, Inode references {1..1000} which appear in the parent snapshot but
> not in the send snapshot are added to the "deleted_refs" list. Next, when
> we process their inode extended references, reference paths {1238..2000}
> are added to the "deleted_refs" list because all of them only appear in the
> parent snapshot. Now two lists contain items as below:
> "new_refs" list: {1238..2000}
> "deleted_refs" list: {1..1000}, {1238..2000}
> 
> Reference paths {1238..2000} appear in both lists. And as the processing
> order talked about before, the receiver gets an -EEXIST error when trying
> the link operations.
> 
> To fix the bug, the intuition is to process the "deleted_refs" list before
> the "new_refs" list. However, it's not easy to reshuffle the processing
> order. For one reason, if we do so, we may unlink all the existing paths
> first, there's no valid path anymore for links. And it's inefficient
> because we do a bunch of unlinks followed by links for the same paths.
> Moreover, it makes less sense to have duplications in both lists. A
> reference path cannot not only be regarded as new but also has been seen in
> the past, or we won't call it a new path. However, it's also not a good
> idea to make find_iref() to check a reference against all inode references
> and all inode extended references because it may result in large disk
> reads. So we introduce two rbtrees to make the references easier for
> lookups. And we also introduce __record_new_ref_if_needed() and
> __record_deleted_ref_if_needed() for changed_ref() to check and remove
> duplicated references early.
> 
> Reviewed-by: Robbie Ko <robbieko@synology.com>
> Signed-off-by: BingJing Chang <bingjingc@synology.com>

Added to misc-next with some fixups, thanks.

> +static int rbtree_ref_comp(const void *k, const struct rb_node *node)
> +{
> +	const struct recorded_ref *data = k;
> +	const struct recorded_ref *ref = rb_entry(node, struct recorded_ref, node);
> +	int result;
> +
> +	if (data->dir > ref->dir)
> +		return 1;
> +	if (data->dir < ref->dir)
> +		return -1;
> +	if (data->dir_gen > ref->dir_gen)
> +		return 1;
> +	if (data->dir_gen < ref->dir_gen)
> +		return -1;
> +	if (data->name_len > ref->name_len)
> +		return 1;
> +	if (data->name_len < ref->name_len)
> +		return -1;
> +	result = strcmp(data->name, ref->name);

I think this is the same as

	return strcmp(...);

but I have kept it as is for now.

> +	if (result > 0)
> +		return 1;
> +	if (result < 0)
> +		return -1;
> +	return 0;
> +}
> +
> +static int __record_new_ref_if_needed(int num, u64 dir, int index,

I've dropped the __ and updated all callers, it's not appropriate to be
used here.

> +				      struct fs_path *name, void *ctx)
> +{
> +	int ret = 0;
> +	struct send_ctx *sctx = ctx;
> +	struct rb_node *node = NULL;
> +	struct recorded_ref data;
> +	struct recorded_ref *ref;
> +	u64 dir_gen;
> +
> +	ret = get_inode_info(sctx->send_root, dir, NULL, &dir_gen, NULL,
> +			     NULL, NULL, NULL);

This function got a new parameter in "btrfs: send: add new command
FILEATTR for file attributes", so added NULL in all new instances.

> +	if (ret < 0)
> +		goto out;
> +
> +	data.dir = dir;
> +	data.dir_gen = dir_gen;
> +	set_ref_path(&data, name);
> +	node = rb_find(&data, &sctx->rbtree_deleted_refs, rbtree_ref_comp);
> +	if (node) {
> +		ref = rb_entry(node, struct recorded_ref, node);
> +		recorded_ref_free(ref);
> +	} else {
> +		ret = record_ref_in_tree(&sctx->rbtree_new_refs,
> +					 &sctx->new_refs, name, dir, dir_gen,
> +					 sctx);
> +	}
> +out:
> +	return ret;
> +}
> +
> +static int __record_deleted_ref_if_needed(int num, u64 dir, int index,

Same, dropped __

> +			    struct fs_path *name,
> +			    void *ctx)
> +{
> +	int ret = 0;
> +	struct send_ctx *sctx = ctx;
> +	struct rb_node *node = NULL;
> +	struct recorded_ref data;
> +	struct recorded_ref *ref;
> +	u64 dir_gen;
> +
> +	ret = get_inode_info(sctx->parent_root, dir, NULL, &dir_gen, NULL,
> +			     NULL, NULL, NULL);
> +	if (ret < 0)
> +		goto out;
> +
> +	data.dir = dir;
> +	data.dir_gen = dir_gen;
> +	set_ref_path(&data, name);
> +	node = rb_find(&data, &sctx->rbtree_new_refs, rbtree_ref_comp);
> +	if (node) {
> +		ref = rb_entry(node, struct recorded_ref, node);
> +		recorded_ref_free(ref);
> +	} else {
> +		ret = record_ref_in_tree(&sctx->rbtree_deleted_refs,
> +					 &sctx->deleted_refs, name, dir,
> +					 dir_gen, sctx);
> +	}
> +out:
> +	return ret;
> +}