The patch titled
Subject: rbtree: clarify documentation of rbtree_postorder_for_each_entry_safe()
has been added to the -mm tree. Its filename is
rbtree-clarify-documentation-of-rbtree_postorder_for_each_entry_safe.patch
This patch should soon appear at
http://ozlabs.org/~akpm/mmots/broken-out/rbtree-clarify-documentation-of-rbtree_postorder_for_each_entry_safe.patch
and later at
http://ozlabs.org/~akpm/mmotm/broken-out/rbtree-clarify-documentation-of-rbtree_postorder_for_each_entry_safe.patch
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/SubmitChecklist when testing your code ***
The -mm tree is included into linux-next and is updated
there every 3-4 working days
------------------------------------------------------
From: Cody P Schafer <dev@xxxxxxxxxx>
Subject: rbtree: clarify documentation of rbtree_postorder_for_each_entry_safe()
I noticed that commit a20135ffbc44 ("writeback: don't drain
bdi_writeback_congested on bdi destruction") added a usage of
rbtree_postorder_for_each_entry_safe() in mm/backing-dev.c which appears
to try to rb_erase() elements from an rbtree while iterating over it using
rbtree_postorder_for_each_entry_safe().
Doing this will cause random nodes to be missed by the iteration because
rb_erase() may rebalance the tree, changing the ordering that we're trying
to iterate over.
The previous documentation for rbtree_postorder_for_each_entry_safe()
wasn't clear that this wasn't allowed, it was taken from the docs for
list_for_each_entry_safe(), where erasing isn't a problem due to
list_del() not reordering.
Explicitly warn developers about this potential pit-fall.
Note that I haven't fixed the actual issue that (it appears) the commit
referenced above introduced (not familiar enough with that code).
In general (and in this case), the patterns to follow are:
- switch to rb_first() + rb_erase(), don't use
rbtree_postorder_for_each_entry_safe().
- keep the postorder iteration and don't rb_erase() at all. Instead
just clear the fields of rb_node & cgwb_congested_tree as required by
other users of those structures.
Signed-off-by: Cody P Schafer <dev@xxxxxxxxxx>
Cc: John de la Garza <john@xxxxxxxxx>
Cc: Michel Lespinasse <walken@xxxxxxxxxx>
Cc: Peter Zijlstra <peterz@xxxxxxxxxxxxx>
Cc: Rusty Russell <rusty@xxxxxxxxxxxxxxx>
Cc: Tejun Heo <tj@xxxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
---
include/linux/rbtree.h | 12 ++++++++++--
1 file changed, 10 insertions(+), 2 deletions(-)
diff -puN include/linux/rbtree.h~rbtree-clarify-documentation-of-rbtree_postorder_for_each_entry_safe include/linux/rbtree.h
--- a/include/linux/rbtree.h~rbtree-clarify-documentation-of-rbtree_postorder_for_each_entry_safe
+++ a/include/linux/rbtree.h
@@ -101,13 +101,21 @@ static inline void rb_link_node_rcu(stru
})
/**
- * rbtree_postorder_for_each_entry_safe - iterate over rb_root in post order of
- * given type safe against removal of rb_node entry
+ * rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of
+ * given type allowing the backing memory of @pos to be invalidated
*
* @pos: the 'type *' to use as a loop cursor.
* @n: another 'type *' to use as temporary storage
* @root: 'rb_root *' of the rbtree.
* @field: the name of the rb_node field within 'type'.
+ *
+ * This function provides a similar guarantee as list_for_each_entry_safe() and
+ * allows the iteration to continue independent of changes to @pos by the body
+ * of the loop.
+ *
+ * Note, however, that it cannot handle other modifications that re-order the
+ * rbtree it is iterating over. This includes calling rb_erase() on @pos, as
+ * rb_erase() may rebalance the tree, causing us to miss some nodes.
*/
#define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \
for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \
_
Patches currently in -mm which might be from dev@xxxxxxxxxx are
rbtree-clarify-documentation-of-rbtree_postorder_for_each_entry_safe.patch
--
To unsubscribe from this list: send the line "unsubscribe mm-commits" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
