index: Add several major tags
cover index: Add several major tags
Hi Paul,
Here are another set of patches WRT indexing.
Patches 1/6 and 2/6 add indexing tags for major references to "NBS", "forward-progress guarantee", "livelock", "starvation", and "unfairness".
Patch 3/6 adds API indexing tags to historic lockless_dereference(). Patch 4/6 fixes a typo found while preparing Patch 5/6. Patch 5/6 adds major and minor tags to "(anti-)heisenbug". Patch 6/6 reforms hierarchical indexes under "Memory consistency" to those under "Consistency".
Patch 5/6 needs the \IXalth{}{}{} macro as \IXh{anti-}{heisenbug} would put a space between the two arguments in the text.
Thanks, Akira
--
Akira Yokosawa (6):
advsync: Add major indexing tags to 'NBS' and 'forward-progress
guarantee'
locking: Mark major references to 'livelock', 'starvation", and
'unfairness'
memorder: Add indexing tags for historic lockless_dereference()
debugging: Fix typo (heisenberg -> heisenbug)
debugging: Add indexing tags to '(anti-)heisenbug'
index: Reform indexing tags related to 'memory consistency'
advsync/advsync.tex | 8 ++++---- debugging/debugging.tex | 7 ++++--- future/formalregress.tex | 2 +- glossary.tex | 6 +++--- indexsee.tex | 7 +++++++ locking/locking.tex | 8 ++++---- memorder/memorder.tex | 8 ++++---- together/seqlock.tex | 3 +-- 8 files changed, 28 insertions(+), 21 deletions(-)
base-commit: 641067ba70383ad751512bd02cfc7cec17647523
Signature · 1 line
2.17.1
PATCH 1/6 advsync: Add major indexing tags to 'NBS' and 'forward-progress guarantee'
Also increment number of classes.
Enum item of "Bounded population-oblivious wait-free" was added in commit 6abfa973f401 ("glossary: Additions from index, F-K").
--- advsync/advsync.tex | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)
advsync/advsync.tex +4 -4
@@ -30,7 +30,7 @@ Memory ordering is also quite important, but it warrants its own \cref{chp:Advanced Synchronization: Memory Ordering}. The second form of advanced synchronization provides the stronger -\IXpl{forward-progress guarantee} needed for parallel real-time computing, +forward-progress guarantees needed for parallel real-time computing, which is the topic of \cref{sec:advsync:Parallel Real-Time Computing}.
@@ -80,9 +80,9 @@ them, please re-read it's supposed to do.} {\emph{Robert A. Heinlein}} -The term \IXacrfst{nbs}~\cite{MauriceHerlihy90a} -describes seven classes of \IX{linearizable} algorithms with differing -\emph{\IXpl{forward-progress guarantee}}~\cite{DanAlitarh2013PracticalProgress}, +The term \IXBacrfst{nbs}~\cite{MauriceHerlihy90a} +describes eight classes of \IX{linearizable} algorithms with differing +\emph{\IXBpl{forward-progress guarantee}}~\cite{DanAlitarh2013PracticalProgress}, which are as follows: \begin{enumerate}
Signature · 1 line
2.17.1
PATCH 2/6 locking: Mark major references to 'livelock', 'starvation", and 'unfairness'
In reply to Akira YokosawaNote: \IX{} or \IXB{} markers can't be used in \subsection{}. low-level macro of \ucindex{} is used instead for "livelock" and "starvation".
--- locking/locking.tex | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)
locking/locking.tex +4 -4
@@ -878,14 +878,14 @@ addressed with other tools. Nevertheless, the strategies described in this section have proven quite useful in many settings. -\subsection{Livelock and Starvation} +\subsection{Livelock and Starvation}\ucindex{Livelock|BF}\ucindex{Starvation|BF} \label{sec:locking:Livelock and Starvation} Although conditional locking can be an effective deadlock-avoidance mechanism, it can be abused. Consider for example the beautifully symmetric example shown in \cref{lst:locking:Abusing Conditional Locking}. -This example's beauty hides an ugly \IX{livelock}. +This example's beauty hides an ugly livelock. To see this, consider the following sequence of events: \begin{listing}
@@ -967,7 +967,7 @@ retry: \lnlbl[thr2:retry] assuming that the global lock need not be acquired too often. }\QuickQuizEnd -Livelock can be thought of as an extreme form of \IX{starvation} where +Livelock can be thought of as an extreme form of starvation where a group of threads starves, rather than just one of them.\footnote{ Try not to get too hung up on the exact definitions of terms like livelock, starvation, and unfairness.
@@ -1060,7 +1060,7 @@ these problems by maintaining low \IX{lock contention}. \label{fig:locking:System Architecture and Lock Unfairness} \end{figure} -\IX{Unfairness} can be thought of as a less-severe form of starvation, +\IXB{Unfairness} can be thought of as a less-severe form of starvation, where a subset of threads contending for a given lock are granted the lion's share of the acquisitions. This can happen on machines with shared caches or \IXacr{numa} characteristics,
Signature · 1 line
2.17.1
PATCH 3/6 memorder: Add indexing tags for historic lockless_dereference()
In reply to Akira Yokosawa--- memorder/memorder.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
memorder/memorder.tex +2 -2
@@ -1280,7 +1280,7 @@ exists (1:r2=x0 /\ 1:r3=1) % ("styleguide: Loosen restriction on comment in litmus test") shows how to make this work reliably on pre-v4.15 Linux kernels running on DEC Alpha, by replacing \clnref{read}'s \co{READ_ONCE()} with -\co{lockless_dereference()},\footnote{ +\apikh{lockless_dereference()},\footnote{ Note that \co{lockless_dereference()} is not needed on v4.15 and later, and therefore is not available in these later Linux kernels. Nor is it needed in versions of this book containing this sentence.}
@@ -1355,7 +1355,7 @@ in pre-v4.15 Linux kernels. address dependencies. And this is why, in Linux kernels predating v4.15, DEC Alpha requires the explicit memory barrier supplied for it by the - now-obsolete \co{lockless_dereference()} on \clnref{deref} of + now-obsolete \apikh{lockless_dereference()} on \clnref{deref} of \cref{lst:memorder:Enforced Ordering of Message-Passing Address-Dependency Litmus Test (Before v4.15)}. \end{fcvref} \begin{fcvref}[ln:formal:C-S+o-wmb-o+o-addr-o:whole]
Signature · 1 line
2.17.1
PATCH 4/6 debugging: Fix typo (heisenberg -> heisenbug)
In reply to Akira Yokosawa--- debugging/debugging.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
debugging/debugging.tex +1 -1
@@ -1718,7 +1718,7 @@ to create an anti-heisenbug by adding delay in this manner. Of course, this begs the question of how to find the race condition in the first place. Although very lucky developers might accidentally create delay-based -anti-heisenbergs when adding debug code, this is in general a dark art. +anti-heisenbugs when adding debug code, this is in general a dark art. Nevertheless, there are a number of things you can do to find your race conditions.
Signature · 1 line
2.17.1
PATCH 5/6 debugging: Add indexing tags to '(anti-)heisenbug'
In reply to Akira YokosawaNote: Use the \IXBalth{}{}{} macro as \IXBh{anti-}{heisenbug} would put a space between the two arguments in the text.
--- debugging/debugging.tex | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-)
debugging/debugging.tex +3 -2
@@ -1660,7 +1660,7 @@ of a bug appearing, which is why extremely lightweight tracing and assertion mechanism are so critically important. -The term ``\IX{heisenbug}'' was inspired by the \pplsur{Weiner}{Heisenberg} +The term ``\IXB{heisenbug}'' was inspired by the \pplsur{Weiner}{Heisenberg} \IX{Uncertainty Principle} from quantum physics, which states that it is impossible to exactly quantify a given particle's position and velocity at any given
@@ -1683,7 +1683,8 @@ more easily reproduced! If the field of physics inspired the name of this problem, it is only fair that the field of physics should inspire the solution. Fortunately, particle physics is up to the task: -Why not create an anti-heisenbug to annihilate the heisenbug? +Why not create an \IXBalth{anti-heisenbug}{anti-}{heisenbug} +to annihilate the heisenbug? Or, perhaps more accurately, to annihilate the heisen-ness of the heisenbug? Although producing an anti-heisenbug for a given heisenbug is more an
Signature · 1 line
2.17.1
PATCH 6/6 index: Reform indexing tags related to 'memory consistency'
In reply to Akira YokosawaHierarchical indices of "sequential consistency", "process consistency", and "weak consistency" are under "memory consistency".
However, "Memory consistency, sequential" would indicate the term "Sequential memory consistency" were preferred to "Sequential consistency".
Improve the organization by putting those terms under "Consistency" alongside "memory consistency" and avoid such a false impression.
Also add several "see xxxxx" references in indexsee.tex.
--- future/formalregress.tex | 2 +- glossary.tex | 6 +++--- indexsee.tex | 7 +++++++ memorder/memorder.tex | 4 ++-- together/seqlock.tex | 3 +-- 5 files changed, 14 insertions(+), 8 deletions(-)
future/formalregress.tex +1 -1
@@ -139,7 +139,7 @@ It is critically important that formal-verification tools correctly model their environment. One all-too-common omission is the memory model, where a great many formal-verification tools, including Promela/spin, are -restricted to \IXalth{sequential consistency}{sequential}{memory consistency}. +restricted to \IXh{sequential}{consistency}. The QRCU experience related in \cref{sec:formal:Is QRCU Really Correct?} is an important cautionary tale.
glossary.tex +3 -3
@@ -386,7 +386,7 @@ caches, and store buffers in which values might be stored. However, this term is often used to denote the main memory itself, excluding caches and store buffers. -\item[\IXG{Memory Consistency}:] +\item[\IXGh{Memory}{Consistency}:] A set of properties that impose constraints on the order in which accesses to groups of variables appear to occur. Memory consistency models range from sequential consistency,
@@ -493,7 +493,7 @@ A source-code memory access that simply mentions the name of the object being accessed. (See ``Marked access''.) -\item[\IXGalth{Process Consistency}{process}{memory consistency}:] +\item[\IXGh{Process}{Consistency}:] A memory-consistency model in which each CPU's stores appear to occur in program order, but in which different CPUs might see accesses from more than one CPU as occurring in different orders.
@@ -607,7 +607,7 @@ \item[\IXGh{Sequence}{Lock}:] A reader-writer synchronization mechanism in which readers retry their operations if a writer was present. -\item[\IXGalth{Sequential Consistency}{sequential}{memory consistency}:] +\item[\IXGh{Sequential}{Consistency}:] A memory-consistency model where all memory references appear to occur in an order consistent with a single global order, and where each CPU's memory references
indexsee.tex +7 -0
@@ -1,6 +1,7 @@ \index{Associativity|see{Cache associativity}} \index{Associativity miss|see{Cache miss, associativity}} \index{Bounded wait free|see{Wait free, bounded}} +\index{Bounded population-oblivious wait free|see{Wait free, bounded population-oblivious}} \index{Capacity miss|see{Cache miss, capacity}} \index{Code locking|see{Locking, code}} \index{Communication miss|see{Cache miss, communication}}
@@ -8,8 +9,14 @@ \index{Direct-mapped cache|see{Cache, direct-mapped}} \index{Exclusive lock|see{Lock, exclusive}} \index{Fully associative cache|see{Cache, fully associative}} +\index{Memory-barrier overhead|see{Overhead, memory-barrier}} +\index{Memory consistency|see{Consistency, memory}} +\index{Process consistency|see{Consistency, process}} +\index{RCU read-side critical section|see{Critical section, RCU read-side}} \index{Read-side critical section|see{Critical section, read-side}} \index{Reader-writer lock|see{Lock, reader-writer}} \index{Sequence lock|see{Lock, sequence}} +\index{Sequencial consistency|see{Consistency, sequencial}} +\index{Weak consistency|see{Consistency, weak}} \index{Write miss|see{Cache miss, write}} \index{Write-side critical section|see{Critical section, write-side}}
memorder/memorder.tex +2 -2
@@ -4313,7 +4313,7 @@ architecture-specific code or synchronization primitives. Besides, they say that a little knowledge is a very dangerous thing. Just imagine the damage you could do with a lot of knowledge! For those who wish to understand more about individual CPUs' -\IX{memory consistency} models, the next sections describe those of a few +\IXh{memory}{consistency} models, the next sections describe those of a few popular and prominent CPUs. Although there is no substitute for actually reading a given CPU's documentation, these sections do give a good overview.
@@ -4672,7 +4672,7 @@ defined its memory ordering with an executable formal model~\cite{ARMv8A:2017}. \subsection{Itanium} \label{sec:memorder:Itanium} -Itanium offers a \IXalth{weak consistency}{weak}{memory consistency} +Itanium offers a \IXh{weak}{consistency} model, so that in absence of explicit memory-barrier instructions or dependencies, Itanium is within its rights to arbitrarily reorder memory references~\cite{IntelItanium02v2}.
together/seqlock.tex +1 -2
@@ -132,8 +132,7 @@ notably in the dcache subsystem~\cite{NeilBrown2015RCUwalk}. Note that it is likely that similar schemes also work with hazard pointers. -This approach provides \IXalth{sequential consistency}{sequential} -{memory consistency} to successful readers, +This approach provides \IXh{sequential}{consistency} to successful readers, each of which will either see the effects of a given update or not, with any partial updates resulting in a read-side retry. Sequential consistency is an extremely strong guarantee, incurring equally
Signature · 1 line
2.17.1
Quoted 8 lines · Akira Yokosawa
Hi Paul,
Here are another set of patches WRT indexing.
Patches 1/6 and 2/6 add indexing tags for major references to "NBS", "forward-progress guarantee", "livelock", "starvation", and "unfairness".
Quoted 8 lines
Patch 3/6 adds API indexing tags to historic
lockless_dereference(). Patch 4/6 fixes a typo found while preparing Patch 5/6. Patch 5/6 adds major and minor tags to "(anti-)heisenbug". Patch 6/6 reforms hierarchical indexes under "Memory consistency" to those under "Consistency".Patch 5/6 needs the \IXalth{}{}{} macro as \IXh{anti-}{heisenbug} would put a space between the two arguments in the text.
Good fixes and updates, queued and pushed, thank you!
I suppose that one could argue that one prominent anti-Heisenberg was none other than Albert Einstein (who was showed up by Niels Bohr). But you are right. I really did mean anti-heisenbug. ;-)
Thanx, Paul
Quoted 27 lines
Thanks, Akira
--
Akira Yokosawa (6):
advsync: Add major indexing tags to 'NBS' and 'forward-progress
guarantee'
locking: Mark major references to 'livelock', 'starvation", and
'unfairness'
memorder: Add indexing tags for historiclockless_dereference()
debugging: Fix typo (heisenberg -> heisenbug)
debugging: Add indexing tags to '(anti-)heisenbug'
index: Reform indexing tags related to 'memory consistency'advsync/advsync.tex | 8 ++++---- debugging/debugging.tex | 7 ++++--- future/formalregress.tex | 2 +- glossary.tex | 6 +++--- indexsee.tex | 7 +++++++ locking/locking.tex | 8 ++++---- memorder/memorder.tex | 8 ++++---- together/seqlock.tex | 3 +-- 8 files changed, 28 insertions(+), 21 deletions(-)base-commit:
641067ba70383ad751512bd02cfc7cec17647523Signature · 1 line
2.17.1