HomeFreeBSD

Fix O(n^2) behavior in sysctl

Description

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

Details

Provenance
asomersAuthored on Sep 7 2022, 2:12 PM
Reviewer
mjg
Differential Revision
D36500: Fix O(n^2) behavior in sysctl
Parents
rGcee4fc7cada8: cxgbe: Use secq(9) to manage the timestamp generations.
Branches
Unknown
Tags
Unknown