From nobody Fri Dec 16 09:18:51 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 4NYNnm1p3czQW2T; Fri, 16 Dec 2022 09:18:52 +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 4NYNnm0q81z420j; Fri, 16 Dec 2022 09:18:52 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1671182332; 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=Jf6JfzJTo/7R5WL0/hWhgn+risSYk3rLLI6ehIzEMqU=; b=OXkHKzyU+i6tZSPAjvIUSfetzgplMS1HN6kKoB8+7V969CBVXnh276Coosblfg1XVmdkhB YV59p1vuY5hM1KUkIuP9TeKFBRWdOASSXFMySNikUho028prs3sLGO9DojV3b/9JyCC3MD xco9+DJg1txkVPSmTdxNwM9LFCrgFb5IziS2h4mOgG49PwrAuAbqnFyGF78DDJW8nnrvic OlXXo3UjIedyr0NLNz4xu1WlTANkjiyHQ6yKYLeSvRBpRgSJdrg56F+5Jvhgs5GOthLCLo m3ySshb+1gPyEm9kif2d/TrCj5szzWFAgV+2by/ZcpGmGYs0/9ujckcCCiepuw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1671182332; 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=Jf6JfzJTo/7R5WL0/hWhgn+risSYk3rLLI6ehIzEMqU=; b=Qj2PelCX9JMZYSGsvHQx3zoa2jdKuVJS2VSVgRL4FqxlEgMdNdyB/I0T6/8BuxZTcypLYe HOftpB4WK/HoF1x0ophAhdyEsYhm9QmMFtAxYHKT4R0pbeDMS2kFv/pmbBg8eB01xKlZYr NzDtuKwi/RhvnJ8QT/e4oBfgQgqch6Gsmx7pKiN2WDrUumEcZKG82rQ1cS9gcWTIj9Cjz6 a1vq3tuNyFLVZ+5+PYip0HZrW8OwP1NidiXJ62XKiNwKU38GsftN3KVU0KM/QimIkJ5ekU ddgGp1+Qbxy6ful4hnj2rLZX5aCaZ0tLVJvO3hnSXKQLy7KXFIGypQvuJvj95A== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1671182332; a=rsa-sha256; cv=none; b=YnUwP/fswVLjrkAbB1inqIPoPOHUGKg5tyYtGNhzHSMWRBEFVhrMQ2DBlDrGox8wOtxO71 EOKz6LkmecQiO6TSNE2xunz30o3QG807ARkZ43rHXYEljVWmbI6a4FgA6K49R6ENW2oF5w cTz6USEv1AS4CKk6rKk3oWxdv48kxxk1+O4f0G+c8PdVCibY4Z0dO0epKAy44cpAY9xizV 25cZrYOiyU6+uDsz/LdUSWIPGcrvrwuvGquqd7VWQs6xQaqYakw4Hdg85+A106tcB1DR1N kujXXWWlqKAOOKZLxPyWU2hGIugsn6oqi5OF93TShj9hXmTZQLqS0kCCGeVeLA== 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 4NYNnl6zycz16r4; Fri, 16 Dec 2022 09:18:51 +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 2BG9Ipfi056319; Fri, 16 Dec 2022 09:18:51 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 2BG9Ip2d056318; Fri, 16 Dec 2022 09:18:51 GMT (envelope-from git) Date: Fri, 16 Dec 2022 09:18:51 GMT Message-Id: <202212160918.2BG9Ip2d056318@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org From: Doug Moore Subject: git: d8a88ec38149 - stable/13 - rb_tree: restore binary compat w/ 13 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: dougm X-Git-Repository: src X-Git-Refname: refs/heads/stable/13 X-Git-Reftype: branch X-Git-Commit: d8a88ec381498f5942403088d28ee325b92e9a78 Auto-Submitted: auto-generated X-ThisMailContainsUnwantedMimeParts: N The branch stable/13 has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=d8a88ec381498f5942403088d28ee325b92e9a78 commit d8a88ec381498f5942403088d28ee325b92e9a78 Author: Doug Moore AuthorDate: 2022-12-16 09:15:28 +0000 Commit: Doug Moore CommitDate: 2022-12-16 09:15:28 +0000 rb_tree: restore binary compat w/ 13 A change to RB_COLOR_INSERT, when merged into stable/13, broke binary compatibility. For 13, call the new function RB_DO_COLOR_INSERT, and restore the old function with the original name and parameters. Define RB_COLOR_INSERT in tree.h, and remove changes to the linux rbtree header. Another change altered the order of pointers in the RB_ENTRY struct. For 13, restore the original order. Reported by: manu Reviewed by: hselasky Tested by: manu Differential Revision: https://reviews.freebsd.org/D37716 --- sys/compat/linuxkpi/common/include/linux/rbtree.h | 11 ++---- sys/sys/tree.h | 46 ++++++++++++++++------- 2 files changed, 35 insertions(+), 22 deletions(-) diff --git a/sys/compat/linuxkpi/common/include/linux/rbtree.h b/sys/compat/linuxkpi/common/include/linux/rbtree.h index 37537d4b2724..de21f0e4c613 100644 --- a/sys/compat/linuxkpi/common/include/linux/rbtree.h +++ b/sys/compat/linuxkpi/common/include/linux/rbtree.h @@ -74,11 +74,8 @@ RB_PROTOTYPE(linux_root, rb_node, __entry, panic_cmp); #define RB_EMPTY_NODE(node) (RB_PARENT(node, __entry) == node) #define RB_CLEAR_NODE(node) RB_SET_PARENT(node, node, __entry) -#define rb_insert_color(node, root) do { \ - if (rb_parent(node)) \ - linux_root_RB_INSERT_COLOR((struct linux_root *)(root), \ - rb_parent(node), (node)); \ -} while (0) +#define rb_insert_color(node, root) \ + linux_root_RB_INSERT_COLOR((struct linux_root *)(root), (node)) #define rb_erase(node, root) \ linux_root_RB_REMOVE((struct linux_root *)(root), (node)) #define rb_next(node) RB_NEXT(linux_root, NULL, (node)) @@ -148,9 +145,7 @@ static inline void rb_insert_color_cached(struct rb_node *node, struct rb_root_cached *root, bool leftmost) { - if (rb_parent(node)) - linux_root_RB_INSERT_COLOR((struct linux_root *)&root->rb_root, - rb_parent(node), node); + linux_root_RB_INSERT_COLOR((struct linux_root *)&root->rb_root, node); if (leftmost) root->rb_leftmost = node; } diff --git a/sys/sys/tree.h b/sys/sys/tree.h index 0fb3cf94eebc..d6408c045913 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -331,7 +331,7 @@ struct { \ * that the left or right child of the tree node is "red". */ #define _RB_LINK(elm, dir, field) (elm)->field.rbe_link[dir] -#define _RB_UP(elm, field) _RB_LINK(elm, 0, field) +#define _RB_UP(elm, field) _RB_LINK(elm, 2, field) #define _RB_L ((__uintptr_t)1) #define _RB_R ((__uintptr_t)2) #define _RB_LR ((__uintptr_t)3) @@ -341,8 +341,8 @@ struct { \ ((__uintptr_t)elm & ~_RB_LR) #define RB_PARENT(elm, field) _RB_PTR(_RB_UP(elm, field)) -#define RB_LEFT(elm, field) _RB_LINK(elm, _RB_L, field) -#define RB_RIGHT(elm, field) _RB_LINK(elm, _RB_R, field) +#define RB_LEFT(elm, field) _RB_LINK(elm, _RB_L-1, field) +#define RB_RIGHT(elm, field) _RB_LINK(elm, _RB_R-1, field) #define RB_ROOT(head) (head)->rbh_root #define RB_EMPTY(head) (RB_ROOT(head) == NULL) @@ -398,10 +398,10 @@ struct { \ * update the same pair of pointer fields with distinct values. */ #define RB_ROTATE(elm, tmp, dir, field) do { \ - if ((_RB_LINK(elm, dir ^ _RB_LR, field) = \ - _RB_LINK(tmp, dir, field)) != NULL) \ - RB_SET_PARENT(_RB_LINK(tmp, dir, field), elm, field); \ - _RB_LINK(tmp, dir, field) = (elm); \ + if ((_RB_LINK(elm, (dir ^ _RB_LR)-1, field) = \ + _RB_LINK(tmp, dir-1, field)) != NULL) \ + RB_SET_PARENT(_RB_LINK(tmp, dir-1, field), elm, field); \ + _RB_LINK(tmp, dir-1, field) = (elm); \ RB_SET_PARENT(elm, tmp, field); \ } while (/*CONSTCOND*/ 0) @@ -412,6 +412,7 @@ struct { \ RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ RB_PROTOTYPE_RANK(name, type, attr) \ + RB_PROTOTYPE_DO_INSERT_COLOR(name, type, attr); \ RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ RB_PROTOTYPE_INSERT_FINISH(name, type, attr); \ @@ -431,9 +432,11 @@ struct { \ #else #define RB_PROTOTYPE_RANK(name, type, attr) #endif -#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ - attr struct type *name##_RB_INSERT_COLOR(struct name *, \ +#define RB_PROTOTYPE_DO_INSERT_COLOR(name, type, attr) \ + attr struct type *name##_RB_DO_INSERT_COLOR(struct name *, \ struct type *, struct type *) +#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ + attr struct type *name##_RB_INSERT_COLOR(struct name *, struct type *) #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ attr struct type *name##_RB_REMOVE_COLOR(struct name *, \ struct type *, struct type *) @@ -472,6 +475,7 @@ struct { \ RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ RB_GENERATE_RANK(name, type, field, attr) \ + RB_GENERATE_DO_INSERT_COLOR(name, type, field, attr) \ RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ RB_GENERATE_INSERT_FINISH(name, type, field, attr) \ @@ -522,9 +526,9 @@ name##_RB_RANK(struct type *elm) \ #define RB_GENERATE_RANK(name, type, field, attr) #endif -#define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ +#define RB_GENERATE_DO_INSERT_COLOR(name, type, field, attr) \ attr struct type * \ -name##_RB_INSERT_COLOR(struct name *head, \ +name##_RB_DO_INSERT_COLOR(struct name *head, \ struct type *parent, struct type *elm) \ { \ /* \ @@ -625,6 +629,20 @@ name##_RB_INSERT_COLOR(struct name *head, \ return (NULL); \ } +#define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ +attr struct type * \ +name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ +{ \ + struct type *parent, *tmp; \ + \ + parent = RB_PARENT(elm, field); \ + if (parent != NULL) \ + tmp = name##_RB_DO_INSERT_COLOR(head, parent, elm); \ + else \ + tmp = NULL; \ + return (tmp); \ +} + #ifndef RB_STRICT_HST /* * In REMOVE_COLOR, the HST paper, in figure 3, in the single-rotate case, has @@ -671,7 +689,7 @@ name##_RB_REMOVE_COLOR(struct name *head, \ continue; \ } \ sibdir = elmdir ^ _RB_LR; \ - sib = _RB_LINK(parent, sibdir, field); \ + sib = _RB_LINK(parent, sibdir-1, field); \ up = _RB_UP(sib, field); \ _RB_BITS(up) ^= _RB_LR; \ if ((_RB_BITS(up) & _RB_LR) == 0) { \ @@ -700,7 +718,7 @@ name##_RB_REMOVE_COLOR(struct name *head, \ * / z \ * y \ */ \ - elm = _RB_LINK(sib, elmdir, field); \ + elm = _RB_LINK(sib, elmdir-1, field); \ /* elm is a 1-child. First rotate at elm. */ \ RB_ROTATE(sib, elm, sibdir, field); \ up = _RB_UP(elm, field); \ @@ -826,7 +844,7 @@ name##_RB_INSERT_FINISH(struct name *head, struct type *parent, \ RB_SET(elm, parent, field); \ *pptr = elm; \ if (parent != NULL) \ - tmp = name##_RB_INSERT_COLOR(head, parent, elm); \ + tmp = name##_RB_DO_INSERT_COLOR(head, parent, elm); \ _RB_AUGMENT_WALK(elm, tmp, field); \ if (tmp != NULL) \ /* \