Skip to contentSkip to conversation

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

PATCH In review Andi Kleen 4 participants 10 messages Sep 19, 2011 – Sep 20, 2011

Subsystems (7)
lore
Share & tools
lore

Andi Kleen

author
#0 lore raw

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

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)
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

---
 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(-)
include/linux/init_task.h +4 -0
index d14e058..d84569d 100644
@@ -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)					\
 }
 
include/linux/sched.h +4 -0
index 4ac2c05..2d0b39f 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;
+	struct mutex idr_lock;		/* Protect posix_timers_id writes */
 };
 
 /* Context switch must be unlocked if interrupts are to be enabled */
kernel/fork.c +3 -0
index 8e6b6f4..6693fc0 100644
@@ -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)
kernel/posix-timers.c +14 -18
index 4556182..f832021 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,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,
Signature · 1 line
1.7.4.4
author
#1 lore raw

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

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.

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

---
 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(-)
fs/proc/base.c +1 -0
index 5eb0206..229ec4e 100644
@@ -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 */
include/asm-generic/resource.h +3 -1
index 61fa862..9fde1b5 100644
@@ -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__ */
include/linux/limits.h +1 -0
index 2d0f941..634a445 100644
@@ -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
 
kernel/posix-timers.c +6 -0
index f832021..9eb0a68 100644
@@ -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;
 
Signature · 1 line
1.7.4.4
#2 lore raw
In reply to Andi Kleen
Quoted 17 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)
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

---

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

Quoted 7 lines
kernel/posix-timers.c +6 -0
+	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 :)

author
#3 lore raw
Quoted 2 lines

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

#4 lore raw
Quoted 6 lines · Andi Kleen
Quoted 2 lines

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.

Quoted 7 lines

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.

#5 lore raw
Quoted 2 lines · Eric Dumazet

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(-)
include/linux/idr.h +13 -0
index 255491c..a6b7655 100644
@@ -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
lib/idr.c +21 -11
index db040ce..d4ce74d 100644
@@ -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);
#6 lore raw
In reply to Eric Dumazet
Quoted 2 lines

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

Great thanks.

Quoted 1 line

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

#7 lore raw
Quoted 7 lines · Andi Kleen
Quoted 1 line

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

Great thanks.

Quoted 1 line

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:

Quoted 7 lines

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 ;)

#8 lore raw
In reply to Eric Dumazet
Quoted 6 lines · Eric Dumazet
Quoted 5 lines · Andi Kleen
Quoted 2 lines

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.

Quoted 1 line

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

#9 lore raw
In reply to Andi Kleen
Quoted 6 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)

Quoted 8 lines

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.

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

Quoted 7 lines

#ifdef CONFIG_SMP

include/linux/init_task.h +2 -0
@@ -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