On Thu, Nov 30 2017, Thiago Rafael Becker wrote:
> The responsibility for calling groups_sort is now on the caller
> of set_groups.
>
> Signed-off-by: Thiago Rafael Becker <[email protected]>
> ---
> kernel/groups.c | 1 +
> kernel/uid16.c | 1 +
> net/sunrpc/svcauth_unix.c | 7 +++++++
> 3 files changed, 9 insertions(+)
>
> diff --git a/kernel/groups.c b/kernel/groups.c
> index 4c9c9ed..17073a9 100644
> --- a/kernel/groups.c
> +++ b/kernel/groups.c
> @@ -208,6 +208,7 @@ SYSCALL_DEFINE2(setgroups, int, gidsetsize, gid_t __user *, grouplist)
> return retval;
> }
>
> + groups_sort(group_info);
> retval = set_current_groups(group_info);
> put_group_info(group_info);
>
> diff --git a/kernel/uid16.c b/kernel/uid16.c
> index ce74a49..ef1da2a 100644
> --- a/kernel/uid16.c
> +++ b/kernel/uid16.c
> @@ -192,6 +192,7 @@ SYSCALL_DEFINE2(setgroups16, int, gidsetsize, old_gid_t __user *, grouplist)
> return retval;
> }
>
> + groups_sort(group_info);
> retval = set_current_groups(group_info);
> put_group_info(group_info);
>
> diff --git a/net/sunrpc/svcauth_unix.c b/net/sunrpc/svcauth_unix.c
> index f81eaa8..91e3d34 100644
> --- a/net/sunrpc/svcauth_unix.c
> +++ b/net/sunrpc/svcauth_unix.c
> @@ -20,6 +20,7 @@
>
>
> #include "netns.h"
> +void groups_sort(struct group_info *group_info);
>
> /*
> * AUTHUNIX and AUTHNULL credentials are both handled here.
> @@ -520,6 +521,12 @@ static int unix_gid_parse(struct cache_detail *cd,
> ug.gi->gid[i] = kgid;
> }
>
> + /* Sort the groups before inserting this entry
> + * into the cache to avoid future corrutpions
> + * by multiple simultaneous attempts to sort this
> + * entry.
> + */
> + groups_sort(ug.gi);
> ugp = unix_gid_lookup(cd, uid);
> if (ugp) {
> struct cache_head *ch;
I think you need to add groups_sort() in a few more places.
Almost anywhere that calls groups_alloc() should be considered.
net/sunrpc/svcauth_unix.c, net/sunrpc/auth_gss/svcauth_gss.c,
fs/nfsd/auth.c definitely need it.
I wonder if there is a more robust way to fix this.
Maybe:
groups_alloc() could initialize ->usage to -1
groups_sort() to require it be -1, and change it to 1
get_group_info() complains if ->usage is -1 ???
or something.
Maybe it could be done with types.
'struct group_info' could be declared with ngroups and
gid[] as const.
'struct group_info_unsorted' could be the same structure but
without the 'const'.
Then groups_sort() takes a 'struct group_info_unsorted *' and returns
a 'struct group_info *'...
Thanks,
NeilBrown
On Mon, 4 Dec 2017, NeilBrown wrote:
> I think you need to add groups_sort() in a few more places.
> Almost anywhere that calls groups_alloc() should be considered.
> net/sunrpc/svcauth_unix.c, net/sunrpc/auth_gss/svcauth_gss.c,
> fs/nfsd/auth.c definitely need it.
So are any other functions that modify group_info. OK, I think I'll
implement the type detection below as it helps detecting where these
situations are located.
This may take some time to make sane. I wonder if we shouldn't
accept the first change suggested to fix the corruption detected in
auth.unix.gid while I work on a new set of patches. Also, that patch
doesn't change behavior of set_groups, and is easier to backport if
distros relying on older kernels need to do so and change behavior. The
first suggestion is undergoing tests, and so far we didn't detect any
new corruptions on auth.unix.gid.
> Maybe it could be done with types.
I changed the interfaces on groups_{alloc,sort} to check. There are some
extra changes needed in groups_from_user and others to make this viable,
but I like it and I'll try to make it happen.
> Thanks,
> NeilBrown
>
Thanks,
trbecker
On Mon, Dec 04, 2017 at 01:39:37PM -0200, Thiago Rafael Becker wrote:
>
>
> On Mon, 4 Dec 2017, NeilBrown wrote:
>
> >I think you need to add groups_sort() in a few more places.
> >Almost anywhere that calls groups_alloc() should be considered.
> >net/sunrpc/svcauth_unix.c, net/sunrpc/auth_gss/svcauth_gss.c,
> >fs/nfsd/auth.c definitely need it.
>
> So are any other functions that modify group_info. OK, I think I'll
> implement the type detection below as it helps detecting where these
> situations are located.
>
> This may take some time to make sane. I wonder if we shouldn't
> accept the first change suggested to fix the corruption detected in
> auth.unix.gid while I work on a new set of patches. Also, that patch
> doesn't change behavior of set_groups, and is easier to backport if
> distros relying on older kernels need to do so and change behavior.
> The first suggestion is undergoing tests, and so far we didn't
> detect any new corruptions on auth.unix.gid.
I'm a little confused--we can remedy the oversight Neil points out just
by adding a few more group_sort()s, and that shouldn't be hard, right?
I'd be OK with doing that first and then adding a code to enforce the
sorting second.
--b.
>
> >Maybe it could be done with types.
>
> I changed the interfaces on groups_{alloc,sort} to check. There are
> some extra changes needed in groups_from_user and others to make
> this viable, but I like it and I'll try to make it happen.
>
> >Thanks,
> >NeilBrown
> >
>
> Thanks,
> trbecker
> --
> To unsubscribe from this list: send the line "unsubscribe linux-nfs" in
> the body of a message to [email protected]
> More majordomo info at http://vger.kernel.org/majordomo-info.html
On Mon, 4 Dec 2017, J. Bruce Fields wrote:
> On Mon, Dec 04, 2017 at 01:39:37PM -0200, Thiago Rafael Becker wrote:
>>
>>
>> On Mon, 4 Dec 2017, NeilBrown wrote:
>>
>>> I think you need to add groups_sort() in a few more places.
>>> Almost anywhere that calls groups_alloc() should be considered.
>>> net/sunrpc/svcauth_unix.c, net/sunrpc/auth_gss/svcauth_gss.c,
>>> fs/nfsd/auth.c definitely need it.
>>
>> So are any other functions that modify group_info. OK, I think I'll
>> implement the type detection below as it helps detecting where these
>> situations are located.
>>
>> This may take some time to make sane. I wonder if we shouldn't
>> accept the first change suggested to fix the corruption detected in
>> auth.unix.gid while I work on a new set of patches. Also, that patch
>> doesn't change behavior of set_groups, and is easier to backport if
>> distros relying on older kernels need to do so and change behavior.
>> The first suggestion is undergoing tests, and so far we didn't
>> detect any new corruptions on auth.unix.gid.
>
> I'm a little confused--we can remedy the oversight Neil points out just
> by adding a few more group_sort()s, and that shouldn't be hard, right?
>
> I'd be OK with doing that first and then adding a code to enforce the
> sorting second.
Ok. Sending a new set. The set will cover all calls to group_alloc, after
the function has ended filling the groups.
> --b.
>
>>
>>> Maybe it could be done with types.
>>
>> I changed the interfaces on groups_{alloc,sort} to check. There are
>> some extra changes needed in groups_from_user and others to make
>> this viable, but I like it and I'll try to make it happen.
>>
>>> Thanks,
>>> NeilBrown
>>>
>>
>> Thanks,
>> trbecker
>> --
>> To unsubscribe from this list: send the line "unsubscribe linux-nfs" in
>> the body of a message to [email protected]
>> More majordomo info at http://vger.kernel.org/majordomo-info.html
>
On Mon, Dec 04 2017, Thiago Rafael Becker wrote:
> On Mon, 4 Dec 2017, NeilBrown wrote:
>
>> I think you need to add groups_sort() in a few more places.
>> Almost anywhere that calls groups_alloc() should be considered.
>> net/sunrpc/svcauth_unix.c, net/sunrpc/auth_gss/svcauth_gss.c,
>> fs/nfsd/auth.c definitely need it.
>
> So are any other functions that modify group_info. OK, I think I'll
> implement the type detection below as it helps detecting where these
> situations are located.
>
> This may take some time to make sane. I wonder if we shouldn't
> accept the first change suggested to fix the corruption detected in
> auth.unix.gid while I work on a new set of patches.
As we don't seem to be pursuing this possibility is probably isn't very
important, but I'd like to point out that the original fix isn't a true
fix.
It just sorts a shared group_info early. This does not stop corruption.
Every time a thread calls set_groups() on that group_info it will be
sorted again.
The sort algorithm used is the heap sort, and a heap sort always moves
elements in the array around - it does not leave a sorted array
untouched (unlike e.g. the quick sort which doesn't move anything in a
sorted array).
So it is still possible for two calls to groups_sort() to race.
We *need* to move groups_sort() out of set_groups().
Thanks,
NeilBrown
> Also, that patch
> doesn't change behavior of set_groups, and is easier to backport if
> distros relying on older kernels need to do so and change behavior. The
> first suggestion is undergoing tests, and so far we didn't detect any
> new corruptions on auth.unix.gid.
>
>> Maybe it could be done with types.
>
> I changed the interfaces on groups_{alloc,sort} to check. There are some
> extra changes needed in groups_from_user and others to make this viable,
> but I like it and I'll try to make it happen.
>
>> Thanks,
>> NeilBrown
>>
>
> Thanks,
> trbecker
On Tue, Dec 05, 2017 at 07:11:00AM +1100, NeilBrown wrote:
> As we don't seem to be pursuing this possibility is probably isn't very
> important, but I'd like to point out that the original fix isn't a true
> fix.
> It just sorts a shared group_info early. This does not stop corruption.
> Every time a thread calls set_groups() on that group_info it will be
> sorted again.
> The sort algorithm used is the heap sort, and a heap sort always moves
> elements in the array around - it does not leave a sorted array
> untouched (unlike e.g. the quick sort which doesn't move anything in a
> sorted array).
> So it is still possible for two calls to groups_sort() to race.
> We *need* to move groups_sort() out of set_groups().
It must be relatively common to sort an already-sorted array. I wonder
if something like this patch would be worthwhile?
I have deliberately broken this patch so it can't be applied. I haven't
tested it, and for all I know, I got the sign of cmp_func wrong.
diff --git a/lib/sort.c b/lib/sort.c
index d6b7a202b0b6..2b527fde6dad 100644
--- a/lib/sort.c
+++ b/lib/sort.c
@@ -75,7 +75,14 @@ void sort(void *base, size_t num, size_t size,
swap_func = generic_swap;
}
- /* heapify */
+ /* Do not sort an already-sorted array */
+ for (c = 0; c < (n - size); c += size) {
+ if (cmp_func(base + c, base + c + size) < 0)
+ goto heapify;
+ }
+ return;
+
+heapify:
for ( ; i >= 0; i -= size) {
for (r = i; r * 2 + size < n; r = c) {
c = r * 2 + size;
On Tue, Dec 05 2017, Matthew Wilcox wrote:
> On Tue, Dec 05, 2017 at 07:11:00AM +1100, NeilBrown wrote:
>> As we don't seem to be pursuing this possibility is probably isn't very
>> important, but I'd like to point out that the original fix isn't a true
>> fix.
>> It just sorts a shared group_info early. This does not stop corruption.
>> Every time a thread calls set_groups() on that group_info it will be
>> sorted again.
>> The sort algorithm used is the heap sort, and a heap sort always moves
>> elements in the array around - it does not leave a sorted array
>> untouched (unlike e.g. the quick sort which doesn't move anything in a
>> sorted array).
>> So it is still possible for two calls to groups_sort() to race.
>> We *need* to move groups_sort() out of set_groups().
>
> It must be relatively common to sort an already-sorted array. I wonder
> if something like this patch would be worthwhile?
>
> I have deliberately broken this patch so it can't be applied. I haven't
> tested it, and for all I know, I got the sign of cmp_func wrong.
>
> diff --git a/lib/sort.c b/lib/sort.c
> index d6b7a202b0b6..2b527fde6dad 100644
> --- a/lib/sort.c
> +++ b/lib/sort.c
> @@ -75,7 +75,14 @@ void sort(void *base, size_t num, size_t size,
> swap_func = generic_swap;
> }
>
> - /* heapify */
> + /* Do not sort an already-sorted array */
> + for (c = 0; c < (n - size); c += size) {
> + if (cmp_func(base + c, base + c + size) < 0)
> + goto heapify;
> + }
> + return;
> +
> +heapify:
> for ( ; i >= 0; i -= size) {
> for (r = i; r * 2 + size < n; r = c) {
> c = r * 2 + size;
I wondered about this possibility...
It is a clear win from a defensive-programming perspective.
Adding a small overhead to every sort call isn't ideal, but I doubt it
is noticeable (typically 2 or 3 tests I suspect).
I probably wouldn't advocate this approach, but I certainly wouldn't
fight it.
I *do* like the way you changed a comment to a label!
Thanks,
NeilBrown
On Tue, 5 Dec 2017, Matthew Wilcox wrote:
> On Tue, Dec 05, 2017 at 07:11:00AM +1100, NeilBrown wrote:
>> As we don't seem to be pursuing this possibility is probably isn't very
>> important, but I'd like to point out that the original fix isn't a true
>> fix.
>> It just sorts a shared group_info early. This does not stop corruption.
>> Every time a thread calls set_groups() on that group_info it will be
>> sorted again.
>> The sort algorithm used is the heap sort, and a heap sort always moves
>> elements in the array around - it does not leave a sorted array
>> untouched (unlike e.g. the quick sort which doesn't move anything in a
>> sorted array).
>> So it is still possible for two calls to groups_sort() to race.
>> We *need* to move groups_sort() out of set_groups().
Hum, makes sense. I've applied it to the most recent Fedora kernel (that
uses heapsort) and I didn't see the problem again. I should run a few more
repetitions to be sure.
> It must be relatively common to sort an already-sorted array. I wonder
> if something like this patch would be worthwhile?
>
> I have deliberately broken this patch so it can't be applied. I haven't
> tested it, and for all I know, I got the sign of cmp_func wrong.
>
> diff --git a/lib/sort.c b/lib/sort.c
> index d6b7a202b0b6..2b527fde6dad 100644
> --- a/lib/sort.c
> +++ b/lib/sort.c
> @@ -75,7 +75,14 @@ void sort(void *base, size_t num, size_t size,
> swap_func = generic_swap;
> }
>
> - /* heapify */
> + /* Do not sort an already-sorted array */
> + for (c = 0; c < (n - size); c += size) {
> + if (cmp_func(base + c, base + c + size) < 0)
> + goto heapify;
> + }
> + return;
> +
> +heapify:
> for ( ; i >= 0; i -= size) {
> for (r = i; r * 2 + size < n; r = c) {
> c = r * 2 + size;
The bug happens when two threads enter sort_groups for the same
group info in parallel, and one thread starts overwriting values
that another thread may already have "heapified" or sorted.
Thread A Thread B
Enter groups_sort
Enter groups_sort
.
.
.
Return from groups_sort
.
.
.
Return from groups_sort
Wouldn't this patch just make both threads see the structure as unsorted
and sort them?
Thanks,
trbecker
On Tue, Dec 05, 2017 at 09:03:02PM -0200, Thiago Rafael Becker wrote:
> On Tue, 5 Dec 2017, Matthew Wilcox wrote:
> > It must be relatively common to sort an already-sorted array. I wonder
> > if something like this patch would be worthwhile?
>
> The bug happens when two threads enter sort_groups for the same group info
> in parallel, and one thread starts overwriting values that another thread
> may already have "heapified" or sorted.
>
> Thread A Thread B
> Enter groups_sort
> Enter groups_sort
> .
> .
> .
> Return from groups_sort
> .
> .
> .
> Return from groups_sort
>
> Wouldn't this patch just make both threads see the structure as unsorted and
> sort them?
I'm sorry, I wasn't clear. I wasn't commenting on the original bug (and
I believe your analysis to be correct unless there's some locking which
prevents two calls to group_sort from happening at the same time).
I was wondering about whether our sort() implementation is the best that
it could possibly be, and whether having the trait of not modifying an
already-sorted array is worthwhile (eg it would not cause cachelines to
enter the dirty state if they were already clean).
On Tue, Dec 05, 2017 at 07:11:00AM +1100, NeilBrown wrote:
> On Mon, Dec 04 2017, Thiago Rafael Becker wrote:
>
> > On Mon, 4 Dec 2017, NeilBrown wrote:
> >
> >> I think you need to add groups_sort() in a few more places.
> >> Almost anywhere that calls groups_alloc() should be considered.
> >> net/sunrpc/svcauth_unix.c, net/sunrpc/auth_gss/svcauth_gss.c,
> >> fs/nfsd/auth.c definitely need it.
> >
> > So are any other functions that modify group_info. OK, I think I'll
> > implement the type detection below as it helps detecting where these
> > situations are located.
> >
> > This may take some time to make sane. I wonder if we shouldn't
> > accept the first change suggested to fix the corruption detected in
> > auth.unix.gid while I work on a new set of patches.
>
> As we don't seem to be pursuing this possibility is probably isn't very
> important, but I'd like to point out that the original fix isn't a true
> fix.
> It just sorts a shared group_info early. This does not stop corruption.
> Every time a thread calls set_groups() on that group_info it will be
> sorted again.
> The sort algorithm used is the heap sort, and a heap sort always moves
> elements in the array around - it does not leave a sorted array
> untouched (unlike e.g. the quick sort which doesn't move anything in a
> sorted array).
> So it is still possible for two calls to groups_sort() to race.
> We *need* to move groups_sort() out of set_groups().
By the way,
https://bugzilla.kernel.org/show_bug.cgi?id=197887
looks like it might be this bug. They report it started to happen on
upgrade from a 4.10-ish kernel to a 4.13-ish kernel, which would include
the commit (b7b2562f725) that converted groups_sort to a function that
is no longer a no-op in the already-sorted case.
Looks like rpc.mountd just uses getgrouplist(), and I don't think that
guarantees any particular oder. I wonder if it's the case that many
common configurations always pass down an already-sorted list. In that
case this may show up as a 4.13 regression for some users.
--b.
On Tue, Dec 19 2017, J. Bruce Fields wrote:
> On Tue, Dec 05, 2017 at 07:11:00AM +1100, NeilBrown wrote:
>> On Mon, Dec 04 2017, Thiago Rafael Becker wrote:
>>
>> > On Mon, 4 Dec 2017, NeilBrown wrote:
>> >
>> >> I think you need to add groups_sort() in a few more places.
>> >> Almost anywhere that calls groups_alloc() should be considered.
>> >> net/sunrpc/svcauth_unix.c, net/sunrpc/auth_gss/svcauth_gss.c,
>> >> fs/nfsd/auth.c definitely need it.
>> >
>> > So are any other functions that modify group_info. OK, I think I'll
>> > implement the type detection below as it helps detecting where these
>> > situations are located.
>> >
>> > This may take some time to make sane. I wonder if we shouldn't
>> > accept the first change suggested to fix the corruption detected in
>> > auth.unix.gid while I work on a new set of patches.
>>
>> As we don't seem to be pursuing this possibility is probably isn't very
>> important, but I'd like to point out that the original fix isn't a true
>> fix.
>> It just sorts a shared group_info early. This does not stop corruption.
>> Every time a thread calls set_groups() on that group_info it will be
>> sorted again.
>> The sort algorithm used is the heap sort, and a heap sort always moves
>> elements in the array around - it does not leave a sorted array
>> untouched (unlike e.g. the quick sort which doesn't move anything in a
>> sorted array).
>> So it is still possible for two calls to groups_sort() to race.
>> We *need* to move groups_sort() out of set_groups().
>
> By the way,
>
> https://bugzilla.kernel.org/show_bug.cgi?id=197887
>
> looks like it might be this bug. They report it started to happen on
> upgrade from a 4.10-ish kernel to a 4.13-ish kernel, which would include
> the commit (b7b2562f725) that converted groups_sort to a function that
> is no longer a no-op in the already-sorted case.
>
> Looks like rpc.mountd just uses getgrouplist(), and I don't think that
> guarantees any particular oder. I wonder if it's the case that many
> common configurations always pass down an already-sorted list. In that
> case this may show up as a 4.13 regression for some users.
I think the 4.13 patch makes the problem worse, but isn't the only
cause. We had this reported against SLE12 which is based on 3.12 and
doesn't have that patch backported.
Before 4.13 the problem only occurs if getgrouplist() returns an
unsorted list, and if two threads both try to sort this list at the same
time they can corrupt it.
If you are using /etc/passwd and /etc/group, then the order of groups
returned by getgrouplist is the order that the groups were added to
/etc/group (or at least, the order they appear in the file).
This will often be numerical order, but site-local policies could easily
result in a different order.
4.13-stable is EOL and the patch has already been queued for 4.14.8.
Greg tried 4.9 and 4.4, but the patch didn't apply. Is anyone
volunteering to do the backport???
Thanks,
NeilBrown