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