From patchwork Wed May 31 21:20:56 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Praveen Kumar X-Patchwork-Id: 9758187 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 85BC0603F7 for ; Wed, 31 May 2017 21:25:05 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 76ABB28423 for ; Wed, 31 May 2017 21:25:05 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 6B3FE284D2; Wed, 31 May 2017 21:25:05 +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 0E18D284D4 for ; Wed, 31 May 2017 21:25:05 +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 1dGB5A-0004wx-1J; Wed, 31 May 2017 21:23:08 +0000 Received: from mail6.bemta6.messagelabs.com ([193.109.254.103]) by lists.xenproject.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dGB59-0004vn-CF for xen-devel@lists.xen.org; Wed, 31 May 2017 21:23:07 +0000 Received: from [193.109.254.147] by server-2.bemta-6.messagelabs.com id E9/EB-03058-A343F295; Wed, 31 May 2017 21:23:06 +0000 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFlrGIsWRWlGSWpSXmKPExsVyMfTAQV0rE/1 Ig2t/WC2WfFzM4sDocXT3b6YAxijWzLyk/IoE1oxF146zFzyWqri0sJetgfGMaBcjF4eQwERG iYad7cwgDovASxaJ+2+/sXUxcnJICPSzSlw7mgdhx0nsWtXNCmFXS2w9NY8FxBYSUJPYMu8UM 8Sk34wST5tXMXUxcnCwCehKtN8qAKkREZCWuPb5MiNIDbNAO5PE/dnbmEASwgIeEm9PfQazWQ RUJZqW/QOzeQVsJWb8+cIMsUxeYtGmGWDLOIHip7pfMUEstpFY+GQy8wRGgQWMDKsYNYpTi8p Si3SNDfSSijLTM0pyEzNzdA0NzPRyU4uLE9NTcxKTivWS83M3MQJDiwEIdjD+XRt4iFGSg0lJ lLfCRi9SiC8pP6UyI7E4I76oNCe1+BCjDAeHkgTvDiP9SCHBotT01Iq0zBxgkMOkJTh4lER4O Y2B0rzFBYm5xZnpEKlTjMYcV66s+8LEMeXA9i9MQix5+XmpUuK8k0AmCYCUZpTmwQ2CRd8lRl kpYV5GoNOEeApSi3IzS1DlXzGKczAqCfMKgSzkycwrgdv3CugUJqBTdu3QBjmlJBEhJdXA2C6 btONvicDJYu+Yyn2L+GPUFmZEL9R/kVT11JPnpETLJZP037zSx3Xt/phkcShtSqy/nZrAHX3h RL7hnWKmD4ZTnx7RODuFJ/z6hsyO7TeTgy5vsvzz5pFUr+gXf3XuD8apKe+yby2e+D+jWq2dT 3NjycYZ2+Z38UVEuKolFPJUnFBZuOO4EktxRqKhFnNRcSIA2L38CLkCAAA= X-Env-Sender: kpraveen.lkml@gmail.com X-Msg-Ref: server-6.tower-27.messagelabs.com!1496265784!105617468!1 X-Originating-IP: [209.85.192.193] X-SpamReason: No, hits=0.5 required=7.0 tests=BODY_RANDOM_LONG X-StarScan-Received: X-StarScan-Version: 9.4.19; banners=-,-,- X-VirusChecked: Checked Received: (qmail 24570 invoked from network); 31 May 2017 21:23:05 -0000 Received: from mail-pf0-f193.google.com (HELO mail-pf0-f193.google.com) (209.85.192.193) by server-6.tower-27.messagelabs.com with AES128-GCM-SHA256 encrypted SMTP; 31 May 2017 21:23:05 -0000 Received: by mail-pf0-f193.google.com with SMTP id n23so4268226pfb.3 for ; Wed, 31 May 2017 14:23:05 -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=NoOuqw4ANZRMEjQAOBbDR+wqFi9BwoV0iOrfYfWRJd4=; b=gCk2beU7zFR/+9Zv7dkv6IP3Wi1RLUdaKkzyPRAAH4JlTmkO+F57MRFAyQE5O819J1 OPetvO+ELxCVv8vuCFB66m8+qi3SZNeXd/UkXbRVvnfRg4Fi0aBrKoGEvBqCWSiDUngx MytvMkqhkXZkY30KDU042KgwkyB43TjKKK5eDXzcndYQG5T1i2K46AqRehoYdlaACUnX RWBOYLXsncw04llJ14vSq7JM6OziQ+YuQGXVvCAbYdiecoOPh8pxN6/BO5s+5N6h1ved JXmVaJ752h2fmMz/3oUBZdvUHDqztdw5fcD2ejq1f2dZKvUFKTZFkLz1gylNcGveqTEl SvRQ== 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=NoOuqw4ANZRMEjQAOBbDR+wqFi9BwoV0iOrfYfWRJd4=; b=Xof51uo5Kpx8q174kSNh2ZfRHadtV1fyJ7yciDyBmMBIis7VvsnOAGumKyANJj0O1f D/F3eKQU0AoMJMTlHEtDMe7z/+UuoNGOqBjmV6Vcd5wB9jaX5g5kNmiRra2UuualliRA C0hiXVVWEvFaxi122m0XAd3j64d7tUkPh5RkTkwuLmYPR9Tdpkl3I4GcCDASMkudQs9V R6Wb5HP59sTFPAeK65AxnejONJvAeo36w2MB+XVNFrruANKXPUVPlxWYElLqAgyamC7w mxHASz+ha++bIB7z9uSVyxhk2wDMyH7BGkOFkx2GgJj5//HUYSjLJ8jXXoFMwlyuxmbM HM+g== X-Gm-Message-State: AODbwcDnVA9N3h8PRMDsm9vyl2F2anBq0XMzpucjtsev2VIhDxj4rGcB 9DDuuzIS/Xx+4rg/ X-Received: by 10.98.44.140 with SMTP id s134mr33094068pfs.193.1496265784238; Wed, 31 May 2017 14:23:04 -0700 (PDT) Received: from kpraveen.labs.blr.name ([103.227.99.58]) by smtp.gmail.com with ESMTPSA id t66sm29496699pfe.134.2017.05.31.14.23.00 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 31 May 2017 14:23:03 -0700 (PDT) From: Praveen Kumar To: xen-devel@lists.xen.org Date: Thu, 1 Jun 2017 02:50:56 +0530 Message-Id: <20170531212056.10583-18-kpraveen.lkml@gmail.com> X-Mailer: git-send-email 2.12.0 In-Reply-To: <20170531212056.10583-1-kpraveen.lkml@gmail.com> References: <20170531212056.10583-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, Praveen Kumar , jbeulich@suse.com Subject: [Xen-devel] [Resend][PATCH 17/17] rbtree: add postorder iteration functions 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 Postorder iteration yields all of a node's children prior to yielding the node itself, and this particular implementation also avoids examining the leaf links in a node after that node has been yielded. In what I expect will be its most common usage, postorder iteration allows the deletion of every node in an rbtree without modifying the rbtree nodes (no _requirement_ that they be nulled) while avoiding referencing child nodes after they have been "deleted" (most commonly, freed). I have only updated zswap to use this functionality at this point, but numerous bits of code (most notably in the filesystem drivers) use a hand rolled postorder iteration that NULLs child links as it traverses the tree. Each of those instances could be replaced with this common implementation. 1 & 2 add rbtree postorder iteration functions. 3 adds testing of the iteration to the rbtree runtime tests 4 allows building the rbtree runtime tests as builtins 5 updates zswap. This patch: Add postorder iteration functions for rbtree. These are useful for safely freeing an entire rbtree without modifying the tree at all. commit 9dee5c51516d2c3fff22633c1272c5652e68075a from Linux tree Signed-off-by: Praveen Kumar --- xen/common/rbtree.c | 45 +++++++++++++++++++++++++++++++++++++++++++++ xen/include/xen/rbtree.h | 4 ++++ 2 files changed, 49 insertions(+) diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c index 83b4892f54..3c994dcc0c 100644 --- a/xen/common/rbtree.c +++ b/xen/common/rbtree.c @@ -584,3 +584,48 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new, *new = *victim; } EXPORT_SYMBOL(rb_replace_node); + +static struct rb_node *rb_left_deepest_node(const struct rb_node *node) +{ + for (;;) + { + if (node->rb_left) + node = node->rb_left; + else if (node->rb_right) + node = node->rb_right; + else + return (struct rb_node *)node; + } +} + +struct rb_node *rb_next_postorder(const struct rb_node *node) +{ + const struct rb_node *parent; + if (!node) + return NULL; + parent = rb_parent(node); + + /* If we're sitting on node, we've already seen our children */ + if (parent && node == parent->rb_left && parent->rb_right) + { + /* If we are the parent's left node, go to the parent's right + * node then all the way down to the left + */ + return rb_left_deepest_node(parent->rb_right); + } else + /* Otherwise we are the parent's right node, and the parent + * should be next + */ + return (struct rb_node *)parent; +} +EXPORT_SYMBOL(rb_next_postorder); + +struct rb_node *rb_first_postorder(const struct rb_root *root) +{ + if (!root->rb_node) + return NULL; + + return rb_left_deepest_node(root->rb_node); +} +EXPORT_SYMBOL(rb_first_postorder); + diff --git a/xen/include/xen/rbtree.h b/xen/include/xen/rbtree.h index 107f1b12f2..24650a5cd8 100644 --- a/xen/include/xen/rbtree.h +++ b/xen/include/xen/rbtree.h @@ -66,4 +66,8 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, *rb_link = node; } +/* Postorder iteration - always visit the parent after its children */ +extern struct rb_node *rb_first_postorder(const struct rb_root *); +extern struct rb_node *rb_next_postorder(const struct rb_node *); + #endif /* __RBTREE_H__ */