tools/memory-model/Documentation: Fix "conflict" definition
PATCH v2 1/1 tools/memory-model/Documentation: Fix "conflict" definition
The definition of "conflict" should not include the type of access nor whether the accesses are concurrent or not, which this patch addresses. The definition of "data race" remains unchanged.
The definition of "conflict" as we know it and is cited by various papers on memory consistency models appeared in [1]: "Two accesses to the same variable conflict if at least one is a write; two operations conflict if they execute conflicting accesses."
The LKMM as well as the C11 memory model are adaptations of data-race-free, which are based on the work in [2]. Necessarily, we need both conflicting data operations (plain) and synchronization operations (marked). For example, C11's definition is based on [3], which defines a "data race" as: "Two memory operations conflict if they access the same memory location, and at least one of them is a store, atomic store, or atomic read-modify-write operation. In a sequentially consistent execution, two memory operations from different threads form a type 1 data race if they conflict, at least one of them is a data operation, and they are adjacent in <T (i.e., they may be executed concurrently)."
[1] D. Shasha, M. Snir, "Efficient and Correct Execution of Parallel Programs that Share Memory", 1988.
URL: http://snir.cs.illinois.edu/listed/J21.pdf
[2] S. Adve, "Designing Memory Consistency Models for Shared-Memory
Multiprocessors", 1993. URL: http://sadve.cs.illinois.edu/Publications/thesis.pdf
[3] H.-J. Boehm, S. Adve, "Foundations of the C++ Concurrency Memory
Model", 2008. URL: https://www.hpl.hp.com/techreports/2008/HPL-2008-56.pdf
---
v2:
* Apply Alan's suggested version.
- Move "from different CPUs (or threads)" from "conflict" to "data race" definition. Update "race candidate" accordingly.
* Add citations to commit message.
v1: http://lkml.kernel.org/r/[email protected]
--- .../Documentation/explanation.txt | 77 +++++++++---------- 1 file changed, 38 insertions(+), 39 deletions(-)
tools/memory-model/Documentation/explanation.txt +38 -39
@@ -1987,28 +1987,28 @@ outcome undefined. In technical terms, the compiler is allowed to assume that when the program executes, there will not be any data races. A "data race" -occurs when two conflicting memory accesses execute concurrently; -two memory accesses "conflict" if: +occurs when two conflicting memory accesses from different CPUs (or +different threads on the same CPU) execute concurrently, and at least +one of them is plain. Two memory accesses "conflict" if: they access the same location, - they occur on different CPUs (or in different threads on the - same CPU), - - at least one of them is a plain access, - and at least one of them is a store. -The LKMM tries to determine whether a program contains two conflicting -accesses which may execute concurrently; if it does then the LKMM says -there is a potential data race and makes no predictions about the -program's outcome. - -Determining whether two accesses conflict is easy; you can see that -all the concepts involved in the definition above are already part of -the memory model. The hard part is telling whether they may execute -concurrently. The LKMM takes a conservative attitude, assuming that -accesses may be concurrent unless it can prove they cannot. +We'll say that two accesses from different threads are "race +candidates" if they conflict and at least one of them is plain. +Whether or not two candidates actually do race in a given execution +then depends on whether they are concurrent. The LKMM tries to +determine whether a program contains race candidates which may execute +concurrently; if it does then the LKMM says there is a potential data +race and makes no predictions about the program's outcome. + +Determining whether two accesses are race candidates is easy; you can +see that all the concepts involved in the definition above are already +part of the memory model. The hard part is telling whether they may +execute concurrently. The LKMM takes a conservative attitude, +assuming that accesses may be concurrent unless it can prove they +are not. If two memory accesses aren't concurrent then one must execute before the other. Therefore the LKMM decides two accesses aren't concurrent
@@ -2171,8 +2171,8 @@ again, now using plain accesses for buf: } This program does not contain a data race. Although the U and V -accesses conflict, the LKMM can prove they are not concurrent as -follows: +accesses are race candidates, the LKMM can prove they are not +concurrent as follows: The smp_wmb() fence in P0 is both a compiler barrier and a cumul-fence. It guarantees that no matter what hash of
@@ -2326,12 +2326,11 @@ could now perform the load of x before the load of ptr (there might be a control dependency but no address dependency at the machine level). Finally, it turns out there is a situation in which a plain write does -not need to be w-post-bounded: when it is separated from the -conflicting access by a fence. At first glance this may seem -impossible. After all, to be conflicting the second access has to be -on a different CPU from the first, and fences don't link events on -different CPUs. Well, normal fences don't -- but rcu-fence can! -Here's an example: +not need to be w-post-bounded: when it is separated from the other +race-candidate access by a fence. At first glance this may seem +impossible. After all, to be race candidates the two accesses must +be on different CPUs, and fences don't link events on different CPUs. +Well, normal fences don't -- but rcu-fence can! Here's an example: int x, y;
@@ -2367,7 +2366,7 @@ concurrent and there is no race, even though P1's plain store to y isn't w-post-bounded by any marked accesses. Putting all this material together yields the following picture. For -two conflicting stores W and W', where W ->co W', the LKMM says the +race-candidate stores W and W', where W ->co W', the LKMM says the stores don't race if W can be linked to W' by a w-post-bounded ; vis ; w-pre-bounded
@@ -2380,8 +2379,8 @@ sequence, and if W' is plain then they also have to be linked by a w-post-bounded ; vis ; r-pre-bounded -sequence. For a conflicting load R and store W, the LKMM says the two -accesses don't race if R can be linked to W by an +sequence. For race-candidate load R and store W, the LKMM says the +two accesses don't race if R can be linked to W by an r-post-bounded ; xb* ; w-pre-bounded
@@ -2413,20 +2412,20 @@ is, the rules governing the memory subsystem's choice of a store to satisfy a load request and its determination of where a store will fall in the coherence order): - If R and W conflict and it is possible to link R to W by one - of the xb* sequences listed above, then W ->rfe R is not - allowed (i.e., a load cannot read from a store that it + If R and W are race candidates and it is possible to link R to + W by one of the xb* sequences listed above, then W ->rfe R is + not allowed (i.e., a load cannot read from a store that it executes before, even if one or both is plain). - If W and R conflict and it is possible to link W to R by one - of the vis sequences listed above, then R ->fre W is not - allowed (i.e., if a store is visible to a load then the load - must read from that store or one coherence-after it). + If W and R are race candidates and it is possible to link W to + R by one of the vis sequences listed above, then R ->fre W is + not allowed (i.e., if a store is visible to a load then the + load must read from that store or one coherence-after it). - If W and W' conflict and it is possible to link W to W' by one - of the vis sequences listed above, then W' ->co W is not - allowed (i.e., if one store is visible to a second then the - second must come after the first in the coherence order). + If W and W' are race candidates and it is possible to link W + to W' by one of the vis sequences listed above, then W' ->co W + is not allowed (i.e., if one store is visible to a second then + the second must come after the first in the coherence order). This is the extent to which the LKMM deals with plain accesses. Perhaps it could say more (for example, plain accesses might
Signature · 1 line
2.25.0.265.gbab2e86ba0-goog
Alan Stern
maintainerQuoted 2 lines · Marco Elver
Alan: I think this needs your Signed-off-by, since I added you as Co-developed-by.
Here you go:
Quoted 1 line
Let me know if this works for you.
See below.
Quoted 76 lines
The definition of "conflict" should not include the type of access nor whether the accesses are concurrent or not, which this patch addresses. The definition of "data race" remains unchanged.
The definition of "conflict" as we know it and is cited by various papers on memory consistency models appeared in [1]: "Two accesses to the same variable conflict if at least one is a write; two operations conflict if they execute conflicting accesses."
The LKMM as well as the C11 memory model are adaptations of data-race-free, which are based on the work in [2]. Necessarily, we need both conflicting data operations (plain) and synchronization operations (marked). For example, C11's definition is based on [3], which defines a "data race" as: "Two memory operations conflict if they access the same memory location, and at least one of them is a store, atomic store, or atomic read-modify-write operation. In a sequentially consistent execution, two memory operations from different threads form a type 1 data race if they conflict, at least one of them is a data operation, and they are adjacent in <T (i.e., they may be executed concurrently)."
[1] D. Shasha, M. Snir, "Efficient and Correct Execution of Parallel Programs that Share Memory", 1988.
URL: http://snir.cs.illinois.edu/listed/J21.pdf[2] S. Adve, "Designing Memory Consistency Models for Shared-Memory
Multiprocessors", 1993. URL: http://sadve.cs.illinois.edu/Publications/thesis.pdf[3] H.-J. Boehm, S. Adve, "Foundations of the C++ Concurrency Memory
Model", 2008. URL: https://www.hpl.hp.com/techreports/2008/HPL-2008-56.pdfSigned-off-by Marco Elver <[email protected]>Co-developed-by Alan Stern <[email protected]>---
v2:
* Apply Alan's suggested version.
- Move "from different CPUs (or threads)" from "conflict" to "data race" definition. Update "race candidate" accordingly.
* Add citations to commit message.v1: http://lkml.kernel.org/r/[email protected]
--- .../Documentation/explanation.txt | 77 +++++++++---------- 1 file changed, 38 insertions(+), 39 deletions(-)tools/memory-model/Documentation/explanation.txt +3
-14@@ -1987,28 +1987,28 @@ outcome undefined. In technical terms, the compiler is allowed to assume that when the program executes, there will not be any data races. A "data race" -occurs when two conflicting memory accesses execute concurrently; -two memory accesses "conflict" if: +occurs when two conflicting memory accesses from different CPUs (or +different threads on the same CPU) execute concurrently, and at least +one of them is plain. Two memory accesses "conflict" if: they access the same location, - they occur on different CPUs (or in different threads on the - same CPU), - - at least one of them is a plain access, - and at least one of them is a store. -The LKMM tries to determine whether a program contains two conflicting -accesses which may execute concurrently; if it does then the LKMM says -there is a potential data race and makes no predictions about the -program's outcome. - -Determining whether two accesses conflict is easy; you can see that -all the concepts involved in the definition above are already part of
tools/memory-model/Documentation/explanation.txt outcome undefined. · line 2004
Quoted 10 lines
tools/memory-model/Documentation/explanation.txt +7
-3-the memory model. The hard part is telling whether they may execute -concurrently. The LKMM takes a conservative attitude, assuming that -accesses may be concurrent unless it can prove they cannot. +We'll say that two accesses from different threads are "race +candidates" if they conflict and at least one of them is plain. +Whether or not two candidates actually do race in a given execution +then depends on whether they are concurrent. The LKMM tries to +determine whether a program contains race candidates which may execute +concurrently; if it does then the LKMM says there is a potential data +race and makes no predictions about the program's outcome.
Hmmm. Although the content is okay, I don't like the organization very much. What do you think of this for the above portion of the patch)?
Alan Stern
tools/memory-model/Documentation/explanation.txt +23 -15
@@ -1987,28 +1987,36 @@ outcome undefined. In technical terms, the compiler is allowed to assume that when the program executes, there will not be any data races. A "data race" -occurs when two conflicting memory accesses execute concurrently; -two memory accesses "conflict" if: +occurs when there are two memory accesses such that: - they access the same location, +1. they access the same location, - they occur on different CPUs (or in different threads on the - same CPU), +2. at least one of them is a store, + +3. at least one of them is plain, - at least one of them is a plain access, +4. they occur on different CPUs (or in different threads on the + same CPU), and - and at least one of them is a store. +5. they execute concurrently. -The LKMM tries to determine whether a program contains two conflicting -accesses which may execute concurrently; if it does then the LKMM says -there is a potential data race and makes no predictions about the +In the literature, two accesses are said to "conflict" if they satisfy +1 and 2 above. We'll go a little farther and say that two accesses +are "race candidates" if they satisfy 1 - 4. Thus, whether or not two +race candidates actually do race in a given execution depends on +whether they are concurrent. + +The LKMM tries to determine whether a program contains two race +candidates which may execute concurrently; if it does then the LKMM +says there is a potential data race and makes no predictions about the program's outcome. -Determining whether two accesses conflict is easy; you can see that -all the concepts involved in the definition above are already part of -the memory model. The hard part is telling whether they may execute -concurrently. The LKMM takes a conservative attitude, assuming that -accesses may be concurrent unless it can prove they cannot. +Determining whether two accesses are race candidates is easy; you can +see that all the concepts involved in the definition above are already +part of the memory model. The hard part is telling whether they may +execute concurrently. The LKMM takes a conservative attitude, +assuming that accesses may be concurrent unless it can prove they +are not. If two memory accesses aren't concurrent then one must execute before the other. Therefore the LKMM decides two accesses aren't concurrent
Quoted 95 lines · Alan Stern
Quoted 2 lines · Marco Elver
Alan: I think this needs your Signed-off-by, since I added you as Co-developed-by.
Here you go:
Signed-off-by Alan Stern <[email protected]>Quoted 1 line
Let me know if this works for you.
See below.
Quoted 81 lines
The definition of "conflict" should not include the type of access nor whether the accesses are concurrent or not, which this patch addresses. The definition of "data race" remains unchanged.
The definition of "conflict" as we know it and is cited by various papers on memory consistency models appeared in [1]: "Two accesses to the same variable conflict if at least one is a write; two operations conflict if they execute conflicting accesses."
The LKMM as well as the C11 memory model are adaptations of data-race-free, which are based on the work in [2]. Necessarily, we need both conflicting data operations (plain) and synchronization operations (marked). For example, C11's definition is based on [3], which defines a "data race" as: "Two memory operations conflict if they access the same memory location, and at least one of them is a store, atomic store, or atomic read-modify-write operation. In a sequentially consistent execution, two memory operations from different threads form a type 1 data race if they conflict, at least one of them is a data operation, and they are adjacent in <T (i.e., they may be executed concurrently)."
[1] D. Shasha, M. Snir, "Efficient and Correct Execution of Parallel Programs that Share Memory", 1988.
URL: http://snir.cs.illinois.edu/listed/J21.pdf[2] S. Adve, "Designing Memory Consistency Models for Shared-Memory
Multiprocessors", 1993. URL: http://sadve.cs.illinois.edu/Publications/thesis.pdf[3] H.-J. Boehm, S. Adve, "Foundations of the C++ Concurrency Memory
Model", 2008. URL: https://www.hpl.hp.com/techreports/2008/HPL-2008-56.pdfSigned-off-by Marco Elver <[email protected]>Co-developed-by Alan Stern <[email protected]>---
v2:
* Apply Alan's suggested version.
- Move "from different CPUs (or threads)" from "conflict" to "data race" definition. Update "race candidate" accordingly.
* Add citations to commit message.v1: http://lkml.kernel.org/r/[email protected]
--- .../Documentation/explanation.txt | 77 +++++++++---------- 1 file changed, 38 insertions(+), 39 deletions(-)tools/memory-model/Documentation/explanation.txt +5
-17@@ -1987,28 +1987,28 @@ outcome undefined. In technical terms, the compiler is allowed to assume that when the program executes, there will not be any data races. A "data race" -occurs when two conflicting memory accesses execute concurrently; -two memory accesses "conflict" if: +occurs when two conflicting memory accesses from different CPUs (or +different threads on the same CPU) execute concurrently, and at least +one of them is plain. Two memory accesses "conflict" if: they access the same location, - they occur on different CPUs (or in different threads on the - same CPU), - - at least one of them is a plain access, - and at least one of them is a store. -The LKMM tries to determine whether a program contains two conflicting -accesses which may execute concurrently; if it does then the LKMM says -there is a potential data race and makes no predictions about the -program's outcome. - -Determining whether two accesses conflict is easy; you can see that -all the concepts involved in the definition above are already part of -the memory model. The hard part is telling whether they may execute -concurrently. The LKMM takes a conservative attitude, assuming that -accesses may be concurrent unless it can prove they cannot. +We'll say that two accesses from different threads are "race +candidates" if they conflict and at least one of them is plain.
Quoted 8 lines
tools/memory-model/Documentation/explanation.txt outcome undefined. · line 2004
Quoted 5 lines
tools/memory-model/Documentation/explanation.txt +5
-0+Whether or not two candidates actually do race in a given execution +then depends on whether they are concurrent. The LKMM tries to +determine whether a program contains race candidates which may execute +concurrently; if it does then the LKMM says there is a potential data +race and makes no predictions about the program's outcome.Hmmm. Although the content is okay, I don't like the organization very much. What do you think of this for the above portion of the patch)?
Thanks, looks good to me. Applied in v3:
http://lkml.kernel.org/r/[email protected]
-- Marco
Quoted 62 lines
Alan Stern
Index:
usb-devel/tools/memory-model/Documentation/explanation.txt
===================================================================tools/memory-model/Documentation/explanation.txt +23
-15@@ -1987,28 +1987,36 @@ outcome undefined. In technical terms, the compiler is allowed to assume that when the program executes, there will not be any data races. A "data race" -occurs when two conflicting memory accesses execute concurrently; -two memory accesses "conflict" if: +occurs when there are two memory accesses such that: - they access the same location, +1. they access the same location, - they occur on different CPUs (or in different threads on the - same CPU), +2. at least one of them is a store, + +3. at least one of them is plain, - at least one of them is a plain access, +4. they occur on different CPUs (or in different threads on the + same CPU), and - and at least one of them is a store. +5. they execute concurrently. -The LKMM tries to determine whether a program contains two conflicting -accesses which may execute concurrently; if it does then the LKMM says -there is a potential data race and makes no predictions about the +In the literature, two accesses are said to "conflict" if they satisfy +1 and 2 above. We'll go a little farther and say that two accesses +are "race candidates" if they satisfy 1 - 4. Thus, whether or not two +race candidates actually do race in a given execution depends on +whether they are concurrent. + +The LKMM tries to determine whether a program contains two race +candidates which may execute concurrently; if it does then the LKMM +says there is a potential data race and makes no predictions about the program's outcome. -Determining whether two accesses conflict is easy; you can see that -all the concepts involved in the definition above are already part of -the memory model. The hard part is telling whether they may execute -concurrently. The LKMM takes a conservative attitude, assuming that -accesses may be concurrent unless it can prove they cannot. +Determining whether two accesses are race candidates is easy; you can +see that all the concepts involved in the definition above are already +part of the memory model. The hard part is telling whether they may +execute concurrently. The LKMM takes a conservative attitude, +assuming that accesses may be concurrent unless it can prove they +are not. If two memory accesses aren't concurrent then one must execute before the other. Therefore the LKMM decides two accesses aren't concurrent
From: Marco Elver
Quoted 10 lines
Sent: 02 March 2020 14:18
The definition of "conflict" should not include the type of access nor whether the accesses are concurrent or not, which this patch addresses. The definition of "data race" remains unchanged.
The definition of "conflict" as we know it and is cited by various papers on memory consistency models appeared in [1]: "Two accesses to the same variable conflict if at least one is a write; two operations conflict if they execute conflicting accesses."
I'm pretty sure that Linux requires that the underlying memory subsystem remove any possible 'conflicts' by serialising the requests (in an arbitrary order).
So 'conflicts' are never relevant.
There are memory subsystems where conflicts MUST be avoided. For instance the fpga I use have some dual-ported memory. Concurrent accesses on the two ports for the same address must (usually) be avoided if one is a write.
Two writes will generate corrupt memory.
A concurrent write+read will generate a garbage read. In the special case where the two ports use the same clock it is possible to force the read to be 'old data' but that constrains the timings.
On such systems the code must avoid conflicting cycles.
David
-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)
Paul E. McKenney
maintainerQuoted 28 lines · David Laight
From: Marco Elver
Quoted 10 lines
Sent: 02 March 2020 14:18
The definition of "conflict" should not include the type of access nor whether the accesses are concurrent or not, which this patch addresses. The definition of "data race" remains unchanged.
The definition of "conflict" as we know it and is cited by various papers on memory consistency models appeared in [1]: "Two accesses to the same variable conflict if at least one is a write; two operations conflict if they execute conflicting accesses."
I'm pretty sure that Linux requires that the underlying memory subsystem remove any possible 'conflicts' by serialising the requests (in an arbitrary order).
So 'conflicts' are never relevant.
There are memory subsystems where conflicts MUST be avoided. For instance the fpga I use have some dual-ported memory. Concurrent accesses on the two ports for the same address must (usually) be avoided if one is a write.
Two writes will generate corrupt memory.
A concurrent write+read will generate a garbage read. In the special case where the two ports use the same clock it is possible to force the read to be 'old data' but that constrains the timings.
Quoted 1 line
On such systems the code must avoid conflicting cycles.
That would be yet another definition of "conflicts". Quite relevant on some older hardware I have worked with. But what we are concerned with here are cases where (as you say) the memory subsystem will do just fine, but where the fact that the memory subsystem is called upon to do the necessary serialization constitutes a bug of some sort.
There are unfortunately a wide variety of definitions and opinions as to exactly what sorts of conflicts constitute bugs. The generic pattern for these definitions and opinions is "a concurrent set of insufficiently marked accesses to a given location, at least one of which is a write".
The differences in definitions and opinions center around exactly what is meant by the word "insufficiently" in this last sentence. We will probably be tolerating some variety of definitions in the kernel, and given the wide variety of code contained therein, this should be just fine.
Thanx, Paul
Quoted 13 lines · David Laight
From: Marco Elver
Quoted 10 lines
Sent: 02 March 2020 14:18
The definition of "conflict" should not include the type of access nor whether the accesses are concurrent or not, which this patch addresses. The definition of "data race" remains unchanged.
The definition of "conflict" as we know it and is cited by various papers on memory consistency models appeared in [1]: "Two accesses to the same variable conflict if at least one is a write; two operations conflict if they execute conflicting accesses."
Quoted 5 lines
I'm pretty sure that Linux requires that the underlying memory subsystem remove any possible 'conflicts' by serialising the requests (in an arbitrary order).
So 'conflicts' are never relevant.
A "conflict" is nothing bad per-se. A conflict is simply "two accesses to the same location, at least one is a write". Conflicting accesses may not even be concurrent.
Quoted 11 lines
There are memory subsystems where conflicts MUST be avoided. For instance the fpga I use have some dual-ported memory. Concurrent accesses on the two ports for the same address must (usually) be avoided if one is a write.
Two writes will generate corrupt memory.
A concurrent write+read will generate a garbage read. In the special case where the two ports use the same clock it is possible to force the read to be 'old data' but that constrains the timings.On such systems the code must avoid conflicting cycles.
What I gather is that on this system you need to avoid "concurrent conflicting" accesses. Note that, "conflict" does not imply "concurrent" and vice-versa.
Thanks,
-- Marco