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

Concurrent spliterators fail to handle exhaustion properly

    Details

    • Type: Bug
    • Status: Resolved
    • Priority: P3
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 9
    • Component/s: core-libs
    • Labels:
      None

      Backports

        Description

        Handling exhaustion in spliterator implementations is error-prone, especially when two fields are involved, and fields transition from null to non-null back to null, sometimes in the same operation.

        Here's a test that finds 3 implementations that get it wrong:

            /**
             * Concurrent Spliterators, once exhausted, stay exhausted.
             */
            public void testStickySpliteratorExhaustion() throws Throwable {
                if (!impl.isConcurrent()) return;
                if (!testImplementationDetails) return;
                final ThreadLocalRandom rnd = ThreadLocalRandom.current();
                final Consumer alwaysThrows = e -> { throw new AssertionError(); };
                final Collection c = impl.emptyCollection();
                final Spliterator s = c.spliterator();
                if (rnd.nextBoolean()) {
                    assertFalse(s.tryAdvance(alwaysThrows));
                } else {
                    s.forEachRemaining(alwaysThrows);
                }
                final Object one = impl.makeElement(1);
                // Spliterator should not notice added element
                c.add(one);
                if (rnd.nextBoolean()) {
                    assertFalse(s.tryAdvance(alwaysThrows));
                } else {
                    s.forEachRemaining(alwaysThrows);
                }
            }

        In LTQ and CLQ, constructions of the form

                    if (!exhausted &&
                        ((p = current) != null || (p = firstDataNode()) != null) &&

        fail to set exhausted to true when firstDataNode returns null.

        Here's idiomatic code to get this right:

                private void setCurrent(Node p) {
                    if ((current = p) == null)
                        exhausted = true;
                }

                private Node current() {
                    Node p;
                    if ((p = current) == null && !exhausted)
                        setCurrent(p = firstDataNode());
                    return p;
                }
        ...
                    Node p;
                    if ((p = current()) != null) {


        In PriorityBlockingQueue, the lazy init code for forEachRemaining does not call getFence (why?), and fails to set array, so a subsequent call to forEachRemaining might return more elements!

                public void forEachRemaining(Consumer<? super E> action) {
                    Object[] a; int i, hi; // hoist accesses and checks from loop
                    if (action == null)
                        throw new NullPointerException();
                    if ((a = array) == null)
                        fence = (a = toArray()).length;

          Activity

          Hide
          hgupdate HG Updates added a comment -
          URL: http://hg.openjdk.java.net/jdk9/dev/jdk/rev/06bdfec766f4
          User: martin
          Date: 2017-02-03 21:32:18 +0000
          Show
          hgupdate HG Updates added a comment - URL: http://hg.openjdk.java.net/jdk9/dev/jdk/rev/06bdfec766f4 User: martin Date: 2017-02-03 21:32:18 +0000
          Hide
          hgupdate HG Updates added a comment -
          URL: http://hg.openjdk.java.net/jdk9/jdk9/jdk/rev/06bdfec766f4
          User: lana
          Date: 2017-02-08 19:31:50 +0000
          Show
          hgupdate HG Updates added a comment - URL: http://hg.openjdk.java.net/jdk9/jdk9/jdk/rev/06bdfec766f4 User: lana Date: 2017-02-08 19:31:50 +0000

            People

            • Assignee:
              martin Martin Buchholz
              Reporter:
              martin Martin Buchholz
            • Votes:
              0 Vote for this issue
              Watchers:
              5 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: