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

[kabutz]

On Wed, 9 Apr 2025 06:24:30 GMT, kabutz <duke at openjdk.org> wrote:

> 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;
>   ...

This pull request has been closed without being integrated.

-------------

PR: https://git.openjdk.org/jdk/pull/24538