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 @@ @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 @@ -501,9 +501,14 @@ (int)ft : MAXIMUM_CAPACITY); if (t > threshold) threshold = tableSizeFor(t); + } else { + // Because of linked-list bucket constraints, we cannot + // expand all at once, but can reduce total resize + // effort by repeated doubling now vs later + while (s > threshold && table.length < MAXIMUM_CAPACITY) + resize(); } - else if (s > threshold) - resize(); + for (Map.Entry e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); 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 @@ es[i] = operator.apply(elementAt(es, i)); if (modCount != expectedModCount) throw new ConcurrentModificationException(); - modCount++; } @SuppressWarnings("unchecked") diff --git a/src/java.base/share/classes/java/util/concurrent/CyclicBarrier.java b/src/java.base/share/classes/java/util/concurrent/CyclicBarrier.java --- a/src/java.base/share/classes/java/util/concurrent/CyclicBarrier.java +++ b/src/java.base/share/classes/java/util/concurrent/CyclicBarrier.java @@ -98,12 +98,11 @@ * } * }} * - * Here, each worker thread processes a row of the matrix then waits at the - * barrier until all rows have been processed. When all rows are processed - * the supplied {@link Runnable} barrier action is executed and merges the - * rows. If the merger - * determines that a solution has been found then {@code done()} will return - * {@code true} and each worker will terminate. + * Here, each worker thread processes a row of the matrix, then waits at the + * barrier until all rows have been processed. When all rows are processed the + * supplied {@link Runnable} barrier action is executed and merges the rows. + * If the merger determines that a solution has been found then {@code done()} + * will return {@code true} and each worker will terminate. * *

If the barrier action does not rely on the parties being suspended when * it is executed, then any of the threads in the party could execute that @@ -132,6 +131,7 @@ * corresponding {@code await()} in other threads. * * @see CountDownLatch + * @see Phaser * * @author Doug Lea * @since 1.5 @@ -214,18 +214,17 @@ int index = --count; if (index == 0) { // tripped - boolean ranAction = false; - try { - final Runnable command = barrierCommand; - if (command != null) + Runnable command = barrierCommand; + if (command != null) { + try { command.run(); - ranAction = true; - nextGeneration(); - return 0; - } finally { - if (!ranAction) + } catch (Throwable ex) { breakBarrier(); + throw ex; + } } + nextGeneration(); + return 0; } // loop until tripped, broken, interrupted, or timed out diff --git a/src/java.base/share/classes/java/util/concurrent/ForkJoinPool.java b/src/java.base/share/classes/java/util/concurrent/ForkJoinPool.java --- a/src/java.base/share/classes/java/util/concurrent/ForkJoinPool.java +++ b/src/java.base/share/classes/java/util/concurrent/ForkJoinPool.java @@ -445,8 +445,7 @@ * if to its current value). This would be extremely costly. So * we relax it in several ways: (1) Producers only signal when * their queue is possibly empty at some point during a push - * operation (which requires conservatively checking size zero or - * one to cover races). (2) Other workers propagate this signal + * operation. (2) Other workers propagate this signal * when they find tasks in a queue with size greater than one. (3) * Workers only enqueue after scanning (see below) and not finding * any tasks. (4) Rather than CASing ctl to its current value in @@ -762,10 +761,8 @@ /** * The maximum number of top-level polls per worker before - * checking other queues, expressed as a bit shift to, in effect, - * multiply by pool size, and then use as random value mask, so - * average bound is about poolSize*(1< task) { ForkJoinTask[] a; - int s = top, d, cap, m; + int s = top, d = s - base, cap, m; ForkJoinPool p = pool; if ((a = array) != null && (cap = a.length) > 0) { QA.setRelease(a, (m = cap - 1) & s, task); top = s + 1; - if (((d = s - (int)BASE.getAcquire(this)) & ~1) == 0 && - p != null) { // size 0 or 1 - VarHandle.fullFence(); - p.signalWork(); + if (d == m) + growArray(false); + else if (QA.getAcquire(a, m & (s - 1)) == null && p != null) { + VarHandle.fullFence(); // was empty + p.signalWork(null); } - else if (d == m) - growArray(false); } } @@ -863,16 +859,16 @@ final boolean lockedPush(ForkJoinTask task) { ForkJoinTask[] a; boolean signal = false; - int s = top, b = base, cap, d; + int s = top, d = s - base, cap, m; if ((a = array) != null && (cap = a.length) > 0) { - a[(cap - 1) & s] = task; + a[(m = (cap - 1)) & s] = task; top = s + 1; - if (b - s + cap - 1 == 0) + if (d == m) growArray(true); else { phase = 0; // full volatile unlock - if (((s - base) & ~1) == 0) // size 0 or 1 - signal = true; + if (a[m & (s - 1)] == null) + signal = true; // was empty } } return signal; @@ -1014,25 +1010,30 @@ * queue, up to bound n (to avoid infinite unfairness). */ final void topLevelExec(ForkJoinTask t, WorkQueue q, int n) { - if (t != null && q != null) { // hoist checks - int nstolen = 1; - for (;;) { + int nstolen = 1; + for (int j = 0;;) { + if (t != null) t.doExec(); - if (n-- < 0) + if (j++ <= n) + t = nextLocalTask(); + else { + j = 0; + t = null; + } + if (t == null) { + if (q != null && (t = q.poll()) != null) { + ++nstolen; + j = 0; + } + else if (j != 0) break; - else if ((t = nextLocalTask()) == null) { - if ((t = q.poll()) == null) - break; - else - ++nstolen; - } } - ForkJoinWorkerThread thread = owner; - nsteals += nstolen; - source = 0; - if (thread != null) - thread.afterTopLevelExec(); } + ForkJoinWorkerThread thread = owner; + nsteals += nstolen; + source = 0; + if (thread != null) + thread.afterTopLevelExec(); } /** @@ -1455,7 +1456,7 @@ if (!tryTerminate(false, false) && // possibly replace worker w != null && w.array != null) // avoid repeated failures - signalWork(); + signalWork(null); if (ex == null) // help clean on way out ForkJoinTask.helpExpungeStaleExceptions(); @@ -1465,8 +1466,9 @@ /** * Tries to create or release a worker if too few are running. + * @param q if non-null recheck if empty on CAS failure */ - final void signalWork() { + final void signalWork(WorkQueue q) { for (;;) { long c; int sp; WorkQueue[] ws; int i; WorkQueue v; if ((c = ctl) >= 0L) // enough workers @@ -1493,6 +1495,8 @@ LockSupport.unpark(vt); break; } + else if (q != null && q.isEmpty()) // no need to retry + break; } } } @@ -1613,19 +1617,24 @@ else if (rc <= 0 && (md & SHUTDOWN) != 0 && tryTerminate(false, false)) break; // quiescent shutdown - else if (rc <= 0 && pred != 0 && phase == (int)c) { - long nc = (UC_MASK & (c - TC_UNIT)) | (SP_MASK & pred); - long d = keepAlive + System.currentTimeMillis(); - LockSupport.parkUntil(this, d); - if (ctl == c && // drop on timeout if all idle - d - System.currentTimeMillis() <= TIMEOUT_SLOP && - CTL.compareAndSet(this, c, nc)) { - w.phase = QUIET; - break; + else if (w.phase < 0) { + if (rc <= 0 && pred != 0 && phase == (int)c) { + long nc = (UC_MASK & (c - TC_UNIT)) | (SP_MASK & pred); + long d = keepAlive + System.currentTimeMillis(); + LockSupport.parkUntil(this, d); + if (ctl == c && // drop on timeout if all idle + d - System.currentTimeMillis() <= TIMEOUT_SLOP && + CTL.compareAndSet(this, c, nc)) { + w.phase = QUIET; + break; + } + } + else { + LockSupport.park(this); + if (w.phase < 0) // one spurious wakeup check + LockSupport.park(this); } } - else if (w.phase < 0) - LockSupport.park(this); // OK if spuriously woken w.source = 0; // disable signal } } @@ -1651,10 +1660,10 @@ QA.compareAndSet(a, k, t, null)) { q.base = b; w.source = qid; - if (q.top - b > 0) - signalWork(); + if (a[(cap - 1) & b] != null) + signalWork(q); // help signal if more tasks w.topLevelExec(t, q, // random fairness bound - r & ((n << TOP_BOUND_SHIFT) - 1)); + (r | (1 << TOP_BOUND_SHIFT)) & SMASK); } } return true; @@ -1900,7 +1909,7 @@ r = ThreadLocalRandom.advanceProbe(r); else { if (q.lockedPush(task)) - signalWork(); + signalWork(null); return; } } diff --git a/src/java.base/share/classes/java/util/concurrent/ForkJoinWorkerThread.java b/src/java.base/share/classes/java/util/concurrent/ForkJoinWorkerThread.java --- a/src/java.base/share/classes/java/util/concurrent/ForkJoinWorkerThread.java +++ b/src/java.base/share/classes/java/util/concurrent/ForkJoinWorkerThread.java @@ -236,7 +236,8 @@ @Override // paranoically public void setContextClassLoader(ClassLoader cl) { - throw new SecurityException("setContextClassLoader"); + if (cl != null && ClassLoader.getSystemClassLoader() != cl) + throw new SecurityException("setContextClassLoader"); } } } diff --git a/test/jdk/java/util/Collection/IteratorMicroBenchmark.java b/test/jdk/java/util/Collection/IteratorMicroBenchmark.java --- a/test/jdk/java/util/Collection/IteratorMicroBenchmark.java +++ b/test/jdk/java/util/Collection/IteratorMicroBenchmark.java @@ -69,8 +69,6 @@ * Be patient; this program runs for a very long time. * For faster runs, restrict execution using command line args. * - * This is an interface based version of ArrayList/IteratorMicroBenchmark - * * @author Martin Buchholz */ public class IteratorMicroBenchmark { @@ -115,7 +113,9 @@ CountDownLatch finalized = new CountDownLatch(1); ReferenceQueue queue = new ReferenceQueue<>(); WeakReference ref = new WeakReference<>( - new Object() { protected void finalize() { finalized.countDown(); }}, + new Object() { + @SuppressWarnings("deprecation") + protected void finalize() { finalized.countDown(); }}, queue); try { for (int tries = 3; tries--> 0; ) { @@ -267,16 +267,22 @@ }); } - static List makeSubList(List list) { + String goodClassName(Object x) { + return goodClassName(x.getClass()); + } + + static List makeSubList( + List elements, + UnaryOperator> copyConstructor) { + final ArrayList padded = new ArrayList<>(); final ThreadLocalRandom rnd = ThreadLocalRandom.current(); - int size = list.size(); - if (size <= 2) return list.subList(0, size); - List subList = list.subList(rnd.nextInt(0, 2), - size - rnd.nextInt(0, 2)); - List copy = new ArrayList<>(list); - subList.clear(); - subList.addAll(copy); - return subList; + final int frontPorch = rnd.nextInt(3); + final int backPorch = rnd.nextInt(3); + for (int n = frontPorch; n--> 0; ) padded.add(rnd.nextInt()); + padded.addAll(elements); + for (int n = backPorch; n--> 0; ) padded.add(rnd.nextInt()); + return copyConstructor.apply(padded) + .subList(frontPorch, frontPorch + elements.size()); } void run() throws Throwable { @@ -297,22 +303,42 @@ abq.add(abq.remove()); } - ArrayList jobs = Stream.>of( - al, ad, abq, - makeSubList(new ArrayList<>(al)), + final Integer[] array = al.toArray(new Integer[0]); + final List immutableSubList + = makeSubList(al, x -> List.of(x.toArray(new Integer[0]))); + + Stream> collections = concatStreams( + Stream.of( + // Lists and their subLists + al, + makeSubList(al, ArrayList::new), + new Vector<>(al), + makeSubList(al, Vector::new), new LinkedList<>(al), - makeSubList(new LinkedList<>(al)), + makeSubList(al, LinkedList::new), + new CopyOnWriteArrayList<>(al), + makeSubList(al, CopyOnWriteArrayList::new), + + ad, new PriorityQueue<>(al), - new Vector<>(al), - makeSubList(new Vector<>(al)), - new CopyOnWriteArrayList<>(al), - makeSubList(new CopyOnWriteArrayList<>(al)), new ConcurrentLinkedQueue<>(al), new ConcurrentLinkedDeque<>(al), + + // Blocking Queues + abq, new LinkedBlockingQueue<>(al), new LinkedBlockingDeque<>(al), new LinkedTransferQueue<>(al), - new PriorityBlockingQueue<>(al)) + new PriorityBlockingQueue<>(al), + + List.of(al.toArray(new Integer[0]))), + + // avoid UnsupportedOperationException in jdk9 and jdk10 + (goodClassName(immutableSubList).equals("RandomAccessSubList")) + ? Stream.empty() + : Stream.of(immutableSubList)); + + ArrayList jobs = collections .flatMap(x -> jobs(x)) .filter(job -> nameFilter == null || nameFilter.matcher(job.name()).find()) @@ -329,16 +355,29 @@ return Stream.of(streams).flatMap(s -> s); } + boolean isMutable(Collection x) { + return !(x.getClass().getName().contains("ImmutableCollections$")); + } + Stream jobs(Collection x) { + final String klazz = goodClassName(x); return concatStreams( collectionJobs(x), + (isMutable(x)) + ? mutableCollectionJobs(x) + : Stream.empty(), + (x instanceof Deque) ? dequeJobs((Deque)x) : Stream.empty(), (x instanceof List) ? listJobs((List)x) + : Stream.empty(), + + (x instanceof List && isMutable(x)) + ? mutableListJobs((List)x) : Stream.empty()); } @@ -350,7 +389,7 @@ } Stream collectionJobs(Collection x) { - final String klazz = goodClassName(x.getClass()); + final String klazz = goodClassName(x); return Stream.of( new Job(klazz + " iterate for loop") { public void work() throws Throwable { @@ -381,14 +420,6 @@ sum[0] = 0; x.spliterator().forEachRemaining(n -> sum[0] += n); check.sum(sum[0]);}}}, - new Job(klazz + " removeIf") { - public void work() throws Throwable { - int[] sum = new int[1]; - for (int i = 0; i < iterations; i++) { - sum[0] = 0; - if (x.removeIf(n -> { sum[0] += n; return false; })) - throw new AssertionError(); - check.sum(sum[0]);}}}, new Job(klazz + " contains") { public void work() throws Throwable { int[] sum = new int[1]; @@ -407,14 +438,6 @@ if (x.containsAll(sneakyAdderCollection)) throw new AssertionError(); check.sum(sum[0]);}}}, - new Job(klazz + " remove(Object)") { - public void work() throws Throwable { - int[] sum = new int[1]; - Object sneakyAdder = sneakyAdder(sum); - for (int i = 0; i < iterations; i++) { - sum[0] = 0; - if (x.remove(sneakyAdder)) throw new AssertionError(); - check.sum(sum[0]);}}}, new Job(klazz + " forEach") { public void work() throws Throwable { int[] sum = new int[1]; @@ -498,8 +521,29 @@ check.sum(sum[0]);}}}); } + Stream mutableCollectionJobs(Collection x) { + final String klazz = goodClassName(x); + return Stream.of( + new Job(klazz + " removeIf") { + public void work() throws Throwable { + int[] sum = new int[1]; + for (int i = 0; i < iterations; i++) { + sum[0] = 0; + if (x.removeIf(n -> { sum[0] += n; return false; })) + throw new AssertionError(); + check.sum(sum[0]);}}}, + new Job(klazz + " remove(Object)") { + public void work() throws Throwable { + int[] sum = new int[1]; + Object sneakyAdder = sneakyAdder(sum); + for (int i = 0; i < iterations; i++) { + sum[0] = 0; + if (x.remove(sneakyAdder)) throw new AssertionError(); + check.sum(sum[0]);}}}); + } + Stream dequeJobs(Deque x) { - String klazz = goodClassName(x.getClass()); + final String klazz = goodClassName(x); return Stream.of( new Job(klazz + " descendingIterator() loop") { public void work() throws Throwable { @@ -519,7 +563,7 @@ } Stream listJobs(List x) { - final String klazz = goodClassName(x.getClass()); + final String klazz = goodClassName(x); return Stream.of( new Job(klazz + " listIterator forward loop") { public void work() throws Throwable { @@ -555,15 +599,6 @@ if (x.lastIndexOf(sneakyAdder) != -1) throw new AssertionError(); check.sum(sum[0]);}}}, - new Job(klazz + " replaceAll") { - public void work() throws Throwable { - int[] sum = new int[1]; - UnaryOperator sneakyAdder = - x -> { sum[0] += x; return x; }; - for (int i = 0; i < iterations; i++) { - sum[0] = 0; - x.replaceAll(sneakyAdder); - check.sum(sum[0]);}}}, new Job(klazz + " equals") { public void work() throws Throwable { ArrayList copy = new ArrayList<>(x); @@ -577,4 +612,18 @@ if (x.hashCode() != hashCode) throw new AssertionError();}}}); } + + Stream mutableListJobs(List x) { + final String klazz = goodClassName(x); + return Stream.of( + new Job(klazz + " replaceAll") { + public void work() throws Throwable { + int[] sum = new int[1]; + UnaryOperator sneakyAdder = + x -> { sum[0] += x; return x; }; + for (int i = 0; i < iterations; i++) { + sum[0] = 0; + x.replaceAll(sneakyAdder); + check.sum(sum[0]);}}}); + } } diff --git a/test/jdk/java/util/Collection/RemoveMicroBenchmark.java b/test/jdk/java/util/Collection/RemoveMicroBenchmark.java --- a/test/jdk/java/util/Collection/RemoveMicroBenchmark.java +++ b/test/jdk/java/util/Collection/RemoveMicroBenchmark.java @@ -270,6 +270,10 @@ }); } + String goodClassName(Object x) { + return goodClassName(x.getClass()); + } + static List makeSubList(List list) { final ThreadLocalRandom rnd = ThreadLocalRandom.current(); int size = rnd.nextInt(4); @@ -369,7 +373,7 @@ } Stream collectionJobs(Collection x) { - final String klazz = goodClassName(x.getClass()); + final String klazz = goodClassName(x); return Stream.of( new Job(klazz + " removeIf") { public void work() throws Throwable { @@ -422,7 +426,7 @@ } Stream iteratorRemoveJobs(Collection x) { - final String klazz = goodClassName(x.getClass()); + final String klazz = goodClassName(x); return Stream.of( new Job(klazz + " Iterator.remove") { public void work() throws Throwable { @@ -460,7 +464,7 @@ } Stream queueJobs(Queue x) { - final String klazz = goodClassName(x.getClass()); + final String klazz = goodClassName(x); return Stream.of( new Job(klazz + " poll()") { public void work() throws Throwable { @@ -474,7 +478,7 @@ } Stream dequeJobs(Deque x) { - final String klazz = goodClassName(x.getClass()); + final String klazz = goodClassName(x); return Stream.of( new Job(klazz + " descendingIterator().remove") { public void work() throws Throwable { @@ -509,7 +513,7 @@ } Stream blockingQueueJobs(BlockingQueue x) { - final String klazz = goodClassName(x.getClass()); + final String klazz = goodClassName(x); return Stream.of( new Job(klazz + " timed poll()") { public void work() throws Throwable { @@ -545,7 +549,7 @@ } Stream blockingDequeJobs(BlockingDeque x) { - final String klazz = goodClassName(x.getClass()); + final String klazz = goodClassName(x); return Stream.of( new Job(klazz + " timed pollFirst()") { public void work() throws Throwable { diff --git a/test/jdk/java/util/HashMap/WhiteBoxResizeTest.java b/test/jdk/java/util/HashMap/WhiteBoxResizeTest.java new file mode 100644 --- /dev/null +++ b/test/jdk/java/util/HashMap/WhiteBoxResizeTest.java @@ -0,0 +1,132 @@ +/* + * Copyright (c) 2018, Red Hat, Inc. All rights reserved. + * + * 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. + */ + +import org.testng.annotations.Test; + +import java.lang.invoke.MethodHandle; +import java.lang.invoke.MethodHandles; +import java.lang.invoke.MethodType; +import java.lang.invoke.VarHandle; +import java.util.HashMap; +import java.util.LinkedHashMap; +import java.util.List; +import java.util.Map; +import java.util.concurrent.ThreadLocalRandom; +import java.util.function.Supplier; +import java.util.stream.IntStream; + +import static java.util.stream.Collectors.toMap; +import static org.testng.Assert.assertEquals; +import static org.testng.Assert.assertNull; + +/* + * @test + * @bug 8210280 + * @modules java.base/java.util:open + * @summary White box tests for HashMap internals around table resize + * @run testng WhiteBoxResizeTest + * @key randomness + */ +public class WhiteBoxResizeTest { + final ThreadLocalRandom rnd = ThreadLocalRandom.current(); + final MethodHandle TABLE_SIZE_FOR; + final VarHandle THRESHOLD; + final VarHandle TABLE; + + public WhiteBoxResizeTest() throws ReflectiveOperationException { + Class mClass = HashMap.class; + String nodeClassName = mClass.getName() + "$Node"; + Class nodeArrayClass = Class.forName("[L" + nodeClassName + ";"); + MethodHandles.Lookup lookup = MethodHandles.privateLookupIn(mClass, MethodHandles.lookup()); + TABLE = lookup.findVarHandle(mClass, "table", nodeArrayClass); + this.TABLE_SIZE_FOR = lookup.findStatic( + mClass, "tableSizeFor", + MethodType.methodType(int.class, int.class)); + this.THRESHOLD = lookup.findVarHandle(mClass, "threshold", int.class); + } + + int tableSizeFor(int n) { + try { + return (int) TABLE_SIZE_FOR.invoke(n); + } catch (Throwable t) { throw new AssertionError(t); } + } + + Object[] table(HashMap map) { + try { + return (Object[]) TABLE.get(map); + } catch (Throwable t) { throw new AssertionError(t); } + } + + int capacity(HashMap map) { + return table(map).length; + } + + @Test + public void testTableSizeFor() { + assertEquals(tableSizeFor(0), 1); + assertEquals(tableSizeFor(1), 1); + assertEquals(tableSizeFor(2), 2); + assertEquals(tableSizeFor(3), 4); + assertEquals(tableSizeFor(15), 16); + assertEquals(tableSizeFor(16), 16); + assertEquals(tableSizeFor(17), 32); + int maxSize = 1 << 30; + assertEquals(tableSizeFor(maxSize - 1), maxSize); + assertEquals(tableSizeFor(maxSize), maxSize); + assertEquals(tableSizeFor(maxSize + 1), maxSize); + assertEquals(tableSizeFor(Integer.MAX_VALUE), maxSize); + } + + @Test + public void capacityTestDefaultConstructor() { + capacityTestDefaultConstructor(new HashMap<>()); + capacityTestDefaultConstructor(new LinkedHashMap<>()); + } + + void capacityTestDefaultConstructor(HashMap map) { + assertNull(table(map)); + + map.put(1, 1); + assertEquals(capacity(map), 16); // default initial capacity + + map.putAll(IntStream.range(0, 64).boxed().collect(toMap(i -> i, i -> i))); + assertEquals(capacity(map), 128); + } + + @Test + public void capacityTestInitialCapacity() { + int initialCapacity = rnd.nextInt(2, 128); + List>> suppliers = List.of( + () -> new HashMap<>(initialCapacity), + () -> new HashMap<>(initialCapacity, 0.75f), + () -> new LinkedHashMap<>(initialCapacity), + () -> new LinkedHashMap<>(initialCapacity, 0.75f)); + + for (Supplier> supplier : suppliers) { + HashMap map = supplier.get(); + assertNull(table(map)); + + map.put(1, 1); + assertEquals(capacity(map), tableSizeFor(initialCapacity)); + } + } +} diff --git a/test/jdk/java/util/concurrent/CountDownLatch/Basic.java b/test/jdk/java/util/concurrent/CountDownLatch/Basic.java --- a/test/jdk/java/util/concurrent/CountDownLatch/Basic.java +++ b/test/jdk/java/util/concurrent/CountDownLatch/Basic.java @@ -25,24 +25,27 @@ * @test * @bug 6332435 * @summary Basic tests for CountDownLatch + * @library /test/lib * @author Seetharam Avadhanam, Martin Buchholz */ import java.util.concurrent.CountDownLatch; import java.util.concurrent.TimeUnit; import java.util.concurrent.atomic.AtomicInteger; - -interface AwaiterFactory { - Awaiter getAwaiter(); -} - -abstract class Awaiter extends Thread { - private volatile Throwable result = null; - protected void result(Throwable result) { this.result = result; } - public Throwable result() { return this.result; } -} +import jdk.test.lib.Utils; public class Basic { + static final long LONG_DELAY_MS = Utils.adjustTimeout(10_000); + + interface AwaiterFactory { + Awaiter getAwaiter(); + } + + abstract static class Awaiter extends Thread { + private volatile Throwable result = null; + protected void result(Throwable result) { this.result = result; } + public Throwable result() { return this.result; } + } private void toTheStartingGate(CountDownLatch gate) { try { @@ -78,15 +81,12 @@ catch (Throwable result) { result(result); }}}; } - private AwaiterFactory awaiterFactories(final CountDownLatch latch, - final CountDownLatch gate, - final int i) { - if (i == 1) - return new AwaiterFactory() { public Awaiter getAwaiter() { - return awaiter(latch, gate); }}; + AwaiterFactory awaiterFactory(CountDownLatch latch, CountDownLatch gate) { + return () -> awaiter(latch, gate); + } - return new AwaiterFactory() { public Awaiter getAwaiter() { - return awaiter(latch, gate, 10000); }}; + AwaiterFactory timedAwaiterFactory(CountDownLatch latch, CountDownLatch gate) { + return () -> awaiter(latch, gate, LONG_DELAY_MS); } //---------------------------------------------------------------- @@ -100,8 +100,8 @@ for (int i = 0; i < 3; i++) { CountDownLatch gate = new CountDownLatch(4); - AwaiterFactory factory1 = test.awaiterFactories(latch, gate, 1); - AwaiterFactory factory2 = test.awaiterFactories(latch, gate, 0); + AwaiterFactory factory1 = test.awaiterFactory(latch, gate); + AwaiterFactory factory2 = test.timedAwaiterFactory(latch, gate); a[count] = factory1.getAwaiter(); a[count++].start(); a[count] = factory1.getAwaiter(); a[count++].start(); a[count] = factory2.getAwaiter(); a[count++].start(); @@ -129,8 +129,8 @@ for (int i = 0; i < 3; i++) { CountDownLatch gate = new CountDownLatch(4); - AwaiterFactory factory1 = test.awaiterFactories(latch, gate, 1); - AwaiterFactory factory2 = test.awaiterFactories(latch, gate, 0); + AwaiterFactory factory1 = test.awaiterFactory(latch, gate); + AwaiterFactory factory2 = test.timedAwaiterFactory(latch, gate); a[count] = factory1.getAwaiter(); a[count++].start(); a[count] = factory1.getAwaiter(); a[count++].start(); a[count] = factory2.getAwaiter(); a[count++].start(); @@ -162,8 +162,8 @@ for (int i = 0; i < 3; i++) { CountDownLatch gate = new CountDownLatch(4); - AwaiterFactory factory1 = test.awaiterFactories(latch, gate, 1); - AwaiterFactory factory2 = test.awaiterFactories(latch, gate, 0); + AwaiterFactory factory1 = test.awaiterFactory(latch, gate); + AwaiterFactory factory2 = test.timedAwaiterFactory(latch, gate); a[count] = test.awaiter(latch, gate, timeout[i]); a[count++].start(); a[count] = factory1.getAwaiter(); a[count++].start(); a[count] = factory2.getAwaiter(); a[count++].start(); 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 @@ } catch (java.io.NotSerializableException acceptable) {} } - public void DISABLED_testReplaceAllIsNotStructuralModification() { + public void testReplaceAllIsNotStructuralModification() { Collection c = impl.emptyCollection(); if (!(c instanceof List)) return; diff --git a/test/jdk/java/util/concurrent/tck/CyclicBarrierTest.java b/test/jdk/java/util/concurrent/tck/CyclicBarrierTest.java --- a/test/jdk/java/util/concurrent/tck/CyclicBarrierTest.java +++ b/test/jdk/java/util/concurrent/tck/CyclicBarrierTest.java @@ -38,6 +38,9 @@ import java.util.concurrent.BrokenBarrierException; import java.util.concurrent.CountDownLatch; import java.util.concurrent.CyclicBarrier; +import java.util.concurrent.ExecutorService; +import java.util.concurrent.Executors; +import java.util.concurrent.ThreadLocalRandom; import java.util.concurrent.TimeoutException; import java.util.concurrent.atomic.AtomicBoolean; import java.util.concurrent.atomic.AtomicInteger; @@ -486,4 +489,34 @@ assertEquals(0, barrier.getNumberWaiting()); } } + + /** + * There can be more threads calling await() than parties, as long as each + * task only calls await once and the task count is a multiple of parties. + */ + public void testMoreTasksThanParties() throws Exception { + final ThreadLocalRandom rnd = ThreadLocalRandom.current(); + final int parties = rnd.nextInt(1, 5); + final int nTasks = rnd.nextInt(1, 5) * parties; + final AtomicInteger tripCount = new AtomicInteger(0); + final AtomicInteger awaitCount = new AtomicInteger(0); + final CyclicBarrier barrier = + new CyclicBarrier(parties, () -> tripCount.getAndIncrement()); + final ExecutorService e = Executors.newFixedThreadPool(nTasks); + final Runnable awaiter = () -> { + try { + if (ThreadLocalRandom.current().nextBoolean()) + barrier.await(); + else + barrier.await(LONG_DELAY_MS, MILLISECONDS); + awaitCount.getAndIncrement(); + } catch (Throwable fail) { threadUnexpectedException(fail); }}; + try (PoolCleaner cleaner = cleaner(e)) { + for (int i = nTasks; i--> 0; ) + e.execute(awaiter); + } + assertEquals(nTasks / parties, tripCount.get()); + assertEquals(nTasks, awaitCount.get()); + assertEquals(0, barrier.getNumberWaiting()); + } } diff --git a/test/jdk/java/util/concurrent/tck/ForkJoinPool9Test.java b/test/jdk/java/util/concurrent/tck/ForkJoinPool9Test.java --- a/test/jdk/java/util/concurrent/tck/ForkJoinPool9Test.java +++ b/test/jdk/java/util/concurrent/tck/ForkJoinPool9Test.java @@ -68,6 +68,10 @@ ClassLoader systemClassLoader = ClassLoader.getSystemClassLoader(); boolean haveSecurityManager = (System.getSecurityManager() != null); CountDownLatch taskStarted = new CountDownLatch(1); + ClassLoader classLoaderDistinctFromSystemClassLoader + = ClassLoader.getPlatformClassLoader(); + assertNotSame(classLoaderDistinctFromSystemClassLoader, + systemClassLoader); Runnable runInCommonPool = () -> { taskStarted.countDown(); assertTrue(ForkJoinTask.inForkJoinPool()); @@ -81,7 +85,8 @@ assertThrows( SecurityException.class, () -> System.getProperty("foo"), - () -> Thread.currentThread().setContextClassLoader(null)); + () -> Thread.currentThread().setContextClassLoader( + classLoaderDistinctFromSystemClassLoader)); // TODO ? // if (haveSecurityManager // && Thread.currentThread().getClass().getSimpleName() diff --git a/test/jdk/java/util/concurrent/tck/JSR166TestCase.java b/test/jdk/java/util/concurrent/tck/JSR166TestCase.java --- a/test/jdk/java/util/concurrent/tck/JSR166TestCase.java +++ b/test/jdk/java/util/concurrent/tck/JSR166TestCase.java @@ -487,6 +487,12 @@ public static boolean atLeastJava9() { return JAVA_CLASS_VERSION >= 53.0; } public static boolean atLeastJava10() { return JAVA_CLASS_VERSION >= 54.0; } public static boolean atLeastJava11() { return JAVA_CLASS_VERSION >= 55.0; } + public static boolean atLeastJava12() { return JAVA_CLASS_VERSION >= 56.0; } + public static boolean atLeastJava13() { return JAVA_CLASS_VERSION >= 57.0; } + public static boolean atLeastJava14() { return JAVA_CLASS_VERSION >= 58.0; } + public static boolean atLeastJava15() { return JAVA_CLASS_VERSION >= 59.0; } + public static boolean atLeastJava16() { return JAVA_CLASS_VERSION >= 60.0; } + public static boolean atLeastJava17() { return JAVA_CLASS_VERSION >= 61.0; } /** * Collects all JSR166 unit tests as one suite. @@ -577,6 +583,7 @@ "HashMapTest", "LinkedBlockingDeque8Test", "LinkedBlockingQueue8Test", + "LinkedHashMapTest", "LongAccumulatorTest", "LongAdderTest", "SplittableRandomTest", diff --git a/test/jdk/java/util/concurrent/tck/LinkedHashMapTest.java b/test/jdk/java/util/concurrent/tck/LinkedHashMapTest.java new file mode 100644 --- /dev/null +++ b/test/jdk/java/util/concurrent/tck/LinkedHashMapTest.java @@ -0,0 +1,60 @@ +/* + * 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 Doug Lea and 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/ + */ + +import java.util.LinkedHashMap; +import java.util.Map; + +import junit.framework.Test; + +public class LinkedHashMapTest extends JSR166TestCase { + public static void main(String[] args) { + main(suite(), args); + } + + public static Test suite() { + class Implementation implements MapImplementation { + public Class klazz() { return LinkedHashMap.class; } + public Map emptyMap() { return new LinkedHashMap(); } + public Object makeKey(int i) { return i; } + public Object makeValue(int i) { return i; } + public boolean isConcurrent() { return false; } + public boolean permitsNullKeys() { return true; } + public boolean permitsNullValues() { return true; } + public boolean supportsSetValue() { return true; } + } + return newTestSuite( + // LinkedHashMapTest.class, + MapTest.testSuite(new Implementation())); + } +} diff --git a/test/jdk/java/util/concurrent/tck/MapTest.java b/test/jdk/java/util/concurrent/tck/MapTest.java --- a/test/jdk/java/util/concurrent/tck/MapTest.java +++ b/test/jdk/java/util/concurrent/tck/MapTest.java @@ -166,6 +166,40 @@ assertEquals(1, m.size()); } + /** + * "Missing" test found while investigating JDK-8210280. + * ant -Djsr166.tckTestClass=HashMapTest -Djsr166.methodFilter=testBug8210280 -Djsr166.runsPerTest=1000000 tck + */ + public void testBug8210280() { + final ThreadLocalRandom rnd = ThreadLocalRandom.current(); + final int size1 = rnd.nextInt(32); + final int size2 = rnd.nextInt(128); + + final Map m1 = impl.emptyMap(); + for (int i = 0; i < size1; i++) { + int elt = rnd.nextInt(1024 * i, 1024 * (i + 1)); + assertNull(m1.put(impl.makeKey(elt), impl.makeValue(elt))); + } + + final Map m2 = impl.emptyMap(); + for (int i = 0; i < size2; i++) { + int elt = rnd.nextInt(Integer.MIN_VALUE + 1024 * i, + Integer.MIN_VALUE + 1024 * (i + 1)); + assertNull(m2.put(impl.makeKey(elt), impl.makeValue(-elt))); + } + + final Map m1Copy = impl.emptyMap(); + m1Copy.putAll(m1); + + m1.putAll(m2); + + for (Object elt : m2.keySet()) + assertEquals(m2.get(elt), m1.get(elt)); + for (Object elt : m1Copy.keySet()) + assertSame(m1Copy.get(elt), m1.get(elt)); + assertEquals(size1 + size2, m1.size()); + } + // public void testFailsIntentionallyForDebugging() { // fail(impl.klazz().getSimpleName()); // } diff --git a/test/micro/org/openjdk/bench/java/util/HashMapBench.java b/test/micro/org/openjdk/bench/java/util/HashMapBench.java new file mode 100644 --- /dev/null +++ b/test/micro/org/openjdk/bench/java/util/HashMapBench.java @@ -0,0 +1,103 @@ +/* + * Copyright (c) 2018, Red Hat, Inc. All rights reserved. + * + * 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. + */ + +package org.openjdk.bench.java.util; + +import org.openjdk.jmh.annotations.Benchmark; +import org.openjdk.jmh.annotations.BenchmarkMode; +import org.openjdk.jmh.annotations.Mode; +import org.openjdk.jmh.annotations.OutputTimeUnit; +import org.openjdk.jmh.annotations.Param; +import org.openjdk.jmh.annotations.Scope; +import org.openjdk.jmh.annotations.Setup; +import org.openjdk.jmh.annotations.State; + +import java.util.HashMap; +import java.util.LinkedHashMap; +import java.util.Map; +import java.util.concurrent.ThreadLocalRandom; +import java.util.concurrent.TimeUnit; +import java.util.function.Supplier; +import java.util.stream.IntStream; + +import static java.util.stream.Collectors.toMap; + +@BenchmarkMode(Mode.AverageTime) +@OutputTimeUnit(TimeUnit.MILLISECONDS) +@State(Scope.Thread) +public class HashMapBench { + private Supplier> mapSupplier; + private Map bigMapToAdd; + + @Param("1000000") + private int size; + + @Param + private MapType mapType; + + public enum MapType { + HASH_MAP, + LINKED_HASH_MAP, + } + + @Setup + public void setup() { + switch (mapType) { + case HASH_MAP: + mapSupplier = () -> new HashMap<>(); + break; + case LINKED_HASH_MAP: + mapSupplier = () -> new LinkedHashMap<>(); + break; + default: + throw new AssertionError(); + } + + ThreadLocalRandom rnd = ThreadLocalRandom.current(); + this.bigMapToAdd = IntStream.range(0, size).boxed() + .collect(toMap(i -> 7 + i * 128, i -> rnd.nextInt())); + } + + @Benchmark + public int putAllWithBigMapToNonEmptyMap() { + Map map = mapSupplier.get(); + map.put(-1, -1); + map.putAll(bigMapToAdd); + return map.size(); + } + + @Benchmark + public int putAllWithBigMapToEmptyMap() { + Map map = mapSupplier.get(); + map.putAll(bigMapToAdd); + return map.size(); + } + + @Benchmark + public int put() { + Map map = mapSupplier.get(); + for (int k : bigMapToAdd.keySet()) { + map.put(k, bigMapToAdd.get(k)); + } + return map.size(); + } +}