Re: [PATCH] Fix to EventQueue 5/7

[Thomas Fitzsimmons <fitzsim at redhat dot com>]

On Fri, 2004-01-16 at 12:23, Fernando Nasser wrote:
> This removes a race condition (very small chance -- an event had to arrive right 
> between the release of a lock and the acquiring of the other) that could cause 
> events to be delivered out of order.
> 
> 2004-01-16  Fernando Nasser  <fnasser@redhat.com>
> 
>          * java/awt/EventQueue.java (pop): Prevent racing condition to add
>          events to the queue out of order by acquiring locks in the proper
>          order and not by releasing one before acquiring the other.
> 
> ______________________________________________________________________
> Index: java/awt/EventQueue.java
> ===================================================================
> RCS file: /cvs/gcc/gcc/libjava/java/awt/EventQueue.java,v
> retrieving revision 1.13
> diff -u -p -r1.13 EventQueue.java
> --- java/awt/EventQueue.java	16 Jan 2004 16:15:49 -0000	1.13
> +++ java/awt/EventQueue.java	16 Jan 2004 16:38:32 -0000
> @@ -348,30 +348,32 @@ public class EventQueue
>      if (prev == null)
>        throw new EmptyStackException();
>  
> -    // Don't synchronize both this and prev at the same time, or deadlock could
> -    // occur.
> +    /* The order is important here, we must get the prev lock first,
> +       or deadlock could occur as callers usually get here following
> +       prev's next pointer, and thus obtain prev's lock before trying
> +       to get this lock. */
>      synchronized (prev)
>        {
>          prev.next = next;
> -      }
>  
> -    synchronized (this)
> -      {
> -        int i = next_out;
> -        while (i != next_in)
> +        synchronized (this)
>            {
> -            prev.postEvent(queue[i]);
> -            next_out = i;
> -            if (++i == queue.length)
> -              i = 0;
> +            int i = next_out;
> +            while (i != next_in)
> +              {
> +                prev.postEvent(queue[i]);
> +                next_out = i;
> +                if (++i == queue.length)
> +                  i = 0;
> +              }
> +	    // Empty the queue so it can be reused
> +	    next_in = 0;
> +	    next_out = 0;
> +
> +            // Tell our EventDispatchThread that it can end execution
> +            dispatchThread.interrupt ();
> +	    dispatchThread = null;
>            }
> -	// Empty the queue so it can be reused
> -	next_in = 0;
> -	next_out = 0;
> -
> -        // Tell our EventDispatchThread that it can end execution
> -        dispatchThread.interrupt ();
> -	dispatchThread = null;
>        }
>    }
>  

So, the patch creates a nested lock, where prev is locked and then this
is locked before prev is unlocked.  If it were possible for another
thread to lock this and then lock prev before it unlocked this, then
deadlock could occur.  I can't see any way for that to happen in the
current code, so this looks OK to me.

I have a question though.  The current code allows the following to
happen:

Thread A calls topEQ.push(newEQ) and topEQ.push executes partially but
doesn't execute this line:

    newEventQueue.prev = this;

So at this point, newEQ.prev is still null (unless it was already
initialized before push was called; that shouldn't happen, but if it
did, the current code could give weird results).  If Thread B calls
newEQ.pop and executes the lines:

    if (prev == null)
      throw new EmptyStackException();

then Thread B will get an EmptyStackException, even though the method
call to push newEQ was issued before newEQ's pop call.  Is that
acceptable behaviour or should there be more synchronization to ensure
that push completes on topEQ before pop can be called on newEQ?

Tom