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

LinkedBlockingDeque spliterator needs to support node self-linking

    Details

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

      Description

      LinkedBlockingDeque Nodes can be self-linked while still in use, in which case traversers must reset iteration to queue.first. But the spliterator is written without that awareness, leading to infloops in case of concurrent access.

        Issue Links

          Activity

          Hide
          martin Martin Buchholz added a comment -
          Here's a repro in a jsr166 CVS workspace, showing off the awesome DetectRaces test.

           $ cvs update -D 2016-10-01 src/main/java/util/concurrent/LinkedBlockingDeque.java && ant -Djsr166.tckTestClass=LinkedBlockingDequeTest -Djsr166.runsPerTest=100 -Djsr166.methodFilter=DetectRaces tck; cvs update -A src/main/java/util/concurrent/LinkedBlockingDeque.java
          Buildfile: /usr/local/google/home/martinrb/jsr166/sublist/build.xml

          configure-compiler:

          compile:

          jar:

          tck:
               [java] junit.framework.AssertionFailedError: ExecutorService java.util.concurrent.ThreadPoolExecutor@71bbf57e[Shutting down, pool size = 6, active threads = 6, queued tasks = 0, completed tasks = 0] did not terminate in a timely manner
               [java] ------ stacktrace dump start ------
               [java] "pool-6-thread-6" prio=5 Id=33 WAITING on java.util.concurrent.locks.ReentrantLock$NonfairSync@6a1aab78 owned by "pool-6-thread-3" Id=30
               [java] at java.base/jdk.internal.misc.Unsafe.park(Native Method)
               [java] - waiting on java.util.concurrent.locks.ReentrantLock$NonfairSync@6a1aab78
               [java] at java.base/java.util.concurrent.locks.LockSupport.park(LockSupport.java:163)
               [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(AbstractQueuedSynchronizer.java:842)
               [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(AbstractQueuedSynchronizer.java:874)
               [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(AbstractQueuedSynchronizer.java:1197)
               [java] at java.base/java.util.concurrent.locks.ReentrantLock.lock(ReentrantLock.java:238)
               [java] at java.base/java.util.concurrent.LinkedBlockingDeque.offerLast(LinkedBlockingDeque.java:331)
               [java] at java.base/java.util.concurrent.LinkedBlockingDeque.addLast(LinkedBlockingDeque.java:305)
               [java] ...
               [java]
               [java] Number of locked synchronizers = 1
               [java] - java.util.concurrent.ThreadPoolExecutor$Worker@6c49835d
               [java]
               [java] "pool-6-thread-5" prio=5 Id=32 WAITING on java.util.concurrent.locks.ReentrantLock$NonfairSync@6a1aab78 owned by "pool-6-thread-3" Id=30
               [java] at java.base/jdk.internal.misc.Unsafe.park(Native Method)
               [java] - waiting on java.util.concurrent.locks.ReentrantLock$NonfairSync@6a1aab78
               [java] at java.base/java.util.concurrent.locks.LockSupport.park(LockSupport.java:163)
               [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(AbstractQueuedSynchronizer.java:842)
               [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(AbstractQueuedSynchronizer.java:874)
               [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(AbstractQueuedSynchronizer.java:1197)
               [java] at java.base/java.util.concurrent.locks.ReentrantLock.lock(ReentrantLock.java:238)
               [java] at java.base/java.util.concurrent.LinkedBlockingDeque.offerLast(LinkedBlockingDeque.java:331)
               [java] at java.base/java.util.concurrent.LinkedBlockingDeque.addLast(LinkedBlockingDeque.java:305)
               [java] ...
               [java]
               [java] Number of locked synchronizers = 1
               [java] - java.util.concurrent.ThreadPoolExecutor$Worker@5a8806ef
               [java]
               [java] "pool-6-thread-4" prio=5 Id=31 WAITING on java.util.concurrent.locks.ReentrantLock$NonfairSync@6a1aab78 owned by "pool-6-thread-3" Id=30
               [java] at java.base/jdk.internal.misc.Unsafe.park(Native Method)
               [java] - waiting on java.util.concurrent.locks.ReentrantLock$NonfairSync@6a1aab78
               [java] at java.base/java.util.concurrent.locks.LockSupport.park(LockSupport.java:163)
               [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(AbstractQueuedSynchronizer.java:842)
               [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(AbstractQueuedSynchronizer.java:874)
               [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(AbstractQueuedSynchronizer.java:1197)
               [java] at java.base/java.util.concurrent.locks.ReentrantLock.lock(ReentrantLock.java:238)
               [java] at java.base/java.util.concurrent.LinkedBlockingDeque$AbstractItr.<init>(LinkedBlockingDeque.java:1015)
               [java] at java.base/java.util.concurrent.LinkedBlockingDeque$Itr.<init>(LinkedBlockingDeque.java:1089)
               [java] ...
               [java]
               [java] Number of locked synchronizers = 1
               [java] - java.util.concurrent.ThreadPoolExecutor$Worker@9660f4e
               [java]
               [java] "pool-6-thread-3" prio=5 Id=30 RUNNABLE
               [java] at java.base/java.util.concurrent.LinkedBlockingDeque$LBDSpliterator.tryAdvance(LinkedBlockingDeque.java:1196)
               [java] at Collection8Test.lambda$testDetectRaces$57(Collection8Test.java:561)
               [java] at Collection8Test$$Lambda$19/1604125387.run(Unknown Source)
               [java] at Collection8Test.lambda$testDetectRaces$62(Collection8Test.java:585)
               [java] at Collection8Test$$Lambda$29/1740189450.run(Unknown Source)
               [java] at java.base/java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:485)
               [java] at java.base/java.util.concurrent.FutureTask.run(FutureTask.java:235)
               [java] at java.base/java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1132)
               [java] ...
               [java]
               [java] Number of locked synchronizers = 2
               [java] - java.util.concurrent.locks.ReentrantLock$NonfairSync@6a1aab78
               [java] - java.util.concurrent.ThreadPoolExecutor$Worker@7c29daf3
               [java]
               [java] "pool-6-thread-2" prio=5 Id=29 WAITING on java.util.concurrent.locks.ReentrantLock$NonfairSync@6a1aab78 owned by "pool-6-thread-3" Id=30
               [java] at java.base/jdk.internal.misc.Unsafe.park(Native Method)
               [java] - waiting on java.util.concurrent.locks.ReentrantLock$NonfairSync@6a1aab78
               [java] at java.base/java.util.concurrent.locks.LockSupport.park(LockSupport.java:163)
               [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(AbstractQueuedSynchronizer.java:842)
               [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(AbstractQueuedSynchronizer.java:874)
               [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(AbstractQueuedSynchronizer.java:1197)
               [java] at java.base/java.util.concurrent.locks.ReentrantLock.lock(ReentrantLock.java:238)
               [java] at java.base/java.util.concurrent.LinkedBlockingDeque.size(LinkedBlockingDeque.java:778)
               [java] at java.base/java.util.concurrent.LinkedBlockingDeque$LBDSpliterator.<init>(LinkedBlockingDeque.java:1110)
               [java] ...
               [java]
               [java] Number of locked synchronizers = 1
               [java] - java.util.concurrent.ThreadPoolExecutor$Worker@4bbfb90a
               [java]
               [java] "pool-6-thread-1" prio=5 Id=28 WAITING on java.util.concurrent.locks.ReentrantLock$NonfairSync@6a1aab78 owned by "pool-6-thread-3" Id=30
               [java] at java.base/jdk.internal.misc.Unsafe.park(Native Method)
               [java] - waiting on java.util.concurrent.locks.ReentrantLock$NonfairSync@6a1aab78
               [java] at java.base/java.util.concurrent.locks.LockSupport.park(LockSupport.java:163)
               [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(AbstractQueuedSynchronizer.java:842)
               [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(AbstractQueuedSynchronizer.java:874)
               [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(AbstractQueuedSynchronizer.java:1197)
               [java] at java.base/java.util.concurrent.locks.ReentrantLock.lock(ReentrantLock.java:238)
               [java] at java.base/java.util.concurrent.LinkedBlockingDeque.size(LinkedBlockingDeque.java:778)
               [java] at java.base/java.util.concurrent.LinkedBlockingDeque$LBDSpliterator.<init>(LinkedBlockingDeque.java:1110)
               [java] ...
               [java]
               [java] Number of locked synchronizers = 1
               [java] - java.util.concurrent.ThreadPoolExecutor$Worker@7494e528
               [java]
               [java] "Common-Cleaner" daemon prio=8 Id=10 TIMED_WAITING on java.lang.ref.ReferenceQueue$Lock@5891e32e
               [java] at java.base/java.lang.Object.wait(Native Method)
               [java] - waiting on java.lang.ref.ReferenceQueue$Lock@5891e32e
               [java] at java.base/java.lang.ref.ReferenceQueue.remove(ReferenceQueue.java:151)
               [java] at java.base/jdk.internal.ref.CleanerImpl.run(CleanerImpl.java:148)
               [java] at java.base/java.lang.Thread.run(Thread.java:844)
               [java] at java.base/jdk.internal.misc.InnocuousThread.run(InnocuousThread.java:122)
               [java]
               [java] "Reference Handler" daemon prio=10 Id=2 RUNNABLE
               [java] at java.base/java.lang.ref.Reference.waitForReferencePendingList(Native Method)
               [java] at java.base/java.lang.ref.Reference.processPendingReferences(Reference.java:163)
               [java] at java.base/java.lang.ref.Reference.access$000(Reference.java:44)
               [java] at java.base/java.lang.ref.Reference$ReferenceHandler.run(Reference.java:138)
               [java]
               [java] "main" prio=5 Id=1 RUNNABLE
               [java] at java.management/sun.management.ThreadImpl.dumpThreads0(Native Method)
               [java] at java.management/sun.management.ThreadImpl.dumpAllThreads(ThreadImpl.java:479)
               [java] at JSR166TestCase.dumpTestThreads(JSR166TestCase.java:1012)
               [java] at JSR166TestCase.threadRecordFailure(JSR166TestCase.java:666)
               [java] at JSR166TestCase.threadFail(JSR166TestCase.java:745)
               [java] at JSR166TestCase.joinPool(JSR166TestCase.java:951)
               [java] at JSR166TestCase$PoolCleaner.close(JSR166TestCase.java:895)
               [java] at JSR166TestCase$PoolCleanerWithReleaser.close(JSR166TestCase.java:911)
               [java] ...
               [java]
               [java] ------ stacktrace dump end ------
               [java] FThere was 1 failure:
               [java] 1) testDetectRaces(Collection8Test)junit.framework.AssertionFailedError: ExecutorService java.util.concurrent.ThreadPoolExecutor@71bbf57e[Shutting down, pool size = 6, active threads = 6, queued tasks = 0, completed tasks = 0] did not terminate in a timely manner
               [java] at JSR166TestCase.threadFail(JSR166TestCase.java:743)
               [java] at JSR166TestCase.joinPool(JSR166TestCase.java:951)
               [java] at JSR166TestCase$PoolCleaner.close(JSR166TestCase.java:895)
               [java] at JSR166TestCase$PoolCleanerWithReleaser.close(JSR166TestCase.java:911)
               [java] at Collection8Test.$closeResource(Collection8Test.java:502)
               [java] at Collection8Test.testDetectRaces(Collection8Test.java:596)
               [java] at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
               [java] at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
               [java] at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
               [java] at JSR166TestCase.runTest(JSR166TestCase.java:303)
               [java] at JSR166TestCase.runBare(JSR166TestCase.java:294)
               [java] at JSR166TestCase.main(JSR166TestCase.java:367)
               [java] at LinkedBlockingDequeTest.main(LinkedBlockingDequeTest.java:40)
               [java] Time: 20.685
               [java]
               [java] FAILURES!!!
               [java] Tests run: 145, Failures: 1, Errors: 0
               [java]
          Show
          martin Martin Buchholz added a comment - Here's a repro in a jsr166 CVS workspace, showing off the awesome DetectRaces test.  $ cvs update -D 2016-10-01 src/main/java/util/concurrent/LinkedBlockingDeque.java && ant -Djsr166.tckTestClass=LinkedBlockingDequeTest -Djsr166.runsPerTest=100 -Djsr166.methodFilter=DetectRaces tck; cvs update -A src/main/java/util/concurrent/LinkedBlockingDeque.java Buildfile: /usr/local/google/home/martinrb/jsr166/sublist/build.xml configure-compiler: compile: jar: tck:      [java] junit.framework.AssertionFailedError: ExecutorService java.util.concurrent.ThreadPoolExecutor@71bbf57e [Shutting down, pool size = 6, active threads = 6, queued tasks = 0, completed tasks = 0] did not terminate in a timely manner      [java] ------ stacktrace dump start ------      [java] "pool-6-thread-6" prio=5 Id=33 WAITING on java.util.concurrent.locks.ReentrantLock$ NonfairSync@6a1aab78 owned by "pool-6-thread-3" Id=30      [java] at java.base/jdk.internal.misc.Unsafe.park(Native Method)      [java] - waiting on java.util.concurrent.locks.ReentrantLock$ NonfairSync@6a1aab78      [java] at java.base/java.util.concurrent.locks.LockSupport.park(LockSupport.java:163)      [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(AbstractQueuedSynchronizer.java:842)      [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(AbstractQueuedSynchronizer.java:874)      [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(AbstractQueuedSynchronizer.java:1197)      [java] at java.base/java.util.concurrent.locks.ReentrantLock.lock(ReentrantLock.java:238)      [java] at java.base/java.util.concurrent.LinkedBlockingDeque.offerLast(LinkedBlockingDeque.java:331)      [java] at java.base/java.util.concurrent.LinkedBlockingDeque.addLast(LinkedBlockingDeque.java:305)      [java] ...      [java]      [java] Number of locked synchronizers = 1      [java] - java.util.concurrent.ThreadPoolExecutor$ Worker@6c49835d      [java]      [java] "pool-6-thread-5" prio=5 Id=32 WAITING on java.util.concurrent.locks.ReentrantLock$ NonfairSync@6a1aab78 owned by "pool-6-thread-3" Id=30      [java] at java.base/jdk.internal.misc.Unsafe.park(Native Method)      [java] - waiting on java.util.concurrent.locks.ReentrantLock$ NonfairSync@6a1aab78      [java] at java.base/java.util.concurrent.locks.LockSupport.park(LockSupport.java:163)      [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(AbstractQueuedSynchronizer.java:842)      [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(AbstractQueuedSynchronizer.java:874)      [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(AbstractQueuedSynchronizer.java:1197)      [java] at java.base/java.util.concurrent.locks.ReentrantLock.lock(ReentrantLock.java:238)      [java] at java.base/java.util.concurrent.LinkedBlockingDeque.offerLast(LinkedBlockingDeque.java:331)      [java] at java.base/java.util.concurrent.LinkedBlockingDeque.addLast(LinkedBlockingDeque.java:305)      [java] ...      [java]      [java] Number of locked synchronizers = 1      [java] - java.util.concurrent.ThreadPoolExecutor$ Worker@5a8806ef      [java]      [java] "pool-6-thread-4" prio=5 Id=31 WAITING on java.util.concurrent.locks.ReentrantLock$ NonfairSync@6a1aab78 owned by "pool-6-thread-3" Id=30      [java] at java.base/jdk.internal.misc.Unsafe.park(Native Method)      [java] - waiting on java.util.concurrent.locks.ReentrantLock$ NonfairSync@6a1aab78      [java] at java.base/java.util.concurrent.locks.LockSupport.park(LockSupport.java:163)      [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(AbstractQueuedSynchronizer.java:842)      [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(AbstractQueuedSynchronizer.java:874)      [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(AbstractQueuedSynchronizer.java:1197)      [java] at java.base/java.util.concurrent.locks.ReentrantLock.lock(ReentrantLock.java:238)      [java] at java.base/java.util.concurrent.LinkedBlockingDeque$AbstractItr.<init>(LinkedBlockingDeque.java:1015)      [java] at java.base/java.util.concurrent.LinkedBlockingDeque$Itr.<init>(LinkedBlockingDeque.java:1089)      [java] ...      [java]      [java] Number of locked synchronizers = 1      [java] - java.util.concurrent.ThreadPoolExecutor$ Worker@9660f4e      [java]      [java] "pool-6-thread-3" prio=5 Id=30 RUNNABLE      [java] at java.base/java.util.concurrent.LinkedBlockingDeque$LBDSpliterator.tryAdvance(LinkedBlockingDeque.java:1196)      [java] at Collection8Test.lambda$testDetectRaces$57(Collection8Test.java:561)      [java] at Collection8Test$$Lambda$19/1604125387.run(Unknown Source)      [java] at Collection8Test.lambda$testDetectRaces$62(Collection8Test.java:585)      [java] at Collection8Test$$Lambda$29/1740189450.run(Unknown Source)      [java] at java.base/java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:485)      [java] at java.base/java.util.concurrent.FutureTask.run(FutureTask.java:235)      [java] at java.base/java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1132)      [java] ...      [java]      [java] Number of locked synchronizers = 2      [java] - java.util.concurrent.locks.ReentrantLock$ NonfairSync@6a1aab78      [java] - java.util.concurrent.ThreadPoolExecutor$ Worker@7c29daf3      [java]      [java] "pool-6-thread-2" prio=5 Id=29 WAITING on java.util.concurrent.locks.ReentrantLock$ NonfairSync@6a1aab78 owned by "pool-6-thread-3" Id=30      [java] at java.base/jdk.internal.misc.Unsafe.park(Native Method)      [java] - waiting on java.util.concurrent.locks.ReentrantLock$ NonfairSync@6a1aab78      [java] at java.base/java.util.concurrent.locks.LockSupport.park(LockSupport.java:163)      [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(AbstractQueuedSynchronizer.java:842)      [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(AbstractQueuedSynchronizer.java:874)      [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(AbstractQueuedSynchronizer.java:1197)      [java] at java.base/java.util.concurrent.locks.ReentrantLock.lock(ReentrantLock.java:238)      [java] at java.base/java.util.concurrent.LinkedBlockingDeque.size(LinkedBlockingDeque.java:778)      [java] at java.base/java.util.concurrent.LinkedBlockingDeque$LBDSpliterator.<init>(LinkedBlockingDeque.java:1110)      [java] ...      [java]      [java] Number of locked synchronizers = 1      [java] - java.util.concurrent.ThreadPoolExecutor$ Worker@4bbfb90a      [java]      [java] "pool-6-thread-1" prio=5 Id=28 WAITING on java.util.concurrent.locks.ReentrantLock$ NonfairSync@6a1aab78 owned by "pool-6-thread-3" Id=30      [java] at java.base/jdk.internal.misc.Unsafe.park(Native Method)      [java] - waiting on java.util.concurrent.locks.ReentrantLock$ NonfairSync@6a1aab78      [java] at java.base/java.util.concurrent.locks.LockSupport.park(LockSupport.java:163)      [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(AbstractQueuedSynchronizer.java:842)      [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(AbstractQueuedSynchronizer.java:874)      [java] at java.base/java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(AbstractQueuedSynchronizer.java:1197)      [java] at java.base/java.util.concurrent.locks.ReentrantLock.lock(ReentrantLock.java:238)      [java] at java.base/java.util.concurrent.LinkedBlockingDeque.size(LinkedBlockingDeque.java:778)      [java] at java.base/java.util.concurrent.LinkedBlockingDeque$LBDSpliterator.<init>(LinkedBlockingDeque.java:1110)      [java] ...      [java]      [java] Number of locked synchronizers = 1      [java] - java.util.concurrent.ThreadPoolExecutor$ Worker@7494e528      [java]      [java] "Common-Cleaner" daemon prio=8 Id=10 TIMED_WAITING on java.lang.ref.ReferenceQueue$ Lock@5891e32e      [java] at java.base/java.lang.Object.wait(Native Method)      [java] - waiting on java.lang.ref.ReferenceQueue$ Lock@5891e32e      [java] at java.base/java.lang.ref.ReferenceQueue.remove(ReferenceQueue.java:151)      [java] at java.base/jdk.internal.ref.CleanerImpl.run(CleanerImpl.java:148)      [java] at java.base/java.lang.Thread.run(Thread.java:844)      [java] at java.base/jdk.internal.misc.InnocuousThread.run(InnocuousThread.java:122)      [java]      [java] "Reference Handler" daemon prio=10 Id=2 RUNNABLE      [java] at java.base/java.lang.ref.Reference.waitForReferencePendingList(Native Method)      [java] at java.base/java.lang.ref.Reference.processPendingReferences(Reference.java:163)      [java] at java.base/java.lang.ref.Reference.access$000(Reference.java:44)      [java] at java.base/java.lang.ref.Reference$ReferenceHandler.run(Reference.java:138)      [java]      [java] "main" prio=5 Id=1 RUNNABLE      [java] at java.management/sun.management.ThreadImpl.dumpThreads0(Native Method)      [java] at java.management/sun.management.ThreadImpl.dumpAllThreads(ThreadImpl.java:479)      [java] at JSR166TestCase.dumpTestThreads(JSR166TestCase.java:1012)      [java] at JSR166TestCase.threadRecordFailure(JSR166TestCase.java:666)      [java] at JSR166TestCase.threadFail(JSR166TestCase.java:745)      [java] at JSR166TestCase.joinPool(JSR166TestCase.java:951)      [java] at JSR166TestCase$PoolCleaner.close(JSR166TestCase.java:895)      [java] at JSR166TestCase$PoolCleanerWithReleaser.close(JSR166TestCase.java:911)      [java] ...      [java]      [java] ------ stacktrace dump end ------      [java] FThere was 1 failure:      [java] 1) testDetectRaces(Collection8Test)junit.framework.AssertionFailedError: ExecutorService java.util.concurrent.ThreadPoolExecutor@71bbf57e [Shutting down, pool size = 6, active threads = 6, queued tasks = 0, completed tasks = 0] did not terminate in a timely manner      [java] at JSR166TestCase.threadFail(JSR166TestCase.java:743)      [java] at JSR166TestCase.joinPool(JSR166TestCase.java:951)      [java] at JSR166TestCase$PoolCleaner.close(JSR166TestCase.java:895)      [java] at JSR166TestCase$PoolCleanerWithReleaser.close(JSR166TestCase.java:911)      [java] at Collection8Test.$closeResource(Collection8Test.java:502)      [java] at Collection8Test.testDetectRaces(Collection8Test.java:596)      [java] at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)      [java] at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)      [java] at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)      [java] at JSR166TestCase.runTest(JSR166TestCase.java:303)      [java] at JSR166TestCase.runBare(JSR166TestCase.java:294)      [java] at JSR166TestCase.main(JSR166TestCase.java:367)      [java] at LinkedBlockingDequeTest.main(LinkedBlockingDequeTest.java:40)      [java] Time: 20.685      [java]      [java] FAILURES!!!      [java] Tests run: 145, Failures: 1, Errors: 0      [java]
          Hide
          martin Martin Buchholz added a comment -
          http://cr.openjdk.java.net/~martin/webrevs/openjdk9/jsr166-jdk9-integration/Collection-optimization/src/java.base/share/classes/java/util/concurrent/LinkedBlockingDeque.java.udiff.html

          I now notice that the spliterator here is implemented in a late-binding-style way, but in fact we can probably simplify the implementation by eagerly setting current to queue.first; we anyways have to handle first getting dequeued; then current == null unambiguously means exhausted. Which means we can get rid of boolean exhausted field?
          Show
          martin Martin Buchholz added a comment - http://cr.openjdk.java.net/~martin/webrevs/openjdk9/jsr166-jdk9-integration/Collection-optimization/src/java.base/share/classes/java/util/concurrent/LinkedBlockingDeque.java.udiff.html I now notice that the spliterator here is implemented in a late-binding-style way, but in fact we can probably simplify the implementation by eagerly setting current to queue.first; we anyways have to handle first getting dequeued; then current == null unambiguously means exhausted. Which means we can get rid of boolean exhausted field?
          Hide
          martin Martin Buchholz added a comment -
          Updating to a slightly cleaner version, keeping exhausted field for now...
          Show
          martin Martin Buchholz added a comment - Updating to a slightly cleaner version, keeping exhausted field for now...
          Hide
          martin Martin Buchholz added a comment -
          Here's a seemingly working version that gets rid of the "exhausted" field. Somewhat less errorprone as expected.

          There is a small change in behavior: If the collection is empty when the spliterator is created then it will never yield any elements, even if any are added before first use. But this is consistent with iterator behavior.

          Paul: Does anyone care about this sort of subtlety ?

          --- src/main/java/util/concurrent/LinkedBlockingDeque.java 17 Nov 2016 04:13:42 -0000 1.63
          +++ src/main/java/util/concurrent/LinkedBlockingDeque.java 17 Nov 2016 04:46:20 -0000
          @@ -1101,12 +1101,12 @@
               static final class LBDSpliterator<E> implements Spliterator<E> {
                   static final int MAX_BATCH = 1 << 25; // max batch array size;
                   final LinkedBlockingDeque<E> queue;
          - Node<E> current; // current node; null until initialized
          + Node<E> current; // current node; null means exhausted
                   int batch; // batch size for splits
          - boolean exhausted; // true when no more nodes
                   long est; // size estimate
                   LBDSpliterator(LinkedBlockingDeque<E> queue) {
                       this.queue = queue;
          + this.current = queue.first;
                       this.est = queue.size();
                   }
           
          @@ -1117,9 +1117,8 @@
                       final LinkedBlockingDeque<E> q = this.queue;
                       int b = batch;
                       int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1;
          - if (!exhausted &&
          - (((h = current) != null && h != h.next)
          - || (h = q.first) != null)
          + if ((h = current) != null
          + && ((h != h.next) || (h = q.first) != null)
                           && h.next != null) {
                           Object[] a = new Object[n];
                           final ReentrantLock lock = q.lock;
          @@ -1127,17 +1126,15 @@
                           Node<E> p = current;
                           lock.lock();
                           try {
          - if (((p != null && p != p.next) || (p = q.first) != null)
          + if ((p != p.next || (p = q.first) != null)
                                   && p.item != null)
                                   for (; p != null && i < n; p = p.next)
                                       a[i++] = p.item;
                           } finally {
                               lock.unlock();
                           }
          - if ((current = p) == null) {
          + if ((current = p) == null)
                               est = 0L;
          - exhausted = true;
          - }
                           else if ((est -= i) < 0L)
                               est = 0L;
                           if (i > 0) {
          @@ -1153,18 +1150,17 @@
           
                   public void forEachRemaining(Consumer<? super E> action) {
                       if (action == null) throw new NullPointerException();
          - if (exhausted)
          + Node<E> p;
          + if ((p = current) == null)
                           return;
          - exhausted = true;
                       final LinkedBlockingDeque<E> q = this.queue;
                       final ReentrantLock lock = q.lock;
          - Node<E> p = current;
                       current = null;
                       do {
                           E e = null;
                           lock.lock();
                           try {
          - if ((p != null && p != p.next) || (p = q.first) != null) {
          + if (p != p.next || (p = q.first) != null) {
                                   e = p.item;
                                   p = p.next;
                               }
          @@ -1178,22 +1174,22 @@
           
                   public boolean tryAdvance(Consumer<? super E> action) {
                       if (action == null) throw new NullPointerException();
          - if (exhausted)
          + Node<E> p;
          + if ((p = current) == null)
                           return false;
                       final LinkedBlockingDeque<E> q = this.queue;
                       final ReentrantLock lock = q.lock;
          - Node<E> p = current;
                       E e = null;
                       lock.lock();
                       try {
          - if ((p != null && p != p.next) || (p = q.first) != null) {
          + if (p != p.next || (p = q.first) != null) {
                               e = p.item;
                               p = p.next;
                           }
                       } finally {
                           lock.unlock();
                       }
          - exhausted = ((current = p) == null);
          + current = p;
                       if (e == null)
                           return false;
                       action.accept(e);
          Show
          martin Martin Buchholz added a comment - Here's a seemingly working version that gets rid of the "exhausted" field. Somewhat less errorprone as expected. There is a small change in behavior: If the collection is empty when the spliterator is created then it will never yield any elements, even if any are added before first use. But this is consistent with iterator behavior. Paul: Does anyone care about this sort of subtlety ? --- src/main/java/util/concurrent/LinkedBlockingDeque.java 17 Nov 2016 04:13:42 -0000 1.63 +++ src/main/java/util/concurrent/LinkedBlockingDeque.java 17 Nov 2016 04:46:20 -0000 @@ -1101,12 +1101,12 @@      static final class LBDSpliterator<E> implements Spliterator<E> {          static final int MAX_BATCH = 1 << 25; // max batch array size;          final LinkedBlockingDeque<E> queue; - Node<E> current; // current node; null until initialized + Node<E> current; // current node; null means exhausted          int batch; // batch size for splits - boolean exhausted; // true when no more nodes          long est; // size estimate          LBDSpliterator(LinkedBlockingDeque<E> queue) {              this.queue = queue; + this.current = queue.first;              this.est = queue.size();          }   @@ -1117,9 +1117,8 @@              final LinkedBlockingDeque<E> q = this.queue;              int b = batch;              int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1; - if (!exhausted && - (((h = current) != null && h != h.next) - || (h = q.first) != null) + if ((h = current) != null + && ((h != h.next) || (h = q.first) != null)                  && h.next != null) {                  Object[] a = new Object[n];                  final ReentrantLock lock = q.lock; @@ -1127,17 +1126,15 @@                  Node<E> p = current;                  lock.lock();                  try { - if (((p != null && p != p.next) || (p = q.first) != null) + if ((p != p.next || (p = q.first) != null)                          && p.item != null)                          for (; p != null && i < n; p = p.next)                              a[i++] = p.item;                  } finally {                      lock.unlock();                  } - if ((current = p) == null) { + if ((current = p) == null)                      est = 0L; - exhausted = true; - }                  else if ((est -= i) < 0L)                      est = 0L;                  if (i > 0) { @@ -1153,18 +1150,17 @@            public void forEachRemaining(Consumer<? super E> action) {              if (action == null) throw new NullPointerException(); - if (exhausted) + Node<E> p; + if ((p = current) == null)                  return; - exhausted = true;              final LinkedBlockingDeque<E> q = this.queue;              final ReentrantLock lock = q.lock; - Node<E> p = current;              current = null;              do {                  E e = null;                  lock.lock();                  try { - if ((p != null && p != p.next) || (p = q.first) != null) { + if (p != p.next || (p = q.first) != null) {                          e = p.item;                          p = p.next;                      } @@ -1178,22 +1174,22 @@            public boolean tryAdvance(Consumer<? super E> action) {              if (action == null) throw new NullPointerException(); - if (exhausted) + Node<E> p; + if ((p = current) == null)                  return false;              final LinkedBlockingDeque<E> q = this.queue;              final ReentrantLock lock = q.lock; - Node<E> p = current;              E e = null;              lock.lock();              try { - if ((p != null && p != p.next) || (p = q.first) != null) { + if (p != p.next || (p = q.first) != null) {                      e = p.item;                      p = p.next;                  }              } finally {                  lock.unlock();              } - exhausted = ((current = p) == null); + current = p;              if (e == null)                  return false;              action.accept(e);
          Hide
          martin Martin Buchholz added a comment -
          Given that late-binding is a feature in many spliterators, and the lazy init was a design goal of spliterators in general, and because compatibility wins unless your replacement is much better, I'm staying with init on first access. OTOH, we should have tests that explicitly check for the lazy init property, and we don't.
          Show
          martin Martin Buchholz added a comment - Given that late-binding is a feature in many spliterators, and the lazy init was a design goal of spliterators in general, and because compatibility wins unless your replacement is much better, I'm staying with init on first access. OTOH, we should have tests that explicitly check for the lazy init property, and we don't.
          Hide
          martin Martin Buchholz added a comment -
          The final LinkedBlockingDeque field in LBDSpliterator strongly suggests that LBDSpliterator should be an inner class, so ... converting:

          --- src/main/java/util/concurrent/LinkedBlockingDeque.java 17 Nov 2016 04:13:42 -0000 1.63
          +++ src/main/java/util/concurrent/LinkedBlockingDeque.java 18 Nov 2016 22:24:58 -0000
          @@ -1098,36 +1098,32 @@
               }
           
               /** A customized variant of Spliterators.IteratorSpliterator */
          - static final class LBDSpliterator<E> implements Spliterator<E> {
          + private final class LBDSpliterator implements Spliterator<E> {
                   static final int MAX_BATCH = 1 << 25; // max batch array size;
          - final LinkedBlockingDeque<E> queue;
                   Node<E> current; // current node; null until initialized
                   int batch; // batch size for splits
                   boolean exhausted; // true when no more nodes
                   long est; // size estimate
          - LBDSpliterator(LinkedBlockingDeque<E> queue) {
          - this.queue = queue;
          - this.est = queue.size();
          - }
          +
          + LBDSpliterator() { est = size(); }
           
                   public long estimateSize() { return est; }
           
                   public Spliterator<E> trySplit() {
                       Node<E> h;
          - final LinkedBlockingDeque<E> q = this.queue;
                       int b = batch;
                       int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1;
                       if (!exhausted &&
                           (((h = current) != null && h != h.next)
          - || (h = q.first) != null)
          + || (h = first) != null)
                           && h.next != null) {
                           Object[] a = new Object[n];
          - final ReentrantLock lock = q.lock;
          + final ReentrantLock lock = LinkedBlockingDeque.this.lock;
                           int i = 0;
                           Node<E> p = current;
                           lock.lock();
                           try {
          - if (((p != null && p != p.next) || (p = q.first) != null)
          + if (((p != null && p != p.next) || (p = first) != null)
                                   && p.item != null)
                                   for (; p != null && i < n; p = p.next)
                                       a[i++] = p.item;
          @@ -1156,15 +1152,14 @@
                       if (exhausted)
                           return;
                       exhausted = true;
          - final LinkedBlockingDeque<E> q = this.queue;
          - final ReentrantLock lock = q.lock;
          + final ReentrantLock lock = LinkedBlockingDeque.this.lock;
                       Node<E> p = current;
                       current = null;
                       do {
                           E e = null;
                           lock.lock();
                           try {
          - if ((p != null && p != p.next) || (p = q.first) != null) {
          + if ((p != null && p != p.next) || (p = first) != null) {
                                   e = p.item;
                                   p = p.next;
                               }
          @@ -1180,13 +1175,12 @@
                       if (action == null) throw new NullPointerException();
                       if (exhausted)
                           return false;
          - final LinkedBlockingDeque<E> q = this.queue;
          - final ReentrantLock lock = q.lock;
          + final ReentrantLock lock = LinkedBlockingDeque.this.lock;
                       Node<E> p = current;
                       E e = null;
                       lock.lock();
                       try {
          - if ((p != null && p != p.next) || (p = q.first) != null) {
          + if ((p != null && p != p.next) || (p = first) != null) {
                               e = p.item;
                               p = p.next;
                           }
          @@ -1224,7 +1218,7 @@
                * @since 1.8
                */
               public Spliterator<E> spliterator() {
          - return new LBDSpliterator<E>(this);
          + return new LBDSpliterator();
               }
           
               /**
          Show
          martin Martin Buchholz added a comment - The final LinkedBlockingDeque field in LBDSpliterator strongly suggests that LBDSpliterator should be an inner class, so ... converting: --- src/main/java/util/concurrent/LinkedBlockingDeque.java 17 Nov 2016 04:13:42 -0000 1.63 +++ src/main/java/util/concurrent/LinkedBlockingDeque.java 18 Nov 2016 22:24:58 -0000 @@ -1098,36 +1098,32 @@      }        /** A customized variant of Spliterators.IteratorSpliterator */ - static final class LBDSpliterator<E> implements Spliterator<E> { + private final class LBDSpliterator implements Spliterator<E> {          static final int MAX_BATCH = 1 << 25; // max batch array size; - final LinkedBlockingDeque<E> queue;          Node<E> current; // current node; null until initialized          int batch; // batch size for splits          boolean exhausted; // true when no more nodes          long est; // size estimate - LBDSpliterator(LinkedBlockingDeque<E> queue) { - this.queue = queue; - this.est = queue.size(); - } + + LBDSpliterator() { est = size(); }            public long estimateSize() { return est; }            public Spliterator<E> trySplit() {              Node<E> h; - final LinkedBlockingDeque<E> q = this.queue;              int b = batch;              int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1;              if (!exhausted &&                  (((h = current) != null && h != h.next) - || (h = q.first) != null) + || (h = first) != null)                  && h.next != null) {                  Object[] a = new Object[n]; - final ReentrantLock lock = q.lock; + final ReentrantLock lock = LinkedBlockingDeque.this.lock;                  int i = 0;                  Node<E> p = current;                  lock.lock();                  try { - if (((p != null && p != p.next) || (p = q.first) != null) + if (((p != null && p != p.next) || (p = first) != null)                          && p.item != null)                          for (; p != null && i < n; p = p.next)                              a[i++] = p.item; @@ -1156,15 +1152,14 @@              if (exhausted)                  return;              exhausted = true; - final LinkedBlockingDeque<E> q = this.queue; - final ReentrantLock lock = q.lock; + final ReentrantLock lock = LinkedBlockingDeque.this.lock;              Node<E> p = current;              current = null;              do {                  E e = null;                  lock.lock();                  try { - if ((p != null && p != p.next) || (p = q.first) != null) { + if ((p != null && p != p.next) || (p = first) != null) {                          e = p.item;                          p = p.next;                      } @@ -1180,13 +1175,12 @@              if (action == null) throw new NullPointerException();              if (exhausted)                  return false; - final LinkedBlockingDeque<E> q = this.queue; - final ReentrantLock lock = q.lock; + final ReentrantLock lock = LinkedBlockingDeque.this.lock;              Node<E> p = current;              E e = null;              lock.lock();              try { - if ((p != null && p != p.next) || (p = q.first) != null) { + if ((p != null && p != p.next) || (p = first) != null) {                      e = p.item;                      p = p.next;                  } @@ -1224,7 +1218,7 @@       * @since 1.8       */      public Spliterator<E> spliterator() { - return new LBDSpliterator<E>(this); + return new LBDSpliterator();      }        /**
          Hide
          hgupdate HG Updates added a comment -
          URL: http://hg.openjdk.java.net/jdk9/dev/jdk/rev/a15610e000ba
          User: martin
          Date: 2016-11-29 08:30:02 +0000
          Show
          hgupdate HG Updates added a comment - URL: http://hg.openjdk.java.net/jdk9/dev/jdk/rev/a15610e000ba User: martin Date: 2016-11-29 08:30:02 +0000
          Hide
          hgupdate HG Updates added a comment -
          URL: http://hg.openjdk.java.net/jdk9/jdk9/jdk/rev/a15610e000ba
          User: lana
          Date: 2016-12-07 19:33:44 +0000
          Show
          hgupdate HG Updates added a comment - URL: http://hg.openjdk.java.net/jdk9/jdk9/jdk/rev/a15610e000ba User: lana Date: 2016-12-07 19:33:44 +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: