lockdep.h 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579
  1. /*
  2. * Runtime locking correctness validator
  3. *
  4. * Copyright (C) 2006,2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
  5. * Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra <pzijlstr@redhat.com>
  6. *
  7. * see Documentation/lockdep-design.txt for more details.
  8. */
  9. #ifndef __LINUX_LOCKDEP_H
  10. #define __LINUX_LOCKDEP_H
  11. struct task_struct;
  12. struct lockdep_map;
  13. /* for sysctl */
  14. extern int prove_locking;
  15. extern int lock_stat;
  16. #ifdef CONFIG_LOCKDEP
  17. #include <linux/linkage.h>
  18. #include <linux/list.h>
  19. #include <linux/debug_locks.h>
  20. #include <linux/stacktrace.h>
  21. /*
  22. * We'd rather not expose kernel/lockdep_states.h this wide, but we do need
  23. * the total number of states... :-(
  24. */
  25. #define XXX_LOCK_USAGE_STATES (1+3*4)
  26. #define MAX_LOCKDEP_SUBCLASSES 8UL
  27. /*
  28. * NR_LOCKDEP_CACHING_CLASSES ... Number of classes
  29. * cached in the instance of lockdep_map
  30. *
  31. * Currently main class (subclass == 0) and signle depth subclass
  32. * are cached in lockdep_map. This optimization is mainly targeting
  33. * on rq->lock. double_rq_lock() acquires this highly competitive with
  34. * single depth.
  35. */
  36. #define NR_LOCKDEP_CACHING_CLASSES 2
  37. /*
  38. * Lock-classes are keyed via unique addresses, by embedding the
  39. * lockclass-key into the kernel (or module) .data section. (For
  40. * static locks we use the lock address itself as the key.)
  41. */
  42. struct lockdep_subclass_key {
  43. char __one_byte;
  44. } __attribute__ ((__packed__));
  45. struct lock_class_key {
  46. struct lockdep_subclass_key subkeys[MAX_LOCKDEP_SUBCLASSES];
  47. };
  48. extern struct lock_class_key __lockdep_no_validate__;
  49. #define LOCKSTAT_POINTS 4
  50. /*
  51. * The lock-class itself:
  52. */
  53. struct lock_class {
  54. /*
  55. * class-hash:
  56. */
  57. struct list_head hash_entry;
  58. /*
  59. * global list of all lock-classes:
  60. */
  61. struct list_head lock_entry;
  62. struct lockdep_subclass_key *key;
  63. unsigned int subclass;
  64. unsigned int dep_gen_id;
  65. /*
  66. * IRQ/softirq usage tracking bits:
  67. */
  68. unsigned long usage_mask;
  69. struct stack_trace usage_traces[XXX_LOCK_USAGE_STATES];
  70. /*
  71. * These fields represent a directed graph of lock dependencies,
  72. * to every node we attach a list of "forward" and a list of
  73. * "backward" graph nodes.
  74. */
  75. struct list_head locks_after, locks_before;
  76. /*
  77. * Generation counter, when doing certain classes of graph walking,
  78. * to ensure that we check one node only once:
  79. */
  80. unsigned int version;
  81. /*
  82. * Statistics counter:
  83. */
  84. unsigned long ops;
  85. const char *name;
  86. int name_version;
  87. #ifdef CONFIG_LOCK_STAT
  88. unsigned long contention_point[LOCKSTAT_POINTS];
  89. unsigned long contending_point[LOCKSTAT_POINTS];
  90. #endif
  91. };
  92. #ifdef CONFIG_LOCK_STAT
  93. struct lock_time {
  94. s64 min;
  95. s64 max;
  96. s64 total;
  97. unsigned long nr;
  98. };
  99. enum bounce_type {
  100. bounce_acquired_write,
  101. bounce_acquired_read,
  102. bounce_contended_write,
  103. bounce_contended_read,
  104. nr_bounce_types,
  105. bounce_acquired = bounce_acquired_write,
  106. bounce_contended = bounce_contended_write,
  107. };
  108. struct lock_class_stats {
  109. unsigned long contention_point[4];
  110. unsigned long contending_point[4];
  111. struct lock_time read_waittime;
  112. struct lock_time write_waittime;
  113. struct lock_time read_holdtime;
  114. struct lock_time write_holdtime;
  115. unsigned long bounces[nr_bounce_types];
  116. };
  117. struct lock_class_stats lock_stats(struct lock_class *class);
  118. void clear_lock_stats(struct lock_class *class);
  119. #endif
  120. /*
  121. * Map the lock object (the lock instance) to the lock-class object.
  122. * This is embedded into specific lock instances:
  123. */
  124. struct lockdep_map {
  125. struct lock_class_key *key;
  126. struct lock_class *class_cache[NR_LOCKDEP_CACHING_CLASSES];
  127. const char *name;
  128. #ifdef CONFIG_LOCK_STAT
  129. int cpu;
  130. unsigned long ip;
  131. #endif
  132. };
  133. static inline void lockdep_copy_map(struct lockdep_map *to,
  134. struct lockdep_map *from)
  135. {
  136. int i;
  137. *to = *from;
  138. /*
  139. * Since the class cache can be modified concurrently we could observe
  140. * half pointers (64bit arch using 32bit copy insns). Therefore clear
  141. * the caches and take the performance hit.
  142. *
  143. * XXX it doesn't work well with lockdep_set_class_and_subclass(), since
  144. * that relies on cache abuse.
  145. */
  146. for (i = 0; i < NR_LOCKDEP_CACHING_CLASSES; i++)
  147. to->class_cache[i] = NULL;
  148. }
  149. /*
  150. * Every lock has a list of other locks that were taken after it.
  151. * We only grow the list, never remove from it:
  152. */
  153. struct lock_list {
  154. struct list_head entry;
  155. struct lock_class *class;
  156. struct stack_trace trace;
  157. int distance;
  158. /*
  159. * The parent field is used to implement breadth-first search, and the
  160. * bit 0 is reused to indicate if the lock has been accessed in BFS.
  161. */
  162. struct lock_list *parent;
  163. };
  164. /*
  165. * We record lock dependency chains, so that we can cache them:
  166. */
  167. struct lock_chain {
  168. u8 irq_context;
  169. u8 depth;
  170. u16 base;
  171. struct list_head entry;
  172. u64 chain_key;
  173. };
  174. #define MAX_LOCKDEP_KEYS_BITS 13
  175. /*
  176. * Subtract one because we offset hlock->class_idx by 1 in order
  177. * to make 0 mean no class. This avoids overflowing the class_idx
  178. * bitfield and hitting the BUG in hlock_class().
  179. */
  180. #define MAX_LOCKDEP_KEYS ((1UL << MAX_LOCKDEP_KEYS_BITS) - 1)
  181. struct held_lock {
  182. /*
  183. * One-way hash of the dependency chain up to this point. We
  184. * hash the hashes step by step as the dependency chain grows.
  185. *
  186. * We use it for dependency-caching and we skip detection
  187. * passes and dependency-updates if there is a cache-hit, so
  188. * it is absolutely critical for 100% coverage of the validator
  189. * to have a unique key value for every unique dependency path
  190. * that can occur in the system, to make a unique hash value
  191. * as likely as possible - hence the 64-bit width.
  192. *
  193. * The task struct holds the current hash value (initialized
  194. * with zero), here we store the previous hash value:
  195. */
  196. u64 prev_chain_key;
  197. unsigned long acquire_ip;
  198. struct lockdep_map *instance;
  199. struct lockdep_map *nest_lock;
  200. #ifdef CONFIG_LOCK_STAT
  201. u64 waittime_stamp;
  202. u64 holdtime_stamp;
  203. #endif
  204. unsigned int class_idx:MAX_LOCKDEP_KEYS_BITS;
  205. /*
  206. * The lock-stack is unified in that the lock chains of interrupt
  207. * contexts nest ontop of process context chains, but we 'separate'
  208. * the hashes by starting with 0 if we cross into an interrupt
  209. * context, and we also keep do not add cross-context lock
  210. * dependencies - the lock usage graph walking covers that area
  211. * anyway, and we'd just unnecessarily increase the number of
  212. * dependencies otherwise. [Note: hardirq and softirq contexts
  213. * are separated from each other too.]
  214. *
  215. * The following field is used to detect when we cross into an
  216. * interrupt context:
  217. */
  218. unsigned int irq_context:2; /* bit 0 - soft, bit 1 - hard */
  219. unsigned int trylock:1; /* 16 bits */
  220. unsigned int read:2; /* see lock_acquire() comment */
  221. unsigned int check:2; /* see lock_acquire() comment */
  222. unsigned int hardirqs_off:1;
  223. unsigned int references:11; /* 32 bits */
  224. };
  225. /*
  226. * Initialization, self-test and debugging-output methods:
  227. */
  228. extern void lockdep_init(void);
  229. extern void lockdep_info(void);
  230. extern void lockdep_reset(void);
  231. extern void lockdep_reset_lock(struct lockdep_map *lock);
  232. extern void lockdep_free_key_range(void *start, unsigned long size);
  233. extern void lockdep_sys_exit(void);
  234. extern void lockdep_off(void);
  235. extern void lockdep_on(void);
  236. /*
  237. * These methods are used by specific locking variants (spinlocks,
  238. * rwlocks, mutexes and rwsems) to pass init/acquire/release events
  239. * to lockdep:
  240. */
  241. extern void lockdep_init_map(struct lockdep_map *lock, const char *name,
  242. struct lock_class_key *key, int subclass);
  243. /*
  244. * To initialize a lockdep_map statically use this macro.
  245. * Note that _name must not be NULL.
  246. */
  247. #define STATIC_LOCKDEP_MAP_INIT(_name, _key) \
  248. { .name = (_name), .key = (void *)(_key), }
  249. /*
  250. * Reinitialize a lock key - for cases where there is special locking or
  251. * special initialization of locks so that the validator gets the scope
  252. * of dependencies wrong: they are either too broad (they need a class-split)
  253. * or they are too narrow (they suffer from a false class-split):
  254. */
  255. #define lockdep_set_class(lock, key) \
  256. lockdep_init_map(&(lock)->dep_map, #key, key, 0)
  257. #define lockdep_set_class_and_name(lock, key, name) \
  258. lockdep_init_map(&(lock)->dep_map, name, key, 0)
  259. #define lockdep_set_class_and_subclass(lock, key, sub) \
  260. lockdep_init_map(&(lock)->dep_map, #key, key, sub)
  261. #define lockdep_set_subclass(lock, sub) \
  262. lockdep_init_map(&(lock)->dep_map, #lock, \
  263. (lock)->dep_map.key, sub)
  264. #define lockdep_set_novalidate_class(lock) \
  265. lockdep_set_class(lock, &__lockdep_no_validate__)
  266. /*
  267. * Compare locking classes
  268. */
  269. #define lockdep_match_class(lock, key) lockdep_match_key(&(lock)->dep_map, key)
  270. static inline int lockdep_match_key(struct lockdep_map *lock,
  271. struct lock_class_key *key)
  272. {
  273. return lock->key == key;
  274. }
  275. /*
  276. * Acquire a lock.
  277. *
  278. * Values for "read":
  279. *
  280. * 0: exclusive (write) acquire
  281. * 1: read-acquire (no recursion allowed)
  282. * 2: read-acquire with same-instance recursion allowed
  283. *
  284. * Values for check:
  285. *
  286. * 0: disabled
  287. * 1: simple checks (freeing, held-at-exit-time, etc.)
  288. * 2: full validation
  289. */
  290. extern void lock_acquire(struct lockdep_map *lock, unsigned int subclass,
  291. int trylock, int read, int check,
  292. struct lockdep_map *nest_lock, unsigned long ip);
  293. extern void lock_release(struct lockdep_map *lock, int nested,
  294. unsigned long ip);
  295. #define lockdep_is_held(lock) lock_is_held(&(lock)->dep_map)
  296. extern int lock_is_held(struct lockdep_map *lock);
  297. extern void lock_set_class(struct lockdep_map *lock, const char *name,
  298. struct lock_class_key *key, unsigned int subclass,
  299. unsigned long ip);
  300. static inline void lock_set_subclass(struct lockdep_map *lock,
  301. unsigned int subclass, unsigned long ip)
  302. {
  303. lock_set_class(lock, lock->name, lock->key, subclass, ip);
  304. }
  305. extern void lockdep_set_current_reclaim_state(gfp_t gfp_mask);
  306. extern void lockdep_clear_current_reclaim_state(void);
  307. extern void lockdep_trace_alloc(gfp_t mask);
  308. # define INIT_LOCKDEP .lockdep_recursion = 0, .lockdep_reclaim_gfp = 0,
  309. #define lockdep_depth(tsk) (debug_locks ? (tsk)->lockdep_depth : 0)
  310. #define lockdep_assert_held(l) WARN_ON(debug_locks && !lockdep_is_held(l))
  311. #define lockdep_recursing(tsk) ((tsk)->lockdep_recursion)
  312. #else /* !LOCKDEP */
  313. static inline void lockdep_off(void)
  314. {
  315. }
  316. static inline void lockdep_on(void)
  317. {
  318. }
  319. # define lock_acquire(l, s, t, r, c, n, i) do { } while (0)
  320. # define lock_release(l, n, i) do { } while (0)
  321. # define lock_set_class(l, n, k, s, i) do { } while (0)
  322. # define lock_set_subclass(l, s, i) do { } while (0)
  323. # define lockdep_set_current_reclaim_state(g) do { } while (0)
  324. # define lockdep_clear_current_reclaim_state() do { } while (0)
  325. # define lockdep_trace_alloc(g) do { } while (0)
  326. # define lockdep_init() do { } while (0)
  327. # define lockdep_info() do { } while (0)
  328. # define lockdep_init_map(lock, name, key, sub) \
  329. do { (void)(name); (void)(key); } while (0)
  330. # define lockdep_set_class(lock, key) do { (void)(key); } while (0)
  331. # define lockdep_set_class_and_name(lock, key, name) \
  332. do { (void)(key); (void)(name); } while (0)
  333. #define lockdep_set_class_and_subclass(lock, key, sub) \
  334. do { (void)(key); } while (0)
  335. #define lockdep_set_subclass(lock, sub) do { } while (0)
  336. #define lockdep_set_novalidate_class(lock) do { } while (0)
  337. /*
  338. * We don't define lockdep_match_class() and lockdep_match_key() for !LOCKDEP
  339. * case since the result is not well defined and the caller should rather
  340. * #ifdef the call himself.
  341. */
  342. # define INIT_LOCKDEP
  343. # define lockdep_reset() do { debug_locks = 1; } while (0)
  344. # define lockdep_free_key_range(start, size) do { } while (0)
  345. # define lockdep_sys_exit() do { } while (0)
  346. /*
  347. * The class key takes no space if lockdep is disabled:
  348. */
  349. struct lock_class_key { };
  350. #define lockdep_depth(tsk) (0)
  351. #define lockdep_assert_held(l) do { } while (0)
  352. #define lockdep_recursing(tsk) (0)
  353. #endif /* !LOCKDEP */
  354. #ifdef CONFIG_LOCK_STAT
  355. extern void lock_contended(struct lockdep_map *lock, unsigned long ip);
  356. extern void lock_acquired(struct lockdep_map *lock, unsigned long ip);
  357. #define LOCK_CONTENDED(_lock, try, lock) \
  358. do { \
  359. if (!try(_lock)) { \
  360. lock_contended(&(_lock)->dep_map, _RET_IP_); \
  361. lock(_lock); \
  362. } \
  363. lock_acquired(&(_lock)->dep_map, _RET_IP_); \
  364. } while (0)
  365. #else /* CONFIG_LOCK_STAT */
  366. #define lock_contended(lockdep_map, ip) do {} while (0)
  367. #define lock_acquired(lockdep_map, ip) do {} while (0)
  368. #define LOCK_CONTENDED(_lock, try, lock) \
  369. lock(_lock)
  370. #endif /* CONFIG_LOCK_STAT */
  371. #ifdef CONFIG_LOCKDEP
  372. /*
  373. * On lockdep we dont want the hand-coded irq-enable of
  374. * _raw_*_lock_flags() code, because lockdep assumes
  375. * that interrupts are not re-enabled during lock-acquire:
  376. */
  377. #define LOCK_CONTENDED_FLAGS(_lock, try, lock, lockfl, flags) \
  378. LOCK_CONTENDED((_lock), (try), (lock))
  379. #else /* CONFIG_LOCKDEP */
  380. #define LOCK_CONTENDED_FLAGS(_lock, try, lock, lockfl, flags) \
  381. lockfl((_lock), (flags))
  382. #endif /* CONFIG_LOCKDEP */
  383. #ifdef CONFIG_TRACE_IRQFLAGS
  384. extern void print_irqtrace_events(struct task_struct *curr);
  385. #else
  386. static inline void print_irqtrace_events(struct task_struct *curr)
  387. {
  388. }
  389. #endif
  390. /*
  391. * For trivial one-depth nesting of a lock-class, the following
  392. * global define can be used. (Subsystems with multiple levels
  393. * of nesting should define their own lock-nesting subclasses.)
  394. */
  395. #define SINGLE_DEPTH_NESTING 1
  396. /*
  397. * Map the dependency ops to NOP or to real lockdep ops, depending
  398. * on the per lock-class debug mode:
  399. */
  400. #ifdef CONFIG_DEBUG_LOCK_ALLOC
  401. # ifdef CONFIG_PROVE_LOCKING
  402. # define spin_acquire(l, s, t, i) lock_acquire(l, s, t, 0, 2, NULL, i)
  403. # define spin_acquire_nest(l, s, t, n, i) lock_acquire(l, s, t, 0, 2, n, i)
  404. # else
  405. # define spin_acquire(l, s, t, i) lock_acquire(l, s, t, 0, 1, NULL, i)
  406. # define spin_acquire_nest(l, s, t, n, i) lock_acquire(l, s, t, 0, 1, NULL, i)
  407. # endif
  408. # define spin_release(l, n, i) lock_release(l, n, i)
  409. #else
  410. # define spin_acquire(l, s, t, i) do { } while (0)
  411. # define spin_release(l, n, i) do { } while (0)
  412. #endif
  413. #ifdef CONFIG_DEBUG_LOCK_ALLOC
  414. # ifdef CONFIG_PROVE_LOCKING
  415. # define rwlock_acquire(l, s, t, i) lock_acquire(l, s, t, 0, 2, NULL, i)
  416. # define rwlock_acquire_read(l, s, t, i) lock_acquire(l, s, t, 2, 2, NULL, i)
  417. # else
  418. # define rwlock_acquire(l, s, t, i) lock_acquire(l, s, t, 0, 1, NULL, i)
  419. # define rwlock_acquire_read(l, s, t, i) lock_acquire(l, s, t, 2, 1, NULL, i)
  420. # endif
  421. # define rwlock_release(l, n, i) lock_release(l, n, i)
  422. #else
  423. # define rwlock_acquire(l, s, t, i) do { } while (0)
  424. # define rwlock_acquire_read(l, s, t, i) do { } while (0)
  425. # define rwlock_release(l, n, i) do { } while (0)
  426. #endif
  427. #ifdef CONFIG_DEBUG_LOCK_ALLOC
  428. # ifdef CONFIG_PROVE_LOCKING
  429. # define mutex_acquire(l, s, t, i) lock_acquire(l, s, t, 0, 2, NULL, i)
  430. # define mutex_acquire_nest(l, s, t, n, i) lock_acquire(l, s, t, 0, 2, n, i)
  431. # else
  432. # define mutex_acquire(l, s, t, i) lock_acquire(l, s, t, 0, 1, NULL, i)
  433. # define mutex_acquire_nest(l, s, t, n, i) lock_acquire(l, s, t, 0, 1, n, i)
  434. # endif
  435. # define mutex_release(l, n, i) lock_release(l, n, i)
  436. #else
  437. # define mutex_acquire(l, s, t, i) do { } while (0)
  438. # define mutex_acquire_nest(l, s, t, n, i) do { } while (0)
  439. # define mutex_release(l, n, i) do { } while (0)
  440. #endif
  441. #ifdef CONFIG_DEBUG_LOCK_ALLOC
  442. # ifdef CONFIG_PROVE_LOCKING
  443. # define rwsem_acquire(l, s, t, i) lock_acquire(l, s, t, 0, 2, NULL, i)
  444. # define rwsem_acquire_nest(l, s, t, n, i) lock_acquire(l, s, t, 0, 2, n, i)
  445. # define rwsem_acquire_read(l, s, t, i) lock_acquire(l, s, t, 1, 2, NULL, i)
  446. # else
  447. # define rwsem_acquire(l, s, t, i) lock_acquire(l, s, t, 0, 1, NULL, i)
  448. # define rwsem_acquire_nest(l, s, t, n, i) lock_acquire(l, s, t, 0, 1, n, i)
  449. # define rwsem_acquire_read(l, s, t, i) lock_acquire(l, s, t, 1, 1, NULL, i)
  450. # endif
  451. # define rwsem_release(l, n, i) lock_release(l, n, i)
  452. #else
  453. # define rwsem_acquire(l, s, t, i) do { } while (0)
  454. # define rwsem_acquire_nest(l, s, t, n, i) do { } while (0)
  455. # define rwsem_acquire_read(l, s, t, i) do { } while (0)
  456. # define rwsem_release(l, n, i) do { } while (0)
  457. #endif
  458. #ifdef CONFIG_DEBUG_LOCK_ALLOC
  459. # ifdef CONFIG_PROVE_LOCKING
  460. # define lock_map_acquire(l) lock_acquire(l, 0, 0, 0, 2, NULL, _THIS_IP_)
  461. # define lock_map_acquire_read(l) lock_acquire(l, 0, 0, 2, 2, NULL, _THIS_IP_)
  462. # else
  463. # define lock_map_acquire(l) lock_acquire(l, 0, 0, 0, 1, NULL, _THIS_IP_)
  464. # define lock_map_acquire_read(l) lock_acquire(l, 0, 0, 2, 1, NULL, _THIS_IP_)
  465. # endif
  466. # define lock_map_release(l) lock_release(l, 1, _THIS_IP_)
  467. #else
  468. # define lock_map_acquire(l) do { } while (0)
  469. # define lock_map_acquire_read(l) do { } while (0)
  470. # define lock_map_release(l) do { } while (0)
  471. #endif
  472. #ifdef CONFIG_PROVE_LOCKING
  473. # define might_lock(lock) \
  474. do { \
  475. typecheck(struct lockdep_map *, &(lock)->dep_map); \
  476. lock_acquire(&(lock)->dep_map, 0, 0, 0, 2, NULL, _THIS_IP_); \
  477. lock_release(&(lock)->dep_map, 0, _THIS_IP_); \
  478. } while (0)
  479. # define might_lock_read(lock) \
  480. do { \
  481. typecheck(struct lockdep_map *, &(lock)->dep_map); \
  482. lock_acquire(&(lock)->dep_map, 0, 0, 1, 2, NULL, _THIS_IP_); \
  483. lock_release(&(lock)->dep_map, 0, _THIS_IP_); \
  484. } while (0)
  485. #else
  486. # define might_lock(lock) do { } while (0)
  487. # define might_lock_read(lock) do { } while (0)
  488. #endif
  489. #ifdef CONFIG_PROVE_RCU
  490. void lockdep_rcu_suspicious(const char *file, const int line, const char *s);
  491. #endif
  492. #endif /* __LINUX_LOCKDEP_H */