cachepc-linux

Fork of AMDESE/linux with modifications for CachePC side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-linux
Log | Files | Refs | README | LICENSE | sfeed.txt

lockdep.c (172072B)


      1// SPDX-License-Identifier: GPL-2.0-only
      2/*
      3 * kernel/lockdep.c
      4 *
      5 * Runtime locking correctness validator
      6 *
      7 * Started by Ingo Molnar:
      8 *
      9 *  Copyright (C) 2006,2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
     10 *  Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra
     11 *
     12 * this code maps all the lock dependencies as they occur in a live kernel
     13 * and will warn about the following classes of locking bugs:
     14 *
     15 * - lock inversion scenarios
     16 * - circular lock dependencies
     17 * - hardirq/softirq safe/unsafe locking bugs
     18 *
     19 * Bugs are reported even if the current locking scenario does not cause
     20 * any deadlock at this point.
     21 *
     22 * I.e. if anytime in the past two locks were taken in a different order,
     23 * even if it happened for another task, even if those were different
     24 * locks (but of the same class as this lock), this code will detect it.
     25 *
     26 * Thanks to Arjan van de Ven for coming up with the initial idea of
     27 * mapping lock dependencies runtime.
     28 */
     29#define DISABLE_BRANCH_PROFILING
     30#include <linux/mutex.h>
     31#include <linux/sched.h>
     32#include <linux/sched/clock.h>
     33#include <linux/sched/task.h>
     34#include <linux/sched/mm.h>
     35#include <linux/delay.h>
     36#include <linux/module.h>
     37#include <linux/proc_fs.h>
     38#include <linux/seq_file.h>
     39#include <linux/spinlock.h>
     40#include <linux/kallsyms.h>
     41#include <linux/interrupt.h>
     42#include <linux/stacktrace.h>
     43#include <linux/debug_locks.h>
     44#include <linux/irqflags.h>
     45#include <linux/utsname.h>
     46#include <linux/hash.h>
     47#include <linux/ftrace.h>
     48#include <linux/stringify.h>
     49#include <linux/bitmap.h>
     50#include <linux/bitops.h>
     51#include <linux/gfp.h>
     52#include <linux/random.h>
     53#include <linux/jhash.h>
     54#include <linux/nmi.h>
     55#include <linux/rcupdate.h>
     56#include <linux/kprobes.h>
     57#include <linux/lockdep.h>
     58
     59#include <asm/sections.h>
     60
     61#include "lockdep_internals.h"
     62
     63#include <trace/events/lock.h>
     64
     65#ifdef CONFIG_PROVE_LOCKING
     66static int prove_locking = 1;
     67module_param(prove_locking, int, 0644);
     68#else
     69#define prove_locking 0
     70#endif
     71
     72#ifdef CONFIG_LOCK_STAT
     73static int lock_stat = 1;
     74module_param(lock_stat, int, 0644);
     75#else
     76#define lock_stat 0
     77#endif
     78
     79#ifdef CONFIG_SYSCTL
     80static struct ctl_table kern_lockdep_table[] = {
     81#ifdef CONFIG_PROVE_LOCKING
     82	{
     83		.procname       = "prove_locking",
     84		.data           = &prove_locking,
     85		.maxlen         = sizeof(int),
     86		.mode           = 0644,
     87		.proc_handler   = proc_dointvec,
     88	},
     89#endif /* CONFIG_PROVE_LOCKING */
     90#ifdef CONFIG_LOCK_STAT
     91	{
     92		.procname       = "lock_stat",
     93		.data           = &lock_stat,
     94		.maxlen         = sizeof(int),
     95		.mode           = 0644,
     96		.proc_handler   = proc_dointvec,
     97	},
     98#endif /* CONFIG_LOCK_STAT */
     99	{ }
    100};
    101
    102static __init int kernel_lockdep_sysctls_init(void)
    103{
    104	register_sysctl_init("kernel", kern_lockdep_table);
    105	return 0;
    106}
    107late_initcall(kernel_lockdep_sysctls_init);
    108#endif /* CONFIG_SYSCTL */
    109
    110DEFINE_PER_CPU(unsigned int, lockdep_recursion);
    111EXPORT_PER_CPU_SYMBOL_GPL(lockdep_recursion);
    112
    113static __always_inline bool lockdep_enabled(void)
    114{
    115	if (!debug_locks)
    116		return false;
    117
    118	if (this_cpu_read(lockdep_recursion))
    119		return false;
    120
    121	if (current->lockdep_recursion)
    122		return false;
    123
    124	return true;
    125}
    126
    127/*
    128 * lockdep_lock: protects the lockdep graph, the hashes and the
    129 *               class/list/hash allocators.
    130 *
    131 * This is one of the rare exceptions where it's justified
    132 * to use a raw spinlock - we really dont want the spinlock
    133 * code to recurse back into the lockdep code...
    134 */
    135static arch_spinlock_t __lock = (arch_spinlock_t)__ARCH_SPIN_LOCK_UNLOCKED;
    136static struct task_struct *__owner;
    137
    138static inline void lockdep_lock(void)
    139{
    140	DEBUG_LOCKS_WARN_ON(!irqs_disabled());
    141
    142	__this_cpu_inc(lockdep_recursion);
    143	arch_spin_lock(&__lock);
    144	__owner = current;
    145}
    146
    147static inline void lockdep_unlock(void)
    148{
    149	DEBUG_LOCKS_WARN_ON(!irqs_disabled());
    150
    151	if (debug_locks && DEBUG_LOCKS_WARN_ON(__owner != current))
    152		return;
    153
    154	__owner = NULL;
    155	arch_spin_unlock(&__lock);
    156	__this_cpu_dec(lockdep_recursion);
    157}
    158
    159static inline bool lockdep_assert_locked(void)
    160{
    161	return DEBUG_LOCKS_WARN_ON(__owner != current);
    162}
    163
    164static struct task_struct *lockdep_selftest_task_struct;
    165
    166
    167static int graph_lock(void)
    168{
    169	lockdep_lock();
    170	/*
    171	 * Make sure that if another CPU detected a bug while
    172	 * walking the graph we dont change it (while the other
    173	 * CPU is busy printing out stuff with the graph lock
    174	 * dropped already)
    175	 */
    176	if (!debug_locks) {
    177		lockdep_unlock();
    178		return 0;
    179	}
    180	return 1;
    181}
    182
    183static inline void graph_unlock(void)
    184{
    185	lockdep_unlock();
    186}
    187
    188/*
    189 * Turn lock debugging off and return with 0 if it was off already,
    190 * and also release the graph lock:
    191 */
    192static inline int debug_locks_off_graph_unlock(void)
    193{
    194	int ret = debug_locks_off();
    195
    196	lockdep_unlock();
    197
    198	return ret;
    199}
    200
    201unsigned long nr_list_entries;
    202static struct lock_list list_entries[MAX_LOCKDEP_ENTRIES];
    203static DECLARE_BITMAP(list_entries_in_use, MAX_LOCKDEP_ENTRIES);
    204
    205/*
    206 * All data structures here are protected by the global debug_lock.
    207 *
    208 * nr_lock_classes is the number of elements of lock_classes[] that is
    209 * in use.
    210 */
    211#define KEYHASH_BITS		(MAX_LOCKDEP_KEYS_BITS - 1)
    212#define KEYHASH_SIZE		(1UL << KEYHASH_BITS)
    213static struct hlist_head lock_keys_hash[KEYHASH_SIZE];
    214unsigned long nr_lock_classes;
    215unsigned long nr_zapped_classes;
    216unsigned long max_lock_class_idx;
    217struct lock_class lock_classes[MAX_LOCKDEP_KEYS];
    218DECLARE_BITMAP(lock_classes_in_use, MAX_LOCKDEP_KEYS);
    219
    220static inline struct lock_class *hlock_class(struct held_lock *hlock)
    221{
    222	unsigned int class_idx = hlock->class_idx;
    223
    224	/* Don't re-read hlock->class_idx, can't use READ_ONCE() on bitfield */
    225	barrier();
    226
    227	if (!test_bit(class_idx, lock_classes_in_use)) {
    228		/*
    229		 * Someone passed in garbage, we give up.
    230		 */
    231		DEBUG_LOCKS_WARN_ON(1);
    232		return NULL;
    233	}
    234
    235	/*
    236	 * At this point, if the passed hlock->class_idx is still garbage,
    237	 * we just have to live with it
    238	 */
    239	return lock_classes + class_idx;
    240}
    241
    242#ifdef CONFIG_LOCK_STAT
    243static DEFINE_PER_CPU(struct lock_class_stats[MAX_LOCKDEP_KEYS], cpu_lock_stats);
    244
    245static inline u64 lockstat_clock(void)
    246{
    247	return local_clock();
    248}
    249
    250static int lock_point(unsigned long points[], unsigned long ip)
    251{
    252	int i;
    253
    254	for (i = 0; i < LOCKSTAT_POINTS; i++) {
    255		if (points[i] == 0) {
    256			points[i] = ip;
    257			break;
    258		}
    259		if (points[i] == ip)
    260			break;
    261	}
    262
    263	return i;
    264}
    265
    266static void lock_time_inc(struct lock_time *lt, u64 time)
    267{
    268	if (time > lt->max)
    269		lt->max = time;
    270
    271	if (time < lt->min || !lt->nr)
    272		lt->min = time;
    273
    274	lt->total += time;
    275	lt->nr++;
    276}
    277
    278static inline void lock_time_add(struct lock_time *src, struct lock_time *dst)
    279{
    280	if (!src->nr)
    281		return;
    282
    283	if (src->max > dst->max)
    284		dst->max = src->max;
    285
    286	if (src->min < dst->min || !dst->nr)
    287		dst->min = src->min;
    288
    289	dst->total += src->total;
    290	dst->nr += src->nr;
    291}
    292
    293struct lock_class_stats lock_stats(struct lock_class *class)
    294{
    295	struct lock_class_stats stats;
    296	int cpu, i;
    297
    298	memset(&stats, 0, sizeof(struct lock_class_stats));
    299	for_each_possible_cpu(cpu) {
    300		struct lock_class_stats *pcs =
    301			&per_cpu(cpu_lock_stats, cpu)[class - lock_classes];
    302
    303		for (i = 0; i < ARRAY_SIZE(stats.contention_point); i++)
    304			stats.contention_point[i] += pcs->contention_point[i];
    305
    306		for (i = 0; i < ARRAY_SIZE(stats.contending_point); i++)
    307			stats.contending_point[i] += pcs->contending_point[i];
    308
    309		lock_time_add(&pcs->read_waittime, &stats.read_waittime);
    310		lock_time_add(&pcs->write_waittime, &stats.write_waittime);
    311
    312		lock_time_add(&pcs->read_holdtime, &stats.read_holdtime);
    313		lock_time_add(&pcs->write_holdtime, &stats.write_holdtime);
    314
    315		for (i = 0; i < ARRAY_SIZE(stats.bounces); i++)
    316			stats.bounces[i] += pcs->bounces[i];
    317	}
    318
    319	return stats;
    320}
    321
    322void clear_lock_stats(struct lock_class *class)
    323{
    324	int cpu;
    325
    326	for_each_possible_cpu(cpu) {
    327		struct lock_class_stats *cpu_stats =
    328			&per_cpu(cpu_lock_stats, cpu)[class - lock_classes];
    329
    330		memset(cpu_stats, 0, sizeof(struct lock_class_stats));
    331	}
    332	memset(class->contention_point, 0, sizeof(class->contention_point));
    333	memset(class->contending_point, 0, sizeof(class->contending_point));
    334}
    335
    336static struct lock_class_stats *get_lock_stats(struct lock_class *class)
    337{
    338	return &this_cpu_ptr(cpu_lock_stats)[class - lock_classes];
    339}
    340
    341static void lock_release_holdtime(struct held_lock *hlock)
    342{
    343	struct lock_class_stats *stats;
    344	u64 holdtime;
    345
    346	if (!lock_stat)
    347		return;
    348
    349	holdtime = lockstat_clock() - hlock->holdtime_stamp;
    350
    351	stats = get_lock_stats(hlock_class(hlock));
    352	if (hlock->read)
    353		lock_time_inc(&stats->read_holdtime, holdtime);
    354	else
    355		lock_time_inc(&stats->write_holdtime, holdtime);
    356}
    357#else
    358static inline void lock_release_holdtime(struct held_lock *hlock)
    359{
    360}
    361#endif
    362
    363/*
    364 * We keep a global list of all lock classes. The list is only accessed with
    365 * the lockdep spinlock lock held. free_lock_classes is a list with free
    366 * elements. These elements are linked together by the lock_entry member in
    367 * struct lock_class.
    368 */
    369static LIST_HEAD(all_lock_classes);
    370static LIST_HEAD(free_lock_classes);
    371
    372/**
    373 * struct pending_free - information about data structures about to be freed
    374 * @zapped: Head of a list with struct lock_class elements.
    375 * @lock_chains_being_freed: Bitmap that indicates which lock_chains[] elements
    376 *	are about to be freed.
    377 */
    378struct pending_free {
    379	struct list_head zapped;
    380	DECLARE_BITMAP(lock_chains_being_freed, MAX_LOCKDEP_CHAINS);
    381};
    382
    383/**
    384 * struct delayed_free - data structures used for delayed freeing
    385 *
    386 * A data structure for delayed freeing of data structures that may be
    387 * accessed by RCU readers at the time these were freed.
    388 *
    389 * @rcu_head:  Used to schedule an RCU callback for freeing data structures.
    390 * @index:     Index of @pf to which freed data structures are added.
    391 * @scheduled: Whether or not an RCU callback has been scheduled.
    392 * @pf:        Array with information about data structures about to be freed.
    393 */
    394static struct delayed_free {
    395	struct rcu_head		rcu_head;
    396	int			index;
    397	int			scheduled;
    398	struct pending_free	pf[2];
    399} delayed_free;
    400
    401/*
    402 * The lockdep classes are in a hash-table as well, for fast lookup:
    403 */
    404#define CLASSHASH_BITS		(MAX_LOCKDEP_KEYS_BITS - 1)
    405#define CLASSHASH_SIZE		(1UL << CLASSHASH_BITS)
    406#define __classhashfn(key)	hash_long((unsigned long)key, CLASSHASH_BITS)
    407#define classhashentry(key)	(classhash_table + __classhashfn((key)))
    408
    409static struct hlist_head classhash_table[CLASSHASH_SIZE];
    410
    411/*
    412 * We put the lock dependency chains into a hash-table as well, to cache
    413 * their existence:
    414 */
    415#define CHAINHASH_BITS		(MAX_LOCKDEP_CHAINS_BITS-1)
    416#define CHAINHASH_SIZE		(1UL << CHAINHASH_BITS)
    417#define __chainhashfn(chain)	hash_long(chain, CHAINHASH_BITS)
    418#define chainhashentry(chain)	(chainhash_table + __chainhashfn((chain)))
    419
    420static struct hlist_head chainhash_table[CHAINHASH_SIZE];
    421
    422/*
    423 * the id of held_lock
    424 */
    425static inline u16 hlock_id(struct held_lock *hlock)
    426{
    427	BUILD_BUG_ON(MAX_LOCKDEP_KEYS_BITS + 2 > 16);
    428
    429	return (hlock->class_idx | (hlock->read << MAX_LOCKDEP_KEYS_BITS));
    430}
    431
    432static inline unsigned int chain_hlock_class_idx(u16 hlock_id)
    433{
    434	return hlock_id & (MAX_LOCKDEP_KEYS - 1);
    435}
    436
    437/*
    438 * The hash key of the lock dependency chains is a hash itself too:
    439 * it's a hash of all locks taken up to that lock, including that lock.
    440 * It's a 64-bit hash, because it's important for the keys to be
    441 * unique.
    442 */
    443static inline u64 iterate_chain_key(u64 key, u32 idx)
    444{
    445	u32 k0 = key, k1 = key >> 32;
    446
    447	__jhash_mix(idx, k0, k1); /* Macro that modifies arguments! */
    448
    449	return k0 | (u64)k1 << 32;
    450}
    451
    452void lockdep_init_task(struct task_struct *task)
    453{
    454	task->lockdep_depth = 0; /* no locks held yet */
    455	task->curr_chain_key = INITIAL_CHAIN_KEY;
    456	task->lockdep_recursion = 0;
    457}
    458
    459static __always_inline void lockdep_recursion_inc(void)
    460{
    461	__this_cpu_inc(lockdep_recursion);
    462}
    463
    464static __always_inline void lockdep_recursion_finish(void)
    465{
    466	if (WARN_ON_ONCE(__this_cpu_dec_return(lockdep_recursion)))
    467		__this_cpu_write(lockdep_recursion, 0);
    468}
    469
    470void lockdep_set_selftest_task(struct task_struct *task)
    471{
    472	lockdep_selftest_task_struct = task;
    473}
    474
    475/*
    476 * Debugging switches:
    477 */
    478
    479#define VERBOSE			0
    480#define VERY_VERBOSE		0
    481
    482#if VERBOSE
    483# define HARDIRQ_VERBOSE	1
    484# define SOFTIRQ_VERBOSE	1
    485#else
    486# define HARDIRQ_VERBOSE	0
    487# define SOFTIRQ_VERBOSE	0
    488#endif
    489
    490#if VERBOSE || HARDIRQ_VERBOSE || SOFTIRQ_VERBOSE
    491/*
    492 * Quick filtering for interesting events:
    493 */
    494static int class_filter(struct lock_class *class)
    495{
    496#if 0
    497	/* Example */
    498	if (class->name_version == 1 &&
    499			!strcmp(class->name, "lockname"))
    500		return 1;
    501	if (class->name_version == 1 &&
    502			!strcmp(class->name, "&struct->lockfield"))
    503		return 1;
    504#endif
    505	/* Filter everything else. 1 would be to allow everything else */
    506	return 0;
    507}
    508#endif
    509
    510static int verbose(struct lock_class *class)
    511{
    512#if VERBOSE
    513	return class_filter(class);
    514#endif
    515	return 0;
    516}
    517
    518static void print_lockdep_off(const char *bug_msg)
    519{
    520	printk(KERN_DEBUG "%s\n", bug_msg);
    521	printk(KERN_DEBUG "turning off the locking correctness validator.\n");
    522#ifdef CONFIG_LOCK_STAT
    523	printk(KERN_DEBUG "Please attach the output of /proc/lock_stat to the bug report\n");
    524#endif
    525}
    526
    527unsigned long nr_stack_trace_entries;
    528
    529#ifdef CONFIG_PROVE_LOCKING
    530/**
    531 * struct lock_trace - single stack backtrace
    532 * @hash_entry:	Entry in a stack_trace_hash[] list.
    533 * @hash:	jhash() of @entries.
    534 * @nr_entries:	Number of entries in @entries.
    535 * @entries:	Actual stack backtrace.
    536 */
    537struct lock_trace {
    538	struct hlist_node	hash_entry;
    539	u32			hash;
    540	u32			nr_entries;
    541	unsigned long		entries[] __aligned(sizeof(unsigned long));
    542};
    543#define LOCK_TRACE_SIZE_IN_LONGS				\
    544	(sizeof(struct lock_trace) / sizeof(unsigned long))
    545/*
    546 * Stack-trace: sequence of lock_trace structures. Protected by the graph_lock.
    547 */
    548static unsigned long stack_trace[MAX_STACK_TRACE_ENTRIES];
    549static struct hlist_head stack_trace_hash[STACK_TRACE_HASH_SIZE];
    550
    551static bool traces_identical(struct lock_trace *t1, struct lock_trace *t2)
    552{
    553	return t1->hash == t2->hash && t1->nr_entries == t2->nr_entries &&
    554		memcmp(t1->entries, t2->entries,
    555		       t1->nr_entries * sizeof(t1->entries[0])) == 0;
    556}
    557
    558static struct lock_trace *save_trace(void)
    559{
    560	struct lock_trace *trace, *t2;
    561	struct hlist_head *hash_head;
    562	u32 hash;
    563	int max_entries;
    564
    565	BUILD_BUG_ON_NOT_POWER_OF_2(STACK_TRACE_HASH_SIZE);
    566	BUILD_BUG_ON(LOCK_TRACE_SIZE_IN_LONGS >= MAX_STACK_TRACE_ENTRIES);
    567
    568	trace = (struct lock_trace *)(stack_trace + nr_stack_trace_entries);
    569	max_entries = MAX_STACK_TRACE_ENTRIES - nr_stack_trace_entries -
    570		LOCK_TRACE_SIZE_IN_LONGS;
    571
    572	if (max_entries <= 0) {
    573		if (!debug_locks_off_graph_unlock())
    574			return NULL;
    575
    576		print_lockdep_off("BUG: MAX_STACK_TRACE_ENTRIES too low!");
    577		dump_stack();
    578
    579		return NULL;
    580	}
    581	trace->nr_entries = stack_trace_save(trace->entries, max_entries, 3);
    582
    583	hash = jhash(trace->entries, trace->nr_entries *
    584		     sizeof(trace->entries[0]), 0);
    585	trace->hash = hash;
    586	hash_head = stack_trace_hash + (hash & (STACK_TRACE_HASH_SIZE - 1));
    587	hlist_for_each_entry(t2, hash_head, hash_entry) {
    588		if (traces_identical(trace, t2))
    589			return t2;
    590	}
    591	nr_stack_trace_entries += LOCK_TRACE_SIZE_IN_LONGS + trace->nr_entries;
    592	hlist_add_head(&trace->hash_entry, hash_head);
    593
    594	return trace;
    595}
    596
    597/* Return the number of stack traces in the stack_trace[] array. */
    598u64 lockdep_stack_trace_count(void)
    599{
    600	struct lock_trace *trace;
    601	u64 c = 0;
    602	int i;
    603
    604	for (i = 0; i < ARRAY_SIZE(stack_trace_hash); i++) {
    605		hlist_for_each_entry(trace, &stack_trace_hash[i], hash_entry) {
    606			c++;
    607		}
    608	}
    609
    610	return c;
    611}
    612
    613/* Return the number of stack hash chains that have at least one stack trace. */
    614u64 lockdep_stack_hash_count(void)
    615{
    616	u64 c = 0;
    617	int i;
    618
    619	for (i = 0; i < ARRAY_SIZE(stack_trace_hash); i++)
    620		if (!hlist_empty(&stack_trace_hash[i]))
    621			c++;
    622
    623	return c;
    624}
    625#endif
    626
    627unsigned int nr_hardirq_chains;
    628unsigned int nr_softirq_chains;
    629unsigned int nr_process_chains;
    630unsigned int max_lockdep_depth;
    631
    632#ifdef CONFIG_DEBUG_LOCKDEP
    633/*
    634 * Various lockdep statistics:
    635 */
    636DEFINE_PER_CPU(struct lockdep_stats, lockdep_stats);
    637#endif
    638
    639#ifdef CONFIG_PROVE_LOCKING
    640/*
    641 * Locking printouts:
    642 */
    643
    644#define __USAGE(__STATE)						\
    645	[LOCK_USED_IN_##__STATE] = "IN-"__stringify(__STATE)"-W",	\
    646	[LOCK_ENABLED_##__STATE] = __stringify(__STATE)"-ON-W",		\
    647	[LOCK_USED_IN_##__STATE##_READ] = "IN-"__stringify(__STATE)"-R",\
    648	[LOCK_ENABLED_##__STATE##_READ] = __stringify(__STATE)"-ON-R",
    649
    650static const char *usage_str[] =
    651{
    652#define LOCKDEP_STATE(__STATE) __USAGE(__STATE)
    653#include "lockdep_states.h"
    654#undef LOCKDEP_STATE
    655	[LOCK_USED] = "INITIAL USE",
    656	[LOCK_USED_READ] = "INITIAL READ USE",
    657	/* abused as string storage for verify_lock_unused() */
    658	[LOCK_USAGE_STATES] = "IN-NMI",
    659};
    660#endif
    661
    662const char *__get_key_name(const struct lockdep_subclass_key *key, char *str)
    663{
    664	return kallsyms_lookup((unsigned long)key, NULL, NULL, NULL, str);
    665}
    666
    667static inline unsigned long lock_flag(enum lock_usage_bit bit)
    668{
    669	return 1UL << bit;
    670}
    671
    672static char get_usage_char(struct lock_class *class, enum lock_usage_bit bit)
    673{
    674	/*
    675	 * The usage character defaults to '.' (i.e., irqs disabled and not in
    676	 * irq context), which is the safest usage category.
    677	 */
    678	char c = '.';
    679
    680	/*
    681	 * The order of the following usage checks matters, which will
    682	 * result in the outcome character as follows:
    683	 *
    684	 * - '+': irq is enabled and not in irq context
    685	 * - '-': in irq context and irq is disabled
    686	 * - '?': in irq context and irq is enabled
    687	 */
    688	if (class->usage_mask & lock_flag(bit + LOCK_USAGE_DIR_MASK)) {
    689		c = '+';
    690		if (class->usage_mask & lock_flag(bit))
    691			c = '?';
    692	} else if (class->usage_mask & lock_flag(bit))
    693		c = '-';
    694
    695	return c;
    696}
    697
    698void get_usage_chars(struct lock_class *class, char usage[LOCK_USAGE_CHARS])
    699{
    700	int i = 0;
    701
    702#define LOCKDEP_STATE(__STATE) 						\
    703	usage[i++] = get_usage_char(class, LOCK_USED_IN_##__STATE);	\
    704	usage[i++] = get_usage_char(class, LOCK_USED_IN_##__STATE##_READ);
    705#include "lockdep_states.h"
    706#undef LOCKDEP_STATE
    707
    708	usage[i] = '\0';
    709}
    710
    711static void __print_lock_name(struct lock_class *class)
    712{
    713	char str[KSYM_NAME_LEN];
    714	const char *name;
    715
    716	name = class->name;
    717	if (!name) {
    718		name = __get_key_name(class->key, str);
    719		printk(KERN_CONT "%s", name);
    720	} else {
    721		printk(KERN_CONT "%s", name);
    722		if (class->name_version > 1)
    723			printk(KERN_CONT "#%d", class->name_version);
    724		if (class->subclass)
    725			printk(KERN_CONT "/%d", class->subclass);
    726	}
    727}
    728
    729static void print_lock_name(struct lock_class *class)
    730{
    731	char usage[LOCK_USAGE_CHARS];
    732
    733	get_usage_chars(class, usage);
    734
    735	printk(KERN_CONT " (");
    736	__print_lock_name(class);
    737	printk(KERN_CONT "){%s}-{%d:%d}", usage,
    738			class->wait_type_outer ?: class->wait_type_inner,
    739			class->wait_type_inner);
    740}
    741
    742static void print_lockdep_cache(struct lockdep_map *lock)
    743{
    744	const char *name;
    745	char str[KSYM_NAME_LEN];
    746
    747	name = lock->name;
    748	if (!name)
    749		name = __get_key_name(lock->key->subkeys, str);
    750
    751	printk(KERN_CONT "%s", name);
    752}
    753
    754static void print_lock(struct held_lock *hlock)
    755{
    756	/*
    757	 * We can be called locklessly through debug_show_all_locks() so be
    758	 * extra careful, the hlock might have been released and cleared.
    759	 *
    760	 * If this indeed happens, lets pretend it does not hurt to continue
    761	 * to print the lock unless the hlock class_idx does not point to a
    762	 * registered class. The rationale here is: since we don't attempt
    763	 * to distinguish whether we are in this situation, if it just
    764	 * happened we can't count on class_idx to tell either.
    765	 */
    766	struct lock_class *lock = hlock_class(hlock);
    767
    768	if (!lock) {
    769		printk(KERN_CONT "<RELEASED>\n");
    770		return;
    771	}
    772
    773	printk(KERN_CONT "%px", hlock->instance);
    774	print_lock_name(lock);
    775	printk(KERN_CONT ", at: %pS\n", (void *)hlock->acquire_ip);
    776}
    777
    778static void lockdep_print_held_locks(struct task_struct *p)
    779{
    780	int i, depth = READ_ONCE(p->lockdep_depth);
    781
    782	if (!depth)
    783		printk("no locks held by %s/%d.\n", p->comm, task_pid_nr(p));
    784	else
    785		printk("%d lock%s held by %s/%d:\n", depth,
    786		       depth > 1 ? "s" : "", p->comm, task_pid_nr(p));
    787	/*
    788	 * It's not reliable to print a task's held locks if it's not sleeping
    789	 * and it's not the current task.
    790	 */
    791	if (p != current && task_is_running(p))
    792		return;
    793	for (i = 0; i < depth; i++) {
    794		printk(" #%d: ", i);
    795		print_lock(p->held_locks + i);
    796	}
    797}
    798
    799static void print_kernel_ident(void)
    800{
    801	printk("%s %.*s %s\n", init_utsname()->release,
    802		(int)strcspn(init_utsname()->version, " "),
    803		init_utsname()->version,
    804		print_tainted());
    805}
    806
    807static int very_verbose(struct lock_class *class)
    808{
    809#if VERY_VERBOSE
    810	return class_filter(class);
    811#endif
    812	return 0;
    813}
    814
    815/*
    816 * Is this the address of a static object:
    817 */
    818#ifdef __KERNEL__
    819/*
    820 * Check if an address is part of freed initmem. After initmem is freed,
    821 * memory can be allocated from it, and such allocations would then have
    822 * addresses within the range [_stext, _end].
    823 */
    824#ifndef arch_is_kernel_initmem_freed
    825static int arch_is_kernel_initmem_freed(unsigned long addr)
    826{
    827	if (system_state < SYSTEM_FREEING_INITMEM)
    828		return 0;
    829
    830	return init_section_contains((void *)addr, 1);
    831}
    832#endif
    833
    834static int static_obj(const void *obj)
    835{
    836	unsigned long start = (unsigned long) &_stext,
    837		      end   = (unsigned long) &_end,
    838		      addr  = (unsigned long) obj;
    839
    840	if (arch_is_kernel_initmem_freed(addr))
    841		return 0;
    842
    843	/*
    844	 * static variable?
    845	 */
    846	if ((addr >= start) && (addr < end))
    847		return 1;
    848
    849	/*
    850	 * in-kernel percpu var?
    851	 */
    852	if (is_kernel_percpu_address(addr))
    853		return 1;
    854
    855	/*
    856	 * module static or percpu var?
    857	 */
    858	return is_module_address(addr) || is_module_percpu_address(addr);
    859}
    860#endif
    861
    862/*
    863 * To make lock name printouts unique, we calculate a unique
    864 * class->name_version generation counter. The caller must hold the graph
    865 * lock.
    866 */
    867static int count_matching_names(struct lock_class *new_class)
    868{
    869	struct lock_class *class;
    870	int count = 0;
    871
    872	if (!new_class->name)
    873		return 0;
    874
    875	list_for_each_entry(class, &all_lock_classes, lock_entry) {
    876		if (new_class->key - new_class->subclass == class->key)
    877			return class->name_version;
    878		if (class->name && !strcmp(class->name, new_class->name))
    879			count = max(count, class->name_version);
    880	}
    881
    882	return count + 1;
    883}
    884
    885/* used from NMI context -- must be lockless */
    886static noinstr struct lock_class *
    887look_up_lock_class(const struct lockdep_map *lock, unsigned int subclass)
    888{
    889	struct lockdep_subclass_key *key;
    890	struct hlist_head *hash_head;
    891	struct lock_class *class;
    892
    893	if (unlikely(subclass >= MAX_LOCKDEP_SUBCLASSES)) {
    894		instrumentation_begin();
    895		debug_locks_off();
    896		printk(KERN_ERR
    897			"BUG: looking up invalid subclass: %u\n", subclass);
    898		printk(KERN_ERR
    899			"turning off the locking correctness validator.\n");
    900		dump_stack();
    901		instrumentation_end();
    902		return NULL;
    903	}
    904
    905	/*
    906	 * If it is not initialised then it has never been locked,
    907	 * so it won't be present in the hash table.
    908	 */
    909	if (unlikely(!lock->key))
    910		return NULL;
    911
    912	/*
    913	 * NOTE: the class-key must be unique. For dynamic locks, a static
    914	 * lock_class_key variable is passed in through the mutex_init()
    915	 * (or spin_lock_init()) call - which acts as the key. For static
    916	 * locks we use the lock object itself as the key.
    917	 */
    918	BUILD_BUG_ON(sizeof(struct lock_class_key) >
    919			sizeof(struct lockdep_map));
    920
    921	key = lock->key->subkeys + subclass;
    922
    923	hash_head = classhashentry(key);
    924
    925	/*
    926	 * We do an RCU walk of the hash, see lockdep_free_key_range().
    927	 */
    928	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
    929		return NULL;
    930
    931	hlist_for_each_entry_rcu_notrace(class, hash_head, hash_entry) {
    932		if (class->key == key) {
    933			/*
    934			 * Huh! same key, different name? Did someone trample
    935			 * on some memory? We're most confused.
    936			 */
    937			WARN_ON_ONCE(class->name != lock->name &&
    938				     lock->key != &__lockdep_no_validate__);
    939			return class;
    940		}
    941	}
    942
    943	return NULL;
    944}
    945
    946/*
    947 * Static locks do not have their class-keys yet - for them the key is
    948 * the lock object itself. If the lock is in the per cpu area, the
    949 * canonical address of the lock (per cpu offset removed) is used.
    950 */
    951static bool assign_lock_key(struct lockdep_map *lock)
    952{
    953	unsigned long can_addr, addr = (unsigned long)lock;
    954
    955#ifdef __KERNEL__
    956	/*
    957	 * lockdep_free_key_range() assumes that struct lock_class_key
    958	 * objects do not overlap. Since we use the address of lock
    959	 * objects as class key for static objects, check whether the
    960	 * size of lock_class_key objects does not exceed the size of
    961	 * the smallest lock object.
    962	 */
    963	BUILD_BUG_ON(sizeof(struct lock_class_key) > sizeof(raw_spinlock_t));
    964#endif
    965
    966	if (__is_kernel_percpu_address(addr, &can_addr))
    967		lock->key = (void *)can_addr;
    968	else if (__is_module_percpu_address(addr, &can_addr))
    969		lock->key = (void *)can_addr;
    970	else if (static_obj(lock))
    971		lock->key = (void *)lock;
    972	else {
    973		/* Debug-check: all keys must be persistent! */
    974		debug_locks_off();
    975		pr_err("INFO: trying to register non-static key.\n");
    976		pr_err("The code is fine but needs lockdep annotation, or maybe\n");
    977		pr_err("you didn't initialize this object before use?\n");
    978		pr_err("turning off the locking correctness validator.\n");
    979		dump_stack();
    980		return false;
    981	}
    982
    983	return true;
    984}
    985
    986#ifdef CONFIG_DEBUG_LOCKDEP
    987
    988/* Check whether element @e occurs in list @h */
    989static bool in_list(struct list_head *e, struct list_head *h)
    990{
    991	struct list_head *f;
    992
    993	list_for_each(f, h) {
    994		if (e == f)
    995			return true;
    996	}
    997
    998	return false;
    999}
   1000
   1001/*
   1002 * Check whether entry @e occurs in any of the locks_after or locks_before
   1003 * lists.
   1004 */
   1005static bool in_any_class_list(struct list_head *e)
   1006{
   1007	struct lock_class *class;
   1008	int i;
   1009
   1010	for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
   1011		class = &lock_classes[i];
   1012		if (in_list(e, &class->locks_after) ||
   1013		    in_list(e, &class->locks_before))
   1014			return true;
   1015	}
   1016	return false;
   1017}
   1018
   1019static bool class_lock_list_valid(struct lock_class *c, struct list_head *h)
   1020{
   1021	struct lock_list *e;
   1022
   1023	list_for_each_entry(e, h, entry) {
   1024		if (e->links_to != c) {
   1025			printk(KERN_INFO "class %s: mismatch for lock entry %ld; class %s <> %s",
   1026			       c->name ? : "(?)",
   1027			       (unsigned long)(e - list_entries),
   1028			       e->links_to && e->links_to->name ?
   1029			       e->links_to->name : "(?)",
   1030			       e->class && e->class->name ? e->class->name :
   1031			       "(?)");
   1032			return false;
   1033		}
   1034	}
   1035	return true;
   1036}
   1037
   1038#ifdef CONFIG_PROVE_LOCKING
   1039static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS];
   1040#endif
   1041
   1042static bool check_lock_chain_key(struct lock_chain *chain)
   1043{
   1044#ifdef CONFIG_PROVE_LOCKING
   1045	u64 chain_key = INITIAL_CHAIN_KEY;
   1046	int i;
   1047
   1048	for (i = chain->base; i < chain->base + chain->depth; i++)
   1049		chain_key = iterate_chain_key(chain_key, chain_hlocks[i]);
   1050	/*
   1051	 * The 'unsigned long long' casts avoid that a compiler warning
   1052	 * is reported when building tools/lib/lockdep.
   1053	 */
   1054	if (chain->chain_key != chain_key) {
   1055		printk(KERN_INFO "chain %lld: key %#llx <> %#llx\n",
   1056		       (unsigned long long)(chain - lock_chains),
   1057		       (unsigned long long)chain->chain_key,
   1058		       (unsigned long long)chain_key);
   1059		return false;
   1060	}
   1061#endif
   1062	return true;
   1063}
   1064
   1065static bool in_any_zapped_class_list(struct lock_class *class)
   1066{
   1067	struct pending_free *pf;
   1068	int i;
   1069
   1070	for (i = 0, pf = delayed_free.pf; i < ARRAY_SIZE(delayed_free.pf); i++, pf++) {
   1071		if (in_list(&class->lock_entry, &pf->zapped))
   1072			return true;
   1073	}
   1074
   1075	return false;
   1076}
   1077
   1078static bool __check_data_structures(void)
   1079{
   1080	struct lock_class *class;
   1081	struct lock_chain *chain;
   1082	struct hlist_head *head;
   1083	struct lock_list *e;
   1084	int i;
   1085
   1086	/* Check whether all classes occur in a lock list. */
   1087	for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
   1088		class = &lock_classes[i];
   1089		if (!in_list(&class->lock_entry, &all_lock_classes) &&
   1090		    !in_list(&class->lock_entry, &free_lock_classes) &&
   1091		    !in_any_zapped_class_list(class)) {
   1092			printk(KERN_INFO "class %px/%s is not in any class list\n",
   1093			       class, class->name ? : "(?)");
   1094			return false;
   1095		}
   1096	}
   1097
   1098	/* Check whether all classes have valid lock lists. */
   1099	for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
   1100		class = &lock_classes[i];
   1101		if (!class_lock_list_valid(class, &class->locks_before))
   1102			return false;
   1103		if (!class_lock_list_valid(class, &class->locks_after))
   1104			return false;
   1105	}
   1106
   1107	/* Check the chain_key of all lock chains. */
   1108	for (i = 0; i < ARRAY_SIZE(chainhash_table); i++) {
   1109		head = chainhash_table + i;
   1110		hlist_for_each_entry_rcu(chain, head, entry) {
   1111			if (!check_lock_chain_key(chain))
   1112				return false;
   1113		}
   1114	}
   1115
   1116	/*
   1117	 * Check whether all list entries that are in use occur in a class
   1118	 * lock list.
   1119	 */
   1120	for_each_set_bit(i, list_entries_in_use, ARRAY_SIZE(list_entries)) {
   1121		e = list_entries + i;
   1122		if (!in_any_class_list(&e->entry)) {
   1123			printk(KERN_INFO "list entry %d is not in any class list; class %s <> %s\n",
   1124			       (unsigned int)(e - list_entries),
   1125			       e->class->name ? : "(?)",
   1126			       e->links_to->name ? : "(?)");
   1127			return false;
   1128		}
   1129	}
   1130
   1131	/*
   1132	 * Check whether all list entries that are not in use do not occur in
   1133	 * a class lock list.
   1134	 */
   1135	for_each_clear_bit(i, list_entries_in_use, ARRAY_SIZE(list_entries)) {
   1136		e = list_entries + i;
   1137		if (in_any_class_list(&e->entry)) {
   1138			printk(KERN_INFO "list entry %d occurs in a class list; class %s <> %s\n",
   1139			       (unsigned int)(e - list_entries),
   1140			       e->class && e->class->name ? e->class->name :
   1141			       "(?)",
   1142			       e->links_to && e->links_to->name ?
   1143			       e->links_to->name : "(?)");
   1144			return false;
   1145		}
   1146	}
   1147
   1148	return true;
   1149}
   1150
   1151int check_consistency = 0;
   1152module_param(check_consistency, int, 0644);
   1153
   1154static void check_data_structures(void)
   1155{
   1156	static bool once = false;
   1157
   1158	if (check_consistency && !once) {
   1159		if (!__check_data_structures()) {
   1160			once = true;
   1161			WARN_ON(once);
   1162		}
   1163	}
   1164}
   1165
   1166#else /* CONFIG_DEBUG_LOCKDEP */
   1167
   1168static inline void check_data_structures(void) { }
   1169
   1170#endif /* CONFIG_DEBUG_LOCKDEP */
   1171
   1172static void init_chain_block_buckets(void);
   1173
   1174/*
   1175 * Initialize the lock_classes[] array elements, the free_lock_classes list
   1176 * and also the delayed_free structure.
   1177 */
   1178static void init_data_structures_once(void)
   1179{
   1180	static bool __read_mostly ds_initialized, rcu_head_initialized;
   1181	int i;
   1182
   1183	if (likely(rcu_head_initialized))
   1184		return;
   1185
   1186	if (system_state >= SYSTEM_SCHEDULING) {
   1187		init_rcu_head(&delayed_free.rcu_head);
   1188		rcu_head_initialized = true;
   1189	}
   1190
   1191	if (ds_initialized)
   1192		return;
   1193
   1194	ds_initialized = true;
   1195
   1196	INIT_LIST_HEAD(&delayed_free.pf[0].zapped);
   1197	INIT_LIST_HEAD(&delayed_free.pf[1].zapped);
   1198
   1199	for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
   1200		list_add_tail(&lock_classes[i].lock_entry, &free_lock_classes);
   1201		INIT_LIST_HEAD(&lock_classes[i].locks_after);
   1202		INIT_LIST_HEAD(&lock_classes[i].locks_before);
   1203	}
   1204	init_chain_block_buckets();
   1205}
   1206
   1207static inline struct hlist_head *keyhashentry(const struct lock_class_key *key)
   1208{
   1209	unsigned long hash = hash_long((uintptr_t)key, KEYHASH_BITS);
   1210
   1211	return lock_keys_hash + hash;
   1212}
   1213
   1214/* Register a dynamically allocated key. */
   1215void lockdep_register_key(struct lock_class_key *key)
   1216{
   1217	struct hlist_head *hash_head;
   1218	struct lock_class_key *k;
   1219	unsigned long flags;
   1220
   1221	if (WARN_ON_ONCE(static_obj(key)))
   1222		return;
   1223	hash_head = keyhashentry(key);
   1224
   1225	raw_local_irq_save(flags);
   1226	if (!graph_lock())
   1227		goto restore_irqs;
   1228	hlist_for_each_entry_rcu(k, hash_head, hash_entry) {
   1229		if (WARN_ON_ONCE(k == key))
   1230			goto out_unlock;
   1231	}
   1232	hlist_add_head_rcu(&key->hash_entry, hash_head);
   1233out_unlock:
   1234	graph_unlock();
   1235restore_irqs:
   1236	raw_local_irq_restore(flags);
   1237}
   1238EXPORT_SYMBOL_GPL(lockdep_register_key);
   1239
   1240/* Check whether a key has been registered as a dynamic key. */
   1241static bool is_dynamic_key(const struct lock_class_key *key)
   1242{
   1243	struct hlist_head *hash_head;
   1244	struct lock_class_key *k;
   1245	bool found = false;
   1246
   1247	if (WARN_ON_ONCE(static_obj(key)))
   1248		return false;
   1249
   1250	/*
   1251	 * If lock debugging is disabled lock_keys_hash[] may contain
   1252	 * pointers to memory that has already been freed. Avoid triggering
   1253	 * a use-after-free in that case by returning early.
   1254	 */
   1255	if (!debug_locks)
   1256		return true;
   1257
   1258	hash_head = keyhashentry(key);
   1259
   1260	rcu_read_lock();
   1261	hlist_for_each_entry_rcu(k, hash_head, hash_entry) {
   1262		if (k == key) {
   1263			found = true;
   1264			break;
   1265		}
   1266	}
   1267	rcu_read_unlock();
   1268
   1269	return found;
   1270}
   1271
   1272/*
   1273 * Register a lock's class in the hash-table, if the class is not present
   1274 * yet. Otherwise we look it up. We cache the result in the lock object
   1275 * itself, so actual lookup of the hash should be once per lock object.
   1276 */
   1277static struct lock_class *
   1278register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
   1279{
   1280	struct lockdep_subclass_key *key;
   1281	struct hlist_head *hash_head;
   1282	struct lock_class *class;
   1283	int idx;
   1284
   1285	DEBUG_LOCKS_WARN_ON(!irqs_disabled());
   1286
   1287	class = look_up_lock_class(lock, subclass);
   1288	if (likely(class))
   1289		goto out_set_class_cache;
   1290
   1291	if (!lock->key) {
   1292		if (!assign_lock_key(lock))
   1293			return NULL;
   1294	} else if (!static_obj(lock->key) && !is_dynamic_key(lock->key)) {
   1295		return NULL;
   1296	}
   1297
   1298	key = lock->key->subkeys + subclass;
   1299	hash_head = classhashentry(key);
   1300
   1301	if (!graph_lock()) {
   1302		return NULL;
   1303	}
   1304	/*
   1305	 * We have to do the hash-walk again, to avoid races
   1306	 * with another CPU:
   1307	 */
   1308	hlist_for_each_entry_rcu(class, hash_head, hash_entry) {
   1309		if (class->key == key)
   1310			goto out_unlock_set;
   1311	}
   1312
   1313	init_data_structures_once();
   1314
   1315	/* Allocate a new lock class and add it to the hash. */
   1316	class = list_first_entry_or_null(&free_lock_classes, typeof(*class),
   1317					 lock_entry);
   1318	if (!class) {
   1319		if (!debug_locks_off_graph_unlock()) {
   1320			return NULL;
   1321		}
   1322
   1323		print_lockdep_off("BUG: MAX_LOCKDEP_KEYS too low!");
   1324		dump_stack();
   1325		return NULL;
   1326	}
   1327	nr_lock_classes++;
   1328	__set_bit(class - lock_classes, lock_classes_in_use);
   1329	debug_atomic_inc(nr_unused_locks);
   1330	class->key = key;
   1331	class->name = lock->name;
   1332	class->subclass = subclass;
   1333	WARN_ON_ONCE(!list_empty(&class->locks_before));
   1334	WARN_ON_ONCE(!list_empty(&class->locks_after));
   1335	class->name_version = count_matching_names(class);
   1336	class->wait_type_inner = lock->wait_type_inner;
   1337	class->wait_type_outer = lock->wait_type_outer;
   1338	class->lock_type = lock->lock_type;
   1339	/*
   1340	 * We use RCU's safe list-add method to make
   1341	 * parallel walking of the hash-list safe:
   1342	 */
   1343	hlist_add_head_rcu(&class->hash_entry, hash_head);
   1344	/*
   1345	 * Remove the class from the free list and add it to the global list
   1346	 * of classes.
   1347	 */
   1348	list_move_tail(&class->lock_entry, &all_lock_classes);
   1349	idx = class - lock_classes;
   1350	if (idx > max_lock_class_idx)
   1351		max_lock_class_idx = idx;
   1352
   1353	if (verbose(class)) {
   1354		graph_unlock();
   1355
   1356		printk("\nnew class %px: %s", class->key, class->name);
   1357		if (class->name_version > 1)
   1358			printk(KERN_CONT "#%d", class->name_version);
   1359		printk(KERN_CONT "\n");
   1360		dump_stack();
   1361
   1362		if (!graph_lock()) {
   1363			return NULL;
   1364		}
   1365	}
   1366out_unlock_set:
   1367	graph_unlock();
   1368
   1369out_set_class_cache:
   1370	if (!subclass || force)
   1371		lock->class_cache[0] = class;
   1372	else if (subclass < NR_LOCKDEP_CACHING_CLASSES)
   1373		lock->class_cache[subclass] = class;
   1374
   1375	/*
   1376	 * Hash collision, did we smoke some? We found a class with a matching
   1377	 * hash but the subclass -- which is hashed in -- didn't match.
   1378	 */
   1379	if (DEBUG_LOCKS_WARN_ON(class->subclass != subclass))
   1380		return NULL;
   1381
   1382	return class;
   1383}
   1384
   1385#ifdef CONFIG_PROVE_LOCKING
   1386/*
   1387 * Allocate a lockdep entry. (assumes the graph_lock held, returns
   1388 * with NULL on failure)
   1389 */
   1390static struct lock_list *alloc_list_entry(void)
   1391{
   1392	int idx = find_first_zero_bit(list_entries_in_use,
   1393				      ARRAY_SIZE(list_entries));
   1394
   1395	if (idx >= ARRAY_SIZE(list_entries)) {
   1396		if (!debug_locks_off_graph_unlock())
   1397			return NULL;
   1398
   1399		print_lockdep_off("BUG: MAX_LOCKDEP_ENTRIES too low!");
   1400		dump_stack();
   1401		return NULL;
   1402	}
   1403	nr_list_entries++;
   1404	__set_bit(idx, list_entries_in_use);
   1405	return list_entries + idx;
   1406}
   1407
   1408/*
   1409 * Add a new dependency to the head of the list:
   1410 */
   1411static int add_lock_to_list(struct lock_class *this,
   1412			    struct lock_class *links_to, struct list_head *head,
   1413			    u16 distance, u8 dep,
   1414			    const struct lock_trace *trace)
   1415{
   1416	struct lock_list *entry;
   1417	/*
   1418	 * Lock not present yet - get a new dependency struct and
   1419	 * add it to the list:
   1420	 */
   1421	entry = alloc_list_entry();
   1422	if (!entry)
   1423		return 0;
   1424
   1425	entry->class = this;
   1426	entry->links_to = links_to;
   1427	entry->dep = dep;
   1428	entry->distance = distance;
   1429	entry->trace = trace;
   1430	/*
   1431	 * Both allocation and removal are done under the graph lock; but
   1432	 * iteration is under RCU-sched; see look_up_lock_class() and
   1433	 * lockdep_free_key_range().
   1434	 */
   1435	list_add_tail_rcu(&entry->entry, head);
   1436
   1437	return 1;
   1438}
   1439
   1440/*
   1441 * For good efficiency of modular, we use power of 2
   1442 */
   1443#define MAX_CIRCULAR_QUEUE_SIZE		(1UL << CONFIG_LOCKDEP_CIRCULAR_QUEUE_BITS)
   1444#define CQ_MASK				(MAX_CIRCULAR_QUEUE_SIZE-1)
   1445
   1446/*
   1447 * The circular_queue and helpers are used to implement graph
   1448 * breadth-first search (BFS) algorithm, by which we can determine
   1449 * whether there is a path from a lock to another. In deadlock checks,
   1450 * a path from the next lock to be acquired to a previous held lock
   1451 * indicates that adding the <prev> -> <next> lock dependency will
   1452 * produce a circle in the graph. Breadth-first search instead of
   1453 * depth-first search is used in order to find the shortest (circular)
   1454 * path.
   1455 */
   1456struct circular_queue {
   1457	struct lock_list *element[MAX_CIRCULAR_QUEUE_SIZE];
   1458	unsigned int  front, rear;
   1459};
   1460
   1461static struct circular_queue lock_cq;
   1462
   1463unsigned int max_bfs_queue_depth;
   1464
   1465static unsigned int lockdep_dependency_gen_id;
   1466
   1467static inline void __cq_init(struct circular_queue *cq)
   1468{
   1469	cq->front = cq->rear = 0;
   1470	lockdep_dependency_gen_id++;
   1471}
   1472
   1473static inline int __cq_empty(struct circular_queue *cq)
   1474{
   1475	return (cq->front == cq->rear);
   1476}
   1477
   1478static inline int __cq_full(struct circular_queue *cq)
   1479{
   1480	return ((cq->rear + 1) & CQ_MASK) == cq->front;
   1481}
   1482
   1483static inline int __cq_enqueue(struct circular_queue *cq, struct lock_list *elem)
   1484{
   1485	if (__cq_full(cq))
   1486		return -1;
   1487
   1488	cq->element[cq->rear] = elem;
   1489	cq->rear = (cq->rear + 1) & CQ_MASK;
   1490	return 0;
   1491}
   1492
   1493/*
   1494 * Dequeue an element from the circular_queue, return a lock_list if
   1495 * the queue is not empty, or NULL if otherwise.
   1496 */
   1497static inline struct lock_list * __cq_dequeue(struct circular_queue *cq)
   1498{
   1499	struct lock_list * lock;
   1500
   1501	if (__cq_empty(cq))
   1502		return NULL;
   1503
   1504	lock = cq->element[cq->front];
   1505	cq->front = (cq->front + 1) & CQ_MASK;
   1506
   1507	return lock;
   1508}
   1509
   1510static inline unsigned int  __cq_get_elem_count(struct circular_queue *cq)
   1511{
   1512	return (cq->rear - cq->front) & CQ_MASK;
   1513}
   1514
   1515static inline void mark_lock_accessed(struct lock_list *lock)
   1516{
   1517	lock->class->dep_gen_id = lockdep_dependency_gen_id;
   1518}
   1519
   1520static inline void visit_lock_entry(struct lock_list *lock,
   1521				    struct lock_list *parent)
   1522{
   1523	lock->parent = parent;
   1524}
   1525
   1526static inline unsigned long lock_accessed(struct lock_list *lock)
   1527{
   1528	return lock->class->dep_gen_id == lockdep_dependency_gen_id;
   1529}
   1530
   1531static inline struct lock_list *get_lock_parent(struct lock_list *child)
   1532{
   1533	return child->parent;
   1534}
   1535
   1536static inline int get_lock_depth(struct lock_list *child)
   1537{
   1538	int depth = 0;
   1539	struct lock_list *parent;
   1540
   1541	while ((parent = get_lock_parent(child))) {
   1542		child = parent;
   1543		depth++;
   1544	}
   1545	return depth;
   1546}
   1547
   1548/*
   1549 * Return the forward or backward dependency list.
   1550 *
   1551 * @lock:   the lock_list to get its class's dependency list
   1552 * @offset: the offset to struct lock_class to determine whether it is
   1553 *          locks_after or locks_before
   1554 */
   1555static inline struct list_head *get_dep_list(struct lock_list *lock, int offset)
   1556{
   1557	void *lock_class = lock->class;
   1558
   1559	return lock_class + offset;
   1560}
   1561/*
   1562 * Return values of a bfs search:
   1563 *
   1564 * BFS_E* indicates an error
   1565 * BFS_R* indicates a result (match or not)
   1566 *
   1567 * BFS_EINVALIDNODE: Find a invalid node in the graph.
   1568 *
   1569 * BFS_EQUEUEFULL: The queue is full while doing the bfs.
   1570 *
   1571 * BFS_RMATCH: Find the matched node in the graph, and put that node into
   1572 *             *@target_entry.
   1573 *
   1574 * BFS_RNOMATCH: Haven't found the matched node and keep *@target_entry
   1575 *               _unchanged_.
   1576 */
   1577enum bfs_result {
   1578	BFS_EINVALIDNODE = -2,
   1579	BFS_EQUEUEFULL = -1,
   1580	BFS_RMATCH = 0,
   1581	BFS_RNOMATCH = 1,
   1582};
   1583
   1584/*
   1585 * bfs_result < 0 means error
   1586 */
   1587static inline bool bfs_error(enum bfs_result res)
   1588{
   1589	return res < 0;
   1590}
   1591
   1592/*
   1593 * DEP_*_BIT in lock_list::dep
   1594 *
   1595 * For dependency @prev -> @next:
   1596 *
   1597 *   SR: @prev is shared reader (->read != 0) and @next is recursive reader
   1598 *       (->read == 2)
   1599 *   ER: @prev is exclusive locker (->read == 0) and @next is recursive reader
   1600 *   SN: @prev is shared reader and @next is non-recursive locker (->read != 2)
   1601 *   EN: @prev is exclusive locker and @next is non-recursive locker
   1602 *
   1603 * Note that we define the value of DEP_*_BITs so that:
   1604 *   bit0 is prev->read == 0
   1605 *   bit1 is next->read != 2
   1606 */
   1607#define DEP_SR_BIT (0 + (0 << 1)) /* 0 */
   1608#define DEP_ER_BIT (1 + (0 << 1)) /* 1 */
   1609#define DEP_SN_BIT (0 + (1 << 1)) /* 2 */
   1610#define DEP_EN_BIT (1 + (1 << 1)) /* 3 */
   1611
   1612#define DEP_SR_MASK (1U << (DEP_SR_BIT))
   1613#define DEP_ER_MASK (1U << (DEP_ER_BIT))
   1614#define DEP_SN_MASK (1U << (DEP_SN_BIT))
   1615#define DEP_EN_MASK (1U << (DEP_EN_BIT))
   1616
   1617static inline unsigned int
   1618__calc_dep_bit(struct held_lock *prev, struct held_lock *next)
   1619{
   1620	return (prev->read == 0) + ((next->read != 2) << 1);
   1621}
   1622
   1623static inline u8 calc_dep(struct held_lock *prev, struct held_lock *next)
   1624{
   1625	return 1U << __calc_dep_bit(prev, next);
   1626}
   1627
   1628/*
   1629 * calculate the dep_bit for backwards edges. We care about whether @prev is
   1630 * shared and whether @next is recursive.
   1631 */
   1632static inline unsigned int
   1633__calc_dep_bitb(struct held_lock *prev, struct held_lock *next)
   1634{
   1635	return (next->read != 2) + ((prev->read == 0) << 1);
   1636}
   1637
   1638static inline u8 calc_depb(struct held_lock *prev, struct held_lock *next)
   1639{
   1640	return 1U << __calc_dep_bitb(prev, next);
   1641}
   1642
   1643/*
   1644 * Initialize a lock_list entry @lock belonging to @class as the root for a BFS
   1645 * search.
   1646 */
   1647static inline void __bfs_init_root(struct lock_list *lock,
   1648				   struct lock_class *class)
   1649{
   1650	lock->class = class;
   1651	lock->parent = NULL;
   1652	lock->only_xr = 0;
   1653}
   1654
   1655/*
   1656 * Initialize a lock_list entry @lock based on a lock acquisition @hlock as the
   1657 * root for a BFS search.
   1658 *
   1659 * ->only_xr of the initial lock node is set to @hlock->read == 2, to make sure
   1660 * that <prev> -> @hlock and @hlock -> <whatever __bfs() found> is not -(*R)->
   1661 * and -(S*)->.
   1662 */
   1663static inline void bfs_init_root(struct lock_list *lock,
   1664				 struct held_lock *hlock)
   1665{
   1666	__bfs_init_root(lock, hlock_class(hlock));
   1667	lock->only_xr = (hlock->read == 2);
   1668}
   1669
   1670/*
   1671 * Similar to bfs_init_root() but initialize the root for backwards BFS.
   1672 *
   1673 * ->only_xr of the initial lock node is set to @hlock->read != 0, to make sure
   1674 * that <next> -> @hlock and @hlock -> <whatever backwards BFS found> is not
   1675 * -(*S)-> and -(R*)-> (reverse order of -(*R)-> and -(S*)->).
   1676 */
   1677static inline void bfs_init_rootb(struct lock_list *lock,
   1678				  struct held_lock *hlock)
   1679{
   1680	__bfs_init_root(lock, hlock_class(hlock));
   1681	lock->only_xr = (hlock->read != 0);
   1682}
   1683
   1684static inline struct lock_list *__bfs_next(struct lock_list *lock, int offset)
   1685{
   1686	if (!lock || !lock->parent)
   1687		return NULL;
   1688
   1689	return list_next_or_null_rcu(get_dep_list(lock->parent, offset),
   1690				     &lock->entry, struct lock_list, entry);
   1691}
   1692
   1693/*
   1694 * Breadth-First Search to find a strong path in the dependency graph.
   1695 *
   1696 * @source_entry: the source of the path we are searching for.
   1697 * @data: data used for the second parameter of @match function
   1698 * @match: match function for the search
   1699 * @target_entry: pointer to the target of a matched path
   1700 * @offset: the offset to struct lock_class to determine whether it is
   1701 *          locks_after or locks_before
   1702 *
   1703 * We may have multiple edges (considering different kinds of dependencies,
   1704 * e.g. ER and SN) between two nodes in the dependency graph. But
   1705 * only the strong dependency path in the graph is relevant to deadlocks. A
   1706 * strong dependency path is a dependency path that doesn't have two adjacent
   1707 * dependencies as -(*R)-> -(S*)->, please see:
   1708 *
   1709 *         Documentation/locking/lockdep-design.rst
   1710 *
   1711 * for more explanation of the definition of strong dependency paths
   1712 *
   1713 * In __bfs(), we only traverse in the strong dependency path:
   1714 *
   1715 *     In lock_list::only_xr, we record whether the previous dependency only
   1716 *     has -(*R)-> in the search, and if it does (prev only has -(*R)->), we
   1717 *     filter out any -(S*)-> in the current dependency and after that, the
   1718 *     ->only_xr is set according to whether we only have -(*R)-> left.
   1719 */
   1720static enum bfs_result __bfs(struct lock_list *source_entry,
   1721			     void *data,
   1722			     bool (*match)(struct lock_list *entry, void *data),
   1723			     bool (*skip)(struct lock_list *entry, void *data),
   1724			     struct lock_list **target_entry,
   1725			     int offset)
   1726{
   1727	struct circular_queue *cq = &lock_cq;
   1728	struct lock_list *lock = NULL;
   1729	struct lock_list *entry;
   1730	struct list_head *head;
   1731	unsigned int cq_depth;
   1732	bool first;
   1733
   1734	lockdep_assert_locked();
   1735
   1736	__cq_init(cq);
   1737	__cq_enqueue(cq, source_entry);
   1738
   1739	while ((lock = __bfs_next(lock, offset)) || (lock = __cq_dequeue(cq))) {
   1740		if (!lock->class)
   1741			return BFS_EINVALIDNODE;
   1742
   1743		/*
   1744		 * Step 1: check whether we already finish on this one.
   1745		 *
   1746		 * If we have visited all the dependencies from this @lock to
   1747		 * others (iow, if we have visited all lock_list entries in
   1748		 * @lock->class->locks_{after,before}) we skip, otherwise go
   1749		 * and visit all the dependencies in the list and mark this
   1750		 * list accessed.
   1751		 */
   1752		if (lock_accessed(lock))
   1753			continue;
   1754		else
   1755			mark_lock_accessed(lock);
   1756
   1757		/*
   1758		 * Step 2: check whether prev dependency and this form a strong
   1759		 *         dependency path.
   1760		 */
   1761		if (lock->parent) { /* Parent exists, check prev dependency */
   1762			u8 dep = lock->dep;
   1763			bool prev_only_xr = lock->parent->only_xr;
   1764
   1765			/*
   1766			 * Mask out all -(S*)-> if we only have *R in previous
   1767			 * step, because -(*R)-> -(S*)-> don't make up a strong
   1768			 * dependency.
   1769			 */
   1770			if (prev_only_xr)
   1771				dep &= ~(DEP_SR_MASK | DEP_SN_MASK);
   1772
   1773			/* If nothing left, we skip */
   1774			if (!dep)
   1775				continue;
   1776
   1777			/* If there are only -(*R)-> left, set that for the next step */
   1778			lock->only_xr = !(dep & (DEP_SN_MASK | DEP_EN_MASK));
   1779		}
   1780
   1781		/*
   1782		 * Step 3: we haven't visited this and there is a strong
   1783		 *         dependency path to this, so check with @match.
   1784		 *         If @skip is provide and returns true, we skip this
   1785		 *         lock (and any path this lock is in).
   1786		 */
   1787		if (skip && skip(lock, data))
   1788			continue;
   1789
   1790		if (match(lock, data)) {
   1791			*target_entry = lock;
   1792			return BFS_RMATCH;
   1793		}
   1794
   1795		/*
   1796		 * Step 4: if not match, expand the path by adding the
   1797		 *         forward or backwards dependencies in the search
   1798		 *
   1799		 */
   1800		first = true;
   1801		head = get_dep_list(lock, offset);
   1802		list_for_each_entry_rcu(entry, head, entry) {
   1803			visit_lock_entry(entry, lock);
   1804
   1805			/*
   1806			 * Note we only enqueue the first of the list into the
   1807			 * queue, because we can always find a sibling
   1808			 * dependency from one (see __bfs_next()), as a result
   1809			 * the space of queue is saved.
   1810			 */
   1811			if (!first)
   1812				continue;
   1813
   1814			first = false;
   1815
   1816			if (__cq_enqueue(cq, entry))
   1817				return BFS_EQUEUEFULL;
   1818
   1819			cq_depth = __cq_get_elem_count(cq);
   1820			if (max_bfs_queue_depth < cq_depth)
   1821				max_bfs_queue_depth = cq_depth;
   1822		}
   1823	}
   1824
   1825	return BFS_RNOMATCH;
   1826}
   1827
   1828static inline enum bfs_result
   1829__bfs_forwards(struct lock_list *src_entry,
   1830	       void *data,
   1831	       bool (*match)(struct lock_list *entry, void *data),
   1832	       bool (*skip)(struct lock_list *entry, void *data),
   1833	       struct lock_list **target_entry)
   1834{
   1835	return __bfs(src_entry, data, match, skip, target_entry,
   1836		     offsetof(struct lock_class, locks_after));
   1837
   1838}
   1839
   1840static inline enum bfs_result
   1841__bfs_backwards(struct lock_list *src_entry,
   1842		void *data,
   1843		bool (*match)(struct lock_list *entry, void *data),
   1844	       bool (*skip)(struct lock_list *entry, void *data),
   1845		struct lock_list **target_entry)
   1846{
   1847	return __bfs(src_entry, data, match, skip, target_entry,
   1848		     offsetof(struct lock_class, locks_before));
   1849
   1850}
   1851
   1852static void print_lock_trace(const struct lock_trace *trace,
   1853			     unsigned int spaces)
   1854{
   1855	stack_trace_print(trace->entries, trace->nr_entries, spaces);
   1856}
   1857
   1858/*
   1859 * Print a dependency chain entry (this is only done when a deadlock
   1860 * has been detected):
   1861 */
   1862static noinline void
   1863print_circular_bug_entry(struct lock_list *target, int depth)
   1864{
   1865	if (debug_locks_silent)
   1866		return;
   1867	printk("\n-> #%u", depth);
   1868	print_lock_name(target->class);
   1869	printk(KERN_CONT ":\n");
   1870	print_lock_trace(target->trace, 6);
   1871}
   1872
   1873static void
   1874print_circular_lock_scenario(struct held_lock *src,
   1875			     struct held_lock *tgt,
   1876			     struct lock_list *prt)
   1877{
   1878	struct lock_class *source = hlock_class(src);
   1879	struct lock_class *target = hlock_class(tgt);
   1880	struct lock_class *parent = prt->class;
   1881
   1882	/*
   1883	 * A direct locking problem where unsafe_class lock is taken
   1884	 * directly by safe_class lock, then all we need to show
   1885	 * is the deadlock scenario, as it is obvious that the
   1886	 * unsafe lock is taken under the safe lock.
   1887	 *
   1888	 * But if there is a chain instead, where the safe lock takes
   1889	 * an intermediate lock (middle_class) where this lock is
   1890	 * not the same as the safe lock, then the lock chain is
   1891	 * used to describe the problem. Otherwise we would need
   1892	 * to show a different CPU case for each link in the chain
   1893	 * from the safe_class lock to the unsafe_class lock.
   1894	 */
   1895	if (parent != source) {
   1896		printk("Chain exists of:\n  ");
   1897		__print_lock_name(source);
   1898		printk(KERN_CONT " --> ");
   1899		__print_lock_name(parent);
   1900		printk(KERN_CONT " --> ");
   1901		__print_lock_name(target);
   1902		printk(KERN_CONT "\n\n");
   1903	}
   1904
   1905	printk(" Possible unsafe locking scenario:\n\n");
   1906	printk("       CPU0                    CPU1\n");
   1907	printk("       ----                    ----\n");
   1908	printk("  lock(");
   1909	__print_lock_name(target);
   1910	printk(KERN_CONT ");\n");
   1911	printk("                               lock(");
   1912	__print_lock_name(parent);
   1913	printk(KERN_CONT ");\n");
   1914	printk("                               lock(");
   1915	__print_lock_name(target);
   1916	printk(KERN_CONT ");\n");
   1917	printk("  lock(");
   1918	__print_lock_name(source);
   1919	printk(KERN_CONT ");\n");
   1920	printk("\n *** DEADLOCK ***\n\n");
   1921}
   1922
   1923/*
   1924 * When a circular dependency is detected, print the
   1925 * header first:
   1926 */
   1927static noinline void
   1928print_circular_bug_header(struct lock_list *entry, unsigned int depth,
   1929			struct held_lock *check_src,
   1930			struct held_lock *check_tgt)
   1931{
   1932	struct task_struct *curr = current;
   1933
   1934	if (debug_locks_silent)
   1935		return;
   1936
   1937	pr_warn("\n");
   1938	pr_warn("======================================================\n");
   1939	pr_warn("WARNING: possible circular locking dependency detected\n");
   1940	print_kernel_ident();
   1941	pr_warn("------------------------------------------------------\n");
   1942	pr_warn("%s/%d is trying to acquire lock:\n",
   1943		curr->comm, task_pid_nr(curr));
   1944	print_lock(check_src);
   1945
   1946	pr_warn("\nbut task is already holding lock:\n");
   1947
   1948	print_lock(check_tgt);
   1949	pr_warn("\nwhich lock already depends on the new lock.\n\n");
   1950	pr_warn("\nthe existing dependency chain (in reverse order) is:\n");
   1951
   1952	print_circular_bug_entry(entry, depth);
   1953}
   1954
   1955/*
   1956 * We are about to add A -> B into the dependency graph, and in __bfs() a
   1957 * strong dependency path A -> .. -> B is found: hlock_class equals
   1958 * entry->class.
   1959 *
   1960 * If A -> .. -> B can replace A -> B in any __bfs() search (means the former
   1961 * is _stronger_ than or equal to the latter), we consider A -> B as redundant.
   1962 * For example if A -> .. -> B is -(EN)-> (i.e. A -(E*)-> .. -(*N)-> B), and A
   1963 * -> B is -(ER)-> or -(EN)->, then we don't need to add A -> B into the
   1964 * dependency graph, as any strong path ..-> A -> B ->.. we can get with
   1965 * having dependency A -> B, we could already get a equivalent path ..-> A ->
   1966 * .. -> B -> .. with A -> .. -> B. Therefore A -> B is redundant.
   1967 *
   1968 * We need to make sure both the start and the end of A -> .. -> B is not
   1969 * weaker than A -> B. For the start part, please see the comment in
   1970 * check_redundant(). For the end part, we need:
   1971 *
   1972 * Either
   1973 *
   1974 *     a) A -> B is -(*R)-> (everything is not weaker than that)
   1975 *
   1976 * or
   1977 *
   1978 *     b) A -> .. -> B is -(*N)-> (nothing is stronger than this)
   1979 *
   1980 */
   1981static inline bool hlock_equal(struct lock_list *entry, void *data)
   1982{
   1983	struct held_lock *hlock = (struct held_lock *)data;
   1984
   1985	return hlock_class(hlock) == entry->class && /* Found A -> .. -> B */
   1986	       (hlock->read == 2 ||  /* A -> B is -(*R)-> */
   1987		!entry->only_xr); /* A -> .. -> B is -(*N)-> */
   1988}
   1989
   1990/*
   1991 * We are about to add B -> A into the dependency graph, and in __bfs() a
   1992 * strong dependency path A -> .. -> B is found: hlock_class equals
   1993 * entry->class.
   1994 *
   1995 * We will have a deadlock case (conflict) if A -> .. -> B -> A is a strong
   1996 * dependency cycle, that means:
   1997 *
   1998 * Either
   1999 *
   2000 *     a) B -> A is -(E*)->
   2001 *
   2002 * or
   2003 *
   2004 *     b) A -> .. -> B is -(*N)-> (i.e. A -> .. -(*N)-> B)
   2005 *
   2006 * as then we don't have -(*R)-> -(S*)-> in the cycle.
   2007 */
   2008static inline bool hlock_conflict(struct lock_list *entry, void *data)
   2009{
   2010	struct held_lock *hlock = (struct held_lock *)data;
   2011
   2012	return hlock_class(hlock) == entry->class && /* Found A -> .. -> B */
   2013	       (hlock->read == 0 || /* B -> A is -(E*)-> */
   2014		!entry->only_xr); /* A -> .. -> B is -(*N)-> */
   2015}
   2016
   2017static noinline void print_circular_bug(struct lock_list *this,
   2018				struct lock_list *target,
   2019				struct held_lock *check_src,
   2020				struct held_lock *check_tgt)
   2021{
   2022	struct task_struct *curr = current;
   2023	struct lock_list *parent;
   2024	struct lock_list *first_parent;
   2025	int depth;
   2026
   2027	if (!debug_locks_off_graph_unlock() || debug_locks_silent)
   2028		return;
   2029
   2030	this->trace = save_trace();
   2031	if (!this->trace)
   2032		return;
   2033
   2034	depth = get_lock_depth(target);
   2035
   2036	print_circular_bug_header(target, depth, check_src, check_tgt);
   2037
   2038	parent = get_lock_parent(target);
   2039	first_parent = parent;
   2040
   2041	while (parent) {
   2042		print_circular_bug_entry(parent, --depth);
   2043		parent = get_lock_parent(parent);
   2044	}
   2045
   2046	printk("\nother info that might help us debug this:\n\n");
   2047	print_circular_lock_scenario(check_src, check_tgt,
   2048				     first_parent);
   2049
   2050	lockdep_print_held_locks(curr);
   2051
   2052	printk("\nstack backtrace:\n");
   2053	dump_stack();
   2054}
   2055
   2056static noinline void print_bfs_bug(int ret)
   2057{
   2058	if (!debug_locks_off_graph_unlock())
   2059		return;
   2060
   2061	/*
   2062	 * Breadth-first-search failed, graph got corrupted?
   2063	 */
   2064	WARN(1, "lockdep bfs error:%d\n", ret);
   2065}
   2066
   2067static bool noop_count(struct lock_list *entry, void *data)
   2068{
   2069	(*(unsigned long *)data)++;
   2070	return false;
   2071}
   2072
   2073static unsigned long __lockdep_count_forward_deps(struct lock_list *this)
   2074{
   2075	unsigned long  count = 0;
   2076	struct lock_list *target_entry;
   2077
   2078	__bfs_forwards(this, (void *)&count, noop_count, NULL, &target_entry);
   2079
   2080	return count;
   2081}
   2082unsigned long lockdep_count_forward_deps(struct lock_class *class)
   2083{
   2084	unsigned long ret, flags;
   2085	struct lock_list this;
   2086
   2087	__bfs_init_root(&this, class);
   2088
   2089	raw_local_irq_save(flags);
   2090	lockdep_lock();
   2091	ret = __lockdep_count_forward_deps(&this);
   2092	lockdep_unlock();
   2093	raw_local_irq_restore(flags);
   2094
   2095	return ret;
   2096}
   2097
   2098static unsigned long __lockdep_count_backward_deps(struct lock_list *this)
   2099{
   2100	unsigned long  count = 0;
   2101	struct lock_list *target_entry;
   2102
   2103	__bfs_backwards(this, (void *)&count, noop_count, NULL, &target_entry);
   2104
   2105	return count;
   2106}
   2107
   2108unsigned long lockdep_count_backward_deps(struct lock_class *class)
   2109{
   2110	unsigned long ret, flags;
   2111	struct lock_list this;
   2112
   2113	__bfs_init_root(&this, class);
   2114
   2115	raw_local_irq_save(flags);
   2116	lockdep_lock();
   2117	ret = __lockdep_count_backward_deps(&this);
   2118	lockdep_unlock();
   2119	raw_local_irq_restore(flags);
   2120
   2121	return ret;
   2122}
   2123
   2124/*
   2125 * Check that the dependency graph starting at <src> can lead to
   2126 * <target> or not.
   2127 */
   2128static noinline enum bfs_result
   2129check_path(struct held_lock *target, struct lock_list *src_entry,
   2130	   bool (*match)(struct lock_list *entry, void *data),
   2131	   bool (*skip)(struct lock_list *entry, void *data),
   2132	   struct lock_list **target_entry)
   2133{
   2134	enum bfs_result ret;
   2135
   2136	ret = __bfs_forwards(src_entry, target, match, skip, target_entry);
   2137
   2138	if (unlikely(bfs_error(ret)))
   2139		print_bfs_bug(ret);
   2140
   2141	return ret;
   2142}
   2143
   2144/*
   2145 * Prove that the dependency graph starting at <src> can not
   2146 * lead to <target>. If it can, there is a circle when adding
   2147 * <target> -> <src> dependency.
   2148 *
   2149 * Print an error and return BFS_RMATCH if it does.
   2150 */
   2151static noinline enum bfs_result
   2152check_noncircular(struct held_lock *src, struct held_lock *target,
   2153		  struct lock_trace **const trace)
   2154{
   2155	enum bfs_result ret;
   2156	struct lock_list *target_entry;
   2157	struct lock_list src_entry;
   2158
   2159	bfs_init_root(&src_entry, src);
   2160
   2161	debug_atomic_inc(nr_cyclic_checks);
   2162
   2163	ret = check_path(target, &src_entry, hlock_conflict, NULL, &target_entry);
   2164
   2165	if (unlikely(ret == BFS_RMATCH)) {
   2166		if (!*trace) {
   2167			/*
   2168			 * If save_trace fails here, the printing might
   2169			 * trigger a WARN but because of the !nr_entries it
   2170			 * should not do bad things.
   2171			 */
   2172			*trace = save_trace();
   2173		}
   2174
   2175		print_circular_bug(&src_entry, target_entry, src, target);
   2176	}
   2177
   2178	return ret;
   2179}
   2180
   2181#ifdef CONFIG_TRACE_IRQFLAGS
   2182
   2183/*
   2184 * Forwards and backwards subgraph searching, for the purposes of
   2185 * proving that two subgraphs can be connected by a new dependency
   2186 * without creating any illegal irq-safe -> irq-unsafe lock dependency.
   2187 *
   2188 * A irq safe->unsafe deadlock happens with the following conditions:
   2189 *
   2190 * 1) We have a strong dependency path A -> ... -> B
   2191 *
   2192 * 2) and we have ENABLED_IRQ usage of B and USED_IN_IRQ usage of A, therefore
   2193 *    irq can create a new dependency B -> A (consider the case that a holder
   2194 *    of B gets interrupted by an irq whose handler will try to acquire A).
   2195 *
   2196 * 3) the dependency circle A -> ... -> B -> A we get from 1) and 2) is a
   2197 *    strong circle:
   2198 *
   2199 *      For the usage bits of B:
   2200 *        a) if A -> B is -(*N)->, then B -> A could be any type, so any
   2201 *           ENABLED_IRQ usage suffices.
   2202 *        b) if A -> B is -(*R)->, then B -> A must be -(E*)->, so only
   2203 *           ENABLED_IRQ_*_READ usage suffices.
   2204 *
   2205 *      For the usage bits of A:
   2206 *        c) if A -> B is -(E*)->, then B -> A could be any type, so any
   2207 *           USED_IN_IRQ usage suffices.
   2208 *        d) if A -> B is -(S*)->, then B -> A must be -(*N)->, so only
   2209 *           USED_IN_IRQ_*_READ usage suffices.
   2210 */
   2211
   2212/*
   2213 * There is a strong dependency path in the dependency graph: A -> B, and now
   2214 * we need to decide which usage bit of A should be accumulated to detect
   2215 * safe->unsafe bugs.
   2216 *
   2217 * Note that usage_accumulate() is used in backwards search, so ->only_xr
   2218 * stands for whether A -> B only has -(S*)-> (in this case ->only_xr is true).
   2219 *
   2220 * As above, if only_xr is false, which means A -> B has -(E*)-> dependency
   2221 * path, any usage of A should be considered. Otherwise, we should only
   2222 * consider _READ usage.
   2223 */
   2224static inline bool usage_accumulate(struct lock_list *entry, void *mask)
   2225{
   2226	if (!entry->only_xr)
   2227		*(unsigned long *)mask |= entry->class->usage_mask;
   2228	else /* Mask out _READ usage bits */
   2229		*(unsigned long *)mask |= (entry->class->usage_mask & LOCKF_IRQ);
   2230
   2231	return false;
   2232}
   2233
   2234/*
   2235 * There is a strong dependency path in the dependency graph: A -> B, and now
   2236 * we need to decide which usage bit of B conflicts with the usage bits of A,
   2237 * i.e. which usage bit of B may introduce safe->unsafe deadlocks.
   2238 *
   2239 * As above, if only_xr is false, which means A -> B has -(*N)-> dependency
   2240 * path, any usage of B should be considered. Otherwise, we should only
   2241 * consider _READ usage.
   2242 */
   2243static inline bool usage_match(struct lock_list *entry, void *mask)
   2244{
   2245	if (!entry->only_xr)
   2246		return !!(entry->class->usage_mask & *(unsigned long *)mask);
   2247	else /* Mask out _READ usage bits */
   2248		return !!((entry->class->usage_mask & LOCKF_IRQ) & *(unsigned long *)mask);
   2249}
   2250
   2251static inline bool usage_skip(struct lock_list *entry, void *mask)
   2252{
   2253	/*
   2254	 * Skip local_lock() for irq inversion detection.
   2255	 *
   2256	 * For !RT, local_lock() is not a real lock, so it won't carry any
   2257	 * dependency.
   2258	 *
   2259	 * For RT, an irq inversion happens when we have lock A and B, and on
   2260	 * some CPU we can have:
   2261	 *
   2262	 *	lock(A);
   2263	 *	<interrupted>
   2264	 *	  lock(B);
   2265	 *
   2266	 * where lock(B) cannot sleep, and we have a dependency B -> ... -> A.
   2267	 *
   2268	 * Now we prove local_lock() cannot exist in that dependency. First we
   2269	 * have the observation for any lock chain L1 -> ... -> Ln, for any
   2270	 * 1 <= i <= n, Li.inner_wait_type <= L1.inner_wait_type, otherwise
   2271	 * wait context check will complain. And since B is not a sleep lock,
   2272	 * therefore B.inner_wait_type >= 2, and since the inner_wait_type of
   2273	 * local_lock() is 3, which is greater than 2, therefore there is no
   2274	 * way the local_lock() exists in the dependency B -> ... -> A.
   2275	 *
   2276	 * As a result, we will skip local_lock(), when we search for irq
   2277	 * inversion bugs.
   2278	 */
   2279	if (entry->class->lock_type == LD_LOCK_PERCPU) {
   2280		if (DEBUG_LOCKS_WARN_ON(entry->class->wait_type_inner < LD_WAIT_CONFIG))
   2281			return false;
   2282
   2283		return true;
   2284	}
   2285
   2286	return false;
   2287}
   2288
   2289/*
   2290 * Find a node in the forwards-direction dependency sub-graph starting
   2291 * at @root->class that matches @bit.
   2292 *
   2293 * Return BFS_MATCH if such a node exists in the subgraph, and put that node
   2294 * into *@target_entry.
   2295 */
   2296static enum bfs_result
   2297find_usage_forwards(struct lock_list *root, unsigned long usage_mask,
   2298			struct lock_list **target_entry)
   2299{
   2300	enum bfs_result result;
   2301
   2302	debug_atomic_inc(nr_find_usage_forwards_checks);
   2303
   2304	result = __bfs_forwards(root, &usage_mask, usage_match, usage_skip, target_entry);
   2305
   2306	return result;
   2307}
   2308
   2309/*
   2310 * Find a node in the backwards-direction dependency sub-graph starting
   2311 * at @root->class that matches @bit.
   2312 */
   2313static enum bfs_result
   2314find_usage_backwards(struct lock_list *root, unsigned long usage_mask,
   2315			struct lock_list **target_entry)
   2316{
   2317	enum bfs_result result;
   2318
   2319	debug_atomic_inc(nr_find_usage_backwards_checks);
   2320
   2321	result = __bfs_backwards(root, &usage_mask, usage_match, usage_skip, target_entry);
   2322
   2323	return result;
   2324}
   2325
   2326static void print_lock_class_header(struct lock_class *class, int depth)
   2327{
   2328	int bit;
   2329
   2330	printk("%*s->", depth, "");
   2331	print_lock_name(class);
   2332#ifdef CONFIG_DEBUG_LOCKDEP
   2333	printk(KERN_CONT " ops: %lu", debug_class_ops_read(class));
   2334#endif
   2335	printk(KERN_CONT " {\n");
   2336
   2337	for (bit = 0; bit < LOCK_TRACE_STATES; bit++) {
   2338		if (class->usage_mask & (1 << bit)) {
   2339			int len = depth;
   2340
   2341			len += printk("%*s   %s", depth, "", usage_str[bit]);
   2342			len += printk(KERN_CONT " at:\n");
   2343			print_lock_trace(class->usage_traces[bit], len);
   2344		}
   2345	}
   2346	printk("%*s }\n", depth, "");
   2347
   2348	printk("%*s ... key      at: [<%px>] %pS\n",
   2349		depth, "", class->key, class->key);
   2350}
   2351
   2352/*
   2353 * Dependency path printing:
   2354 *
   2355 * After BFS we get a lock dependency path (linked via ->parent of lock_list),
   2356 * printing out each lock in the dependency path will help on understanding how
   2357 * the deadlock could happen. Here are some details about dependency path
   2358 * printing:
   2359 *
   2360 * 1)	A lock_list can be either forwards or backwards for a lock dependency,
   2361 * 	for a lock dependency A -> B, there are two lock_lists:
   2362 *
   2363 * 	a)	lock_list in the ->locks_after list of A, whose ->class is B and
   2364 * 		->links_to is A. In this case, we can say the lock_list is
   2365 * 		"A -> B" (forwards case).
   2366 *
   2367 * 	b)	lock_list in the ->locks_before list of B, whose ->class is A
   2368 * 		and ->links_to is B. In this case, we can say the lock_list is
   2369 * 		"B <- A" (bacwards case).
   2370 *
   2371 * 	The ->trace of both a) and b) point to the call trace where B was
   2372 * 	acquired with A held.
   2373 *
   2374 * 2)	A "helper" lock_list is introduced during BFS, this lock_list doesn't
   2375 * 	represent a certain lock dependency, it only provides an initial entry
   2376 * 	for BFS. For example, BFS may introduce a "helper" lock_list whose
   2377 * 	->class is A, as a result BFS will search all dependencies starting with
   2378 * 	A, e.g. A -> B or A -> C.
   2379 *
   2380 * 	The notation of a forwards helper lock_list is like "-> A", which means
   2381 * 	we should search the forwards dependencies starting with "A", e.g A -> B
   2382 * 	or A -> C.
   2383 *
   2384 * 	The notation of a bacwards helper lock_list is like "<- B", which means
   2385 * 	we should search the backwards dependencies ending with "B", e.g.
   2386 * 	B <- A or B <- C.
   2387 */
   2388
   2389/*
   2390 * printk the shortest lock dependencies from @root to @leaf in reverse order.
   2391 *
   2392 * We have a lock dependency path as follow:
   2393 *
   2394 *    @root                                                                 @leaf
   2395 *      |                                                                     |
   2396 *      V                                                                     V
   2397 *	          ->parent                                   ->parent
   2398 * | lock_list | <--------- | lock_list | ... | lock_list  | <--------- | lock_list |
   2399 * |    -> L1  |            | L1 -> L2  | ... |Ln-2 -> Ln-1|            | Ln-1 -> Ln|
   2400 *
   2401 * , so it's natural that we start from @leaf and print every ->class and
   2402 * ->trace until we reach the @root.
   2403 */
   2404static void __used
   2405print_shortest_lock_dependencies(struct lock_list *leaf,
   2406				 struct lock_list *root)
   2407{
   2408	struct lock_list *entry = leaf;
   2409	int depth;
   2410
   2411	/*compute depth from generated tree by BFS*/
   2412	depth = get_lock_depth(leaf);
   2413
   2414	do {
   2415		print_lock_class_header(entry->class, depth);
   2416		printk("%*s ... acquired at:\n", depth, "");
   2417		print_lock_trace(entry->trace, 2);
   2418		printk("\n");
   2419
   2420		if (depth == 0 && (entry != root)) {
   2421			printk("lockdep:%s bad path found in chain graph\n", __func__);
   2422			break;
   2423		}
   2424
   2425		entry = get_lock_parent(entry);
   2426		depth--;
   2427	} while (entry && (depth >= 0));
   2428}
   2429
   2430/*
   2431 * printk the shortest lock dependencies from @leaf to @root.
   2432 *
   2433 * We have a lock dependency path (from a backwards search) as follow:
   2434 *
   2435 *    @leaf                                                                 @root
   2436 *      |                                                                     |
   2437 *      V                                                                     V
   2438 *	          ->parent                                   ->parent
   2439 * | lock_list | ---------> | lock_list | ... | lock_list  | ---------> | lock_list |
   2440 * | L2 <- L1  |            | L3 <- L2  | ... | Ln <- Ln-1 |            |    <- Ln  |
   2441 *
   2442 * , so when we iterate from @leaf to @root, we actually print the lock
   2443 * dependency path L1 -> L2 -> .. -> Ln in the non-reverse order.
   2444 *
   2445 * Another thing to notice here is that ->class of L2 <- L1 is L1, while the
   2446 * ->trace of L2 <- L1 is the call trace of L2, in fact we don't have the call
   2447 * trace of L1 in the dependency path, which is alright, because most of the
   2448 * time we can figure out where L1 is held from the call trace of L2.
   2449 */
   2450static void __used
   2451print_shortest_lock_dependencies_backwards(struct lock_list *leaf,
   2452					   struct lock_list *root)
   2453{
   2454	struct lock_list *entry = leaf;
   2455	const struct lock_trace *trace = NULL;
   2456	int depth;
   2457
   2458	/*compute depth from generated tree by BFS*/
   2459	depth = get_lock_depth(leaf);
   2460
   2461	do {
   2462		print_lock_class_header(entry->class, depth);
   2463		if (trace) {
   2464			printk("%*s ... acquired at:\n", depth, "");
   2465			print_lock_trace(trace, 2);
   2466			printk("\n");
   2467		}
   2468
   2469		/*
   2470		 * Record the pointer to the trace for the next lock_list
   2471		 * entry, see the comments for the function.
   2472		 */
   2473		trace = entry->trace;
   2474
   2475		if (depth == 0 && (entry != root)) {
   2476			printk("lockdep:%s bad path found in chain graph\n", __func__);
   2477			break;
   2478		}
   2479
   2480		entry = get_lock_parent(entry);
   2481		depth--;
   2482	} while (entry && (depth >= 0));
   2483}
   2484
   2485static void
   2486print_irq_lock_scenario(struct lock_list *safe_entry,
   2487			struct lock_list *unsafe_entry,
   2488			struct lock_class *prev_class,
   2489			struct lock_class *next_class)
   2490{
   2491	struct lock_class *safe_class = safe_entry->class;
   2492	struct lock_class *unsafe_class = unsafe_entry->class;
   2493	struct lock_class *middle_class = prev_class;
   2494
   2495	if (middle_class == safe_class)
   2496		middle_class = next_class;
   2497
   2498	/*
   2499	 * A direct locking problem where unsafe_class lock is taken
   2500	 * directly by safe_class lock, then all we need to show
   2501	 * is the deadlock scenario, as it is obvious that the
   2502	 * unsafe lock is taken under the safe lock.
   2503	 *
   2504	 * But if there is a chain instead, where the safe lock takes
   2505	 * an intermediate lock (middle_class) where this lock is
   2506	 * not the same as the safe lock, then the lock chain is
   2507	 * used to describe the problem. Otherwise we would need
   2508	 * to show a different CPU case for each link in the chain
   2509	 * from the safe_class lock to the unsafe_class lock.
   2510	 */
   2511	if (middle_class != unsafe_class) {
   2512		printk("Chain exists of:\n  ");
   2513		__print_lock_name(safe_class);
   2514		printk(KERN_CONT " --> ");
   2515		__print_lock_name(middle_class);
   2516		printk(KERN_CONT " --> ");
   2517		__print_lock_name(unsafe_class);
   2518		printk(KERN_CONT "\n\n");
   2519	}
   2520
   2521	printk(" Possible interrupt unsafe locking scenario:\n\n");
   2522	printk("       CPU0                    CPU1\n");
   2523	printk("       ----                    ----\n");
   2524	printk("  lock(");
   2525	__print_lock_name(unsafe_class);
   2526	printk(KERN_CONT ");\n");
   2527	printk("                               local_irq_disable();\n");
   2528	printk("                               lock(");
   2529	__print_lock_name(safe_class);
   2530	printk(KERN_CONT ");\n");
   2531	printk("                               lock(");
   2532	__print_lock_name(middle_class);
   2533	printk(KERN_CONT ");\n");
   2534	printk("  <Interrupt>\n");
   2535	printk("    lock(");
   2536	__print_lock_name(safe_class);
   2537	printk(KERN_CONT ");\n");
   2538	printk("\n *** DEADLOCK ***\n\n");
   2539}
   2540
   2541static void
   2542print_bad_irq_dependency(struct task_struct *curr,
   2543			 struct lock_list *prev_root,
   2544			 struct lock_list *next_root,
   2545			 struct lock_list *backwards_entry,
   2546			 struct lock_list *forwards_entry,
   2547			 struct held_lock *prev,
   2548			 struct held_lock *next,
   2549			 enum lock_usage_bit bit1,
   2550			 enum lock_usage_bit bit2,
   2551			 const char *irqclass)
   2552{
   2553	if (!debug_locks_off_graph_unlock() || debug_locks_silent)
   2554		return;
   2555
   2556	pr_warn("\n");
   2557	pr_warn("=====================================================\n");
   2558	pr_warn("WARNING: %s-safe -> %s-unsafe lock order detected\n",
   2559		irqclass, irqclass);
   2560	print_kernel_ident();
   2561	pr_warn("-----------------------------------------------------\n");
   2562	pr_warn("%s/%d [HC%u[%lu]:SC%u[%lu]:HE%u:SE%u] is trying to acquire:\n",
   2563		curr->comm, task_pid_nr(curr),
   2564		lockdep_hardirq_context(), hardirq_count() >> HARDIRQ_SHIFT,
   2565		curr->softirq_context, softirq_count() >> SOFTIRQ_SHIFT,
   2566		lockdep_hardirqs_enabled(),
   2567		curr->softirqs_enabled);
   2568	print_lock(next);
   2569
   2570	pr_warn("\nand this task is already holding:\n");
   2571	print_lock(prev);
   2572	pr_warn("which would create a new lock dependency:\n");
   2573	print_lock_name(hlock_class(prev));
   2574	pr_cont(" ->");
   2575	print_lock_name(hlock_class(next));
   2576	pr_cont("\n");
   2577
   2578	pr_warn("\nbut this new dependency connects a %s-irq-safe lock:\n",
   2579		irqclass);
   2580	print_lock_name(backwards_entry->class);
   2581	pr_warn("\n... which became %s-irq-safe at:\n", irqclass);
   2582
   2583	print_lock_trace(backwards_entry->class->usage_traces[bit1], 1);
   2584
   2585	pr_warn("\nto a %s-irq-unsafe lock:\n", irqclass);
   2586	print_lock_name(forwards_entry->class);
   2587	pr_warn("\n... which became %s-irq-unsafe at:\n", irqclass);
   2588	pr_warn("...");
   2589
   2590	print_lock_trace(forwards_entry->class->usage_traces[bit2], 1);
   2591
   2592	pr_warn("\nother info that might help us debug this:\n\n");
   2593	print_irq_lock_scenario(backwards_entry, forwards_entry,
   2594				hlock_class(prev), hlock_class(next));
   2595
   2596	lockdep_print_held_locks(curr);
   2597
   2598	pr_warn("\nthe dependencies between %s-irq-safe lock and the holding lock:\n", irqclass);
   2599	print_shortest_lock_dependencies_backwards(backwards_entry, prev_root);
   2600
   2601	pr_warn("\nthe dependencies between the lock to be acquired");
   2602	pr_warn(" and %s-irq-unsafe lock:\n", irqclass);
   2603	next_root->trace = save_trace();
   2604	if (!next_root->trace)
   2605		return;
   2606	print_shortest_lock_dependencies(forwards_entry, next_root);
   2607
   2608	pr_warn("\nstack backtrace:\n");
   2609	dump_stack();
   2610}
   2611
   2612static const char *state_names[] = {
   2613#define LOCKDEP_STATE(__STATE) \
   2614	__stringify(__STATE),
   2615#include "lockdep_states.h"
   2616#undef LOCKDEP_STATE
   2617};
   2618
   2619static const char *state_rnames[] = {
   2620#define LOCKDEP_STATE(__STATE) \
   2621	__stringify(__STATE)"-READ",
   2622#include "lockdep_states.h"
   2623#undef LOCKDEP_STATE
   2624};
   2625
   2626static inline const char *state_name(enum lock_usage_bit bit)
   2627{
   2628	if (bit & LOCK_USAGE_READ_MASK)
   2629		return state_rnames[bit >> LOCK_USAGE_DIR_MASK];
   2630	else
   2631		return state_names[bit >> LOCK_USAGE_DIR_MASK];
   2632}
   2633
   2634/*
   2635 * The bit number is encoded like:
   2636 *
   2637 *  bit0: 0 exclusive, 1 read lock
   2638 *  bit1: 0 used in irq, 1 irq enabled
   2639 *  bit2-n: state
   2640 */
   2641static int exclusive_bit(int new_bit)
   2642{
   2643	int state = new_bit & LOCK_USAGE_STATE_MASK;
   2644	int dir = new_bit & LOCK_USAGE_DIR_MASK;
   2645
   2646	/*
   2647	 * keep state, bit flip the direction and strip read.
   2648	 */
   2649	return state | (dir ^ LOCK_USAGE_DIR_MASK);
   2650}
   2651
   2652/*
   2653 * Observe that when given a bitmask where each bitnr is encoded as above, a
   2654 * right shift of the mask transforms the individual bitnrs as -1 and
   2655 * conversely, a left shift transforms into +1 for the individual bitnrs.
   2656 *
   2657 * So for all bits whose number have LOCK_ENABLED_* set (bitnr1 == 1), we can
   2658 * create the mask with those bit numbers using LOCK_USED_IN_* (bitnr1 == 0)
   2659 * instead by subtracting the bit number by 2, or shifting the mask right by 2.
   2660 *
   2661 * Similarly, bitnr1 == 0 becomes bitnr1 == 1 by adding 2, or shifting left 2.
   2662 *
   2663 * So split the mask (note that LOCKF_ENABLED_IRQ_ALL|LOCKF_USED_IN_IRQ_ALL is
   2664 * all bits set) and recompose with bitnr1 flipped.
   2665 */
   2666static unsigned long invert_dir_mask(unsigned long mask)
   2667{
   2668	unsigned long excl = 0;
   2669
   2670	/* Invert dir */
   2671	excl |= (mask & LOCKF_ENABLED_IRQ_ALL) >> LOCK_USAGE_DIR_MASK;
   2672	excl |= (mask & LOCKF_USED_IN_IRQ_ALL) << LOCK_USAGE_DIR_MASK;
   2673
   2674	return excl;
   2675}
   2676
   2677/*
   2678 * Note that a LOCK_ENABLED_IRQ_*_READ usage and a LOCK_USED_IN_IRQ_*_READ
   2679 * usage may cause deadlock too, for example:
   2680 *
   2681 * P1				P2
   2682 * <irq disabled>
   2683 * write_lock(l1);		<irq enabled>
   2684 *				read_lock(l2);
   2685 * write_lock(l2);
   2686 * 				<in irq>
   2687 * 				read_lock(l1);
   2688 *
   2689 * , in above case, l1 will be marked as LOCK_USED_IN_IRQ_HARDIRQ_READ and l2
   2690 * will marked as LOCK_ENABLE_IRQ_HARDIRQ_READ, and this is a possible
   2691 * deadlock.
   2692 *
   2693 * In fact, all of the following cases may cause deadlocks:
   2694 *
   2695 * 	 LOCK_USED_IN_IRQ_* -> LOCK_ENABLED_IRQ_*
   2696 * 	 LOCK_USED_IN_IRQ_*_READ -> LOCK_ENABLED_IRQ_*
   2697 * 	 LOCK_USED_IN_IRQ_* -> LOCK_ENABLED_IRQ_*_READ
   2698 * 	 LOCK_USED_IN_IRQ_*_READ -> LOCK_ENABLED_IRQ_*_READ
   2699 *
   2700 * As a result, to calculate the "exclusive mask", first we invert the
   2701 * direction (USED_IN/ENABLED) of the original mask, and 1) for all bits with
   2702 * bitnr0 set (LOCK_*_READ), add those with bitnr0 cleared (LOCK_*). 2) for all
   2703 * bits with bitnr0 cleared (LOCK_*_READ), add those with bitnr0 set (LOCK_*).
   2704 */
   2705static unsigned long exclusive_mask(unsigned long mask)
   2706{
   2707	unsigned long excl = invert_dir_mask(mask);
   2708
   2709	excl |= (excl & LOCKF_IRQ_READ) >> LOCK_USAGE_READ_MASK;
   2710	excl |= (excl & LOCKF_IRQ) << LOCK_USAGE_READ_MASK;
   2711
   2712	return excl;
   2713}
   2714
   2715/*
   2716 * Retrieve the _possible_ original mask to which @mask is
   2717 * exclusive. Ie: this is the opposite of exclusive_mask().
   2718 * Note that 2 possible original bits can match an exclusive
   2719 * bit: one has LOCK_USAGE_READ_MASK set, the other has it
   2720 * cleared. So both are returned for each exclusive bit.
   2721 */
   2722static unsigned long original_mask(unsigned long mask)
   2723{
   2724	unsigned long excl = invert_dir_mask(mask);
   2725
   2726	/* Include read in existing usages */
   2727	excl |= (excl & LOCKF_IRQ_READ) >> LOCK_USAGE_READ_MASK;
   2728	excl |= (excl & LOCKF_IRQ) << LOCK_USAGE_READ_MASK;
   2729
   2730	return excl;
   2731}
   2732
   2733/*
   2734 * Find the first pair of bit match between an original
   2735 * usage mask and an exclusive usage mask.
   2736 */
   2737static int find_exclusive_match(unsigned long mask,
   2738				unsigned long excl_mask,
   2739				enum lock_usage_bit *bitp,
   2740				enum lock_usage_bit *excl_bitp)
   2741{
   2742	int bit, excl, excl_read;
   2743
   2744	for_each_set_bit(bit, &mask, LOCK_USED) {
   2745		/*
   2746		 * exclusive_bit() strips the read bit, however,
   2747		 * LOCK_ENABLED_IRQ_*_READ may cause deadlocks too, so we need
   2748		 * to search excl | LOCK_USAGE_READ_MASK as well.
   2749		 */
   2750		excl = exclusive_bit(bit);
   2751		excl_read = excl | LOCK_USAGE_READ_MASK;
   2752		if (excl_mask & lock_flag(excl)) {
   2753			*bitp = bit;
   2754			*excl_bitp = excl;
   2755			return 0;
   2756		} else if (excl_mask & lock_flag(excl_read)) {
   2757			*bitp = bit;
   2758			*excl_bitp = excl_read;
   2759			return 0;
   2760		}
   2761	}
   2762	return -1;
   2763}
   2764
   2765/*
   2766 * Prove that the new dependency does not connect a hardirq-safe(-read)
   2767 * lock with a hardirq-unsafe lock - to achieve this we search
   2768 * the backwards-subgraph starting at <prev>, and the
   2769 * forwards-subgraph starting at <next>:
   2770 */
   2771static int check_irq_usage(struct task_struct *curr, struct held_lock *prev,
   2772			   struct held_lock *next)
   2773{
   2774	unsigned long usage_mask = 0, forward_mask, backward_mask;
   2775	enum lock_usage_bit forward_bit = 0, backward_bit = 0;
   2776	struct lock_list *target_entry1;
   2777	struct lock_list *target_entry;
   2778	struct lock_list this, that;
   2779	enum bfs_result ret;
   2780
   2781	/*
   2782	 * Step 1: gather all hard/soft IRQs usages backward in an
   2783	 * accumulated usage mask.
   2784	 */
   2785	bfs_init_rootb(&this, prev);
   2786
   2787	ret = __bfs_backwards(&this, &usage_mask, usage_accumulate, usage_skip, NULL);
   2788	if (bfs_error(ret)) {
   2789		print_bfs_bug(ret);
   2790		return 0;
   2791	}
   2792
   2793	usage_mask &= LOCKF_USED_IN_IRQ_ALL;
   2794	if (!usage_mask)
   2795		return 1;
   2796
   2797	/*
   2798	 * Step 2: find exclusive uses forward that match the previous
   2799	 * backward accumulated mask.
   2800	 */
   2801	forward_mask = exclusive_mask(usage_mask);
   2802
   2803	bfs_init_root(&that, next);
   2804
   2805	ret = find_usage_forwards(&that, forward_mask, &target_entry1);
   2806	if (bfs_error(ret)) {
   2807		print_bfs_bug(ret);
   2808		return 0;
   2809	}
   2810	if (ret == BFS_RNOMATCH)
   2811		return 1;
   2812
   2813	/*
   2814	 * Step 3: we found a bad match! Now retrieve a lock from the backward
   2815	 * list whose usage mask matches the exclusive usage mask from the
   2816	 * lock found on the forward list.
   2817	 *
   2818	 * Note, we should only keep the LOCKF_ENABLED_IRQ_ALL bits, considering
   2819	 * the follow case:
   2820	 *
   2821	 * When trying to add A -> B to the graph, we find that there is a
   2822	 * hardirq-safe L, that L -> ... -> A, and another hardirq-unsafe M,
   2823	 * that B -> ... -> M. However M is **softirq-safe**, if we use exact
   2824	 * invert bits of M's usage_mask, we will find another lock N that is
   2825	 * **softirq-unsafe** and N -> ... -> A, however N -> .. -> M will not
   2826	 * cause a inversion deadlock.
   2827	 */
   2828	backward_mask = original_mask(target_entry1->class->usage_mask & LOCKF_ENABLED_IRQ_ALL);
   2829
   2830	ret = find_usage_backwards(&this, backward_mask, &target_entry);
   2831	if (bfs_error(ret)) {
   2832		print_bfs_bug(ret);
   2833		return 0;
   2834	}
   2835	if (DEBUG_LOCKS_WARN_ON(ret == BFS_RNOMATCH))
   2836		return 1;
   2837
   2838	/*
   2839	 * Step 4: narrow down to a pair of incompatible usage bits
   2840	 * and report it.
   2841	 */
   2842	ret = find_exclusive_match(target_entry->class->usage_mask,
   2843				   target_entry1->class->usage_mask,
   2844				   &backward_bit, &forward_bit);
   2845	if (DEBUG_LOCKS_WARN_ON(ret == -1))
   2846		return 1;
   2847
   2848	print_bad_irq_dependency(curr, &this, &that,
   2849				 target_entry, target_entry1,
   2850				 prev, next,
   2851				 backward_bit, forward_bit,
   2852				 state_name(backward_bit));
   2853
   2854	return 0;
   2855}
   2856
   2857#else
   2858
   2859static inline int check_irq_usage(struct task_struct *curr,
   2860				  struct held_lock *prev, struct held_lock *next)
   2861{
   2862	return 1;
   2863}
   2864
   2865static inline bool usage_skip(struct lock_list *entry, void *mask)
   2866{
   2867	return false;
   2868}
   2869
   2870#endif /* CONFIG_TRACE_IRQFLAGS */
   2871
   2872#ifdef CONFIG_LOCKDEP_SMALL
   2873/*
   2874 * Check that the dependency graph starting at <src> can lead to
   2875 * <target> or not. If it can, <src> -> <target> dependency is already
   2876 * in the graph.
   2877 *
   2878 * Return BFS_RMATCH if it does, or BFS_RNOMATCH if it does not, return BFS_E* if
   2879 * any error appears in the bfs search.
   2880 */
   2881static noinline enum bfs_result
   2882check_redundant(struct held_lock *src, struct held_lock *target)
   2883{
   2884	enum bfs_result ret;
   2885	struct lock_list *target_entry;
   2886	struct lock_list src_entry;
   2887
   2888	bfs_init_root(&src_entry, src);
   2889	/*
   2890	 * Special setup for check_redundant().
   2891	 *
   2892	 * To report redundant, we need to find a strong dependency path that
   2893	 * is equal to or stronger than <src> -> <target>. So if <src> is E,
   2894	 * we need to let __bfs() only search for a path starting at a -(E*)->,
   2895	 * we achieve this by setting the initial node's ->only_xr to true in
   2896	 * that case. And if <prev> is S, we set initial ->only_xr to false
   2897	 * because both -(S*)-> (equal) and -(E*)-> (stronger) are redundant.
   2898	 */
   2899	src_entry.only_xr = src->read == 0;
   2900
   2901	debug_atomic_inc(nr_redundant_checks);
   2902
   2903	/*
   2904	 * Note: we skip local_lock() for redundant check, because as the
   2905	 * comment in usage_skip(), A -> local_lock() -> B and A -> B are not
   2906	 * the same.
   2907	 */
   2908	ret = check_path(target, &src_entry, hlock_equal, usage_skip, &target_entry);
   2909
   2910	if (ret == BFS_RMATCH)
   2911		debug_atomic_inc(nr_redundant);
   2912
   2913	return ret;
   2914}
   2915
   2916#else
   2917
   2918static inline enum bfs_result
   2919check_redundant(struct held_lock *src, struct held_lock *target)
   2920{
   2921	return BFS_RNOMATCH;
   2922}
   2923
   2924#endif
   2925
   2926static void inc_chains(int irq_context)
   2927{
   2928	if (irq_context & LOCK_CHAIN_HARDIRQ_CONTEXT)
   2929		nr_hardirq_chains++;
   2930	else if (irq_context & LOCK_CHAIN_SOFTIRQ_CONTEXT)
   2931		nr_softirq_chains++;
   2932	else
   2933		nr_process_chains++;
   2934}
   2935
   2936static void dec_chains(int irq_context)
   2937{
   2938	if (irq_context & LOCK_CHAIN_HARDIRQ_CONTEXT)
   2939		nr_hardirq_chains--;
   2940	else if (irq_context & LOCK_CHAIN_SOFTIRQ_CONTEXT)
   2941		nr_softirq_chains--;
   2942	else
   2943		nr_process_chains--;
   2944}
   2945
   2946static void
   2947print_deadlock_scenario(struct held_lock *nxt, struct held_lock *prv)
   2948{
   2949	struct lock_class *next = hlock_class(nxt);
   2950	struct lock_class *prev = hlock_class(prv);
   2951
   2952	printk(" Possible unsafe locking scenario:\n\n");
   2953	printk("       CPU0\n");
   2954	printk("       ----\n");
   2955	printk("  lock(");
   2956	__print_lock_name(prev);
   2957	printk(KERN_CONT ");\n");
   2958	printk("  lock(");
   2959	__print_lock_name(next);
   2960	printk(KERN_CONT ");\n");
   2961	printk("\n *** DEADLOCK ***\n\n");
   2962	printk(" May be due to missing lock nesting notation\n\n");
   2963}
   2964
   2965static void
   2966print_deadlock_bug(struct task_struct *curr, struct held_lock *prev,
   2967		   struct held_lock *next)
   2968{
   2969	if (!debug_locks_off_graph_unlock() || debug_locks_silent)
   2970		return;
   2971
   2972	pr_warn("\n");
   2973	pr_warn("============================================\n");
   2974	pr_warn("WARNING: possible recursive locking detected\n");
   2975	print_kernel_ident();
   2976	pr_warn("--------------------------------------------\n");
   2977	pr_warn("%s/%d is trying to acquire lock:\n",
   2978		curr->comm, task_pid_nr(curr));
   2979	print_lock(next);
   2980	pr_warn("\nbut task is already holding lock:\n");
   2981	print_lock(prev);
   2982
   2983	pr_warn("\nother info that might help us debug this:\n");
   2984	print_deadlock_scenario(next, prev);
   2985	lockdep_print_held_locks(curr);
   2986
   2987	pr_warn("\nstack backtrace:\n");
   2988	dump_stack();
   2989}
   2990
   2991/*
   2992 * Check whether we are holding such a class already.
   2993 *
   2994 * (Note that this has to be done separately, because the graph cannot
   2995 * detect such classes of deadlocks.)
   2996 *
   2997 * Returns: 0 on deadlock detected, 1 on OK, 2 if another lock with the same
   2998 * lock class is held but nest_lock is also held, i.e. we rely on the
   2999 * nest_lock to avoid the deadlock.
   3000 */
   3001static int
   3002check_deadlock(struct task_struct *curr, struct held_lock *next)
   3003{
   3004	struct held_lock *prev;
   3005	struct held_lock *nest = NULL;
   3006	int i;
   3007
   3008	for (i = 0; i < curr->lockdep_depth; i++) {
   3009		prev = curr->held_locks + i;
   3010
   3011		if (prev->instance == next->nest_lock)
   3012			nest = prev;
   3013
   3014		if (hlock_class(prev) != hlock_class(next))
   3015			continue;
   3016
   3017		/*
   3018		 * Allow read-after-read recursion of the same
   3019		 * lock class (i.e. read_lock(lock)+read_lock(lock)):
   3020		 */
   3021		if ((next->read == 2) && prev->read)
   3022			continue;
   3023
   3024		/*
   3025		 * We're holding the nest_lock, which serializes this lock's
   3026		 * nesting behaviour.
   3027		 */
   3028		if (nest)
   3029			return 2;
   3030
   3031		print_deadlock_bug(curr, prev, next);
   3032		return 0;
   3033	}
   3034	return 1;
   3035}
   3036
   3037/*
   3038 * There was a chain-cache miss, and we are about to add a new dependency
   3039 * to a previous lock. We validate the following rules:
   3040 *
   3041 *  - would the adding of the <prev> -> <next> dependency create a
   3042 *    circular dependency in the graph? [== circular deadlock]
   3043 *
   3044 *  - does the new prev->next dependency connect any hardirq-safe lock
   3045 *    (in the full backwards-subgraph starting at <prev>) with any
   3046 *    hardirq-unsafe lock (in the full forwards-subgraph starting at
   3047 *    <next>)? [== illegal lock inversion with hardirq contexts]
   3048 *
   3049 *  - does the new prev->next dependency connect any softirq-safe lock
   3050 *    (in the full backwards-subgraph starting at <prev>) with any
   3051 *    softirq-unsafe lock (in the full forwards-subgraph starting at
   3052 *    <next>)? [== illegal lock inversion with softirq contexts]
   3053 *
   3054 * any of these scenarios could lead to a deadlock.
   3055 *
   3056 * Then if all the validations pass, we add the forwards and backwards
   3057 * dependency.
   3058 */
   3059static int
   3060check_prev_add(struct task_struct *curr, struct held_lock *prev,
   3061	       struct held_lock *next, u16 distance,
   3062	       struct lock_trace **const trace)
   3063{
   3064	struct lock_list *entry;
   3065	enum bfs_result ret;
   3066
   3067	if (!hlock_class(prev)->key || !hlock_class(next)->key) {
   3068		/*
   3069		 * The warning statements below may trigger a use-after-free
   3070		 * of the class name. It is better to trigger a use-after free
   3071		 * and to have the class name most of the time instead of not
   3072		 * having the class name available.
   3073		 */
   3074		WARN_ONCE(!debug_locks_silent && !hlock_class(prev)->key,
   3075			  "Detected use-after-free of lock class %px/%s\n",
   3076			  hlock_class(prev),
   3077			  hlock_class(prev)->name);
   3078		WARN_ONCE(!debug_locks_silent && !hlock_class(next)->key,
   3079			  "Detected use-after-free of lock class %px/%s\n",
   3080			  hlock_class(next),
   3081			  hlock_class(next)->name);
   3082		return 2;
   3083	}
   3084
   3085	/*
   3086	 * Prove that the new <prev> -> <next> dependency would not
   3087	 * create a circular dependency in the graph. (We do this by
   3088	 * a breadth-first search into the graph starting at <next>,
   3089	 * and check whether we can reach <prev>.)
   3090	 *
   3091	 * The search is limited by the size of the circular queue (i.e.,
   3092	 * MAX_CIRCULAR_QUEUE_SIZE) which keeps track of a breadth of nodes
   3093	 * in the graph whose neighbours are to be checked.
   3094	 */
   3095	ret = check_noncircular(next, prev, trace);
   3096	if (unlikely(bfs_error(ret) || ret == BFS_RMATCH))
   3097		return 0;
   3098
   3099	if (!check_irq_usage(curr, prev, next))
   3100		return 0;
   3101
   3102	/*
   3103	 * Is the <prev> -> <next> dependency already present?
   3104	 *
   3105	 * (this may occur even though this is a new chain: consider
   3106	 *  e.g. the L1 -> L2 -> L3 -> L4 and the L5 -> L1 -> L2 -> L3
   3107	 *  chains - the second one will be new, but L1 already has
   3108	 *  L2 added to its dependency list, due to the first chain.)
   3109	 */
   3110	list_for_each_entry(entry, &hlock_class(prev)->locks_after, entry) {
   3111		if (entry->class == hlock_class(next)) {
   3112			if (distance == 1)
   3113				entry->distance = 1;
   3114			entry->dep |= calc_dep(prev, next);
   3115
   3116			/*
   3117			 * Also, update the reverse dependency in @next's
   3118			 * ->locks_before list.
   3119			 *
   3120			 *  Here we reuse @entry as the cursor, which is fine
   3121			 *  because we won't go to the next iteration of the
   3122			 *  outer loop:
   3123			 *
   3124			 *  For normal cases, we return in the inner loop.
   3125			 *
   3126			 *  If we fail to return, we have inconsistency, i.e.
   3127			 *  <prev>::locks_after contains <next> while
   3128			 *  <next>::locks_before doesn't contain <prev>. In
   3129			 *  that case, we return after the inner and indicate
   3130			 *  something is wrong.
   3131			 */
   3132			list_for_each_entry(entry, &hlock_class(next)->locks_before, entry) {
   3133				if (entry->class == hlock_class(prev)) {
   3134					if (distance == 1)
   3135						entry->distance = 1;
   3136					entry->dep |= calc_depb(prev, next);
   3137					return 1;
   3138				}
   3139			}
   3140
   3141			/* <prev> is not found in <next>::locks_before */
   3142			return 0;
   3143		}
   3144	}
   3145
   3146	/*
   3147	 * Is the <prev> -> <next> link redundant?
   3148	 */
   3149	ret = check_redundant(prev, next);
   3150	if (bfs_error(ret))
   3151		return 0;
   3152	else if (ret == BFS_RMATCH)
   3153		return 2;
   3154
   3155	if (!*trace) {
   3156		*trace = save_trace();
   3157		if (!*trace)
   3158			return 0;
   3159	}
   3160
   3161	/*
   3162	 * Ok, all validations passed, add the new lock
   3163	 * to the previous lock's dependency list:
   3164	 */
   3165	ret = add_lock_to_list(hlock_class(next), hlock_class(prev),
   3166			       &hlock_class(prev)->locks_after, distance,
   3167			       calc_dep(prev, next), *trace);
   3168
   3169	if (!ret)
   3170		return 0;
   3171
   3172	ret = add_lock_to_list(hlock_class(prev), hlock_class(next),
   3173			       &hlock_class(next)->locks_before, distance,
   3174			       calc_depb(prev, next), *trace);
   3175	if (!ret)
   3176		return 0;
   3177
   3178	return 2;
   3179}
   3180
   3181/*
   3182 * Add the dependency to all directly-previous locks that are 'relevant'.
   3183 * The ones that are relevant are (in increasing distance from curr):
   3184 * all consecutive trylock entries and the final non-trylock entry - or
   3185 * the end of this context's lock-chain - whichever comes first.
   3186 */
   3187static int
   3188check_prevs_add(struct task_struct *curr, struct held_lock *next)
   3189{
   3190	struct lock_trace *trace = NULL;
   3191	int depth = curr->lockdep_depth;
   3192	struct held_lock *hlock;
   3193
   3194	/*
   3195	 * Debugging checks.
   3196	 *
   3197	 * Depth must not be zero for a non-head lock:
   3198	 */
   3199	if (!depth)
   3200		goto out_bug;
   3201	/*
   3202	 * At least two relevant locks must exist for this
   3203	 * to be a head:
   3204	 */
   3205	if (curr->held_locks[depth].irq_context !=
   3206			curr->held_locks[depth-1].irq_context)
   3207		goto out_bug;
   3208
   3209	for (;;) {
   3210		u16 distance = curr->lockdep_depth - depth + 1;
   3211		hlock = curr->held_locks + depth - 1;
   3212
   3213		if (hlock->check) {
   3214			int ret = check_prev_add(curr, hlock, next, distance, &trace);
   3215			if (!ret)
   3216				return 0;
   3217
   3218			/*
   3219			 * Stop after the first non-trylock entry,
   3220			 * as non-trylock entries have added their
   3221			 * own direct dependencies already, so this
   3222			 * lock is connected to them indirectly:
   3223			 */
   3224			if (!hlock->trylock)
   3225				break;
   3226		}
   3227
   3228		depth--;
   3229		/*
   3230		 * End of lock-stack?
   3231		 */
   3232		if (!depth)
   3233			break;
   3234		/*
   3235		 * Stop the search if we cross into another context:
   3236		 */
   3237		if (curr->held_locks[depth].irq_context !=
   3238				curr->held_locks[depth-1].irq_context)
   3239			break;
   3240	}
   3241	return 1;
   3242out_bug:
   3243	if (!debug_locks_off_graph_unlock())
   3244		return 0;
   3245
   3246	/*
   3247	 * Clearly we all shouldn't be here, but since we made it we
   3248	 * can reliable say we messed up our state. See the above two
   3249	 * gotos for reasons why we could possibly end up here.
   3250	 */
   3251	WARN_ON(1);
   3252
   3253	return 0;
   3254}
   3255
   3256struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS];
   3257static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS);
   3258static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS];
   3259unsigned long nr_zapped_lock_chains;
   3260unsigned int nr_free_chain_hlocks;	/* Free chain_hlocks in buckets */
   3261unsigned int nr_lost_chain_hlocks;	/* Lost chain_hlocks */
   3262unsigned int nr_large_chain_blocks;	/* size > MAX_CHAIN_BUCKETS */
   3263
   3264/*
   3265 * The first 2 chain_hlocks entries in the chain block in the bucket
   3266 * list contains the following meta data:
   3267 *
   3268 *   entry[0]:
   3269 *     Bit    15 - always set to 1 (it is not a class index)
   3270 *     Bits 0-14 - upper 15 bits of the next block index
   3271 *   entry[1]    - lower 16 bits of next block index
   3272 *
   3273 * A next block index of all 1 bits means it is the end of the list.
   3274 *
   3275 * On the unsized bucket (bucket-0), the 3rd and 4th entries contain
   3276 * the chain block size:
   3277 *
   3278 *   entry[2] - upper 16 bits of the chain block size
   3279 *   entry[3] - lower 16 bits of the chain block size
   3280 */
   3281#define MAX_CHAIN_BUCKETS	16
   3282#define CHAIN_BLK_FLAG		(1U << 15)
   3283#define CHAIN_BLK_LIST_END	0xFFFFU
   3284
   3285static int chain_block_buckets[MAX_CHAIN_BUCKETS];
   3286
   3287static inline int size_to_bucket(int size)
   3288{
   3289	if (size > MAX_CHAIN_BUCKETS)
   3290		return 0;
   3291
   3292	return size - 1;
   3293}
   3294
   3295/*
   3296 * Iterate all the chain blocks in a bucket.
   3297 */
   3298#define for_each_chain_block(bucket, prev, curr)		\
   3299	for ((prev) = -1, (curr) = chain_block_buckets[bucket];	\
   3300	     (curr) >= 0;					\
   3301	     (prev) = (curr), (curr) = chain_block_next(curr))
   3302
   3303/*
   3304 * next block or -1
   3305 */
   3306static inline int chain_block_next(int offset)
   3307{
   3308	int next = chain_hlocks[offset];
   3309
   3310	WARN_ON_ONCE(!(next & CHAIN_BLK_FLAG));
   3311
   3312	if (next == CHAIN_BLK_LIST_END)
   3313		return -1;
   3314
   3315	next &= ~CHAIN_BLK_FLAG;
   3316	next <<= 16;
   3317	next |= chain_hlocks[offset + 1];
   3318
   3319	return next;
   3320}
   3321
   3322/*
   3323 * bucket-0 only
   3324 */
   3325static inline int chain_block_size(int offset)
   3326{
   3327	return (chain_hlocks[offset + 2] << 16) | chain_hlocks[offset + 3];
   3328}
   3329
   3330static inline void init_chain_block(int offset, int next, int bucket, int size)
   3331{
   3332	chain_hlocks[offset] = (next >> 16) | CHAIN_BLK_FLAG;
   3333	chain_hlocks[offset + 1] = (u16)next;
   3334
   3335	if (size && !bucket) {
   3336		chain_hlocks[offset + 2] = size >> 16;
   3337		chain_hlocks[offset + 3] = (u16)size;
   3338	}
   3339}
   3340
   3341static inline void add_chain_block(int offset, int size)
   3342{
   3343	int bucket = size_to_bucket(size);
   3344	int next = chain_block_buckets[bucket];
   3345	int prev, curr;
   3346
   3347	if (unlikely(size < 2)) {
   3348		/*
   3349		 * We can't store single entries on the freelist. Leak them.
   3350		 *
   3351		 * One possible way out would be to uniquely mark them, other
   3352		 * than with CHAIN_BLK_FLAG, such that we can recover them when
   3353		 * the block before it is re-added.
   3354		 */
   3355		if (size)
   3356			nr_lost_chain_hlocks++;
   3357		return;
   3358	}
   3359
   3360	nr_free_chain_hlocks += size;
   3361	if (!bucket) {
   3362		nr_large_chain_blocks++;
   3363
   3364		/*
   3365		 * Variable sized, sort large to small.
   3366		 */
   3367		for_each_chain_block(0, prev, curr) {
   3368			if (size >= chain_block_size(curr))
   3369				break;
   3370		}
   3371		init_chain_block(offset, curr, 0, size);
   3372		if (prev < 0)
   3373			chain_block_buckets[0] = offset;
   3374		else
   3375			init_chain_block(prev, offset, 0, 0);
   3376		return;
   3377	}
   3378	/*
   3379	 * Fixed size, add to head.
   3380	 */
   3381	init_chain_block(offset, next, bucket, size);
   3382	chain_block_buckets[bucket] = offset;
   3383}
   3384
   3385/*
   3386 * Only the first block in the list can be deleted.
   3387 *
   3388 * For the variable size bucket[0], the first block (the largest one) is
   3389 * returned, broken up and put back into the pool. So if a chain block of
   3390 * length > MAX_CHAIN_BUCKETS is ever used and zapped, it will just be
   3391 * queued up after the primordial chain block and never be used until the
   3392 * hlock entries in the primordial chain block is almost used up. That
   3393 * causes fragmentation and reduce allocation efficiency. That can be
   3394 * monitored by looking at the "large chain blocks" number in lockdep_stats.
   3395 */
   3396static inline void del_chain_block(int bucket, int size, int next)
   3397{
   3398	nr_free_chain_hlocks -= size;
   3399	chain_block_buckets[bucket] = next;
   3400
   3401	if (!bucket)
   3402		nr_large_chain_blocks--;
   3403}
   3404
   3405static void init_chain_block_buckets(void)
   3406{
   3407	int i;
   3408
   3409	for (i = 0; i < MAX_CHAIN_BUCKETS; i++)
   3410		chain_block_buckets[i] = -1;
   3411
   3412	add_chain_block(0, ARRAY_SIZE(chain_hlocks));
   3413}
   3414
   3415/*
   3416 * Return offset of a chain block of the right size or -1 if not found.
   3417 *
   3418 * Fairly simple worst-fit allocator with the addition of a number of size
   3419 * specific free lists.
   3420 */
   3421static int alloc_chain_hlocks(int req)
   3422{
   3423	int bucket, curr, size;
   3424
   3425	/*
   3426	 * We rely on the MSB to act as an escape bit to denote freelist
   3427	 * pointers. Make sure this bit isn't set in 'normal' class_idx usage.
   3428	 */
   3429	BUILD_BUG_ON((MAX_LOCKDEP_KEYS-1) & CHAIN_BLK_FLAG);
   3430
   3431	init_data_structures_once();
   3432
   3433	if (nr_free_chain_hlocks < req)
   3434		return -1;
   3435
   3436	/*
   3437	 * We require a minimum of 2 (u16) entries to encode a freelist
   3438	 * 'pointer'.
   3439	 */
   3440	req = max(req, 2);
   3441	bucket = size_to_bucket(req);
   3442	curr = chain_block_buckets[bucket];
   3443
   3444	if (bucket) {
   3445		if (curr >= 0) {
   3446			del_chain_block(bucket, req, chain_block_next(curr));
   3447			return curr;
   3448		}
   3449		/* Try bucket 0 */
   3450		curr = chain_block_buckets[0];
   3451	}
   3452
   3453	/*
   3454	 * The variable sized freelist is sorted by size; the first entry is
   3455	 * the largest. Use it if it fits.
   3456	 */
   3457	if (curr >= 0) {
   3458		size = chain_block_size(curr);
   3459		if (likely(size >= req)) {
   3460			del_chain_block(0, size, chain_block_next(curr));
   3461			add_chain_block(curr + req, size - req);
   3462			return curr;
   3463		}
   3464	}
   3465
   3466	/*
   3467	 * Last resort, split a block in a larger sized bucket.
   3468	 */
   3469	for (size = MAX_CHAIN_BUCKETS; size > req; size--) {
   3470		bucket = size_to_bucket(size);
   3471		curr = chain_block_buckets[bucket];
   3472		if (curr < 0)
   3473			continue;
   3474
   3475		del_chain_block(bucket, size, chain_block_next(curr));
   3476		add_chain_block(curr + req, size - req);
   3477		return curr;
   3478	}
   3479
   3480	return -1;
   3481}
   3482
   3483static inline void free_chain_hlocks(int base, int size)
   3484{
   3485	add_chain_block(base, max(size, 2));
   3486}
   3487
   3488struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i)
   3489{
   3490	u16 chain_hlock = chain_hlocks[chain->base + i];
   3491	unsigned int class_idx = chain_hlock_class_idx(chain_hlock);
   3492
   3493	return lock_classes + class_idx;
   3494}
   3495
   3496/*
   3497 * Returns the index of the first held_lock of the current chain
   3498 */
   3499static inline int get_first_held_lock(struct task_struct *curr,
   3500					struct held_lock *hlock)
   3501{
   3502	int i;
   3503	struct held_lock *hlock_curr;
   3504
   3505	for (i = curr->lockdep_depth - 1; i >= 0; i--) {
   3506		hlock_curr = curr->held_locks + i;
   3507		if (hlock_curr->irq_context != hlock->irq_context)
   3508			break;
   3509
   3510	}
   3511
   3512	return ++i;
   3513}
   3514
   3515#ifdef CONFIG_DEBUG_LOCKDEP
   3516/*
   3517 * Returns the next chain_key iteration
   3518 */
   3519static u64 print_chain_key_iteration(u16 hlock_id, u64 chain_key)
   3520{
   3521	u64 new_chain_key = iterate_chain_key(chain_key, hlock_id);
   3522
   3523	printk(" hlock_id:%d -> chain_key:%016Lx",
   3524		(unsigned int)hlock_id,
   3525		(unsigned long long)new_chain_key);
   3526	return new_chain_key;
   3527}
   3528
   3529static void
   3530print_chain_keys_held_locks(struct task_struct *curr, struct held_lock *hlock_next)
   3531{
   3532	struct held_lock *hlock;
   3533	u64 chain_key = INITIAL_CHAIN_KEY;
   3534	int depth = curr->lockdep_depth;
   3535	int i = get_first_held_lock(curr, hlock_next);
   3536
   3537	printk("depth: %u (irq_context %u)\n", depth - i + 1,
   3538		hlock_next->irq_context);
   3539	for (; i < depth; i++) {
   3540		hlock = curr->held_locks + i;
   3541		chain_key = print_chain_key_iteration(hlock_id(hlock), chain_key);
   3542
   3543		print_lock(hlock);
   3544	}
   3545
   3546	print_chain_key_iteration(hlock_id(hlock_next), chain_key);
   3547	print_lock(hlock_next);
   3548}
   3549
   3550static void print_chain_keys_chain(struct lock_chain *chain)
   3551{
   3552	int i;
   3553	u64 chain_key = INITIAL_CHAIN_KEY;
   3554	u16 hlock_id;
   3555
   3556	printk("depth: %u\n", chain->depth);
   3557	for (i = 0; i < chain->depth; i++) {
   3558		hlock_id = chain_hlocks[chain->base + i];
   3559		chain_key = print_chain_key_iteration(hlock_id, chain_key);
   3560
   3561		print_lock_name(lock_classes + chain_hlock_class_idx(hlock_id));
   3562		printk("\n");
   3563	}
   3564}
   3565
   3566static void print_collision(struct task_struct *curr,
   3567			struct held_lock *hlock_next,
   3568			struct lock_chain *chain)
   3569{
   3570	pr_warn("\n");
   3571	pr_warn("============================\n");
   3572	pr_warn("WARNING: chain_key collision\n");
   3573	print_kernel_ident();
   3574	pr_warn("----------------------------\n");
   3575	pr_warn("%s/%d: ", current->comm, task_pid_nr(current));
   3576	pr_warn("Hash chain already cached but the contents don't match!\n");
   3577
   3578	pr_warn("Held locks:");
   3579	print_chain_keys_held_locks(curr, hlock_next);
   3580
   3581	pr_warn("Locks in cached chain:");
   3582	print_chain_keys_chain(chain);
   3583
   3584	pr_warn("\nstack backtrace:\n");
   3585	dump_stack();
   3586}
   3587#endif
   3588
   3589/*
   3590 * Checks whether the chain and the current held locks are consistent
   3591 * in depth and also in content. If they are not it most likely means
   3592 * that there was a collision during the calculation of the chain_key.
   3593 * Returns: 0 not passed, 1 passed
   3594 */
   3595static int check_no_collision(struct task_struct *curr,
   3596			struct held_lock *hlock,
   3597			struct lock_chain *chain)
   3598{
   3599#ifdef CONFIG_DEBUG_LOCKDEP
   3600	int i, j, id;
   3601
   3602	i = get_first_held_lock(curr, hlock);
   3603
   3604	if (DEBUG_LOCKS_WARN_ON(chain->depth != curr->lockdep_depth - (i - 1))) {
   3605		print_collision(curr, hlock, chain);
   3606		return 0;
   3607	}
   3608
   3609	for (j = 0; j < chain->depth - 1; j++, i++) {
   3610		id = hlock_id(&curr->held_locks[i]);
   3611
   3612		if (DEBUG_LOCKS_WARN_ON(chain_hlocks[chain->base + j] != id)) {
   3613			print_collision(curr, hlock, chain);
   3614			return 0;
   3615		}
   3616	}
   3617#endif
   3618	return 1;
   3619}
   3620
   3621/*
   3622 * Given an index that is >= -1, return the index of the next lock chain.
   3623 * Return -2 if there is no next lock chain.
   3624 */
   3625long lockdep_next_lockchain(long i)
   3626{
   3627	i = find_next_bit(lock_chains_in_use, ARRAY_SIZE(lock_chains), i + 1);
   3628	return i < ARRAY_SIZE(lock_chains) ? i : -2;
   3629}
   3630
   3631unsigned long lock_chain_count(void)
   3632{
   3633	return bitmap_weight(lock_chains_in_use, ARRAY_SIZE(lock_chains));
   3634}
   3635
   3636/* Must be called with the graph lock held. */
   3637static struct lock_chain *alloc_lock_chain(void)
   3638{
   3639	int idx = find_first_zero_bit(lock_chains_in_use,
   3640				      ARRAY_SIZE(lock_chains));
   3641
   3642	if (unlikely(idx >= ARRAY_SIZE(lock_chains)))
   3643		return NULL;
   3644	__set_bit(idx, lock_chains_in_use);
   3645	return lock_chains + idx;
   3646}
   3647
   3648/*
   3649 * Adds a dependency chain into chain hashtable. And must be called with
   3650 * graph_lock held.
   3651 *
   3652 * Return 0 if fail, and graph_lock is released.
   3653 * Return 1 if succeed, with graph_lock held.
   3654 */
   3655static inline int add_chain_cache(struct task_struct *curr,
   3656				  struct held_lock *hlock,
   3657				  u64 chain_key)
   3658{
   3659	struct hlist_head *hash_head = chainhashentry(chain_key);
   3660	struct lock_chain *chain;
   3661	int i, j;
   3662
   3663	/*
   3664	 * The caller must hold the graph lock, ensure we've got IRQs
   3665	 * disabled to make this an IRQ-safe lock.. for recursion reasons
   3666	 * lockdep won't complain about its own locking errors.
   3667	 */
   3668	if (lockdep_assert_locked())
   3669		return 0;
   3670
   3671	chain = alloc_lock_chain();
   3672	if (!chain) {
   3673		if (!debug_locks_off_graph_unlock())
   3674			return 0;
   3675
   3676		print_lockdep_off("BUG: MAX_LOCKDEP_CHAINS too low!");
   3677		dump_stack();
   3678		return 0;
   3679	}
   3680	chain->chain_key = chain_key;
   3681	chain->irq_context = hlock->irq_context;
   3682	i = get_first_held_lock(curr, hlock);
   3683	chain->depth = curr->lockdep_depth + 1 - i;
   3684
   3685	BUILD_BUG_ON((1UL << 24) <= ARRAY_SIZE(chain_hlocks));
   3686	BUILD_BUG_ON((1UL << 6)  <= ARRAY_SIZE(curr->held_locks));
   3687	BUILD_BUG_ON((1UL << 8*sizeof(chain_hlocks[0])) <= ARRAY_SIZE(lock_classes));
   3688
   3689	j = alloc_chain_hlocks(chain->depth);
   3690	if (j < 0) {
   3691		if (!debug_locks_off_graph_unlock())
   3692			return 0;
   3693
   3694		print_lockdep_off("BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!");
   3695		dump_stack();
   3696		return 0;
   3697	}
   3698
   3699	chain->base = j;
   3700	for (j = 0; j < chain->depth - 1; j++, i++) {
   3701		int lock_id = hlock_id(curr->held_locks + i);
   3702
   3703		chain_hlocks[chain->base + j] = lock_id;
   3704	}
   3705	chain_hlocks[chain->base + j] = hlock_id(hlock);
   3706	hlist_add_head_rcu(&chain->entry, hash_head);
   3707	debug_atomic_inc(chain_lookup_misses);
   3708	inc_chains(chain->irq_context);
   3709
   3710	return 1;
   3711}
   3712
   3713/*
   3714 * Look up a dependency chain. Must be called with either the graph lock or
   3715 * the RCU read lock held.
   3716 */
   3717static inline struct lock_chain *lookup_chain_cache(u64 chain_key)
   3718{
   3719	struct hlist_head *hash_head = chainhashentry(chain_key);
   3720	struct lock_chain *chain;
   3721
   3722	hlist_for_each_entry_rcu(chain, hash_head, entry) {
   3723		if (READ_ONCE(chain->chain_key) == chain_key) {
   3724			debug_atomic_inc(chain_lookup_hits);
   3725			return chain;
   3726		}
   3727	}
   3728	return NULL;
   3729}
   3730
   3731/*
   3732 * If the key is not present yet in dependency chain cache then
   3733 * add it and return 1 - in this case the new dependency chain is
   3734 * validated. If the key is already hashed, return 0.
   3735 * (On return with 1 graph_lock is held.)
   3736 */
   3737static inline int lookup_chain_cache_add(struct task_struct *curr,
   3738					 struct held_lock *hlock,
   3739					 u64 chain_key)
   3740{
   3741	struct lock_class *class = hlock_class(hlock);
   3742	struct lock_chain *chain = lookup_chain_cache(chain_key);
   3743
   3744	if (chain) {
   3745cache_hit:
   3746		if (!check_no_collision(curr, hlock, chain))
   3747			return 0;
   3748
   3749		if (very_verbose(class)) {
   3750			printk("\nhash chain already cached, key: "
   3751					"%016Lx tail class: [%px] %s\n",
   3752					(unsigned long long)chain_key,
   3753					class->key, class->name);
   3754		}
   3755
   3756		return 0;
   3757	}
   3758
   3759	if (very_verbose(class)) {
   3760		printk("\nnew hash chain, key: %016Lx tail class: [%px] %s\n",
   3761			(unsigned long long)chain_key, class->key, class->name);
   3762	}
   3763
   3764	if (!graph_lock())
   3765		return 0;
   3766
   3767	/*
   3768	 * We have to walk the chain again locked - to avoid duplicates:
   3769	 */
   3770	chain = lookup_chain_cache(chain_key);
   3771	if (chain) {
   3772		graph_unlock();
   3773		goto cache_hit;
   3774	}
   3775
   3776	if (!add_chain_cache(curr, hlock, chain_key))
   3777		return 0;
   3778
   3779	return 1;
   3780}
   3781
   3782static int validate_chain(struct task_struct *curr,
   3783			  struct held_lock *hlock,
   3784			  int chain_head, u64 chain_key)
   3785{
   3786	/*
   3787	 * Trylock needs to maintain the stack of held locks, but it
   3788	 * does not add new dependencies, because trylock can be done
   3789	 * in any order.
   3790	 *
   3791	 * We look up the chain_key and do the O(N^2) check and update of
   3792	 * the dependencies only if this is a new dependency chain.
   3793	 * (If lookup_chain_cache_add() return with 1 it acquires
   3794	 * graph_lock for us)
   3795	 */
   3796	if (!hlock->trylock && hlock->check &&
   3797	    lookup_chain_cache_add(curr, hlock, chain_key)) {
   3798		/*
   3799		 * Check whether last held lock:
   3800		 *
   3801		 * - is irq-safe, if this lock is irq-unsafe
   3802		 * - is softirq-safe, if this lock is hardirq-unsafe
   3803		 *
   3804		 * And check whether the new lock's dependency graph
   3805		 * could lead back to the previous lock:
   3806		 *
   3807		 * - within the current held-lock stack
   3808		 * - across our accumulated lock dependency records
   3809		 *
   3810		 * any of these scenarios could lead to a deadlock.
   3811		 */
   3812		/*
   3813		 * The simple case: does the current hold the same lock
   3814		 * already?
   3815		 */
   3816		int ret = check_deadlock(curr, hlock);
   3817
   3818		if (!ret)
   3819			return 0;
   3820		/*
   3821		 * Add dependency only if this lock is not the head
   3822		 * of the chain, and if the new lock introduces no more
   3823		 * lock dependency (because we already hold a lock with the
   3824		 * same lock class) nor deadlock (because the nest_lock
   3825		 * serializes nesting locks), see the comments for
   3826		 * check_deadlock().
   3827		 */
   3828		if (!chain_head && ret != 2) {
   3829			if (!check_prevs_add(curr, hlock))
   3830				return 0;
   3831		}
   3832
   3833		graph_unlock();
   3834	} else {
   3835		/* after lookup_chain_cache_add(): */
   3836		if (unlikely(!debug_locks))
   3837			return 0;
   3838	}
   3839
   3840	return 1;
   3841}
   3842#else
   3843static inline int validate_chain(struct task_struct *curr,
   3844				 struct held_lock *hlock,
   3845				 int chain_head, u64 chain_key)
   3846{
   3847	return 1;
   3848}
   3849
   3850static void init_chain_block_buckets(void)	{ }
   3851#endif /* CONFIG_PROVE_LOCKING */
   3852
   3853/*
   3854 * We are building curr_chain_key incrementally, so double-check
   3855 * it from scratch, to make sure that it's done correctly:
   3856 */
   3857static void check_chain_key(struct task_struct *curr)
   3858{
   3859#ifdef CONFIG_DEBUG_LOCKDEP
   3860	struct held_lock *hlock, *prev_hlock = NULL;
   3861	unsigned int i;
   3862	u64 chain_key = INITIAL_CHAIN_KEY;
   3863
   3864	for (i = 0; i < curr->lockdep_depth; i++) {
   3865		hlock = curr->held_locks + i;
   3866		if (chain_key != hlock->prev_chain_key) {
   3867			debug_locks_off();
   3868			/*
   3869			 * We got mighty confused, our chain keys don't match
   3870			 * with what we expect, someone trample on our task state?
   3871			 */
   3872			WARN(1, "hm#1, depth: %u [%u], %016Lx != %016Lx\n",
   3873				curr->lockdep_depth, i,
   3874				(unsigned long long)chain_key,
   3875				(unsigned long long)hlock->prev_chain_key);
   3876			return;
   3877		}
   3878
   3879		/*
   3880		 * hlock->class_idx can't go beyond MAX_LOCKDEP_KEYS, but is
   3881		 * it registered lock class index?
   3882		 */
   3883		if (DEBUG_LOCKS_WARN_ON(!test_bit(hlock->class_idx, lock_classes_in_use)))
   3884			return;
   3885
   3886		if (prev_hlock && (prev_hlock->irq_context !=
   3887							hlock->irq_context))
   3888			chain_key = INITIAL_CHAIN_KEY;
   3889		chain_key = iterate_chain_key(chain_key, hlock_id(hlock));
   3890		prev_hlock = hlock;
   3891	}
   3892	if (chain_key != curr->curr_chain_key) {
   3893		debug_locks_off();
   3894		/*
   3895		 * More smoking hash instead of calculating it, damn see these
   3896		 * numbers float.. I bet that a pink elephant stepped on my memory.
   3897		 */
   3898		WARN(1, "hm#2, depth: %u [%u], %016Lx != %016Lx\n",
   3899			curr->lockdep_depth, i,
   3900			(unsigned long long)chain_key,
   3901			(unsigned long long)curr->curr_chain_key);
   3902	}
   3903#endif
   3904}
   3905
   3906#ifdef CONFIG_PROVE_LOCKING
   3907static int mark_lock(struct task_struct *curr, struct held_lock *this,
   3908		     enum lock_usage_bit new_bit);
   3909
   3910static void print_usage_bug_scenario(struct held_lock *lock)
   3911{
   3912	struct lock_class *class = hlock_class(lock);
   3913
   3914	printk(" Possible unsafe locking scenario:\n\n");
   3915	printk("       CPU0\n");
   3916	printk("       ----\n");
   3917	printk("  lock(");
   3918	__print_lock_name(class);
   3919	printk(KERN_CONT ");\n");
   3920	printk("  <Interrupt>\n");
   3921	printk("    lock(");
   3922	__print_lock_name(class);
   3923	printk(KERN_CONT ");\n");
   3924	printk("\n *** DEADLOCK ***\n\n");
   3925}
   3926
   3927static void
   3928print_usage_bug(struct task_struct *curr, struct held_lock *this,
   3929		enum lock_usage_bit prev_bit, enum lock_usage_bit new_bit)
   3930{
   3931	if (!debug_locks_off() || debug_locks_silent)
   3932		return;
   3933
   3934	pr_warn("\n");
   3935	pr_warn("================================\n");
   3936	pr_warn("WARNING: inconsistent lock state\n");
   3937	print_kernel_ident();
   3938	pr_warn("--------------------------------\n");
   3939
   3940	pr_warn("inconsistent {%s} -> {%s} usage.\n",
   3941		usage_str[prev_bit], usage_str[new_bit]);
   3942
   3943	pr_warn("%s/%d [HC%u[%lu]:SC%u[%lu]:HE%u:SE%u] takes:\n",
   3944		curr->comm, task_pid_nr(curr),
   3945		lockdep_hardirq_context(), hardirq_count() >> HARDIRQ_SHIFT,
   3946		lockdep_softirq_context(curr), softirq_count() >> SOFTIRQ_SHIFT,
   3947		lockdep_hardirqs_enabled(),
   3948		lockdep_softirqs_enabled(curr));
   3949	print_lock(this);
   3950
   3951	pr_warn("{%s} state was registered at:\n", usage_str[prev_bit]);
   3952	print_lock_trace(hlock_class(this)->usage_traces[prev_bit], 1);
   3953
   3954	print_irqtrace_events(curr);
   3955	pr_warn("\nother info that might help us debug this:\n");
   3956	print_usage_bug_scenario(this);
   3957
   3958	lockdep_print_held_locks(curr);
   3959
   3960	pr_warn("\nstack backtrace:\n");
   3961	dump_stack();
   3962}
   3963
   3964/*
   3965 * Print out an error if an invalid bit is set:
   3966 */
   3967static inline int
   3968valid_state(struct task_struct *curr, struct held_lock *this,
   3969	    enum lock_usage_bit new_bit, enum lock_usage_bit bad_bit)
   3970{
   3971	if (unlikely(hlock_class(this)->usage_mask & (1 << bad_bit))) {
   3972		graph_unlock();
   3973		print_usage_bug(curr, this, bad_bit, new_bit);
   3974		return 0;
   3975	}
   3976	return 1;
   3977}
   3978
   3979
   3980/*
   3981 * print irq inversion bug:
   3982 */
   3983static void
   3984print_irq_inversion_bug(struct task_struct *curr,
   3985			struct lock_list *root, struct lock_list *other,
   3986			struct held_lock *this, int forwards,
   3987			const char *irqclass)
   3988{
   3989	struct lock_list *entry = other;
   3990	struct lock_list *middle = NULL;
   3991	int depth;
   3992
   3993	if (!debug_locks_off_graph_unlock() || debug_locks_silent)
   3994		return;
   3995
   3996	pr_warn("\n");
   3997	pr_warn("========================================================\n");
   3998	pr_warn("WARNING: possible irq lock inversion dependency detected\n");
   3999	print_kernel_ident();
   4000	pr_warn("--------------------------------------------------------\n");
   4001	pr_warn("%s/%d just changed the state of lock:\n",
   4002		curr->comm, task_pid_nr(curr));
   4003	print_lock(this);
   4004	if (forwards)
   4005		pr_warn("but this lock took another, %s-unsafe lock in the past:\n", irqclass);
   4006	else
   4007		pr_warn("but this lock was taken by another, %s-safe lock in the past:\n", irqclass);
   4008	print_lock_name(other->class);
   4009	pr_warn("\n\nand interrupts could create inverse lock ordering between them.\n\n");
   4010
   4011	pr_warn("\nother info that might help us debug this:\n");
   4012
   4013	/* Find a middle lock (if one exists) */
   4014	depth = get_lock_depth(other);
   4015	do {
   4016		if (depth == 0 && (entry != root)) {
   4017			pr_warn("lockdep:%s bad path found in chain graph\n", __func__);
   4018			break;
   4019		}
   4020		middle = entry;
   4021		entry = get_lock_parent(entry);
   4022		depth--;
   4023	} while (entry && entry != root && (depth >= 0));
   4024	if (forwards)
   4025		print_irq_lock_scenario(root, other,
   4026			middle ? middle->class : root->class, other->class);
   4027	else
   4028		print_irq_lock_scenario(other, root,
   4029			middle ? middle->class : other->class, root->class);
   4030
   4031	lockdep_print_held_locks(curr);
   4032
   4033	pr_warn("\nthe shortest dependencies between 2nd lock and 1st lock:\n");
   4034	root->trace = save_trace();
   4035	if (!root->trace)
   4036		return;
   4037	print_shortest_lock_dependencies(other, root);
   4038
   4039	pr_warn("\nstack backtrace:\n");
   4040	dump_stack();
   4041}
   4042
   4043/*
   4044 * Prove that in the forwards-direction subgraph starting at <this>
   4045 * there is no lock matching <mask>:
   4046 */
   4047static int
   4048check_usage_forwards(struct task_struct *curr, struct held_lock *this,
   4049		     enum lock_usage_bit bit)
   4050{
   4051	enum bfs_result ret;
   4052	struct lock_list root;
   4053	struct lock_list *target_entry;
   4054	enum lock_usage_bit read_bit = bit + LOCK_USAGE_READ_MASK;
   4055	unsigned usage_mask = lock_flag(bit) | lock_flag(read_bit);
   4056
   4057	bfs_init_root(&root, this);
   4058	ret = find_usage_forwards(&root, usage_mask, &target_entry);
   4059	if (bfs_error(ret)) {
   4060		print_bfs_bug(ret);
   4061		return 0;
   4062	}
   4063	if (ret == BFS_RNOMATCH)
   4064		return 1;
   4065
   4066	/* Check whether write or read usage is the match */
   4067	if (target_entry->class->usage_mask & lock_flag(bit)) {
   4068		print_irq_inversion_bug(curr, &root, target_entry,
   4069					this, 1, state_name(bit));
   4070	} else {
   4071		print_irq_inversion_bug(curr, &root, target_entry,
   4072					this, 1, state_name(read_bit));
   4073	}
   4074
   4075	return 0;
   4076}
   4077
   4078/*
   4079 * Prove that in the backwards-direction subgraph starting at <this>
   4080 * there is no lock matching <mask>:
   4081 */
   4082static int
   4083check_usage_backwards(struct task_struct *curr, struct held_lock *this,
   4084		      enum lock_usage_bit bit)
   4085{
   4086	enum bfs_result ret;
   4087	struct lock_list root;
   4088	struct lock_list *target_entry;
   4089	enum lock_usage_bit read_bit = bit + LOCK_USAGE_READ_MASK;
   4090	unsigned usage_mask = lock_flag(bit) | lock_flag(read_bit);
   4091
   4092	bfs_init_rootb(&root, this);
   4093	ret = find_usage_backwards(&root, usage_mask, &target_entry);
   4094	if (bfs_error(ret)) {
   4095		print_bfs_bug(ret);
   4096		return 0;
   4097	}
   4098	if (ret == BFS_RNOMATCH)
   4099		return 1;
   4100
   4101	/* Check whether write or read usage is the match */
   4102	if (target_entry->class->usage_mask & lock_flag(bit)) {
   4103		print_irq_inversion_bug(curr, &root, target_entry,
   4104					this, 0, state_name(bit));
   4105	} else {
   4106		print_irq_inversion_bug(curr, &root, target_entry,
   4107					this, 0, state_name(read_bit));
   4108	}
   4109
   4110	return 0;
   4111}
   4112
   4113void print_irqtrace_events(struct task_struct *curr)
   4114{
   4115	const struct irqtrace_events *trace = &curr->irqtrace;
   4116
   4117	printk("irq event stamp: %u\n", trace->irq_events);
   4118	printk("hardirqs last  enabled at (%u): [<%px>] %pS\n",
   4119		trace->hardirq_enable_event, (void *)trace->hardirq_enable_ip,
   4120		(void *)trace->hardirq_enable_ip);
   4121	printk("hardirqs last disabled at (%u): [<%px>] %pS\n",
   4122		trace->hardirq_disable_event, (void *)trace->hardirq_disable_ip,
   4123		(void *)trace->hardirq_disable_ip);
   4124	printk("softirqs last  enabled at (%u): [<%px>] %pS\n",
   4125		trace->softirq_enable_event, (void *)trace->softirq_enable_ip,
   4126		(void *)trace->softirq_enable_ip);
   4127	printk("softirqs last disabled at (%u): [<%px>] %pS\n",
   4128		trace->softirq_disable_event, (void *)trace->softirq_disable_ip,
   4129		(void *)trace->softirq_disable_ip);
   4130}
   4131
   4132static int HARDIRQ_verbose(struct lock_class *class)
   4133{
   4134#if HARDIRQ_VERBOSE
   4135	return class_filter(class);
   4136#endif
   4137	return 0;
   4138}
   4139
   4140static int SOFTIRQ_verbose(struct lock_class *class)
   4141{
   4142#if SOFTIRQ_VERBOSE
   4143	return class_filter(class);
   4144#endif
   4145	return 0;
   4146}
   4147
   4148static int (*state_verbose_f[])(struct lock_class *class) = {
   4149#define LOCKDEP_STATE(__STATE) \
   4150	__STATE##_verbose,
   4151#include "lockdep_states.h"
   4152#undef LOCKDEP_STATE
   4153};
   4154
   4155static inline int state_verbose(enum lock_usage_bit bit,
   4156				struct lock_class *class)
   4157{
   4158	return state_verbose_f[bit >> LOCK_USAGE_DIR_MASK](class);
   4159}
   4160
   4161typedef int (*check_usage_f)(struct task_struct *, struct held_lock *,
   4162			     enum lock_usage_bit bit, const char *name);
   4163
   4164static int
   4165mark_lock_irq(struct task_struct *curr, struct held_lock *this,
   4166		enum lock_usage_bit new_bit)
   4167{
   4168	int excl_bit = exclusive_bit(new_bit);
   4169	int read = new_bit & LOCK_USAGE_READ_MASK;
   4170	int dir = new_bit & LOCK_USAGE_DIR_MASK;
   4171
   4172	/*
   4173	 * Validate that this particular lock does not have conflicting
   4174	 * usage states.
   4175	 */
   4176	if (!valid_state(curr, this, new_bit, excl_bit))
   4177		return 0;
   4178
   4179	/*
   4180	 * Check for read in write conflicts
   4181	 */
   4182	if (!read && !valid_state(curr, this, new_bit,
   4183				  excl_bit + LOCK_USAGE_READ_MASK))
   4184		return 0;
   4185
   4186
   4187	/*
   4188	 * Validate that the lock dependencies don't have conflicting usage
   4189	 * states.
   4190	 */
   4191	if (dir) {
   4192		/*
   4193		 * mark ENABLED has to look backwards -- to ensure no dependee
   4194		 * has USED_IN state, which, again, would allow  recursion deadlocks.
   4195		 */
   4196		if (!check_usage_backwards(curr, this, excl_bit))
   4197			return 0;
   4198	} else {
   4199		/*
   4200		 * mark USED_IN has to look forwards -- to ensure no dependency
   4201		 * has ENABLED state, which would allow recursion deadlocks.
   4202		 */
   4203		if (!check_usage_forwards(curr, this, excl_bit))
   4204			return 0;
   4205	}
   4206
   4207	if (state_verbose(new_bit, hlock_class(this)))
   4208		return 2;
   4209
   4210	return 1;
   4211}
   4212
   4213/*
   4214 * Mark all held locks with a usage bit:
   4215 */
   4216static int
   4217mark_held_locks(struct task_struct *curr, enum lock_usage_bit base_bit)
   4218{
   4219	struct held_lock *hlock;
   4220	int i;
   4221
   4222	for (i = 0; i < curr->lockdep_depth; i++) {
   4223		enum lock_usage_bit hlock_bit = base_bit;
   4224		hlock = curr->held_locks + i;
   4225
   4226		if (hlock->read)
   4227			hlock_bit += LOCK_USAGE_READ_MASK;
   4228
   4229		BUG_ON(hlock_bit >= LOCK_USAGE_STATES);
   4230
   4231		if (!hlock->check)
   4232			continue;
   4233
   4234		if (!mark_lock(curr, hlock, hlock_bit))
   4235			return 0;
   4236	}
   4237
   4238	return 1;
   4239}
   4240
   4241/*
   4242 * Hardirqs will be enabled:
   4243 */
   4244static void __trace_hardirqs_on_caller(void)
   4245{
   4246	struct task_struct *curr = current;
   4247
   4248	/*
   4249	 * We are going to turn hardirqs on, so set the
   4250	 * usage bit for all held locks:
   4251	 */
   4252	if (!mark_held_locks(curr, LOCK_ENABLED_HARDIRQ))
   4253		return;
   4254	/*
   4255	 * If we have softirqs enabled, then set the usage
   4256	 * bit for all held locks. (disabled hardirqs prevented
   4257	 * this bit from being set before)
   4258	 */
   4259	if (curr->softirqs_enabled)
   4260		mark_held_locks(curr, LOCK_ENABLED_SOFTIRQ);
   4261}
   4262
   4263/**
   4264 * lockdep_hardirqs_on_prepare - Prepare for enabling interrupts
   4265 *
   4266 * Invoked before a possible transition to RCU idle from exit to user or
   4267 * guest mode. This ensures that all RCU operations are done before RCU
   4268 * stops watching. After the RCU transition lockdep_hardirqs_on() has to be
   4269 * invoked to set the final state.
   4270 */
   4271void lockdep_hardirqs_on_prepare(void)
   4272{
   4273	if (unlikely(!debug_locks))
   4274		return;
   4275
   4276	/*
   4277	 * NMIs do not (and cannot) track lock dependencies, nothing to do.
   4278	 */
   4279	if (unlikely(in_nmi()))
   4280		return;
   4281
   4282	if (unlikely(this_cpu_read(lockdep_recursion)))
   4283		return;
   4284
   4285	if (unlikely(lockdep_hardirqs_enabled())) {
   4286		/*
   4287		 * Neither irq nor preemption are disabled here
   4288		 * so this is racy by nature but losing one hit
   4289		 * in a stat is not a big deal.
   4290		 */
   4291		__debug_atomic_inc(redundant_hardirqs_on);
   4292		return;
   4293	}
   4294
   4295	/*
   4296	 * We're enabling irqs and according to our state above irqs weren't
   4297	 * already enabled, yet we find the hardware thinks they are in fact
   4298	 * enabled.. someone messed up their IRQ state tracing.
   4299	 */
   4300	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
   4301		return;
   4302
   4303	/*
   4304	 * See the fine text that goes along with this variable definition.
   4305	 */
   4306	if (DEBUG_LOCKS_WARN_ON(early_boot_irqs_disabled))
   4307		return;
   4308
   4309	/*
   4310	 * Can't allow enabling interrupts while in an interrupt handler,
   4311	 * that's general bad form and such. Recursion, limited stack etc..
   4312	 */
   4313	if (DEBUG_LOCKS_WARN_ON(lockdep_hardirq_context()))
   4314		return;
   4315
   4316	current->hardirq_chain_key = current->curr_chain_key;
   4317
   4318	lockdep_recursion_inc();
   4319	__trace_hardirqs_on_caller();
   4320	lockdep_recursion_finish();
   4321}
   4322EXPORT_SYMBOL_GPL(lockdep_hardirqs_on_prepare);
   4323
   4324void noinstr lockdep_hardirqs_on(unsigned long ip)
   4325{
   4326	struct irqtrace_events *trace = &current->irqtrace;
   4327
   4328	if (unlikely(!debug_locks))
   4329		return;
   4330
   4331	/*
   4332	 * NMIs can happen in the middle of local_irq_{en,dis}able() where the
   4333	 * tracking state and hardware state are out of sync.
   4334	 *
   4335	 * NMIs must save lockdep_hardirqs_enabled() to restore IRQ state from,
   4336	 * and not rely on hardware state like normal interrupts.
   4337	 */
   4338	if (unlikely(in_nmi())) {
   4339		if (!IS_ENABLED(CONFIG_TRACE_IRQFLAGS_NMI))
   4340			return;
   4341
   4342		/*
   4343		 * Skip:
   4344		 *  - recursion check, because NMI can hit lockdep;
   4345		 *  - hardware state check, because above;
   4346		 *  - chain_key check, see lockdep_hardirqs_on_prepare().
   4347		 */
   4348		goto skip_checks;
   4349	}
   4350
   4351	if (unlikely(this_cpu_read(lockdep_recursion)))
   4352		return;
   4353
   4354	if (lockdep_hardirqs_enabled()) {
   4355		/*
   4356		 * Neither irq nor preemption are disabled here
   4357		 * so this is racy by nature but losing one hit
   4358		 * in a stat is not a big deal.
   4359		 */
   4360		__debug_atomic_inc(redundant_hardirqs_on);
   4361		return;
   4362	}
   4363
   4364	/*
   4365	 * We're enabling irqs and according to our state above irqs weren't
   4366	 * already enabled, yet we find the hardware thinks they are in fact
   4367	 * enabled.. someone messed up their IRQ state tracing.
   4368	 */
   4369	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
   4370		return;
   4371
   4372	/*
   4373	 * Ensure the lock stack remained unchanged between
   4374	 * lockdep_hardirqs_on_prepare() and lockdep_hardirqs_on().
   4375	 */
   4376	DEBUG_LOCKS_WARN_ON(current->hardirq_chain_key !=
   4377			    current->curr_chain_key);
   4378
   4379skip_checks:
   4380	/* we'll do an OFF -> ON transition: */
   4381	__this_cpu_write(hardirqs_enabled, 1);
   4382	trace->hardirq_enable_ip = ip;
   4383	trace->hardirq_enable_event = ++trace->irq_events;
   4384	debug_atomic_inc(hardirqs_on_events);
   4385}
   4386EXPORT_SYMBOL_GPL(lockdep_hardirqs_on);
   4387
   4388/*
   4389 * Hardirqs were disabled:
   4390 */
   4391void noinstr lockdep_hardirqs_off(unsigned long ip)
   4392{
   4393	if (unlikely(!debug_locks))
   4394		return;
   4395
   4396	/*
   4397	 * Matching lockdep_hardirqs_on(), allow NMIs in the middle of lockdep;
   4398	 * they will restore the software state. This ensures the software
   4399	 * state is consistent inside NMIs as well.
   4400	 */
   4401	if (in_nmi()) {
   4402		if (!IS_ENABLED(CONFIG_TRACE_IRQFLAGS_NMI))
   4403			return;
   4404	} else if (__this_cpu_read(lockdep_recursion))
   4405		return;
   4406
   4407	/*
   4408	 * So we're supposed to get called after you mask local IRQs, but for
   4409	 * some reason the hardware doesn't quite think you did a proper job.
   4410	 */
   4411	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
   4412		return;
   4413
   4414	if (lockdep_hardirqs_enabled()) {
   4415		struct irqtrace_events *trace = &current->irqtrace;
   4416
   4417		/*
   4418		 * We have done an ON -> OFF transition:
   4419		 */
   4420		__this_cpu_write(hardirqs_enabled, 0);
   4421		trace->hardirq_disable_ip = ip;
   4422		trace->hardirq_disable_event = ++trace->irq_events;
   4423		debug_atomic_inc(hardirqs_off_events);
   4424	} else {
   4425		debug_atomic_inc(redundant_hardirqs_off);
   4426	}
   4427}
   4428EXPORT_SYMBOL_GPL(lockdep_hardirqs_off);
   4429
   4430/*
   4431 * Softirqs will be enabled:
   4432 */
   4433void lockdep_softirqs_on(unsigned long ip)
   4434{
   4435	struct irqtrace_events *trace = &current->irqtrace;
   4436
   4437	if (unlikely(!lockdep_enabled()))
   4438		return;
   4439
   4440	/*
   4441	 * We fancy IRQs being disabled here, see softirq.c, avoids
   4442	 * funny state and nesting things.
   4443	 */
   4444	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
   4445		return;
   4446
   4447	if (current->softirqs_enabled) {
   4448		debug_atomic_inc(redundant_softirqs_on);
   4449		return;
   4450	}
   4451
   4452	lockdep_recursion_inc();
   4453	/*
   4454	 * We'll do an OFF -> ON transition:
   4455	 */
   4456	current->softirqs_enabled = 1;
   4457	trace->softirq_enable_ip = ip;
   4458	trace->softirq_enable_event = ++trace->irq_events;
   4459	debug_atomic_inc(softirqs_on_events);
   4460	/*
   4461	 * We are going to turn softirqs on, so set the
   4462	 * usage bit for all held locks, if hardirqs are
   4463	 * enabled too:
   4464	 */
   4465	if (lockdep_hardirqs_enabled())
   4466		mark_held_locks(current, LOCK_ENABLED_SOFTIRQ);
   4467	lockdep_recursion_finish();
   4468}
   4469
   4470/*
   4471 * Softirqs were disabled:
   4472 */
   4473void lockdep_softirqs_off(unsigned long ip)
   4474{
   4475	if (unlikely(!lockdep_enabled()))
   4476		return;
   4477
   4478	/*
   4479	 * We fancy IRQs being disabled here, see softirq.c
   4480	 */
   4481	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
   4482		return;
   4483
   4484	if (current->softirqs_enabled) {
   4485		struct irqtrace_events *trace = &current->irqtrace;
   4486
   4487		/*
   4488		 * We have done an ON -> OFF transition:
   4489		 */
   4490		current->softirqs_enabled = 0;
   4491		trace->softirq_disable_ip = ip;
   4492		trace->softirq_disable_event = ++trace->irq_events;
   4493		debug_atomic_inc(softirqs_off_events);
   4494		/*
   4495		 * Whoops, we wanted softirqs off, so why aren't they?
   4496		 */
   4497		DEBUG_LOCKS_WARN_ON(!softirq_count());
   4498	} else
   4499		debug_atomic_inc(redundant_softirqs_off);
   4500}
   4501
   4502static int
   4503mark_usage(struct task_struct *curr, struct held_lock *hlock, int check)
   4504{
   4505	if (!check)
   4506		goto lock_used;
   4507
   4508	/*
   4509	 * If non-trylock use in a hardirq or softirq context, then
   4510	 * mark the lock as used in these contexts:
   4511	 */
   4512	if (!hlock->trylock) {
   4513		if (hlock->read) {
   4514			if (lockdep_hardirq_context())
   4515				if (!mark_lock(curr, hlock,
   4516						LOCK_USED_IN_HARDIRQ_READ))
   4517					return 0;
   4518			if (curr->softirq_context)
   4519				if (!mark_lock(curr, hlock,
   4520						LOCK_USED_IN_SOFTIRQ_READ))
   4521					return 0;
   4522		} else {
   4523			if (lockdep_hardirq_context())
   4524				if (!mark_lock(curr, hlock, LOCK_USED_IN_HARDIRQ))
   4525					return 0;
   4526			if (curr->softirq_context)
   4527				if (!mark_lock(curr, hlock, LOCK_USED_IN_SOFTIRQ))
   4528					return 0;
   4529		}
   4530	}
   4531	if (!hlock->hardirqs_off) {
   4532		if (hlock->read) {
   4533			if (!mark_lock(curr, hlock,
   4534					LOCK_ENABLED_HARDIRQ_READ))
   4535				return 0;
   4536			if (curr->softirqs_enabled)
   4537				if (!mark_lock(curr, hlock,
   4538						LOCK_ENABLED_SOFTIRQ_READ))
   4539					return 0;
   4540		} else {
   4541			if (!mark_lock(curr, hlock,
   4542					LOCK_ENABLED_HARDIRQ))
   4543				return 0;
   4544			if (curr->softirqs_enabled)
   4545				if (!mark_lock(curr, hlock,
   4546						LOCK_ENABLED_SOFTIRQ))
   4547					return 0;
   4548		}
   4549	}
   4550
   4551lock_used:
   4552	/* mark it as used: */
   4553	if (!mark_lock(curr, hlock, LOCK_USED))
   4554		return 0;
   4555
   4556	return 1;
   4557}
   4558
   4559static inline unsigned int task_irq_context(struct task_struct *task)
   4560{
   4561	return LOCK_CHAIN_HARDIRQ_CONTEXT * !!lockdep_hardirq_context() +
   4562	       LOCK_CHAIN_SOFTIRQ_CONTEXT * !!task->softirq_context;
   4563}
   4564
   4565static int separate_irq_context(struct task_struct *curr,
   4566		struct held_lock *hlock)
   4567{
   4568	unsigned int depth = curr->lockdep_depth;
   4569
   4570	/*
   4571	 * Keep track of points where we cross into an interrupt context:
   4572	 */
   4573	if (depth) {
   4574		struct held_lock *prev_hlock;
   4575
   4576		prev_hlock = curr->held_locks + depth-1;
   4577		/*
   4578		 * If we cross into another context, reset the
   4579		 * hash key (this also prevents the checking and the
   4580		 * adding of the dependency to 'prev'):
   4581		 */
   4582		if (prev_hlock->irq_context != hlock->irq_context)
   4583			return 1;
   4584	}
   4585	return 0;
   4586}
   4587
   4588/*
   4589 * Mark a lock with a usage bit, and validate the state transition:
   4590 */
   4591static int mark_lock(struct task_struct *curr, struct held_lock *this,
   4592			     enum lock_usage_bit new_bit)
   4593{
   4594	unsigned int new_mask, ret = 1;
   4595
   4596	if (new_bit >= LOCK_USAGE_STATES) {
   4597		DEBUG_LOCKS_WARN_ON(1);
   4598		return 0;
   4599	}
   4600
   4601	if (new_bit == LOCK_USED && this->read)
   4602		new_bit = LOCK_USED_READ;
   4603
   4604	new_mask = 1 << new_bit;
   4605
   4606	/*
   4607	 * If already set then do not dirty the cacheline,
   4608	 * nor do any checks:
   4609	 */
   4610	if (likely(hlock_class(this)->usage_mask & new_mask))
   4611		return 1;
   4612
   4613	if (!graph_lock())
   4614		return 0;
   4615	/*
   4616	 * Make sure we didn't race:
   4617	 */
   4618	if (unlikely(hlock_class(this)->usage_mask & new_mask))
   4619		goto unlock;
   4620
   4621	if (!hlock_class(this)->usage_mask)
   4622		debug_atomic_dec(nr_unused_locks);
   4623
   4624	hlock_class(this)->usage_mask |= new_mask;
   4625
   4626	if (new_bit < LOCK_TRACE_STATES) {
   4627		if (!(hlock_class(this)->usage_traces[new_bit] = save_trace()))
   4628			return 0;
   4629	}
   4630
   4631	if (new_bit < LOCK_USED) {
   4632		ret = mark_lock_irq(curr, this, new_bit);
   4633		if (!ret)
   4634			return 0;
   4635	}
   4636
   4637unlock:
   4638	graph_unlock();
   4639
   4640	/*
   4641	 * We must printk outside of the graph_lock:
   4642	 */
   4643	if (ret == 2) {
   4644		printk("\nmarked lock as {%s}:\n", usage_str[new_bit]);
   4645		print_lock(this);
   4646		print_irqtrace_events(curr);
   4647		dump_stack();
   4648	}
   4649
   4650	return ret;
   4651}
   4652
   4653static inline short task_wait_context(struct task_struct *curr)
   4654{
   4655	/*
   4656	 * Set appropriate wait type for the context; for IRQs we have to take
   4657	 * into account force_irqthread as that is implied by PREEMPT_RT.
   4658	 */
   4659	if (lockdep_hardirq_context()) {
   4660		/*
   4661		 * Check if force_irqthreads will run us threaded.
   4662		 */
   4663		if (curr->hardirq_threaded || curr->irq_config)
   4664			return LD_WAIT_CONFIG;
   4665
   4666		return LD_WAIT_SPIN;
   4667	} else if (curr->softirq_context) {
   4668		/*
   4669		 * Softirqs are always threaded.
   4670		 */
   4671		return LD_WAIT_CONFIG;
   4672	}
   4673
   4674	return LD_WAIT_MAX;
   4675}
   4676
   4677static int
   4678print_lock_invalid_wait_context(struct task_struct *curr,
   4679				struct held_lock *hlock)
   4680{
   4681	short curr_inner;
   4682
   4683	if (!debug_locks_off())
   4684		return 0;
   4685	if (debug_locks_silent)
   4686		return 0;
   4687
   4688	pr_warn("\n");
   4689	pr_warn("=============================\n");
   4690	pr_warn("[ BUG: Invalid wait context ]\n");
   4691	print_kernel_ident();
   4692	pr_warn("-----------------------------\n");
   4693
   4694	pr_warn("%s/%d is trying to lock:\n", curr->comm, task_pid_nr(curr));
   4695	print_lock(hlock);
   4696
   4697	pr_warn("other info that might help us debug this:\n");
   4698
   4699	curr_inner = task_wait_context(curr);
   4700	pr_warn("context-{%d:%d}\n", curr_inner, curr_inner);
   4701
   4702	lockdep_print_held_locks(curr);
   4703
   4704	pr_warn("stack backtrace:\n");
   4705	dump_stack();
   4706
   4707	return 0;
   4708}
   4709
   4710/*
   4711 * Verify the wait_type context.
   4712 *
   4713 * This check validates we take locks in the right wait-type order; that is it
   4714 * ensures that we do not take mutexes inside spinlocks and do not attempt to
   4715 * acquire spinlocks inside raw_spinlocks and the sort.
   4716 *
   4717 * The entire thing is slightly more complex because of RCU, RCU is a lock that
   4718 * can be taken from (pretty much) any context but also has constraints.
   4719 * However when taken in a stricter environment the RCU lock does not loosen
   4720 * the constraints.
   4721 *
   4722 * Therefore we must look for the strictest environment in the lock stack and
   4723 * compare that to the lock we're trying to acquire.
   4724 */
   4725static int check_wait_context(struct task_struct *curr, struct held_lock *next)
   4726{
   4727	u8 next_inner = hlock_class(next)->wait_type_inner;
   4728	u8 next_outer = hlock_class(next)->wait_type_outer;
   4729	u8 curr_inner;
   4730	int depth;
   4731
   4732	if (!next_inner || next->trylock)
   4733		return 0;
   4734
   4735	if (!next_outer)
   4736		next_outer = next_inner;
   4737
   4738	/*
   4739	 * Find start of current irq_context..
   4740	 */
   4741	for (depth = curr->lockdep_depth - 1; depth >= 0; depth--) {
   4742		struct held_lock *prev = curr->held_locks + depth;
   4743		if (prev->irq_context != next->irq_context)
   4744			break;
   4745	}
   4746	depth++;
   4747
   4748	curr_inner = task_wait_context(curr);
   4749
   4750	for (; depth < curr->lockdep_depth; depth++) {
   4751		struct held_lock *prev = curr->held_locks + depth;
   4752		u8 prev_inner = hlock_class(prev)->wait_type_inner;
   4753
   4754		if (prev_inner) {
   4755			/*
   4756			 * We can have a bigger inner than a previous one
   4757			 * when outer is smaller than inner, as with RCU.
   4758			 *
   4759			 * Also due to trylocks.
   4760			 */
   4761			curr_inner = min(curr_inner, prev_inner);
   4762		}
   4763	}
   4764
   4765	if (next_outer > curr_inner)
   4766		return print_lock_invalid_wait_context(curr, next);
   4767
   4768	return 0;
   4769}
   4770
   4771#else /* CONFIG_PROVE_LOCKING */
   4772
   4773static inline int
   4774mark_usage(struct task_struct *curr, struct held_lock *hlock, int check)
   4775{
   4776	return 1;
   4777}
   4778
   4779static inline unsigned int task_irq_context(struct task_struct *task)
   4780{
   4781	return 0;
   4782}
   4783
   4784static inline int separate_irq_context(struct task_struct *curr,
   4785		struct held_lock *hlock)
   4786{
   4787	return 0;
   4788}
   4789
   4790static inline int check_wait_context(struct task_struct *curr,
   4791				     struct held_lock *next)
   4792{
   4793	return 0;
   4794}
   4795
   4796#endif /* CONFIG_PROVE_LOCKING */
   4797
   4798/*
   4799 * Initialize a lock instance's lock-class mapping info:
   4800 */
   4801void lockdep_init_map_type(struct lockdep_map *lock, const char *name,
   4802			    struct lock_class_key *key, int subclass,
   4803			    u8 inner, u8 outer, u8 lock_type)
   4804{
   4805	int i;
   4806
   4807	for (i = 0; i < NR_LOCKDEP_CACHING_CLASSES; i++)
   4808		lock->class_cache[i] = NULL;
   4809
   4810#ifdef CONFIG_LOCK_STAT
   4811	lock->cpu = raw_smp_processor_id();
   4812#endif
   4813
   4814	/*
   4815	 * Can't be having no nameless bastards around this place!
   4816	 */
   4817	if (DEBUG_LOCKS_WARN_ON(!name)) {
   4818		lock->name = "NULL";
   4819		return;
   4820	}
   4821
   4822	lock->name = name;
   4823
   4824	lock->wait_type_outer = outer;
   4825	lock->wait_type_inner = inner;
   4826	lock->lock_type = lock_type;
   4827
   4828	/*
   4829	 * No key, no joy, we need to hash something.
   4830	 */
   4831	if (DEBUG_LOCKS_WARN_ON(!key))
   4832		return;
   4833	/*
   4834	 * Sanity check, the lock-class key must either have been allocated
   4835	 * statically or must have been registered as a dynamic key.
   4836	 */
   4837	if (!static_obj(key) && !is_dynamic_key(key)) {
   4838		if (debug_locks)
   4839			printk(KERN_ERR "BUG: key %px has not been registered!\n", key);
   4840		DEBUG_LOCKS_WARN_ON(1);
   4841		return;
   4842	}
   4843	lock->key = key;
   4844
   4845	if (unlikely(!debug_locks))
   4846		return;
   4847
   4848	if (subclass) {
   4849		unsigned long flags;
   4850
   4851		if (DEBUG_LOCKS_WARN_ON(!lockdep_enabled()))
   4852			return;
   4853
   4854		raw_local_irq_save(flags);
   4855		lockdep_recursion_inc();
   4856		register_lock_class(lock, subclass, 1);
   4857		lockdep_recursion_finish();
   4858		raw_local_irq_restore(flags);
   4859	}
   4860}
   4861EXPORT_SYMBOL_GPL(lockdep_init_map_type);
   4862
   4863struct lock_class_key __lockdep_no_validate__;
   4864EXPORT_SYMBOL_GPL(__lockdep_no_validate__);
   4865
   4866static void
   4867print_lock_nested_lock_not_held(struct task_struct *curr,
   4868				struct held_lock *hlock)
   4869{
   4870	if (!debug_locks_off())
   4871		return;
   4872	if (debug_locks_silent)
   4873		return;
   4874
   4875	pr_warn("\n");
   4876	pr_warn("==================================\n");
   4877	pr_warn("WARNING: Nested lock was not taken\n");
   4878	print_kernel_ident();
   4879	pr_warn("----------------------------------\n");
   4880
   4881	pr_warn("%s/%d is trying to lock:\n", curr->comm, task_pid_nr(curr));
   4882	print_lock(hlock);
   4883
   4884	pr_warn("\nbut this task is not holding:\n");
   4885	pr_warn("%s\n", hlock->nest_lock->name);
   4886
   4887	pr_warn("\nstack backtrace:\n");
   4888	dump_stack();
   4889
   4890	pr_warn("\nother info that might help us debug this:\n");
   4891	lockdep_print_held_locks(curr);
   4892
   4893	pr_warn("\nstack backtrace:\n");
   4894	dump_stack();
   4895}
   4896
   4897static int __lock_is_held(const struct lockdep_map *lock, int read);
   4898
   4899/*
   4900 * This gets called for every mutex_lock*()/spin_lock*() operation.
   4901 * We maintain the dependency maps and validate the locking attempt:
   4902 *
   4903 * The callers must make sure that IRQs are disabled before calling it,
   4904 * otherwise we could get an interrupt which would want to take locks,
   4905 * which would end up in lockdep again.
   4906 */
   4907static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
   4908			  int trylock, int read, int check, int hardirqs_off,
   4909			  struct lockdep_map *nest_lock, unsigned long ip,
   4910			  int references, int pin_count)
   4911{
   4912	struct task_struct *curr = current;
   4913	struct lock_class *class = NULL;
   4914	struct held_lock *hlock;
   4915	unsigned int depth;
   4916	int chain_head = 0;
   4917	int class_idx;
   4918	u64 chain_key;
   4919
   4920	if (unlikely(!debug_locks))
   4921		return 0;
   4922
   4923	if (!prove_locking || lock->key == &__lockdep_no_validate__)
   4924		check = 0;
   4925
   4926	if (subclass < NR_LOCKDEP_CACHING_CLASSES)
   4927		class = lock->class_cache[subclass];
   4928	/*
   4929	 * Not cached?
   4930	 */
   4931	if (unlikely(!class)) {
   4932		class = register_lock_class(lock, subclass, 0);
   4933		if (!class)
   4934			return 0;
   4935	}
   4936
   4937	debug_class_ops_inc(class);
   4938
   4939	if (very_verbose(class)) {
   4940		printk("\nacquire class [%px] %s", class->key, class->name);
   4941		if (class->name_version > 1)
   4942			printk(KERN_CONT "#%d", class->name_version);
   4943		printk(KERN_CONT "\n");
   4944		dump_stack();
   4945	}
   4946
   4947	/*
   4948	 * Add the lock to the list of currently held locks.
   4949	 * (we dont increase the depth just yet, up until the
   4950	 * dependency checks are done)
   4951	 */
   4952	depth = curr->lockdep_depth;
   4953	/*
   4954	 * Ran out of static storage for our per-task lock stack again have we?
   4955	 */
   4956	if (DEBUG_LOCKS_WARN_ON(depth >= MAX_LOCK_DEPTH))
   4957		return 0;
   4958
   4959	class_idx = class - lock_classes;
   4960
   4961	if (depth) { /* we're holding locks */
   4962		hlock = curr->held_locks + depth - 1;
   4963		if (hlock->class_idx == class_idx && nest_lock) {
   4964			if (!references)
   4965				references++;
   4966
   4967			if (!hlock->references)
   4968				hlock->references++;
   4969
   4970			hlock->references += references;
   4971
   4972			/* Overflow */
   4973			if (DEBUG_LOCKS_WARN_ON(hlock->references < references))
   4974				return 0;
   4975
   4976			return 2;
   4977		}
   4978	}
   4979
   4980	hlock = curr->held_locks + depth;
   4981	/*
   4982	 * Plain impossible, we just registered it and checked it weren't no
   4983	 * NULL like.. I bet this mushroom I ate was good!
   4984	 */
   4985	if (DEBUG_LOCKS_WARN_ON(!class))
   4986		return 0;
   4987	hlock->class_idx = class_idx;
   4988	hlock->acquire_ip = ip;
   4989	hlock->instance = lock;
   4990	hlock->nest_lock = nest_lock;
   4991	hlock->irq_context = task_irq_context(curr);
   4992	hlock->trylock = trylock;
   4993	hlock->read = read;
   4994	hlock->check = check;
   4995	hlock->hardirqs_off = !!hardirqs_off;
   4996	hlock->references = references;
   4997#ifdef CONFIG_LOCK_STAT
   4998	hlock->waittime_stamp = 0;
   4999	hlock->holdtime_stamp = lockstat_clock();
   5000#endif
   5001	hlock->pin_count = pin_count;
   5002
   5003	if (check_wait_context(curr, hlock))
   5004		return 0;
   5005
   5006	/* Initialize the lock usage bit */
   5007	if (!mark_usage(curr, hlock, check))
   5008		return 0;
   5009
   5010	/*
   5011	 * Calculate the chain hash: it's the combined hash of all the
   5012	 * lock keys along the dependency chain. We save the hash value
   5013	 * at every step so that we can get the current hash easily
   5014	 * after unlock. The chain hash is then used to cache dependency
   5015	 * results.
   5016	 *
   5017	 * The 'key ID' is what is the most compact key value to drive
   5018	 * the hash, not class->key.
   5019	 */
   5020	/*
   5021	 * Whoops, we did it again.. class_idx is invalid.
   5022	 */
   5023	if (DEBUG_LOCKS_WARN_ON(!test_bit(class_idx, lock_classes_in_use)))
   5024		return 0;
   5025
   5026	chain_key = curr->curr_chain_key;
   5027	if (!depth) {
   5028		/*
   5029		 * How can we have a chain hash when we ain't got no keys?!
   5030		 */
   5031		if (DEBUG_LOCKS_WARN_ON(chain_key != INITIAL_CHAIN_KEY))
   5032			return 0;
   5033		chain_head = 1;
   5034	}
   5035
   5036	hlock->prev_chain_key = chain_key;
   5037	if (separate_irq_context(curr, hlock)) {
   5038		chain_key = INITIAL_CHAIN_KEY;
   5039		chain_head = 1;
   5040	}
   5041	chain_key = iterate_chain_key(chain_key, hlock_id(hlock));
   5042
   5043	if (nest_lock && !__lock_is_held(nest_lock, -1)) {
   5044		print_lock_nested_lock_not_held(curr, hlock);
   5045		return 0;
   5046	}
   5047
   5048	if (!debug_locks_silent) {
   5049		WARN_ON_ONCE(depth && !hlock_class(hlock - 1)->key);
   5050		WARN_ON_ONCE(!hlock_class(hlock)->key);
   5051	}
   5052
   5053	if (!validate_chain(curr, hlock, chain_head, chain_key))
   5054		return 0;
   5055
   5056	curr->curr_chain_key = chain_key;
   5057	curr->lockdep_depth++;
   5058	check_chain_key(curr);
   5059#ifdef CONFIG_DEBUG_LOCKDEP
   5060	if (unlikely(!debug_locks))
   5061		return 0;
   5062#endif
   5063	if (unlikely(curr->lockdep_depth >= MAX_LOCK_DEPTH)) {
   5064		debug_locks_off();
   5065		print_lockdep_off("BUG: MAX_LOCK_DEPTH too low!");
   5066		printk(KERN_DEBUG "depth: %i  max: %lu!\n",
   5067		       curr->lockdep_depth, MAX_LOCK_DEPTH);
   5068
   5069		lockdep_print_held_locks(current);
   5070		debug_show_all_locks();
   5071		dump_stack();
   5072
   5073		return 0;
   5074	}
   5075
   5076	if (unlikely(curr->lockdep_depth > max_lockdep_depth))
   5077		max_lockdep_depth = curr->lockdep_depth;
   5078
   5079	return 1;
   5080}
   5081
   5082static void print_unlock_imbalance_bug(struct task_struct *curr,
   5083				       struct lockdep_map *lock,
   5084				       unsigned long ip)
   5085{
   5086	if (!debug_locks_off())
   5087		return;
   5088	if (debug_locks_silent)
   5089		return;
   5090
   5091	pr_warn("\n");
   5092	pr_warn("=====================================\n");
   5093	pr_warn("WARNING: bad unlock balance detected!\n");
   5094	print_kernel_ident();
   5095	pr_warn("-------------------------------------\n");
   5096	pr_warn("%s/%d is trying to release lock (",
   5097		curr->comm, task_pid_nr(curr));
   5098	print_lockdep_cache(lock);
   5099	pr_cont(") at:\n");
   5100	print_ip_sym(KERN_WARNING, ip);
   5101	pr_warn("but there are no more locks to release!\n");
   5102	pr_warn("\nother info that might help us debug this:\n");
   5103	lockdep_print_held_locks(curr);
   5104
   5105	pr_warn("\nstack backtrace:\n");
   5106	dump_stack();
   5107}
   5108
   5109static noinstr int match_held_lock(const struct held_lock *hlock,
   5110				   const struct lockdep_map *lock)
   5111{
   5112	if (hlock->instance == lock)
   5113		return 1;
   5114
   5115	if (hlock->references) {
   5116		const struct lock_class *class = lock->class_cache[0];
   5117
   5118		if (!class)
   5119			class = look_up_lock_class(lock, 0);
   5120
   5121		/*
   5122		 * If look_up_lock_class() failed to find a class, we're trying
   5123		 * to test if we hold a lock that has never yet been acquired.
   5124		 * Clearly if the lock hasn't been acquired _ever_, we're not
   5125		 * holding it either, so report failure.
   5126		 */
   5127		if (!class)
   5128			return 0;
   5129
   5130		/*
   5131		 * References, but not a lock we're actually ref-counting?
   5132		 * State got messed up, follow the sites that change ->references
   5133		 * and try to make sense of it.
   5134		 */
   5135		if (DEBUG_LOCKS_WARN_ON(!hlock->nest_lock))
   5136			return 0;
   5137
   5138		if (hlock->class_idx == class - lock_classes)
   5139			return 1;
   5140	}
   5141
   5142	return 0;
   5143}
   5144
   5145/* @depth must not be zero */
   5146static struct held_lock *find_held_lock(struct task_struct *curr,
   5147					struct lockdep_map *lock,
   5148					unsigned int depth, int *idx)
   5149{
   5150	struct held_lock *ret, *hlock, *prev_hlock;
   5151	int i;
   5152
   5153	i = depth - 1;
   5154	hlock = curr->held_locks + i;
   5155	ret = hlock;
   5156	if (match_held_lock(hlock, lock))
   5157		goto out;
   5158
   5159	ret = NULL;
   5160	for (i--, prev_hlock = hlock--;
   5161	     i >= 0;
   5162	     i--, prev_hlock = hlock--) {
   5163		/*
   5164		 * We must not cross into another context:
   5165		 */
   5166		if (prev_hlock->irq_context != hlock->irq_context) {
   5167			ret = NULL;
   5168			break;
   5169		}
   5170		if (match_held_lock(hlock, lock)) {
   5171			ret = hlock;
   5172			break;
   5173		}
   5174	}
   5175
   5176out:
   5177	*idx = i;
   5178	return ret;
   5179}
   5180
   5181static int reacquire_held_locks(struct task_struct *curr, unsigned int depth,
   5182				int idx, unsigned int *merged)
   5183{
   5184	struct held_lock *hlock;
   5185	int first_idx = idx;
   5186
   5187	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
   5188		return 0;
   5189
   5190	for (hlock = curr->held_locks + idx; idx < depth; idx++, hlock++) {
   5191		switch (__lock_acquire(hlock->instance,
   5192				    hlock_class(hlock)->subclass,
   5193				    hlock->trylock,
   5194				    hlock->read, hlock->check,
   5195				    hlock->hardirqs_off,
   5196				    hlock->nest_lock, hlock->acquire_ip,
   5197				    hlock->references, hlock->pin_count)) {
   5198		case 0:
   5199			return 1;
   5200		case 1:
   5201			break;
   5202		case 2:
   5203			*merged += (idx == first_idx);
   5204			break;
   5205		default:
   5206			WARN_ON(1);
   5207			return 0;
   5208		}
   5209	}
   5210	return 0;
   5211}
   5212
   5213static int
   5214__lock_set_class(struct lockdep_map *lock, const char *name,
   5215		 struct lock_class_key *key, unsigned int subclass,
   5216		 unsigned long ip)
   5217{
   5218	struct task_struct *curr = current;
   5219	unsigned int depth, merged = 0;
   5220	struct held_lock *hlock;
   5221	struct lock_class *class;
   5222	int i;
   5223
   5224	if (unlikely(!debug_locks))
   5225		return 0;
   5226
   5227	depth = curr->lockdep_depth;
   5228	/*
   5229	 * This function is about (re)setting the class of a held lock,
   5230	 * yet we're not actually holding any locks. Naughty user!
   5231	 */
   5232	if (DEBUG_LOCKS_WARN_ON(!depth))
   5233		return 0;
   5234
   5235	hlock = find_held_lock(curr, lock, depth, &i);
   5236	if (!hlock) {
   5237		print_unlock_imbalance_bug(curr, lock, ip);
   5238		return 0;
   5239	}
   5240
   5241	lockdep_init_map_waits(lock, name, key, 0,
   5242			       lock->wait_type_inner,
   5243			       lock->wait_type_outer);
   5244	class = register_lock_class(lock, subclass, 0);
   5245	hlock->class_idx = class - lock_classes;
   5246
   5247	curr->lockdep_depth = i;
   5248	curr->curr_chain_key = hlock->prev_chain_key;
   5249
   5250	if (reacquire_held_locks(curr, depth, i, &merged))
   5251		return 0;
   5252
   5253	/*
   5254	 * I took it apart and put it back together again, except now I have
   5255	 * these 'spare' parts.. where shall I put them.
   5256	 */
   5257	if (DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth - merged))
   5258		return 0;
   5259	return 1;
   5260}
   5261
   5262static int __lock_downgrade(struct lockdep_map *lock, unsigned long ip)
   5263{
   5264	struct task_struct *curr = current;
   5265	unsigned int depth, merged = 0;
   5266	struct held_lock *hlock;
   5267	int i;
   5268
   5269	if (unlikely(!debug_locks))
   5270		return 0;
   5271
   5272	depth = curr->lockdep_depth;
   5273	/*
   5274	 * This function is about (re)setting the class of a held lock,
   5275	 * yet we're not actually holding any locks. Naughty user!
   5276	 */
   5277	if (DEBUG_LOCKS_WARN_ON(!depth))
   5278		return 0;
   5279
   5280	hlock = find_held_lock(curr, lock, depth, &i);
   5281	if (!hlock) {
   5282		print_unlock_imbalance_bug(curr, lock, ip);
   5283		return 0;
   5284	}
   5285
   5286	curr->lockdep_depth = i;
   5287	curr->curr_chain_key = hlock->prev_chain_key;
   5288
   5289	WARN(hlock->read, "downgrading a read lock");
   5290	hlock->read = 1;
   5291	hlock->acquire_ip = ip;
   5292
   5293	if (reacquire_held_locks(curr, depth, i, &merged))
   5294		return 0;
   5295
   5296	/* Merging can't happen with unchanged classes.. */
   5297	if (DEBUG_LOCKS_WARN_ON(merged))
   5298		return 0;
   5299
   5300	/*
   5301	 * I took it apart and put it back together again, except now I have
   5302	 * these 'spare' parts.. where shall I put them.
   5303	 */
   5304	if (DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth))
   5305		return 0;
   5306
   5307	return 1;
   5308}
   5309
   5310/*
   5311 * Remove the lock from the list of currently held locks - this gets
   5312 * called on mutex_unlock()/spin_unlock*() (or on a failed
   5313 * mutex_lock_interruptible()).
   5314 */
   5315static int
   5316__lock_release(struct lockdep_map *lock, unsigned long ip)
   5317{
   5318	struct task_struct *curr = current;
   5319	unsigned int depth, merged = 1;
   5320	struct held_lock *hlock;
   5321	int i;
   5322
   5323	if (unlikely(!debug_locks))
   5324		return 0;
   5325
   5326	depth = curr->lockdep_depth;
   5327	/*
   5328	 * So we're all set to release this lock.. wait what lock? We don't
   5329	 * own any locks, you've been drinking again?
   5330	 */
   5331	if (depth <= 0) {
   5332		print_unlock_imbalance_bug(curr, lock, ip);
   5333		return 0;
   5334	}
   5335
   5336	/*
   5337	 * Check whether the lock exists in the current stack
   5338	 * of held locks:
   5339	 */
   5340	hlock = find_held_lock(curr, lock, depth, &i);
   5341	if (!hlock) {
   5342		print_unlock_imbalance_bug(curr, lock, ip);
   5343		return 0;
   5344	}
   5345
   5346	if (hlock->instance == lock)
   5347		lock_release_holdtime(hlock);
   5348
   5349	WARN(hlock->pin_count, "releasing a pinned lock\n");
   5350
   5351	if (hlock->references) {
   5352		hlock->references--;
   5353		if (hlock->references) {
   5354			/*
   5355			 * We had, and after removing one, still have
   5356			 * references, the current lock stack is still
   5357			 * valid. We're done!
   5358			 */
   5359			return 1;
   5360		}
   5361	}
   5362
   5363	/*
   5364	 * We have the right lock to unlock, 'hlock' points to it.
   5365	 * Now we remove it from the stack, and add back the other
   5366	 * entries (if any), recalculating the hash along the way:
   5367	 */
   5368
   5369	curr->lockdep_depth = i;
   5370	curr->curr_chain_key = hlock->prev_chain_key;
   5371
   5372	/*
   5373	 * The most likely case is when the unlock is on the innermost
   5374	 * lock. In this case, we are done!
   5375	 */
   5376	if (i == depth-1)
   5377		return 1;
   5378
   5379	if (reacquire_held_locks(curr, depth, i + 1, &merged))
   5380		return 0;
   5381
   5382	/*
   5383	 * We had N bottles of beer on the wall, we drank one, but now
   5384	 * there's not N-1 bottles of beer left on the wall...
   5385	 * Pouring two of the bottles together is acceptable.
   5386	 */
   5387	DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth - merged);
   5388
   5389	/*
   5390	 * Since reacquire_held_locks() would have called check_chain_key()
   5391	 * indirectly via __lock_acquire(), we don't need to do it again
   5392	 * on return.
   5393	 */
   5394	return 0;
   5395}
   5396
   5397static __always_inline
   5398int __lock_is_held(const struct lockdep_map *lock, int read)
   5399{
   5400	struct task_struct *curr = current;
   5401	int i;
   5402
   5403	for (i = 0; i < curr->lockdep_depth; i++) {
   5404		struct held_lock *hlock = curr->held_locks + i;
   5405
   5406		if (match_held_lock(hlock, lock)) {
   5407			if (read == -1 || !!hlock->read == read)
   5408				return LOCK_STATE_HELD;
   5409
   5410			return LOCK_STATE_NOT_HELD;
   5411		}
   5412	}
   5413
   5414	return LOCK_STATE_NOT_HELD;
   5415}
   5416
   5417static struct pin_cookie __lock_pin_lock(struct lockdep_map *lock)
   5418{
   5419	struct pin_cookie cookie = NIL_COOKIE;
   5420	struct task_struct *curr = current;
   5421	int i;
   5422
   5423	if (unlikely(!debug_locks))
   5424		return cookie;
   5425
   5426	for (i = 0; i < curr->lockdep_depth; i++) {
   5427		struct held_lock *hlock = curr->held_locks + i;
   5428
   5429		if (match_held_lock(hlock, lock)) {
   5430			/*
   5431			 * Grab 16bits of randomness; this is sufficient to not
   5432			 * be guessable and still allows some pin nesting in
   5433			 * our u32 pin_count.
   5434			 */
   5435			cookie.val = 1 + (sched_clock() & 0xffff);
   5436			hlock->pin_count += cookie.val;
   5437			return cookie;
   5438		}
   5439	}
   5440
   5441	WARN(1, "pinning an unheld lock\n");
   5442	return cookie;
   5443}
   5444
   5445static void __lock_repin_lock(struct lockdep_map *lock, struct pin_cookie cookie)
   5446{
   5447	struct task_struct *curr = current;
   5448	int i;
   5449
   5450	if (unlikely(!debug_locks))
   5451		return;
   5452
   5453	for (i = 0; i < curr->lockdep_depth; i++) {
   5454		struct held_lock *hlock = curr->held_locks + i;
   5455
   5456		if (match_held_lock(hlock, lock)) {
   5457			hlock->pin_count += cookie.val;
   5458			return;
   5459		}
   5460	}
   5461
   5462	WARN(1, "pinning an unheld lock\n");
   5463}
   5464
   5465static void __lock_unpin_lock(struct lockdep_map *lock, struct pin_cookie cookie)
   5466{
   5467	struct task_struct *curr = current;
   5468	int i;
   5469
   5470	if (unlikely(!debug_locks))
   5471		return;
   5472
   5473	for (i = 0; i < curr->lockdep_depth; i++) {
   5474		struct held_lock *hlock = curr->held_locks + i;
   5475
   5476		if (match_held_lock(hlock, lock)) {
   5477			if (WARN(!hlock->pin_count, "unpinning an unpinned lock\n"))
   5478				return;
   5479
   5480			hlock->pin_count -= cookie.val;
   5481
   5482			if (WARN((int)hlock->pin_count < 0, "pin count corrupted\n"))
   5483				hlock->pin_count = 0;
   5484
   5485			return;
   5486		}
   5487	}
   5488
   5489	WARN(1, "unpinning an unheld lock\n");
   5490}
   5491
   5492/*
   5493 * Check whether we follow the irq-flags state precisely:
   5494 */
   5495static noinstr void check_flags(unsigned long flags)
   5496{
   5497#if defined(CONFIG_PROVE_LOCKING) && defined(CONFIG_DEBUG_LOCKDEP)
   5498	if (!debug_locks)
   5499		return;
   5500
   5501	/* Get the warning out..  */
   5502	instrumentation_begin();
   5503
   5504	if (irqs_disabled_flags(flags)) {
   5505		if (DEBUG_LOCKS_WARN_ON(lockdep_hardirqs_enabled())) {
   5506			printk("possible reason: unannotated irqs-off.\n");
   5507		}
   5508	} else {
   5509		if (DEBUG_LOCKS_WARN_ON(!lockdep_hardirqs_enabled())) {
   5510			printk("possible reason: unannotated irqs-on.\n");
   5511		}
   5512	}
   5513
   5514#ifndef CONFIG_PREEMPT_RT
   5515	/*
   5516	 * We dont accurately track softirq state in e.g.
   5517	 * hardirq contexts (such as on 4KSTACKS), so only
   5518	 * check if not in hardirq contexts:
   5519	 */
   5520	if (!hardirq_count()) {
   5521		if (softirq_count()) {
   5522			/* like the above, but with softirqs */
   5523			DEBUG_LOCKS_WARN_ON(current->softirqs_enabled);
   5524		} else {
   5525			/* lick the above, does it taste good? */
   5526			DEBUG_LOCKS_WARN_ON(!current->softirqs_enabled);
   5527		}
   5528	}
   5529#endif
   5530
   5531	if (!debug_locks)
   5532		print_irqtrace_events(current);
   5533
   5534	instrumentation_end();
   5535#endif
   5536}
   5537
   5538void lock_set_class(struct lockdep_map *lock, const char *name,
   5539		    struct lock_class_key *key, unsigned int subclass,
   5540		    unsigned long ip)
   5541{
   5542	unsigned long flags;
   5543
   5544	if (unlikely(!lockdep_enabled()))
   5545		return;
   5546
   5547	raw_local_irq_save(flags);
   5548	lockdep_recursion_inc();
   5549	check_flags(flags);
   5550	if (__lock_set_class(lock, name, key, subclass, ip))
   5551		check_chain_key(current);
   5552	lockdep_recursion_finish();
   5553	raw_local_irq_restore(flags);
   5554}
   5555EXPORT_SYMBOL_GPL(lock_set_class);
   5556
   5557void lock_downgrade(struct lockdep_map *lock, unsigned long ip)
   5558{
   5559	unsigned long flags;
   5560
   5561	if (unlikely(!lockdep_enabled()))
   5562		return;
   5563
   5564	raw_local_irq_save(flags);
   5565	lockdep_recursion_inc();
   5566	check_flags(flags);
   5567	if (__lock_downgrade(lock, ip))
   5568		check_chain_key(current);
   5569	lockdep_recursion_finish();
   5570	raw_local_irq_restore(flags);
   5571}
   5572EXPORT_SYMBOL_GPL(lock_downgrade);
   5573
   5574/* NMI context !!! */
   5575static void verify_lock_unused(struct lockdep_map *lock, struct held_lock *hlock, int subclass)
   5576{
   5577#ifdef CONFIG_PROVE_LOCKING
   5578	struct lock_class *class = look_up_lock_class(lock, subclass);
   5579	unsigned long mask = LOCKF_USED;
   5580
   5581	/* if it doesn't have a class (yet), it certainly hasn't been used yet */
   5582	if (!class)
   5583		return;
   5584
   5585	/*
   5586	 * READ locks only conflict with USED, such that if we only ever use
   5587	 * READ locks, there is no deadlock possible -- RCU.
   5588	 */
   5589	if (!hlock->read)
   5590		mask |= LOCKF_USED_READ;
   5591
   5592	if (!(class->usage_mask & mask))
   5593		return;
   5594
   5595	hlock->class_idx = class - lock_classes;
   5596
   5597	print_usage_bug(current, hlock, LOCK_USED, LOCK_USAGE_STATES);
   5598#endif
   5599}
   5600
   5601static bool lockdep_nmi(void)
   5602{
   5603	if (raw_cpu_read(lockdep_recursion))
   5604		return false;
   5605
   5606	if (!in_nmi())
   5607		return false;
   5608
   5609	return true;
   5610}
   5611
   5612/*
   5613 * read_lock() is recursive if:
   5614 * 1. We force lockdep think this way in selftests or
   5615 * 2. The implementation is not queued read/write lock or
   5616 * 3. The locker is at an in_interrupt() context.
   5617 */
   5618bool read_lock_is_recursive(void)
   5619{
   5620	return force_read_lock_recursive ||
   5621	       !IS_ENABLED(CONFIG_QUEUED_RWLOCKS) ||
   5622	       in_interrupt();
   5623}
   5624EXPORT_SYMBOL_GPL(read_lock_is_recursive);
   5625
   5626/*
   5627 * We are not always called with irqs disabled - do that here,
   5628 * and also avoid lockdep recursion:
   5629 */
   5630void lock_acquire(struct lockdep_map *lock, unsigned int subclass,
   5631			  int trylock, int read, int check,
   5632			  struct lockdep_map *nest_lock, unsigned long ip)
   5633{
   5634	unsigned long flags;
   5635
   5636	trace_lock_acquire(lock, subclass, trylock, read, check, nest_lock, ip);
   5637
   5638	if (!debug_locks)
   5639		return;
   5640
   5641	if (unlikely(!lockdep_enabled())) {
   5642		/* XXX allow trylock from NMI ?!? */
   5643		if (lockdep_nmi() && !trylock) {
   5644			struct held_lock hlock;
   5645
   5646			hlock.acquire_ip = ip;
   5647			hlock.instance = lock;
   5648			hlock.nest_lock = nest_lock;
   5649			hlock.irq_context = 2; // XXX
   5650			hlock.trylock = trylock;
   5651			hlock.read = read;
   5652			hlock.check = check;
   5653			hlock.hardirqs_off = true;
   5654			hlock.references = 0;
   5655
   5656			verify_lock_unused(lock, &hlock, subclass);
   5657		}
   5658		return;
   5659	}
   5660
   5661	raw_local_irq_save(flags);
   5662	check_flags(flags);
   5663
   5664	lockdep_recursion_inc();
   5665	__lock_acquire(lock, subclass, trylock, read, check,
   5666		       irqs_disabled_flags(flags), nest_lock, ip, 0, 0);
   5667	lockdep_recursion_finish();
   5668	raw_local_irq_restore(flags);
   5669}
   5670EXPORT_SYMBOL_GPL(lock_acquire);
   5671
   5672void lock_release(struct lockdep_map *lock, unsigned long ip)
   5673{
   5674	unsigned long flags;
   5675
   5676	trace_lock_release(lock, ip);
   5677
   5678	if (unlikely(!lockdep_enabled()))
   5679		return;
   5680
   5681	raw_local_irq_save(flags);
   5682	check_flags(flags);
   5683
   5684	lockdep_recursion_inc();
   5685	if (__lock_release(lock, ip))
   5686		check_chain_key(current);
   5687	lockdep_recursion_finish();
   5688	raw_local_irq_restore(flags);
   5689}
   5690EXPORT_SYMBOL_GPL(lock_release);
   5691
   5692noinstr int lock_is_held_type(const struct lockdep_map *lock, int read)
   5693{
   5694	unsigned long flags;
   5695	int ret = LOCK_STATE_NOT_HELD;
   5696
   5697	/*
   5698	 * Avoid false negative lockdep_assert_held() and
   5699	 * lockdep_assert_not_held().
   5700	 */
   5701	if (unlikely(!lockdep_enabled()))
   5702		return LOCK_STATE_UNKNOWN;
   5703
   5704	raw_local_irq_save(flags);
   5705	check_flags(flags);
   5706
   5707	lockdep_recursion_inc();
   5708	ret = __lock_is_held(lock, read);
   5709	lockdep_recursion_finish();
   5710	raw_local_irq_restore(flags);
   5711
   5712	return ret;
   5713}
   5714EXPORT_SYMBOL_GPL(lock_is_held_type);
   5715NOKPROBE_SYMBOL(lock_is_held_type);
   5716
   5717struct pin_cookie lock_pin_lock(struct lockdep_map *lock)
   5718{
   5719	struct pin_cookie cookie = NIL_COOKIE;
   5720	unsigned long flags;
   5721
   5722	if (unlikely(!lockdep_enabled()))
   5723		return cookie;
   5724
   5725	raw_local_irq_save(flags);
   5726	check_flags(flags);
   5727
   5728	lockdep_recursion_inc();
   5729	cookie = __lock_pin_lock(lock);
   5730	lockdep_recursion_finish();
   5731	raw_local_irq_restore(flags);
   5732
   5733	return cookie;
   5734}
   5735EXPORT_SYMBOL_GPL(lock_pin_lock);
   5736
   5737void lock_repin_lock(struct lockdep_map *lock, struct pin_cookie cookie)
   5738{
   5739	unsigned long flags;
   5740
   5741	if (unlikely(!lockdep_enabled()))
   5742		return;
   5743
   5744	raw_local_irq_save(flags);
   5745	check_flags(flags);
   5746
   5747	lockdep_recursion_inc();
   5748	__lock_repin_lock(lock, cookie);
   5749	lockdep_recursion_finish();
   5750	raw_local_irq_restore(flags);
   5751}
   5752EXPORT_SYMBOL_GPL(lock_repin_lock);
   5753
   5754void lock_unpin_lock(struct lockdep_map *lock, struct pin_cookie cookie)
   5755{
   5756	unsigned long flags;
   5757
   5758	if (unlikely(!lockdep_enabled()))
   5759		return;
   5760
   5761	raw_local_irq_save(flags);
   5762	check_flags(flags);
   5763
   5764	lockdep_recursion_inc();
   5765	__lock_unpin_lock(lock, cookie);
   5766	lockdep_recursion_finish();
   5767	raw_local_irq_restore(flags);
   5768}
   5769EXPORT_SYMBOL_GPL(lock_unpin_lock);
   5770
   5771#ifdef CONFIG_LOCK_STAT
   5772static void print_lock_contention_bug(struct task_struct *curr,
   5773				      struct lockdep_map *lock,
   5774				      unsigned long ip)
   5775{
   5776	if (!debug_locks_off())
   5777		return;
   5778	if (debug_locks_silent)
   5779		return;
   5780
   5781	pr_warn("\n");
   5782	pr_warn("=================================\n");
   5783	pr_warn("WARNING: bad contention detected!\n");
   5784	print_kernel_ident();
   5785	pr_warn("---------------------------------\n");
   5786	pr_warn("%s/%d is trying to contend lock (",
   5787		curr->comm, task_pid_nr(curr));
   5788	print_lockdep_cache(lock);
   5789	pr_cont(") at:\n");
   5790	print_ip_sym(KERN_WARNING, ip);
   5791	pr_warn("but there are no locks held!\n");
   5792	pr_warn("\nother info that might help us debug this:\n");
   5793	lockdep_print_held_locks(curr);
   5794
   5795	pr_warn("\nstack backtrace:\n");
   5796	dump_stack();
   5797}
   5798
   5799static void
   5800__lock_contended(struct lockdep_map *lock, unsigned long ip)
   5801{
   5802	struct task_struct *curr = current;
   5803	struct held_lock *hlock;
   5804	struct lock_class_stats *stats;
   5805	unsigned int depth;
   5806	int i, contention_point, contending_point;
   5807
   5808	depth = curr->lockdep_depth;
   5809	/*
   5810	 * Whee, we contended on this lock, except it seems we're not
   5811	 * actually trying to acquire anything much at all..
   5812	 */
   5813	if (DEBUG_LOCKS_WARN_ON(!depth))
   5814		return;
   5815
   5816	hlock = find_held_lock(curr, lock, depth, &i);
   5817	if (!hlock) {
   5818		print_lock_contention_bug(curr, lock, ip);
   5819		return;
   5820	}
   5821
   5822	if (hlock->instance != lock)
   5823		return;
   5824
   5825	hlock->waittime_stamp = lockstat_clock();
   5826
   5827	contention_point = lock_point(hlock_class(hlock)->contention_point, ip);
   5828	contending_point = lock_point(hlock_class(hlock)->contending_point,
   5829				      lock->ip);
   5830
   5831	stats = get_lock_stats(hlock_class(hlock));
   5832	if (contention_point < LOCKSTAT_POINTS)
   5833		stats->contention_point[contention_point]++;
   5834	if (contending_point < LOCKSTAT_POINTS)
   5835		stats->contending_point[contending_point]++;
   5836	if (lock->cpu != smp_processor_id())
   5837		stats->bounces[bounce_contended + !!hlock->read]++;
   5838}
   5839
   5840static void
   5841__lock_acquired(struct lockdep_map *lock, unsigned long ip)
   5842{
   5843	struct task_struct *curr = current;
   5844	struct held_lock *hlock;
   5845	struct lock_class_stats *stats;
   5846	unsigned int depth;
   5847	u64 now, waittime = 0;
   5848	int i, cpu;
   5849
   5850	depth = curr->lockdep_depth;
   5851	/*
   5852	 * Yay, we acquired ownership of this lock we didn't try to
   5853	 * acquire, how the heck did that happen?
   5854	 */
   5855	if (DEBUG_LOCKS_WARN_ON(!depth))
   5856		return;
   5857
   5858	hlock = find_held_lock(curr, lock, depth, &i);
   5859	if (!hlock) {
   5860		print_lock_contention_bug(curr, lock, _RET_IP_);
   5861		return;
   5862	}
   5863
   5864	if (hlock->instance != lock)
   5865		return;
   5866
   5867	cpu = smp_processor_id();
   5868	if (hlock->waittime_stamp) {
   5869		now = lockstat_clock();
   5870		waittime = now - hlock->waittime_stamp;
   5871		hlock->holdtime_stamp = now;
   5872	}
   5873
   5874	stats = get_lock_stats(hlock_class(hlock));
   5875	if (waittime) {
   5876		if (hlock->read)
   5877			lock_time_inc(&stats->read_waittime, waittime);
   5878		else
   5879			lock_time_inc(&stats->write_waittime, waittime);
   5880	}
   5881	if (lock->cpu != cpu)
   5882		stats->bounces[bounce_acquired + !!hlock->read]++;
   5883
   5884	lock->cpu = cpu;
   5885	lock->ip = ip;
   5886}
   5887
   5888void lock_contended(struct lockdep_map *lock, unsigned long ip)
   5889{
   5890	unsigned long flags;
   5891
   5892	trace_lock_contended(lock, ip);
   5893
   5894	if (unlikely(!lock_stat || !lockdep_enabled()))
   5895		return;
   5896
   5897	raw_local_irq_save(flags);
   5898	check_flags(flags);
   5899	lockdep_recursion_inc();
   5900	__lock_contended(lock, ip);
   5901	lockdep_recursion_finish();
   5902	raw_local_irq_restore(flags);
   5903}
   5904EXPORT_SYMBOL_GPL(lock_contended);
   5905
   5906void lock_acquired(struct lockdep_map *lock, unsigned long ip)
   5907{
   5908	unsigned long flags;
   5909
   5910	trace_lock_acquired(lock, ip);
   5911
   5912	if (unlikely(!lock_stat || !lockdep_enabled()))
   5913		return;
   5914
   5915	raw_local_irq_save(flags);
   5916	check_flags(flags);
   5917	lockdep_recursion_inc();
   5918	__lock_acquired(lock, ip);
   5919	lockdep_recursion_finish();
   5920	raw_local_irq_restore(flags);
   5921}
   5922EXPORT_SYMBOL_GPL(lock_acquired);
   5923#endif
   5924
   5925/*
   5926 * Used by the testsuite, sanitize the validator state
   5927 * after a simulated failure:
   5928 */
   5929
   5930void lockdep_reset(void)
   5931{
   5932	unsigned long flags;
   5933	int i;
   5934
   5935	raw_local_irq_save(flags);
   5936	lockdep_init_task(current);
   5937	memset(current->held_locks, 0, MAX_LOCK_DEPTH*sizeof(struct held_lock));
   5938	nr_hardirq_chains = 0;
   5939	nr_softirq_chains = 0;
   5940	nr_process_chains = 0;
   5941	debug_locks = 1;
   5942	for (i = 0; i < CHAINHASH_SIZE; i++)
   5943		INIT_HLIST_HEAD(chainhash_table + i);
   5944	raw_local_irq_restore(flags);
   5945}
   5946
   5947/* Remove a class from a lock chain. Must be called with the graph lock held. */
   5948static void remove_class_from_lock_chain(struct pending_free *pf,
   5949					 struct lock_chain *chain,
   5950					 struct lock_class *class)
   5951{
   5952#ifdef CONFIG_PROVE_LOCKING
   5953	int i;
   5954
   5955	for (i = chain->base; i < chain->base + chain->depth; i++) {
   5956		if (chain_hlock_class_idx(chain_hlocks[i]) != class - lock_classes)
   5957			continue;
   5958		/*
   5959		 * Each lock class occurs at most once in a lock chain so once
   5960		 * we found a match we can break out of this loop.
   5961		 */
   5962		goto free_lock_chain;
   5963	}
   5964	/* Since the chain has not been modified, return. */
   5965	return;
   5966
   5967free_lock_chain:
   5968	free_chain_hlocks(chain->base, chain->depth);
   5969	/* Overwrite the chain key for concurrent RCU readers. */
   5970	WRITE_ONCE(chain->chain_key, INITIAL_CHAIN_KEY);
   5971	dec_chains(chain->irq_context);
   5972
   5973	/*
   5974	 * Note: calling hlist_del_rcu() from inside a
   5975	 * hlist_for_each_entry_rcu() loop is safe.
   5976	 */
   5977	hlist_del_rcu(&chain->entry);
   5978	__set_bit(chain - lock_chains, pf->lock_chains_being_freed);
   5979	nr_zapped_lock_chains++;
   5980#endif
   5981}
   5982
   5983/* Must be called with the graph lock held. */
   5984static void remove_class_from_lock_chains(struct pending_free *pf,
   5985					  struct lock_class *class)
   5986{
   5987	struct lock_chain *chain;
   5988	struct hlist_head *head;
   5989	int i;
   5990
   5991	for (i = 0; i < ARRAY_SIZE(chainhash_table); i++) {
   5992		head = chainhash_table + i;
   5993		hlist_for_each_entry_rcu(chain, head, entry) {
   5994			remove_class_from_lock_chain(pf, chain, class);
   5995		}
   5996	}
   5997}
   5998
   5999/*
   6000 * Remove all references to a lock class. The caller must hold the graph lock.
   6001 */
   6002static void zap_class(struct pending_free *pf, struct lock_class *class)
   6003{
   6004	struct lock_list *entry;
   6005	int i;
   6006
   6007	WARN_ON_ONCE(!class->key);
   6008
   6009	/*
   6010	 * Remove all dependencies this lock is
   6011	 * involved in:
   6012	 */
   6013	for_each_set_bit(i, list_entries_in_use, ARRAY_SIZE(list_entries)) {
   6014		entry = list_entries + i;
   6015		if (entry->class != class && entry->links_to != class)
   6016			continue;
   6017		__clear_bit(i, list_entries_in_use);
   6018		nr_list_entries--;
   6019		list_del_rcu(&entry->entry);
   6020	}
   6021	if (list_empty(&class->locks_after) &&
   6022	    list_empty(&class->locks_before)) {
   6023		list_move_tail(&class->lock_entry, &pf->zapped);
   6024		hlist_del_rcu(&class->hash_entry);
   6025		WRITE_ONCE(class->key, NULL);
   6026		WRITE_ONCE(class->name, NULL);
   6027		nr_lock_classes--;
   6028		__clear_bit(class - lock_classes, lock_classes_in_use);
   6029		if (class - lock_classes == max_lock_class_idx)
   6030			max_lock_class_idx--;
   6031	} else {
   6032		WARN_ONCE(true, "%s() failed for class %s\n", __func__,
   6033			  class->name);
   6034	}
   6035
   6036	remove_class_from_lock_chains(pf, class);
   6037	nr_zapped_classes++;
   6038}
   6039
   6040static void reinit_class(struct lock_class *class)
   6041{
   6042	WARN_ON_ONCE(!class->lock_entry.next);
   6043	WARN_ON_ONCE(!list_empty(&class->locks_after));
   6044	WARN_ON_ONCE(!list_empty(&class->locks_before));
   6045	memset_startat(class, 0, key);
   6046	WARN_ON_ONCE(!class->lock_entry.next);
   6047	WARN_ON_ONCE(!list_empty(&class->locks_after));
   6048	WARN_ON_ONCE(!list_empty(&class->locks_before));
   6049}
   6050
   6051static inline int within(const void *addr, void *start, unsigned long size)
   6052{
   6053	return addr >= start && addr < start + size;
   6054}
   6055
   6056static bool inside_selftest(void)
   6057{
   6058	return current == lockdep_selftest_task_struct;
   6059}
   6060
   6061/* The caller must hold the graph lock. */
   6062static struct pending_free *get_pending_free(void)
   6063{
   6064	return delayed_free.pf + delayed_free.index;
   6065}
   6066
   6067static void free_zapped_rcu(struct rcu_head *cb);
   6068
   6069/*
   6070 * Schedule an RCU callback if no RCU callback is pending. Must be called with
   6071 * the graph lock held.
   6072 */
   6073static void call_rcu_zapped(struct pending_free *pf)
   6074{
   6075	WARN_ON_ONCE(inside_selftest());
   6076
   6077	if (list_empty(&pf->zapped))
   6078		return;
   6079
   6080	if (delayed_free.scheduled)
   6081		return;
   6082
   6083	delayed_free.scheduled = true;
   6084
   6085	WARN_ON_ONCE(delayed_free.pf + delayed_free.index != pf);
   6086	delayed_free.index ^= 1;
   6087
   6088	call_rcu(&delayed_free.rcu_head, free_zapped_rcu);
   6089}
   6090
   6091/* The caller must hold the graph lock. May be called from RCU context. */
   6092static void __free_zapped_classes(struct pending_free *pf)
   6093{
   6094	struct lock_class *class;
   6095
   6096	check_data_structures();
   6097
   6098	list_for_each_entry(class, &pf->zapped, lock_entry)
   6099		reinit_class(class);
   6100
   6101	list_splice_init(&pf->zapped, &free_lock_classes);
   6102
   6103#ifdef CONFIG_PROVE_LOCKING
   6104	bitmap_andnot(lock_chains_in_use, lock_chains_in_use,
   6105		      pf->lock_chains_being_freed, ARRAY_SIZE(lock_chains));
   6106	bitmap_clear(pf->lock_chains_being_freed, 0, ARRAY_SIZE(lock_chains));
   6107#endif
   6108}
   6109
   6110static void free_zapped_rcu(struct rcu_head *ch)
   6111{
   6112	struct pending_free *pf;
   6113	unsigned long flags;
   6114
   6115	if (WARN_ON_ONCE(ch != &delayed_free.rcu_head))
   6116		return;
   6117
   6118	raw_local_irq_save(flags);
   6119	lockdep_lock();
   6120
   6121	/* closed head */
   6122	pf = delayed_free.pf + (delayed_free.index ^ 1);
   6123	__free_zapped_classes(pf);
   6124	delayed_free.scheduled = false;
   6125
   6126	/*
   6127	 * If there's anything on the open list, close and start a new callback.
   6128	 */
   6129	call_rcu_zapped(delayed_free.pf + delayed_free.index);
   6130
   6131	lockdep_unlock();
   6132	raw_local_irq_restore(flags);
   6133}
   6134
   6135/*
   6136 * Remove all lock classes from the class hash table and from the
   6137 * all_lock_classes list whose key or name is in the address range [start,
   6138 * start + size). Move these lock classes to the zapped_classes list. Must
   6139 * be called with the graph lock held.
   6140 */
   6141static void __lockdep_free_key_range(struct pending_free *pf, void *start,
   6142				     unsigned long size)
   6143{
   6144	struct lock_class *class;
   6145	struct hlist_head *head;
   6146	int i;
   6147
   6148	/* Unhash all classes that were created by a module. */
   6149	for (i = 0; i < CLASSHASH_SIZE; i++) {
   6150		head = classhash_table + i;
   6151		hlist_for_each_entry_rcu(class, head, hash_entry) {
   6152			if (!within(class->key, start, size) &&
   6153			    !within(class->name, start, size))
   6154				continue;
   6155			zap_class(pf, class);
   6156		}
   6157	}
   6158}
   6159
   6160/*
   6161 * Used in module.c to remove lock classes from memory that is going to be
   6162 * freed; and possibly re-used by other modules.
   6163 *
   6164 * We will have had one synchronize_rcu() before getting here, so we're
   6165 * guaranteed nobody will look up these exact classes -- they're properly dead
   6166 * but still allocated.
   6167 */
   6168static void lockdep_free_key_range_reg(void *start, unsigned long size)
   6169{
   6170	struct pending_free *pf;
   6171	unsigned long flags;
   6172
   6173	init_data_structures_once();
   6174
   6175	raw_local_irq_save(flags);
   6176	lockdep_lock();
   6177	pf = get_pending_free();
   6178	__lockdep_free_key_range(pf, start, size);
   6179	call_rcu_zapped(pf);
   6180	lockdep_unlock();
   6181	raw_local_irq_restore(flags);
   6182
   6183	/*
   6184	 * Wait for any possible iterators from look_up_lock_class() to pass
   6185	 * before continuing to free the memory they refer to.
   6186	 */
   6187	synchronize_rcu();
   6188}
   6189
   6190/*
   6191 * Free all lockdep keys in the range [start, start+size). Does not sleep.
   6192 * Ignores debug_locks. Must only be used by the lockdep selftests.
   6193 */
   6194static void lockdep_free_key_range_imm(void *start, unsigned long size)
   6195{
   6196	struct pending_free *pf = delayed_free.pf;
   6197	unsigned long flags;
   6198
   6199	init_data_structures_once();
   6200
   6201	raw_local_irq_save(flags);
   6202	lockdep_lock();
   6203	__lockdep_free_key_range(pf, start, size);
   6204	__free_zapped_classes(pf);
   6205	lockdep_unlock();
   6206	raw_local_irq_restore(flags);
   6207}
   6208
   6209void lockdep_free_key_range(void *start, unsigned long size)
   6210{
   6211	init_data_structures_once();
   6212
   6213	if (inside_selftest())
   6214		lockdep_free_key_range_imm(start, size);
   6215	else
   6216		lockdep_free_key_range_reg(start, size);
   6217}
   6218
   6219/*
   6220 * Check whether any element of the @lock->class_cache[] array refers to a
   6221 * registered lock class. The caller must hold either the graph lock or the
   6222 * RCU read lock.
   6223 */
   6224static bool lock_class_cache_is_registered(struct lockdep_map *lock)
   6225{
   6226	struct lock_class *class;
   6227	struct hlist_head *head;
   6228	int i, j;
   6229
   6230	for (i = 0; i < CLASSHASH_SIZE; i++) {
   6231		head = classhash_table + i;
   6232		hlist_for_each_entry_rcu(class, head, hash_entry) {
   6233			for (j = 0; j < NR_LOCKDEP_CACHING_CLASSES; j++)
   6234				if (lock->class_cache[j] == class)
   6235					return true;
   6236		}
   6237	}
   6238	return false;
   6239}
   6240
   6241/* The caller must hold the graph lock. Does not sleep. */
   6242static void __lockdep_reset_lock(struct pending_free *pf,
   6243				 struct lockdep_map *lock)
   6244{
   6245	struct lock_class *class;
   6246	int j;
   6247
   6248	/*
   6249	 * Remove all classes this lock might have:
   6250	 */
   6251	for (j = 0; j < MAX_LOCKDEP_SUBCLASSES; j++) {
   6252		/*
   6253		 * If the class exists we look it up and zap it:
   6254		 */
   6255		class = look_up_lock_class(lock, j);
   6256		if (class)
   6257			zap_class(pf, class);
   6258	}
   6259	/*
   6260	 * Debug check: in the end all mapped classes should
   6261	 * be gone.
   6262	 */
   6263	if (WARN_ON_ONCE(lock_class_cache_is_registered(lock)))
   6264		debug_locks_off();
   6265}
   6266
   6267/*
   6268 * Remove all information lockdep has about a lock if debug_locks == 1. Free
   6269 * released data structures from RCU context.
   6270 */
   6271static void lockdep_reset_lock_reg(struct lockdep_map *lock)
   6272{
   6273	struct pending_free *pf;
   6274	unsigned long flags;
   6275	int locked;
   6276
   6277	raw_local_irq_save(flags);
   6278	locked = graph_lock();
   6279	if (!locked)
   6280		goto out_irq;
   6281
   6282	pf = get_pending_free();
   6283	__lockdep_reset_lock(pf, lock);
   6284	call_rcu_zapped(pf);
   6285
   6286	graph_unlock();
   6287out_irq:
   6288	raw_local_irq_restore(flags);
   6289}
   6290
   6291/*
   6292 * Reset a lock. Does not sleep. Ignores debug_locks. Must only be used by the
   6293 * lockdep selftests.
   6294 */
   6295static void lockdep_reset_lock_imm(struct lockdep_map *lock)
   6296{
   6297	struct pending_free *pf = delayed_free.pf;
   6298	unsigned long flags;
   6299
   6300	raw_local_irq_save(flags);
   6301	lockdep_lock();
   6302	__lockdep_reset_lock(pf, lock);
   6303	__free_zapped_classes(pf);
   6304	lockdep_unlock();
   6305	raw_local_irq_restore(flags);
   6306}
   6307
   6308void lockdep_reset_lock(struct lockdep_map *lock)
   6309{
   6310	init_data_structures_once();
   6311
   6312	if (inside_selftest())
   6313		lockdep_reset_lock_imm(lock);
   6314	else
   6315		lockdep_reset_lock_reg(lock);
   6316}
   6317
   6318/*
   6319 * Unregister a dynamically allocated key.
   6320 *
   6321 * Unlike lockdep_register_key(), a search is always done to find a matching
   6322 * key irrespective of debug_locks to avoid potential invalid access to freed
   6323 * memory in lock_class entry.
   6324 */
   6325void lockdep_unregister_key(struct lock_class_key *key)
   6326{
   6327	struct hlist_head *hash_head = keyhashentry(key);
   6328	struct lock_class_key *k;
   6329	struct pending_free *pf;
   6330	unsigned long flags;
   6331	bool found = false;
   6332
   6333	might_sleep();
   6334
   6335	if (WARN_ON_ONCE(static_obj(key)))
   6336		return;
   6337
   6338	raw_local_irq_save(flags);
   6339	lockdep_lock();
   6340
   6341	hlist_for_each_entry_rcu(k, hash_head, hash_entry) {
   6342		if (k == key) {
   6343			hlist_del_rcu(&k->hash_entry);
   6344			found = true;
   6345			break;
   6346		}
   6347	}
   6348	WARN_ON_ONCE(!found && debug_locks);
   6349	if (found) {
   6350		pf = get_pending_free();
   6351		__lockdep_free_key_range(pf, key, 1);
   6352		call_rcu_zapped(pf);
   6353	}
   6354	lockdep_unlock();
   6355	raw_local_irq_restore(flags);
   6356
   6357	/* Wait until is_dynamic_key() has finished accessing k->hash_entry. */
   6358	synchronize_rcu();
   6359}
   6360EXPORT_SYMBOL_GPL(lockdep_unregister_key);
   6361
   6362void __init lockdep_init(void)
   6363{
   6364	printk("Lock dependency validator: Copyright (c) 2006 Red Hat, Inc., Ingo Molnar\n");
   6365
   6366	printk("... MAX_LOCKDEP_SUBCLASSES:  %lu\n", MAX_LOCKDEP_SUBCLASSES);
   6367	printk("... MAX_LOCK_DEPTH:          %lu\n", MAX_LOCK_DEPTH);
   6368	printk("... MAX_LOCKDEP_KEYS:        %lu\n", MAX_LOCKDEP_KEYS);
   6369	printk("... CLASSHASH_SIZE:          %lu\n", CLASSHASH_SIZE);
   6370	printk("... MAX_LOCKDEP_ENTRIES:     %lu\n", MAX_LOCKDEP_ENTRIES);
   6371	printk("... MAX_LOCKDEP_CHAINS:      %lu\n", MAX_LOCKDEP_CHAINS);
   6372	printk("... CHAINHASH_SIZE:          %lu\n", CHAINHASH_SIZE);
   6373
   6374	printk(" memory used by lock dependency info: %zu kB\n",
   6375	       (sizeof(lock_classes) +
   6376		sizeof(lock_classes_in_use) +
   6377		sizeof(classhash_table) +
   6378		sizeof(list_entries) +
   6379		sizeof(list_entries_in_use) +
   6380		sizeof(chainhash_table) +
   6381		sizeof(delayed_free)
   6382#ifdef CONFIG_PROVE_LOCKING
   6383		+ sizeof(lock_cq)
   6384		+ sizeof(lock_chains)
   6385		+ sizeof(lock_chains_in_use)
   6386		+ sizeof(chain_hlocks)
   6387#endif
   6388		) / 1024
   6389		);
   6390
   6391#if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING)
   6392	printk(" memory used for stack traces: %zu kB\n",
   6393	       (sizeof(stack_trace) + sizeof(stack_trace_hash)) / 1024
   6394	       );
   6395#endif
   6396
   6397	printk(" per task-struct memory footprint: %zu bytes\n",
   6398	       sizeof(((struct task_struct *)NULL)->held_locks));
   6399}
   6400
   6401static void
   6402print_freed_lock_bug(struct task_struct *curr, const void *mem_from,
   6403		     const void *mem_to, struct held_lock *hlock)
   6404{
   6405	if (!debug_locks_off())
   6406		return;
   6407	if (debug_locks_silent)
   6408		return;
   6409
   6410	pr_warn("\n");
   6411	pr_warn("=========================\n");
   6412	pr_warn("WARNING: held lock freed!\n");
   6413	print_kernel_ident();
   6414	pr_warn("-------------------------\n");
   6415	pr_warn("%s/%d is freeing memory %px-%px, with a lock still held there!\n",
   6416		curr->comm, task_pid_nr(curr), mem_from, mem_to-1);
   6417	print_lock(hlock);
   6418	lockdep_print_held_locks(curr);
   6419
   6420	pr_warn("\nstack backtrace:\n");
   6421	dump_stack();
   6422}
   6423
   6424static inline int not_in_range(const void* mem_from, unsigned long mem_len,
   6425				const void* lock_from, unsigned long lock_len)
   6426{
   6427	return lock_from + lock_len <= mem_from ||
   6428		mem_from + mem_len <= lock_from;
   6429}
   6430
   6431/*
   6432 * Called when kernel memory is freed (or unmapped), or if a lock
   6433 * is destroyed or reinitialized - this code checks whether there is
   6434 * any held lock in the memory range of <from> to <to>:
   6435 */
   6436void debug_check_no_locks_freed(const void *mem_from, unsigned long mem_len)
   6437{
   6438	struct task_struct *curr = current;
   6439	struct held_lock *hlock;
   6440	unsigned long flags;
   6441	int i;
   6442
   6443	if (unlikely(!debug_locks))
   6444		return;
   6445
   6446	raw_local_irq_save(flags);
   6447	for (i = 0; i < curr->lockdep_depth; i++) {
   6448		hlock = curr->held_locks + i;
   6449
   6450		if (not_in_range(mem_from, mem_len, hlock->instance,
   6451					sizeof(*hlock->instance)))
   6452			continue;
   6453
   6454		print_freed_lock_bug(curr, mem_from, mem_from + mem_len, hlock);
   6455		break;
   6456	}
   6457	raw_local_irq_restore(flags);
   6458}
   6459EXPORT_SYMBOL_GPL(debug_check_no_locks_freed);
   6460
   6461static void print_held_locks_bug(void)
   6462{
   6463	if (!debug_locks_off())
   6464		return;
   6465	if (debug_locks_silent)
   6466		return;
   6467
   6468	pr_warn("\n");
   6469	pr_warn("====================================\n");
   6470	pr_warn("WARNING: %s/%d still has locks held!\n",
   6471	       current->comm, task_pid_nr(current));
   6472	print_kernel_ident();
   6473	pr_warn("------------------------------------\n");
   6474	lockdep_print_held_locks(current);
   6475	pr_warn("\nstack backtrace:\n");
   6476	dump_stack();
   6477}
   6478
   6479void debug_check_no_locks_held(void)
   6480{
   6481	if (unlikely(current->lockdep_depth > 0))
   6482		print_held_locks_bug();
   6483}
   6484EXPORT_SYMBOL_GPL(debug_check_no_locks_held);
   6485
   6486#ifdef __KERNEL__
   6487void debug_show_all_locks(void)
   6488{
   6489	struct task_struct *g, *p;
   6490
   6491	if (unlikely(!debug_locks)) {
   6492		pr_warn("INFO: lockdep is turned off.\n");
   6493		return;
   6494	}
   6495	pr_warn("\nShowing all locks held in the system:\n");
   6496
   6497	rcu_read_lock();
   6498	for_each_process_thread(g, p) {
   6499		if (!p->lockdep_depth)
   6500			continue;
   6501		lockdep_print_held_locks(p);
   6502		touch_nmi_watchdog();
   6503		touch_all_softlockup_watchdogs();
   6504	}
   6505	rcu_read_unlock();
   6506
   6507	pr_warn("\n");
   6508	pr_warn("=============================================\n\n");
   6509}
   6510EXPORT_SYMBOL_GPL(debug_show_all_locks);
   6511#endif
   6512
   6513/*
   6514 * Careful: only use this function if you are sure that
   6515 * the task cannot run in parallel!
   6516 */
   6517void debug_show_held_locks(struct task_struct *task)
   6518{
   6519	if (unlikely(!debug_locks)) {
   6520		printk("INFO: lockdep is turned off.\n");
   6521		return;
   6522	}
   6523	lockdep_print_held_locks(task);
   6524}
   6525EXPORT_SYMBOL_GPL(debug_show_held_locks);
   6526
   6527asmlinkage __visible void lockdep_sys_exit(void)
   6528{
   6529	struct task_struct *curr = current;
   6530
   6531	if (unlikely(curr->lockdep_depth)) {
   6532		if (!debug_locks_off())
   6533			return;
   6534		pr_warn("\n");
   6535		pr_warn("================================================\n");
   6536		pr_warn("WARNING: lock held when returning to user space!\n");
   6537		print_kernel_ident();
   6538		pr_warn("------------------------------------------------\n");
   6539		pr_warn("%s/%d is leaving the kernel with locks still held!\n",
   6540				curr->comm, curr->pid);
   6541		lockdep_print_held_locks(curr);
   6542	}
   6543
   6544	/*
   6545	 * The lock history for each syscall should be independent. So wipe the
   6546	 * slate clean on return to userspace.
   6547	 */
   6548	lockdep_invariant_state(false);
   6549}
   6550
   6551void lockdep_rcu_suspicious(const char *file, const int line, const char *s)
   6552{
   6553	struct task_struct *curr = current;
   6554	int dl = READ_ONCE(debug_locks);
   6555
   6556	/* Note: the following can be executed concurrently, so be careful. */
   6557	pr_warn("\n");
   6558	pr_warn("=============================\n");
   6559	pr_warn("WARNING: suspicious RCU usage\n");
   6560	print_kernel_ident();
   6561	pr_warn("-----------------------------\n");
   6562	pr_warn("%s:%d %s!\n", file, line, s);
   6563	pr_warn("\nother info that might help us debug this:\n\n");
   6564	pr_warn("\n%srcu_scheduler_active = %d, debug_locks = %d\n%s",
   6565	       !rcu_lockdep_current_cpu_online()
   6566			? "RCU used illegally from offline CPU!\n"
   6567			: "",
   6568	       rcu_scheduler_active, dl,
   6569	       dl ? "" : "Possible false positive due to lockdep disabling via debug_locks = 0\n");
   6570
   6571	/*
   6572	 * If a CPU is in the RCU-free window in idle (ie: in the section
   6573	 * between rcu_idle_enter() and rcu_idle_exit(), then RCU
   6574	 * considers that CPU to be in an "extended quiescent state",
   6575	 * which means that RCU will be completely ignoring that CPU.
   6576	 * Therefore, rcu_read_lock() and friends have absolutely no
   6577	 * effect on a CPU running in that state. In other words, even if
   6578	 * such an RCU-idle CPU has called rcu_read_lock(), RCU might well
   6579	 * delete data structures out from under it.  RCU really has no
   6580	 * choice here: we need to keep an RCU-free window in idle where
   6581	 * the CPU may possibly enter into low power mode. This way we can
   6582	 * notice an extended quiescent state to other CPUs that started a grace
   6583	 * period. Otherwise we would delay any grace period as long as we run
   6584	 * in the idle task.
   6585	 *
   6586	 * So complain bitterly if someone does call rcu_read_lock(),
   6587	 * rcu_read_lock_bh() and so on from extended quiescent states.
   6588	 */
   6589	if (!rcu_is_watching())
   6590		pr_warn("RCU used illegally from extended quiescent state!\n");
   6591
   6592	lockdep_print_held_locks(curr);
   6593	pr_warn("\nstack backtrace:\n");
   6594	dump_stack();
   6595}
   6596EXPORT_SYMBOL_GPL(lockdep_rcu_suspicious);