backport issue: second opinion needed

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

backport issue: second opinion needed

Dawid Kurzyniec
Hello,

the issue has been reported against backport-util-concurrent, related to
the use of unfair condition variables. The TCK test
ReentrantLockTest.testAwaitUninterruptibly sometimes hangs at
Thread.join when run on AIX. I believe that the problem is due to a race
condition between interruptions and signals in the JVM, and I think it
can also occur on other non-SUN JVMs and on older JVMs. (The problem is
that when Thread.interrupt() happens very soon after notify(), the
InterruptedException is sometimes thrown from wait(), masking the
notification which should have caused the thread to complete normally).
SUN 1.4 JVMs does not seem to suffer from this issue.

Most of the code in the backport is written defensively to guard against
this race. But it turns out that Condition.awaitUninterruptibly, for
conditions of non-fair locks, is affected. The current implementation is
as follows:

    public void awaitUninterruptibly() {
        int holdCount = lock.getHoldCount();
        if (holdCount == 0) {
            throw new IllegalMonitorStateException();
        }
        boolean wasInterrupted = false;
        try {
            synchronized (this) {
                for (int i=holdCount; i>0; i--) lock.unlock();
                while (true) {
                    try {
                        wait();
                        break;
                    }
                    catch (InterruptedException ex) {
                        wasInterrupted = true;
                    }
                }
            }
        }
        finally {
            for (int i=holdCount; i>0; i--) lock.lock();
            if (wasInterrupted) {
                Thread.currentThread().interrupt();
            }
        }
    }


This works on JVMs which do not have the interrupt/signal race. But to
guard against the JVM race, when catching IE, I have to assume that the
signal has possibly been masked by the IE. I don't have any way to know
for sure, unless I use explicit wait queue management, which will affect
performance, and which is already done in the fair version of the
condition. So, the only solution that I can see that 1) retains
conformance with the specification and 2) does not affect performance is
to wake up spuriously upon interrupt:

    public void awaitUninterruptibly() {
        int holdCount = lock.getHoldCount();
        if (holdCount == 0) {
            throw new IllegalMonitorStateException();
        }
        // avoid immediate spurious wakeup if the thread is already
interrupted
        boolean wasInterrupted = Thread.interrupted();
        try {
            synchronized (this) {
                for (int i=holdCount; i>0; i--) lock.unlock();
                try {
                    wait();
                }
                catch (InterruptedException ex) {
                    // may have masked the signal and there is no way
                    // to know for sure; we must wake up spuriously
                    wasInterrupted = true;
                }
            }
        }
        finally {
            for (int i=holdCount; i>0; i--) lock.lock();
            if (wasInterrupted) {
                Thread.currentThread().interrupt();
            }
        }
    }

(Note the lack of the "while" loop). This is a little bit bad:
"uninterruptible" wait wakes up spuriously upon interrupt. And it would
be a change of existing behavior. But it is allowed by the spec.

I would like to ask experts to 1) confirm/refine the diagnosis and 2)
comment on whether there is any better way to handle this. Is there
something that I am missing?

(BTW. _fair_ ReentrantLock will not suffer from this; there are no
spurious wakeups in its case).

Kind regards,
Dawid Kurzyniec

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

backport issue: second opinion needed (cont.)

Dawid Kurzyniec
Dawid Kurzyniec wrote:

> (...) So, the only solution that I can see that 1) retains conformance
> with the specification and 2) does not affect performance is to wake
> up spuriously upon interrupt: (...)

Actually, there is also another option, common in dl.u.c: to signal upon
interrupt:

    public void awaitUninterruptibly() {
        int holdCount = lock.getHoldCount();
        if (holdCount == 0) {
            throw new IllegalMonitorStateException();
        }
        // avoid instant spurious wakeups if thread already interrupted
        boolean wasInterrupted = Thread.interrupted();
        try {
            synchronized (this) {
                for (int i=holdCount; i>0; i--) lock.unlock();
                while (true) {
                    try {
                        wait();
                        break;
                    }
                    catch (InterruptedException ex) {
                        wasInterrupted = true;
                        // may have masked the signal and there is no way
                        // to tell; defensively propagate the signal,
potentially
                        // causing a spurious wakeup
                        notify();
                    }
                }
            }
        }
        finally {
            for (int i=holdCount; i>0; i--) lock.lock();
            if (wasInterrupted) {
                Thread.currentThread().interrupt();
            }
        }
    }

However, this causes ANOTHER thread, rather than the interrupted one, to
wake up spuriously. Therefore, initially I didn't see any advantage in
doing that - a spurious wakeup is a spurious wakeup. But there might be
an advantage: if there are no other threads waiting on this condition,
which is often the case e.g. in single-producer-single-consumer queues,
then there is going to be no spurious wakeups. So now I am leaning
towards this solution. But again: aren't I missing something?

Regards,
Dawid

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

RE: backport issue: second opinion needed

David Holmes
In reply to this post by Dawid Kurzyniec
Dawid,

> the issue has been reported against backport-util-concurrent, related to
> the use of unfair condition variables. The TCK test
> ReentrantLockTest.testAwaitUninterruptibly sometimes hangs at
> Thread.join when run on AIX. I believe that the problem is due to a race
> condition between interruptions and signals in the JVM, and I think it
> can also occur on other non-SUN JVMs and on older JVMs. (The problem is
> that when Thread.interrupt() happens very soon after notify(), the
> InterruptedException is sometimes thrown from wait(), masking the
> notification which should have caused the thread to complete normally).
> SUN 1.4 JVMs does not seem to suffer from this issue.

<sigh> Yes this was an old problem that Sun Vm's used to suffer from back in
early 1.2, not sure when it was fixed. Basically the VM logic for doing a
wait() separates the wakeup mechanism from the interruption check, so when
the internal blocking call returns the thread does the logical equivalent
of:

 if (Thread.currentThread().interupted())
    throw new InterruptedException();

This causes the notification to be lost and is definitely a bug in the VM -
but one that is hard to argue conclusively from the spec, at least prior to
5.0

Lots of our older code examples in the tutorials, and CPJ2E if I recall
correctly. perform the extra notify() on catching IE as a workaround. If you
already do your own queue management then you can do an explicit signalled
check, but otherwise the extra notify is best as you rarely expect this to
get trigerred in practice.

Cheers,
David Holmes

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

Re: backport issue: second opinion needed

Dawid Kurzyniec
David Holmes wrote:

><sigh> Yes this was an old problem that Sun Vm's used to suffer from back in
>early 1.2, not sure when it was fixed. Basically the VM logic for doing a
>wait() separates the wakeup mechanism from the interruption check, so when
>the internal blocking call returns the thread does the logical equivalent
>of:
>
> if (Thread.currentThread().interupted())
>    throw new InterruptedException();
>
>This causes the notification to be lost and is definitely a bug in the VM -
>but one that is hard to argue conclusively from the spec, at least prior to
>5.0
>
>Lots of our older code examples in the tutorials, and CPJ2E if I recall
>correctly. perform the extra notify() on catching IE as a workaround.
>

A follow-up: the code for waiting on a reentrant lock in the backport
(borrowed from dl.u.c.) is the following:

                       try {
                           do { wait(); } while (owner_ != null);
                           owner_ = caller;
                           holds_ = 1;
                           return;
                       }
                       catch (InterruptedException ex) {
                           notify();
                           throw ex;
                       }

It seems to me though that notification is not needed if owner_ != null,
since this is the condition the waiters are testing anyway. Could it be
safely substituted with "if (owner_ == null) notify()"? In general, to
deal with the interruption/signal masking, is the following idiom OK:

when interruption should be preferred:

if (Thread.interrupted()) throw new InterruptedException();
if (condition) return;
try {
   do { wait(); } while (!condition);
}
catch (InterruptedException ex) {
  if (condition) notify();
  throw ex;
}

otherwise:

if (condition) return;
try {
   do { wait(); } while (!condition);
}
catch (InterruptedException ex) {
  if (!condition) throw ex;
  else Thread.currentThread().interrupt();
}


Regards,
Dawid

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

RE: backport issue: second opinion needed

David Holmes-3
Dawid,

> A follow-up: the code for waiting on a reentrant lock in the backport
> (borrowed from dl.u.c.) is the following:
>
>                        try {
>                            do { wait(); } while (owner_ != null);
>                            owner_ = caller;
>                            holds_ = 1;
>                            return;
>                        }
>                        catch (InterruptedException ex) {
>                            notify();
>                            throw ex;
>                        }
>
> It seems to me though that notification is not needed if owner_ != null,
> since this is the condition the waiters are testing anyway. Could it be
> safely substituted with "if (owner_ == null) notify()"?

If you can easily identify the condition being waited upon (and know for a
fact that noone will be waiting on that object for any other condition) then
you could make the notify() conditional. But it is a micro optimization at
best (interrupt should be rare and a notify is a simple queue transfer) and
introduces a context sensitivity that the unconditional notify does not
have.

> when interruption should be preferred:
>
> if (Thread.interrupted()) throw new InterruptedException();
> if (condition) return;
> try {
>    do { wait(); } while (!condition);
> }
> catch (InterruptedException ex) {
>   if (condition) notify();
>   throw ex;
> }
> otherwise:
>
> if (condition) return;
> try {
>    do { wait(); } while (!condition);
> }
> catch (InterruptedException ex) {
>   if (!condition) throw ex;
>   else Thread.currentThread().interrupt();
> }

I prefer a simple while loop :) but with the caveat on the use of condition,
yes these seem fine.

Cheers,
David Holmes

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

Re: backport issue: second opinion needed

Dawid Kurzyniec
David Holmes wrote:

>>if (condition) return;
>>try {
>>   do { wait(); } while (!condition);
>>}
>>catch (InterruptedException ex) {
>>  if (!condition) throw ex;
>>  else Thread.currentThread().interrupt();
>>}
>>    
>>
>
>I prefer a simple while loop :)
>  
>

Sure; it's just that with timed versions of these, there's a bunch of
extra stuff in between (System.nanoTime() etc.), which is worth skipping
in the uncontended case.

> but with the caveat on the use of condition,
> yes these seem fine.


Thanks!

Regards,
Dawid


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