From nobody Sat Jan 22 19:36:16 2022 X-Original-To: dev-commits-src-all@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 06CFC196AEF1; Sat, 22 Jan 2022 19:36:19 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4Jh61Y5LDKz3R2v; Sat, 22 Jan 2022 19:36:17 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1642880178; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=Zo4FHrwPTTv0Iu/YKOMHiFpgHGIkUC8r1frgbTVwU9A=; b=pFRwcFAOQDrfSZYmEaxivAjxE7EtEgSMCkjk1rwcjQ6LOTBdEGAdTSUWMzIFcpHuE7pRXn 4Vi/csOYwZSIaNn7+YsCcq0lmx6jpVUKeMZvXj1b0qaPMdAUFXmajCcdxGRPcxjNV8eslP vWMdTH13ZQX/CHjFL1T8dktjk4yaQnqGycEcD5l/Gi/P9JYCovA6bcPI/xkdTyWpdKzTaW VLLcXunjq+CanIvi77UFwYtufaWtgcFj+L1AoRKrczIUXiToOfWlRHuypCAYwFhkGOSeF8 9IGf3SsFTH1Jtcb15BvpLsyuk2czw0Tv52RyAovkdCRAmmJrOTCgI2UpfLFJow== Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 03BD015032; Sat, 22 Jan 2022 19:36:17 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 20MJaGMZ099816; Sat, 22 Jan 2022 19:36:16 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 20MJaGFu099815; Sat, 22 Jan 2022 19:36:16 GMT (envelope-from git) Date: Sat, 22 Jan 2022 19:36:16 GMT Message-Id: <202201221936.20MJaGFu099815@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org From: Vladimir Kondratyev Subject: git: 10cb54117ee2 - stable/13 - LinuxKPI: Implement interval_tree List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: wulf X-Git-Repository: src X-Git-Refname: refs/heads/stable/13 X-Git-Reftype: branch X-Git-Commit: 10cb54117ee26ec57b6ba3b551a2212ffdbb06ac Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1642880178; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=Zo4FHrwPTTv0Iu/YKOMHiFpgHGIkUC8r1frgbTVwU9A=; b=POZX6uTgETptI0Iofeuq3VkUq0ALgN0u8zcSiCMRunjF0dSalvSb1C6l6hKRzycpf4Wvjl 15zLowitJipnX36nTcZp2vUS0Ys0zZ+QrXOz7nqESkbr/Ism3GtgXqs7p59VAoYZ8fLrBK O73HHA3cTqN1T6Xm9Hi0xnoqJQpLgzJ4KPitQ9rzeOelAyP9axfPZlSRzXY3gz7kWVuePF 6uKoJjuQrA4lc7X8863KIDWDe/jyb1uiYl3H68u+omKP6DbMNzU1JCc/k2mQAB2ppY+OjM OBTOrsq87RWue1+MbFX895GrbXtfpNAS/KHpa/KyuXfrg4V5vVGjaOSt5G3Zhw== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1642880178; a=rsa-sha256; cv=none; b=WObkEkqiWeAAzQyzx7JmeeYWeb2NiXGZIAZk+AcLbYbPEKtXm8P19uIoInvQOMELxSD8WY LoXAX8GRtidIOWlGdu+TQVt1uOxXJ8mWoYem1G3kOAzUeA9P8wXksTNjSCpc/QMziGQ6HN ycHu2iG2nv5XGew75d6Q5QZe1/CqCNLkxEwa2KsT5/8NG9UzctjsOBvtOqTXlD3vyVoxy8 1c722+j2ReCDBOQEJGycZOLrWppdgEaC1+9kSZGWn0IHOfi0jwSJXa6OYb4d3Ppu8ibIAv 6+zt7P59X/8Y6vqzGmquNm5Y4+Odd+t4TU5knStbUJUZVXyUvCs/01HZ4sfl8A== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N The branch stable/13 has been updated by wulf: URL: https://cgit.FreeBSD.org/src/commit/?id=10cb54117ee26ec57b6ba3b551a2212ffdbb06ac commit 10cb54117ee26ec57b6ba3b551a2212ffdbb06ac Author: Vladimir Kondratyev AuthorDate: 2021-11-06 10:07:02 +0000 Commit: Vladimir Kondratyev 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 + * + * 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 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 + * 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 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 #endif +#include #include 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 #include #include +#include +#include #if defined(__i386__) || defined(__amd64__) #include @@ -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) {