posix timers: allocate timer id per process

v4:
1) a couple of coding style fixes (lines over 80 characters)

v3:
1) hash calculation simlified to improve perfomance.

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 process.

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_32(current->signal) ^ hash_32(posix_timer_id);

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

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 */

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;

This should not be in the changelog, only after the --- separator.

I wonder if some applications relied on our idr, assuming they would get low values for their timer id.
(We could imagine some applications use a table indexed by the timer id)

Only on x86_64. Why not instead saying hashtable has 512 slots ?

This is outdated.

Thanks

19.10.2012 11:56, Eric Dumazet пишет:

Hmm.
Probably, this particular case can be optimised by tuning min_id to id of releasing timer (if id of this timer is less than current->signal min_id). Does this approach solves the issue you mentioned above?

Best regards,
Stanislav Kinsbursky

Not generally, but I am not sure we want a per signal_struct idr ;)

Really that should be clearly explained in the changelog, so that buggy applications can have a clue of what happened.

When we changed UDP source port selection being random instead of sequential, maybe this broke some applications. That was an implementation choice (with security impact).