[PATCH v2 tip/core/timers] Crude timer-wheel latency hacks

[PATCH v2 tip/core/timers] 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.	Add ->all_timers field to tbase_vec to count all timers, not
	just the non-deferrable ones.

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

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

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

Differences from v1:

o	Fix an embarrassing bug located by Oleg Nesterov where the
	timer wheel could be judged to be empty even if it contained
	deferrable timers.

							Thanx, Paul

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

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

[PATCH tip/core/timers 1/4] timers: Track total number of timers in list

[Paul E. McKenney]

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

Currently, the tvec_base structure's ->active_timers field tracks only
the non-deferrable timers, which means that even if ->active_timers is
zero, there might well be non-deferrable timers in the list.  This commit
therefore adds an ->all_timers field to track all the timers, whether
deferrable or not.

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

diff --git a/kernel/timer.c b/kernel/timer.c
index 6582b82fa966..2245b7374c3d 100644
--- a/kernel/timer.c
+++ b/kernel/timer.c
@@ -81,6 +81,7 @@ struct tvec_base {
 	unsigned long timer_jiffies;
 	unsigned long next_timer;
 	unsigned long active_timers;
+	unsigned long all_timers;
 	struct tvec_root tv1;
 	struct tvec tv2;
 	struct tvec tv3;
@@ -392,6 +393,7 @@ static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)
 			base->next_timer = timer->expires;
 		base->active_timers++;
 	}
+	base->all_timers++;
 }
 
 #ifdef CONFIG_TIMER_STATS
@@ -671,6 +673,7 @@ detach_expired_timer(struct timer_list *timer, struct tvec_base *base)
 	detach_timer(timer, true);
 	if (!tbase_get_deferrable(timer->base))
 		base->active_timers--;
+	base->all_timers--;
 }
 
 static int detach_if_pending(struct timer_list *timer, struct tvec_base *base,
@@ -685,6 +688,7 @@ static int detach_if_pending(struct timer_list *timer, struct tvec_base *base,
 		if (timer->expires == base->next_timer)
 			base->next_timer = base->timer_jiffies;
 	}
+	base->all_timers--;
 	return 1;
 }
 
@@ -1560,6 +1564,7 @@ static int init_timers_cpu(int cpu)
 	base->timer_jiffies = jiffies;
 	base->next_timer = base->timer_jiffies;
 	base->active_timers = 0;
+	base->all_timers = 0;
 	return 0;
 }
 
-- 
1.8.1.5

[PATCH tip/core/timers 2/4] 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 2245b7374c3d..295837e5e011 100644
--- a/kernel/timer.c
+++ b/kernel/timer.c
@@ -338,6 +338,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->all_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)
 {
@@ -1150,6 +1161,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 3/4] 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 295837e5e011..bdd1c00ec4ec 100644
--- a/kernel/timer.c
+++ b/kernel/timer.c
@@ -700,6 +700,7 @@ static int detach_if_pending(struct timer_list *timer, struct tvec_base *base,
 			base->next_timer = base->timer_jiffies;
 	}
 	base->all_timers--;
+	(void)catchup_timer_jiffies(base);
 	return 1;
 }
 
-- 
1.8.1.5

[PATCH tip/core/timers 4/4] 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 bdd1c00ec4ec..b49d2d0e879e 100644
--- a/kernel/timer.c
+++ b/kernel/timer.c
@@ -749,6 +749,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 2/4] timers: Reduce __run_timers() latency for empty list

[Oleg Nesterov]

On 01/14, Paul E. McKenney wrote:
>
> The __run_timers() function currently steps through the list one jiffy at
> a time

And this is very suboptimal if jiffies - timer_jiffies is huge. Looks
like, we should rework base->tv* structures, or (perhaps) optimize
the "cascade" logic so that __run_timers() can increment timer_jiffies
and move all the expired timers into work_list at one step. And the
->next_timer logic is obviously very suboptimal.

But this is almost off-topic, I agree that in the short term these
changes make sense.

> +static bool catchup_timer_jiffies(struct tvec_base *base)
> +{
> +#ifdef CONFIG_NO_HZ_FULL
> +	if (!base->all_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)
>  {
> @@ -1150,6 +1161,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;
> +	}


This is really minor, but perhaps it would be better to modify
run_timer_softirq() to call catchup_timer_jiffies() lockless along
with another fast-path time_after_eq() check.

Better yet, it would be nice to avoid raise_softirq(TIMER_SOFTIRQ),
but this is not simple due to hrtimer_run_pending().

Oleg.

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

[Oleg Nesterov]

On 01/14, Paul E. McKenney wrote:
>
> @@ -700,6 +700,7 @@ static int detach_if_pending(struct timer_list *timer, struct tvec_base *base,
>  			base->next_timer = base->timer_jiffies;
>  	}
>  	base->all_timers--;
> +	(void)catchup_timer_jiffies(base);

Agreed, but I think that detach_expired_timer() should do the same,
this can stop main loop in __run_timers().

Oleg.

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

[Peter Zijlstra]

On Wed, Jan 15, 2014 at 06:03:10PM +0100, Oleg Nesterov wrote:
> On 01/14, Paul E. McKenney wrote:
> >
> > The __run_timers() function currently steps through the list one jiffy at
> > a time
> 
> And this is very suboptimal if jiffies - timer_jiffies is huge. Looks
> like, we should rework base->tv* structures, or (perhaps) optimize
> the "cascade" logic so that __run_timers() can increment timer_jiffies
> and move all the expired timers into work_list at one step. And the
> ->next_timer logic is obviously very suboptimal.

Thomas is actually actively working on a replacement for the entire
cascade mess.

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

[Oleg Nesterov]

On 01/14, Paul E. McKenney wrote:
>
> @@ -749,6 +749,7 @@ __mod_timer(struct timer_list *timer, unsigned long expires,
>
>  	base = lock_timer_base(timer, &flags);
>
> +	(void)catchup_timer_jiffies(base);

Agreed, but perhaps it would be better to do this before
all_timers++ in internal_add_timer() ?

This is funny, but I already have the same change for ->next_timer,
if we add this optimization perhaps that trivial patch makes sense
too.

Oleg.

[PATCH 0/1] timers: internal_add_timer() should update ->next_timer if ->active_timers == 0

[Oleg Nesterov]

On 01/15, Oleg Nesterov wrote:
>
> This is funny, but I already have the same change for ->next_timer,
> if we add this optimization perhaps that trivial patch makes sense
> too.

Please see 1/1, it should not conflict with your changes.

Oleg.

[PATCH 1/1] timers: internal_add_timer() should update ->next_timer if ->active_timers == 0

[Oleg Nesterov]

internal_add_timer(timer) updates base->next_timer only if
timer->expires < base->next_timer. This is correct, but it also
makes sense to do the same if we add the first non-deferrable
timer.

Signed-off-by: Oleg Nesterov <oleg@redhat.com>
---
 kernel/timer.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/kernel/timer.c b/kernel/timer.c
index 6582b82..9492d57 100644
--- a/kernel/timer.c
+++ b/kernel/timer.c
@@ -388,9 +388,9 @@ static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)
 	 * Update base->active_timers and base->next_timer
 	 */
 	if (!tbase_get_deferrable(timer->base)) {
-		if (time_before(timer->expires, base->next_timer))
+		if (!base->active_timers++ ||
+		    time_before(timer->expires, base->next_timer))
 			base->next_timer = timer->expires;
-		base->active_timers++;
 	}
 }
 
-- 
1.5.5.1

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

[Oleg Nesterov]

forgot to mention...

On 01/14, Paul E. McKenney wrote:
>
> +static bool catchup_timer_jiffies(struct tvec_base *base)
> +{
> +#ifdef CONFIG_NO_HZ_FULL
> +	if (!base->all_timers) {
> +		base->timer_jiffies = jiffies;
> +		return 1;
> +	}
> +#endif /* #ifdef CONFIG_NO_HZ_FULL */
> +	return 0;
> +}

Do we really want ifdef?

This check is cheap, and !CONFIG_NO_HZ_FULL case looks a bit
strange because we still update ->all_timers for no reason.

Oleg.

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

[Josh Triplett]

On Wed, Jan 15, 2014 at 06:38:58PM +0100, Oleg Nesterov wrote:
> forgot to mention...
> 
> On 01/14, Paul E. McKenney wrote:
> >
> > +static bool catchup_timer_jiffies(struct tvec_base *base)
> > +{
> > +#ifdef CONFIG_NO_HZ_FULL
> > +	if (!base->all_timers) {
> > +		base->timer_jiffies = jiffies;
> > +		return 1;
> > +	}
> > +#endif /* #ifdef CONFIG_NO_HZ_FULL */
> > +	return 0;
> > +}
> 
> Do we really want ifdef?
> 
> This check is cheap, and !CONFIG_NO_HZ_FULL case looks a bit
> strange because we still update ->all_timers for no reason.

There's an easy way to improve this: instead of using an ifdef, put
"IS_ENABLED(CONFIG_NO_HZ_FULL) && " in the if condition.

- Josh Triplett

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

[Josh Triplett]

On Tue, Jan 14, 2014 at 09:20:46PM -0800, Paul E. McKenney wrote:
> 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 2245b7374c3d..295837e5e011 100644
> --- a/kernel/timer.c
> +++ b/kernel/timer.c
> @@ -338,6 +338,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->all_timers) {
> +		base->timer_jiffies = jiffies;
> +		return 1;
> +	}
> +#endif /* #ifdef CONFIG_NO_HZ_FULL */
> +	return 0;
> +}

In a function with return type "bool", please use true/false, not 1/0.

Please also document the semantic of the return value.

- Josh Triplett

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

[Steven Rostedt]

On Wed, 15 Jan 2014 12:32:45 -0800
Josh Triplett <josh@joshtriplett.org> wrote:

> On Wed, Jan 15, 2014 at 06:38:58PM +0100, Oleg Nesterov wrote:
> > forgot to mention...
> > 
> > On 01/14, Paul E. McKenney wrote:
> > >
> > > +static bool catchup_timer_jiffies(struct tvec_base *base)
> > > +{
> > > +#ifdef CONFIG_NO_HZ_FULL
> > > +	if (!base->all_timers) {
> > > +		base->timer_jiffies = jiffies;
> > > +		return 1;
> > > +	}
> > > +#endif /* #ifdef CONFIG_NO_HZ_FULL */
> > > +	return 0;
> > > +}
> > 
> > Do we really want ifdef?
> > 
> > This check is cheap, and !CONFIG_NO_HZ_FULL case looks a bit
> > strange because we still update ->all_timers for no reason.
> 
> There's an easy way to improve this: instead of using an ifdef, put
> "IS_ENABLED(CONFIG_NO_HZ_FULL) && " in the if condition.
> 

Why even bother with that? What's wrong with doing this check all the
time? Looks like it will save of the normal case too.

-- Steve

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

[Steven Rostedt]

On Tue, 14 Jan 2014 21:20:47 -0800
"Paul E. McKenney" <paulmck@linux.vnet.ibm.com> wrote:


> diff --git a/kernel/timer.c b/kernel/timer.c
> index 295837e5e011..bdd1c00ec4ec 100644
> --- a/kernel/timer.c
> +++ b/kernel/timer.c
> @@ -700,6 +700,7 @@ static int detach_if_pending(struct timer_list *timer, struct tvec_base *base,
>  			base->next_timer = base->timer_jiffies;
>  	}
>  	base->all_timers--;
> +	(void)catchup_timer_jiffies(base);

Why the "(void)" ?

-- Steve

>  	return 1;
>  }
>  

Re: [PATCH 1/1] timers: internal_add_timer() should update ->next_timer if ->active_timers == 0

[Steven Rostedt]

On Wed, 15 Jan 2014 18:31:37 +0100
Oleg Nesterov <oleg@redhat.com> wrote:

> internal_add_timer(timer) updates base->next_timer only if
> timer->expires < base->next_timer. This is correct, but it also
> makes sense to do the same if we add the first non-deferrable
> timer.
> 
> Signed-off-by: Oleg Nesterov <oleg@redhat.com>

Makes sense.

Reviewed-by: Steven Rostedt <rostedt@goodmis.org>

-- Steve

> ---
>  kernel/timer.c |    4 ++--
>  1 files changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/timer.c b/kernel/timer.c
> index 6582b82..9492d57 100644
> --- a/kernel/timer.c
> +++ b/kernel/timer.c
> @@ -388,9 +388,9 @@ static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)
>  	 * Update base->active_timers and base->next_timer
>  	 */
>  	if (!tbase_get_deferrable(timer->base)) {
> -		if (time_before(timer->expires, base->next_timer))
> +		if (!base->active_timers++ ||
> +		    time_before(timer->expires, base->next_timer))
>  			base->next_timer = timer->expires;
> -		base->active_timers++;
>  	}
>  }
>  

Re: [PATCH v2 tip/core/timers] Crude timer-wheel latency hacks

[Thomas Gleixner]

Paul,

On Tue, 14 Jan 2014, Paul E. McKenney wrote:
> 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:

so far that makes sense, though I'd rather like to redesign the whole
timer wheel mess than adding more duct tape to it. I can't dig into
the details right now as I'm dead tired and about to leave for a
funeral. i'll have a detailed look at this at the weekend.

Thanks,

	tglx

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

[Paul E. McKenney]

On Wed, Jan 15, 2014 at 03:54:05PM -0500, Steven Rostedt wrote:
> On Tue, 14 Jan 2014 21:20:47 -0800
> "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> wrote:
> 
> 
> > diff --git a/kernel/timer.c b/kernel/timer.c
> > index 295837e5e011..bdd1c00ec4ec 100644
> > --- a/kernel/timer.c
> > +++ b/kernel/timer.c
> > @@ -700,6 +700,7 @@ static int detach_if_pending(struct timer_list *timer, struct tvec_base *base,
> >  			base->next_timer = base->timer_jiffies;
> >  	}
> >  	base->all_timers--;
> > +	(void)catchup_timer_jiffies(base);
> 
> Why the "(void)" ?

Just a way of saying "I really did intend to ignore the return value."

							Thanx, Paul

> -- Steve
> 
> >  	return 1;
> >  }
> >  
> 

Re: [PATCH 1/1] timers: internal_add_timer() should update ->next_timer if ->active_timers == 0

[Paul E. McKenney]

On Wed, Jan 15, 2014 at 06:31:37PM +0100, Oleg Nesterov wrote:
> internal_add_timer(timer) updates base->next_timer only if
> timer->expires < base->next_timer. This is correct, but it also
> makes sense to do the same if we add the first non-deferrable
> timer.
> 
> Signed-off-by: Oleg Nesterov <oleg@redhat.com>

I have pulled this on in, thank you Oleg!

							Thanx, Paul

> ---
>  kernel/timer.c |    4 ++--
>  1 files changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/timer.c b/kernel/timer.c
> index 6582b82..9492d57 100644
> --- a/kernel/timer.c
> +++ b/kernel/timer.c
> @@ -388,9 +388,9 @@ static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)
>  	 * Update base->active_timers and base->next_timer
>  	 */
>  	if (!tbase_get_deferrable(timer->base)) {
> -		if (time_before(timer->expires, base->next_timer))
> +		if (!base->active_timers++ ||
> +		    time_before(timer->expires, base->next_timer))
>  			base->next_timer = timer->expires;
> -		base->active_timers++;
>  	}
>  }
> 
> -- 
> 1.5.5.1
> 
> 

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

[Paul E. McKenney]

On Wed, Jan 15, 2014 at 06:03:10PM +0100, Oleg Nesterov wrote:
> On 01/14, Paul E. McKenney wrote:
> >
> > The __run_timers() function currently steps through the list one jiffy at
> > a time
> 
> And this is very suboptimal if jiffies - timer_jiffies is huge. Looks
> like, we should rework base->tv* structures, or (perhaps) optimize
> the "cascade" logic so that __run_timers() can increment timer_jiffies
> and move all the expired timers into work_list at one step. And the
> ->next_timer logic is obviously very suboptimal.
> 
> But this is almost off-topic, I agree that in the short term these
> changes make sense.
> 
> > +static bool catchup_timer_jiffies(struct tvec_base *base)
> > +{
> > +#ifdef CONFIG_NO_HZ_FULL
> > +	if (!base->all_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)
> >  {
> > @@ -1150,6 +1161,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;
> > +	}
> 
> 
> This is really minor, but perhaps it would be better to modify
> run_timer_softirq() to call catchup_timer_jiffies() lockless along
> with another fast-path time_after_eq() check.

Given that this is at best a temporary solution, I would like to avoid
the complexity of this sort of optimization unless it turns out to be
a major performance issue.

> Better yet, it would be nice to avoid raise_softirq(TIMER_SOFTIRQ),
> but this is not simple due to hrtimer_run_pending().

And I do want to keep this pretty simple!

							Thanx, Paul

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

[Paul E. McKenney]

On Wed, Jan 15, 2014 at 03:47:10PM -0500, Steven Rostedt wrote:
> On Wed, 15 Jan 2014 12:32:45 -0800
> Josh Triplett <josh@joshtriplett.org> wrote:
> 
> > On Wed, Jan 15, 2014 at 06:38:58PM +0100, Oleg Nesterov wrote:
> > > forgot to mention...
> > > 
> > > On 01/14, Paul E. McKenney wrote:
> > > >
> > > > +static bool catchup_timer_jiffies(struct tvec_base *base)
> > > > +{
> > > > +#ifdef CONFIG_NO_HZ_FULL
> > > > +	if (!base->all_timers) {
> > > > +		base->timer_jiffies = jiffies;
> > > > +		return 1;
> > > > +	}
> > > > +#endif /* #ifdef CONFIG_NO_HZ_FULL */
> > > > +	return 0;
> > > > +}
> > > 
> > > Do we really want ifdef?
> > > 
> > > This check is cheap, and !CONFIG_NO_HZ_FULL case looks a bit
> > > strange because we still update ->all_timers for no reason.
> > 
> > There's an easy way to improve this: instead of using an ifdef, put
> > "IS_ENABLED(CONFIG_NO_HZ_FULL) && " in the if condition.
> 
> Why even bother with that? What's wrong with doing this check all the
> time? Looks like it will save of the normal case too.

Sold!  I removed the ifdef.

							Thanx, Paul

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

[Paul E. McKenney]

On Wed, Jan 15, 2014 at 06:08:35PM +0100, Oleg Nesterov wrote:
> On 01/14, Paul E. McKenney wrote:
> >
> > @@ -700,6 +700,7 @@ static int detach_if_pending(struct timer_list *timer, struct tvec_base *base,
> >  			base->next_timer = base->timer_jiffies;
> >  	}
> >  	base->all_timers--;
> > +	(void)catchup_timer_jiffies(base);
> 
> Agreed, but I think that detach_expired_timer() should do the same,
> this can stop main loop in __run_timers().

Good point, added to detach_expired_timer().

							Thanx, Paul

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

[Paul E. McKenney]

On Wed, Jan 15, 2014 at 12:33:55PM -0800, Josh Triplett wrote:
> On Tue, Jan 14, 2014 at 09:20:46PM -0800, Paul E. McKenney wrote:
> > 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 2245b7374c3d..295837e5e011 100644
> > --- a/kernel/timer.c
> > +++ b/kernel/timer.c
> > @@ -338,6 +338,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->all_timers) {
> > +		base->timer_jiffies = jiffies;
> > +		return 1;
> > +	}
> > +#endif /* #ifdef CONFIG_NO_HZ_FULL */
> > +	return 0;
> > +}
> 
> In a function with return type "bool", please use true/false, not 1/0.
> 
> Please also document the semantic of the return value.

Done for both, thank you.

							Thanx, Paul

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

[Paul E. McKenney]

On Wed, Jan 15, 2014 at 06:24:09PM +0100, Oleg Nesterov wrote:
> On 01/14, Paul E. McKenney wrote:
> >
> > @@ -749,6 +749,7 @@ __mod_timer(struct timer_list *timer, unsigned long expires,
> >
> >  	base = lock_timer_base(timer, &flags);
> >
> > +	(void)catchup_timer_jiffies(base);
> 
> Agreed, but perhaps it would be better to do this before
> all_timers++ in internal_add_timer() ?

Excellent point, changed.

> This is funny, but I already have the same change for ->next_timer,
> if we add this optimization perhaps that trivial patch makes sense
> too.

Yep, I queued your change in my series as well, thank you!

							Thanx, Paul

Re: [PATCH v2 tip/core/timers] Crude timer-wheel latency hacks

[Paul E. McKenney]

On Wed, Jan 15, 2014 at 11:22:41PM +0100, Thomas Gleixner wrote:
> Paul,
> 
> On Tue, 14 Jan 2014, Paul E. McKenney wrote:
> > 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:
> 
> so far that makes sense, though I'd rather like to redesign the whole
> timer wheel mess than adding more duct tape to it.

This is supposed to be in addition you your redesign, absolutely not
instead of your redesign.  For one thing, hopefully your redesign
will avoid jiffy-scanning in the case where the CPU has a pair of
timers separated by many jiffies.  My patches won't help in that case.

My patches are instead intended for testing in the meantime, and they
do help a bit in some common NO_HZ_FULL situations.

>                                                    I can't dig into
> the details right now as I'm dead tired and about to leave for a
> funeral. i'll have a detailed look at this at the weekend.

My sympathies!

And I will be sending out an updated series shortly anyway.

							Thanx, Paul