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 --- /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 + * + * 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 + +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 --- /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 + * Copyright (c) 2021 Vladimir Kondratyev + * + * 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 + +#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 --- a/sys/compat/linuxkpi/common/include/linux/rbtree.h +++ b/sys/compat/linuxkpi/common/include/linux/rbtree.h @@ -35,6 +35,7 @@ #include #endif +#include #include struct rb_node { @@ -51,6 +52,11 @@ 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 @@ #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 @@ *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 --- a/sys/compat/linuxkpi/common/src/linux_compat.c +++ b/sys/compat/linuxkpi/common/src/linux_compat.c @@ -91,6 +91,8 @@ #include #include #include +#include +#include #if defined(__i386__) || defined(__amd64__) #include @@ -148,6 +150,12 @@ 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) {