Remove NGROUPS hardlimit (resend w/o qsort)
Two questions.
1. Why are arrays vmalloc-ed? This is a goochism which you have to justify.
2. How do these changes sit with LLNL's changes to increase number of groups that NFS client can support? It's not a showstopper, but would be nice if you two cooperated.
-- Pete
Quoted 4 lines · Pete Zaitcev
Two questions.
1. Why are arrays vmalloc-ed? This is a goochism which you have to justify.
Because they can be as large as root allows, and when we used kmalloc() it would actually fail from time to time.
Quoted 3 lines
2. How do these changes sit with LLNL's changes to increase number of groups that NFS client can support? It's not a showstopper, but would be nice if you two cooperated.
hmm, I haven't heard anything about them - can you offer an email or URL?
Thanks
Signature · 4 lines
Tim Hockin Systems Software Engineer Sun Microsystems, Linux Kernel Engineering [email protected]
Quoted 8 lines
Date: Thu, 14 Nov 2002 16:14:29 -0800
From: Tim Hockin <[email protected]>Quoted 2 lines
1. Why are arrays vmalloc-ed? This is a goochism which you have to justify.
Because they can be as large as root allows, and when we used
kmalloc()it would actually fail from time to time.
OK. I think in your case it's probably harmless. I thought that two (order 1) 4K pages can hold 2000 4 byte group IDs, and that "ought to be enough for anybody". If you envision 10,000 groups, then perhaps you are right, except that it may be about time to think about your data structures a little more. I'll let Andi to remind you about the performance impact (vmalloc area is outside of the big TLB area).
Quoted 5 lines
Quoted 3 lines
2. How do these changes sit with LLNL's changes to increase number of groups that NFS client can support? It's not a showstopper, but would be nice if you two cooperated.
hmm, I haven't heard anything about them - can you offer an email or URL?
http://www.uwsg.iu.edu/hypermail/linux/kernel/0010.0/0788.html
The sad part is that the patch was around since 2000, but the effort to get it in was a little half-hearted, perhaps. I am thinking about reviving it.
-- Pete
Quoted 8 lines · Pete Zaitcev
Quoted 1 line
Date: Thu, 14 Nov 2002 16:14:29 -0800
OK. I think in your case it's probably harmless. I thought that two (order 1) 4K pages can hold 2000 4 byte group IDs, and that "ought to be enough for anybody". If you envision 10,000 groups, then perhaps you are right, except that it may be about time to think about your data structures a little more. I'll let Andi to remind you about the performance impact (vmalloc area is outside of the big TLB area).
vmalloc will allocate 12K of address space or so and will actually die first with fragmentation problems. We should also keep small numbers of groups inline otherwise you are going to upset the "million threads" people 8)
Quoted 3 lines · Pete Zaitcev
be about time to think about your data structures a little more. I'll let Andi to remind you about the performance impact (vmalloc area is outside of the big TLB area).
Offer an alternative? :) Linked list costs us as much or MORE for ->next as the gid_t. kmalloc() doesn't work for previous reasoning. I considered a list of gid arr[256] or similar. A voice reminds me that it doesn't impact us noticably in real use. Now, maybe other architectures will find a good reason to switch to kmalloc() list of smaller arrays, and the associated complextities or something else more clever.
Quoted 3 lines
Quoted 1 line
hmm, I haven't heard anything about them - can you offer an email or URL?
http://www.uwsg.iu.edu/hypermail/linux/kernel/0010.0/0788.html
Thanks - will check it..
Signature · 4 lines
Tim Hockin Systems Software Engineer Sun Microsystems, Linux Kernel Engineering [email protected]
Quoted 7 lines · Tim Hockin
Offer an alternative? :) Linked list costs us as much or MORE for ->next as the
gid_t.kmalloc()doesn't work for previous reasoning. I considered a list of gid arr[256] or similar. A voice reminds me that it doesn't impact us noticably in real use. Now, maybe other architectures will find a good reason to switch tokmalloc()list of smaller arrays, and the associated complextities or something else more clever.
Well, there are always B-trees; nice low arrival rates to the allocator owing to elements/node and O(lg(n)) searches with low constants due to big fat branching factors. Not my call though.
Bill
Quoted 7 lines · Andrew Morton
What are you actually using the search for?
Quoted 1 line
From a quick look, it seems that it's purely to answer
the question "is this process a member of group X?". Is that correct?
If so,
test_bit()would work nicely.
This could work if we find the max gid, allocate an array of max_gid/CHAR_BITS + 1 bytes then test_bit, but given the non-contiguity (is that a word) of group memberships, we'll waste a lot of space on holes. Now, it could be argued that 10,000 groups are PROBABLY local enough. Getting the groups back out will be nasty nastiness, though.
perhaps:
if (gidsetsize < (2 * EXEC_PAGESIZE)/sizeof(gid_t)) { /* or something */
/* use kmalloc() */ else /* use vmalloc() */
thoughts?
Signature · 4 lines
Tim Hockin Systems Software Engineer Sun Microsystems, Linux Kernel Engineering [email protected]
Quoted 17 lines · Tim Hockin
Quoted 7 lines · Andrew Morton
What are you actually using the search for?
Quoted 1 line
From a quick look, it seems that it's purely to answer
the question "is this process a member of group X?". Is that correct?
If so,
test_bit()would work nicely.This could work if we find the max gid, allocate an array of max_gid/CHAR_BITS + 1 bytes then
test_bit, but given the non-contiguity (is that a word) of group memberships, we'll waste a lot of space on holes. Now, it could be argued that 10,000 groups are PROBABLY local enough. Getting the groups back out will be nasty nastiness, though.
Quoted 9 lines
perhaps:
if (gidsetsize < (2 * EXEC_PAGESIZE)/sizeof(gid_t)) { /* or something */
/* use kmalloc() */ else /* use vmalloc() */thoughts?
10,000 bits isn't much. Maybe:
- add `char groups[16]' to task_struct
- add `struct page *groups_page' to task_struct
- then
if (getsetsize <= 256) use current->groups[] /* 256 groups max */ else use current->groups_page; /* 32768 groups max */
Quoted 11 lines
Quoted 7 lines
Offer an alternative? :) Linked list costs us as much or MORE for ->next as the
gid_t.kmalloc()doesn't work for previous reasoning. I considered a list of gid arr[256] or similar. A voice reminds me that it doesn't impact us noticably in real use. Now, maybe other architectures will find a good reason to switch tokmalloc()list of smaller arrays, and the associated complextities or something else more clever.Well, there are always B-trees; nice low arrival rates to the allocator owing to elements/node and O(lg(n)) searches with low constants due to big fat branching factors. Not my call though.
This sounds intriguing.
Bill, if I may borrow from your data structure expertise, what would you do if you wanted gid_t's indexed by two criteria? Obviously, we want them them indexed by value (to look them up for access checking), but NFS also needs them sorted by usage, to fit the last 3 into the RPC parameters. This looks like something requiring two overlaying trees who share leafs, and every leaf being a single gid_t, with nightmarish overhead.
Before Tim came to the scene, the hope was that lookups would do exhaustive search of arrays, sorted by LRU, while RPC picked N leading elements of said sorted array. Tim busts this scheme to pieces, because he sorts arrays by value (if I read it right).
-- Pete
Quoted 5 lines · Pete Zaitcev
This sounds intriguing.
Bill, if I may borrow from your data structure expertise, what would you do if you wanted gid_t's indexed by two criteria? Obviously, we want them them indexed by value (to look them up for access checking), but NFS also needs them sorted by usage,
Quoted 8 lines
to fit the last 3 into the RPC parameters. This looks like something requiring two overlaying trees who share leafs, and every leaf being a single
gid_t, with nightmarish overhead. Before Tim came to the scene, the hope was that lookups would do exhaustive search of arrays, sorted by LRU, while RPC picked N leading elements of said sorted array. Tim busts this scheme to pieces, because he sorts arrays by value (if I read it right).
B+ trees separate metadata from data entirely, so two distinct B+ tree "indices" attached will work just fine for this overlaying of trees that share leaves.
Bill
Quoted 1 line
10,000 bits isn't much. Maybe:
That's 10000 USED bits. Remember groups are non-contiguously allocated. If a task is a member of just groups 32767 and 65535, you'll get one bit per page used, and when they call getgroups() you need to pull it apart and return an array of gid_t.
Quoted 9 lines
- add `char groups[16]' to
task_struct- add `struct page
*groups_page' totask_struct- then
if (getsetsize <= 256) use current->groups[] /* 256 groups max */ else use current->groups_page; /* 32768 groups max */
Quoted 8 lines · Tim Hockin
Quoted 2 lines
10,000 bits isn't much. Maybe:
That's 10000 USED bits. Remember groups are non-contiguously allocated. If a task is a member of just groups 32767 and 65535, you'll get one bit per page used, and when they call
getgroups()you need to pull it apart and return an array ofgid_t.
Well that's what I was asking.
What is the maximum group ID? 0xffffffff?
In that case a radix tree _might_ suit. All you need to put in the node is a (void *)1 or (void *)0. But it won't be very space-efficient for really sparse groups.
Quoted 3 lines · Andrew Morton
- add `char groups[16]' to
task_struct- add `struct page
*groups_page' totask_struct
Wouldn't it be better to use a union to save space?
Quoted 11 lines · Pete Zaitcev
Quoted 5 lines
Quoted 3 lines
2. How do these changes sit with LLNL's changes to increase number of groups that NFS client can support? It's not a showstopper, but would be nice if you two cooperated.
hmm, I haven't heard anything about them - can you offer an email or URL?
http://www.uwsg.iu.edu/hypermail/linux/kernel/0010.0/0788.html
The sad part is that the patch was around since 2000, but the effort to get it in was a little half-hearted, perhaps. I am thinking about reviving it.
It's still alive. I'll make a 2.4.20 version of the patch once 2.4.20 is released. Or maybe earlier (a -rc version) since 2.4.20 appears to be imminent and I don't expect changes in that area. 2.5.latest is next on my list. Latest version is:
http://web.inter.nl.net/users/fvm/nfs-ngroups/2.4.19-nfs-ngroups-3.98.patch
I have dropped all the older versions (they go back to 2.2.13)
Signature · 1 line
Frank
Quoted 3 lines · Andrew Morton
In that case a radix tree _might_ suit. All you need to put in the node is a (void *)1 or (void *)0. But it won't be very space-efficient for really sparse groups.
99.999% of users will have < 16 groups, probably less than 8. If the system doesn't get that default case as fast and memory efficient as before the priorities are badly wrong.