diff options
Diffstat (limited to 'tools')
| -rw-r--r-- | tools/memory-model/Documentation/cheatsheet.txt | 7 | ||||
| -rw-r--r-- | tools/memory-model/Documentation/explanation.txt | 221 | ||||
| -rw-r--r-- | tools/memory-model/Documentation/references.txt | 17 | ||||
| -rw-r--r-- | tools/memory-model/README | 2 | ||||
| -rw-r--r-- | tools/memory-model/linux-kernel.bell | 4 | ||||
| -rw-r--r-- | tools/memory-model/linux-kernel.cat | 41 | ||||
| -rw-r--r-- | tools/memory-model/linux-kernel.def | 34 | ||||
| -rw-r--r-- | tools/memory-model/litmus-tests/.gitignore | 1 | ||||
| -rw-r--r-- | tools/memory-model/litmus-tests/IRIW+mbonceonces+OnceOnce.litmus | 2 | ||||
| -rw-r--r-- | tools/memory-model/litmus-tests/MP+polockmbonce+poacquiresilsil.litmus | 35 | ||||
| -rw-r--r-- | tools/memory-model/litmus-tests/MP+polockonce+poacquiresilsil.litmus | 34 | ||||
| -rw-r--r-- | tools/memory-model/litmus-tests/README | 19 | ||||
| -rw-r--r-- | tools/memory-model/litmus-tests/WRC+pooncerelease+rmbonceonce+Once.litmus | 4 | ||||
| -rw-r--r-- | tools/memory-model/lock.cat | 107 | ||||
| -rw-r--r-- | tools/memory-model/scripts/checkalllitmus.sh | 73 | ||||
| -rw-r--r-- | tools/memory-model/scripts/checklitmus.sh | 86 |
16 files changed, 523 insertions, 164 deletions
diff --git a/tools/memory-model/Documentation/cheatsheet.txt b/tools/memory-model/Documentation/cheatsheet.txt index 956b1ae4aafb..33ba98d72b16 100644 --- a/tools/memory-model/Documentation/cheatsheet.txt +++ b/tools/memory-model/Documentation/cheatsheet.txt @@ -1,6 +1,6 @@ Prior Operation Subsequent Operation --------------- --------------------------- - C Self R W RWM Self R W DR DW RMW SV + C Self R W RMW Self R W DR DW RMW SV -- ---- - - --- ---- - - -- -- --- -- Store, e.g., WRITE_ONCE() Y Y @@ -14,7 +14,7 @@ smp_wmb() Y W Y Y W smp_mb() & synchronize_rcu() CP Y Y Y Y Y Y Y Y Successful full non-void RMW CP Y Y Y Y Y Y Y Y Y Y Y smp_mb__before_atomic() CP Y Y Y a a a a Y -smp_mb__after_atomic() CP a a Y Y Y Y Y +smp_mb__after_atomic() CP a a Y Y Y Y Y Y Key: C: Ordering is cumulative @@ -26,4 +26,5 @@ Key: C: Ordering is cumulative DR: Dependent read (address dependency) DW: Dependent write (address, data, or control dependency) RMW: Atomic read-modify-write operation - SV Same-variable access + SELF: Orders self, as opposed to accesses before and/or after + SV: Orders later accesses to the same variable diff --git a/tools/memory-model/Documentation/explanation.txt b/tools/memory-model/Documentation/explanation.txt index a727c82bd434..1b09f3175a1f 100644 --- a/tools/memory-model/Documentation/explanation.txt +++ b/tools/memory-model/Documentation/explanation.txt @@ -27,7 +27,7 @@ Explanation of the Linux-Kernel Memory Consistency Model 19. AND THEN THERE WAS ALPHA 20. THE HAPPENS-BEFORE RELATION: hb 21. THE PROPAGATES-BEFORE RELATION: pb - 22. RCU RELATIONS: link, gp-link, rscs-link, and rcu-path + 22. RCU RELATIONS: rcu-link, gp, rscs, rcu-fence, and rb 23. ODDS AND ENDS @@ -1451,8 +1451,8 @@ they execute means that it cannot have cycles. This requirement is the content of the LKMM's "propagation" axiom. -RCU RELATIONS: link, gp-link, rscs-link, and rcu-path ------------------------------------------------------ +RCU RELATIONS: rcu-link, gp, rscs, rcu-fence, and rb +---------------------------------------------------- RCU (Read-Copy-Update) is a powerful synchronization mechanism. It rests on two concepts: grace periods and read-side critical sections. @@ -1509,8 +1509,8 @@ y, which occurs before the end of the critical section, did not propagate to P1 before the end of the grace period, violating the Guarantee. -In the kernel's implementations of RCU, the business about stores -propagating to every CPU is realized by placing strong fences at +In the kernel's implementations of RCU, the requirements for stores +to propagate to every CPU are fulfilled by placing strong fences at suitable places in the RCU-related code. Thus, if a critical section starts before a grace period does then the critical section's CPU will execute an smp_mb() fence after the end of the critical section and @@ -1523,72 +1523,124 @@ executes. What exactly do we mean by saying that a critical section "starts before" or "ends after" a grace period? Some aspects of the meaning are pretty obvious, as in the example above, but the details aren't -entirely clear. The LKMM formalizes this notion by means of a -relation with the unfortunately generic name "link". It is a very -general relation; among other things, X ->link Z includes cases where -X happens-before or is equal to some event Y which is equal to or -comes before Z in the coherence order. Taking Y = Z, this says that -X ->rfe Z implies X ->link Z, and taking Y = X, it says that X ->fr Z -and X ->co Z each imply X ->link Z. - -The formal definition of the link relation is more than a little +entirely clear. The LKMM formalizes this notion by means of the +rcu-link relation. rcu-link encompasses a very general notion of +"before": Among other things, X ->rcu-link Z includes cases where X +happens-before or is equal to some event Y which is equal to or comes +before Z in the coherence order. When Y = Z this says that X ->rfe Z +implies X ->rcu-link Z. In addition, when Y = X it says that X ->fr Z +and X ->co Z each imply X ->rcu-link Z. + +The formal definition of the rcu-link relation is more than a little obscure, and we won't give it here. It is closely related to the pb relation, and the details don't matter unless you want to comb through a somewhat lengthy formal proof. Pretty much all you need to know -about link is the information in the preceding paragraph. - -The LKMM goes on to define the gp-link and rscs-link relations. They -bring grace periods and read-side critical sections into the picture, -in the following way: - - E ->gp-link F means there is a synchronize_rcu() fence event S - and an event X such that E ->po S, either S ->po X or S = X, - and X ->link F. In other words, E and F are connected by a - grace period followed by an instance of link. - - E ->rscs-link F means there is a critical section delimited by - an rcu_read_lock() fence L and an rcu_read_unlock() fence U, - and an event X such that E ->po U, either L ->po X or L = X, - and X ->link F. Roughly speaking, this says that some event - in the same critical section as E is connected by link to F. - -If we think of the link relation as standing for an extended "before", -then E ->gp-link F says that E executes before a grace period which -ends before F executes. (In fact it says more than this, because it -includes cases where E executes before a grace period and some store -propagates to F's CPU before F executes and doesn't propagate to some -other CPU until after the grace period ends.) Similarly, -E ->rscs-link F says that E is part of (or before the start of) a -critical section which starts before F executes. +about rcu-link is the information in the preceding paragraph. + +The LKMM also defines the gp and rscs relations. They bring grace +periods and read-side critical sections into the picture, in the +following way: + + E ->gp F means there is a synchronize_rcu() fence event S such + that E ->po S and either S ->po F or S = F. In simple terms, + there is a grace period po-between E and F. + + E ->rscs F means there is a critical section delimited by an + rcu_read_lock() fence L and an rcu_read_unlock() fence U, such + that E ->po U and either L ->po F or L = F. You can think of + this as saying that E and F are in the same critical section + (in fact, it also allows E to be po-before the start of the + critical section and F to be po-after the end). + +If we think of the rcu-link relation as standing for an extended +"before", then X ->gp Y ->rcu-link Z says that X executes before a +grace period which ends before Z executes. (In fact it covers more +than this, because it also includes cases where X executes before a +grace period and some store propagates to Z's CPU before Z executes +but doesn't propagate to some other CPU until after the grace period +ends.) Similarly, X ->rscs Y ->rcu-link Z says that X is part of (or +before the start of) a critical section which starts before Z +executes. + +The LKMM goes on to define the rcu-fence relation as a sequence of gp +and rscs links separated by rcu-link links, in which the number of gp +links is >= the number of rscs links. For example: + + X ->gp Y ->rcu-link Z ->rscs T ->rcu-link U ->gp V + +would imply that X ->rcu-fence V, because this sequence contains two +gp links and only one rscs link. (It also implies that X ->rcu-fence T +and Z ->rcu-fence V.) On the other hand: + + X ->rscs Y ->rcu-link Z ->rscs T ->rcu-link U ->gp V + +does not imply X ->rcu-fence V, because the sequence contains only +one gp link but two rscs links. + +The rcu-fence relation is important because the Grace Period Guarantee +means that rcu-fence acts kind of like a strong fence. In particular, +if W is a write and we have W ->rcu-fence Z, the Guarantee says that W +will propagate to every CPU before Z executes. + +To prove this in full generality requires some intellectual effort. +We'll consider just a very simple case: + + W ->gp X ->rcu-link Y ->rscs Z. + +This formula means that there is a grace period G and a critical +section C such that: + + 1. W is po-before G; + + 2. X is equal to or po-after G; + + 3. X comes "before" Y in some sense; + + 4. Y is po-before the end of C; + + 5. Z is equal to or po-after the start of C. + +From 2 - 4 we deduce that the grace period G ends before the critical +section C. Then the second part of the Grace Period Guarantee says +not only that G starts before C does, but also that W (which executes +on G's CPU before G starts) must propagate to every CPU before C +starts. In particular, W propagates to every CPU before Z executes +(or finishes executing, in the case where Z is equal to the +rcu_read_lock() fence event which starts C.) This sort of reasoning +can be expanded to handle all the situations covered by rcu-fence. + +Finally, the LKMM defines the RCU-before (rb) relation in terms of +rcu-fence. This is done in essentially the same way as the pb +relation was defined in terms of strong-fence. We will omit the +details; the end result is that E ->rb F implies E must execute before +F, just as E ->pb F does (and for much the same reasons). Putting this all together, the LKMM expresses the Grace Period -Guarantee by requiring that there are no cycles consisting of gp-link -and rscs-link connections in which the number of gp-link instances is ->= the number of rscs-link instances. It does this by defining the -rcu-path relation to link events E and F whenever it is possible to -pass from E to F by a sequence of gp-link and rscs-link connections -with at least as many of the former as the latter. The LKMM's "rcu" -axiom then says that there are no events E such that E ->rcu-path E. - -Justifying this axiom takes some intellectual effort, but it is in -fact a valid formalization of the Grace Period Guarantee. We won't -attempt to go through the detailed argument, but the following -analysis gives a taste of what is involved. Suppose we have a -violation of the first part of the Guarantee: A critical section -starts before a grace period, and some store propagates to the -critical section's CPU before the end of the critical section but -doesn't propagate to some other CPU until after the end of the grace -period. +Guarantee by requiring that the rb relation does not contain a cycle. +Equivalently, this "rcu" axiom requires that there are no events E and +F with E ->rcu-link F ->rcu-fence E. Or to put it a third way, the +axiom requires that there are no cycles consisting of gp and rscs +alternating with rcu-link, where the number of gp links is >= the +number of rscs links. + +Justifying the axiom isn't easy, but it is in fact a valid +formalization of the Grace Period Guarantee. We won't attempt to go +through the detailed argument, but the following analysis gives a +taste of what is involved. Suppose we have a violation of the first +part of the Guarantee: A critical section starts before a grace +period, and some store propagates to the critical section's CPU before +the end of the critical section but doesn't propagate to some other +CPU until after the end of the grace period. Putting symbols to these ideas, let L and U be the rcu_read_lock() and rcu_read_unlock() fence events delimiting the critical section in question, and let S be the synchronize_rcu() fence event for the grace period. Saying that the critical section starts before S means there are events E and F where E is po-after L (which marks the start of the -critical section), E is "before" F in the sense of the link relation, -and F is po-before the grace period S: +critical section), E is "before" F in the sense of the rcu-link +relation, and F is po-before the grace period S: - L ->po E ->link F ->po S. + L ->po E ->rcu-link F ->po S. Let W be the store mentioned above, let Z come before the end of the critical section and witness that W propagates to the critical @@ -1600,16 +1652,19 @@ some event X which is po-after S. Symbolically, this amounts to: The fr link from Y to W indicates that W has not propagated to Y's CPU at the time that Y executes. From this, it can be shown (see the -discussion of the link relation earlier) that X and Z are connected by -link, yielding: +discussion of the rcu-link relation earlier) that X and Z are related +by rcu-link, yielding: + + S ->po X ->rcu-link Z ->po U. + +The formulas say that S is po-between F and X, hence F ->gp X. They +also say that Z comes before the end of the critical section and E +comes after its start, hence Z ->rscs E. From all this we obtain: - S ->po X ->link Z ->po U. + F ->gp X ->rcu-link Z ->rscs E ->rcu-link F, -These formulas say that S is po-between F and X, hence F ->gp-link Z -via X. They also say that Z comes before the end of the critical -section and E comes after its start, hence Z ->rscs-link F via E. But -now we have a forbidden cycle: F ->gp-link Z ->rscs-link F. Thus the -"rcu" axiom rules out this violation of the Grace Period Guarantee. +a forbidden cycle. Thus the "rcu" axiom rules out this violation of +the Grace Period Guarantee. For something a little more down-to-earth, let's see how the axiom works out in practice. Consider the RCU code example from above, this @@ -1635,18 +1690,18 @@ time with statement labels added to the memory access instructions: } -If r2 = 0 at the end then P0's store at X overwrites the value -that P1's load at Z reads from, so we have Z ->fre X and thus -Z ->link X. In addition, there is a synchronize_rcu() between Y and -Z, so therefore we have Y ->gp-link X. +If r2 = 0 at the end then P0's store at X overwrites the value that +P1's load at Z reads from, so we have Z ->fre X and thus Z ->rcu-link X. +In addition, there is a synchronize_rcu() between Y and Z, so therefore +we have Y ->gp Z. If r1 = 1 at the end then P1's load at Y reads from P0's store at W, -so we have W ->link Y. In addition, W and X are in the same critical -section, so therefore we have X ->rscs-link Y. +so we have W ->rcu-link Y. In addition, W and X are in the same critical +section, so therefore we have X ->rscs W. -This gives us a cycle, Y ->gp-link X ->rscs-link Y, with one gp-link -and one rscs-link, violating the "rcu" axiom. Hence the outcome is -not allowed by the LKMM, as we would expect. +Then X ->rscs W ->rcu-link Y ->gp Z ->rcu-link X is a forbidden cycle, +violating the "rcu" axiom. Hence the outcome is not allowed by the +LKMM, as we would expect. For contrast, let's see what can happen in a more complicated example: @@ -1682,15 +1737,11 @@ For contrast, let's see what can happen in a more complicated example: } If r0 = r1 = r2 = 1 at the end, then similar reasoning to before shows -that W ->rscs-link Y via X, Y ->gp-link U via Z, and U ->rscs-link W -via V. And just as before, this gives a cycle: - - W ->rscs-link Y ->gp-link U ->rscs-link W. - -However, this cycle has fewer gp-link instances than rscs-link -instances, and consequently the outcome is not forbidden by the LKMM. -The following instruction timing diagram shows how it might actually -occur: +that W ->rscs X ->rcu-link Y ->gp Z ->rcu-link U ->rscs V ->rcu-link W. +However this cycle is not forbidden, because the sequence of relations +contains fewer instances of gp (one) than of rscs (two). Consequently +the outcome is allowed by the LKMM. The following instruction timing +diagram shows how it might actually occur: P0 P1 P2 -------------------- -------------------- -------------------- diff --git a/tools/memory-model/Documentation/references.txt b/tools/memory-model/Documentation/references.txt index ba2e34c2ec3f..b177f3e4a614 100644 --- a/tools/memory-model/Documentation/references.txt +++ b/tools/memory-model/Documentation/references.txt @@ -63,15 +63,22 @@ o Shaked Flur, Susmit Sarkar, Christopher Pulte, Kyndylan Nienhuis, Principles of Programming Languages (POPL 2017). ACM, New York, NY, USA, 429–442. +o Christopher Pulte, Shaked Flur, Will Deacon, Jon French, + Susmit Sarkar, and Peter Sewell. 2018. "Simplifying ARM concurrency: + multicopy-atomic axiomatic and operational models for ARMv8". In + Proceedings of the ACM on Programming Languages, Volume 2, Issue + POPL, Article No. 19. ACM, New York, NY, USA. + Linux-kernel memory model ========================= -o Andrea Parri, Alan Stern, Luc Maranget, Paul E. McKenney, - and Jade Alglave. 2017. "A formal model of - Linux-kernel memory ordering - companion webpage". - http://moscova.inria.fr/∼maranget/cats7/linux/. (2017). [Online; - accessed 30-January-2017]. +o Jade Alglave, Luc Maranget, Paul E. McKenney, Andrea Parri, and + Alan Stern. 2018. "Frightening small children and disconcerting + grown-ups: Concurrency in the Linux kernel". In Proceedings of + the 23rd International Conference on Architectural Support for + Programming Languages and Operating Systems (ASPLOS 2018). ACM, + New York, NY, USA, 405-418. Webpage: http://diy.inria.fr/linux/. o Jade Alglave, Luc Maranget, Paul E. McKenney, Andrea Parri, and Alan Stern. 2017. "A formal kernel memory-ordering model (part 1)" diff --git a/tools/memory-model/README b/tools/memory-model/README index 0b3a5f3c9ccd..734f7feaa5dc 100644 --- a/tools/memory-model/README +++ b/tools/memory-model/README @@ -20,7 +20,7 @@ that litmus test to be exercised within the Linux kernel. REQUIREMENTS ============ -Version 7.48 of the "herd7" and "klitmus7" tools must be downloaded +Version 7.49 of the "herd7" and "klitmus7" tools must be downloaded separately: https://github.com/herd/herdtools7 diff --git a/tools/memory-model/linux-kernel.bell b/tools/memory-model/linux-kernel.bell index 432c7cf71b23..64f5740e0e75 100644 --- a/tools/memory-model/linux-kernel.bell +++ b/tools/memory-model/linux-kernel.bell @@ -5,10 +5,10 @@ * Copyright (C) 2017 Alan Stern <stern@rowland.harvard.edu>, * Andrea Parri <parri.andrea@gmail.com> * - * An earlier version of this file appears in the companion webpage for + * An earlier version of this file appeared in the companion webpage for * "Frightening small children and disconcerting grown-ups: Concurrency * in the Linux kernel" by Alglave, Maranget, McKenney, Parri, and Stern, - * which is to appear in ASPLOS 2018. + * which appeared in ASPLOS 2018. *) "Linux-kernel memory consistency model" diff --git a/tools/memory-model/linux-kernel.cat b/tools/memory-model/linux-kernel.cat index df97db03b6c2..59b5cbe6b624 100644 --- a/tools/memory-model/linux-kernel.cat +++ b/tools/memory-model/linux-kernel.cat @@ -5,10 +5,10 @@ * Copyright (C) 2017 Alan Stern <stern@rowland.harvard.edu>, * Andrea Parri <parri.andrea@gmail.com> * - * An earlier version of this file appears in the companion webpage for + * An earlier version of this file appeared in the companion webpage for * "Frightening small children and disconcerting grown-ups: Concurrency * in the Linux kernel" by Alglave, Maranget, McKenney, Parri, and Stern, - * which is to appear in ASPLOS 2018. + * which appeared in ASPLOS 2018. *) "Linux-kernel memory consistency model" @@ -100,22 +100,29 @@ let rscs = po ; crit^-1 ; po? * one but two non-rf relations, but only in conjunction with an RCU * read-side critical section. *) -let link = hb* ; pb* ; prop +let rcu-link = hb* ; pb* ; prop -(* Chains that affect the RCU grace-period guarantee *) -let gp-link = gp ; link -let rscs-link = rscs ; link +(* + * Any sequence containing at least as many grace periods as RCU read-side + * critical sections (joined by rcu-link) acts as a generalized strong fence. + *) +let rec rcu-fence = gp | + (gp ; rcu-link ; rscs) | + (rscs ; rcu-link ; gp) | + (gp ; rcu-link ; rcu-fence ; rcu-link ; rscs) | + (rscs ; rcu-link ; rcu-fence ; rcu-link ; gp) | + (rcu-fence ; rcu-link ; rcu-fence) + +(* rb orders instructions just as pb does *) +let rb = prop ; rcu-fence ; hb* ; pb* + +irreflexive rb as rcu (* - * A cycle containing at least as many grace periods as RCU read-side - * critical sections is forbidden. + * The happens-before, propagation, and rcu constraints are all + * expressions of temporal ordering. They could be replaced by + * a single constraint on an "executes-before" relation, xb: + * + * let xb = hb | pb | rb + * acyclic xb as executes-before *) -let rec rcu-path = - gp-link | - (gp-link ; rscs-link) | - (rscs-link ; gp-link) | - (rcu-path ; rcu-path) | - (gp-link ; rcu-path ; rscs-link) | - (rscs-link ; rcu-path ; gp-link) - -irreflexive rcu-path as rcu diff --git a/tools/memory-model/linux-kernel.def b/tools/memory-model/linux-kernel.def index 397e4e67e8c8..6fa3eb28d40b 100644 --- a/tools/memory-model/linux-kernel.def +++ b/tools/memory-model/linux-kernel.def @@ -1,9 +1,9 @@ // SPDX-License-Identifier: GPL-2.0+ // -// An earlier version of this file appears in the companion webpage for +// An earlier version of this file appeared in the companion webpage for // "Frightening small children and disconcerting grown-ups: Concurrency // in the Linux kernel" by Alglave, Maranget, McKenney, Parri, and Stern, -// which is to appear in ASPLOS 2018. +// which appeared in ASPLOS 2018. // ONCE READ_ONCE(X) __load{once}(X) @@ -14,14 +14,15 @@ smp_store_release(X,V) { __store{release}(*X,V); } smp_load_acquire(X) __load{acquire}(*X) rcu_assign_pointer(X,V) { __store{release}(X,V); } rcu_dereference(X) __load{once}(X) +smp_store_mb(X,V) { __store{once}(X,V); __fence{mb}; } // Fences -smp_mb() { __fence{mb} ; } -smp_rmb() { __fence{rmb} ; } -smp_wmb() { __fence{wmb} ; } -smp_mb__before_atomic() { __fence{before-atomic} ; } -smp_mb__after_atomic() { __fence{after-atomic} ; } -smp_mb__after_spinlock() { __fence{after-spinlock} ; } +smp_mb() { __fence{mb}; } +smp_rmb() { __fence{rmb}; } +smp_wmb() { __fence{wmb}; } +smp_mb__before_atomic() { __fence{before-atomic}; } +smp_mb__after_atomic() { __fence{after-atomic}; } +smp_mb__after_spinlock() { __fence{after-spinlock}; } // Exchange xchg(X,V) __xchg{mb}(X,V) @@ -34,26 +35,27 @@ cmpxchg_acquire(X,V,W) __cmpxchg{acquire}(X,V,W) cmpxchg_release(X,V,W) __cmpxchg{release}(X,V,W) // Spinlocks -spin_lock(X) { __lock(X) ; } -spin_unlock(X) { __unlock(X) ; } +spin_lock(X) { __lock(X); } +spin_unlock(X) { __unlock(X); } spin_trylock(X) __trylock(X) +spin_is_locked(X) __islocked(X) // RCU rcu_read_lock() { __fence{rcu-lock}; } -rcu_read_unlock() { __fence{rcu-unlock};} +rcu_read_unlock() { __fence{rcu-unlock}; } synchronize_rcu() { __fence{sync-rcu}; } synchronize_rcu_expedited() { __fence{sync-rcu}; } // Atomic atomic_read(X) READ_ONCE(*X) -atomic_set(X,V) { WRITE_ONCE(*X,V) ; } +atomic_set(X,V) { WRITE_ONCE(*X,V); } atomic_read_acquire(X) smp_load_acquire(X) atomic_set_release(X,V) { smp_store_release(X,V); } -atomic_add(V,X) { __atomic_op(X,+,V) ; } -atomic_sub(V,X) { __atomic_op(X,-,V) ; } -atomic_inc(X) { __atomic_op(X,+,1) ; } -atomic_dec(X) { __atomic_op(X,-,1) ; } +atomic_add(V,X) { __atomic_op(X,+,V); } +atomic_sub(V,X) { __atomic_op(X,-,V); } +atomic_inc(X) { __atomic_op(X,+,1); } +atomic_dec(X) { __atomic_op(X,-,1); } atomic_add_return(V,X) __atomic_op_return{mb}(X,+,V) atomic_add_return_relaxed(V,X) __atomic_op_return{once}(X,+,V) diff --git a/tools/memory-model/litmus-tests/.gitignore b/tools/memory-model/litmus-tests/.gitignore new file mode 100644 index 000000000000..6e2ddc54152f --- /dev/null +++ b/tools/memory-model/litmus-tests/.gitignore @@ -0,0 +1 @@ +*.litmus.out diff --git a/tools/memory-model/litmus-tests/IRIW+mbonceonces+OnceOnce.litmus b/tools/memory-model/litmus-tests/IRIW+mbonceonces+OnceOnce.litmus index 50d5db9ea983..98a3716efa37 100644 --- a/tools/memory-model/litmus-tests/IRIW+mbonceonces+OnceOnce.litmus +++ b/tools/memory-model/litmus-tests/IRIW+mbonceonces+OnceOnce.litmus @@ -7,7 +7,7 @@ C IRIW+mbonceonces+OnceOnce * between each pairs of reads. In other words, is smp_mb() sufficient to * cause two different reading processes to agree on the order of a pair * of writes, where each write is to a different variable by a different - * process? + * process? This litmus test exercises LKMM's "propagation" rule. *) {} diff --git a/tools/memory-model/litmus-tests/MP+polockmbonce+poacquiresilsil.litmus b/tools/memory-model/litmus-tests/MP+polockmbonce+poacquiresilsil.litmus new file mode 100644 index 000000000000..50f4d62bbf0e --- /dev/null +++ b/tools/memory-model/litmus-tests/MP+polockmbonce+poacquiresilsil.litmus @@ -0,0 +1,35 @@ +C MP+polockmbonce+poacquiresilsil + +(* + * Result: Never + * + * Do spinlocks combined with smp_mb__after_spinlock() provide order + * to outside observers using spin_is_locked() to sense the lock-held + * state, ordered by acquire? Note that when the first spin_is_locked() + * returns false and the second true, we know that the smp_load_acquire() + * executed before the lock was acquired (loosely speaking). + *) + +{ +} + +P0(spinlock_t *lo, int *x) +{ + spin_lock(lo); + smp_mb__after_spinlock(); + WRITE_ONCE(*x, 1); + spin_unlock(lo); +} + +P1(spinlock_t *lo, int *x) +{ + int r1; + int r2; + int r3; + + r1 = smp_load_acquire(x); + r2 = spin_is_locked(lo); + r3 = spin_is_locked(lo); +} + +exists (1:r1=1 /\ 1:r2=0 /\ 1:r3=1) diff --git a/tools/memory-model/litmus-tests/MP+polockonce+poacquiresilsil.litmus b/tools/memory-model/litmus-tests/MP+polockonce+poacquiresilsil.litmus new file mode 100644 index 000000000000..abf81e7a0895 --- /dev/null +++ b/tools/memory-model/litmus-tests/MP+polockonce+poacquiresilsil.litmus @@ -0,0 +1,34 @@ +C MP+polockonce+poacquiresilsil + +(* + * Result: Sometimes + * + * Do spinlocks provide order to outside observers using spin_is_locked() + * to sense the lock-held state, ordered by acquire? Note that when the + * first spin_is_locked() returns false and the second true, we know that + * the smp_load_acquire() executed before the lock was acquired (loosely + * speaking). + *) + +{ +} + +P0(spinlock_t *lo, int *x) +{ + spin_lock(lo); + WRITE_ONCE(*x, 1); + spin_unlock(lo); +} + +P1(spinlock_t *lo, int *x) +{ + int r1; + int r2; + int r3; + + r1 = smp_load_acquire(x); + r2 = spin_is_locked(lo); + r3 = spin_is_locked(lo); +} + +exists (1:r1=1 /\ 1:r2=0 /\ 1:r3=1) diff --git a/tools/memory-model/litmus-tests/README b/tools/memory-model/litmus-tests/README index 04096fb8b8d9..17eb9a8c222d 100644 --- a/tools/memory-model/litmus-tests/README +++ b/tools/memory-model/litmus-tests/README @@ -23,7 +23,8 @@ IRIW+mbonceonces+OnceOnce.litmus between each pairs of reads. In other words, is smp_mb() sufficient to cause two different reading processes to agree on the order of a pair of writes, where each write is to a different - variable by a different process? + variable by a different process? This litmus test is forbidden + by LKMM's propagation rule. IRIW+poonceonces+OnceOnce.litmus Test of independent reads from independent writes with nothing @@ -63,6 +64,16 @@ LB+poonceonces.litmus MP+onceassign+derefonce.litmus As below, but with rcu_assign_pointer() and an rcu_dereference(). +MP+polockmbonce+poacquiresilsil.litmus + Protect the access with a lock and an smp_mb__after_spinlock() + in one process, and use an acquire load followed by a pair of + spin_is_locked() calls in the other process. + +MP+polockonce+poacquiresilsil.litmus + Protect the access with a lock in one process, and use an + acquire load followed by a pair of spin_is_locked() calls + in the other process. + MP+polocks.litmus As below, but with the second access of the writer process and the first access of reader process protected by a lock. @@ -109,8 +120,10 @@ S+wmbonceonce+poacquireonce.litmus WRC+poonceonces+Once.litmus WRC+pooncerelease+rmbonceonce+Once.litmus - These two are members of an extension of the MP litmus-test class - in which the first write is moved to a separate process. + These two are members of an extension of the MP litmus-test + class in which the first write is moved to a separate process. + The second is forbidden because smp_store_release() is + A-cumulative in LKMM. Z6.0+pooncelock+pooncelock+pombonce.litmus Is the ordering provided by a spin_unlock() and a subsequent diff --git a/tools/memory-model/litmus-tests/WRC+pooncerelease+rmbonceonce+Once.litmus b/tools/memory-model/litmus-tests/WRC+pooncerelease+rmbonceonce+Once.litmus index 97fcbffde9a0..ad3448b941e6 100644 --- a/tools/memory-model/litmus-tests/WRC+pooncerelease+rmbonceonce+Once.litmus +++ b/tools/memory-model/litmus-tests/WRC+pooncerelease+rmbonceonce+Once.litmus @@ -5,7 +5,9 @@ C WRC+pooncerelease+rmbonceonce+Once * * This litmus test is an extension of the message-passing pattern, where * the first write is moved to a separate process. Because it features - * a release and a read memory barrier, it should be forbidden. + * a release and a read memory barrier, it should be forbidden. More + * specifically, this litmus test is forbidden because smp_store_release() + * is A-cumulative in LKMM. *) {} diff --git a/tools/memory-model/lock.cat b/tools/memory-model/lock.cat index ba4a4ec6d313..305ded17e741 100644 --- a/tools/memory-model/lock.cat +++ b/tools/memory-model/lock.cat @@ -4,46 +4,72 @@ * Copyright (C) 2017 Alan Stern <stern@rowland.harvard.edu> *) -(* Generate coherence orders and handle lock operations *) +(* + * Generate coherence orders and handle lock operations + * + * Warning: spin_is_locked() crashes herd7 versions strictly before 7.48. + * spin_is_locked() is functional from herd7 version 7.49. + *) include "cross.cat" -(* From lock reads to their partner lock writes *) -let lk-rmw = ([LKR] ; po-loc ; [LKW]) \ (po ; po) -let rmw = rmw | lk-rmw - (* - * A paired LKR must always see an unlocked value; spin_lock() calls nested - * inside a critical section (for the same lock) always deadlock. + * The lock-related events generated by herd are as follows: + * + * LKR Lock-Read: the read part of a spin_lock() or successful + * spin_trylock() read-modify-write event pair + * LKW Lock-Write: the write part of a spin_lock() or successful + * spin_trylock() RMW event pair + * UL Unlock: a spin_unlock() event + * LF Lock-Fail: a failed spin_trylock() event + * RL Read-Locked: a spin_is_locked() event which returns True + * RU Read-Unlocked: a spin_is_locked() event which returns False + * + * LKR and LKW events always come paired, like all RMW event sequences. + * + * LKR, LF, RL, and RU are read events; LKR has Acquire ordering. + * LKW and UL are write events; UL has Release ordering. + * LKW, LF, RL, and RU have no ordering properties. *) -empty ([LKW] ; po-loc ; [domain(lk-rmw)]) \ (po-loc ; [UL] ; po-loc) - as lock-nest -(* The litmus test is invalid if an LKW event is not part of an RMW pair *) -flag ~empty LKW \ range(lk-rmw) as unpaired-LKW +(* Backward compatibility *) +let RL = try RL with emptyset +let RU = try RU with emptyset -(* This will be allowed if we implement spin_is_locked() *) -flag ~empty LKR \ domain(lk-rmw) as unpaired-LKR +(* Treat RL as a kind of LF: a read with no ordering properties *) +let LF = LF | RL -(* There should be no R or W accesses to spinlocks *) -let ALL-LOCKS = LKR | LKW | UL | LF +(* There should be no ordinary R or W accesses to spinlocks *) +let ALL-LOCKS = LKR | LKW | UL | LF | RU flag ~empty [M \ IW] ; loc ; [ALL-LOCKS] as mixed-lock-accesses +(* Link Lock-Reads to their RMW-partner Lock-Writes *) +let lk-rmw = ([LKR] ; po-loc ; [LKW]) \ (po ; po) +let rmw = rmw | lk-rmw + +(* The litmus test is invalid if an LKR/LKW event is not part of an RMW pair *) +flag ~empty LKW \ range(lk-rmw) as unpaired-LKW +flag ~empty LKR \ domain(lk-rmw) as unpaired-LKR + +(* + * An LKR must always see an unlocked value; spin_lock() calls nested + * inside a critical section (for the same lock) always deadlock. + *) +empty ([LKW] ; po-loc ; [LKR]) \ (po-loc ; [UL] ; po-loc) as lock-nest + (* The final value of a spinlock should not be tested *) flag ~empty [FW] ; loc ; [ALL-LOCKS] as lock-final - (* * Put lock operations in their appropriate classes, but leave UL out of W * until after the co relation has been generated. *) -let R = R | LKR | LF +let R = R | LKR | LF | RU let W = W | LKW let Release = Release | UL let Acquire = Acquire | LKR - (* Match LKW events to their corresponding UL events *) let critical = ([LKW] ; po-loc ; [UL]) \ (po-loc ; [LKW | UL] ; po-loc) @@ -53,27 +79,48 @@ flag ~empty UL \ range(critical) as unmatched-unlock let UNMATCHED-LKW = LKW \ domain(critical) empty ([UNMATCHED-LKW] ; loc ; [UNMATCHED-LKW]) \ id as unmatched-locks - (* rfi for LF events: link each LKW to the LF events in its critical section *) let rfi-lf = ([LKW] ; po-loc ; [LF]) \ ([LKW] ; po-loc ; [UL] ; po-loc) (* rfe for LF events *) let all-possible-rfe-lf = - (* - * Given an LF event r, compute the possible rfe edges for that event - * (all those starting from LKW events in other threads), - * and then convert that relation to a set of single-edge relations. - *) - let possible-rfe-lf r = - let pair-to-relation p = p ++ 0 - in map pair-to-relation ((LKW * {r}) & loc & ext) - (* Do this for each LF event r that isn't in rfi-lf *) - in map possible-rfe-lf (LF \ range(rfi-lf)) + (* + * Given an LF event r, compute the possible rfe edges for that event + * (all those starting from LKW events in other threads), + * and then convert that relation to a set of single-edge relations. + *) + let possible-rfe-lf r = + let pair-to-relation p = p ++ 0 + in map pair-to-relation ((LKW * {r}) & loc & ext) + (* Do this for each LF event r that isn't in rfi-lf *) + in map possible-rfe-lf (LF \ range(rfi-lf)) (* Generate all rf relations for LF events *) with rfe-lf from cross(all-possible-rfe-lf) -let rf = rf | rfi-lf | rfe-lf +let rf-lf = rfe-lf | rfi-lf + +(* + * RU, i.e., spin_is_locked() returning False, is slightly different. + * We rely on the memory model to rule out cases where spin_is_locked() + * within one of the lock's critical sections returns False. + *) + +(* rfi for RU events: an RU may read from the last po-previous UL *) +let rfi-ru = ([UL] ; po-loc ; [RU]) \ ([UL] ; po-loc ; [LKW] ; po-loc) + +(* rfe for RU events: an RU may read from an external UL or the initial write *) +let all-possible-rfe-ru = + let possible-rfe-ru r = + let pair-to-relation p = p ++ 0 + in map pair-to-relation (((UL | IW) * {r}) & loc & ext) + in map possible-rfe-ru RU + +(* Generate all rf relations for RU events *) +with rfe-ru from cross(all-possible-rfe-ru) +let rf-ru = rfe-ru | rfi-ru +(* Final rf relation *) +let rf = rf | rf-lf | rf-ru (* Generate all co relations, including LKW events but not UL *) let co0 = co0 | ([IW] ; loc ; [LKW]) | diff --git a/tools/memory-model/scripts/checkalllitmus.sh b/tools/memory-model/scripts/checkalllitmus.sh new file mode 100644 index 000000000000..af0aa15ab84e --- /dev/null +++ b/tools/memory-model/scripts/checkalllitmus.sh @@ -0,0 +1,73 @@ +#!/bin/sh +# +# Run herd tests on all .litmus files in the specified directory (which +# defaults to litmus-tests) and check each file's result against a "Result:" +# comment within that litmus test. If the verification result does not +# match that specified in the litmus test, this script prints an error +# message prefixed with "^^^". It also outputs verification results to +# a file whose name is that of the specified litmus test, but with ".out" +# appended. +# +# Usage: +# sh checkalllitmus.sh [ directory ] +# +# The LINUX_HERD_OPTIONS environment variable may be used to specify +# arguments to herd, whose default is defined by the checklitmus.sh script. +# Thus, one would normally run this in the directory containing the memory +# model, specifying the pathname of the litmus test to check. +# +# This script makes no attempt to run the litmus tests concurrently. +# +# This program is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 2 of the License, or +# (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with this program; if not, you can access it online at +# http://www.gnu.org/licenses/gpl-2.0.html. +# +# Copyright IBM Corporation, 2018 +# +# Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com> + +litmusdir=${1-litmus-tests} +if test -d "$litmusdir" -a -r "$litmusdir" -a -x "$litmusdir" +then + : +else + echo ' --- ' error: $litmusdir is not an accessible directory + exit 255 +fi + +# Find the checklitmus script. If it is not where we expect it, then +# assume that the caller has the PATH environment variable set +# appropriately. +if test -x scripts/checklitmus.sh +then + clscript=scripts/checklitmus.sh +else + clscript=checklitmus.sh +fi + +# Run the script on all the litmus tests in the specified directory +ret=0 +for i in litmus-tests/*.litmus +do + if ! $clscript $i + then + ret=1 + fi +done +if test "$ret" -ne 0 +then + echo " ^^^ VERIFICATION MISMATCHES" +else + echo All litmus tests verified as was expected. +fi +exit $ret diff --git a/tools/memory-model/scripts/checklitmus.sh b/tools/memory-model/scripts/checklitmus.sh new file mode 100644 index 000000000000..e2e477472844 --- /dev/null +++ b/tools/memory-model/scripts/checklitmus.sh @@ -0,0 +1,86 @@ +#!/bin/sh +# +# Run a herd test and check the result against a "Result:" comment within +# the litmus test. If the verification result does not match that specified +# in the litmus test, this script prints an error message prefixed with +# "^^^" and exits with a non-zero status. It also outputs verification +# results to a file whose name is that of the specified litmus test, but +# with ".out" appended. +# +# Usage: +# sh checklitmus.sh file.litmus +# +# The LINUX_HERD_OPTIONS environment variable may be used to specify +# arguments to herd, which default to "-conf linux-kernel.cfg". Thus, +# one would normally run this in the directory containing the memory model, +# specifying the pathname of the litmus test to check. +# +# This program is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 2 of the License, or +# (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with this program; if not, you can access it online at +# http://www.gnu.org/licenses/gpl-2.0.html. +# +# Copyright IBM Corporation, 2018 +# +# Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com> + +litmus=$1 +herdoptions=${LINUX_HERD_OPTIONS--conf linux-kernel.cfg} + +if test -f "$litmus" -a -r "$litmus" +then + : +else + echo ' --- ' error: \"$litmus\" is not a readable file + exit 255 +fi +if grep -q '^ \* Result: ' $litmus +then + outcome=`grep -m 1 '^ \* Result: ' $litmus | awk '{ print $3 }'` +else + outcome=specified +fi + +echo Herd options: $herdoptions > $litmus.out +/usr/bin/time herd7 -o ~/tmp $herdoptions $litmus >> $litmus.out 2>&1 +grep "Herd options:" $litmus.out +grep '^Observation' $litmus.out +if grep -q '^Observation' $litmus.out +then + : +else + cat $litmus.out + echo ' ^^^ Verification error' + echo ' ^^^ Verification error' >> $litmus.out 2>&1 + exit 255 +fi +if test "$outcome" = DEADLOCK +then + echo grep 3 and 4 + if grep '^Observation' $litmus.out | grep -q 'Never 0 0$' + then + ret=0 + else + echo " ^^^ Unexpected non-$outcome verification" + echo " ^^^ Unexpected non-$outcome verification" >> $litmus.out 2>&1 + ret=1 + fi +elif grep '^Observation' $litmus.out | grep -q $outcome || test "$outcome" = Maybe +then + ret=0 +else + echo " ^^^ Unexpected non-$outcome verification" + echo " ^^^ Unexpected non-$outcome verification" >> $litmus.out 2>&1 + ret=1 +fi +tail -2 $litmus.out | head -1 +exit $ret |