From nobody Mon Jan 10 19:50:30 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 CC96119541DC; Mon, 10 Jan 2022 19:50:30 +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 4JXkvV38Y7z3Ndc; Mon, 10 Jan 2022 19:50:30 +0000 (UTC) (envelope-from git@FreeBSD.org) 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 490452ED2; Mon, 10 Jan 2022 19:50:30 +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 20AJoUDV005073; Mon, 10 Jan 2022 19:50:30 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 20AJoUiK005072; Mon, 10 Jan 2022 19:50:30 GMT (envelope-from git) Date: Mon, 10 Jan 2022 19:50:30 GMT Message-Id: <202201101950.20AJoUiK005072@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Vladimir Kondratyev Subject: git: dbc920bd9a9b - main - 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/main X-Git-Reftype: branch X-Git-Commit: dbc920bd9a9b413182a1940155539a3144a405aa Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1641844230; 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=XEHhsXZSqigNcpw2jSoIRsvizwrGlZWpDv0I1W21cc0=; b=gBnWlX7vczQ7t0hQVejT+a7lsDpLGaTZGldLH7MXTqb9kNWPM3hQQm9Q9n18g7kyihkxu4 XqSPMO1RNKMhFLjL4rc3PHeHzSvZqVtTdQxYWM6Cw0OSHOEf0tGGyY63+SUnO+Q6hkP1of WBm3m1F/KHVkvnuV+m+wCmozaklN/9Ujt+uEOQpIKKJfrP0kJPUm57AEXrsmOOAvykzhMt 3q+aqFwnzP037cFl0SaiazS3+fZ9NlHkIRmyEAmasi+3tzvsTCvADOXGIj2O64eE4P8Dnz oWs0m7Srt6ebDMaBWYMQxm79bc5z3C2+22G3yDlxHquKTNPu981kEmhsRSqM9Q== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1641844230; a=rsa-sha256; cv=none; b=C8sscMGtUUyF4z1pUHeUafbZgrMsPzR5k5B5n890Wxr29k7KZQ9XCA90ylLW3zK67XZ9zL wugnvxTzX/a/vRq/7/aY5ppU0BcM80RIBShnIIdZK/wAZrDm6jhByGxVviV3lq17hgo5O3 N8YbLx6fq/V2gbiWp2AF1QnR0bUSGcCvwKSWCijtAYtnamEz5LqKXjNBnLyK4byVimviSL d4luvP+QMVfXfVp0E5Q81zX6jPzBopJX6/wDimJe+JmiIw9MgfjwbpSVV9Q1QUPzEt3Y+/ hjC4SvK9cqeEEurYDTGk22c71AwF7TPZzF/zt1V7b5RD6eU0+4PMhZdFmhzM6Q== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N The branch main has been updated by wulf: URL: https://cgit.FreeBSD.org/src/commit/?id=dbc920bd9a9b413182a1940155539a3144a405aa commit dbc920bd9a9b413182a1940155539a3144a405aa Author: Vladimir Kondratyev AuthorDate: 2021-11-06 10:07:02 +0000 Commit: Vladimir Kondratyev CommitDate: 2022-01-10 19:49:36 +0000 LinuxKPI: Implement interval_tree Required by drm-kmod MFC after: 1 week Reviewed by: hselasky, manu Differential Revision: https://reviews.freebsd.org/D32869 --- .../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 6440f7bdcff4..f375196aa72e 100644 --- a/sys/compat/linuxkpi/common/src/linux_compat.c +++ b/sys/compat/linuxkpi/common/src/linux_compat.c @@ -91,6 +91,8 @@ __FBSDID("$FreeBSD$"); #include #include #include +#include +#include #if defined(__i386__) || defined(__amd64__) #include @@ -148,6 +150,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) {