* [PATCH v3 1/7] Revert "Btrfs: incremental send, remove dead code"
2015-06-23 10:39 [PATCH v3 0/7] Btrfs incremental send fix serval case for rename and rm directory Robbie Ko
@ 2015-06-23 10:39 ` Robbie Ko
2015-06-23 15:09 ` Filipe David Manana
2015-06-23 10:39 ` [PATCH v3 2/7] Btrfs: incremental send, avoid circular waiting and descendant overwrite ancestor need to update path Robbie Ko
` (6 subsequent siblings)
7 siblings, 1 reply; 13+ messages in thread
From: Robbie Ko @ 2015-06-23 10:39 UTC (permalink / raw)
To: linux-btrfs; +Cc: Robbie Ko
This reverts commit 5f806c3ae2ff6263a10a6901f97abb74dac03d36.
This is a necessary patch for a subsequent patch in the series (patch 3).
"[PATCH] Btrfs: incremental send, don't delay directory renames
unnecessarily" changes behavior of wait_for_parent_move function.
It may cause path loop problem, so fix it in the patch 3.
Example:
Parent snapshot:
|---- @tmp/ (ino 257)
|---- pre/ (ino 260)
|---- wait_dir (ino 261)
|---- ance/ (ino 263)
|---- wait_at_below_ance/ (ino 259)
|---- desc/ (ino 262)
|---- other_dir/ (ino 264)
Send snapshot:
|---- @tmp/ (ino 257)
|---- other_dir/ (ino 264)
|---- wait_at_below_ance/ (ino 259)
|---- pre/ (ino 260)
|---- wait_dir/ (ino 261)
|---- desc/ (ino 262)
|---- ance/ (ino 263)
This cause will cause path building loop like this : 261 -> 260 -> 259 ->
263 -> 262 -> 261
Signed-off-by: Robbie Ko <robbieko@synology.com>
---
V3: modify comment
fs/btrfs/send.c | 59 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 59 insertions(+)
diff --git a/fs/btrfs/send.c b/fs/btrfs/send.c
index 1c1f161..257753b 100644
--- a/fs/btrfs/send.c
+++ b/fs/btrfs/send.c
@@ -3080,6 +3080,48 @@ static struct pending_dir_move *get_pending_dir_moves(struct send_ctx *sctx,
return NULL;
}
+static int path_loop(struct send_ctx *sctx, struct fs_path *name,
+ u64 ino, u64 gen, u64 *ancestor_ino)
+{
+ int ret = 0;
+ u64 parent_inode = 0;
+ u64 parent_gen = 0;
+ u64 start_ino = ino;
+
+ *ancestor_ino = 0;
+ while (ino != BTRFS_FIRST_FREE_OBJECTID) {
+ fs_path_reset(name);
+
+ if (is_waiting_for_rm(sctx, ino))
+ break;
+ if (is_waiting_for_move(sctx, ino)) {
+ if (*ancestor_ino == 0)
+ *ancestor_ino = ino;
+ ret = get_first_ref(sctx->parent_root, ino,
+ &parent_inode, &parent_gen, name);
+ } else {
+ ret = __get_cur_name_and_parent(sctx, ino, gen,
+ &parent_inode,
+ &parent_gen, name);
+ if (ret > 0) {
+ ret = 0;
+ break;
+ }
+ }
+ if (ret < 0)
+ break;
+ if (parent_inode == start_ino) {
+ ret = 1;
+ if (*ancestor_ino == 0)
+ *ancestor_ino = ino;
+ break;
+ }
+ ino = parent_inode;
+ gen = parent_gen;
+ }
+ return ret;
+}
+
static int apply_dir_move(struct send_ctx *sctx, struct pending_dir_move *pm)
{
struct fs_path *from_path = NULL;
@@ -3091,6 +3133,7 @@ static int apply_dir_move(struct send_ctx *sctx, struct pending_dir_move *pm)
struct waiting_dir_move *dm = NULL;
u64 rmdir_ino = 0;
int ret;
+ u64 ancestor = 0;
name = fs_path_alloc();
from_path = fs_path_alloc();
@@ -3122,6 +3165,22 @@ static int apply_dir_move(struct send_ctx *sctx, struct pending_dir_move *pm)
goto out;
sctx->send_progress = sctx->cur_ino + 1;
+ ret = path_loop(sctx, name, pm->ino, pm->gen, &ancestor);
+ if (ret) {
+ LIST_HEAD(deleted_refs);
+ ASSERT(ancestor > BTRFS_FIRST_FREE_OBJECTID);
+ ret = add_pending_dir_move(sctx, pm->ino, pm->gen, ancestor,
+ &pm->update_refs, &deleted_refs,
+ pm->is_orphan);
+ if (ret < 0)
+ goto out;
+ if (rmdir_ino) {
+ dm = get_waiting_dir_move(sctx, pm->ino);
+ ASSERT(dm);
+ dm->rmdir_ino = rmdir_ino;
+ }
+ goto out;
+ }
fs_path_reset(name);
to_path = name;
name = NULL;
--
1.9.1
^ permalink raw reply related [flat|nested] 13+ messages in thread* Re: [PATCH v3 1/7] Revert "Btrfs: incremental send, remove dead code"
2015-06-23 10:39 ` [PATCH v3 1/7] Revert "Btrfs: incremental send, remove dead code" Robbie Ko
@ 2015-06-23 15:09 ` Filipe David Manana
2015-06-23 15:24 ` David Sterba
0 siblings, 1 reply; 13+ messages in thread
From: Filipe David Manana @ 2015-06-23 15:09 UTC (permalink / raw)
To: Robbie Ko; +Cc: linux-btrfs@vger.kernel.org
On Tue, Jun 23, 2015 at 11:39 AM, Robbie Ko <robbieko@synology.com> wrote:
> This reverts commit 5f806c3ae2ff6263a10a6901f97abb74dac03d36.
>
> This is a necessary patch for a subsequent patch in the series (patch 3).
Still confused.
Reverting that commit (5f806c3ae2ff6263a10a6901f97abb74dac03d36) alone
will fix any issue?
Reading the part below gives that understanding, but it's basically a
trimmed down version of the scenario/problem mentioned in patch 3, so
it doesn't seem, nor it's clear, that this revert alone fixes any
problem.
>
> "[PATCH] Btrfs: incremental send, don't delay directory renames
> unnecessarily" changes behavior of wait_for_parent_move function.
> It may cause path loop problem, so fix it in the patch 3.
>
> Example:
> Parent snapshot:
> |---- @tmp/ (ino 257)
> |---- pre/ (ino 260)
> |---- wait_dir (ino 261)
> |---- ance/ (ino 263)
> |---- wait_at_below_ance/ (ino 259)
> |---- desc/ (ino 262)
> |---- other_dir/ (ino 264)
>
> Send snapshot:
> |---- @tmp/ (ino 257)
> |---- other_dir/ (ino 264)
> |---- wait_at_below_ance/ (ino 259)
> |---- pre/ (ino 260)
> |---- wait_dir/ (ino 261)
> |---- desc/ (ino 262)
> |---- ance/ (ino 263)
>
> This cause will cause path building loop like this : 261 -> 260 -> 259 ->
> 263 -> 262 -> 261
>
> Signed-off-by: Robbie Ko <robbieko@synology.com>
> ---
>
> V3: modify comment
>
> fs/btrfs/send.c | 59 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 59 insertions(+)
>
> diff --git a/fs/btrfs/send.c b/fs/btrfs/send.c
> index 1c1f161..257753b 100644
> --- a/fs/btrfs/send.c
> +++ b/fs/btrfs/send.c
> @@ -3080,6 +3080,48 @@ static struct pending_dir_move *get_pending_dir_moves(struct send_ctx *sctx,
> return NULL;
> }
>
> +static int path_loop(struct send_ctx *sctx, struct fs_path *name,
> + u64 ino, u64 gen, u64 *ancestor_ino)
> +{
> + int ret = 0;
> + u64 parent_inode = 0;
> + u64 parent_gen = 0;
> + u64 start_ino = ino;
> +
> + *ancestor_ino = 0;
> + while (ino != BTRFS_FIRST_FREE_OBJECTID) {
> + fs_path_reset(name);
> +
> + if (is_waiting_for_rm(sctx, ino))
> + break;
> + if (is_waiting_for_move(sctx, ino)) {
> + if (*ancestor_ino == 0)
> + *ancestor_ino = ino;
> + ret = get_first_ref(sctx->parent_root, ino,
> + &parent_inode, &parent_gen, name);
> + } else {
> + ret = __get_cur_name_and_parent(sctx, ino, gen,
> + &parent_inode,
> + &parent_gen, name);
> + if (ret > 0) {
> + ret = 0;
> + break;
> + }
> + }
> + if (ret < 0)
> + break;
> + if (parent_inode == start_ino) {
> + ret = 1;
> + if (*ancestor_ino == 0)
> + *ancestor_ino = ino;
> + break;
> + }
> + ino = parent_inode;
> + gen = parent_gen;
> + }
> + return ret;
> +}
> +
> static int apply_dir_move(struct send_ctx *sctx, struct pending_dir_move *pm)
> {
> struct fs_path *from_path = NULL;
> @@ -3091,6 +3133,7 @@ static int apply_dir_move(struct send_ctx *sctx, struct pending_dir_move *pm)
> struct waiting_dir_move *dm = NULL;
> u64 rmdir_ino = 0;
> int ret;
> + u64 ancestor = 0;
>
> name = fs_path_alloc();
> from_path = fs_path_alloc();
> @@ -3122,6 +3165,22 @@ static int apply_dir_move(struct send_ctx *sctx, struct pending_dir_move *pm)
> goto out;
>
> sctx->send_progress = sctx->cur_ino + 1;
> + ret = path_loop(sctx, name, pm->ino, pm->gen, &ancestor);
> + if (ret) {
> + LIST_HEAD(deleted_refs);
> + ASSERT(ancestor > BTRFS_FIRST_FREE_OBJECTID);
> + ret = add_pending_dir_move(sctx, pm->ino, pm->gen, ancestor,
> + &pm->update_refs, &deleted_refs,
> + pm->is_orphan);
> + if (ret < 0)
> + goto out;
> + if (rmdir_ino) {
> + dm = get_waiting_dir_move(sctx, pm->ino);
> + ASSERT(dm);
> + dm->rmdir_ino = rmdir_ino;
> + }
> + goto out;
> + }
> fs_path_reset(name);
> to_path = name;
> name = NULL;
> --
> 1.9.1
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at http://vger.kernel.org/majordomo-info.html
--
Filipe David Manana,
"Reasonable men adapt themselves to the world.
Unreasonable men adapt the world to themselves.
That's why all progress depends on unreasonable men."
^ permalink raw reply [flat|nested] 13+ messages in thread* Re: [PATCH v3 1/7] Revert "Btrfs: incremental send, remove dead code"
2015-06-23 15:09 ` Filipe David Manana
@ 2015-06-23 15:24 ` David Sterba
0 siblings, 0 replies; 13+ messages in thread
From: David Sterba @ 2015-06-23 15:24 UTC (permalink / raw)
To: Filipe David Manana; +Cc: Robbie Ko, linux-btrfs@vger.kernel.org
On Tue, Jun 23, 2015 at 04:09:07PM +0100, Filipe David Manana wrote:
> On Tue, Jun 23, 2015 at 11:39 AM, Robbie Ko <robbieko@synology.com> wrote:
> > This reverts commit 5f806c3ae2ff6263a10a6901f97abb74dac03d36.
> >
> > This is a necessary patch for a subsequent patch in the series (patch 3).
>
> Still confused.
> Reverting that commit (5f806c3ae2ff6263a10a6901f97abb74dac03d36) alone
> will fix any issue?
> Reading the part below gives that understanding, but it's basically a
> trimmed down version of the scenario/problem mentioned in patch 3, so
> it doesn't seem, nor it's clear, that this revert alone fixes any
> problem.
If it's only to re-introduce the path_loop helper alone, then the revert
is indeed confusing.
^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH v3 2/7] Btrfs: incremental send, avoid circular waiting and descendant overwrite ancestor need to update path
2015-06-23 10:39 [PATCH v3 0/7] Btrfs incremental send fix serval case for rename and rm directory Robbie Ko
2015-06-23 10:39 ` [PATCH v3 1/7] Revert "Btrfs: incremental send, remove dead code" Robbie Ko
@ 2015-06-23 10:39 ` Robbie Ko
2015-06-23 10:39 ` [PATCH v3 3/7] Btrfs: incremental send, avoid ancestor rename to descendant Robbie Ko
` (5 subsequent siblings)
7 siblings, 0 replies; 13+ messages in thread
From: Robbie Ko @ 2015-06-23 10:39 UTC (permalink / raw)
To: linux-btrfs; +Cc: Robbie Ko
There are several more cases where we can't do the renames immediately.
Example1:
Parent snapshot:
|---- d/ (ino 257)
|---- p1 (ino 258)
|---- p1/ (ino 259)
Send snapshot:
|---- d/ (ino 257)
|---- p1 (ino 259)
|---- p1/ (ino 258)
Inode 258 became a child of inode 259 and both
were renamed in the send snapshot. Therefore inode 258's rename
operation is delayed to happen after 259 is renamed.
And we can not rename 259 from 'p1' to 'd/p1' without the rename
of inode 258, because the name of both 259 and 258 are identical
at the same time 258 is waiting to move.
so 259's rename is delayed to happen after 258's rename,
which creates a circular dependency (258 -> 259 -> 258).
Example2:
Parent snapshot:
|---- a/ (ino 259)
|---- c (ino 266)
|---- d/ (ino 260)
|---- ance (ino 265)
|---- e (ino 261)
|---- f (ino 262)
|---- ance (ino 263)
Send snapshot:
|---- a/ (ino 259)
|---- c/ (ino 266)
|---- ance (ino 265)
|---- d/ (ino 260)
|---- ance (ino 263)
|---- f/ (ino 262)
|---- e (ino 261)
After moving 262 outside, path of 265 is stored in the name_cache_entry.
When 263 try to overwrite 265, its ancestor, 265 is moved to orphanized.
However, the path of 263 is the original path before 265 is renamed, which
causes error while we try to rename a non-exist path.
Example3:
There is another case for 2nd scenario where is_ancestor() can't be used.
Parent snapshot:
|---- a/ (ino 261)
|---- c (ino 267)
|---- d/ (ino 259)
|---- ance/ (ino 266)
|---- waiting_dir/ (ino 262)
|---- pre/ (ino 264)
|---- ance/ (ino 265)
Send snapshot:
|---- a/ (ino 261)
|---- ance/ (ino 266)
|---- c (ino 267)
|---- waiting_dir/ (ino 262)
|---- pre/ (ino 264)
|---- d/ (ino 259)
|---- ance/ (ino 265)
First, 262 can't move to c/waiting_dir without the rename of inode 267.
Second, 264 can move into dir 262. Although 262 is waiting, 264 is not
parent of 262 in the parent root.
(The second behavior will happen after applying "[PATCH] Btrfs:
incremental send, don't delay directory renames unnecessarily")
Finally, 265 will overwrite 266 and path for 265 should be updated
since 266 is not the ancestor of 265.
Here we need to check the current state of tree rather than parent
root which is_ancestor function does.
Signed-off-by: Robbie Ko <robbieko@synology.com>
---
V3: modify comment and coding style
fs/btrfs/send.c | 43 +++++++++++++++++++++++++++++++++++++------
1 file changed, 37 insertions(+), 6 deletions(-)
diff --git a/fs/btrfs/send.c b/fs/btrfs/send.c
index 257753b..95dc1d4 100644
--- a/fs/btrfs/send.c
+++ b/fs/btrfs/send.c
@@ -230,7 +230,6 @@ struct pending_dir_move {
u64 parent_ino;
u64 ino;
u64 gen;
- bool is_orphan;
struct list_head update_refs;
};
@@ -1840,7 +1839,8 @@ static int will_overwrite_ref(struct send_ctx *sctx, u64 dir, u64 dir_gen,
* was already unlinked/moved, so we can safely assume that we will not
* overwrite anything at this point in time.
*/
- if (other_inode > sctx->send_progress) {
+ if (other_inode > sctx->send_progress ||
+ is_waiting_for_move(sctx, other_inode)) {
ret = get_inode_info(sctx->parent_root, other_inode, NULL,
who_gen, NULL, NULL, NULL, NULL);
if (ret < 0)
@@ -3014,7 +3014,6 @@ static int add_pending_dir_move(struct send_ctx *sctx,
pm->parent_ino = parent_ino;
pm->ino = ino;
pm->gen = ino_gen;
- pm->is_orphan = is_orphan;
INIT_LIST_HEAD(&pm->list);
INIT_LIST_HEAD(&pm->update_refs);
RB_CLEAR_NODE(&pm->node);
@@ -3134,6 +3133,7 @@ static int apply_dir_move(struct send_ctx *sctx, struct pending_dir_move *pm)
u64 rmdir_ino = 0;
int ret;
u64 ancestor = 0;
+ bool is_orphan;
name = fs_path_alloc();
from_path = fs_path_alloc();
@@ -3145,9 +3145,10 @@ static int apply_dir_move(struct send_ctx *sctx, struct pending_dir_move *pm)
dm = get_waiting_dir_move(sctx, pm->ino);
ASSERT(dm);
rmdir_ino = dm->rmdir_ino;
+ is_orphan = dm->orphanized;
free_waiting_dir_move(sctx, dm);
- if (pm->is_orphan) {
+ if (is_orphan) {
ret = gen_unique_name(sctx, pm->ino,
pm->gen, from_path);
} else {
@@ -3171,7 +3172,7 @@ static int apply_dir_move(struct send_ctx *sctx, struct pending_dir_move *pm)
ASSERT(ancestor > BTRFS_FIRST_FREE_OBJECTID);
ret = add_pending_dir_move(sctx, pm->ino, pm->gen, ancestor,
&pm->update_refs, &deleted_refs,
- pm->is_orphan);
+ is_orphan);
if (ret < 0)
goto out;
if (rmdir_ino) {
@@ -3351,6 +3352,7 @@ static int wait_for_dest_dir_move(struct send_ctx *sctx,
u64 left_gen;
u64 right_gen;
int ret = 0;
+ struct waiting_dir_move *wdm;
if (RB_EMPTY_ROOT(&sctx->waiting_dir_moves))
return 0;
@@ -3409,7 +3411,8 @@ static int wait_for_dest_dir_move(struct send_ctx *sctx,
goto out;
}
- if (is_waiting_for_move(sctx, di_key.objectid)) {
+ wdm = get_waiting_dir_move(sctx, di_key.objectid);
+ if (wdm && !wdm->orphanized) {
ret = add_pending_dir_move(sctx,
sctx->cur_ino,
sctx->cur_inode_gen,
@@ -3669,11 +3672,26 @@ verbose_printk("btrfs: process_recorded_refs %llu\n", sctx->cur_ino);
goto out;
if (ret) {
struct name_cache_entry *nce;
+ struct waiting_dir_move *wdm;
ret = orphanize_inode(sctx, ow_inode, ow_gen,
cur->full_path);
if (ret < 0)
goto out;
+
+ /*
+ * If ow_inode has its rename operation delayed
+ * make sure that its orphanized name is used in
+ * the source path when performing its rename
+ * operation.
+ */
+ if (is_waiting_for_move(sctx, ow_inode)) {
+ wdm = get_waiting_dir_move(sctx,
+ ow_inode);
+ ASSERT(wdm);
+ wdm->orphanized = true;
+ }
+
/*
* Make sure we clear our orphanized inode's
* name from the name cache. This is because the
@@ -3689,6 +3707,19 @@ verbose_printk("btrfs: process_recorded_refs %llu\n", sctx->cur_ino);
name_cache_delete(sctx, nce);
kfree(nce);
}
+
+ /*
+ * ow_inode might currently be an ancestor of
+ * cur_ino, therefore compute valid_path (the
+ * current path of cur_ino) again because it
+ * might contain the pre-orphanization name of
+ * ow_inode, which is no longer valid.
+ */
+ fs_path_reset(valid_path);
+ ret = get_cur_path(sctx, sctx->cur_ino,
+ sctx->cur_inode_gen, valid_path);
+ if (ret < 0)
+ goto out;
} else {
ret = send_unlink(sctx, cur->full_path);
if (ret < 0)
--
1.9.1
^ permalink raw reply related [flat|nested] 13+ messages in thread* [PATCH v3 3/7] Btrfs: incremental send, avoid ancestor rename to descendant
2015-06-23 10:39 [PATCH v3 0/7] Btrfs incremental send fix serval case for rename and rm directory Robbie Ko
2015-06-23 10:39 ` [PATCH v3 1/7] Revert "Btrfs: incremental send, remove dead code" Robbie Ko
2015-06-23 10:39 ` [PATCH v3 2/7] Btrfs: incremental send, avoid circular waiting and descendant overwrite ancestor need to update path Robbie Ko
@ 2015-06-23 10:39 ` Robbie Ko
2015-06-23 15:05 ` Filipe David Manana
2015-06-23 10:39 ` [PATCH v3 4/7] Btrfs: incremental send, fix orphan_dir_info leak Robbie Ko
` (4 subsequent siblings)
7 siblings, 1 reply; 13+ messages in thread
From: Robbie Ko @ 2015-06-23 10:39 UTC (permalink / raw)
To: linux-btrfs; +Cc: Robbie Ko
There's one more case where we can't issue a rename operation
for a directory as soon as we process it. We move a directory
from ancestor to descendant.
|---- a
|---- b
|---- c
|---- d
"Move a directory from ancestor to descendant" means moving
dir. a into dir. c
This case will happen after applying "[PATCH] Btrfs: incremental
send, don't delay directory renames unnecessarily".
Because, that patch changes behavior of wait_for_parent_move function.
Example:
Parent snapshot:
|---- @tmp/ (ino 257)
|---- pre/ (ino 260)
|---- wait_dir (ino 261)
|---- ance/ (ino 263)
|---- wait_at_below_ance/ (ino 259)
|---- desc/ (ino 262)
|---- other_dir/ (ino 264)
Send snapshot:
|---- @tmp/ (ino 257)
|---- other_dir/ (ino 264)
|---- wait_at_below_ance/ (ino 259)
|---- pre/ (ino 260)
|---- wait_dir/ (ino 261)
|---- desc/ (ino 262)
|---- ance/ (ino 263)
1. 259 must move to @tmp/other_dir, so it is waiting on other_dir(264).
2. 260 is able to rename as ance/wait_at_below_ance/pre since
wait_at_below_ance(259) is waiting and 260 is not the ancestor
of wait_at_below_ance(259).
3. 261 must move to @tmp/other_dir, so it is waiting on other_dir(264).
4. 262 is able to rename as ance/wait_at_below_ance/pre/wait_dir/desc since
wait_dir(261) is waiting and 262 is not the ancestor of wait_dir(261).
5. 263 is rename as ance/wait_at_below_ance/pre/wait_dir/desc/ance since
wait_dir(261) is waiting and 263 is not the ancestor of wait_dir(261).
At the same time, receiving side will encounter error.
If anyone calls get_cur_path() to any element in
ance/wait_at_below_ance/pre/wait_dir/desc/ance like wait_dir(260),
there will cause path building loop like this : 261 -> 260 -> 259 ->
263 -> 262 -> 261
So fix the problem by check path_loop for this case.
Signed-off-by: Robbie Ko <robbieko@synology.com>
---
V3: add error handling and modify comment and coding style
fs/btrfs/send.c | 49 ++++++++++++++++++++++++++++++++++++++++++++++++-
1 file changed, 48 insertions(+), 1 deletion(-)
diff --git a/fs/btrfs/send.c b/fs/btrfs/send.c
index 95dc1d4..ca8cb87 100644
--- a/fs/btrfs/send.c
+++ b/fs/btrfs/send.c
@@ -3089,13 +3089,18 @@ static int path_loop(struct send_ctx *sctx, struct fs_path *name,
*ancestor_ino = 0;
while (ino != BTRFS_FIRST_FREE_OBJECTID) {
+ struct waiting_dir_move *wdm;
fs_path_reset(name);
if (is_waiting_for_rm(sctx, ino))
break;
- if (is_waiting_for_move(sctx, ino)) {
+
+ wdm = get_waiting_dir_move(sctx, ino);
+ if (wdm) {
if (*ancestor_ino == 0)
*ancestor_ino = ino;
+ if (wdm->orphanized)
+ break;
ret = get_first_ref(sctx->parent_root, ino,
&parent_inode, &parent_gen, name);
} else {
@@ -3748,6 +3753,48 @@ verbose_printk("btrfs: process_recorded_refs %llu\n", sctx->cur_ino);
}
/*
+ * need to check whether rename/move causes path loop.
+ * If it does, need to delay the rename of the current
+ * inode (sctx->cur_ino), then perform after the rename of
+ * its ancestor.
+ */
+ if (S_ISDIR(sctx->cur_inode_mode) &&
+ sctx->parent_root && can_rename) {
+ struct fs_path *name = NULL;
+ u64 ancestor;
+ u64 old_send_progress = sctx->send_progress;
+
+ name = fs_path_alloc();
+ if (!name) {
+ ret = -ENOMEM;
+ goto out;
+ }
+
+ sctx->send_progress = sctx->cur_ino + 1;
+ ret = path_loop(sctx, name, sctx->cur_ino,
+ sctx->cur_inode_gen, &ancestor);
+ if (ret) {
+ ret = add_pending_dir_move(sctx, sctx->cur_ino,
+ sctx->cur_inode_gen,
+ ancestor,
+ &sctx->new_refs,
+ &sctx->deleted_refs,
+ is_orphan);
+ if (ret < 0) {
+ sctx->send_progress = old_send_progress;
+ fs_path_free(name);
+ goto out;
+ }
+ can_rename = false;
+ *pending_move = 1;
+ }
+ sctx->send_progress = old_send_progress;
+ fs_path_free(name);
+ if (ret < 0)
+ goto out;
+ }
+
+ /*
* link/move the ref to the new place. If we have an orphan
* inode, move it and update valid_path. If not, link or move
* it depending on the inode mode.
--
1.9.1
^ permalink raw reply related [flat|nested] 13+ messages in thread* Re: [PATCH v3 3/7] Btrfs: incremental send, avoid ancestor rename to descendant
2015-06-23 10:39 ` [PATCH v3 3/7] Btrfs: incremental send, avoid ancestor rename to descendant Robbie Ko
@ 2015-06-23 15:05 ` Filipe David Manana
0 siblings, 0 replies; 13+ messages in thread
From: Filipe David Manana @ 2015-06-23 15:05 UTC (permalink / raw)
To: Robbie Ko; +Cc: linux-btrfs@vger.kernel.org
On Tue, Jun 23, 2015 at 11:39 AM, Robbie Ko <robbieko@synology.com> wrote:
> There's one more case where we can't issue a rename operation
> for a directory as soon as we process it. We move a directory
> from ancestor to descendant.
>
> |---- a
> |---- b
> |---- c
> |---- d
> "Move a directory from ancestor to descendant" means moving
> dir. a into dir. c
>
> This case will happen after applying "[PATCH] Btrfs: incremental
> send, don't delay directory renames unnecessarily".
> Because, that patch changes behavior of wait_for_parent_move function.
>
> Example:
> Parent snapshot:
> |---- @tmp/ (ino 257)
> |---- pre/ (ino 260)
> |---- wait_dir (ino 261)
> |---- ance/ (ino 263)
> |---- wait_at_below_ance/ (ino 259)
> |---- desc/ (ino 262)
> |---- other_dir/ (ino 264)
>
> Send snapshot:
> |---- @tmp/ (ino 257)
> |---- other_dir/ (ino 264)
> |---- wait_at_below_ance/ (ino 259)
> |---- pre/ (ino 260)
> |---- wait_dir/ (ino 261)
> |---- desc/ (ino 262)
> |---- ance/ (ino 263)
>
> 1. 259 must move to @tmp/other_dir, so it is waiting on other_dir(264).
>
> 2. 260 is able to rename as ance/wait_at_below_ance/pre since
> wait_at_below_ance(259) is waiting and 260 is not the ancestor
> of wait_at_below_ance(259).
>
> 3. 261 must move to @tmp/other_dir, so it is waiting on other_dir(264).
>
> 4. 262 is able to rename as ance/wait_at_below_ance/pre/wait_dir/desc since
> wait_dir(261) is waiting and 262 is not the ancestor of wait_dir(261).
>
> 5. 263 is rename as ance/wait_at_below_ance/pre/wait_dir/desc/ance since
> wait_dir(261) is waiting and 263 is not the ancestor of wait_dir(261).
> At the same time, receiving side will encounter error.
> If anyone calls get_cur_path() to any element in
> ance/wait_at_below_ance/pre/wait_dir/desc/ance like wait_dir(260),
> there will cause path building loop like this : 261 -> 260 -> 259 ->
> 263 -> 262 -> 261
>
> So fix the problem by check path_loop for this case.
>
> Signed-off-by: Robbie Ko <robbieko@synology.com>
> ---
>
> V3: add error handling and modify comment and coding style
>
> fs/btrfs/send.c | 49 ++++++++++++++++++++++++++++++++++++++++++++++++-
> 1 file changed, 48 insertions(+), 1 deletion(-)
>
> diff --git a/fs/btrfs/send.c b/fs/btrfs/send.c
> index 95dc1d4..ca8cb87 100644
> --- a/fs/btrfs/send.c
> +++ b/fs/btrfs/send.c
> @@ -3089,13 +3089,18 @@ static int path_loop(struct send_ctx *sctx, struct fs_path *name,
>
> *ancestor_ino = 0;
> while (ino != BTRFS_FIRST_FREE_OBJECTID) {
> + struct waiting_dir_move *wdm;
> fs_path_reset(name);
>
> if (is_waiting_for_rm(sctx, ino))
> break;
> - if (is_waiting_for_move(sctx, ino)) {
> +
> + wdm = get_waiting_dir_move(sctx, ino);
> + if (wdm) {
> if (*ancestor_ino == 0)
> *ancestor_ino = ino;
> + if (wdm->orphanized)
> + break;
> ret = get_first_ref(sctx->parent_root, ino,
> &parent_inode, &parent_gen, name);
> } else {
> @@ -3748,6 +3753,48 @@ verbose_printk("btrfs: process_recorded_refs %llu\n", sctx->cur_ino);
> }
>
> /*
> + * need to check whether rename/move causes path loop.
> + * If it does, need to delay the rename of the current
> + * inode (sctx->cur_ino), then perform after the rename of
> + * its ancestor.
> + */
Well the comment says only what the code below does, not why. We can
see that it calls path_loop() and if it returns true, delays the
rename of the current inode to happen after the rename of the ancestor
inode that path_loop() finds.
We should either have the comment say why this is done or simply
remove it... Having a comment that doesn't bring any value is the same
as not having it in the first place, explaining the "why" is the
important part.
> + if (S_ISDIR(sctx->cur_inode_mode) &&
> + sctx->parent_root && can_rename) {
> + struct fs_path *name = NULL;
> + u64 ancestor;
> + u64 old_send_progress = sctx->send_progress;
> +
> + name = fs_path_alloc();
> + if (!name) {
> + ret = -ENOMEM;
> + goto out;
> + }
> +
> + sctx->send_progress = sctx->cur_ino + 1;
> + ret = path_loop(sctx, name, sctx->cur_ino,
> + sctx->cur_inode_gen, &ancestor);
> + if (ret) {
> + ret = add_pending_dir_move(sctx, sctx->cur_ino,
> + sctx->cur_inode_gen,
> + ancestor,
> + &sctx->new_refs,
> + &sctx->deleted_refs,
> + is_orphan);
> + if (ret < 0) {
> + sctx->send_progress = old_send_progress;
> + fs_path_free(name);
> + goto out;
> + }
> + can_rename = false;
> + *pending_move = 1;
> + }
> + sctx->send_progress = old_send_progress;
> + fs_path_free(name);
> + if (ret < 0)
> + goto out;
This check for ret < 0 is useless here. The former check "if (ret) {
..." will clobber it. Either do this check before the other one or
make the other check as "if (ret == 1) { ...". In other words, we're
still ignoring errors (return value < 0) from path_loop().
> + }
> +
> + /*
> * link/move the ref to the new place. If we have an orphan
> * inode, move it and update valid_path. If not, link or move
> * it depending on the inode mode.
> --
> 1.9.1
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at http://vger.kernel.org/majordomo-info.html
--
Filipe David Manana,
"Reasonable men adapt themselves to the world.
Unreasonable men adapt the world to themselves.
That's why all progress depends on unreasonable men."
^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH v3 4/7] Btrfs: incremental send, fix orphan_dir_info leak
2015-06-23 10:39 [PATCH v3 0/7] Btrfs incremental send fix serval case for rename and rm directory Robbie Ko
` (2 preceding siblings ...)
2015-06-23 10:39 ` [PATCH v3 3/7] Btrfs: incremental send, avoid ancestor rename to descendant Robbie Ko
@ 2015-06-23 10:39 ` Robbie Ko
2015-06-23 10:39 ` [PATCH v3 5/7] Btrfs: incremental send, fix rmdir but dir have a unprocess item Robbie Ko
` (3 subsequent siblings)
7 siblings, 0 replies; 13+ messages in thread
From: Robbie Ko @ 2015-06-23 10:39 UTC (permalink / raw)
To: linux-btrfs; +Cc: Robbie Ko
There's one case where we leak a orphan_dir_info structure.
Example:
Parent snapshot:
|---- a/ (ino 279)
|---- c (ino 282)
|---- del/ (ino 281)
|---- tmp/ (ino 280)
|---- long/ (ino 283)
|---- longlong/ (ino 284)
Send snapshot:
|---- a/ (ino 279)
|---- long (ino 283)
|---- longlong (ino 284)
|---- c/ (ino 282)
|---- tmp/ (ino 280)
Freeing an existing orphan_dir_info for a directory, when we realize
we can't rmdir the directory because it has a descendant that wasn't
yet processed, and the orphan_dir_info was created because it had a
descendant that had its rename operation delayed.
Signed-off-by: Robbie Ko <robbieko@synology.com>
---
fs/btrfs/send.c | 5 +++++
1 file changed, 5 insertions(+)
diff --git a/fs/btrfs/send.c b/fs/btrfs/send.c
index ca8cb87..194df76 100644
--- a/fs/btrfs/send.c
+++ b/fs/btrfs/send.c
@@ -2914,6 +2914,11 @@ static int can_rmdir(struct send_ctx *sctx, u64 dir, u64 dir_gen,
}
if (loc.objectid > send_progress) {
+ struct orphan_dir_info *odi;
+
+ odi = get_orphan_dir_info(sctx, dir);
+ if (odi)
+ free_orphan_dir_info(sctx, odi);
ret = 0;
goto out;
}
--
1.9.1
^ permalink raw reply related [flat|nested] 13+ messages in thread* [PATCH v3 5/7] Btrfs: incremental send, fix rmdir but dir have a unprocess item
2015-06-23 10:39 [PATCH v3 0/7] Btrfs incremental send fix serval case for rename and rm directory Robbie Ko
` (3 preceding siblings ...)
2015-06-23 10:39 ` [PATCH v3 4/7] Btrfs: incremental send, fix orphan_dir_info leak Robbie Ko
@ 2015-06-23 10:39 ` Robbie Ko
2015-06-23 10:39 ` [PATCH v3 6/7] Btrfs: incremental send, don't send utimes for non-existing directory Robbie Ko
` (2 subsequent siblings)
7 siblings, 0 replies; 13+ messages in thread
From: Robbie Ko @ 2015-06-23 10:39 UTC (permalink / raw)
To: linux-btrfs; +Cc: Robbie Ko
There's one case where we attempt to rmdir a directory prematurely.
Example:
Parent snapshot:
|---- a/ (ino 279)
|---- c (ino 282)
|---- del/ (ino 281)
|---- tmp/ (ino 280)
|---- long/ (ino 283)
Send snapshot:
|---- a/ (ino 279)
|---- long (ino 283)
|---- c/ (ino 282)
|---- tmp/ (ino 280)
While process inode 281, since inode 280 is waiting for inode 282,
rmdir_ino of struct waitng_dir_move for inode 280 will assigned to 281
and an orphan_dir_info will be created for node 281 in can_rmdir().
Such that, when process inode 282, we will do following steps.
First, move inode 282 from a/c to c
Second, move inode 280 from del/tmp to c/tmp
Third, try to remove inode 281
In Third step, we pass 283 (sctx->cur_ino + 1) as the send_progress to the
can_rmdir() function and that makes it return true when it shouldn't,
because the inode 283 wasn't processed yet and it's still a child of
the directory with inode number 281, which makes the receiver run into
an ENOTEMPTY error when attempting to remove the directory.
Signed-off-by: Robbie Ko <robbieko@synology.com>
---
fs/btrfs/send.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/fs/btrfs/send.c b/fs/btrfs/send.c
index 194df76..838abf4 100644
--- a/fs/btrfs/send.c
+++ b/fs/btrfs/send.c
@@ -3211,7 +3211,7 @@ static int apply_dir_move(struct send_ctx *sctx, struct pending_dir_move *pm)
/* already deleted */
goto finish;
}
- ret = can_rmdir(sctx, rmdir_ino, odi->gen, sctx->cur_ino + 1);
+ ret = can_rmdir(sctx, rmdir_ino, odi->gen, sctx->cur_ino);
if (ret < 0)
goto out;
if (!ret)
--
1.9.1
^ permalink raw reply related [flat|nested] 13+ messages in thread* [PATCH v3 6/7] Btrfs: incremental send, don't send utimes for non-existing directory
2015-06-23 10:39 [PATCH v3 0/7] Btrfs incremental send fix serval case for rename and rm directory Robbie Ko
` (4 preceding siblings ...)
2015-06-23 10:39 ` [PATCH v3 5/7] Btrfs: incremental send, fix rmdir but dir have a unprocess item Robbie Ko
@ 2015-06-23 10:39 ` Robbie Ko
2015-06-23 10:39 ` [PATCH v3 7/7] Btrfs: incremental send, avoid the overhead of allocating an orphan_dir_info object unnecessarily Robbie Ko
2015-06-23 15:35 ` [PATCH v3 0/7] Btrfs incremental send fix serval case for rename and rm directory Filipe David Manana
7 siblings, 0 replies; 13+ messages in thread
From: Robbie Ko @ 2015-06-23 10:39 UTC (permalink / raw)
To: linux-btrfs; +Cc: Robbie Ko
There's one where we attempt to get utimes from a directory that
doesn't exist in the send snapshot.
Example:
Parent snapshot:
|---- a/ (ino 259)
|---- c (ino 264)
|---- b/ (ino 260)
|---- d (ino 265)
|---- del/ (ino 263)
|---- item1/ (ino 261)
|---- item2/ (ino 262)
Send snapshot:
|---- a/ (ino 259)
|---- b/ (ino 260)
|---- c/ (ino 264)
|---- item2 (ino 262)
|---- d/ (ino 265)
|---- item1/ (ino 261)
First, 261 can't move to d/item1 without the rename of inode 265.
So as 262. Thus 261 and 262 need to wait for rename.
Second, since 263 will be deleted and there are two waiting
sub-directory 261 and 262, rmdir_ino of 261 will set to 263 and
rmdir_ino of 262 is not set. If 262 is processed earlier than 261,
utime of both 263 and 264 will be updated. However, 263 should not
update since it will vanish.
We're trying to send utimes for a directory/inode that doesn't exist
in the send snapshot. That send_utimes() will use part of a leaf
beyond its boundaries or a wrong slot (belonging to some other
unrelated inode), because btrfs_search_slot() returns 1 when we call
it to find the inode item to extract a utimes value from, and
send_utimes() is not prepared to deal with such case because it
assumes no one calls it for an inode that doesn't exist in the send
root. And that we fix the problem in the offending caller.
Signed-off-by: Robbie Ko <robbieko@synology.com>
---
V3:modify comment
fs/btrfs/send.c | 12 +++++++++++-
1 file changed, 11 insertions(+), 1 deletion(-)
diff --git a/fs/btrfs/send.c b/fs/btrfs/send.c
index 838abf4..dcf384d 100644
--- a/fs/btrfs/send.c
+++ b/fs/btrfs/send.c
@@ -3241,8 +3241,18 @@ finish:
* and old parent(s).
*/
list_for_each_entry(cur, &pm->update_refs, list) {
- if (cur->dir == rmdir_ino)
+ /*
+ * don't send utimes for non-existing directory
+ */
+ ret = get_inode_info(sctx->send_root, cur->dir, NULL,
+ NULL, NULL, NULL, NULL, NULL);
+ if (ret == -ENOENT) {
+ ret = 0;
continue;
+ }
+ if (ret < 0)
+ goto out;
+
ret = send_utimes(sctx, cur->dir, cur->dir_gen);
if (ret < 0)
goto out;
--
1.9.1
^ permalink raw reply related [flat|nested] 13+ messages in thread* [PATCH v3 7/7] Btrfs: incremental send, avoid the overhead of allocating an orphan_dir_info object unnecessarily
2015-06-23 10:39 [PATCH v3 0/7] Btrfs incremental send fix serval case for rename and rm directory Robbie Ko
` (5 preceding siblings ...)
2015-06-23 10:39 ` [PATCH v3 6/7] Btrfs: incremental send, don't send utimes for non-existing directory Robbie Ko
@ 2015-06-23 10:39 ` Robbie Ko
2015-06-23 14:52 ` David Sterba
2015-06-23 15:35 ` [PATCH v3 0/7] Btrfs incremental send fix serval case for rename and rm directory Filipe David Manana
7 siblings, 1 reply; 13+ messages in thread
From: Robbie Ko @ 2015-06-23 10:39 UTC (permalink / raw)
To: linux-btrfs; +Cc: Robbie Ko
Avoid the overhead of allocating an orphan_dir_info object unnecessarily.
Signed-off-by: Robbie Ko <robbieko@synology.com>
---
fs/btrfs/send.c | 13 ++++++-------
1 file changed, 6 insertions(+), 7 deletions(-)
diff --git a/fs/btrfs/send.c b/fs/btrfs/send.c
index dcf384d..7c61365 100644
--- a/fs/btrfs/send.c
+++ b/fs/btrfs/send.c
@@ -2786,12 +2786,6 @@ add_orphan_dir_info(struct send_ctx *sctx, u64 dir_ino)
struct rb_node *parent = NULL;
struct orphan_dir_info *entry, *odi;
- odi = kmalloc(sizeof(*odi), GFP_NOFS);
- if (!odi)
- return ERR_PTR(-ENOMEM);
- odi->ino = dir_ino;
- odi->gen = 0;
-
while (*p) {
parent = *p;
entry = rb_entry(parent, struct orphan_dir_info, node);
@@ -2800,11 +2794,16 @@ add_orphan_dir_info(struct send_ctx *sctx, u64 dir_ino)
} else if (dir_ino > entry->ino) {
p = &(*p)->rb_right;
} else {
- kfree(odi);
return entry;
}
}
+ odi = kmalloc(sizeof(*odi), GFP_NOFS);
+ if (!odi)
+ return ERR_PTR(-ENOMEM);
+ odi->ino = dir_ino;
+ odi->gen = 0;
+
rb_link_node(&odi->node, parent, p);
rb_insert_color(&odi->node, &sctx->orphan_dirs);
return odi;
--
1.9.1
^ permalink raw reply related [flat|nested] 13+ messages in thread* Re: [PATCH v3 0/7] Btrfs incremental send fix serval case for rename and rm directory
2015-06-23 10:39 [PATCH v3 0/7] Btrfs incremental send fix serval case for rename and rm directory Robbie Ko
` (6 preceding siblings ...)
2015-06-23 10:39 ` [PATCH v3 7/7] Btrfs: incremental send, avoid the overhead of allocating an orphan_dir_info object unnecessarily Robbie Ko
@ 2015-06-23 15:35 ` Filipe David Manana
7 siblings, 0 replies; 13+ messages in thread
From: Filipe David Manana @ 2015-06-23 15:35 UTC (permalink / raw)
To: Robbie Ko; +Cc: linux-btrfs@vger.kernel.org
On Tue, Jun 23, 2015 at 11:39 AM, Robbie Ko <robbieko@synology.com> wrote:
> Patch for fix btrfs send receive. These patches base on v4.1
> plus following patches.
> [PATCH] Btrfs: incremental send, don't delay directory renames unnecessarily
> [PATCH] Btrfs: incremental send, check if orphanized dir inode needs delayed rename
>
> Thanks.
>
> Robbie Ko (7):
> Revert "Btrfs: incremental send, remove dead code"
> Btrfs: incremental send, avoid circular waiting and descendant
> overwrite ancestor need to update path
> Btrfs: incremental send, avoid ancestor rename to descendant
> Btrfs: incremental send, fix orphan_dir_info leak
> Btrfs: incremental send, fix rmdir but dir have a unprocess item
> Btrfs: incremental send, don't send utimes for non-existing directory
> Btrfs: incremental send, avoid the overhead of allocating an
> orphan_dir_info object unnecessarily
Robbie,
Are you considering sending test cases for fstests for the patches 2
(all 3 examples in the commit message), 3 and 5?
Let me know if you want any assistance making those tests.
Thanks.
>
> fs/btrfs/send.c | 179 +++++++++++++++++++++++++++++++++++++++++++++++++++-----
> 1 file changed, 165 insertions(+), 14 deletions(-)
>
> --
> 1.9.1
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at http://vger.kernel.org/majordomo-info.html
--
Filipe David Manana,
"Reasonable men adapt themselves to the world.
Unreasonable men adapt the world to themselves.
That's why all progress depends on unreasonable men."
^ permalink raw reply [flat|nested] 13+ messages in thread