Bug 578211 - an attempt to improve HashtableOfObject size issuesI20220116-1800I20220115-1800

HashtableOfObject changes:

- Added extra checks for negative/too large table size values.
- Table can be created with size up to Integer.MAX_VALUE - 2 (before it
was Integer.MAX_VALUE / 1.75) and will throw OOME with specific error
information if table can't be increased in size anymore.
- rehash() uses now adoptive size calculation (not just doubles the
array size), and will throw OOME with specific error information if
table can't be increased in size anymore.
- added unit tests for expected possible HashtableOfObject sizes.

Related caller changes:

- IndexManager.saveIndexes() catches additionally
NegativeArraySizeException & OutOfMemoryError if index write fails, and
logs failed index name.
- DiskIndex.readCategoryTable() report IO error in case
HashtableOfObject reports NegativeArraySizeException or
OutOfMemoryError.
- DiskIndex.mergeWith() uses nio API for index move/delete and report IO
errors now.
- PatternSearchJob/AddJarFileToIndex/AddJrtToIndex report IO errors now.

Change-Id: I11255589705ea03fdbc08b6a452b211aca013c62
Signed-off-by: Andrey Loskutov <loskutov@gmx.de>
Reviewed-on: https://git.eclipse.org/r/c/jdt/eclipse.jdt.core/+/189648
Tested-by: JDT Bot <jdt-bot@eclipse.org>

2 files changed, 228 insertions, 3 deletions

diff --git a/org.eclipse.jdt.core.tests.compiler/src/org/eclipse/jdt/core/tests/compiler/regression/TestAll.java b/org.eclipse.jdt.core.tests.compiler/src/org/eclipse/jdt/core/tests/compiler/regression/TestAll.java
index 26ce171052..cfae158648 100644
--- a/org.eclipse.jdt.core.tests.compiler/src/org/eclipse/jdt/core/tests/compiler/regression/TestAll.java
+++ b/org.eclipse.jdt.core.tests.compiler/src/org/eclipse/jdt/core/tests/compiler/regression/TestAll.java
@@ -25,15 +25,16 @@ package org.eclipse.jdt.core.tests.compiler.regression;
 
 import java.util.ArrayList;
 
-import junit.framework.Test;
-import junit.framework.TestSuite;
-
+import org.eclipse.jdt.core.tests.compiler.util.HashtableOfObjectTest;
 import org.eclipse.jdt.core.tests.dom.StandAloneASTParserTest;
 import org.eclipse.jdt.core.tests.junit.extension.TestCase;
 import org.eclipse.jdt.core.tests.util.AbstractCompilerTest;
 import org.eclipse.jdt.internal.compiler.classfmt.ClassFileConstants;
 import org.eclipse.jdt.internal.compiler.flow.UnconditionalFlowInfo;
 
+import junit.framework.Test;
+import junit.framework.TestSuite;
+
 /**
  * Run all compiler regression tests
  */
@@ -223,6 +224,7 @@ public static Test suite() {
 	 // Build final test suite
 	TestSuite all = new TestSuite(TestAll.class.getName());
 	all.addTest(new TestSuite(StandAloneASTParserTest.class));
+	all.addTest(new TestSuite(HashtableOfObjectTest.class));
 	int possibleComplianceLevels = AbstractCompilerTest.getPossibleComplianceLevels();
 	if ((possibleComplianceLevels & AbstractCompilerTest.F_1_3) != 0) {
 		ArrayList tests_1_3 = (ArrayList)standardTests.clone();
diff --git a/org.eclipse.jdt.core.tests.compiler/src/org/eclipse/jdt/core/tests/compiler/util/HashtableOfObjectTest.java b/org.eclipse.jdt.core.tests.compiler/src/org/eclipse/jdt/core/tests/compiler/util/HashtableOfObjectTest.java
new file mode 100644
index 0000000000..a4c36d6845
--- /dev/null
+++ b/org.eclipse.jdt.core.tests.compiler/src/org/eclipse/jdt/core/tests/compiler/util/HashtableOfObjectTest.java
@@ -0,0 +1,223 @@
+/*******************************************************************************
+ * Copyright (c) 2022 Andrey Loskujtov, and others.
+ *
+ * This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License 2.0
+ * which accompanies this distribution, and is available at
+ * https://www.eclipse.org/legal/epl-2.0/
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ *
+ * Contributors:
+ *     Andrey Loskutov (loskutov@gmx.de) - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.jdt.core.tests.compiler.util;
+
+import static org.eclipse.jdt.internal.compiler.util.HashtableOfObject.MAX_ARRAY_SIZE;
+import static org.eclipse.jdt.internal.compiler.util.HashtableOfObject.calculateNewSize;
+
+import org.eclipse.jdt.core.tests.junit.extension.TestCase;
+import org.eclipse.jdt.internal.compiler.util.HashtableOfObject;
+
+public class HashtableOfObjectTest extends TestCase {
+
+	public HashtableOfObjectTest(String name) {
+		super(name);
+	}
+
+	public void testCalculateNewSize() {
+		int input;
+		int expected;
+
+		// Overflow
+		input = Integer.MAX_VALUE * 2;
+		try {
+			calculateNewSize(input);
+			fail("Should not accept " + input);
+		} catch (NegativeArraySizeException e) {
+			// expected
+		}
+		input = Integer.MAX_VALUE + 1;
+		try {
+			calculateNewSize(input);
+			fail("Should not accept " + input);
+		} catch (NegativeArraySizeException e) {
+			// expected
+		}
+		input = -1;
+		try {
+			calculateNewSize(input);
+			fail("Should not accept " + input);
+		} catch (NegativeArraySizeException e) {
+			// expected
+		}
+
+		// Regular size
+		assertEquals(1, calculateNewSize(0));
+		assertEquals(2, calculateNewSize(1));
+
+		input = (MAX_ARRAY_SIZE / 2) - 10000;
+		expected = input * 2;
+		assertEquals(expected, calculateNewSize(input));
+
+		input = (MAX_ARRAY_SIZE / 2) - 1;
+		expected = input * 2;
+		assertEquals(expected, calculateNewSize(input));
+
+		input = (MAX_ARRAY_SIZE / 2);
+		expected = input + (MAX_ARRAY_SIZE - input) / 2;
+		assertEquals(expected, calculateNewSize(input));
+
+		// Can't simply double the size
+		input = (MAX_ARRAY_SIZE / 2) + 1;
+		expected = input + (MAX_ARRAY_SIZE - input) / 2;
+		assertEquals(expected, calculateNewSize(input));
+
+		input = (MAX_ARRAY_SIZE / 2) + 10000;
+		expected = input + (MAX_ARRAY_SIZE - input) / 2;
+		assertEquals(expected, calculateNewSize(input));
+
+		// Last few possible sizes
+		input = MAX_ARRAY_SIZE - 4;
+		expected = input + (MAX_ARRAY_SIZE - input) / 2;
+		assertEquals(expected, calculateNewSize(input));
+
+		input = MAX_ARRAY_SIZE - 3;
+		expected = input + 1;
+		assertEquals(expected, calculateNewSize(input));
+
+		// No way to increase
+		try {
+			input = MAX_ARRAY_SIZE - 2;
+			calculateNewSize(input);
+			fail("Should not support table size " + input);
+		} catch (OutOfMemoryError e) {
+			// expected
+		}
+		try {
+			input = MAX_ARRAY_SIZE - 1;
+			calculateNewSize(input);
+			fail("Should not support table size " + input);
+		} catch (OutOfMemoryError e) {
+			// expected
+		}
+		try {
+			input = MAX_ARRAY_SIZE;
+			calculateNewSize(input);
+			fail("Should not support table size " + input);
+		} catch (OutOfMemoryError e) {
+			// expected
+		}
+		try {
+			input = Integer.MAX_VALUE - 1;
+			calculateNewSize(input);
+			fail("Should not support table size " + input);
+		} catch (OutOfMemoryError e) {
+			// expected
+		}
+		try {
+			input = Integer.MAX_VALUE;
+			calculateNewSize(input);
+			fail("Should not support table size " + input);
+		} catch (OutOfMemoryError e) {
+			// expected
+		}
+	}
+
+	public void testCreateNewTable() {
+		int input;
+		int expected;
+		// Overflow
+		input = Integer.MAX_VALUE + 1;
+		try {
+			new HashtableOfObject(input);
+			fail("Should not accept " + input);
+		} catch (NegativeArraySizeException e) {
+			// expected
+		}
+		input = Integer.MAX_VALUE * 2;
+		try {
+			new HashtableOfObject(input);
+			fail("Should not accept " + input);
+		} catch (NegativeArraySizeException e) {
+			// expected
+		}
+		input = Integer.MAX_VALUE * 2 + 1;
+		try {
+			new HashtableOfObject(input);
+			fail("Should not accept " + input);
+		} catch (NegativeArraySizeException e) {
+			// expected
+		}
+		input = -1;
+		try {
+			new HashtableOfObject(input);
+			fail("Should not accept " + input);
+		} catch (NegativeArraySizeException e) {
+			// expected
+		}
+
+		// Regular sizes
+		assertEquals(1, new HashtableOfObject(0).storageSize());
+		assertEquals(2, new HashtableOfObject(1).storageSize());
+		assertEquals(3, new HashtableOfObject(2).storageSize());
+
+		// No way to increase
+		try {
+			input = MAX_ARRAY_SIZE - 2;
+			new HashtableOfObject(input);
+			fail("Should support table size " + input);
+		} catch (OutOfMemoryError e) {
+			// expected
+		}
+		try {
+			input = MAX_ARRAY_SIZE - 1;
+			new HashtableOfObject(input);
+			fail("Should support table size " + input);
+		} catch (OutOfMemoryError e) {
+			// expected
+		}
+		try {
+			input = MAX_ARRAY_SIZE;
+			new HashtableOfObject(input);
+			fail("Should not accept " + input);
+		} catch (OutOfMemoryError e) {
+			// expected
+		}
+		try {
+			input = Integer.MAX_VALUE - 1;
+			new HashtableOfObject(input);
+			fail("Should not accept " + input);
+		} catch (OutOfMemoryError e) {
+			// expected
+		}
+		try {
+			input = Integer.MAX_VALUE;
+			new HashtableOfObject(input);
+			fail("Should not accept " + input);
+		} catch (OutOfMemoryError e) {
+			// expected
+		}
+
+		if(Runtime.getRuntime().maxMemory() / (1024 * 1024) < 31000) {
+			// requires lot of heap
+			return;
+		}
+
+		// Can't simply double the size
+		input = (int)(MAX_ARRAY_SIZE / 1.75);
+		expected = input + (MAX_ARRAY_SIZE - input) / 2;
+		assertEquals(expected, new HashtableOfObject(input).storageSize());
+
+		input = MAX_ARRAY_SIZE - 4;
+		expected = input + (MAX_ARRAY_SIZE - input) / 2;
+		assertEquals(expected, new HashtableOfObject(input).storageSize());
+
+		// Last possible size
+		input = MAX_ARRAY_SIZE - 3;
+		expected = input + 1;
+		assertEquals(expected, new HashtableOfObject(input).storageSize());
+
+		System.gc();
+	}
+}