8149330: Capacity of StringBuilder should not get close to Integer.MAX_VALUE unless necessary
Reviewed-by: martin
--- a/jdk/src/java.base/share/classes/java/lang/AbstractStringBuilder.java Wed Mar 02 11:14:35 2016 +0100
+++ b/jdk/src/java.base/share/classes/java/lang/AbstractStringBuilder.java Wed Mar 02 14:10:40 2016 +0300
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2003, 2015, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2003, 2016, Oracle and/or its affiliates. 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
@@ -133,39 +133,62 @@
}
/**
- * This method has the same contract as ensureCapacity, but is
- * never synchronized.
+ * For positive values of {@code minimumCapacity}, this method
+ * behaves like {@code ensureCapacity}, however it is never
+ * synchronized.
+ * If {@code minimumCapacity} is non positive due to numeric
+ * overflow, this method throws {@code OutOfMemoryError}.
*/
private void ensureCapacityInternal(int minimumCapacity) {
// overflow-conscious code
- int capacity = value.length >> coder;
- if (minimumCapacity - capacity > 0) {
- expandCapacity(minimumCapacity);
+ int oldCapacity = value.length >> coder;
+ if (minimumCapacity - oldCapacity > 0) {
+ value = Arrays.copyOf(value,
+ newCapacity(minimumCapacity) << coder);
}
}
/**
- * This implements the expansion semantics of ensureCapacity with no
- * size check or synchronization.
+ * 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 void expandCapacity(int minimumCapacity) {
- int newCapacity = (value.length >> coder) * 2 + 2;
- if (newCapacity - minimumCapacity < 0) {
- newCapacity = minimumCapacity;
+ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
+
+ /**
+ * Returns a capacity at least as large as the given minimum capacity.
+ * Returns the current capacity increased by the same amount + 2 if
+ * that suffices.
+ * Will not return a capacity greater than
+ * {@code (MAX_ARRAY_SIZE >> coder)} unless the given minimum capacity
+ * is greater than that.
+ *
+ * @param minCapacity the desired minimum capacity
+ * @throws OutOfMemoryError if minCapacity is less than zero or
+ * greater than (Integer.MAX_VALUE >> coder)
+ */
+ private int newCapacity(int minCapacity) {
+ // overflow-conscious code
+ int oldCapacity = value.length >> coder;
+ int newCapacity = (oldCapacity << 1) + 2;
+ if (newCapacity - minCapacity < 0) {
+ newCapacity = minCapacity;
}
- if (newCapacity < 0) {
- if (minimumCapacity < 0) {// overflow
- throw new OutOfMemoryError();
- }
- newCapacity = Integer.MAX_VALUE;
+ int SAFE_BOUND = MAX_ARRAY_SIZE >> coder;
+ return (newCapacity <= 0 || SAFE_BOUND - newCapacity < 0)
+ ? hugeCapacity(minCapacity)
+ : newCapacity;
+ }
+
+ private int hugeCapacity(int minCapacity) {
+ int SAFE_BOUND = MAX_ARRAY_SIZE >> coder;
+ int UNSAFE_BOUND = Integer.MAX_VALUE >> coder;
+ if (UNSAFE_BOUND - minCapacity < 0) { // overflow
+ throw new OutOfMemoryError();
}
- if (coder != LATIN1 && newCapacity > StringUTF16.MAX_LENGTH) {
- if (minimumCapacity >= StringUTF16.MAX_LENGTH) {
- throw new OutOfMemoryError();
- }
- newCapacity = StringUTF16.MAX_LENGTH;
- }
- this.value = Arrays.copyOf(value, newCapacity << coder);
+ return (minCapacity > SAFE_BOUND)
+ ? minCapacity : SAFE_BOUND;
}
/**
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/lang/StringBuilder/Capacity.java Wed Mar 02 14:10:40 2016 +0300
@@ -0,0 +1,182 @@
+/*
+ * Copyright (c) 2016, Oracle and/or its affiliates. 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 8149330
+ * @summary Basic set of tests of capacity management
+ * @run testng Capacity
+ */
+
+import java.lang.reflect.Field;
+import java.util.AbstractList;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.SplittableRandom;
+
+import org.testng.annotations.Test;
+import org.testng.annotations.DataProvider;
+import static org.testng.Assert.*;
+
+public class Capacity {
+ static final int DEFAULT_CAPACITY = 16;
+
+ private static int newCapacity(int oldCapacity,
+ int desiredCapacity)
+ {
+ return Math.max(oldCapacity * 2 + 2, desiredCapacity);
+ }
+
+ private static int nextNewCapacity(int oldCapacity) {
+ return newCapacity(oldCapacity, oldCapacity + 1);
+ }
+
+ @Test(dataProvider = "singleChar")
+ public void defaultCapacity(Character ch) {
+ StringBuilder sb = new StringBuilder();
+ assertEquals(sb.capacity(), DEFAULT_CAPACITY);
+ for (int i = 0; i < DEFAULT_CAPACITY; i++) {
+ sb.append(ch);
+ assertEquals(sb.capacity(), DEFAULT_CAPACITY);
+ }
+ sb.append(ch);
+ assertEquals(sb.capacity(), nextNewCapacity(DEFAULT_CAPACITY));
+ }
+
+ @Test(dataProvider = "charCapacity")
+ public void explicitCapacity(Character ch, int initCapacity) {
+ StringBuilder sb = new StringBuilder(initCapacity);
+ assertEquals(sb.capacity(), initCapacity);
+ for (int i = 0; i < initCapacity; i++) {
+ sb.append(ch);
+ assertEquals(sb.capacity(), initCapacity);
+ }
+ sb.append(ch);
+ assertEquals(sb.capacity(), nextNewCapacity(initCapacity));
+ }
+
+ @Test(dataProvider = "singleChar")
+ public void sbFromString(Character ch) {
+ String s = "string " + ch;
+ int expectedCapacity = s.length() + DEFAULT_CAPACITY;
+ StringBuilder sb = new StringBuilder(s);
+ assertEquals(sb.capacity(), expectedCapacity);
+ for (int i = 0; i < DEFAULT_CAPACITY; i++) {
+ sb.append(ch);
+ assertEquals(sb.capacity(), expectedCapacity);
+ }
+ sb.append(ch);
+ assertEquals(sb.capacity(), nextNewCapacity(expectedCapacity));
+ }
+
+ @Test(dataProvider = "singleChar")
+ public void sbFromCharSeq(Character ch) {
+ CharSequence cs = new MyCharSeq("char seq " + ch);
+ int expectedCapacity = cs.length() + DEFAULT_CAPACITY;
+ StringBuilder sb = new StringBuilder(cs);
+ assertEquals(sb.capacity(), expectedCapacity);
+ for (int i = 0; i < DEFAULT_CAPACITY; i++) {
+ sb.append(ch);
+ assertEquals(sb.capacity(), expectedCapacity);
+ }
+ sb.append(ch);
+ assertEquals(sb.capacity(), nextNewCapacity(expectedCapacity));
+ }
+
+ @Test(dataProvider = "charCapacity")
+ public void ensureCapacity(Character ch, int cap) {
+ StringBuilder sb = new StringBuilder(0);
+ assertEquals(sb.capacity(), 0);
+ sb.ensureCapacity(cap); // only has effect if cap > 0
+ int newCap = (cap == 0) ? 0 : newCapacity(0, cap);
+ assertEquals(sb.capacity(), newCap);
+ sb.ensureCapacity(newCap + 1);
+ assertEquals(sb.capacity(), nextNewCapacity(newCap));
+ sb.append(ch);
+ assertEquals(sb.capacity(), nextNewCapacity(newCap));
+ }
+
+ @Test(dataProvider = "negativeCapacity",
+ expectedExceptions = NegativeArraySizeException.class)
+ public void negativeInitialCapacity(int negCap) {
+ StringBuilder sb = new StringBuilder(negCap);
+ }
+
+ @Test(dataProvider = "negativeCapacity")
+ public void ensureNegativeCapacity(int negCap) {
+ StringBuilder sb = new StringBuilder();
+ sb.ensureCapacity(negCap);
+ assertEquals(sb.capacity(), DEFAULT_CAPACITY);
+ }
+
+ @Test(dataProvider = "charCapacity")
+ public void trimToSize(Character ch, int cap) {
+ StringBuilder sb = new StringBuilder(cap);
+ int halfOfCap = cap / 2;
+ for (int i = 0; i < halfOfCap; i++) {
+ sb.append(ch);
+ }
+ sb.trimToSize();
+ // according to the spec, capacity doesn't have to
+ // become exactly the size
+ assertTrue(sb.capacity() >= halfOfCap);
+ }
+
+ @DataProvider
+ public Object[][] singleChar() {
+ return new Object[][] { {'J'}, {'\u042b'} };
+ }
+
+ @DataProvider
+ public Object[][] charCapacity() {
+ return new Object[][] {
+ {'J', 0},
+ {'J', 1},
+ {'J', 15},
+ {'J', DEFAULT_CAPACITY},
+ {'J', 1024},
+ {'\u042b', 0},
+ {'\u042b', 1},
+ {'\u042b', 15},
+ {'\u042b', DEFAULT_CAPACITY},
+ {'\u042b', 1024},
+ };
+ }
+
+ @DataProvider
+ public Object[][] negativeCapacity() {
+ return new Object[][] { {-1}, {Integer.MIN_VALUE} };
+ }
+
+ private static class MyCharSeq implements CharSequence {
+ private CharSequence s;
+ public MyCharSeq(CharSequence s) { this.s = s; }
+ public char charAt(int i) { return s.charAt(i); }
+ public int length() { return s.length(); }
+ public CharSequence subSequence(int st, int e) {
+ return s.subSequence(st, e);
+ }
+ public String toString() { return s.toString(); }
+ }
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/lang/StringBuilder/HugeCapacity.java Wed Mar 02 14:10:40 2016 +0300
@@ -0,0 +1,66 @@
+/*
+ * Copyright (c) 2016, Oracle and/or its affiliates. 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 8149330
+ * @summary Capacity should not get close to Integer.MAX_VALUE unless
+ * necessary
+ * @run main/othervm -Xmx5G HugeCapacity
+ * @ignore This test has huge memory requirements
+ */
+
+public class HugeCapacity {
+ private static int failures = 0;
+
+ public static void main(String[] args) {
+ testLatin1();
+ testUtf16();
+ if (failures > 0) {
+ throw new RuntimeException(failures + " tests failed");
+ }
+ }
+
+ private static void testLatin1() {
+ try {
+ StringBuilder sb = new StringBuilder();
+ sb.ensureCapacity(Integer.MAX_VALUE / 2);
+ sb.ensureCapacity(Integer.MAX_VALUE / 2 + 1);
+ } catch (OutOfMemoryError oom) {
+ oom.printStackTrace();
+ failures++;
+ }
+ }
+
+ private static void testUtf16() {
+ try {
+ StringBuilder sb = new StringBuilder();
+ sb.append('\u042b');
+ sb.ensureCapacity(Integer.MAX_VALUE / 4);
+ sb.ensureCapacity(Integer.MAX_VALUE / 4 + 1);
+ } catch (OutOfMemoryError oom) {
+ oom.printStackTrace();
+ failures++;
+ }
+ }
+}