FULL PRODUCT VERSION :
java version "1.8.0"
Java<TM> SE Runtime Environment <build 1.8.0-b132>
Java HotSpot<TM> 64-Bit Server VM <build 25.0-b70, mixed mode>
A DESCRIPTION OF THE PROBLEM :
linkedTransferQueue is based on the Dual Queues with Slack in which nodes may represent either data or requests, and Nodes can be appended only if their predecessors are either already matched or are of the same mode(method tryAppend), but matched node and canceled node represented by the same way, their "item" field will eventually get node own values.So there is one situation in which we will lose data in this way: if the list is empty, we have an untimed call to take at first, have an untimed call to take with interrupted status at second, then have a call to offer. The first two calls will try to add request nodes to the list, the first node will wait for another thread to match node, the second node instead cancelling because the current thread was interrupted, and the offer call is found at the end of the list is a ������canceled������ node, and in the code is a ������matched������ node, So the offer call will also add a data node to the list. Now the first take call is waiting for the data but the data has been inserted into the list, They are separated by a ������matched" node, Obviously now lost data, and there are two modes exist in the list of nodes, the first is a request node, the last is a data node. In this case, If we once again call take, this will be caught in an infinite loop, one core of CPU will be occupied.
ADDITIONAL REGRESSION INFORMATION:
java version "1.8.0"
Java<TM> SE Runtime Environment <build 1.8.0-b132>
Java HotSpot<TM> 64-Bit Server VM <build 25.0-b70, mixed mode>
STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
The bug of Multi-threaded environment is extremely difficult to reproduce,
So I reproduce it through breakpoints.
Hit a breakpoint at line 643 of the below code of LinkedTransferQueue.class(jdk1.8.0):
642 s = new Node(e, haveData);
643 Node pred = tryAppend(s, haveData);
644 if (pred == null)
Then execute the test case in "Source code for an executable test case".
When these four threads(Thread-0/Thread-1/Thread-2/Thread-3) suspended on the breakpoint:
let "Thread-0" go at first, no output;
let "Thread-1" go at second, Examples of output "14 java.lang.InterruptedException";
let"Thread-2" go at third, Examples of output "15 offerTask thread has come out!", Now bug has occurred! Our "8" has been lost;
Skip all breakpoints, then let "Thread-3" go at last, Now a CPU core has been completely occupied;
EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
"8" will be output
ACTUAL -
"8" is not output
REPRODUCIBILITY :
This bug can be reproduced rarely.
---------- BEGIN SOURCE ----------
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedTransferQueue;
public class TestForLinkedTransferQueue {
public static void main(String[] args) {
final BlockingQueue<Long> queue = new LinkedTransferQueue<Long>();
Runnable takeTask = new Runnable() {
public void run() {
try {
System.out.println(Thread.currentThread().getId() + " "
+ queue.take());
} catch (InterruptedException e) {
e.printStackTrace();
}
}
};
Runnable takeTaskInterrupted = new Runnable() {
public void run() {
Thread.currentThread().interrupt();
try {
System.out.println(Thread.currentThread().getId() + " "
+ queue.take());
} catch (InterruptedException e) {
System.out.println(Thread.currentThread().getId() + " " + e);
}
}
};
Runnable offerTask = new Runnable() {
public void run() {
queue.offer(8L);
System.out.println(Thread.currentThread().getId() + " offerTask thread has come out!");
}
};
new Thread(takeTask).start();// first untimed call to take
new Thread(takeTaskInterrupted).start();// second untimed call to take with interrupted status
new Thread(offerTask).start();// a call to offer
new Thread(takeTask).start();
}
}
---------- END SOURCE ----------
CUSTOMER SUBMITTED WORKAROUND :
This bug is a potential problem, I cannot replicate it either in practice;
I have provided a patch for it:https://github.com/zuai/Hui/blob/master/LinkedTransferQueueFix.java