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

Concurrent calls to CHM.put can fail to add the key/value to the map

    XMLWordPrintable

Details

    • b120
    • x86
    • linux
    • Verified

    Backports

      Description

        Parallel execution of Stream.forEachOrdered can fail to terminate.

        This is due to the CHM used by ForEachOps.ForEachOrderedTask.

        Concurrent calls to CHM.put can result in lost entries if a put by one thread is resizing the table (a transfer) while puts by other threads are adding new nodes (holding an entries) to the link list of nodes whose entries all hash to the same value.
         
        The issue can be reliably reproduced with the following program:

        import java.util.concurrent.CompletableFuture;
        import java.util.concurrent.ConcurrentHashMap;
        import java.util.concurrent.CountDownLatch;
        import java.util.concurrent.ThreadLocalRandom;
        import java.util.function.Supplier;
        import java.util.stream.IntStream;
        import java.util.stream.Stream;

        public class TestCHM {

            static final int N = Integer.getInteger("n", 128);
            static final int I = Integer.getInteger("i", 10);

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

            static class X {
                int hc = ThreadLocalRandom.current().nextInt(1, 9);

                public int hashCode() { return hc; }
            }

            public static void test() throws Exception {
                ConcurrentHashMap<Object, Object> m = new ConcurrentHashMap<>();
                CountDownLatch s = new CountDownLatch(1);

                Supplier<Runnable> putter = () -> () -> {
                    try {
                        s.await();
                    }
                    catch (InterruptedException e) {
                    }

                    for (int i = 0; i < N; i++) {
                        Object o = new X();
                        m.put(o, o);
                        if (!m.containsKey(o)) {
                            System.out.println("PUT: Entry does not exist!");
                        }
                    }
                };

                int ps = Runtime.getRuntime().availableProcessors();
                Stream<CompletableFuture> putters = IntStream.range(0, ps)
                        .mapToObj(i -> putter.get())
                        .map(CompletableFuture::runAsync);

                CompletableFuture all = CompletableFuture.allOf(
                        putters.toArray(CompletableFuture[]::new));

                s.countDown();
                all.join();
            }
        }

        Attachments

          Issue Links

            Activity

              People

                psandoz Paul Sandoz
                tyan Tristan Yan (Inactive)
                Votes:
                0 Vote for this issue
                Watchers:
                12 Start watching this issue

                Dates

                  Created:
                  Updated:
                  Resolved: