timer: Lazily wakup nohz CPU when adding new timer.
PATCH 1/1 timer: Lazily wakup nohz CPU when adding new timer.
Currently, when a new timer added to timer wheel for a nohz_active CPU, the target CPU will always be waked up.
In fact, if the new added timer is after the base->next_timer, we don't need wake up the target CPU since it will not change the sleep time. A lazy wake up is better in such scenario.
I cooked a test scenario. On my 32 cores system, a driver on CPU 15 continuous enqueues timer to CPU 8/9/10/11 with random expire and then checks the idle_calls difference after 10 seconds. Below data shows that lazy wake up do reduce the wakeup a lot.
w/o Lazy w/ lazy
CPU 8: 135 88
CPU 9: 238 43
CPU 10: 157 83
CPU 11: 172 70
--- kernel/time/timer.c | 21 ++++++++++++++------- 1 file changed, 14 insertions(+), 7 deletions(-)
kernel/time/timer.c +14 -7
@@ -414,6 +414,8 @@ __internal_add_timer(struct tvec_base *base, struct timer_list *timer)static void internal_add_timer (struct tvec_base *base,struct timer_list *timer) { +bool kick_nohz = false; +/* Advance base->jiffies, if the base is empty */ if (!base->all_timers++) base->timer_jiffies = jiffies;
@@ -424,9 +426,17 @@ static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)*/ if (!(timer->flags &TIMER_DEFERRABLE )) {if (!base->active_timers++ || -time_before (timer->expires, base->next_timer)) +time_before (timer->expires, base->next_timer)) { base->next_timer = timer->expires; - } +/* +* CPU in dynticks need reevaluate the timer wheel +* if newer timer added with next_timer updated. +*/ +if (base->nohz_active) + kick_nohz = true; + } + }else if (base->nohz_active &&tick_nohz_full_cpu (base->cpu)) + kick_nohz = true;/* * Check whether the other CPU is in dynticks mode and needs
@@ -441,11 +451,8 @@ static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)* require special care against races with idle_cpu(), lets deal * with that later. */ -if (base->nohz_active) { -if (!(timer->flags &TIMER_DEFERRABLE ) || -tick_nohz_full_cpu (base->cpu)) -wake_up_nohz_cpu (base->cpu); - } +if (kick_nohz) +wake_up_nohz_cpu (base->cpu); }#ifdef CONFIG_TIMER_STATS
Signature · 1 line
1.8.3.1
Ping for any response.
Thanks
--jyh
Quoted 78 lines · Yunhong Jiang
Currently, when a new timer added to timer wheel for a
nohz_activeCPU, the target CPU will always be waked up.In fact, if the new added timer is after the
base->next_timer, we don't need wake up the target CPU since it will not change the sleep time. A lazy wake up is better in such scenario.I cooked a test scenario. On my 32 cores system, a driver on CPU 15 continuous enqueues timer to CPU 8/9/10/11 with random expire and then checks the
idle_callsdifference after 10 seconds. Below data shows that lazy wake up do reduce the wakeup a lot.w/o Lazy w/ lazy
CPU 8: 135 88
CPU 9: 238 43
CPU 10: 157 83
CPU 11: 172 70Signed-off-by Yunhong Jiang <[email protected]>--- kernel/time/timer.c | 21 ++++++++++++++------- 1 file changed, 14 insertions(+), 7 deletions(-)kernel/time/timer.c +14
-7@@ -414,6 +414,8 @@ __internal_add_timer(struct tvec_base *base, struct timer_list *timer)static void internal_add_timer (struct tvec_base *base,struct timer_list *timer) { +bool kick_nohz = false; +/* Advance base->jiffies, if the base is empty */ if (!base->all_timers++) base->timer_jiffies = jiffies;@@ -424,9 +426,17 @@ static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)*/ if (!(timer->flags &TIMER_DEFERRABLE )) {if (!base->active_timers++ || -time_before (timer->expires, base->next_timer)) +time_before (timer->expires, base->next_timer)) { base->next_timer = timer->expires; - } +/* +* CPU in dynticks need reevaluate the timer wheel +* if newer timer added with next_timer updated. +*/ +if (base->nohz_active) + kick_nohz = true; + } + }else if (base->nohz_active &&tick_nohz_full_cpu (base->cpu)) + kick_nohz = true;/* * Check whether the other CPU is in dynticks mode and needs @@ -441,11 +451,8 @@ static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)* require special care against races with idle_cpu(), lets deal * with that later. */ -if (base->nohz_active) { -if (!(timer->flags &TIMER_DEFERRABLE ) || -tick_nohz_full_cpu (base->cpu)) -wake_up_nohz_cpu (base->cpu); - } +if (kick_nohz) +wake_up_nohz_cpu (base->cpu); }#ifdef CONFIG_TIMER_STATS Signature · 7 lines
1.8.3.1 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Quoted 14 lines · Yunhong Jiang
static void
internal_add_timer(struct tvec_base *base, struct timer_list *timer){kernel/time/timer.c +3
-1+bool kick_nohz = false; +/* Advance base->jiffies, if the base is empty */ if (!base->all_timers++) base->timer_jiffies = jiffies;@@ -424,9 +426,17 @@ static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)*/ if (!(timer->flags &TIMER_DEFERRABLE )) {if (!base->active_timers++ || -time_before (timer->expires, base->next_timer)) +time_before (timer->expires, base->next_timer)) { base->next_timer = timer->expires;
kernel/time/timer.c static void internal_add_timer(struct tvec_base *base, struct timer_list *timer) · line 439
Quoted 10 lines
kernel/time/timer.c +9
-1- } +/* +* CPU in dynticks need reevaluate the timer wheel +* if newer timer added with next_timer updated. +*/ +if (base->nohz_active) + kick_nohz = true; + } + }else if (base->nohz_active &&tick_nohz_full_cpu (base->cpu)) + kick_nohz = true;
Why do you want to kick the other cpu when a deferrable timer got added?
Thanks,
tglx
Quoted 19 lines · Thomas Gleixner
Quoted 18 lines · Yunhong Jiang
static void
internal_add_timer(struct tvec_base *base, struct timer_list *timer){kernel/time/timer.c +6
-2+bool kick_nohz = false; +/* Advance base->jiffies, if the base is empty */ if (!base->all_timers++) base->timer_jiffies = jiffies;@@ -424,9 +426,17 @@ static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)*/ if (!(timer->flags &TIMER_DEFERRABLE )) {if (!base->active_timers++ || -time_before (timer->expires, base->next_timer)) +time_before (timer->expires, base->next_timer)) { base->next_timer = timer->expires; - } +/* +* CPU in dynticks need reevaluate the timer wheel +* if newer timer added with next_timer updated.
Quoted 8 lines
kernel/time/timer.c static void internal_add_timer(struct tvec_base *base, struct timer_list *timer) · line 439
Quoted 6 lines
kernel/time/timer.c +6
-0+*/ +if (base->nohz_active) + kick_nohz = true; + } + }else if (base->nohz_active &&tick_nohz_full_cpu (base->cpu)) + kick_nohz = true;Why do you want to kick the other cpu when a deferrable timer got added?
This is what happens in current implementation and this patch does not change the logic. According to the comments, it's to avoid race with idle_cpu(). Frankly speaking, I didn't get the idea of the race.
Viresh, do you have any hints?
Thanks
--jyh
Quoted 9 lines
Thanks,
tglx
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Cc'ing Frederic.
Quoted 29 lines · Yunhong Jiang
Quoted 19 lines · Thomas Gleixner
Quoted 18 lines · Yunhong Jiang
static void
internal_add_timer(struct tvec_base *base, struct timer_list *timer){kernel/time/timer.c +6
-2+bool kick_nohz = false; +/* Advance base->jiffies, if the base is empty */ if (!base->all_timers++) base->timer_jiffies = jiffies;@@ -424,9 +426,17 @@ static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)*/ if (!(timer->flags &TIMER_DEFERRABLE )) {if (!base->active_timers++ || -time_before (timer->expires, base->next_timer)) +time_before (timer->expires, base->next_timer)) { base->next_timer = timer->expires; - } +/* +* CPU in dynticks need reevaluate the timer wheel +* if newer timer added with next_timer updated. Quoted 8 lines
kernel/time/timer.c static void internal_add_timer(struct tvec_base *base, struct timer_list *timer) · line 439
Quoted 6 lines
kernel/time/timer.c +6
-0+*/ +if (base->nohz_active) + kick_nohz = true; + } + }else if (base->nohz_active &&tick_nohz_full_cpu (base->cpu)) + kick_nohz = true;Why do you want to kick the other cpu when a deferrable timer got added?
Quoted 5 lines
This is what happens in current implementation and this patch does not change the logic. According to the comments, it's to avoid race with
idle_cpu(). Frankly speaking, I didn't get the idea of the race.Viresh, do you have any hints?
I haven't looked at the core since few months now and looks like I don't remember anything :)
This thread is where we discussed it initially:
http://marc.info/?l=linux-kernel&m=139039035809125
AFAIU, this is why we kick the other CPU for a deferrable timer:
- The other CPU is a full-dynticks capable CPU and may be running tickless and we should serve the timer in time (even if it is deferrable) if the CPU isn't idle.
- We could have saved the kick for a full-dynticks idle CPU, but a race can happen where we thought the CPU is idle, but it has just started serving userspace tick-lessly. And the timer wouldn't be served for long time, even when the cpu was busy.
Ofcourse, Frederic will kick me if I forgot the lessons he gave me earlier :)
Signature · 1 line
viresh
Quoted 36 lines · Viresh Kumar
Cc'ing Frederic.
Quoted 33 lines · Yunhong Jiang
Quoted 19 lines · Thomas Gleixner
Quoted 18 lines · Yunhong Jiang
static void
internal_add_timer(struct tvec_base *base, struct timer_list *timer){kernel/time/timer.c +6
-2+bool kick_nohz = false; +/* Advance base->jiffies, if the base is empty */ if (!base->all_timers++) base->timer_jiffies = jiffies;@@ -424,9 +426,17 @@ static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)*/ if (!(timer->flags &TIMER_DEFERRABLE )) {if (!base->active_timers++ || -time_before (timer->expires, base->next_timer)) +time_before (timer->expires, base->next_timer)) { base->next_timer = timer->expires; - } +/* +* CPU in dynticks need reevaluate the timer wheel +* if newer timer added with next_timer updated. Quoted 8 lines
kernel/time/timer.c static void internal_add_timer(struct tvec_base *base, struct timer_list *timer) · line 439
Quoted 6 lines
kernel/time/timer.c +6
-0+*/ +if (base->nohz_active) + kick_nohz = true; + } + }else if (base->nohz_active &&tick_nohz_full_cpu (base->cpu)) + kick_nohz = true;Why do you want to kick the other cpu when a deferrable timer got added?
This is what happens in current implementation and this patch does not change the logic. According to the comments, it's to avoid race with
idle_cpu(). Frankly speaking, I didn't get the idea of the race.
Quoted 8 lines
Quoted 1 line
Viresh, do you have any hints?
I haven't looked at the core since few months now and looks like I don't remember anything :)
This thread is where we discussed it initially:
http://marc.info/?l=linux-kernel&m=139039035809125
Viresh, thanks for the link, it's helpful.
Quoted 8 lines
AFAIU, this is why we kick the other CPU for a deferrable timer:
- The other CPU is a full-dynticks capable CPU and may be running tickless and we should serve the timer in time (even if it is deferrable) if the CPU isn't idle.
- We could have saved the kick for a full-dynticks idle CPU, but a race can happen where we thought the CPU is idle, but it has just started serving userspace tick-lessly. And the timer wouldn't be served for long time, even when the cpu was busy.
Thanks for explaination. Frederic's reply on that thread
(http://marc.info/?l=linux-pm&m=139048414803209&w=2) also gives clear information.
A naive question is, why it's sure a tick will happen when the tickless processor is in idle? Is it because scheduler load balance is sure to send a tick to the processor in future?
Thanks
--jyh
Quoted 11 lines
Ofcourse, Frederic will kick me if I forgot the lessons he gave me earlier :)
Signature · 6 lines
viresh -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Quoted 2 lines · Yunhong Jiang
A naive question is, why it's sure a tick will happen when the tickless processor is in idle?
How do you get this impression? I don't think anyone has said that.
We are talking about deferrable timers, which by design are only required if the target CPU is not-idle. If it is idle, then the timer isn't required to be serviced until the CPU wakes up. And the CPU can take whatever time it wants to wake up again.
Quoted 2 lines
Is it because scheduler load balance is sure to send a tick to the processor in future?
No. We aren't expecting the CPU to wake up any time soon. Just ignore the deferrable timer.
Signature · 1 line
viresh
Quoted 5 lines · Viresh Kumar
Quoted 2 lines · Yunhong Jiang
A naive question is, why it's sure a tick will happen when the tickless processor is in idle?
How do you get this impression? I don't think anyone has said that.
Viresh, thanks for your reply for my question.
I got this impression from Frederic's comments on
http://marc.info/?l=linux-kernel&m=139048415303210&w=2, "So you simply rely on the next tick to see the new timer. This should work with CONFIG_NO_HZ_IDLE but not with CONFIG_NO_HZ_FULL since the target may be running without the tick".
Per my understanding of this comment, it means we can rely on the next tick for CONFIG_NO_HZ_IDLE, which means it's sure a tick will happen for CONFIG_NO_HZ_IDLE, am I right?
Quoted 5 lines
We are talking about deferrable timers, which by design are only required if the target CPU is not-idle. If it is idle, then the timer isn't required to be serviced until the CPU wakes up. And the CPU can take whatever time it wants to wake up again.
Hmm, per http://lxr.free-electrons.com/source/include/linux/timer.h#L51, the deferreable timer will be serviced when the CPU eventually wakes up "with a subsequent non-deferrable timer". If there is no non-deferrable timer, based on Frederic's comments, we in fact depends on next tick.
My confusion is, why we are sure there is next tick on CONFIG_NO_HZ_IDLE idle processor to wake it up. If there is no tick, and no other timer, will the timer get no chance to be waken up at all? I don't think "deferred for ever" is deferreable.
Thanks
-jyh
Quoted 9 lines
Quoted 3 lines
Is it because scheduler load balance is sure to send a tick to the processor in future?
No. We aren't expecting the CPU to wake up any time soon. Just ignore the deferrable timer.
Signature · 1 line
viresh
Quoted 8 lines · Yunhong Jiang
I got this impression from Frederic's comments on
http://marc.info/?l=linux-kernel&m=139048415303210&w=2, "So you simply rely on the next tick to see the new timer. This should work withCONFIG_NO_HZ_IDLEbut not withCONFIG_NO_HZ_FULLsince the target may be running without the tick".
Per my understanding of this comment, it means we can rely on the next tick forCONFIG_NO_HZ_IDLE, which means it's sure a tick will happen forCONFIG_NO_HZ_IDLE, am I right?
Yeah, the CPU wouldn't like in idle for ever but the time is not known and it can be really really long.
Quoted 3 lines
Hmm, per http://lxr.free-electrons.com/source/include/linux/timer.h#L51, the deferreable timer will be serviced when the CPU eventually wakes up "with a subsequent non-deferrable timer".
It will be an IPI mostly..
Quoted 2 lines
If there is no non-deferrable timer, based
on Frederic's comments, we in fact depends on next tick.
So, the cpu will wake up when it receives an IPI. The first thing we do then is to restart the tick and we will then service all the pending deferred timers.
Quoted 4 lines
My confusion is, why we are sure there is next tick on
CONFIG_NO_HZ_IDLEidle processor to wake it up. If there is no tick, and no other timer, will the timer get no chance to be waken up at all? I don't think "deferred for ever" is deferreable.
There are many kind of works we may want to do. If its really important to be done earlier, then it should be serviced with a timer.
deferred timers are better used for activities, which are irrelevant once the CPU is idle. One case is doing some per-cpu load tracking for cpufreq governors or the work that vmstat does.
Even if the CPU wakes up after few hours (hypothetically), it shouldn't matter.
Signature · 1 line
viresh
Quoted 34 lines · Viresh Kumar
Quoted 8 lines · Yunhong Jiang
I got this impression from Frederic's comments on
http://marc.info/?l=linux-kernel&m=139048415303210&w=2, "So you simply rely on the next tick to see the new timer. This should work withCONFIG_NO_HZ_IDLEbut not withCONFIG_NO_HZ_FULLsince the target may be running without the tick".
Per my understanding of this comment, it means we can rely on the next tick forCONFIG_NO_HZ_IDLE, which means it's sure a tick will happen forCONFIG_NO_HZ_IDLE, am I right?Yeah, the CPU wouldn't like in idle for ever but the time is not known and it can be really really long.
Quoted 3 lines
Hmm, per http://lxr.free-electrons.com/source/include/linux/timer.h#L51, the deferreable timer will be serviced when the CPU eventually wakes up "with a subsequent non-deferrable timer".
It will be an IPI mostly..
Quoted 2 lines
If there is no non-deferrable timer, based
on Frederic's comments, we in fact depends on next tick.So, the cpu will wake up when it receives an IPI. The first thing we do then is to restart the tick and we will then service all the pending deferred timers.
Quoted 4 lines
My confusion is, why we are sure there is next tick on
CONFIG_NO_HZ_IDLEidle processor to wake it up. If there is no tick, and no other timer, will the timer get no chance to be waken up at all? I don't think "deferred for ever" is deferreable.There are many kind of works we may want to do. If its really important to be done earlier, then it should be serviced with a timer.
Quoted 6 lines
deferred timers are better used for activities, which are irrelevant once the CPU is idle. One case is doing some per-cpu load tracking for cpufreq governors or the work that vmstat does.
Even if the CPU wakes up after few hours (hypothetically), it shouldn't matter.
Viresh, thanks for the clarification.
So seems the original patch is correct to wakeup the full dyntick CPU even for deferred timer. Thomas/Fred, your idea?
Thanks
--jyh
Quoted 8 lines
Signature · 7 lines
-- viresh -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Quoted 44 lines · Viresh Kumar
Cc'ing Frederic.
Quoted 29 lines · Yunhong Jiang
Quoted 19 lines · Thomas Gleixner
Quoted 18 lines · Yunhong Jiang
static void
internal_add_timer(struct tvec_base *base, struct timer_list *timer){kernel/time/timer.c +6
-2+bool kick_nohz = false; +/* Advance base->jiffies, if the base is empty */ if (!base->all_timers++) base->timer_jiffies = jiffies;@@ -424,9 +426,17 @@ static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)*/ if (!(timer->flags &TIMER_DEFERRABLE )) {if (!base->active_timers++ || -time_before (timer->expires, base->next_timer)) +time_before (timer->expires, base->next_timer)) { base->next_timer = timer->expires; - } +/* +* CPU in dynticks need reevaluate the timer wheel +* if newer timer added with next_timer updated. Quoted 8 lines
kernel/time/timer.c static void internal_add_timer(struct tvec_base *base, struct timer_list *timer) · line 439
Quoted 6 lines
kernel/time/timer.c +6
-0+*/ +if (base->nohz_active) + kick_nohz = true; + } + }else if (base->nohz_active &&tick_nohz_full_cpu (base->cpu)) + kick_nohz = true;Why do you want to kick the other cpu when a deferrable timer got added?
Quoted 5 lines
This is what happens in current implementation and this patch does not change the logic. According to the comments, it's to avoid race with
idle_cpu(). Frankly speaking, I didn't get the idea of the race.Viresh, do you have any hints?
I haven't looked at the core since few months now and looks like I don't remember anything :)
This thread is where we discussed it initially:
http://marc.info/?l=linux-kernel&m=139039035809125
Quoted 8 lines
AFAIU, this is why we kick the other CPU for a deferrable timer:
- The other CPU is a full-dynticks capable CPU and may be running tickless and we should serve the timer in time (even if it is deferrable) if the CPU isn't idle.
- We could have saved the kick for a full-dynticks idle CPU, but a race can happen where we thought the CPU is idle, but it has just started serving userspace tick-lessly. And the timer wouldn't be served for long time, even when the cpu was busy.
Yeah, deferrable implies "idle deferrable", not "user deferrable". So if the CPU is tickless in userland, we want to kick it to handle the deferrable timer.
This is further optimizable by making sure that we don't kick nohz full CPUs when they are idle as well.
That said the handling of deferrable timers is buggy in full dynticks because get_next_timer_interrupt() ignores deferrable timers always. I should pass an "ignore_deferrable" parameter for non-idle dynticks but I'm afraid this will uncover timers that people don't want to see. But we'll have to do it eventually and maybe audit which of these deferrable timers also implies deferrable in userspace.
Quoted 3 lines
Ofcourse, Frederic will kick me if I forgot the lessons he gave me earlier :)
Oh I know too much how easy it is to forget what $CODE_I_REVIEWED_X_MONTH_AGO actually does ;-)
Quoted 58 lines · Yunhong Jiang
Currently, when a new timer added to timer wheel for a
nohz_activeCPU, the target CPU will always be waked up.In fact, if the new added timer is after the
base->next_timer, we don't need wake up the target CPU since it will not change the sleep time. A lazy wake up is better in such scenario.I cooked a test scenario. On my 32 cores system, a driver on CPU 15 continuous enqueues timer to CPU 8/9/10/11 with random expire and then checks the
idle_callsdifference after 10 seconds. Below data shows that lazy wake up do reduce the wakeup a lot.w/o Lazy w/ lazy
CPU 8: 135 88
CPU 9: 238 43
CPU 10: 157 83
CPU 11: 172 70Signed-off-by Yunhong Jiang <[email protected]>--- kernel/time/timer.c | 21 ++++++++++++++------- 1 file changed, 14 insertions(+), 7 deletions(-)kernel/time/timer.c +12
-2@@ -414,6 +414,8 @@ __internal_add_timer(struct tvec_base *base, struct timer_list *timer)static void internal_add_timer (struct tvec_base *base,struct timer_list *timer) { +bool kick_nohz = false; +/* Advance base->jiffies, if the base is empty */ if (!base->all_timers++) base->timer_jiffies = jiffies;@@ -424,9 +426,17 @@ static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)*/ if (!(timer->flags &TIMER_DEFERRABLE )) {if (!base->active_timers++ || -time_before (timer->expires, base->next_timer)) +time_before (timer->expires, base->next_timer)) { base->next_timer = timer->expires; - } +/* +* CPU in dynticks need reevaluate the timer wheel +* if newer timer added with next_timer updated. +*/ +if (base->nohz_active) + kick_nohz = true; + } + }else if (base->nohz_active &&tick_nohz_full_cpu (base->cpu)) + kick_nohz = true;/* * Check whether the other CPU is in dynticks mode and needs @@ -441,11 +451,8 @@ static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)* require special care against races with idle_cpu(), lets deal
kernel/time/timer.c static void internal_add_timer(struct tvec_base *base, struct timer_list *timer) · line 456
Quoted 10 lines
kernel/time/timer.c +2
-5* with that later. */ -if (base->nohz_active) { -if (!(timer->flags &TIMER_DEFERRABLE ) || -tick_nohz_full_cpu (base->cpu)) -wake_up_nohz_cpu (base->cpu); - } +if (kick_nohz) +wake_up_nohz_cpu (base->cpu); }
This patch makes sense. Thomas?