Re: CVS commit: [elad-kernelauth] src/sys/kern

[Elad Efrat <elad%NetBSD.org@localhost>]

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

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);