diff --git a/sys/compat/linuxkpi/common/include/linux/sysfs.h b/sys/compat/linuxkpi/common/include/linux/sysfs.h --- a/sys/compat/linuxkpi/common/include/linux/sysfs.h +++ b/sys/compat/linuxkpi/common/include/linux/sysfs.h @@ -246,7 +246,7 @@ 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) != 0) continue; for (attr = grp->attrs; *attr != NULL; attr++) { diff --git a/sys/kern/kern_sysctl.c b/sys/kern/kern_sysctl.c --- a/sys/kern/kern_sysctl.c +++ b/sys/kern/kern_sysctl.c @@ -84,6 +84,8 @@ static MALLOC_DEFINE(M_SYSCTLOID, "sysctloid", "sysctl dynamic oids"); static MALLOC_DEFINE(M_SYSCTLTMP, "sysctltmp", "sysctl temp output buffer"); +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 int sysctl_root(SYSCTL_HANDLER_ARGS); /* Root list */ -struct sysctl_oid_list sysctl__children = SLIST_HEAD_INITIALIZER(&sysctl__children); +struct sysctl_oid_list sysctl__children = RB_INITIALIZER(&sysctl__children); static char* sysctl_escape_name(const char*); static int sysctl_remove_oid_locked(struct sysctl_oid *oidp, int del, @@ -134,7 +136,7 @@ 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) == 0) { return (oidp); } @@ -356,11 +358,14 @@ indx = 0; while (indx < CTL_MAXNAME && indx >= 0) { if (nodes[indx] == NULL && indx == 0) - nodes[indx] = SLIST_FIRST(&sysctl__children); + nodes[indx] = RB_MIN(sysctl_oid_list, + &sysctl__children); else if (nodes[indx] == NULL) - nodes[indx] = SLIST_FIRST(&nodes[indx - 1]->oid_children); + nodes[indx] = RB_MIN(sysctl_oid_list, + &nodes[indx - 1]->oid_children); else - nodes[indx] = SLIST_NEXT(nodes[indx], oid_link); + nodes[indx] = RB_NEXT(sysctl_oid_list, + &nodes[indx - 1]->oid_children, nodes[indx]); if (nodes[indx] == needle) return (indx + 1); @@ -425,8 +430,7 @@ sysctl_register_oid(struct sysctl_oid *oidp) { struct sysctl_oid_list *parent = oidp->oid_parent; - struct sysctl_oid *p; - struct sysctl_oid *q; + struct sysctl_oid *p, key; int oid_number; int timeout = 2; @@ -476,25 +480,21 @@ * Insert the OID into the parent's list sorted by OID number. */ retry: - q = NULL; - SLIST_FOREACH(p, parent, oid_link) { - /* check if the current OID number is in use */ - if (oid_number == p->oid_number) { - /* get the next valid OID number */ - if (oid_number < CTL_AUTO_START || - oid_number == 0x7fffffff) { - /* wraparound - restart */ - oid_number = CTL_AUTO_START; - /* don't loop forever */ - if (!timeout--) - panic("sysctl: Out of OID numbers\n"); - goto retry; - } else { - oid_number++; - } - } else if (oid_number < p->oid_number) - break; - q = p; + key.oid_number = oid_number; + p = RB_FIND(sysctl_oid_list, parent, &key); + if (p) { + /* get the next valid OID number */ + if (oid_number < CTL_AUTO_START || + oid_number == 0x7fffffff) { + /* wraparound - restart */ + oid_number = 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 >= 0 && oidp->oid_number < CTL_AUTO_START && @@ -504,10 +504,7 @@ } /* update the OID number, if any */ oidp->oid_number = oid_number; - if (q != 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) != CTLTYPE_NODE && #ifdef VIMAGE @@ -556,7 +553,6 @@ void sysctl_unregister_oid(struct sysctl_oid *oidp) { - struct sysctl_oid *p; int error; SYSCTL_ASSERT_WLOCKED(); @@ -564,14 +560,8 @@ error = EINVAL; } else { error = ENOENT; - SLIST_FOREACH(p, oidp->oid_parent, oid_link) { - if (p == oidp) { - SLIST_REMOVE(oidp->oid_parent, oidp, - sysctl_oid, oid_link); - error = 0; - break; - } - } + if (RB_REMOVE(sysctl_oid_list, oidp->oid_parent, oidp)) + error = 0; } /* @@ -732,17 +722,14 @@ 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 = ENOENT; SYSCTL_WLOCK(); - SLIST_FOREACH_SAFE(p, SYSCTL_CHILDREN(parent), oid_link, tmp) { - if (strcmp(p->oid_name, name) == 0) { - error = sysctl_remove_oid_locked(p, del, recurse); - break; - } - } + p = sysctl_find_oidname(name, &parent->oid_children); + if (p) + error = sysctl_remove_oid_locked(p, del, recurse); SYSCTL_WUNLOCK(); return (error); @@ -811,14 +798,16 @@ */ if ((oidp->oid_kind & CTLTYPE) == CTLTYPE_NODE) { if (oidp->oid_refcnt == 1) { - SLIST_FOREACH_SAFE(p, - SYSCTL_CHILDREN(oidp), oid_link, tmp) { + for(p = RB_MIN(sysctl_oid_list, &oidp->oid_children); + p != NULL; p = tmp) { if (!recurse) { printf("Warning: failed attempt to " "remove oid %s with child %s\n", oidp->oid_name, p->oid_name); return (ENOTEMPTY); } + tmp = RB_NEXT(sysctl_oid_list, + &oidp->oid_children, p); error = sysctl_remove_oid_locked(p, del, recurse); if (error) @@ -895,7 +884,7 @@ } oidp = malloc(sizeof(struct sysctl_oid), M_SYSCTLOID, M_WAITOK|M_ZERO); oidp->oid_parent = parent; - SLIST_INIT(&oidp->oid_children); + RB_INIT(&oidp->oid_children); oidp->oid_number = number; oidp->oid_refcnt = 1; oidp->oid_name = escaped; @@ -1016,7 +1005,7 @@ struct sysctl_oid *oidp; SYSCTL_ASSERT_LOCKED(); - SLIST_FOREACH(oidp, l, oid_link) { + RB_FOREACH(oidp, sysctl_oid_list, l) { for (k=0; koid_number != *name) - continue; - + key.oid_number = *name; + oid = RB_FIND(sysctl_oid_list, lsp, &key); + if (oid) { if (req->oldidx) error = SYSCTL_OUT(req, ".", 1); if (!error) @@ -1120,14 +1108,9 @@ namelen--; name++; - if ((oid->oid_kind & CTLTYPE) != CTLTYPE_NODE) - break; - - if (oid->oid_handler) - break; - - lsp2 = SYSCTL_CHILDREN(oid); - break; + if ((oid->oid_kind & CTLTYPE) == CTLTYPE_NODE && + !oid->oid_handler) + lsp2 = SYSCTL_CHILDREN(oid); } lsp = lsp2; } @@ -1239,13 +1222,25 @@ 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 = NULL, key; bool success = false; enum sysctl_iter_action action; SYSCTL_ASSERT_LOCKED(); - SLIST_FOREACH(oidp, lsp, oid_link) { - action = sysctl_sysctl_next_node(oidp, name, namelen, honor_skip); + /* + * Start the search at the requested oid. But if not found, then scan + * through all children. + */ + if (namelen > 0) { + key.oid_number = *name; + oidp = RB_FIND(sysctl_oid_list, lsp, &key); + } + if (!oidp) + oidp = RB_MIN(sysctl_oid_list, lsp); + for(; oidp != NULL; oidp = RB_NEXT(sysctl_oid_list, lsp, oidp)) { + action = sysctl_sysctl_next_node(oidp, name, namelen, + honor_skip); if (action == ITER_SIBLINGS) continue; if (action == ITER_FOUND) { @@ -1254,13 +1249,13 @@ } KASSERT((action== ITER_CHILDREN), ("ret(%d)!=ITER_CHILDREN", action)); - lsp = SYSCTL_CHILDREN(oidp); + next_lsp = SYSCTL_CHILDREN(oidp); if (namelen == 0) { - success = sysctl_sysctl_next_action(lsp, NULL, 0, + success = sysctl_sysctl_next_action(next_lsp, NULL, 0, next + 1, len, level + 1, honor_skip); } else { - success = sysctl_sysctl_next_action(lsp, name + 1, namelen - 1, - next + 1, len, level + 1, honor_skip); + success = sysctl_sysctl_next_action(next_lsp, name + 1, + namelen - 1, next + 1, len, level + 1, honor_skip); if (!success) { /* @@ -1332,13 +1327,12 @@ for (*len = 0; *len < CTL_MAXNAME;) { p = strsep(&name, "."); - oidp = SLIST_FIRST(lsp); - for (;; oidp = SLIST_NEXT(oidp, oid_link)) { - if (oidp == NULL) - return (ENOENT); + RB_FOREACH(oidp, sysctl_oid_list, lsp) { if (strcmp(p, oidp->oid_name) == 0) break; } + if (oidp == NULL) + return (ENOENT); *oid++ = oidp->oid_number; (*len)++; @@ -2162,16 +2156,15 @@ { struct sysctl_oid_list *lsp; struct sysctl_oid *oid; + struct sysctl_oid key; int indx; SYSCTL_ASSERT_LOCKED(); lsp = &sysctl__children; indx = 0; while (indx < CTL_MAXNAME) { - SLIST_FOREACH(oid, lsp, oid_link) { - if (oid->oid_number == name[indx]) - break; - } + key.oid_number = name[indx]; + oid = RB_FIND(sysctl_oid_list, lsp, &key); if (oid == NULL) return (ENOENT); diff --git a/sys/kern/vfs_init.c b/sys/kern/vfs_init.c --- a/sys/kern/vfs_init.c +++ b/sys/kern/vfs_init.c @@ -525,7 +525,7 @@ * 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) == 0) { sysctl_unregister_oid(oidp); oidp->oid_number = vfc->vfc_typenum; diff --git a/sys/sys/param.h b/sys/sys/param.h --- 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 FreeBSD, diff --git a/sys/sys/sysctl.h b/sys/sys/sysctl.h --- a/sys/sys/sysctl.h +++ b/sys/sys/sysctl.h @@ -39,7 +39,8 @@ #define _SYS_SYSCTL_H_ #ifdef _KERNEL -#include +#include +#include #endif /* @@ -173,20 +174,25 @@ 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 can * 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 @@ 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 @@ #define SYSCTL_OID_RAW(id, parent_child_head, nbr, name, kind, a1, a2, handler, fmt, descr, label) \ struct sysctl_oid id = { \ .oid_parent = (parent_child_head), \ - .oid_children = SLIST_HEAD_INITIALIZER(&id.oid_children), \ + .oid_children = RB_INITIALIZER(&id.oid_children), \ .oid_number = (nbr), \ .oid_kind = (kind), \ .oid_arg1 = (a1), \