[PATCH 00/14] advsync: Use pseudo asm in code sequence

[PATCH 00/14] advsync: Use pseudo asm in code sequence

[Akira Yokosawa]

From 6efc224d8e6d2b64bf7a86b52d03de01ccea7032 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Mon, 17 Apr 2017 06:53:11 +0900
Subject: [PATCH 00/14] advsync: Use pseudo asm in code sequence

Hi Paul,

This series substitutes pseudo-asm codes for C style statements
in code sequences in 'Memory Barrier' section.

Other than the substitution, Patch 2 replaces ACCESS_ONCE(),
Patch 4 is a backport of the changes made in memory-barriers.txt,
Patches 8 and 12 add footnotes to imply the necessity of data
dependency barrier, and Patch 11 renames Section "Guarantee"
to "Minimal Guarantee".

My guess is that the original intention of the "Guarantee"
section was to present minimal guarantees free of memory barriers.
When the necessity of read dependency barrier was recognized,
the barrier sneaked into this section.

In LaTeX, as footnotes can prevent readers' misunderstanding,
We can preserve the original intention.

Thoughts?

                                  Thanks Akira
--
Akira Yokosawa (14):
  advsync: Use pseudo asm in sequence in 'Paring' section
  advsync: Substitute READ_ONCE()/WRITE_ONCE() for ACCESS_ONCE()
  advsync: Use pseudo asm in sequence in 'Review of Locking Impl'
  advsync: Backport upstream commits regarding reordering example
  advsync: Use pseudo asm in reordering example
  advsync: Use pseudo asm in another reordering example
  advsync: Avoid indent after minipages
  advsync: Add footnote to imply necessity of data dependency barrier
  advsync: Use READ_ONCE()/WRITE_ONCE() in sequence of 'Device
    Operations'
  advsync: Use READ_ONCE()/WRITE_ONCE() in sequence in 'Guarantees'
  advsync: Rename Section 'Guarantee' to 'Minimal Guarantee'
  advsync: Add another footnote implying data dependency barrier
  advsync: Use pseudo asm in sequence in 'Data Dependency Barriers'
  advsync: Use pseudo asm in sequence in 'SMP Barrier Pairing'

 advsync/memorybarriers.tex | 321 ++++++++++++++++++++++++---------------------
 1 file changed, 172 insertions(+), 149 deletions(-)

-- 
2.7.4

[PATCH 01/14] advsync: Use pseudo asm in sequence in 'Paring' section

[Akira Yokosawa]

From 78178c3e06de801acde0c35f7077d7d27fa7900f Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sat, 15 Apr 2017 23:21:37 +0900
Subject: [PATCH 01/14] advsync: Use pseudo asm in sequence in 'Paring' section

Also format 2 CPU scenario in Quick Quiz Answer as a table.

Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
 advsync/memorybarriers.tex | 56 +++++++++++++++++++++++++++-------------------
 1 file changed, 33 insertions(+), 23 deletions(-)

diff --git a/advsync/memorybarriers.tex b/advsync/memorybarriers.tex
index 5f8ea7f..d82a968 100644
--- a/advsync/memorybarriers.tex
+++ b/advsync/memorybarriers.tex
@@ -520,11 +520,11 @@ on this weaker if-then conditional ordering guarantee.
 \tt
 \scriptsize
 \begin{tabular}{l|l}
-	\nf{CPU 1} &		\nf{CPU 2} \\
+	\nf{CPU 1}	& \nf{CPU 2} \\
 	\hline
-	access(A);	&	access(B); \\
-	\tco{smp_mb();}	&	\tco{smp_mb();} \\
-	access(B);	&	access(A); \\
+	<access> A	& <access> B \\
+	<memory barrier>& <memory barrier> \\
+	<access> B	& <access> A \\
 \end{tabular}
 \end{minipage}
 \vspace{5pt}
@@ -615,11 +615,11 @@ pairings that portable software may depend on.
 	\tt
 	\scriptsize
 	\begin{tabular}{l|l}
-		\nf{CPU 1} &		\nf{CPU 2} \\
+		\nf{CPU 1}	& \nf{CPU 2} \\
 		\hline
-		A=1;		&	Y=B; \\
-		\tco{smp_mb();}	&	\tco{smp_mb();} \\
-		B=1;		&	X=A; \\
+		STORE A = 1	& Y = LOAD B \\
+		<memory barrier>& <memory barrier> \\
+		STORE B = 1	& X = LOAD A \\
 	\end{tabular}
 	\end{minipage}
 	\vspace{5pt}
@@ -647,11 +647,11 @@ pairings that portable software may depend on.
 	\tt
 	\scriptsize
 	\begin{tabular}{l|l}
-		\nf{CPU 1} &		\nf{CPU 2} \\
+		\nf{CPU 1}	& \nf{CPU 2} \\
 		\hline
-		X=A;            &	Y=B; \\
-		\tco{smp_mb();}	&	\tco{smp_mb();} \\
-		B=1;            &	A=1; \\
+		X = LOAD A	& Y = LOAD B \\
+		<memory barrier>& <memory barrier> \\
+		STORE B = 1	& STORE A = 1 \\
 	\end{tabular}
 	\end{minipage}
 	\vspace{5pt}
@@ -684,11 +684,11 @@ pairings that portable software may depend on.
 	\tt
 	\scriptsize
 	\begin{tabular}{l|l}
-		\nf{CPU 1} &		\nf{CPU 2} \\
+		\nf{CPU 1}	& \nf{CPU 2} \\
 		\hline
-		X=A;		&	B=2; \\
-		\tco{smp_mb();}	&	\tco{smp_mb();} \\
-		B=1;		&	A=1; \\
+		X = LOAD A	& STORE B = 2 \\
+		<memory barrier>& <memory barrier> \\
+		STORE B = 1	& STORE A = 1 \\
 	\end{tabular}
 	\end{minipage}
 	\vspace{5pt}
@@ -735,9 +735,19 @@ keep in mind that they used to be a \emph{lot} harder on some systems!
 \QuickQuizAnswer{
 	The scenario is as follows, with~A and~B both initially zero:

-	CPU~0: A=1; \co{smp_mb()}; r1=B;
-
-	CPU~1: B=1; \co{smp_mb()}; r2=A;
+	\vspace{5pt}
+	\begin{minipage}[t]{\columnwidth}
+	\tt
+	\scriptsize
+	\begin{tabular}{l|l}
+		\nf{CPU 0}	& \nf{CPU 1} \\
+		\hline
+		STORE A = 1	& STORE B = 1 \\
+		<memory barrier>& <memory barrier> \\
+		r1 = LOAD B	& r2 = LOAD A \\
+	\end{tabular}
+	\end{minipage}
+	\vspace{5pt}

 	If neither of the loads see the corresponding store, when both
 	CPUs finish, both \co{r1} and \co{r2} will be equal to zero.
@@ -765,11 +775,11 @@ keep in mind that they used to be a \emph{lot} harder on some systems!
 	\tt
 	\scriptsize
 	\begin{tabular}{l|l}
-		\nf{CPU 1} &		\nf{CPU 2} \\
+		\nf{CPU 1}	& \nf{CPU 2} \\
 		\hline
-		A=1;		&	B=2; \\
-		\tco{smp_mb();}	&	\tco{smp_mb();} \\
-		B=1;		&	A=2; \\
+		STORE A = 1	& STORE B = 2 \\
+		<memory barrier>& <memory barrier> \\
+		STORE B = 1	& STORE A = 2 \\
 	\end{tabular}
 	\end{minipage}
 	\vspace{5pt}
-- 
2.7.4

[PATCH 02/14] advsync: Substitute READ_ONCE()/WRITE_ONCE() for ACCESS_ONCE()

[Akira Yokosawa]

From ca4c666a7c30440610ce148f73960c2e21030a56 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sat, 15 Apr 2017 23:41:35 +0900
Subject: [PATCH 02/14] advsync: Substitute READ_ONCE()/WRITE_ONCE() for ACCESS_ONCE()

Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
 advsync/memorybarriers.tex | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/advsync/memorybarriers.tex b/advsync/memorybarriers.tex
index d82a968..173380a 100644
--- a/advsync/memorybarriers.tex
+++ b/advsync/memorybarriers.tex
@@ -490,7 +490,7 @@ CPUs' accesses are to one single variable.
 In this single-variable case, cache coherence guarantees the
 global ordering, at least assuming that some of the more aggressive
 compiler optimizations are disabled via the Linux kernel's
-\co{ACCESS_ONCE()} directive or C++11's relaxed
+\co{READ_ONCE()} and \co{WRITE_ONCE()} directives or C++11's relaxed
 atomics~\cite{PeteBecker2011N3242}.
 In contrast, if there are multiple variables, memory barriers are
 required for the CPUs to consistently agree on the order for current
-- 
2.7.4

[PATCH 03/14] advsync: Use pseudo asm in sequence in 'Review of Locking Impl'

[Akira Yokosawa]

From 81c2ce55ce99ede156f407c869b18289366917e4 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 16 Apr 2017 00:01:10 +0900
Subject: [PATCH 03/14] advsync: Use pseudo asm in sequence in 'Review of Locking Impl'

Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
 advsync/memorybarriers.tex | 18 +++++++++---------
 1 file changed, 9 insertions(+), 9 deletions(-)

diff --git a/advsync/memorybarriers.tex b/advsync/memorybarriers.tex
index 173380a..299c436 100644
--- a/advsync/memorybarriers.tex
+++ b/advsync/memorybarriers.tex
@@ -1060,16 +1060,16 @@ the sequence of operations might be as follows:
 \begin{minipage}[t]{\columnwidth}
 \tt \scriptsize
 \begin{tabular}{l|l}
-	\nf{CPU 1} &		\nf{CPU 2} \\
+	\nf{CPU 1}		& \nf{CPU 2} \\
 	\hline
-	(critical section) &	\tco{atomic_xchg(&lck->a, 1)->1} \\
-	\tco{smp_mb();}    &	lck->a->1 \\
-	lck->a=0;	   &	lck->a->1 \\
-	&			lck->a->0 \\
-	&			(implicit \tco{smp_mb()} 1) \\
-	&			\tco{atomic_xchg(&lck->a, 1)->0} \\
-	&			(implicit \tco{smp_mb()} 2) \\
-	&			(critical section) \\
+	(critical section)	& \tco{atomic_xchg(&lck->a, 1)} $\rightarrow$1 \\
+	<memory barrier>	& LOAD lck->a $\rightarrow$1 \\
+	STORE lck->a = 0	& LOAD lck->a $\rightarrow$1 \\
+				& LOAD lck->a $\rightarrow$0 \\
+				& (implicit memory barrier \#1) \\
+				& \tco{atomic_xchg(&lck->a, 1)} $\rightarrow$0 \\
+				& (implicit memory barrier \#2) \\
+				& (critical section) \\
 \end{tabular}
 \end{minipage}
 \vspace{5pt}
-- 
2.7.4

[PATCH 04/14] advsync: Backport upstream commits regarding reordering example

[Akira Yokosawa]

From 1c166a002fcdc1a7f1d417a0d81b7400cd7a80fe Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 16 Apr 2017 07:42:52 +0900
Subject: [PATCH 04/14] advsync: Backport upstream commits regarding reordering example

Backport following commits for memory-barriers.txt in upstream

  o 615cc2c9cf95 ("Documentation/memory-barriers.txt: fix important
    typo re memory barriers")
  o 8ab8b3e1837f ("documentation: memory-barriers.txt: Correct
    example for reorderings")

Also reword the leading sentence to clarify 'A' and 'B' are shared,
and reword the closing sentence to clarify 'x' and 'y' are local.

Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
 advsync/memorybarriers.tex | 30 +++++++++++++++---------------
 1 file changed, 15 insertions(+), 15 deletions(-)

diff --git a/advsync/memorybarriers.tex b/advsync/memorybarriers.tex
index 299c436..fc361ad 100644
--- a/advsync/memorybarriers.tex
+++ b/advsync/memorybarriers.tex
@@ -1152,7 +1152,7 @@ interface between the CPU and rest of the system (the dotted lines).


 For example, consider the following sequence of events given the
-initial values {\tt \{A~=~1, B~=~2\}}:
+initial values of shared variables {\tt \{A~=~1, B~=~2\}}:

 \vspace{5pt}
 \begin{minipage}[t]{\columnwidth}
@@ -1161,8 +1161,8 @@ initial values {\tt \{A~=~1, B~=~2\}}:
 \begin{tabular}{l|l}
 	\nf{CPU 1} &	\nf{CPU 2} \\
 	\hline
-	A = 3; &	x = A; \\
-	B = 4; &	y = B; \\
+	A = 3; &	x = B; \\
+	B = 4; &	y = A; \\
 \end{tabular}
 \end{minipage}
 \vspace{5pt}
@@ -1176,30 +1176,30 @@ denoted by ``st'':
 \tt
 \scriptsize
 \begin{tabular}{llll}
-	st A=3, & st B=4, & x=ld A$\rightarrow$3, & y=ld B$\rightarrow$4 \\
-	st A=3, & st B=4, & y=ld B$\rightarrow$4, & x=ld A$\rightarrow$3 \\
-	st A=3, & x=ld A$\rightarrow$3, & st B=4, & y=ld B$\rightarrow$4 \\
-	st A=3, & x=ld A$\rightarrow$3, & y=ld B$\rightarrow$2, & st B=4 \\
-	st A=3, & y=ld B$\rightarrow$2, & st B=4, & x=ld A$\rightarrow$3 \\
-	st A=3, & y=ld B$\rightarrow$2, & x=ld A$\rightarrow$3, & st B=4 \\
-	st B=4, & st A=3, & x=ld A$\rightarrow$3, & y=ld B$\rightarrow$4 \\
+	st A=3, & st B=4, & x=ld B$\rightarrow$3, & y=ld A$\rightarrow$4 \\
+	st A=3, & st B=4, & y=ld A$\rightarrow$4, & x=ld B$\rightarrow$3 \\
+	st A=3, & x=ld B$\rightarrow$3, & st B=4, & y=ld A$\rightarrow$4 \\
+	st A=3, & x=ld B$\rightarrow$3, & y=ld A$\rightarrow$2, & st B=4 \\
+	st A=3, & y=ld A$\rightarrow$2, & st B=4, & x=ld B$\rightarrow$3 \\
+	st A=3, & y=ld A$\rightarrow$2, & x=ld B$\rightarrow$3, & st B=4 \\
+	st B=4, & st A=3, & x=ld B$\rightarrow$3, & y=ld A$\rightarrow$4 \\
 	st B=4, & ... & & \\
 	... & & & \\
 \end{tabular}
 \end{minipage}
 \vspace{5pt}

-and can thus result in four different combinations of values:
+and can thus result in four different combinations of local values:

 \vspace{5pt}
 \begin{minipage}[t]{\columnwidth}
 \tt
 \scriptsize
 \begin{tabular}{ll}
-	x == 1, & y == 2 \\
-	x == 1, & y == 4 \\
-	x == 3, & y == 2 \\
-	x == 3, & y == 4 \\
+	x == 2, & y == 1 \\
+	x == 2, & y == 3 \\
+	x == 4, & y == 1 \\
+	x == 4, & y == 3 \\
 \end{tabular}
 \end{minipage}
 \vspace{5pt}
-- 
2.7.4

[PATCH 05/14] advsync: Use pseudo asm in reordering example

[Akira Yokosawa]

From 79fac48313712400900333ca8f3e920e0cc1ed75 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 16 Apr 2017 07:52:31 +0900
Subject: [PATCH 05/14] advsync: Use pseudo asm in reordering example

Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
 advsync/memorybarriers.tex | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/advsync/memorybarriers.tex b/advsync/memorybarriers.tex
index fc361ad..f60eb3a 100644
--- a/advsync/memorybarriers.tex
+++ b/advsync/memorybarriers.tex
@@ -1161,8 +1161,8 @@ initial values of shared variables {\tt \{A~=~1, B~=~2\}}:
 \begin{tabular}{l|l}
 	\nf{CPU 1} &	\nf{CPU 2} \\
 	\hline
-	A = 3; &	x = B; \\
-	B = 4; &	y = A; \\
+	STORE A = 3 &	x = LOAD B \\
+	STORE B = 4 &	y = LOAD A \\
 \end{tabular}
 \end{minipage}
 \vspace{5pt}
-- 
2.7.4

[PATCH 06/14] advsync: Use pseudo asm in another reordering example

[Akira Yokosawa]

From 8e91a3c8c27c2d39d7954138676be3e0b2f5cf98 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 16 Apr 2017 07:58:21 +0900
Subject: [PATCH 06/14] advsync: Use pseudo asm in another reordering example

Also make it clear the initial values are for shared variables.

Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
 advsync/memorybarriers.tex | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

diff --git a/advsync/memorybarriers.tex b/advsync/memorybarriers.tex
index f60eb3a..270c868 100644
--- a/advsync/memorybarriers.tex
+++ b/advsync/memorybarriers.tex
@@ -1209,17 +1209,18 @@ perceived by the loads made by another CPU in the same order as the stores were
 committed.

 As a further example, consider this sequence of events given the
-initial values {\tt \{A~=~1, B~=~2, C~=~3, P~=~\&A, Q~=~\&C\}}:
+initial values of shared variables
+{\tt \{A~=~1, B~=~2, C~=~3, P~=~\&A, Q~=~\&C\}}:

 \vspace{5pt}
 \begin{minipage}[t]{\columnwidth}
 \tt
 \scriptsize
 \begin{tabular}{l|l}
-	\nf{CPU 1} &	\nf{CPU 2} \\
+	\nf{CPU 1}	& \nf{CPU 2} \\
 	\hline
-	B = 4; &	Q = P; \\
-	P = \&B &	D = *Q; \\
+	STORE B = 4	& Q = LOAD P \\
+	STORE P = \&B	& D = LOAD *Q \\
 \end{tabular}
 \end{minipage}
 \vspace{5pt}
-- 
2.7.4

[PATCH 07/14] advsync: Avoid indent after minipages

[Akira Yokosawa]

From b987758d115a7260e9ff8f7453c69a6e6bc9768b Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 16 Apr 2017 08:11:14 +0900
Subject: [PATCH 07/14] advsync: Avoid indent after minipages

Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
 advsync/memorybarriers.tex | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/advsync/memorybarriers.tex b/advsync/memorybarriers.tex
index 270c868..8173684 100644
--- a/advsync/memorybarriers.tex
+++ b/advsync/memorybarriers.tex
@@ -1186,9 +1186,9 @@ denoted by ``st'':
 	st B=4, & ... & & \\
 	... & & & \\
 \end{tabular}
+\vspace{3pt}
 \end{minipage}
-\vspace{5pt}
-
+%
 and can thus result in four different combinations of local values:

 \vspace{5pt}
@@ -1263,9 +1263,9 @@ be used:
 *A = 5;
 x = *D;
 \end{verbatim}
+\vspace{1pt}
 \end{minipage}
-\vspace{5pt}
-
+%
 but this might show up as either of the following two sequences:

 \vspace{5pt}
@@ -1275,9 +1275,9 @@ but this might show up as either of the following two sequences:
 STORE *A = 5, x = LOAD *D
 x = LOAD *D, STORE *A = 5
 \end{verbatim}
+\vspace{1pt}
 \end{minipage}
-\vspace{5pt}
-
+%
 the second of which will almost certainly result in a malfunction, since it set
 the address \emph{after} attempting to read the register.

-- 
2.7.4

[PATCH 08/14] advsync: Add footnote to imply necessity of data dependency barrier

[Akira Yokosawa]

From 827f6c65b5fbae89edab6b86b70d39a7582d708d Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 16 Apr 2017 08:15:26 +0900
Subject: [PATCH 08/14] advsync: Add footnote to imply necessity of data dependency barrier

Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
 advsync/memorybarriers.tex | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)

diff --git a/advsync/memorybarriers.tex b/advsync/memorybarriers.tex
index 8173684..7b50511 100644
--- a/advsync/memorybarriers.tex
+++ b/advsync/memorybarriers.tex
@@ -1244,7 +1244,15 @@ following results are possible:
 \vspace{5pt}

 Note that CPU~2 will never try and load~C into~D because the CPU will load~P
-into~Q before issuing the load of~*Q.
+into~Q before issuing the load of~*Q.\footnote{Although it might sound
+	counterintuitive, one of the results,
+	{\tt\scriptsize (Q~==~\&B) and (D~==~2)},
+	does not necessarily mean that CPU~1's
+	{\tt\scriptsize STORE B~=~4} was issued
+	{\em after} {\tt\scriptsize STORE P~=~\&B}.
+	To reach a consensus in ordering, we need a pair of memory barriers
+	as is described in
+	Section~\ref{sec:advsync:Data Dependency Barriers}.}

 \subsection{Device Operations}
 \label{sec:advsync:Device Operations}
-- 
2.7.4

[PATCH 09/14] advsync: Use READ_ONCE()/WRITE_ONCE() in sequence of 'Device Operations'

[Akira Yokosawa]

From 20904d88784deb41bfb853b198017eca6a058bc8 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 16 Apr 2017 23:44:56 +0900
Subject: [PATCH 09/14] advsync: Use READ_ONCE()/WRITE_ONCE() in sequence of 'Device Operations'

Using pseudo-asm code here results in a redundant look. In this
section, using READ_ONCE()/WRITE_ONCE() in code sequence gives
a good contrast with the resulting ordering of memory accesses.

Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
 advsync/memorybarriers.tex | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/advsync/memorybarriers.tex b/advsync/memorybarriers.tex
index 7b50511..f94b113 100644
--- a/advsync/memorybarriers.tex
+++ b/advsync/memorybarriers.tex
@@ -1261,15 +1261,15 @@ Some devices present their control interfaces as collections of memory
 locations, but the order in which the control registers are accessed is very
 important.  For instance, imagine an Ethernet card with a set of internal
 registers that are accessed through an address port register~(A) and a data
-port register~(D).  To read internal register~5, the following code might then
-be used:
+port register~(D).  To read internal register~5, the following code (in C)
+might then be used:

 \vspace{5pt}
 \begin{minipage}[t]{\columnwidth}
 \scriptsize
 \begin{verbatim}
-*A = 5;
-x = *D;
+WRITE_ONCE(*A, 5);
+x = READ_ONCE(*D);
 \end{verbatim}
 \vspace{1pt}
 \end{minipage}
-- 
2.7.4

[PATCH 10/14] advsync: Use READ_ONCE()/WRITE_ONCE() in sequence in 'Guarantees'

[Akira Yokosawa]

From e3b3c4d1b9bc77cbedd5282ae00c26bc853750d9 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 16 Apr 2017 10:55:49 +0900
Subject: [PATCH 10/14] advsync: Use READ_ONCE()/WRITE_ONCE() in sequence in 'Guarantees'

Using pseudo-asm code for sequences here also gives redundant look.
Using READ_ONCE/WRITE_ONCE() instead is a good idea.
In memory-barriers.txt, sequences corresponding to the latter part
of this section are not yet enclosed by READ_ONCE()/WRITE_ONCE(),
but memory subsystem can merge overlapping accesses even if these
directives are used.

Also use "," as delimiters in the memory access ordering lists.

Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
 advsync/memorybarriers.tex | 32 ++++++++++++++++----------------
 1 file changed, 16 insertions(+), 16 deletions(-)

diff --git a/advsync/memorybarriers.tex b/advsync/memorybarriers.tex
index f94b113..0cd690b 100644
--- a/advsync/memorybarriers.tex
+++ b/advsync/memorybarriers.tex
@@ -1296,12 +1296,12 @@ There are some minimal guarantees that may be expected of a CPU:

 \begin{enumerate}
 \item	On any given CPU, dependent memory accesses will be issued in order,
-	with respect to itself.  This means that for:
+	with respect to itself.  This means that for a sequence (in C):

 \begin{minipage}[t]{\columnwidth}
 \scriptsize
 \begin{verbatim}
-Q = P; D = *Q;
+Q = READ_ONCE(P); D = READ_ONCE(*Q);
 \end{verbatim}
 \end{minipage}

@@ -1322,7 +1322,7 @@ Q = LOAD P, D = LOAD *Q
 \begin{minipage}[t]{\columnwidth}
 \scriptsize
 \begin{verbatim}
-a = *X; *X = b;
+a = READ_ONCE(*X); WRITE_ONCE(*X, b);
 \end{verbatim}
 \end{minipage}

@@ -1341,7 +1341,7 @@ a = LOAD *X, STORE *X = b
 \begin{minipage}[t]{\columnwidth}
 \scriptsize
 \begin{verbatim}
-*X = c; d = *X;
+WRITE_ONCE(*X, c); d = READ_ONCE(*X);
 \end{verbatim}
 \end{minipage}

@@ -1371,7 +1371,7 @@ And there are a number of things that \emph{must} or \emph{must not} be assumed:
 \begin{minipage}[t]{\columnwidth}
 \scriptsize
 \begin{verbatim}
-X = *A; Y = *B; *D = Z;
+X = READ_ONCE(*A); Y = READ_ONCE(*B); WRITE_ONCE(*D, Z);
 \end{verbatim}
 \end{minipage}

@@ -1395,7 +1395,7 @@ STORE *D = Z,  Y = LOAD *B,  X = LOAD *A
 \begin{minipage}[t]{\columnwidth}
 \scriptsize
 \begin{verbatim}
-X = *A; Y = *(A + 4);
+X = READ_ONCE(*A); Y = READ_ONCE(*(A + 4));
 \end{verbatim}
 \end{minipage}

@@ -1404,9 +1404,9 @@ X = *A; Y = *(A + 4);
 \begin{minipage}[t]{\columnwidth}
 \scriptsize
 \begin{verbatim}
-X = LOAD *A; Y = LOAD *(A + 4);
-Y = LOAD *(A + 4); X = LOAD *A;
-{X, Y} = LOAD {*A, *(A + 4) };
+X = LOAD *A, Y = LOAD *(A + 4)
+Y = LOAD *(A + 4), X = LOAD *A
+{X, Y} = LOAD {*A, *(A + 4) }
 \end{verbatim}
 \vspace{1pt}
 \end{minipage}
@@ -1416,7 +1416,7 @@ Y = LOAD *(A + 4); X = LOAD *A;
 \begin{minipage}[t]{\columnwidth}
 \scriptsize
 \begin{verbatim}
-*A = X; *(A + 4) = Y;
+WRITE_ONCE(*A, X); WRITE_ONCE(*(A + 4), Y);
 \end{verbatim}
 \end{minipage}

@@ -1425,9 +1425,9 @@ Y = LOAD *(A + 4); X = LOAD *A;
 \begin{minipage}[t]{\columnwidth}
 \scriptsize
 \begin{verbatim}
-STORE *A = X; STORE *(A + 4) = Y;
-STORE *(A + 4) = Y; STORE *A = X;
-STORE {*A, *(A + 4) } = {X, Y};
+STORE *A = X, STORE *(A + 4) = Y
+STORE *(A + 4) = Y, STORE *A = X
+STORE {*A, *(A + 4) } = {X, Y}
 \end{verbatim}
 \vspace{1pt}
 \end{minipage}
@@ -1437,7 +1437,7 @@ STORE {*A, *(A + 4) } = {X, Y};
 \begin{minipage}[t]{\columnwidth}
 \scriptsize
 \begin{verbatim}
-*A = X; *A = Y;
+WRITE_ONCE(*A, X); WRITE_ONCE(*A, Y);
 \end{verbatim}
 \end{minipage}

@@ -1446,8 +1446,8 @@ STORE {*A, *(A + 4) } = {X, Y};
 \begin{minipage}[t]{\columnwidth}
 \scriptsize
 \begin{verbatim}
-STORE *A = X; STORE *A = Y;
-STORE *A = Y;
+STORE *A = X, STORE *A = Y
+STORE *A = Y
 \end{verbatim}
 \end{minipage}

-- 
2.7.4

[PATCH 11/14] advsync: Rename Section 'Guarantees' to 'Minimal Guarantees'

[Akira Yokosawa]

From 8b244f86f9f9c26e2de37624c5ad9064367c3332 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 16 Apr 2017 15:53:34 +0900
Subject: [PATCH 11/14] advsync: Rename Section 'Guarantees' to 'Minimal Guarantees'

Also make it clear that this section discusses guarantees which
are free of memory barriers.

Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
 advsync/memorybarriers.tex | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/advsync/memorybarriers.tex b/advsync/memorybarriers.tex
index 0cd690b..6cf25a9 100644
--- a/advsync/memorybarriers.tex
+++ b/advsync/memorybarriers.tex
@@ -1289,10 +1289,11 @@ x = LOAD *D, STORE *A = 5
 the second of which will almost certainly result in a malfunction, since it set
 the address \emph{after} attempting to read the register.

-\subsection{Guarantees}
-\label{sec:advsync:Guarantees}
+\subsection{Minimal Guarantees}
+\label{sec:advsync:Minimal Guarantees}

-There are some minimal guarantees that may be expected of a CPU:
+In our abstract memory model, there are some minimal guarantees of ordering
+that may be expected of a CPU without any need of memory barriers:

 \begin{enumerate}
 \item	On any given CPU, dependent memory accesses will be issued in order,
-- 
2.7.4

[PATCH 12/14] advsync: Add another footnote implying data dependency barrier

[Akira Yokosawa]

From 9fe9a9b3ae4323986287d291e7a516d90163b742 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 16 Apr 2017 16:11:30 +0900
Subject: [PATCH 12/14] advsync: Add another footnote implying data dependency barrier

Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
 advsync/memorybarriers.tex | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/advsync/memorybarriers.tex b/advsync/memorybarriers.tex
index 6cf25a9..2b36214 100644
--- a/advsync/memorybarriers.tex
+++ b/advsync/memorybarriers.tex
@@ -1315,7 +1315,9 @@ Q = LOAD P, D = LOAD *Q
 \end{verbatim}
 \end{minipage}

-	and always in that order.
+	and always in that order.\footnote{Again, you can not assume
+		any ordering between~\co{P} and the value loaded via
+		the pointer when they are updated by another CPU.}

 \item	Overlapping loads and stores within a particular CPU will appear to be
 	ordered within that CPU.  This means that for:
-- 
2.7.4

[PATCH 13/14] advsync: Use pseudo asm in sequence in 'Data Dependency Barriers'

[Akira Yokosawa]

From 2b779ea16b0185b121063faa0ca534a75d67fc8d Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 16 Apr 2017 16:14:24 +0900
Subject: [PATCH 13/14] advsync: Use pseudo asm in sequence in 'Data Dependency Barriers'

Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
 advsync/memorybarriers.tex | 33 +++++++++++++++++----------------
 1 file changed, 17 insertions(+), 16 deletions(-)

diff --git a/advsync/memorybarriers.tex b/advsync/memorybarriers.tex
index 2b36214..9b878f3 100644
--- a/advsync/memorybarriers.tex
+++ b/advsync/memorybarriers.tex
@@ -1622,8 +1622,8 @@ Section~\ref{sec:advsync:Device Operations}).
 	\begin{minipage}[t]{\columnwidth}
 	\small
 	\begin{verbatim}
-	a = 1;
-	b = 1;
+	STORE a = 1
+	STORE b = 1
 	<write barrier>
 	\end{verbatim}
 	\end{minipage}
@@ -1673,7 +1673,8 @@ of the confines of a given architecture:

 The usage requirements of data dependency barriers are a little subtle, and
 it's not always obvious that they're needed.  To illustrate, consider the
-following sequence of events, with initial values
+following sequence of events (in pseudo asm), with initial values of shared
+variables
 {\tt \{A~=~1, B~=~2, C~=~3, P~=~\&A, Q~=~\&C\}}:

 \vspace{5pt}
@@ -1681,13 +1682,13 @@ following sequence of events, with initial values
 \tt
 \scriptsize
 \begin{tabular}{l|l}
-	\nf{CPU 1} &	\nf{CPU 2} \\
+	\nf{CPU 1}	& \nf{CPU 2} \\
 	\hline
-	B = 4; & \\
-	<write barrier> & \\
-	P = \&B; &	\\
-		&	Q = P; \\
-		&	D = *Q; \\
+	STORE B = 4	& \\
+	<write barrier>	& \\
+	STORE P = \&B	& \\
+			& Q = LOAD P \\
+			& D = LOAD *Q \\
 \end{tabular}
 \end{minipage}
 \vspace{5pt}
@@ -1734,14 +1735,14 @@ address load and the data load (again with initial values of
 \tt
 \scriptsize
 \begin{tabular}{l|p{1.5in}}
-	\nf{CPU 1} &	\nf{CPU 2} \\
+	\nf{CPU 1}	& \nf{CPU 2} \\
 	\hline
-	B = 4; & \\
-	<write barrier> & \\
-	P = \&B; &	\\
-		&	Q = P; \\
-		&	<data dependency barrier> \\
-		&	D = *Q; \\
+	STORE B = 4	& \\
+	<write barrier>	& \\
+	STORE P = \&B	& \\
+			& Q = LOAD P \\
+			& <data dependency barrier> \\
+			& D = LOAD *Q \\
 \end{tabular}
 \end{minipage}
 \vspace{5pt}
-- 
2.7.4

[PATCH 14/14] advsync: Use pseudo asm in sequence in 'SMP Barrier Pairing'

[Akira Yokosawa]

From 6efc224d8e6d2b64bf7a86b52d03de01ccea7032 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 16 Apr 2017 17:07:46 +0900
Subject: [PATCH 14/14] advsync: Use pseudo asm in sequence in 'SMP Barrier Pairing'

Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
 advsync/memorybarriers.tex | 100 ++++++++++++++++++++++-----------------------
 1 file changed, 50 insertions(+), 50 deletions(-)

diff --git a/advsync/memorybarriers.tex b/advsync/memorybarriers.tex
index 9b878f3..f36994e 100644
--- a/advsync/memorybarriers.tex
+++ b/advsync/memorybarriers.tex
@@ -2211,14 +2211,14 @@ write barrier, though, again, a general barrier is viable:
 \tt
 \scriptsize
 \begin{tabular}{l|p{1.5in}}
-	\nf{CPU 1} &	\nf{CPU 2} \\
+	\nf{CPU 1}	& \nf{CPU 2} \\
 	\hline
-	A = 1; & \\
-	<write barrier> & \\
-	B = 2;	&	\\
-		&	X = B; \\
-		&	<read barrier> \\
-		&	Y = A; \\
+	STORE A = 1	& \\
+	<write barrier>	& \\
+	STORE B = 2	& \\
+			& X = LOAD B \\
+			& <read barrier> \\
+			& Y = LOAD A \\
 \end{tabular}
 \end{minipage}
 \vspace{5pt}
@@ -2230,14 +2230,14 @@ Or:
 \tt
 \scriptsize
 \begin{tabular}{l|p{1.5in}}
-	\nf{CPU 1} &	\nf{CPU 2} \\
+	\nf{CPU 1}	& \nf{CPU 2} \\
 	\hline
-	A = 1; & \\
-	<write barrier> & \\
-	B = \&A; &	\\
-		&	X = B; \\
-		&	<data dependency barrier> \\
-		&	Y = *X; \\
+	STORE A = 1	& \\
+	<write barrier>	& \\
+	STORE B = \&A	& \\
+			& X = LOAD B \\
+			& <data dependency barrier> \\
+			& Y = LOAD *X \\
 \end{tabular}
 \end{minipage}
 \vspace{5pt}
@@ -2300,14 +2300,14 @@ loads.  Consider the following sequence of events with initial values
 \tt
 \scriptsize
 \begin{tabular}{l|p{1.5in}}
-	\nf{CPU 1} &	\nf{CPU 2} \\
+	\nf{CPU 1}	& \nf{CPU 2} \\
 	\hline
-	A = 1; & \\
-	B = 2; & \\
-	<write barrier> & \\
-	C = \&B; & 	LOAD X\\
-	D = 4;	&	LOAD C \nf{(gets \tco{&B})} \\
-		&	LOAD *C \nf{(reads \tco{B})} \\
+	STORE A = 1	& \\
+	STORE B = 2	& \\
+	<write barrier>	& \\
+	STORE C = \&B	& LOAD X\\
+	STORE D = 4	& LOAD C \nf{(gets \tco{&B})} \\
+			& LOAD *C \nf{(reads \tco{B})} \\
 \end{tabular}
 \end{minipage}
 \vspace{5pt}
@@ -2336,15 +2336,15 @@ values of {\tt \{B~=~7, X~=~9, Y~=~8, C~=~\&Y\}}:
 \tt
 \scriptsize
 \begin{tabular}{l|p{1.5in}}
-	\nf{CPU 1} &	\nf{CPU 2} \\
+	\nf{CPU 1}	& \nf{CPU 2} \\
 	\hline
-	A = 1; & \\
-	B = 2; & \\
-	<write barrier> & \\
-	C = \&B; & 	LOAD X\\
-	D = 4;	&	LOAD C \nf{(gets \tco{&B})} \\
-		&	<data dependency barrier> \\
-		&	LOAD *C \nf{(reads \tco{B})} \\
+	STORE A = 1	& \\
+	STORE B = 2	& \\
+	<write barrier>	& \\
+	STORE C = \&B	& LOAD X\\
+	STORE D = 4	& LOAD C \nf{(gets \tco{&B})} \\
+			& <data dependency barrier> \\
+			& LOAD *C \nf{(reads \tco{B})} \\
 \end{tabular}
 \end{minipage}
 \vspace{5pt}
@@ -2368,13 +2368,13 @@ following sequence of events, with initial values
 \tt
 \scriptsize
 \begin{tabular}{l|p{1.5in}}
-	\nf{CPU 1} &	\nf{CPU 2} \\
+	\nf{CPU 1}	& \nf{CPU 2} \\
 	\hline
-	A = 1; & \\
-	<write barrier> & \\
-	B = 2; & \\
-		&	LOAD B \\
-		&	LOAD A \\
+	STORE A = 1	& \\
+	<write barrier>	& \\
+	STORE B = 2	& \\
+			& LOAD B \\
+			& LOAD A \\
 \end{tabular}
 \end{minipage}
 \vspace{5pt}
@@ -2399,14 +2399,14 @@ and the load of~\co{A} on CPU~2, again with initial values of
 \tt
 \scriptsize
 \begin{tabular}{l|p{1.5in}}
-	\nf{CPU 1} &	\nf{CPU 2} \\
+	\nf{CPU 1}	& \nf{CPU 2} \\
 	\hline
-	A = 1; & \\
-	<write barrier> & \\
-	B = 2; & \\
-		&	LOAD B \\
-		&	<read barrier> \\
-		&	LOAD A \\
+	STORE A = 1	& \\
+	<write barrier>	& \\
+	STORE B = 2	& \\
+			& LOAD B \\
+			& <read barrier> \\
+			& LOAD A \\
 \end{tabular}
 \end{minipage}
 \vspace{5pt}
@@ -2432,15 +2432,15 @@ with the same initial values of
 \tt
 \scriptsize
 \begin{tabular}{l|p{1.5in}}
-	\nf{CPU 1} &	\nf{CPU 2} \\
+	\nf{CPU 1}	& \nf{CPU 2} \\
 	\hline
-	A = 1; & \\
-	<write barrier> & \\
-	B = 2; & \\
-		&	LOAD B \\
-		&	LOAD A \nf{(1\textsuperscript{st})} \\
-		&	<read barrier> \\
-		&	LOAD A \nf{(2\textsuperscript{nd})} \\
+	STORE A = 1	& \\
+	<write barrier>	& \\
+	STORE B = 2	& \\
+			& LOAD B \\
+			& LOAD A \nf{(1\textsuperscript{st})} \\
+			& <read barrier> \\
+			& LOAD A \nf{(2\textsuperscript{nd})} \\
 \end{tabular}
 \end{minipage}
 \vspace{5pt}
-- 
2.7.4

Re: [PATCH 00/14] advsync: Use pseudo asm in code sequence

[Paul E. McKenney]

On Mon, Apr 17, 2017 at 07:11:37AM +0900, Akira Yokosawa wrote:
> >From 6efc224d8e6d2b64bf7a86b52d03de01ccea7032 Mon Sep 17 00:00:00 2001
> From: Akira Yokosawa <akiyks@gmail.com>
> Date: Mon, 17 Apr 2017 06:53:11 +0900
> Subject: [PATCH 00/14] advsync: Use pseudo asm in code sequence
> 
> Hi Paul,
> 
> This series substitutes pseudo-asm codes for C style statements
> in code sequences in 'Memory Barrier' section.
> 
> Other than the substitution, Patch 2 replaces ACCESS_ONCE(),
> Patch 4 is a backport of the changes made in memory-barriers.txt,
> Patches 8 and 12 add footnotes to imply the necessity of data
> dependency barrier, and Patch 11 renames Section "Guarantee"
> to "Minimal Guarantee".
> 
> My guess is that the original intention of the "Guarantee"
> section was to present minimal guarantees free of memory barriers.
> When the necessity of read dependency barrier was recognized,
> the barrier sneaked into this section.
> 
> In LaTeX, as footnotes can prevent readers' misunderstanding,
> We can preserve the original intention.
> 
> Thoughts?

Good changes, queued, thank you!  Of course, please feel free to
submit clarifying and style patches against memory-barriers.txt if
needed.

							Thanx, Paul

>                                   Thanks Akira
> --
> Akira Yokosawa (14):
>   advsync: Use pseudo asm in sequence in 'Paring' section
>   advsync: Substitute READ_ONCE()/WRITE_ONCE() for ACCESS_ONCE()
>   advsync: Use pseudo asm in sequence in 'Review of Locking Impl'
>   advsync: Backport upstream commits regarding reordering example
>   advsync: Use pseudo asm in reordering example
>   advsync: Use pseudo asm in another reordering example
>   advsync: Avoid indent after minipages
>   advsync: Add footnote to imply necessity of data dependency barrier
>   advsync: Use READ_ONCE()/WRITE_ONCE() in sequence of 'Device
>     Operations'
>   advsync: Use READ_ONCE()/WRITE_ONCE() in sequence in 'Guarantees'
>   advsync: Rename Section 'Guarantee' to 'Minimal Guarantee'
>   advsync: Add another footnote implying data dependency barrier
>   advsync: Use pseudo asm in sequence in 'Data Dependency Barriers'
>   advsync: Use pseudo asm in sequence in 'SMP Barrier Pairing'
> 
>  advsync/memorybarriers.tex | 321 ++++++++++++++++++++++++---------------------
>  1 file changed, 172 insertions(+), 149 deletions(-)
> 
> -- 
> 2.7.4
>