Skip to contentSkip to conversation

index: Add several major tags

PATCH In review Akira Yokosawa 2 participants 8 messages Jan 25, 2022

lore
Share & tools
lore
#0 lore raw

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
#1 lore raw

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
index 2d1f316c..d39e0f01 100644
@@ -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
#2 lore raw

PATCH 2/6 locking: Mark major references to 'livelock', 'starvation", and 'unfairness'

In reply to Akira Yokosawa

Note: \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
index c223d40c..e8477f6d 100644
@@ -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
#3 lore raw

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
index 1c6b61d9..3793c233 100644
@@ -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
#4 lore raw

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
index d5fbf471..13a3c59b 100644
@@ -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
#5 lore raw

PATCH 5/6 debugging: Add indexing tags to '(anti-)heisenbug'

In reply to Akira Yokosawa

Note: 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
index 13a3c59b..fbe581f7 100644
@@ -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
#6 lore raw

PATCH 6/6 index: Reform indexing tags related to 'memory consistency'

In reply to Akira Yokosawa

Hierarchical 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
index 12d3e5d8..e33c5161 100644
@@ -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
index 1d4a2404..f0cb33e3 100644
@@ -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
index 2331966b..1fc2d8b5 100644
@@ -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
index 3793c233..865eff95 100644
@@ -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
index a00103ef..b8acbe3d 100644
@@ -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
#7 lore raw
In reply to Akira Yokosawa
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 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