Skip to contentSkip to conversation

futex atomic vs ordering constraints

DISCUSSION Peter Zijlstra 6 participants 15 messages Aug 26, 2015 – Sep 7, 2015

Subsystems (5)
lore
Share & tools
lore

Peter Zijlstra

author reviewer
#0 lore raw

Hi all,

I tried to keep this email short, but failed miserably at this. For the TL;DR skip to the tail.

So the question of ordering constraints of futex atomic operations has come up recently:

http://marc.info/?l=linux-kernel&m=143894765931868

This email will attempt to describe the two primitives and start a discussion on the constraints.

* futex_atomic_op_inuser()

There is but a single callsite of this function: futex_wake_op().

It being part of a wake primitive seems to suggest a (RCsc) RELEASE is the strongest required (the RCsc part because I don't think we want to expose RCpc to userspace if we don't have to).

The immediate scenario where this is important is:

        CPU0            CPU1            CPU2

        futex_lock(); -> uncontended user acquire
        A = 1;
                        futex_lock(); -> kernel, set pending, sleep
        B = 1;
        futex_unlock();
          if pending
            <kernel>
              futex_wake_op
                spin_lock(bh->lock)
                RELEASE
                futex_atomic_op_inuser(); -> futex unlocked
                                        futex_lock() -> uncontended user steal
                                        load A;

In other words, the moment we perform the WAKE_OP userspace can observe the 'lock' as unlocked and do a lock (steal) acquire of the 'lock'.

If userspace succeeds with this acquire, we need full serialization of the locked (RCsc) variables (eg A and B in the above).

Of course, if anything else prior to futex_atomic_op_inuser() implies an (RCsc) RELEASE or stronger the primitive can do without providing anything itself.

This turns out to be the case, a successful get_futex_key() implies a full memory barrier; recent: 1d0dcb3ad9d3 ("futex: Implement lockless wakeups").

And since get_futex_key() is fundamental to doing _anything_ with a futex, I think its semi-sane to rely on this.

So we have two valid options:

- RCsc RELEASE
- no ordering at all

Current implementation:

alpha: MB ll/sc RELEASE
arm64: ll/sc-release MB FULL
arm: MB ll/sc RELEASE
mips: ll/sc MB ACQUIRE
powerpc: lwsync ll/sc sync FULL

* futex_atomic_cmpxchg_inatomic()

This is called from:

lock_pi_update_atomic
wake_futex_pi
fixup_pi_state_owner
futex_unlock_pi
handle_futex_death

But I think we can form a position from just two of them:

futex_unlock_pi() and lock_pi_update_atomic()

these end up being ACQUIRE and RELEASE, and a combination of these two would give us a requirement for full serialization.

And unlike the previous we cannot talk this one away. Even though every futex op needs a get_futex_key() which implies a full memory barrier, and every get_futex_key() needs a put_futex_key(), the latter does _NOT_ imply a full barrier.

So while we could relax the RELEASE semantics we cannot relax the ACQUIRE semantics.

Then there is handle_futex_death(), which is difficult, I _think_ it wants to be a RELEASE, but state is corrupted anyhow and I can well imagine not wanting to play any games here and go fully serialized like we're used to with cmpxchg.

Now the robust stuff doesn't use {get,put}_futex_key() stuff, so no implied barriers here.

Which leaves us all with a great big mess.

Current implementation:

alpha: MB ll/sc RELEASE
arm64: ll/sc-release MB FULL
arm: MB ll/sc MB FULL
mips: ll/sc MB ACQUIRE
powerpc: lwsync ll/sc sync FULL

There are a few options:

1) punt, mandate they're both fully ordered and stop thinking about it

2) make them both fully relaxed, rely on implied barriers and employ smp_mb__{before,after}_atomic in key places

Given the current state of things and that I don't really think there is a compelling performance argument to be made for 2, I would suggest we go with 1.

#1 lore raw
Quoted 7 lines · Peter Zijlstra

Of course, if anything else prior to futex_atomic_op_inuser() implies an (RCsc) RELEASE or stronger the primitive can do without providing anything itself.

This turns out to be the case, a successful get_futex_key() implies a full memory barrier; recent: 1d0dcb3ad9d3 ("futex: Implement lockless wakeups").

Hmm while it is certainly true that get_futex_key() implies a full barrier, I don't see why you're referring to the recent wake_q stuff; where the futex "wakeup" is done much after futex_atomic_op_inuser. Yes, that too implies a barrier, but not wrt get_futex_key() -- which fundamentally relies on get_futex_key_refs().

Quoted 3 lines

And since get_futex_key() is fundamental to doing _anything_ with a futex, I think its semi-sane to rely on this.

Right, and it wouldn't be the first thing that relies on get_futex_key() implying a full barrier.

author reviewer
#2 lore raw
Quoted 11 lines · Davidlohr Bueso
Quoted 7 lines · Peter Zijlstra

Of course, if anything else prior to futex_atomic_op_inuser() implies an (RCsc) RELEASE or stronger the primitive can do without providing anything itself.

This turns out to be the case, a successful get_futex_key() implies a full memory barrier; recent: 1d0dcb3ad9d3 ("futex: Implement lockless wakeups").

Hmm while it is certainly true that get_futex_key() implies a full barrier, I don't see why you're referring to the recent wake_q stuff;

D'oh, because I'm a sheep or so. I meant:

b0c29f79ecea (futexes: Avoid taking the hb->lock if there's nothing to wake up)

#3 lore raw
In reply to Peter Zijlstra

Hi Peter,

Quoted 2 lines · Peter Zijlstra

I tried to keep this email short, but failed miserably at this. For the TL;DR skip to the tail.

[...]

Quoted 10 lines

There are a few options:

1) punt, mandate they're both fully ordered and stop thinking about it

2) make them both fully relaxed, rely on implied barriers and employ smp_mb__{before,after}_atomic in key places

Given the current state of things and that I don't really think there is a compelling performance argument to be made for 2, I would suggest we go with 1.

I'd also go for (1). Since there is a userspace side to this, I'd *really* like to avoid a potential situation on arm64 where the kernel builds its side of the futex using barrier instructions (e.g. treat LDR + smp_mb() as acquire) and userspace builds its side out of native acquire/release instructions and the two end up interacting badly (for example, loss of SC).

Will

author reviewer
#4 lore raw
Quoted 19 lines · Will Deacon

Hi Peter,

Quoted 2 lines · Peter Zijlstra

I tried to keep this email short, but failed miserably at this. For the TL;DR skip to the tail.

[...]

Quoted 10 lines

There are a few options:

1) punt, mandate they're both fully ordered and stop thinking about it

2) make them both fully relaxed, rely on implied barriers and employ smp_mb__{before,after}_atomic in key places

Given the current state of things and that I don't really think there is a compelling performance argument to be made for 2, I would suggest we go with 1.

Quoted 6 lines

I'd also go for (1). Since there is a userspace side to this, I'd *really* like to avoid a potential situation on arm64 where the kernel builds its side of the futex using barrier instructions (e.g. treat LDR + smp_mb() as acquire) and userspace builds its side out of native acquire/release instructions and the two end up interacting badly (for example, loss of SC).

I thought your native acquire/release were RCsc, or is it that in combination with the 'fancy' 'full' barrier of stlxr + dmb-ish something goes sideways?

But yes, unless Thomas has other plans, I'll go ahead and create some patches to make sure everybody is fully ordered so we can forget about it again.

#5 lore raw
Quoted 25 lines · Peter Zijlstra
Quoted 17 lines · Will Deacon
Quoted 2 lines · Peter Zijlstra

I tried to keep this email short, but failed miserably at this. For the TL;DR skip to the tail.

[...]

Quoted 10 lines

There are a few options:

1) punt, mandate they're both fully ordered and stop thinking about it

2) make them both fully relaxed, rely on implied barriers and employ smp_mb__{before,after}_atomic in key places

Given the current state of things and that I don't really think there is a compelling performance argument to be made for 2, I would suggest we go with 1.

Quoted 6 lines

I'd also go for (1). Since there is a userspace side to this, I'd *really* like to avoid a potential situation on arm64 where the kernel builds its side of the futex using barrier instructions (e.g. treat LDR + smp_mb() as acquire) and userspace builds its side out of native acquire/release instructions and the two end up interacting badly (for example, loss of SC).

Quoted 3 lines

I thought your native acquire/release were RCsc, or is it that in combination with the 'fancy' 'full' barrier of stlxr + dmb-ish something goes sideways?

Yeah, they don't interact nicely because you can lose the multi-copy atomicity guarantees you get from using either native acquire/release everywhere or explicit barriers everywhere. IRIW shows the failure if you use {DMB; STR} for the writers and LDAR for the readers.

Quoted 3 lines

But yes, unless Thomas has other plans, I'll go ahead and create some patches to make sure everybody is fully ordered so we can forget about it again.

Sounds good to me!

Will

#6 lore raw
In reply to Peter Zijlstra
Quoted 27 lines · Peter Zijlstra
Quoted 19 lines · Will Deacon

Hi Peter,

Quoted 2 lines · Peter Zijlstra

I tried to keep this email short, but failed miserably at this. For the TL;DR skip to the tail.

[...]

Quoted 10 lines

There are a few options:

1) punt, mandate they're both fully ordered and stop thinking about it

2) make them both fully relaxed, rely on implied barriers and employ smp_mb__{before,after}_atomic in key places

Given the current state of things and that I don't really think there is a compelling performance argument to be made for 2, I would suggest we go with 1.

Quoted 6 lines

I'd also go for (1). Since there is a userspace side to this, I'd *really* like to avoid a potential situation on arm64 where the kernel builds its side of the futex using barrier instructions (e.g. treat LDR + smp_mb() as acquire) and userspace builds its side out of native acquire/release instructions and the two end up interacting badly (for example, loss of SC).

Quoted 7 lines

I thought your native acquire/release were RCsc, or is it that in combination with the 'fancy' 'full' barrier of stlxr + dmb-ish something goes sideways?

But yes, unless Thomas has other plans, I'll go ahead and create some patches to make sure everybody is fully ordered so we can forget about it again.

No, I don't. There are too many ways to screw that up, so unless someone has a serious performance issue, we should keep it on the safe side.

Thanks,

tglx

author reviewer
#7 lore raw

So here goes..

Chris, I'm awfully sorry, but I seem to be Tile challenged.

TileGX seems to define:

#define smp_mb__before_atomic() smp_mb()
#define smp_mb__after_atomic() smp_mb()

However, its atomic_add_return() implementation looks like:

static inline int atomic_add_return(int i, atomic_t *v)

{
	int val;
	smp_mb();  /* barrier for proper semantics */
	val = __insn_fetchadd4((void *)&v->counter, i) + i;
	barrier();  /* the "+ i" above will wait on memory */
	return val;
}

Which leaves me confused on smp_mb__after_atomic().

That said, your futex ops seem to lack any memory barrier, so naively I'd add both, its just that your add_return() confuses me.

---
Subject: futex, arch: Make futex atomic ops fully ordered

There was no clear ordering requirement for the two futex atomic primitives which led to various archs implementing different things.

Since there currently is no clear performance argument (its the syscall 'slow' path) favour mandating full order over complexity seems the right call.

This patch adds the new ordering requirements to the function comments (which it places in a more visible location) and updates all arches that were not already fully ordered (I checked those that have smp_mb__{before,after}_atomic() definitions, as those are the only ones that can actually be more relaxed).

In particular:

futex_atomic_op_inuser():

alpha:   MB ll/sc   (RELEASE) -> MB ll/sc MB
arm:     MB ll/sc   (RELEASE) -> MB ll/sc MB
mips:    ll/sc MB   (ACQUIRE) -> MB ll/sc MB

futex_atomic_cmpxchg_inatomic():

alpha:   MB ll/sc   (RELEASE) -> MB ll/sc MB
mips:    ll/sc MB   (ACQUIRE) -> MB ll/sc MB

XXX tile (again).

Cc Ralf Baechle <[email protected]>
Cc Russell King <[email protected]>
Cc Richard Henderson <[email protected]>
---
 arch/alpha/include/asm/futex.h | 10 +++++++---
 arch/arm/include/asm/futex.h   |  3 ++-
 arch/mips/include/asm/futex.h  |  4 ++++
 include/asm-generic/futex.h    | 26 +-------------------------
 include/linux/futex.h          | 35 +++++++++++++++++++++++++++++++++++
 5 files changed, 49 insertions(+), 29 deletions(-)
arch/alpha/include/asm/futex.h +7 -3
index f939794363ac..e0d5edad2cd4 100644
@@ -9,8 +9,8 @@
 #include <asm/barrier.h>
 
 #define __futex_atomic_op(insn, ret, oldval, uaddr, oparg)	\
+	smp_mb();						\
 	__asm__ __volatile__(					\
-		__ASM_SMP_MB					\
 	"1:	ldl_l	%0,0(%2)\n"				\
 		insn						\
 	"2:	stl_c	%1,0(%2)\n"				\
@@ -27,7 +27,8 @@
 	"	.previous\n"					\
 	:	"=&r" (oldval), "=&r"(ret)			\
 	:	"r" (uaddr), "r"(oparg)				\
-	:	"memory")
+	:	"memory");					\
+	smp_mb()
 
 static inline int futex_atomic_op_inuser (int encoded_op, u32 __user *uaddr)
 {
@@ -90,8 +91,9 @@ futex_atomic_cmpxchg_inatomic(u32 *uval, u32 __user *uaddr,
 	if (!access_ok(VERIFY_WRITE, uaddr, sizeof(u32)))
 		return -EFAULT;
 
+	smp_mb();
+
 	__asm__ __volatile__ (
-		__ASM_SMP_MB
 	"1:	ldl_l	%1,0(%3)\n"
 	"	cmpeq	%1,%4,%2\n"
 	"	beq	%2,3f\n"
@@ -111,6 +113,8 @@ futex_atomic_cmpxchg_inatomic(u32 *uval, u32 __user *uaddr,
 	:	"r"(uaddr), "r"((long)(int)oldval), "r"(newval)
 	:	"memory");
 
+	smp_mb();
+
 	*uval = prev;
 	return ret;
 }
arch/arm/include/asm/futex.h +2 -1
index 5eed82809d82..1be3be8eb8c2 100644
@@ -34,7 +34,8 @@
 	__futex_atomic_ex_table("%5")				\
 	: "=&r" (ret), "=&r" (oldval), "=&r" (tmp)		\
 	: "r" (uaddr), "r" (oparg), "Ir" (-EFAULT)		\
-	: "cc", "memory")
+	: "cc", "memory");					\
+	smp_mb()
 
 static inline int
 futex_atomic_cmpxchg_inatomic(u32 *uval, u32 __user *uaddr,
arch/mips/include/asm/futex.h +4 -0
index 1de190bdfb9c..2f38cc84fb04 100644
@@ -20,6 +20,8 @@
 
 #define __futex_atomic_op(insn, ret, oldval, uaddr, oparg)		\
 {									\
+	smp_mb__before_llsc();						\
+									\
 	if (cpu_has_llsc && R10000_LLSC_WAR) {				\
 		__asm__ __volatile__(					\
 		"	.set	push				\n"	\
@@ -149,6 +151,8 @@ futex_atomic_cmpxchg_inatomic(u32 *uval, u32 __user *uaddr,
 	if (!access_ok(VERIFY_WRITE, uaddr, sizeof(u32)))
 		return -EFAULT;
 
+	smp_mb__before_llsc();
+
 	if (cpu_has_llsc && R10000_LLSC_WAR) {
 		__asm__ __volatile__(
 		"# futex_atomic_cmpxchg_inatomic			\n"
include/asm-generic/futex.h +1 -25
index e56272c919b5..e3c2a0cea438 100644
@@ -12,18 +12,6 @@
  *
  */
 
-/**
- * futex_atomic_op_inuser() - Atomic arithmetic operation with constant
- *			  argument and comparison of the previous
- *			  futex value with another constant.
- *
- * @encoded_op:	encoded operation to execute
- * @uaddr:	pointer to user space address
- *
- * Return:
- * 0 - On success
- * <0 - On error
- */
 static inline int
 futex_atomic_op_inuser(int encoded_op, u32 __user *uaddr)
 {
@@ -88,19 +76,6 @@ futex_atomic_op_inuser(int encoded_op, u32 __user *uaddr)
 	return ret;
 }
 
-/**
- * futex_atomic_cmpxchg_inatomic() - Compare and exchange the content of the
- *				uaddr with newval if the current value is
- *				oldval.
- * @uval:	pointer to store content of @uaddr
- * @uaddr:	pointer to user space address
- * @oldval:	old value
- * @newval:	new value to store to @uaddr
- *
- * Return:
- * 0 - On success
- * <0 - On error
- */
 static inline int
 futex_atomic_cmpxchg_inatomic(u32 *uval, u32 __user *uaddr,
 			      u32 oldval, u32 newval)
@@ -121,6 +96,7 @@ futex_atomic_cmpxchg_inatomic(u32 *uval, u32 __user *uaddr,
 }
 
 #else
+
 static inline int
 futex_atomic_op_inuser (int encoded_op, u32 __user *uaddr)
 {
include/linux/futex.h +35 -0
index 6435f46d6e13..fadb46f38800 100644
@@ -55,6 +55,41 @@ union futex_key {
 #ifdef CONFIG_FUTEX
 extern void exit_robust_list(struct task_struct *curr);
 extern void exit_pi_state_list(struct task_struct *curr);
+
+/**
+ * futex_atomic_op_inuser() - Atomic arithmetic operation with constant
+ *			  argument and comparison of the previous
+ *			  futex value with another constant.
+ *
+ * @encoded_op:	encoded operation to execute
+ * @uaddr:	pointer to user space address
+ *
+ * This operation is assumed to be fully ordered.
+ *
+ * Return:
+ * 0 - On success
+ * <0 - On error
+ */
+extern int futex_atomic_op_inuser(int encoded_op, u32 __user *uaddr);
+
+/**
+ * futex_atomic_cmpxchg_inatomic() - Compare and exchange the content of the
+ *				uaddr with newval if the current value is
+ *				oldval.
+ * @uval:	pointer to store content of @uaddr
+ * @uaddr:	pointer to user space address
+ * @oldval:	old value
+ * @newval:	new value to store to @uaddr
+ *
+ * This operation is assumed to be fully ordered.
+ *
+ * Return:
+ * 0 - On success
+ * <0 - On error
+ */
+extern int futex_atomic_cmpxchg_inatomic(u32 *uval, u32 __user *uaddr,
+					 u32 oldval, u32 newval);
+
 #ifdef CONFIG_HAVE_FUTEX_CMPXCHG
 #define futex_cmpxchg_enabled 1
 #else
#8 lore raw
Quoted 20 lines · Peter Zijlstra

So here goes..

Chris, I'm awfully sorry, but I seem to be Tile challenged.

TileGX seems to define:

#define smp_mb__before_atomic() smp_mb()
#define smp_mb__after_atomic() smp_mb()

However, its atomic_add_return() implementation looks like:

static inline int atomic_add_return(int i, atomic_t *v)

{
	int val;
	smp_mb();  /* barrier for proper semantics */
	val = __insn_fetchadd4((void *)&v->counter, i) + i;
	barrier();  /* the "+ i" above will wait on memory */
	return val;
}
Quoted 1 line

Which leaves me confused on smp_mb__after_atomic().

Are you concerned about whether it has proper memory barrier semantics already, i.e. full barriers before and after? In fact we do have a full barrier before, but then because of the "+ i" / "barrier()", we know that the only other operation since the previous mb(), namely the read of v->counter, has completed after the atomic operation. As a result we can omit explicitly having a second barrier.

It does seem like all the current memory-order semantics are correct, unless I'm missing something!

Quoted 2 lines

That said, your futex ops seem to lack any memory barrier, so naively I'd add both, its just that your add_return() confuses me.

So something like this?

arch/tile/include/asm/futex.h +7 -2
index 1a6ef1b69cb1..0a5501b11d02 100644
@@ -39,6 +39,7 @@
 #ifdef __tilegx__
 
 #define __futex_asm(OP) \
+	smp_mb();						\
 	asm("1: {" #OP " %1, %3, %4; movei %0, 0 }\n"		\
 	    ".pushsection .fixup,\"ax\"\n"			\
 	    "0: { movei %0, %5; j 9f }\n"			\
@@ -48,7 +49,8 @@
 	    ".popsection\n"					\
 	    "9:"						\
 	    : "=r" (ret), "=r" (val), "+m" (*(uaddr))		\
-	    : "r" (uaddr), "r" (oparg), "i" (-EFAULT))
+	    : "r" (uaddr), "r" (oparg), "i" (-EFAULT)); 	\
+	smp_mb()
 
 #define __futex_set() __futex_asm(exch4)
 #define __futex_add() __futex_asm(fetchadd4)
@@ -75,7 +77,10 @@
 
 #define __futex_call(FN)						\
 	{								\
-		struct __get_user gu = FN((u32 __force *)uaddr, lock, oparg); \
+		struct __get_user gu;					\
+		smp_mb();						\
+		gu = FN((u32 __force *)uaddr, lock, oparg);		\
+		/* See smp_mb__after_atomic() */			\
 		val = gu.val;						\
 		ret = gu.err;						\
 	}
Signature · 2 lines
Chris Metcalf, EZChip Semiconductor
http://www.ezchip.com
author reviewer
#9 lore raw
Quoted 31 lines · Chris Metcalf
Quoted 20 lines · Peter Zijlstra

So here goes..

Chris, I'm awfully sorry, but I seem to be Tile challenged.

TileGX seems to define:

#define smp_mb__before_atomic() smp_mb()
#define smp_mb__after_atomic() smp_mb()

However, its atomic_add_return() implementation looks like:

static inline int atomic_add_return(int i, atomic_t *v)

{
	int val;
	smp_mb();  /* barrier for proper semantics */
	val = __insn_fetchadd4((void *)&v->counter, i) + i;
	barrier();  /* the "+ i" above will wait on memory */
	return val;
}
Quoted 1 line

Which leaves me confused on smp_mb__after_atomic().

Are you concerned about whether it has proper memory barrier semantics already, i.e. full barriers before and after? In fact we do have a full barrier before, but then because of the "+ i" / "barrier()", we know that the only other operation since the previous mb(), namely the read of v->counter, has completed after the atomic operation. As a result we can omit explicitly having a second barrier.

Quoted 2 lines

It does seem like all the current memory-order semantics are correct, unless I'm missing something!

So I'm reading that code like:

MB
[RmW] ret = *val += i

So what is stopping later memory ops like:

[R] a = *foo
[S] *bar = b

Quoted 1 line

From getting reordered with the RmW, like:

MB

[R] a = *foo
[S] *bar = b

[RmW] ret = *val += i

Are you saying Tile does not reorder things like that? If so, why then is smp_mb__after_atomic() a full mb(). If it does, I don't see how your add_return is correct.

Alternatively I'm just confused..

#10 lore raw
Quoted 51 lines · Peter Zijlstra
Quoted 30 lines · Chris Metcalf
Quoted 20 lines · Peter Zijlstra

So here goes..

Chris, I'm awfully sorry, but I seem to be Tile challenged.

TileGX seems to define:

#define smp_mb__before_atomic() smp_mb()
#define smp_mb__after_atomic() smp_mb()

However, its atomic_add_return() implementation looks like:

static inline int atomic_add_return(int i, atomic_t *v)

{
	int val;
	smp_mb();  /* barrier for proper semantics */
	val = __insn_fetchadd4((void *)&v->counter, i) + i;
	barrier();  /* the "+ i" above will wait on memory */
	return val;
}
Quoted 1 line

Which leaves me confused on smp_mb__after_atomic().

Are you concerned about whether it has proper memory barrier semantics already, i.e. full barriers before and after? In fact we do have a full barrier before, but then because of the "+ i" / "barrier()", we know that the only other operation since the previous mb(), namely the read of v->counter, has completed after the atomic operation. As a result we can omit explicitly having a second barrier.

Quoted 2 lines

It does seem like all the current memory-order semantics are correct, unless I'm missing something!

So I'm reading that code like:

MB
[RmW] ret = *val += i

So what is stopping later memory ops like:

    [R]	a = *foo
    [S]	*bar = b

From getting reordered with the RmW, like:

	MB

    [R]	a = *foo
    [S]	*bar = b
Quoted 7 lines

[RmW] ret = *val += i

Are you saying Tile does not reorder things like that? If so, why then is smp_mb__after_atomic() a full mb(). If it does, I don't see how your add_return is correct.

Alternatively I'm just confused..

Tile does not do out-of-order instruction issue, but it does have an out-of-order memory subsystem, so in addition to stores becoming unpredictably visible without a memory barrier, loads will also potentially not read from memory predictably after issue. As a result, later operations that use a register that was previously loaded may stall instruction issue until the load value is available. A memory fence instruction will cause the core to wait for all stores to become visible and all load values to be available.

So [R] can't move up to before [RmW] due to the in-order issue nature of the processor. And smp_mb__after_atomic() has to be a full mb() because that's the only barrier we have available to guarantee that the load has read from memory. (If the value of the actual atomic was passed to smp_mb__after_atomic() then we could just generate a fake use of the value, basically generating something like "move r1, r1", which would cause the instruction issue to halt until the value had been read.)

Signature · 2 lines
Chris Metcalf, EZChip Semiconductor
http://www.ezchip.com
#11 lore raw
In reply to Peter Zijlstra
Quoted 12 lines · Peter Zijlstra

So I'm reading that code like:

MB
[RmW] ret = *val += i

So what is stopping later memory ops like:

   [R]  a = *foo
   [S]  *bar = b
Quoted 8 lines

From getting reordered with the RmW, like:

MB

   [R]  a = *foo
   [S]  *bar = b

[RmW] ret = *val += i

So I do agree that for the atomic futex operation to be usable for locking (which I think we all agree is a primary objective), the futex write operations have to work both as acquire and release operations, which basically means that it has to be both an acquire _and_ release op.

That said, I'm not sure it really needs to be a full memory barrier on both sides, and in particular, I'm not sure it needs to be a memory barroer for the surrounding *kernel* operations.

So I do suspect that adding full smp_mb()'s on both sides is not necessarily required for architectures, because there are often serialization guarantees at kernel entry/exit.

So I think we could possibly relax the requirements (and document this very clearly) to say that the futex operation must be totally ordered wrt any other _user_space_ accesses by that thread. I suspect a lot of architectures can then say "we may be very weakly ordered, but kernel entry/exit implies enough synchronization that we do not need any futher memory barriers".

For example, on x86, the locked instructions are obviously already sufficiently strong, but even if they weren't, kernel entry/exit is documented to be a serializing instruction (which is something insanely much stronger than just memory ordering). And I suspect there are similar issues on a lot of architectures where the memory ordering is done by the core, but the cache subsystem is strongly ordered (ie saen good SMP systems - so it sounds like tile needs the smp_mb()'s, but I would almost suspect that POWER and ARM might *not* need them).

Linus

#12 lore raw
Quoted 8 lines · Linus Torvalds

For example, on x86, the locked instructions are obviously already sufficiently strong, but even if they weren't, kernel entry/exit is documented to be a serializing instruction (which is something insanely much stronger than just memory ordering). And I suspect there are similar issues on a lot of architectures where the memory ordering is done by the core, but the cache subsystem is strongly ordered (ie saen good SMP systems - so it sounds like tile needs the smp_mb()'s, but I would almost suspect that POWER and ARM might *not* need them).

Because POWER and ARM have serializing kernel entry/exit? I think tile has relatively conventional cache/memory semantics, but it's certainly true there is implicit memory ordering guarantee for kernel entry/exit.

Signature · 2 lines
Chris Metcalf, EZChip Semiconductor
http://www.ezchip.com
author reviewer
#13 lore raw
In reply to Linus Torvalds
Quoted 6 lines · Linus Torvalds

So I think we could possibly relax the requirements (and document this very clearly) to say that the futex operation must be totally ordered wrt any other _user_space_ accesses by that thread. I suspect a lot of architectures can then say "we may be very weakly ordered, but kernel entry/exit implies enough synchronization that we do not need any futher memory barriers".

Right, so before sending this email I actually spoke to Ralf about this option, and he said that this is not actually well defined for MIPS.

But we could certainly document it such and let archs for which this is well documented (I would expect this to be most) choose that implementation.

#14 lore raw
Quoted 8 lines · Peter Zijlstra
Quoted 6 lines · Linus Torvalds

So I think we could possibly relax the requirements (and document this very clearly) to say that the futex operation must be totally ordered wrt any other _user_space_ accesses by that thread. I suspect a lot of architectures can then say "we may be very weakly ordered, but kernel entry/exit implies enough synchronization that we do not need any futher memory barriers".

Quoted 6 lines

Right, so before sending this email I actually spoke to Ralf about this option, and he said that this is not actually well defined for MIPS.

But we could certainly document it such and let archs for which this is well documented (I would expect this to be most) choose that implementation.

Whilst a control-dependency + exception return forms a barrier of sorts on arm/arm64, it's not required to be transitive [1], so I wouldn't be comfortable making that relaxation on the futex path.

Will

[1] See, for example, "ISA2+dmb+ctrlisb+dmb" at

    https://www.cl.cam.ac.uk/~pes20/ppcmem/index.html#ARM