Hans Boehm on Reader-Writer Locks

This time we have a cool talk from Hans Boehm on Reader-Writer Locks:
http://safari.ece.cmu.edu/MSPC2012/slides_posters/boehm-slides.pdf
unfortunately, no video, just the slides, but they are insightful enough to deserve its own post.

In case you didn't notice, the "SeqLock" that he refers to, is the same kind of mechanism that is used in Java by the StampedLock.tryOptimisticRead() and StampedLock.validate().
From his slides, it looks like this approach is broken, which I am forced to agree after looking at his presentation... but does that mean that StampedLock is broken?



If we look at the code in StampedLock we see the following:

    /**

     * Returns a stamp that can later be validated, or zero

     * if exclusively locked.

     *

     * @return a stamp, or zero if exclusively locked

     */

    public long tryOptimisticRead() {

        long s;

        return (((s = state) & WBIT) == 0L) ? (s & SBITS) : 0L;

    }

    /**

     * Returns true if the lock has not been exclusively acquired

     * since issuance of the given stamp. Always returns false if the

     * stamp is zero. Always returns true if the stamp represents a

     * currently held lock. Invoking this method with a value not

     * obtained from {@link #tryOptimisticRead} or a locking method

     * for this lock has no defined effect or result.

     *

     * @param stamp a stamp

     * @return {@code true} if the lock has not been exclusively acquired

     * since issuance of the given stamp; else false

     */

    public boolean validate(long stamp) {

        U.loadFence();

        return (stamp & SBITS) == (state & SBITS);

    }

notice that there is a load-fence in validate(), and no store-fence, which in my mind, and apparently Hans Boehm's as well, means that the code inside a block of tryOptimisticRead()/validate() can escape down, out of the critical section.

The problem with validate() is, at the compiler level, any instruction above validate() may be re-ordered and placed after it, because the guarantee on the JVM memory model allows instructions to "pass down" from a loadFence(), but not "pass up". This means that the appropriate fence should be a storeFence().


The answer to this conundrum can be seen here http://openjdk.java.net/jeps/171

/**
 * Ensures lack of reordering of loads before the fence
 * with loads or stores after the fence.
 */
void loadFence();

/**
 * Ensures lack of reordering of stores before the fence
 * with loads or stores after the fence.
 */
void storeFence();

As it so happens, I thought that a loadFence() in Java was the same as an acquire-barrier in C/C++, but from the description on the comments, it is something else altogether. You see, an acquire-barrier allows normal load and store instructions to pass from above to below the barrier, but this description is something different. The loadFence() prevents load instructions from passing from above to below the fence, and the storeFence() prevents store instructions from passing from above to below the fence.

In the StampedLock you should only have load instructions inside a block of tryOptimisticRead()/validate() because it is meant to the a read-only operation, and therefore, it is fine to use the loadFence() function to avoid re-ordering. This is in fact a kind of optimization that only works because we are guaranteed to only have load instructions (for globally visible variables).

So no, StampedLock is not broken, but Hans Boehm message is strong: be very careful with this kind of approaches.

For more info,  you can take a look at his paper "Can Seqlocks Get Along With Programming Language Memory Models?"