blob: 0bb204464afec4395120aa1548d61c664b460769 [file] [log] [blame]
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07001/*
2 * kernel/lockdep.c
3 *
4 * Runtime locking correctness validator
5 *
6 * Started by Ingo Molnar:
7 *
Peter Zijlstra4b32d0a2007-07-19 01:48:59 -07008 * Copyright (C) 2006,2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
Peter Zijlstra90eec102015-11-16 11:08:45 +01009 * Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra
Ingo Molnarfbb9ce952006-07-03 00:24:50 -070010 *
11 * this code maps all the lock dependencies as they occur in a live kernel
12 * and will warn about the following classes of locking bugs:
13 *
14 * - lock inversion scenarios
15 * - circular lock dependencies
16 * - hardirq/softirq safe/unsafe locking bugs
17 *
18 * Bugs are reported even if the current locking scenario does not cause
19 * any deadlock at this point.
20 *
21 * I.e. if anytime in the past two locks were taken in a different order,
22 * even if it happened for another task, even if those were different
23 * locks (but of the same class as this lock), this code will detect it.
24 *
25 * Thanks to Arjan van de Ven for coming up with the initial idea of
26 * mapping lock dependencies runtime.
27 */
Steven Rostedta5e25882008-12-02 15:34:05 -050028#define DISABLE_BRANCH_PROFILING
Ingo Molnarfbb9ce952006-07-03 00:24:50 -070029#include <linux/mutex.h>
30#include <linux/sched.h>
Ingo Molnare6017572017-02-01 16:36:40 +010031#include <linux/sched/clock.h>
Ingo Molnar29930022017-02-08 18:51:36 +010032#include <linux/sched/task.h>
Nikolay Borisov6d7225f2017-05-03 14:53:05 -070033#include <linux/sched/mm.h>
Ingo Molnarfbb9ce952006-07-03 00:24:50 -070034#include <linux/delay.h>
35#include <linux/module.h>
36#include <linux/proc_fs.h>
37#include <linux/seq_file.h>
38#include <linux/spinlock.h>
39#include <linux/kallsyms.h>
40#include <linux/interrupt.h>
41#include <linux/stacktrace.h>
42#include <linux/debug_locks.h>
43#include <linux/irqflags.h>
Dave Jones99de0552006-09-29 02:00:10 -070044#include <linux/utsname.h>
Peter Zijlstra4b32d0a2007-07-19 01:48:59 -070045#include <linux/hash.h>
Steven Rostedt81d68a92008-05-12 21:20:42 +020046#include <linux/ftrace.h>
Peter Zijlstrab4b136f2009-01-29 14:50:36 +010047#include <linux/stringify.h>
Bart Van Asscheace35a72019-02-14 15:00:47 -080048#include <linux/bitmap.h>
Ming Leid588e462009-07-16 15:44:29 +020049#include <linux/bitops.h>
Tejun Heo5a0e3ad2010-03-24 17:04:11 +090050#include <linux/gfp.h>
Peter Zijlstrae7904a22015-08-01 19:25:08 +020051#include <linux/random.h>
Peter Zijlstradfaaf3f2016-05-30 18:31:33 +020052#include <linux/jhash.h>
Tejun Heo88f1c872018-01-22 14:00:55 -080053#include <linux/nmi.h>
Bart Van Asschea0b0fd52019-02-14 15:00:46 -080054#include <linux/rcupdate.h>
Peter Zijlstraaf012962009-07-16 15:44:29 +020055
Ingo Molnarfbb9ce952006-07-03 00:24:50 -070056#include <asm/sections.h>
57
58#include "lockdep_internals.h"
59
Steven Rostedta8d154b2009-04-10 09:36:00 -040060#define CREATE_TRACE_POINTS
Frederic Weisbecker67178762009-11-13 10:06:34 +010061#include <trace/events/lock.h>
Steven Rostedta8d154b2009-04-10 09:36:00 -040062
Peter Zijlstraf20786f2007-07-19 01:48:56 -070063#ifdef CONFIG_PROVE_LOCKING
64int prove_locking = 1;
65module_param(prove_locking, int, 0644);
66#else
67#define prove_locking 0
68#endif
69
70#ifdef CONFIG_LOCK_STAT
71int lock_stat = 1;
72module_param(lock_stat, int, 0644);
73#else
74#define lock_stat 0
75#endif
76
Ingo Molnarfbb9ce952006-07-03 00:24:50 -070077/*
Ingo Molnar74c383f2006-12-13 00:34:43 -080078 * lockdep_lock: protects the lockdep graph, the hashes and the
79 * class/list/hash allocators.
Ingo Molnarfbb9ce952006-07-03 00:24:50 -070080 *
81 * This is one of the rare exceptions where it's justified
82 * to use a raw spinlock - we really dont want the spinlock
Ingo Molnar74c383f2006-12-13 00:34:43 -080083 * code to recurse back into the lockdep code...
Ingo Molnarfbb9ce952006-07-03 00:24:50 -070084 */
Thomas Gleixneredc35bd2009-12-03 12:38:57 +010085static arch_spinlock_t lockdep_lock = (arch_spinlock_t)__ARCH_SPIN_LOCK_UNLOCKED;
Bart Van Asschecdc84d72019-02-14 15:00:44 -080086static struct task_struct *lockdep_selftest_task_struct;
Ingo Molnar74c383f2006-12-13 00:34:43 -080087
88static int graph_lock(void)
89{
Thomas Gleixner0199c4e2009-12-02 20:01:25 +010090 arch_spin_lock(&lockdep_lock);
Ingo Molnar74c383f2006-12-13 00:34:43 -080091 /*
92 * Make sure that if another CPU detected a bug while
93 * walking the graph we dont change it (while the other
94 * CPU is busy printing out stuff with the graph lock
95 * dropped already)
96 */
97 if (!debug_locks) {
Thomas Gleixner0199c4e2009-12-02 20:01:25 +010098 arch_spin_unlock(&lockdep_lock);
Ingo Molnar74c383f2006-12-13 00:34:43 -080099 return 0;
100 }
Steven Rostedtbb065af2008-05-12 21:21:00 +0200101 /* prevent any recursions within lockdep from causing deadlocks */
102 current->lockdep_recursion++;
Ingo Molnar74c383f2006-12-13 00:34:43 -0800103 return 1;
104}
105
106static inline int graph_unlock(void)
107{
Peter Zijlstra0119fee2011-09-02 01:30:29 +0200108 if (debug_locks && !arch_spin_is_locked(&lockdep_lock)) {
109 /*
110 * The lockdep graph lock isn't locked while we expect it to
111 * be, we're confused now, bye!
112 */
Jarek Poplawski381a2292007-02-10 01:44:58 -0800113 return DEBUG_LOCKS_WARN_ON(1);
Peter Zijlstra0119fee2011-09-02 01:30:29 +0200114 }
Jarek Poplawski381a2292007-02-10 01:44:58 -0800115
Steven Rostedtbb065af2008-05-12 21:21:00 +0200116 current->lockdep_recursion--;
Thomas Gleixner0199c4e2009-12-02 20:01:25 +0100117 arch_spin_unlock(&lockdep_lock);
Ingo Molnar74c383f2006-12-13 00:34:43 -0800118 return 0;
119}
120
121/*
122 * Turn lock debugging off and return with 0 if it was off already,
123 * and also release the graph lock:
124 */
125static inline int debug_locks_off_graph_unlock(void)
126{
127 int ret = debug_locks_off();
128
Thomas Gleixner0199c4e2009-12-02 20:01:25 +0100129 arch_spin_unlock(&lockdep_lock);
Ingo Molnar74c383f2006-12-13 00:34:43 -0800130
131 return ret;
132}
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700133
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700134unsigned long nr_list_entries;
Peter Zijlstraaf012962009-07-16 15:44:29 +0200135static struct lock_list list_entries[MAX_LOCKDEP_ENTRIES];
Bart Van Asscheace35a72019-02-14 15:00:47 -0800136static DECLARE_BITMAP(list_entries_in_use, MAX_LOCKDEP_ENTRIES);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700137
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700138/*
139 * All data structures here are protected by the global debug_lock.
140 *
Bart Van Asschea0b0fd52019-02-14 15:00:46 -0800141 * nr_lock_classes is the number of elements of lock_classes[] that is
142 * in use.
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700143 */
144unsigned long nr_lock_classes;
Bart Van Assche1431a5d2018-12-06 17:11:32 -0800145#ifndef CONFIG_DEBUG_LOCKDEP
146static
147#endif
Waiman Long8ca2b56c2018-10-03 13:07:18 -0400148struct lock_class lock_classes[MAX_LOCKDEP_KEYS];
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700149
Dave Jonesf82b2172008-08-11 09:30:23 +0200150static inline struct lock_class *hlock_class(struct held_lock *hlock)
151{
152 if (!hlock->class_idx) {
Peter Zijlstra0119fee2011-09-02 01:30:29 +0200153 /*
154 * Someone passed in garbage, we give up.
155 */
Dave Jonesf82b2172008-08-11 09:30:23 +0200156 DEBUG_LOCKS_WARN_ON(1);
157 return NULL;
158 }
159 return lock_classes + hlock->class_idx - 1;
160}
161
Peter Zijlstraf20786f2007-07-19 01:48:56 -0700162#ifdef CONFIG_LOCK_STAT
Peter Zijlstra25528212016-03-15 14:52:49 -0700163static DEFINE_PER_CPU(struct lock_class_stats[MAX_LOCKDEP_KEYS], cpu_lock_stats);
Peter Zijlstraf20786f2007-07-19 01:48:56 -0700164
Peter Zijlstra3365e7792009-10-09 10:12:41 +0200165static inline u64 lockstat_clock(void)
166{
Peter Zijlstrac6763292010-05-25 10:48:51 +0200167 return local_clock();
Peter Zijlstra3365e7792009-10-09 10:12:41 +0200168}
169
Peter Zijlstrac7e78cf2008-10-16 23:17:09 +0200170static int lock_point(unsigned long points[], unsigned long ip)
Peter Zijlstraf20786f2007-07-19 01:48:56 -0700171{
172 int i;
173
Peter Zijlstrac7e78cf2008-10-16 23:17:09 +0200174 for (i = 0; i < LOCKSTAT_POINTS; i++) {
175 if (points[i] == 0) {
176 points[i] = ip;
Peter Zijlstraf20786f2007-07-19 01:48:56 -0700177 break;
178 }
Peter Zijlstrac7e78cf2008-10-16 23:17:09 +0200179 if (points[i] == ip)
Peter Zijlstraf20786f2007-07-19 01:48:56 -0700180 break;
181 }
182
183 return i;
184}
185
Peter Zijlstra3365e7792009-10-09 10:12:41 +0200186static void lock_time_inc(struct lock_time *lt, u64 time)
Peter Zijlstraf20786f2007-07-19 01:48:56 -0700187{
188 if (time > lt->max)
189 lt->max = time;
190
Frank Rowand109d71c2009-11-19 13:42:06 -0800191 if (time < lt->min || !lt->nr)
Peter Zijlstraf20786f2007-07-19 01:48:56 -0700192 lt->min = time;
193
194 lt->total += time;
195 lt->nr++;
196}
197
Peter Zijlstrac46261d2007-07-19 01:48:57 -0700198static inline void lock_time_add(struct lock_time *src, struct lock_time *dst)
199{
Frank Rowand109d71c2009-11-19 13:42:06 -0800200 if (!src->nr)
201 return;
202
203 if (src->max > dst->max)
204 dst->max = src->max;
205
206 if (src->min < dst->min || !dst->nr)
207 dst->min = src->min;
208
Peter Zijlstrac46261d2007-07-19 01:48:57 -0700209 dst->total += src->total;
210 dst->nr += src->nr;
211}
212
213struct lock_class_stats lock_stats(struct lock_class *class)
214{
215 struct lock_class_stats stats;
216 int cpu, i;
217
218 memset(&stats, 0, sizeof(struct lock_class_stats));
219 for_each_possible_cpu(cpu) {
220 struct lock_class_stats *pcs =
Tejun Heo1871e522009-10-29 22:34:13 +0900221 &per_cpu(cpu_lock_stats, cpu)[class - lock_classes];
Peter Zijlstrac46261d2007-07-19 01:48:57 -0700222
223 for (i = 0; i < ARRAY_SIZE(stats.contention_point); i++)
224 stats.contention_point[i] += pcs->contention_point[i];
225
Peter Zijlstrac7e78cf2008-10-16 23:17:09 +0200226 for (i = 0; i < ARRAY_SIZE(stats.contending_point); i++)
227 stats.contending_point[i] += pcs->contending_point[i];
228
Peter Zijlstrac46261d2007-07-19 01:48:57 -0700229 lock_time_add(&pcs->read_waittime, &stats.read_waittime);
230 lock_time_add(&pcs->write_waittime, &stats.write_waittime);
231
232 lock_time_add(&pcs->read_holdtime, &stats.read_holdtime);
233 lock_time_add(&pcs->write_holdtime, &stats.write_holdtime);
Peter Zijlstra96645672007-07-19 01:49:00 -0700234
235 for (i = 0; i < ARRAY_SIZE(stats.bounces); i++)
236 stats.bounces[i] += pcs->bounces[i];
Peter Zijlstrac46261d2007-07-19 01:48:57 -0700237 }
238
239 return stats;
240}
241
242void clear_lock_stats(struct lock_class *class)
243{
244 int cpu;
245
246 for_each_possible_cpu(cpu) {
247 struct lock_class_stats *cpu_stats =
Tejun Heo1871e522009-10-29 22:34:13 +0900248 &per_cpu(cpu_lock_stats, cpu)[class - lock_classes];
Peter Zijlstrac46261d2007-07-19 01:48:57 -0700249
250 memset(cpu_stats, 0, sizeof(struct lock_class_stats));
251 }
252 memset(class->contention_point, 0, sizeof(class->contention_point));
Peter Zijlstrac7e78cf2008-10-16 23:17:09 +0200253 memset(class->contending_point, 0, sizeof(class->contending_point));
Peter Zijlstrac46261d2007-07-19 01:48:57 -0700254}
255
Peter Zijlstraf20786f2007-07-19 01:48:56 -0700256static struct lock_class_stats *get_lock_stats(struct lock_class *class)
257{
Joel Fernandes (Google)01f38492018-07-30 15:24:21 -0700258 return &this_cpu_ptr(cpu_lock_stats)[class - lock_classes];
Peter Zijlstraf20786f2007-07-19 01:48:56 -0700259}
260
261static void lock_release_holdtime(struct held_lock *hlock)
262{
263 struct lock_class_stats *stats;
Peter Zijlstra3365e7792009-10-09 10:12:41 +0200264 u64 holdtime;
Peter Zijlstraf20786f2007-07-19 01:48:56 -0700265
266 if (!lock_stat)
267 return;
268
Peter Zijlstra3365e7792009-10-09 10:12:41 +0200269 holdtime = lockstat_clock() - hlock->holdtime_stamp;
Peter Zijlstraf20786f2007-07-19 01:48:56 -0700270
Dave Jonesf82b2172008-08-11 09:30:23 +0200271 stats = get_lock_stats(hlock_class(hlock));
Peter Zijlstraf20786f2007-07-19 01:48:56 -0700272 if (hlock->read)
273 lock_time_inc(&stats->read_holdtime, holdtime);
274 else
275 lock_time_inc(&stats->write_holdtime, holdtime);
Peter Zijlstraf20786f2007-07-19 01:48:56 -0700276}
277#else
278static inline void lock_release_holdtime(struct held_lock *hlock)
279{
280}
281#endif
282
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700283/*
Bart Van Asschea0b0fd52019-02-14 15:00:46 -0800284 * We keep a global list of all lock classes. The list is only accessed with
285 * the lockdep spinlock lock held. free_lock_classes is a list with free
286 * elements. These elements are linked together by the lock_entry member in
287 * struct lock_class.
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700288 */
289LIST_HEAD(all_lock_classes);
Bart Van Asschea0b0fd52019-02-14 15:00:46 -0800290static LIST_HEAD(free_lock_classes);
291
292/**
293 * struct pending_free - information about data structures about to be freed
294 * @zapped: Head of a list with struct lock_class elements.
Bart Van Asschede4643a2019-02-14 15:00:50 -0800295 * @lock_chains_being_freed: Bitmap that indicates which lock_chains[] elements
296 * are about to be freed.
Bart Van Asschea0b0fd52019-02-14 15:00:46 -0800297 */
298struct pending_free {
299 struct list_head zapped;
Bart Van Asschede4643a2019-02-14 15:00:50 -0800300 DECLARE_BITMAP(lock_chains_being_freed, MAX_LOCKDEP_CHAINS);
Bart Van Asschea0b0fd52019-02-14 15:00:46 -0800301};
302
303/**
304 * struct delayed_free - data structures used for delayed freeing
305 *
306 * A data structure for delayed freeing of data structures that may be
307 * accessed by RCU readers at the time these were freed.
308 *
309 * @rcu_head: Used to schedule an RCU callback for freeing data structures.
310 * @index: Index of @pf to which freed data structures are added.
311 * @scheduled: Whether or not an RCU callback has been scheduled.
312 * @pf: Array with information about data structures about to be freed.
313 */
314static struct delayed_free {
315 struct rcu_head rcu_head;
316 int index;
317 int scheduled;
318 struct pending_free pf[2];
319} delayed_free;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700320
321/*
322 * The lockdep classes are in a hash-table as well, for fast lookup:
323 */
324#define CLASSHASH_BITS (MAX_LOCKDEP_KEYS_BITS - 1)
325#define CLASSHASH_SIZE (1UL << CLASSHASH_BITS)
Peter Zijlstra4b32d0a2007-07-19 01:48:59 -0700326#define __classhashfn(key) hash_long((unsigned long)key, CLASSHASH_BITS)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700327#define classhashentry(key) (classhash_table + __classhashfn((key)))
328
Andrew Mortona63f38c2016-02-03 13:44:12 -0800329static struct hlist_head classhash_table[CLASSHASH_SIZE];
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700330
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700331/*
332 * We put the lock dependency chains into a hash-table as well, to cache
333 * their existence:
334 */
335#define CHAINHASH_BITS (MAX_LOCKDEP_CHAINS_BITS-1)
336#define CHAINHASH_SIZE (1UL << CHAINHASH_BITS)
Peter Zijlstra4b32d0a2007-07-19 01:48:59 -0700337#define __chainhashfn(chain) hash_long(chain, CHAINHASH_BITS)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700338#define chainhashentry(chain) (chainhash_table + __chainhashfn((chain)))
339
Andrew Mortona63f38c2016-02-03 13:44:12 -0800340static struct hlist_head chainhash_table[CHAINHASH_SIZE];
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700341
342/*
343 * The hash key of the lock dependency chains is a hash itself too:
344 * it's a hash of all locks taken up to that lock, including that lock.
345 * It's a 64-bit hash, because it's important for the keys to be
346 * unique.
347 */
Peter Zijlstradfaaf3f2016-05-30 18:31:33 +0200348static inline u64 iterate_chain_key(u64 key, u32 idx)
349{
350 u32 k0 = key, k1 = key >> 32;
351
352 __jhash_mix(idx, k0, k1); /* Macro that modifies arguments! */
353
354 return k0 | (u64)k1 << 32;
355}
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700356
Steven Rostedt1d09daa2008-05-12 21:20:55 +0200357void lockdep_off(void)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700358{
359 current->lockdep_recursion++;
360}
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700361EXPORT_SYMBOL(lockdep_off);
362
Steven Rostedt1d09daa2008-05-12 21:20:55 +0200363void lockdep_on(void)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700364{
365 current->lockdep_recursion--;
366}
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700367EXPORT_SYMBOL(lockdep_on);
368
Bart Van Asschecdc84d72019-02-14 15:00:44 -0800369void lockdep_set_selftest_task(struct task_struct *task)
370{
371 lockdep_selftest_task_struct = task;
372}
373
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700374/*
375 * Debugging switches:
376 */
377
378#define VERBOSE 0
Ingo Molnar33e94e92006-12-13 00:34:41 -0800379#define VERY_VERBOSE 0
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700380
381#if VERBOSE
382# define HARDIRQ_VERBOSE 1
383# define SOFTIRQ_VERBOSE 1
384#else
385# define HARDIRQ_VERBOSE 0
386# define SOFTIRQ_VERBOSE 0
387#endif
388
Peter Zijlstrad92a8cf2017-03-03 10:13:38 +0100389#if VERBOSE || HARDIRQ_VERBOSE || SOFTIRQ_VERBOSE
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700390/*
391 * Quick filtering for interesting events:
392 */
393static int class_filter(struct lock_class *class)
394{
Andi Kleenf9829cc2006-07-10 04:44:01 -0700395#if 0
396 /* Example */
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700397 if (class->name_version == 1 &&
Andi Kleenf9829cc2006-07-10 04:44:01 -0700398 !strcmp(class->name, "lockname"))
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700399 return 1;
400 if (class->name_version == 1 &&
Andi Kleenf9829cc2006-07-10 04:44:01 -0700401 !strcmp(class->name, "&struct->lockfield"))
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700402 return 1;
Andi Kleenf9829cc2006-07-10 04:44:01 -0700403#endif
Ingo Molnara6640892006-12-13 00:34:39 -0800404 /* Filter everything else. 1 would be to allow everything else */
405 return 0;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700406}
407#endif
408
409static int verbose(struct lock_class *class)
410{
411#if VERBOSE
412 return class_filter(class);
413#endif
414 return 0;
415}
416
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700417/*
418 * Stack-trace: tightly packed array of stack backtrace
Ingo Molnar74c383f2006-12-13 00:34:43 -0800419 * addresses. Protected by the graph_lock.
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700420 */
421unsigned long nr_stack_trace_entries;
422static unsigned long stack_trace[MAX_STACK_TRACE_ENTRIES];
423
Dave Jones2c522832013-04-25 13:40:02 -0400424static void print_lockdep_off(const char *bug_msg)
425{
426 printk(KERN_DEBUG "%s\n", bug_msg);
427 printk(KERN_DEBUG "turning off the locking correctness validator.\n");
Andreas Gruenbacheracf59372014-07-15 21:10:52 +0200428#ifdef CONFIG_LOCK_STAT
Dave Jones2c522832013-04-25 13:40:02 -0400429 printk(KERN_DEBUG "Please attach the output of /proc/lock_stat to the bug report\n");
Andreas Gruenbacheracf59372014-07-15 21:10:52 +0200430#endif
Dave Jones2c522832013-04-25 13:40:02 -0400431}
432
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700433static int save_trace(struct stack_trace *trace)
434{
435 trace->nr_entries = 0;
436 trace->max_entries = MAX_STACK_TRACE_ENTRIES - nr_stack_trace_entries;
437 trace->entries = stack_trace + nr_stack_trace_entries;
438
Andi Kleen5a1b3992006-09-26 10:52:34 +0200439 trace->skip = 3;
Andi Kleen5a1b3992006-09-26 10:52:34 +0200440
Christoph Hellwigab1b6f02007-05-08 00:23:29 -0700441 save_stack_trace(trace);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700442
Peter Zijlstra4f84f432009-07-20 15:27:04 +0200443 /*
444 * Some daft arches put -1 at the end to indicate its a full trace.
445 *
446 * <rant> this is buggy anyway, since it takes a whole extra entry so a
447 * complete trace that maxes out the entries provided will be reported
448 * as incomplete, friggin useless </rant>
449 */
Luck, Tonyea5b41f2009-12-09 14:29:36 -0800450 if (trace->nr_entries != 0 &&
451 trace->entries[trace->nr_entries-1] == ULONG_MAX)
Peter Zijlstra4f84f432009-07-20 15:27:04 +0200452 trace->nr_entries--;
453
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700454 trace->max_entries = trace->nr_entries;
455
456 nr_stack_trace_entries += trace->nr_entries;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700457
Peter Zijlstra4f84f432009-07-20 15:27:04 +0200458 if (nr_stack_trace_entries >= MAX_STACK_TRACE_ENTRIES-1) {
Ingo Molnar74c383f2006-12-13 00:34:43 -0800459 if (!debug_locks_off_graph_unlock())
460 return 0;
461
Dave Jones2c522832013-04-25 13:40:02 -0400462 print_lockdep_off("BUG: MAX_STACK_TRACE_ENTRIES too low!");
Ingo Molnar74c383f2006-12-13 00:34:43 -0800463 dump_stack();
464
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700465 return 0;
466 }
467
468 return 1;
469}
470
471unsigned int nr_hardirq_chains;
472unsigned int nr_softirq_chains;
473unsigned int nr_process_chains;
474unsigned int max_lockdep_depth;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700475
476#ifdef CONFIG_DEBUG_LOCKDEP
477/*
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700478 * Various lockdep statistics:
479 */
Frederic Weisbeckerbd6d29c2010-04-06 00:10:17 +0200480DEFINE_PER_CPU(struct lockdep_stats, lockdep_stats);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700481#endif
482
483/*
484 * Locking printouts:
485 */
486
Peter Zijlstrafabe9c42009-01-22 14:51:01 +0100487#define __USAGE(__STATE) \
Peter Zijlstrab4b136f2009-01-29 14:50:36 +0100488 [LOCK_USED_IN_##__STATE] = "IN-"__stringify(__STATE)"-W", \
489 [LOCK_ENABLED_##__STATE] = __stringify(__STATE)"-ON-W", \
490 [LOCK_USED_IN_##__STATE##_READ] = "IN-"__stringify(__STATE)"-R",\
491 [LOCK_ENABLED_##__STATE##_READ] = __stringify(__STATE)"-ON-R",
Peter Zijlstrafabe9c42009-01-22 14:51:01 +0100492
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700493static const char *usage_str[] =
494{
Peter Zijlstrafabe9c42009-01-22 14:51:01 +0100495#define LOCKDEP_STATE(__STATE) __USAGE(__STATE)
496#include "lockdep_states.h"
497#undef LOCKDEP_STATE
498 [LOCK_USED] = "INITIAL USE",
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700499};
500
501const char * __get_key_name(struct lockdep_subclass_key *key, char *str)
502{
Alexey Dobriyanffb45122007-05-08 00:28:41 -0700503 return kallsyms_lookup((unsigned long)key, NULL, NULL, NULL, str);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700504}
505
Peter Zijlstra3ff176c2009-01-22 17:40:42 +0100506static inline unsigned long lock_flag(enum lock_usage_bit bit)
507{
508 return 1UL << bit;
509}
510
511static char get_usage_char(struct lock_class *class, enum lock_usage_bit bit)
512{
513 char c = '.';
514
515 if (class->usage_mask & lock_flag(bit + 2))
516 c = '+';
517 if (class->usage_mask & lock_flag(bit)) {
518 c = '-';
519 if (class->usage_mask & lock_flag(bit + 2))
520 c = '?';
521 }
522
523 return c;
524}
525
Peter Zijlstraf510b232009-01-22 17:53:47 +0100526void get_usage_chars(struct lock_class *class, char usage[LOCK_USAGE_CHARS])
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700527{
Peter Zijlstraf510b232009-01-22 17:53:47 +0100528 int i = 0;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700529
Peter Zijlstraf510b232009-01-22 17:53:47 +0100530#define LOCKDEP_STATE(__STATE) \
531 usage[i++] = get_usage_char(class, LOCK_USED_IN_##__STATE); \
532 usage[i++] = get_usage_char(class, LOCK_USED_IN_##__STATE##_READ);
533#include "lockdep_states.h"
534#undef LOCKDEP_STATE
535
536 usage[i] = '\0';
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700537}
538
Steven Rostedte5e78d02011-11-02 20:24:16 -0400539static void __print_lock_name(struct lock_class *class)
Steven Rostedt3003eba2011-04-20 21:41:54 -0400540{
541 char str[KSYM_NAME_LEN];
542 const char *name;
543
544 name = class->name;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700545 if (!name) {
546 name = __get_key_name(class->key, str);
Dmitry Vyukovf943fe02016-11-28 15:24:43 +0100547 printk(KERN_CONT "%s", name);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700548 } else {
Dmitry Vyukovf943fe02016-11-28 15:24:43 +0100549 printk(KERN_CONT "%s", name);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700550 if (class->name_version > 1)
Dmitry Vyukovf943fe02016-11-28 15:24:43 +0100551 printk(KERN_CONT "#%d", class->name_version);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700552 if (class->subclass)
Dmitry Vyukovf943fe02016-11-28 15:24:43 +0100553 printk(KERN_CONT "/%d", class->subclass);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700554 }
Steven Rostedte5e78d02011-11-02 20:24:16 -0400555}
556
557static void print_lock_name(struct lock_class *class)
558{
559 char usage[LOCK_USAGE_CHARS];
560
561 get_usage_chars(class, usage);
562
Dmitry Vyukovf943fe02016-11-28 15:24:43 +0100563 printk(KERN_CONT " (");
Steven Rostedte5e78d02011-11-02 20:24:16 -0400564 __print_lock_name(class);
Dmitry Vyukovf943fe02016-11-28 15:24:43 +0100565 printk(KERN_CONT "){%s}", usage);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700566}
567
568static void print_lockdep_cache(struct lockdep_map *lock)
569{
570 const char *name;
Tejun Heo9281ace2007-07-17 04:03:51 -0700571 char str[KSYM_NAME_LEN];
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700572
573 name = lock->name;
574 if (!name)
575 name = __get_key_name(lock->key->subkeys, str);
576
Dmitry Vyukovf943fe02016-11-28 15:24:43 +0100577 printk(KERN_CONT "%s", name);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700578}
579
580static void print_lock(struct held_lock *hlock)
581{
Peter Zijlstrad7bc3192015-04-15 17:11:57 +0200582 /*
583 * We can be called locklessly through debug_show_all_locks() so be
584 * extra careful, the hlock might have been released and cleared.
585 */
586 unsigned int class_idx = hlock->class_idx;
587
588 /* Don't re-read hlock->class_idx, can't use READ_ONCE() on bitfields: */
589 barrier();
590
591 if (!class_idx || (class_idx - 1) >= MAX_LOCKDEP_KEYS) {
Dmitry Vyukovf943fe02016-11-28 15:24:43 +0100592 printk(KERN_CONT "<RELEASED>\n");
Peter Zijlstrad7bc3192015-04-15 17:11:57 +0200593 return;
594 }
595
Tetsuo Handab3c39752018-03-27 19:41:41 +0900596 printk(KERN_CONT "%p", hlock->instance);
Peter Zijlstrad7bc3192015-04-15 17:11:57 +0200597 print_lock_name(lock_classes + class_idx - 1);
Tetsuo Handab3c39752018-03-27 19:41:41 +0900598 printk(KERN_CONT ", at: %pS\n", (void *)hlock->acquire_ip);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700599}
600
Tetsuo Handa8cc05c712018-04-06 19:41:19 +0900601static void lockdep_print_held_locks(struct task_struct *p)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700602{
Tetsuo Handa8cc05c712018-04-06 19:41:19 +0900603 int i, depth = READ_ONCE(p->lockdep_depth);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700604
Tetsuo Handa8cc05c712018-04-06 19:41:19 +0900605 if (!depth)
606 printk("no locks held by %s/%d.\n", p->comm, task_pid_nr(p));
607 else
608 printk("%d lock%s held by %s/%d:\n", depth,
609 depth > 1 ? "s" : "", p->comm, task_pid_nr(p));
610 /*
611 * It's not reliable to print a task's held locks if it's not sleeping
612 * and it's not the current task.
613 */
614 if (p->state == TASK_RUNNING && p != current)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700615 return;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700616 for (i = 0; i < depth; i++) {
617 printk(" #%d: ", i);
Tetsuo Handa8cc05c712018-04-06 19:41:19 +0900618 print_lock(p->held_locks + i);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700619 }
620}
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700621
Ben Hutchingsfbdc4b92011-10-28 04:36:55 +0100622static void print_kernel_ident(void)
Dave Jones99de0552006-09-29 02:00:10 -0700623{
Ben Hutchingsfbdc4b92011-10-28 04:36:55 +0100624 printk("%s %.*s %s\n", init_utsname()->release,
Serge E. Hallyn96b644b2006-10-02 02:18:13 -0700625 (int)strcspn(init_utsname()->version, " "),
Ben Hutchingsfbdc4b92011-10-28 04:36:55 +0100626 init_utsname()->version,
627 print_tainted());
Dave Jones99de0552006-09-29 02:00:10 -0700628}
629
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700630static int very_verbose(struct lock_class *class)
631{
632#if VERY_VERBOSE
633 return class_filter(class);
634#endif
635 return 0;
636}
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700637
638/*
639 * Is this the address of a static object:
640 */
Sasha Levin8dce7a92013-06-13 18:41:16 -0400641#ifdef __KERNEL__
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700642static int static_obj(void *obj)
643{
644 unsigned long start = (unsigned long) &_stext,
645 end = (unsigned long) &_end,
646 addr = (unsigned long) obj;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700647
648 /*
649 * static variable?
650 */
651 if ((addr >= start) && (addr < end))
652 return 1;
653
Mike Frysinger2a9ad182009-09-22 16:44:16 -0700654 if (arch_is_kernel_data(addr))
655 return 1;
656
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700657 /*
Tejun Heo10fad5e2010-03-10 18:57:54 +0900658 * in-kernel percpu var?
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700659 */
Tejun Heo10fad5e2010-03-10 18:57:54 +0900660 if (is_kernel_percpu_address(addr))
661 return 1;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700662
663 /*
Tejun Heo10fad5e2010-03-10 18:57:54 +0900664 * module static or percpu var?
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700665 */
Tejun Heo10fad5e2010-03-10 18:57:54 +0900666 return is_module_address(addr) || is_module_percpu_address(addr);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700667}
Sasha Levin8dce7a92013-06-13 18:41:16 -0400668#endif
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700669
670/*
671 * To make lock name printouts unique, we calculate a unique
Bart Van Asschefe27b0d2018-12-06 17:11:37 -0800672 * class->name_version generation counter. The caller must hold the graph
673 * lock.
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700674 */
675static int count_matching_names(struct lock_class *new_class)
676{
677 struct lock_class *class;
678 int count = 0;
679
680 if (!new_class->name)
681 return 0;
682
Bart Van Asschefe27b0d2018-12-06 17:11:37 -0800683 list_for_each_entry(class, &all_lock_classes, lock_entry) {
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700684 if (new_class->key - new_class->subclass == class->key)
685 return class->name_version;
686 if (class->name && !strcmp(class->name, new_class->name))
687 count = max(count, class->name_version);
688 }
689
690 return count + 1;
691}
692
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700693static inline struct lock_class *
Matthew Wilcox08f36ff2018-01-17 07:14:13 -0800694look_up_lock_class(const struct lockdep_map *lock, unsigned int subclass)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700695{
696 struct lockdep_subclass_key *key;
Andrew Mortona63f38c2016-02-03 13:44:12 -0800697 struct hlist_head *hash_head;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700698 struct lock_class *class;
699
Hitoshi Mitake4ba053c2010-10-13 17:30:26 +0900700 if (unlikely(subclass >= MAX_LOCKDEP_SUBCLASSES)) {
701 debug_locks_off();
702 printk(KERN_ERR
703 "BUG: looking up invalid subclass: %u\n", subclass);
704 printk(KERN_ERR
705 "turning off the locking correctness validator.\n");
706 dump_stack();
707 return NULL;
708 }
709
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700710 /*
Matthew Wilcox64f29d12018-01-17 07:14:12 -0800711 * If it is not initialised then it has never been locked,
712 * so it won't be present in the hash table.
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700713 */
Matthew Wilcox64f29d12018-01-17 07:14:12 -0800714 if (unlikely(!lock->key))
715 return NULL;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700716
717 /*
718 * NOTE: the class-key must be unique. For dynamic locks, a static
719 * lock_class_key variable is passed in through the mutex_init()
720 * (or spin_lock_init()) call - which acts as the key. For static
721 * locks we use the lock object itself as the key.
722 */
Peter Zijlstra4b32d0a2007-07-19 01:48:59 -0700723 BUILD_BUG_ON(sizeof(struct lock_class_key) >
724 sizeof(struct lockdep_map));
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700725
726 key = lock->key->subkeys + subclass;
727
728 hash_head = classhashentry(key);
729
730 /*
Peter Zijlstra35a93932015-02-26 16:23:11 +0100731 * We do an RCU walk of the hash, see lockdep_free_key_range().
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700732 */
Peter Zijlstra35a93932015-02-26 16:23:11 +0100733 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
734 return NULL;
735
Andrew Mortona63f38c2016-02-03 13:44:12 -0800736 hlist_for_each_entry_rcu(class, hash_head, hash_entry) {
Peter Zijlstra4b32d0a2007-07-19 01:48:59 -0700737 if (class->key == key) {
Peter Zijlstra0119fee2011-09-02 01:30:29 +0200738 /*
739 * Huh! same key, different name? Did someone trample
740 * on some memory? We're most confused.
741 */
Peter Zijlstra4b32d0a2007-07-19 01:48:59 -0700742 WARN_ON_ONCE(class->name != lock->name);
Ingo Molnard6d897c2006-07-10 04:44:04 -0700743 return class;
Peter Zijlstra4b32d0a2007-07-19 01:48:59 -0700744 }
745 }
Ingo Molnard6d897c2006-07-10 04:44:04 -0700746
Matthew Wilcox64f29d12018-01-17 07:14:12 -0800747 return NULL;
748}
749
750/*
751 * Static locks do not have their class-keys yet - for them the key is
752 * the lock object itself. If the lock is in the per cpu area, the
753 * canonical address of the lock (per cpu offset removed) is used.
754 */
755static bool assign_lock_key(struct lockdep_map *lock)
756{
757 unsigned long can_addr, addr = (unsigned long)lock;
758
759 if (__is_kernel_percpu_address(addr, &can_addr))
760 lock->key = (void *)can_addr;
761 else if (__is_module_percpu_address(addr, &can_addr))
762 lock->key = (void *)can_addr;
763 else if (static_obj(lock))
764 lock->key = (void *)lock;
765 else {
766 /* Debug-check: all keys must be persistent! */
767 debug_locks_off();
768 pr_err("INFO: trying to register non-static key.\n");
769 pr_err("the code is fine but needs lockdep annotation.\n");
770 pr_err("turning off the locking correctness validator.\n");
771 dump_stack();
772 return false;
773 }
774
775 return true;
Ingo Molnard6d897c2006-07-10 04:44:04 -0700776}
777
778/*
Bart Van Asschea0b0fd52019-02-14 15:00:46 -0800779 * Initialize the lock_classes[] array elements, the free_lock_classes list
780 * and also the delayed_free structure.
Bart Van Asschefeb0a382019-02-14 15:00:42 -0800781 */
782static void init_data_structures_once(void)
783{
784 static bool initialization_happened;
785 int i;
786
787 if (likely(initialization_happened))
788 return;
789
790 initialization_happened = true;
791
Bart Van Asschea0b0fd52019-02-14 15:00:46 -0800792 init_rcu_head(&delayed_free.rcu_head);
793 INIT_LIST_HEAD(&delayed_free.pf[0].zapped);
794 INIT_LIST_HEAD(&delayed_free.pf[1].zapped);
795
Bart Van Asschefeb0a382019-02-14 15:00:42 -0800796 for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
Bart Van Asschea0b0fd52019-02-14 15:00:46 -0800797 list_add_tail(&lock_classes[i].lock_entry, &free_lock_classes);
Bart Van Asschefeb0a382019-02-14 15:00:42 -0800798 INIT_LIST_HEAD(&lock_classes[i].locks_after);
799 INIT_LIST_HEAD(&lock_classes[i].locks_before);
800 }
801}
802
803/*
Ingo Molnard6d897c2006-07-10 04:44:04 -0700804 * Register a lock's class in the hash-table, if the class is not present
805 * yet. Otherwise we look it up. We cache the result in the lock object
806 * itself, so actual lookup of the hash should be once per lock object.
807 */
Denys Vlasenkoc003ed92016-04-08 20:58:46 +0200808static struct lock_class *
Peter Zijlstra4dfbb9d2006-10-11 01:45:14 -0400809register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
Ingo Molnard6d897c2006-07-10 04:44:04 -0700810{
811 struct lockdep_subclass_key *key;
Andrew Mortona63f38c2016-02-03 13:44:12 -0800812 struct hlist_head *hash_head;
Ingo Molnard6d897c2006-07-10 04:44:04 -0700813 struct lock_class *class;
Peter Zijlstra35a93932015-02-26 16:23:11 +0100814
815 DEBUG_LOCKS_WARN_ON(!irqs_disabled());
Ingo Molnard6d897c2006-07-10 04:44:04 -0700816
817 class = look_up_lock_class(lock, subclass);
Matthew Wilcox64f29d12018-01-17 07:14:12 -0800818 if (likely(class))
Yong Zhang87cdee72011-11-09 16:07:14 +0800819 goto out_set_class_cache;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700820
Matthew Wilcox64f29d12018-01-17 07:14:12 -0800821 if (!lock->key) {
822 if (!assign_lock_key(lock))
823 return NULL;
824 } else if (!static_obj(lock->key)) {
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700825 return NULL;
826 }
827
Ingo Molnard6d897c2006-07-10 04:44:04 -0700828 key = lock->key->subkeys + subclass;
829 hash_head = classhashentry(key);
830
Ingo Molnar74c383f2006-12-13 00:34:43 -0800831 if (!graph_lock()) {
Ingo Molnar74c383f2006-12-13 00:34:43 -0800832 return NULL;
833 }
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700834 /*
835 * We have to do the hash-walk again, to avoid races
836 * with another CPU:
837 */
Andrew Mortona63f38c2016-02-03 13:44:12 -0800838 hlist_for_each_entry_rcu(class, hash_head, hash_entry) {
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700839 if (class->key == key)
840 goto out_unlock_set;
Peter Zijlstra35a93932015-02-26 16:23:11 +0100841 }
842
Bart Van Asschefeb0a382019-02-14 15:00:42 -0800843 init_data_structures_once();
844
Bart Van Asschea0b0fd52019-02-14 15:00:46 -0800845 /* Allocate a new lock class and add it to the hash. */
846 class = list_first_entry_or_null(&free_lock_classes, typeof(*class),
847 lock_entry);
848 if (!class) {
Ingo Molnar74c383f2006-12-13 00:34:43 -0800849 if (!debug_locks_off_graph_unlock()) {
Ingo Molnar74c383f2006-12-13 00:34:43 -0800850 return NULL;
851 }
Ingo Molnar74c383f2006-12-13 00:34:43 -0800852
Dave Jones2c522832013-04-25 13:40:02 -0400853 print_lockdep_off("BUG: MAX_LOCKDEP_KEYS too low!");
Peter Zijlstraeedeeab2009-03-18 12:38:47 +0100854 dump_stack();
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700855 return NULL;
856 }
Bart Van Asschea0b0fd52019-02-14 15:00:46 -0800857 nr_lock_classes++;
Frederic Weisbeckerbd6d29c2010-04-06 00:10:17 +0200858 debug_atomic_inc(nr_unused_locks);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700859 class->key = key;
860 class->name = lock->name;
861 class->subclass = subclass;
Bart Van Asschefeb0a382019-02-14 15:00:42 -0800862 WARN_ON_ONCE(!list_empty(&class->locks_before));
863 WARN_ON_ONCE(!list_empty(&class->locks_after));
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700864 class->name_version = count_matching_names(class);
865 /*
866 * We use RCU's safe list-add method to make
867 * parallel walking of the hash-list safe:
868 */
Andrew Mortona63f38c2016-02-03 13:44:12 -0800869 hlist_add_head_rcu(&class->hash_entry, hash_head);
Dale Farnsworth14811972008-02-25 23:03:02 +0100870 /*
Bart Van Asschea0b0fd52019-02-14 15:00:46 -0800871 * Remove the class from the free list and add it to the global list
872 * of classes.
Dale Farnsworth14811972008-02-25 23:03:02 +0100873 */
Bart Van Asschea0b0fd52019-02-14 15:00:46 -0800874 list_move_tail(&class->lock_entry, &all_lock_classes);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700875
876 if (verbose(class)) {
Ingo Molnar74c383f2006-12-13 00:34:43 -0800877 graph_unlock();
Ingo Molnar74c383f2006-12-13 00:34:43 -0800878
Borislav Petkov04860d42018-02-26 14:49:26 +0100879 printk("\nnew class %px: %s", class->key, class->name);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700880 if (class->name_version > 1)
Dmitry Vyukovf943fe02016-11-28 15:24:43 +0100881 printk(KERN_CONT "#%d", class->name_version);
882 printk(KERN_CONT "\n");
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700883 dump_stack();
Ingo Molnar74c383f2006-12-13 00:34:43 -0800884
Ingo Molnar74c383f2006-12-13 00:34:43 -0800885 if (!graph_lock()) {
Ingo Molnar74c383f2006-12-13 00:34:43 -0800886 return NULL;
887 }
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700888 }
889out_unlock_set:
Ingo Molnar74c383f2006-12-13 00:34:43 -0800890 graph_unlock();
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700891
Yong Zhang87cdee72011-11-09 16:07:14 +0800892out_set_class_cache:
Peter Zijlstra4dfbb9d2006-10-11 01:45:14 -0400893 if (!subclass || force)
Hitoshi Mitake62016252010-10-05 18:01:51 +0900894 lock->class_cache[0] = class;
895 else if (subclass < NR_LOCKDEP_CACHING_CLASSES)
896 lock->class_cache[subclass] = class;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700897
Peter Zijlstra0119fee2011-09-02 01:30:29 +0200898 /*
899 * Hash collision, did we smoke some? We found a class with a matching
900 * hash but the subclass -- which is hashed in -- didn't match.
901 */
Jarek Poplawski381a2292007-02-10 01:44:58 -0800902 if (DEBUG_LOCKS_WARN_ON(class->subclass != subclass))
903 return NULL;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700904
905 return class;
906}
907
Peter Zijlstraca58abc2007-07-19 01:48:53 -0700908#ifdef CONFIG_PROVE_LOCKING
Ingo Molnarfbb9ce952006-07-03 00:24:50 -0700909/*
Peter Zijlstra8e182572007-07-19 01:48:54 -0700910 * Allocate a lockdep entry. (assumes the graph_lock held, returns
911 * with NULL on failure)
912 */
913static struct lock_list *alloc_list_entry(void)
914{
Bart Van Asscheace35a72019-02-14 15:00:47 -0800915 int idx = find_first_zero_bit(list_entries_in_use,
916 ARRAY_SIZE(list_entries));
917
918 if (idx >= ARRAY_SIZE(list_entries)) {
Peter Zijlstra8e182572007-07-19 01:48:54 -0700919 if (!debug_locks_off_graph_unlock())
920 return NULL;
921
Dave Jones2c522832013-04-25 13:40:02 -0400922 print_lockdep_off("BUG: MAX_LOCKDEP_ENTRIES too low!");
Peter Zijlstraeedeeab2009-03-18 12:38:47 +0100923 dump_stack();
Peter Zijlstra8e182572007-07-19 01:48:54 -0700924 return NULL;
925 }
Bart Van Asscheace35a72019-02-14 15:00:47 -0800926 nr_list_entries++;
927 __set_bit(idx, list_entries_in_use);
928 return list_entries + idx;
Peter Zijlstra8e182572007-07-19 01:48:54 -0700929}
930
931/*
932 * Add a new dependency to the head of the list:
933 */
Bart Van Assche86cffb82019-02-14 15:00:41 -0800934static int add_lock_to_list(struct lock_class *this,
935 struct lock_class *links_to, struct list_head *head,
Tahsin Erdogan83f06162016-11-08 00:02:07 -0800936 unsigned long ip, int distance,
937 struct stack_trace *trace)
Peter Zijlstra8e182572007-07-19 01:48:54 -0700938{
939 struct lock_list *entry;
940 /*
941 * Lock not present yet - get a new dependency struct and
942 * add it to the list:
943 */
944 entry = alloc_list_entry();
945 if (!entry)
946 return 0;
947
Zhu Yi74870172008-08-27 14:33:00 +0800948 entry->class = this;
Bart Van Assche86cffb82019-02-14 15:00:41 -0800949 entry->links_to = links_to;
Zhu Yi74870172008-08-27 14:33:00 +0800950 entry->distance = distance;
Yong Zhang4726f2a2010-05-04 14:16:48 +0800951 entry->trace = *trace;
Peter Zijlstra8e182572007-07-19 01:48:54 -0700952 /*
Peter Zijlstra35a93932015-02-26 16:23:11 +0100953 * Both allocation and removal are done under the graph lock; but
954 * iteration is under RCU-sched; see look_up_lock_class() and
955 * lockdep_free_key_range().
Peter Zijlstra8e182572007-07-19 01:48:54 -0700956 */
957 list_add_tail_rcu(&entry->entry, head);
958
959 return 1;
960}
961
Peter Zijlstra98c33ed2009-07-21 13:19:07 +0200962/*
963 * For good efficiency of modular, we use power of 2
964 */
Peter Zijlstraaf012962009-07-16 15:44:29 +0200965#define MAX_CIRCULAR_QUEUE_SIZE 4096UL
966#define CQ_MASK (MAX_CIRCULAR_QUEUE_SIZE-1)
967
Peter Zijlstra98c33ed2009-07-21 13:19:07 +0200968/*
969 * The circular_queue and helpers is used to implement the
Peter Zijlstraaf012962009-07-16 15:44:29 +0200970 * breadth-first search(BFS)algorithem, by which we can build
971 * the shortest path from the next lock to be acquired to the
972 * previous held lock if there is a circular between them.
Peter Zijlstra98c33ed2009-07-21 13:19:07 +0200973 */
Peter Zijlstraaf012962009-07-16 15:44:29 +0200974struct circular_queue {
975 unsigned long element[MAX_CIRCULAR_QUEUE_SIZE];
976 unsigned int front, rear;
977};
978
979static struct circular_queue lock_cq;
Peter Zijlstraaf012962009-07-16 15:44:29 +0200980
Ming Lei12f3dfd2009-07-16 15:44:29 +0200981unsigned int max_bfs_queue_depth;
Peter Zijlstraaf012962009-07-16 15:44:29 +0200982
Ming Leie351b662009-07-22 22:48:09 +0800983static unsigned int lockdep_dependency_gen_id;
984
Peter Zijlstraaf012962009-07-16 15:44:29 +0200985static inline void __cq_init(struct circular_queue *cq)
986{
987 cq->front = cq->rear = 0;
Ming Leie351b662009-07-22 22:48:09 +0800988 lockdep_dependency_gen_id++;
Peter Zijlstraaf012962009-07-16 15:44:29 +0200989}
990
991static inline int __cq_empty(struct circular_queue *cq)
992{
993 return (cq->front == cq->rear);
994}
995
996static inline int __cq_full(struct circular_queue *cq)
997{
998 return ((cq->rear + 1) & CQ_MASK) == cq->front;
999}
1000
1001static inline int __cq_enqueue(struct circular_queue *cq, unsigned long elem)
1002{
1003 if (__cq_full(cq))
1004 return -1;
1005
1006 cq->element[cq->rear] = elem;
1007 cq->rear = (cq->rear + 1) & CQ_MASK;
1008 return 0;
1009}
1010
1011static inline int __cq_dequeue(struct circular_queue *cq, unsigned long *elem)
1012{
1013 if (__cq_empty(cq))
1014 return -1;
1015
1016 *elem = cq->element[cq->front];
1017 cq->front = (cq->front + 1) & CQ_MASK;
1018 return 0;
1019}
1020
1021static inline unsigned int __cq_get_elem_count(struct circular_queue *cq)
1022{
1023 return (cq->rear - cq->front) & CQ_MASK;
1024}
1025
1026static inline void mark_lock_accessed(struct lock_list *lock,
1027 struct lock_list *parent)
1028{
1029 unsigned long nr;
Peter Zijlstra98c33ed2009-07-21 13:19:07 +02001030
Peter Zijlstraaf012962009-07-16 15:44:29 +02001031 nr = lock - list_entries;
Bart Van Asscheace35a72019-02-14 15:00:47 -08001032 WARN_ON(nr >= ARRAY_SIZE(list_entries)); /* Out-of-bounds, input fail */
Peter Zijlstraaf012962009-07-16 15:44:29 +02001033 lock->parent = parent;
Ming Leie351b662009-07-22 22:48:09 +08001034 lock->class->dep_gen_id = lockdep_dependency_gen_id;
Peter Zijlstraaf012962009-07-16 15:44:29 +02001035}
1036
1037static inline unsigned long lock_accessed(struct lock_list *lock)
1038{
1039 unsigned long nr;
Peter Zijlstra98c33ed2009-07-21 13:19:07 +02001040
Peter Zijlstraaf012962009-07-16 15:44:29 +02001041 nr = lock - list_entries;
Bart Van Asscheace35a72019-02-14 15:00:47 -08001042 WARN_ON(nr >= ARRAY_SIZE(list_entries)); /* Out-of-bounds, input fail */
Ming Leie351b662009-07-22 22:48:09 +08001043 return lock->class->dep_gen_id == lockdep_dependency_gen_id;
Peter Zijlstraaf012962009-07-16 15:44:29 +02001044}
1045
1046static inline struct lock_list *get_lock_parent(struct lock_list *child)
1047{
1048 return child->parent;
1049}
1050
1051static inline int get_lock_depth(struct lock_list *child)
1052{
1053 int depth = 0;
1054 struct lock_list *parent;
1055
1056 while ((parent = get_lock_parent(child))) {
1057 child = parent;
1058 depth++;
1059 }
1060 return depth;
1061}
1062
Ming Lei9e2d5512009-07-16 15:44:29 +02001063static int __bfs(struct lock_list *source_entry,
Peter Zijlstraaf012962009-07-16 15:44:29 +02001064 void *data,
1065 int (*match)(struct lock_list *entry, void *data),
1066 struct lock_list **target_entry,
1067 int forward)
Ming Leic94aa5c2009-07-16 15:44:29 +02001068{
1069 struct lock_list *entry;
Ming Leid588e462009-07-16 15:44:29 +02001070 struct list_head *head;
Ming Leic94aa5c2009-07-16 15:44:29 +02001071 struct circular_queue *cq = &lock_cq;
1072 int ret = 1;
1073
Ming Lei9e2d5512009-07-16 15:44:29 +02001074 if (match(source_entry, data)) {
Ming Leic94aa5c2009-07-16 15:44:29 +02001075 *target_entry = source_entry;
1076 ret = 0;
1077 goto exit;
1078 }
1079
Ming Leid588e462009-07-16 15:44:29 +02001080 if (forward)
1081 head = &source_entry->class->locks_after;
1082 else
1083 head = &source_entry->class->locks_before;
1084
1085 if (list_empty(head))
1086 goto exit;
1087
1088 __cq_init(cq);
Ming Leic94aa5c2009-07-16 15:44:29 +02001089 __cq_enqueue(cq, (unsigned long)source_entry);
1090
1091 while (!__cq_empty(cq)) {
1092 struct lock_list *lock;
Ming Leic94aa5c2009-07-16 15:44:29 +02001093
1094 __cq_dequeue(cq, (unsigned long *)&lock);
1095
1096 if (!lock->class) {
1097 ret = -2;
1098 goto exit;
1099 }
1100
1101 if (forward)
1102 head = &lock->class->locks_after;
1103 else
1104 head = &lock->class->locks_before;
1105
Peter Zijlstra35a93932015-02-26 16:23:11 +01001106 DEBUG_LOCKS_WARN_ON(!irqs_disabled());
1107
1108 list_for_each_entry_rcu(entry, head, entry) {
Ming Leic94aa5c2009-07-16 15:44:29 +02001109 if (!lock_accessed(entry)) {
Ming Lei12f3dfd2009-07-16 15:44:29 +02001110 unsigned int cq_depth;
Ming Leic94aa5c2009-07-16 15:44:29 +02001111 mark_lock_accessed(entry, lock);
Ming Lei9e2d5512009-07-16 15:44:29 +02001112 if (match(entry, data)) {
Ming Leic94aa5c2009-07-16 15:44:29 +02001113 *target_entry = entry;
1114 ret = 0;
1115 goto exit;
1116 }
1117
1118 if (__cq_enqueue(cq, (unsigned long)entry)) {
1119 ret = -1;
1120 goto exit;
1121 }
Ming Lei12f3dfd2009-07-16 15:44:29 +02001122 cq_depth = __cq_get_elem_count(cq);
1123 if (max_bfs_queue_depth < cq_depth)
1124 max_bfs_queue_depth = cq_depth;
Ming Leic94aa5c2009-07-16 15:44:29 +02001125 }
1126 }
1127 }
1128exit:
1129 return ret;
1130}
1131
Ming Leid7aaba12009-07-16 15:44:29 +02001132static inline int __bfs_forwards(struct lock_list *src_entry,
Ming Lei9e2d5512009-07-16 15:44:29 +02001133 void *data,
1134 int (*match)(struct lock_list *entry, void *data),
1135 struct lock_list **target_entry)
Ming Leic94aa5c2009-07-16 15:44:29 +02001136{
Ming Lei9e2d5512009-07-16 15:44:29 +02001137 return __bfs(src_entry, data, match, target_entry, 1);
Ming Leic94aa5c2009-07-16 15:44:29 +02001138
1139}
1140
Ming Leid7aaba12009-07-16 15:44:29 +02001141static inline int __bfs_backwards(struct lock_list *src_entry,
Ming Lei9e2d5512009-07-16 15:44:29 +02001142 void *data,
1143 int (*match)(struct lock_list *entry, void *data),
1144 struct lock_list **target_entry)
Ming Leic94aa5c2009-07-16 15:44:29 +02001145{
Ming Lei9e2d5512009-07-16 15:44:29 +02001146 return __bfs(src_entry, data, match, target_entry, 0);
Ming Leic94aa5c2009-07-16 15:44:29 +02001147
1148}
1149
Peter Zijlstra8e182572007-07-19 01:48:54 -07001150/*
1151 * Recursive, forwards-direction lock-dependency checking, used for
1152 * both noncyclic checking and for hardirq-unsafe/softirq-unsafe
1153 * checking.
Peter Zijlstra8e182572007-07-19 01:48:54 -07001154 */
Peter Zijlstra8e182572007-07-19 01:48:54 -07001155
1156/*
1157 * Print a dependency chain entry (this is only done when a deadlock
1158 * has been detected):
1159 */
1160static noinline int
Ming Lei24208ca2009-07-16 15:44:29 +02001161print_circular_bug_entry(struct lock_list *target, int depth)
Peter Zijlstra8e182572007-07-19 01:48:54 -07001162{
1163 if (debug_locks_silent)
1164 return 0;
1165 printk("\n-> #%u", depth);
1166 print_lock_name(target->class);
Dmitry Vyukovf943fe02016-11-28 15:24:43 +01001167 printk(KERN_CONT ":\n");
Peter Zijlstra8e182572007-07-19 01:48:54 -07001168 print_stack_trace(&target->trace, 6);
1169
1170 return 0;
1171}
1172
Steven Rostedtf4185812011-04-20 21:41:55 -04001173static void
1174print_circular_lock_scenario(struct held_lock *src,
1175 struct held_lock *tgt,
1176 struct lock_list *prt)
1177{
1178 struct lock_class *source = hlock_class(src);
1179 struct lock_class *target = hlock_class(tgt);
1180 struct lock_class *parent = prt->class;
1181
1182 /*
1183 * A direct locking problem where unsafe_class lock is taken
1184 * directly by safe_class lock, then all we need to show
1185 * is the deadlock scenario, as it is obvious that the
1186 * unsafe lock is taken under the safe lock.
1187 *
1188 * But if there is a chain instead, where the safe lock takes
1189 * an intermediate lock (middle_class) where this lock is
1190 * not the same as the safe lock, then the lock chain is
1191 * used to describe the problem. Otherwise we would need
1192 * to show a different CPU case for each link in the chain
1193 * from the safe_class lock to the unsafe_class lock.
1194 */
1195 if (parent != source) {
1196 printk("Chain exists of:\n ");
1197 __print_lock_name(source);
Dmitry Vyukovf943fe02016-11-28 15:24:43 +01001198 printk(KERN_CONT " --> ");
Steven Rostedtf4185812011-04-20 21:41:55 -04001199 __print_lock_name(parent);
Dmitry Vyukovf943fe02016-11-28 15:24:43 +01001200 printk(KERN_CONT " --> ");
Steven Rostedtf4185812011-04-20 21:41:55 -04001201 __print_lock_name(target);
Dmitry Vyukovf943fe02016-11-28 15:24:43 +01001202 printk(KERN_CONT "\n\n");
Steven Rostedtf4185812011-04-20 21:41:55 -04001203 }
1204
Ingo Molnare966eae2017-12-12 12:31:16 +01001205 printk(" Possible unsafe locking scenario:\n\n");
1206 printk(" CPU0 CPU1\n");
1207 printk(" ---- ----\n");
1208 printk(" lock(");
1209 __print_lock_name(target);
1210 printk(KERN_CONT ");\n");
1211 printk(" lock(");
1212 __print_lock_name(parent);
1213 printk(KERN_CONT ");\n");
1214 printk(" lock(");
1215 __print_lock_name(target);
1216 printk(KERN_CONT ");\n");
1217 printk(" lock(");
1218 __print_lock_name(source);
1219 printk(KERN_CONT ");\n");
1220 printk("\n *** DEADLOCK ***\n\n");
Steven Rostedtf4185812011-04-20 21:41:55 -04001221}
1222
Peter Zijlstra8e182572007-07-19 01:48:54 -07001223/*
1224 * When a circular dependency is detected, print the
1225 * header first:
1226 */
1227static noinline int
Ming Leidb0002a2009-07-16 15:44:29 +02001228print_circular_bug_header(struct lock_list *entry, unsigned int depth,
1229 struct held_lock *check_src,
1230 struct held_lock *check_tgt)
Peter Zijlstra8e182572007-07-19 01:48:54 -07001231{
1232 struct task_struct *curr = current;
1233
Ming Leic94aa5c2009-07-16 15:44:29 +02001234 if (debug_locks_silent)
Peter Zijlstra8e182572007-07-19 01:48:54 -07001235 return 0;
1236
Paul E. McKenney681fbec2017-05-04 15:44:38 -07001237 pr_warn("\n");
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08001238 pr_warn("======================================================\n");
1239 pr_warn("WARNING: possible circular locking dependency detected\n");
Ben Hutchingsfbdc4b92011-10-28 04:36:55 +01001240 print_kernel_ident();
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08001241 pr_warn("------------------------------------------------------\n");
Paul E. McKenney681fbec2017-05-04 15:44:38 -07001242 pr_warn("%s/%d is trying to acquire lock:\n",
Pavel Emelyanovba25f9d2007-10-18 23:40:40 -07001243 curr->comm, task_pid_nr(curr));
Ming Leidb0002a2009-07-16 15:44:29 +02001244 print_lock(check_src);
Byungchul Park383a4bc2017-08-07 16:12:55 +09001245
Ingo Molnare966eae2017-12-12 12:31:16 +01001246 pr_warn("\nbut task is already holding lock:\n");
Byungchul Park383a4bc2017-08-07 16:12:55 +09001247
Ming Leidb0002a2009-07-16 15:44:29 +02001248 print_lock(check_tgt);
Paul E. McKenney681fbec2017-05-04 15:44:38 -07001249 pr_warn("\nwhich lock already depends on the new lock.\n\n");
1250 pr_warn("\nthe existing dependency chain (in reverse order) is:\n");
Peter Zijlstra8e182572007-07-19 01:48:54 -07001251
1252 print_circular_bug_entry(entry, depth);
1253
1254 return 0;
1255}
1256
Ming Lei9e2d5512009-07-16 15:44:29 +02001257static inline int class_equal(struct lock_list *entry, void *data)
1258{
1259 return entry->class == data;
1260}
1261
Ming Leidb0002a2009-07-16 15:44:29 +02001262static noinline int print_circular_bug(struct lock_list *this,
1263 struct lock_list *target,
1264 struct held_lock *check_src,
Byungchul Park383a4bc2017-08-07 16:12:55 +09001265 struct held_lock *check_tgt,
1266 struct stack_trace *trace)
Peter Zijlstra8e182572007-07-19 01:48:54 -07001267{
1268 struct task_struct *curr = current;
Ming Leic94aa5c2009-07-16 15:44:29 +02001269 struct lock_list *parent;
Steven Rostedtf4185812011-04-20 21:41:55 -04001270 struct lock_list *first_parent;
Ming Lei24208ca2009-07-16 15:44:29 +02001271 int depth;
Peter Zijlstra8e182572007-07-19 01:48:54 -07001272
Ming Leic94aa5c2009-07-16 15:44:29 +02001273 if (!debug_locks_off_graph_unlock() || debug_locks_silent)
Peter Zijlstra8e182572007-07-19 01:48:54 -07001274 return 0;
1275
Ingo Molnare966eae2017-12-12 12:31:16 +01001276 if (!save_trace(&this->trace))
Peter Zijlstra8e182572007-07-19 01:48:54 -07001277 return 0;
1278
Ming Leic94aa5c2009-07-16 15:44:29 +02001279 depth = get_lock_depth(target);
1280
Ming Leidb0002a2009-07-16 15:44:29 +02001281 print_circular_bug_header(target, depth, check_src, check_tgt);
Ming Leic94aa5c2009-07-16 15:44:29 +02001282
1283 parent = get_lock_parent(target);
Steven Rostedtf4185812011-04-20 21:41:55 -04001284 first_parent = parent;
Ming Leic94aa5c2009-07-16 15:44:29 +02001285
1286 while (parent) {
1287 print_circular_bug_entry(parent, --depth);
1288 parent = get_lock_parent(parent);
1289 }
Peter Zijlstra8e182572007-07-19 01:48:54 -07001290
1291 printk("\nother info that might help us debug this:\n\n");
Steven Rostedtf4185812011-04-20 21:41:55 -04001292 print_circular_lock_scenario(check_src, check_tgt,
1293 first_parent);
1294
Peter Zijlstra8e182572007-07-19 01:48:54 -07001295 lockdep_print_held_locks(curr);
1296
1297 printk("\nstack backtrace:\n");
1298 dump_stack();
1299
1300 return 0;
1301}
1302
Ming Leidb0002a2009-07-16 15:44:29 +02001303static noinline int print_bfs_bug(int ret)
1304{
1305 if (!debug_locks_off_graph_unlock())
1306 return 0;
1307
Peter Zijlstra0119fee2011-09-02 01:30:29 +02001308 /*
1309 * Breadth-first-search failed, graph got corrupted?
1310 */
Ming Leidb0002a2009-07-16 15:44:29 +02001311 WARN(1, "lockdep bfs error:%d\n", ret);
1312
1313 return 0;
1314}
1315
Ming Leief681022009-07-16 15:44:29 +02001316static int noop_count(struct lock_list *entry, void *data)
David Miller419ca3f2008-07-29 21:45:03 -07001317{
Ming Leief681022009-07-16 15:44:29 +02001318 (*(unsigned long *)data)++;
1319 return 0;
David Miller419ca3f2008-07-29 21:45:03 -07001320}
1321
Fengguang Wu5216d532013-11-09 00:55:35 +08001322static unsigned long __lockdep_count_forward_deps(struct lock_list *this)
Ming Leief681022009-07-16 15:44:29 +02001323{
1324 unsigned long count = 0;
1325 struct lock_list *uninitialized_var(target_entry);
1326
1327 __bfs_forwards(this, (void *)&count, noop_count, &target_entry);
1328
1329 return count;
1330}
David Miller419ca3f2008-07-29 21:45:03 -07001331unsigned long lockdep_count_forward_deps(struct lock_class *class)
1332{
1333 unsigned long ret, flags;
Ming Leief681022009-07-16 15:44:29 +02001334 struct lock_list this;
1335
1336 this.parent = NULL;
1337 this.class = class;
David Miller419ca3f2008-07-29 21:45:03 -07001338
Steven Rostedt (VMware)fcc784b2018-04-04 14:06:30 -04001339 raw_local_irq_save(flags);
Thomas Gleixner0199c4e2009-12-02 20:01:25 +01001340 arch_spin_lock(&lockdep_lock);
Ming Leief681022009-07-16 15:44:29 +02001341 ret = __lockdep_count_forward_deps(&this);
Thomas Gleixner0199c4e2009-12-02 20:01:25 +01001342 arch_spin_unlock(&lockdep_lock);
Steven Rostedt (VMware)fcc784b2018-04-04 14:06:30 -04001343 raw_local_irq_restore(flags);
David Miller419ca3f2008-07-29 21:45:03 -07001344
1345 return ret;
1346}
1347
Fengguang Wu5216d532013-11-09 00:55:35 +08001348static unsigned long __lockdep_count_backward_deps(struct lock_list *this)
David Miller419ca3f2008-07-29 21:45:03 -07001349{
Ming Leief681022009-07-16 15:44:29 +02001350 unsigned long count = 0;
1351 struct lock_list *uninitialized_var(target_entry);
David Miller419ca3f2008-07-29 21:45:03 -07001352
Ming Leief681022009-07-16 15:44:29 +02001353 __bfs_backwards(this, (void *)&count, noop_count, &target_entry);
David Miller419ca3f2008-07-29 21:45:03 -07001354
Ming Leief681022009-07-16 15:44:29 +02001355 return count;
David Miller419ca3f2008-07-29 21:45:03 -07001356}
1357
1358unsigned long lockdep_count_backward_deps(struct lock_class *class)
1359{
1360 unsigned long ret, flags;
Ming Leief681022009-07-16 15:44:29 +02001361 struct lock_list this;
1362
1363 this.parent = NULL;
1364 this.class = class;
David Miller419ca3f2008-07-29 21:45:03 -07001365
Steven Rostedt (VMware)fcc784b2018-04-04 14:06:30 -04001366 raw_local_irq_save(flags);
Thomas Gleixner0199c4e2009-12-02 20:01:25 +01001367 arch_spin_lock(&lockdep_lock);
Ming Leief681022009-07-16 15:44:29 +02001368 ret = __lockdep_count_backward_deps(&this);
Thomas Gleixner0199c4e2009-12-02 20:01:25 +01001369 arch_spin_unlock(&lockdep_lock);
Steven Rostedt (VMware)fcc784b2018-04-04 14:06:30 -04001370 raw_local_irq_restore(flags);
David Miller419ca3f2008-07-29 21:45:03 -07001371
1372 return ret;
1373}
1374
Peter Zijlstra8e182572007-07-19 01:48:54 -07001375/*
1376 * Prove that the dependency graph starting at <entry> can not
1377 * lead to <target>. Print an error and return 0 if it does.
1378 */
1379static noinline int
Ming Leidb0002a2009-07-16 15:44:29 +02001380check_noncircular(struct lock_list *root, struct lock_class *target,
1381 struct lock_list **target_entry)
Peter Zijlstra8e182572007-07-19 01:48:54 -07001382{
Ming Leidb0002a2009-07-16 15:44:29 +02001383 int result;
Peter Zijlstra8e182572007-07-19 01:48:54 -07001384
Frederic Weisbeckerbd6d29c2010-04-06 00:10:17 +02001385 debug_atomic_inc(nr_cyclic_checks);
David Miller419ca3f2008-07-29 21:45:03 -07001386
Ming Leid7aaba12009-07-16 15:44:29 +02001387 result = __bfs_forwards(root, target, class_equal, target_entry);
Ming Leidb0002a2009-07-16 15:44:29 +02001388
1389 return result;
Peter Zijlstra8e182572007-07-19 01:48:54 -07001390}
1391
Peter Zijlstraae813302017-03-03 10:13:38 +01001392static noinline int
1393check_redundant(struct lock_list *root, struct lock_class *target,
1394 struct lock_list **target_entry)
1395{
1396 int result;
1397
1398 debug_atomic_inc(nr_redundant_checks);
1399
1400 result = __bfs_forwards(root, target, class_equal, target_entry);
1401
1402 return result;
1403}
1404
Steven Rostedt81d68a92008-05-12 21:20:42 +02001405#if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING)
Peter Zijlstra8e182572007-07-19 01:48:54 -07001406/*
1407 * Forwards and backwards subgraph searching, for the purposes of
1408 * proving that two subgraphs can be connected by a new dependency
1409 * without creating any illegal irq-safe -> irq-unsafe lock dependency.
1410 */
Peter Zijlstra8e182572007-07-19 01:48:54 -07001411
Ming Leid7aaba12009-07-16 15:44:29 +02001412static inline int usage_match(struct lock_list *entry, void *bit)
1413{
1414 return entry->class->usage_mask & (1 << (enum lock_usage_bit)bit);
1415}
1416
1417
1418
Peter Zijlstra8e182572007-07-19 01:48:54 -07001419/*
1420 * Find a node in the forwards-direction dependency sub-graph starting
Ming Leid7aaba12009-07-16 15:44:29 +02001421 * at @root->class that matches @bit.
Peter Zijlstra8e182572007-07-19 01:48:54 -07001422 *
Ming Leid7aaba12009-07-16 15:44:29 +02001423 * Return 0 if such a node exists in the subgraph, and put that node
1424 * into *@target_entry.
Peter Zijlstra8e182572007-07-19 01:48:54 -07001425 *
Ming Leid7aaba12009-07-16 15:44:29 +02001426 * Return 1 otherwise and keep *@target_entry unchanged.
1427 * Return <0 on error.
Peter Zijlstra8e182572007-07-19 01:48:54 -07001428 */
Ming Leid7aaba12009-07-16 15:44:29 +02001429static int
1430find_usage_forwards(struct lock_list *root, enum lock_usage_bit bit,
1431 struct lock_list **target_entry)
Peter Zijlstra8e182572007-07-19 01:48:54 -07001432{
Ming Leid7aaba12009-07-16 15:44:29 +02001433 int result;
Peter Zijlstra8e182572007-07-19 01:48:54 -07001434
Frederic Weisbeckerbd6d29c2010-04-06 00:10:17 +02001435 debug_atomic_inc(nr_find_usage_forwards_checks);
Peter Zijlstra8e182572007-07-19 01:48:54 -07001436
Ming Leid7aaba12009-07-16 15:44:29 +02001437 result = __bfs_forwards(root, (void *)bit, usage_match, target_entry);
1438
1439 return result;
Peter Zijlstra8e182572007-07-19 01:48:54 -07001440}
1441
1442/*
1443 * Find a node in the backwards-direction dependency sub-graph starting
Ming Leid7aaba12009-07-16 15:44:29 +02001444 * at @root->class that matches @bit.
Peter Zijlstra8e182572007-07-19 01:48:54 -07001445 *
Ming Leid7aaba12009-07-16 15:44:29 +02001446 * Return 0 if such a node exists in the subgraph, and put that node
1447 * into *@target_entry.
Peter Zijlstra8e182572007-07-19 01:48:54 -07001448 *
Ming Leid7aaba12009-07-16 15:44:29 +02001449 * Return 1 otherwise and keep *@target_entry unchanged.
1450 * Return <0 on error.
Peter Zijlstra8e182572007-07-19 01:48:54 -07001451 */
Ming Leid7aaba12009-07-16 15:44:29 +02001452static int
1453find_usage_backwards(struct lock_list *root, enum lock_usage_bit bit,
1454 struct lock_list **target_entry)
Peter Zijlstra8e182572007-07-19 01:48:54 -07001455{
Ming Leid7aaba12009-07-16 15:44:29 +02001456 int result;
Peter Zijlstra8e182572007-07-19 01:48:54 -07001457
Frederic Weisbeckerbd6d29c2010-04-06 00:10:17 +02001458 debug_atomic_inc(nr_find_usage_backwards_checks);
Peter Zijlstra8e182572007-07-19 01:48:54 -07001459
Ming Leid7aaba12009-07-16 15:44:29 +02001460 result = __bfs_backwards(root, (void *)bit, usage_match, target_entry);
Dave Jonesf82b2172008-08-11 09:30:23 +02001461
Ming Leid7aaba12009-07-16 15:44:29 +02001462 return result;
Peter Zijlstra8e182572007-07-19 01:48:54 -07001463}
1464
Peter Zijlstraaf012962009-07-16 15:44:29 +02001465static void print_lock_class_header(struct lock_class *class, int depth)
1466{
1467 int bit;
1468
1469 printk("%*s->", depth, "");
1470 print_lock_name(class);
Waiman Long8ca2b56c2018-10-03 13:07:18 -04001471#ifdef CONFIG_DEBUG_LOCKDEP
1472 printk(KERN_CONT " ops: %lu", debug_class_ops_read(class));
1473#endif
Dmitry Vyukovf943fe02016-11-28 15:24:43 +01001474 printk(KERN_CONT " {\n");
Peter Zijlstraaf012962009-07-16 15:44:29 +02001475
1476 for (bit = 0; bit < LOCK_USAGE_STATES; bit++) {
1477 if (class->usage_mask & (1 << bit)) {
1478 int len = depth;
1479
1480 len += printk("%*s %s", depth, "", usage_str[bit]);
Dmitry Vyukovf943fe02016-11-28 15:24:43 +01001481 len += printk(KERN_CONT " at:\n");
Peter Zijlstraaf012962009-07-16 15:44:29 +02001482 print_stack_trace(class->usage_traces + bit, len);
1483 }
1484 }
1485 printk("%*s }\n", depth, "");
1486
Borislav Petkov04860d42018-02-26 14:49:26 +01001487 printk("%*s ... key at: [<%px>] %pS\n",
Dmitry Vyukovf943fe02016-11-28 15:24:43 +01001488 depth, "", class->key, class->key);
Peter Zijlstraaf012962009-07-16 15:44:29 +02001489}
1490
1491/*
1492 * printk the shortest lock dependencies from @start to @end in reverse order:
1493 */
1494static void __used
1495print_shortest_lock_dependencies(struct lock_list *leaf,
1496 struct lock_list *root)
1497{
1498 struct lock_list *entry = leaf;
1499 int depth;
1500
1501 /*compute depth from generated tree by BFS*/
1502 depth = get_lock_depth(leaf);
1503
1504 do {
1505 print_lock_class_header(entry->class, depth);
1506 printk("%*s ... acquired at:\n", depth, "");
1507 print_stack_trace(&entry->trace, 2);
1508 printk("\n");
1509
1510 if (depth == 0 && (entry != root)) {
Steven Rostedt6be8c392011-04-20 21:41:58 -04001511 printk("lockdep:%s bad path found in chain graph\n", __func__);
Peter Zijlstraaf012962009-07-16 15:44:29 +02001512 break;
1513 }
1514
1515 entry = get_lock_parent(entry);
1516 depth--;
1517 } while (entry && (depth >= 0));
1518
1519 return;
1520}
Ming Leid7aaba12009-07-16 15:44:29 +02001521
Steven Rostedt3003eba2011-04-20 21:41:54 -04001522static void
1523print_irq_lock_scenario(struct lock_list *safe_entry,
1524 struct lock_list *unsafe_entry,
Steven Rostedtdad3d742011-04-20 21:41:57 -04001525 struct lock_class *prev_class,
1526 struct lock_class *next_class)
Steven Rostedt3003eba2011-04-20 21:41:54 -04001527{
1528 struct lock_class *safe_class = safe_entry->class;
1529 struct lock_class *unsafe_class = unsafe_entry->class;
Steven Rostedtdad3d742011-04-20 21:41:57 -04001530 struct lock_class *middle_class = prev_class;
Steven Rostedt3003eba2011-04-20 21:41:54 -04001531
1532 if (middle_class == safe_class)
Steven Rostedtdad3d742011-04-20 21:41:57 -04001533 middle_class = next_class;
Steven Rostedt3003eba2011-04-20 21:41:54 -04001534
1535 /*
1536 * A direct locking problem where unsafe_class lock is taken
1537 * directly by safe_class lock, then all we need to show
1538 * is the deadlock scenario, as it is obvious that the
1539 * unsafe lock is taken under the safe lock.
1540 *
1541 * But if there is a chain instead, where the safe lock takes
1542 * an intermediate lock (middle_class) where this lock is
1543 * not the same as the safe lock, then the lock chain is
1544 * used to describe the problem. Otherwise we would need
1545 * to show a different CPU case for each link in the chain
1546 * from the safe_class lock to the unsafe_class lock.
1547 */
1548 if (middle_class != unsafe_class) {
1549 printk("Chain exists of:\n ");
1550 __print_lock_name(safe_class);
Dmitry Vyukovf943fe02016-11-28 15:24:43 +01001551 printk(KERN_CONT " --> ");
Steven Rostedt3003eba2011-04-20 21:41:54 -04001552 __print_lock_name(middle_class);
Dmitry Vyukovf943fe02016-11-28 15:24:43 +01001553 printk(KERN_CONT " --> ");
Steven Rostedt3003eba2011-04-20 21:41:54 -04001554 __print_lock_name(unsafe_class);
Dmitry Vyukovf943fe02016-11-28 15:24:43 +01001555 printk(KERN_CONT "\n\n");
Steven Rostedt3003eba2011-04-20 21:41:54 -04001556 }
1557
1558 printk(" Possible interrupt unsafe locking scenario:\n\n");
1559 printk(" CPU0 CPU1\n");
1560 printk(" ---- ----\n");
1561 printk(" lock(");
1562 __print_lock_name(unsafe_class);
Dmitry Vyukovf943fe02016-11-28 15:24:43 +01001563 printk(KERN_CONT ");\n");
Steven Rostedt3003eba2011-04-20 21:41:54 -04001564 printk(" local_irq_disable();\n");
1565 printk(" lock(");
1566 __print_lock_name(safe_class);
Dmitry Vyukovf943fe02016-11-28 15:24:43 +01001567 printk(KERN_CONT ");\n");
Steven Rostedt3003eba2011-04-20 21:41:54 -04001568 printk(" lock(");
1569 __print_lock_name(middle_class);
Dmitry Vyukovf943fe02016-11-28 15:24:43 +01001570 printk(KERN_CONT ");\n");
Steven Rostedt3003eba2011-04-20 21:41:54 -04001571 printk(" <Interrupt>\n");
1572 printk(" lock(");
1573 __print_lock_name(safe_class);
Dmitry Vyukovf943fe02016-11-28 15:24:43 +01001574 printk(KERN_CONT ");\n");
Steven Rostedt3003eba2011-04-20 21:41:54 -04001575 printk("\n *** DEADLOCK ***\n\n");
1576}
1577
Peter Zijlstra8e182572007-07-19 01:48:54 -07001578static int
1579print_bad_irq_dependency(struct task_struct *curr,
Ming Lei24208ca2009-07-16 15:44:29 +02001580 struct lock_list *prev_root,
1581 struct lock_list *next_root,
1582 struct lock_list *backwards_entry,
1583 struct lock_list *forwards_entry,
Peter Zijlstra8e182572007-07-19 01:48:54 -07001584 struct held_lock *prev,
1585 struct held_lock *next,
1586 enum lock_usage_bit bit1,
1587 enum lock_usage_bit bit2,
1588 const char *irqclass)
1589{
1590 if (!debug_locks_off_graph_unlock() || debug_locks_silent)
1591 return 0;
1592
Paul E. McKenney681fbec2017-05-04 15:44:38 -07001593 pr_warn("\n");
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08001594 pr_warn("=====================================================\n");
1595 pr_warn("WARNING: %s-safe -> %s-unsafe lock order detected\n",
Peter Zijlstra8e182572007-07-19 01:48:54 -07001596 irqclass, irqclass);
Ben Hutchingsfbdc4b92011-10-28 04:36:55 +01001597 print_kernel_ident();
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08001598 pr_warn("-----------------------------------------------------\n");
Paul E. McKenney681fbec2017-05-04 15:44:38 -07001599 pr_warn("%s/%d [HC%u[%lu]:SC%u[%lu]:HE%u:SE%u] is trying to acquire:\n",
Pavel Emelyanovba25f9d2007-10-18 23:40:40 -07001600 curr->comm, task_pid_nr(curr),
Peter Zijlstra8e182572007-07-19 01:48:54 -07001601 curr->hardirq_context, hardirq_count() >> HARDIRQ_SHIFT,
1602 curr->softirq_context, softirq_count() >> SOFTIRQ_SHIFT,
1603 curr->hardirqs_enabled,
1604 curr->softirqs_enabled);
1605 print_lock(next);
1606
Paul E. McKenney681fbec2017-05-04 15:44:38 -07001607 pr_warn("\nand this task is already holding:\n");
Peter Zijlstra8e182572007-07-19 01:48:54 -07001608 print_lock(prev);
Paul E. McKenney681fbec2017-05-04 15:44:38 -07001609 pr_warn("which would create a new lock dependency:\n");
Dave Jonesf82b2172008-08-11 09:30:23 +02001610 print_lock_name(hlock_class(prev));
Paul E. McKenney681fbec2017-05-04 15:44:38 -07001611 pr_cont(" ->");
Dave Jonesf82b2172008-08-11 09:30:23 +02001612 print_lock_name(hlock_class(next));
Paul E. McKenney681fbec2017-05-04 15:44:38 -07001613 pr_cont("\n");
Peter Zijlstra8e182572007-07-19 01:48:54 -07001614
Paul E. McKenney681fbec2017-05-04 15:44:38 -07001615 pr_warn("\nbut this new dependency connects a %s-irq-safe lock:\n",
Peter Zijlstra8e182572007-07-19 01:48:54 -07001616 irqclass);
Ming Lei24208ca2009-07-16 15:44:29 +02001617 print_lock_name(backwards_entry->class);
Paul E. McKenney681fbec2017-05-04 15:44:38 -07001618 pr_warn("\n... which became %s-irq-safe at:\n", irqclass);
Peter Zijlstra8e182572007-07-19 01:48:54 -07001619
Ming Lei24208ca2009-07-16 15:44:29 +02001620 print_stack_trace(backwards_entry->class->usage_traces + bit1, 1);
Peter Zijlstra8e182572007-07-19 01:48:54 -07001621
Paul E. McKenney681fbec2017-05-04 15:44:38 -07001622 pr_warn("\nto a %s-irq-unsafe lock:\n", irqclass);
Ming Lei24208ca2009-07-16 15:44:29 +02001623 print_lock_name(forwards_entry->class);
Paul E. McKenney681fbec2017-05-04 15:44:38 -07001624 pr_warn("\n... which became %s-irq-unsafe at:\n", irqclass);
1625 pr_warn("...");
Peter Zijlstra8e182572007-07-19 01:48:54 -07001626
Ming Lei24208ca2009-07-16 15:44:29 +02001627 print_stack_trace(forwards_entry->class->usage_traces + bit2, 1);
Peter Zijlstra8e182572007-07-19 01:48:54 -07001628
Paul E. McKenney681fbec2017-05-04 15:44:38 -07001629 pr_warn("\nother info that might help us debug this:\n\n");
Steven Rostedtdad3d742011-04-20 21:41:57 -04001630 print_irq_lock_scenario(backwards_entry, forwards_entry,
1631 hlock_class(prev), hlock_class(next));
Steven Rostedt3003eba2011-04-20 21:41:54 -04001632
Peter Zijlstra8e182572007-07-19 01:48:54 -07001633 lockdep_print_held_locks(curr);
1634
Paul E. McKenney681fbec2017-05-04 15:44:38 -07001635 pr_warn("\nthe dependencies between %s-irq-safe lock and the holding lock:\n", irqclass);
Ming Lei24208ca2009-07-16 15:44:29 +02001636 if (!save_trace(&prev_root->trace))
1637 return 0;
1638 print_shortest_lock_dependencies(backwards_entry, prev_root);
Peter Zijlstra8e182572007-07-19 01:48:54 -07001639
Paul E. McKenney681fbec2017-05-04 15:44:38 -07001640 pr_warn("\nthe dependencies between the lock to be acquired");
1641 pr_warn(" and %s-irq-unsafe lock:\n", irqclass);
Ming Lei24208ca2009-07-16 15:44:29 +02001642 if (!save_trace(&next_root->trace))
1643 return 0;
1644 print_shortest_lock_dependencies(forwards_entry, next_root);
Peter Zijlstra8e182572007-07-19 01:48:54 -07001645
Paul E. McKenney681fbec2017-05-04 15:44:38 -07001646 pr_warn("\nstack backtrace:\n");
Peter Zijlstra8e182572007-07-19 01:48:54 -07001647 dump_stack();
1648
1649 return 0;
1650}
1651
1652static int
1653check_usage(struct task_struct *curr, struct held_lock *prev,
1654 struct held_lock *next, enum lock_usage_bit bit_backwards,
1655 enum lock_usage_bit bit_forwards, const char *irqclass)
1656{
1657 int ret;
Ming Lei24208ca2009-07-16 15:44:29 +02001658 struct lock_list this, that;
Ming Leid7aaba12009-07-16 15:44:29 +02001659 struct lock_list *uninitialized_var(target_entry);
Ming Lei24208ca2009-07-16 15:44:29 +02001660 struct lock_list *uninitialized_var(target_entry1);
Peter Zijlstra8e182572007-07-19 01:48:54 -07001661
Ming Leid7aaba12009-07-16 15:44:29 +02001662 this.parent = NULL;
Peter Zijlstra8e182572007-07-19 01:48:54 -07001663
Ming Leid7aaba12009-07-16 15:44:29 +02001664 this.class = hlock_class(prev);
1665 ret = find_usage_backwards(&this, bit_backwards, &target_entry);
Peter Zijlstraaf012962009-07-16 15:44:29 +02001666 if (ret < 0)
1667 return print_bfs_bug(ret);
1668 if (ret == 1)
1669 return ret;
Ming Leid7aaba12009-07-16 15:44:29 +02001670
Ming Lei24208ca2009-07-16 15:44:29 +02001671 that.parent = NULL;
1672 that.class = hlock_class(next);
1673 ret = find_usage_forwards(&that, bit_forwards, &target_entry1);
Peter Zijlstraaf012962009-07-16 15:44:29 +02001674 if (ret < 0)
1675 return print_bfs_bug(ret);
1676 if (ret == 1)
1677 return ret;
Ming Leid7aaba12009-07-16 15:44:29 +02001678
Ming Lei24208ca2009-07-16 15:44:29 +02001679 return print_bad_irq_dependency(curr, &this, &that,
1680 target_entry, target_entry1,
1681 prev, next,
Peter Zijlstra8e182572007-07-19 01:48:54 -07001682 bit_backwards, bit_forwards, irqclass);
1683}
1684
Peter Zijlstra4f367d8a2009-01-22 18:10:42 +01001685static const char *state_names[] = {
1686#define LOCKDEP_STATE(__STATE) \
Peter Zijlstrab4b136f2009-01-29 14:50:36 +01001687 __stringify(__STATE),
Peter Zijlstra4f367d8a2009-01-22 18:10:42 +01001688#include "lockdep_states.h"
1689#undef LOCKDEP_STATE
1690};
1691
1692static const char *state_rnames[] = {
1693#define LOCKDEP_STATE(__STATE) \
Peter Zijlstrab4b136f2009-01-29 14:50:36 +01001694 __stringify(__STATE)"-READ",
Peter Zijlstra4f367d8a2009-01-22 18:10:42 +01001695#include "lockdep_states.h"
1696#undef LOCKDEP_STATE
1697};
1698
1699static inline const char *state_name(enum lock_usage_bit bit)
1700{
Frederic Weisbeckerbba2a8f2018-12-28 06:02:01 +01001701 return (bit & LOCK_USAGE_READ_MASK) ? state_rnames[bit >> 2] : state_names[bit >> 2];
Peter Zijlstra4f367d8a2009-01-22 18:10:42 +01001702}
1703
1704static int exclusive_bit(int new_bit)
1705{
Frederic Weisbeckerbba2a8f2018-12-28 06:02:01 +01001706 int state = new_bit & LOCK_USAGE_STATE_MASK;
1707 int dir = new_bit & LOCK_USAGE_DIR_MASK;
Peter Zijlstra4f367d8a2009-01-22 18:10:42 +01001708
1709 /*
1710 * keep state, bit flip the direction and strip read.
1711 */
Frederic Weisbeckerbba2a8f2018-12-28 06:02:01 +01001712 return state | (dir ^ LOCK_USAGE_DIR_MASK);
Peter Zijlstra4f367d8a2009-01-22 18:10:42 +01001713}
1714
1715static int check_irq_usage(struct task_struct *curr, struct held_lock *prev,
1716 struct held_lock *next, enum lock_usage_bit bit)
Peter Zijlstra8e182572007-07-19 01:48:54 -07001717{
1718 /*
1719 * Prove that the new dependency does not connect a hardirq-safe
1720 * lock with a hardirq-unsafe lock - to achieve this we search
1721 * the backwards-subgraph starting at <prev>, and the
1722 * forwards-subgraph starting at <next>:
1723 */
Peter Zijlstra4f367d8a2009-01-22 18:10:42 +01001724 if (!check_usage(curr, prev, next, bit,
1725 exclusive_bit(bit), state_name(bit)))
Peter Zijlstra8e182572007-07-19 01:48:54 -07001726 return 0;
1727
Peter Zijlstra4f367d8a2009-01-22 18:10:42 +01001728 bit++; /* _READ */
1729
Peter Zijlstra8e182572007-07-19 01:48:54 -07001730 /*
1731 * Prove that the new dependency does not connect a hardirq-safe-read
1732 * lock with a hardirq-unsafe lock - to achieve this we search
1733 * the backwards-subgraph starting at <prev>, and the
1734 * forwards-subgraph starting at <next>:
1735 */
Peter Zijlstra4f367d8a2009-01-22 18:10:42 +01001736 if (!check_usage(curr, prev, next, bit,
1737 exclusive_bit(bit), state_name(bit)))
Peter Zijlstra8e182572007-07-19 01:48:54 -07001738 return 0;
1739
Peter Zijlstra4f367d8a2009-01-22 18:10:42 +01001740 return 1;
1741}
Peter Zijlstra8e182572007-07-19 01:48:54 -07001742
Peter Zijlstra4f367d8a2009-01-22 18:10:42 +01001743static int
1744check_prev_add_irq(struct task_struct *curr, struct held_lock *prev,
1745 struct held_lock *next)
1746{
1747#define LOCKDEP_STATE(__STATE) \
1748 if (!check_irq_usage(curr, prev, next, LOCK_USED_IN_##__STATE)) \
Nick Piggincf40bd12009-01-21 08:12:39 +01001749 return 0;
Peter Zijlstra4f367d8a2009-01-22 18:10:42 +01001750#include "lockdep_states.h"
1751#undef LOCKDEP_STATE
Nick Piggincf40bd12009-01-21 08:12:39 +01001752
Peter Zijlstra8e182572007-07-19 01:48:54 -07001753 return 1;
1754}
1755
1756static void inc_chains(void)
1757{
1758 if (current->hardirq_context)
1759 nr_hardirq_chains++;
1760 else {
1761 if (current->softirq_context)
1762 nr_softirq_chains++;
1763 else
1764 nr_process_chains++;
1765 }
1766}
1767
1768#else
1769
1770static inline int
1771check_prev_add_irq(struct task_struct *curr, struct held_lock *prev,
1772 struct held_lock *next)
1773{
1774 return 1;
1775}
1776
1777static inline void inc_chains(void)
1778{
1779 nr_process_chains++;
1780}
1781
1782#endif
1783
Steven Rostedt48702ec2011-04-20 21:41:56 -04001784static void
1785print_deadlock_scenario(struct held_lock *nxt,
1786 struct held_lock *prv)
1787{
1788 struct lock_class *next = hlock_class(nxt);
1789 struct lock_class *prev = hlock_class(prv);
1790
1791 printk(" Possible unsafe locking scenario:\n\n");
1792 printk(" CPU0\n");
1793 printk(" ----\n");
1794 printk(" lock(");
1795 __print_lock_name(prev);
Dmitry Vyukovf943fe02016-11-28 15:24:43 +01001796 printk(KERN_CONT ");\n");
Steven Rostedt48702ec2011-04-20 21:41:56 -04001797 printk(" lock(");
1798 __print_lock_name(next);
Dmitry Vyukovf943fe02016-11-28 15:24:43 +01001799 printk(KERN_CONT ");\n");
Steven Rostedt48702ec2011-04-20 21:41:56 -04001800 printk("\n *** DEADLOCK ***\n\n");
1801 printk(" May be due to missing lock nesting notation\n\n");
1802}
1803
Peter Zijlstra8e182572007-07-19 01:48:54 -07001804static int
1805print_deadlock_bug(struct task_struct *curr, struct held_lock *prev,
1806 struct held_lock *next)
1807{
1808 if (!debug_locks_off_graph_unlock() || debug_locks_silent)
1809 return 0;
1810
Paul E. McKenney681fbec2017-05-04 15:44:38 -07001811 pr_warn("\n");
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08001812 pr_warn("============================================\n");
1813 pr_warn("WARNING: possible recursive locking detected\n");
Ben Hutchingsfbdc4b92011-10-28 04:36:55 +01001814 print_kernel_ident();
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08001815 pr_warn("--------------------------------------------\n");
Paul E. McKenney681fbec2017-05-04 15:44:38 -07001816 pr_warn("%s/%d is trying to acquire lock:\n",
Pavel Emelyanovba25f9d2007-10-18 23:40:40 -07001817 curr->comm, task_pid_nr(curr));
Peter Zijlstra8e182572007-07-19 01:48:54 -07001818 print_lock(next);
Paul E. McKenney681fbec2017-05-04 15:44:38 -07001819 pr_warn("\nbut task is already holding lock:\n");
Peter Zijlstra8e182572007-07-19 01:48:54 -07001820 print_lock(prev);
1821
Paul E. McKenney681fbec2017-05-04 15:44:38 -07001822 pr_warn("\nother info that might help us debug this:\n");
Steven Rostedt48702ec2011-04-20 21:41:56 -04001823 print_deadlock_scenario(next, prev);
Peter Zijlstra8e182572007-07-19 01:48:54 -07001824 lockdep_print_held_locks(curr);
1825
Paul E. McKenney681fbec2017-05-04 15:44:38 -07001826 pr_warn("\nstack backtrace:\n");
Peter Zijlstra8e182572007-07-19 01:48:54 -07001827 dump_stack();
1828
1829 return 0;
1830}
1831
1832/*
1833 * Check whether we are holding such a class already.
1834 *
1835 * (Note that this has to be done separately, because the graph cannot
1836 * detect such classes of deadlocks.)
1837 *
1838 * Returns: 0 on deadlock detected, 1 on OK, 2 on recursive read
1839 */
1840static int
1841check_deadlock(struct task_struct *curr, struct held_lock *next,
1842 struct lockdep_map *next_instance, int read)
1843{
1844 struct held_lock *prev;
Peter Zijlstra7531e2f2008-08-11 09:30:24 +02001845 struct held_lock *nest = NULL;
Peter Zijlstra8e182572007-07-19 01:48:54 -07001846 int i;
1847
1848 for (i = 0; i < curr->lockdep_depth; i++) {
1849 prev = curr->held_locks + i;
Peter Zijlstra7531e2f2008-08-11 09:30:24 +02001850
1851 if (prev->instance == next->nest_lock)
1852 nest = prev;
1853
Dave Jonesf82b2172008-08-11 09:30:23 +02001854 if (hlock_class(prev) != hlock_class(next))
Peter Zijlstra8e182572007-07-19 01:48:54 -07001855 continue;
Peter Zijlstra7531e2f2008-08-11 09:30:24 +02001856
Peter Zijlstra8e182572007-07-19 01:48:54 -07001857 /*
1858 * Allow read-after-read recursion of the same
1859 * lock class (i.e. read_lock(lock)+read_lock(lock)):
1860 */
1861 if ((read == 2) && prev->read)
1862 return 2;
Peter Zijlstra7531e2f2008-08-11 09:30:24 +02001863
1864 /*
1865 * We're holding the nest_lock, which serializes this lock's
1866 * nesting behaviour.
1867 */
1868 if (nest)
1869 return 2;
1870
Peter Zijlstra8e182572007-07-19 01:48:54 -07001871 return print_deadlock_bug(curr, prev, next);
1872 }
1873 return 1;
1874}
1875
1876/*
1877 * There was a chain-cache miss, and we are about to add a new dependency
1878 * to a previous lock. We recursively validate the following rules:
1879 *
1880 * - would the adding of the <prev> -> <next> dependency create a
1881 * circular dependency in the graph? [== circular deadlock]
1882 *
1883 * - does the new prev->next dependency connect any hardirq-safe lock
1884 * (in the full backwards-subgraph starting at <prev>) with any
1885 * hardirq-unsafe lock (in the full forwards-subgraph starting at
1886 * <next>)? [== illegal lock inversion with hardirq contexts]
1887 *
1888 * - does the new prev->next dependency connect any softirq-safe lock
1889 * (in the full backwards-subgraph starting at <prev>) with any
1890 * softirq-unsafe lock (in the full forwards-subgraph starting at
1891 * <next>)? [== illegal lock inversion with softirq contexts]
1892 *
1893 * any of these scenarios could lead to a deadlock.
1894 *
1895 * Then if all the validations pass, we add the forwards and backwards
1896 * dependency.
1897 */
1898static int
1899check_prev_add(struct task_struct *curr, struct held_lock *prev,
Byungchul Parkce07a9412017-08-07 16:12:51 +09001900 struct held_lock *next, int distance, struct stack_trace *trace,
1901 int (*save)(struct stack_trace *trace))
Peter Zijlstra8e182572007-07-19 01:48:54 -07001902{
Ming Leidb0002a2009-07-16 15:44:29 +02001903 struct lock_list *uninitialized_var(target_entry);
Peter Zijlstra8b405d52017-10-04 11:13:37 +02001904 struct lock_list *entry;
1905 struct lock_list this;
1906 int ret;
Peter Zijlstra8e182572007-07-19 01:48:54 -07001907
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08001908 if (!hlock_class(prev)->key || !hlock_class(next)->key) {
1909 /*
1910 * The warning statements below may trigger a use-after-free
1911 * of the class name. It is better to trigger a use-after free
1912 * and to have the class name most of the time instead of not
1913 * having the class name available.
1914 */
1915 WARN_ONCE(!debug_locks_silent && !hlock_class(prev)->key,
1916 "Detected use-after-free of lock class %px/%s\n",
1917 hlock_class(prev),
1918 hlock_class(prev)->name);
1919 WARN_ONCE(!debug_locks_silent && !hlock_class(next)->key,
1920 "Detected use-after-free of lock class %px/%s\n",
1921 hlock_class(next),
1922 hlock_class(next)->name);
1923 return 2;
1924 }
1925
Peter Zijlstra8e182572007-07-19 01:48:54 -07001926 /*
1927 * Prove that the new <prev> -> <next> dependency would not
1928 * create a circular dependency in the graph. (We do this by
1929 * forward-recursing into the graph starting at <next>, and
1930 * checking whether we can reach <prev>.)
1931 *
1932 * We are using global variables to control the recursion, to
1933 * keep the stackframe size of the recursive functions low:
1934 */
Ming Leidb0002a2009-07-16 15:44:29 +02001935 this.class = hlock_class(next);
1936 this.parent = NULL;
1937 ret = check_noncircular(&this, hlock_class(prev), &target_entry);
Peter Zijlstra8b405d52017-10-04 11:13:37 +02001938 if (unlikely(!ret)) {
1939 if (!trace->entries) {
1940 /*
1941 * If @save fails here, the printing might trigger
1942 * a WARN but because of the !nr_entries it should
1943 * not do bad things.
1944 */
1945 save(trace);
1946 }
Byungchul Park383a4bc2017-08-07 16:12:55 +09001947 return print_circular_bug(&this, target_entry, next, prev, trace);
Peter Zijlstra8b405d52017-10-04 11:13:37 +02001948 }
Ming Leidb0002a2009-07-16 15:44:29 +02001949 else if (unlikely(ret < 0))
1950 return print_bfs_bug(ret);
Ming Leic94aa5c2009-07-16 15:44:29 +02001951
Peter Zijlstra8e182572007-07-19 01:48:54 -07001952 if (!check_prev_add_irq(curr, prev, next))
1953 return 0;
1954
1955 /*
1956 * For recursive read-locks we do all the dependency checks,
1957 * but we dont store read-triggered dependencies (only
1958 * write-triggered dependencies). This ensures that only the
1959 * write-side dependencies matter, and that if for example a
1960 * write-lock never takes any other locks, then the reads are
1961 * equivalent to a NOP.
1962 */
1963 if (next->read == 2 || prev->read == 2)
1964 return 1;
1965 /*
1966 * Is the <prev> -> <next> dependency already present?
1967 *
1968 * (this may occur even though this is a new chain: consider
1969 * e.g. the L1 -> L2 -> L3 -> L4 and the L5 -> L1 -> L2 -> L3
1970 * chains - the second one will be new, but L1 already has
1971 * L2 added to its dependency list, due to the first chain.)
1972 */
Dave Jonesf82b2172008-08-11 09:30:23 +02001973 list_for_each_entry(entry, &hlock_class(prev)->locks_after, entry) {
1974 if (entry->class == hlock_class(next)) {
Peter Zijlstra8e182572007-07-19 01:48:54 -07001975 if (distance == 1)
1976 entry->distance = 1;
Byungchul Park70911fd2017-08-07 16:12:50 +09001977 return 1;
Peter Zijlstra8e182572007-07-19 01:48:54 -07001978 }
1979 }
1980
Peter Zijlstraae813302017-03-03 10:13:38 +01001981 /*
1982 * Is the <prev> -> <next> link redundant?
1983 */
1984 this.class = hlock_class(prev);
1985 this.parent = NULL;
1986 ret = check_redundant(&this, hlock_class(next), &target_entry);
1987 if (!ret) {
1988 debug_atomic_inc(nr_redundant);
1989 return 2;
1990 }
1991 if (ret < 0)
1992 return print_bfs_bug(ret);
1993
1994
Peter Zijlstra8b405d52017-10-04 11:13:37 +02001995 if (!trace->entries && !save(trace))
Byungchul Parkce07a9412017-08-07 16:12:51 +09001996 return 0;
Yong Zhang4726f2a2010-05-04 14:16:48 +08001997
Peter Zijlstra8e182572007-07-19 01:48:54 -07001998 /*
1999 * Ok, all validations passed, add the new lock
2000 * to the previous lock's dependency list:
2001 */
Bart Van Assche86cffb82019-02-14 15:00:41 -08002002 ret = add_lock_to_list(hlock_class(next), hlock_class(prev),
Dave Jonesf82b2172008-08-11 09:30:23 +02002003 &hlock_class(prev)->locks_after,
Byungchul Parkce07a9412017-08-07 16:12:51 +09002004 next->acquire_ip, distance, trace);
Peter Zijlstra8e182572007-07-19 01:48:54 -07002005
2006 if (!ret)
2007 return 0;
2008
Bart Van Assche86cffb82019-02-14 15:00:41 -08002009 ret = add_lock_to_list(hlock_class(prev), hlock_class(next),
Dave Jonesf82b2172008-08-11 09:30:23 +02002010 &hlock_class(next)->locks_before,
Byungchul Parkce07a9412017-08-07 16:12:51 +09002011 next->acquire_ip, distance, trace);
Peter Zijlstra8e182572007-07-19 01:48:54 -07002012 if (!ret)
2013 return 0;
2014
Byungchul Park70911fd2017-08-07 16:12:50 +09002015 return 2;
Peter Zijlstra8e182572007-07-19 01:48:54 -07002016}
2017
2018/*
2019 * Add the dependency to all directly-previous locks that are 'relevant'.
2020 * The ones that are relevant are (in increasing distance from curr):
2021 * all consecutive trylock entries and the final non-trylock entry - or
2022 * the end of this context's lock-chain - whichever comes first.
2023 */
2024static int
2025check_prevs_add(struct task_struct *curr, struct held_lock *next)
2026{
2027 int depth = curr->lockdep_depth;
2028 struct held_lock *hlock;
Peter Zijlstra8b405d52017-10-04 11:13:37 +02002029 struct stack_trace trace = {
2030 .nr_entries = 0,
2031 .max_entries = 0,
2032 .entries = NULL,
2033 .skip = 0,
2034 };
Peter Zijlstra8e182572007-07-19 01:48:54 -07002035
2036 /*
2037 * Debugging checks.
2038 *
2039 * Depth must not be zero for a non-head lock:
2040 */
2041 if (!depth)
2042 goto out_bug;
2043 /*
2044 * At least two relevant locks must exist for this
2045 * to be a head:
2046 */
2047 if (curr->held_locks[depth].irq_context !=
2048 curr->held_locks[depth-1].irq_context)
2049 goto out_bug;
2050
2051 for (;;) {
2052 int distance = curr->lockdep_depth - depth + 1;
Oleg Nesterov1b5ff812014-01-20 19:20:10 +01002053 hlock = curr->held_locks + depth - 1;
Byungchul Parkce07a9412017-08-07 16:12:51 +09002054
Ingo Molnare966eae2017-12-12 12:31:16 +01002055 /*
2056 * Only non-recursive-read entries get new dependencies
2057 * added:
2058 */
2059 if (hlock->read != 2 && hlock->check) {
2060 int ret = check_prev_add(curr, hlock, next, distance, &trace, save_trace);
2061 if (!ret)
2062 return 0;
2063
2064 /*
2065 * Stop after the first non-trylock entry,
2066 * as non-trylock entries have added their
2067 * own direct dependencies already, so this
2068 * lock is connected to them indirectly:
2069 */
2070 if (!hlock->trylock)
2071 break;
Peter Zijlstra8e182572007-07-19 01:48:54 -07002072 }
Ingo Molnare966eae2017-12-12 12:31:16 +01002073
Peter Zijlstra8e182572007-07-19 01:48:54 -07002074 depth--;
2075 /*
2076 * End of lock-stack?
2077 */
2078 if (!depth)
2079 break;
2080 /*
2081 * Stop the search if we cross into another context:
2082 */
2083 if (curr->held_locks[depth].irq_context !=
2084 curr->held_locks[depth-1].irq_context)
2085 break;
2086 }
2087 return 1;
2088out_bug:
2089 if (!debug_locks_off_graph_unlock())
2090 return 0;
2091
Peter Zijlstra0119fee2011-09-02 01:30:29 +02002092 /*
2093 * Clearly we all shouldn't be here, but since we made it we
2094 * can reliable say we messed up our state. See the above two
2095 * gotos for reasons why we could possibly end up here.
2096 */
Peter Zijlstra8e182572007-07-19 01:48:54 -07002097 WARN_ON(1);
2098
2099 return 0;
2100}
2101
Huang, Ying443cd502008-06-20 16:39:21 +08002102struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS];
Bart Van Asschede4643a2019-02-14 15:00:50 -08002103static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS);
Huang, Yingcd1a28e2008-06-23 11:20:54 +08002104int nr_chain_hlocks;
Huang, Ying443cd502008-06-20 16:39:21 +08002105static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS];
2106
2107struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i)
2108{
2109 return lock_classes + chain_hlocks[chain->base + i];
2110}
Peter Zijlstra8e182572007-07-19 01:48:54 -07002111
2112/*
Ingo Molnar9e4e7552016-02-29 10:03:58 +01002113 * Returns the index of the first held_lock of the current chain
2114 */
2115static inline int get_first_held_lock(struct task_struct *curr,
2116 struct held_lock *hlock)
2117{
2118 int i;
2119 struct held_lock *hlock_curr;
2120
2121 for (i = curr->lockdep_depth - 1; i >= 0; i--) {
2122 hlock_curr = curr->held_locks + i;
2123 if (hlock_curr->irq_context != hlock->irq_context)
2124 break;
2125
2126 }
2127
2128 return ++i;
2129}
2130
Borislav Petkov5c8a0102016-04-04 10:42:07 +02002131#ifdef CONFIG_DEBUG_LOCKDEP
Ingo Molnar9e4e7552016-02-29 10:03:58 +01002132/*
Alfredo Alvarez Fernandez39e2e172016-03-30 19:03:36 +02002133 * Returns the next chain_key iteration
2134 */
2135static u64 print_chain_key_iteration(int class_idx, u64 chain_key)
2136{
2137 u64 new_chain_key = iterate_chain_key(chain_key, class_idx);
2138
2139 printk(" class_idx:%d -> chain_key:%016Lx",
2140 class_idx,
2141 (unsigned long long)new_chain_key);
2142 return new_chain_key;
2143}
2144
2145static void
2146print_chain_keys_held_locks(struct task_struct *curr, struct held_lock *hlock_next)
2147{
2148 struct held_lock *hlock;
2149 u64 chain_key = 0;
2150 int depth = curr->lockdep_depth;
2151 int i;
2152
2153 printk("depth: %u\n", depth + 1);
2154 for (i = get_first_held_lock(curr, hlock_next); i < depth; i++) {
2155 hlock = curr->held_locks + i;
2156 chain_key = print_chain_key_iteration(hlock->class_idx, chain_key);
2157
2158 print_lock(hlock);
2159 }
2160
2161 print_chain_key_iteration(hlock_next->class_idx, chain_key);
2162 print_lock(hlock_next);
2163}
2164
2165static void print_chain_keys_chain(struct lock_chain *chain)
2166{
2167 int i;
2168 u64 chain_key = 0;
2169 int class_id;
2170
2171 printk("depth: %u\n", chain->depth);
2172 for (i = 0; i < chain->depth; i++) {
2173 class_id = chain_hlocks[chain->base + i];
2174 chain_key = print_chain_key_iteration(class_id + 1, chain_key);
2175
2176 print_lock_name(lock_classes + class_id);
2177 printk("\n");
2178 }
2179}
2180
2181static void print_collision(struct task_struct *curr,
2182 struct held_lock *hlock_next,
2183 struct lock_chain *chain)
2184{
Paul E. McKenney681fbec2017-05-04 15:44:38 -07002185 pr_warn("\n");
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08002186 pr_warn("============================\n");
2187 pr_warn("WARNING: chain_key collision\n");
Alfredo Alvarez Fernandez39e2e172016-03-30 19:03:36 +02002188 print_kernel_ident();
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08002189 pr_warn("----------------------------\n");
Paul E. McKenney681fbec2017-05-04 15:44:38 -07002190 pr_warn("%s/%d: ", current->comm, task_pid_nr(current));
2191 pr_warn("Hash chain already cached but the contents don't match!\n");
Alfredo Alvarez Fernandez39e2e172016-03-30 19:03:36 +02002192
Paul E. McKenney681fbec2017-05-04 15:44:38 -07002193 pr_warn("Held locks:");
Alfredo Alvarez Fernandez39e2e172016-03-30 19:03:36 +02002194 print_chain_keys_held_locks(curr, hlock_next);
2195
Paul E. McKenney681fbec2017-05-04 15:44:38 -07002196 pr_warn("Locks in cached chain:");
Alfredo Alvarez Fernandez39e2e172016-03-30 19:03:36 +02002197 print_chain_keys_chain(chain);
2198
Paul E. McKenney681fbec2017-05-04 15:44:38 -07002199 pr_warn("\nstack backtrace:\n");
Alfredo Alvarez Fernandez39e2e172016-03-30 19:03:36 +02002200 dump_stack();
2201}
Borislav Petkov5c8a0102016-04-04 10:42:07 +02002202#endif
Alfredo Alvarez Fernandez39e2e172016-03-30 19:03:36 +02002203
2204/*
Ingo Molnar9e4e7552016-02-29 10:03:58 +01002205 * Checks whether the chain and the current held locks are consistent
2206 * in depth and also in content. If they are not it most likely means
2207 * that there was a collision during the calculation of the chain_key.
2208 * Returns: 0 not passed, 1 passed
2209 */
2210static int check_no_collision(struct task_struct *curr,
2211 struct held_lock *hlock,
2212 struct lock_chain *chain)
2213{
2214#ifdef CONFIG_DEBUG_LOCKDEP
2215 int i, j, id;
2216
2217 i = get_first_held_lock(curr, hlock);
2218
Alfredo Alvarez Fernandez39e2e172016-03-30 19:03:36 +02002219 if (DEBUG_LOCKS_WARN_ON(chain->depth != curr->lockdep_depth - (i - 1))) {
2220 print_collision(curr, hlock, chain);
Ingo Molnar9e4e7552016-02-29 10:03:58 +01002221 return 0;
Alfredo Alvarez Fernandez39e2e172016-03-30 19:03:36 +02002222 }
Ingo Molnar9e4e7552016-02-29 10:03:58 +01002223
2224 for (j = 0; j < chain->depth - 1; j++, i++) {
2225 id = curr->held_locks[i].class_idx - 1;
2226
Alfredo Alvarez Fernandez39e2e172016-03-30 19:03:36 +02002227 if (DEBUG_LOCKS_WARN_ON(chain_hlocks[chain->base + j] != id)) {
2228 print_collision(curr, hlock, chain);
Ingo Molnar9e4e7552016-02-29 10:03:58 +01002229 return 0;
Alfredo Alvarez Fernandez39e2e172016-03-30 19:03:36 +02002230 }
Ingo Molnar9e4e7552016-02-29 10:03:58 +01002231 }
2232#endif
2233 return 1;
2234}
2235
2236/*
Bart Van Assche22126842019-02-14 15:00:48 -08002237 * Given an index that is >= -1, return the index of the next lock chain.
2238 * Return -2 if there is no next lock chain.
2239 */
2240long lockdep_next_lockchain(long i)
2241{
Bart Van Asschede4643a2019-02-14 15:00:50 -08002242 i = find_next_bit(lock_chains_in_use, ARRAY_SIZE(lock_chains), i + 1);
2243 return i < ARRAY_SIZE(lock_chains) ? i : -2;
Bart Van Assche22126842019-02-14 15:00:48 -08002244}
2245
2246unsigned long lock_chain_count(void)
2247{
Bart Van Asschede4643a2019-02-14 15:00:50 -08002248 return bitmap_weight(lock_chains_in_use, ARRAY_SIZE(lock_chains));
2249}
2250
2251/* Must be called with the graph lock held. */
2252static struct lock_chain *alloc_lock_chain(void)
2253{
2254 int idx = find_first_zero_bit(lock_chains_in_use,
2255 ARRAY_SIZE(lock_chains));
2256
2257 if (unlikely(idx >= ARRAY_SIZE(lock_chains)))
2258 return NULL;
2259 __set_bit(idx, lock_chains_in_use);
2260 return lock_chains + idx;
Bart Van Assche22126842019-02-14 15:00:48 -08002261}
2262
2263/*
Byungchul Park545c23f2017-08-07 16:12:48 +09002264 * Adds a dependency chain into chain hashtable. And must be called with
2265 * graph_lock held.
2266 *
2267 * Return 0 if fail, and graph_lock is released.
2268 * Return 1 if succeed, with graph_lock held.
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002269 */
Byungchul Park545c23f2017-08-07 16:12:48 +09002270static inline int add_chain_cache(struct task_struct *curr,
2271 struct held_lock *hlock,
2272 u64 chain_key)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002273{
Dave Jonesf82b2172008-08-11 09:30:23 +02002274 struct lock_class *class = hlock_class(hlock);
Andrew Mortona63f38c2016-02-03 13:44:12 -08002275 struct hlist_head *hash_head = chainhashentry(chain_key);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002276 struct lock_chain *chain;
Steven Rostedte0944ee2011-04-20 21:42:00 -04002277 int i, j;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002278
Peter Zijlstra0119fee2011-09-02 01:30:29 +02002279 /*
Bart Van Assche527af3e2019-02-14 15:00:49 -08002280 * The caller must hold the graph lock, ensure we've got IRQs
Peter Zijlstra0119fee2011-09-02 01:30:29 +02002281 * disabled to make this an IRQ-safe lock.. for recursion reasons
2282 * lockdep won't complain about its own locking errors.
2283 */
Jarek Poplawski381a2292007-02-10 01:44:58 -08002284 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
2285 return 0;
Ingo Molnar9e4e7552016-02-29 10:03:58 +01002286
Bart Van Asschede4643a2019-02-14 15:00:50 -08002287 chain = alloc_lock_chain();
2288 if (!chain) {
Ingo Molnar74c383f2006-12-13 00:34:43 -08002289 if (!debug_locks_off_graph_unlock())
2290 return 0;
2291
Dave Jones2c522832013-04-25 13:40:02 -04002292 print_lockdep_off("BUG: MAX_LOCKDEP_CHAINS too low!");
Peter Zijlstraeedeeab2009-03-18 12:38:47 +01002293 dump_stack();
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002294 return 0;
2295 }
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002296 chain->chain_key = chain_key;
Huang, Ying443cd502008-06-20 16:39:21 +08002297 chain->irq_context = hlock->irq_context;
Ingo Molnar9e4e7552016-02-29 10:03:58 +01002298 i = get_first_held_lock(curr, hlock);
Huang, Ying443cd502008-06-20 16:39:21 +08002299 chain->depth = curr->lockdep_depth + 1 - i;
Peter Zijlstra75dd6022016-03-30 11:36:59 +02002300
2301 BUILD_BUG_ON((1UL << 24) <= ARRAY_SIZE(chain_hlocks));
2302 BUILD_BUG_ON((1UL << 6) <= ARRAY_SIZE(curr->held_locks));
2303 BUILD_BUG_ON((1UL << 8*sizeof(chain_hlocks[0])) <= ARRAY_SIZE(lock_classes));
2304
Steven Rostedte0944ee2011-04-20 21:42:00 -04002305 if (likely(nr_chain_hlocks + chain->depth <= MAX_LOCKDEP_CHAIN_HLOCKS)) {
2306 chain->base = nr_chain_hlocks;
Huang, Ying443cd502008-06-20 16:39:21 +08002307 for (j = 0; j < chain->depth - 1; j++, i++) {
Dave Jonesf82b2172008-08-11 09:30:23 +02002308 int lock_id = curr->held_locks[i].class_idx - 1;
Huang, Ying443cd502008-06-20 16:39:21 +08002309 chain_hlocks[chain->base + j] = lock_id;
2310 }
2311 chain_hlocks[chain->base + j] = class - lock_classes;
Peter Zijlstra75dd6022016-03-30 11:36:59 +02002312 nr_chain_hlocks += chain->depth;
Bart Van Assche523b1132019-02-14 15:00:39 -08002313 } else {
Byungchul Parkf9af4562017-01-13 11:42:04 +09002314 if (!debug_locks_off_graph_unlock())
Peter Zijlstra75dd6022016-03-30 11:36:59 +02002315 return 0;
2316
2317 print_lockdep_off("BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!");
2318 dump_stack();
2319 return 0;
2320 }
Peter Zijlstra75dd6022016-03-30 11:36:59 +02002321
Andrew Mortona63f38c2016-02-03 13:44:12 -08002322 hlist_add_head_rcu(&chain->entry, hash_head);
Frederic Weisbeckerbd6d29c2010-04-06 00:10:17 +02002323 debug_atomic_inc(chain_lookup_misses);
Peter Zijlstra8e182572007-07-19 01:48:54 -07002324 inc_chains();
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002325
2326 return 1;
2327}
Peter Zijlstra8e182572007-07-19 01:48:54 -07002328
Byungchul Park545c23f2017-08-07 16:12:48 +09002329/*
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08002330 * Look up a dependency chain. Must be called with either the graph lock or
2331 * the RCU read lock held.
Byungchul Park545c23f2017-08-07 16:12:48 +09002332 */
2333static inline struct lock_chain *lookup_chain_cache(u64 chain_key)
2334{
2335 struct hlist_head *hash_head = chainhashentry(chain_key);
2336 struct lock_chain *chain;
2337
Byungchul Park545c23f2017-08-07 16:12:48 +09002338 hlist_for_each_entry_rcu(chain, hash_head, entry) {
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08002339 if (READ_ONCE(chain->chain_key) == chain_key) {
Byungchul Park545c23f2017-08-07 16:12:48 +09002340 debug_atomic_inc(chain_lookup_hits);
2341 return chain;
2342 }
2343 }
2344 return NULL;
2345}
2346
2347/*
2348 * If the key is not present yet in dependency chain cache then
2349 * add it and return 1 - in this case the new dependency chain is
2350 * validated. If the key is already hashed, return 0.
2351 * (On return with 1 graph_lock is held.)
2352 */
2353static inline int lookup_chain_cache_add(struct task_struct *curr,
2354 struct held_lock *hlock,
2355 u64 chain_key)
2356{
2357 struct lock_class *class = hlock_class(hlock);
2358 struct lock_chain *chain = lookup_chain_cache(chain_key);
2359
2360 if (chain) {
2361cache_hit:
2362 if (!check_no_collision(curr, hlock, chain))
2363 return 0;
2364
2365 if (very_verbose(class)) {
2366 printk("\nhash chain already cached, key: "
Borislav Petkov04860d42018-02-26 14:49:26 +01002367 "%016Lx tail class: [%px] %s\n",
Byungchul Park545c23f2017-08-07 16:12:48 +09002368 (unsigned long long)chain_key,
2369 class->key, class->name);
2370 }
2371
2372 return 0;
2373 }
2374
2375 if (very_verbose(class)) {
Borislav Petkov04860d42018-02-26 14:49:26 +01002376 printk("\nnew hash chain, key: %016Lx tail class: [%px] %s\n",
Byungchul Park545c23f2017-08-07 16:12:48 +09002377 (unsigned long long)chain_key, class->key, class->name);
2378 }
2379
2380 if (!graph_lock())
2381 return 0;
2382
2383 /*
2384 * We have to walk the chain again locked - to avoid duplicates:
2385 */
2386 chain = lookup_chain_cache(chain_key);
2387 if (chain) {
2388 graph_unlock();
2389 goto cache_hit;
2390 }
2391
2392 if (!add_chain_cache(curr, hlock, chain_key))
2393 return 0;
2394
2395 return 1;
2396}
2397
Peter Zijlstra8e182572007-07-19 01:48:54 -07002398static int validate_chain(struct task_struct *curr, struct lockdep_map *lock,
Johannes Berg4e6045f2007-10-18 23:39:55 -07002399 struct held_lock *hlock, int chain_head, u64 chain_key)
Peter Zijlstra8e182572007-07-19 01:48:54 -07002400{
2401 /*
2402 * Trylock needs to maintain the stack of held locks, but it
2403 * does not add new dependencies, because trylock can be done
2404 * in any order.
2405 *
2406 * We look up the chain_key and do the O(N^2) check and update of
2407 * the dependencies only if this is a new dependency chain.
Byungchul Park545c23f2017-08-07 16:12:48 +09002408 * (If lookup_chain_cache_add() return with 1 it acquires
Peter Zijlstra8e182572007-07-19 01:48:54 -07002409 * graph_lock for us)
2410 */
Oleg Nesterovfb9edbe2014-01-20 19:20:06 +01002411 if (!hlock->trylock && hlock->check &&
Byungchul Park545c23f2017-08-07 16:12:48 +09002412 lookup_chain_cache_add(curr, hlock, chain_key)) {
Peter Zijlstra8e182572007-07-19 01:48:54 -07002413 /*
2414 * Check whether last held lock:
2415 *
2416 * - is irq-safe, if this lock is irq-unsafe
2417 * - is softirq-safe, if this lock is hardirq-unsafe
2418 *
2419 * And check whether the new lock's dependency graph
2420 * could lead back to the previous lock.
2421 *
2422 * any of these scenarios could lead to a deadlock. If
2423 * All validations
2424 */
2425 int ret = check_deadlock(curr, hlock, lock, hlock->read);
2426
2427 if (!ret)
2428 return 0;
2429 /*
2430 * Mark recursive read, as we jump over it when
2431 * building dependencies (just like we jump over
2432 * trylock entries):
2433 */
2434 if (ret == 2)
2435 hlock->read = 2;
2436 /*
2437 * Add dependency only if this lock is not the head
2438 * of the chain, and if it's not a secondary read-lock:
2439 */
Byungchul Park545c23f2017-08-07 16:12:48 +09002440 if (!chain_head && ret != 2) {
Peter Zijlstra8e182572007-07-19 01:48:54 -07002441 if (!check_prevs_add(curr, hlock))
2442 return 0;
Byungchul Park545c23f2017-08-07 16:12:48 +09002443 }
2444
Peter Zijlstra8e182572007-07-19 01:48:54 -07002445 graph_unlock();
Byungchul Park545c23f2017-08-07 16:12:48 +09002446 } else {
2447 /* after lookup_chain_cache_add(): */
Peter Zijlstra8e182572007-07-19 01:48:54 -07002448 if (unlikely(!debug_locks))
2449 return 0;
Byungchul Park545c23f2017-08-07 16:12:48 +09002450 }
Peter Zijlstra8e182572007-07-19 01:48:54 -07002451
2452 return 1;
2453}
2454#else
2455static inline int validate_chain(struct task_struct *curr,
2456 struct lockdep_map *lock, struct held_lock *hlock,
Gregory Haskins3aa416b2007-10-11 22:11:11 +02002457 int chain_head, u64 chain_key)
Peter Zijlstra8e182572007-07-19 01:48:54 -07002458{
2459 return 1;
2460}
Peter Zijlstraca58abc2007-07-19 01:48:53 -07002461#endif
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002462
2463/*
2464 * We are building curr_chain_key incrementally, so double-check
2465 * it from scratch, to make sure that it's done correctly:
2466 */
Steven Rostedt1d09daa2008-05-12 21:20:55 +02002467static void check_chain_key(struct task_struct *curr)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002468{
2469#ifdef CONFIG_DEBUG_LOCKDEP
2470 struct held_lock *hlock, *prev_hlock = NULL;
Alfredo Alvarez Fernandez5f18ab52016-02-11 00:33:32 +01002471 unsigned int i;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002472 u64 chain_key = 0;
2473
2474 for (i = 0; i < curr->lockdep_depth; i++) {
2475 hlock = curr->held_locks + i;
2476 if (chain_key != hlock->prev_chain_key) {
2477 debug_locks_off();
Peter Zijlstra0119fee2011-09-02 01:30:29 +02002478 /*
2479 * We got mighty confused, our chain keys don't match
2480 * with what we expect, someone trample on our task state?
2481 */
Arjan van de Ven2df8b1d2008-07-30 12:43:11 -07002482 WARN(1, "hm#1, depth: %u [%u], %016Lx != %016Lx\n",
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002483 curr->lockdep_depth, i,
2484 (unsigned long long)chain_key,
2485 (unsigned long long)hlock->prev_chain_key);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002486 return;
2487 }
Peter Zijlstra0119fee2011-09-02 01:30:29 +02002488 /*
2489 * Whoops ran out of static storage again?
2490 */
Alfredo Alvarez Fernandez5f18ab52016-02-11 00:33:32 +01002491 if (DEBUG_LOCKS_WARN_ON(hlock->class_idx > MAX_LOCKDEP_KEYS))
Jarek Poplawski381a2292007-02-10 01:44:58 -08002492 return;
2493
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002494 if (prev_hlock && (prev_hlock->irq_context !=
2495 hlock->irq_context))
2496 chain_key = 0;
Alfredo Alvarez Fernandez5f18ab52016-02-11 00:33:32 +01002497 chain_key = iterate_chain_key(chain_key, hlock->class_idx);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002498 prev_hlock = hlock;
2499 }
2500 if (chain_key != curr->curr_chain_key) {
2501 debug_locks_off();
Peter Zijlstra0119fee2011-09-02 01:30:29 +02002502 /*
2503 * More smoking hash instead of calculating it, damn see these
2504 * numbers float.. I bet that a pink elephant stepped on my memory.
2505 */
Arjan van de Ven2df8b1d2008-07-30 12:43:11 -07002506 WARN(1, "hm#2, depth: %u [%u], %016Lx != %016Lx\n",
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002507 curr->lockdep_depth, i,
2508 (unsigned long long)chain_key,
2509 (unsigned long long)curr->curr_chain_key);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002510 }
2511#endif
2512}
2513
Steven Rostedt282b5c22011-04-20 21:41:59 -04002514static void
2515print_usage_bug_scenario(struct held_lock *lock)
2516{
2517 struct lock_class *class = hlock_class(lock);
2518
2519 printk(" Possible unsafe locking scenario:\n\n");
2520 printk(" CPU0\n");
2521 printk(" ----\n");
2522 printk(" lock(");
2523 __print_lock_name(class);
Dmitry Vyukovf943fe02016-11-28 15:24:43 +01002524 printk(KERN_CONT ");\n");
Steven Rostedt282b5c22011-04-20 21:41:59 -04002525 printk(" <Interrupt>\n");
2526 printk(" lock(");
2527 __print_lock_name(class);
Dmitry Vyukovf943fe02016-11-28 15:24:43 +01002528 printk(KERN_CONT ");\n");
Steven Rostedt282b5c22011-04-20 21:41:59 -04002529 printk("\n *** DEADLOCK ***\n\n");
2530}
2531
Peter Zijlstra8e182572007-07-19 01:48:54 -07002532static int
2533print_usage_bug(struct task_struct *curr, struct held_lock *this,
2534 enum lock_usage_bit prev_bit, enum lock_usage_bit new_bit)
2535{
2536 if (!debug_locks_off_graph_unlock() || debug_locks_silent)
2537 return 0;
2538
Paul E. McKenney681fbec2017-05-04 15:44:38 -07002539 pr_warn("\n");
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08002540 pr_warn("================================\n");
2541 pr_warn("WARNING: inconsistent lock state\n");
Ben Hutchingsfbdc4b92011-10-28 04:36:55 +01002542 print_kernel_ident();
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08002543 pr_warn("--------------------------------\n");
Peter Zijlstra8e182572007-07-19 01:48:54 -07002544
Paul E. McKenney681fbec2017-05-04 15:44:38 -07002545 pr_warn("inconsistent {%s} -> {%s} usage.\n",
Peter Zijlstra8e182572007-07-19 01:48:54 -07002546 usage_str[prev_bit], usage_str[new_bit]);
2547
Paul E. McKenney681fbec2017-05-04 15:44:38 -07002548 pr_warn("%s/%d [HC%u[%lu]:SC%u[%lu]:HE%u:SE%u] takes:\n",
Pavel Emelyanovba25f9d2007-10-18 23:40:40 -07002549 curr->comm, task_pid_nr(curr),
Peter Zijlstra8e182572007-07-19 01:48:54 -07002550 trace_hardirq_context(curr), hardirq_count() >> HARDIRQ_SHIFT,
2551 trace_softirq_context(curr), softirq_count() >> SOFTIRQ_SHIFT,
2552 trace_hardirqs_enabled(curr),
2553 trace_softirqs_enabled(curr));
2554 print_lock(this);
2555
Paul E. McKenney681fbec2017-05-04 15:44:38 -07002556 pr_warn("{%s} state was registered at:\n", usage_str[prev_bit]);
Dave Jonesf82b2172008-08-11 09:30:23 +02002557 print_stack_trace(hlock_class(this)->usage_traces + prev_bit, 1);
Peter Zijlstra8e182572007-07-19 01:48:54 -07002558
2559 print_irqtrace_events(curr);
Paul E. McKenney681fbec2017-05-04 15:44:38 -07002560 pr_warn("\nother info that might help us debug this:\n");
Steven Rostedt282b5c22011-04-20 21:41:59 -04002561 print_usage_bug_scenario(this);
2562
Peter Zijlstra8e182572007-07-19 01:48:54 -07002563 lockdep_print_held_locks(curr);
2564
Paul E. McKenney681fbec2017-05-04 15:44:38 -07002565 pr_warn("\nstack backtrace:\n");
Peter Zijlstra8e182572007-07-19 01:48:54 -07002566 dump_stack();
2567
2568 return 0;
2569}
2570
2571/*
2572 * Print out an error if an invalid bit is set:
2573 */
2574static inline int
2575valid_state(struct task_struct *curr, struct held_lock *this,
2576 enum lock_usage_bit new_bit, enum lock_usage_bit bad_bit)
2577{
Dave Jonesf82b2172008-08-11 09:30:23 +02002578 if (unlikely(hlock_class(this)->usage_mask & (1 << bad_bit)))
Peter Zijlstra8e182572007-07-19 01:48:54 -07002579 return print_usage_bug(curr, this, bad_bit, new_bit);
2580 return 1;
2581}
2582
2583static int mark_lock(struct task_struct *curr, struct held_lock *this,
2584 enum lock_usage_bit new_bit);
2585
Steven Rostedt81d68a92008-05-12 21:20:42 +02002586#if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002587
2588/*
2589 * print irq inversion bug:
2590 */
2591static int
Ming Lei24208ca2009-07-16 15:44:29 +02002592print_irq_inversion_bug(struct task_struct *curr,
2593 struct lock_list *root, struct lock_list *other,
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002594 struct held_lock *this, int forwards,
2595 const char *irqclass)
2596{
Steven Rostedtdad3d742011-04-20 21:41:57 -04002597 struct lock_list *entry = other;
2598 struct lock_list *middle = NULL;
2599 int depth;
2600
Ingo Molnar74c383f2006-12-13 00:34:43 -08002601 if (!debug_locks_off_graph_unlock() || debug_locks_silent)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002602 return 0;
2603
Paul E. McKenney681fbec2017-05-04 15:44:38 -07002604 pr_warn("\n");
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08002605 pr_warn("========================================================\n");
2606 pr_warn("WARNING: possible irq lock inversion dependency detected\n");
Ben Hutchingsfbdc4b92011-10-28 04:36:55 +01002607 print_kernel_ident();
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08002608 pr_warn("--------------------------------------------------------\n");
Paul E. McKenney681fbec2017-05-04 15:44:38 -07002609 pr_warn("%s/%d just changed the state of lock:\n",
Pavel Emelyanovba25f9d2007-10-18 23:40:40 -07002610 curr->comm, task_pid_nr(curr));
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002611 print_lock(this);
2612 if (forwards)
Paul E. McKenney681fbec2017-05-04 15:44:38 -07002613 pr_warn("but this lock took another, %s-unsafe lock in the past:\n", irqclass);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002614 else
Paul E. McKenney681fbec2017-05-04 15:44:38 -07002615 pr_warn("but this lock was taken by another, %s-safe lock in the past:\n", irqclass);
Ming Lei24208ca2009-07-16 15:44:29 +02002616 print_lock_name(other->class);
Paul E. McKenney681fbec2017-05-04 15:44:38 -07002617 pr_warn("\n\nand interrupts could create inverse lock ordering between them.\n\n");
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002618
Paul E. McKenney681fbec2017-05-04 15:44:38 -07002619 pr_warn("\nother info that might help us debug this:\n");
Steven Rostedtdad3d742011-04-20 21:41:57 -04002620
2621 /* Find a middle lock (if one exists) */
2622 depth = get_lock_depth(other);
2623 do {
2624 if (depth == 0 && (entry != root)) {
Paul E. McKenney681fbec2017-05-04 15:44:38 -07002625 pr_warn("lockdep:%s bad path found in chain graph\n", __func__);
Steven Rostedtdad3d742011-04-20 21:41:57 -04002626 break;
2627 }
2628 middle = entry;
2629 entry = get_lock_parent(entry);
2630 depth--;
2631 } while (entry && entry != root && (depth >= 0));
2632 if (forwards)
2633 print_irq_lock_scenario(root, other,
2634 middle ? middle->class : root->class, other->class);
2635 else
2636 print_irq_lock_scenario(other, root,
2637 middle ? middle->class : other->class, root->class);
2638
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002639 lockdep_print_held_locks(curr);
2640
Paul E. McKenney681fbec2017-05-04 15:44:38 -07002641 pr_warn("\nthe shortest dependencies between 2nd lock and 1st lock:\n");
Ming Lei24208ca2009-07-16 15:44:29 +02002642 if (!save_trace(&root->trace))
2643 return 0;
2644 print_shortest_lock_dependencies(other, root);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002645
Paul E. McKenney681fbec2017-05-04 15:44:38 -07002646 pr_warn("\nstack backtrace:\n");
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002647 dump_stack();
2648
2649 return 0;
2650}
2651
2652/*
2653 * Prove that in the forwards-direction subgraph starting at <this>
2654 * there is no lock matching <mask>:
2655 */
2656static int
2657check_usage_forwards(struct task_struct *curr, struct held_lock *this,
2658 enum lock_usage_bit bit, const char *irqclass)
2659{
2660 int ret;
Ming Leid7aaba12009-07-16 15:44:29 +02002661 struct lock_list root;
2662 struct lock_list *uninitialized_var(target_entry);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002663
Ming Leid7aaba12009-07-16 15:44:29 +02002664 root.parent = NULL;
2665 root.class = hlock_class(this);
2666 ret = find_usage_forwards(&root, bit, &target_entry);
Peter Zijlstraaf012962009-07-16 15:44:29 +02002667 if (ret < 0)
2668 return print_bfs_bug(ret);
2669 if (ret == 1)
2670 return ret;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002671
Ming Lei24208ca2009-07-16 15:44:29 +02002672 return print_irq_inversion_bug(curr, &root, target_entry,
Ming Leid7aaba12009-07-16 15:44:29 +02002673 this, 1, irqclass);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002674}
2675
2676/*
2677 * Prove that in the backwards-direction subgraph starting at <this>
2678 * there is no lock matching <mask>:
2679 */
2680static int
2681check_usage_backwards(struct task_struct *curr, struct held_lock *this,
2682 enum lock_usage_bit bit, const char *irqclass)
2683{
2684 int ret;
Ming Leid7aaba12009-07-16 15:44:29 +02002685 struct lock_list root;
2686 struct lock_list *uninitialized_var(target_entry);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002687
Ming Leid7aaba12009-07-16 15:44:29 +02002688 root.parent = NULL;
2689 root.class = hlock_class(this);
2690 ret = find_usage_backwards(&root, bit, &target_entry);
Peter Zijlstraaf012962009-07-16 15:44:29 +02002691 if (ret < 0)
2692 return print_bfs_bug(ret);
2693 if (ret == 1)
2694 return ret;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002695
Ming Lei24208ca2009-07-16 15:44:29 +02002696 return print_irq_inversion_bug(curr, &root, target_entry,
Oleg Nesterov48d50672010-01-26 19:16:41 +01002697 this, 0, irqclass);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002698}
2699
Ingo Molnar3117df02006-12-13 00:34:43 -08002700void print_irqtrace_events(struct task_struct *curr)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002701{
2702 printk("irq event stamp: %u\n", curr->irq_events);
Borislav Petkov04860d42018-02-26 14:49:26 +01002703 printk("hardirqs last enabled at (%u): [<%px>] %pS\n",
Dmitry Vyukovf943fe02016-11-28 15:24:43 +01002704 curr->hardirq_enable_event, (void *)curr->hardirq_enable_ip,
2705 (void *)curr->hardirq_enable_ip);
Borislav Petkov04860d42018-02-26 14:49:26 +01002706 printk("hardirqs last disabled at (%u): [<%px>] %pS\n",
Dmitry Vyukovf943fe02016-11-28 15:24:43 +01002707 curr->hardirq_disable_event, (void *)curr->hardirq_disable_ip,
2708 (void *)curr->hardirq_disable_ip);
Borislav Petkov04860d42018-02-26 14:49:26 +01002709 printk("softirqs last enabled at (%u): [<%px>] %pS\n",
Dmitry Vyukovf943fe02016-11-28 15:24:43 +01002710 curr->softirq_enable_event, (void *)curr->softirq_enable_ip,
2711 (void *)curr->softirq_enable_ip);
Borislav Petkov04860d42018-02-26 14:49:26 +01002712 printk("softirqs last disabled at (%u): [<%px>] %pS\n",
Dmitry Vyukovf943fe02016-11-28 15:24:43 +01002713 curr->softirq_disable_event, (void *)curr->softirq_disable_ip,
2714 (void *)curr->softirq_disable_ip);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002715}
2716
Peter Zijlstracd953022009-01-22 16:38:21 +01002717static int HARDIRQ_verbose(struct lock_class *class)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002718{
Peter Zijlstra8e182572007-07-19 01:48:54 -07002719#if HARDIRQ_VERBOSE
2720 return class_filter(class);
2721#endif
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002722 return 0;
2723}
2724
Peter Zijlstracd953022009-01-22 16:38:21 +01002725static int SOFTIRQ_verbose(struct lock_class *class)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002726{
Peter Zijlstra8e182572007-07-19 01:48:54 -07002727#if SOFTIRQ_VERBOSE
2728 return class_filter(class);
2729#endif
2730 return 0;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002731}
2732
2733#define STRICT_READ_CHECKS 1
2734
Peter Zijlstracd953022009-01-22 16:38:21 +01002735static int (*state_verbose_f[])(struct lock_class *class) = {
2736#define LOCKDEP_STATE(__STATE) \
2737 __STATE##_verbose,
2738#include "lockdep_states.h"
2739#undef LOCKDEP_STATE
2740};
2741
2742static inline int state_verbose(enum lock_usage_bit bit,
2743 struct lock_class *class)
2744{
2745 return state_verbose_f[bit >> 2](class);
2746}
2747
Peter Zijlstra42c50d52009-01-22 16:58:16 +01002748typedef int (*check_usage_f)(struct task_struct *, struct held_lock *,
2749 enum lock_usage_bit bit, const char *name);
2750
Peter Zijlstra6a6904d2009-01-22 16:07:44 +01002751static int
Peter Zijlstra1c21f142009-03-04 13:51:13 +01002752mark_lock_irq(struct task_struct *curr, struct held_lock *this,
2753 enum lock_usage_bit new_bit)
Peter Zijlstra6a6904d2009-01-22 16:07:44 +01002754{
Peter Zijlstraf9892092009-01-22 16:09:59 +01002755 int excl_bit = exclusive_bit(new_bit);
Frederic Weisbeckerbba2a8f2018-12-28 06:02:01 +01002756 int read = new_bit & LOCK_USAGE_READ_MASK;
2757 int dir = new_bit & LOCK_USAGE_DIR_MASK;
Peter Zijlstra42c50d52009-01-22 16:58:16 +01002758
Peter Zijlstra38aa2712009-01-27 14:53:50 +01002759 /*
2760 * mark USED_IN has to look forwards -- to ensure no dependency
2761 * has ENABLED state, which would allow recursion deadlocks.
2762 *
2763 * mark ENABLED has to look backwards -- to ensure no dependee
2764 * has USED_IN state, which, again, would allow recursion deadlocks.
2765 */
Peter Zijlstra42c50d52009-01-22 16:58:16 +01002766 check_usage_f usage = dir ?
2767 check_usage_backwards : check_usage_forwards;
Peter Zijlstraf9892092009-01-22 16:09:59 +01002768
Peter Zijlstra38aa2712009-01-27 14:53:50 +01002769 /*
2770 * Validate that this particular lock does not have conflicting
2771 * usage states.
2772 */
Peter Zijlstra6a6904d2009-01-22 16:07:44 +01002773 if (!valid_state(curr, this, new_bit, excl_bit))
2774 return 0;
Peter Zijlstra9d3651a2009-01-22 17:18:32 +01002775
Peter Zijlstra38aa2712009-01-27 14:53:50 +01002776 /*
2777 * Validate that the lock dependencies don't have conflicting usage
2778 * states.
2779 */
2780 if ((!read || !dir || STRICT_READ_CHECKS) &&
Frederic Weisbeckerbba2a8f2018-12-28 06:02:01 +01002781 !usage(curr, this, excl_bit, state_name(new_bit & ~LOCK_USAGE_READ_MASK)))
Peter Zijlstra6a6904d2009-01-22 16:07:44 +01002782 return 0;
Peter Zijlstra780e8202009-01-22 16:51:29 +01002783
Peter Zijlstra38aa2712009-01-27 14:53:50 +01002784 /*
2785 * Check for read in write conflicts
2786 */
2787 if (!read) {
Frederic Weisbeckerbba2a8f2018-12-28 06:02:01 +01002788 if (!valid_state(curr, this, new_bit, excl_bit + LOCK_USAGE_READ_MASK))
Peter Zijlstra38aa2712009-01-27 14:53:50 +01002789 return 0;
2790
2791 if (STRICT_READ_CHECKS &&
Frederic Weisbeckerbba2a8f2018-12-28 06:02:01 +01002792 !usage(curr, this, excl_bit + LOCK_USAGE_READ_MASK,
2793 state_name(new_bit + LOCK_USAGE_READ_MASK)))
Peter Zijlstra38aa2712009-01-27 14:53:50 +01002794 return 0;
2795 }
Peter Zijlstra780e8202009-01-22 16:51:29 +01002796
Peter Zijlstracd953022009-01-22 16:38:21 +01002797 if (state_verbose(new_bit, hlock_class(this)))
Peter Zijlstra6a6904d2009-01-22 16:07:44 +01002798 return 2;
2799
2800 return 1;
2801}
2802
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002803/*
2804 * Mark all held locks with a usage bit:
2805 */
Steven Rostedt1d09daa2008-05-12 21:20:55 +02002806static int
Frederic Weisbecker436a49a2018-12-28 06:02:00 +01002807mark_held_locks(struct task_struct *curr, enum lock_usage_bit base_bit)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002808{
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002809 struct held_lock *hlock;
2810 int i;
2811
2812 for (i = 0; i < curr->lockdep_depth; i++) {
Frederic Weisbecker436a49a2018-12-28 06:02:00 +01002813 enum lock_usage_bit hlock_bit = base_bit;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002814 hlock = curr->held_locks + i;
2815
Peter Zijlstracf2ad4d2009-01-27 13:58:08 +01002816 if (hlock->read)
Frederic Weisbeckerbba2a8f2018-12-28 06:02:01 +01002817 hlock_bit += LOCK_USAGE_READ_MASK;
Peter Zijlstracf2ad4d2009-01-27 13:58:08 +01002818
Frederic Weisbecker436a49a2018-12-28 06:02:00 +01002819 BUG_ON(hlock_bit >= LOCK_USAGE_STATES);
Nick Piggincf40bd12009-01-21 08:12:39 +01002820
Oleg Nesterov34d0ed52014-01-20 19:20:13 +01002821 if (!hlock->check)
Peter Zijlstraefbe2ee2011-07-07 11:39:45 +02002822 continue;
2823
Frederic Weisbecker436a49a2018-12-28 06:02:00 +01002824 if (!mark_lock(curr, hlock, hlock_bit))
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002825 return 0;
2826 }
2827
2828 return 1;
2829}
2830
2831/*
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002832 * Hardirqs will be enabled:
2833 */
Peter Zijlstradd4e5d32011-06-21 17:17:27 +02002834static void __trace_hardirqs_on_caller(unsigned long ip)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002835{
2836 struct task_struct *curr = current;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002837
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002838 /* we'll do an OFF -> ON transition: */
2839 curr->hardirqs_enabled = 1;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002840
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002841 /*
2842 * We are going to turn hardirqs on, so set the
2843 * usage bit for all held locks:
2844 */
Frederic Weisbecker436a49a2018-12-28 06:02:00 +01002845 if (!mark_held_locks(curr, LOCK_ENABLED_HARDIRQ))
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002846 return;
2847 /*
2848 * If we have softirqs enabled, then set the usage
2849 * bit for all held locks. (disabled hardirqs prevented
2850 * this bit from being set before)
2851 */
2852 if (curr->softirqs_enabled)
Frederic Weisbecker436a49a2018-12-28 06:02:00 +01002853 if (!mark_held_locks(curr, LOCK_ENABLED_SOFTIRQ))
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002854 return;
2855
2856 curr->hardirq_enable_ip = ip;
2857 curr->hardirq_enable_event = ++curr->irq_events;
Frederic Weisbeckerbd6d29c2010-04-06 00:10:17 +02002858 debug_atomic_inc(hardirqs_on_events);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002859}
Peter Zijlstradd4e5d32011-06-21 17:17:27 +02002860
Steven Rostedt (VMware)bff1b202018-08-06 15:50:58 -04002861void lockdep_hardirqs_on(unsigned long ip)
Peter Zijlstradd4e5d32011-06-21 17:17:27 +02002862{
Peter Zijlstradd4e5d32011-06-21 17:17:27 +02002863 if (unlikely(!debug_locks || current->lockdep_recursion))
2864 return;
2865
Peter Zijlstra7d36b262011-07-26 13:13:44 +02002866 if (unlikely(current->hardirqs_enabled)) {
2867 /*
2868 * Neither irq nor preemption are disabled here
2869 * so this is racy by nature but losing one hit
2870 * in a stat is not a big deal.
2871 */
2872 __debug_atomic_inc(redundant_hardirqs_on);
2873 return;
2874 }
2875
Peter Zijlstra0119fee2011-09-02 01:30:29 +02002876 /*
2877 * We're enabling irqs and according to our state above irqs weren't
2878 * already enabled, yet we find the hardware thinks they are in fact
2879 * enabled.. someone messed up their IRQ state tracing.
2880 */
Peter Zijlstradd4e5d32011-06-21 17:17:27 +02002881 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
2882 return;
2883
Peter Zijlstra0119fee2011-09-02 01:30:29 +02002884 /*
2885 * See the fine text that goes along with this variable definition.
2886 */
Peter Zijlstra7d36b262011-07-26 13:13:44 +02002887 if (DEBUG_LOCKS_WARN_ON(unlikely(early_boot_irqs_disabled)))
2888 return;
2889
Peter Zijlstra0119fee2011-09-02 01:30:29 +02002890 /*
2891 * Can't allow enabling interrupts while in an interrupt handler,
2892 * that's general bad form and such. Recursion, limited stack etc..
2893 */
Peter Zijlstra7d36b262011-07-26 13:13:44 +02002894 if (DEBUG_LOCKS_WARN_ON(current->hardirq_context))
2895 return;
2896
Peter Zijlstradd4e5d32011-06-21 17:17:27 +02002897 current->lockdep_recursion = 1;
2898 __trace_hardirqs_on_caller(ip);
2899 current->lockdep_recursion = 0;
2900}
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002901
2902/*
2903 * Hardirqs were disabled:
2904 */
Steven Rostedt (VMware)bff1b202018-08-06 15:50:58 -04002905void lockdep_hardirqs_off(unsigned long ip)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002906{
2907 struct task_struct *curr = current;
2908
2909 if (unlikely(!debug_locks || current->lockdep_recursion))
2910 return;
2911
Peter Zijlstra0119fee2011-09-02 01:30:29 +02002912 /*
2913 * So we're supposed to get called after you mask local IRQs, but for
2914 * some reason the hardware doesn't quite think you did a proper job.
2915 */
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002916 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
2917 return;
2918
2919 if (curr->hardirqs_enabled) {
2920 /*
2921 * We have done an ON -> OFF transition:
2922 */
2923 curr->hardirqs_enabled = 0;
Heiko Carstens6afe40b2008-10-28 11:14:58 +01002924 curr->hardirq_disable_ip = ip;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002925 curr->hardirq_disable_event = ++curr->irq_events;
Frederic Weisbeckerbd6d29c2010-04-06 00:10:17 +02002926 debug_atomic_inc(hardirqs_off_events);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002927 } else
Frederic Weisbeckerbd6d29c2010-04-06 00:10:17 +02002928 debug_atomic_inc(redundant_hardirqs_off);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002929}
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002930
2931/*
2932 * Softirqs will be enabled:
2933 */
2934void trace_softirqs_on(unsigned long ip)
2935{
2936 struct task_struct *curr = current;
2937
Peter Zijlstradd4e5d32011-06-21 17:17:27 +02002938 if (unlikely(!debug_locks || current->lockdep_recursion))
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002939 return;
2940
Peter Zijlstra0119fee2011-09-02 01:30:29 +02002941 /*
2942 * We fancy IRQs being disabled here, see softirq.c, avoids
2943 * funny state and nesting things.
2944 */
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002945 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
2946 return;
2947
2948 if (curr->softirqs_enabled) {
Frederic Weisbeckerbd6d29c2010-04-06 00:10:17 +02002949 debug_atomic_inc(redundant_softirqs_on);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002950 return;
2951 }
2952
Peter Zijlstradd4e5d32011-06-21 17:17:27 +02002953 current->lockdep_recursion = 1;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002954 /*
2955 * We'll do an OFF -> ON transition:
2956 */
2957 curr->softirqs_enabled = 1;
2958 curr->softirq_enable_ip = ip;
2959 curr->softirq_enable_event = ++curr->irq_events;
Frederic Weisbeckerbd6d29c2010-04-06 00:10:17 +02002960 debug_atomic_inc(softirqs_on_events);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002961 /*
2962 * We are going to turn softirqs on, so set the
2963 * usage bit for all held locks, if hardirqs are
2964 * enabled too:
2965 */
2966 if (curr->hardirqs_enabled)
Frederic Weisbecker436a49a2018-12-28 06:02:00 +01002967 mark_held_locks(curr, LOCK_ENABLED_SOFTIRQ);
Peter Zijlstradd4e5d32011-06-21 17:17:27 +02002968 current->lockdep_recursion = 0;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002969}
2970
2971/*
2972 * Softirqs were disabled:
2973 */
2974void trace_softirqs_off(unsigned long ip)
2975{
2976 struct task_struct *curr = current;
2977
Peter Zijlstradd4e5d32011-06-21 17:17:27 +02002978 if (unlikely(!debug_locks || current->lockdep_recursion))
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002979 return;
2980
Peter Zijlstra0119fee2011-09-02 01:30:29 +02002981 /*
2982 * We fancy IRQs being disabled here, see softirq.c
2983 */
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002984 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
2985 return;
2986
2987 if (curr->softirqs_enabled) {
2988 /*
2989 * We have done an ON -> OFF transition:
2990 */
2991 curr->softirqs_enabled = 0;
2992 curr->softirq_disable_ip = ip;
2993 curr->softirq_disable_event = ++curr->irq_events;
Frederic Weisbeckerbd6d29c2010-04-06 00:10:17 +02002994 debug_atomic_inc(softirqs_off_events);
Peter Zijlstra0119fee2011-09-02 01:30:29 +02002995 /*
2996 * Whoops, we wanted softirqs off, so why aren't they?
2997 */
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07002998 DEBUG_LOCKS_WARN_ON(!softirq_count());
2999 } else
Frederic Weisbeckerbd6d29c2010-04-06 00:10:17 +02003000 debug_atomic_inc(redundant_softirqs_off);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003001}
3002
Peter Zijlstra8e182572007-07-19 01:48:54 -07003003static int mark_irqflags(struct task_struct *curr, struct held_lock *hlock)
3004{
3005 /*
3006 * If non-trylock use in a hardirq or softirq context, then
3007 * mark the lock as used in these contexts:
3008 */
3009 if (!hlock->trylock) {
3010 if (hlock->read) {
3011 if (curr->hardirq_context)
3012 if (!mark_lock(curr, hlock,
3013 LOCK_USED_IN_HARDIRQ_READ))
3014 return 0;
3015 if (curr->softirq_context)
3016 if (!mark_lock(curr, hlock,
3017 LOCK_USED_IN_SOFTIRQ_READ))
3018 return 0;
3019 } else {
3020 if (curr->hardirq_context)
3021 if (!mark_lock(curr, hlock, LOCK_USED_IN_HARDIRQ))
3022 return 0;
3023 if (curr->softirq_context)
3024 if (!mark_lock(curr, hlock, LOCK_USED_IN_SOFTIRQ))
3025 return 0;
3026 }
3027 }
3028 if (!hlock->hardirqs_off) {
3029 if (hlock->read) {
3030 if (!mark_lock(curr, hlock,
Peter Zijlstra4fc95e82009-01-22 13:10:52 +01003031 LOCK_ENABLED_HARDIRQ_READ))
Peter Zijlstra8e182572007-07-19 01:48:54 -07003032 return 0;
3033 if (curr->softirqs_enabled)
3034 if (!mark_lock(curr, hlock,
Peter Zijlstra4fc95e82009-01-22 13:10:52 +01003035 LOCK_ENABLED_SOFTIRQ_READ))
Peter Zijlstra8e182572007-07-19 01:48:54 -07003036 return 0;
3037 } else {
3038 if (!mark_lock(curr, hlock,
Peter Zijlstra4fc95e82009-01-22 13:10:52 +01003039 LOCK_ENABLED_HARDIRQ))
Peter Zijlstra8e182572007-07-19 01:48:54 -07003040 return 0;
3041 if (curr->softirqs_enabled)
3042 if (!mark_lock(curr, hlock,
Peter Zijlstra4fc95e82009-01-22 13:10:52 +01003043 LOCK_ENABLED_SOFTIRQ))
Peter Zijlstra8e182572007-07-19 01:48:54 -07003044 return 0;
3045 }
3046 }
3047
3048 return 1;
3049}
3050
Boqun Fengc2469752016-02-16 13:57:40 +08003051static inline unsigned int task_irq_context(struct task_struct *task)
3052{
3053 return 2 * !!task->hardirq_context + !!task->softirq_context;
3054}
3055
Peter Zijlstra8e182572007-07-19 01:48:54 -07003056static int separate_irq_context(struct task_struct *curr,
3057 struct held_lock *hlock)
3058{
3059 unsigned int depth = curr->lockdep_depth;
3060
3061 /*
3062 * Keep track of points where we cross into an interrupt context:
3063 */
Peter Zijlstra8e182572007-07-19 01:48:54 -07003064 if (depth) {
3065 struct held_lock *prev_hlock;
3066
3067 prev_hlock = curr->held_locks + depth-1;
3068 /*
3069 * If we cross into another context, reset the
3070 * hash key (this also prevents the checking and the
3071 * adding of the dependency to 'prev'):
3072 */
3073 if (prev_hlock->irq_context != hlock->irq_context)
3074 return 1;
3075 }
3076 return 0;
3077}
3078
Peter Zijlstra0119fee2011-09-02 01:30:29 +02003079#else /* defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING) */
Peter Zijlstra8e182572007-07-19 01:48:54 -07003080
3081static inline
3082int mark_lock_irq(struct task_struct *curr, struct held_lock *this,
3083 enum lock_usage_bit new_bit)
3084{
Peter Zijlstra0119fee2011-09-02 01:30:29 +02003085 WARN_ON(1); /* Impossible innit? when we don't have TRACE_IRQFLAG */
Peter Zijlstra8e182572007-07-19 01:48:54 -07003086 return 1;
3087}
3088
3089static inline int mark_irqflags(struct task_struct *curr,
3090 struct held_lock *hlock)
3091{
3092 return 1;
3093}
3094
Boqun Fengc2469752016-02-16 13:57:40 +08003095static inline unsigned int task_irq_context(struct task_struct *task)
3096{
3097 return 0;
3098}
3099
Peter Zijlstra8e182572007-07-19 01:48:54 -07003100static inline int separate_irq_context(struct task_struct *curr,
3101 struct held_lock *hlock)
3102{
3103 return 0;
3104}
3105
Peter Zijlstra0119fee2011-09-02 01:30:29 +02003106#endif /* defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING) */
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003107
3108/*
Peter Zijlstra8e182572007-07-19 01:48:54 -07003109 * Mark a lock with a usage bit, and validate the state transition:
3110 */
Steven Rostedt1d09daa2008-05-12 21:20:55 +02003111static int mark_lock(struct task_struct *curr, struct held_lock *this,
Steven Rostedt0764d232008-05-12 21:20:44 +02003112 enum lock_usage_bit new_bit)
Peter Zijlstra8e182572007-07-19 01:48:54 -07003113{
3114 unsigned int new_mask = 1 << new_bit, ret = 1;
3115
3116 /*
3117 * If already set then do not dirty the cacheline,
3118 * nor do any checks:
3119 */
Dave Jonesf82b2172008-08-11 09:30:23 +02003120 if (likely(hlock_class(this)->usage_mask & new_mask))
Peter Zijlstra8e182572007-07-19 01:48:54 -07003121 return 1;
3122
3123 if (!graph_lock())
3124 return 0;
3125 /*
Lucas De Marchi25985ed2011-03-30 22:57:33 -03003126 * Make sure we didn't race:
Peter Zijlstra8e182572007-07-19 01:48:54 -07003127 */
Dave Jonesf82b2172008-08-11 09:30:23 +02003128 if (unlikely(hlock_class(this)->usage_mask & new_mask)) {
Peter Zijlstra8e182572007-07-19 01:48:54 -07003129 graph_unlock();
3130 return 1;
3131 }
3132
Dave Jonesf82b2172008-08-11 09:30:23 +02003133 hlock_class(this)->usage_mask |= new_mask;
Peter Zijlstra8e182572007-07-19 01:48:54 -07003134
Dave Jonesf82b2172008-08-11 09:30:23 +02003135 if (!save_trace(hlock_class(this)->usage_traces + new_bit))
Peter Zijlstra8e182572007-07-19 01:48:54 -07003136 return 0;
3137
3138 switch (new_bit) {
Peter Zijlstra53464172009-01-22 14:15:53 +01003139#define LOCKDEP_STATE(__STATE) \
3140 case LOCK_USED_IN_##__STATE: \
3141 case LOCK_USED_IN_##__STATE##_READ: \
3142 case LOCK_ENABLED_##__STATE: \
3143 case LOCK_ENABLED_##__STATE##_READ:
3144#include "lockdep_states.h"
3145#undef LOCKDEP_STATE
Peter Zijlstra8e182572007-07-19 01:48:54 -07003146 ret = mark_lock_irq(curr, this, new_bit);
3147 if (!ret)
3148 return 0;
3149 break;
3150 case LOCK_USED:
Frederic Weisbeckerbd6d29c2010-04-06 00:10:17 +02003151 debug_atomic_dec(nr_unused_locks);
Peter Zijlstra8e182572007-07-19 01:48:54 -07003152 break;
3153 default:
3154 if (!debug_locks_off_graph_unlock())
3155 return 0;
3156 WARN_ON(1);
3157 return 0;
3158 }
3159
3160 graph_unlock();
3161
3162 /*
3163 * We must printk outside of the graph_lock:
3164 */
3165 if (ret == 2) {
3166 printk("\nmarked lock as {%s}:\n", usage_str[new_bit]);
3167 print_lock(this);
3168 print_irqtrace_events(curr);
3169 dump_stack();
3170 }
3171
3172 return ret;
3173}
3174
3175/*
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003176 * Initialize a lock instance's lock-class mapping info:
3177 */
Bart Van Assched35568b2018-12-06 17:11:33 -08003178void lockdep_init_map(struct lockdep_map *lock, const char *name,
Peter Zijlstra4dfbb9d2006-10-11 01:45:14 -04003179 struct lock_class_key *key, int subclass)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003180{
Yong Zhangd3d03d42011-11-09 16:04:51 +08003181 int i;
3182
Yong Zhangd3d03d42011-11-09 16:04:51 +08003183 for (i = 0; i < NR_LOCKDEP_CACHING_CLASSES; i++)
3184 lock->class_cache[i] = NULL;
Hitoshi Mitake62016252010-10-05 18:01:51 +09003185
Peter Zijlstrac8a25002009-04-17 09:40:49 +02003186#ifdef CONFIG_LOCK_STAT
3187 lock->cpu = raw_smp_processor_id();
3188#endif
3189
Peter Zijlstra0119fee2011-09-02 01:30:29 +02003190 /*
3191 * Can't be having no nameless bastards around this place!
3192 */
Peter Zijlstrac8a25002009-04-17 09:40:49 +02003193 if (DEBUG_LOCKS_WARN_ON(!name)) {
3194 lock->name = "NULL";
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003195 return;
Peter Zijlstrac8a25002009-04-17 09:40:49 +02003196 }
3197
3198 lock->name = name;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003199
Peter Zijlstra0119fee2011-09-02 01:30:29 +02003200 /*
3201 * No key, no joy, we need to hash something.
3202 */
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003203 if (DEBUG_LOCKS_WARN_ON(!key))
3204 return;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003205 /*
3206 * Sanity check, the lock-class key must be persistent:
3207 */
3208 if (!static_obj(key)) {
Borislav Petkov04860d42018-02-26 14:49:26 +01003209 printk("BUG: key %px not in .data!\n", key);
Peter Zijlstra0119fee2011-09-02 01:30:29 +02003210 /*
3211 * What it says above ^^^^^, I suggest you read it.
3212 */
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003213 DEBUG_LOCKS_WARN_ON(1);
3214 return;
3215 }
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003216 lock->key = key;
Peter Zijlstrac8a25002009-04-17 09:40:49 +02003217
3218 if (unlikely(!debug_locks))
3219 return;
3220
Peter Zijlstra35a93932015-02-26 16:23:11 +01003221 if (subclass) {
3222 unsigned long flags;
3223
3224 if (DEBUG_LOCKS_WARN_ON(current->lockdep_recursion))
3225 return;
3226
3227 raw_local_irq_save(flags);
3228 current->lockdep_recursion = 1;
Peter Zijlstra4dfbb9d2006-10-11 01:45:14 -04003229 register_lock_class(lock, subclass, 1);
Peter Zijlstra35a93932015-02-26 16:23:11 +01003230 current->lockdep_recursion = 0;
3231 raw_local_irq_restore(flags);
3232 }
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003233}
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003234EXPORT_SYMBOL_GPL(lockdep_init_map);
3235
Peter Zijlstra1704f472010-03-19 01:37:42 +01003236struct lock_class_key __lockdep_no_validate__;
Kent Overstreetea6749c2012-12-27 22:21:58 -08003237EXPORT_SYMBOL_GPL(__lockdep_no_validate__);
Peter Zijlstra1704f472010-03-19 01:37:42 +01003238
Maarten Lankhorstd0945952012-09-13 11:39:51 +02003239static int
3240print_lock_nested_lock_not_held(struct task_struct *curr,
3241 struct held_lock *hlock,
3242 unsigned long ip)
3243{
3244 if (!debug_locks_off())
3245 return 0;
3246 if (debug_locks_silent)
3247 return 0;
3248
Paul E. McKenney681fbec2017-05-04 15:44:38 -07003249 pr_warn("\n");
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08003250 pr_warn("==================================\n");
3251 pr_warn("WARNING: Nested lock was not taken\n");
Maarten Lankhorstd0945952012-09-13 11:39:51 +02003252 print_kernel_ident();
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08003253 pr_warn("----------------------------------\n");
Maarten Lankhorstd0945952012-09-13 11:39:51 +02003254
Paul E. McKenney681fbec2017-05-04 15:44:38 -07003255 pr_warn("%s/%d is trying to lock:\n", curr->comm, task_pid_nr(curr));
Maarten Lankhorstd0945952012-09-13 11:39:51 +02003256 print_lock(hlock);
3257
Paul E. McKenney681fbec2017-05-04 15:44:38 -07003258 pr_warn("\nbut this task is not holding:\n");
3259 pr_warn("%s\n", hlock->nest_lock->name);
Maarten Lankhorstd0945952012-09-13 11:39:51 +02003260
Paul E. McKenney681fbec2017-05-04 15:44:38 -07003261 pr_warn("\nstack backtrace:\n");
Maarten Lankhorstd0945952012-09-13 11:39:51 +02003262 dump_stack();
3263
Paul E. McKenney681fbec2017-05-04 15:44:38 -07003264 pr_warn("\nother info that might help us debug this:\n");
Maarten Lankhorstd0945952012-09-13 11:39:51 +02003265 lockdep_print_held_locks(curr);
3266
Paul E. McKenney681fbec2017-05-04 15:44:38 -07003267 pr_warn("\nstack backtrace:\n");
Maarten Lankhorstd0945952012-09-13 11:39:51 +02003268 dump_stack();
3269
3270 return 0;
3271}
3272
Matthew Wilcox08f36ff2018-01-17 07:14:13 -08003273static int __lock_is_held(const struct lockdep_map *lock, int read);
Maarten Lankhorstd0945952012-09-13 11:39:51 +02003274
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003275/*
3276 * This gets called for every mutex_lock*()/spin_lock*() operation.
3277 * We maintain the dependency maps and validate the locking attempt:
Waiman Long8ee10862018-10-02 16:19:17 -04003278 *
3279 * The callers must make sure that IRQs are disabled before calling it,
3280 * otherwise we could get an interrupt which would want to take locks,
3281 * which would end up in lockdep again.
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003282 */
3283static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
3284 int trylock, int read, int check, int hardirqs_off,
Peter Zijlstrabb97a912009-07-20 19:15:35 +02003285 struct lockdep_map *nest_lock, unsigned long ip,
Peter Zijlstra21199f22015-09-16 16:10:40 +02003286 int references, int pin_count)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003287{
3288 struct task_struct *curr = current;
Ingo Molnard6d897c2006-07-10 04:44:04 -07003289 struct lock_class *class = NULL;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003290 struct held_lock *hlock;
Alfredo Alvarez Fernandez5f18ab52016-02-11 00:33:32 +01003291 unsigned int depth;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003292 int chain_head = 0;
Peter Zijlstrabb97a912009-07-20 19:15:35 +02003293 int class_idx;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003294 u64 chain_key;
3295
3296 if (unlikely(!debug_locks))
3297 return 0;
3298
Oleg Nesterovfb9edbe2014-01-20 19:20:06 +01003299 if (!prove_locking || lock->key == &__lockdep_no_validate__)
3300 check = 0;
Peter Zijlstra1704f472010-03-19 01:37:42 +01003301
Hitoshi Mitake62016252010-10-05 18:01:51 +09003302 if (subclass < NR_LOCKDEP_CACHING_CLASSES)
3303 class = lock->class_cache[subclass];
Ingo Molnard6d897c2006-07-10 04:44:04 -07003304 /*
Hitoshi Mitake62016252010-10-05 18:01:51 +09003305 * Not cached?
Ingo Molnard6d897c2006-07-10 04:44:04 -07003306 */
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003307 if (unlikely(!class)) {
Peter Zijlstra4dfbb9d2006-10-11 01:45:14 -04003308 class = register_lock_class(lock, subclass, 0);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003309 if (!class)
3310 return 0;
3311 }
Waiman Long8ca2b56c2018-10-03 13:07:18 -04003312
3313 debug_class_ops_inc(class);
3314
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003315 if (very_verbose(class)) {
Borislav Petkov04860d42018-02-26 14:49:26 +01003316 printk("\nacquire class [%px] %s", class->key, class->name);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003317 if (class->name_version > 1)
Dmitry Vyukovf943fe02016-11-28 15:24:43 +01003318 printk(KERN_CONT "#%d", class->name_version);
3319 printk(KERN_CONT "\n");
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003320 dump_stack();
3321 }
3322
3323 /*
3324 * Add the lock to the list of currently held locks.
3325 * (we dont increase the depth just yet, up until the
3326 * dependency checks are done)
3327 */
3328 depth = curr->lockdep_depth;
Peter Zijlstra0119fee2011-09-02 01:30:29 +02003329 /*
3330 * Ran out of static storage for our per-task lock stack again have we?
3331 */
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003332 if (DEBUG_LOCKS_WARN_ON(depth >= MAX_LOCK_DEPTH))
3333 return 0;
3334
Peter Zijlstrabb97a912009-07-20 19:15:35 +02003335 class_idx = class - lock_classes + 1;
3336
Ingo Molnare966eae2017-12-12 12:31:16 +01003337 if (depth) {
Peter Zijlstrabb97a912009-07-20 19:15:35 +02003338 hlock = curr->held_locks + depth - 1;
3339 if (hlock->class_idx == class_idx && nest_lock) {
Peter Zijlstra7fb4a2c2017-03-01 16:23:30 +01003340 if (hlock->references) {
3341 /*
3342 * Check: unsigned int references:12, overflow.
3343 */
3344 if (DEBUG_LOCKS_WARN_ON(hlock->references == (1 << 12)-1))
3345 return 0;
3346
Peter Zijlstrabb97a912009-07-20 19:15:35 +02003347 hlock->references++;
Peter Zijlstra7fb4a2c2017-03-01 16:23:30 +01003348 } else {
Peter Zijlstrabb97a912009-07-20 19:15:35 +02003349 hlock->references = 2;
Peter Zijlstra7fb4a2c2017-03-01 16:23:30 +01003350 }
Peter Zijlstrabb97a912009-07-20 19:15:35 +02003351
3352 return 1;
3353 }
3354 }
3355
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003356 hlock = curr->held_locks + depth;
Peter Zijlstra0119fee2011-09-02 01:30:29 +02003357 /*
3358 * Plain impossible, we just registered it and checked it weren't no
3359 * NULL like.. I bet this mushroom I ate was good!
3360 */
Dave Jonesf82b2172008-08-11 09:30:23 +02003361 if (DEBUG_LOCKS_WARN_ON(!class))
3362 return 0;
Peter Zijlstrabb97a912009-07-20 19:15:35 +02003363 hlock->class_idx = class_idx;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003364 hlock->acquire_ip = ip;
3365 hlock->instance = lock;
Peter Zijlstra7531e2f2008-08-11 09:30:24 +02003366 hlock->nest_lock = nest_lock;
Boqun Fengc2469752016-02-16 13:57:40 +08003367 hlock->irq_context = task_irq_context(curr);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003368 hlock->trylock = trylock;
3369 hlock->read = read;
3370 hlock->check = check;
Dmitry Baryshkov6951b122008-08-18 04:26:37 +04003371 hlock->hardirqs_off = !!hardirqs_off;
Peter Zijlstrabb97a912009-07-20 19:15:35 +02003372 hlock->references = references;
Peter Zijlstraf20786f2007-07-19 01:48:56 -07003373#ifdef CONFIG_LOCK_STAT
3374 hlock->waittime_stamp = 0;
Peter Zijlstra3365e7792009-10-09 10:12:41 +02003375 hlock->holdtime_stamp = lockstat_clock();
Peter Zijlstraf20786f2007-07-19 01:48:56 -07003376#endif
Peter Zijlstra21199f22015-09-16 16:10:40 +02003377 hlock->pin_count = pin_count;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003378
Oleg Nesterovfb9edbe2014-01-20 19:20:06 +01003379 if (check && !mark_irqflags(curr, hlock))
Peter Zijlstra8e182572007-07-19 01:48:54 -07003380 return 0;
3381
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003382 /* mark it as used: */
Jarek Poplawski4ff773bb2007-05-08 00:31:00 -07003383 if (!mark_lock(curr, hlock, LOCK_USED))
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003384 return 0;
Peter Zijlstra8e182572007-07-19 01:48:54 -07003385
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003386 /*
Gautham R Shenoy17aacfb92007-10-28 20:47:01 +01003387 * Calculate the chain hash: it's the combined hash of all the
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003388 * lock keys along the dependency chain. We save the hash value
3389 * at every step so that we can get the current hash easily
3390 * after unlock. The chain hash is then used to cache dependency
3391 * results.
3392 *
3393 * The 'key ID' is what is the most compact key value to drive
3394 * the hash, not class->key.
3395 */
Peter Zijlstra0119fee2011-09-02 01:30:29 +02003396 /*
3397 * Whoops, we did it again.. ran straight out of our static allocation.
3398 */
Alfredo Alvarez Fernandez5f18ab52016-02-11 00:33:32 +01003399 if (DEBUG_LOCKS_WARN_ON(class_idx > MAX_LOCKDEP_KEYS))
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003400 return 0;
3401
3402 chain_key = curr->curr_chain_key;
3403 if (!depth) {
Peter Zijlstra0119fee2011-09-02 01:30:29 +02003404 /*
3405 * How can we have a chain hash when we ain't got no keys?!
3406 */
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003407 if (DEBUG_LOCKS_WARN_ON(chain_key != 0))
3408 return 0;
3409 chain_head = 1;
3410 }
3411
3412 hlock->prev_chain_key = chain_key;
Peter Zijlstra8e182572007-07-19 01:48:54 -07003413 if (separate_irq_context(curr, hlock)) {
3414 chain_key = 0;
3415 chain_head = 1;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003416 }
Alfredo Alvarez Fernandez5f18ab52016-02-11 00:33:32 +01003417 chain_key = iterate_chain_key(chain_key, class_idx);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003418
Peter Zijlstraf8319482016-11-30 14:32:25 +11003419 if (nest_lock && !__lock_is_held(nest_lock, -1))
Maarten Lankhorstd0945952012-09-13 11:39:51 +02003420 return print_lock_nested_lock_not_held(curr, hlock, ip);
3421
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08003422 if (!debug_locks_silent) {
3423 WARN_ON_ONCE(depth && !hlock_class(hlock - 1)->key);
3424 WARN_ON_ONCE(!hlock_class(hlock)->key);
3425 }
3426
Gregory Haskins3aa416b2007-10-11 22:11:11 +02003427 if (!validate_chain(curr, lock, hlock, chain_head, chain_key))
Peter Zijlstra8e182572007-07-19 01:48:54 -07003428 return 0;
Jarek Poplawski381a2292007-02-10 01:44:58 -08003429
Gregory Haskins3aa416b2007-10-11 22:11:11 +02003430 curr->curr_chain_key = chain_key;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003431 curr->lockdep_depth++;
3432 check_chain_key(curr);
Jarek Poplawski60e114d2007-02-20 13:58:00 -08003433#ifdef CONFIG_DEBUG_LOCKDEP
3434 if (unlikely(!debug_locks))
3435 return 0;
3436#endif
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003437 if (unlikely(curr->lockdep_depth >= MAX_LOCK_DEPTH)) {
3438 debug_locks_off();
Dave Jones2c522832013-04-25 13:40:02 -04003439 print_lockdep_off("BUG: MAX_LOCK_DEPTH too low!");
3440 printk(KERN_DEBUG "depth: %i max: %lu!\n",
Ben Greearc0540602013-02-06 10:56:19 -08003441 curr->lockdep_depth, MAX_LOCK_DEPTH);
Ben Greearc0540602013-02-06 10:56:19 -08003442
3443 lockdep_print_held_locks(current);
3444 debug_show_all_locks();
Peter Zijlstraeedeeab2009-03-18 12:38:47 +01003445 dump_stack();
Ben Greearc0540602013-02-06 10:56:19 -08003446
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003447 return 0;
3448 }
Jarek Poplawski381a2292007-02-10 01:44:58 -08003449
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003450 if (unlikely(curr->lockdep_depth > max_lockdep_depth))
3451 max_lockdep_depth = curr->lockdep_depth;
3452
3453 return 1;
3454}
3455
3456static int
Srivatsa S. Bhatf86f7552013-01-08 18:35:58 +05303457print_unlock_imbalance_bug(struct task_struct *curr, struct lockdep_map *lock,
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003458 unsigned long ip)
3459{
3460 if (!debug_locks_off())
3461 return 0;
3462 if (debug_locks_silent)
3463 return 0;
3464
Paul E. McKenney681fbec2017-05-04 15:44:38 -07003465 pr_warn("\n");
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08003466 pr_warn("=====================================\n");
3467 pr_warn("WARNING: bad unlock balance detected!\n");
Ben Hutchingsfbdc4b92011-10-28 04:36:55 +01003468 print_kernel_ident();
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08003469 pr_warn("-------------------------------------\n");
Paul E. McKenney681fbec2017-05-04 15:44:38 -07003470 pr_warn("%s/%d is trying to release lock (",
Pavel Emelyanovba25f9d2007-10-18 23:40:40 -07003471 curr->comm, task_pid_nr(curr));
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003472 print_lockdep_cache(lock);
Paul E. McKenney681fbec2017-05-04 15:44:38 -07003473 pr_cont(") at:\n");
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003474 print_ip_sym(ip);
Paul E. McKenney681fbec2017-05-04 15:44:38 -07003475 pr_warn("but there are no more locks to release!\n");
3476 pr_warn("\nother info that might help us debug this:\n");
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003477 lockdep_print_held_locks(curr);
3478
Paul E. McKenney681fbec2017-05-04 15:44:38 -07003479 pr_warn("\nstack backtrace:\n");
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003480 dump_stack();
3481
3482 return 0;
3483}
3484
Matthew Wilcox08f36ff2018-01-17 07:14:13 -08003485static int match_held_lock(const struct held_lock *hlock,
3486 const struct lockdep_map *lock)
Peter Zijlstrabb97a912009-07-20 19:15:35 +02003487{
3488 if (hlock->instance == lock)
3489 return 1;
3490
3491 if (hlock->references) {
Matthew Wilcox08f36ff2018-01-17 07:14:13 -08003492 const struct lock_class *class = lock->class_cache[0];
Peter Zijlstrabb97a912009-07-20 19:15:35 +02003493
3494 if (!class)
3495 class = look_up_lock_class(lock, 0);
3496
Peter Zijlstra80e04012011-08-05 14:26:17 +02003497 /*
3498 * If look_up_lock_class() failed to find a class, we're trying
3499 * to test if we hold a lock that has never yet been acquired.
3500 * Clearly if the lock hasn't been acquired _ever_, we're not
3501 * holding it either, so report failure.
3502 */
Matthew Wilcox64f29d12018-01-17 07:14:12 -08003503 if (!class)
Peter Zijlstrabb97a912009-07-20 19:15:35 +02003504 return 0;
3505
Peter Zijlstra0119fee2011-09-02 01:30:29 +02003506 /*
3507 * References, but not a lock we're actually ref-counting?
3508 * State got messed up, follow the sites that change ->references
3509 * and try to make sense of it.
3510 */
Peter Zijlstrabb97a912009-07-20 19:15:35 +02003511 if (DEBUG_LOCKS_WARN_ON(!hlock->nest_lock))
3512 return 0;
3513
3514 if (hlock->class_idx == class - lock_classes + 1)
3515 return 1;
3516 }
3517
3518 return 0;
3519}
3520
J. R. Okajima41c2c5b2017-02-03 01:38:15 +09003521/* @depth must not be zero */
3522static struct held_lock *find_held_lock(struct task_struct *curr,
3523 struct lockdep_map *lock,
3524 unsigned int depth, int *idx)
3525{
3526 struct held_lock *ret, *hlock, *prev_hlock;
3527 int i;
3528
3529 i = depth - 1;
3530 hlock = curr->held_locks + i;
3531 ret = hlock;
3532 if (match_held_lock(hlock, lock))
3533 goto out;
3534
3535 ret = NULL;
3536 for (i--, prev_hlock = hlock--;
3537 i >= 0;
3538 i--, prev_hlock = hlock--) {
3539 /*
3540 * We must not cross into another context:
3541 */
3542 if (prev_hlock->irq_context != hlock->irq_context) {
3543 ret = NULL;
3544 break;
3545 }
3546 if (match_held_lock(hlock, lock)) {
3547 ret = hlock;
3548 break;
3549 }
3550 }
3551
3552out:
3553 *idx = i;
3554 return ret;
3555}
3556
J. R. Okajimae9699702017-02-03 01:38:16 +09003557static int reacquire_held_locks(struct task_struct *curr, unsigned int depth,
3558 int idx)
3559{
3560 struct held_lock *hlock;
3561
Waiman Long8ee10862018-10-02 16:19:17 -04003562 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
3563 return 0;
3564
J. R. Okajimae9699702017-02-03 01:38:16 +09003565 for (hlock = curr->held_locks + idx; idx < depth; idx++, hlock++) {
3566 if (!__lock_acquire(hlock->instance,
3567 hlock_class(hlock)->subclass,
3568 hlock->trylock,
3569 hlock->read, hlock->check,
3570 hlock->hardirqs_off,
3571 hlock->nest_lock, hlock->acquire_ip,
3572 hlock->references, hlock->pin_count))
3573 return 1;
3574 }
3575 return 0;
3576}
3577
Peter Zijlstra64aa3482008-08-11 09:30:21 +02003578static int
Peter Zijlstra00ef9f72008-12-04 09:00:17 +01003579__lock_set_class(struct lockdep_map *lock, const char *name,
3580 struct lock_class_key *key, unsigned int subclass,
3581 unsigned long ip)
Peter Zijlstra64aa3482008-08-11 09:30:21 +02003582{
3583 struct task_struct *curr = current;
J. R. Okajima41c2c5b2017-02-03 01:38:15 +09003584 struct held_lock *hlock;
Peter Zijlstra64aa3482008-08-11 09:30:21 +02003585 struct lock_class *class;
3586 unsigned int depth;
3587 int i;
3588
Waiman Long513e1072019-01-09 23:03:25 -05003589 if (unlikely(!debug_locks))
3590 return 0;
3591
Peter Zijlstra64aa3482008-08-11 09:30:21 +02003592 depth = curr->lockdep_depth;
Peter Zijlstra0119fee2011-09-02 01:30:29 +02003593 /*
3594 * This function is about (re)setting the class of a held lock,
3595 * yet we're not actually holding any locks. Naughty user!
3596 */
Peter Zijlstra64aa3482008-08-11 09:30:21 +02003597 if (DEBUG_LOCKS_WARN_ON(!depth))
3598 return 0;
3599
J. R. Okajima41c2c5b2017-02-03 01:38:15 +09003600 hlock = find_held_lock(curr, lock, depth, &i);
3601 if (!hlock)
3602 return print_unlock_imbalance_bug(curr, lock, ip);
Peter Zijlstra64aa3482008-08-11 09:30:21 +02003603
Peter Zijlstra00ef9f72008-12-04 09:00:17 +01003604 lockdep_init_map(lock, name, key, 0);
Peter Zijlstra64aa3482008-08-11 09:30:21 +02003605 class = register_lock_class(lock, subclass, 0);
Dave Jonesf82b2172008-08-11 09:30:23 +02003606 hlock->class_idx = class - lock_classes + 1;
Peter Zijlstra64aa3482008-08-11 09:30:21 +02003607
3608 curr->lockdep_depth = i;
3609 curr->curr_chain_key = hlock->prev_chain_key;
3610
J. R. Okajimae9699702017-02-03 01:38:16 +09003611 if (reacquire_held_locks(curr, depth, i))
3612 return 0;
Peter Zijlstra64aa3482008-08-11 09:30:21 +02003613
Peter Zijlstra0119fee2011-09-02 01:30:29 +02003614 /*
3615 * I took it apart and put it back together again, except now I have
3616 * these 'spare' parts.. where shall I put them.
3617 */
Peter Zijlstra64aa3482008-08-11 09:30:21 +02003618 if (DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth))
3619 return 0;
3620 return 1;
3621}
3622
J. R. Okajima6419c4a2017-02-03 01:38:17 +09003623static int __lock_downgrade(struct lockdep_map *lock, unsigned long ip)
3624{
3625 struct task_struct *curr = current;
3626 struct held_lock *hlock;
3627 unsigned int depth;
3628 int i;
3629
Waiman Long71492582019-01-09 23:03:25 -05003630 if (unlikely(!debug_locks))
3631 return 0;
3632
J. R. Okajima6419c4a2017-02-03 01:38:17 +09003633 depth = curr->lockdep_depth;
3634 /*
3635 * This function is about (re)setting the class of a held lock,
3636 * yet we're not actually holding any locks. Naughty user!
3637 */
3638 if (DEBUG_LOCKS_WARN_ON(!depth))
3639 return 0;
3640
3641 hlock = find_held_lock(curr, lock, depth, &i);
3642 if (!hlock)
3643 return print_unlock_imbalance_bug(curr, lock, ip);
3644
3645 curr->lockdep_depth = i;
3646 curr->curr_chain_key = hlock->prev_chain_key;
3647
3648 WARN(hlock->read, "downgrading a read lock");
3649 hlock->read = 1;
3650 hlock->acquire_ip = ip;
3651
3652 if (reacquire_held_locks(curr, depth, i))
3653 return 0;
3654
3655 /*
3656 * I took it apart and put it back together again, except now I have
3657 * these 'spare' parts.. where shall I put them.
3658 */
3659 if (DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth))
3660 return 0;
3661 return 1;
3662}
3663
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003664/*
Peter Zijlstrae0f56fd2015-06-11 14:46:52 +02003665 * Remove the lock to the list of currently held locks - this gets
3666 * called on mutex_unlock()/spin_unlock*() (or on a failed
3667 * mutex_lock_interruptible()).
3668 *
3669 * @nested is an hysterical artifact, needs a tree wide cleanup.
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003670 */
3671static int
Peter Zijlstrae0f56fd2015-06-11 14:46:52 +02003672__lock_release(struct lockdep_map *lock, int nested, unsigned long ip)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003673{
Peter Zijlstrae0f56fd2015-06-11 14:46:52 +02003674 struct task_struct *curr = current;
J. R. Okajima41c2c5b2017-02-03 01:38:15 +09003675 struct held_lock *hlock;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003676 unsigned int depth;
Ingo Molnare966eae2017-12-12 12:31:16 +01003677 int i;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003678
Peter Zijlstrae0f56fd2015-06-11 14:46:52 +02003679 if (unlikely(!debug_locks))
3680 return 0;
3681
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003682 depth = curr->lockdep_depth;
Peter Zijlstra0119fee2011-09-02 01:30:29 +02003683 /*
3684 * So we're all set to release this lock.. wait what lock? We don't
3685 * own any locks, you've been drinking again?
3686 */
Peter Zijlstrae0f56fd2015-06-11 14:46:52 +02003687 if (DEBUG_LOCKS_WARN_ON(depth <= 0))
3688 return print_unlock_imbalance_bug(curr, lock, ip);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003689
Peter Zijlstrae0f56fd2015-06-11 14:46:52 +02003690 /*
3691 * Check whether the lock exists in the current stack
3692 * of held locks:
3693 */
J. R. Okajima41c2c5b2017-02-03 01:38:15 +09003694 hlock = find_held_lock(curr, lock, depth, &i);
3695 if (!hlock)
3696 return print_unlock_imbalance_bug(curr, lock, ip);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003697
Peter Zijlstrabb97a912009-07-20 19:15:35 +02003698 if (hlock->instance == lock)
3699 lock_release_holdtime(hlock);
3700
Peter Zijlstraa24fc602015-06-11 14:46:53 +02003701 WARN(hlock->pin_count, "releasing a pinned lock\n");
3702
Peter Zijlstrabb97a912009-07-20 19:15:35 +02003703 if (hlock->references) {
3704 hlock->references--;
3705 if (hlock->references) {
3706 /*
3707 * We had, and after removing one, still have
3708 * references, the current lock stack is still
3709 * valid. We're done!
3710 */
3711 return 1;
3712 }
3713 }
Peter Zijlstraf20786f2007-07-19 01:48:56 -07003714
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003715 /*
3716 * We have the right lock to unlock, 'hlock' points to it.
3717 * Now we remove it from the stack, and add back the other
3718 * entries (if any), recalculating the hash along the way:
3719 */
Peter Zijlstrabb97a912009-07-20 19:15:35 +02003720
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003721 curr->lockdep_depth = i;
3722 curr->curr_chain_key = hlock->prev_chain_key;
3723
Waiman Longce52a182018-10-02 16:19:18 -04003724 /*
3725 * The most likely case is when the unlock is on the innermost
3726 * lock. In this case, we are done!
3727 */
3728 if (i == depth-1)
3729 return 1;
3730
J. R. Okajimae9699702017-02-03 01:38:16 +09003731 if (reacquire_held_locks(curr, depth, i + 1))
3732 return 0;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003733
Peter Zijlstra0119fee2011-09-02 01:30:29 +02003734 /*
3735 * We had N bottles of beer on the wall, we drank one, but now
3736 * there's not N-1 bottles of beer left on the wall...
3737 */
Waiman Longce52a182018-10-02 16:19:18 -04003738 DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth-1);
Peter Zijlstrae0f56fd2015-06-11 14:46:52 +02003739
Waiman Longce52a182018-10-02 16:19:18 -04003740 /*
3741 * Since reacquire_held_locks() would have called check_chain_key()
3742 * indirectly via __lock_acquire(), we don't need to do it again
3743 * on return.
3744 */
3745 return 0;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003746}
3747
Matthew Wilcox08f36ff2018-01-17 07:14:13 -08003748static int __lock_is_held(const struct lockdep_map *lock, int read)
Peter Zijlstraf607c662009-07-20 19:16:29 +02003749{
3750 struct task_struct *curr = current;
3751 int i;
3752
3753 for (i = 0; i < curr->lockdep_depth; i++) {
Peter Zijlstrabb97a912009-07-20 19:15:35 +02003754 struct held_lock *hlock = curr->held_locks + i;
3755
Peter Zijlstraf8319482016-11-30 14:32:25 +11003756 if (match_held_lock(hlock, lock)) {
3757 if (read == -1 || hlock->read == read)
3758 return 1;
3759
3760 return 0;
3761 }
Peter Zijlstraf607c662009-07-20 19:16:29 +02003762 }
3763
3764 return 0;
3765}
3766
Peter Zijlstrae7904a22015-08-01 19:25:08 +02003767static struct pin_cookie __lock_pin_lock(struct lockdep_map *lock)
3768{
3769 struct pin_cookie cookie = NIL_COOKIE;
3770 struct task_struct *curr = current;
3771 int i;
3772
3773 if (unlikely(!debug_locks))
3774 return cookie;
3775
3776 for (i = 0; i < curr->lockdep_depth; i++) {
3777 struct held_lock *hlock = curr->held_locks + i;
3778
3779 if (match_held_lock(hlock, lock)) {
3780 /*
3781 * Grab 16bits of randomness; this is sufficient to not
3782 * be guessable and still allows some pin nesting in
3783 * our u32 pin_count.
3784 */
3785 cookie.val = 1 + (prandom_u32() >> 16);
3786 hlock->pin_count += cookie.val;
3787 return cookie;
3788 }
3789 }
3790
3791 WARN(1, "pinning an unheld lock\n");
3792 return cookie;
3793}
3794
3795static void __lock_repin_lock(struct lockdep_map *lock, struct pin_cookie cookie)
Peter Zijlstraa24fc602015-06-11 14:46:53 +02003796{
3797 struct task_struct *curr = current;
3798 int i;
3799
3800 if (unlikely(!debug_locks))
3801 return;
3802
3803 for (i = 0; i < curr->lockdep_depth; i++) {
3804 struct held_lock *hlock = curr->held_locks + i;
3805
3806 if (match_held_lock(hlock, lock)) {
Peter Zijlstrae7904a22015-08-01 19:25:08 +02003807 hlock->pin_count += cookie.val;
Peter Zijlstraa24fc602015-06-11 14:46:53 +02003808 return;
3809 }
3810 }
3811
3812 WARN(1, "pinning an unheld lock\n");
3813}
3814
Peter Zijlstrae7904a22015-08-01 19:25:08 +02003815static void __lock_unpin_lock(struct lockdep_map *lock, struct pin_cookie cookie)
Peter Zijlstraa24fc602015-06-11 14:46:53 +02003816{
3817 struct task_struct *curr = current;
3818 int i;
3819
3820 if (unlikely(!debug_locks))
3821 return;
3822
3823 for (i = 0; i < curr->lockdep_depth; i++) {
3824 struct held_lock *hlock = curr->held_locks + i;
3825
3826 if (match_held_lock(hlock, lock)) {
3827 if (WARN(!hlock->pin_count, "unpinning an unpinned lock\n"))
3828 return;
3829
Peter Zijlstrae7904a22015-08-01 19:25:08 +02003830 hlock->pin_count -= cookie.val;
3831
3832 if (WARN((int)hlock->pin_count < 0, "pin count corrupted\n"))
3833 hlock->pin_count = 0;
3834
Peter Zijlstraa24fc602015-06-11 14:46:53 +02003835 return;
3836 }
3837 }
3838
3839 WARN(1, "unpinning an unheld lock\n");
3840}
3841
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003842/*
3843 * Check whether we follow the irq-flags state precisely:
3844 */
Steven Rostedt1d09daa2008-05-12 21:20:55 +02003845static void check_flags(unsigned long flags)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003846{
Ingo Molnar992860e2008-07-14 10:28:38 +02003847#if defined(CONFIG_PROVE_LOCKING) && defined(CONFIG_DEBUG_LOCKDEP) && \
3848 defined(CONFIG_TRACE_IRQFLAGS)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003849 if (!debug_locks)
3850 return;
3851
Ingo Molnar5f9fa8a2007-12-07 19:02:47 +01003852 if (irqs_disabled_flags(flags)) {
3853 if (DEBUG_LOCKS_WARN_ON(current->hardirqs_enabled)) {
3854 printk("possible reason: unannotated irqs-off.\n");
3855 }
3856 } else {
3857 if (DEBUG_LOCKS_WARN_ON(!current->hardirqs_enabled)) {
3858 printk("possible reason: unannotated irqs-on.\n");
3859 }
3860 }
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003861
3862 /*
3863 * We dont accurately track softirq state in e.g.
3864 * hardirq contexts (such as on 4KSTACKS), so only
3865 * check if not in hardirq contexts:
3866 */
3867 if (!hardirq_count()) {
Peter Zijlstra0119fee2011-09-02 01:30:29 +02003868 if (softirq_count()) {
3869 /* like the above, but with softirqs */
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003870 DEBUG_LOCKS_WARN_ON(current->softirqs_enabled);
Peter Zijlstra0119fee2011-09-02 01:30:29 +02003871 } else {
3872 /* lick the above, does it taste good? */
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003873 DEBUG_LOCKS_WARN_ON(!current->softirqs_enabled);
Peter Zijlstra0119fee2011-09-02 01:30:29 +02003874 }
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003875 }
3876
3877 if (!debug_locks)
3878 print_irqtrace_events(current);
3879#endif
3880}
3881
Peter Zijlstra00ef9f72008-12-04 09:00:17 +01003882void lock_set_class(struct lockdep_map *lock, const char *name,
3883 struct lock_class_key *key, unsigned int subclass,
3884 unsigned long ip)
Peter Zijlstra64aa3482008-08-11 09:30:21 +02003885{
3886 unsigned long flags;
3887
3888 if (unlikely(current->lockdep_recursion))
3889 return;
3890
3891 raw_local_irq_save(flags);
3892 current->lockdep_recursion = 1;
3893 check_flags(flags);
Peter Zijlstra00ef9f72008-12-04 09:00:17 +01003894 if (__lock_set_class(lock, name, key, subclass, ip))
Peter Zijlstra64aa3482008-08-11 09:30:21 +02003895 check_chain_key(current);
3896 current->lockdep_recursion = 0;
3897 raw_local_irq_restore(flags);
3898}
Peter Zijlstra00ef9f72008-12-04 09:00:17 +01003899EXPORT_SYMBOL_GPL(lock_set_class);
Peter Zijlstra64aa3482008-08-11 09:30:21 +02003900
J. R. Okajima6419c4a2017-02-03 01:38:17 +09003901void lock_downgrade(struct lockdep_map *lock, unsigned long ip)
3902{
3903 unsigned long flags;
3904
3905 if (unlikely(current->lockdep_recursion))
3906 return;
3907
3908 raw_local_irq_save(flags);
3909 current->lockdep_recursion = 1;
3910 check_flags(flags);
3911 if (__lock_downgrade(lock, ip))
3912 check_chain_key(current);
3913 current->lockdep_recursion = 0;
3914 raw_local_irq_restore(flags);
3915}
3916EXPORT_SYMBOL_GPL(lock_downgrade);
3917
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003918/*
3919 * We are not always called with irqs disabled - do that here,
3920 * and also avoid lockdep recursion:
3921 */
Steven Rostedt1d09daa2008-05-12 21:20:55 +02003922void lock_acquire(struct lockdep_map *lock, unsigned int subclass,
Peter Zijlstra7531e2f2008-08-11 09:30:24 +02003923 int trylock, int read, int check,
3924 struct lockdep_map *nest_lock, unsigned long ip)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003925{
3926 unsigned long flags;
3927
3928 if (unlikely(current->lockdep_recursion))
3929 return;
3930
3931 raw_local_irq_save(flags);
3932 check_flags(flags);
3933
3934 current->lockdep_recursion = 1;
Frederic Weisbeckerdb2c4c72010-02-02 23:34:40 +01003935 trace_lock_acquire(lock, subclass, trylock, read, check, nest_lock, ip);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003936 __lock_acquire(lock, subclass, trylock, read, check,
Peter Zijlstra21199f22015-09-16 16:10:40 +02003937 irqs_disabled_flags(flags), nest_lock, ip, 0, 0);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003938 current->lockdep_recursion = 0;
3939 raw_local_irq_restore(flags);
3940}
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003941EXPORT_SYMBOL_GPL(lock_acquire);
3942
Steven Rostedt1d09daa2008-05-12 21:20:55 +02003943void lock_release(struct lockdep_map *lock, int nested,
Steven Rostedt0764d232008-05-12 21:20:44 +02003944 unsigned long ip)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003945{
3946 unsigned long flags;
3947
3948 if (unlikely(current->lockdep_recursion))
3949 return;
3950
3951 raw_local_irq_save(flags);
3952 check_flags(flags);
3953 current->lockdep_recursion = 1;
Frederic Weisbecker93135432010-05-08 06:24:25 +02003954 trace_lock_release(lock, ip);
Peter Zijlstrae0f56fd2015-06-11 14:46:52 +02003955 if (__lock_release(lock, nested, ip))
3956 check_chain_key(current);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003957 current->lockdep_recursion = 0;
3958 raw_local_irq_restore(flags);
3959}
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07003960EXPORT_SYMBOL_GPL(lock_release);
3961
Matthew Wilcox08f36ff2018-01-17 07:14:13 -08003962int lock_is_held_type(const struct lockdep_map *lock, int read)
Peter Zijlstraf607c662009-07-20 19:16:29 +02003963{
3964 unsigned long flags;
3965 int ret = 0;
3966
3967 if (unlikely(current->lockdep_recursion))
Peter Zijlstraf2513cd2011-06-06 12:32:43 +02003968 return 1; /* avoid false negative lockdep_assert_held() */
Peter Zijlstraf607c662009-07-20 19:16:29 +02003969
3970 raw_local_irq_save(flags);
3971 check_flags(flags);
3972
3973 current->lockdep_recursion = 1;
Peter Zijlstraf8319482016-11-30 14:32:25 +11003974 ret = __lock_is_held(lock, read);
Peter Zijlstraf607c662009-07-20 19:16:29 +02003975 current->lockdep_recursion = 0;
3976 raw_local_irq_restore(flags);
3977
3978 return ret;
3979}
Peter Zijlstraf8319482016-11-30 14:32:25 +11003980EXPORT_SYMBOL_GPL(lock_is_held_type);
Peter Zijlstraf607c662009-07-20 19:16:29 +02003981
Peter Zijlstrae7904a22015-08-01 19:25:08 +02003982struct pin_cookie lock_pin_lock(struct lockdep_map *lock)
Peter Zijlstraa24fc602015-06-11 14:46:53 +02003983{
Peter Zijlstrae7904a22015-08-01 19:25:08 +02003984 struct pin_cookie cookie = NIL_COOKIE;
Peter Zijlstraa24fc602015-06-11 14:46:53 +02003985 unsigned long flags;
3986
3987 if (unlikely(current->lockdep_recursion))
Peter Zijlstrae7904a22015-08-01 19:25:08 +02003988 return cookie;
Peter Zijlstraa24fc602015-06-11 14:46:53 +02003989
3990 raw_local_irq_save(flags);
3991 check_flags(flags);
3992
3993 current->lockdep_recursion = 1;
Peter Zijlstrae7904a22015-08-01 19:25:08 +02003994 cookie = __lock_pin_lock(lock);
Peter Zijlstraa24fc602015-06-11 14:46:53 +02003995 current->lockdep_recursion = 0;
3996 raw_local_irq_restore(flags);
Peter Zijlstrae7904a22015-08-01 19:25:08 +02003997
3998 return cookie;
Peter Zijlstraa24fc602015-06-11 14:46:53 +02003999}
4000EXPORT_SYMBOL_GPL(lock_pin_lock);
4001
Peter Zijlstrae7904a22015-08-01 19:25:08 +02004002void lock_repin_lock(struct lockdep_map *lock, struct pin_cookie cookie)
Peter Zijlstraa24fc602015-06-11 14:46:53 +02004003{
4004 unsigned long flags;
4005
4006 if (unlikely(current->lockdep_recursion))
4007 return;
4008
4009 raw_local_irq_save(flags);
4010 check_flags(flags);
4011
4012 current->lockdep_recursion = 1;
Peter Zijlstrae7904a22015-08-01 19:25:08 +02004013 __lock_repin_lock(lock, cookie);
4014 current->lockdep_recursion = 0;
4015 raw_local_irq_restore(flags);
4016}
4017EXPORT_SYMBOL_GPL(lock_repin_lock);
4018
4019void lock_unpin_lock(struct lockdep_map *lock, struct pin_cookie cookie)
4020{
4021 unsigned long flags;
4022
4023 if (unlikely(current->lockdep_recursion))
4024 return;
4025
4026 raw_local_irq_save(flags);
4027 check_flags(flags);
4028
4029 current->lockdep_recursion = 1;
4030 __lock_unpin_lock(lock, cookie);
Peter Zijlstraa24fc602015-06-11 14:46:53 +02004031 current->lockdep_recursion = 0;
4032 raw_local_irq_restore(flags);
4033}
4034EXPORT_SYMBOL_GPL(lock_unpin_lock);
4035
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004036#ifdef CONFIG_LOCK_STAT
4037static int
4038print_lock_contention_bug(struct task_struct *curr, struct lockdep_map *lock,
4039 unsigned long ip)
4040{
4041 if (!debug_locks_off())
4042 return 0;
4043 if (debug_locks_silent)
4044 return 0;
4045
Paul E. McKenney681fbec2017-05-04 15:44:38 -07004046 pr_warn("\n");
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08004047 pr_warn("=================================\n");
4048 pr_warn("WARNING: bad contention detected!\n");
Ben Hutchingsfbdc4b92011-10-28 04:36:55 +01004049 print_kernel_ident();
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08004050 pr_warn("---------------------------------\n");
Paul E. McKenney681fbec2017-05-04 15:44:38 -07004051 pr_warn("%s/%d is trying to contend lock (",
Pavel Emelyanovba25f9d2007-10-18 23:40:40 -07004052 curr->comm, task_pid_nr(curr));
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004053 print_lockdep_cache(lock);
Paul E. McKenney681fbec2017-05-04 15:44:38 -07004054 pr_cont(") at:\n");
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004055 print_ip_sym(ip);
Paul E. McKenney681fbec2017-05-04 15:44:38 -07004056 pr_warn("but there are no locks held!\n");
4057 pr_warn("\nother info that might help us debug this:\n");
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004058 lockdep_print_held_locks(curr);
4059
Paul E. McKenney681fbec2017-05-04 15:44:38 -07004060 pr_warn("\nstack backtrace:\n");
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004061 dump_stack();
4062
4063 return 0;
4064}
4065
4066static void
4067__lock_contended(struct lockdep_map *lock, unsigned long ip)
4068{
4069 struct task_struct *curr = current;
J. R. Okajima41c2c5b2017-02-03 01:38:15 +09004070 struct held_lock *hlock;
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004071 struct lock_class_stats *stats;
4072 unsigned int depth;
Peter Zijlstrac7e78cf2008-10-16 23:17:09 +02004073 int i, contention_point, contending_point;
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004074
4075 depth = curr->lockdep_depth;
Peter Zijlstra0119fee2011-09-02 01:30:29 +02004076 /*
4077 * Whee, we contended on this lock, except it seems we're not
4078 * actually trying to acquire anything much at all..
4079 */
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004080 if (DEBUG_LOCKS_WARN_ON(!depth))
4081 return;
4082
J. R. Okajima41c2c5b2017-02-03 01:38:15 +09004083 hlock = find_held_lock(curr, lock, depth, &i);
4084 if (!hlock) {
4085 print_lock_contention_bug(curr, lock, ip);
4086 return;
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004087 }
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004088
Peter Zijlstrabb97a912009-07-20 19:15:35 +02004089 if (hlock->instance != lock)
4090 return;
4091
Peter Zijlstra3365e7792009-10-09 10:12:41 +02004092 hlock->waittime_stamp = lockstat_clock();
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004093
Peter Zijlstrac7e78cf2008-10-16 23:17:09 +02004094 contention_point = lock_point(hlock_class(hlock)->contention_point, ip);
4095 contending_point = lock_point(hlock_class(hlock)->contending_point,
4096 lock->ip);
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004097
Dave Jonesf82b2172008-08-11 09:30:23 +02004098 stats = get_lock_stats(hlock_class(hlock));
Peter Zijlstrac7e78cf2008-10-16 23:17:09 +02004099 if (contention_point < LOCKSTAT_POINTS)
4100 stats->contention_point[contention_point]++;
4101 if (contending_point < LOCKSTAT_POINTS)
4102 stats->contending_point[contending_point]++;
Peter Zijlstra96645672007-07-19 01:49:00 -07004103 if (lock->cpu != smp_processor_id())
4104 stats->bounces[bounce_contended + !!hlock->read]++;
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004105}
4106
4107static void
Peter Zijlstrac7e78cf2008-10-16 23:17:09 +02004108__lock_acquired(struct lockdep_map *lock, unsigned long ip)
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004109{
4110 struct task_struct *curr = current;
J. R. Okajima41c2c5b2017-02-03 01:38:15 +09004111 struct held_lock *hlock;
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004112 struct lock_class_stats *stats;
4113 unsigned int depth;
Peter Zijlstra3365e7792009-10-09 10:12:41 +02004114 u64 now, waittime = 0;
Peter Zijlstra96645672007-07-19 01:49:00 -07004115 int i, cpu;
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004116
4117 depth = curr->lockdep_depth;
Peter Zijlstra0119fee2011-09-02 01:30:29 +02004118 /*
4119 * Yay, we acquired ownership of this lock we didn't try to
4120 * acquire, how the heck did that happen?
4121 */
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004122 if (DEBUG_LOCKS_WARN_ON(!depth))
4123 return;
4124
J. R. Okajima41c2c5b2017-02-03 01:38:15 +09004125 hlock = find_held_lock(curr, lock, depth, &i);
4126 if (!hlock) {
4127 print_lock_contention_bug(curr, lock, _RET_IP_);
4128 return;
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004129 }
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004130
Peter Zijlstrabb97a912009-07-20 19:15:35 +02004131 if (hlock->instance != lock)
4132 return;
4133
Peter Zijlstra96645672007-07-19 01:49:00 -07004134 cpu = smp_processor_id();
4135 if (hlock->waittime_stamp) {
Peter Zijlstra3365e7792009-10-09 10:12:41 +02004136 now = lockstat_clock();
Peter Zijlstra96645672007-07-19 01:49:00 -07004137 waittime = now - hlock->waittime_stamp;
4138 hlock->holdtime_stamp = now;
4139 }
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004140
Frederic Weisbecker883a2a32010-05-08 06:16:11 +02004141 trace_lock_acquired(lock, ip);
Frederic Weisbecker20625012009-04-06 01:49:33 +02004142
Dave Jonesf82b2172008-08-11 09:30:23 +02004143 stats = get_lock_stats(hlock_class(hlock));
Peter Zijlstra96645672007-07-19 01:49:00 -07004144 if (waittime) {
4145 if (hlock->read)
4146 lock_time_inc(&stats->read_waittime, waittime);
4147 else
4148 lock_time_inc(&stats->write_waittime, waittime);
4149 }
4150 if (lock->cpu != cpu)
4151 stats->bounces[bounce_acquired + !!hlock->read]++;
Peter Zijlstra96645672007-07-19 01:49:00 -07004152
4153 lock->cpu = cpu;
Peter Zijlstrac7e78cf2008-10-16 23:17:09 +02004154 lock->ip = ip;
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004155}
4156
4157void lock_contended(struct lockdep_map *lock, unsigned long ip)
4158{
4159 unsigned long flags;
4160
Waiman Long9506a742018-10-18 21:45:17 -04004161 if (unlikely(!lock_stat || !debug_locks))
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004162 return;
4163
4164 if (unlikely(current->lockdep_recursion))
4165 return;
4166
4167 raw_local_irq_save(flags);
4168 check_flags(flags);
4169 current->lockdep_recursion = 1;
Frederic Weisbeckerdb2c4c72010-02-02 23:34:40 +01004170 trace_lock_contended(lock, ip);
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004171 __lock_contended(lock, ip);
4172 current->lockdep_recursion = 0;
4173 raw_local_irq_restore(flags);
4174}
4175EXPORT_SYMBOL_GPL(lock_contended);
4176
Peter Zijlstrac7e78cf2008-10-16 23:17:09 +02004177void lock_acquired(struct lockdep_map *lock, unsigned long ip)
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004178{
4179 unsigned long flags;
4180
Waiman Long9506a742018-10-18 21:45:17 -04004181 if (unlikely(!lock_stat || !debug_locks))
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004182 return;
4183
4184 if (unlikely(current->lockdep_recursion))
4185 return;
4186
4187 raw_local_irq_save(flags);
4188 check_flags(flags);
4189 current->lockdep_recursion = 1;
Peter Zijlstrac7e78cf2008-10-16 23:17:09 +02004190 __lock_acquired(lock, ip);
Peter Zijlstraf20786f2007-07-19 01:48:56 -07004191 current->lockdep_recursion = 0;
4192 raw_local_irq_restore(flags);
4193}
4194EXPORT_SYMBOL_GPL(lock_acquired);
4195#endif
4196
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004197/*
4198 * Used by the testsuite, sanitize the validator state
4199 * after a simulated failure:
4200 */
4201
4202void lockdep_reset(void)
4203{
4204 unsigned long flags;
Ingo Molnar23d95a02006-12-13 00:34:40 -08004205 int i;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004206
4207 raw_local_irq_save(flags);
4208 current->curr_chain_key = 0;
4209 current->lockdep_depth = 0;
4210 current->lockdep_recursion = 0;
4211 memset(current->held_locks, 0, MAX_LOCK_DEPTH*sizeof(struct held_lock));
4212 nr_hardirq_chains = 0;
4213 nr_softirq_chains = 0;
4214 nr_process_chains = 0;
4215 debug_locks = 1;
Ingo Molnar23d95a02006-12-13 00:34:40 -08004216 for (i = 0; i < CHAINHASH_SIZE; i++)
Andrew Mortona63f38c2016-02-03 13:44:12 -08004217 INIT_HLIST_HEAD(chainhash_table + i);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004218 raw_local_irq_restore(flags);
4219}
4220
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004221/* Remove a class from a lock chain. Must be called with the graph lock held. */
Bart Van Asschede4643a2019-02-14 15:00:50 -08004222static void remove_class_from_lock_chain(struct pending_free *pf,
4223 struct lock_chain *chain,
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004224 struct lock_class *class)
4225{
4226#ifdef CONFIG_PROVE_LOCKING
4227 struct lock_chain *new_chain;
4228 u64 chain_key;
4229 int i;
4230
4231 for (i = chain->base; i < chain->base + chain->depth; i++) {
4232 if (chain_hlocks[i] != class - lock_classes)
4233 continue;
4234 /* The code below leaks one chain_hlock[] entry. */
4235 if (--chain->depth > 0)
4236 memmove(&chain_hlocks[i], &chain_hlocks[i + 1],
4237 (chain->base + chain->depth - i) *
4238 sizeof(chain_hlocks[0]));
4239 /*
4240 * Each lock class occurs at most once in a lock chain so once
4241 * we found a match we can break out of this loop.
4242 */
4243 goto recalc;
4244 }
4245 /* Since the chain has not been modified, return. */
4246 return;
4247
4248recalc:
4249 chain_key = 0;
4250 for (i = chain->base; i < chain->base + chain->depth; i++)
4251 chain_key = iterate_chain_key(chain_key, chain_hlocks[i] + 1);
4252 if (chain->depth && chain->chain_key == chain_key)
4253 return;
4254 /* Overwrite the chain key for concurrent RCU readers. */
4255 WRITE_ONCE(chain->chain_key, chain_key);
4256 /*
4257 * Note: calling hlist_del_rcu() from inside a
4258 * hlist_for_each_entry_rcu() loop is safe.
4259 */
4260 hlist_del_rcu(&chain->entry);
Bart Van Asschede4643a2019-02-14 15:00:50 -08004261 __set_bit(chain - lock_chains, pf->lock_chains_being_freed);
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004262 if (chain->depth == 0)
4263 return;
4264 /*
4265 * If the modified lock chain matches an existing lock chain, drop
4266 * the modified lock chain.
4267 */
4268 if (lookup_chain_cache(chain_key))
4269 return;
Bart Van Asschede4643a2019-02-14 15:00:50 -08004270 new_chain = alloc_lock_chain();
4271 if (WARN_ON_ONCE(!new_chain)) {
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004272 debug_locks_off();
4273 return;
4274 }
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004275 *new_chain = *chain;
4276 hlist_add_head_rcu(&new_chain->entry, chainhashentry(chain_key));
4277#endif
4278}
4279
4280/* Must be called with the graph lock held. */
Bart Van Asschede4643a2019-02-14 15:00:50 -08004281static void remove_class_from_lock_chains(struct pending_free *pf,
4282 struct lock_class *class)
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004283{
4284 struct lock_chain *chain;
4285 struct hlist_head *head;
4286 int i;
4287
4288 for (i = 0; i < ARRAY_SIZE(chainhash_table); i++) {
4289 head = chainhash_table + i;
4290 hlist_for_each_entry_rcu(chain, head, entry) {
Bart Van Asschede4643a2019-02-14 15:00:50 -08004291 remove_class_from_lock_chain(pf, chain, class);
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004292 }
4293 }
4294}
4295
Bart Van Assche786fa292018-12-06 17:11:36 -08004296/*
4297 * Remove all references to a lock class. The caller must hold the graph lock.
4298 */
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004299static void zap_class(struct pending_free *pf, struct lock_class *class)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004300{
Bart Van Assche86cffb82019-02-14 15:00:41 -08004301 struct lock_list *entry;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004302 int i;
4303
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004304 WARN_ON_ONCE(!class->key);
4305
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004306 /*
4307 * Remove all dependencies this lock is
4308 * involved in:
4309 */
Bart Van Asscheace35a72019-02-14 15:00:47 -08004310 for_each_set_bit(i, list_entries_in_use, ARRAY_SIZE(list_entries)) {
4311 entry = list_entries + i;
Bart Van Assche86cffb82019-02-14 15:00:41 -08004312 if (entry->class != class && entry->links_to != class)
4313 continue;
Bart Van Asscheace35a72019-02-14 15:00:47 -08004314 __clear_bit(i, list_entries_in_use);
4315 nr_list_entries--;
Bart Van Assche86cffb82019-02-14 15:00:41 -08004316 list_del_rcu(&entry->entry);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004317 }
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004318 if (list_empty(&class->locks_after) &&
4319 list_empty(&class->locks_before)) {
4320 list_move_tail(&class->lock_entry, &pf->zapped);
4321 hlist_del_rcu(&class->hash_entry);
4322 WRITE_ONCE(class->key, NULL);
4323 WRITE_ONCE(class->name, NULL);
4324 nr_lock_classes--;
4325 } else {
4326 WARN_ONCE(true, "%s() failed for class %s\n", __func__,
4327 class->name);
4328 }
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004329
Bart Van Asschede4643a2019-02-14 15:00:50 -08004330 remove_class_from_lock_chains(pf, class);
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004331}
4332
4333static void reinit_class(struct lock_class *class)
4334{
4335 void *const p = class;
4336 const unsigned int offset = offsetof(struct lock_class, key);
4337
4338 WARN_ON_ONCE(!class->lock_entry.next);
4339 WARN_ON_ONCE(!list_empty(&class->locks_after));
4340 WARN_ON_ONCE(!list_empty(&class->locks_before));
4341 memset(p + offset, 0, sizeof(*class) - offset);
4342 WARN_ON_ONCE(!class->lock_entry.next);
4343 WARN_ON_ONCE(!list_empty(&class->locks_after));
4344 WARN_ON_ONCE(!list_empty(&class->locks_before));
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004345}
4346
Arjan van de Venfabe8742008-01-24 07:00:45 +01004347static inline int within(const void *addr, void *start, unsigned long size)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004348{
4349 return addr >= start && addr < start + size;
4350}
4351
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004352static bool inside_selftest(void)
4353{
4354 return current == lockdep_selftest_task_struct;
4355}
4356
4357/* The caller must hold the graph lock. */
4358static struct pending_free *get_pending_free(void)
4359{
4360 return delayed_free.pf + delayed_free.index;
4361}
4362
4363static void free_zapped_rcu(struct rcu_head *cb);
4364
4365/*
4366 * Schedule an RCU callback if no RCU callback is pending. Must be called with
4367 * the graph lock held.
4368 */
4369static void call_rcu_zapped(struct pending_free *pf)
4370{
4371 WARN_ON_ONCE(inside_selftest());
4372
4373 if (list_empty(&pf->zapped))
4374 return;
4375
4376 if (delayed_free.scheduled)
4377 return;
4378
4379 delayed_free.scheduled = true;
4380
4381 WARN_ON_ONCE(delayed_free.pf + delayed_free.index != pf);
4382 delayed_free.index ^= 1;
4383
4384 call_rcu(&delayed_free.rcu_head, free_zapped_rcu);
4385}
4386
4387/* The caller must hold the graph lock. May be called from RCU context. */
4388static void __free_zapped_classes(struct pending_free *pf)
4389{
4390 struct lock_class *class;
4391
4392 list_for_each_entry(class, &pf->zapped, lock_entry)
4393 reinit_class(class);
4394
4395 list_splice_init(&pf->zapped, &free_lock_classes);
Bart Van Asschede4643a2019-02-14 15:00:50 -08004396
4397#ifdef CONFIG_PROVE_LOCKING
4398 bitmap_andnot(lock_chains_in_use, lock_chains_in_use,
4399 pf->lock_chains_being_freed, ARRAY_SIZE(lock_chains));
4400 bitmap_clear(pf->lock_chains_being_freed, 0, ARRAY_SIZE(lock_chains));
4401#endif
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004402}
4403
4404static void free_zapped_rcu(struct rcu_head *ch)
4405{
4406 struct pending_free *pf;
4407 unsigned long flags;
4408
4409 if (WARN_ON_ONCE(ch != &delayed_free.rcu_head))
4410 return;
4411
4412 raw_local_irq_save(flags);
4413 if (!graph_lock())
4414 goto out_irq;
4415
4416 /* closed head */
4417 pf = delayed_free.pf + (delayed_free.index ^ 1);
4418 __free_zapped_classes(pf);
4419 delayed_free.scheduled = false;
4420
4421 /*
4422 * If there's anything on the open list, close and start a new callback.
4423 */
4424 call_rcu_zapped(delayed_free.pf + delayed_free.index);
4425
4426 graph_unlock();
4427out_irq:
4428 raw_local_irq_restore(flags);
4429}
4430
4431/*
4432 * Remove all lock classes from the class hash table and from the
4433 * all_lock_classes list whose key or name is in the address range [start,
4434 * start + size). Move these lock classes to the zapped_classes list. Must
4435 * be called with the graph lock held.
4436 */
4437static void __lockdep_free_key_range(struct pending_free *pf, void *start,
4438 unsigned long size)
Bart Van Assche956f3562019-02-14 15:00:43 -08004439{
4440 struct lock_class *class;
4441 struct hlist_head *head;
4442 int i;
4443
4444 /* Unhash all classes that were created by a module. */
4445 for (i = 0; i < CLASSHASH_SIZE; i++) {
4446 head = classhash_table + i;
4447 hlist_for_each_entry_rcu(class, head, hash_entry) {
4448 if (!within(class->key, start, size) &&
4449 !within(class->name, start, size))
4450 continue;
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004451 zap_class(pf, class);
Bart Van Assche956f3562019-02-14 15:00:43 -08004452 }
4453 }
4454}
4455
Peter Zijlstra35a93932015-02-26 16:23:11 +01004456/*
4457 * Used in module.c to remove lock classes from memory that is going to be
4458 * freed; and possibly re-used by other modules.
4459 *
Bart Van Assche29fc33f2019-02-14 15:00:45 -08004460 * We will have had one synchronize_rcu() before getting here, so we're
4461 * guaranteed nobody will look up these exact classes -- they're properly dead
4462 * but still allocated.
Peter Zijlstra35a93932015-02-26 16:23:11 +01004463 */
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004464static void lockdep_free_key_range_reg(void *start, unsigned long size)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004465{
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004466 struct pending_free *pf;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004467 unsigned long flags;
Nick Piggin5a26db52008-01-16 09:51:58 +01004468 int locked;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004469
Bart Van Asschefeb0a382019-02-14 15:00:42 -08004470 init_data_structures_once();
4471
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004472 raw_local_irq_save(flags);
Nick Piggin5a26db52008-01-16 09:51:58 +01004473 locked = graph_lock();
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004474 if (!locked)
4475 goto out_irq;
4476
4477 pf = get_pending_free();
4478 __lockdep_free_key_range(pf, start, size);
4479 call_rcu_zapped(pf);
4480
4481 graph_unlock();
4482out_irq:
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004483 raw_local_irq_restore(flags);
Peter Zijlstra35a93932015-02-26 16:23:11 +01004484
4485 /*
4486 * Wait for any possible iterators from look_up_lock_class() to pass
4487 * before continuing to free the memory they refer to.
Peter Zijlstra35a93932015-02-26 16:23:11 +01004488 */
Paul E. McKenney51959d82018-11-06 19:06:51 -08004489 synchronize_rcu();
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004490}
Peter Zijlstra35a93932015-02-26 16:23:11 +01004491
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004492/*
4493 * Free all lockdep keys in the range [start, start+size). Does not sleep.
4494 * Ignores debug_locks. Must only be used by the lockdep selftests.
4495 */
4496static void lockdep_free_key_range_imm(void *start, unsigned long size)
4497{
4498 struct pending_free *pf = delayed_free.pf;
4499 unsigned long flags;
4500
4501 init_data_structures_once();
4502
4503 raw_local_irq_save(flags);
4504 arch_spin_lock(&lockdep_lock);
4505 __lockdep_free_key_range(pf, start, size);
4506 __free_zapped_classes(pf);
4507 arch_spin_unlock(&lockdep_lock);
4508 raw_local_irq_restore(flags);
4509}
4510
4511void lockdep_free_key_range(void *start, unsigned long size)
4512{
4513 init_data_structures_once();
4514
4515 if (inside_selftest())
4516 lockdep_free_key_range_imm(start, size);
4517 else
4518 lockdep_free_key_range_reg(start, size);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004519}
4520
Bart Van Assche2904d9f2018-12-06 17:11:34 -08004521/*
4522 * Check whether any element of the @lock->class_cache[] array refers to a
4523 * registered lock class. The caller must hold either the graph lock or the
4524 * RCU read lock.
4525 */
4526static bool lock_class_cache_is_registered(struct lockdep_map *lock)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004527{
Peter Zijlstra35a93932015-02-26 16:23:11 +01004528 struct lock_class *class;
Andrew Mortona63f38c2016-02-03 13:44:12 -08004529 struct hlist_head *head;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004530 int i, j;
Bart Van Assche2904d9f2018-12-06 17:11:34 -08004531
4532 for (i = 0; i < CLASSHASH_SIZE; i++) {
4533 head = classhash_table + i;
4534 hlist_for_each_entry_rcu(class, head, hash_entry) {
4535 for (j = 0; j < NR_LOCKDEP_CACHING_CLASSES; j++)
4536 if (lock->class_cache[j] == class)
4537 return true;
4538 }
4539 }
4540 return false;
4541}
4542
Bart Van Assche956f3562019-02-14 15:00:43 -08004543/* The caller must hold the graph lock. Does not sleep. */
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004544static void __lockdep_reset_lock(struct pending_free *pf,
4545 struct lockdep_map *lock)
Bart Van Assche2904d9f2018-12-06 17:11:34 -08004546{
4547 struct lock_class *class;
Bart Van Assche956f3562019-02-14 15:00:43 -08004548 int j;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004549
4550 /*
Ingo Molnard6d897c2006-07-10 04:44:04 -07004551 * Remove all classes this lock might have:
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004552 */
Ingo Molnard6d897c2006-07-10 04:44:04 -07004553 for (j = 0; j < MAX_LOCKDEP_SUBCLASSES; j++) {
4554 /*
4555 * If the class exists we look it up and zap it:
4556 */
4557 class = look_up_lock_class(lock, j);
Matthew Wilcox64f29d12018-01-17 07:14:12 -08004558 if (class)
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004559 zap_class(pf, class);
Ingo Molnard6d897c2006-07-10 04:44:04 -07004560 }
4561 /*
4562 * Debug check: in the end all mapped classes should
4563 * be gone.
4564 */
Bart Van Assche956f3562019-02-14 15:00:43 -08004565 if (WARN_ON_ONCE(lock_class_cache_is_registered(lock)))
4566 debug_locks_off();
4567}
4568
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004569/*
4570 * Remove all information lockdep has about a lock if debug_locks == 1. Free
4571 * released data structures from RCU context.
4572 */
4573static void lockdep_reset_lock_reg(struct lockdep_map *lock)
Bart Van Assche956f3562019-02-14 15:00:43 -08004574{
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004575 struct pending_free *pf;
Bart Van Assche956f3562019-02-14 15:00:43 -08004576 unsigned long flags;
4577 int locked;
4578
Bart Van Assche956f3562019-02-14 15:00:43 -08004579 raw_local_irq_save(flags);
4580 locked = graph_lock();
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004581 if (!locked)
4582 goto out_irq;
4583
4584 pf = get_pending_free();
4585 __lockdep_reset_lock(pf, lock);
4586 call_rcu_zapped(pf);
4587
4588 graph_unlock();
4589out_irq:
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004590 raw_local_irq_restore(flags);
4591}
4592
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004593/*
4594 * Reset a lock. Does not sleep. Ignores debug_locks. Must only be used by the
4595 * lockdep selftests.
4596 */
4597static void lockdep_reset_lock_imm(struct lockdep_map *lock)
4598{
4599 struct pending_free *pf = delayed_free.pf;
4600 unsigned long flags;
4601
4602 raw_local_irq_save(flags);
4603 arch_spin_lock(&lockdep_lock);
4604 __lockdep_reset_lock(pf, lock);
4605 __free_zapped_classes(pf);
4606 arch_spin_unlock(&lockdep_lock);
4607 raw_local_irq_restore(flags);
4608}
4609
4610void lockdep_reset_lock(struct lockdep_map *lock)
4611{
4612 init_data_structures_once();
4613
4614 if (inside_selftest())
4615 lockdep_reset_lock_imm(lock);
4616 else
4617 lockdep_reset_lock_reg(lock);
4618}
4619
Joel Fernandes (Google)c3bc8fd2018-07-30 15:24:23 -07004620void __init lockdep_init(void)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004621{
4622 printk("Lock dependency validator: Copyright (c) 2006 Red Hat, Inc., Ingo Molnar\n");
4623
Li Zefanb0788ca2008-11-21 15:57:32 +08004624 printk("... MAX_LOCKDEP_SUBCLASSES: %lu\n", MAX_LOCKDEP_SUBCLASSES);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004625 printk("... MAX_LOCK_DEPTH: %lu\n", MAX_LOCK_DEPTH);
4626 printk("... MAX_LOCKDEP_KEYS: %lu\n", MAX_LOCKDEP_KEYS);
Li Zefanb0788ca2008-11-21 15:57:32 +08004627 printk("... CLASSHASH_SIZE: %lu\n", CLASSHASH_SIZE);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004628 printk("... MAX_LOCKDEP_ENTRIES: %lu\n", MAX_LOCKDEP_ENTRIES);
4629 printk("... MAX_LOCKDEP_CHAINS: %lu\n", MAX_LOCKDEP_CHAINS);
4630 printk("... CHAINHASH_SIZE: %lu\n", CHAINHASH_SIZE);
4631
Bart Van Assche09d75ec2019-02-14 15:00:36 -08004632 printk(" memory used by lock dependency info: %zu kB\n",
Bart Van Assche7ff85172019-02-14 15:00:37 -08004633 (sizeof(lock_classes) +
4634 sizeof(classhash_table) +
4635 sizeof(list_entries) +
Bart Van Asscheace35a72019-02-14 15:00:47 -08004636 sizeof(list_entries_in_use) +
Bart Van Asschea0b0fd52019-02-14 15:00:46 -08004637 sizeof(chainhash_table) +
4638 sizeof(delayed_free)
Ming Lei4dd861d2009-07-16 15:44:29 +02004639#ifdef CONFIG_PROVE_LOCKING
Bart Van Assche7ff85172019-02-14 15:00:37 -08004640 + sizeof(lock_cq)
Bart Van Assche15ea86b2019-02-14 15:00:38 -08004641 + sizeof(lock_chains)
Bart Van Asschede4643a2019-02-14 15:00:50 -08004642 + sizeof(lock_chains_in_use)
Bart Van Assche15ea86b2019-02-14 15:00:38 -08004643 + sizeof(chain_hlocks)
Ming Lei4dd861d2009-07-16 15:44:29 +02004644#endif
Ming Lei906292092009-08-02 21:43:36 +08004645 ) / 1024
Ming Lei4dd861d2009-07-16 15:44:29 +02004646 );
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004647
Bart Van Assche09d75ec2019-02-14 15:00:36 -08004648 printk(" per task-struct memory footprint: %zu bytes\n",
Bart Van Assche7ff85172019-02-14 15:00:37 -08004649 sizeof(((struct task_struct *)NULL)->held_locks));
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004650}
4651
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004652static void
4653print_freed_lock_bug(struct task_struct *curr, const void *mem_from,
Arjan van de Ven55794a42006-07-10 04:44:03 -07004654 const void *mem_to, struct held_lock *hlock)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004655{
4656 if (!debug_locks_off())
4657 return;
4658 if (debug_locks_silent)
4659 return;
4660
Paul E. McKenney681fbec2017-05-04 15:44:38 -07004661 pr_warn("\n");
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08004662 pr_warn("=========================\n");
4663 pr_warn("WARNING: held lock freed!\n");
Ben Hutchingsfbdc4b92011-10-28 04:36:55 +01004664 print_kernel_ident();
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08004665 pr_warn("-------------------------\n");
Borislav Petkov04860d42018-02-26 14:49:26 +01004666 pr_warn("%s/%d is freeing memory %px-%px, with a lock still held there!\n",
Pavel Emelyanovba25f9d2007-10-18 23:40:40 -07004667 curr->comm, task_pid_nr(curr), mem_from, mem_to-1);
Arjan van de Ven55794a42006-07-10 04:44:03 -07004668 print_lock(hlock);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004669 lockdep_print_held_locks(curr);
4670
Paul E. McKenney681fbec2017-05-04 15:44:38 -07004671 pr_warn("\nstack backtrace:\n");
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004672 dump_stack();
4673}
4674
Oleg Nesterov54561782007-12-05 15:46:09 +01004675static inline int not_in_range(const void* mem_from, unsigned long mem_len,
4676 const void* lock_from, unsigned long lock_len)
4677{
4678 return lock_from + lock_len <= mem_from ||
4679 mem_from + mem_len <= lock_from;
4680}
4681
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004682/*
4683 * Called when kernel memory is freed (or unmapped), or if a lock
4684 * is destroyed or reinitialized - this code checks whether there is
4685 * any held lock in the memory range of <from> to <to>:
4686 */
4687void debug_check_no_locks_freed(const void *mem_from, unsigned long mem_len)
4688{
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004689 struct task_struct *curr = current;
4690 struct held_lock *hlock;
4691 unsigned long flags;
4692 int i;
4693
4694 if (unlikely(!debug_locks))
4695 return;
4696
Steven Rostedt (VMware)fcc784b2018-04-04 14:06:30 -04004697 raw_local_irq_save(flags);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004698 for (i = 0; i < curr->lockdep_depth; i++) {
4699 hlock = curr->held_locks + i;
4700
Oleg Nesterov54561782007-12-05 15:46:09 +01004701 if (not_in_range(mem_from, mem_len, hlock->instance,
4702 sizeof(*hlock->instance)))
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004703 continue;
4704
Oleg Nesterov54561782007-12-05 15:46:09 +01004705 print_freed_lock_bug(curr, mem_from, mem_from + mem_len, hlock);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004706 break;
4707 }
Steven Rostedt (VMware)fcc784b2018-04-04 14:06:30 -04004708 raw_local_irq_restore(flags);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004709}
Peter Zijlstraed075362006-12-06 20:35:24 -08004710EXPORT_SYMBOL_GPL(debug_check_no_locks_freed);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004711
Colin Cross1b1d2fb2013-05-06 23:50:08 +00004712static void print_held_locks_bug(void)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004713{
4714 if (!debug_locks_off())
4715 return;
4716 if (debug_locks_silent)
4717 return;
4718
Paul E. McKenney681fbec2017-05-04 15:44:38 -07004719 pr_warn("\n");
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08004720 pr_warn("====================================\n");
4721 pr_warn("WARNING: %s/%d still has locks held!\n",
Colin Cross1b1d2fb2013-05-06 23:50:08 +00004722 current->comm, task_pid_nr(current));
Ben Hutchingsfbdc4b92011-10-28 04:36:55 +01004723 print_kernel_ident();
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08004724 pr_warn("------------------------------------\n");
Colin Cross1b1d2fb2013-05-06 23:50:08 +00004725 lockdep_print_held_locks(current);
Paul E. McKenney681fbec2017-05-04 15:44:38 -07004726 pr_warn("\nstack backtrace:\n");
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004727 dump_stack();
4728}
4729
Colin Cross1b1d2fb2013-05-06 23:50:08 +00004730void debug_check_no_locks_held(void)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004731{
Colin Cross1b1d2fb2013-05-06 23:50:08 +00004732 if (unlikely(current->lockdep_depth > 0))
4733 print_held_locks_bug();
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004734}
Colin Cross1b1d2fb2013-05-06 23:50:08 +00004735EXPORT_SYMBOL_GPL(debug_check_no_locks_held);
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004736
Sasha Levin8dce7a92013-06-13 18:41:16 -04004737#ifdef __KERNEL__
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004738void debug_show_all_locks(void)
4739{
4740 struct task_struct *g, *p;
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004741
Jarek Poplawski9c35dd72007-03-22 00:11:28 -08004742 if (unlikely(!debug_locks)) {
Paul E. McKenney681fbec2017-05-04 15:44:38 -07004743 pr_warn("INFO: lockdep is turned off.\n");
Jarek Poplawski9c35dd72007-03-22 00:11:28 -08004744 return;
4745 }
Paul E. McKenney681fbec2017-05-04 15:44:38 -07004746 pr_warn("\nShowing all locks held in the system:\n");
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004747
Tetsuo Handa0f736a52018-04-06 19:41:18 +09004748 rcu_read_lock();
4749 for_each_process_thread(g, p) {
Tetsuo Handa0f736a52018-04-06 19:41:18 +09004750 if (!p->lockdep_depth)
4751 continue;
4752 lockdep_print_held_locks(p);
Tejun Heo88f1c872018-01-22 14:00:55 -08004753 touch_nmi_watchdog();
Tetsuo Handa0f736a52018-04-06 19:41:18 +09004754 touch_all_softlockup_watchdogs();
4755 }
4756 rcu_read_unlock();
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004757
Paul E. McKenney681fbec2017-05-04 15:44:38 -07004758 pr_warn("\n");
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08004759 pr_warn("=============================================\n\n");
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004760}
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004761EXPORT_SYMBOL_GPL(debug_show_all_locks);
Sasha Levin8dce7a92013-06-13 18:41:16 -04004762#endif
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004763
Ingo Molnar82a1fcb2008-01-25 21:08:02 +01004764/*
4765 * Careful: only use this function if you are sure that
4766 * the task cannot run in parallel!
4767 */
John Kacurf1b499f2010-08-05 17:10:53 +02004768void debug_show_held_locks(struct task_struct *task)
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004769{
Jarek Poplawski9c35dd72007-03-22 00:11:28 -08004770 if (unlikely(!debug_locks)) {
4771 printk("INFO: lockdep is turned off.\n");
4772 return;
4773 }
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004774 lockdep_print_held_locks(task);
4775}
Ingo Molnarfbb9ce952006-07-03 00:24:50 -07004776EXPORT_SYMBOL_GPL(debug_show_held_locks);
Peter Zijlstrab351d162007-10-11 22:11:12 +02004777
Andi Kleen722a9f92014-05-02 00:44:38 +02004778asmlinkage __visible void lockdep_sys_exit(void)
Peter Zijlstrab351d162007-10-11 22:11:12 +02004779{
4780 struct task_struct *curr = current;
4781
4782 if (unlikely(curr->lockdep_depth)) {
4783 if (!debug_locks_off())
4784 return;
Paul E. McKenney681fbec2017-05-04 15:44:38 -07004785 pr_warn("\n");
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08004786 pr_warn("================================================\n");
4787 pr_warn("WARNING: lock held when returning to user space!\n");
Ben Hutchingsfbdc4b92011-10-28 04:36:55 +01004788 print_kernel_ident();
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08004789 pr_warn("------------------------------------------------\n");
Paul E. McKenney681fbec2017-05-04 15:44:38 -07004790 pr_warn("%s/%d is leaving the kernel with locks still held!\n",
Peter Zijlstrab351d162007-10-11 22:11:12 +02004791 curr->comm, curr->pid);
4792 lockdep_print_held_locks(curr);
4793 }
Byungchul Parkb09be672017-08-07 16:12:52 +09004794
4795 /*
4796 * The lock history for each syscall should be independent. So wipe the
4797 * slate clean on return to userspace.
4798 */
Peter Zijlstraf52be572017-08-29 10:59:39 +02004799 lockdep_invariant_state(false);
Peter Zijlstrab351d162007-10-11 22:11:12 +02004800}
Paul E. McKenney0632eb32010-02-22 17:04:47 -08004801
Paul E. McKenneyb3fbab02011-05-24 08:31:09 -07004802void lockdep_rcu_suspicious(const char *file, const int line, const char *s)
Paul E. McKenney0632eb32010-02-22 17:04:47 -08004803{
4804 struct task_struct *curr = current;
4805
Lai Jiangshan2b3fc352010-04-20 16:23:07 +08004806 /* Note: the following can be executed concurrently, so be careful. */
Paul E. McKenney681fbec2017-05-04 15:44:38 -07004807 pr_warn("\n");
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08004808 pr_warn("=============================\n");
4809 pr_warn("WARNING: suspicious RCU usage\n");
Ben Hutchingsfbdc4b92011-10-28 04:36:55 +01004810 print_kernel_ident();
Paul E. McKenneya5dd63e2017-01-31 07:45:13 -08004811 pr_warn("-----------------------------\n");
Paul E. McKenney681fbec2017-05-04 15:44:38 -07004812 pr_warn("%s:%d %s!\n", file, line, s);
4813 pr_warn("\nother info that might help us debug this:\n\n");
4814 pr_warn("\n%srcu_scheduler_active = %d, debug_locks = %d\n",
Paul E. McKenneyc5fdcec2012-01-30 08:46:32 -08004815 !rcu_lockdep_current_cpu_online()
4816 ? "RCU used illegally from offline CPU!\n"
Paul E. McKenney5c173eb2013-09-13 17:20:11 -07004817 : !rcu_is_watching()
Paul E. McKenneyc5fdcec2012-01-30 08:46:32 -08004818 ? "RCU used illegally from idle CPU!\n"
4819 : "",
4820 rcu_scheduler_active, debug_locks);
Frederic Weisbecker0464e932011-10-07 18:22:01 +02004821
4822 /*
4823 * If a CPU is in the RCU-free window in idle (ie: in the section
4824 * between rcu_idle_enter() and rcu_idle_exit(), then RCU
4825 * considers that CPU to be in an "extended quiescent state",
4826 * which means that RCU will be completely ignoring that CPU.
4827 * Therefore, rcu_read_lock() and friends have absolutely no
4828 * effect on a CPU running in that state. In other words, even if
4829 * such an RCU-idle CPU has called rcu_read_lock(), RCU might well
4830 * delete data structures out from under it. RCU really has no
4831 * choice here: we need to keep an RCU-free window in idle where
4832 * the CPU may possibly enter into low power mode. This way we can
4833 * notice an extended quiescent state to other CPUs that started a grace
4834 * period. Otherwise we would delay any grace period as long as we run
4835 * in the idle task.
4836 *
4837 * So complain bitterly if someone does call rcu_read_lock(),
4838 * rcu_read_lock_bh() and so on from extended quiescent states.
4839 */
Paul E. McKenney5c173eb2013-09-13 17:20:11 -07004840 if (!rcu_is_watching())
Paul E. McKenney681fbec2017-05-04 15:44:38 -07004841 pr_warn("RCU used illegally from extended quiescent state!\n");
Frederic Weisbecker0464e932011-10-07 18:22:01 +02004842
Paul E. McKenney0632eb32010-02-22 17:04:47 -08004843 lockdep_print_held_locks(curr);
Paul E. McKenney681fbec2017-05-04 15:44:38 -07004844 pr_warn("\nstack backtrace:\n");
Paul E. McKenney0632eb32010-02-22 17:04:47 -08004845 dump_stack();
4846}
Paul E. McKenneyb3fbab02011-05-24 08:31:09 -07004847EXPORT_SYMBOL_GPL(lockdep_rcu_suspicious);