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

Groups > linux.kernel > #1662178 > unrolled thread

[RFC][PATCH]: documentation,atomic: Add a new atomic_t document

Back to article view | Back to linux.kernel

Contents

  [RFC][PATCH]: documentation,atomic: Add a new atomic_t document Peter Zijlstra <peterz@infradead.org> - 2017-06-09 11:30 +0200
    [RFC][PATCH] atomic: Fix atomic_set_release() for 'funny'  architectures Peter Zijlstra <peterz@infradead.org> - 2017-06-09 13:10 +0200
      Re: [RFC][PATCH] atomic: Fix atomic_set_release() for 'funny'  architectures Peter Zijlstra <peterz@infradead.org> - 2017-06-09 13:20 +0200
        Re: [RFC][PATCH] atomic: Fix atomic_set_release() for 'funny'  architectures Vineet Gupta <Vineet.Gupta1@synopsys.com> - 2017-06-09 19:30 +0200
          Re: [RFC][PATCH] atomic: Fix atomic_set_release() for 'funny'  architectures Peter Zijlstra <peterz@infradead.org> - 2017-06-09 21:00 +0200
        Re: [RFC][PATCH] atomic: Fix atomic_set_release() for 'funny'  architectures James Bottomley <James.Bottomley@HansenPartnership.com> - 2017-06-09 21:00 +0200
    Re: [RFC][PATCH]: documentation,atomic: Add a new atomic_t document Will Deacon <will.deacon@arm.com> - 2017-06-09 17:50 +0200
      Re: [RFC][PATCH]: documentation,atomic: Add a new atomic_t document Peter Zijlstra <peterz@infradead.org> - 2017-06-09 21:40 +0200
        Re: [RFC][PATCH]: documentation,atomic: Add a new atomic_t document Boqun Feng <boqun.feng@gmail.com> - 2017-06-11 16:00 +0200
          Re: [RFC][PATCH]: documentation,atomic: Add a new atomic_t document Peter Zijlstra <peterz@infradead.org> - 2017-06-12 17:00 +0200
            Re: [RFC][PATCH]: documentation,atomic: Add a new atomic_t document Boqun Feng <boqun.feng@gmail.com> - 2017-06-13 08:40 +0200
            Re: [RFC][PATCH]: documentation,atomic: Add a new atomic_t document Will Deacon <will.deacon@arm.com> - 2017-06-14 14:40 +0200
    Re: [RFC][PATCH]: documentation,atomic: Add a new atomic_t document Randy Dunlap <rdunlap@infradead.org> - 2017-06-09 20:20 +0200

#1662178 — [RFC][PATCH]: documentation,atomic: Add a new atomic_t document

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>
---

--- /dev/null	2017-05-05 13:16:22.636212333 +0200
+++ b/Documentation/atomic_t.txt	2017-06-09 11:05:31.501599153 +0200
@@ -0,0 +1,147 @@
+
+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:
+
+  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,notand}()
+  atomic_fetch_{and,or,xor,notand}{,_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()
+
+
+
+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:
+
+  CPU0						CPU1
+
+  val = atomic_read(&X)
+  do {
+						atomic_set(&X, 0)
+	new = val + 1;
+  } while (!atomic_try_cmpxchg(&X, &val, new));
+
+Should cause the cmpxchg to *FAIL* (when @val != 0). This is typically true;
+on 'normal' platforms; a regular competing STORE will invalidate a LL/SC.
+
+The obvious case where this is not so is where we need to implement atomic ops
+with a spinlock hashtable; 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 Sequentially Consistent;
+
+ - 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 is an ACQUIRE
+ {}_release: the W of the RmW is a  RELEASE
+
+NOTE: our ACQUIRE/RELEASE are RCpc
+
+
+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 SC atomics and these barriers are no-ops.
+
+So while something like:
+
+	smp_mb__before_atomic();
+	val = atomic_dec_return_relaxed(&X);
+
+is a 'typical' RELEASE pattern (please use atomic_dec_return_release()), the
+barrier is strictly stronger than a RELEASE.

[toc] | [next] | [standalone]

#1662299 — [RFC][PATCH] atomic: Fix atomic_set_release() for 'funny' architectures

On Fri, Jun 09, 2017 at 11:24:50AM +0200, Peter Zijlstra wrote:
> +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:
> +
> +  CPU0						CPU1
> +
> +  val = atomic_read(&X)
> +  do {
> +						atomic_set(&X, 0)
> +	new = val + 1;
> +  } while (!atomic_try_cmpxchg(&X, &val, new));
> +
> +Should cause the cmpxchg to *FAIL* (when @val != 0). This is typically true;
> +on 'normal' platforms; a regular competing STORE will invalidate a LL/SC.
> +
> +The obvious case where this is not so is where we need to implement atomic ops
> +with a spinlock hashtable; the typical solution is to then implement
> +atomic_set() with atomic_xchg().

---
Subject: atomic: Fix atomic_set_release() for 'funny' architectures

Those architectures that have a special atomic_set implementation also
need a special atomic_set_release(), because for the very same reason
WRITE_ONCE() is broken for them, smp_store_release() is too.

The vast majority is architectures that have spinlock hash based atomic
implementation except hexagon which seems to have a hardware 'feature'.

The spinlock based atomics should be SC, that is, none of them appear to
place extra barriers in atomic_cmpxchg() or any of the other SC atomic
primitives and therefore seem to rely on their spinlock implementation
being SC (I did not fully validate all that).

Therefore, the normal atomic_set() is SC and can be used at
atomic_set_release().

Cc: Vineet Gupta <vgupta@synopsys.com>
Cc: Richard Kuo <rkuo@codeaurora.org>
Cc: James Hogan <james.hogan@imgtec.com>
Cc: "James E.J. Bottomley" <jejb@parisc-linux.org>
Cc: "David S. Miller" <davem@davemloft.net>
Cc: Chris Metcalf <cmetcalf@mellanox.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 arch/arc/include/asm/atomic.h         | 2 ++
 arch/hexagon/include/asm/atomic.h     | 2 ++
 arch/metag/include/asm/atomic_lock1.h | 2 ++
 arch/parisc/include/asm/atomic.h      | 2 ++
 arch/sparc/include/asm/atomic_32.h    | 2 ++
 arch/tile/include/asm/atomic_32.h     | 2 ++
 include/asm-generic/atomic64.h        | 2 ++
 7 files changed, 14 insertions(+)

diff --git a/arch/arc/include/asm/atomic.h b/arch/arc/include/asm/atomic.h
index 54b54da6384c..11859287c52a 100644
--- a/arch/arc/include/asm/atomic.h
+++ b/arch/arc/include/asm/atomic.h
@@ -123,6 +123,8 @@ static inline void atomic_set(atomic_t *v, int i)
 	atomic_ops_unlock(flags);
 }
 
+#define atomic_set_release(v, i)	atomic_set((v), (i))
+
 #endif
 
 /*
diff --git a/arch/hexagon/include/asm/atomic.h b/arch/hexagon/include/asm/atomic.h
index a62ba368b27d..fb3dfb2a667e 100644
--- a/arch/hexagon/include/asm/atomic.h
+++ b/arch/hexagon/include/asm/atomic.h
@@ -42,6 +42,8 @@ static inline void atomic_set(atomic_t *v, int new)
 	);
 }
 
+#define atomic_set_release(v, i)	atomic_set((v), (i))
+
 /**
  * atomic_read - reads a word, atomically
  * @v: pointer to atomic value
diff --git a/arch/metag/include/asm/atomic_lock1.h b/arch/metag/include/asm/atomic_lock1.h
index 6c1380a8a0d4..eee779f26cc4 100644
--- a/arch/metag/include/asm/atomic_lock1.h
+++ b/arch/metag/include/asm/atomic_lock1.h
@@ -37,6 +37,8 @@ static inline int atomic_set(atomic_t *v, int i)
 	return i;
 }
 
+#define atomic_set_release(v, i) atomic_set((v), (i))
+
 #define ATOMIC_OP(op, c_op)						\
 static inline void atomic_##op(int i, atomic_t *v)			\
 {									\
diff --git a/arch/parisc/include/asm/atomic.h b/arch/parisc/include/asm/atomic.h
index 5394b9c5f914..17b98a87e5e2 100644
--- a/arch/parisc/include/asm/atomic.h
+++ b/arch/parisc/include/asm/atomic.h
@@ -65,6 +65,8 @@ static __inline__ void atomic_set(atomic_t *v, int i)
 	_atomic_spin_unlock_irqrestore(v, flags);
 }
 
+#define atomic_set_release(v, i)	atomic_set((v), (i))
+
 static __inline__ int atomic_read(const atomic_t *v)
 {
 	return READ_ONCE((v)->counter);
diff --git a/arch/sparc/include/asm/atomic_32.h b/arch/sparc/include/asm/atomic_32.h
index ee3f11c43cda..7643e979e333 100644
--- a/arch/sparc/include/asm/atomic_32.h
+++ b/arch/sparc/include/asm/atomic_32.h
@@ -29,6 +29,8 @@ int atomic_xchg(atomic_t *, int);
 int __atomic_add_unless(atomic_t *, int, int);
 void atomic_set(atomic_t *, int);
 
+#define atomic_set_release(v, i)	atomic_set((v), (i))
+
 #define atomic_read(v)          ACCESS_ONCE((v)->counter)
 
 #define atomic_add(i, v)	((void)atomic_add_return( (int)(i), (v)))
diff --git a/arch/tile/include/asm/atomic_32.h b/arch/tile/include/asm/atomic_32.h
index a93774255136..53a423e7cb92 100644
--- a/arch/tile/include/asm/atomic_32.h
+++ b/arch/tile/include/asm/atomic_32.h
@@ -101,6 +101,8 @@ static inline void atomic_set(atomic_t *v, int n)
 	_atomic_xchg(&v->counter, n);
 }
 
+#define atomic_set_release(v, i)	atomic_set((v), (i))
+
 /* A 64bit atomic type */
 
 typedef struct {
diff --git a/include/asm-generic/atomic64.h b/include/asm-generic/atomic64.h
index dad68bf46c77..8d28eb010d0d 100644
--- a/include/asm-generic/atomic64.h
+++ b/include/asm-generic/atomic64.h
@@ -21,6 +21,8 @@ typedef struct {
 extern long long atomic64_read(const atomic64_t *v);
 extern void	 atomic64_set(atomic64_t *v, long long i);
 
+#define atomic64_set_release(v, i)	atomic64_set((v), (i))
+
 #define ATOMIC64_OP(op)							\
 extern void	 atomic64_##op(long long a, atomic64_t *v);
 

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

#1662309 — Re: [RFC][PATCH] atomic: Fix atomic_set_release() for 'funny' architectures

On Fri, Jun 09, 2017 at 01:05:06PM +0200, Peter Zijlstra wrote:

> The spinlock based atomics should be SC, that is, none of them appear to
> place extra barriers in atomic_cmpxchg() or any of the other SC atomic
> primitives and therefore seem to rely on their spinlock implementation
> being SC (I did not fully validate all that).

So I did see that ARC and PARISC have 'superfluous' smp_mb() calls
around their spinlock implementation.

That is, for spinlock semantics you only need one _after_ lock and one
_before_ unlock. But the atomic stuff relies on being SC and thus would
need one before and after both lock and unlock.

Now, afaict PARISC doesn't even have memory barriers (it uses
asm-generic/barrier.h) so that's a bit of a puzzle.

But ARC could probably optimize (if they still care about that hardware)
by pulling out those barriers and putting it in the atomic
implementation.

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

#1662642 — Re: [RFC][PATCH] atomic: Fix atomic_set_release() for 'funny' architectures

On 06/09/2017 04:13 AM, Peter Zijlstra wrote:
> On Fri, Jun 09, 2017 at 01:05:06PM +0200, Peter Zijlstra wrote:
> 
>> The spinlock based atomics should be SC, that is, none of them appear to
>> place extra barriers in atomic_cmpxchg() or any of the other SC atomic
>> primitives and therefore seem to rely on their spinlock implementation
>> being SC (I did not fully validate all that).
> 
> So I did see that ARC and PARISC have 'superfluous' smp_mb() calls
> around their spinlock implementation.
> 
> That is, for spinlock semantics you only need one _after_ lock and one
> _before_ unlock. But the atomic stuff relies on being SC and thus would
> need one before and after both lock and unlock.

Right we discussed this a while back: https://lkml.org/lkml/2015/6/11/276

At the time when I tried removing these extra barriers, hackbench regressed. I'm 
about to get a new quad core 1GHz chip (vs. the FPGA before) and will 
re-experiment. Likely we don't need it otherwise I will add a comment of this 
"feature"

> But ARC could probably optimize (if they still care about that hardware)
> by pulling out those barriers and putting it in the atomic
> implementation.

A bit confused here. Reading the lkml posting for this thread, you posted 2 
patches, and they had to do with atomic_set() for EZChip platform which is really 
special (no ll/sc). The extra smp_mb() is related to ll/sc variants. Just tryign 
to make sure that we are talking 2 different things here :-)

-Vineet

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

#1662689 — Re: [RFC][PATCH] atomic: Fix atomic_set_release() for 'funny' architectures

On Fri, Jun 09, 2017 at 10:28:50AM -0700, Vineet Gupta wrote:
> On 06/09/2017 04:13 AM, Peter Zijlstra wrote:
> > On Fri, Jun 09, 2017 at 01:05:06PM +0200, Peter Zijlstra wrote:
> > 
> > > The spinlock based atomics should be SC, that is, none of them appear to
> > > place extra barriers in atomic_cmpxchg() or any of the other SC atomic
> > > primitives and therefore seem to rely on their spinlock implementation
> > > being SC (I did not fully validate all that).
> > 
> > So I did see that ARC and PARISC have 'superfluous' smp_mb() calls
> > around their spinlock implementation.
> > 
> > That is, for spinlock semantics you only need one _after_ lock and one
> > _before_ unlock. But the atomic stuff relies on being SC and thus would
> > need one before and after both lock and unlock.
> 
> Right we discussed this a while back: https://lkml.org/lkml/2015/6/11/276
> 
> At the time when I tried removing these extra barriers, hackbench regressed.
> I'm about to get a new quad core 1GHz chip (vs. the FPGA before) and will
> re-experiment. Likely we don't need it otherwise I will add a comment of
> this "feature"
> 
> > But ARC could probably optimize (if they still care about that hardware)
> > by pulling out those barriers and putting it in the atomic
> > implementation.
> 
> A bit confused here. Reading the lkml posting for this thread, you posted 2
> patches, and they had to do with atomic_set() for EZChip platform which is
> really special (no ll/sc). The extra smp_mb() is related to ll/sc variants.
> Just tryign to make sure that we are talking 2 different things here :-)

Could be I just got all my variants in a twist... wouldn't be the first
time ;-)

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

#1662690 — Re: [RFC][PATCH] atomic: Fix atomic_set_release() for 'funny' architectures

[adding parisc list]
On Fri, 2017-06-09 at 13:13 +0200, Peter Zijlstra wrote:
> On Fri, Jun 09, 2017 at 01:05:06PM +0200, Peter Zijlstra wrote:
> 
> > The spinlock based atomics should be SC, that is, none of them
> > appear to
> > place extra barriers in atomic_cmpxchg() or any of the other SC
> > atomic
> > primitives and therefore seem to rely on their spinlock
> > implementation
> > being SC (I did not fully validate all that).
> 
> So I did see that ARC and PARISC have 'superfluous' smp_mb() calls
> around their spinlock implementation.
> 
> That is, for spinlock semantics you only need one _after_ lock and 
> one _before_ unlock. But the atomic stuff relies on being SC and thus
> would need one before and after both lock and unlock.

Actually, for us that's not true.  You are correct in the above for
safety but not for performance: If we remove the safety unnecessary
barriers, it can elongate our critical sections (the spinlock can move
up in the code stream and the spin unlock can move down) which leads to
performance regressions because we end up holding locks longer than we
need (we also have a lot of hot locks).

> Now, afaict PARISC doesn't even have memory barriers (it uses
> asm-generic/barrier.h) so that's a bit of a puzzle.

We disable relaxed ordering on our architecture which means the CPU
issue stream must match the instruction stream.  We've debated turning
on relaxed ordering, but decided it was more hassle than it's worth.

James


> But ARC could probably optimize (if they still care about that 
> hardware) by pulling out those barriers and putting it in the atomic
> implementation.
> 

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

#1662573

Hi Peter,

On Fri, Jun 09, 2017 at 11:24:50AM +0200, Peter Zijlstra wrote:
> 
> 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.

Yeah, we should aim at killing (replacing) most of atomic_ops.txt in the
medium term, but this is a good start.

> Also please, ReST people, go away.
> 
> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> ---
> 
> --- /dev/null	2017-05-05 13:16:22.636212333 +0200
> +++ b/Documentation/atomic_t.txt	2017-06-09 11:05:31.501599153 +0200
> @@ -0,0 +1,147 @@
> +
> +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).

We should be stronger here: atomics to IO could lead to kernel panics (i.e.
raise a fatal abort), whereas this sounds like they just lose some ordering
or atomicity guarantees.

> +The 'full' API consists of:

Need to mention the 64-bit and the long variants?

> +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,notand}()
> +  atomic_fetch_{and,or,xor,notand}{,_relaxed,_acquire,_release}()

s/notand/andnot/

> +
> +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()

I *think* you have all of them here.

> +
> +Barriers:
> +
> +  smp_mb__{before,after}_atomic()
> +
> +
> +
> +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:
> +
> +  CPU0						CPU1
> +
> +  val = atomic_read(&X)
> +  do {
> +						atomic_set(&X, 0)
> +	new = val + 1;
> +  } while (!atomic_try_cmpxchg(&X, &val, new));
> +
> +Should cause the cmpxchg to *FAIL* (when @val != 0). This is typically true;
> +on 'normal' platforms; a regular competing STORE will invalidate a LL/SC.

I see what you're getting at here, but the example is a bit weird because
CPU1 might hold the store to X in a local store-buffer and not shoot down
the cmpxchg immediately. I think you need something to show how the write
to X has at least partially propagated.

> +The obvious case where this is not so is where we need to implement atomic ops
> +with a spinlock hashtable; the typical solution is to then implement
> +atomic_set() with atomic_xchg().

Looking at sparc32, atomic_set takes the hashed lock, so I can't see what
goes wrong here: atomic_try_cmpxchg will get called with val !=0, but the
comparison will fail because the value in memory will be 0. What am I
missing?

> +
> +
> +RmW ops:
> +
> +These come in various forms:
> +
> + - plain operations without return value: atomic_{}()

Maybe just list the API here, instead of having the separate section
previously?

> + - 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 Sequentially Consistent;

I think it's stronger than that, because they also order non-RmW operations,
whereas this makes it sounds like there's just a total order over all RmW
operations.

> + - RmW operations that are conditional are unordered on FAILURE, otherwise the
> +   above rules apply.

We should make it clear that "unordered" here refers to accesses to other
memory locations.

> +
> +Except of course when an operation has an explicit ordering like:
> +
> + {}_relaxed: unordered
> + {}_acquire: the R of the RmW is an ACQUIRE
> + {}_release: the W of the RmW is a  RELEASE
> +
> +NOTE: our ACQUIRE/RELEASE are RCpc

The NOTE belongs in memory-barriers.txt

> +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().

inherit?

Will

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

#1662710

On Fri, Jun 09, 2017 at 04:44:42PM +0100, Will Deacon wrote:

> > +++ b/Documentation/atomic_t.txt	2017-06-09 11:05:31.501599153 +0200
> > @@ -0,0 +1,147 @@
> > +
> > +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).
> 
> We should be stronger here: atomics to IO could lead to kernel panics (i.e.
> raise a fatal abort), whereas this sounds like they just lose some ordering
> or atomicity guarantees.
> 
> > +The 'full' API consists of:
> 
> Need to mention the 64-bit and the long variants?

Makes a bit of a mess of things I felt, maybe I should be a little more
explicit and mention that everything applies to all 3 variants?


> > +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:
> > +
> > +  CPU0						CPU1
> > +
> > +  val = atomic_read(&X)
> > +  do {
> > +						atomic_set(&X, 0)
> > +	new = val + 1;
> > +  } while (!atomic_try_cmpxchg(&X, &val, new));
> > +
> > +Should cause the cmpxchg to *FAIL* (when @val != 0). This is typically true;
> > +on 'normal' platforms; a regular competing STORE will invalidate a LL/SC.
> 
> I see what you're getting at here, but the example is a bit weird because
> CPU1 might hold the store to X in a local store-buffer and not shoot down
> the cmpxchg immediately. I think you need something to show how the write
> to X has at least partially propagated.

Hurm.. would the example from metag atomic_set be better?

> > +The obvious case where this is not so is where we need to implement atomic ops
> > +with a spinlock hashtable; the typical solution is to then implement
> > +atomic_set() with atomic_xchg().
> 
> Looking at sparc32, atomic_set takes the hashed lock, so I can't see what
> goes wrong here: atomic_try_cmpxchg will get called with val !=0, but the
> comparison will fail because the value in memory will be 0. What am I
> missing?

This is the reason their atomic_set() is special and needs to take the
lock.

> > +
> > +
> > +RmW ops:
> > +
> > +These come in various forms:
> > +
> > + - plain operations without return value: atomic_{}()
> 
> Maybe just list the API here, instead of having the separate section
> previously?

That then leaves you with no place to put those comments. I wanted
to slice the API in different ways for each subject without endless
repetition.

> > + - 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 Sequentially Consistent;
> 
> I think it's stronger than that, because they also order non-RmW operations,
> whereas this makes it sounds like there's just a total order over all RmW
> operations.

Right, what should I call it?

> > + - RmW operations that are conditional are unordered on FAILURE, otherwise the
> > +   above rules apply.
> 
> We should make it clear that "unordered" here refers to accesses to other
> memory locations.
> 
> > +
> > +Except of course when an operation has an explicit ordering like:
> > +
> > + {}_relaxed: unordered
> > + {}_acquire: the R of the RmW is an ACQUIRE
> > + {}_release: the W of the RmW is a  RELEASE
> > +
> > +NOTE: our ACQUIRE/RELEASE are RCpc
> 
> The NOTE belongs in memory-barriers.txt

It is of course; I'll remove that line.

> > +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().
> 
> inherit?

"inherent" is I think the word I wanted..

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

#1663107

[Multipart message — attachments visible in raw view] — view raw

Hi Peter,

On Fri, Jun 09, 2017 at 09:36:04PM +0200, Peter Zijlstra wrote:
[...]
> > > +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 Sequentially Consistent;
> > 
> > I think it's stronger than that, because they also order non-RmW operations,
> > whereas this makes it sounds like there's just a total order over all RmW
> > operations.
> 
> Right, what should I call it?
> 

I think the term we use to refer this behavior is "fully-ordered"? 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 ;-)

Regards,
Boqun



> > > + - RmW operations that are conditional are unordered on FAILURE, otherwise the
> > > +   above rules apply.
> > 

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

#1663588

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).



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:
+
+  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()
+
+
+
+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.
 
 

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

#1664490

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.
>  
>  

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

#1665756

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

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

#1662659

On 06/09/17 02:24, Peter Zijlstra wrote:
> 
> --- /dev/null	2017-05-05 13:16:22.636212333 +0200
> +++ b/Documentation/atomic_t.txt	2017-06-09 11:05:31.501599153 +0200
> @@ -0,0 +1,147 @@
> +
> +The one detail to this is that atomic_set() should be observable to the RmW
> +ops. That is:
> +
> +  CPU0						CPU1
> +
> +  val = atomic_read(&X)
> +  do {
> +						atomic_set(&X, 0)
> +	new = val + 1;
> +  } while (!atomic_try_cmpxchg(&X, &val, new));
> +
> +Should cause the cmpxchg to *FAIL* (when @val != 0). This is typically true;

   should

> +on 'normal' platforms; a regular competing STORE will invalidate a LL/SC.

too many semi-colons above.

> +
> +The obvious case where this is not so is where we need to implement atomic ops
> +with a spinlock hashtable; 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 Sequentially Consistent;
> +
> + - 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 is an ACQUIRE
> + {}_release: the W of the RmW is a  RELEASE
> +
> +NOTE: our ACQUIRE/RELEASE are RCpc
> +
> +
> +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().

   inherent ?

> +
> +These helper barriers exist because architectures have varying implicit
> +ordering on their SMP atomic primitives. For example our TSO architectures
> +provide SC atomics and these barriers are no-ops.
> +
> +So while something like:
> +
> +	smp_mb__before_atomic();
> +	val = atomic_dec_return_relaxed(&X);
> +
> +is a 'typical' RELEASE pattern (please use atomic_dec_return_release()), the
> +barrier is strictly stronger than a RELEASE.
> 


-- 
~Randy

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web