13d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey/* 23d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * Copyright (C) 2016 The Android Open Source Project 33d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * 43d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * Licensed under the Apache License, Version 2.0 (the "License"); 53d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * you may not use this file except in compliance with the License. 63d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * You may obtain a copy of the License at 73d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * 83d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * http://www.apache.org/licenses/LICENSE-2.0 93d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * 103d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * Unless required by applicable law or agreed to in writing, software 113d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * distributed under the License is distributed on an "AS IS" BASIS, 123d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 133d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * See the License for the specific language governing permissions and 143d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * limitations under the License. 153d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey */ 163d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey 173d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkeypackage com.android.server; 183d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey 193d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkeyimport android.util.ArrayMap; 203d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkeyimport android.util.ArraySet; 213d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkeyimport android.util.Slog; 223d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey 233d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkeyimport java.io.FileDescriptor; 243d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkeyimport java.io.PrintWriter; 253d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey 263d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey/** 273d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * LockGuard is a mechanism to help detect lock inversions inside the system 283d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * server. It works by requiring each lock acquisition site to follow this 293d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * pattern: 303d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * 313d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * <pre> 323d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * synchronized (LockGuard.guard(lock)) { 333d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * } 343d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * </pre> 353d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * 363d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * <pre> 373d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * $ find services/ -name "*.java" -exec sed -i -r \ 383d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * 's/synchronized.?\((.+?)\)/synchronized \(com.android.server.LockGuard.guard\(\1\)\)/' {} \; 393d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * </pre> 403d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * 413d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * The {@link #guard(Object)} method internally verifies that all locking is 423d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * done in a consistent order, and will log if any inversion is detected. For 433d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * example, if the calling thread is trying to acquire the 443d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * {@code ActivityManager} lock while holding the {@code PackageManager} lock, 453d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * it will yell. 463d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * <p> 473d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * This class requires no prior knowledge of locks or their ordering; it derives 483d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * all of this data at runtime. However, this means the overhead is 493d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * <em>substantial</em> and it should not be enabled by default. For example, 503d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * here are some benchmarked timings: 513d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * <ul> 523d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * <li>An unguarded synchronized block takes 40ns. 533d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * <li>A guarded synchronized block takes 50ns when disabled. 543d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * <li>A guarded synchronized block takes 460ns per lock checked when enabled. 553d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * </ul> 563d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey */ 573d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkeypublic class LockGuard { 583d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey private static final String TAG = "LockGuard"; 593d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey 603d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey private static ArrayMap<Object, LockInfo> sKnown = new ArrayMap<>(0, true); 613d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey 623d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey private static class LockInfo { 633d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey /** Friendly label to describe this lock */ 643d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey public String label; 653d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey 663d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey /** Child locks that can be acquired while this lock is already held */ 673d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey public ArraySet<Object> children = new ArraySet<>(0, true); 683d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey } 693d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey 703d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey private static LockInfo findOrCreateLockInfo(Object lock) { 713d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey LockInfo info = sKnown.get(lock); 723d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey if (info == null) { 733d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey info = new LockInfo(); 743d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey info.label = "0x" + Integer.toHexString(System.identityHashCode(lock)) + " [" 753d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey + new Throwable().getStackTrace()[2].toString() + "]"; 763d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey sKnown.put(lock, info); 773d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey } 783d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey return info; 793d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey } 803d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey 813d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey /** 823d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * Check if the calling thread is holding any locks in an inverted order. 833d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * 843d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * @param lock The lock the calling thread is attempting to acquire. 853d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey */ 863d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey public static Object guard(Object lock) { 873d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey // If we already hold this lock, ignore 883d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey if (lock == null || Thread.holdsLock(lock)) return lock; 893d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey 903d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey // Check to see if we're already holding any child locks 913d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey boolean triggered = false; 923d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey final LockInfo info = findOrCreateLockInfo(lock); 933d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey for (int i = 0; i < info.children.size(); i++) { 943d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey final Object child = info.children.valueAt(i); 953d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey if (child == null) continue; 963d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey 973d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey if (Thread.holdsLock(child)) { 983d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey Slog.w(TAG, "Calling thread " + Thread.currentThread().getName() + " is holding " 993d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey + lockToString(child) + " while trying to acquire " 1003d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey + lockToString(lock), new Throwable()); 1013d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey triggered = true; 1023d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey } 1033d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey } 1043d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey 1053d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey if (!triggered) { 1063d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey // If no trouble found above, record this lock as being a valid 1073d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey // child of all locks currently being held 1083d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey for (int i = 0; i < sKnown.size(); i++) { 1093d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey final Object test = sKnown.keyAt(i); 1103d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey if (test == null || test == lock) continue; 1113d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey 1123d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey if (Thread.holdsLock(test)) { 1133d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey sKnown.valueAt(i).children.add(lock); 1143d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey } 1153d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey } 1163d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey } 1173d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey 1183d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey return lock; 1193d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey } 1203d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey 1213d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey /** 1223d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey * Report the given lock with a well-known label. 1233d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey */ 1243d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey public static void installLock(Object lock, String label) { 1253d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey final LockInfo info = findOrCreateLockInfo(lock); 1263d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey info.label = label; 1273d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey } 1283d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey 1293d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey private static String lockToString(Object lock) { 1303d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey final LockInfo info = sKnown.get(lock); 1313d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey if (info != null) { 1323d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey return info.label; 1333d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey } else { 1343d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey return "0x" + Integer.toHexString(System.identityHashCode(lock)); 1353d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey } 1363d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey } 1373d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey 1383d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey public static void dump(FileDescriptor fd, PrintWriter pw, String[] args) { 1393d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey for (int i = 0; i < sKnown.size(); i++) { 1403d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey final Object lock = sKnown.keyAt(i); 1413d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey final LockInfo info = sKnown.valueAt(i); 1423d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey pw.println("Lock " + lockToString(lock) + ":"); 1433d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey for (int j = 0; j < info.children.size(); j++) { 1443d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey pw.println(" Child " + lockToString(info.children.valueAt(j))); 1453d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey } 1463d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey pw.println(); 1473d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey } 1483d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey } 1493d1cb6a2b6882a9b702fc97aa50b2d5779956492Jeff Sharkey} 150