posix timers: allocate timer id per process
PATCH v5 1/1 posix timers: allocate timer id per process
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 process. 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 has 512 slots.
Key is constructed as follows:
key = hash_32(hash_32(current->signal) ^ posix_timer_id));
Note: with this patch, id, returned to user, is not the minimal free amymore. It means, that id, returned to user space in loop, listed below, will be increasing on each iteration till INT_MAX and then dropped to zero:
while(1) {
id = timer_create(...);
timer_delete(id);
}---
v5:
1) Patch changelog updated
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
--- include/linux/posix-timers.h | 1 include/linux/sched.h | 4 + kernel/posix-timers.c | 113 ++++++++++++++++++++++++++++-------------- 3 files changed, 79 insertions(+), 39 deletions(-)
include/linux/posix-timers.h +1 -0
@@ -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
@@ -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 +75 -38
163 lines not on this page · raw message
Quoted 21 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 process.Patch replaces global idr with global hash table for posix timers and makes timer ids unique not globally, but per process. 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-EAGAINwill be returned to user.Hash table has 512 slots.
Key is constructed as follows:
key =hash_32(hash_32(current->signal) ^ posix_timer_id));Note: with this patch, id, returned to user, is not the minimal free amymore. It means, that id, returned to user space in loop, listed below, will be increasing on each iteration till
INT_MAXand then dropped to zero:
Quoted 8 lines
while(1) { id = timer_create(...); timer_delete(id); }Signed-off-by Stanislav Kinsbursky <[email protected]>---
SGTM
Thanks !
Quoted 27 lines · Eric Dumazet
Quoted 26 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 process.Patch replaces global idr with global hash table for posix timers and makes timer ids unique not globally, but per process. 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-EAGAINwill be returned to user.Hash table has 512 slots.
Key is constructed as follows:
key =hash_32(hash_32(current->signal) ^ posix_timer_id));Note: with this patch, id, returned to user, is not the minimal free amymore. It means, that id, returned to user space in loop, listed below, will be increasing on each iteration till
INT_MAXand then dropped to zero:while(1) { id = timer_create(...); timer_delete(id); }
Quoted 5 lines
Quoted 3 lines
Signed-off-by Stanislav Kinsbursky <[email protected]>---
SGTM
Not so good to me.
Quoted 1 line
Signed-off-by Eric Dumazet <[email protected]>
And that should be either an Acked-by or a Reviewed-by. You can't sign off on patches which have not been submitted or transported by you.
Thanks,
tglx
Quoted 6 lines · Thomas Gleixner
Not so good to me.
Quoted 1 line
Signed-off-by Eric Dumazet <[email protected]>And that should be either an Acked-by or a Reviewed-by. You can't sign off on patches which have not been submitted or transported by you.
I actually gave some input, provided a hash function, and so on.
So this SOB was valid. I do that all the time.
And yes, there are bugs in this patch, as many patches that were merged in linux tree, included by you.
Thanks
Quoted 4 lines · Eric Dumazet
Quoted 2 lines · Thomas Gleixner
Not so good to me.
Quoted 8 lines
Quoted 4 lines
Quoted 1 line
Signed-off-by Eric Dumazet <[email protected]>And that should be either an Acked-by or a Reviewed-by. You can't sign off on patches which have not been submitted or transported by you.
I actually gave some input, provided a hash function, and so on.
So this SOB was valid. I do that all the time.
Not really. I recommend you to read the relevant file in Documentation which covers what can have your SOB.
Your input is documented in the mail thread, but it does not contain a patch - which is Signed-off-by YOU - on which the thing at hand is based on. So it's not covered by what SOB actually means.
You can rightfully request the patch author to add a "Suggested-by" tag, but you can't rightfully claim authorship of something you did not author.
Quoted 2 lines
And yes, there are bugs in this patch, as many patches that were merged in linux tree, included by you.
That's a totally different issue. We can ack/review/signoff and commit totally bogus patches as long as we want.
Though that does not change the meanings of the tags (Acked, Reviewed, Signed-off) at all.
Thanks,
tglx
Quoted 11 lines · Thomas Gleixner
Quoted 9 lines · Eric Dumazet
Quoted 6 lines · Thomas Gleixner
Not so good to me.
Quoted 1 line
Signed-off-by Eric Dumazet <[email protected]>And that should be either an Acked-by or a Reviewed-by. You can't sign off on patches which have not been submitted or transported by you.
Quoted 6 lines
Quoted 3 lines
I actually gave some input, provided a hash function, and so on.
So this SOB was valid. I do that all the time.
Not really. I recommend you to read the relevant file in Documentation which covers what can have your SOB.
OK I did that again, and found this :
The Signed-off-by: tag indicates that the signer was involved in the development of the patch, or that he/she was in the patch's delivery path.
And I was involved in the development of the patch.
I understand you dont like it at all, so I'll remember not trying to help anymore in this area.
Quoted 26 lines · Eric Dumazet
Quoted 11 lines · Thomas Gleixner
Quoted 9 lines · Eric Dumazet
Quoted 6 lines · Thomas Gleixner
Not so good to me.
Quoted 1 line
Signed-off-by Eric Dumazet <[email protected]>And that should be either an Acked-by or a Reviewed-by. You can't sign off on patches which have not been submitted or transported by you.
Quoted 6 lines
Quoted 3 lines
I actually gave some input, provided a hash function, and so on.
So this SOB was valid. I do that all the time.
Not really. I recommend you to read the relevant file in Documentation which covers what can have your SOB.
OK I did that again, and found this :
The Signed-off-by: tag indicates that the signer was involved in the development of the patch, or that he/she was in the patch's delivery path.
Quoted 4 lines
And I was involved in the development of the patch.
I understand you dont like it at all, so I'll remember not trying to help anymore in this area.
No, you are simply wrong and Linus would (rightfully) complain to *Thomas* if he added a SOB like that and pushed such a faulty commit to him. Linus has complained about such SOBs before and Thomas would be wrong to put them into commits.
SOBs get added if you are the developer of the patch or if you are actually one of the 'hops' in the route of the patch that gets it to Thomas. SOBs don't get added over email like you did and what Thomas pointed out was simply a maintainer's job to point out.
Adding credits for helping development get added via different tags, not via SOBs.
Thanks,
Ingo
Quoted 5 lines · Stanislav Kinsbursky
Patch replaces global idr with global hash table for posix timers and makes timer ids unique not globally, but per process. 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-EAGAINwill be returned to user.
That's the theory ...
include/linux/sched.h struct sched_param { · line 54
Quoted 9 lines
include/linux/sched.h +1
-0@@ -51,6 +51,7 @@ struct sched_param {#include <linux/cred.h> #include <linux/llist.h> #include <linux/uidgid.h> +#include <linux/idr.h>
Why ?
include/linux/sched.h struct sched_param {
Quoted 13 lines
include/linux/sched.h +13
-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)) { + hlist_add_head_rcu(&timer->t_hash, head); + ret = sig->posix_timer_id++;
Let's assume a program, which creates timers and destroys them in a loop.
while (1) {
id = timer_create();
if (id < 0)
continue;
timer_delete(id);
}After 2^31 iterations sig->posix_timer_id contains 0x80000000.
__posix_timer_find() will return NULL as there is no timer with this id and you happily add the new timer to the hash list and return 0x80000000, which translates to -INT_MAX.
Now this will return a totally useless error code to user space and what's worse it will free that timer without removing it from the hash bucket. The next access to that bucket will explode nicely.
include/linux/sched.h
Quoted 5 lines
include/linux/sched.h +5
-0+ }else { +if (++sig->posix_timer_id <0 ) + sig->posix_timer_id =0 ; +if (sig->posix_timer_id == next_free_id) + ret = -EAGAIN ;
This code path has obvioulsy never been executed.
include/linux/sched.h
Quoted 5 lines
include/linux/sched.h +5
-0+ } +spin_unlock (&hash_lock); + }while (ret == -ENOENT ); +return ret; +}
Thanks,
tglx