| Message ID | 20240110103941.2e26da60@gandalf.local.home (mailing list archive) |
|---|---|
| State | Accepted |
| Commit | 7d8b3c02c6583bdf8d39e5f32ada33edbd437669 |
| Headers | show |
| Series | libtracecmd rbtree: Fix deletion of leaf nodes | expand |
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,
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,