linux-kernel - Re: [PATCH v5 1/7] perf dsos: Switch backing storage to array from rbtree/list

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives
Hash Suite for Android: free password hash cracker in your pocket
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <CAP-5=fXE6-atL+FdCdD529eqyveWUqgR6QbJgzvGy=5xR_TBRg@mail.gmail.com>
Date: Sat, 4 May 2024 11:14:52 -0700
From: Ian Rogers <irogers@...gle.com>
To: Arnaldo Carvalho de Melo <acme@...nel.org>
Cc: Peter Zijlstra <peterz@...radead.org>, Ingo Molnar <mingo@...hat.com>, 
	Namhyung Kim <namhyung@...nel.org>, Mark Rutland <mark.rutland@....com>, 
	Alexander Shishkin <alexander.shishkin@...ux.intel.com>, Jiri Olsa <jolsa@...nel.org>, 
	Adrian Hunter <adrian.hunter@...el.com>, Kan Liang <kan.liang@...ux.intel.com>, 
	James Clark <james.clark@....com>, Athira Rajeev <atrajeev@...ux.vnet.ibm.com>, 
	Colin Ian King <colin.i.king@...il.com>, nabijaczleweli@...ijaczleweli.xyz, 
	Leo Yan <leo.yan@...ux.dev>, Song Liu <song@...nel.org>, 
	Ilkka Koskinen <ilkka@...amperecomputing.com>, Ben Gainey <ben.gainey@....com>, 
	K Prateek Nayak <kprateek.nayak@....com>, Yanteng Si <siyanteng@...ngson.cn>, 
	Sun Haiyong <sunhaiyong@...ngson.cn>, Changbin Du <changbin.du@...wei.com>, 
	Andi Kleen <ak@...ux.intel.com>, Thomas Richter <tmricht@...ux.ibm.com>, 
	Masami Hiramatsu <mhiramat@...nel.org>, Dima Kogan <dima@...retsauce.net>, 
	zhaimingbing <zhaimingbing@...s.chinamobile.com>, Paran Lee <p4ranlee@...il.com>, 
	Li Dong <lidong@...o.com>, Tiezhu Yang <yangtiezhu@...ngson.cn>, 
	Yang Jihong <yangjihong1@...wei.com>, Chengen Du <chengen.du@...onical.com>, 
	linux-perf-users@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH v5 1/7] perf dsos: Switch backing storage to array from rbtree/list

On Fri, May 3, 2024 at 1:21 PM Arnaldo Carvalho de Melo <acme@...nel.org> wrote:
>
> On Mon, Apr 29, 2024 at 11:46:08AM -0700, Ian Rogers wrote:
> > 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.
>
> With just this first one applied:
>
> ⬢[acme@...lbox perf-tools-next]$ git log --oneline -10
> 325557715f1d8593 (HEAD) perf dsos: Switch backing storage to array from rbtree/list
> 7b6dd7a923281a7c perf pmu: Assume sysfs events are always the same case
> 6debc5aa326fa2ee perf test pmu: Test all sysfs PMU event names are the same case
> 18eb2ca8c18f0612 perf test pmu: Add an eagerly loaded event test
> aa1551f299ba414c perf test pmu: Refactor format test and exposed test APIs
> 785623ee855e893d perf Document: Sysfs event names must be lower or upper case
> 97c48ea8ff1cd70f perf test pmu-events: Make it clearer that pmu-events tests JSON events
> 3cdd98b42d212160 (x1/perf-tools-next) perf maps: Remove check_invariants() from maps__lock()
> e3123079b906dc2e perf cs-etm: Improve version detection and error reporting
> bc5e0e1b93565e37 perf cs-etm: Remove repeated fetches of the ETM PMU
> ⬢[acme@...lbox perf-tools-next]$
>
> root@...ber:~# perf -v
> perf version 6.9.rc5.g325557715f1d
> root@...ber:~# perf probe -l
> DSO [kernel.kallsyms] is still in rbtree when being deleted!
> DSO /lib/modules/6.8.7-200.fc39.x86_64/kernel/drivers/hid/hid-sensor-hub.ko.xz is still in rbtree when being deleted!
> DSO /lib/modules/6.8.7-200.fc39.x86_64/kernel/drivers/hid/uhid.ko.xz is still in rbtree when being deleted!
> DSO /lib/modules/6.8.7-200.fc39.x86_64/kernel/drivers/net/tun.ko.xz is still in rbtree when being deleted!
> DSO /lib/modules/6.8.7-200.fc39.x86_64/kernel/fs/overlayfs/overlay.ko.xz is still in rbtree when being deleted!
> DSO /lib/modules/6.8.7-200.fc39.x86_64/kernel/net/bluetooth/rfcomm/rfcommko.xz is still in rbtree when being deleted!
> DSO /lib/modules/6.8.7-200.fc39.x86_64/kernel/drivers/input/misc/uinput.ko.xz is still in rbtree when being deleted!
> DSO /lib/modules/6.8.7-200.fc39.x86_64/kernel/sound/core/seq/snd-seq-dummy.ko.xz is still in rbtree when being deleted!
> <SNIP a lot of other modules, probably all of them>


Right, we don't have a test on this and this motivates the addition of
reference count checking on DSO in the later patches. With the series
applied, fixing the rebase issue, I see:

$ git log --oneline
eabe5dd91331 (HEAD) perf dso: Use container_of to avoid a pointer in dso_data
fd47ec98a05c perf dso: Reference counting related fixes
962af2d2b092 perf dso: Add reference count checking and accessor functions
48664a9a6ca4 perf dsos: Switch hand code to bsearch
ae7a9854dabd perf dsos: Remove __dsos__findnew_link_by_longname_id
e616a6b3739d perf dsos: Remove __dsos__addnew
e789368716dd perf dsos: Switch backing storage to array from rbtree/list
7b6dd7a92328 (ptn/tmp.perf-tools-next, ptn/perf-tools-next) perf pmu:
Assume sysfs events are always the same case
..
$ sudo /tmp/perf/perf -v
perf version 6.9.rc5.geabe5dd91331
$ sudo /tmp/perf/perf probe -l
$

I'll see if I can find a fix to backport before sending a new series
to work around the 2 line rebase conflict.

Thanks,
Ian

>
> Then with:
>
> 65e1e704f37916a0 (HEAD -> perf-tools-next) perf dsos: Switch hand code to bsearch
> 64377d6b7d5f9a71 perf dsos: Remove __dsos__findnew_link_by_longname_id
> 8e773b8be95aff66 perf dsos: Remove __dsos__addnew
> b1d064fc9b912ece perf dsos: Switch backing storage to array from rbtree/list
>
> applied it continues like that, the next patch in line isn't applying.
>
> I'll push what I have to tmp.perf-tools-next.
>
> - Arnaldo