Skip to contentSkip to conversation

advsync: Use pseudo asm in code sequence

PATCH In review Akira Yokosawa 2 participants 16 messages Apr 16, 2017 – Apr 17, 2017

lore
Share & tools
lore
#0 lore raw

cover advsync: Use pseudo asm in code sequence

From 6efc224d8e6d2b64bf7a86b52d03de01ccea7032 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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(-)
Signature · 1 line
2.7.4
#1 lore raw

PATCH 1/14 advsync: Use pseudo asm in sequence in 'Paring' section

From 78178c3e06de801acde0c35f7077d7d27fa7900f Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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.

---
 advsync/memorybarriers.tex | 56 +++++++++++++++++++++++++++-------------------
 1 file changed, 33 insertions(+), 23 deletions(-)
advsync/memorybarriers.tex +33 -23
index 5f8ea7f..d82a968 100644
@@ -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}
Signature · 1 line
2.7.4
#2 lore raw

PATCH 2/14 advsync: Substitute READ_ONCE()/WRITE_ONCE() for ACCESS_ONCE()

In reply to Akira Yokosawa

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

---
 advsync/memorybarriers.tex | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
advsync/memorybarriers.tex +1 -1
index d82a968..173380a 100644
@@ -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
Signature · 1 line
2.7.4
#3 lore raw

PATCH 3/14 advsync: Use pseudo asm in sequence in 'Review of Locking Impl'

In reply to Akira Yokosawa

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

---
 advsync/memorybarriers.tex | 18 +++++++++---------
 1 file changed, 9 insertions(+), 9 deletions(-)
advsync/memorybarriers.tex +9 -9
index 173380a..299c436 100644
@@ -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}
Signature · 1 line
2.7.4
#4 lore raw

PATCH 4/14 advsync: Backport upstream commits regarding reordering example

In reply to Akira Yokosawa

From 1c166a002fcdc1a7f1d417a0d81b7400cd7a80fe Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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.

---
 advsync/memorybarriers.tex | 30 +++++++++++++++---------------
 1 file changed, 15 insertions(+), 15 deletions(-)
advsync/memorybarriers.tex +15 -15
index 299c436..fc361ad 100644
@@ -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}
Signature · 1 line
2.7.4
#5 lore raw

PATCH 5/14 advsync: Use pseudo asm in reordering example

In reply to Akira Yokosawa

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

---
 advsync/memorybarriers.tex | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
advsync/memorybarriers.tex +2 -2
index fc361ad..f60eb3a 100644
@@ -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}
Signature · 1 line
2.7.4
#6 lore raw

PATCH 6/14 advsync: Use pseudo asm in another reordering example

In reply to Akira Yokosawa

From 8e91a3c8c27c2d39d7954138676be3e0b2f5cf98 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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.

---
 advsync/memorybarriers.tex | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)
advsync/memorybarriers.tex +5 -4
index f60eb3a..270c868 100644
@@ -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}
Signature · 1 line
2.7.4
#7 lore raw

PATCH 7/14 advsync: Avoid indent after minipages

In reply to Akira Yokosawa

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

---
 advsync/memorybarriers.tex | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)
advsync/memorybarriers.tex +6 -6
index 270c868..8173684 100644
@@ -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.
 
Signature · 1 line
2.7.4
#8 lore raw

PATCH 8/14 advsync: Add footnote to imply necessity of data dependency barrier

In reply to Akira Yokosawa

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

---
 advsync/memorybarriers.tex | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)
advsync/memorybarriers.tex +9 -1
index 8173684..7b50511 100644
@@ -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}
Signature · 1 line
2.7.4
#9 lore raw

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

In reply to Akira Yokosawa

From 20904d88784deb41bfb853b198017eca6a058bc8 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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.

---
 advsync/memorybarriers.tex | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)
advsync/memorybarriers.tex +4 -4
index 7b50511..f94b113 100644
@@ -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}
Signature · 1 line
2.7.4
#10 lore raw

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

In reply to Akira Yokosawa

From e3b3c4d1b9bc77cbedd5282ae00c26bc853750d9 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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.

---
 advsync/memorybarriers.tex | 32 ++++++++++++++++----------------
 1 file changed, 16 insertions(+), 16 deletions(-)
advsync/memorybarriers.tex +16 -16
index f94b113..0cd690b 100644
@@ -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}
 
Signature · 1 line
2.7.4
#11 lore raw

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

In reply to Akira Yokosawa

From 8b244f86f9f9c26e2de37624c5ad9064367c3332 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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.

---
 advsync/memorybarriers.tex | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)
advsync/memorybarriers.tex +4 -3
index 0cd690b..6cf25a9 100644
@@ -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,
Signature · 1 line
2.7.4
#12 lore raw

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

In reply to Akira Yokosawa

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

---
 advsync/memorybarriers.tex | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)
advsync/memorybarriers.tex +3 -1
index 6cf25a9..2b36214 100644
@@ -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:
Signature · 1 line
2.7.4
#13 lore raw

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

In reply to Akira Yokosawa

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

---
 advsync/memorybarriers.tex | 33 +++++++++++++++++----------------
 1 file changed, 17 insertions(+), 16 deletions(-)
advsync/memorybarriers.tex +17 -16
index 2b36214..9b878f3 100644
@@ -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}
Signature · 1 line
2.7.4
#14 lore raw

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

In reply to Akira Yokosawa

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

---
 advsync/memorybarriers.tex | 100 ++++++++++++++++++++++-----------------------
 1 file changed, 50 insertions(+), 50 deletions(-)
advsync/memorybarriers.tex +50 -50
index 9b878f3..f36994e 100644
@@ -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}
Signature · 1 line
2.7.4
#15 lore raw
In reply to Akira Yokosawa
Quoted 21 lines · Akira Yokosawa
Quoted 1 line

From 6efc224d8e6d2b64bf7a86b52d03de01ccea7032 Mon Sep 17 00:00:00 2001

From: Akira Yokosawa <[email protected]>
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.

Quoted 4 lines

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

Quoted 25 lines

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(-)
Signature · 1 line
2.7.4