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