Improve signal delivery scalability

From: Matt Fleming <[email protected]>

This series is most definitely RFC material. At this early stage I'm just asking for feedback on whether the concepts/ideas are sound. For example, I'm fairly sure that these patches break ia64 because it accesses tsk->pending in asm and I haven't had time to look closely at that yet.

This patch series was motivated by the signal1_threads testcase from the Will It Scale benchmark suite. Currently, signal generation and delivery in a thread group is serialised by the thread group's siglock, tsk->sighand->siglock. This lock is a huge point of contention in multithreaded applications, even when sending a signal to one thread in a thread group.

In light of this, this patch series tries to improve scalability by,

- introducing a per-thread siglock to protect the per-thread pending signal queue

- avoiding acquiring the shared siglock wherever possible

- using a rwlock to protect signal handlers

This series is based on the assumption that it is OK to acquire and release the shared siglock across function calls and do things like execute PENDING() without holding any locks.

The improvement on the "signal delivery" testcase can be seen here,
http://userweb.kernel.org/~mfleming/will-it-scale/signals-per-thread-siglock/

Tejun, these patches are based on your ptrace branch as both you and Oleg have touched alot of the same code paths lately.

All comments appreciated!

Matt Fleming (5):
signals: Always place SIGCONT and SIGSTOP on 'shared_pending'
signals: Introduce per-thread siglock and action rwlock
ia64: Catch up with new sighand action spinlock
signals: Introduce __dequeue_private_signal helper function
signals: Don't hold shared siglock across signal delivery

 arch/ia64/kernel/signal.c |   13 +--
 fs/autofs4/waitq.c        |    2 +
 fs/exec.c                 |    2 +
 fs/signalfd.c             |    7 +-
 include/linux/init_task.h |    2 +
 include/linux/sched.h     |    4 +
 include/linux/signal.h    |    5 +
 include/linux/tracehook.h |    3 +-
 kernel/compat.c           |    7 +-
 kernel/exit.c             |   12 +-
 kernel/fork.c             |    2 +
 kernel/kmod.c             |    8 +-
 kernel/ptrace.c           |    4 +-
 kernel/signal.c           |  429 +++++++++++++++++++++++++++++++++------------
 security/selinux/hooks.c  |    6 +-
 15 files changed, 360 insertions(+), 146 deletions(-)

1.7.4

From: Matt Fleming <[email protected]>

Because SIGCONT and SIGSTOP affect an entire thread group, we can place them on the 'shared_pending' queue. This means that we no longer have to iterate over every thread in a thread group to remove SIGCONT/SIGSTOP signals from their private 'pending' queues.

SIGCONT and SIGSTOP signals are now only placed on the shared queue and not on the private so queue we need to prevent them from being starved of service. We need to prioritize signals on the shared queue over signals on the private queue. For example, if we don't do this there's potential for a task to keep handling private signals even though they were delivered _after_ a SIGSTOP. Note that POSIX does not mandate any kind of priority between signals to a thread group or a specific thread, so this change in behaviour should be safe.

This is an optimization to reduce the amount of code that we execute while holding ->siglock, and is preparation for introducing a per-thread siglock for modifying the private signal queue.

---
 kernel/signal.c |  123 +++++++++++++++++++++++++++++++++++--------------------
 1 files changed, 79 insertions(+), 44 deletions(-)

index 4f7312b..9595d86 100644
@@ -545,51 +545,41 @@ static int __dequeue_signal(struct sigpending *pending, sigset_t *mask,
 }
 
 /*
- * Dequeue a signal and return the element to the caller, which is 
- * expected to free it.
- *
- * All callers have to hold the siglock.
+ * All callers must hold tsk->sighand->siglock.
  */
-int dequeue_signal(struct task_struct *tsk, sigset_t *mask, siginfo_t *info)
+static int __dequeue_shared_signal(struct task_struct *tsk,
+				   sigset_t *mask, siginfo_t *info)
 {
 	int signr;
 
-	/* We only dequeue private signals from ourselves, we don't let
-	 * signalfd steal them
+	assert_spin_locked(&tsk->sighand->siglock);
+
+	signr = __dequeue_signal(&tsk->signal->shared_pending,
+				 mask, info);
+	/*
+	 * itimer signal ?
+	 *
+	 * itimers are process shared and we restart periodic
+	 * itimers in the signal delivery path to prevent DoS
+	 * attacks in the high resolution timer case. This is
+	 * compliant with the old way of self restarting
+	 * itimers, as the SIGALRM is a legacy signal and only
+	 * queued once. Changing the restart behaviour to
+	 * restart the timer in the signal dequeue path is
+	 * reducing the timer noise on heavy loaded !highres
+	 * systems too.
 	 */
-	signr = __dequeue_signal(&tsk->pending, mask, info);
-	if (!signr) {
-		signr = __dequeue_signal(&tsk->signal->shared_pending,
-					 mask, info);
-		/*
-		 * itimer signal ?
-		 *
-		 * itimers are process shared and we restart periodic
-		 * itimers in the signal delivery path to prevent DoS
-		 * attacks in the high resolution timer case. This is
-		 * compliant with the old way of self restarting
-		 * itimers, as the SIGALRM is a legacy signal and only
-		 * queued once. Changing the restart behaviour to
-		 * restart the timer in the signal dequeue path is
-		 * reducing the timer noise on heavy loaded !highres
-		 * systems too.
-		 */
-		if (unlikely(signr == SIGALRM)) {
-			struct hrtimer *tmr = &tsk->signal->real_timer;
-
-			if (!hrtimer_is_queued(tmr) &&
-			    tsk->signal->it_real_incr.tv64 != 0) {
-				hrtimer_forward(tmr, tmr->base->get_time(),
-						tsk->signal->it_real_incr);
-				hrtimer_restart(tmr);
-			}
+	if (unlikely(signr == SIGALRM)) {
+		struct hrtimer *tmr = &tsk->signal->real_timer;
+
+		if (!hrtimer_is_queued(tmr) &&
+		    tsk->signal->it_real_incr.tv64 != 0) {
+			hrtimer_forward(tmr, tmr->base->get_time(),
+					tsk->signal->it_real_incr);
+			hrtimer_restart(tmr);
 		}
 	}
 
-	recalc_sigpending();
-	if (!signr)
-		return 0;
-
 	if (unlikely(sig_kernel_stop(signr))) {
 		/*
 		 * Set a marker that we have dequeued a stop signal.  Our

@@ -605,6 +595,40 @@ int dequeue_signal(struct task_struct *tsk, sigset_t *mask, siginfo_t *info)
 		 */
 		current->group_stop |= GROUP_STOP_DEQUEUED;
 	}
+
+	return signr;
+}
+
+/*
+ * Dequeue a signal and return the element to the caller, which is 
+ * expected to free it.
+ *
+ * All callers have to hold the siglock.
+ */
+int dequeue_signal(struct task_struct *tsk, sigset_t *mask, siginfo_t *info)
+{
+	int signr;
+
+	/*
+	 * Dequeue shared signals first since this is where SIGSTOP
+	 * and SIGCONTs will be. If we don't dequeue these first
+	 * there's a chance that we could keep handling private
+	 * signals even when there are SIGSTOPs or SIGCONTs pending in
+	 * the shared queue, e.g. we'd starve shared signals from
+	 * being serviced.
+	 */
+	signr = __dequeue_shared_signal(tsk, mask, info);
+
+	/* We only dequeue private signals from ourselves, we don't let
+	 * signalfd steal them
+	 */
+	if (!signr)
+		signr = __dequeue_signal(&tsk->pending, mask, info);
+
+	recalc_sigpending();
+	if (!signr)
+		return 0;
+
 	if ((info->si_code & __SI_MASK) == __SI_TIMER && info->si_sys_private) {
 		/*
 		 * Release the siglock to ensure proper locking order

@@ -779,13 +803,10 @@ static int prepare_signal(int sig, struct task_struct *p, int from_ancestor_ns)
 		 */
 	} else if (sig_kernel_stop(sig)) {
 		/*
-		 * This is a stop signal.  Remove SIGCONT from all queues.
+		 * This is a stop signal.  Remove SIGCONT from the
+		 * shared queue.
 		 */
 		rm_from_queue(sigmask(SIGCONT), &signal->shared_pending);
-		t = p;
-		do {
-			rm_from_queue(sigmask(SIGCONT), &t->pending);
-		} while_each_thread(p, t);
 	} else if (sig == SIGCONT) {
 		unsigned int why;
 		/*

@@ -795,7 +816,6 @@ static int prepare_signal(int sig, struct task_struct *p, int from_ancestor_ns)
 		t = p;
 		do {
 			task_clear_group_stop_pending(t);
-			rm_from_queue(SIG_KERNEL_STOP_MASK, &t->pending);
 			wake_up_state(t, __TASK_STOPPED);
 		} while_each_thread(p, t);
 

@@ -945,7 +965,22 @@ static int __send_signal(int sig, struct siginfo *info, struct task_struct *t,
 	if (!prepare_signal(sig, t, from_ancestor_ns))
 		return 0;
 
-	pending = group ? &t->signal->shared_pending : &t->pending;
+	/*
+	 * We always enqueue SIGSTOP or SIGCONT signals on the shared
+	 * queue. This means that a SIGSTOP or SIGCONT signal _cannot_
+	 * be present on a thread's private pending queue.
+	 *
+	 * This makes prepare_signal() more optimal as we do not have
+	 * to remove signals from each thread's pending queue and so
+	 * can avoid iterating over all threads in the thread group
+	 * (and therefore avoid the locking that would be necessary to
+	 * do that safely).
+	 */
+	if (group || sig_kernel_stop(sig) || sig == SIGCONT)
+		pending = &t->signal->shared_pending;
+	else
+		pending = &t->pending;
+
 	/*
 	 * Short-circuit ignored signals and support queuing
 	 * exactly one non-rt signal, so that we can get more

1.7.4

Hi Matt,

I'll try to study this series, but not before Friday, sorry.

Only one thing,

Yes, the effect is global, but

I don't think we can.

- pending = group ? &t->signal->shared_pending : &t->pending;

No problem!

D'oh, yes. I think I got confused here. You're right, this won't work.

Urgh, debuggers actually peek at shared_pending and pending?

My patches are already based on that tree.

Matt Fleming, Intel Open Source Technology Center

Argh, sorry, I was not clear.

First of all, only SIGSTOP is never delivered to user-space, other sig_kernel_stop() signals can have a handler and in this case, say, SIGTTIN doesn't stop but acts like the normal signal. This means you can't put it into shared_pending.

But even SIGSTOP should be routed properly. If the process is ptraced, the tracee reports SIGSTOP to the debugger first. This means that tkill(SIGSTOP) should be delivered to the right target.

Ah, good.

Oleg.

Hey, guys.

I think the more important part is that there really isn't much point in optimizing SIGSTOP/CONT. They inherently involve heavy, walk-every-thread operations of putting them to sleep and reversing it and there isn't much point in optimizing sending SIGSTOP to stopped processes or CONT to running ones. In addition, STOP/CONT interaction is already scary enough so I'd like to avoid adding complexities there if at all possible.

I think it would be better to concentrate on more usual signals.

Thank you.

tejun

Fair point. Note that none of the other patches try to optimize SIGSTOP/CONT paths.

This patch was also my attempt to make my brain not explode while figuring out the locking order. This was the first patch I wrote in the series and it was before I'd decided on the order. In other words, I was trying to eliminate any code where we'd do,

    tsk->sighand->action_lock
        tsk->siglock
            [Dequeue STOP signal from tsk->pending]
                tsk->sighand->siglock

because that complicates the locking order and this patch seemed like a worthwhile cleanup. As it turns out, it's not a worthwhile/correct cleanup so I'll have to think how I can handle those paths safely with a different locking order.

Matt Fleming, Intel Open Source Technology Center

Yeah, good point. This patch definitely needs dropping from the series.

Right, thanks.

Matt Fleming, Intel Open Source Technology Center

Yes.

Sorry for delay again. I'll try to read the rest of this series tomorrow, I can no longer look at signal.c to today.

Oh, these changes do not look trivial. I must admit, I am a bit sceptical, but this is only my first impression based on amount on changes and more complex locking.

Oleg.

No problem.

Yeah, the locking is more complex and I suspect that because I'm dropping this patch the next iteration might become even more complex. However, I definitely think the complexity is worth it because of how much better signal delivery scales with these patches.

If you find anything that you think is overly complex I'm sure I could clean it up with either comments or refactoring the code.

Matt Fleming, Intel Open Source Technology Center

From: Matt Fleming <[email protected]>

Try to reduce the amount of time we hold the shared siglock by introducing a per-thread siglock that protects each thread's 'pending' queue. Currently, the shared siglock protects both the shared and private signal queues. As such, it is a huge point of contention when generating and delivering signals to single threads in a multithreaded process. For example, even if a thread is delivering a signal to itself (thereby putting a signal on its private signal queue) it must acquire the shared siglock.

To improve signal generation scalability we only acquire the shared siglock when generating a shared signal. If we're generating a private signal which will be delivered to a specific thread (and that signal does not affect an entire thread group) then we can optimise that case by only taking the per-thread siglock. However, the case where we're sending a fatal signal to a specific thread is special because we need to modify tsk->signal->flags, so we need to be holding the shared siglock.

Note that we now hold both the shared and per-thread siglock when delivering a private signal. That will be fixed in the next patch so that signal delivery scales with signal generation.

Also, because we now run signal code paths without holding the shared siglock at all, it can no longer be used to protect tsk->sighand->action. So we introduce a rwlock for protecting tsk->sighand->action. A rwlock is better than a spinlock in this case because there are many more readers than writers and a rwlock allows us to scale much better than a spinlock.

Move the the majority of the shared signal code into a helper function to make the code in dequeue_signal() easier to read.

---
 fs/autofs4/waitq.c        |    2 +
 fs/exec.c                 |    2 +
 fs/signalfd.c             |    2 +
 include/linux/init_task.h |    2 +
 include/linux/sched.h     |    4 +
 include/linux/signal.h    |    5 +
 kernel/exit.c             |   12 ++-
 kernel/fork.c             |    2 +
 kernel/kmod.c             |    8 +-
 kernel/ptrace.c           |    4 +-
 kernel/signal.c           |  189 ++++++++++++++++++++++++++++++++++++++-------
 security/selinux/hooks.c  |    6 +-
 12 files changed, 199 insertions(+), 39 deletions(-)

index 5601005..a7adbf8 100644
@@ -83,7 +83,9 @@ static int autofs4_write(struct file *file, const void *addr, int bytes)
 	   SIGPIPE unless it was already supposed to get one */
 	if (wr == -EPIPE && !sigpipe) {
 		spin_lock_irqsave(&current->sighand->siglock, flags);
+		spin_lock(&current->siglock);
 		sigdelset(&current->pending.signal, SIGPIPE);
+		spin_unlock(&current->siglock);
 		recalc_sigpending();
 		spin_unlock_irqrestore(&current->sighand->siglock, flags);
 	}

index 8328beb..5cc4a6c 100644
@@ -1661,8 +1661,10 @@ static int zap_process(struct task_struct *start, int exit_code)
 	do {
 		task_clear_group_stop_pending(t);
 		if (t != current && t->mm) {
+			spin_lock(&t->siglock);
 			sigaddset(&t->pending.signal, SIGKILL);
 			signal_wake_up(t, 1);
+			spin_unlock(&t->siglock);
 			nr++;
 		}
 	} while_each_thread(start, t);

index 492465b..ed49c40 100644
@@ -48,10 +48,12 @@ static unsigned int signalfd_poll(struct file *file, poll_table *wait)
 	poll_wait(file, &current->sighand->signalfd_wqh, wait);
 
 	spin_lock_irq(&current->sighand->siglock);
+	spin_lock(&current->siglock);
 	if (next_signal(&current->pending, &ctx->sigmask) ||
 	    next_signal(&current->signal->shared_pending,
 			&ctx->sigmask))
 		events |= POLLIN;
+	spin_unlock(&current->siglock);
 	spin_unlock_irq(&current->sighand->siglock);
 
 	return events;

index caa151f..a948d24 100644
@@ -47,6 +47,7 @@ extern struct nsproxy init_nsproxy;
 	.action		= { { { .sa_handler = SIG_DFL, } }, },		\
 	.siglock	= __SPIN_LOCK_UNLOCKED(sighand.siglock),	\
 	.signalfd_wqh	= __WAIT_QUEUE_HEAD_INITIALIZER(sighand.signalfd_wqh),	\
+	.action_lock	= __RW_LOCK_UNLOCKED(sighand.action_lock),	\
 }
 
 extern struct group_info init_groups;

@@ -168,6 +169,7 @@ extern struct cred init_cred;
 	.signal		= &init_signals,				\
 	.sighand	= &init_sighand,				\
 	.nsproxy	= &init_nsproxy,				\
+	.siglock	= __SPIN_LOCK_UNLOCKED(tsk.siglock),		\
 	.pending	= {						\
 		.list = LIST_HEAD_INIT(tsk.pending.list),		\
 		.signal = {{0}}},					\

index 8cef82d..7b2ea86 100644
@@ -443,6 +443,9 @@ struct sighand_struct {
 	struct k_sigaction	action[_NSIG];
 	spinlock_t		siglock;
 	wait_queue_head_t	signalfd_wqh;
+
+	/* protects action */
+	rwlock_t		action_lock;
 };
 
 struct pacct_struct {

@@ -1358,6 +1361,7 @@ struct task_struct {
 
 	sigset_t blocked, real_blocked;
 	sigset_t saved_sigmask;	/* restored if set_restore_sigmask() was used */
+	spinlock_t siglock;	/* protects pending */
 	struct sigpending pending;
 
 	unsigned long sas_ss_sp;

index fcd2b14..9aad2b0 100644
@@ -376,6 +376,11 @@ int unhandled_signal(struct task_struct *tsk, int sig);
 	(!siginmask(signr, SIG_KERNEL_IGNORE_MASK|SIG_KERNEL_STOP_MASK) && \
 	 (t)->sighand->action[(signr)-1].sa.sa_handler == SIG_DFL)
 
+/* Should the signal be placed on shared_pending? */
+#define sig_shared(sig)	\
+	(((sig) < SIGRTMIN) && \
+	 siginmask(sig, SIG_KERNEL_STOP_MASK | rt_sigmask(SIGCONT)))
+
 void signals_init(void);
 
 #endif /* __KERNEL__ */

index 1a0f10f..7774126 100644
@@ -142,7 +142,9 @@ static void __exit_signal(struct task_struct *tsk)
 	 * Do this under ->siglock, we can race with another thread
 	 * doing sigqueue_free() if we have SIGQUEUE_PREALLOC signals.
 	 */
+	spin_lock(&tsk->siglock);
 	flush_sigqueue(&tsk->pending);
+	spin_unlock(&tsk->siglock);
 	tsk->sighand = NULL;
 	spin_unlock(&sighand->siglock);
 

@@ -386,7 +388,8 @@ int allow_signal(int sig)
 	if (!valid_signal(sig) || sig < 1)
 		return -EINVAL;
 
-	spin_lock_irq(&current->sighand->siglock);
+	write_lock_irq(&current->sighand->action_lock);
+	spin_lock(&current->sighand->siglock);
 	/* This is only needed for daemonize()'ed kthreads */
 	sigdelset(&current->blocked, sig);
 	/*

@@ -396,7 +399,8 @@ int allow_signal(int sig)
 	 */
 	current->sighand->action[(sig)-1].sa.sa_handler = (void __user *)2;
 	recalc_sigpending();
-	spin_unlock_irq(&current->sighand->siglock);
+	spin_unlock(&current->sighand->siglock);
+	write_unlock_irq(&current->sighand->action_lock);
 	return 0;
 }
 

@@ -407,10 +411,10 @@ int disallow_signal(int sig)
 	if (!valid_signal(sig) || sig < 1)
 		return -EINVAL;
 
-	spin_lock_irq(&current->sighand->siglock);
+	write_lock_irq(&current->sighand->action_lock);
 	current->sighand->action[(sig)-1].sa.sa_handler = SIG_IGN;
 	recalc_sigpending();
-	spin_unlock_irq(&current->sighand->siglock);
+	write_unlock_irq(&current->sighand->action_lock);
 	return 0;
 }
 

index f2b494d..50fa84f 100644
@@ -1081,6 +1081,7 @@ static struct task_struct *copy_process(unsigned long clone_flags,
 	p->vfork_done = NULL;
 	spin_lock_init(&p->alloc_lock);
 
+	spin_lock_init(&p->siglock);
 	init_sigpending(&p->pending);
 
 	p->utime = cputime_zero;

@@ -1494,6 +1495,7 @@ static void sighand_ctor(void *data)
 
 	spin_lock_init(&sighand->siglock);
 	init_waitqueue_head(&sighand->signalfd_wqh);
+	rwlock_init(&sighand->action_lock);
 }
 
 void __init proc_caches_init(void)

index 9cd0591..551a6e9 100644
@@ -134,9 +134,9 @@ static int ____call_usermodehelper(void *data)
 	struct subprocess_info *sub_info = data;
 	int retval;
 
-	spin_lock_irq(&current->sighand->siglock);
+	write_lock_irq(&current->sighand->action_lock);
 	flush_signal_handlers(current, 1);
-	spin_unlock_irq(&current->sighand->siglock);
+	write_unlock_irq(&current->sighand->action_lock);
 
 	/* We can run anywhere, unlike our parent keventd(). */
 	set_cpus_allowed_ptr(current, cpu_all_mask);

@@ -178,9 +178,9 @@ static int wait_for_helper(void *data)
 	pid_t pid;
 
 	/* If SIGCLD is ignored sys_wait4 won't populate the status. */
-	spin_lock_irq(&current->sighand->siglock);
+	write_lock_irq(&current->sighand->action_lock);
 	current->sighand->action[SIGCHLD-1].sa.sa_handler = SIG_DFL;
-	spin_unlock_irq(&current->sighand->siglock);
+	write_unlock_irq(&current->sighand->action_lock);
 
 	pid = kernel_thread(____call_usermodehelper, sub_info, SIGCHLD);
 	if (pid < 0) {

index 20d5efd..c72d40d 100644
@@ -294,10 +294,10 @@ static int ptrace_traceme(void)
 static int ignoring_children(struct sighand_struct *sigh)
 {
 	int ret;
-	spin_lock(&sigh->siglock);
+	read_lock(&sigh->action_lock);
 	ret = (sigh->action[SIGCHLD-1].sa.sa_handler == SIG_IGN) ||
 	      (sigh->action[SIGCHLD-1].sa.sa_flags & SA_NOCLDWAIT);
-	spin_unlock(&sigh->siglock);
+	read_unlock(&sigh->action_lock);
 	return ret;
 }
 

index 6475e1f..91e2450 100644
@@ -2244,13 +2244,15 @@ static void selinux_bprm_committed_creds(struct linux_binprm *bprm)
 		memset(&itimer, 0, sizeof itimer);
 		for (i = 0; i < 3; i++)
 			do_setitimer(i, &itimer, NULL);
-		spin_lock_irq(&current->sighand->siglock);
+		write_lock_irq(&current->sighand->action_lock);
+		spin_lock(&current->sighand->siglock);
 		if (!(current->signal->flags & SIGNAL_GROUP_EXIT)) {
 			__flush_signals(current);
 			flush_signal_handlers(current, 1);
 			sigemptyset(&current->blocked);
 		}
-		spin_unlock_irq(&current->sighand->siglock);
+		spin_unlock(&current->sighand->siglock);
+		write_unlock_irq(&current->sighand->action_lock);
 	}
 
 	/* Wake up the parent if it is waiting so that it can recheck

1.7.4

Matt, sorry for huge delay.

So. This complicates the locking enormously. I must admit, I dislike this very much. Yes, the signals are slow... But this returns us to the original question: do we really care? Of course, it is always nice to makes the things faster, but I am not sure the added complexity worth the trouble.

Random example,

	int
	force_sig_info(int sig, struct siginfo *info, struct task_struct *t)
	{
		unsigned long int flags;
		int ret, blocked, ignored;
		struct k_sigaction *action;
		int shared_siglock;

		write_lock_irqsave(&t->sighand->action_lock, flags);
		spin_lock(&t->sighand->siglock);
		action = &t->sighand->action[sig-1];
		ignored = action->sa.sa_handler == SIG_IGN;
		blocked = sigismember(&t->blocked, sig);
		if (blocked || ignored) {
			action->sa.sa_handler = SIG_DFL;
			if (blocked) {
				sigdelset(&t->blocked, sig);
				recalc_sigpending_and_wake(t);
			}
		}
		if (action->sa.sa_handler == SIG_DFL)
			t->signal->flags &= ~SIGNAL_UNKILLABLE;

		shared_siglock = sig_shared(sig) || sig_fatal(t, sig);
		if (!shared_siglock) {
			spin_unlock(&t->sighand->siglock);
			spin_lock(&t->siglock);
		}

		ret = specific_send_sig_info(sig, info, t);

		if (!shared_siglock)
			spin_unlock(&t->siglock);
		else
			spin_unlock(&t->sighand->siglock);

		write_unlock_irqrestore(&t->sighand->action_lock, flags);
		return ret;
	}

This doesn't look very nice ;)

To me personally, the only "real" performance problem is kill-from-irq (posix timers is the worst case), this should be solved somehow but these changes can't help...

Anyway, the patches do not look right.

No problem. Thanks for the review!

Well, it's not really that signals are slow (though that might be true!), it's more that they don't scale. So, this patch series was not designed to speed up signals in a single-threaded app, but rather to make signals scale better in multithreaded apps. We do that by reducing the contention on the shared siglock. Signal delivery isn't getting any faster with these patches, they just try to stop it getting slower when you add more threads ;-)

As for the complexity... OK, point taken. Since we've already established that the patch series doesn't work as-is because the first patch is bogus, I'll treat the rest of the review as an academic exercise in helping to highlight any of my misunderstandings about the signal code. If/when I respin this series I'll certainly try to keep it simpler.

Yeah, not my finest work ;-)

But seriously, you're not wrong. This code was written this way as a result of the locking design, which suggests I need to go back to the drawing board and come up with something simpler.

True.

And by "target can't exit" you mean, how can we ensure that the target doesn't execute __exit_signal() and set tsk->signal to NULL if we're not holding the shared siglock in the tkill() path? Good point, that's totally a bug.

While we're discussing the technique for stopping tasks from exiting...

Is there a reason that a short-term reference counter isn't used to prevent this, instead of taking the siglock? Obviously, the siglock already exists and we would have to add a new atomic_t to sighand for the short-term ref, but is there any other fundamental reason why the siglock acquiring method is better? Maybe a short-term ref would make things more complicated? I dunno. siglock does seem to be used for a few different things at the moment though, so currently things are already quite complicated.

Of course, the reason I'm asking is that this entire series relies on avoiding acquiring the shared siglock wherever possible. As you've pointed out above, by not acquiring the shared siglock in the tkill() path we can race with the task exiting, and somehow I need to fix that. Though note that I don't think it's just the tkill() path that is the problem here, it's signal generation in general, i.e. anybody who calls send_signal() without the shared siglock held.

Ah, it's the set_tsk_thread_flag(t, TIF_SIGPENDING) that we need to do atomically. Right, damn, that's a race.

Right.

Yeah, this is a fundamental problem with this series.

D'oh, yes, my bad. I've compounded the case of picking the pending queue with picking the siglock, that's wrong. OK, maybe this new locking is complicated ;-)

We need action_lock because we're reading sighand->action and making decisions based upon its value, so we need it to not change. Also, __send_signal() needs us to have the action_lock at least for reading because we call sig_fatal() in complete_signal(), which checks tsk's action handlers, so again, we need to prevent the handlers from being modified.

We need sighand->siglock because we're sending a group signal, and therefore modifying signal->shared_pending.

The answer also applies to do_notify_parent().

Thanks for the review!

Matt Fleming, Intel Open Source Technology Center

Yes, I understand. Even the private signal needs the "global" per-process lock bit it is rwlock.

No, tsk->signal can't go away, ->sighand can. This means that prepare_signal()->sig_ignored() is not safe.

Another problem is, __send_signal() shouldn't add the new sigqueue to tsk->pending if this tsk has already passed __exit_signal()->flush_sigqueue().

Well, sighand->count is the reference counter. The problem is, ->sighand is not per-process, we can share it with abother CLONE_SIGHAND process and de_thread() can change ->sighand during exec.

Also. We have the code which checks ->sighand != NULL to check if this thread was released or not.

I was going to try to add some cleanups here after the scope of ->signal was changed, but right now I can't recall what I had in mind. Anyway, everything in sighand_struct needs ->siglock anyway, a lockless access doesn't buy too much currently.

Ah, indeed, thanks. Somehow I misread the code as if it takes task->siglock, not sighand->siglock. But anyway I was wrong, I forgot we are going to send the signal.

Oleg.

On Thu, 14 Apr 2011 21:00:12 +0200
Oleg Nesterov <[email protected]> wrote:

[Added Chris to Cc. Chris, check out point 3 below]

Sorry, that was a typo - I meant tsk->sighand.

Right.

What I meant was, a reference to say "You can't change/free ->sighand because I'm reading/modifying it". So you'd have two new functions, get_sighand() and put_sighand(), which would protect the sighand from changing while you were looking at it. Obviously, you'd still need to see if sighand = NULL, but you wouldn't need to grab the shared siglock.

Note how this is different from sighand->count. sighand->count is a much longer term reference which stops it being freed while a task is using it, kinda like a "Don't free _MY_ sighand" reference, whereas what I'm talking about is a "I'm touching YOUR sighand, so don't change/free it" reference, e.g. a short term ref for when we're operating on a target task. It could be that the two references can really be just one atomic_t, I would have to write the code to figure that out.

(Note I haven't thought this through all the way yet. There may be a reason that the above idea is the most stupid thing anyone's ever heard)

Now, at the moment that suggestion just seems like needless overhead because siglock already provides the features we want. But, my problem with siglock is,

1. It needs to be acquired to stop a task passing through __exit_signal().

2. It protects bits of signal_struct and that struct is getting pretty bloated and siglock is being used to protect lots of different things. Do we really need to completely prevent signals being generated/delivered to a thread group while we modify signal->it[] in kernel/itimer.c?

3. I suspect most people find the rules of ->sighand pretty confusing. Just look at

arch/tile/kernel/hardwall.c:do_hardwall_trap()

the use of siglock there looks buggy to me. What if 'p' passes through __exit_signal()? 'p' might not have reached free_task() yet and so won't have called hardwall_deactivate(), which means 'p' could still be on rect->task_head. Chris?

4. It's a heavily contended lock in thread groups (which was the reason for this patch series).

Well, as I think my patch series shows, (in theory) not needing to acquire ->siglock gets us decent scalability improvements (in practice it was buggy as hell but that should be fixable ;-).

Do you have any recollection of the cleanups? signal_struct needs to be put on a diet for sure.

Matt Fleming, Intel Open Source Technology Center

Can't understand...

OK, someone does get_sighand(). Now, what de_thread() should do if it wants to change ->sighand?

And I don't really understand the point. You can read *sighand lockless. But you need some per-CLONE_SIGHAND lock if you want to modify it anyway.

Yes, this is the main problem: it is overused.

We need the better locking. Honestly, _personally_ I do not really care about scalability (but perhaps I should) when it comes to signals, but there are other problems. And, apart from the already mentioned problems with signals-from-irq, I think the main problem is tasklist_lock in do_wait/exit/etc pathes.

And we still have the problems with signals which should be fixed. de_thread() can miss a signal, vfork() should be interruptible, do_coredump() should be interruptible. But first of all we need to define better the behaviour of explicit SIGKILL and what it means after exit_signals(). This should be fixed first, I think.

Indeed, I agree. It shouldn't use __group_send_sig_info() at all. I'll send the patch. Nobody outside of signal code should play with ->sighand, this is almost always wrong.

There is another problem, historically we have a lot, a lot of send-signal helpers, but you can never find the right one. And the naming sucks.

I was going to remove ->sighand from fs/proc first, probably I should try to resend these patches... Then we should remove the "sighand != NULL" checks, we need the new helper, and btw it should be used instead of pid_alive(). Then something else... boring ;)

Oleg.

Hmm. It turns out, I can't make the patch because I do not understand what this code tries to do.

hardwall_activate() adds the thread to hardwall_list, but do_hardwall_trap() sends the signal to the whole process. I know nothing about arch/tile and probably this is correct, but could you confirm this?

Note that SIGILL can be delivered to another thread in the thread-group, is it correct?

Also. Is it supposed that SIGILL can have a hanlder or can be blocked, or it should always kill the whole thread group?

I think we need the patch below, assuming that SIGILL should be sent to the single thread and it is fine to have a handler for SIGILL.

Oleg.

@@ -268,12 +268,10 @@ void __kprobes do_hardwall_trap(struct p
 	found_processes = 0;
 	list_for_each_entry(p, &rect->task_head, thread.hardwall_list) {
 		BUG_ON(p->thread.hardwall != rect);
-		if (p->sighand) {
+		if (!(p->flags & PF_EXITING)) {
 			found_processes = 1;
 			pr_notice("hardwall: killing %d\n", p->pid);
-			spin_lock(&p->sighand->siglock);
-			__group_send_sig_info(info.si_signo, &info, p);
-			spin_unlock(&p->sighand->siglock);
+			do_send_sig_info(info.si_signo, &info, p, false);
 		}
 	}
 	if (!found_processes)

Yes, the intended behavior is to send the signal to the process, as a way of indicating the OS's displeasure with sending a malformed packet on the user network. But I think sending it to the specific thread is reasonable too; I don't have a strong preference in this design.

A handler would be reasonable for the process.

Thanks; I appreciate the additional code review in any case. I'll look at the ramifications of the change in more detail when I return from vacation late next week.

Chris Metcalf, Tilera Corp.
http://www.tilera.com

OK. In this case the thread-specific SIGILL makes more sense afaics.

Great. I am sending the same patch + the changelog.

Please do not forget, I know _nothing_ about arch/tile, and of course the patch was not tested.

Oleg.

1. do_hardwall_trap() checks ->sighand != NULL and then takes ->siglock.

This is unsafe even if the task can't run (I assume it is pinned to the same CPU), its parent can reap the task and set ->sighand = NULL right after this check. Even if the compiler dosn't read ->sighand twice and this memory can't to away __group_send_sig_info() is wrong after that. Use do_send_sig_info().

2. Send SIGILL to the thread, not to the whole process. Unless it has the handler or blocked this kills the whole thread-group as before. IIUC, different threads can be bound to different rect's.

3. Check PF_EXITING instead of ->sighand. A zombie thread can go away but its ->sighand can be !NULL.

---

 arch/tile/kernel/hardwall.c |    6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)

@@ -268,12 +268,10 @@ void __kprobes do_hardwall_trap(struct p
 	found_processes = 0;
 	list_for_each_entry(p, &rect->task_head, thread.hardwall_list) {
 		BUG_ON(p->thread.hardwall != rect);
-		if (p->sighand) {
+		if (!(p->flags & PF_EXITING)) {
 			found_processes = 1;
 			pr_notice("hardwall: killing %d\n", p->pid);
-			spin_lock(&p->sighand->siglock);
-			__group_send_sig_info(info.si_signo, &info, p);
-			spin_unlock(&p->sighand->siglock);
+			do_send_sig_info(info.si_signo, &info, p, false);
 		}
 	}
 	if (!found_processes)

Thanks, I've taken this change into the tile tree.

Chris Metcalf, Tilera Corp.
http://www.tilera.com

[Sorry it's taken me so long to reply to this email]

I think at this stage the best thing for me to do is to write a patch to demonstrate what I'm talking about.

Is the tasklist_lock problem that we acquire the write lock for these paths? Or is it a problem acquiring the read lock too?

Hmm.. interesting. Does the SIGKILL case cause any bugs? Or is it more of a theoretical scenario? I must admit that I can't see any problems.

Heh. I'd be interested in reviewing these patches if you could find and submit them.

Matt Fleming, Intel Open Source Technology Center

From: Matt Fleming <[email protected]>

Also delete the comment that says holding siglock might not be necessary - it is, parts of signal code require that the handlers for a sighand do not change.

---
 arch/ia64/kernel/signal.c |   13 ++-----------
 1 files changed, 2 insertions(+), 11 deletions(-)

index 7bdafc8..d3b37c4 100644
@@ -308,18 +308,9 @@ force_sigsegv_info (int sig, void __user *addr)
 	struct siginfo si;
 
 	if (sig == SIGSEGV) {
-		/*
-		 * Acquiring siglock around the sa_handler-update is almost
-		 * certainly overkill, but this isn't a
-		 * performance-critical path and I'd rather play it safe
-		 * here than having to debug a nasty race if and when
-		 * something changes in kernel/signal.c that would make it
-		 * no longer safe to modify sa_handler without holding the
-		 * lock.
-		 */
-		spin_lock_irqsave(&current->sighand->siglock, flags);
+		write_lock_irqsave(&current->sighand->action_lock, flags);
 		current->sighand->action[sig - 1].sa.sa_handler = SIG_DFL;
-		spin_unlock_irqrestore(&current->sighand->siglock, flags);
+		write_unlock_irqrestore(&current->sighand->action_lock, flags);
 	}
 	si.si_signo = SIGSEGV;
 	si.si_errno = 0;

1.7.4

From: Matt Fleming <[email protected]>

To keep things symmetric with __dequeue_shared_signal() create a __dequeue_private_signal() function which helps to hide the required locking for accessing tsk->pending.

---
 kernel/signal.c |   19 ++++++++++++++-----
 1 files changed, 14 insertions(+), 5 deletions(-)

index c67f27a..db0ce0e 100644
@@ -642,6 +642,18 @@ static int __dequeue_shared_signal(struct task_struct *tsk,
 	return signr;
 }
 
+static int __dequeue_private_signal(struct task_struct *tsk,
+				    sigset_t *mask, siginfo_t *info)
+{
+	int signr;
+
+	spin_lock_irq(&tsk->siglock);
+	signr = __dequeue_signal(&tsk->pending, mask, info);
+	spin_unlock_irq(&tsk->siglock);
+
+	return signr;
+}
+
 /*
  * Dequeue a signal and return the element to the caller, which is 
  * expected to free it.

@@ -665,11 +677,8 @@ int dequeue_signal(struct task_struct *tsk, sigset_t *mask, siginfo_t *info)
 	/* We only dequeue private signals from ourselves, we don't let
 	 * signalfd steal them
 	 */
-	if (!signr) {
-		spin_lock(&tsk->siglock);
-		signr = __dequeue_signal(&tsk->pending, mask, info);
-		spin_unlock(&tsk->siglock);
-	}
+	if (!signr)
+		signr = __dequeue_private_signal(tsk, mask, info);
 
 	recalc_sigpending();
 	if (!signr)

1.7.4

From: Matt Fleming <[email protected]>

To reduce the contention on the shared siglock this patch pushes the responsibility of acquiring and releasing the shared siglock down into the functions that need it. That way, if we don't call a function that needs to be run under the shared siglock, we can run without acquiring it at all.

Note that this does not make signal delivery lockless. A signal must still be dequeued from either the shared or private signal queues. However, in the private signal case we can now get by with just acquiring the per-thread siglock which massively reduces contention on the shared siglock.

Also update tracehook.h to indicate it's not called with siglock held anymore.

With this commit signal delivery now scales much better (though not linearly with the number of threads) as can be seen in these two graphs which execute the signal1 testcase from the Will It Scale benchmark suite,

http://userweb.kernel.org/~mfleming/will-it-scale/signals-per-thread-siglock/

---
 fs/signalfd.c             |    5 --
 include/linux/tracehook.h |    3 +-
 kernel/compat.c           |    7 ++-
 kernel/signal.c           |  124 +++++++++++++++++++++++++++------------------
 4 files changed, 79 insertions(+), 60 deletions(-)

index ed49c40..a9d5c6f 100644
@@ -146,7 +146,6 @@ static ssize_t signalfd_dequeue(struct signalfd_ctx *ctx, siginfo_t *info,
 	ssize_t ret;
 	DECLARE_WAITQUEUE(wait, current);
 
-	spin_lock_irq(&current->sighand->siglock);
 	ret = dequeue_signal(current, &ctx->sigmask, info);
 	switch (ret) {
 	case 0:

@@ -154,7 +153,6 @@ static ssize_t signalfd_dequeue(struct signalfd_ctx *ctx, siginfo_t *info,
 			break;
 		ret = -EAGAIN;
 	default:
-		spin_unlock_irq(&current->sighand->siglock);
 		return ret;
 	}
 

@@ -168,11 +166,8 @@ static ssize_t signalfd_dequeue(struct signalfd_ctx *ctx, siginfo_t *info,
 			ret = -ERESTARTSYS;
 			break;
 		}
-		spin_unlock_irq(&current->sighand->siglock);
 		schedule();
-		spin_lock_irq(&current->sighand->siglock);
 	}
-	spin_unlock_irq(&current->sighand->siglock);
 
 	remove_wait_queue(&current->sighand->signalfd_wqh, &wait);
 	__set_current_state(TASK_RUNNING);

index b073f3c..849336d 100644
@@ -447,7 +447,7 @@ static inline int tracehook_force_sigpending(void)
  * @return_ka:		sigaction for synthetic signal
  *
  * Return zero to check for a real pending signal normally.
- * Return -1 after releasing the siglock to repeat the check.
+ * Return -1 to repeat the check.
  * Return a signal number to induce an artifical signal delivery,
  * setting *@info and *@return_ka to specify its details and behavior.
  *

@@ -458,7 +458,6 @@ static inline int tracehook_force_sigpending(void)
  * %SIGTSTP for stop unless in an orphaned pgrp), but the signal number
  * reported will be @info->si_signo instead.
  *
- * Called with @task->sighand->siglock held, before dequeuing pending signals.
  */
 static inline int tracehook_get_signal(struct task_struct *task,
 				       struct pt_regs *regs,

index 38b1d2c..c7c5f9f 100644
@@ -912,7 +912,6 @@ compat_sys_rt_sigtimedwait (compat_sigset_t __user *uthese,
 			return -EINVAL;
 	}
 
-	spin_lock_irq(&current->sighand->siglock);
 	sig = dequeue_signal(current, &s, &info);
 	if (!sig) {
 		timeout = MAX_SCHEDULE_TIMEOUT;

@@ -920,6 +919,7 @@ compat_sys_rt_sigtimedwait (compat_sigset_t __user *uthese,
 			timeout = timespec_to_jiffies(&t)
 				+(t.tv_sec || t.tv_nsec);
 		if (timeout) {
+			spin_lock_irq(&current->sighand->siglock);
 			current->real_blocked = current->blocked;
 			sigandsets(&current->blocked, &current->blocked, &s);
 

@@ -928,14 +928,15 @@ compat_sys_rt_sigtimedwait (compat_sigset_t __user *uthese,
 
 			timeout = schedule_timeout_interruptible(timeout);
 
-			spin_lock_irq(&current->sighand->siglock);
 			sig = dequeue_signal(current, &s, &info);
+
+			spin_lock_irq(&current->sighand->siglock);
 			current->blocked = current->real_blocked;
 			siginitset(&current->real_blocked, 0);
 			recalc_sigpending();
+			spin_unlock_irq(&current->sighand->siglock);
 		}
 	}
-	spin_unlock_irq(&current->sighand->siglock);
 
 	if (sig) {
 		ret = sig;

1.7.4

This adds new races. And this time I do not even understand the intent. I mean, it is not clear to me why this change can really help to speed up get_signal_to_deliver().

OK, we can dequeue the signal. But dequeue_signal()->recalc_sigpending() becomes even more wrong. We do not hold any lock, we can race with both shared/private signal sending.

Heh. This breaks this tracehook completely ;) OK, nobody cares about the out-of-tree users, forget.

Also. get_signal_to_deliver() does

		signr = dequeue_signal(current, &current->blocked,
					       info);
		...

		ka = &sighand->action[signr-1];

		...

		if (ka->sa.sa_handler != SIG_DFL) {
			/* Run the handler.  */
			*return_ka = *ka;

This memcpy() can race with sys_rt_sigaction(), we can't read *ka atomically.

Actually, even SIG_DFL/SIG_IGN checks can race, although this is minor... But still not correct.

			if (ka->sa.sa_flags & SA_ONESHOT) {
				write_lock(&sighand->action_lock);
				ka->sa.sa_handler = SIG_DFL;
				write_unlock(&sighand->action_lock);

We should check SA_ONESHOT under ->action_lock. But even then this will bw racy, although we can probably ignore this... Suppose that SA_ONESHOT was set after we dequeued the signal.

Oleg.

Again, it's not necessarily speeding up get_signal_to_deliver(), but rather it's reducing the contention on the shared siglock.

For example, without this patch, if you've got someone sending a signal to a task group, you can't run get_signal_to_deliver() in parallel because you'll be waiting for the sending thread to release the shared siglock. Which, if you were going to dequeue a private signal anyway and didn't need to access signal->shared_pending, is unnecessary overhead :-(

As it turns out, the shared siglock protects more than just signal->shared_pending, so in certain cases you need to acquire it anyway (like the fatal signal code paths) so this isn't as optimised as it could be, which is a shame.

Yep, this was covered in the previous patch review.

I was hoping you'd say that ;-)

Eek! I hadn't noticed that. Thanks.

Right, most of this side is wrong wrt to the action_lock.

Thanks Oleg.

Matt Fleming, Intel Open Source Technology Center

Yes, sorry for confusion. I used the "speed up" term wrongly throughout. I understand what are you trying to do.

But yes, in this case I probably missed the intent,

I missed the simple fact, get_signal_to_deliver() could avoid ->siglock completely if it dequeues the private signal.

Btw, I forgot to mention another problem. We should not dequeue from signal->shared_pending before task->pending. There are various reasons why we shouldn't, but in particular please look at a27341cd "Prioritize synchronous signals over 'normal' signals".

Oleg.

Oh, that's an interesting point! I hadn't thought of that.

OK, I'll swap the dequeue order back to the way it was. This actually makes things a little easier as we can now get away with not reading the list of pending shared signals in the fast path.

Matt Fleming, Intel Open Source Technology Center