On Tue, 15 Aug 2023 09:45:43 GMT, Nikita Sakharin <d...@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