atom feed23 messages in edu.oswego.cs.concurrency-interest[concurrency-interest] Fwd: StampedLo...
FromSent OnAttachments
Dr Heinz M. KabutzNov 1, 2016 5:17 am 
Nitsan WakartNov 1, 2016 7:37 am 
Alex OtenkoNov 1, 2016 8:07 am 
Nitsan WakartNov 1, 2016 8:42 am 
Alex OtenkoNov 1, 2016 9:02 am 
Henri TremblayNov 1, 2016 9:02 am 
Alex SnapsNov 1, 2016 9:18 am 
Alex OtenkoNov 1, 2016 9:36 am 
Alex SnapsNov 1, 2016 9:46 am 
Martin BuchholzNov 1, 2016 9:55 am 
Martin BuchholzNov 1, 2016 10:01 am 
Dr Heinz M. KabutzNov 1, 2016 11:08 am 
Aleksey ShipilevNov 1, 2016 11:14 am 
Dr Heinz M. KabutzNov 1, 2016 11:31 am 
Aleksey ShipilevNov 1, 2016 12:18 pm 
Dr Heinz M. KabutzNov 1, 2016 1:01 pm 
Alex SnapsNov 1, 2016 1:02 pm 
Dr Heinz M. KabutzNov 1, 2016 1:29 pm 
Dr Heinz M. KabutzNov 1, 2016 1:32 pm 
Alex OtenkoNov 1, 2016 1:34 pm 
Josh HumphriesNov 1, 2016 1:35 pm 
Alex SnapsNov 1, 2016 1:54 pm 
Dr Heinz M. KabutzNov 2, 2016 1:28 am 
Subject:[concurrency-interest] Fwd: StampedLock happens-before with tryOptimisticRead()
From:Alex Snaps (alex@gmail.com)
Date:Nov 1, 2016 1:54:50 pm
List:edu.oswego.cs.concurrency-interest

That was meant to be a reply all!

---------- Forwarded message --------- From: Alex Snaps <alex@gmail.com> Date: Tue, Nov 1, 2016 at 4:54 PM Subject: Re: [concurrency-interest] StampedLock happens-before with tryOptimisticRead() To: Josh Humphries <jh@squareup.com>

Yes. Actually you are right, if the get doesn't settle on the optimistic read but upgrades to pessimistic read it'd block. My bad!

On Tue, Nov 1, 2016 at 4:35 PM Josh Humphries <jh@squareup.com> wrote:

Surely the method that fetches the element uses the full optimistic read -> validate -> maybe pessimistic read lock idiom. If so, a call to get() after observing the increased size will either successfully see the new element (writer concurrently finished and optimistic read succeeds) or block until the writer finishes (optimistic read fails).

So the fetch will successfully yield the element whose addition was "in flight" during the call to size().

This of course doesn't work if there are threads concurrently removing elements, but that has nothing to do with size() not validating the optimistic read but is instead due to size() and get() not being atomic.

---- *Josh Humphries* Payments Engineering Atlanta, GA | 678-400-4867 *Square* (www.squareup.com)

On Tue, Nov 1, 2016 at 4:02 PM, Alex Snaps <alex@gmail.com> 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 <sha@redhat.com> 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