linux/tools/memory-model, branch v5.4

tools/memory-model: Update the informal documentation

2019-08-09T17:28:57Z

The formal memory consistency model has added support for plain accesses (and data races). While updating the informal documentation to describe this addition to the model is highly desirable and important future work, update the informal documentation to at least acknowledge such addition. Signed-off-by: Andrea Parri Cc: Will Deacon Cc: Peter Zijlstra Cc: Boqun Feng Cc: Nicholas Piggin Cc: David Howells Cc: Jade Alglave Cc: Luc Maranget Cc: "Paul E. McKenney" Cc: Akira Yokosawa Cc: Daniel Lustig Signed-off-by: Paul E. McKenney Acked-by: Alan Stern

tools/memory-model: Use cumul-fence instead of fence in ->prop example

2019-08-09T17:28:57Z

To reduce ambiguity in the more exotic ->prop ordering example, this commit uses the term cumul-fence instead of the term fence for the two fences, so that the implict ->rfe on loads/stores to Y are covered by the description. Link: https://lore.kernel.org/lkml/20190729121745.GA140682@google.com Suggested-by: Alan Stern Signed-off-by: Joel Fernandes (Google) Acked-by: Alan Stern Signed-off-by: Paul E. McKenney

tools/memory-model: Make scripts be executable

2019-08-01T15:40:07Z

This commit simplifies life a bit by making all of the scripts in tools/memory-model/scripts be executable. Signed-off-by: Paul E. McKenney

tools/memory-model: Improve data-race detection

2019-06-24T16:08:54Z

Herbert Xu recently reported a problem concerning RCU and compiler barriers. In the course of discussing the problem, he put forth a litmus test which illustrated a serious defect in the Linux Kernel Memory Model's data-race-detection code [1]. The defect was that the LKMM assumed visibility and executes-before ordering of plain accesses had to be mediated by marked accesses. In Herbert's litmus test this wasn't so, and the LKMM claimed the litmus test was allowed and contained a data race although neither is true. In fact, plain accesses can be ordered by fences even in the absence of marked accesses. In most cases this doesn't matter, because most fences only order accesses within a single thread. But the rcu-fence relation is different; it can order (and induce visibility between) accesses in different threads -- events which otherwise might be concurrent. This makes it relevant to data-race detection. This patch makes two changes to the memory model to incorporate the new insight: If a store is separated by a fence from another access, the store is necessarily visible to the other access (as reflected in the ww-vis and wr-vis relations). Similarly, if a load is separated by a fence from another access then the load necessarily executes before the other access (as reflected in the rw-xbstar relation). If a store is separated by a strong fence from a marked access then it is necessarily visible to any access that executes after the marked access (as reflected in the ww-vis and wr-vis relations). With these changes, the LKMM gives the desired result for Herbert's litmus test and other related ones [2]. [1] https://lore.kernel.org/lkml/Pine.LNX.4.44L0.1906041026570.1731-100000@iolanthe.rowland.org/ [2] https://github.com/paulmckrcu/litmus/blob/master/manual/plain/C-S-rcunoderef-1.litmus https://github.com/paulmckrcu/litmus/blob/master/manual/plain/C-S-rcunoderef-2.litmus https://github.com/paulmckrcu/litmus/blob/master/manual/plain/C-S-rcunoderef-3.litmus https://github.com/paulmckrcu/litmus/blob/master/manual/plain/C-S-rcunoderef-4.litmus https://github.com/paulmckrcu/litmus/blob/master/manual/plain/strong-vis.litmus Reported-by: Herbert Xu Signed-off-by: Alan Stern Acked-by: Andrea Parri Signed-off-by: Paul E. McKenney Tested-by: Akira Yokosawa

tools/memory-model: Change definition of rcu-fence

2019-06-21T23:20:49Z

The rcu-fence relation in the Linux Kernel Memory Model is not well named. It doesn't act like any other fence relation, in that it does not relate events before a fence to events after that fence. All it does is relate certain RCU events to one another (those that are ordered by the RCU Guarantee); this induces an actual strong-fence-like relation linking events preceding the first RCU event to those following the second. This patch renames rcu-fence, now called rcu-order. It adds a new definition of rcu-fence, something which should have been present all along because it is used in the rb relation. And it modifies the fence and strong-fence relations by making them incorporate the new rcu-fence. As a result of this change, there is no longer any need to define full-fence in the section for detecting data races. It can simply be replaced by the updated strong-fence relation. This change should have no effect on the operation of the memory model. Signed-off-by: Alan Stern Acked-by: Andrea Parri Signed-off-by: Paul E. McKenney

tools/memory-model: Expand definition of barrier

2019-06-21T23:18:45Z

Commit 66be4e66a7f4 ("rcu: locking and unlocking need to always be at least barriers") added compiler barriers back into rcu_read_lock() and rcu_read_unlock(). Furthermore, srcu_read_lock() and srcu_read_unlock() have always contained compiler barriers. The Linux Kernel Memory Model ought to know about these barriers. This patch adds them into the memory model. Signed-off-by: Alan Stern Acked-by: Andrea Parri Signed-off-by: Paul E. McKenney

tools/memory-model: Do not use "herd" to refer to "herd7"

2019-06-19T16:32:10Z

Use "herd7" in each such reference. Signed-off-by: Andrea Parri Cc: Will Deacon Cc: Peter Zijlstra Cc: Boqun Feng Cc: Nicholas Piggin Cc: David Howells Cc: Jade Alglave Cc: Luc Maranget Cc: "Paul E. McKenney" Cc: Akira Yokosawa Cc: Daniel Lustig Acked-by: Alan Stern Signed-off-by: Paul E. McKenney

tools/memory-model: Fix comment in MP+poonceonces.litmus

2019-06-19T16:31:54Z

The comment should say "Sometimes" for the result. Signed-off-by: Andrea Parri Cc: Will Deacon Cc: Peter Zijlstra Cc: Boqun Feng Cc: Nicholas Piggin Cc: David Howells Cc: Jade Alglave Cc: Luc Maranget Cc: "Paul E. McKenney" Cc: Akira Yokosawa Cc: Daniel Lustig Acked-by: Alan Stern Signed-off-by: Paul E. McKenney

tools/memory-model: Add data-race detection

2019-05-28T15:18:21Z

This patch adds data-race detection to the Linux-Kernel Memory Model. As part of this effort, support is added for: compiler barriers (the barrier() function), and a new Preserved Program Order term: (addr ; [Plain] ; wmb) Data races are marked with a special Flag warning in herd. It is not guaranteed that the model will provide accurate predictions when a data race is present. The patch does not include documentation for the data-race detection facility. The basic design has been explained in various emails, and a separate documentation patch will be submitted later. This work is based on an earlier formulation of data races for the LKMM by Andrea Parri. Signed-off-by: Alan Stern Reviewed-by: Andrea Parri Signed-off-by: Paul E. McKenney

tools/memory-model: Add definitions of plain and marked accesses

2019-05-28T15:18:21Z

This patch adds definitions for marked and plain accesses to the Linux-Kernel Memory Model. It also modifies the definitions of the existing parts of the model (including the cumul-fence, prop, hb, pb, and rb relations) so as to make them apply only to marked accesses. Signed-off-by: Alan Stern Reviewed-by: Andrea Parri Signed-off-by: Paul E. McKenney