From owner-svn-src-head@FreeBSD.ORG Sat Jun 20 20:29:21 2009 Return-Path: Delivered-To: svn-src-head@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id D39331065687; Sat, 20 Jun 2009 20:29:21 +0000 (UTC) (envelope-from brooks@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:4f8:fff6::2c]) by mx1.freebsd.org (Postfix) with ESMTP id A73D38FC21; Sat, 20 Jun 2009 20:29:21 +0000 (UTC) (envelope-from brooks@FreeBSD.org) Received: from svn.freebsd.org (localhost [127.0.0.1]) by svn.freebsd.org (8.14.3/8.14.3) with ESMTP id n5KKTLZb086047; Sat, 20 Jun 2009 20:29:21 GMT (envelope-from brooks@svn.freebsd.org) Received: (from brooks@localhost) by svn.freebsd.org (8.14.3/8.14.3/Submit) id n5KKTLDx086045; Sat, 20 Jun 2009 20:29:21 GMT (envelope-from brooks@svn.freebsd.org) Message-Id: <200906202029.n5KKTLDx086045@svn.freebsd.org> From: Brooks Davis Date: Sat, 20 Jun 2009 20:29:21 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org X-SVN-Group: head MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Cc: Subject: svn commit: r194556 - head/sys/kern X-BeenThere: svn-src-head@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: SVN commit messages for the src tree for head/-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 20 Jun 2009 20:29:22 -0000 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; + } } /*