[PATCH v2 0/2] btrfs :incremental send, improve rmdir performance

[PATCH v2 0/2] btrfs :incremental send, improve rmdir performance

[robbieko]

From: Robbie Ko <robbieko@synology.com>

The following patch is to improve the btrfs send, the speed of large
directory deletion.

1. Optimization, avoid unnecessary allocations.

2. Increase the speed of can_rmdir.

Robbie Ko (2):
  btrfs: incremental send, optimization add orphan_dir_info
  btrfs: incremental send, improve rmdir performance for large directory

 fs/btrfs/send.c | 44 ++++++++++++++++++++++++++++----------------
 1 file changed, 28 insertions(+), 16 deletions(-)

-- 
1.9.1

[PATCH v2 1/2] btrfs: incremental send, optimization add orphan_dir_info

[robbieko]

From: Robbie Ko <robbieko@synology.com>

moving the allocation to the end in order to avoid unnecessary
allocations

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 484e2af..2830871 100644
--- a/fs/btrfs/send.c
+++ b/fs/btrfs/send.c
@@ -2855,12 +2855,6 @@ static int orphanize_inode(struct send_ctx *sctx, u64 ino, u64 gen,
 	struct rb_node *parent = NULL;
 	struct orphan_dir_info *entry, *odi;
 
-	odi = kmalloc(sizeof(*odi), GFP_KERNEL);
-	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);
@@ -2869,11 +2863,16 @@ static int orphanize_inode(struct send_ctx *sctx, u64 ino, u64 gen,
 		} else if (dir_ino > entry->ino) {
 			p = &(*p)->rb_right;
 		} else {
-			kfree(odi);
 			return entry;
 		}
 	}
 
+	odi = kmalloc(sizeof(*odi), GFP_KERNEL);
+	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

Re: [PATCH v2 1/2] btrfs: incremental send, optimization add orphan_dir_info

[Filipe Manana]

On Tue, May 8, 2018 at 11:11 AM, robbieko <robbieko@synology.com> wrote:
> From: Robbie Ko <robbieko@synology.com>
>
> moving the allocation to the end in order to avoid unnecessary
> allocations
>
> Signed-off-by: Robbie Ko <robbieko@synology.com>
Reviewed-by: Filipe Manana <fdmanana@suse.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 484e2af..2830871 100644
> --- a/fs/btrfs/send.c
> +++ b/fs/btrfs/send.c
> @@ -2855,12 +2855,6 @@ static int orphanize_inode(struct send_ctx *sctx, u64 ino, u64 gen,
>         struct rb_node *parent = NULL;
>         struct orphan_dir_info *entry, *odi;
>
> -       odi = kmalloc(sizeof(*odi), GFP_KERNEL);
> -       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);
> @@ -2869,11 +2863,16 @@ static int orphanize_inode(struct send_ctx *sctx, u64 ino, u64 gen,
>                 } else if (dir_ino > entry->ino) {
>                         p = &(*p)->rb_right;
>                 } else {
> -                       kfree(odi);
>                         return entry;
>                 }
>         }
>
> +       odi = kmalloc(sizeof(*odi), GFP_KERNEL);
> +       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
>
> --
> 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,

“Whether you think you can, or you think you can't — you're right.”

[PATCH v2 2/2] btrfs: incremental send, improve rmdir performance for large directory

[robbieko]

From: Robbie Ko <robbieko@synology.com>

Currently when checking if we can delete a directory, we always
check if all its children have been processed.

Example: A directory with 2,000,000 files was deleted
Result:
original : 1994m57.071s
patch : 1m38.554s

[FIX]
Instead of checking all children on all calls to can_rmdir(),
we keep track of the directory index offset of the child last
checked in the last call to can_rmdir(), and then use it as the
starting point for future calls to can_rmdir().

Signed-off-by: Robbie Ko <robbieko@synology.com>
---
V2:
 fix comments
 split optimization allocations orphan_dir_info

 fs/btrfs/send.c | 31 ++++++++++++++++++++++---------
 1 file changed, 22 insertions(+), 9 deletions(-)

diff --git a/fs/btrfs/send.c b/fs/btrfs/send.c
index 2830871..a477268 100644
--- a/fs/btrfs/send.c
+++ b/fs/btrfs/send.c
@@ -247,6 +247,7 @@ struct orphan_dir_info {
 	struct rb_node node;
 	u64 ino;
 	u64 gen;
+	u64 last_dir_index_offset;
 };
 
 struct name_cache_entry {
@@ -2872,6 +2873,7 @@ static int orphanize_inode(struct send_ctx *sctx, u64 ino, u64 gen,
 		return ERR_PTR(-ENOMEM);
 	odi->ino = dir_ino;
 	odi->gen = 0;
+	odi->last_dir_index_offset = 0;
 
 	rb_link_node(&odi->node, parent, p);
 	rb_insert_color(&odi->node, &sctx->orphan_dirs);
@@ -2927,6 +2929,7 @@ static int can_rmdir(struct send_ctx *sctx, u64 dir, u64 dir_gen,
 	struct btrfs_key found_key;
 	struct btrfs_key loc;
 	struct btrfs_dir_item *di;
+	struct orphan_dir_info *odi = NULL;
 
 	/*
 	 * Don't try to rmdir the top/root subvolume dir.
@@ -2941,6 +2944,11 @@ static int can_rmdir(struct send_ctx *sctx, u64 dir, u64 dir_gen,
 	key.objectid = dir;
 	key.type = BTRFS_DIR_INDEX_KEY;
 	key.offset = 0;
+
+	odi = get_orphan_dir_info(sctx, dir);
+	if (odi)
+		key.offset = odi->last_dir_index_offset;
+
 	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 	if (ret < 0)
 		goto out;
@@ -2968,30 +2976,33 @@ static int can_rmdir(struct send_ctx *sctx, u64 dir, u64 dir_gen,
 
 		dm = get_waiting_dir_move(sctx, loc.objectid);
 		if (dm) {
-			struct orphan_dir_info *odi;
-
 			odi = add_orphan_dir_info(sctx, dir);
 			if (IS_ERR(odi)) {
 				ret = PTR_ERR(odi);
 				goto out;
 			}
 			odi->gen = dir_gen;
+			odi->last_dir_index_offset = found_key.offset;
 			dm->rmdir_ino = dir;
 			ret = 0;
 			goto out;
 		}
 
 		if (loc.objectid > send_progress) {
-			struct orphan_dir_info *odi;
-
-			odi = get_orphan_dir_info(sctx, dir);
-			free_orphan_dir_info(sctx, odi);
+			odi = add_orphan_dir_info(sctx, dir);
+			if (IS_ERR(odi)) {
+				ret = PTR_ERR(odi);
+				goto out;
+			}
+			odi->gen = dir_gen;
+			odi->last_dir_index_offset = found_key.offset;
 			ret = 0;
 			goto out;
 		}
 
 		path->slots[0]++;
 	}
+	free_orphan_dir_info(sctx, odi);
 
 	ret = 1;
 
@@ -3269,13 +3280,16 @@ static int apply_dir_move(struct send_ctx *sctx, struct pending_dir_move *pm)
 
 	if (rmdir_ino) {
 		struct orphan_dir_info *odi;
+		u64 gen;
 
 		odi = get_orphan_dir_info(sctx, rmdir_ino);
 		if (!odi) {
 			/* already deleted */
 			goto finish;
 		}
-		ret = can_rmdir(sctx, rmdir_ino, odi->gen, sctx->cur_ino);
+		gen = odi->gen;
+
+		ret = can_rmdir(sctx, rmdir_ino, gen, sctx->cur_ino);
 		if (ret < 0)
 			goto out;
 		if (!ret)
@@ -3286,13 +3300,12 @@ static int apply_dir_move(struct send_ctx *sctx, struct pending_dir_move *pm)
 			ret = -ENOMEM;
 			goto out;
 		}
-		ret = get_cur_path(sctx, rmdir_ino, odi->gen, name);
+		ret = get_cur_path(sctx, rmdir_ino, gen, name);
 		if (ret < 0)
 			goto out;
 		ret = send_rmdir(sctx, name);
 		if (ret < 0)
 			goto out;
-		free_orphan_dir_info(sctx, odi);
 	}
 
 finish:
-- 
1.9.1

Re: [PATCH v2 2/2] btrfs: incremental send, improve rmdir performance for large directory

[Filipe Manana]

On Tue, May 8, 2018 at 11:11 AM, robbieko <robbieko@synology.com> wrote:
> From: Robbie Ko <robbieko@synology.com>
>
> Currently when checking if we can delete a directory, we always
> check if all its children have been processed.
>
> Example: A directory with 2,000,000 files was deleted
> Result:
> original : 1994m57.071s
> patch : 1m38.554s
>
> [FIX]
> Instead of checking all children on all calls to can_rmdir(),
> we keep track of the directory index offset of the child last
> checked in the last call to can_rmdir(), and then use it as the
> starting point for future calls to can_rmdir().
>
> Signed-off-by: Robbie Ko <robbieko@synology.com>
Reviewed-by: Filipe Manana <fdmanana@suse.com>

> ---
> V2:
>  fix comments
>  split optimization allocations orphan_dir_info
>
>  fs/btrfs/send.c | 31 ++++++++++++++++++++++---------
>  1 file changed, 22 insertions(+), 9 deletions(-)
>
> diff --git a/fs/btrfs/send.c b/fs/btrfs/send.c
> index 2830871..a477268 100644
> --- a/fs/btrfs/send.c
> +++ b/fs/btrfs/send.c
> @@ -247,6 +247,7 @@ struct orphan_dir_info {
>         struct rb_node node;
>         u64 ino;
>         u64 gen;
> +       u64 last_dir_index_offset;
>  };
>
>  struct name_cache_entry {
> @@ -2872,6 +2873,7 @@ static int orphanize_inode(struct send_ctx *sctx, u64 ino, u64 gen,
>                 return ERR_PTR(-ENOMEM);
>         odi->ino = dir_ino;
>         odi->gen = 0;
> +       odi->last_dir_index_offset = 0;
>
>         rb_link_node(&odi->node, parent, p);
>         rb_insert_color(&odi->node, &sctx->orphan_dirs);
> @@ -2927,6 +2929,7 @@ static int can_rmdir(struct send_ctx *sctx, u64 dir, u64 dir_gen,
>         struct btrfs_key found_key;
>         struct btrfs_key loc;
>         struct btrfs_dir_item *di;
> +       struct orphan_dir_info *odi = NULL;
>
>         /*
>          * Don't try to rmdir the top/root subvolume dir.
> @@ -2941,6 +2944,11 @@ static int can_rmdir(struct send_ctx *sctx, u64 dir, u64 dir_gen,
>         key.objectid = dir;
>         key.type = BTRFS_DIR_INDEX_KEY;
>         key.offset = 0;
> +
> +       odi = get_orphan_dir_info(sctx, dir);
> +       if (odi)
> +               key.offset = odi->last_dir_index_offset;
> +
>         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
>         if (ret < 0)
>                 goto out;
> @@ -2968,30 +2976,33 @@ static int can_rmdir(struct send_ctx *sctx, u64 dir, u64 dir_gen,
>
>                 dm = get_waiting_dir_move(sctx, loc.objectid);
>                 if (dm) {
> -                       struct orphan_dir_info *odi;
> -
>                         odi = add_orphan_dir_info(sctx, dir);
>                         if (IS_ERR(odi)) {
>                                 ret = PTR_ERR(odi);
>                                 goto out;
>                         }
>                         odi->gen = dir_gen;
> +                       odi->last_dir_index_offset = found_key.offset;
>                         dm->rmdir_ino = dir;
>                         ret = 0;
>                         goto out;
>                 }
>
>                 if (loc.objectid > send_progress) {
> -                       struct orphan_dir_info *odi;
> -
> -                       odi = get_orphan_dir_info(sctx, dir);
> -                       free_orphan_dir_info(sctx, odi);
> +                       odi = add_orphan_dir_info(sctx, dir);
> +                       if (IS_ERR(odi)) {
> +                               ret = PTR_ERR(odi);
> +                               goto out;
> +                       }
> +                       odi->gen = dir_gen;
> +                       odi->last_dir_index_offset = found_key.offset;
>                         ret = 0;
>                         goto out;
>                 }
>
>                 path->slots[0]++;
>         }
> +       free_orphan_dir_info(sctx, odi);
>
>         ret = 1;
>
> @@ -3269,13 +3280,16 @@ static int apply_dir_move(struct send_ctx *sctx, struct pending_dir_move *pm)
>
>         if (rmdir_ino) {
>                 struct orphan_dir_info *odi;
> +               u64 gen;
>
>                 odi = get_orphan_dir_info(sctx, rmdir_ino);
>                 if (!odi) {
>                         /* already deleted */
>                         goto finish;
>                 }
> -               ret = can_rmdir(sctx, rmdir_ino, odi->gen, sctx->cur_ino);
> +               gen = odi->gen;
> +
> +               ret = can_rmdir(sctx, rmdir_ino, gen, sctx->cur_ino);
>                 if (ret < 0)
>                         goto out;
>                 if (!ret)
> @@ -3286,13 +3300,12 @@ static int apply_dir_move(struct send_ctx *sctx, struct pending_dir_move *pm)
>                         ret = -ENOMEM;
>                         goto out;
>                 }
> -               ret = get_cur_path(sctx, rmdir_ino, odi->gen, name);
> +               ret = get_cur_path(sctx, rmdir_ino, gen, name);
>                 if (ret < 0)
>                         goto out;
>                 ret = send_rmdir(sctx, name);
>                 if (ret < 0)
>                         goto out;
> -               free_orphan_dir_info(sctx, odi);
>         }
>
>  finish:
> --
> 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,

“Whether you think you can, or you think you can't — you're right.”

Re: [PATCH v2 0/2] btrfs :incremental send, improve rmdir performance

[David Sterba]

On Tue, May 08, 2018 at 06:11:36PM +0800, robbieko wrote:
> From: Robbie Ko <robbieko@synology.com>
> 
> The following patch is to improve the btrfs send, the speed of large
> directory deletion.
> 
> 1. Optimization, avoid unnecessary allocations.
> 
> 2. Increase the speed of can_rmdir.
> 
> Robbie Ko (2):
>   btrfs: incremental send, optimization add orphan_dir_info
>   btrfs: incremental send, improve rmdir performance for large directory

Added to next, thanks. I've updated the changelogs a bit.