From patchwork Sat Jun 17 09:32:46 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Praveen Kumar X-Patchwork-Id: 9794035 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 DC5F96038E for ; Sat, 17 Jun 2017 09:36:23 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id CD92B284BB for ; Sat, 17 Jun 2017 09:36:23 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id C24A9284C0; Sat, 17 Jun 2017 09:36:23 +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 12D712855E for ; Sat, 17 Jun 2017 09:36:23 +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 1dMA7K-0002Yv-08; Sat, 17 Jun 2017 09:34:06 +0000 Received: from mail6.bemta6.messagelabs.com ([193.109.254.103]) by lists.xenproject.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dMA7I-0002TD-9R for xen-devel@lists.xen.org; Sat, 17 Jun 2017 09:34:04 +0000 Received: from [193.109.254.147] by server-11.bemta-6.messagelabs.com id 5F/5D-03587-C87F4495; Sat, 17 Jun 2017 09:34:04 +0000 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFlrCIsWRWlGSWpSXmKPExsVyMfTAQd3u7y6 RBl9Pi1os+biYxYHR4+ju30wBjFGsmXlJ+RUJrBn9LauZC+aGVSzYuIatgfGMSRcjF4eQwERG ictzbzGCOCwCL1kkXj7bwQ7iSAj0s0pMbe0FcjiBnDiJ17e/skDYlRItS7ezgdhCAmoSW+adY oawfzNKzJgFZHNwsAnoSrTfKgAJiwhIS1z7fBlsAbPAd0aJNe+nsIIkhAX8JW52/mECsVkEVC U6fkwEm8krYCPRu/E81C55iUWbZrCAzOQEivcs8gQxhQSsJU7MYZ/AKLCAkWEVo0ZxalFZapG ukYFeUlFmekZJbmJmjq6hgZlebmpxcWJ6ak5iUrFecn7uJkZgWDEAwQ7GX8sCDjFKcjApifLm hLtECvEl5adUZiQWZ8QXleakFh9ilOHgUJLgNfsGlBMsSk1PrUjLzAEGOExagoNHSYT3/GOgN G9xQWJucWY6ROoUozHHlSvrvjBxTDmw/QuTEEtefl6qlDhvKMgkAZDSjNI8uEGwyLvEKCslzM sIdJoQT0FqUW5mCar8K0ZxDkYlYV6Pr0BTeDLzSuD2vQI6hQnoFOYzYKeUJCKkpBoY92l6cfQ 7xtxaccl6mdpjvUO6mgrv1bMtW/combTVH5AR+m/T5Ltu5d5EjR2asnHWTn/dL6TFMkV9+TPf ZGnZkafsaxieL2ovmml82+elV+lOyyvC99q95zO/NXTMvbVUpPTgWsvr5bvPhRkuD0+/P/fFT bnPfVUXd0r7b2yeW/9tnUnR81fblViKMxINtZiLihMBsnrsi7cCAAA= X-Env-Sender: kpraveen.lkml@gmail.com X-Msg-Ref: server-16.tower-27.messagelabs.com!1497692041!107801052!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 43985 invoked from network); 17 Jun 2017 09:34:03 -0000 Received: from mail-pf0-f193.google.com (HELO mail-pf0-f193.google.com) (209.85.192.193) by server-16.tower-27.messagelabs.com with AES128-GCM-SHA256 encrypted SMTP; 17 Jun 2017 09:34:03 -0000 Received: by mail-pf0-f193.google.com with SMTP id w12so9928399pfk.0 for ; Sat, 17 Jun 2017 02:34:02 -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=XhX0mcXVaGBse+FIYp0QWVYltnfkPhzbcGuHxgX8Yj0=; b=cM6B0uJQoKLdP5JKMcUJJjcPaEMYs9kxDYhM2Pv9BT2muURW1vQhKzZG67UAaAsD1f qg7XCHp3oQCHCyx5ho+iHC30txsIsQ4o92VApoOaSiqycWgxtsUaD7C8HfoIBkSNI0BC rBQ7YQ5rtPzk49qHBN5fvXShsSGrsZVgXJMAs3H5TLaE59tPyTbcG5m4gltqVkgZ4M4j +Nq17wCO+f/w6PSFmw/8q90gGHBRIC1lJJ/yBUDkuMY9Z0zeYDnPydghwqpjVOnPScnA RZO6QLMsJ+j7xseoI8Mhv2DdpMfBDxwp8YXTt2/PbGIW51oG7ZPRCAUFOqnx66c0q0Yc 9xuQ== 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=XhX0mcXVaGBse+FIYp0QWVYltnfkPhzbcGuHxgX8Yj0=; b=kUulY1BW8Id2opq6SxG13JjyK8yCI2jaybk9m8M/j2NiEzLRbxIXiNfu64mzqMoO5D GnQnJtQ8bQS57UgfRX9nXv5Whk+qdEbajzUOyE6E7xp/YrE8nojZkkEfdCxhr/TUEdCr DV7nRm0b9yHGeNF7wvlqhddlEdysjWKhzD+GIUpV/lplqZgVXunBY6B2ijNx4MI5mWH4 fElbineCi2XoF3/ibp98j75cRQBXKv/lZdT8BwlejhJwSlZHkOdOvsITnQLsJYLGXbkB iBBhP/Lj7klCaYJWUZ3EmEwxM5a54PNEh5cRMA1K9WphZWJwYlbIg6sUx+wZt0eo2XM+ zaJQ== X-Gm-Message-State: AKS2vOzQMmK8Ug1VIFw0LBMIUvKcBjl9V4KNZdTrK+pBPWSH+1kRkc6J Iah3Iyl0mnkAgO9A X-Received: by 10.99.121.66 with SMTP id u63mr15736882pgc.20.1497692041181; Sat, 17 Jun 2017 02:34:01 -0700 (PDT) Received: from kpraveen.labs.blr.name ([103.227.99.177]) by smtp.gmail.com with ESMTPSA id k129sm9653921pfc.87.2017.06.17.02.33.57 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Sat, 17 Jun 2017 02:34:00 -0700 (PDT) From: Praveen Kumar To: xen-devel@lists.xen.org Date: Sat, 17 Jun 2017 15:02:46 +0530 Message-Id: <20170617093253.3990-14-kpraveen.lkml@gmail.com> X-Mailer: git-send-email 2.12.0 In-Reply-To: <20170617093253.3990-1-kpraveen.lkml@gmail.com> References: <20170617093253.3990-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, kpraveen.lkml@gmail.com, jbeulich@suse.com Subject: [Xen-devel] [PATCH v2 13/20] rbtree: low level optimizations in __rb_erase_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 In __rb_erase_color(), we often already have pointers to the nodes being rotated and/or know what their colors must be, so we can generate more efficient code than the generic __rb_rotate_left() and __rb_rotate_right() functions. Also when the current node is red or when flipping the sibling's color, the parent is already known so we can use the more efficient rb_set_parent_color() function to set the desired 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 6280d2356fd8ad0936a63c10dc1e6accf48d0c61] Ported to Xen. Signed-off-by: Praveen Kumar --- xen/common/rbtree.c | 196 ++++++++++++++++++++++++++++------------------------ 1 file changed, 107 insertions(+), 89 deletions(-) diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c index a365670369..1fe059a568 100644 --- a/xen/common/rbtree.c +++ b/xen/common/rbtree.c @@ -38,7 +38,8 @@ * 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. + * nodes will be lowercase. Unknown color nodes shall be drawn as red within + * parentheses and have some accompanying text comment. */ #define RB_RED 0 @@ -47,17 +48,11 @@ #define rb_color(r) ((r)->__rb_parent_color & 1) #define rb_is_red(r) (!rb_color(r)) #define rb_is_black(r) rb_color(r) -#define rb_set_red(r) do { (r)->__rb_parent_color &= ~1; } while (0) -#define rb_set_black(r) do { (r)->__rb_parent_color |= 1; } while (0) static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) { rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; } -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) @@ -70,52 +65,6 @@ 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; - struct rb_node *parent = rb_parent(node); - - if ((node->rb_right = right->rb_left)) - rb_set_parent(right->rb_left, node); - right->rb_left = node; - - rb_set_parent(right, parent); - - if (parent) - { - if (node == parent->rb_left) - parent->rb_left = right; - else - parent->rb_right = right; - } - else - root->rb_node = right; - rb_set_parent(node, right); -} - -static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) -{ - struct rb_node *left = node->rb_left; - struct rb_node *parent = rb_parent(node); - - if ((node->rb_left = left->rb_right)) - rb_set_parent(left->rb_right, node); - left->rb_right = node; - - rb_set_parent(left, parent); - - if (parent) - { - if (node == parent->rb_right) - parent->rb_right = left; - else - parent->rb_left = left; - } - else - root->rb_node = left; - rb_set_parent(node, left); -} - /* * Helper function for rotations: * - old's parent and color get assigned to new @@ -259,7 +208,7 @@ EXPORT_SYMBOL(rb_insert_color); static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, struct rb_root *root) { - struct rb_node *other; + struct rb_node *sibling, *tmp1, *tmp2; while (true) { @@ -274,67 +223,136 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, */ if (node && rb_is_red(node)) { - rb_set_black(node); + rb_set_parent_color(node, parent, RB_BLACK); break; } else if (!parent) { break; } else if (parent->rb_left == node) { - other = parent->rb_right; - if (rb_is_red(other)) + sibling = parent->rb_right; + if (rb_is_red(sibling)) { - rb_set_black(other); - rb_set_red(parent); - __rb_rotate_left(parent, root); - other = parent->rb_right; + /* + * Case 1 - left rotate at parent + * + * P S + * / \ / \ + * N s --> p Sr + * / \ / \ + * Sl Sr N Sl + */ + parent->rb_right = tmp1 = sibling->rb_left; + sibling->rb_left = parent; + rb_set_parent_color(tmp1, parent, RB_BLACK); + __rb_rotate_set_parents(parent, sibling, root, RB_RED); + sibling = tmp1; } - if (!other->rb_right || rb_is_black(other->rb_right)) + tmp1 = sibling->rb_right; + if (!tmp1 || rb_is_black(tmp1)) { - if (!other->rb_left || rb_is_black(other->rb_left)) + tmp2 = sibling->rb_left; + if (!tmp2 || rb_is_black(tmp2)) { - rb_set_red(other); + /* + * Case 2 - sibling color flip + * (p could be either color here) + * + * (p) (p) + * / \ / \ + * N S --> N s + * / \ / \ + * Sl Sr Sl Sr + * + * This leaves us violating 5), so + * recurse at p. If p is red, the + * recursion will just flip it to black + * and exit. If coming from Case 1, + * p is known to be red. + */ + rb_set_parent_color(sibling, parent, RB_RED); node = parent; parent = rb_parent(node); continue; } - rb_set_black(other->rb_left); - rb_set_red(other); - __rb_rotate_right(other, root); - other = parent->rb_right; + /* + * Case 3 - right rotate at sibling + * (p could be either color here) + * + * (p) (p) + * / \ / \ + * N S --> N Sl + * / \ \ + * sl Sr s + * \ + * Sr + */ + sibling->rb_left = tmp1 = tmp2->rb_right; + tmp2->rb_right = sibling; + parent->rb_right = tmp2; + if (tmp1) + rb_set_parent_color(tmp1, sibling, RB_BLACK); + tmp1 = sibling; + sibling = tmp2; } - rb_set_color(other, rb_color(parent)); - rb_set_black(parent); - rb_set_black(other->rb_right); - __rb_rotate_left(parent, root); + /* + * Case 4 - left rotate at parent + color flips + * (p and sl could be either color here. + * After rotation, p becomes black, s acquires + * p's color, and sl keeps its color) + * + * (p) (s) + * / \ / \ + * N S --> P Sr + * / \ / \ + * (sl) sr N (sl) + */ + parent->rb_right = tmp2 = sibling->rb_left; + sibling->rb_left = parent; + rb_set_parent_color(tmp1, sibling, RB_BLACK); + if (tmp2) + rb_set_parent(tmp2, parent); + __rb_rotate_set_parents(parent, sibling, root, RB_BLACK); break; } else { - other = parent->rb_left; - if (rb_is_red(other)) + sibling = parent->rb_left; + if (rb_is_red(sibling)) { - rb_set_black(other); - rb_set_red(parent); - __rb_rotate_right(parent, root); - other = parent->rb_left; + /* Case 1 - right rotate at parent */ + parent->rb_left = tmp1 = sibling->rb_right; + sibling->rb_right = parent; + rb_set_parent_color(tmp1, parent, RB_BLACK); + __rb_rotate_set_parents(parent, sibling, root, RB_RED); + sibling = tmp1; } - if (!other->rb_left || rb_is_black(other->rb_left)) + tmp1 = sibling->rb_left; + if (!tmp1 || rb_is_black(tmp1)) { - if (!other->rb_right || rb_is_black(other->rb_right)) + tmp2 = sibling->rb_right; + if (!tmp2 || rb_is_black(tmp2)) { - rb_set_red(other); + /* Case 2 - sibling color flip */ + rb_set_parent_color(sibling, parent, RB_RED); node = parent; parent = rb_parent(node); continue; } - rb_set_black(other->rb_right); - rb_set_red(other); - __rb_rotate_left(other, root); - other = parent->rb_left; + /* Case 3 - right rotate at sibling */ + sibling->rb_right = tmp1 = tmp2->rb_left; + tmp2->rb_left = sibling; + parent->rb_left = tmp2; + if (tmp1) + rb_set_parent_color(tmp1, sibling, RB_BLACK); + tmp1 = sibling; + sibling = tmp2; } - rb_set_color(other, rb_color(parent)); - rb_set_black(parent); - rb_set_black(other->rb_left); - __rb_rotate_right(parent, root); + /* Case 4 - left rotate at parent + color flips */ + parent->rb_left = tmp2 = sibling->rb_right; + sibling->rb_right = parent; + rb_set_parent_color(tmp1, sibling, RB_BLACK); + if (tmp2) + rb_set_parent(tmp2, parent); + __rb_rotate_set_parents(parent, sibling, root, RB_BLACK); break; } }