Module Name: src
Committed By: riastradh
Date: Sun Feb 27 14:18:25 UTC 2022
Modified Files:
src/sys/external/bsd/drm2/include/linux: interval_tree.h rbtree.h
Log Message:
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.
To generate a diff of this commit:
cvs rdiff -u -r1.12 -r1.13 \
src/sys/external/bsd/drm2/include/linux/interval_tree.h
cvs rdiff -u -r1.16 -r1.17 src/sys/external/bsd/drm2/include/linux/rbtree.h
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/sys/external/bsd/drm2/include/linux/interval_tree.h
diff -u src/sys/external/bsd/drm2/include/linux/interval_tree.h:1.12 src/sys/external/bsd/drm2/include/linux/interval_tree.h:1.13
--- src/sys/external/bsd/drm2/include/linux/interval_tree.h:1.12 Sun Dec 19 11:00:18 2021
+++ src/sys/external/bsd/drm2/include/linux/interval_tree.h Sun Feb 27 14:18:25 2022
@@ -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 @@ interval_tree_compare_key(void *cookie,
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
Index: src/sys/external/bsd/drm2/include/linux/rbtree.h
diff -u src/sys/external/bsd/drm2/include/linux/rbtree.h:1.16 src/sys/external/bsd/drm2/include/linux/rbtree.h:1.17
--- src/sys/external/bsd/drm2/include/linux/rbtree.h:1.16 Mon Feb 14 19:13:04 2022
+++ src/sys/external/bsd/drm2/include/linux/rbtree.h Sun Feb 27 14:18:25 2022
@@ -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 @@ rb_replace_node_cached(struct rb_node *o
}
/*
- * 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_ */
