advsync: Use pseudo asm in code sequence
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
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
@@ -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
PATCH 2/14 advsync: Substitute READ_ONCE()/WRITE_ONCE() for ACCESS_ONCE()
In reply to Akira YokosawaFrom 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
@@ -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
PATCH 3/14 advsync: Use pseudo asm in sequence in 'Review of Locking Impl'
In reply to Akira YokosawaFrom 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
@@ -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
PATCH 4/14 advsync: Backport upstream commits regarding reordering example
In reply to Akira YokosawaFrom 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
@@ -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
PATCH 5/14 advsync: Use pseudo asm in reordering example
In reply to Akira YokosawaFrom 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
@@ -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
PATCH 6/14 advsync: Use pseudo asm in another reordering example
In reply to Akira YokosawaFrom 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
@@ -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
PATCH 7/14 advsync: Avoid indent after minipages
In reply to Akira YokosawaFrom 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
@@ -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
PATCH 8/14 advsync: Add footnote to imply necessity of data dependency barrier
In reply to Akira YokosawaFrom 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
@@ -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
PATCH 9/14 advsync: Use READ_ONCE()/WRITE_ONCE() in sequence of 'Device Operations'
In reply to Akira YokosawaFrom 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
@@ -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
PATCH 10/14 advsync: Use READ_ONCE()/WRITE_ONCE() in sequence in 'Guarantees'
In reply to Akira YokosawaFrom 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
@@ -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
PATCH 11/14 advsync: Rename Section 'Guarantees' to 'Minimal Guarantees'
In reply to Akira YokosawaFrom 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
@@ -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
PATCH 12/14 advsync: Add another footnote implying data dependency barrier
In reply to Akira YokosawaFrom 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
@@ -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
PATCH 13/14 advsync: Use pseudo asm in sequence in 'Data Dependency Barriers'
In reply to Akira YokosawaFrom 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
@@ -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
PATCH 14/14 advsync: Use pseudo asm in sequence in 'SMP Barrier Pairing'
In reply to Akira YokosawaFrom 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
@@ -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
Quoted 21 lines · Akira Yokosawa
Quoted 1 line
From
6efc224d8e6d2b64bf7a86b52d03de01ccea7032Mon Sep 17 00:00:00 2001From: Akira Yokosawa <[email protected]>
Date: Mon, 17 Apr 2017 06:53:11 +0900
Subject: [PATCH 00/14] advsync: Use pseudo asm in code sequenceHi 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() forACCESS_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