Make group sorting optional in the 2.6.x kernels
Subsystems (3)
PATCH 1/1 Make group sorting optional in the 2.6.x kernels
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
arch/i386/Kconfig +1 -0
@@ -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"
arch/mips/Kconfig +1 -0
@@ -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"
arch/parisc/Kconfig +1 -0
@@ -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
arch/powerpc/Kconfig +1 -0
@@ -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
arch/x86_64/Kconfig +2 -0
@@ -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"
kernel/Kconfig.unsortedgroups +16 -0
@@ -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.
kernel/sys.c +14 -2
@@ -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_infoif (retval)return retval; +#ifndef USE_UNSORTED_SUPPLEMENTAL_GROUPS groups_sort (group_info); +#endif +get_group_info (group_info);task_lock (current);
Quoted 10 lines · 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.
Quoted 32 lines
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_GROUPLISTwill allow the use of setgroups(2) to reorder a supplemental group list to work around the NFSAUTH_UNIX16 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 NFSv3AUTH_UNIXflavour 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.
Quoted 3 lines
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 withDocumentation/SubmittingPatches.
---
~Randy
A message that is not in the archive (sent off-list or not yet received): [email protected]
(Sorry for the duplicate, Bill -- lkml bounced my gmail account's message.)
In addition to Randy's fine comments...
Quoted 15 lines · Bill Ryder
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_UNIXflavour 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.
Quoted 3 lines
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
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 6 lines · Ray Lee
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.
Quoted 6 lines
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 :-)
Quoted 5 lines · Bill Ryder
Hello all,
Setting the kernel config option of
UNSORTED_SUPPLEMENTAL_GROUPLISTwill allow the use of setgroups(2) to reorder a supplemental group list to work around the NFSAUTH_UNIX16 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/
Signature · 1 line
Frank
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
Quoted 18 lines · Frank van Maarseveen
Quoted 6 lines · Bill Ryder
Hello all,
Setting the kernel config option of
UNSORTED_SUPPLEMENTAL_GROUPLISTwill allow the use of setgroups(2) to reorder a supplemental group list to work around the NFSAUTH_UNIX16 group limit.FYI,
This problem has been worked around for several years now using these 2.4.x and 2.6.x patches:
On Thu, Jul 20, 2006 at 08:17:47AM +1200, Bill Ryder wrote:
[...]
Quoted 2 lines
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
Quoted 7 lines
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)
Quoted 5 lines
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.
Signature · 1 line
Frank
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.
Quoted 5 lines · Frank van Maarseveen
On Thu, Jul 20, 2006 at 08:17:47AM +1200, Bill Ryder wrote: [...]
Quoted 2 lines
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 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.
Quoted 12 lines
Quoted 12 lines
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.
Quoted 6 lines
Quoted 1 line
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.
On Fri, Jul 21, 2006 at 08:40:44AM +1200, Bill Ryder wrote:
[...]
Quoted 6 lines
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_.
Quoted 2 lines
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.
Signature · 1 line
Frank