[PATCH v3 tip/core/timers 0/5] Crude timer-wheel latency hacks

[PATCH v3 tip/core/timers 0/5] Crude timer-wheel latency hacks

[Paul E. McKenney]

Hello!

The following five 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.
Note that these patches do not help in the case where a given timer wheel
has a pair of widely separated timers, while the more comprehensive
solution is likely to handle more gracefully.  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.

5.	Make internal_add_timer() update ->next_timer if ->active_timers == 0,
	courtesy of Oleg Nesterov.

Differences from v2:

o	Add patch #5 from Oleg.

o	Move the check for adding to an empty timer wheel from mod_timer()
	to internal_add_timer(), as suggested by Oleg Nesterov.

o	Addressed review comments from Oleg, Steven Rostedt, Josh Triplett,
	and Fengguang Wu.

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 |   30 ++++++++++++++++++++++++++++--
 1 file changed, 28 insertions(+), 2 deletions(-)

[PATCH tip/core/timers 1/5] 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/5] 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 | 18 ++++++++++++++++++
 1 file changed, 18 insertions(+)

diff --git a/kernel/timer.c b/kernel/timer.c
index 2245b7374c3d..eff9052001e1 100644
--- a/kernel/timer.c
+++ b/kernel/timer.c
@@ -338,6 +338,20 @@ void set_timer_slack(struct timer_list *timer, int slack_hz)
 }
 EXPORT_SYMBOL_GPL(set_timer_slack);
 
+/*
+ * If the list is empty, catch up ->timer_jiffies to the current time.
+ * The caller must hold the tvec_base lock.  Returns true if the list
+ * was empty and therefore ->timer_jiffies was updated.
+ */
+static bool catchup_timer_jiffies(struct tvec_base *base)
+{
+	if (!base->all_timers) {
+		base->timer_jiffies = jiffies;
+		return true;
+	}
+	return false;
+}
+
 static void
 __internal_add_timer(struct tvec_base *base, struct timer_list *timer)
 {
@@ -1150,6 +1164,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/5] 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 | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/kernel/timer.c b/kernel/timer.c
index eff9052001e1..1e53acb33361 100644
--- a/kernel/timer.c
+++ b/kernel/timer.c
@@ -688,6 +688,7 @@ detach_expired_timer(struct timer_list *timer, struct tvec_base *base)
 	if (!tbase_get_deferrable(timer->base))
 		base->active_timers--;
 	base->all_timers--;
+	(void)catchup_timer_jiffies(base);
 }
 
 static int detach_if_pending(struct timer_list *timer, struct tvec_base *base,
@@ -703,6 +704,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/5] 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 1e53acb33361..b9cc28271646 100644
--- a/kernel/timer.c
+++ b/kernel/timer.c
@@ -398,6 +398,7 @@ __internal_add_timer(struct tvec_base *base, struct timer_list *timer)
 
 static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)
 {
+	(void)catchup_timer_jiffies(base);
 	__internal_add_timer(base, timer);
 	/*
 	 * Update base->active_timers and base->next_timer
-- 
1.8.1.5

[PATCH tip/core/timers 5/5] timers: Make internal_add_timer() update ->next_timer if ->active_timers == 0

[Paul E. McKenney]

From: Oleg Nesterov <oleg@redhat.com>

The internal_add_timer() function 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>
Reviewed-by: Steven Rostedt <rostedt@goodmis.org>
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
---
 kernel/timer.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/kernel/timer.c b/kernel/timer.c
index b9cc28271646..e74685309b14 100644
--- a/kernel/timer.c
+++ b/kernel/timer.c
@@ -404,9 +404,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++;
 	}
 	base->all_timers++;
 }
-- 
1.8.1.5

Re: [PATCH v3 tip/core/timers 0/5] Crude timer-wheel latency hacks

[Josh Triplett]

On Wed, Jan 15, 2014 at 08:02:03PM -0800, Paul E. McKenney wrote:
> Hello!
> 
> The following five 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.
> Note that these patches do not help in the case where a given timer wheel
> has a pair of widely separated timers, while the more comprehensive
> solution is likely to handle more gracefully.  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.
> 
> 5.	Make internal_add_timer() update ->next_timer if ->active_timers == 0,
> 	courtesy of Oleg Nesterov.

For all five patches in v3:

Reviewed-by: Josh Triplett <josh@joshtriplett.org>

Re: [PATCH v3 tip/core/timers 0/5] Crude timer-wheel latency hacks

[Peter Zijlstra]

On Wed, Jan 15, 2014 at 08:02:03PM -0800, Paul E. McKenney wrote:
> Hello!
> 
> The following five 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.
> Note that these patches do not help in the case where a given timer wheel
> has a pair of widely separated timers, while the more comprehensive
> solution is likely to handle more gracefully.  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.
> 
> 5.	Make internal_add_timer() update ->next_timer if ->active_timers == 0,
> 	courtesy of Oleg Nesterov.

They seem like perfectly fine bandaids ;-)

Acked-by: Peter Zijlstra <peterz@infradead.org>

Re: [PATCH v3 tip/core/timers 0/5] Crude timer-wheel latency hacks

[Oleg Nesterov]

On 01/15, Paul E. McKenney wrote:
>
> The following five patches provide some crude timer-wheel latency patches.

The whole series looks fine to me,

Reviewed-by: Oleg Nesterov <oleg@redhat.com>

Re: [PATCH v3 tip/core/timers 0/5] Crude timer-wheel latency hacks

[Steven Rostedt]

On Wed, 15 Jan 2014 20:02:03 -0800
"Paul E. McKenney" <paulmck@linux.vnet.ibm.com> wrote:

> Hello!
> 
> The following five 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.
> Note that these patches do not help in the case where a given timer wheel
> has a pair of widely separated timers, while the more comprehensive
> solution is likely to handle more gracefully.  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.
> 
> 5.	Make internal_add_timer() update ->next_timer if ->active_timers == 0,
> 	courtesy of Oleg Nesterov.
> 

Although I think the "(void)" is ugly and uncalled for (there's lots of
functions that return a value in the kernel that don't have that). But,
it's not up to me to argue this.

For all 5 patches,

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

-- Steve