Fixes for RCU handling of task_struct

Hello!

My earlier code that applies RCU to the task list (in PREEMPT_RT) was missing some rcu_dereference() and rcu_assign_pointer() calls. This patch fixes these problems.

Signed-off-by <[email protected]>

RCU signal handling: send signals RCU-read-locked instead of tasklist_lock read-locked. This is a scalability improvement on SMP and a preemption-latency improvement under PREEMPT_RCU.

Review send_group_sigqueue(int sig, struct sigq

Quoted 12 lines · Ingo Molnar

(quoted diff) +0 -0

@@ -1433,7 +1485,16 @@ send_group_sigqueue(int sig, struct sigq
  	int ret = 0;
 
  	BUG_ON(!(q->flags & SIGQUEUE_PREALLOC));
 -	read_lock(&tasklist_lock);
 +
 +	while(!read_trylock(&tasklist_lock)) {
 +		if (!p->sighand)
 +			return -1;
 +		cpu_relax();
 +	}

This looks kind of ugly and quite unobvious.

What's going on there?

Quoted 16 lines · Andrew Morton

Review send_group_sigqueue(int sig, struct sigq

Quoted 12 lines · Ingo Molnar

(quoted diff) +0 -0

@@ -1433,7 +1485,16 @@ send_group_sigqueue(int sig, struct sigq
    int ret = 0;
 
    BUG_ON(!(q->flags & SIGQUEUE_PREALLOC));
 -  read_lock(&tasklist_lock);
 +
 +  while(!read_trylock(&tasklist_lock)) {
 +          if (!p->sighand)
 +                  return -1;
 +          cpu_relax();
 +  }

This looks kind of ugly and quite unobvious.

Quoted 1 line

What's going on there?

This was discussed in the following thread:

        http://marc.theaimsgroup.com/?l=linux-kernel&m=112756875713008&w=2

Looks like its author asked for it to be withdrawn in favor of Roland's "[PATCH] Call exit_itimers from do_exit, not __exit_signal" patch:

        http://marc.theaimsgroup.com/?l=linux-kernel&m=113008567108608&w=2

My guess is that "Roland" is "Roland McGrath", but I cannot find the referenced patch. Oleg, any enlightenment?

kernel/signal.c +6 -1

@@ -1385,16 +1407,47 @@ send_sigqueue(int sig, struct sigqueue *
 {
        unsigned long flags;
        int ret = 0;
+       struct sighand_struct *sh = p->sighand;
 
        BUG_ON(!(q->flags & SIGQUEUE_PREALLOC));
-       read_lock(&tasklist_lock);
+
+       /*
+        * The rcu based delayed sighand destroy makes it possible to
+        * run this without tasklist lock held. The task struct itself
+        * cannot go away as create_timer did get_task_struct().

include/linux/sched.h +3 -0

+static inline int get_task_struct_rcu(struct task_struct *t)
+{
+       int oldusage;

Quoted 24 lines · Paul E. McKenney

Quoted 16 lines · Andrew Morton

Review send_group_sigqueue(int sig, struct sigq

Quoted 12 lines · Ingo Molnar

(quoted diff) +0 -0

@@ -1433,7 +1485,16 @@ send_group_sigqueue(int sig, struct sigq
    int ret = 0;
 
    BUG_ON(!(q->flags & SIGQUEUE_PREALLOC));
 -  read_lock(&tasklist_lock);
 +
 +  while(!read_trylock(&tasklist_lock)) {
 +          if (!p->sighand)
 +                  return -1;
 +          cpu_relax();
 +  }

This looks kind of ugly and quite unobvious.

Quoted 1 line

What's going on there?

This was discussed in the following thread:

        http://marc.theaimsgroup.com/?l=linux-kernel&m=112756875713008&w=2

Quoted 7 lines

Looks like its author asked for it to be withdrawn in favor of Roland's "[PATCH] Call exit_itimers from do_exit, not __exit_signal" patch:

        http://marc.theaimsgroup.com/?l=linux-kernel&m=113008567108608&w=2

My guess is that "Roland" is "Roland McGrath", but I cannot find the referenced patch. Oleg, any enlightenment?

Yes, it was from Roland McGrath:

	http://kernel.org/git/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commit;h=25f407f0b668f5e4ebd5d13e1fb4306ba6427ead

So I think you can remove ->sighand == NULL re-check and do s/read_trylock/read_lock/. Posix timers are destroyed from do_exit()->exit_itimers(), after that nobody can send SI_TIMER to this dying thread group (even if cpu-timer was attached to another process).

send_sigqueue() is different,

Quoted 20 lines

kernel/signal.c +12 -1

@@ -1385,16 +1407,47 @@ send_sigqueue(int sig, struct sigqueue *
 {
        unsigned long flags;
        int ret = 0;
+       struct sighand_struct *sh = p->sighand;
 
        BUG_ON(!(q->flags & SIGQUEUE_PREALLOC));
-       read_lock(&tasklist_lock);
+
+       /*
+        * The rcu based delayed sighand destroy makes it possible to
+        * run this without tasklist lock held. The task struct itself
+        * cannot go away as create_timer did get_task_struct().
+        *
+        * We return -1, when the task is marked exiting, so
+        * posix_timer_event can redirect it to the group leader
+        *
+        */
+       rcu_read_lock();
 

kernel/signal.c send_sigqueue(int sig, struct sigqueue * · line 1427

Quoted 3 lines

kernel/signal.c +0 -0

        if (unlikely(p->flags & PF_EXITING)) {
                ret = -1;
                goto out_err;

Is it really needed? You are doing this check again below.

kernel/signal.c send_sigqueue(int sig, struct sigqueue * · line 1430

Quoted 2 lines

kernel/signal.c +1 -1

-       spin_lock_irqsave(&p->sighand->siglock, flags);
+       spin_lock_irqsave(&sh->siglock, flags);

But 'sh' can be NULL, no? Yes, you already checked PF_EXITING, so this is very unlikely, but I think it is still possible in theory. 'sh' was loaded before reading p->flags, but rcu_read_lock() does not imply memory barrier.

Paul, currently I have no time to read the patch carefully, so probably this all is my misunderstanding.

kernel/signal.c void __exit_signal(struct task_struct *t · line 363

Quoted 6 lines

kernel/signal.c +1 -0

@@ -352,6 +359,7 @@ void __exit_signal(struct task_struct *t
                BUG();
        if (!atomic_read(&sig->count))
                BUG();
+       rcu_read_lock();
        spin_lock(&sighand->siglock);

Why rcu_read_lock() here?

Quoted 8 lines

include/linux/sched.h +8 -0

+static inline int get_task_struct_rcu(struct task_struct *t)
+{
+       int oldusage;
+
+       do {
+               oldusage = atomic_read(&t->usage);
+               if (oldusage == 0) {
+                       return 0;

include/linux/sched.h static inline int pid_alive(struct task_ · line 962

Quoted 6 lines

include/linux/sched.h +5 -0

+               }
+       } while (cmpxchg(&t->usage.counter,
+                oldusage, oldusage + 1) != oldusage);
+       return 1;
+}

I still don't understand the purpose of get_task_struct_rcu().

Quoted 7 lines

kernel/signal.c send_sigqueue(int sig, struct sigqueue * · line 1430

Quoted 3 lines

kernel/signal.c +1 -1

-       spin_lock_irqsave(&p->sighand->siglock, flags);
+       spin_lock_irqsave(&sh->siglock, flags);

But 'sh' can be NULL, no? Yes, you already checked PF_EXITING, so this is very unlikely, but I think it is still possible in theory. 'sh' was loaded before reading p->flags, but rcu_read_lock() does not imply memory barrier.

'sh' cannot be NULL, because the caller holds ->it_lock and has checked for timer deletion under that lock, and because the exiting process quiesces and deletes timers before freeing sighand.

Quoted 11 lines · Paul E. McKenney

Quoted 7 lines

Review

Quoted 3 lines

(quoted diff) +1 -1

-       spin_lock_irqsave(&p->sighand->siglock, flags);
+       spin_lock_irqsave(&sh->siglock, flags);

But 'sh' can be NULL, no? Yes, you already checked PF_EXITING, so this is very unlikely, but I think it is still possible in theory. 'sh' was loaded before reading p->flags, but rcu_read_lock() does not imply memory barrier.

'sh' cannot be NULL, because the caller holds ->it_lock and has checked for timer deletion under that lock, and because the exiting process quiesces and deletes timers before freeing sighand.

               ^^^^^^^^^^^^^^

Exiting process (thread group) - yes, but exiting thread - no. That is why send_sigqueue() should check that the target thread is not exiting now. If we do not take tasklist_lock we can't be sure that ->sighand != NULL. The caller holds ->it_lock, yes, but this can't help.

Please don't be confused by the 'posix_cpu_timers_exit(tsk)' in __exit_signal() which is called under sighand->siglock before clearing ->signal/->sighand. This is completely different, it detaches (but not destroys) cpu-timers, these timers can have another thread/process as a target for signal sending.

So the idea is to error out of send_sigqueue() so that posix_timer_event() will instead call send_group_sigqueeue(). But that could suffer from the same race if the new leader thread also exits -- or if the exiting thread was the leader thread to begin with.

But once send_group_sigqueue() read-acquires tasklist_lock, threads and processes must stay put. So it should be possible to follow the ->group_leader chain at that point.

Except that the group leader could do an exec(), right? If it does so, it must do so before tasklist_lock is read-acquired. So the nightmare case is where all but one thread exits, and then that one thread does and exec().

If this case can really happen, we want to drop the signal on the floor, right?

...

RCU signal handling: send signals RCU-read-locked instead of tasklist_lock read-locked. This is a scalability improvement on SMP and a preemption-latency improvement under PREEMPT_RCU.

Signed-off-by Paul E. McKenney <[email protected]>

Signed-off-by Ingo Molnar <[email protected]>

...

include/linux/sched.h +3 -0

+static inline int get_task_struct_rcu(struct task_struct *t)
+{
+	int oldusage;

Quoted 14 lines · Ingo Molnar

...

RCU signal handling: send signals RCU-read-locked instead of tasklist_lock read-locked. This is a scalability improvement on SMP and a preemption-latency improvement under PREEMPT_RCU.

Signed-off-by Paul E. McKenney <[email protected]>

Signed-off-by Ingo Molnar <[email protected]>

...

(quoted diff) +3 -0

+static inline int get_task_struct_rcu(struct task_struct *t)
+{
+	int oldusage;

Review

Quoted 10 lines

(quoted diff) +10 -0

+
+	do {
+		oldusage = atomic_read(&t->usage);
+		if (oldusage == 0) {
+			return 0;
+		}
+	} while (cmpxchg(&t->usage.counter,
+		 oldusage, oldusage + 1) != oldusage);
+	return 1;
+}

arm (at least) does not implement cmpxchg.

I think Nick is working on patches which implement cmpxchg on all architectures?

Quoted 5 lines · Paul E. McKenney

So the idea is to error out of send_sigqueue() so that posix_timer_event() will instead call send_group_sigqueeue(). But that could suffer from the same race if the new leader thread also exits -- or if the exiting thread was the leader thread to begin with.

The case when leader exits is ok. If it is the only (last) thread - it will call exit_itimers(). If not - it (or sys_wait4 from parent) will not call release_task(), but will stay TASK_ZOMBIE with valid ->signal/sighand until the last thread in same thread group exits (and call exit_itimers).

Quoted 3 lines

But once send_group_sigqueue() read-acquires tasklist_lock, threads and processes must stay put. So it should be possible to follow the ->group_leader chain at that point.

Not quite so, I think. See below.

Quoted 4 lines

Except that the group leader could do an exec(), right? If it does so, it must do so before tasklist_lock is read-acquired. So the nightmare case is where all but one thread exits, and then that one thread does and exec().

... and that thread is not group leader. Actually, it does not matter if other threads exited or not, execing thread will kill other threads.

Quoted 2 lines

If this case can really happen, we want to drop the signal on the floor, right?

I think yes.

Quoted 5 lines

diff -urpNa -X dontdiff linux-2.6.14-mm0-fix/kernel/signal.c linux-2.6.14-mm0-fix-2/kernel/signal.c

kernel/signal.c 2005-11-05 15:05:38.000000000 -0800 renamed from kernel/signal.c 2005-11-04 17:23:40.000000000 -0800 +0 -0

@@ -1408,6 +1408,11 @@ send_sigqueue(int sig, struct sigqueue *
 

kernel/signal.c 2005-11-05 15:05:38.000000000 -0800 send_sigqueue(int sig, struct sigqueue * · line 1415

Quoted 7 lines

kernel/signal.c 2005-11-05 15:05:38.000000000 -0800 renamed from kernel/signal.c 2005-11-04 17:23:40.000000000 -0800 +5 -0

 retry:
        sh = rcu_dereference(p->sighand);
+       if (sh == NULL) {
+               /* We raced with pthread_exit()... */
+               ret = -1;
+               goto out_err;
+       }

I lost the plot. Because I can't apply this and previous patches (rejects) and can't imagine how send_sigqueue() looks now. I think this is ok, but we also need to re-check ->signal != NULL after lock(->sighand) or check PF_EXITING (iirc ve do have such check).

kernel/signal.c 2005-11-05 15:05:38.000000000 -0800 send_group_sigqueue(int sig, struct sigq · line 1483

Quoted 7 lines

kernel/signal.c 2005-11-05 15:05:38.000000000 -0800 renamed from kernel/signal.c 2005-11-04 17:23:40.000000000 -0800 +2 -1

@@ -1474,7 +1479,8 @@ send_group_sigqueue(int sig, struct sigq
        BUG_ON(!(q->flags & SIGQUEUE_PREALLOC));
 
        read_lock(&tasklist_lock);
-       /* Since it_lock is held, p->sighand cannot be NULL. */
+       while (p->group_leader != p)
+               p = p->group_leader;

No, this is definitely not right. de_thread() does not change leader->group_leader when non-leader execs, so p->group_leader == p always.

Quoted 8 lines

include/linux/sched.h +8 -0

+static inline int get_task_struct_rcu(struct task_struct *t)
+{
+	int oldusage;
+
+	do {
+		oldusage = atomic_read(&t->usage);
+		if (oldusage == 0) {
+			return 0;

include/linux/sched.h static inline int pid_alive(struct task_ · line 962

Quoted 5 lines

include/linux/sched.h +5 -0

+		}
+	} while (cmpxchg(&t->usage.counter,
+		 oldusage, oldusage + 1) != oldusage);
+	return 1;
+}

arm (at least) does not implement cmpxchg.

I think Nick is working on patches which implement cmpxchg on all architectures?

Quoted 8 lines · Andrew Morton

Quoted 8 lines

include/linux/sched.h +8 -0

+static inline int get_task_struct_rcu(struct task_struct *t)
+{
+	int oldusage;
+
+	do {
+		oldusage = atomic_read(&t->usage);
+		if (oldusage == 0) {
+			return 0;

Quoted 9 lines

include/linux/sched.h static inline int pid_alive(struct task_ · line 962

Quoted 5 lines

include/linux/sched.h +5 -0

+		}
+	} while (cmpxchg(&t->usage.counter,
+		 oldusage, oldusage + 1) != oldusage);
+	return 1;
+}

arm (at least) does not implement cmpxchg.

Yes, and using atomic_t.counter in generic code is ugly, albeit compatible with all current implementations.

Quoted 2 lines

I think Nick is working on patches which implement cmpxchg on all architectures?

Yes, it is basically ready to go.

Quoted 1 line · Nick Piggin

Yes, it is basically ready to go.

Would it simplify the rcuref.h code? Or lib/dec_and_lock.c?

Quoted 6 lines

kernel/signal.c send_group_sigqueue(int sig, struct sigq · line 1483

Quoted 3 lines

kernel/signal.c +2 -0

+       while (p->group_leader != p)
+               p = p->group_leader;

No, this is definitely not right. de_thread() does not change leader->group_leader when non-leader execs, so p->group_leader == p always.

This was intended for the case where the group leader does pthread_exit, which would cause some other thread to assume group leadership. Or am I missing something from that code path? (Quite likely that I am...)

When group leader exits it goes into TASK_ZOMBIE state (if it is not the only one thread in the same group).

So, I think send_group_sigqueue() should do:

        read_lock(tasklist_lock);

        if (!tsk->signal) {
                // Can happen only if de_thread did release_task(tsk)
                // while switching to new leader.
                // We can't figure out the new leader, but it does not
                // matter - we should drop the signal anyway.
                unlock(tasklist);
                return;

Quoted 5 lines · Paul E. McKenney

Quoted 1 line · Nick Piggin

Yes, it is basically ready to go.

Would it simplify the rcuref.h code? Or lib/dec_and_lock.c?

Yep, I recently posted it to lkml... rcuref.h disappears, and dec_and_lock becomes simplified not to mention more efficient on those architectures which do not define HAVE_ARCH_CMPXCHG.

http://marc.theaimsgroup.com/?l=linux-kernel&m=113117753625350&w=2
http://marc.theaimsgroup.com/?l=linux-kernel&m=113117753629218&w=2

I need the infrastructure for lockless pagecache, but fortunately it is very useful for other things as well. Especially lockless algorithms it seems.