OpenJDK / amber / amber
changeset 44039:058585425bb7
8173909: Miscellaneous changes imported from jsr166 CVS 2017-03
Reviewed-by: martin, psandoz
| author | dl |
|---|---|
| date | Fri, 03 Mar 2017 10:45:38 -0800 |
| parents | eb5d68f18d4d |
| children | 3dc7457351f8 |
| files | jdk/src/java.base/share/classes/java/util/SplittableRandom.java jdk/src/java.base/share/classes/java/util/concurrent/ArrayBlockingQueue.java jdk/src/java.base/share/classes/java/util/concurrent/ThreadLocalRandom.java jdk/src/java.base/share/classes/java/util/concurrent/locks/ReentrantReadWriteLock.java jdk/test/java/util/concurrent/ArrayBlockingQueue/IteratorConsistency.java jdk/test/java/util/concurrent/ArrayBlockingQueue/WhiteBox.java jdk/test/java/util/concurrent/tck/JSR166TestCase.java jdk/test/java/util/concurrent/tck/LinkedTransferQueueTest.java jdk/test/java/util/concurrent/tck/PhaserTest.java jdk/test/java/util/concurrent/tck/StampedLockTest.java |
| diffstat | 10 files changed, 858 insertions(+), 808 deletions(-) [+] |
line wrap: on
line diff
--- a/jdk/src/java.base/share/classes/java/util/SplittableRandom.java Fri Mar 03 10:45:38 2017 -0800 +++ b/jdk/src/java.base/share/classes/java/util/SplittableRandom.java Fri Mar 03 10:45:38 2017 -0800 @@ -779,8 +779,7 @@ * @return a stream of pseudorandom {@code double} values, * each with the given origin (inclusive) and bound (exclusive) * @throws IllegalArgumentException if {@code streamSize} is - * less than zero - * @throws IllegalArgumentException if {@code randomNumberOrigin} + * less than zero, or {@code randomNumberOrigin} * is greater than or equal to {@code randomNumberBound} */ public DoubleStream doubles(long streamSize, double randomNumberOrigin,
--- a/jdk/src/java.base/share/classes/java/util/concurrent/ArrayBlockingQueue.java Fri Mar 03 10:45:38 2017 -0800 +++ b/jdk/src/java.base/share/classes/java/util/concurrent/ArrayBlockingQueue.java Fri Mar 03 10:45:38 2017 -0800 @@ -1226,6 +1226,7 @@ } else { nextIndex = NONE; nextItem = null; + if (lastRet == REMOVED) detach(); } } finally { lock.unlock();
--- a/jdk/src/java.base/share/classes/java/util/concurrent/ThreadLocalRandom.java Fri Mar 03 10:45:38 2017 -0800 +++ b/jdk/src/java.base/share/classes/java/util/concurrent/ThreadLocalRandom.java Fri Mar 03 10:45:38 2017 -0800 @@ -699,8 +699,7 @@ * @return a stream of pseudorandom {@code double} values, * each with the given origin (inclusive) and bound (exclusive) * @throws IllegalArgumentException if {@code streamSize} is - * less than zero - * @throws IllegalArgumentException if {@code randomNumberOrigin} + * less than zero, or {@code randomNumberOrigin} * is greater than or equal to {@code randomNumberBound} * @since 1.8 */
--- a/jdk/src/java.base/share/classes/java/util/concurrent/locks/ReentrantReadWriteLock.java Fri Mar 03 10:45:38 2017 -0800 +++ b/jdk/src/java.base/share/classes/java/util/concurrent/locks/ReentrantReadWriteLock.java Fri Mar 03 10:45:38 2017 -0800 @@ -53,16 +53,14 @@ * * <dl> * <dt><b><i>Non-fair mode (default)</i></b> - * <dd style="font-family:'DejaVu Sans', Arial, Helvetica, sans-serif"> - * When constructed as non-fair (the default), the order of entry + * <dd>When constructed as non-fair (the default), the order of entry * to the read and write lock is unspecified, subject to reentrancy * constraints. A nonfair lock that is continuously contended may * indefinitely postpone one or more reader or writer threads, but * will normally have higher throughput than a fair lock. * * <dt><b><i>Fair mode</i></b> - * <dd style="font-family:'DejaVu Sans', Arial, Helvetica, sans-serif"> - * When constructed as fair, threads contend for entry using an + * <dd>When constructed as fair, threads contend for entry using an * approximately arrival-order policy. When the currently held lock * is released, either the longest-waiting single writer thread will * be assigned the write lock, or if there is a group of reader threads
--- a/jdk/test/java/util/concurrent/ArrayBlockingQueue/IteratorConsistency.java Fri Mar 03 10:45:38 2017 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,755 +0,0 @@ -/* - * 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/ - */ - -import java.lang.ref.WeakReference; -import java.lang.reflect.Field; -import java.util.ArrayList; -import java.util.Arrays; -import java.util.ArrayDeque; -import java.util.Collection; -import java.util.Collections; -import java.util.Iterator; -import java.util.List; -import java.util.NoSuchElementException; -import java.util.Queue; -import java.util.concurrent.ArrayBlockingQueue; -import java.util.concurrent.CountDownLatch; -import java.util.concurrent.ThreadLocalRandom; - -/* - * @test - * @bug 7014263 - * @modules java.base/java.util.concurrent:open - * @summary White box testing of ArrayBlockingQueue iterators. - */ - -/** - * Tightly coupled to the implementation of ArrayBlockingQueue. - * Uses reflection to inspect queue and iterator state. - */ -@SuppressWarnings({"unchecked", "rawtypes"}) -public class IteratorConsistency { - final ThreadLocalRandom rnd = ThreadLocalRandom.current(); - final int CAPACITY = 20; - Field itrsField; - Field itemsField; - Field takeIndexField; - Field headField; - Field nextField; - Field prevTakeIndexField; - - void test(String[] args) throws Throwable { - itrsField = ArrayBlockingQueue.class.getDeclaredField("itrs"); - itemsField = ArrayBlockingQueue.class.getDeclaredField("items"); - takeIndexField = ArrayBlockingQueue.class.getDeclaredField("takeIndex"); - headField = Class.forName("java.util.concurrent.ArrayBlockingQueue$Itrs").getDeclaredField("head"); - nextField = Class.forName("java.util.concurrent.ArrayBlockingQueue$Itrs$Node").getDeclaredField("next"); - prevTakeIndexField = Class.forName("java.util.concurrent.ArrayBlockingQueue$Itr").getDeclaredField("prevTakeIndex"); - itrsField.setAccessible(true); - itemsField.setAccessible(true); - takeIndexField.setAccessible(true); - headField.setAccessible(true); - nextField.setAccessible(true); - prevTakeIndexField.setAccessible(true); - test(CAPACITY, true); - test(CAPACITY, false); - } - - Object itrs(ArrayBlockingQueue q) { - try { return itrsField.get(q); } - catch (Throwable ex) { throw new AssertionError(ex); } - } - - int takeIndex(ArrayBlockingQueue q) { - try { return takeIndexField.getInt(q); } - catch (Throwable ex) { throw new AssertionError(ex); } - } - - List<Iterator> trackedIterators(Object itrs) { - try { - List<Iterator> its = new ArrayList<>(); - if (itrs != null) - for (Object p = headField.get(itrs); p != null; p = nextField.get(p)) - its.add(((WeakReference<Iterator>)(p)).get()); - Collections.reverse(its); - return its; - } catch (Throwable ex) { throw new AssertionError(ex); } - } - - List<Iterator> trackedIterators(ArrayBlockingQueue q) { - return trackedIterators(itrs(q)); - } - - List<Iterator> attachedIterators(Object itrs) { - try { - List<Iterator> its = new ArrayList<>(); - if (itrs != null) - for (Object p = headField.get(itrs); p != null; p = nextField.get(p)) { - Iterator it = ((WeakReference<Iterator>)(p)).get(); - if (it != null && !isDetached(it)) - its.add(it); - } - Collections.reverse(its); - return its; - } catch (Throwable ex) { unexpected(ex); return null; } - } - - List<Iterator> attachedIterators(ArrayBlockingQueue q) { - return attachedIterators(itrs(q)); - } - - Object[] internalArray(ArrayBlockingQueue q) { - try { return (Object[]) itemsField.get(q); } - catch (Throwable ex) { throw new AssertionError(ex); } - } - - void printInternalArray(ArrayBlockingQueue q) { - System.err.println(Arrays.toString(internalArray(q))); - } - - void checkExhausted(Iterator it) { - if (rnd.nextBoolean()) { - check(!it.hasNext()); - check(isDetached(it)); - } - if (rnd.nextBoolean()) { - it.forEachRemaining(e -> { throw new AssertionError(); }); - checkDetached(it); - } - if (rnd.nextBoolean()) - try { it.next(); fail("should throw"); } - catch (NoSuchElementException success) {} - } - - boolean isDetached(Iterator it) { - try { - return prevTakeIndexField.getInt(it) < 0; - } catch (IllegalAccessException t) { unexpected(t); return false; } - } - - void checkDetached(Iterator it) { - check(isDetached(it)); - } - - void removeUsingIterator(ArrayBlockingQueue q, Object element) { - Iterator it = q.iterator(); - while (it.hasNext()) { - Object x = it.next(); - if (element.equals(x)) - it.remove(); - checkRemoveThrowsISE(it); - } - } - - void checkRemoveThrowsISE(Iterator it) { - if (rnd.nextBoolean()) - return; - try { it.remove(); fail("should throw"); } - catch (IllegalStateException success) {} - } - - void checkRemoveHasNoEffect(Iterator it, Collection c) { - if (rnd.nextBoolean()) - return; - int size = c.size(); - it.remove(); // no effect - equal(c.size(), size); - checkRemoveThrowsISE(it); - } - - void checkIterationSanity(Queue q) { - if (rnd.nextBoolean()) - return; - int size = q.size(); - Object[] a = q.toArray(); - Object[] b = new Object[size+2]; - Arrays.fill(b, Boolean.TRUE); - Object[] c = q.toArray(b); - equal(a.length, size); - check(b == c); - check(b[size] == null); - check(b[size+1] == Boolean.TRUE); - equal(q.toString(), Arrays.toString(a)); - Integer[] xx = null, yy = null; - if (size > 0) { - xx = new Integer[size - 1]; - Arrays.fill(xx, 42); - yy = ((Queue<Integer>)q).toArray(xx); - for (Integer zz : xx) - equal(42, zz); - } - Iterator it = q.iterator(); - for (int i = 0; i < size; i++) { - check(it.hasNext()); - Object x = it.next(); - check(x == a[i]); - check(x == b[i]); - if (xx != null) check(x == yy[i]); - } - check(!it.hasNext()); - } - - private static void waitForFinalizersToRun() { - for (int i = 0; i < 2; i++) - tryWaitForFinalizersToRun(); - } - - private static void tryWaitForFinalizersToRun() { - System.gc(); - final CountDownLatch fin = new CountDownLatch(1); - new Object() { protected void finalize() { fin.countDown(); }}; - System.gc(); - try { fin.await(); } - catch (InterruptedException ie) { throw new Error(ie); } - } - - void test(int capacity, boolean fair) { - //---------------------------------------------------------------- - // q.clear will clear out itrs. - //---------------------------------------------------------------- - try { - ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); - List<Iterator> its = new ArrayList<>(); - for (int i = 0; i < capacity; i++) - check(q.add(i)); - check(itrs(q) == null); - for (int i = 0; i < capacity; i++) { - its.add(q.iterator()); - equal(trackedIterators(q), its); - q.poll(); - q.add(capacity+i); - } - q.clear(); - check(itrs(q) == null); - int j = 0; - for (Iterator it : its) { - if (rnd.nextBoolean()) - check(it.hasNext()); - equal(it.next(), j++); - checkExhausted(it); - } - } catch (Throwable t) { unexpected(t); } - - //---------------------------------------------------------------- - // q emptying will clear out itrs. - //---------------------------------------------------------------- - try { - ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); - List<Iterator> its = new ArrayList<>(); - for (int i = 0; i < capacity; i++) - q.add(i); - check(itrs(q) == null); - for (int i = 0; i < capacity; i++) { - its.add(q.iterator()); - equal(trackedIterators(q), its); - q.poll(); - q.add(capacity+i); - } - for (int i = 0; i < capacity; i++) - q.poll(); - check(itrs(q) == null); - int j = 0; - for (Iterator it : its) { - if (rnd.nextBoolean()) - check(it.hasNext()); - equal(it.next(), j++); - checkExhausted(it); - } - } catch (Throwable t) { unexpected(t); } - - //---------------------------------------------------------------- - // Advancing 2 cycles will remove iterators. - //---------------------------------------------------------------- - try { - ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); - List<Iterator> its = new ArrayList<>(); - for (int i = 0; i < capacity; i++) - q.add(i); - check(itrs(q) == null); - for (int i = capacity; i < 3 * capacity; i++) { - its.add(q.iterator()); - equal(trackedIterators(q), its); - q.poll(); - q.add(i); - } - for (int i = 3 * capacity; i < 4 * capacity; i++) { - equal(trackedIterators(q), its.subList(capacity,2*capacity)); - q.poll(); - q.add(i); - } - check(itrs(q) == null); - int j = 0; - for (Iterator it : its) { - if (rnd.nextBoolean()) - check(it.hasNext()); - equal(it.next(), j++); - checkExhausted(it); - } - } catch (Throwable t) { unexpected(t); } - - //---------------------------------------------------------------- - // Interior removal of elements used by an iterator will cause - // it to be untracked. - //---------------------------------------------------------------- - try { - ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); - q.add(0); - for (int i = 1; i < 2 * capacity; i++) { - q.add(i); - Integer[] elts = { -1, -2, -3 }; - for (Integer elt : elts) q.add(elt); - equal(q.remove(), i - 1); - Iterator it = q.iterator(); - equal(it.next(), i); - equal(it.next(), elts[0]); - Collections.shuffle(Arrays.asList(elts)); - check(q.remove(elts[0])); - check(q.remove(elts[1])); - equal(trackedIterators(q), Collections.singletonList(it)); - check(q.remove(elts[2])); - check(itrs(q) == null); - equal(it.next(), -2); - if (rnd.nextBoolean()) checkExhausted(it); - if (rnd.nextBoolean()) checkDetached(it); - } - } catch (Throwable t) { unexpected(t); } - - //---------------------------------------------------------------- - // Check iterators on an empty q - //---------------------------------------------------------------- - try { - ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); - for (int i = 0; i < 4; i++) { - Iterator it = q.iterator(); - check(itrs(q) == null); - if (rnd.nextBoolean()) checkExhausted(it); - if (rnd.nextBoolean()) checkDetached(it); - checkRemoveThrowsISE(it); - } - } catch (Throwable t) { unexpected(t); } - - //---------------------------------------------------------------- - // Check "interior" removal of iterator's last element - //---------------------------------------------------------------- - try { - ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); - List<Iterator> its = new ArrayList<>(); - for (int i = 0; i < capacity; i++) - q.add(i); - for (int i = 0; i < capacity; i++) { - Iterator it = q.iterator(); - its.add(it); - for (int j = 0; j < i; j++) - equal(j, it.next()); - equal(attachedIterators(q), its); - } - q.remove(capacity - 1); - equal(attachedIterators(q), its); - for (int i = 1; i < capacity - 1; i++) { - q.remove(capacity - i - 1); - Iterator it = its.get(capacity - i); - checkDetached(it); - equal(attachedIterators(q), its.subList(0, capacity - i)); - if (rnd.nextBoolean()) check(it.hasNext()); - equal(it.next(), capacity - i); - checkExhausted(it); - } - equal(attachedIterators(q), its.subList(0, 2)); - q.remove(0); - check(q.isEmpty()); - check(itrs(q) == null); - Iterator it = its.get(0); - equal(it.next(), 0); - checkRemoveHasNoEffect(it, q); - checkExhausted(it); - checkDetached(it); - checkRemoveHasNoEffect(its.get(1), q); - } catch (Throwable t) { unexpected(t); } - - //---------------------------------------------------------------- - // Check "interior" removal of alternating elements, straddling 2 cycles - //---------------------------------------------------------------- - try { - ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); - List<Iterator> its = new ArrayList<>(); - // Move takeIndex to middle - for (int i = 0; i < capacity/2; i++) { - check(q.add(i)); - equal(q.poll(), i); - } - check(takeIndex(q) == capacity/2); - for (int i = 0; i < capacity; i++) - q.add(i); - for (int i = 0; i < capacity; i++) { - Iterator it = q.iterator(); - its.add(it); - for (int j = 0; j < i; j++) - equal(j, it.next()); - equal(attachedIterators(q), its); - } - // Remove all even elements, in either direction using - // q.remove(), or iterator.remove() - switch (rnd.nextInt(3)) { - case 0: - for (int i = 0; i < capacity; i+=2) { - check(q.remove(i)); - equal(attachedIterators(q), its); - } - break; - case 1: - for (int i = capacity - 2; i >= 0; i-=2) { - check(q.remove(i)); - equal(attachedIterators(q), its); - } - break; - case 2: - Iterator it = q.iterator(); - while (it.hasNext()) { - int i = (Integer) it.next(); - if ((i & 1) == 0) - it.remove(); - } - equal(attachedIterators(q), its); - break; - default: throw new AssertionError(); - } - - for (int i = 0; i < capacity; i++) { - Iterator it = its.get(i); - boolean even = ((i & 1) == 0); - if (even) { - if (rnd.nextBoolean()) check(it.hasNext()); - equal(i, it.next()); - for (int j = i+1; j < capacity; j += 2) - equal(j, it.next()); - check(!isDetached(it)); - check(!it.hasNext()); - check(isDetached(it)); - } else { /* odd */ - if (rnd.nextBoolean()) check(it.hasNext()); - checkRemoveHasNoEffect(it, q); - equal(i, it.next()); - for (int j = i+2; j < capacity; j += 2) - equal(j, it.next()); - check(!isDetached(it)); - check(!it.hasNext()); - check(isDetached(it)); - } - } - equal(trackedIterators(q), Collections.emptyList()); - check(itrs(q) == null); - } catch (Throwable t) { unexpected(t); } - - //---------------------------------------------------------------- - // Check garbage collection of discarded iterators - //---------------------------------------------------------------- - try { - ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); - List<Iterator> its = new ArrayList<>(); - for (int i = 0; i < capacity; i++) - q.add(i); - for (int i = 0; i < capacity; i++) { - its.add(q.iterator()); - equal(attachedIterators(q), its); - } - its = null; - waitForFinalizersToRun(); - List<Iterator> trackedIterators = trackedIterators(q); - equal(trackedIterators.size(), capacity); - for (Iterator x : trackedIterators) - check(x == null); - Iterator it = q.iterator(); - equal(trackedIterators(q), Collections.singletonList(it)); - } catch (Throwable t) { unexpected(t); } - - //---------------------------------------------------------------- - // Check garbage collection of discarded iterators, - // with a randomly retained subset. - //---------------------------------------------------------------- - try { - ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); - List<Iterator> its = new ArrayList<>(); - List<Iterator> retained = new ArrayList<>(); - final int size = 1 + rnd.nextInt(capacity); - for (int i = 0; i < size; i++) - q.add(i); - for (int i = 0; i < size; i++) { - Iterator it = q.iterator(); - its.add(it); - equal(attachedIterators(q), its); - } - // Leave sufficient gaps in retained - for (int i = 0; i < size; i+= 2+rnd.nextInt(3)) - retained.add(its.get(i)); - its = null; - waitForFinalizersToRun(); - List<Iterator> trackedIterators = trackedIterators(q); - equal(trackedIterators.size(), size); - for (Iterator it : trackedIterators) - check((it == null) ^ retained.contains(it)); - Iterator it = q.iterator(); // trigger another sweep - retained.add(it); - equal(trackedIterators(q), retained); - } catch (Throwable t) { unexpected(t); } - - //---------------------------------------------------------------- - // Check incremental sweeping of discarded iterators. - // Excessively white box?! - //---------------------------------------------------------------- - try { - final int SHORT_SWEEP_PROBES = 4; - final int LONG_SWEEP_PROBES = 16; - final int PROBE_HOP = LONG_SWEEP_PROBES + 6 * SHORT_SWEEP_PROBES; - final int PROBE_HOP_COUNT = 10; - // Expect around 8 sweeps per PROBE_HOP - final int SWEEPS_PER_PROBE_HOP = 8; - ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); - List<Iterator> its = new ArrayList<>(); - for (int i = 0; i < capacity; i++) - q.add(i); - for (int i = 0; i < PROBE_HOP_COUNT * PROBE_HOP; i++) { - its.add(q.iterator()); - equal(attachedIterators(q), its); - } - // make some garbage, separated by PROBE_HOP - for (int i = 0; i < its.size(); i += PROBE_HOP) - its.set(i, null); - waitForFinalizersToRun(); - int retries; - for (retries = 0; - trackedIterators(q).contains(null) && retries < 1000; - retries++) - // one round of sweeping - its.add(q.iterator()); - check(retries >= PROBE_HOP_COUNT * (SWEEPS_PER_PROBE_HOP - 2)); - check(retries <= PROBE_HOP_COUNT * (SWEEPS_PER_PROBE_HOP + 2)); - Iterator itsit = its.iterator(); - while (itsit.hasNext()) - if (itsit.next() == null) - itsit.remove(); - equal(trackedIterators(q), its); - } catch (Throwable t) { unexpected(t); } - - //---------------------------------------------------------------- - // Check safety of iterator.remove while in detached mode. - //---------------------------------------------------------------- - try { - ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); - List<Iterator> its = new ArrayList<>(); - for (int i = 0; i < capacity/2; i++) { - q.add(i); - q.remove(); - } - check(takeIndex(q) == capacity/2); - for (int i = 0; i < capacity; i++) - q.add(i); - for (int i = 0; i < capacity; i++) { - Iterator it = q.iterator(); - its.add(it); - for (int j = 0; j < i; j++) - equal(j, it.next()); - equal(attachedIterators(q), its); - } - for (int i = capacity - 1; i >= 0; i--) { - Iterator it = its.get(i); - equal(i, it.next()); // last element - check(!isDetached(it)); - check(!it.hasNext()); // first hasNext failure - check(isDetached(it)); - int size = q.size(); - check(q.contains(i)); - switch (rnd.nextInt(3)) { - case 0: - it.remove(); - check(!q.contains(i)); - equal(q.size(), size - 1); - break; - case 1: - // replace i with impostor - if (q.remainingCapacity() == 0) { - check(q.remove(i)); - check(q.add(-1)); - } else { - check(q.add(-1)); - check(q.remove(i)); - } - it.remove(); // should have no effect - equal(size, q.size()); - check(q.contains(-1)); - check(q.remove(-1)); - break; - case 2: - // replace i with true impostor - if (i != 0) { - check(q.remove(i)); - check(q.add(i)); - } - it.remove(); - check(!q.contains(i)); - equal(q.size(), size - 1); - break; - default: throw new AssertionError(); - } - checkRemoveThrowsISE(it); - check(isDetached(it)); - check(!trackedIterators(q).contains(it)); - } - check(q.isEmpty()); - check(itrs(q) == null); - for (Iterator it : its) - checkExhausted(it); - } catch (Throwable t) { unexpected(t); } - - //---------------------------------------------------------------- - // Check dequeues bypassing iterators' current positions. - //---------------------------------------------------------------- - try { - ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); - Queue<Iterator> its0 = new ArrayDeque<>(); - Queue<Iterator> itsMid = new ArrayDeque<>(); - List<Iterator> its = new ArrayList<>(); - for (int i = 0; i < capacity; i++) - q.add(i); - for (int i = 0; i < 2 * capacity + 1; i++) { - Iterator it = q.iterator(); - its.add(it); - its0.add(it); - } - for (int i = 0; i < 2 * capacity + 1; i++) { - Iterator it = q.iterator(); - for (int j = 0; j < capacity/2; j++) - equal(j, it.next()); - its.add(it); - itsMid.add(it); - } - for (int i = capacity; i < 3 * capacity; i++) { - Iterator it; - - it = its0.remove(); - checkRemoveThrowsISE(it); - if (rnd.nextBoolean()) check(it.hasNext()); - equal(0, it.next()); - int victim = i - capacity; - for (int j = victim + (victim == 0 ? 1 : 0); j < i; j++) { - if (rnd.nextBoolean()) check(it.hasNext()); - equal(j, it.next()); - } - checkExhausted(it); - - it = itsMid.remove(); - if (victim >= capacity/2) - checkRemoveHasNoEffect(it, q); - equal(capacity/2, it.next()); - if (victim > capacity/2) - checkRemoveHasNoEffect(it, q); - for (int j = Math.max(victim, capacity/2 + 1); j < i; j++) { - if (rnd.nextBoolean()) check(it.hasNext()); - equal(j, it.next()); - } - checkExhausted(it); - - if (rnd.nextBoolean()) { - equal(victim, q.remove()); - } else { - ArrayList list = new ArrayList(1); - q.drainTo(list, 1); - equal(list.size(), 1); - equal(victim, list.get(0)); - } - check(q.add(i)); - } - // takeIndex has wrapped twice. - Iterator it0 = its0.remove(); - Iterator itMid = itsMid.remove(); - check(isDetached(it0)); - check(isDetached(itMid)); - if (rnd.nextBoolean()) check(it0.hasNext()); - if (rnd.nextBoolean()) check(itMid.hasNext()); - checkRemoveThrowsISE(it0); - checkRemoveHasNoEffect(itMid, q); - if (rnd.nextBoolean()) equal(0, it0.next()); - if (rnd.nextBoolean()) equal(capacity/2, itMid.next()); - check(isDetached(it0)); - check(isDetached(itMid)); - equal(capacity, q.size()); - equal(0, q.remainingCapacity()); - } catch (Throwable t) { unexpected(t); } - - //---------------------------------------------------------------- - // Check collective sanity of iteration, toArray() and toString() - //---------------------------------------------------------------- - try { - ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); - for (int i = 0; i < capacity; i++) { - checkIterationSanity(q); - equal(capacity, q.size() + q.remainingCapacity()); - q.add(i); - } - for (int i = 0; i < (capacity + (capacity >> 1)); i++) { - checkIterationSanity(q); - equal(capacity, q.size() + q.remainingCapacity()); - equal(i, q.peek()); - equal(i, q.poll()); - checkIterationSanity(q); - equal(capacity, q.size() + q.remainingCapacity()); - q.add(capacity + i); - } - for (int i = 0; i < capacity; i++) { - checkIterationSanity(q); - equal(capacity, q.size() + q.remainingCapacity()); - int expected = i + capacity + (capacity >> 1); - equal(expected, q.peek()); - equal(expected, q.poll()); - } - checkIterationSanity(q); - } catch (Throwable t) { unexpected(t); } - - } - - //--------------------- Infrastructure --------------------------- - volatile int passed = 0, failed = 0; - void pass() {passed++;} - void fail() {failed++; Thread.dumpStack();} - void fail(String msg) {System.err.println(msg); fail();} - void unexpected(Throwable t) {failed++; t.printStackTrace();} - void check(boolean cond) {if (cond) pass(); else fail();} - void equal(Object x, Object y) { - if (x == null ? y == null : x.equals(y)) pass(); - else fail(x + " not equal to " + y);} - public static void main(String[] args) throws Throwable { - new IteratorConsistency().instanceMain(args);} - public void instanceMain(String[] args) throws Throwable { - try {test(args);} catch (Throwable t) {unexpected(t);} - System.err.printf("%nPassed = %d, failed = %d%n%n", passed, failed); - if (failed > 0) throw new AssertionError("Some tests failed");} -}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/jdk/test/java/util/concurrent/ArrayBlockingQueue/WhiteBox.java Fri Mar 03 10:45:38 2017 -0800 @@ -0,0 +1,759 @@ +/* + * 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.concurrent:open + * @run testng WhiteBox + * @summary White box tests of implementation details + */ + +import static org.testng.Assert.*; +import org.testng.annotations.DataProvider; +import org.testng.annotations.Test; + +import java.lang.ref.WeakReference; +import java.lang.invoke.MethodHandles; +import java.lang.invoke.VarHandle; +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collection; +import java.util.Collections; +import java.util.Iterator; +import java.util.List; +import java.util.NoSuchElementException; +import java.util.Queue; +import java.util.concurrent.ArrayBlockingQueue; +import java.util.concurrent.CountDownLatch; +import java.util.concurrent.ThreadLocalRandom; +import java.util.concurrent.TimeUnit; +import java.util.function.BooleanSupplier; + +@Test +public class WhiteBox { + final ThreadLocalRandom rnd = ThreadLocalRandom.current(); + final MethodHandles.Lookup lookup = MethodHandles.lookup(); + final VarHandle ITRS, ITEMS, TAKEINDEX, PUTINDEX, COUNT, HEAD, NEXT, PREVTAKEINDEX; + + WhiteBox() throws ReflectiveOperationException { + Class<?> qClass = ArrayBlockingQueue.class; + Class<?> itrClass = Class.forName(qClass.getName() + "$Itr"); + Class<?> itrsClass = Class.forName(qClass.getName() + "$Itrs"); + Class<?> nodeClass = Class.forName(itrsClass.getName() + "$Node"); + ITRS = findVarHandle(qClass, "itrs", itrsClass); + ITEMS = findVarHandle(qClass, "items", Object[].class); + TAKEINDEX = findVarHandle(qClass, "takeIndex", int.class); + PUTINDEX = findVarHandle(qClass, "putIndex", int.class); + COUNT = findVarHandle(qClass, "count", int.class); + HEAD = findVarHandle(itrsClass, "head", nodeClass); + NEXT = findVarHandle(nodeClass, "next", nodeClass); + PREVTAKEINDEX = findVarHandle(itrClass, "prevTakeIndex", int.class); + } + + VarHandle findVarHandle(Class<?> recv, String name, Class<?> type) + throws ReflectiveOperationException { + return MethodHandles.privateLookupIn(recv, lookup) + .findVarHandle(recv, name, type); + } + + Object itrs(ArrayBlockingQueue q) { return ITRS.get(q); } + Object[] items(ArrayBlockingQueue q) { return (Object[]) ITEMS.get(q); } + int takeIndex(ArrayBlockingQueue q) { return (int) TAKEINDEX.get(q); } + int putIndex(ArrayBlockingQueue q) { return (int) PUTINDEX.get(q); } + int count(ArrayBlockingQueue q) { return (int) COUNT.get(q); } + Object head(Object itrs) { return HEAD.get(itrs); } + Object next(Object node) { return NEXT.get(node); } + int prevTakeIndex(Iterator itr) { return (int) PREVTAKEINDEX.get(itr); } + + boolean isDetached(Iterator it) { + return prevTakeIndex(it) < 0; + } + + void assertIteratorExhausted(Iterator it) { + if (rnd.nextBoolean()) { + assertTrue(!it.hasNext()); + assertTrue(isDetached(it)); + } + if (rnd.nextBoolean()) { + it.forEachRemaining(e -> { throw new AssertionError(); }); + assertTrue(isDetached(it)); + } + if (rnd.nextBoolean()) + try { it.next(); fail("should throw"); } + catch (NoSuchElementException success) {} + } + + List<Iterator> trackedIterators(ArrayBlockingQueue q) { + List<Iterator> its = new ArrayList<>(); + Object itrs = itrs(q); + if (itrs != null) { + for (Object p = head(itrs); p != null; p = next(p)) + its.add(((WeakReference<Iterator>)(p)).get()); + Collections.reverse(its); + } + return its; + } + + List<Iterator> attachedIterators(ArrayBlockingQueue q) { + List<Iterator> its = new ArrayList<>(); + Object itrs = itrs(q); + if (itrs != null) { + for (Object p = head(itrs); p != null; p = next(p)) { + Iterator it = ((WeakReference<Iterator>)(p)).get(); + if (it != null && !isDetached(it)) + its.add(it); + } + Collections.reverse(its); + } + return its; + } + + void assertRemoveThrowsISE(Iterator it) { + if (rnd.nextBoolean()) + try { it.remove(); fail("should throw"); } + catch (IllegalStateException success) {} + } + + void assertRemoveHasNoEffect(Iterator it, Collection c) { + if (rnd.nextBoolean()) { + int size = c.size(); + it.remove(); // no effect + assertEquals(c.size(), size); + assertRemoveThrowsISE(it); + } + } + + void checkIterationSanity(Queue q) { + if (rnd.nextBoolean()) + return; + int size = q.size(); + Object[] a = q.toArray(); + Object[] b = new Object[size+2]; + Arrays.fill(b, Boolean.TRUE); + Object[] c = q.toArray(b); + assertEquals(a.length, size); + assertSame(b, c); + assertNull(b[size]); + assertSame(b[size+1], Boolean.TRUE); + assertEquals(q.toString(), Arrays.toString(a)); + Integer[] xx = null, yy = null; + if (size > 0) { + xx = new Integer[size - 1]; + Arrays.fill(xx, 42); + yy = ((Queue<Integer>)q).toArray(xx); + for (Integer zz : xx) + assertEquals(42, (int) zz); + } + Iterator it = q.iterator(); + for (int i = 0; i < size; i++) { + if (rnd.nextBoolean()) assertTrue(it.hasNext()); + Object x = it.next(); + assertSame(x, a[i]); + assertSame(x, b[i]); + if (xx != null) assertSame(x, yy[i]); + } + if (rnd.nextBoolean()) assertTrue(!it.hasNext()); + } + + /** + * Instead of having putIndex (and takeIndex) at the initial + * default of 0, move them to a random location. + */ + void randomizePutIndex(ArrayBlockingQueue q) { + assertTrue(q.isEmpty()); + int capacity = q.remainingCapacity(); + int n = rnd.nextInt(capacity + 1); + int putIndex = putIndex(q); + for (int i = n; i-->0; ) q.add(Boolean.TRUE); + for (int i = n; i-->0; ) q.remove(); + assertEquals(putIndex(q), (putIndex + n) % items(q).length); + } + + /** No guarantees, but effective in practice. */ + static void forceFullGc() { + CountDownLatch finalizeDone = new CountDownLatch(1); + WeakReference<?> ref = new WeakReference<Object>(new Object() { + protected void finalize() { finalizeDone.countDown(); }}); + try { + for (int i = 0; i < 10; i++) { + System.gc(); + if (finalizeDone.await(1L, TimeUnit.SECONDS) && ref.get() == null) { + System.runFinalization(); // try to pick up stragglers + return; + } + } + } catch (InterruptedException unexpected) { + throw new AssertionError("unexpected InterruptedException"); + } + throw new AssertionError("failed to do a \"full\" gc"); + } + + static void gcAwait(BooleanSupplier s) { + for (int i = 0; i < 10; i++) { + if (s.getAsBoolean()) + return; + forceFullGc(); + } + throw new AssertionError("failed to satisfy condition"); + } + + public void clear_willClearItrs() { + boolean fair = rnd.nextBoolean(); + int capacity = rnd.nextInt(2, 10); + ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); + randomizePutIndex(q); + List<Iterator> its = new ArrayList<>(); + for (int i = 0; i < capacity; i++) + assertTrue(q.add(i)); + assertNull(itrs(q)); + for (int i = 0; i < capacity; i++) { + its.add(q.iterator()); + assertEquals(trackedIterators(q), its); + q.poll(); + q.add(capacity + i); + } + q.clear(); + assertNull(itrs(q)); + int j = 0; + for (Iterator it : its) { + assertTrue(isDetached(it)); + if (rnd.nextBoolean()) assertTrue(it.hasNext()); + if (rnd.nextBoolean()) { + assertEquals(it.next(), j); + assertIteratorExhausted(it); + } + j++; + } + } + + public void queueEmptyingWillClearItrs() { + boolean fair = rnd.nextBoolean(); + int capacity = rnd.nextInt(2, 10); + ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); + randomizePutIndex(q); + List<Iterator> its = new ArrayList<>(); + for (int i = 0; i < capacity; i++) + q.add(i); + assertNull(itrs(q)); + for (int i = 0; i < capacity; i++) { + its.add(q.iterator()); + assertEquals(trackedIterators(q), its); + q.poll(); + q.add(capacity+i); + } + for (int i = 0; i < capacity; i++) + q.poll(); + assertNull(itrs(q)); + int j = 0; + for (Iterator it : its) { + assertTrue(isDetached(it)); + if (rnd.nextBoolean()) assertTrue(it.hasNext()); + if (rnd.nextBoolean()) { + assertEquals(it.next(), j); + assertIteratorExhausted(it); + } + j++; + } + } + + public void advancing2CyclesWillRemoveIterators() { + boolean fair = rnd.nextBoolean(); + int capacity = rnd.nextInt(2, 10); + ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); + List<Iterator> its = new ArrayList<>(); + for (int i = 0; i < capacity; i++) + q.add(i); + assertNull(itrs(q)); + for (int i = capacity; i < 3 * capacity; i++) { + its.add(q.iterator()); + assertEquals(trackedIterators(q), its); + q.poll(); + q.add(i); + } + for (int i = 3 * capacity; i < 4 * capacity; i++) { + assertEquals(trackedIterators(q), its.subList(capacity,2*capacity)); + q.poll(); + q.add(i); + } + assertNull(itrs(q)); + int j = 0; + for (Iterator it : its) { + assertTrue(isDetached(it)); + if (rnd.nextBoolean()) assertTrue(it.hasNext()); + if (rnd.nextBoolean()) { + assertEquals(it.next(), j); + assertIteratorExhausted(it); + } + j++; + } + } + + /** + * Interior removal of elements used by an iterator will cause it + * to be untracked. + */ + public void interiorRemovalOfElementsUsedByIterator() { + boolean fair = rnd.nextBoolean(); + int capacity = rnd.nextInt(10, 20); + ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); + randomizePutIndex(q); + q.add(0); + for (int i = 1; i < 2 * capacity; i++) { + q.add(i); + Integer[] elts = { -1, -2, -3 }; + for (Integer elt : elts) q.add(elt); + assertEquals(q.remove(), i - 1); + Iterator it = q.iterator(); + assertEquals(it.next(), i); + assertEquals(it.next(), elts[0]); + Collections.shuffle(Arrays.asList(elts)); + assertTrue(q.remove(elts[0])); + assertTrue(q.remove(elts[1])); + assertEquals(trackedIterators(q), Collections.singletonList(it)); + assertTrue(q.remove(elts[2])); + assertNull(itrs(q)); + assertEquals(it.next(), -2); + assertIteratorExhausted(it); + assertTrue(isDetached(it)); + } + } + + public void iteratorsOnEmptyQueue() { + boolean fair = rnd.nextBoolean(); + int capacity = rnd.nextInt(1, 10); + ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); + randomizePutIndex(q); + for (int i = 0; i < 4; i++) { + Iterator it = q.iterator(); + assertNull(itrs(q)); + assertIteratorExhausted(it); + assertTrue(isDetached(it)); + assertRemoveThrowsISE(it); + } + } + + public void interiorRemovalOfIteratorsLastElement() { + boolean fair = rnd.nextBoolean(); + int capacity = rnd.nextInt(3, 10); + ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); + randomizePutIndex(q); + List<Iterator> its = new ArrayList<>(); + for (int i = 0; i < capacity; i++) + q.add(i); + for (int i = 0; i < capacity; i++) { + Iterator it = q.iterator(); + its.add(it); + for (int j = 0; j < i; j++) + assertEquals(j, it.next()); + assertEquals(attachedIterators(q), its); + } + q.remove(capacity - 1); + assertEquals(attachedIterators(q), its); + for (int i = 1; i < capacity - 1; i++) { + q.remove(capacity - i - 1); + Iterator it = its.get(capacity - i); + assertTrue(isDetached(it)); + assertEquals(attachedIterators(q), its.subList(0, capacity - i)); + if (rnd.nextBoolean()) assertTrue(it.hasNext()); + assertEquals(it.next(), capacity - i); + assertIteratorExhausted(it); + } + assertEquals(attachedIterators(q), its.subList(0, 2)); + q.remove(0); + assertTrue(q.isEmpty()); + assertNull(itrs(q)); + Iterator it = its.get(0); + assertEquals(it.next(), 0); + assertRemoveHasNoEffect(it, q); + assertIteratorExhausted(it); + assertTrue(isDetached(it)); + assertRemoveHasNoEffect(its.get(1), q); + } + + /** + * Checks "interior" removal of alternating elements, straddling 2 cycles + */ + public void interiorRemovalOfAlternatingElements() { + boolean fair = rnd.nextBoolean(); + int capacity = 2 * rnd.nextInt(2, 10); + ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); + List<Iterator> its = new ArrayList<>(); + // Move takeIndex to middle + for (int i = 0; i < capacity/2; i++) { + assertTrue(q.add(i)); + assertEquals(q.poll(), i); + } + assertEquals(takeIndex(q), capacity/2); + for (int i = 0; i < capacity; i++) + q.add(i); + for (int i = 0; i < capacity; i++) { + Iterator it = q.iterator(); + its.add(it); + for (int j = 0; j < i; j++) + assertEquals(j, it.next()); + assertEquals(attachedIterators(q), its); + } + + // Remove all even elements, in either direction, using + // q.remove(), or iterator.remove() + switch (rnd.nextInt(3)) { + case 0: + for (int i = 0; i < capacity; i+=2) assertTrue(q.remove(i)); + break; + case 1: + for (int i = capacity - 2; i >= 0; i-=2) assertTrue(q.remove(i)); + break; + case 2: + Iterator it = q.iterator(); + while (it.hasNext()) { + int i = (Integer) it.next(); + if ((i & 1) == 0) + it.remove(); + } + break; + default: throw new AssertionError(); + } + assertEquals(attachedIterators(q), its); + + for (int i = 0; i < capacity; i++) { + Iterator it = its.get(i); + boolean even = ((i & 1) == 0); + if (even) { + if (rnd.nextBoolean()) assertTrue(it.hasNext()); + assertEquals(i, it.next()); + for (int j = i+1; j < capacity; j += 2) + assertEquals(j, it.next()); + assertTrue(!isDetached(it)); + assertTrue(!it.hasNext()); + assertTrue(isDetached(it)); + } else { /* odd */ + if (rnd.nextBoolean()) assertTrue(it.hasNext()); + assertRemoveHasNoEffect(it, q); + assertEquals(i, it.next()); + for (int j = i+2; j < capacity; j += 2) + assertEquals(j, it.next()); + assertTrue(!isDetached(it)); + assertTrue(!it.hasNext()); + assertTrue(isDetached(it)); + } + } + assertEquals(trackedIterators(q), Collections.emptyList()); + assertNull(itrs(q)); + } + + public void garbageCollectionOfUnreachableIterators() { + boolean fair = rnd.nextBoolean(); + int capacity = rnd.nextInt(1, 10); + ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); + randomizePutIndex(q); + List<Iterator> its = new ArrayList<>(); + for (int i = 0; i < capacity; i++) q.add(i); + for (int i = 0; i < capacity; i++) its.add(q.iterator()); + assertEquals(attachedIterators(q), its); + its = null; + gcAwait(() -> { + List<Iterator> trackedIterators = trackedIterators(q); + assertEquals(trackedIterators.size(), capacity); + for (Iterator x : trackedIterators) + if (x != null) return false; + return true; + }); + Iterator it = q.iterator(); // + assertEquals(trackedIterators(q), Collections.singletonList(it)); + } + + public void garbageCollectionOfUnreachableIteratorsWithRandomlyRetainedSubset() { + boolean fair = rnd.nextBoolean(); + int capacity = rnd.nextInt(10, 20); + ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); + randomizePutIndex(q); + List<Iterator> its = new ArrayList<>(); + List<Iterator> retained = new ArrayList<>(); + final int size = 1 + rnd.nextInt(capacity); + for (int i = 0; i < size; i++) q.add(i); + for (int i = 0; i < size; i++) its.add(q.iterator()); + assertEquals(attachedIterators(q), its); + // Leave sufficient gaps in retained + for (int i = 0; i < size; i+= 2+rnd.nextInt(3)) + retained.add(its.get(i)); + its = null; + gcAwait(() -> { + List<Iterator> trackedIterators = trackedIterators(q); + assertEquals(trackedIterators.size(), size); + for (Iterator it : trackedIterators) + if ((it != null) ^ retained.contains(it)) return false; + return true; + }); + Iterator it = q.iterator(); // trigger another sweep + retained.add(it); + assertEquals(trackedIterators(q), retained); + } + + /** + * Checks incremental sweeping of unreachable iterators. + * Excessively white box?! + */ + public void incrementalSweepingOfUnreachableIterators() { + boolean fair = rnd.nextBoolean(); + int capacity = rnd.nextInt(10, 20); + ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); + randomizePutIndex(q); + final int SHORT_SWEEP_PROBES = 4; + final int LONG_SWEEP_PROBES = 16; + final int PROBE_HOP = LONG_SWEEP_PROBES + 6 * SHORT_SWEEP_PROBES; + final int PROBE_HOP_COUNT = 10; + // Expect around 8 sweeps per PROBE_HOP + final int SWEEPS_PER_PROBE_HOP = 8; + List<Iterator> its = new ArrayList<>(); + for (int i = 0; i < capacity; i++) + q.add(i); + for (int i = 0; i < PROBE_HOP_COUNT * PROBE_HOP; i++) + its.add(q.iterator()); + assertEquals(attachedIterators(q), its); + // make some garbage, separated by PROBE_HOP + for (int i = 0; i < its.size(); i += PROBE_HOP) + its.set(i, null); + its.removeIf(it -> it == null); + forceFullGc(); + int retries; + for (retries = 0; + trackedIterators(q).contains(null) && retries < 1000; + retries++) + // one round of sweeping + its.add(q.iterator()); + assertTrue(retries >= PROBE_HOP_COUNT * (SWEEPS_PER_PROBE_HOP - 2)); + assertTrue(retries <= PROBE_HOP_COUNT * (SWEEPS_PER_PROBE_HOP + 2)); + assertEquals(trackedIterators(q), its); + } + + public void Iterator_remove_safetyWhileInDetachedMode() { + boolean fair = rnd.nextBoolean(); + int capacity = rnd.nextInt(10, 20); + ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); + List<Iterator> its = new ArrayList<>(); + for (int i = 0; i < capacity/2; i++) { + q.add(i); + q.remove(); + } + assertEquals(takeIndex(q), capacity/2); + for (int i = 0; i < capacity; i++) + q.add(i); + for (int i = 0; i < capacity; i++) { + Iterator it = q.iterator(); + its.add(it); + for (int j = 0; j < i; j++) + assertEquals(j, it.next()); + } + assertEquals(attachedIterators(q), its); + for (int i = capacity - 1; i >= 0; i--) { + Iterator it = its.get(i); + assertEquals(i, it.next()); // last element + assertTrue(!isDetached(it)); + assertTrue(!it.hasNext()); // first hasNext failure + assertTrue(isDetached(it)); + int size = q.size(); + assertTrue(q.contains(i)); + switch (rnd.nextInt(3)) { + case 0: + it.remove(); + assertTrue(!q.contains(i)); + assertEquals(q.size(), size - 1); + break; + case 1: + // replace i with impostor + if (q.remainingCapacity() == 0) { + assertTrue(q.remove(i)); + assertTrue(q.add(-1)); + } else { + assertTrue(q.add(-1)); + assertTrue(q.remove(i)); + } + it.remove(); // should have no effect + assertEquals(size, q.size()); + assertTrue(q.contains(-1)); + assertTrue(q.remove(-1)); + break; + case 2: + // replace i with true impostor + if (i != 0) { + assertTrue(q.remove(i)); + assertTrue(q.add(i)); + } + it.remove(); + assertTrue(!q.contains(i)); + assertEquals(q.size(), size - 1); + break; + default: throw new AssertionError(); + } + assertRemoveThrowsISE(it); + assertTrue(isDetached(it)); + assertTrue(!trackedIterators(q).contains(it)); + } + assertTrue(q.isEmpty()); + assertNull(itrs(q)); + for (Iterator it : its) + assertIteratorExhausted(it); + } + + /** + * Checks dequeues bypassing iterators' current positions. + */ + public void dequeuesBypassingIteratorCurrentPositions() { + boolean fair = rnd.nextBoolean(); + int capacity = rnd.nextInt(10, 20); + ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); + Queue<Iterator> its0 = new ArrayDeque<>(); + Queue<Iterator> itsMid = new ArrayDeque<>(); + List<Iterator> its = new ArrayList<>(); + for (int i = 0; i < capacity; i++) + q.add(i); + for (int i = 0; i < 2 * capacity + 1; i++) { + Iterator it = q.iterator(); + its.add(it); + its0.add(it); + } + for (int i = 0; i < 2 * capacity + 1; i++) { + Iterator it = q.iterator(); + for (int j = 0; j < capacity/2; j++) + assertEquals(j, it.next()); + its.add(it); + itsMid.add(it); + } + for (int i = capacity; i < 3 * capacity; i++) { + Iterator it; + + it = its0.remove(); + assertRemoveThrowsISE(it); + if (rnd.nextBoolean()) assertTrue(it.hasNext()); + assertEquals(0, it.next()); + int victim = i - capacity; + for (int j = victim + (victim == 0 ? 1 : 0); j < i; j++) { + if (rnd.nextBoolean()) assertTrue(it.hasNext()); + assertEquals(j, it.next()); + } + assertIteratorExhausted(it); + + it = itsMid.remove(); + if (victim >= capacity/2) + assertRemoveHasNoEffect(it, q); + assertEquals(capacity/2, it.next()); + if (victim > capacity/2) + assertRemoveHasNoEffect(it, q); + for (int j = Math.max(victim, capacity/2 + 1); j < i; j++) { + if (rnd.nextBoolean()) assertTrue(it.hasNext()); + assertEquals(j, it.next()); + } + assertIteratorExhausted(it); + + if (rnd.nextBoolean()) { + assertEquals(victim, q.remove()); + } else { + ArrayList list = new ArrayList(1); + q.drainTo(list, 1); + assertEquals(list.size(), 1); + assertEquals(victim, list.get(0)); + } + assertTrue(q.add(i)); + } + // takeIndex has wrapped twice. + Iterator it0 = its0.remove(); + Iterator itMid = itsMid.remove(); + assertTrue(isDetached(it0)); + assertTrue(isDetached(itMid)); + if (rnd.nextBoolean()) assertTrue(it0.hasNext()); + if (rnd.nextBoolean()) assertTrue(itMid.hasNext()); + assertRemoveThrowsISE(it0); + assertRemoveHasNoEffect(itMid, q); + if (rnd.nextBoolean()) assertEquals(0, it0.next()); + if (rnd.nextBoolean()) assertEquals(capacity/2, itMid.next()); + assertTrue(isDetached(it0)); + assertTrue(isDetached(itMid)); + assertEquals(capacity, q.size()); + assertEquals(0, q.remainingCapacity()); + } + + /** + * Checks collective sanity of iteration, toArray() and toString(). + */ + public void collectiveSanity() { + boolean fair = rnd.nextBoolean(); + int capacity = rnd.nextInt(10, 20); + ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); + randomizePutIndex(q); + for (int i = 0; i < capacity; i++) { + checkIterationSanity(q); + assertEquals(capacity, q.size() + q.remainingCapacity()); + q.add(i); + } + for (int i = 0; i < (capacity + (capacity >> 1)); i++) { + checkIterationSanity(q); + assertEquals(capacity, q.size() + q.remainingCapacity()); + assertEquals(i, q.peek()); + assertEquals(i, q.poll()); + checkIterationSanity(q); + assertEquals(capacity, q.size() + q.remainingCapacity()); + q.add(capacity + i); + } + for (int i = 0; i < capacity; i++) { + checkIterationSanity(q); + assertEquals(capacity, q.size() + q.remainingCapacity()); + int expected = i + capacity + (capacity >> 1); + assertEquals(expected, q.peek()); + assertEquals(expected, q.poll()); + } + checkIterationSanity(q); + } + + public void iteratorsDetachedWhenExhaustedAndLastRetRemoved() { + boolean fair = rnd.nextBoolean(); + int capacity = rnd.nextInt(2, 10); + ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); + randomizePutIndex(q); + int size = rnd.nextInt(1, capacity + 1); + for (int i = 0; i < size; i++) q.add(i); + Iterator it = q.iterator(); + for (int i = 0; i < size - 1; i++) assertEquals(i, it.next()); + assertEquals(trackedIterators(q), Collections.singletonList(it)); + assertFalse(isDetached(it)); + switch (rnd.nextInt(2)) { + case 0: assertTrue(q.remove(size - 1)); break; + case 1: assertTrue(q.removeIf(e -> e.equals(size - 1))); break; + default: throw new AssertionError(); + } + assertEquals(size - 1, it.next()); // should trigger detach + assertNull(itrs(q)); + assertTrue(isDetached(it)); + assertRemoveHasNoEffect(it, q); + } +}
--- a/jdk/test/java/util/concurrent/tck/JSR166TestCase.java Fri Mar 03 10:45:38 2017 -0800 +++ b/jdk/test/java/util/concurrent/tck/JSR166TestCase.java Fri Mar 03 10:45:38 2017 -0800 @@ -1326,21 +1326,61 @@ startTime = System.nanoTime(); else if (millisElapsedSince(startTime) > timeoutMillis) { threadAssertTrue(thread.isAlive()); - return; + fail("timed out waiting for thread to enter wait state"); } Thread.yield(); } } /** - * Waits up to LONG_DELAY_MS for the given thread to enter a wait - * state: BLOCKED, WAITING, or TIMED_WAITING. + * Spin-waits up to the specified number of milliseconds for the given + * thread to enter a wait state: BLOCKED, WAITING, or TIMED_WAITING, + * and additionally satisfy the given condition. + */ + void waitForThreadToEnterWaitState( + Thread thread, long timeoutMillis, Callable<Boolean> waitingForGodot) { + long startTime = 0L; + for (;;) { + Thread.State s = thread.getState(); + if (s == Thread.State.BLOCKED || + s == Thread.State.WAITING || + s == Thread.State.TIMED_WAITING) { + try { + if (waitingForGodot.call()) + return; + } catch (Throwable fail) { threadUnexpectedException(fail); } + } + else if (s == Thread.State.TERMINATED) + fail("Unexpected thread termination"); + else if (startTime == 0L) + startTime = System.nanoTime(); + else if (millisElapsedSince(startTime) > timeoutMillis) { + threadAssertTrue(thread.isAlive()); + fail("timed out waiting for thread to enter wait state"); + } + Thread.yield(); + } + } + + /** + * Spin-waits up to LONG_DELAY_MS milliseconds for the given thread to + * enter a wait state: BLOCKED, WAITING, or TIMED_WAITING. */ void waitForThreadToEnterWaitState(Thread thread) { waitForThreadToEnterWaitState(thread, LONG_DELAY_MS); } /** + * Spin-waits up to LONG_DELAY_MS milliseconds for the given thread to + * enter a wait state: BLOCKED, WAITING, or TIMED_WAITING, + * and additionally satisfy the given condition. + */ + void waitForThreadToEnterWaitState( + Thread thread, Callable<Boolean> waitingForGodot) { + waitForThreadToEnterWaitState(thread, LONG_DELAY_MS, waitingForGodot); + } + + /** * Returns the number of milliseconds since time given by * startNanoTime, which must have been previously returned from a * call to {@link System#nanoTime()}.
--- a/jdk/test/java/util/concurrent/tck/LinkedTransferQueueTest.java Fri Mar 03 10:45:38 2017 -0800 +++ b/jdk/test/java/util/concurrent/tck/LinkedTransferQueueTest.java Fri Mar 03 10:45:38 2017 -0800 @@ -42,6 +42,7 @@ import java.util.NoSuchElementException; import java.util.Queue; import java.util.concurrent.BlockingQueue; +import java.util.concurrent.Callable; import java.util.concurrent.CountDownLatch; import java.util.concurrent.Executors; import java.util.concurrent.ExecutorService; @@ -766,9 +767,11 @@ }}); threadStarted.await(); - waitForThreadToEnterWaitState(t); - assertEquals(1, q.getWaitingConsumerCount()); - assertTrue(q.hasWaitingConsumer()); + Callable<Boolean> oneConsumer + = new Callable<Boolean>() { public Boolean call() { + return q.hasWaitingConsumer() + && q.getWaitingConsumerCount() == 1; }}; + waitForThreadToEnterWaitState(t, oneConsumer); assertTrue(q.offer(one)); assertEquals(0, q.getWaitingConsumerCount()); @@ -790,7 +793,7 @@ /** * transfer waits until a poll occurs. The transfered element - * is returned by this associated poll. + * is returned by the associated poll. */ public void testTransfer2() throws InterruptedException { final LinkedTransferQueue<Integer> q = new LinkedTransferQueue<>(); @@ -804,8 +807,11 @@ }}); threadStarted.await(); - waitForThreadToEnterWaitState(t); - assertEquals(1, q.size()); + Callable<Boolean> oneElement + = new Callable<Boolean>() { public Boolean call() { + return !q.isEmpty() && q.size() == 1; }}; + waitForThreadToEnterWaitState(t, oneElement); + assertSame(five, q.poll()); checkEmpty(q); awaitTermination(t); @@ -868,7 +874,7 @@ /** * transfer waits until a take occurs. The transfered element - * is returned by this associated take. + * is returned by the associated take. */ public void testTransfer5() throws InterruptedException { final LinkedTransferQueue<Integer> q = new LinkedTransferQueue<>();
--- a/jdk/test/java/util/concurrent/tck/PhaserTest.java Fri Mar 03 10:45:38 2017 -0800 +++ b/jdk/test/java/util/concurrent/tck/PhaserTest.java Fri Mar 03 10:45:38 2017 -0800 @@ -550,7 +550,7 @@ }}); await(pleaseArrive); - waitForThreadToEnterWaitState(t, SHORT_DELAY_MS); + waitForThreadToEnterWaitState(t); assertEquals(0, phaser.arrive()); awaitTermination(t); @@ -578,7 +578,7 @@ }}); await(pleaseArrive); - waitForThreadToEnterWaitState(t, SHORT_DELAY_MS); + waitForThreadToEnterWaitState(t); t.interrupt(); assertEquals(0, phaser.arrive()); awaitTermination(t); @@ -594,20 +594,20 @@ public void testArriveAndAwaitAdvanceAfterInterrupt() { final Phaser phaser = new Phaser(); assertEquals(0, phaser.register()); - final CountDownLatch pleaseInterrupt = new CountDownLatch(1); + final CountDownLatch pleaseArrive = new CountDownLatch(1); Thread t = newStartedThread(new CheckedRunnable() { public void realRun() { Thread.currentThread().interrupt(); assertEquals(0, phaser.register()); - pleaseInterrupt.countDown(); + pleaseArrive.countDown(); assertTrue(Thread.currentThread().isInterrupted()); assertEquals(1, phaser.arriveAndAwaitAdvance()); - assertTrue(Thread.currentThread().isInterrupted()); + assertTrue(Thread.interrupted()); }}); - await(pleaseInterrupt); - waitForThreadToEnterWaitState(t, SHORT_DELAY_MS); + await(pleaseArrive); + waitForThreadToEnterWaitState(t); Thread.currentThread().interrupt(); assertEquals(1, phaser.arriveAndAwaitAdvance()); assertTrue(Thread.interrupted()); @@ -628,11 +628,11 @@ assertFalse(Thread.currentThread().isInterrupted()); pleaseInterrupt.countDown(); assertEquals(1, phaser.arriveAndAwaitAdvance()); - assertTrue(Thread.currentThread().isInterrupted()); + assertTrue(Thread.interrupted()); }}); await(pleaseInterrupt); - waitForThreadToEnterWaitState(t, SHORT_DELAY_MS); + waitForThreadToEnterWaitState(t); t.interrupt(); Thread.currentThread().interrupt(); assertEquals(1, phaser.arriveAndAwaitAdvance()); @@ -807,7 +807,7 @@ assertEquals(THREADS, phaser.getArrivedParties()); assertTrue(millisElapsedSince(startTime) < LONG_DELAY_MS); for (Thread thread : threads) - waitForThreadToEnterWaitState(thread, SHORT_DELAY_MS); + waitForThreadToEnterWaitState(thread); for (Thread thread : threads) assertTrue(thread.isAlive()); assertState(phaser, 0, THREADS + 1, 1);
--- a/jdk/test/java/util/concurrent/tck/StampedLockTest.java Fri Mar 03 10:45:38 2017 -0800 +++ b/jdk/test/java/util/concurrent/tck/StampedLockTest.java Fri Mar 03 10:45:38 2017 -0800 @@ -299,7 +299,6 @@ * interruptible operations throw InterruptedException when pre-interrupted */ public void testInterruptibleOperationsThrowInterruptedExceptionWhenPreInterrupted() { - final CountDownLatch running = new CountDownLatch(1); final StampedLock lock = new StampedLock(); Action[] interruptibleLockActions = { @@ -364,7 +363,6 @@ * interruptible operations throw InterruptedException when write locked and interrupted */ public void testInterruptibleOperationsThrowInterruptedExceptionWriteLockedInterrupted() { - final CountDownLatch running = new CountDownLatch(1); final StampedLock lock = new StampedLock(); long s = lock.writeLock(); @@ -387,7 +385,6 @@ * interruptible operations throw InterruptedException when read locked and interrupted */ public void testInterruptibleOperationsThrowInterruptedExceptionReadLockedInterrupted() { - final CountDownLatch running = new CountDownLatch(1); final StampedLock lock = new StampedLock(); long s = lock.readLock(); @@ -506,29 +503,32 @@ } /** - * A writelock succeeds only after a reading thread unlocks + * writeLock() succeeds only after a reading thread unlocks */ public void testWriteAfterReadLock() throws InterruptedException { - final CountDownLatch running = new CountDownLatch(1); + final CountDownLatch aboutToLock = new CountDownLatch(1); final StampedLock lock = new StampedLock(); long rs = lock.readLock(); Thread t = newStartedThread(new CheckedRunnable() { public void realRun() { - running.countDown(); + aboutToLock.countDown(); long s = lock.writeLock(); + assertTrue(lock.isWriteLocked()); + assertFalse(lock.isReadLocked()); lock.unlockWrite(s); }}); - running.await(); - waitForThreadToEnterWaitState(t, MEDIUM_DELAY_MS); + aboutToLock.await(); + waitForThreadToEnterWaitState(t); assertFalse(lock.isWriteLocked()); + assertTrue(lock.isReadLocked()); lock.unlockRead(rs); awaitTermination(t); - assertFalse(lock.isWriteLocked()); + assertUnlocked(lock); } /** - * A writelock succeeds only after reading threads unlock + * writeLock() succeeds only after reading threads unlock */ public void testWriteAfterMultipleReadLocks() { final StampedLock lock = new StampedLock(); @@ -551,35 +551,36 @@ assertFalse(lock.isWriteLocked()); lock.unlockRead(s); awaitTermination(t2); - assertFalse(lock.isWriteLocked()); + assertUnlocked(lock); } /** - * Readlocks succeed only after a writing thread unlocks + * readLock() succeed only after a writing thread unlocks */ public void testReadAfterWriteLock() { final StampedLock lock = new StampedLock(); final CountDownLatch threadsStarted = new CountDownLatch(2); final long s = lock.writeLock(); - Thread t1 = newStartedThread(new CheckedRunnable() { - public void realRun() { - threadsStarted.countDown(); - long rs = lock.readLock(); - lock.unlockRead(rs); - }}); - Thread t2 = newStartedThread(new CheckedRunnable() { + final Runnable acquireReleaseReadLock = new CheckedRunnable() { public void realRun() { threadsStarted.countDown(); long rs = lock.readLock(); + assertTrue(lock.isReadLocked()); + assertFalse(lock.isWriteLocked()); lock.unlockRead(rs); - }}); + }}; + Thread t1 = newStartedThread(acquireReleaseReadLock); + Thread t2 = newStartedThread(acquireReleaseReadLock); await(threadsStarted); - waitForThreadToEnterWaitState(t1, MEDIUM_DELAY_MS); - waitForThreadToEnterWaitState(t2, MEDIUM_DELAY_MS); + waitForThreadToEnterWaitState(t1); + waitForThreadToEnterWaitState(t2); + assertTrue(lock.isWriteLocked()); + assertFalse(lock.isReadLocked()); releaseWriteLock(lock, s); awaitTermination(t1); awaitTermination(t2); + assertUnlocked(lock); } /** @@ -765,22 +766,24 @@ */ public void testValidateOptimisticWriteLocked2() throws InterruptedException { - final CountDownLatch running = new CountDownLatch(1); + final CountDownLatch locked = new CountDownLatch(1); final StampedLock lock = new StampedLock(); final long p = assertValid(lock, lock.tryOptimisticRead()); Thread t = newStartedThread(new CheckedInterruptedRunnable() { public void realRun() throws InterruptedException { lock.writeLockInterruptibly(); - running.countDown(); + locked.countDown(); lock.writeLockInterruptibly(); }}); - running.await(); + locked.await(); assertFalse(lock.validate(p)); assertEquals(0L, lock.tryOptimisticRead()); + waitForThreadToEnterWaitState(t); t.interrupt(); awaitTermination(t); + assertTrue(lock.isWriteLocked()); } /**