Skip to content

Instantly share code, notes, and snippets.

@djspiewak
Forked from RaasAhsan/Main.java
Created November 10, 2020 22:00
Show Gist options
  • Save djspiewak/28049aaed3775b4c0a762883dd61c2f2 to your computer and use it in GitHub Desktop.
Save djspiewak/28049aaed3775b4c0a762883dd61c2f2 to your computer and use it in GitHub Desktop.
minimized ARM memory barrier violation
import java.util.concurrent.atomic.*;
import java.util.concurrent.*;
public class Main {
private static ExecutorService executor = Executors.newFixedThreadPool(2);
private static int iterations = 10000000;
public static class Runner {
// writes to canceled happen before a CAS on suspended
// reads on canceled happen after a CAS on suspended
private boolean canceled = false;
// an optimistic lock. false == locked, true == unlocked
private AtomicBoolean suspended = new AtomicBoolean(false);
private volatile boolean result = false;
private CountDownLatch latch = new CountDownLatch(1);
public void start() {
// start two tasks that synchronize on suspended and canceled
// this is a minimized version of a synchronization mechanism in cats effect
Future<?> f1 = executor.submit(() -> {
try {
latch.await();
} catch (Exception ex) {
ex.printStackTrace();
}
// assumption: this task already has the lock
// release the lock
suspended.compareAndSet(false, true);
if (canceled) {
// double-check, the other thread may have set canceled but failed the CAS check,
// so we'll try to reacquire the lock
if (suspended.compareAndSet(true, false)) {
result = true;
}
}
});
Future<?> f2 = executor.submit(() -> {
try {
latch.await();
} catch (Exception ex) {
ex.printStackTrace();
}
canceled = true;
// attempt to acquire the lock to set result.
// regardless of whether the CAS succeeds or not, the write to canceled should be published
if (suspended.compareAndSet(true, false)) {
result = true;
}
});
// signal threads to proceed
latch.countDown();
try {
// wait for tasks to complete
f1.get();
f2.get();
} catch (Exception ex) {
ex.printStackTrace();
}
// after both tasks have completed, result should be true
if (result != true) {
System.out.println("STUCK");
System.exit(0);
}
}
}
public static void main(String[] args) {
for (int i = 0; i < iterations; i++) {
Runner runner = new Runner();
runner.start();
}
System.exit(0);
}
}
@viktorklang
Copy link

import java.util.concurrent.atomic.*;
import java.util.concurrent.*;

public class Main {
    private static ExecutorService executor = Executors.newFixedThreadPool(2);
    private static int iterations = 10000000;
  
    public static class Runner {
        // writes to canceled happen before a CAS on suspended
        // reads on canceled happen after a CAS on suspended
        private boolean canceled = false;
        // an optimistic lock. false == locked, true == unlocked
        private AtomicBoolean suspended = new AtomicBoolean(false);
    
        private volatile boolean result = false;
        private CountDownLatch latch = new CountDownLatch(1);
    
        public void start() {
            // start two tasks that synchronize on suspended and canceled
            // this is a minimized version of a synchronization mechanism in cats effect
            Future<?> f1 = executor.submit(() -> {
                try {
                    latch.await();
                } catch (Exception ex) {
                    ex.printStackTrace();
                }
                
                // assumption: this task already has the lock

                // release the lock
                suspended.set(true);
                if (canceled) {
                    // double-check, the other thread may have set canceled but failed the CAS check,
                    // so we'll try to reacquire the lock
                    if (suspended.getAndSet(false)) {
                        result = true;
                    }
                }
            });

            Future<?> f2 = executor.submit(() -> {
                try {
                    latch.await();
                } catch (Exception ex) {
                    ex.printStackTrace();
                }

                // Viktor: Missing read barrier here?

                canceled = true;
                // attempt to acquire the lock to set result.
                // regardless of whether the CAS succeeds or not, the write to canceled should be published
                if (suspended.getAndSet(false)) {
                    result = true;
                }
            });

            // signal threads to proceed
            latch.countDown();

            try {
                // wait for tasks to complete
                f1.get();
                f2.get();
            } catch (Exception ex) {
                ex.printStackTrace();
            }

            // after both tasks have completed, result should be true
            if (result != true) {
                System.out.println("STUCK");
                System.exit(0);
            }
        }
    }
    
    public static void main(String[] args) {
        for (int i = 0; i < iterations; i++) {
            Runner runner = new Runner();
            runner.start();
        }
        System.exit(0);
    }
}

@djspiewak
Copy link
Author

@viktorklang Check out the original gist (by Raas). A few folks swung by and explained the exact problem. It is in fact the CAS! If a CAS succeeds, then it has the effect of a volatile write. If it fails, it only has the effect of a volatile read, and thus the canceled write isn’t always published!

This is actually undocumented in Java 8. The introduction of VarHandle clarified this semantic.

@viktorklang
Copy link

@djspiewak Yep—then that's the thing I suspected initially :) the assumption that a failed cas causes a write barrier :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment