Subject: Re: CVS commit: [elad-kernelauth] src/sys/kern
To: David Laight <david@l8s.co.uk>
From: Elad Efrat <elad@NetBSD.org>
List: source-changes
Date: 03/12/2006 00:28:13
This is a multi-part message in MIME format.
--------------020503040002020500060404
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

David Laight wrote:

> Are you really sure you want to replace a memcmp() with an O(n^2) operation ?

I'll elaborate some more...

kauth(9) sorts the group on its own, so we could make that a binary
search, improving performance a bit.

But using memcmp() will treat the groups associated with the credentials
as a block of memory, while they're not guaranteed (in the future) to be
one.

Attached is a diff that does binary search instead of the current
linear one, would you prefer something like this?

-e.

-- 
Elad Efrat

--------------020503040002020500060404
Content-Type: text/plain;
 name="kern_auth.c.diff"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="kern_auth.c.diff"

Index: kern_auth.c
===================================================================
RCS file: /cvsroot/src/sys/kern/Attic/kern_auth.c,v
retrieving revision 1.1.2.19
diff -u -p -r1.1.2.19 kern_auth.c
--- kern_auth.c	11 Mar 2006 16:45:25 -0000	1.1.2.19
+++ kern_auth.c	11 Mar 2006 22:21:35 -0000
@@ -306,7 +306,7 @@ kauth_cred_setsvgid(kauth_cred_t cred, g
 int
 kauth_cred_ismember_gid(kauth_cred_t cred, gid_t gid, int *resultp)
 {
-	int i;
+	int high, low, mid;
 
 	KASSERT(cred != NULL);
 	KASSERT(gid >= 0 && gid <= GID_MAX);
@@ -314,9 +314,19 @@ kauth_cred_ismember_gid(kauth_cred_t cre
 
 	*resultp = 0;
 
-	for (i = 0; i < cred->cr_ngroups; i++) {
-		if (cred->cr_groups[i] == gid)
+	high = cred->cr_ngroups;
+	low = -1;
+
+	while (high - low > 1) {
+		mid = (high + low) / 2;
+		if (cred->cr_groups[mid] == gid) {
 			*resultp = 1;
+			break;
+		}
+		if (cred->cr_groups[mid] > gid)
+			high = mid;
+		else
+			low = mid;
 	}
 
 	return (0);

--------------020503040002020500060404--