lockdep.h 16 KB

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