In LinkedBlockingDeque.addAll() we first build up the chain of nodes and then
add that chain in bulk to the existing nodes. We count the nodes in "int n" and
then whilst holding the lock, we check that we haven't exceeded the capacity
with "if (count + n <= capacity)". However, if we pass in a collection that has
more than Integer.MAX_VALUE items in it, then we can overflow n, making it
negative. Since "count + n" is also negative, we can add the chain to our last
item, and thus we end up with a LinkedBlockingDeque with more than
Integer.MAX_VALUE of items and a negative size(). stream().count() gives the
correct number of items.
This happens both via the bulk add constructor LinkedBlockingDeque(Collection)
and when we call addAll(Collection) directly.
In Java 8, they didn't have the clever addAll() method, and thus it failed
immediately.
Here is some test code:
import java.util.*;
import java.util.concurrent.*;
// To see the issue, run with at least 90 GB of memory:
// -XX:+UnlockExperimentalVMOptions -Xmx90g -Xms90g -XX:+UseEpsilonGC
-verbose:gc
// To verify the fix, run with at least 200 GB of memory:
// -XX:+UnlockExperimentalVMOptions -Xmx200g -Xms200g -XX:+UseEpsilonGC
-verbose:gc
// To try on older versions of Java that don't have the EpsilonGC, you can use:
// -XX:+UseG1GC -verbose:gc -Xmx91g -Xms91g -XX:NewSize=89g
public class NegativeSizedLinkedBlockingDeque {
public static void main(String... args) {
HUUUGECollection list = new HUUUGECollection(Integer.MAX_VALUE + 1L);
LinkedBlockingDeque<Integer> lbd = new LinkedBlockingDeque<>(10);
lbd.addAll(list);
System.out.println("lbd.size() = " + lbd.size());
System.out.println(lbd.stream().count());
}
public static class HUUUGECollection extends AbstractCollection<Integer> {
private final long size;
public HUUUGECollection(long size) {
this.size = size;
}
@Override
public int size() {
return size < Integer.MAX_VALUE ? (int) size : Integer.MAX_VALUE;
}
@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
private long count = 0;
public boolean hasNext() {
return count < size;
}
public Integer next() {
if (!hasNext()) throw new NoSuchElementException();
count++;
return 42;
}
};
}
}
}
Output is:
heinz$ java -XX:+UnlockExperimentalVMOptions -XX:+UseEpsilonGC -verbose:gc
-Xmx90g -Xms90g tjsn/ideas2025/juc/NegativeSizedLinkedBlockingDeque
[0.004s][info][gc] Using Epsilon
[0.005s][warning][gc,init] Consider enabling -XX:+AlwaysPreTouch to avoid
memory commit hiccups
[0.668s][info ][gc ] Heap: 92160M reserved, 92160M (100.00%) committed,
4610M (5.00%) used
[1.321s][info ][gc ] Heap: 92160M reserved, 92160M (100.00%) committed,
9218M (10.00%) used
[1.962s][info ][gc ] Heap: 92160M reserved, 92160M (100.00%) committed,
13826M (15.00%) used
[2.626s][info ][gc ] Heap: 92160M reserved, 92160M (100.00%) committed,
18434M (20.00%) used
[3.283s][info ][gc ] Heap: 92160M reserved, 92160M (100.00%) committed,
23042M (25.00%) used
[3.934s][info ][gc ] Heap: 92160M reserved, 92160M (100.00%) committed,
27650M (30.00%) used
[4.602s][info ][gc ] Heap: 92160M reserved, 92160M (100.00%) committed,
32258M (35.00%) used
[5.253s][info ][gc ] Heap: 92160M reserved, 92160M (100.00%) committed,
36866M (40.00%) used
[5.907s][info ][gc ] Heap: 92160M reserved, 92160M (100.00%) committed,
41474M (45.00%) used
[6.577s][info ][gc ] Heap: 92160M reserved, 92160M (100.00%) committed,
46082M (50.00%) used
[7.228s][info ][gc ] Heap: 92160M reserved, 92160M (100.00%) committed,
50690M (55.00%) used
[7.884s][info ][gc ] Heap: 92160M reserved, 92160M (100.00%) committed,
55298M (60.00%) used
[8.526s][info ][gc ] Heap: 92160M reserved, 92160M (100.00%) committed,
59906M (65.00%) used
[9.179s][info ][gc ] Heap: 92160M reserved, 92160M (100.00%) committed,
64514M (70.00%) used
[10.282s][info ][gc ] Heap: 92160M reserved, 92160M (100.00%) committed,
69122M (75.00%) used
[11.096s][info ][gc ] Heap: 92160M reserved, 92160M (100.00%) committed,
73730M (80.00%) used
[11.957s][info ][gc ] Heap: 92160M reserved, 92160M (100.00%) committed,
78338M (85.00%) used
lbd.size() = -2147483648
2147483648
[27.619s][info ][gc ] Heap: 92160M reserved, 92160M (100.00%) committed,
81942M (88.91%) used
This has been submitted as a bug - internal review ID : 9078362.
-------------
Commit messages:
- Clear the previously created chain to allow it to be GC'ed before calling
the super.addAll() method
- Fixed bug in addAll() that allowed overflow on LBD nodes
Changes: https://git.openjdk.org/jdk/pull/24538/files
Webrev: https://webrevs.openjdk.org/?repo=jdk&pr=24538&range=00
Issue: https://bugs.openjdk.org/browse/JDK-8354138
Stats: 3 lines in 1 file changed: 1 ins; 0 del; 2 mod
Patch: https://git.openjdk.org/jdk/pull/24538.diff
Fetch: git fetch https://git.openjdk.org/jdk.git pull/24538/head:pull/24538
PR: https://git.openjdk.org/jdk/pull/24538
