lkml.org 
[lkml]   [2020]   [Mar]   [2]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH v3] tools/memory-model/Documentation: Fix "conflict" definition
On Mon, Mar 02, 2020 at 06:21:01PM +0100, Marco Elver wrote:
> 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
>
> Signed-off-by: Marco Elver <elver@google.com>
> Co-developed-by: Alan Stern <stern@rowland.harvard.edu>
> Signed-off-by: Alan Stern <stern@rowland.harvard.edu>

LGTM:

Acked-by: Andrea Parri <parri.andrea@gmail.com>

Thank you both,

Andrea


> ---
> v3:
> * Apply Alan's suggestion.
> * s/two race candidates/race candidates/
>
> v2: http://lkml.kernel.org/r/20200302141819.40270-1-elver@google.com
> * 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/20200228164621.87523-1-elver@google.com
> ---
> .../Documentation/explanation.txt | 83 ++++++++++---------
> 1 file changed, 45 insertions(+), 38 deletions(-)
>
> diff --git a/tools/memory-model/Documentation/explanation.txt b/tools/memory-model/Documentation/explanation.txt
> index e91a2eb19592a..993f800659c6a 100644
> --- a/tools/memory-model/Documentation/explanation.txt
> +++ b/tools/memory-model/Documentation/explanation.txt
> @@ -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,
>
> - at least one of them is a plain access,
> +3. at least one of them is plain,
>
> - and at least one of them is a store.
> +4. they occur on different CPUs (or in different threads on the
> + same CPU), and
>
> -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.
> +5. they execute concurrently.
>
> -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.
> +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 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 +2179,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 +2334,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 +2374,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 +2387,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 +2420,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
> --
> 2.25.0.265.gbab2e86ba0-goog
>

\
 
 \ /
  Last update: 2020-03-02 19:52    [W:0.125 / U:0.380 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site