[concurrency-interest] ConcurrentHashMap entrySet Iterator remove issue?

Joe Bowbeer joe.bowbeer at gmail.com
Thu Feb 4 15:01:10 EST 2016


Also see: http://bugs.java.com/bugdatabase/view_bug.do?bug_id=8078645

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

> 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/2c9882ca/attachment-0001.html>


More information about the Concurrency-interest mailing list