[PATCH 1/3] btrfs: Fix missed backrefs in backref walking code

[PATCH 1/3] btrfs: Fix missed backrefs in backref walking code

[Alexander Block]

__merge_refs was deleting unresolved prelim refs resulting in missed
backrefs in the backref walking code. Thanks to Arne and Jan for finding
this.

Signed-off-by: Alexander Block <ablock84@googlemail.com>
---
 fs/btrfs/backref.c |    2 ++
 1 files changed, 2 insertions(+), 0 deletions(-)

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index b4b940e..f28ecba 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -265,6 +265,8 @@ static int __merge_refs(struct list_head *head, int mode)
 
 		if (mode == 1 && ref1->key.type == 0)
 			continue;
+		if (ref1->parent)
+			continue;
 		for (pos2 = pos1->next, n2 = pos2->next; pos2 != head;
 		     pos2 = n2, n2 = pos2->next) {
 			struct __prelim_ref *ref2;
-- 
1.7.3.4

[PATCH 2/3] btrfs: Fix ulist related problems in backref walking code

[Alexander Block]

1. in btrfs_find_all_roots
   This method uses a ulist to solve the recursion. The local variable
   node is used in combination with ulist_next to iterate through the
   list. Calls to find_parent_nodes fill up this list. The problem is,
   adding new nodes to the ulist may cause the ulist->nodes pointer to
   change in case the ulist needs to realloc the buffer. The call to
   ulist_next may use a wrong prev pointer in that case, resulting in
   undefined behaviour. It is changed now to not use ulist_next.
2. in __iterate_extent_inodes
   the first while loop calls btrfs_find_all_roots, which then allocates
   a new ulist for the roots. In case the first while loops loops more
   then once, we leak the previous ulist as it is not freed.

Point 1 was also causing missed backrefs because the iteration stopped
too early.

Signed-off-by: Alexander Block <ablock84@googlemail.com>
---
 fs/btrfs/backref.c |   20 ++++++++++++++------
 1 files changed, 14 insertions(+), 6 deletions(-)

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index f28ecba..b08cf93 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -791,6 +791,7 @@ int btrfs_find_all_roots(struct btrfs_trans_handle *trans,
 	struct ulist *tmp;
 	struct ulist_node *node = NULL;
 	int ret;
+	int cur;
 
 	tmp = ulist_alloc(GFP_NOFS);
 	if (!tmp)
@@ -801,7 +802,14 @@ int btrfs_find_all_roots(struct btrfs_trans_handle *trans,
 		return -ENOMEM;
 	}
 
-	while (1) {
+	cur = 0;
+	ulist_add(tmp, bytenr, 0, GFP_NOFS);
+
+	while (cur < tmp->nnodes) {
+		node = &tmp->nodes[cur++];
+		bytenr = node->val;
+
+		/* this will add new nodes to the tmp ulist */
 		ret = find_parent_nodes(trans, fs_info, bytenr, seq,
 					tmp, *roots);
 		if (ret < 0 && ret != -ENOENT) {
@@ -809,10 +817,6 @@ int btrfs_find_all_roots(struct btrfs_trans_handle *trans,
 			ulist_free(*roots);
 			return ret;
 		}
-		node = ulist_next(tmp, node);
-		if (!node)
-			break;
-		bytenr = node->val;
 	}
 
 	ulist_free(tmp);
@@ -1231,10 +1235,14 @@ static int __iterate_extent_inodes(struct btrfs_fs_info *fs_info,
 						match_with_offset,
 						iterate, ctx);
 		}
+		if (roots)
+			ulist_free(roots);
+		roots = NULL;
 	}
 
 	ulist_free(refs);
-	ulist_free(roots);
+	if (roots)
+		ulist_free(roots);
 out:
 	if (!search_commit_root) {
 		btrfs_put_delayed_seq(delayed_refs, &seq_elem);
-- 
1.7.3.4

[PATCH 3/3] btrfs: Update comment above ulist_next

[Alexander Block]

The comment above ulist_next stated that it's allowed to call ulist_add
while enumerating. This is actually not allowed as an add may realocate
the nodes buffer und thus make the prev pointer invalid.

Signed-off-by: Alexander Block <ablock84@googlemail.com>
---
 fs/btrfs/ulist.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/fs/btrfs/ulist.c b/fs/btrfs/ulist.c
index 12f5147..07ea3e5 100644
--- a/fs/btrfs/ulist.c
+++ b/fs/btrfs/ulist.c
@@ -198,8 +198,8 @@ EXPORT_SYMBOL(ulist_add);
  * end is reached. No guarantee is made with respect to the order in which
  * the elements are returned. They might neither be returned in order of
  * addition nor in ascending order.
- * It is allowed to call ulist_add during an enumeration. Newly added items
- * are guaranteed to show up in the running enumeration.
+ * It is not allowed to call ulist_add during an enumeration as this would
+ * cause undefined behavior.
  */
 struct ulist_node *ulist_next(struct ulist *ulist, struct ulist_node *prev)
 {
-- 
1.7.3.4

Re: [PATCH 3/3] btrfs: Update comment above ulist_next

[Arne Jansen]

On 05/04/12 20:54, Alexander Block wrote:
> The comment above ulist_next stated that it's allowed to call ulist_add
> while enumerating. This is actually not allowed as an add may realocate
> the nodes buffer und thus make the prev pointer invalid.
>
> Signed-off-by: Alexander Block<ablock84@googlemail.com>

I'd much prefer to fix the problem in ulist_next, as being able to add
values while enumerating is a key feature of ulist. If it's unfixable,
it should be thrown out completely.

-Arne

> ---
>   fs/btrfs/ulist.c |    4 ++--
>   1 files changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/fs/btrfs/ulist.c b/fs/btrfs/ulist.c
> index 12f5147..07ea3e5 100644
> --- a/fs/btrfs/ulist.c
> +++ b/fs/btrfs/ulist.c
> @@ -198,8 +198,8 @@ EXPORT_SYMBOL(ulist_add);
>    * end is reached. No guarantee is made with respect to the order in which
>    * the elements are returned. They might neither be returned in order of
>    * addition nor in ascending order.
> - * It is allowed to call ulist_add during an enumeration. Newly added items
> - * are guaranteed to show up in the running enumeration.
> + * It is not allowed to call ulist_add during an enumeration as this would
> + * cause undefined behavior.
>    */
>   struct ulist_node *ulist_next(struct ulist *ulist, struct ulist_node *prev)
>   {