Date: Sat, 20 Jun 2009 20:29:21 +0000 (UTC) From: Brooks Davis <brooks@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r194556 - head/sys/kern Message-ID: <200906202029.n5KKTLDx086045@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: brooks Date: Sat Jun 20 20:29:21 2009 New Revision: 194556 URL: http://svn.freebsd.org/changeset/base/194556 Log: Change crsetgroups_locked() (called by crsetgroups()) to sort the supplemental groups using insertion sort. Use this property in groupmember() to let us use a binary search instead of the previous linear search. Modified: head/sys/kern/kern_prot.c Modified: head/sys/kern/kern_prot.c ============================================================================== --- head/sys/kern/kern_prot.c Sat Jun 20 20:22:11 2009 (r194555) +++ head/sys/kern/kern_prot.c Sat Jun 20 20:29:21 2009 (r194556) @@ -86,7 +86,6 @@ static void crextend(struct ucred *cr, i static void crsetgroups_locked(struct ucred *cr, int ngrp, gid_t *groups); - #ifndef _SYS_SYSPROTO_H_ struct getpid_args { int dummy; @@ -1248,13 +1247,30 @@ __setugid(struct thread *td, struct __se int groupmember(gid_t gid, struct ucred *cred) { - register gid_t *gp; - gid_t *egp; + int l; + int h; + int m; + + if (cred->cr_groups[0] == gid) + return(1); + + /* + * If gid was not our primary group, perform a binary search + * of the supplemental groups. This is possible because we + * sort the groups in crsetgroups(). + */ + l = 1; + h = cred->cr_ngroups; + while (l < h) { + m = l + ((h - l) / 2); + if (cred->cr_groups[m] < gid) + l = m + 1; + else + h = m; + } + if ((l < cred->cr_ngroups) && (cred->cr_groups[l] == gid)) + return (1); - egp = &(cred->cr_groups[cred->cr_ngroups]); - for (gp = cred->cr_groups; gp < egp; gp++) - if (*gp == gid) - return (1); return (0); } @@ -1986,18 +2002,37 @@ crextend(struct ucred *cr, int n) } /* - * Copy groups in to a credential, preserving any necessicary invariants - * (i.e. sorting in the future). crextend() must have been called - * before hand to ensure sufficient space is available. If + * Copy groups in to a credential, preserving any necessary invariants. + * Currently this includes the sorting of all supplemental gids. + * crextend() must have been called before hand to ensure sufficient + * space is available. */ static void crsetgroups_locked(struct ucred *cr, int ngrp, gid_t *groups) { + int i; + int j; + gid_t g; KASSERT(cr->cr_agroups >= ngrp, ("cr_ngroups is too small")); bcopy(groups, cr->cr_groups, ngrp * sizeof(gid_t)); cr->cr_ngroups = ngrp; + + /* + * 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; + } } /*
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200906202029.n5KKTLDx086045>