Skip to contentSkip to conversation

spin_unlock_wait and assorted borkage

RFC PATCH NAK Peter Zijlstra 9 participants 40 messages May 24, 2016 – Jun 7, 2016 2 messages not in the archive

Subsystems (7)
lore
Share & tools
lore

Peter Zijlstra

author maintainer
#0 lore raw

cover spin_unlock_wait and assorted borkage

As per recent discussions spin_unlock_wait() has an unintuitive 'feature'.

lkml.kernel.org/r/[email protected]

These patches pull the existing solution into generic code; annotate all spin_unlock_wait() users and fix nf_conntrack more.

The alternative -- putting smp_acquire__after_ctrl_dep() into spin_unlock_wait() can be done later if desired, now that al users are audited and corrected.

Please (very) carefully consider.

author maintainer
#1 lore raw

RFC PATCH 1/3 locking: Introduce smp_acquire__after_ctrl_dep

Introduce smp_acquire__after_ctrl_dep(), this construct is not uncommen, but the lack of this barrier is.

---
 include/linux/compiler.h |   14 ++++++++++----
 ipc/sem.c                |   14 ++------------
 2 files changed, 12 insertions(+), 16 deletions(-)
include/linux/compiler.h +10 -4
@@ -305,20 +305,26 @@ static __always_inline void __write_once
 })
 
 /**
+ * smp_acquire__after_ctrl_dep() - Provide ACQUIRE ordering after a control dependency
+ *
+ * A control dependency provides a LOAD->STORE order, the additional RMB
+ * provides LOAD->LOAD order, together they provide LOAD->{LOAD,STORE} order,
+ * aka. ACQUIRE.
+ */
+#define smp_acquire__after_ctrl_dep()		smp_rmb()
+
+/**
  * smp_cond_acquire() - Spin wait for cond with ACQUIRE ordering
  * @cond: boolean expression to wait for
  *
  * Equivalent to using smp_load_acquire() on the condition variable but employs
  * the control dependency of the wait to reduce the barrier on many platforms.
  *
- * The control dependency provides a LOAD->STORE order, the additional RMB
- * provides LOAD->LOAD order, together they provide LOAD->{LOAD,STORE} order,
- * aka. ACQUIRE.
  */
 #define smp_cond_acquire(cond)	do {		\
 	while (!(cond))				\
 		cpu_relax();			\
-	smp_rmb(); /* ctrl + rmb := acquire */	\
+	smp_acquire__after_ctrl_dep();		\
 } while (0)
 
 #endif /* __KERNEL__ */
ipc/sem.c +2 -12
@@ -260,16 +260,6 @@ static void sem_rcu_free(struct rcu_head
 }
 
 /*
- * spin_unlock_wait() and !spin_is_locked() are not memory barriers, they
- * are only control barriers.
- * The code must pair with spin_unlock(&sem->lock) or
- * spin_unlock(&sem_perm.lock), thus just the control barrier is insufficient.
- *
- * smp_rmb() is sufficient, as writes cannot pass the control barrier.
- */
-#define ipc_smp_acquire__after_spin_is_unlocked()	smp_rmb()
-
-/*
  * Wait until all currently ongoing simple ops have completed.
  * Caller must own sem_perm.lock.
  * New simple ops cannot start, because simple ops first check
@@ -292,7 +282,7 @@ static void sem_wait_array(struct sem_ar
 		sem = sma->sem_base + i;
 		spin_unlock_wait(&sem->lock);
 	}
-	ipc_smp_acquire__after_spin_is_unlocked();
+	smp_acquire__after_ctrl_dep();
 }
 
 /*
@@ -350,7 +340,7 @@ static inline int sem_lock(struct sem_ar
 			 *	complex_count++;
 			 *	spin_unlock(sem_perm.lock);
 			 */
-			ipc_smp_acquire__after_spin_is_unlocked();
+			smp_acquire__after_ctrl_dep();
 
 			/*
 			 * Now repeat the test of complex_count:

A message that is not in the archive (sent off-list or not yet received): [email protected]

#3 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

Quoted 47 lines · Waiman Long
Quoted 32 lines · Peter Zijlstra

Introduce smp_acquire__after_ctrl_dep(), this construct is not uncommen, but the lack of this barrier is.

---
 include/linux/compiler.h |   14 ++++++++++----
 ipc/sem.c                |   14 ++------------
 2 files changed, 12 insertions(+), 16 deletions(-)
include/linux/compiler.h +9 -2
@@ -305,20 +305,26 @@ static __always_inline void __write_once
 })
 
 /**
+ * smp_acquire__after_ctrl_dep() - Provide ACQUIRE ordering after a control dependency
+ *
+ * A control dependency provides a LOAD->STORE order, the additional RMB
+ * provides LOAD->LOAD order, together they provide LOAD->{LOAD,STORE} order,
+ * aka. ACQUIRE.
+ */
+#define smp_acquire__after_ctrl_dep()		smp_rmb()
+
+/**
  * smp_cond_acquire() - Spin wait for cond with ACQUIRE ordering
  * @cond: boolean expression to wait for
  *
  * Equivalent to using smp_load_acquire() on the condition variable but employs
  * the control dependency of the wait to reduce the barrier on many platforms.
  *
- * The control dependency provides a LOAD->STORE order, the additional RMB
- * provides LOAD->LOAD order, together they provide LOAD->{LOAD,STORE} order,

include/linux/compiler.h static __always_inline void __write_once · line 330

Quoted 10 lines
include/linux/compiler.h +1 -2
- * aka. ACQUIRE.
  */
 #define smp_cond_acquire(cond)	do {		\
 	while (!(cond))				\
 		cpu_relax();			\
-	smp_rmb(); /* ctrl + rmb := acquire */	\
+	smp_acquire__after_ctrl_dep();		\
 } while (0)
 
 

I have a question about the claim that control dependence + rmb is equivalent to an acquire memory barrier. For example,

Quoted 7 lines
S1:    if (a)
S2:       b = 1;
       smp_rmb()

S3: c = 2;

Since c is independent of both a and b, is it possible that the cpu may reorder to execute store statement S3 first before S1 and S2?

The CPUs I know of won't do, nor should the compiler, at least assuming "a" (AKA "cond") includes READ_ONCE(). Ditto "b" and WRITE_ONCE(). Otherwise, the compiler could do quite a few "interesting" things, especially if it knows the value of "b". For example, if the compiler knows that b==1, without the volatile casts, the compiler could just throw away both S1 and S2, eliminating any ordering. This can get quite tricky -- see memory-barriers.txt for more mischief.

The smp_rmb() is not needed in this example because S3 is a write, not a read. Perhaps you meant something more like this:

	if (READ_ONCE(a))
		WRITE_ONCE(b, 1);
	smp_rmb();
	r1 = READ_ONCE(c);

This sequence would guarantee that "a" was read before "c".

Thanx, Paul

#4 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

Quoted 64 lines · Paul E. McKenney
Quoted 47 lines · Waiman Long
Quoted 32 lines · Peter Zijlstra

Introduce smp_acquire__after_ctrl_dep(), this construct is not uncommen, but the lack of this barrier is.

---
 include/linux/compiler.h |   14 ++++++++++----
 ipc/sem.c                |   14 ++------------
 2 files changed, 12 insertions(+), 16 deletions(-)
include/linux/compiler.h +9 -2
@@ -305,20 +305,26 @@ static __always_inline void __write_once
 })
 
 /**
+ * smp_acquire__after_ctrl_dep() - Provide ACQUIRE ordering after a control dependency
+ *
+ * A control dependency provides a LOAD->STORE order, the additional RMB
+ * provides LOAD->LOAD order, together they provide LOAD->{LOAD,STORE} order,
+ * aka. ACQUIRE.
+ */
+#define smp_acquire__after_ctrl_dep()		smp_rmb()
+
+/**
  * smp_cond_acquire() - Spin wait for cond with ACQUIRE ordering
  * @cond: boolean expression to wait for
  *
  * Equivalent to using smp_load_acquire() on the condition variable but employs
  * the control dependency of the wait to reduce the barrier on many platforms.
  *
- * The control dependency provides a LOAD->STORE order, the additional RMB
- * provides LOAD->LOAD order, together they provide LOAD->{LOAD,STORE} order,

include/linux/compiler.h static __always_inline void __write_once · line 330

Quoted 10 lines
include/linux/compiler.h +1 -2
- * aka. ACQUIRE.
  */
 #define smp_cond_acquire(cond)	do {		\
 	while (!(cond))				\
 		cpu_relax();			\
-	smp_rmb(); /* ctrl + rmb := acquire */	\
+	smp_acquire__after_ctrl_dep();		\
 } while (0)
 
 

I have a question about the claim that control dependence + rmb is equivalent to an acquire memory barrier. For example,

Quoted 7 lines
S1:    if (a)
S2:       b = 1;
       smp_rmb()

S3: c = 2;

Since c is independent of both a and b, is it possible that the cpu may reorder to execute store statement S3 first before S1 and S2?

The CPUs I know of won't do, nor should the compiler, at least assuming "a" (AKA "cond") includes READ_ONCE(). Ditto "b" and WRITE_ONCE(). Otherwise, the compiler could do quite a few "interesting" things, especially if it knows the value of "b". For example, if the compiler knows that b==1, without the volatile casts, the compiler could just throw away both S1 and S2, eliminating any ordering. This can get quite tricky -- see memory-barriers.txt for more mischief.

Quoted 1 line

The smp_rmb() is not needed in this example because S3 is a write, not

but S3 needs to be an WRITE_ONCE(), right? IOW, the following code can result in reordering:

S1: if (READ_ONCE(a))
S2: WRITE_ONCE(b, 1);

S3: c = 2; // this can be reordered before READ_ONCE(a)

but if we change S3 to WRITE_ONCE(c, 2), the reordering can not happen for the CPUs you are aware of, right?

Regards,
Boqun

Quoted 11 lines

a read. Perhaps you meant something more like this:

	if (READ_ONCE(a))
		WRITE_ONCE(b, 1);
	smp_rmb();
	r1 = READ_ONCE(c);

This sequence would guarantee that "a" was read before "c".

Thanx, Paul

#5 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

Quoted 70 lines · Boqun Feng
Quoted 64 lines · Paul E. McKenney
Quoted 47 lines · Waiman Long
Quoted 32 lines · Peter Zijlstra

Introduce smp_acquire__after_ctrl_dep(), this construct is not uncommen, but the lack of this barrier is.

---
 include/linux/compiler.h |   14 ++++++++++----
 ipc/sem.c                |   14 ++------------
 2 files changed, 12 insertions(+), 16 deletions(-)
include/linux/compiler.h +9 -2
@@ -305,20 +305,26 @@ static __always_inline void __write_once
 })
 
 /**
+ * smp_acquire__after_ctrl_dep() - Provide ACQUIRE ordering after a control dependency
+ *
+ * A control dependency provides a LOAD->STORE order, the additional RMB
+ * provides LOAD->LOAD order, together they provide LOAD->{LOAD,STORE} order,
+ * aka. ACQUIRE.
+ */
+#define smp_acquire__after_ctrl_dep()		smp_rmb()
+
+/**
  * smp_cond_acquire() - Spin wait for cond with ACQUIRE ordering
  * @cond: boolean expression to wait for
  *
  * Equivalent to using smp_load_acquire() on the condition variable but employs
  * the control dependency of the wait to reduce the barrier on many platforms.
  *
- * The control dependency provides a LOAD->STORE order, the additional RMB
- * provides LOAD->LOAD order, together they provide LOAD->{LOAD,STORE} order,

include/linux/compiler.h static __always_inline void __write_once · line 330

Quoted 10 lines
include/linux/compiler.h +1 -2
- * aka. ACQUIRE.
  */
 #define smp_cond_acquire(cond)	do {		\
 	while (!(cond))				\
 		cpu_relax();			\
-	smp_rmb(); /* ctrl + rmb := acquire */	\
+	smp_acquire__after_ctrl_dep();		\
 } while (0)
 
 

I have a question about the claim that control dependence + rmb is equivalent to an acquire memory barrier. For example,

Quoted 7 lines
S1:    if (a)
S2:       b = 1;
       smp_rmb()

S3: c = 2;

Since c is independent of both a and b, is it possible that the cpu may reorder to execute store statement S3 first before S1 and S2?

The CPUs I know of won't do, nor should the compiler, at least assuming "a" (AKA "cond") includes READ_ONCE(). Ditto "b" and WRITE_ONCE(). Otherwise, the compiler could do quite a few "interesting" things, especially if it knows the value of "b". For example, if the compiler knows that b==1, without the volatile casts, the compiler could just throw away both S1 and S2, eliminating any ordering. This can get quite tricky -- see memory-barriers.txt for more mischief.

Quoted 1 line

The smp_rmb() is not needed in this example because S3 is a write, not

but S3 needs to be an WRITE_ONCE(), right? IOW, the following code can result in reordering:

Quoted 7 lines

S1: if (READ_ONCE(a))
S2: WRITE_ONCE(b, 1);

S3: c = 2; // this can be reordered before READ_ONCE(a)

but if we change S3 to WRITE_ONCE(c, 2), the reordering can not happen for the CPUs you are aware of, right?

Yes, if you remove the smp_rmb(), you also need a WRITE_ONCE() for S3.

Even with the smp_rmb(), you have to be careful.

In general, if you don't tell the compiler otherwise, it is within its rights to assume that nothing else is reading from or writing to the variables in question. That means that it can split and fuse loads and stores. Or keep some of the variables in registers, so that it never loads and stores them. ;-)

Thanx, Paul

Quoted 14 lines

Regards,
Boqun

Quoted 11 lines

a read. Perhaps you meant something more like this:

	if (READ_ONCE(a))
		WRITE_ONCE(b, 1);
	smp_rmb();
	r1 = READ_ONCE(c);

This sequence would guarantee that "a" was read before "c".

Thanx, Paul

#6 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

In reply to Paul E. McKenney
Quoted 65 lines · Paul E. McKenney
Quoted 46 lines · Waiman Long
Quoted 32 lines · Peter Zijlstra

Introduce smp_acquire__after_ctrl_dep(), this construct is not uncommen, but the lack of this barrier is.

---
  include/linux/compiler.h |   14 ++++++++++----
  ipc/sem.c                |   14 ++------------
  2 files changed, 12 insertions(+), 16 deletions(-)
include/linux/compiler.h +9 -2
@@ -305,20 +305,26 @@ static __always_inline void __write_once
  })
 
  /**
+ * smp_acquire__after_ctrl_dep() - Provide ACQUIRE ordering after a control dependency
+ *
+ * A control dependency provides a LOAD->STORE order, the additional RMB
+ * provides LOAD->LOAD order, together they provide LOAD->{LOAD,STORE} order,
+ * aka. ACQUIRE.
+ */
+#define smp_acquire__after_ctrl_dep()		smp_rmb()
+
+/**
   * smp_cond_acquire() - Spin wait for cond with ACQUIRE ordering
   * @cond: boolean expression to wait for
   *
   * Equivalent to using smp_load_acquire() on the condition variable but employs
   * the control dependency of the wait to reduce the barrier on many platforms.
   *
- * The control dependency provides a LOAD->STORE order, the additional RMB
- * provides LOAD->LOAD order, together they provide LOAD->{LOAD,STORE} order,

include/linux/compiler.h static __always_inline void __write_once · line 330

Quoted 10 lines
include/linux/compiler.h +1 -2
- * aka. ACQUIRE.
   */
  #define smp_cond_acquire(cond)	do {		\
  	while (!(cond))				\
  		cpu_relax();			\
-	smp_rmb(); /* ctrl + rmb := acquire */	\
+	smp_acquire__after_ctrl_dep();		\
  } while (0)
 
 

I have a question about the claim that control dependence + rmb is equivalent to an acquire memory barrier. For example,

Quoted 7 lines
S1:    if (a)
S2:       b = 1;
        smp_rmb()

S3: c = 2;

Since c is independent of both a and b, is it possible that the cpu may reorder to execute store statement S3 first before S1 and S2?

The CPUs I know of won't do, nor should the compiler, at least assuming "a" (AKA "cond") includes READ_ONCE(). Ditto "b" and WRITE_ONCE(). Otherwise, the compiler could do quite a few "interesting" things, especially if it knows the value of "b". For example, if the compiler knows that b==1, without the volatile casts, the compiler could just throw away both S1 and S2, eliminating any ordering. This can get quite tricky -- see memory-barriers.txt for more mischief.

The smp_rmb() is not needed in this example because S3 is a write, not a read. Perhaps you meant something more like this:

Quoted 9 lines
	if (READ_ONCE(a))
		WRITE_ONCE(b, 1);
	smp_rmb();
	r1 = READ_ONCE(c);

This sequence would guarantee that "a" was read before "c".

Thanx, Paul

The smp_rmb() in Linux should be a compiler barrier. So the compiler should not recorder it above smp_rmb. However, what I am wondering is whether a condition + rmb combination can be considered a real acquire memory barrier from the CPU point of view which requires that it cannot reorder the data store in S3 above S1 and S2. This is where I am not so sure about.

Cheers,
Longman

#7 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

Quoted 71 lines · Waiman Long
Quoted 70 lines · Paul E. McKenney
Quoted 46 lines · Waiman Long
Quoted 32 lines · Peter Zijlstra

Introduce smp_acquire__after_ctrl_dep(), this construct is not uncommen, but the lack of this barrier is.

---
 include/linux/compiler.h |   14 ++++++++++----
 ipc/sem.c                |   14 ++------------
 2 files changed, 12 insertions(+), 16 deletions(-)
include/linux/compiler.h +9 -2
@@ -305,20 +305,26 @@ static __always_inline void __write_once
 })
 
 /**
+ * smp_acquire__after_ctrl_dep() - Provide ACQUIRE ordering after a control dependency
+ *
+ * A control dependency provides a LOAD->STORE order, the additional RMB
+ * provides LOAD->LOAD order, together they provide LOAD->{LOAD,STORE} order,
+ * aka. ACQUIRE.
+ */
+#define smp_acquire__after_ctrl_dep()		smp_rmb()
+
+/**
  * smp_cond_acquire() - Spin wait for cond with ACQUIRE ordering
  * @cond: boolean expression to wait for
  *
  * Equivalent to using smp_load_acquire() on the condition variable but employs
  * the control dependency of the wait to reduce the barrier on many platforms.
  *
- * The control dependency provides a LOAD->STORE order, the additional RMB
- * provides LOAD->LOAD order, together they provide LOAD->{LOAD,STORE} order,

include/linux/compiler.h static __always_inline void __write_once · line 330

Quoted 10 lines
include/linux/compiler.h +1 -2
- * aka. ACQUIRE.
  */
 #define smp_cond_acquire(cond)	do {		\
 	while (!(cond))				\
 		cpu_relax();			\
-	smp_rmb(); /* ctrl + rmb := acquire */	\
+	smp_acquire__after_ctrl_dep();		\
 } while (0)
 
 

I have a question about the claim that control dependence + rmb is equivalent to an acquire memory barrier. For example,

Quoted 7 lines
S1:    if (a)
S2:       b = 1;
       smp_rmb()

S3: c = 2;

Since c is independent of both a and b, is it possible that the cpu may reorder to execute store statement S3 first before S1 and S2?

The CPUs I know of won't do, nor should the compiler, at least assuming "a" (AKA "cond") includes READ_ONCE(). Ditto "b" and WRITE_ONCE(). Otherwise, the compiler could do quite a few "interesting" things, especially if it knows the value of "b". For example, if the compiler knows that b==1, without the volatile casts, the compiler could just throw away both S1 and S2, eliminating any ordering. This can get quite tricky -- see memory-barriers.txt for more mischief.

The smp_rmb() is not needed in this example because S3 is a write, not a read. Perhaps you meant something more like this:

	if (READ_ONCE(a))
		WRITE_ONCE(b, 1);
	smp_rmb();
	r1 = READ_ONCE(c);
Quoted 8 lines
Quoted 1 line

This sequence would guarantee that "a" was read before "c".

The smp_rmb() in Linux should be a compiler barrier. So the compiler should not recorder it above smp_rmb. However, what I am wondering is whether a condition + rmb combination can be considered a real acquire memory barrier from the CPU point of view which requires that it cannot reorder the data store in S3 above S1 and S2. This is where I am not so sure about.

For your example, but keeping the compiler in check:

	if (READ_ONCE(a))
		WRITE_ONCE(b, 1);
	smp_rmb();
	WRITE_ONCE(c, 2);

On x86, the smp_rmb() is as you say nothing but barrier(). However, x86's TSO prohibits reordering reads with subsequent writes. So the read from "a" is ordered before the write to "c".

On powerpc, the smp_rmb() will be the lwsync instruction plus a compiler barrier. This orders prior reads against subsequent reads and writes, so again the read from "a" will be ordered befoer the write to "c". But the ordering against subsequent writes is an accident of implementation. The real guarantee comes from powerpc's guarantee that stores won't be speculated, so that the read from "a" is guaranteed to be ordered before the write to "c" even without the smp_rmb().

On arm, the smp_rmb() is a full memory barrier, so you are good there. On arm64, it is the "dmb ishld" instruction, which only orders reads. But in both arm and arm64, speculative stores are forbidden, just as in powerpc. So in both cases, the load from "a" is ordered before the store to "c".

Other CPUs are required to behave similarly, but hopefully those examples help.

But the READ_ONCE() and WRITE_ONCE() are critically important. The compiler is permitted to play all sorts of tricks if you have something like this:

	if (a)
		b = 1;
	smp_rmb();
	c = 2;

Here, the compiler is permitted to assume that no other CPU is either looking at or touching these variables. After all, you didn't tell it otherwise! (Another way of telling it otherwise is through use of atomics, as in David Howells's earlier patch.)

First, it might decide to place a, b, and c into registers for the duration. In that case, the compiler barrier has no effect, and the compiler is free to rearrange. (Yes, real compilers are probably more strict and thus more forgiving of this sort of thing. But they are under no obligation to forgive.)

Second, as noted earlier, the compiler might see an earlier load from or store to "b". If so, it is permitted to remember the value loaded or stored, and if that value happened to have been 1, the compiler is within its rights to drop the "if" statement completely, thus never loading "a" or storing to "b".

Finally, at least for this email, there is the possibility of load or store tearing.

Does that help?

Thanx, Paul

author maintainer
#8 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

Quoted 19 lines · Paul E. McKenney

For your example, but keeping the compiler in check:

	if (READ_ONCE(a))
		WRITE_ONCE(b, 1);
	smp_rmb();
	WRITE_ONCE(c, 2);

On x86, the smp_rmb() is as you say nothing but barrier(). However, x86's TSO prohibits reordering reads with subsequent writes. So the read from "a" is ordered before the write to "c".

On powerpc, the smp_rmb() will be the lwsync instruction plus a compiler barrier. This orders prior reads against subsequent reads and writes, so again the read from "a" will be ordered befoer the write to "c". But the ordering against subsequent writes is an accident of implementation. The real guarantee comes from powerpc's guarantee that stores won't be speculated, so that the read from "a" is guaranteed to be ordered before the write to "c" even without the smp_rmb().

Quoted 3 lines

On arm, the smp_rmb() is a full memory barrier, so you are good there. On arm64, it is the "dmb ishld" instruction, which only orders reads.

IIRC dmb ishld orders more than load vs load (like the manual states), but I forgot the details; we'll have to wait for Will to clarify. But yes, it also orders loads vs loads so it sufficient here.

Quoted 6 lines

But in both arm and arm64, speculative stores are forbidden, just as in powerpc. So in both cases, the load from "a" is ordered before the store to "c".

Other CPUs are required to behave similarly, but hopefully those examples help.

I would consider any architecture that allows speculative stores as broken. They are values out of thin air and would make any kind of concurrency extremely 'interesting'.

#9 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

Quoted 4 lines · Peter Zijlstra

I would consider any architecture that allows speculative stores as broken. They are values out of thin air and would make any kind of concurrency extremely 'interesting'.

It's worth noting that the same is true of compilers too. You will find compiler people who argue that speculative stores are valid because the spec doesn't explicitly forbid them. Same is true of compiler-generated value speculation.

Both are cases of "yeah, the C standard may not explicitly disallow it, but sanity in a threaded environment does". Sadly, I've seen compiler people who dismiss "sanity" as an argument, since that also isn't defined in the C standard. There are people who think that paper is the most precious resource in the universe.

I'm not actually aware of anybody doing speculative stores or value speculation in a compiler we care about, but if those kinds of things are the kinds of things where we'd just go "that compiler is shit" and not use it (possibly with a command line option to disable the particular broken optimization, like we do for the broken type-based aliasing and some other code generation things that just don't work in the kernel).

So we definitely have the option to just say "theory is just theory". We'll never make design decisions based on insane things being possible in theory, whether it be crazy architectures or crazy compilers.

Linus

#10 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

Quoted 10 lines · Linus Torvalds
Quoted 4 lines · Peter Zijlstra

I would consider any architecture that allows speculative stores as broken. They are values out of thin air and would make any kind of concurrency extremely 'interesting'.

It's worth noting that the same is true of compilers too. You will find compiler people who argue that speculative stores are valid because the spec doesn't explicitly forbid them. Same is true of compiler-generated value speculation.

Thankfully, this has improved. There was a time when compiler writers were happy to overwrite adjacent variables and fix them up later, believe it or not. Not so good if the variables are shared variables, possibly protected by different locks. Most compiler writers now understand that this sort of thing is not permitted, and recent versions of the standard explicitly forbid it.

But there are still any number of optimizations that can cause trouble for concurrent code. Common subexpresssion elimination, for example... Which is one reason for my heavy use of READ_ONCE() and WRITE_ONCE().

Quoted 14 lines

Both are cases of "yeah, the C standard may not explicitly disallow it, but sanity in a threaded environment does". Sadly, I've seen compiler people who dismiss "sanity" as an argument, since that also isn't defined in the C standard. There are people who think that paper is the most precious resource in the universe.

I'm not actually aware of anybody doing speculative stores or value speculation in a compiler we care about, but if those kinds of things are the kinds of things where we'd just go "that compiler is shit" and not use it (possibly with a command line option to disable the particular broken optimization, like we do for the broken type-based aliasing and some other code generation things that just don't work in the kernel).

Quoted 4 lines

So we definitely have the option to just say "theory is just theory". We'll never make design decisions based on insane things being possible in theory, whether it be crazy architectures or crazy compilers.

There has been some discussion of adding "-std=kernel" to tell the compiler to follow Linux-kernel rules, but not sure whether this is really going anywhere.

Thanx, Paul

#11 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

In reply to Paul E. McKenney
Quoted 19 lines · Paul E. McKenney

For your example, but keeping the compiler in check:

	if (READ_ONCE(a))
		WRITE_ONCE(b, 1);
	smp_rmb();
	WRITE_ONCE(c, 2);

On x86, the smp_rmb() is as you say nothing but barrier(). However, x86's TSO prohibits reordering reads with subsequent writes. So the read from "a" is ordered before the write to "c".

On powerpc, the smp_rmb() will be the lwsync instruction plus a compiler barrier. This orders prior reads against subsequent reads and writes, so again the read from "a" will be ordered befoer the write to "c". But the ordering against subsequent writes is an accident of implementation. The real guarantee comes from powerpc's guarantee that stores won't be speculated, so that the read from "a" is guaranteed to be ordered before the write to "c" even without the smp_rmb().

Quoted 8 lines

On arm, the smp_rmb() is a full memory barrier, so you are good there. On arm64, it is the "dmb ishld" instruction, which only orders reads. But in both arm and arm64, speculative stores are forbidden, just as in powerpc. So in both cases, the load from "a" is ordered before the store to "c".

Other CPUs are required to behave similarly, but hopefully those examples help.

Sorry for being late to the party - and apologies in advance for naive sounding questions below: just trying to put this into perspective for ARC.

Is speculative store same as reordering of stores or is it different/more/less ?

So with some form of MOESI, Core0 stores to line0 in Shared state (requiring a MOESI transactions to Core1) which could be deferred to the very next store to line1 in exclusive state. So the update of Core0 cache could be reorder and that in itself is fine (and probably happens all the time). Are we saying that the issue is if Core1 observes line1 write before line0, then arch is broken.

Ofcourse this specific example is too simple and impossible anyways. For Core1 to observe the line1 write will itself require another MOESI transaction which will naturally get behind the first one...

Am I on the right track !

-Vineet

author maintainer
#12 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

Quoted 7 lines · Vineet Gupta
Quoted 6 lines · Paul E. McKenney

For your example, but keeping the compiler in check:

	if (READ_ONCE(a))
		WRITE_ONCE(b, 1);
	smp_rmb();
	WRITE_ONCE(c, 2);

So I think it example is broken. The store to @c is not in fact dependent on the condition of @a.

Something that would match the text below would be:

	while (READ_ONCE(a))
		cpu_relax();
	smp_rmb();
	WRITE_ONCE(c, 2);
	t = READ_ONCE(d);

Where the smp_rmb() then ensures the load of "d" happens after the load of "a".

Quoted 18 lines
Quoted 18 lines

On x86, the smp_rmb() is as you say nothing but barrier(). However, x86's TSO prohibits reordering reads with subsequent writes. So the read from "a" is ordered before the write to "c".

On powerpc, the smp_rmb() will be the lwsync instruction plus a compiler barrier. This orders prior reads against subsequent reads and writes, so again the read from "a" will be ordered befoer the write to "c". But the ordering against subsequent writes is an accident of implementation. The real guarantee comes from powerpc's guarantee that stores won't be speculated, so that the read from "a" is guaranteed to be ordered before the write to "c" even without the smp_rmb().

On arm, the smp_rmb() is a full memory barrier, so you are good there. On arm64, it is the "dmb ishld" instruction, which only orders reads. But in both arm and arm64, speculative stores are forbidden, just as in powerpc. So in both cases, the load from "a" is ordered before the store to "c".

Quoted 7 lines
Quoted 2 lines

Other CPUs are required to behave similarly, but hopefully those examples help.

Sorry for being late to the party - and apologies in advance for naive sounding questions below: just trying to put this into perspective for ARC.

Is speculative store same as reordering of stores or is it different/more/less ?

Different, speculative stores are making stores visible that might not happen. For example, the branch the store is in will not be taken after all.

Take Paul's example, if !a but we see b==1 at any point, something is busted.

So while a core can speculate on the write in so far as that it might pull the line into exclusive mode, the actual modification must never be visible until such time that the branch is decided.

#13 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

Quoted 11 lines · Peter Zijlstra
Quoted 7 lines · Vineet Gupta
Quoted 6 lines · Paul E. McKenney

For your example, but keeping the compiler in check:

	if (READ_ONCE(a))
		WRITE_ONCE(b, 1);
	smp_rmb();
	WRITE_ONCE(c, 2);

So I think it example is broken. The store to @c is not in fact dependent on the condition of @a.

At first glance, the compiler could pull the write to "c" above the conditional, but the "memory" constraint in smp_rmb() prevents this.

Quoted 1 line

From a hardware viewpoint, the write to "c" does depend on the "if",

as the conditional branch does precede that write in execution order.

But yes, this is using smp_rmb() in a very strange way, if that is what you are getting at.

Quoted 10 lines

Something that would match the text below would be:

	while (READ_ONCE(a))
		cpu_relax();
	smp_rmb();
	WRITE_ONCE(c, 2);
	t = READ_ONCE(d);

Where the smp_rmb() then ensures the load of "d" happens after the load of "a".

I agree that this is a more natural example.

Quoted 30 lines
Quoted 18 lines
Quoted 18 lines

On x86, the smp_rmb() is as you say nothing but barrier(). However, x86's TSO prohibits reordering reads with subsequent writes. So the read from "a" is ordered before the write to "c".

On powerpc, the smp_rmb() will be the lwsync instruction plus a compiler barrier. This orders prior reads against subsequent reads and writes, so again the read from "a" will be ordered befoer the write to "c". But the ordering against subsequent writes is an accident of implementation. The real guarantee comes from powerpc's guarantee that stores won't be speculated, so that the read from "a" is guaranteed to be ordered before the write to "c" even without the smp_rmb().

On arm, the smp_rmb() is a full memory barrier, so you are good there. On arm64, it is the "dmb ishld" instruction, which only orders reads. But in both arm and arm64, speculative stores are forbidden, just as in powerpc. So in both cases, the load from "a" is ordered before the store to "c".

Quoted 7 lines
Quoted 2 lines

Other CPUs are required to behave similarly, but hopefully those examples help.

Sorry for being late to the party - and apologies in advance for naive sounding questions below: just trying to put this into perspective for ARC.

Is speculative store same as reordering of stores or is it different/more/less ?

Different, speculative stores are making stores visible that might not happen. For example, the branch the store is in will not be taken after all.

Quoted 6 lines

Take Paul's example, if !a but we see b==1 at any point, something is busted.

So while a core can speculate on the write in so far as that it might pull the line into exclusive mode, the actual modification must never be visible until such time that the branch is decided.

It could even modify the cacheline ahead of time, but if it does do so, it needs to be prepared to undo that modification if its speculation is wrong, and it needs to carefully avoid letting any other CPU see the modification unless/until the speculation proves correct. And "any other CPU" includes other hardware threads within that same core!

Some implementations of hardware transactional memory do this sort of tentative speculative store into their own cache.

Thanx, Paul

author maintainer
#14 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

Quoted 13 lines · Paul E. McKenney
Quoted 11 lines · Peter Zijlstra
Quoted 7 lines · Vineet Gupta
Quoted 6 lines · Paul E. McKenney

For your example, but keeping the compiler in check:

	if (READ_ONCE(a))
		WRITE_ONCE(b, 1);
	smp_rmb();
	WRITE_ONCE(c, 2);

So I think it example is broken. The store to @c is not in fact dependent on the condition of @a.

Quoted 7 lines

At first glance, the compiler could pull the write to "c" above the conditional, but the "memory" constraint in smp_rmb() prevents this. From a hardware viewpoint, the write to "c" does depend on the "if", as the conditional branch does precede that write in execution order.

But yes, this is using smp_rmb() in a very strange way, if that is what you are getting at.

Well, the CPU could decide that the store to C happens either way around the branch. I'm not sure I'd rely on CPUs not being _that_ clever.

	test	%a, $0
	jnz	1f
	mov	$1, %b

1: mov $2, %c

Its not too much to ask the CPU to look ahead 2 instructions to figure out the store into c is going to happen unconditionally.

I would really only rely on stores immediately dependent on the conditional.

author maintainer
#15 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

Quoted 28 lines · Peter Zijlstra
Quoted 13 lines · Paul E. McKenney
Quoted 11 lines · Peter Zijlstra
Quoted 7 lines · Vineet Gupta
Quoted 6 lines · Paul E. McKenney

For your example, but keeping the compiler in check:

	if (READ_ONCE(a))
		WRITE_ONCE(b, 1);
	smp_rmb();
	WRITE_ONCE(c, 2);

So I think it example is broken. The store to @c is not in fact dependent on the condition of @a.

Quoted 7 lines

At first glance, the compiler could pull the write to "c" above the conditional, but the "memory" constraint in smp_rmb() prevents this. From a hardware viewpoint, the write to "c" does depend on the "if", as the conditional branch does precede that write in execution order.

But yes, this is using smp_rmb() in a very strange way, if that is what you are getting at.

Well, the CPU could decide that the store to C happens either way around the branch. I'm not sure I'd rely on CPUs not being _that_ clever.

	test	%a, $0
	jnz	1f
	mov	$1, %b
Quoted 7 lines

1: mov $2, %c

Its not too much to ask the CPU to look ahead 2 instructions to figure out the store into c is going to happen unconditionally.

I would really only rely on stores immediately dependent on the conditional.

Ah, interrupts could observe the difference, which is your execution order constraint. So yes, maybe.

I'm still rather hesitant on this.

#16 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

Quoted 34 lines · Peter Zijlstra
Quoted 33 lines · Peter Zijlstra
Quoted 13 lines · Paul E. McKenney
Quoted 11 lines · Peter Zijlstra
Quoted 7 lines · Vineet Gupta
Quoted 6 lines · Paul E. McKenney

For your example, but keeping the compiler in check:

	if (READ_ONCE(a))
		WRITE_ONCE(b, 1);
	smp_rmb();
	WRITE_ONCE(c, 2);

So I think it example is broken. The store to @c is not in fact dependent on the condition of @a.

Quoted 7 lines

At first glance, the compiler could pull the write to "c" above the conditional, but the "memory" constraint in smp_rmb() prevents this. From a hardware viewpoint, the write to "c" does depend on the "if", as the conditional branch does precede that write in execution order.

But yes, this is using smp_rmb() in a very strange way, if that is what you are getting at.

Well, the CPU could decide that the store to C happens either way around the branch. I'm not sure I'd rely on CPUs not being _that_ clever.

	test	%a, $0
	jnz	1f
	mov	$1, %b

1: mov $2, %c

Its not too much to ask the CPU to look ahead 2 instructions to figure out the store into c is going to happen unconditionally.

Quoted 7 lines
Quoted 2 lines

I would really only rely on stores immediately dependent on the conditional.

Ah, interrupts could observe the difference, which is your execution order constraint. So yes, maybe.

I'm still rather hesitant on this.

Any info on Itanium? Again, I am reasonably sure that Power and ARM architectures guarantee to avoid excess cleverness on the part of the CPU in this case.

Thanx, Paul

#17 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

In reply to Peter Zijlstra
Quoted 19 lines · Peter Zijlstra
Quoted 18 lines · Paul E. McKenney
Quoted 11 lines · Peter Zijlstra
Quoted 7 lines · Vineet Gupta
Quoted 6 lines · Paul E. McKenney

For your example, but keeping the compiler in check:

	if (READ_ONCE(a))
		WRITE_ONCE(b, 1);
	smp_rmb();
	WRITE_ONCE(c, 2);

So I think it example is broken. The store to @c is not in fact dependent on the condition of @a.

At first glance, the compiler could pull the write to "c" above the conditional, but the "memory" constraint in smp_rmb() prevents this. From a hardware viewpoint, the write to "c" does depend on the "if", as the conditional branch does precede that write in execution order.

Quoted 5 lines
Quoted 2 lines

But yes, this is using smp_rmb() in a very strange way, if that is what you are getting at.

Well, the CPU could decide that the store to C happens either way around the branch. I'm not sure I'd rely on CPUs not being _that_ clever.

If I remember correctly, both Power and ARM guarantee that the CPU won't be that clever. Not sure about Itanium.

Quoted 10 lines
	test	%a, $0
	jnz	1f
	mov	$1, %b

1: mov $2, %c

Its not too much to ask the CPU to look ahead 2 instructions to figure out the store into c is going to happen unconditionally.

I would really only rely on stores immediately dependent on the conditional.

Given compiler tricks, a good choice.

Thanx, Paul

#18 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

Quoted 20 lines · Paul E. McKenney
Quoted 19 lines · Peter Zijlstra
Quoted 18 lines · Paul E. McKenney
Quoted 11 lines · Peter Zijlstra
Quoted 7 lines · Vineet Gupta
Quoted 6 lines · Paul E. McKenney

For your example, but keeping the compiler in check:

	if (READ_ONCE(a))
		WRITE_ONCE(b, 1);
	smp_rmb();
	WRITE_ONCE(c, 2);

So I think it example is broken. The store to @c is not in fact dependent on the condition of @a.

At first glance, the compiler could pull the write to "c" above the conditional, but the "memory" constraint in smp_rmb() prevents this. From a hardware viewpoint, the write to "c" does depend on the "if", as the conditional branch does precede that write in execution order.

Quoted 8 lines
Quoted 5 lines
Quoted 2 lines

But yes, this is using smp_rmb() in a very strange way, if that is what you are getting at.

Well, the CPU could decide that the store to C happens either way around the branch. I'm not sure I'd rely on CPUs not being _that_ clever.

If I remember correctly, both Power and ARM guarantee that the CPU won't be that clever. Not sure about Itanium.

I wouldn't be so sure about ARM. On 32-bit, at least, we have conditional store instructions so if the compiler could somehow use one of those for the first WRITE_ONCE then there's very obviously no control dependency on the second WRITE_ONCE and they could be observed out of order.

I note that smp_rmb() on ARM and arm64 actually orders against subsequent (in program order) writes, so this is still pretty theoretical for us.

Will

#19 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

Quoted 27 lines · Will Deacon
Quoted 26 lines · Paul E. McKenney
Quoted 24 lines · Peter Zijlstra
Quoted 13 lines · Paul E. McKenney
Quoted 11 lines · Peter Zijlstra
Quoted 7 lines · Vineet Gupta
Quoted 6 lines · Paul E. McKenney

For your example, but keeping the compiler in check:

	if (READ_ONCE(a))
		WRITE_ONCE(b, 1);
	smp_rmb();
	WRITE_ONCE(c, 2);

So I think it example is broken. The store to @c is not in fact dependent on the condition of @a.

Quoted 7 lines

At first glance, the compiler could pull the write to "c" above the conditional, but the "memory" constraint in smp_rmb() prevents this. From a hardware viewpoint, the write to "c" does depend on the "if", as the conditional branch does precede that write in execution order.

But yes, this is using smp_rmb() in a very strange way, if that is what you are getting at.

Well, the CPU could decide that the store to C happens either way around the branch. I'm not sure I'd rely on CPUs not being _that_ clever.

Quoted 7 lines
Quoted 2 lines

If I remember correctly, both Power and ARM guarantee that the CPU won't be that clever. Not sure about Itanium.

I wouldn't be so sure about ARM. On 32-bit, at least, we have conditional store instructions so if the compiler could somehow use one of those for the first WRITE_ONCE then there's very obviously no control dependency on the second WRITE_ONCE and they could be observed out of order.

OK, good to know...

Quoted 2 lines

I note that smp_rmb() on ARM and arm64 actually orders against subsequent (in program order) writes, so this is still pretty theoretical for us.

So the combined control-dependency/smp_rmb() still works, but I should re-examine the straight control dependency stuff.

Thanx, Paul

#20 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

Quoted 36 lines · Paul E. McKenney
Quoted 27 lines · Will Deacon
Quoted 26 lines · Paul E. McKenney
Quoted 24 lines · Peter Zijlstra
Quoted 13 lines · Paul E. McKenney
Quoted 11 lines · Peter Zijlstra
Quoted 7 lines · Vineet Gupta
Quoted 6 lines · Paul E. McKenney

For your example, but keeping the compiler in check:

	if (READ_ONCE(a))
		WRITE_ONCE(b, 1);
	smp_rmb();
	WRITE_ONCE(c, 2);

So I think it example is broken. The store to @c is not in fact dependent on the condition of @a.

Quoted 7 lines

At first glance, the compiler could pull the write to "c" above the conditional, but the "memory" constraint in smp_rmb() prevents this. From a hardware viewpoint, the write to "c" does depend on the "if", as the conditional branch does precede that write in execution order.

But yes, this is using smp_rmb() in a very strange way, if that is what you are getting at.

Well, the CPU could decide that the store to C happens either way around the branch. I'm not sure I'd rely on CPUs not being _that_ clever.

Quoted 7 lines
Quoted 2 lines

If I remember correctly, both Power and ARM guarantee that the CPU won't be that clever. Not sure about Itanium.

I wouldn't be so sure about ARM. On 32-bit, at least, we have conditional store instructions so if the compiler could somehow use one of those for the first WRITE_ONCE then there's very obviously no control dependency on the second WRITE_ONCE and they could be observed out of order.

Quoted 7 lines

OK, good to know...

Quoted 2 lines

I note that smp_rmb() on ARM and arm64 actually orders against subsequent (in program order) writes, so this is still pretty theoretical for us.

So the combined control-dependency/smp_rmb() still works, but I should re-examine the straight control dependency stuff.

And how about the patch below?

Thanx, Paul

------------------------------------------------------------------------

commit 43672d15aeb69b1a196c06cbc071cbade8d247fd

Author: Paul E. McKenney <[email protected]>
Date:   Mon Jun 6 10:19:42 2016 -0700

documentation: Clarify limited control-dependency scope

Nothing in the control-dependencies section of memory-barriers.txt says that control dependencies don't extend beyond the end of the if-statement containing the control dependency. Worse yet, in many situations, they do extend beyond that if-statement. In particular, the compiler cannot destroy the control dependency given proper use of READ_ONCE() and WRITE_ONCE(). However, a weakly ordered system having a conditional-move instruction provides the control-dependency guarantee only to code within the scope of the if-statement itself.

This commit therefore adds words and an example demonstrating this limitation of control dependencies.

Documentation/memory-barriers.txt +41 -0
index 147ae8ec836f..a4d0a99de04d 100644
@@ -806,6 +806,41 @@ out-guess your code.  More generally, although READ_ONCE() does force
 the compiler to actually emit code for a given load, it does not force
 the compiler to use the results.
 
+In addition, control dependencies apply only to the then-clause and
+else-clause of the if-statement in question.  In particular, it does
+not necessarily apply to code following the if-statement:
+
+	q = READ_ONCE(a);
+	if (q) {
+		WRITE_ONCE(b, p);
+	} else {
+		WRITE_ONCE(b, r);
+	}
+	WRITE_ONCE(c, 1);  /* BUG: No ordering against the read from "a". */
+
+It is tempting to argue that there in fact is ordering because the
+compiler cannot reorder volatile accesses and also cannot reorder
+the writes to "b" with the condition.  Unfortunately for this line
+of reasoning, the compiler might compile the two writes to "b" as
+conditional-move instructions, as in this fanciful pseudo-assembly
+language:
+
+	ld r1,a
+	ld r2,p
+	ld r3,r
+	cmp r1,$0
+	cmov,ne r4,r2
+	cmov,eq r4,r3
+	st r4,b
+	st $1,c
+
+A weakly ordered CPU would have no dependency of any sort between the load
+from "a" and the store to "c".  The control dependencies would extend
+only to the pair of cmov instructions and the store depending on them.
+In short, control dependencies apply only to the stores in the then-clause
+and else-clause of the if-statement in question (including functions
+invoked by those two clauses), not to code following that if-statement.
+
 Finally, control dependencies do -not- provide transitivity.  This is
 demonstrated by two related examples, with the initial values of
 x and y both being zero:
@@ -869,6 +904,12 @@ In summary:
       atomic{,64}_read() can help to preserve your control dependency.
       Please see the COMPILER BARRIER section for more information.
 
+  (*) Control dependencies apply only to the then-clause and else-clause
+      of the if-statement containing the control dependency, including
+      any functions that these two clauses call.  Control dependencies
+      do -not- apply to code following the if-statement containing the
+      control dependency.
+
   (*) Control dependencies pair normally with other types of barriers.
 
   (*) Control dependencies do -not- provide transitivity.  If you
author maintainer Acked-by
#21 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

Quoted 15 lines · Paul E. McKenney

commit 43672d15aeb69b1a196c06cbc071cbade8d247fd

Author: Paul E. McKenney <[email protected]>
Date:   Mon Jun 6 10:19:42 2016 -0700

documentation: Clarify limited control-dependency scope

Nothing in the control-dependencies section of memory-barriers.txt says that control dependencies don't extend beyond the end of the if-statement containing the control dependency. Worse yet, in many situations, they do extend beyond that if-statement. In particular, the compiler cannot destroy the control dependency given proper use of READ_ONCE() and WRITE_ONCE(). However, a weakly ordered system having a conditional-move instruction provides the control-dependency guarantee only to code within the scope of the if-statement itself.

Quoted 5 lines

This commit therefore adds words and an example demonstrating this limitation of control dependencies.

Quoted 61 lines
Documentation/memory-barriers.txt +41 -0
index 147ae8ec836f..a4d0a99de04d 100644
@@ -806,6 +806,41 @@ out-guess your code.  More generally, although READ_ONCE() does force
 the compiler to actually emit code for a given load, it does not force
 the compiler to use the results.
 
+In addition, control dependencies apply only to the then-clause and
+else-clause of the if-statement in question.  In particular, it does
+not necessarily apply to code following the if-statement:
+
+	q = READ_ONCE(a);
+	if (q) {
+		WRITE_ONCE(b, p);
+	} else {
+		WRITE_ONCE(b, r);
+	}
+	WRITE_ONCE(c, 1);  /* BUG: No ordering against the read from "a". */
+
+It is tempting to argue that there in fact is ordering because the
+compiler cannot reorder volatile accesses and also cannot reorder
+the writes to "b" with the condition.  Unfortunately for this line
+of reasoning, the compiler might compile the two writes to "b" as
+conditional-move instructions, as in this fanciful pseudo-assembly
+language:
+
+	ld r1,a
+	ld r2,p
+	ld r3,r
+	cmp r1,$0
+	cmov,ne r4,r2
+	cmov,eq r4,r3
+	st r4,b
+	st $1,c
+
+A weakly ordered CPU would have no dependency of any sort between the load
+from "a" and the store to "c".  The control dependencies would extend
+only to the pair of cmov instructions and the store depending on them.
+In short, control dependencies apply only to the stores in the then-clause
+and else-clause of the if-statement in question (including functions
+invoked by those two clauses), not to code following that if-statement.
+
 Finally, control dependencies do -not- provide transitivity.  This is
 demonstrated by two related examples, with the initial values of
 x and y both being zero:
@@ -869,6 +904,12 @@ In summary:
       atomic{,64}_read() can help to preserve your control dependency.
       Please see the COMPILER BARRIER section for more information.
 
+  (*) Control dependencies apply only to the then-clause and else-clause
+      of the if-statement containing the control dependency, including
+      any functions that these two clauses call.  Control dependencies
+      do -not- apply to code following the if-statement containing the
+      control dependency.
+
   (*) Control dependencies pair normally with other types of barriers.
 
   (*) Control dependencies do -not- provide transitivity.  If you
#22 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

Quoted 19 lines · Peter Zijlstra
Quoted 19 lines
Documentation/memory-barriers.txt +10 -0
index 147ae8ec836f..a4d0a99de04d 100644
@@ -806,6 +806,41 @@ out-guess your code.  More generally, although READ_ONCE() does force
 the compiler to actually emit code for a given load, it does not force
 the compiler to use the results.
 
+In addition, control dependencies apply only to the then-clause and
+else-clause of the if-statement in question.  In particular, it does
+not necessarily apply to code following the if-statement:
+
+	q = READ_ONCE(a);
+	if (q) {
+		WRITE_ONCE(b, p);
+	} else {
+		WRITE_ONCE(b, r);
+	}
Quoted 8 lines

Documentation/memory-barriers.txt out-guess your code. More generally, although READ_ONCE() does force · line 826

Quoted 8 lines
Documentation/memory-barriers.txt +8 -0
+	WRITE_ONCE(c, 1);  /* BUG: No ordering against the read from "a". */
+
+It is tempting to argue that there in fact is ordering because the
+compiler cannot reorder volatile accesses and also cannot reorder
+the writes to "b" with the condition.  Unfortunately for this line
+of reasoning, the compiler might compile the two writes to "b" as
+conditional-move instructions, as in this fanciful pseudo-assembly
+language:

I wonder if we already guarantee by kernel compiler settings that this behavior is not allowed by at least gcc.

We unconditionally set --param allow-store-data-races=0 which should actually prevent gcc from generating such conditional stores.

Am I seeing this correct here?

Thanks,
Hannes

#23 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

Quoted 32 lines · Hannes Frederic Sowa
Quoted 19 lines · Peter Zijlstra
Quoted 19 lines
Documentation/memory-barriers.txt +10 -0
index 147ae8ec836f..a4d0a99de04d 100644
@@ -806,6 +806,41 @@ out-guess your code.  More generally, although READ_ONCE() does force
 the compiler to actually emit code for a given load, it does not force
 the compiler to use the results.
 
+In addition, control dependencies apply only to the then-clause and
+else-clause of the if-statement in question.  In particular, it does
+not necessarily apply to code following the if-statement:
+
+	q = READ_ONCE(a);
+	if (q) {
+		WRITE_ONCE(b, p);
+	} else {
+		WRITE_ONCE(b, r);
+	}
Quoted 8 lines

Documentation/memory-barriers.txt out-guess your code. More generally, although READ_ONCE() does force · line 826

Quoted 8 lines
Documentation/memory-barriers.txt +8 -0
+	WRITE_ONCE(c, 1);  /* BUG: No ordering against the read from "a". */
+
+It is tempting to argue that there in fact is ordering because the
+compiler cannot reorder volatile accesses and also cannot reorder
+the writes to "b" with the condition.  Unfortunately for this line
+of reasoning, the compiler might compile the two writes to "b" as
+conditional-move instructions, as in this fanciful pseudo-assembly
+language:

I wonder if we already guarantee by kernel compiler settings that this behavior is not allowed by at least gcc.

Quoted 4 lines

We unconditionally set --param allow-store-data-races=0 which should actually prevent gcc from generating such conditional stores.

Am I seeing this correct here?

In this case, the store to "c" is unconditional, so pulling it forward would not generate a data race. However, the compiler is still prohibited from pulling it forward because it is not allowed to reorder volatile references. So, yes, the compiler cannot reorder, but for a different reason.

Some CPUs, on the other hand, can do this reordering, as Will Deacon pointed out earlier in this thread.

Thanx, Paul

#24 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

Quoted 38 lines · Paul E. McKenney
Quoted 32 lines · Hannes Frederic Sowa
Quoted 19 lines · Peter Zijlstra
Quoted 19 lines
Documentation/memory-barriers.txt +10 -0
index 147ae8ec836f..a4d0a99de04d 100644
@@ -806,6 +806,41 @@ out-guess your code.  More generally, although READ_ONCE() does force
 the compiler to actually emit code for a given load, it does not force
 the compiler to use the results.
 
+In addition, control dependencies apply only to the then-clause and
+else-clause of the if-statement in question.  In particular, it does
+not necessarily apply to code following the if-statement:
+
+	q = READ_ONCE(a);
+	if (q) {
+		WRITE_ONCE(b, p);
+	} else {
+		WRITE_ONCE(b, r);
+	}
Quoted 8 lines

Documentation/memory-barriers.txt out-guess your code. More generally, although READ_ONCE() does force · line 826

Quoted 8 lines
Documentation/memory-barriers.txt +8 -0
+	WRITE_ONCE(c, 1);  /* BUG: No ordering against the read from "a". */
+
+It is tempting to argue that there in fact is ordering because the
+compiler cannot reorder volatile accesses and also cannot reorder
+the writes to "b" with the condition.  Unfortunately for this line
+of reasoning, the compiler might compile the two writes to "b" as
+conditional-move instructions, as in this fanciful pseudo-assembly
+language:

I wonder if we already guarantee by kernel compiler settings that this behavior is not allowed by at least gcc.

Quoted 4 lines

We unconditionally set --param allow-store-data-races=0 which should actually prevent gcc from generating such conditional stores.

Am I seeing this correct here?

Quoted 8 lines

In this case, the store to "c" is unconditional, so pulling it forward would not generate a data race. However, the compiler is still prohibited from pulling it forward because it is not allowed to reorder volatile references. So, yes, the compiler cannot reorder, but for a different reason.

Some CPUs, on the other hand, can do this reordering, as Will Deacon pointed out earlier in this thread.

Sorry, to follow-up again on this. Will Deacon's comments were about conditional-move instructions, which this compiler-option would prevent, as far as I can see it. Thus I couldn't follow your answer completely:

The writes to b would be non-conditional-moves with a control dependency from a and and edge down to the write to c, which obviously is non-conditional. As such in terms of dependency ordering, we would have the control dependency always, thus couldn't we assume that in a current kernel we always have a load(a)->store(c) requirement?

Is there something else than conditional move instructions that could come to play here? Obviously a much smarter CPU could evaluate all the jumps and come to the conclusion that the write to c is never depending on the load from a, but is this implemented somewhere in hardware?

Thank you,
Hannes

#25 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

Quoted 45 lines · Hannes Frederic Sowa
Quoted 44 lines · Paul E. McKenney
Quoted 32 lines · Hannes Frederic Sowa
Quoted 19 lines · Peter Zijlstra
Quoted 19 lines
Documentation/memory-barriers.txt +10 -0
index 147ae8ec836f..a4d0a99de04d 100644
@@ -806,6 +806,41 @@ out-guess your code.  More generally, although READ_ONCE() does force
 the compiler to actually emit code for a given load, it does not force
 the compiler to use the results.
 
+In addition, control dependencies apply only to the then-clause and
+else-clause of the if-statement in question.  In particular, it does
+not necessarily apply to code following the if-statement:
+
+	q = READ_ONCE(a);
+	if (q) {
+		WRITE_ONCE(b, p);
+	} else {
+		WRITE_ONCE(b, r);
+	}
Quoted 8 lines

Documentation/memory-barriers.txt out-guess your code. More generally, although READ_ONCE() does force · line 826

Quoted 8 lines
Documentation/memory-barriers.txt +8 -0
+	WRITE_ONCE(c, 1);  /* BUG: No ordering against the read from "a". */
+
+It is tempting to argue that there in fact is ordering because the
+compiler cannot reorder volatile accesses and also cannot reorder
+the writes to "b" with the condition.  Unfortunately for this line
+of reasoning, the compiler might compile the two writes to "b" as
+conditional-move instructions, as in this fanciful pseudo-assembly
+language:

I wonder if we already guarantee by kernel compiler settings that this behavior is not allowed by at least gcc.

Quoted 4 lines

We unconditionally set --param allow-store-data-races=0 which should actually prevent gcc from generating such conditional stores.

Am I seeing this correct here?

In this case, the store to "c" is unconditional, so pulling it forward would not generate a data race. However, the compiler is still prohibited from pulling it forward because it is not allowed to reorder volatile references. So, yes, the compiler cannot reorder, but for a different reason.

Quoted 6 lines
Quoted 2 lines

Some CPUs, on the other hand, can do this reordering, as Will Deacon pointed out earlier in this thread.

Sorry, to follow-up again on this. Will Deacon's comments were about conditional-move instructions, which this compiler-option would prevent, as far as I can see it.

According to this email thread, I believe that this works the other way around:

http://thread.gmane.org/gmane.linux.kernel/1721993

That parameter prevents the compiler from converting a conditional store into an unconditional store, which would be really problematic. Give the current kernel build, I believe that the compiler really is within its rights to use conditional-move instructions as shown above. But I again must defer to Will Deacon on the details.

Or am I misinterpreting that email thread?

Quoted 7 lines

Thus I couldn't follow your answer completely:

The writes to b would be non-conditional-moves with a control dependency from a and and edge down to the write to c, which obviously is non-conditional. As such in terms of dependency ordering, we would have the control dependency always, thus couldn't we assume that in a current kernel we always have a load(a)->store(c) requirement?

I agree that if the compiler uses the normal comparisons and conditional branches, and if the hardware is not excessively clever (bad bet, by the way, long term), then the load from "a" should not be reordered with the store to "c".

Quoted 4 lines

Is there something else than conditional move instructions that could come to play here? Obviously a much smarter CPU could evaluate all the jumps and come to the conclusion that the write to c is never depending on the load from a, but is this implemented somewhere in hardware?

I don't know of any hardware that does that, but given that conditional moves are supported by some weakly ordered hardware, it looks to me that we are stuck with the possibility of "a"-"c" reordering.

Thanx, Paul

author maintainer
#26 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

Quoted 2 lines · Paul E. McKenney

and if the hardware is not excessively clever (bad bet, by the way, long term),

This ^

Quoted 8 lines
Quoted 4 lines

Is there something else than conditional move instructions that could come to play here? Obviously a much smarter CPU could evaluate all the jumps and come to the conclusion that the write to c is never depending on the load from a, but is this implemented somewhere in hardware?

I don't know of any hardware that does that, but given that conditional moves are supported by some weakly ordered hardware, it looks to me that we are stuck with the possibility of "a"-"c" reordering.

Is why I'm scared of relying on the non-condition.

The if and else branches are obviously dependent on the completion of the load; anything after that, not so much.

You could construct an argument against this program order speculation based on interrupts, which should not observe the stores out of order etc.. but if the hardware is that clever, it can also abort the entire speculation on interrupt (much like hardware transactions already can).

So even if today no hardware is this clever (and that isn't proven) there's nothing saying it will not ever be.

This is why I really do not want to advertise and or rely on this behaviour.

#27 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

Quoted 25 lines · Peter Zijlstra
Quoted 2 lines · Paul E. McKenney

and if the hardware is not excessively clever (bad bet, by the way, long term),

This ^

Quoted 8 lines
Quoted 4 lines

Is there something else than conditional move instructions that could come to play here? Obviously a much smarter CPU could evaluate all the jumps and come to the conclusion that the write to c is never depending on the load from a, but is this implemented somewhere in hardware?

I don't know of any hardware that does that, but given that conditional moves are supported by some weakly ordered hardware, it looks to me that we are stuck with the possibility of "a"-"c" reordering.

Is why I'm scared of relying on the non-condition.

The if and else branches are obviously dependent on the completion of the load; anything after that, not so much.

You could construct an argument against this program order speculation based on interrupts, which should not observe the stores out of order etc.. but if the hardware is that clever, it can also abort the entire speculation on interrupt (much like hardware transactions already can).

Quoted 5 lines

So even if today no hardware is this clever (and that isn't proven) there's nothing saying it will not ever be.

This is why I really do not want to advertise and or rely on this behaviour.

What Peter said! ;-)

Thanx, Paul

#28 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

In reply to Paul E. McKenney
Quoted 8 lines · Paul E. McKenney
Quoted 3 lines · Hannes Frederic Sowa

Sorry, to follow-up again on this. Will Deacon's comments were about conditional-move instructions, which this compiler-option would prevent, as far as I can see it.

According to this email thread, I believe that this works the other way around:

Quoted 7 lines

http://thread.gmane.org/gmane.linux.kernel/1721993

That parameter prevents the compiler from converting a conditional store into an unconditional store, which would be really problematic. Give the current kernel build, I believe that the compiler really is within its rights to use conditional-move instructions as shown above. But I again must defer to Will Deacon on the details.

A multi_v7_defconfig build of mainline certainly spits out conditional store instructions, but I have no idea whether these correspond to WRITE_ONCE or not:

$ objdump -d vmlinux | grep 'str\(eq\|ne\)' | wc -l
7326

At the end of the day, the ARM architecture says you can't rely on this being ordered and I can see it happening in practice in the face of conditional stores.

Will

#29 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

Quoted 21 lines · Will Deacon
Quoted 8 lines · Paul E. McKenney
Quoted 3 lines · Hannes Frederic Sowa

Sorry, to follow-up again on this. Will Deacon's comments were about conditional-move instructions, which this compiler-option would prevent, as far as I can see it.

According to this email thread, I believe that this works the other way around:

Quoted 7 lines

http://thread.gmane.org/gmane.linux.kernel/1721993

That parameter prevents the compiler from converting a conditional store into an unconditional store, which would be really problematic. Give the current kernel build, I believe that the compiler really is within its rights to use conditional-move instructions as shown above. But I again must defer to Will Deacon on the details.

A multi_v7_defconfig build of mainline certainly spits out conditional store instructions, but I have no idea whether these correspond to WRITE_ONCE or not:

Quoted 6 lines
$ objdump -d vmlinux | grep 'str\(eq\|ne\)' | wc -l
7326

At the end of the day, the ARM architecture says you can't rely on this being ordered and I can see it happening in practice in the face of conditional stores.

Thank you for the info, Will!

Thanx, Paul

#30 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

In reply to Will Deacon
Quoted 21 lines · Will Deacon
Quoted 8 lines · Paul E. McKenney
Quoted 3 lines · Hannes Frederic Sowa

Sorry, to follow-up again on this. Will Deacon's comments were about conditional-move instructions, which this compiler-option would prevent, as far as I can see it.

According to this email thread, I believe that this works the other way around:

Quoted 7 lines

http://thread.gmane.org/gmane.linux.kernel/1721993

That parameter prevents the compiler from converting a conditional store into an unconditional store, which would be really problematic. Give the current kernel build, I believe that the compiler really is within its rights to use conditional-move instructions as shown above. But I again must defer to Will Deacon on the details.

A multi_v7_defconfig build of mainline certainly spits out conditional store instructions, but I have no idea whether these correspond to WRITE_ONCE or not:

Quoted 6 lines
$ objdump -d vmlinux | grep 'str\(eq\|ne\)' | wc -l
7326

At the end of the day, the ARM architecture says you can't rely on this being ordered and I can see it happening in practice in the face of conditional stores.

Thank you for the information, Will!

Thanx, Paul

#31 lore raw

Re: [RFC][PATCH 1/3] locking: Introduce smp_acquire__after_ctrl_dep

In reply to Paul E. McKenney
Quoted 58 lines · Paul E. McKenney
Quoted 45 lines · Hannes Frederic Sowa
Quoted 44 lines · Paul E. McKenney
Quoted 32 lines · Hannes Frederic Sowa
Quoted 19 lines · Peter Zijlstra
Quoted 19 lines
Documentation/memory-barriers.txt +10 -0
index 147ae8ec836f..a4d0a99de04d 100644
@@ -806,6 +806,41 @@ out-guess your code.  More generally, although READ_ONCE() does force
 the compiler to actually emit code for a given load, it does not force
 the compiler to use the results.
 
+In addition, control dependencies apply only to the then-clause and
+else-clause of the if-statement in question.  In particular, it does
+not necessarily apply to code following the if-statement:
+
+	q = READ_ONCE(a);
+	if (q) {
+		WRITE_ONCE(b, p);
+	} else {
+		WRITE_ONCE(b, r);
+	}
Quoted 8 lines

Documentation/memory-barriers.txt out-guess your code. More generally, although READ_ONCE() does force · line 826

Quoted 8 lines
Documentation/memory-barriers.txt +8 -0
+	WRITE_ONCE(c, 1);  /* BUG: No ordering against the read from "a". */
+
+It is tempting to argue that there in fact is ordering because the
+compiler cannot reorder volatile accesses and also cannot reorder
+the writes to "b" with the condition.  Unfortunately for this line
+of reasoning, the compiler might compile the two writes to "b" as
+conditional-move instructions, as in this fanciful pseudo-assembly
+language:

I wonder if we already guarantee by kernel compiler settings that this behavior is not allowed by at least gcc.

Quoted 4 lines

We unconditionally set --param allow-store-data-races=0 which should actually prevent gcc from generating such conditional stores.

Am I seeing this correct here?

In this case, the store to "c" is unconditional, so pulling it forward would not generate a data race. However, the compiler is still prohibited from pulling it forward because it is not allowed to reorder volatile references. So, yes, the compiler cannot reorder, but for a different reason.

Quoted 6 lines
Quoted 2 lines

Some CPUs, on the other hand, can do this reordering, as Will Deacon pointed out earlier in this thread.

Sorry, to follow-up again on this. Will Deacon's comments were about conditional-move instructions, which this compiler-option would prevent, as far as I can see it.

According to this email thread, I believe that this works the other way around:

http://thread.gmane.org/gmane.linux.kernel/1721993

Quoted 7 lines

That parameter prevents the compiler from converting a conditional store into an unconditional store, which would be really problematic. Give the current kernel build, I believe that the compiler really is within its rights to use conditional-move instructions as shown above. But I again must defer to Will Deacon on the details.

Or am I misinterpreting that email thread?

Thanks, Paul!

Based on the description in the thread above, it makes perfectly sense what you wrote. Sorry for the noise.

Quoted 13 lines
Quoted 7 lines

Thus I couldn't follow your answer completely:

The writes to b would be non-conditional-moves with a control dependency from a and and edge down to the write to c, which obviously is non-conditional. As such in terms of dependency ordering, we would have the control dependency always, thus couldn't we assume that in a current kernel we always have a load(a)->store(c) requirement?

I agree that if the compiler uses the normal comparisons and conditional branches, and if the hardware is not excessively clever (bad bet, by the way, long term), then the load from "a" should not be reordered with the store to "c".

Quoted 8 lines
Quoted 4 lines

Is there something else than conditional move instructions that could come to play here? Obviously a much smarter CPU could evaluate all the jumps and come to the conclusion that the write to c is never depending on the load from a, but is this implemented somewhere in hardware?

I don't know of any hardware that does that, but given that conditional moves are supported by some weakly ordered hardware, it looks to me that we are stuck with the possibility of "a"-"c" reordering.

I totally agree.

Thanks,
Hannes

author maintainer
#32 lore raw

RFC PATCH 2/3 locking: Annotate spin_unlock_wait() users

In reply to Peter Zijlstra

spin_unlock_wait() has an unintuitive 'feature' in that it doesn't fully serialize against the spin_unlock() we've waited on.

In particular, spin_unlock_wait() only provides a control dependency, which is a LOAD->STORE order. This means subsequent loads can creep up and observe state prior to the waited-for unlock. This means we don't necessarily observe the full critical section.

We must employ smp_acquire__after_ctrl_dep() to upgrade the LOAD->STORE to LOAD->{LOAD,STORE} aka. load-AQUIRE and thereby ensure we observe the full critical section we've waited on.

Many spin_unlock_wait() users were unaware of this issue and need help.

---
 drivers/ata/libata-eh.c   |    4 +++-
 kernel/exit.c             |   14 ++++++++++++--
 kernel/sched/completion.c |    7 +++++++
 kernel/task_work.c        |    2 +-
 4 files changed, 23 insertions(+), 4 deletions(-)
drivers/ata/libata-eh.c +3 -1
@@ -703,8 +703,10 @@ void ata_scsi_cmd_error_handler(struct S
 
 		/* initialize eh_tries */
 		ap->eh_tries = ATA_EH_MAX_TRIES;
-	} else
+	} else {
 		spin_unlock_wait(ap->lock);
+		smp_acquire__after_ctrl_dep();
+	}
 
 }
 EXPORT_SYMBOL(ata_scsi_cmd_error_handler);
kernel/exit.c +12 -2
@@ -776,11 +776,16 @@ void do_exit(long code)
 
 	exit_signals(tsk);  /* sets PF_EXITING */
 	/*
-	 * tsk->flags are checked in the futex code to protect against
-	 * an exiting task cleaning up the robust pi futexes.
+	 * Ensure that all new tsk->pi_lock acquisitions must observe
+	 * PF_EXITING. Serializes against futex.c:attach_to_pi_owner().
 	 */
 	smp_mb();
 	raw_spin_unlock_wait(&tsk->pi_lock);
+	/*
+	 * Ensure that we must observe the pi_state in exit_mm() ->
+	 * mm_release() -> exit_pi_state_list().
+	 */
+	smp_acquire__after_ctrl_dep();
 
 	if (unlikely(in_atomic())) {
 		pr_info("note: %s[%d] exited with preempt_count %d\n",
@@ -897,6 +902,11 @@ void do_exit(long code)
 	 */
 	smp_mb();
 	raw_spin_unlock_wait(&tsk->pi_lock);
+	/*
+	 * Since there are no following loads the LOAD->LOAD order
+	 * provided by smp_acquire__after_ctrl_dep() is not
+	 * strictly required.
+	 */
 
 	/* causes final put_task_struct in finish_task_switch(). */
 	tsk->state = TASK_DEAD;
kernel/sched/completion.c +7 -0
@@ -312,6 +312,13 @@ bool completion_done(struct completion *
 	 */
 	smp_rmb();
 	spin_unlock_wait(&x->wait.lock);
+	/*
+	 * Even though we've observed 'done', this doesn't mean we can observe
+	 * all stores prior to complete(), as the only RELEASE barrier on that
+	 * path is provided by the spin_unlock().
+	 */
+	smp_acquire__after_ctrl_dep();
+
 	return true;
 }
 EXPORT_SYMBOL(completion_done);
kernel/task_work.c +1 -1
@@ -108,7 +108,7 @@ void task_work_run(void)
 		 * fail, but it can play with *work and other entries.
 		 */
 		raw_spin_unlock_wait(&task->pi_lock);
-		smp_mb();
+		smp_acquire__after_ctrl_dep();
 
 		do {
 			next = work->next;
#33 lore raw

Re: [RFC][PATCH 2/3] locking: Annotate spin_unlock_wait() users

Quoted 2 lines · Peter Zijlstra

spin_unlock_wait() has an unintuitive 'feature' in that it doesn't fully serialize against the spin_unlock() we've waited on.

NAK.

We don't start adding more of this "after_ctrl_dep" crap.

It's completely impossible to understand, and even people who have been locking experts have gotten it wrong.

So it is *completely* unacceptable to have it in drivers.

This needs to be either hidden inside the basic spinlock functions, _or_ it needs to be a clear and unambiguous interface. Anything that starts talking about control dependencies is not it.

Note that this really is about naming and use, not about implementation. So something like "spin_sync_after_unlock_wait()" is acceptable, even if the actual _implementation_ were to be exactly the same as the "after_ctrl_dep()" crap.

The difference is that one talks about incomprehensible implementation details that nobody outside of the person who *implemented* the spinlock code is supposed to understand (and seriously, I have my doubts even the spinlock implementer understands it, judging by the last time this happened), and the other is a much simpler semantic guarantee.

So don't talk about "acquire". And most certainly don't talk about "control dependencies". Not if we end up having things like *drivers* using this like in this example libata.

Linus

#34 lore raw

Re: [RFC][PATCH 2/3] locking: Annotate spin_unlock_wait() users

Hello,

Quoted 3 lines · Linus Torvalds

So don't talk about "acquire". And most certainly don't talk about "control dependencies". Not if we end up having things like *drivers* using this like in this example libata.

A delta but that particular libata usage is probably not needed now. The path was used while libata was gradually adding error handlers to the low level drivers. I don't think we don't have any left w/o one at this point. I'll verify and get rid of that usage.

Thanks.

Signature · 1 line
tejun
author maintainer
#35 lore raw

Re: [RFC][PATCH 2/3] locking: Annotate spin_unlock_wait() users

Quoted 4 lines · Tejun Heo

A delta but that particular libata usage is probably not needed now. The path was used while libata was gradually adding error handlers to the low level drivers. I don't think we don't have any left w/o one at this point. I'll verify and get rid of that usage.

OK, that would be great; I was sorta lost in there, but it looked like if you need the spin_unlock_wait() you also need the extra barrier thing.

If you can remove it, better still.

#36 lore raw

Re: [RFC][PATCH 2/3] locking: Annotate spin_unlock_wait() users

Quoted 11 lines · Peter Zijlstra
Quoted 4 lines · Tejun Heo

A delta but that particular libata usage is probably not needed now. The path was used while libata was gradually adding error handlers to the low level drivers. I don't think we don't have any left w/o one at this point. I'll verify and get rid of that usage.

OK, that would be great; I was sorta lost in there, but it looked like if you need the spin_unlock_wait() you also need the extra barrier thing.

If you can remove it, better still.

Unfortunately, ipr SAS driver is still using the old error handling path, so please include libata in the conversion for now. I'll see if ipr can be converted.

Thanks.

Signature · 1 line
tejun
author maintainer
#37 lore raw

Re: [RFC][PATCH 2/3] locking: Annotate spin_unlock_wait() users

In reply to Linus Torvalds
Quoted 8 lines · Linus Torvalds

This needs to be either hidden inside the basic spinlock functions, _or_ it needs to be a clear and unambiguous interface. Anything that starts talking about control dependencies is not it.

Note that this really is about naming and use, not about implementation. So something like "spin_sync_after_unlock_wait()" is acceptable, even if the actual _implementation_ were to be exactly the same as the "after_ctrl_dep()" crap.

OK; so I would prefer to keep the smp_acquire__after_ctrl_dep() crap for common use in smp_cond_acquire() and such, but I'd be more than happy to just stuff it unconditionally into spin_unlock_wait().

Most users really need it, and its restores intuitive semantics to the primitive.

I'm assuming the explicit use then left in ipc/sem.c (as paired with the spin_is_locked) is fine with you; that's certainly not driver code.

Todays series was really more about auditing all the spin_unlock_wait() usage sites.

author maintainer
#38 lore raw

RFC PATCH 3/3 locking,netfilter: Fix nf_conntrack_lock()

In reply to Peter Zijlstra

nf_conntrack_lock{,_all}() is borken as it misses a bunch of memory barriers to order the whole global vs local locks scheme.

Even x86 (and other TSO archs) are affected.

---
 net/netfilter/nf_conntrack_core.c |   30 +++++++++++++++++++++++++++++-
 1 file changed, 29 insertions(+), 1 deletion(-)
net/netfilter/nf_conntrack_core.c +29 -1
@@ -74,7 +74,18 @@ void nf_conntrack_lock(spinlock_t *lock)
 	spin_lock(lock);
 	while (unlikely(nf_conntrack_locks_all)) {
 		spin_unlock(lock);
+		/*
+		 * Order the nf_contrack_locks_all load vs the spin_unlock_wait()
+		 * loads below, to ensure locks_all is indeed held.
+		 */
+		smp_rmb(); /* spin_lock(locks_all) */
 		spin_unlock_wait(&nf_conntrack_locks_all_lock);
+		/*
+		 * The control dependency's LOAD->STORE order is enough to
+		 * guarantee the spin_lock() is ordered after the above
+		 * unlock_wait(). And the ACQUIRE of the lock ensures we are
+		 * fully ordered against the spin_unlock() of locks_all.
+		 */
 		spin_lock(lock);
 	}
 }
@@ -119,14 +130,31 @@ static void nf_conntrack_all_lock(void)
 	spin_lock(&nf_conntrack_locks_all_lock);
 	nf_conntrack_locks_all = true;
 
+	/*
+	 * Order the above store against the spin_unlock_wait() loads
+	 * below, such that if nf_conntrack_lock() observes lock_all
+	 * we must observe lock[] held.
+	 */
+	smp_mb(); /* spin_lock(locks_all) */
+
 	for (i = 0; i < CONNTRACK_LOCKS; i++) {
 		spin_unlock_wait(&nf_conntrack_locks[i]);
 	}
+	/*
+	 * Ensure we observe all state prior to the spin_unlock()s
+	 * observed above.
+	 */
+	smp_acquire__after_ctrl_dep();
 }
 
 static void nf_conntrack_all_unlock(void)
 {
-	nf_conntrack_locks_all = false;
+	/*
+	 * All prior stores must be complete before we clear locks_all.
+	 * Otherwise nf_conntrack_lock() might observe the false but not
+	 * the entire critical section.
+	 */
+	smp_store_release(&nf_conntrack_locks_all, false);
 	spin_unlock(&nf_conntrack_locks_all_lock);
 }
 
author maintainer
#39 lore raw

Re: [RFC][PATCH 3/3] locking,netfilter: Fix nf_conntrack_lock()

Quoted 13 lines · Peter Zijlstra

nf_conntrack_lock{,_all}() is borken as it misses a bunch of memory barriers to order the whole global vs local locks scheme.

Even x86 (and other TSO archs) are affected.

---
 net/netfilter/nf_conntrack_core.c |   30 +++++++++++++++++++++++++++++-
 1 file changed, 29 insertions(+), 1 deletion(-)

net/netfilter/nf_conntrack_core.c void nf_conntrack_lock(spinlock_t *lock) · line 75

Quoted 2 lines
net/netfilter/nf_conntrack_core.c +0 -0
@@ -74,7 +74,18 @@ void nf_conntrack_lock(spinlock_t *lock)
 	spin_lock(lock);
 	while (unlikely(nf_conntrack_locks_all)) {

And note that we can replace nf_conntrack_locks_all with spin_is_locked(nf_conntrack_locks_all_lock), since that is the exact same state.

But I didn't want to do too much in one go.

Quoted 16 lines
net/netfilter/nf_conntrack_core.c +11 -0
 		spin_unlock(lock);
+		/*
+		 * Order the nf_contrack_locks_all load vs the spin_unlock_wait()
+		 * loads below, to ensure locks_all is indeed held.
+		 */
+		smp_rmb(); /* spin_lock(locks_all) */
 		spin_unlock_wait(&nf_conntrack_locks_all_lock);
+		/*
+		 * The control dependency's LOAD->STORE order is enough to
+		 * guarantee the spin_lock() is ordered after the above
+		 * unlock_wait(). And the ACQUIRE of the lock ensures we are
+		 * fully ordered against the spin_unlock() of locks_all.
+		 */
 		spin_lock(lock);
 	}
 }

A message that is not in the archive (sent off-list or not yet received): [email protected]

author maintainer
#41 lore raw

Re: [RFC][PATCH 3/3] locking,netfilter: Fix nf_conntrack_lock()

Quoted 7 lines · Manfred Spraul
Quoted 7 lines
net/netfilter/nf_conntrack_core.c +1 -0
@@ -74,7 +74,18 @@ void nf_conntrack_lock(spinlock_t *lock)
 	spin_lock(lock);
 	while (unlikely(nf_conntrack_locks_all)) {
 		spin_unlock(lock);
+		/*
Quoted 8 lines

net/netfilter/nf_conntrack_core.c void nf_conntrack_lock(spinlock_t *lock) · line 82

Quoted 5 lines
net/netfilter/nf_conntrack_core.c +4 -0
+		 * Order the nf_contrack_locks_all load vs the spin_unlock_wait()
+		 * loads below, to ensure locks_all is indeed held.
+		 */
+		smp_rmb(); /* spin_lock(locks_all) */
 		spin_unlock_wait(&nf_conntrack_locks_all_lock);

I don't understand the comment, and I don't understand why the smp_rmb() is
required: What do you want to protect against?

I order against the spin_unlock_wait() load of nf_conntrack_locks_all_lock being done _before_ the nf_conntrack_locks_all load.

This is possible because the spin_unlock() in between will stop the nf_conntrack_locks_all load from falling down, but it doesn't stop the &nf_conntrack_locks_all_lock lock from being done early.

Inverting these two loads could result in not waiting when we should.

	nf_conntrack_all_lock()		nf_conntrack_lock()

					  [L] all_locks == unlocked
	  [S] spin_lock(&all_lock);
	  [S] all = true;
					  [L] all == true

And we'll not wait for the current all_lock section to finish. Resulting in an all_lock and lock section at the same time.