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