[concurrency-interest] ConcurrentHashMap entrySet Iterator remove issue?

Mike Duigou openjdk at duigou.org
Thu Feb 4 13:46:58 EST 2016


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!");
     }
}


More information about the Concurrency-interest mailing list