From nobody Wed Oct 12 03:00:23 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 4MnHT36cwFz4f7c1; Wed, 12 Oct 2022 03:00:23 +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 4MnHT35sWDz4H26; Wed, 12 Oct 2022 03:00:23 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1665543623; 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=WlpLmfrNa0Di+sj36rBRfok++1OcLtlv4UqqDm0cusM=; b=usFkTDLuG3+KkONFt+Er+qooDK+D0hHP5M27qGzvAzabmeDLLZBW1i1f0CNm8yaoAEIukC qvh8Iu9Xzh2ocF0g0z5cu6wgxm9nNNuPKOttnR5XIXv63ZlE9xaCqMCJKI3A0jIsrc9y+m /WqAkkyBHZFjavjjSlhXEHBWexNFbdtZ4H3mQAqebGdknNhvEIRWnKWVRuS7R/GyD5QFP3 5yLEIm61RKWfFvT9ORUfEY/K5gSzMVYKWJKeKykvw6FAjSCFEgNb+Qiothw07uDpapbcfV nWW6r3zfyoJdr5Y34oeZ/yPoKWSX58O85i0P606t6PjBSd8kSnMgrcF21estVQ== 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 4MnHT34wHQz19hF; Wed, 12 Oct 2022 03:00:23 +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 29C30NhC079472; Wed, 12 Oct 2022 03:00:23 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 29C30NVa079471; Wed, 12 Oct 2022 03:00:23 GMT (envelope-from git) Date: Wed, 12 Oct 2022 03:00:23 GMT Message-Id: <202210120300.29C30NVa079471@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: deeaf9c4d85d - stable/13 - rb_tree: pass parent to RB_INSERT_COLOR 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: deeaf9c4d85d937d3c935291e913ae614a28f824 Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1665543623; 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=WlpLmfrNa0Di+sj36rBRfok++1OcLtlv4UqqDm0cusM=; b=IuPakL0Nmd5S1brfn9MnE9/uq5++YEnQKTejtpYm8jchyIzzo5Woll7OoEI5+n7tX+m7Jk WGnSG4EFOo7e5PnTRUFqYU5kcdXNR6lGXpjYZbVHvZ53iCu5CG/Qbr+9gRUYEYROsg1jlV igsYnHKiWOV6Z109E/E5dPkjcTvrdVNtW4O32WHQyR/nRTat6FFhjL908gIyCiNKawlAmm RYQ5u4t5PrJcGR8ns9OrCnaUaV07UxAltV6A3R9qNOGZQUyzSYUPYBO2AT8bmA/wNVGsTj ZvaGYLWg/kKWqUoKHAuYCZ06bBgBKr8xL7/paGV8ZeffngeoHkj9oA8bTP+Qqg== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1665543623; a=rsa-sha256; cv=none; b=pgr8FLwB7Lhg0XVelBASB6L35ZxC/isGE7aJ71uCaW+wi7N9BGFV0G7i8Hhp0bAOcKCgVw ZHUt1YcpXwjlpgg2rPy6u/bP++FiF+bGCPMlengONIcmuA0xP4lb0R3UQclkw8FqjAxdo2 QOHLeh23BG9bvexJHFS9ZoAB1OZhK66mFhq3zu+f8sMlWM7dXUxHje7FHlj5lG+uLQBvXl fwu6zy4rAhUInCyUzcqSt4AJbddlohCxPN4WWS/6Gog+hJIcb+afNCs3M9TKvAESQ91bkJ g9AxN+3ePmeMM6HKQ4xGEHrWgwT5U3kA8LbpTpHsh96RV2zgh33g66iQ4RLFiQ== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N The branch stable/13 has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=deeaf9c4d85d937d3c935291e913ae614a28f824 commit deeaf9c4d85d937d3c935291e913ae614a28f824 Author: Doug Moore AuthorDate: 2022-09-13 06:11:47 +0000 Commit: Doug Moore CommitDate: 2022-10-12 02:42:55 +0000 rb_tree: pass parent to RB_INSERT_COLOR Change RB_COLOR_INSERT to take a parent parameter, to avoid looking up a value already available. Make adjustments to a linux rbtree header, which invokes it. Reviewed by: alc, hselasky Differential Revision: https://reviews.freebsd.org/D36114 (cherry picked from commit 4893472c9a18cd8ce3b68d0c54084ef6f0285d0f) --- sys/compat/linuxkpi/common/include/linux/rbtree.h | 11 ++++++++--- sys/sys/tree.h | 18 ++++++++++-------- 2 files changed, 18 insertions(+), 11 deletions(-) diff --git a/sys/compat/linuxkpi/common/include/linux/rbtree.h b/sys/compat/linuxkpi/common/include/linux/rbtree.h index 1f337d59545c..37537d4b2724 100644 --- a/sys/compat/linuxkpi/common/include/linux/rbtree.h +++ b/sys/compat/linuxkpi/common/include/linux/rbtree.h @@ -74,8 +74,11 @@ 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) \ - linux_root_RB_INSERT_COLOR((struct linux_root *)(root), (node)) +#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_erase(node, root) \ linux_root_RB_REMOVE((struct linux_root *)(root), (node)) #define rb_next(node) RB_NEXT(linux_root, NULL, (node)) @@ -145,7 +148,9 @@ 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 (rb_parent(node)) + linux_root_RB_INSERT_COLOR((struct linux_root *)&root->rb_root, + rb_parent(node), node); if (leftmost) root->rb_leftmost = node; } diff --git a/sys/sys/tree.h b/sys/sys/tree.h index 6a64498f6deb..c0cd65f41acb 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -422,7 +422,8 @@ struct { \ #define RB_PROTOTYPE_RANK(name, type, attr) #endif #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ - attr void name##_RB_INSERT_COLOR(struct name *, struct type *) + attr void name##_RB_INSERT_COLOR(struct name *, \ + struct type *, struct type *) #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ attr void name##_RB_REMOVE_COLOR(struct name *, \ struct type *, struct type *) @@ -491,7 +492,8 @@ name##_RB_RANK(struct type *elm) \ #define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ attr void \ -name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ +name##_RB_INSERT_COLOR(struct name *head, \ + struct type *parent, struct type *elm) \ { \ /* \ * Initially, elm is a leaf. Either its parent was previously \ @@ -503,12 +505,11 @@ name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ * uninitialized 'child', and a later iteration can only happen \ * when a value has been assigned to 'child' in the previous \ * one. \ - */ \ - struct type *child, *child_up, *gpar, *parent; \ + */ \ + struct type *child, *child_up, *gpar; \ __uintptr_t elmdir, sibdir; \ \ - gpar = _RB_UP(elm, field); \ - while ((parent = gpar) != NULL) { \ + do { \ /* the rank of the tree rooted at elm grew */ \ gpar = _RB_UP(parent, field); \ elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \ @@ -584,7 +585,7 @@ name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ RB_AUGMENT(elm); \ RB_AUGMENT(parent); \ break; \ - } \ + } while ((parent = gpar) != NULL); \ } #ifndef RB_STRICT_HST @@ -774,7 +775,8 @@ name##_RB_INSERT(struct name *head, struct type *elm) \ } \ RB_SET(elm, parent, field); \ *tmpp = elm; \ - name##_RB_INSERT_COLOR(head, elm); \ + if (parent != NULL) \ + name##_RB_INSERT_COLOR(head, parent, elm); \ RB_UPDATE_AUGMENT(elm, field); \ return (NULL); \ }