[PATCH 1/2] posix-timers: move global timer id management to signal_struct v4

[PATCH 1/2] posix-timers: move global timer id management to signal_struct v4

[Andi Kleen]

From: Andi Kleen <ak@linux.intel.com>

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)
v3: Fix the locking too (Eric Dumazet)
v4: Use a mutex. Get rid of retry loop.
idr_pre_get() is still there to avoid major surgery in lib/idr.c.
Random gleixnerfication
Signed-off-by: Andi Kleen <ak@linux.intel.com>
---
 include/linux/init_task.h |    4 ++++
 include/linux/sched.h     |    4 ++++
 kernel/fork.c             |    3 +++
 kernel/posix-timers.c     |   32 ++++++++++++++------------------
 4 files changed, 25 insertions(+), 18 deletions(-)

diff --git a/include/linux/init_task.h b/include/linux/init_task.h
index d14e058..d84569d 100644
--- a/include/linux/init_task.h
+++ b/include/linux/init_task.h
@@ -10,6 +10,8 @@
 #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
@@ -46,6 +48,8 @@ extern struct fs_struct init_fs;
 	},								\
 	.cred_guard_mutex =						\
 		 __MUTEX_INITIALIZER(sig.cred_guard_mutex),		\
+	.posix_timers_id = IDR_INIT(posix_timer_id),			\
+	.idr_lock	 = __MUTEX_INITIALIZER(init_signals.idr_lock),  \
 	INIT_THREADGROUP_FORK_LOCK(sig)					\
 }
 
diff --git a/include/linux/sched.h b/include/linux/sched.h
index 4ac2c05..2d0b39f 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -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;
+	struct mutex idr_lock;		/* Protect posix_timers_id writes */
 };
 
 /* Context switch must be unlocked if interrupts are to be enabled */
diff --git a/kernel/fork.c b/kernel/fork.c
index 8e6b6f4..6693fc0 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -943,6 +943,9 @@ 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);
+	mutex_init(&sig->idr_lock);
 }
 
 static int copy_signal(unsigned long clone_flags, struct task_struct *tsk)
diff --git a/kernel/posix-timers.c b/kernel/posix-timers.c
index 4556182..f832021 100644
--- a/kernel/posix-timers.c
+++ b/kernel/posix-timers.c
@@ -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,10 @@ 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) {
-		unsigned long flags;
-		spin_lock_irqsave(&idr_lock, flags);
-		idr_remove(&posix_timers_id, tmr->it_id);
-		spin_unlock_irqrestore(&idr_lock, flags);
+		struct signal_struct *s = current->signal;
+		mutex_lock(&s->idr_lock);
+		idr_remove(&s->posix_timers_id, tmr->it_id);
+		mutex_unlock(&s->idr_lock);
 	}
 	put_pid(tmr->it_pid);
 	sigqueue_free(tmr->sigq);
@@ -541,6 +538,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 *sig = current->signal;
 
 	if (!kc)
 		return -EINVAL;
@@ -552,17 +550,13 @@ SYSCALL_DEFINE3(timer_create, const clockid_t, which_clock,
 		return -EAGAIN;
 
 	spin_lock_init(&new_timer->it_lock);
- retry:
-	if (unlikely(!idr_pre_get(&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);
+	mutex_lock(&sig->idr_lock);
+	error = -EAGAIN;
+	if (idr_pre_get(&sig->posix_timers_id, GFP_KERNEL))
+		error = idr_get_new(&sig->posix_timers_id, new_timer, 
+				    &new_timer_id);
+	mutex_unlock(&sig->idr_lock);
 	if (error) {
-		if (error == -EAGAIN)
-			goto retry;
 		/*
 		 * Weird looking, but we return EAGAIN if the IDR is
 		 * full (proper POSIX return value for this)
@@ -638,9 +632,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 +940,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,
-- 
1.7.4.4

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

[Andi Kleen]

From: Andi Kleen <ak@linux.intel.com>

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.

Uses a rlimit to limit the number of timers.

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

v2: Use a rlimit instead of sysctl
Signed-off-by: Andi Kleen <ak@linux.intel.com>
---
 fs/proc/base.c                 |    1 +
 include/asm-generic/resource.h |    4 +++-
 include/linux/limits.h         |    1 +
 kernel/posix-timers.c          |    6 ++++++
 4 files changed, 11 insertions(+), 1 deletions(-)

diff --git a/fs/proc/base.c b/fs/proc/base.c
index 5eb0206..229ec4e 100644
--- a/fs/proc/base.c
+++ b/fs/proc/base.c
@@ -511,6 +511,7 @@ static const struct limit_names lnames[RLIM_NLIMITS] = {
 	[RLIMIT_NICE] = {"Max nice priority", NULL},
 	[RLIMIT_RTPRIO] = {"Max realtime priority", NULL},
 	[RLIMIT_RTTIME] = {"Max realtime timeout", "us"},
+	[RLIMIT_POSIX_TIMERS] = {"Max number of POSIX timers", "timers"},
 };
 
 /* Display limits for a process */
diff --git a/include/asm-generic/resource.h b/include/asm-generic/resource.h
index 61fa862..9fde1b5 100644
--- a/include/asm-generic/resource.h
+++ b/include/asm-generic/resource.h
@@ -45,7 +45,8 @@
 					   0-39 for nice level 19 .. -20 */
 #define RLIMIT_RTPRIO		14	/* maximum realtime priority */
 #define RLIMIT_RTTIME		15	/* timeout for RT tasks in us */
-#define RLIM_NLIMITS		16
+#define RLIMIT_POSIX_TIMERS	16	/* max number of posix timers/process */
+#define RLIM_NLIMITS		17
 
 /*
  * SuS says limits have to be unsigned.
@@ -87,6 +88,7 @@
 	[RLIMIT_NICE]		= { 0, 0 },				\
 	[RLIMIT_RTPRIO]		= { 0, 0 },				\
 	[RLIMIT_RTTIME]		= {  RLIM_INFINITY,  RLIM_INFINITY },	\
+	[RLIMIT_POSIX_TIMERS]	= { POSIX_TIMERS_LIM, POSIX_TIMERS_LIM }, \
 }
 
 #endif	/* __KERNEL__ */
diff --git a/include/linux/limits.h b/include/linux/limits.h
index 2d0f941..634a445 100644
--- a/include/linux/limits.h
+++ b/include/linux/limits.h
@@ -14,6 +14,7 @@
 #define XATTR_NAME_MAX   255	/* # chars in an extended attribute name */
 #define XATTR_SIZE_MAX 65536	/* size of an extended attribute value (64k) */
 #define XATTR_LIST_MAX 65536	/* size of extended attribute namelist (64k) */
+#define POSIX_TIMERS_LIM 1024   /* Number of posix timers process (default) */
 
 #define RTSIG_MAX	  32
 
diff --git a/kernel/posix-timers.c b/kernel/posix-timers.c
index f832021..9eb0a68 100644
--- a/kernel/posix-timers.c
+++ b/kernel/posix-timers.c
@@ -567,6 +567,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 >= rlimit(RLIMIT_POSIX_TIMERS)) {
+		error = -EPERM;
+		goto out;
+	}
+
 	new_timer->it_clock = which_clock;
 	new_timer->it_overrun = -1;
 
-- 
1.7.4.4

Re: [PATCH 1/2] posix-timers: move global timer id management to signal_struct v4

[Eric Dumazet]

Le lundi 19 septembre 2011 à 14:48 -0700, Andi Kleen a écrit :
> From: Andi Kleen <ak@linux.intel.com>
> 
> 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)
> v3: Fix the locking too (Eric Dumazet)
> v4: Use a mutex. Get rid of retry loop.
> idr_pre_get() is still there to avoid major surgery in lib/idr.c.
> Random gleixnerfication
> Signed-off-by: Andi Kleen <ak@linux.intel.com>
> ---

> +	mutex_lock(&sig->idr_lock);
> +	error = -EAGAIN;
> +	if (idr_pre_get(&sig->posix_timers_id, GFP_KERNEL))
> +		error = idr_get_new(&sig->posix_timers_id, new_timer, 
> +				    &new_timer_id);
> +	mutex_unlock(&sig->idr_lock);
>  	if (error) {

On 64bit arches :

IDR_FREE_MAX=12 && sizeof(struct idr_layer)=544

This means idr_pre_get() consumes 6528 bytes of spare space per process,
even if only one posix timer is used.

I guess we should allow idr to call slab directly in this case (only a
mutex held, it's safe to sleep in slab), and not have this per idr
reserve/free_list : This was done because of some idr callers using a
spinlock.

I dont believe its major idr surgery :)

Re: [PATCH 1/2] posix-timers: move global timer id management to signal_struct v4

[Andi Kleen]

> This means idr_pre_get() consumes 6528 bytes of spare space per process,
> even if only one posix timer is used.

And? Given the now normal bloat level in the kernel that's small
potatoes.

The idr code is so messy that I don't really want to touch it.

If you think it is that important feel free to do a followon 
patch.

If it's that big a problem I'm sure a general solution would
be better than some quick hack for a special case.

-Andi

Re: [PATCH 1/2] posix-timers: move global timer id management to signal_struct v4

[Eric Dumazet]

Le mardi 20 septembre 2011 à 00:36 +0200, Andi Kleen a écrit :
> > This means idr_pre_get() consumes 6528 bytes of spare space per process,
> > even if only one posix timer is used.
> 
> And? Given the now normal bloat level in the kernel that's small
> potatoes.
> 

I see. Oh yes, you work for a known hardware vendor.

> The idr code is so messy that I don't really want to touch it.
> 
> If you think it is that important feel free to do a followon 
> patch.
> 
> If it's that big a problem I'm sure a general solution would
> be better than some quick hack for a special case.

I'll provide not a hack but a clean patch for this.

I read once idr code, and its not messy at all.

Re: [PATCH 1/2] posix-timers: move global timer id management to signal_struct v4

[Eric Dumazet]

Le mardi 20 septembre 2011 à 00:41 +0200, Eric Dumazet a écrit :

> I'll provide not a hack but a clean patch for this.
> 

Here is a draft, just in case. (not even booted, its late here...)

I'll test it tomorrow with a variant of your patch.


 include/linux/idr.h |   13 +++++++++++++
 lib/idr.c           |   32 +++++++++++++++++++++-----------
 2 files changed, 34 insertions(+), 11 deletions(-)

diff --git a/include/linux/idr.h b/include/linux/idr.h
index 255491c..a6b7655 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -64,6 +64,14 @@ struct idr {
 	spinlock_t	  lock;
 };
 
+/* special id_free_cnt value to mark idr without freelist */
+#define IDR_NOFREELIST -1
+
+static inline bool idr_nofreelist(const struct idr *idr)
+{
+	return idr->id_free_cnt == IDR_NOFREELIST;
+}
+
 #define IDR_INIT(name)						\
 {								\
 	.top		= NULL,					\
@@ -114,6 +122,11 @@ void idr_remove_all(struct idr *idp);
 void idr_destroy(struct idr *idp);
 void idr_init(struct idr *idp);
 
+static inline void idr_nofreelist_init(struct idr *idp)
+{
+	idr_init(idp);
+	idp->id_free_cnt = IDR_NOFREELIST;
+}
 
 /*
  * IDA - IDR based id allocator, use when translation from id to
diff --git a/lib/idr.c b/lib/idr.c
index db040ce..d4ce74d 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -44,6 +44,9 @@ static struct idr_layer *get_from_free_list(struct idr *idp)
 	struct idr_layer *p;
 	unsigned long flags;
 
+	if (idr_nofreelist(idp))
+		return kmem_cache_zalloc(idr_layer_cache, GFP_KERNEL);
+
 	spin_lock_irqsave(&idp->lock, flags);
 	if ((p = idp->id_free)) {
 		idp->id_free = p->ary[0];
@@ -77,14 +80,17 @@ static void __move_to_free_list(struct idr *idp, struct idr_layer *p)
 
 static void move_to_free_list(struct idr *idp, struct idr_layer *p)
 {
-	unsigned long flags;
-
-	/*
-	 * Depends on the return element being zeroed.
-	 */
-	spin_lock_irqsave(&idp->lock, flags);
-	__move_to_free_list(idp, p);
-	spin_unlock_irqrestore(&idp->lock, flags);
+	if (idr_nofreelist(idp)) {
+		kmem_cache_free(idr_layer_cache, p);
+	} else {
+		unsigned long flags;
+		/*
+		 * Depends on the return element being zeroed.
+		 */
+		spin_lock_irqsave(&idp->lock, flags);
+		__move_to_free_list(idp, p);
+		spin_unlock_irqrestore(&idp->lock, flags);
+	}
 }
 
 static void idr_mark_full(struct idr_layer **pa, int id)
@@ -122,6 +128,7 @@ static void idr_mark_full(struct idr_layer **pa, int id)
  */
 int idr_pre_get(struct idr *idp, gfp_t gfp_mask)
 {
+	BUG_ON(idr_nofreelist(idp));
 	while (idp->id_free_cnt < IDR_FREE_MAX) {
 		struct idr_layer *new;
 		new = kmem_cache_zalloc(idr_layer_cache, gfp_mask);
@@ -243,7 +250,10 @@ build_up:
 				p = p->ary[0];
 				new->ary[0] = NULL;
 				new->bitmap = new->count = 0;
-				__move_to_free_list(idp, new);
+				if (idr_nofreelist(idp))
+					kmem_cache_free(idr_layer_cache, p);
+				else
+					__move_to_free_list(idp, new);
 			}
 			spin_unlock_irqrestore(&idp->lock, flags);
 			return -1;
@@ -487,7 +497,7 @@ EXPORT_SYMBOL(idr_remove_all);
  */
 void idr_destroy(struct idr *idp)
 {
-	while (idp->id_free_cnt) {
+	while (idp->id_free_cnt > 0) {
 		struct idr_layer *p = get_from_free_list(idp);
 		kmem_cache_free(idr_layer_cache, p);
 	}
@@ -839,7 +849,7 @@ int ida_get_new_above(struct ida *ida, int starting_id, int *p_id)
 	 * Throw away extra resources one by one after each successful
 	 * allocation.
 	 */
-	if (ida->idr.id_free_cnt || ida->free_bitmap) {
+	if (ida->idr.id_free_cnt > 0 || ida->free_bitmap) {
 		struct idr_layer *p = get_from_free_list(&ida->idr);
 		if (p)
 			kmem_cache_free(idr_layer_cache, p);

Re: [PATCH 1/2] posix-timers: move global timer id management to signal_struct v4

[Andi Kleen]

> I'll provide not a hack but a clean patch for this.

Great thanks.
> I read once idr code, and its not messy at all.
You're not serious right? Especially the locking scheme is just
a extreme mess:

sometimes takes a lock, sometimes requires locking from the caller
even though the internal lock should be fine, sometimes uses unlocked 
bitmap
operations outside a lock, all mixed with a partial RCU implementation,
no assumption is documented of course.  etc.etc. It's a great poster child
for messy kernel code.

I read the code and I would be afraid touching it.

-Andi

Re: [PATCH 1/2] posix-timers: move global timer id management to signal_struct v4

[Eric Dumazet]

Le lundi 19 septembre 2011 à 16:11 -0700, Andi Kleen a écrit :
> > I'll provide not a hack but a clean patch for this.
> 
> Great thanks.
> > I read once idr code, and its not messy at all.
> You're not serious right? Especially the locking scheme is just
> a extreme mess:
> 
> sometimes takes a lock, sometimes requires locking from the caller
> even though the internal lock should be fine, sometimes uses unlocked 
> bitmap
> operations outside a lock, all mixed with a partial RCU implementation,
> no assumption is documented of course.  etc.etc. It's a great poster child
> for messy kernel code.
> 

I dont know, I met more complex code in kernel, but I wont say where ;)

Re: [PATCH 1/2] posix-timers: move global timer id management to signal_struct v4

[Thomas Gleixner]

On Mon, 19 Sep 2011, Andi Kleen wrote:
> From: Andi Kleen <ak@linux.intel.com>
> 
> 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)
> v3: Fix the locking too (Eric Dumazet)
> v4: Use a mutex. Get rid of retry loop.
> idr_pre_get() is still there to avoid major surgery in lib/idr.c.
> Random gleixnerfication

I could laugh about that if you've had actually addressed my review
comments proper.

>  #ifdef CONFIG_SMP
> @@ -46,6 +48,8 @@ extern struct fs_struct init_fs;
>  	},								\
>  	.cred_guard_mutex =						\
>  		 __MUTEX_INITIALIZER(sig.cred_guard_mutex),		\
> +	.posix_timers_id = IDR_INIT(posix_timer_id),			\
> +	.idr_lock	 = __MUTEX_INITIALIZER(init_signals.idr_lock),  \

Hint: I even gave you the proper arguments for both initializers last
time.

So the above should be: Random sloppyfication.

Andi, seriously. Your signal to noise ratio has become annoying
again. We've been there before and you are on the verge of entering
the ignore list again.

Thanks,

	tglx

Re: [PATCH 1/2] posix-timers: move global timer id management to signal_struct v4

[Thomas Gleixner]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1195 bytes --]

On Tue, 20 Sep 2011, Eric Dumazet wrote:

> Le mardi 20 septembre 2011 à 00:36 +0200, Andi Kleen a écrit :
> > > This means idr_pre_get() consumes 6528 bytes of spare space per process,
> > > even if only one posix timer is used.
> > 
> > And? Given the now normal bloat level in the kernel that's small
> > potatoes.

That's not really a good excuse to create more bloat without spending
a few brain cycles.

> I see. Oh yes, you work for a known hardware vendor.

LOL

Aside of that this patch already adds sizeof(idr) + sizeof(mutex) to
every signal_struct unconditionally. There is no reason to do that. We
simply can have a pointer to

struct posix_timer_idr {
	struct mutex lock;
	struct idr idr;
};

and allocate that when a process creates the first posix timer.

Thinking more about that the question arises whether the global idr is
in fact a real scalability issue. The number of posix timers actually
used is usually pretty low and I doubt that they are created/deleted
with high frequency.

If it's just about limiting the per process posix timer allocation we
can achieve the same goal with a simple per process counter which
holds the number of allocated timers.

Thanks,

	tglx