[concurrency-interest] ConcurrentHashMap entrySet Iterator remove issue?

Joe Bowbeer joe.bowbeer at gmail.com
Thu Feb 4 14:52:41 EST 2016


Regarding removeAll, I was asking about entrySet.removeAll().

I'm not sure this is really relevant. I was wondering if one might expect
that clear() and entrySet.removeAll and removing each item from an
entrySet's iterator should all have the same behavior.

On Thu, Feb 4, 2016 at 11:35 AM, Joe Bowbeer <joe.bowbeer at gmail.com> wrote:

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


More information about the Concurrency-interest mailing list