6 #include "util/evlist.h"
7 #include "util/evsel.h"
9 #include "util/cache.h"
10 #include "util/symbol.h"
11 #include "util/thread.h"
12 #include "util/header.h"
14 #include <subcmd/parse-options.h>
15 #include "util/trace-event.h"
17 #include "util/debug.h"
18 #include "util/session.h"
19 #include "util/tool.h"
20 #include "util/data.h"
22 #include <sys/types.h>
23 #include <sys/prctl.h>
24 #include <semaphore.h>
29 #include <linux/list.h>
30 #include <linux/hash.h>
31 #include <linux/kernel.h>
33 static struct perf_session *session;
35 /* based on kernel/lockdep.c */
36 #define LOCKHASH_BITS 12
37 #define LOCKHASH_SIZE (1UL << LOCKHASH_BITS)
39 static struct list_head lockhash_table[LOCKHASH_SIZE];
41 #define __lockhashfn(key) hash_long((unsigned long)key, LOCKHASH_BITS)
42 #define lockhashentry(key) (lockhash_table + __lockhashfn((key)))
45 struct list_head hash_entry;
46 struct rb_node rb; /* used for sorting */
49 * FIXME: perf_evsel__intval() returns u64,
50 * so address of lockdep_map should be dealed as 64bit.
51 * Is there more better solution?
53 void *addr; /* address of lockdep_map, used as ID */
54 char *name; /* for strcpy(), we cannot use const */
56 unsigned int nr_acquire;
57 unsigned int nr_acquired;
58 unsigned int nr_contended;
59 unsigned int nr_release;
61 unsigned int nr_readlock;
62 unsigned int nr_trylock;
64 /* these times are in nano sec. */
70 int discard; /* flag of blacklist */
74 * States of lock_seq_stat
76 * UNINITIALIZED is required for detecting first event of acquire.
77 * As the nature of lock events, there is no guarantee
78 * that the first event for the locks are acquire,
79 * it can be acquired, contended or release.
81 #define SEQ_STATE_UNINITIALIZED 0 /* initial state */
82 #define SEQ_STATE_RELEASED 1
83 #define SEQ_STATE_ACQUIRING 2
84 #define SEQ_STATE_ACQUIRED 3
85 #define SEQ_STATE_READ_ACQUIRED 4
86 #define SEQ_STATE_CONTENDED 5
90 * Imported from include/linux/sched.h.
91 * Should this be synchronized?
93 #define MAX_LOCK_DEPTH 48
96 * struct lock_seq_stat:
97 * Place to put on state of one lock sequence
98 * 1) acquire -> acquired -> release
99 * 2) acquire -> contended -> acquired -> release
100 * 3) acquire (with read or try) -> release
101 * 4) Are there other patterns?
103 struct lock_seq_stat {
104 struct list_head list;
116 struct list_head seq_list;
119 static struct rb_root thread_stats;
121 static struct thread_stat *thread_stat_find(u32 tid)
123 struct rb_node *node;
124 struct thread_stat *st;
126 node = thread_stats.rb_node;
128 st = container_of(node, struct thread_stat, rb);
131 else if (tid < st->tid)
132 node = node->rb_left;
134 node = node->rb_right;
140 static void thread_stat_insert(struct thread_stat *new)
142 struct rb_node **rb = &thread_stats.rb_node;
143 struct rb_node *parent = NULL;
144 struct thread_stat *p;
147 p = container_of(*rb, struct thread_stat, rb);
150 if (new->tid < p->tid)
151 rb = &(*rb)->rb_left;
152 else if (new->tid > p->tid)
153 rb = &(*rb)->rb_right;
155 BUG_ON("inserting invalid thread_stat\n");
158 rb_link_node(&new->rb, parent, rb);
159 rb_insert_color(&new->rb, &thread_stats);
162 static struct thread_stat *thread_stat_findnew_after_first(u32 tid)
164 struct thread_stat *st;
166 st = thread_stat_find(tid);
170 st = zalloc(sizeof(struct thread_stat));
172 pr_err("memory allocation failed\n");
177 INIT_LIST_HEAD(&st->seq_list);
179 thread_stat_insert(st);
184 static struct thread_stat *thread_stat_findnew_first(u32 tid);
185 static struct thread_stat *(*thread_stat_findnew)(u32 tid) =
186 thread_stat_findnew_first;
188 static struct thread_stat *thread_stat_findnew_first(u32 tid)
190 struct thread_stat *st;
192 st = zalloc(sizeof(struct thread_stat));
194 pr_err("memory allocation failed\n");
198 INIT_LIST_HEAD(&st->seq_list);
200 rb_link_node(&st->rb, NULL, &thread_stats.rb_node);
201 rb_insert_color(&st->rb, &thread_stats);
203 thread_stat_findnew = thread_stat_findnew_after_first;
207 /* build simple key function one is bigger than two */
208 #define SINGLE_KEY(member) \
209 static int lock_stat_key_ ## member(struct lock_stat *one, \
210 struct lock_stat *two) \
212 return one->member > two->member; \
215 SINGLE_KEY(nr_acquired)
216 SINGLE_KEY(nr_contended)
217 SINGLE_KEY(avg_wait_time)
218 SINGLE_KEY(wait_time_total)
219 SINGLE_KEY(wait_time_max)
221 static int lock_stat_key_wait_time_min(struct lock_stat *one,
222 struct lock_stat *two)
224 u64 s1 = one->wait_time_min;
225 u64 s2 = two->wait_time_min;
226 if (s1 == ULLONG_MAX)
228 if (s2 == ULLONG_MAX)
235 * name: the value for specify by user
236 * this should be simpler than raw name of member
237 * e.g. nr_acquired -> acquired, wait_time_total -> wait_total
240 int (*key)(struct lock_stat*, struct lock_stat*);
243 static const char *sort_key = "acquired";
245 static int (*compare)(struct lock_stat *, struct lock_stat *);
247 static struct rb_root result; /* place to store sorted data */
249 #define DEF_KEY_LOCK(name, fn_suffix) \
250 { #name, lock_stat_key_ ## fn_suffix }
251 struct lock_key keys[] = {
252 DEF_KEY_LOCK(acquired, nr_acquired),
253 DEF_KEY_LOCK(contended, nr_contended),
254 DEF_KEY_LOCK(avg_wait, avg_wait_time),
255 DEF_KEY_LOCK(wait_total, wait_time_total),
256 DEF_KEY_LOCK(wait_min, wait_time_min),
257 DEF_KEY_LOCK(wait_max, wait_time_max),
259 /* extra comparisons much complicated should be here */
264 static int select_key(void)
268 for (i = 0; keys[i].name; i++) {
269 if (!strcmp(keys[i].name, sort_key)) {
270 compare = keys[i].key;
275 pr_err("Unknown compare key: %s\n", sort_key);
280 static void insert_to_result(struct lock_stat *st,
281 int (*bigger)(struct lock_stat *, struct lock_stat *))
283 struct rb_node **rb = &result.rb_node;
284 struct rb_node *parent = NULL;
288 p = container_of(*rb, struct lock_stat, rb);
292 rb = &(*rb)->rb_left;
294 rb = &(*rb)->rb_right;
297 rb_link_node(&st->rb, parent, rb);
298 rb_insert_color(&st->rb, &result);
301 /* returns left most element of result, and erase it */
302 static struct lock_stat *pop_from_result(void)
304 struct rb_node *node = result.rb_node;
309 while (node->rb_left)
310 node = node->rb_left;
312 rb_erase(node, &result);
313 return container_of(node, struct lock_stat, rb);
316 static struct lock_stat *lock_stat_findnew(void *addr, const char *name)
318 struct list_head *entry = lockhashentry(addr);
319 struct lock_stat *ret, *new;
321 list_for_each_entry(ret, entry, hash_entry) {
322 if (ret->addr == addr)
326 new = zalloc(sizeof(struct lock_stat));
331 new->name = zalloc(sizeof(char) * strlen(name) + 1);
337 strcpy(new->name, name);
338 new->wait_time_min = ULLONG_MAX;
340 list_add(&new->hash_entry, entry);
344 pr_err("memory allocation failed\n");
348 struct trace_lock_handler {
349 int (*acquire_event)(struct perf_evsel *evsel,
350 struct perf_sample *sample);
352 int (*acquired_event)(struct perf_evsel *evsel,
353 struct perf_sample *sample);
355 int (*contended_event)(struct perf_evsel *evsel,
356 struct perf_sample *sample);
358 int (*release_event)(struct perf_evsel *evsel,
359 struct perf_sample *sample);
362 static struct lock_seq_stat *get_seq(struct thread_stat *ts, void *addr)
364 struct lock_seq_stat *seq;
366 list_for_each_entry(seq, &ts->seq_list, list) {
367 if (seq->addr == addr)
371 seq = zalloc(sizeof(struct lock_seq_stat));
373 pr_err("memory allocation failed\n");
376 seq->state = SEQ_STATE_UNINITIALIZED;
379 list_add(&seq->list, &ts->seq_list);
391 static int bad_hist[BROKEN_MAX];
398 static int report_lock_acquire_event(struct perf_evsel *evsel,
399 struct perf_sample *sample)
402 struct lock_stat *ls;
403 struct thread_stat *ts;
404 struct lock_seq_stat *seq;
405 const char *name = perf_evsel__strval(evsel, sample, "name");
406 u64 tmp = perf_evsel__intval(evsel, sample, "lockdep_addr");
407 int flag = perf_evsel__intval(evsel, sample, "flag");
409 memcpy(&addr, &tmp, sizeof(void *));
411 ls = lock_stat_findnew(addr, name);
417 ts = thread_stat_findnew(sample->tid);
421 seq = get_seq(ts, addr);
425 switch (seq->state) {
426 case SEQ_STATE_UNINITIALIZED:
427 case SEQ_STATE_RELEASED:
429 seq->state = SEQ_STATE_ACQUIRING;
433 if (flag & READ_LOCK)
435 seq->state = SEQ_STATE_READ_ACQUIRED;
440 case SEQ_STATE_READ_ACQUIRED:
441 if (flag & READ_LOCK) {
449 case SEQ_STATE_ACQUIRED:
450 case SEQ_STATE_ACQUIRING:
451 case SEQ_STATE_CONTENDED:
453 /* broken lock sequence, discard it */
455 bad_hist[BROKEN_ACQUIRE]++;
456 list_del(&seq->list);
460 BUG_ON("Unknown state of lock sequence found!\n");
465 seq->prev_event_time = sample->time;
470 static int report_lock_acquired_event(struct perf_evsel *evsel,
471 struct perf_sample *sample)
474 struct lock_stat *ls;
475 struct thread_stat *ts;
476 struct lock_seq_stat *seq;
478 const char *name = perf_evsel__strval(evsel, sample, "name");
479 u64 tmp = perf_evsel__intval(evsel, sample, "lockdep_addr");
481 memcpy(&addr, &tmp, sizeof(void *));
483 ls = lock_stat_findnew(addr, name);
489 ts = thread_stat_findnew(sample->tid);
493 seq = get_seq(ts, addr);
497 switch (seq->state) {
498 case SEQ_STATE_UNINITIALIZED:
499 /* orphan event, do nothing */
501 case SEQ_STATE_ACQUIRING:
503 case SEQ_STATE_CONTENDED:
504 contended_term = sample->time - seq->prev_event_time;
505 ls->wait_time_total += contended_term;
506 if (contended_term < ls->wait_time_min)
507 ls->wait_time_min = contended_term;
508 if (ls->wait_time_max < contended_term)
509 ls->wait_time_max = contended_term;
511 case SEQ_STATE_RELEASED:
512 case SEQ_STATE_ACQUIRED:
513 case SEQ_STATE_READ_ACQUIRED:
514 /* broken lock sequence, discard it */
516 bad_hist[BROKEN_ACQUIRED]++;
517 list_del(&seq->list);
521 BUG_ON("Unknown state of lock sequence found!\n");
525 seq->state = SEQ_STATE_ACQUIRED;
527 ls->avg_wait_time = ls->nr_contended ? ls->wait_time_total/ls->nr_contended : 0;
528 seq->prev_event_time = sample->time;
533 static int report_lock_contended_event(struct perf_evsel *evsel,
534 struct perf_sample *sample)
537 struct lock_stat *ls;
538 struct thread_stat *ts;
539 struct lock_seq_stat *seq;
540 const char *name = perf_evsel__strval(evsel, sample, "name");
541 u64 tmp = perf_evsel__intval(evsel, sample, "lockdep_addr");
543 memcpy(&addr, &tmp, sizeof(void *));
545 ls = lock_stat_findnew(addr, name);
551 ts = thread_stat_findnew(sample->tid);
555 seq = get_seq(ts, addr);
559 switch (seq->state) {
560 case SEQ_STATE_UNINITIALIZED:
561 /* orphan event, do nothing */
563 case SEQ_STATE_ACQUIRING:
565 case SEQ_STATE_RELEASED:
566 case SEQ_STATE_ACQUIRED:
567 case SEQ_STATE_READ_ACQUIRED:
568 case SEQ_STATE_CONTENDED:
569 /* broken lock sequence, discard it */
571 bad_hist[BROKEN_CONTENDED]++;
572 list_del(&seq->list);
576 BUG_ON("Unknown state of lock sequence found!\n");
580 seq->state = SEQ_STATE_CONTENDED;
582 ls->avg_wait_time = ls->wait_time_total/ls->nr_contended;
583 seq->prev_event_time = sample->time;
588 static int report_lock_release_event(struct perf_evsel *evsel,
589 struct perf_sample *sample)
592 struct lock_stat *ls;
593 struct thread_stat *ts;
594 struct lock_seq_stat *seq;
595 const char *name = perf_evsel__strval(evsel, sample, "name");
596 u64 tmp = perf_evsel__intval(evsel, sample, "lockdep_addr");
598 memcpy(&addr, &tmp, sizeof(void *));
600 ls = lock_stat_findnew(addr, name);
606 ts = thread_stat_findnew(sample->tid);
610 seq = get_seq(ts, addr);
614 switch (seq->state) {
615 case SEQ_STATE_UNINITIALIZED:
617 case SEQ_STATE_ACQUIRED:
619 case SEQ_STATE_READ_ACQUIRED:
621 BUG_ON(seq->read_count < 0);
622 if (!seq->read_count) {
627 case SEQ_STATE_ACQUIRING:
628 case SEQ_STATE_CONTENDED:
629 case SEQ_STATE_RELEASED:
630 /* broken lock sequence, discard it */
632 bad_hist[BROKEN_RELEASE]++;
635 BUG_ON("Unknown state of lock sequence found!\n");
641 list_del(&seq->list);
647 /* lock oriented handlers */
648 /* TODO: handlers for CPU oriented, thread oriented */
649 static struct trace_lock_handler report_lock_ops = {
650 .acquire_event = report_lock_acquire_event,
651 .acquired_event = report_lock_acquired_event,
652 .contended_event = report_lock_contended_event,
653 .release_event = report_lock_release_event,
656 static struct trace_lock_handler *trace_handler;
658 static int perf_evsel__process_lock_acquire(struct perf_evsel *evsel,
659 struct perf_sample *sample)
661 if (trace_handler->acquire_event)
662 return trace_handler->acquire_event(evsel, sample);
666 static int perf_evsel__process_lock_acquired(struct perf_evsel *evsel,
667 struct perf_sample *sample)
669 if (trace_handler->acquired_event)
670 return trace_handler->acquired_event(evsel, sample);
674 static int perf_evsel__process_lock_contended(struct perf_evsel *evsel,
675 struct perf_sample *sample)
677 if (trace_handler->contended_event)
678 return trace_handler->contended_event(evsel, sample);
682 static int perf_evsel__process_lock_release(struct perf_evsel *evsel,
683 struct perf_sample *sample)
685 if (trace_handler->release_event)
686 return trace_handler->release_event(evsel, sample);
690 static void print_bad_events(int bad, int total)
692 /* Output for debug, this have to be removed */
694 const char *name[4] =
695 { "acquire", "acquired", "contended", "release" };
697 pr_info("\n=== output for debug===\n\n");
698 pr_info("bad: %d, total: %d\n", bad, total);
699 pr_info("bad rate: %.2f %%\n", (double)bad / (double)total * 100);
700 pr_info("histogram of events caused bad sequence\n");
701 for (i = 0; i < BROKEN_MAX; i++)
702 pr_info(" %10s: %d\n", name[i], bad_hist[i]);
705 /* TODO: various way to print, coloring, nano or milli sec */
706 static void print_result(void)
708 struct lock_stat *st;
712 pr_info("%20s ", "Name");
713 pr_info("%10s ", "acquired");
714 pr_info("%10s ", "contended");
716 pr_info("%15s ", "avg wait (ns)");
717 pr_info("%15s ", "total wait (ns)");
718 pr_info("%15s ", "max wait (ns)");
719 pr_info("%15s ", "min wait (ns)");
724 while ((st = pop_from_result())) {
732 if (strlen(st->name) < 16) {
733 /* output raw name */
734 pr_info("%20s ", st->name);
736 strncpy(cut_name, st->name, 16);
741 /* cut off name for saving output style */
742 pr_info("%20s ", cut_name);
745 pr_info("%10u ", st->nr_acquired);
746 pr_info("%10u ", st->nr_contended);
748 pr_info("%15" PRIu64 " ", st->avg_wait_time);
749 pr_info("%15" PRIu64 " ", st->wait_time_total);
750 pr_info("%15" PRIu64 " ", st->wait_time_max);
751 pr_info("%15" PRIu64 " ", st->wait_time_min == ULLONG_MAX ?
752 0 : st->wait_time_min);
756 print_bad_events(bad, total);
759 static bool info_threads, info_map;
761 static void dump_threads(void)
763 struct thread_stat *st;
764 struct rb_node *node;
767 pr_info("%10s: comm\n", "Thread ID");
769 node = rb_first(&thread_stats);
771 st = container_of(node, struct thread_stat, rb);
772 t = perf_session__findnew(session, st->tid);
773 pr_info("%10d: %s\n", st->tid, thread__comm_str(t));
774 node = rb_next(node);
779 static void dump_map(void)
782 struct lock_stat *st;
784 pr_info("Address of instance: name of class\n");
785 for (i = 0; i < LOCKHASH_SIZE; i++) {
786 list_for_each_entry(st, &lockhash_table[i], hash_entry) {
787 pr_info(" %p: %s\n", st->addr, st->name);
792 static int dump_info(void)
802 pr_err("Unknown type of information\n");
808 typedef int (*tracepoint_handler)(struct perf_evsel *evsel,
809 struct perf_sample *sample);
811 static int process_sample_event(struct perf_tool *tool __maybe_unused,
812 union perf_event *event,
813 struct perf_sample *sample,
814 struct perf_evsel *evsel,
815 struct machine *machine)
818 struct thread *thread = machine__findnew_thread(machine, sample->pid,
821 if (thread == NULL) {
822 pr_debug("problem processing %d event, skipping it.\n",
827 if (evsel->handler != NULL) {
828 tracepoint_handler f = evsel->handler;
829 err = f(evsel, sample);
837 static void sort_result(void)
840 struct lock_stat *st;
842 for (i = 0; i < LOCKHASH_SIZE; i++) {
843 list_for_each_entry(st, &lockhash_table[i], hash_entry) {
844 insert_to_result(st, compare);
849 static const struct perf_evsel_str_handler lock_tracepoints[] = {
850 { "lock:lock_acquire", perf_evsel__process_lock_acquire, }, /* CONFIG_LOCKDEP */
851 { "lock:lock_acquired", perf_evsel__process_lock_acquired, }, /* CONFIG_LOCKDEP, CONFIG_LOCK_STAT */
852 { "lock:lock_contended", perf_evsel__process_lock_contended, }, /* CONFIG_LOCKDEP, CONFIG_LOCK_STAT */
853 { "lock:lock_release", perf_evsel__process_lock_release, }, /* CONFIG_LOCKDEP */
858 static int __cmd_report(bool display_info)
861 struct perf_tool eops = {
862 .sample = process_sample_event,
863 .comm = perf_event__process_comm,
864 .namespaces = perf_event__process_namespaces,
865 .ordered_events = true,
867 struct perf_data_file file = {
869 .mode = PERF_DATA_MODE_READ,
873 session = perf_session__new(&file, false, &eops);
875 pr_err("Initializing perf session failed\n");
879 symbol__init(&session->header.env);
881 if (!perf_session__has_traces(session, "lock record"))
884 if (perf_session__set_tracepoints_handlers(session, lock_tracepoints)) {
885 pr_err("Initializing perf session tracepoint handlers failed\n");
892 err = perf_session__process_events(session);
897 if (display_info) /* used for info subcommand */
905 perf_session__delete(session);
909 static int __cmd_record(int argc, const char **argv)
911 const char *record_args[] = {
912 "record", "-R", "-m", "1024", "-c", "1",
914 unsigned int rec_argc, i, j, ret;
915 const char **rec_argv;
917 for (i = 0; i < ARRAY_SIZE(lock_tracepoints); i++) {
918 if (!is_valid_tracepoint(lock_tracepoints[i].name)) {
919 pr_err("tracepoint %s is not enabled. "
920 "Are CONFIG_LOCKDEP and CONFIG_LOCK_STAT enabled?\n",
921 lock_tracepoints[i].name);
926 rec_argc = ARRAY_SIZE(record_args) + argc - 1;
927 /* factor of 2 is for -e in front of each tracepoint */
928 rec_argc += 2 * ARRAY_SIZE(lock_tracepoints);
930 rec_argv = calloc(rec_argc + 1, sizeof(char *));
934 for (i = 0; i < ARRAY_SIZE(record_args); i++)
935 rec_argv[i] = strdup(record_args[i]);
937 for (j = 0; j < ARRAY_SIZE(lock_tracepoints); j++) {
938 rec_argv[i++] = "-e";
939 rec_argv[i++] = strdup(lock_tracepoints[j].name);
942 for (j = 1; j < (unsigned int)argc; j++, i++)
943 rec_argv[i] = argv[j];
945 BUG_ON(i != rec_argc);
947 ret = cmd_record(i, rec_argv);
952 int cmd_lock(int argc, const char **argv)
954 const struct option lock_options[] = {
955 OPT_STRING('i', "input", &input_name, "file", "input file name"),
956 OPT_INCR('v', "verbose", &verbose, "be more verbose (show symbol address, etc)"),
957 OPT_BOOLEAN('D', "dump-raw-trace", &dump_trace, "dump raw trace in ASCII"),
958 OPT_BOOLEAN('f', "force", &force, "don't complain, do it"),
962 const struct option info_options[] = {
963 OPT_BOOLEAN('t', "threads", &info_threads,
964 "dump thread list in perf.data"),
965 OPT_BOOLEAN('m', "map", &info_map,
966 "map of lock instances (address:name table)"),
967 OPT_PARENT(lock_options)
970 const struct option report_options[] = {
971 OPT_STRING('k', "key", &sort_key, "acquired",
972 "key for sorting (acquired / contended / avg_wait / wait_total / wait_max / wait_min)"),
974 OPT_PARENT(lock_options)
977 const char * const info_usage[] = {
978 "perf lock info [<options>]",
981 const char *const lock_subcommands[] = { "record", "report", "script",
983 const char *lock_usage[] = {
987 const char * const report_usage[] = {
988 "perf lock report [<options>]",
994 for (i = 0; i < LOCKHASH_SIZE; i++)
995 INIT_LIST_HEAD(lockhash_table + i);
997 argc = parse_options_subcommand(argc, argv, lock_options, lock_subcommands,
998 lock_usage, PARSE_OPT_STOP_AT_NON_OPTION);
1000 usage_with_options(lock_usage, lock_options);
1002 if (!strncmp(argv[0], "rec", 3)) {
1003 return __cmd_record(argc, argv);
1004 } else if (!strncmp(argv[0], "report", 6)) {
1005 trace_handler = &report_lock_ops;
1007 argc = parse_options(argc, argv,
1008 report_options, report_usage, 0);
1010 usage_with_options(report_usage, report_options);
1012 rc = __cmd_report(false);
1013 } else if (!strcmp(argv[0], "script")) {
1014 /* Aliased to 'perf script' */
1015 return cmd_script(argc, argv);
1016 } else if (!strcmp(argv[0], "info")) {
1018 argc = parse_options(argc, argv,
1019 info_options, info_usage, 0);
1021 usage_with_options(info_usage, info_options);
1023 /* recycling report_lock_ops */
1024 trace_handler = &report_lock_ops;
1025 rc = __cmd_report(true);
1027 usage_with_options(lock_usage, lock_options);