changeset 17460:3e1edf1df296

8188900: ConcurrentLinkedDeque linearizability Reviewed-by: martin, psandoz
author dl
date Fri, 13 Oct 2017 18:07:47 -0700
parents 645defa9e6e3
children b7cbf8fbe796
files src/java.base/share/classes/java/util/concurrent/ConcurrentLinkedDeque.java test/java/util/concurrent/tck/ConcurrentLinkedDequeTest.java
diffstat 2 files changed, 139 insertions(+), 37 deletions(-) [+]
line wrap: on
line diff
--- a/src/java.base/share/classes/java/util/concurrent/ConcurrentLinkedDeque.java	Tue Oct 03 13:37:01 2017 -0700
+++ b/src/java.base/share/classes/java/util/concurrent/ConcurrentLinkedDeque.java	Fri Oct 13 18:07:47 2017 -0700
@@ -231,15 +231,16 @@
      *
      * The implementation is completely directionally symmetrical,
      * except that most public methods that iterate through the list
-     * follow next pointers ("forward" direction).
+     * follow next pointers, in the "forward" direction.
      *
-     * We believe (without full proof) that all single-element deque
-     * operations (e.g., addFirst, peekLast, pollLast) are linearizable
-     * (see Herlihy and Shavit's book).  However, some combinations of
+     * We believe (without full proof) that all single-element Deque
+     * operations that operate directly at the two ends of the Deque
+     * (e.g., addFirst, peekLast, pollLast) are linearizable (see
+     * Herlihy and Shavit's book).  However, some combinations of
      * operations are known not to be linearizable.  In particular,
-     * when an addFirst(A) is racing with pollFirst() removing B, it is
-     * possible for an observer iterating over the elements to observe
-     * A B C and subsequently observe A C, even though no interior
+     * when an addFirst(A) is racing with pollFirst() removing B, it
+     * is possible for an observer iterating over the elements to
+     * observe first [A B C] and then [A C], even though no interior
      * removes are ever performed.  Nevertheless, iterators behave
      * reasonably, providing the "weakly consistent" guarantees.
      *
@@ -865,21 +866,33 @@
     }
 
     public E peekFirst() {
-        for (Node<E> p = first(); p != null; p = succ(p)) {
-            final E item;
-            if ((item = p.item) != null)
-                return item;
+        restart: for (;;) {
+            for (Node<E> first = first(), p = first;;) {
+                final E item;
+                if ((item = p.item) != null) {
+                    // recheck for linearizability
+                    if (first.prev != null) continue restart;
+                    return item;
+                }
+                if ((p = succ(p)) == null)
+                    return null;
+            }
         }
-        return null;
     }
 
     public E peekLast() {
-        for (Node<E> p = last(); p != null; p = pred(p)) {
-            final E item;
-            if ((item = p.item) != null)
-                return item;
+        restart: for (;;) {
+            for (Node<E> last = last(), p = last;;) {
+                final E item;
+                if ((item = p.item) != null) {
+                    // recheck for linearizability
+                    if (last.next != null) continue restart;
+                    return item;
+                }
+                if ((p = pred(p)) == null)
+                    return null;
+            }
         }
-        return null;
     }
 
     /**
@@ -897,27 +910,39 @@
     }
 
     public E pollFirst() {
-        for (Node<E> p = first(); p != null; p = succ(p)) {
-            final E item;
-            if ((item = p.item) != null
-                && ITEM.compareAndSet(p, item, null)) {
-                unlink(p);
-                return item;
+        restart: for (;;) {
+            for (Node<E> first = first(), p = first;;) {
+                final E item;
+                if ((item = p.item) != null) {
+                    // recheck for linearizability
+                    if (first.prev != null) continue restart;
+                    if (ITEM.compareAndSet(p, item, null)) {
+                        unlink(p);
+                        return item;
+                    }
+                }
+                if ((p = succ(p)) == null)
+                    return null;
             }
         }
-        return null;
     }
 
     public E pollLast() {
-        for (Node<E> p = last(); p != null; p = pred(p)) {
-            final E item;
-            if ((item = p.item) != null
-                && ITEM.compareAndSet(p, item, null)) {
-                unlink(p);
-                return item;
+        restart: for (;;) {
+            for (Node<E> last = last(), p = last;;) {
+                final E item;
+                if ((item = p.item) != null) {
+                    // recheck for linearizability
+                    if (last.next != null) continue restart;
+                    if (ITEM.compareAndSet(p, item, null)) {
+                        unlink(p);
+                        return item;
+                    }
+                }
+                if ((p = pred(p)) == null)
+                    return null;
             }
         }
-        return null;
     }
 
     /**
@@ -1079,14 +1104,14 @@
      * @return the number of elements in this deque
      */
     public int size() {
-        restartFromHead: for (;;) {
+        restart: for (;;) {
             int count = 0;
             for (Node<E> p = first(); p != null;) {
                 if (p.item != null)
                     if (++count == Integer.MAX_VALUE)
                         break;  // @see Collection.size()
                 if (p == (p = p.next))
-                    continue restartFromHead;
+                    continue restart;
             }
             return count;
         }
@@ -1183,7 +1208,7 @@
 
     public String toString() {
         String[] a = null;
-        restartFromHead: for (;;) {
+        restart: for (;;) {
             int charLength = 0;
             int size = 0;
             for (Node<E> p = first(); p != null;) {
@@ -1198,7 +1223,7 @@
                     charLength += s.length();
                 }
                 if (p == (p = p.next))
-                    continue restartFromHead;
+                    continue restart;
             }
 
             if (size == 0)
@@ -1210,7 +1235,7 @@
 
     private Object[] toArrayInternal(Object[] a) {
         Object[] x = a;
-        restartFromHead: for (;;) {
+        restart: for (;;) {
             int size = 0;
             for (Node<E> p = first(); p != null;) {
                 final E item;
@@ -1222,7 +1247,7 @@
                     x[size++] = item;
                 }
                 if (p == (p = p.next))
-                    continue restartFromHead;
+                    continue restart;
             }
             if (x == null)
                 return new Object[0];
--- a/test/java/util/concurrent/tck/ConcurrentLinkedDequeTest.java	Tue Oct 03 13:37:01 2017 -0700
+++ b/test/java/util/concurrent/tck/ConcurrentLinkedDequeTest.java	Fri Oct 13 18:07:47 2017 -0700
@@ -40,7 +40,10 @@
 import java.util.NoSuchElementException;
 import java.util.Queue;
 import java.util.Random;
+import java.util.concurrent.CompletableFuture;
 import java.util.concurrent.ConcurrentLinkedDeque;
+import java.util.concurrent.ThreadLocalRandom;
+import java.util.concurrent.atomic.LongAdder;
 
 import junit.framework.Test;
 import junit.framework.TestSuite;
@@ -933,4 +936,78 @@
             } catch (NullPointerException success) {}
         }
     }
+
+    /**
+     * Non-traversing Deque operations are linearizable.
+     * https://bugs.openjdk.java.net/browse/JDK-8188900
+     * ant -Djsr166.expensiveTests=true -Djsr166.tckTestClass=ConcurrentLinkedDequeTest -Djsr166.methodFilter=testBug8188900 tck
+     */
+    public void testBug8188900() {
+        final ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        final LongAdder nulls = new LongAdder(), zeros = new LongAdder();
+        for (int n = expensiveTests ? 100_000 : 10; n--> 0; ) {
+            ConcurrentLinkedDeque<Integer> d = new ConcurrentLinkedDeque<>();
+
+            boolean peek = rnd.nextBoolean();
+            Runnable getter = () -> {
+                Integer x = peek ? d.peekFirst() : d.pollFirst();
+                if (x == null) nulls.increment();
+                else if (x == 0) zeros.increment();
+                else
+                    throw new AssertionError(
+                        String.format(
+                            "unexpected value %d after %d nulls and %d zeros",
+                            x, nulls.sum(), zeros.sum()));
+            };
+
+            Runnable adder = () -> {
+                d.addFirst(0);
+                d.addLast(42);
+            };
+
+            boolean b = rnd.nextBoolean();
+            Runnable r1 = b ? getter : adder;
+            Runnable r2 = b ? adder : getter;
+            CompletableFuture<Void> f1 = CompletableFuture.runAsync(r1);
+            CompletableFuture<Void> f2 = CompletableFuture.runAsync(r2);
+            f1.join();
+            f2.join();
+        }
+    }
+
+    /**
+     * Reverse direction variant of testBug8188900
+     */
+    public void testBug8188900_reverse() {
+        final ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        final LongAdder nulls = new LongAdder(), zeros = new LongAdder();
+        for (int n = expensiveTests ? 100_000 : 10; n--> 0; ) {
+            ConcurrentLinkedDeque<Integer> d = new ConcurrentLinkedDeque<>();
+
+            boolean peek = rnd.nextBoolean();
+            Runnable getter = () -> {
+                Integer x = peek ? d.peekLast() : d.pollLast();
+                if (x == null) nulls.increment();
+                else if (x == 0) zeros.increment();
+                else
+                    throw new AssertionError(
+                        String.format(
+                            "unexpected value %d after %d nulls and %d zeros",
+                            x, nulls.sum(), zeros.sum()));
+            };
+
+            Runnable adder = () -> {
+                d.addLast(0);
+                d.addFirst(42);
+            };
+
+            boolean b = rnd.nextBoolean();
+            Runnable r1 = b ? getter : adder;
+            Runnable r2 = b ? adder : getter;
+            CompletableFuture<Void> f1 = CompletableFuture.runAsync(r1);
+            CompletableFuture<Void> f2 = CompletableFuture.runAsync(r2);
+            f1.join();
+            f2.join();
+        }
+    }
 }