Sorry for the noise, it should be PATCH 1/2 and PATCH 2/2.
-liubo
On Thu, Feb 27, 2014 at 03:39:40PM +0800, Liu Bo wrote:
> Currently to check whether a directory has been created, we search
> DIR_INDEX items one by one to check if children has been processed.
>
> Try to picture such a scenario:
> .
> |-- dir (ino X)
> |-- foo_1 (ino X+1)
> |-- ...
> |-- foo_k (ino X+k)
>
> With the current way, we have to check all the k DIR_INDEX items
> to find it is a fresh new one.
>
> So this introduced a rbtree to store those directories which are
> created out of order, and in the above case, we just need an O(logn)
> search instead of O(1) search.
>
> Signed-off-by: Liu Bo <bo.li.liu@xxxxxxxxxx>
> ---
> fs/btrfs/send.c | 87 ++++++++++++++++++++++++++++-----------------------------
> 1 file changed, 43 insertions(+), 44 deletions(-)
>
> diff --git a/fs/btrfs/send.c b/fs/btrfs/send.c
> index 33063d1..fcad93c 100644
> --- a/fs/btrfs/send.c
> +++ b/fs/btrfs/send.c
> @@ -175,6 +175,9 @@ struct send_ctx {
> * own move/rename can be performed.
> */
> struct rb_root waiting_dir_moves;
> +
> + /* directories which are created out of order, check did_create_dir() */
> + struct rb_root out_of_order;
> };
>
> struct pending_dir_move {
> @@ -2494,56 +2497,40 @@ out:
> */
> static int did_create_dir(struct send_ctx *sctx, u64 dir)
> {
> - int ret = 0;
> - struct btrfs_path *path = NULL;
> - struct btrfs_key key;
> - struct btrfs_key found_key;
> - struct btrfs_key di_key;
> - struct extent_buffer *eb;
> - struct btrfs_dir_item *di;
> - int slot;
> + struct rb_node **p = &sctx->out_of_order.rb_node;
> + struct rb_node *parent = NULL;
> + struct send_dir_node *entry = NULL;
> + int cur_is_dir = !!(dir == sctx->cur_ino);
>
> - path = alloc_path_for_send();
> - if (!path) {
> - ret = -ENOMEM;
> - goto out;
> - }
> + verbose_printk("dir=%llu cur_ino=%llu send_progress=%llu\n",
> + dir, sctx->cur_ino, sctx->send_progress);
>
> - key.objectid = dir;
> - key.type = BTRFS_DIR_INDEX_KEY;
> - key.offset = 0;
> - while (1) {
> - ret = btrfs_search_slot_for_read(sctx->send_root, &key, path,
> - 1, 0);
> - if (ret < 0)
> - goto out;
> - if (!ret) {
> - eb = path->nodes[0];
> - slot = path->slots[0];
> - btrfs_item_key_to_cpu(eb, &found_key, slot);
> - }
> - if (ret || found_key.objectid != key.objectid ||
> - found_key.type != key.type) {
> - ret = 0;
> - goto out;
> + while (*p) {
> + parent = *p;
> + entry = rb_entry(parent, struct send_dir_node, node);
> + if (dir < entry->ino) {
> + p = &(*p)->rb_left;
> + } else if (dir > entry->ino) {
> + p = &(*p)->rb_right;
> + } else {
> + if (cur_is_dir) {
> + rb_erase(&entry->node, &sctx->out_of_order);
> + kfree(entry);
> + }
> + return 1;
> }
> + }
>
> - di = btrfs_item_ptr(eb, slot, struct btrfs_dir_item);
> - btrfs_dir_item_key_to_cpu(eb, di, &di_key);
> -
> - if (di_key.type != BTRFS_ROOT_ITEM_KEY &&
> - di_key.objectid < sctx->send_progress) {
> - ret = 1;
> - goto out;
> - }
> + if (!cur_is_dir) {
> + entry = kmalloc(sizeof(*entry), GFP_NOFS);
> + if (!entry)
> + return -ENOMEM;
> + entry->ino = dir;
>
> - key.offset = found_key.offset + 1;
> - btrfs_release_path(path);
> + rb_link_node(&entry->node, parent, p);
> + rb_insert_color(&entry->node, &sctx->out_of_order);
> }
> -
> -out:
> - btrfs_free_path(path);
> - return ret;
> + return 0;
> }
>
> /*
> @@ -5340,6 +5327,7 @@ long btrfs_ioctl_send(struct file *mnt_file, void __user *arg_)
>
> sctx->pending_dir_moves = RB_ROOT;
> sctx->waiting_dir_moves = RB_ROOT;
> + sctx->out_of_order = RB_ROOT;
>
> sctx->clone_roots = vzalloc(sizeof(struct clone_root) *
> (arg->clone_sources_count + 1));
> @@ -5477,6 +5465,17 @@ out:
> kfree(dm);
> }
>
> + WARN_ON(sctx && !ret && !RB_EMPTY_ROOT(&sctx->out_of_order));
> + while (sctx && !RB_EMPTY_ROOT(&sctx->out_of_order)) {
> + struct rb_node *n;
> + struct send_dir_node *entry;
> +
> + n = rb_first(&sctx->out_of_order);
> + entry = rb_entry(n, struct send_dir_node, node);
> + rb_erase(&entry->node, &sctx->out_of_order);
> + kfree(entry);
> + }
> +
> if (sort_clone_roots) {
> for (i = 0; i < sctx->clone_roots_cnt; i++)
> btrfs_root_dec_send_in_progress(
> --
> 1.8.2.1
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
> the body of a message to majordomo@xxxxxxxxxxxxxxx
> More majordomo info at http://vger.kernel.org/majordomo-info.html
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
