svn commit: r194514 - projects/ngroups/sys/kern

[Brooks Davis]

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;
+	}
 }
 
 /*