Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8078645

removeIf(filter) in ConcurrentHashMap removes entries for which filter is false

    Details

      Backports

        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 ----------

          Attachments

            Issue Links

              Activity

                People

                • Assignee:
                  psandoz Paul Sandoz (Inactive)
                  Reporter:
                  webbuggrp Webbug Group
                • Votes:
                  0 Vote for this issue
                  Watchers:
                  7 Start watching this issue

                  Dates

                  • Created:
                    Updated:
                    Resolved: