RFR: 8354138: LinkedBlockingDeque allows us to exceed size with addAll()

[kabutz]

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