block: Fix the starving writes bug in the anticipatory IO scheduler
[pandora-kernel.git] / kernel / lockdep_proc.c
1 /*
2  * kernel/lockdep_proc.c
3  *
4  * Runtime locking correctness validator
5  *
6  * Started by Ingo Molnar:
7  *
8  *  Copyright (C) 2006,2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
9  *  Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra <pzijlstr@redhat.com>
10  *
11  * Code for /proc/lockdep and /proc/lockdep_stats:
12  *
13  */
14 #include <linux/module.h>
15 #include <linux/proc_fs.h>
16 #include <linux/seq_file.h>
17 #include <linux/kallsyms.h>
18 #include <linux/debug_locks.h>
19 #include <linux/vmalloc.h>
20 #include <linux/sort.h>
21 #include <asm/uaccess.h>
22 #include <asm/div64.h>
23
24 #include "lockdep_internals.h"
25
26 static void *l_next(struct seq_file *m, void *v, loff_t *pos)
27 {
28         struct lock_class *class;
29
30         (*pos)++;
31
32         if (v == SEQ_START_TOKEN)
33                 class = m->private;
34         else {
35                 class = v;
36
37                 if (class->lock_entry.next != &all_lock_classes)
38                         class = list_entry(class->lock_entry.next,
39                                            struct lock_class, lock_entry);
40                 else
41                         class = NULL;
42         }
43
44         return class;
45 }
46
47 static void *l_start(struct seq_file *m, loff_t *pos)
48 {
49         struct lock_class *class;
50         loff_t i = 0;
51
52         if (*pos == 0)
53                 return SEQ_START_TOKEN;
54
55         list_for_each_entry(class, &all_lock_classes, lock_entry) {
56                 if (++i == *pos)
57                 return class;
58         }
59         return NULL;
60 }
61
62 static void l_stop(struct seq_file *m, void *v)
63 {
64 }
65
66 static unsigned long count_forward_deps(struct lock_class *class)
67 {
68         struct lock_list *entry;
69         unsigned long ret = 1;
70
71         /*
72          * Recurse this class's dependency list:
73          */
74         list_for_each_entry(entry, &class->locks_after, entry)
75                 ret += count_forward_deps(entry->class);
76
77         return ret;
78 }
79
80 static unsigned long count_backward_deps(struct lock_class *class)
81 {
82         struct lock_list *entry;
83         unsigned long ret = 1;
84
85         /*
86          * Recurse this class's dependency list:
87          */
88         list_for_each_entry(entry, &class->locks_before, entry)
89                 ret += count_backward_deps(entry->class);
90
91         return ret;
92 }
93
94 static void print_name(struct seq_file *m, struct lock_class *class)
95 {
96         char str[128];
97         const char *name = class->name;
98
99         if (!name) {
100                 name = __get_key_name(class->key, str);
101                 seq_printf(m, "%s", name);
102         } else{
103                 seq_printf(m, "%s", name);
104                 if (class->name_version > 1)
105                         seq_printf(m, "#%d", class->name_version);
106                 if (class->subclass)
107                         seq_printf(m, "/%d", class->subclass);
108         }
109 }
110
111 static int l_show(struct seq_file *m, void *v)
112 {
113         unsigned long nr_forward_deps, nr_backward_deps;
114         struct lock_class *class = v;
115         struct lock_list *entry;
116         char c1, c2, c3, c4;
117
118         if (v == SEQ_START_TOKEN) {
119                 seq_printf(m, "all lock classes:\n");
120                 return 0;
121         }
122
123         seq_printf(m, "%p", class->key);
124 #ifdef CONFIG_DEBUG_LOCKDEP
125         seq_printf(m, " OPS:%8ld", class->ops);
126 #endif
127         nr_forward_deps = count_forward_deps(class);
128         seq_printf(m, " FD:%5ld", nr_forward_deps);
129
130         nr_backward_deps = count_backward_deps(class);
131         seq_printf(m, " BD:%5ld", nr_backward_deps);
132
133         get_usage_chars(class, &c1, &c2, &c3, &c4);
134         seq_printf(m, " %c%c%c%c", c1, c2, c3, c4);
135
136         seq_printf(m, ": ");
137         print_name(m, class);
138         seq_puts(m, "\n");
139
140         list_for_each_entry(entry, &class->locks_after, entry) {
141                 if (entry->distance == 1) {
142                         seq_printf(m, " -> [%p] ", entry->class);
143                         print_name(m, entry->class);
144                         seq_puts(m, "\n");
145                 }
146         }
147         seq_puts(m, "\n");
148
149         return 0;
150 }
151
152 static const struct seq_operations lockdep_ops = {
153         .start  = l_start,
154         .next   = l_next,
155         .stop   = l_stop,
156         .show   = l_show,
157 };
158
159 static int lockdep_open(struct inode *inode, struct file *file)
160 {
161         int res = seq_open(file, &lockdep_ops);
162         if (!res) {
163                 struct seq_file *m = file->private_data;
164
165                 if (!list_empty(&all_lock_classes))
166                         m->private = list_entry(all_lock_classes.next,
167                                         struct lock_class, lock_entry);
168                 else
169                         m->private = NULL;
170         }
171         return res;
172 }
173
174 static const struct file_operations proc_lockdep_operations = {
175         .open           = lockdep_open,
176         .read           = seq_read,
177         .llseek         = seq_lseek,
178         .release        = seq_release,
179 };
180
181 static void lockdep_stats_debug_show(struct seq_file *m)
182 {
183 #ifdef CONFIG_DEBUG_LOCKDEP
184         unsigned int hi1 = debug_atomic_read(&hardirqs_on_events),
185                      hi2 = debug_atomic_read(&hardirqs_off_events),
186                      hr1 = debug_atomic_read(&redundant_hardirqs_on),
187                      hr2 = debug_atomic_read(&redundant_hardirqs_off),
188                      si1 = debug_atomic_read(&softirqs_on_events),
189                      si2 = debug_atomic_read(&softirqs_off_events),
190                      sr1 = debug_atomic_read(&redundant_softirqs_on),
191                      sr2 = debug_atomic_read(&redundant_softirqs_off);
192
193         seq_printf(m, " chain lookup misses:           %11u\n",
194                 debug_atomic_read(&chain_lookup_misses));
195         seq_printf(m, " chain lookup hits:             %11u\n",
196                 debug_atomic_read(&chain_lookup_hits));
197         seq_printf(m, " cyclic checks:                 %11u\n",
198                 debug_atomic_read(&nr_cyclic_checks));
199         seq_printf(m, " cyclic-check recursions:       %11u\n",
200                 debug_atomic_read(&nr_cyclic_check_recursions));
201         seq_printf(m, " find-mask forwards checks:     %11u\n",
202                 debug_atomic_read(&nr_find_usage_forwards_checks));
203         seq_printf(m, " find-mask forwards recursions: %11u\n",
204                 debug_atomic_read(&nr_find_usage_forwards_recursions));
205         seq_printf(m, " find-mask backwards checks:    %11u\n",
206                 debug_atomic_read(&nr_find_usage_backwards_checks));
207         seq_printf(m, " find-mask backwards recursions:%11u\n",
208                 debug_atomic_read(&nr_find_usage_backwards_recursions));
209
210         seq_printf(m, " hardirq on events:             %11u\n", hi1);
211         seq_printf(m, " hardirq off events:            %11u\n", hi2);
212         seq_printf(m, " redundant hardirq ons:         %11u\n", hr1);
213         seq_printf(m, " redundant hardirq offs:        %11u\n", hr2);
214         seq_printf(m, " softirq on events:             %11u\n", si1);
215         seq_printf(m, " softirq off events:            %11u\n", si2);
216         seq_printf(m, " redundant softirq ons:         %11u\n", sr1);
217         seq_printf(m, " redundant softirq offs:        %11u\n", sr2);
218 #endif
219 }
220
221 static int lockdep_stats_show(struct seq_file *m, void *v)
222 {
223         struct lock_class *class;
224         unsigned long nr_unused = 0, nr_uncategorized = 0,
225                       nr_irq_safe = 0, nr_irq_unsafe = 0,
226                       nr_softirq_safe = 0, nr_softirq_unsafe = 0,
227                       nr_hardirq_safe = 0, nr_hardirq_unsafe = 0,
228                       nr_irq_read_safe = 0, nr_irq_read_unsafe = 0,
229                       nr_softirq_read_safe = 0, nr_softirq_read_unsafe = 0,
230                       nr_hardirq_read_safe = 0, nr_hardirq_read_unsafe = 0,
231                       sum_forward_deps = 0, factor = 0;
232
233         list_for_each_entry(class, &all_lock_classes, lock_entry) {
234
235                 if (class->usage_mask == 0)
236                         nr_unused++;
237                 if (class->usage_mask == LOCKF_USED)
238                         nr_uncategorized++;
239                 if (class->usage_mask & LOCKF_USED_IN_IRQ)
240                         nr_irq_safe++;
241                 if (class->usage_mask & LOCKF_ENABLED_IRQS)
242                         nr_irq_unsafe++;
243                 if (class->usage_mask & LOCKF_USED_IN_SOFTIRQ)
244                         nr_softirq_safe++;
245                 if (class->usage_mask & LOCKF_ENABLED_SOFTIRQS)
246                         nr_softirq_unsafe++;
247                 if (class->usage_mask & LOCKF_USED_IN_HARDIRQ)
248                         nr_hardirq_safe++;
249                 if (class->usage_mask & LOCKF_ENABLED_HARDIRQS)
250                         nr_hardirq_unsafe++;
251                 if (class->usage_mask & LOCKF_USED_IN_IRQ_READ)
252                         nr_irq_read_safe++;
253                 if (class->usage_mask & LOCKF_ENABLED_IRQS_READ)
254                         nr_irq_read_unsafe++;
255                 if (class->usage_mask & LOCKF_USED_IN_SOFTIRQ_READ)
256                         nr_softirq_read_safe++;
257                 if (class->usage_mask & LOCKF_ENABLED_SOFTIRQS_READ)
258                         nr_softirq_read_unsafe++;
259                 if (class->usage_mask & LOCKF_USED_IN_HARDIRQ_READ)
260                         nr_hardirq_read_safe++;
261                 if (class->usage_mask & LOCKF_ENABLED_HARDIRQS_READ)
262                         nr_hardirq_read_unsafe++;
263
264                 sum_forward_deps += count_forward_deps(class);
265         }
266 #ifdef CONFIG_DEBUG_LOCKDEP
267         DEBUG_LOCKS_WARN_ON(debug_atomic_read(&nr_unused_locks) != nr_unused);
268 #endif
269         seq_printf(m, " lock-classes:                  %11lu [max: %lu]\n",
270                         nr_lock_classes, MAX_LOCKDEP_KEYS);
271         seq_printf(m, " direct dependencies:           %11lu [max: %lu]\n",
272                         nr_list_entries, MAX_LOCKDEP_ENTRIES);
273         seq_printf(m, " indirect dependencies:         %11lu\n",
274                         sum_forward_deps);
275
276         /*
277          * Total number of dependencies:
278          *
279          * All irq-safe locks may nest inside irq-unsafe locks,
280          * plus all the other known dependencies:
281          */
282         seq_printf(m, " all direct dependencies:       %11lu\n",
283                         nr_irq_unsafe * nr_irq_safe +
284                         nr_hardirq_unsafe * nr_hardirq_safe +
285                         nr_list_entries);
286
287         /*
288          * Estimated factor between direct and indirect
289          * dependencies:
290          */
291         if (nr_list_entries)
292                 factor = sum_forward_deps / nr_list_entries;
293
294 #ifdef CONFIG_PROVE_LOCKING
295         seq_printf(m, " dependency chains:             %11lu [max: %lu]\n",
296                         nr_lock_chains, MAX_LOCKDEP_CHAINS);
297 #endif
298
299 #ifdef CONFIG_TRACE_IRQFLAGS
300         seq_printf(m, " in-hardirq chains:             %11u\n",
301                         nr_hardirq_chains);
302         seq_printf(m, " in-softirq chains:             %11u\n",
303                         nr_softirq_chains);
304 #endif
305         seq_printf(m, " in-process chains:             %11u\n",
306                         nr_process_chains);
307         seq_printf(m, " stack-trace entries:           %11lu [max: %lu]\n",
308                         nr_stack_trace_entries, MAX_STACK_TRACE_ENTRIES);
309         seq_printf(m, " combined max dependencies:     %11u\n",
310                         (nr_hardirq_chains + 1) *
311                         (nr_softirq_chains + 1) *
312                         (nr_process_chains + 1)
313         );
314         seq_printf(m, " hardirq-safe locks:            %11lu\n",
315                         nr_hardirq_safe);
316         seq_printf(m, " hardirq-unsafe locks:          %11lu\n",
317                         nr_hardirq_unsafe);
318         seq_printf(m, " softirq-safe locks:            %11lu\n",
319                         nr_softirq_safe);
320         seq_printf(m, " softirq-unsafe locks:          %11lu\n",
321                         nr_softirq_unsafe);
322         seq_printf(m, " irq-safe locks:                %11lu\n",
323                         nr_irq_safe);
324         seq_printf(m, " irq-unsafe locks:              %11lu\n",
325                         nr_irq_unsafe);
326
327         seq_printf(m, " hardirq-read-safe locks:       %11lu\n",
328                         nr_hardirq_read_safe);
329         seq_printf(m, " hardirq-read-unsafe locks:     %11lu\n",
330                         nr_hardirq_read_unsafe);
331         seq_printf(m, " softirq-read-safe locks:       %11lu\n",
332                         nr_softirq_read_safe);
333         seq_printf(m, " softirq-read-unsafe locks:     %11lu\n",
334                         nr_softirq_read_unsafe);
335         seq_printf(m, " irq-read-safe locks:           %11lu\n",
336                         nr_irq_read_safe);
337         seq_printf(m, " irq-read-unsafe locks:         %11lu\n",
338                         nr_irq_read_unsafe);
339
340         seq_printf(m, " uncategorized locks:           %11lu\n",
341                         nr_uncategorized);
342         seq_printf(m, " unused locks:                  %11lu\n",
343                         nr_unused);
344         seq_printf(m, " max locking depth:             %11u\n",
345                         max_lockdep_depth);
346         seq_printf(m, " max recursion depth:           %11u\n",
347                         max_recursion_depth);
348         lockdep_stats_debug_show(m);
349         seq_printf(m, " debug_locks:                   %11u\n",
350                         debug_locks);
351
352         return 0;
353 }
354
355 static int lockdep_stats_open(struct inode *inode, struct file *file)
356 {
357         return single_open(file, lockdep_stats_show, NULL);
358 }
359
360 static const struct file_operations proc_lockdep_stats_operations = {
361         .open           = lockdep_stats_open,
362         .read           = seq_read,
363         .llseek         = seq_lseek,
364         .release        = single_release,
365 };
366
367 #ifdef CONFIG_LOCK_STAT
368
369 struct lock_stat_data {
370         struct lock_class *class;
371         struct lock_class_stats stats;
372 };
373
374 struct lock_stat_seq {
375         struct lock_stat_data *iter;
376         struct lock_stat_data *iter_end;
377         struct lock_stat_data stats[MAX_LOCKDEP_KEYS];
378 };
379
380 /*
381  * sort on absolute number of contentions
382  */
383 static int lock_stat_cmp(const void *l, const void *r)
384 {
385         const struct lock_stat_data *dl = l, *dr = r;
386         unsigned long nl, nr;
387
388         nl = dl->stats.read_waittime.nr + dl->stats.write_waittime.nr;
389         nr = dr->stats.read_waittime.nr + dr->stats.write_waittime.nr;
390
391         return nr - nl;
392 }
393
394 static void seq_line(struct seq_file *m, char c, int offset, int length)
395 {
396         int i;
397
398         for (i = 0; i < offset; i++)
399                 seq_puts(m, " ");
400         for (i = 0; i < length; i++)
401                 seq_printf(m, "%c", c);
402         seq_puts(m, "\n");
403 }
404
405 static void snprint_time(char *buf, size_t bufsiz, s64 nr)
406 {
407         unsigned long rem;
408
409         rem = do_div(nr, 1000); /* XXX: do_div_signed */
410         snprintf(buf, bufsiz, "%lld.%02d", (long long)nr, ((int)rem+5)/10);
411 }
412
413 static void seq_time(struct seq_file *m, s64 time)
414 {
415         char num[15];
416
417         snprint_time(num, sizeof(num), time);
418         seq_printf(m, " %14s", num);
419 }
420
421 static void seq_lock_time(struct seq_file *m, struct lock_time *lt)
422 {
423         seq_printf(m, "%14lu", lt->nr);
424         seq_time(m, lt->min);
425         seq_time(m, lt->max);
426         seq_time(m, lt->total);
427 }
428
429 static void seq_stats(struct seq_file *m, struct lock_stat_data *data)
430 {
431         char name[39];
432         struct lock_class *class;
433         struct lock_class_stats *stats;
434         int i, namelen;
435
436         class = data->class;
437         stats = &data->stats;
438
439         namelen = 38;
440         if (class->name_version > 1)
441                 namelen -= 2; /* XXX truncates versions > 9 */
442         if (class->subclass)
443                 namelen -= 2;
444
445         if (!class->name) {
446                 char str[KSYM_NAME_LEN];
447                 const char *key_name;
448
449                 key_name = __get_key_name(class->key, str);
450                 snprintf(name, namelen, "%s", key_name);
451         } else {
452                 snprintf(name, namelen, "%s", class->name);
453         }
454         namelen = strlen(name);
455         if (class->name_version > 1) {
456                 snprintf(name+namelen, 3, "#%d", class->name_version);
457                 namelen += 2;
458         }
459         if (class->subclass) {
460                 snprintf(name+namelen, 3, "/%d", class->subclass);
461                 namelen += 2;
462         }
463
464         if (stats->write_holdtime.nr) {
465                 if (stats->read_holdtime.nr)
466                         seq_printf(m, "%38s-W:", name);
467                 else
468                         seq_printf(m, "%40s:", name);
469
470                 seq_printf(m, "%14lu ", stats->bounces[bounce_contended_write]);
471                 seq_lock_time(m, &stats->write_waittime);
472                 seq_printf(m, " %14lu ", stats->bounces[bounce_acquired_write]);
473                 seq_lock_time(m, &stats->write_holdtime);
474                 seq_puts(m, "\n");
475         }
476
477         if (stats->read_holdtime.nr) {
478                 seq_printf(m, "%38s-R:", name);
479                 seq_printf(m, "%14lu ", stats->bounces[bounce_contended_read]);
480                 seq_lock_time(m, &stats->read_waittime);
481                 seq_printf(m, " %14lu ", stats->bounces[bounce_acquired_read]);
482                 seq_lock_time(m, &stats->read_holdtime);
483                 seq_puts(m, "\n");
484         }
485
486         if (stats->read_waittime.nr + stats->write_waittime.nr == 0)
487                 return;
488
489         if (stats->read_holdtime.nr)
490                 namelen += 2;
491
492         for (i = 0; i < ARRAY_SIZE(class->contention_point); i++) {
493                 char sym[KSYM_SYMBOL_LEN];
494                 char ip[32];
495
496                 if (class->contention_point[i] == 0)
497                         break;
498
499                 if (!i)
500                         seq_line(m, '-', 40-namelen, namelen);
501
502                 sprint_symbol(sym, class->contention_point[i]);
503                 snprintf(ip, sizeof(ip), "[<%p>]",
504                                 (void *)class->contention_point[i]);
505                 seq_printf(m, "%40s %14lu %29s %s\n", name,
506                                 stats->contention_point[i],
507                                 ip, sym);
508         }
509         if (i) {
510                 seq_puts(m, "\n");
511                 seq_line(m, '.', 0, 40 + 1 + 10 * (14 + 1));
512                 seq_puts(m, "\n");
513         }
514 }
515
516 static void seq_header(struct seq_file *m)
517 {
518         seq_printf(m, "lock_stat version 0.2\n");
519         seq_line(m, '-', 0, 40 + 1 + 10 * (14 + 1));
520         seq_printf(m, "%40s %14s %14s %14s %14s %14s %14s %14s %14s "
521                         "%14s %14s\n",
522                         "class name",
523                         "con-bounces",
524                         "contentions",
525                         "waittime-min",
526                         "waittime-max",
527                         "waittime-total",
528                         "acq-bounces",
529                         "acquisitions",
530                         "holdtime-min",
531                         "holdtime-max",
532                         "holdtime-total");
533         seq_line(m, '-', 0, 40 + 1 + 10 * (14 + 1));
534         seq_printf(m, "\n");
535 }
536
537 static void *ls_start(struct seq_file *m, loff_t *pos)
538 {
539         struct lock_stat_seq *data = m->private;
540
541         if (*pos == 0)
542                 return SEQ_START_TOKEN;
543
544         data->iter = data->stats + *pos;
545         if (data->iter >= data->iter_end)
546                 data->iter = NULL;
547
548         return data->iter;
549 }
550
551 static void *ls_next(struct seq_file *m, void *v, loff_t *pos)
552 {
553         struct lock_stat_seq *data = m->private;
554
555         (*pos)++;
556
557         if (v == SEQ_START_TOKEN)
558                 data->iter = data->stats;
559         else {
560                 data->iter = v;
561                 data->iter++;
562         }
563
564         if (data->iter == data->iter_end)
565                 data->iter = NULL;
566
567         return data->iter;
568 }
569
570 static void ls_stop(struct seq_file *m, void *v)
571 {
572 }
573
574 static int ls_show(struct seq_file *m, void *v)
575 {
576         if (v == SEQ_START_TOKEN)
577                 seq_header(m);
578         else
579                 seq_stats(m, v);
580
581         return 0;
582 }
583
584 static struct seq_operations lockstat_ops = {
585         .start  = ls_start,
586         .next   = ls_next,
587         .stop   = ls_stop,
588         .show   = ls_show,
589 };
590
591 static int lock_stat_open(struct inode *inode, struct file *file)
592 {
593         int res;
594         struct lock_class *class;
595         struct lock_stat_seq *data = vmalloc(sizeof(struct lock_stat_seq));
596
597         if (!data)
598                 return -ENOMEM;
599
600         res = seq_open(file, &lockstat_ops);
601         if (!res) {
602                 struct lock_stat_data *iter = data->stats;
603                 struct seq_file *m = file->private_data;
604
605                 data->iter = iter;
606                 list_for_each_entry(class, &all_lock_classes, lock_entry) {
607                         iter->class = class;
608                         iter->stats = lock_stats(class);
609                         iter++;
610                 }
611                 data->iter_end = iter;
612
613                 sort(data->stats, data->iter_end - data->iter,
614                                 sizeof(struct lock_stat_data),
615                                 lock_stat_cmp, NULL);
616
617                 m->private = data;
618         } else
619                 vfree(data);
620
621         return res;
622 }
623
624 static ssize_t lock_stat_write(struct file *file, const char __user *buf,
625                                size_t count, loff_t *ppos)
626 {
627         struct lock_class *class;
628         char c;
629
630         if (count) {
631                 if (get_user(c, buf))
632                         return -EFAULT;
633
634                 if (c != '0')
635                         return count;
636
637                 list_for_each_entry(class, &all_lock_classes, lock_entry)
638                         clear_lock_stats(class);
639         }
640         return count;
641 }
642
643 static int lock_stat_release(struct inode *inode, struct file *file)
644 {
645         struct seq_file *seq = file->private_data;
646
647         vfree(seq->private);
648         seq->private = NULL;
649         return seq_release(inode, file);
650 }
651
652 static const struct file_operations proc_lock_stat_operations = {
653         .open           = lock_stat_open,
654         .write          = lock_stat_write,
655         .read           = seq_read,
656         .llseek         = seq_lseek,
657         .release        = lock_stat_release,
658 };
659 #endif /* CONFIG_LOCK_STAT */
660
661 static int __init lockdep_proc_init(void)
662 {
663         proc_create("lockdep", S_IRUSR, NULL, &proc_lockdep_operations);
664         proc_create("lockdep_stats", S_IRUSR, NULL,
665                     &proc_lockdep_stats_operations);
666
667 #ifdef CONFIG_LOCK_STAT
668         proc_create("lock_stat", S_IRUSR, NULL, &proc_lock_stat_operations);
669 #endif
670
671         return 0;
672 }
673
674 __initcall(lockdep_proc_init);
675