Skip to contentSkip to conversation

v2 expedited "big hammer" RCU grace periods

RFC PATCH In review Paul E. McKenney 4 participants 13 messages Apr 26, 2009 – Apr 27, 2009

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 v2 expedited "big hammer" RCU grace periods

Second cut of "big hammer" expedited RCU grace periods, but only for rcu_bh. This creates another softirq vector, so that entering this softirq vector will have forced an rcu_bh quiescent state (as noted by Dave Miller). Use smp_call_function() to invoke raise_softirq() on all CPUs in order to cause this to happen. Track the CPUs that have passed through a quiescent state (or gone offline) with a cpumask.

Does nothing to expedite callbacks already registered with call_rcu_bh(), but there is no need to.

Passes light rcutorture testing. Grace periods take about 28 microseconds on an 8CPU 1.5GHZ Power box.

Shortcomings:

o Needs more testing, still not for inclusion.

o Does not handle rcu, only rcu_bh.

Changes since v1:

o Added rcutorture support, and added exports required by
rcutorture.

o Added comment stating that smp_call_function() implies a
memory barrier, suggested by Mathieu.

o Added #include for delay.h.

---

 include/linux/interrupt.h |    1 
 include/linux/rcupdate.h  |    2 
 kernel/rcupdate.c         |  115 +++++++++++++++++++++++++
 kernel/rcutorture.c       |  205 +++++++++++++++++++++++++---------------------
 4 files changed, 231 insertions(+), 92 deletions(-)
include/linux/interrupt.h +1 -0
index 91bb76f..b7b58cc 100644
@@ -338,6 +338,7 @@ enum
 	TASKLET_SOFTIRQ,
 	SCHED_SOFTIRQ,
 	HRTIMER_SOFTIRQ,
+	RCU_EXPEDITED_SOFTIRQ,
 	RCU_SOFTIRQ,	/* Preferable RCU should always be the last softirq */
 
 	NR_SOFTIRQS
include/linux/rcupdate.h +2 -0
index 15fbb3c..a606b42 100644
@@ -264,6 +264,8 @@ extern void synchronize_rcu(void);
 extern void rcu_barrier(void);
 extern void rcu_barrier_bh(void);
 extern void rcu_barrier_sched(void);
+extern void synchronize_rcu_bh_expedited(void);
+extern long rcu_batches_completed_bh_expedited(void);
 
 /* Internal to kernel */
 extern void rcu_init(void);
kernel/rcupdate.c +115 -0

131 lines not on this page · raw message

kernel/rcutorture.c +113 -92

297 lines not on this page · raw message

#1 lore raw
Quoted 7 lines · Paul E. McKenney

Second cut of "big hammer" expedited RCU grace periods, but only for rcu_bh. This creates another softirq vector, so that entering this softirq vector will have forced an rcu_bh quiescent state (as noted by Dave Miller). Use smp_call_function() to invoke raise_softirq() on all CPUs in order to cause this to happen. Track the CPUs that have passed through a quiescent state (or gone offline) with a cpumask.

hm, i'm still asking whether doing this would be simpler via a reschedule vector - which not only is an existing facility but also forces all RCU domains through a quiescent state - not just bh-RCU participants.

Triggering a new softirq is in no way simpler that doing an SMP cross-call - in fact softirqs are a finite resource so using some other facility would be preferred.

Am i missing something?

Ingo

#2 lore raw
Quoted 16 lines · * Ingo Molnar ([email protected]) wrote:
Quoted 7 lines · Paul E. McKenney

Second cut of "big hammer" expedited RCU grace periods, but only for rcu_bh. This creates another softirq vector, so that entering this softirq vector will have forced an rcu_bh quiescent state (as noted by Dave Miller). Use smp_call_function() to invoke raise_softirq() on all CPUs in order to cause this to happen. Track the CPUs that have passed through a quiescent state (or gone offline) with a cpumask.

hm, i'm still asking whether doing this would be simpler via a reschedule vector - which not only is an existing facility but also forces all RCU domains through a quiescent state - not just bh-RCU participants.

Quoted 6 lines

Triggering a new softirq is in no way simpler that doing an SMP cross-call - in fact softirqs are a finite resource so using some other facility would be preferred.

Am i missing something?

I think the reason for this whole thread is that waiting for rcu quiescent state, when called many times e.g. in multiple iptables invokations, takes too longs (5 seconds to load the netfilter rules at boot). The three solutions proposed so far are :

- bh disabling + per-cpu read-write lock
- RCU FGP (fast grace periods), where the writer directly check each per-cpu variables associated with netfilter to make sure the quiescent state for a particular resource has been reached. (derived from my userspace RCU implementation)
- expedited "big hammer" rcu GP, where the writer only waits for bh quiescent state. This is useful if we can guarantee that all readers are either in bh context or disable bottom halves.

Therefore, it's really on purpose that Paul does not wait for global RCU quiescent states, but rather just for bh : it's faster.

IMHO, the bh rcu GP shares the same problem as the global RCU GP approach : it monitors global kernel state to ensure quiescence. It's better in practice because bh quiescent states are much more frequent than global QS, but it still depends on every other bh handler and bh disabled section duration to calculate the maximum writer delay. One might argue that if we keep those small, this should not matter in practice.

The RCU FGP approach is interesting because it's based solely on netfilter-specific per-cpu variables to detect QS. Therefore, even if an unrelated piece of kernel software eventually decides to be a bad citizen and disable bh for long periods on a 4096 cpu box, it won't slow down the netfilter tables update.

This last positive aspect of RCU FGP is common with the bh disabling + per-cpu rw lock approach, where the rw lock is also local to netfilter. However, taking a rwlock and disabling bh will make the read-side much slower than RCU FGP (which simply disables preemption and touches a per-cpu GP/nesting count variable). But given RCU FGP is relatively new, it makes sense to use a known-good solution in the short term.

Mathieu

Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#3 lore raw
Quoted 21 lines · Mathieu Desnoyers
Quoted 20 lines · * Ingo Molnar ([email protected]) wrote:
Quoted 7 lines · Paul E. McKenney

Second cut of "big hammer" expedited RCU grace periods, but only for rcu_bh. This creates another softirq vector, so that entering this softirq vector will have forced an rcu_bh quiescent state (as noted by Dave Miller). Use smp_call_function() to invoke raise_softirq() on all CPUs in order to cause this to happen. Track the CPUs that have passed through a quiescent state (or gone offline) with a cpumask.

hm, i'm still asking whether doing this would be simpler via a reschedule vector - which not only is an existing facility but also forces all RCU domains through a quiescent state - not just bh-RCU participants.

Triggering a new softirq is in no way simpler that doing an SMP cross-call - in fact softirqs are a finite resource so using some other facility would be preferred.

Quoted 7 lines
Quoted 2 lines

Am i missing something?

I think the reason for this whole thread is that waiting for rcu quiescent state, when called many times e.g. in multiple iptables invokations, takes too longs (5 seconds to load the netfilter rules at boot). [...]

I'm aware of the problem space.

I was suggesting that to trigger the quiescent state and to wait for it to propagate it would be enough to reuse the reschedule mechanism.

It would be relatively straightforward: first a send-reschedule then do a wait_task_context_switch() on rq->curr - both are existing primitives. (a task reference has to be taken but that's pretty much all)

By the time wait_task_context_switch() returns from the last CPU we know that the quiescent state has passed.

Ingo

#4 lore raw
Quoted 34 lines · Ingo Molnar
Quoted 21 lines · Mathieu Desnoyers
Quoted 20 lines · * Ingo Molnar ([email protected]) wrote:
Quoted 7 lines · Paul E. McKenney

Second cut of "big hammer" expedited RCU grace periods, but only for rcu_bh. This creates another softirq vector, so that entering this softirq vector will have forced an rcu_bh quiescent state (as noted by Dave Miller). Use smp_call_function() to invoke raise_softirq() on all CPUs in order to cause this to happen. Track the CPUs that have passed through a quiescent state (or gone offline) with a cpumask.

hm, i'm still asking whether doing this would be simpler via a reschedule vector - which not only is an existing facility but also forces all RCU domains through a quiescent state - not just bh-RCU participants.

Triggering a new softirq is in no way simpler that doing an SMP cross-call - in fact softirqs are a finite resource so using some other facility would be preferred.

Quoted 7 lines
Quoted 2 lines

Am i missing something?

I think the reason for this whole thread is that waiting for rcu quiescent state, when called many times e.g. in multiple iptables invokations, takes too longs (5 seconds to load the netfilter rules at boot). [...]

I'm aware of the problem space.

Quoted 8 lines

I was suggesting that to trigger the quiescent state and to wait for it to propagate it would be enough to reuse the reschedule mechanism.

It would be relatively straightforward: first a send-reschedule then do a wait_task_context_switch() on rq->curr - both are existing primitives. (a task reference has to be taken but that's pretty much all)

Well, one reason I didn't take this approach was that I didn't happen to think of it. ;-)

Also that I hadn't heard of wait_task_context_switch().

Hmmm... Looking for wait_task_context_switch(). OK, found it.

It looks to me that this primitive won't return until the scheduler actually decides to run something else. We instead need to have something that stops waiting once the CPU enters the scheduler, hence the previous thought of making rcu_qsctr_inc() do a bit of extra work.

This would be a way of making an expedited RCU-sched across all RCU implementations. As noted in the earlier email, it would not handle RCU or RCU-bh in a -rt kernel.

Quoted 2 lines

By the time wait_task_context_switch() returns from the last CPU we know that the quiescent state has passed.

We would want to wait for all of the CPUs in parallel, though, wouldn't we? Seems that we would not want to wait for the last CPU to do another trip through the scheduler if it had already passed through the scheduler while we were waiting on the earlier CPUs.

So it seems like we would still want a two-pass approach -- one pass to capture the current state, the second pass to wait for the state to change.

Thanx, Paul

#5 lore raw
Quoted 70 lines · Paul E. McKenney
Quoted 34 lines · Ingo Molnar
Quoted 21 lines · Mathieu Desnoyers
Quoted 20 lines · * Ingo Molnar ([email protected]) wrote:
Quoted 7 lines · Paul E. McKenney

Second cut of "big hammer" expedited RCU grace periods, but only for rcu_bh. This creates another softirq vector, so that entering this softirq vector will have forced an rcu_bh quiescent state (as noted by Dave Miller). Use smp_call_function() to invoke raise_softirq() on all CPUs in order to cause this to happen. Track the CPUs that have passed through a quiescent state (or gone offline) with a cpumask.

hm, i'm still asking whether doing this would be simpler via a reschedule vector - which not only is an existing facility but also forces all RCU domains through a quiescent state - not just bh-RCU participants.

Triggering a new softirq is in no way simpler that doing an SMP cross-call - in fact softirqs are a finite resource so using some other facility would be preferred.

Quoted 7 lines
Quoted 2 lines

Am i missing something?

I think the reason for this whole thread is that waiting for rcu quiescent state, when called many times e.g. in multiple iptables invokations, takes too longs (5 seconds to load the netfilter rules at boot). [...]

I'm aware of the problem space.

Quoted 8 lines

I was suggesting that to trigger the quiescent state and to wait for it to propagate it would be enough to reuse the reschedule mechanism.

It would be relatively straightforward: first a send-reschedule then do a wait_task_context_switch() on rq->curr - both are existing primitives. (a task reference has to be taken but that's pretty much all)

Well, one reason I didn't take this approach was that I didn't happen to think of it. ;-)

Also that I hadn't heard of wait_task_context_switch().

Hmmm... Looking for wait_task_context_switch(). OK, found it.

It looks to me that this primitive won't return until the scheduler actually decides to run something else. We instead need to have something that stops waiting once the CPU enters the scheduler, hence the previous thought of making rcu_qsctr_inc() do a bit of extra work.

This would be a way of making an expedited RCU-sched across all RCU implementations. As noted in the earlier email, it would not handle RCU or RCU-bh in a -rt kernel.

Quoted 2 lines

By the time wait_task_context_switch() returns from the last CPU we know that the quiescent state has passed.

We would want to wait for all of the CPUs in parallel, though, wouldn't we? Seems that we would not want to wait for the last CPU to do another trip through the scheduler if it had already passed through the scheduler while we were waiting on the earlier CPUs.

Quoted 3 lines

So it seems like we would still want a two-pass approach -- one pass to capture the current state, the second pass to wait for the state to change.

I think waiting in parallel is still possible (first kick all tasks, then make sure all tasks have left the CPU at least once).

The busy-waiting in wait_task_context_switch() is indeed a problem - but perhaps that could be refactored to be a migration-thread driven wait_for_completion() + complete() cycle? It could be driven by preempt notifiers perhaps - and become zero-cost.

Ingo

#6 lore raw
Quoted 77 lines · Ingo Molnar
Quoted 70 lines · Paul E. McKenney
Quoted 34 lines · Ingo Molnar
Quoted 21 lines · Mathieu Desnoyers
Quoted 20 lines · * Ingo Molnar ([email protected]) wrote:
Quoted 7 lines · Paul E. McKenney

Second cut of "big hammer" expedited RCU grace periods, but only for rcu_bh. This creates another softirq vector, so that entering this softirq vector will have forced an rcu_bh quiescent state (as noted by Dave Miller). Use smp_call_function() to invoke raise_softirq() on all CPUs in order to cause this to happen. Track the CPUs that have passed through a quiescent state (or gone offline) with a cpumask.

hm, i'm still asking whether doing this would be simpler via a reschedule vector - which not only is an existing facility but also forces all RCU domains through a quiescent state - not just bh-RCU participants.

Triggering a new softirq is in no way simpler that doing an SMP cross-call - in fact softirqs are a finite resource so using some other facility would be preferred.

Quoted 7 lines
Quoted 2 lines

Am i missing something?

I think the reason for this whole thread is that waiting for rcu quiescent state, when called many times e.g. in multiple iptables invokations, takes too longs (5 seconds to load the netfilter rules at boot). [...]

I'm aware of the problem space.

Quoted 8 lines

I was suggesting that to trigger the quiescent state and to wait for it to propagate it would be enough to reuse the reschedule mechanism.

It would be relatively straightforward: first a send-reschedule then do a wait_task_context_switch() on rq->curr - both are existing primitives. (a task reference has to be taken but that's pretty much all)

Well, one reason I didn't take this approach was that I didn't happen to think of it. ;-)

Also that I hadn't heard of wait_task_context_switch().

Hmmm... Looking for wait_task_context_switch(). OK, found it.

It looks to me that this primitive won't return until the scheduler actually decides to run something else. We instead need to have something that stops waiting once the CPU enters the scheduler, hence the previous thought of making rcu_qsctr_inc() do a bit of extra work.

This would be a way of making an expedited RCU-sched across all RCU implementations. As noted in the earlier email, it would not handle RCU or RCU-bh in a -rt kernel.

Quoted 2 lines

By the time wait_task_context_switch() returns from the last CPU we know that the quiescent state has passed.

We would want to wait for all of the CPUs in parallel, though, wouldn't we? Seems that we would not want to wait for the last CPU to do another trip through the scheduler if it had already passed through the scheduler while we were waiting on the earlier CPUs.

Quoted 3 lines

So it seems like we would still want a two-pass approach -- one pass to capture the current state, the second pass to wait for the state to change.

Quoted 7 lines

I think waiting in parallel is still possible (first kick all tasks, then make sure all tasks have left the CPU at least once).

The busy-waiting in wait_task_context_switch() is indeed a problem - but perhaps that could be refactored to be a migration-thread driven wait_for_completion() + complete() cycle? It could be driven by preempt notifiers perhaps - and become zero-cost.

Hmmm... It would need to be informed of the quiescent state even if that quiescent state did not result in a preemption.

But you are right -- I do need to expedite RCU, not just RCU-bh, especially given that the boot-speed guys are starting to see grace periods as a measureable fraction of the boot time. I will take another pass at this.

Thanx, Paul

#7 lore raw
Quoted 87 lines · Paul E. McKenney
Quoted 77 lines · Ingo Molnar
Quoted 70 lines · Paul E. McKenney
Quoted 34 lines · Ingo Molnar
Quoted 21 lines · Mathieu Desnoyers
Quoted 20 lines · * Ingo Molnar ([email protected]) wrote:
Quoted 7 lines · Paul E. McKenney

Second cut of "big hammer" expedited RCU grace periods, but only for rcu_bh. This creates another softirq vector, so that entering this softirq vector will have forced an rcu_bh quiescent state (as noted by Dave Miller). Use smp_call_function() to invoke raise_softirq() on all CPUs in order to cause this to happen. Track the CPUs that have passed through a quiescent state (or gone offline) with a cpumask.

hm, i'm still asking whether doing this would be simpler via a reschedule vector - which not only is an existing facility but also forces all RCU domains through a quiescent state - not just bh-RCU participants.

Triggering a new softirq is in no way simpler that doing an SMP cross-call - in fact softirqs are a finite resource so using some other facility would be preferred.

Quoted 7 lines
Quoted 2 lines

Am i missing something?

I think the reason for this whole thread is that waiting for rcu quiescent state, when called many times e.g. in multiple iptables invokations, takes too longs (5 seconds to load the netfilter rules at boot). [...]

I'm aware of the problem space.

Quoted 8 lines

I was suggesting that to trigger the quiescent state and to wait for it to propagate it would be enough to reuse the reschedule mechanism.

It would be relatively straightforward: first a send-reschedule then do a wait_task_context_switch() on rq->curr - both are existing primitives. (a task reference has to be taken but that's pretty much all)

Well, one reason I didn't take this approach was that I didn't happen to think of it. ;-)

Also that I hadn't heard of wait_task_context_switch().

Hmmm... Looking for wait_task_context_switch(). OK, found it.

It looks to me that this primitive won't return until the scheduler actually decides to run something else. We instead need to have something that stops waiting once the CPU enters the scheduler, hence the previous thought of making rcu_qsctr_inc() do a bit of extra work.

This would be a way of making an expedited RCU-sched across all RCU implementations. As noted in the earlier email, it would not handle RCU or RCU-bh in a -rt kernel.

Quoted 2 lines

By the time wait_task_context_switch() returns from the last CPU we know that the quiescent state has passed.

We would want to wait for all of the CPUs in parallel, though, wouldn't we? Seems that we would not want to wait for the last CPU to do another trip through the scheduler if it had already passed through the scheduler while we were waiting on the earlier CPUs.

Quoted 3 lines

So it seems like we would still want a two-pass approach -- one pass to capture the current state, the second pass to wait for the state to change.

Quoted 8 lines

I think waiting in parallel is still possible (first kick all tasks, then make sure all tasks have left the CPU at least once).

The busy-waiting in wait_task_context_switch() is indeed a problem - but perhaps that could be refactored to be a migration-thread driven wait_for_completion() + complete() cycle? It could be driven by preempt notifiers perhaps - and become zero-cost.

Quoted 7 lines

Hmmm... It would need to be informed of the quiescent state even if that quiescent state did not result in a preemption.

But you are right -- I do need to expedite RCU, not just RCU-bh, especially given that the boot-speed guys are starting to see grace periods as a measureable fraction of the boot time. I will take another pass at this.

The precise method of signalling is a detail i suspect - so by all means use a new softirq if that is the cleanest. I'd also agree that covering not just bh-rcu would definitely be a good idea.

Ingo

#8 lore raw
Quoted 93 lines · Ingo Molnar
Quoted 90 lines · Paul E. McKenney
Quoted 77 lines · Ingo Molnar
Quoted 70 lines · Paul E. McKenney
Quoted 34 lines · Ingo Molnar
Quoted 21 lines · Mathieu Desnoyers
Quoted 20 lines · * Ingo Molnar ([email protected]) wrote:
Quoted 7 lines · Paul E. McKenney

Second cut of "big hammer" expedited RCU grace periods, but only for rcu_bh. This creates another softirq vector, so that entering this softirq vector will have forced an rcu_bh quiescent state (as noted by Dave Miller). Use smp_call_function() to invoke raise_softirq() on all CPUs in order to cause this to happen. Track the CPUs that have passed through a quiescent state (or gone offline) with a cpumask.

hm, i'm still asking whether doing this would be simpler via a reschedule vector - which not only is an existing facility but also forces all RCU domains through a quiescent state - not just bh-RCU participants.

Triggering a new softirq is in no way simpler that doing an SMP cross-call - in fact softirqs are a finite resource so using some other facility would be preferred.

Quoted 7 lines
Quoted 2 lines

Am i missing something?

I think the reason for this whole thread is that waiting for rcu quiescent state, when called many times e.g. in multiple iptables invokations, takes too longs (5 seconds to load the netfilter rules at boot). [...]

I'm aware of the problem space.

Quoted 8 lines

I was suggesting that to trigger the quiescent state and to wait for it to propagate it would be enough to reuse the reschedule mechanism.

It would be relatively straightforward: first a send-reschedule then do a wait_task_context_switch() on rq->curr - both are existing primitives. (a task reference has to be taken but that's pretty much all)

Well, one reason I didn't take this approach was that I didn't happen to think of it. ;-)

Also that I hadn't heard of wait_task_context_switch().

Hmmm... Looking for wait_task_context_switch(). OK, found it.

It looks to me that this primitive won't return until the scheduler actually decides to run something else. We instead need to have something that stops waiting once the CPU enters the scheduler, hence the previous thought of making rcu_qsctr_inc() do a bit of extra work.

This would be a way of making an expedited RCU-sched across all RCU implementations. As noted in the earlier email, it would not handle RCU or RCU-bh in a -rt kernel.

Quoted 2 lines

By the time wait_task_context_switch() returns from the last CPU we know that the quiescent state has passed.

We would want to wait for all of the CPUs in parallel, though, wouldn't we? Seems that we would not want to wait for the last CPU to do another trip through the scheduler if it had already passed through the scheduler while we were waiting on the earlier CPUs.

Quoted 3 lines

So it seems like we would still want a two-pass approach -- one pass to capture the current state, the second pass to wait for the state to change.

Quoted 8 lines

I think waiting in parallel is still possible (first kick all tasks, then make sure all tasks have left the CPU at least once).

The busy-waiting in wait_task_context_switch() is indeed a problem - but perhaps that could be refactored to be a migration-thread driven wait_for_completion() + complete() cycle? It could be driven by preempt notifiers perhaps - and become zero-cost.

Hmmm... It would need to be informed of the quiescent state even if that quiescent state did not result in a preemption.

Quoted 8 lines
Quoted 4 lines

But you are right -- I do need to expedite RCU, not just RCU-bh, especially given that the boot-speed guys are starting to see grace periods as a measureable fraction of the boot time. I will take another pass at this.

The precise method of signalling is a detail i suspect - so by all means use a new softirq if that is the cleanest. I'd also agree that covering not just bh-rcu would definitely be a good idea.

Fair enough! ;-)

Thanx, Paul

#9 lore raw
In reply to Paul E. McKenney
Quoted 89 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 77 lines · Ingo Molnar
Quoted 70 lines · Paul E. McKenney
Quoted 34 lines · Ingo Molnar
Quoted 21 lines · Mathieu Desnoyers
Quoted 20 lines · * Ingo Molnar ([email protected]) wrote:
Quoted 7 lines · Paul E. McKenney

Second cut of "big hammer" expedited RCU grace periods, but only for rcu_bh. This creates another softirq vector, so that entering this softirq vector will have forced an rcu_bh quiescent state (as noted by Dave Miller). Use smp_call_function() to invoke raise_softirq() on all CPUs in order to cause this to happen. Track the CPUs that have passed through a quiescent state (or gone offline) with a cpumask.

hm, i'm still asking whether doing this would be simpler via a reschedule vector - which not only is an existing facility but also forces all RCU domains through a quiescent state - not just bh-RCU participants.

Triggering a new softirq is in no way simpler that doing an SMP cross-call - in fact softirqs are a finite resource so using some other facility would be preferred.

Quoted 7 lines
Quoted 2 lines

Am i missing something?

I think the reason for this whole thread is that waiting for rcu quiescent state, when called many times e.g. in multiple iptables invokations, takes too longs (5 seconds to load the netfilter rules at boot). [...]

I'm aware of the problem space.

Quoted 8 lines

I was suggesting that to trigger the quiescent state and to wait for it to propagate it would be enough to reuse the reschedule mechanism.

It would be relatively straightforward: first a send-reschedule then do a wait_task_context_switch() on rq->curr - both are existing primitives. (a task reference has to be taken but that's pretty much all)

Well, one reason I didn't take this approach was that I didn't happen to think of it. ;-)

Also that I hadn't heard of wait_task_context_switch().

Hmmm... Looking for wait_task_context_switch(). OK, found it.

It looks to me that this primitive won't return until the scheduler actually decides to run something else. We instead need to have something that stops waiting once the CPU enters the scheduler, hence the previous thought of making rcu_qsctr_inc() do a bit of extra work.

This would be a way of making an expedited RCU-sched across all RCU implementations. As noted in the earlier email, it would not handle RCU or RCU-bh in a -rt kernel.

Quoted 2 lines

By the time wait_task_context_switch() returns from the last CPU we know that the quiescent state has passed.

We would want to wait for all of the CPUs in parallel, though, wouldn't we? Seems that we would not want to wait for the last CPU to do another trip through the scheduler if it had already passed through the scheduler while we were waiting on the earlier CPUs.

Quoted 3 lines

So it seems like we would still want a two-pass approach -- one pass to capture the current state, the second pass to wait for the state to change.

Quoted 7 lines

I think waiting in parallel is still possible (first kick all tasks, then make sure all tasks have left the CPU at least once).

The busy-waiting in wait_task_context_switch() is indeed a problem - but perhaps that could be refactored to be a migration-thread driven wait_for_completion() + complete() cycle? It could be driven by preempt notifiers perhaps - and become zero-cost.

Hmmm... It would need to be informed of the quiescent state even if that quiescent state did not result in a preemption.

Quoted 6 lines

But you are right -- I do need to expedite RCU, not just RCU-bh, especially given that the boot-speed guys are starting to see grace periods as a measureable fraction of the boot time. I will take another pass at this.

Thanx, Paul

It might sound a bit simplistic, but... scheduling a high-priority workqueue on every CPUs would give you the guarantees you seem to need here. Or is the delay of letting the scheduler schedule a high-priority task a delay you are trying to avoid ?

Some kind of priority boosting done by synchronize_rcu() could probably work, and you could support rcu callbacks priority boosting by assigning a priority to each callback registered (same priority as the thread which invoked call_rcu). The rcu callbacks could then be sorted by priority in a RB tree, and only the callbacks associated with priority

Quoted 1 line

= than the next priority task would be executed.

Mathieu

Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#10 lore raw
Quoted 100 lines · Mathieu Desnoyers
Quoted 86 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 77 lines · Ingo Molnar
Quoted 70 lines · Paul E. McKenney
Quoted 34 lines · Ingo Molnar
Quoted 21 lines · Mathieu Desnoyers
Quoted 20 lines · * Ingo Molnar ([email protected]) wrote:
Quoted 7 lines · Paul E. McKenney

Second cut of "big hammer" expedited RCU grace periods, but only for rcu_bh. This creates another softirq vector, so that entering this softirq vector will have forced an rcu_bh quiescent state (as noted by Dave Miller). Use smp_call_function() to invoke raise_softirq() on all CPUs in order to cause this to happen. Track the CPUs that have passed through a quiescent state (or gone offline) with a cpumask.

hm, i'm still asking whether doing this would be simpler via a reschedule vector - which not only is an existing facility but also forces all RCU domains through a quiescent state - not just bh-RCU participants.

Triggering a new softirq is in no way simpler that doing an SMP cross-call - in fact softirqs are a finite resource so using some other facility would be preferred.

Quoted 7 lines
Quoted 2 lines

Am i missing something?

I think the reason for this whole thread is that waiting for rcu quiescent state, when called many times e.g. in multiple iptables invokations, takes too longs (5 seconds to load the netfilter rules at boot). [...]

I'm aware of the problem space.

Quoted 8 lines

I was suggesting that to trigger the quiescent state and to wait for it to propagate it would be enough to reuse the reschedule mechanism.

It would be relatively straightforward: first a send-reschedule then do a wait_task_context_switch() on rq->curr - both are existing primitives. (a task reference has to be taken but that's pretty much all)

Well, one reason I didn't take this approach was that I didn't happen to think of it. ;-)

Also that I hadn't heard of wait_task_context_switch().

Hmmm... Looking for wait_task_context_switch(). OK, found it.

It looks to me that this primitive won't return until the scheduler actually decides to run something else. We instead need to have something that stops waiting once the CPU enters the scheduler, hence the previous thought of making rcu_qsctr_inc() do a bit of extra work.

This would be a way of making an expedited RCU-sched across all RCU implementations. As noted in the earlier email, it would not handle RCU or RCU-bh in a -rt kernel.

Quoted 2 lines

By the time wait_task_context_switch() returns from the last CPU we know that the quiescent state has passed.

We would want to wait for all of the CPUs in parallel, though, wouldn't we? Seems that we would not want to wait for the last CPU to do another trip through the scheduler if it had already passed through the scheduler while we were waiting on the earlier CPUs.

Quoted 3 lines

So it seems like we would still want a two-pass approach -- one pass to capture the current state, the second pass to wait for the state to change.

Quoted 7 lines

I think waiting in parallel is still possible (first kick all tasks, then make sure all tasks have left the CPU at least once).

The busy-waiting in wait_task_context_switch() is indeed a problem - but perhaps that could be refactored to be a migration-thread driven wait_for_completion() + complete() cycle? It could be driven by preempt notifiers perhaps - and become zero-cost.

Quoted 7 lines

Hmmm... It would need to be informed of the quiescent state even if that quiescent state did not result in a preemption.

But you are right -- I do need to expedite RCU, not just RCU-bh, especially given that the boot-speed guys are starting to see grace periods as a measureable fraction of the boot time. I will take another pass at this.

It might sound a bit simplistic, but... scheduling a high-priority workqueue on every CPUs would give you the guarantees you seem to need here. Or is the delay of letting the scheduler schedule a high-priority task a delay you are trying to avoid ?

Quoted 6 lines

Some kind of priority boosting done by synchronize_rcu() could probably work, and you could support rcu callbacks priority boosting by assigning a priority to each callback registered (same priority as the thread which invoked call_rcu). The rcu callbacks could then be sorted by priority in a RB tree, and only the callbacks associated with priority

Quoted 1 line

= than the next priority task would be executed.

I did something similar for the implementation of synchronize_sched() in preemptable RCU. The interactions with CPU hotplug are a bit ugly. It will be easier to hook into rcu_qsctr_inc(). ;-)

But this discussion has been quite useful -- my thoughts for the design of the long-term solution were a bit lacking, as they would have allowed a heavy callback load to delay an expedited grace period. So this will be a bit of a hack until I get all the RCU implementations converged, but there is a nice long-term solution to be had by integrating the expediting into the hierarchical-RCU data structures.

Thanx, Paul

#11 lore raw
In reply to Mathieu Desnoyers

Hi.

Quoted 4 lines · Mathieu Desnoyers

It might sound a bit simplistic, but... scheduling a high-priority workqueue on every CPUs would give you the guarantees you seem to need here. Or is the delay of letting the scheduler schedule a high-priority task a delay you are trying to avoid ?

I believe not the abstract (empty) task should be invoked, but a real task which does the work. Presumably if we want to schedule a way networking part to copy its counters, system should wake up the appropriate userspace thread blocked in a grace-period waking path, so effectively either RCU callback processing code or some registered thread should be awakened.

Just a detail though.

Signature · 1 line
	Evgeniy Polyakov
#12 lore raw
In reply to Ingo Molnar
Quoted 16 lines · Ingo Molnar
Quoted 7 lines · Paul E. McKenney

Second cut of "big hammer" expedited RCU grace periods, but only for rcu_bh. This creates another softirq vector, so that entering this softirq vector will have forced an rcu_bh quiescent state (as noted by Dave Miller). Use smp_call_function() to invoke raise_softirq() on all CPUs in order to cause this to happen. Track the CPUs that have passed through a quiescent state (or gone offline) with a cpumask.

hm, i'm still asking whether doing this would be simpler via a reschedule vector - which not only is an existing facility but also forces all RCU domains through a quiescent state - not just bh-RCU participants.

Quoted 5 lines

Triggering a new softirq is in no way simpler that doing an SMP cross-call - in fact softirqs are a finite resource so using some other facility would be preferred.

Am i missing something?

Well, it is entirely possible that I am the one missing something.

So, here is the line of reasoning that lead me to the bh-RCU approach:

o The two flavors of RCU that can support an off-to-the-side
expedited implementation are RCU-bh and RCU-sched. Preemptable RCU requires a more intrusive approach for normal RCU, due to the fact that RCU readers can be preempted and can block on locks. Therefore, forcing a reschedule on each CPU does not force a grace period for preemptable RCU.

Of course, there is an easy workaround -- for preemptable RCU, make the expedited primitive just directly invoke synchronize_rcu(). Although this would not provide any speedup,
it would at least guarantee correct operation. But I believe
that we need to have a way to expedite grace periods on -rt kernels with preemptable RCU as well as on non-real-time kernels.

o As you say, an RCU-sched grace period implies an RCU-bh grace
period on non-realtime kernels. Unfortunately, for -rt kernels, softirq handlers can be preempted and can block while waiting for locks, so forcing a reschedule on each CPU does not force a grace period for RCU-bh in a -rt kernel.

Again, there is an easy workaround: in CONFIG_PREEMPT_RT kernels, make the RCU-bh variant of the expedited primitive invoke a new synchronize_rcu_bh() primitive.

Of course, allowing an RCU-sched grace period to imply an RCU-bh grace period loses the DoS-resistance advantages of RCU-bh. However, very few of the RCU updates in the kernel take advantage of DoS resistance. Furthermore, Steve's patch did not use RCU-bh, so one could argue that we should forget about DoS-resistance for the time being. Thoughts?

o The approach in the previous patch works across all kernel
builds, because of the fact that it forces a new softirq handler to run, thus guaranteeing that all prior softirq handlers and RCU-bh read-side critical sections for the CPU in question have completed.

o I used a new softirq vector out of laziness. I could instead
raise RCU_SOFTIRQ, and then add code to each of the rcu_process_callbacks() functions to ack the expedited raise_softirq().

Easy for me to change, though. I guess I don't have to be -that- lazy. ;-)

o So, why RCU-bh rather than RCU-sched?

Again, laziness. The RCU-sched approach requires greater intrusiveness into the existing RCU implementations. Nothing wrong with that, given that this is in fact another RCU API member, but given the choice, I would rather do the intruding after dropping Classic RCU.

The easiest way I could see to minimize intrusion for RCU-sched is to create a new per-CPU counter that is incremented by each implementation of rcu_qsctr_inc(). But even easier to avoid the rcu_qsctr_inc() code path entirely.

Once we have dropped Classic RCU and I have merged Preemptable RCU into Hierarchical RCU, it becomes much more attractive to merge the expediting into the main RCU state machine.

Thoughts?

Thanx, Paul