[PATCH 1/2 v2] Btrfs: rename waiting_dir_move

[PATCH 1/2 v2] Btrfs: rename waiting_dir_move

[Liu Bo]

This is a preparation work, rename waiting_dir_move to send_dir_node.
We'd like to share waiting_dir_move structure in new did_create_dir() code.

Signed-off-by: Liu Bo <bo.li.liu@oracle.com>
---
v2: fix wrong patch name.

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

diff --git a/fs/btrfs/send.c b/fs/btrfs/send.c
index 9dde971..33063d1 100644
--- a/fs/btrfs/send.c
+++ b/fs/btrfs/send.c
@@ -186,7 +186,7 @@ struct pending_dir_move {
 	struct list_head update_refs;
 };
 
-struct waiting_dir_move {
+struct send_dir_node {
 	struct rb_node node;
 	u64 ino;
 };
@@ -2741,10 +2741,10 @@ out:
 static int is_waiting_for_move(struct send_ctx *sctx, u64 ino)
 {
 	struct rb_node *n = sctx->waiting_dir_moves.rb_node;
-	struct waiting_dir_move *entry;
+	struct send_dir_node *entry;
 
 	while (n) {
-		entry = rb_entry(n, struct waiting_dir_move, node);
+		entry = rb_entry(n, struct send_dir_node, node);
 		if (ino < entry->ino)
 			n = n->rb_left;
 		else if (ino > entry->ino)
@@ -2759,7 +2759,7 @@ static int add_waiting_dir_move(struct send_ctx *sctx, u64 ino)
 {
 	struct rb_node **p = &sctx->waiting_dir_moves.rb_node;
 	struct rb_node *parent = NULL;
-	struct waiting_dir_move *entry, *dm;
+	struct send_dir_node *entry, *dm;
 
 	dm = kmalloc(sizeof(*dm), GFP_NOFS);
 	if (!dm)
@@ -2768,7 +2768,7 @@ static int add_waiting_dir_move(struct send_ctx *sctx, u64 ino)
 
 	while (*p) {
 		parent = *p;
-		entry = rb_entry(parent, struct waiting_dir_move, node);
+		entry = rb_entry(parent, struct send_dir_node, node);
 		if (ino < entry->ino) {
 			p = &(*p)->rb_left;
 		} else if (ino > entry->ino) {
@@ -2787,10 +2787,10 @@ static int add_waiting_dir_move(struct send_ctx *sctx, u64 ino)
 static int del_waiting_dir_move(struct send_ctx *sctx, u64 ino)
 {
 	struct rb_node *n = sctx->waiting_dir_moves.rb_node;
-	struct waiting_dir_move *entry;
+	struct send_dir_node *entry;
 
 	while (n) {
-		entry = rb_entry(n, struct waiting_dir_move, node);
+		entry = rb_entry(n, struct send_dir_node, node);
 		if (ino < entry->ino) {
 			n = n->rb_left;
 		} else if (ino > entry->ino) {
@@ -5469,10 +5469,10 @@ out:
 	WARN_ON(sctx && !ret && !RB_EMPTY_ROOT(&sctx->waiting_dir_moves));
 	while (sctx && !RB_EMPTY_ROOT(&sctx->waiting_dir_moves)) {
 		struct rb_node *n;
-		struct waiting_dir_move *dm;
+		struct send_dir_node *dm;
 
 		n = rb_first(&sctx->waiting_dir_moves);
-		dm = rb_entry(n, struct waiting_dir_move, node);
+		dm = rb_entry(n, struct send_dir_node, node);
 		rb_erase(&dm->node, &sctx->waiting_dir_moves);
 		kfree(dm);
 	}
-- 
1.8.2.1

[PATCH 2/2 v2] Btrfs: check if directory has already been created smarter

[Liu Bo]

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@oracle.com>
---
v2: fix wrong patch name.

 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

Re: [PATCH 2/2 v2] Btrfs: check if directory has already been created smarter

[Wang Shilong]

On 02/27/2014 03:47 PM, 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.
Just a reminder, we ususally call O(n) rather O(1) here.
If we falls O(1) to O(logn)..things are becoming worse~~


Thanks,
Wang
>
> Signed-off-by: Liu Bo <bo.li.liu@oracle.com>
> ---
> v2: fix wrong patch name.
>
>   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(

Re: [PATCH 2/2 v2] Btrfs: check if directory has already been created smarter

[Liu Bo]

On Thu, Feb 27, 2014 at 04:01:23PM +0800, Wang Shilong wrote:
> On 02/27/2014 03:47 PM, 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.
> Just a reminder, we ususally call O(n) rather O(1) here.
> If we falls O(1) to O(logn)..things are becoming worse~~

Good catch, my bad.

thanks,
-liubo

[PATCH 2/2 v3] Btrfs: check if directory has already been created smarter

[Liu Bo]

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(log n)
search instead of O(n) search.

Signed-off-by: Liu Bo <bo.li.liu@oracle.com>
---
v3: fix typo, s/O(1)/O(n)/g, thanks Wang Shilong.
v2: fix wrong patch name.

 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

Re: [PATCH 1/2 v2] Btrfs: rename waiting_dir_move

[Josef Bacik]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 02/27/2014 02:47 AM, Liu Bo wrote:
> This is a preparation work, rename waiting_dir_move to
> send_dir_node. We'd like to share waiting_dir_move structure in new
> did_create_dir() code.
> 
> Signed-off-by: Liu Bo <bo.li.liu@oracle.com> --- v2: fix wrong
> patch name.
> 
This isn't applying cleanly, rebase once I push out btrfs-next today
and resend.  Thanks,

Josef

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/

iQIcBAEBAgAGBQJTGglEAAoJEANb+wAKly3Bm9YP+wSnaq7jN0pQT8UVORFE2BVI
rTKGWfSnJQtEAUx3sF0xCp6dCQlkG+BBPHmK3W1yGovtHQrkR0rkGufx0aLzqD2m
xpV7qQKa9rAQjK5Xsx0K0vDETqYFzEIGv+bv1Q6jFVKoEBVSSdWDPZoSLkVZ9T0Q
aoYUvC/xd4fkp6ikb11vL+3c7WysWaDpSTflZdEFgrd5PgE+r1CoxmTs5NMCxhIK
V6GEu/l3yKK2/95CNAfhkkeRXyV2NVxf/AzM0Jay7+zyCUBM4u2B7BAuC7ZlCxG2
kUhqTw4TkFUIW6mW/sszKWJM9bjDLyq7bYzmJ08yFeiiS0Pvr9NaYxkNc55HUve0
ZLnrICzAJbjQV0f01+Tn5G2/jKX6PEeGRcyWJ1RgEFBRDPh5AMsbHeme3JKWkikZ
xxtT3gvZMlASm1CFtepoFQiBwtd8KR7VJIS9VAhO7VGyvWu3+DSvGe8di+OKvjIh
kBnx7mgfmQChIe4Ccem3iJsNPkR/e9vpoZalBSGTnBGNiztDc64Ht3Xh+YN034n1
4zw6XjYoKo+NJ/8pz2auKjWtZdC3AUSEkaU3koB4U1+uyQJAqDfki8j0Trye5ehn
TemIj6kSfOvuuiCaGCqYwJJYG5r0UXALRwpGtiMk+SGzUklbjmg8q1LKKJiagV8K
yVTNyMKP8Qldlsw1bAPm
=Nkos
-----END PGP SIGNATURE-----