* Re: [RFC][PATCH]: documentation,atomic: Add a new atomic_t document
2017-06-12 14:49 ` Peter Zijlstra
@ 2017-06-13 6:39 ` Boqun Feng
2017-06-14 12:33 ` Will Deacon
` (2 subsequent siblings)
3 siblings, 0 replies; 43+ messages in thread
From: Boqun Feng @ 2017-06-13 6:39 UTC (permalink / raw)
To: Peter Zijlstra
Cc: Will Deacon, Paul McKenney, linux-kernel, Ingo Molnar, Thomas Gleixner
On Mon, Jun 12, 2017 at 04:49:29PM +0200, Peter Zijlstra wrote:
> On Sun, Jun 11, 2017 at 09:56:32PM +0800, Boqun Feng wrote:
>
> > I think the term we use to refer this behavior is "fully-ordered"?
>
> Right, that is what we used to call it, and the term even occurs in
> memory-barriers.txt but isn't actually defined therein.
>
> > Could we give it a slight formal definition like:
> >
> > a. memory operations preceding and following the RmW operation is
> > Sequentially Consistent.
> >
> > b. load or store part of the RmW operation is Sequentially
> > Consistent with operations preceding or following.
> >
> > Though, sounds like defining "fully-ordered" is the job for
> > memory-barriers.txt, but it's never done ;-)
>
> Right, so while memory-barriers.txt uses the term 'fully ordered' it
> doesn't appear to mean the same thing we need here.
>
> Still, lacking anything better, I did the below. Note that I also
> removed much of the atomic stuff from memory-barrier.txt in order to
> avoid duplication and confusion (it too was severely stale).
>
Agreed ;-)
>
>
> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> ---
> Documentation/atomic_t.txt | 182 ++++++++++++++++++++++++++++++++++++++
> Documentation/memory-barriers.txt | 86 -----------------
> 2 files changed, 184 insertions(+), 84 deletions(-)
>
> --- /dev/null
> +++ b/Documentation/atomic_t.txt
> @@ -0,0 +1,182 @@
> +
> +On atomic types (atomic_t atomic64_t and atomic_long_t).
> +
> +The atomic type provides an interface to the architecture's means of atomic
> +RmW operations between CPUs (it specifically does not order/work/etc. on
> +IO).
> +
> +The 'full' API consists of:
> +
> +Non RmW ops:
This is the first "Non RmW ops:", and..
> +
> + atomic_read(), atomic_set()
> + atomic_read_acquire(), atomic_set_release()
> +
> +
> +RmW atomic operations:
> +
> +Arithmetic:
> +
> + atomic_{add,sub,inc,dec}()
> + atomic_{add,sub,inc,dec}_return{,_relaxed,_acquire,_release}()
> + atomic_fetch_{add,sub,inc,dec}{,_relaxed,_acquire,_release}()
> +
> +
> +Bitwise:
> +
> + atomic_{and,or,xor,andnot}()
> + atomic_fetch_{and,or,xor,andnot}{,_relaxed,_acquire,_release}()
> +
> +
> +Swap:
> +
> + atomic_xchg{,_relaxed,_acquire,_release}()
> + atomic_cmpxchg{,_relaxed,_acquire,_release}()
> + atomic_try_cmpxchg{,_relaxed,_acquire,_release}()
> +
> +
> +Reference count (but please see refcount_t):
> +
> + atomic_add_unless(), atomic_inc_not_zero()
> + atomic_sub_and_test(), atomic_dec_and_test()
> +
> +
> +Misc:
> +
> + atomic_inc_and_test(), atomic_add_negative()
> + atomic_dec_unless_positive(), atomic_inc_unless_negative()
> +
> +
> +Barriers:
> +
> + smp_mb__{before,after}_atomic()
> +
> +
> +
I feel like some words or a cutting line required here, indicating we
end listing the api ops and begin to talk more details(atomicity,
ordering, etc.). Otherwise, the following second "Non RmW ops:" may
confuse people a little bit. Thoughts?
Regards,
Boqun
> +Non RmW ops:
> +
> +The non-RmW ops are (typically) regular LOADs and STOREs and are canonically
> +implemented using READ_ONCE(), WRITE_ONCE(), smp_load_acquire() and
> +smp_store_release() respectively.
> +
> +The one detail to this is that atomic_set() should be observable to the RmW
> +ops. That is:
> +
> +
> + PRE:
> + atomic_set(v, 1);
> +
> + CPU0 CPU1
> + atomic_add_unless(v, 1, 0) atomic_set(v, 0);
> +
> + POST:
> + BUG_ON(v->counter == 2);
> +
> +
> +In this case we would expect the atomic_set() from CPU1 to either happen
> +before the atomic_add_unless(), in which case that latter one would no-op, or
> +_after_ in which case we'd overwrite its result. In no case is "2" a valid
> +outcome.
> +
> +This is typically true on 'normal' platforms, where a regular competing STORE
> +will invalidate a LL/SC or fail a CMPXCHG.
> +
> +The obvious case where this is not so is when we need to implement atomic ops
> +with a lock:
> +
> +
> + CPU0
> +
> + atomic_add_unless(v, 1, 0);
> + lock();
> + ret = READ_ONCE(v->counter); // == 1
> + atomic_set(v, 0);
> + if (ret != u) WRITE_ONCE(v->counter, 0);
> + WRITE_ONCE(v->counter, ret + 1);
> + unlock();
> +
> +
> +the typical solution is to then implement atomic_set() with atomic_xchg().
> +
> +
> +RmW ops:
> +
> +These come in various forms:
> +
> + - plain operations without return value: atomic_{}()
> +
> + - operations which return the modified value: atomic_{}_return()
> +
> + these are limited to the arithmetic operations because those are
> + reversible. Bitops are irreversible and therefore the modified value
> + is of dubious utility.
> +
> + - operations which return the original value: atomic_fetch_{}()
> +
> + - swap operations: xchg(), cmpxchg() and try_cmpxchg()
> +
> + - misc; the special purpose operations that are commonly used and would,
> + given the interface, normally be implemented using (try_)cmpxchg loops but
> + are time critical and can, (typically) on LL/SC architectures, be more
> + efficiently implemented.
> +
> +
> +All these operations are SMP atomic; that is, the operations (for a single
> +atomic variable) can be fully ordered and no intermediate state is lost or
> +visible.
> +
> +
> +Ordering: (go read memory-barriers.txt first)
> +
> +The rule of thumb:
> +
> + - non-RmW operations are unordered;
> +
> + - RmW operations that have no return value are unordered;
> +
> + - RmW operations that have a return value are fully ordered;
> +
> + - RmW operations that are conditional are unordered on FAILURE, otherwise the
> + above rules apply.
> +
> +Except of course when an operation has an explicit ordering like:
> +
> + {}_relaxed: unordered
> + {}_acquire: the R of the RmW (or atomic_read) is an ACQUIRE
> + {}_release: the W of the RmW (or atomic_set) is a RELEASE
> +
> +
> +Fully ordered primitives are ordered against everything prior and everything
> +subsequenct. They also imply transitivity. Therefore a fully ordered primitive
> +is like having an smp_mb() before and an smp_mb() after the primitive.
> +
> +
> +The barriers:
> +
> + smp_mb__{before,after}_atomic()
> +
> +only apply to the RmW ops and can be used to augment/upgrade the ordering
> +inherit to the used atomic op. These barriers provide a full smp_mb().
> +
> +These helper barriers exist because architectures have varying implicit
> +ordering on their SMP atomic primitives. For example our TSO architectures
> +provide full ordered atomics and these barriers are no-ops.
> +
> +Thus:
> +
> + atomic_fetch_add();
> +
> +is equivalent to:
> +
> + smp_mb__before_atomic();
> + atomic_fetch_add_relaxed();
> + smp_mb__after_atomic();
> +
> +
> +Further, while something like:
> +
> + smp_mb__before_atomic();
> + atomic_dec(&X);
> +
> +is a 'typical' RELEASE pattern, the barrier is strictly stronger than
> +a RELEASE.
> --- a/Documentation/memory-barriers.txt
> +++ b/Documentation/memory-barriers.txt
> @@ -498,7 +498,7 @@ VARIETIES OF MEMORY BARRIER
> This means that ACQUIRE acts as a minimal "acquire" operation and
> RELEASE acts as a minimal "release" operation.
>
> -A subset of the atomic operations described in atomic_ops.txt have ACQUIRE
> +A subset of the atomic operations described in atomic_t.txt have ACQUIRE
> and RELEASE variants in addition to fully-ordered and relaxed (no barrier
> semantics) definitions. For compound atomics performing both a load and a
> store, ACQUIRE semantics apply only to the load and RELEASE semantics apply
> @@ -1876,8 +1876,7 @@ compiler and the CPU from reordering the
> This makes sure that the death mark on the object is perceived to be set
> *before* the reference counter is decremented.
>
> - See Documentation/atomic_ops.txt for more information. See the "Atomic
> - operations" subsection for information on where to use these.
> + See Documentation/atomic_t.txt for more information.
>
>
> (*) lockless_dereference();
> @@ -2503,87 +2502,6 @@ operations are noted specially as some o
> some don't, but they're very heavily relied on as a group throughout the
> kernel.
>
> -Any atomic operation that modifies some state in memory and returns information
> -about the state (old or new) implies an SMP-conditional general memory barrier
> -(smp_mb()) on each side of the actual operation (with the exception of
> -explicit lock operations, described later). These include:
> -
> - xchg();
> - atomic_xchg(); atomic_long_xchg();
> - atomic_inc_return(); atomic_long_inc_return();
> - atomic_dec_return(); atomic_long_dec_return();
> - atomic_add_return(); atomic_long_add_return();
> - atomic_sub_return(); atomic_long_sub_return();
> - atomic_inc_and_test(); atomic_long_inc_and_test();
> - atomic_dec_and_test(); atomic_long_dec_and_test();
> - atomic_sub_and_test(); atomic_long_sub_and_test();
> - atomic_add_negative(); atomic_long_add_negative();
> - test_and_set_bit();
> - test_and_clear_bit();
> - test_and_change_bit();
> -
> - /* when succeeds */
> - cmpxchg();
> - atomic_cmpxchg(); atomic_long_cmpxchg();
> - atomic_add_unless(); atomic_long_add_unless();
> -
> -These are used for such things as implementing ACQUIRE-class and RELEASE-class
> -operations and adjusting reference counters towards object destruction, and as
> -such the implicit memory barrier effects are necessary.
> -
> -
> -The following operations are potential problems as they do _not_ imply memory
> -barriers, but might be used for implementing such things as RELEASE-class
> -operations:
> -
> - atomic_set();
> - set_bit();
> - clear_bit();
> - change_bit();
> -
> -With these the appropriate explicit memory barrier should be used if necessary
> -(smp_mb__before_atomic() for instance).
> -
> -
> -The following also do _not_ imply memory barriers, and so may require explicit
> -memory barriers under some circumstances (smp_mb__before_atomic() for
> -instance):
> -
> - atomic_add();
> - atomic_sub();
> - atomic_inc();
> - atomic_dec();
> -
> -If they're used for statistics generation, then they probably don't need memory
> -barriers, unless there's a coupling between statistical data.
> -
> -If they're used for reference counting on an object to control its lifetime,
> -they probably don't need memory barriers because either the reference count
> -will be adjusted inside a locked section, or the caller will already hold
> -sufficient references to make the lock, and thus a memory barrier unnecessary.
> -
> -If they're used for constructing a lock of some description, then they probably
> -do need memory barriers as a lock primitive generally has to do things in a
> -specific order.
> -
> -Basically, each usage case has to be carefully considered as to whether memory
> -barriers are needed or not.
> -
> -The following operations are special locking primitives:
> -
> - test_and_set_bit_lock();
> - clear_bit_unlock();
> - __clear_bit_unlock();
> -
> -These implement ACQUIRE-class and RELEASE-class operations. These should be
> -used in preference to other operations when implementing locking primitives,
> -because their implementations can be optimised on many architectures.
> -
> -[!] Note that special memory barrier primitives are available for these
> -situations because on some CPUs the atomic instructions used imply full memory
> -barriers, and so barrier instructions are superfluous in conjunction with them,
> -and in such cases the special barrier primitives will be no-ops.
> -
> See Documentation/atomic_ops.txt for more information.
>
>
^ permalink raw reply [flat|nested] 43+ messages in thread* Re: [RFC][PATCH]: documentation,atomic: Add a new atomic_t document
2017-06-12 14:49 ` Peter Zijlstra
2017-06-13 6:39 ` Boqun Feng
@ 2017-06-14 12:33 ` Will Deacon
2017-07-12 12:53 ` Boqun Feng
2017-07-26 11:53 ` [RFC][PATCH v3]: documentation,atomic: Add new documents Peter Zijlstra
3 siblings, 0 replies; 43+ messages in thread
From: Will Deacon @ 2017-06-14 12:33 UTC (permalink / raw)
To: Peter Zijlstra
Cc: Boqun Feng, Paul McKenney, linux-kernel, Ingo Molnar, Thomas Gleixner
On Mon, Jun 12, 2017 at 04:49:29PM +0200, Peter Zijlstra wrote:
> On Sun, Jun 11, 2017 at 09:56:32PM +0800, Boqun Feng wrote:
>
> > I think the term we use to refer this behavior is "fully-ordered"?
>
> Right, that is what we used to call it, and the term even occurs in
> memory-barriers.txt but isn't actually defined therein.
>
> > Could we give it a slight formal definition like:
> >
> > a. memory operations preceding and following the RmW operation is
> > Sequentially Consistent.
> >
> > b. load or store part of the RmW operation is Sequentially
> > Consistent with operations preceding or following.
> >
> > Though, sounds like defining "fully-ordered" is the job for
> > memory-barriers.txt, but it's never done ;-)
>
> Right, so while memory-barriers.txt uses the term 'fully ordered' it
> doesn't appear to mean the same thing we need here.
>
> Still, lacking anything better, I did the below. Note that I also
> removed much of the atomic stuff from memory-barrier.txt in order to
> avoid duplication and confusion (it too was severely stale).
A few more comments inline...
> +The one detail to this is that atomic_set() should be observable to the RmW
> +ops. That is:
I'm afraid this one is still confusing me :)
> + PRE:
> + atomic_set(v, 1);
> +
> + CPU0 CPU1
> + atomic_add_unless(v, 1, 0) atomic_set(v, 0);
> +
> + POST:
> + BUG_ON(v->counter == 2);
> +
> +
> +In this case we would expect the atomic_set() from CPU1 to either happen
> +before the atomic_add_unless(), in which case that latter one would no-op, or
> +_after_ in which case we'd overwrite its result. In no case is "2" a valid
> +outcome.
What do you mean by PRE and POST? Are they running on CPU0, or someplace
else (with barriers)? It sounds like you want to rule out:
CPU1
PRE
CPU0
POST
but it's tough to say whether or not that's actually forbidden.
> +This is typically true on 'normal' platforms, where a regular competing STORE
> +will invalidate a LL/SC or fail a CMPXCHG.
> +
> +The obvious case where this is not so is when we need to implement atomic ops
> +with a lock:
> +
> +
> + CPU0
> +
> + atomic_add_unless(v, 1, 0);
> + lock();
> + ret = READ_ONCE(v->counter); // == 1
> + atomic_set(v, 0);
> + if (ret != u) WRITE_ONCE(v->counter, 0);
> + WRITE_ONCE(v->counter, ret + 1);
> + unlock();
> +
> +
> +the typical solution is to then implement atomic_set() with atomic_xchg().
> +
> +
> +RmW ops:
> +
> +These come in various forms:
> +
> + - plain operations without return value: atomic_{}()
> +
> + - operations which return the modified value: atomic_{}_return()
> +
> + these are limited to the arithmetic operations because those are
> + reversible. Bitops are irreversible and therefore the modified value
> + is of dubious utility.
> +
> + - operations which return the original value: atomic_fetch_{}()
> +
> + - swap operations: xchg(), cmpxchg() and try_cmpxchg()
> +
> + - misc; the special purpose operations that are commonly used and would,
> + given the interface, normally be implemented using (try_)cmpxchg loops but
> + are time critical and can, (typically) on LL/SC architectures, be more
> + efficiently implemented.
> +
> +
> +All these operations are SMP atomic; that is, the operations (for a single
> +atomic variable) can be fully ordered and no intermediate state is lost or
> +visible.
> +
> +
> +Ordering: (go read memory-barriers.txt first)
> +
> +The rule of thumb:
> +
> + - non-RmW operations are unordered;
> +
> + - RmW operations that have no return value are unordered;
> +
> + - RmW operations that have a return value are fully ordered;
> +
> + - RmW operations that are conditional are unordered on FAILURE, otherwise the
> + above rules apply.
> +
> +Except of course when an operation has an explicit ordering like:
> +
> + {}_relaxed: unordered
> + {}_acquire: the R of the RmW (or atomic_read) is an ACQUIRE
> + {}_release: the W of the RmW (or atomic_set) is a RELEASE
> +
> +
> +Fully ordered primitives are ordered against everything prior and everything
> +subsequenct. They also imply transitivity. Therefore a fully ordered primitive
subsequent
> +is like having an smp_mb() before and an smp_mb() after the primitive.
Actually, perhaps that's the best way to explain this: just say that
fully-ordered primitives behave as is they have an smp_mb() before and an
smp_mb() after. Defer the transitivity to memory_barriers.txt (espec. since
it makes it sounds like acquire/release have no transitivity at all).
> +
> +
> +The barriers:
> +
> + smp_mb__{before,after}_atomic()
> +
> +only apply to the RmW ops and can be used to augment/upgrade the ordering
> +inherit to the used atomic op. These barriers provide a full smp_mb().
> +
> +These helper barriers exist because architectures have varying implicit
> +ordering on their SMP atomic primitives. For example our TSO architectures
> +provide full ordered atomics and these barriers are no-ops.
> +
> +Thus:
> +
> + atomic_fetch_add();
> +
> +is equivalent to:
> +
> + smp_mb__before_atomic();
> + atomic_fetch_add_relaxed();
> + smp_mb__after_atomic();
> +
> +
> +Further, while something like:
> +
> + smp_mb__before_atomic();
> + atomic_dec(&X);
> +
> +is a 'typical' RELEASE pattern, the barrier is strictly stronger than
> +a RELEASE.
There's also an ACQUIRE analogue here, and I think you can interwork the
{_acquire,_release} variants with the smp_mb__{before,after}_atomic
variants. On ARM64 the former will be stronger (RCsc), but the kernel memory
model doesn't distinguish. Agreed?
Will
^ permalink raw reply [flat|nested] 43+ messages in thread* Re: [RFC][PATCH]: documentation,atomic: Add a new atomic_t document
2017-06-12 14:49 ` Peter Zijlstra
2017-06-13 6:39 ` Boqun Feng
2017-06-14 12:33 ` Will Deacon
@ 2017-07-12 12:53 ` Boqun Feng
2017-07-12 13:08 ` Peter Zijlstra
2017-07-26 11:53 ` [RFC][PATCH v3]: documentation,atomic: Add new documents Peter Zijlstra
3 siblings, 1 reply; 43+ messages in thread
From: Boqun Feng @ 2017-07-12 12:53 UTC (permalink / raw)
To: Peter Zijlstra
Cc: Will Deacon, Paul McKenney, linux-kernel, Ingo Molnar, Thomas Gleixner
[-- Attachment #1: Type: text/plain, Size: 1266 bytes --]
On Mon, Jun 12, 2017 at 04:49:29PM +0200, Peter Zijlstra wrote:
[...]
> -Any atomic operation that modifies some state in memory and returns information
> -about the state (old or new) implies an SMP-conditional general memory barrier
> -(smp_mb()) on each side of the actual operation (with the exception of
> -explicit lock operations, described later). These include:
> -
> - xchg();
> - atomic_xchg(); atomic_long_xchg();
> - atomic_inc_return(); atomic_long_inc_return();
> - atomic_dec_return(); atomic_long_dec_return();
> - atomic_add_return(); atomic_long_add_return();
> - atomic_sub_return(); atomic_long_sub_return();
> - atomic_inc_and_test(); atomic_long_inc_and_test();
> - atomic_dec_and_test(); atomic_long_dec_and_test();
> - atomic_sub_and_test(); atomic_long_sub_and_test();
> - atomic_add_negative(); atomic_long_add_negative();
> - test_and_set_bit();
> - test_and_clear_bit();
> - test_and_change_bit();
> -
The bit related operations are removed from memory-barriers.txt, I think
we'd better add them in atomic_t.txt? By "them", I mean:
test_and_{set,clear,change}_bit() as RMW atomic
{set,clear,change}_bit() as non-RMW atomic
test_and_set_bit_lock()
clear_bit_unlock() as non-RMW(but barrier-like) atomic
Regards,
Boqun
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]
^ permalink raw reply [flat|nested] 43+ messages in thread* Re: [RFC][PATCH]: documentation,atomic: Add a new atomic_t document
2017-07-12 12:53 ` Boqun Feng
@ 2017-07-12 13:08 ` Peter Zijlstra
2017-07-12 19:13 ` Paul E. McKenney
0 siblings, 1 reply; 43+ messages in thread
From: Peter Zijlstra @ 2017-07-12 13:08 UTC (permalink / raw)
To: Boqun Feng
Cc: Will Deacon, Paul McKenney, linux-kernel, Ingo Molnar, Thomas Gleixner
On Wed, Jul 12, 2017 at 08:53:47PM +0800, Boqun Feng wrote:
> On Mon, Jun 12, 2017 at 04:49:29PM +0200, Peter Zijlstra wrote:
> [...]
> > -Any atomic operation that modifies some state in memory and returns information
> > -about the state (old or new) implies an SMP-conditional general memory barrier
> > -(smp_mb()) on each side of the actual operation (with the exception of
> > -explicit lock operations, described later). These include:
> > -
> > - xchg();
> > - atomic_xchg(); atomic_long_xchg();
> > - atomic_inc_return(); atomic_long_inc_return();
> > - atomic_dec_return(); atomic_long_dec_return();
> > - atomic_add_return(); atomic_long_add_return();
> > - atomic_sub_return(); atomic_long_sub_return();
> > - atomic_inc_and_test(); atomic_long_inc_and_test();
> > - atomic_dec_and_test(); atomic_long_dec_and_test();
> > - atomic_sub_and_test(); atomic_long_sub_and_test();
> > - atomic_add_negative(); atomic_long_add_negative();
> > - test_and_set_bit();
> > - test_and_clear_bit();
> > - test_and_change_bit();
> > -
>
> The bit related operations are removed from memory-barriers.txt, I think
> we'd better add them in atomic_t.txt? By "them", I mean:
>
> test_and_{set,clear,change}_bit() as RMW atomic
>
> {set,clear,change}_bit() as non-RMW atomic
>
> test_and_set_bit_lock()
> clear_bit_unlock() as non-RMW(but barrier-like) atomic
I was thinking maybe a separate file, as I was hoping to eventually
write a separate file on spinlocks too.
I'd like to keep the the new thing purely about the atomic* family of
stuff, that's large enough as is.
^ permalink raw reply [flat|nested] 43+ messages in thread* Re: [RFC][PATCH]: documentation,atomic: Add a new atomic_t document
2017-07-12 13:08 ` Peter Zijlstra
@ 2017-07-12 19:13 ` Paul E. McKenney
0 siblings, 0 replies; 43+ messages in thread
From: Paul E. McKenney @ 2017-07-12 19:13 UTC (permalink / raw)
To: Peter Zijlstra
Cc: Boqun Feng, Will Deacon, linux-kernel, Ingo Molnar, Thomas Gleixner
On Wed, Jul 12, 2017 at 03:08:26PM +0200, Peter Zijlstra wrote:
> On Wed, Jul 12, 2017 at 08:53:47PM +0800, Boqun Feng wrote:
> > On Mon, Jun 12, 2017 at 04:49:29PM +0200, Peter Zijlstra wrote:
> > [...]
> > > -Any atomic operation that modifies some state in memory and returns information
> > > -about the state (old or new) implies an SMP-conditional general memory barrier
> > > -(smp_mb()) on each side of the actual operation (with the exception of
> > > -explicit lock operations, described later). These include:
> > > -
> > > - xchg();
> > > - atomic_xchg(); atomic_long_xchg();
> > > - atomic_inc_return(); atomic_long_inc_return();
> > > - atomic_dec_return(); atomic_long_dec_return();
> > > - atomic_add_return(); atomic_long_add_return();
> > > - atomic_sub_return(); atomic_long_sub_return();
> > > - atomic_inc_and_test(); atomic_long_inc_and_test();
> > > - atomic_dec_and_test(); atomic_long_dec_and_test();
> > > - atomic_sub_and_test(); atomic_long_sub_and_test();
> > > - atomic_add_negative(); atomic_long_add_negative();
> > > - test_and_set_bit();
> > > - test_and_clear_bit();
> > > - test_and_change_bit();
> > > -
> >
> > The bit related operations are removed from memory-barriers.txt, I think
> > we'd better add them in atomic_t.txt? By "them", I mean:
> >
> > test_and_{set,clear,change}_bit() as RMW atomic
> >
> > {set,clear,change}_bit() as non-RMW atomic
> >
> > test_and_set_bit_lock()
> > clear_bit_unlock() as non-RMW(but barrier-like) atomic
>
> I was thinking maybe a separate file, as I was hoping to eventually
> write a separate file on spinlocks too.
>
> I'd like to keep the the new thing purely about the atomic* family of
> stuff, that's large enough as is.
As long as wherever the information is kept actually gets updated when
new functions are added or old ones change, I am good.
Thanx, Paul
^ permalink raw reply [flat|nested] 43+ messages in thread
* [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-06-12 14:49 ` Peter Zijlstra
` (2 preceding siblings ...)
2017-07-12 12:53 ` Boqun Feng
@ 2017-07-26 11:53 ` Peter Zijlstra
2017-07-26 12:47 ` Boqun Feng
2017-07-26 16:28 ` Randy Dunlap
3 siblings, 2 replies; 43+ messages in thread
From: Peter Zijlstra @ 2017-07-26 11:53 UTC (permalink / raw)
To: Boqun Feng
Cc: Will Deacon, Paul McKenney, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap
New version..
---
Subject: documentation,atomic: Add new documents
From: Peter Zijlstra <peterz@infradead.org>
Date: Mon Jun 12 14:50:27 CEST 2017
Since we've vastly expanded the atomic_t interface in recent years the
existing documentation is woefully out of date and people seem to get
confused a bit.
Start a new document to hopefully better explain the current state of
affairs.
The old atomic_ops.txt also covers bitmaps and a few more details so
this is not a full replacement and we'll therefore keep that document
around until such a time that we've managed to write more text to cover
its entire.
Also please, ReST people, go away.
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
Documentation/atomic_bitops.txt | 66 ++++++++++++
Documentation/atomic_t.txt | 200 ++++++++++++++++++++++++++++++++++++++
Documentation/memory-barriers.txt | 88 ----------------
3 files changed, 269 insertions(+), 85 deletions(-)
--- /dev/null
+++ b/Documentation/atomic_bitops.txt
@@ -0,0 +1,66 @@
+
+On atomic bitops.
+
+
+While our bitmap_{}() functions are non-atomic, we have a number of operations
+operating on single bits in a bitmap that are atomic.
+
+
+API
+---
+
+The single bit operations are:
+
+Non RmW ops:
+
+ test_bit()
+
+RmW atomic operations without return value:
+
+ {set,clear,change}_bit()
+ clear_bit_unlock()
+
+RmW atomic operations with return value:
+
+ test_and_{set,clear,change}_bit()
+ test_and_set_bit_lock()
+
+Barriers:
+
+ smp_mb__{before,after}_atomic()
+
+
+All RmW atomic operations have a '__' prefixed variant which is non-atomic.
+
+
+SEMANTICS
+---------
+
+Non-atomic ops:
+
+In particular __clear_bit_unlock() suffers the same issue as atomic_set(),
+which is why the generic version maps to clear_bit_unlock(), see atomic_t.txt.
+
+
+RmW ops:
+
+The test_and_{}_bit() operations return the original value of the bit.
+
+
+ORDERING
+--------
+
+Like with atomic_t, the rule of thumb is:
+
+ - non-RmW operations are unordered;
+
+ - RmW operations that have no return value are unordered;
+
+ - RmW operations that have a return value are fully ordered.
+
+Except for test_and_set_bit_lock() which has ACQUIRE semantics and
+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.
+
--- /dev/null
+++ b/Documentation/atomic_t.txt
@@ -0,0 +1,200 @@
+
+On atomic types (atomic_t atomic64_t and atomic_long_t).
+
+The atomic type provides an interface to the architecture's means of atomic
+RmW operations between CPUs (atomic operations on MMIO are not supported and
+can lead to fatal traps on some platforms).
+
+API
+---
+
+The 'full' API consists of (atomic64_ and atomic_long_ prefixes omitted for
+brevity):
+
+Non RmW ops:
+
+ atomic_read(), atomic_set()
+ atomic_read_acquire(), atomic_set_release()
+
+
+RmW atomic operations:
+
+Arithmetic:
+
+ atomic_{add,sub,inc,dec}()
+ atomic_{add,sub,inc,dec}_return{,_relaxed,_acquire,_release}()
+ atomic_fetch_{add,sub,inc,dec}{,_relaxed,_acquire,_release}()
+
+
+Bitwise:
+
+ atomic_{and,or,xor,andnot}()
+ atomic_fetch_{and,or,xor,andnot}{,_relaxed,_acquire,_release}()
+
+
+Swap:
+
+ atomic_xchg{,_relaxed,_acquire,_release}()
+ atomic_cmpxchg{,_relaxed,_acquire,_release}()
+ atomic_try_cmpxchg{,_relaxed,_acquire,_release}()
+
+
+Reference count (but please see refcount_t):
+
+ atomic_add_unless(), atomic_inc_not_zero()
+ atomic_sub_and_test(), atomic_dec_and_test()
+
+
+Misc:
+
+ atomic_inc_and_test(), atomic_add_negative()
+ atomic_dec_unless_positive(), atomic_inc_unless_negative()
+
+
+Barriers:
+
+ smp_mb__{before,after}_atomic()
+
+
+
+SEMANTICS
+---------
+
+Non RmW ops:
+
+The non-RmW ops are (typically) regular LOADs and STOREs and are canonically
+implemented using READ_ONCE(), WRITE_ONCE(), smp_load_acquire() and
+smp_store_release() respectively.
+
+The one detail to this is that atomic_set{}() should be observable to the RmW
+ops. That is:
+
+ C atomic-set
+
+ {
+ atomic_set(v, 1);
+ }
+
+ P1(atomic_t *v)
+ {
+ atomic_add_unless(v, 1, 0);
+ }
+
+ P2(atomic_t *v)
+ {
+ atomic_set(v, 0);
+ }
+
+ exists
+ (v=2)
+
+In this case we would expect the atomic_set() from CPU1 to either happen
+before the atomic_add_unless(), in which case that latter one would no-op, or
+_after_ in which case we'd overwrite its result. In no case is "2" a valid
+outcome.
+
+This is typically true on 'normal' platforms, where a regular competing STORE
+will invalidate a LL/SC or fail a CMPXCHG.
+
+The obvious case where this is not so is when we need to implement atomic ops
+with a lock:
+
+ CPU0 CPU1
+
+ atomic_add_unless(v, 1, 0);
+ lock();
+ ret = READ_ONCE(v->counter); // == 1
+ atomic_set(v, 0);
+ if (ret != u) WRITE_ONCE(v->counter, 0);
+ WRITE_ONCE(v->counter, ret + 1);
+ unlock();
+
+the typical solution is to then implement atomic_set{}() with atomic_xchg().
+
+
+RmW ops:
+
+These come in various forms:
+
+ - plain operations without return value: atomic_{}()
+
+ - operations which return the modified value: atomic_{}_return()
+
+ these are limited to the arithmetic operations because those are
+ reversible. Bitops are irreversible and therefore the modified value
+ is of dubious utility.
+
+ - operations which return the original value: atomic_fetch_{}()
+
+ - swap operations: xchg(), cmpxchg() and try_cmpxchg()
+
+ - misc; the special purpose operations that are commonly used and would,
+ given the interface, normally be implemented using (try_)cmpxchg loops but
+ are time critical and can, (typically) on LL/SC architectures, be more
+ efficiently implemented.
+
+All these operations are SMP atomic; that is, the operations (for a single
+atomic variable) can be fully ordered and no intermediate state is lost or
+visible.
+
+
+ORDERING (go read memory-barriers.txt first)
+--------
+
+The rule of thumb:
+
+ - non-RmW operations are unordered;
+
+ - RmW operations that have no return value are unordered;
+
+ - RmW operations that have a return value are fully ordered;
+
+ - RmW operations that are conditional are unordered on FAILURE,
+ otherwise the above rules apply.
+
+Except of course when an operation has an explicit ordering like:
+
+ {}_relaxed: unordered
+ {}_acquire: the R of the RmW (or atomic_read) is an ACQUIRE
+ {}_release: the W of the RmW (or atomic_set) is a RELEASE
+
+Where 'unordered' is against other memory locations. Address dependencies are
+not defeated.
+
+Fully ordered primitives are ordered against everything prior and everything
+subsequent. Therefore a fully ordered primitive is like having an smp_mb()
+before and an smp_mb() after the primitive.
+
+
+The barriers:
+
+ smp_mb__{before,after}_atomic()
+
+only apply to the RmW ops and can be used to augment/upgrade the ordering
+inherent to the used atomic op. These barriers provide a full smp_mb().
+
+These helper barriers exist because architectures have varying implicit
+ordering on their SMP atomic primitives. For example our TSO architectures
+provide full ordered atomics and these barriers are no-ops.
+
+Thus:
+
+ atomic_fetch_add();
+
+is equivalent to:
+
+ smp_mb__before_atomic();
+ atomic_fetch_add_relaxed();
+ smp_mb__after_atomic();
+
+However the atomic_fetch_add() might be implemented more efficiently.
+
+Further, while something like:
+
+ smp_mb__before_atomic();
+ atomic_dec(&X);
+
+is a 'typical' RELEASE pattern, the barrier is strictly stronger than
+a RELEASE. Similarly for something like:
+
+
--- a/Documentation/memory-barriers.txt
+++ b/Documentation/memory-barriers.txt
@@ -498,7 +498,7 @@ VARIETIES OF MEMORY BARRIER
This means that ACQUIRE acts as a minimal "acquire" operation and
RELEASE acts as a minimal "release" operation.
-A subset of the atomic operations described in core-api/atomic_ops.rst have
+A subset of the atomic operations described in atomic_t.txt have ACQUIRE
ACQUIRE and RELEASE variants in addition to fully-ordered and relaxed (no
barrier semantics) definitions. For compound atomics performing both a load
and a store, ACQUIRE semantics apply only to the load and RELEASE semantics
@@ -1876,8 +1876,7 @@ compiler and the CPU from reordering the
This makes sure that the death mark on the object is perceived to be set
*before* the reference counter is decremented.
- See Documentation/core-api/atomic_ops.rst for more information. See the
- "Atomic operations" subsection for information on where to use these.
+ See Documentation/atomic_t.txt for more information.
(*) lockless_dereference();
@@ -2503,88 +2502,7 @@ operations are noted specially as some o
some don't, but they're very heavily relied on as a group throughout the
kernel.
-Any atomic operation that modifies some state in memory and returns information
-about the state (old or new) implies an SMP-conditional general memory barrier
-(smp_mb()) on each side of the actual operation (with the exception of
-explicit lock operations, described later). These include:
-
- xchg();
- atomic_xchg(); atomic_long_xchg();
- atomic_inc_return(); atomic_long_inc_return();
- atomic_dec_return(); atomic_long_dec_return();
- atomic_add_return(); atomic_long_add_return();
- atomic_sub_return(); atomic_long_sub_return();
- atomic_inc_and_test(); atomic_long_inc_and_test();
- atomic_dec_and_test(); atomic_long_dec_and_test();
- atomic_sub_and_test(); atomic_long_sub_and_test();
- atomic_add_negative(); atomic_long_add_negative();
- test_and_set_bit();
- test_and_clear_bit();
- test_and_change_bit();
-
- /* when succeeds */
- cmpxchg();
- atomic_cmpxchg(); atomic_long_cmpxchg();
- atomic_add_unless(); atomic_long_add_unless();
-
-These are used for such things as implementing ACQUIRE-class and RELEASE-class
-operations and adjusting reference counters towards object destruction, and as
-such the implicit memory barrier effects are necessary.
-
-
-The following operations are potential problems as they do _not_ imply memory
-barriers, but might be used for implementing such things as RELEASE-class
-operations:
-
- atomic_set();
- set_bit();
- clear_bit();
- change_bit();
-
-With these the appropriate explicit memory barrier should be used if necessary
-(smp_mb__before_atomic() for instance).
-
-
-The following also do _not_ imply memory barriers, and so may require explicit
-memory barriers under some circumstances (smp_mb__before_atomic() for
-instance):
-
- atomic_add();
- atomic_sub();
- atomic_inc();
- atomic_dec();
-
-If they're used for statistics generation, then they probably don't need memory
-barriers, unless there's a coupling between statistical data.
-
-If they're used for reference counting on an object to control its lifetime,
-they probably don't need memory barriers because either the reference count
-will be adjusted inside a locked section, or the caller will already hold
-sufficient references to make the lock, and thus a memory barrier unnecessary.
-
-If they're used for constructing a lock of some description, then they probably
-do need memory barriers as a lock primitive generally has to do things in a
-specific order.
-
-Basically, each usage case has to be carefully considered as to whether memory
-barriers are needed or not.
-
-The following operations are special locking primitives:
-
- test_and_set_bit_lock();
- clear_bit_unlock();
- __clear_bit_unlock();
-
-These implement ACQUIRE-class and RELEASE-class operations. These should be
-used in preference to other operations when implementing locking primitives,
-because their implementations can be optimised on many architectures.
-
-[!] Note that special memory barrier primitives are available for these
-situations because on some CPUs the atomic instructions used imply full memory
-barriers, and so barrier instructions are superfluous in conjunction with them,
-and in such cases the special barrier primitives will be no-ops.
-
-See Documentation/core-api/atomic_ops.rst for more information.
+See Documentation/atomic_t.txt for more information.
ACCESSING DEVICES
^ permalink raw reply [flat|nested] 43+ messages in thread* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-07-26 11:53 ` [RFC][PATCH v3]: documentation,atomic: Add new documents Peter Zijlstra
@ 2017-07-26 12:47 ` Boqun Feng
2017-07-31 9:05 ` Peter Zijlstra
2017-07-26 16:28 ` Randy Dunlap
1 sibling, 1 reply; 43+ messages in thread
From: Boqun Feng @ 2017-07-26 12:47 UTC (permalink / raw)
To: Peter Zijlstra
Cc: Will Deacon, Paul McKenney, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap
[-- Attachment #1: Type: text/plain, Size: 2116 bytes --]
On Wed, Jul 26, 2017 at 01:53:28PM +0200, Peter Zijlstra wrote:
>
> New version..
>
>
> ---
> Subject: documentation,atomic: Add new documents
> From: Peter Zijlstra <peterz@infradead.org>
> Date: Mon Jun 12 14:50:27 CEST 2017
>
> Since we've vastly expanded the atomic_t interface in recent years the
> existing documentation is woefully out of date and people seem to get
> confused a bit.
>
> Start a new document to hopefully better explain the current state of
> affairs.
>
> The old atomic_ops.txt also covers bitmaps and a few more details so
> this is not a full replacement and we'll therefore keep that document
> around until such a time that we've managed to write more text to cover
> its entire.
>
You seems have a unfinished paragraph..
> Also please, ReST people, go away.
>
> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> ---
[...]
> +
> +Further, while something like:
> +
> + smp_mb__before_atomic();
> + atomic_dec(&X);
> +
> +is a 'typical' RELEASE pattern, the barrier is strictly stronger than
> +a RELEASE. Similarly for something like:
> +
.. at here. Maybe you planned to put stronger ACQUIRE pattern?
> +
> --- a/Documentation/memory-barriers.txt
> +++ b/Documentation/memory-barriers.txt
> @@ -498,7 +498,7 @@ VARIETIES OF MEMORY BARRIER
> This means that ACQUIRE acts as a minimal "acquire" operation and
> RELEASE acts as a minimal "release" operation.
>
[...]
> -
> -[!] Note that special memory barrier primitives are available for these
> -situations because on some CPUs the atomic instructions used imply full memory
> -barriers, and so barrier instructions are superfluous in conjunction with them,
> -and in such cases the special barrier primitives will be no-ops.
> -
> -See Documentation/core-api/atomic_ops.rst for more information.
> +See Documentation/atomic_t.txt for more information.
>
s/atomic_t.txt/atomic_{t,bitops}.txt/ ?
other than those two tiny things,
Reviewed-by: Boqun Feng <boqun.feng@gmail.com>
Regards,
Boqun
>
> ACCESSING DEVICES
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]
^ permalink raw reply [flat|nested] 43+ messages in thread* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-07-26 12:47 ` Boqun Feng
@ 2017-07-31 9:05 ` Peter Zijlstra
2017-07-31 11:04 ` Boqun Feng
0 siblings, 1 reply; 43+ messages in thread
From: Peter Zijlstra @ 2017-07-31 9:05 UTC (permalink / raw)
To: Boqun Feng
Cc: Will Deacon, Paul McKenney, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap
On Wed, Jul 26, 2017 at 08:47:50PM +0800, Boqun Feng wrote:
> > +
> > +Further, while something like:
> > +
> > + smp_mb__before_atomic();
> > + atomic_dec(&X);
> > +
> > +is a 'typical' RELEASE pattern, the barrier is strictly stronger than
> > +a RELEASE. Similarly for something like:
> > +
>
> .. at here. Maybe you planned to put stronger ACQUIRE pattern?
Yes, although I struggled to find a sensible one. The problem is that
ACQUIRE is on loads and value returning atomics have an ACQUIRE variant,
so why would you ever want to use smp_mb__after_atomic() for this.
That is, the best I could come up with is something like:
val = atomic_fetch_or_relaxed(1, &var);
smp_mb__after_atomic();
But in that case we should've just written:
val = atomic_fetch_or_acquire(1, &var);
Suggestions?
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-07-31 9:05 ` Peter Zijlstra
@ 2017-07-31 11:04 ` Boqun Feng
2017-07-31 17:43 ` Paul E. McKenney
0 siblings, 1 reply; 43+ messages in thread
From: Boqun Feng @ 2017-07-31 11:04 UTC (permalink / raw)
To: Peter Zijlstra
Cc: Will Deacon, Paul McKenney, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap
[-- Attachment #1: Type: text/plain, Size: 1816 bytes --]
On Mon, Jul 31, 2017 at 11:05:35AM +0200, Peter Zijlstra wrote:
> On Wed, Jul 26, 2017 at 08:47:50PM +0800, Boqun Feng wrote:
>
> > > +
> > > +Further, while something like:
> > > +
> > > + smp_mb__before_atomic();
> > > + atomic_dec(&X);
> > > +
> > > +is a 'typical' RELEASE pattern, the barrier is strictly stronger than
> > > +a RELEASE. Similarly for something like:
> > > +
> >
> > .. at here. Maybe you planned to put stronger ACQUIRE pattern?
>
> Yes, although I struggled to find a sensible one. The problem is that
> ACQUIRE is on loads and value returning atomics have an ACQUIRE variant,
> so why would you ever want to use smp_mb__after_atomic() for this.
>
>
> That is, the best I could come up with is something like:
>
> val = atomic_fetch_or_relaxed(1, &var);
> smp_mb__after_atomic();
>
> But in that case we should've just written:
>
> val = atomic_fetch_or_acquire(1, &var);
>
Agreed.
And besides, in memory-barriers.txt, the wording is:
(*) smp_mb__before_atomic();
(*) smp_mb__after_atomic();
These are for use with atomic (such as add, subtract, increment and
decrement) functions that don't return a value, especially when used for
reference counting.
So actually, using smp_mb__after_atomic() for ACQUIRE is a misuse.
>
> Suggestions?
As a result, I think it's better we say smp_mb__{before,after}_atomic()
are only for 1) non-value-returning RmW atomic ops, 2)
{set,clear,change}_bit and 3) internal use of atomic primitives(e.g. the
generic version of fully ordered atomics).
1) prevents people to use it for an ACQUIRE, but allows for a RELEASE.
1) & 2) makes atomic_t.txt consistent with memory-barriers.txt
3) explains our usage of those barriers internally.
Thoughts?
Regards,
Boqun
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]
^ permalink raw reply [flat|nested] 43+ messages in thread* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-07-31 11:04 ` Boqun Feng
@ 2017-07-31 17:43 ` Paul E. McKenney
2017-08-01 2:14 ` Boqun Feng
2017-08-01 9:01 ` Peter Zijlstra
0 siblings, 2 replies; 43+ messages in thread
From: Paul E. McKenney @ 2017-07-31 17:43 UTC (permalink / raw)
To: Boqun Feng
Cc: Peter Zijlstra, Will Deacon, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap
On Mon, Jul 31, 2017 at 07:04:03PM +0800, Boqun Feng wrote:
> On Mon, Jul 31, 2017 at 11:05:35AM +0200, Peter Zijlstra wrote:
> > On Wed, Jul 26, 2017 at 08:47:50PM +0800, Boqun Feng wrote:
> >
> > > > +
> > > > +Further, while something like:
> > > > +
> > > > + smp_mb__before_atomic();
> > > > + atomic_dec(&X);
> > > > +
> > > > +is a 'typical' RELEASE pattern, the barrier is strictly stronger than
> > > > +a RELEASE. Similarly for something like:
> > > > +
> > >
> > > .. at here. Maybe you planned to put stronger ACQUIRE pattern?
> >
> > Yes, although I struggled to find a sensible one. The problem is that
> > ACQUIRE is on loads and value returning atomics have an ACQUIRE variant,
> > so why would you ever want to use smp_mb__after_atomic() for this.
> >
> >
> > That is, the best I could come up with is something like:
> >
> > val = atomic_fetch_or_relaxed(1, &var);
> > smp_mb__after_atomic();
> >
> > But in that case we should've just written:
> >
> > val = atomic_fetch_or_acquire(1, &var);
> >
>
> Agreed.
>
> And besides, in memory-barriers.txt, the wording is:
>
> (*) smp_mb__before_atomic();
> (*) smp_mb__after_atomic();
>
> These are for use with atomic (such as add, subtract, increment and
> decrement) functions that don't return a value, especially when used for
> reference counting.
>
> So actually, using smp_mb__after_atomic() for ACQUIRE is a misuse.
You lost me on this one.
Why wouldn't the following have ACQUIRE semantics?
atomic_inc(&var);
smp_mb__after_atomic();
Is the issue that there is no actual value returned or some such?
> > Suggestions?
>
> As a result, I think it's better we say smp_mb__{before,after}_atomic()
> are only for 1) non-value-returning RmW atomic ops, 2)
> {set,clear,change}_bit and 3) internal use of atomic primitives(e.g. the
> generic version of fully ordered atomics).
>
> 1) prevents people to use it for an ACQUIRE, but allows for a RELEASE.
> 1) & 2) makes atomic_t.txt consistent with memory-barriers.txt
> 3) explains our usage of those barriers internally.
>
> Thoughts?
So if I have something like this, the assertion really can trigger?
WRITE_ONCE(x, 1); atomic_inc(&y);
r0 = xchg_release(&y, 5); smp_mb__after_atomic();
r1 = READ_ONCE(x);
WARN_ON(r0 == 0 && r1 == 0);
I must confess that I am not seeing why we would want to allow this
outcome.
Thanx, Paul
^ permalink raw reply [flat|nested] 43+ messages in thread* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-07-31 17:43 ` Paul E. McKenney
@ 2017-08-01 2:14 ` Boqun Feng
2017-08-01 9:01 ` Peter Zijlstra
1 sibling, 0 replies; 43+ messages in thread
From: Boqun Feng @ 2017-08-01 2:14 UTC (permalink / raw)
To: Paul E. McKenney
Cc: Peter Zijlstra, Will Deacon, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap
[-- Attachment #1: Type: text/plain, Size: 3514 bytes --]
On Mon, Jul 31, 2017 at 10:43:45AM -0700, Paul E. McKenney wrote:
> On Mon, Jul 31, 2017 at 07:04:03PM +0800, Boqun Feng wrote:
> > On Mon, Jul 31, 2017 at 11:05:35AM +0200, Peter Zijlstra wrote:
> > > On Wed, Jul 26, 2017 at 08:47:50PM +0800, Boqun Feng wrote:
> > >
> > > > > +
> > > > > +Further, while something like:
> > > > > +
> > > > > + smp_mb__before_atomic();
> > > > > + atomic_dec(&X);
> > > > > +
> > > > > +is a 'typical' RELEASE pattern, the barrier is strictly stronger than
> > > > > +a RELEASE. Similarly for something like:
> > > > > +
> > > >
> > > > .. at here. Maybe you planned to put stronger ACQUIRE pattern?
> > >
> > > Yes, although I struggled to find a sensible one. The problem is that
> > > ACQUIRE is on loads and value returning atomics have an ACQUIRE variant,
> > > so why would you ever want to use smp_mb__after_atomic() for this.
> > >
> > >
> > > That is, the best I could come up with is something like:
> > >
> > > val = atomic_fetch_or_relaxed(1, &var);
> > > smp_mb__after_atomic();
> > >
> > > But in that case we should've just written:
> > >
> > > val = atomic_fetch_or_acquire(1, &var);
> > >
> >
> > Agreed.
> >
> > And besides, in memory-barriers.txt, the wording is:
> >
> > (*) smp_mb__before_atomic();
> > (*) smp_mb__after_atomic();
> >
> > These are for use with atomic (such as add, subtract, increment and
> > decrement) functions that don't return a value, especially when used for
> > reference counting.
> >
> > So actually, using smp_mb__after_atomic() for ACQUIRE is a misuse.
>
> You lost me on this one.
>
> Why wouldn't the following have ACQUIRE semantics?
>
> atomic_inc(&var);
> smp_mb__after_atomic();
>
> Is the issue that there is no actual value returned or some such?
>
That "misuse" is a wrong word there ;-(
I actually meant "the usage is correct but we don't encourage using
smp_mb__after_atomic() *only* for an ACQUIRE, because _acquire() could
always be used in that case, as Peter said".
In fact in your case, the ordering is stronger, both the load and store
part of the atomic op are ordered with the memory ops following it.
In short, I suggested we tell users to use
smp_mb__{before,after}_atomic() only when _{release,acquire} ops don't
suffice, i.e. for an RCsc RELEASE or a smp_mb() to order ops other than
the atomic op itself(like the one you use in __call_rcu_nocb_enqueue()).
But maybe this is too strict, and Peter said he would write something
about it in IRC, so I'm not that stick to this suggestion ;-)
Regards,
Boqun
> > > Suggestions?
> >
> > As a result, I think it's better we say smp_mb__{before,after}_atomic()
> > are only for 1) non-value-returning RmW atomic ops, 2)
> > {set,clear,change}_bit and 3) internal use of atomic primitives(e.g. the
> > generic version of fully ordered atomics).
> >
> > 1) prevents people to use it for an ACQUIRE, but allows for a RELEASE.
> > 1) & 2) makes atomic_t.txt consistent with memory-barriers.txt
> > 3) explains our usage of those barriers internally.
> >
> > Thoughts?
>
> So if I have something like this, the assertion really can trigger?
>
> WRITE_ONCE(x, 1); atomic_inc(&y);
> r0 = xchg_release(&y, 5); smp_mb__after_atomic();
> r1 = READ_ONCE(x);
>
>
> WARN_ON(r0 == 0 && r1 == 0);
>
> I must confess that I am not seeing why we would want to allow this
> outcome.
>
> Thanx, Paul
>
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]
^ permalink raw reply [flat|nested] 43+ messages in thread* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-07-31 17:43 ` Paul E. McKenney
2017-08-01 2:14 ` Boqun Feng
@ 2017-08-01 9:01 ` Peter Zijlstra
2017-08-01 10:19 ` Will Deacon
2017-08-01 13:35 ` Paul E. McKenney
1 sibling, 2 replies; 43+ messages in thread
From: Peter Zijlstra @ 2017-08-01 9:01 UTC (permalink / raw)
To: Paul E. McKenney
Cc: Boqun Feng, Will Deacon, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap
On Mon, Jul 31, 2017 at 10:43:45AM -0700, Paul E. McKenney wrote:
> Why wouldn't the following have ACQUIRE semantics?
>
> atomic_inc(&var);
> smp_mb__after_atomic();
>
> Is the issue that there is no actual value returned or some such?
Yes, so that the inc is a load-store, and thus there is a load, we loose
the value.
But I see your point I think. Irrespective of still having the value,
the ordering is preserved and nothing should pass across that.
> So if I have something like this, the assertion really can trigger?
>
> WRITE_ONCE(x, 1); atomic_inc(&y);
> r0 = xchg_release(&y, 5); smp_mb__after_atomic();
> r1 = READ_ONCE(x);
>
>
> WARN_ON(r0 == 0 && r1 == 0);
>
> I must confess that I am not seeing why we would want to allow this
> outcome.
No you are indeed quite right. I just wasn't creative enough. Thanks for
the inspiration.
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-08-01 9:01 ` Peter Zijlstra
@ 2017-08-01 10:19 ` Will Deacon
2017-08-01 11:47 ` Peter Zijlstra
2017-08-01 13:35 ` Paul E. McKenney
1 sibling, 1 reply; 43+ messages in thread
From: Will Deacon @ 2017-08-01 10:19 UTC (permalink / raw)
To: Peter Zijlstra
Cc: Paul E. McKenney, Boqun Feng, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap
On Tue, Aug 01, 2017 at 11:01:21AM +0200, Peter Zijlstra wrote:
> On Mon, Jul 31, 2017 at 10:43:45AM -0700, Paul E. McKenney wrote:
>
> > Why wouldn't the following have ACQUIRE semantics?
> >
> > atomic_inc(&var);
> > smp_mb__after_atomic();
> >
> > Is the issue that there is no actual value returned or some such?
>
> Yes, so that the inc is a load-store, and thus there is a load, we loose
> the value.
>
> But I see your point I think. Irrespective of still having the value,
> the ordering is preserved and nothing should pass across that.
>
> > So if I have something like this, the assertion really can trigger?
> >
> > WRITE_ONCE(x, 1); atomic_inc(&y);
> > r0 = xchg_release(&y, 5); smp_mb__after_atomic();
> > r1 = READ_ONCE(x);
> >
> >
> > WARN_ON(r0 == 0 && r1 == 0);
> >
> > I must confess that I am not seeing why we would want to allow this
> > outcome.
>
> No you are indeed quite right. I just wasn't creative enough. Thanks for
> the inspiration.
Just to close this out, we agree that an smp_rmb() instead of
smp_mb__after_atomic() would *not* forbid this outcome, right?
Will
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-08-01 10:19 ` Will Deacon
@ 2017-08-01 11:47 ` Peter Zijlstra
2017-08-01 12:17 ` Will Deacon
0 siblings, 1 reply; 43+ messages in thread
From: Peter Zijlstra @ 2017-08-01 11:47 UTC (permalink / raw)
To: Will Deacon
Cc: Paul E. McKenney, Boqun Feng, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap
On Tue, Aug 01, 2017 at 11:19:00AM +0100, Will Deacon wrote:
> On Tue, Aug 01, 2017 at 11:01:21AM +0200, Peter Zijlstra wrote:
> > On Mon, Jul 31, 2017 at 10:43:45AM -0700, Paul E. McKenney wrote:
> >
> > > Why wouldn't the following have ACQUIRE semantics?
> > >
> > > atomic_inc(&var);
> > > smp_mb__after_atomic();
> > >
> > > Is the issue that there is no actual value returned or some such?
> >
> > Yes, so that the inc is a load-store, and thus there is a load, we loose
> > the value.
> >
> > But I see your point I think. Irrespective of still having the value,
> > the ordering is preserved and nothing should pass across that.
> >
> > > So if I have something like this, the assertion really can trigger?
> > >
> > > WRITE_ONCE(x, 1); atomic_inc(&y);
> > > r0 = xchg_release(&y, 5); smp_mb__after_atomic();
> > > r1 = READ_ONCE(x);
> > >
> > >
> > > WARN_ON(r0 == 0 && r1 == 0);
> > >
> > > I must confess that I am not seeing why we would want to allow this
> > > outcome.
> >
> > No you are indeed quite right. I just wasn't creative enough. Thanks for
> > the inspiration.
>
> Just to close this out, we agree that an smp_rmb() instead of
> smp_mb__after_atomic() would *not* forbid this outcome, right?
So that really hurts my brain. Per the normal rules that smp_rmb() would
order the read of @x against the last ll of @y and per ll/sc ordering
you then still don't get to make the WARN happen.
On IRC you explained that your 8.1 LSE instructions are not in fact
ordered by a smp_rmb, only by smp_wmb, which is 'surprising' since you
really need to load the old value to compute the new value.
Not happy... :-(
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-08-01 11:47 ` Peter Zijlstra
@ 2017-08-01 12:17 ` Will Deacon
2017-08-01 12:52 ` Peter Zijlstra
2017-08-01 16:14 ` Paul E. McKenney
0 siblings, 2 replies; 43+ messages in thread
From: Will Deacon @ 2017-08-01 12:17 UTC (permalink / raw)
To: Peter Zijlstra
Cc: Paul E. McKenney, Boqun Feng, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap
On Tue, Aug 01, 2017 at 01:47:44PM +0200, Peter Zijlstra wrote:
> On Tue, Aug 01, 2017 at 11:19:00AM +0100, Will Deacon wrote:
> > On Tue, Aug 01, 2017 at 11:01:21AM +0200, Peter Zijlstra wrote:
> > > On Mon, Jul 31, 2017 at 10:43:45AM -0700, Paul E. McKenney wrote:
> > >
> > > > Why wouldn't the following have ACQUIRE semantics?
> > > >
> > > > atomic_inc(&var);
> > > > smp_mb__after_atomic();
> > > >
> > > > Is the issue that there is no actual value returned or some such?
> > >
> > > Yes, so that the inc is a load-store, and thus there is a load, we loose
> > > the value.
> > >
> > > But I see your point I think. Irrespective of still having the value,
> > > the ordering is preserved and nothing should pass across that.
> > >
> > > > So if I have something like this, the assertion really can trigger?
> > > >
> > > > WRITE_ONCE(x, 1); atomic_inc(&y);
> > > > r0 = xchg_release(&y, 5); smp_mb__after_atomic();
> > > > r1 = READ_ONCE(x);
> > > >
> > > >
> > > > WARN_ON(r0 == 0 && r1 == 0);
> > > >
> > > > I must confess that I am not seeing why we would want to allow this
> > > > outcome.
> > >
> > > No you are indeed quite right. I just wasn't creative enough. Thanks for
> > > the inspiration.
> >
> > Just to close this out, we agree that an smp_rmb() instead of
> > smp_mb__after_atomic() would *not* forbid this outcome, right?
>
> So that really hurts my brain. Per the normal rules that smp_rmb() would
> order the read of @x against the last ll of @y and per ll/sc ordering
> you then still don't get to make the WARN happen.
>
> On IRC you explained that your 8.1 LSE instructions are not in fact
> ordered by a smp_rmb, only by smp_wmb, which is 'surprising' since you
> really need to load the old value to compute the new value.
To be clear, it's only the ST* variants of the LSE instructions that are
treated as a write for the purposes of memory ordering, so these are the
non-*_return variants. It's not unlikely that other architectures will
exhibit the same behaviour (e.g. Power, RISC-V), because the CPU can
treat non-return atomics as "fire-and-forget" and have them handled
elsewhere in the memory subsystem, causing them to be treated similarly
to posted writes.
For the code snippet above, the second thread has no idea about the value
of y and so smp_rmb() is the wrong thing to be using imo. It really cares
about ordering the store to y before the read of x, so needs a full mb (i.e.
the test is more like 'R' than 'MP').
Also, wouldn't this problem also arise if your atomics were built using a
spinlock where unlock had release semantics?
Will
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-08-01 12:17 ` Will Deacon
@ 2017-08-01 12:52 ` Peter Zijlstra
2017-08-01 16:14 ` Paul E. McKenney
1 sibling, 0 replies; 43+ messages in thread
From: Peter Zijlstra @ 2017-08-01 12:52 UTC (permalink / raw)
To: Will Deacon
Cc: Paul E. McKenney, Boqun Feng, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap
On Tue, Aug 01, 2017 at 01:17:13PM +0100, Will Deacon wrote:
> Also, wouldn't this problem also arise if your atomics were built using a
> spinlock where unlock had release semantics?
I'm hoping none of our spnilock based atomics have weak ordering.
Spinlock based atomics are a little crazy to begin with, making them
weak *shudder*.
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-08-01 12:17 ` Will Deacon
2017-08-01 12:52 ` Peter Zijlstra
@ 2017-08-01 16:14 ` Paul E. McKenney
2017-08-01 16:42 ` Peter Zijlstra
` (2 more replies)
1 sibling, 3 replies; 43+ messages in thread
From: Paul E. McKenney @ 2017-08-01 16:14 UTC (permalink / raw)
To: Will Deacon
Cc: Peter Zijlstra, Boqun Feng, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap
On Tue, Aug 01, 2017 at 01:17:13PM +0100, Will Deacon wrote:
> On Tue, Aug 01, 2017 at 01:47:44PM +0200, Peter Zijlstra wrote:
> > On Tue, Aug 01, 2017 at 11:19:00AM +0100, Will Deacon wrote:
> > > On Tue, Aug 01, 2017 at 11:01:21AM +0200, Peter Zijlstra wrote:
> > > > On Mon, Jul 31, 2017 at 10:43:45AM -0700, Paul E. McKenney wrote:
> > > >
> > > > > Why wouldn't the following have ACQUIRE semantics?
> > > > >
> > > > > atomic_inc(&var);
> > > > > smp_mb__after_atomic();
> > > > >
> > > > > Is the issue that there is no actual value returned or some such?
> > > >
> > > > Yes, so that the inc is a load-store, and thus there is a load, we loose
> > > > the value.
> > > >
> > > > But I see your point I think. Irrespective of still having the value,
> > > > the ordering is preserved and nothing should pass across that.
> > > >
> > > > > So if I have something like this, the assertion really can trigger?
> > > > >
> > > > > WRITE_ONCE(x, 1); atomic_inc(&y);
> > > > > r0 = xchg_release(&y, 5); smp_mb__after_atomic();
> > > > > r1 = READ_ONCE(x);
> > > > >
> > > > >
> > > > > WARN_ON(r0 == 0 && r1 == 0);
> > > > >
> > > > > I must confess that I am not seeing why we would want to allow this
> > > > > outcome.
> > > >
> > > > No you are indeed quite right. I just wasn't creative enough. Thanks for
> > > > the inspiration.
> > >
> > > Just to close this out, we agree that an smp_rmb() instead of
> > > smp_mb__after_atomic() would *not* forbid this outcome, right?
> >
> > So that really hurts my brain. Per the normal rules that smp_rmb() would
> > order the read of @x against the last ll of @y and per ll/sc ordering
> > you then still don't get to make the WARN happen.
> >
> > On IRC you explained that your 8.1 LSE instructions are not in fact
> > ordered by a smp_rmb, only by smp_wmb, which is 'surprising' since you
> > really need to load the old value to compute the new value.
>
> To be clear, it's only the ST* variants of the LSE instructions that are
> treated as a write for the purposes of memory ordering, so these are the
> non-*_return variants. It's not unlikely that other architectures will
> exhibit the same behaviour (e.g. Power, RISC-V), because the CPU can
> treat non-return atomics as "fire-and-forget" and have them handled
> elsewhere in the memory subsystem, causing them to be treated similarly
> to posted writes.
>
> For the code snippet above, the second thread has no idea about the value
> of y and so smp_rmb() is the wrong thing to be using imo. It really cares
> about ordering the store to y before the read of x, so needs a full mb (i.e.
> the test is more like 'R' than 'MP').
>
> Also, wouldn't this problem also arise if your atomics were built using a
> spinlock where unlock had release semantics?
The current Linux kernel memory model forbids this outcome with smp_rmb(),
though I did have to work around the current lack of atomic_inc() using
xchg_relaxed(), so please review my litmus tests carefully.
C C-WillDeacon-MP+o-r+ai-rmb-o.litmus
(*
* Expected result: Never.
*
* Desired litmus test, with atomic_inc() emulated by xchg_relaxed():
*
* WRITE_ONCE(x, 1); atomic_inc(&y);
* r0 = xchg_release(&y, 5); smp_rmb();
* r1 = READ_ONCE(x);
*
*
* WARN_ON(r0 == 0 && r1 == 0);
*)
{
}
P0(int *x, int *y)
{
WRITE_ONCE(*x, 1);
r0 = xchg_release(y, 5);
}
P1(int *x, int *y)
{
r2 = xchg_relaxed(y, 1);
smp_rmb();
r1 = READ_ONCE(*x);
}
exists
(0:r0=0 /\ 1:r1=0)
Here is what herd thinks:
$ herd7 -bell strong-kernel.bell -cat weak-kernel.cat -macros linux.def ../litmus/manual/kernel/C-WillDeacon-MP+o-r+ai-rmb-o.litmus
Test C-WillDeacon-MP+o-r+ai-rmb-o Allowed
States 3
0:r0=0; 1:r1=1;
0:r0=1; 1:r1=0;
0:r0=1; 1:r1=1;
No
Witnesses
Positive: 0 Negative: 3
Condition exists (0:r0=0 /\ 1:r1=0)
Observation C-WillDeacon-MP+o-r+ai-rmb-o Never 0 3
Hash=0c3e25a94b38708a2c5ea11ff52c8077
I get the same answer from strong-kernel.cat (which is our best-guess
envelope over hardware guarantees), weak-kernel.cat (which is simplified
based on what people actually use), and proposal.cat (which is a candidate
model with further simplifications).
I converted this (possibly incorrectly) to PowerPC assembly:
PPC w-RMWl-r+w-RMWl-r.litmus
""
(*
* Does 3.0 Linux-kernel Power atomic_add_return() provide local
* barrier that orders prior stores against subsequent loads?
* Use the atomic_add_return() in both threads, but to different variables.
* And use the trailing-lwsync variant of atomic_add_return().
*)
(* 24-Aug-2011: ppcmem says "Sometimes" *)
{
0:r1=1; 0:r2=x; 0:r3=5; 0:r4=y; 0:r10=0 ; 0:r11=0;
1:r1=1; 1:r2=x; 1:r3=5; 1:r4=y; 1:r10=0 ; 1:r11=0;
}
P0 | P1 ;
stw r1,0(r2) | lwarx r11,r10,r4 ;
lwsync | stwcx. r1,r10,r4 ;
lwarx r11,r10,r4 | bne Fail1 ;
stwcx. r3,r10,r4 | lwsync ;
bne Fail0 | lwz r3,0(r2) ;
li r3,42 | Fail1: ;
Fail0: | ;
exists
(0:r11=0 /\ 0:r3=42 /\ 1:r3=0)
And ppcmem agrees with the linux-kernel memory model:
[ . . . ]
Found 82 : Prune count= 13946 seen_succs= 7453 7454 states
Found 83 : Prune count= 13997 seen_succs= 7490 7491 states
Found 84 : Prune count= 14007 seen_succs= 7506 7507 states
Found 85 : Prune count= 17229 seen_succs= 8889 8890 states
Found 86 : Prune count= 17235 seen_succs= 8897 8898 states
Test w-RMWl-r+w-RMWl-r Allowed
States 9
0:r3=5; 0:r11=0; 1:r3=0;
0:r3=5; 0:r11=0; 1:r3=1;
0:r3=5; 0:r11=0; 1:r3=5;
0:r3=5; 0:r11=1; 1:r3=0;
0:r3=5; 0:r11=1; 1:r3=1;
0:r3=42; 0:r11=0; 1:r3=1;
0:r3=42; 0:r11=0; 1:r3=5;
0:r3=42; 0:r11=1; 1:r3=0;
0:r3=42; 0:r11=1; 1:r3=1;
No (allowed not found)
Condition exists (0:r11=0 /\ 0:r3=42 /\ 1:r3=0)
Hash=58fb07516ac5697580c33e06a354f667
Observation w-RMWl-r+w-RMWl-r Never 0 9
So if ARM really needs the litmus test with smp_rmb() to be allowed,
we need to adjust the Linux-kernel memory model appropriately. Which
means that one of us needs to reach out to the usual suspects. Would
you like to do that, or would you like me to?
Thanx, Paul
^ permalink raw reply [flat|nested] 43+ messages in thread* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-08-01 16:14 ` Paul E. McKenney
@ 2017-08-01 16:42 ` Peter Zijlstra
2017-08-01 16:53 ` Will Deacon
2017-08-01 22:18 ` Paul E. McKenney
2017-08-01 18:37 ` Paul E. McKenney
2017-08-02 9:45 ` Will Deacon
2 siblings, 2 replies; 43+ messages in thread
From: Peter Zijlstra @ 2017-08-01 16:42 UTC (permalink / raw)
To: Paul E. McKenney
Cc: Will Deacon, Boqun Feng, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap
On Tue, Aug 01, 2017 at 09:14:12AM -0700, Paul E. McKenney wrote:
> So if ARM really needs the litmus test with smp_rmb() to be allowed,
> we need to adjust the Linux-kernel memory model appropriately. Which
> means that one of us needs to reach out to the usual suspects. Would
> you like to do that, or would you like me to?
I'm really sad ARM8.1 LSE breaks this stuff.. It is rather counter
intuitive (then again, we _are_ talking barriers).
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-08-01 16:42 ` Peter Zijlstra
@ 2017-08-01 16:53 ` Will Deacon
2017-08-01 22:18 ` Paul E. McKenney
1 sibling, 0 replies; 43+ messages in thread
From: Will Deacon @ 2017-08-01 16:53 UTC (permalink / raw)
To: Peter Zijlstra
Cc: Paul E. McKenney, Boqun Feng, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap
On Tue, Aug 01, 2017 at 06:42:00PM +0200, Peter Zijlstra wrote:
> On Tue, Aug 01, 2017 at 09:14:12AM -0700, Paul E. McKenney wrote:
> > So if ARM really needs the litmus test with smp_rmb() to be allowed,
> > we need to adjust the Linux-kernel memory model appropriately. Which
> > means that one of us needs to reach out to the usual suspects. Would
> > you like to do that, or would you like me to?
>
> I'm really sad ARM8.1 LSE breaks this stuff.. It is rather counter
> intuitive (then again, we _are_ talking barriers).
I can upgrade smp_rmb to smp_mb if I have to, but I still think that
code using smp_rmb() to order an operation that doesn't return a value is
weird.
Will
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-08-01 16:42 ` Peter Zijlstra
2017-08-01 16:53 ` Will Deacon
@ 2017-08-01 22:18 ` Paul E. McKenney
2017-08-02 8:46 ` Will Deacon
1 sibling, 1 reply; 43+ messages in thread
From: Paul E. McKenney @ 2017-08-01 22:18 UTC (permalink / raw)
To: Peter Zijlstra
Cc: Will Deacon, Boqun Feng, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap
On Tue, Aug 01, 2017 at 06:42:00PM +0200, Peter Zijlstra wrote:
> On Tue, Aug 01, 2017 at 09:14:12AM -0700, Paul E. McKenney wrote:
> > So if ARM really needs the litmus test with smp_rmb() to be allowed,
> > we need to adjust the Linux-kernel memory model appropriately. Which
> > means that one of us needs to reach out to the usual suspects. Would
> > you like to do that, or would you like me to?
>
> I'm really sad ARM8.1 LSE breaks this stuff.. It is rather counter
> intuitive (then again, we _are_ talking barriers).
No argument.
Then again, when we said that the Linux kernel memory model would
have a non-trivial rate of change, we weren't joking.
Will, is this the official description?
http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ddi0557a.b/index.html
If so, is B6.1 what we should be looking at?
Thanx, Paul
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-08-01 22:18 ` Paul E. McKenney
@ 2017-08-02 8:46 ` Will Deacon
0 siblings, 0 replies; 43+ messages in thread
From: Will Deacon @ 2017-08-02 8:46 UTC (permalink / raw)
To: Paul E. McKenney
Cc: Peter Zijlstra, Boqun Feng, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap
On Tue, Aug 01, 2017 at 03:18:18PM -0700, Paul E. McKenney wrote:
> On Tue, Aug 01, 2017 at 06:42:00PM +0200, Peter Zijlstra wrote:
> > On Tue, Aug 01, 2017 at 09:14:12AM -0700, Paul E. McKenney wrote:
> > > So if ARM really needs the litmus test with smp_rmb() to be allowed,
> > > we need to adjust the Linux-kernel memory model appropriately. Which
> > > means that one of us needs to reach out to the usual suspects. Would
> > > you like to do that, or would you like me to?
> >
> > I'm really sad ARM8.1 LSE breaks this stuff.. It is rather counter
> > intuitive (then again, we _are_ talking barriers).
>
> No argument.
>
> Then again, when we said that the Linux kernel memory model would
> have a non-trivial rate of change, we weren't joking.
>
> Will, is this the official description?
>
> http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ddi0557a.b/index.html
>
> If so, is B6.1 what we should be looking at?
Sorry it's so tricky to find. The architecture document is here:
https://static.docs.arm.com/ddi0487/b/DDI0487B_a_armv8_arm.pdf
and in section C3.2.13 ("Atomic memory operations") it states:
| The ST<OP> instructions are not regarded as doing a read for the purpose
| of a DMB LD barrier.
Will
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-08-01 16:14 ` Paul E. McKenney
2017-08-01 16:42 ` Peter Zijlstra
@ 2017-08-01 18:37 ` Paul E. McKenney
2017-08-02 9:45 ` Will Deacon
2 siblings, 0 replies; 43+ messages in thread
From: Paul E. McKenney @ 2017-08-01 18:37 UTC (permalink / raw)
To: Will Deacon
Cc: Peter Zijlstra, Boqun Feng, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap, stern
On Tue, Aug 01, 2017 at 09:14:12AM -0700, Paul E. McKenney wrote:
> On Tue, Aug 01, 2017 at 01:17:13PM +0100, Will Deacon wrote:
> > On Tue, Aug 01, 2017 at 01:47:44PM +0200, Peter Zijlstra wrote:
> > > On Tue, Aug 01, 2017 at 11:19:00AM +0100, Will Deacon wrote:
> > > > On Tue, Aug 01, 2017 at 11:01:21AM +0200, Peter Zijlstra wrote:
> > > > > On Mon, Jul 31, 2017 at 10:43:45AM -0700, Paul E. McKenney wrote:
> > > > >
> > > > > > Why wouldn't the following have ACQUIRE semantics?
> > > > > >
> > > > > > atomic_inc(&var);
> > > > > > smp_mb__after_atomic();
> > > > > >
> > > > > > Is the issue that there is no actual value returned or some such?
> > > > >
> > > > > Yes, so that the inc is a load-store, and thus there is a load, we loose
> > > > > the value.
> > > > >
> > > > > But I see your point I think. Irrespective of still having the value,
> > > > > the ordering is preserved and nothing should pass across that.
> > > > >
> > > > > > So if I have something like this, the assertion really can trigger?
> > > > > >
> > > > > > WRITE_ONCE(x, 1); atomic_inc(&y);
> > > > > > r0 = xchg_release(&y, 5); smp_mb__after_atomic();
> > > > > > r1 = READ_ONCE(x);
> > > > > >
> > > > > >
> > > > > > WARN_ON(r0 == 0 && r1 == 0);
> > > > > >
> > > > > > I must confess that I am not seeing why we would want to allow this
> > > > > > outcome.
> > > > >
> > > > > No you are indeed quite right. I just wasn't creative enough. Thanks for
> > > > > the inspiration.
> > > >
> > > > Just to close this out, we agree that an smp_rmb() instead of
> > > > smp_mb__after_atomic() would *not* forbid this outcome, right?
> > >
> > > So that really hurts my brain. Per the normal rules that smp_rmb() would
> > > order the read of @x against the last ll of @y and per ll/sc ordering
> > > you then still don't get to make the WARN happen.
> > >
> > > On IRC you explained that your 8.1 LSE instructions are not in fact
> > > ordered by a smp_rmb, only by smp_wmb, which is 'surprising' since you
> > > really need to load the old value to compute the new value.
> >
> > To be clear, it's only the ST* variants of the LSE instructions that are
> > treated as a write for the purposes of memory ordering, so these are the
> > non-*_return variants. It's not unlikely that other architectures will
> > exhibit the same behaviour (e.g. Power, RISC-V), because the CPU can
> > treat non-return atomics as "fire-and-forget" and have them handled
> > elsewhere in the memory subsystem, causing them to be treated similarly
> > to posted writes.
> >
> > For the code snippet above, the second thread has no idea about the value
> > of y and so smp_rmb() is the wrong thing to be using imo. It really cares
> > about ordering the store to y before the read of x, so needs a full mb (i.e.
> > the test is more like 'R' than 'MP').
> >
> > Also, wouldn't this problem also arise if your atomics were built using a
> > spinlock where unlock had release semantics?
And responding more directly to the bit about spinlocks after a side
discussion with Alan Stern, both the xchg_release() and the atomic_inc()
are operating on the same variable, namely "y". Even by the very weak
"roach motel" locking semantics, this outcome would be forbidden.
But if you have hardware that allows this, let's all discuss and get
it hashed out...
Thanx, Paul
Thanx, Paul
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-08-01 16:14 ` Paul E. McKenney
2017-08-01 16:42 ` Peter Zijlstra
2017-08-01 18:37 ` Paul E. McKenney
@ 2017-08-02 9:45 ` Will Deacon
2017-08-02 16:17 ` Paul E. McKenney
2017-08-03 14:05 ` Boqun Feng
2 siblings, 2 replies; 43+ messages in thread
From: Will Deacon @ 2017-08-02 9:45 UTC (permalink / raw)
To: Paul E. McKenney
Cc: Peter Zijlstra, Boqun Feng, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap
Hi Paul,
On Tue, Aug 01, 2017 at 09:14:12AM -0700, Paul E. McKenney wrote:
> On Tue, Aug 01, 2017 at 01:17:13PM +0100, Will Deacon wrote:
> > On Tue, Aug 01, 2017 at 01:47:44PM +0200, Peter Zijlstra wrote:
> > > On Tue, Aug 01, 2017 at 11:19:00AM +0100, Will Deacon wrote:
> > > > On Tue, Aug 01, 2017 at 11:01:21AM +0200, Peter Zijlstra wrote:
> > > > > On Mon, Jul 31, 2017 at 10:43:45AM -0700, Paul E. McKenney wrote:
> > > > > > So if I have something like this, the assertion really can trigger?
> > > > > >
> > > > > > WRITE_ONCE(x, 1); atomic_inc(&y);
> > > > > > r0 = xchg_release(&y, 5); smp_mb__after_atomic();
> > > > > > r1 = READ_ONCE(x);
> > > > > >
> > > > > >
> > > > > > WARN_ON(r0 == 0 && r1 == 0);
> > > > > >
> > > > > > I must confess that I am not seeing why we would want to allow this
> > > > > > outcome.
> > > > >
> > > > > No you are indeed quite right. I just wasn't creative enough. Thanks for
> > > > > the inspiration.
> > > >
> > > > Just to close this out, we agree that an smp_rmb() instead of
> > > > smp_mb__after_atomic() would *not* forbid this outcome, right?
> > >
> > > So that really hurts my brain. Per the normal rules that smp_rmb() would
> > > order the read of @x against the last ll of @y and per ll/sc ordering
> > > you then still don't get to make the WARN happen.
> > >
> > > On IRC you explained that your 8.1 LSE instructions are not in fact
> > > ordered by a smp_rmb, only by smp_wmb, which is 'surprising' since you
> > > really need to load the old value to compute the new value.
> >
> > To be clear, it's only the ST* variants of the LSE instructions that are
> > treated as a write for the purposes of memory ordering, so these are the
> > non-*_return variants. It's not unlikely that other architectures will
> > exhibit the same behaviour (e.g. Power, RISC-V), because the CPU can
> > treat non-return atomics as "fire-and-forget" and have them handled
> > elsewhere in the memory subsystem, causing them to be treated similarly
> > to posted writes.
> >
> > For the code snippet above, the second thread has no idea about the value
> > of y and so smp_rmb() is the wrong thing to be using imo. It really cares
> > about ordering the store to y before the read of x, so needs a full mb (i.e.
> > the test is more like 'R' than 'MP').
> >
> > Also, wouldn't this problem also arise if your atomics were built using a
> > spinlock where unlock had release semantics?
>
> The current Linux kernel memory model forbids this outcome with smp_rmb(),
> though I did have to work around the current lack of atomic_inc() using
> xchg_relaxed(), so please review my litmus tests carefully.
It's worth noting that we don't have the problem with any value-returning
atomics, so all flavours of xchg in this test would be forbidden on arm64
too.
> C C-WillDeacon-MP+o-r+ai-rmb-o.litmus
>
> (*
> * Expected result: Never.
> *
> * Desired litmus test, with atomic_inc() emulated by xchg_relaxed():
> *
> * WRITE_ONCE(x, 1); atomic_inc(&y);
> * r0 = xchg_release(&y, 5); smp_rmb();
> * r1 = READ_ONCE(x);
> *
> *
> * WARN_ON(r0 == 0 && r1 == 0);
> *)
>
> {
> }
>
> P0(int *x, int *y)
> {
> WRITE_ONCE(*x, 1);
> r0 = xchg_release(y, 5);
> }
>
> P1(int *x, int *y)
> {
> r2 = xchg_relaxed(y, 1);
> smp_rmb();
> r1 = READ_ONCE(*x);
> }
>
> exists
> (0:r0=0 /\ 1:r1=0)
>
> Here is what herd thinks:
>
> $ herd7 -bell strong-kernel.bell -cat weak-kernel.cat -macros linux.def ../litmus/manual/kernel/C-WillDeacon-MP+o-r+ai-rmb-o.litmus
> Test C-WillDeacon-MP+o-r+ai-rmb-o Allowed
> States 3
> 0:r0=0; 1:r1=1;
> 0:r0=1; 1:r1=0;
> 0:r0=1; 1:r1=1;
> No
> Witnesses
> Positive: 0 Negative: 3
> Condition exists (0:r0=0 /\ 1:r1=0)
> Observation C-WillDeacon-MP+o-r+ai-rmb-o Never 0 3
> Hash=0c3e25a94b38708a2c5ea11ff52c8077
>
> I get the same answer from strong-kernel.cat (which is our best-guess
> envelope over hardware guarantees), weak-kernel.cat (which is simplified
> based on what people actually use), and proposal.cat (which is a candidate
> model with further simplifications).
>
> I converted this (possibly incorrectly) to PowerPC assembly:
>
> PPC w-RMWl-r+w-RMWl-r.litmus
> ""
> (*
> * Does 3.0 Linux-kernel Power atomic_add_return() provide local
> * barrier that orders prior stores against subsequent loads?
> * Use the atomic_add_return() in both threads, but to different variables.
> * And use the trailing-lwsync variant of atomic_add_return().
> *)
> (* 24-Aug-2011: ppcmem says "Sometimes" *)
> {
> 0:r1=1; 0:r2=x; 0:r3=5; 0:r4=y; 0:r10=0 ; 0:r11=0;
> 1:r1=1; 1:r2=x; 1:r3=5; 1:r4=y; 1:r10=0 ; 1:r11=0;
> }
> P0 | P1 ;
> stw r1,0(r2) | lwarx r11,r10,r4 ;
> lwsync | stwcx. r1,r10,r4 ;
> lwarx r11,r10,r4 | bne Fail1 ;
> stwcx. r3,r10,r4 | lwsync ;
> bne Fail0 | lwz r3,0(r2) ;
> li r3,42 | Fail1: ;
> Fail0: | ;
>
>
> exists
> (0:r11=0 /\ 0:r3=42 /\ 1:r3=0)
>
> And ppcmem agrees with the linux-kernel memory model:
>
> [ . . . ]
>
> Found 82 : Prune count= 13946 seen_succs= 7453 7454 states
> Found 83 : Prune count= 13997 seen_succs= 7490 7491 states
> Found 84 : Prune count= 14007 seen_succs= 7506 7507 states
> Found 85 : Prune count= 17229 seen_succs= 8889 8890 states
> Found 86 : Prune count= 17235 seen_succs= 8897 8898 states
> Test w-RMWl-r+w-RMWl-r Allowed
> States 9
> 0:r3=5; 0:r11=0; 1:r3=0;
> 0:r3=5; 0:r11=0; 1:r3=1;
> 0:r3=5; 0:r11=0; 1:r3=5;
> 0:r3=5; 0:r11=1; 1:r3=0;
> 0:r3=5; 0:r11=1; 1:r3=1;
> 0:r3=42; 0:r11=0; 1:r3=1;
> 0:r3=42; 0:r11=0; 1:r3=5;
> 0:r3=42; 0:r11=1; 1:r3=0;
> 0:r3=42; 0:r11=1; 1:r3=1;
> No (allowed not found)
> Condition exists (0:r11=0 /\ 0:r3=42 /\ 1:r3=0)
> Hash=58fb07516ac5697580c33e06a354f667
> Observation w-RMWl-r+w-RMWl-r Never 0 9
>
> So if ARM really needs the litmus test with smp_rmb() to be allowed,
> we need to adjust the Linux-kernel memory model appropriately. Which
> means that one of us needs to reach out to the usual suspects. Would
> you like to do that, or would you like me to?
If you don't mind doing it, then that would be great, thanks. Do shout if
you need me to help with anything, though!
Will
^ permalink raw reply [flat|nested] 43+ messages in thread* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-08-02 9:45 ` Will Deacon
@ 2017-08-02 16:17 ` Paul E. McKenney
2017-08-03 14:05 ` Boqun Feng
1 sibling, 0 replies; 43+ messages in thread
From: Paul E. McKenney @ 2017-08-02 16:17 UTC (permalink / raw)
To: Will Deacon
Cc: Peter Zijlstra, Boqun Feng, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap
On Wed, Aug 02, 2017 at 10:45:32AM +0100, Will Deacon wrote:
> Hi Paul,
>
> On Tue, Aug 01, 2017 at 09:14:12AM -0700, Paul E. McKenney wrote:
> > On Tue, Aug 01, 2017 at 01:17:13PM +0100, Will Deacon wrote:
> > > On Tue, Aug 01, 2017 at 01:47:44PM +0200, Peter Zijlstra wrote:
> > > > On Tue, Aug 01, 2017 at 11:19:00AM +0100, Will Deacon wrote:
> > > > > On Tue, Aug 01, 2017 at 11:01:21AM +0200, Peter Zijlstra wrote:
> > > > > > On Mon, Jul 31, 2017 at 10:43:45AM -0700, Paul E. McKenney wrote:
> > > > > > > So if I have something like this, the assertion really can trigger?
> > > > > > >
> > > > > > > WRITE_ONCE(x, 1); atomic_inc(&y);
> > > > > > > r0 = xchg_release(&y, 5); smp_mb__after_atomic();
> > > > > > > r1 = READ_ONCE(x);
> > > > > > >
> > > > > > >
> > > > > > > WARN_ON(r0 == 0 && r1 == 0);
> > > > > > >
> > > > > > > I must confess that I am not seeing why we would want to allow this
> > > > > > > outcome.
> > > > > >
> > > > > > No you are indeed quite right. I just wasn't creative enough. Thanks for
> > > > > > the inspiration.
> > > > >
> > > > > Just to close this out, we agree that an smp_rmb() instead of
> > > > > smp_mb__after_atomic() would *not* forbid this outcome, right?
> > > >
> > > > So that really hurts my brain. Per the normal rules that smp_rmb() would
> > > > order the read of @x against the last ll of @y and per ll/sc ordering
> > > > you then still don't get to make the WARN happen.
> > > >
> > > > On IRC you explained that your 8.1 LSE instructions are not in fact
> > > > ordered by a smp_rmb, only by smp_wmb, which is 'surprising' since you
> > > > really need to load the old value to compute the new value.
> > >
> > > To be clear, it's only the ST* variants of the LSE instructions that are
> > > treated as a write for the purposes of memory ordering, so these are the
> > > non-*_return variants. It's not unlikely that other architectures will
> > > exhibit the same behaviour (e.g. Power, RISC-V), because the CPU can
> > > treat non-return atomics as "fire-and-forget" and have them handled
> > > elsewhere in the memory subsystem, causing them to be treated similarly
> > > to posted writes.
> > >
> > > For the code snippet above, the second thread has no idea about the value
> > > of y and so smp_rmb() is the wrong thing to be using imo. It really cares
> > > about ordering the store to y before the read of x, so needs a full mb (i.e.
> > > the test is more like 'R' than 'MP').
> > >
> > > Also, wouldn't this problem also arise if your atomics were built using a
> > > spinlock where unlock had release semantics?
> >
> > The current Linux kernel memory model forbids this outcome with smp_rmb(),
> > though I did have to work around the current lack of atomic_inc() using
> > xchg_relaxed(), so please review my litmus tests carefully.
>
> It's worth noting that we don't have the problem with any value-returning
> atomics, so all flavours of xchg in this test would be forbidden on arm64
> too.
Plus after upgrading to the latest and greatest version of herd,
atomic_inc() worked just fine. (Hey, I -try- to keep up!) The updated
litmus test is here:
https://github.com/paulmckrcu/litmus/blob/master/manual/kernel/C-WillDeacon-MP%2Bo-r%2Bai-rmb-o.litmus
Same outcome. Alan Stern is looking into what might be adjusted.
Of course, there is no guarantee that this will turn out to be reasonable
or for that matter acceptable to the usual suspects, but if feasible we
should at least see what this does to the model.
> > C C-WillDeacon-MP+o-r+ai-rmb-o.litmus
> >
> > (*
> > * Expected result: Never.
> > *
> > * Desired litmus test, with atomic_inc() emulated by xchg_relaxed():
> > *
> > * WRITE_ONCE(x, 1); atomic_inc(&y);
> > * r0 = xchg_release(&y, 5); smp_rmb();
> > * r1 = READ_ONCE(x);
> > *
> > *
> > * WARN_ON(r0 == 0 && r1 == 0);
> > *)
> >
> > {
> > }
> >
> > P0(int *x, int *y)
> > {
> > WRITE_ONCE(*x, 1);
> > r0 = xchg_release(y, 5);
> > }
> >
> > P1(int *x, int *y)
> > {
> > r2 = xchg_relaxed(y, 1);
> > smp_rmb();
> > r1 = READ_ONCE(*x);
> > }
> >
> > exists
> > (0:r0=0 /\ 1:r1=0)
> >
> > Here is what herd thinks:
> >
> > $ herd7 -bell strong-kernel.bell -cat weak-kernel.cat -macros linux.def ../litmus/manual/kernel/C-WillDeacon-MP+o-r+ai-rmb-o.litmus
> > Test C-WillDeacon-MP+o-r+ai-rmb-o Allowed
> > States 3
> > 0:r0=0; 1:r1=1;
> > 0:r0=1; 1:r1=0;
> > 0:r0=1; 1:r1=1;
> > No
> > Witnesses
> > Positive: 0 Negative: 3
> > Condition exists (0:r0=0 /\ 1:r1=0)
> > Observation C-WillDeacon-MP+o-r+ai-rmb-o Never 0 3
> > Hash=0c3e25a94b38708a2c5ea11ff52c8077
> >
> > I get the same answer from strong-kernel.cat (which is our best-guess
> > envelope over hardware guarantees), weak-kernel.cat (which is simplified
> > based on what people actually use), and proposal.cat (which is a candidate
> > model with further simplifications).
> >
> > I converted this (possibly incorrectly) to PowerPC assembly:
> >
> > PPC w-RMWl-r+w-RMWl-r.litmus
> > ""
> > (*
> > * Does 3.0 Linux-kernel Power atomic_add_return() provide local
> > * barrier that orders prior stores against subsequent loads?
> > * Use the atomic_add_return() in both threads, but to different variables.
> > * And use the trailing-lwsync variant of atomic_add_return().
> > *)
> > (* 24-Aug-2011: ppcmem says "Sometimes" *)
> > {
> > 0:r1=1; 0:r2=x; 0:r3=5; 0:r4=y; 0:r10=0 ; 0:r11=0;
> > 1:r1=1; 1:r2=x; 1:r3=5; 1:r4=y; 1:r10=0 ; 1:r11=0;
> > }
> > P0 | P1 ;
> > stw r1,0(r2) | lwarx r11,r10,r4 ;
> > lwsync | stwcx. r1,r10,r4 ;
> > lwarx r11,r10,r4 | bne Fail1 ;
> > stwcx. r3,r10,r4 | lwsync ;
> > bne Fail0 | lwz r3,0(r2) ;
> > li r3,42 | Fail1: ;
> > Fail0: | ;
> >
> >
> > exists
> > (0:r11=0 /\ 0:r3=42 /\ 1:r3=0)
> >
> > And ppcmem agrees with the linux-kernel memory model:
> >
> > [ . . . ]
> >
> > Found 82 : Prune count= 13946 seen_succs= 7453 7454 states
> > Found 83 : Prune count= 13997 seen_succs= 7490 7491 states
> > Found 84 : Prune count= 14007 seen_succs= 7506 7507 states
> > Found 85 : Prune count= 17229 seen_succs= 8889 8890 states
> > Found 86 : Prune count= 17235 seen_succs= 8897 8898 states
> > Test w-RMWl-r+w-RMWl-r Allowed
> > States 9
> > 0:r3=5; 0:r11=0; 1:r3=0;
> > 0:r3=5; 0:r11=0; 1:r3=1;
> > 0:r3=5; 0:r11=0; 1:r3=5;
> > 0:r3=5; 0:r11=1; 1:r3=0;
> > 0:r3=5; 0:r11=1; 1:r3=1;
> > 0:r3=42; 0:r11=0; 1:r3=1;
> > 0:r3=42; 0:r11=0; 1:r3=5;
> > 0:r3=42; 0:r11=1; 1:r3=0;
> > 0:r3=42; 0:r11=1; 1:r3=1;
> > No (allowed not found)
> > Condition exists (0:r11=0 /\ 0:r3=42 /\ 1:r3=0)
> > Hash=58fb07516ac5697580c33e06a354f667
> > Observation w-RMWl-r+w-RMWl-r Never 0 9
> >
> > So if ARM really needs the litmus test with smp_rmb() to be allowed,
> > we need to adjust the Linux-kernel memory model appropriately. Which
> > means that one of us needs to reach out to the usual suspects. Would
> > you like to do that, or would you like me to?
>
> If you don't mind doing it, then that would be great, thanks. Do shout if
> you need me to help with anything, though!
You will be copied, just to cut out the timezone delays if nothing else.
Thanx, Paul
^ permalink raw reply [flat|nested] 43+ messages in thread* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-08-02 9:45 ` Will Deacon
2017-08-02 16:17 ` Paul E. McKenney
@ 2017-08-03 14:05 ` Boqun Feng
2017-08-03 14:55 ` Paul E. McKenney
1 sibling, 1 reply; 43+ messages in thread
From: Boqun Feng @ 2017-08-03 14:05 UTC (permalink / raw)
To: Will Deacon
Cc: Paul E. McKenney, Peter Zijlstra, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap
[-- Attachment #1: Type: text/plain, Size: 1666 bytes --]
Hi Will,
On Wed, Aug 02, 2017 at 10:45:32AM +0100, Will Deacon wrote:
[...]
>
> It's worth noting that we don't have the problem with any value-returning
> atomics, so all flavours of xchg in this test would be forbidden on arm64
> too.
>
> > C C-WillDeacon-MP+o-r+ai-rmb-o.litmus
> >
> > (*
> > * Expected result: Never.
> > *
> > * Desired litmus test, with atomic_inc() emulated by xchg_relaxed():
> > *
> > * WRITE_ONCE(x, 1); atomic_inc(&y);
> > * r0 = xchg_release(&y, 5); smp_rmb();
> > * r1 = READ_ONCE(x);
> > *
> > *
> > * WARN_ON(r0 == 0 && r1 == 0);
> > *)
> >
> > {
> > }
> >
> > P0(int *x, int *y)
> > {
> > WRITE_ONCE(*x, 1);
> > r0 = xchg_release(y, 5);
> > }
> >
> > P1(int *x, int *y)
> > {
> > r2 = xchg_relaxed(y, 1);
> > smp_rmb();
> > r1 = READ_ONCE(*x);
> > }
> >
> > exists
> > (0:r0=0 /\ 1:r1=0)
> >
How about a litmus test like this?
C C-AMO-global-transitivity.litmus
{
}
P0(int *x, int *y)
{
WRITE_ONCE(*x, 1);
r0 = xchg_release(y, 5);
}
P1(int *y, int *z)
{
atomic_inc(y);
smp_mb();
r1 = READ_ONCE(*z);
}
P2(int *x, int *z)
{
WRITE_ONCE(*z, 1);
smp_mb();
r2 = READ_ONCE(*x);
}
exists
(0:r0=0 /\ 1:r1=0 /\ 2:r2=0 )
Should we forbid the outcome in the exists-clause? I ask because I want
to know whether we can just treat atomic_inc() as a store, because if I
replace atomic_inc() with a WRITE(*y, 6), IIUC, the current model says
this could happen.
Thoughts?
Regards,
Boqun
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]
^ permalink raw reply [flat|nested] 43+ messages in thread* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-08-03 14:05 ` Boqun Feng
@ 2017-08-03 14:55 ` Paul E. McKenney
2017-08-03 16:12 ` Will Deacon
0 siblings, 1 reply; 43+ messages in thread
From: Paul E. McKenney @ 2017-08-03 14:55 UTC (permalink / raw)
To: Boqun Feng
Cc: Will Deacon, Peter Zijlstra, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap
On Thu, Aug 03, 2017 at 10:05:16PM +0800, Boqun Feng wrote:
> Hi Will,
>
> On Wed, Aug 02, 2017 at 10:45:32AM +0100, Will Deacon wrote:
> [...]
> >
> > It's worth noting that we don't have the problem with any value-returning
> > atomics, so all flavours of xchg in this test would be forbidden on arm64
> > too.
> >
> > > C C-WillDeacon-MP+o-r+ai-rmb-o.litmus
> > >
> > > (*
> > > * Expected result: Never.
> > > *
> > > * Desired litmus test, with atomic_inc() emulated by xchg_relaxed():
> > > *
> > > * WRITE_ONCE(x, 1); atomic_inc(&y);
> > > * r0 = xchg_release(&y, 5); smp_rmb();
> > > * r1 = READ_ONCE(x);
> > > *
> > > *
> > > * WARN_ON(r0 == 0 && r1 == 0);
> > > *)
> > >
> > > {
> > > }
> > >
> > > P0(int *x, int *y)
> > > {
> > > WRITE_ONCE(*x, 1);
> > > r0 = xchg_release(y, 5);
> > > }
> > >
> > > P1(int *x, int *y)
> > > {
> > > r2 = xchg_relaxed(y, 1);
> > > smp_rmb();
> > > r1 = READ_ONCE(*x);
> > > }
> > >
> > > exists
> > > (0:r0=0 /\ 1:r1=0)
> > >
>
> How about a litmus test like this?
>
> C C-AMO-global-transitivity.litmus
>
> {
> }
>
> P0(int *x, int *y)
> {
> WRITE_ONCE(*x, 1);
> r0 = xchg_release(y, 5);
> }
>
> P1(int *y, int *z)
> {
> atomic_inc(y);
> smp_mb();
I am going to guess that the smp_mb() enforces the needed ordering,
but Will will let me know. ;-)
Thanx, Paul
> r1 = READ_ONCE(*z);
> }
>
> P2(int *x, int *z)
> {
> WRITE_ONCE(*z, 1);
> smp_mb();
> r2 = READ_ONCE(*x);
> }
>
> exists
> (0:r0=0 /\ 1:r1=0 /\ 2:r2=0 )
>
> Should we forbid the outcome in the exists-clause? I ask because I want
> to know whether we can just treat atomic_inc() as a store, because if I
> replace atomic_inc() with a WRITE(*y, 6), IIUC, the current model says
> this could happen.
>
> Thoughts?
>
> Regards,
> Boqun
^ permalink raw reply [flat|nested] 43+ messages in thread* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-08-03 14:55 ` Paul E. McKenney
@ 2017-08-03 16:12 ` Will Deacon
2017-08-03 16:58 ` Paul E. McKenney
0 siblings, 1 reply; 43+ messages in thread
From: Will Deacon @ 2017-08-03 16:12 UTC (permalink / raw)
To: Paul E. McKenney
Cc: Boqun Feng, Peter Zijlstra, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap
On Thu, Aug 03, 2017 at 07:55:14AM -0700, Paul E. McKenney wrote:
> On Thu, Aug 03, 2017 at 10:05:16PM +0800, Boqun Feng wrote:
> > Hi Will,
> >
> > On Wed, Aug 02, 2017 at 10:45:32AM +0100, Will Deacon wrote:
> > [...]
> > >
> > > It's worth noting that we don't have the problem with any value-returning
> > > atomics, so all flavours of xchg in this test would be forbidden on arm64
> > > too.
> > >
> > > > C C-WillDeacon-MP+o-r+ai-rmb-o.litmus
> > > >
> > > > (*
> > > > * Expected result: Never.
> > > > *
> > > > * Desired litmus test, with atomic_inc() emulated by xchg_relaxed():
> > > > *
> > > > * WRITE_ONCE(x, 1); atomic_inc(&y);
> > > > * r0 = xchg_release(&y, 5); smp_rmb();
> > > > * r1 = READ_ONCE(x);
> > > > *
> > > > *
> > > > * WARN_ON(r0 == 0 && r1 == 0);
> > > > *)
> > > >
> > > > {
> > > > }
> > > >
> > > > P0(int *x, int *y)
> > > > {
> > > > WRITE_ONCE(*x, 1);
> > > > r0 = xchg_release(y, 5);
> > > > }
> > > >
> > > > P1(int *x, int *y)
> > > > {
> > > > r2 = xchg_relaxed(y, 1);
> > > > smp_rmb();
> > > > r1 = READ_ONCE(*x);
> > > > }
> > > >
> > > > exists
> > > > (0:r0=0 /\ 1:r1=0)
> > > >
> >
> > How about a litmus test like this?
> >
> > C C-AMO-global-transitivity.litmus
> >
> > {
> > }
> >
> > P0(int *x, int *y)
> > {
> > WRITE_ONCE(*x, 1);
> > r0 = xchg_release(y, 5);
> > }
> >
> > P1(int *y, int *z)
> > {
> > atomic_inc(y);
> > smp_mb();
>
> I am going to guess that the smp_mb() enforces the needed ordering,
> but Will will let me know. ;-)
Yup, that would be forbidden on arm64, and would also be forbidden if
you used WRITE_ONCE instead of atomic_inc (remember that we recently
became multi-copy atomic).
Will
^ permalink raw reply [flat|nested] 43+ messages in thread* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-08-03 16:12 ` Will Deacon
@ 2017-08-03 16:58 ` Paul E. McKenney
0 siblings, 0 replies; 43+ messages in thread
From: Paul E. McKenney @ 2017-08-03 16:58 UTC (permalink / raw)
To: Will Deacon
Cc: Boqun Feng, Peter Zijlstra, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap
On Thu, Aug 03, 2017 at 05:12:24PM +0100, Will Deacon wrote:
> On Thu, Aug 03, 2017 at 07:55:14AM -0700, Paul E. McKenney wrote:
> > On Thu, Aug 03, 2017 at 10:05:16PM +0800, Boqun Feng wrote:
> > > Hi Will,
> > >
> > > On Wed, Aug 02, 2017 at 10:45:32AM +0100, Will Deacon wrote:
> > > [...]
> > > >
> > > > It's worth noting that we don't have the problem with any value-returning
> > > > atomics, so all flavours of xchg in this test would be forbidden on arm64
> > > > too.
> > > >
> > > > > C C-WillDeacon-MP+o-r+ai-rmb-o.litmus
> > > > >
> > > > > (*
> > > > > * Expected result: Never.
> > > > > *
> > > > > * Desired litmus test, with atomic_inc() emulated by xchg_relaxed():
> > > > > *
> > > > > * WRITE_ONCE(x, 1); atomic_inc(&y);
> > > > > * r0 = xchg_release(&y, 5); smp_rmb();
> > > > > * r1 = READ_ONCE(x);
> > > > > *
> > > > > *
> > > > > * WARN_ON(r0 == 0 && r1 == 0);
> > > > > *)
> > > > >
> > > > > {
> > > > > }
> > > > >
> > > > > P0(int *x, int *y)
> > > > > {
> > > > > WRITE_ONCE(*x, 1);
> > > > > r0 = xchg_release(y, 5);
> > > > > }
> > > > >
> > > > > P1(int *x, int *y)
> > > > > {
> > > > > r2 = xchg_relaxed(y, 1);
> > > > > smp_rmb();
> > > > > r1 = READ_ONCE(*x);
> > > > > }
> > > > >
> > > > > exists
> > > > > (0:r0=0 /\ 1:r1=0)
> > > > >
> > >
> > > How about a litmus test like this?
> > >
> > > C C-AMO-global-transitivity.litmus
> > >
> > > {
> > > }
> > >
> > > P0(int *x, int *y)
> > > {
> > > WRITE_ONCE(*x, 1);
> > > r0 = xchg_release(y, 5);
> > > }
> > >
> > > P1(int *y, int *z)
> > > {
> > > atomic_inc(y);
> > > smp_mb();
> >
> > I am going to guess that the smp_mb() enforces the needed ordering,
> > but Will will let me know. ;-)
>
> Yup, that would be forbidden on arm64, and would also be forbidden if
> you used WRITE_ONCE instead of atomic_inc (remember that we recently
> became multi-copy atomic).
Thank you for the confirmation!
Thanx, Paul
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-08-01 9:01 ` Peter Zijlstra
2017-08-01 10:19 ` Will Deacon
@ 2017-08-01 13:35 ` Paul E. McKenney
1 sibling, 0 replies; 43+ messages in thread
From: Paul E. McKenney @ 2017-08-01 13:35 UTC (permalink / raw)
To: Peter Zijlstra
Cc: Boqun Feng, Will Deacon, linux-kernel, Ingo Molnar,
Thomas Gleixner, Randy Dunlap
On Tue, Aug 01, 2017 at 11:01:21AM +0200, Peter Zijlstra wrote:
> On Mon, Jul 31, 2017 at 10:43:45AM -0700, Paul E. McKenney wrote:
>
> > Why wouldn't the following have ACQUIRE semantics?
> >
> > atomic_inc(&var);
> > smp_mb__after_atomic();
> >
> > Is the issue that there is no actual value returned or some such?
>
> Yes, so that the inc is a load-store, and thus there is a load, we loose
> the value.
>
> But I see your point I think. Irrespective of still having the value,
> the ordering is preserved and nothing should pass across that.
>
> > So if I have something like this, the assertion really can trigger?
> >
> > WRITE_ONCE(x, 1); atomic_inc(&y);
> > r0 = xchg_release(&y, 5); smp_mb__after_atomic();
> > r1 = READ_ONCE(x);
> >
> >
> > WARN_ON(r0 == 0 && r1 == 0);
> >
> > I must confess that I am not seeing why we would want to allow this
> > outcome.
>
> No you are indeed quite right. I just wasn't creative enough. Thanks for
> the inspiration.
Whew! You guys had me worried there for a bit. ;-)
Thanx, Paul
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: [RFC][PATCH v3]: documentation,atomic: Add new documents
2017-07-26 11:53 ` [RFC][PATCH v3]: documentation,atomic: Add new documents Peter Zijlstra
2017-07-26 12:47 ` Boqun Feng
@ 2017-07-26 16:28 ` Randy Dunlap
1 sibling, 0 replies; 43+ messages in thread
From: Randy Dunlap @ 2017-07-26 16:28 UTC (permalink / raw)
To: Peter Zijlstra, Boqun Feng
Cc: Will Deacon, Paul McKenney, linux-kernel, Ingo Molnar, Thomas Gleixner
nits... <chirping>
On 07/26/2017 04:53 AM, Peter Zijlstra wrote:
> ---
> Subject: documentation,atomic: Add new documents
> From: Peter Zijlstra <peterz@infradead.org>
> Date: Mon Jun 12 14:50:27 CEST 2017
>
> Since we've vastly expanded the atomic_t interface in recent years the
> existing documentation is woefully out of date and people seem to get
> confused a bit.
>
> Start a new document to hopefully better explain the current state of
> affairs.
>
> The old atomic_ops.txt also covers bitmaps and a few more details so
> this is not a full replacement and we'll therefore keep that document
> around until such a time that we've managed to write more text to cover
> its entire.
>
> Also please, ReST people, go away.
>
> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> ---
> Documentation/atomic_bitops.txt | 66 ++++++++++++
> Documentation/atomic_t.txt | 200 ++++++++++++++++++++++++++++++++++++++
> Documentation/memory-barriers.txt | 88 ----------------
> 3 files changed, 269 insertions(+), 85 deletions(-)
>
> --- /dev/null
> +++ b/Documentation/atomic_bitops.txt
> @@ -0,0 +1,66 @@
> +
> +On atomic bitops.
> +
> +
> +While our bitmap_{}() functions are non-atomic, we have a number of operations
> +operating on single bits in a bitmap that are atomic.
> +
> +
> +API
> +---
> +
> +The single bit operations are:
> +
> +Non RmW ops:
Non-RmW ops:
> +
> + test_bit()
> +
[]
> --- /dev/null
> +++ b/Documentation/atomic_t.txt
> @@ -0,0 +1,200 @@
> +
> +On atomic types (atomic_t atomic64_t and atomic_long_t).
> +
> +The atomic type provides an interface to the architecture's means of atomic
> +RmW operations between CPUs (atomic operations on MMIO are not supported and
> +can lead to fatal traps on some platforms).
> +
> +API
> +---
> +
> +The 'full' API consists of (atomic64_ and atomic_long_ prefixes omitted for
> +brevity):
> +
> +Non RmW ops:
Non-RmW ops:
> +
> + atomic_read(), atomic_set()
> + atomic_read_acquire(), atomic_set_release()
> +
> +
> +RmW atomic operations:
> +
> +Arithmetic:
> +
> + atomic_{add,sub,inc,dec}()
> + atomic_{add,sub,inc,dec}_return{,_relaxed,_acquire,_release}()
> + atomic_fetch_{add,sub,inc,dec}{,_relaxed,_acquire,_release}()
> +
> +
> +Bitwise:
> +
> + atomic_{and,or,xor,andnot}()
> + atomic_fetch_{and,or,xor,andnot}{,_relaxed,_acquire,_release}()
> +
> +
> +Swap:
> +
> + atomic_xchg{,_relaxed,_acquire,_release}()
> + atomic_cmpxchg{,_relaxed,_acquire,_release}()
> + atomic_try_cmpxchg{,_relaxed,_acquire,_release}()
> +
> +
> +Reference count (but please see refcount_t):
> +
> + atomic_add_unless(), atomic_inc_not_zero()
> + atomic_sub_and_test(), atomic_dec_and_test()
> +
> +
> +Misc:
> +
> + atomic_inc_and_test(), atomic_add_negative()
> + atomic_dec_unless_positive(), atomic_inc_unless_negative()
> +
> +
> +Barriers:
> +
> + smp_mb__{before,after}_atomic()
> +
> +
> +
> +SEMANTICS
> +---------
> +
> +Non RmW ops:
Non-RmW ops:
> +
> +The non-RmW ops are (typically) regular LOADs and STOREs and are canonically
> +implemented using READ_ONCE(), WRITE_ONCE(), smp_load_acquire() and
> +smp_store_release() respectively.
> +
> +The one detail to this is that atomic_set{}() should be observable to the RmW
> +ops. That is:
> +
> + C atomic-set
> +
> + {
> + atomic_set(v, 1);
> + }
> +
> + P1(atomic_t *v)
> + {
> + atomic_add_unless(v, 1, 0);
> + }
> +
> + P2(atomic_t *v)
> + {
> + atomic_set(v, 0);
> + }
> +
> + exists
> + (v=2)
> +
> +In this case we would expect the atomic_set() from CPU1 to either happen
> +before the atomic_add_unless(), in which case that latter one would no-op, or
> +_after_ in which case we'd overwrite its result. In no case is "2" a valid
> +outcome.
> +
> +This is typically true on 'normal' platforms, where a regular competing STORE
> +will invalidate a LL/SC or fail a CMPXCHG.
> +
> +The obvious case where this is not so is when we need to implement atomic ops
> +with a lock:
> +
> + CPU0 CPU1
> +
> + atomic_add_unless(v, 1, 0);
> + lock();
> + ret = READ_ONCE(v->counter); // == 1
> + atomic_set(v, 0);
> + if (ret != u) WRITE_ONCE(v->counter, 0);
> + WRITE_ONCE(v->counter, ret + 1);
> + unlock();
> +
> +the typical solution is to then implement atomic_set{}() with atomic_xchg().
> +
> +
> +RmW ops:
I prefer (and have usually seen) RMW, but it's your document -- er, text file. :)
> +
> +These come in various forms:
> +
[]
> --- a/Documentation/memory-barriers.txt
> +++ b/Documentation/memory-barriers.txt
> @@ -498,7 +498,7 @@ VARIETIES OF MEMORY BARRIER
> This means that ACQUIRE acts as a minimal "acquire" operation and
> RELEASE acts as a minimal "release" operation.
>
> -A subset of the atomic operations described in core-api/atomic_ops.rst have
> +A subset of the atomic operations described in atomic_t.txt have ACQUIRE
> ACQUIRE and RELEASE variants in addition to fully-ordered and relaxed (no
duplicate ACQUIRE.
> barrier semantics) definitions. For compound atomics performing both a load
> and a store, ACQUIRE semantics apply only to the load and RELEASE semantics
--
~Randy
^ permalink raw reply [flat|nested] 43+ messages in thread