Crude timer-wheel latency hacks

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

From: "Paul E. McKenney" <[email protected]>

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.

---
 kernel/timer.c | 5 +++++
 1 file changed, 5 insertions(+)

index 6582b82fa966..2245b7374c3d 100644
@@ -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

From: "Paul E. McKenney" <[email protected]>

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.

---
 kernel/timer.c | 2 ++
 1 file changed, 2 insertions(+)

index eff9052001e1..1e53acb33361 100644
@@ -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

From: Oleg Nesterov <[email protected]>

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.

---
 kernel/timer.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

index b9cc28271646..e74685309b14 100644
@@ -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

From: "Paul E. McKenney" <[email protected]>

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.

---
 kernel/timer.c | 18 ++++++++++++++++++
 1 file changed, 18 insertions(+)

index 2245b7374c3d..eff9052001e1 100644
@@ -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

From: "Paul E. McKenney" <[email protected]>

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.

---
 kernel/timer.c | 1 +
 1 file changed, 1 insertion(+)

index 1e53acb33361..b9cc28271646 100644
@@ -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

For all five patches in v3:

They seem like perfectly fine bandaids ;-)

The whole series looks fine to me,

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,

-- Steve