8148174: NegativeArraySizeException in Vector.grow(int)
Summary: improve management of internal array
Reviewed-by: smarks, forax
--- 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<? extends E> 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;
}
/**
--- 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
--- /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<E> extends Vector<E> {
+ 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<Object> singletonList() {
+ return Collections.singletonList(Boolean.TRUE);
+ }
+
+ /** Opportunistically randomly test various add operations. */
+ static void addOneElement(PublicVector<Object> 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<Object> list = new PublicVector<>();
+ assertEquals(new PublicVector<Object>().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<Object> 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<Object> list = new PublicVector<>();
+ list.ensureCapacity(DEFAULT_CAPACITY + 1);
+ assertEquals(list.capacity(), newCapacity(DEFAULT_CAPACITY));
+ }
+
+ @Test public void explicitZeroCapacity() {
+ PublicVector<Object> 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<Object> 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<Object> 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<Object> 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<Object>(0).elementData(),
+ new PublicVector<Object>(0).elementData());
+ }
+
+ @Test public void negativeCapacity() {
+ for (int capacity : new int[] { -1, Integer.MIN_VALUE }) {
+ try {
+ new Vector<Object>(capacity);
+ fail("should throw");
+ } catch (IllegalArgumentException success) {}
+ }
+ }
+}
--- /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<Object> 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) {}
+ }
+}