* [PATCH 1/3] btrfs: Fix missed backrefs in backref walking code
@ 2012-05-04 18:54 Alexander Block
2012-05-04 18:54 ` [PATCH 2/3] btrfs: Fix ulist related problems " Alexander Block
2012-05-04 18:54 ` [PATCH 3/3] btrfs: Update comment above ulist_next Alexander Block
0 siblings, 2 replies; 4+ messages in thread
From: Alexander Block @ 2012-05-04 18:54 UTC (permalink / raw)
To: chris.mason; +Cc: linux-btrfs, 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
^ permalink raw reply related [flat|nested] 4+ messages in thread
* [PATCH 2/3] btrfs: Fix ulist related problems in backref walking code
2012-05-04 18:54 [PATCH 1/3] btrfs: Fix missed backrefs in backref walking code Alexander Block
@ 2012-05-04 18:54 ` Alexander Block
2012-05-04 18:54 ` [PATCH 3/3] btrfs: Update comment above ulist_next Alexander Block
1 sibling, 0 replies; 4+ messages in thread
From: Alexander Block @ 2012-05-04 18:54 UTC (permalink / raw)
To: chris.mason; +Cc: linux-btrfs, 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
^ permalink raw reply related [flat|nested] 4+ messages in thread
* [PATCH 3/3] btrfs: Update comment above ulist_next
2012-05-04 18:54 [PATCH 1/3] btrfs: Fix missed backrefs in backref walking code Alexander Block
2012-05-04 18:54 ` [PATCH 2/3] btrfs: Fix ulist related problems " Alexander Block
@ 2012-05-04 18:54 ` Alexander Block
2012-05-04 19:10 ` Arne Jansen
1 sibling, 1 reply; 4+ messages in thread
From: Alexander Block @ 2012-05-04 18:54 UTC (permalink / raw)
To: chris.mason; +Cc: linux-btrfs, 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
^ permalink raw reply related [flat|nested] 4+ messages in thread
* Re: [PATCH 3/3] btrfs: Update comment above ulist_next
2012-05-04 18:54 ` [PATCH 3/3] btrfs: Update comment above ulist_next Alexander Block
@ 2012-05-04 19:10 ` Arne Jansen
0 siblings, 0 replies; 4+ messages in thread
From: Arne Jansen @ 2012-05-04 19:10 UTC (permalink / raw)
To: Alexander Block; +Cc: chris.mason, linux-btrfs
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)
> {
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2012-05-04 19:10 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-05-04 18:54 [PATCH 1/3] btrfs: Fix missed backrefs in backref walking code Alexander Block
2012-05-04 18:54 ` [PATCH 2/3] btrfs: Fix ulist related problems " Alexander Block
2012-05-04 18:54 ` [PATCH 3/3] btrfs: Update comment above ulist_next Alexander Block
2012-05-04 19:10 ` Arne Jansen
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.