[concurrency-interest] Bug in ConcurrentHashMap keyset iterator?

Adrian Tarau adrian.tarau at gmail.com
Fri Feb 17 09:44:29 EST 2012


Indeed, mea culpa. To avoid keeping/updating another structure I will 
probably just do /new CopyOnWriteArrayList(map.keySet()) /and use this 
as a thread safe iterable structure.

Thank you for you help,
Adrian Tarau.

On 02/16/2012 10:38 PM, Ben Manes wrote:
> It is mentioned in the class JavaDoc:
> Similarly, Iterators and Enumerations return elements reflecting the 
> state of the hash table at some point at or since the creation of the 
> iterator/enumeration. They do /not/ throw 
> |ConcurrentModificationException| 
> <http://docs.oracle.com/javase/6/docs/api/java/util/ConcurrentModificationException.html>. 
> However, iterators are designed to be used by only one thread at a time.
>
> It sounds like your situation might be well served by a cyclical 
> buffer, where the next location to process is just an increment of an 
> atomic read counter % buffer size.
>
> ------------------------------------------------------------------------
> *From:* Adrian Tarau <adrian.tarau at gmail.com>
> *To:* Vitaly Davidovich <vitalyd at gmail.com>
> *Cc:* concurrency-interest at cs.oswego.edu
> *Sent:* Thursday, February 16, 2012 7:06 PM
> *Subject:* Re: [concurrency-interest] Bug in ConcurrentHashMap keyset 
> iterator?
>
> 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
>>>
>>
>
>
> _______________________________________________
> 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/20120217/427d093c/attachment-0001.html>


More information about the Concurrency-interest mailing list