[jmm-dev] weakCompareAndSet memory semantics

[Martin Buchholz]

It's time for me to understand this. Perhaps by explaining it to
others in public?

On a LL/SC platform with spurious failures, strong cas has to be
implemented in a loop

boolean strong_cas(address, expect, update) {
  for (;;) {
    if (load_linked(address) != expect) return false;
    if (store_conditional(address, update)) return true;
  }
}

while weak cas can do the straightforward

boolean weak_cas(address, expect, update) {
    return load_linked(address) == expect && store_conditional(address, update);
}

If the store_conditional in strong_cas fails, it's probably because of
true contention and not a spurious failure, so the extra load_linked
and compare on retry is very likely wasted effort.  Especially
because, unlike C++, we don't return the value we read to the caller,
so they will probably uselessly re-read.  Hotspot could optimize away
the useless read, but I would be surprised if it does.

So we should rewrite every cas loop to use weak cas!  Except, to muddy
the waters ...
There's two kinds of weakness - spurious failure, and relaxed memory order.
The "weak cas" methods in Unsafe.java have no documentation, so we
don't know what kind of weakness!
The old public methods in j.u.c.atomic have documentation, but they
are weak in two different ways!
"""May fail spuriously and does not provide ordering guarantees"""
https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/atomic/AtomicLong.html#weakCompareAndSet-long-long-
but we (probably) want a variant that "may fail spuriously" but still
provides sequential consistency, for use in our CAS loops.