Skip to contentSkip to conversation

locking/qrwlock: Rename ->lock to ->wait_lock

PATCH In review Davidlohr Bueso 6 participants 28 messages Sep 14, 2015 – Sep 25, 2015

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

PATCH 1/3 locking/qrwlock: Rename ->lock to ->wait_lock

... trivial, but reads a little nicer when we name our actual primitive 'lock'.

---
 include/asm-generic/qrwlock_types.h | 4 ++--
 kernel/locking/qrwlock.c            | 8 ++++----
 2 files changed, 6 insertions(+), 6 deletions(-)
include/asm-generic/qrwlock_types.h +2 -2
index 4d76f24..0abc6b6 100644
@@ -10,12 +10,12 @@
 
 typedef struct qrwlock {
 	atomic_t		cnts;
-	arch_spinlock_t		lock;
+	arch_spinlock_t		wait_lock;
 } arch_rwlock_t;
 
 #define	__ARCH_RW_LOCK_UNLOCKED {		\
 	.cnts = ATOMIC_INIT(0),			\
-	.lock = __ARCH_SPIN_LOCK_UNLOCKED,	\
+	.wait_lock = __ARCH_SPIN_LOCK_UNLOCKED,	\
 }
 
 #endif /* __ASM_GENERIC_QRWLOCK_TYPES_H */
kernel/locking/qrwlock.c +4 -4
index f17a3e3..fec0823 100644
@@ -86,7 +86,7 @@ void queued_read_lock_slowpath(struct qrwlock *lock, u32 cnts)
 	/*
 	 * Put the reader into the wait queue
 	 */
-	arch_spin_lock(&lock->lock);
+	arch_spin_lock(&lock->wait_lock);
 
 	/*
 	 * The ACQUIRE semantics of the following spinning code ensure
@@ -99,7 +99,7 @@ void queued_read_lock_slowpath(struct qrwlock *lock, u32 cnts)
 	/*
 	 * Signal the next one in queue to become queue head
 	 */
-	arch_spin_unlock(&lock->lock);
+	arch_spin_unlock(&lock->wait_lock);
 }
 EXPORT_SYMBOL(queued_read_lock_slowpath);
 
@@ -112,7 +112,7 @@ void queued_write_lock_slowpath(struct qrwlock *lock)
 	u32 cnts;
 
 	/* Put the writer into the wait queue */
-	arch_spin_lock(&lock->lock);
+	arch_spin_lock(&lock->wait_lock);
 
 	/* Try to acquire the lock directly if no reader is present */
 	if (!atomic_read(&lock->cnts) &&
@@ -144,6 +144,6 @@ void queued_write_lock_slowpath(struct qrwlock *lock)
 		cpu_relax_lowlatency();
 	}
 unlock:
-	arch_spin_unlock(&lock->lock);
+	arch_spin_unlock(&lock->wait_lock);
 }
 EXPORT_SYMBOL(queued_write_lock_slowpath);
Signature · 1 line
2.1.4
#1 lore raw

PATCH 2/3 sched/wake_q: Relax to acquire semantics

The barrier parings for wake-queues are very straightforward, and thus we can ease the barrier requirements, for archs that support it, for wake_q_add by relying on acquire semantics. As such, (i) we keep the pairing structure/logic and (ii) users, such as mqueues, can continue to rely on a full barrier after the successful [Rmw].

[Another alternative could be to just not try at all and fully downgrade to cmpxchg_relaxed() and rely on users to enable their own synchronization. But controlling this ourselves makes me sleep better at night.]

---
 kernel/sched/core.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)
kernel/sched/core.c +6 -6
index 6ab415a..7567603 100644
@@ -523,14 +523,14 @@ void wake_q_add(struct wake_q_head *head, struct task_struct *task)
 	struct wake_q_node *node = &task->wake_q;
 
 	/*
-	 * Atomically grab the task, if ->wake_q is !nil already it means
-	 * its already queued (either by us or someone else) and will get the
-	 * wakeup due to that.
+	 * Atomically grab the task. If ->wake_q is non-nil (failed cmpxchg)
+	 * then the task is already queued (by us or someone else) and will
+	 * get the wakeup due to that.
 	 *
-	 * This cmpxchg() implies a full barrier, which pairs with the write
-	 * barrier implied by the wakeup in wake_up_list().
+	 * Use acquire semantics to add the next pointer, which pairs with the
+	 * write barrier implied by the wakeup in wake_up_list().
 	 */
-	if (cmpxchg(&node->next, NULL, WAKE_Q_TAIL))
+	if (cmpxchg_acquire(&node->next, NULL, WAKE_Q_TAIL))
 		return;
 
 	get_task_struct(task);
Signature · 1 line
2.1.4
maintainer
#2 lore raw

Re: [PATCH -tip 2/3] sched/wake_q: Relax to acquire semantics

Quoted 20 lines · Davidlohr Bueso

The barrier parings for wake-queues are very straightforward, and thus we can ease the barrier requirements, for archs that support it, for wake_q_add by relying on acquire semantics. As such, (i) we keep the pairing structure/logic and (ii) users, such as mqueues, can continue to rely on a full barrier after the successful [Rmw].

---
 kernel/sched/core.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)
kernel/sched/core.c +1 -0
index 6ab415a..7567603 100644
@@ -523,14 +523,14 @@ void wake_q_add(struct wake_q_head *head, struct task_struct *task)
 	struct wake_q_node *node = &task->wake_q;
 
 	/*
+	 * Atomically grab the task. If ->wake_q is non-nil (failed cmpxchg)

kernel/sched/core.c void wake_q_add(struct wake_q_head *head, struct task_struct *task) · line 536

Quoted 10 lines
kernel/sched/core.c +5 -0
+	 * then the task is already queued (by us or someone else) and will
+	 * get the wakeup due to that.
 	 *
+	 * Use acquire semantics to add the next pointer, which pairs with the
+	 * write barrier implied by the wakeup in wake_up_list().
 	 */
+	if (cmpxchg_acquire(&node->next, NULL, WAKE_Q_TAIL))
 		return;
 
 	get_task_struct(task);

I'm not seeing a _why_ on the acquire semantics. Not saying the patch is wrong, just saying I want words on why acquire is correct.

#3 lore raw

Re: [PATCH -tip 2/3] sched/wake_q: Relax to acquire semantics

Quoted 12 lines · Peter Zijlstra
Quoted 11 lines · Davidlohr Bueso
	/*
kernel/sched/core.c +3 -0
+	 * Atomically grab the task. If ->wake_q is non-nil (failed cmpxchg)
+	 * then the task is already queued (by us or someone else) and will
+	 * get the wakeup due to that.
	 *
kernel/sched/core.c +2 -0
+	 * Use acquire semantics to add the next pointer, which pairs with the
+	 * write barrier implied by the wakeup in wake_up_list().
	 */
kernel/sched/core.c +1 -0
+	if (cmpxchg_acquire(&node->next, NULL, WAKE_Q_TAIL))
		return;
Quoted 4 lines
Quoted 1 line
	get_task_struct(task);

I'm not seeing a _why_ on the acquire semantics. Not saying the patch is wrong, just saying I want words on why acquire is correct.

Well, I was just taking advantage of removing the upper barrier. Considering that the formal semantics, you are right that we need not actual acquire per-se (ie for node->next) but instead merely ensure a barrier in wake_q_add(). This is kind of why I had hinted of going full _relaxed(). We could also rephrase the comment, something like:

* Use ACQUIRE semantics to add the next pointer, such that
* wake_q_add() implies a full barrier. This pairs with the
* write barrier implied by the wakeup in wake_up_list(). */

What do you think?

maintainer
#4 lore raw

Re: [PATCH -tip 2/3] sched/wake_q: Relax to acquire semantics

Quoted 25 lines · Davidlohr Bueso
Quoted 12 lines · Peter Zijlstra
Quoted 11 lines · Davidlohr Bueso
	/*
kernel/sched/core.c +3 -0
+	 * Atomically grab the task. If ->wake_q is non-nil (failed cmpxchg)
+	 * then the task is already queued (by us or someone else) and will
+	 * get the wakeup due to that.
	 *
kernel/sched/core.c +2 -0
+	 * Use acquire semantics to add the next pointer, which pairs with the
+	 * write barrier implied by the wakeup in wake_up_list().
	 */
kernel/sched/core.c +1 -0
+	if (cmpxchg_acquire(&node->next, NULL, WAKE_Q_TAIL))
		return;
Quoted 4 lines
Quoted 1 line
	get_task_struct(task);

I'm not seeing a _why_ on the acquire semantics. Not saying the patch is wrong, just saying I want words on why acquire is correct.

Well, I was just taking advantage of removing the upper barrier. Considering that the formal semantics, you are right that we need not actual acquire per-se (ie for node->next) but instead merely ensure a barrier in wake_q_add(). This is kind of why I had hinted of going full _relaxed(). We could also rephrase the comment, something like:

Quoted 6 lines

* Use ACQUIRE semantics to add the next pointer, such that
* wake_q_add() implies a full barrier. This pairs with the
* write barrier implied by the wakeup in wake_up_list(). */

What do you think?

Still befuddled. I'm thinking that if you want to remove a barrier, you'd remove that second and keep the first. That is RELEASE.

That way, you know the stores prior to the wake queue are done by the time you observe the queued entry, and therefore (transitively) know those stores are done by the time you do the actual wakeup.

Two issues with that though; firstly RELEASE is not actually guaranteed to be transitive -- now the only arch that does not implement it with a full barrier is ARGH64, so we could just ask Will, but I'm not sure its 'good' to start relying on this.

Secondly, the wake queues are not concurrent, they're in context, so I don't see ordering matter at all. The only reason its a cmpxchg() is because there is the (small) possibility of two contexts wanting to wake the same task, and we use task_struct storage for the queue.

Or am I mistaken and do we have concurrent users of wake queues?

maintainer
#5 lore raw

Re: [PATCH -tip 2/3] sched/wake_q: Relax to acquire semantics

Quoted 36 lines · Peter Zijlstra
Quoted 25 lines · Davidlohr Bueso
Quoted 12 lines · Peter Zijlstra
Quoted 11 lines · Davidlohr Bueso
	/*
kernel/sched/core.c +3 -0
+	 * Atomically grab the task. If ->wake_q is non-nil (failed cmpxchg)
+	 * then the task is already queued (by us or someone else) and will
+	 * get the wakeup due to that.
	 *
kernel/sched/core.c +2 -0
+	 * Use acquire semantics to add the next pointer, which pairs with the
+	 * write barrier implied by the wakeup in wake_up_list().
	 */
kernel/sched/core.c +1 -0
+	if (cmpxchg_acquire(&node->next, NULL, WAKE_Q_TAIL))
		return;
Quoted 4 lines
Quoted 1 line
	get_task_struct(task);

I'm not seeing a _why_ on the acquire semantics. Not saying the patch is wrong, just saying I want words on why acquire is correct.

Well, I was just taking advantage of removing the upper barrier. Considering that the formal semantics, you are right that we need not actual acquire per-se (ie for node->next) but instead merely ensure a barrier in wake_q_add(). This is kind of why I had hinted of going full _relaxed(). We could also rephrase the comment, something like:

Quoted 6 lines

* Use ACQUIRE semantics to add the next pointer, such that
* wake_q_add() implies a full barrier. This pairs with the
* write barrier implied by the wakeup in wake_up_list(). */

What do you think?

Still befuddled. I'm thinking that if you want to remove a barrier, you'd remove that second and keep the first. That is RELEASE.

Quoted 8 lines

That way, you know the stores prior to the wake queue are done by the time you observe the queued entry, and therefore (transitively) know those stores are done by the time you do the actual wakeup.

Two issues with that though; firstly RELEASE is not actually guaranteed to be transitive -- now the only arch that does not implement it with a full barrier is ARGH64, so we could just ask Will, but I'm not sure its 'good' to start relying on this.

Never mind, the PPC people will implement this with lwsync and that is very much not transitive IIRC.

That said, you could do:

	smp_mb__before_atomic();
	cmpxchg_relaxed();

Which would still be a full barrier and therefore transitive. However this point still stands:

Quoted 4 lines

Secondly, the wake queues are not concurrent, they're in context, so I don't see ordering matter at all. The only reason its a cmpxchg() is because there is the (small) possibility of two contexts wanting to wake the same task, and we use task_struct storage for the queue.

I don't think we need _any_ barriers here, unless we have concurrent users of the wake queues (or want to allow any, do we?).

#6 lore raw

Re: [PATCH -tip 2/3] sched/wake_q: Relax to acquire semantics

Quoted 41 lines · Peter Zijlstra
Quoted 40 lines · Peter Zijlstra
Quoted 25 lines · Davidlohr Bueso
Quoted 12 lines · Peter Zijlstra
Quoted 11 lines · Davidlohr Bueso
	/*
kernel/sched/core.c +3 -0
+	 * Atomically grab the task. If ->wake_q is non-nil (failed cmpxchg)
+	 * then the task is already queued (by us or someone else) and will
+	 * get the wakeup due to that.
	 *
kernel/sched/core.c +2 -0
+	 * Use acquire semantics to add the next pointer, which pairs with the
+	 * write barrier implied by the wakeup in wake_up_list().
	 */
kernel/sched/core.c +1 -0
+	if (cmpxchg_acquire(&node->next, NULL, WAKE_Q_TAIL))
		return;
Quoted 4 lines
Quoted 1 line
	get_task_struct(task);

I'm not seeing a _why_ on the acquire semantics. Not saying the patch is wrong, just saying I want words on why acquire is correct.

Well, I was just taking advantage of removing the upper barrier. Considering that the formal semantics, you are right that we need not actual acquire per-se (ie for node->next) but instead merely ensure a barrier in wake_q_add(). This is kind of why I had hinted of going full _relaxed(). We could also rephrase the comment, something like:

Quoted 6 lines

* Use ACQUIRE semantics to add the next pointer, such that
* wake_q_add() implies a full barrier. This pairs with the
* write barrier implied by the wakeup in wake_up_list(). */

What do you think?

Still befuddled. I'm thinking that if you want to remove a barrier, you'd remove that second and keep the first. That is RELEASE.

That way, you know the stores prior to the wake queue are done by the time you observe the queued entry, and therefore (transitively) know those stores are done by the time you do the actual wakeup.

Quoted 7 lines
Quoted 4 lines

Two issues with that though; firstly RELEASE is not actually guaranteed to be transitive -- now the only arch that does not implement it with a full barrier is ARGH64, so we could just ask Will, but I'm not sure its 'good' to start relying on this.

Never mind, the PPC people will implement this with lwsync and that is very much not transitive IIRC.

I am probably lost on context, but...

It turns out that lwsync is transitive in special cases. One of them is a series of release-acquire pairs, which can extend indefinitely.

Does that help in this case?

Thanx, Paul

Quoted 16 lines

That said, you could do:

	smp_mb__before_atomic();
	cmpxchg_relaxed();

Which would still be a full barrier and therefore transitive. However this point still stands:

Quoted 4 lines

Secondly, the wake queues are not concurrent, they're in context, so I don't see ordering matter at all. The only reason its a cmpxchg() is because there is the (small) possibility of two contexts wanting to wake the same task, and we use task_struct storage for the queue.

I don't think we need _any_ barriers here, unless we have concurrent users of the wake queues (or want to allow any, do we?).

maintainer
#7 lore raw

Re: [PATCH -tip 2/3] sched/wake_q: Relax to acquire semantics

Quoted 9 lines · Paul E. McKenney
Quoted 2 lines

Never mind, the PPC people will implement this with lwsync and that is very much not transitive IIRC.

I am probably lost on context, but...

It turns out that lwsync is transitive in special cases. One of them is a series of release-acquire pairs, which can extend indefinitely.

Does that help in this case?

Probably not, but good to know. I still don't think we want to rely on ACQUIRE/RELEASE being transitive in general though.

#8 lore raw

Re: [PATCH -tip 2/3] sched/wake_q: Relax to acquire semantics

Quoted 6 lines · Peter Zijlstra
Quoted 5 lines · Paul E. McKenney
Quoted 2 lines

Never mind, the PPC people will implement this with lwsync and that is very much not transitive IIRC.

I am probably lost on context, but...

Quoted 7 lines
Quoted 4 lines

It turns out that lwsync is transitive in special cases. One of them is a series of release-acquire pairs, which can extend indefinitely.

Does that help in this case?

Probably not, but good to know. I still don't think we want to rely on ACQUIRE/RELEASE being transitive in general though.

OK, I will bite... Why not?

Thanx, Paul

maintainer
#9 lore raw

Re: [PATCH -tip 2/3] sched/wake_q: Relax to acquire semantics

Quoted 10 lines · Paul E. McKenney
Quoted 9 lines · Peter Zijlstra
Quoted 8 lines · Paul E. McKenney
Quoted 2 lines

Never mind, the PPC people will implement this with lwsync and that is very much not transitive IIRC.

I am probably lost on context, but...

It turns out that lwsync is transitive in special cases. One of them is a series of release-acquire pairs, which can extend indefinitely.

Quoted 6 lines
Quoted 4 lines
Quoted 1 line

Does that help in this case?

Probably not, but good to know. I still don't think we want to rely on ACQUIRE/RELEASE being transitive in general though.

OK, I will bite... Why not?

It would mean us reviewing all archs (again) and documenting it I suppose. Which is of course entirely possible.

That said, I don't think the case at hand requires it, so lets postpone this for now ;-)

#10 lore raw

Re: [PATCH -tip 2/3] sched/wake_q: Relax to acquire semantics

Quoted 16 lines · Peter Zijlstra
Quoted 15 lines · Paul E. McKenney
Quoted 13 lines · Peter Zijlstra
Quoted 9 lines · Paul E. McKenney
Quoted 2 lines

Never mind, the PPC people will implement this with lwsync and that is very much not transitive IIRC.

I am probably lost on context, but...

It turns out that lwsync is transitive in special cases. One of them is a series of release-acquire pairs, which can extend indefinitely.

Does that help in this case?

Probably not, but good to know. I still don't think we want to rely on ACQUIRE/RELEASE being transitive in general though.

Quoted 7 lines
Quoted 1 line

OK, I will bite... Why not?

It would mean us reviewing all archs (again) and documenting it I suppose. Which is of course entirely possible.

That said, I don't think the case at hand requires it, so lets postpone this for now ;-)

True enough, but in my experience smp_store_release() and smp_load_acquire() are a -lot- easier to use than other barriers, and transitivity will help promote their use. So...

All the TSO architectures (x86, s390, SPARC, HPPA, ...) support transitive smp_store_release()/smp_load_acquire() via their native ordering in combination with barrier() macros. x86 with CONFIG_X86_PPRO_FENCE=y, which is not TSO, uses an mfence instruction. Power supports this via lwsync's partial cumulativity. ARM64 supports it in SMP via the new ldar and stlr instructions (in non-SMP, it uses barrier(), which suffices in that case). IA64 supports this via total ordering of all release instructions in theory and by the actual full-barrier implementation in practice (and the fact that gcc emits st.rel and ld.acq instructions for volatile stores and loads). All other architectures use smp_mb(), which is transitive.

Did I miss anything?

Thanx, Paul

maintainer
#11 lore raw

Re: [PATCH -tip 2/3] sched/wake_q: Relax to acquire semantics

Quoted 41 lines · Paul E. McKenney
Quoted 16 lines · Peter Zijlstra
Quoted 15 lines · Paul E. McKenney
Quoted 13 lines · Peter Zijlstra
Quoted 9 lines · Paul E. McKenney
Quoted 2 lines

Never mind, the PPC people will implement this with lwsync and that is very much not transitive IIRC.

I am probably lost on context, but...

It turns out that lwsync is transitive in special cases. One of them is a series of release-acquire pairs, which can extend indefinitely.

Does that help in this case?

Probably not, but good to know. I still don't think we want to rely on ACQUIRE/RELEASE being transitive in general though.

Quoted 7 lines
Quoted 1 line

OK, I will bite... Why not?

It would mean us reviewing all archs (again) and documenting it I suppose. Which is of course entirely possible.

That said, I don't think the case at hand requires it, so lets postpone this for now ;-)

True enough, but in my experience smp_store_release() and smp_load_acquire() are a -lot- easier to use than other barriers, and transitivity will help promote their use. So...

All the TSO architectures (x86, s390, SPARC, HPPA, ...) support transitive smp_store_release()/smp_load_acquire() via their native ordering in combination with barrier() macros. x86 with CONFIG_X86_PPRO_FENCE=y, which is not TSO, uses an mfence instruction. Power supports this via lwsync's partial cumulativity. ARM64 supports it in SMP via the new ldar and stlr instructions (in non-SMP, it uses barrier(), which suffices in that case). IA64 supports this via total ordering of all release instructions in theory and by the actual full-barrier implementation in practice (and the fact that gcc emits st.rel and ld.acq instructions for volatile stores and loads). All other architectures use smp_mb(), which is transitive.

Quoted 1 line

Did I miss anything?

I think that about covers it.. the only odd duckling might be s390 which is documented as TSO but recently grew smp_mb__{before,after}_atomic(), which seems to confuse matters.

#12 lore raw

Re: [PATCH -tip 2/3] sched/wake_q: Relax to acquire semantics

Quoted 42 lines · Peter Zijlstra
Quoted 41 lines · Paul E. McKenney
Quoted 16 lines · Peter Zijlstra
Quoted 15 lines · Paul E. McKenney
Quoted 13 lines · Peter Zijlstra
Quoted 9 lines · Paul E. McKenney
Quoted 2 lines

Never mind, the PPC people will implement this with lwsync and that is very much not transitive IIRC.

I am probably lost on context, but...

It turns out that lwsync is transitive in special cases. One of them is a series of release-acquire pairs, which can extend indefinitely.

Does that help in this case?

Probably not, but good to know. I still don't think we want to rely on ACQUIRE/RELEASE being transitive in general though.

Quoted 7 lines
Quoted 1 line

OK, I will bite... Why not?

It would mean us reviewing all archs (again) and documenting it I suppose. Which is of course entirely possible.

That said, I don't think the case at hand requires it, so lets postpone this for now ;-)

True enough, but in my experience smp_store_release() and smp_load_acquire() are a -lot- easier to use than other barriers, and transitivity will help promote their use. So...

All the TSO architectures (x86, s390, SPARC, HPPA, ...) support transitive smp_store_release()/smp_load_acquire() via their native ordering in combination with barrier() macros. x86 with CONFIG_X86_PPRO_FENCE=y, which is not TSO, uses an mfence instruction. Power supports this via lwsync's partial cumulativity. ARM64 supports it in SMP via the new ldar and stlr instructions (in non-SMP, it uses barrier(), which suffices in that case). IA64 supports this via total ordering of all release instructions in theory and by the actual full-barrier implementation in practice (and the fact that gcc emits st.rel and ld.acq instructions for volatile stores and loads). All other architectures use smp_mb(), which is transitive.

Quoted 5 lines
Quoted 1 line

Did I miss anything?

I think that about covers it.. the only odd duckling might be s390 which is documented as TSO but recently grew smp_mb__{before,after}_atomic(), which seems to confuse matters.

Fair point, adding Martin and Heiko on CC for their thoughts.

It looks like this applies to recent mainframes that have new atomic instructions, which, yes, might need something to make them work with fully transitive smp_load_acquire() and smp_store_release().

Martin, Heiko, the question is whether or not the current s390 smp_store_release() and smp_load_acquire() can be transitive. For example, if all the Xi variables below are initially zero, is it possible for all the r0, r1, r2, ... rN variables to have the value 1 at the end of the test.

CPU 0

	r0 = smp_load_acquire(&X0);
	smp_store_release(&X1, 1);

CPU 1

	r1 = smp_load_acquire(&X1);
	smp_store_release(&X2, 1);

CPU 2

	r2 = smp_load_acquire(&X2);
	smp_store_release(&X3, 1);

...

CPU N

	rN = smp_load_acquire(&XN);
	smp_store_release(&X0, 1);

If smp_store_release() and smp_load_acquire() are transitive, the answer would be "no".

A similar litmus test involving atomics would be as follows, again with all Xi initially zero:

CPU 0

	atomic_inc(&X0);
	smp_store_release(&X1, 1);

CPU 1

	r1 = smp_load_acquire(&X1);
	smp_store_release(&X2, 1);

CPU 2

	r2 = smp_load_acquire(&X2);
	smp_store_release(&X3, 1);

...

CPU N

	rN = smp_load_acquire(&XN);
	r0 = atomic_read(&X0);

Here, the question is whether r0 can be zero, but r1, r2, ... rN all being 1 at the end of the test.

Thoughts?

Thanx, Paul

#13 lore raw

Re: [PATCH -tip 2/3] sched/wake_q: Relax to acquire semantics

Quoted 55 lines · Paul E. McKenney
Quoted 42 lines · Peter Zijlstra
Quoted 41 lines · Paul E. McKenney
Quoted 16 lines · Peter Zijlstra
Quoted 15 lines · Paul E. McKenney
Quoted 13 lines · Peter Zijlstra
Quoted 9 lines · Paul E. McKenney
Quoted 2 lines

Never mind, the PPC people will implement this with lwsync and that is very much not transitive IIRC.

I am probably lost on context, but...

It turns out that lwsync is transitive in special cases. One of them is a series of release-acquire pairs, which can extend indefinitely.

Does that help in this case?

Probably not, but good to know. I still don't think we want to rely on ACQUIRE/RELEASE being transitive in general though.

Quoted 7 lines
Quoted 1 line

OK, I will bite... Why not?

It would mean us reviewing all archs (again) and documenting it I suppose. Which is of course entirely possible.

That said, I don't think the case at hand requires it, so lets postpone this for now ;-)

True enough, but in my experience smp_store_release() and smp_load_acquire() are a -lot- easier to use than other barriers, and transitivity will help promote their use. So...

All the TSO architectures (x86, s390, SPARC, HPPA, ...) support transitive smp_store_release()/smp_load_acquire() via their native ordering in combination with barrier() macros. x86 with CONFIG_X86_PPRO_FENCE=y, which is not TSO, uses an mfence instruction. Power supports this via lwsync's partial cumulativity. ARM64 supports it in SMP via the new ldar and stlr instructions (in non-SMP, it uses barrier(), which suffices in that case). IA64 supports this via total ordering of all release instructions in theory and by the actual full-barrier implementation in practice (and the fact that gcc emits st.rel and ld.acq instructions for volatile stores and loads). All other architectures use smp_mb(), which is transitive.

Quoted 5 lines
Quoted 1 line

Did I miss anything?

I think that about covers it.. the only odd duckling might be s390 which is documented as TSO but recently grew smp_mb__{before,after}_atomic(), which seems to confuse matters.

Fair point, adding Martin and Heiko on CC for their thoughts.

It looks like this applies to recent mainframes that have new atomic instructions, which, yes, might need something to make them work with fully transitive smp_load_acquire() and smp_store_release().

Quoted 5 lines

Martin, Heiko, the question is whether or not the current s390 smp_store_release() and smp_load_acquire() can be transitive. For example, if all the Xi variables below are initially zero, is it possible for all the r0, r1, r2, ... rN variables to have the value 1 at the end of the test.

Right... This time actually adding Martin and Heiko on CC...

Thanx, Paul

Quoted 48 lines

CPU 0

	r0 = smp_load_acquire(&X0);
	smp_store_release(&X1, 1);

CPU 1

	r1 = smp_load_acquire(&X1);
	smp_store_release(&X2, 1);

CPU 2

	r2 = smp_load_acquire(&X2);
	smp_store_release(&X3, 1);

...

CPU N

	rN = smp_load_acquire(&XN);
	smp_store_release(&X0, 1);

If smp_store_release() and smp_load_acquire() are transitive, the answer would be "no".

A similar litmus test involving atomics would be as follows, again with all Xi initially zero:

CPU 0

	atomic_inc(&X0);
	smp_store_release(&X1, 1);

CPU 1

	r1 = smp_load_acquire(&X1);
	smp_store_release(&X2, 1);

CPU 2

	r2 = smp_load_acquire(&X2);
	smp_store_release(&X3, 1);

...

CPU N

	rN = smp_load_acquire(&XN);
	r0 = atomic_read(&X0);

Here, the question is whether r0 can be zero, but r1, r2, ... rN all being 1 at the end of the test.

Thoughts?

Thanx, Paul

#14 lore raw

Re: [PATCH -tip 2/3] sched/wake_q: Relax to acquire semantics

Quoted 44 lines · On Fri, 18 Sep 2015 14:41:20 -0700 "Paul E. McKenney"…
Quoted 43 lines · Paul E. McKenney
Quoted 42 lines · Peter Zijlstra
Quoted 41 lines · Paul E. McKenney
Quoted 16 lines · Peter Zijlstra
Quoted 15 lines · Paul E. McKenney
Quoted 13 lines · Peter Zijlstra
Quoted 9 lines · Paul E. McKenney
Quoted 2 lines

Never mind, the PPC people will implement this with lwsync and that is very much not transitive IIRC.

I am probably lost on context, but...

It turns out that lwsync is transitive in special cases. One of them is a series of release-acquire pairs, which can extend indefinitely.

Does that help in this case?

Probably not, but good to know. I still don't think we want to rely on ACQUIRE/RELEASE being transitive in general though.

Quoted 7 lines
Quoted 1 line

OK, I will bite... Why not?

It would mean us reviewing all archs (again) and documenting it I suppose. Which is of course entirely possible.

That said, I don't think the case at hand requires it, so lets postpone this for now ;-)

True enough, but in my experience smp_store_release() and smp_load_acquire() are a -lot- easier to use than other barriers, and transitivity will help promote their use. So...

All the TSO architectures (x86, s390, SPARC, HPPA, ...) support transitive smp_store_release()/smp_load_acquire() via their native ordering in combination with barrier() macros. x86 with CONFIG_X86_PPRO_FENCE=y, which is not TSO, uses an mfence instruction. Power supports this via lwsync's partial cumulativity. ARM64 supports it in SMP via the new ldar and stlr instructions (in non-SMP, it uses barrier(), which suffices in that case). IA64 supports this via total ordering of all release instructions in theory and by the actual full-barrier implementation in practice (and the fact that gcc emits st.rel and ld.acq instructions for volatile stores and loads). All other architectures use smp_mb(), which is transitive.

Quoted 7 lines
Quoted 7 lines
Quoted 5 lines
Quoted 1 line

Did I miss anything?

I think that about covers it.. the only odd duckling might be s390 which is documented as TSO but recently grew smp_mb__{before,after}_atomic(), which seems to confuse matters.

Fair point, adding Martin and Heiko on CC for their thoughts.

Well we always had the full memory barrier for the various versions of smp_mb__xxx, they just have moved around and renamed several times.

After discussing this with Heiko we came to the conclusion that we can use a simple barrier() for smp_mb__before_atomic() and smp_mb__after_atomic().

Quoted 10 lines
Quoted 9 lines

It looks like this applies to recent mainframes that have new atomic instructions, which, yes, might need something to make them work with fully transitive smp_load_acquire() and smp_store_release().

Martin, Heiko, the question is whether or not the current s390 smp_store_release() and smp_load_acquire() can be transitive. For example, if all the Xi variables below are initially zero, is it possible for all the r0, r1, r2, ... rN variables to have the value 1 at the end of the test.

Quoted 24 lines

Right... This time actually adding Martin and Heiko on CC...

Thanx, Paul

Quoted 20 lines

CPU 0

	r0 = smp_load_acquire(&X0);
	smp_store_release(&X1, 1);

CPU 1

	r1 = smp_load_acquire(&X1);
	smp_store_release(&X2, 1);

CPU 2

	r2 = smp_load_acquire(&X2);
	smp_store_release(&X3, 1);

...

CPU N

	rN = smp_load_acquire(&XN);
	smp_store_release(&X0, 1);

If smp_store_release() and smp_load_acquire() are transitive, the answer would be "no".

The answer is "no". Christian recently summarized what the principles of operation has to say about the CPU read / write behavior. If you consider the sequential order of instructions then

1) reads are in order
2) writes are in order
3) reads can happen earlier
4) writes can happen later

Quoted 15 lines
Quoted 15 lines

A similar litmus test involving atomics would be as follows, again with all Xi initially zero:

CPU 0

	atomic_inc(&X0);
	smp_store_release(&X1, 1);

CPU 1

	r1 = smp_load_acquire(&X1);
	smp_store_release(&X2, 1);

CPU 2

	r2 = smp_load_acquire(&X2);
	smp_store_release(&X3, 1);
Quoted 8 lines
Quoted 8 lines

...

CPU N

	rN = smp_load_acquire(&XN);
	r0 = atomic_read(&X0);

Here, the question is whether r0 can be zero, but r1, r2, ... rN all being 1 at the end of the test.

r0 = 0 and all r1, r2, ... rN = 1 can not happen on s390.

Signature · 4 lines
blue skies,
   Martin.

"Reality continues to ruin my life." - Calvin.
#15 lore raw

Re: [PATCH -tip 2/3] sched/wake_q: Relax to acquire semantics

Quoted 96 lines · On Mon, 21 Sep 2015 11:22:52 +0200 Martin Schwidefsky <[email protected]>…
Quoted 44 lines · On Fri, 18 Sep 2015 14:41:20 -0700 "Paul E. McKenney"…
Quoted 43 lines · Paul E. McKenney
Quoted 42 lines · Peter Zijlstra
Quoted 41 lines · Paul E. McKenney
Quoted 16 lines · Peter Zijlstra
Quoted 15 lines · Paul E. McKenney
Quoted 13 lines · Peter Zijlstra
Quoted 9 lines · Paul E. McKenney
Quoted 2 lines

Never mind, the PPC people will implement this with lwsync and that is very much not transitive IIRC.

I am probably lost on context, but...

It turns out that lwsync is transitive in special cases. One of them is a series of release-acquire pairs, which can extend indefinitely.

Does that help in this case?

Probably not, but good to know. I still don't think we want to rely on ACQUIRE/RELEASE being transitive in general though.

Quoted 7 lines
Quoted 1 line

OK, I will bite... Why not?

It would mean us reviewing all archs (again) and documenting it I suppose. Which is of course entirely possible.

That said, I don't think the case at hand requires it, so lets postpone this for now ;-)

True enough, but in my experience smp_store_release() and smp_load_acquire() are a -lot- easier to use than other barriers, and transitivity will help promote their use. So...

All the TSO architectures (x86, s390, SPARC, HPPA, ...) support transitive smp_store_release()/smp_load_acquire() via their native ordering in combination with barrier() macros. x86 with CONFIG_X86_PPRO_FENCE=y, which is not TSO, uses an mfence instruction. Power supports this via lwsync's partial cumulativity. ARM64 supports it in SMP via the new ldar and stlr instructions (in non-SMP, it uses barrier(), which suffices in that case). IA64 supports this via total ordering of all release instructions in theory and by the actual full-barrier implementation in practice (and the fact that gcc emits st.rel and ld.acq instructions for volatile stores and loads). All other architectures use smp_mb(), which is transitive.

Quoted 7 lines
Quoted 7 lines
Quoted 5 lines
Quoted 1 line

Did I miss anything?

I think that about covers it.. the only odd duckling might be s390 which is documented as TSO but recently grew smp_mb__{before,after}_atomic(), which seems to confuse matters.

Fair point, adding Martin and Heiko on CC for their thoughts.

Well we always had the full memory barrier for the various versions of smp_mb__xxx, they just have moved around and renamed several times.

After discussing this with Heiko we came to the conclusion that we can use a simple barrier() for smp_mb__before_atomic() and smp_mb__after_atomic().

Quoted 10 lines
Quoted 9 lines

It looks like this applies to recent mainframes that have new atomic instructions, which, yes, might need something to make them work with fully transitive smp_load_acquire() and smp_store_release().

Martin, Heiko, the question is whether or not the current s390 smp_store_release() and smp_load_acquire() can be transitive. For example, if all the Xi variables below are initially zero, is it possible for all the r0, r1, r2, ... rN variables to have the value 1 at the end of the test.

Quoted 24 lines

Right... This time actually adding Martin and Heiko on CC...

Thanx, Paul

Quoted 20 lines

CPU 0

	r0 = smp_load_acquire(&X0);
	smp_store_release(&X1, 1);

CPU 1

	r1 = smp_load_acquire(&X1);
	smp_store_release(&X2, 1);

CPU 2

	r2 = smp_load_acquire(&X2);
	smp_store_release(&X3, 1);

...

CPU N

	rN = smp_load_acquire(&XN);
	smp_store_release(&X0, 1);

If smp_store_release() and smp_load_acquire() are transitive, the answer would be "no".

Quoted 8 lines

The answer is "no". Christian recently summarized what the principles of operation has to say about the CPU read / write behavior. If you consider the sequential order of instructions then

1) reads are in order
2) writes are in order
3) reads can happen earlier
4) writes can happen later

Correction. The principles of operation states this:

"A storage-operand store specified by one instruction appears to precede all storage-operand stores specified by conceptually subsequent instructions, but it does not necessarily precede storage-operand fetches specified by conceptually subsequent instructions. However, a storage-operand store appears to precede a conceptually subsequent storage-operand fetch from the same main-storage location."

As observed by other CPUs a write to one memory location can "overtake" a read of another memory location if there is no explicit memory-barrier between the load and the store instruction.

In the above example X0, X1, ... XN are different memory locations, so architecturally the answer is "yes", all r0, r1, ... rN variables can have the value of 1 after the test. I doubt that any existing machine will show this behavior though.

Quoted 17 lines
Quoted 17 lines
Quoted 17 lines

A similar litmus test involving atomics would be as follows, again with all Xi initially zero:

CPU 0

	atomic_inc(&X0);
	smp_store_release(&X1, 1);

CPU 1

	r1 = smp_load_acquire(&X1);
	smp_store_release(&X2, 1);

CPU 2

	r2 = smp_load_acquire(&X2);
	smp_store_release(&X3, 1);

...

Quoted 8 lines
Quoted 6 lines
Quoted 6 lines

CPU N

	rN = smp_load_acquire(&XN);
	r0 = atomic_read(&X0);

Here, the question is whether r0 can be zero, but r1, r2, ... rN all being 1 at the end of the test.

r0 = 0 and all r1, r2, ... rN = 1 can not happen on s390.

This indeed can not happen as the atomic_inc is a store type reference which precedes the smp_store_release store type reference.

Signature · 4 lines
blue skies,
   Martin.

"Reality continues to ruin my life." - Calvin.
#16 lore raw

Re: [PATCH -tip 2/3] sched/wake_q: Relax to acquire semantics

Hi Martin,

Quoted 117 lines · Martin Schwidefsky
Quoted 96 lines · On Mon, 21 Sep 2015 11:22:52 +0200 Martin Schwidefsky <[email protected]>…
Quoted 44 lines · On Fri, 18 Sep 2015 14:41:20 -0700 "Paul E. McKenney"…
Quoted 43 lines · Paul E. McKenney
Quoted 42 lines · Peter Zijlstra
Quoted 41 lines · Paul E. McKenney
Quoted 16 lines · Peter Zijlstra
Quoted 15 lines · Paul E. McKenney
Quoted 13 lines · Peter Zijlstra
Quoted 9 lines · Paul E. McKenney
Quoted 2 lines

Never mind, the PPC people will implement this with lwsync and that is very much not transitive IIRC.

I am probably lost on context, but...

It turns out that lwsync is transitive in special cases. One of them is a series of release-acquire pairs, which can extend indefinitely.

Does that help in this case?

Probably not, but good to know. I still don't think we want to rely on ACQUIRE/RELEASE being transitive in general though.

Quoted 7 lines
Quoted 1 line

OK, I will bite... Why not?

It would mean us reviewing all archs (again) and documenting it I suppose. Which is of course entirely possible.

That said, I don't think the case at hand requires it, so lets postpone this for now ;-)

True enough, but in my experience smp_store_release() and smp_load_acquire() are a -lot- easier to use than other barriers, and transitivity will help promote their use. So...

All the TSO architectures (x86, s390, SPARC, HPPA, ...) support transitive smp_store_release()/smp_load_acquire() via their native ordering in combination with barrier() macros. x86 with CONFIG_X86_PPRO_FENCE=y, which is not TSO, uses an mfence instruction. Power supports this via lwsync's partial cumulativity. ARM64 supports it in SMP via the new ldar and stlr instructions (in non-SMP, it uses barrier(), which suffices in that case). IA64 supports this via total ordering of all release instructions in theory and by the actual full-barrier implementation in practice (and the fact that gcc emits st.rel and ld.acq instructions for volatile stores and loads). All other architectures use smp_mb(), which is transitive.

Quoted 7 lines
Quoted 7 lines
Quoted 5 lines
Quoted 1 line

Did I miss anything?

I think that about covers it.. the only odd duckling might be s390 which is documented as TSO but recently grew smp_mb__{before,after}_atomic(), which seems to confuse matters.

Fair point, adding Martin and Heiko on CC for their thoughts.

Well we always had the full memory barrier for the various versions of smp_mb__xxx, they just have moved around and renamed several times.

After discussing this with Heiko we came to the conclusion that we can use a simple barrier() for smp_mb__before_atomic() and smp_mb__after_atomic().

Quoted 10 lines
Quoted 9 lines

It looks like this applies to recent mainframes that have new atomic instructions, which, yes, might need something to make them work with fully transitive smp_load_acquire() and smp_store_release().

Martin, Heiko, the question is whether or not the current s390 smp_store_release() and smp_load_acquire() can be transitive. For example, if all the Xi variables below are initially zero, is it possible for all the r0, r1, r2, ... rN variables to have the value 1 at the end of the test.

Quoted 24 lines

Right... This time actually adding Martin and Heiko on CC...

Thanx, Paul

Quoted 20 lines

CPU 0

	r0 = smp_load_acquire(&X0);
	smp_store_release(&X1, 1);

CPU 1

	r1 = smp_load_acquire(&X1);
	smp_store_release(&X2, 1);

CPU 2

	r2 = smp_load_acquire(&X2);
	smp_store_release(&X3, 1);

...

CPU N

	rN = smp_load_acquire(&XN);
	smp_store_release(&X0, 1);

If smp_store_release() and smp_load_acquire() are transitive, the answer would be "no".

Quoted 8 lines

The answer is "no". Christian recently summarized what the principles of operation has to say about the CPU read / write behavior. If you consider the sequential order of instructions then

1) reads are in order
2) writes are in order
3) reads can happen earlier
4) writes can happen later

Correction. The principles of operation states this:

"A storage-operand store specified by one instruction appears to precede all storage-operand stores specified by conceptually subsequent instructions, but it does not necessarily precede storage-operand fetches specified by conceptually subsequent instructions. However, a storage-operand store appears to precede a conceptually subsequent storage-operand fetch from the same main-storage location."

Quoted 9 lines

As observed by other CPUs a write to one memory location can "overtake" a read of another memory location if there is no explicit memory-barrier between the load and the store instruction.

In the above example X0, X1, ... XN are different memory locations, so architecturally the answer is "yes", all r0, r1, ... rN variables can have the value of 1 after the test. I doubt that any existing machine will show this behavior though.

Just be curious, how about when N == 1? The test then becomes:

CPU 0

	r0 = smp_load_acquire(&X0);
	smp_store_release(&X1,1);

CPU 1

	r1 = smp_load_acquire(&X1);
	smp_store_release(&X0,1);

Is it possible that r0 == 1 and r1 == 1 at the end, due to the same reason?

Regards,
Boqun

Quoted 40 lines
Quoted 17 lines
Quoted 17 lines
Quoted 17 lines

A similar litmus test involving atomics would be as follows, again with all Xi initially zero:

CPU 0

	atomic_inc(&X0);
	smp_store_release(&X1, 1);

CPU 1

	r1 = smp_load_acquire(&X1);
	smp_store_release(&X2, 1);

CPU 2

	r2 = smp_load_acquire(&X2);
	smp_store_release(&X3, 1);

...

Quoted 8 lines
Quoted 6 lines
Quoted 6 lines

CPU N

	rN = smp_load_acquire(&XN);
	r0 = atomic_read(&X0);

Here, the question is whether r0 can be zero, but r1, r2, ... rN all being 1 at the end of the test.

r0 = 0 and all r1, r2, ... rN = 1 can not happen on s390.

This indeed can not happen as the atomic_inc is a store type reference which precedes the smp_store_release store type reference.

Signature · 10 lines
blue skies,
   Martin.

"Reality continues to ruin my life." - Calvin.

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
#17 lore raw

Re: [PATCH -tip 2/3] sched/wake_q: Relax to acquire semantics

Quoted 136 lines · On Tue, 22 Sep 2015 20:23:26 +0800 Boqun Feng <[email protected]> wrote:

Hi Martin,

Quoted 117 lines · Martin Schwidefsky
Quoted 96 lines · On Mon, 21 Sep 2015 11:22:52 +0200 Martin Schwidefsky <[email protected]>…
Quoted 44 lines · On Fri, 18 Sep 2015 14:41:20 -0700 "Paul E. McKenney"…
Quoted 43 lines · Paul E. McKenney
Quoted 42 lines · Peter Zijlstra
Quoted 41 lines · Paul E. McKenney
Quoted 16 lines · Peter Zijlstra
Quoted 15 lines · Paul E. McKenney
Quoted 13 lines · Peter Zijlstra
Quoted 9 lines · Paul E. McKenney
Quoted 2 lines

Never mind, the PPC people will implement this with lwsync and that is very much not transitive IIRC.

I am probably lost on context, but...

It turns out that lwsync is transitive in special cases. One of them is a series of release-acquire pairs, which can extend indefinitely.

Does that help in this case?

Probably not, but good to know. I still don't think we want to rely on ACQUIRE/RELEASE being transitive in general though.

Quoted 7 lines
Quoted 1 line

OK, I will bite... Why not?

It would mean us reviewing all archs (again) and documenting it I suppose. Which is of course entirely possible.

That said, I don't think the case at hand requires it, so lets postpone this for now ;-)

True enough, but in my experience smp_store_release() and smp_load_acquire() are a -lot- easier to use than other barriers, and transitivity will help promote their use. So...

All the TSO architectures (x86, s390, SPARC, HPPA, ...) support transitive smp_store_release()/smp_load_acquire() via their native ordering in combination with barrier() macros. x86 with CONFIG_X86_PPRO_FENCE=y, which is not TSO, uses an mfence instruction. Power supports this via lwsync's partial cumulativity. ARM64 supports it in SMP via the new ldar and stlr instructions (in non-SMP, it uses barrier(), which suffices in that case). IA64 supports this via total ordering of all release instructions in theory and by the actual full-barrier implementation in practice (and the fact that gcc emits st.rel and ld.acq instructions for volatile stores and loads). All other architectures use smp_mb(), which is transitive.

Quoted 7 lines
Quoted 7 lines
Quoted 5 lines
Quoted 1 line

Did I miss anything?

I think that about covers it.. the only odd duckling might be s390 which is documented as TSO but recently grew smp_mb__{before,after}_atomic(), which seems to confuse matters.

Fair point, adding Martin and Heiko on CC for their thoughts.

Well we always had the full memory barrier for the various versions of smp_mb__xxx, they just have moved around and renamed several times.

After discussing this with Heiko we came to the conclusion that we can use a simple barrier() for smp_mb__before_atomic() and smp_mb__after_atomic().

Quoted 10 lines
Quoted 9 lines

It looks like this applies to recent mainframes that have new atomic instructions, which, yes, might need something to make them work with fully transitive smp_load_acquire() and smp_store_release().

Martin, Heiko, the question is whether or not the current s390 smp_store_release() and smp_load_acquire() can be transitive. For example, if all the Xi variables below are initially zero, is it possible for all the r0, r1, r2, ... rN variables to have the value 1 at the end of the test.

Quoted 24 lines

Right... This time actually adding Martin and Heiko on CC...

Thanx, Paul

Quoted 20 lines

CPU 0

	r0 = smp_load_acquire(&X0);
	smp_store_release(&X1, 1);

CPU 1

	r1 = smp_load_acquire(&X1);
	smp_store_release(&X2, 1);

CPU 2

	r2 = smp_load_acquire(&X2);
	smp_store_release(&X3, 1);

...

CPU N

	rN = smp_load_acquire(&XN);
	smp_store_release(&X0, 1);

If smp_store_release() and smp_load_acquire() are transitive, the answer would be "no".

Quoted 8 lines

The answer is "no". Christian recently summarized what the principles of operation has to say about the CPU read / write behavior. If you consider the sequential order of instructions then

1) reads are in order
2) writes are in order
3) reads can happen earlier
4) writes can happen later

Correction. The principles of operation states this:

"A storage-operand store specified by one instruction appears to precede all storage-operand stores specified by conceptually subsequent instructions, but it does not necessarily precede storage-operand fetches specified by conceptually subsequent instructions. However, a storage-operand store appears to precede a conceptually subsequent storage-operand fetch from the same main-storage location."

Quoted 9 lines

As observed by other CPUs a write to one memory location can "overtake" a read of another memory location if there is no explicit memory-barrier between the load and the store instruction.

In the above example X0, X1, ... XN are different memory locations, so architecturally the answer is "yes", all r0, r1, ... rN variables can have the value of 1 after the test. I doubt that any existing machine will show this behavior though.

Just be curious, how about when N == 1? The test then becomes:

CPU 0

	r0 = smp_load_acquire(&X0);
	smp_store_release(&X1,1);
Quoted 6 lines

CPU 1

	r1 = smp_load_acquire(&X1);
	smp_store_release(&X0,1);

Is it possible that r0 == 1 and r1 == 1 at the end, due to the same reason?

Yes, that is possible for the same reason. To change that we would have to replace the barrier() in smp_load_acquire/smp_store_release with smp_mb().

Signature · 4 lines
blue skies,
   Martin.

"Reality continues to ruin my life." - Calvin.
#18 lore raw

Re: [PATCH -tip 2/3] sched/wake_q: Relax to acquire semantics

Quoted 116 lines · Martin Schwidefsky
Quoted 113 lines · On Tue, 22 Sep 2015 20:23:26 +0800 Boqun Feng <[email protected]> wrote:

Hi Martin,

Quoted 110 lines · Martin Schwidefsky
Quoted 96 lines · On Mon, 21 Sep 2015 11:22:52 +0200 Martin Schwidefsky <[email protected]>…
Quoted 44 lines · On Fri, 18 Sep 2015 14:41:20 -0700 "Paul E. McKenney"…
Quoted 43 lines · Paul E. McKenney
Quoted 42 lines · Peter Zijlstra
Quoted 41 lines · Paul E. McKenney
Quoted 16 lines · Peter Zijlstra
Quoted 15 lines · Paul E. McKenney
Quoted 13 lines · Peter Zijlstra
Quoted 9 lines · Paul E. McKenney
Quoted 2 lines

Never mind, the PPC people will implement this with lwsync and that is
very much not transitive IIRC.

I am probably lost on context, but...

It turns out that lwsync is transitive in special cases. One of them is a series of release-acquire pairs, which can extend indefinitely.

Does that help in this case?

Probably not, but good to know. I still don't think we want to rely on ACQUIRE/RELEASE being transitive in general though.

Quoted 7 lines
Quoted 1 line

OK, I will bite... Why not?

It would mean us reviewing all archs (again) and documenting it I suppose. Which is of course entirely possible.

That said, I don't think the case at hand requires it, so lets postpone this for now ;-)

True enough, but in my experience smp_store_release() and smp_load_acquire() are a -lot- easier to use than other barriers, and transitivity will help promote their use. So...

All the TSO architectures (x86, s390, SPARC, HPPA, ...) support transitive smp_store_release()/smp_load_acquire() via their native ordering in combination with barrier() macros. x86 with CONFIG_X86_PPRO_FENCE=y, which is not TSO, uses an mfence instruction. Power supports this via lwsync's partial cumulativity. ARM64 supports it in SMP via the new ldar and stlr instructions (in non-SMP, it uses barrier(), which suffices in that case). IA64 supports this via total ordering of all release instructions in theory and by the actual full-barrier implementation in practice (and the fact that gcc emits st.rel and ld.acq instructions for volatile stores and loads). All other architectures use smp_mb(), which is transitive.

Quoted 7 lines
Quoted 7 lines
Quoted 5 lines
Quoted 1 line

Did I miss anything?

I think that about covers it.. the only odd duckling might be s390 which is documented as TSO but recently grew smp_mb__{before,after}_atomic(), which seems to confuse matters.

Fair point, adding Martin and Heiko on CC for their thoughts.

Well we always had the full memory barrier for the various versions of smp_mb__xxx, they just have moved around and renamed several times.

After discussing this with Heiko we came to the conclusion that we can use a simple barrier() for smp_mb__before_atomic() and smp_mb__after_atomic().

Quoted 10 lines
Quoted 9 lines

It looks like this applies to recent mainframes that have new atomic instructions, which, yes, might need something to make them work with fully transitive smp_load_acquire() and smp_store_release().

Martin, Heiko, the question is whether or not the current s390 smp_store_release() and smp_load_acquire() can be transitive. For example, if all the Xi variables below are initially zero, is it possible for all the r0, r1, r2, ... rN variables to have the value 1 at the end of the test.

Quoted 24 lines

Right... This time actually adding Martin and Heiko on CC...

Thanx, Paul

Quoted 20 lines

CPU 0

	r0 = smp_load_acquire(&X0);
	smp_store_release(&X1, 1);

CPU 1

	r1 = smp_load_acquire(&X1);
	smp_store_release(&X2, 1);

CPU 2

	r2 = smp_load_acquire(&X2);
	smp_store_release(&X3, 1);

...

CPU N

	rN = smp_load_acquire(&XN);
	smp_store_release(&X0, 1);

If smp_store_release() and smp_load_acquire() are transitive, the answer would be "no".

Quoted 8 lines

The answer is "no". Christian recently summarized what the principles of operation has to say about the CPU read / write behavior. If you consider the sequential order of instructions then

1) reads are in order
2) writes are in order
3) reads can happen earlier
4) writes can happen later

Correction. The principles of operation states this:

Quoted 7 lines
Quoted 7 lines
Quoted 7 lines

"A storage-operand store specified by one instruction appears to precede all storage-operand stores specified by conceptually subsequent instructions, but it does not necessarily precede storage-operand fetches specified by conceptually subsequent instructions. However, a storage-operand store appears to precede a conceptually subsequent storage-operand fetch from the same main-storage location."

Confused...

IIUC, the previous paragraph actually means that a STORE-LOAD pair can be reordered. But the below reasoning is saying that a LOAD-STORE pair can be reordered. Do I miss something here?

Quoted 20 lines
Quoted 20 lines
Quoted 9 lines

As observed by other CPUs a write to one memory location can "overtake" a read of another memory location if there is no explicit memory-barrier between the load and the store instruction.

In the above example X0, X1, ... XN are different memory locations, so architecturally the answer is "yes", all r0, r1, ... rN variables can have the value of 1 after the test. I doubt that any existing machine will show this behavior though.

Just be curious, how about when N == 1? The test then becomes:

CPU 0

	r0 = smp_load_acquire(&X0);
	smp_store_release(&X1,1);

CPU 1

	r1 = smp_load_acquire(&X1);
	smp_store_release(&X0,1);
Quoted 7 lines
Quoted 2 lines

Is it possible that r0 == 1 and r1 == 1 at the end, due to the same reason?

Yes, that is possible for the same reason. To change that we would have to replace the barrier() in smp_load_acquire/smp_store_release with smp_mb().

I thought that s390 is TSO, so this is prohibitted. If that is possible, I think, that means the current implementation of smp_load_acquire and smp_store_release on s390 is incorrect...

Regards,
Boqun

#19 lore raw

Re: [PATCH -tip 2/3] sched/wake_q: Relax to acquire semantics

Quoted 125 lines · On Tue, 22 Sep 2015 21:29:14 +0800 Boqun Feng <[email protected]> wrote:
Quoted 116 lines · Martin Schwidefsky
Quoted 113 lines · On Tue, 22 Sep 2015 20:23:26 +0800 Boqun Feng <[email protected]> wrote:

Hi Martin,

Quoted 110 lines · Martin Schwidefsky
Quoted 96 lines · On Mon, 21 Sep 2015 11:22:52 +0200 Martin Schwidefsky <[email protected]>…
Quoted 44 lines · On Fri, 18 Sep 2015 14:41:20 -0700 "Paul E. McKenney"…
Quoted 43 lines · Paul E. McKenney
Quoted 42 lines · Peter Zijlstra
Quoted 41 lines · Paul E. McKenney
Quoted 16 lines · Peter Zijlstra
Quoted 15 lines · Paul E. McKenney
Quoted 13 lines · Peter Zijlstra
Quoted 9 lines · Paul E. McKenney

Never mind, the PPC people will implement this with lwsync and that is
very much not transitive IIRC.

I am probably lost on context, but...

It turns out that lwsync is transitive in special cases. One of them
is a series of release-acquire pairs, which can extend indefinitely.

Does that help in this case?

Probably not, but good to know. I still don't think we want to rely on ACQUIRE/RELEASE being transitive in general though.

Quoted 7 lines
Quoted 1 line

OK, I will bite... Why not?

It would mean us reviewing all archs (again) and documenting it I suppose. Which is of course entirely possible.

That said, I don't think the case at hand requires it, so lets postpone this for now ;-)

True enough, but in my experience smp_store_release() and smp_load_acquire() are a -lot- easier to use than other barriers, and transitivity will help promote their use. So...

All the TSO architectures (x86, s390, SPARC, HPPA, ...) support transitive smp_store_release()/smp_load_acquire() via their native ordering in combination with barrier() macros. x86 with CONFIG_X86_PPRO_FENCE=y, which is not TSO, uses an mfence instruction. Power supports this via lwsync's partial cumulativity. ARM64 supports it in SMP via the new ldar and stlr instructions (in non-SMP, it uses barrier(), which suffices in that case). IA64 supports this via total ordering of all release instructions in theory and by the actual full-barrier implementation in practice (and the fact that gcc emits st.rel and ld.acq instructions for volatile stores and loads). All other architectures use smp_mb(), which is transitive.

Quoted 7 lines
Quoted 7 lines
Quoted 5 lines
Quoted 1 line

Did I miss anything?

I think that about covers it.. the only odd duckling might be s390 which is documented as TSO but recently grew smp_mb__{before,after}_atomic(), which seems to confuse matters.

Fair point, adding Martin and Heiko on CC for their thoughts.

Well we always had the full memory barrier for the various versions of smp_mb__xxx, they just have moved around and renamed several times.

After discussing this with Heiko we came to the conclusion that we can use a simple barrier() for smp_mb__before_atomic() and smp_mb__after_atomic().

Quoted 10 lines
Quoted 9 lines

It looks like this applies to recent mainframes that have new atomic instructions, which, yes, might need something to make them work with fully transitive smp_load_acquire() and smp_store_release().

Martin, Heiko, the question is whether or not the current s390 smp_store_release() and smp_load_acquire() can be transitive. For example, if all the Xi variables below are initially zero, is it possible for all the r0, r1, r2, ... rN variables to have the value 1 at the end of the test.

Quoted 24 lines

Right... This time actually adding Martin and Heiko on CC...

Thanx, Paul

Quoted 20 lines

CPU 0

	r0 = smp_load_acquire(&X0);
	smp_store_release(&X1, 1);

CPU 1

	r1 = smp_load_acquire(&X1);
	smp_store_release(&X2, 1);

CPU 2

	r2 = smp_load_acquire(&X2);
	smp_store_release(&X3, 1);

...

CPU N

	rN = smp_load_acquire(&XN);
	smp_store_release(&X0, 1);

If smp_store_release() and smp_load_acquire() are transitive, the answer would be "no".

Quoted 8 lines

The answer is "no". Christian recently summarized what the principles of operation has to say about the CPU read / write behavior. If you consider the sequential order of instructions then

1) reads are in order
2) writes are in order
3) reads can happen earlier
4) writes can happen later

Correction. The principles of operation states this:

Quoted 7 lines
Quoted 7 lines
Quoted 7 lines

"A storage-operand store specified by one instruction appears to precede all storage-operand stores specified by conceptually subsequent instructions, but it does not necessarily precede storage-operand fetches specified by conceptually subsequent instructions. However, a storage-operand store appears to precede a conceptually subsequent storage-operand fetch from the same main-storage location."

Quoted 1 line

Confused...

Yeah, seems like I'm confused as well. This stuff always make my head hurt..

Quoted 3 lines

IIUC, the previous paragraph actually means that a STORE-LOAD pair can be reordered. But the below reasoning is saying that a LOAD-STORE pair can be reordered. Do I miss something here?

True, the above paragraph allows a store to move past a load and not the other way around.

Quoted 23 lines
Quoted 23 lines
Quoted 22 lines
Quoted 9 lines

As observed by other CPUs a write to one memory location can "overtake" a read of another memory location if there is no explicit memory-barrier between the load and the store instruction.

In the above example X0, X1, ... XN are different memory locations, so architecturally the answer is "yes", all r0, r1, ... rN variables can have the value of 1 after the test. I doubt that any existing machine will show this behavior though.

Just be curious, how about when N == 1? The test then becomes:

CPU 0

	r0 = smp_load_acquire(&X0);
	smp_store_release(&X1,1);

CPU 1

	r1 = smp_load_acquire(&X1);
	smp_store_release(&X0,1);

Is it possible that r0 == 1 and r1 == 1 at the end, due to the same reason?

Quoted 8 lines
Quoted 4 lines

Yes, that is possible for the same reason. To change that we would have to replace the barrier() in smp_load_acquire/smp_store_release with smp_mb().

I thought that s390 is TSO, so this is prohibitted. If that is possible, I think, that means the current implementation of smp_load_acquire and smp_store_release on s390 is incorrect...

Ok, further reading of chapter 5 of the principles revealed this:

"As observed by other CPUs and by channel programs, storage-operand fetches associated with one instruction execution appear to precede all storage operand references for conceptually subsequent instructions."

So no writes before reads. Correction to the correction: all r0, r1, ...rN equal to one can not happen after all. Got me worried there ;-)

Signature · 4 lines
blue skies,
   Martin.

"Reality continues to ruin my life." - Calvin.
#20 lore raw

Re: [PATCH -tip 2/3] sched/wake_q: Relax to acquire semantics

Quoted 171 lines · Martin Schwidefsky
Quoted 125 lines · On Tue, 22 Sep 2015 21:29:14 +0800 Boqun Feng <[email protected]> wrote:
Quoted 116 lines · Martin Schwidefsky
Quoted 113 lines · On Tue, 22 Sep 2015 20:23:26 +0800 Boqun Feng <[email protected]> wrote:

Hi Martin,

Quoted 110 lines · Martin Schwidefsky
Quoted 96 lines · On Mon, 21 Sep 2015 11:22:52 +0200 Martin Schwidefsky <[email protected]>…
Quoted 44 lines · On Fri, 18 Sep 2015 14:41:20 -0700 "Paul E. McKenney"…
Quoted 43 lines · Paul E. McKenney
Quoted 42 lines · Peter Zijlstra
Quoted 41 lines · Paul E. McKenney
Quoted 16 lines · Peter Zijlstra
Quoted 15 lines · Paul E. McKenney
Quoted 13 lines · Peter Zijlstra

On Tue, Sep 15, 2015 at 05:41:42AM -0700, Paul E. McKenney wrote:
Never mind, the PPC people will implement this with lwsync and that is
very much not transitive IIRC.

I am probably lost on context, but...

It turns out that lwsync is transitive in special cases. One of them
is a series of release-acquire pairs, which can extend indefinitely.

Does that help in this case?

Probably not, but good to know. I still don't think we want to rely on
ACQUIRE/RELEASE being transitive in general though.

Quoted 7 lines
Quoted 1 line

OK, I will bite... Why not?

It would mean us reviewing all archs (again) and documenting it I suppose. Which is of course entirely possible.

That said, I don't think the case at hand requires it, so lets postpone this for now ;-)

True enough, but in my experience smp_store_release() and smp_load_acquire() are a -lot- easier to use than other barriers, and transitivity will help promote their use. So...

All the TSO architectures (x86, s390, SPARC, HPPA, ...) support transitive smp_store_release()/smp_load_acquire() via their native ordering in combination with barrier() macros. x86 with CONFIG_X86_PPRO_FENCE=y, which is not TSO, uses an mfence instruction. Power supports this via lwsync's partial cumulativity. ARM64 supports it in SMP via the new ldar and stlr instructions (in non-SMP, it uses barrier(), which suffices in that case). IA64 supports this via total ordering of all release instructions in theory and by the actual full-barrier implementation in practice (and the fact that gcc emits st.rel and ld.acq instructions for volatile stores and loads). All other architectures use smp_mb(), which is transitive.

Quoted 7 lines
Quoted 7 lines
Quoted 5 lines
Quoted 1 line

Did I miss anything?

I think that about covers it.. the only odd duckling might be s390 which is documented as TSO but recently grew smp_mb__{before,after}_atomic(), which seems to confuse matters.

Fair point, adding Martin and Heiko on CC for their thoughts.

Well we always had the full memory barrier for the various versions of smp_mb__xxx, they just have moved around and renamed several times.

After discussing this with Heiko we came to the conclusion that we can use a simple barrier() for smp_mb__before_atomic() and smp_mb__after_atomic().

Quoted 10 lines
Quoted 9 lines

It looks like this applies to recent mainframes that have new atomic instructions, which, yes, might need something to make them work with fully transitive smp_load_acquire() and smp_store_release().

Martin, Heiko, the question is whether or not the current s390 smp_store_release() and smp_load_acquire() can be transitive. For example, if all the Xi variables below are initially zero, is it possible for all the r0, r1, r2, ... rN variables to have the value 1 at the end of the test.

Quoted 24 lines

Right... This time actually adding Martin and Heiko on CC...

Thanx, Paul

Quoted 20 lines

CPU 0

	r0 = smp_load_acquire(&X0);
	smp_store_release(&X1, 1);

CPU 1

	r1 = smp_load_acquire(&X1);
	smp_store_release(&X2, 1);

CPU 2

	r2 = smp_load_acquire(&X2);
	smp_store_release(&X3, 1);

...

CPU N

	rN = smp_load_acquire(&XN);
	smp_store_release(&X0, 1);

If smp_store_release() and smp_load_acquire() are transitive, the answer would be "no".

Quoted 8 lines

The answer is "no". Christian recently summarized what the principles of operation has to say about the CPU read / write behavior. If you consider the sequential order of instructions then

1) reads are in order
2) writes are in order
3) reads can happen earlier
4) writes can happen later

Correction. The principles of operation states this:

Quoted 7 lines
Quoted 7 lines
Quoted 7 lines

"A storage-operand store specified by one instruction appears to precede all storage-operand stores specified by conceptually subsequent instructions, but it does not necessarily precede storage-operand fetches specified by conceptually subsequent instructions. However, a storage-operand store appears to precede a conceptually subsequent storage-operand fetch from the same main-storage location."

Quoted 1 line

Confused...

Yeah, seems like I'm confused as well. This stuff always make my head hurt..

Quoted 3 lines

IIUC, the previous paragraph actually means that a STORE-LOAD pair can be reordered. But the below reasoning is saying that a LOAD-STORE pair can be reordered. Do I miss something here?

True, the above paragraph allows a store to move past a load and not the other way around.

Quoted 23 lines
Quoted 23 lines
Quoted 22 lines
Quoted 9 lines

As observed by other CPUs a write to one memory location can "overtake" a read of another memory location if there is no explicit memory-barrier between the load and the store instruction.

In the above example X0, X1, ... XN are different memory locations, so architecturally the answer is "yes", all r0, r1, ... rN variables can have the value of 1 after the test. I doubt that any existing machine will show this behavior though.

Just be curious, how about when N == 1? The test then becomes:

CPU 0

	r0 = smp_load_acquire(&X0);
	smp_store_release(&X1,1);

CPU 1

	r1 = smp_load_acquire(&X1);
	smp_store_release(&X0,1);

Is it possible that r0 == 1 and r1 == 1 at the end, due to the same reason?

Quoted 8 lines
Quoted 4 lines

Yes, that is possible for the same reason. To change that we would have to replace the barrier() in smp_load_acquire/smp_store_release with smp_mb().

I thought that s390 is TSO, so this is prohibitted. If that is possible, I think, that means the current implementation of smp_load_acquire and smp_store_release on s390 is incorrect...

Quoted 8 lines

Ok, further reading of chapter 5 of the principles revealed this:

"As observed by other CPUs and by channel programs, storage-operand fetches associated with one instruction execution appear to precede all storage operand references for conceptually subsequent instructions."

So no writes before reads. Correction to the correction: all r0, r1, ...rN equal to one can not happen after all. Got me worried there ;-)

Whew!!!

So s390's current smp_store_release() and smp_load_acquire() provide ordering as needed, then, right? For example, suppose that there was a long chain of smp_load_acquire()/smp_store_release() pairs involving many CPUs. Would the all-ones case still be impossible?

Thanx, Paul

#21 lore raw

Re: [PATCH -tip 2/3] sched/wake_q: Relax to acquire semantics

Quoted 181 lines · On Tue, 22 Sep 2015 08:28:22 -0700 "Paul E. McKenney"…
Quoted 171 lines · Martin Schwidefsky
Quoted 125 lines · On Tue, 22 Sep 2015 21:29:14 +0800 Boqun Feng <[email protected]> wrote:
Quoted 116 lines · Martin Schwidefsky
Quoted 113 lines · On Tue, 22 Sep 2015 20:23:26 +0800 Boqun Feng <[email protected]> wrote:

Hi Martin,

Quoted 110 lines · Martin Schwidefsky
Quoted 96 lines · On Mon, 21 Sep 2015 11:22:52 +0200 Martin Schwidefsky <[email protected]>…
Quoted 44 lines · On Fri, 18 Sep 2015 14:41:20 -0700 "Paul E. McKenney"…
Quoted 43 lines · Paul E. McKenney
Quoted 42 lines · Peter Zijlstra
Quoted 41 lines · Paul E. McKenney
Quoted 16 lines · Peter Zijlstra
Quoted 15 lines · Paul E. McKenney

On Tue, Sep 15, 2015 at 02:48:00PM +0200, Peter Zijlstra wrote:
On Tue, Sep 15, 2015 at 05:41:42AM -0700, Paul E. McKenney wrote:
Never mind, the PPC people will implement this with lwsync and that is
very much not transitive IIRC.

I am probably lost on context, but...

It turns out that lwsync is transitive in special cases. One of them
is a series of release-acquire pairs, which can extend indefinitely.

Does that help in this case?

Probably not, but good to know. I still don't think we want to rely on
ACQUIRE/RELEASE being transitive in general though.

Quoted 7 lines
Quoted 1 line

OK, I will bite... Why not?

It would mean us reviewing all archs (again) and documenting it I suppose. Which is of course entirely possible.

That said, I don't think the case at hand requires it, so lets postpone this for now ;-)

True enough, but in my experience smp_store_release() and smp_load_acquire() are a -lot- easier to use than other barriers, and transitivity will help promote their use. So...

All the TSO architectures (x86, s390, SPARC, HPPA, ...) support transitive smp_store_release()/smp_load_acquire() via their native ordering in combination with barrier() macros. x86 with CONFIG_X86_PPRO_FENCE=y, which is not TSO, uses an mfence instruction. Power supports this via lwsync's partial cumulativity. ARM64 supports it in SMP via the new ldar and stlr instructions (in non-SMP, it uses barrier(), which suffices in that case). IA64 supports this via total ordering of all release instructions in theory and by the actual full-barrier implementation in practice (and the fact that gcc emits st.rel and ld.acq instructions for volatile stores and loads). All other architectures use smp_mb(), which is transitive.

Quoted 7 lines
Quoted 7 lines
Quoted 5 lines
Quoted 1 line

Did I miss anything?

I think that about covers it.. the only odd duckling might be s390 which is documented as TSO but recently grew smp_mb__{before,after}_atomic(), which seems to confuse matters.

Fair point, adding Martin and Heiko on CC for their thoughts.

Well we always had the full memory barrier for the various versions of smp_mb__xxx, they just have moved around and renamed several times.

After discussing this with Heiko we came to the conclusion that we can use a simple barrier() for smp_mb__before_atomic() and smp_mb__after_atomic().

Quoted 10 lines
Quoted 9 lines

It looks like this applies to recent mainframes that have new atomic instructions, which, yes, might need something to make them work with fully transitive smp_load_acquire() and smp_store_release().

Martin, Heiko, the question is whether or not the current s390 smp_store_release() and smp_load_acquire() can be transitive. For example, if all the Xi variables below are initially zero, is it possible for all the r0, r1, r2, ... rN variables to have the value 1 at the end of the test.

Quoted 24 lines

Right... This time actually adding Martin and Heiko on CC...

Thanx, Paul

Quoted 20 lines

CPU 0

	r0 = smp_load_acquire(&X0);
	smp_store_release(&X1, 1);

CPU 1

	r1 = smp_load_acquire(&X1);
	smp_store_release(&X2, 1);

CPU 2

	r2 = smp_load_acquire(&X2);
	smp_store_release(&X3, 1);

...

CPU N

	rN = smp_load_acquire(&XN);
	smp_store_release(&X0, 1);

If smp_store_release() and smp_load_acquire() are transitive, the answer would be "no".

Quoted 8 lines

The answer is "no". Christian recently summarized what the principles of operation has to say about the CPU read / write behavior. If you consider the sequential order of instructions then

1) reads are in order
2) writes are in order
3) reads can happen earlier
4) writes can happen later

Correction. The principles of operation states this:

Quoted 7 lines
Quoted 7 lines
Quoted 7 lines

"A storage-operand store specified by one instruction appears to precede all storage-operand stores specified by conceptually subsequent instructions, but it does not necessarily precede storage-operand fetches specified by conceptually subsequent instructions. However, a storage-operand store appears to precede a conceptually subsequent storage-operand fetch from the same main-storage location."

Quoted 1 line

Confused...

Yeah, seems like I'm confused as well. This stuff always make my head hurt..

Quoted 3 lines

IIUC, the previous paragraph actually means that a STORE-LOAD pair can be reordered. But the below reasoning is saying that a LOAD-STORE pair can be reordered. Do I miss something here?

True, the above paragraph allows a store to move past a load and not the other way around.

Quoted 23 lines
Quoted 23 lines
Quoted 22 lines
Quoted 9 lines

As observed by other CPUs a write to one memory location can "overtake" a read of another memory location if there is no explicit memory-barrier between the load and the store instruction.

In the above example X0, X1, ... XN are different memory locations, so architecturally the answer is "yes", all r0, r1, ... rN variables can have the value of 1 after the test. I doubt that any existing machine will show this behavior though.

Just be curious, how about when N == 1? The test then becomes:

CPU 0

	r0 = smp_load_acquire(&X0);
	smp_store_release(&X1,1);

CPU 1

	r1 = smp_load_acquire(&X1);
	smp_store_release(&X0,1);

Is it possible that r0 == 1 and r1 == 1 at the end, due to the same reason?

Quoted 8 lines
Quoted 4 lines

Yes, that is possible for the same reason. To change that we would have to replace the barrier() in smp_load_acquire/smp_store_release with smp_mb().

I thought that s390 is TSO, so this is prohibitted. If that is possible, I think, that means the current implementation of smp_load_acquire and smp_store_release on s390 is incorrect...

Quoted 8 lines

Ok, further reading of chapter 5 of the principles revealed this:

"As observed by other CPUs and by channel programs, storage-operand fetches associated with one instruction execution appear to precede all storage operand references for conceptually subsequent instructions."

So no writes before reads. Correction to the correction: all r0, r1, ...rN equal to one can not happen after all. Got me worried there ;-)

Quoted 6 lines

Whew!!!

So s390's current smp_store_release() and smp_load_acquire() provide ordering as needed, then, right? For example, suppose that there was a long chain of smp_load_acquire()/smp_store_release() pairs involving many CPUs. Would the all-ones case still be impossible?

Yes, that is impossible.

Signature · 4 lines
blue skies,
   Martin.

"Reality continues to ruin my life." - Calvin.
#22 lore raw

Re: [PATCH -tip 2/3] sched/wake_q: Relax to acquire semantics

Quoted 184 lines · Martin Schwidefsky
Quoted 181 lines · On Tue, 22 Sep 2015 08:28:22 -0700 "Paul E. McKenney"…
Quoted 179 lines · Martin Schwidefsky
Quoted 125 lines · On Tue, 22 Sep 2015 21:29:14 +0800 Boqun Feng <[email protected]> wrote:
Quoted 116 lines · Martin Schwidefsky
Quoted 113 lines · On Tue, 22 Sep 2015 20:23:26 +0800 Boqun Feng <[email protected]> wrote:

Hi Martin,

Quoted 110 lines · Martin Schwidefsky
Quoted 96 lines · On Mon, 21 Sep 2015 11:22:52 +0200 Martin Schwidefsky <[email protected]>…
Quoted 44 lines · On Fri, 18 Sep 2015 14:41:20 -0700 "Paul E. McKenney"…
Quoted 43 lines · Paul E. McKenney
Quoted 42 lines · Peter Zijlstra
Quoted 41 lines · Paul E. McKenney
Quoted 23 lines · Peter Zijlstra

On Tue, Sep 15, 2015 at 07:09:22AM -0700, Paul E. McKenney wrote:
On Tue, Sep 15, 2015 at 02:48:00PM +0200, Peter Zijlstra wrote:
On Tue, Sep 15, 2015 at 05:41:42AM -0700, Paul E. McKenney wrote:
Never mind, the PPC people will implement this with lwsync and that is
very much not transitive IIRC.

I am probably lost on context, but...

It turns out that lwsync is transitive in special cases. One of them
is a series of release-acquire pairs, which can extend indefinitely.

Does that help in this case?

Probably not, but good to know. I still don't think we want to rely on
ACQUIRE/RELEASE being transitive in general though.

OK, I will bite... Why not?

It would mean us reviewing all archs (again) and documenting it I
suppose. Which is of course entirely possible.

That said, I don't think the case at hand requires it, so lets postpone
this for now ;-)

True enough, but in my experience smp_store_release() and smp_load_acquire() are a -lot- easier to use than other barriers, and transitivity will help promote their use. So...

All the TSO architectures (x86, s390, SPARC, HPPA, ...) support transitive smp_store_release()/smp_load_acquire() via their native ordering in combination with barrier() macros. x86 with CONFIG_X86_PPRO_FENCE=y, which is not TSO, uses an mfence instruction. Power supports this via lwsync's partial cumulativity. ARM64 supports it in SMP via the new ldar and stlr instructions (in non-SMP, it uses barrier(), which suffices in that case). IA64 supports this via total ordering of all release instructions in theory and by the actual full-barrier implementation in practice (and the fact that gcc emits st.rel and ld.acq instructions for volatile stores and loads). All other architectures use smp_mb(), which is transitive.

Quoted 7 lines
Quoted 7 lines
Quoted 5 lines
Quoted 1 line

Did I miss anything?

I think that about covers it.. the only odd duckling might be s390 which is documented as TSO but recently grew smp_mb__{before,after}_atomic(), which seems to confuse matters.

Fair point, adding Martin and Heiko on CC for their thoughts.

Well we always had the full memory barrier for the various versions of smp_mb__xxx, they just have moved around and renamed several times.

After discussing this with Heiko we came to the conclusion that we can use a simple barrier() for smp_mb__before_atomic() and smp_mb__after_atomic().

Quoted 10 lines
Quoted 9 lines

It looks like this applies to recent mainframes that have new atomic instructions, which, yes, might need something to make them work with fully transitive smp_load_acquire() and smp_store_release().

Martin, Heiko, the question is whether or not the current s390 smp_store_release() and smp_load_acquire() can be transitive. For example, if all the Xi variables below are initially zero, is it possible for all the r0, r1, r2, ... rN variables to have the value 1 at the end of the test.

Quoted 24 lines

Right... This time actually adding Martin and Heiko on CC...

Thanx, Paul

Quoted 20 lines

CPU 0

	r0 = smp_load_acquire(&X0);
	smp_store_release(&X1, 1);

CPU 1

	r1 = smp_load_acquire(&X1);
	smp_store_release(&X2, 1);

CPU 2

	r2 = smp_load_acquire(&X2);
	smp_store_release(&X3, 1);

...

CPU N

	rN = smp_load_acquire(&XN);
	smp_store_release(&X0, 1);

If smp_store_release() and smp_load_acquire() are transitive, the answer would be "no".

Quoted 8 lines

The answer is "no". Christian recently summarized what the principles of operation has to say about the CPU read / write behavior. If you consider the sequential order of instructions then

1) reads are in order
2) writes are in order
3) reads can happen earlier
4) writes can happen later

Correction. The principles of operation states this:

Quoted 7 lines
Quoted 7 lines
Quoted 7 lines

"A storage-operand store specified by one instruction appears to precede all storage-operand stores specified by conceptually subsequent instructions, but it does not necessarily precede storage-operand fetches specified by conceptually subsequent instructions. However, a storage-operand store appears to precede a conceptually subsequent storage-operand fetch from the same main-storage location."

Quoted 1 line

Confused...

Yeah, seems like I'm confused as well. This stuff always make my head hurt..

Quoted 3 lines

IIUC, the previous paragraph actually means that a STORE-LOAD pair can be reordered. But the below reasoning is saying that a LOAD-STORE pair can be reordered. Do I miss something here?

True, the above paragraph allows a store to move past a load and not the other way around.

Quoted 23 lines
Quoted 23 lines
Quoted 22 lines
Quoted 9 lines

As observed by other CPUs a write to one memory location can "overtake" a read of another memory location if there is no explicit memory-barrier between the load and the store instruction.

In the above example X0, X1, ... XN are different memory locations, so architecturally the answer is "yes", all r0, r1, ... rN variables can have the value of 1 after the test. I doubt that any existing machine will show this behavior though.

Just be curious, how about when N == 1? The test then becomes:

CPU 0

	r0 = smp_load_acquire(&X0);
	smp_store_release(&X1,1);

CPU 1

	r1 = smp_load_acquire(&X1);
	smp_store_release(&X0,1);

Is it possible that r0 == 1 and r1 == 1 at the end, due to the same reason?

Quoted 8 lines
Quoted 4 lines

Yes, that is possible for the same reason. To change that we would have to replace the barrier() in smp_load_acquire/smp_store_release with smp_mb().

I thought that s390 is TSO, so this is prohibitted. If that is possible, I think, that means the current implementation of smp_load_acquire and smp_store_release on s390 is incorrect...

Ok, further reading of chapter 5 of the principles revealed this:

"As observed by other CPUs and by channel programs, storage-operand fetches associated with one instruction execution appear to precede all storage operand references for conceptually subsequent instructions."

So no writes before reads. Correction to the correction: all r0, r1, ...rN equal to one can not happen after all. Got me worried there ;-)

Quoted 8 lines
Quoted 6 lines

Whew!!!

So s390's current smp_store_release() and smp_load_acquire() provide ordering as needed, then, right? For example, suppose that there was a long chain of smp_load_acquire()/smp_store_release() pairs involving many CPUs. Would the all-ones case still be impossible?

Yes, that is impossible.

Very good! Release-acquire chains can be transitive, then. ;-)

Thanx, Paul

#23 lore raw

Re: [PATCH -tip 2/3] sched/wake_q: Relax to acquire semantics

In reply to Peter Zijlstra
Quoted 7 lines · Peter Zijlstra
Quoted 4 lines

Secondly, the wake queues are not concurrent, they're in context, so I don't see ordering matter at all. The only reason its a cmpxchg() is because there is the (small) possibility of two contexts wanting to wake the same task, and we use task_struct storage for the queue.

I don't think we need _any_ barriers here, unless we have concurrent users of the wake queues (or want to allow any, do we?).

Exactly, the queues are not concurent and do not need barriers, but some of our callers do expect them.

maintainer
#24 lore raw

Re: [PATCH -tip 2/3] sched/wake_q: Relax to acquire semantics

Quoted 7 lines · Davidlohr Bueso
Quoted 5 lines · Peter Zijlstra
Quoted 4 lines

Secondly, the wake queues are not concurrent, they're in context, so I don't see ordering matter at all. The only reason its a cmpxchg() is because there is the (small) possibility of two contexts wanting to wake the same task, and we use task_struct storage for the queue.

Quoted 5 lines
Quoted 2 lines

I don't think we need _any_ barriers here, unless we have concurrent users of the wake queues (or want to allow any, do we?).

Exactly, the queues are not concurent and do not need barriers, but some of our callers do expect them.

Ah, that is what you were saying. In that case, I think we should remove all our barriers and make them explicit in the callers where needed.

#25 lore raw

PATCH 3/3 locking/osq: Relax atomic semantics

In reply to Davidlohr Bueso

... by using acquire/release for ops around the lock->tail. As such, weakly ordered archs can benefit from more relaxed use of barriers when issuing atomics.

---
 kernel/locking/osq_lock.c | 11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)
kernel/locking/osq_lock.c +8 -3
index dc85ee2..d092a0c 100644
@@ -50,7 +50,7 @@ osq_wait_next(struct optimistic_spin_queue *lock,
 
 	for (;;) {
 		if (atomic_read(&lock->tail) == curr &&
-		    atomic_cmpxchg(&lock->tail, curr, old) == curr) {
+		    atomic_cmpxchg_acquire(&lock->tail, curr, old) == curr) {
 			/*
 			 * We were the last queued, we moved @lock back. @prev
 			 * will now observe @lock and will complete its
@@ -92,7 +92,11 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 	node->next = NULL;
 	node->cpu = curr;
 
-	old = atomic_xchg(&lock->tail, curr);
+	/*
+	 * ACQUIRE semantics, pairs with corresponding RELEASE
+	 * in unlock() uncontended, or fastpath.
+	 */
+	old = atomic_xchg_acquire(&lock->tail, curr);
 	if (old == OSQ_UNLOCKED_VAL)
 		return true;
 
@@ -184,7 +188,8 @@ void osq_unlock(struct optimistic_spin_queue *lock)
 	/*
 	 * Fast path for the uncontended case.
 	 */
-	if (likely(atomic_cmpxchg(&lock->tail, curr, OSQ_UNLOCKED_VAL) == curr))
+	if (likely(atomic_cmpxchg_release(&lock->tail, curr,
+					  OSQ_UNLOCKED_VAL) == curr))
 		return;
 
 	/*
Signature · 1 line
2.1.4
#26 lore raw

[tip:locking/core] locking/osq: Relax atomic semantics

locking/osq: Relax atomic semantics
Commit-ID:  c55a6ffa6285e29f874ed403979472631ec70bff
Gitweb:     http://git.kernel.org/tip/c55a6ffa6285e29f874ed403979472631ec70bff
Author:     Davidlohr Bueso <[email protected]>
AuthorDate: Mon, 14 Sep 2015 00:37:24 -0700
Committer:  Ingo Molnar <[email protected]>
CommitDate: Fri, 18 Sep 2015 09:27:29 +0200

locking/osq: Relax atomic semantics

... by using acquire/release for ops around the lock->tail. As such, weakly ordered archs can benefit from more relaxed use of barriers when issuing atomics.

---
 kernel/locking/osq_lock.c | 11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)
kernel/locking/osq_lock.c +8 -3
index dc85ee2..d092a0c 100644
@@ -50,7 +50,7 @@ osq_wait_next(struct optimistic_spin_queue *lock,
 
 	for (;;) {
 		if (atomic_read(&lock->tail) == curr &&
-		    atomic_cmpxchg(&lock->tail, curr, old) == curr) {
+		    atomic_cmpxchg_acquire(&lock->tail, curr, old) == curr) {
 			/*
 			 * We were the last queued, we moved @lock back. @prev
 			 * will now observe @lock and will complete its
@@ -92,7 +92,11 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 	node->next = NULL;
 	node->cpu = curr;
 
-	old = atomic_xchg(&lock->tail, curr);
+	/*
+	 * ACQUIRE semantics, pairs with corresponding RELEASE
+	 * in unlock() uncontended, or fastpath.
+	 */
+	old = atomic_xchg_acquire(&lock->tail, curr);
 	if (old == OSQ_UNLOCKED_VAL)
 		return true;
 
@@ -184,7 +188,8 @@ void osq_unlock(struct optimistic_spin_queue *lock)
 	/*
 	 * Fast path for the uncontended case.
 	 */
-	if (likely(atomic_cmpxchg(&lock->tail, curr, OSQ_UNLOCKED_VAL) == curr))
+	if (likely(atomic_cmpxchg_release(&lock->tail, curr,
+					  OSQ_UNLOCKED_VAL) == curr))
 		return;
 
 	/*
#27 lore raw
In reply to Davidlohr Bueso
locking/qrwlock: Rename ->lock to ->wait_lock
Commit-ID:  6e1e5196975fb7ecc501b3fe1075b77aea2b7839
Gitweb:     http://git.kernel.org/tip/6e1e5196975fb7ecc501b3fe1075b77aea2b7839
Author:     Davidlohr Bueso <[email protected]>
AuthorDate: Mon, 14 Sep 2015 00:37:22 -0700
Committer:  Ingo Molnar <[email protected]>
CommitDate: Fri, 18 Sep 2015 09:27:29 +0200

locking/qrwlock: Rename ->lock to ->wait_lock

... trivial, but reads a little nicer when we name our actual primitive 'lock'.

---
 include/asm-generic/qrwlock_types.h | 4 ++--
 kernel/locking/qrwlock.c            | 8 ++++----
 2 files changed, 6 insertions(+), 6 deletions(-)
include/asm-generic/qrwlock_types.h +2 -2
index 4d76f24..0abc6b6 100644
@@ -10,12 +10,12 @@
 
 typedef struct qrwlock {
 	atomic_t		cnts;
-	arch_spinlock_t		lock;
+	arch_spinlock_t		wait_lock;
 } arch_rwlock_t;
 
 #define	__ARCH_RW_LOCK_UNLOCKED {		\
 	.cnts = ATOMIC_INIT(0),			\
-	.lock = __ARCH_SPIN_LOCK_UNLOCKED,	\
+	.wait_lock = __ARCH_SPIN_LOCK_UNLOCKED,	\
 }
 
 #endif /* __ASM_GENERIC_QRWLOCK_TYPES_H */
kernel/locking/qrwlock.c +4 -4
index f17a3e3..fec0823 100644
@@ -86,7 +86,7 @@ void queued_read_lock_slowpath(struct qrwlock *lock, u32 cnts)
 	/*
 	 * Put the reader into the wait queue
 	 */
-	arch_spin_lock(&lock->lock);
+	arch_spin_lock(&lock->wait_lock);
 
 	/*
 	 * The ACQUIRE semantics of the following spinning code ensure
@@ -99,7 +99,7 @@ void queued_read_lock_slowpath(struct qrwlock *lock, u32 cnts)
 	/*
 	 * Signal the next one in queue to become queue head
 	 */
-	arch_spin_unlock(&lock->lock);
+	arch_spin_unlock(&lock->wait_lock);
 }
 EXPORT_SYMBOL(queued_read_lock_slowpath);
 
@@ -112,7 +112,7 @@ void queued_write_lock_slowpath(struct qrwlock *lock)
 	u32 cnts;
 
 	/* Put the writer into the wait queue */
-	arch_spin_lock(&lock->lock);
+	arch_spin_lock(&lock->wait_lock);
 
 	/* Try to acquire the lock directly if no reader is present */
 	if (!atomic_read(&lock->cnts) &&
@@ -144,6 +144,6 @@ void queued_write_lock_slowpath(struct qrwlock *lock)
 		cpu_relax_lowlatency();
 	}
 unlock:
-	arch_spin_unlock(&lock->lock);
+	arch_spin_unlock(&lock->wait_lock);
 }
 EXPORT_SYMBOL(queued_write_lock_slowpath);