============
LITMUS TESTS
============

Each subdirectory contains litmus tests that are typical to describe the
semantics of respective kernel APIs.
For more information about how to "run" a litmus test or how to generate
a kernel test module based on a litmus test, please see
tools/memory-model/README.


atomic (/atomic directory)
--------------------------

Atomic-RMW+mb__after_atomic-is-stronger-than-acquire.litmus
    Test that an atomic RMW followed by a smp_mb__after_atomic() is
    stronger than a normal acquire: both the read and write parts of
    the RMW are ordered before the subsequential memory accesses.

Atomic-RMW-ops-are-atomic-WRT-atomic_set.litmus
    Test that atomic_set() cannot break the atomicity of atomic RMWs.
    NOTE: Require herd7 7.56 or later which supports "(void)expr".

cmpxchg-fail-ordered-1.litmus
    Demonstrate that a failing cmpxchg() operation acts as a full barrier
    when followed by smp_mb__after_atomic().

cmpxchg-fail-ordered-2.litmus
    Demonstrate that a failing cmpxchg() operation acts as an acquire
    operation when followed by smp_mb__after_atomic().

cmpxchg-fail-unordered-1.litmus
    Demonstrate that a failing cmpxchg() operation does not act as a
    full barrier.

cmpxchg-fail-unordered-2.litmus
    Demonstrate that a failing cmpxchg() operation does not act as an
    acquire operation.


fs (/fs directory)
------------------

A struct file is SLAB_TYPESAFE_BY_RCU.  __fget_files_rcu() loads the
descriptor slot, takes a reference with file_ref_get(), reloads the
slot and compares, and between the first load and the increment the
file can be closed, freed and handed out again.  The tests encode the
counter as an atomic_t holding references minus one (ONEREF 0, NOREF
-1, DEAD -4), file_ref_get() as atomic_fetch_add() with the ordering
under test, file_ref_put() as atomic_fetch_sub() followed by the
cmpxchg to DEAD of __file_ref_put(), init_file() as a plain
atomic_set() and fd_install() as a release store.  The slot is an int
where only its identity matters and a pointer where a later load has
to depend on it.  The counter is a separate variable, so the address
dependency of the increment on the first load is not in the model;
that only makes the model weaker than the code, a "Never" here holds
for the code.

file-ref-get-acquire-recheck.litmus
    Demonstrates that an acquire-ordered file_ref_get() is enough for
    the recheck of __fget_files_rcu(): the full ordering of the
    decrement orders the cleared slot before the counter is set up
    again and the acquire orders the reload after the increment, so a
    lookup that increments a recycled file cannot pass the recheck with
    the old slot.

file-ref-get-relaxed-recheck.litmus
    The same with a relaxed increment; the reload can be satisfied
    before the increment and the lookup returns a file the descriptor
    never named.

file-ref-reload-dep-field.litmus
    Demonstrates that reading the file's fields through the reloaded
    pointer, as __get_file_rcu() does, orders them after the store of
    fd_install() that the reload saw: a thread that closes and reopens
    the same descriptor and gets the same file back cannot make a
    concurrent lookup read the old incarnation's f_op.

file-ref-reload-nodep-field.litmus
    The same with the fields read through the pointer of the first
    load; the field read is ordered after the increment but not after
    the reload, and a fully ordered increment does not change that.

file-ref-put-full-handoff.litmus
    Demonstrates why file_ref_put() keeps its full ordering: when the
    last put frees the file synchronously and another CPU takes it from
    the slab freelist, the fully ordered decrement orders the cleared
    slot before the free, so a lookup on a third CPU that increments
    the recycled counter cannot pass its recheck with the old slot.

file-ref-put-release-handoff.litmus
    The same with a release-ordered decrement; it orders the cleared
    slot before the decrement and not before the free, and the lookup
    can keep a reference to a recycled file for a descriptor that never
    named it.

The reference count of a mount is split into per-CPU gets and puts.  A
holder drops a reference on the fast path of mntput_no_expire() without
mount_lock, a walker in __legitimize_mnt() takes one during an RCU path
walk, and the unmounter sums the counters under mount_lock with
mnt_get_count() to decide whether it can finish the mount off without
waiting for a grace period.  The tests spell write_seqlock() out as a
spinlock, a seqcount store and smp_wmb(), read_seqbegin() and
read_seqretry() as READ_ONCE() and smp_rmb(), and the per-CPU counters
as one variable per CPU.

mnt-sum-misses-fastpath-put.litmus
    Demonstrates that the sum under mount_lock can miss a put on the
    fast path of mntput_no_expire(), which is why mntput_unmounted()
    falls back to a grace period when the count is not one.

mnt-holder-get-before-put.litmus
    Demonstrates that a fast-path put the sum counts has its get counted
    too: the smp_wmb() in mntput_no_expire() pairs with the smp_mb()
    between the puts pass and the gets pass of mnt_get_count().

mnt-holder-get-before-put-nowmb.litmus
    The same without the holder's smp_wmb(); the sum can count the put
    but not the get.

mnt-holder-get-before-put-nomb.litmus
    The same without the smp_mb() inside mnt_get_count(); an smp_mb()
    ahead of the puts pass does not stand in for it.

mnt-holder-get-before-put-getsfirst.litmus
    The same with the gets summed before the puts; the order of the two
    passes is part of the pairing.

mnt-gp-sees-fastpath-put.litmus
    Demonstrates that after the grace period of mntput_unmounted() the
    plain mntput() sees the fast-path put the sum missed, because the
    holder's read-side critical section ended before the grace period.

mnt-gp-sees-fastpath-put-sync-rcu.litmus
    The same with synchronize_rcu() in place of
    synchronize_rcu_expedited().

mnt-gp-sees-fastpath-put-nogp.litmus
    The same with an smp_mb() in place of the grace period; the put can
    still be missed.

mnt-walker-get-vs-seqcount.litmus
    Demonstrates the store buffering pairing between the increment and
    smp_mb() of __legitimize_mnt() and the seqcount store and the
    smp_mb() of mnt_get_count() under mount_lock: the walker cannot
    keep a reference to a mount the sum finishes off.

mnt-walker-get-vs-seqcount-no-outer-mb.litmus
    The same with the sum as the tree has it, without an smp_mb()
    between taking mount_lock and the sum; the smp_mb() inside
    mnt_get_count() is the one that pairs.

mnt-walker-get-vs-seqcount-nomb.litmus
    The same without the walker's smp_mb(); the walker can keep a
    reference to a freed mount.

mnt-walker-bail-sees-doomed.litmus
    Demonstrates that a walker which sees the seqcount change and reads
    ->mnt_flags under mount_lock finds MNT_DOOMED on a mount the sum
    finished off; mount_lock orders the two critical sections.

mnt-walker-bail-sees-doomed-nolock.litmus
    The same with ->mnt_flags read outside mount_lock; the walker can
    miss MNT_DOOMED.

mnt-walker-late-sees-new-pwd.litmus
    Demonstrates that a walker which starts after the sum finished a
    mount off cannot reach it through the old cwd of a holder whose put
    the sum counted: the holder orders the new fs->pwd before the put
    and the smp_mb() of mnt_get_count() orders the load of the put
    before the seqcount store the walker samples.

mnt-walker-late-sees-new-pwd-nowmb.litmus
    The same without the smp_wmb()s that order the new fs->pwd before
    the put; the walker can read the old cwd.

mnt-walker-late-sees-new-pwd-nomb.litmus
    The same without the smp_mb() inside mnt_get_count(); the walker can
    read the old cwd.

mnt-kern-unmount-holder-get-before-put.litmus
    The holder test for kern_unmount_array(), where mnt_make_shortterm()
    clears ->mnt_ns with a plain WRITE_ONCE() outside mount_lock.

mnt-kern-unmount-gp-sees-fastpath-put.litmus
    The grace period test for kern_unmount_array().


locking (/locking directory)
----------------------------

DCL-broken.litmus
    Demonstrates that double-checked locking needs more than just
    the obvious lock acquisitions and releases.

DCL-fixed.litmus
    Demonstrates corrected double-checked locking that uses
    smp_store_release() and smp_load_acquire() in addition to the
    obvious lock acquisitions and releases.

RM-broken.litmus
    Demonstrates problems with "roach motel" locking, where code is
    freely moved into lock-based critical sections.  This example also
    shows how to use the "filter" clause to discard executions that
    would be excluded by other code not modeled in the litmus test.
    Note also that this "roach motel" optimization is emulated by
    physically moving P1()'s two reads from x under the lock.

    What is a roach motel?  This is from an old advertisement for
    a cockroach trap, much later featured in one of the "Men in
    Black" movies.  "The roaches check in.  They don't check out."

RM-fixed.litmus
    The counterpart to RM-broken.litmus, showing P0()'s two loads from
    x safely outside of the critical section.


RCU (/rcu directory)
--------------------

MP+onceassign+derefonce.litmus (under tools/memory-model/litmus-tests/)
    Demonstrates the use of rcu_assign_pointer() and rcu_dereference() to
    ensure that an RCU reader will not see pre-initialization garbage.

RCU+sync+read.litmus
RCU+sync+free.litmus
    Both the above litmus tests demonstrate the RCU grace period guarantee
    that an RCU read-side critical section can never span a grace period.

SRCU (/srcu directory)
----------------------

SRCU-fastpath-anchor-before-scan.litmus
    This models the synchronize_srcu_atomic() fastpath with the
    grace-period anchor ordered before the lock-counter scan.  This
    ordering prevents readers that existed before the grace period
    from being missed by the scan.  See
    SRCU-fastpath-scan-before-anchor.litmus for the reversed
    ordering.

SRCU-fastpath-scan-before-anchor.litmus
    This models the synchronize_srcu_atomic() fastpath with the
    lock-counter scan ordered before the grace-period anchor.  This
    permits the scan to miss readers that existed before the grace
    period, violating the SRCU grace-period guarantee.  See
    SRCU-fastpath-anchor-before-scan.litmus for the opposite
    ordering.
