[PATCH 1/2] perf report: Use map_symbol__copy() when copying callchians

[PATCH 1/2] perf report: Use map_symbol__copy() when copying callchians

[Namhyung Kim]

It seems there are places to miss updating refcount of maps.
Let's use map_symbol__copy() helper to properly copy them with
refcounts updated.

Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/util/callchain.c | 9 +++------
 1 file changed, 3 insertions(+), 6 deletions(-)

diff --git a/tools/perf/util/callchain.c b/tools/perf/util/callchain.c
index 0c7564747a14e539..4fe7a10de33b6de8 100644
--- a/tools/perf/util/callchain.c
+++ b/tools/perf/util/callchain.c
@@ -590,8 +590,7 @@ fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
 		}
 		call->ip = cursor_node->ip;
 		call->ms = cursor_node->ms;
-		call->ms.map = map__get(call->ms.map);
-		call->ms.maps = maps__get(call->ms.maps);
+		map_symbol__copy(&call->ms, &cursor_node->ms);
 		call->srcline = cursor_node->srcline;
 
 		if (cursor_node->branch) {
@@ -1094,9 +1093,7 @@ int callchain_cursor_append(struct callchain_cursor *cursor,
 
 	node->ip = ip;
 	map_symbol__exit(&node->ms);
-	node->ms = *ms;
-	node->ms.maps = maps__get(ms->maps);
-	node->ms.map = map__get(ms->map);
+	map_symbol__copy(&node->ms, ms);
 	node->branch = branch;
 	node->nr_loop_iter = nr_loop_iter;
 	node->iter_cycles = iter_cycles;
@@ -1564,7 +1561,7 @@ int callchain_node__make_parent_list(struct callchain_node *node)
 				goto out;
 			*new = *chain;
 			new->has_children = false;
-			new->ms.map = map__get(new->ms.map);
+			map_symbol__copy(&new->ms, &chain->ms);
 			list_add_tail(&new->list, &head);
 		}
 		parent = parent->parent;
-- 
2.48.1.711.g2feabab25a-goog

[PATCH 2/2] perf report: Fix memory leaks in the hierarchy mode

[Namhyung Kim]

Ian told me that there are many memory leaks in the hierarchy mode.  I
can easily reproduce it with the follwing command.

  $ make DEBUG=1 EXTRA_CFLAGS=-fsanitize=leak

  $ perf record --latency -g -- ./perf test -w thloop

  $ perf report -H --stdio
  ...
  Indirect leak of 168 byte(s) in 21 object(s) allocated from:
      #0 0x7f3414c16c65 in malloc ../../../../src/libsanitizer/lsan/lsan_interceptors.cpp:75
      #1 0x55ed3602346e in map__get util/map.h:189
      #2 0x55ed36024cc4 in hist_entry__init util/hist.c:476
      #3 0x55ed36025208 in hist_entry__new util/hist.c:588
      #4 0x55ed36027c05 in hierarchy_insert_entry util/hist.c:1587
      #5 0x55ed36027e2e in hists__hierarchy_insert_entry util/hist.c:1638
      #6 0x55ed36027fa4 in hists__collapse_insert_entry util/hist.c:1685
      #7 0x55ed360283e8 in hists__collapse_resort util/hist.c:1776
      #8 0x55ed35de0323 in report__collapse_hists /home/namhyung/project/linux/tools/perf/builtin-report.c:735
      #9 0x55ed35de15b4 in __cmd_report /home/namhyung/project/linux/tools/perf/builtin-report.c:1119
      #10 0x55ed35de43dc in cmd_report /home/namhyung/project/linux/tools/perf/builtin-report.c:1867
      #11 0x55ed35e66767 in run_builtin /home/namhyung/project/linux/tools/perf/perf.c:351
      #12 0x55ed35e66a0e in handle_internal_command /home/namhyung/project/linux/tools/perf/perf.c:404
      #13 0x55ed35e66b67 in run_argv /home/namhyung/project/linux/tools/perf/perf.c:448
      #14 0x55ed35e66eb0 in main /home/namhyung/project/linux/tools/perf/perf.c:556
      #15 0x7f340ac33d67 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
  ...

  $ perf report -H --stdio 2>&1 | grep -c '^Indirect leak'
  93

I found that hist_entry__delete() missed to release child entries in the
hierarchy tree (hroot_{in,out}).  It needs to iterate the child entries
and call hist_entry__delete() recursively.

After this change:

  $ perf report -H --stdio 2>&1 | grep -c '^Indirect leak'
  0

Reported-by: Ian Rogers <irogers@google.com>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/util/hist.c | 9 +++++++++
 1 file changed, 9 insertions(+)

diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c
index fbf131aeae7ffe9b..bbc6a299b5106c3b 100644
--- a/tools/perf/util/hist.c
+++ b/tools/perf/util/hist.c
@@ -1385,6 +1385,15 @@ void hist_entry__delete(struct hist_entry *he)
 {
 	struct hist_entry_ops *ops = he->ops;
 
+	while (!RB_EMPTY_ROOT(&he->hroot_out.rb_root)) {
+		struct rb_node *node = rb_first(&he->hroot_out.rb_root);
+		struct hist_entry *child = rb_entry(node, struct hist_entry, rb_node);
+
+		rb_erase_init(node, &he->hroot_out.rb_root);
+
+		hist_entry__delete(child);
+	}
+
 	thread__zput(he->thread);
 	map_symbol__exit(&he->ms);
 
-- 
2.48.1.711.g2feabab25a-goog

Re: [PATCH 2/2] perf report: Fix memory leaks in the hierarchy mode

[Ian Rogers]

On Wed, Mar 5, 2025 at 11:51 PM Namhyung Kim <namhyung@kernel.org> wrote:
>
> Ian told me that there are many memory leaks in the hierarchy mode.  I
> can easily reproduce it with the follwing command.
>
>   $ make DEBUG=1 EXTRA_CFLAGS=-fsanitize=leak
>
>   $ perf record --latency -g -- ./perf test -w thloop
>
>   $ perf report -H --stdio
>   ...
>   Indirect leak of 168 byte(s) in 21 object(s) allocated from:
>       #0 0x7f3414c16c65 in malloc ../../../../src/libsanitizer/lsan/lsan_interceptors.cpp:75
>       #1 0x55ed3602346e in map__get util/map.h:189
>       #2 0x55ed36024cc4 in hist_entry__init util/hist.c:476
>       #3 0x55ed36025208 in hist_entry__new util/hist.c:588
>       #4 0x55ed36027c05 in hierarchy_insert_entry util/hist.c:1587
>       #5 0x55ed36027e2e in hists__hierarchy_insert_entry util/hist.c:1638
>       #6 0x55ed36027fa4 in hists__collapse_insert_entry util/hist.c:1685
>       #7 0x55ed360283e8 in hists__collapse_resort util/hist.c:1776
>       #8 0x55ed35de0323 in report__collapse_hists /home/namhyung/project/linux/tools/perf/builtin-report.c:735
>       #9 0x55ed35de15b4 in __cmd_report /home/namhyung/project/linux/tools/perf/builtin-report.c:1119
>       #10 0x55ed35de43dc in cmd_report /home/namhyung/project/linux/tools/perf/builtin-report.c:1867
>       #11 0x55ed35e66767 in run_builtin /home/namhyung/project/linux/tools/perf/perf.c:351
>       #12 0x55ed35e66a0e in handle_internal_command /home/namhyung/project/linux/tools/perf/perf.c:404
>       #13 0x55ed35e66b67 in run_argv /home/namhyung/project/linux/tools/perf/perf.c:448
>       #14 0x55ed35e66eb0 in main /home/namhyung/project/linux/tools/perf/perf.c:556
>       #15 0x7f340ac33d67 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
>   ...
>
>   $ perf report -H --stdio 2>&1 | grep -c '^Indirect leak'
>   93
>
> I found that hist_entry__delete() missed to release child entries in the
> hierarchy tree (hroot_{in,out}).  It needs to iterate the child entries
> and call hist_entry__delete() recursively.
>
> After this change:
>
>   $ perf report -H --stdio 2>&1 | grep -c '^Indirect leak'
>   0
>
> Reported-by: Ian Rogers <irogers@google.com>
> Signed-off-by: Namhyung Kim <namhyung@kernel.org>
> ---
>  tools/perf/util/hist.c | 9 +++++++++
>  1 file changed, 9 insertions(+)
>
> diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c
> index fbf131aeae7ffe9b..bbc6a299b5106c3b 100644
> --- a/tools/perf/util/hist.c
> +++ b/tools/perf/util/hist.c
> @@ -1385,6 +1385,15 @@ void hist_entry__delete(struct hist_entry *he)
>  {
>         struct hist_entry_ops *ops = he->ops;
>
> +       while (!RB_EMPTY_ROOT(&he->hroot_out.rb_root)) {
> +               struct rb_node *node = rb_first(&he->hroot_out.rb_root);
> +               struct hist_entry *child = rb_entry(node, struct hist_entry, rb_node);
> +
> +               rb_erase_init(node, &he->hroot_out.rb_root);
> +
> +               hist_entry__delete(child);
> +       }

Thanks for the fix! A nit, iterating the rbtree of N nodes and calling
erase on the first entry, an O(log N) operation, means this is a O(N *
log N). rbtree.h has rbtree_postorder_for_each_entry_safe:
https://web.git.kernel.org/pub/scm/linux/kernel/git/perf/perf-tools-next.git/tree/tools/include/linux/rbtree.h?h=perf-tools-next#n81
```
 * rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of
 * given type allowing the backing memory of @pos to be invalidated
```
which is O(N). I think this code would be better something like:
```
struct hist_entry *pos, *tmp;
rbtree_postorder_for_each_entry_safe(pos, tmp, he->hroot_out.rb_root, rb_node)
        hist_entry__delete(pos);
```

Thanks!
Ian

> +
>         thread__zput(he->thread);
>         map_symbol__exit(&he->ms);
>
> --
> 2.48.1.711.g2feabab25a-goog
>

Re: [PATCH 2/2] perf report: Fix memory leaks in the hierarchy mode

[Namhyung Kim]

Hi Ian,

On Thu, Mar 06, 2025 at 08:55:05AM -0800, Ian Rogers wrote:
> On Wed, Mar 5, 2025 at 11:51 PM Namhyung Kim <namhyung@kernel.org> wrote:
> >
> > Ian told me that there are many memory leaks in the hierarchy mode.  I
> > can easily reproduce it with the follwing command.
> >
> >   $ make DEBUG=1 EXTRA_CFLAGS=-fsanitize=leak
> >
> >   $ perf record --latency -g -- ./perf test -w thloop
> >
> >   $ perf report -H --stdio
> >   ...
> >   Indirect leak of 168 byte(s) in 21 object(s) allocated from:
> >       #0 0x7f3414c16c65 in malloc ../../../../src/libsanitizer/lsan/lsan_interceptors.cpp:75
> >       #1 0x55ed3602346e in map__get util/map.h:189
> >       #2 0x55ed36024cc4 in hist_entry__init util/hist.c:476
> >       #3 0x55ed36025208 in hist_entry__new util/hist.c:588
> >       #4 0x55ed36027c05 in hierarchy_insert_entry util/hist.c:1587
> >       #5 0x55ed36027e2e in hists__hierarchy_insert_entry util/hist.c:1638
> >       #6 0x55ed36027fa4 in hists__collapse_insert_entry util/hist.c:1685
> >       #7 0x55ed360283e8 in hists__collapse_resort util/hist.c:1776
> >       #8 0x55ed35de0323 in report__collapse_hists /home/namhyung/project/linux/tools/perf/builtin-report.c:735
> >       #9 0x55ed35de15b4 in __cmd_report /home/namhyung/project/linux/tools/perf/builtin-report.c:1119
> >       #10 0x55ed35de43dc in cmd_report /home/namhyung/project/linux/tools/perf/builtin-report.c:1867
> >       #11 0x55ed35e66767 in run_builtin /home/namhyung/project/linux/tools/perf/perf.c:351
> >       #12 0x55ed35e66a0e in handle_internal_command /home/namhyung/project/linux/tools/perf/perf.c:404
> >       #13 0x55ed35e66b67 in run_argv /home/namhyung/project/linux/tools/perf/perf.c:448
> >       #14 0x55ed35e66eb0 in main /home/namhyung/project/linux/tools/perf/perf.c:556
> >       #15 0x7f340ac33d67 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
> >   ...
> >
> >   $ perf report -H --stdio 2>&1 | grep -c '^Indirect leak'
> >   93
> >
> > I found that hist_entry__delete() missed to release child entries in the
> > hierarchy tree (hroot_{in,out}).  It needs to iterate the child entries
> > and call hist_entry__delete() recursively.
> >
> > After this change:
> >
> >   $ perf report -H --stdio 2>&1 | grep -c '^Indirect leak'
> >   0
> >
> > Reported-by: Ian Rogers <irogers@google.com>
> > Signed-off-by: Namhyung Kim <namhyung@kernel.org>
> > ---
> >  tools/perf/util/hist.c | 9 +++++++++
> >  1 file changed, 9 insertions(+)
> >
> > diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c
> > index fbf131aeae7ffe9b..bbc6a299b5106c3b 100644
> > --- a/tools/perf/util/hist.c
> > +++ b/tools/perf/util/hist.c
> > @@ -1385,6 +1385,15 @@ void hist_entry__delete(struct hist_entry *he)
> >  {
> >         struct hist_entry_ops *ops = he->ops;
> >
> > +       while (!RB_EMPTY_ROOT(&he->hroot_out.rb_root)) {
> > +               struct rb_node *node = rb_first(&he->hroot_out.rb_root);
> > +               struct hist_entry *child = rb_entry(node, struct hist_entry, rb_node);
> > +
> > +               rb_erase_init(node, &he->hroot_out.rb_root);
> > +
> > +               hist_entry__delete(child);
> > +       }
> 
> Thanks for the fix! A nit, iterating the rbtree of N nodes and calling
> erase on the first entry, an O(log N) operation, means this is a O(N *
> log N). rbtree.h has rbtree_postorder_for_each_entry_safe:
> https://web.git.kernel.org/pub/scm/linux/kernel/git/perf/perf-tools-next.git/tree/tools/include/linux/rbtree.h?h=perf-tools-next#n81
> ```
>  * rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of
>  * given type allowing the backing memory of @pos to be invalidated
> ```
> which is O(N). I think this code would be better something like:
> ```
> struct hist_entry *pos, *tmp;
> rbtree_postorder_for_each_entry_safe(pos, tmp, he->hroot_out.rb_root, rb_node)
>         hist_entry__delete(pos);
> ```

Thanks for your review!  I was wondering if there's something like this.
Will update with that.

Thanks,
Namhyung

Re: [PATCH 2/2] perf report: Fix memory leaks in the hierarchy mode

[Namhyung Kim]

On Thu, Mar 06, 2025 at 09:07:00AM -0800, Namhyung Kim wrote:
> Hi Ian,
> 
> On Thu, Mar 06, 2025 at 08:55:05AM -0800, Ian Rogers wrote:
> > On Wed, Mar 5, 2025 at 11:51 PM Namhyung Kim <namhyung@kernel.org> wrote:
> > >
> > > Ian told me that there are many memory leaks in the hierarchy mode.  I
> > > can easily reproduce it with the follwing command.
> > >
> > >   $ make DEBUG=1 EXTRA_CFLAGS=-fsanitize=leak
> > >
> > >   $ perf record --latency -g -- ./perf test -w thloop
> > >
> > >   $ perf report -H --stdio
> > >   ...
> > >   Indirect leak of 168 byte(s) in 21 object(s) allocated from:
> > >       #0 0x7f3414c16c65 in malloc ../../../../src/libsanitizer/lsan/lsan_interceptors.cpp:75
> > >       #1 0x55ed3602346e in map__get util/map.h:189
> > >       #2 0x55ed36024cc4 in hist_entry__init util/hist.c:476
> > >       #3 0x55ed36025208 in hist_entry__new util/hist.c:588
> > >       #4 0x55ed36027c05 in hierarchy_insert_entry util/hist.c:1587
> > >       #5 0x55ed36027e2e in hists__hierarchy_insert_entry util/hist.c:1638
> > >       #6 0x55ed36027fa4 in hists__collapse_insert_entry util/hist.c:1685
> > >       #7 0x55ed360283e8 in hists__collapse_resort util/hist.c:1776
> > >       #8 0x55ed35de0323 in report__collapse_hists /home/namhyung/project/linux/tools/perf/builtin-report.c:735
> > >       #9 0x55ed35de15b4 in __cmd_report /home/namhyung/project/linux/tools/perf/builtin-report.c:1119
> > >       #10 0x55ed35de43dc in cmd_report /home/namhyung/project/linux/tools/perf/builtin-report.c:1867
> > >       #11 0x55ed35e66767 in run_builtin /home/namhyung/project/linux/tools/perf/perf.c:351
> > >       #12 0x55ed35e66a0e in handle_internal_command /home/namhyung/project/linux/tools/perf/perf.c:404
> > >       #13 0x55ed35e66b67 in run_argv /home/namhyung/project/linux/tools/perf/perf.c:448
> > >       #14 0x55ed35e66eb0 in main /home/namhyung/project/linux/tools/perf/perf.c:556
> > >       #15 0x7f340ac33d67 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
> > >   ...
> > >
> > >   $ perf report -H --stdio 2>&1 | grep -c '^Indirect leak'
> > >   93
> > >
> > > I found that hist_entry__delete() missed to release child entries in the
> > > hierarchy tree (hroot_{in,out}).  It needs to iterate the child entries
> > > and call hist_entry__delete() recursively.
> > >
> > > After this change:
> > >
> > >   $ perf report -H --stdio 2>&1 | grep -c '^Indirect leak'
> > >   0
> > >
> > > Reported-by: Ian Rogers <irogers@google.com>
> > > Signed-off-by: Namhyung Kim <namhyung@kernel.org>
> > > ---
> > >  tools/perf/util/hist.c | 9 +++++++++
> > >  1 file changed, 9 insertions(+)
> > >
> > > diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c
> > > index fbf131aeae7ffe9b..bbc6a299b5106c3b 100644
> > > --- a/tools/perf/util/hist.c
> > > +++ b/tools/perf/util/hist.c
> > > @@ -1385,6 +1385,15 @@ void hist_entry__delete(struct hist_entry *he)
> > >  {
> > >         struct hist_entry_ops *ops = he->ops;
> > >
> > > +       while (!RB_EMPTY_ROOT(&he->hroot_out.rb_root)) {
> > > +               struct rb_node *node = rb_first(&he->hroot_out.rb_root);
> > > +               struct hist_entry *child = rb_entry(node, struct hist_entry, rb_node);
> > > +
> > > +               rb_erase_init(node, &he->hroot_out.rb_root);
> > > +
> > > +               hist_entry__delete(child);
> > > +       }
> > 
> > Thanks for the fix! A nit, iterating the rbtree of N nodes and calling
> > erase on the first entry, an O(log N) operation, means this is a O(N *
> > log N). rbtree.h has rbtree_postorder_for_each_entry_safe:
> > https://web.git.kernel.org/pub/scm/linux/kernel/git/perf/perf-tools-next.git/tree/tools/include/linux/rbtree.h?h=perf-tools-next#n81
> > ```
> >  * rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of
> >  * given type allowing the backing memory of @pos to be invalidated
> > ```
> > which is O(N). I think this code would be better something like:
> > ```
> > struct hist_entry *pos, *tmp;
> > rbtree_postorder_for_each_entry_safe(pos, tmp, he->hroot_out.rb_root, rb_node)
> >         hist_entry__delete(pos);
> > ```
> 
> Thanks for your review!  I was wondering if there's something like this.
> Will update with that.

I found that the following comments:

 * Note, however, that it cannot handle other modifications that re-order the
 * rbtree it is iterating over. This includes calling rb_erase() on @pos, as
 * rb_erase() may rebalance the tree, causing us to miss some nodes.

So I cannot use this here.

Thanks,
Namhyung

Re: [PATCH 2/2] perf report: Fix memory leaks in the hierarchy mode

[Ian Rogers]

On Thu, Mar 6, 2025 at 6:01 PM Namhyung Kim <namhyung@kernel.org> wrote:
>
> On Thu, Mar 06, 2025 at 09:07:00AM -0800, Namhyung Kim wrote:
> > Hi Ian,
> >
> > On Thu, Mar 06, 2025 at 08:55:05AM -0800, Ian Rogers wrote:
> > > On Wed, Mar 5, 2025 at 11:51 PM Namhyung Kim <namhyung@kernel.org> wrote:
> > > >
> > > > Ian told me that there are many memory leaks in the hierarchy mode.  I
> > > > can easily reproduce it with the follwing command.
> > > >
> > > >   $ make DEBUG=1 EXTRA_CFLAGS=-fsanitize=leak
> > > >
> > > >   $ perf record --latency -g -- ./perf test -w thloop
> > > >
> > > >   $ perf report -H --stdio
> > > >   ...
> > > >   Indirect leak of 168 byte(s) in 21 object(s) allocated from:
> > > >       #0 0x7f3414c16c65 in malloc ../../../../src/libsanitizer/lsan/lsan_interceptors.cpp:75
> > > >       #1 0x55ed3602346e in map__get util/map.h:189
> > > >       #2 0x55ed36024cc4 in hist_entry__init util/hist.c:476
> > > >       #3 0x55ed36025208 in hist_entry__new util/hist.c:588
> > > >       #4 0x55ed36027c05 in hierarchy_insert_entry util/hist.c:1587
> > > >       #5 0x55ed36027e2e in hists__hierarchy_insert_entry util/hist.c:1638
> > > >       #6 0x55ed36027fa4 in hists__collapse_insert_entry util/hist.c:1685
> > > >       #7 0x55ed360283e8 in hists__collapse_resort util/hist.c:1776
> > > >       #8 0x55ed35de0323 in report__collapse_hists /home/namhyung/project/linux/tools/perf/builtin-report.c:735
> > > >       #9 0x55ed35de15b4 in __cmd_report /home/namhyung/project/linux/tools/perf/builtin-report.c:1119
> > > >       #10 0x55ed35de43dc in cmd_report /home/namhyung/project/linux/tools/perf/builtin-report.c:1867
> > > >       #11 0x55ed35e66767 in run_builtin /home/namhyung/project/linux/tools/perf/perf.c:351
> > > >       #12 0x55ed35e66a0e in handle_internal_command /home/namhyung/project/linux/tools/perf/perf.c:404
> > > >       #13 0x55ed35e66b67 in run_argv /home/namhyung/project/linux/tools/perf/perf.c:448
> > > >       #14 0x55ed35e66eb0 in main /home/namhyung/project/linux/tools/perf/perf.c:556
> > > >       #15 0x7f340ac33d67 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
> > > >   ...
> > > >
> > > >   $ perf report -H --stdio 2>&1 | grep -c '^Indirect leak'
> > > >   93
> > > >
> > > > I found that hist_entry__delete() missed to release child entries in the
> > > > hierarchy tree (hroot_{in,out}).  It needs to iterate the child entries
> > > > and call hist_entry__delete() recursively.
> > > >
> > > > After this change:
> > > >
> > > >   $ perf report -H --stdio 2>&1 | grep -c '^Indirect leak'
> > > >   0
> > > >
> > > > Reported-by: Ian Rogers <irogers@google.com>
> > > > Signed-off-by: Namhyung Kim <namhyung@kernel.org>
> > > > ---
> > > >  tools/perf/util/hist.c | 9 +++++++++
> > > >  1 file changed, 9 insertions(+)
> > > >
> > > > diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c
> > > > index fbf131aeae7ffe9b..bbc6a299b5106c3b 100644
> > > > --- a/tools/perf/util/hist.c
> > > > +++ b/tools/perf/util/hist.c
> > > > @@ -1385,6 +1385,15 @@ void hist_entry__delete(struct hist_entry *he)
> > > >  {
> > > >         struct hist_entry_ops *ops = he->ops;
> > > >
> > > > +       while (!RB_EMPTY_ROOT(&he->hroot_out.rb_root)) {
> > > > +               struct rb_node *node = rb_first(&he->hroot_out.rb_root);
> > > > +               struct hist_entry *child = rb_entry(node, struct hist_entry, rb_node);
> > > > +
> > > > +               rb_erase_init(node, &he->hroot_out.rb_root);
> > > > +
> > > > +               hist_entry__delete(child);
> > > > +       }
> > >
> > > Thanks for the fix! A nit, iterating the rbtree of N nodes and calling
> > > erase on the first entry, an O(log N) operation, means this is a O(N *
> > > log N). rbtree.h has rbtree_postorder_for_each_entry_safe:
> > > https://web.git.kernel.org/pub/scm/linux/kernel/git/perf/perf-tools-next.git/tree/tools/include/linux/rbtree.h?h=perf-tools-next#n81
> > > ```
> > >  * rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of
> > >  * given type allowing the backing memory of @pos to be invalidated
> > > ```
> > > which is O(N). I think this code would be better something like:
> > > ```
> > > struct hist_entry *pos, *tmp;
> > > rbtree_postorder_for_each_entry_safe(pos, tmp, he->hroot_out.rb_root, rb_node)
> > >         hist_entry__delete(pos);
> > > ```
> >
> > Thanks for your review!  I was wondering if there's something like this.
> > Will update with that.
>
> I found that the following comments:
>
>  * Note, however, that it cannot handle other modifications that re-order the
>  * rbtree it is iterating over. This includes calling rb_erase() on @pos, as
>  * rb_erase() may rebalance the tree, causing us to miss some nodes.
>
> So I cannot use this here.

I thought the tree is no longer in use after the hist_entry__delete,
so you don't need to maintain the child/parent pointers as everything
is going to get freed. Here is what I think is a similar use:
https://web.git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/kernel/trace/trace_stat.c#n51

Thanks,
Ian

Re: [PATCH 2/2] perf report: Fix memory leaks in the hierarchy mode

[Namhyung Kim]

On Thu, Mar 06, 2025 at 08:50:46PM -0800, Ian Rogers wrote:
> On Thu, Mar 6, 2025 at 6:01 PM Namhyung Kim <namhyung@kernel.org> wrote:
> >
> > On Thu, Mar 06, 2025 at 09:07:00AM -0800, Namhyung Kim wrote:
> > > Hi Ian,
> > >
> > > On Thu, Mar 06, 2025 at 08:55:05AM -0800, Ian Rogers wrote:
> > > > On Wed, Mar 5, 2025 at 11:51 PM Namhyung Kim <namhyung@kernel.org> wrote:
> > > > >
> > > > > Ian told me that there are many memory leaks in the hierarchy mode.  I
> > > > > can easily reproduce it with the follwing command.
> > > > >
> > > > >   $ make DEBUG=1 EXTRA_CFLAGS=-fsanitize=leak
> > > > >
> > > > >   $ perf record --latency -g -- ./perf test -w thloop
> > > > >
> > > > >   $ perf report -H --stdio
> > > > >   ...
> > > > >   Indirect leak of 168 byte(s) in 21 object(s) allocated from:
> > > > >       #0 0x7f3414c16c65 in malloc ../../../../src/libsanitizer/lsan/lsan_interceptors.cpp:75
> > > > >       #1 0x55ed3602346e in map__get util/map.h:189
> > > > >       #2 0x55ed36024cc4 in hist_entry__init util/hist.c:476
> > > > >       #3 0x55ed36025208 in hist_entry__new util/hist.c:588
> > > > >       #4 0x55ed36027c05 in hierarchy_insert_entry util/hist.c:1587
> > > > >       #5 0x55ed36027e2e in hists__hierarchy_insert_entry util/hist.c:1638
> > > > >       #6 0x55ed36027fa4 in hists__collapse_insert_entry util/hist.c:1685
> > > > >       #7 0x55ed360283e8 in hists__collapse_resort util/hist.c:1776
> > > > >       #8 0x55ed35de0323 in report__collapse_hists /home/namhyung/project/linux/tools/perf/builtin-report.c:735
> > > > >       #9 0x55ed35de15b4 in __cmd_report /home/namhyung/project/linux/tools/perf/builtin-report.c:1119
> > > > >       #10 0x55ed35de43dc in cmd_report /home/namhyung/project/linux/tools/perf/builtin-report.c:1867
> > > > >       #11 0x55ed35e66767 in run_builtin /home/namhyung/project/linux/tools/perf/perf.c:351
> > > > >       #12 0x55ed35e66a0e in handle_internal_command /home/namhyung/project/linux/tools/perf/perf.c:404
> > > > >       #13 0x55ed35e66b67 in run_argv /home/namhyung/project/linux/tools/perf/perf.c:448
> > > > >       #14 0x55ed35e66eb0 in main /home/namhyung/project/linux/tools/perf/perf.c:556
> > > > >       #15 0x7f340ac33d67 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
> > > > >   ...
> > > > >
> > > > >   $ perf report -H --stdio 2>&1 | grep -c '^Indirect leak'
> > > > >   93
> > > > >
> > > > > I found that hist_entry__delete() missed to release child entries in the
> > > > > hierarchy tree (hroot_{in,out}).  It needs to iterate the child entries
> > > > > and call hist_entry__delete() recursively.
> > > > >
> > > > > After this change:
> > > > >
> > > > >   $ perf report -H --stdio 2>&1 | grep -c '^Indirect leak'
> > > > >   0
> > > > >
> > > > > Reported-by: Ian Rogers <irogers@google.com>
> > > > > Signed-off-by: Namhyung Kim <namhyung@kernel.org>
> > > > > ---
> > > > >  tools/perf/util/hist.c | 9 +++++++++
> > > > >  1 file changed, 9 insertions(+)
> > > > >
> > > > > diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c
> > > > > index fbf131aeae7ffe9b..bbc6a299b5106c3b 100644
> > > > > --- a/tools/perf/util/hist.c
> > > > > +++ b/tools/perf/util/hist.c
> > > > > @@ -1385,6 +1385,15 @@ void hist_entry__delete(struct hist_entry *he)
> > > > >  {
> > > > >         struct hist_entry_ops *ops = he->ops;
> > > > >
> > > > > +       while (!RB_EMPTY_ROOT(&he->hroot_out.rb_root)) {
> > > > > +               struct rb_node *node = rb_first(&he->hroot_out.rb_root);
> > > > > +               struct hist_entry *child = rb_entry(node, struct hist_entry, rb_node);
> > > > > +
> > > > > +               rb_erase_init(node, &he->hroot_out.rb_root);
> > > > > +
> > > > > +               hist_entry__delete(child);
> > > > > +       }
> > > >
> > > > Thanks for the fix! A nit, iterating the rbtree of N nodes and calling
> > > > erase on the first entry, an O(log N) operation, means this is a O(N *
> > > > log N). rbtree.h has rbtree_postorder_for_each_entry_safe:
> > > > https://web.git.kernel.org/pub/scm/linux/kernel/git/perf/perf-tools-next.git/tree/tools/include/linux/rbtree.h?h=perf-tools-next#n81
> > > > ```
> > > >  * rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of
> > > >  * given type allowing the backing memory of @pos to be invalidated
> > > > ```
> > > > which is O(N). I think this code would be better something like:
> > > > ```
> > > > struct hist_entry *pos, *tmp;
> > > > rbtree_postorder_for_each_entry_safe(pos, tmp, he->hroot_out.rb_root, rb_node)
> > > >         hist_entry__delete(pos);
> > > > ```
> > >
> > > Thanks for your review!  I was wondering if there's something like this.
> > > Will update with that.
> >
> > I found that the following comments:
> >
> >  * Note, however, that it cannot handle other modifications that re-order the
> >  * rbtree it is iterating over. This includes calling rb_erase() on @pos, as
> >  * rb_erase() may rebalance the tree, causing us to miss some nodes.
> >
> > So I cannot use this here.
> 
> I thought the tree is no longer in use after the hist_entry__delete,
> so you don't need to maintain the child/parent pointers as everything
> is going to get freed. Here is what I think is a similar use:
> https://web.git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/kernel/trace/trace_stat.c#n51

Oh, I see.  So it should not call rb_erase().  Will check again.

Thanks,
Namhyung

Re: [PATCH 2/2] perf report: Fix memory leaks in the hierarchy mode

[Namhyung Kim]

On Thu, Mar 06, 2025 at 09:19:09PM -0800, Namhyung Kim wrote:
> On Thu, Mar 06, 2025 at 08:50:46PM -0800, Ian Rogers wrote:
> > On Thu, Mar 6, 2025 at 6:01 PM Namhyung Kim <namhyung@kernel.org> wrote:
> > >
> > > On Thu, Mar 06, 2025 at 09:07:00AM -0800, Namhyung Kim wrote:
> > > > Hi Ian,
> > > >
> > > > On Thu, Mar 06, 2025 at 08:55:05AM -0800, Ian Rogers wrote:
> > > > > On Wed, Mar 5, 2025 at 11:51 PM Namhyung Kim <namhyung@kernel.org> wrote:
> > > > > >
> > > > > > Ian told me that there are many memory leaks in the hierarchy mode.  I
> > > > > > can easily reproduce it with the follwing command.
> > > > > >
> > > > > >   $ make DEBUG=1 EXTRA_CFLAGS=-fsanitize=leak
> > > > > >
> > > > > >   $ perf record --latency -g -- ./perf test -w thloop
> > > > > >
> > > > > >   $ perf report -H --stdio
> > > > > >   ...
> > > > > >   Indirect leak of 168 byte(s) in 21 object(s) allocated from:
> > > > > >       #0 0x7f3414c16c65 in malloc ../../../../src/libsanitizer/lsan/lsan_interceptors.cpp:75
> > > > > >       #1 0x55ed3602346e in map__get util/map.h:189
> > > > > >       #2 0x55ed36024cc4 in hist_entry__init util/hist.c:476
> > > > > >       #3 0x55ed36025208 in hist_entry__new util/hist.c:588
> > > > > >       #4 0x55ed36027c05 in hierarchy_insert_entry util/hist.c:1587
> > > > > >       #5 0x55ed36027e2e in hists__hierarchy_insert_entry util/hist.c:1638
> > > > > >       #6 0x55ed36027fa4 in hists__collapse_insert_entry util/hist.c:1685
> > > > > >       #7 0x55ed360283e8 in hists__collapse_resort util/hist.c:1776
> > > > > >       #8 0x55ed35de0323 in report__collapse_hists /home/namhyung/project/linux/tools/perf/builtin-report.c:735
> > > > > >       #9 0x55ed35de15b4 in __cmd_report /home/namhyung/project/linux/tools/perf/builtin-report.c:1119
> > > > > >       #10 0x55ed35de43dc in cmd_report /home/namhyung/project/linux/tools/perf/builtin-report.c:1867
> > > > > >       #11 0x55ed35e66767 in run_builtin /home/namhyung/project/linux/tools/perf/perf.c:351
> > > > > >       #12 0x55ed35e66a0e in handle_internal_command /home/namhyung/project/linux/tools/perf/perf.c:404
> > > > > >       #13 0x55ed35e66b67 in run_argv /home/namhyung/project/linux/tools/perf/perf.c:448
> > > > > >       #14 0x55ed35e66eb0 in main /home/namhyung/project/linux/tools/perf/perf.c:556
> > > > > >       #15 0x7f340ac33d67 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
> > > > > >   ...
> > > > > >
> > > > > >   $ perf report -H --stdio 2>&1 | grep -c '^Indirect leak'
> > > > > >   93
> > > > > >
> > > > > > I found that hist_entry__delete() missed to release child entries in the
> > > > > > hierarchy tree (hroot_{in,out}).  It needs to iterate the child entries
> > > > > > and call hist_entry__delete() recursively.
> > > > > >
> > > > > > After this change:
> > > > > >
> > > > > >   $ perf report -H --stdio 2>&1 | grep -c '^Indirect leak'
> > > > > >   0
> > > > > >
> > > > > > Reported-by: Ian Rogers <irogers@google.com>
> > > > > > Signed-off-by: Namhyung Kim <namhyung@kernel.org>
> > > > > > ---
> > > > > >  tools/perf/util/hist.c | 9 +++++++++
> > > > > >  1 file changed, 9 insertions(+)
> > > > > >
> > > > > > diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c
> > > > > > index fbf131aeae7ffe9b..bbc6a299b5106c3b 100644
> > > > > > --- a/tools/perf/util/hist.c
> > > > > > +++ b/tools/perf/util/hist.c
> > > > > > @@ -1385,6 +1385,15 @@ void hist_entry__delete(struct hist_entry *he)
> > > > > >  {
> > > > > >         struct hist_entry_ops *ops = he->ops;
> > > > > >
> > > > > > +       while (!RB_EMPTY_ROOT(&he->hroot_out.rb_root)) {
> > > > > > +               struct rb_node *node = rb_first(&he->hroot_out.rb_root);
> > > > > > +               struct hist_entry *child = rb_entry(node, struct hist_entry, rb_node);
> > > > > > +
> > > > > > +               rb_erase_init(node, &he->hroot_out.rb_root);
> > > > > > +
> > > > > > +               hist_entry__delete(child);
> > > > > > +       }
> > > > >
> > > > > Thanks for the fix! A nit, iterating the rbtree of N nodes and calling
> > > > > erase on the first entry, an O(log N) operation, means this is a O(N *
> > > > > log N). rbtree.h has rbtree_postorder_for_each_entry_safe:
> > > > > https://web.git.kernel.org/pub/scm/linux/kernel/git/perf/perf-tools-next.git/tree/tools/include/linux/rbtree.h?h=perf-tools-next#n81
> > > > > ```
> > > > >  * rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of
> > > > >  * given type allowing the backing memory of @pos to be invalidated
> > > > > ```
> > > > > which is O(N). I think this code would be better something like:
> > > > > ```
> > > > > struct hist_entry *pos, *tmp;
> > > > > rbtree_postorder_for_each_entry_safe(pos, tmp, he->hroot_out.rb_root, rb_node)
> > > > >         hist_entry__delete(pos);
> > > > > ```
> > > >
> > > > Thanks for your review!  I was wondering if there's something like this.
> > > > Will update with that.
> > >
> > > I found that the following comments:
> > >
> > >  * Note, however, that it cannot handle other modifications that re-order the
> > >  * rbtree it is iterating over. This includes calling rb_erase() on @pos, as
> > >  * rb_erase() may rebalance the tree, causing us to miss some nodes.
> > >
> > > So I cannot use this here.
> > 
> > I thought the tree is no longer in use after the hist_entry__delete,
> > so you don't need to maintain the child/parent pointers as everything
> > is going to get freed. Here is what I think is a similar use:
> > https://web.git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/kernel/trace/trace_stat.c#n51
> 
> Oh, I see.  So it should not call rb_erase().  Will check again.

It works!  Will send v2 soon.

Thanks,
Namhyung