perf dsos: Switch backing storage to array from rbtree/list

DSOs were held on a list for fast iteration and in an rbtree for fast
finds.

Switch to using a lazily sorted array where iteration is just iterating
through the array and binary searches are the same complexity as
searching the rbtree.

The find may need to sort the array first which does increase the
complexity, but add operations have lower complexity and overall the
complexity should remain about the same.

The set name operations on the dso just records that the array is no
longer sorted, avoiding complexity in rebalancing the rbtree.

Tighter locking discipline is enforced to avoid the array being resorted
while long and short names or ids are changed.

The array is smaller in size, replacing 6 pointers with 2, and so even
with extra allocated space in the array, the array may be 50%
unoccupied, the memory saving should be at least 2x.

Committer testing:

On a previous version of this patchset we were getting a lot of warnings
about deleting a DSO still on a list, now it is ok:

  root@x1:~# perf probe -l
  root@x1:~# perf probe finish_task_switch
  Added new event:
    probe:finish_task_switch (on finish_task_switch)

  You can now use it in all perf tools, such as:

  	perf record -e probe:finish_task_switch -aR sleep 1

  root@x1:~# perf probe -l
    probe:finish_task_switch (on finish_task_switch@kernel/sched/core.c)
  root@x1:~# perf trace -e probe:finish_task_switch/max-stack=8/ --max-events=1
       0.000 migration/0/19 probe:finish_task_switch(__probe_ip: -1894408688)
                                         finish_task_switch.isra.0 ([kernel.kallsyms])
                                         __schedule ([kernel.kallsyms])
                                         schedule ([kernel.kallsyms])
                                         smpboot_thread_fn ([kernel.kallsyms])
                                         kthread ([kernel.kallsyms])
                                         ret_from_fork ([kernel.kallsyms])
                                         ret_from_fork_asm ([kernel.kallsyms])
  root@x1:~#
  root@x1:~# perf probe -d probe:*
  Removed event: probe:finish_task_switch
  root@x1:~# perf probe -l
  root@x1:~#

I also ran the full 'perf test' suite after applying this one, no
regressions.

Signed-off-by: Ian Rogers <[email protected]>
Tested-by: Arnaldo Carvalho de Melo <[email protected]>
Cc: Adrian Hunter <[email protected]>
Cc: Ahelenia Ziemiańska <[email protected]>
Cc: Alexander Shishkin <[email protected]>
Cc: Andi Kleen <[email protected]>
Cc: Athira Rajeev <[email protected]>
Cc: Ben Gainey <[email protected]>
Cc: Changbin Du <[email protected]>
Cc: Chengen Du <[email protected]>
Cc: Colin Ian King <[email protected]>
Cc: Dima Kogan <[email protected]>
Cc: Ilkka Koskinen <[email protected]>
Cc: Ingo Molnar <[email protected]>
Cc: James Clark <[email protected]>
Cc: Jiri Olsa <[email protected]>
Cc: K Prateek Nayak <[email protected]>
Cc: Kan Liang <[email protected]>
Cc: Leo Yan <[email protected]>
Cc: Li Dong <[email protected]>
Cc: Mark Rutland <[email protected]>
Cc: Masami Hiramatsu <[email protected]>
Cc: Namhyung Kim <[email protected]>
Cc: Paran Lee <[email protected]>
Cc: Peter Zijlstra <[email protected]>
Cc: Song Liu <[email protected]>
Cc: Sun Haiyong <[email protected]>
Cc: Thomas Richter <[email protected]>
Cc: Tiezhu Yang <[email protected]>
Cc: Yanteng Si <[email protected]>
Cc: zhaimingbing <[email protected]>
Link: https://lore.kernel.org/r/[email protected]
Signed-off-by: Arnaldo Carvalho de Melo <[email protected]>

0 files changed, 0 insertions, 0 deletions