Skip to contentSkip to conversation

do not raise timer softirq unconditionally (spinlockless version)

PATCH In review Marcelo Tosatti 5 participants 18 messages Apr 15, 2019 – Jun 11, 2019 High-resolution timers, timer wheel, clockevents

lore
Share & tools
lore
#0 lore raw

cover do not raise timer softirq unconditionally (spinlockless version)

For isolated CPUs, we'd like to skip awakening ktimersoftd (the switch to and then back from ktimersoftd takes 10us in virtualized environments, in addition to other OS overhead, which exceeds telco requirements for packet forwarding for 5G) from the sched tick.

The patch "timers: do not raise softirq unconditionally" from Thomas attempts to address that by checking, in the sched tick, whether its necessary to raise the timer softirq. Unfortunately, it attempts to grab the tvec base spinlock which generates the issue described in the patch "Revert "timers: do not raise softirq unconditionally"".

tvec_base->lock protects addition of timers to the wheel versus timer interrupt execution.

This patch does not grab the tvec base spinlock from irq context, but rather performs a lockless access to base->pending_map.

It handles the the race between timer addition and timer interrupt execution by unconditionally (in case of isolated CPUs) raising the timer softirq after making sure the updated bitmap is visible on remote CPUs.

This patchset reduces cyclictest latency from 25us to 14us on my testbox.

#4 lore raw

PATCH 2/3 timers: do not raise softirq unconditionally (spinlockless version)

Check base->pending_map locklessly and skip raising timer softirq if empty.

What allows the lockless (and potentially racy against mod_timer) check is that mod_timer will raise another timer softirq after modifying base->pending_map.

---
 kernel/time/timer.c |   18 ++++++++++++++++++
 1 file changed, 18 insertions(+)
kernel/time/timer.c +18 -0
Index: linux-rt-devel/kernel/time/timer.c
===================================================================
@@ -1776,6 +1776,24 @@
 		if (time_before(jiffies, base->clk))
 			return;
 	}
+
+#ifdef CONFIG_PREEMPT_RT_FULL
+/* On RT, irq work runs from softirq */
+	if (irq_work_needs_cpu())
+		goto raise;
+#endif
+	base = this_cpu_ptr(&timer_bases[BASE_STD]);
+	if (!housekeeping_cpu(base->cpu, HK_FLAG_TIMER)) {
+		if (!bitmap_empty(base->pending_map, WHEEL_SIZE))
+			goto raise;
+		base++;
+		if (!bitmap_empty(base->pending_map, WHEEL_SIZE))
+			goto raise;
+
+		return;
+	}
+
+raise:
 	raise_softirq(TIMER_SOFTIRQ);
 }
 
#11 lore raw

PATCH 3/3 timers: condense pending bitmap information

In reply to Marcelo Tosatti

Condense the pending bitmap information in a bool.

Improves cyclictest results by 4us.

---
 kernel/time/timer.c |    9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)
kernel/time/timer.c +7 -2
Index: linux-rt-devel/kernel/time/timer.c
===================================================================
@@ -206,6 +206,7 @@
 	unsigned int		cpu;
 	bool			is_idle;
 	bool			must_forward_clk;
+	bool			pending_map_clear;
 	DECLARE_BITMAP(pending_map, WHEEL_SIZE);
 	struct hlist_head	vectors[WHEEL_SIZE];
 } ____cacheline_aligned;
@@ -538,6 +539,7 @@
 {
 	hlist_add_head(&timer->entry, base->vectors + idx);
 	__set_bit(idx, base->pending_map);
+	base->pending_map_clear = false;
 	timer_set_idx(timer, idx);
 }
 
@@ -1741,6 +1743,9 @@
 		while (levels--)
 			expire_timers(base, heads + levels);
 	}
+	if (!housekeeping_cpu(base->cpu, HK_FLAG_TIMER) &&
+	    bitmap_empty(base->pending_map, WHEEL_SIZE))
+		base->pending_map_clear = true;
 	raw_spin_unlock_irq(&base->lock);
 	wakeup_timer_waiters(base);
 }
@@ -1784,10 +1789,10 @@
 #endif
 	base = this_cpu_ptr(&timer_bases[BASE_STD]);
 	if (!housekeeping_cpu(base->cpu, HK_FLAG_TIMER)) {
-		if (!bitmap_empty(base->pending_map, WHEEL_SIZE))
+		if (!base->pending_map_clear)
 			goto raise;
 		base++;
-		if (!bitmap_empty(base->pending_map, WHEEL_SIZE))
+		if (!base->pending_map_clear)
 			goto raise;
 
 		return;
#1 lore raw

PATCH 1/3 timers: raise timer softirq on __mod_timer/add_timer_on

In reply to Marcelo Tosatti

For isolated CPUs, we'd like to skip awakening ktimersoftd (the switch to and then back from ktimersoftd takes 10us in virtualized environments, in addition to other OS overhead, which exceeds telco requirements for packet forwarding for 5G) from the sched tick.

The patch "timers: do not raise softirq unconditionally" from Thomas attempts to address that by checking, in the sched tick, whether its necessary to raise the timer softirq. Unfortunately, it attempts to grab the tvec base spinlock which generates the issue described in the patch "Revert "timers: do not raise softirq unconditionally"".

tvec_base->lock protects addition of timers to the wheel versus timer interrupt execution.

This patch does not grab the tvec base spinlock from irq context, but rather performs a lockless access to base->pending_map.

It handles the the race between timer addition and timer interrupt execution by unconditionally (in case of isolated CPUs) raising the timer softirq after making sure the updated bitmap is visible on remote CPUs.

This patch reduces cyclictest latency from 25us to 14us on my testbox.

---
 kernel/time/timer.c |   38 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 38 insertions(+)
kernel/time/timer.c +38 -0
Index: linux-rt-devel/kernel/time/timer.c
===================================================================
@@ -41,6 +41,7 @@
 #include <linux/sched/sysctl.h>
 #include <linux/sched/nohz.h>
 #include <linux/sched/debug.h>
+#include <linux/sched/isolation.h>
 #include <linux/slab.h>
 #include <linux/compat.h>
 #include <linux/swait.h>
@@ -907,6 +908,12 @@
 #endif
 }
 
+static DEFINE_PER_CPU(call_single_data_t, raise_timer_csd);
+
+static void raise_timer_softirq(void *arg)
+{
+	raise_softirq(TIMER_SOFTIRQ);
+}
 
 /*
  * We are using hashed locking: Holding per_cpu(timer_bases[x]).lock means
@@ -1056,6 +1063,17 @@
 		internal_add_timer(base, timer);
 	}
 
+	if (!housekeeping_cpu(base->cpu, HK_FLAG_TIMER) &&
+	    !(timer->flags & TIMER_DEFERRABLE)) {
+		call_single_data_t *c;
+
+		c = per_cpu_ptr(&raise_timer_csd, base->cpu);
+
+		/* Make sure bitmap updates are visible on remote CPUs */
+		smp_wmb();
+		smp_call_function_single_async(base->cpu, c);
+	}
+
 out_unlock:
 	raw_spin_unlock_irqrestore(&base->lock, flags);
 
@@ -1175,6 +1193,17 @@
 
 	debug_activate(timer, timer->expires);
 	internal_add_timer(base, timer);
+
+	if (!housekeeping_cpu(base->cpu, HK_FLAG_TIMER) &&
+	    !(timer->flags & TIMER_DEFERRABLE)) {
+		call_single_data_t *c;
+
+		c = per_cpu_ptr(&raise_timer_csd, base->cpu);
+
+		/* Make sure bitmap updates are visible on remote CPUs */
+		smp_wmb();
+		smp_call_function_single_async(base->cpu, c);
+	}
 	raw_spin_unlock_irqrestore(&base->lock, flags);
 }
 EXPORT_SYMBOL_GPL(add_timer_on);
@@ -1970,6 +1999,15 @@
 {
 	int cpu;
 
+	for_each_possible_cpu(cpu) {
+		call_single_data_t *c;
+
+		c = per_cpu_ptr(&raise_timer_csd, cpu);
+		c->func = raise_timer_softirq;
+		c->info = NULL;
+		c->flags = 0;
+	}
+
 	for_each_possible_cpu(cpu)
 		init_timer_cpu(cpu);
 }
#12 lore raw
In reply to Marcelo Tosatti
Quoted 18 lines · Marcelo Tosatti

For isolated CPUs, we'd like to skip awakening ktimersoftd (the switch to and then back from ktimersoftd takes 10us in virtualized environments, in addition to other OS overhead, which exceeds telco requirements for packet forwarding for 5G) from the sched tick.

The patch "timers: do not raise softirq unconditionally" from Thomas attempts to address that by checking, in the sched tick, whether its necessary to raise the timer softirq. Unfortunately, it attempts to grab the tvec base spinlock which generates the issue described in the patch "Revert "timers: do not raise softirq unconditionally"".

tvec_base->lock protects addition of timers to the wheel versus timer interrupt execution.

This patch does not grab the tvec base spinlock from irq context, but rather performs a lockless access to base->pending_map.

Quoted 7 lines

It handles the the race between timer addition and timer interrupt execution by unconditionally (in case of isolated CPUs) raising the timer softirq after making sure the updated bitmap is visible on remote CPUs.

This patchset reduces cyclictest latency from 25us to 14us on my testbox.

Patch against v5.0.5-rt3 branch of linux-rt-devel.

#13 lore raw
In reply to Marcelo Tosatti
Quoted 18 lines · Marcelo Tosatti

For isolated CPUs, we'd like to skip awakening ktimersoftd (the switch to and then back from ktimersoftd takes 10us in virtualized environments, in addition to other OS overhead, which exceeds telco requirements for packet forwarding for 5G) from the sched tick.

The patch "timers: do not raise softirq unconditionally" from Thomas attempts to address that by checking, in the sched tick, whether its necessary to raise the timer softirq. Unfortunately, it attempts to grab the tvec base spinlock which generates the issue described in the patch "Revert "timers: do not raise softirq unconditionally"".

tvec_base->lock protects addition of timers to the wheel versus timer interrupt execution.

This patch does not grab the tvec base spinlock from irq context, but rather performs a lockless access to base->pending_map.

Quoted 9 lines

It handles the the race between timer addition and timer interrupt execution by unconditionally (in case of isolated CPUs) raising the timer softirq after making sure the updated bitmap is visible on remote CPUs.

This patchset reduces cyclictest latency from 25us to 14us on my testbox.

Ping?

#14 lore raw
Quoted 24 lines · Marcelo Tosatti
Quoted 23 lines · Marcelo Tosatti

For isolated CPUs, we'd like to skip awakening ktimersoftd (the switch to and then back from ktimersoftd takes 10us in virtualized environments, in addition to other OS overhead, which exceeds telco requirements for packet forwarding for 5G) from the sched tick.

The patch "timers: do not raise softirq unconditionally" from Thomas attempts to address that by checking, in the sched tick, whether its necessary to raise the timer softirq. Unfortunately, it attempts to grab the tvec base spinlock which generates the issue described in the patch "Revert "timers: do not raise softirq unconditionally"".

tvec_base->lock protects addition of timers to the wheel versus timer interrupt execution.

This patch does not grab the tvec base spinlock from irq context, but rather performs a lockless access to base->pending_map.

It handles the the race between timer addition and timer interrupt execution by unconditionally (in case of isolated CPUs) raising the timer softirq after making sure the updated bitmap is visible on remote CPUs.

Quoted 7 lines
Quoted 4 lines

This patchset reduces cyclictest latency from 25us to 14us on my testbox.

Ping?

Hi Marcelo,

I've been running your patches with lockdep and other debug options and did not find any problem of this kind. Also, I did not find any kind of timing regressions in tests with the PREEMPT RT...

-- Daniel

#15 lore raw
In reply to Marcelo Tosatti
Quoted 10 lines · Marcelo Tosatti
Quoted 7 lines · Marcelo Tosatti

It handles the the race between timer addition and timer interrupt execution by unconditionally (in case of isolated CPUs) raising the timer softirq after making sure the updated bitmap is visible on remote CPUs.

This patchset reduces cyclictest latency from 25us to 14us on my testbox.

Ping?

On my list ....

#16 lore raw
In reply to Marcelo Tosatti

Hi,

I had a look at the queue and have several questions about your implementation.

First of all, I had some troubles to understand your commit messages. So I first had to read the code and then tried to understand the commit messages. It is easier, if it works the other way round.

Quoted 5 lines · Marcelo Tosatti

For isolated CPUs, we'd like to skip awakening ktimersoftd (the switch to and then back from ktimersoftd takes 10us in virtualized environments, in addition to other OS overhead, which exceeds telco requirements for packet forwarding for 5G) from the sched tick.

You would like to prevent raising the timer softirq in general from the sched tick for isolated CPUs? Or you would like to prevent raising the timer softirq if no pending timer is available?

Nevertheless, this change is not PREEMPT_RT specific. It is a NOHZ dependand change. So it would be nice, if the queue is against mainline. But please correct me, if I'm wrong.

[...]

Quoted 3 lines

This patchset reduces cyclictest latency from 25us to 14us on my testbox.

A lot of information is missing: How does your environment looks like for this test, what is your workload,...?

Did you also run other tests?

Thanks,

Anna-Maria

#2 lore raw

Re: [patch 1/3] timers: raise timer softirq on __mod_timer/add_timer_on

In reply to Marcelo Tosatti

On Mon, 15 Apr 2019, Marcelo Tosatti wrote:

[...]

Quoted 5 lines

The patch "timers: do not raise softirq unconditionally" from Thomas attempts to address that by checking, in the sched tick, whether its necessary to raise the timer softirq. Unfortunately, it attempts to grab the tvec base spinlock which generates the issue described in the patch "Revert "timers: do not raise softirq unconditionally"".

Both patches are not available in the version your patch set is based on. Better pointers would be helpful.

Quoted 2 lines

tvec_base->lock protects addition of timers to the wheel versus timer interrupt execution.

The timer_base->lock (formally known as tvec_base->lock), synchronizes all accesses to timer_base and not only addition of timers versus timer interrupt execution. Deletion of timers, getting the next timer interrupt, forwarding the base clock and migration of timers are protected as well by timer_base->lock.

Quoted 2 lines

This patch does not grab the tvec base spinlock from irq context, but rather performs a lockless access to base->pending_map.

I cannot see where this patch performs a lockless access to timer_base->pending_map.

Quoted 4 lines

It handles the the race between timer addition and timer interrupt execution by unconditionally (in case of isolated CPUs) raising the timer softirq after making sure the updated bitmap is visible on remote CPUs.

So after modifying a timer on a non housekeeping timer base, the timer softirq is raised - even if there is no pending timer in the next bucket. Only with this patch, this shouldn't be a problem - but it is an additional raise of timer softirq and an overhead when adding a timer, because the normal timer softirq is raised from sched tick anyway.

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

Index: linux-rt-devel/kernel/time/timer.c
===================================================================

kernel/time/timer.c +4 -0
@@ -1056,6 +1063,17 @@
 		internal_add_timer(base, timer);
 	}
 
+	if (!housekeeping_cpu(base->cpu, HK_FLAG_TIMER) &&
+	    !(timer->flags & TIMER_DEFERRABLE)) {
+		call_single_data_t *c;
+

kernel/time/timer.c line 1079

Quoted 10 lines
kernel/time/timer.c +7 -0
+		c = per_cpu_ptr(&raise_timer_csd, base->cpu);
+
+		/* Make sure bitmap updates are visible on remote CPUs */
+		smp_wmb();
+		smp_call_function_single_async(base->cpu, c);
+	}
+
 out_unlock:
 	raw_spin_unlock_irqrestore(&base->lock, flags);
 

Could you please explain me, why you decided to use the above implementation for raising the timer softirq after modifying a timer?

Thanks,

Anna-Maria

#5 lore raw

Re: [patch 2/3] timers: do not raise softirq unconditionally (spinlockless version)

In reply to Marcelo Tosatti
Quoted 6 lines · Marcelo Tosatti

Check base->pending_map locklessly and skip raising timer softirq if empty.

What allows the lockless (and potentially racy against mod_timer) check is that mod_timer will raise another timer softirq after modifying base->pending_map.

The raise of the timer softirq after adding the timer is done unconditionally - so there are timer softirqs raised which are not required at all, as mentioned before.

This check is for !CONFIG_PREEMPT_RT_FULL only implemented. The commit message totally igonres that you are implementing something CONFIG_PREEMPT_RT_FULL dependent as well.

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

Index: linux-rt-devel/kernel/time/timer.c
===================================================================

kernel/time/timer.c line 1783

Quoted 8 lines
kernel/time/timer.c +5 -0
@@ -1776,6 +1776,24 @@
 		if (time_before(jiffies, base->clk))
 			return;
 	}
+
+#ifdef CONFIG_PREEMPT_RT_FULL
+/* On RT, irq work runs from softirq */
+	if (irq_work_needs_cpu())
+		goto raise;

So with this patch and the change you made in the patch before, timers on RT are expired only when there is pending irq work or after modifying a timer on a non housekeeping cpu?

With your patches I could create the following problematic situation on RT (if I understood everything properly): I add a timer which should expire in 50 jiffies to the wheel of a non housekeeping cpu. So it ends up 50 buckets away form now in the first wheel. This timer is the only timer in the wheel and the next timer softirq raise is required in 50 jiffies. After adding the timer, the timer interrupt is raised, and no timer has to be expired, because there is no timer pending. If there is no irq work required during the next 51 jiffies and also no timer changed, the timer I added, will not expire in time. The timer_base will come out of idle but will not forward the base clk. This makes it even worse: When then adding a timer, the timer base is forwarded - but without checking for the next pending timer, so the first added timer will be delayed even more.

So your implementation lacks forwarding the timer_base->clk when timer_base comes out of idle with respect to the next pending timer.

Quoted 7 lines
kernel/time/timer.c +6 -0
+#endif
+	base = this_cpu_ptr(&timer_bases[BASE_STD]);
+	if (!housekeeping_cpu(base->cpu, HK_FLAG_TIMER)) {
+		if (!bitmap_empty(base->pending_map, WHEEL_SIZE))
+			goto raise;
+		base++;

kernel/time/timer.c line 1799

Quoted 10 lines
kernel/time/timer.c +7 -0
+		if (!bitmap_empty(base->pending_map, WHEEL_SIZE))
+			goto raise;
+
+		return;
+	}
+
+raise:
 	raise_softirq(TIMER_SOFTIRQ);
 }
 

Thanks,

Anna-Maria

#3 lore raw

Re: [patch 1/3] timers: raise timer softirq on __mod_timer/add_timer_on

In reply to Anna-Maria Gleixner

Hi Anna-Maria,

Quoted 7 lines · Anna-Maria Gleixner

On Mon, 15 Apr 2019, Marcelo Tosatti wrote:

[...]

Quoted 3 lines

The patch "timers: do not raise softirq unconditionally" from Thomas attempts to address that by checking, in the sched tick, whether its necessary to raise the timer softirq.

https://lore.kernel.org/patchwork/patch/446045/

Quoted 3 lines
Quoted 3 lines

Unfortunately, it attempts to grab
the tvec base spinlock which generates the issue described in the patch "Revert "timers: do not raise softirq unconditionally"".

https://lore.kernel.org/patchwork/patch/552474/

Quoted 2 lines

Both patches are not available in the version your patch set is based on. Better pointers would be helpful.

See above.

Quoted 9 lines
Quoted 3 lines

tvec_base->lock protects addition of timers to the wheel versus timer interrupt execution.

The timer_base->lock (formally known as tvec_base->lock), synchronizes all accesses to timer_base and not only addition of timers versus timer interrupt execution. Deletion of timers, getting the next timer interrupt, forwarding the base clock and migration of timers are protected as well by timer_base->lock.

Right.

Quoted 5 lines
Quoted 2 lines

This patch does not grab the tvec base spinlock from irq context, but rather performs a lockless access to base->pending_map.

I cannot see where this patch performs a lockless access to timer_base->pending_map.

[patch 2/3] timers: do not raise softirq unconditionally (spinlockless version)

Quoted 10 lines
Quoted 4 lines

It handles the the race between timer addition and timer interrupt execution by unconditionally (in case of isolated CPUs) raising the timer softirq after making sure the updated bitmap is visible on remote CPUs.

So after modifying a timer on a non housekeeping timer base, the timer softirq is raised - even if there is no pending timer in the next bucket. Only with this patch, this shouldn't be a problem - but it is an additional raise of timer softirq and an overhead when adding a timer, because the normal timer softirq is raised from sched tick anyway.

It should be clear why this is necessary when reading

[patch 2/3] timers: do not raise softirq unconditionally (spinlockless version)

Quoted 24 lines
Quoted 24 lines
---
 kernel/time/timer.c |   38 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 38 insertions(+)

Index: linux-rt-devel/kernel/time/timer.c
===================================================================

kernel/time/timer.c +9 -0
@@ -1056,6 +1063,17 @@
 		internal_add_timer(base, timer);
 	}
 
+	if (!housekeeping_cpu(base->cpu, HK_FLAG_TIMER) &&
+	    !(timer->flags & TIMER_DEFERRABLE)) {
+		call_single_data_t *c;
+
+		c = per_cpu_ptr(&raise_timer_csd, base->cpu);
+
+		/* Make sure bitmap updates are visible on remote CPUs */
+		smp_wmb();
+		smp_call_function_single_async(base->cpu, c);
Quoted 8 lines

kernel/time/timer.c line 1079

Quoted 5 lines
kernel/time/timer.c +2 -0
+	}
+
 out_unlock:
 	raw_spin_unlock_irqrestore(&base->lock, flags);
 

Could you please explain me, why you decided to use the above implementation for raising the timer softirq after modifying a timer?

Because of the following race condition which is open after

"[patch 2/3] timers: do not raise softirq unconditionally (spinlockless version)":

CPU-0 CPU-1

				jiffies=99
runs
add_timer_on, with 
timer->expires=100
				jiffies=100
				run_softirq(), sees pending bitmap clear

add_timer_on
returns and
timer was not executed

P)

This race did not exist before.

So by raising a softirq on the remote CPU
at point P), its ensured the timer will
be executed ASAP.

#17 lore raw
In reply to Anna-Maria Gleixner
Quoted 8 lines · Anna-Maria Gleixner

Hi,

I had a look at the queue and have several questions about your implementation.

First of all, I had some troubles to understand your commit messages. So I first had to read the code and then tried to understand the commit messages. It is easier, if it works the other way round.

Right. Commit message seemed descriptive to me, but i should probably try to improve the explanation in the commit message.

Quoted 11 lines · Marcelo Tosatti
Quoted 6 lines

For isolated CPUs, we'd like to skip awakening ktimersoftd (the switch to and then back from ktimersoftd takes 10us in virtualized environments, in addition to other OS overhead, which exceeds telco requirements for packet forwarding for 5G) from the sched tick.

You would like to prevent raising the timer softirq in general from the sched tick for isolated CPUs? Or you would like to prevent raising the timer softirq if no pending timer is available?

With DPDK and CPU isolation, there are no low resolution timers running on the isolated CPUs. So prevent raising timer softirq if no pending timer is available is enough.

Quoted 3 lines

Nevertheless, this change is not PREEMPT_RT specific. It is a NOHZ dependand change. So it would be nice, if the queue is against mainline. But please correct me, if I'm wrong.

Since it was based on the idea of

https://lore.kernel.org/patchwork/patch/446045/

Which was an -RT patch, i decided to submit it against the -RT kernel.

But it can be merged through the mainline kernel queue as well, i believe.

Quoted 8 lines

[...]

Quoted 3 lines

This patchset reduces cyclictest latency from 25us to 14us on my testbox.

A lot of information is missing: How does your environment looks like for this test, what is your workload,...?

x86 hardware, with KVM virtualized, running -RT kernel on both host and guest. Relevant host kernel command line:

isolcpus=1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,14 intel_pstate=disable nosoftlockup nohz=on nohz_full=1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,14 rcu_nocbs=1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,14

Relevant guest kernel command line:
isolcpus=1 nosoftlockup nohz=on nohz_full=1
rcu_nocbs=1

And workload in question is cyclictest (the production software is DPDK, but cyclictest is used to gather latency data).

Quoted 1 line

Did you also run other tests?

Yes, have a custom module stress test to attempt to hit the race. Daniel (CC'ed) ran it under a kernel with debugging enabled, with no apparent problems.

So one downside of this patch is that raises the softirq unnecessarily sometimes. However, its impact is reduced to isolated CPUs.

#6 lore raw

Re: [patch 2/3] timers: do not raise softirq unconditionally (spinlockless version)

In reply to Anna-Maria Gleixner
Quoted 5 lines · Anna-Maria Gleixner
Quoted 3 lines · Marcelo Tosatti

Check base->pending_map locklessly and skip raising timer softirq if empty.

Quoted 7 lines
Quoted 3 lines

What allows the lockless (and potentially racy against mod_timer) check is that mod_timer will raise another timer softirq after modifying base->pending_map.

The raise of the timer softirq after adding the timer is done unconditionally - so there are timer softirqs raised which are not required at all, as mentioned before.

Yes. However i can't see a way to avoid that: its not possible to know if the race described earlier happened or not.

Do you have a suggestion on how to avoid this or a way to avoid the IPI+raise softirq ?

Quoted 19 lines

This check is for !CONFIG_PREEMPT_RT_FULL only implemented. The commit message totally igonres that you are implementing something CONFIG_PREEMPT_RT_FULL dependent as well.

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

Index: linux-rt-devel/kernel/time/timer.c
===================================================================

kernel/time/timer.c +1 -0
@@ -1776,6 +1776,24 @@
 		if (time_before(jiffies, base->clk))
 			return;
 	}
+
Quoted 8 lines

kernel/time/timer.c line 1783

Quoted 4 lines
kernel/time/timer.c +4 -0
+#ifdef CONFIG_PREEMPT_RT_FULL
+/* On RT, irq work runs from softirq */
+	if (irq_work_needs_cpu())
+		goto raise;

So with this patch and the change you made in the patch before, timers on RT are expired only when there is pending irq work or after modifying a timer on a non housekeeping cpu?

Well, run_timer_softirq execute only if pending_map contains a bit set.

Quoted 7 lines

With your patches I could create the following problematic situation on RT (if I understood everything properly): I add a timer which should expire in 50 jiffies to the wheel of a non housekeeping cpu. So it ends up 50 buckets away form now in the first wheel. This timer is the only timer in the wheel and the next timer softirq raise is required in 50 jiffies. After adding the timer, the timer interrupt is raised, and no timer has to be expired, because there is no timer pending.

But the softirq will be raised, because pending_map will be set:

+ if (!bitmap_empty(base->pending_map, WHEEL_SIZE))
+ goto raise;

No?

Quoted 33 lines

If there is no irq work required during
the next 51 jiffies and also no timer changed, the timer I added, will not expire in time. The timer_base will come out of idle but will not forward the base clk.

This makes it even worse: When then adding a timer, the timer base is forwarded - but without checking for the next pending timer, so the first added timer will be delayed even more.

So your implementation lacks forwarding the timer_base->clk when timer_base comes out of idle with respect to the next pending timer.

Quoted 7 lines
kernel/time/timer.c +6 -0
+#endif
+	base = this_cpu_ptr(&timer_bases[BASE_STD]);
+	if (!housekeeping_cpu(base->cpu, HK_FLAG_TIMER)) {
+		if (!bitmap_empty(base->pending_map, WHEEL_SIZE))
+			goto raise;
+		base++;

kernel/time/timer.c line 1799

Quoted 10 lines
kernel/time/timer.c +7 -0
+		if (!bitmap_empty(base->pending_map, WHEEL_SIZE))
+			goto raise;
+
+		return;
+	}
+
+raise:
 	raise_softirq(TIMER_SOFTIRQ);
 }
 

Thanks,

Anna-Maria

#7 lore raw

Re: [patch 2/3] timers: do not raise softirq unconditionally (spinlockless version)

Quoted 34 lines · Marcelo Tosatti
Quoted 17 lines · Anna-Maria Gleixner

kernel/time/timer.c line 1783

Quoted 11 lines · Marcelo Tosatti
kernel/time/timer.c +5 -0
@@ -1776,6 +1776,24 @@
 		if (time_before(jiffies, base->clk))
 			return;
 	}
+
+#ifdef CONFIG_PREEMPT_RT_FULL
+/* On RT, irq work runs from softirq */
+	if (irq_work_needs_cpu())
+		goto raise;

So with this patch and the change you made in the patch before, timers on RT are expired only when there is pending irq work or after modifying a timer on a non housekeeping cpu?

Well, run_timer_softirq execute only if pending_map contains a bit set.

Quoted 7 lines

With your patches I could create the following problematic situation on RT (if I understood everything properly): I add a timer which should expire in 50 jiffies to the wheel of a non housekeeping cpu. So it ends up 50 buckets away form now in the first wheel. This timer is the only timer in the wheel and the next timer softirq raise is required in 50 jiffies. After adding the timer, the timer interrupt is raised, and no timer has to be expired, because there is no timer pending.

But the softirq will be raised, because pending_map will be set:

(quoted diff) +2 -0
+               if (!bitmap_empty(base->pending_map, WHEEL_SIZE))
+                       goto raise;
Quoted 1 line

No?

I'm sorry! I read the #endif of the CONFIG_PREEMPT_RT_FULL section as an #else... This is where my confusion comes from. I will think about the problem and your solution a little bit more and give you feedback hopefully on monday.

Thanks,
Anna-Maria

#9 lore raw

Re: [patch 2/3] timers: do not raise softirq unconditionally (spinlockless version)

In reply to Marcelo Tosatti
Quoted 22 lines · Marcelo Tosatti

Check base->pending_map locklessly and skip raising timer softirq if empty.

What allows the lockless (and potentially racy against mod_timer) check is that mod_timer will raise another timer softirq after modifying base->pending_map.

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

Index: linux-rt-devel/kernel/time/timer.c
===================================================================

kernel/time/timer.c +1 -0
@@ -1776,6 +1776,24 @@
 		if (time_before(jiffies, base->clk))
 			return;
 	}
+

kernel/time/timer.c line 1789

Quoted 10 lines
kernel/time/timer.c +10 -0
+#ifdef CONFIG_PREEMPT_RT_FULL
+/* On RT, irq work runs from softirq */
+	if (irq_work_needs_cpu())
+		goto raise;
+#endif
+	base = this_cpu_ptr(&timer_bases[BASE_STD]);
+	if (!housekeeping_cpu(base->cpu, HK_FLAG_TIMER)) {
+		if (!bitmap_empty(base->pending_map, WHEEL_SIZE))
+			goto raise;
+		base++;

Shall we check against CONFIG_NO_HZ_COMMON? Otherwise the base could point to something else rather tha the deferred base (NR_BASES==1 if without nohz-common).

I see that run_local_timers() has similar pattern, actually I'm thinking whether we can put things like "base++" to be inside some "if"s of CONFIG_NO_HZ_COMMON to be clear.

Thanks,

Signature · 1 line
Peter Xu
#10 lore raw

Re: [patch 2/3] timers: do not raise softirq unconditionally (spinlockless version)

Quoted 38 lines · Peter Xu
Quoted 22 lines · Marcelo Tosatti

Check base->pending_map locklessly and skip raising timer softirq if empty.

What allows the lockless (and potentially racy against mod_timer) check is that mod_timer will raise another timer softirq after modifying base->pending_map.

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

Index: linux-rt-devel/kernel/time/timer.c
===================================================================

kernel/time/timer.c +1 -0
@@ -1776,6 +1776,24 @@
 		if (time_before(jiffies, base->clk))
 			return;
 	}
+

kernel/time/timer.c line 1789

Quoted 10 lines
kernel/time/timer.c +10 -0
+#ifdef CONFIG_PREEMPT_RT_FULL
+/* On RT, irq work runs from softirq */
+	if (irq_work_needs_cpu())
+		goto raise;
+#endif
+	base = this_cpu_ptr(&timer_bases[BASE_STD]);
+	if (!housekeeping_cpu(base->cpu, HK_FLAG_TIMER)) {
+		if (!bitmap_empty(base->pending_map, WHEEL_SIZE))
+			goto raise;
+		base++;

Shall we check against CONFIG_NO_HZ_COMMON? Otherwise the base could point to something else rather tha the deferred base (NR_BASES==1 if without nohz-common).

Quoted 8 lines

I see that run_local_timers() has similar pattern, actually I'm thinking whether we can put things like "base++" to be inside some "if"s of CONFIG_NO_HZ_COMMON to be clear.

Thanks,

Signature · 1 line
Peter Xu

Hi Peter,

Yes, that is a good point and needs fixing.

I'll wait for Anna's comments before posting -v2.

#8 lore raw

Re: [patch 2/3] timers: do not raise softirq unconditionally (spinlockless version)

In reply to Anna-Maria Gleixner

On Fri, 31 May 2019, Anna-Maria Gleixner wrote:

[...]

Quoted 2 lines

I will think about the problem and your solution a little bit more and give you feedback hopefully on monday.

I'm sorry for the delay. But now I'm able to give you a detailed feedback:

The general problem is, that your solution is customized to a single
use-case: preventing softirq raise but only if there is _no_ timer pending. To reach this goal without using locks, overhead is added to the formerly optimized add/mod path of a timer. With your code the timer softirq is raised even when there is a pending timer which does not has to be expired right now. But there have been requests in the past for this use case already.

I discussed with Thomas several approaches during the last week how to solve the unconditional softirq timer raise in a more general way without loosing the fast add/mod path of a timer. The approach which seems to be the best has a dependency on a timer code change from a push to pull model which is still under developement (see v2 patchset:
http://lkml.kernel.org/r/[email protected]). The patchset v2 has several problems but we are working on a solution for those problems right now. When the timer pull model is in place the approach to solve the unconditional timer softirq raise could look like the following:

---8<---
The next_expiry value of timer_base struct is used to store the next expiry value even if timer_base is not idle. Therefore it is udpated after adding or modifying a timer and also at the end of timer softirq. In case timer softirq does not has to be raised, the timer_base->clk is incremented to prevent stale clocks. Checking whether timer softirq has to be raised cannot be done lockless.

This code is not compile tested nor boot tested.

---
 kernel/time/timer.c |   60 +++++++++++++++++++++++++++++++---------------------
 1 file changed, 36 insertions(+), 24 deletions(-)
kernel/time/timer.c +36 -24
@@ -552,37 +552,32 @@ static void
 static void
 trigger_dyntick_cpu(struct timer_base *base, struct timer_list *timer)
 {
-	if (!is_timers_nohz_active())
-		return;
-
-	/*
-	 * TODO: This wants some optimizing similar to the code below, but we
-	 * will do that when we switch from push to pull for deferrable timers.
-	 */
-	if (timer->flags & TIMER_DEFERRABLE) {
-		if (tick_nohz_full_cpu(base->cpu))
-			wake_up_nohz_cpu(base->cpu);
-		return;
+	if (is_timers_nohz_active()) {
+		/*
+		 * TODO: This wants some optimizing similar to the code
+		 * below, but we will do that when we switch from push to
+		 * pull for deferrable timers.
+		 */
+		if (timer->flags & TIMER_DEFERRABLE) {
+			if (tick_nohz_full_cpu(base->cpu))
+				wake_up_nohz_cpu(base->cpu);
+			return;
+		}
 	}
 
-	/*
-	 * We might have to IPI the remote CPU if the base is idle and the
-	 * 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;
-
 	/* Check whether this is the new first expiring timer: */
 	if (time_after_eq(timer->expires, base->next_expiry))
 		return;
+	/* Update next expiry time */
+	base->next_expiry = timer->expires;
 
 	/*
-	 * Set the next expiry time and kick the CPU so it can reevaluate the
-	 * wheel:
+	 * We might have to IPI the remote CPU if the base is idle and the
+	 * 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:
 	 */
-	base->next_expiry = timer->expires;
-	wake_up_nohz_cpu(base->cpu);
+	if (is_timers_nohz_active() && base->is_idle)
+		wake_up_nohz_cpu(base->cpu);
 }
 
 static void
@@ -1684,6 +1679,7 @@ static inline void __run_timers(struct t
 		while (levels--)
 			expire_timers(base, heads + levels);
 	}
+	base->next_expiry = __next_timer_interrupt(base);
 	base->running_timer = NULL;
 	raw_spin_unlock_irq(&base->lock);
 }
@@ -1716,8 +1712,24 @@ void run_local_timers(void)
 		base++;
 		if (time_before(jiffies, base->clk))
 			return;
+		base--;
+	}
+
+	/*
+	 * check for next expiry
+	 *
+	 * deferrable base is igonred here - it is only usable when
+	 * switching from push to pull model for deferrable timers
+	 */
+	raw_spin_lock_irq(&base->lock);
+	if (base->clk == base->next_expiry) {
+		raw_spin_unlock_irq(&base->lock);
+		raise_softirq(TIMER_SOFTIRQ);
+	} else {
+		base->clk++;
+		raw_spin_unlock_irq(&base->lock);
+		return;
 	}
-	raise_softirq(TIMER_SOFTIRQ);
 }
 
 /*

---8<---

Thanks,

Anna-Maria