From patchwork Mon Jul 3 19:58:07 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Praveen Kumar X-Patchwork-Id: 9823901 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 1DD5B60353 for ; Mon, 3 Jul 2017 20:01:14 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 11A2F27FB1 for ; Mon, 3 Jul 2017 20:01:14 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 0661D27FA6; Mon, 3 Jul 2017 20:01:14 +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 B455B27FB1 for ; Mon, 3 Jul 2017 20:01:12 +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 1dS7Ui-0000lW-CQ; Mon, 03 Jul 2017 19:58:52 +0000 Received: from mail6.bemta5.messagelabs.com ([195.245.231.135]) by lists.xenproject.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dS7Uh-0000lD-Hp for xen-devel@lists.xen.org; Mon, 03 Jul 2017 19:58:51 +0000 Received: from [85.158.139.211] by server-10.bemta-5.messagelabs.com id F7/36-01732-AF1AA595; Mon, 03 Jul 2017 19:58:50 +0000 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFlrKIsWRWlGSWpSXmKPExsXiVRvkpPtrYVS kwf+1bBZLPi5mcWD0OLr7N1MAYxRrZl5SfkUCa8b/LR3sBRdkKl58bGZvYLwo0cXIySEkMJFR 4sh9rS5GLg4WgZcsEgce9TKCOBIC/awSx7tWs4JUSQjESRza2cUGYVdJnFx4nBWiW01iy7xTz CANQgL/GSWWX5jK0sXIwcEmoCvRfqsApEZEQFri2ufLYEOZBb4zSqx5PwWsWVjAWuL34QvsIP UsAqoSR+YWgoR5BWwkPlzrg9orL7Fo0wwWEJtTwFZi5oMZTBB7bSR+XulnnMAosICRYRWjRnF qUVlqka6RhV5SUWZ6RkluYmaOrqGBqV5uanFxYnpqTmJSsV5yfu4mRmBg1TMwMO5g7Fvld4hR koNJSZTX9WZkpBBfUn5KZUZicUZ8UWlOavEhRhkODiUJ3nkLoiKFBItS01Mr0jJzgCEOk5bg4 FES4Z3cCJTmLS5IzC3OTIdInWI05ph0YPsXJo5XE/5/YxJiycvPS5US510NMkkApDSjNA9uEC z2LjHKSgnzMjIwMAjxFKQW5WaWoMq/YhTnYFQS5q0HmcKTmVcCt+8V0ClMQKc09ESAnFKSiJC SamBMXqEtZt36ZN6u1DzjsINzuas6Pke4T+O6lfJ7A1u9WNTqsFDmRW+q1miHcBh3C3NHTQl2 kQ2KdFv3OMp2zV25/cZnbFOVWjpm+R1tCjjOKczax37kyuLw19O+5p3q+JHhPnky56UfNlfUR Rimfvz+lmOhD+vkWb58JgELs6JkYwMmmAXOvKrEUpyRaKjFXFScCAD7MgLpuAIAAA== X-Env-Sender: kpraveen.lkml@gmail.com X-Msg-Ref: server-7.tower-206.messagelabs.com!1499111929!98330481!1 X-Originating-IP: [74.125.82.66] X-SpamReason: No, hits=0.0 required=7.0 tests= X-StarScan-Received: X-StarScan-Version: 9.4.25; banners=-,-,- X-VirusChecked: Checked Received: (qmail 56932 invoked from network); 3 Jul 2017 19:58:50 -0000 Received: from mail-wm0-f66.google.com (HELO mail-wm0-f66.google.com) (74.125.82.66) by server-7.tower-206.messagelabs.com with AES128-GCM-SHA256 encrypted SMTP; 3 Jul 2017 19:58:50 -0000 Received: by mail-wm0-f66.google.com with SMTP id u23so22443395wma.2 for ; Mon, 03 Jul 2017 12:58:50 -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=0khbW1PeyOKrsLSK4q1Lv+Io4ghcFGAbVroNncELHmc=; b=sxP3hyrwgd2lgf2FLzU1I7IJ1SHgIh8R51Y5jjUtocDKaaFn76ld95f5P40rt75Snp tzlmVUabpzMG2sJxyBv7epEyEMVzsyXIgHrxTZlnl7c1OwO/evgW83KQYvb/p05XTIck TG4rqu6Adin0EEJApKeBjsD+PiI9QoVw06Oksh9NXLxGMjVUSxr9ZNwe5bcZcQszU6Pr JaeMAPo0LDNzUA4zSIqYIyQclzpXWAzXHqtoyBhVzKTEhk9SCt2IM6qz194kKS8RoqPx eQvDpi0dGMVjIM80if8HSSYFzxLE/myeeE8xcGOkn7VEInQyo452TOQQxyWflDjdW2K+ jgmA== 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=0khbW1PeyOKrsLSK4q1Lv+Io4ghcFGAbVroNncELHmc=; b=YCpxWpUVB8UGFpknB6AoPFP1qQXefc1PbCryx+MT53Kiw6f8jFWJEd7SpyB56yl0Ol QUkZOYg/QsZolm1NBHfa9h3boC4remCU11YiVT3aOt57emrYzBR6cqPi8oQM9nkz6lsK g4Vn4BynKLLEpXFMu4CLFJTN9enHRvC7YZRt2tRExgOJdPLmQ8i6reKVW6RiToKZVKmI kdEj1K8xaIgzTrqkHJY8i8vnqf/4uH9/8TqZlOr1m2ZA0BllKt6i7Re7O5z4tkwi8LfI Gm0+zIHl+Ey9tnHe7fIAkW7aZLZ1idp/m4ptT83IFXKfkC5wOMmsE8r3CnSFdeFbapME djQA== X-Gm-Message-State: AIVw112ZEFdd0lg8wtojzbT9LCipzShWsfahoOnv+6yp95GRUQIHrUad D0jylpiaAohl/gx0 X-Received: by 10.28.65.135 with SMTP id o129mr12910540wma.20.1499111929434; Mon, 03 Jul 2017 12:58:49 -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.58.43 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Mon, 03 Jul 2017 12:58:48 -0700 (PDT) From: Praveen Kumar To: xen-devel@lists.xen.org Date: Tue, 4 Jul 2017 01:28:07 +0530 Message-Id: <20170703195821.29845-4-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 03/17] rbtree: empty nodes have no 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 Empty nodes have no color. We can make use of this property to simplify the code emitted by the RB_EMPTY_NODE and RB_CLEAR_NODE macros. Also, we can get rid of the rb_init_node function which had been introduced by commit 88d19cf37952 ("timers: Add rb_init_node() to allow for stack allocated rb nodes") to avoid some issue with the empty node's color not being initialized. I'm not sure what the RB_EMPTY_NODE checks in rb_prev() / rb_next() are doing there, though. axboe introduced them in commit 10fd48f2376d ("rbtree: fixed reversed RB_EMPTY_NODE and rb_next/prev"). The way I see it, the 'empty node' abstraction is only used by rbtree users to flag nodes that they haven't inserted in any rbtree, so asking the predecessor or successor of such nodes doesn't make any sense. One final rb_init_node() caller was recently added in sysctl code to implement faster sysctl name lookups. This code doesn't make use of RB_EMPTY_NODE at all, and from what I could see it only called rb_init_node() under the mistaken assumption that such initialization was required before node insertion. [sfr@canb.auug.org.au: fix net/ceph/osd_client.c build] 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" Cc: John Stultz Signed-off-by: Stephen Rothwell Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds [Linux commit 4c199a93a2d36b277a9fd209a0f2793f8460a215] Ported rbtree.h and rbtree.c changes which are relevant to Xen. Signed-off-by: Praveen Kumar --- xen/common/rbtree.c | 4 ++-- xen/include/xen/rbtree.h | 8 +++++--- 2 files changed, 7 insertions(+), 5 deletions(-) diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c index 3a19b44a2f..e2a665118b 100644 --- a/xen/common/rbtree.c +++ b/xen/common/rbtree.c @@ -316,7 +316,7 @@ struct rb_node *rb_next(const struct rb_node *node) { struct rb_node *parent; - if (rb_parent(node) == node) + if (RB_EMPTY_NODE(node)) return NULL; /* If we have a right-hand child, go down and then left as far @@ -345,7 +345,7 @@ struct rb_node *rb_prev(const struct rb_node *node) { struct rb_node *parent; - if (rb_parent(node) == node) + if (RB_EMPTY_NODE(node)) return NULL; /* If we have a left-hand child, go down and then right as far diff --git a/xen/include/xen/rbtree.h b/xen/include/xen/rbtree.h index 1a13ea66fa..4249752dcb 100644 --- a/xen/include/xen/rbtree.h +++ b/xen/include/xen/rbtree.h @@ -53,9 +53,11 @@ static inline void rb_set_color(struct rb_node *rb, int color) #define RB_ROOT (struct rb_root) { NULL, } #define rb_entry(ptr, type, member) container_of(ptr, type, member) -#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) -#define RB_EMPTY_NODE(node) (rb_parent(node) == node) -#define RB_CLEAR_NODE(node) (rb_set_parent(node, node)) +#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) + +/* 'empty' nodes are nodes that are known not to be inserted in an rbree */ +#define RB_EMPTY_NODE(node) ((node)->rb_parent_color == (unsigned long)(node)) +#define RB_CLEAR_NODE(node) ((node)->rb_parent_color = (unsigned long)(node)) extern void rb_insert_color(struct rb_node *, struct rb_root *); extern void rb_erase(struct rb_node *, struct rb_root *);