From owner-svn-src-projects@FreeBSD.ORG Fri Jun 19 21:11:09 2009 Return-Path: Delivered-To: svn-src-projects@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id B76491065674; Fri, 19 Jun 2009 21:11:09 +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 8C67A8FC28; Fri, 19 Jun 2009 21:11:09 +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 n5JLB9XW055394; Fri, 19 Jun 2009 21:11:09 GMT (envelope-from brooks@svn.freebsd.org) Received: (from brooks@localhost) by svn.freebsd.org (8.14.3/8.14.3/Submit) id n5JLB978055392; Fri, 19 Jun 2009 21:11:09 GMT (envelope-from brooks@svn.freebsd.org) Message-Id: <200906192111.n5JLB978055392@svn.freebsd.org> From: Brooks Davis Date: Fri, 19 Jun 2009 21:11:09 +0000 (UTC) To: src-committers@freebsd.org, svn-src-projects@freebsd.org X-SVN-Group: projects MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Cc: Subject: svn commit: r194514 - projects/ngroups/sys/kern X-BeenThere: svn-src-projects@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "SVN commit messages for the src " projects" tree" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 19 Jun 2009 21:11:10 -0000 Author: brooks Date: Fri Jun 19 21:11:09 2009 New Revision: 194514 URL: http://svn.freebsd.org/changeset/base/194514 Log: Use insertion sort of sort supplemental groups in crsetgroups(). Take advantage of this an reimplement groupmember() as a test against cr_group[0] followed by a binary search of the supplemental groups. Seems to work in trivial testing. Modified: projects/ngroups/sys/kern/kern_prot.c Modified: projects/ngroups/sys/kern/kern_prot.c ============================================================================== --- projects/ngroups/sys/kern/kern_prot.c Fri Jun 19 21:01:55 2009 (r194513) +++ projects/ngroups/sys/kern/kern_prot.c Fri Jun 19 21:11:09 2009 (r194514) @@ -1248,13 +1248,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 wasn't 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 +2003,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; + } } /*