Happens before and stampedlocks

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

Happens before and stampedlocks

JSR166 Concurrency mailing list
Dear sirs and madams


Please accept my humble respects.


Please let me know if stampedlock class guarantees any happens before relationship.   Yes or no.    Kindly provide some reading resources on this subject

Sincerely
Sudhakar Krsna

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

Re: Happens before and stampedlocks

JSR166 Concurrency mailing list
 Hi Sudhakar,

I understand that this question is specifically about the optimistic read (because HB for read/write stamped lock is obvious).

Optimistic read does provide a HB between the previous (in synchronization order) release of a write lock and a successful optimistic read. This is also obvious, btw, because optimistic read is essentially a volatile read, and release of the write lock has a volatile write to the same field. 

The problem with optimistic reads is that neither tryOptimisticRead nor validate methods have a volatile write, thus allowing data races with subsequent (again, in synchronization order) acquire actions of the write lock (and as a result with writes happening under those write locks). This is the reason why we can only safely read data before (in program order) calling validate method, and not after it. OpenJDK 11 solves this problem (removes such data races for reads inside tryOptimisticRead/validate block) by introducing VarHandle.acquireFence() into validate method before actually validating the stamp.

A more detailed and very good explanation is here:
"Can Seqlocks Get Along With Programming Language Memory Models?" http://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf

Regards,
Valentin
LinkedIn   GitHub   YouTube


On Tue, 23 Oct 2018 at 10:05, <[hidden email]> wrote:
Send Concurrency-interest mailing list submissions to
        [hidden email]

To subscribe or unsubscribe via the World Wide Web, visit
        http://cs.oswego.edu/mailman/listinfo/concurrency-interest
or, via email, send a message with subject or body 'help' to
        [hidden email]

You can reach the person managing the list at
        [hidden email]

When replying, please edit your Subject line so it is more specific
than "Re: Contents of Concurrency-interest digest..."


Today's Topics:

   1. Happens before and stampedlocks (Sudhakar Govindavajhala)


----------------------------------------------------------------------

Message: 1
Date: Mon, 22 Oct 2018 23:21:36 -0400
From: Sudhakar Govindavajhala <[hidden email]>
To: [hidden email]
Subject: [concurrency-interest] Happens before and stampedlocks
Message-ID:
        <[hidden email]>
Content-Type: text/plain; charset="utf-8"

Dear sirs and madams


Please accept my humble respects.


Please let me know if stampedlock class guarantees any happens before
relationship.   Yes or no.    Kindly provide some reading resources on this
subject

Sincerely
Sudhakar Krsna
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20181022/0d7d662f/attachment-0001.html>

------------------------------

Subject: Digest Footer

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


------------------------------

End of Concurrency-interest Digest, Vol 164, Issue 28
*****************************************************

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

Re: Happens before and stampedlocks

JSR166 Concurrency mailing list
We "should" have more memory model level docs in StampedLock.
We "should" say that only those who have completely understood 
"Can Seqlocks Get Along With Programming Language Memory Models?"
are qualified to use optimistic reads.

But we're likely to run into human deadlocks trying to come up with wording.

On Tue, Oct 23, 2018 at 9:24 AM, Valentin Kovalenko via Concurrency-interest <[hidden email]> wrote:
 Hi Sudhakar,

I understand that this question is specifically about the optimistic read (because HB for read/write stamped lock is obvious).

Optimistic read does provide a HB between the previous (in synchronization order) release of a write lock and a successful optimistic read. This is also obvious, btw, because optimistic read is essentially a volatile read, and release of the write lock has a volatile write to the same field. 

The problem with optimistic reads is that neither tryOptimisticRead nor validate methods have a volatile write, thus allowing data races with subsequent (again, in synchronization order) acquire actions of the write lock (and as a result with writes happening under those write locks). This is the reason why we can only safely read data before (in program order) calling validate method, and not after it. OpenJDK 11 solves this problem (removes such data races for reads inside tryOptimisticRead/validate block) by introducing VarHandle.acquireFence() into validate method before actually validating the stamp.

A more detailed and very good explanation is here:
"Can Seqlocks Get Along With Programming Language Memory Models?" http://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf

Regards,
Valentin
LinkedIn   GitHub   YouTube


On Tue, 23 Oct 2018 at 10:05, <[hidden email]> wrote:
Send Concurrency-interest mailing list submissions to
        [hidden email]

To subscribe or unsubscribe via the World Wide Web, visit
        http://cs.oswego.edu/mailman/listinfo/concurrency-interest
or, via email, send a message with subject or body 'help' to
        [hidden email]

You can reach the person managing the list at
        [hidden email]

When replying, please edit your Subject line so it is more specific
than "Re: Contents of Concurrency-interest digest..."


Today's Topics:

   1. Happens before and stampedlocks (Sudhakar Govindavajhala)


----------------------------------------------------------------------

Message: 1
Date: Mon, 22 Oct 2018 23:21:36 -0400
From: Sudhakar Govindavajhala <[hidden email]>
To: [hidden email]
Subject: [concurrency-interest] Happens before and stampedlocks
Message-ID:
        <[hidden email]>
Content-Type: text/plain; charset="utf-8"


Dear sirs and madams


Please accept my humble respects.


Please let me know if stampedlock class guarantees any happens before
relationship.   Yes or no.    Kindly provide some reading resources on this
subject

Sincerely
Sudhakar Krsna
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20181022/0d7d662f/attachment-0001.html>

------------------------------

Subject: Digest Footer

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


------------------------------

End of Concurrency-interest Digest, Vol 164, Issue 28
*****************************************************

_______________________________________________
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: Happens before and stampedlocks

JSR166 Concurrency mailing list

I’d be in favor of removing API’s that can only be understood by reading a ten-page conference paper or journal article.

But how much knowledge should documentation really presuppose? (Perhaps an understanding of “Java Concurrency in Practice”?)

 

Seriously, I’d be interested to hear what guidelines people follow (consciously or as a matter of habit) when writing the docs.

 

From: Concurrency-interest [mailto:[hidden email]] On Behalf Of Martin Buchholz via Concurrency-interest
Sent: Tuesday, October 23, 2018 7:13 PM
To: Valentin Kovalenko
Cc: concurrency-interest
Subject: Re: [concurrency-interest] Happens before and stampedlocks

 

We "should" have more memory model level docs in StampedLock.

We "should" say that only those who have completely understood 

"Can Seqlocks Get Along With Programming Language Memory Models?"

are qualified to use optimistic reads.

 

But we're likely to run into human deadlocks trying to come up with wording.

 

On Tue, Oct 23, 2018 at 9:24 AM, Valentin Kovalenko via Concurrency-interest <[hidden email]> wrote:

 Hi Sudhakar,

 

I understand that this question is specifically about the optimistic read (because HB for read/write stamped lock is obvious).

 

Optimistic read does provide a HB between the previous (in synchronization order) release of a write lock and a successful optimistic read. This is also obvious, btw, because optimistic read is essentially a volatile read, and release of the write lock has a volatile write to the same field. 

 

The problem with optimistic reads is that neither tryOptimisticRead nor validate methods have a volatile write, thus allowing data races with subsequent (again, in synchronization order) acquire actions of the write lock (and as a result with writes happening under those write locks). This is the reason why we can only safely read data before (in program order) calling validate method, and not after it. OpenJDK 11 solves this problem (removes such data races for reads inside tryOptimisticRead/validate block) by introducing VarHandle.acquireFence() into validate method before actually validating the stamp.

 

A more detailed and very good explanation is here:

"Can Seqlocks Get Along With Programming Language Memory Models?" http://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf


Regards,

Valentin

LinkedIn   GitHub   YouTube

 

On Tue, 23 Oct 2018 at 10:05, <[hidden email]> wrote:

Send Concurrency-interest mailing list submissions to
        [hidden email]

To subscribe or unsubscribe via the World Wide Web, visit
        http://cs.oswego.edu/mailman/listinfo/concurrency-interest
or, via email, send a message with subject or body 'help' to
        [hidden email]

You can reach the person managing the list at
        [hidden email]

When replying, please edit your Subject line so it is more specific
than "Re: Contents of Concurrency-interest digest..."


Today's Topics:

   1. Happens before and stampedlocks (Sudhakar Govindavajhala)


----------------------------------------------------------------------

Message: 1
Date: Mon, 22 Oct 2018 23:21:36 -0400
From: Sudhakar Govindavajhala <[hidden email]>
To: [hidden email]
Subject: [concurrency-interest] Happens before and stampedlocks
Message-ID:
        <[hidden email]>
Content-Type: text/plain; charset="utf-8"



Dear sirs and madams


Please accept my humble respects.


Please let me know if stampedlock class guarantees any happens before
relationship.   Yes or no.    Kindly provide some reading resources on this
subject

Sincerely
Sudhakar Krsna

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20181022/0d7d662f/attachment-0001.html>

------------------------------

Subject: Digest Footer

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


------------------------------

End of Concurrency-interest Digest, Vol 164, Issue 28
*****************************************************


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

 


Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt, Germany – Registergericht/Commercial register: Darmstadt HRB 1562 - Vorstand/Management Board: Sanjay Brahmawar (Vorsitzender/Chairman), Eric Duffaut, Dr. Wolfram Jost, Arnd Zinnhardt, Dr. Stefan Sigg; - Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas Bereczky - http://www.softwareag.com


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

Re: Happens before and stampedlocks

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
hi all

I wrote privately to Valentin that my interest is not in optimistic reads.   My interest is in plain read and write locks.

Valentin wrote as follows:


what is the basis for this statement?
Lock interface (https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/locks/Lock.html) specifies this in "Memory Synchronization" paragraph. Since both ReentrantReadWriteLock.ReadLock and ReentrantReadWriteLock.WriteLock implement Lock interface, that specification is also applied here.

With StampedLock lock the docs, unfortunately, docs are less clear. StampedLock does not implement Lock interface and has no mentions of memory synchronization effects. However, it has methods asReadLock/asWriteLock which return plain Lock views of this StampedLock in which the Lock.lock() method is mapped to readLock()/writeLock(), and similarly for other methods. So since asReadLock/asWriteLock just map methods of StamedLock to methods of Lock interface, we can infer that StampedLock provides the same memory synchronization effects for read/write locks. This is all we have in the current docs. Everything else comes from common sense and the knowledge about the implementation.



Thanks
Sudhakar

On Tue, Oct 23, 2018, 12:27 PM Valentin Kovalenko via Concurrency-interest <[hidden email] wrote:
 Hi Sudhakar,

I understand that this question is specifically about the optimistic read (because HB for read/write stamped lock is obvious).

Optimistic read does provide a HB between the previous (in synchronization order) release of a write lock and a successful optimistic read. This is also obvious, btw, because optimistic read is essentially a volatile read, and release of the write lock has a volatile write to the same field. 

The problem with optimistic reads is that neither tryOptimisticRead nor validate methods have a volatile write, thus allowing data races with subsequent (again, in synchronization order) acquire actions of the write lock (and as a result with writes happening under those write locks). This is the reason why we can only safely read data before (in program order) calling validate method, and not after it. OpenJDK 11 solves this problem (removes such data races for reads inside tryOptimisticRead/validate block) by introducing VarHandle.acquireFence() into validate method before actually validating the stamp.

A more detailed and very good explanation is here:
"Can Seqlocks Get Along With Programming Language Memory Models?" http://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf

Regards,
Valentin
LinkedIn   GitHub   YouTube


On Tue, 23 Oct 2018 at 10:05, <[hidden email]> wrote:
Send Concurrency-interest mailing list submissions to
        [hidden email]

To subscribe or unsubscribe via the World Wide Web, visit
        http://cs.oswego.edu/mailman/listinfo/concurrency-interest
or, via email, send a message with subject or body 'help' to
        [hidden email]

You can reach the person managing the list at
        [hidden email]

When replying, please edit your Subject line so it is more specific
than "Re: Contents of Concurrency-interest digest..."


Today's Topics:

   1. Happens before and stampedlocks (Sudhakar Govindavajhala)


----------------------------------------------------------------------

Message: 1
Date: Mon, 22 Oct 2018 23:21:36 -0400
From: Sudhakar Govindavajhala <[hidden email]>
To: [hidden email]
Subject: [concurrency-interest] Happens before and stampedlocks
Message-ID:
        <[hidden email]>
Content-Type: text/plain; charset="utf-8"

Dear sirs and madams


Please accept my humble respects.


Please let me know if stampedlock class guarantees any happens before
relationship.   Yes or no.    Kindly provide some reading resources on this
subject

Sincerely
Sudhakar Krsna
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20181022/0d7d662f/attachment-0001.html>

------------------------------

Subject: Digest Footer

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


------------------------------

End of Concurrency-interest Digest, Vol 164, Issue 28
*****************************************************
_______________________________________________
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: Happens before and stampedlocks

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list


On Tue, Oct 23, 2018 at 10:33 AM, Millies, Sebastian <[hidden email]> wrote:

I’d be in favor of removing API’s that can only be understood by reading a ten-page conference paper or journal article.


You make compromises for 10x performance. 

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

Re: Happens before and stampedlocks

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
On 10/23/2018 06:33 PM, Millies, Sebastian via Concurrency-interest wrote:
> I’d be in favor of removing API’s that can only be understood by
> reading a ten-page conference paper or journal article.  But how
> much knowledge should documentation really presuppose? (Perhaps an
> understanding of “Java Concurrency in Practice”?)

I don't think this is really fair. It's not a good idea to over-
specify APIs like this one: the guarantees in the documentation are
all you've got, and all you should rely on in your code.

--
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Happens before and stampedlocks

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
Sorry for delay answering:

On 10/22/18 11:21 PM, Sudhakar Govindavajhala via Concurrency-interest
wrote:
>
> Please let me know if stampedlock class guarantees any happens before
> relationship.   Yes or no.    Kindly provide some reading resources on
> this subject
>

Yes. As mentioned in the java.util.concurrent package documentation
(https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/package-summary.html),
all j.u.c locks conform to happens-before requirements. This is not
repeated in any lock APIs, but perhaps it should be. Additionally, this
could/should be made explicit for optimistic mode:

  *   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.

+ *   stamp, in which case all actions prior to the most recent write
+ *   lock release happen-before actions following the call to
+ *   validate. This mode can be thought of as an extremely weak
+ *   ...

Some of the difficulty in documenting this and some other APIs is that
the official JMM is still languishing without incorporating specs for
the jdk9+ VarHandle modes and related methods falling between plain and
volatile, that could be used to more clearly specify behavior. Some day.
In the mean time, I added something in the guide at
http://gee.cs.oswego.edu/dl/html/j9mm.html indicating the techniques
used here.

-Doug

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

Re: Happens before and stampedlocks

JSR166 Concurrency mailing list


On Fri, Oct 26, 2018 at 7:00 AM, Doug Lea via Concurrency-interest <[hidden email]> wrote:

+ *   stamp, in which case all actions prior to the most recent write
+ *   lock release happen-before actions following the call to
+ *   validate.
+ *   ...

It's trickier.

The happens-before is actually established by the tryOptimisticRead, but because there's no mutual exclusion, you can't tell that a read between tryOptimisticRead and validate didn't come from the future -i.e. validate establishes the mutual exclusion that allows you to conclude that reads prior to validate "happened after" the release of the lock held when the corresponding write occurred.

Coming up with good wording here is hard.

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

Re: Happens before and stampedlocks

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
On 10/26/18 10:00 AM, Doug Lea via Concurrency-interest wrote:

> Yes. As mentioned in the java.util.concurrent package documentation
> (https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/package-summary.html),
> all j.u.c locks conform to happens-before requirements. This is not
> repeated in any lock APIs, but perhaps it should be.

On second thought, we should add this explicitly to avoid future
confusion (also improving the wording in previous post):

 * <p><b>Memory Synchronization.</b> Methods with the effect of
 * successfully locking in any mode have the same memory
 * synchronization effects as a <em>Lock</em> action described <a
 *
href="https://docs.oracle.com/javase/specs/jls/se8/html/jls-17.html#jls-17.4">
 * Chapter 17 of <cite>The Java&trade; Language
 * Specification</cite></a>.  Methods successfully unlocking in write
 * mode have the same memory synchronization effects as
 * <em>Unlock</em> actions.  In optimistic usages, actions prior to
 * the most recent write mode unlock action are guaranteed to
 * happen-before those following a tryOptimisticRead only if a later
 * validate returns true; otherwise there is no guarantee that the
 * reads between tryOptimisticRead and validate obtain a consistent
 * snapshot.
 *

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