MCS Lock: MCS lock code cleanup and optimizations

In this patch series, we separated out the MCS lock code which was previously embedded in the mutex.c. This allows for easier reuse of MCS lock in other places like rwsem and qrwlock. We also did some micro optimizations and barrier cleanup.

The original code has potential leaks between critical sections, which was not a problem when MCS was embedded within the mutex but needs to be corrected when allowing the MCS lock to be used by itself for other locking purposes.

Proper barriers are now embedded with the usage of smp_load_acquire() in mcs_spin_lock() and smp_store_release() in mcs_spin_unlock. See
http://marc.info/?l=linux-arch&m=138386254111507 for info on the new smp_load_acquire() and smp_store_release() functions.

This patches were previously part of the rwsem optimization patch series but now we spearate them out.

We have also added hooks to allow for architecture specific implementation of the mcs_spin_lock and mcs_spin_unlock functions.

Will, do you want to take a crack at adding implementation for ARM with wfe instruction?

Hi Tim,

Quoted 21 lines · Tim Chen

In this patch series, we separated out the MCS lock code which was previously embedded in the mutex.c. This allows for easier reuse of MCS lock in other places like rwsem and qrwlock. We also did some micro optimizations and barrier cleanup.

The original code has potential leaks between critical sections, which was not a problem when MCS was embedded within the mutex but needs to be corrected when allowing the MCS lock to be used by itself for other locking purposes.

Proper barriers are now embedded with the usage of smp_load_acquire() in mcs_spin_lock() and smp_store_release() in mcs_spin_unlock. See
http://marc.info/?l=linux-arch&m=138386254111507 for info on the new smp_load_acquire() and smp_store_release() functions.

This patches were previously part of the rwsem optimization patch series but now we spearate them out.

We have also added hooks to allow for architecture specific implementation of the mcs_spin_lock and mcs_spin_unlock functions.

Quoted 2 lines

Will, do you want to take a crack at adding implementation for ARM with wfe instruction?

Sure, I'll have a go this week. Thanks for keeping that as a consideration!

As an aside: what are you using to test this code, so that I can make sure I don't break it?

Quoted 4 lines · Will Deacon

Quoted 2 lines · Tim Chen

Will, do you want to take a crack at adding implementation for ARM with wfe instruction?

Quoted 4 lines

Sure, I'll have a go this week. Thanks for keeping that as a consideration!

As an aside: what are you using to test this code, so that I can make sure I don't break it?

+1 to that! In fact, it would be nice to have the test code in-tree, especially if it can test a wide variety of locks. (/me needs to look at what test code for locks might already be in tree, for that matter...)

Quoted 5 lines · Paul E. McKenney

Quoted 4 lines · Will Deacon

Quoted 2 lines · Tim Chen

Will, do you want to take a crack at adding implementation for ARM with wfe instruction?

Quoted 8 lines

Quoted 4 lines

Sure, I'll have a go this week. Thanks for keeping that as a consideration!

As an aside: what are you using to test this code, so that I can make sure I don't break it?

+1 to that! In fact, it would be nice to have the test code in-tree, especially if it can test a wide variety of locks. (/me needs to look at what test code for locks might already be in tree, for that matter...)

Well, in the absence of those tests, I've implemented something that I think will work for ARM and could be easily extended to arm64.

Tim: I reverted your final patch and went with Paul's suggestion just to look into the contended case. I'm also not sure about adding asm/mcs_spinlock.h. This stuff might be better in asm/spinlock.h, which already exists and contains both spinlocks and rwlocks. Depends on how much people dislike the Kconfig symbol + conditional #include.

Anyway, patches below. I included the ARM bits for reference, but please don't include them in your series!

Cheers,

Will

--->8

Quoted 1 line

From 074f4cdf9ddc97454467b9ad9f85128ee67c5604 Mon Sep 17 00:00:00 2001

From: Will Deacon <[email protected]>
Date: Wed, 20 Nov 2013 16:14:04 +0000
Subject: [PATCH 1/3] MCS Lock: allow architectures to hook in to contended
paths

When contended, architectures may be able to reduce the polling overhead in ways which aren't expressible using a simple relax() primitive.

This patch allows architectures to hook into the mcs_{lock,unlock} functions for the contended cases only.

Signed-off-by Will Deacon <[email protected]>

---
 kernel/locking/mcs_spinlock.c | 47 +++++++++++++++++++++++++------------------
 1 file changed, 27 insertions(+), 20 deletions(-)

kernel/locking/mcs_spinlock.c +27 -20

index 6f2ce8efb006..853070b8a86d 100644
@@ -7,19 +7,34 @@
  * It avoids expensive cache bouncings that common test-and-set spin-lock
  * implementations incur.
  */
-/*
- * asm/processor.h may define arch_mutex_cpu_relax().
- * If it is not defined, cpu_relax() will be used.
- */
+
 #include <asm/barrier.h>
 #include <asm/cmpxchg.h>
 #include <asm/processor.h>
 #include <linux/compiler.h>
 #include <linux/mcs_spinlock.h>
+#include <linux/mutex.h>
 #include <linux/export.h>
 
-#ifndef arch_mutex_cpu_relax
-# define arch_mutex_cpu_relax() cpu_relax()
+#ifndef arch_mcs_spin_lock_contended
+/*
+ * Using smp_load_acquire() provides a memory barrier that ensures
+ * subsequent operations happen after the lock is acquired.
+ */
+#define arch_mcs_spin_lock_contended(l)					\
+	while (!(smp_load_acquire(l))) {				\
+		arch_mutex_cpu_relax();					\
+	}
+#endif
+
+#ifndef arch_mcs_spin_unlock_contended
+/*
+ * smp_store_release() provides a memory barrier to ensure all
+ * operations in the critical section has been completed before
+ * unlocking.
+ */
+#define arch_mcs_spin_unlock_contended(l)				\
+	smp_store_release((l), 1)
 #endif
 
 /*

@@ -44,13 +59,9 @@ void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
 		return;
 	}
 	ACCESS_ONCE(prev->next) = node;
-	/*
-	 * Wait until the lock holder passes the lock down.
-	 * Using smp_load_acquire() provides a memory barrier that
-	 * ensures subsequent operations happen after the lock is acquired.
-	 */
-	while (!(smp_load_acquire(&node->locked)))
-		arch_mutex_cpu_relax();
+
+	/* Wait until the lock holder passes the lock down. */
+	arch_mcs_spin_lock_contended(&node->locked);
 }
 EXPORT_SYMBOL_GPL(mcs_spin_lock);
 

@@ -72,12 +83,8 @@ void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
 		while (!(next = ACCESS_ONCE(node->next)))
 			arch_mutex_cpu_relax();
 	}
-	/*
-	 * Pass lock to next waiter.
-	 * smp_store_release() provides a memory barrier to ensure
-	 * all operations in the critical section has been completed
-	 * before unlocking.
-	 */
-	smp_store_release(&next->locked, 1);
+
+	/* Pass lock to next waiter. */
+	arch_mcs_spin_unlock_contended(&next->locked);
 }
 EXPORT_SYMBOL_GPL(mcs_spin_unlock);

Signature · 1 line

1.8.2.2

Quoted 1 line

From faa48f77a17cfd99562b1e36de278367aa4d389c Mon Sep 17 00:00:00 2001

From: Will Deacon <[email protected]>
Date: Wed, 20 Nov 2013 16:10:57 +0000
Subject: [PATCH 2/3] MCS Lock: add Kconfig entries to allow arch-specific
hooks

This patch adds Kconfig entries to allow architectures to hook into the MCS lock/unlock functions in the contended case.

Signed-off-by Will Deacon <[email protected]>

---
 arch/Kconfig                 | 3 +++
 include/linux/mcs_spinlock.h | 8 ++++++++
 2 files changed, 11 insertions(+)

arch/Kconfig +3 -0

index f1cf895c040f..ae738f706325 100644
@@ -303,6 +303,9 @@ config HAVE_CMPXCHG_LOCAL
 config HAVE_CMPXCHG_DOUBLE
 	bool
 
+config HAVE_ARCH_MCS_LOCK
+	bool
+
 config ARCH_WANT_IPC_PARSE_VERSION
 	bool
 

include/linux/mcs_spinlock.h +8 -0

index d54bb232a238..d2c02adb0bbd 100644
@@ -12,6 +12,14 @@
 #ifndef __LINUX_MCS_SPINLOCK_H
 #define __LINUX_MCS_SPINLOCK_H
 
+/*
+ * An architecture may provide its own lock/unlock functions for the
+ * contended case.
+ */
+#ifdef CONFIG_HAVE_ARCH_MCS_LOCK
+#include <asm/mcs_spinlock.h>
+#endif
+
 struct mcs_spinlock {
 	struct mcs_spinlock *next;
 	int locked; /* 1 if lock acquired */

Signature · 1 line

1.8.2.2

Quoted 1 line

From 21f047d40002ec4f1b780eee88f16a1870ab00ef Mon Sep 17 00:00:00 2001

From: Will Deacon <[email protected]>
Date: Wed, 20 Nov 2013 16:15:31 +0000
Subject: [PATCH 3/3] ARM: mcs lock: implement wfe-based polling for MCS
locking

This patch introduces a wfe-based polling loop for spinning on contended MCS locks and waking up corresponding waiters when the lock is released.

Signed-off-by Will Deacon <[email protected]>

---
 arch/arm/Kconfig                    |  1 +
 arch/arm/include/asm/mcs_spinlock.h | 20 ++++++++++++++++++++
 2 files changed, 21 insertions(+)
 create mode 100644 arch/arm/include/asm/mcs_spinlock.h

arch/arm/Kconfig +1 -0

index 214b698cefea..ab9fb84599ac 100644
@@ -25,6 +25,7 @@ config ARM
 	select HARDIRQS_SW_RESEND
 	select HAVE_ARCH_JUMP_LABEL if !XIP_KERNEL
 	select HAVE_ARCH_KGDB
+	select HAVE_ARCH_MCS_LOCK
 	select HAVE_ARCH_SECCOMP_FILTER
 	select HAVE_ARCH_TRACEHOOK
 	select HAVE_BPF_JIT

arch/arm/include/asm/mcs_spinlock.h new file +20 -0

new file mode 100644
index 000000000000..f32f97e81471
@@ -0,0 +1,20 @@
+#ifndef __ASM_MCS_LOCK_H
+#define __ASM_MCS_LOCK_H
+
+/* MCS spin-locking. */
+#define arch_mcs_spin_lock_contended(lock)				\
+do {									\
+	/* Ensure prior stores are observed before we enter wfe. */	\
+	smp_mb();							\
+	while (!(smp_load_acquire(lock)))				\
+		wfe();							\
+} while (0)								\
+
+#define arch_mcs_spin_unlock_contended(lock)				\
+do {									\
+	smp_store_release(lock, 1);					\
+	dsb(ishst);							\
+	sev();								\
+} while (0)
+
+#endif	/* __ASM_MCS_LOCK_H */

Signature · 1 line

1.8.2.2

Hi Tim,

Quoted 21 lines · Tim Chen

In this patch series, we separated out the MCS lock code which was previously embedded in the mutex.c. This allows for easier reuse of MCS lock in other places like rwsem and qrwlock. We also did some micro optimizations and barrier cleanup.

The original code has potential leaks between critical sections, which was not a problem when MCS was embedded within the mutex but needs to be corrected when allowing the MCS lock to be used by itself for other locking purposes.

Proper barriers are now embedded with the usage of smp_load_acquire() in mcs_spin_lock() and smp_store_release() in mcs_spin_unlock. See
http://marc.info/?l=linux-arch&m=138386254111507 for info on the new smp_load_acquire() and smp_store_release() functions.

This patches were previously part of the rwsem optimization patch series but now we spearate them out.

We have also added hooks to allow for architecture specific implementation of the mcs_spin_lock and mcs_spin_unlock functions.

Quoted 2 lines

Will, do you want to take a crack at adding implementation for ARM with wfe instruction?

Sure, I'll have a go this week. Thanks for keeping that as a consideration!

As an aside: what are you using to test this code, so that I can make sure I don't break it?

Will

Quoted 27 lines · Will Deacon

Hi Tim,

Quoted 23 lines · Tim Chen

In this patch series, we separated out the MCS lock code which was previously embedded in the mutex.c. This allows for easier reuse of MCS lock in other places like rwsem and qrwlock. We also did some micro optimizations and barrier cleanup.

The original code has potential leaks between critical sections, which was not a problem when MCS was embedded within the mutex but needs to be corrected when allowing the MCS lock to be used by itself for other locking purposes.

Proper barriers are now embedded with the usage of smp_load_acquire() in mcs_spin_lock() and smp_store_release() in mcs_spin_unlock. See
http://marc.info/?l=linux-arch&m=138386254111507 for info on the new smp_load_acquire() and smp_store_release() functions.

This patches were previously part of the rwsem optimization patch series but now we spearate them out.

We have also added hooks to allow for architecture specific implementation of the mcs_spin_lock and mcs_spin_unlock functions.

Will, do you want to take a crack at adding implementation for ARM with wfe instruction?

Quoted 4 lines

Sure, I'll have a go this week. Thanks for keeping that as a consideration!

As an aside: what are you using to test this code, so that I can make sure I don't break it?

I was testing it against my rwsem patches. But any workload that exercises mutex should also use this code, as this is part of mutex.

This patch corrects the way memory barriers are used in the MCS lock with smp_load_acquire and smp_store_release fucnction.
It removes ones that are not needed.

It uses architecture specific load-acquire and store-release primitives for synchronization, if available. Generic implementations are provided in case they are not defined even though they may not be optimal. These generic implementation could be removed later on once changes are made in all the relevant header files.

Suggested-by Michel Lespinasse <[email protected]>

Signed-off-by Waiman Long <[email protected]>

Signed-off-by Jason Low <[email protected]>

Signed-off-by Tim Chen <[email protected]>

---
 kernel/locking/mcs_spinlock.c | 19 ++++++++++++++-----
 1 file changed, 14 insertions(+), 5 deletions(-)

kernel/locking/mcs_spinlock.c +7 -3

index 44fb092..6f2ce8e 100644
@@ -37,15 +37,19 @@ void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
 	node->locked = 0;
 	node->next   = NULL;
 
+	/* xchg() provides a memory barrier */
 	prev = xchg(lock, node);
 	if (likely(prev == NULL)) {
 		/* Lock acquired */
 		return;
 	}
 	ACCESS_ONCE(prev->next) = node;
-	smp_wmb();
-	/* Wait until the lock holder passes the lock down */
-	while (!ACCESS_ONCE(node->locked))
+	/*
+	 * Wait until the lock holder passes the lock down.
+	 * Using smp_load_acquire() provides a memory barrier that
+	 * ensures subsequent operations happen after the lock is acquired.
+	 */
+	while (!(smp_load_acquire(&node->locked)))
 		arch_mutex_cpu_relax();
 }
 EXPORT_SYMBOL_GPL(mcs_spin_lock);

@@ -68,7 +72,12 @@ void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
 		while (!(next = ACCESS_ONCE(node->next)))
 			arch_mutex_cpu_relax();

kernel/locking/mcs_spinlock.c +0 -0

 }
 EXPORT_SYMBOL_GPL(mcs_spin_unlock);

Signature · 1 line

1.7.11.7

kernel/locking/mcs_spinlock.c void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node) · line 81

Quoted 13 lines · Tim Chen

kernel/locking/mcs_spinlock.c +7 -2

@@ -68,7 +72,12 @@ void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
 		while (!(next = ACCESS_ONCE(node->next)))
 			arch_mutex_cpu_relax();
 	}
-	ACCESS_ONCE(next->locked) = 1;
-	smp_wmb();
+	/*
+	 * Pass lock to next waiter.
+	 * smp_store_release() provides a memory barrier to ensure
+	 * all operations in the critical section has been completed
+	 * before unlocking.
+	 */
+	smp_store_release(&next->locked, 1);

However, there is one problem with this that I missed yesterday.

Documentation/memory-barriers.txt requires that an unlock-lock pair provide a full barrier, but this is not guaranteed if we use smp_store_release() for unlock and smp_load_acquire() for lock. At least one of these needs a full memory barrier.

Hi Paul,

Quoted 17 lines · Paul E. McKenney

kernel/locking/mcs_spinlock.c void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node) · line 81

Quoted 13 lines · Tim Chen

kernel/locking/mcs_spinlock.c +7 -2

@@ -68,7 +72,12 @@ void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
 		while (!(next = ACCESS_ONCE(node->next)))
 			arch_mutex_cpu_relax();
 	}
-	ACCESS_ONCE(next->locked) = 1;
-	smp_wmb();
+	/*
+	 * Pass lock to next waiter.
+	 * smp_store_release() provides a memory barrier to ensure
+	 * all operations in the critical section has been completed
+	 * before unlocking.
+	 */
+	smp_store_release(&next->locked, 1);

However, there is one problem with this that I missed yesterday.

Quoted 4 lines

Documentation/memory-barriers.txt requires that an unlock-lock pair provide a full barrier, but this is not guaranteed if we use smp_store_release() for unlock and smp_load_acquire() for lock. At least one of these needs a full memory barrier.

Hmm, so in the following case:

Access A
unlock() /* release semantics */
lock() /* acquire semantics */
Access B

A cannot pass beyond the unlock() and B cannot pass the before the lock().

I agree that accesses between the unlock and the lock can be move across both A and B, but that doesn't seem to matter by my reading of the above.

What is the problematic scenario you have in mind? Are you thinking of the lock() moving before the unlock()? That's only permitted by RCpc afaiu, which I don't think any architectures supported by Linux implement... (ARMv8 acquire/release is RCsc).

Quoted 34 lines · Will Deacon

Hi Paul,

Quoted 17 lines · Paul E. McKenney

kernel/locking/mcs_spinlock.c void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node) · line 81

Quoted 13 lines · Tim Chen

kernel/locking/mcs_spinlock.c +7 -2

@@ -68,7 +72,12 @@ void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
 		while (!(next = ACCESS_ONCE(node->next)))
 			arch_mutex_cpu_relax();
 	}
-	ACCESS_ONCE(next->locked) = 1;
-	smp_wmb();
+	/*
+	 * Pass lock to next waiter.
+	 * smp_store_release() provides a memory barrier to ensure
+	 * all operations in the critical section has been completed
+	 * before unlocking.
+	 */
+	smp_store_release(&next->locked, 1);

However, there is one problem with this that I missed yesterday.

Quoted 4 lines

Documentation/memory-barriers.txt requires that an unlock-lock pair provide a full barrier, but this is not guaranteed if we use smp_store_release() for unlock and smp_load_acquire() for lock. At least one of these needs a full memory barrier.

Hmm, so in the following case:

Access A
unlock() /* release semantics */
lock() /* acquire semantics */
Access B

A cannot pass beyond the unlock() and B cannot pass the before the lock().

Quoted 7 lines

I agree that accesses between the unlock and the lock can be move across both A and B, but that doesn't seem to matter by my reading of the above.

What is the problematic scenario you have in mind? Are you thinking of the lock() moving before the unlock()? That's only permitted by RCpc afaiu, which I don't think any architectures supported by Linux implement... (ARMv8 acquire/release is RCsc).

If smp_load_acquire() and smp_store_release() are both implemented using lwsync on powerpc, and if Access A is a store and Access B is a load, then Access A and Access B can be reordered.

Of course, if every other architecture will be providing RCsc implementations for smp_load_acquire() and smp_store_release(), which would not be a bad thing, then another approach is for powerpc to use sync rather than lwsync for one or the other of smp_load_acquire() or smp_store_release().

Thanx, Paul

Quoted 47 lines · Paul E. McKenney

Quoted 34 lines · Will Deacon

Hi Paul,

Quoted 17 lines · Paul E. McKenney

kernel/locking/mcs_spinlock.c void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node) · line 81

Quoted 13 lines · Tim Chen

kernel/locking/mcs_spinlock.c +7 -2

@@ -68,7 +72,12 @@ void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
 		while (!(next = ACCESS_ONCE(node->next)))
 			arch_mutex_cpu_relax();
 	}
-	ACCESS_ONCE(next->locked) = 1;
-	smp_wmb();
+	/*
+	 * Pass lock to next waiter.
+	 * smp_store_release() provides a memory barrier to ensure
+	 * all operations in the critical section has been completed
+	 * before unlocking.
+	 */
+	smp_store_release(&next->locked, 1);

However, there is one problem with this that I missed yesterday.

Quoted 4 lines

Documentation/memory-barriers.txt requires that an unlock-lock pair provide a full barrier, but this is not guaranteed if we use smp_store_release() for unlock and smp_load_acquire() for lock. At least one of these needs a full memory barrier.

Hmm, so in the following case:

Access A
unlock() /* release semantics */
lock() /* acquire semantics */
Access B

A cannot pass beyond the unlock() and B cannot pass the before the lock().

Quoted 7 lines

I agree that accesses between the unlock and the lock can be move across both A and B, but that doesn't seem to matter by my reading of the above.

What is the problematic scenario you have in mind? Are you thinking of the lock() moving before the unlock()? That's only permitted by RCpc afaiu, which I don't think any architectures supported by Linux implement... (ARMv8 acquire/release is RCsc).

If smp_load_acquire() and smp_store_release() are both implemented using lwsync on powerpc, and if Access A is a store and Access B is a load, then Access A and Access B can be reordered.

Quoted 4 lines

Of course, if every other architecture will be providing RCsc implementations for smp_load_acquire() and smp_store_release(), which would not be a bad thing, then another approach is for powerpc to use sync rather than lwsync for one or the other of smp_load_acquire() or smp_store_release().

Can we count on the xchg function in the beginning of mcs_lock to provide a memory barrier? It should provide an implicit memory barrier according to the memory-barriers document.

Quoted 48 lines · Tim Chen

Quoted 47 lines · Paul E. McKenney

Quoted 34 lines · Will Deacon

Hi Paul,

Quoted 17 lines · Paul E. McKenney

kernel/locking/mcs_spinlock.c void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node) · line 81

Quoted 13 lines · Tim Chen

kernel/locking/mcs_spinlock.c +7 -2

@@ -68,7 +72,12 @@ void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
 		while (!(next = ACCESS_ONCE(node->next)))
 			arch_mutex_cpu_relax();
 	}
-	ACCESS_ONCE(next->locked) = 1;
-	smp_wmb();
+	/*
+	 * Pass lock to next waiter.
+	 * smp_store_release() provides a memory barrier to ensure
+	 * all operations in the critical section has been completed
+	 * before unlocking.
+	 */
+	smp_store_release(&next->locked, 1);

However, there is one problem with this that I missed yesterday.

Quoted 4 lines

Documentation/memory-barriers.txt requires that an unlock-lock pair provide a full barrier, but this is not guaranteed if we use smp_store_release() for unlock and smp_load_acquire() for lock. At least one of these needs a full memory barrier.

Hmm, so in the following case:

Access A
unlock() /* release semantics */
lock() /* acquire semantics */
Access B

A cannot pass beyond the unlock() and B cannot pass the before the lock().

Quoted 7 lines

I agree that accesses between the unlock and the lock can be move across both A and B, but that doesn't seem to matter by my reading of the above.

What is the problematic scenario you have in mind? Are you thinking of the lock() moving before the unlock()? That's only permitted by RCpc afaiu, which I don't think any architectures supported by Linux implement... (ARMv8 acquire/release is RCsc).

If smp_load_acquire() and smp_store_release() are both implemented using lwsync on powerpc, and if Access A is a store and Access B is a load, then Access A and Access B can be reordered.

Quoted 8 lines

Quoted 4 lines

Of course, if every other architecture will be providing RCsc implementations for smp_load_acquire() and smp_store_release(), which would not be a bad thing, then another approach is for powerpc to use sync rather than lwsync for one or the other of smp_load_acquire() or smp_store_release().

Can we count on the xchg function in the beginning of mcs_lock to provide a memory barrier? It should provide an implicit memory barrier according to the memory-barriers document.

The problem with the implicit full barrier associated with the xchg() function is that it is in the wrong place if the lock is contended. We need to ensure that the previous lock holder's critical section is seen by everyone to precede that of the next lock holder, and we need transitivity. The only operations that are in the right place to force the needed ordering in the contended case are those involved in the lock handoff. :-(

Thanx, Paul

Quoted 58 lines · Paul E. McKenney

Quoted 48 lines · Tim Chen

Quoted 47 lines · Paul E. McKenney

Quoted 34 lines · Will Deacon

Hi Paul,

Quoted 17 lines · Paul E. McKenney

Review void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node) · line 81

Quoted 13 lines · Tim Chen

(quoted diff) +7 -2

@@ -68,7 +72,12 @@ void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
 		while (!(next = ACCESS_ONCE(node->next)))
 			arch_mutex_cpu_relax();
 	}
-	ACCESS_ONCE(next->locked) = 1;
-	smp_wmb();
+	/*
+	 * Pass lock to next waiter.
+	 * smp_store_release() provides a memory barrier to ensure
+	 * all operations in the critical section has been completed
+	 * before unlocking.
+	 */
+	smp_store_release(&next->locked, 1);

However, there is one problem with this that I missed yesterday.

Quoted 4 lines

Documentation/memory-barriers.txt requires that an unlock-lock pair provide a full barrier, but this is not guaranteed if we use smp_store_release() for unlock and smp_load_acquire() for lock. At least one of these needs a full memory barrier.

Hmm, so in the following case:

Access A
unlock() /* release semantics */
lock() /* acquire semantics */
Access B

A cannot pass beyond the unlock() and B cannot pass the before the lock().

Quoted 7 lines

I agree that accesses between the unlock and the lock can be move across both A and B, but that doesn't seem to matter by my reading of the above.

What is the problematic scenario you have in mind? Are you thinking of the lock() moving before the unlock()? That's only permitted by RCpc afaiu, which I don't think any architectures supported by Linux implement... (ARMv8 acquire/release is RCsc).

If smp_load_acquire() and smp_store_release() are both implemented using lwsync on powerpc, and if Access A is a store and Access B is a load, then Access A and Access B can be reordered.

Quoted 8 lines

Quoted 4 lines

Of course, if every other architecture will be providing RCsc implementations for smp_load_acquire() and smp_store_release(), which would not be a bad thing, then another approach is for powerpc to use sync rather than lwsync for one or the other of smp_load_acquire() or smp_store_release().

Can we count on the xchg function in the beginning of mcs_lock to provide a memory barrier? It should provide an implicit memory barrier according to the memory-barriers document.

Quoted 8 lines

The problem with the implicit full barrier associated with the xchg() function is that it is in the wrong place if the lock is contended. We need to ensure that the previous lock holder's critical section is seen by everyone to precede that of the next lock holder, and we need transitivity. The only operations that are in the right place to force the needed ordering in the contended case are those involved in the lock handoff. :-(

Paul,

I'm still scratching my head on how ACCESS A
and ACCESS B could get reordered.

The smp_store_release instruction in unlock should guarantee that all memory operations in the previous lock holder's critical section has been completed and seen by everyone, before the store operation to set the lock for the next holder is seen. And the smp_load_acquire should guarantee that all memory operations for next lock holder happen after checking that it has got lock. So it seems like the two critical sections should not overlap.

Does using lwsync means that these smp_load_acquire and smp_store_release guarantees are no longer true?

Quoted 81 lines · Tim Chen

Quoted 58 lines · Paul E. McKenney

Quoted 48 lines · Tim Chen

Quoted 47 lines · Paul E. McKenney

Quoted 34 lines · Will Deacon

Hi Paul,

Quoted 17 lines · Paul E. McKenney

Review void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node) · line 81

Quoted 13 lines · Tim Chen

(quoted diff) +7 -2

@@ -68,7 +72,12 @@ void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
 		while (!(next = ACCESS_ONCE(node->next)))
 			arch_mutex_cpu_relax();
 	}
-	ACCESS_ONCE(next->locked) = 1;
-	smp_wmb();
+	/*
+	 * Pass lock to next waiter.
+	 * smp_store_release() provides a memory barrier to ensure
+	 * all operations in the critical section has been completed
+	 * before unlocking.
+	 */
+	smp_store_release(&next->locked, 1);

However, there is one problem with this that I missed yesterday.

Quoted 4 lines

Documentation/memory-barriers.txt requires that an unlock-lock pair provide a full barrier, but this is not guaranteed if we use smp_store_release() for unlock and smp_load_acquire() for lock. At least one of these needs a full memory barrier.

Hmm, so in the following case:

Access A
unlock() /* release semantics */
lock() /* acquire semantics */
Access B

A cannot pass beyond the unlock() and B cannot pass the before the lock().

Quoted 7 lines

I agree that accesses between the unlock and the lock can be move across both A and B, but that doesn't seem to matter by my reading of the above.

What is the problematic scenario you have in mind? Are you thinking of the lock() moving before the unlock()? That's only permitted by RCpc afaiu, which I don't think any architectures supported by Linux implement... (ARMv8 acquire/release is RCsc).

If smp_load_acquire() and smp_store_release() are both implemented using lwsync on powerpc, and if Access A is a store and Access B is a load, then Access A and Access B can be reordered.

Quoted 8 lines

Quoted 4 lines

Of course, if every other architecture will be providing RCsc implementations for smp_load_acquire() and smp_store_release(), which would not be a bad thing, then another approach is for powerpc to use sync rather than lwsync for one or the other of smp_load_acquire() or smp_store_release().

Can we count on the xchg function in the beginning of mcs_lock to provide a memory barrier? It should provide an implicit memory barrier according to the memory-barriers document.

Quoted 8 lines

The problem with the implicit full barrier associated with the xchg() function is that it is in the wrong place if the lock is contended. We need to ensure that the previous lock holder's critical section is seen by everyone to precede that of the next lock holder, and we need transitivity. The only operations that are in the right place to force the needed ordering in the contended case are those involved in the lock handoff. :-(

Paul,

I'm still scratching my head on how ACCESS A
and ACCESS B could get reordered.

The smp_store_release instruction in unlock should guarantee that all memory operations in the previous lock holder's critical section has been completed and seen by everyone, before the store operation to set the lock for the next holder is seen. And the smp_load_acquire should guarantee that all memory operations for next lock holder happen after checking that it has got lock. So it seems like the two critical sections should not overlap.

Quoted 2 lines

Does using lwsync means that these smp_load_acquire and smp_store_release guarantees are no longer true?

Suppose that CPU 0 stores to a variable, then releases a lock, CPU 1 acquires that same lock and reads a second variable, and that CPU 2 writes the second variable, does smp_mb(), and then reads the first variable. Like this, where we replace the spinloop by a check in the assertion:

	CPU 0		CPU 1			CPU 2
	-----		-----			-----
	x = 1;		r1 = SLA(lock);		y = 1;
	SSR(lock, 1);	r2 = y;			smp_mb();
						r3 = x;

The SSR() is an abbreviation for smp_store_release() and the SLA() is an abbreviation for smp_load_acquire().

Now, if an unlock and following lock act as a full memory barrier, and given lock, x, and y all initially zero, it should not be possible to see the following situation:

	r1 == 1 && r2 == 0 && r3 == 0

The "r1 == 1" means that the lock was released, the "r2 == 1" means that

CPU 1's load from y happened before CPU 2's assignment to y, and the "r3 == 0" means that CPU 2's load from x happened before CPU 0's store to x. If the unlock/lock combination was acting like a full barrier, this would be impossible. But if you implement both SSR() and SLA() with lwsync on powerpc, this condition can in fact happen. See scenario W+RWC on page 2 of: http://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf.

This may seem strange, but when you say "lwsync" you are saying "don't bother flushing the store buffer", which in turn allows this outcome.

So if we require that smp_load_acquire() and smp_store_release() have RCsc semantics, which we might well want to do, then your use becomes legal and powerpc needs smp_store_release() to have a sync instruction rather than the lighter-weight lwsync instruction. Otherwise, you need an smp_mb() in the lock-release handoff path.

Thoughts?

Thanx, Paul

Quoted 82 lines · Paul E. McKenney

Quoted 81 lines · Tim Chen

Quoted 58 lines · Paul E. McKenney

Quoted 48 lines · Tim Chen

Quoted 47 lines · Paul E. McKenney

Quoted 34 lines · Will Deacon

Hi Paul,

Quoted 17 lines · Paul E. McKenney

Review void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node) · line 81

Quoted 13 lines · Tim Chen

(quoted diff) +7 -2

@@ -68,7 +72,12 @@ void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
 		while (!(next = ACCESS_ONCE(node->next)))
 			arch_mutex_cpu_relax();
 	}
-	ACCESS_ONCE(next->locked) = 1;
-	smp_wmb();
+	/*
+	 * Pass lock to next waiter.
+	 * smp_store_release() provides a memory barrier to ensure
+	 * all operations in the critical section has been completed
+	 * before unlocking.
+	 */
+	smp_store_release(&next->locked, 1);

However, there is one problem with this that I missed yesterday.

Quoted 4 lines

Documentation/memory-barriers.txt requires that an unlock-lock pair provide a full barrier, but this is not guaranteed if we use smp_store_release() for unlock and smp_load_acquire() for lock. At least one of these needs a full memory barrier.

Hmm, so in the following case:

Access A
unlock() /* release semantics */
lock() /* acquire semantics */
Access B

A cannot pass beyond the unlock() and B cannot pass the before the lock().

Quoted 7 lines

I agree that accesses between the unlock and the lock can be move across both A and B, but that doesn't seem to matter by my reading of the above.

What is the problematic scenario you have in mind? Are you thinking of the lock() moving before the unlock()? That's only permitted by RCpc afaiu, which I don't think any architectures supported by Linux implement... (ARMv8 acquire/release is RCsc).

If smp_load_acquire() and smp_store_release() are both implemented using lwsync on powerpc, and if Access A is a store and Access B is a load, then Access A and Access B can be reordered.

Quoted 8 lines

Quoted 4 lines

Of course, if every other architecture will be providing RCsc implementations for smp_load_acquire() and smp_store_release(), which would not be a bad thing, then another approach is for powerpc to use sync rather than lwsync for one or the other of smp_load_acquire() or smp_store_release().

Can we count on the xchg function in the beginning of mcs_lock to provide a memory barrier? It should provide an implicit memory barrier according to the memory-barriers document.

Quoted 8 lines

The problem with the implicit full barrier associated with the xchg() function is that it is in the wrong place if the lock is contended. We need to ensure that the previous lock holder's critical section is seen by everyone to precede that of the next lock holder, and we need transitivity. The only operations that are in the right place to force the needed ordering in the contended case are those involved in the lock handoff. :-(

Paul,

I'm still scratching my head on how ACCESS A
and ACCESS B could get reordered.

The smp_store_release instruction in unlock should guarantee that all memory operations in the previous lock holder's critical section has been completed and seen by everyone, before the store operation to set the lock for the next holder is seen. And the smp_load_acquire should guarantee that all memory operations for next lock holder happen after checking that it has got lock. So it seems like the two critical sections should not overlap.

Quoted 3 lines

Quoted 2 lines

Does using lwsync means that these smp_load_acquire and smp_store_release guarantees are no longer true?

Thanks for the detailed explanation.

Quoted 19 lines

Suppose that CPU 0 stores to a variable, then releases a lock, CPU 1 acquires that same lock and reads a second variable, and that CPU 2 writes the second variable, does smp_mb(), and then reads the first variable. Like this, where we replace the spinloop by a check in the assertion:

	CPU 0		CPU 1			CPU 2
	-----		-----			-----
	x = 1;		r1 = SLA(lock);		y = 1;
	SSR(lock, 1);	r2 = y;			smp_mb();
						r3 = x;

The SSR() is an abbreviation for smp_store_release() and the SLA() is an abbreviation for smp_load_acquire().

Now, if an unlock and following lock act as a full memory barrier, and given lock, x, and y all initially zero, it should not be possible to see the following situation:

Quoted 3 lines

	r1 == 1 && r2 == 0 && r3 == 0

The "r1 == 1" means that the lock was released, the "r2 == 1" means that

You mean "r2 == 0"?

Quoted 9 lines

CPU 1's load from y happened before CPU 2's assignment to y, and the "r3 == 0" means that CPU 2's load from x happened before CPU 0's store to x. If the unlock/lock combination was acting like a full barrier, this would be impossible. But if you implement both SSR() and SLA() with lwsync on powerpc, this condition can in fact happen. See scenario W+RWC on page 2 of: http://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf.

This may seem strange, but when you say "lwsync" you are saying "don't bother flushing the store buffer", which in turn allows this outcome.

Yes, this outcome is certainly not expected. I find the behavior somewhat at odds with the memory barrier documentation:

"The use of ACQUIRE and RELEASE operations generally precludes the need for other sorts of memory barrier (but note the exceptions mentioned in the subsection "MMIO write barrier")."

Quoted 7 lines

So if we require that smp_load_acquire() and smp_store_release() have RCsc semantics, which we might well want to do, then your use becomes legal and powerpc needs smp_store_release() to have a sync instruction rather than the lighter-weight lwsync instruction. Otherwise, you need an smp_mb() in the lock-release handoff path.

Thoughts?

If we intend to use smp_load_acquire and smp_store_release extensively for locks, making RCsc semantics the default will simply things a lot.

Quoted 2 lines · Tim Chen

If we intend to use smp_load_acquire and smp_store_release extensively for locks, making RCsc semantics the default will simply things a lot.

The other option is to weaken lock semantics so that unlock-lock no longer implies a full barrier, but I believe that we would regret taking that path. (It would be OK by me, I would just add a few smp_mb() calls on various slowpaths in RCU. But...)

Quoted 8 lines · Paul E. McKenney

Quoted 2 lines · Tim Chen

If we intend to use smp_load_acquire and smp_store_release extensively for locks, making RCsc semantics the default will simply things a lot.

The other option is to weaken lock semantics so that unlock-lock no longer implies a full barrier, but I believe that we would regret taking that path. (It would be OK by me, I would just add a few smp_mb() calls on various slowpaths in RCU. But...)

Unsurprisingly, my vote is for RCsc semantics.

One major advantage (in my opinion) of the acquire/release accessors is that they feel intuitive in an area where intuition is hardly rife. I believe that the additional reordering permitted by RCpc detracts from the relative simplicity of what is currently being proposed.

The other option is to weaken lock semantics so that unlock-lock no longer implies a full barrier, but I believe that we would regret taking that path. (It would be OK by me, I would just add a few smp_mb() calls on various slowpaths in RCU. But...)

Quoted 4 lines · Paul E. McKenney

The other option is to weaken lock semantics so that unlock-lock no longer implies a full barrier, but I believe that we would regret taking that path. (It would be OK by me, I would just add a few smp_mb() calls on various slowpaths in RCU. But...)

Please no, I know we rely on it in a number of places, I just can't remember where all those were :/

The other option is to weaken lock semantics so that unlock-lock no longer implies a full barrier, but I believe that we would regret taking that path. (It would be OK by me, I would just add a few smp_mb() calls on various slowpaths in RCU. But...)

Quoted 5 lines · Paul E. McKenney

The other option is to weaken lock semantics so that unlock-lock no longer implies a full barrier, but I believe that we would regret taking that path. (It would be OK by me, I would just add a few smp_mb() calls on various slowpaths in RCU. But...)

Hmm. I *thought* we already did that, exactly because some architecture already hit this issue, and we got rid of some of the more subtle "this works because.."

No?

Anyway, isn't "unlock+lock" fundamentally guaranteed to be a memory barrier? Anything before the unlock cannot possibly migrate down below the unlock, and anything after the lock must not possibly migrate up to before the lock? If either of those happens, then something has migrated out of the critical region, which is against the whole point of locking..

It's the "lock+unlock" where it's possible that something before the lock might migrate *into* the critical region (ie after the lock), and something after the unlock might similarly migrate to precede the unlock, so you could end up having out-of-order accesses across a lock/unlock sequence (that both happen "inside" the lock, but there is no guaranteed ordering between the two accesses themselves).

Or am I confused? The one major reason for strong memory ordering is that weak ordering is too f*cking easy to get wrong on a software level, and even people who know about it will make mistakes.

Actually, the weakest forms of locking only guarantee a consistent view of memory if you are actually holding the lock. Not "a" lock, but "the" lock.

So the three fixes I know of at the moment are:

1. Upgrade smp_store_release()'s PPC implementation from lwsync
to sync.

What about ARM? ARM platforms that have the load-acquire and store-release instructions could use them, but other ARM platforms have to use dmb. ARM avoids PPC's lwsync issue because it has no equivalent to lwsync.

2. Place an explicit smp_mb() into the MCS-lock queued handoff
code.

3. Remove the requirement that "unlock+lock" be a full memory
barrier.

We have been leaning towards #1, but before making any hard decision on this we are looking more closely at what the situation is on other architectures.

Quoted 4 lines · Paul E. McKenney

Actually, the weakest forms of locking only guarantee a consistent view of memory if you are actually holding the lock. Not "a" lock, but "the" lock.

I don't think we necessarily support any architecture that does that, though. And afaik, it's almost impossible to actually do sanely in hardware with any sane cache coherency, so..

So realistically, I think we only really need to worry about memory ordering that is tied to cache coherency protocols, where even locking rules tend to be about memory ordering (although extended rules like acquire/release rather than the broken pure barrier model).

Do you know any actual architecture where this isn't the case?

Quoted 4 lines

So the three fixes I know of at the moment are:

1. Upgrade smp_store_release()'s PPC implementation from lwsync
to sync.

Quoted 7 lines

What about ARM? ARM platforms that have the load-acquire and store-release instructions could use them, but other ARM platforms have to use dmb. ARM avoids PPC's lwsync issue because it has no equivalent to lwsync.

2. Place an explicit smp_mb() into the MCS-lock queued handoff
code.

Quoted 2 lines

3. Remove the requirement that "unlock+lock" be a full memory
barrier.

Quoted 3 lines

We have been leaning towards #1, but before making any hard decision on this we are looking more closely at what the situation is on other architectures.

So I might be inclined to lean towards #1 simply because of test coverage.

We have no sane test coverage of weakly ordered models. Sure, ARM may be weakly ordered (with saner acquire/release in ARM64), but realistically, no existing ARM platforms actually gives us any reasonable test *coverage* for things like this, despite having tons of chips out there running Linux. Very few people debug problems in that world. The PPC people probably have much better testing and are more likely to figure out the bugs, but don't have the pure number of machines. So x86 tends to still remain the main platform where serious testing gets done.

That said, I'd still be perfectly happy with #3, since - unlike, say, the PCI ordering issues with drivers - at least people *can* try to think about this somewhat analytically, even if it's ripe for confusion and subtle mistakes. And I still think you got the ordering wrong, and should be talking about "lock+unlock" rather than "unlock+lock".

It is not the architecture that matters here, it is just a definition of what ordering guarantees the locking primitives provide, independent of the architecture.

Quoted 4 lines · Paul E. McKenney

It is not the architecture that matters here, it is just a definition of what ordering guarantees the locking primitives provide, independent of the architecture.

So we definitely come from very different backgrounds.

I don't care one *whit* about theoretical lock orderings. Not a bit.

I do care deeply about reality, particularly of architectures that actually matter. To me, a spinlock in some theoretical case is uninteresting, but a efficient spinlock implementation on a real architecture is a big deal that matters a lot.

On Thu, Nov 21, 2013 at 08:25:59PM -0800, Linus Torvalds wrote:

[...]

Quoted 4 lines

I do care deeply about reality, particularly of architectures that actually matter. To me, a spinlock in some theoretical case is uninteresting, but a efficient spinlock implementation on a real architecture is a big deal that matters a lot.

Agreed, reality and efficiency are the prime concerns. Theory serves reality and efficiency, but definitely not the other way around.

But if we want locking primitives that don't rely solely on atomic instructions (such as the queued locks that people have been putting forward), we are going to need to wade through a fair bit of theory to make sure that they actually work on real hardware. Subtle bugs in locking primitives is a type of reality that I think we can both agree that we should avoid.

Or am I missing your point?

Quoted 13 lines · Paul E. McKenney

On Thu, Nov 21, 2013 at 08:25:59PM -0800, Linus Torvalds wrote:

[...]

Quoted 4 lines

I do care deeply about reality, particularly of architectures that actually matter. To me, a spinlock in some theoretical case is uninteresting, but a efficient spinlock implementation on a real architecture is a big deal that matters a lot.

Agreed, reality and efficiency are the prime concerns. Theory serves reality and efficiency, but definitely not the other way around.

Quoted 8 lines

But if we want locking primitives that don't rely solely on atomic instructions (such as the queued locks that people have been putting forward), we are going to need to wade through a fair bit of theory to make sure that they actually work on real hardware. Subtle bugs in locking primitives is a type of reality that I think we can both agree that we should avoid.

Or am I missing your point?

I think one point Linus wanted to make that it's not true that Linux has to offer a barrier and locking model that panders to the weakest (and craziest!) memory ordering model amongst all the possible Linux platforms - theoretical or real metal.

Instead what we want to do is to consciously, intelligently _pick_ a sane, maintainable memory model and offer primitives for that - at least as far as generic code is concerned. Each architecture can map those primitives to the best of its abilities.

Because as we increase abstraction, as we allow more and more complex memory ordering details, so does maintainability and robustness decrease. So there's a very real crossover point at which point increased smarts will actually hurt our code in real life.

[ Same goes for compilers, we draw a line: for example we generally
turn off strict aliasing optimizations, or we turn off NULL pointer check elimination optimizations. ]

I'm not saying this to not discuss theoretical complexities - I'm just saying that the craziest memory ordering complexities are probably best dealt with by agreeing not to use them ;-)

You see, my problem is not the "crazy ordering" DEC Alpha, Itanium, PowerPC, or even ARM. It is really obvious what instructions to use in a stiffened-up smp_store_release() for those guys: "mb" for DEC Alpha, "st.rel" for Itanium, "sync" for PowerPC, and "dmb" for ARM. Believe it or not, my problem is instead with good old tightly ordered x86.

We -could- just put an mfence into x86's smp_store_release() and be done with it

Quoted 7 lines · Paul E. McKenney

You see, my problem is not the "crazy ordering" DEC Alpha, Itanium, PowerPC, or even ARM. It is really obvious what instructions to use in a stiffened-up smp_store_release() for those guys: "mb" for DEC Alpha, "st.rel" for Itanium, "sync" for PowerPC, and "dmb" for ARM. Believe it or not, my problem is instead with good old tightly ordered x86.

Quoted 2 lines

We -could- just put an mfence into x86's smp_store_release() and be done with it

Why would you bother? The *acquire* has a memory barrier. End of story. On x86, it has to (since otherwise a load inside the locked region could be re-ordered wrt the write that takes the lock).

Basically, any time you think you need to add a memory barrier on x86, you should go "I'm doing something wrong". It's that simple.

Linus

I am sorry, but that is not always correct. For example, in the contended case for Tim Chen's MCS queued locks, the x86 acquisition-side handoff code does -not- contain any stores or memory-barrier instructions.

Quoted 4 lines · Paul E. McKenney

I am sorry, but that is not always correct. For example, in the contended case for Tim Chen's MCS queued locks, the x86 acquisition-side handoff code does -not- contain any stores or memory-barrier instructions.

So? In order to get *into* that contention code, you will have to go through the fast-case code. Which will contain a locked instruction.

So I repeat: a "lock" sequence will always be a memory barrier on x86.

Linus

Quoted 3 lines · Linus Torvalds

So? In order to get *into* that contention code, you will have to go through the fast-case code. Which will contain a locked instruction.

So you must also maintain ordering against the critical section that just ended on some other CPU.

Quoted 7 lines · Paul E. McKenney

Quoted 3 lines · Linus Torvalds

So? In order to get *into* that contention code, you will have to go through the fast-case code. Which will contain a locked instruction.

So you must also maintain ordering against the critical section that just ended on some other CPU.

But that's completely irrelevant to what you yourself have been saying in this thread.

Your stated concern in this thread been whether the "unlock+lock" sequence implies an ordering that is at least equivalent to a memory barrier. And it clearly does, because the lock clearly contains a memory barrier inside of it.

The fact that the locking sequence contains *other* things too is irrelevant for that question. Those other things are at most relevant then for *other* questions, ie from the standpoint of somebody wanting to convince himself that the locking actually works as a lock, but that wasn't what we were actually talking about earlier.

The x86 memory ordering doesn't follow the traditional theoretical operations, no. Tough. It's generally superior than the alternatives because of its somewhat unorthodox rules (in that it then makes the many other common barriers generally be no-ops). If you try to describe the x86 ops in terms of the theory, you will have pain. So just don't do it. Think of them in the context of their own rules, not somehow trying to translate them to non-x86 rules.

I think you can try to approximate the x86 rules as "every load is a RCpc acquire, every store is a RCpc release", and then to make yourself happier you can say that the lock sequence always starts out with a serializing operation (which is obviously the actual locked r-m-w op) so that on a lock/unlock level (as opposed to an individual memory op level) you get the RCsc behavior of the acquire/releases not re-ordering across separate locking events.

I'm not actually convinced that that is really a full and true description of the x86 semantics, but it may _approximate_ being true to the degree that you might translate it to some of the academic papers that talk about these things.

(Side note: this is also true when the locked r-m-w instruction has been replaced with a xbegin/xend. Intel documents that an RTM region has the "same ordering semantics as a LOCK prefixed instruction": see section 15.3.6 in the intel x86 architecture sw manual)

You seem to be assuming that the unlock+lock rule applies only when the unlock and the lock are executed by the same CPU. This is not always the case. For example, when the unlock and lock are operating on the same lock variable, the critical sections must appear to be ordered from the perspective of some other CPU, even when that CPU is not holding any lock.

Quoted 7 lines · Paul E. McKenney

You seem to be assuming that the unlock+lock rule applies only when the unlock and the lock are executed by the same CPU. This is not always the case. For example, when the unlock and lock are operating on the same lock variable, the critical sections must appear to be ordered from the perspective of some other CPU, even when that CPU is not holding any lock.

Umm. Isn't that pretty much *guaranteed* by any cache-coherent locking scheme.

The unlock - by virtue of being an unlock - means that all ops within the first critical region must be visible in the cache coherency protocol before the unlock is visible. Same goes for the lock on the other CPU wrt the memory accesses within that locked region.

IOW, I'd argue that any locking model that depends on cache coherency
- as opposed to some magic external locks independent of cache coherenecy - *has* to follow the rules in that section as far as I can see. Or it's not a locking model at all, and lets the cache accesses leak outside of the critical section.

Btw, you can see the difference in the very next section, where you have *non-cache-coherent* (IO) accesses. So once you have different rules for the data and the lock accesses, you can get different results. And yes, there have been broken SMP models (historically) where locking was "separate" from the memory system, and you could get coherence only by taking the right lock. But I really don't think we care about such locking models (for memory - again, IO accesses are different, exactly because locking and data are in different "ordering domains").

IOW, I don't think you *can* violate that "locks vs memory accesses" model with any system where locking is in the same ordering domain as the data (ie we lock by using cache coherency). And locking using cache coherency is imnsho the only valid model for SMP. No?

Start with Tim Chen's most recent patches for MCS locking, the ones that do the lock handoff using smp_store_release() and smp_load_acquire(). Add to that Peter Zijlstra's patch that uses PowerPC lwsync for both smp_store_release() and smp_load_acquire(). Run the resulting lock at high contention, so that all lock handoffs are done via the queue. Then you will have something that acts like a lock from the viewpoint of CPU holding that lock, but which does -not- guarantee that an unlock+lock acts like a full memory barrier if the unlock and lock run on two different CPUs, and if the observer is running on a third CPU.

Quoted 10 lines · Paul E. McKenney

Start with Tim Chen's most recent patches for MCS locking, the ones that do the lock handoff using smp_store_release() and smp_load_acquire(). Add to that Peter Zijlstra's patch that uses PowerPC lwsync for both smp_store_release() and smp_load_acquire(). Run the resulting lock at high contention, so that all lock handoffs are done via the queue. Then you will have something that acts like a lock from the viewpoint of CPU holding that lock, but which does -not- guarantee that an unlock+lock acts like a full memory barrier if the unlock and lock run on two different CPUs, and if the observer is running on a third CPU.

Umm. If the unlock and the lock run on different CPU's, then the lock handoff cannot be done through the queue (I assume that what you mean by "queue" is the write buffer).

And yes, the write buffer is why running unlock+lock on the *same* CPU is a special case and can generate more re-ordering than is visible externally (and I generally do agree that we should strive for serialization at that point), but even it does not actually violate the rules mentioned in Documentation/memory-barriers.txt wrt an external CPU because the write that releases the lock isn't actually visible at that point in the cache, and if the same CPU re-aquires it by doing a read that bypasses the write and hits in the write buffer or the unlock, the unlocked state in between won't even be seen outside of that CPU.

See? The local write buffer is special. It very much bypasses the cache, but the thing about it is that it's local to that CPU.

Now, I do have to admit that cache coherency protocols are really subtle, and there may be something else I'm missing, but the thing you brought up is not one of those things, afaik.

Linus

So there is your example. It really can and does happen.

Again, easy fix. Just change powerpc's smp_store_release() from lwsync to smp_mb(). That fixes the problem and doesn't hurt anyone but powerpc.

OK?

Quoted 7 lines · Paul E. McKenney

So there is your example. It really can and does happen.

Again, easy fix. Just change powerpc's smp_store_release() from lwsync to smp_mb(). That fixes the problem and doesn't hurt anyone but powerpc.

OK?

Hmm. Ok

Except now I'm worried it can happen on x86 too because my mental model was clearly wrong.

x86 does have that extra "Memory ordering obeys causality (memory ordering respects transitive visibility)." rule, and the example in the architecture manual (section 8.2.3.6 "Stores Are Transitively Visible") seems to very much about this, but your particular example is subtly different, so..

I will have to ruminate on this.

Quoted 5 lines

x86 does have that extra "Memory ordering obeys causality (memory ordering respects transitive visibility)." rule, and the example in the architecture manual (section 8.2.3.6 "Stores Are Transitively Visible") seems to very much about this, but your particular example is subtly different, so..

Indeed, my example needs CPU 1's -load- from y to be transitively visible, so I am nervous about this one as well.

Quoted 1 line

I will have to ruminate on this.

The rules on the left-hand column of page 5 of the below URL apply to this example more straightforwardly, but I don't know that Intel and AMD stand behind them:

	http://www.cl.cam.ac.uk/~pes20/weakmemory/cacm.pdf

My guess is that x86 does guarantee this ordering, but at this point I would have to ask someone from Intel and AMD.

Quoted 11 lines · Paul E. McKenney

Quoted 5 lines

x86 does have that extra "Memory ordering obeys causality (memory ordering respects transitive visibility)." rule, and the example in the architecture manual (section 8.2.3.6 "Stores Are Transitively Visible") seems to very much about this, but your particular example is subtly different, so..

Indeed, my example needs CPU 1's -load- from y to be transitively visible, so I am nervous about this one as well.

Quoted 1 line

I will have to ruminate on this.

Quoted 8 lines

The rules on the left-hand column of page 5 of the below URL apply to this example more straightforwardly, but I don't know that Intel and AMD stand behind them:

	http://www.cl.cam.ac.uk/~pes20/weakmemory/cacm.pdf

My guess is that x86 does guarantee this ordering, but at this point I would have to ask someone from Intel and AMD.

An additional option might be to create a user-space testcase engineered to hit all the exotic ordering situations, one that might disprove any particular assumptions we have about the behavior of hardware. (Back a decade ago when the x86 space first introduced quad core CPUs with newfangled on-die cache coherency I managed to demonstrate a causality violation by simulating kernel locks in user-space, which turned out to be a hardware bug. Also, when Hyperthreading/SMT was new it demonstrated many interesting bugs never seen in practice before. So running stuff on real hardware is useful.)

And a cache coherency (and/or locking) test suite would be very useful anyway, for so many other purposes as well: such as a new platform/CPU bootstrap, or to prove the correctness of some fancy new locking scheme people want to add. Maybe as an extension to rcutorture, or a generalization of it?

Quoted 34 lines · Ingo Molnar

Quoted 11 lines · Paul E. McKenney

Quoted 5 lines

x86 does have that extra "Memory ordering obeys causality (memory ordering respects transitive visibility)." rule, and the example in the architecture manual (section 8.2.3.6 "Stores Are Transitively Visible") seems to very much about this, but your particular example is subtly different, so..

Indeed, my example needs CPU 1's -load- from y to be transitively visible, so I am nervous about this one as well.

Quoted 1 line

I will have to ruminate on this.

Quoted 8 lines

The rules on the left-hand column of page 5 of the below URL apply to this example more straightforwardly, but I don't know that Intel and AMD stand behind them:

	http://www.cl.cam.ac.uk/~pes20/weakmemory/cacm.pdf

My guess is that x86 does guarantee this ordering, but at this point I would have to ask someone from Intel and AMD.

An additional option might be to create a user-space testcase engineered to hit all the exotic ordering situations, one that might disprove any particular assumptions we have about the behavior of hardware. (Back a decade ago when the x86 space first introduced quad core CPUs with newfangled on-die cache coherency I managed to demonstrate a causality violation by simulating kernel locks in user-space, which turned out to be a hardware bug. Also, when Hyperthreading/SMT was new it demonstrated many interesting bugs never seen in practice before. So running stuff on real hardware is useful.)

Quoted 5 lines

And a cache coherency (and/or locking) test suite would be very useful anyway, for so many other purposes as well: such as a new platform/CPU bootstrap, or to prove the correctness of some fancy new locking scheme people want to add. Maybe as an extension to rcutorture, or a generalization of it?

I have the locking counterpart of rcutorture on my todo list. ;-)

Of course, we cannot prove locks correct via testing, but a quick test can often find a bug faster and more reliably than manual inspection.

Quoted 43 lines · Paul E. McKenney

Quoted 34 lines · Ingo Molnar

Quoted 11 lines · Paul E. McKenney

Quoted 5 lines

x86 does have that extra "Memory ordering obeys causality (memory ordering respects transitive visibility)." rule, and the example in the architecture manual (section 8.2.3.6 "Stores Are Transitively Visible") seems to very much about this, but your particular example is subtly different, so..

Indeed, my example needs CPU 1's -load- from y to be transitively visible, so I am nervous about this one as well.

Quoted 1 line

I will have to ruminate on this.

Quoted 8 lines

The rules on the left-hand column of page 5 of the below URL apply to this example more straightforwardly, but I don't know that Intel and AMD stand behind them:

	http://www.cl.cam.ac.uk/~pes20/weakmemory/cacm.pdf

My guess is that x86 does guarantee this ordering, but at this point I would have to ask someone from Intel and AMD.

An additional option might be to create a user-space testcase engineered to hit all the exotic ordering situations, one that might disprove any particular assumptions we have about the behavior of hardware. (Back a decade ago when the x86 space first introduced quad core CPUs with newfangled on-die cache coherency I managed to demonstrate a causality violation by simulating kernel locks in user-space, which turned out to be a hardware bug. Also, when Hyperthreading/SMT was new it demonstrated many interesting bugs never seen in practice before. So running stuff on real hardware is useful.)

Quoted 5 lines

And a cache coherency (and/or locking) test suite would be very useful anyway, for so many other purposes as well: such as a new platform/CPU bootstrap, or to prove the correctness of some fancy new locking scheme people want to add. Maybe as an extension to rcutorture, or a generalization of it?

I have the locking counterpart of rcutorture on my todo list. ;-)

Quoted 3 lines

Of course, we cannot prove locks correct via testing, but a quick test can often find a bug faster and more reliably than manual inspection.

We cannot prove them correct via testing, but we can test our hypothesis about how the platform works and chances are that if the tests are smart enough then we will be proven wrong via an actual failure if our assumptions are wrong.

But this does -not- guarantee that some other non-lock-holding CPU 2 will see CS0 and CS1 in order. To see this, let's fill in the two critical sections, where variables X and Y are both initially zero:

        CPU 0 (releasing)       CPU 1 (acquiring)
        -----                   -----
        ACCESS_ONCE(X) = 1;     while (ACCESS_ONCE(lock) == 1)
        lwsync                          continue;
        ACCESS_ONCE(lock) = 0;  lwsync
                                r1 = ACCESS_ONCE(Y);

Then let's add in the observer CPU 2:

        CPU 2
        -----
        ACCESS_ONCE(Y) = 1;
        sync
        r2 = ACCESS_ONCE(X);

If unlock+lock act as a full memory barrier, it would be impossible to end up with (r1 == 0 && r2 == 0). After all, (r1 == 0) implies that CPU 2's store to Y happened after CPU 1's load from Y, and (r2 == 0) implies that CPU 0's load from X happened after CPU 2's store to X. If CPU 0's unlock combined with CPU 1's lock really acted like a full memory barrier, we end up with CPU 0's load happening before CPU 1's store happening before CPU 2's store happening before CPU 2's load happening before CPU 0's load.

However, the outcome (r1 == 0 && r2 == 0) really does happen both in theory and on real hardware.

And as far as I can tell, the above gives you: A < B < C < D < E < F < A. Which doesn't look possible.

Quoted 3 lines · Linus Torvalds

And as far as I can tell, the above gives you: A < B < C < D < E < F < A. Which doesn't look possible.

Hmm.. I guess technically all of those cases aren't "strictly precedes" as much as "cannot have happened in the opposite order". So the "<" might be "<=". Which I guess *is* possible: "it all happened at the same time". And then the difference between your suggested "lwsync" and "sync" in the unlock path on CPU0 basically approximating the difference between "A <= B" and "A < B"..

Ho humm.

Quoted 6 lines · Linus Torvalds

Quoted 3 lines · Linus Torvalds

And as far as I can tell, the above gives you: A < B < C < D < E < F < A. Which doesn't look possible.

Quoted 8 lines

Hmm.. I guess technically all of those cases aren't "strictly precedes" as much as "cannot have happened in the opposite order". So the "<" might be "<=". Which I guess *is* possible: "it all happened at the same time". And then the difference between your suggested "lwsync" and "sync" in the unlock path on CPU0 basically approximating the difference between "A <= B" and "A < B"..

Ho humm.

But remember, there's an actual full proper barrier between E and F, so at best you'd end up with something like:

A <= B <= C <= D <= E < F <= A

Which is still an impossibility.

I'm hoping others will explain things, as I'm very much on shaky ground myself wrt transitivity.

Hi Peter, Linus,

Quoted 19 lines · Peter Zijlstra

Quoted 6 lines · Linus Torvalds

Quoted 3 lines · Linus Torvalds

And as far as I can tell, the above gives you: A < B < C < D < E < F < A. Which doesn't look possible.

Quoted 8 lines

Hmm.. I guess technically all of those cases aren't "strictly precedes" as much as "cannot have happened in the opposite order". So the "<" might be "<=". Which I guess *is* possible: "it all happened at the same time". And then the difference between your suggested "lwsync" and "sync" in the unlock path on CPU0 basically approximating the difference between "A <= B" and "A < B"..

Ho humm.

But remember, there's an actual full proper barrier between E and F, so at best you'd end up with something like:

Quoted 6 lines

A <= B <= C <= D <= E < F <= A

Which is still an impossibility.

I'm hoping others will explain things, as I'm very much on shaky ground myself wrt transitivity.

The transitivity issues come about by having multiple, valid copies of the same data at a given moment in time (hence the term `multi-copy atomicity', where all of these copies appear to be updated at once).

Now, I'm not familiar with the Power memory model and the implementation intricacies between lwsync and sync, but I think a better way to think about this is to think of the cacheline state changes being broadcast as asynchronous requests, rather than necessarily responding to snoops from a canonical source.

So, in Paul's example, the upgrade requests on X and lock (shared -> invalid) may have reached CPU1, but not CPU2 by the time CPU2 reads X and therefore reads 0 from its shared line. It really depends on the multi-copy semantics you give to the different barrier instructions.

The other thing worth noting is that exclusive access instructions (e.g. ldrex and strex on ARM) may interact differently with barriers than conventional accesses, so lighter weight barriers can sometimes be acceptable for things like locks and atomics.

Does that help at all?

Will

Quoted 3 lines · Linus Torvalds

And as far as I can tell, the above gives you: A < B < C < D < E < F < A. Which doesn't look possible.

Hmm.. I guess technically all of those cases aren't "strictly precedes" as much as "cannot have happened in the opposite order". So the "<" might be "<=". Which I guess *is* possible: "it all happened at the same time". And then the difference between your suggested "lwsync" and "sync" in the unlock path on CPU0 basically approximating the difference between "A <= B" and "A < B"..

Ho humm.

*SOME* assumption of mine must be wrong. But I don't see which one.

I haven't read your email in full detail yet, but one thing I did miss was cache-snoops.

One of the reasons for failing transitive / multi-copy atomicity is that CPUs might have different views of the memory state depending on from which caches they can get snoops.

Quoted 29 lines · Paul E. McKenney

But this does -not- guarantee that some other non-lock-holding CPU 2 will see CS0 and CS1 in order. To see this, let's fill in the two critical sections, where variables X and Y are both initially zero:

        CPU 0 (releasing)       CPU 1 (acquiring)
        -----                   -----
        ACCESS_ONCE(X) = 1;     while (ACCESS_ONCE(lock) == 1)
        lwsync                          continue;
        ACCESS_ONCE(lock) = 0;  lwsync
                                r1 = ACCESS_ONCE(Y);

Then let's add in the observer CPU 2:

        CPU 2
        -----
        ACCESS_ONCE(Y) = 1;
        sync
        r2 = ACCESS_ONCE(X);

If unlock+lock act as a full memory barrier, it would be impossible to end up with (r1 == 0 && r2 == 0). After all, (r1 == 0) implies that CPU 2's store to Y happened after CPU 1's load from Y, and (r2 == 0) implies that CPU 0's load from X happened after CPU 2's store to X. If CPU 0's unlock combined with CPU 1's lock really acted like a full memory barrier, we end up with CPU 0's load happening before CPU 1's store happening before CPU 2's store happening before CPU 2's load happening before CPU 0's load.

Quoted 2 lines

However, the outcome (r1 == 0 && r2 == 0) really does happen both in theory and on real hardware.

Ok, so I have ruminated.

But even after having ruminated, the one thing I cannot find is support for your "(r1 == 0 && r2 == 0) really does happen on hardware".

Ignore theory, and assume just cache coherency,

ie the notion that in
order to write to a cacheline, you have to have that cacheline in some exclusive state. We have three cachelines, X, Y and lock (and our cachelines only have a single bit, starting out as 0,0,1 respectively).

CPU0:

   write X = 1;
   lwsync
   write lock = 0;

doesn't even really require any cache accesses at all per se, but it *does* require that the two stores be ordered in the store buffer on CPU0 in such a way that cacheline X gets updated (ie is in exclusive/dirty state in CPU0 with the value 1) before cacheline 'lock' gets released from its exclusive/dirty state after having itself been updated to 0.

So basically we know that *within* CPU0, by the time the lock actually makes it out of the CPU, the cacheline containing X will have been in dirty mode with the value "1".

The core might actually have written
'lock' first, but it can't release that cacheline from exclusive state (so that it is visible anywhere else) until it has _also_ gotten 'X' into exclusive state (once both cachelines are exclusive within CPU0, it can do any ordering, because the ordering won't be externally visible).

And this is all just looking at CPU0, nothing else. But if it is exclusive/dirty on CPU0, then it cannot be shared in any other CPU (although a previous stale value may obviously still be "in flight" somewhere else outside of the coherency domain).

So let's look at CPU2, which is similar, but now the second access is a read (of zero), not a write:

CPU2:
write Y = 1;
sync
read X as zero

So if 'sync' is a true memory barrier between the write and the read, then we know that the following is true: CPU2 must have gotten cacheline 'Y' into exclusive state and acquired (or held on to, which is equivalent) cacheline 'X' in shared state _after_ it got that Y into exclusive state. It can't rely on some "in flight" previously read value of 'X' until after it got Y into exclusive state. Otherwise it wouldn't be a ordering between the write and the read, agreed?

The pattern on CPU1, meanwhile, is somewhat different. But I'm going to ignore the "while" part, and just concentrate on the last iteration of the loop, and it turns into:

CPU1:
read lock as zero
lwsync
read Y as zero

It only does reads, so it is happy with a shared cacheline, but in order for the lwsync to actually act as an acquire, it does mean that the cacheline 'Y' needs to be in some shared state within the cache coherency domain after (or, again, across) cacheline 'lock' having been in a shared state with value == 0 on CPU1. No "in flight" values.

Agreed?

So the above isn't really about lwsync/sync/memory ordering any more, the above is basically rewriting things purely about cacheline states as seen by individual processors. And I know the POWER cache coherency is really complex (iirc cachelines can have 11+ states - we're not talking about MOESI any more), but even there you have to have a notion of "exclusive access" to be able to write in the end. So my states are certainly simplified, but I don't see how that basic rule can be violated (and still be called cache coherent).

And let's just look at the individual "events" on these CPU's:

- A = CPU0 acquires exclusive access to cacheline X (in order to
write 1 into it)
- B = CPU0 releases its exclusive access to cacheline lock (after
having written 0 into it)
- C = CPU1 reads shared cacheline lock as being zero
- D = CPU1 reads shared cacheline Y as being zero
- E = CPU2 acquires exclusive access to cacheline Y (in order to
write 1 into it)
- F = CPU2 reads shared cacheline X as being zero

and you cannot order these events arbitrarily, but there *ARE* certain orderings you can rely on:

- within a CPU due to the barriers. This gives you

A < B, C < D and E < F

- with regards to a particular cacheline because of that cacheline
coming exclusive (or, in the case of 'B', moving out of exclusive state) and the value it has at that point:

B < C, F < A and D < E

And as far as I can tell, the above gives you: A < B < C < D < E < F < A. Which doesn't look possible.

So which step in my rumination here is actually wrong? Because I really don't see how you can get that "(r1 == 0 && r2 == 0)" on real hardware using cache coherency.

*SOME* assumption of mine must be wrong. But I don't see which one.

Linus

but the lwsync instructions do not order prior stores against later loads.

Quoted 9 lines

Hmm, so in the following case:

Access A
unlock() /* release semantics */
lock() /* acquire semantics */
Access B

A cannot pass beyond the unlock() and B cannot pass the before the lock().

Quoted 7 lines

I agree that accesses between the unlock and the lock can be move across both A and B, but that doesn't seem to matter by my reading of the above.

What is the problematic scenario you have in mind? Are you thinking of the lock() moving before the unlock()? That's only permitted by RCpc afaiu, which I don't think any architectures supported by Linux implement... (ARMv8 acquire/release is RCsc).

If smp_load_acquire() and smp_store_release() are both implemented using lwsync on powerpc, and if Access A is a store and Access B is a load, then Access A and Access B can be reordered.

Of course, if every other architecture will be providing RCsc implementations for smp_load_acquire() and smp_store_release(), which would not be a bad thing, then another approach is for powerpc to use sync rather than lwsync for one or the other of smp_load_acquire() or smp_store_release().

Quoted 17 lines · Paul E. McKenney

Quoted 9 lines

Hmm, so in the following case:

Access A
unlock() /* release semantics */
lock() /* acquire semantics */
Access B

A cannot pass beyond the unlock() and B cannot pass the before the lock().

Quoted 7 lines

I agree that accesses between the unlock and the lock can be move across both A and B, but that doesn't seem to matter by my reading of the above.

What is the problematic scenario you have in mind? Are you thinking of the lock() moving before the unlock()? That's only permitted by RCpc afaiu, which I don't think any architectures supported by Linux implement... (ARMv8 acquire/release is RCsc).

Quoted 8 lines

If smp_load_acquire() and smp_store_release() are both implemented using lwsync on powerpc, and if Access A is a store and Access B is a load, then Access A and Access B can be reordered.

Of course, if every other architecture will be providing RCsc implementations for smp_load_acquire() and smp_store_release(), which would not be a bad thing, then another approach is for powerpc to use sync rather than lwsync for one or the other of smp_load_acquire() or smp_store_release().

So which of the two would make most sense?

As per the Document, loads/stores should not be able to pass up through an ACQUIRE and loads/stores should not be able to pass down through a RELEASE.

I think PPC would match that if we use sync for smp_store_release() such that it will flush the store buffer, and thereby guarantee all stores are kept within the required section.

Quoted 33 lines · Peter Zijlstra

Quoted 17 lines · Paul E. McKenney

Quoted 9 lines

Hmm, so in the following case:

Access A
unlock() /* release semantics */
lock() /* acquire semantics */
Access B

A cannot pass beyond the unlock() and B cannot pass the before the lock().

Quoted 7 lines

I agree that accesses between the unlock and the lock can be move across both A and B, but that doesn't seem to matter by my reading of the above.

What is the problematic scenario you have in mind? Are you thinking of the lock() moving before the unlock()? That's only permitted by RCpc afaiu, which I don't think any architectures supported by Linux implement... (ARMv8 acquire/release is RCsc).

Quoted 8 lines

If smp_load_acquire() and smp_store_release() are both implemented using lwsync on powerpc, and if Access A is a store and Access B is a load, then Access A and Access B can be reordered.

Of course, if every other architecture will be providing RCsc implementations for smp_load_acquire() and smp_store_release(), which would not be a bad thing, then another approach is for powerpc to use sync rather than lwsync for one or the other of smp_load_acquire() or smp_store_release().

So which of the two would make most sense?

As per the Document, loads/stores should not be able to pass up through an ACQUIRE and loads/stores should not be able to pass down through a RELEASE.

Quoted 3 lines

I think PPC would match that if we use sync for smp_store_release() such that it will flush the store buffer, and thereby guarantee all stores are kept within the required section.

Wouldn't that also mean that TSO archs need the full barrier on RELEASE?

Quoted 34 lines · Peter Zijlstra

Quoted 33 lines · Peter Zijlstra

Quoted 17 lines · Paul E. McKenney

Quoted 9 lines

Hmm, so in the following case:

Access A
unlock() /* release semantics */
lock() /* acquire semantics */
Access B

A cannot pass beyond the unlock() and B cannot pass the before the lock().

Quoted 7 lines

I agree that accesses between the unlock and the lock can be move across both A and B, but that doesn't seem to matter by my reading of the above.

What is the problematic scenario you have in mind? Are you thinking of the lock() moving before the unlock()? That's only permitted by RCpc afaiu, which I don't think any architectures supported by Linux implement... (ARMv8 acquire/release is RCsc).

Quoted 8 lines

If smp_load_acquire() and smp_store_release() are both implemented using lwsync on powerpc, and if Access A is a store and Access B is a load, then Access A and Access B can be reordered.

Of course, if every other architecture will be providing RCsc implementations for smp_load_acquire() and smp_store_release(), which would not be a bad thing, then another approach is for powerpc to use sync rather than lwsync for one or the other of smp_load_acquire() or smp_store_release().

So which of the two would make most sense?

As per the Document, loads/stores should not be able to pass up through an ACQUIRE and loads/stores should not be able to pass down through a RELEASE.

Quoted 6 lines

Quoted 3 lines

I think PPC would match that if we use sync for smp_store_release() such that it will flush the store buffer, and thereby guarantee all stores are kept within the required section.

Wouldn't that also mean that TSO archs need the full barrier on RELEASE?

It just might... I was thinking not, but I do need to check.

I am still thinking not, at least for x86, given Section 8.2.2 of "Intel® 64 and IA-32 Architectures Developer's Manual: Vol. 3A" dated March 2013 from:

http://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-software-developer-vol-3a-part-1-manual.html

Also from Sewell et al. "x86-TSO: A Rigorous and Usable Programmer's Model for x86 Multiprocessors" in 2010 CACM.

Let's apply the Intel manual to the earlier example:

	CPU 0		CPU 1			CPU 2
	-----		-----			-----
	x = 1;		r1 = SLA(lock);		y = 1;
	SSR(lock, 1);	r2 = y;			smp_mb();
						r3 = x;

	assert(!(r1 == 1 && r2 == 0 && r3 == 0));

Let's try applying this to x86:

o Stores from a given processor are ordered, so everyone
agrees that CPU 0's store to x happens before the store-release to lock.

o Reads from a given processor are ordered, so everyone agrees
that CPU 1's load from lock precedes its load from y.

o Because r1 == 1, we know that CPU 0's store to lock happened
before CPU 1's load from lock.

o Causality (AKA transitive visibility) means that everyone
agrees that CPU 0's store to x happens before CPU 1's load from y. (This is a crucial point, so it would be good to have confirmation/debunking from someone who understands the x86 architecture better than I do.)

o CPU 2's memory barrier prohibits CPU 2's store to y from
being reordered with its load from x.

o Because r2 == 0, we know that CPU 1's load from y happened
before CPU 2's store to y.

o At this point, it looks to me that (r1 == 1 && r2 == 0)

	implies r3 == 1.

Sewell's model plays out as follows:

o Rule 2 never applies in this example because no processor
is reading its own write.

o Rules 3 and 4 force CPU 0's writes to be seen in order.

o Rule 1 combined with the ordered-instruction nature of
the model force CPU 1's reads to happen in order.

o Rule 4 means that if r1 == 1, CPU 0's write to x is
globally visible before CPU 1 loads from y.

o The fact that r2 == 0 combined with rules 1, 3, and 4
mean that CPU 1's load from y happens before CPU 2 makes its store to y visible.

o Rule 5 means that CPU 1 cannot execute its load from x
until it has made its store to y globally visible.

o Therefore, when CPU 2 executes its load from x, CPU 0's

	store to x must be visible, ruling out r3 == 0, and
	preventing the assertion from firing.

The other three orderings would play out similarly. (These are read before lock release and read after subsequent lock acquisition, read before lock release and write after subsequent lock acquisition, and read before lock release and read after subsequent lock acquisition.)

But before chasing those down, is the analysis above sound?

Quoted 6 lines · Paul E. McKenney

I am still thinking not, at least for x86, given Section 8.2.2 of "Intel® 64 and IA-32 Architectures Developer's Manual: Vol. 3A" dated March 2013 from:

http://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-software-developer-vol-3a-part-1-manual.html

Quoted 2 lines

Also from Sewell et al. "x86-TSO: A Rigorous and Usable Programmer's Model for x86 Multiprocessors" in 2010 CACM.

Should be this one:

http://www.cl.cam.ac.uk/~pes20/weakmemory/cacm.pdf

And the rules referenced below are on page 5; left-hand column.

Quoted 66 lines

Let's apply the Intel manual to the earlier example:

	CPU 0		CPU 1			CPU 2
	-----		-----			-----
	x = 1;		r1 = SLA(lock);		y = 1;
	SSR(lock, 1);	r2 = y;			smp_mb();
						r3 = x;

	assert(!(r1 == 1 && r2 == 0 && r3 == 0));

Let's try applying this to x86:

o Stores from a given processor are ordered, so everyone
agrees that CPU 0's store to x happens before the store-release to lock.

o Reads from a given processor are ordered, so everyone agrees
that CPU 1's load from lock precedes its load from y.

o Because r1 == 1, we know that CPU 0's store to lock happened
before CPU 1's load from lock.

o Causality (AKA transitive visibility) means that everyone
agrees that CPU 0's store to x happens before CPU 1's load from y. (This is a crucial point, so it would be good to have confirmation/debunking from someone who understands the x86 architecture better than I do.)

o CPU 2's memory barrier prohibits CPU 2's store to y from
being reordered with its load from x.

o Because r2 == 0, we know that CPU 1's load from y happened
before CPU 2's store to y.

o At this point, it looks to me that (r1 == 1 && r2 == 0)

	implies r3 == 1.

Sewell's model plays out as follows:

o Rule 2 never applies in this example because no processor
is reading its own write.

o Rules 3 and 4 force CPU 0's writes to be seen in order.

o Rule 1 combined with the ordered-instruction nature of
the model force CPU 1's reads to happen in order.

o Rule 4 means that if r1 == 1, CPU 0's write to x is
globally visible before CPU 1 loads from y.

o The fact that r2 == 0 combined with rules 1, 3, and 4
mean that CPU 1's load from y happens before CPU 2 makes its store to y visible.

o Rule 5 means that CPU 1 cannot execute its load from x
until it has made its store to y globally visible.

o Therefore, when CPU 2 executes its load from x, CPU 0's

	store to x must be visible, ruling out r3 == 0, and
	preventing the assertion from firing.

The other three orderings would play out similarly. (These are read before lock release and read after subsequent lock acquisition, read before lock release and write after subsequent lock acquisition, and read before lock release and read after subsequent lock acquisition.)

Quoted 1 line

But before chasing those down, is the analysis above sound?

I _think_ so.. but its late. I'm also struggling to find where lwsync goes bad in this story, because as you say lwsync does all except flush the store buffer, which sounds like TSO.. but clearly is not quite the same.

For one TSO has multi-copy atomicity, whereas ARM/PPC do not have this.

The explanation of lwsync given in 3.3 of 'A Tutorial Introduction to the ARM and POWER Relaxed Memory Models'

http://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test7.pdf

Leaves me slightly puzzled as to the exact differences between the 2 WW variants.

Anyway, hopefully a little sleep will cure some of my confusion, otherwise I'll try and confuse you more tomorrow ;-)

Quoted 28 lines

Quoted 28 lines

Let's apply the Intel manual to the earlier example:

	CPU 0		CPU 1			CPU 2
	-----		-----			-----
	x = 1;		r1 = SLA(lock);		y = 1;
	SSR(lock, 1);	r2 = y;			smp_mb();
						r3 = x;

	assert(!(r1 == 1 && r2 == 0 && r3 == 0));

Let's try applying this to x86:

o Stores from a given processor are ordered, so everyone
agrees that CPU 0's store to x happens before the store-release to lock.

o Reads from a given processor are ordered, so everyone agrees
that CPU 1's load from lock precedes its load from y.

o Because r1 == 1, we know that CPU 0's store to lock happened
before CPU 1's load from lock.

o Causality (AKA transitive visibility) means that everyone
agrees that CPU 0's store to x happens before CPU 1's load from y. (This is a crucial point, so it would be good to have confirmation/debunking from someone who understands the x86 architecture better than I do.)

Quoted 8 lines

Quoted 8 lines

o CPU 2's memory barrier prohibits CPU 2's store to y from
being reordered with its load from x.

o Because r2 == 0, we know that CPU 1's load from y happened
before CPU 2's store to y.

o At this point, it looks to me that (r1 == 1 && r2 == 0)

	implies r3 == 1.

Quoted 1 line

Quoted 1 line

Sewell's model plays out as follows:

Quoted 1 line

Quoted 1 line

o Rules 3 and 4 force CPU 0's writes to be seen in order.

Quoted 6 lines

I _think_ so.. but its late. I'm also struggling to find where lwsync goes bad in this story, because as you say lwsync does all except flush the store buffer, which sounds like TSO.. but clearly is not quite the same.

For one TSO has multi-copy atomicity, whereas ARM/PPC do not have this.

At least PPC lwsync does not have multi-copy atomicity.

The heavier sync
instruction does. Last I checked, ARM did not have a direct replacment for lwsync, though it does have something sort of like eieio.

But yes, we were trying to use lwsync for both smp_load_acquire() and smp_store_release(), which does not provide exactly the same guarantees that TSO does. Though it does come close in many cases.

Quoted 7 lines

The explanation of lwsync given in 3.3 of 'A Tutorial Introduction to the ARM and POWER Relaxed Memory Models'

http://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test7.pdf

Leaves me slightly puzzled as to the exact differences between the 2 WW variants.

The WW at the top of the page is discussing the ARM "dmb" instruction and the PPC "sync" instruction, both of which are full barriers, and both of which can therefore be thought of as flushing the store buffer.

In contrast, the WW at the bottom of the page is discussing the PPC lwsync instruction, which most definitely is not guaranteed to flush the write buffer.

Quoted 34 lines · Paul E. McKenney

Quoted 34 lines

Quoted 34 lines

Let's apply the Intel manual to the earlier example:

	CPU 0		CPU 1			CPU 2
	-----		-----			-----
	x = 1;		r1 = SLA(lock);		y = 1;
	SSR(lock, 1);	r2 = y;			smp_mb();
						r3 = x;

	assert(!(r1 == 1 && r2 == 0 && r3 == 0));

Let's try applying this to x86:

o Stores from a given processor are ordered, so everyone
agrees that CPU 0's store to x happens before the store-release to lock.

o Reads from a given processor are ordered, so everyone agrees
that CPU 1's load from lock precedes its load from y.

o Because r1 == 1, we know that CPU 0's store to lock happened
before CPU 1's load from lock.

o Causality (AKA transitive visibility) means that everyone
agrees that CPU 0's store to x happens before CPU 1's load from y. (This is a crucial point, so it would be good to have confirmation/debunking from someone who understands the x86 architecture better than I do.)

o CPU 2's memory barrier prohibits CPU 2's store to y from
being reordered with its load from x.

o Because r2 == 0, we know that CPU 1's load from y happened
before CPU 2's store to y.

Quoted 2 lines

Quoted 2 lines

Quoted 2 lines

o At this point, it looks to me that (r1 == 1 && r2 == 0)

	implies r3 == 1.

Agreed, and I now fully appreciate the transitive point. I can't say if x86 does in fact do this, but I can agree that rules in the SDM support your logic.

Quoted 1 line

Quoted 1 line

Quoted 1 line

Sewell's model plays out as follows:

I have problems with these rules, for instance:

Quoted 1 line

Quoted 1 line

Quoted 1 line

o Rules 3 and 4 force CPU 0's writes to be seen in order.

Nothing in those rules state the store buffer is a strict FIFO, it might be suggested by rule 4's use of 'oldest', but being a pendant the text as given doesn't disallow store reordering in the store buffer.

Suppose an address a was written to two times, a store buffer might simply update the entry for the first write with the new value. The entry would still become oldest at some point and get flushed.

(Note the above is ambiguous in if the entry's time stamp is updated or not -- also note that both cases violate TSO and therefore it doesn't matter.)

That violates FIFO (and TSO) but not the definitions.

Similarly its not at all clear from rule 2 that reads are not re-ordered.

So I'll ignore this section for now.

OK, so reading back a little he does describe the abstract machine and does say the store buffer is FIFO, but what use are rules if you first need more 'rules'.

Rules should be self supporting.

Quoted 8 lines

Quoted 6 lines

I _think_ so.. but its late. I'm also struggling to find where lwsync goes bad in this story, because as you say lwsync does all except flush the store buffer, which sounds like TSO.. but clearly is not quite the same.

For one TSO has multi-copy atomicity, whereas ARM/PPC do not have this.

At least PPC lwsync does not have multi-copy atomicity.

Right, which is why it lacks transitivity.

Quoted 4 lines

The heavier sync
instruction does. Last I checked, ARM did not have a direct replacment for lwsync, though it does have something sort of like eieio.

Quoted 3 lines

But yes, we were trying to use lwsync for both smp_load_acquire() and smp_store_release(), which does not provide exactly the same guarantees that TSO does. Though it does come close in many cases.

Right, and this lack of transitivity is what kills it.

Quoted 8 lines

Quoted 7 lines

The explanation of lwsync given in 3.3 of 'A Tutorial Introduction to the ARM and POWER Relaxed Memory Models'

http://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test7.pdf

Leaves me slightly puzzled as to the exact differences between the 2 WW variants.

Quoted 7 lines

The WW at the top of the page is discussing the ARM "dmb" instruction and the PPC "sync" instruction, both of which are full barriers, and both of which can therefore be thought of as flushing the store buffer.

In contrast, the WW at the bottom of the page is discussing the PPC lwsync instruction, which most definitely is not guaranteed to flush the write buffer.

Right, my complaint was that from the two definitions given the factual difference in behaviour was not clear to me.

I knew that upgrading the SSR's lwsync to sync would 'fix' the thing, and that is exactly the WW case, but given these two definitions I was at a loss to find the hole.

The real source of my cognitive pain is that here we have a sequence of code that has neither atomic instructions or memory-barrier instructions, but it looks like it still manages to act as a full memory barrier. Still not quite sure I should trust it...

Quoted 4 lines · Paul E. McKenney

The real source of my cognitive pain is that here we have a sequence of code that has neither atomic instructions or memory-barrier instructions, but it looks like it still manages to act as a full memory barrier. Still not quite sure I should trust it...

Yes, this is something that puzzles me too.

That said, the two rules that:

1) stores aren't re-ordered against other stores
2) reads aren't re-ordered against other reads

Do make that:

STORE x
LOAD x

form a fence that neither stores nor loads can pass through from either side; note however that they themselves rely on the data dependency to not reorder against themselves.

If you put them the other way around:

LOAD x
STORE y

we seem to get a stronger variant because stores are not re-ordered against older reads.

There is however the exception cause for rule 1) above, which includes clflush, non-temporal stores and string ops; the actual mfence instruction doesn't seem to have this exception and would thus be slightly stronger still.

Still confusion situation all round.

Quoted 4 lines · Paul E. McKenney

The real source of my cognitive pain is that here we have a sequence of code that has neither atomic instructions or memory-barrier instructions, but it looks like it still manages to act as a full memory barrier. Still not quite sure I should trust it...

Yes, this is something that puzzles me too.

That said, the two rules that:

1) stores aren't re-ordered against other stores
2) reads aren't re-ordered against other reads

Do make that:

STORE x
LOAD x

form a fence that neither stores nor loads can pass through from either side; note however that they themselves rely on the data dependency to not reorder against themselves.

If you put them the other way around:

LOAD x
STORE y

we seem to get a stronger variant because stores are not re-ordered against older reads.

There is however the exception cause for rule 1) above, which includes clflush, non-temporal stores and string ops; the actual mfence instruction doesn't seem to have this exception and would thus be slightly stronger still.

Still confusion situation all round.

Quoted 30 lines · Peter Zijlstra

Quoted 4 lines · Paul E. McKenney

The real source of my cognitive pain is that here we have a sequence of code that has neither atomic instructions or memory-barrier instructions, but it looks like it still manages to act as a full memory barrier. Still not quite sure I should trust it...

Yes, this is something that puzzles me too.

That said, the two rules that:

1) stores aren't re-ordered against other stores
2) reads aren't re-ordered against other reads

Do make that:

STORE x
LOAD x

form a fence that neither stores nor loads can pass through from either side; note however that they themselves rely on the data dependency to not reorder against themselves.

If you put them the other way around:

LOAD x
STORE y

we seem to get a stronger variant because stores are not re-ordered against older reads.

Quoted 6 lines

There is however the exception cause for rule 1) above, which includes clflush, non-temporal stores and string ops; the actual mfence instruction doesn't seem to have this exception and would thus be slightly stronger still.

Still confusion situation all round.

I think this means x86 needs help too.

Consider:

x = y = 0

  w[x] = 1  |  w[y] = 1
  mfence    |  mfence
  r[y] = 0  |  r[x] = 0

This is generally an impossible case, right? (Since if we observe y=0 this means that w[y]=1 has not yet happened, and therefore x=1, and vice-versa).

Now replace one of the mfences with smp_store_release(l1); smp_load_acquire(l2); such that we have a RELEASE+ACQUIRE pair that _should_ form a full barrier:

  w[x] = 1   | w[y] = 1
  w[l1] = 1  | mfence
  r[l2] = 0  | r[x] = 0
  r[y] = 0   |

At which point we can observe the impossible, because as per the rule:

'reads may be reordered with older writes to different locations'

Our r[y] can slip before the w[x]=1.

Thus x86's smp_store_release() would need to be:

(quoted diff) +6 -0

+#define smp_store_release(p, v)						\
+do {									\
+	compiletime_assert_atomic_type(*p);				\
+	smp_mb();							\
+	ACCESS_ONCE(*p) = (v);						\
+} while (0)

Or: (void)xchg((p), (v));

Idem for s390 and sparc I suppose.

The only reason your example worked is because the unlock and lock were for the same lock.

This of course leaves us without joy for circular buffers, which can do without this LOCK'ed op and without sync on PPC. Now I'm not at all sure we've got enough of those to justify primitives just for them.

I still do not believe that it does. Again, strangely enough.

We need to ask someone in Intel that understands this all the way down to the silicon. The guy I used to rely on for this no longer works at Intel.

Do you know someone who fits this description, or should I start sending cold-call emails to various Intel contacts?

Quoted 6 lines · Paul E. McKenney

I still do not believe that it does. Again, strangely enough.

We need to ask someone in Intel that understands this all the way down to the silicon. The guy I used to rely on for this no longer works at Intel.

Quoted 2 lines

Do you know someone who fits this description, or should I start sending cold-call emails to various Intel contacts?

There's a whole bunch of Intel folks on the Cc. list; could one of you find a suitable HW engineer and put him onto this thread?

And if the two locks are different, then the guarantee applies only when the unlock and lock are on the same CPU, in which case, as Linus noted, the xchg() on entry to the slow path does the job for use.

Quoted 3 lines · Paul E. McKenney

And if the two locks are different, then the guarantee applies only when the unlock and lock are on the same CPU, in which case, as Linus noted, the xchg() on entry to the slow path does the job for use.

But in that case we rely on the fact that the thing is part of a composite and we should no longer call it load_acquire, because frankly it doesn't have acquire semantics anymore because the read can escape out.

Quoted 9 lines · Peter Zijlstra

Quoted 3 lines · Paul E. McKenney

And if the two locks are different, then the guarantee applies only when the unlock and lock are on the same CPU, in which case, as Linus noted, the xchg() on entry to the slow path does the job for use.

But in that case we rely on the fact that the thing is part of a composite and we should no longer call it load_acquire, because frankly it doesn't have acquire semantics anymore because the read can escape out.

Actually, load-acquire and store-release are only required to provide ordering in the threads/CPUs doing the load-acquire/store-release operations. It is just that we require something stronger than minimal load-acquire/store-release to make a Linux-kernel lock.

Quoted 11 lines · Paul E. McKenney

Quoted 9 lines · Peter Zijlstra

Quoted 3 lines · Paul E. McKenney

And if the two locks are different, then the guarantee applies only when the unlock and lock are on the same CPU, in which case, as Linus noted, the xchg() on entry to the slow path does the job for use.

But in that case we rely on the fact that the thing is part of a composite and we should no longer call it load_acquire, because frankly it doesn't have acquire semantics anymore because the read can escape out.

Quoted 4 lines

Actually, load-acquire and store-release are only required to provide ordering in the threads/CPUs doing the load-acquire/store-release operations. It is just that we require something stronger than minimal load-acquire/store-release to make a Linux-kernel lock.

I suspect we're talking past one another here; but our Document describes ACQUIRE/RELEASE semantics such that

RELEASE
ACQUIRE

matches a full barrier, regardless on whether it is the same lock or not.

If you now want to weaken this definition, then that needs consideration because we actually rely on things like

spin_unlock(l1);
spin_lock(l2);

being full barriers.

Now granted, for lock operations we have actual atomic ops in between which would cure x86, but it would leave us confused with the barrier semantics.

So please; either:

A) we have the strong ACQUIRE/RELEASE semantics as currently described; and therefore any RELEASE+ACQUIRE pair must form a full barrier; and our propose primitives are non-compliant and needs strengthening.

B) we go fudge about with the definitions.

But given the current description of our ACQUIRE barrier, we simply cannot claim the proposed primitives are good on x86 IMO.

Also, instead of the smp_store_release() I would argue that smp_load_acquire() is the one that needs the full buffer, even on PPC.

Because our ACQUIRE dis-allows loads/stores leaking out upwards, and both TSO and PPC lwsync allow just that, so the smp_load_acquire() is the one that needs the full barrier.

So what am I missing?

If you now want to weaken this definition, then that needs consideration because we actually rely on things like

spin_unlock(l1);
spin_lock(l2);

being full barriers.

Quoted 7 lines · Peter Zijlstra

If you now want to weaken this definition, then that needs consideration because we actually rely on things like

spin_unlock(l1);
spin_lock(l2);

Quoted 1 line

being full barriers.

Btw, maybe we should just stop that assumption. The complexity of this discussion makes me go "maybe we should stop with subtle assumptions that happen to be obviously true on x86 due to historical implementations, but aren't obviously true even *there* any more with the MCS lock".

We already have a concept of

        smp_mb__before_spinlock();
        spin_lock():

for sequences where we *know* we need to make getting a spin-lock be a full memory barrier. It's free on x86 (and remains so even with the MCS lock, regardless of any subtle issues, if only because even the MCS lock starts out with a locked atomic, never mind the contention slow-case). Of course, that macro is only used inside the scheduler, and is actually documented to not really be a full memory barrier, but it handles the case we actually care about.

IOW, where do we really care about the "unlock+lock" is a memory barrier? And could we make those places explicit, and then do something similar to the above to them?

There are several places in RCU that assume unlock+lock is a full memory barrier, but I would be more than happy to fix them up given an smp_mb__after_spinlock() and an smp_mb__before_spinunlock(), or something similar.

Quoted 5 lines · Paul E. McKenney

There are several places in RCU that assume unlock+lock is a full memory barrier, but I would be more than happy to fix them up given an smp_mb__after_spinlock() and an smp_mb__before_spinunlock(), or something similar.

A "before_spinunlock" would actually be expensive on x86.

So I'd *much* rather see the "after_spinlock()" version, if that is sufficient for all users. And it should be, since that's the traditional x86 behavior that we had before the MCS lock discussion.

Because it's worth noting that a spin_lock() is still a full memory barrier on x86, even with the MCS code, *assuming it is done in the context of the thread needing the memory barrier". And I suspect that is much more generally true than just x86. It's the final MCS hand-off of a lock that is pretty weak with just a local read. The full lock sequence is always going to be much stronger, if only because it will contain a write somewhere shared as well.

Good points, and after_spinlock() works for me from an RCU perspective.

Quoted 2 lines · Paul E. McKenney

Good points, and after_spinlock() works for me from an RCU perspective.

Note that there's still a semantic question about exactly what that "after_spinlock()" is: would it be a memory barrier *only* for the CPU that actually does the spinlock? Or is it that "third CPU" order?

IOW, it would stil not necessarily make your "unlock+lock" (on different CPU's) be an actual barrier as far as a third CPU was concerned, because you could still have the "unlock happened after contention was going on, so the final unlock only released the MCS waiter, and there was no barrier".

See what I'm saying? We could guarantee that if somebody does

    write A;
    spin_lock()
    mb__after_spinlock();
    read B

then the "write A" -> "read B" would be ordered. That's one thing.

But your

- CPU 1:

write A
spin_unlock()

- CPU 2

    spin_lock()
    mb__after_spinlock();
    read B

ordering as far as a *third* CPU is concerned is a whole different thing again, and wouldn't be at all the same thing.

Is it really that cross-CPU ordering you care about?

Quoted 2 lines · Paul E. McKenney

Good points, and after_spinlock() works for me from an RCU perspective.

Note that there's still a semantic question about exactly what that "after_spinlock()" is: would it be a memory barrier *only* for the CPU that actually does the spinlock? Or is it that "third CPU" order?

IOW, it would stil not necessarily make your "unlock+lock" (on different CPU's) be an actual barrier as far as a third CPU was concerned, because you could still have the "unlock happened after contention was going on, so the final unlock only released the MCS waiter, and there was no barrier".

See what I'm saying? We could guarantee that if somebody does

    write A;
    spin_lock()
    mb__after_spinlock();
    read B

then the "write A" -> "read B" would be ordered. That's one thing.

But your

- CPU 1:

write A
spin_unlock()

- CPU 2

    spin_lock()
    mb__after_spinlock();
    read B

ordering as far as a *third* CPU is concerned is a whole different thing again, and wouldn't be at all the same thing.

Is it really that cross-CPU ordering you care about?

Cross-CPU ordering.

Quoted 2 lines · Paul E. McKenney

Cross-CPU ordering.

Ok, in that case I *suspect* we want an actual "spin_lock_mb()" primitive, because if we go with the MCS lock approach, it's quite possible that we find cases where the fast-case is already a barrier (like it is on x86 by virtue of the locked instruction) but the MCS case then is not. And then a separate barrier wouldn't be able to make that kind of judgement.

Or maybe we don't care enough. It *sounds* like on x86, we do probably already get the cross-cpu case for free, and on other architectures we may always need the memory barrier, so maybe the whole "mb_after_spin_lock()" thing is fine.

Ugh.

Quoted 9 lines · Linus Torvalds

Quoted 5 lines · Paul E. McKenney

There are several places in RCU that assume unlock+lock is a full memory barrier, but I would be more than happy to fix them up given an smp_mb__after_spinlock() and an smp_mb__before_spinunlock(), or something similar.

A "before_spinunlock" would actually be expensive on x86.

Good point, on x86 the typical non-queued spin-lock acquisition path has an atomic operation with full memory barrier in any case. I believe that this is the case for the other TSO architectures. For the non-TSO architectures:

o ARM has an smp_mb() during lock acquisition, so after_spinlock()
can be a no-op for them.

Quoted 16 lines · Paul E. McKenney

Quoted 9 lines · Linus Torvalds

Quoted 5 lines · Paul E. McKenney

There are several places in RCU that assume unlock+lock is a full memory barrier, but I would be more than happy to fix them up given an smp_mb__after_spinlock() and an smp_mb__before_spinunlock(), or something similar.

A "before_spinunlock" would actually be expensive on x86.

Good point, on x86 the typical non-queued spin-lock acquisition path has an atomic operation with full memory barrier in any case. I believe that this is the case for the other TSO architectures. For the non-TSO architectures:

Quoted 2 lines

o ARM has an smp_mb() during lock acquisition, so after_spinlock()
can be a no-op for them.

Ok, but what about arm64? We use acquire for lock() and release for unlock(), so in Linus' example:

    write A;
    spin_lock()
    mb__after_spinlock();
    read B

Then A could very well be reordered after B if mb__after_spinlock() is a nop. Making that a full barrier kind of defeats the point of using acquire in the first place...

It's one thing ordering unlock -> lock, but another getting those two to behave as full barriers for any arbitrary memory accesses.

Quoted 8 lines · Will Deacon

Quoted 4 lines · Paul E. McKenney

Quoted 1 line · Linus Torvalds

On Tue, Nov 26, 2013 at 11:20 AM, Paul E. McKenney wrote:

o ARM has an smp_mb() during lock acquisition, so after_spinlock()
can be a no-op for them.

Ok, but what about arm64? We use acquire for lock() and release for unlock(), so in Linus' example:

Right, I did forget the arm vs. arm64 split!

Quoted 5 lines

    write A;
    spin_lock()
    mb__after_spinlock();
    read B

Quoted 3 lines

Then A could very well be reordered after B if mb__after_spinlock() is a nop. Making that a full barrier kind of defeats the point of using acquire in the first place...

The trick is that you don't have mb__after_spinlock() unless you need the ordering, which we expect in a small minority of the lock acquisitions. So you would normally get the benefit of acquire/release efficiency.

Quoted 2 lines

It's one thing ordering unlock -> lock, but another getting those two to behave as full barriers for any arbitrary memory accesses.

And in fact the unlock+lock barrier is all that RCU needs. I guess the question is whether it is worth having two flavors of __after_spinlock(), one that is a full barrier with just the lock, and another that is only guaranteed to be a full barrier with unlock+lock.

Quoted 21 lines · Paul E. McKenney

Quoted 8 lines · Will Deacon

Quoted 4 lines · Paul E. McKenney

Quoted 1 line · Linus Torvalds

On Tue, Nov 26, 2013 at 11:20 AM, Paul E. McKenney wrote:

o ARM has an smp_mb() during lock acquisition, so after_spinlock()
can be a no-op for them.

Ok, but what about arm64? We use acquire for lock() and release for unlock(), so in Linus' example:

Right, I did forget the arm vs. arm64 split!

Quoted 8 lines

    write A;
    spin_lock()
    mb__after_spinlock();
    read B

Then A could very well be reordered after B if mb__after_spinlock() is a nop. Making that a full barrier kind of defeats the point of using acquire in the first place...

Quoted 3 lines

The trick is that you don't have mb__after_spinlock() unless you need the ordering, which we expect in a small minority of the lock acquisitions. So you would normally get the benefit of acquire/release efficiency.

Ok, understood. I take it this means that you don't care about ordering the write to A with the actual locking operation? (that would require the mb to be *inside* the spin_lock() implementation).

Quoted 7 lines

Quoted 2 lines

It's one thing ordering unlock -> lock, but another getting those two to behave as full barriers for any arbitrary memory accesses.

And in fact the unlock+lock barrier is all that RCU needs. I guess the question is whether it is worth having two flavors of __after_spinlock(), one that is a full barrier with just the lock, and another that is only guaranteed to be a full barrier with unlock+lock.

I think it's worth distinguishing those cases because, in my mind, one is potentially a lot heavier than the other. The risk is that we end up producing a set of strangely named barrier abstractions that nobody can figure out how to use properly:

	/*
	 * Prevent re-ordering of arbitrary accesses across spin_lock and
	 * spin_unlock.
	 */
	mb__after_spin_lock()
	mb__after_spin_unlock()

	/*
	 * Order spin_lock() vs spin_unlock()
	 */
	mb__between_spin_unlock_lock() /* Horrible name! */

We could potentially replace the first set of barriers with spin_lock_mb() and spin_unlock_mb() variants (which would be more efficient than half barrier + full barrier), then we only end up with strangely named barrier which applies to the non _mb() spinlock routines.

Quoted 25 lines · Will Deacon

Quoted 4 lines · Paul E. McKenney

And in fact the unlock+lock barrier is all that RCU needs. I guess the question is whether it is worth having two flavors of __after_spinlock(), one that is a full barrier with just the lock, and another that is only guaranteed to be a full barrier with unlock+lock.

I think it's worth distinguishing those cases because, in my mind, one is potentially a lot heavier than the other. The risk is that we end up producing a set of strangely named barrier abstractions that nobody can figure out how to use properly:

	/*
	 * Prevent re-ordering of arbitrary accesses across spin_lock and
	 * spin_unlock.
	 */
	mb__after_spin_lock()
	mb__after_spin_unlock()

	/*
	 * Order spin_lock() vs spin_unlock()
	 */
	mb__between_spin_unlock_lock() /* Horrible name! */

Quoted 4 lines

We could potentially replace the first set of barriers with spin_lock_mb() and spin_unlock_mb() variants (which would be more efficient than half barrier + full barrier), then we only end up with strangely named barrier which applies to the non _mb() spinlock routines.

How about the current mb__before_spinlock() making the acquisition be a full barrier, and an mb_after_spinlock() making a prior release plus this acquisition be a full barrier?

Yes, we might need better names, but I believe that this approach does what you need.

Thoughts?

Quoted 31 lines · Paul E. McKenney

Quoted 29 lines · Will Deacon

Quoted 4 lines · Paul E. McKenney

And in fact the unlock+lock barrier is all that RCU needs. I guess the question is whether it is worth having two flavors of __after_spinlock(), one that is a full barrier with just the lock, and another that is only guaranteed to be a full barrier with unlock+lock.

I think it's worth distinguishing those cases because, in my mind, one is potentially a lot heavier than the other. The risk is that we end up producing a set of strangely named barrier abstractions that nobody can figure out how to use properly:

	/*
	 * Prevent re-ordering of arbitrary accesses across spin_lock and
	 * spin_unlock.
	 */
	mb__after_spin_lock()
	mb__after_spin_unlock()

	/*
	 * Order spin_lock() vs spin_unlock()
	 */
	mb__between_spin_unlock_lock() /* Horrible name! */

We could potentially replace the first set of barriers with spin_lock_mb() and spin_unlock_mb() variants (which would be more efficient than half barrier + full barrier), then we only end up with strangely named barrier which applies to the non _mb() spinlock routines.

Quoted 3 lines

How about the current mb__before_spinlock() making the acquisition be a full barrier, and an mb_after_spinlock() making a prior release plus this acquisition be a full barrier?

Hmm, without horrible hacks to keep track of whether we've done an mb__before_spinlock() without a matching spinlock(), that's going to end up with full-barrier + pointless half-barrier (similarly on the release path).

Quoted 4 lines

Yes, we might need better names, but I believe that this approach does what you need.

Thoughts?

I still think we need to draw the distinction between ordering all accesses against a lock and ordering an unlock against a lock. The latter is free for arm64 (STLR => LDAR is ordered) but the former requires a DMB.

Not sure I completely got your drift...

Quoted 3 lines · Will Deacon

Hmm, without horrible hacks to keep track of whether we've done an mb__before_spinlock() without a matching spinlock(), that's going to end up with full-barrier + pointless half-barrier (similarly on the release path).

We should be able to detect mb__before_spinlock() without a matching spinlock via static analysis, right?

Or am I missing your point?

Quoted 10 lines

Quoted 4 lines

Yes, we might need better names, but I believe that this approach does what you need.

Thoughts?

I still think we need to draw the distinction between ordering all accesses against a lock and ordering an unlock against a lock. The latter is free for arm64 (STLR => LDAR is ordered) but the former requires a DMB.

Not sure I completely got your drift...

Here is what I am suggesting:

o mb__before_spinlock():

o Must appear immediately before a lock acquisition.
o Upgrades a lock acquisition to a full barrier.
o Emits DMB on ARM64.

o mb_after_spinlock():

o Must appear immediatly after a lock acquisition.
o Upgrades an unlock+lock pair to a full barrier.
o Emits a no-op on ARM64, as in "do { } while (0)".
o Might need a separate flavor for queued locks on
some platforms, but no sign of that yet.

Quoted 9 lines · Paul E. McKenney

Quoted 3 lines · Will Deacon

Hmm, without horrible hacks to keep track of whether we've done an mb__before_spinlock() without a matching spinlock(), that's going to end up with full-barrier + pointless half-barrier (similarly on the release path).

We should be able to detect mb__before_spinlock() without a matching spinlock via static analysis, right?

Or am I missing your point?

See below...

Quoted 11 lines

Quoted 10 lines

Quoted 4 lines

Yes, we might need better names, but I believe that this approach does what you need.

Thoughts?

I still think we need to draw the distinction between ordering all accesses against a lock and ordering an unlock against a lock. The latter is free for arm64 (STLR => LDAR is ordered) but the former requires a DMB.

Not sure I completely got your drift...

Quoted 7 lines

Here is what I am suggesting:

o mb__before_spinlock():

o Must appear immediately before a lock acquisition.
o Upgrades a lock acquisition to a full barrier.
o Emits DMB on ARM64.

Ok, so that then means that:

	mb__before_spinlock();
	spin_lock();

on ARM64 expands to:

	dmb	ish
	ldaxr	...

so there's a redundant half-barrier there. If we want to get rid of that, we need mb__before_spinlock() to set a flag, then we could conditionalise ldaxr/ldxr but it's really horrible and you have to deal with interrupts etc. so in reality we just end up having extra barriers.

Or we have separate a spin_lock_mb() function.

Quoted 7 lines

o mb_after_spinlock():

o Must appear immediatly after a lock acquisition.
o Upgrades an unlock+lock pair to a full barrier.
o Emits a no-op on ARM64, as in "do { } while (0)".
o Might need a separate flavor for queued locks on
some platforms, but no sign of that yet.

Ok, so mb__after_spinlock() doesn't imply a full barrier but mb__before_spinlock() does? I think people will get that wrong :)

Quoted 10 lines · Will Deacon

Ok, so that then means that:

	mb__before_spinlock();
	spin_lock();

on ARM64 expands to:

	dmb	ish
	ldaxr	...

Quoted 4 lines

so there's a redundant half-barrier there. If we want to get rid of that, we need mb__before_spinlock() to set a flag, then we could conditionalise ldaxr/ldxr but it's really horrible and you have to deal with interrupts etc. so in reality we just end up having extra barriers.

Given that there was just a dmb, how much does the ish &c really hurt? Would the performance difference be measurable at the system level?

Quoted 1 line

Or we have separate a spin_lock_mb() function.

And mutex_lock_mb(). And spin_lock_irqsave_mb(). And spin_lock_irq_mb(). And...

Admittedly this is not yet a problem given the current very low usage of smp_mb__before_spinlock(), but the potential for API explosion is non-trivial.

That said, if the effect on ARM64 is measurable at the system level, I won't stand in the way of the additional APIs.

Quoted 8 lines

Quoted 7 lines

o mb_after_spinlock():

o Must appear immediatly after a lock acquisition.
o Upgrades an unlock+lock pair to a full barrier.
o Emits a no-op on ARM64, as in "do { } while (0)".
o Might need a separate flavor for queued locks on
some platforms, but no sign of that yet.

Quoted 2 lines

Ok, so mb__after_spinlock() doesn't imply a full barrier but mb__before_spinlock() does? I think people will get that wrong :)

As I said earlier in the thread, I am open to better names.

How about smp_mb__after_spin_unlock_lock_pair()? That said, I am sure that I could come up with something longer given enough time. ;-)

To get some sort of
idea, I tried adding a dmb to the start of spin_unlock on ARMv7 and I saw

3% performance hit in hackbench on my dual-cluster board.

Quoted 4 lines · On Nov 29, 2013 8:18 AM, "Will Deacon" <[email protected]<mailto:will.deacon@…

To get some sort of idea, I tried adding a dmb to the start of spin_unlock on ARMv7 and I saw a 3% performance hit in hackbench on my dual-cluster board.

Don't do a dmb. Just do a dummy release. You just said that on arm64 a unlock+lock is a memory barrier, so just make the mb__before_spinlock() be a dummy store with release to the stack..

Quoted 3 lines · Will Deacon

To get some sort of
idea, I tried adding a dmb to the start of spin_unlock on ARMv7 and I saw

a

Quoted 1 line

3% performance hit in hackbench on my dual-cluster board.

Don't do a dmb. Just do a dummy release. You just said that on arm64 a unlock+lock is a memory barrier, so just make the mb__before_spinlock() be a dummy store with release to the stack..

That should be noticeably cheaper than a full dmb.