Additional RCU commits queued for 2.6.37

kernel/rcutiny_plugin.h +5 -0

+
+/*
+ * Tiny-preemptible RCU implementation for rcu_read_unlock().
+ * Decrement ->rcu_read_lock_nesting.  If the result is zero (outermost
+ * rcu_read_unlock()) and ->rcu_read_unlock_special is non-zero, then

kernel/rcutiny_plugin.h +6 -0

+/*
+ * Check for a task exiting while in a preemptible -RCU read-side
+ * critical section, clean up if so.  No need to issue warnings,
+ * as debug_check_no_locks_held() already does this if lockdep
+ * is enabled.
+ */

* Paul E. McKenney ([email protected]) wrote:
[...]

Quoted 5 lines

kernel/rcutiny_plugin.h +5 -0

+
+/*
+ * Tiny-preemptible RCU implementation for rcu_read_unlock().
+ * Decrement ->rcu_read_lock_nesting.  If the result is zero (outermost
+ * rcu_read_unlock()) and ->rcu_read_unlock_special is non-zero, then

kernel/rcutiny_plugin.h line 354

Quoted 10 lines

kernel/rcutiny_plugin.h +10 -0

+ * invoke rcu_read_unlock_special() to clean up after a context switch
+ * in an RCU read-side critical section and other special cases.
+ */
+void __rcu_read_unlock(void)
+{
+	struct task_struct *t = current;
+
+	barrier();  /* needed if we ever invoke rcu_read_unlock in rcutiny.c */
+	if (--t->rcu_read_lock_nesting == 0 &&
+	    unlikely(t->rcu_read_unlock_special))

Hrm I think we discussed this in a past life, but would the following sequence be possible and correct ?

CPU 0

read t->rcu_read_unlock_special
interrupt comes in, preempts. sets t->rcu_read_unlock_special <preempted>
<scheduled back>
iret
decrement and read t->rcu_read_lock_nesting
test both old "special" value (which we have locally on the stack) and detect that rcu_read_lock_nesting is 0.

We actually missed a reschedule.

I think we might need a barrier() between the t->rcu_read_lock_nesting and t->rcu_read_unlock_special reads.

We might need to audit
TREE PREEMPT RCU for the same kind of behavior.

But I might be (again ?) missing something. I've got the feeling you already convinced me that this was OK for some reason, but I trip on this every time I read the code.

[...]

Quoted 13 lines

kernel/rcutiny_plugin.h +13 -0

+/*
+ * Check for a task exiting while in a preemptible -RCU read-side
+ * critical section, clean up if so.  No need to issue warnings,
+ * as debug_check_no_locks_held() already does this if lockdep
+ * is enabled.
+ */
+void exit_rcu(void)
+{
+	struct task_struct *t = current;
+
+	if (t->rcu_read_lock_nesting == 0)
+		return;
+	t->rcu_read_lock_nesting = 1;

kernel/rcutiny_plugin.h line 570

Quoted 3 lines

kernel/rcutiny_plugin.h +3 -0

+	rcu_read_unlock();
+}
+

The interaction with preemption is unclear here. exit.c disables preemption around the call to exit_rcu(), but if, for some reason, rcu_read_unlock_special was set earlier by preemption, then the rcu_read_unlock() code might block and cause problems.

Maybe we should consider clearing rcu_read_unlock_special here ?

Thanks,

Mathieu

Signature · 9 lines

Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Quoted 17 lines · Mathieu Desnoyers

* Paul E. McKenney ([email protected]) wrote:
[...]

Quoted 5 lines

kernel/rcutiny_plugin.h +5 -0

+
+/*
+ * Tiny-preemptible RCU implementation for rcu_read_unlock().
+ * Decrement ->rcu_read_lock_nesting.  If the result is zero (outermost
+ * rcu_read_unlock()) and ->rcu_read_unlock_special is non-zero, then

kernel/rcutiny_plugin.h line 354

Quoted 10 lines

kernel/rcutiny_plugin.h +10 -0

+ * invoke rcu_read_unlock_special() to clean up after a context switch
+ * in an RCU read-side critical section and other special cases.
+ */
+void __rcu_read_unlock(void)
+{
+	struct task_struct *t = current;
+
+	barrier();  /* needed if we ever invoke rcu_read_unlock in rcutiny.c */
+	if (--t->rcu_read_lock_nesting == 0 &&
+	    unlikely(t->rcu_read_unlock_special))

First, thank you for looking this over!!!

Quoted 14 lines

Hrm I think we discussed this in a past life, but would the following sequence be possible and correct ?

CPU 0

read t->rcu_read_unlock_special
interrupt comes in, preempts. sets t->rcu_read_unlock_special <preempted>
<scheduled back>
iret
decrement and read t->rcu_read_lock_nesting
test both old "special" value (which we have locally on the stack) and detect that rcu_read_lock_nesting is 0.

Quoted 4 lines

We actually missed a reschedule.

I think we might need a barrier() between the t->rcu_read_lock_nesting and t->rcu_read_unlock_special reads.

You are correct -- I got too aggressive in eliminating synchronization.

Good catch!!!

I added an ACCESS_ONCE() to the second term of the "if" condition so that it now reads:

	if (--t->rcu_read_lock_nesting == 0 &&
	    unlikely((ACCESS_ONCE(t->rcu_read_unlock_special)))

This prevents the compiler from reordering because the ACCESS_ONCE() prohibits accessing t->rcu_read_unlock_special unless the value of t->rcu_read_lock_nesting is known to be zero.

Quoted 3 lines

We might need to audit
TREE PREEMPT RCU for the same kind of behavior.

The version of __rcu_read_unlock() in kernel/rcutree_plugin.h is as follows:

void __rcu_read_unlock(void)

{
	struct task_struct *t = current;

	barrier();  /* needed if we ever invoke rcu_read_unlock in rcutree.c */
	if (--ACCESS_ONCE(t->rcu_read_lock_nesting) == 0 &&
	    unlikely(ACCESS_ONCE(t->rcu_read_unlock_special)))

		rcu_read_unlock_special(t);
#ifdef CONFIG_PROVE_LOCKING
	WARN_ON_ONCE(ACCESS_ONCE(t->rcu_read_lock_nesting) < 0);

#endif /* #ifdef CONFIG_PROVE_LOCKING */
}

The ACCESS_ONCE() calls should cover this. I believe that the first ACCESS_ONCE() is redundant, and have checking this more closely on my todo list.

Quoted 20 lines

But I might be (again ?) missing something. I've got the feeling you already convinced me that this was OK for some reason, but I trip on this every time I read the code.

[...]

Quoted 13 lines

kernel/rcutiny_plugin.h +13 -0

+/*
+ * Check for a task exiting while in a preemptible -RCU read-side
+ * critical section, clean up if so.  No need to issue warnings,
+ * as debug_check_no_locks_held() already does this if lockdep
+ * is enabled.
+ */
+void exit_rcu(void)
+{
+	struct task_struct *t = current;
+
+	if (t->rcu_read_lock_nesting == 0)
+		return;
+	t->rcu_read_lock_nesting = 1;

Quoted 8 lines

kernel/rcutiny_plugin.h line 570

Quoted 3 lines

kernel/rcutiny_plugin.h +3 -0

+	rcu_read_unlock();
+}
+

The interaction with preemption is unclear here. exit.c disables preemption around the call to exit_rcu(), but if, for some reason, rcu_read_unlock_special was set earlier by preemption, then the rcu_read_unlock() code might block and cause problems.

But rcu_read_unlock_special() does not block. In fact, it disables interrupts over almost all of its execution. Or am I missing some subtlety here?

Quoted 2 lines

Maybe we should consider clearing rcu_read_unlock_special here ?

If the task blocked in an RCU read-side critical section just before exit_rcu() was called, we need to remove the task from the ->blkd_tasks list. If we fail to do so, we might get a segfault later on. Also, we do need to handle any RCU_READ_UNLOCK_NEED_QS requests from the RCU core.

So I really do like the current approach of calling rcu_read_unlock() to do this sort of cleanup.

Thanx, Paul

Quoted 14 lines

Thanks,

Mathieu

Signature · 9 lines

Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Quoted 50 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 17 lines · Mathieu Desnoyers

* Paul E. McKenney ([email protected]) wrote:
[...]

Quoted 5 lines

kernel/rcutiny_plugin.h +5 -0

+
+/*
+ * Tiny-preemptible RCU implementation for rcu_read_unlock().
+ * Decrement ->rcu_read_lock_nesting.  If the result is zero (outermost
+ * rcu_read_unlock()) and ->rcu_read_unlock_special is non-zero, then

kernel/rcutiny_plugin.h line 354

Quoted 10 lines

kernel/rcutiny_plugin.h +10 -0

+ * invoke rcu_read_unlock_special() to clean up after a context switch
+ * in an RCU read-side critical section and other special cases.
+ */
+void __rcu_read_unlock(void)
+{
+	struct task_struct *t = current;
+
+	barrier();  /* needed if we ever invoke rcu_read_unlock in rcutiny.c */
+	if (--t->rcu_read_lock_nesting == 0 &&
+	    unlikely(t->rcu_read_unlock_special))

First, thank you for looking this over!!!

Quoted 14 lines

Hrm I think we discussed this in a past life, but would the following sequence be possible and correct ?

CPU 0

read t->rcu_read_unlock_special
interrupt comes in, preempts. sets t->rcu_read_unlock_special <preempted>
<scheduled back>
iret
decrement and read t->rcu_read_lock_nesting
test both old "special" value (which we have locally on the stack) and detect that rcu_read_lock_nesting is 0.

Quoted 4 lines

We actually missed a reschedule.

I think we might need a barrier() between the t->rcu_read_lock_nesting and t->rcu_read_unlock_special reads.

You are correct -- I got too aggressive in eliminating synchronization.

Good catch!!!

I added an ACCESS_ONCE() to the second term of the "if" condition so that it now reads:

	if (--t->rcu_read_lock_nesting == 0 &&
	    unlikely((ACCESS_ONCE(t->rcu_read_unlock_special)))

Quoted 3 lines

This prevents the compiler from reordering because the ACCESS_ONCE() prohibits accessing t->rcu_read_unlock_special unless the value of t->rcu_read_lock_nesting is known to be zero.

Hrm, --t->rcu_read_lock_nesting does not have any globally visible side-effect, so the compiler is free to reorder the memory access across the rcu_read_unlock_special access. I think we need the ACCESS_ONCE() around the t->rcu_read_lock_nesting access too.

Quoted 6 lines

Quoted 2 lines

We might need to audit
TREE PREEMPT RCU for the same kind of behavior.

The version of __rcu_read_unlock() in kernel/rcutree_plugin.h is as follows:

Quoted 7 lines

void __rcu_read_unlock(void)

{
	struct task_struct *t = current;

	barrier();  /* needed if we ever invoke rcu_read_unlock in rcutree.c */
	if (--ACCESS_ONCE(t->rcu_read_lock_nesting) == 0 &&
	    unlikely(ACCESS_ONCE(t->rcu_read_unlock_special)))

This seem to work because we have:

volatile access (read/update t->rcu_read_lock_nesting) && (sequence point)
volatile access (t->rcu_read_unlock_special)

The C standard seems to forbid reordering of volatile accesses across sequence points, so this should be fine. But it would probably be good to document this implied ordering explicitly.

Quoted 9 lines

		rcu_read_unlock_special(t);
#ifdef CONFIG_PROVE_LOCKING
	WARN_ON_ONCE(ACCESS_ONCE(t->rcu_read_lock_nesting) < 0);

#endif /* #ifdef CONFIG_PROVE_LOCKING */
}

The ACCESS_ONCE() calls should cover this. I believe that the first ACCESS_ONCE() is redundant, and have checking this more closely on my todo list.

I doubt so, see explanation above.

Quoted 28 lines

Quoted 19 lines

But I might be (again ?) missing something. I've got the feeling you already convinced me that this was OK for some reason, but I trip on this every time I read the code.

[...]

Quoted 13 lines

kernel/rcutiny_plugin.h +13 -0

+/*
+ * Check for a task exiting while in a preemptible -RCU read-side
+ * critical section, clean up if so.  No need to issue warnings,
+ * as debug_check_no_locks_held() already does this if lockdep
+ * is enabled.
+ */
+void exit_rcu(void)
+{
+	struct task_struct *t = current;
+
+	if (t->rcu_read_lock_nesting == 0)
+		return;
+	t->rcu_read_lock_nesting = 1;

Quoted 8 lines

kernel/rcutiny_plugin.h line 570

Quoted 3 lines

kernel/rcutiny_plugin.h +3 -0

+	rcu_read_unlock();
+}
+

The interaction with preemption is unclear here. exit.c disables preemption around the call to exit_rcu(), but if, for some reason, rcu_read_unlock_special was set earlier by preemption, then the rcu_read_unlock() code might block and cause problems.

Quoted 3 lines

But rcu_read_unlock_special() does not block. In fact, it disables interrupts over almost all of its execution. Or am I missing some subtlety here?

I am probably the one who was missing a subtlety about how rcu_read_unlock_special() works.

Quoted 9 lines

Quoted 2 lines

Maybe we should consider clearing rcu_read_unlock_special here ?

If the task blocked in an RCU read-side critical section just before exit_rcu() was called, we need to remove the task from the ->blkd_tasks list. If we fail to do so, we might get a segfault later on. Also, we do need to handle any RCU_READ_UNLOCK_NEED_QS requests from the RCU core.

Quoted 2 lines

So I really do like the current approach of calling rcu_read_unlock() to do this sort of cleanup.

It looks good then, I just wanted to ensure that the side-effects of calling rcu_read_unlock() in this code path were well-thought.

Quoted 55 lines · Mathieu Desnoyers

Quoted 53 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 17 lines · Mathieu Desnoyers

* Paul E. McKenney ([email protected]) wrote:
[...]

Quoted 5 lines

kernel/rcutiny_plugin.h +5 -0

+
+/*
+ * Tiny-preemptible RCU implementation for rcu_read_unlock().
+ * Decrement ->rcu_read_lock_nesting.  If the result is zero (outermost
+ * rcu_read_unlock()) and ->rcu_read_unlock_special is non-zero, then

kernel/rcutiny_plugin.h line 354

Quoted 10 lines

kernel/rcutiny_plugin.h +10 -0

+ * invoke rcu_read_unlock_special() to clean up after a context switch
+ * in an RCU read-side critical section and other special cases.
+ */
+void __rcu_read_unlock(void)
+{
+	struct task_struct *t = current;
+
+	barrier();  /* needed if we ever invoke rcu_read_unlock in rcutiny.c */
+	if (--t->rcu_read_lock_nesting == 0 &&
+	    unlikely(t->rcu_read_unlock_special))

First, thank you for looking this over!!!

Quoted 14 lines

Hrm I think we discussed this in a past life, but would the following sequence be possible and correct ?

CPU 0

read t->rcu_read_unlock_special
interrupt comes in, preempts. sets t->rcu_read_unlock_special <preempted>
<scheduled back>
iret
decrement and read t->rcu_read_lock_nesting
test both old "special" value (which we have locally on the stack) and detect that rcu_read_lock_nesting is 0.

Quoted 4 lines

We actually missed a reschedule.

I think we might need a barrier() between the t->rcu_read_lock_nesting and t->rcu_read_unlock_special reads.

You are correct -- I got too aggressive in eliminating synchronization.

Good catch!!!

I added an ACCESS_ONCE() to the second term of the "if" condition so that it now reads:

	if (--t->rcu_read_lock_nesting == 0 &&
	    unlikely((ACCESS_ONCE(t->rcu_read_unlock_special)))

This prevents the compiler from reordering because the ACCESS_ONCE() prohibits accessing t->rcu_read_unlock_special unless the value of t->rcu_read_lock_nesting is known to be zero.

Quoted 4 lines

Hrm, --t->rcu_read_lock_nesting does not have any globally visible side-effect, so the compiler is free to reorder the memory access across the rcu_read_unlock_special access. I think we need the ACCESS_ONCE() around the t->rcu_read_lock_nesting access too.

Indeed, it is free to reorder that access. This has the effect of extending the scope of the RCU read-side critical section, which is harmless as long as it doesn't pull a lock or some such into it.

Quoted 56 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 55 lines · Mathieu Desnoyers

Quoted 53 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 17 lines · Mathieu Desnoyers

* Paul E. McKenney ([email protected]) wrote:
[...]

Quoted 5 lines

kernel/rcutiny_plugin.h +5 -0

+
+/*
+ * Tiny-preemptible RCU implementation for rcu_read_unlock().
+ * Decrement ->rcu_read_lock_nesting.  If the result is zero (outermost
+ * rcu_read_unlock()) and ->rcu_read_unlock_special is non-zero, then

kernel/rcutiny_plugin.h line 354

Quoted 10 lines

kernel/rcutiny_plugin.h +10 -0

+ * invoke rcu_read_unlock_special() to clean up after a context switch
+ * in an RCU read-side critical section and other special cases.
+ */
+void __rcu_read_unlock(void)
+{
+	struct task_struct *t = current;
+
+	barrier();  /* needed if we ever invoke rcu_read_unlock in rcutiny.c */
+	if (--t->rcu_read_lock_nesting == 0 &&
+	    unlikely(t->rcu_read_unlock_special))

First, thank you for looking this over!!!

Quoted 14 lines

Hrm I think we discussed this in a past life, but would the following sequence be possible and correct ?

CPU 0

read t->rcu_read_unlock_special
interrupt comes in, preempts. sets t->rcu_read_unlock_special <preempted>
<scheduled back>
iret
decrement and read t->rcu_read_lock_nesting
test both old "special" value (which we have locally on the stack) and detect that rcu_read_lock_nesting is 0.

Quoted 4 lines

We actually missed a reschedule.

I think we might need a barrier() between the t->rcu_read_lock_nesting and t->rcu_read_unlock_special reads.

You are correct -- I got too aggressive in eliminating synchronization.

Good catch!!!

I added an ACCESS_ONCE() to the second term of the "if" condition so that it now reads:

	if (--t->rcu_read_lock_nesting == 0 &&
	    unlikely((ACCESS_ONCE(t->rcu_read_unlock_special)))

This prevents the compiler from reordering because the ACCESS_ONCE() prohibits accessing t->rcu_read_unlock_special unless the value of t->rcu_read_lock_nesting is known to be zero.

Quoted 9 lines

Quoted 4 lines

Hrm, --t->rcu_read_lock_nesting does not have any globally visible side-effect, so the compiler is free to reorder the memory access across the rcu_read_unlock_special access. I think we need the ACCESS_ONCE() around the t->rcu_read_lock_nesting access too.

Indeed, it is free to reorder that access. This has the effect of extending the scope of the RCU read-side critical section, which is harmless as long as it doesn't pull a lock or some such into it.

So what happens if we get:

CPU 0

read t->rcu_read_lock_nesting
check if equals to 1
read t->rcu_read_unlock_special
interrupt comes in, preempts. sets t->rcu_read_unlock_special <preempted>
<scheduled back>
iret
decrement t->rcu_read_lock_nesting

test rcu_read_unlock_special value (read prior to interrupt)
-> fails to notice the preemption that came in after the
rcu_read_unlock_special read.

Thanks,

Mathieu

Signature · 4 lines

Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

Quoted 71 lines · Mathieu Desnoyers

Quoted 56 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 55 lines · Mathieu Desnoyers

Quoted 53 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 17 lines · Mathieu Desnoyers

* Paul E. McKenney ([email protected]) wrote:
[...]

Quoted 5 lines

(quoted diff) +5 -0

+
+/*
+ * Tiny-preemptible RCU implementation for rcu_read_unlock().
+ * Decrement ->rcu_read_lock_nesting.  If the result is zero (outermost
+ * rcu_read_unlock()) and ->rcu_read_unlock_special is non-zero, then

Review

Quoted 10 lines

(quoted diff) +10 -0

+ * invoke rcu_read_unlock_special() to clean up after a context switch
+ * in an RCU read-side critical section and other special cases.
+ */
+void __rcu_read_unlock(void)
+{
+	struct task_struct *t = current;
+
+	barrier();  /* needed if we ever invoke rcu_read_unlock in rcutiny.c */
+	if (--t->rcu_read_lock_nesting == 0 &&
+	    unlikely(t->rcu_read_unlock_special))

First, thank you for looking this over!!!

Quoted 14 lines

Hrm I think we discussed this in a past life, but would the following sequence be possible and correct ?

CPU 0

read t->rcu_read_unlock_special
interrupt comes in, preempts. sets t->rcu_read_unlock_special <preempted>
<scheduled back>
iret
decrement and read t->rcu_read_lock_nesting
test both old "special" value (which we have locally on the stack) and detect that rcu_read_lock_nesting is 0.

Quoted 4 lines

We actually missed a reschedule.

I think we might need a barrier() between the t->rcu_read_lock_nesting and t->rcu_read_unlock_special reads.

You are correct -- I got too aggressive in eliminating synchronization.

Good catch!!!

I added an ACCESS_ONCE() to the second term of the "if" condition so that it now reads:

	if (--t->rcu_read_lock_nesting == 0 &&
	    unlikely((ACCESS_ONCE(t->rcu_read_unlock_special)))

This prevents the compiler from reordering because the ACCESS_ONCE() prohibits accessing t->rcu_read_unlock_special unless the value of t->rcu_read_lock_nesting is known to be zero.

Quoted 9 lines

Quoted 4 lines

Hrm, --t->rcu_read_lock_nesting does not have any globally visible side-effect, so the compiler is free to reorder the memory access across the rcu_read_unlock_special access. I think we need the ACCESS_ONCE() around the t->rcu_read_lock_nesting access too.

Indeed, it is free to reorder that access. This has the effect of extending the scope of the RCU read-side critical section, which is harmless as long as it doesn't pull a lock or some such into it.

So what happens if we get:

CPU 0

Quoted 8 lines

read t->rcu_read_lock_nesting
check if equals to 1
read t->rcu_read_unlock_special
interrupt comes in, preempts. sets t->rcu_read_unlock_special <preempted>
<scheduled back>
iret
decrement t->rcu_read_lock_nesting

Moving this down past the check of t->rcu_read_lock_special (which is now covered by ACCESS_ONCE()) would violate the C standard, as it would be equivalent to moving a volatile up past a sequence point.

Thanx, Paul

Quoted 13 lines

test rcu_read_unlock_special value (read prior to interrupt)
-> fails to notice the preemption that came in after the
rcu_read_unlock_special read.

Thanks,

Mathieu

Signature · 4 lines

Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

Quoted 81 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 71 lines · Mathieu Desnoyers

Quoted 56 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 55 lines · Mathieu Desnoyers

Quoted 53 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 17 lines · Mathieu Desnoyers

* Paul E. McKenney ([email protected]) wrote:
[...]

Quoted 5 lines

(quoted diff) +5 -0

+
+/*
+ * Tiny-preemptible RCU implementation for rcu_read_unlock().
+ * Decrement ->rcu_read_lock_nesting.  If the result is zero (outermost
+ * rcu_read_unlock()) and ->rcu_read_unlock_special is non-zero, then

Review

Quoted 10 lines

(quoted diff) +10 -0

+ * invoke rcu_read_unlock_special() to clean up after a context switch
+ * in an RCU read-side critical section and other special cases.
+ */
+void __rcu_read_unlock(void)
+{
+	struct task_struct *t = current;
+
+	barrier();  /* needed if we ever invoke rcu_read_unlock in rcutiny.c */
+	if (--t->rcu_read_lock_nesting == 0 &&
+	    unlikely(t->rcu_read_unlock_special))

First, thank you for looking this over!!!

Quoted 14 lines

Hrm I think we discussed this in a past life, but would the following sequence be possible and correct ?

CPU 0

read t->rcu_read_unlock_special
interrupt comes in, preempts. sets t->rcu_read_unlock_special <preempted>
<scheduled back>
iret
decrement and read t->rcu_read_lock_nesting
test both old "special" value (which we have locally on the stack) and detect that rcu_read_lock_nesting is 0.

Quoted 4 lines

We actually missed a reschedule.

I think we might need a barrier() between the t->rcu_read_lock_nesting and t->rcu_read_unlock_special reads.

You are correct -- I got too aggressive in eliminating synchronization.

Good catch!!!

I added an ACCESS_ONCE() to the second term of the "if" condition so that it now reads:

	if (--t->rcu_read_lock_nesting == 0 &&
	    unlikely((ACCESS_ONCE(t->rcu_read_unlock_special)))

This prevents the compiler from reordering because the ACCESS_ONCE() prohibits accessing t->rcu_read_unlock_special unless the value of t->rcu_read_lock_nesting is known to be zero.

Quoted 9 lines

Quoted 4 lines

Hrm, --t->rcu_read_lock_nesting does not have any globally visible side-effect, so the compiler is free to reorder the memory access across the rcu_read_unlock_special access. I think we need the ACCESS_ONCE() around the t->rcu_read_lock_nesting access too.

Indeed, it is free to reorder that access. This has the effect of extending the scope of the RCU read-side critical section, which is harmless as long as it doesn't pull a lock or some such into it.

So what happens if we get:

CPU 0

Quoted 8 lines

read t->rcu_read_lock_nesting
check if equals to 1
read t->rcu_read_unlock_special
interrupt comes in, preempts. sets t->rcu_read_unlock_special <preempted>
<scheduled back>
iret
decrement t->rcu_read_lock_nesting

Quoted 3 lines

Moving this down past the check of t->rcu_read_lock_special (which is now covered by ACCESS_ONCE()) would violate the C standard, as it would be equivalent to moving a volatile up past a sequence point.

Hrm, I'm not quite convinced yet. I am not concerned about gcc moving the volatile access prior to the sequence point (as you say, this is forbidden by the C standard), but rather that:

--(t->rcu_read_lock_nesting)

could be split in two distinct operations:

read t->rcu_read_lock_nesting
decrement t->rcu_read_lock_nesting

Note that in order to know the result required to pass the sequence point "&&" (the test), we only need to perform the read, not the decrement. AFAIU, gcc would be in its rights to move the t->rcu_read_lock_nesting update after the volatile access.

Quoted 7 lines

--(t->rcu_read_lock_nesting)

could be split in two distinct operations:

read t->rcu_read_lock_nesting
decrement t->rcu_read_lock_nesting

Quoted 4 lines

Note that in order to know the result required to pass the sequence point "&&" (the test), we only need to perform the read, not the decrement. AFAIU, gcc would be in its rights to move the t->rcu_read_lock_nesting update after the volatile access.

I will run this by some compiler experts.

Quoted 12 lines · Paul E. McKenney

Quoted 11 lines

--(t->rcu_read_lock_nesting)

could be split in two distinct operations:

read t->rcu_read_lock_nesting
decrement t->rcu_read_lock_nesting

Note that in order to know the result required to pass the sequence point "&&" (the test), we only need to perform the read, not the decrement. AFAIU, gcc would be in its rights to move the t->rcu_read_lock_nesting update after the volatile access.

Quoted 1 line

I will run this by some compiler experts.

We can just use "read and decrement statements" instead of "--" to avoid dependency from compilers.

Quoted 3 lines

Moving this down past the check of t->rcu_read_lock_special (which is now covered by ACCESS_ONCE()) would violate the C standard, as it would be equivalent to moving a volatile up past a sequence point.

Hrm, I'm not quite convinced yet. I am not concerned about gcc moving the volatile access prior to the sequence point (as you say, this is forbidden by the C standard), but rather that:

--(t->rcu_read_lock_nesting)

could be split in two distinct operations:

read t->rcu_read_lock_nesting
decrement t->rcu_read_lock_nesting

Note that in order to know the result required to pass the sequence point "&&" (the test), we only need to perform the read, not the decrement. AFAIU, gcc would be in its rights to move the t->rcu_read_lock_nesting update after the volatile access.

Quoted 12 lines · Mathieu Desnoyers

Quoted 3 lines

Moving this down past the check of t->rcu_read_lock_special (which is now covered by ACCESS_ONCE()) would violate the C standard, as it would be equivalent to moving a volatile up past a sequence point.

Hrm, I'm not quite convinced yet. I am not concerned about gcc moving the volatile access prior to the sequence point (as you say, this is forbidden by the C standard), but rather that:

--(t->rcu_read_lock_nesting)

could be split in two distinct operations:

Quoted 8 lines

read t->rcu_read_lock_nesting
decrement t->rcu_read_lock_nesting

Note that in order to know the result required to pass the sequence point "&&" (the test), we only need to perform the read, not the decrement. AFAIU, gcc would be in its rights to move the t->rcu_read_lock_nesting update after the volatile access.

If we are this concerned, what about just doing:

	--t->rcu_read_lock_nesting;
        if (ACCESS_ONCE(t->rcu_read_lock_nesting) == 0 &&
             unlikely((ACCESS_ONCE(t->rcu_read_unlock_special)))

-- Steve

Quoted 5 lines · * Steven Rostedt ([email protected]) wrote:

If we are this concerned, what about just doing:

	--t->rcu_read_lock_nesting;
        if (ACCESS_ONCE(t->rcu_read_lock_nesting) == 0 &&
             unlikely((ACCESS_ONCE(t->rcu_read_unlock_special)))

I'd be concerned by the fact that there is no strong ordering guarantee that the non-volatile --t->rcu_read_lock_nesting is done before ACCESS_ONCE(t->rcu_read_unlock_special).

My concern is that the compiler might be allowed to turn your code into:

        if (ACCESS_ONCE(t->rcu_read_lock_nesting) == 1 &&
             unlikely((ACCESS_ONCE(t->rcu_read_unlock_special))) {
 		--t->rcu_read_lock_nesting;
		do_something();
	} else
	 	--t->rcu_read_lock_nesting;

So whether or not this could be done by the compiler depending on the various definitions of volatile, I strongly recommend against using volatile accesses to provide compiler ordering guarantees. It is bad in terms of code documentation (we don't document _what_ is ordered) and it is also bad because the volatile ordering guarantees seems to be very easy to misinterpret.

ACCESS_ONCE() should be only that: a macro that tells the access should be performed only once. Why are we suddenly presuming it should have any ordering semantic ?

It should be totally valid to create arch-specific ACCESS_ONCE() macros that only perform the "read once", without the ordering guarantees provided by the current ACCESS_ONCE() "volatile" implementation. The following code is only for unsigned long, but you get the idea: there is no volatile at all, and I ensure that "val" is only read once by using the "+m" (val) constraint, telling the compiler (falsely) that the assembler is modifying the value (it therefore has a side-effect), so gcc won't be tempted to re-issue the assembly statement.

static inline unsigned long arch_access_once(unsigned long val)

{
	unsigned long ret;

#if (__BITS_PER_LONG == 32)
	asm ("movl %1,%0": "=r" (ret), "+m" (val));
#else
	asm ("movq %1,%0": "=r" (ret), "+m" (val));

#endif
}

Quoted 12 lines · Mathieu Desnoyers

Quoted 5 lines · * Steven Rostedt ([email protected]) wrote:

If we are this concerned, what about just doing:

	--t->rcu_read_lock_nesting;
        if (ACCESS_ONCE(t->rcu_read_lock_nesting) == 0 &&
             unlikely((ACCESS_ONCE(t->rcu_read_unlock_special)))

I'd be concerned by the fact that there is no strong ordering guarantee that the non-volatile --t->rcu_read_lock_nesting is done before ACCESS_ONCE(t->rcu_read_unlock_special).

Quoted 8 lines

My concern is that the compiler might be allowed to turn your code into:

        if (ACCESS_ONCE(t->rcu_read_lock_nesting) == 1 &&
             unlikely((ACCESS_ONCE(t->rcu_read_unlock_special))) {
 		--t->rcu_read_lock_nesting;
		do_something();
	} else
	 	--t->rcu_read_lock_nesting;

That just seems to break all sorts of rules.

Quoted 8 lines

So whether or not this could be done by the compiler depending on the various definitions of volatile, I strongly recommend against using volatile accesses to provide compiler ordering guarantees. It is bad in terms of code documentation (we don't document _what_ is ordered) and it is also bad because the volatile ordering guarantees seems to be very easy to misinterpret.

Yes, volatile does not guarantee ordering of other accesses, but it should at least guarantee ordering of access to the thing that is volatile.

	b++;
	a++;
	c = ACCESS_ONCE(a);

'b++' can be moved to anywhere. But I'm pretty sure the compiler is not allowed to move the 'a++' after the ACCESS_ONCE(a) because it is the thing that is volatile.

We are telling the compiler that 'a' can change outside our scope, which to me is the same as doing:

	a++;
	c = some_global_function(&a);

Where, the compiler does not know the result of 'a' and can not move the 'a++'.

Maybe I'm wrong, and need to verify this with a compiler expert. But what's the use of volatile if it can't protect the ordering of what is volatile from itself.

Quoted 5 lines

ACCESS_ONCE() should be only that: a macro that tells the access should be performed only once. Why are we suddenly presuming it should have any ordering semantic ?

Only ordering with the variable that is volatile. It has no ordering to any other variable.

Quoted 15 lines

It should be totally valid to create arch-specific ACCESS_ONCE() macros that only perform the "read once", without the ordering guarantees provided by the current ACCESS_ONCE() "volatile" implementation. The following code is only for unsigned long, but you get the idea: there is no volatile at all, and I ensure that "val" is only read once by using the "+m" (val) constraint, telling the compiler (falsely) that the assembler is modifying the value (it therefore has a side-effect), so gcc won't be tempted to re-issue the assembly statement.

static inline unsigned long arch_access_once(unsigned long val)

{
	unsigned long ret;

Quoted 6 lines

#if (__BITS_PER_LONG == 32)
	asm ("movl %1,%0": "=r" (ret), "+m" (val));
#else
	asm ("movq %1,%0": "=r" (ret), "+m" (val));

#endif
}

Heck, this is too much micro optimization. We could just be safe and do the:

 	--t->rcu_read_lock_nesting;
	barrier();
         if (ACCESS_ONCE(t->rcu_read_lock_nesting) == 0 &&
              unlikely((ACCESS_ONCE(t->rcu_read_unlock_special)))

And be done with it.

-- Steve

Quoted 7 lines

Heck, this is too much micro optimization. We could just be safe and do the:

 	--t->rcu_read_lock_nesting;
	barrier();
         if (ACCESS_ONCE(t->rcu_read_lock_nesting) == 0 &&
              unlikely((ACCESS_ONCE(t->rcu_read_unlock_special)))

Quoted 1 line

And be done with it.

Then we could go for the simpler:

--t->rcu_read_lock_nesting;

 	barrier();
        if (t->rcu_read_lock_nesting == 0 &&
             unlikely((t->rcu_read_unlock_special))

Which puts a constraint across all memory accesses. I'd be fine with that if you are afraid of too much micro-optimization (e.g. my barrier2(a, b) proposal).

Quoted 6 lines

Then we could go for the simpler:

--t->rcu_read_lock_nesting;

 	barrier();
        if (t->rcu_read_lock_nesting == 0 &&
             unlikely((t->rcu_read_unlock_special))

Yeah, that's what I meant, I was too lazy to remove the ACCESS_ONCE() from the cut and paste I did.

Quoted 1 line

Quoted 3 lines

Which puts a constraint across all memory accesses. I'd be fine with that if you are afraid of too much micro-optimization (e.g. my barrier2(a, b) proposal).

Not afraid, but just too much code for a simple solution.

Quoted 15 lines · Steven Rostedt

Quoted 6 lines

Then we could go for the simpler:

--t->rcu_read_lock_nesting;

 	barrier();
        if (t->rcu_read_lock_nesting == 0 &&
             unlikely((t->rcu_read_unlock_special))

Yeah, that's what I meant, I was too lazy to remove the ACCESS_ONCE() from the cut and paste I did.

Quoted 4 lines

Which puts a constraint across all memory accesses. I'd be fine with that if you are afraid of too much micro-optimization (e.g. my barrier2(a, b) proposal).

Quoted 1 line

Not afraid, but just too much code for a simple solution.

IOW,

I think just pulling out the '--' and adding the barrier() is the proper solution here. Compiler barriers are rather cheap.

Can we all agree on this solution?

Quoted 24 lines · * Steven Rostedt ([email protected]) wrote:

Quoted 11 lines · Steven Rostedt

Quoted 6 lines

Then we could go for the simpler:

--t->rcu_read_lock_nesting;

 	barrier();
        if (t->rcu_read_lock_nesting == 0 &&
             unlikely((t->rcu_read_unlock_special))

Yeah, that's what I meant, I was too lazy to remove the ACCESS_ONCE() from the cut and paste I did.

Quoted 1 line

Quoted 5 lines

Quoted 3 lines

Which puts a constraint across all memory accesses. I'd be fine with that if you are afraid of too much micro-optimization (e.g. my barrier2(a, b) proposal).

Not afraid, but just too much code for a simple solution.

IOW,

I think just pulling out the '--' and adding the barrier() is the proper solution here. Compiler barriers are rather cheap.

Quoted 1 line

Can we all agree on this solution?

Given that we already have a barrier() at the beginning of rcu_read_unlock(), adding a second one will not have much more global optimisation impact than what is already there. I'm personally fine with this solution. Let's see what others have to say about this.

Quoted 27 lines · Mathieu Desnoyers

Quoted 25 lines · * Steven Rostedt ([email protected]) wrote:

Quoted 11 lines · Steven Rostedt

Quoted 6 lines

Then we could go for the simpler:

--t->rcu_read_lock_nesting;

 	barrier();
        if (t->rcu_read_lock_nesting == 0 &&
             unlikely((t->rcu_read_unlock_special))

Yeah, that's what I meant, I was too lazy to remove the ACCESS_ONCE() from the cut and paste I did.

Quoted 1 line

Quoted 5 lines

Quoted 3 lines

Which puts a constraint across all memory accesses. I'd be fine with that if you are afraid of too much micro-optimization (e.g. my barrier2(a, b) proposal).

Not afraid, but just too much code for a simple solution.

IOW,

I think just pulling out the '--' and adding the barrier() is the proper solution here. Compiler barriers are rather cheap.

Can we all agree on this solution?

Quoted 4 lines

Given that we already have a barrier() at the beginning of rcu_read_unlock(), adding a second one will not have much more global optimisation impact than what is already there. I'm personally fine with this solution. Let's see what others have to say about this.

Thank you both for the optimization work -- the read-side primitives do need to be fast. And the barrier() approach generates decent code, on some systems better than the original. So the second barrier wins. ;-)

The comment says that blocking is illegal in rcu_read_lock()-style RCU read-side critical sections, which is no longer entirely true given preemptible RCU. This commit provides a fix.

Suggested-by David Miller <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

---
 include/linux/rcupdate.h |   15 ++++++++++++++-
 1 files changed, 14 insertions(+), 1 deletions(-)

include/linux/rcupdate.h +4 -1

index 24b8966..d7af96e 100644
@@ -458,7 +458,20 @@ extern int rcu_my_thread_group_empty(void);
  * will be deferred until the outermost RCU read-side critical section
  * completes.
  *
- * It is illegal to block while in an RCU read-side critical section.
+ * You can avoid reading and understanding the next paragraph by
+ * following this rule: don't put anything in an rcu_read_lock() RCU
+ * read-side critical section that would block in a !PREEMPT kernel.
+ * But if you want the full story, read on!

include/linux/rcupdate.h +0 -0

  */
 static inline void rcu_read_lock(void)
 {

Signature · 1 line

1.7.0.6

Quoted 23 lines · * Paul E. McKenney ([email protected]) wrote:

The comment says that blocking is illegal in rcu_read_lock()-style RCU read-side critical sections, which is no longer entirely true given preemptible RCU. This commit provides a fix.

Suggested-by David Miller <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

---
 include/linux/rcupdate.h |   15 ++++++++++++++-
 1 files changed, 14 insertions(+), 1 deletions(-)

include/linux/rcupdate.h +4 -1

index 24b8966..d7af96e 100644
@@ -458,7 +458,20 @@ extern int rcu_my_thread_group_empty(void);
  * will be deferred until the outermost RCU read-side critical section
  * completes.
  *
- * It is illegal to block while in an RCU read-side critical section.
+ * You can avoid reading and understanding the next paragraph by
+ * following this rule: don't put anything in an rcu_read_lock() RCU
+ * read-side critical section that would block in a !PREEMPT kernel.
+ * But if you want the full story, read on!

include/linux/rcupdate.h extern int rcu_my_thread_group_empty(void); · line 474

Quoted 10 lines

include/linux/rcupdate.h +10 -0

+ *
+ * In non-preemptible RCU implementations (TREE_RCU and TINY_RCU), it
+ * is illegal to block while in an RCU read-side critical section.  In
+ * preemptible RCU implementations (TREE_PREEMPT_RCU and TINY_PREEMPT_RCU)
+ * in CONFIG_PREEMPT kernel builds, RCU read-side critical sections may
+ * be preempted, but explicit blocking is illegal.  Finally, in preemptible
+ * RCU implementations in real-time (CONFIG_PREEMPT_RT) kernel builds,
+ * RCU read-side critical sections may be preempted and they may also
+ * block, but only when acquiring spinlocks that are subject to priority
+ * inheritance.

It might be good to add a note about locking chain dependency that is created in the RT case, e.g., the lock we are sharing with another context in preempt RT is subject to the same rules as the RCU C.S.. It should never call synchronize_rcu(); this would cause a RCU+lock-induced deadlock.

I must admit, however, that because calling synchronize_rcu() from spinlocks is already forbidden, this is already implied.

Thanks,

Mathieu

Quoted 6 lines

include/linux/rcupdate.h +0 -0

  */
 static inline void rcu_read_lock(void)
 {

Signature · 1 line

1.7.0.6

Signature · 4 lines

Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

Quoted 41 lines · Mathieu Desnoyers

Quoted 23 lines · * Paul E. McKenney ([email protected]) wrote:

The comment says that blocking is illegal in rcu_read_lock()-style RCU read-side critical sections, which is no longer entirely true given preemptible RCU. This commit provides a fix.

Suggested-by David Miller <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

---
 include/linux/rcupdate.h |   15 ++++++++++++++-
 1 files changed, 14 insertions(+), 1 deletions(-)

include/linux/rcupdate.h +4 -1

index 24b8966..d7af96e 100644
@@ -458,7 +458,20 @@ extern int rcu_my_thread_group_empty(void);
  * will be deferred until the outermost RCU read-side critical section
  * completes.
  *
- * It is illegal to block while in an RCU read-side critical section.
+ * You can avoid reading and understanding the next paragraph by
+ * following this rule: don't put anything in an rcu_read_lock() RCU
+ * read-side critical section that would block in a !PREEMPT kernel.
+ * But if you want the full story, read on!

include/linux/rcupdate.h extern int rcu_my_thread_group_empty(void); · line 474

Quoted 10 lines

include/linux/rcupdate.h +10 -0

+ *
+ * In non-preemptible RCU implementations (TREE_RCU and TINY_RCU), it
+ * is illegal to block while in an RCU read-side critical section.  In
+ * preemptible RCU implementations (TREE_PREEMPT_RCU and TINY_PREEMPT_RCU)
+ * in CONFIG_PREEMPT kernel builds, RCU read-side critical sections may
+ * be preempted, but explicit blocking is illegal.  Finally, in preemptible
+ * RCU implementations in real-time (CONFIG_PREEMPT_RT) kernel builds,
+ * RCU read-side critical sections may be preempted and they may also
+ * block, but only when acquiring spinlocks that are subject to priority
+ * inheritance.

It might be good to add a note about locking chain dependency that is created in the RT case, e.g., the lock we are sharing with another context in preempt RT is subject to the same rules as the RCU C.S.. It should never call synchronize_rcu(); this would cause a RCU+lock-induced deadlock.

Quoted 2 lines

I must admit, however, that because calling synchronize_rcu() from spinlocks is already forbidden, this is already implied.

Thank you for looking this over!

I am updating the srcu_read_lock() docbook comments to call out the potential for this problem, given that SRCU read-side critical sections can acquire mutexes, which can be held across both synchronize_srcu() and synchronize_srcu_expedited().

Seem reasonable?

Thanx, Paul

include/linux/srcu.h +6 -1

index 6f456a7..58971e8 100644
@@ -139,7 +139,12 @@ static inline int srcu_read_lock_held(struct srcu_struct *sp)
  * @sp: srcu_struct in which to register the new reader.
  *
  * Enter an SRCU read-side critical section.  Note that SRCU read-side
- * critical sections may be nested.
+ * critical sections may be nested.  However, it is illegal to
+ * call anything that waits on an SRCU grace period for the same
+ * srcu_struct, whether directly or indirectly.  Please note that
+ * one way to indirectly wait on an SRCU grace period is to acquire
+ * a mutex that is held elsewhere while calling synchronize_srcu() or
+ * synchronize_srcu_expedited().
  */
 static inline int srcu_read_lock(struct srcu_struct *sp) __acquires(sp)
 {

Quoted 17 lines

Thanks,

Mathieu

Quoted 6 lines

include/linux/rcupdate.h +0 -0

  */
 static inline void rcu_read_lock(void)
 {

Signature · 1 line

1.7.0.6

Signature · 4 lines

Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com