Change last_dependent_accesses for atomics

[nkaretnikov]

Consider the following program (x is a shared variable, the SeqCst
ordering is assumed):

• thread 0 (main): store 0 in x
• thread 1: store 1 in x
• thread 2: store 2 in x
• thread 0 (main): wait for thread 1; wait for thread 2; load x

Without this change, concurrent writes are considered independent, so
Loom fails to explore store 2 followed by store 1.

For orderings other than SeqCst, this is likely to introduce
redundant dependencies, resulting in more thread interleavings being
explored than necessary.

[nkaretnikov]

Example program:

use loom;
use loom::thread;
use loom::sync::atomic::AtomicUsize;
use loom::sync::Arc;

use std::sync::atomic::Ordering::SeqCst;

fn main() {
    loom::model(|| {
        let x = Arc::new(AtomicUsize::new(0));

        let x1 = x.clone();
        let th1 = thread::spawn(move || {
            x1.store(1, SeqCst);
        });

        let x2 = x.clone();
        let th2 = thread::spawn(move || {
            x2.store(2, SeqCst);
        });

        th1.join().unwrap();
        th2.join().unwrap();

        println!("result: {:?}", x.load(SeqCst));
    });
}

Should print these messages when executed:

result: 1
result: 2

[nkaretnikov]

For SeqCst, depending just on last_store should do, but it breaks these tests (in
tests/atomic_relaxed.rs):

test check_ordering_invalid_1 ... FAILED
test check_ordering_invalid_2 ... FAILED

So this patch considers last_load as well.

[nkaretnikov]

Forgot to check if this has any effect on tests in Tokio. Investigating, will report back.

[carllerche]

The current implementation made the (obviously incorrect) assumption that atomic objects were always acquire / release. When using acquire / release, then concurrent stores are independent.

While this change will result in redundant paths being explored when using acquire / release atomics, it should not result in incorrect behavior. It will fix atomics used with SeqCst ordering.

Thanks for catching this 👍

[carllerche]

@nkaretnikov let me know when you validate the change w/ Tokio and I can merge.

[nkaretnikov]

Rebased my Loom branch on top of the current master (and force-pushed).

Made these changes in Tokio:

diff --git a/tokio-sync/Cargo.toml b/tokio-sync/Cargo.toml
index bb2fd607..2672159b 100644
--- a/tokio-sync/Cargo.toml
+++ b/tokio-sync/Cargo.toml
@@ -36 +36 @@ env_logger = { version = "0.6", default-features = false }
-loom = { version = "0.2.1", features = ["futures"] }
+loom = { path = "../../loom", features = ["futures"] }
diff --git a/tokio/Cargo.toml b/tokio/Cargo.toml
index 569a3fe7..9d4b49f3 100644
--- a/tokio/Cargo.toml
+++ b/tokio/Cargo.toml
@@ -127 +127 @@ libc = "0.2"
-loom = { version = "0.2.11", features = ["futures", "checkpoint"] }
+loom = { path = "../../loom", features = ["futures", "checkpoint"] }

Ran this (as done in ci/azure-loom.yml):

LOOM_MAX_PREEMPTIONS=2 RUSTFLAGS="--cfg loom" cargo test --lib --release ; echo $?

No failures reported. Is this how you typically test it?

[carllerche]

Yep, that looks good 👍

No need to rebase in the future. I can do that when the PR merges 👍

[nkaretnikov]

@carllerche Okay, noted!