[src/trunk]: src/sys/external/bsd/drm2/include/linux linux: Actually do post-...

[riastradh <riastradh%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/45c8547d45dc
branches:  trunk
changeset: 362430:45c8547d45dc
user:      riastradh <riastradh%NetBSD.org@localhost>
date:      Sun Feb 27 14:18:25 2022 +0000

description:
linux: Actually do post-order tree traversal.

Requires breaking the rbtree(3) abstraction, but this is necessary
because the body of the loop often frees the element, so as is we had
a huge pile of use-after-free going on.

Requires changing struct interval_tree_node's rbnode member to match
the Linux name, since we now use container_of here, and radeon relies
on this.

diffstat:

 sys/external/bsd/drm2/include/linux/interval_tree.h |   6 +-
 sys/external/bsd/drm2/include/linux/rbtree.h        |  77 ++++++++++++++++++--
 2 files changed, 70 insertions(+), 13 deletions(-)

diffs (118 lines):

diff -r c604c42641f5 -r 45c8547d45dc sys/external/bsd/drm2/include/linux/interval_tree.h
--- a/sys/external/bsd/drm2/include/linux/interval_tree.h       Sun Feb 27 14:17:10 2022 +0000
+++ b/sys/external/bsd/drm2/include/linux/interval_tree.h       Sun Feb 27 14:18:25 2022 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: interval_tree.h,v 1.12 2021/12/19 11:00:18 riastradh Exp $     */
+/*     $NetBSD: interval_tree.h,v 1.13 2022/02/27 14:18:25 riastradh Exp $     */
 
 /*-
  * Copyright (c) 2018 The NetBSD Foundation, Inc.
@@ -43,7 +43,7 @@
 #include <linux/rbtree.h>
 
 struct interval_tree_node {
-       struct rb_node  itn_node;
+       struct rb_node  rb;
        unsigned long   start;  /* inclusive */
        unsigned long   last;   /* inclusive */
 };
@@ -81,7 +81,7 @@
 static const rb_tree_ops_t interval_tree_ops = {
        .rbto_compare_nodes = interval_tree_compare_nodes,
        .rbto_compare_key = interval_tree_compare_key,
-       .rbto_node_offset = offsetof(struct interval_tree_node, itn_node),
+       .rbto_node_offset = offsetof(struct interval_tree_node, rb),
 };
 
 static inline void
diff -r c604c42641f5 -r 45c8547d45dc sys/external/bsd/drm2/include/linux/rbtree.h
--- a/sys/external/bsd/drm2/include/linux/rbtree.h      Sun Feb 27 14:17:10 2022 +0000
+++ b/sys/external/bsd/drm2/include/linux/rbtree.h      Sun Feb 27 14:18:25 2022 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: rbtree.h,v 1.16 2022/02/14 19:13:04 riastradh Exp $    */
+/*     $NetBSD: rbtree.h,v 1.17 2022/02/27 14:18:25 riastradh Exp $    */
 
 /*-
  * Copyright (c) 2013 The NetBSD Foundation, Inc.
@@ -144,15 +144,72 @@
 }
 
 /*
- * XXX This is not actually postorder, but I can't fathom why you would
- * want postorder for an ordered tree; different insertion orders lead
- * to different traversal orders.
+ * This violates the abstraction of rbtree(3) for postorder traversal
+ * -- children first, then parents -- so it is safe for cleanup code
+ * that just frees all the nodes without removing them from the tree.
  */
-#define        rbtree_postorder_for_each_entry_safe(NODE, TMP, ROOT, FIELD)          \
-       for ((NODE) = RB_TREE_MIN(&(ROOT)->rbr_tree);                         \
-               ((NODE) != NULL &&                                            \
-                   ((TMP) = rb_tree_iterate(&(ROOT)->rbr_tree, (NODE),       \
-                       RB_DIR_RIGHT), 1));                                   \
-               (NODE) = (TMP))
+static inline struct rb_node *
+rb_first_postorder(const struct rb_root *root)
+{
+       struct rb_node *node, *child;
+
+       if ((node = root->rbr_tree.rbt_root) == NULL)
+               return NULL;
+       for (;; node = child) {
+               if ((child = node->rb_left) != NULL)
+                       continue;
+               if ((child = node->rb_right) != NULL)
+                       continue;
+               return node;
+       }
+}
+
+static inline struct rb_node *
+rb_next2_postorder(const struct rb_root *root, struct rb_node *node)
+{
+       struct rb_node *parent, *child;
+
+       if (node == NULL)
+               return NULL;
+
+       /*
+        * If we're at the root, there are no more siblings and no
+        * parent, so post-order iteration is done.
+        */
+       if (RB_ROOT_P(&root->rbr_tree, node))
+               return NULL;
+       parent = RB_FATHER(node);       /* kinda sexist, innit */
+       KASSERT(parent != NULL);
+
+       /*
+        * If we're the right child, we've already processed the left
+        * child (which may be gone by now), so just return the parent.
+        */
+       if (RB_RIGHT_P(node))
+               return parent;
+
+       /*
+        * Otherwise, move down to the leftmost child of our right
+        * sibling -- or return the parent if there is none.
+        */
+       if ((node = parent->rb_right) == NULL)
+               return parent;
+       for (;; node = child) {
+               if ((child = node->rb_left) != NULL)
+                       continue;
+               if ((child = node->rb_right) != NULL)
+                       continue;
+               return node;
+       }
+}
+
+#define        rbtree_postorder_for_each_entry_safe(ENTRY, TMP, ROOT, FIELD)         \
+       for ((ENTRY) = rb_entry_safe(rb_first_postorder(ROOT),                \
+                   __typeof__(*(ENTRY)), FIELD);                             \
+               ((ENTRY) != NULL &&                                           \
+                   ((TMP) = rb_entry_safe(rb_next2_postorder((ROOT),         \
+                           &(ENTRY)->FIELD), __typeof__(*(ENTRY)), FIELD),   \
+                       1));                                                  \
+               (ENTRY) = (TMP))
 
 #endif  /* _LINUX_RBTREE_H_ */