Skip to contentSkip to conversation

posix-timers: move global timer id management to signal_struct v2

PATCH In review Andi Kleen 7 participants 40 messages Aug 29, 2011 – Sep 22, 2011

Subsystems (5)
lore
Share & tools
lore

Andi Kleen

author
#0 lore raw

PATCH 1/4 posix-timers: move global timer id management to signal_struct v2

From: Andi Kleen <[email protected]>

Move the global posix timer ids IDR to signal_struct. This removes a minor global scalability bottleneck and also allows to finally limit the number of process timers in a sane way (see next patch)

I put it into signal_struct following the other posix timer per process structures.

v2: Now with locking again (thanks Eric)

---
 include/linux/init_task.h |    3 +++
 include/linux/sched.h     |    4 ++++
 kernel/fork.c             |    2 ++
 kernel/posix-timers.c     |   23 ++++++++++++-----------
 4 files changed, 21 insertions(+), 11 deletions(-)
include/linux/init_task.h +3 -0
index d14e058..564248d 100644
@@ -10,6 +10,7 @@
 #include <linux/pid_namespace.h>
 #include <linux/user_namespace.h>
 #include <linux/securebits.h>
+#include <linux/idr.h>
 #include <net/net_namespace.h>
 
 #ifdef CONFIG_SMP
@@ -37,6 +38,7 @@ extern struct fs_struct init_fs;
 		.list = LIST_HEAD_INIT(sig.shared_pending.list),	\
 		.signal =  {{0}}},					\
 	.posix_timers	 = LIST_HEAD_INIT(sig.posix_timers),		\
+	.idr_lock	 = __SPIN_LOCK_UNLOCKED(idr_lock),		\
 	.cpu_timers	= INIT_CPU_TIMERS(sig.cpu_timers),		\
 	.rlim		= INIT_RLIMITS,					\
 	.cputimer	= { 						\
@@ -46,6 +48,7 @@ extern struct fs_struct init_fs;
 	},								\
 	.cred_guard_mutex =						\
 		 __MUTEX_INITIALIZER(sig.cred_guard_mutex),		\
+	.posix_timers_id = IDR_INIT(posix_timer_id),			\
 	INIT_THREADGROUP_FORK_LOCK(sig)					\
 }
 
include/linux/sched.h +4 -0
index 4ac2c05..87fa2fc 100644
@@ -62,6 +62,7 @@ struct sched_param {
 #include <linux/errno.h>
 #include <linux/nodemask.h>
 #include <linux/mm_types.h>
+#include <linux/idr.h>
 
 #include <asm/system.h>
 #include <asm/page.h>
@@ -652,6 +653,9 @@ struct signal_struct {
 	struct mutex cred_guard_mutex;	/* guard against foreign influences on
 					 * credential calculations
 					 * (notably. ptrace) */
+
+	struct idr posix_timers_id;
+	spinlock_t idr_lock;		/* Protect posix_timers_id writes */
 };
 
 /* Context switch must be unlocked if interrupts are to be enabled */
kernel/fork.c +2 -0
index 8e6b6f4..1054cfd 100644
@@ -943,6 +943,8 @@ static void posix_cpu_timers_init_group(struct signal_struct *sig)
 	INIT_LIST_HEAD(&sig->cpu_timers[0]);
 	INIT_LIST_HEAD(&sig->cpu_timers[1]);
 	INIT_LIST_HEAD(&sig->cpu_timers[2]);
+
+	idr_init(&sig->posix_timers_id);
 }
 
 static int copy_signal(unsigned long clone_flags, struct task_struct *tsk)
kernel/posix-timers.c +12 -11
index 4556182..4193cf7 100644
@@ -70,8 +70,6 @@
  * Lets keep our timers in a slab cache :-)
  */
 static struct kmem_cache *posix_timers_cache;
-static struct idr posix_timers_id;
-static DEFINE_SPINLOCK(idr_lock);
 
 /*
  * we assume that the new SIGEV_THREAD_ID shares no bits with the other
@@ -282,7 +280,6 @@ static __init int init_posix_timers(void)
 	posix_timers_cache = kmem_cache_create("posix_timers_cache",
 					sizeof (struct k_itimer), 0, SLAB_PANIC,
 					NULL);
-	idr_init(&posix_timers_id);
 	return 0;
 }
 
@@ -503,10 +500,11 @@ static void k_itimer_rcu_free(struct rcu_head *head)
 static void release_posix_timer(struct k_itimer *tmr, int it_id_set)
 {
 	if (it_id_set) {
+		struct signal_struct *s = current->signal;
 		unsigned long flags;
-		spin_lock_irqsave(&idr_lock, flags);
-		idr_remove(&posix_timers_id, tmr->it_id);
-		spin_unlock_irqrestore(&idr_lock, flags);
+		spin_lock_irqsave(&s->idr_lock, flags);
+		idr_remove(&s->posix_timers_id, tmr->it_id);
+		spin_unlock_irqrestore(&s->idr_lock, flags);
 	}
 	put_pid(tmr->it_pid);
 	sigqueue_free(tmr->sigq);
@@ -541,6 +539,7 @@ SYSCALL_DEFINE3(timer_create, const clockid_t, which_clock,
 	int error, new_timer_id;
 	sigevent_t event;
 	int it_id_set = IT_ID_NOT_SET;
+	struct signal_struct *s = current->signal;
 
 	if (!kc)
 		return -EINVAL;
@@ -553,13 +552,13 @@ SYSCALL_DEFINE3(timer_create, const clockid_t, which_clock,
 
 	spin_lock_init(&new_timer->it_lock);
  retry:
-	if (unlikely(!idr_pre_get(&posix_timers_id, GFP_KERNEL))) {
+	if (unlikely(!idr_pre_get(&s->posix_timers_id, GFP_KERNEL))) {
 		error = -EAGAIN;
 		goto out;
 	}
-	spin_lock_irq(&idr_lock);
-	error = idr_get_new(&posix_timers_id, new_timer, &new_timer_id);
-	spin_unlock_irq(&idr_lock);
+	spin_lock_irq(&s->idr_lock);
+	error = idr_get_new(&s->posix_timers_id, new_timer, &new_timer_id);
+	spin_unlock_irq(&s->idr_lock);
 	if (error) {
 		if (error == -EAGAIN)
 			goto retry;
@@ -638,9 +637,10 @@ out:
 static struct k_itimer *__lock_timer(timer_t timer_id, unsigned long *flags)
 {
 	struct k_itimer *timr;
+	struct signal_struct *s = current->signal;
 
 	rcu_read_lock();
-	timr = idr_find(&posix_timers_id, (int)timer_id);
+	timr = idr_find(&s->posix_timers_id, (int)timer_id);
 	if (timr) {
 		spin_lock_irqsave(&timr->it_lock, *flags);
 		if (timr->it_signal == current->signal) {
@@ -945,6 +945,7 @@ void exit_itimers(struct signal_struct *sig)
 		tmr = list_entry(sig->posix_timers.next, struct k_itimer, list);
 		itimer_delete(tmr);
 	}
+	idr_destroy(&sig->posix_timers_id);
 }
 
 SYSCALL_DEFINE2(clock_settime, const clockid_t, which_clock,
Signature · 1 line
1.7.4.4
author
#1 lore raw

PATCH 2/4 posix-timers: limit the number of posix timers per process

From: Andi Kleen <[email protected]>

Now this is the main reason I wrote the whole patchkit: previously there was no limit on the maximum number of POSIX timers a process could allocate. This limits the amount of unswappable kernel memory a process can pin down this way.

With the POSIX timer ids being per process we can do this limit per process now without allowing one process DoSing another.

I implemented it as a sysctl, not a rlimit for now, because there was no clear use case for rlimit.

The 1024 default is completely arbitrary, but seems reasonable for now.

---
 Documentation/sysctl/kernel.txt |    7 +++++++
 kernel/posix-timers.c           |    8 ++++++++
 kernel/sysctl.c                 |    9 +++++++++
 3 files changed, 24 insertions(+), 0 deletions(-)
Documentation/sysctl/kernel.txt +7 -0
index 704e474..1f69cae 100644
@@ -35,6 +35,7 @@ show up in /proc/sys/kernel:
 - kptr_restrict
 - kstack_depth_to_print       [ X86 only ]
 - l2cr                        [ PPC only ]
+- max_posix_timer
 - modprobe                    ==> Documentation/debugging-modules.txt
 - modules_disabled
 - msgmax
@@ -299,6 +300,12 @@ This flag controls the L2 cache of G3 processor boards. If
 
 ==============================================================
 
+max_posix_timers
+
+The maximum number of POSIX timer ids per process.
+
+==============================================================
+
 modules_disabled:
 
 A toggle value indicating if modules are allowed to be loaded
kernel/posix-timers.c +8 -0
index 4193cf7..ef6721c 100644
@@ -71,6 +71,8 @@
  */
 static struct kmem_cache *posix_timers_cache;
 
+int sysctl_max_posix_timers __read_mostly = 1024;
+
 /*
  * we assume that the new SIGEV_THREAD_ID shares no bits with the other
  * SIGEV values.  Here we put out an error if this assumption fails.
@@ -572,6 +574,12 @@ SYSCALL_DEFINE3(timer_create, const clockid_t, which_clock,
 
 	it_id_set = IT_ID_SET;
 	new_timer->it_id = (timer_t) new_timer_id;
+
+	if (new_timer_id >= sysctl_max_posix_timers) {
+		error = -EMFILE;  /* better error? */
+		goto out;
+	}
+
 	new_timer->it_clock = which_clock;
 	new_timer->it_overrun = -1;
 
kernel/sysctl.c +9 -0
index 11d65b5..8fcf8b5 100644
@@ -108,6 +108,7 @@ extern int sysctl_nr_trim_pages;
 #ifdef CONFIG_BLOCK
 extern int blk_iopoll_enabled;
 #endif
+extern int sysctl_max_posix_timers;
 
 /* Constants used for minimum and  maximum */
 #ifdef CONFIG_LOCKUP_DETECTOR
@@ -984,6 +985,14 @@ static struct ctl_table kern_table[] = {
 		.proc_handler	= proc_dointvec,
 	},
 #endif
+	{
+		.procname	= "max_posix_timers",
+		.data		= &sysctl_max_posix_timers,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= proc_dointvec,
+	},
+
 	{ }
 };
 
Signature · 1 line
1.7.4.4
maintainer
#2 lore raw

Re: [PATCH 2/4] posix-timers: limit the number of posix timers per process

Quoted 5 lines · On Mon, 29 Aug 2011 16:39:15 -0700 Andi Kleen <[email protected]> wrote:

Now this is the main reason I wrote the whole patchkit: previously there was no limit on the maximum number of POSIX timers a process could allocate. This limits the amount of unswappable kernel memory a process can pin down this way.

Quoted 8 lines

With the POSIX timer ids being per process we can do this limit per process now without allowing one process DoSing another.

I implemented it as a sysctl, not a rlimit for now, because there was no clear use case for rlimit.

The 1024 default is completely arbitrary, but seems reasonable for now.

Sorry, it should be an rlimit from day one, IMO.

Partly because rlimits are a better implementation.

Partly because if we later do it via rlimit, we're stuck having to maintain the /proc knob for ever.

Partly because once rlimits are added, the /proc knob no longer has any sane behaviour. Does it only modify /sbin/init? Does it do a global process walk, modifying all threads?

#3 lore raw

Re: [PATCH 2/4] posix-timers: limit the number of posix timers per process

Quoted 3 lines

Sorry, it should be an rlimit from day one, IMO.

Ok.

Quoted 1 line

Partly because rlimits are a better implementation.

The reason I went with a sysctl is that rlimits are more intrusive for user space, requires special tools or patching bash.

Quoted 3 lines

Partly because once rlimits are added, the /proc knob no longer has any sane behaviour. Does it only modify /sbin/init? Does it do a global process walk, modifying all threads?

There's no way to modify: you would need to kill the process or randomly take timers away. The limit only applies to new timers.

-Andi

maintainer
#4 lore raw

Re: [PATCH 2/4] posix-timers: limit the number of posix timers per process

Quoted 11 lines · On Tue, 30 Aug 2011 15:06:30 -0700 Andi Kleen <[email protected]> wrote:
Quoted 3 lines

Sorry, it should be an rlimit from day one, IMO.

Ok.

Quoted 1 line

Partly because rlimits are a better implementation.

The reason I went with a sysctl is that rlimits are more intrusive for user space,
requires special tools or patching bash.

Yes, deployment for new rlimits is a big PITA. It would be sensible to modify the shells to take some anonymous numeric argument, so you could do

	ulimit 42 1000

to set rlimit number 42 if your shell version doesn't understand the symbolic representation of more recent additions. Who do I call?

There was code floating about which would permit rlimits to be modified from other processes, perhaps by making /proc/pid/limits writable. I don't think it got merged. I have a vague feeling that this might be my fault.

Quoted 6 lines
Quoted 3 lines

Partly because once rlimits are added, the /proc knob no longer has any sane behaviour. Does it only modify /sbin/init? Does it do a global process walk, modifying all threads?

There's no way to modify: you would need to kill the process or randomly take timers away. The limit only applies to new timers.

Sure, it applies to new timers. My concern is: what does a write to the old /proc knob _do_? Modify all the system's task_struct.rlim[], overwriting whatever was there? Something else? It would need to at least roughly emulate the old behaviour.

#5 lore raw

Re: [PATCH 2/4] posix-timers: limit the number of posix timers per process

Quoted 9 lines

Yes, deployment for new rlimits is a big PITA. It would be sensible to modify the shells to take some anonymous numeric argument, so you could do

	ulimit 42 1000

to set rlimit number 42 if your shell version doesn't understand the symbolic representation of more recent additions. Who do I call?

I guess sending a patch to the bash maintainers?

-Andi

maintainer
#6 lore raw

Re: [PATCH 2/4] posix-timers: limit the number of posix timers per process

Quoted 5 lines · On Tue, 30 Aug 2011 15:47:47 -0700 Andi Kleen <[email protected]> wrote:
Quoted 5 lines

Yes, deployment for new rlimits is a big PITA. It would be sensible to modify the shells to take some anonymous numeric argument, so you could do

Quoted 7 lines
Quoted 4 lines
	ulimit 42 1000

to set rlimit number 42 if your shell version doesn't understand the symbolic representation of more recent additions. Who do I call?

I guess sending a patch to the bash maintainers?

That would help ;) And all the other shells :(

It would be worth going back and taking another look at the writable /proc/<pid>/limits patches (http://lwn.net/Articles/365732/). Why didn't that work get merged?

#7 lore raw

Re: [PATCH 2/4] posix-timers: limit the number of posix timers per process

Quoted 13 lines · Andrew Morton
Quoted 10 lines · On Tue, 30 Aug 2011 15:47:47 -0700 Andi Kleen<[email protected]> wrote:
Quoted 9 lines

Yes, deployment for new rlimits is a big PITA. It would be sensible to modify the shells to take some anonymous numeric argument, so you could do

	ulimit 42 1000

to set rlimit number 42 if your shell version doesn't understand the symbolic representation of more recent additions. Who do I call?

Quoted 8 lines
Quoted 2 lines

I guess sending a patch to the bash maintainers?

That would help ;) And all the other shells :(

It would be worth going back and taking another look at the writable /proc/<pid>/limits patches (http://lwn.net/Articles/365732/). Why didn't that work get merged?

This turned out to be too heavy-weight. We ended up having prlimit64 syscall. I.e. most of the pull request was merged. But not the 2 patches for writable /proc/.../limits.

With that syscall we might augment coreutils (or better kernel/tools to be updated properly) by a tool such as `prlimit', I think. Actually something I had when I was testing the syscall:
https://github.com/jirislaby/collected_sources/blob/master/lim/lim.c#L1

regards,

Signature · 2 lines
js
suse labs
#8 lore raw

Re: [PATCH 2/4] posix-timers: limit the number of posix timers per process

In reply to Andi Kleen
Quoted 7 lines · Andi Kleen

From: Andi Kleen <[email protected]>

Now this is the main reason I wrote the whole patchkit: previously there was no limit on the maximum number of POSIX timers a process could allocate. This limits the amount of unswappable kernel memory a process can pin down this way.

Quoted 5 lines

With the POSIX timer ids being per process we can do this limit per process now without allowing one process DoSing another.

I implemented it as a sysctl, not a rlimit for now, because there was no clear use case for rlimit.

rlimit please.

kernel/posix-timers.c SYSCALL_DEFINE3(timer_create, const clockid_t, which_clock, · line 579

Quoted 10 lines

/*
* we assume that the new SIGEV_THREAD_ID shares no bits with the other
* SIGEV values. Here we put out an error if this assumption fails.

kernel/posix-timers.c +3 -0
@@ -572,6 +574,12 @@ SYSCALL_DEFINE3(timer_create, const clockid_t, which_clock,
 
 	it_id_set = IT_ID_SET;
 	new_timer->it_id = (timer_t) new_timer_id;
+
+	if (new_timer_id >= sysctl_max_posix_timers) {
+		error = -EMFILE;  /* better error? */

EPERM might work as well

Thanks,

tglx

author
#9 lore raw

PATCH 3/4 posix-timers: Don't disable interrupts in idr_lock

In reply to Andi Kleen

From: Andi Kleen <[email protected]>

idr_lock is only used for modifying a timer and never used from interrupts, only from process context. So don't disable interrupts while taking that lock.

---
 kernel/posix-timers.c |    9 ++++-----
 1 files changed, 4 insertions(+), 5 deletions(-)
kernel/posix-timers.c +4 -5
index ef6721c..320659d 100644
@@ -503,10 +503,9 @@ static void release_posix_timer(struct k_itimer *tmr, int it_id_set)
 {
 	if (it_id_set) {
 		struct signal_struct *s = current->signal;
-		unsigned long flags;
-		spin_lock_irqsave(&s->idr_lock, flags);
+		spin_lock(&s->idr_lock);
 		idr_remove(&s->posix_timers_id, tmr->it_id);
-		spin_unlock_irqrestore(&s->idr_lock, flags);
+		spin_unlock(&s->idr_lock);
 	}
 	put_pid(tmr->it_pid);
 	sigqueue_free(tmr->sigq);
@@ -558,9 +557,9 @@ SYSCALL_DEFINE3(timer_create, const clockid_t, which_clock,
 		error = -EAGAIN;
 		goto out;
 	}
-	spin_lock_irq(&s->idr_lock);
+	spin_lock(&s->idr_lock);
 	error = idr_get_new(&s->posix_timers_id, new_timer, &new_timer_id);
-	spin_unlock_irq(&s->idr_lock);
+	spin_unlock(&s->idr_lock);
 	if (error) {
 		if (error == -EAGAIN)
 			goto retry;
Signature · 1 line
1.7.4.4
author
#10 lore raw

PATCH 4/4 posix-timers: turn it_signal into it_valid flag

In reply to Andi Kleen

From: Andi Kleen <[email protected]>

Now that the timer IDR is per process we don't need to save the signal_struct in the timer anymore. Still need this as a flag for RCU, so turn it into a it_valid flag.

Suggested by Eric Dumazet

---
 include/linux/posix-timers.h |    2 +-
 kernel/posix-timers.c        |    8 ++++----
 2 files changed, 5 insertions(+), 5 deletions(-)
include/linux/posix-timers.h +1 -1
index 959c141..02c1f04 100644
@@ -63,7 +63,7 @@ struct k_itimer {
 	int it_requeue_pending;		/* waiting to requeue this timer */
 #define REQUEUE_PENDING 1
 	int it_sigev_notify;		/* notify word of sigevent struct */
-	struct signal_struct *it_signal;
+	int it_valid;
 	union {
 		struct pid *it_pid;	/* pid of process to send signal to */
 		struct task_struct *it_process;	/* for clock_nanosleep */
kernel/posix-timers.c +4 -4
index 320659d..5b27641 100644
@@ -618,7 +618,7 @@ SYSCALL_DEFINE3(timer_create, const clockid_t, which_clock,
 		goto out;
 
 	spin_lock_irq(&current->sighand->siglock);
-	new_timer->it_signal = current->signal;
+	new_timer->it_valid = 1;
 	list_add(&new_timer->list, &current->signal->posix_timers);
 	spin_unlock_irq(&current->sighand->siglock);
 
@@ -650,7 +650,7 @@ static struct k_itimer *__lock_timer(timer_t timer_id, unsigned long *flags)
 	timr = idr_find(&s->posix_timers_id, (int)timer_id);
 	if (timr) {
 		spin_lock_irqsave(&timr->it_lock, *flags);
-		if (timr->it_signal == current->signal) {
+		if (timr->it_valid) {
 			rcu_read_unlock();
 			return timr;
 		}
@@ -908,7 +908,7 @@ retry_delete:
 	 * This keeps any tasks waiting on the spin lock from thinking
 	 * they got something (see the lock code above).
 	 */
-	timer->it_signal = NULL;
+	timer->it_valid = 0;
 
 	unlock_timer(timer, flags);
 	release_posix_timer(timer, IT_ID_SET);
@@ -934,7 +934,7 @@ retry_delete:
 	 * This keeps any tasks waiting on the spin lock from thinking
 	 * they got something (see the lock code above).
 	 */
-	timer->it_signal = NULL;
+	timer->it_valid = 0;
 
 	unlock_timer(timer, flags);
 	release_posix_timer(timer, IT_ID_SET);
Signature · 1 line
1.7.4.4
#11 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

Quoted 5 lines · Andi Kleen

From: Andi Kleen <[email protected]>

Now that the timer IDR is per process we don't need to save the signal_struct in the timer anymore. Still need this as a flag for RCU, so turn it into a it_valid flag.

That's wrong. it_signal is not necessary for RCU, it's necessary for protecting against a concurrent timer deletion.

Quoted 13 lines

Suggested by Eric Dumazet

---
 include/linux/posix-timers.h |    2 +-
 kernel/posix-timers.c        |    8 ++++----
 2 files changed, 5 insertions(+), 5 deletions(-)
include/linux/posix-timers.h +0 -0
index 959c141..02c1f04 100644

include/linux/posix-timers.h struct k_itimer { · line 66

Quoted 5 lines
include/linux/posix-timers.h +1 -1
@@ -63,7 +63,7 @@ struct k_itimer {
 	int it_requeue_pending;		/* waiting to requeue this timer */
 #define REQUEUE_PENDING 1
 	int it_sigev_notify;		/* notify word of sigevent struct */
-	struct signal_struct *it_signal;
+	int it_valid;

What's the gain of this change? Nothing, AFAICT. But looking closer we can get rid of it_signal completely.

Thanks,

tglx

------------------>
Subject: posix-timers: Simplify deletion protection
From: Thomas Gleixner <[email protected]>
Date: Fri, 02 Sep 2011 11:59:14 +0200

k_itimer->it_signal is soleley used to protect a timer lookup against a concurrent deletion. We can use k_itimer->list for the same purpose.

---
 include/linux/posix-timers.h |    1 -
 kernel/posix-timers.c        |   20 +++++++++-----------
 2 files changed, 9 insertions(+), 12 deletions(-)
include/linux/posix-timers.h +0 -1
Index: linux-2.6/include/linux/posix-timers.h
===================================================================
@@ -63,7 +63,6 @@ struct k_itimer {
 	int it_requeue_pending;		/* waiting to requeue this timer */
 #define REQUEUE_PENDING 1
 	int it_sigev_notify;		/* notify word of sigevent struct */
-	struct signal_struct *it_signal;
 	union {
 		struct pid *it_pid;	/* pid of process to send signal to */
 		struct task_struct *it_process;	/* for clock_nanosleep */
kernel/posix-timers.c +9 -11
Index: linux-2.6/kernel/posix-timers.c
===================================================================
@@ -483,6 +483,7 @@ static struct k_itimer * alloc_posix_tim
 	tmr = kmem_cache_zalloc(posix_timers_cache, GFP_KERNEL);
 	if (!tmr)
 		return tmr;
+	INIT_LIST_HEAD(&tmr->list);
 	if (unlikely(!(tmr->sigq = sigqueue_alloc()))) {
 		kmem_cache_free(posix_timers_cache, tmr);
 		return NULL;
@@ -612,7 +613,6 @@ SYSCALL_DEFINE3(timer_create, const cloc
 		goto out;
 
 	spin_lock_irq(&current->sighand->siglock);
-	new_timer->it_signal = current->signal;
 	list_add(&new_timer->list, &current->signal->posix_timers);
 	spin_unlock_irq(&current->sighand->siglock);
 
@@ -643,7 +643,7 @@ static struct k_itimer *__lock_timer(tim
 	timr = idr_find(&posix_timers_id, (int)timer_id);
 	if (timr) {
 		spin_lock_irqsave(&timr->it_lock, *flags);
-		if (timr->it_signal == current->signal) {
+		if (!list_empty(&timr->list)) {
 			rcu_read_unlock();
 			return timr;
 		}
@@ -895,13 +895,12 @@ retry_delete:
 	}
 
 	spin_lock(&current->sighand->siglock);
-	list_del(&timer->list);
-	spin_unlock(&current->sighand->siglock);
 	/*
-	 * This keeps any tasks waiting on the spin lock from thinking
-	 * they got something (see the lock code above).
+	 * We initialize the list to indicate deletion for
+	 * __lock_timer().
 	 */
-	timer->it_signal = NULL;
+	list_del_init(&timer->list);
+	spin_unlock(&current->sighand->siglock);
 
 	unlock_timer(timer, flags);
 	release_posix_timer(timer, IT_ID_SET);
@@ -922,12 +921,11 @@ retry_delete:
 		unlock_timer(timer, flags);
 		goto retry_delete;
 	}
-	list_del(&timer->list);
 	/*
-	 * This keeps any tasks waiting on the spin lock from thinking
-	 * they got something (see the lock code above).
+	 * We initialize the list to indicate deletion for
+	 * __lock_timer().
 	 */
-	timer->it_signal = NULL;
+	list_del_init(&timer->list);
 
 	unlock_timer(timer, flags);
 	release_posix_timer(timer, IT_ID_SET);
#12 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

Quoted 8 lines · Thomas Gleixner

------------------>
Subject: posix-timers: Simplify deletion protection
From: Thomas Gleixner <[email protected]>
Date: Fri, 02 Sep 2011 11:59:14 +0200

k_itimer->it_signal is soleley used to protect a timer lookup against a concurrent deletion. We can use k_itimer->list for the same purpose.

Well, this patch is wrong too, unless you base it after Andi patch 1/4 (move global timer id management to signal_struct)

The test is also present to make sure one process doesnt try to use a timer_id of another process.

Quoted 9 lines
kernel/posix-timers.c +1 -1
@@ -643,7 +643,7 @@ static struct k_itimer *__lock_timer(tim
 	timr = idr_find(&posix_timers_id, (int)timer_id);
 	if (timr) {
 		spin_lock_irqsave(&timr->it_lock, *flags);
-		if (timr->it_signal == current->signal) {
+		if (!list_empty(&timr->list)) {
 			rcu_read_unlock();
 			return timr;
 		}
#13 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

Quoted 7 lines · Eric Dumazet
Quoted 5 lines · Thomas Gleixner

------------------>
Subject: posix-timers: Simplify deletion protection
From: Thomas Gleixner <[email protected]>
Date: Fri, 02 Sep 2011 11:59:14 +0200

Quoted 6 lines
Quoted 3 lines

k_itimer->it_signal is soleley used to protect a timer lookup against a concurrent deletion. We can use k_itimer->list for the same purpose.

Well, this patch is wrong too, unless you base it after Andi patch 1/4 (move global timer id management to signal_struct)

I know, it's not for the current code.

Quoted 2 lines

The test is also present to make sure one process doesnt try to use a timer_id of another process.

Right, but after moving the idr into sig struct it's only purpose is to protect against deletion, which is nicely covered by the list_head check as well.

Thanks,

tglx

Quoted 14 lines
Quoted 10 lines
kernel/posix-timers.c +1 -1
@@ -643,7 +643,7 @@ static struct k_itimer *__lock_timer(tim
 	timr = idr_find(&posix_timers_id, (int)timer_id);
 	if (timr) {
 		spin_lock_irqsave(&timr->it_lock, *flags);
-		if (timr->it_signal == current->signal) {
+		if (!list_empty(&timr->list)) {
 			rcu_read_unlock();
 			return timr;
 		}
#14 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

In reply to Thomas Gleixner
Quoted 11 lines · Thomas Gleixner
Quoted 5 lines · Andi Kleen

From: Andi Kleen <[email protected]>

Now that the timer IDR is per process we don't need to save the signal_struct in the timer anymore. Still need this as a flag for RCU, so turn it into a it_valid flag.

That's wrong. it_signal is not necessary for RCU, it's necessary for protecting against a concurrent timer deletion.

The main reason for it_signal was the fact we use the global idr database, we should check that the timer was created by us. But yes, another reason was to check that the timer is "valid", we can race with create/delete. See 27af4245.

Quoted 19 lines
kernel/posix-timers.c +1 -1
@@ -483,6 +483,7 @@ static struct k_itimer * alloc_posix_tim
 	tmr = kmem_cache_zalloc(posix_timers_cache, GFP_KERNEL);
 	if (!tmr)
 		return tmr;
+	INIT_LIST_HEAD(&tmr->list);
 	if (unlikely(!(tmr->sigq = sigqueue_alloc()))) {
 		kmem_cache_free(posix_timers_cache, tmr);
 		return NULL;
@@ -612,7 +613,6 @@ SYSCALL_DEFINE3(timer_create, const cloc
 		goto out;
 
 	spin_lock_irq(&current->sighand->siglock);
-	new_timer->it_signal = current->signal;
 	list_add(&new_timer->list, &current->signal->posix_timers);
 	spin_unlock_irq(&current->sighand->siglock);
 

kernel/posix-timers.c static struct k_itimer *__lock_timer(tim · line 646

Quoted 5 lines
kernel/posix-timers.c +1 -1
@@ -643,7 +643,7 @@ static struct k_itimer *__lock_timer(tim
 	timr = idr_find(&posix_timers_id, (int)timer_id);
 	if (timr) {
 		spin_lock_irqsave(&timr->it_lock, *flags);
-		if (timr->it_signal == current->signal) {
+		if (!list_empty(&timr->list)) {

looks correct at first glance....

The problem is, now that we have signal->posix_timers_id, we can kill signal->posix_timers and k_itimer->list. Probably we can nullify k_itimer->it_id to mark it as invalid before idr_remove. Although I feel this all can be simplified even more.

And why do we need to add signal->idr_lock ? It is only used to serialize idr_get/idr_remove. Probably we can use ->siglock for that, posix timers use this lock anyway.

Also. I am not sure, but perhaps it make sense to turn signal->posix_timers_id into the pointer to "struct idr" and allocate idr on demand?

Oleg.

author
#15 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

Quoted 4 lines

And why do we need to add signal->idr_lock ? It is only used to serialize idr_get/idr_remove. Probably we can use ->siglock for that, posix timers use this lock anyway.

Ok. In fact idrs have an own lock too, I'll check that out.

Quoted 4 lines

Also. I am not sure, but perhaps it make sense to turn signal->posix_timers_id into the pointer to "struct idr" and allocate idr on demand?

Probably not worth it, it's not big enough.

-Andi

#16 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

In reply to Oleg Nesterov
Quoted 3 lines · Oleg Nesterov

Although I
feel this all can be simplified even more.

And perhaps we need some fixes?

I forgot everything I knew about ->it_requeue_pending logic, but it seems to me that do_schedule_next_timer()->lock_timer() can find and lock successfully the wrong timer. Another thread can do timer_delete() and then re-create the timer with the same id.

Oleg.

#17 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

Quoted 4 lines

I forgot everything I knew about ->it_requeue_pending logic, but it seems to me that do_schedule_next_timer()->lock_timer() can find and lock successfully the wrong timer. Another thread can do timer_delete() and then re-create the timer with the same id.

Do you mean after my patches or even before?
-Andi

#18 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

Quoted 7 lines · Andi Kleen
Quoted 5 lines

I forgot everything I knew about ->it_requeue_pending logic, but it seems to me that do_schedule_next_timer()->lock_timer() can find and lock successfully the wrong timer. Another thread can do timer_delete() and then re-create the timer with the same id.

Do you mean after my patches or even before?

Ah, sorry for confusion.

Before. And after. IOW, I think this has nothing to do with your patches.

Oleg.

#19 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

Quoted 7 lines · Oleg Nesterov
Quoted 6 lines · Andi Kleen
Quoted 5 lines

I forgot everything I knew about ->it_requeue_pending logic, but it seems to me that do_schedule_next_timer()->lock_timer() can find and lock successfully the wrong timer. Another thread can do timer_delete() and then re-create the timer with the same id.

Quoted 6 lines
Quoted 1 line

Do you mean after my patches or even before?

Ah, sorry for confusion.

Before. And after. IOW, I think this has nothing to do with your patches.

Hmm, you mean following patch is needed ?

Before release of timer id to idr pool, we should make sure do_schedule_next_timer() wont be called, or it could find another timer reusing the just released id.

kernel/posix-timers.c +2 -2
index 4556182..4369747 100644
@@ -502,14 +502,14 @@ static void k_itimer_rcu_free(struct rcu_head *head)
 #define IT_ID_NOT_SET	0
 static void release_posix_timer(struct k_itimer *tmr, int it_id_set)
 {
+	put_pid(tmr->it_pid);
+	sigqueue_free(tmr->sigq);
 	if (it_id_set) {
 		unsigned long flags;
 		spin_lock_irqsave(&idr_lock, flags);
 		idr_remove(&posix_timers_id, tmr->it_id);
 		spin_unlock_irqrestore(&idr_lock, flags);
 	}
-	put_pid(tmr->it_pid);
-	sigqueue_free(tmr->sigq);
 	call_rcu(&tmr->it.rcu, k_itimer_rcu_free);
 }
 
#20 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

Quoted 30 lines · Eric Dumazet
Quoted 7 lines · Oleg Nesterov
Quoted 6 lines · Andi Kleen
Quoted 5 lines

I forgot everything I knew about ->it_requeue_pending logic, but it seems to me that do_schedule_next_timer()->lock_timer() can find and lock successfully the wrong timer. Another thread can do timer_delete() and then re-create the timer with the same id.

Quoted 6 lines
Quoted 1 line

Do you mean after my patches or even before?

Ah, sorry for confusion.

Before. And after. IOW, I think this has nothing to do with your patches.

Hmm, you mean following patch is needed ?

Before release of timer id to idr pool, we should make sure do_schedule_next_timer() wont be called, or it could find another timer reusing the just released id.

kernel/posix-timers.c +0 -0
index 4556182..4369747 100644
@@ -502,14 +502,14 @@ static void k_itimer_rcu_free(struct rcu_head *head)
 #define IT_ID_NOT_SET	0
 static void release_posix_timer(struct k_itimer *tmr, int it_id_set)
 {

kernel/posix-timers.c static void k_itimer_rcu_free(struct rcu_head *head) · line 512

Quoted 10 lines
kernel/posix-timers.c +2 -2
+	put_pid(tmr->it_pid);
+	sigqueue_free(tmr->sigq);
 	if (it_id_set) {
 		unsigned long flags;
 		spin_lock_irqsave(&idr_lock, flags);
 		idr_remove(&posix_timers_id, tmr->it_id);
 		spin_unlock_irqrestore(&idr_lock, flags);
 	}
-	put_pid(tmr->it_pid);
-	sigqueue_free(tmr->sigq);

I don't think this can make any difference. We simply can't guarantee do_schedule_next_timer() won't be called.

We could mark tmr->sigq as "invalid", but even this can't help. Suppose that the task has already dequeued the __SI_TIMER signal, now it plays withe the copy of tmr->sigq.

Oleg.

#21 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

In reply to Eric Dumazet
Quoted 12 lines · Eric Dumazet
Quoted 11 lines · Oleg Nesterov
Quoted 7 lines · Andi Kleen
Quoted 5 lines

I forgot everything I knew about ->it_requeue_pending logic, but it seems to me that do_schedule_next_timer()->lock_timer() can find and lock successfully the wrong timer. Another thread can do timer_delete() and then re-create the timer with the same id.

Do you mean after my patches or even before?

Ah, sorry for confusion.

Quoted 8 lines
Quoted 2 lines

Before. And after. IOW, I think this has nothing to do with your patches.

Hmm, you mean following patch is needed ?

Before release of timer id to idr pool, we should make sure do_schedule_next_timer() wont be called, or it could find another timer reusing the just released id.

I don't see how that makes it sure. If the signal is queued, then it stays queued and the put_pid() has no effect either.

Thanks,

tglx

Quoted 25 lines
kernel/posix-timers.c +2 -2
index 4556182..4369747 100644
@@ -502,14 +502,14 @@ static void k_itimer_rcu_free(struct rcu_head *head)
 #define IT_ID_NOT_SET	0
 static void release_posix_timer(struct k_itimer *tmr, int it_id_set)
 {
+	put_pid(tmr->it_pid);
+	sigqueue_free(tmr->sigq);
 	if (it_id_set) {
 		unsigned long flags;
 		spin_lock_irqsave(&idr_lock, flags);
 		idr_remove(&posix_timers_id, tmr->it_id);
 		spin_unlock_irqrestore(&idr_lock, flags);
 	}
-	put_pid(tmr->it_pid);
-	sigqueue_free(tmr->sigq);
 	call_rcu(&tmr->it.rcu, k_itimer_rcu_free);
 }
 
#22 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

Quoted 18 lines · Thomas Gleixner
Quoted 15 lines · Eric Dumazet
Quoted 13 lines · Oleg Nesterov
Quoted 7 lines · Andi Kleen
Quoted 5 lines

I forgot everything I knew about ->it_requeue_pending logic, but it seems to me that do_schedule_next_timer()->lock_timer() can find and lock successfully the wrong timer. Another thread can do timer_delete() and then re-create the timer with the same id.

Do you mean after my patches or even before?

Ah, sorry for confusion.

Before. And after. IOW, I think this has nothing to do with your patches.

Quoted 8 lines
Quoted 5 lines

Hmm, you mean following patch is needed ?

Before release of timer id to idr pool, we should make sure do_schedule_next_timer() wont be called, or it could find another timer reusing the just released id.

I don't see how that makes it sure. If the signal is queued, then it stays queued and the put_pid() has no effect either.

Yes.

But "If the signal is queued" is simple, in this case we could, say, do "tmr->sigq->info.si_tid = -1" to ensure lock_timer()->find_idr() can't succeed after dequeue_signal().

The problem is, it can be already dequeued.

Oleg.

#23 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

Quoted 28 lines · Oleg Nesterov
Quoted 18 lines · Thomas Gleixner
Quoted 15 lines · Eric Dumazet
Quoted 13 lines · Oleg Nesterov
Quoted 7 lines · Andi Kleen
Quoted 5 lines

I forgot everything I knew about ->it_requeue_pending logic, but it seems to me that do_schedule_next_timer()->lock_timer() can find and lock successfully the wrong timer. Another thread can do timer_delete() and then re-create the timer with the same id.

Do you mean after my patches or even before?

Ah, sorry for confusion.

Before. And after. IOW, I think this has nothing to do with your patches.

Quoted 8 lines
Quoted 5 lines

Hmm, you mean following patch is needed ?

Before release of timer id to idr pool, we should make sure do_schedule_next_timer() wont be called, or it could find another timer reusing the just released id.

I don't see how that makes it sure. If the signal is queued, then it stays queued and the put_pid() has no effect either.

Quoted 7 lines

Yes.

But "If the signal is queued" is simple, in this case we could, say, do "tmr->sigq->info.si_tid = -1" to ensure lock_timer()->find_idr() can't succeed after dequeue_signal().

The problem is, it can be already dequeued.

Right, but we can solve this by moving the whole detach code into rcu.

Subject: posix-timer-fix-detach-race.patch
From: Thomas Gleixner <[email protected]>
Date: Tue, 06 Sep 2011 21:08:06 +0200

---
 kernel/posix-timers.c |   26 +++++++++++++++++---------
 1 file changed, 17 insertions(+), 9 deletions(-)
kernel/posix-timers.c +17 -9
Index: linux-2.6/kernel/posix-timers.c
===================================================================
@@ -495,22 +495,30 @@ static void k_itimer_rcu_free(struct rcu
 {
 	struct k_itimer *tmr = container_of(head, struct k_itimer, it.rcu);
 
+	put_pid(tmr->it_pid);
+	sigqueue_free(tmr->sigq);
 	kmem_cache_free(posix_timers_cache, tmr);
 }
 
+static void k_itimer_rcu_free_idr(struct rcu_head *head)
+{
+	struct k_itimer *tmr = container_of(head, struct k_itimer, it.rcu);
+	unsigned long flags;
+
+	spin_lock_irqsave(&idr_lock, flags);
+	idr_remove(&posix_timers_id, tmr->it_id);
+	spin_unlock_irqrestore(&idr_lock, flags);
+	k_itimer_rcu_free(head);
+}
+
 #define IT_ID_SET	1
 #define IT_ID_NOT_SET	0
 static void release_posix_timer(struct k_itimer *tmr, int it_id_set)
 {
-	if (it_id_set) {
-		unsigned long flags;
-		spin_lock_irqsave(&idr_lock, flags);
-		idr_remove(&posix_timers_id, tmr->it_id);
-		spin_unlock_irqrestore(&idr_lock, flags);
-	}
-	put_pid(tmr->it_pid);
-	sigqueue_free(tmr->sigq);
-	call_rcu(&tmr->it.rcu, k_itimer_rcu_free);
+	if (it_id_set)
+		call_rcu(&tmr->it.rcu, k_itimer_rcu_free_idr);
+	else
+		call_rcu(&tmr->it.rcu, k_itimer_rcu_free);
 }
 
 static struct k_clock *clockid_to_kclock(const clockid_t id)
#24 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

Quoted 6 lines · Thomas Gleixner
Quoted 2 lines · Oleg Nesterov

The problem is, it can be already dequeued.

Right, but we can solve this by moving the whole detach code into rcu.

Hmm, I don't understand...

kernel/posix-timers.c static void k_itimer_rcu_free(struct rcu · line 500

Quoted 9 lines
kernel/posix-timers.c +2 -0
@@ -495,22 +495,30 @@ static void k_itimer_rcu_free(struct rcu
 {
 	struct k_itimer *tmr = container_of(head, struct k_itimer, it.rcu);
 
+	put_pid(tmr->it_pid);
+	sigqueue_free(tmr->sigq);
 	kmem_cache_free(posix_timers_cache, tmr);

Why do we need to move put_pid/sigqueue_free ?

The caller of release_posix_timer() should cancel the timer, we can can do this even before idr_remove() with or without this patch.

kernel/posix-timers.c static void k_itimer_rcu_free(struct rcu · line 519

Quoted 13 lines
kernel/posix-timers.c +2 -9
 static void release_posix_timer(struct k_itimer *tmr, int it_id_set)
 {
-	if (it_id_set) {
-		unsigned long flags;
-		spin_lock_irqsave(&idr_lock, flags);
-		idr_remove(&posix_timers_id, tmr->it_id);
-		spin_unlock_irqrestore(&idr_lock, flags);
-	}
-	put_pid(tmr->it_pid);
-	sigqueue_free(tmr->sigq);
-	call_rcu(&tmr->it.rcu, k_itimer_rcu_free);
+	if (it_id_set)
+		call_rcu(&tmr->it.rcu, k_itimer_rcu_free_idr);

But how this can help? Suppose that the task is preempted right after dequeue_signal() drops ->siglock. We need rcu_read_lock() before unlock then, no?

And. This breaks the accounting logic. I mean the patch from Andi which adds the limits.

Oleg.

#25 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

Quoted 16 lines · Oleg Nesterov
Quoted 6 lines · Thomas Gleixner
Quoted 2 lines · Oleg Nesterov

The problem is, it can be already dequeued.

Right, but we can solve this by moving the whole detach code into rcu.

Hmm, I don't understand...

Quoted 6 lines
kernel/posix-timers.c +0 -0
@@ -495,22 +495,30 @@ static void k_itimer_rcu_free(struct rcu
 {
 	struct k_itimer *tmr = container_of(head, struct k_itimer, it.rcu);
 
Quoted 8 lines

kernel/posix-timers.c static void k_itimer_rcu_free(struct rcu · line 500

Quoted 3 lines
kernel/posix-timers.c +2 -0
+	put_pid(tmr->it_pid);
+	sigqueue_free(tmr->sigq);
 	kmem_cache_free(posix_timers_cache, tmr);

Why do we need to move put_pid/sigqueue_free ?

The caller of release_posix_timer() should cancel the timer, we can can do this even before idr_remove() with or without this patch.

All callers cancel the timer. Right, put_pid() and sigqueue_free() can stay where they are.

Quoted 9 lines
Quoted 9 lines
kernel/posix-timers.c +0 -7
 static void release_posix_timer(struct k_itimer *tmr, int it_id_set)
 {
-	if (it_id_set) {
-		unsigned long flags;
-		spin_lock_irqsave(&idr_lock, flags);
-		idr_remove(&posix_timers_id, tmr->it_id);
-		spin_unlock_irqrestore(&idr_lock, flags);
-	}
-	put_pid(tmr->it_pid);
Quoted 8 lines

kernel/posix-timers.c static void k_itimer_rcu_free(struct rcu · line 519

Quoted 4 lines
kernel/posix-timers.c +2 -2
-	sigqueue_free(tmr->sigq);
-	call_rcu(&tmr->it.rcu, k_itimer_rcu_free);
+	if (it_id_set)
+		call_rcu(&tmr->it.rcu, k_itimer_rcu_free_idr);

But how this can help? Suppose that the task is preempted right after dequeue_signal() drops ->siglock. We need rcu_read_lock() before unlock then, no?

Crap, you are right, but that's fortunately an easy to solve one :)

Quoted 2 lines

And. This breaks the accounting logic. I mean the patch from Andi which adds the limits.

That's a different problem and really, it does not break it by any means. When the timer is released, then the count is decreased and we can safely assume that the memory is going to be freed in the next grace period. If that's not the case, then we have a totally different problem which is not fixable by any limits to the number of timers per process.

Thanks,

tglx

#26 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

Quoted 8 lines · Thomas Gleixner
Quoted 3 lines · Oleg Nesterov

But how this can help? Suppose that the task is preempted right after dequeue_signal() drops ->siglock. We need rcu_read_lock() before unlock then, no?

Crap, you are right, but that's fortunately an easy to solve one :)

Yes, this is solvable. But I think we can do something better.

Quoted 7 lines
Quoted 2 lines

And. This breaks the accounting logic. I mean the patch from Andi which adds the limits.

That's a different problem and really, it does not break it by any means. When the timer is released, then the count is decreased and we can safely assume that the memory is going to be freed in the next grace period.

Yes, but this means we need the counter which we do not have.

I think we can avoid this problems. Although I am not sure, I am already sleeping.

	- we add rcu_read_lock() into dequeueu_signal().

	- we add the new "struct k_itimer *my_timer" member into
	 siginfo._timer. Like _sys_private it is not passed to
	 user, and perhaps we can kill _sys_private later.

	 It is initialized in sys_timer_create() along with
	 info.si_tid/etc

	- release_posix_timer() nullifies tmr->sigq->my_timer

	- do_schedule_next_timer() does

	 	timr = info->my_timer;
	 	if (!timr)
	 		return;

		// protected by rcu

	 	spin_lock_irq(timr->it_lock);
	 	if (!timr->it_signal) {
	 		spin_unlock_irq();
	 		return;
	 	}

	 	....

This also avoids idr_find(), and we do not need to delay idr_remove().

Possible?

Oleg.

#27 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

Quoted 52 lines · Oleg Nesterov
Quoted 8 lines · Thomas Gleixner
Quoted 3 lines · Oleg Nesterov

But how this can help? Suppose that the task is preempted right after dequeue_signal() drops ->siglock. We need rcu_read_lock() before unlock then, no?

Crap, you are right, but that's fortunately an easy to solve one :)

Yes, this is solvable. But I think we can do something better.

Quoted 7 lines
Quoted 2 lines

And. This breaks the accounting logic. I mean the patch from Andi which adds the limits.

That's a different problem and really, it does not break it by any means. When the timer is released, then the count is decreased and we can safely assume that the memory is going to be freed in the next grace period.

Yes, but this means we need the counter which we do not have.

I think we can avoid this problems. Although I am not sure, I am already sleeping.

	- we add rcu_read_lock() into dequeueu_signal().

	- we add the new "struct k_itimer *my_timer" member into
	 siginfo._timer. Like _sys_private it is not passed to
	 user, and perhaps we can kill _sys_private later.

	 It is initialized in sys_timer_create() along with
	 info.si_tid/etc

	- release_posix_timer() nullifies tmr->sigq->my_timer

	- do_schedule_next_timer() does

	 	timr = info->my_timer;
	 	if (!timr)
	 		return;

		// protected by rcu

	 	spin_lock_irq(timr->it_lock);
	 	if (!timr->it_signal) {
	 		spin_unlock_irq();
	 		return;
	 	}

	 	....
Quoted 3 lines

This also avoids idr_find(), and we do not need to delay idr_remove().

Possible?

Sounds reasonable, though I have the same sleep deprivation problem as you :) Will have a closer look when awake.

Thanks,

tglx

#28 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

In reply to Oleg Nesterov
Quoted 22 lines · Oleg Nesterov
Quoted 8 lines · Thomas Gleixner
Quoted 3 lines · Oleg Nesterov

But how this can help? Suppose that the task is preempted right after dequeue_signal() drops ->siglock. We need rcu_read_lock() before unlock then, no?

Crap, you are right, but that's fortunately an easy to solve one :)

Yes, this is solvable. But I think we can do something better.

Quoted 7 lines
Quoted 2 lines

And. This breaks the accounting logic. I mean the patch from Andi which adds the limits.

That's a different problem and really, it does not break it by any means. When the timer is released, then the count is decreased and we can safely assume that the memory is going to be freed in the next grace period.

Yes, but this means we need the counter which we do not have.

Quoted 8 lines

I think we can avoid this problems. Although I am not sure, I am already sleeping.

- we add rcu_read_lock() into dequeueu_signal().

- we add the new "struct k_itimer *my_timer" member into siginfo._timer. Like _sys_private it is not passed to user, and perhaps we can kill _sys_private later.

sys_private is ugly as hell and we should avoid to add another field to siginfo.

I think we can embed the timer siginfo into k_itimer instead and provide a proper init function in signal.c. We always allocate a siginfo for a timer so we are better of allocating that stuff at once.

That way we can use container_of() and check the timer fields directly. That moves sys_private info k_itimer, gets rid of the idr lookup and avoids an extra siginfo field.

Further this would allow us to distangle the posixtimer rlimit from the sigpending rlimit, once we have that in place.

Thanks,

tglx

#29 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

Quoted 28 lines · Thomas Gleixner
Quoted 27 lines · Oleg Nesterov
Quoted 8 lines · Thomas Gleixner
Quoted 3 lines · Oleg Nesterov

But how this can help? Suppose that the task is preempted right after dequeue_signal() drops ->siglock. We need rcu_read_lock() before unlock then, no?

Crap, you are right, but that's fortunately an easy to solve one :)

Yes, this is solvable. But I think we can do something better.

Quoted 7 lines
Quoted 2 lines

And. This breaks the accounting logic. I mean the patch from Andi which adds the limits.

That's a different problem and really, it does not break it by any means. When the timer is released, then the count is decreased and we can safely assume that the memory is going to be freed in the next grace period.

Yes, but this means we need the counter which we do not have.

I think we can avoid this problems. Although I am not sure, I am already sleeping.

- we add rcu_read_lock() into dequeueu_signal().

Quoted 8 lines
Quoted 3 lines

- we add the new "struct k_itimer *my_timer" member into siginfo._timer. Like _sys_private it is not passed to user, and perhaps we can kill _sys_private later.

sys_private is ugly as hell and we should avoid to add another field to siginfo.

I think we can embed the timer siginfo into k_itimer instead and

That should be sigqeue of course, which has siginfo embedded.

Thanks,

tglx

#30 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

Quoted 33 lines · Thomas Gleixner
Quoted 32 lines · Thomas Gleixner
Quoted 30 lines · Oleg Nesterov
Quoted 8 lines · Thomas Gleixner
Quoted 3 lines · Oleg Nesterov

But how this can help? Suppose that the task is preempted right after dequeue_signal() drops ->siglock. We need rcu_read_lock() before unlock then, no?

Crap, you are right, but that's fortunately an easy to solve one :)

Yes, this is solvable. But I think we can do something better.

Quoted 7 lines
Quoted 2 lines

And. This breaks the accounting logic. I mean the patch from Andi which adds the limits.

That's a different problem and really, it does not break it by any means. When the timer is released, then the count is decreased and we can safely assume that the memory is going to be freed in the next grace period.

Yes, but this means we need the counter which we do not have.

I think we can avoid this problems. Although I am not sure, I am already sleeping.

- we add rcu_read_lock() into dequeueu_signal().

- we add the new "struct k_itimer *my_timer" member into siginfo._timer. Like _sys_private it is not passed to user, and perhaps we can kill _sys_private later.

Quoted 6 lines
Quoted 4 lines

sys_private is ugly as hell and we should avoid to add another field to siginfo.

I think we can embed the timer siginfo into k_itimer instead and

That should be sigqeue of course, which has siginfo embedded.

Bah, dequeue_signal only gets the copy of the siginfo. So we need to do something about that in any case (*my_timer or embedded sigqueue).

Thanks,

tglx

#31 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

In reply to Thomas Gleixner
Quoted 31 lines · Thomas Gleixner
Quoted 30 lines · Oleg Nesterov
Quoted 18 lines · Thomas Gleixner
Quoted 15 lines · Eric Dumazet
Quoted 13 lines · Oleg Nesterov
Quoted 7 lines · Andi Kleen
Quoted 5 lines

I forgot everything I knew about ->it_requeue_pending logic, but it seems to me that do_schedule_next_timer()->lock_timer() can find and lock successfully the wrong timer. Another thread can do timer_delete() and then re-create the timer with the same id.

Do you mean after my patches or even before?

Ah, sorry for confusion.

Before. And after. IOW, I think this has nothing to do with your patches.

Quoted 8 lines
Quoted 5 lines

Hmm, you mean following patch is needed ?

Before release of timer id to idr pool, we should make sure do_schedule_next_timer() wont be called, or it could find another timer reusing the just released id.

I don't see how that makes it sure. If the signal is queued, then it stays queued and the put_pid() has no effect either.

Yes.

Quoted 8 lines
Quoted 5 lines

But "If the signal is queued" is simple, in this case we could, say, do "tmr->sigq->info.si_tid = -1" to ensure lock_timer()->find_idr() can't succeed after dequeue_signal().

The problem is, it can be already dequeued.

Right, but we can solve this by moving the whole detach code into rcu.

Why ? Is the dequeue thing guaranteed in the rcu grace period ?

ALso, delaying the idr_remove() probably makes next Andi patch more complex (move global timer id management to signal_struct)

struct k_itimer will need a backpointer to signal_struct, and an additional refcount on it.

Quoted 53 lines

Subject: posix-timer-fix-detach-race.patch
From: Thomas Gleixner <[email protected]>
Date: Tue, 06 Sep 2011 21:08:06 +0200

---
 kernel/posix-timers.c |   26 +++++++++++++++++---------
 1 file changed, 17 insertions(+), 9 deletions(-)

Index: linux-2.6/kernel/posix-timers.c
===================================================================

kernel/posix-timers.c +17 -9
@@ -495,22 +495,30 @@ static void k_itimer_rcu_free(struct rcu
 {
 	struct k_itimer *tmr = container_of(head, struct k_itimer, it.rcu);
 
+	put_pid(tmr->it_pid);
+	sigqueue_free(tmr->sigq);
 	kmem_cache_free(posix_timers_cache, tmr);
 }
 
+static void k_itimer_rcu_free_idr(struct rcu_head *head)
+{
+	struct k_itimer *tmr = container_of(head, struct k_itimer, it.rcu);
+	unsigned long flags;
+
+	spin_lock_irqsave(&idr_lock, flags);
+	idr_remove(&posix_timers_id, tmr->it_id);
+	spin_unlock_irqrestore(&idr_lock, flags);
+	k_itimer_rcu_free(head);
+}
+
 #define IT_ID_SET	1
 #define IT_ID_NOT_SET	0
 static void release_posix_timer(struct k_itimer *tmr, int it_id_set)
 {
-	if (it_id_set) {
-		unsigned long flags;
-		spin_lock_irqsave(&idr_lock, flags);
-		idr_remove(&posix_timers_id, tmr->it_id);
-		spin_unlock_irqrestore(&idr_lock, flags);
-	}
-	put_pid(tmr->it_pid);
-	sigqueue_free(tmr->sigq);
-	call_rcu(&tmr->it.rcu, k_itimer_rcu_free);
+	if (it_id_set)
+		call_rcu(&tmr->it.rcu, k_itimer_rcu_free_idr);
+	else
+		call_rcu(&tmr->it.rcu, k_itimer_rcu_free);
 }
 
 static struct k_clock *clockid_to_kclock(const clockid_t id)
#32 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

Quoted 6 lines · Eric Dumazet
Quoted 3 lines · Thomas Gleixner

On Tue, 6 Sep 2011, Oleg Nesterov wrote:
Right, but we can solve this by moving the whole detach code into rcu.

Why ? Is the dequeue thing guaranteed in the rcu grace period ?

No, as Oleg pointed out we need an rcu_read_lock() in dequeue_signal()

Quoted 5 lines

ALso, delaying the idr_remove() probably makes next Andi patch more complex (move global timer id management to signal_struct)

struct k_itimer will need a backpointer to signal_struct, and an additional refcount on it.

Well, first of all we need that problem at hand to be fixed.

And the backpointer is not rocket science at all.

include/linux/posix-timers.h +4 -1
@@ -82,7 +82,10 @@ struct k_itimer {
 			unsigned long expires;
 		} mmtimer;
 		struct alarm alarmtimer;
-		struct rcu_head rcu;
+		struct {
+			struct rcu_head rcu;
+			struct signal_struct *it_signal;
+		} rcu;
 	} it;
 };
 

Solves that nicely and we still can get rid of the original *it_signal and rely on the list_head.

Vs. the refcounting, that should be solvable by a rcu_barrier() before

+ idr_destroy(&sig->posix_timers_id);

in exit_itimers().

Thanks,

tglx

#33 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

Quoted 5 lines · Thomas Gleixner

Vs. the refcounting, that should be solvable by a rcu_barrier() before

+ idr_destroy(&sig->posix_timers_id);

in exit_itimers().

Well, rcu_barrier() is too slow, please Andi dont try this :)

#34 lore raw

Re: [PATCH 4/4] posix-timers: turn it_signal into it_valid flag

In reply to Thomas Gleixner
Quoted 17 lines · Thomas Gleixner
Quoted 15 lines · Eric Dumazet
Quoted 13 lines · Oleg Nesterov
Quoted 7 lines · Andi Kleen
Quoted 5 lines

I forgot everything I knew about ->it_requeue_pending logic, but it seems to me that do_schedule_next_timer()->lock_timer() can find and lock successfully the wrong timer. Another thread can do timer_delete() and then re-create the timer with the same id.

Do you mean after my patches or even before?

Ah, sorry for confusion.

Before. And after. IOW, I think this has nothing to do with your patches.

Quoted 8 lines
Quoted 5 lines

Hmm, you mean following patch is needed ?

Before release of timer id to idr pool, we should make sure do_schedule_next_timer() wont be called, or it could find another timer reusing the just released id.

I don't see how that makes it sure. If the signal is queued, then it stays queued and the put_pid() has no effect either.

Indeed, this is a real old bug then...

#35 lore raw
In reply to Andi Kleen
Quoted 73 lines · Andi Kleen

From: Andi Kleen <[email protected]>

Move the global posix timer ids IDR to signal_struct. This removes a minor global scalability bottleneck and also allows to finally limit the number of process timers in a sane way (see next patch)

I put it into signal_struct following the other posix timer per process structures.

v2: Now with locking again (thanks Eric)

---
 include/linux/init_task.h |    3 +++
 include/linux/sched.h     |    4 ++++
 kernel/fork.c             |    2 ++
 kernel/posix-timers.c     |   23 ++++++++++++-----------
 4 files changed, 21 insertions(+), 11 deletions(-)
include/linux/init_task.h +3 -0
index d14e058..564248d 100644
@@ -10,6 +10,7 @@
 #include <linux/pid_namespace.h>
 #include <linux/user_namespace.h>
 #include <linux/securebits.h>
+#include <linux/idr.h>
 #include <net/net_namespace.h>
 
 #ifdef CONFIG_SMP
@@ -37,6 +38,7 @@ extern struct fs_struct init_fs;
 		.list = LIST_HEAD_INIT(sig.shared_pending.list),	\
 		.signal =  {{0}}},					\
 	.posix_timers	 = LIST_HEAD_INIT(sig.posix_timers),		\
+	.idr_lock	 = __SPIN_LOCK_UNLOCKED(idr_lock),		\
 	.cpu_timers	= INIT_CPU_TIMERS(sig.cpu_timers),		\
 	.rlim		= INIT_RLIMITS,					\
 	.cputimer	= { 						\
@@ -46,6 +48,7 @@ extern struct fs_struct init_fs;
 	},								\
 	.cred_guard_mutex =						\
 		 __MUTEX_INITIALIZER(sig.cred_guard_mutex),		\
+	.posix_timers_id = IDR_INIT(posix_timer_id),			\
 	INIT_THREADGROUP_FORK_LOCK(sig)					\
 }
 
include/linux/sched.h +4 -0
index 4ac2c05..87fa2fc 100644
@@ -62,6 +62,7 @@ struct sched_param {
 #include <linux/errno.h>
 #include <linux/nodemask.h>
 #include <linux/mm_types.h>
+#include <linux/idr.h>
 
 #include <asm/system.h>
 #include <asm/page.h>
@@ -652,6 +653,9 @@ struct signal_struct {
 	struct mutex cred_guard_mutex;	/* guard against foreign influences on
 					 * credential calculations
 					 * (notably. ptrace) */
+
+	struct idr posix_timers_id;
+	spinlock_t idr_lock;		/* Protect posix_timers_id writes */
 };
 
 /* Context switch must be unlocked if interrupts are to be enabled */
kernel/fork.c +0 -0
index 8e6b6f4..1054cfd 100644

kernel/fork.c static void posix_cpu_timers_init_group(struct signal_struct *sig) · line 947

Quoted 5 lines
kernel/fork.c +2 -0
@@ -943,6 +943,8 @@ static void posix_cpu_timers_init_group(struct signal_struct *sig)
 	INIT_LIST_HEAD(&sig->cpu_timers[0]);
 	INIT_LIST_HEAD(&sig->cpu_timers[1]);
 	INIT_LIST_HEAD(&sig->cpu_timers[2]);
+
+	idr_init(&sig->posix_timers_id);

I might miss something, but dont you also need to

	spin_lock_init(&sig->idr_lock);

Maybe you should try with LOCKDEP on ;)

author
#36 lore raw
Quoted 5 lines

I might miss something, but dont you also need to

	spin_lock_init(&sig->idr_lock);

Maybe you should try with LOCKDEP on ;)

Yes I should. Fixed thanks.
-Andi

#37 lore raw
In reply to Andi Kleen

On Mon, 29 Aug 2011, Andi Kleen wrote:

Hint: Ccing maintainers of affected code might help to get code
reviewed and eventually merged.

include/linux/init_task.h line 13

Quoted 9 lines
include/linux/init_task.h +1 -0
index d14e058..564248d 100644
@@ -10,6 +10,7 @@
 #include <linux/pid_namespace.h>
 #include <linux/user_namespace.h>
 #include <linux/securebits.h>
+#include <linux/idr.h>

New line please.

include/linux/init_task.h extern struct fs_struct init_fs; · line 41

Quoted 8 lines
include/linux/init_task.h +1 -0
 #include <net/net_namespace.h>
 
 #ifdef CONFIG_SMP
@@ -37,6 +38,7 @@ extern struct fs_struct init_fs;
 		.list = LIST_HEAD_INIT(sig.shared_pending.list),	\
 		.signal =  {{0}}},					\
 	.posix_timers	 = LIST_HEAD_INIT(sig.posix_timers),		\
+	.idr_lock	 = __SPIN_LOCK_UNLOCKED(idr_lock),		\

sig.idr_lock

Also is there a requirement, that this is a spinlock? AFAICT it's all process context and slowpath, so we can make it a mutex.

include/linux/init_task.h extern struct fs_struct init_fs; · line 51

Quoted 8 lines
include/linux/init_task.h +1 -0
 	.cpu_timers	= INIT_CPU_TIMERS(sig.cpu_timers),		\
 	.rlim		= INIT_RLIMITS,					\
 	.cputimer	= { 						\
@@ -46,6 +48,7 @@ extern struct fs_struct init_fs;
 	},								\
 	.cred_guard_mutex =						\
 		 __MUTEX_INITIALIZER(sig.cred_guard_mutex),		\
+	.posix_timers_id = IDR_INIT(posix_timer_id),			\

sig.posix_timer_id

include/linux/init_task.h SYSCALL_DEFINE3(timer_create, const clockid_t, which_clock, · line 542

Quoted 8 lines
include/linux/init_task.h +1 -0
 	INIT_THREADGROUP_FORK_LOCK(sig)					\
 }
 
@@ -541,6 +539,7 @@ SYSCALL_DEFINE3(timer_create, const clockid_t, which_clock,
 	int error, new_timer_id;
 	sigevent_t event;
 	int it_id_set = IT_ID_NOT_SET;
+	struct signal_struct *s = current->signal;

*sig please, cryptic variable names are a PITA.

Thanks,

tglx

#38 lore raw
Quoted 17 lines · Thomas Gleixner

On Mon, 29 Aug 2011, Andi Kleen wrote:

Hint: Ccing maintainers of affected code might help to get code
reviewed and eventually merged.

include/linux/init_task.h extern struct fs_struct init_fs; · line 41

Quoted 8 lines

#include <net/net_namespace.h>

#ifdef CONFIG_SMP

include/linux/init_task.h +1 -0
@@ -37,6 +38,7 @@ extern struct fs_struct init_fs;
 		.list = LIST_HEAD_INIT(sig.shared_pending.list),	\
 		.signal =  {{0}}},					\
 	.posix_timers	 = LIST_HEAD_INIT(sig.posix_timers),		\
+	.idr_lock	 = __SPIN_LOCK_UNLOCKED(idr_lock),		\

sig.idr_lock

Quoted 2 lines

Also is there a requirement, that this is a spinlock? AFAICT it's all process context and slowpath, so we can make it a mutex.

If so, please Andi remove the idr_pre_get() call : This would be useless, since we are allowed to sleep under mutex.

This would lower the memory needs of a per-process idr pre-initted with IDR_FREE_MAX items in free list. This was OK for a system wide posix_timers_id.

author
#39 lore raw
In reply to Thomas Gleixner
Quoted 10 lines

include/linux/init_task.h extern struct fs_struct init_fs; · line 51

Quoted 8 lines
include/linux/init_task.h +1 -0
 	.cpu_timers	= INIT_CPU_TIMERS(sig.cpu_timers),		\
 	.rlim		= INIT_RLIMITS,					\
 	.cputimer	= { 						\
@@ -46,6 +48,7 @@ extern struct fs_struct init_fs;
 	},								\
 	.cred_guard_mutex =						\
 		 __MUTEX_INITIALIZER(sig.cred_guard_mutex),		\
+	.posix_timers_id = IDR_INIT(posix_timer_id),			\

sig.posix_timer_id

I don't understand this comment. This is already the signal_struct. Do you want double nesting?

-Andi