Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1471345 > unrolled thread

[PATCH 0/4] Clarify/standardize memory barriers for lock/unlock

Back to article view | Back to linux.kernel

Contents

  [PATCH 0/4] Clarify/standardize memory barriers for lock/unlock Manfred Spraul <manfred@colorfullife.com> - 2016-08-28 14:00 +0200
    [PATCH 1/4] spinlock: Document memory barrier rules Manfred Spraul <manfred@colorfullife.com> - 2016-08-28 14:00 +0200
      [PATCH 2/4] barrier.h: Move smp_mb__after_unlock_lock to barrier.h Manfred Spraul <manfred@colorfullife.com> - 2016-08-28 14:00 +0200
        Re: [PATCH 2/4] barrier.h: Move smp_mb__after_unlock_lock to  barrier.h "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-08-28 15:50 +0200
          [PATCH 2/4] barrier.h: Move smp_mb__after_unlock_lock to barrier.h Manfred Spraul <manfred@colorfullife.com> - 2016-08-28 18:40 +0200
          Re: [PATCH 2/4] barrier.h: Move smp_mb__after_unlock_lock to  barrier.h Manfred Spraul <manfred@colorfullife.com> - 2016-08-28 20:10 +0200
      Re: [PATCH 1/4] spinlock: Document memory barrier rules Peter Zijlstra <peterz@infradead.org> - 2016-08-29 12:50 +0200
        Re: [PATCH 1/4] spinlock: Document memory barrier rules Manfred Spraul <manfred@colorfullife.com> - 2016-08-29 15:00 +0200
          Re: [PATCH 1/4] spinlock: Document memory barrier rules Peter Zijlstra <peterz@infradead.org> - 2016-08-29 15:50 +0200
            Re: [PATCH 1/4] spinlock: Document memory barrier rules Manfred Spraul <manfred@colorfullife.com> - 2016-08-31 07:00 +0200
              Re: [PATCH 1/4] spinlock: Document memory barrier rules Peter Zijlstra <peterz@infradead.org> - 2016-08-31 17:50 +0200
                Re: [PATCH 1/4] spinlock: Document memory barrier rules Will Deacon <will.deacon@arm.com> - 2016-08-31 18:50 +0200
                  Re: [PATCH 1/4] spinlock: Document memory barrier rules Manfred Spraul <manfred@colorfullife.com> - 2016-08-31 20:40 +0200
                    Re: [PATCH 1/4] spinlock: Document memory barrier rules Peter Zijlstra <peterz@infradead.org> - 2016-09-01 10:50 +0200
                      Re: [PATCH 1/4] spinlock: Document memory barrier rules Manfred Spraul <manfred@colorfullife.com> - 2016-09-01 13:10 +0200
                        Re: [PATCH 1/4] spinlock: Document memory barrier rules Will Deacon <will.deacon@arm.com> - 2016-09-01 13:20 +0200
                        Re: [PATCH 1/4] spinlock: Document memory barrier rules Peter Zijlstra <peterz@infradead.org> - 2016-09-01 14:00 +0200
                          Re: [PATCH 1/4] spinlock: Document memory barrier rules Boqun Feng <boqun.feng@gmail.com> - 2016-09-01 16:10 +0200
    Re: [PATCH 0/4] Clarify/standardize memory barriers for lock/unlock Peter Zijlstra <peterz@infradead.org> - 2016-08-29 13:00 +0200

#1471345 — [PATCH 0/4] Clarify/standardize memory barriers for lock/unlock

Hi,

as discussed before:
If a high-scalability locking scheme is built with multiple
spinlocks, then often additional memory barriers are required.

The documentation was not as clear as possible, and memory
barriers were missing / superfluous in the implementation.

Patch 1: Documentation, define one standard barrier, update ipc/sem.c
Patch 2: Update rcutree
Patch 3: Update nf_conntrack
Patch 4: Update for qspinlock: smp_mb__after_spin_lock is free.

Patch 3 is larger than required, it rewrites the conntrack logic
with the code from ipc/sem.c. I think the new code is simpler
and more realtime-friendly.

Please review!

@Andrew: The patches are relative to mmots.
Could you include them in your tree, with the target of including in
linux-next?

--
	Manfred

[toc] | [next] | [standalone]

#1471346 — [PATCH 1/4] spinlock: Document memory barrier rules

Right now, the spinlock machinery tries to guarantee barriers even for
unorthodox locking cases, which ends up as a constant stream of updates
as the architectures try to support new unorthodox ideas.

The patch proposes to reverse that:
spin_lock is ACQUIRE, spin_unlock is RELEASE.
spin_unlock_wait is also ACQUIRE.
Code that needs further guarantees must use appropriate explicit barriers.

Architectures that can implement some barriers for free can define the
barriers as NOPs.

As the initial step, the patch converts ipc/sem.c to the new defines:
- no more smp_rmb() after spin_unlock_wait(), that is part of
  spin_unlock_wait()
- smp_mb__after_spin_lock() instead of a direct smp_mb().

Signed-off-by: Manfred Spraul <manfred@colorfullife.com>
---
 Documentation/locking/spinlocks.txt |  5 +++++
 include/linux/spinlock.h            | 12 ++++++++++++
 ipc/sem.c                           | 16 +---------------
 3 files changed, 18 insertions(+), 15 deletions(-)

diff --git a/Documentation/locking/spinlocks.txt b/Documentation/locking/spinlocks.txt
index ff35e40..fc37beb 100644
--- a/Documentation/locking/spinlocks.txt
+++ b/Documentation/locking/spinlocks.txt
@@ -40,6 +40,11 @@ example, internal driver data structures that nobody else ever touches).
    touches a shared variable has to agree about the spinlock they want
    to use.
 
+   NOTE! Code that needs stricter memory barriers than ACQUIRE during
+   LOCK and RELEASE during UNLOCK must use appropriate memory barriers
+   such as smp_mb__after_spin_lock().
+   spin_unlock_wait() has ACQUIRE semantics.
+
 ----
 
 Lesson 2: reader-writer spinlocks.
diff --git a/include/linux/spinlock.h b/include/linux/spinlock.h
index 47dd0ce..d79000e 100644
--- a/include/linux/spinlock.h
+++ b/include/linux/spinlock.h
@@ -130,6 +130,18 @@ do {								\
 #define smp_mb__before_spinlock()	smp_wmb()
 #endif
 
+#ifndef smp_mb__after_spin_lock
+/**
+ * smp_mb__after_spin_lock() - Provide smp_mb() after spin_lock
+ *
+ * spin_lock() provides ACQUIRE semantics regarding reading the lock.
+ * There are no guarantees that the lock write is visible before any read
+ * or write operation within the protected area is performed.
+ * If the lock write must happen first, this function is required.
+ */
+#define smp_mb__after_spin_lock()	smp_mb()
+#endif
+
 /**
  * raw_spin_unlock_wait - wait until the spinlock gets unlocked
  * @lock: the spinlock in question.
diff --git a/ipc/sem.c b/ipc/sem.c
index 5e318c5..ac15ab2 100644
--- a/ipc/sem.c
+++ b/ipc/sem.c
@@ -290,14 +290,6 @@ static void complexmode_enter(struct sem_array *sma)
 		sem = sma->sem_base + i;
 		spin_unlock_wait(&sem->lock);
 	}
-	/*
-	 * spin_unlock_wait() is not a memory barriers, it is only a
-	 * control barrier. The code must pair with spin_unlock(&sem->lock),
-	 * thus just the control barrier is insufficient.
-	 *
-	 * smp_rmb() is sufficient, as writes cannot pass the control barrier.
-	 */
-	smp_rmb();
 }
 
 /*
@@ -363,13 +355,7 @@ static inline int sem_lock(struct sem_array *sma, struct sembuf *sops,
 		 */
 		spin_lock(&sem->lock);
 
-		/*
-		 * See 51d7d5205d33
-		 * ("powerpc: Add smp_mb() to arch_spin_is_locked()"):
-		 * A full barrier is required: the write of sem->lock
-		 * must be visible before the read is executed
-		 */
-		smp_mb();
+		smp_mb__after_spin_lock();
 
 		if (!smp_load_acquire(&sma->complex_mode)) {
 			/* fast path successful! */
-- 
2.5.5

[toc] | [prev] | [next] | [standalone]

#1471347 — [PATCH 2/4] barrier.h: Move smp_mb__after_unlock_lock to barrier.h

spin_unlock() + spin_lock() together do not form a full memory barrier:

  a=1;
  spin_unlock(&b);
  spin_lock(&c);
+ smp_mb__after_unlock_lock();
  d=1;

Without the smp_mb__after_unlock_lock(), other CPUs can observe the
write to d without seeing the write to a.

Signed-off-by: Manfred Spraul <manfred@colorfullife.com>
---
 include/asm-generic/barrier.h | 16 ++++++++++++++++
 kernel/rcu/tree.h             | 12 ------------
 2 files changed, 16 insertions(+), 12 deletions(-)

diff --git a/include/asm-generic/barrier.h b/include/asm-generic/barrier.h
index fe297b5..9b4d28f 100644
--- a/include/asm-generic/barrier.h
+++ b/include/asm-generic/barrier.h
@@ -244,6 +244,22 @@ do {									\
 	smp_acquire__after_ctrl_dep();				\
 	VAL;							\
 })
+
+#ifndef smp_mb__after_unlock_lock
+/*
+ * Place this after a lock-acquisition primitive to guarantee that
+ * an UNLOCK+LOCK pair act as a full barrier.  This guarantee applies
+ * if the UNLOCK and LOCK are executed by the same CPU or if the
+ * UNLOCK and LOCK operate on the same lock variable.
+ */
+#ifdef CONFIG_PPC
+#define smp_mb__after_unlock_lock()	smp_mb()  /* Full ordering for lock. */
+#else /* #ifdef CONFIG_PPC */
+#define smp_mb__after_unlock_lock()	do { } while (0)
+#endif /* #else #ifdef CONFIG_PPC */
+
+#endif
+
 #endif
 
 #endif /* !__ASSEMBLY__ */
diff --git a/kernel/rcu/tree.h b/kernel/rcu/tree.h
index e99a523..a0cd9ab 100644
--- a/kernel/rcu/tree.h
+++ b/kernel/rcu/tree.h
@@ -687,18 +687,6 @@ static inline void rcu_nocb_q_lengths(struct rcu_data *rdp, long *ql, long *qll)
 #endif /* #ifdef CONFIG_RCU_TRACE */
 
 /*
- * Place this after a lock-acquisition primitive to guarantee that
- * an UNLOCK+LOCK pair act as a full barrier.  This guarantee applies
- * if the UNLOCK and LOCK are executed by the same CPU or if the
- * UNLOCK and LOCK operate on the same lock variable.
- */
-#ifdef CONFIG_PPC
-#define smp_mb__after_unlock_lock()	smp_mb()  /* Full ordering for lock. */
-#else /* #ifdef CONFIG_PPC */
-#define smp_mb__after_unlock_lock()	do { } while (0)
-#endif /* #else #ifdef CONFIG_PPC */
-
-/*
  * Wrappers for the rcu_node::lock acquire and release.
  *
  * Because the rcu_nodes form a tree, the tree traversal locking will observe
-- 
2.5.5

[toc] | [prev] | [next] | [standalone]

#1471367 — Re: [PATCH 2/4] barrier.h: Move smp_mb__after_unlock_lock to barrier.h

On Sun, Aug 28, 2016 at 01:56:14PM +0200, Manfred Spraul wrote:
> spin_unlock() + spin_lock() together do not form a full memory barrier:
> 
>   a=1;
>   spin_unlock(&b);
>   spin_lock(&c);
> + smp_mb__after_unlock_lock();
>   d=1;

Better would be s/d=1/r1=d/ above.

Then another process doing this:

	d=1
	smp_mb()
	r2=a

might have the after-the-dust-settles outcome of r1==0&&r2==0.

The advantage of this scenario is that it can happen on real hardware.

> 
> Without the smp_mb__after_unlock_lock(), other CPUs can observe the
> write to d without seeing the write to a.
> 
> Signed-off-by: Manfred Spraul <manfred@colorfullife.com>

With the upgraded commit log, I am OK with the patch below.
However, others will probably want to see at least one use of
smp_mb__after_unlock_lock() outside of RCU.

							Thanx, Paul

> ---
>  include/asm-generic/barrier.h | 16 ++++++++++++++++
>  kernel/rcu/tree.h             | 12 ------------
>  2 files changed, 16 insertions(+), 12 deletions(-)
> 
> diff --git a/include/asm-generic/barrier.h b/include/asm-generic/barrier.h
> index fe297b5..9b4d28f 100644
> --- a/include/asm-generic/barrier.h
> +++ b/include/asm-generic/barrier.h
> @@ -244,6 +244,22 @@ do {									\
>  	smp_acquire__after_ctrl_dep();				\
>  	VAL;							\
>  })
> +
> +#ifndef smp_mb__after_unlock_lock
> +/*
> + * Place this after a lock-acquisition primitive to guarantee that
> + * an UNLOCK+LOCK pair act as a full barrier.  This guarantee applies
> + * if the UNLOCK and LOCK are executed by the same CPU or if the
> + * UNLOCK and LOCK operate on the same lock variable.
> + */
> +#ifdef CONFIG_PPC
> +#define smp_mb__after_unlock_lock()	smp_mb()  /* Full ordering for lock. */
> +#else /* #ifdef CONFIG_PPC */
> +#define smp_mb__after_unlock_lock()	do { } while (0)
> +#endif /* #else #ifdef CONFIG_PPC */
> +
> +#endif
> +
>  #endif
> 
>  #endif /* !__ASSEMBLY__ */
> diff --git a/kernel/rcu/tree.h b/kernel/rcu/tree.h
> index e99a523..a0cd9ab 100644
> --- a/kernel/rcu/tree.h
> +++ b/kernel/rcu/tree.h
> @@ -687,18 +687,6 @@ static inline void rcu_nocb_q_lengths(struct rcu_data *rdp, long *ql, long *qll)
>  #endif /* #ifdef CONFIG_RCU_TRACE */
> 
>  /*
> - * Place this after a lock-acquisition primitive to guarantee that
> - * an UNLOCK+LOCK pair act as a full barrier.  This guarantee applies
> - * if the UNLOCK and LOCK are executed by the same CPU or if the
> - * UNLOCK and LOCK operate on the same lock variable.
> - */
> -#ifdef CONFIG_PPC
> -#define smp_mb__after_unlock_lock()	smp_mb()  /* Full ordering for lock. */
> -#else /* #ifdef CONFIG_PPC */
> -#define smp_mb__after_unlock_lock()	do { } while (0)
> -#endif /* #else #ifdef CONFIG_PPC */
> -
> -/*
>   * Wrappers for the rcu_node::lock acquire and release.
>   *
>   * Because the rcu_nodes form a tree, the tree traversal locking will observe
> -- 
> 2.5.5
> 

[toc] | [prev] | [next] | [standalone]

#1471389 — [PATCH 2/4] barrier.h: Move smp_mb__after_unlock_lock to barrier.h

spin_unlock() + spin_lock() together do not form a full memory barrier:
(everything initialized to 0)

CPU1:
  a=1;
  spin_unlock(&b);
  spin_lock(&c);
+ smp_mb__after_unlock_lock();
  r1=d;

CPU2:
  d=1;
  smp_mb();
  r2=a;

Without the smp_mb__after_unlock_lock(), r1==0 && r2==0 would
be possible.

Signed-off-by: Manfred Spraul <manfred@colorfullife.com>
---
 include/asm-generic/barrier.h | 16 ++++++++++++++++
 kernel/rcu/tree.h             | 12 ------------
 2 files changed, 16 insertions(+), 12 deletions(-)

diff --git a/include/asm-generic/barrier.h b/include/asm-generic/barrier.h
index fe297b5..9b4d28f 100644
--- a/include/asm-generic/barrier.h
+++ b/include/asm-generic/barrier.h
@@ -244,6 +244,22 @@ do {									\
 	smp_acquire__after_ctrl_dep();				\
 	VAL;							\
 })
+
+#ifndef smp_mb__after_unlock_lock
+/*
+ * Place this after a lock-acquisition primitive to guarantee that
+ * an UNLOCK+LOCK pair act as a full barrier.  This guarantee applies
+ * if the UNLOCK and LOCK are executed by the same CPU or if the
+ * UNLOCK and LOCK operate on the same lock variable.
+ */
+#ifdef CONFIG_PPC
+#define smp_mb__after_unlock_lock()	smp_mb()  /* Full ordering for lock. */
+#else /* #ifdef CONFIG_PPC */
+#define smp_mb__after_unlock_lock()	do { } while (0)
+#endif /* #else #ifdef CONFIG_PPC */
+
+#endif
+
 #endif
 
 #endif /* !__ASSEMBLY__ */
diff --git a/kernel/rcu/tree.h b/kernel/rcu/tree.h
index e99a523..a0cd9ab 100644
--- a/kernel/rcu/tree.h
+++ b/kernel/rcu/tree.h
@@ -687,18 +687,6 @@ static inline void rcu_nocb_q_lengths(struct rcu_data *rdp, long *ql, long *qll)
 #endif /* #ifdef CONFIG_RCU_TRACE */
 
 /*
- * Place this after a lock-acquisition primitive to guarantee that
- * an UNLOCK+LOCK pair act as a full barrier.  This guarantee applies
- * if the UNLOCK and LOCK are executed by the same CPU or if the
- * UNLOCK and LOCK operate on the same lock variable.
- */
-#ifdef CONFIG_PPC
-#define smp_mb__after_unlock_lock()	smp_mb()  /* Full ordering for lock. */
-#else /* #ifdef CONFIG_PPC */
-#define smp_mb__after_unlock_lock()	do { } while (0)
-#endif /* #else #ifdef CONFIG_PPC */
-
-/*
  * Wrappers for the rcu_node::lock acquire and release.
  *
  * Because the rcu_nodes form a tree, the tree traversal locking will observe
-- 
2.5.5

[toc] | [prev] | [next] | [standalone]

#1471429 — Re: [PATCH 2/4] barrier.h: Move smp_mb__after_unlock_lock to barrier.h

On 08/28/2016 03:43 PM, Paul E. McKenney wrote:
>
>> Without the smp_mb__after_unlock_lock(), other CPUs can observe the
>> write to d without seeing the write to a.
>>
>> Signed-off-by: Manfred Spraul <manfred@colorfullife.com>
> With the upgraded commit log, I am OK with the patch below.
Done.
> However, others will probably want to see at least one use of
> smp_mb__after_unlock_lock() outside of RCU.
I would look at it from the other side:
There are at least half a dozen hardware/spinlock implementations that 
must support rcu.
And for half a dozen implementations, a global header file makes sense, 
regardless of the number of users.

With this in the global header file
 > #ifndef complex_memory_barrier()
 > #define complex_memory_barrier()    always_safe_fallback()
 > #endif

it is easier for the architectures to support rcu, ipc/sem and nf_conntrack.
Especially if everything is (as it is now) in <linux/spinlock.h>

--
     Manfred

[toc] | [prev] | [next] | [standalone]

#1471714 — Re: [PATCH 1/4] spinlock: Document memory barrier rules

On Sun, Aug 28, 2016 at 01:56:13PM +0200, Manfred Spraul wrote:
> Right now, the spinlock machinery tries to guarantee barriers even for
> unorthodox locking cases, which ends up as a constant stream of updates
> as the architectures try to support new unorthodox ideas.
> 
> The patch proposes to reverse that:
> spin_lock is ACQUIRE, spin_unlock is RELEASE.
> spin_unlock_wait is also ACQUIRE.
> Code that needs further guarantees must use appropriate explicit barriers.
> 
> Architectures that can implement some barriers for free can define the
> barriers as NOPs.
> 
> As the initial step, the patch converts ipc/sem.c to the new defines:
> - no more smp_rmb() after spin_unlock_wait(), that is part of
>   spin_unlock_wait()
> - smp_mb__after_spin_lock() instead of a direct smp_mb().
> 

Why? This does not explain why..

[toc] | [prev] | [next] | [standalone]

#1471814 — Re: [PATCH 1/4] spinlock: Document memory barrier rules

Hi Peter,

On 08/29/2016 12:48 PM, Peter Zijlstra wrote:
> On Sun, Aug 28, 2016 at 01:56:13PM +0200, Manfred Spraul wrote:
>> Right now, the spinlock machinery tries to guarantee barriers even for
>> unorthodox locking cases, which ends up as a constant stream of updates
>> as the architectures try to support new unorthodox ideas.
>>
>> The patch proposes to reverse that:
>> spin_lock is ACQUIRE, spin_unlock is RELEASE.
>> spin_unlock_wait is also ACQUIRE.
>> Code that needs further guarantees must use appropriate explicit barriers.
>>
>> Architectures that can implement some barriers for free can define the
>> barriers as NOPs.
>>
>> As the initial step, the patch converts ipc/sem.c to the new defines:
>> - no more smp_rmb() after spin_unlock_wait(), that is part of
>>    spin_unlock_wait()
>> - smp_mb__after_spin_lock() instead of a direct smp_mb().
>>
> Why? This does not explain why..

Which explanation is missing?

- removal of the smb_rmb() after spin_unlock_wait?

What about:

> - With commit 2c6100227116
>   ("locking/qspinlock: Fix spin_unlock_wait() some more"),
>   (and the commits for the other archs), spin_unlock_wait() is an
>   ACQUIRE.
>   Therefore the smp_rmb() after spin_unlock_wait() can be removed.
> - smp_mb__after_spin_lock() instead of a direct smp_mb().
>   This allows that architectures override it with a less expensive
>   barrier if this is sufficient for their hardware.
- Why smp_mb is required after spin_lock? See Patch 02, I added the race 
that exists on real hardware.

Exactly the same issue exists for sem.c

- Why introduce a smp_mb__after_spin_lock()?

The other options would be:
- same as RCU, i.e. add CONFIG_PPC into sem.c and nf_contrack_core.c
- overhead for all archs by added an unconditional smp_mb()

--
     Manfred

[toc] | [prev] | [next] | [standalone]

#1471853 — Re: [PATCH 1/4] spinlock: Document memory barrier rules

On Mon, Aug 29, 2016 at 02:54:54PM +0200, Manfred Spraul wrote:
> Hi Peter,
> 
> On 08/29/2016 12:48 PM, Peter Zijlstra wrote:
> >On Sun, Aug 28, 2016 at 01:56:13PM +0200, Manfred Spraul wrote:
> >>Right now, the spinlock machinery tries to guarantee barriers even for
> >>unorthodox locking cases, which ends up as a constant stream of updates
> >>as the architectures try to support new unorthodox ideas.
> >>
> >>The patch proposes to reverse that:
> >>spin_lock is ACQUIRE, spin_unlock is RELEASE.
> >>spin_unlock_wait is also ACQUIRE.
> >>Code that needs further guarantees must use appropriate explicit barriers.
> >>
> >>Architectures that can implement some barriers for free can define the
> >>barriers as NOPs.
> >>
> >>As the initial step, the patch converts ipc/sem.c to the new defines:
> >>- no more smp_rmb() after spin_unlock_wait(), that is part of
> >>   spin_unlock_wait()
> >>- smp_mb__after_spin_lock() instead of a direct smp_mb().
> >>
> >Why? This does not explain why..
> 
> Which explanation is missing?
> 
> - removal of the smb_rmb() after spin_unlock_wait?

So that should have been a separate patch. This thing doing two things
is wrong too. But no, this I get. I did make spin_unlock_wait() an
ACQUIRE after all.

> - Why smp_mb is required after spin_lock? See Patch 02, I added the race
> that exists on real hardware.
> 
> Exactly the same issue exists for sem.c
> 
> - Why introduce a smp_mb__after_spin_lock()?
> 
> The other options would be:
> - same as RCU, i.e. add CONFIG_PPC into sem.c and nf_contrack_core.c
> - overhead for all archs by added an unconditional smp_mb()

See, this too doesn't adequately explain the situation, since all refers
to other sources.

If you add a barrier, the Changelog had better be clear. And I'm still
not entirely sure I get what exactly this barrier should do, nor why it
defaults to a full smp_mb. If what I suspect it should do, only PPC and
ARM64 need the barrier.

And x86 doesn't need it -- _however_ it would need it if you require
full smp_mb semantics, which I suspect you don't.

Which brings us back to a very poor definition of what this barrier
should be doing.

[toc] | [prev] | [next] | [standalone]

#1473033 — Re: [PATCH 1/4] spinlock: Document memory barrier rules

On 08/29/2016 03:44 PM, Peter Zijlstra wrote:
>
> If you add a barrier, the Changelog had better be clear. And I'm still
> not entirely sure I get what exactly this barrier should do, nor why it
> defaults to a full smp_mb. If what I suspect it should do, only PPC and
> ARM64 need the barrier.
The barrier must ensure that taking the spinlock (as observed by another 
cpu with spin_unlock_wait()) and a following read are ordered.

start condition: sma->complex_mode = false;

CPU 1:
     spin_lock(&sem->lock); /* sem_nsems instances */
     smp_mb__after_spin_lock();
     if (!smp_load_acquire(&sma->complex_mode)) {
         /* fast path successful! */
         return sops->sem_num;
     }
      /* slow path, not relevant */

CPU 2: (holding sma->sem_perm.lock)

         smp_store_mb(sma->complex_mode, true);

         for (i = 0; i < sma->sem_nsems; i++) {
                 spin_unlock_wait(&sma->sem_base[i].lock);
         }

It must not happen that both CPUs proceed:
Either CPU1 proceeds, then CPU2 must spin in spin_unlock_wait()
or CPU2 proceeds, then CPU1 must enter the slow path.

What about this?
/*
  * spin_lock() provides ACQUIRE semantics regarding reading the lock.
  * There are no guarantees that the store of the lock is visible before
  * any read or write operation within the protected area is performed.
  * If the store of the lock must happen first, this function is required.
  */
#define spin_lock_store_acquire()

I would update the patch series.

--
     Manfred

[toc] | [prev] | [next] | [standalone]

#1473619 — Re: [PATCH 1/4] spinlock: Document memory barrier rules

On Wed, Aug 31, 2016 at 06:59:07AM +0200, Manfred Spraul wrote:

> The barrier must ensure that taking the spinlock (as observed by another cpu
> with spin_unlock_wait()) and a following read are ordered.
> 
> start condition: sma->complex_mode = false;
> 
> CPU 1:
>     spin_lock(&sem->lock); /* sem_nsems instances */
>     smp_mb__after_spin_lock();
>     if (!smp_load_acquire(&sma->complex_mode)) {
>         /* fast path successful! */
>         return sops->sem_num;
>     }
>      /* slow path, not relevant */
> 
> CPU 2: (holding sma->sem_perm.lock)
> 
>         smp_store_mb(sma->complex_mode, true);
> 
>         for (i = 0; i < sma->sem_nsems; i++) {
>                 spin_unlock_wait(&sma->sem_base[i].lock);
>         }
> 
> It must not happen that both CPUs proceed:
> Either CPU1 proceeds, then CPU2 must spin in spin_unlock_wait()
> or CPU2 proceeds, then CPU1 must enter the slow path.
> 
> What about this?
> /*
>  * spin_lock() provides ACQUIRE semantics regarding reading the lock.
>  * There are no guarantees that the store of the lock is visible before
>  * any read or write operation within the protected area is performed.
>  * If the store of the lock must happen first, this function is required.
>  */
> #define spin_lock_store_acquire()

So I think the fundamental problem is with our atomic_*_acquire()
primitives, where we've specified that the ACQUIRE only pertains to the
LOAD of the RmW.

The spinlock implementations suffer this problem mostly because of
that (not 100% accurate but close enough).

One solution would be to simply use smp_mb__after_atomic(). The
'problem' with that is __atomic_op_acquire() defaults to using that, so
the archs that use __atomic_op_acquire() will get a double smp_mb()
(arm64 and powerpc do not use __atomic_op_acquire()).

I'm not sure we want to introduce a new primitive for this specific to
spinlocks.

Will, any opinions?

[toc] | [prev] | [next] | [standalone]

#1473695 — Re: [PATCH 1/4] spinlock: Document memory barrier rules

On Wed, Aug 31, 2016 at 05:40:49PM +0200, Peter Zijlstra wrote:
> On Wed, Aug 31, 2016 at 06:59:07AM +0200, Manfred Spraul wrote:
> 
> > The barrier must ensure that taking the spinlock (as observed by another cpu
> > with spin_unlock_wait()) and a following read are ordered.
> > 
> > start condition: sma->complex_mode = false;
> > 
> > CPU 1:
> >     spin_lock(&sem->lock); /* sem_nsems instances */
> >     smp_mb__after_spin_lock();
> >     if (!smp_load_acquire(&sma->complex_mode)) {
> >         /* fast path successful! */
> >         return sops->sem_num;
> >     }
> >      /* slow path, not relevant */
> > 
> > CPU 2: (holding sma->sem_perm.lock)
> > 
> >         smp_store_mb(sma->complex_mode, true);
> > 
> >         for (i = 0; i < sma->sem_nsems; i++) {
> >                 spin_unlock_wait(&sma->sem_base[i].lock);
> >         }

I'm struggling with this example. We have these locks:

  &sem->lock
  &sma->sem_base[0...sma->sem_nsems].lock
  &sma->sem_perm.lock

a condition variable:

  sma->complex_mode

and a new barrier:

  smp_mb__after_spin_lock()

For simplicity, we can make sma->sem_nsems == 1, and have &sma->sem_base[0]
be &sem->lock in the example above. &sma->sem_perm.lock seems to be
irrelevant.

The litmus test then looks a bit like:

CPUm:

LOCK(x)
smp_mb();
RyAcq=0


CPUn:

Wy=1
smp_mb();
UNLOCK_WAIT(x)


which I think can be simplified to:


LOCK(x)
Ry=0

Wy=1
smp_mb(); // Note that this is implied by spin_unlock_wait on PPC and arm64
LOCK(x)   // spin_unlock_wait behaves like lock; unlock
UNLOCK(x)


[I've removed a bunch of barriers here, that I don't think are necessary
 for the guarantees you're after]

and the question is "Can both CPUs proceed?".

Looking at the above, then I don't think that they can. Whilst CPUm can
indeed speculate the Ry=0 before successfully taking the lock, if CPUn
observes CPUm's read, then it must also observe the lock being held wrt
the spin_lock API. That is because a successful LOCK operation by CPUn
would force CPUm to replay its LL/SC loop and therefore discard its
speculation of y.

What am I missing? The code snippet seems to have too many barriers to me!

Will

[toc] | [prev] | [next] | [standalone]

#1473787 — Re: [PATCH 1/4] spinlock: Document memory barrier rules

On 08/31/2016 06:40 PM, Will Deacon wrote:
>
> I'm struggling with this example. We have these locks:
>
>    &sem->lock
>    &sma->sem_base[0...sma->sem_nsems].lock
>    &sma->sem_perm.lock
>
> a condition variable:
>
>    sma->complex_mode
>
> and a new barrier:
>
>    smp_mb__after_spin_lock()
>
> For simplicity, we can make sma->sem_nsems == 1, and have &sma->sem_base[0]
> be &sem->lock in the example above.
Correct.
>   &sma->sem_perm.lock seems to be
> irrelevant.
Correct.
> The litmus test then looks a bit like:
>
> CPUm:
>
> LOCK(x)
> smp_mb();
> RyAcq=0
>
>
> CPUn:
>
> Wy=1
> smp_mb();
> UNLOCK_WAIT(x)
Correct.
>
> which I think can be simplified to:
>
>
> LOCK(x)
I thought that here a barrier is required, because Ry=0 could be before 
store of the lock.
> Ry=0
RyAcq instead of Ry would required due to the unlock at the end of the 
critical section
CpuN: <...>
           WyRelease=0
for the litmus test irrelevant.
> Wy=1
> smp_mb(); // Note that this is implied by spin_unlock_wait on PPC and arm64
> LOCK(x)   // spin_unlock_wait behaves like lock; unlock
> UNLOCK(x)

> [I've removed a bunch of barriers here, that I don't think are necessary
>   for the guarantees you're after]
>
> and the question is "Can both CPUs proceed?".
>
> Looking at the above, then I don't think that they can. Whilst CPUm can
> indeed speculate the Ry=0 before successfully taking the lock, if CPUn
> observes CPUm's read, then it must also observe the lock being held wrt
> the spin_lock API. That is because a successful LOCK operation by CPUn
> would force CPUm to replay its LL/SC loop and therefore discard its
> speculation of y.
>
> What am I missing? The code snippet seems to have too many barriers to me!
spin_unlock_wait() is not necessarily lock()+unlock().
It can be a simple Rx, or now RxAcq.

So I had assumed:

CPUm:

LOCK(x)
smp_mb(); /* at least for PPC, therefore with arch override */
RyAcq=0


CPUn:

Wy=1
smp_mb(); /* at least for archs where UNLOCK_WAIT is RxAcq */
UNLOCK_WAIT(x)
smp_rmb(); /* not required anymore, was required when UNLOCK_WAIT was Rx */


--
     Manfred

[toc] | [prev] | [next] | [standalone]

#1474175 — Re: [PATCH 1/4] spinlock: Document memory barrier rules

On Wed, Aug 31, 2016 at 08:32:18PM +0200, Manfred Spraul wrote:
> On 08/31/2016 06:40 PM, Will Deacon wrote:

> >The litmus test then looks a bit like:
> >
> >CPUm:
> >
> >LOCK(x)
> >smp_mb();
> >RyAcq=0
> >
> >
> >CPUn:
> >
> >Wy=1
> >smp_mb();
> >UNLOCK_WAIT(x)
> Correct.
> >
> >which I think can be simplified to:
> >
> >
> >LOCK(x)
> I thought that here a barrier is required, because Ry=0 could be before
> store of the lock.
> >Ry=0
> RyAcq instead of Ry would required due to the unlock at the end of the
> critical section
> CpuN: <...>
>           WyRelease=0
> for the litmus test irrelevant.
> >Wy=1
> >smp_mb(); // Note that this is implied by spin_unlock_wait on PPC and arm64
> >LOCK(x)   // spin_unlock_wait behaves like lock; unlock
> >UNLOCK(x)
> 
> >[I've removed a bunch of barriers here, that I don't think are necessary
> >  for the guarantees you're after]
> >
> >and the question is "Can both CPUs proceed?".
> >
> >Looking at the above, then I don't think that they can. Whilst CPUm can
> >indeed speculate the Ry=0 before successfully taking the lock, if CPUn
> >observes CPUm's read, then it must also observe the lock being held wrt
> >the spin_lock API. That is because a successful LOCK operation by CPUn
> >would force CPUm to replay its LL/SC loop and therefore discard its
> >speculation of y.
> >
> >What am I missing? The code snippet seems to have too many barriers to me!

> spin_unlock_wait() is not necessarily lock()+unlock().
> It can be a simple Rx, or now RxAcq.

Can be, normally, yes. But on power and arm64, the only architectures on
which the ACQUIRE is 'funny' they do the 'pointless' ll/sc cycle in
spin_unlock_wait() to 'fix' things.

So for both power and arm64, you can in fact model spin_unlock_wait()
as LOCK+UNLOCK.

All the other archs have (so far) 'sensible' ACQUIRE semantics and all
this is moot.

[ MIPS _could_ possibly do the 'interesting' ACQUIRE too, but so far
  hasn't introduced their fancy barriers. ]

The other interesting case is qspinlock, which does the unordered store
in software, but that is after a necessary atomic (ACQUIRE) operation to
enqueue, which we exploit in the queued_spin_unlock_wait() to order
against. So that too is good, assuming the ACQUIRE is good.

Once Power/ARM64 use qspinlock, they'll need to be careful again.

[toc] | [prev] | [next] | [standalone]

#1474282 — Re: [PATCH 1/4] spinlock: Document memory barrier rules

Hi,

On 09/01/2016 10:44 AM, Peter Zijlstra wrote:
> On Wed, Aug 31, 2016 at 08:32:18PM +0200, Manfred Spraul wrote:
>> On 08/31/2016 06:40 PM, Will Deacon wrote:
>>> The litmus test then looks a bit like:
>>>
>>> CPUm:
>>>
>>> LOCK(x)
>>> smp_mb();
>>> RyAcq=0
>>>
>>>
>>> CPUn:
>>>
>>> Wy=1
>>> smp_mb();
>>> UNLOCK_WAIT(x)
>> Correct.
>>> which I think can be simplified to:
>>>
>>>
>>> LOCK(x)
>> I thought that here a barrier is required, because Ry=0 could be before
>> store of the lock.
>>> Ry=0
>> RyAcq instead of Ry would required due to the unlock at the end of the
>> critical section
>> CpuN: <...>
>>            WyRelease=0
>> for the litmus test irrelevant.
>>> Wy=1
>>> smp_mb(); // Note that this is implied by spin_unlock_wait on PPC and arm64
>>> LOCK(x)   // spin_unlock_wait behaves like lock; unlock
>>> UNLOCK(x)
>>> [I've removed a bunch of barriers here, that I don't think are necessary
>>>   for the guarantees you're after]
>>>
>>> and the question is "Can both CPUs proceed?".
>>>
>>> Looking at the above, then I don't think that they can. Whilst CPUm can
>>> indeed speculate the Ry=0 before successfully taking the lock, if CPUn
>>> observes CPUm's read, then it must also observe the lock being held wrt
>>> the spin_lock API. That is because a successful LOCK operation by CPUn
>>> would force CPUm to replay its LL/SC loop and therefore discard its
>>> speculation of y.
>>>
>>> What am I missing? The code snippet seems to have too many barriers to me!
>> spin_unlock_wait() is not necessarily lock()+unlock().
>> It can be a simple Rx, or now RxAcq.
> Can be, normally, yes. But on power and arm64, the only architectures on
> which the ACQUIRE is 'funny' they do the 'pointless' ll/sc cycle in
> spin_unlock_wait() to 'fix' things.
>
> So for both power and arm64, you can in fact model spin_unlock_wait()
> as LOCK+UNLOCK.
Is this consensus?

If I understand it right, the rules are:
1. spin_unlock_wait() must behave like spin_lock();spin_unlock();
2. spin_is_locked() must behave like spin_trylock() ? spin_unlock(),TRUE 
: FALSE
3. the ACQUIRE during spin_lock applies to the lock load, not to the store.

sem.c and nf_conntrack.c need only rule 1 now, but I would document the 
rest as well, ok?

I'll update the patches.

--
     Manfred

[toc] | [prev] | [next] | [standalone]

#1474292 — Re: [PATCH 1/4] spinlock: Document memory barrier rules

On Thu, Sep 01, 2016 at 01:04:26PM +0200, Manfred Spraul wrote:
> If I understand it right, the rules are:
> 1. spin_unlock_wait() must behave like spin_lock();spin_unlock();
> 2. spin_is_locked() must behave like spin_trylock() ? spin_unlock(),TRUE :
> FALSE

I don't think spin_is_locked is as strong as all that. On arm64 and ppc,
it's just smp_mb(); followed by a check on the lock value. It can't be
used for the same sorts of inter-CPU synchronisation that spin_unlock_wait
provides.

> 3. the ACQUIRE during spin_lock applies to the lock load, not to the store.

Correct. This is already documented for things like cmpxchg.

> sem.c and nf_conntrack.c need only rule 1 now, but I would document the rest
> as well, ok?
> 
> I'll update the patches.

Please CC me!

Will

[toc] | [prev] | [next] | [standalone]

#1474357 — Re: [PATCH 1/4] spinlock: Document memory barrier rules

On Thu, Sep 01, 2016 at 01:04:26PM +0200, Manfred Spraul wrote:

> >So for both power and arm64, you can in fact model spin_unlock_wait()
> >as LOCK+UNLOCK.

> Is this consensus?

Dunno, but it was done to fix your earlier locking scheme and both
architectures where it matters have done so.

So I suppose that could be taken as consensus ;-)

> If I understand it right, the rules are:
> 1. spin_unlock_wait() must behave like spin_lock();spin_unlock();

From a barrier perspective, yes I think so. Ideally the implementation
would avoid stores (which was the entire point of introducing that
primitive IIRC) if at all possible (not possible on ARM64/Power).

> 2. spin_is_locked() must behave like spin_trylock() ? spin_unlock(),TRUE :
> FALSE

Not sure on this one, That might be consistent, but I don't see the
ll/sc-nop in there. Will?

> 3. the ACQUIRE during spin_lock applies to the lock load, not to the store.

I think we can state that ACQUIRE on _any_ atomic only applies to the
LOAD not the STORE.

And we're waiting for that to bite us again before trying to deal with
it in a more generic manner; for now only the spinlock implementations
(specifically spin_unlock_wait) deal with it.


Will, Boqun, did I get that right?

[toc] | [prev] | [next] | [standalone]

#1474418 — Re: [PATCH 1/4] spinlock: Document memory barrier rules

[Multipart message — attachments visible in raw view] — view raw

On Thu, Sep 01, 2016 at 01:51:34PM +0200, Peter Zijlstra wrote:
> On Thu, Sep 01, 2016 at 01:04:26PM +0200, Manfred Spraul wrote:
> 
> > >So for both power and arm64, you can in fact model spin_unlock_wait()
> > >as LOCK+UNLOCK.
> 
> > Is this consensus?
> 
> Dunno, but it was done to fix your earlier locking scheme and both
> architectures where it matters have done so.
> 
> So I suppose that could be taken as consensus ;-)
> 
> > If I understand it right, the rules are:
> > 1. spin_unlock_wait() must behave like spin_lock();spin_unlock();
> 
> From a barrier perspective, yes I think so. Ideally the implementation
> would avoid stores (which was the entire point of introducing that
> primitive IIRC) if at all possible (not possible on ARM64/Power).
> 
> > 2. spin_is_locked() must behave like spin_trylock() ? spin_unlock(),TRUE :
> > FALSE
> 
> Not sure on this one, That might be consistent, but I don't see the
> ll/sc-nop in there. Will?
> 

My understanding is as Will stated, we don't provide this strong
gaurantee for spin_is_locked(). The reason is mostly because all(?)
uses of spin_is_locked() are not for correctness but for other purposes
like debug output.

> > 3. the ACQUIRE during spin_lock applies to the lock load, not to the store.
> 
> I think we can state that ACQUIRE on _any_ atomic only applies to the
> LOAD not the STORE.
> 
> And we're waiting for that to bite us again before trying to deal with

;-)

> it in a more generic manner; for now only the spinlock implementations
> (specifically spin_unlock_wait) deal with it.
> 

I think the hope is that, with herd or other tools, and a formal order
model, we can make more people understand this "counter-intuitive"
behavior and help them write correct and efficient code ;-)

> 
> Will, Boqun, did I get that right?
> 

Yep ;-)

Regards,
Boqun

[toc] | [prev] | [next] | [standalone]

#1471717

Please use --no-chain-reply-to.

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web