summaryrefslogtreecommitdiffstats
path: root/tools/memory-model
AgeCommit message (Collapse)AuthorFilesLines
2022-10-18tools/memory-model: Weaken ctrl dependency definition in explanation.txtPaul Heidekrüger1-3/+4
The current informal control dependency definition in explanation.txt is too broad and, as discussed, needs to be updated. Consider the following example: > if(READ_ONCE(x)) > return 42; > > WRITE_ONCE(y, 42); > > return 21; The read event determines whether the write event will be executed "at all" - as per the current definition - but the formal LKMM does not recognize this as a control dependency. Introduce a new definition which includes the requirement for the second memory access event to syntactically lie within the arm of a non-loop conditional. Link: https://lore.kernel.org/all/20220615114330.2573952-1-paul.heidekrueger@in.tum.de/ Cc: Marco Elver <elver@google.com> Cc: Charalampos Mainas <charalampos.mainas@gmail.com> Cc: Pramod Bhatotia <pramod.bhatotia@in.tum.de> Cc: Soham Chakraborty <s.s.chakraborty@tudelft.nl> Cc: Martin Fink <martin.fink@in.tum.de> Co-developed-by: Alan Stern <stern@rowland.harvard.edu> Signed-off-by: Alan Stern <stern@rowland.harvard.edu> Signed-off-by: Paul Heidekrüger <paul.heidekrueger@in.tum.de> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2022-08-31tools/memory-model: Clarify LKMM's limitations in litmus-tests.txtPaul Heidekrüger1-10/+27
As discussed, clarify LKMM not recognizing certain kinds of orderings. In particular, highlight the fact that LKMM might deliberately make weaker guarantees than compilers and architectures. [ paulmck: Fix whitespace issue noted by checkpatch.pl. ] Link: https://lore.kernel.org/all/YpoW1deb%2FQeeszO1@ethstick13.dse.in.tum.de/T/#u Co-developed-by: Alan Stern <stern@rowland.harvard.edu> Signed-off-by: Alan Stern <stern@rowland.harvard.edu> Signed-off-by: Paul Heidekrüger <paul.heidekrueger@in.tum.de> Reviewed-by: Marco Elver <elver@google.com> Reviewed-by: Joel Fernandes (Google) <joel@joelfernandes.org> Cc: Charalampos Mainas <charalampos.mainas@gmail.com> Cc: Pramod Bhatotia <pramod.bhatotia@in.tum.de> Cc: Soham Chakraborty <s.s.chakraborty@tudelft.nl> Cc: Martin Fink <martin.fink@in.tum.de> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2022-05-03tools/memory-model/README: Update klitmus7 compat tableAkira Yokosawa1-1/+2
EXPORT_SYMBOL of do_exec() was removed in v5.17. Unfortunately, kernel modules from klitmus7 7.56 have do_exec() at the end of each kthread. herdtools7 7.56.1 has addressed the issue. Update the compatibility table accordingly. Signed-off-by: Akira Yokosawa <akiyks@gmail.com> Cc: Luc Maranget <luc.maranget@inria.fr> Cc: Jade Alglave <j.alglave@ucl.ac.uk> Cc: stable@vger.kernel.org # v5.17+ Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2022-02-01tools/memory-model: Explain syntactic and semantic dependenciesAlan Stern1-0/+51
Paul Heidekrüger pointed out that the Linux Kernel Memory Model documentation doesn't mention the distinction between syntactic and semantic dependencies. This is an important difference, because the compiler can easily break dependencies that are only syntactic, not semantic. This patch adds a few paragraphs to the LKMM documentation explaining these issues and illustrating how they can matter. Suggested-by: Paul Heidekrüger <paul.heidekrueger@in.tum.de> Reviewed-by: Akira Yokosawa <akiyks@gmail.com> Signed-off-by: Alan Stern <stern@rowland.harvard.edu> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2021-11-30tools/memory-model: litmus: Add two tests for unlock(A)+lock(B) orderingBoqun Feng3-0/+76
The memory model has been updated to provide a stronger ordering guarantee for unlock(A)+lock(B) on the same CPU/thread. Therefore add two litmus tests describing this new guarantee, these tests are simple yet can clearly show the usage of the new guarantee, also they can serve as the self tests for the modification in the model. Co-developed-by: Alan Stern <stern@rowland.harvard.edu> Signed-off-by: Alan Stern <stern@rowland.harvard.edu> Signed-off-by: Boqun Feng <boqun.feng@gmail.com> Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2021-11-30tools/memory-model: doc: Describe the requirement of the litmus-tests directoryBoqun Feng1-0/+12
It's better that we have some "standard" about which test should be put in the litmus-tests directory because it helps future contributors understand whether they should work on litmus-tests in kernel or Paul's GitHub repo. Therefore explain a little bit on what a "representative" litmus test is. Signed-off-by: Boqun Feng <boqun.feng@gmail.com> Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2021-11-30tools/memory-model: Provide extra ordering for unlock+lock pair on the same CPUBoqun Feng2-22/+28
A recent discussion[1] shows that we are in favor of strengthening the ordering of unlock + lock on the same CPU: a unlock and a po-after lock should provide the so-called RCtso ordering, that is a memory access S po-before the unlock should be ordered against a memory access R po-after the lock, unless S is a store and R is a load. The strengthening meets programmers' expection that "sequence of two locked regions to be ordered wrt each other" (from Linus), and can reduce the mental burden when using locks. Therefore add it in LKMM. [1]: https://lore.kernel.org/lkml/20210909185937.GA12379@rowland.harvard.edu/ Co-developed-by: Alan Stern <stern@rowland.harvard.edu> Signed-off-by: Alan Stern <stern@rowland.harvard.edu> Signed-off-by: Boqun Feng <boqun.feng@gmail.com> Reviewed-by: Michael Ellerman <mpe@ellerman.id.au> (powerpc) Acked-by: Palmer Dabbelt <palmerdabbelt@google.com> (RISC-V) Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2021-07-27tools/memory-model: Document data_race(READ_ONCE())Paul E. McKenney1-14/+35
It is possible to cause KCSAN to ignore marked accesses by applying __no_kcsan to the function or applying data_race() to the marked accesses. These approaches allow the developer to restrict compiler optimizations while also causing KCSAN to ignore diagnostic accesses. This commit therefore updates the documentation accordingly. Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2021-07-27tools/memory-model: Heuristics using data_race() must handle all valuesManfred Spraul1-0/+5
Data loaded for use by some sorts of heuristics can tolerate the occasional erroneous value. In this case the loads may use data_race() to give the compiler full freedom to optimize while also informing KCSAN of the intent. However, for this to work, the heuristic needs to be able to tolerate any erroneous value that could possibly arise. This commit therefore adds a paragraph spelling this out. Signed-off-by: Manfred Spraul <manfred@colorfullife.com> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2021-07-27tools/memory-model: Add example for heuristic lockless readsPaul E. McKenney1-0/+93
This commit adds example code for heuristic lockless reads, based loosely on the sem_lock() and sem_unlock() functions. [ paulmck: Apply Alan Stern and Manfred Spraul feedback. ] Reported-by: Manfred Spraul <manfred@colorfullife.com> [ paulmck: Update per Manfred Spraul and Hillf Danton feedback. ] Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2021-07-20tools/memory-model: Make read_foo_diagnostic() more clearly diagnosticPaul E. McKenney1-2/+2
The current definition of read_foo_diagnostic() in the "Lock Protection With Lockless Diagnostic Access" section returns a value, which could be use for any purpose. This could mislead people into incorrectly using data_race() in cases where READ_ONCE() is required. This commit therefore makes read_foo_diagnostic() simply print the value read. Reported-by: Manfred Spraul <manfred@colorfullife.com> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2021-05-10tools/memory-model: Fix smp_mb__after_spinlock() spellingBjörn Töpel1-1/+1
A misspelled git-grep regex revealed that smp_mb__after_spinlock() was misspelled in explanation.txt. This commit adds the missing "_". Fixes: 1c27b644c0fd ("Automate memory-barriers.txt; provide Linux-kernel memory model") [ paulmck: Apply Alan Stern commit-log feedback. ] Signed-off-by: Björn Töpel <bjorn.topel@intel.com> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2021-03-15tools/memory-model: Add access-marking documentationPaul E. McKenney1-0/+479
This commit adapts the "Concurrency bugs should fear the big bad data-race detector (part 2)" LWN article (https://lwn.net/Articles/816854/) to kernel-documentation form. This allows more easily updating the material as needed. Suggested-by: Thomas Gleixner <tglx@linutronix.de> [ paulmck: Apply Marco Elver feedback. ] [ paulmck: Update per Akira Yokosawa feedback. ] Reviewed-by: Marco Elver <elver@google.com> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2021-03-08tools/memory-model: Remove reference to atomic_ops.rstAkira Yokosawa1-1/+0
atomic_ops.rst was removed by commit f0400a77ebdc ("atomic: Delete obsolete documentation"). Remove the broken link in tools/memory-model/Documentation/simple.txt. Cc: Peter Zijlstra <peterz@infradead.org> Signed-off-by: Akira Yokosawa <akiyks@gmail.com> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2021-03-08doc: Update rcu_dereference.rst referenceMauro Carvalho Chehab1-1/+1
Changeset b00aedf978aa ("doc: Convert to rcu_dereference.txt to rcu_dereference.rst") renamed: Documentation/RCU/rcu_dereference.txt to: Documentation/RCU/rcu_dereference.rst. Update its cross-reference accordingly. Signed-off-by: Mauro Carvalho Chehab <mchehab+huawei@kernel.org> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2021-01-04tools/memory-model: Fix typo in klitmus7 compatibility tableAkira Yokosawa1-1/+1
klitmus7 of herdtools7 7.48 or earlier depends on ACCESS_ONCE(), which was removed in Linux v4.15. Fix the obvious typo in the table. Fixes: d075a78a5ab1 ("tools/memory-model/README: Expand dependency of klitmus7") Signed-off-by: Akira Yokosawa <akiyks@gmail.com> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2021-01-04tools/memory-model: Remove redundant initialization in litmus testsAkira Yokosawa32-134/+32
This is a revert of commit 1947bfcf81a9 ("tools/memory-model: Add types to litmus tests") with conflict resolutions. klitmus7 [1] is aware of default types of "int" and "int*". It accepts litmus tests for herd7 without extra type info unless non-"int" variables are referenced by an "exists", "locations", or "filter" directive. [1]: Tested with klitmus7 versions 7.49 or later. Suggested-by: Paul E. McKenney <paulmck@kernel.org> Signed-off-by: Akira Yokosawa <akiyks@gmail.com> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2021-01-04tools/memory-model: Tie acquire loads to reads-fromPaul E. McKenney1-3/+9
This commit explicitly makes the connection between acquire loads and the reads-from relation. It also adds an entry for happens-before, and refers to the corresponding section of explanation.txt. Reported-by: Boqun Feng <boqun.feng@gmail.com> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2020-11-06tools/memory-model: Label MP tests' producers and consumersPaul E. McKenney8-24/+24
This commit adds comments that label the MP tests' producer and consumer processes, and also that label the "exists" clause as the bad outcome. Reported-by: Johannes Weiner <hannes@cmpxchg.org> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2020-11-06tools/memory-model: Use "buf" and "flag" for message-passing testsPaul E. McKenney6-46/+46
The use of "x" and "y" for message-passing tests is fine for people familiar with memory models and litmus-test nomenclature, but is a bit obtuse for others. This commit therefore substitutes "buf" for "x" and "flag" for "y" for the MP tests. There are a few special-case MP tests that use locks and these are unchanged. There is another MP test that uses pointers, and this is changed to name the pointer "p". Reported-by: Johannes Weiner <hannes@cmpxchg.org> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2020-11-06tools/memory-model: Add types to litmus testsPaul E. McKenney32-31/+130
This commit adds type information for global variables in the litmus tests in order to allow easier use with klitmus7. Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2020-11-06tools/memory-model: Add a glossary of LKMM termsPaul E. McKenney1-0/+172
[ paulmck: Apply Alan Stern feedback. ] Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2020-11-06tools/memory-model: Document categories of ordering primitivesPaul E. McKenney3-0/+831
The Linux kernel has a number of categories of ordering primitives, which are recorded in the LKMM implementation and hinted at by cheatsheet.txt. But there is no overview of these categories, and such an overview is needed in order to understand multithreaded LKMM litmus tests. This commit therefore adds an ordering.txt as well as extracting a control-dependencies.txt from memory-barriers.txt. It also updates the README file. [ paulmck: Apply Akira Yokosawa file-placement feedback. ] [ paulmck: Apply Alan Stern feedback. ] [ paulmck: Apply self-review feedback. ] Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2020-10-26tools/memory-model: Move Documentation description to Documentation/READMEPaul E. McKenney2-20/+61
This commit moves the descriptions of the files residing in tools/memory-model/Documentation to a README file in that directory, leaving behind the description of tools/memory-model/Documentation/README itself. After this change, tools/memory-model/Documentation/README provides a guide to the files in the tools/memory-model/Documentation directory, guiding people with different skills and needs to the most appropriate starting point. Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2020-10-26tools: memory-model: Document that the LKMM can easily miss control dependenciesAlan Stern1-0/+17
Add a small section to the litmus-tests.txt documentation file for the Linux Kernel Memory Model explaining that the memory model often fails to recognize certain control dependencies. Suggested-by: Akira Yokosawa <akiyks@gmail.com> Signed-off-by: Alan Stern <stern@rowland.harvard.edu> Reviewed-by: Joel Fernandes (Google) <joel@joelfernandes.org> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2020-09-04tools/memory-model: Expand the cheatsheet.txt notion of relaxedPaul E. McKenney1-14/+19
This commit adds a key entry enumerating the various types of relaxed operations. While in the area, it also renames the relaxed rows. [ paulmck: Apply Boqun Feng feedback. ] Acked-by: Boqun Feng <boqun.feng@gmail.com> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2020-09-03tools/memory-model: Add a simple entry point documentPaul E. McKenney3-2/+282
Current LKMM documentation assumes that the reader already understands concurrency in the Linux kernel, which won't necessarily always be the case. This commit supplies a simple.txt file that provides a starting point for someone who is new to concurrency in the Linux kernel. That said, this file might also useful as a reminder to experienced developers of simpler approaches to dealing with concurrency. Link: Link: https://lwn.net/Articles/827180/ [ paulmck: Apply feedback from Joel Fernandes. ] Co-developed-by: Dave Chinner <dchinner@redhat.com> Signed-off-by: Dave Chinner <dchinner@redhat.com> Co-developed-by: Paul E. McKenney <paulmck@kernel.org> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2020-09-03tools/memory-model: Improve litmus-test documentationPaul E. McKenney2-117/+1108
The current LKMM documentation says very little about litmus tests, and worse yet directs people to the herd7 documentation for more information. Now, the herd7 documentation is quite voluminous and educational, but it is intended for people creating and modifying memory models, not those attempting to use them. This commit therefore updates README and creates a litmus-tests.txt file that gives an overview of litmus-test format and describes ways of modeling various special cases, illustrated with numerous examples. [ paulmck: Add Alan Stern feedback. ] [ paulmck: Apply Dave Chinner feedback. ] [ paulmck: Apply Andrii Nakryiko feedback. ] [ paulmck: Apply Johannes Weiner feedback. ] Link: https://lwn.net/Articles/827180/ Reported-by: Dave Chinner <david@fromorbit.com> Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2020-09-03tools/memory-model: Update recipes.txt prime_numbers.c pathPaul E. McKenney1-2/+2
The expand_to_next_prime() and next_prime_number() functions have moved from lib/prime_numbers.c to lib/math/prime_numbers.c, so this commit updates recipes.txt to reflect this change. Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2020-09-03Replace HTTP links with HTTPS ones: LKMMAlexander A. Klimov1-1/+1
Rationale: Reduces attack surface on kernel devs opening the links for MITM as HTTPS traffic is much harder to manipulate. Deterministic algorithm: For each file: If not .svg: For each line: If doesn't contain `\bxmlns\b`: For each link, `\bhttp://[^# \t\r\n]*(?:\w|/)`: If both the HTTP and HTTPS versions return 200 OK and serve the same content: Replace HTTP with HTTPS. Signed-off-by: Alexander A. Klimov <grandmaster@al2klimov.de> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2020-08-03Merge tag 'locking-core-2020-08-03' of ↵Linus Torvalds4-46/+100
git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip Pull locking updates from Ingo Molnar: - LKMM updates: mostly documentation changes, but also some new litmus tests for atomic ops. - KCSAN updates: the most important change is that GCC 11 now has all fixes in place to support KCSAN, so GCC support can be enabled again. Also more annotations. - futex updates: minor cleanups and simplifications - seqlock updates: merge preparatory changes/cleanups for the 'associated locks' facilities. - lockdep updates: - simplify IRQ trace event handling - add various new debug checks - simplify header dependencies, split out <linux/lockdep_types.h>, decouple lockdep from other low level headers some more - fix NMI handling - misc cleanups and smaller fixes * tag 'locking-core-2020-08-03' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip: (60 commits) kcsan: Improve IRQ state trace reporting lockdep: Refactor IRQ trace events fields into struct seqlock: lockdep assert non-preemptibility on seqcount_t write lockdep: Add preemption enabled/disabled assertion APIs seqlock: Implement raw_seqcount_begin() in terms of raw_read_seqcount() seqlock: Add kernel-doc for seqcount_t and seqlock_t APIs seqlock: Reorder seqcount_t and seqlock_t API definitions seqlock: seqcount_t latch: End read sections with read_seqcount_retry() seqlock: Properly format kernel-doc code samples Documentation: locking: Describe seqlock design and usage locking/qspinlock: Do not include atomic.h from qspinlock_types.h locking/atomic: Move ATOMIC_INIT into linux/types.h lockdep: Move list.h inclusion into lockdep.h locking/lockdep: Fix TRACE_IRQFLAGS vs. NMIs futex: Remove unused or redundant includes futex: Consistently use fshared as boolean futex: Remove needless goto's futex: Remove put_futex_key() rwsem: fix commas in initialisation docs: locking: Replace HTTP links with HTTPS ones ...
2020-07-21tools/memory-model: Remove smp_read_barrier_depends() from informal docWill Deacon1-14/+12
smp_read_barrier_depends() has gone the way of mmiowb() and so many esoteric memory barriers before it. Drop the two mentions of this deceased barrier from the LKMM informal explanation document. Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org> Acked-by: Alan Stern <stern@rowland.harvard.edu> Acked-by: Paul E. McKenney <paulmck@kernel.org> Signed-off-by: Will Deacon <will@kernel.org>
2020-06-29tools/memory-model/README: Mention herdtools7 7.56 in compatibility tableAkira Yokosawa1-1/+1
herdtools7 7.56 is going to be released in the week of 22 Jun 2020. This commit therefore adds the exact version in the compatibility table. Acked-by: Andrea Parri <parri.andrea@gmail.com> Signed-off-by: Akira Yokosawa <akiyks@gmail.com> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2020-06-29tools/memory-model/README: Expand dependency of klitmus7Akira Yokosawa1-2/+28
klitmus7 is independent of the memory model but depends on the build-target kernel release. It occasionally lost compatibility due to kernel API changes [1, 2, 3]. It was remedied in a backwards-compatible manner respectively [4, 5, 6]. Reflect this fact in README. [1]: b899a850431e ("compiler.h: Remove ACCESS_ONCE()") [2]: 0bb95f80a38f ("Makefile: Globally enable VLA warning") [3]: d56c0d45f0e2 ("proc: decouple proc from VFS with "struct proc_ops"") [4]: https://github.com/herd/herdtools7/commit/e87d7f9287d1 ("klitmus: Use WRITE_ONCE and READ_ONCE in place of deprecated ACCESS_ONCE") [5]: https://github.com/herd/herdtools7/commit/a0cbb10d02be ("klitmus: Avoid variable length array") [6]: https://github.com/herd/herdtools7/commit/46b9412d3a58 ("klitmus: Linux kernel v5.6.x compat") NOTE: [5] was ahead of herdtools7 7.53, which did not make an official release. Code generated by klitmus7 without [5] can still be built targeting Linux 4.20--5.5 if you don't care VLA warnings. Acked-by: Andrea Parri <parri.andrea@gmail.com> Signed-off-by: Akira Yokosawa <akiyks@gmail.com> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2020-06-29tools/memory-model: Fix reference to litmus test in recipes.txtAkira Yokosawa1-1/+1
The name of litmus test doesn't match the one described below. Fix the name of litmus test. Acked-by: Andrea Parri <parri.andrea@gmail.com> Acked-by: Joel Fernandes (Google) <joel@joelfernandes.org> Signed-off-by: Akira Yokosawa <akiyks@gmail.com> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2020-06-29tools/memory-model: Add an exception for limitations on _unless() familyBoqun Feng1-3/+7
According to Luc, atomic_add_unless() is directly provided by herd7, therefore it can be used in litmus tests. So change the limitation section in README to unlimit the use of atomic_add_unless(). Cc: Luc Maranget <luc.maranget@inria.fr> Acked-by: Andrea Parri <parri.andrea@gmail.com> Reviewed-by: Joel Fernandes (Google) <joel@joelfernandes.org> Signed-off-by: Boqun Feng <boqun.feng@gmail.com> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2020-06-29tools/memory-model: Fix "conflict" definitionMarco Elver1-38/+45
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> Acked-by: Andrea Parri <parri.andrea@gmail.com> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2020-06-29tools/memory-model: Add recent referencesPaul E. McKenney1-2/+19
This commit updates the list of LKMM-related publications in Documentation/references.txt. Signed-off-by: Paul E. McKenney <paulmck@kernel.org> Acked-by: Andrea Parri <parri.andrea@gmail.com>
2020-03-25.gitignore: add SPDX License IdentifierMasahiro Yamada2-0/+2
Add SPDX License Identifier to all .gitignore files. Signed-off-by: Masahiro Yamada <masahiroy@kernel.org> Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
2019-10-05tools/memory-model/Documentation: Add plain accesses and data races to ↵Alan Stern1-5/+534
explanation.txt This patch updates the Linux Kernel Memory Model's explanation.txt file by adding a section devoted to the model's handling of plain accesses and data-race detection. Signed-off-by: Alan Stern <stern@rowland.harvard.edu> Acked-by: Andrea Parri <parri.andrea@gmail.com> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2019-10-05tools/memory-model/Documentation: Put redefinition of rcu-fence into ↵Alan Stern1-17/+36
explanation.txt This patch updates the Linux Kernel Memory Model's explanation.txt file to incorporate the introduction of the rcu-order relation and the redefinition of rcu-fence made by commit 15aa25cbf0cc ("tools/memory-model: Change definition of rcu-fence"). Signed-off-by: Alan Stern <stern@rowland.harvard.edu> Acked-by: Andrea Parri <parri.andrea@gmail.com> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2019-10-05tools/memory-model/Documentation: Fix typos in explanation.txtAlan Stern1-5/+5
This patch fixes a few minor typos and improves word usage in a few places in the Linux Kernel Memory Model's explanation.txt file. Signed-off-by: Alan Stern <stern@rowland.harvard.edu> Reviewed-by: Joel Fernandes (Google) <joel@joelfernandes.org> Acked-by: Andrea Parri <parri.andrea@gmail.com> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2019-10-05tools/memory-model: Fix data race detection for unordered store and loadAlan Stern1-1/+1
Currently the Linux Kernel Memory Model gives an incorrect response for the following litmus test: C plain-WWC {} P0(int *x) { WRITE_ONCE(*x, 2); } P1(int *x, int *y) { int r1; int r2; int r3; r1 = READ_ONCE(*x); if (r1 == 2) { smp_rmb(); r2 = *x; } smp_rmb(); r3 = READ_ONCE(*x); WRITE_ONCE(*y, r3 - 1); } P2(int *x, int *y) { int r4; r4 = READ_ONCE(*y); if (r4 > 0) WRITE_ONCE(*x, 1); } exists (x=2 /\ 1:r2=2 /\ 2:r4=1) The memory model says that the plain read of *x in P1 races with the WRITE_ONCE(*x) in P2. The problem is that we have a write W and a read R related by neither fre or rfe, but rather W ->coe W' ->rfe R, where W' is an intermediate write (the WRITE_ONCE() in P0). In this situation there is no particular ordering between W and R, so either a wr-vis link from W to R or an rw-xbstar link from R to W would prove that the accesses aren't concurrent. But the LKMM only looks for a wr-vis link, which is equivalent to assuming that W must execute before R. This is not necessarily true on non-multicopy-atomic systems, as the WWC pattern demonstrates. This patch changes the LKMM to accept either a wr-vis or a reverse rw-xbstar link as a proof of non-concurrency. Signed-off-by: Alan Stern <stern@rowland.harvard.edu> Acked-by: Andrea Parri <parri.andrea@gmail.com> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2019-08-09tools/memory-model: Update the informal documentationAndrea Parri2-35/+30
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 <andrea.parri@amarulasolutions.com> Cc: Will Deacon <will.deacon@arm.com> Cc: Peter Zijlstra <peterz@infradead.org> Cc: Boqun Feng <boqun.feng@gmail.com> Cc: Nicholas Piggin <npiggin@gmail.com> Cc: David Howells <dhowells@redhat.com> Cc: Jade Alglave <j.alglave@ucl.ac.uk> Cc: Luc Maranget <luc.maranget@inria.fr> Cc: "Paul E. McKenney" <paulmck@linux.ibm.com> Cc: Akira Yokosawa <akiyks@gmail.com> Cc: Daniel Lustig <dlustig@nvidia.com> Signed-off-by: Paul E. McKenney <paulmck@linux.ibm.com> Acked-by: Alan Stern <stern@rowland.harvard.edu>
2019-08-09tools/memory-model: Use cumul-fence instead of fence in ->prop exampleJoel Fernandes (Google)1-3/+3
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 <stern@rowland.harvard.edu> Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org> Acked-by: Alan Stern <stern@rowland.harvard.edu> Signed-off-by: Paul E. McKenney <paulmck@linux.ibm.com>
2019-08-01tools/memory-model: Make scripts be executablePaul E. McKenney8-0/+0
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 <paulmck@linux.ibm.com>
2019-06-24tools/memory-model: Improve data-race detectionAlan Stern1-3/+5
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 <herbert@gondor.apana.org.au> Signed-off-by: Alan Stern <stern@rowland.harvard.edu> Acked-by: Andrea Parri <andrea.parri@amarulasolutions.com> Signed-off-by: Paul E. McKenney <paulmck@linux.ibm.com> Tested-by: Akira Yokosawa <akiyks@gmail.com>
2019-06-21tools/memory-model: Change definition of rcu-fenceAlan Stern1-10/+13
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 <stern@rowland.harvard.edu> Acked-by: Andrea Parri <andrea.parri@amarulasolutions.com> Signed-off-by: Paul E. McKenney <paulmck@linux.ibm.com>
2019-06-21tools/memory-model: Expand definition of barrierAlan Stern1-1/+2
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 <stern@rowland.harvard.edu> Acked-by: Andrea Parri <andrea.parri@amarulasolutions.com> Signed-off-by: Paul E. McKenney <paulmck@linux.ibm.com>
2019-06-19tools/memory-model: Do not use "herd" to refer to "herd7"Andrea Parri7-8/+8
Use "herd7" in each such reference. Signed-off-by: Andrea Parri <andrea.parri@amarulasolutions.com> Cc: Will Deacon <will.deacon@arm.com> Cc: Peter Zijlstra <peterz@infradead.org> Cc: Boqun Feng <boqun.feng@gmail.com> Cc: Nicholas Piggin <npiggin@gmail.com> Cc: David Howells <dhowells@redhat.com> Cc: Jade Alglave <j.alglave@ucl.ac.uk> Cc: Luc Maranget <luc.maranget@inria.fr> Cc: "Paul E. McKenney" <paulmck@linux.ibm.com> Cc: Akira Yokosawa <akiyks@gmail.com> Cc: Daniel Lustig <dlustig@nvidia.com> Acked-by: Alan Stern <stern@rowland.harvard.edu> Signed-off-by: Paul E. McKenney <paulmck@linux.ibm.com>
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-17 22:23:20 +0000