JDK-8078645 : removeIf(filter) in ConcurrentHashMap removes entries for which filter is false
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.util.concurrent
  • Affected Version: 8u45
  • Priority: P4
  • Status: Closed
  • Resolution: Fixed
  • Submitted: 2015-04-26
  • Updated: 2017-05-17
  • Resolved: 2015-05-12
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 9
9 b65Fixed
Related Reports
Duplicate :  
Description
FULL PRODUCT VERSION :
java version "1.8.0_45"
Java(TM) SE Runtime Environment (build 1.8.0_45-b14)
Java HotSpot(TM) 64-Bit Server VM (build 25.45-b02, mixed mode)

ADDITIONAL OS VERSION INFORMATION :
Linux sw 3.13.0-49-generic #83-Ubuntu SMP Fri Apr 10 20:11:33 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux


A DESCRIPTION OF THE PROBLEM :
Running concurrently with map's updates, ConcurrentHashMap.removeIf(filter) can remove entries, for which filter actually returns false. Therefore, it removes entries which should not be removed.

This happens because `EntrySetView` (which is returned by `ConcurrentHashMap.entrySet()`) inherits its `removeIf` implementation from `Collection`, and it is not thread-safe (see my comments in code):

    default boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        boolean removed = false;
        final Iterator<E> each = iterator();
        while (each.hasNext()) {
            // `test` returns `true` for some entry
            if (filter.test(each.next())) { 
               // entry has been just changed, `test` would return `false` now
               each.remove(); // ...but we still remove
               removed = true;
            }
        }
        return removed;
    }

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
1. Create new ConcurrentHashMap and put 1000 entries to it, with keys=1,2,3,...,1000 and all values=0.
2. Start 2 parallel threads:
- First thread: for i=1,2,3,...,1000 puts an entry (k=i, v=1) into the map;
- Second thread: removes all `0` from the map: `map.entrySet().removeIf(e -> e.getValue() == 0)`.
3. Check size of the map. 


EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
After we removed all `0` and added 1000 `1`, the size should be 1000.
ACTUAL -
The size is less, e.g. 998-999, because some `1` were accidentally removed.
(It might require to make several runs until this issue appears. On my machine it requires 2-3 runs.)

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
public class ConcurrentHashMapTest {

    static final int K = 100;
    static final int SIZE = 1000;

    public static void main(String[] args) throws InterruptedException {
        for (int i = 0; i < K; i++) {
            System.out.println(i + " of " + K);
            test();
        }
    }

    private static void test() throws InterruptedException {
        ConcurrentHashMap<Integer, Integer> map = new ConcurrentHashMap<>();
        // put 0's
        for (int i = 0; i < SIZE; i++) {
            map.put(i, 0);
        }

        CyclicBarrier barrier = new CyclicBarrier(2); // to start working simultaneously
        CountDownLatch latch = new CountDownLatch(2); // to wait until both threads finished

        // this thread put 1's into map
        new Thread(new Changer(map, barrier, latch)).start();

        // this thread remove all 0's from map
        new Thread(new Remover(map, barrier, latch)).start();

        latch.await();

        // there should be SIZE 1's in map
        if (map.size() != SIZE) {
            System.out.println("Number of 1's: " + map.values().stream().filter(v -> v == 1).count());
            throw new IllegalStateException(String.format("Size should be %d, but it is %d", SIZE, map.size()));
        }
    }

    static class Changer implements Runnable {

        private final ConcurrentHashMap<Integer, Integer> map;
        private final CyclicBarrier barrier;
        private final CountDownLatch latch;

        public Changer(ConcurrentHashMap<Integer, Integer> map, CyclicBarrier barrier, CountDownLatch latch) {
            this.map = map;
            this.barrier = barrier;
            this.latch = latch;
        }

        @Override
        public void run() {
            try {
                barrier.await();
            } catch (Exception e) {}

            for (int i = 0; i < SIZE; i++) {
                map.put(i, 1);
            }

            latch.countDown();
        }
    }

    static class Remover implements Runnable {

        private final ConcurrentHashMap<Integer, Integer> map;
        private final CyclicBarrier barrier;
        private final CountDownLatch latch;

        public Remover(ConcurrentHashMap<Integer, Integer> map, CyclicBarrier barrier, CountDownLatch latch) {
            this.map = map;
            this.barrier = barrier;
            this.latch = latch;
        }

        @Override
        public void run() {
            try {
                barrier.await();
            } catch (Exception e) {}

            map.entrySet().removeIf(e -> e.getValue() == 0);

            latch.countDown();
        }
    }
}

---------- END SOURCE ----------


Comments
I checked in overrides of removeIf for EntrySets for ConcurrentHashMap and ConcurrentSkipListMap in jsr166 CVS. The CHM version is just a cosmetic variant of Paul's. It would be a good idea to add a statement somewhere that all ConcurrentMaps should do so, but I don't know where to place it. It would be possible to reuse a single mutable Map.Entry in each of these, but not worth the possibility that someone might try retaining inside their test predicate and complain.
2015-04-28

I agree with David that the results of the test program are not guaranteed for any ConcurrentMap (not just CHM). On the other hand, it is probably a good idea to better conform to user expectations in this use case. So EntrySet.removeIf should be overridden in any ConcurrentMap, Paul's version for CHM seems OK, although requiring a snapshot for the sake of handling this case makes it a borderline call. I'll put together a similar solution for ConcurrentSkipListMap.
2015-04-27

It is observed that the CHM.BaseIterator's remove method is implemented as follows: public final void remove() { Node<K,V> p; if ((p = lastReturned) == null) throw new IllegalStateException(); lastReturned = null; map.replaceNode(p.key, null, null); } The expected value "cv" is null. For bulk collection operations of map views that are composed of Iterator.remove then the removal of an entry is not conditional on it's value. Note that for the bulk operation CHM.replaceAll replacement is conditional on the old value of an entry. The CHM.EntrySet could override removeIf with an implementation similar to CHM.replaceAll w.r.t. CHM.replaceNode calls where the new value is always null (signalling removal). The following patch seems to fix things. It's a little awkward as a snapshot of the actual entry needs to be created that is then passed to the predicate. diff -r 294c734ed73d src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java --- a/src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java Fri Apr 24 16:07:08 2015 +0200 +++ b/src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java Mon Apr 27 10:34:22 2015 +0200 @@ -58,12 +58,14 @@ import java.util.concurrent.locks.ReentrantLock; import java.util.function.BiConsumer; import java.util.function.BiFunction; +import java.util.function.BiPredicate; import java.util.function.BinaryOperator; import java.util.function.Consumer; import java.util.function.DoubleBinaryOperator; import java.util.function.Function; import java.util.function.IntBinaryOperator; import java.util.function.LongBinaryOperator; +import java.util.function.Predicate; import java.util.function.ToDoubleBiFunction; import java.util.function.ToDoubleFunction; import java.util.function.ToIntBiFunction; @@ -1618,6 +1620,23 @@ } } + boolean removeIf(Predicate<? super Entry<K, V>> function) { + if (function == null) throw new NullPointerException(); + Node<K,V>[] t; + boolean removed = false; + if ((t = table) != null) { + Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length); + for (Node<K,V> p; (p = it.advance()) != null; ) { + K key = p.key; + V value = p.val; + if (function.test(new AbstractMap.SimpleImmutableEntry<>(key, value)) && replaceNode(key, null, value) != null) { + removed = true; + } + } + } + return removed; + } + /** * If the specified key is not already associated with a value, * attempts to compute its value using the given mapping function @@ -4759,6 +4778,10 @@ return added; } + public boolean removeIf(Predicate<? super Entry<K, V>> filter) { + return map.removeIf(filter); + } + public final int hashCode() { int h = 0; Node<K,V>[] t;
2015-04-27

The stream documentation for ConcurrentHashMap alludes to this kind of potential problem: * <p>ConcurrentHashMaps support a set of sequential and parallel bulk * operations that, unlike most {@link Stream} methods, are designed * to be safely, and often sensibly, applied even with maps that are * being concurrently updated by other threads; for example, when * computing a snapshot summary of the values in a shared registry. * There are three kinds of operation, each with four forms, accepting * functions with Keys, Values, Entries, and (Key, Value) arguments * and/or return values. Because the elements of a ConcurrentHashMap * are not ordered in any particular way, and may be processed in * different orders in different parallel executions, the correctness * of supplied functions should not depend on any ordering, or on any * other objects or values that may transiently change while * computation is in progress; and except for forEach actions, should * ideally be side-effect-free. Bulk operations on {@link java.util.Map.Entry} * objects do not support method {@code setValue}. In particular: "the correctness of supplied functions should not depend on any ordering, or on any other objects or values that may transiently change while computation is in progress" Without explicit locking of the CHM (which somewhat defeats the purpose) there is an inherent race between the thread performing removeIf, and the thread mutating the Map.Entry object.
2015-04-27

1) Run the attached test case ConcurrentHashMapTest.java with JDK 8u31, 8u45, 8u60 ea b10 and 9 ea b60. 2) Result Table (Linux and Windows 7 (64-bit): 8u31: FAIL 8u45: FAIL 8u60 ea b10: FAIL 9 ea b60: FAIL Output with different JDK's: --------------------------------------------------------------- 8u31: # java ConcurrentHashMapTest.java 0 of 100 1 of 100 2 of 100 Number of 1's: 999 Exception in thread "main" java.lang.IllegalStateException: Size should be 1000, but it is 999 at javaapplication270.ConcurrentHashMapTest.test(ConcurrentHashMapTest.java:40) at javaapplication270.ConcurrentHashMapTest.main(ConcurrentHashMapTest.java:15) ------------------------------------------------------------------------ 8u45: 0 of 100 1 of 100 2 of 100 Number of 1's: 997 Exception in thread "main" java.lang.IllegalStateException: Size should be 1000, but it is 997 at javaapplication270.ConcurrentHashMapTest.test(ConcurrentHashMapTest.java:40) at javaapplication270.ConcurrentHashMapTest.main(ConcurrentHashMapTest.java:15) ------------------------------------------------------------------------------------------------ 8u60: 0 of 100 1 of 100 Number of 1's: 988 Exception in thread "main" java.lang.IllegalStateException: Size should be 1000, but it is 988 at javaapplication270.ConcurrentHashMapTest.test(ConcurrentHashMapTest.java:40) at javaapplication270.ConcurrentHashMapTest.main(ConcurrentHashMapTest.java:15) ------------------------------------------------------------------------------------------------------------------------------------------------------- 9 ea b60: # java ConcurrentHashMapTest 0 of 100 1 of 100 Number of 1's: 938 Exception in thread "main" java.lang.IllegalStateException: Size should be 1000, but it is 938 at ConcurrentHashMapTest.test(ConcurrentHashMapTest.java:38) at ConcurrentHashMapTest.main(ConcurrentHashMapTest.java:13) ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Result: The issue is reproducible with the provided test case and the number of entries reduces with subsequent JDK versions.
2015-04-27