From patchwork Tue Nov 21 15:20:08 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Praveen Kumar X-Patchwork-Id: 10068471 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 84B2A60586 for ; Tue, 21 Nov 2017 15:23:22 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 73D1F2977D for ; Tue, 21 Nov 2017 15:23:22 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 637172977C; Tue, 21 Nov 2017 15:23:22 +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 B7D9029777 for ; Tue, 21 Nov 2017 15:23:21 +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 1eHAMb-0000j3-4H; Tue, 21 Nov 2017 15:21:29 +0000 Received: from mail6.bemta6.messagelabs.com ([193.109.254.103]) by lists.xenproject.org with esmtp (Exim 4.84_2) (envelope-from ) id 1eHAMa-0000i8-CZ for xen-devel@lists.xen.org; Tue, 21 Nov 2017 15:21:28 +0000 Received: from [85.158.143.35] by server-3.bemta-6.messagelabs.com id 50/68-00303-774441A5; Tue, 21 Nov 2017 15:21:27 +0000 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFtrPIsWRWlGSWpSXmKPExsVyMfTAEd0yF5E og/2/zS2WfFzM4sDocXT3b6YAxijWzLyk/IoE1oyXLe9YCn5rVfye/omtgfGjYhcjF4eQwERG if6Nh1lAHBaBlywSny+3s4M4EgL9rBJtD18zdTFyAjlZEq++T2GDsNMkrrz+zgxhV0nsvPYez BYSUJPYMu8UM8TYd4wSW989Z+1i5OBgE9CVaL9VAFIjIiAtce3zZUaQGmaB74wSa95PYQVJCA v4SfSc2wg2iEVAVeLEplNgcV4BW4kTc1dALZOXmPauFyzOCRS/dPATG8RiG4l/c5+wTWAUXMD IsIpRozi1qCy1SNfITC+pKDM9oyQ3MTNH19DATC83tbg4MT01JzGpWC85P3cTIzDoGIBgB+OZ BYGHGCU5mJREeSVNRaKE+JLyUyozEosz4otKc1KLDzHKcHAoSfDyOgPlBItS01Mr0jJzgOEPk 5bg4FES4W11AkrzFhck5hZnpkOkTjHac1y4c+kPE8eBPbeA5LOZrxuYOaZdbW1iFmLJy89LlR LndQWZKgDSllGaBzcUFq+XGGWlhHkZgc4U4ilILcrNLEGVf8UozsGoJMwrCDKFJzOvBG73K6C zmIDO+nlcGOSskkSElFQD4wVbvTyB/7YFOdqqBztmlJ/KWsikz7ikIuXAHv2XDxQ6w3/+35nw cuPPMP8vukcvzGZTnftn5r77Qay8vytfN3JFKXwqWxHpk/Iv2iRhu4aArWjlR4fpHTlunBs25 9v1r0o4u+O9fobHporZMZcuzcnaf0MjhC3z+dZrubmSHiEV81kE+m8/UmIpzkg01GIuKk4EAH 1xM+/SAgAA X-Env-Sender: kpraveen.lkml@gmail.com X-Msg-Ref: server-5.tower-21.messagelabs.com!1511277685!72729895!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 18739 invoked from network); 21 Nov 2017 15:21:26 -0000 Received: from mail-pf0-f196.google.com (HELO mail-pf0-f196.google.com) (209.85.192.196) by server-5.tower-21.messagelabs.com with AES128-GCM-SHA256 encrypted SMTP; 21 Nov 2017 15:21:26 -0000 Received: by mail-pf0-f196.google.com with SMTP id r88so6108108pfi.2 for ; Tue, 21 Nov 2017 07:21:26 -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=NaYqucSneBWxtQBe3AdED2NMY3wCTE+L5da1MAsGefo=; b=GDGI/DoDc/eTfuZntfev7Wr75sV1bdxEpeCrZcvJDhX4Lhfm1Hk4FC+JjhSsfSqlWC Hl8CRWWADrl9jZe74F+IO2HY4qd3H7ba3iTWHzDiilctxHBq4pZC71lWft/quc6b2AaQ mxMx3HtImL5aqb+Re1ENZpTDMDOL3kmrJzuOOevBrM1DJ7IXAeeS8IUKpgO8+BKo71D1 hxyXkSlRIjEl1JkUY0E1JT0BolyJ+Q1FQLGzsBdRS42pbN2nYDWyQ30I2jK8+/Qo+otW AN3GjuHZ6zLLXm+xGWo3GK+v/AsJ84PVBfakjh1tEjI646xzjtNs0eihkifkOyOx6AFT 2Kkw== 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=NaYqucSneBWxtQBe3AdED2NMY3wCTE+L5da1MAsGefo=; b=GwmleCH7aCAfaRekwx/WWps2CDCBlnPQ7lf6T5E+rwE1XFH1Kh0kg3ICj8oT5z4FtC JJIx0tjWH8J2hIzfpwrdd9XdZ+5cQ/TxQ+Useff/xTccRqkxTdQX9GnrK/0APUkqdCfF YpqQ5QQFbpdIC7bSnbHv6C9Z6jE124g5iyfQ3gHJ0SaiZvh+DmJY/4X1VCOggbjsfK9c iC2lOj9H1sS9WK53GksZScDABfme8rVlI4W1Vf0FZJJDwL6AgpVGMMiDop1mZZPOZG5U dLXKPBtHkSGiYuGO+WPqQu15XY3OHGwLc4w2RhFM0SSANquzXOJCPOjCJzsJtpTf15DU haAA== X-Gm-Message-State: AJaThX5zLAkRgQszOtc4L//lXLkQKH+Yw7PcU8MULtfdXWoLtOygfEB6 Pwff973jPc500JCJTgylLX+LaQ== X-Google-Smtp-Source: AGs4zMY65TUBcXh6CgmYDf8b1QQJZmF0LpWCjqraywYYUjNuM0oVNrrVHMizNqPCDtcSEIvjIJUK5A== X-Received: by 10.101.80.132 with SMTP id r4mr17169755pgp.428.1511277685107; Tue, 21 Nov 2017 07:21:25 -0800 (PST) Received: from praveen.name ([106.51.29.204]) by smtp.gmail.com with ESMTPSA id 3sm26905504pfo.17.2017.11.21.07.21.21 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Tue, 21 Nov 2017 07:21:24 -0800 (PST) From: Praveen Kumar To: xen-devel@lists.xen.org Date: Tue, 21 Nov 2017 20:50:08 +0530 Message-Id: <20171121152009.15591-16-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 15/16 RESEND] rbtree: low level optimizations in rb_erase() 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 Various minor optimizations in rb_erase(): - Avoid multiple loading of node->__rb_parent_color when computing parent and color information (possibly not in close sequence, as there might be further branches in the algorithm) - In the 1-child subcase of case 1, copy the __rb_parent_color field from the erased node to the child instead of recomputing it from the desired parent and color - When searching for the erased node's successor, differentiate between cases 2 and 3 based on whether any left links were followed. This avoids a condition later down. - In case 3, keep a pointer to the erased node's right child so we don't have to refetch it later to adjust its parent. - In the no-childs subcase of cases 2 and 3, place the rebalance assigment last so that the compiler can remove the following if(rebalance) test. Also, added some comments to illustrate cases 2 and 3. Signed-off-by: Michel Lespinasse Acked-by: Rik van Riel Cc: Peter Zijlstra Cc: Andrea Arcangeli Cc: David Woodhouse Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds [Linux commit 4f035ad67f4633c233cb3642711d49b4efc9c82d] Ported to Xen. Signed-off-by: Praveen Kumar --- xen/common/rbtree.c | 98 ++++++++++++++++++++++++++++++++++------------------- 1 file changed, 64 insertions(+), 34 deletions(-) diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c index e7df273800..5c4e239c24 100644 --- a/xen/common/rbtree.c +++ b/xen/common/rbtree.c @@ -47,9 +47,14 @@ #define RB_RED 0 #define RB_BLACK 1 -#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_parent(pc) ((struct rb_node *)(pc & ~3)) + +#define __rb_color(pc) ((pc) & 1) +#define __rb_is_black(pc) __rb_color(pc) +#define __rb_is_red(pc) (!__rb_color(pc)) +#define rb_color(rb) __rb_color((rb)->__rb_parent_color) +#define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color) +#define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color) static inline void rb_set_black(struct rb_node *rb) { @@ -378,6 +383,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root) { struct rb_node *child = node->rb_right, *tmp = node->rb_left; struct rb_node *parent, *rebalance; + unsigned long pc; if (!tmp) { /* @@ -387,51 +393,75 @@ void rb_erase(struct rb_node *node, struct rb_root *root) * and node must be black due to 4). We adjust colors locally * so as to bypass __rb_erase_color() later on. */ - - parent = rb_parent(node); + pc = node->__rb_parent_color; + parent = __rb_parent(pc); __rb_change_child(node, child, parent, root); if (child) { - rb_set_parent_color(child, parent, RB_BLACK); + child->__rb_parent_color = pc; rebalance = NULL; - } else { - rebalance = rb_is_black(node) ? parent : NULL; - } + } else + rebalance = __rb_is_black(pc) ? parent : NULL; } else if (!child) { /* Still case 1, but this time the child is node->rb_left */ - parent = rb_parent(node); + tmp->__rb_parent_color = pc = node->__rb_parent_color; + parent = __rb_parent(pc); __rb_change_child(node, tmp, parent, root); - rb_set_parent_color(tmp, parent, RB_BLACK); rebalance = NULL; } else { - struct rb_node *old = node, *left; - - node = child; - while ((left = node->rb_left) != NULL) - node = left; - - __rb_change_child(old, node, rb_parent(old), root); - - child = node->rb_right; - parent = rb_parent(node); - - if (parent == old) { - parent = node; + struct rb_node *successor = child, *child2; + tmp = child->rb_left; + if (!tmp) { + /* + * Case 2: node's successor is its right child + * + * (n) (s) + * / \ / \ + * (x) (s) -> (x) (c) + * \ + * (c) + */ + parent = child; + child2 = child->rb_right; } else { - parent->rb_left = child; - - node->rb_right = old->rb_right; - rb_set_parent(old->rb_right, node); + /* + * Case 3: node's successor is leftmost under + * node's right child subtree + * + * (n) (s) + * / \ / \ + * (x) (y) -> (x) (y) + * / / + * (p) (p) + * / / + * (s) (c) + * \ + * (c) + */ + do { + parent = successor; + successor = tmp; + tmp = tmp->rb_left; + } while (tmp); + parent->rb_left = child2 = successor->rb_right; + successor->rb_right = child; + rb_set_parent(child, successor); } - if (child) { - rb_set_parent_color(child, parent, RB_BLACK); + successor->rb_left = tmp = node->rb_left; + rb_set_parent(tmp, successor); + + pc = node->__rb_parent_color; + tmp = __rb_parent(pc); + __rb_change_child(node, successor, tmp, root); + if (child2) { + successor->__rb_parent_color = pc; + rb_set_parent_color(child2, parent, RB_BLACK); rebalance = NULL; } else { - rebalance = rb_is_black(node) ? parent : NULL; + unsigned long pc2 = successor->__rb_parent_color; + successor->__rb_parent_color = pc; + rebalance = __rb_is_black(pc2) ? parent : NULL; } - node->__rb_parent_color = old->__rb_parent_color; - node->rb_left = old->rb_left; - rb_set_parent(old->rb_left, node); } if (rebalance)