StampedLock happens-before with tryOptimisticRead()

classic Classic list List threaded Threaded
23 messages Options
12
Reply | Threaded
Open this post in threaded view
|

StampedLock happens-before with tryOptimisticRead()

Dr Heinz M. Kabutz
Hi,

in my latest newsletter, I showed an IntList that was protected with a
StampedLock.  http://www.javaspecialists.eu/archive/Issue242.html  It
was more an educational exercise than a class you'd want to use to store
ints :-)

In my first version of this class, I made size volatile, but Alex Snaps
suggested that I could simply call tryOptimisticRead() before reading
the size field.  Since inside tryOptimisticRead() we are doing a
volatile read of "state", I believe that we are correct with the code
below.  However, there were some objections to this code on Twitter
""Volatile read == synchronized" will keep biting us forever. The
comment is broken."
https://twitter.com/VladimirSitnikv/status/793364258658607104 "

I based my comment on JCiP and the JMM FAQ, so I think it is correct.  
There was a follow-on comment that there was no happens-before guarantee
with tryOptimisticRead(), but IMHO there would have to be, otherwise it
would be possible to read stale fields into local variables.  
StampedLock (and similar constructs) would be fundamentally broken if
this does not work.

import java.util.*;
import java.util.concurrent.locks.*;

public class IntList {
  private static final int OPTIMISTIC_SPIN = 3;
  private final StampedLock sl = new StampedLock();
  private int[] arr = new int[10];
  private int size = 0;

  public int size() {
    // volatile read, same as entering a synchronized block
    sl.tryOptimisticRead();
    return this.size;
  }

  public int get(int index) {
    for (int i = 0; i < OPTIMISTIC_SPIN; i++) {
      long stamp = sl.tryOptimisticRead();
      int size = this.size;
      int[] arr = this.arr;
      if (index < arr.length) {
        int r = arr[index];
        if (sl.validate(stamp)) {
          rangeCheck(index, size);
          return r;
        }
      }
    }
    long stamp = sl.readLock();
    try {
      rangeCheck(index, this.size);
      return this.arr[index];
    } finally {
      sl.unlockRead(stamp);
    }
  }

  public void trimToSize() {
    long stamp = sl.tryOptimisticRead();
    int currentSize = size;
    int[] currentArr = arr;
    if (sl.validate(stamp)) {
      // fast optimistic read to accelerate trimToSize() when
      // there is no work to do
      if (currentSize == currentArr.length) return;
    }
    stamp = sl.writeLock();
    try {
      if (size < arr.length) {
        arr = Arrays.copyOf(arr, size);
      }
    } finally {
      sl.unlockWrite(stamp);
    }
  }

  public boolean add(int e) {
    long stamp = sl.writeLock();
    try {
      if (size + 1 > arr.length)
        arr = Arrays.copyOf(arr, size + 10);

      arr[size++] = e;
      return true;
    } finally {
      sl.unlockWrite(stamp);
    }
  }

  // just to illustrate how an upgrade could be coded
  public int removeWithUpgrade(int index) {
    long stamp = sl.readLock();
    try {
      while (true) {
        rangeCheck(index, size);
        long writeStamp = sl.tryConvertToWriteLock(stamp);
        if (writeStamp == 0) {
          sl.unlockRead(stamp);
          stamp = sl.writeLock();
        } else {
          stamp = writeStamp;
          return doActualRemove(index);
        }
      }
    } finally {
      sl.unlock(stamp);
    }
  }

  public int remove(int index) {
    long stamp = sl.writeLock();
    try {
      rangeCheck(index, size);
      return doActualRemove(index);
    } finally {
      sl.unlock(stamp);
    }
  }

  private int doActualRemove(int index) {
    int oldValue = arr[index];

    int numMoved = size - index - 1;
    if (numMoved > 0)
      System.arraycopy(arr, index + 1, arr, index, numMoved);
    arr[--size] = 0;

    return oldValue;
  }

  private static void rangeCheck(int index, int size) {
    if (index >= size)
      throw new IndexOutOfBoundsException(
          "Index: " + index + ", Size: " + size);
  }
}

Regards

Heinz
--
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion since 2005
JavaOne Rock Star Speaker 2012
http://www.javaspecialists.eu
Tel: +30 69 75 595 262
Skype: kabutz

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: StampedLock happens-before with tryOptimisticRead()

Nitsan Wakart-2
Hi,
Even if the code is correct the comment is misleading. Volatile loads
are not the same as syncronized block entry. They may work in particular
usecases as a cheap replacement, but that is context sensitive. The
"volatile read of a field written in a synchronized block" idiom is
appropriate in this case if size was volatile, but that cannot be
generalized as the comment suggests. (E.g. Size read is not volatile,
this implies for instance that if I were to change it to a long this
code will be broken. If I were to add writes to the mix they can get
reordered etc)

But I don't believe the code is correct. Because the value returned by
tryOptimisticRead is never used it can be eliminated after inlining, at
that point the fence/barrier is also notionally gone. See here:

https://shipilev.net/blog/2016/close-encounters-of-jmm-kind/#wishful-unobserved-volatiles

Cheers,

Nitsan


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: StampedLock happens-before with tryOptimisticRead()

Alex Otenko
Graal’s behaviour in that link is not correct. The comment there simply says that it is likely to cause you problems, even though formally the barriers should have stayed.

Alex

> On 1 Nov 2016, at 14:37, Nitsan Wakart <[hidden email]> wrote:
>
> Hi,
> Even if the code is correct the comment is misleading. Volatile loads are not the same as syncronized block entry. They may work in particular usecases as a cheap replacement, but that is context sensitive. The "volatile read of a field written in a synchronized block" idiom is appropriate in this case if size was volatile, but that cannot be generalized as the comment suggests. (E.g. Size read is not volatile, this implies for instance that if I were to change it to a long this code will be broken. If I were to add writes to the mix they can get reordered etc)
>
> But I don't believe the code is correct. Because the value returned by tryOptimisticRead is never used it can be eliminated after inlining, at that point the fence/barrier is also notionally gone. See here:
>
> https://shipilev.net/blog/2016/close-encounters-of-jmm-kind/#wishful-unobserved-volatiles
>
> Cheers,
>
> Nitsan
>
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: StampedLock happens-before with tryOptimisticRead()

Nitsan Wakart-2
Can you provide a pointer to the JMM or other sources? I'm not sure
which comment you refer to.

I can't see clear rules around the behaviour of eliminated volatile
accesses expanded on in JMM or cookbook, but I could easily have missed
something.

Thanks


On 01/11/2016 17:07, Alex Otenko wrote:
> Graal’s behaviour in that link is not correct. The comment there simply says that it is likely to cause you problems, even though formally the barriers should have stayed.
>
> Alex
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: StampedLock happens-before with tryOptimisticRead()

Alex Otenko
I am referring to “But we certainly would not like to throw compilers under the bus and say this is forbidden.”

If elimination of barriers destroys synchronizes-with edges, it should not be allowed. The write itself is futile, so it’s ok to eliminate it, but the h-b edges are not.

That particular idiom,

        x = 1;
        h.GREAT_BARRIER_REEF = h.GREAT_BARRIER_REEF;
        y = 1;

is broken for other reasons, and would permit to reorder the reads/writes like so:

        tmp =  h.GREAT_BARRIER_REEF;
        x = 1;
        y = 1;
        h.GREAT_BARRIER_REEF = tmp;

But complete elimination of the barriers would be wrong.


Alex


> On 1 Nov 2016, at 15:42, Nitsan Wakart <[hidden email]> wrote:
>
> Can you provide a pointer to the JMM or other sources? I'm not sure which comment you refer to.
>
> I can't see clear rules around the behaviour of eliminated volatile accesses expanded on in JMM or cookbook, but I could easily have missed something.
>
> Thanks
>
>
> On 01/11/2016 17:07, Alex Otenko wrote:
>> Graal’s behaviour in that link is not correct. The comment there simply says that it is likely to cause you problems, even though formally the barriers should have stayed.
>>
>> Alex

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: StampedLock happens-before with tryOptimisticRead()

Henri Tremblay
In reply to this post by Nitsan Wakart-2
Alex is referring to Alexsey's post https://shipilev.net/blog/2016/close-encounters-of-jmm-kind/#wishful-unobserved-volatiles

There is a comment about Graal. Telling that nothing prevents a volatile assignment from disappearing if unused (and so the barrier). Even though C2 doesn't do it right now.

On 1 November 2016 at 11:42, Nitsan Wakart <[hidden email]> wrote:
Can you provide a pointer to the JMM or other sources? I'm not sure which comment you refer to.

I can't see clear rules around the behaviour of eliminated volatile accesses expanded on in JMM or cookbook, but I could easily have missed something.

Thanks


On 01/11/2016 17:07, Alex Otenko wrote:
Graal’s behaviour in that link is not correct. The comment there simply says that it is likely to cause you problems, even though formally the barriers should have stayed.

Alex
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: StampedLock happens-before with tryOptimisticRead()

Alex Snaps-2
Am I getting you right Alex, that since we don't `StampedLock.validate()` (or otherwise _use_) the status returned by `.tryOptimisticRead()` the barrier may disappear as the code gets optimized? So that the read/write to the volatile status within StampedLock doesn't provide enough guarantees... 

On Tue, Nov 1, 2016 at 12:10 PM Henri Tremblay <[hidden email]> wrote:
Alex is referring to Alexsey's post https://shipilev.net/blog/2016/close-encounters-of-jmm-kind/#wishful-unobserved-volatiles

There is a comment about Graal. Telling that nothing prevents a volatile assignment from disappearing if unused (and so the barrier). Even though C2 doesn't do it right now.

On 1 November 2016 at 11:42, Nitsan Wakart <[hidden email]> wrote:
Can you provide a pointer to the JMM or other sources? I'm not sure which comment you refer to.

I can't see clear rules around the behaviour of eliminated volatile accesses expanded on in JMM or cookbook, but I could easily have missed something.

Thanks


On 01/11/2016 17:07, Alex Otenko wrote:
Graal’s behaviour in that link is not correct. The comment there simply says that it is likely to cause you problems, even though formally the barriers should have stayed.

Alex
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
--
Alex Snaps
Twitter: @alexsnaps

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: StampedLock happens-before with tryOptimisticRead()

Alex Otenko
In my opinion Nitsan’s comment about the validity of the algorithm and the caveats is correct. But I disagree with the suggestion that the barriers could/should be optimized for unused reads. The article Aleksey posted in his blog is talking about a different case, where there may be room for optimization - eg through reordering of reads.

But if Graal completely removes the barriers (rather than move them around) in cases like these, it is not correct.

Alex

On 1 Nov 2016, at 16:18, Alex Snaps <[hidden email]> wrote:

Am I getting you right Alex, that since we don't `StampedLock.validate()` (or otherwise _use_) the status returned by `.tryOptimisticRead()` the barrier may disappear as the code gets optimized? So that the read/write to the volatile status within StampedLock doesn't provide enough guarantees... 

On Tue, Nov 1, 2016 at 12:10 PM Henri Tremblay <[hidden email]> wrote:
Alex is referring to Alexsey's post https://shipilev.net/blog/2016/close-encounters-of-jmm-kind/#wishful-unobserved-volatiles

There is a comment about Graal. Telling that nothing prevents a volatile assignment from disappearing if unused (and so the barrier). Even though C2 doesn't do it right now.

On 1 November 2016 at 11:42, Nitsan Wakart <[hidden email]> wrote:
Can you provide a pointer to the JMM or other sources? I'm not sure which comment you refer to.

I can't see clear rules around the behaviour of eliminated volatile accesses expanded on in JMM or cookbook, but I could easily have missed something.

Thanks


On 01/11/2016 17:07, Alex Otenko wrote:
Graal’s behaviour in that link is not correct. The comment there simply says that it is likely to cause you problems, even though formally the barriers should have stayed.

Alex
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
--
Alex Snaps
Twitter: @alexsnaps
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: StampedLock happens-before with tryOptimisticRead()

Alex Snaps-2
So as per my understanding this code is currently (still) correct... But I also I can see how people get confused by synchronized == volatile. 
Now, forgive my ignorance, but with Graal, we're talking about a new revision of the JMM then, is that right? 
Piggybacking on volatile read/write, afaik, has been widely used out there... This would loosen the contract, right? 



On Tue, Nov 1, 2016 at 12:36 PM Alex Otenko <[hidden email]> wrote:
In my opinion Nitsan’s comment about the validity of the algorithm and the caveats is correct. But I disagree with the suggestion that the barriers could/should be optimized for unused reads. The article Aleksey posted in his blog is talking about a different case, where there may be room for optimization - eg through reordering of reads.

But if Graal completely removes the barriers (rather than move them around) in cases like these, it is not correct.


Alex

On 1 Nov 2016, at 16:18, Alex Snaps <[hidden email]> wrote:

Am I getting you right Alex, that since we don't `StampedLock.validate()` (or otherwise _use_) the status returned by `.tryOptimisticRead()` the barrier may disappear as the code gets optimized? So that the read/write to the volatile status within StampedLock doesn't provide enough guarantees... 

On Tue, Nov 1, 2016 at 12:10 PM Henri Tremblay <[hidden email]> wrote:
Alex is referring to Alexsey's post https://shipilev.net/blog/2016/close-encounters-of-jmm-kind/#wishful-unobserved-volatiles

There is a comment about Graal. Telling that nothing prevents a volatile assignment from disappearing if unused (and so the barrier). Even though C2 doesn't do it right now.

On 1 November 2016 at 11:42, Nitsan Wakart <[hidden email]> wrote:
Can you provide a pointer to the JMM or other sources? I'm not sure which comment you refer to.

I can't see clear rules around the behaviour of eliminated volatile accesses expanded on in JMM or cookbook, but I could easily have missed something.

Thanks


On 01/11/2016 17:07, Alex Otenko wrote:
Graal’s behaviour in that link is not correct. The comment there simply says that it is likely to cause you problems, even though formally the barriers should have stayed.

Alex
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
--
Alex Snaps
Twitter: @alexsnaps
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

--
Alex Snaps
Twitter: @alexsnaps

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: StampedLock happens-before with tryOptimisticRead()

Martin Buchholz-3
In reply to this post by Alex Otenko
Using and implementing StampedLock is tricky.  There were implementation changes in jdk9.
See previous discussion 
Does StampedLock need a releaseFence in theory?
which did lead to an implementation change.

I keep thinking of adding "No one is smart enough to use StampedLock correctly." to the javadoc, but we haven't quite gone that far.

 *  <li><b>Optimistic Reading.</b> Method {@link #tryOptimisticRead}
 *   returns a non-zero stamp only if the lock is not currently held
 *   in write mode. Method {@link #validate} returns true if the lock
 *   has not been acquired in write mode since obtaining a given
 *   stamp.  This mode can be thought of as an extremely weak version
 *   of a read-lock, that can be broken by a writer at any time.  The
 *   use of optimistic mode for short read-only code segments often
 *   reduces contention and improves throughput.  However, its use is
 *   inherently fragile.  Optimistic read sections should only read
 *   fields and hold them in local variables for later use after
 *   validation. Fields read while in optimistic mode may be wildly
 *   inconsistent, so usage applies only when you are familiar enough
 *   with data representations to check consistency and/or repeatedly
 *   invoke method {@code validate()}.  For example, such steps are
 *   typically required when first reading an object or array
 *   reference, and then accessing one of its fields, elements or
 *   methods.


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: StampedLock happens-before with tryOptimisticRead()

Martin Buchholz-3
In reply to this post by Dr Heinz M. Kabutz


On Tue, Nov 1, 2016 at 5:17 AM, Dr Heinz M. Kabutz <[hidden email]> wrote:

In my first version of this class, I made size volatile, but Alex Snaps suggested that I could simply call tryOptimisticRead() before reading the size field.  

It is the intent that fields protected by a StampedLock need not be volatile, but then for example out-of-thin-air reads of longs becomes possible.  You should be OK if you always validate the stamp before using any of the values read.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: StampedLock happens-before with tryOptimisticRead()

Dr Heinz M. Kabutz
Martin Buchholz wrote:
On Tue, Nov 1, 2016 at 5:17 AM, Dr Heinz M. Kabutz <[hidden email]> wrote:

In my first version of this class, I made size volatile, but Alex Snaps suggested that I could simply call tryOptimisticRead() before reading the size field.  

It is the intent that fields protected by a StampedLock need not be volatile, but then for example out-of-thin-air reads of longs becomes possible.  You should be OK if you always validate the stamp before using any of the values read.
If all we want is to ensure visibility of the size field (an int), do we need a validate() or is a simple tryOptimisticRead() sufficient?

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: StampedLock happens-before with tryOptimisticRead()

Aleksey Shipilev-3
In reply to this post by Dr Heinz M. Kabutz
On 11/01/2016 01:17 PM, Dr Heinz M. Kabutz wrote:
> In my first version of this class, I made size volatile, but Alex Snaps
> suggested that I could simply call tryOptimisticRead() before reading
> the size field.  Since inside tryOptimisticRead() we are doing a
> volatile read of "state", I believe that we are correct with the code
> below.

Trick question: can a correct (yet not very efficient) implementation of
StampedLock.tryOptimisticRead() simply return zero (e.g. "lock is busy,
no optimistic reads for you, go away")? If so, the whole argument goes
down the sink, as there are obviously no memory effects whatsoever, and
this is a data race.

I do think that a correct size() method should validate the stamp, e.g.:

public int size() {
  long stamp = sl.tryOptimisticRead();
  int size = this.size;
  if (sl.validate(stamp)) {
    return size;
  } else {
    ... go full read lock ...
  }
}

...which plays nicely into suggested StampedLock use patterns. If
StampedLock wanted to advertise memory consistency properties for
optimistic reads, it would have to talk about stamp validation, IMO --
because otherwise it has to mandate the particular implementation of
never-a-noop tryOptimisticRead().

Having that in mind, peeking into StampedLock implementation is cheating
;) This does not rely on specification, but only on the actual
implementation -- which is fragile, as we all know.

> However, there were some objections to this code on Twitter
> ""Volatile read == synchronized" will keep biting us forever. The
> comment is broken."
> https://twitter.com/VladimirSitnikv/status/793364258658607104 "

Well... kinda. As far as the memory effects are concerned, volatile and
synchronized are pretty symmetrical. But, synchronized also gives you
mutual exclusion, which makes it different enough to break "==".

How many times you have seen people blindly removing synchronized for
piggybacking on volatiles, and then realizing their mutex guarantees are
gone? That's usually fun to watch. If you are doing the educational
example, I would try to not to perpetuate this easy to make mistake.

> I based my comment on JCiP and the JMM FAQ, so I think it is
> correct. There was a follow-on comment that there was no
> happens-before guarantee with tryOptimisticRead(), but IMHO there
> would have to be, otherwise it would be possible to read stale fields
> into local variables. StampedLock (and similar constructs) would be
> fundamentally broken if this does not work.

This is why you *need* to call validate(stamp) -- in the case of no-op
tryOptimisticRead, it would tell you have read garbage. Coding to the
actual implementation, not to the spec, would always be fundamentally
broken.

Now, to the original question: does volatile read of SL.state suffices
to provide happens-before-s? Yes, it does, by accident.

Thanks,
-Aleksey


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: StampedLock happens-before with tryOptimisticRead()

Dr Heinz M. Kabutz
Aleksey Shipilev wrote:
> On 11/01/2016 01:17 PM, Dr Heinz M. Kabutz wrote:
>
> Now, to the original question: does volatile read of SL.state suffices
> to provide happens-before-s? Yes, it does, by accident.
>
> Thanks,
> -Aleksey
Phew, glad I'm not mad :-)

And yes, you are 100% correct.  I did peep into the StampedLock
implementation and used that to make my decision.
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: StampedLock happens-before with tryOptimisticRead()

Aleksey Shipilev-3
On 11/01/2016 07:31 PM, Dr Heinz M. Kabutz wrote:
> Aleksey Shipilev wrote:
>> On 11/01/2016 01:17 PM, Dr Heinz M. Kabutz wrote:
>>
>> Now, to the original question: does volatile read of SL.state suffices
>> to provide happens-before-s? Yes, it does, by accident.
>>
>> Thanks,
>> -Aleksey
> Phew, glad I'm not mad :-)

Teaching people to peek into the implementation and making the
correctness arguments based on the implementation alone *is* mad in my
book ;)

But I really should expand. Should read:

-Yes, it does, by accident.
+Yes, it does, sometimes, by accident.

The trouble with the "happens-before" reasoning here is that you can
certainly argue there are executions where SL.unlock() --hb-->
SL.tryOptimisticRead(), but you *also* have to prove there are no other
interesting executions where the read of some $size *in progress* is racy.

The deal with optimistic reads is that they *are* in some linear order
with the rest of the updates under the lock. stamps provide that linear
versioning, and validate(stamp) enforces that you have actually seen the
"latest" version of the state protected by the lock, and advises you to
ignore the garbage you read, if you got in the unlucky spot.

Motivating example requires a stupidly excessive thing during the add():
not the "size++", but "size += 2; size--;" plus hand-wrist compiler into
not collapsing the updates" [1]. Then, this happens:

IntList il = ..;

Thread 1:
  il.add(1); // happens under write lock

Thread 2:
  // Naked half-optimisic read; we don't validate the stamp, and
  // so return with untrusted $size in hands, and it can be the write
  // in progress...
  int r1 = il.size(); // reads 2; <-- WTF, a transient result?
  int r2 = il.size(); // reads 1;

Notice that formally the second read can be justified by the execution
where "volatile write in SL.writeLock()" --sw/hb--> "volatile read in
tryOptimisticRead()". But the first read is completely racy!

Notice two things:
 a) this would not happen if size() validated the stamp. It would then
figure the update under writeLock is happening, and dealt with it
accordingly;
 b) volatile size would not help either -- so much for "volatile ==
synchronized" again, mutual exclusion is not something to ignore;

The goal for a good lock is to provide mutual exclusion with readers, so
that no transient result is ever visible. In other words, you want a
linearizable primitive...

Thanks,
-Aleksey

[1] http://cr.openjdk.java.net/~shade/scratch/UnwarrantedOptimismRead.java


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: StampedLock happens-before with tryOptimisticRead()

Dr Heinz M. Kabutz
Aleksey Shipilev wrote:
On 11/01/2016 07:31 PM, Dr Heinz M. Kabutz wrote:
  
Aleksey Shipilev wrote:
    
On 11/01/2016 01:17 PM, Dr Heinz M. Kabutz wrote:

Now, to the original question: does volatile read of SL.state suffices
to provide happens-before-s? Yes, it does, by accident.

Thanks,
-Aleksey
      
Phew, glad I'm not mad :-)
    

Teaching people to peek into the implementation and making the
correctness arguments based on the implementation alone *is* mad in my
book ;)

But I really should expand. Should read:

-Yes, it does, by accident.
+Yes, it does, sometimes, by accident.

The trouble with the "happens-before" reasoning here is that you can
certainly argue there are executions where SL.unlock() --hb-->
SL.tryOptimisticRead(), but you *also* have to prove there are no other
interesting executions where the read of some $size *in progress* is racy.

The deal with optimistic reads is that they *are* in some linear order
with the rest of the updates under the lock. stamps provide that linear
versioning, and validate(stamp) enforces that you have actually seen the
"latest" version of the state protected by the lock, and advises you to
ignore the garbage you read, if you got in the unlucky spot.

Motivating example requires a stupidly excessive thing during the add():
not the "size++", but "size += 2; size--;" plus hand-wrist compiler into
not collapsing the updates" [1]. Then, this happens:

IntList il = ..;

Thread 1:
  il.add(1); // happens under write lock

Thread 2:
  // Naked half-optimisic read; we don't validate the stamp, and
  // so return with untrusted $size in hands, and it can be the write
  // in progress...
  int r1 = il.size(); // reads 2; <-- WTF, a transient result?
  int r2 = il.size(); // reads 1;

Notice that formally the second read can be justified by the execution
where "volatile write in SL.writeLock()" --sw/hb--> "volatile read in
tryOptimisticRead()". But the first read is completely racy!

Notice two things:
 a) this would not happen if size() validated the stamp. It would then
figure the update under writeLock is happening, and dealt with it
accordingly;
 b) volatile size would not help either -- so much for "volatile ==
synchronized" again, mutual exclusion is not something to ignore;

The goal for a good lock is to provide mutual exclusion with readers, so
that no transient result is ever visible. In other words, you want a
linearizable primitive...

Thanks,
-Aleksey

[1] http://cr.openjdk.java.net/~shade/scratch/UnwarrantedOptimismRead.jav
In my IntList implementation though, we just do size++ or size--, not size+=2, followed by size--.   I don't mind reading reading a slightly dirty field, since by the time I return from the method, the size could have changed anyway.  Thus absolute precision is not important in this case (since it can't anyway be guaranteed by this type of class).

Someone wrote to me that the current code is not linearizable, thus his argument was that you would imagine that x <= y <= z in the following code:

// Thread 1:
sl.tryOptimisticRead();
int x = il.size;
sl.tryOptimisticRead();
int y = il.size;
sl.tryOptimisticRead();
int z = il.size;
System.out.println("z="+z+"  y="+y+"  x="+x);


could get re-ordered into:

// Thread 1:
sl.tryOptimisticRead();
sl.tryOptimisticRead();
sl.tryOptimisticRead();
int x = il.size;
int y = il.size;
int z = il.size;
System.out.println("z="+z+"  y="+y+"  x="+x);

and further into:

// Thread 1:
sl.tryOptimisticRead();
sl.tryOptimisticRead();
sl.tryOptimisticRead();
System.out.println("z="+il.size+"  y="+il.size+"  x="+il.size);


So the relation of x <= y <= z might not hold according to his linearizability argument.
 
Because of the way that tryOptimisticRead() is written, I believe that those calls can't be reordered so it can't happen.  His argument is that making size volatile guarantees happens-before and thus the relationship will always hold.  However, there is nothing in the JavaDocs of tryOptimisticRead() that would indicate that happens-before is guaranteed, but it would be difficult to use if it wasn't offering this to us.

For the record, I never wrote or implied that volatile == synchronizeds.  I wrote "volatile read, same as entering a synchronized block" - which I meant from a memory visibility perspective, most definitely not mutual exclusion, etc..  I could have been a bit more explicit and said that, but I was trying to squeeze the line onto 65 characters and assumed that my readers would be smart enough to realize what I was saying :-)  I'll fix it in the online version, as I'm not sure who will read it :-D

Heinz












_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: StampedLock happens-before with tryOptimisticRead()

Alex Snaps-2
In reply to this post by Aleksey Shipilev-3
Actually there is somewhat of a "similar" race in this current implementation, if I'm not mistaken:
Since we increment size prior to inserting the entry in the backing array, it could well be we observe inconsistent state of `IntList`.
If for some reason size gets incremented and say the mutative thread gets unscheduled "for longer", the entry wouldn't yet be installed, and it wouldn't be "get"able (as the SL protects that ok, yet size() would reflect the "to be size" once the mutation eventually completes). I guess this would be fixable by incrementing size only after the element was inserted... 


On Tue, Nov 1, 2016 at 3:22 PM Aleksey Shipilev <[hidden email]> wrote:
On 11/01/2016 07:31 PM, Dr Heinz M. Kabutz wrote:
> Aleksey Shipilev wrote:
>> On 11/01/2016 01:17 PM, Dr Heinz M. Kabutz wrote:
>>
>> Now, to the original question: does volatile read of SL.state suffices
>> to provide happens-before-s? Yes, it does, by accident.
>>
>> Thanks,
>> -Aleksey
> Phew, glad I'm not mad :-)

Teaching people to peek into the implementation and making the
correctness arguments based on the implementation alone *is* mad in my
book ;)

But I really should expand. Should read:

-Yes, it does, by accident.
+Yes, it does, sometimes, by accident.

The trouble with the "happens-before" reasoning here is that you can
certainly argue there are executions where SL.unlock() --hb-->
SL.tryOptimisticRead(), but you *also* have to prove there are no other
interesting executions where the read of some $size *in progress* is racy.

The deal with optimistic reads is that they *are* in some linear order
with the rest of the updates under the lock. stamps provide that linear
versioning, and validate(stamp) enforces that you have actually seen the
"latest" version of the state protected by the lock, and advises you to
ignore the garbage you read, if you got in the unlucky spot.

Motivating example requires a stupidly excessive thing during the add():
not the "size++", but "size += 2; size--;" plus hand-wrist compiler into
not collapsing the updates" [1]. Then, this happens:

IntList il = ..;

Thread 1:
  il.add(1); // happens under write lock

Thread 2:
  // Naked half-optimisic read; we don't validate the stamp, and
  // so return with untrusted $size in hands, and it can be the write
  // in progress...
  int r1 = il.size(); // reads 2; <-- WTF, a transient result?
  int r2 = il.size(); // reads 1;

Notice that formally the second read can be justified by the execution
where "volatile write in SL.writeLock()" --sw/hb--> "volatile read in
tryOptimisticRead()". But the first read is completely racy!

Notice two things:
 a) this would not happen if size() validated the stamp. It would then
figure the update under writeLock is happening, and dealt with it
accordingly;
 b) volatile size would not help either -- so much for "volatile ==
synchronized" again, mutual exclusion is not something to ignore;

The goal for a good lock is to provide mutual exclusion with readers, so
that no transient result is ever visible. In other words, you want a
linearizable primitive...

Thanks,
-Aleksey

[1] http://cr.openjdk.java.net/~shade/scratch/UnwarrantedOptimismRead.java

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
--
Alex Snaps
Twitter: @alexsnaps

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: StampedLock happens-before with tryOptimisticRead()

Dr Heinz M. Kabutz
OK, you've convinced me Alex & Aleks.  My simple rule is that if there is an invariant across multiple fields, then volatile is not appropriate.  This is indeed the case here.  So if we have code like this:

Thread 1:
while(list.size() < 100) ;
list.get(100);

Thread 2:
for(int i=0; i<10000; i++) {
  list.add(i);
}

Then Thread 1 could still get an IndexOutOfBoundsException.

Volatile would not help either unfortunately.

Back to the boring old, but correct, algorithm :-)
Regards

Heinz
-- 
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion since 2005
JavaOne Rock Star Speaker 2012
http://www.javaspecialists.eu
Tel: +30 69 75 595 262
Skype: kabutz


Alex Snaps wrote:
Actually there is somewhat of a "similar" race in this current implementation, if I'm not mistaken:
Since we increment size prior to inserting the entry in the backing array, it could well be we observe inconsistent state of `IntList`.
If for some reason size gets incremented and say the mutative thread gets unscheduled "for longer", the entry wouldn't yet be installed, and it wouldn't be "get"able (as the SL protects that ok, yet size() would reflect the "to be size" once the mutation eventually completes). I guess this would be fixable by incrementing size only after the element was inserted... 


On Tue, Nov 1, 2016 at 3:22 PM Aleksey Shipilev <[hidden email]> wrote:
On 11/01/2016 07:31 PM, Dr Heinz M. Kabutz wrote:
> Aleksey Shipilev wrote:
>> On 11/01/2016 01:17 PM, Dr Heinz M. Kabutz wrote:
>>
>> Now, to the original question: does volatile read of SL.state suffices
>> to provide happens-before-s? Yes, it does, by accident.
>>
>> Thanks,
>> -Aleksey
> Phew, glad I'm not mad :-)

Teaching people to peek into the implementation and making the
correctness arguments based on the implementation alone *is* mad in my
book ;)

But I really should expand. Should read:

-Yes, it does, by accident.
+Yes, it does, sometimes, by accident.

The trouble with the "happens-before" reasoning here is that you can
certainly argue there are executions where SL.unlock() --hb-->
SL.tryOptimisticRead(), but you *also* have to prove there are no other
interesting executions where the read of some $size *in progress* is racy.

The deal with optimistic reads is that they *are* in some linear order
with the rest of the updates under the lock. stamps provide that linear
versioning, and validate(stamp) enforces that you have actually seen the
"latest" version of the state protected by the lock, and advises you to
ignore the garbage you read, if you got in the unlucky spot.

Motivating example requires a stupidly excessive thing during the add():
not the "size++", but "size += 2; size--;" plus hand-wrist compiler into
not collapsing the updates" [1]. Then, this happens:

IntList il = ..;

Thread 1:
  il.add(1); // happens under write lock

Thread 2:
  // Naked half-optimisic read; we don't validate the stamp, and
  // so return with untrusted $size in hands, and it can be the write
  // in progress...
  int r1 = il.size(); // reads 2; <-- WTF, a transient result?
  int r2 = il.size(); // reads 1;

Notice that formally the second read can be justified by the execution
where "volatile write in SL.writeLock()" --sw/hb--> "volatile read in
tryOptimisticRead()". But the first read is completely racy!

Notice two things:
 a) this would not happen if size() validated the stamp. It would then
figure the update under writeLock is happening, and dealt with it
accordingly;
 b) volatile size would not help either -- so much for "volatile ==
synchronized" again, mutual exclusion is not something to ignore;

The goal for a good lock is to provide mutual exclusion with readers, so
that no transient result is ever visible. In other words, you want a
linearizable primitive...

Thanks,
-Aleksey

[1] http://cr.openjdk.java.net/~shade/scratch/UnwarrantedOptimismRead.java

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
--
Alex Snaps
Twitter: @alexsnaps

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: StampedLock happens-before with tryOptimisticRead()

Dr Heinz M. Kabutz
Or I could follow the CLQ approach and just add a JavaDoc comment:

"Thus, this method is typically not very useful in concurrent applications."
Regards

Heinz
-- 
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion since 2005
JavaOne Rock Star Speaker 2012
http://www.javaspecialists.eu
Tel: +30 69 75 595 262
Skype: kabutz


Dr Heinz M. Kabutz wrote:
OK, you've convinced me Alex & Aleks.  My simple rule is that if there is an invariant across multiple fields, then volatile is not appropriate.  This is indeed the case here.  So if we have code like this:

Thread 1:
while(list.size() < 100) ;
list.get(100);

Thread 2:
for(int i=0; i<10000; i++) {
  list.add(i);
}

Then Thread 1 could still get an IndexOutOfBoundsException.

Volatile would not help either unfortunately.

Back to the boring old, but correct, algorithm :-)
Regards

Heinz
-- 
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion since 2005
JavaOne Rock Star Speaker 2012
http://www.javaspecialists.eu
Tel: +30 69 75 595 262
Skype: kabutz
  


Alex Snaps wrote:
Actually there is somewhat of a "similar" race in this current implementation, if I'm not mistaken:
Since we increment size prior to inserting the entry in the backing array, it could well be we observe inconsistent state of `IntList`.
If for some reason size gets incremented and say the mutative thread gets unscheduled "for longer", the entry wouldn't yet be installed, and it wouldn't be "get"able (as the SL protects that ok, yet size() would reflect the "to be size" once the mutation eventually completes). I guess this would be fixable by incrementing size only after the element was inserted... 


On Tue, Nov 1, 2016 at 3:22 PM Aleksey Shipilev <[hidden email]> wrote:
On 11/01/2016 07:31 PM, Dr Heinz M. Kabutz wrote:
> Aleksey Shipilev wrote:
>> On 11/01/2016 01:17 PM, Dr Heinz M. Kabutz wrote:
>>
>> Now, to the original question: does volatile read of SL.state suffices
>> to provide happens-before-s? Yes, it does, by accident.
>>
>> Thanks,
>> -Aleksey
> Phew, glad I'm not mad :-)

Teaching people to peek into the implementation and making the
correctness arguments based on the implementation alone *is* mad in my
book ;)

But I really should expand. Should read:

-Yes, it does, by accident.
+Yes, it does, sometimes, by accident.

The trouble with the "happens-before" reasoning here is that you can
certainly argue there are executions where SL.unlock() --hb-->
SL.tryOptimisticRead(), but you *also* have to prove there are no other
interesting executions where the read of some $size *in progress* is racy.

The deal with optimistic reads is that they *are* in some linear order
with the rest of the updates under the lock. stamps provide that linear
versioning, and validate(stamp) enforces that you have actually seen the
"latest" version of the state protected by the lock, and advises you to
ignore the garbage you read, if you got in the unlucky spot.

Motivating example requires a stupidly excessive thing during the add():
not the "size++", but "size += 2; size--;" plus hand-wrist compiler into
not collapsing the updates" [1]. Then, this happens:

IntList il = ..;

Thread 1:
  il.add(1); // happens under write lock

Thread 2:
  // Naked half-optimisic read; we don't validate the stamp, and
  // so return with untrusted $size in hands, and it can be the write
  // in progress...
  int r1 = il.size(); // reads 2; <-- WTF, a transient result?
  int r2 = il.size(); // reads 1;

Notice that formally the second read can be justified by the execution
where "volatile write in SL.writeLock()" --sw/hb--> "volatile read in
tryOptimisticRead()". But the first read is completely racy!

Notice two things:
 a) this would not happen if size() validated the stamp. It would then
figure the update under writeLock is happening, and dealt with it
accordingly;
 b) volatile size would not help either -- so much for "volatile ==
synchronized" again, mutual exclusion is not something to ignore;

The goal for a good lock is to provide mutual exclusion with readers, so
that no transient result is ever visible. In other words, you want a
linearizable primitive...

Thanks,
-Aleksey

[1] http://cr.openjdk.java.net/~shade/scratch/UnwarrantedOptimismRead.java

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
--
Alex Snaps
Twitter: @alexsnaps

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: StampedLock happens-before with tryOptimisticRead()

Alex Otenko
In reply to this post by Alex Snaps-2
You need a definition of a “consistent” size().

Like, “if the list only grows, then a value at location size()-1 can always be read”. If so, then size() must have the validate() call, etc, like in get().

Alex

On 1 Nov 2016, at 20:02, Alex Snaps <[hidden email]> wrote:

Actually there is somewhat of a "similar" race in this current implementation, if I'm not mistaken:
Since we increment size prior to inserting the entry in the backing array, it could well be we observe inconsistent state of `IntList`.
If for some reason size gets incremented and say the mutative thread gets unscheduled "for longer", the entry wouldn't yet be installed, and it wouldn't be "get"able (as the SL protects that ok, yet size() would reflect the "to be size" once the mutation eventually completes). I guess this would be fixable by incrementing size only after the element was inserted... 


On Tue, Nov 1, 2016 at 3:22 PM Aleksey Shipilev <[hidden email]> wrote:
On 11/01/2016 07:31 PM, Dr Heinz M. Kabutz wrote:
> Aleksey Shipilev wrote:
>> On 11/01/2016 01:17 PM, Dr Heinz M. Kabutz wrote:
>>
>> Now, to the original question: does volatile read of SL.state suffices
>> to provide happens-before-s? Yes, it does, by accident.
>>
>> Thanks,
>> -Aleksey
> Phew, glad I'm not mad :-)

Teaching people to peek into the implementation and making the
correctness arguments based on the implementation alone *is* mad in my
book ;)

But I really should expand. Should read:

-Yes, it does, by accident.
+Yes, it does, sometimes, by accident.

The trouble with the "happens-before" reasoning here is that you can
certainly argue there are executions where SL.unlock() --hb-->
SL.tryOptimisticRead(), but you *also* have to prove there are no other
interesting executions where the read of some $size *in progress* is racy.

The deal with optimistic reads is that they *are* in some linear order
with the rest of the updates under the lock. stamps provide that linear
versioning, and validate(stamp) enforces that you have actually seen the
"latest" version of the state protected by the lock, and advises you to
ignore the garbage you read, if you got in the unlucky spot.

Motivating example requires a stupidly excessive thing during the add():
not the "size++", but "size += 2; size--;" plus hand-wrist compiler into
not collapsing the updates" [1]. Then, this happens:

IntList il = ..;

Thread 1:
  il.add(1); // happens under write lock

Thread 2:
  // Naked half-optimisic read; we don't validate the stamp, and
  // so return with untrusted $size in hands, and it can be the write
  // in progress...
  int r1 = il.size(); // reads 2; <-- WTF, a transient result?
  int r2 = il.size(); // reads 1;

Notice that formally the second read can be justified by the execution
where "volatile write in SL.writeLock()" --sw/hb--> "volatile read in
tryOptimisticRead()". But the first read is completely racy!

Notice two things:
 a) this would not happen if size() validated the stamp. It would then
figure the update under writeLock is happening, and dealt with it
accordingly;
 b) volatile size would not help either -- so much for "volatile ==
synchronized" again, mutual exclusion is not something to ignore;

The goal for a good lock is to provide mutual exclusion with readers, so
that no transient result is ever visible. In other words, you want a
linearizable primitive...

Thanks,
-Aleksey

[1] http://cr.openjdk.java.net/~shade/scratch/UnwarrantedOptimismRead.java

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
--
Alex Snaps
Twitter: @alexsnaps
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
12