[concurrency-interest] Bug in ConcurrentHashMap keyset iterator?

Adrian Tarau adrian.tarau at gmail.com
Thu Feb 16 22:06:59 EST 2012


Well, again, I do not see it specified "this is not thread safe" and by 
default you presume ConcurrentHashMap and its structures are thread 
safe. I usually dive into the JDK source code to understend the 
inner-things but I took ConcurrentHashMap as "everything it should be 
thread safe, why looking, it's obvious".

The reason why I'm caching the iterator(last used position) is the 
following: let's say I have 20 locations(everyone with it's own queue) 
and a maximum number of allowed "workers" 10. The scheduling worker(runs 
every N seconds) gets the iterator with the last known position(or it 
creates one) and consumes as many locations as it can. Next time when 
the scheduling worker is executed(it might be executed on a different 
thread) I want to continue from the last known position - I want to 
consume objects from queues in a round-robin fashion, not exceeding the 
maximum number of "processing units" running at any time.

That was the reason why grabbing the key iterator, cache it(since it 
might not be consumed all at once) and once it reaches the end grab a 
new one. It looked pretty trivial  but I guess I was wrong presuming the 
key set iterator is thread safe.

I'm looking at ConcurrentHashMap.HashIterator implementation and I can 
see it is not thread safe, but it would be good to have this mentioned 
in the javadoc of ConcurrentHashMap.keySet().

Thank you,
Adrian Tarau.

On 02/16/2012 05:07 PM, Vitaly Davidovich wrote:
>
> The keyset is threadsafe but not its iterator.  The CHM internally 
> caches a keyset instance, so I don't think you really need to cache 
> anything in your code.
>
> Sent from my phone
>
> On Feb 16, 2012 5:04 PM, "Adrian Tarau" <adrian.tarau at gmail.com 
> <mailto:adrian.tarau at gmail.com>> wrote:
>
>     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/2f91d53e/attachment-0001.html>


More information about the Concurrency-interest mailing list