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

[kabutz]

On Wed, 9 Apr 2025 11:43:16 GMT, Chen Liang <liach 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()...
>
> Hi @kabutz, I believe you can create issues on JBS (bugs.openjdk.org) directly without going thorough bugs.java.com - as an author in OpenJDK census, you have an account associated with your email, and you can log in to the JBS at https://id.openjdk.org/console/login?backUrl=https://bugs.openjdk.org and from there, you can create or edit issues or CSRs.

Thanks @liach, I'm just not sure about all the fields in the OpenJDK census - will try do that next time.

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

PR Comment: https://git.openjdk.org/jdk/pull/24538#issuecomment-2789503132