JDK-7014263 : NegativeArraySizeException reported in ArrayBlockingQueue under load
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.util.concurrent
  • Affected Version: 6
  • Priority: P3
  • Status: Closed
  • Resolution: Fixed
  • OS: generic
  • CPU: generic
  • Submitted: 2011-01-24
  • Updated: 2011-10-11
  • Resolved: 2011-10-11
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 6
6u30 b08Fixed
Related Reports
Relates :  
JDK-7005424 - Resync java.util.concurrent classes with Dougs CVS - Jan 2011
Relates :  
JDK-7145112 - Error in method Iterator.remove() from ArrayBlockingQueue
Description
SYNOPSIS
--------
NegativeArraySizeException reported in ArrayBlockingQueue under load

OPERATING SYSTEM
----------------
All

FULL JDK VERSION
----------------
All Java 6 releases and all JDK7 builds
Does not occur with 5.0

DESCRIPTION from LICENSEE
-------------------------
Instances of ArrayBlockingQueue (and possibly other collection classes in the java.util.concurrent package) can become broken under load, resulting in NegativeArraySizeExceptions.

STEPS TO REPRODUCE
------------------
1. Run the supplied testcase repeatedly:

   java CutDownArrayBlockingQueueTest

The problem is intermittent. When running the test repeatedly in quick succession, I see the exceptions about once every 5-10 executions - sometimes more, sometimes less.

OBSERVED RESULT
---------------
One or more exceptions similar to the following:

Exception in thread "Thread-27" java.lang.NegativeArraySizeException
        at java.util.concurrent.ArrayBlockingQueue.toArray(ArrayBlockingQueue.java:483)
        at WorkerThread.run(CutDownArrayBlockingQueueTest.java:142)
Exception in thread "Thread-72" java.lang.NegativeArraySizeException
        at java.util.concurrent.ArrayBlockingQueue.toArray(ArrayBlockingQueue.java:483)
        at WorkerThread.run(CutDownArrayBlockingQueueTest.java:156)
Exception in thread "Thread-80" java.lang.NegativeArraySizeException
        at java.util.concurrent.ArrayBlockingQueue.toArray(ArrayBlockingQueue.java:483)
        at WorkerThread.run(CutDownArrayBlockingQueueTest.java:156)
Exception in thread "Thread-47" java.lang.NegativeArraySizeException
        at java.util.concurrent.ArrayBlockingQueue.toArray(ArrayBlockingQueue.java:483)
        at WorkerThread.run(CutDownArrayBlockingQueueTest.java:156)

EXPECTED RESULT
---------------
This situation should never arise. It seems that one or more elements can be removed from the ArrayBlocking queue even when there are no elements to be removed, which clearly should not occur. We should receive a NoSuchElementException when invoking remove() on an empty queue.

For example, in a single threaded context the following code:

    ArrayBlockingQueue queue = new ArrayBlockingQueue(20);
    queue.remove();

will *always* result in this exception:

    Exception in thread "main" java.util.NoSuchElementException
    at java.util.AbstractQueue.remove(AbstractQueue.java:97)

It seems that this does not always happen in the multithreaded stress test we have provided.
Comments
SUGGESTED FIX http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/ArrayBlockingQueue.java?r1=1.59&r2=1.60
28-08-2011
EVALUATION The problem is fixed in ArrayBlockingQueue.java, Revision 1.60, Doug Lea's JSR-166 CVS. http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/ArrayBlockingQueue.java?r1=1.59&r2=1.60
28-08-2011
EVALUATION This bug is no longer an issue in JDK 7 b128. It has been fixed as part of the changes for CR 7005424. Adding '7-na' keyword to reflect this. Here's what is happening (pre 7005424). Invoking remove on the iterator returned by ABQ simply tries to remove the item at the index of the item that was previously returned by the iterator, using removeAt(int). This is not correct as the item at that index may not the same item, or in this case the queue may be empty. removeAt will always decrement the count, causing it to become negative if the queue is empty. Many other operations will now cause the queue to get into a very bad state as they use if (count == 0) to determine if the queue is empty ( they assume count will never be negative ). But how is iterator.remove being invoked, since the test does not call it directly? The test invokes retainAll ( which is inherited from AbstractCollection ). AbstractCollection.retainAll creates an iterator over the the collection and invokes remove() if the given collection does not contain the item. Targeting this bug to JDK6, to backport the specific changes required fix the iterators remove method.
26-01-2011
PUBLIC COMMENTS I suspect the updates to the Iterator locking and logic may be the fix here, though I would expect itr.remove() to be the cause of the problem and I don't see that being used.
25-01-2011
PUBLIC COMMENTS I can reproduce this quite easily with JDK7 b125, and it is failing because count is negative. With the latest JDK7, built from JDK b128, I no longer see the problem. There were some changes to ArrayBlockingQueue that were integrated under CR 7005424. It is possible that this issue was fixed. More investigation into the root cause needs to be done to ensure it has actually been fixed.
24-01-2011