[PATCH 2.6.18-rc1] Make group sorting optional in the 2.6.x kernels

[PATCH 2.6.18-rc1] Make group sorting optional in the 2.6.x kernels

[Bill Ryder]

[-- Attachment #1: Type: text/plain, Size: 1904 bytes --]

Hello all,

I've read all the stuff on submitting patches and this seems to be the
place.

Please CC me on any replies to this (although I do watch this through
list with  gmane)

Here's the patch description. I've attached the patch. Hopefully I've
followed the rules in Documentation/Submit* - apart from CC'ing Linus).

Summary:

Patch to allow the option of not sorting a process's supplemental
(also known ask secondary aka supplementary) group list. 

Setting the kernel config option of UNSORTED_SUPPLEMENTAL_GROUPLIST
will allow the use of setgroups(2) to reorder a supplemental
group list to work around the NFS AUTH_UNIX 16 group limit. 

In fact I  think this should be the default option because anyone using
setgroups
may get an unpleasant surprise with 2.6.x. But for now this patch makes
it an option.

Longer version:

Like many places Weta Digital (we did the VFX for Lord of the Rings,
King Kong etc)
uses supplemental group lists to allow users access to multiple
directories and files (films mostly in our
case) . Unfortunately NFSv2 and NFSv3 AUTH_UNIX flavour authentication
is hardcoded to only support 16 supplemental groups. Since we currently
have some users and processes which need to be in more than 16 groups
we use setgroups to build a list of groups that a process requires when
they access data on nfs exported filesystems.

This worked fine for the 2.4.x kernels. 2.6.x is designed to handle
thousands of groups for a single user. To support that the kernel was
changed to sort the group list, then use a binary search to decide if
a user was in the correct group. Unfortunately this BREAKS the use of
setgroups(2) to put the 16 most important groups first. 

This patch provides the option of not sorting that list. The help
describes the pitfalls of not sorting the groups (performance when
there are a lot of groups).

----
Bill Ryder
System Engineer
Weta Digital




[-- Attachment #2: linux-2.6.18-rc1.unsorted_groups.patch --]
[-- Type: text/x-patch, Size: 5145 bytes --]

diff -uprN -X linux-2.6.18-rc1.orig/Documentation/dontdiff linux-2.6.18-rc1.orig/arch/i386/Kconfig linux-2.6.18-rc1.unsorted_groups/arch/i386/Kconfig
--- linux-2.6.18-rc1.orig/arch/i386/Kconfig	2006-07-07 13:12:20.000000000 +1200
+++ linux-2.6.18-rc1.unsorted_groups/arch/i386/Kconfig	2006-07-07 11:46:34.000000000 +1200
@@ -258,6 +258,7 @@ config SCHED_MC
 	  increased overhead in some places. If unsure say N here.
 
 source "kernel/Kconfig.preempt"
+source "kernel/Kconfig.unsortedgroups"
 
 config X86_UP_APIC
 	bool "Local APIC support on uniprocessors"
diff -uprN -X linux-2.6.18-rc1.orig/Documentation/dontdiff linux-2.6.18-rc1.orig/arch/mips/Kconfig linux-2.6.18-rc1.unsorted_groups/arch/mips/Kconfig
--- linux-2.6.18-rc1.orig/arch/mips/Kconfig	2006-07-07 13:12:22.000000000 +1200
+++ linux-2.6.18-rc1.unsorted_groups/arch/mips/Kconfig	2006-07-07 11:46:34.000000000 +1200
@@ -1820,6 +1820,7 @@ config HZ
 	default 1024 if HZ_1024
 
 source "kernel/Kconfig.preempt"
+source "kernel/Kconfig.unsortedgroups"
 
 config RTC_DS1742
 	bool "DS1742 BRAM/RTC support"
diff -uprN -X linux-2.6.18-rc1.orig/Documentation/dontdiff linux-2.6.18-rc1.orig/arch/parisc/Kconfig linux-2.6.18-rc1.unsorted_groups/arch/parisc/Kconfig
--- linux-2.6.18-rc1.orig/arch/parisc/Kconfig	2006-07-07 13:12:23.000000000 +1200
+++ linux-2.6.18-rc1.unsorted_groups/arch/parisc/Kconfig	2006-07-07 11:46:34.000000000 +1200
@@ -220,6 +220,7 @@ config NODES_SHIFT
 source "kernel/Kconfig.preempt"
 source "kernel/Kconfig.hz"
 source "mm/Kconfig"
+source "kernel/Kconfig.unsortedgroups"
 
 config COMPAT
 	def_bool y
diff -uprN -X linux-2.6.18-rc1.orig/Documentation/dontdiff linux-2.6.18-rc1.orig/arch/powerpc/Kconfig linux-2.6.18-rc1.unsorted_groups/arch/powerpc/Kconfig
--- linux-2.6.18-rc1.orig/arch/powerpc/Kconfig	2006-07-07 13:12:23.000000000 +1200
+++ linux-2.6.18-rc1.unsorted_groups/arch/powerpc/Kconfig	2006-07-07 11:46:34.000000000 +1200
@@ -593,6 +593,7 @@ config HIGHMEM
 source kernel/Kconfig.hz
 source kernel/Kconfig.preempt
 source "fs/Kconfig.binfmt"
+source "kernel/Kconfig.unsortedgroups"
 
 # We optimistically allocate largepages from the VM, so make the limit
 # large enough (16MB). This badly named config option is actually
diff -uprN -X linux-2.6.18-rc1.orig/Documentation/dontdiff linux-2.6.18-rc1.orig/arch/x86_64/Kconfig linux-2.6.18-rc1.unsorted_groups/arch/x86_64/Kconfig
--- linux-2.6.18-rc1.orig/arch/x86_64/Kconfig	2006-07-07 13:12:26.000000000 +1200
+++ linux-2.6.18-rc1.unsorted_groups/arch/x86_64/Kconfig	2006-07-07 11:46:34.000000000 +1200
@@ -273,6 +273,8 @@ config SCHED_MC
 	  increased overhead in some places. If unsure say N here.
 
 source "kernel/Kconfig.preempt"
+source "kernel/Kconfig.unsortedgroups"
+
 
 config NUMA
        bool "Non Uniform Memory Access (NUMA) Support"
diff -uprN -X linux-2.6.18-rc1.orig/Documentation/dontdiff linux-2.6.18-rc1.orig/kernel/Kconfig.unsortedgroups linux-2.6.18-rc1.unsorted_groups/kernel/Kconfig.unsortedgroups
--- linux-2.6.18-rc1.orig/kernel/Kconfig.unsortedgroups	1970-01-01 12:00:00.000000000 +1200
+++ linux-2.6.18-rc1.unsorted_groups/kernel/Kconfig.unsortedgroups	2006-07-07 11:46:34.000000000 +1200
@@ -0,0 +1,16 @@
+#
+# Groups order
+#
+config USE_UNSORTED_SUPPLEMENTAL_GROUPS
+	bool "Use unsorted supplemental groups"
+	help
+
+	 If you need to use setgroups(2) to order a process's supplemental group list so that you can 
+         choose which 16 groups are sent during a NFSv2 or NFSv3 AUTH_UNIX (the default authentication protocol)
+         transaction you need to say Y here.
+
+         If you do not have users with more than 16 groups who need to access NFS you don't need this.
+
+         Do not set this option if you are going to have users in thousands of secondary groups. The default 
+	 kernel implementation sorts the groups and then binary searches them for membership. This option forces 
+  	 the search to be linear.
diff -uprN -X linux-2.6.18-rc1.orig/Documentation/dontdiff linux-2.6.18-rc1.orig/kernel/sys.c linux-2.6.18-rc1.unsorted_groups/kernel/sys.c
--- linux-2.6.18-rc1.orig/kernel/sys.c	2006-07-07 13:12:44.000000000 +1200
+++ linux-2.6.18-rc1.unsorted_groups/kernel/sys.c	2006-07-11 14:45:08.007916000 +1200
@@ -1535,14 +1535,22 @@ static void groups_sort(struct group_inf
 	}
 }
 
-/* a simple bsearch */
+/* if USE_UNSORTED_SUPPLEMENTAL_GROUPS is set this is a linear search. If not it's a binary search */
 int groups_search(struct group_info *group_info, gid_t grp)
 {
-	unsigned int left, right;
 
 	if (!group_info)
 		return 0;
 
+#ifdef USE_UNSORTED_SUPPLEMENTAL_GROUPS
+	unsigned int i;
+
+	for (i=0; i < group_info->ngroups; i++)
+		if (GROUP_AT(group_info,i) == grp)
+			return 1;
+#else
+	unsigned int left, right;
+
 	left = 0;
 	right = group_info->ngroups;
 	while (left < right) {
@@ -1555,6 +1563,7 @@ int groups_search(struct group_info *gro
 		else
 			return 1;
 	}
+#endif
 	return 0;
 }
 
@@ -1568,7 +1577,10 @@ int set_current_groups(struct group_info
 	if (retval)
 		return retval;
 
+#ifndef USE_UNSORTED_SUPPLEMENTAL_GROUPS
 	groups_sort(group_info);
+#endif
+
 	get_group_info(group_info);
 
 	task_lock(current);

Re: [PATCH 2.6.18-rc1] Make group sorting optional in the 2.6.x kernels

[Randy.Dunlap]

On Tue, 11 Jul 2006 16:26:48 +1200 Bill Ryder wrote:

> Hello all,
> 
> I've read all the stuff on submitting patches and this seems to be the
> place.
> 
> Please CC me on any replies to this (although I do watch this through
> list with  gmane)
> 
> Here's the patch description. I've attached the patch. Hopefully I've
> followed the rules in Documentation/Submit* - apart from CC'ing Linus).

6) No MIME, no links, no compression, no attachments.  Just plain text.

Attachments make it difficult to review/comment.

You'll likely need to coax Andrew into merging/testing it in -mm
rather than sending it to Linus.

> Summary:
> 
> Patch to allow the option of not sorting a process's supplemental
> (also known ask secondary aka supplementary) group list. 
> 
> Setting the kernel config option of UNSORTED_SUPPLEMENTAL_GROUPLIST
> will allow the use of setgroups(2) to reorder a supplemental
> group list to work around the NFS AUTH_UNIX 16 group limit. 
> 
> In fact I  think this should be the default option because anyone using
> setgroups
> may get an unpleasant surprise with 2.6.x. But for now this patch makes
> it an option.
> 
> Longer version:
> 
> Like many places Weta Digital (we did the VFX for Lord of the Rings,
> King Kong etc)
> uses supplemental group lists to allow users access to multiple
> directories and files (films mostly in our
> case) . Unfortunately NFSv2 and NFSv3 AUTH_UNIX flavour authentication
> is hardcoded to only support 16 supplemental groups. Since we currently
> have some users and processes which need to be in more than 16 groups
> we use setgroups to build a list of groups that a process requires when
> they access data on nfs exported filesystems.
> 
> This worked fine for the 2.4.x kernels. 2.6.x is designed to handle
> thousands of groups for a single user. To support that the kernel was
> changed to sort the group list, then use a binary search to decide if
> a user was in the correct group. Unfortunately this BREAKS the use of
> setgroups(2) to put the 16 most important groups first. 
> 
> This patch provides the option of not sorting that list. The help
> describes the pitfalls of not sorting the groups (performance when
> there are a lot of groups).

Patch comments:

Keep Kconfig help text to less than 80 columns so that it fits in
an xterm without requiring left/right scrolling.

Keep source code/comments within 80 columns (for xterms again).
So this comment needs to be broken/split:

+/* if USE_UNSORTED_SUPPLEMENTAL_GROUPS is set this is a linear search. If not it's a binary search */

In the groups_search() function, all data needs to be declared
before any executable code statements.

Lines like this:
+#ifdef USE_UNSORTED_SUPPLEMENTAL_GROUPS

should be:
+#ifdef CONFIG_USE_UNSORTED_SUPPLEMENTAL_GROUPS

i.e., the config system prefixes all config symbols with CONFIG_.

Was it tested like this?
Look at Documentation/SubmitChecklist along with
Documentation/SubmittingPatches.

---
~Randy

Re: [PATCH 2.6.18-rc1] Make group sorting optional in the 2.6.x kernels

[Ray Lee]

(Sorry for the duplicate, Bill -- lkml bounced my gmail account's message.)

In addition to Randy's fine comments...

On 7/10/06, Bill Ryder <bryder@wetafx.co.nz> wrote:
> Like many places Weta Digital (we did the VFX for Lord of the Rings,
> King Kong etc) uses supplemental group lists to allow users access to
> multiple directories and files (films mostly in our case) .
> Unfortunately NFSv2 and NFSv3 AUTH_UNIX flavour authentication is
> hardcoded to only support 16 supplemental groups. Since we currently
> have some users and processes which need to be in more than 16 groups
> we use setgroups to build a list of groups that a process requires
> when they access data on nfs exported filesystems.
>
> This worked fine for the 2.4.x kernels. 2.6.x is designed to handle
> thousands of groups for a single user. To support that the kernel was
> changed to sort the group list, then use a binary search to decide if
> a user was in the correct group. Unfortunately this BREAKS the use of
> setgroups(2) to put the 16 most important groups first.
>
> This patch provides the option of not sorting that list. The help
> describes the pitfalls of not sorting the groups (performance when
> there are a lot of groups).

It seems there's a third way to do this that would maintain setgroups(2)
compatibility and speed when you have a lot of groups.

Maintain the list of groups such that the first sixteen correspond to
what setgroups(2) requested, and keep the rest sorted. A search for
groups would then linearly check each of the first sixteen entries then,
if there's more, binary search the remainder from 16 to group_info->ngroups.

That'd allow this to be enabled everywhere (removing the CONFIG_
option), maintain backward compatibility, and still be fast in the face
of thousands of groups. The down side is slightly more complex code.
Well, and that you have to write it :-/.

On the other hand, as I haven't looked at the groups code, my suggestion
may be, y'know, nuts.

Ray

Re: [PATCH 2.6.18-rc1] Make group sorting optional in the 2.6.x kernels

[Bill Ryder]

Ray Lee wrote:
> In addition to Randy's fine comments...
>
>
>
> It seems there's a third way to do this that would maintain
> setgroups(2) compatibility and speed when you have a lot of groups.
At least for NFS which is the problem here.
>
> Maintain the list of groups such that the first sixteen correspond to
> what setgroups(2) requested, and keep the rest sorted. A search for
> groups would then linearly check each of the first sixteen entries
> then, if there's more, binary search the remainder from 16 to
> group_info->ngroups.
That's a great idea.

I'll do that instead.

And next time I won't attach the patch :-)

Re: [PATCH 2.6.18-rc1] Make group sorting optional in the 2.6.x kernels

[Frank van Maarseveen]

On Tue, Jul 11, 2006 at 04:26:48PM +1200, Bill Ryder wrote:
> Hello all,
> 
> Setting the kernel config option of UNSORTED_SUPPLEMENTAL_GROUPLIST
> will allow the use of setgroups(2) to reorder a supplemental
> group list to work around the NFS AUTH_UNIX 16 group limit. 

FYI,

This problem has been worked around for several years now using
these 2.4.x and 2.6.x patches:

	http://www.frankvm.com/nfs-ngroups/


-- 
Frank

Re: [PATCH 2.6.18-rc1] Make group sorting optional in the 2.6.x kernels

[Bill Ryder]

Hi Frank,

I'm aware of the patch. In fact I've spent far too much time researching
the > 16 groups problem as I'm sure so many others have. It's so sad the
nfs designers made that gid list a fixed length array. Anyway ..

There are two reasons we don't use your patch:

* It's not a standard part of the kernel. So we have to always patch.
This can be  painful for our junior admins for new versions.
* The major reason though is that we run OSX and IRIX as well linux. By
using setgroups everywhere we solve our problem for all cases, including
the proprietary OS's for which we don't have source. This is a big deal.


I thought a smaller simpler patch would be easier to get into linux as
standard would be easier to accept - and that in combination with our
userland tools solves our problem. Also the new version of the patch
which I will write will not completely break the semantics of setgroups
which is what the 2.6.x kernel does now.


As an aside Frank - can you point at a paper which provides a
walkthrough of how your patch  works and what the caveats are?

I tried to find a straightforward explanation a while ago and couldn't
-  and didn't have the time to work through it myself. I only have a
pretty sketchy understanding of the flow of control/data for nfs/fs
permissions checking in the kernel and it would take me a LONG time to
figure it out - assuming I even could.

For our purposes we would have a single process which needs to be able
to access multiple groups at completely different points in the tree..

For example

/top(0)/p1(2)/p3(2)/p4(2)/p5(6)/file1(6)
/top(0)/p1(2)/p3(2)/p4(2)/p6(7)/file2(7)
/top(0)/p1(2)/p3(2)/p4(2)/p7(8)/file3(6)
/top(0)/p1(2)/p3(2)/p4(2)/p7(8)/file4(8)

And so on - where the (n) indicated the (gid) for that directory/file.
So most of our directories are in the same group. But as you get further
down the tree the groups start to change.

The process will belong to > 16 groups.


Thanx
Bill


Frank van Maarseveen wrote:
> On Tue, Jul 11, 2006 at 04:26:48PM +1200, Bill Ryder wrote:
>   
>> Hello all,
>>
>> Setting the kernel config option of UNSORTED_SUPPLEMENTAL_GROUPLIST
>> will allow the use of setgroups(2) to reorder a supplemental
>> group list to work around the NFS AUTH_UNIX 16 group limit. 
>>     
>
> FYI,
>
> This problem has been worked around for several years now using
> these 2.4.x and 2.6.x patches:
>
> 	http://www.frankvm.com/nfs-ngroups/
>
>
>   

Re: [PATCH 2.6.18-rc1] Make group sorting optional in the 2.6.x kernels

[Frank van Maarseveen]

On Thu, Jul 20, 2006 at 08:17:47AM +1200, Bill Ryder wrote:
[...]
> As an aside Frank - can you point at a paper which provides a
> walkthrough of how your patch  works and what the caveats are?

	http://www.frankvm.com/nfs-ngroups/README

> For example
> 
> /top(0)/p1(2)/p3(2)/p4(2)/p5(6)/file1(6)
> /top(0)/p1(2)/p3(2)/p4(2)/p6(7)/file2(7)
> /top(0)/p1(2)/p3(2)/p4(2)/p7(8)/file3(6)
> /top(0)/p1(2)/p3(2)/p4(2)/p7(8)/file4(8)
> 
> And so on - where the (n) indicated the (gid) for that directory/file.
> So most of our directories are in the same group. But as you get further
> down the tree the groups start to change.
> 
> The process will belong to > 16 groups.

setgroups() require privilege. I don't understand how the above is
supposed to work for non-root users needing >16 groups. And when you're
root it is silly to play these group games for getting access.

-- 
Frank

Re: [PATCH 2.6.18-rc1] Make group sorting optional in the 2.6.x kernels

[Bill Ryder]

First of all a reminder.

We have proprietary UNIX here.

All I need from linux is that it obeys the setgroups(2) POSIX call - at
least  in the first 16 groups.


Frank van Maarseveen wrote:
> On Thu, Jul 20, 2006 at 08:17:47AM +1200, Bill Ryder wrote: [...]
>> As an aside Frank - can you point at a paper which provides a
>> walkthrough of how your patch  works and what the caveats are?
>
> http://www.frankvm.com/nfs-ngroups/README

I  read that when I was first researching this. But I couldn't see how
it works based on the description. Bearing in mind I do not spend hours
understanding how the kernel walks permissions and paths.

By walkthrough I mean a walkthrough of permissions checking for the
paths I outlined below. The test case being where every file is in a
different group (and of course the groups are outside fo the first 16
groups in the grouplist). You can not assume their parent directory
belongs to the same group as the file.

This isn't a walkthrough:

<quote>

It is fairly simple to predict the group id's which might make a difference
in an operation on NFS on the client system, assuming the NFS server does
permission checking conform UNIX. This is not a bad assumption when NFS
uses RPC with AUTH_UNIX authentication. Pathnames at system call time
are not handled in one NFS operation (NFS != WebNFS) but by a series
of NFS lookups. Therefor the maximum number of groups required at any
specific point in time is 3 at most: see nfs_rename().

</quote>

Nor is this:

<quote>
Patch 4.x

Group id cache is gone. At the top NFS layer the group ids of
"interesting" file-system objects are collected (max 3, mostly 1) and
passed downwards. When an RPC credential is created the new AUTH_UNIX
specific unx_add_groups() function will add all the necessary group
information. When the number of groups is 16 or lower then it reverts
to old behavior. When there is no group id information passed downwards
then it reverts to old behavior too. Otherwise, only groups present in
_both_ group information passed downwards and the secondary group list
will be used for the AUTH_UNIX rpc credential (i.e. group lists are
intersected).
</quote>

There are a number of  'assumptions' that I do not have the knowledge to
know if they are reasonable or not.

This phrase is worrying:

When there is no group id information passed downwards
then it reverts to old behavior too.

Why would no group id information be passed?

For someone of my level of knowledge of the kernel the README does not
convince me it will work in all situations. One of my colleagues coined
the phrase  "You can't predict the worse case at Weta DIgital". This is
definitely a true statement for us!

In other words the README assumes a lot of implied knowledge which I
don't have. Hence I don't understand why it doesn't work in the above
case. Which is why I asked for a presentation/paper which would
walkthrough the case below (extending it to > 16 groups of course).


But I will say again just to be sure you understand it's not your patch
that is the problem (or the solution). I need a solution that will work
with *nixs for which I do not have kernel source.

The 'right' way to do this is to use posix calls and/or provides OS
calls to solve the problem in a transparent easy to explain and
understand way to all levels of reasonable IT people.

>
>> For example
>>
>> /top(0)/p1(2)/p3(2)/p4(2)/p5(6)/file1(6)
>> /top(0)/p1(2)/p3(2)/p4(2)/p6(7)/file2(7)
>> /top(0)/p1(2)/p3(2)/p4(2)/p7(8)/file3(6)
>> /top(0)/p1(2)/p3(2)/p4(2)/p7(8)/file4(8)
>>
>> And so on - where the (n) indicated the (gid) for that
>> directory/file. So most of our directories are in the same group.
>> But as you get further down the tree the groups start to change.
>>
>> The process will belong to > 16 groups.
>
> setgroups() require privilege. I don't understand how the above is
> supposed to work for non-root users needing >16 groups. And when
> you're root it is silly to play these group games for getting access.
>

It's no sillier than sg or SCO's sgs. There are clearly defined posix
ways to get this information and to use it. OSx of course has a slightly
different way to handle > 16 groups but it still is sensible and
setgroups still works.

I need to solve the problem of NFS only allowing 16 groups when we have
around 32 groups here.

It needs to work on multiple OSs. At the moment Linux is the only OS
this does not work for (unless we stick to 2.4.x kernels - which is not
acceptable).

Any solution needs to use standard methods (ie using APIs shipped with
the box/OS and using a standard kernel - ie not patched).

At the moment linux 2.6.x breaks the semantics of setgroups,  That needs
to be fixed. I will write a patch for that (at least in the first 16
groups)  It will be small and hopefully easy enought to understand so
that it will be a standard part of the kernel.

That way linux will behave in the same way with respect to the first 16
groups as all the other *nixs we run.

---
Bill Ryder
System Engineer
Weta Digital  - land of virtual  hobbits, Gandalf, Big Monkeys, robots,
mutants and anything else you can imagine that can be rendered, shaded,
modelled, animated, motion captured, tracked, simulated, comped or painted.

Re: [PATCH 2.6.18-rc1] Make group sorting optional in the 2.6.x kernels

[Frank van Maarseveen]

On Fri, Jul 21, 2006 at 08:40:44AM +1200, Bill Ryder wrote:
[...]
> This phrase is worrying:
> 
> When there is no group id information passed downwards
> then it reverts to old behavior too.
> 
> Why would no group id information be passed?

There are a few NFS operations (or related ones such as
for file locking) which do not need that information IIRC.
"old behavior" means doing what it does _today_.


> For someone of my level of knowledge of the kernel the README does not
> convince me it will work in all situations.

NFS with AUTH_UNIX authentication cannot possibly get worse than it is
today with respect to processes in more than 16 groups. And the patch
is effectively disabled for processes in <=16 groups so I wouldn't
worry.

Anyway, a revised patch from you which no longer sorts the first 16
groups for compatibility reasons is probably easier to get merged.

-- 
Frank