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

Groups > linux.kernel > #1494222 > unrolled thread

[RFC] arm64: Enforce observed order for spinlock and data

Back to article view | Back to linux.kernel

Contents

  [RFC] arm64: Enforce observed order for spinlock and data Brent DeGraaf <bdegraaf@codeaurora.org> - 2016-09-30 19:50 +0200
    Re: [RFC] arm64: Enforce observed order for spinlock and data Robin Murphy <robin.murphy@arm.com> - 2016-09-30 20:50 +0200
      Re: [RFC] arm64: Enforce observed order for spinlock and data bdegraaf@codeaurora.org - 2016-10-01 17:50 +0200
    Re: [RFC] arm64: Enforce observed order for spinlock and data Peter Zijlstra <peterz@infradead.org> - 2016-09-30 21:00 +0200
    Re: [RFC] arm64: Enforce observed order for spinlock and data Peter Zijlstra <peterz@infradead.org> - 2016-09-30 21:10 +0200
      Re: [RFC] arm64: Enforce observed order for spinlock and data bdegraaf@codeaurora.org - 2016-10-01 18:10 +0200
    Re: [RFC] arm64: Enforce observed order for spinlock and data Mark Rutland <mark.rutland@arm.com> - 2016-09-30 21:40 +0200
      Re: [RFC] arm64: Enforce observed order for spinlock and data bdegraaf@codeaurora.org - 2016-10-01 18:20 +0200
        Re: [RFC] arm64: Enforce observed order for spinlock and data Mark Rutland <mark.rutland@arm.com> - 2016-10-01 20:20 +0200
          Re: [RFC] arm64: Enforce observed order for spinlock and data bdegraaf@codeaurora.org - 2016-10-03 21:30 +0200
            Re: [RFC] arm64: Enforce observed order for spinlock and data Peter Zijlstra <peterz@infradead.org> - 2016-10-04 09:00 +0200
            Re: [RFC] arm64: Enforce observed order for spinlock and data Mark Rutland <mark.rutland@arm.com> - 2016-10-04 12:20 +0200
              Re: [RFC] arm64: Enforce observed order for spinlock and data bdegraaf@codeaurora.org - 2016-10-04 20:00 +0200
                Re: [RFC] arm64: Enforce observed order for spinlock and data bdegraaf@codeaurora.org - 2016-10-04 20:30 +0200
                Re: [RFC] arm64: Enforce observed order for spinlock and data Mark Rutland <mark.rutland@arm.com> - 2016-10-04 21:20 +0200
                  Re: [RFC] arm64: Enforce observed order for spinlock and data bdegraaf@codeaurora.org - 2016-10-05 17:00 +0200
                    Re: [RFC] arm64: Enforce observed order for spinlock and data bdegraaf@codeaurora.org - 2016-10-05 17:20 +0200
                    Re: [RFC] arm64: Enforce observed order for spinlock and data Peter Zijlstra <peterz@infradead.org> - 2016-10-05 17:20 +0200
                      Re: [RFC] arm64: Enforce observed order for spinlock and data bdegraaf@codeaurora.org - 2016-10-05 17:40 +0200
                        Re: [RFC] arm64: Enforce observed order for spinlock and data bdegraaf@codeaurora.org - 2016-10-12 22:10 +0200
                          Re: [RFC] arm64: Enforce observed order for spinlock and data Will Deacon <will.deacon@arm.com> - 2016-10-13 13:20 +0200
                            Re: [RFC] arm64: Enforce observed order for spinlock and data bdegraaf@codeaurora.org - 2016-10-13 22:10 +0200
                              Re: [RFC] arm64: Enforce observed order for spinlock and data Mark Rutland <mark.rutland@arm.com> - 2016-10-14 02:30 +0200

Page 1 of 2  [1] 2  Next page →

#1494222 — [RFC] arm64: Enforce observed order for spinlock and data

Prior spinlock code solely used load-acquire and store-release
semantics to ensure ordering of the spinlock lock and the area it
protects. However, store-release semantics and ordinary stores do
not protect against accesses to the protected area being observed
prior to the access that locks the lock itself.

While the load-acquire and store-release ordering is sufficient
when the spinlock routines themselves are strictly used, other
kernel code that references the lock values directly (e.g. lockrefs)
could observe changes to the area protected by the spinlock prior
to observance of the lock itself being in a locked state, despite
the fact that the spinlock logic itself is correct.

Barriers were added to all the locking routines wherever necessary
to ensure that outside observers which read the lock values directly
will not observe changes to the protected data before the lock itself
is observed.

Signed-off-by: Brent DeGraaf <bdegraaf@codeaurora.org>
---
 arch/arm64/include/asm/spinlock.h | 59 ++++++++++++++++++++++++++++++++++++---
 1 file changed, 55 insertions(+), 4 deletions(-)

diff --git a/arch/arm64/include/asm/spinlock.h b/arch/arm64/include/asm/spinlock.h
index 89206b5..4dd0977 100644
--- a/arch/arm64/include/asm/spinlock.h
+++ b/arch/arm64/include/asm/spinlock.h
@@ -106,7 +106,20 @@ static inline void arch_spin_lock(arch_spinlock_t *lock)
 
 	/* Did we get the lock? */
 "	eor	%w1, %w0, %w0, ror #16\n"
-"	cbz	%w1, 3f\n"
+"	cbnz	%w1, 4f\n"
+	/*
+	 * Yes: The store done on this cpu was the one that locked the lock.
+	 * Store-release one-way barrier on LL/SC means that accesses coming
+	 * after this could be reordered into the critical section of the
+	 * load-acquire/store-release, where we did not own the lock. On LSE,
+	 * even the one-way barrier of the store-release semantics is missing,
+	 * so LSE needs an explicit barrier here as well.  Without this, the
+	 * changed contents of the area protected by the spinlock could be
+	 * observed prior to the lock.
+	 */
+"	dmb	ish\n"
+"	b	3f\n"
+"4:\n"
 	/*
 	 * No: spin on the owner. Send a local event to avoid missing an
 	 * unlock before the exclusive load.
@@ -116,7 +129,15 @@ static inline void arch_spin_lock(arch_spinlock_t *lock)
 "	ldaxrh	%w2, %4\n"
 "	eor	%w1, %w2, %w0, lsr #16\n"
 "	cbnz	%w1, 2b\n"
-	/* We got the lock. Critical section starts here. */
+	/*
+	 * We got the lock and have observed the prior owner's store-release.
+	 * In this case, the one-way barrier of the prior owner that we
+	 * observed combined with the one-way barrier of our load-acquire is
+	 * enough to ensure accesses to the protected area coming after this
+	 * are not accessed until we own the lock.  In this case, other
+	 * observers will not see our changes prior to observing the lock
+	 * itself.  Critical locked section starts here.
+	 */
 "3:"
 	: "=&r" (lockval), "=&r" (newval), "=&r" (tmp), "+Q" (*lock)
 	: "Q" (lock->owner), "I" (1 << TICKET_SHIFT)
@@ -137,6 +158,13 @@ static inline int arch_spin_trylock(arch_spinlock_t *lock)
 	"	add	%w0, %w0, %3\n"
 	"	stxr	%w1, %w0, %2\n"
 	"	cbnz	%w1, 1b\n"
+	/*
+	 * We got the lock with a successful store-release: Store-release
+	 * one-way barrier means accesses coming after this could be observed
+	 * before the lock is observed as locked.
+	 */
+	"	dmb	ish\n"
+	"	nop\n"
 	"2:",
 	/* LSE atomics */
 	"	ldr	%w0, %2\n"
@@ -146,6 +174,13 @@ static inline int arch_spin_trylock(arch_spinlock_t *lock)
 	"	casa	%w0, %w1, %2\n"
 	"	and	%w1, %w1, #0xffff\n"
 	"	eor	%w1, %w1, %w0, lsr #16\n"
+	"	cbnz	%w1, 1f\n"
+	/*
+	 * We got the lock with the LSE casa store.
+	 * A barrier is required to ensure accesses coming from the
+	 * critical section of the lock are not observed before our lock.
+	 */
+	"	dmb	ish\n"
 	"1:")
 	: "=&r" (lockval), "=&r" (tmp), "+Q" (*lock)
 	: "I" (1 << TICKET_SHIFT)
@@ -212,6 +247,12 @@ static inline void arch_write_lock(arch_rwlock_t *rw)
 	"	cbnz	%w0, 1b\n"
 	"	stxr	%w0, %w2, %1\n"
 	"	cbnz	%w0, 2b\n"
+	/*
+	 * Lock is not ours until the store, which has no implicit barrier.
+	 * Barrier is needed so our writes to the protected area are not
+	 * observed before our lock ownership is observed.
+	 */
+	"	dmb	ish\n"
 	"	nop",
 	/* LSE atomics */
 	"1:	mov	%w0, wzr\n"
@@ -221,7 +262,12 @@ static inline void arch_write_lock(arch_rwlock_t *rw)
 	"	cbz	%w0, 2b\n"
 	"	wfe\n"
 	"	b	1b\n"
-	"3:")
+	/*
+	 * Casa doesn't use store-release semantics. Even if it did,
+	 * it would not protect us from our writes being observed before
+	 * our ownership is observed. Barrier is required.
+	 */
+	"3:	dmb	ish")
 	: "=&r" (tmp), "+Q" (rw->lock)
 	: "r" (0x80000000)
 	: "memory");
@@ -299,7 +345,12 @@ static inline void arch_read_lock(arch_rwlock_t *rw)
 	"	tbnz	%w1, #31, 1b\n"
 	"	casa	%w0, %w1, %2\n"
 	"	sbc	%w0, %w1, %w0\n"
-	"	cbnz	%w0, 2b")
+	"	cbnz	%w0, 2b\n"
+	/*
+	 * Need to ensure that our reads of the area protected by the lock
+	 * are not observed before our lock ownership is observed.
+	 */
+	"	dmb	ish\n")
 	: "=&r" (tmp), "=&r" (tmp2), "+Q" (rw->lock)
 	:
 	: "cc", "memory");
-- 
Qualcomm Datacenter Technologies, Inc. as an affiliate of Qualcomm
Technologies, Inc. Qualcomm Technologies, Inc. is a member of the Code Aurora
Forum, a Linux Foundation Collaborative Project.

[toc] | [next] | [standalone]

#1494231

Hi Brent,

On 30/09/16 18:40, Brent DeGraaf wrote:
> Prior spinlock code solely used load-acquire and store-release
> semantics to ensure ordering of the spinlock lock and the area it
> protects. However, store-release semantics and ordinary stores do
> not protect against accesses to the protected area being observed
> prior to the access that locks the lock itself.
> 
> While the load-acquire and store-release ordering is sufficient
> when the spinlock routines themselves are strictly used, other
> kernel code that references the lock values directly (e.g. lockrefs)
> could observe changes to the area protected by the spinlock prior
> to observance of the lock itself being in a locked state, despite
> the fact that the spinlock logic itself is correct.
> 
> Barriers were added to all the locking routines wherever necessary
> to ensure that outside observers which read the lock values directly
> will not observe changes to the protected data before the lock itself
> is observed.
> 
> Signed-off-by: Brent DeGraaf <bdegraaf@codeaurora.org>
> ---
>  arch/arm64/include/asm/spinlock.h | 59 ++++++++++++++++++++++++++++++++++++---
>  1 file changed, 55 insertions(+), 4 deletions(-)
> 
> diff --git a/arch/arm64/include/asm/spinlock.h b/arch/arm64/include/asm/spinlock.h
> index 89206b5..4dd0977 100644
> --- a/arch/arm64/include/asm/spinlock.h
> +++ b/arch/arm64/include/asm/spinlock.h
> @@ -106,7 +106,20 @@ static inline void arch_spin_lock(arch_spinlock_t *lock)
>  
>  	/* Did we get the lock? */
>  "	eor	%w1, %w0, %w0, ror #16\n"
> -"	cbz	%w1, 3f\n"
> +"	cbnz	%w1, 4f\n"
> +	/*
> +	 * Yes: The store done on this cpu was the one that locked the lock.
> +	 * Store-release one-way barrier on LL/SC means that accesses coming
> +	 * after this could be reordered into the critical section of the
> +	 * load-acquire/store-release, where we did not own the lock. On LSE,
> +	 * even the one-way barrier of the store-release semantics is missing,
> +	 * so LSE needs an explicit barrier here as well.  Without this, the
> +	 * changed contents of the area protected by the spinlock could be
> +	 * observed prior to the lock.

What is that last sentence supposed to mean? If the lock is free, then
surely any previous writes to the data it's protecting would have
already been observed by the release semantics of the previous unlock?
If the lock is currently held, what do we care about the state of the
data while we're still spinning on the lock itself? And if someone's
touching the data without having acquired *or* released the lock, why is
there a lock in the first place?

This seems like a very expensive way of papering over broken callers :/

Robin.

> +	 */
> +"	dmb	ish\n"
> +"	b	3f\n"
> +"4:\n"
>  	/*
>  	 * No: spin on the owner. Send a local event to avoid missing an
>  	 * unlock before the exclusive load.
> @@ -116,7 +129,15 @@ static inline void arch_spin_lock(arch_spinlock_t *lock)
>  "	ldaxrh	%w2, %4\n"
>  "	eor	%w1, %w2, %w0, lsr #16\n"
>  "	cbnz	%w1, 2b\n"
> -	/* We got the lock. Critical section starts here. */
> +	/*
> +	 * We got the lock and have observed the prior owner's store-release.
> +	 * In this case, the one-way barrier of the prior owner that we
> +	 * observed combined with the one-way barrier of our load-acquire is
> +	 * enough to ensure accesses to the protected area coming after this
> +	 * are not accessed until we own the lock.  In this case, other
> +	 * observers will not see our changes prior to observing the lock
> +	 * itself.  Critical locked section starts here.
> +	 */
>  "3:"
>  	: "=&r" (lockval), "=&r" (newval), "=&r" (tmp), "+Q" (*lock)
>  	: "Q" (lock->owner), "I" (1 << TICKET_SHIFT)
> @@ -137,6 +158,13 @@ static inline int arch_spin_trylock(arch_spinlock_t *lock)
>  	"	add	%w0, %w0, %3\n"
>  	"	stxr	%w1, %w0, %2\n"
>  	"	cbnz	%w1, 1b\n"
> +	/*
> +	 * We got the lock with a successful store-release: Store-release
> +	 * one-way barrier means accesses coming after this could be observed
> +	 * before the lock is observed as locked.
> +	 */
> +	"	dmb	ish\n"
> +	"	nop\n"
>  	"2:",
>  	/* LSE atomics */
>  	"	ldr	%w0, %2\n"
> @@ -146,6 +174,13 @@ static inline int arch_spin_trylock(arch_spinlock_t *lock)
>  	"	casa	%w0, %w1, %2\n"
>  	"	and	%w1, %w1, #0xffff\n"
>  	"	eor	%w1, %w1, %w0, lsr #16\n"
> +	"	cbnz	%w1, 1f\n"
> +	/*
> +	 * We got the lock with the LSE casa store.
> +	 * A barrier is required to ensure accesses coming from the
> +	 * critical section of the lock are not observed before our lock.
> +	 */
> +	"	dmb	ish\n"
>  	"1:")
>  	: "=&r" (lockval), "=&r" (tmp), "+Q" (*lock)
>  	: "I" (1 << TICKET_SHIFT)
> @@ -212,6 +247,12 @@ static inline void arch_write_lock(arch_rwlock_t *rw)
>  	"	cbnz	%w0, 1b\n"
>  	"	stxr	%w0, %w2, %1\n"
>  	"	cbnz	%w0, 2b\n"
> +	/*
> +	 * Lock is not ours until the store, which has no implicit barrier.
> +	 * Barrier is needed so our writes to the protected area are not
> +	 * observed before our lock ownership is observed.
> +	 */
> +	"	dmb	ish\n"
>  	"	nop",
>  	/* LSE atomics */
>  	"1:	mov	%w0, wzr\n"
> @@ -221,7 +262,12 @@ static inline void arch_write_lock(arch_rwlock_t *rw)
>  	"	cbz	%w0, 2b\n"
>  	"	wfe\n"
>  	"	b	1b\n"
> -	"3:")
> +	/*
> +	 * Casa doesn't use store-release semantics. Even if it did,
> +	 * it would not protect us from our writes being observed before
> +	 * our ownership is observed. Barrier is required.
> +	 */
> +	"3:	dmb	ish")
>  	: "=&r" (tmp), "+Q" (rw->lock)
>  	: "r" (0x80000000)
>  	: "memory");
> @@ -299,7 +345,12 @@ static inline void arch_read_lock(arch_rwlock_t *rw)
>  	"	tbnz	%w1, #31, 1b\n"
>  	"	casa	%w0, %w1, %2\n"
>  	"	sbc	%w0, %w1, %w0\n"
> -	"	cbnz	%w0, 2b")
> +	"	cbnz	%w0, 2b\n"
> +	/*
> +	 * Need to ensure that our reads of the area protected by the lock
> +	 * are not observed before our lock ownership is observed.
> +	 */
> +	"	dmb	ish\n")
>  	: "=&r" (tmp), "=&r" (tmp2), "+Q" (rw->lock)
>  	:
>  	: "cc", "memory");
> 

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

#1494431

On 2016-09-30 14:43, Robin Murphy wrote:
>> +	 * so LSE needs an explicit barrier here as well.  Without this, the
>> +	 * changed contents of the area protected by the spinlock could be
>> +	 * observed prior to the lock.
> 
> What is that last sentence supposed to mean? If the lock is free, then
> surely any previous writes to the data it's protecting would have
> already been observed by the release semantics of the previous unlock?
> If the lock is currently held, what do we care about the state of the
> data while we're still spinning on the lock itself? And if someone's
> touching the data without having acquired *or* released the lock, why 
> is
> there a lock in the first place?
> 
> This seems like a very expensive way of papering over broken callers :/
> 
> Robin.
> 

Thanks for your question.

First off, I saw no negative impact to performance as a result of 
introducing
these barriers running a wide variety of use cases, both for mobile and
server-class devices ranging from 4 to 24 cpus.

Yes, it does protect lockref, which observes the spinlocks in a 
non-conventional
way.  In fact, with this code in place, the performance of Linus' test 
which runs
stat like crazy actually improved in the range of 1-2% (I suspect this 
is due to
fewer failures due to contention on the protected count lockref uses).

The lockref code can be made compliant, but not by a single 
load-acquire--it has
to take the lock.  Turning off CONFIG_ARCH_USE_CMPXCHG_LOCKREF is the 
most
obvious solution as it forces lockref.c to take the lock.  That, 
however, comes
at a very high performance cost: 30-50% on Linus' stat test on a 24-core 
system.
For larger systems, this performance gap will get even worse.

With the above in mind, it seems that supporting lockref's unorthodox 
method of
dealing with the lock is the better alternative, as it helps, rather 
than hurts,
arm64 performance.

Brent

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

#1494235

On Fri, Sep 30, 2016 at 01:40:57PM -0400, Brent DeGraaf wrote:
> Prior spinlock code solely used load-acquire and store-release
> semantics to ensure ordering of the spinlock lock and the area it
> protects. However, store-release semantics and ordinary stores do
> not protect against accesses to the protected area being observed
> prior to the access that locks the lock itself.
> 
> While the load-acquire and store-release ordering is sufficient
> when the spinlock routines themselves are strictly used, other
> kernel code that references the lock values directly (e.g. lockrefs)
> could observe changes to the area protected by the spinlock prior
> to observance of the lock itself being in a locked state, despite
> the fact that the spinlock logic itself is correct.
> 
> Barriers were added to all the locking routines wherever necessary
> to ensure that outside observers which read the lock values directly
> will not observe changes to the protected data before the lock itself
> is observed.

I cannot see this going in. You're making spinlocks far more expensive
in the common case that doesn't need this.

Please enumerate the special cases (there's more than just lockref?) and
fix those.

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

#1494242

On Fri, Sep 30, 2016 at 01:40:57PM -0400, Brent DeGraaf wrote:
> Prior spinlock code solely used load-acquire and store-release
> semantics to ensure ordering of the spinlock lock and the area it
> protects. However, store-release semantics and ordinary stores do
> not protect against accesses to the protected area being observed
> prior to the access that locks the lock itself.
> 
> While the load-acquire and store-release ordering is sufficient
> when the spinlock routines themselves are strictly used, other
> kernel code that references the lock values directly (e.g. lockrefs)

Isn't the problem with lockref the fact that arch_spin_value_unlocked()
isn't a load-acquire, and therefore the CPU in question doesn't need to
observe the contents of the critical section etc..?

That is, wouldn't fixing arch_spin_value_unlocked() by making that an
smp_load_acquire() fix things much better?

> could observe changes to the area protected by the spinlock prior
> to observance of the lock itself being in a locked state, despite
> the fact that the spinlock logic itself is correct.

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

#1494433

On 2016-09-30 15:05, Peter Zijlstra wrote:
> On Fri, Sep 30, 2016 at 01:40:57PM -0400, Brent DeGraaf wrote:
>> Prior spinlock code solely used load-acquire and store-release
>> semantics to ensure ordering of the spinlock lock and the area it
>> protects. However, store-release semantics and ordinary stores do
>> not protect against accesses to the protected area being observed
>> prior to the access that locks the lock itself.
>> 
>> While the load-acquire and store-release ordering is sufficient
>> when the spinlock routines themselves are strictly used, other
>> kernel code that references the lock values directly (e.g. lockrefs)
> 
> Isn't the problem with lockref the fact that arch_spin_value_unlocked()
> isn't a load-acquire, and therefore the CPU in question doesn't need to
> observe the contents of the critical section etc..?
> 
> That is, wouldn't fixing arch_spin_value_unlocked() by making that an
> smp_load_acquire() fix things much better?
> 
>> could observe changes to the area protected by the spinlock prior
>> to observance of the lock itself being in a locked state, despite
>> the fact that the spinlock logic itself is correct.

Thanks for your comments.

The load-acquire would not be enough for lockref, as it can still 
observe
the changed data out of order. To ensure order, lockref has to take the
lock, which comes at a high performance cost.  Turning off the config
option CONFIG_ARCH_USE_CMPXCHG_LOCKREF, which forces arch_spin_lock 
calls
reduced my multicore performance between 30 and 50 percent using Linus'
"stat" test that was part of the grounds for introducing lockref.

On the other hand, I did not see any negative impact to performance by
the new barriers, in large part probably because they only tend to come
into play when locks are not heavily contended in the case of ticket
locks.

I have not yet found any other spinlock "abuses" in the kernel besides
lockref, but locks are referenced in a large number of places that
includes drivers, which are dynamic.  It is arguable that I could remove
the barriers to the read/write locks, as lockref doesn't use those, but
it seemed to me to be safer and more "normal" to ensure that the locked
write to the lock itself is visible prior to the changed contents of the
protected area.

Brent

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

#1494256

On Fri, Sep 30, 2016 at 01:40:57PM -0400, Brent DeGraaf wrote:
> Prior spinlock code solely used load-acquire and store-release
> semantics to ensure ordering of the spinlock lock and the area it
> protects. However, store-release semantics and ordinary stores do
> not protect against accesses to the protected area being observed
> prior to the access that locks the lock itself.
> 
> While the load-acquire and store-release ordering is sufficient
> when the spinlock routines themselves are strictly used, other
> kernel code that references the lock values directly (e.g. lockrefs)
> could observe changes to the area protected by the spinlock prior
> to observance of the lock itself being in a locked state, despite
> the fact that the spinlock logic itself is correct.

If the spinlock logic is correct, why are we changing that, and not the lockref
code that you say has a problem?

What exactly goes wrong in the lockref code? Can you give a concrete example?

Why does the lockref code accesses lock-protected fields without taking the
lock first? Wouldn't concurrent modification be a problem regardless?

> +	/*
> +	 * Yes: The store done on this cpu was the one that locked the lock.
> +	 * Store-release one-way barrier on LL/SC means that accesses coming
> +	 * after this could be reordered into the critical section of the

I assume you meant s/store-release/load-acquire/ here. This does not make sense
to me otherwise.

> +	 * load-acquire/store-release, where we did not own the lock. On LSE,
> +	 * even the one-way barrier of the store-release semantics is missing,

Likewise (for the LSE case description).

> +	 * so LSE needs an explicit barrier here as well.  Without this, the
> +	 * changed contents of the area protected by the spinlock could be
> +	 * observed prior to the lock.
> +	 */

By whom? We generally expect that if data is protected by a lock, you take the
lock before accessing it. If you expect concurrent lockless readers, then
there's a requirement on the writer side to explicitly provide the ordering it
requires -- spinlocks are not expected to provide that.

So, why aren't those observers taking the lock?

What pattern of accesses are made by readers and writers such that there is a
problem?

What does this result in?

> +"	dmb	ish\n"
> +"	b	3f\n"
> +"4:\n"
>  	/*
>  	 * No: spin on the owner. Send a local event to avoid missing an
>  	 * unlock before the exclusive load.
> @@ -116,7 +129,15 @@ static inline void arch_spin_lock(arch_spinlock_t *lock)
>  "	ldaxrh	%w2, %4\n"
>  "	eor	%w1, %w2, %w0, lsr #16\n"
>  "	cbnz	%w1, 2b\n"
> -	/* We got the lock. Critical section starts here. */
> +	/*
> +	 * We got the lock and have observed the prior owner's store-release.
> +	 * In this case, the one-way barrier of the prior owner that we
> +	 * observed combined with the one-way barrier of our load-acquire is
> +	 * enough to ensure accesses to the protected area coming after this
> +	 * are not accessed until we own the lock.  In this case, other
> +	 * observers will not see our changes prior to observing the lock
> +	 * itself.  Critical locked section starts here.
> +	 */

Each of these comments ends up covers, and their repeated presence makes the
code harder to read. If there's a common problem, note it once at the top of
the file.

Thanks,
Mark.

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

#1494435

On 2016-09-30 15:32, Mark Rutland wrote:
> On Fri, Sep 30, 2016 at 01:40:57PM -0400, Brent DeGraaf wrote:
>> Prior spinlock code solely used load-acquire and store-release
>> semantics to ensure ordering of the spinlock lock and the area it
>> protects. However, store-release semantics and ordinary stores do
>> not protect against accesses to the protected area being observed
>> prior to the access that locks the lock itself.
>> 
>> While the load-acquire and store-release ordering is sufficient
>> when the spinlock routines themselves are strictly used, other
>> kernel code that references the lock values directly (e.g. lockrefs)
>> could observe changes to the area protected by the spinlock prior
>> to observance of the lock itself being in a locked state, despite
>> the fact that the spinlock logic itself is correct.
> 
> If the spinlock logic is correct, why are we changing that, and not the 
> lockref
> code that you say has a problem?
> 
> What exactly goes wrong in the lockref code? Can you give a concrete 
> example?
> 
> Why does the lockref code accesses lock-protected fields without taking 
> the
> lock first? Wouldn't concurrent modification be a problem regardless?
> 
>> +	/*
>> +	 * Yes: The store done on this cpu was the one that locked the lock.
>> +	 * Store-release one-way barrier on LL/SC means that accesses coming
>> +	 * after this could be reordered into the critical section of the
> 
> I assume you meant s/store-release/load-acquire/ here. This does not 
> make sense
> to me otherwise.
> 
>> +	 * load-acquire/store-release, where we did not own the lock. On 
>> LSE,
>> +	 * even the one-way barrier of the store-release semantics is 
>> missing,
> 
> Likewise (for the LSE case description).
> 
>> +	 * so LSE needs an explicit barrier here as well.  Without this, the
>> +	 * changed contents of the area protected by the spinlock could be
>> +	 * observed prior to the lock.
>> +	 */
> 
> By whom? We generally expect that if data is protected by a lock, you 
> take the
> lock before accessing it. If you expect concurrent lockless readers, 
> then
> there's a requirement on the writer side to explicitly provide the 
> ordering it
> requires -- spinlocks are not expected to provide that.
More details are in my response to Robin, but there is an API arm64 
supports
in spinlock.h which is used by lockref to determine whether a lock is 
free or not.
For that code to work properly without adding these barriers, that API 
needs to
take the lock.  I tested that configuration, and it cost us heavily in 
terms of
lockref performance in the form of a 30 to 50 percent performance loss.  
On the
other hand, I have not seen any performance degradation due to the 
introduction
of these barriers.

> 
> So, why aren't those observers taking the lock?

lockref doesn't take the lock specifically because it is slower.

> 
> What pattern of accesses are made by readers and writers such that 
> there is a
> problem?

I added the barriers to the readers/writers because I do not know these 
are not
similarly abused.  There is a lot of driver code out there, and ensuring 
order is
the safest way to be sure we don't get burned by something similar to 
the lockref
access.

> 
> What does this result in?
> 
No measureable negative performance impact.  However, the lockref 
performance actually
improved slightly (between 1 and 2 percent on my 24-core test system) 
due to the change.

>> +"	dmb	ish\n"
>> +"	b	3f\n"
>> +"4:\n"
>>  	/*
>>  	 * No: spin on the owner. Send a local event to avoid missing an
>>  	 * unlock before the exclusive load.
>> @@ -116,7 +129,15 @@ static inline void arch_spin_lock(arch_spinlock_t 
>> *lock)
>>  "	ldaxrh	%w2, %4\n"
>>  "	eor	%w1, %w2, %w0, lsr #16\n"
>>  "	cbnz	%w1, 2b\n"
>> -	/* We got the lock. Critical section starts here. */
>> +	/*
>> +	 * We got the lock and have observed the prior owner's 
>> store-release.
>> +	 * In this case, the one-way barrier of the prior owner that we
>> +	 * observed combined with the one-way barrier of our load-acquire is
>> +	 * enough to ensure accesses to the protected area coming after this
>> +	 * are not accessed until we own the lock.  In this case, other
>> +	 * observers will not see our changes prior to observing the lock
>> +	 * itself.  Critical locked section starts here.
>> +	 */
> 
> Each of these comments ends up covers, and their repeated presence 
> makes the
> code harder to read. If there's a common problem, note it once at the 
> top of
> the file.

I added these comments to make it crystal clear that the absence of a 
barrier at this
point was deliberate, and that I did consider each code path.

> 
> Thanks,
> Mark.

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

#1494454

Hi Brent,

Evidently my questions weren't sufficiently clear; even with your answers it's
not clear to me what precise issue you're attempting to solve. I've tried to be
more specific this time.

At a high-level, can you clarify whether you're attempting to solve is:

(a) a functional correctness issue (e.g. data corruption) 
(b) a performance issue

And whether this was seen in practice, or found through code inspection?

On Sat, Oct 01, 2016 at 12:11:36PM -0400, bdegraaf@codeaurora.org wrote:
> On 2016-09-30 15:32, Mark Rutland wrote:
> >On Fri, Sep 30, 2016 at 01:40:57PM -0400, Brent DeGraaf wrote:
> >>+	 * so LSE needs an explicit barrier here as well.  Without this, the
> >>+	 * changed contents of the area protected by the spinlock could be
> >>+	 * observed prior to the lock.
> >>+	 */
> >
> >By whom? We generally expect that if data is protected by a lock, you take
> >the lock before accessing it. If you expect concurrent lockless readers,
> >then there's a requirement on the writer side to explicitly provide the
> >ordering it requires -- spinlocks are not expected to provide that.
>
> More details are in my response to Robin, but there is an API arm64 supports
> in spinlock.h which is used by lockref to determine whether a lock is free or
> not.  For that code to work properly without adding these barriers, that API
> needs to take the lock.

Can you please provide a concrete example of a case where things go wrong,
citing the code (or access pattern) in question? e.g. as in the commit messages
for:

  8e86f0b409a44193 ("arm64: atomics: fix use of acquire + release for full barrier semantics)
  859b7a0e89120505 ("mm/slub: fix lockups on PREEMPT && !SMP kernels")

(for the latter, I messed up the register -> var mapping in one paragraph, but
the style and reasoning is otherwise sound).

In the absence of a concrete example as above, it's very difficult to reason
about what the underlying issue is, and what a valid fix would be for said
issue.

> >What pattern of accesses are made by readers and writers such that there is
> >a problem?

Please note here I was asking specifically w.r.t. the lockref code, e.g. which
loads could see stale data, and what does the code do based on this value such
that there is a problem.

> I added the barriers to the readers/writers because I do not know these are
> not similarly abused.  There is a lot of driver code out there, and ensuring
> order is the safest way to be sure we don't get burned by something similar
> to the lockref access.

Making the architecture-provided primitives overly strong harms performance and
efficiency (in general), makes the code harder to maintain and optimise in
future, and only masks the issue (which could crop up on other architectures,
for instance).

Thanks,
Mark.

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

#1495009

On 2016-10-01 14:11, Mark Rutland wrote:
> Hi Brent,
> 
> Evidently my questions weren't sufficiently clear; even with your 
> answers it's
> not clear to me what precise issue you're attempting to solve. I've 
> tried to be
> more specific this time.
> 
> At a high-level, can you clarify whether you're attempting to solve is:
> 
> (a) a functional correctness issue (e.g. data corruption)
> (b) a performance issue
> 
> And whether this was seen in practice, or found through code 
> inspection?
> 
> On Sat, Oct 01, 2016 at 12:11:36PM -0400, bdegraaf@codeaurora.org 
> wrote:
>> On 2016-09-30 15:32, Mark Rutland wrote:
>> >On Fri, Sep 30, 2016 at 01:40:57PM -0400, Brent DeGraaf wrote:
>> >>+	 * so LSE needs an explicit barrier here as well.  Without this, the
>> >>+	 * changed contents of the area protected by the spinlock could be
>> >>+	 * observed prior to the lock.
>> >>+	 */
>> >
>> >By whom? We generally expect that if data is protected by a lock, you take
>> >the lock before accessing it. If you expect concurrent lockless readers,
>> >then there's a requirement on the writer side to explicitly provide the
>> >ordering it requires -- spinlocks are not expected to provide that.
>> 
>> More details are in my response to Robin, but there is an API arm64 
>> supports
>> in spinlock.h which is used by lockref to determine whether a lock is 
>> free or
>> not.  For that code to work properly without adding these barriers, 
>> that API
>> needs to take the lock.
> 
> Can you please provide a concrete example of a case where things go 
> wrong,
> citing the code (or access pattern) in question? e.g. as in the commit 
> messages
> for:
> 
>   8e86f0b409a44193 ("arm64: atomics: fix use of acquire + release for
> full barrier semantics)
>   859b7a0e89120505 ("mm/slub: fix lockups on PREEMPT && !SMP kernels")
> 
> (for the latter, I messed up the register -> var mapping in one 
> paragraph, but
> the style and reasoning is otherwise sound).
> 
> In the absence of a concrete example as above, it's very difficult to 
> reason
> about what the underlying issue is, and what a valid fix would be for 
> said
> issue.
> 
>> >What pattern of accesses are made by readers and writers such that there is
>> >a problem?
> 
> Please note here I was asking specifically w.r.t. the lockref code, 
> e.g. which
> loads could see stale data, and what does the code do based on this 
> value such
> that there is a problem.
> 
>> I added the barriers to the readers/writers because I do not know 
>> these are
>> not similarly abused.  There is a lot of driver code out there, and 
>> ensuring
>> order is the safest way to be sure we don't get burned by something 
>> similar
>> to the lockref access.
> 
> Making the architecture-provided primitives overly strong harms 
> performance and
> efficiency (in general), makes the code harder to maintain and optimise 
> in
> future, and only masks the issue (which could crop up on other 
> architectures,
> for instance).
> 
> Thanks,
> Mark.


Thinking about this, as the reader/writer code has no known "abuse" 
case, I'll
remove it from the patchset, then provide a v2 patchset with a detailed
explanation for the lockref problem using the commits you provided as an 
example,
as well as performance consideration.

Brent

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

#1495229

On Mon, Oct 03, 2016 at 03:20:57PM -0400, bdegraaf@codeaurora.org wrote:
> Thinking about this, as the reader/writer code has no known "abuse"
> case, I'll remove it from the patchset, then provide a v2 patchset
> with a detailed explanation for the lockref problem using the commits
> you provided as an example, as well as performance consideration.

Please, fix lockref in those patches. Touching the spinlock because
lockref does something dubious really is the wrong thing.

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

#1495342

On Mon, Oct 03, 2016 at 03:20:57PM -0400, bdegraaf@codeaurora.org wrote:
> On 2016-10-01 14:11, Mark Rutland wrote:
> >Hi Brent,
> >
> >Evidently my questions weren't sufficiently clear; even with your
> >answers it's not clear to me what precise issue you're attempting to
> >solve.  I've tried to be more specific this time.
> >
> >At a high-level, can you clarify whether you're attempting to solve is:
> >
> >(a) a functional correctness issue (e.g. data corruption)
> >(b) a performance issue
> >
> >And whether this was seen in practice, or found through code
> >inspection?

> Thinking about this, as the reader/writer code has no known "abuse"
> case, I'll remove it from the patchset, then provide a v2 patchset
> with a detailed explanation for the lockref problem using the commits
> you provided as an example, as well as performance consideration.

If there's a functional problem, let's consider that in isolation first.
Once we understand that, then we can consider doing what is optimal.

As should be obvious from the above, I'm confused because this patch
conflates functional details with performance optimisations which (to
me) sound architecturally dubious.

I completely agree with Peter that if the problem lies with lockref, it
should be solved in the lockref code.

Thanks,
Mark.

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

#1495541

On 2016-10-04 06:12, Mark Rutland wrote:
> On Mon, Oct 03, 2016 at 03:20:57PM -0400, bdegraaf@codeaurora.org 
> wrote:
>> On 2016-10-01 14:11, Mark Rutland wrote:
>> >Hi Brent,
>> >
>> >Evidently my questions weren't sufficiently clear; even with your
>> >answers it's not clear to me what precise issue you're attempting to
>> >solve.  I've tried to be more specific this time.
>> >
>> >At a high-level, can you clarify whether you're attempting to solve is:
>> >
>> >(a) a functional correctness issue (e.g. data corruption)
>> >(b) a performance issue
>> >
>> >And whether this was seen in practice, or found through code
>> >inspection?
> 
>> Thinking about this, as the reader/writer code has no known "abuse"
>> case, I'll remove it from the patchset, then provide a v2 patchset
>> with a detailed explanation for the lockref problem using the commits
>> you provided as an example, as well as performance consideration.
> 
> If there's a functional problem, let's consider that in isolation 
> first.
> Once we understand that, then we can consider doing what is optimal.
> 
> As should be obvious from the above, I'm confused because this patch
> conflates functional details with performance optimisations which (to
> me) sound architecturally dubious.
> 
> I completely agree with Peter that if the problem lies with lockref, it
> should be solved in the lockref code.
> 
> Thanks,
> Mark.

After looking at this, the problem is not with the lockref code per se: 
it is
a problem with arch_spin_value_unlocked().  In the out-of-order case,
arch_spin_value_unlocked() can return TRUE for a spinlock that is in 
fact
locked but the lock is not observable yet via an ordinary load.  Other 
than
ensuring order on the locking side (as the prior patch did), there is a 
way
to make arch_spin_value_unlock's TRUE return value deterministic, but it
requires that it does a write-back to the lock to ensure we didn't 
observe
the unlocked value while another agent was in process of writing back a
locked value.

Brent

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

#1495552

On 2016-10-04 13:53, bdegraaf@codeaurora.org wrote:
> On 2016-10-04 06:12, Mark Rutland wrote:
>> On Mon, Oct 03, 2016 at 03:20:57PM -0400, bdegraaf@codeaurora.org 
>> wrote:
>>> On 2016-10-01 14:11, Mark Rutland wrote:
>>> >Hi Brent,
>>> >
>>> >Evidently my questions weren't sufficiently clear; even with your
>>> >answers it's not clear to me what precise issue you're attempting to
>>> >solve.  I've tried to be more specific this time.
>>> >
>>> >At a high-level, can you clarify whether you're attempting to solve is:
>>> >
>>> >(a) a functional correctness issue (e.g. data corruption)
>>> >(b) a performance issue
>>> >
>>> >And whether this was seen in practice, or found through code
>>> >inspection?
>> 
>>> Thinking about this, as the reader/writer code has no known "abuse"
>>> case, I'll remove it from the patchset, then provide a v2 patchset
>>> with a detailed explanation for the lockref problem using the commits
>>> you provided as an example, as well as performance consideration.
>> 
>> If there's a functional problem, let's consider that in isolation 
>> first.
>> Once we understand that, then we can consider doing what is optimal.
>> 
>> As should be obvious from the above, I'm confused because this patch
>> conflates functional details with performance optimisations which (to
>> me) sound architecturally dubious.
>> 
>> I completely agree with Peter that if the problem lies with lockref, 
>> it
>> should be solved in the lockref code.
>> 
>> Thanks,
>> Mark.
> 
> After looking at this, the problem is not with the lockref code per se: 
> it is
> a problem with arch_spin_value_unlocked().  In the out-of-order case,
> arch_spin_value_unlocked() can return TRUE for a spinlock that is in 
> fact
> locked but the lock is not observable yet via an ordinary load.  Other 
> than
> ensuring order on the locking side (as the prior patch did), there is a 
> way
> to make arch_spin_value_unlock's TRUE return value deterministic, but 
> it
> requires that it does a write-back to the lock to ensure we didn't 
> observe
> the unlocked value while another agent was in process of writing back a
> locked value.
> 
> Brent

Scratch that--things get complicated as the lock itself gets "cloned," 
which
could happen during the out-of-order window.  I'll post back later after 
I've
analyzed it fully.

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

#1495564

Hi Brent,

Could you *please* clarify if you are trying to solve:

(a) a correctness issue (e.g. data corruption) seen in practice.
(b) a correctness issue (e.g. data corruption) found by inspection.
(c) A performance issue, seen in practice.
(d) A performance issue, found by inspection.

Any one of these is fine; we just need to know in order to be able to
help effectively, and so far it hasn't been clear.

On Tue, Oct 04, 2016 at 01:53:35PM -0400, bdegraaf@codeaurora.org wrote:
> After looking at this, the problem is not with the lockref code per
> se: it is a problem with arch_spin_value_unlocked(). In the
> out-of-order case, arch_spin_value_unlocked() can return TRUE for a
> spinlock that is in fact locked but the lock is not observable yet via
> an ordinary load. 

Given arch_spin_value_unlocked() doesn't perform any load itself, I
assume the ordinary load that you are referring to is the READ_ONCE()
early in CMPXCHG_LOOP().

It's worth noting that even if we ignore ordering and assume a
sequentially-consistent machine, READ_ONCE() can give us a stale value.
We could perform the read, then another agent can acquire the lock, then
we can move onto the cmpxchg(), i.e.

    CPU0                              CPU1
    old = READ_ONCE(x.lock_val)
                                      spin_lock(x.lock)
    cmpxchg(x.lock_val, old, new)
                                      spin_unlock(x.lock)

If the 'old' value is stale, the cmpxchg *must* fail, and the cmpxchg
should return an up-to-date value which we will then retry with.

> Other than ensuring order on the locking side (as the prior patch
> did), there is a way to make arch_spin_value_unlock's TRUE return
> value deterministic, 

In general, this cannot be made deterministic. As above, there is a race
that cannot be avoided.

> but it requires that it does a write-back to the lock to ensure we
> didn't observe the unlocked value while another agent was in process
> of writing back a locked value.

The cmpxchg gives us this guarantee. If it successfully stores, then the
value it observed was the same as READ_ONCE() saw, and the update was
atomic.

There *could* have been an intervening sequence between the READ_ONCE
and cmpxchg (e.g. put(); get()) but that's not problematic for lockref.
Until you've taken your reference it was possible that things changed
underneath you.

Thanks,
Mark.

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

#1495906

On 2016-10-04 15:12, Mark Rutland wrote:
> Hi Brent,
> 
> Could you *please* clarify if you are trying to solve:
> 
> (a) a correctness issue (e.g. data corruption) seen in practice.
> (b) a correctness issue (e.g. data corruption) found by inspection.
> (c) A performance issue, seen in practice.
> (d) A performance issue, found by inspection.
> 
> Any one of these is fine; we just need to know in order to be able to
> help effectively, and so far it hasn't been clear.
> 
> On Tue, Oct 04, 2016 at 01:53:35PM -0400, bdegraaf@codeaurora.org 
> wrote:
>> After looking at this, the problem is not with the lockref code per
>> se: it is a problem with arch_spin_value_unlocked(). In the
>> out-of-order case, arch_spin_value_unlocked() can return TRUE for a
>> spinlock that is in fact locked but the lock is not observable yet via
>> an ordinary load.
> 
> Given arch_spin_value_unlocked() doesn't perform any load itself, I
> assume the ordinary load that you are referring to is the READ_ONCE()
> early in CMPXCHG_LOOP().
> 
> It's worth noting that even if we ignore ordering and assume a
> sequentially-consistent machine, READ_ONCE() can give us a stale value.
> We could perform the read, then another agent can acquire the lock, 
> then
> we can move onto the cmpxchg(), i.e.
> 
>     CPU0                              CPU1
>     old = READ_ONCE(x.lock_val)
>                                       spin_lock(x.lock)
>     cmpxchg(x.lock_val, old, new)
>                                       spin_unlock(x.lock)
> 
> If the 'old' value is stale, the cmpxchg *must* fail, and the cmpxchg
> should return an up-to-date value which we will then retry with.
> 
>> Other than ensuring order on the locking side (as the prior patch
>> did), there is a way to make arch_spin_value_unlock's TRUE return
>> value deterministic,
> 
> In general, this cannot be made deterministic. As above, there is a 
> race
> that cannot be avoided.
> 
>> but it requires that it does a write-back to the lock to ensure we
>> didn't observe the unlocked value while another agent was in process
>> of writing back a locked value.
> 
> The cmpxchg gives us this guarantee. If it successfully stores, then 
> the
> value it observed was the same as READ_ONCE() saw, and the update was
> atomic.
> 
> There *could* have been an intervening sequence between the READ_ONCE
> and cmpxchg (e.g. put(); get()) but that's not problematic for lockref.
> Until you've taken your reference it was possible that things changed
> underneath you.
> 
> Thanks,
> Mark.

Mark,

I found the problem.

Back in September of 2013, arm64 atomics were broken due to missing 
barriers
in certain situations, but the problem at that time was undiscovered.

Will Deacon's commit d2212b4dce596fee83e5c523400bf084f4cc816c went in at 
that
time and changed the correct cmpxchg64 in lockref.c to 
cmpxchg64_relaxed.

d2212b4 appeared to be OK at that time because the additional barrier
requirements of this specific code sequence were not yet discovered, and
this change was consistent with the arm64 atomic code of that time.

Around February of 2014, some discovery led Will to correct the problem 
with
the atomic code via commit 8e86f0b409a44193f1587e87b69c5dcf8f65be67, 
which
has an excellent explanation of potential ordering problems with the 
same
code sequence used by lockref.c.

With this updated understanding, the earlier commit
(d2212b4dce596fee83e5c523400bf084f4cc816c) should be reverted.

Because acquire/release semantics are insufficient for the full 
ordering,
the single barrier after the store exclusive is the best approach, 
similar
to Will's atomic barrier fix.

Best regards,
Brent

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

#1495918

On 2016-10-05 10:55, bdegraaf@codeaurora.org wrote:
> On 2016-10-04 15:12, Mark Rutland wrote:
>> Hi Brent,
>> 
>> Could you *please* clarify if you are trying to solve:
>> 
>> (a) a correctness issue (e.g. data corruption) seen in practice.
>> (b) a correctness issue (e.g. data corruption) found by inspection.
>> (c) A performance issue, seen in practice.
>> (d) A performance issue, found by inspection.
>> 
>> Any one of these is fine; we just need to know in order to be able to
>> help effectively, and so far it hasn't been clear.
>> 
>> On Tue, Oct 04, 2016 at 01:53:35PM -0400, bdegraaf@codeaurora.org 
>> wrote:
>>> After looking at this, the problem is not with the lockref code per
>>> se: it is a problem with arch_spin_value_unlocked(). In the
>>> out-of-order case, arch_spin_value_unlocked() can return TRUE for a
>>> spinlock that is in fact locked but the lock is not observable yet 
>>> via
>>> an ordinary load.
>> 
>> Given arch_spin_value_unlocked() doesn't perform any load itself, I
>> assume the ordinary load that you are referring to is the READ_ONCE()
>> early in CMPXCHG_LOOP().
>> 
>> It's worth noting that even if we ignore ordering and assume a
>> sequentially-consistent machine, READ_ONCE() can give us a stale 
>> value.
>> We could perform the read, then another agent can acquire the lock, 
>> then
>> we can move onto the cmpxchg(), i.e.
>> 
>>     CPU0                              CPU1
>>     old = READ_ONCE(x.lock_val)
>>                                       spin_lock(x.lock)
>>     cmpxchg(x.lock_val, old, new)
>>                                       spin_unlock(x.lock)
>> 
>> If the 'old' value is stale, the cmpxchg *must* fail, and the cmpxchg
>> should return an up-to-date value which we will then retry with.
>> 
>>> Other than ensuring order on the locking side (as the prior patch
>>> did), there is a way to make arch_spin_value_unlock's TRUE return
>>> value deterministic,
>> 
>> In general, this cannot be made deterministic. As above, there is a 
>> race
>> that cannot be avoided.
>> 
>>> but it requires that it does a write-back to the lock to ensure we
>>> didn't observe the unlocked value while another agent was in process
>>> of writing back a locked value.
>> 
>> The cmpxchg gives us this guarantee. If it successfully stores, then 
>> the
>> value it observed was the same as READ_ONCE() saw, and the update was
>> atomic.
>> 
>> There *could* have been an intervening sequence between the READ_ONCE
>> and cmpxchg (e.g. put(); get()) but that's not problematic for 
>> lockref.
>> Until you've taken your reference it was possible that things changed
>> underneath you.
>> 
>> Thanks,
>> Mark.
> 
> Mark,
> 
> I found the problem.
> 
> Back in September of 2013, arm64 atomics were broken due to missing 
> barriers
> in certain situations, but the problem at that time was undiscovered.
> 
> Will Deacon's commit d2212b4dce596fee83e5c523400bf084f4cc816c went in 
> at that
> time and changed the correct cmpxchg64 in lockref.c to 
> cmpxchg64_relaxed.
> 
> d2212b4 appeared to be OK at that time because the additional barrier
> requirements of this specific code sequence were not yet discovered, 
> and
> this change was consistent with the arm64 atomic code of that time.
> 
> Around February of 2014, some discovery led Will to correct the problem 
> with
> the atomic code via commit 8e86f0b409a44193f1587e87b69c5dcf8f65be67, 
> which
> has an excellent explanation of potential ordering problems with the 
> same
> code sequence used by lockref.c.
> 
> With this updated understanding, the earlier commit
> (d2212b4dce596fee83e5c523400bf084f4cc816c) should be reverted.
> 
> Because acquire/release semantics are insufficient for the full 
> ordering,
> the single barrier after the store exclusive is the best approach, 
> similar
> to Will's atomic barrier fix.
> 
> Best regards,
> Brent

FYI, this is a "b" type fix (correctness fix based on code inspection).

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

#1495920

On Wed, Oct 05, 2016 at 10:55:57AM -0400, bdegraaf@codeaurora.org wrote:
> On 2016-10-04 15:12, Mark Rutland wrote:
> >Hi Brent,
> >
> >Could you *please* clarify if you are trying to solve:
> >
> >(a) a correctness issue (e.g. data corruption) seen in practice.
> >(b) a correctness issue (e.g. data corruption) found by inspection.
> >(c) A performance issue, seen in practice.
> >(d) A performance issue, found by inspection.
> >
> >Any one of these is fine; we just need to know in order to be able to
> >help effectively, and so far it hasn't been clear.

Brent, you forgot to state which: 'a-d' is the case here.

> I found the problem.
> 
> Back in September of 2013, arm64 atomics were broken due to missing barriers
> in certain situations, but the problem at that time was undiscovered.
> 
> Will Deacon's commit d2212b4dce596fee83e5c523400bf084f4cc816c went in at
> that
> time and changed the correct cmpxchg64 in lockref.c to cmpxchg64_relaxed.
> 
> d2212b4 appeared to be OK at that time because the additional barrier
> requirements of this specific code sequence were not yet discovered, and
> this change was consistent with the arm64 atomic code of that time.
> 
> Around February of 2014, some discovery led Will to correct the problem with
> the atomic code via commit 8e86f0b409a44193f1587e87b69c5dcf8f65be67, which
> has an excellent explanation of potential ordering problems with the same
> code sequence used by lockref.c.
> 
> With this updated understanding, the earlier commit
> (d2212b4dce596fee83e5c523400bf084f4cc816c) should be reverted.
> 
> Because acquire/release semantics are insufficient for the full ordering,
> the single barrier after the store exclusive is the best approach, similar
> to Will's atomic barrier fix.

This again does not in fact describe the problem.

What is the problem with lockref, and how (refer the earlier a-d
multiple choice answer) was this found.

Now, I have been looking, and we have some idea what you _might_ be
alluding to, but please explain which accesses get reordered how and
cause problems.

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

#1495938

On 2016-10-05 11:10, Peter Zijlstra wrote:
> On Wed, Oct 05, 2016 at 10:55:57AM -0400, bdegraaf@codeaurora.org 
> wrote:
>> On 2016-10-04 15:12, Mark Rutland wrote:
>> >Hi Brent,
>> >
>> >Could you *please* clarify if you are trying to solve:
>> >
>> >(a) a correctness issue (e.g. data corruption) seen in practice.
>> >(b) a correctness issue (e.g. data corruption) found by inspection.
>> >(c) A performance issue, seen in practice.
>> >(d) A performance issue, found by inspection.
>> >
>> >Any one of these is fine; we just need to know in order to be able to
>> >help effectively, and so far it hasn't been clear.
> 
> Brent, you forgot to state which: 'a-d' is the case here.
> 
>> I found the problem.
>> 
>> Back in September of 2013, arm64 atomics were broken due to missing 
>> barriers
>> in certain situations, but the problem at that time was undiscovered.
>> 
>> Will Deacon's commit d2212b4dce596fee83e5c523400bf084f4cc816c went in 
>> at
>> that
>> time and changed the correct cmpxchg64 in lockref.c to 
>> cmpxchg64_relaxed.
>> 
>> d2212b4 appeared to be OK at that time because the additional barrier
>> requirements of this specific code sequence were not yet discovered, 
>> and
>> this change was consistent with the arm64 atomic code of that time.
>> 
>> Around February of 2014, some discovery led Will to correct the 
>> problem with
>> the atomic code via commit 8e86f0b409a44193f1587e87b69c5dcf8f65be67, 
>> which
>> has an excellent explanation of potential ordering problems with the 
>> same
>> code sequence used by lockref.c.
>> 
>> With this updated understanding, the earlier commit
>> (d2212b4dce596fee83e5c523400bf084f4cc816c) should be reverted.
>> 
>> Because acquire/release semantics are insufficient for the full 
>> ordering,
>> the single barrier after the store exclusive is the best approach, 
>> similar
>> to Will's atomic barrier fix.
> 
> This again does not in fact describe the problem.
> 
> What is the problem with lockref, and how (refer the earlier a-d
> multiple choice answer) was this found.
> 
> Now, I have been looking, and we have some idea what you _might_ be
> alluding to, but please explain which accesses get reordered how and
> cause problems.

Sorry for the confusion, this was a "b" item (correctness fix based on 
code
inspection. I had sent an answer to this yesterday, but didn't realize 
that
it was in a separate, private email thread.

I'll work out the before/after problem scenarios and send them along 
once
I've hashed them out (it may take a while for me to paint a clear 
picture).
In the meantime, however, consider that even without the spinlock code 
in
the picture, lockref needs to treat the cmpxchg as a full system-level 
atomic,
because multiple agents could access the value in a variety of timings. 
Since
atomics similar to this are barriered on arm64 since 8e86f0b, the access 
to
lockref should be similar.

Brent

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

#1499909

On 2016-10-05 11:30, bdegraaf@codeaurora.org wrote:
> On 2016-10-05 11:10, Peter Zijlstra wrote:
>> On Wed, Oct 05, 2016 at 10:55:57AM -0400, bdegraaf@codeaurora.org 
>> wrote:
>>> On 2016-10-04 15:12, Mark Rutland wrote:
>>> >Hi Brent,
>>> >
>>> >Could you *please* clarify if you are trying to solve:
>>> >
>>> >(a) a correctness issue (e.g. data corruption) seen in practice.
>>> >(b) a correctness issue (e.g. data corruption) found by inspection.
>>> >(c) A performance issue, seen in practice.
>>> >(d) A performance issue, found by inspection.
>>> >
>>> >Any one of these is fine; we just need to know in order to be able to
>>> >help effectively, and so far it hasn't been clear.
>> 
>> Brent, you forgot to state which: 'a-d' is the case here.
>> 
>>> I found the problem.
>>> 
>>> Back in September of 2013, arm64 atomics were broken due to missing 
>>> barriers
>>> in certain situations, but the problem at that time was undiscovered.
>>> 
>>> Will Deacon's commit d2212b4dce596fee83e5c523400bf084f4cc816c went in 
>>> at
>>> that
>>> time and changed the correct cmpxchg64 in lockref.c to 
>>> cmpxchg64_relaxed.
>>> 
>>> d2212b4 appeared to be OK at that time because the additional barrier
>>> requirements of this specific code sequence were not yet discovered, 
>>> and
>>> this change was consistent with the arm64 atomic code of that time.
>>> 
>>> Around February of 2014, some discovery led Will to correct the 
>>> problem with
>>> the atomic code via commit 8e86f0b409a44193f1587e87b69c5dcf8f65be67, 
>>> which
>>> has an excellent explanation of potential ordering problems with the 
>>> same
>>> code sequence used by lockref.c.
>>> 
>>> With this updated understanding, the earlier commit
>>> (d2212b4dce596fee83e5c523400bf084f4cc816c) should be reverted.
>>> 
>>> Because acquire/release semantics are insufficient for the full 
>>> ordering,
>>> the single barrier after the store exclusive is the best approach, 
>>> similar
>>> to Will's atomic barrier fix.
>> 
>> This again does not in fact describe the problem.
>> 
>> What is the problem with lockref, and how (refer the earlier a-d
>> multiple choice answer) was this found.
>> 
>> Now, I have been looking, and we have some idea what you _might_ be
>> alluding to, but please explain which accesses get reordered how and
>> cause problems.
> 
> Sorry for the confusion, this was a "b" item (correctness fix based on 
> code
> inspection. I had sent an answer to this yesterday, but didn't realize 
> that
> it was in a separate, private email thread.
> 
> I'll work out the before/after problem scenarios and send them along 
> once
> I've hashed them out (it may take a while for me to paint a clear 
> picture).
> In the meantime, however, consider that even without the spinlock code 
> in
> the picture, lockref needs to treat the cmpxchg as a full system-level 
> atomic,
> because multiple agents could access the value in a variety of timings. 
> Since
> atomics similar to this are barriered on arm64 since 8e86f0b, the 
> access to
> lockref should be similar.
> 
> Brent

I am still working through some additional analyses for mixed accesses, 
but I
thought I'd send along some sample commit text for the fix as it 
currently stands.
Please feel free to comment if you see something that needs 
clarification.

Brent



Text:

All arm64 lockref accesses that occur without taking the spinlock must 
behave like
true atomics, ensuring successive operations are all done sequentially.  
Currently
the lockref accesses, when decompiled, look like the following sequence:

                     <Lockref "unlocked" Access [A]>

                     // Lockref "unlocked" (B)
                 1:  ldxr   x0, [B]         // Exclusive load
                      <change lock_count B>
                     stxr   w1, x0, [B]
                     cbnz   w1, 1b

                      <Lockref "unlocked" Access [C]>

Even though access to the lock_count is protected by exclusives, this is 
not enough
to guarantee order: The lock_count must change atomically, in order, so 
the only
permitted ordering would be:
                               A -> B -> C

Unfortunately, this is not the case by the letter of the architecture 
and, in fact,
the accesses to A and C are not protected by any sort of barrier, and 
hence are
permitted to reorder freely, resulting in orderings such as

                            Bl -> A -> C -> Bs

In this specific scenario, since "change lock_count" could be an 
increment, a decrement
or even a set to a specific value, there could be trouble.  With more 
agents accessing
the lockref without taking the lock, even scenarios where the cmpxchg 
passes falsely
can be encountered, as there is no guarantee that the the "old" value 
will not match
exactly a newer value due to out-of-order access by a combination of 
agents that
increment and decrement the lock_count by the same amount.

Since multiple agents are accessing this without locking the spinlock, 
this access
must have the same protections in place as atomics do in the arch's 
atomic.h.
Fortunately, the fix is not complicated: merely removing the errant 
_relaxed option
on the cmpxchg64 is enough to introduce exactly the same code sequence 
justified
in commit 8e86f0b409a44193f1587e87b69c5dcf8f65be67 to fix arm64 atomics.

                    1:  ldxr   x0, [B]
                        <change lock_count>
                        stlxr   w1, x0, [B]
                        cbnz   w1, 1b
                        dmb    ish

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

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | linux.kernel

csiph-web