# HG changeset patch # User martin # Date 1453766820 28800 # Node ID 61820dd2360e875a4d1480ac1088a0f688676241 # Parent 1f36500e84c7395e874bd7d8162878d221bfd7fc 8148174: NegativeArraySizeException in Vector.grow(int) Summary: improve management of internal array Reviewed-by: smarks, forax diff -r 1f36500e84c7 -r 61820dd2360e jdk/src/java.base/share/classes/java/util/Vector.java --- a/jdk/src/java.base/share/classes/java/util/Vector.java Wed Jan 27 21:59:00 2016 +0800 +++ b/jdk/src/java.base/share/classes/java/util/Vector.java Mon Jan 25 16:07:00 2016 -0800 @@ -233,42 +233,56 @@ public synchronized void ensureCapacity(int minCapacity) { if (minCapacity > 0) { modCount++; - ensureCapacityHelper(minCapacity); + if (minCapacity > elementData.length) + grow(minCapacity); } } /** - * This implements the unsynchronized semantics of ensureCapacity. - * Synchronized methods in this class can internally call this - * method for ensuring capacity without incurring the cost of an - * extra synchronization. - * - * @see #ensureCapacity(int) - */ - private void ensureCapacityHelper(int minCapacity) { - // overflow-conscious code - if (minCapacity - elementData.length > 0) - grow(minCapacity); - } - - /** - * The maximum size of array to allocate. + * The maximum size of array to allocate (unless necessary). * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; - private void grow(int minCapacity) { + /** + * Increases the capacity to ensure that it can hold at least the + * number of elements specified by the minimum capacity argument. + * + * @param minCapacity the desired minimum capacity + * @throws OutOfMemoryError if minCapacity is less than zero + */ + private Object[] grow(int minCapacity) { + return elementData = Arrays.copyOf(elementData, + newCapacity(minCapacity)); + } + + private Object[] grow() { + return grow(elementCount + 1); + } + + /** + * Returns a capacity at least as large as the given minimum capacity. + * Will not return a capacity greater than MAX_ARRAY_SIZE unless + * the given minimum capacity is greater than MAX_ARRAY_SIZE. + * + * @param minCapacity the desired minimum capacity + * @throws OutOfMemoryError if minCapacity is less than zero + */ + private int newCapacity(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); - if (newCapacity - minCapacity < 0) - newCapacity = minCapacity; - if (newCapacity - MAX_ARRAY_SIZE > 0) - newCapacity = hugeCapacity(minCapacity); - elementData = Arrays.copyOf(elementData, newCapacity); + if (newCapacity - minCapacity <= 0) { + if (minCapacity < 0) // overflow + throw new OutOfMemoryError(); + return minCapacity; + } + return (newCapacity - MAX_ARRAY_SIZE <= 0) + ? newCapacity + : hugeCapacity(minCapacity); } private static int hugeCapacity(int minCapacity) { @@ -290,13 +304,10 @@ */ public synchronized void setSize(int newSize) { modCount++; - if (newSize > elementCount) { - ensureCapacityHelper(newSize); - } else { - for (int i = newSize ; i < elementCount ; i++) { - elementData[i] = null; - } - } + if (newSize > elementData.length) + grow(newSize); + for (int i = newSize; i < elementCount; i++) + elementData[i] = null; elementCount = newSize; } @@ -604,11 +615,16 @@ throw new ArrayIndexOutOfBoundsException(index + " > " + elementCount); } - ensureCapacityHelper(elementCount + 1); - System.arraycopy(elementData, index, elementData, index + 1, elementCount - index); + modCount++; + final int s = elementCount; + Object[] elementData = this.elementData; + if (s == elementData.length) + elementData = grow(); + System.arraycopy(elementData, index, + elementData, index + 1, + s - index); elementData[index] = obj; - modCount++; - elementCount++; + elementCount = s + 1; } /** @@ -623,9 +639,8 @@ * @param obj the component to be added */ public synchronized void addElement(E obj) { - ensureCapacityHelper(elementCount + 1); modCount++; - elementData[elementCount++] = obj; + add(obj, elementData, elementCount); } /** @@ -781,6 +796,18 @@ } /** + * This helper method split out from add(E) to keep method + * bytecode size under 35 (the -XX:MaxInlineSize default value), + * which helps when add(E) is called in a C1-compiled loop. + */ + private void add(E e, Object[] elementData, int s) { + if (s == elementData.length) + elementData = grow(); + elementData[s] = e; + elementCount = s + 1; + } + + /** * Appends the specified element to the end of this Vector. * * @param e element to be appended to this Vector @@ -788,9 +815,8 @@ * @since 1.2 */ public synchronized boolean add(E e) { - ensureCapacityHelper(elementCount + 1); modCount++; - elementData[elementCount++] = e; + add(e, elementData, elementCount); return true; } @@ -891,16 +917,19 @@ */ public boolean addAll(Collection c) { Object[] a = c.toArray(); + modCount++; int numNew = a.length; - if (numNew > 0) { - synchronized (this) { - ensureCapacityHelper(elementCount + numNew); - System.arraycopy(a, 0, elementData, elementCount, numNew); - modCount++; - elementCount += numNew; - } + if (numNew == 0) + return false; + synchronized (this) { + Object[] elementData = this.elementData; + final int s = elementCount; + if (numNew > elementData.length - s) + elementData = grow(s + numNew); + System.arraycopy(a, 0, elementData, s, numNew); + elementCount = s + numNew; + return true; } - return numNew > 0; } /** @@ -969,21 +998,23 @@ throw new ArrayIndexOutOfBoundsException(index); Object[] a = c.toArray(); + modCount++; int numNew = a.length; - - if (numNew > 0) { - ensureCapacityHelper(elementCount + numNew); + if (numNew == 0) + return false; + Object[] elementData = this.elementData; + final int s = elementCount; + if (numNew > elementData.length - s) + elementData = grow(s + numNew); - int numMoved = elementCount - index; - if (numMoved > 0) - System.arraycopy(elementData, index, elementData, - index + numNew, numMoved); - - System.arraycopy(a, 0, elementData, index, numNew); - elementCount += numNew; - modCount++; - } - return numNew > 0; + int numMoved = s - index; + if (numMoved > 0) + System.arraycopy(elementData, index, + elementData, index + numNew, + numMoved); + System.arraycopy(a, 0, elementData, index, numNew); + elementCount = s + numNew; + return true; } /** diff -r 1f36500e84c7 -r 61820dd2360e jdk/test/java/util/ArrayList/ArrayManagement.java --- a/jdk/test/java/util/ArrayList/ArrayManagement.java Wed Jan 27 21:59:00 2016 +0800 +++ b/jdk/test/java/util/ArrayList/ArrayManagement.java Mon Jan 25 16:07:00 2016 -0800 @@ -83,6 +83,7 @@ int oldCapacity = capacity(list); int oldModCount = modCount(list); list.ensureCapacity(capacity); + assertTrue(capacity(list) >= capacity || capacity(list) == 0); assertEquals(modCount(list), (capacity(list) == oldCapacity) ? oldModCount diff -r 1f36500e84c7 -r 61820dd2360e jdk/test/java/util/Vector/ArrayManagement.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/jdk/test/java/util/Vector/ArrayManagement.java Mon Jan 25 16:07:00 2016 -0800 @@ -0,0 +1,218 @@ +/* + * Copyright 2016 Google, Inc. All Rights Reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ + +/* + * @test + * @bug 8148174 + * @summary brittle white box test of internal array management + * @run testng ArrayManagement + */ + +import java.lang.reflect.Field; +import java.util.AbstractList; +import java.util.Vector; +import java.util.Collections; +import java.util.List; +import java.util.SplittableRandom; + +import org.testng.annotations.Test; +import static org.testng.Assert.*; + +public class ArrayManagement { + + /** + * A Vector that exposes all protected elements, and checks class + * invariants. + */ + static class PublicVector extends Vector { + public PublicVector() { super(); } + public PublicVector(int capacity) { super(capacity); } + public PublicVector(int capacity, int capacityIncrement) { + super(capacity, capacityIncrement); + } + public Object[] elementData() { return elementData; } + public int modCount() { return modCount; } + public int capacityIncrement() { return capacityIncrement; } + public int capacity() { return elementData.length; } + + public void ensureCapacity(int minCapacity) { + int oldCapacity = capacity(); + int oldModCount = modCount(); + super.ensureCapacity(minCapacity); + assertTrue(capacity() >= minCapacity); + if (minCapacity <= oldCapacity) + assertEquals(capacity(), oldCapacity); + if (minCapacity > 0) + assertEquals(modCount(), oldModCount + 1); + } + } + + static final int DEFAULT_CAPACITY = 10; + static final SplittableRandom rnd = new SplittableRandom(); + + static int newCapacity(int oldCapacity) { + return 2 * oldCapacity; + } + + static List singletonList() { + return Collections.singletonList(Boolean.TRUE); + } + + /** Opportunistically randomly test various add operations. */ + static void addOneElement(PublicVector list) { + int size = list.size(); + int modCount = list.modCount(); + switch (rnd.nextInt(4)) { + case 0: assertTrue(list.add(Boolean.TRUE)); break; + case 1: list.add(size, Boolean.TRUE); break; + case 2: assertTrue(list.addAll(singletonList())); break; + case 3: assertTrue(list.addAll(size, singletonList())); break; + default: throw new AssertionError(); + } + assertEquals(list.modCount(), modCount + 1); + assertEquals(list.size(), size + 1); + } + + @Test public void defaultCapacity() { + PublicVector list = new PublicVector<>(); + assertEquals(new PublicVector().capacity(), DEFAULT_CAPACITY); + for (int i = 0; i < DEFAULT_CAPACITY; i++) { + addOneElement(list); + assertEquals(list.capacity(), DEFAULT_CAPACITY); + } + addOneElement(list); + assertEquals(list.capacity(), newCapacity(DEFAULT_CAPACITY)); + } + + @Test public void defaultCapacityEnsureCapacity() { + PublicVector list = new PublicVector<>(); + for (int i = 0; i <= DEFAULT_CAPACITY; i++) { + list.ensureCapacity(i); // no-op! + assertEquals(list.capacity(), DEFAULT_CAPACITY); + } + for (int i = 0; i < DEFAULT_CAPACITY; i++) { + addOneElement(list); + assertEquals(list.capacity(), DEFAULT_CAPACITY); + } + addOneElement(list); + assertEquals(list.capacity(), newCapacity(DEFAULT_CAPACITY)); + { + int capacity = list.capacity(); + list.ensureCapacity(capacity + 1); + assertEquals(list.capacity(), newCapacity(capacity)); + } + { + int capacity = list.capacity(); + list.ensureCapacity(3 * capacity); + assertEquals(list.capacity(), 3 * capacity); + } + } + + @Test public void ensureCapacityBeyondDefaultCapacity() { + PublicVector list = new PublicVector<>(); + list.ensureCapacity(DEFAULT_CAPACITY + 1); + assertEquals(list.capacity(), newCapacity(DEFAULT_CAPACITY)); + } + + @Test public void explicitZeroCapacity() { + PublicVector list = new PublicVector<>(0); + assertEquals(list.capacity(), 0); + addOneElement(list); + assertEquals(list.capacity(), 1); + addOneElement(list); + assertEquals(list.capacity(), 2); + addOneElement(list); + assertEquals(list.capacity(), 4); + addOneElement(list); + assertEquals(list.capacity(), 4); + addOneElement(list); + assertEquals(list.capacity(), 8); + addOneElement(list); + assertEquals(list.capacity(), 8); + addOneElement(list); + assertEquals(list.capacity(), 8); + list.clear(); + assertEquals(list.capacity(), 8); + } + + @Test public void explicitZeroCapacityWithCapacityIncrement() { + PublicVector list = new PublicVector<>(0, 2); + assertEquals(list.capacity(), 0); + addOneElement(list); + assertEquals(list.capacity(), 2); + addOneElement(list); + assertEquals(list.capacity(), 2); + addOneElement(list); + assertEquals(list.capacity(), 4); + addOneElement(list); + assertEquals(list.capacity(), 4); + addOneElement(list); + assertEquals(list.capacity(), 6); + addOneElement(list); + assertEquals(list.capacity(), 6); + addOneElement(list); + assertEquals(list.capacity(), 8); + list.clear(); + assertEquals(list.capacity(), 8); + } + + @Test public void explicitLargeCapacity() { + int n = DEFAULT_CAPACITY * 3; + PublicVector list = new PublicVector<>(n); + assertEquals(list.capacity(), n); + list.ensureCapacity(0); + list.ensureCapacity(n); + for (int i = 0; i < n; i++) addOneElement(list); + assertEquals(list.capacity(), n); + + addOneElement(list); + assertEquals(list.capacity(), newCapacity(n)); + } + + @Test public void explicitLargeCapacityWithCapacityIncrement() { + int n = DEFAULT_CAPACITY * 3; + PublicVector list = new PublicVector<>(n, 2); + assertEquals(list.capacity(), n); + list.ensureCapacity(0); + list.ensureCapacity(n); + for (int i = 0; i < n; i++) addOneElement(list); + assertEquals(list.capacity(), n); + + addOneElement(list); + assertEquals(list.capacity(), n + 2); + } + + @Test public void emptyArraysAreNotShared() { + assertNotSame(new PublicVector(0).elementData(), + new PublicVector(0).elementData()); + } + + @Test public void negativeCapacity() { + for (int capacity : new int[] { -1, Integer.MIN_VALUE }) { + try { + new Vector(capacity); + fail("should throw"); + } catch (IllegalArgumentException success) {} + } + } +} diff -r 1f36500e84c7 -r 61820dd2360e jdk/test/java/util/Vector/Bug8148174.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/jdk/test/java/util/Vector/Bug8148174.java Mon Jan 25 16:07:00 2016 -0800 @@ -0,0 +1,43 @@ +/* + * Copyright 2016 Google, Inc. All Rights Reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ + +/* + * @test + * @bug 8148174 + * @summary repro for: NegativeArraySizeException in Vector.grow(int) + * @run main/othervm -Xmx17g Bug8148174 + * @ignore This test has huge memory requirements + */ + +public class Bug8148174 { + public static void main(String[] args) { + int size = Integer.MAX_VALUE - 2; + java.util.Vector huge = new java.util.Vector<>(size); + for (int i = 0; i < size; i++) + huge.add(null); + try { + huge.addAll(huge); + throw new Error("expected OutOfMemoryError not thrown"); + } catch (OutOfMemoryError success) {} + } +}