Skip to contentSkip to conversation

timer: Reduce timers softirq v2

PATCH In review Frederic Weisbecker 4 participants 17 messages Jul 7, 2020 – Jul 17, 2020 High-resolution timers, timer wheel, clockevents

lore
Share & tools
lore

Frederic Weisbecker

author maintainer
#0 lore raw

cover timer: Reduce timers softirq v2

Hi,

No huge change here, just addressed reviews and fixed warnings:

* Reposted patch 1 separately with appropriate "Fixes:" tag and stable Cc'ed:
https://lore.kernel.org/lkml/[email protected]/

* Fix missing initialization of next_expiry in 4/9 (thanks Juri)

* Dropped "timer: Simplify LVL_START() and calc_index()" and added comments to explain current layout instead in 2/9 (thanks Thomas)

* Rewrote changelog of 9/9 (Thanks Thomas)

git://git.kernel.org/pub/scm/linux/kernel/git/frederic/linux-dynticks.git
timers/softirq-v2

HEAD: 5545d80b7b9bd69ede1c17fda194ac6620e7063f

Thanks,
Frederic
---

Frederic Weisbecker (9):
timer: Move trigger_dyntick_cpu() to enqueue_timer()
timer: Add comments about calc_index() ceiling work
timer: Optimize _next_timer_interrupt() level iteration
timers: Always keep track of next expiry
timer: Reuse next expiry cache after nohz exit
timer: Expand clk forward logic beyond nohz
timer: Spare timer softirq until next expiry
timer: Remove must_forward_clk
timer: Lower base clock forwarding threshold

 kernel/time/timer.c | 169 ++++++++++++++++++----------------------------------
 1 file changed, 58 insertions(+), 111 deletions(-)
author maintainer
#1 lore raw

PATCH 1/9 timer: Move trigger_dyntick_cpu() to enqueue_timer()

Consolidate the code by calling trigger_dyntick_cpu() from enqueue_timer() instead of calling it from all its callers.

Cc Peter Zijlstra <[email protected]>
Cc Anna-Maria Gleixner <[email protected]>
Cc Juri Lelli <[email protected]>
---
 kernel/time/timer.c | 46 +++++++++++++++++++--------------------------
 1 file changed, 19 insertions(+), 27 deletions(-)
kernel/time/timer.c +19 -27
index 9a838d38dbe6..4c977df3610b 100644
@@ -529,29 +529,6 @@ static int calc_wheel_index(unsigned long expires, unsigned long clk)
 	return idx;
 }
 
-/*
- * Enqueue the timer into the hash bucket, mark it pending in
- * the bitmap and store the index in the timer flags.
- */
-static void enqueue_timer(struct timer_base *base, struct timer_list *timer,
-			  unsigned int idx)
-{
-	hlist_add_head(&timer->entry, base->vectors + idx);
-	__set_bit(idx, base->pending_map);
-	timer_set_idx(timer, idx);
-
-	trace_timer_start(timer, timer->expires, timer->flags);
-}
-
-static void
-__internal_add_timer(struct timer_base *base, struct timer_list *timer)
-{
-	unsigned int idx;
-
-	idx = calc_wheel_index(timer->expires, base->clk);
-	enqueue_timer(base, timer, idx);
-}
-
 static void
 trigger_dyntick_cpu(struct timer_base *base, struct timer_list *timer)
 {
@@ -596,13 +573,29 @@ trigger_dyntick_cpu(struct timer_base *base, struct timer_list *timer)
 	wake_up_nohz_cpu(base->cpu);
 }
 
-static void
-internal_add_timer(struct timer_base *base, struct timer_list *timer)
+/*
+ * Enqueue the timer into the hash bucket, mark it pending in
+ * the bitmap and store the index in the timer flags.
+ */
+static void enqueue_timer(struct timer_base *base, struct timer_list *timer,
+			  unsigned int idx)
 {
-	__internal_add_timer(base, timer);
+	hlist_add_head(&timer->entry, base->vectors + idx);
+	__set_bit(idx, base->pending_map);
+	timer_set_idx(timer, idx);
+
+	trace_timer_start(timer, timer->expires, timer->flags);
 	trigger_dyntick_cpu(base, timer);
 }
 
+static void internal_add_timer(struct timer_base *base, struct timer_list *timer)
+{
+	unsigned int idx;
+
+	idx = calc_wheel_index(timer->expires, base->clk);
+	enqueue_timer(base, timer, idx);
+}
+
 #ifdef CONFIG_DEBUG_OBJECTS_TIMERS
 
 static struct debug_obj_descr timer_debug_descr;
@@ -1059,7 +1052,6 @@ __mod_timer(struct timer_list *timer, unsigned long expires, unsigned int option
 	 */
 	if (idx != UINT_MAX && clk == base->clk) {
 		enqueue_timer(base, timer, idx);
-		trigger_dyntick_cpu(base, timer);
 	} else {
 		internal_add_timer(base, timer);
 	}
Signature · 1 line
2.26.2
#2 lore raw

Re: [PATCH 1/9] timer: Move trigger_dyntick_cpu() to enqueue_timer()

Hi Frederic,

Quoted 2 lines · Frederic Weisbecker

Consolidate the code by calling trigger_dyntick_cpu() from enqueue_timer() instead of calling it from all its callers.

Looks good, but maybe you could also update the comments in the code (see remarks below)?

Quoted 13 lines
Cc Peter Zijlstra <[email protected]>
Cc Anna-Maria Gleixner <[email protected]>
Cc Juri Lelli <[email protected]>
---
 kernel/time/timer.c | 46 +++++++++++++++++++--------------------------
 1 file changed, 19 insertions(+), 27 deletions(-)
kernel/time/timer.c +0 -0
index 9a838d38dbe6..4c977df3610b 100644

kernel/time/timer.c trigger_dyntick_cpu(struct timer_base *base, struct timer_list *timer) · line 579

Quoted 9 lines
kernel/time/timer.c +4 -2
@@ -596,13 +573,29 @@ trigger_dyntick_cpu(struct timer_base *base, struct timer_list *timer)
 	wake_up_nohz_cpu(base->cpu);
 }
 
-static void
-internal_add_timer(struct timer_base *base, struct timer_list *timer)
+/*
+ * Enqueue the timer into the hash bucket, mark it pending in
+ * the bitmap and store the index in the timer flags.
+ */

enqueue_timer() also calls trigger_dyntick_cpu().

Quoted 24 lines
kernel/time/timer.c +15 -1
+static void enqueue_timer(struct timer_base *base, struct timer_list *timer,
+			  unsigned int idx)
 {
-	__internal_add_timer(base, timer);
+	hlist_add_head(&timer->entry, base->vectors + idx);
+	__set_bit(idx, base->pending_map);
+	timer_set_idx(timer, idx);
+
+	trace_timer_start(timer, timer->expires, timer->flags);
 	trigger_dyntick_cpu(base, timer);
 }
 
+static void internal_add_timer(struct timer_base *base, struct timer_list *timer)
+{
+	unsigned int idx;
+
+	idx = calc_wheel_index(timer->expires, base->clk);
+	enqueue_timer(base, timer, idx);
+}
+
 #ifdef CONFIG_DEBUG_OBJECTS_TIMERS
 
 static struct debug_obj_descr timer_debug_descr;

kernel/time/timer.c __mod_timer(struct timer_list *timer, unsigned long expires, unsigned int option · line 1052

Quoted 1 line
kernel/time/timer.c +0 -0
@@ -1059,7 +1052,6 @@ __mod_timer(struct timer_list *timer, unsigned long expires, unsigned int option
 	 */

The comment above still mentions that trigger_dyntick_cpu() is called which is now part of enqueue_timer(). Might be a little confusing.

kernel/time/timer.c __mod_timer(struct timer_list *timer, unsigned long expires, unsigned int option · line 1057

Quoted 6 lines
kernel/time/timer.c +0 -1
 	if (idx != UINT_MAX && clk == base->clk) {
 		enqueue_timer(base, timer, idx);
-		trigger_dyntick_cpu(base, timer);
 	} else {
 		internal_add_timer(base, timer);
 	}

Thanks,

Anna-Maria

author maintainer
#3 lore raw

Re: [PATCH 1/9] timer: Move trigger_dyntick_cpu() to enqueue_timer()

Quoted 9 lines · Anna-Maria Behnsen

Hi Frederic,

Quoted 2 lines · Frederic Weisbecker

Consolidate the code by calling trigger_dyntick_cpu() from enqueue_timer() instead of calling it from all its callers.

Looks good, but maybe you could also update the comments in the code (see remarks below)?

Ok, fixing that, thanks!

author maintainer
#4 lore raw

PATCH 2/9 timer: Add comments about calc_index() ceiling work

In reply to Frederic Weisbecker

calc_index() adds 1 unit of the level granularity to the expiry passed in parameter to ensure that the timer doesn't expire too early. Add a comment to explain that and the resulting layout in the wheel.

Cc Peter Zijlstra <[email protected]>
Cc Anna-Maria Gleixner <[email protected]>
Cc Juri Lelli <[email protected]>
---
 kernel/time/timer.c | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)
kernel/time/timer.c +9 -1
index 4c977df3610b..ae1259f67486 100644
@@ -156,7 +156,8 @@ EXPORT_SYMBOL(jiffies_64);
 
 /*
  * The time start value for each level to select the bucket at enqueue
- * time.
+ * time. We start from the last possible delta of the previous level
+ * so that we can later add an extra LVL_GRAN(n) to n (see calc_index()).
  */
 #define LVL_START(n)	((LVL_SIZE - 1) << (((n) - 1) * LVL_CLK_SHIFT))
 
@@ -489,6 +490,13 @@ static inline void timer_set_idx(struct timer_list *timer, unsigned int idx)
  */
 static inline unsigned calc_index(unsigned expires, unsigned lvl)
 {
+	/*
+	 * Time may have past since the clock last reached an index of
+	 * this @lvl. And that time, below LVL_GRAN(@lvl), is going to
+	 * be substracted from the delta until we reach @expires. To
+	 * fix that we must add one level granularity unit to make sure
+	 * we rather expire late than early. Prefer ceil over floor.
+	 */
 	expires = (expires + LVL_GRAN(lvl)) >> LVL_SHIFT(lvl);
 	return LVL_OFFS(lvl) + (expires & LVL_MASK);
 }
Signature · 1 line
2.26.2
#5 lore raw

Re: [PATCH 2/9] timer: Add comments about calc_index() ceiling work

kernel/time/timer.c static inline void timer_set_idx(struct timer_list *timer, unsigned int idx) · line 498

Quoted 8 lines · Frederic Weisbecker

static inline unsigned calc_index(unsigned expires, unsigned lvl) {

kernel/time/timer.c +6 -0
+	/*
+	 * Time may have past since the clock last reached an index of
+	 * this @lvl. And that time, below LVL_GRAN(@lvl), is going to
+	 * be substracted from the delta until we reach @expires. To
+	 * fix that we must add one level granularity unit to make sure
+	 * we rather expire late than early. Prefer ceil over floor.

This comment confuses the hell out of me.

/*
* The timer wheel has to guarantee that a timer does not fire
* early. Early expiry can happen due to:
* - Timer is armed at the edge of a tick
* - Truncation of the expiry time in the outer wheel levels *
* Round up with level granularity to prevent this. */

Hmm?

Thanks,

tglx

author maintainer
#6 lore raw

Re: [PATCH 2/9] timer: Add comments about calc_index() ceiling work

Quoted 11 lines · Thomas Gleixner

kernel/time/timer.c static inline void timer_set_idx(struct timer_list *timer, unsigned int idx) · line 498

Quoted 8 lines · Frederic Weisbecker

static inline unsigned calc_index(unsigned expires, unsigned lvl) {

kernel/time/timer.c +6 -0
+	/*
+	 * Time may have past since the clock last reached an index of
+	 * this @lvl. And that time, below LVL_GRAN(@lvl), is going to
+	 * be substracted from the delta until we reach @expires. To
+	 * fix that we must add one level granularity unit to make sure
+	 * we rather expire late than early. Prefer ceil over floor.

This comment confuses the hell out of me.

Me too...

Quoted 11 lines

/*
* The timer wheel has to guarantee that a timer does not fire
* early. Early expiry can happen due to:
* - Timer is armed at the edge of a tick
* - Truncation of the expiry time in the outer wheel levels *
* Round up with level granularity to prevent this. */

Hmm?

That's relieving, I'm updating the patch.

Thanks!

author maintainer
#7 lore raw

PATCH 3/9 timer: Optimize _next_timer_interrupt() level iteration

In reply to Frederic Weisbecker

If a level has a timer that expires before we reach the next level, there is no need to iterate further.

The next level is reached when the 3 lower bits of the current level are cleared. If the next event happens before/during that, the next levels won't give us an earlier expiration.

Cc Peter Zijlstra <[email protected]>
Cc Anna-Maria Gleixner <[email protected]>
Cc Juri Lelli <[email protected]>
---
 kernel/time/timer.c | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)
kernel/time/timer.c +9 -1
index ae1259f67486..acf7cb8c09f8 100644
@@ -1523,6 +1523,7 @@ static unsigned long __next_timer_interrupt(struct timer_base *base)
 	clk = base->clk;
 	for (lvl = 0; lvl < LVL_DEPTH; lvl++, offset += LVL_SIZE) {
 		int pos = next_pending_bucket(base, offset, clk & LVL_MASK);
+		unsigned long lvl_clk = clk & LVL_CLK_MASK;
 
 		if (pos >= 0) {
 			unsigned long tmp = clk + (unsigned long) pos;
@@ -1530,6 +1531,13 @@ static unsigned long __next_timer_interrupt(struct timer_base *base)
 			tmp <<= LVL_SHIFT(lvl);
 			if (time_before(tmp, next))
 				next = tmp;
+
+			/*
+			 * If the next expiration happens before we reach
+			 * the next level, no need to check further.
+			 */
+			if (pos <= ((LVL_CLK_DIV - lvl_clk) & LVL_CLK_MASK))
+				break;
 		}
 		/*
 		 * Clock for the next level. If the current level clock lower
@@ -1567,7 +1575,7 @@ static unsigned long __next_timer_interrupt(struct timer_base *base)
 		 * So the simple check whether the lower bits of the current
 		 * level are 0 or not is sufficient for all cases.
 		 */
-		adj = clk & LVL_CLK_MASK ? 1 : 0;
+		adj = lvl_clk ? 1 : 0;
 		clk >>= LVL_CLK_SHIFT;
 		clk += adj;
 	}
Signature · 1 line
2.26.2
author maintainer
#8 lore raw

PATCH 4/9 timers: Always keep track of next expiry

In reply to Frederic Weisbecker

So far next expiry was only tracked while the CPU was in nohz_idle mode in order to cope with missing ticks that can't increment the base->clk periodically anymore.

We are going to expand that logic beyond nohz in order to spare timers softirqs so do it unconditionally.

Cc Peter Zijlstra <[email protected]>
Cc Anna-Maria Gleixner <[email protected]>
Cc Juri Lelli <[email protected]>
---
 kernel/time/timer.c | 36 +++++++++++++++++++-----------------
 1 file changed, 19 insertions(+), 17 deletions(-)
kernel/time/timer.c +19 -17
index acf7cb8c09f8..8a4138e47aa4 100644
@@ -558,8 +558,22 @@ trigger_dyntick_cpu(struct timer_base *base, struct timer_list *timer)
 	 * timer is not deferrable. If the other CPU is on the way to idle
 	 * then it can't set base->is_idle as we hold the base lock:
 	 */
-	if (!base->is_idle)
-		return;
+	if (base->is_idle)
+		wake_up_nohz_cpu(base->cpu);
+}
+
+/*
+ * Enqueue the timer into the hash bucket, mark it pending in
+ * the bitmap and store the index in the timer flags.
+ */
+static void enqueue_timer(struct timer_base *base, struct timer_list *timer,
+			  unsigned int idx)
+{
+	hlist_add_head(&timer->entry, base->vectors + idx);
+	__set_bit(idx, base->pending_map);
+	timer_set_idx(timer, idx);
+
+	trace_timer_start(timer, timer->expires, timer->flags);
 
 	/* Check whether this is the new first expiring timer: */
 	if (time_after_eq(timer->expires, base->next_expiry))
@@ -578,21 +592,7 @@ trigger_dyntick_cpu(struct timer_base *base, struct timer_list *timer)
 	} else {
 		base->next_expiry = timer->expires;
 	}
-	wake_up_nohz_cpu(base->cpu);
-}
 
-/*
- * Enqueue the timer into the hash bucket, mark it pending in
- * the bitmap and store the index in the timer flags.
- */
-static void enqueue_timer(struct timer_base *base, struct timer_list *timer,
-			  unsigned int idx)
-{
-	hlist_add_head(&timer->entry, base->vectors + idx);
-	__set_bit(idx, base->pending_map);
-	timer_set_idx(timer, idx);
-
-	trace_timer_start(timer, timer->expires, timer->flags);
 	trigger_dyntick_cpu(base, timer);
 }
 
@@ -1490,7 +1490,6 @@ static int __collect_expired_timers(struct timer_base *base,
 	return levels;
 }
 
-#ifdef CONFIG_NO_HZ_COMMON
 /*
  * Find the next pending bucket of a level. Search from level start (@offset)
  * + @clk upwards and if nothing there, search from start of the level
@@ -1582,6 +1581,7 @@ static unsigned long __next_timer_interrupt(struct timer_base *base)
 	return next;
 }
 
+#ifdef CONFIG_NO_HZ_COMMON
 /*
  * Check, if the next hrtimer event is before the next timer wheel
  * event:
@@ -1787,6 +1787,7 @@ static inline void __run_timers(struct timer_base *base)
 
 		levels = collect_expired_timers(base, heads);
 		base->clk++;
+		base->next_expiry = __next_timer_interrupt(base);
 
 		while (levels--)
 			expire_timers(base, heads + levels);
@@ -2039,6 +2040,7 @@ static void __init init_timer_cpu(int cpu)
 		base->cpu = cpu;
 		raw_spin_lock_init(&base->lock);
 		base->clk = jiffies;
+		base->next_expiry = base->clk + NEXT_TIMER_MAX_DELTA;
 		timer_base_init_expiry_lock(base);
 	}
 }
Signature · 1 line
2.26.2
#9 lore raw

Re: [PATCH 4/9] timers: Always keep track of next expiry

Hi Frederic,

Quoted 56 lines · Frederic Weisbecker

So far next expiry was only tracked while the CPU was in nohz_idle mode in order to cope with missing ticks that can't increment the base->clk periodically anymore.

We are going to expand that logic beyond nohz in order to spare timers softirqs so do it unconditionally.

Cc Peter Zijlstra <[email protected]>
Cc Anna-Maria Gleixner <[email protected]>
Cc Juri Lelli <[email protected]>
---
 kernel/time/timer.c | 36 +++++++++++++++++++-----------------
 1 file changed, 19 insertions(+), 17 deletions(-)
kernel/time/timer.c +16 -9
index acf7cb8c09f8..8a4138e47aa4 100644
@@ -558,8 +558,22 @@ trigger_dyntick_cpu(struct timer_base *base, struct timer_list *timer)
 	 * timer is not deferrable. If the other CPU is on the way to idle
 	 * then it can't set base->is_idle as we hold the base lock:
 	 */
-	if (!base->is_idle)
-		return;
+	if (base->is_idle)
+		wake_up_nohz_cpu(base->cpu);
+}
+
+/*
+ * Enqueue the timer into the hash bucket, mark it pending in
+ * the bitmap and store the index in the timer flags.
+ */
+static void enqueue_timer(struct timer_base *base, struct timer_list *timer,
+			  unsigned int idx)
+{
+	hlist_add_head(&timer->entry, base->vectors + idx);
+	__set_bit(idx, base->pending_map);
+	timer_set_idx(timer, idx);
+
+	trace_timer_start(timer, timer->expires, timer->flags);
 
 	/* Check whether this is the new first expiring timer: */
 	if (time_after_eq(timer->expires, base->next_expiry))
@@ -578,21 +592,7 @@ trigger_dyntick_cpu(struct timer_base *base, struct timer_list *timer)
 	} else {
 		base->next_expiry = timer->expires;
 	}
-	wake_up_nohz_cpu(base->cpu);
-}
 
-/*
- * Enqueue the timer into the hash bucket, mark it pending in
- * the bitmap and store the index in the timer flags.
- */
-static void enqueue_timer(struct timer_base *base, struct timer_list *timer,

kernel/time/timer.c trigger_dyntick_cpu(struct timer_base *base, struct timer_list *timer) · line 598

Quoted 10 lines
kernel/time/timer.c +0 -7
-			  unsigned int idx)
-{
-	hlist_add_head(&timer->entry, base->vectors + idx);
-	__set_bit(idx, base->pending_map);
-	timer_set_idx(timer, idx);
-
-	trace_timer_start(timer, timer->expires, timer->flags);
 	trigger_dyntick_cpu(base, timer);
 }
 

Could you please split those two hunks which do only a restructuring into a separate patch?

Thanks,

Anna-Maria

author maintainer
#10 lore raw

Re: [PATCH 4/9] timers: Always keep track of next expiry

Quoted 65 lines · Anna-Maria Behnsen

Hi Frederic,

Quoted 61 lines · Frederic Weisbecker

So far next expiry was only tracked while the CPU was in nohz_idle mode in order to cope with missing ticks that can't increment the base->clk periodically anymore.

We are going to expand that logic beyond nohz in order to spare timers softirqs so do it unconditionally.

Cc Peter Zijlstra <[email protected]>
Cc Anna-Maria Gleixner <[email protected]>
Cc Juri Lelli <[email protected]>
---
 kernel/time/timer.c | 36 +++++++++++++++++++-----------------
 1 file changed, 19 insertions(+), 17 deletions(-)
kernel/time/timer.c +16 -14
index acf7cb8c09f8..8a4138e47aa4 100644
@@ -558,8 +558,22 @@ trigger_dyntick_cpu(struct timer_base *base, struct timer_list *timer)
 	 * timer is not deferrable. If the other CPU is on the way to idle
 	 * then it can't set base->is_idle as we hold the base lock:
 	 */
-	if (!base->is_idle)
-		return;
+	if (base->is_idle)
+		wake_up_nohz_cpu(base->cpu);
+}
+
+/*
+ * Enqueue the timer into the hash bucket, mark it pending in
+ * the bitmap and store the index in the timer flags.
+ */
+static void enqueue_timer(struct timer_base *base, struct timer_list *timer,
+			  unsigned int idx)
+{
+	hlist_add_head(&timer->entry, base->vectors + idx);
+	__set_bit(idx, base->pending_map);
+	timer_set_idx(timer, idx);
+
+	trace_timer_start(timer, timer->expires, timer->flags);
 
 	/* Check whether this is the new first expiring timer: */
 	if (time_after_eq(timer->expires, base->next_expiry))
@@ -578,21 +592,7 @@ trigger_dyntick_cpu(struct timer_base *base, struct timer_list *timer)
 	} else {
 		base->next_expiry = timer->expires;
 	}
-	wake_up_nohz_cpu(base->cpu);
-}
 
-/*
- * Enqueue the timer into the hash bucket, mark it pending in
- * the bitmap and store the index in the timer flags.
- */
-static void enqueue_timer(struct timer_base *base, struct timer_list *timer,
-			  unsigned int idx)
-{
-	hlist_add_head(&timer->entry, base->vectors + idx);
-	__set_bit(idx, base->pending_map);
-	timer_set_idx(timer, idx);
Quoted 8 lines

kernel/time/timer.c trigger_dyntick_cpu(struct timer_base *base, struct timer_list *timer) · line 598

Quoted 5 lines
kernel/time/timer.c +0 -2
-
-	trace_timer_start(timer, timer->expires, timer->flags);
 	trigger_dyntick_cpu(base, timer);
 }
 

Could you please split those two hunks which do only a restructuring into a separate patch?

The problem is that those hunks are not only a restructuring but they also change the way we update next_expiry, since we do it outside idle context. And that update won't make sense without the proper initialization of next_expiry that comes later in the patch.

Thanks.

author maintainer
#11 lore raw

PATCH 5/9 timer: Reuse next expiry cache after nohz exit

In reply to Frederic Weisbecker

Now that we track the next expiry unconditionally when a timer is added, we can reuse that information on a tick firing after exiting nohz.

Cc Peter Zijlstra <[email protected]>
Cc Anna-Maria Gleixner <[email protected]>
Cc Juri Lelli <[email protected]>
---
 kernel/time/timer.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)
kernel/time/timer.c +2 -4
index 8a4138e47aa4..501d36ef0b75 100644
@@ -1705,13 +1705,11 @@ static int collect_expired_timers(struct timer_base *base,
 	 * the next expiring timer.
 	 */
 	if ((long)(now - base->clk) > 2) {
-		unsigned long next = __next_timer_interrupt(base);
-
 		/*
 		 * If the next timer is ahead of time forward to current
 		 * jiffies, otherwise forward to the next expiry time:
 		 */
-		if (time_after(next, now)) {
+		if (time_after(base->next_expiry, now)) {
 			/*
 			 * The call site will increment base->clk and then
 			 * terminate the expiry loop immediately.
@@ -1719,7 +1717,7 @@ static int collect_expired_timers(struct timer_base *base,
 			base->clk = now;
 			return 0;
 		}
-		base->clk = next;
+		base->clk = base->next_expiry;
 	}
 	return __collect_expired_timers(base, heads);
 }
Signature · 1 line
2.26.2
author maintainer
#12 lore raw

PATCH 6/9 timer: Expand clk forward logic beyond nohz

In reply to Frederic Weisbecker

As for next_expiry, we want to expand base->clk catch up logic beyond nohz in order to avoid triggering useless softirqs.

If we want to fire softirqs only to expire pending timers, periodic base->clk increments must be skippable for random amounts of time. Therefore we must prepare to catch-up with missing updates whenever we need an up-to-date base clock.

Cc Peter Zijlstra <[email protected]>
Cc Anna-Maria Gleixner <[email protected]>
Cc Juri Lelli <[email protected]>
---
 kernel/time/timer.c | 26 ++++----------------------
 1 file changed, 4 insertions(+), 22 deletions(-)
kernel/time/timer.c +4 -22
index 501d36ef0b75..ffa2c956d968 100644
@@ -885,19 +885,12 @@ get_target_base(struct timer_base *base, unsigned tflags)
 
 static inline void forward_timer_base(struct timer_base *base)
 {
-#ifdef CONFIG_NO_HZ_COMMON
 	unsigned long jnow;
 
-	/*
-	 * We only forward the base when we are idle or have just come out of
-	 * idle (must_forward_clk logic), and have a delta between base clock
-	 * and jiffies. In the common case, run_timers will take care of it.
-	 */
-	if (likely(!base->must_forward_clk))
+	if (!base->must_forward_clk)
 		return;
 
 	jnow = READ_ONCE(jiffies);
-	base->must_forward_clk = base->is_idle;
 	if ((long)(jnow - base->clk) < 2)
 		return;
 
@@ -912,7 +905,6 @@ static inline void forward_timer_base(struct timer_base *base)
 			return;
 		base->clk = base->next_expiry;
 	}
-#endif
 }
 
 
@@ -1666,10 +1658,8 @@ u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
 		 * logic is only maintained for the BASE_STD base, deferrable
 		 * timers may still see large granularity skew (by design).
 		 */
-		if ((expires - basem) > TICK_NSEC) {
-			base->must_forward_clk = true;
+		if ((expires - basem) > TICK_NSEC)
 			base->is_idle = true;
-		}
 	}
 	raw_spin_unlock(&base->lock);
 
@@ -1768,16 +1758,7 @@ static inline void __run_timers(struct timer_base *base)
 	/*
 	 * timer_base::must_forward_clk must be cleared before running
 	 * timers so that any timer functions that call mod_timer() will
-	 * not try to forward the base. Idle tracking / clock forwarding
-	 * logic is only used with BASE_STD timers.
-	 *
-	 * The must_forward_clk flag is cleared unconditionally also for
-	 * the deferrable base. The deferrable base is not affected by idle
-	 * tracking and never forwarded, so clearing the flag is a NOOP.
-	 *
-	 * The fact that the deferrable base is never forwarded can cause
-	 * large variations in granularity for deferrable timers, but they
-	 * can be deferred for long periods due to idle anyway.
+	 * not try to forward the base.
 	 */
 	base->must_forward_clk = false;
 
@@ -1790,6 +1771,7 @@ static inline void __run_timers(struct timer_base *base)
 		while (levels--)
 			expire_timers(base, heads + levels);
 	}
+	base->must_forward_clk = true;
 	raw_spin_unlock_irq(&base->lock);
 	timer_base_unlock_expiry(base);
 }
Signature · 1 line
2.26.2
author maintainer
#13 lore raw

PATCH 7/9 timer: Spare timer softirq until next expiry

In reply to Frederic Weisbecker

Now that the core timer infrastructure doesn't depend anymore on periodic base->clk increments, even when the CPU is not in NO_HZ mode, we can delay the timer softirqs until we have actual timers to expire.

Some spurious softirqs can still remain since base->next_expiry doesn't keep track of canceled timers but we are still way ahead of the unconditional periodic softirqs (~15 times less of them with 1000 Hz and ~5 times less with 100 Hz).

Cc Peter Zijlstra <[email protected]>
Cc Anna-Maria Gleixner <[email protected]>
Cc Juri Lelli <[email protected]>
---
 kernel/time/timer.c | 49 ++++++++-------------------------------------
 1 file changed, 8 insertions(+), 41 deletions(-)
kernel/time/timer.c +8 -41
index ffa2c956d968..cbc5ac7f772d 100644
@@ -1457,10 +1457,10 @@ static void expire_timers(struct timer_base *base, struct hlist_head *head)
 	}
 }
 
-static int __collect_expired_timers(struct timer_base *base,
-				    struct hlist_head *heads)
+static int collect_expired_timers(struct timer_base *base,
+				  struct hlist_head *heads)
 {
-	unsigned long clk = base->clk;
+	unsigned long clk = base->clk = base->next_expiry;
 	struct hlist_head *vec;
 	int i, levels = 0;
 	unsigned int idx;
@@ -1683,40 +1683,6 @@ void timer_clear_idle(void)
 	 */
 	base->is_idle = false;
 }
-
-static int collect_expired_timers(struct timer_base *base,
-				  struct hlist_head *heads)
-{
-	unsigned long now = READ_ONCE(jiffies);
-
-	/*
-	 * NOHZ optimization. After a long idle sleep we need to forward the
-	 * base to current jiffies. Avoid a loop by searching the bitfield for
-	 * the next expiring timer.
-	 */
-	if ((long)(now - base->clk) > 2) {
-		/*
-		 * If the next timer is ahead of time forward to current
-		 * jiffies, otherwise forward to the next expiry time:
-		 */
-		if (time_after(base->next_expiry, now)) {
-			/*
-			 * The call site will increment base->clk and then
-			 * terminate the expiry loop immediately.
-			 */
-			base->clk = now;
-			return 0;
-		}
-		base->clk = base->next_expiry;
-	}
-	return __collect_expired_timers(base, heads);
-}
-#else
-static inline int collect_expired_timers(struct timer_base *base,
-					 struct hlist_head *heads)
-{
-	return __collect_expired_timers(base, heads);
-}
 #endif
 
 /*
@@ -1749,7 +1715,7 @@ static inline void __run_timers(struct timer_base *base)
 	struct hlist_head heads[LVL_DEPTH];
 	int levels;
 
-	if (!time_after_eq(jiffies, base->clk))
+	if (time_before(jiffies, base->next_expiry))
 		return;
 
 	timer_base_lock_expiry(base);
@@ -1762,7 +1728,8 @@ static inline void __run_timers(struct timer_base *base)
 	 */
 	base->must_forward_clk = false;
 
-	while (time_after_eq(jiffies, base->clk)) {
+	while (time_after_eq(jiffies, base->clk) &&
+	       time_after_eq(jiffies, base->next_expiry)) {
 
 		levels = collect_expired_timers(base, heads);
 		base->clk++;
@@ -1797,12 +1764,12 @@ void run_local_timers(void)
 
 	hrtimer_run_queues();
 	/* Raise the softirq only if required. */
-	if (time_before(jiffies, base->clk)) {
+	if (time_before(jiffies, base->next_expiry)) {
 		if (!IS_ENABLED(CONFIG_NO_HZ_COMMON))
 			return;
 		/* CPU is awake, so check the deferrable base. */
 		base++;
-		if (time_before(jiffies, base->clk))
+		if (time_before(jiffies, base->next_expiry))
 			return;
 	}
 	raise_softirq(TIMER_SOFTIRQ);
Signature · 1 line
2.26.2
author maintainer
#14 lore raw

PATCH 8/9 timer: Remove must_forward_clk

In reply to Frederic Weisbecker

There is no reason to keep this guard around. The code makes sure that base->clk remains sane and won't be forwarded beyond jiffies nor set backward.

Cc Peter Zijlstra <[email protected]>
Cc Anna-Maria Gleixner <[email protected]>
Cc Juri Lelli <[email protected]>
---
 kernel/time/timer.c | 22 ++++++----------------
 1 file changed, 6 insertions(+), 16 deletions(-)
kernel/time/timer.c +6 -16
index cbc5ac7f772d..60126d5c79e1 100644
@@ -205,7 +205,6 @@ struct timer_base {
 	unsigned long		next_expiry;
 	unsigned int		cpu;
 	bool			is_idle;
-	bool			must_forward_clk;
 	DECLARE_BITMAP(pending_map, WHEEL_SIZE);
 	struct hlist_head	vectors[WHEEL_SIZE];
 } ____cacheline_aligned;
@@ -885,12 +884,13 @@ get_target_base(struct timer_base *base, unsigned tflags)
 
 static inline void forward_timer_base(struct timer_base *base)
 {
-	unsigned long jnow;
+	unsigned long jnow = READ_ONCE(jiffies);
 
-	if (!base->must_forward_clk)
-		return;
-
-	jnow = READ_ONCE(jiffies);
+	/*
+	 * No need to forward if we are close enough below jiffies.
+	 * Also while executing timers, base->clk is 1 offset ahead
+	 * of jiffies to avoid endless requeuing to current jffies.
+	 */
 	if ((long)(jnow - base->clk) < 2)
 		return;
 
@@ -1721,16 +1721,8 @@ static inline void __run_timers(struct timer_base *base)
 	timer_base_lock_expiry(base);
 	raw_spin_lock_irq(&base->lock);
 
-	/*
-	 * timer_base::must_forward_clk must be cleared before running
-	 * timers so that any timer functions that call mod_timer() will
-	 * not try to forward the base.
-	 */
-	base->must_forward_clk = false;
-
 	while (time_after_eq(jiffies, base->clk) &&
 	       time_after_eq(jiffies, base->next_expiry)) {
-
 		levels = collect_expired_timers(base, heads);
 		base->clk++;
 		base->next_expiry = __next_timer_interrupt(base);
@@ -1738,7 +1730,6 @@ static inline void __run_timers(struct timer_base *base)
 		while (levels--)
 			expire_timers(base, heads + levels);
 	}
-	base->must_forward_clk = true;
 	raw_spin_unlock_irq(&base->lock);
 	timer_base_unlock_expiry(base);
 }
@@ -1934,7 +1925,6 @@ int timers_prepare_cpu(unsigned int cpu)
 		base->clk = jiffies;
 		base->next_expiry = base->clk + NEXT_TIMER_MAX_DELTA;
 		base->is_idle = false;
-		base->must_forward_clk = true;
 	}
 	return 0;
 }
Signature · 1 line
2.26.2
author maintainer
#15 lore raw

PATCH 9/9 timer: Lower base clock forwarding threshold

In reply to Frederic Weisbecker

There is nothing that prevents us from forwarding the base clock if it's one jiffy off. This reason for this arbitrary limit is historical and doesn't seem to stand anymore.

Cc Peter Zijlstra <[email protected]>
Cc Anna-Maria Gleixner <[email protected]>
Cc Juri Lelli <[email protected]>
---
 kernel/time/timer.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/time/timer.c +1 -1
index 60126d5c79e1..814eaf42a8b5 100644
@@ -891,7 +891,7 @@ static inline void forward_timer_base(struct timer_base *base)
 	 * Also while executing timers, base->clk is 1 offset ahead
 	 * of jiffies to avoid endless requeuing to current jffies.
 	 */
-	if ((long)(jnow - base->clk) < 2)
+	if ((long)(jnow - base->clk) < 1)
 		return;
 
 	/*
Signature · 1 line
2.26.2
Tested-by on the v1 series
#16 lore raw
In reply to Frederic Weisbecker

Hi,

Quoted 14 lines · Frederic Weisbecker

Hi,

No huge change here, just addressed reviews and fixed warnings:

* Reposted patch 1 separately with appropriate "Fixes:" tag and stable Cc'ed:
https://lore.kernel.org/lkml/[email protected]/

* Fix missing initialization of next_expiry in 4/9 (thanks Juri)

* Dropped "timer: Simplify LVL_START() and calc_index()" and added comments to explain current layout instead in 2/9 (thanks Thomas)

* Rewrote changelog of 9/9 (Thanks Thomas)

Quoted 8 lines

git://git.kernel.org/pub/scm/linux/kernel/git/frederic/linux-dynticks.git
timers/softirq-v2

HEAD: 5545d80b7b9bd69ede1c17fda194ac6620e7063f

Thanks,
Frederic
---

Testing of this set looks good (even with RT). Feel free to add

to all the patches and to the patch you posted separately (old 01).

Thanks!

Juri