[PATCH tip/core/rcu 0/3] Crude timer-wheel latency hacks

[PATCH tip/core/rcu 0/3] Crude timer-wheel latency hacks

[Paul E. McKenney]

Hello!

The following three patches provide some crude timer-wheel latency
patches.  I understand that a more comprehensive solution is in progress,
but in the meantime, these patches work well in cases where a given
CPU has either zero or one timers pending, which is a common case for
NO_HZ_FULL kernels.  So, on the off-chance that this is helpful to
someone, the individual patches are as follows:

1.	Avoid jiffy-at-a-time stepping when the timer wheel is empty.

2.	Avoid jiffy-at-a-time stepping when the timer wheel transitions
	to empty.

3.	Avoid jiffy-at-a-time stepping after a timer is added to an
	initially empty timer wheel.

							Thanx, Paul

------------------------------------------------------------------------

 b/kernel/timer.c |   17 +++++++++++++++++
 1 file changed, 17 insertions(+)

[PATCH tip/core/timers 1/3] timers: Reduce __run_timers() latency for empty list

[Paul E. McKenney]

From: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>

The __run_timers() function currently steps through the list one jiffy at
a time in order to update the timer wheel.  However, if the timer wheel
is empty, no adjustment is needed other than updating ->timer_jiffies.
In this case, which is likely to be common for NO_HZ_FULL kernels, the
kernel currently incurs a large latency for no good reason.  This commit
therefore short-circuits this case.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
---
 kernel/timer.c | 15 +++++++++++++++
 1 file changed, 15 insertions(+)

diff --git a/kernel/timer.c b/kernel/timer.c
index 6582b82fa966..21849275828f 100644
--- a/kernel/timer.c
+++ b/kernel/timer.c
@@ -337,6 +337,17 @@ void set_timer_slack(struct timer_list *timer, int slack_hz)
 }
 EXPORT_SYMBOL_GPL(set_timer_slack);
 
+static bool catchup_timer_jiffies(struct tvec_base *base)
+{
+#ifdef CONFIG_NO_HZ_FULL
+	if (!base->active_timers) {
+		base->timer_jiffies = jiffies;
+		return 1;
+	}
+#endif /* #ifdef CONFIG_NO_HZ_FULL */
+	return 0;
+}
+
 static void
 __internal_add_timer(struct tvec_base *base, struct timer_list *timer)
 {
@@ -1146,6 +1157,10 @@ static inline void __run_timers(struct tvec_base *base)
 	struct timer_list *timer;
 
 	spin_lock_irq(&base->lock);
+	if (catchup_timer_jiffies(base)) {
+		spin_unlock_irq(&base->lock);
+		return;
+	}
 	while (time_after_eq(jiffies, base->timer_jiffies)) {
 		struct list_head work_list;
 		struct list_head *head = &work_list;
-- 
1.8.1.5

[PATCH tip/core/timers 2/3] timers: Reduce future __run_timers() latency for newly emptied list

[Paul E. McKenney]

From: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>

The __run_timers() function currently steps through the list one jiffy at
a time in order to update the timer wheel.  However, if the timer wheel
is empty, no adjustment is needed other than updating ->timer_jiffies.
Therefore, if we just emptied the timer wheel, for example, by deleting
the last timer, we should mark the timer wheel as being up to date.
This marking will reduce (and perhaps eliminate) the jiffy-stepping that
a future __run_timers() call will need to do in response to some future
timer posting or migration.  This commit therefore catches ->timer_jiffies
for this case.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
---
 kernel/timer.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/kernel/timer.c b/kernel/timer.c
index 21849275828f..2b2e235ea7f1 100644
--- a/kernel/timer.c
+++ b/kernel/timer.c
@@ -693,6 +693,7 @@ static int detach_if_pending(struct timer_list *timer, struct tvec_base *base,
 	detach_timer(timer, clear_pending);
 	if (!tbase_get_deferrable(timer->base)) {
 		base->active_timers--;
+		(void)catchup_timer_jiffies(base);
 		if (timer->expires == base->next_timer)
 			base->next_timer = base->timer_jiffies;
 	}
-- 
1.8.1.5

[PATCH tip/core/timers 3/3] timers: Reduce future __run_timers() latency for first add to empty list

[Paul E. McKenney]

From: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>

The __run_timers() function currently steps through the list one jiffy at
a time in order to update the timer wheel.  However, if the timer wheel
is empty, no adjustment is needed other than updating ->timer_jiffies.
Therefore, just before we add a timer to an empty timer wheel, we should
mark the timer wheel as being up to date.  This marking will reduce (and
perhaps eliminate) the jiffy-stepping that a future __run_timers() call
will need to do in response to some future timer posting or migration.
This commit therefore updates ->timer_jiffies for this case.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
---
 kernel/timer.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/kernel/timer.c b/kernel/timer.c
index 2b2e235ea7f1..e539dbf5b9c5 100644
--- a/kernel/timer.c
+++ b/kernel/timer.c
@@ -745,6 +745,7 @@ __mod_timer(struct timer_list *timer, unsigned long expires,
 
 	base = lock_timer_base(timer, &flags);
 
+	(void)catchup_timer_jiffies(base);
 	ret = detach_if_pending(timer, base, false);
 	if (!ret && pending_only)
 		goto out_unlock;
-- 
1.8.1.5

Re: [PATCH tip/core/timers 1/3] timers: Reduce __run_timers() latency for empty list

[Oleg Nesterov]

On 01/13, Paul E. McKenney wrote:
>
> The __run_timers() function currently steps through the list one jiffy at
> a time in order to update the timer wheel.  However, if the timer wheel
> is empty, no adjustment is needed other than updating ->timer_jiffies.

Yes, but ->active_timers == 0 doesn't necessarily mean "empty", it only
counts the non-deferrable timers?

> In this case, which is likely to be common for NO_HZ_FULL kernels, the
> kernel currently incurs a large latency for no good reason.  This commit
> therefore short-circuits this case.
> 
> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> ---
>  kernel/timer.c | 15 +++++++++++++++
>  1 file changed, 15 insertions(+)
> 
> diff --git a/kernel/timer.c b/kernel/timer.c
> index 6582b82fa966..21849275828f 100644
> --- a/kernel/timer.c
> +++ b/kernel/timer.c
> @@ -337,6 +337,17 @@ void set_timer_slack(struct timer_list *timer, int slack_hz)
>  }
>  EXPORT_SYMBOL_GPL(set_timer_slack);
>
> +static bool catchup_timer_jiffies(struct tvec_base *base)
> +{
> +#ifdef CONFIG_NO_HZ_FULL
> +	if (!base->active_timers) {
> +		base->timer_jiffies = jiffies;
> +		return 1;
> +	}
> +#endif /* #ifdef CONFIG_NO_HZ_FULL */
> +	return 0;
> +}
> +
>  static void
>  __internal_add_timer(struct tvec_base *base, struct timer_list *timer)
>  {
> @@ -1146,6 +1157,10 @@ static inline void __run_timers(struct tvec_base *base)
>  	struct timer_list *timer;
>
>  	spin_lock_irq(&base->lock);

Do we really need to take base->lock before catchup_timer_jiffies() ?
->timer_jiffies can only be changed by us, and it seems that we do
not care if we race with base->active_timers++.

> +	if (catchup_timer_jiffies(base)) {
> +		spin_unlock_irq(&base->lock);
> +		return;

This is what I can't understand... Doesn't this mean that, unless this
base have a non-deferrable timer, we can never run the pending deferrable
timers even if the system/cpu is "busy" ?

Oleg.

Re: [PATCH tip/core/timers 1/3] timers: Reduce __run_timers() latency for empty list

[Paul E. McKenney]

On Tue, Jan 14, 2014 at 07:48:28PM +0100, Oleg Nesterov wrote:
> On 01/13, Paul E. McKenney wrote:
> >
> > The __run_timers() function currently steps through the list one jiffy at
> > a time in order to update the timer wheel.  However, if the timer wheel
> > is empty, no adjustment is needed other than updating ->timer_jiffies.
> 
> Yes, but ->active_timers == 0 doesn't necessarily mean "empty", it only
> counts the non-deferrable timers?

Right you are!  Color me slow and stupid...

Separate counter clearly required.

> > In this case, which is likely to be common for NO_HZ_FULL kernels, the
> > kernel currently incurs a large latency for no good reason.  This commit
> > therefore short-circuits this case.
> > 
> > Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > ---
> >  kernel/timer.c | 15 +++++++++++++++
> >  1 file changed, 15 insertions(+)
> > 
> > diff --git a/kernel/timer.c b/kernel/timer.c
> > index 6582b82fa966..21849275828f 100644
> > --- a/kernel/timer.c
> > +++ b/kernel/timer.c
> > @@ -337,6 +337,17 @@ void set_timer_slack(struct timer_list *timer, int slack_hz)
> >  }
> >  EXPORT_SYMBOL_GPL(set_timer_slack);
> >
> > +static bool catchup_timer_jiffies(struct tvec_base *base)
> > +{
> > +#ifdef CONFIG_NO_HZ_FULL
> > +	if (!base->active_timers) {
> > +		base->timer_jiffies = jiffies;
> > +		return 1;
> > +	}
> > +#endif /* #ifdef CONFIG_NO_HZ_FULL */
> > +	return 0;
> > +}
> > +
> >  static void
> >  __internal_add_timer(struct tvec_base *base, struct timer_list *timer)
> >  {
> > @@ -1146,6 +1157,10 @@ static inline void __run_timers(struct tvec_base *base)
> >  	struct timer_list *timer;
> >
> >  	spin_lock_irq(&base->lock);
> 
> Do we really need to take base->lock before catchup_timer_jiffies() ?
> ->timer_jiffies can only be changed by us, and it seems that we do
> not care if we race with base->active_timers++.

Given that this lock should be almost always acquired by the current
CPU, the penalty for acquiring it should be low.  After all, we were
acquiring it prior to this patch as many times as we are after this patch,
right?

> > +	if (catchup_timer_jiffies(base)) {
> > +		spin_unlock_irq(&base->lock);
> > +		return;
> 
> This is what I can't understand... Doesn't this mean that, unless this
> base have a non-deferrable timer, we can never run the pending deferrable
> timers even if the system/cpu is "busy" ?

It does, and that is a bug in my patch.  Good catch!

							Thanx, Paul

Re: [PATCH tip/core/timers 1/3] timers: Reduce __run_timers() latency for empty list

[Oleg Nesterov]

On 01/14, Paul E. McKenney wrote:
>
> On Tue, Jan 14, 2014 at 07:48:28PM +0100, Oleg Nesterov wrote:
> > >  __internal_add_timer(struct tvec_base *base, struct timer_list *timer)
> > >  {
> > > @@ -1146,6 +1157,10 @@ static inline void __run_timers(struct tvec_base *base)
> > >  	struct timer_list *timer;
> > >
> > >  	spin_lock_irq(&base->lock);
> >
> > Do we really need to take base->lock before catchup_timer_jiffies() ?
> > ->timer_jiffies can only be changed by us, and it seems that we do
> > not care if we race with base->active_timers++.
>
> Given that this lock should be almost always acquired by the current
> CPU, the penalty for acquiring it should be low.  After all, we were
> acquiring it prior to this patch as many times as we are after this patch,
> right?

Yes. But

	if (catchup_timer_jiffies())
		return;

looks a bit simpler and can save a couple of insn. I won't argue of course,
this is minor. And you already sent v2, I'll try add some comments...

Oleg.