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