changeset 13553:77e3647b88c6

8148174: NegativeArraySizeException in Vector.grow(int) Summary: improve management of internal array Reviewed-by: smarks, forax
author martin
date Mon, 25 Jan 2016 16:07:00 -0800
parents 20a68adf2159
children a4091026bf79
files src/java.base/share/classes/java/util/Vector.java test/java/util/ArrayList/ArrayManagement.java test/java/util/Vector/ArrayManagement.java test/java/util/Vector/Bug8148174.java
diffstat 4 files changed, 351 insertions(+), 58 deletions(-) [+]
line wrap: on
line diff
--- a/src/java.base/share/classes/java/util/Vector.java	Wed Jan 27 21:59:00 2016 +0800
+++ b/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)
+            return false;
+        Object[] elementData = this.elementData;
+        final int s = elementCount;
+        if (numNew > elementData.length - s)
+            elementData = grow(s + numNew);
 
-        if (numNew > 0) {
-            ensureCapacityHelper(elementCount + 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/test/java/util/ArrayList/ArrayManagement.java	Wed Jan 27 21:59:00 2016 +0800
+++ b/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/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/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) {}
+    }
+}