Date: Sat, 2 Nov 2024 20:39:32 GMT From: Olivier Certner <olce@FreeBSD.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org Subject: git: 6d2efbb34fdb - main - cred: crsetgroups(): Improve and factor out groups normalization Message-ID: <202411022039.4A2KdW33046380@gitrepo.freebsd.org>
next in thread | raw e-mail | index | archive | help
The branch main has been updated by olce: URL: https://cgit.FreeBSD.org/src/commit/?id=6d2efbb34fdb59facbe6d83374ef4ab69d395866 commit 6d2efbb34fdb59facbe6d83374ef4ab69d395866 Author: Olivier Certner <olce@FreeBSD.org> AuthorDate: 2024-10-02 12:40:27 +0000 Commit: Olivier Certner <olce@FreeBSD.org> CommitDate: 2024-11-02 20:37:41 +0000 cred: crsetgroups(): Improve and factor out groups normalization The groups array has been sorted (not including the first element, which is always the effective GID) to enable performing a binary search for determining if some group is part of the supplementary groups set. Factor out this sorting operation into an internal normalization function (groups_normalize()), adding to it the removal of duplicates after the sort. Separating groups normalization code allows to perform it in advance, and in particular before calling MAC hooks which need the groups array to be sorted to perform better. This also enables sorting input arrays ahead of acquiring the process lock (which is not necessary for this operation). kern_setgroups() has been changed accordingly, so MAC modules implementing the mac_cred_check_setgroups() hook now can assume a normalized groups array (and also that it has at least one element, as if kern_setgroups() is passed no groups, the hook is called with an array of one element being the current effective GID, as this is effectively the effect of such a call to kern_setgroups()). Further commits introducing the setcred() system call and associated MAC hooks will also guarantee a normalized groups array to MAC modules implementing these hooks. Rename crsetgroups_locked() into crsetgroups_internal(), as it is no more "locked" than crsetgroups() itself. However, it can be called under any lock (as needed), whereas the second may sleep to allocate memory. Update their herald comments to make that explicit. In passing, using qsort() instead of the old open-coded insertion sort (in crsetgroups_locked()) fixes the performance concern about the latter when using a large number of groups. Also, our qsort() falls back to insertion sort for small arrays and in case the array is likely to be mostly sorted, so this shouldn't cause concerns for the small number of groups common case. While here, add assertions in inner modification routines to check that the passed credentials object has a reference count of exactly 1 (in particular, it must not be shared). Remove a redundant one from some outer routine. Reviewed by: mhorne Approved by: markj (mentor) MFC after: 3 days Differential Revision: https://reviews.freebsd.org/D46914 --- sys/kern/kern_prot.c | 168 ++++++++++++++++++++++++++++++++++++++------------ sys/sys/syscallsubr.h | 2 +- sys/sys/ucred.h | 2 +- 3 files changed, 131 insertions(+), 41 deletions(-) diff --git a/sys/kern/kern_prot.c b/sys/kern/kern_prot.c index 67e4428b039e..d87d008e0bc2 100644 --- a/sys/kern/kern_prot.c +++ b/sys/kern/kern_prot.c @@ -89,8 +89,22 @@ SYSCTL_NODE(_security, OID_AUTO, bsd, CTLFLAG_RW | CTLFLAG_MPSAFE, 0, "BSD security policy"); static void crfree_final(struct ucred *cr); -static void crsetgroups_locked(struct ucred *cr, int ngrp, - gid_t *groups); + +static inline void +groups_check_positive_len(int ngrp) +{ + MPASS2(ngrp >= 0, "negative number of groups"); + MPASS2(ngrp != 0, "at least one group expected (effective GID)"); +} +static inline void +groups_check_max_len(int ngrp) +{ + MPASS2(ngrp <= ngroups_max + 1, "too many groups"); +} + +static void groups_normalize(int *ngrp, gid_t *groups); +static void crsetgroups_internal(struct ucred *cr, int ngrp, + const gid_t *groups); static int cr_canseeotheruids(struct ucred *u1, struct ucred *u2); static int cr_canseeothergids(struct ucred *u1, struct ucred *u2); @@ -835,9 +849,9 @@ sys_setgroups(struct thread *td, struct setgroups_args *uap) error = copyin(uap->gidset, groups, gidsetsize * sizeof(gid_t)); if (error == 0) - error = kern_setgroups(td, gidsetsize, groups); + error = kern_setgroups(td, &gidsetsize, groups); - if (gidsetsize > CRED_SMALLGROUPS_NB) + if (groups != smallgroups) free(groups, M_TEMP); return (error); } @@ -851,25 +865,38 @@ gidp_cmp(const void *p1, const void *p2) return ((g1 > g2) - (g1 < g2)); } +/* + * CAUTION: This function normalizes 'groups', possibly also changing the value + * of '*ngrpp' as a consequence. + */ int -kern_setgroups(struct thread *td, int ngrp, gid_t *groups) +kern_setgroups(struct thread *td, int *ngrpp, gid_t *groups) { struct proc *p = td->td_proc; struct ucred *newcred, *oldcred; - int error; + int ngrp, error; + ngrp = *ngrpp; /* Sanity check size. */ if (ngrp < 0 || ngrp > ngroups_max + 1) return (EINVAL); AUDIT_ARG_GROUPSET(groups, ngrp); + if (ngrp != 0) { + /* We allow and treat 0 specially below. */ + groups_normalize(ngrpp, groups); + ngrp = *ngrpp; + } newcred = crget(); crextend(newcred, ngrp); PROC_LOCK(p); oldcred = crcopysafe(p, newcred); #ifdef MAC - error = mac_cred_check_setgroups(oldcred, ngrp, groups); + error = ngrp == 0 ? + /* If 'ngrp' is 0, we'll keep just the current effective GID. */ + mac_cred_check_setgroups(oldcred, 1, oldcred->cr_groups) : + mac_cred_check_setgroups(oldcred, ngrp, groups); if (error) goto fail; #endif @@ -886,9 +913,9 @@ kern_setgroups(struct thread *td, int ngrp, gid_t *groups) * when running non-BSD software if we do not do the same. */ newcred->cr_ngroups = 1; - } else { - crsetgroups_locked(newcred, ngrp, groups); - } + } else + crsetgroups_internal(newcred, ngrp, groups); + setsugid(p); proc_set_cred(p, newcred); PROC_UNLOCK(p); @@ -1298,6 +1325,32 @@ sys___setugid(struct thread *td, struct __setugid_args *uap) #endif /* REGRESSION */ } +#ifdef INVARIANTS +static void +groups_check_normalized(int ngrp, const gid_t *groups) +{ + gid_t prev_g; + + groups_check_positive_len(ngrp); + groups_check_max_len(ngrp); + + if (ngrp == 1) + return; + + prev_g = groups[1]; + for (int i = 2; i < ngrp; ++i) { + const gid_t g = groups[i]; + + if (prev_g >= g) + panic("%s: groups[%d] (%u) >= groups[%d] (%u)", + __func__, i - 1, prev_g, i, g); + prev_g = g; + } +} +#else +#define groups_check_normalized(...) +#endif + /* * Returns whether gid designates a supplementary group in cred. */ @@ -2158,7 +2211,6 @@ void crcopy(struct ucred *dest, struct ucred *src) { - KASSERT(dest->cr_ref == 1, ("crcopy of shared ucred")); bcopy(&src->cr_startcopy, &dest->cr_startcopy, (unsigned)((caddr_t)&src->cr_endcopy - (caddr_t)&src->cr_startcopy)); @@ -2293,6 +2345,8 @@ crextend(struct ucred *cr, int n) { int cnt; + MPASS2(cr->cr_ref == 1, "'cr_ref' must be 1 (referenced, unshared)"); + /* Truncate? */ if (n <= cr->cr_agroups) return; @@ -2326,52 +2380,88 @@ crextend(struct ucred *cr, int n) } /* - * Copy groups in to a credential, preserving any necessary invariants. - * Currently this includes the sorting of all supplementary gids. - * crextend() must have been called before hand to ensure sufficient - * space is available. + * Normalizes a set of groups to be applied to a 'struct ucred'. + * + * The set of groups is an array that must comprise the effective GID as its + * first element (so its length cannot be 0). + * + * Normalization ensures that elements after the first, which stand for the + * supplementary groups, are sorted in ascending order and do not contain + * duplicates. */ static void -crsetgroups_locked(struct ucred *cr, int ngrp, gid_t *groups) +groups_normalize(int *ngrp, gid_t *groups) { - int i; - int j; - gid_t g; + gid_t prev_g; + int ins_idx; - KASSERT(cr->cr_agroups >= ngrp, ("cr_ngroups is too small")); + groups_check_positive_len(*ngrp); + groups_check_max_len(*ngrp); - bcopy(groups, cr->cr_groups, ngrp * sizeof(gid_t)); - cr->cr_ngroups = ngrp; + if (*ngrp == 1) + return; - /* - * Sort all groups except cr_groups[0] to allow groupmember to - * perform a binary search. - * - * XXX: If large numbers of groups become common this should - * be replaced with shell sort like linux uses or possibly - * heap sort. - */ - for (i = 2; i < ngrp; i++) { - g = cr->cr_groups[i]; - for (j = i-1; j >= 1 && g < cr->cr_groups[j]; j--) - cr->cr_groups[j + 1] = cr->cr_groups[j]; - cr->cr_groups[j + 1] = g; + qsort(groups + 1, *ngrp - 1, sizeof(*groups), gidp_cmp); + + /* Remove duplicates. */ + prev_g = groups[1]; + ins_idx = 2; + for (int i = 2; i < *ngrp; ++i) { + const gid_t g = groups[i]; + + if (g != prev_g) { + if (i != ins_idx) + groups[ins_idx] = g; + ++ins_idx; + prev_g = g; + } } + *ngrp = ins_idx; + + groups_check_normalized(*ngrp, groups); +} + +/* + * Internal function copying groups into a credential. + * + * 'ngrp' must be strictly positive. Either the passed 'groups' array must have + * been normalized in advance (see groups_normalize()), else it must be so + * before the structure is to be used again. + * + * This function is suitable to be used under any lock (it doesn't take any lock + * itself nor sleep, and in particular doesn't allocate memory). crextend() + * must have been called beforehand to ensure sufficient space is available. + * See also crsetgroups(), which handles that. + */ +static void +crsetgroups_internal(struct ucred *cr, int ngrp, const gid_t *groups) +{ + + MPASS2(cr->cr_ref == 1, "'cr_ref' must be 1 (referenced, unshared)"); + MPASS2(cr->cr_agroups >= ngrp, "'cr_agroups' too small"); + groups_check_positive_len(ngrp); + + bcopy(groups, cr->cr_groups, ngrp * sizeof(gid_t)); + cr->cr_ngroups = ngrp; } /* * Copy groups in to a credential after expanding it if required. - * Truncate the list to (ngroups_max + 1) if it is too large. + * + * May sleep in order to allocate memory (except if, e.g., crextend() was called + * before with 'ngrp' or greater). Truncates the list to (ngroups_max + 1) if + * it is too large. Array 'groups' doesn't need to be sorted. 'ngrp' must be + * strictly positive. */ void -crsetgroups(struct ucred *cr, int ngrp, gid_t *groups) +crsetgroups(struct ucred *cr, int ngrp, const gid_t *groups) { if (ngrp > ngroups_max + 1) ngrp = ngroups_max + 1; - crextend(cr, ngrp); - crsetgroups_locked(cr, ngrp, groups); + crsetgroups_internal(cr, ngrp, groups); + groups_normalize(&cr->cr_ngroups, cr->cr_groups); } /* diff --git a/sys/sys/syscallsubr.h b/sys/sys/syscallsubr.h index 6ee7c6d802c4..a7f3d2307df1 100644 --- a/sys/sys/syscallsubr.h +++ b/sys/sys/syscallsubr.h @@ -320,7 +320,7 @@ int kern_select(struct thread *td, int nd, fd_set *fd_in, fd_set *fd_ou, fd_set *fd_ex, struct timeval *tvp, int abi_nfdbits); int kern_sendit(struct thread *td, int s, struct msghdr *mp, int flags, struct mbuf *control, enum uio_seg segflg); -int kern_setgroups(struct thread *td, int ngrp, gid_t *groups); +int kern_setgroups(struct thread *td, int *ngrpp, gid_t *groups); int kern_setitimer(struct thread *, u_int, struct itimerval *, struct itimerval *); int kern_setpriority(struct thread *td, int which, int who, int prio); diff --git a/sys/sys/ucred.h b/sys/sys/ucred.h index 4311a73b73a5..358bb3c5566e 100644 --- a/sys/sys/ucred.h +++ b/sys/sys/ucred.h @@ -162,7 +162,7 @@ struct ucred *crcowget(struct ucred *cr); void crcowfree(struct thread *td); void cru2x(struct ucred *cr, struct xucred *xcr); void cru2xt(struct thread *td, struct xucred *xcr); -void crsetgroups(struct ucred *cr, int n, gid_t *groups); +void crsetgroups(struct ucred *cr, int ngrp, const gid_t *groups); /* * Returns whether gid designates a primary group in cred.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?202411022039.4A2KdW33046380>