Date: Wed, 28 Sep 2022 10:33:38 -0600 From: Alan Somers <asomers@freebsd.org> To: Maxim Sobolev <sobomax@freebsd.org> Cc: src-committers <src-committers@freebsd.org>, dev-commits-src-all@freebsd.org, dev-commits-src-main@freebsd.org Subject: Re: git: d3f96f661050 - main - Fix O(n^2) behavior in sysctl Message-ID: <CAOtMX2hrd2cp5mj_E1OcyDEi7AZOTWaBJ8TcvS1BCBWDm=afQQ@mail.gmail.com> In-Reply-To: <CAH7qZfvgRyva8gry0J1VX2oUGcJ8ncPsavkjHa9GdYYiSu_-DQ@mail.gmail.com> References: <202209270004.28R04K1r086731@gitrepo.freebsd.org> <CAH7qZfvgRyva8gry0J1VX2oUGcJ8ncPsavkjHa9GdYYiSu_-DQ@mail.gmail.com>
next in thread | previous in thread | raw e-mail | index | archive | help
I don't think a different interface would necessarily fix all consistency problems, because there are probably additional consistency problems within ZFS itself. The ZFS stats just weren't designed to provide a consistent view, like "zpool status". But a different interface certainly could be much faster; sysctl is slow. Do you have any good ideas for how to easily create such an alternate interface? On Wed, Sep 28, 2022 at 10:19 AM Maxim Sobolev <sobomax@freebsd.org> wrote: > > This also brings a question as to whether sysctl is the right interface t= o pull this data from the kernel in the first place? From my somewhat ignor= ant look this approach is likely to be poised with all sorts of race condit= ions, such so if configuration changes while you are pulling it out you'd g= et 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 so= mething like that? Then you can iterate over it as much as you need in user= land. > > -Max > > On Tue, Sep 27, 2022, 3:04 AM Alan Somers <asomers@freebsd.org> wrote: >> >> The branch main has been updated by asomers: >> >> URL: https://cgit.FreeBSD.org/src/commit/?id=3Dd3f96f661050e9bd21fe29931= 992a8b9e67ff189 >> >> 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 speedu= p >> 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 >> --- >> sys/compat/linuxkpi/common/include/linux/sysfs.h | 2 +- >> sys/kern/kern_sysctl.c | 149 +++++++++++-----= ------- >> sys/kern/vfs_init.c | 2 +- >> sys/sys/param.h | 2 +- >> sys/sys/sysctl.h | 31 ++++- >> 5 files changed, 99 insertions(+), 87 deletions(-) >> >> diff --git a/sys/compat/linuxkpi/common/include/linux/sysfs.h b/sys/comp= at/linuxkpi/common/include/linux/sysfs.h >> index 0b6b479d9362..881a72e62ed9 100644 >> --- a/sys/compat/linuxkpi/common/include/linux/sysfs.h >> +++ b/sys/compat/linuxkpi/common/include/linux/sysfs.h >> @@ -246,7 +246,7 @@ sysfs_unmerge_group(struct kobject *kobj, const stru= ct attribute_group *grp) >> struct attribute **attr; >> struct sysctl_oid *oidp; >> >> - SLIST_FOREACH(oidp, SYSCTL_CHILDREN(kobj->oidp), oid_link) { >> + RB_FOREACH(oidp, sysctl_oid_list, SYSCTL_CHILDREN(kobj->oidp)) { >> if (strcmp(oidp->oid_name, grp->name) !=3D 0) >> continue; >> for (attr =3D grp->attrs; *attr !=3D NULL; attr++) { >> diff --git a/sys/kern/kern_sysctl.c b/sys/kern/kern_sysctl.c >> index 9bc595f111cc..e1cd6ea4bd61 100644 >> --- a/sys/kern/kern_sysctl.c >> +++ b/sys/kern/kern_sysctl.c >> @@ -84,6 +84,8 @@ static MALLOC_DEFINE(M_SYSCTL, "sysctl", "sysctl inter= nal magic"); >> static MALLOC_DEFINE(M_SYSCTLOID, "sysctloid", "sysctl dynamic oids"); >> static MALLOC_DEFINE(M_SYSCTLTMP, "sysctltmp", "sysctl temp output buff= er"); >> >> +RB_GENERATE(sysctl_oid_list, sysctl_oid, oid_link, cmp_sysctl_oid); >> + >> /* >> * The sysctllock protects the MIB tree. It also protects sysctl >> * contexts used with dynamic sysctls. The sysctl_register_oid() and >> @@ -120,7 +122,7 @@ static struct sx sysctlstringlock; >> static int sysctl_root(SYSCTL_HANDLER_ARGS); >> >> /* Root list */ >> -struct sysctl_oid_list sysctl__children =3D SLIST_HEAD_INITIALIZER(&sys= ctl__children); >> +struct sysctl_oid_list sysctl__children =3D RB_INITIALIZER(&sysctl__chi= ldren); >> >> static char* sysctl_escape_name(const char*); >> static int sysctl_remove_oid_locked(struct sysctl_oid *oidp, int de= l, >> @@ -134,7 +136,7 @@ sysctl_find_oidname(const char *name, struct sysctl_= oid_list *list) >> struct sysctl_oid *oidp; >> >> SYSCTL_ASSERT_LOCKED(); >> - SLIST_FOREACH(oidp, list, oid_link) { >> + RB_FOREACH(oidp, sysctl_oid_list, list) { >> if (strcmp(oidp->oid_name, name) =3D=3D 0) { >> return (oidp); >> } >> @@ -356,11 +358,14 @@ sysctl_search_oid(struct sysctl_oid **nodes, struc= t sysctl_oid *needle) >> indx =3D 0; >> while (indx < CTL_MAXNAME && indx >=3D 0) { >> if (nodes[indx] =3D=3D NULL && indx =3D=3D 0) >> - nodes[indx] =3D SLIST_FIRST(&sysctl__children); >> + nodes[indx] =3D RB_MIN(sysctl_oid_list, >> + &sysctl__children); >> else if (nodes[indx] =3D=3D NULL) >> - nodes[indx] =3D SLIST_FIRST(&nodes[indx - 1]->oi= d_children); >> + nodes[indx] =3D RB_MIN(sysctl_oid_list, >> + &nodes[indx - 1]->oid_children); >> else >> - nodes[indx] =3D SLIST_NEXT(nodes[indx], oid_link= ); >> + nodes[indx] =3D RB_NEXT(sysctl_oid_list, >> + &nodes[indx - 1]->oid_children, nodes[indx])= ; >> >> if (nodes[indx] =3D=3D needle) >> return (indx + 1); >> @@ -425,8 +430,7 @@ void >> sysctl_register_oid(struct sysctl_oid *oidp) >> { >> struct sysctl_oid_list *parent =3D oidp->oid_parent; >> - struct sysctl_oid *p; >> - struct sysctl_oid *q; >> + struct sysctl_oid *p, key; >> int oid_number; >> int timeout =3D 2; >> >> @@ -476,25 +480,21 @@ sysctl_register_oid(struct sysctl_oid *oidp) >> * Insert the OID into the parent's list sorted by OID number. >> */ >> retry: >> - q =3D NULL; >> - SLIST_FOREACH(p, parent, oid_link) { >> - /* check if the current OID number is in use */ >> - if (oid_number =3D=3D p->oid_number) { >> - /* get the next valid OID number */ >> - if (oid_number < CTL_AUTO_START || >> - oid_number =3D=3D 0x7fffffff) { >> - /* wraparound - restart */ >> - oid_number =3D CTL_AUTO_START; >> - /* don't loop forever */ >> - if (!timeout--) >> - panic("sysctl: Out of OID number= s\n"); >> - goto retry; >> - } else { >> - oid_number++; >> - } >> - } else if (oid_number < p->oid_number) >> - break; >> - q =3D p; >> + key.oid_number =3D oid_number; >> + p =3D RB_FIND(sysctl_oid_list, parent, &key); >> + if (p) { >> + /* get the next valid OID number */ >> + if (oid_number < CTL_AUTO_START || >> + oid_number =3D=3D 0x7fffffff) { >> + /* wraparound - restart */ >> + oid_number =3D CTL_AUTO_START; >> + /* don't loop forever */ >> + if (!timeout--) >> + panic("sysctl: Out of OID numbers\n"); >> + goto retry; >> + } else { >> + oid_number++; >> + } >> } >> /* check for non-auto OID number collision */ >> if (oidp->oid_number >=3D 0 && oidp->oid_number < CTL_AUTO_START= && >> @@ -504,10 +504,7 @@ retry: >> } >> /* update the OID number, if any */ >> oidp->oid_number =3D oid_number; >> - if (q !=3D NULL) >> - SLIST_INSERT_AFTER(q, oidp, oid_link); >> - else >> - SLIST_INSERT_HEAD(parent, oidp, oid_link); >> + RB_INSERT(sysctl_oid_list, parent, oidp); >> >> if ((oidp->oid_kind & CTLTYPE) !=3D CTLTYPE_NODE && >> #ifdef VIMAGE >> @@ -556,7 +553,6 @@ sysctl_enable_oid(struct sysctl_oid *oidp) >> void >> sysctl_unregister_oid(struct sysctl_oid *oidp) >> { >> - struct sysctl_oid *p; >> int error; >> >> SYSCTL_ASSERT_WLOCKED(); >> @@ -564,14 +560,8 @@ sysctl_unregister_oid(struct sysctl_oid *oidp) >> error =3D EINVAL; >> } else { >> error =3D ENOENT; >> - SLIST_FOREACH(p, oidp->oid_parent, oid_link) { >> - if (p =3D=3D oidp) { >> - SLIST_REMOVE(oidp->oid_parent, oidp, >> - sysctl_oid, oid_link); >> - error =3D 0; >> - break; >> - } >> - } >> + if (RB_REMOVE(sysctl_oid_list, oidp->oid_parent, oidp)) >> + error =3D 0; >> } >> >> /* >> @@ -732,17 +722,14 @@ int >> sysctl_remove_name(struct sysctl_oid *parent, const char *name, >> int del, int recurse) >> { >> - struct sysctl_oid *p, *tmp; >> + struct sysctl_oid *p; >> int error; >> >> error =3D ENOENT; >> SYSCTL_WLOCK(); >> - SLIST_FOREACH_SAFE(p, SYSCTL_CHILDREN(parent), oid_link, tmp) { >> - if (strcmp(p->oid_name, name) =3D=3D 0) { >> - error =3D sysctl_remove_oid_locked(p, del, recur= se); >> - break; >> - } >> - } >> + p =3D sysctl_find_oidname(name, &parent->oid_children); >> + if (p) >> + error =3D sysctl_remove_oid_locked(p, del, recurse); >> SYSCTL_WUNLOCK(); >> >> return (error); >> @@ -811,14 +798,16 @@ sysctl_remove_oid_locked(struct sysctl_oid *oidp, = int del, int recurse) >> */ >> if ((oidp->oid_kind & CTLTYPE) =3D=3D CTLTYPE_NODE) { >> if (oidp->oid_refcnt =3D=3D 1) { >> - SLIST_FOREACH_SAFE(p, >> - SYSCTL_CHILDREN(oidp), oid_link, tmp) { >> + for(p =3D RB_MIN(sysctl_oid_list, &oidp->oid_chi= ldren); >> + p !=3D NULL; p =3D tmp) { >> if (!recurse) { >> printf("Warning: failed attempt = to " >> "remove oid %s with child %s= \n", >> oidp->oid_name, p->oid_name)= ; >> return (ENOTEMPTY); >> } >> + tmp =3D RB_NEXT(sysctl_oid_list, >> + &oidp->oid_children, p); >> error =3D sysctl_remove_oid_locked(p, de= l, >> recurse); >> if (error) >> @@ -895,7 +884,7 @@ sysctl_add_oid(struct sysctl_ctx_list *clist, struct= sysctl_oid_list *parent, >> } >> oidp =3D malloc(sizeof(struct sysctl_oid), M_SYSCTLOID, M_WAITOK= |M_ZERO); >> oidp->oid_parent =3D parent; >> - SLIST_INIT(&oidp->oid_children); >> + RB_INIT(&oidp->oid_children); >> oidp->oid_number =3D number; >> oidp->oid_refcnt =3D 1; >> oidp->oid_name =3D escaped; >> @@ -1016,7 +1005,7 @@ sysctl_sysctl_debug_dump_node(struct sysctl_oid_li= st *l, int i) >> struct sysctl_oid *oidp; >> >> SYSCTL_ASSERT_LOCKED(); >> - SLIST_FOREACH(oidp, l, oid_link) { >> + RB_FOREACH(oidp, sysctl_oid_list, l) { >> for (k=3D0; k<i; k++) >> printf(" "); >> >> @@ -1081,7 +1070,7 @@ sysctl_sysctl_name(SYSCTL_HANDLER_ARGS) >> int *name =3D (int *) arg1; >> u_int namelen =3D arg2; >> int error; >> - struct sysctl_oid *oid; >> + struct sysctl_oid *oid, key; >> struct sysctl_oid_list *lsp =3D &sysctl__children, *lsp2; >> struct rm_priotracker tracker; >> char buf[10]; >> @@ -1105,10 +1094,9 @@ sysctl_sysctl_name(SYSCTL_HANDLER_ARGS) >> continue; >> } >> lsp2 =3D NULL; >> - SLIST_FOREACH(oid, lsp, oid_link) { >> - if (oid->oid_number !=3D *name) >> - continue; >> - >> + key.oid_number =3D *name; >> + oid =3D RB_FIND(sysctl_oid_list, lsp, &key); >> + if (oid) { >> if (req->oldidx) >> error =3D SYSCTL_OUT(req, ".", 1); >> if (!error) >> @@ -1120,14 +1108,9 @@ sysctl_sysctl_name(SYSCTL_HANDLER_ARGS) >> namelen--; >> name++; >> >> - if ((oid->oid_kind & CTLTYPE) !=3D CTLTYPE_NODE) >> - break; >> - >> - if (oid->oid_handler) >> - break; >> - >> - lsp2 =3D SYSCTL_CHILDREN(oid); >> - break; >> + if ((oid->oid_kind & CTLTYPE) =3D=3D CTLTYPE_NOD= E && >> + !oid->oid_handler) >> + lsp2 =3D SYSCTL_CHILDREN(oid); >> } >> lsp =3D lsp2; >> } >> @@ -1239,13 +1222,25 @@ static bool >> sysctl_sysctl_next_action(struct sysctl_oid_list *lsp, int *name, u_int= namelen, >> int *next, int *len, int level, bool honor_skip) >> { >> - struct sysctl_oid *oidp; >> + struct sysctl_oid_list *next_lsp; >> + struct sysctl_oid *oidp =3D NULL, key; >> bool success =3D false; >> enum sysctl_iter_action action; >> >> SYSCTL_ASSERT_LOCKED(); >> - SLIST_FOREACH(oidp, lsp, oid_link) { >> - action =3D sysctl_sysctl_next_node(oidp, name, namelen, = honor_skip); >> + /* >> + * Start the search at the requested oid. But if not found, the= n scan >> + * through all children. >> + */ >> + if (namelen > 0) { >> + key.oid_number =3D *name; >> + oidp =3D RB_FIND(sysctl_oid_list, lsp, &key); >> + } >> + if (!oidp) >> + oidp =3D RB_MIN(sysctl_oid_list, lsp); >> + for(; oidp !=3D NULL; oidp =3D RB_NEXT(sysctl_oid_list, lsp, oid= p)) { >> + action =3D sysctl_sysctl_next_node(oidp, name, namelen, >> + honor_skip); >> if (action =3D=3D ITER_SIBLINGS) >> continue; >> if (action =3D=3D ITER_FOUND) { >> @@ -1254,13 +1249,13 @@ sysctl_sysctl_next_action(struct sysctl_oid_list= *lsp, int *name, u_int namelen, >> } >> KASSERT((action=3D=3D ITER_CHILDREN), ("ret(%d)!=3DITER_= CHILDREN", action)); >> >> - lsp =3D SYSCTL_CHILDREN(oidp); >> + next_lsp =3D SYSCTL_CHILDREN(oidp); >> if (namelen =3D=3D 0) { >> - success =3D sysctl_sysctl_next_action(lsp, NULL,= 0, >> + success =3D sysctl_sysctl_next_action(next_lsp, = NULL, 0, >> next + 1, len, level + 1, honor_skip); >> } else { >> - success =3D sysctl_sysctl_next_action(lsp, name = + 1, namelen - 1, >> - next + 1, len, level + 1, honor_skip); >> + success =3D sysctl_sysctl_next_action(next_lsp, = name + 1, >> + namelen - 1, next + 1, len, level + 1, honor= _skip); >> if (!success) { >> >> /* >> @@ -1332,13 +1327,12 @@ name2oid(char *name, int *oid, int *len, struct = sysctl_oid **oidpp) >> for (*len =3D 0; *len < CTL_MAXNAME;) { >> p =3D strsep(&name, "."); >> >> - oidp =3D SLIST_FIRST(lsp); >> - for (;; oidp =3D SLIST_NEXT(oidp, oid_link)) { >> - if (oidp =3D=3D NULL) >> - return (ENOENT); >> + RB_FOREACH(oidp, sysctl_oid_list, lsp) { >> if (strcmp(p, oidp->oid_name) =3D=3D 0) >> break; >> } >> + if (oidp =3D=3D NULL) >> + return (ENOENT); >> *oid++ =3D oidp->oid_number; >> (*len)++; >> >> @@ -2162,16 +2156,15 @@ sysctl_find_oid(int *name, u_int namelen, struct= sysctl_oid **noid, >> { >> struct sysctl_oid_list *lsp; >> struct sysctl_oid *oid; >> + struct sysctl_oid key; >> int indx; >> >> SYSCTL_ASSERT_LOCKED(); >> lsp =3D &sysctl__children; >> indx =3D 0; >> while (indx < CTL_MAXNAME) { >> - SLIST_FOREACH(oid, lsp, oid_link) { >> - if (oid->oid_number =3D=3D name[indx]) >> - break; >> - } >> + key.oid_number =3D name[indx]; >> + oid =3D RB_FIND(sysctl_oid_list, lsp, &key); >> if (oid =3D=3D NULL) >> return (ENOENT); >> >> diff --git a/sys/kern/vfs_init.c b/sys/kern/vfs_init.c >> index 6572a8e362c2..6e2e78aaf597 100644 >> --- a/sys/kern/vfs_init.c >> +++ b/sys/kern/vfs_init.c >> @@ -525,7 +525,7 @@ vfs_register(struct vfsconf *vfc) >> * number. >> */ >> sysctl_wlock(); >> - SLIST_FOREACH(oidp, SYSCTL_CHILDREN(&sysctl___vfs), oid_link) { >> + RB_FOREACH(oidp, sysctl_oid_list, SYSCTL_CHILDREN(&sysctl___vfs)= ) { >> if (strcmp(oidp->oid_name, vfc->vfc_name) =3D=3D 0) { >> sysctl_unregister_oid(oidp); >> oidp->oid_number =3D vfc->vfc_typenum; >> diff --git a/sys/sys/param.h b/sys/sys/param.h >> index f875d839d41f..3f5da06ef951 100644 >> --- a/sys/sys/param.h >> +++ b/sys/sys/param.h >> @@ -76,7 +76,7 @@ >> * cannot include sys/param.h and should only be updated here. >> */ >> #undef __FreeBSD_version >> -#define __FreeBSD_version 1400070 >> +#define __FreeBSD_version 1400071 >> >> /* >> * __FreeBSD_kernel__ indicates that this system uses the kernel of Fre= eBSD, >> diff --git a/sys/sys/sysctl.h b/sys/sys/sysctl.h >> index 451d83bbe125..3bd77cf87243 100644 >> --- a/sys/sys/sysctl.h >> +++ b/sys/sys/sysctl.h >> @@ -39,7 +39,8 @@ >> #define _SYS_SYSCTL_H_ >> >> #ifdef _KERNEL >> -#include <sys/queue.h> >> +#include <sys/tree.h> >> +#include <sys/systm.h> >> #endif >> >> /* >> @@ -173,20 +174,25 @@ struct sysctl_req { >> int flags; >> }; >> >> -SLIST_HEAD(sysctl_oid_list, sysctl_oid); >> +struct sysctl_oid; >> + >> +/* RB Tree handling */ >> +RB_HEAD(sysctl_oid_list, sysctl_oid); >> >> /* >> * This describes one "oid" in the MIB tree. Potentially more nodes ca= n >> * be hidden behind it, expanded by the handler. >> */ >> struct sysctl_oid { >> - struct sysctl_oid_list oid_children; >> - struct sysctl_oid_list *oid_parent; >> - SLIST_ENTRY(sysctl_oid) oid_link; >> + struct sysctl_oid_list oid_children; >> + struct sysctl_oid_list* oid_parent; >> + RB_ENTRY(sysctl_oid) oid_link; >> + /* Sort key for all siblings, and lookup key for userland */ >> int oid_number; >> u_int oid_kind; >> void *oid_arg1; >> intmax_t oid_arg2; >> + /* Must be unique amongst all siblings. */ >> const char *oid_name; >> int (*oid_handler)(SYSCTL_HANDLER_ARGS); >> const char *oid_fmt; >> @@ -196,6 +202,19 @@ struct sysctl_oid { >> const char *oid_label; >> }; >> >> +static inline int >> +cmp_sysctl_oid(struct sysctl_oid *a, struct sysctl_oid *b) >> +{ >> + if (a->oid_number > b->oid_number) >> + return (1); >> + else if (a->oid_number < b->oid_number) >> + return (-1); >> + else >> + return (0); >> +} >> + >> +RB_PROTOTYPE(sysctl_oid_list, sysctl_oid, oid_link, cmp_sysctl_oid); >> + >> #define SYSCTL_IN(r, p, l) (r->newfunc)(r, p, l) >> #define SYSCTL_OUT(r, p, l) (r->oldfunc)(r, p, l) >> #define SYSCTL_OUT_STR(r, p) (r->oldfunc)(r, p, strlen(p) + 1= ) >> @@ -275,7 +294,7 @@ TAILQ_HEAD(sysctl_ctx_list, sysctl_ctx_entry); >> #define SYSCTL_OID_RAW(id, parent_child_head, nbr, name, kind, a= 1, a2, handler, fmt, descr, label) \ >> struct sysctl_oid id =3D { = \ >> .oid_parent =3D (parent_child_head), = \ >> - .oid_children =3D SLIST_HEAD_INITIALIZER(&id.oid_childre= n), \ >> + .oid_children =3D RB_INITIALIZER(&id.oid_children), \ >> .oid_number =3D (nbr), = \ >> .oid_kind =3D (kind), = \ >> .oid_arg1 =3D (a1), = \ >>
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CAOtMX2hrd2cp5mj_E1OcyDEi7AZOTWaBJ8TcvS1BCBWDm=afQQ>