• Paul E. McKenney's avatar
    Automate memory-barriers.txt; provide Linux-kernel memory model · 1c27b644
    Paul E. McKenney authored
    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: default avatarAlan Stern <stern@rowland.harvard.edu>
    Co-Developed-by: default avatarAndrea Parri <parri.andrea@gmail.com>
    Co-Developed-by: default avatarJade Alglave <j.alglave@ucl.ac.uk>
    Co-Developed-by: default avatarLuc Maranget <luc.maranget@inria.fr>
    Co-Developed-by: default avatar"Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
    Signed-off-by: default avatarAlan Stern <stern@rowland.harvard.edu>
    Signed-off-by: default avatarAndrea Parri <parri.andrea@gmail.com>
    Signed-off-by: default avatarJade Alglave <j.alglave@ucl.ac.uk>
    Signed-off-by: default avatarLuc Maranget <luc.maranget@inria.fr>
    Signed-off-by: default avatar"Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
    Reviewed-by: default avatarBoqun Feng <boqun.feng@gmail.com>
    Acked-by: default avatarWill Deacon <will.deacon@arm.com>
    Acked-by: default avatarPeter Zijlstra <peterz@infradead.org>
    Acked-by: default avatarNicholas Piggin <npiggin@gmail.com>
    Acked-by: default avatarDavid Howells <dhowells@redhat.com>
    Acked-by: default avatar"Reshetova, Elena" <elena.reshetova@intel.com>
    Acked-by: default avatarMichal Hocko <mhocko@suse.com>
    Acked-by: default avatarAkira Yokosawa <akiyks@gmail.com>
    Cc: <linux-arch@vger.kernel.org>
    1c27b644
WRC+poonceonces+Once.litmus 260 Bytes