From patchwork Mon Jul 3 19:58:19 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Praveen Kumar X-Patchwork-Id: 9823927 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 2204E60353 for ; Mon, 3 Jul 2017 20:02:33 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 133B326D08 for ; Mon, 3 Jul 2017 20:02:33 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 0773C27F3E; Mon, 3 Jul 2017 20:02:33 +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 3564426D08 for ; Mon, 3 Jul 2017 20:02:32 +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 1dS7Vs-000209-I3; Mon, 03 Jul 2017 20:00:04 +0000 Received: from mail6.bemta3.messagelabs.com ([195.245.230.39]) by lists.xenproject.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dS7Vq-0001mB-VH for xen-devel@lists.xen.org; Mon, 03 Jul 2017 20:00:03 +0000 Received: from [85.158.137.68] by server-9.bemta-3.messagelabs.com id 04/1A-01995-242AA595; Mon, 03 Jul 2017 20:00:02 +0000 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFlrDIsWRWlGSWpSXmKPExsVyMbThkK7joqh Ig6cnxC2WfFzM4sDocXT3b6YAxijWzLyk/IoE1oy9h9azFDw2qWjcfJC5gbFJs4uRi0NIYBKj xL+tJ5hBHBaBlywSO4+sYwJxJAT6WSUmPwNxOIGcOIkL574xQ9iVEj1LNzOC2EICahJb5p1ih rD/M0o87ZLuYuTgYBPQlWi/VQASFhGQlrj2+TIjyExmge+MEmveT2EFSQgLpEpMW/WfHcRmEV CVWLHxIRuIzStgK7H3/zQWiF3yEos2zQCzOYHiMx/MYILYZSPx80o/4wRGgQWMDKsYNYpTi8p Si3SNDfSSijLTM0pyEzNzdA0NjPVyU4uLE9NTcxKTivWS83M3MQJDq56BgXEHY+cJv0OMkhxM SqK8rjcjI4X4kvJTKjMSizPii0pzUosPMcpwcChJ8LIujIoUEixKTU+tSMvMAQY5TFqCg0dJh HdyI1Cat7ggMbc4Mx0idYrRkuPKlXVfmDimHNgOJF9N+P+NSYglLz8vVUqcVwtkngBIQ0ZpHt w4WCReYpSVEuZlZGBgEOIpSC3KzSxBlX/FKM7BqCTMW78AaApPZl4J3NZXQAcxAR3U0BMBclB JIkJKqoFx0uKyjw9yhHMsU5u/d07knnhowR+NdS3MV51Fc/4umV+a+sI8JCyU01FEpCNy+xTO vYoCKww/OZ3w6TpxZA9n8nOZqzViju2O9ge1hXpkNn3hPr3HxHKW6bIXxq1NXO5veVvWvknQO ji5ekpK0dw1E5tm2Ofbdwb0iCuEVuxuU4x5fHvB6kwlluKMREMt5qLiRABS2mAPvwIAAA== X-Env-Sender: kpraveen.lkml@gmail.com X-Msg-Ref: server-4.tower-31.messagelabs.com!1499112001!45674379!1 X-Originating-IP: [209.85.128.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 23601 invoked from network); 3 Jul 2017 20:00:01 -0000 Received: from mail-wr0-f194.google.com (HELO mail-wr0-f194.google.com) (209.85.128.194) by server-4.tower-31.messagelabs.com with AES128-GCM-SHA256 encrypted SMTP; 3 Jul 2017 20:00:01 -0000 Received: by mail-wr0-f194.google.com with SMTP id k67so45450787wrc.1 for ; Mon, 03 Jul 2017 13:00:01 -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=K6WrzBy2fKk31IdKv6UhDOgXViu/Cnc0loXw2XPPVAg=; b=H6oFYL+EJNhSjQcQtdHLOr/EEbuHZ3eawR33gtzP6kxSx0uwUwQIGQ7xfNEapvOyFJ kEAADYnTTvMWhYQVCMzKHhrbOoauIZ2TzIMfGYchYYcRYkBS+6Fs1CrXL9SHDzMi0O7H KAeC3q/CvWBLWCCJmH3ZFCIcP8LVT7MeO7dtK1GaxgC79MeLZ8LIyqfN7KNXdqrj+Pjg eJHM29fl6VmPVlVRyrQVXyi+05veYbCVaJrvucAQCZJ2DUo8V4HVMMgE1qwe7wnCPWdc ij9BE+UBOwkqfleteGul09grNv9p2HKkSiysGACYmnDfE9sYXdy10KZPWvaBuhRgBgpX haYg== 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=K6WrzBy2fKk31IdKv6UhDOgXViu/Cnc0loXw2XPPVAg=; b=gSSKN3bDfLDGzIqKge4ks037BKxRxYUl2h5vrGKQwnQtXKX+d+VuzAMiJ5BNKpcERG vxutdckSPikfofoL7EF/LNpqLW/IaQq2I4rsuMuolNd6wxqQvk7fQrVVtcmE1UkDGBoX JvIY9khkYlzaonRQ3ANd+Wb1Fd1wa1gFclCfnwI2btTBJ9CXiF8HrhhAIZgnqNwnVC+L csfB3ewIj+AxJJxOW0FFajYpU6sXOwpvKUjsXbrF+xS8Q8FCGXzDYWNBazxk/RkU2U5h LrQKKMeqh7AEdBkIEZFfjiwLsfvE3XEW3QobM8QhlgH7lgjqoaKnnSrPEqFVaI8AmGXy LDhw== X-Gm-Message-State: AKS2vOwDWzaE7J2xMLEBzUiyWf2cU/k1Sb0QbQjwNiaVbsJLNGHkI2bs IvuGTyf6EvRkQuMD X-Received: by 10.223.133.67 with SMTP id 61mr39078413wrh.30.1499112000736; Mon, 03 Jul 2017 13:00:00 -0700 (PDT) Received: from kpraveen.labs.blr.novell.com ([106.51.128.11]) by smtp.gmail.com with ESMTPSA id 21sm25658979wmo.16.2017.07.03.12.59.55 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Mon, 03 Jul 2017 13:00:00 -0700 (PDT) From: Praveen Kumar To: xen-devel@lists.xen.org Date: Tue, 4 Jul 2017 01:28:19 +0530 Message-Id: <20170703195821.29845-16-kpraveen.lkml@gmail.com> X-Mailer: git-send-email 2.12.0 In-Reply-To: <20170703195821.29845-1-kpraveen.lkml@gmail.com> References: <20170703195821.29845-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 v4 15/17] rbtree: handle 1-child recoloring in rb_erase() instead of 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 From: Michel Lespinasse An interesting observation for rb_erase() is that when a node has exactly one child, the node must be black and the child must be red. An interesting consequence is that removing such a node can be done by simply replacing it with its child and making the child black, which we can do efficiently in rb_erase(). __rb_erase_color() then only needs to handle the no-childs case and can be modified accordingly. 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 46b6135a7402ac23c5b25f2bd79b03bab8f98278] Ported to Xen. Signed-off-by: Praveen Kumar --- xen/common/rbtree.c | 102 +++++++++++++++++++++++++++++++--------------------- 1 file changed, 61 insertions(+), 41 deletions(-) diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c index 891f04e919..e506e0451d 100644 --- a/xen/common/rbtree.c +++ b/xen/common/rbtree.c @@ -2,6 +2,7 @@ Red Black Trees (C) 1999 Andrea Arcangeli (C) 2002 David Woodhouse + (C) 2012 Michel Lespinasse This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -49,6 +50,11 @@ #define rb_is_red(r) (!rb_color(r)) #define rb_is_black(r) rb_color(r) +static inline void rb_set_black(struct rb_node *rb) +{ + rb->__rb_parent_color |= RB_BLACK; +} + static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) { rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; @@ -213,27 +219,18 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) } EXPORT_SYMBOL(rb_insert_color); -static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, - struct rb_root *root) +static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) { - struct rb_node *sibling, *tmp1, *tmp2; + struct rb_node *node = NULL, *sibling, *tmp1, *tmp2; while (true) { /* - * 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. + * Loop invariants: + * - node is black (or NULL on first iteration) + * - node is not the root (parent is not NULL) + * - All leaf paths going through parent and node have a + * black node count that is 1 lower than other leaf paths. */ - if (node && rb_is_red(node)) { - rb_set_parent_color(node, parent, RB_BLACK); - break; - } else if (!parent) { - break; - } sibling = parent->rb_right; if (node != sibling) { /* node == parent->rb_left */ if (rb_is_red(sibling)) { @@ -267,17 +264,22 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, * / \ / \ * 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. + * This leaves us violating 5) which + * can be fixed by flipping p to black + * if it was red, or by recursing at p. + * p is red when coming from Case 1. */ rb_set_parent_color(sibling, parent, RB_RED); - node = parent; - parent = rb_parent(node); - continue; + if (rb_is_red(parent)) + rb_set_black(parent); + else { + node = parent; + parent = rb_parent(node); + if (parent) + continue; + } + break; } /* * Case 3 - right rotate at sibling @@ -338,9 +340,15 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, /* Case 2 - sibling color flip */ rb_set_parent_color(sibling, parent, RB_RED); - node = parent; - parent = rb_parent(node); - continue; + if (rb_is_red(parent)) + rb_set_black(parent); + else { + node = parent; + parent = rb_parent(node); + if (parent) + continue; + } + break; } /* Case 3 - right rotate at sibling */ sibling->rb_right = tmp1 = tmp2->rb_left; @@ -368,23 +376,32 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, 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; - int color; + struct rb_node *parent, *rebalance; if (!tmp) { - case1: - /* Case 1: node to erase has no more than 1 child (easy!) */ + /* + * Case 1: node to erase has no more than 1 child (easy!) + * + * Note that if there is one child it must be red due to 5) + * 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); - color = rb_color(node); - if (child) - rb_set_parent(child, parent); __rb_change_child(node, child, parent, root); + if (child) { + rb_set_parent_color(child, parent, RB_BLACK); + rebalance = NULL; + } else { + rebalance = rb_is_black(node) ? parent : NULL; + } } else if (!child) { /* Still case 1, but this time the child is node->rb_left */ - child = tmp; - goto case1; + parent = rb_parent(node); + __rb_change_child(node, tmp, parent, root); + rb_set_parent_color(tmp, parent, RB_BLACK); + rebalance = NULL; } else { struct rb_node *old = node, *left; @@ -396,27 +413,30 @@ void rb_erase(struct rb_node *node, struct rb_root *root) child = node->rb_right; parent = rb_parent(node); - color = rb_color(node); if (parent == old) { parent = node; } else { - if (child) - rb_set_parent(child, parent); parent->rb_left = child; node->rb_right = old->rb_right; rb_set_parent(old->rb_right, node); } + if (child) { + rb_set_parent_color(child, parent, RB_BLACK); + rebalance = NULL; + } else { + rebalance = rb_is_black(node) ? parent : NULL; + } node->__rb_parent_color = old->__rb_parent_color; node->rb_left = old->rb_left; rb_set_parent(old->rb_left, node); } - if (color == RB_BLACK) - __rb_erase_color(child, parent, root); + if (rebalance) + __rb_erase_color(rebalance, root); } EXPORT_SYMBOL(rb_erase);