From patchwork Wed May 31 20:46:59 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Praveen Kumar X-Patchwork-Id: 9758075 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 D442C60390 for ; Wed, 31 May 2017 20:50:36 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id C660D284AF for ; Wed, 31 May 2017 20:50:36 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id BAB85284C4; Wed, 31 May 2017 20:50:36 +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 D119B284F2 for ; Wed, 31 May 2017 20:50:35 +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 1dGAXQ-00087x-96; Wed, 31 May 2017 20:48:16 +0000 Received: from mail6.bemta3.messagelabs.com ([195.245.230.39]) by lists.xenproject.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dGAXP-00087F-LR for xen-devel@lists.xen.org; Wed, 31 May 2017 20:48:15 +0000 Received: from [85.158.137.68] by server-4.bemta-3.messagelabs.com id 0F/E2-31580-E0C2F295; Wed, 31 May 2017 20:48:14 +0000 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFlrKIsWRWlGSWpSXmKPExsVyMfTAQV0+Hf1 Ig0NTGS2WfFzM4sDocXT3b6YAxijWzLyk/IoE1ozLk3wL2jwrDv5fytzAuFOvi5GTQ0hgIqPE o3saXYxcHCwCL1kkjj6+wwriSAj0s0pM2XiCDaRKQiBJ4sTqXewQdpnEmr47zBDdahJb5p1iB mkQEvjFKHH5/xugIg4ONgFdifZbBSA1IgLSEtc+X2YEqWEW+M4i8WTRDCaQhLCAt8TDhu1gQ1 kEVCUOL18CNpRXwEbi5+o/LBDL5CUWbZoBZnMK2Epc6VrMBrHYRmLh+glsExgFFjAyrGLUKE4 tKkst0jU00UsqykzPKMlNzMzRNTQw1stNLS5OTE/NSUwq1kvOz93ECAwsBiDYwbhiu+chRkkO JiVR3gobvUghvqT8lMqMxOKM+KLSnNTiQ4wyHBxKErw7tfQjhQSLUtNTK9Iyc4AhDpOW4OBRE uE9CpLmLS5IzC3OTIdInWI05rhyZd0XJo4pB7Z/YRJiycvPS5US59XVBioVACnNKM2DGwSLvU uMslLCvIxApwnxFKQW5WaWoMq/YhTnYFQS5r0KspAnM68Ebt8roFOYgE7ZtUMb5JSSRISUVAP jrD//d8cs+ho9fX6xtfgTI6YNuzW3s3x0szfnK+A3sGDP+M2fPW+uU+TTHte2xEaTDYLVqbpL RD5c/NjcNr3L+qXD5i/G4iyG3Dq/K1fMKvd61TBDsnrByl06vBnikz3uGKpcKDjHad6zTCnNM OaryYeZ0hbFZYsD7VjbjpclBa503Nq3j0WJpTgj0VCLuag4EQDq7u+RuAIAAA== X-Env-Sender: kpraveen.lkml@gmail.com X-Msg-Ref: server-11.tower-31.messagelabs.com!1496263692!72589261!1 X-Originating-IP: [209.85.192.193] 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 24243 invoked from network); 31 May 2017 20:48:13 -0000 Received: from mail-pf0-f193.google.com (HELO mail-pf0-f193.google.com) (209.85.192.193) by server-11.tower-31.messagelabs.com with AES128-GCM-SHA256 encrypted SMTP; 31 May 2017 20:48:13 -0000 Received: by mail-pf0-f193.google.com with SMTP id w69so4141116pfk.1 for ; Wed, 31 May 2017 13:48:13 -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=h5bC+A6Y8ppKuOr7XkKSMMrWkA6Zqy4MrP/7FgvAwxk=; b=aemCWYLJW1N1HIL60fsRjB7PKeNsM+HiIxLVkIx76O332gbJABdqp/vxRorxwzRcEE yDY8OkxkvfPQBypoTIG4idHjRZMW5T+EAJiSGirUl/pfwTXpF0WHv1SrJcli+owCBMlF 9+BaPC2N1fz/63qyfKRYXxiuvSoQORgFjQgFBVYnnaNm/H665AWPaNCeJDRACF8j4dlF mB1TU8qjEe8b2Kyp6U9jmTRlO6agogKlxyNdCHfaFv8x86aWt/TtZTJrro3uplK58ZG5 Qfo40gGn6OhqEh8/7PGsX1eWo/McftQUBI9sbMS88oA1V1F4O0yYakKJ0TeU617ZHVh8 yzuw== 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=h5bC+A6Y8ppKuOr7XkKSMMrWkA6Zqy4MrP/7FgvAwxk=; b=W82oC9oE+yRyCmLKBIMeyqDvg56VH1Q7BzXeznBdpCK4U8+geDuMmGZUtam5vASphw 4vKlx9OKfr/CQUklVUQvLzWb7UezHeL5FYGCCtj56ZXbVFQjR3t6wG6frthgkJtgbh+g xojJiv/kzcTPCMwm5/gqs+Z1TXEo/PVfuWayi+q35jGCbLSYvJDWsUJ7f8REw8m2DPlI pDuLyBYH1XUf3jMVjxZ9a5gXsfpTwSt/DPDoqD3uRSq6fSmXzxX1V9VeuwxUpeZXtVKP 1LZL8haw11179kI0WISEbzzjHlRGe6bzdvWsjshMSNjzcsmpaVqtSZkvq7xV5T5AtioS tDDg== X-Gm-Message-State: AODbwcB2ZZ9FAgUutgeeGquDg2H0dTBNRphQVn3FYDBIa8nQS+7pBC1k e2Y1agfESDLawdvN/2E= X-Received: by 10.98.32.92 with SMTP id g89mr37230pfg.153.1496263691866; Wed, 31 May 2017 13:48:11 -0700 (PDT) Received: from kpraveen.labs.blr.name ([103.227.99.58]) by smtp.gmail.com with ESMTPSA id d75sm31798444pfj.75.2017.05.31.13.48.06 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 31 May 2017 13:48:11 -0700 (PDT) From: Praveen Kumar To: xen-devel@lists.xen.org Date: Thu, 1 Jun 2017 02:16:59 +0530 Message-Id: <20170531204708.10470-9-kpraveen.lkml@gmail.com> X-Mailer: git-send-email 2.12.0 In-Reply-To: <20170531204708.10470-1-kpraveen.lkml@gmail.com> References: <20170531204708.10470-1-kpraveen.lkml@gmail.com> Cc: Andrea Arcangeli , Jens Axboe , Rik van Riel , sstabellini@kernel.org, wei.liu2@citrix.com, Peter Zijlstra , George.Dunlap@eu.citrix.com, andrew.cooper3@citrix.com, dario.faggioli@citrix.com, ian.jackson@eu.citrix.com, tim@xen.org, Daniel Santos , Praveen Kumar , "Eric W. Biederman" , jbeulich@suse.com, Andrew Morton , Michel Lespinasse , Linus Torvalds Subject: [Xen-devel] [PATCH 08/17] rbtree: low level optimizations in rb_insert_color() 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 - Use the newly introduced rb_set_parent_color() function to flip the color of nodes whose parent is already known. - Optimize rb_parent() when the node is known to be red - there is no need to mask out the color in that case. - Flipping gparent's color to red requires us to fetch its rb_parent_color field, so we can reuse it as the parent value for the next loop iteration. - Do not use __rb_rotate_left() and __rb_rotate_right() to handle tree rotations: we already have pointers to all relevant nodes, and know their colors (either because we want to adjust it, or because we've tested it, or we can deduce it as black due to the node proximity to a known red node). So we can generate more efficient code by making use of the node pointers we already have, and setting both the parent and color attributes for nodes all at once. Also in Case 2, some node attributes don't have to be set because we know another tree rotation (Case 3) will always follow and override them. commit 5bc9188aa207dafd47eab57df7c4fe5b3d3f636a from linux tree 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 --- xen/common/rbtree.c | 160 ++++++++++++++++++++++++++++++++++++++++++---------- 1 file changed, 129 insertions(+), 31 deletions(-) diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c index ccf905e35c..8db7a5b4ca 100644 --- a/xen/common/rbtree.c +++ b/xen/common/rbtree.c @@ -22,6 +22,25 @@ #include #include +/* + * red-black trees properties: http://en.wikipedia.org/wiki/Rbtree + * + * 1) A node is either red or black + * 2) The root is black + * 3) All leaves (NULL) are black + * 4) Both children of every red node are black + * 5) Every simple path from root to leaves contains the same number + * of black nodes. + * + * 4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two + * consecutive red nodes in a path and every red node is therefore followed by + * a black. So if B is the number of black nodes on every simple path (as per + * 5), then the longest possible path due to 4 is 2B. + * + * We shall indicate color with case, where black nodes are uppercase and red + * nodes will be lowercase. + */ + #define RB_RED 0 #define RB_BLACK 1 @@ -40,6 +59,17 @@ static inline void rb_set_color(struct rb_node *rb, int color) rb->__rb_parent_color = (rb->__rb_parent_color & ~1) | color; } +static inline void rb_set_parent_color(struct rb_node *rb, + struct rb_node *p, int color) +{ + rb->__rb_parent_color = (unsigned long)p | color; +} + +static inline struct rb_node *rb_red_parent(struct rb_node *red) +{ + return (struct rb_node *)red->__rb_parent_color; +} + static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) { struct rb_node *right = node->rb_right; @@ -86,9 +116,30 @@ static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) rb_set_parent(node, left); } +/* + * Helper function for rotations: + * - old's parent and color get assigned to new + * - old gets assigned new as a parent and 'color' as a color. + */ +static inline void +__rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, + struct rb_root *root, int color) +{ + struct rb_node *parent = rb_parent(old); + new->__rb_parent_color = old->__rb_parent_color; + rb_set_parent_color(old, new, color); + if (parent) { + if (parent->rb_left == old) + parent->rb_left = new; + else + parent->rb_right = new; + } else + root->rb_node = new; +} + void rb_insert_color(struct rb_node *node, struct rb_root *root) { - struct rb_node *parent, *gparent; + struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; while (true) { @@ -99,61 +150,108 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) * 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); + rb_set_parent_color(node, NULL, RB_BLACK); break; } else if (rb_is_black(parent)) break; - gparent = rb_parent(parent); + gparent = rb_red_parent(parent); if (parent == gparent->rb_left) { + tmp = gparent->rb_right; + if (tmp && rb_is_red(tmp)) { - register struct rb_node *uncle = gparent->rb_right; - if (uncle && rb_is_red(uncle)) - { - rb_set_black(uncle); - rb_set_black(parent); - rb_set_red(gparent); - node = gparent; - continue; - } + /* + * Case 1 - color flips + * + * G g + * / \ / \ + * p u --> P U + * / / + * n N + * + * However, since g's parent might be red, and + * 4) does not allow this, we need to recurse + * at g. + */ + rb_set_parent_color(tmp, gparent, RB_BLACK); + rb_set_parent_color(parent, gparent, RB_BLACK); + node = gparent; + parent = rb_parent(node); + rb_set_parent_color(node, parent, RB_RED); + continue; } if (parent->rb_right == node) { - __rb_rotate_left(parent, root); + /* + * Case 2 - left rotate at parent + * + * G G + * / \ / \ + * p U --> n U + * \ / + * n p + * + * This still leaves us in violation of 4), the + * continuation into Case 3 will fix that. + */ + parent->rb_right = tmp = node->rb_left; + node->rb_left = parent; + if (tmp) + rb_set_parent_color(tmp, parent, RB_BLACK); + rb_set_parent_color(parent, node, RB_RED); parent = node; } - - rb_set_black(parent); - rb_set_red(gparent); - __rb_rotate_right(gparent, root); + /* + * Case 3 - right rotate at gparent + * + * G P + * / \ / \ + * p U --> n g + * / \ + * n U + */ + gparent->rb_left = tmp = parent->rb_right; + parent->rb_right = gparent; + if (tmp) + rb_set_parent_color(tmp, gparent, RB_BLACK); + __rb_rotate_set_parents(gparent, parent, root, RB_RED); + break; } else { + tmp = gparent->rb_left; + if (tmp && rb_is_red(tmp)) { - register struct rb_node *uncle = gparent->rb_left; - if (uncle && rb_is_red(uncle)) - { - rb_set_black(uncle); - rb_set_black(parent); - rb_set_red(gparent); - node = gparent; - continue; - } + /* Case 1 - color flips */ + rb_set_parent_color(tmp, gparent, RB_BLACK); + rb_set_parent_color(parent, gparent, RB_BLACK); + node = gparent; + parent = rb_parent(node); + rb_set_parent_color(node, parent, RB_RED); + continue; } if (parent->rb_left == node) { - __rb_rotate_right(parent, root); + /* Case 2 - right rotate at parent */ + parent->rb_left = tmp = node->rb_right; + node->rb_right = parent; + if (tmp) + rb_set_parent_color(tmp, parent, RB_BLACK); + rb_set_parent_color(parent, node, RB_RED); parent = node; } - rb_set_black(parent); - rb_set_red(gparent); - __rb_rotate_left(gparent, root); + /* Case 3 - left rotate at gparent */ + gparent->rb_right = tmp = parent->rb_left; + parent->rb_left = gparent; + if (tmp) + rb_set_parent_color(tmp, gparent, RB_BLACK); + __rb_rotate_set_parents(gparent, parent, root, RB_RED); + break; } } }