1 /*
2  * Copyright (C) 2017 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 import java.lang.Thread.State;
18 import java.lang.reflect.Method;
19 import java.util.Arrays;
20 import java.util.LinkedList;
21 import java.util.List;
22 import java.util.Map;
23 import java.util.concurrent.BrokenBarrierException;
24 import java.util.concurrent.CyclicBarrier;
25 
26 public class Main {
27 
28     static class Runner implements Runnable {
29         List<Object> locks;
30         List<CyclicBarrier> barriers;
31 
Runner(List<Object> locks, List<CyclicBarrier> barriers)32         public Runner(List<Object> locks, List<CyclicBarrier> barriers) {
33             this.locks = locks;
34             this.barriers = barriers;
35         }
36 
37         @Override
run()38         public void run() {
39             step(locks, barriers);
40         }
41 
step(List<Object> l, List<CyclicBarrier> b)42         private void step(List<Object> l, List<CyclicBarrier> b) {
43             if (l.isEmpty()) {
44                 // Nothing to do, sleep indefinitely.
45                 try {
46                     Thread.sleep(100000000);
47                 } catch (InterruptedException e) {
48                     throw new RuntimeException(e);
49                 }
50             } else {
51                 Object lockObject = l.remove(0);
52                 CyclicBarrier barrierObject = b.remove(0);
53 
54                 if (lockObject == null) {
55                     // No lock object: only take barrier, recurse.
56                     try {
57                         barrierObject.await();
58                     } catch (InterruptedException | BrokenBarrierException e) {
59                         throw new RuntimeException(e);
60                     }
61                     step(l, b);
62                 } else if (barrierObject != null) {
63                     // Have barrier: sync, wait and recurse.
64                     synchronized(lockObject) {
65                         try {
66                             barrierObject.await();
67                         } catch (InterruptedException | BrokenBarrierException e) {
68                             throw new RuntimeException(e);
69                         }
70                         step(l, b);
71                     }
72                 } else {
73                     // Sync, and get next step (which is assumed to have object and barrier).
74                     synchronized (lockObject) {
75                         Object lockObject2 = l.remove(0);
76                         CyclicBarrier barrierObject2 = b.remove(0);
77                         synchronized(lockObject2) {
78                             try {
79                                 barrierObject2.await();
80                             } catch (InterruptedException | BrokenBarrierException e) {
81                                 throw new RuntimeException(e);
82                             }
83                             step(l, b);
84                         }
85                     }
86                 }
87             }
88         }
89     }
90 
main(String[] args)91     public static void main(String[] args) throws Exception {
92         try {
93             testCluster1();
94         } catch (Exception e) {
95             Map<Thread,StackTraceElement[]> stacks = Thread.getAllStackTraces();
96             for (Map.Entry<Thread,StackTraceElement[]> entry : stacks.entrySet()) {
97                 System.out.println(entry.getKey());
98                 System.out.println(Arrays.toString(entry.getValue()));
99             }
100             throw e;
101         }
102     }
103 
testCluster1()104     private static void testCluster1() throws Exception {
105         // Test setup (at deadlock):
106         //
107         // Thread 1:
108         //   #0 step: synchornized(o3) { synchronized(o2) }
109         //   #1 step: synchronized(o1)
110         //
111         // Thread 2:
112         //   #0 step: synchronized(o1)
113         //   #1 step: synchronized(o4) { synchronized(o2) }
114         //
115         LinkedList<Object> l1 = new LinkedList<>();
116         LinkedList<CyclicBarrier> b1 = new LinkedList<>();
117         LinkedList<Object> l2 = new LinkedList<>();
118         LinkedList<CyclicBarrier> b2 = new LinkedList<>();
119 
120         Object o1 = new Object();
121         Object o2 = new Object();
122         Object o3 = new Object();
123         Object o4 = new Object();
124 
125         l1.add(o1);
126         l1.add(o3);
127         l1.add(o2);
128         l2.add(o4);
129         l2.add(o2);
130         l2.add(o1);
131 
132         CyclicBarrier c1 = new CyclicBarrier(3);
133         CyclicBarrier c2 = new CyclicBarrier(2);
134         b1.add(c1);
135         b1.add(null);
136         b1.add(c2);
137         b2.add(null);
138         b2.add(c1);
139         b2.add(c2);
140 
141         Thread t1 = new Thread(new Runner(l1, b1));
142         t1.setDaemon(true);
143         t1.start();
144         Thread t2 = new Thread(new Runner(l2, b2));
145         t2.setDaemon(true);
146         t2.start();
147 
148         c1.await();
149 
150         waitNotRunnable(t1);
151         waitNotRunnable(t2);
152         Thread.sleep(250);    // Unfortunately this seems necessary. :-(
153 
154         // Thread 1.
155         {
156             Object[] stack1 = getAnnotatedStack(t1);
157             assertBlockedOn(stack1[0], o2);              // Blocked on o2.
158             assertLocks(stack1[0], o3);                  // Locked o3.
159             assertStackTraceElementStep(stack1[0]);
160 
161             assertBlockedOn(stack1[1], null);            // Frame can't be blocked.
162             assertLocks(stack1[1], o1);                  // Locked o1.
163             assertStackTraceElementStep(stack1[1]);
164         }
165 
166         // Thread 2.
167         {
168             Object[] stack2 = getAnnotatedStack(t2);
169             assertBlockedOn(stack2[0], o1);              // Blocked on o1.
170             assertLocks(stack2[0]);                      // Nothing locked.
171             assertStackTraceElementStep(stack2[0]);
172 
173             assertBlockedOn(stack2[1], null);            // Frame can't be blocked.
174             assertLocks(stack2[1], o4, o2);              // Locked o4, o2.
175             assertStackTraceElementStep(stack2[1]);
176         }
177     }
178 
waitNotRunnable(Thread t)179     private static void waitNotRunnable(Thread t) throws InterruptedException {
180         while (t.getState() == State.RUNNABLE) {
181             Thread.sleep(100);
182         }
183     }
184 
getAnnotatedStack(Thread t)185     private static Object[] getAnnotatedStack(Thread t) throws Exception {
186         Class<?> vmStack = Class.forName("dalvik.system.VMStack");
187         Method m = vmStack.getDeclaredMethod("getAnnotatedThreadStackTrace", Thread.class);
188         return (Object[]) m.invoke(null, t);
189     }
190 
assertEquals(Object o1, Object o2)191     private static void assertEquals(Object o1, Object o2) {
192         if (o1 != o2) {
193             throw new RuntimeException("Expected " + o1 + " == " + o2);
194         }
195     }
assertLocks(Object fromTrace, Object... locks)196     private static void assertLocks(Object fromTrace, Object... locks) throws Exception {
197         Object fieldValue = fromTrace.getClass().getDeclaredMethod("getHeldLocks").
198                 invoke(fromTrace);
199         assertEquals((Object[]) fieldValue,
200                 (locks == null) ? null : (locks.length == 0 ? null : locks));
201     }
assertBlockedOn(Object fromTrace, Object block)202     private static void assertBlockedOn(Object fromTrace, Object block) throws Exception {
203         Object fieldValue = fromTrace.getClass().getDeclaredMethod("getBlockedOn").
204                 invoke(fromTrace);
205         assertEquals(fieldValue, block);
206     }
assertEquals(Object[] o1, Object[] o2)207     private static void assertEquals(Object[] o1, Object[] o2) {
208         if (!Arrays.equals(o1, o2)) {
209             throw new RuntimeException(
210                     "Expected " + Arrays.toString(o1) + " == " + Arrays.toString(o2));
211         }
212     }
assertStackTraceElementStep(Object o)213     private static void assertStackTraceElementStep(Object o) throws Exception {
214         Object fieldValue = o.getClass().getDeclaredMethod("getStackTraceElement").invoke(o);
215         if (fieldValue instanceof StackTraceElement) {
216             StackTraceElement elem = (StackTraceElement) fieldValue;
217             if (!elem.getMethodName().equals("step")) {
218                 throw new RuntimeException("Expected step method");
219             }
220             return;
221         }
222         throw new RuntimeException("Expected StackTraceElement " + fieldValue + " / " + o);
223     }
224 }
225 
226