summaryrefslogtreecommitdiff
path: root/sys/external/bsd/drm2/include/linux
diff options
context:
space:
mode:
authorriastradh <riastradh@NetBSD.org>2022-02-27 14:18:25 +0000
committerriastradh <riastradh@NetBSD.org>2022-02-27 14:18:25 +0000
commit8c5c41ba333b2ced287c42f098c63b7cdd64aafa (patch)
treefce513faf65f9f0f17a0e051799f77efeebe1caa /sys/external/bsd/drm2/include/linux
parent50e1b58ca3059e9dd51fde5b6b2526f8d0cf1932 (diff)
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 (limited to 'sys/external/bsd/drm2/include/linux')
-rw-r--r--sys/external/bsd/drm2/include/linux/interval_tree.h6
-rw-r--r--sys/external/bsd/drm2/include/linux/rbtree.h77
2 files changed, 70 insertions, 13 deletions
diff --git a/sys/external/bsd/drm2/include/linux/interval_tree.h b/sys/external/bsd/drm2/include/linux/interval_tree.h
index 61694479cde..05688049781 100644
--- a/sys/external/bsd/drm2/include/linux/interval_tree.h
+++ b/sys/external/bsd/drm2/include/linux/interval_tree.h
@@ -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, const void *vn, const void *vk)
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 --git a/sys/external/bsd/drm2/include/linux/rbtree.h b/sys/external/bsd/drm2/include/linux/rbtree.h
index 5a06ae4a159..1a15145205e 100644
--- a/sys/external/bsd/drm2/include/linux/rbtree.h
+++ b/sys/external/bsd/drm2/include/linux/rbtree.h
@@ -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 *old, struct rb_node *new,
}
/*
- * 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_ */