Skip to contentSkip to conversation

locking/atomic: Make test_and_*_bit() ordered on failure

PATCH In review Hector Martin 8 participants 15 messages Aug 16, 2022 – Aug 17, 2022

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

PATCH 1/1 locking/atomic: Make test_and_*_bit() ordered on failure

These operations are documented as always ordered in include/asm-generic/bitops/instrumented-atomic.h, and producer-consumer type use cases where one side needs to ensure a flag is left pending after some shared data was updated rely on this ordering, even in the failure case.

This is the case with the workqueue code, which currently suffers from a reproducible ordering violation on Apple M1 platforms (which are notoriously out-of-order) that ends up causing the TTY layer to fail to deliver data to userspace properly under the right conditions. This change fixes that bug.

Change the documentation to restrict the "no order on failure" story to the _lock() variant (for which it makes sense), and remove the early-exit from the generic implementation, which is what causes the missing barrier semantics in that case. Without this, the remaining atomic op is fully ordered (including on ARM64 LSE, as of recent versions of the architecture spec).

Fixes e986a0d6cb36 ("locking/atomics, asm-generic/bitops/atomic.h: Rewrite using atomic_*() APIs")
Fixes 61e02392d3c7 ("locking/atomic/bitops: Document and clarify ordering semantics for failed test_and_{}_bit()")
---
 Documentation/atomic_bitops.txt     | 2 +-
 include/asm-generic/bitops/atomic.h | 6 ------
 2 files changed, 1 insertion(+), 7 deletions(-)
Documentation/atomic_bitops.txt +1 -1
index 093cdaefdb37..d8b101c97031 100644
@@ -59,7 +59,7 @@ Like with atomic_t, the rule of thumb is:
  - RMW operations that have a return value are fully ordered.
 
  - RMW operations that are conditional are unordered on FAILURE,
-   otherwise the above rules apply. In the case of test_and_{}_bit() operations,
+   otherwise the above rules apply. In the case of test_and_set_bit_lock(),
    if the bit in memory is unchanged by the operation then it is deemed to have
    failed.
 
include/asm-generic/bitops/atomic.h +0 -6
index 3096f086b5a3..71ab4ba9c25d 100644
@@ -39,9 +39,6 @@ arch_test_and_set_bit(unsigned int nr, volatile unsigned long *p)
 	unsigned long mask = BIT_MASK(nr);
 
 	p += BIT_WORD(nr);
-	if (READ_ONCE(*p) & mask)
-		return 1;
-
 	old = arch_atomic_long_fetch_or(mask, (atomic_long_t *)p);
 	return !!(old & mask);
 }
@@ -53,9 +50,6 @@ arch_test_and_clear_bit(unsigned int nr, volatile unsigned long *p)
 	unsigned long mask = BIT_MASK(nr);
 
 	p += BIT_WORD(nr);
-	if (!(READ_ONCE(*p) & mask))
-		return 0;
-
 	old = arch_atomic_long_fetch_andnot(mask, (atomic_long_t *)p);
 	return !!(old & mask);
 }
Signature · 1 line
2.35.1
maintainer Reviewed-by on v1 1/1
#1 lore raw
Quoted 20 lines · Hector Martin

These operations are documented as always ordered in include/asm-generic/bitops/instrumented-atomic.h, and producer-consumer type use cases where one side needs to ensure a flag is left pending after some shared data was updated rely on this ordering, even in the failure case.

This is the case with the workqueue code, which currently suffers from a reproducible ordering violation on Apple M1 platforms (which are notoriously out-of-order) that ends up causing the TTY layer to fail to deliver data to userspace properly under the right conditions. This change fixes that bug.

Change the documentation to restrict the "no order on failure" story to the _lock() variant (for which it makes sense), and remove the early-exit from the generic implementation, which is what causes the missing barrier semantics in that case. Without this, the remaining atomic op is fully ordered (including on ARM64 LSE, as of recent versions of the architecture spec).

Quoted 8 lines
Fixes e986a0d6cb36 ("locking/atomics, asm-generic/bitops/atomic.h: Rewrite using atomic_*() APIs")
Fixes 61e02392d3c7 ("locking/atomic/bitops: Document and clarify ordering semantics for failed test_and_{}_bit()")
---
 Documentation/atomic_bitops.txt     | 2 +-
 include/asm-generic/bitops/atomic.h | 6 ------

I double-checked all the architecture specific implementations to ensure that the asm-generic one is the only one that needs the fix.

I assume this gets merged through the locking tree or that Linus picks it up directly, not through my asm-generic tree.

#2 lore raw
Quoted 37 lines · Arnd Bergmann
Quoted 20 lines · Hector Martin

These operations are documented as always ordered in include/asm-generic/bitops/instrumented-atomic.h, and producer-consumer type use cases where one side needs to ensure a flag is left pending after some shared data was updated rely on this ordering, even in the failure case.

This is the case with the workqueue code, which currently suffers from a reproducible ordering violation on Apple M1 platforms (which are notoriously out-of-order) that ends up causing the TTY layer to fail to deliver data to userspace properly under the right conditions. This change fixes that bug.

Change the documentation to restrict the "no order on failure" story to the _lock() variant (for which it makes sense), and remove the early-exit from the generic implementation, which is what causes the missing barrier semantics in that case. Without this, the remaining atomic op is fully ordered (including on ARM64 LSE, as of recent versions of the architecture spec).

Quoted 8 lines
Fixes e986a0d6cb36 ("locking/atomics, asm-generic/bitops/atomic.h: Rewrite using atomic_*() APIs")
Fixes 61e02392d3c7 ("locking/atomic/bitops: Document and clarify ordering semantics for failed test_and_{}_bit()")
---
 Documentation/atomic_bitops.txt     | 2 +-
 include/asm-generic/bitops/atomic.h | 6 ------

I double-checked all the architecture specific implementations to ensure that the asm-generic one is the only one that needs the fix.

I assume this gets merged through the locking tree or that Linus picks it up directly, not through my asm-generic tree.

Quoted 6 lines

_______________________________________________
linux-arm-kernel mailing list
[email protected]
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Testing this patch on pre Armv8.1 specifically Cortex-A72 and Cortex-A53 cores I am seeing
a huge performance drop with this patch applied. Perf is showing lock_is_held_type() as the worst offender
but that could just be the function getting blamed. The most obvious indicator of the performance loss is
ssh throughput. With the patch I am only able to achieve around 20MB/s and without the patch I am able
to transfer around 112MB/s, no other changes.

When I have more time I can do some more in depth testing, but for now I just wanted to bring this
issue up so perhaps others can chime in regarding how it performs on their hardware.

-Jon

maintainer
#3 lore raw
Quoted 45 lines · Jon Nettleton
Quoted 37 lines · Arnd Bergmann
Quoted 20 lines · Hector Martin

These operations are documented as always ordered in include/asm-generic/bitops/instrumented-atomic.h, and producer-consumer type use cases where one side needs to ensure a flag is left pending after some shared data was updated rely on this ordering, even in the failure case.

This is the case with the workqueue code, which currently suffers from a reproducible ordering violation on Apple M1 platforms (which are notoriously out-of-order) that ends up causing the TTY layer to fail to deliver data to userspace properly under the right conditions. This change fixes that bug.

Change the documentation to restrict the "no order on failure" story to the _lock() variant (for which it makes sense), and remove the early-exit from the generic implementation, which is what causes the missing barrier semantics in that case. Without this, the remaining atomic op is fully ordered (including on ARM64 LSE, as of recent versions of the architecture spec).

Quoted 8 lines
Fixes e986a0d6cb36 ("locking/atomics, asm-generic/bitops/atomic.h: Rewrite using atomic_*() APIs")
Fixes 61e02392d3c7 ("locking/atomic/bitops: Document and clarify ordering semantics for failed test_and_{}_bit()")
---
 Documentation/atomic_bitops.txt     | 2 +-
 include/asm-generic/bitops/atomic.h | 6 ------

I double-checked all the architecture specific implementations to ensure that the asm-generic one is the only one that needs the fix.

I assume this gets merged through the locking tree or that Linus picks it up directly, not through my asm-generic tree.

Quoted 6 lines

_______________________________________________
linux-arm-kernel mailing list
[email protected]
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Quoted 4 lines

Testing this patch on pre Armv8.1 specifically Cortex-A72 and Cortex-A53 cores I am seeing
a huge performance drop with this patch applied. Perf is showing lock_is_held_type() as the worst offender

Hmm, that should only exist if LOCKDEP is enabled and performance tends to go out of the window if you have that on. Can you reproduce the same regression with lockdep disabled?

Will

#4 lore raw
Quoted 52 lines · Will Deacon
Quoted 45 lines · Jon Nettleton
Quoted 37 lines · Arnd Bergmann
Quoted 20 lines · Hector Martin

These operations are documented as always ordered in include/asm-generic/bitops/instrumented-atomic.h, and producer-consumer type use cases where one side needs to ensure a flag is left pending after some shared data was updated rely on this ordering, even in the failure case.

This is the case with the workqueue code, which currently suffers from a reproducible ordering violation on Apple M1 platforms (which are notoriously out-of-order) that ends up causing the TTY layer to fail to deliver data to userspace properly under the right conditions. This change fixes that bug.

Change the documentation to restrict the "no order on failure" story to the _lock() variant (for which it makes sense), and remove the early-exit from the generic implementation, which is what causes the missing barrier semantics in that case. Without this, the remaining atomic op is fully ordered (including on ARM64 LSE, as of recent versions of the architecture spec).

Quoted 8 lines
Fixes e986a0d6cb36 ("locking/atomics, asm-generic/bitops/atomic.h: Rewrite using atomic_*() APIs")
Fixes 61e02392d3c7 ("locking/atomic/bitops: Document and clarify ordering semantics for failed test_and_{}_bit()")
---
 Documentation/atomic_bitops.txt     | 2 +-
 include/asm-generic/bitops/atomic.h | 6 ------

I double-checked all the architecture specific implementations to ensure that the asm-generic one is the only one that needs the fix.

I assume this gets merged through the locking tree or that Linus picks it up directly, not through my asm-generic tree.

Quoted 6 lines

_______________________________________________
linux-arm-kernel mailing list
[email protected]
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Quoted 4 lines

Testing this patch on pre Armv8.1 specifically Cortex-A72 and Cortex-A53 cores I am seeing
a huge performance drop with this patch applied. Perf is showing lock_is_held_type() as the worst offender

Quoted 5 lines

Hmm, that should only exist if LOCKDEP is enabled and performance tends to go out of the window if you have that on. Can you reproduce the same regression with lockdep disabled?

Will

Yep I am working on it. We should note that

config LOCKDEP_SUPPORT
def_bool y

is the default for arm64

-Jon

#5 lore raw
Quoted 58 lines · Jon Nettleton
Quoted 56 lines · Will Deacon
Quoted 45 lines · Jon Nettleton
Quoted 37 lines · Arnd Bergmann
Quoted 20 lines · Hector Martin

These operations are documented as always ordered in include/asm-generic/bitops/instrumented-atomic.h, and producer-consumer type use cases where one side needs to ensure a flag is left pending after some shared data was updated rely on this ordering, even in the failure case.

This is the case with the workqueue code, which currently suffers from a reproducible ordering violation on Apple M1 platforms (which are notoriously out-of-order) that ends up causing the TTY layer to fail to deliver data to userspace properly under the right conditions. This change fixes that bug.

Change the documentation to restrict the "no order on failure" story to the _lock() variant (for which it makes sense), and remove the early-exit from the generic implementation, which is what causes the missing barrier semantics in that case. Without this, the remaining atomic op is fully ordered (including on ARM64 LSE, as of recent versions of the architecture spec).

Quoted 8 lines
Fixes e986a0d6cb36 ("locking/atomics, asm-generic/bitops/atomic.h: Rewrite using atomic_*() APIs")
Fixes 61e02392d3c7 ("locking/atomic/bitops: Document and clarify ordering semantics for failed test_and_{}_bit()")
---
 Documentation/atomic_bitops.txt     | 2 +-
 include/asm-generic/bitops/atomic.h | 6 ------

I double-checked all the architecture specific implementations to ensure that the asm-generic one is the only one that needs the fix.

I assume this gets merged through the locking tree or that Linus picks it up directly, not through my asm-generic tree.

Quoted 6 lines

_______________________________________________
linux-arm-kernel mailing list
[email protected]
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Quoted 4 lines

Testing this patch on pre Armv8.1 specifically Cortex-A72 and Cortex-A53 cores I am seeing
a huge performance drop with this patch applied. Perf is showing lock_is_held_type() as the worst offender

Hmm, that should only exist if LOCKDEP is enabled and performance tends to go out of the window if you have that on. Can you reproduce the same regression with lockdep disabled?

Quoted 8 lines
Quoted 1 line

Will

Yep I am working on it. We should note that

config LOCKDEP_SUPPORT
def_bool y

is the default for arm64

Yes, as the architecture supports LOCKDEP. However, you probably have something like CONFIG_PROVE_LOCKING to see such a performance hit (and that's definitely not on by default).

	M.
Signature · 1 line
Without deviation from the norm, progress is not possible.
maintainer
#6 lore raw
In reply to Arnd Bergmann
Quoted 30 lines · Arnd Bergmann
Quoted 20 lines · Hector Martin

These operations are documented as always ordered in include/asm-generic/bitops/instrumented-atomic.h, and producer-consumer type use cases where one side needs to ensure a flag is left pending after some shared data was updated rely on this ordering, even in the failure case.

This is the case with the workqueue code, which currently suffers from a reproducible ordering violation on Apple M1 platforms (which are notoriously out-of-order) that ends up causing the TTY layer to fail to deliver data to userspace properly under the right conditions. This change fixes that bug.

Change the documentation to restrict the "no order on failure" story to the _lock() variant (for which it makes sense), and remove the early-exit from the generic implementation, which is what causes the missing barrier semantics in that case. Without this, the remaining atomic op is fully ordered (including on ARM64 LSE, as of recent versions of the architecture spec).

Quoted 8 lines
Fixes e986a0d6cb36 ("locking/atomics, asm-generic/bitops/atomic.h: Rewrite using atomic_*() APIs")
Fixes 61e02392d3c7 ("locking/atomic/bitops: Document and clarify ordering semantics for failed test_and_{}_bit()")
---
 Documentation/atomic_bitops.txt     | 2 +-
 include/asm-generic/bitops/atomic.h | 6 ------
Quoted 2 lines

I double-checked all the architecture specific implementations to ensure that the asm-generic one is the only one that needs the fix.

I couldn't figure out parisc -- do you know what ordering their spinlocks provide? They have a comment talking about a release, but I don't know what the ordering guarantees of an "ldcw" are.

Will

#7 lore raw
Quoted 31 lines · Will Deacon
Quoted 30 lines · Arnd Bergmann
Quoted 28 lines · Hector Martin

These operations are documented as always ordered in include/asm-generic/bitops/instrumented-atomic.h, and producer-consumer type use cases where one side needs to ensure a flag is left pending after some shared data was updated rely on this ordering, even in the failure case.

This is the case with the workqueue code, which currently suffers from a reproducible ordering violation on Apple M1 platforms (which are notoriously out-of-order) that ends up causing the TTY layer to fail to deliver data to userspace properly under the right conditions. This change fixes that bug.

Change the documentation to restrict the "no order on failure" story to the _lock() variant (for which it makes sense), and remove the early-exit from the generic implementation, which is what causes the missing barrier semantics in that case. Without this, the remaining atomic op is fully ordered (including on ARM64 LSE, as of recent versions of the architecture spec).

Fixes e986a0d6cb36 ("locking/atomics, asm-generic/bitops/atomic.h: Rewrite using atomic_*() APIs")
Fixes 61e02392d3c7 ("locking/atomic/bitops: Document and clarify ordering semantics for failed test_and_{}_bit()")
---
 Documentation/atomic_bitops.txt     | 2 +-
 include/asm-generic/bitops/atomic.h | 6 ------
Quoted 6 lines
Quoted 2 lines

I double-checked all the architecture specific implementations to ensure that the asm-generic one is the only one that needs the fix.

I couldn't figure out parisc -- do you know what ordering their spinlocks provide? They have a comment talking about a release, but I don't know what the ordering guarantees of an "ldcw" are.

"The semaphore operation is strongly ordered" (that's from the description of the LDCW instruction)

maintainer Acked-by on v1 1/1
#8 lore raw
In reply to Hector Martin
Quoted 34 lines · Hector Martin

These operations are documented as always ordered in include/asm-generic/bitops/instrumented-atomic.h, and producer-consumer type use cases where one side needs to ensure a flag is left pending after some shared data was updated rely on this ordering, even in the failure case.

This is the case with the workqueue code, which currently suffers from a reproducible ordering violation on Apple M1 platforms (which are notoriously out-of-order) that ends up causing the TTY layer to fail to deliver data to userspace properly under the right conditions. This change fixes that bug.

Change the documentation to restrict the "no order on failure" story to the _lock() variant (for which it makes sense), and remove the early-exit from the generic implementation, which is what causes the missing barrier semantics in that case. Without this, the remaining atomic op is fully ordered (including on ARM64 LSE, as of recent versions of the architecture spec).

Fixes e986a0d6cb36 ("locking/atomics, asm-generic/bitops/atomic.h: Rewrite using atomic_*() APIs")
Fixes 61e02392d3c7 ("locking/atomic/bitops: Document and clarify ordering semantics for failed test_and_{}_bit()")
---
 Documentation/atomic_bitops.txt     | 2 +-
 include/asm-generic/bitops/atomic.h | 6 ------
 2 files changed, 1 insertion(+), 7 deletions(-)
Documentation/atomic_bitops.txt +0 -0
index 093cdaefdb37..d8b101c97031 100644

Documentation/atomic_bitops.txt Like with atomic_t, the rule of thumb is: · line 64

Quoted 7 lines
Documentation/atomic_bitops.txt +1 -1
@@ -59,7 +59,7 @@ Like with atomic_t, the rule of thumb is:
  - RMW operations that have a return value are fully ordered.
 
  - RMW operations that are conditional are unordered on FAILURE,
-   otherwise the above rules apply. In the case of test_and_{}_bit() operations,
+   otherwise the above rules apply. In the case of test_and_set_bit_lock(),
    if the bit in memory is unchanged by the operation then it is deemed to have
    failed.

The next sentence is:

| Except for a successful test_and_set_bit_lock() which has ACQUIRE | semantics and clear_bit_unlock() which has RELEASE semantics.

so I think it reads a bit strangely now. How about something like:

Documentation/atomic_bitops.txt +8 -5
index 093cdaefdb37..3b516729ec81 100644
@@ -59,12 +59,15 @@ Like with atomic_t, the rule of thumb is:
  - RMW operations that have a return value are fully ordered.
 
  - RMW operations that are conditional are unordered on FAILURE,
-   otherwise the above rules apply. In the case of test_and_{}_bit() operations,
-   if the bit in memory is unchanged by the operation then it is deemed to have
-   failed.
+   otherwise the above rules apply. For the purposes of ordering, the
+   test_and_{}_bit() operations are treated as unconditional.
 
-Except for a successful test_and_set_bit_lock() which has ACQUIRE semantics and
-clear_bit_unlock() which has RELEASE semantics.
+Except for:
+
+ - test_and_set_bit_lock() which has ACQUIRE semantics on success and is
+   unordered on failure;
+
+ - clear_bit_unlock() which has RELEASE semantics.
 
 Since a platform only has a single means of achieving atomic operations
 the same barriers as for atomic_t are used, see atomic_t.txt.

?

Quoted 15 lines
include/asm-generic/bitops/atomic.h +0 -3
index 3096f086b5a3..71ab4ba9c25d 100644
@@ -39,9 +39,6 @@ arch_test_and_set_bit(unsigned int nr, volatile unsigned long *p)
 	unsigned long mask = BIT_MASK(nr);
 
 	p += BIT_WORD(nr);
-	if (READ_ONCE(*p) & mask)
-		return 1;
-
 	old = arch_atomic_long_fetch_or(mask, (atomic_long_t *)p);
 	return !!(old & mask);
 }

include/asm-generic/bitops/atomic.h arch_test_and_clear_bit(unsigned int nr, volatile unsigned long *p) · line 54

Quoted 8 lines
include/asm-generic/bitops/atomic.h +0 -3
@@ -53,9 +50,6 @@ arch_test_and_clear_bit(unsigned int nr, volatile unsigned long *p)
 	unsigned long mask = BIT_MASK(nr);
 
 	p += BIT_WORD(nr);
-	if (!(READ_ONCE(*p) & mask))
-		return 0;
-
 	old = arch_atomic_long_fetch_andnot(mask, (atomic_long_t *)p);
 	return !!(old & mask);

I suppose one sad thing about this is that, on arm64, we could reasonably keep the READ_ONCE() path with a DMB LD (R->RW) barrier before the return but I don't think we can express that in the Linux memory model so we end up in RmW territory every time. Perhaps we should roll our own implementation in the arch code?

In any case, this should fix the problem so:

Will

#9 lore raw
Quoted 36 lines · Will Deacon

Documentation/atomic_bitops.txt Like with atomic_t, the rule of thumb is: · line 64

Quoted 12 lines
Documentation/atomic_bitops.txt +1 -1
index 093cdaefdb37..d8b101c97031 100644
@@ -59,7 +59,7 @@ Like with atomic_t, the rule of thumb is:
  - RMW operations that have a return value are fully ordered.
 
  - RMW operations that are conditional are unordered on FAILURE,
-   otherwise the above rules apply. In the case of test_and_{}_bit() operations,
+   otherwise the above rules apply. In the case of test_and_set_bit_lock(),
    if the bit in memory is unchanged by the operation then it is deemed to have
    failed.

The next sentence is:

| Except for a successful test_and_set_bit_lock() which has ACQUIRE | semantics and clear_bit_unlock() which has RELEASE semantics.

so I think it reads a bit strangely now. How about something like:

Documentation/atomic_bitops.txt +2 -4
index 093cdaefdb37..3b516729ec81 100644
@@ -59,12 +59,15 @@ Like with atomic_t, the rule of thumb is:
  - RMW operations that have a return value are fully ordered.
 
  - RMW operations that are conditional are unordered on FAILURE,
-   otherwise the above rules apply. In the case of test_and_{}_bit() operations,
-   if the bit in memory is unchanged by the operation then it is deemed to have
-   failed.
+   otherwise the above rules apply. For the purposes of ordering, the
+   test_and_{}_bit() operations are treated as unconditional.
 
-Except for a successful test_and_set_bit_lock() which has ACQUIRE semantics and

Documentation/atomic_bitops.txt Like with atomic_t, the rule of thumb is: · line 73

Quoted 10 lines
Documentation/atomic_bitops.txt +6 -1
-clear_bit_unlock() which has RELEASE semantics.
+Except for:
+
+ - test_and_set_bit_lock() which has ACQUIRE semantics on success and is
+   unordered on failure;
+
+ - clear_bit_unlock() which has RELEASE semantics.
 
 Since a platform only has a single means of achieving atomic operations
 the same barriers as for atomic_t are used, see atomic_t.txt.

Makes sense! I'll send a v2 with that in a couple of days if nothing else comes up.

Quoted 17 lines
Quoted 17 lines
include/asm-generic/bitops/atomic.h +0 -3
index 3096f086b5a3..71ab4ba9c25d 100644
@@ -39,9 +39,6 @@ arch_test_and_set_bit(unsigned int nr, volatile unsigned long *p)
 	unsigned long mask = BIT_MASK(nr);
 
 	p += BIT_WORD(nr);
-	if (READ_ONCE(*p) & mask)
-		return 1;
-
 	old = arch_atomic_long_fetch_or(mask, (atomic_long_t *)p);
 	return !!(old & mask);
 }
@@ -53,9 +50,6 @@ arch_test_and_clear_bit(unsigned int nr, volatile unsigned long *p)
 	unsigned long mask = BIT_MASK(nr);
 
Quoted 11 lines

include/asm-generic/bitops/atomic.h arch_test_and_clear_bit(unsigned int nr, volatile unsigned long *p) · line 54

Quoted 6 lines
include/asm-generic/bitops/atomic.h +0 -3
 	p += BIT_WORD(nr);
-	if (!(READ_ONCE(*p) & mask))
-		return 0;
-
 	old = arch_atomic_long_fetch_andnot(mask, (atomic_long_t *)p);
 	return !!(old & mask);

I suppose one sad thing about this is that, on arm64, we could reasonably keep the READ_ONCE() path with a DMB LD (R->RW) barrier before the return but I don't think we can express that in the Linux memory model so we end up in RmW territory every time.

You'd need a barrier *before* the READ_ONCE(), since what we're trying to prevent is a consumer from writing to the value without being able to observe the writes that happened prior, while this side read the old value. A barrier after the READ_ONCE() doesn't do anything, as that read is the last memory operation in this thread (of the problematic sequence).

At that point, I'm not sure DMB LD / early read / LSE atomic would be any faster than just always doing the LSE atomic?

- Hector

maintainer
#10 lore raw
Quoted 30 lines · Hector Martin
Quoted 17 lines · Will Deacon
Quoted 17 lines
include/asm-generic/bitops/atomic.h +0 -3
index 3096f086b5a3..71ab4ba9c25d 100644
@@ -39,9 +39,6 @@ arch_test_and_set_bit(unsigned int nr, volatile unsigned long *p)
 	unsigned long mask = BIT_MASK(nr);
 
 	p += BIT_WORD(nr);
-	if (READ_ONCE(*p) & mask)
-		return 1;
-
 	old = arch_atomic_long_fetch_or(mask, (atomic_long_t *)p);
 	return !!(old & mask);
 }
@@ -53,9 +50,6 @@ arch_test_and_clear_bit(unsigned int nr, volatile unsigned long *p)
 	unsigned long mask = BIT_MASK(nr);
 
Quoted 11 lines

include/asm-generic/bitops/atomic.h arch_test_and_clear_bit(unsigned int nr, volatile unsigned long *p) · line 54

Quoted 6 lines
include/asm-generic/bitops/atomic.h +0 -3
 	p += BIT_WORD(nr);
-	if (!(READ_ONCE(*p) & mask))
-		return 0;
-
 	old = arch_atomic_long_fetch_andnot(mask, (atomic_long_t *)p);
 	return !!(old & mask);

I suppose one sad thing about this is that, on arm64, we could reasonably keep the READ_ONCE() path with a DMB LD (R->RW) barrier before the return but I don't think we can express that in the Linux memory model so we end up in RmW territory every time.

Quoted 5 lines

You'd need a barrier *before* the READ_ONCE(), since what we're trying to prevent is a consumer from writing to the value without being able to observe the writes that happened prior, while this side read the old value. A barrier after the READ_ONCE() doesn't do anything, as that read is the last memory operation in this thread (of the problematic sequence).

Right, having gone back to your litmus test, I now realise it's the "SB" shape from the memory ordering terminology. It's funny because the arm64 acquire/release instructions are RCsc and so upgrading the READ_ONCE() to an *arm64* acquire instruction would work for your specific case, but only because the preceeding store is a release.

Quoted 2 lines

At that point, I'm not sure DMB LD / early read / LSE atomic would be any faster than just always doing the LSE atomic?

It depends a lot on the configuration of the system and the state of the relevant cacheline, but generally avoiding an RmW by introducing a barrier is likely to be a win. It just gets ugly here as we'd want to avoid the DMB in the case where we end up doing the RmW. Possibly we could do something funky like a test-and-test-and-test-and-set (!) where we do the DMB+READ_ONCE() only if the first READ_ONCE() has the bit set, but even just typing that is horrible and I'd _absolutely_ want to see perf numbers to show that it's a benefit once you start taking into account things like branch prediction.

Anywho, since Linus has applied the patch and it should work, this is just an interesting aside.

Will

#11 lore raw
Quoted 57 lines · Will Deacon
Quoted 30 lines · Hector Martin
Quoted 17 lines · Will Deacon
Quoted 17 lines
include/asm-generic/bitops/atomic.h +0 -3
index 3096f086b5a3..71ab4ba9c25d 100644
@@ -39,9 +39,6 @@ arch_test_and_set_bit(unsigned int nr, volatile unsigned long *p)
   unsigned long mask = BIT_MASK(nr);
 
   p += BIT_WORD(nr);
-  if (READ_ONCE(*p) & mask)
-          return 1;
-
   old = arch_atomic_long_fetch_or(mask, (atomic_long_t *)p);
   return !!(old & mask);
 }
@@ -53,9 +50,6 @@ arch_test_and_clear_bit(unsigned int nr, volatile unsigned long *p)
   unsigned long mask = BIT_MASK(nr);
 
Quoted 11 lines

include/asm-generic/bitops/atomic.h arch_test_and_clear_bit(unsigned int nr, volatile unsigned long *p) · line 54

Quoted 6 lines
include/asm-generic/bitops/atomic.h +0 -3
   p += BIT_WORD(nr);
-  if (!(READ_ONCE(*p) & mask))
-          return 0;
-
   old = arch_atomic_long_fetch_andnot(mask, (atomic_long_t *)p);
   return !!(old & mask);

I suppose one sad thing about this is that, on arm64, we could reasonably keep the READ_ONCE() path with a DMB LD (R->RW) barrier before the return but I don't think we can express that in the Linux memory model so we end up in RmW territory every time.

Quoted 5 lines

You'd need a barrier *before* the READ_ONCE(), since what we're trying to prevent is a consumer from writing to the value without being able to observe the writes that happened prior, while this side read the old value. A barrier after the READ_ONCE() doesn't do anything, as that read is the last memory operation in this thread (of the problematic sequence).

Right, having gone back to your litmus test, I now realise it's the "SB" shape from the memory ordering terminology. It's funny because the arm64 acquire/release instructions are RCsc and so upgrading the READ_ONCE() to an *arm64* acquire instruction would work for your specific case, but only because the preceeding store is a release.

Quoted 2 lines

At that point, I'm not sure DMB LD / early read / LSE atomic would be any faster than just always doing the LSE atomic?

It depends a lot on the configuration of the system and the state of the relevant cacheline, but generally avoiding an RmW by introducing a barrier is likely to be a win. It just gets ugly here as we'd want to avoid the DMB in the case where we end up doing the RmW. Possibly we could do something funky like a test-and-test-and-test-and-set (!) where we do the DMB+READ_ONCE() only if the first READ_ONCE() has the bit set, but even just typing that is horrible and I'd _absolutely_ want to see perf numbers to show that it's a benefit once you start taking into account things like branch prediction.

Quoted 5 lines

Anywho, since Linus has applied the patch and it should work, this is just an interesting aside.

Will

It is moot if Linus has already taken the patch, but with a stock kernel config I am
still seeing a slight performance dip but only ~1-2% in the specific tests I was running.
Sorry about the noise I will need to look at my kernel builder and see what went wrong when I have more time.

Cheers,
Jon

#12 lore raw
Quoted 5 lines · Jon Nettleton

It is moot if Linus has already taken the patch, but with a stock kernel config I am
still seeing a slight performance dip but only ~1-2% in the specific tests I was running.

It would be interesting to hear if you can pinpoint in the profiles where the time is spent.

It might be some random place that really doesn't care about ordering at all, and then we could easily rewrite _that_ particular case to do the unordered test explicitly, ie something like

- if (test_and_set_bit()) ...
+ if (test_bit() || test_and_set_bit()) ...

or even introduce an explicitly unordered "test_and_set_bit_relaxed()" thing.

Linus

#13 lore raw
Quoted 18 lines · Linus Torvalds
Quoted 5 lines · Jon Nettleton

It is moot if Linus has already taken the patch, but with a stock kernel config I am
still seeing a slight performance dip but only ~1-2% in the specific tests I was running.

It would be interesting to hear if you can pinpoint in the profiles where the time is spent.

It might be some random place that really doesn't care about ordering at all, and then we could easily rewrite _that_ particular case to do the unordered test explicitly, ie something like

(quoted diff) +1 -1
-        if (test_and_set_bit()) ...
+       if (test_bit() || test_and_set_bit()) ...
Quoted 3 lines

or even introduce an explicitly unordered "test_and_set_bit_relaxed()" thing.

Linus

This is very interesting, the additional performance overhead doesn't seem to be coming from within the kernel but from userspace. Comparing patched and unpatched kernels I am seeing more cycles being taken up by glibc atomics like __aarch64_cas4_acq and __aarch64_ldadd4_acq_rel.

I need to test further to see if there is less effect on a system with less cores,
This is a 16-core Cortex-A72, it is possible this is less of an issue on 4 core A72's and A53's.

-Jon

#14 lore raw
In reply to Hector Martin

...

include/asm-generic/bitops/atomic.h arch_test_and_set_bit(unsigned int nr, volatile unsigned long *p) · line 44

Quoted 7 lines
include/asm-generic/bitops/atomic.h +0 -3
 	p += BIT_WORD(nr);
-	if (READ_ONCE(*p) & mask)
-		return 1;
-
 	old = arch_atomic_long_fetch_or(mask, (atomic_long_t *)p);
 	return !!(old & mask);
 }

This looks like the same pattern (attempting to avoid a locked bus cycle) that caused the qdisc code to sit on transmit packets (even on x86).
That had some barriers in it (possibly nops on x86) that didn't help - although the comments suggested otherwise.

I wonder if the pattern has been used anywhere else?

David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)