linux-kernel - [PATCH] rbtree: introduce three helpers about sort-order iteration

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Date:   Tue, 10 Mar 2020 00:02:14 +0800
From:   qiwuchen55@...il.com
To:     akpm@...ux-foundation.org, peterz@...radead.org, walken@...gle.com,
        rfontana@...hat.com, dbueso@...e.de
Cc:     tglx@...utronix.de, linux-kernel@...r.kernel.org,
        chenqiwu <chenqiwu@...omi.com>
Subject: [PATCH] rbtree: introduce three helpers about sort-order iteration

From: chenqiwu <chenqiwu@...omi.com>

I noticed that there are many relatively common usages about the
sort-order iteration for rbtree, like this:

[drivers/android/binder.c]
for (n = rb_first(&proc->nodes); n != NULL; n = rb_next(n)) {
	struct binder_node *node = rb_entry(n, struct binder_node,
					    rb_node);
	......
}

This patch introduced three helpers to simplify sort-order iteration
for rbtree.

Signed-off-by: chenqiwu <chenqiwu@...omi.com>
---
 include/linux/rbtree.h | 45 +++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 43 insertions(+), 2 deletions(-)

diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 1fd61a9..26b4359 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -90,11 +90,52 @@ static inline void rb_link_node_rcu(struct rb_node *node, struct rb_node *parent
 	})
 
 /**
+ * rbtree_for_each - iterate in sort-order over a rbtree.
+ * @pos:	the 'rb_node *' to use as a loop cursor.
+ * @root:	'rb_root *' of the rbtree.
+ */
+#define rbtree_for_each(pos, root) \
+	for (pos = rb_first(root); pos; pos = rb_next(pos))
+
+/**
+ * rbtree_for_each_entry - iterate in sort-order over rb_root of given type.
+ * @pos:	the 'type *' to use as a loop cursor.
+ * @root:	'rb_root *' of the rbtree.
+ * @field:	the name of the rb_node field within 'type'.
+ */
+#define rbtree_for_each_entry(pos, root, field) \
+	for (pos = rb_entry_safe(rb_first(root), typeof(*pos), field); \
+	     pos; \
+	     pos = rb_entry_safe(rb_next(&pos->field), typeof(*pos), field))
+
+/**
+ * rbtree_for_each_entry_safe - iterate in sort-order over 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'.
+ *
+ * rbtree_order_for_each_entry_safe() provides a similar guarantee as
+ * list_for_each_entry_safe() and allows the sort-order 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_for_each_entry_safe(pos, n, root, field) \
+	for (pos = rb_entry_safe(rb_first(root), typeof(*pos), field); \
+	     pos && ({ n = rb_entry_safe(rb_next(&pos->field), \
+			typeof(*pos), field); 1; }); \
+	     pos = n)
+
+/**
  * 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
+ * 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
+ * @n:		another 'type *' to use as temporary storage.
  * @root:	'rb_root *' of the rbtree.
  * @field:	the name of the rb_node field within 'type'.
  *
-- 
1.9.1