On Sat, 20 Mar 2021 12:23:23 -0700, Paul E. McKenney wrote:
> On Sun, Mar 21, 2021 at 12:50:43AM +0900, Akira Yokosawa wrote:
>> On Sun, 21 Mar 2021 00:24:46 +0900, Akira Yokosawa wrote:
>>> Signed-off-by: Akira Yokosawa <akiyks@xxxxxxxxx>
>>> ---
>>> debugging/debugging.tex | 2 +-
>>> 1 file changed, 1 insertion(+), 1 deletion(-)
>>>
>>> diff --git a/debugging/debugging.tex b/debugging/debugging.tex
>>> index fd52d9e7..3f697f58 100644
>>> --- a/debugging/debugging.tex
>>> +++ b/debugging/debugging.tex
>>> @@ -755,7 +755,7 @@ access to data.
>>> The Kernel Concurrency Sanitizer (KCSAN)~\cite{JonathanCorbet2019KCSAN}
>>> uses existing markings such as \co{READ_ONCE()} and \co{WRITE_ONCE()}
>>> to determine which concurrent accesses deserve warning messages.
>>> -KCSAN has a significant false-positive rate, especially in from the
>>> +KCSAN has a significant false-positive rate, especially from the
>>> viewpoint of developers thinking in terms of C as assembly language
>>> with additional syntax.
>>> KCSAN therefore provides a \co{data_race()} construct to forgive
>>>
>>
>> Paul,
>>
>> I caught this one while searching the usage of "data race" in perfbook.
>> I thought "data race" also deserves an entry in Glossaries, especially
>> because our use of "data race" is heavily related to compiler
>> optimizations and somewhat stricter than the common definition
>> found on the web.
>>
>> The first of data race in Section 4.2.2 (just before QQ4.8) does
>> not (explicitly) talk about optimizations.
>>
>> Would it be possible for you to come up with some concise definition
>> of data race which will fit as an entry in the Glossaries?
>
> How about like the following?
Looks good to me!
Note on the index entry:
My experiment on the way to annotate index entries can manage automatic
capitalization of only the first letter in indexed words/terms.
So you won't need to take care of them.
And I'll get rid of direct uses of \index{} macro.
Will start rebasing those experiment soon after the release of
second edition.
Thanks, Akira
>
> Thanx, Paul
>
> ------------------------------------------------------------------------
>
> commit da6dcf306cf2eb05324c306bbed230cc543fc426
> Author: Paul E. McKenney <paulmck@xxxxxxxxxx>
> Date: Sat Mar 20 12:21:07 2021 -0700
>
> toolsoftrade,glossary: Explain data races
>
> While in the area, make the cases of index entries consistent,
> fixing my copy-pasta from the glossary entry.
>
> Reported-by: Akira Yokosawa <akiyks@xxxxxxxxx>
> Signed-off-by: Paul E. McKenney <paulmck@xxxxxxxxxx>
>
> diff --git a/glossary.tex b/glossary.tex
> index c6c9c62..e6aa612 100644
> --- a/glossary.tex
> +++ b/glossary.tex
> @@ -38,13 +38,13 @@
> is atomic, because other CPUs will see either the old value or
> the new value, but are guaranteed not to see some mixed value
> containing some pieces of the new and old values.
> -\item[Atomic Read-Modify-Write Operation:]\index{Atomic Read-Modify-Write Operation}
> +\item[Atomic Read-Modify-Write Operation:]\index{Atomic read-modify-write operation}
> An atomic operation that both reads and writes memory is
> considered an atomic read-modify-write operation, or atomic RMW
> operation for short.
> Although the value written usually depends on the value read,
> \co{atomic_xchg()} is the exception that proves this rule.
> -\item[Bounded Wait Free:]\index{Bounded Wait Free}
> +\item[Bounded Wait Free:]\index{Bounded wait free}
> A forward-progress guarantee in which every thread makes
> progress within a specific finite period of time, the specific
> time being the bound.
> @@ -126,7 +126,7 @@
> \item[Capacity Miss:]\index{Capacity miss}
> A cache miss incurred because the corresponding CPU has recently
> accessed more data than will fit into the cache.
> -\item[Clash Free:]\index{Clash Free}
> +\item[Clash Free:]\index{Clash free}
> A forward-progress guarantee in which, in the absence of
> contention, at least one thread makes progress within a finite
> period of time.
> @@ -170,7 +170,16 @@
> increasing numbers of CPUs as the number of instances of
> data grows.
> Contrast with ``code locking''.
> -\item[Deadlock Free:]\index{Deadlock Free}
> +\item[Data Race:]\index{Data race}
> + A race condition in which several CPUs or threads access
> + a variable concurrently, and in which at least one of those
> + accesses is a store and at least one of those accesses
> + is unmarked.
> + It is important to note that while the presence of data races
> + often indicates the presence of bugs, the absence of data races
> + in no way implies the absence of bugs.
> + (See ``Marked access''.)
> +\item[Deadlock Free:]\index{Deadlock free}
> A forward-progress guarantee in which, in the absence of
> failures, at least one thread makes progress within a finite
> period of time.
> @@ -226,7 +235,7 @@
> Since RCU read-side critical sections by definition cannot
> contain quiescent states, these two definitions are almost
> always interchangeable.
> -\item[Hazard Pointer:]\index{Hazard Pointer}
> +\item[Hazard Pointer:]\index{Hazard pointer}
> A scalable counterpart to a reference counter in which an
> object's reference count is represented implicitly by a count
> of the number of special hazard pointers referencing that object.
> @@ -284,9 +293,21 @@
> used so heavily that there is often a CPU waiting on it.
> Reducing lock contention is often a concern when designing
> parallel algorithms and when implementing parallel programs.
> -\item[Lock Free:]\index{Lock Free}
> +\item[Lock Free:]\index{Lock free}
> A forward-progress guarantee in which at least one thread makes
> progress within a finite period of time.
> +\item[Marked Access:]\index{Marked access}
> + A source-code memory access that uses a special function or
> + macro, such as \co{READ_ONCE()}, \co{WRITE_ONCE()},
> + \co{atomic_inc()}, and so on, in order to protect that access
> + from compiler and/or hardware optimizations.
> + In contrast, an unmarked access simply mentions the name of
> + the object being accessed, so that in the following, line~2
> + is the unmarked equivalent of line~1:
> + \begin{VerbatimN}
> + WRITE_ONCE(a, READ_ONCE(b) + READ_ONCE(c));
> + a = b + c;
> + \end{VerbatimN}
> \item[Memory:]\index{Memory}
> From the viewpoint of memory models, the main memory,
> caches, and store buffers in which values might be stored.
> @@ -345,7 +366,7 @@
> \item[NUMA Node:]\index{NUMA node}
> A group of closely placed CPUs and associated memory within
> a larger NUMA machines.
> -\item[Obstruction Free:]\index{Obstruction Free}
> +\item[Obstruction Free:]\index{Obstruction free}
> A forward-progress guarantee in which, in the absence of
> contention, every thread makes progress within a finite
> period of time.
> @@ -428,7 +449,7 @@
> wait for the writer to release the lock.
> A key concern for reader-writer locks is ``fairness'':
> can an unending stream of readers starve a writer or vice versa.
> -\item[Real Time:]\index{Real Time}
> +\item[Real Time:]\index{Real time}
> A situation in which getting the correct result is not sufficient,
> but where this result must also be obtained within a given amount
> of time.
> @@ -437,7 +458,7 @@
> additional resources.
> For parallel computing, the additional resources are usually
> additional CPUs.
> -\item[Sequence Lock:]\index{Sequence Lock}
> +\item[Sequence Lock:]\index{Sequence lock}
> A reader-writer synchronization mechanism in which readers
> retry their operations if a writer was present.
> \item[Sequential Consistency:]\index{Sequential consistency}
> @@ -445,7 +466,7 @@
> in an order consistent with
> a single global order, and where each CPU's memory references
> appear to all CPUs to occur in program order.
> -\item[Starvation Free:]\index{Starvation Free}
> +\item[Starvation Free:]\index{Starvation free}
> A forward-progress guarantee in which, in the absence of
> failures, every thread makes progress within a finite
> period of time.
> @@ -483,7 +504,7 @@
> they understand completely and are therefore comfortable teaching.
> \item[Throughput:]\index{Throughput}
> A performance metric featuring work items completed per unit time.
> -\item[Transactional Lock Elision (TLE):]\index{Transactional Lock Elision (TLE)}
> +\item[Transactional Lock Elision (TLE):]\index{Transactional lock elision (TLE)}
> The use of transactional memory to emulate locking.
> Synchronization is instead carried out by conflicting accesses
> to the data to be protected by the lock.
> @@ -503,7 +524,7 @@
> In the 1960s through the 1980s, only supercomputers had vector
> capabilities, but the advent of MMX in x86 CPUs and VMX in
> PowerPC CPUs brought vector processing to the masses.
> -\item[Wait Free:]\index{Wait Free}
> +\item[Wait Free:]\index{Wait free}
> A forward-progress guarantee in which every thread makes
> progress within a finite period of time.
> \item[Write Miss:]\index{Write miss}
> diff --git a/toolsoftrade/toolsoftrade.tex b/toolsoftrade/toolsoftrade.tex
> index 1f667e0..9e0838c 100644
> --- a/toolsoftrade/toolsoftrade.tex
> +++ b/toolsoftrade/toolsoftrade.tex
> @@ -397,12 +397,20 @@ Note that this program carefully makes sure that only one of the threads
> stores a value to variable \co{x} at a time.
> Any situation in which one thread might be storing a value to a given
> variable while some other thread either loads from or stores to that
> -same variable is termed a ``data race''.
> +same variable is termed a \emph{data race}.
> Because the C language makes no guarantee that the results of a data race
> will be in any way reasonable, we need some way of safely accessing
> and modifying data concurrently, such as the locking primitives discussed
> in the following section.
>
> +But your data races are benign, you say?
> +Well, maybe they are.
> +But please do everyone (yourself included) a big favor and read
> +\cref{sec:toolsoftrade:Shared-Variable Shenanigans}
> +very carefully.
> +As compilers optimize more and more aggressively, there are fewer and
> +fewer truly benign data races.
> +
> \QuickQuiz{
> If the C language makes no guarantees in presence of a data
> race, then why does the Linux kernel have so many data races?
>
