From patchwork Wed May 31 21:20:48 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Praveen Kumar X-Patchwork-Id: 9758169 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 9E569603F7 for ; Wed, 31 May 2017 21:24:16 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 910C527569 for ; Wed, 31 May 2017 21:24:16 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 85BE8284D2; Wed, 31 May 2017 21:24:16 +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=-3.6 required=2.0 tests=BAYES_00, DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED, FREEMAIL_FROM, RCVD_IN_DNSWL_MED, RCVD_IN_SORBS_SPAM, 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 33D3727569 for ; Wed, 31 May 2017 21:24:16 +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 1dGB4Q-0004NH-Pw; Wed, 31 May 2017 21:22:22 +0000 Received: from mail6.bemta3.messagelabs.com ([195.245.230.39]) by lists.xenproject.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dGB4P-0004MJ-Ig for xen-devel@lists.xen.org; Wed, 31 May 2017 21:22:21 +0000 Received: from [85.158.137.68] by server-4.bemta-3.messagelabs.com id 06/33-31580-C043F295; Wed, 31 May 2017 21:22:20 +0000 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFlrMIsWRWlGSWpSXmKPExsVyMfTAIV0eE/1 Ig395Fks+LmZxYPQ4uvs3UwBjFGtmXlJ+RQJrxu2rk1kL2kQr/rQ+Ym5gfMrXxcjFISQwkVFi TfdGFhCHReAli8TjY1uZQBwJgX5WieObr7B2MXICOXESf55uYoawqyQ2d69hBLGFBNQktsw7x Qxh/2aUeNya3sXIwcEmoCvRfqsAJCwiIC1x7fNlRpCZzALtTBL3Z29jAkkICyRJrDnXwAZisw ioSiw6f4AJpJdXwFZi0nI+iFXyEos2zWABsTmBwqe6XzFBrLKRWPhkMvMERoEFjAyrGNWLU4v KUot0LfWSijLTM0pyEzNzdA0NjPVyU4uLE9NTcxKTivWS83M3MQKDqp6BgXEH4+ufTocYJTmY lER5K2z0IoX4kvJTKjMSizPii0pzUosPMcpwcChJ8O4w0o8UEixKTU+tSMvMAYY3TFqCg0dJh PcoSJq3uCAxtzgzHSJ1itGY48qVdV+YOKYc2P6FSYglLz8vVUqcdxJIqQBIaUZpHtwgWNxdYp SVEuZlZGBgEOIpSC3KzSxBlX/FKM7BqCTMOxVkCk9mXgncvldApzABnbJrhzbIKSWJCCmpBsa YD7c2zfA6Kn9uQugbuxfP4ua0vPj91Ey0VN5/rSVb8ku7b4teBd+9OaduueXEu+8b+Rwvd6je W3bGgF/t5WE9IYNozeUJDnWPGB7kiO++6ntrZV8em+rLPVe1r0y5lT+zb6rHbMW2hYsKI7LVr u74x594UW5pdtGU2niL5z3rWe8Wh4dI9B9UYinOSDTUYi4qTgQAYmVBLbYCAAA= X-Env-Sender: kpraveen.lkml@gmail.com X-Msg-Ref: server-15.tower-31.messagelabs.com!1496265738!99420005!1 X-Originating-IP: [209.85.192.194] X-SpamReason: No, hits=0.0 required=7.0 tests= X-StarScan-Received: X-StarScan-Version: 9.4.19; banners=-,-,- X-VirusChecked: Checked Received: (qmail 29772 invoked from network); 31 May 2017 21:22:19 -0000 Received: from mail-pf0-f194.google.com (HELO mail-pf0-f194.google.com) (209.85.192.194) by server-15.tower-31.messagelabs.com with AES128-GCM-SHA256 encrypted SMTP; 31 May 2017 21:22:19 -0000 Received: by mail-pf0-f194.google.com with SMTP id w69so4287730pfk.1 for ; Wed, 31 May 2017 14:22:19 -0700 (PDT) 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=hlW2l4xkcB7leSAXt/c0dXMNCim64rb3yG3X+PGxYUM=; b=iHkYGuk6fsmIZyoau0SGa50G36LM/v3rQlBDT9e7YnnaKnHhH5cn2vrVTRCyfV31HX qgxdbVVtBoKF1R7Bj3O/MlE1JonuYFbWUJkSGO1iLD9xDAZL2/JLAH9zCR2uaaA1S/BI 1qMca49MRoY5MXn+dBHH0Ovc8i78E5h0Wch5i+SyTiVfH6TyPPEInsM0R3BwibP/QpzU 72UMZ8lFXoCzS4UdqS0YnwLcFTLt6+tf+Q31H47PZOv0e4QIsEWLjgg+g3s70hYuTY52 dGrGl1iP7JPAgzZ43WYi8Henn0PH9OGgF7Rc5Il6I4i3NEJjn8byJVfKifdohQppKobj kf/g== 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=hlW2l4xkcB7leSAXt/c0dXMNCim64rb3yG3X+PGxYUM=; b=IsBdEfhQt+1FYEZCOuSBxWe0a1ae9l5tQSERVcy7NElvnL3No68KeFKMWm78kCA7FV RpLkdcrVEpjC9IMiE30ezHMbQvJFOVrfC0jLuK9l9GxAlXuQSdfmmBRgmIawYvBODiDg FrkNsHEosyoMV/2XSyOJlXHzAAER3MZRE67YhzNRfVXgvXWW/sgOWyj6StfTyXB2+Ufg wDgoSaYOMfQxaaJCYtoSScwEU8725ADotAepRh1ibvDeTmViULwYkLPiVHzOUrEm8f4W waN5u756r0qnlGVaZ6Vu2LHIMasfHHqkhAEWkjdlsIrsSaizTIhXRYV/RDCvNAKzr1jx sdkA== X-Gm-Message-State: AODbwcCO03sVAVu+bTrfVWiQ4C519KNjUUGX5ba5l3PtSzQX7OpKyNXa pOu0V3A2fSNASg== X-Received: by 10.84.140.164 with SMTP id 33mr91855939plt.142.1496265738233; Wed, 31 May 2017 14:22:18 -0700 (PDT) Received: from kpraveen.labs.blr.name ([103.227.99.58]) by smtp.gmail.com with ESMTPSA id t66sm29496699pfe.134.2017.05.31.14.22.13 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 31 May 2017 14:22:17 -0700 (PDT) From: Praveen Kumar To: xen-devel@lists.xen.org Date: Thu, 1 Jun 2017 02:50:48 +0530 Message-Id: <20170531212056.10583-10-kpraveen.lkml@gmail.com> X-Mailer: git-send-email 2.12.0 In-Reply-To: <20170531212056.10583-1-kpraveen.lkml@gmail.com> References: <20170531212056.10583-1-kpraveen.lkml@gmail.com> Cc: sstabellini@kernel.org, wei.liu2@citrix.com, George.Dunlap@eu.citrix.com, andrew.cooper3@citrix.com, dario.faggioli@citrix.com, ian.jackson@eu.citrix.com, tim@xen.org, Praveen Kumar , jbeulich@suse.com Subject: [Xen-devel] [Resend][PATCH 09/17] rbtree: adjust node color in __rb_erase_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 In __rb_erase_color(), we were always setting a node to black after exiting the main loop. And in one case, after fixing up the tree to satisfy all rbtree invariants, we were setting the current node to root just to guarantee a loop exit, at which point the root would be set to black. However this is not necessary, as the root of an rbtree is already known to be black. The only case where the color flip is required is when we exit the loop due to the current node being red, and it's easiest to just do the flip at that point instead of doing it after the loop. commit d6ff1273928ebf15466a85b7e1810cd00e72998b from linux tree Signed-off-by: Praveen Kumar --- xen/common/rbtree.c | 22 ++++++++++++++++------ 1 file changed, 16 insertions(+), 6 deletions(-) diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c index 8db7a5b4ca..736e2a55aa 100644 --- a/xen/common/rbtree.c +++ b/xen/common/rbtree.c @@ -262,10 +262,24 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, { struct rb_node *other; - while ((!node || rb_is_black(node)) && node != root->rb_node) + while (true) { - if (parent->rb_left == node) + /* + * Loop invariant: all leaf paths going through node have a + * black node count that is 1 lower than other leaf paths. + * + * If node is red, we can flip it to black to adjust. + * If node is the root, all leaf paths go through it. + * Otherwise, we need to adjust the tree through color flips + * and tree rotations as per one of the 4 cases below. + */ + if (node && rb_is_red(node)) { + rb_set_black(node); + break; + } else if (!parent) { + break; + } else if (parent->rb_left == node) { other = parent->rb_right; if (rb_is_red(other)) { @@ -297,7 +311,6 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, if (other->rb_right) rb_set_black(other->rb_right); __rb_rotate_left(parent, root); - node = root->rb_node; break; } } @@ -334,13 +347,10 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, if (other->rb_left) rb_set_black(other->rb_left); __rb_rotate_right(parent, root); - node = root->rb_node; break; } } } - if (node) - rb_set_black(node); } void rb_erase(struct rb_node *node, struct rb_root *root)