summaryrefslogtreecommitdiff
path: root/tools/memory-model
AgeCommit message (Collapse)AuthorFilesLines
2018-03-10tools/memory-model: Finish the removal of rb-dep, ↵Alan Stern3-6/+6
smp_read_barrier_depends(), and lockless_dereference() Commit: bf28ae562744 ("tools/memory-model: Remove rb-dep, smp_read_barrier_depends, and lockless_dereference") was merged too early, while it was still in RFC form. This patch adds in the missing pieces. Akira pointed out some typos in the original patch, and he noted that cheatsheet.txt should indicate that READ_ONCE() now implies an address dependency. Andrea suggested documenting the relationship betwwen unsuccessful RMW operations and address dependencies. Andrea pointed out that the macro for rcu_dereference() in linux.def should now use the "once" annotation instead of "deref". He also suggested that the comments should mention commit: 5a8897cc7631 ("locking/atomics/alpha: Add smp_read_barrier_depends() to _release()/_relaxed() atomics") ... as an important precursor, and he contributed commit: cb13b424e986 ("locking/xchg/alpha: Add unconditional memory barrier to cmpxchg()") which is another prerequisite. Suggested-by: Akira Yokosawa <akiyks@gmail.com> Suggested-by: Andrea Parri <parri.andrea@gmail.com> Signed-off-by: Alan Stern <stern@rowland.harvard.edu> [ Fixed read_read_lock() typo reported by Akira. ] Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> Acked-by: Andrea Parri <parri.andrea@gmail.com> Acked-by: Akira Yokosawa <akiyks@gmail.com> Cc: Linus Torvalds <torvalds@linux-foundation.org> Cc: Peter Zijlstra <peterz@infradead.org> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: boqun.feng@gmail.com Cc: dhowells@redhat.com Cc: j.alglave@ucl.ac.uk Cc: linux-arch@vger.kernel.org Cc: luc.maranget@inria.fr Cc: npiggin@gmail.com Cc: will.deacon@arm.com Fixes: bf28ae562744 ("tools/memory-model: Remove rb-dep, smp_read_barrier_depends, and lockless_dereference") Link: http://lkml.kernel.org/r/1520443660-16858-4-git-send-email-paulmck@linux.vnet.ibm.com Signed-off-by: Ingo Molnar <mingo@kernel.org>
2018-03-10tools/memory-model: Add documentation of new litmus testPaul E. McKenney1-0/+6
The litmus-tests/README file lacks any mention of the new litmus test ISA2+pooncelock+pooncelock+pombonce.litmus. This commit therefore adds a description of this test. Reported-by: Alan Stern <stern@rowland.harvard.edu> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> Cc: Linus Torvalds <torvalds@linux-foundation.org> Cc: Peter Zijlstra <peterz@infradead.org> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: akiyks@gmail.com Cc: boqun.feng@gmail.com Cc: dhowells@redhat.com Cc: j.alglave@ucl.ac.uk Cc: linux-arch@vger.kernel.org Cc: luc.maranget@inria.fr Cc: npiggin@gmail.com Cc: parri.andrea@gmail.com Cc: will.deacon@arm.com Link: http://lkml.kernel.org/r/1520443660-16858-3-git-send-email-paulmck@linux.vnet.ibm.com Signed-off-by: Ingo Molnar <mingo@kernel.org>
2018-03-10tools/memory-model: Remove mention of docker/gentoo imagePaul E. McKenney1-15/+0
Because the docker and gentoo images haven't been updated in quite some time, they are likely to provide more confusion than help. This commit therefore removes mention of them from the README file. Reported-by: Alan Stern <stern@rowland.harvard.edu> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> Cc: Linus Torvalds <torvalds@linux-foundation.org> Cc: Peter Zijlstra <peterz@infradead.org> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: akiyks@gmail.com Cc: boqun.feng@gmail.com Cc: dhowells@redhat.com Cc: j.alglave@ucl.ac.uk Cc: linux-arch@vger.kernel.org Cc: luc.maranget@inria.fr Cc: npiggin@gmail.com Cc: parri.andrea@gmail.com Cc: will.deacon@arm.com Link: http://lkml.kernel.org/r/1520443660-16858-2-git-send-email-paulmck@linux.vnet.ibm.com Signed-off-by: Ingo Molnar <mingo@kernel.org>
2018-02-21tools/memory-model: Remove rb-dep, smp_read_barrier_depends, and ↵Alan Stern5-48/+46
lockless_dereference Since commit 76ebbe78f739 ("locking/barriers: Add implicit smp_read_barrier_depends() to READ_ONCE()") was merged for the 4.15 kernel, it has not been necessary to use smp_read_barrier_depends(). Similarly, commit 59ecbbe7b31c ("locking/barriers: Kill lockless_dereference()") removed lockless_dereference() from the kernel. Since these primitives are no longer part of the kernel, they do not belong in the Linux Kernel Memory Consistency Model. This patch removes them, along with the internal rb-dep relation, and updates the revelant documentation. Signed-off-by: Alan Stern <stern@rowland.harvard.edu> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> Acked-by: Peter Zijlstra <peterz@infradead.org> Cc: Linus Torvalds <torvalds@linux-foundation.org> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: akiyks@gmail.com Cc: boqun.feng@gmail.com Cc: dhowells@redhat.com Cc: j.alglave@ucl.ac.uk Cc: linux-arch@vger.kernel.org Cc: luc.maranget@inria.fr Cc: nborisov@suse.com Cc: npiggin@gmail.com Cc: parri.andrea@gmail.com Cc: will.deacon@arm.com Link: http://lkml.kernel.org/r/1519169112-20593-12-git-send-email-paulmck@linux.vnet.ibm.com Signed-off-by: Ingo Molnar <mingo@kernel.org>
2018-02-21tools/memory-model: Convert underscores to hyphensPaul E. McKenney3-9/+9
Typical cat-language code uses hyphens for word separators in identifiers, but several LKMM identifiers use underscores instead. This commit therefore converts underscores to hyphens in the .bell- and .cat-file identifiers corresponding to smp_mb__before_atomic(), smp_mb__after_atomic(), and smp_mb__after_spinlock(). Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> Acked-by: Peter Zijlstra <peterz@infradead.org> Cc: Linus Torvalds <torvalds@linux-foundation.org> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: akiyks@gmail.com Cc: boqun.feng@gmail.com Cc: dhowells@redhat.com Cc: j.alglave@ucl.ac.uk Cc: linux-arch@vger.kernel.org Cc: luc.maranget@inria.fr Cc: nborisov@suse.com Cc: npiggin@gmail.com Cc: parri.andrea@gmail.com Cc: stern@rowland.harvard.edu Cc: will.deacon@arm.com Link: http://lkml.kernel.org/r/1519169112-20593-11-git-send-email-paulmck@linux.vnet.ibm.com Signed-off-by: Ingo Molnar <mingo@kernel.org>
2018-02-21tools/memory-model: Add a S lock-based external-view litmus testAlan Stern1-0/+41
This commit adds a litmus test in which P0() and P1() form a lock-based S litmus test, with the addition of P2(), which observes P0()'s and P1()'s accesses with a full memory barrier but without the lock. This litmus test asks whether writes carried out by two different processes under the same lock will be seen in order by a third process not holding that lock. The answer to this question is "yes" for all architectures supporting the Linux kernel, but is "no" according to the current version of LKMM. A patch to LKMM is under development. Signed-off-by: Alan Stern <stern@rowland.harvard.edu> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> Acked-by: Peter Zijlstra <peterz@infradead.org> Cc: Linus Torvalds <torvalds@linux-foundation.org> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: akiyks@gmail.com Cc: boqun.feng@gmail.com Cc: dhowells@redhat.com Cc: j.alglave@ucl.ac.uk Cc: linux-arch@vger.kernel.org Cc: luc.maranget@inria.fr Cc: nborisov@suse.com Cc: npiggin@gmail.com Cc: parri.andrea@gmail.com Cc: will.deacon@arm.com Link: http://lkml.kernel.org/r/1519169112-20593-10-git-send-email-paulmck@linux.vnet.ibm.com Signed-off-by: Ingo Molnar <mingo@kernel.org>
2018-02-21tools/memory-model: Add required herd7 version to README filePaul E. McKenney1-1/+2
LKMM and the herd7 tool are co-evolving, and out-of-date herd7 tools produce inaccurate results, often with no obvious error messages. This commit therefore adds the required herd7 version to the LKMM README file. Longer term, it would be good if .cat files could specify the required version in a manner allowing herd7 to produce clear diagnostics. Suggested-by: Akira Yokosawa <akiyks@gmail.com> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> Acked-by: Peter Zijlstra <peterz@infradead.org> Cc: Linus Torvalds <torvalds@linux-foundation.org> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: boqun.feng@gmail.com Cc: dhowells@redhat.com Cc: j.alglave@ucl.ac.uk Cc: linux-arch@vger.kernel.org Cc: luc.maranget@inria.fr Cc: nborisov@suse.com Cc: npiggin@gmail.com Cc: parri.andrea@gmail.com Cc: stern@rowland.harvard.edu Cc: will.deacon@arm.com Link: http://lkml.kernel.org/r/1519169112-20593-9-git-send-email-paulmck@linux.vnet.ibm.com Signed-off-by: Ingo Molnar <mingo@kernel.org>
2018-02-21README: Fix a couple of punctuation errorsPaul E. McKenney1-2/+2
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> Acked-by: Peter Zijlstra <peterz@infradead.org> Cc: Linus Torvalds <torvalds@linux-foundation.org> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: akiyks@gmail.com Cc: boqun.feng@gmail.com Cc: dhowells@redhat.com Cc: j.alglave@ucl.ac.uk Cc: linux-arch@vger.kernel.org Cc: luc.maranget@inria.fr Cc: nborisov@suse.com Cc: npiggin@gmail.com Cc: parri.andrea@gmail.com Cc: stern@rowland.harvard.edu Cc: will.deacon@arm.com Link: http://lkml.kernel.org/r/1519169112-20593-5-git-send-email-paulmck@linux.vnet.ibm.com Signed-off-by: Ingo Molnar <mingo@kernel.org>
2018-02-21EXP litmus_tests: Add comments explaining tests' purposesPaul E. McKenney28-1/+246
This commit adds comments to the litmus tests summarizing what these tests are intended to demonstrate. [ paulmck: Apply Andrea's and Alan's feedback. ] Suggested-by: Ingo Molnar <mingo@kernel.org> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> Acked-by: Peter Zijlstra <peterz@infradead.org> Cc: Linus Torvalds <torvalds@linux-foundation.org> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: akiyks@gmail.com Cc: boqun.feng@gmail.com Cc: dhowells@redhat.com Cc: j.alglave@ucl.ac.uk Cc: linux-arch@vger.kernel.org Cc: luc.maranget@inria.fr Cc: nborisov@suse.com Cc: npiggin@gmail.com Cc: parri.andrea@gmail.com Cc: stern@rowland.harvard.edu Cc: will.deacon@arm.com Link: http://lkml.kernel.org/r/1519169112-20593-4-git-send-email-paulmck@linux.vnet.ibm.com Signed-off-by: Ingo Molnar <mingo@kernel.org>
2018-02-21MAINTAINERS: Add the Memory Consistency Model subsystemAndrea Parri1-15/+0
Move the contents of tools/memory-model/MAINTAINERS into the main MAINTAINERS file, removing tools/memory-model/MAINTAINERS. This allows get_maintainer.pl to correctly identify the maintainers of tools/memory-model/. Suggested-by: Ingo Molnar <mingo@kernel.org> Signed-off-by: Andrea Parri <parri.andrea@gmail.com> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> Acked-by: Peter Zijlstra <peterz@infradead.org> Acked-by: Will Deacon <will.deacon@arm.com> Acked-by: Alan Stern <stern@rowland.harvard.edu> Cc: Linus Torvalds <torvalds@linux-foundation.org> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: akiyks@gmail.com Cc: boqun.feng@gmail.com Cc: dhowells@redhat.com Cc: j.alglave@ucl.ac.uk Cc: linux-arch@vger.kernel.org Cc: luc.maranget@inria.fr Cc: nborisov@suse.com Cc: npiggin@gmail.com Link: http://lkml.kernel.org/r/1519169112-20593-2-git-send-email-paulmck@linux.vnet.ibm.com Signed-off-by: Ingo Molnar <mingo@kernel.org>
2018-02-21tools/memory-model: Clarify the origin/scope of the tool nameAndrea Parri4-10/+10
Ingo pointed out that: "The "memory model" name is overly generic, ambiguous and somewhat misleading, as we usually mean the virtual memory layout/model when we say "memory model". GCC too uses it in that sense [...]" Make it clear that tools/memory-model/ uses the term "memory model" as shorthand for "memory consistency model" by calling out this convention in tools/memory-model/README. Stick to the original "memory model" term in sources' headers and for the subsystem name. Suggested-by: Ingo Molnar <mingo@kernel.org> Signed-off-by: Andrea Parri <parri.andrea@gmail.com> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> Acked-by: Peter Zijlstra <peterz@infradead.org> Acked-by: Will Deacon <will.deacon@arm.com> Acked-by: Alan Stern <stern@rowland.harvard.edu> Cc: Linus Torvalds <torvalds@linux-foundation.org> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: akiyks@gmail.com Cc: boqun.feng@gmail.com Cc: dhowells@redhat.com Cc: j.alglave@ucl.ac.uk Cc: linux-arch@vger.kernel.org Cc: luc.maranget@inria.fr Cc: nborisov@suse.com Cc: npiggin@gmail.com Link: http://lkml.kernel.org/r/1519169112-20593-1-git-send-email-paulmck@linux.vnet.ibm.com Signed-off-by: Ingo Molnar <mingo@kernel.org>
2018-01-25Automate memory-barriers.txt; provide Linux-kernel memory modelPaul E. McKenney40-0/+3973
There is some reason to believe that Documentation/memory-barriers.txt could use some help, and a major purpose of this patch is to provide that help in the form of a design-time tool that can produce all valid executions of a small fragment of concurrent Linux-kernel code, which is called a "litmus test". This tool's functionality is roughly similar to a full state-space search. Please note that this is a design-time tool, not useful for regression testing. However, we hope that the underlying Linux-kernel memory model will be incorporated into other tools capable of analyzing large bodies of code for regression-testing purposes. The main tool is herd7, together with the linux-kernel.bell, linux-kernel.cat, linux-kernel.cfg, linux-kernel.def, and lock.cat files added by this patch. The herd7 executable takes the other files as input, and all of these files collectively define the Linux-kernel memory memory model. A brief description of each of these other files is provided in the README file. Although this tool does have its limitations, which are documented in the README file, it does improve on the version reported on in the LWN series (https://lwn.net/Articles/718628/ and https://lwn.net/Articles/720550/) by supporting locking and arithmetic, including a much wider variety of read-modify-write atomic operations. Please note that herd7 is not part of this submission, but is freely available from http://diy.inria.fr/sources/index.html (and via "git" at https://github.com/herd/herdtools7). A second tool is klitmus7, which converts litmus tests to loadable kernel modules for direct testing. As with herd7, the klitmus7 code is freely available from http://diy.inria.fr/sources/index.html (and via "git" at https://github.com/herd/herdtools7). Of course, litmus tests are not always the best way to fully understand a memory model, so this patch also includes Documentation/explanation.txt, which describes the memory model in detail. In addition, Documentation/recipes.txt provides example known-good and known-bad use cases for those who prefer working by example. This patch also includes a few sample litmus tests, and a great many more litmus tests are available at https://github.com/paulmckrcu/litmus. This patch was the result of a most excellent collaboration founded by Jade Alglave and also including Alan Stern, Andrea Parri, and Luc Maranget. For more details on the history of this collaboration, please refer to the Linux-kernel memory model presentations at 2016 LinuxCon EU, 2016 Kernel Summit, 2016 Linux Plumbers Conference, 2017 linux.conf.au, or 2017 Linux Plumbers Conference microconference. However, one aspect of the history does bear repeating due to weak copyright tracking earlier in this project, which extends back to early 2015. This weakness came to light in late 2017 after an LKMM presentation by Paul in which an audience member noted the similarity of some LKMM code to code in early published papers. This prompted a copyright review. From Alan Stern: To say that the model was mine is not entirely accurate. Pieces of it (especially the Scpv and Atomic axioms) were taken directly from Jade's models. And of course the Happens-before and Propagation relations and axioms were heavily based on Jade and Luc's work, even though they weren't identical to the earlier versions. Only the RCU portion was completely original. . . . One can make a much better case that I wrote the bulk of lock.cat. However, it was inspired by Luc's earlier version (and still shares some elements in common), and of course it benefited from feedback and testing from all members of our group. The model prior to Alan's was Luc Maranget's. From Luc: I totally agree on Alan Stern's account of the linux kernel model genesis. I thank him for his acknowledgments of my participation to previous model drafts. I'd like to complete Alan Stern's statement: any bell cat code I have written has its roots in discussions with Jade Alglave and Paul McKenney. Moreover I have borrowed cat and bell code written by Jade Alglave freely. This copyright review therefore resulted in late adds to the copyright statements of several files. Discussion of v1 has raised several issues, which we do not believe should block acceptance given that this level of change will be ongoing, just as it has been with memory-barriers.txt: o Under what conditions should ordering provided by pure locking be seen by CPUs not holding the relevant lock(s)? In particular, should the message-passing pattern be forbidden? o Should examples involving C11 release sequences be forbidden? Note that this C11 is still a moving target for this issue: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0735r0.html o Some details of the handling of internal dependencies for atomic read-modify-write atomic operations are still subject to debate. o Changes recently accepted into mainline greatly reduce the need to handle DEC Alpha as a special case. These changes add an smp_read_barrier_depends() to READ_ONCE(), thus causing Alpha to respect ordering of dependent reads. If these changes stick, the memory model can be simplified accordingly. o Will changes be required to accommodate RISC-V? Differences from v1: (http://lkml.kernel.org/r/20171113184031.GA26302@linux.vnet.ibm.com) o Add SPDX notations to .bell and .cat files, replacing textual license statements. o Add reference to upcoming ASPLOS paper to .bell and .cat files. o Updated identifier names in .bell and .cat files to match those used in the ASPLOS paper. o Updates to READMEs and other documentation based on review feedback. o Added a memory-ordering cheatsheet. o Update sigs to new Co-Developed-by and add acks and reviewed-bys. o Simplify rules detecting nested RCU read-side critical sections. o Update copyright statements as noted above. Co-Developed-by: Alan Stern <stern@rowland.harvard.edu> Co-Developed-by: Andrea Parri <parri.andrea@gmail.com> Co-Developed-by: Jade Alglave <j.alglave@ucl.ac.uk> Co-Developed-by: Luc Maranget <luc.maranget@inria.fr> Co-Developed-by: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> Signed-off-by: Alan Stern <stern@rowland.harvard.edu> Signed-off-by: Andrea Parri <parri.andrea@gmail.com> Signed-off-by: Jade Alglave <j.alglave@ucl.ac.uk> Signed-off-by: Luc Maranget <luc.maranget@inria.fr> Signed-off-by: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> Reviewed-by: Boqun Feng <boqun.feng@gmail.com> Acked-by: Will Deacon <will.deacon@arm.com> Acked-by: Peter Zijlstra <peterz@infradead.org> Acked-by: Nicholas Piggin <npiggin@gmail.com> Acked-by: David Howells <dhowells@redhat.com> Acked-by: "Reshetova, Elena" <elena.reshetova@intel.com> Acked-by: Michal Hocko <mhocko@suse.com> Acked-by: Akira Yokosawa <akiyks@gmail.com> Cc: <linux-arch@vger.kernel.org>