Message-ID: <m1pr6npkjp.fsf@fess.ebiederm.org>
Date:	Wed, 09 Dec 2009 19:36:26 -0800
From:	ebiederm@...ssion.com (Eric W. Biederman)
To:	Oleg Nesterov <oleg@...hat.com>
Cc:	Linus Torvalds <torvalds@...ux-foundation.org>,
	Thomas Gleixner <tglx@...utronix.de>,
	Peter Zijlstra <peterz@...radead.org>,
	Ingo Molnar <mingo@...e.hu>,
	Christoph Hellwig <hch@...radead.org>,
	Nick Piggin <npiggin@...e.de>,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
Subject: Re: [rfc] "fair" rw spinlocks

Oleg Nesterov <oleg@...hat.com> writes:

> On 12/07, Eric W. Biederman wrote:
>>
>> Oleg Nesterov <oleg@...hat.com> writes:
>>
>> > On 12/05, Eric W. Biederman wrote:
>> >>
>> >> Atomically sending signal to every member of a process group, is the
>> >> big fly in the ointment I am aware of.  Last time I looked I could
>> >> not see how to convert it rcu.
>> >
>> > I am not sure, but iirc we can do this lockless (under rcu_lock).
>> > We need to modify pid_link to use list_entry and attach_pid() should
>> > add the new task to the end. Of course we need more changes, but
>> > (again iirc) this is not too hard.
>>
>> The problem is that even adding to the end of the list, we could run
>> into a deleted entry and not see the new end of the list.
>>
>> Suppose when we start iterating the list we have:
>>
>>   A -> B -> C -> D
>>
>> Then someone deletes some of the entries while we are iterating the list.
>>
>> A ->
>>  B' -> C' -> D'
>>
>> We will continue on traversing through the deleted entries.
>>
>> Then someone adds a new entry to the end of the list.
>>
>> A-> N
>>
>> Since we are at B', C' or D' we will never see the new entry on the
>> end of the list.
>
> Yes, but who can add the new entry?
>
> Let's forget about setpgrp/etc for the moment, I think we have "races"
> with or without tasklist. Say, setpgrp() can add the new process to the
> already "killed" pgrp.

Agreed. A setpgrp call that we miss can be considered to have happened
after the signal was sent to the process group.

> Then, I think the only important case is SIGKILL/SIGSTOP (or other
> signals which can't be blockes/ignored). We must kill/stop the entire
> pgrp, we must not race with fork() and miss a child.
>
> In this case I _think_ rcu_read_lock() is enough,
>
> 	rcu_read_lock()
>
> 	list_for_each_entry_rcu(task, pid->tasks[PIDTYPE_PGID)
> 		group_send_sig_info(sig, task);
>
> 	rcu_read_unlock();
>
> except group_send_sig_info() can race with mt-exec, but this is simple
> to fix.

After we change the code to always add new entries to the end of
the rcu list you are correct.

The danger I saw is having a new process ( that we must handle ) show
up while we have gotten into a rcu cul-de-sac of the process list,
where we do not see new processes added to the end.

Once a process has gotten a signal we don't care, any children it spawns
happen after the signal was sent.

So we only care about children for processes that we have not delivered
the signal to.  If we add children to the end of the list they will be
visible if you traverse through the parent.  Since we have not traversed
through the parent and delivered the signal (by definition) then we don't
care.

This works for all signals, and especially for SIGKILL and SIGSTOP.

I am tempted to apply the test that if user space can prove the ordering
is not what is expected than there is a problem.  However signals have
not always arrived strongly orders with other user space events, and
the tasklist lock today does not appear to preclude a task that has
received a signal from talking to a task that has not yet received a
signal via pipes, etc.  

So as long as we can guarantee that if you traverse a parent you will
also traverse all of the children forked before you traversed the
parent, then we should be fine.


> If we send a signal (not necessary SIGKILL) to a process P, we must see
> all childs which were forked by P, both send_signal() and copy_process()
> take the same ->siglock, we must see the result of list_add_tail_rcu().
> And, after we sent SIGKILL/SIGSTOP, it can't fork the new child.

Sounds right.

> If list_for_each_entry() does not see the exited process P, this means
> we see the result of list_del_rcu(). But this also means we must the
> the result of the previous list_add_rcu().
>
> IOW, fork+exit means list_add_rcu() + wmb() + list_del_rcu(), if we
> don't see the new entry on list, we must see the new one, right?
>
> (I am ignoring the case when list_for_each_entry_rcu() sees a process
>  P but lock_task_sighand(P) fails, I think this is the same as if we
>  we missed P)
>
> Now suppose a signal is blocked/ignored or has a handler. In this case
> we can miss a child, but I think this is OK, we can pretend the new
> child was forked after kill_pgrp() completes. Say, this child C was
> forked by some process P. We can miss C only if it was forked after
> we already sent the signal to P.

I don't see how we can miss a child that matters.

> However. I do not pretend the reasoning above is "complete", and
> perhaps I missed something else.

I can not find fault with your idea.

Eric
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Powered by blists - more mailing lists