Introduce greedy hrtimer walk on idle
RFC 1/1 Introduce greedy hrtimer walk on idle
Current hrtimer range timers reduces the number of timer interrupts by grouping together softexpired timers until the next unexpired timer. It does not look at softexpired timers that may be after the unexpired timer in the rbtree.
Specifically, as the comment in hrtimer.c says
* The immediate goal for using the softexpires is
* minimizing wakeups, not running timers at the
* earliest interrupt after their soft expiration.
* This allows us to avoid using a Priority Search
* Tree, which can answer a stabbing querry for
* overlapping intervals and instead use the simple
* BST we already have.
* We don't add extra wakeups by delaying timers that
* are right-of a not yet expired timer, because that
* timer will have to trigger a wakeup anyway.
But, doing an exhaustive search for all softexpired timers, especially when
CPU is idle, has its advantages:
* it will result in less interruptions later (when CPU may be busy).
* it can reduce number of wakeups in cases where not yet expired timer in above description could be deleted before they expire.
* For timers resulting in task wakeups, doing wakeup on idle can improve the
overall efficiency of the system. It can also bring load balance/migration benefits.
The change below adds this exhaustive soft expired timer search on idle (Only on x86-64 for now). It uses the underlying augmented rbtree mechanism to do this in an optimal way. The change does add an extra element into struct hrtimer and some complexity in insert/delete path (Any microbenchmark that I should use to measure this overhead?)
Some preliminary results showing the effect on sched migrations (perf stat -r 5 -a -e migrations sleep 60)
(16 logical CPU server)
(0) System <0.5% busy with
bunch of background management threads doing periodic wakeups (slack 50us) Before -
2,118 CPU-migrations ( +- 7.851% ) After - 2,140 CPU-migrations ( +- 7.278% )
(1) System >80% busy with 16 threads in <4ms busy, 1ms idle> cycle + bunch of background management threads doing periodic wakeups (slack 50us)
Before -
20,568 CPU-migrations ( +- 2.210% ) After - 17,954 CPU-migrations ( +- 1.459% )
Instrumentation showed ~10% among all non sched_timer timers being invoked due to greedy lookup
(2) System >80% busy system with 16 threads in (4ms busy - 1ms idle) cycle + bunch of background management threads doing periodic wakeups (slack 10ms) Before -
24,510 CPU-migrations ( +- 2.431% ) After - 13,042 CPU-migrations ( +- 3.721% )
Instrumentation showed 86% among all non sched_timer timers being invoked due to greedy lookup
(3) System 100% busy with 16 threads in infinite loop +
bunch of background management threads doing periodic wakeups (slack 50us) Before -
938 CPU-migrations ( +- 13.147% ) After - 973 CPU-migrations ( +- 7.746% )
Comments?
--- arch/x86/kernel/process_64.c | 2 + include/linux/hrtimer.h | 14 ++++ include/linux/sched.h | 1 + include/linux/timerqueue.h | 11 +++ kernel/hrtimer.c | 175 +++++++++++++++++++++++++++++++++++++----- kernel/sched.c | 2 + kernel/sysctl.c | 7 ++ 7 files changed, 191 insertions(+), 21 deletions(-)
arch/x86/kernel/process_64.c +2 -0
@@ -149,6 +149,8 @@ void cpu_idle(void)preempt_enable_no_resched ();schedule ();preempt_disable (); +if (sysctl_hrtimer_greedy_lookup) +hrtimer_peek_ahead_timers (); } }
include/linux/hrtimer.h +14 -0
@@ -93,6 +93,8 @@ enum hrtimer_restart {* @_softexpires: the absolute earliest expiry time of the hrtimer. * The time which was given as expiry time when the timer * was armed. +* @_subtree_least_se: the least _softexpires among all the nodes in the +* subtree rooted at this node. * @function: timer expiry callback function * @base: pointer to the timer base (per cpu and per clock) * @state: state information (See bit values above)
@@ -108,6 +110,7 @@ enum hrtimer_restart {struct hrtimer {struct timerqueue_node node;ktime_t _softexpires; +ktime_t _subtree_least_se;enum hrtimer_restart (*function)(struct hrtimer *);struct hrtimer_clock_base *base;unsigned long state;
@@ -214,6 +217,11 @@ static inline void hrtimer_set_expires_tv64(struct hrtimer *timer, s64 tv64) timer->_softexpires.tv64 = tv64; } +static inline void hrtimer_set_subtree_least_se_tv64 (struct hrtimer *timer,s64 tv64) +{ + timer->_subtree_least_se.tv64 = tv64; +} +static inline void hrtimer_add_expires (struct hrtimer *timer,ktime_t time) { timer->node.expires =ktime_add_safe (timer->node.expires, time);
@@ -240,6 +248,12 @@ static inline s64 hrtimer_get_expires_tv64(const struct hrtimer *timer) {return timer->node.expires.tv64; } + +static inline s64 hrtimer_get_subtree_least_se_tv64 (const struct hrtimer *timer) +{ +return timer->_subtree_least_se.tv64; +} +static inline s64 hrtimer_get_softexpires_tv64 (const struct hrtimer *timer) {return timer->_softexpires.tv64;
include/linux/sched.h +1 -0
@@ -132,6 +132,7 @@ extern void get_avenrun(unsigned long *loads, unsigned long offset, int shift); load += n*(FIXED_1 -exp); \ load >>=FSHIFT ; +extern int sysctl_hrtimer_greedy_lookup;extern unsigned long total_forks;extern int nr_threads; DECLARE_PER_CPU(unsigned long, process_counts);
include/linux/timerqueue.h +11 -0
@@ -47,4 +47,15 @@ static inline void timerqueue_init_head(struct timerqueue_head *head) head->head =RB_ROOT ; head->next =NULL ; } + +static inline +struct timerqueue_node *timerqueue_getroot (struct timerqueue_head *head) +{ +struct rb_node *rbnode = head->head.rb_node; + +if (!rbnode) +return NULL ; + + return rb_entry(rbnode, struct timerqueue_node, node); +}#endif /* _LINUX_TIMERQUEUE_H */
kernel/hrtimer.c +154 -21
227 lines not on this page · raw message
kernel/sched.c +2 -0
@@ -154,6 +154,8 @@ static struct rt_bandwidth def_rt_bandwidth;static int do_sched_rt_period_timer (struct rt_bandwidth *rt_b,int overrun); +int sysctl_hrtimer_greedy_lookup =0 ; +static enum hrtimer_restart sched_rt_period_timer (struct hrtimer *timer) { struct rt_bandwidth *rt_b =
kernel/sysctl.c +7 -0
@@ -279,6 +279,13 @@ static struct ctl_table kern_table[] = { .mode = 0644, .proc_handler = proc_dointvec, }, + { + .procname = "hrtimer_greedy_lookup", + .data = &sysctl_hrtimer_greedy_lookup, + .maxlen = sizeof(unsigned int), + .mode = 0644, + .proc_handler = proc_dointvec, + }, #ifdef CONFIG_SCHED_DEBUG { .procname = "sched_min_granularity_ns",
Signature · 1 line
1.7.3.1
Quoted 5 lines · Venkatesh Pallipadi
Current hrtimer range timers reduces the number of timer interrupts by grouping together softexpired timers until the next unexpired timer. It does not look at softexpired timers that may be after the unexpired timer in the rbtree.
Quoted 12 lines
Specifically, as the comment in
hrtimer.csays
* The immediate goal for using the softexpires is
* minimizing wakeups, not running timers at the
* earliest interrupt after their soft expiration.
* This allows us to avoid using a Priority Search
* Tree, which can answer a stabbing querry for
* overlapping intervals and instead use the simple
* BST we already have.
* We don't add extra wakeups by delaying timers that
* are right-of a not yet expired timer, because that
* timer will have to trigger a wakeup anyway.
Since you found that it now makes a difference, I'm all for it..
(at original introduction it was in the noise, but usage patterns clearly changed a lot and ranges are much more prevalent now)
I would not do the sysctl/configurability thing though.... that's not worth it.
Quoted 23 lines · Arjan van de Ven
Quoted 6 lines · Venkatesh Pallipadi
Current hrtimer range timers reduces the number of timer interrupts by grouping together softexpired timers until the next unexpired timer. It does not look at softexpired timers that may be after the unexpired timer in the rbtree.
Quoted 14 lines
Specifically, as the comment in
hrtimer.csays
* The immediate goal for using the softexpires is
* minimizing wakeups, not running timers at the
* earliest interrupt after their soft expiration.
* This allows us to avoid using a Priority Search
* Tree, which can answer a stabbing querry for
* overlapping intervals and instead use the simple
* BST we already have.
* We don't add extra wakeups by delaying timers that
* are right-of a not yet expired timer, because that
* timer will have to trigger a wakeup anyway.
Quoted 9 lines
Since you found that it now makes a difference, I'm all for it..
Acked-by Arjan van de Ven <[email protected]>(at original introduction it was in the noise, but usage patterns clearly changed a lot and ranges are much more prevalent now)
I would not do the sysctl/configurability thing though.... that's not worth it.
Yes. I kept the sysctl there for this RFC, so that anyone testing this can easily switch this on/off and measure the impact. Will remove it in updates..
Thanks,
Venki
Quoted 3 lines · Venki Pallipadi
Yes. I kept the sysctl there for this RFC, so that anyone testing this can easily switch this on/off and measure the impact. Will remove it in updates..
I presume we have a plan to ensure the sysctl gets removed/disabled for releases, so it doesn't escape and become official API we then have to deprecate? ("We'll stuff it in at the front of the 3.2 merge window, and nuke it around 3.2-rc5" is OK by me...)
Peter Zijlstra
maintainerQuoted 1 line · Venkatesh Pallipadi
Comments?
One of the reasons we didn't do it before was added cost to hrtimer_{add,del}, did you measure workloads that are heavy on that?
Quoted 6 lines · Peter Zijlstra
Quoted 1 line · Venkatesh Pallipadi
Comments?
One of the reasons we didn't do it before was added cost to hrtimer_{add,del}, did you measure workloads that are heavy on that?
I haven't seen any measurable overhead with workloads I have tried. But, I don't think I have hit that path hard enough. Do you have any particular workload in mind?
Peter Zijlstra
maintainerQuoted 11 lines · Venki Pallipadi
Quoted 6 lines · Peter Zijlstra
Quoted 1 line · Venkatesh Pallipadi
Comments?
One of the reasons we didn't do it before was added cost to hrtimer_{add,del}, did you measure workloads that are heavy on that?
I haven't seen any measurable overhead with workloads I have tried. But, I don't think I have hit that path hard enough. Do you have any particular workload in mind?
Not really, I asked tglx if he knew a particular workload to test this, but he didn't have anything either.
Peter Zijlstra
maintainerQuoted 1 line · Venkatesh Pallipadi
Comments?
Looks to be a possible IRQ latency issue as well, that can be a lot of timers to run..
Quoted 6 lines · Peter Zijlstra
Quoted 1 line · Venkatesh Pallipadi
Comments?
Looks to be a possible IRQ latency issue as well, that can be a lot of timers to run..
We could add some rate limit on how many timers we service this way and/or interrupt/disable-enable in the inner loop.
But, this would be a problem with current hrtimer as well. When sched_tick timer is not around, we may end up servicing lot of timers depending on number of them and slack. No?
Peter Zijlstra
maintainerQuoted 8 lines · Venki Pallipadi
Quoted 6 lines · Peter Zijlstra
Quoted 1 line · Venkatesh Pallipadi
Comments?
Looks to be a possible IRQ latency issue as well, that can be a lot of timers to run..
Quoted 5 lines
We could add some rate limit on how many timers we service this way and/or interrupt/disable-enable in the inner loop.
But, this would be a problem with current hrtimer as well. Whensched_ticktimer is not around, we may end up servicing lot of timers depending on number of them and slack. No?
Right, still something to consider. We might just have to push down on slack for -rt or so when it becomes a problem.
Quoted 7 lines · Peter Zijlstra
Quoted 6 lines · Venki Pallipadi
Quoted 5 lines · Peter Zijlstra
Quoted 1 line · Venkatesh Pallipadi
Comments?
Looks to be a possible IRQ latency issue as well, that can be a lot of timers to run..
Quoted 7 lines
Quoted 5 lines
We could add some rate limit on how many timers we service this way and/or interrupt/disable-enable in the inner loop.
But, this would be a problem with current hrtimer as well. Whensched_ticktimer is not around, we may end up servicing lot of timers depending on number of them and slack. No?Right, still something to consider. We might just have to push down on slack for -rt or so when it becomes a problem.
that might not be the right answer ;-)
Slack gives you freedom to schedule these guys; without slack you can still get bursts of timers, but with no freedom to punt some for RT behavior. with slack, you can run the mandatory ones first, and then the optionals until you hit some RT limit.. the optionals you do run are not going to bunch up to you at the time they become mandatory.
Peter Zijlstra
maintainerQuoted 16 lines · Arjan van de Ven
Quoted 7 lines · Peter Zijlstra
Quoted 6 lines · Venki Pallipadi
Quoted 5 lines · Peter Zijlstra
Quoted 1 line · Venkatesh Pallipadi
Comments?
Looks to be a possible IRQ latency issue as well, that can be a lot of timers to run..
Quoted 7 lines
Quoted 5 lines
We could add some rate limit on how many timers we service this way and/or interrupt/disable-enable in the inner loop.
But, this would be a problem with current hrtimer as well. Whensched_ticktimer is not around, we may end up servicing lot of timers depending on number of them and slack. No?Right, still something to consider. We might just have to push down on slack for -rt or so when it becomes a problem.
Quoted 7 lines
that might not be the right answer ;-)
Slack gives you freedom to schedule these guys; without slack you can still get bursts of timers, but with no freedom to punt some for RT behavior.
with slack, you can run the mandatory ones first, and then the optionals until you hit some RT limit.. the optionals you do run are not going to bunch up to you at the time they become mandatory.
Fair enough.. so far it has not been a problem yet, mostly because we have to run all timers from softirq due to other wreckage (which makes the whole thing preemptible etc..). But once we can actually get away with running timers from hardirq again we'll have to sort something out.
Quoted 7 lines · Venkatesh Pallipadi
But, doing an exhaustive search for all softexpired timers, especially when
CPU is idle, has its advantages:
* it will result in less interruptions later (when CPU may be busy).
* it can reduce number of wakeups in cases where not yet expired timer in above description could be deleted before they expire.
* For timers resulting in task wakeups, doing wakeup on idle can improve the
overall efficiency of the system. It can also bring load balance/migration benefits.
Seems like a good idea in general.
arch/x86/kernel/process_64.c void cpu_idle(void) · line 153
Quoted 10 lines
arch/x86/kernel/process_64.c +2
-0@@ -149,6 +149,8 @@ void cpu_idle(void)preempt_enable_no_resched ();schedule ();preempt_disable (); +if (sysctl_hrtimer_greedy_lookup) +hrtimer_peek_ahead_timers ();
So why is it a sysctl and not default?
-Andi
Signature · 1 line
[email protected] -- Speaking for myself only
Quoted 10 lines
Signed-off-by Venkatesh Pallipadi <[email protected]>---
arch/x86/kernel/process_64.c | 2 +
include/linux/hrtimer.h | 14 ++++
include/linux/sched.h | 1 +
include/linux/timerqueue.h | 11 +++
kernel/hrtimer.c | 175 +++++++++++++++++++++++++++++++++++++-----kernel/sched.c| 2 +
kernel/sysctl.c | 7 ++
Quoted 2 lines
7 files changed, 191 insertions(+), 21 deletions(-)
Hi, venki, what version of thia patch against? I want to test the power consumption for your patch.
Quoted 12 lines · alex shi
Quoted 10 lines
Signed-off-by Venkatesh Pallipadi <[email protected]>---
arch/x86/kernel/process_64.c | 2 +
include/linux/hrtimer.h | 14 ++++
include/linux/sched.h | 1 +
include/linux/timerqueue.h | 11 +++
kernel/hrtimer.c | 175 +++++++++++++++++++++++++++++++++++++-----kernel/sched.c| 2 +
kernel/sysctl.c | 7 ++Quoted 2 lines
7 files changed, 191 insertions(+), 21 deletions(-)
Quoted 2 lines
Hi, venki, what version of thia patch against? I want to test the power consumption for your patch.
Hi Alex,
It should apply cleanly over 3.0. Thanks for testing the patch..
-Venki
Quoted 7 lines
Quoted 2 lines
Hi, venki, what version of thia patch against? I want to test the power consumption for your patch.
Hi Alex,
It should apply cleanly over 3.0. Thanks for testing the patch..
Sorry still can not apply the patch on 3.0 kernel, and seems 3.0 kernel is too old. :)
---
[alexs@lkp-os linux-2.6]$ git am ~/Fwd\:_\[RFC\]_Introduce_greedy_hrtimer_walk_on_idle
Applying: Introduce greedy hrtimer walk on idle
fatal: corrupt patch at line 46
Patch failed at 0001 Introduce greedy hrtimer walk on idle When you have resolved this problem run "git am --resolved".
---
Could you like to resend it against 3.1 kernel and cc to [email protected] ?
Quoted 3 lines
Hi Alex,
It should apply cleanly over 3.0. Thanks for testing the patch..
I tested the patch against 3.1 kernel for specpower benchmark on our machine, westmere core laptop Thinkpad t410(internal name lkp-t410), and on Romely-EP machine(lkp-sb03). No clear power or performance change found. the performance and power has no clear change for every level system load. from 0 to 100%.
Quoted 9 lines · alex shi
Quoted 3 lines
Hi Alex,
It should apply cleanly over 3.0. Thanks for testing the patch..
I tested the patch against 3.1 kernel for specpower benchmark on our machine, westmere core laptop Thinkpad t410(internal name lkp-t410), and on Romely-EP machine(lkp-sb03). No clear power or performance change found. the performance and power has no clear change for every level system load. from 0 to 100%.
Thanks Alex for testing this. Likely that with specpower there are not many active timers. Was the run with run level 5 and with all the system daemons that come with distro active?
Thanks,
Venki
Quoted 10 lines
Quoted 5 lines
I tested the patch against 3.1 kernel for specpower benchmark on our machine, westmere core laptop Thinkpad t410(internal name lkp-t410), and on Romely-EP machine(lkp-sb03). No clear power or performance change found. the performance and power has no clear change for every level system load. from 0 to 100%.
Thanks Alex for testing this. Likely that with specpower there are not many active timers. Was the run with run level 5 and with all the system daemons that come with distro active?
The testing run under level 3, without X system. and there really has no many daemons.
Following is the LOC record on the westmere laptop, before and after testing. testing costs 4368'.
LOC: 22850 24984 60558 61003 Local timer interrupts
---
LOC: 2773346 2772016 2623716 2644598 Local timer interrupts
There are about 65 interrupts per second on each of cpu. Yes it is not too much.
Without your patch, the timer interrupts number as following:
LOC: 10564 11942 11758 13075 Local timer interrupts
---
LOC: 2805402 2800421 2671229 2663266 Local timer interrupts
As to X system timers, I didn't find much timers on my working desktop, the LOC change just a little during 120'. That is i7, Ubuntu, without default daemons and running many APPs like, evolution/firefox etc etc.
LOC: 125 114 97 80 63 110108127
77084851 77289464 Local timer interrupts
--
LOC: 125 114 97 80 63 110112467
77087975 77294653 Local timer interrupts
So, guess, X system is not good candidate to show the patch effect. Any others benchmarks recommend?