diff options
| author | Andrey Loskutov | 2022-01-14 15:15:14 +0000 |
|---|---|---|
| committer | Andrey Loskutov | 2022-01-15 09:13:17 +0000 |
| commit | d041f3803d811a0e9790d305639e77e557feceab (patch) | |
| tree | ebb376eca253b40a177b1f2d2827690d1e3dd55e | |
| parent | e48c5c71d428f69c32ea7ac51ce736ff9dfb0e59 (diff) | |
| download | eclipse.jdt.core-d041f3803d811a0e9790d305639e77e557feceab.tar.gz eclipse.jdt.core-d041f3803d811a0e9790d305639e77e557feceab.tar.xz eclipse.jdt.core-d041f3803d811a0e9790d305639e77e557feceab.zip | |
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>
8 files changed, 333 insertions, 57 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(); + } +} diff --git a/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/util/HashtableOfObject.java b/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/util/HashtableOfObject.java index 79d6dc5a08..2633884a0f 100644 --- a/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/util/HashtableOfObject.java +++ b/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/util/HashtableOfObject.java @@ -20,6 +20,9 @@ import org.eclipse.jdt.core.compiler.CharOperation; */ public final class HashtableOfObject implements Cloneable { + /** Max array size accepted by JVM */ + public static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 2; + // to avoid using Enumerations, walk the individual tables skipping nulls public char[] keyTable[]; public Object valueTable[]; @@ -31,13 +34,25 @@ public final class HashtableOfObject implements Cloneable { this(13); } + /** + * @param size preferred table size + * @throws NegativeArraySizeException if size is negative + * @throws OutOfMemoryError if size exceeds {@link #MAX_ARRAY_SIZE} + */ public HashtableOfObject(int size) { - + if (size < 0) { + throw new NegativeArraySizeException("Bad attempt to create table with " + size + " elements"); //$NON-NLS-1$ //$NON-NLS-2$ + } this.elementSize = 0; this.threshold = size; // size represents the expected number of elements int extraRoom = (int) (size * 1.75f); - if (this.threshold == extraRoom) + if (this.threshold == extraRoom) { extraRoom++; + } + // Check for integer overflow & max array size limit + if (extraRoom < 1 || extraRoom > MAX_ARRAY_SIZE) { + extraRoom = calculateNewSize(size); + } this.keyTable = new char[extraRoom][]; this.valueTable = new Object[extraRoom]; } @@ -165,8 +180,8 @@ public final class HashtableOfObject implements Cloneable { } private void rehash() { - - HashtableOfObject newHashtable = new HashtableOfObject(this.elementSize * 2); // double the number of expected elements + int newSize = calculateNewSize(this.elementSize); + HashtableOfObject newHashtable = new HashtableOfObject(newSize); char[] currentKey; for (int i = this.keyTable.length; --i >= 0;) if ((currentKey = this.keyTable[i]) != null) @@ -177,6 +192,42 @@ public final class HashtableOfObject implements Cloneable { this.threshold = newHashtable.threshold; } + /** + * Tries to double the number of given elements but returns {@link #MAX_ARRAY_SIZE} - 2 in case new value would + * overflow + * + * @return new map size that fits to JVM limits or throws an error + */ + public static int calculateNewSize(int currentSize) { + if(currentSize == 0) { + return 1; + } + if(currentSize < 0) { + throw new NegativeArraySizeException("Bad attempt to calculate table size with " + currentSize + " elements"); //$NON-NLS-1$ //$NON-NLS-2$ + } + + // double the number of expected elements + int newSize = currentSize * 2; + + // int overflow or JVM limit hit + if (newSize + 1 < 1 || newSize + 1 >= MAX_ARRAY_SIZE) { + // add half of space between current size and max array size + newSize = currentSize + (MAX_ARRAY_SIZE - currentSize) / 2; + if (newSize + 1 < 1 || newSize + 1 >= MAX_ARRAY_SIZE) { + // use max possible value + newSize = MAX_ARRAY_SIZE - 2; + if (newSize <= currentSize) { + throw new OutOfMemoryError("Unable to increase table size over " + currentSize + " elements"); //$NON-NLS-1$ //$NON-NLS-2$ + } + } + } + return newSize; + } + + public int storageSize() { + return this.keyTable.length; + } + public int size() { return this.elementSize; } diff --git a/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/index/DiskIndex.java b/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/index/DiskIndex.java index 5732c6741b..6915594bbf 100644 --- a/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/index/DiskIndex.java +++ b/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/index/DiskIndex.java @@ -14,6 +14,8 @@ package org.eclipse.jdt.internal.core.index; import java.io.*; +import java.nio.file.Files; +import java.nio.file.StandardCopyOption; import java.util.regex.Pattern; import org.eclipse.jdt.core.compiler.CharOperation; @@ -585,28 +587,35 @@ DiskIndex mergeWith(MemoryIndex memoryIndex) throws IOException { newDiskIndex.writeOffsetToHeader(offsetToHeader); // rename file by deleting previous index file & renaming temp one - if (oldIndexFile.exists() && !oldIndexFile.delete()) { - if (DEBUG) - System.out.println("mergeWith - Failed to delete " + this.indexLocation); //$NON-NLS-1$ - throw new IOException("Failed to delete index file " + this.indexLocation); //$NON-NLS-1$ + try { + Files.deleteIfExists(oldIndexFile.toPath()); + } catch (Exception e2) { + throw new IOException("Failed to delete index file " + this.indexLocation, e2); //$NON-NLS-1$ } - if (!usingTmp && !newIndexFile.renameTo(oldIndexFile)) { - // try again after waiting for two milli secs + if (!usingTmp) { try { - Thread.sleep(2); - } catch (InterruptedException e) { - //ignore - } - if (!newIndexFile.renameTo(oldIndexFile)) { - if (DEBUG) - System.out.println("mergeWith - Failed to rename " + this.indexLocation); //$NON-NLS-1$ - usingTmp = true; + Files.move(newIndexFile.toPath(), oldIndexFile.toPath(), StandardCopyOption.REPLACE_EXISTING); + } catch (IOException ioe) { + // try again after waiting for two milli secs + try { + Thread.sleep(2); + } catch (InterruptedException e) { + //ignore + } + try { + Files.move(newIndexFile.toPath(), oldIndexFile.toPath(), StandardCopyOption.REPLACE_EXISTING); + } catch (IOException e) { + Util.log(ioe, "mergeWith - Failed to rename index " + this.indexLocation); //$NON-NLS-1$ + usingTmp = true; + } } } } catch (IOException e) { - if (newIndexFile.exists() && !newIndexFile.delete()) - if (DEBUG) - System.out.println("mergeWith - Failed to delete temp index " + newDiskIndex.indexLocation); //$NON-NLS-1$ + try { + Files.deleteIfExists(newIndexFile.toPath()); + } catch (Exception e2) { + Util.log(e2, "mergeWith - Failed to delete temp index " + newDiskIndex.indexLocation); //$NON-NLS-1$ + } throw e; } @@ -669,23 +678,11 @@ private synchronized HashtableOfObject readCategoryTable(char[] categoryName, bo this.bufferEnd = stream.read(this.streamBuffer, 0, this.streamBuffer.length); int size = readStreamInt(stream); try { - if (size < 0) { // DEBUG - System.err.println("-------------------- DEBUG --------------------"); //$NON-NLS-1$ - System.err.println("file = "+this.indexLocation); //$NON-NLS-1$ - System.err.println("offset = "+offset); //$NON-NLS-1$ - System.err.println("size = "+size); //$NON-NLS-1$ - System.err.println("-------------------- END --------------------"); //$NON-NLS-1$ - } categoryTable = new HashtableOfObject(size); - } catch (OutOfMemoryError oom) { - // DEBUG - oom.printStackTrace(); - System.err.println("-------------------- DEBUG --------------------"); //$NON-NLS-1$ - System.err.println("file = "+this.indexLocation); //$NON-NLS-1$ - System.err.println("offset = "+offset); //$NON-NLS-1$ - System.err.println("size = "+size); //$NON-NLS-1$ - System.err.println("-------------------- END --------------------"); //$NON-NLS-1$ - throw oom; + } catch (NegativeArraySizeException | OutOfMemoryError e) { + String message = "Failed to read index data from " + this.indexLocation + " at offset " + offset //$NON-NLS-1$ //$NON-NLS-2$ + + " and size " + size; //$NON-NLS-1$ + throw new IOException(message, e); } int largeArraySize = 256; for (int i = 0; i < size; i++) { diff --git a/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/search/PatternSearchJob.java b/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/search/PatternSearchJob.java index 7054192453..daf2518378 100644 --- a/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/search/PatternSearchJob.java +++ b/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/search/PatternSearchJob.java @@ -242,8 +242,14 @@ public boolean search(Index index, IndexQueryRequestor queryRequestor, IProgress this.executionTime.addAndGet(System.currentTimeMillis() - start); return COMPLETE; } catch (IOException e) { - if (e instanceof java.io.EOFException) + if (e instanceof java.io.EOFException) { e.printStackTrace(); + } else { + Throwable cause = e.getCause(); + if (cause != null) { + Util.log(e, "Search failed for index " + index); //$NON-NLS-1$ + } + } return FAILED; } finally { monitor.exitRead(); // finished reading diff --git a/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/search/indexing/AddJarFileToIndex.java b/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/search/indexing/AddJarFileToIndex.java index ea722725c2..496ef0ced4 100644 --- a/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/search/indexing/AddJarFileToIndex.java +++ b/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/search/indexing/AddJarFileToIndex.java @@ -279,10 +279,7 @@ class AddJarFileToIndex extends BinaryContainer { monitor.exitWrite(); // free write lock } } catch (IOException | ZipError e) { - if (JobManager.VERBOSE) { - org.eclipse.jdt.internal.core.util.Util.verbose("-> failed to index " + this.containerPath + " because of the following exception:"); //$NON-NLS-1$ //$NON-NLS-2$ - e.printStackTrace(); - } + org.eclipse.jdt.internal.core.util.Util.log(e, "Failed to index " + this.containerPath); //$NON-NLS-1$ this.manager.removeIndex(this.containerPath); return false; } diff --git a/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/search/indexing/AddJrtToIndex.java b/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/search/indexing/AddJrtToIndex.java index ba64a2e082..0f20ecd577 100644 --- a/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/search/indexing/AddJrtToIndex.java +++ b/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/search/indexing/AddJrtToIndex.java @@ -281,10 +281,7 @@ public class AddJrtToIndex extends BinaryContainer { monitor.exitWrite(); } } catch (IOException e ) { - if (JobManager.VERBOSE) { - org.eclipse.jdt.internal.core.util.Util.verbose("-> failed to index " + this.containerPath + " because of the following exception:"); //$NON-NLS-1$ //$NON-NLS-2$ - e.printStackTrace(); - } + org.eclipse.jdt.internal.core.util.Util.log(e, "Failed to index " + this.containerPath); //$NON-NLS-1$ this.manager.removeIndex(this.containerPath); return false; } diff --git a/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/search/indexing/IndexManager.java b/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/search/indexing/IndexManager.java index 540556e8f9..241abb3d52 100644 --- a/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/search/indexing/IndexManager.java +++ b/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/search/indexing/IndexManager.java @@ -1190,11 +1190,8 @@ public void saveIndexes() { if (monitor.exitReadEnterWrite()) { try { saveIndex(index); - } catch(IOException e) { - if (VERBOSE) { - Util.verbose("-> got the following exception while saving:", System.err); //$NON-NLS-1$ - e.printStackTrace(); - } + } catch(IOException | NegativeArraySizeException | OutOfMemoryError e) { + Util.log(e, "Failed to save JDT index: " + index.toString()); //$NON-NLS-1$ allSaved = false; } finally { monitor.exitWriteEnterRead(); @@ -1775,9 +1772,15 @@ class MetaIndexUpdateRequest implements IJob { try { updateMetaIndex(indexFile.getName(), index.getMetaIndexQualifications()); } catch (IOException e) { - if (JobManager.VERBOSE) { - Util.verbose("-> failed to update meta index for index " + indexFile.getName() + " because of the following exception:"); //$NON-NLS-1$ //$NON-NLS-2$ - e.printStackTrace(); + Throwable cause = e.getCause(); + if (cause != null) { + Util.log(e, "Failed to update meta index"); //$NON-NLS-1$ + } else { + if (JobManager.VERBOSE) { + Util.verbose("-> failed to update meta index for index " + indexFile.getName() //$NON-NLS-1$ + + " because of the following exception:"); //$NON-NLS-1$ + e.printStackTrace(); + } } } } |
