[concurrency-interest] ConcurrentHashMap entrySet Iterator remove issue?

Joe Bowbeer joe.bowbeer at gmail.com
Thu Feb 4 14:35:44 EST 2016


The entrySet iterator is recommended (by IDE's, static analysis, code
reviewers) for efficiency any time the key and value might both be used
during the iteration. As a result, keySet iteration tends to be refactored
to entrySet iteration.

So I don't think we can deduce that it.remove(k,v) necessarily means remove
that *exact* (k,v). And in a concurrent context, the programmer probably
does not have the expectation that it will always do so.

If the intent is to remove any entry corresponding to the key, how would
this be accomplished in an entrySet iteration after your change? How can a
programmer remove only the exact entry with today's behavior?

Futhermore, what should removeAll do? Can it remove nothing if all of the
iterator's mappings are stale? The existing implementation favors removal.

Here is some discussion around this behavior:

http://stackoverflow.com/questions/29876083/behavior-of-entryset-removeif-in-concurrenthashmap

Also this, tangentially:

http://stackoverflow.com/questions/3768554/is-iterating-concurrenthashmap-values-thread-safe

I suspect there are more than a few people who care, and some who have
already worked around the current behavior if it was not their desired one.


On Thu, Feb 4, 2016 at 10:46 AM, Mike Duigou <openjdk at duigou.org> wrote:

> Hello all;
>
> I have found what seems like a bug in the way that the remove() method of
> CHM entrySet iterators works. The bug doesn't require concurrent behaviour
> but realistically that is the most likely way it arises. The problem is
> that the entrySet iterator remove() internally uses the chm.remove(key)
> method rather than the chm.remove(key, value) method. If there is an
> intervening replacement of the mapping for a key between the iterator
> next() and the remove() then it is possible to incorrectly remove that
> mapping.
>
> I have made test program which compares the behaviour of
> entryset().remove(staleMapping) to entrySet().iterator() remove() of the
> same mapping.
>
> I encountered the problem in real world code where the entry was replaced
> concurrently. I don't believe that there should be programs which expect
> the existing behaviour though undoubtedly there are some. I believe it is
> more likely that programs would/should expect the behaviour in which remove
> of a stale entry does nothing.
>
> Cheers,
>
> Mike
>
>
> /*
>  * Written by Mike Duigou and released to the public domain, as explained
> at
>  * http://creativecommons.org/publicdomain/zero/1.0/
> */
>
> package chm.test;
>
> import java.util.Iterator;
> import java.util.Map;
> import java.util.Set;
> import java.util.concurrent.ConcurrentHashMap;
>
> /**
>  * Compares behaviour of removal of a stale entry via entrySet.remove() vs.
>  * entrySet().iterator().remove()
>  */
> public class ConcurrentHashMapBug {
>
>     public static void main(String... args) {
>         ConcurrentHashMap<String, String> chm = new ConcurrentHashMap<>();
>
>         chm.put("fred", "wilma");
>         chm.put("barney", "betty");
>
>         Set<Map.Entry<String, String>> entries = chm.entrySet();
>
>         // Attempt removal of a mapping through entrySet with stale entry.
>
>         Map.Entry<String, String> fredEntry = null;
>         for (Map.Entry<String, String> each : entries) {
>             if ("fred".equals(each.getKey())) {
>                 fredEntry = each;
>                 break;
>             }
>         }
>         assert fredEntry != null : "Entry not found";
>         assert "wilma".equals(fredEntry.getValue()) : "wrong value";
>
>         // modify fred mapping
>         chm.put("fred", "mildred");
>         // fredEntry is now stale
>         assert "wilma".equals(fredEntry.getValue()) : "live value?";
>
>         // attempt to remove our stale entry.
>         assert !entries.remove(fredEntry) : "fred unexpectedly removed";
>         // Mapping was not removed because entry value did not match
> current mapping.
>         assert chm.containsKey("fred") : "fred mapping missing";
>         assert "mildred".equals(chm.get("fred")) : "fred mapping
> incorrect";
>
>         // Attempt remove of a  mapping through entrySet iterator.remove()
> with stale entry.
>
>         Iterator<Map.Entry<String, String>> iter = entries.iterator();
>         Map.Entry<String, String> barneyEntry = null;
>         while (iter.hasNext()) {
>             Map.Entry<String, String> each = iter.next();
>             if ("barney".equals(each.getKey())) {
>                 barneyEntry = each;
>                 break;
>             }
>         }
>
>         assert barneyEntry != null : "barney entry not found";
>         assert "betty".equals(barneyEntry.getValue()) : "wrong value";
>
>         // modify barney mapping
>         chm.put("barney", "hortence");
>         // barneyEntry is now stale
>         assert chm.containsKey("barney") : "mapping missing";
>         assert "hortence".equals(chm.get("barney")) : "mapping incorrect";
>         assert "betty".equals(barneyEntry.getValue()) : "live value?";
>
>         // attempt to remove our stale entry
>         iter.remove();
>         assert "betty".equals(barneyEntry.getValue()) : "live value?";
>         // XXX Following fails. iter.remove() with stale entry incorrectly
> succeeds.
>         // should behave like chm.remove(barneyEntry.getKey(),
> barneyEntry.getValue())
>         assert chm.containsKey("barney") : "mapping missing";
>         assert "hortence".equals(chm.get("barney")) : "mapping incorrect";
>
>         System.out.println("Success!");
>     }
> }
> _______________________________________________
> 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/20160204/33557c1b/attachment.html>


More information about the Concurrency-interest mailing list