From nobody Sat Jan 22 19:36:15 2022 X-Original-To: dev-commits-src-branches@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 26D55196AED4; Sat, 22 Jan 2022 19:36:16 +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 4Jh61X0Tfrz3R9y; Sat, 22 Jan 2022 19:36:16 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1642880176; 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=khb08/fihcfptquVjT/ChJpqExH/tDYaBcoqXE3BV8k=; b=eVpGa/GDpByMKIkofHUriVpp0wUWQacKM8MYqIlTKkVwlYLhuA32JFoEjTBLy3HQF9yNh5 z/3t4uqa4r6CLPqzPzPWH6Adi7Rdi6Rhplo8WBKHknStBJvQIxJlql9729Mp6UGGjsJll6 m2j9i79/lUo7OH9+a+CjhDc6JjuXt+NG91JA7A+W6JksoqRDFhtKMx4p4emSmTqsYDB6Cg BgNq62VzSiDYy0nIA/AizkNAqydxOwxAgdM+F/ouAVG4FAD9z6KHKF1tPa1wYkZq9+EhLU h/68/HUcNfYW6r/hghdME/kFBh4XY/ynLVYin8Wa2ROWlOnf4APpf5LFaYvK1g== 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 DDAA314CCB; Sat, 22 Jan 2022 19:36:15 +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 20MJaFdB099785; Sat, 22 Jan 2022 19:36:15 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 20MJaFTr099784; Sat, 22 Jan 2022 19:36:15 GMT (envelope-from git) Date: Sat, 22 Jan 2022 19:36:15 GMT Message-Id: <202201221936.20MJaFTr099784@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: c8ddc214cf76 - stable/13 - LinuxKPI: Import some linux/rbtree.h functions from OpenBSD List-Id: Commits to the stable branches of the FreeBSD src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-branches List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-branches@freebsd.org X-BeenThere: dev-commits-src-branches@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: c8ddc214cf76785e99358a92700f68c148d63365 Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1642880176; 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=khb08/fihcfptquVjT/ChJpqExH/tDYaBcoqXE3BV8k=; b=O1JE7NWEj90oZSgm9HRzmngDlOz3a6xXjIkfeYpNu46QWj2w4Lt04ZZxwOKya3ueHIbdES keaq+W3lLsYAOj8diHs+EbS1gAE7Xh5jJIAlaGMOi1M3P9tnWPNWBRsshpOIHAIwkcBvfV tJporx/0zsKHJyCk76roZ9BaD44rmbrvQTUU/ztcBgjMkWJJDespb+3tSlbrh0CjmZ4Y+j 1HH94hx2W7s9ebkQf/MVdug+yqml+Db4rZeDJ4KvDm3sskbcTGJz3oOJyCAI9w0WLxKX5r 4OsOZuezQPlVxOl0ylB0YsQieJbTcEkpEZE1EECZ30Q5lMbVzH3i9Z7DZMQbIg== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1642880176; a=rsa-sha256; cv=none; b=na3WaHeyoWw5+euyo0Gva/P3f992TtcPznvf5h24pgHEPzARB0gSQpBAW6JlfuOiMwUEW9 YnIHbNN3X1NkHuBuVdtGO+Us1TUihDN0BjhA9XaNec6dYRjzvwJlUyw1NNsoQuZHAzpn2f tXx2+u8oXp025tDJ2fm8P3WRdwFCdyYym9dPF60AxTw+y6ibpUGS1uDhcLNJPizTMMp/eo YUKNeD7IbCjT4uxdJpFRWtrW+s8lwr2erXL2/4kgboYal7IcPGqBdKKL8iyGu2qDwVP7Ta O0ZzaiPLfLf1rSZtslhYJmLCfCYaxJprWkFiddUIO0aC4QpMLFQnMhAECAHLGA== 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=c8ddc214cf76785e99358a92700f68c148d63365 commit c8ddc214cf76785e99358a92700f68c148d63365 Author: Vladimir Kondratyev AuthorDate: 2021-11-05 11:43:31 +0000 Commit: Vladimir Kondratyev CommitDate: 2022-01-22 19:34:35 +0000 LinuxKPI: Import some linux/rbtree.h functions from OpenBSD Required by drm-kmod Obtained from: OpenBSD MFC after: 1 week (cherry picked from commit dd52763387abd18bb6ac510b1148632a13b945f0) --- sys/compat/linuxkpi/common/include/linux/rbtree.h | 40 ++++++++++++++++++++++- 1 file changed, 39 insertions(+), 1 deletion(-) diff --git a/sys/compat/linuxkpi/common/include/linux/rbtree.h b/sys/compat/linuxkpi/common/include/linux/rbtree.h index 78da33ad2658..17d87f73ab75 100644 --- a/sys/compat/linuxkpi/common/include/linux/rbtree.h +++ b/sys/compat/linuxkpi/common/include/linux/rbtree.h @@ -59,9 +59,12 @@ int panic_cmp(struct rb_node *one, struct rb_node *two); RB_HEAD(linux_root, rb_node); RB_PROTOTYPE(linux_root, rb_node, __entry, panic_cmp); +#define rb_parent(r) RB_PARENT(r, __entry) #define rb_entry(ptr, type, member) container_of(ptr, type, member) +#define rb_entry_safe(ptr, type, member) \ + ((ptr) != NULL ? rb_entry(ptr, type, member) : NULL) -#define RB_EMPTY_ROOT(root) RB_EMPTY((struct linux_root *)root) +#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) #define RB_EMPTY_NODE(node) (RB_PARENT(node, __entry) == node) #define RB_CLEAR_NODE(node) RB_SET_PARENT(node, node, __entry) @@ -74,6 +77,41 @@ RB_PROTOTYPE(linux_root, rb_node, __entry, panic_cmp); #define rb_first(root) RB_MIN(linux_root, (struct linux_root *)(root)) #define rb_last(root) RB_MAX(linux_root, (struct linux_root *)(root)) +static inline struct rb_node * +__rb_deepest_left(struct rb_node *node) +{ + struct rb_node *parent = NULL; + while (node != NULL) { + parent = node; + if (RB_LEFT(node, __entry)) + node = RB_LEFT(node, __entry); + else + node = RB_RIGHT(node, __entry); + } + return (parent); +} + +static inline struct rb_node * +rb_next_postorder(const struct rb_node *node) +{ + struct rb_node *parent = + RB_PARENT(__DECONST(struct rb_node *, node), __entry); + /* left -> right, right -> root */ + if (parent != NULL && + (node == RB_LEFT(parent, __entry)) && + (RB_RIGHT(parent, __entry))) + return (__rb_deepest_left(RB_RIGHT(parent, __entry))); + else + return (parent); +} + +#define rbtree_postorder_for_each_entry_safe(x, y, head, member) \ + for ((x) = rb_entry_safe(__rb_deepest_left((head)->rb_node), \ + __typeof(*x), member); \ + ((x) != NULL) && ((y) = \ + rb_entry_safe(rb_next_postorder(&x->member), typeof(*x), member), 1); \ + (x) = (y)) + static inline void rb_link_node(struct rb_node *node, struct rb_node *parent, struct rb_node **rb_link)