1/*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3 *
4 * This code is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License version 2 only, as
6 * published by the Free Software Foundation.
7 *
8 * This code is distributed in the hope that it will be useful, but WITHOUT
9 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
10 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
11 * version 2 for more details (a copy is included in the LICENSE file that
12 * accompanied this code).
13 *
14 * You should have received a copy of the GNU General Public License version
15 * 2 along with this work; if not, write to the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
17 *
18 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
19 * or visit www.oracle.com if you need additional information or have any
20 * questions.
21 */
22
23/*
24 * This file is available under and governed by the GNU General Public
25 * License version 2 only, as published by the Free Software Foundation.
26 * However, the following notice accompanied the original version of this
27 * file:
28 *
29 * Written by Doug Lea with assistance from members of JCP JSR-166
30 * Expert Group and released to the public domain, as explained at
31 * http://creativecommons.org/publicdomain/zero/1.0/
32 * Other contributors include Andrew Wright, Jeffrey Hayes,
33 * Pat Fisher, Mike Judd.
34 */
35
36import static java.util.concurrent.TimeUnit.MILLISECONDS;
37import static java.util.concurrent.TimeUnit.NANOSECONDS;
38
39import java.util.Arrays;
40import java.util.Collection;
41import java.util.HashSet;
42import java.util.concurrent.locks.AbstractQueuedLongSynchronizer;
43import java.util.concurrent.locks.AbstractQueuedLongSynchronizer.ConditionObject;
44
45import junit.framework.AssertionFailedError;
46import junit.framework.Test;
47import junit.framework.TestSuite;
48
49@SuppressWarnings("WaitNotInLoop") // we implement spurious-wakeup freedom
50public class AbstractQueuedLongSynchronizerTest extends JSR166TestCase {
51    public static void main(String[] args) {
52        main(suite(), args);
53    }
54    public static Test suite() {
55        return new TestSuite(AbstractQueuedLongSynchronizerTest.class);
56    }
57
58    /**
59     * A simple mutex class, adapted from the class javadoc.  Exclusive
60     * acquire tests exercise this as a sample user extension.
61     */
62    static class Mutex extends AbstractQueuedLongSynchronizer {
63        /** An eccentric value > 32 bits for locked synchronizer state. */
64        static final long LOCKED = (1L << 63) | (1L << 15);
65
66        static final long UNLOCKED = 0;
67
68        public boolean isHeldExclusively() {
69            long state = getState();
70            assertTrue(state == UNLOCKED || state == LOCKED);
71            return state == LOCKED;
72        }
73
74        public boolean tryAcquire(long acquires) {
75            assertEquals(LOCKED, acquires);
76            return compareAndSetState(UNLOCKED, LOCKED);
77        }
78
79        public boolean tryRelease(long releases) {
80            if (getState() != LOCKED) throw new IllegalMonitorStateException();
81            setState(UNLOCKED);
82            return true;
83        }
84
85        public boolean tryAcquireNanos(long nanos) throws InterruptedException {
86            return tryAcquireNanos(LOCKED, nanos);
87        }
88
89        public boolean tryAcquire() {
90            return tryAcquire(LOCKED);
91        }
92
93        public boolean tryRelease() {
94            return tryRelease(LOCKED);
95        }
96
97        public void acquire() {
98            acquire(LOCKED);
99        }
100
101        public void acquireInterruptibly() throws InterruptedException {
102            acquireInterruptibly(LOCKED);
103        }
104
105        public void release() {
106            release(LOCKED);
107        }
108
109        public ConditionObject newCondition() {
110            return new ConditionObject();
111        }
112    }
113
114    /**
115     * A simple latch class, to test shared mode.
116     */
117    static class BooleanLatch extends AbstractQueuedLongSynchronizer {
118        public boolean isSignalled() { return getState() != 0; }
119
120        public long tryAcquireShared(long ignore) {
121            return isSignalled() ? 1 : -1;
122        }
123
124        public boolean tryReleaseShared(long ignore) {
125            setState(1L << 62);
126            return true;
127        }
128    }
129
130    /**
131     * A runnable calling acquireInterruptibly that does not expect to
132     * be interrupted.
133     */
134    class InterruptibleSyncRunnable extends CheckedRunnable {
135        final Mutex sync;
136        InterruptibleSyncRunnable(Mutex sync) { this.sync = sync; }
137        public void realRun() throws InterruptedException {
138            sync.acquireInterruptibly();
139        }
140    }
141
142    /**
143     * A runnable calling acquireInterruptibly that expects to be
144     * interrupted.
145     */
146    class InterruptedSyncRunnable extends CheckedInterruptedRunnable {
147        final Mutex sync;
148        InterruptedSyncRunnable(Mutex sync) { this.sync = sync; }
149        public void realRun() throws InterruptedException {
150            sync.acquireInterruptibly();
151        }
152    }
153
154    /** A constant to clarify calls to checking methods below. */
155    static final Thread[] NO_THREADS = new Thread[0];
156
157    /**
158     * Spin-waits until sync.isQueued(t) becomes true.
159     */
160    void waitForQueuedThread(AbstractQueuedLongSynchronizer sync,
161                             Thread t) {
162        long startTime = System.nanoTime();
163        while (!sync.isQueued(t)) {
164            if (millisElapsedSince(startTime) > LONG_DELAY_MS)
165                throw new AssertionFailedError("timed out");
166            Thread.yield();
167        }
168        assertTrue(t.isAlive());
169    }
170
171    /**
172     * Checks that sync has exactly the given queued threads.
173     */
174    void assertHasQueuedThreads(AbstractQueuedLongSynchronizer sync,
175                                Thread... expected) {
176        Collection<Thread> actual = sync.getQueuedThreads();
177        assertEquals(expected.length > 0, sync.hasQueuedThreads());
178        assertEquals(expected.length, sync.getQueueLength());
179        assertEquals(expected.length, actual.size());
180        assertEquals(expected.length == 0, actual.isEmpty());
181        assertEquals(new HashSet<Thread>(actual),
182                     new HashSet<Thread>(Arrays.asList(expected)));
183    }
184
185    /**
186     * Checks that sync has exactly the given (exclusive) queued threads.
187     */
188    void assertHasExclusiveQueuedThreads(AbstractQueuedLongSynchronizer sync,
189                                         Thread... expected) {
190        assertHasQueuedThreads(sync, expected);
191        assertEquals(new HashSet<Thread>(sync.getExclusiveQueuedThreads()),
192                     new HashSet<Thread>(sync.getQueuedThreads()));
193        assertEquals(0, sync.getSharedQueuedThreads().size());
194        assertTrue(sync.getSharedQueuedThreads().isEmpty());
195    }
196
197    /**
198     * Checks that sync has exactly the given (shared) queued threads.
199     */
200    void assertHasSharedQueuedThreads(AbstractQueuedLongSynchronizer sync,
201                                      Thread... expected) {
202        assertHasQueuedThreads(sync, expected);
203        assertEquals(new HashSet<Thread>(sync.getSharedQueuedThreads()),
204                     new HashSet<Thread>(sync.getQueuedThreads()));
205        assertEquals(0, sync.getExclusiveQueuedThreads().size());
206        assertTrue(sync.getExclusiveQueuedThreads().isEmpty());
207    }
208
209    /**
210     * Checks that condition c has exactly the given waiter threads,
211     * after acquiring mutex.
212     */
213    void assertHasWaitersUnlocked(Mutex sync, ConditionObject c,
214                                 Thread... threads) {
215        sync.acquire();
216        assertHasWaitersLocked(sync, c, threads);
217        sync.release();
218    }
219
220    /**
221     * Checks that condition c has exactly the given waiter threads.
222     */
223    void assertHasWaitersLocked(Mutex sync, ConditionObject c,
224                                Thread... threads) {
225        assertEquals(threads.length > 0, sync.hasWaiters(c));
226        assertEquals(threads.length, sync.getWaitQueueLength(c));
227        assertEquals(threads.length == 0, sync.getWaitingThreads(c).isEmpty());
228        assertEquals(threads.length, sync.getWaitingThreads(c).size());
229        assertEquals(new HashSet<Thread>(sync.getWaitingThreads(c)),
230                     new HashSet<Thread>(Arrays.asList(threads)));
231    }
232
233    enum AwaitMethod { await, awaitTimed, awaitNanos, awaitUntil }
234
235    /**
236     * Awaits condition using the specified AwaitMethod.
237     */
238    void await(ConditionObject c, AwaitMethod awaitMethod)
239            throws InterruptedException {
240        long timeoutMillis = 2 * LONG_DELAY_MS;
241        switch (awaitMethod) {
242        case await:
243            c.await();
244            break;
245        case awaitTimed:
246            assertTrue(c.await(timeoutMillis, MILLISECONDS));
247            break;
248        case awaitNanos:
249            long nanosTimeout = MILLISECONDS.toNanos(timeoutMillis);
250            long nanosRemaining = c.awaitNanos(nanosTimeout);
251            assertTrue(nanosRemaining > 0);
252            break;
253        case awaitUntil:
254            assertTrue(c.awaitUntil(delayedDate(timeoutMillis)));
255            break;
256        default:
257            throw new AssertionError();
258        }
259    }
260
261    /**
262     * Checks that awaiting the given condition times out (using the
263     * default timeout duration).
264     */
265    void assertAwaitTimesOut(ConditionObject c, AwaitMethod awaitMethod) {
266        final long timeoutMillis = timeoutMillis();
267        final long startTime;
268        try {
269            switch (awaitMethod) {
270            case awaitTimed:
271                startTime = System.nanoTime();
272                assertFalse(c.await(timeoutMillis, MILLISECONDS));
273                assertTrue(millisElapsedSince(startTime) >= timeoutMillis);
274                break;
275            case awaitNanos:
276                startTime = System.nanoTime();
277                long nanosTimeout = MILLISECONDS.toNanos(timeoutMillis);
278                long nanosRemaining = c.awaitNanos(nanosTimeout);
279                assertTrue(nanosRemaining <= 0);
280                assertTrue(nanosRemaining > -MILLISECONDS.toNanos(LONG_DELAY_MS));
281                assertTrue(millisElapsedSince(startTime) >= timeoutMillis);
282                break;
283            case awaitUntil:
284                // We shouldn't assume that nanoTime and currentTimeMillis
285                // use the same time source, so don't use nanoTime here.
286                java.util.Date delayedDate = delayedDate(timeoutMillis);
287                assertFalse(c.awaitUntil(delayedDate(timeoutMillis)));
288                assertTrue(new java.util.Date().getTime() >= delayedDate.getTime());
289                break;
290            default:
291                throw new UnsupportedOperationException();
292            }
293        } catch (InterruptedException ie) { threadUnexpectedException(ie); }
294    }
295
296    /**
297     * isHeldExclusively is false upon construction
298     */
299    public void testIsHeldExclusively() {
300        Mutex sync = new Mutex();
301        assertFalse(sync.isHeldExclusively());
302    }
303
304    /**
305     * acquiring released sync succeeds
306     */
307    public void testAcquire() {
308        Mutex sync = new Mutex();
309        sync.acquire();
310        assertTrue(sync.isHeldExclusively());
311        sync.release();
312        assertFalse(sync.isHeldExclusively());
313    }
314
315    /**
316     * tryAcquire on a released sync succeeds
317     */
318    public void testTryAcquire() {
319        Mutex sync = new Mutex();
320        assertTrue(sync.tryAcquire());
321        assertTrue(sync.isHeldExclusively());
322        sync.release();
323        assertFalse(sync.isHeldExclusively());
324    }
325
326    /**
327     * hasQueuedThreads reports whether there are waiting threads
328     */
329    public void testHasQueuedThreads() {
330        final Mutex sync = new Mutex();
331        assertFalse(sync.hasQueuedThreads());
332        sync.acquire();
333        Thread t1 = newStartedThread(new InterruptedSyncRunnable(sync));
334        waitForQueuedThread(sync, t1);
335        assertTrue(sync.hasQueuedThreads());
336        Thread t2 = newStartedThread(new InterruptibleSyncRunnable(sync));
337        waitForQueuedThread(sync, t2);
338        assertTrue(sync.hasQueuedThreads());
339        t1.interrupt();
340        awaitTermination(t1);
341        assertTrue(sync.hasQueuedThreads());
342        sync.release();
343        awaitTermination(t2);
344        assertFalse(sync.hasQueuedThreads());
345    }
346
347    /**
348     * isQueued(null) throws NullPointerException
349     */
350    public void testIsQueuedNPE() {
351        final Mutex sync = new Mutex();
352        try {
353            sync.isQueued(null);
354            shouldThrow();
355        } catch (NullPointerException success) {}
356    }
357
358    /**
359     * isQueued reports whether a thread is queued
360     */
361    public void testIsQueued() {
362        final Mutex sync = new Mutex();
363        Thread t1 = new Thread(new InterruptedSyncRunnable(sync));
364        Thread t2 = new Thread(new InterruptibleSyncRunnable(sync));
365        assertFalse(sync.isQueued(t1));
366        assertFalse(sync.isQueued(t2));
367        sync.acquire();
368        t1.start();
369        waitForQueuedThread(sync, t1);
370        assertTrue(sync.isQueued(t1));
371        assertFalse(sync.isQueued(t2));
372        t2.start();
373        waitForQueuedThread(sync, t2);
374        assertTrue(sync.isQueued(t1));
375        assertTrue(sync.isQueued(t2));
376        t1.interrupt();
377        awaitTermination(t1);
378        assertFalse(sync.isQueued(t1));
379        assertTrue(sync.isQueued(t2));
380        sync.release();
381        awaitTermination(t2);
382        assertFalse(sync.isQueued(t1));
383        assertFalse(sync.isQueued(t2));
384    }
385
386    /**
387     * getFirstQueuedThread returns first waiting thread or null if none
388     */
389    public void testGetFirstQueuedThread() {
390        final Mutex sync = new Mutex();
391        assertNull(sync.getFirstQueuedThread());
392        sync.acquire();
393        Thread t1 = newStartedThread(new InterruptedSyncRunnable(sync));
394        waitForQueuedThread(sync, t1);
395        assertEquals(t1, sync.getFirstQueuedThread());
396        Thread t2 = newStartedThread(new InterruptibleSyncRunnable(sync));
397        waitForQueuedThread(sync, t2);
398        assertEquals(t1, sync.getFirstQueuedThread());
399        t1.interrupt();
400        awaitTermination(t1);
401        assertEquals(t2, sync.getFirstQueuedThread());
402        sync.release();
403        awaitTermination(t2);
404        assertNull(sync.getFirstQueuedThread());
405    }
406
407    /**
408     * hasContended reports false if no thread has ever blocked, else true
409     */
410    public void testHasContended() {
411        final Mutex sync = new Mutex();
412        assertFalse(sync.hasContended());
413        sync.acquire();
414        assertFalse(sync.hasContended());
415        Thread t1 = newStartedThread(new InterruptedSyncRunnable(sync));
416        waitForQueuedThread(sync, t1);
417        assertTrue(sync.hasContended());
418        Thread t2 = newStartedThread(new InterruptibleSyncRunnable(sync));
419        waitForQueuedThread(sync, t2);
420        assertTrue(sync.hasContended());
421        t1.interrupt();
422        awaitTermination(t1);
423        assertTrue(sync.hasContended());
424        sync.release();
425        awaitTermination(t2);
426        assertTrue(sync.hasContended());
427    }
428
429    /**
430     * getQueuedThreads returns all waiting threads
431     */
432    public void testGetQueuedThreads() {
433        final Mutex sync = new Mutex();
434        Thread t1 = new Thread(new InterruptedSyncRunnable(sync));
435        Thread t2 = new Thread(new InterruptibleSyncRunnable(sync));
436        assertHasExclusiveQueuedThreads(sync, NO_THREADS);
437        sync.acquire();
438        assertHasExclusiveQueuedThreads(sync, NO_THREADS);
439        t1.start();
440        waitForQueuedThread(sync, t1);
441        assertHasExclusiveQueuedThreads(sync, t1);
442        assertTrue(sync.getQueuedThreads().contains(t1));
443        assertFalse(sync.getQueuedThreads().contains(t2));
444        t2.start();
445        waitForQueuedThread(sync, t2);
446        assertHasExclusiveQueuedThreads(sync, t1, t2);
447        assertTrue(sync.getQueuedThreads().contains(t1));
448        assertTrue(sync.getQueuedThreads().contains(t2));
449        t1.interrupt();
450        awaitTermination(t1);
451        assertHasExclusiveQueuedThreads(sync, t2);
452        sync.release();
453        awaitTermination(t2);
454        assertHasExclusiveQueuedThreads(sync, NO_THREADS);
455    }
456
457    /**
458     * getExclusiveQueuedThreads returns all exclusive waiting threads
459     */
460    public void testGetExclusiveQueuedThreads() {
461        final Mutex sync = new Mutex();
462        Thread t1 = new Thread(new InterruptedSyncRunnable(sync));
463        Thread t2 = new Thread(new InterruptibleSyncRunnable(sync));
464        assertHasExclusiveQueuedThreads(sync, NO_THREADS);
465        sync.acquire();
466        assertHasExclusiveQueuedThreads(sync, NO_THREADS);
467        t1.start();
468        waitForQueuedThread(sync, t1);
469        assertHasExclusiveQueuedThreads(sync, t1);
470        assertTrue(sync.getExclusiveQueuedThreads().contains(t1));
471        assertFalse(sync.getExclusiveQueuedThreads().contains(t2));
472        t2.start();
473        waitForQueuedThread(sync, t2);
474        assertHasExclusiveQueuedThreads(sync, t1, t2);
475        assertTrue(sync.getExclusiveQueuedThreads().contains(t1));
476        assertTrue(sync.getExclusiveQueuedThreads().contains(t2));
477        t1.interrupt();
478        awaitTermination(t1);
479        assertHasExclusiveQueuedThreads(sync, t2);
480        sync.release();
481        awaitTermination(t2);
482        assertHasExclusiveQueuedThreads(sync, NO_THREADS);
483    }
484
485    /**
486     * getSharedQueuedThreads does not include exclusively waiting threads
487     */
488    public void testGetSharedQueuedThreads_Exclusive() {
489        final Mutex sync = new Mutex();
490        assertTrue(sync.getSharedQueuedThreads().isEmpty());
491        sync.acquire();
492        assertTrue(sync.getSharedQueuedThreads().isEmpty());
493        Thread t1 = newStartedThread(new InterruptedSyncRunnable(sync));
494        waitForQueuedThread(sync, t1);
495        assertTrue(sync.getSharedQueuedThreads().isEmpty());
496        Thread t2 = newStartedThread(new InterruptibleSyncRunnable(sync));
497        waitForQueuedThread(sync, t2);
498        assertTrue(sync.getSharedQueuedThreads().isEmpty());
499        t1.interrupt();
500        awaitTermination(t1);
501        assertTrue(sync.getSharedQueuedThreads().isEmpty());
502        sync.release();
503        awaitTermination(t2);
504        assertTrue(sync.getSharedQueuedThreads().isEmpty());
505    }
506
507    /**
508     * getSharedQueuedThreads returns all shared waiting threads
509     */
510    public void testGetSharedQueuedThreads_Shared() {
511        final BooleanLatch l = new BooleanLatch();
512        assertHasSharedQueuedThreads(l, NO_THREADS);
513        Thread t1 = newStartedThread(new CheckedInterruptedRunnable() {
514            public void realRun() throws InterruptedException {
515                l.acquireSharedInterruptibly(0);
516            }});
517        waitForQueuedThread(l, t1);
518        assertHasSharedQueuedThreads(l, t1);
519        Thread t2 = newStartedThread(new CheckedRunnable() {
520            public void realRun() throws InterruptedException {
521                l.acquireSharedInterruptibly(0);
522            }});
523        waitForQueuedThread(l, t2);
524        assertHasSharedQueuedThreads(l, t1, t2);
525        t1.interrupt();
526        awaitTermination(t1);
527        assertHasSharedQueuedThreads(l, t2);
528        assertTrue(l.releaseShared(0));
529        awaitTermination(t2);
530        assertHasSharedQueuedThreads(l, NO_THREADS);
531    }
532
533    /**
534     * tryAcquireNanos is interruptible
535     */
536    public void testTryAcquireNanos_Interruptible() {
537        final Mutex sync = new Mutex();
538        sync.acquire();
539        Thread t = newStartedThread(new CheckedInterruptedRunnable() {
540            public void realRun() throws InterruptedException {
541                sync.tryAcquireNanos(MILLISECONDS.toNanos(2 * LONG_DELAY_MS));
542            }});
543
544        waitForQueuedThread(sync, t);
545        t.interrupt();
546        awaitTermination(t);
547    }
548
549    /**
550     * tryAcquire on exclusively held sync fails
551     */
552    public void testTryAcquireWhenSynced() {
553        final Mutex sync = new Mutex();
554        sync.acquire();
555        Thread t = newStartedThread(new CheckedRunnable() {
556            public void realRun() {
557                assertFalse(sync.tryAcquire());
558            }});
559
560        awaitTermination(t);
561        sync.release();
562    }
563
564    /**
565     * tryAcquireNanos on an exclusively held sync times out
566     */
567    public void testAcquireNanos_Timeout() {
568        final Mutex sync = new Mutex();
569        sync.acquire();
570        Thread t = newStartedThread(new CheckedRunnable() {
571            public void realRun() throws InterruptedException {
572                long startTime = System.nanoTime();
573                long nanos = MILLISECONDS.toNanos(timeoutMillis());
574                assertFalse(sync.tryAcquireNanos(nanos));
575                assertTrue(millisElapsedSince(startTime) >= timeoutMillis());
576            }});
577
578        awaitTermination(t);
579        sync.release();
580    }
581
582    /**
583     * getState is true when acquired and false when not
584     */
585    public void testGetState() {
586        final Mutex sync = new Mutex();
587        sync.acquire();
588        assertTrue(sync.isHeldExclusively());
589        sync.release();
590        assertFalse(sync.isHeldExclusively());
591
592        final BooleanLatch acquired = new BooleanLatch();
593        final BooleanLatch done = new BooleanLatch();
594        Thread t = newStartedThread(new CheckedRunnable() {
595            public void realRun() throws InterruptedException {
596                sync.acquire();
597                assertTrue(acquired.releaseShared(0));
598                done.acquireShared(0);
599                sync.release();
600            }});
601
602        acquired.acquireShared(0);
603        assertTrue(sync.isHeldExclusively());
604        assertTrue(done.releaseShared(0));
605        awaitTermination(t);
606        assertFalse(sync.isHeldExclusively());
607    }
608
609    /**
610     * acquireInterruptibly succeeds when released, else is interruptible
611     */
612    public void testAcquireInterruptibly() throws InterruptedException {
613        final Mutex sync = new Mutex();
614        final BooleanLatch threadStarted = new BooleanLatch();
615        sync.acquireInterruptibly();
616        Thread t = newStartedThread(new CheckedInterruptedRunnable() {
617            public void realRun() throws InterruptedException {
618                assertTrue(threadStarted.releaseShared(0));
619                sync.acquireInterruptibly();
620            }});
621
622        threadStarted.acquireShared(0);
623        waitForQueuedThread(sync, t);
624        t.interrupt();
625        awaitTermination(t);
626        assertTrue(sync.isHeldExclusively());
627    }
628
629    /**
630     * owns is true for a condition created by sync else false
631     */
632    public void testOwns() {
633        final Mutex sync = new Mutex();
634        final ConditionObject c = sync.newCondition();
635        final Mutex sync2 = new Mutex();
636        assertTrue(sync.owns(c));
637        assertFalse(sync2.owns(c));
638    }
639
640    /**
641     * Calling await without holding sync throws IllegalMonitorStateException
642     */
643    public void testAwait_IMSE() {
644        final Mutex sync = new Mutex();
645        final ConditionObject c = sync.newCondition();
646        for (AwaitMethod awaitMethod : AwaitMethod.values()) {
647            long startTime = System.nanoTime();
648            try {
649                await(c, awaitMethod);
650                shouldThrow();
651            } catch (IllegalMonitorStateException success) {
652            } catch (InterruptedException e) { threadUnexpectedException(e); }
653            assertTrue(millisElapsedSince(startTime) < LONG_DELAY_MS);
654        }
655    }
656
657    /**
658     * Calling signal without holding sync throws IllegalMonitorStateException
659     */
660    public void testSignal_IMSE() {
661        final Mutex sync = new Mutex();
662        final ConditionObject c = sync.newCondition();
663        try {
664            c.signal();
665            shouldThrow();
666        } catch (IllegalMonitorStateException success) {}
667        assertHasWaitersUnlocked(sync, c, NO_THREADS);
668    }
669
670    /**
671     * Calling signalAll without holding sync throws IllegalMonitorStateException
672     */
673    public void testSignalAll_IMSE() {
674        final Mutex sync = new Mutex();
675        final ConditionObject c = sync.newCondition();
676        try {
677            c.signalAll();
678            shouldThrow();
679        } catch (IllegalMonitorStateException success) {}
680    }
681
682    /**
683     * await/awaitNanos/awaitUntil without a signal times out
684     */
685    public void testAwaitTimed_Timeout() { testAwait_Timeout(AwaitMethod.awaitTimed); }
686    public void testAwaitNanos_Timeout() { testAwait_Timeout(AwaitMethod.awaitNanos); }
687    public void testAwaitUntil_Timeout() { testAwait_Timeout(AwaitMethod.awaitUntil); }
688    public void testAwait_Timeout(AwaitMethod awaitMethod) {
689        final Mutex sync = new Mutex();
690        final ConditionObject c = sync.newCondition();
691        sync.acquire();
692        assertAwaitTimesOut(c, awaitMethod);
693        sync.release();
694    }
695
696    /**
697     * await/awaitNanos/awaitUntil returns when signalled
698     */
699    public void testSignal_await()      { testSignal(AwaitMethod.await); }
700    public void testSignal_awaitTimed() { testSignal(AwaitMethod.awaitTimed); }
701    public void testSignal_awaitNanos() { testSignal(AwaitMethod.awaitNanos); }
702    public void testSignal_awaitUntil() { testSignal(AwaitMethod.awaitUntil); }
703    public void testSignal(final AwaitMethod awaitMethod) {
704        final Mutex sync = new Mutex();
705        final ConditionObject c = sync.newCondition();
706        final BooleanLatch acquired = new BooleanLatch();
707        Thread t = newStartedThread(new CheckedRunnable() {
708            public void realRun() throws InterruptedException {
709                sync.acquire();
710                assertTrue(acquired.releaseShared(0));
711                await(c, awaitMethod);
712                sync.release();
713            }});
714
715        acquired.acquireShared(0);
716        sync.acquire();
717        assertHasWaitersLocked(sync, c, t);
718        assertHasExclusiveQueuedThreads(sync, NO_THREADS);
719        c.signal();
720        assertHasWaitersLocked(sync, c, NO_THREADS);
721        assertHasExclusiveQueuedThreads(sync, t);
722        sync.release();
723        awaitTermination(t);
724    }
725
726    /**
727     * hasWaiters(null) throws NullPointerException
728     */
729    public void testHasWaitersNPE() {
730        final Mutex sync = new Mutex();
731        try {
732            sync.hasWaiters(null);
733            shouldThrow();
734        } catch (NullPointerException success) {}
735    }
736
737    /**
738     * getWaitQueueLength(null) throws NullPointerException
739     */
740    public void testGetWaitQueueLengthNPE() {
741        final Mutex sync = new Mutex();
742        try {
743            sync.getWaitQueueLength(null);
744            shouldThrow();
745        } catch (NullPointerException success) {}
746    }
747
748    /**
749     * getWaitingThreads throws NPE if null
750     */
751    public void testGetWaitingThreadsNPE() {
752        final Mutex sync = new Mutex();
753        try {
754            sync.getWaitingThreads(null);
755            shouldThrow();
756        } catch (NullPointerException success) {}
757    }
758
759    /**
760     * hasWaiters throws IllegalArgumentException if not owned
761     */
762    public void testHasWaitersIAE() {
763        final Mutex sync = new Mutex();
764        final ConditionObject c = sync.newCondition();
765        final Mutex sync2 = new Mutex();
766        try {
767            sync2.hasWaiters(c);
768            shouldThrow();
769        } catch (IllegalArgumentException success) {}
770        assertHasWaitersUnlocked(sync, c, NO_THREADS);
771    }
772
773    /**
774     * hasWaiters throws IllegalMonitorStateException if not synced
775     */
776    public void testHasWaitersIMSE() {
777        final Mutex sync = new Mutex();
778        final ConditionObject c = sync.newCondition();
779        try {
780            sync.hasWaiters(c);
781            shouldThrow();
782        } catch (IllegalMonitorStateException success) {}
783        assertHasWaitersUnlocked(sync, c, NO_THREADS);
784    }
785
786    /**
787     * getWaitQueueLength throws IllegalArgumentException if not owned
788     */
789    public void testGetWaitQueueLengthIAE() {
790        final Mutex sync = new Mutex();
791        final ConditionObject c = sync.newCondition();
792        final Mutex sync2 = new Mutex();
793        try {
794            sync2.getWaitQueueLength(c);
795            shouldThrow();
796        } catch (IllegalArgumentException success) {}
797        assertHasWaitersUnlocked(sync, c, NO_THREADS);
798    }
799
800    /**
801     * getWaitQueueLength throws IllegalMonitorStateException if not synced
802     */
803    public void testGetWaitQueueLengthIMSE() {
804        final Mutex sync = new Mutex();
805        final ConditionObject c = sync.newCondition();
806        try {
807            sync.getWaitQueueLength(c);
808            shouldThrow();
809        } catch (IllegalMonitorStateException success) {}
810        assertHasWaitersUnlocked(sync, c, NO_THREADS);
811    }
812
813    /**
814     * getWaitingThreads throws IllegalArgumentException if not owned
815     */
816    public void testGetWaitingThreadsIAE() {
817        final Mutex sync = new Mutex();
818        final ConditionObject c = sync.newCondition();
819        final Mutex sync2 = new Mutex();
820        try {
821            sync2.getWaitingThreads(c);
822            shouldThrow();
823        } catch (IllegalArgumentException success) {}
824        assertHasWaitersUnlocked(sync, c, NO_THREADS);
825    }
826
827    /**
828     * getWaitingThreads throws IllegalMonitorStateException if not synced
829     */
830    public void testGetWaitingThreadsIMSE() {
831        final Mutex sync = new Mutex();
832        final ConditionObject c = sync.newCondition();
833        try {
834            sync.getWaitingThreads(c);
835            shouldThrow();
836        } catch (IllegalMonitorStateException success) {}
837        assertHasWaitersUnlocked(sync, c, NO_THREADS);
838    }
839
840    /**
841     * hasWaiters returns true when a thread is waiting, else false
842     */
843    public void testHasWaiters() {
844        final Mutex sync = new Mutex();
845        final ConditionObject c = sync.newCondition();
846        final BooleanLatch acquired = new BooleanLatch();
847        Thread t = newStartedThread(new CheckedRunnable() {
848            public void realRun() throws InterruptedException {
849                sync.acquire();
850                assertHasWaitersLocked(sync, c, NO_THREADS);
851                assertFalse(sync.hasWaiters(c));
852                assertTrue(acquired.releaseShared(0));
853                c.await();
854                sync.release();
855            }});
856
857        acquired.acquireShared(0);
858        sync.acquire();
859        assertHasWaitersLocked(sync, c, t);
860        assertHasExclusiveQueuedThreads(sync, NO_THREADS);
861        assertTrue(sync.hasWaiters(c));
862        c.signal();
863        assertHasWaitersLocked(sync, c, NO_THREADS);
864        assertHasExclusiveQueuedThreads(sync, t);
865        assertFalse(sync.hasWaiters(c));
866        sync.release();
867
868        awaitTermination(t);
869        assertHasWaitersUnlocked(sync, c, NO_THREADS);
870    }
871
872    /**
873     * getWaitQueueLength returns number of waiting threads
874     */
875    public void testGetWaitQueueLength() {
876        final Mutex sync = new Mutex();
877        final ConditionObject c = sync.newCondition();
878        final BooleanLatch acquired1 = new BooleanLatch();
879        final BooleanLatch acquired2 = new BooleanLatch();
880        final Thread t1 = newStartedThread(new CheckedRunnable() {
881            public void realRun() throws InterruptedException {
882                sync.acquire();
883                assertHasWaitersLocked(sync, c, NO_THREADS);
884                assertEquals(0, sync.getWaitQueueLength(c));
885                assertTrue(acquired1.releaseShared(0));
886                c.await();
887                sync.release();
888            }});
889        acquired1.acquireShared(0);
890        sync.acquire();
891        assertHasWaitersLocked(sync, c, t1);
892        assertEquals(1, sync.getWaitQueueLength(c));
893        sync.release();
894
895        final Thread t2 = newStartedThread(new CheckedRunnable() {
896            public void realRun() throws InterruptedException {
897                sync.acquire();
898                assertHasWaitersLocked(sync, c, t1);
899                assertEquals(1, sync.getWaitQueueLength(c));
900                assertTrue(acquired2.releaseShared(0));
901                c.await();
902                sync.release();
903            }});
904        acquired2.acquireShared(0);
905        sync.acquire();
906        assertHasWaitersLocked(sync, c, t1, t2);
907        assertHasExclusiveQueuedThreads(sync, NO_THREADS);
908        assertEquals(2, sync.getWaitQueueLength(c));
909        c.signalAll();
910        assertHasWaitersLocked(sync, c, NO_THREADS);
911        assertHasExclusiveQueuedThreads(sync, t1, t2);
912        assertEquals(0, sync.getWaitQueueLength(c));
913        sync.release();
914
915        awaitTermination(t1);
916        awaitTermination(t2);
917        assertHasWaitersUnlocked(sync, c, NO_THREADS);
918    }
919
920    /**
921     * getWaitingThreads returns only and all waiting threads
922     */
923    public void testGetWaitingThreads() {
924        final Mutex sync = new Mutex();
925        final ConditionObject c = sync.newCondition();
926        final BooleanLatch acquired1 = new BooleanLatch();
927        final BooleanLatch acquired2 = new BooleanLatch();
928        final Thread t1 = new Thread(new CheckedRunnable() {
929            public void realRun() throws InterruptedException {
930                sync.acquire();
931                assertHasWaitersLocked(sync, c, NO_THREADS);
932                assertTrue(sync.getWaitingThreads(c).isEmpty());
933                assertTrue(acquired1.releaseShared(0));
934                c.await();
935                sync.release();
936            }});
937
938        final Thread t2 = new Thread(new CheckedRunnable() {
939            public void realRun() throws InterruptedException {
940                sync.acquire();
941                assertHasWaitersLocked(sync, c, t1);
942                assertTrue(sync.getWaitingThreads(c).contains(t1));
943                assertFalse(sync.getWaitingThreads(c).isEmpty());
944                assertEquals(1, sync.getWaitingThreads(c).size());
945                assertTrue(acquired2.releaseShared(0));
946                c.await();
947                sync.release();
948            }});
949
950        sync.acquire();
951        assertHasWaitersLocked(sync, c, NO_THREADS);
952        assertFalse(sync.getWaitingThreads(c).contains(t1));
953        assertFalse(sync.getWaitingThreads(c).contains(t2));
954        assertTrue(sync.getWaitingThreads(c).isEmpty());
955        assertEquals(0, sync.getWaitingThreads(c).size());
956        sync.release();
957
958        t1.start();
959        acquired1.acquireShared(0);
960        sync.acquire();
961        assertHasWaitersLocked(sync, c, t1);
962        assertTrue(sync.getWaitingThreads(c).contains(t1));
963        assertFalse(sync.getWaitingThreads(c).contains(t2));
964        assertFalse(sync.getWaitingThreads(c).isEmpty());
965        assertEquals(1, sync.getWaitingThreads(c).size());
966        sync.release();
967
968        t2.start();
969        acquired2.acquireShared(0);
970        sync.acquire();
971        assertHasWaitersLocked(sync, c, t1, t2);
972        assertHasExclusiveQueuedThreads(sync, NO_THREADS);
973        assertTrue(sync.getWaitingThreads(c).contains(t1));
974        assertTrue(sync.getWaitingThreads(c).contains(t2));
975        assertFalse(sync.getWaitingThreads(c).isEmpty());
976        assertEquals(2, sync.getWaitingThreads(c).size());
977        c.signalAll();
978        assertHasWaitersLocked(sync, c, NO_THREADS);
979        assertHasExclusiveQueuedThreads(sync, t1, t2);
980        assertFalse(sync.getWaitingThreads(c).contains(t1));
981        assertFalse(sync.getWaitingThreads(c).contains(t2));
982        assertTrue(sync.getWaitingThreads(c).isEmpty());
983        assertEquals(0, sync.getWaitingThreads(c).size());
984        sync.release();
985
986        awaitTermination(t1);
987        awaitTermination(t2);
988        assertHasWaitersUnlocked(sync, c, NO_THREADS);
989    }
990
991    /**
992     * awaitUninterruptibly is uninterruptible
993     */
994    public void testAwaitUninterruptibly() {
995        final Mutex sync = new Mutex();
996        final ConditionObject condition = sync.newCondition();
997        final BooleanLatch pleaseInterrupt = new BooleanLatch();
998        Thread t = newStartedThread(new CheckedRunnable() {
999            public void realRun() {
1000                sync.acquire();
1001                assertTrue(pleaseInterrupt.releaseShared(0));
1002                condition.awaitUninterruptibly();
1003                assertTrue(Thread.interrupted());
1004                assertHasWaitersLocked(sync, condition, NO_THREADS);
1005                sync.release();
1006            }});
1007
1008        pleaseInterrupt.acquireShared(0);
1009        sync.acquire();
1010        assertHasWaitersLocked(sync, condition, t);
1011        sync.release();
1012        t.interrupt();
1013        assertHasWaitersUnlocked(sync, condition, t);
1014        assertThreadBlocks(t, Thread.State.WAITING);
1015        sync.acquire();
1016        assertHasWaitersLocked(sync, condition, t);
1017        assertHasExclusiveQueuedThreads(sync, NO_THREADS);
1018        condition.signal();
1019        assertHasWaitersLocked(sync, condition, NO_THREADS);
1020        assertHasExclusiveQueuedThreads(sync, t);
1021        sync.release();
1022        awaitTermination(t);
1023    }
1024
1025    /**
1026     * await/awaitNanos/awaitUntil is interruptible
1027     */
1028    public void testInterruptible_await()      { testInterruptible(AwaitMethod.await); }
1029    public void testInterruptible_awaitTimed() { testInterruptible(AwaitMethod.awaitTimed); }
1030    public void testInterruptible_awaitNanos() { testInterruptible(AwaitMethod.awaitNanos); }
1031    public void testInterruptible_awaitUntil() { testInterruptible(AwaitMethod.awaitUntil); }
1032    public void testInterruptible(final AwaitMethod awaitMethod) {
1033        final Mutex sync = new Mutex();
1034        final ConditionObject c = sync.newCondition();
1035        final BooleanLatch pleaseInterrupt = new BooleanLatch();
1036        Thread t = newStartedThread(new CheckedInterruptedRunnable() {
1037            public void realRun() throws InterruptedException {
1038                sync.acquire();
1039                assertTrue(pleaseInterrupt.releaseShared(0));
1040                await(c, awaitMethod);
1041            }});
1042
1043        pleaseInterrupt.acquireShared(0);
1044        t.interrupt();
1045        awaitTermination(t);
1046    }
1047
1048    /**
1049     * signalAll wakes up all threads
1050     */
1051    public void testSignalAll_await()      { testSignalAll(AwaitMethod.await); }
1052    public void testSignalAll_awaitTimed() { testSignalAll(AwaitMethod.awaitTimed); }
1053    public void testSignalAll_awaitNanos() { testSignalAll(AwaitMethod.awaitNanos); }
1054    public void testSignalAll_awaitUntil() { testSignalAll(AwaitMethod.awaitUntil); }
1055    public void testSignalAll(final AwaitMethod awaitMethod) {
1056        final Mutex sync = new Mutex();
1057        final ConditionObject c = sync.newCondition();
1058        final BooleanLatch acquired1 = new BooleanLatch();
1059        final BooleanLatch acquired2 = new BooleanLatch();
1060        Thread t1 = newStartedThread(new CheckedRunnable() {
1061            public void realRun() throws InterruptedException {
1062                sync.acquire();
1063                acquired1.releaseShared(0);
1064                await(c, awaitMethod);
1065                sync.release();
1066            }});
1067
1068        Thread t2 = newStartedThread(new CheckedRunnable() {
1069            public void realRun() throws InterruptedException {
1070                sync.acquire();
1071                acquired2.releaseShared(0);
1072                await(c, awaitMethod);
1073                sync.release();
1074            }});
1075
1076        acquired1.acquireShared(0);
1077        acquired2.acquireShared(0);
1078        sync.acquire();
1079        assertHasWaitersLocked(sync, c, t1, t2);
1080        assertHasExclusiveQueuedThreads(sync, NO_THREADS);
1081        c.signalAll();
1082        assertHasWaitersLocked(sync, c, NO_THREADS);
1083        assertHasExclusiveQueuedThreads(sync, t1, t2);
1084        sync.release();
1085        awaitTermination(t1);
1086        awaitTermination(t2);
1087    }
1088
1089    /**
1090     * toString indicates current state
1091     */
1092    public void testToString() {
1093        Mutex sync = new Mutex();
1094        assertTrue(sync.toString().contains("State = " + Mutex.UNLOCKED));
1095        sync.acquire();
1096        assertTrue(sync.toString().contains("State = " + Mutex.LOCKED));
1097    }
1098
1099    /**
1100     * A serialized AQS deserializes with current state, but no queued threads
1101     */
1102    public void testSerialization() {
1103        Mutex sync = new Mutex();
1104        assertFalse(serialClone(sync).isHeldExclusively());
1105        sync.acquire();
1106        Thread t = newStartedThread(new InterruptedSyncRunnable(sync));
1107        waitForQueuedThread(sync, t);
1108        assertTrue(sync.isHeldExclusively());
1109
1110        Mutex clone = serialClone(sync);
1111        assertTrue(clone.isHeldExclusively());
1112        assertHasExclusiveQueuedThreads(sync, t);
1113        assertHasExclusiveQueuedThreads(clone, NO_THREADS);
1114        t.interrupt();
1115        awaitTermination(t);
1116        sync.release();
1117        assertFalse(sync.isHeldExclusively());
1118        assertTrue(clone.isHeldExclusively());
1119        assertHasExclusiveQueuedThreads(sync, NO_THREADS);
1120        assertHasExclusiveQueuedThreads(clone, NO_THREADS);
1121    }
1122
1123    /**
1124     * tryReleaseShared setting state changes getState
1125     */
1126    public void testGetStateWithReleaseShared() {
1127        final BooleanLatch l = new BooleanLatch();
1128        assertFalse(l.isSignalled());
1129        assertTrue(l.releaseShared(0));
1130        assertTrue(l.isSignalled());
1131    }
1132
1133    /**
1134     * releaseShared has no effect when already signalled
1135     */
1136    public void testReleaseShared() {
1137        final BooleanLatch l = new BooleanLatch();
1138        assertFalse(l.isSignalled());
1139        assertTrue(l.releaseShared(0));
1140        assertTrue(l.isSignalled());
1141        assertTrue(l.releaseShared(0));
1142        assertTrue(l.isSignalled());
1143    }
1144
1145    /**
1146     * acquireSharedInterruptibly returns after release, but not before
1147     */
1148    public void testAcquireSharedInterruptibly() {
1149        final BooleanLatch l = new BooleanLatch();
1150
1151        Thread t = newStartedThread(new CheckedRunnable() {
1152            public void realRun() throws InterruptedException {
1153                assertFalse(l.isSignalled());
1154                l.acquireSharedInterruptibly(0);
1155                assertTrue(l.isSignalled());
1156                l.acquireSharedInterruptibly(0);
1157                assertTrue(l.isSignalled());
1158            }});
1159
1160        waitForQueuedThread(l, t);
1161        assertFalse(l.isSignalled());
1162        assertThreadBlocks(t, Thread.State.WAITING);
1163        assertHasSharedQueuedThreads(l, t);
1164        assertTrue(l.releaseShared(0));
1165        assertTrue(l.isSignalled());
1166        awaitTermination(t);
1167    }
1168
1169    /**
1170     * tryAcquireSharedNanos returns after release, but not before
1171     */
1172    public void testTryAcquireSharedNanos() {
1173        final BooleanLatch l = new BooleanLatch();
1174
1175        Thread t = newStartedThread(new CheckedRunnable() {
1176            public void realRun() throws InterruptedException {
1177                assertFalse(l.isSignalled());
1178                long nanos = MILLISECONDS.toNanos(2 * LONG_DELAY_MS);
1179                assertTrue(l.tryAcquireSharedNanos(0, nanos));
1180                assertTrue(l.isSignalled());
1181                assertTrue(l.tryAcquireSharedNanos(0, nanos));
1182                assertTrue(l.isSignalled());
1183            }});
1184
1185        waitForQueuedThread(l, t);
1186        assertFalse(l.isSignalled());
1187        assertThreadBlocks(t, Thread.State.TIMED_WAITING);
1188        assertTrue(l.releaseShared(0));
1189        assertTrue(l.isSignalled());
1190        awaitTermination(t);
1191    }
1192
1193    /**
1194     * acquireSharedInterruptibly is interruptible
1195     */
1196    public void testAcquireSharedInterruptibly_Interruptible() {
1197        final BooleanLatch l = new BooleanLatch();
1198        Thread t = newStartedThread(new CheckedInterruptedRunnable() {
1199            public void realRun() throws InterruptedException {
1200                assertFalse(l.isSignalled());
1201                l.acquireSharedInterruptibly(0);
1202            }});
1203
1204        waitForQueuedThread(l, t);
1205        assertFalse(l.isSignalled());
1206        t.interrupt();
1207        awaitTermination(t);
1208        assertFalse(l.isSignalled());
1209    }
1210
1211    /**
1212     * tryAcquireSharedNanos is interruptible
1213     */
1214    public void testTryAcquireSharedNanos_Interruptible() {
1215        final BooleanLatch l = new BooleanLatch();
1216        Thread t = newStartedThread(new CheckedInterruptedRunnable() {
1217            public void realRun() throws InterruptedException {
1218                assertFalse(l.isSignalled());
1219                long nanos = MILLISECONDS.toNanos(2 * LONG_DELAY_MS);
1220                l.tryAcquireSharedNanos(0, nanos);
1221            }});
1222
1223        waitForQueuedThread(l, t);
1224        assertFalse(l.isSignalled());
1225        t.interrupt();
1226        awaitTermination(t);
1227        assertFalse(l.isSignalled());
1228    }
1229
1230    /**
1231     * tryAcquireSharedNanos times out if not released before timeout
1232     */
1233    public void testTryAcquireSharedNanos_Timeout() {
1234        final BooleanLatch l = new BooleanLatch();
1235        final BooleanLatch observedQueued = new BooleanLatch();
1236        Thread t = newStartedThread(new CheckedRunnable() {
1237            public void realRun() throws InterruptedException {
1238                assertFalse(l.isSignalled());
1239                for (long millis = timeoutMillis();
1240                     !observedQueued.isSignalled();
1241                     millis *= 2) {
1242                    long nanos = MILLISECONDS.toNanos(millis);
1243                    long startTime = System.nanoTime();
1244                    assertFalse(l.tryAcquireSharedNanos(0, nanos));
1245                    assertTrue(millisElapsedSince(startTime) >= millis);
1246                }
1247                assertFalse(l.isSignalled());
1248            }});
1249
1250        waitForQueuedThread(l, t);
1251        observedQueued.releaseShared(0);
1252        assertFalse(l.isSignalled());
1253        awaitTermination(t);
1254        assertFalse(l.isSignalled());
1255    }
1256
1257    /**
1258     * awaitNanos/timed await with 0 wait times out immediately
1259     */
1260    public void testAwait_Zero() throws InterruptedException {
1261        final Mutex sync = new Mutex();
1262        final ConditionObject c = sync.newCondition();
1263        sync.acquire();
1264        assertTrue(c.awaitNanos(0L) <= 0);
1265        assertFalse(c.await(0L, NANOSECONDS));
1266        sync.release();
1267    }
1268
1269    /**
1270     * awaitNanos/timed await with maximum negative wait times does not underflow
1271     */
1272    public void testAwait_NegativeInfinity() throws InterruptedException {
1273        final Mutex sync = new Mutex();
1274        final ConditionObject c = sync.newCondition();
1275        sync.acquire();
1276        assertTrue(c.awaitNanos(Long.MIN_VALUE) <= 0);
1277        assertFalse(c.await(Long.MIN_VALUE, NANOSECONDS));
1278        sync.release();
1279    }
1280
1281}
1282