lockless_dereference() in perfbook

lockless_dereference() in perfbook

[Akira Yokosawa]

Hi Paul,

As LKMM dropped lockless_dereference() when it was merged in v4.17,
CodeSamples/formal/litmus/C-MP+o-wmb-o+ld-addr-o.litmus fails to
be evaluated by "make run-herd7" under CodeSamples/formal/herd.

lockless_dereference() is still covered by CodeSamples/formal/litmus/api.h
and klitmus7, so the test can be evaluated by litmus7 and "klitmus7 at the
moment.

In commit 48ec12dac0c3 ("memorder: Update based on v4.15 Linux kernel
de-Alpha-ication"), you added a footnote in Section 15.2.3 saying:

    Note that lockless_dereference() is not needed on v4.15 and later,
    and therefore is not available in these later Linux kernels.

There remain several lockless_dereference()s in perfbook without any
updates.

In the Answer to Quick Quiz 15.15, lockless_dereference() is mentioned
several times.

Quick Quiz 15.17 says:

    Why doesn't line 18 of Listing 15.12 need a lockless_dereference()?

Leading paragraph of Section 15.3.2.1 says:

    The load that heads your dependency chain must use proper ordering,
    for example, lockless_dereference(), rcu_dereference(), or a READ_ONCE()
    followed by smp_read_barrier_depends().

In the middle of Section 15.5, there is a sentence:

    Note also that a dependency leading to a load must be headed by a
    lockless_dereference() or an rcu_dereference(): READ_ONCE() is not
    sufficient.

Could you look into them?

One problem in regard to litmus tests might be that there is no means
to indicate plain accesses with no memory barrier in current LKMM.
At the moment, C-MP+o-wmb-o+o-addr-o.litmus behaves identically as
C-MP+o-wmb-o+ld-addr-o.litmus would do.

        Thanks, Akira

Re: lockless_dereference() in perfbook

[Paul E. McKenney]

On Sat, Dec 01, 2018 at 04:48:03PM +0900, Akira Yokosawa wrote:
> Hi Paul,
> 
> As LKMM dropped lockless_dereference() when it was merged in v4.17,
> CodeSamples/formal/litmus/C-MP+o-wmb-o+ld-addr-o.litmus fails to
> be evaluated by "make run-herd7" under CodeSamples/formal/herd.
> 
> lockless_dereference() is still covered by CodeSamples/formal/litmus/api.h
> and klitmus7, so the test can be evaluated by litmus7 and "klitmus7 at the
> moment.
> 
> In commit 48ec12dac0c3 ("memorder: Update based on v4.15 Linux kernel
> de-Alpha-ication"), you added a footnote in Section 15.2.3 saying:
> 
>     Note that lockless_dereference() is not needed on v4.15 and later,
>     and therefore is not available in these later Linux kernels.
> 
> There remain several lockless_dereference()s in perfbook without any
> updates.
> 
> In the Answer to Quick Quiz 15.15, lockless_dereference() is mentioned
> several times.
> 
> Quick Quiz 15.17 says:
> 
>     Why doesn't line 18 of Listing 15.12 need a lockless_dereference()?
> 
> Leading paragraph of Section 15.3.2.1 says:
> 
>     The load that heads your dependency chain must use proper ordering,
>     for example, lockless_dereference(), rcu_dereference(), or a READ_ONCE()
>     followed by smp_read_barrier_depends().
> 
> In the middle of Section 15.5, there is a sentence:
> 
>     Note also that a dependency leading to a load must be headed by a
>     lockless_dereference() or an rcu_dereference(): READ_ONCE() is not
>     sufficient.
> 
> Could you look into them?
> 
> One problem in regard to litmus tests might be that there is no means
> to indicate plain accesses with no memory barrier in current LKMM.
> At the moment, C-MP+o-wmb-o+o-addr-o.litmus behaves identically as
> C-MP+o-wmb-o+ld-addr-o.litmus would do.

Good catches!  How about the following?

1.	I remove CodeSamples/formal/litmus/C-MP+o-wmb-o+ld-addr-o.litmus.

2.	I add a comment to the lockless_dereference() call in
	lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test
	stating that this API member is obsolete.

3.	I remove the (\path{C-MP+o-wmb-o+ld-addr-o.litmus}) from the
	discussion.  I also add a LaTeX comment stating which commit
	removed this file for future reference.

4.	I remove lockless_dereference() from CodeSamples/formal/litmus/api.h.

Does that sound reasonable?

							Thanx, Paul

Re: lockless_dereference() in perfbook

[Akira Yokosawa]

On 2018/12/01 10:30:19 -0800, Paul E. McKenney wrote:
> On Sat, Dec 01, 2018 at 04:48:03PM +0900, Akira Yokosawa wrote:
>> Hi Paul,
>>
>> As LKMM dropped lockless_dereference() when it was merged in v4.17,
>> CodeSamples/formal/litmus/C-MP+o-wmb-o+ld-addr-o.litmus fails to
>> be evaluated by "make run-herd7" under CodeSamples/formal/herd.
>>
>> lockless_dereference() is still covered by CodeSamples/formal/litmus/api.h
>> and klitmus7, so the test can be evaluated by litmus7 and "klitmus7 at the
>> moment.
>>
>> In commit 48ec12dac0c3 ("memorder: Update based on v4.15 Linux kernel
>> de-Alpha-ication"), you added a footnote in Section 15.2.3 saying:
>>
>>     Note that lockless_dereference() is not needed on v4.15 and later,
>>     and therefore is not available in these later Linux kernels.
>>
>> There remain several lockless_dereference()s in perfbook without any
>> updates.
>>
>> In the Answer to Quick Quiz 15.15, lockless_dereference() is mentioned
>> several times.
>>
>> Quick Quiz 15.17 says:
>>
>>     Why doesn't line 18 of Listing 15.12 need a lockless_dereference()?
>>
>> Leading paragraph of Section 15.3.2.1 says:
>>
>>     The load that heads your dependency chain must use proper ordering,
>>     for example, lockless_dereference(), rcu_dereference(), or a READ_ONCE()
>>     followed by smp_read_barrier_depends().
>>
>> In the middle of Section 15.5, there is a sentence:
>>
>>     Note also that a dependency leading to a load must be headed by a
>>     lockless_dereference() or an rcu_dereference(): READ_ONCE() is not
>>     sufficient.
>>
>> Could you look into them?
>>
>> One problem in regard to litmus tests might be that there is no means
>> to indicate plain accesses with no memory barrier in current LKMM.
>> At the moment, C-MP+o-wmb-o+o-addr-o.litmus behaves identically as
>> C-MP+o-wmb-o+ld-addr-o.litmus would do.
> 
> Good catches!  How about the following?
> 
> 1.	I remove CodeSamples/formal/litmus/C-MP+o-wmb-o+ld-addr-o.litmus.
> 
> 2.	I add a comment to the lockless_dereference() call in
> 	lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test
> 	stating that this API member is obsolete.
> 
> 3.	I remove the (\path{C-MP+o-wmb-o+ld-addr-o.litmus}) from the
> 	discussion.  I also add a LaTeX comment stating which commit
> 	removed this file for future reference.
> 
> 4.	I remove lockless_dereference() from CodeSamples/formal/litmus/api.h.
> 
> Does that sound reasonable?

Yes, it does!

Maybe discussion of
lst:memorder:Message-Passing Address-Dependency Litmus Test (No Ordering)
needs further tweaks, including the update of its caption, i.e.,
it is now _ordered_. Quick Quiz 15.13 looks odd as of now.

And the caption to
lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test
also needs update to indicate it is not necessary any more.

Looking forward to seeing the update.

        Thanks, Akira

> 
> 							Thanx, Paul
> 

Re: lockless_dereference() in perfbook

[Paul E. McKenney]

On Sun, Dec 02, 2018 at 07:25:21AM +0900, Akira Yokosawa wrote:
> On 2018/12/01 10:30:19 -0800, Paul E. McKenney wrote:
> > On Sat, Dec 01, 2018 at 04:48:03PM +0900, Akira Yokosawa wrote:
> >> Hi Paul,
> >>
> >> As LKMM dropped lockless_dereference() when it was merged in v4.17,
> >> CodeSamples/formal/litmus/C-MP+o-wmb-o+ld-addr-o.litmus fails to
> >> be evaluated by "make run-herd7" under CodeSamples/formal/herd.
> >>
> >> lockless_dereference() is still covered by CodeSamples/formal/litmus/api.h
> >> and klitmus7, so the test can be evaluated by litmus7 and "klitmus7 at the
> >> moment.
> >>
> >> In commit 48ec12dac0c3 ("memorder: Update based on v4.15 Linux kernel
> >> de-Alpha-ication"), you added a footnote in Section 15.2.3 saying:
> >>
> >>     Note that lockless_dereference() is not needed on v4.15 and later,
> >>     and therefore is not available in these later Linux kernels.
> >>
> >> There remain several lockless_dereference()s in perfbook without any
> >> updates.
> >>
> >> In the Answer to Quick Quiz 15.15, lockless_dereference() is mentioned
> >> several times.
> >>
> >> Quick Quiz 15.17 says:
> >>
> >>     Why doesn't line 18 of Listing 15.12 need a lockless_dereference()?
> >>
> >> Leading paragraph of Section 15.3.2.1 says:
> >>
> >>     The load that heads your dependency chain must use proper ordering,
> >>     for example, lockless_dereference(), rcu_dereference(), or a READ_ONCE()
> >>     followed by smp_read_barrier_depends().
> >>
> >> In the middle of Section 15.5, there is a sentence:
> >>
> >>     Note also that a dependency leading to a load must be headed by a
> >>     lockless_dereference() or an rcu_dereference(): READ_ONCE() is not
> >>     sufficient.
> >>
> >> Could you look into them?
> >>
> >> One problem in regard to litmus tests might be that there is no means
> >> to indicate plain accesses with no memory barrier in current LKMM.
> >> At the moment, C-MP+o-wmb-o+o-addr-o.litmus behaves identically as
> >> C-MP+o-wmb-o+ld-addr-o.litmus would do.
> > 
> > Good catches!  How about the following?
> > 
> > 1.	I remove CodeSamples/formal/litmus/C-MP+o-wmb-o+ld-addr-o.litmus.
> > 
> > 2.	I add a comment to the lockless_dereference() call in
> > 	lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test
> > 	stating that this API member is obsolete.
> > 
> > 3.	I remove the (\path{C-MP+o-wmb-o+ld-addr-o.litmus}) from the
> > 	discussion.  I also add a LaTeX comment stating which commit
> > 	removed this file for future reference.
> > 
> > 4.	I remove lockless_dereference() from CodeSamples/formal/litmus/api.h.
> > 
> > Does that sound reasonable?
> 
> Yes, it does!
> 
> Maybe discussion of
> lst:memorder:Message-Passing Address-Dependency Litmus Test (No Ordering)
> needs further tweaks, including the update of its caption, i.e.,
> it is now _ordered_. Quick Quiz 15.13 looks odd as of now.
> 
> And the caption to
> lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test
> also needs update to indicate it is not necessary any more.
> 
> Looking forward to seeing the update.

How about the following?

							Thanx, Paul

------------------------------------------------------------------------

commit c9a15859a4451ee449b8d46dc9845e050acf5760
Author: Paul E. McKenney <paulmck@linux.ibm.com>
Date:   Sat Dec 1 17:07:35 2018 -0800

    memorder: Clean up reference to lockless_dereference()
    
    The lockless_dereference() primitive has been obsolete since Linux
    kernel version v4.15, but it is mentioned in several places in the
    memory-ordering chapter and in a litmus test.  This commit removes that
    litmus test, removes the definition of lockless_dereference(), makes
    READ_ONCE() work properly on DEC Alpha, and clearly labels remaining
    instances of lockless_dereference() in the text as obsolete.
    
    Reported-by: Akira Yokosawa <akiyks@gmail.com>
    Signed-off-by: Paul E. McKenney <paulmck@linux.ibm.com>

diff --git a/CodeSamples/formal/litmus/C-MP+o-wmb-o+ld-addr-o.litmus b/CodeSamples/formal/litmus/C-MP+o-wmb-o+ld-addr-o.litmus
deleted file mode 100644
index 117a6e3ffda8..000000000000
--- a/CodeSamples/formal/litmus/C-MP+o-wmb-o+ld-addr-o.litmus
+++ /dev/null
@@ -1,30 +0,0 @@
-C C-MP+o-wmb-o+ld-ad-o
-
-{
-int y=1;
-int *x1 = &y;
-}
-
-{
-#include "api.h"
-}
-
-P0(int* x0, int** x1) {
-
-	WRITE_ONCE(*x0, 2);
-	smp_wmb();
-	WRITE_ONCE(*x1, x0);
-
-}
-
-P1(int** x1) {
-
-	int *r2;
-	int r3;
-
-	r2 = lockless_dereference(*x1);
-	r3 = READ_ONCE(*r2);
-
-}
-
-exists (1:r2=x0 /\ 1:r3=1)
diff --git a/CodeSamples/formal/litmus/api.h b/CodeSamples/formal/litmus/api.h
index 0f14a48dd128..8bf0ba629a9e 100644
--- a/CodeSamples/formal/litmus/api.h
+++ b/CodeSamples/formal/litmus/api.h
@@ -1,7 +1,12 @@
 #ifndef __API_H__
 #define __API_H__
 #ifndef READ_ONCE
-#define READ_ONCE(x) __atomic_load_n((typeof(x) *)&(x), __ATOMIC_RELAXED)
+#define __READ_ONCE(x) __atomic_load_n((typeof(x) *)&(x), __ATOMIC_RELAXED)
+#ifdef __alpha__
+#define READ_ONCE(x) ({ typeof(x) ___x = __READ_ONCE(x); smp_mb(); ___x; })
+#else
+#define READ_ONCE(x) __READ_ONCE(x)
+#endif
 #define WRITE_ONCE(x, v) __atomic_store_n((typeof(x) *)&(x), (v), __ATOMIC_RELAXED)
 #define smp_mb() __atomic_thread_fence(__ATOMIC_SEQ_CST)
 #define smp_rmb() __atomic_thread_fence(__ATOMIC_ACQUIRE) /* outside std. */
@@ -14,10 +19,5 @@
 	__atomic_compare_exchange_n((x), &__old, (n), 1, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED); \
 	__old; \
 })
-#ifdef __alpha__
-#define lockless_dereference(x) ({ typeof(x) ___x = READ_ONCE(x); smp_mb(); ___x; })
-#else
-#define lockless_dereference(x) READ_ONCE(x)
-#endif
 #endif
 #endif
diff --git a/memorder/memorder.tex b/memorder/memorder.tex
index 943c3af3fe6f..bdeaba10e0b2 100644
--- a/memorder/memorder.tex
+++ b/memorder/memorder.tex
@@ -590,8 +590,7 @@ are at most two threads involved.
 	Section~\ref{sec:memorder:Address- and Data-Dependency Difficulties}.
 
 	The \co{*_dereference()} row captures the address and data
-	dependency ordering provided by \co{lockless_dereference()},
-	\co{rcu_dereference()}, and friends.
+	dependency ordering provided by \co{rcu_dereference()} and friends.
 
 	The ``Successful \co{*_acquire()}'' row captures the fact that many
 	CPUs have special ``acquire'' forms of loads and of atomic RMW
@@ -1411,7 +1410,7 @@ P1(int** x1) {
   int *r2;
   int r3;
 
-  r2 = lockless_dereference(*x1);
+  r2 = lockless_dereference(*x1); // Obsolete
   r3 = READ_ONCE(*r2);
 
 }
@@ -1426,12 +1425,14 @@ exists (1:r2=x0 /\ 1:r3=1)
 \end{listing}
 
 Listing~\ref{lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test}
-(\path{C-MP+o-wmb-o+ld-addr-o.litmus})
-shows how to make this work reliably on old Linux kernels running on
+% \path{C-MP+o-wmb-o+ld-addr-o.litmus} available at commit bc4b1c3f3b35
+% ("styleguide: Loosen restriction on comment in litmus test")
+shows how to make this work reliably on pre-v4.15 Linux kernels running on
 DEC Alpha, by
 replacing line~21's \co{READ_ONCE()} with \co{lockless_dereference()},\footnote{
 	Note that \co{lockless_dereference()} is not needed on v4.15 and
-	later, and therefore is not available in these later Linux kernels.}
+	later, and therefore is not available in these later Linux kernels.
+	Nor is it needed in versions of this book containing this sentence.}
 which acts like \co{READ_ONCE()} on all platforms other than DEC Alpha,
 where it acts like a \co{READ_ONCE()} followed by an \co{smp_mb()},
 thereby forcing the required ordering on all platforms, in turn
@@ -1482,8 +1483,7 @@ Because no production-quality platform speculates stores,
 it is not possible for the \co{WRITE_ONCE()} on line~10 to overwrite
 the \co{WRITE_ONCE()} on line~21, meaning that the \co{exists}
 clause on line~25 cannot trigger, even on DEC Alpha, even
-without the \co{lockless_dereference()} that is required in the
-dependent-load case.
+in pre-v4.15 Linux kernels.
 
 \QuickQuiz{}
 	But how do we know that \emph{all} platforms really avoid
@@ -1520,19 +1520,23 @@ dependent-load case.
 	There is one (famous) exception to this rule for weakly ordered
 	platforms, and that exception is DEC Alpha for load-to-load
 	address dependencies.
-	And this is why DEC Alpha requires the explicit memory barrier
-	supplied for it by the \co{lockless_dereference()} on line~21 of
+	And this is why, in Linux kernels predating v4.15, DEC Alpha
+	requires the explicit memory barrier supplied for it by the
+	now-obsolete \co{lockless_dereference()} on line~21 of
 	Listing~\ref{lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test}.
 	However, DEC Alpha does track load-to-store address dependencies,
 	which is why line~20 of
 	Listing~\ref{lst:memorder:S Address-Dependency Litmus Test}
-	does not have a \co{lockless_dereference()}.
+	does not need a \co{lockless_dereference()}, even in Linux
+	kernels predating v4.15.
 
 	To sum up, current platforms either respect address dependencies
 	implicitly, as is the case for TSO platforms (x86, mainframe,
 	SPARC,~...), have hardware tracking for address dependencies
-	(ARM, PowerPC, MIPS,~...), or have the required memory barriers
-	supplied by \co{lockless_dereference()} (DEC Alpha).
+	(ARM, PowerPC, MIPS,~...), have the required memory barriers
+	supplied by \co{READ_ONCE()} (DEC Alpha in Linux kernel v4.15 and
+	later), or require the memory barriers supplied by
+	\co{rcu_dereference()} (DEC Alpha in Linux kernel v4.14 and earlier).
 } \QuickQuizEnd
 
 \QuickQuiz{}
@@ -1605,16 +1609,6 @@ The value loaded by line~18 is what line~19 stores.
 The ordering provided by this data dependency is sufficient to prevent
 the \co{exists} clause from triggering.
 
-\QuickQuiz{}
-	Why doesn't line~18 of
-	Listing~\ref{lst:memorder:Load-Buffering Data-Dependency Litmus Test}
-	need a \co{lockless_dereference()}?
-\QuickQuizAnswer{
-	Data dependencies are always load-to-store dependencies, and
-	so all platforms respect them, even DEC Alpha, and for the
-	same reasons that they respect load-to-store address dependencies.
-} \QuickQuizEnd
-
 Just as with address dependencies, data dependencies are
 fragile and can be easily broken by compiler optimizations, as discussed in
 Section~\ref{sec:memorder:Address- and Data-Dependency Difficulties}.
@@ -3388,9 +3382,7 @@ your compiler from breaking your dependencies.
 
 \subsubsection{Give your dependency chain a good start}
 The load that heads your dependency chain must use proper
-ordering, for example, \co{lockless_dereference()},
-\co{rcu_dereference()}, or
-a \co{READ_ONCE()} followed by \co{smp_read_barrier_depends()}.
+ordering, for example \co{rcu_dereference()} or \co{READ_ONCE()}.
 Failure to follow this rule can have serious side effects:
 
 \begin{enumerate}
@@ -4353,8 +4345,7 @@ set of memory-ordering primitives, which are as follows:
 	that depend on prior operations to be ordered.
 	This primitive is a no-op on all platforms except Alpha, but
 	is normally not used directly, but rather as part of
-	something like \co{lockless_dereference()} or
-	\co{rcu_dereference()}.
+	something like \co{READ_ONCE()} or \co{rcu_dereference()}.
 \item	[\tco{smp_mb__before_atomic()}] that forces ordering of accesses
 	preceding the \co{smp_mb__before_atomic()} against accesses following
 	a later RMW atomic operation.
@@ -5133,8 +5124,8 @@ You can replace a given acquire with a a dependency in environments permitting
 this, keeping in mind that the C11 standard's memory model does \emph{not}
 permit this.
 Note also that a dependency leading to a load must be headed by
-a \co{lockless_dereference()} or an \co{rcu_dereference()}:
-\co{READ_ONCE()} is not sufficient.
+a \co{READ_ONCE()} or an \co{rcu_dereference()}:
+a plain C-language load is not sufficient.
 Never forget to carefully review
 Sections~\ref{sec:memorder:Address- and Data-Dependency Difficulties}
 and~\ref{sec:memorder:Control-Dependency Calamities}, because

Re: lockless_dereference() in perfbook

[Paul E. McKenney]

On Sun, Dec 02, 2018 at 12:32:19PM +0900, Akira Yokosawa wrote:
> On 2018/12/01 17:10:53 -0800, Paul E. McKenney wrote:
> > On Sun, Dec 02, 2018 at 07:25:21AM +0900, Akira Yokosawa wrote:
> >> On 2018/12/01 10:30:19 -0800, Paul E. McKenney wrote:
> >>> On Sat, Dec 01, 2018 at 04:48:03PM +0900, Akira Yokosawa wrote:
> >>>> Hi Paul,
> >>>>
> >>>> As LKMM dropped lockless_dereference() when it was merged in v4.17,
> >>>> CodeSamples/formal/litmus/C-MP+o-wmb-o+ld-addr-o.litmus fails to
> >>>> be evaluated by "make run-herd7" under CodeSamples/formal/herd.
> >>>>
> >>>> lockless_dereference() is still covered by CodeSamples/formal/litmus/api.h
> >>>> and klitmus7, so the test can be evaluated by litmus7 and "klitmus7 at the
> >>>> moment.
> >>>>
> >>>> In commit 48ec12dac0c3 ("memorder: Update based on v4.15 Linux kernel
> >>>> de-Alpha-ication"), you added a footnote in Section 15.2.3 saying:
> >>>>
> >>>>     Note that lockless_dereference() is not needed on v4.15 and later,
> >>>>     and therefore is not available in these later Linux kernels.
> >>>>
> >>>> There remain several lockless_dereference()s in perfbook without any
> >>>> updates.
> >>>>
> >>>> In the Answer to Quick Quiz 15.15, lockless_dereference() is mentioned
> >>>> several times.
> >>>>
> >>>> Quick Quiz 15.17 says:
> >>>>
> >>>>     Why doesn't line 18 of Listing 15.12 need a lockless_dereference()?
> >>>>
> >>>> Leading paragraph of Section 15.3.2.1 says:
> >>>>
> >>>>     The load that heads your dependency chain must use proper ordering,
> >>>>     for example, lockless_dereference(), rcu_dereference(), or a READ_ONCE()
> >>>>     followed by smp_read_barrier_depends().
> >>>>
> >>>> In the middle of Section 15.5, there is a sentence:
> >>>>
> >>>>     Note also that a dependency leading to a load must be headed by a
> >>>>     lockless_dereference() or an rcu_dereference(): READ_ONCE() is not
> >>>>     sufficient.
> >>>>
> >>>> Could you look into them?
> >>>>
> >>>> One problem in regard to litmus tests might be that there is no means
> >>>> to indicate plain accesses with no memory barrier in current LKMM.
> >>>> At the moment, C-MP+o-wmb-o+o-addr-o.litmus behaves identically as
> >>>> C-MP+o-wmb-o+ld-addr-o.litmus would do.
> >>>
> >>> Good catches!  How about the following?
> >>>
> >>> 1.	I remove CodeSamples/formal/litmus/C-MP+o-wmb-o+ld-addr-o.litmus.
> >>>
> >>> 2.	I add a comment to the lockless_dereference() call in
> >>> 	lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test
> >>> 	stating that this API member is obsolete.
> >>>
> >>> 3.	I remove the (\path{C-MP+o-wmb-o+ld-addr-o.litmus}) from the
> >>> 	discussion.  I also add a LaTeX comment stating which commit
> >>> 	removed this file for future reference.
> >>>
> >>> 4.	I remove lockless_dereference() from CodeSamples/formal/litmus/api.h.
> >>>
> >>> Does that sound reasonable?
> >>
> >> Yes, it does!
> >>
> >> Maybe discussion of
> >> lst:memorder:Message-Passing Address-Dependency Litmus Test (No Ordering)
> >> needs further tweaks, including the update of its caption, i.e.,
> >> it is now _ordered_. Quick Quiz 15.13 looks odd as of now.
> >>
> >> And the caption to
> >> lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test
> >> also needs update to indicate it is not necessary any more.
> >>
> >> Looking forward to seeing the update.
> > 
> > How about the following?
> > 
> > 							Thanx, Paul
> > 
> > ------------------------------------------------------------------------
> > 
> > commit c9a15859a4451ee449b8d46dc9845e050acf5760
> > Author: Paul E. McKenney <paulmck@linux.ibm.com>
> > Date:   Sat Dec 1 17:07:35 2018 -0800
> > 
> >     memorder: Clean up reference to lockless_dereference()
> >     
> >     The lockless_dereference() primitive has been obsolete since Linux
> >     kernel version v4.15, but it is mentioned in several places in the
> >     memory-ordering chapter and in a litmus test.  This commit removes that
> >     litmus test, removes the definition of lockless_dereference(), makes
> >     READ_ONCE() work properly on DEC Alpha, and clearly labels remaining
> >     instances of lockless_dereference() in the text as obsolete.
> >     
> >     Reported-by: Akira Yokosawa <akiyks@gmail.com>
> >     Signed-off-by: Paul E. McKenney <paulmck@linux.ibm.com>
> > 
> > diff --git a/CodeSamples/formal/litmus/C-MP+o-wmb-o+ld-addr-o.litmus b/CodeSamples/formal/litmus/C-MP+o-wmb-o+ld-addr-o.litmus
> > deleted file mode 100644
> > index 117a6e3ffda8..000000000000
> > --- a/CodeSamples/formal/litmus/C-MP+o-wmb-o+ld-addr-o.litmus
> > +++ /dev/null
> > @@ -1,30 +0,0 @@
> > -C C-MP+o-wmb-o+ld-ad-o
> > -
> > -{
> > -int y=1;
> > -int *x1 = &y;
> > -}
> > -
> > -{
> > -#include "api.h"
> > -}
> > -
> > -P0(int* x0, int** x1) {
> > -
> > -	WRITE_ONCE(*x0, 2);
> > -	smp_wmb();
> > -	WRITE_ONCE(*x1, x0);
> > -
> > -}
> > -
> > -P1(int** x1) {
> > -
> > -	int *r2;
> > -	int r3;
> > -
> > -	r2 = lockless_dereference(*x1);
> > -	r3 = READ_ONCE(*r2);
> > -
> > -}
> > -
> > -exists (1:r2=x0 /\ 1:r3=1)
> > diff --git a/CodeSamples/formal/litmus/api.h b/CodeSamples/formal/litmus/api.h
> > index 0f14a48dd128..8bf0ba629a9e 100644
> > --- a/CodeSamples/formal/litmus/api.h
> > +++ b/CodeSamples/formal/litmus/api.h
> > @@ -1,7 +1,12 @@
> >  #ifndef __API_H__
> >  #define __API_H__
> >  #ifndef READ_ONCE
> > -#define READ_ONCE(x) __atomic_load_n((typeof(x) *)&(x), __ATOMIC_RELAXED)
> > +#define __READ_ONCE(x) __atomic_load_n((typeof(x) *)&(x), __ATOMIC_RELAXED)
> > +#ifdef __alpha__
> > +#define READ_ONCE(x) ({ typeof(x) ___x = __READ_ONCE(x); smp_mb(); ___x; })
> > +#else
> > +#define READ_ONCE(x) __READ_ONCE(x)
> > +#endif
> >  #define WRITE_ONCE(x, v) __atomic_store_n((typeof(x) *)&(x), (v), __ATOMIC_RELAXED)
> >  #define smp_mb() __atomic_thread_fence(__ATOMIC_SEQ_CST)
> >  #define smp_rmb() __atomic_thread_fence(__ATOMIC_ACQUIRE) /* outside std. */
> > @@ -14,10 +19,5 @@
> >  	__atomic_compare_exchange_n((x), &__old, (n), 1, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED); \
> >  	__old; \
> >  })
> > -#ifdef __alpha__
> > -#define lockless_dereference(x) ({ typeof(x) ___x = READ_ONCE(x); smp_mb(); ___x; })
> > -#else
> > -#define lockless_dereference(x) READ_ONCE(x)
> > -#endif
> >  #endif
> >  #endif
> > diff --git a/memorder/memorder.tex b/memorder/memorder.tex
> > index 943c3af3fe6f..bdeaba10e0b2 100644
> > --- a/memorder/memorder.tex
> > +++ b/memorder/memorder.tex
> > @@ -590,8 +590,7 @@ are at most two threads involved.
> >  	Section~\ref{sec:memorder:Address- and Data-Dependency Difficulties}.
> >  
> >  	The \co{*_dereference()} row captures the address and data
> > -	dependency ordering provided by \co{lockless_dereference()},
> > -	\co{rcu_dereference()}, and friends.
> > +	dependency ordering provided by \co{rcu_dereference()} and friends.
> >  
> >  	The ``Successful \co{*_acquire()}'' row captures the fact that many
> >  	CPUs have special ``acquire'' forms of loads and of atomic RMW
> > @@ -1411,7 +1410,7 @@ P1(int** x1) {
> >    int *r2;
> >    int r3;
> >  
> > -  r2 = lockless_dereference(*x1);
> > +  r2 = lockless_dereference(*x1); // Obsolete
> >    r3 = READ_ONCE(*r2);
> >  
> >  }
> > @@ -1426,12 +1425,14 @@ exists (1:r2=x0 /\ 1:r3=1)
> >  \end{listing}
> >  
> >  Listing~\ref{lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test}
> > -(\path{C-MP+o-wmb-o+ld-addr-o.litmus})
> > -shows how to make this work reliably on old Linux kernels running on
> > +% \path{C-MP+o-wmb-o+ld-addr-o.litmus} available at commit bc4b1c3f3b35
> > +% ("styleguide: Loosen restriction on comment in litmus test")
> > +shows how to make this work reliably on pre-v4.15 Linux kernels running on
> >  DEC Alpha, by
> >  replacing line~21's \co{READ_ONCE()} with \co{lockless_dereference()},\footnote{
> >  	Note that \co{lockless_dereference()} is not needed on v4.15 and
> > -	later, and therefore is not available in these later Linux kernels.}
> > +	later, and therefore is not available in these later Linux kernels.
> > +	Nor is it needed in versions of this book containing this sentence.}
> >  which acts like \co{READ_ONCE()} on all platforms other than DEC Alpha,
> >  where it acts like a \co{READ_ONCE()} followed by an \co{smp_mb()},
> >  thereby forcing the required ordering on all platforms, in turn
> > @@ -1482,8 +1483,7 @@ Because no production-quality platform speculates stores,
> >  it is not possible for the \co{WRITE_ONCE()} on line~10 to overwrite
> >  the \co{WRITE_ONCE()} on line~21, meaning that the \co{exists}
> >  clause on line~25 cannot trigger, even on DEC Alpha, even
> > -without the \co{lockless_dereference()} that is required in the
> > -dependent-load case.
> > +in pre-v4.15 Linux kernels.
> >  
> >  \QuickQuiz{}
> >  	But how do we know that \emph{all} platforms really avoid
> > @@ -1520,19 +1520,23 @@ dependent-load case.
> >  	There is one (famous) exception to this rule for weakly ordered
> >  	platforms, and that exception is DEC Alpha for load-to-load
> >  	address dependencies.
> > -	And this is why DEC Alpha requires the explicit memory barrier
> > -	supplied for it by the \co{lockless_dereference()} on line~21 of
> > +	And this is why, in Linux kernels predating v4.15, DEC Alpha
> > +	requires the explicit memory barrier supplied for it by the
> > +	now-obsolete \co{lockless_dereference()} on line~21 of
> >  	Listing~\ref{lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test}.
> >  	However, DEC Alpha does track load-to-store address dependencies,
> >  	which is why line~20 of
> >  	Listing~\ref{lst:memorder:S Address-Dependency Litmus Test}
> > -	does not have a \co{lockless_dereference()}.
> > +	does not need a \co{lockless_dereference()}, even in Linux
> > +	kernels predating v4.15.
> >  
> >  	To sum up, current platforms either respect address dependencies
> >  	implicitly, as is the case for TSO platforms (x86, mainframe,
> >  	SPARC,~...), have hardware tracking for address dependencies
> > -	(ARM, PowerPC, MIPS,~...), or have the required memory barriers
> > -	supplied by \co{lockless_dereference()} (DEC Alpha).
> > +	(ARM, PowerPC, MIPS,~...), have the required memory barriers
> > +	supplied by \co{READ_ONCE()} (DEC Alpha in Linux kernel v4.15 and
> > +	later), or require the memory barriers supplied by
> > +	\co{rcu_dereference()} (DEC Alpha in Linux kernel v4.14 and earlier).
> >  } \QuickQuizEnd
> >  
> >  \QuickQuiz{}
> > @@ -1605,16 +1609,6 @@ The value loaded by line~18 is what line~19 stores.
> >  The ordering provided by this data dependency is sufficient to prevent
> >  the \co{exists} clause from triggering.
> >  
> > -\QuickQuiz{}
> > -	Why doesn't line~18 of
> > -	Listing~\ref{lst:memorder:Load-Buffering Data-Dependency Litmus Test}
> > -	need a \co{lockless_dereference()}?
> > -\QuickQuizAnswer{
> > -	Data dependencies are always load-to-store dependencies, and
> > -	so all platforms respect them, even DEC Alpha, and for the
> > -	same reasons that they respect load-to-store address dependencies.
> > -} \QuickQuizEnd
> > -
> >  Just as with address dependencies, data dependencies are
> >  fragile and can be easily broken by compiler optimizations, as discussed in
> >  Section~\ref{sec:memorder:Address- and Data-Dependency Difficulties}.
> > @@ -3388,9 +3382,7 @@ your compiler from breaking your dependencies.
> >  
> >  \subsubsection{Give your dependency chain a good start}
> >  The load that heads your dependency chain must use proper
> > -ordering, for example, \co{lockless_dereference()},
> > -\co{rcu_dereference()}, or
> > -a \co{READ_ONCE()} followed by \co{smp_read_barrier_depends()}.
> > +ordering, for example \co{rcu_dereference()} or \co{READ_ONCE()}.
> >  Failure to follow this rule can have serious side effects:
> >  
> >  \begin{enumerate}
> > @@ -4353,8 +4345,7 @@ set of memory-ordering primitives, which are as follows:
> >  	that depend on prior operations to be ordered.
> >  	This primitive is a no-op on all platforms except Alpha, but
> >  	is normally not used directly, but rather as part of
> > -	something like \co{lockless_dereference()} or
> > -	\co{rcu_dereference()}.
> > +	something like \co{READ_ONCE()} or \co{rcu_dereference()}.
> >  \item	[\tco{smp_mb__before_atomic()}] that forces ordering of accesses
> >  	preceding the \co{smp_mb__before_atomic()} against accesses following
> >  	a later RMW atomic operation.
> > @@ -5133,8 +5124,8 @@ You can replace a given acquire with a a dependency in environments permitting
> >  this, keeping in mind that the C11 standard's memory model does \emph{not}
> >  permit this.
> >  Note also that a dependency leading to a load must be headed by
> > -a \co{lockless_dereference()} or an \co{rcu_dereference()}:
> > -\co{READ_ONCE()} is not sufficient.
> > +a \co{READ_ONCE()} or an \co{rcu_dereference()}:
> > +a plain C-language load is not sufficient.
> >  Never forget to carefully review
> >  Sections~\ref{sec:memorder:Address- and Data-Dependency Difficulties}
> >  and~\ref{sec:memorder:Control-Dependency Calamities}, because
> > 
> 
> How about adding the following changes on top of yours?
> 
>         Thanks, Akira
> 
> ----->8----
> >From 23b28a43fb1b0873d4661efff29b727c4d665773 Mon Sep 17 00:00:00 2001
> From: Akira Yokosawa <akiyks@gmail.com>
> Date: Sun, 2 Dec 2018 12:21:27 +0900
> Subject: [PATCH] memorder: Amend captions to 'Message-Passing Address-Dependency' tests
> 
> Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
> ---
>  memorder/memorder.tex | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/memorder/memorder.tex b/memorder/memorder.tex
> index bdeaba1..ac05ddc 100644
> --- a/memorder/memorder.tex
> +++ b/memorder/memorder.tex
> @@ -1352,7 +1352,7 @@ exists (1:r2=x0 /\ 1:r3=1)
>  }
>  \centering
>  \theverbbox
> -\caption{Message-Passing Address-Dependency Litmus Test (No Ordering)}
> +\caption{Message-Passing Address-Dependency Litmus Test (No Ordering on Pre v4.15)}
>  \label{lst:memorder:Message-Passing Address-Dependency Litmus Test (No Ordering)}
>  \end{listing}
>  
> @@ -1420,7 +1420,7 @@ exists (1:r2=x0 /\ 1:r3=1)
>  }
>  \centering
>  \theverbbox
> -\caption{Enforced Ordering of Message-Passing Address-Dependency Litmus Test}
> +\caption{Enforced Ordering of Message-Passing Address-Dependency Litmus Test (Pre v4.15)}
>  \label{lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test}
>  \end{listing}

Good point!

I applied this, but changed "Pre" to "Before" (no added line breaks)
and also applied this change to the various \ref{} commands.  As always,
please let me know if I messed anything up!

							Thanx, Paul

------------------------------------------------------------------------

commit cc25e121f9e267aa82d3d7bf1d30f65cc52b2c64
Author: Akira Yokosawa <akiyks@gmail.com>
Date:   Sun Dec 2 08:06:31 2018 -0800

    memorder: Amend captions to 'Message-Passing Address-Dependency' tests
    
    Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
    [ paulmck: s/Pre/Before/ and also apply to references. ]
    Signed-off-by: Paul E. McKenney <paulmck@linux.ibm.com>

diff --git a/memorder/memorder.tex b/memorder/memorder.tex
index bdeaba10e0b2..b5c1e906e185 100644
--- a/memorder/memorder.tex
+++ b/memorder/memorder.tex
@@ -1352,11 +1352,11 @@ exists (1:r2=x0 /\ 1:r3=1)
 }
 \centering
 \theverbbox
-\caption{Message-Passing Address-Dependency Litmus Test (No Ordering)}
-\label{lst:memorder:Message-Passing Address-Dependency Litmus Test (No Ordering)}
+\caption{Message-Passing Address-Dependency Litmus Test (No Ordering Before v4.15)}
+\label{lst:memorder:Message-Passing Address-Dependency Litmus Test (No Ordering Before v4.15)}
 \end{listing}
 
-Listing~\ref{lst:memorder:Message-Passing Address-Dependency Litmus Test (No Ordering)}
+Listing~\ref{lst:memorder:Message-Passing Address-Dependency Litmus Test (No Ordering Before v4.15)}
 (\path{C-MP+o-wmb-o+o-addr-o.litmus})
 shows a linked variant of the message-passing pattern.
 The head pointer is \co{x1}, which initially
@@ -1384,7 +1384,7 @@ However, prior to v4.15, this is not the case on DEC Alpha, which can
 in effect use a speculated value for the dependent load, as described
 in more detail in Section~\ref{sec:memorder:Alpha}.
 Therefore, on older versions of Linux,
-Listing~\ref{lst:memorder:Message-Passing Address-Dependency Litmus Test (No Ordering)}'s
+Listing~\ref{lst:memorder:Message-Passing Address-Dependency Litmus Test (No Ordering Before v4.15)}'s
 \co{exists} clause \emph{can} trigger.
 
 \begin{listing}[tbp]
@@ -1420,11 +1420,11 @@ exists (1:r2=x0 /\ 1:r3=1)
 }
 \centering
 \theverbbox
-\caption{Enforced Ordering of Message-Passing Address-Dependency Litmus Test}
-\label{lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test}
+\caption{Enforced Ordering of Message-Passing Address-Dependency Litmus Test (Before v4.15)}
+\label{lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test (Before v4.15)}
 \end{listing}
 
-Listing~\ref{lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test}
+Listing~\ref{lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test (Before v4.15)}
 % \path{C-MP+o-wmb-o+ld-addr-o.litmus} available at commit bc4b1c3f3b35
 % ("styleguide: Loosen restriction on comment in litmus test")
 shows how to make this work reliably on pre-v4.15 Linux kernels running on
@@ -1488,7 +1488,7 @@ in pre-v4.15 Linux kernels.
 \QuickQuiz{}
 	But how do we know that \emph{all} platforms really avoid
 	triggering the \co{exists} clauses in
-	Listings~\ref{lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test}
+	Listings~\ref{lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test (Before v4.15)}
 	and~\ref{lst:memorder:S Address-Dependency Litmus Test}?
 \QuickQuizAnswer{
 	Answering this requires identifying three major groups of platforms:
@@ -1499,7 +1499,7 @@ in pre-v4.15 Linux kernels.
 	The TSO platforms order all pairs of memory references except for
 	prior stores against later loads.
 	Because the address dependency on lines~21 and~22 of
-	Listing~\ref{lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test}
+	Listing~\ref{lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test (Before v4.15)}
 	is instead a load followed by another load, TSO platforms preserve
 	this address dependency.
 	They also preserve the address dependency on lines~20 and~21 of
@@ -1511,7 +1511,7 @@ in pre-v4.15 Linux kernels.
 	Weakly ordered platforms don't necessarily maintain ordering of
 	unrelated accesses.
 	However, the address dependencies in
-	Listings~\ref{lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test}
+	Listings~\ref{lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test (Before v4.15)}
 	and~\ref{lst:memorder:S Address-Dependency Litmus Test}
 	are not unrelated: There is an address dependency.
 	The hardware tracks dependencies and maintains the needed
@@ -1523,7 +1523,7 @@ in pre-v4.15 Linux kernels.
 	And this is why, in Linux kernels predating v4.15, DEC Alpha
 	requires the explicit memory barrier supplied for it by the
 	now-obsolete \co{lockless_dereference()} on line~21 of
-	Listing~\ref{lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test}.
+	Listing~\ref{lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test (Before v4.15)}.
 	However, DEC Alpha does track load-to-store address dependencies,
 	which is why line~20 of
 	Listing~\ref{lst:memorder:S Address-Dependency Litmus Test}