RFR: 8314236: Overflow in Collections.rotate [v2]

[Aleksey Shipilev]

On Tue, 15 Aug 2023 09:45:43 GMT, Nikita Sakharin <duke at openjdk.org> wrote:

>> `Collections.rotate` method contains a bug. This method throws IndexOutOfBoundsException on arrays larger than $2^{30}$ elements. The way to reproduce:
>> 
>> final int size = (1 << 30) + 1;
>> final List<Byte> list = new ArrayList<>(size);
>> for (int i = 0; i < size; ++i)
>>     list.add((byte) 0);
>> Collections.rotate(list, size - 1);
>> 
>> Output:
>> ```Exception in thread "main" java.lang.IndexOutOfBoundsException: Index -2147483648 out of bounds for length 1073741825```
>> 
>> In that case private method `Collections.rotate1` will be called. And the line:
>> `i += distance;`
>> will cause overflow. I fixed this method and wrote a test for it.
>> 
>> I've signed the Oracle Contributor Agreement, but I don't have permission to raise a bug in the JDK Bug System.
>> 
>> Kindly ask you to raise a bug.
>
> Nikita Sakharin has updated the pull request incrementally with one additional commit since the last revision:
> 
>   8314236: change bug number and summary

Superficially, this looks okay. Some OpenJDK code/test style trivia:

src/java.base/share/classes/java/util/Collections.java line 810:

> 808: 
> 809:     private static <T> void rotate1(final List<T> list, int distance) {
> 810:         final int size = list.size();

Let's keep the style, and do a focused fix: skip adding `final` here. (`final` mostly matters for fields).

src/java.base/share/classes/java/util/Collections.java line 813:

> 811:         if (size == 0)
> 812:             return;
> 813:         distance %= size;

Same, let's keep the original style.

test/jdk/java/util/Collections/RotateHuge.java line 27:

> 25:  * @test
> 26:  * @bug 8314236
> 27:  * @summary Overflow in Collections.rotate

Since this test takes >4G of heap to hold the list with compressed oops, and >8G of heap without compressed oops, we need to run it in a separate VM with enough headroom, something like this:


 * @test
 * @bug 8314236
 * @summary Overflow in Collections.rotate
 * @requires (sun.arch.data.model == "64" & os.maxMemory >= 16g)
 * @run main/othervm -Xmx12g RotateHuge

test/jdk/java/util/Collections/RotateHuge.java line 40:

> 38:         final List<Byte> list = new ArrayList<>(size);
> 39:         for (int i = 0; i < size; ++i)
> 40:             list.add((byte) 0);

We don't actually need to rely on auto-boxing here, right?

Suggestion:

        final Object o = new Object();
        final List<Object> list = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            list.add(o);
        }

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

PR Review: https://git.openjdk.org/jdk/pull/15270#pullrequestreview-1578268533
PR Review Comment: https://git.openjdk.org/jdk/pull/15270#discussion_r1294404136
PR Review Comment: https://git.openjdk.org/jdk/pull/15270#discussion_r1294404599
PR Review Comment: https://git.openjdk.org/jdk/pull/15270#discussion_r1294399882
PR Review Comment: https://git.openjdk.org/jdk/pull/15270#discussion_r1294395844