diff --git a/src/java.base/share/classes/java/util/ArrayDeque.java b/src/java.base/share/classes/java/util/ArrayDeque.java --- a/src/java.base/share/classes/java/util/ArrayDeque.java +++ b/src/java.base/share/classes/java/util/ArrayDeque.java @@ -180,7 +180,7 @@ public class ArrayDeque extends Abstr * sufficient to hold 16 elements. */ public ArrayDeque() { - elements = new Object[16]; + elements = new Object[16 + 1]; } /** diff --git a/src/java.base/share/classes/java/util/ArrayList.java b/src/java.base/share/classes/java/util/ArrayList.java --- a/src/java.base/share/classes/java/util/ArrayList.java +++ b/src/java.base/share/classes/java/util/ArrayList.java @@ -1729,7 +1729,6 @@ public class ArrayList extends Abstra @Override public void replaceAll(UnaryOperator operator) { replaceAllRange(operator, 0, size); - modCount++; } private void replaceAllRange(UnaryOperator operator, int i, int end) { diff --git a/src/java.base/share/classes/java/util/HashMap.java b/src/java.base/share/classes/java/util/HashMap.java --- a/src/java.base/share/classes/java/util/HashMap.java +++ b/src/java.base/share/classes/java/util/HashMap.java @@ -1263,9 +1263,7 @@ public class HashMap extends Abstra @Override public V merge(K key, V value, BiFunction remappingFunction) { - if (value == null) - throw new NullPointerException(); - if (remappingFunction == null) + if (value == null || remappingFunction == null) throw new NullPointerException(); int hash = hash(key); Node[] tab; Node first; int n, i; @@ -1308,8 +1306,7 @@ public class HashMap extends Abstra else removeNode(hash, key, null, false, true); return v; - } - if (value != null) { + } else { if (t != null) t.putTreeVal(this, tab, hash, key, value); else { @@ -1320,8 +1317,8 @@ public class HashMap extends Abstra ++modCount; ++size; afterNodeInsertion(true); + return value; } - return value; } @Override diff --git a/src/java.base/share/classes/java/util/Vector.java b/src/java.base/share/classes/java/util/Vector.java --- a/src/java.base/share/classes/java/util/Vector.java +++ b/src/java.base/share/classes/java/util/Vector.java @@ -1402,7 +1402,6 @@ public class Vector es[i] = operator.apply(elementAt(es, i)); if (modCount != expectedModCount) throw new ConcurrentModificationException(); - modCount++; } @SuppressWarnings("unchecked") diff --git a/test/jdk/java/util/ArrayDeque/WhiteBox.java b/test/jdk/java/util/ArrayDeque/WhiteBox.java new file mode 100644 --- /dev/null +++ b/test/jdk/java/util/ArrayDeque/WhiteBox.java @@ -0,0 +1,153 @@ +/* + * 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. + */ + +/* + * This file is available under and governed by the GNU General Public + * License version 2 only, as published by the Free Software Foundation. + * However, the following notice accompanied the original version of this + * file: + * + * Written by Martin Buchholz with assistance from members of JCP + * JSR-166 Expert Group and released to the public domain, as + * explained at http://creativecommons.org/publicdomain/zero/1.0/ + */ + +/* + * @test + * @modules java.base/java.util:open + * @run testng WhiteBox + * @summary White box tests of implementation details + */ + +import static org.testng.Assert.*; +import org.testng.annotations.Test; + +import java.io.ByteArrayInputStream; +import java.io.ByteArrayOutputStream; +import java.io.ObjectInputStream; +import java.io.ObjectOutputStream; +import java.lang.invoke.MethodHandles; +import java.lang.invoke.VarHandle; +import java.util.ArrayDeque; +import java.util.concurrent.ThreadLocalRandom; + +@Test +public class WhiteBox { + final ThreadLocalRandom rnd = ThreadLocalRandom.current(); + final VarHandle ELEMENTS, HEAD, TAIL; + + WhiteBox() throws ReflectiveOperationException { + Class klazz = ArrayDeque.class; + MethodHandles.Lookup lookup + = MethodHandles.privateLookupIn(klazz, MethodHandles.lookup()); + ELEMENTS = lookup.findVarHandle(klazz, "elements", Object[].class); + HEAD = lookup.findVarHandle(klazz, "head", int.class); + TAIL = lookup.findVarHandle(klazz, "tail", int.class); + } + + Object[] elements(ArrayDeque d) { return (Object[]) ELEMENTS.get(d); } + int head(ArrayDeque d) { return (int) HEAD.get(d); } + int tail(ArrayDeque d) { return (int) TAIL.get(d); } + + void checkCapacity(ArrayDeque d, int capacity) { + assertTrue(d.isEmpty()); + assertEquals(0, head(d)); + assertEquals(0, tail(d)); + Object[] initialElements = elements(d); + + assertInvariants(d); + for (int i = capacity; i--> 0; ) { + d.add(rnd.nextInt(42)); + assertSame(elements(d), initialElements); + assertInvariants(d); + } + + d.add(rnd.nextInt(42)); + assertNotSame(elements(d), initialElements); + assertInvariants(d); + } + + @Test + public void defaultConstructor() { + checkCapacity(new ArrayDeque(), 16); + } + + @Test + public void shouldNotResizeWhenInitialCapacityProvided() { + int initialCapacity = rnd.nextInt(20); + checkCapacity(new ArrayDeque(initialCapacity), initialCapacity); + } + + byte[] serialBytes(Object o) { + try { + ByteArrayOutputStream bos = new ByteArrayOutputStream(); + ObjectOutputStream oos = new ObjectOutputStream(bos); + oos.writeObject(o); + oos.flush(); + oos.close(); + return bos.toByteArray(); + } catch (Exception fail) { + throw new AssertionError(fail); + } + } + + @SuppressWarnings("unchecked") + T serialClone(T o) { + try { + ObjectInputStream ois = new ObjectInputStream + (new ByteArrayInputStream(serialBytes(o))); + T clone = (T) ois.readObject(); + assertNotSame(o, clone); + assertSame(o.getClass(), clone.getClass()); + return clone; + } catch (Exception fail) { + throw new AssertionError(fail); + } + } + + @Test + public void testSerialization() { + ArrayDeque[] ds = { new ArrayDeque(), new ArrayDeque(rnd.nextInt(20)) }; + for (ArrayDeque d : ds) { + if (rnd.nextBoolean()) d.add(99); + ArrayDeque clone = serialClone(d); + assertInvariants(clone); + assertNotSame(elements(d), elements(clone)); + assertEquals(d, clone); + } + } + + /** Checks conditions which should always be true. */ + void assertInvariants(ArrayDeque d) { + final Object[] elements = elements(d); + final int head = head(d); + final int tail = tail(d); + final int capacity = elements.length; + assertTrue(0 <= head && head < capacity); + assertTrue(0 <= tail && tail < capacity); + assertTrue(capacity > 0); + assertTrue(d.size() < capacity); + assertTrue((head == tail) ^ (elements[head] != null)); + assertNull(elements[tail]); + assertTrue((head == tail) ^ (elements[Math.floorMod(tail - 1, capacity)] != null)); + } +} diff --git a/test/jdk/java/util/concurrent/forkjoin/FJExceptionTableLeak.java b/test/jdk/java/util/concurrent/forkjoin/FJExceptionTableLeak.java --- a/test/jdk/java/util/concurrent/forkjoin/FJExceptionTableLeak.java +++ b/test/jdk/java/util/concurrent/forkjoin/FJExceptionTableLeak.java @@ -34,82 +34,136 @@ /* * @test - * @bug 8004138 + * @bug 8004138 8205576 * @modules java.base/java.util.concurrent:open + * @run testng FJExceptionTableLeak * @summary Checks that ForkJoinTask thrown exceptions are not leaked. * This whitebox test is sensitive to forkjoin implementation details. */ +import static org.testng.Assert.*; +import org.testng.annotations.Test; + import static java.util.concurrent.TimeUnit.MILLISECONDS; import java.lang.ref.ReferenceQueue; import java.lang.ref.WeakReference; -import java.lang.reflect.Field; +import java.lang.invoke.MethodHandles; +import java.lang.invoke.VarHandle; import java.util.ArrayList; import java.util.concurrent.CountDownLatch; import java.util.concurrent.ForkJoinPool; import java.util.concurrent.ForkJoinTask; import java.util.concurrent.RecursiveAction; +import java.util.concurrent.ThreadLocalRandom; +import java.util.concurrent.locks.ReentrantLock; import java.util.function.BooleanSupplier; +@Test public class FJExceptionTableLeak { + final ThreadLocalRandom rnd = ThreadLocalRandom.current(); + final VarHandle NEXT, EX; + final Object[] exceptionTable; + final ReentrantLock exceptionTableLock; + + FJExceptionTableLeak() throws ReflectiveOperationException { + MethodHandles.Lookup lookup = MethodHandles.privateLookupIn( + ForkJoinTask.class, MethodHandles.lookup()); + Class nodeClass = Class.forName( + ForkJoinTask.class.getName() + "$ExceptionNode"); + VarHandle exceptionTableHandle = lookup.findStaticVarHandle( + ForkJoinTask.class, "exceptionTable", arrayClass(nodeClass)); + VarHandle exceptionTableLockHandle = lookup.findStaticVarHandle( + ForkJoinTask.class, "exceptionTableLock", ReentrantLock.class); + exceptionTable = (Object[]) exceptionTableHandle.get(); + exceptionTableLock = (ReentrantLock) exceptionTableLockHandle.get(); + + NEXT = lookup.findVarHandle(nodeClass, "next", nodeClass); + EX = lookup.findVarHandle(nodeClass, "ex", Throwable.class); + } + + static Class arrayClass(Class klazz) { + try { + return (Class) Class.forName("[L" + klazz.getName() + ";"); + } catch (ReflectiveOperationException ex) { + throw new Error(ex); + } + } + + Object next(Object node) { return NEXT.get(node); } + Throwable ex(Object node) { return (Throwable) EX.get(node); } + static class FailingTaskException extends RuntimeException {} static class FailingTask extends RecursiveAction { public void compute() { throw new FailingTaskException(); } } - static int bucketsInuse(Object[] exceptionTable) { + /** Counts all FailingTaskExceptions still recorded in exceptionTable. */ + int retainedExceptions() { + exceptionTableLock.lock(); + try { int count = 0; - for (Object x : exceptionTable) - if (x != null) count++; + for (Object node : exceptionTable) + for (; node != null; node = next(node)) + if (ex(node) instanceof FailingTaskException) + count++; return count; + } finally { + exceptionTableLock.unlock(); + } } - public static void main(String[] args) throws Exception { - final ForkJoinPool pool = new ForkJoinPool(4); - final Field exceptionTableField = - ForkJoinTask.class.getDeclaredField("exceptionTable"); - exceptionTableField.setAccessible(true); - final Object[] exceptionTable = (Object[]) exceptionTableField.get(null); + @Test + public void exceptionTableCleanup() throws Exception { + ArrayList failedTasks = failedTasks(); + + // Retain a strong ref to one last failing task + FailingTask lastTask = failedTasks.get(rnd.nextInt(failedTasks.size())); + + // Clear all other strong refs, making exception table cleanable + failedTasks.clear(); - if (bucketsInuse(exceptionTable) != 0) throw new AssertionError(); + BooleanSupplier exceptionTableIsClean = () -> { + try { + // Trigger exception table expunging as side effect + lastTask.join(); + throw new AssertionError("should throw"); + } catch (FailingTaskException expected) {} + int count = retainedExceptions(); + if (count == 0) + throw new AssertionError("expected to find last task"); + return count == 1; + }; + gcAwait(exceptionTableIsClean); + } + + /** Sequestered into a separate method to inhibit GC retention. */ + ArrayList failedTasks() + throws Exception { + final ForkJoinPool pool = new ForkJoinPool(rnd.nextInt(1, 4)); + + assertEquals(0, retainedExceptions()); final ArrayList tasks = new ArrayList<>(); - // Keep submitting failing tasks until most of the exception - // table buckets are in use - do { - for (int i = 0; i < exceptionTable.length; i++) { + for (int i = exceptionTable.length; i--> 0; ) { FailingTask task = new FailingTask(); pool.execute(task); tasks.add(task); // retain strong refs to all tasks, for now + task = null; // excessive GC retention paranoia } for (FailingTask task : tasks) { try { task.join(); throw new AssertionError("should throw"); } catch (FailingTaskException success) {} + task = null; // excessive GC retention paranoia } - } while (bucketsInuse(exceptionTable) < exceptionTable.length * 3 / 4); - - // Retain a strong ref to one last failing task; - // task.join() will trigger exception table expunging. - FailingTask lastTask = tasks.get(0); - - // Clear all other strong refs, making exception table cleanable - tasks.clear(); - BooleanSupplier exceptionTableIsClean = () -> { - try { - lastTask.join(); - throw new AssertionError("should throw"); - } catch (FailingTaskException expected) {} - int count = bucketsInuse(exceptionTable); - if (count == 0) - throw new AssertionError("expected to find last task"); - return count == 1; - }; - gcAwait(exceptionTableIsClean); + if (rnd.nextBoolean()) + gcAwait(() -> retainedExceptions() == tasks.size()); + + return tasks; } // --------------- GC finalization infrastructure --------------- diff --git a/test/jdk/java/util/concurrent/tck/Collection8Test.java b/test/jdk/java/util/concurrent/tck/Collection8Test.java --- a/test/jdk/java/util/concurrent/tck/Collection8Test.java +++ b/test/jdk/java/util/concurrent/tck/Collection8Test.java @@ -979,7 +979,7 @@ public class Collection8Test extends JSR } catch (java.io.NotSerializableException acceptable) {} } - public void DISABLED_testReplaceAllIsNotStructuralModification() { + public void testReplaceAllIsNotStructuralModification() { Collection c = impl.emptyCollection(); if (!(c instanceof List)) return;