/*
|
* Copyright (C) 2017 The Android Open Source Project
|
*
|
* Licensed under the Apache License, Version 2.0 (the "License");
|
* you may not use this file except in compliance with the License.
|
* You may obtain a copy of the License at
|
*
|
* http://www.apache.org/licenses/LICENSE-2.0
|
*
|
* Unless required by applicable law or agreed to in writing, software
|
* distributed under the License is distributed on an "AS IS" BASIS,
|
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
* See the License for the specific language governing permissions and
|
* limitations under the License.
|
*/
|
|
import java.lang.Thread.State;
|
import java.lang.reflect.Method;
|
import java.util.Arrays;
|
import java.util.LinkedList;
|
import java.util.List;
|
import java.util.Map;
|
import java.util.concurrent.BrokenBarrierException;
|
import java.util.concurrent.CyclicBarrier;
|
|
public class Main {
|
|
static class Runner implements Runnable {
|
List<Object> locks;
|
List<CyclicBarrier> barriers;
|
|
public Runner(List<Object> locks, List<CyclicBarrier> barriers) {
|
this.locks = locks;
|
this.barriers = barriers;
|
}
|
|
@Override
|
public void run() {
|
step(locks, barriers);
|
}
|
|
private void step(List<Object> l, List<CyclicBarrier> b) {
|
if (l.isEmpty()) {
|
// Nothing to do, sleep indefinitely.
|
try {
|
Thread.sleep(100000000);
|
} catch (InterruptedException e) {
|
throw new RuntimeException(e);
|
}
|
} else {
|
Object lockObject = l.remove(0);
|
CyclicBarrier barrierObject = b.remove(0);
|
|
if (lockObject == null) {
|
// No lock object: only take barrier, recurse.
|
try {
|
barrierObject.await();
|
} catch (InterruptedException | BrokenBarrierException e) {
|
throw new RuntimeException(e);
|
}
|
step(l, b);
|
} else if (barrierObject != null) {
|
// Have barrier: sync, wait and recurse.
|
synchronized(lockObject) {
|
try {
|
barrierObject.await();
|
} catch (InterruptedException | BrokenBarrierException e) {
|
throw new RuntimeException(e);
|
}
|
step(l, b);
|
}
|
} else {
|
// Sync, and get next step (which is assumed to have object and barrier).
|
synchronized (lockObject) {
|
Object lockObject2 = l.remove(0);
|
CyclicBarrier barrierObject2 = b.remove(0);
|
synchronized(lockObject2) {
|
try {
|
barrierObject2.await();
|
} catch (InterruptedException | BrokenBarrierException e) {
|
throw new RuntimeException(e);
|
}
|
step(l, b);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
public static void main(String[] args) throws Exception {
|
try {
|
testCluster1();
|
} catch (Exception e) {
|
Map<Thread,StackTraceElement[]> stacks = Thread.getAllStackTraces();
|
for (Map.Entry<Thread,StackTraceElement[]> entry : stacks.entrySet()) {
|
System.out.println(entry.getKey());
|
System.out.println(Arrays.toString(entry.getValue()));
|
}
|
throw e;
|
}
|
}
|
|
private static void testCluster1() throws Exception {
|
// Test setup (at deadlock):
|
//
|
// Thread 1:
|
// #0 step: synchornized(o3) { synchronized(o2) }
|
// #1 step: synchronized(o1)
|
//
|
// Thread 2:
|
// #0 step: synchronized(o1)
|
// #1 step: synchronized(o4) { synchronized(o2) }
|
//
|
LinkedList<Object> l1 = new LinkedList<>();
|
LinkedList<CyclicBarrier> b1 = new LinkedList<>();
|
LinkedList<Object> l2 = new LinkedList<>();
|
LinkedList<CyclicBarrier> b2 = new LinkedList<>();
|
|
Object o1 = new Object();
|
Object o2 = new Object();
|
Object o3 = new Object();
|
Object o4 = new Object();
|
|
l1.add(o1);
|
l1.add(o3);
|
l1.add(o2);
|
l2.add(o4);
|
l2.add(o2);
|
l2.add(o1);
|
|
CyclicBarrier c1 = new CyclicBarrier(3);
|
CyclicBarrier c2 = new CyclicBarrier(2);
|
b1.add(c1);
|
b1.add(null);
|
b1.add(c2);
|
b2.add(null);
|
b2.add(c1);
|
b2.add(c2);
|
|
Thread t1 = new Thread(new Runner(l1, b1));
|
t1.setDaemon(true);
|
t1.start();
|
Thread t2 = new Thread(new Runner(l2, b2));
|
t2.setDaemon(true);
|
t2.start();
|
|
c1.await();
|
|
waitNotRunnable(t1);
|
waitNotRunnable(t2);
|
Thread.sleep(250); // Unfortunately this seems necessary. :-(
|
|
// Thread 1.
|
{
|
Object[] stack1 = getAnnotatedStack(t1);
|
assertBlockedOn(stack1[0], o2); // Blocked on o2.
|
assertLocks(stack1[0], o3); // Locked o3.
|
assertStackTraceElementStep(stack1[0]);
|
|
assertBlockedOn(stack1[1], null); // Frame can't be blocked.
|
assertLocks(stack1[1], o1); // Locked o1.
|
assertStackTraceElementStep(stack1[1]);
|
}
|
|
// Thread 2.
|
{
|
Object[] stack2 = getAnnotatedStack(t2);
|
assertBlockedOn(stack2[0], o1); // Blocked on o1.
|
assertLocks(stack2[0]); // Nothing locked.
|
assertStackTraceElementStep(stack2[0]);
|
|
assertBlockedOn(stack2[1], null); // Frame can't be blocked.
|
assertLocks(stack2[1], o4, o2); // Locked o4, o2.
|
assertStackTraceElementStep(stack2[1]);
|
}
|
}
|
|
private static void waitNotRunnable(Thread t) throws InterruptedException {
|
while (t.getState() == State.RUNNABLE) {
|
Thread.sleep(100);
|
}
|
}
|
|
private static Object[] getAnnotatedStack(Thread t) throws Exception {
|
Class<?> vmStack = Class.forName("dalvik.system.VMStack");
|
Method m = vmStack.getDeclaredMethod("getAnnotatedThreadStackTrace", Thread.class);
|
return (Object[]) m.invoke(null, t);
|
}
|
|
private static void assertEquals(Object o1, Object o2) {
|
if (o1 != o2) {
|
throw new RuntimeException("Expected " + o1 + " == " + o2);
|
}
|
}
|
private static void assertLocks(Object fromTrace, Object... locks) throws Exception {
|
Object fieldValue = fromTrace.getClass().getDeclaredMethod("getHeldLocks").
|
invoke(fromTrace);
|
assertEquals((Object[]) fieldValue,
|
(locks == null) ? null : (locks.length == 0 ? null : locks));
|
}
|
private static void assertBlockedOn(Object fromTrace, Object block) throws Exception {
|
Object fieldValue = fromTrace.getClass().getDeclaredMethod("getBlockedOn").
|
invoke(fromTrace);
|
assertEquals(fieldValue, block);
|
}
|
private static void assertEquals(Object[] o1, Object[] o2) {
|
if (!Arrays.equals(o1, o2)) {
|
throw new RuntimeException(
|
"Expected " + Arrays.toString(o1) + " == " + Arrays.toString(o2));
|
}
|
}
|
private static void assertStackTraceElementStep(Object o) throws Exception {
|
Object fieldValue = o.getClass().getDeclaredMethod("getStackTraceElement").invoke(o);
|
if (fieldValue instanceof StackTraceElement) {
|
StackTraceElement elem = (StackTraceElement) fieldValue;
|
if (!elem.getMethodName().equals("step")) {
|
throw new RuntimeException("Expected step method");
|
}
|
return;
|
}
|
throw new RuntimeException("Expected StackTraceElement " + fieldValue + " / " + o);
|
}
|
}
|
