implement linux interval tree functions

Adapt kettenis' amdgpu interval tree replacement functions for the
interval_tree.h functions radeondrm uses on cayman, aruba and GCN.

3 files changed, 68 insertions, 37 deletions

diff --git a/sys/dev/pci/drm/drm_linux.c b/sys/dev/pci/drm/drm_linux.c
index 2cbd0905406..fd797effc74 100644
--- a/sys/dev/pci/drm/drm_linux.c
+++ b/sys/dev/pci/drm/drm_linux.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: drm_linux.c,v 1.63 2020/08/26 03:29:06 visa Exp $	*/
+/*	$OpenBSD: drm_linux.c,v 1.64 2020/10/16 09:20:04 jsg Exp $	*/
 /*
  * Copyright (c) 2013 Jonathan Gray <jsg@openbsd.org>
  * Copyright (c) 2015, 2016 Mark Kettenis <kettenis@openbsd.org>
@@ -46,6 +46,7 @@
 #include <linux/shrinker.h>
 #include <linux/fb.h>
 #include <linux/xarray.h>
+#include <linux/interval_tree.h>
 
 #include <drm/drm_device.h>
 #include <drm/drm_print.h>
@@ -2090,3 +2091,50 @@ printk(const char *fmt, ...)
 
 	return ret;
 }
+
+#define START(node) ((node)->start)
+#define LAST(node) ((node)->last)
+
+struct interval_tree_node *
+interval_tree_iter_first(struct rb_root_cached *root, unsigned long start,
+    unsigned long last)
+{
+	struct interval_tree_node *node;
+	struct rb_node *rb;
+
+	for (rb = rb_first_cached(root); rb; rb = rb_next(rb)) {
+		node = rb_entry(rb, typeof(*node), rb);
+		if (LAST(node) >= start && START(node) <= last)
+			return node;
+	}
+	return NULL;
+}
+
+void
+interval_tree_remove(struct interval_tree_node *node,
+    struct rb_root_cached *root) 
+{
+	rb_erase_cached(&node->rb, root);
+}
+
+void
+interval_tree_insert(struct interval_tree_node *node,
+    struct rb_root_cached *root)
+{
+	struct rb_node **iter = &root->rb_root.rb_node;
+	struct rb_node *parent = NULL;
+	struct interval_tree_node *iter_node;
+
+	while (*iter) {
+		parent = *iter;
+		iter_node = rb_entry(*iter, struct interval_tree_node, rb);
+
+		if (node->start < iter_node->start)
+			iter = &(*iter)->rb_left;
+		else
+			iter = &(*iter)->rb_right;
+	}
+
+	rb_link_node(&node->rb, parent, iter);
+	rb_insert_color_cached(&node->rb, root, false);
+}
diff --git a/sys/dev/pci/drm/include/linux/interval_tree.h b/sys/dev/pci/drm/include/linux/interval_tree.h
index e69de29bb2d..75f7a3799bd 100644
--- a/sys/dev/pci/drm/include/linux/interval_tree.h
+++ b/sys/dev/pci/drm/include/linux/interval_tree.h
@@ -0,0 +1,19 @@
+/* Public domain. */
+
+#ifndef _LINUX_INTERVAL_TREE_H
+#define _LINUX_INTERVAL_TREE_H
+
+#include <linux/rbtree.h>
+
+struct interval_tree_node {
+	struct rb_node rb;
+	unsigned long start;
+	unsigned long last;
+};
+
+struct interval_tree_node *interval_tree_iter_first(struct rb_root_cached *,
+    unsigned long, unsigned long);
+void interval_tree_insert(struct interval_tree_node *, struct rb_root_cached *);
+void interval_tree_remove(struct interval_tree_node *, struct rb_root_cached *);
+
+#endif
diff --git a/sys/dev/pci/drm/include/linux/rbtree.h b/sys/dev/pci/drm/include/linux/rbtree.h
index fe45a4eeeb1..875ce42f2cd 100644
--- a/sys/dev/pci/drm/include/linux/rbtree.h
+++ b/sys/dev/pci/drm/include/linux/rbtree.h
@@ -29,10 +29,6 @@
 #ifndef	_LINUX_RBTREE_H_
 #define	_LINUX_RBTREE_H_
 
-/* for printf */
-#include <sys/types.h>
-#include <sys/systm.h>
-
 #include <sys/tree.h>
 
 struct rb_node {
@@ -163,36 +159,4 @@ rb_replace_node(struct rb_node *victim, struct rb_node *new,
 #define RB_ROOT_CACHED	(struct rb_root_cached) { { NULL } }
 #endif
 
-struct interval_tree_node {
-	struct rb_node rb;
-	unsigned long start;
-	unsigned long last;
-};
-
-static inline struct interval_tree_node *
-interval_tree_iter_first(struct rb_root_cached *root,
-    unsigned long start, unsigned long last)
-{
-#ifdef DRMDEBUG
-	printf("%s: stub start: 0x%lx last: 0x%lx\n", __func__, start, last);
-#endif
-	return NULL;
-}
-
-static inline void
-interval_tree_insert(struct interval_tree_node *node, struct rb_root_cached *root)
-{
-#ifdef DRMDEBUG
-	printf("%s: stub start: 0x%lx last: 0x%lx\n", __func__, node->start, node->last);
-#endif
-}
-
-static inline void
-interval_tree_remove(struct interval_tree_node *node, struct rb_root_cached *root)
-{
-#ifdef DRMDEBUG
-	printf("%s: stub start: 0x%lx last: 0x%lx\n", __func__, node->start, node->last);
-#endif
-}
-
 #endif	/* _LINUX_RBTREE_H_ */