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