8173909: Miscellaneous changes imported from jsr166 CVS 2017-03
Reviewed-by: martin, psandoz
--- 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());
}
/**