[concurrency-interest] Bug in ConcurrentHashMap keyset iterator?

Ben Manes ben_manes at yahoo.com
Thu Feb 16 22:38:39 EST 2012


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. 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> 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)
>>>>
>>>>_______________________________________________
>>>>Concurrency-interest mailing list
>>>>Concurrency-interest at cs.oswego.edu
>>>>http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>>>
>>>>
>>

_______________________________________________
Concurrency-interest mailing list
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/8a89c91b/attachment-0001.html>


More information about the Concurrency-interest mailing list