[concurrency-interest] Does StampedLock need a releaseFence in theory?

Hans Boehm boehm at acm.org
Wed Jul 13 20:53:21 EDT 2016


[Sorry about the delay]

That paper clearly paid too little attention to the writer side of the
seqlock implementation.  It has an outright (boring, unrelated) bug, which
was minimally fixed in the slides at
http://safari.ece.cmu.edu/MSPC2012/slides_posters/boehm-slides.pdf . (This
bug convinced me that the C++ compare_exchange semantics that update the
expected value may not have been the best thing since sliced bread.)

The writer code also assumes that data updates use plain C++ assignments to
atomic variables, which are sequentially consistent. Thus it dodges all
further memory ordering issues in the writer.  At some cost. But the
assumption throughout is that the writer is not performance critical.

If the data updates are allowed to use relaxed operations, then Martin's
concern is entirely valid. I believe it is valid in practice, not just in
theory.  The easiest way to convince yourself is to consider the case in
which compareAndSet is in fact implemented with a lock.  Using "roach motel
semantics", the data stores are allowed to move into the compareAndSet
critical section, and become visible before the compareAndSet update
itself. Oops.

An ARMv8 compareAndSet operation (using only acquire and release
operations, not dmb, as it should be implemented) will behave like the
lock-based one in this respect.  I think the current code above is
incorrect on ARMv8 (barring compensating pessimizations elsewhere).

On Wed, Jun 15, 2016 at 6:53 PM, Martin Buchholz <martinrb at google.com>
wrote:

> Somehow I ended up re-reading Hans' excellent
> Can Seqlocks Get Along With Programming Language Memory Models?
> http://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf
> and was wondering about why there wasn't a symmetrical releaseFence to
> pair up with the acquireFence.  The proof in section 5 says
>
> """
> The correctness argument is basically as above, but the
> happens-before chain becomes:
> Initial update of seq by w is sequenced before
> Write to datan by w synchronizes with
> The acquire fence in r (since preceding operation saw
> write, 29.8 p4 in [11]) is sequenced before
> final read of seq by r
> """
>
> But if the write to datan is a relaxed write (as would be written by
> programmers accustomed to using plain writes in a critical section), then I
> don't see the "Write to datan by w synchronizes with ..."  and I wonder
> whether for theoretical correctness one needs something like:
>
> --- src/main/java/util/concurrent/locks/StampedLock.java 9 Jun 2016
> 00:32:02 -0000 1.60
> +++ src/main/java/util/concurrent/locks/StampedLock.java 16 Jun 2016
> 01:30:09 -0000
> @@ -349,9 +347,14 @@
>      public long tryWriteLock() {
>          long s, next;
> -        return ((((s = state) & ABITS) == 0L &&
> -                 STATE.compareAndSet(this, s, next = s + WBIT)) ?
> -                next : 0L);
> +        if (((s = state) & ABITS) == 0L &&
> +            STATE.compareAndSet(this, s, next = s + WBIT)) {
> +            // Necessary in theory, but not in practice?
> +            VarHandle.releaseFence();
> +            return next;
> +        } else {
> +            return 0L;
> +        }
>      }
>
> In practice it's probably not an issue because CASes are implemented using
> full fences, and the JIT cannot reorder the dependent write.
>
> BTW, with jdk9 VarHandles seqlocks can be implemented without Unsafe, so a
> "new release" of the Seqlocks paper might be useful.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20160713/bb70f6f5/attachment.html>


More information about the Concurrency-interest mailing list