[concurrency-interest] Bug in ConcurrentHashMap keyset iterator?

[Adrian Tarau]

Good morning,

I get recently several failures in one of the processes(a remote file 
collector) which looks like a bug in ConcurrentHashMap implementation. I 
attached all relevant code...I do not think I misused the map but... I 
searched for similar complaints but I couldn't find anything relevant - 
bugs.sun.com returns noting when searching for "ConcurrentHashMap 
ArrayIndexOutOfBoundsException".

Thank you,
Adrian Tarau.

I have a map declared like this:

/private final Map<Location, PriorityBlockingQueue<WorkUnit>> 
workUnitsPerLocation = new ConcurrentHashMap<Location, 
PriorityBlockingQueue<WorkUnit>>();/

a work unit is pushed like this:

......
Queue<WorkUnit> locationQueue = getLocationQueue(location);
boolean offer = locationQueue.offer(workUnit);
.......
private Queue<WorkUnit> getLocationQueue(Location location) {
         synchronized (workUnitsPerLocation) {
             PriorityBlockingQueue<WorkUnit> queue = 
workUnitsPerLocation.get(location);
             if (queue == null) {
                 queue = new PriorityBlockingQueue<WorkUnit>(100, new 
WorkUnit.Comparator());
                 workUnitsPerLocation.put(location, queue);
             }
             return queue;
         }
     }

and a working thread(scheduled to run every 5 seconds) is scanning for 
available work units, peeking one from every location(until a maximum 
number of working units are running) like this:

/class WorkUnitScheduler extends AbstractWorker {

         ...
         // volatile since the state of the iterator must be preserved 
under different working threads
         private volatile Iterator<Location> workUnitsIterator;

         ....

         private Queue<WorkUnit> getNextQueue() {
             for (int i = 0; i < 2; i++) {// loop twice so we go over 
all possible locations
                 if (workUnitsIterator == null || 
!workUnitsIterator.hasNext()) {
                     workUnitsIterator = 
workUnitsPerLocation.keySet().iterator();//start from beginning
                 }
                 while (workUnitsIterator.hasNext()) {
                     try {
                         Location location = workUnitsIterator.next(); 
*<--- fails here*
                         if (canScheduleFromLocation(location)) {//if 
allowed, get next working unit from this location
                             return workUnitsPerLocation.get(location);
                         }
                     } catch (NoSuchElementException e) {
                         // no location
                     }
                 }
             }
             return null;
         }

         @Override
         protected void doRun() {
                  ....
                 Queue<WorkUnit> queue = getNextQueue();
                 if (queue == null) {
                     break;
                 }
                 WorkUnit workingUnit = queue.poll();
                 if (workingUnit == null) {
                     continue;
                 }
                 WorkerService.getInstance().schedule(new 
DownloadUploadWorker(workingUnit));
                 ....
         }
     }/

and it fails with:

/got exception java.lang.ArrayIndexOutOfBoundsException: 3
      at 
java.util.concurrent.ConcurrentHashMap$HashIterator.advance(ConcurrentHashMap.java:1086)
      at 
java.util.concurrent.ConcurrentHashMap$HashIterator.nextEntry(ConcurrentHashMap.java:1101)
      at 
java.util.concurrent.ConcurrentHashMap$KeyIterator.next(ConcurrentHashMap.java:1117)/

it fails here(ConcurrentHashMap implementation fragment):

/final void advance() {
             if (nextEntry != null && (nextEntry = nextEntry.next) != null)
                 return;

             while (nextTableIndex >= 0) {
                 if ( (nextEntry = currentTable[nextTableIndex--]) != null)
                     return;
             }

             while (nextSegmentIndex >= 0) {
                 Segment<K,V> seg = segments[nextSegmentIndex--];
                 if (seg.count != 0) {
                     currentTable = seg.table;
                     for (int j = currentTable.length - 1; j >= 0; --j) {
                         if ( (nextEntry = currentTable[j]) != null) 
{*<-- failure*
                             nextTableIndex = j - 1;
                             return;
                         }
                     }
                 }
             }
         }/

JVM info:

/java version "1.6.0_30"
Java(TM) SE Runtime Environment (build 1.6.0_30-b12)
Java HotSpot(TM) Server VM (build 20.5-b03, mixed mode)/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20120216/0d514eb0/attachment-0001.html>