JDK-8085978 : LinkedTransferQueue.spliterator can report LTQ.Node object, not T
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.util.concurrent
  • Affected Version: 8u45,9
  • Priority: P4
  • Status: Closed
  • Resolution: Fixed
  • Submitted: 2015-06-08
  • Updated: 2016-08-24
  • Resolved: 2015-06-16
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 8 JDK 9
8u60Fixed 9 b70Fixed
Description
Originally reported by Heinz Kabutz. The minimized example follows.

import java.util.Collection;
import java.util.concurrent.*;

public class LTQ {
    public static void main(String... args) throws ExecutionException, InterruptedException {
        final int REPEATS = 10_000_000;
        Collection<String> msgs = new LinkedTransferQueue<>();
        ExecutorService pool = Executors.newCachedThreadPool();
        Future<?> f1 = pool.submit(() -> {
            for (int i = 0; i < REPEATS; i++) {
                msgs.stream().forEach(System.out::println);
            }
        });
        Future<?> f2 = pool.submit(() -> {
            String alert = "msg";
            for (int i = 0; i < REPEATS; i++) {
                msgs.add(alert);
                msgs.remove(alert);
            }
        });
        pool.shutdown();
        f1.get();
        f2.get();
    }
}

$  ~/trunks/jdk9-dev/build/linux-x86_64-normal-server-release/jdk/bin/java LTQ
class java.util.concurrent.LinkedTransferQueue$Node
Exception in thread "main" java.util.concurrent.ExecutionException: java.lang.ClassCastException: java.util.concurrent.LinkedTransferQueue$Node cannot be cast to java.lang.String
	at java.util.concurrent.FutureTask.report(FutureTask.java:122)
	at java.util.concurrent.FutureTask.get(FutureTask.java:192)
	at LTQ.main(LTQ.java:23)
Caused by: java.lang.ClassCastException: java.util.concurrent.LinkedTransferQueue$Node cannot be cast to java.lang.String
	at java.util.concurrent.LinkedTransferQueue$LTQSpliterator.forEachRemaining(LinkedTransferQueue.java:987)
	at java.util.stream.ReferencePipeline$Head.forEach(ReferencePipeline.java:579)
	at LTQ.lambda$main$0(LTQ.java:12)
	at java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:511)
	at java.util.concurrent.FutureTask.run(FutureTask.java:265)
	at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
	at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
	at java.lang.Thread.run(Thread.java:745)

Reproduces on 8u40, 8u45, latest jdk9-dev.
Does not reproduce with either JDK and bootclasspath-ed JSR166.
Bisection shows this is the first commit that does not fail with JSR166:
  http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/LinkedTransferQueue.java?r1=1.70&r2=1.71
Comments
Aleksey, yes, i will get around to this next week.
12-06-2015
Paging Paul Sandoz here. Paul, can you follow up with the Doug's fix?
12-06-2015
I got distracted proving !p.isData after the first element, but in lieu of this, checks should be conservatively added: *** LinkedTransferQueue.java.~1.88.~ 2015-06-09 19:56:41.000000000 -0400 --- LinkedTransferQueue.java 2015-06-11 12:20:09.285818814 -0400 *************** *** 1044,1050 **** ++i; if (p == (p = p.next)) p = q.firstDataNode(); ! } while (p != null && i < n); if ((current = p) == null) exhausted = true; if (i > 0) { --- 1044,1050 ---- ++i; if (p == (p = p.next)) p = q.firstDataNode(); ! } while (p != null && i < n && p.isData); if ((current = p) == null) exhausted = true; if (i > 0) { *************** *** 1072,1078 **** action.accept((E)e); if (p == (p = p.next)) p = q.firstDataNode(); ! } while (p != null); } } --- 1072,1078 ---- action.accept((E)e); if (p == (p = p.next)) p = q.firstDataNode(); ! } while (p != null && p.isData); } } *************** *** 1089,1095 **** e = null; if (p == (p = p.next)) p = q.firstDataNode(); ! } while (e == null && p != null); if ((current = p) == null) exhausted = true; if (e != null) { --- 1089,1095 ---- e = null; if (p == (p = p.next)) p = q.firstDataNode(); ! } while (e == null && p != null && p.isData); if ((current = p) == null) exhausted = true; if (e != null) {
11-06-2015
Doug, I'm pretty sure your patch fixes the reported bug, but ... I'm not sure whether p.isData should also be checked, as elsewhere in this file. Is it possible that p will (rarely) end up at a just-fulfilled request node? If not, there should be a comment clarifying why.
10-06-2015
Callers of firstDataNode must check if the node's item has been forgotten before using. Somehow the checks got dropped in the course of Spliterator API evolution in JDK8. Sorry! Here are diffs to current 166 CVS. They should apply with different offsets to JDK8 and 9. *** LinkedTransferQueue.java.~1.86.~ 2015-05-27 08:12:30.803532208 -0400 --- LinkedTransferQueue.java 2015-06-09 19:37:43.742450370 -0400 *************** *** 744,750 **** } /** ! * Version of firstOfMode used by Spliterator */ final Node firstDataNode() { for (Node p = head; p != null;) { --- 744,752 ---- } /** ! * Version of firstOfMode used by Spliterator. Callers must ! * recheck if the returned node's item field is null or ! * self-linked before using. */ final Node firstDataNode() { for (Node p = head; p != null;) { *************** *** 1037,1043 **** Object[] a = new Object[n]; int i = 0; do { ! if ((a[i] = p.item) != null) ++i; if (p == (p = p.next)) p = q.firstDataNode(); --- 1039,1046 ---- Object[] a = new Object[n]; int i = 0; do { ! Object e = p.item; ! if (e != p && (a[i] = e) != null) ++i; if (p == (p = p.next)) p = q.firstDataNode(); *************** *** 1065,1074 **** exhausted = true; do { Object e = p.item; if (p == (p = p.next)) p = q.firstDataNode(); - if (e != null) - action.accept((E)e); } while (p != null); } } --- 1068,1077 ---- exhausted = true; do { Object e = p.item; + if (e != null && e != p) + action.accept((E)e); if (p == (p = p.next)) p = q.firstDataNode(); } while (p != null); } } *************** *** 1082,1088 **** ((p = current) != null || (p = q.firstDataNode()) != null)) { Object e; do { ! e = p.item; if (p == (p = p.next)) p = q.firstDataNode(); } while (e == null && p != null); --- 1085,1092 ---- ((p = current) != null || (p = q.firstDataNode()) != null)) { Object e; do { ! if ((e = p.item) == p) ! e = null; if (p == (p = p.next)) p = q.firstDataNode(); } while (e == null && p != null);
09-06-2015
Another version of the failing test: import java.util.Collection; import java.util.concurrent.Executors; import java.util.concurrent.ExecutorService; import java.util.concurrent.Future; import java.util.concurrent.LinkedTransferQueue; import java.util.concurrent.TimeUnit; import java.util.concurrent.atomic.AtomicBoolean; public class LTQ { public static void main(String... args) throws Throwable { final long testDurationMillis = 1000; final AtomicBoolean done = new AtomicBoolean(false); Collection<String> msgs = new LinkedTransferQueue<>(); ExecutorService pool = Executors.newCachedThreadPool(); Runnable foreach = () -> { while (!done.get()) msgs.stream().forEach(Object::toString); }; Runnable addRemove = () -> { while (!done.get()) { msgs.add("msg"); msgs.remove("msg"); }}; Future<?> f1 = pool.submit(foreach); Future<?> f2 = pool.submit(addRemove); Thread.sleep(testDurationMillis); done.set(true); pool.shutdown(); pool.awaitTermination(10L, TimeUnit.SECONDS); f1.get(); f2.get(); } }
09-06-2015
I did my own bisection, giving revision 1.70 instead of 1.80 - correcting that, assuming it was a typo. 1.70 looks much more plausible, because of the call to forgetContents, which sets this.item to this, causing a Node to be returned. Doug, could you recommend a fix for jdk8?
08-06-2015
Generally, the methods added in jdk8 could have used more testing. The tck tests are mostly missing. It looks to me like this bug was fixed without being aware of that fact, by simple code cleanliness and consistency. Again, we can bulk integrate jsr166 into jdk9 to fix this. Probably not appropriate for jdk8, where a point fix seems like the right thing.
08-06-2015