* [PATCH v2 0/2] btrfs :incremental send, improve rmdir performance
@ 2018-05-08 10:11 robbieko
2018-05-08 10:11 ` [PATCH v2 1/2] btrfs: incremental send, optimization add orphan_dir_info robbieko
` (2 more replies)
0 siblings, 3 replies; 6+ messages in thread
From: robbieko @ 2018-05-08 10:11 UTC (permalink / raw)
To: linux-btrfs; +Cc: Robbie Ko
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
^ permalink raw reply [flat|nested] 6+ messages in thread
* [PATCH v2 1/2] btrfs: incremental send, optimization add orphan_dir_info
2018-05-08 10:11 [PATCH v2 0/2] btrfs :incremental send, improve rmdir performance robbieko
@ 2018-05-08 10:11 ` robbieko
2018-05-08 19:04 ` Filipe Manana
2018-05-08 10:11 ` [PATCH v2 2/2] btrfs: incremental send, improve rmdir performance for large directory robbieko
2018-05-09 10:21 ` [PATCH v2 0/2] btrfs :incremental send, improve rmdir performance David Sterba
2 siblings, 1 reply; 6+ messages in thread
From: robbieko @ 2018-05-08 10:11 UTC (permalink / raw)
To: linux-btrfs; +Cc: Robbie Ko
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
^ permalink raw reply related [flat|nested] 6+ messages in thread
* [PATCH v2 2/2] btrfs: incremental send, improve rmdir performance for large directory
2018-05-08 10:11 [PATCH v2 0/2] btrfs :incremental send, improve rmdir performance robbieko
2018-05-08 10:11 ` [PATCH v2 1/2] btrfs: incremental send, optimization add orphan_dir_info robbieko
@ 2018-05-08 10:11 ` robbieko
2018-05-08 19:05 ` Filipe Manana
2018-05-09 10:21 ` [PATCH v2 0/2] btrfs :incremental send, improve rmdir performance David Sterba
2 siblings, 1 reply; 6+ messages in thread
From: robbieko @ 2018-05-08 10:11 UTC (permalink / raw)
To: linux-btrfs; +Cc: Robbie Ko
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
^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [PATCH v2 1/2] btrfs: incremental send, optimization add orphan_dir_info
2018-05-08 10:11 ` [PATCH v2 1/2] btrfs: incremental send, optimization add orphan_dir_info robbieko
@ 2018-05-08 19:04 ` Filipe Manana
0 siblings, 0 replies; 6+ messages in thread
From: Filipe Manana @ 2018-05-08 19:04 UTC (permalink / raw)
To: robbieko; +Cc: linux-btrfs
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.”
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH v2 2/2] btrfs: incremental send, improve rmdir performance for large directory
2018-05-08 10:11 ` [PATCH v2 2/2] btrfs: incremental send, improve rmdir performance for large directory robbieko
@ 2018-05-08 19:05 ` Filipe Manana
0 siblings, 0 replies; 6+ messages in thread
From: Filipe Manana @ 2018-05-08 19:05 UTC (permalink / raw)
To: robbieko; +Cc: linux-btrfs
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.”
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH v2 0/2] btrfs :incremental send, improve rmdir performance
2018-05-08 10:11 [PATCH v2 0/2] btrfs :incremental send, improve rmdir performance robbieko
2018-05-08 10:11 ` [PATCH v2 1/2] btrfs: incremental send, optimization add orphan_dir_info robbieko
2018-05-08 10:11 ` [PATCH v2 2/2] btrfs: incremental send, improve rmdir performance for large directory robbieko
@ 2018-05-09 10:21 ` David Sterba
2 siblings, 0 replies; 6+ messages in thread
From: David Sterba @ 2018-05-09 10:21 UTC (permalink / raw)
To: robbieko; +Cc: linux-btrfs
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.
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2018-05-09 10:23 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-05-08 10:11 [PATCH v2 0/2] btrfs :incremental send, improve rmdir performance robbieko
2018-05-08 10:11 ` [PATCH v2 1/2] btrfs: incremental send, optimization add orphan_dir_info robbieko
2018-05-08 19:04 ` Filipe Manana
2018-05-08 10:11 ` [PATCH v2 2/2] btrfs: incremental send, improve rmdir performance for large directory robbieko
2018-05-08 19:05 ` Filipe Manana
2018-05-09 10:21 ` [PATCH v2 0/2] btrfs :incremental send, improve rmdir performance David Sterba
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.