posix timers: allocate timer id per task

RFC PATCH Superseded Stanislav Kinsbursky 4 participants 7 messages Oct 15, 2012 – Oct 16, 2012 Scheduler

Share & tools

Stanislav Kinsbursky

author

2012-10-15 16:16 UTC #0 lore raw

RFC PATCH 1/1 posix timers: allocate timer id per task

This patch is required CRIU project (www.criu.org).
To migrate processes with posix timers we have to make sure, that we can restore posix timer with proper id.
Currently, this is not true, because timer ids are allocated globally. So, this is precursor patch and it's purpose is make posix timer id to be allocated per task.

Patch replaces global idr with global hash table for posix timers and makes timer ids unique not globally, but per task. Next free timer id is type of integer and stored on signal struct (posix_timer_id). If free timer id reaches negative value on timer creation, it will be dropped to zero and -EAGAIN will be returned to user.
Hash table is size of page (4KB).
Key is constructed as follows:
key = hash_ptr(current->signal) ^ hash_32(posix_timer_id);

Signed-off-by Stanislav Kinsbursky <[email protected]>

---
 include/linux/posix-timers.h |    1 
 include/linux/sched.h        |    4 +-
 kernel/posix-timers.c        |  111 ++++++++++++++++++++++++++++--------------
 3 files changed, 77 insertions(+), 39 deletions(-)

include/linux/posix-timers.h +1 -0

index 042058f..60bac69 100644
@@ -55,6 +55,7 @@ struct cpu_timer_list {
 /* POSIX.1b interval timer structure. */
 struct k_itimer {
 	struct list_head list;		/* free/ allocate list */
+	struct hlist_node t_hash;
 	spinlock_t it_lock;
 	clockid_t it_clock;		/* which timer type */
 	timer_t it_id;			/* timer id */

include/linux/sched.h +3 -1

index 0dd42a0..dce1651 100644
@@ -51,6 +51,7 @@ struct sched_param {
 #include <linux/cred.h>
 #include <linux/llist.h>
 #include <linux/uidgid.h>
+#include <linux/idr.h>
 
 #include <asm/processor.h>

@@ -536,7 +537,8 @@ struct signal_struct {
 	unsigned int		has_child_subreaper:1;
 
 	/* POSIX.1b Interval Timers */
-	struct list_head posix_timers;
+	int			posix_timer_id;
+	struct list_head	posix_timers;
 
 	/* ITIMER_REAL timer for the process */
 	struct hrtimer real_timer;

kernel/posix-timers.c +73 ~~-38~~

161 lines not on this page · raw message

Eric Dumazet

2012-10-15 16:34 UTC #1 lore raw

Quoted 16 lines · Stanislav Kinsbursky

This patch is required CRIU project (www.criu.org).
To migrate processes with posix timers we have to make sure, that we can restore posix timer with proper id.
Currently, this is not true, because timer ids are allocated globally. So, this is precursor patch and it's purpose is make posix timer id to be allocated per task.
Patch replaces global idr with global hash table for posix timers and makes timer ids unique not globally, but per task. Next free timer id is type of integer and stored on signal struct (posix_timer_id). If free timer id reaches negative value on timer creation, it will be dropped to zero and -EAGAIN will be returned to user.
Hash table is size of page (4KB).
Key is constructed as follows:
key = hash_ptr(current->signal) ^ hash_32(posix_timer_id);

Quoted 1 line

Signed-off-by Stanislav Kinsbursky <[email protected]>

Hmm, it seems you removed idr, rcu friendly, and reinstated a fixed size hash table, protected by a _single_ spinlock ? Oh well.

Please take a look at commit 8af088710d1e, and make sure you fix your problem and keep performance as good as before.

Stanislav Kinsbursky

author

2012-10-16 07:58 UTC #2 lore raw

15.10.2012 20:34, Eric Dumazet пишет:

Quoted 17 lines · Stanislav Kinsbursky

Quoted 16 lines
This patch is required CRIU project (www.criu.org).
To migrate processes with posix timers we have to make sure, that we can restore posix timer with proper id.
Currently, this is not true, because timer ids are allocated globally. So, this is precursor patch and it's purpose is make posix timer id to be allocated per task.
Patch replaces global idr with global hash table for posix timers and makes timer ids unique not globally, but per task. Next free timer id is type of integer and stored on signal struct (posix_timer_id). If free timer id reaches negative value on timer creation, it will be dropped to zero and -EAGAIN will be returned to user.
Hash table is size of page (4KB).
Key is constructed as follows:
key = hash_ptr(current->signal) ^ hash_32(posix_timer_id);

Quoted 9 lines

Quoted 1 line
Signed-off-by Stanislav Kinsbursky <[email protected]>
Hmm, it seems you removed idr, rcu friendly, and reinstated a fixed size hash table, protected by a _single_ spinlock ? Oh well.
Please take a look at commit 8af088710d1e, and make sure you fix your problem and keep performance as good as before.

Thanks, Eric.
I'll update.

Quoted 2 lines

Signature · 2 lines

Best regards,
Stanislav Kinsbursky

Peter Zijlstra

maintainer

2012-10-15 17:04 UTC #3 lore raw

In reply to Stanislav Kinsbursky

Quoted 7 lines · Stanislav Kinsbursky

This patch is required CRIU project (www.criu.org).
To migrate processes with posix timers we have to make sure, that we can restore posix timer with proper id.
Currently, this is not true, because timer ids are allocated globally. So, this is precursor patch and it's purpose is make posix timer id to be allocated per task.

Quoted 8 lines

Patch replaces global idr with global hash table for posix timers and makes timer ids unique not globally, but per task. Next free timer id is type of integer and stored on signal struct (posix_timer_id). If free timer id reaches negative value on timer creation, it will be dropped to zero and -EAGAIN will be returned to user.
Hash table is size of page (4KB).
Key is constructed as follows:
key = hash_ptr(current->signal) ^ hash_32(posix_timer_id);

but but but.. isn't this what namespaces were invented for to solve? Why not use the regular namespace infrastructure?

Stanislav Kinsbursky

author

2012-10-16 08:00 UTC #4 lore raw

15.10.2012 21:04, Peter Zijlstra пишет:

Quoted 17 lines · Stanislav Kinsbursky

Quoted 7 lines
This patch is required CRIU project (www.criu.org).
To migrate processes with posix timers we have to make sure, that we can restore posix timer with proper id.
Currently, this is not true, because timer ids are allocated globally. So, this is precursor patch and it's purpose is make posix timer id to be allocated per task.
Quoted 8 lines
Patch replaces global idr with global hash table for posix timers and makes timer ids unique not globally, but per task. Next free timer id is type of integer and stored on signal struct (posix_timer_id). If free timer id reaches negative value on timer creation, it will be dropped to zero and -EAGAIN will be returned to user.
Hash table is size of page (4KB).
Key is constructed as follows:
key = hash_ptr(current->signal) ^ hash_32(posix_timer_id);

Quoted 3 lines

but but but.. isn't this what namespaces were invented for to solve? Why not use the regular namespace infrastructure?

The reason is that CRIU have to support single processes within existent namespaces.

Signature · 2 lines

Best regards,
Stanislav Kinsbursky

Thomas Gleixner

2012-10-15 19:08 UTC #5 lore raw

In reply to Stanislav Kinsbursky

Quoted 6 lines · Stanislav Kinsbursky

This patch is required CRIU project (www.criu.org).
To migrate processes with posix timers we have to make sure, that we can restore posix timer with proper id.
Currently, this is not true, because timer ids are allocated globally. So, this is precursor patch and it's purpose is make posix timer id to be allocated per task.

You can't allocate them per task. posix timers are process wide.

What's the reason why you did not make the posix timer ids per name space instead of going down to the per process level ?

Quoted 5 lines

Patch replaces global idr with global hash table for posix timers and makes timer ids unique not globally, but per task. Next free timer id is type of integer and stored on signal struct (posix_timer_id). If free timer id reaches negative value on timer creation, it will be dropped to zero and -EAGAIN will be returned to user.

So you want to allow 2^31 posix timers created for a single process?

Quoted 9 lines

kernel/posix-timers.c +9 -0

+static struct k_itimer *__posix_timers_find(struct hlist_head *head, struct signal_struct *sig, timer_t id)
+{
+	struct hlist_node *node;
+	struct k_itimer *timer;
+
+	hlist_for_each_entry(timer, node, head, t_hash) {
+		if ((timer->it_signal == sig) && (timer->it_id == id))
+			return timer;
+	}

kernel/posix-timers.c static struct k_itimer *__lock_timer(timer_t timer_id, unsigned long *flags); · line 175

Quoted 10 lines

kernel/posix-timers.c +10 -0

+	return NULL;
+}
+
+static struct k_itimer *posix_timer_find(timer_t id, unsigned long *flags)
+{
+	struct k_itimer *timer;
+	struct signal_struct *sig = current->signal;
+	struct hlist_head *head = &posix_timers_hashtable[hash(sig, id)];
+
+	spin_lock_irqsave(&hash_lock, *flags);

This is not going to fly. You just reintroduced a massive scalability problem. See commit 8af08871

Thanks,

tglx

Stanislav Kinsbursky

author

2012-10-16 08:08 UTC #6 lore raw

15.10.2012 23:08, Thomas Gleixner пишет:

Quoted 11 lines · Stanislav Kinsbursky

Quoted 7 lines
This patch is required CRIU project (www.criu.org).
To migrate processes with posix timers we have to make sure, that we can restore posix timer with proper id.
Currently, this is not true, because timer ids are allocated globally. So, this is precursor patch and it's purpose is make posix timer id to be allocated per task.
You can't allocate them per task. posix timers are process wide.

This is probably a misunderstanding.
I meant process process.

Quoted 3 lines

What's the reason why you did not make the posix timer ids per name space instead of going down to the per process level ?

The reason is that CRIU have to support single processes regardless to namespaces.

Quoted 8 lines

Quoted 5 lines
Patch replaces global idr with global hash table for posix timers and makes timer ids unique not globally, but per task. Next free timer id is type of integer and stored on signal struct (posix_timer_id). If free timer id reaches negative value on timer creation, it will be dropped to zero and -EAGAIN will be returned to user.
So you want to allow 2^31 posix timers created for a single process?

I don't really want it.
I just tried to preserve existent logic. I.e. currently one process can create 2^31 posix timers (if no other processes tried to do the same). But the amount can be decreased, of course.

Quoted 14 lines

kernel/posix-timers.c +14 -0

+static struct k_itimer *__posix_timers_find(struct hlist_head *head, struct signal_struct *sig, timer_t id)
+{
+	struct hlist_node *node;
+	struct k_itimer *timer;
+
+	hlist_for_each_entry(timer, node, head, t_hash) {
+		if ((timer->it_signal == sig) && (timer->it_id == id))
+			return timer;
+	}
+	return NULL;
+}
+
+static struct k_itimer *posix_timer_find(timer_t id, unsigned long *flags)
+{

Quoted 9 lines

kernel/posix-timers.c static struct k_itimer *__lock_timer(timer_t timer_id, unsigned long *flags); · line 175
Quoted 5 lines
kernel/posix-timers.c +5 -0
+	struct k_itimer *timer;
+	struct signal_struct *sig = current->signal;
+	struct hlist_head *head = &posix_timers_hashtable[hash(sig, id)];
+
+	spin_lock_irqsave(&hash_lock, *flags);
This is not going to fly. You just reintroduced a massive scalability problem. See commit 8af08871

Yep, Eric already pointed to it.
I'll try to fix this problem, if the idea with hash table suits in general. Thanks.

Quoted 4 lines

Thanks,
tglx

Signature · 2 lines

Best regards,
Stanislav Kinsbursky