Skip to contentSkip to conversation

Introduce greedy hrtimer walk on idle

RFC In review Venkatesh Pallipadi 6 participants 19 messages Sep 23, 2011 – Nov 2, 2011

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

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
index ca6f7ab..8d3e287 100644
@@ -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
index fd0dc30..eaa43da 100644
@@ -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
index 14a6c7b..bd61826 100644
@@ -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
index 5088727..e79674f 100644
@@ -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
index fde6ff9..380bf2a 100644
@@ -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
index f175d98..5d1c701 100644
@@ -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
Acked-by on v1 1/1
#1 lore raw
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.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.

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.

#2 lore raw
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.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.

Quoted 9 lines

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.

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

#3 lore raw
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...)

#5 lore raw
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?

maintainer
#6 lore raw
Quoted 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.

#8 lore raw
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?

maintainer
#9 lore raw
Quoted 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. When sched_tick timer 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.

#10 lore raw
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. When sched_tick timer 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.

maintainer
#11 lore raw
Quoted 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. When sched_tick timer 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.

#12 lore raw
In reply to Venkatesh Pallipadi
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
index ca6f7ab..8d3e287 100644
@@ -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
#13 lore raw
In reply to Venkatesh Pallipadi
Quoted 10 lines

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

#14 lore raw
Quoted 12 lines · alex shi
Quoted 10 lines

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

#15 lore raw
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] ?

#16 lore raw
In reply to Venki Pallipadi
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%.

#17 lore raw
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

#18 lore raw
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?