From: Pierre Gondois <pierre.gondois@arm.com>
To: Steven Rostedt <rostedt@goodmis.org>,
Linux Trace Devel <linux-trace-devel@vger.kernel.org>
Subject: Re: [PATCH] libtracecmd rbtree: Fix deletion of leaf nodes
Date: Thu, 11 Jan 2024 10:13:31 +0100 [thread overview]
Message-ID: <76a1bb98-a573-4bd2-aee3-b1b98cc5be74@arm.com> (raw)
In-Reply-To: <20240110103941.2e26da60@gandalf.local.home>
Thanks for the fix,
Tested-by: Pierre Gondois <pierre.gondois@arm.com>
On 1/10/24 16:39, Steven Rostedt wrote:
> From: "Steven Rostedt (Google)" <rostedt@goodmis.org>
>
> In the rbtree deletion, the deletion had the logic:
>
> if (!node->left || !node->right)
> y = node;
> else
> y = next_node(node);
>
> if (y->left)
> x = y->left;
> else
> x = y->right;
>
> x->parent = y->parent;
>
> Where if the node had both right and left, the y returned would not have
> children. This is fine, but the x would be NULL. In that case, do not update
> the parent of x. But instead, skip over and continue the work. As x->parent
> would be the same as y->parent, instead of checking the x->parent (where x
> could be NULL), check y->parent, which is already known to be the same as
> x->parent if x is not NULL.
>
> Also add another check_tree() at the end of the deletion routine.
>
> Fixes: 5274db32a ("libtracecmd: Use an rbtree for mapping of cache pages")
> Bugzilla: https://bugzilla.kernel.org/show_bug.cgi?id=218357
> Reported-by: pierre.gondois@arm.com
> Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
> ---
> lib/trace-cmd/trace-rbtree.c | 8 +++++---
> 1 file changed, 5 insertions(+), 3 deletions(-)
>
> diff --git a/lib/trace-cmd/trace-rbtree.c b/lib/trace-cmd/trace-rbtree.c
> index 24beabec..90671819 100644
> --- a/lib/trace-cmd/trace-rbtree.c
> +++ b/lib/trace-cmd/trace-rbtree.c
> @@ -314,7 +314,7 @@ void trace_rbtree_delete(struct trace_rbtree *tree, struct trace_rbtree_node *no
> struct trace_rbtree_node *x, *y;
> bool do_fixup = false;
>
> - if (!node->left && !node->right) {
> + if (!node->left && !node->right && !node->parent) {
> tree->node = NULL;
> goto out;
> }
> @@ -329,9 +329,10 @@ void trace_rbtree_delete(struct trace_rbtree *tree, struct trace_rbtree_node *no
> else
> x = y->right;
>
> - x->parent = y->parent;
> + if (x)
> + x->parent = y->parent;
>
> - if (!x->parent) {
> + if (!y->parent) {
> tree->node = x;
> } else {
> if (is_left(y))
> @@ -367,6 +368,7 @@ void trace_rbtree_delete(struct trace_rbtree *tree, struct trace_rbtree_node *no
> out:
> node->parent = node->left = node->right = NULL;
> tree->nr_nodes--;
> + check_tree(tree);
> }
>
> __hidden struct trace_rbtree_node *trace_rbtree_next(struct trace_rbtree *tree,
prev parent reply other threads:[~2024-01-11 9:13 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-01-10 15:39 [PATCH] libtracecmd rbtree: Fix deletion of leaf nodes Steven Rostedt
2024-01-11 9:13 ` Pierre Gondois [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=76a1bb98-a573-4bd2-aee3-b1b98cc5be74@arm.com \
--to=pierre.gondois@arm.com \
--cc=linux-trace-devel@vger.kernel.org \
--cc=rostedt@goodmis.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).