[concurrency-interest] Bug in ConcurrentHashMap keyset iterator?

Joe Bowbeer joe.bowbeer at gmail.com
Thu Feb 16 22:56:21 EST 2012


This check-then-act sequence is fundamentally not thread-safe:

    while (workUnitsIterator.hasNext()) {
        try {
            Location location = workUnitsIterator.next(); <--- fails here

If the iterator were to be designed for multiple-thread access then these
operations would probably be merged so that, for example, next() would
return null when the end was reached.

    for (Location location; (location = iter.next()) != null; ) { ...

--Joe

On Thu, Feb 16, 2012 at 7:06 PM, Adrian Tarau wrote:

>  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> 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> 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 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/e1b8baf9/attachment.html>


More information about the Concurrency-interest mailing list