Skip to contentSkip to conversation

posix timers: allocate timer id per task

RFC PATCH Superseded Stanislav Kinsbursky 2 participants 5 messages Oct 17, 2012 Scheduler

v2 of 6 Superseded Latest is v6 →

lore
Share & tools
lore

Stanislav Kinsbursky

author
#0 lore raw

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

v2:
1) Hash table become RCU-friendly. Hash table search now done under RCU lock protection.
I've tested scalability on KVM with 4 CPU. The testing environment was build of 10 processes, each had 512 posix timers running (SIGSEV_NONE) and was calling timer_gettime() in loop. With all this stuff being running, I was measuring time of calling of syscall timer_gettime() 10000 times.

Without this patch: ~7ms
With this patch : ~7ms

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        |  112 ++++++++++++++++++++++++++++--------------
 3 files changed, 78 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 +74 -38

162 lines not on this page · raw message

#1 lore raw

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

Quoted 6 lines · Stanislav Kinsbursky
kernel/posix-timers.c +6 -0
+static int hash(struct signal_struct *sig, unsigned int nr)
+{
+	int hash = hash_ptr(sig, POSIX_TIMERS_HASH_BITS);
+	return hash ^ hash_32(nr, POSIX_TIMERS_HASH_BITS);
+}
+

This is quite expensive on 64 bit arches. I suggest instead :

return hash_32(hash32_ptr(sig) ^ nr, POSIX_TIMERS_HASH_BITS);

author
#2 lore raw

17.10.2012 17:44, Eric Dumazet пишет:

Quoted 11 lines · Stanislav Kinsbursky

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

Quoted 7 lines
kernel/posix-timers.c +6 -0
+static int hash(struct signal_struct *sig, unsigned int nr)
+{
+	int hash = hash_ptr(sig, POSIX_TIMERS_HASH_BITS);
+	return hash ^ hash_32(nr, POSIX_TIMERS_HASH_BITS);
+}
+

This is quite expensive on 64 bit arches. I suggest instead :

Quoted 3 lines

return hash_32(hash32_ptr(sig) ^ nr, POSIX_TIMERS_HASH_BITS);

I'm not familiar with hashing costs, so sure, I'll update.

Signature · 2 lines
Best regards,
Stanislav Kinsbursky
#3 lore raw
In reply to Stanislav Kinsbursky

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

Quoted 12 lines · Stanislav Kinsbursky
kernel/posix-timers.c +12 -0
+static int posix_timer_add(struct k_itimer *timer)
+{
+	struct signal_struct *sig = current->signal;
+	int next_free_id = sig->posix_timer_id;
+	struct hlist_head *head;
+	int ret = -ENOENT;
+
+	do {
+		spin_lock(&hash_lock);
+		head = &posix_timers_hashtable[hash(sig, sig->posix_timer_id)];
+		if (__posix_timers_find(head, sig, sig->posix_timer_id) == NULL) {
+			hlist_add_head_rcu(&timer->t_hash, head);

Hmm...

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

Quoted 12 lines
kernel/posix-timers.c +12 -0
+			ret = sig->posix_timer_id++;
+		} else {
+			if (++sig->posix_timer_id < 0)
+				sig->posix_timer_id = 0;
+			if (sig->posix_timer_id == next_free_id)
+				ret = -EAGAIN;
+		}
+		spin_unlock(&hash_lock);
+	} while (ret == -ENOENT);
+	return ret;
+}
+

You probably need to add a rcu_assign_pointer() or smp_wmb() before the :

new_timer->it_signal = current->signal;

in the following block :

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

Or else another thread can read outdated informations...

        spin_lock_irq(&current->sighand->siglock);
        list_add(&new_timer->list, &current->signal->posix_timers);
        spin_unlock_irq(&current->sighand->siglock);
	smp_wmb();
        new_timer->it_signal = current->signal;
author
#4 lore raw

17.10.2012 17:57, Eric Dumazet пишет:

Quoted 42 lines · Stanislav Kinsbursky

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

Quoted 13 lines
kernel/posix-timers.c +12 -0
+static int posix_timer_add(struct k_itimer *timer)
+{
+	struct signal_struct *sig = current->signal;
+	int next_free_id = sig->posix_timer_id;
+	struct hlist_head *head;
+	int ret = -ENOENT;
+
+	do {
+		spin_lock(&hash_lock);
+		head = &posix_timers_hashtable[hash(sig, sig->posix_timer_id)];
+		if (__posix_timers_find(head, sig, sig->posix_timer_id) == NULL) {
+			hlist_add_head_rcu(&timer->t_hash, head);

Hmm...

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

Quoted 12 lines
kernel/posix-timers.c +12 -0
+			ret = sig->posix_timer_id++;
+		} else {
+			if (++sig->posix_timer_id < 0)
+				sig->posix_timer_id = 0;
+			if (sig->posix_timer_id == next_free_id)
+				ret = -EAGAIN;
+		}
+		spin_unlock(&hash_lock);
+	} while (ret == -ENOENT);
+	return ret;
+}
+

You probably need to add a rcu_assign_pointer() or smp_wmb() before the :

new_timer->it_signal = current->signal;

in the following block :

         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);
Quoted 10 lines

Or else another thread can read outdated informations...

         spin_lock_irq(&current->sighand->siglock);
         list_add(&new_timer->list, &current->signal->posix_timers);
         spin_unlock_irq(&current->sighand->siglock);
	smp_wmb();
         new_timer->it_signal = current->signal;

Sorry, but I don't understand what races you are talking about. Could you specify, please?

Signature · 2 lines
Best regards,
Stanislav Kinsbursky