Re: git: d3f96f661050 - main - Fix O(n^2) behavior in sysctl
- In reply to: Maxim Sobolev : "Re: git: d3f96f661050 - main - Fix O(n^2) behavior in sysctl"
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Wed, 28 Sep 2022 16:34:57 UTC
On 28/09/2022 19:18, Maxim Sobolev wrote: > This also brings a question as to whether sysctl is the right interface to pull > this data from the kernel in the first place? From my somewhat ignorant look > this approach is likely to be poised with all sorts of race conditions, such so > if configuration changes while you are pulling it out you'd get some > inconsistent view that is not here not there. Wouldn't it be easier to use some > other mechanism to pull configuration of all 1,000 datasets as one blob in one > or few system calls? Like read(2) from /dev/zfsstats or something like that? > Then you can iterate over it as much as you need in userland. I've learnt that we do not talk about the "sensors framework" in a good company, but one of the reasons it got killed was the "inadequate" sysctl mechanism for querying [allegedly massive amounts of] data. > On Tue, Sep 27, 2022, 3:04 AM Alan Somers <asomers@freebsd.org > <mailto:asomers@freebsd.org>> wrote: > > The branch main has been updated by asomers: > > URL: > https://cgit.FreeBSD.org/src/commit/?id=d3f96f661050e9bd21fe29931992a8b9e67ff189 <https://cgit.FreeBSD.org/src/commit/?id=d3f96f661050e9bd21fe29931992a8b9e67ff189> > > commit d3f96f661050e9bd21fe29931992a8b9e67ff189 > Author: Alan Somers <asomers@FreeBSD.org> > AuthorDate: 2022-09-07 14:12:49 +0000 > Commit: Alan Somers <asomers@FreeBSD.org> > CommitDate: 2022-09-27 00:03:34 +0000 > > Fix O(n^2) behavior in sysctl > > Sysctl OIDs were internally stored in linked lists, triggering O(n^2) > behavior when userland iterates over many of them. The slowdown is > noticeable for MIBs that have > 100 children (for example, vm.uma). But > it's unignorable for kstat.zfs when a pool has > 1000 datasets. > > Convert the linked lists into RB trees. This produces a ~25x speedup > for listing kstat.zfs with 4100 datasets, and no measurable penalty for > small dataset counts. > > Bump __FreeBSD_version for the KPI change. > > Sponsored by: Axcient > Reviewed by: mjg > Differential Revision: https://reviews.freebsd.org/D36500 > <https://reviews.freebsd.org/D36500> \ -- Andriy Gapon