From patchwork Tue Nov 21 15:19:58 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Praveen Kumar X-Patchwork-Id: 10068465 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id EC7596022E for ; Tue, 21 Nov 2017 15:23:13 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id DE14629778 for ; Tue, 21 Nov 2017 15:23:13 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id D2BEE2976B; Tue, 21 Nov 2017 15:23:13 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-4.1 required=2.0 tests=BAYES_00, DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED, FREEMAIL_FROM, RCVD_IN_DNSWL_MED, T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) (using TLSv1.2 with cipher AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id 78B142976B for ; Tue, 21 Nov 2017 15:23:13 +0000 (UTC) Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.84_2) (envelope-from ) id 1eHAM0-0000El-DL; Tue, 21 Nov 2017 15:20:52 +0000 Received: from mail6.bemta6.messagelabs.com ([193.109.254.103]) by lists.xenproject.org with esmtp (Exim 4.84_2) (envelope-from ) id 1eHALz-0000BG-JD for xen-devel@lists.xen.org; Tue, 21 Nov 2017 15:20:51 +0000 Received: from [193.109.254.147] by server-5.bemta-6.messagelabs.com id F9/76-10664-354441A5; Tue, 21 Nov 2017 15:20:51 +0000 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFtrHIsWRWlGSWpSXmKPExsVyMfTAEd0gF5E og1XLdS2WfFzM4sDocXT3b6YAxijWzLyk/IoE1oyWuZ9YCtYIVDw/VNLA+IC3i5GLQ0hgEqPE nYX9TCAOi8BLFomDTddYQBwJgX5WiV3XNzJ3MXICOVkSp25/YYSw0yQautcxQdiVEg27P7CA2 EICahJb5p1ihhj7jlFizq65QEUcHGwCuhLttwpAakQEpCWufb7MCFLDLPCdUWLN+ymsIAlhgW SJC1emgdksAqoSE6+tYAexeQVsJNa8/A11hLzEtHe9YDWcArYSlw5+YoNYbCPxb+4TtgmMggs YGVYxahSnFpWlFukaGeolFWWmZ5TkJmbm6BoamOnlphYXJ6an5iQmFesl5+duYgSGHAMQ7GD8 syzgEKMkB5OSKK+kqUiUEF9SfkplRmJxRnxRaU5q8SFGGQ4OJQnew05AOcGi1PTUirTMHGDww 6QlOHiURHhbQdK8xQWJucWZ6RCpU4z2HBfuXPrDxHFgzy0g+Wzm6wZmjmlXW5uYhVjy8vNSpc R5L4O0CYC0ZZTmwQ2FReslRlkpYV5GoDOFeApSi3IzS1DlXzGKczAqCfPOApnCk5lXArf7FdB ZTEBn/TwuDHJWSSJCSqqBUXvl8hmzjC6cCKuZe6o4seqRmMOhrJPaEdxrfz+fs27pEcVyLseL 33IeMxy4o2V+5Ora9S5R3YsCnG4tnLh+stv3c2ufrfvuFP/FMvjVz07bw7dX7bBSPHo2REbyZ 7NtxfUtNW8vc6QfOcopVlA9Kf9jRGe5ZPD0O64KCadmJWYud5q4PkKMxUyJpTgj0VCLuag4EQ Aowz+f0QIAAA== X-Env-Sender: kpraveen.lkml@gmail.com X-Msg-Ref: server-8.tower-27.messagelabs.com!1511277649!107226553!1 X-Originating-IP: [209.85.192.196] X-SpamReason: No, hits=0.0 required=7.0 tests= X-StarScan-Received: X-StarScan-Version: 9.4.45; banners=-,-,- X-VirusChecked: Checked Received: (qmail 25175 invoked from network); 21 Nov 2017 15:20:50 -0000 Received: from mail-pf0-f196.google.com (HELO mail-pf0-f196.google.com) (209.85.192.196) by server-8.tower-27.messagelabs.com with AES128-GCM-SHA256 encrypted SMTP; 21 Nov 2017 15:20:50 -0000 Received: by mail-pf0-f196.google.com with SMTP id a84so10071762pfl.0 for ; Tue, 21 Nov 2017 07:20:50 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=JPJ0hQcR509iU7vtmQhOFI6uVWLa1E11MY1/tT/UaoY=; b=uHFeS8MVOmzEqOgfowDtP6fZZp8w4D5ZfRpF8q/2Ub9aWysp8RPZ2x3F1+tUj1OHdr DH/t8BJeKXkN6AY+1nPT932qUqbgImA9ohqJ+Km46KciDR3cwjiEAeL7mw3scDChCecl IsNji2uUNR8bys3pcpD3kXJwuPmFAGqPM+3m+9TdAJrweDGpWNwNAodVGPkmQZkb8BHP EYY/996pMbTjBClLeA/2rerrFWMmME/JwkWkSKig6ve5UWQdLLIukqgQ0nLexE/5t9l/ C3Q6AikmwgYvI9NzOOrny21uAOGxFomC8RIen74Qa+4lnZKPeukFsJzLgjSXFNvzsYBP OUvA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=JPJ0hQcR509iU7vtmQhOFI6uVWLa1E11MY1/tT/UaoY=; b=Jtaw/BWSjhGawQL3SauTg3T/vkX4O+Ux3Cv5OHHOr2fLCPKTPdOe8mr0cZNqBAmVfS ZSsV02iWfm9z4M+zrn1ZGpyuez4Khbhi+GZwtbp338KwtWQ9Kvrz15DEbZE2zD50PnFy pB6LQa1TIzOWNtUTRb+pX1FNX/v6+gkvDQkBWyEXs6LLALR2RGXXSwV+SV8IRzeHZ5lZ l+zXp5ujqM54FEydd+mLNS/jIrSFsE9Kad3ByHOMxpLAbm/jpGxiB+KFYyiKaseUe8FF sUTjOCq0LNsEt6l+Vskl442H6xWRMbokoDXEJP73F03HRbJ6gbv8nRw7dOZZXqD9v7C0 a53Q== X-Gm-Message-State: AJaThX6Jvdb+cCc6Jtzg6dyBE2E7BAsoCYcz4+xHNNJLXTrLVZhoj+md LSCMtlRSphRwwIYgKokn5RgndA== X-Google-Smtp-Source: AGs4zMasE0MfLCCCuAf689XYeIBPsd8UHbCLj0uDCh0mA7aT+XISdLBXmaTePfZIYfAEeZ2DAQU3IQ== X-Received: by 10.99.140.22 with SMTP id m22mr17982854pgd.47.1511277648863; Tue, 21 Nov 2017 07:20:48 -0800 (PST) Received: from praveen.name ([106.51.29.204]) by smtp.gmail.com with ESMTPSA id 3sm26905504pfo.17.2017.11.21.07.20.45 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Tue, 21 Nov 2017 07:20:48 -0800 (PST) From: Praveen Kumar To: xen-devel@lists.xen.org Date: Tue, 21 Nov 2017 20:49:58 +0530 Message-Id: <20171121152009.15591-6-kpraveen.lkml@gmail.com> X-Mailer: git-send-email 2.13.1 In-Reply-To: <20171121152009.15591-1-kpraveen.lkml@gmail.com> References: <20171121152009.15591-1-kpraveen.lkml@gmail.com> Cc: sstabellini@kernel.org, wei.liu2@citrix.com, konrad.wilk@oracle.com, George.Dunlap@eu.citrix.com, andrew.cooper3@citrix.com, dario.faggioli@citrix.com, ian.jackson@eu.citrix.com, tim@xen.org, kpraveen.lkml@gmail.com, jbeulich@suse.com Subject: [Xen-devel] [PATCH v6 05/16 RESEND] rbtree: adjust root color in rb_insert_color() only when necessary X-BeenThere: xen-devel@lists.xen.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: xen-devel-bounces@lists.xen.org Sender: "Xen-devel" X-Virus-Scanned: ClamAV using ClamSMTP From: Michel Lespinasse The root node of an rbtree must always be black. However, rb_insert_color() only needs to maintain this invariant when it has been broken - that is, when it exits the loop due to the current (red) node being the root. In all other cases (exiting after tree rotations, or exiting due to an existing black parent) the invariant is already satisfied, so there is no need to adjust the root node color. Signed-off-by: Michel Lespinasse Cc: Andrea Arcangeli Acked-by: David Woodhouse Cc: Rik van Riel Cc: Peter Zijlstra Cc: Daniel Santos Cc: Jens Axboe Cc: "Eric W. Biederman" Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds [Linux commit 6d58452dc066db61acdff7b84671db1b11a3de1c] Ported to Xen. Signed-off-by: Praveen Kumar --- xen/common/rbtree.c | 19 +++++++++++++++---- 1 file changed, 15 insertions(+), 4 deletions(-) diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c index 9dc296e0d8..244f1d8818 100644 --- a/xen/common/rbtree.c +++ b/xen/common/rbtree.c @@ -91,8 +91,21 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) { struct rb_node *parent, *gparent; - while ((parent = rb_parent(node)) && rb_is_red(parent)) - { + while (true) { + /* + * Loop invariant: node is red + * + * If there is a black parent, we are done. + * Otherwise, take some corrective action as we don't + * want a red root or two consecutive red nodes. + */ + parent = rb_parent(node); + if (!parent) { + rb_set_black(node); + break; + } else if (rb_is_black(parent)) + break; + gparent = rb_parent(parent); if (parent == gparent->rb_left) @@ -142,8 +155,6 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) break; } } - - rb_set_black(root->rb_node); } EXPORT_SYMBOL(rb_insert_color);