git: 10cb54117ee2 - stable/13 - LinuxKPI: Implement interval_tree
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Sat, 22 Jan 2022 19:36:16 UTC
The branch stable/13 has been updated by wulf:
URL: https://cgit.FreeBSD.org/src/commit/?id=10cb54117ee26ec57b6ba3b551a2212ffdbb06ac
commit 10cb54117ee26ec57b6ba3b551a2212ffdbb06ac
Author: Vladimir Kondratyev <wulf@FreeBSD.org>
AuthorDate: 2021-11-06 10:07:02 +0000
Commit: Vladimir Kondratyev <wulf@FreeBSD.org>
CommitDate: 2022-01-22 19:34:35 +0000
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)
---
.../linuxkpi/common/include/linux/interval_tree.h | 55 ++++++++++++
.../common/include/linux/interval_tree_generic.h | 99 ++++++++++++++++++++++
sys/compat/linuxkpi/common/include/linux/rbtree.h | 39 +++++++++
sys/compat/linuxkpi/common/src/linux_compat.c | 8 ++
4 files changed, 201 insertions(+)
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)
{