diff options
| author | Steven Rostedt (Google) <rostedt@goodmis.org> | 2024-01-10 10:39:41 -0500 |
|---|---|---|
| committer | Steven Rostedt (Google) <rostedt@goodmis.org> | 2024-01-10 13:49:49 -0500 |
| commit | 7d8b3c02c6583bdf8d39e5f32ada33edbd437669 (patch) | |
| tree | a32f62b77528ea3759b82a6ad446eeaf323e0067 | |
| parent | 6ef58ed45cb03ecc48f1901a9beb16d8dc9252f5 (diff) | |
| download | trace-cmd-7d8b3c02c6583bdf8d39e5f32ada33edbd437669.tar.gz | |
libtracecmd rbtree: Fix deletion of leaf nodes
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.
Link: https://lore.kernel.org/linux-trace-devel/20240110103941.2e26da60@gandalf.local.home
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>
| -rw-r--r-- | lib/trace-cmd/trace-rbtree.c | 8 |
1 files 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, |