LinuxKPI: Implement interval_tree

Required by drm-kmod

MFC after:	1 week
Reviewed by:	hselasky, manu
Differential Revision: https://reviews.freebsd.org/D32869

(cherry picked from commit dbc920bd9a9b413182a1940155539a3144a405aa)

4 files changed, 201 insertions, 0 deletions

diff --git a/sys/compat/linuxkpi/common/include/linux/interval_tree.h b/sys/compat/linuxkpi/common/include/linux/interval_tree.h
new file mode 100644
index 000000000000..7910f8131d2f
--- /dev/null
+++ b/sys/compat/linuxkpi/common/include/linux/interval_tree.h
@@ -0,0 +1,55 @@
+/*-
+ * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
+ *
+ * Copyright (c) 2021 Vladimir Kondratyev <wulf@FreeBSD.org>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice unmodified, this list of conditions, and the following
+ *    disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#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;
+};
+
+#define	interval_tree_iter_first(...)	\
+	lkpi_interval_tree_iter_first(__VA_ARGS__)
+#define	interval_tree_iter_next(...)	\
+	lkpi_interval_tree_iter_next(__VA_ARGS__)
+#define	interval_tree_insert(...)	lkpi_interval_tree_insert(__VA_ARGS__)
+#define	interval_tree_remove(...)	lkpi_interval_tree_remove(__VA_ARGS__)
+
+struct interval_tree_node *lkpi_interval_tree_iter_first(
+    struct rb_root_cached *, unsigned long, unsigned long);
+struct interval_tree_node *lkpi_interval_tree_iter_next(
+    struct interval_tree_node *, unsigned long, unsigned long);
+void lkpi_interval_tree_insert(struct interval_tree_node *,
+    struct rb_root_cached *);
+void lkpi_interval_tree_remove(struct interval_tree_node *,
+    struct rb_root_cached *);
+
+#endif	/* _LINUX_INTERVAL_TREE_H */
diff --git a/sys/compat/linuxkpi/common/include/linux/interval_tree_generic.h b/sys/compat/linuxkpi/common/include/linux/interval_tree_generic.h
new file mode 100644
index 000000000000..2ee615fda159
--- /dev/null
+++ b/sys/compat/linuxkpi/common/include/linux/interval_tree_generic.h
@@ -0,0 +1,99 @@
+/*-
+ * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
+ *
+ * Copyright (c) 2019 Mark Kettenis <kettenis@OpenBSD.org>
+ * Copyright (c) 2021 Vladimir Kondratyev <wulf@FreeBSD.org>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice unmodified, this list of conditions, and the following
+ *    disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <linux/rbtree.h>
+
+#define	INTERVAL_TREE_DEFINE(type, field, valtype, dummy, START, LAST, 	\
+		attr, name)						\
+	__IT_DEFINE_ITER_FROM(type, field, valtype, START, LAST, name)	\
+	__IT_DEFINE_ITER_FIRST(type, valtype, attr, name)		\
+	__IT_DEFINE_ITER_NEXT(type, field, valtype, attr, name)		\
+	__IT_DEFINE_INSERT(type, field, START, attr, name)		\
+	__IT_DEFINE_REMOVE(type, field, attr, name)
+
+#define	__IT_DEFINE_ITER_FROM(type, field, valtype, START, LAST, name)	\
+static inline type *							\
+name##_iter_from(struct rb_node *rb, valtype start, valtype last)	\
+{									\
+	type *node;							\
+									\
+	while (rb != NULL) {						\
+		node = rb_entry(rb, type, field);			\
+		if (LAST(node) >= start && START(node) <= last)		\
+			return (node);					\
+		else if (START(node) > last)				\
+			break;						\
+		rb = rb_next(rb);					\
+	}								\
+	return (NULL);							\
+}
+
+#define	__IT_DEFINE_ITER_FIRST(type, valtype, attr, name)		\
+attr type *								\
+name##_iter_first(struct rb_root_cached *root, valtype start, valtype last) \
+{									\
+	return (name##_iter_from(rb_first_cached(root), start, last));	\
+}
+
+#define	__IT_DEFINE_ITER_NEXT(type, field, valtype, attr, name)		\
+attr type *								\
+name##_iter_next(type *node, valtype start, valtype last)		\
+{									\
+	return (name##_iter_from(rb_next(&node->field), start, last));	\
+}
+
+#define	__IT_DEFINE_INSERT(type, field, START, attr, name)		\
+attr void								\
+name##_insert(type *node, struct rb_root_cached *root)			\
+{									\
+	struct rb_node **iter = &root->rb_root.rb_node;			\
+	struct rb_node *parent = NULL;					\
+	type *iter_node;						\
+	bool min_entry = true;						\
+									\
+	while (*iter != NULL) {						\
+		parent = *iter;						\
+		iter_node = rb_entry(parent, type, field);		\
+		if (START(node) < START(iter_node))			\
+			iter = &parent->rb_left;			\
+		else {							\
+			iter = &parent->rb_right;			\
+			min_entry = false;				\
+		}							\
+	}								\
+									\
+	rb_link_node(&node->field, parent, iter);			\
+	rb_insert_color_cached(&node->field, root, min_entry);		\
+}
+
+#define	__IT_DEFINE_REMOVE(type, field, attr, name)			\
+attr void								\
+name##_remove(type *node, struct rb_root_cached *root)			\
+{									\
+	rb_erase_cached(&node->field, root);				\
+}
diff --git a/sys/compat/linuxkpi/common/include/linux/rbtree.h b/sys/compat/linuxkpi/common/include/linux/rbtree.h
index 17d87f73ab75..b010c277ee1a 100644
--- a/sys/compat/linuxkpi/common/include/linux/rbtree.h
+++ b/sys/compat/linuxkpi/common/include/linux/rbtree.h
@@ -35,6 +35,7 @@
 #include <sys/stddef.h>
 #endif
 
+#include <sys/types.h>
 #include <sys/tree.h>
 
 struct rb_node {
@@ -51,6 +52,11 @@ struct rb_root {
 	struct	rb_node	*rb_node;
 };
 
+struct rb_root_cached {
+	struct rb_root rb_root;
+	struct rb_node *rb_leftmost;
+};
+
 /*
  * In linux all of the comparisons are done by the caller.
  */
@@ -76,6 +82,7 @@ RB_PROTOTYPE(linux_root, rb_node, __entry, panic_cmp);
 #define	rb_prev(node)	RB_PREV(linux_root, NULL, (node))
 #define	rb_first(root)	RB_MIN(linux_root, (struct linux_root *)(root))
 #define	rb_last(root)	RB_MAX(linux_root, (struct linux_root *)(root))
+#define	rb_first_cached(root)	(root)->rb_leftmost
 
 static inline struct rb_node *
 __rb_deepest_left(struct rb_node *node)
@@ -133,7 +140,39 @@ rb_replace_node(struct rb_node *victim, struct rb_node *new,
 	*new = *victim;
 }
 
+static inline void
+rb_insert_color_cached(struct rb_node *node, struct rb_root_cached *root,
+    bool leftmost)
+{
+	linux_root_RB_INSERT_COLOR((struct linux_root *)&root->rb_root, node);
+	if (leftmost)
+		root->rb_leftmost = node;
+}
+
+static inline struct rb_node *
+rb_erase_cached(struct rb_node *node, struct rb_root_cached *root)
+{
+	struct rb_node *retval;
+
+	if (node == root->rb_leftmost)
+		retval = root->rb_leftmost = linux_root_RB_NEXT(node);
+	else
+		retval = NULL;
+	linux_root_RB_REMOVE((struct linux_root *)&root->rb_root, node);
+	return (retval);
+}
+
+static inline void
+rb_replace_node_cached(struct rb_node *old, struct rb_node *new,
+    struct rb_root_cached *root)
+{
+	rb_replace_node(old, new, &root->rb_root);
+	if (root->rb_leftmost == old)
+		root->rb_leftmost = new;
+}
+
 #undef RB_ROOT
 #define RB_ROOT		(struct rb_root) { NULL }
+#define	RB_ROOT_CACHED	(struct rb_root_cached) { RB_ROOT, NULL }
 
 #endif	/* _LINUX_RBTREE_H_ */
diff --git a/sys/compat/linuxkpi/common/src/linux_compat.c b/sys/compat/linuxkpi/common/src/linux_compat.c
index 45b149a08ae8..9c6ed96c19b6 100644
--- a/sys/compat/linuxkpi/common/src/linux_compat.c
+++ b/sys/compat/linuxkpi/common/src/linux_compat.c
@@ -90,6 +90,8 @@ __FBSDID("$FreeBSD$");
 #include <linux/smp.h>
 #include <linux/wait_bit.h>
 #include <linux/rcupdate.h>
+#include <linux/interval_tree.h>
+#include <linux/interval_tree_generic.h>
 
 #if defined(__i386__) || defined(__amd64__)
 #include <asm/smp.h>
@@ -147,6 +149,12 @@ panic_cmp(struct rb_node *one, struct rb_node *two)
 
 RB_GENERATE(linux_root, rb_node, __entry, panic_cmp);
 
+#define	START(node)	((node)->start)
+#define	LAST(node)	((node)->last)
+
+INTERVAL_TREE_DEFINE(struct interval_tree_node, rb, unsigned long,, START,
+    LAST,, lkpi_interval_tree)
+
 int
 kobject_set_name_vargs(struct kobject *kobj, const char *fmt, va_list args)
 {