United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
Bug ID: 7014263 NegativeArraySizeException reported in ArrayBlockingQueue under load
7014263 : NegativeArraySizeException reported in ArrayBlockingQueue under load

Details
Type:
Bug
Submit Date:
2011-01-24
Status:
Closed
Updated Date:
2011-10-11
Project Name:
JDK
Resolved Date:
2011-10-11
Component:
core-libs
OS:
generic
Sub-Component:
java.util.concurrent
CPU:
generic
Priority:
P3
Resolution:
Fixed
Affected Versions:
6
Fixed Versions:
6u30

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

Sub Tasks

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
2011-08-28 
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
2011-08-28 
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.
2011-01-26 
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.
2011-01-25 
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.
2011-01-24


Hardware and Software, Engineered to Work Together