[concurrency-interest] Bug in ConcurrentHashMap keyset iterator?

Adrian Tarau adrian.tarau at gmail.com
Thu Feb 16 17:04:55 EST 2012


Yes, I do. I presumed they are thread safe. There is no mention in the 
keySet method that is not thread safe(or the class documentation) and 
you can easily presume you will get a set that's thread safe(including 
the iterator) since you are using ConcurrentHashMap :)

//**
      * Returns a {@link Set} view of the keys contained in this map.
      * The set is backed by the map, so changes to the map are
      * reflected in the set, and vice-versa.  The set supports element
      * removal, which removes the corresponding mapping from this map,
      * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
      * operations.  It does not support the <tt>add</tt> or
      * <tt>addAll</tt> operations.
      *
      * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
      * that will never throw {@link ConcurrentModificationException},
      * and guarantees to traverse elements as they existed upon
      * construction of the iterator, and may (but is not guaranteed to)
      * reflect any modifications subsequent to construction.
      */
     public Set<K> keySet() {
         ....
     }/

On 02/16/2012 10:26 AM, Vitaly Davidovich wrote:
>
> Are you sharing the same iterator between multiple threads? That's 
> what it sounds like - you can't do that as they aren't threadsafe.
>
> Sent from my phone
>
> On Feb 16, 2012 9:47 AM, "Adrian Tarau" <adrian.tarau at gmail.com 
> <mailto:adrian.tarau at gmail.com>> wrote:
>
>     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
>     <http://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)/
>
>     _______________________________________________
>     Concurrency-interest mailing list
>     Concurrency-interest at cs.oswego.edu
>     <mailto:Concurrency-interest at cs.oswego.edu>
>     http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20120216/9a358819/attachment.html>


More information about the Concurrency-interest mailing list