1 /*
2  * Copyright (C) 2016 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 package com.android.server;
18 
19 import android.annotation.Nullable;
20 import android.text.TextUtils;
21 import android.util.ArrayMap;
22 import android.util.ArraySet;
23 import android.util.Slog;
24 
25 import java.io.FileDescriptor;
26 import java.io.PrintWriter;
27 
28 /**
29  * LockGuard is a mechanism to help detect lock inversions inside the system
30  * server. It works by requiring each lock acquisition site to follow this
31  * pattern:
32  *
33  * <pre>
34  * synchronized (LockGuard.guard(lock)) {
35  * }
36  * </pre>
37  *
38  * <pre>
39  * $ find services/ -name "*.java" -exec sed -i -r \
40  *     's/synchronized.?\((.+?)\)/synchronized \(com.android.server.LockGuard.guard\(\1\)\)/' {} \;
41  * </pre>
42  *
43  * The {@link #guard(Object)} method internally verifies that all locking is
44  * done in a consistent order, and will log if any inversion is detected. For
45  * example, if the calling thread is trying to acquire the
46  * {@code ActivityManager} lock while holding the {@code PackageManager} lock,
47  * it will yell.
48  * <p>
49  * This class requires no prior knowledge of locks or their ordering; it derives
50  * all of this data at runtime. However, this means the overhead is
51  * <em>substantial</em> and it should not be enabled by default. For example,
52  * here are some benchmarked timings:
53  * <ul>
54  * <li>An unguarded synchronized block takes 40ns.
55  * <li>A guarded synchronized block takes 50ns when disabled.
56  * <li>A guarded synchronized block takes 460ns per lock checked when enabled.
57  * </ul>
58  * <p>
59  * This class also supports a second simpler mode of operation where well-known
60  * locks are explicitly registered and checked via indexes.
61  */
62 public class LockGuard {
63     private static final String TAG = "LockGuard";
64 
65     /**
66      * Well-known locks ordered by fixed index. Locks with a specific index
67      * should never be acquired while holding a lock of a lower index.
68      */
69     public static final int INDEX_APP_OPS = 0;
70     public static final int INDEX_POWER = 1;
71     public static final int INDEX_USER = 2;
72     public static final int INDEX_PACKAGES = 3;
73     public static final int INDEX_STORAGE = 4;
74     public static final int INDEX_WINDOW = 5;
75     public static final int INDEX_PROC = 6;
76     public static final int INDEX_ACTIVITY = 7;
77     public static final int INDEX_DPMS = 8;
78 
79     private static Object[] sKnownFixed = new Object[INDEX_DPMS + 1];
80 
81     private static ArrayMap<Object, LockInfo> sKnown = new ArrayMap<>(0, true);
82 
83     private static class LockInfo {
84         /** Friendly label to describe this lock */
85         public String label;
86 
87         /** Child locks that can be acquired while this lock is already held */
88         public ArraySet<Object> children = new ArraySet<>(0, true);
89 
90         /** If true, do wtf instead of a warning log. */
91         public boolean doWtf;
92     }
93 
findOrCreateLockInfo(Object lock)94     private static LockInfo findOrCreateLockInfo(Object lock) {
95         LockInfo info = sKnown.get(lock);
96         if (info == null) {
97             info = new LockInfo();
98             info.label = "0x" + Integer.toHexString(System.identityHashCode(lock)) + " ["
99                     + new Throwable().getStackTrace()[2].toString() + "]";
100             sKnown.put(lock, info);
101         }
102         return info;
103     }
104 
105     /**
106      * Check if the calling thread is holding any locks in an inverted order.
107      *
108      * @param lock The lock the calling thread is attempting to acquire.
109      */
guard(Object lock)110     public static Object guard(Object lock) {
111         // If we already hold this lock, ignore
112         if (lock == null || Thread.holdsLock(lock)) return lock;
113 
114         // Check to see if we're already holding any child locks
115         boolean triggered = false;
116         final LockInfo info = findOrCreateLockInfo(lock);
117         for (int i = 0; i < info.children.size(); i++) {
118             final Object child = info.children.valueAt(i);
119             if (child == null) continue;
120 
121             if (Thread.holdsLock(child)) {
122                 doLog(lock, "Calling thread " + Thread.currentThread().getName()
123                         + " is holding " + lockToString(child) + " while trying to acquire "
124                         + lockToString(lock));
125                 triggered = true;
126             }
127         }
128 
129         if (!triggered) {
130             // If no trouble found above, record this lock as being a valid
131             // child of all locks currently being held
132             for (int i = 0; i < sKnown.size(); i++) {
133                 final Object test = sKnown.keyAt(i);
134                 if (test == null || test == lock) continue;
135 
136                 if (Thread.holdsLock(test)) {
137                     sKnown.valueAt(i).children.add(lock);
138                 }
139             }
140         }
141 
142         return lock;
143     }
144 
145     /**
146      * Yell if any lower-level locks are being held by the calling thread that
147      * is about to acquire the given lock.
148      */
guard(int index)149     public static void guard(int index) {
150         for (int i = 0; i < index; i++) {
151             final Object lock = sKnownFixed[i];
152             if (lock != null && Thread.holdsLock(lock)) {
153 
154                 // Note in this case sKnownFixed may not contain a lock at the given index,
155                 // which is okay and in that case we just don't do a WTF.
156                 final Object targetMayBeNull = sKnownFixed[index];
157                 doLog(targetMayBeNull, "Calling thread " + Thread.currentThread().getName()
158                         + " is holding " + lockToString(i) + " while trying to acquire "
159                         + lockToString(index));
160             }
161         }
162     }
163 
doLog(@ullable Object lock, String message)164     private static void doLog(@Nullable Object lock, String message) {
165         if (lock != null && findOrCreateLockInfo(lock).doWtf) {
166 
167             // Don't want to call into ActivityManager with any lock held, so let's just call it
168             // from a new thread. We don't want to use known threads (e.g. BackgroundThread) either
169             // because they may be stuck too.
170             final Throwable stackTrace = new RuntimeException(message);
171             new Thread(() -> Slog.wtf(TAG, stackTrace)).start();
172             return;
173         }
174         Slog.w(TAG, message, new Throwable());
175     }
176 
177     /**
178      * Report the given lock with a well-known label.
179      */
installLock(Object lock, String label)180     public static Object installLock(Object lock, String label) {
181         final LockInfo info = findOrCreateLockInfo(lock);
182         info.label = label;
183         return lock;
184     }
185 
186     /**
187      * Report the given lock with a well-known index.
188      */
installLock(Object lock, int index)189     public static Object installLock(Object lock, int index) {
190         return installLock(lock, index, /*doWtf=*/ false);
191     }
192 
193     /**
194      * Report the given lock with a well-known index.
195      */
installLock(Object lock, int index, boolean doWtf)196     public static Object installLock(Object lock, int index, boolean doWtf) {
197         sKnownFixed[index] = lock;
198         final LockInfo info = findOrCreateLockInfo(lock);
199         info.doWtf = doWtf;
200         info.label = "Lock-" + lockToString(index);
201         return lock;
202     }
203 
installNewLock(int index)204     public static Object installNewLock(int index) {
205         return installNewLock(index, /*doWtf=*/ false);
206     }
207 
installNewLock(int index, boolean doWtf)208     public static Object installNewLock(int index, boolean doWtf) {
209         final Object lock = new Object();
210         installLock(lock, index, doWtf);
211         return lock;
212     }
213 
lockToString(Object lock)214     private static String lockToString(Object lock) {
215         final LockInfo info = sKnown.get(lock);
216         if (info != null && !TextUtils.isEmpty(info.label)) {
217             return info.label;
218         } else {
219             return "0x" + Integer.toHexString(System.identityHashCode(lock));
220         }
221     }
222 
lockToString(int index)223     private static String lockToString(int index) {
224         switch (index) {
225             case INDEX_APP_OPS: return "APP_OPS";
226             case INDEX_POWER: return "POWER";
227             case INDEX_USER: return "USER";
228             case INDEX_PACKAGES: return "PACKAGES";
229             case INDEX_STORAGE: return "STORAGE";
230             case INDEX_WINDOW: return "WINDOW";
231             case INDEX_PROC: return "PROCESS";
232             case INDEX_ACTIVITY: return "ACTIVITY";
233             case INDEX_DPMS: return "DPMS";
234             default: return Integer.toString(index);
235         }
236     }
237 
dump(FileDescriptor fd, PrintWriter pw, String[] args)238     public static void dump(FileDescriptor fd, PrintWriter pw, String[] args) {
239         for (int i = 0; i < sKnown.size(); i++) {
240             final Object lock = sKnown.keyAt(i);
241             final LockInfo info = sKnown.valueAt(i);
242             pw.println("Lock " + lockToString(lock) + ":");
243             for (int j = 0; j < info.children.size(); j++) {
244                 pw.println("  Child " + lockToString(info.children.valueAt(j)));
245             }
246             pw.println();
247         }
248     }
249 }
250