Utility to detect lock inversions in system.
This change adds a new LockGuard utility class that can be used to
detect lock inversions across the system server. For example, if a
thread is trying to acquire the ActivityManager lock while holding the
PackageManager lock, it will yell.
This class requires no prior knowledge of locks or their ordering; it
derives all of this data at runtime. However, this means the overhead
is substantial and it should not be enabled by default.
Adds overrides to ArrayMap and ArraySet to use identityHashCode()
instead of the hashCode() provided by the object.
Bug: 27336728
Change-Id: I26c31bc99fe8d61ff13c3455aaeddd5517e44433
diff --git a/core/java/android/util/ArrayMap.java b/core/java/android/util/ArrayMap.java
index bdb1fdc..92a5803 100644
--- a/core/java/android/util/ArrayMap.java
+++ b/core/java/android/util/ArrayMap.java
@@ -67,7 +67,7 @@
/**
* @hide Special immutable empty ArrayMap.
*/
- public static final ArrayMap EMPTY = new ArrayMap(true);
+ public static final ArrayMap EMPTY = new ArrayMap<>(-1);
/**
* Caches of small array objects to avoid spamming garbage. The cache
@@ -80,6 +80,7 @@
static Object[] mTwiceBaseCache;
static int mTwiceBaseCacheSize;
+ final boolean mIdentityHashCode;
int[] mHashes;
Object[] mArray;
int mSize;
@@ -236,16 +237,27 @@
* will grow once items are added to it.
*/
public ArrayMap() {
- mHashes = EmptyArray.INT;
- mArray = EmptyArray.OBJECT;
- mSize = 0;
+ this(0, false);
}
/**
* Create a new ArrayMap with a given initial capacity.
*/
public ArrayMap(int capacity) {
- if (capacity == 0) {
+ this(capacity, false);
+ }
+
+ /** {@hide} */
+ public ArrayMap(int capacity, boolean identityHashCode) {
+ mIdentityHashCode = identityHashCode;
+
+ // If this is immutable, use the sentinal EMPTY_IMMUTABLE_INTS
+ // instance instead of the usual EmptyArray.INT. The reference
+ // is checked later to see if the array is allowed to grow.
+ if (capacity < 0) {
+ mHashes = EMPTY_IMMUTABLE_INTS;
+ mArray = EmptyArray.OBJECT;
+ } else if (capacity == 0) {
mHashes = EmptyArray.INT;
mArray = EmptyArray.OBJECT;
} else {
@@ -254,15 +266,6 @@
mSize = 0;
}
- private ArrayMap(boolean immutable) {
- // If this is immutable, use the sentinal EMPTY_IMMUTABLE_INTS
- // instance instead of the usual EmptyArray.INT. The reference
- // is checked later to see if the array is allowed to grow.
- mHashes = immutable ? EMPTY_IMMUTABLE_INTS : EmptyArray.INT;
- mArray = EmptyArray.OBJECT;
- mSize = 0;
- }
-
/**
* Create a new ArrayMap with the mappings from the given ArrayMap.
*/
@@ -336,7 +339,8 @@
* @return Returns the index of the key if it exists, else a negative integer.
*/
public int indexOfKey(Object key) {
- return key == null ? indexOfNull() : indexOf(key, key.hashCode());
+ return key == null ? indexOfNull()
+ : indexOf(key, mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
}
int indexOfValue(Object value) {
@@ -437,7 +441,7 @@
hash = 0;
index = indexOfNull();
} else {
- hash = key.hashCode();
+ hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
index = indexOf(key, hash);
}
if (index >= 0) {
@@ -488,7 +492,8 @@
*/
public void append(K key, V value) {
int index = mSize;
- final int hash = key == null ? 0 : key.hashCode();
+ final int hash = key == null ? 0
+ : (mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
if (index >= mHashes.length) {
throw new IllegalStateException("Array is full");
}
diff --git a/core/java/android/util/ArraySet.java b/core/java/android/util/ArraySet.java
index b7a3c42..9e9314f 100644
--- a/core/java/android/util/ArraySet.java
+++ b/core/java/android/util/ArraySet.java
@@ -69,6 +69,7 @@
static Object[] mTwiceBaseCache;
static int mTwiceBaseCacheSize;
+ final boolean mIdentityHashCode;
int[] mHashes;
Object[] mArray;
int mSize;
@@ -222,15 +223,19 @@
* will grow once items are added to it.
*/
public ArraySet() {
- mHashes = EmptyArray.INT;
- mArray = EmptyArray.OBJECT;
- mSize = 0;
+ this(0, false);
}
/**
* Create a new ArraySet with a given initial capacity.
*/
public ArraySet(int capacity) {
+ this(capacity, false);
+ }
+
+ /** {@hide} */
+ public ArraySet(int capacity, boolean identityHashCode) {
+ mIdentityHashCode = identityHashCode;
if (capacity == 0) {
mHashes = EmptyArray.INT;
mArray = EmptyArray.OBJECT;
@@ -306,7 +311,8 @@
* @return Returns the index of the value if it exists, else a negative integer.
*/
public int indexOf(Object key) {
- return key == null ? indexOfNull() : indexOf(key, key.hashCode());
+ return key == null ? indexOfNull()
+ : indexOf(key, mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
}
/**
@@ -343,7 +349,7 @@
hash = 0;
index = indexOfNull();
} else {
- hash = value.hashCode();
+ hash = mIdentityHashCode ? System.identityHashCode(value) : value.hashCode();
index = indexOf(value, hash);
}
if (index >= 0) {
diff --git a/services/core/java/com/android/server/LockGuard.java b/services/core/java/com/android/server/LockGuard.java
new file mode 100644
index 0000000..3a381ae
--- /dev/null
+++ b/services/core/java/com/android/server/LockGuard.java
@@ -0,0 +1,149 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+package com.android.server;
+
+import android.util.ArrayMap;
+import android.util.ArraySet;
+import android.util.Slog;
+
+import java.io.FileDescriptor;
+import java.io.PrintWriter;
+
+/**
+ * LockGuard is a mechanism to help detect lock inversions inside the system
+ * server. It works by requiring each lock acquisition site to follow this
+ * pattern:
+ *
+ * <pre>
+ * synchronized (LockGuard.guard(lock)) {
+ * }
+ * </pre>
+ *
+ * <pre>
+ * $ find services/ -name "*.java" -exec sed -i -r \
+ * 's/synchronized.?\((.+?)\)/synchronized \(com.android.server.LockGuard.guard\(\1\)\)/' {} \;
+ * </pre>
+ *
+ * The {@link #guard(Object)} method internally verifies that all locking is
+ * done in a consistent order, and will log if any inversion is detected. For
+ * example, if the calling thread is trying to acquire the
+ * {@code ActivityManager} lock while holding the {@code PackageManager} lock,
+ * it will yell.
+ * <p>
+ * This class requires no prior knowledge of locks or their ordering; it derives
+ * all of this data at runtime. However, this means the overhead is
+ * <em>substantial</em> and it should not be enabled by default. For example,
+ * here are some benchmarked timings:
+ * <ul>
+ * <li>An unguarded synchronized block takes 40ns.
+ * <li>A guarded synchronized block takes 50ns when disabled.
+ * <li>A guarded synchronized block takes 460ns per lock checked when enabled.
+ * </ul>
+ */
+public class LockGuard {
+ private static final String TAG = "LockGuard";
+
+ private static ArrayMap<Object, LockInfo> sKnown = new ArrayMap<>(0, true);
+
+ private static class LockInfo {
+ /** Friendly label to describe this lock */
+ public String label;
+
+ /** Child locks that can be acquired while this lock is already held */
+ public ArraySet<Object> children = new ArraySet<>(0, true);
+ }
+
+ private static LockInfo findOrCreateLockInfo(Object lock) {
+ LockInfo info = sKnown.get(lock);
+ if (info == null) {
+ info = new LockInfo();
+ info.label = "0x" + Integer.toHexString(System.identityHashCode(lock)) + " ["
+ + new Throwable().getStackTrace()[2].toString() + "]";
+ sKnown.put(lock, info);
+ }
+ return info;
+ }
+
+ /**
+ * Check if the calling thread is holding any locks in an inverted order.
+ *
+ * @param lock The lock the calling thread is attempting to acquire.
+ */
+ public static Object guard(Object lock) {
+ // If we already hold this lock, ignore
+ if (lock == null || Thread.holdsLock(lock)) return lock;
+
+ // Check to see if we're already holding any child locks
+ boolean triggered = false;
+ final LockInfo info = findOrCreateLockInfo(lock);
+ for (int i = 0; i < info.children.size(); i++) {
+ final Object child = info.children.valueAt(i);
+ if (child == null) continue;
+
+ if (Thread.holdsLock(child)) {
+ Slog.w(TAG, "Calling thread " + Thread.currentThread().getName() + " is holding "
+ + lockToString(child) + " while trying to acquire "
+ + lockToString(lock), new Throwable());
+ triggered = true;
+ }
+ }
+
+ if (!triggered) {
+ // If no trouble found above, record this lock as being a valid
+ // child of all locks currently being held
+ for (int i = 0; i < sKnown.size(); i++) {
+ final Object test = sKnown.keyAt(i);
+ if (test == null || test == lock) continue;
+
+ if (Thread.holdsLock(test)) {
+ sKnown.valueAt(i).children.add(lock);
+ }
+ }
+ }
+
+ return lock;
+ }
+
+ /**
+ * Report the given lock with a well-known label.
+ */
+ public static void installLock(Object lock, String label) {
+ final LockInfo info = findOrCreateLockInfo(lock);
+ info.label = label;
+ }
+
+ private static String lockToString(Object lock) {
+ final LockInfo info = sKnown.get(lock);
+ if (info != null) {
+ return info.label;
+ } else {
+ return "0x" + Integer.toHexString(System.identityHashCode(lock));
+ }
+ }
+
+ public static void dump(FileDescriptor fd, PrintWriter pw, String[] args) {
+ for (int i = 0; i < sKnown.size(); i++) {
+ final Object lock = sKnown.keyAt(i);
+ final LockInfo info = sKnown.valueAt(i);
+ pw.println("Lock " + lockToString(lock) + ":");
+ for (int j = 0; j < info.children.size(); j++) {
+ pw.println(" Child " + lockToString(info.children.valueAt(j)));
+ }
+ pw.println();
+ }
+ }
+}
diff --git a/services/core/java/com/android/server/am/ActivityManagerService.java b/services/core/java/com/android/server/am/ActivityManagerService.java
index 5f40e5c..d7225f6 100644
--- a/services/core/java/com/android/server/am/ActivityManagerService.java
+++ b/services/core/java/com/android/server/am/ActivityManagerService.java
@@ -45,6 +45,7 @@
import com.android.server.DeviceIdleController;
import com.android.server.IntentResolver;
import com.android.server.LocalServices;
+import com.android.server.LockGuard;
import com.android.server.ServiceThread;
import com.android.server.SystemService;
import com.android.server.SystemServiceManager;
@@ -13581,6 +13582,8 @@
synchronized (this) {
mServices.dumpServicesLocked(fd, pw, args, opti, true, dumpClient, dumpPackage);
}
+ } else if ("locks".equals(cmd)) {
+ LockGuard.dump(fd, pw, args);
} else {
// Dumping a single activity?
if (!dumpActivity(fd, pw, cmd, args, opti, dumpAll)) {