[RFC] Race condition?

[RFC] Race condition?

[Kasper Dupont]

Is there a race condition in this piece of code from do_fork in
linux/kernel/fork.c? I cannot see what prevents two processes
from calling this at the same time and both successfully fork
even though the user had only one process left.

        if (atomic_read(&p->user->processes) >= p->rlim[RLIMIT_NPROC].rlim_cur
                      && !capable(CAP_SYS_ADMIN) && !capable(CAP_SYS_RESOURCE))
                goto bad_fork_free;

        atomic_inc(&p->user->__count);
        atomic_inc(&p->user->processes);

-- 
Kasper Dupont -- der bruger for meget tid på usenet.
For sending spam use mailto:razrep@daimi.au.dk
or mailto:mcxumhvenwblvtl@skrammel.yaboo.dk

Re: [RFC] Race condition?

[Oliver Neukum]

Am Freitag, 2. August 2002 15:46 schrieb Kasper Dupont:
> Is there a race condition in this piece of code from do_fork in

It would seem so. Perhaps the BKL was taken previously.

	Regards
		Oliver

Re: [RFC] Race condition?

[Dave Hansen]

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

Kasper Dupont wrote:
> Is there a race condition in this piece of code from do_fork in
> linux/kernel/fork.c? I cannot see what prevents two processes
> from calling this at the same time and both successfully fork
> even though the user had only one process left.
> 
>         if (atomic_read(&p->user->processes) >= p->rlim[RLIMIT_NPROC].rlim_cur
>                       && !capable(CAP_SYS_ADMIN) && !capable(CAP_SYS_RESOURCE))
>                 goto bad_fork_free;
> 
>         atomic_inc(&p->user->__count);
>         atomic_inc(&p->user->processes);

I don't see any locking in the call chain leading to this function, so 
I think you're right.  The attached patch fixes this.  It costs an 
extra 2 atomic ops in the failure case, but otherwise just makes the 
processes++ operation earlier.

Patch is against 2.5.27, but applies against 30.
-- 
Dave Hansen
haveblue@us.ibm.com

[-- Attachment #2: fork-up-race-2.5.27.patch --]
[-- Type: text/plain, Size: 672 bytes --]

--- linux-2.5.27-clean/kernel/fork.c	Sat Jul 20 12:11:07 2002
+++ linux/kernel/fork.c	Fri Aug  2 09:35:17 2002
@@ -628,13 +628,15 @@
 		goto fork_out;
 
 	retval = -EAGAIN;
-	if (atomic_read(&p->user->processes) >= p->rlim[RLIMIT_NPROC].rlim_cur) {
-		if (!capable(CAP_SYS_ADMIN) && !capable(CAP_SYS_RESOURCE))
+	atomic_inc(&p->user->processes);
+	if (atomic_read(&p->user->processes) > p->rlim[RLIMIT_NPROC].rlim_cur) {
+		if (!capable(CAP_SYS_ADMIN) && !capable(CAP_SYS_RESOURCE)) {
+			atomic_dec(&p->user->processes);
 			goto bad_fork_free;
+		}
 	}
 
 	atomic_inc(&p->user->__count);
-	atomic_inc(&p->user->processes);
 
 	/*
 	 * Counter increases are protected by

Re: [RFC] Race condition?

[Kasper Dupont]

Oliver Neukum wrote:
> 
> Am Freitag, 2. August 2002 15:46 schrieb Kasper Dupont:
> > Is there a race condition in this piece of code from do_fork in
> 
> It would seem so. Perhaps the BKL was taken previously.

I guess you are right. Looking closer on the following lines
I find a comment stating that nr_threads is protected by the
kernel lock, but I don't see a lock_kernel() anywhere in this
code. How about the next code using the nr_threads variable,
is that safe?

-- 
Kasper Dupont -- der bruger for meget tid på usenet.
For sending spam use mailto:razrep@daimi.au.dk
or mailto:mcxumhvenwblvtl@skrammel.yaboo.dk

Re: [RFC] Race condition?

[Dave Hansen]

Oliver Neukum wrote:
> Am Freitag, 2. August 2002 15:46 schrieb Kasper Dupont:
> 
>>Is there a race condition in this piece of code from do_fork in
> 
> It would seem so. Perhaps the BKL was taken previously.
> 

Even if it was, I doubt the code ever knowingly relied upon it.  If I 
know that I'm protected under a lock, I rarely go to the trouble of 
atomic operations.

The root of the problem is that the reference count is being relied on 
for the wrong thing.  There is a race on p->user between the
dup_task_struct() and whenever the atomic_inc(&p->user->__count) 
occcurs.   The user reference count needs to be incremented in 
dup_task_struct(), before the copy occurs.
-- 
Dave Hansen
haveblue@us.ibm.com

Re: [RFC] Race condition?

[Oliver Neukum]

Am Freitag, 2. August 2002 19:00 schrieb Dave Hansen:
> Kasper Dupont wrote:
> > Is there a race condition in this piece of code from do_fork in
> > linux/kernel/fork.c? I cannot see what prevents two processes
> > from calling this at the same time and both successfully fork
> > even though the user had only one process left.
> >
> >         if (atomic_read(&p->user->processes) >=
> > p->rlim[RLIMIT_NPROC].rlim_cur && !capable(CAP_SYS_ADMIN) &&
> > !capable(CAP_SYS_RESOURCE)) goto bad_fork_free;
> >
> >         atomic_inc(&p->user->__count);
> >         atomic_inc(&p->user->processes);
>
> I don't see any locking in the call chain leading to this function, so
> I think you're right.  The attached patch fixes this.  It costs an
> extra 2 atomic ops in the failure case, but otherwise just makes the
> processes++ operation earlier.
>
> Patch is against 2.5.27, but applies against 30.

It has the opposite failure mode. Forks only some of which should
succeed may all fail.

	Regards
		Oliver

Re: [RFC] Race condition?

[Oliver Neukum]

Am Freitag, 2. August 2002 19:37 schrieb Dave Hansen:
> Oliver Neukum wrote:
> > Am Freitag, 2. August 2002 15:46 schrieb Kasper Dupont:
> >>Is there a race condition in this piece of code from do_fork in
> >
> > It would seem so. Perhaps the BKL was taken previously.
>
> Even if it was, I doubt the code ever knowingly relied upon it.  If I
> know that I'm protected under a lock, I rarely go to the trouble of
> atomic operations.

That depends on where else you need these variables.

> The root of the problem is that the reference count is being relied on
> for the wrong thing.  There is a race on p->user between the
> dup_task_struct() and whenever the atomic_inc(&p->user->__count)
> occcurs.   The user reference count needs to be incremented in
> dup_task_struct(), before the copy occurs.

I don't get you. The user_struct can hardly go away while we are
forking.

IMHO you should add a spinlock to user_struct and take it.
A clear solution that doesn't hurt the common case.

	Regards
		Oliver

Re: [RFC] Race condition?

[Dave Hansen]

Oliver Neukum wrote:
> Am Freitag, 2. August 2002 19:00 schrieb Dave Hansen:
> 
>>Kasper Dupont wrote:
>>
>>>Is there a race condition in this piece of code from do_fork in
>>>linux/kernel/fork.c? I cannot see what prevents two processes
>>>from calling this at the same time and both successfully fork
>>>even though the user had only one process left.
>>>
>>>        if (atomic_read(&p->user->processes) >=
>>>p->rlim[RLIMIT_NPROC].rlim_cur && !capable(CAP_SYS_ADMIN) &&
>>>!capable(CAP_SYS_RESOURCE)) goto bad_fork_free;
>>>
>>>        atomic_inc(&p->user->__count);
>>>        atomic_inc(&p->user->processes);
>>
>>I don't see any locking in the call chain leading to this function, so
>>I think you're right.  The attached patch fixes this.  It costs an
>>extra 2 atomic ops in the failure case, but otherwise just makes the
>>processes++ operation earlier.
>>
>>Patch is against 2.5.27, but applies against 30.
> 
> It has the opposite failure mode. Forks only some of which should
> succeed may all fail.

You beat me to it.  I haven't had a chance to test it yet.

 >>>        if (atomic_read(&p->user->processes) >=
 >>>p->rlim[RLIMIT_NPROC].rlim_cur && !capable(CAP_SYS_ADMIN) &&
 >>>!capable(CAP_SYS_RESOURCE)) goto bad_fork_free;
-- 
Dave Hansen
haveblue@us.ibm.com

Re: [RFC] Race condition?

[Oliver Neukum]

Am Freitag, 2. August 2002 19:13 schrieb Kasper Dupont:
> Oliver Neukum wrote:
> > Am Freitag, 2. August 2002 15:46 schrieb Kasper Dupont:
> > > Is there a race condition in this piece of code from do_fork in
> >
> > It would seem so. Perhaps the BKL was taken previously.
>
> I guess you are right. Looking closer on the following lines
> I find a comment stating that nr_threads is protected by the
> kernel lock, but I don't see a lock_kernel() anywhere in this
> code. How about the next code using the nr_threads variable,
> is that safe?

No, it isn't either.
In fact you can even lose updates as it isn't atomic_t.

	Regards
		Oliver

Re: [RFC] Race condition?

[Dave Hansen]

The failure is because 0 means no limit.
limit==0
processes==0
processes++
processes > limit

I'll have a patch generated in a couple of minutes.

-- 
Dave Hansen
haveblue@us.ibm.com

Re: [RFC] Race condition?

[Dave Hansen]

Oliver Neukum wrote:
>>The root of the problem is that the reference count is being relied on
>>for the wrong thing.  There is a race on p->user between the
>>dup_task_struct() and whenever the atomic_inc(&p->user->__count)
>>occcurs.   The user reference count needs to be incremented in
>>dup_task_struct(), before the copy occurs.
> 
> I don't get you. The user_struct can hardly go away while we are
> forking.

Good point.  I was figuring that it could disappear when the task 
clearly can't be exiting or setuid'ing while forking.

> IMHO you should add a spinlock to user_struct and take it.
> A clear solution that doesn't hurt the common case.

That _is_ a pretty clear solution.  It looks like there are grand 
plans for struct user, so it might come in handy in the future.  But, 
a spinlock _will_ hurt the common case.  With the atomic incs, we have 
2 of them in the common case and, at most, 4 in the failure case. 
Adding a spinlock will require more lock instructions, which are the 
most costly operations in either a spinlock or atomic op.

Either of these are _incredibly_ small prices to pay in any case. 
Forks are slow anyway.  A spinlock would be just fine with me.
-- 
Dave Hansen
haveblue@us.ibm.com

Re: [RFC] Race condition?

[Keith Owens]

On Fri, 02 Aug 2002 10:00:13 -0700, 
Dave Hansen <haveblue@us.ibm.com> wrote:
>Kasper Dupont wrote:
>> Is there a race condition in this piece of code from do_fork in
>> linux/kernel/fork.c? I cannot see what prevents two processes
>> from calling this at the same time and both successfully fork
>> even though the user had only one process left.
>> 
>>         if (atomic_read(&p->user->processes) >= p->rlim[RLIMIT_NPROC].rlim_cur
>>                       && !capable(CAP_SYS_ADMIN) && !capable(CAP_SYS_RESOURCE))
>>                 goto bad_fork_free;
>> 
>>         atomic_inc(&p->user->__count);
>>         atomic_inc(&p->user->processes);
>
>I don't see any locking in the call chain leading to this function, so 
>I think you're right.  The attached patch fixes this.  It costs an 
>extra 2 atomic ops in the failure case, but otherwise just makes the 
>processes++ operation earlier.

Does this race really justify extra locks?  AFAICT the worst case is
that a user can go slightly over their RLIMIT_NPROC, and that will only
occur if they fork on multiple cpus "at the same time".  Given the
timing constraints on that small window, I would be surprised if this
race could be exploited to gain more than a couple of extra processes.
This looks like a case where close enough is good enough.

Re: [RFC] Race condition?

[Keith Owens]

On Sat, 3 Aug 2002 12:08:28 +0200, 
Oliver Neukum <Oliver.Neukum@lrz.uni-muenchen.de> wrote:
>Hi,
>
>> >I don't see any locking in the call chain leading to this function, so
>> >I think you're right.  The attached patch fixes this.  It costs an
>> >extra 2 atomic ops in the failure case, but otherwise just makes the
>> >processes++ operation earlier.
>>
>> Does this race really justify extra locks?  AFAICT the worst case is
>> that a user can go slightly over their RLIMIT_NPROC, and that will only
>> occur if they fork on multiple cpus "at the same time".  Given the
>
>Only if preempt is not enabled.

Preempt is irrelevant here.  To make any difference, there would have
to be an interrupt in the window between reading and updating
p->user->processes _and_ another process would have to be waiting to
enter fork().  Even if that occurred, the result is the user is one
process over their limit, big deal.

>> timing constraints on that small window, I would be surprised if this
>> race could be exploited to gain more than a couple of extra processes.
>> This looks like a case where close enough is good enough.
>
>There's no such thing as a tolerable race :-)

The result is just a slightly elevated process count in rare cases.
Even then it is self correcting.  It is not a significant race, just a
bit of fuzzy counting.

>Anyway this code can corrupt the global variable nr_threads.
>Without the BKL it is buggy, so it has to be fixed anyway and we
>can do it right.

nr_threads is protected by tasklist_lock.  How on earth can fuzzy
counting on user->processes corrupt nr_threads?

Re: [RFC] Race condition?

[Keith Owens]

On Sat, 03 Aug 2002 21:07:11 +1000, 
Keith Owens <kaos@ocs.com.au> wrote:
>On Sat, 3 Aug 2002 12:08:28 +0200, 
>Oliver Neukum <Oliver.Neukum@lrz.uni-muenchen.de> wrote:
>>Anyway this code can corrupt the global variable nr_threads.
>>Without the BKL it is buggy, so it has to be fixed anyway and we
>>can do it right.
>
>nr_threads is protected by tasklist_lock.  How on earth can fuzzy
>counting on user->processes corrupt nr_threads?

Never mind.  Checking and updating nr_threads is a seperate race from
the one on user->processes.  The nr_threads race is a problem that
needs to be fixed.