1 #include "builtin.h" 2 #include "perf.h" 3 4 #include "util/util.h" 5 #include "util/cache.h" 6 #include "util/symbol.h" 7 #include "util/thread.h" 8 #include "util/header.h" 9 #include "util/session.h" 10 11 #include "util/parse-options.h" 12 #include "util/trace-event.h" 13 14 #include "util/debug.h" 15 16 #include <linux/rbtree.h> 17 18 struct alloc_stat; 19 typedef int (*sort_fn_t)(struct alloc_stat *, struct alloc_stat *); 20 21 static char const *input_name = "perf.data"; 22 23 static int alloc_flag; 24 static int caller_flag; 25 26 static int alloc_lines = -1; 27 static int caller_lines = -1; 28 29 static bool raw_ip; 30 31 static char default_sort_order[] = "frag,hit,bytes"; 32 33 static int *cpunode_map; 34 static int max_cpu_num; 35 36 struct alloc_stat { 37 u64 call_site; 38 u64 ptr; 39 u64 bytes_req; 40 u64 bytes_alloc; 41 u32 hit; 42 u32 pingpong; 43 44 short alloc_cpu; 45 46 struct rb_node node; 47 }; 48 49 static struct rb_root root_alloc_stat; 50 static struct rb_root root_alloc_sorted; 51 static struct rb_root root_caller_stat; 52 static struct rb_root root_caller_sorted; 53 54 static unsigned long total_requested, total_allocated; 55 static unsigned long nr_allocs, nr_cross_allocs; 56 57 #define PATH_SYS_NODE "/sys/devices/system/node" 58 59 static void init_cpunode_map(void) 60 { 61 FILE *fp; 62 int i; 63 64 fp = fopen("/sys/devices/system/cpu/kernel_max", "r"); 65 if (!fp) { 66 max_cpu_num = 4096; 67 return; 68 } 69 70 if (fscanf(fp, "%d", &max_cpu_num) < 1) 71 die("Failed to read 'kernel_max' from sysfs"); 72 max_cpu_num++; 73 74 cpunode_map = calloc(max_cpu_num, sizeof(int)); 75 if (!cpunode_map) 76 die("calloc"); 77 for (i = 0; i < max_cpu_num; i++) 78 cpunode_map[i] = -1; 79 fclose(fp); 80 } 81 82 static void setup_cpunode_map(void) 83 { 84 struct dirent *dent1, *dent2; 85 DIR *dir1, *dir2; 86 unsigned int cpu, mem; 87 char buf[PATH_MAX]; 88 89 init_cpunode_map(); 90 91 dir1 = opendir(PATH_SYS_NODE); 92 if (!dir1) 93 return; 94 95 while ((dent1 = readdir(dir1)) != NULL) { 96 if (dent1->d_type != DT_DIR || 97 sscanf(dent1->d_name, "node%u", &mem) < 1) 98 continue; 99 100 snprintf(buf, PATH_MAX, "%s/%s", PATH_SYS_NODE, dent1->d_name); 101 dir2 = opendir(buf); 102 if (!dir2) 103 continue; 104 while ((dent2 = readdir(dir2)) != NULL) { 105 if (dent2->d_type != DT_LNK || 106 sscanf(dent2->d_name, "cpu%u", &cpu) < 1) 107 continue; 108 cpunode_map[cpu] = mem; 109 } 110 } 111 } 112 113 static void insert_alloc_stat(unsigned long call_site, unsigned long ptr, 114 int bytes_req, int bytes_alloc, int cpu) 115 { 116 struct rb_node **node = &root_alloc_stat.rb_node; 117 struct rb_node *parent = NULL; 118 struct alloc_stat *data = NULL; 119 120 while (*node) { 121 parent = *node; 122 data = rb_entry(*node, struct alloc_stat, node); 123 124 if (ptr > data->ptr) 125 node = &(*node)->rb_right; 126 else if (ptr < data->ptr) 127 node = &(*node)->rb_left; 128 else 129 break; 130 } 131 132 if (data && data->ptr == ptr) { 133 data->hit++; 134 data->bytes_req += bytes_req; 135 data->bytes_alloc += bytes_alloc; 136 } else { 137 data = malloc(sizeof(*data)); 138 if (!data) 139 die("malloc"); 140 data->ptr = ptr; 141 data->pingpong = 0; 142 data->hit = 1; 143 data->bytes_req = bytes_req; 144 data->bytes_alloc = bytes_alloc; 145 146 rb_link_node(&data->node, parent, node); 147 rb_insert_color(&data->node, &root_alloc_stat); 148 } 149 data->call_site = call_site; 150 data->alloc_cpu = cpu; 151 } 152 153 static void insert_caller_stat(unsigned long call_site, 154 int bytes_req, int bytes_alloc) 155 { 156 struct rb_node **node = &root_caller_stat.rb_node; 157 struct rb_node *parent = NULL; 158 struct alloc_stat *data = NULL; 159 160 while (*node) { 161 parent = *node; 162 data = rb_entry(*node, struct alloc_stat, node); 163 164 if (call_site > data->call_site) 165 node = &(*node)->rb_right; 166 else if (call_site < data->call_site) 167 node = &(*node)->rb_left; 168 else 169 break; 170 } 171 172 if (data && data->call_site == call_site) { 173 data->hit++; 174 data->bytes_req += bytes_req; 175 data->bytes_alloc += bytes_alloc; 176 } else { 177 data = malloc(sizeof(*data)); 178 if (!data) 179 die("malloc"); 180 data->call_site = call_site; 181 data->pingpong = 0; 182 data->hit = 1; 183 data->bytes_req = bytes_req; 184 data->bytes_alloc = bytes_alloc; 185 186 rb_link_node(&data->node, parent, node); 187 rb_insert_color(&data->node, &root_caller_stat); 188 } 189 } 190 191 static void process_alloc_event(void *data, 192 struct event *event, 193 int cpu, 194 u64 timestamp __used, 195 struct thread *thread __used, 196 int node) 197 { 198 unsigned long call_site; 199 unsigned long ptr; 200 int bytes_req; 201 int bytes_alloc; 202 int node1, node2; 203 204 ptr = raw_field_value(event, "ptr", data); 205 call_site = raw_field_value(event, "call_site", data); 206 bytes_req = raw_field_value(event, "bytes_req", data); 207 bytes_alloc = raw_field_value(event, "bytes_alloc", data); 208 209 insert_alloc_stat(call_site, ptr, bytes_req, bytes_alloc, cpu); 210 insert_caller_stat(call_site, bytes_req, bytes_alloc); 211 212 total_requested += bytes_req; 213 total_allocated += bytes_alloc; 214 215 if (node) { 216 node1 = cpunode_map[cpu]; 217 node2 = raw_field_value(event, "node", data); 218 if (node1 != node2) 219 nr_cross_allocs++; 220 } 221 nr_allocs++; 222 } 223 224 static int ptr_cmp(struct alloc_stat *, struct alloc_stat *); 225 static int callsite_cmp(struct alloc_stat *, struct alloc_stat *); 226 227 static struct alloc_stat *search_alloc_stat(unsigned long ptr, 228 unsigned long call_site, 229 struct rb_root *root, 230 sort_fn_t sort_fn) 231 { 232 struct rb_node *node = root->rb_node; 233 struct alloc_stat key = { .ptr = ptr, .call_site = call_site }; 234 235 while (node) { 236 struct alloc_stat *data; 237 int cmp; 238 239 data = rb_entry(node, struct alloc_stat, node); 240 241 cmp = sort_fn(&key, data); 242 if (cmp < 0) 243 node = node->rb_left; 244 else if (cmp > 0) 245 node = node->rb_right; 246 else 247 return data; 248 } 249 return NULL; 250 } 251 252 static void process_free_event(void *data, 253 struct event *event, 254 int cpu, 255 u64 timestamp __used, 256 struct thread *thread __used) 257 { 258 unsigned long ptr; 259 struct alloc_stat *s_alloc, *s_caller; 260 261 ptr = raw_field_value(event, "ptr", data); 262 263 s_alloc = search_alloc_stat(ptr, 0, &root_alloc_stat, ptr_cmp); 264 if (!s_alloc) 265 return; 266 267 if (cpu != s_alloc->alloc_cpu) { 268 s_alloc->pingpong++; 269 270 s_caller = search_alloc_stat(0, s_alloc->call_site, 271 &root_caller_stat, callsite_cmp); 272 assert(s_caller); 273 s_caller->pingpong++; 274 } 275 s_alloc->alloc_cpu = -1; 276 } 277 278 static void 279 process_raw_event(event_t *raw_event __used, void *data, 280 int cpu, u64 timestamp, struct thread *thread) 281 { 282 struct event *event; 283 int type; 284 285 type = trace_parse_common_type(data); 286 event = trace_find_event(type); 287 288 if (!strcmp(event->name, "kmalloc") || 289 !strcmp(event->name, "kmem_cache_alloc")) { 290 process_alloc_event(data, event, cpu, timestamp, thread, 0); 291 return; 292 } 293 294 if (!strcmp(event->name, "kmalloc_node") || 295 !strcmp(event->name, "kmem_cache_alloc_node")) { 296 process_alloc_event(data, event, cpu, timestamp, thread, 1); 297 return; 298 } 299 300 if (!strcmp(event->name, "kfree") || 301 !strcmp(event->name, "kmem_cache_free")) { 302 process_free_event(data, event, cpu, timestamp, thread); 303 return; 304 } 305 } 306 307 static int process_sample_event(event_t *event, struct perf_session *session) 308 { 309 struct sample_data data; 310 struct thread *thread; 311 312 memset(&data, 0, sizeof(data)); 313 data.time = -1; 314 data.cpu = -1; 315 data.period = 1; 316 317 event__parse_sample(event, session->sample_type, &data); 318 319 dump_printf("(IP, %d): %d/%d: %#Lx period: %Ld\n", event->header.misc, 320 data.pid, data.tid, data.ip, data.period); 321 322 thread = perf_session__findnew(session, event->ip.pid); 323 if (thread == NULL) { 324 pr_debug("problem processing %d event, skipping it.\n", 325 event->header.type); 326 return -1; 327 } 328 329 dump_printf(" ... thread: %s:%d\n", thread->comm, thread->pid); 330 331 process_raw_event(event, data.raw_data, data.cpu, 332 data.time, thread); 333 334 return 0; 335 } 336 337 static struct perf_event_ops event_ops = { 338 .sample = process_sample_event, 339 .comm = event__process_comm, 340 .ordered_samples = true, 341 }; 342 343 static double fragmentation(unsigned long n_req, unsigned long n_alloc) 344 { 345 if (n_alloc == 0) 346 return 0.0; 347 else 348 return 100.0 - (100.0 * n_req / n_alloc); 349 } 350 351 static void __print_result(struct rb_root *root, struct perf_session *session, 352 int n_lines, int is_caller) 353 { 354 struct rb_node *next; 355 struct machine *machine; 356 357 printf("%.102s\n", graph_dotted_line); 358 printf(" %-34s |", is_caller ? "Callsite": "Alloc Ptr"); 359 printf(" Total_alloc/Per | Total_req/Per | Hit | Ping-pong | Frag\n"); 360 printf("%.102s\n", graph_dotted_line); 361 362 next = rb_first(root); 363 364 machine = perf_session__find_host_machine(session); 365 if (!machine) { 366 pr_err("__print_result: couldn't find kernel information\n"); 367 return; 368 } 369 while (next && n_lines--) { 370 struct alloc_stat *data = rb_entry(next, struct alloc_stat, 371 node); 372 struct symbol *sym = NULL; 373 struct map *map; 374 char buf[BUFSIZ]; 375 u64 addr; 376 377 if (is_caller) { 378 addr = data->call_site; 379 if (!raw_ip) 380 sym = machine__find_kernel_function(machine, addr, &map, NULL); 381 } else 382 addr = data->ptr; 383 384 if (sym != NULL) 385 snprintf(buf, sizeof(buf), "%s+%Lx", sym->name, 386 addr - map->unmap_ip(map, sym->start)); 387 else 388 snprintf(buf, sizeof(buf), "%#Lx", addr); 389 printf(" %-34s |", buf); 390 391 printf(" %9llu/%-5lu | %9llu/%-5lu | %8lu | %8lu | %6.3f%%\n", 392 (unsigned long long)data->bytes_alloc, 393 (unsigned long)data->bytes_alloc / data->hit, 394 (unsigned long long)data->bytes_req, 395 (unsigned long)data->bytes_req / data->hit, 396 (unsigned long)data->hit, 397 (unsigned long)data->pingpong, 398 fragmentation(data->bytes_req, data->bytes_alloc)); 399 400 next = rb_next(next); 401 } 402 403 if (n_lines == -1) 404 printf(" ... | ... | ... | ... | ... | ... \n"); 405 406 printf("%.102s\n", graph_dotted_line); 407 } 408 409 static void print_summary(void) 410 { 411 printf("\nSUMMARY\n=======\n"); 412 printf("Total bytes requested: %lu\n", total_requested); 413 printf("Total bytes allocated: %lu\n", total_allocated); 414 printf("Total bytes wasted on internal fragmentation: %lu\n", 415 total_allocated - total_requested); 416 printf("Internal fragmentation: %f%%\n", 417 fragmentation(total_requested, total_allocated)); 418 printf("Cross CPU allocations: %lu/%lu\n", nr_cross_allocs, nr_allocs); 419 } 420 421 static void print_result(struct perf_session *session) 422 { 423 if (caller_flag) 424 __print_result(&root_caller_sorted, session, caller_lines, 1); 425 if (alloc_flag) 426 __print_result(&root_alloc_sorted, session, alloc_lines, 0); 427 print_summary(); 428 } 429 430 struct sort_dimension { 431 const char name[20]; 432 sort_fn_t cmp; 433 struct list_head list; 434 }; 435 436 static LIST_HEAD(caller_sort); 437 static LIST_HEAD(alloc_sort); 438 439 static void sort_insert(struct rb_root *root, struct alloc_stat *data, 440 struct list_head *sort_list) 441 { 442 struct rb_node **new = &(root->rb_node); 443 struct rb_node *parent = NULL; 444 struct sort_dimension *sort; 445 446 while (*new) { 447 struct alloc_stat *this; 448 int cmp = 0; 449 450 this = rb_entry(*new, struct alloc_stat, node); 451 parent = *new; 452 453 list_for_each_entry(sort, sort_list, list) { 454 cmp = sort->cmp(data, this); 455 if (cmp) 456 break; 457 } 458 459 if (cmp > 0) 460 new = &((*new)->rb_left); 461 else 462 new = &((*new)->rb_right); 463 } 464 465 rb_link_node(&data->node, parent, new); 466 rb_insert_color(&data->node, root); 467 } 468 469 static void __sort_result(struct rb_root *root, struct rb_root *root_sorted, 470 struct list_head *sort_list) 471 { 472 struct rb_node *node; 473 struct alloc_stat *data; 474 475 for (;;) { 476 node = rb_first(root); 477 if (!node) 478 break; 479 480 rb_erase(node, root); 481 data = rb_entry(node, struct alloc_stat, node); 482 sort_insert(root_sorted, data, sort_list); 483 } 484 } 485 486 static void sort_result(void) 487 { 488 __sort_result(&root_alloc_stat, &root_alloc_sorted, &alloc_sort); 489 __sort_result(&root_caller_stat, &root_caller_sorted, &caller_sort); 490 } 491 492 static int __cmd_kmem(void) 493 { 494 int err = -EINVAL; 495 struct perf_session *session = perf_session__new(input_name, O_RDONLY, 0, false); 496 if (session == NULL) 497 return -ENOMEM; 498 499 if (perf_session__create_kernel_maps(session) < 0) 500 goto out_delete; 501 502 if (!perf_session__has_traces(session, "kmem record")) 503 goto out_delete; 504 505 setup_pager(); 506 err = perf_session__process_events(session, &event_ops); 507 if (err != 0) 508 goto out_delete; 509 sort_result(); 510 print_result(session); 511 out_delete: 512 perf_session__delete(session); 513 return err; 514 } 515 516 static const char * const kmem_usage[] = { 517 "perf kmem [<options>] {record|stat}", 518 NULL 519 }; 520 521 static int ptr_cmp(struct alloc_stat *l, struct alloc_stat *r) 522 { 523 if (l->ptr < r->ptr) 524 return -1; 525 else if (l->ptr > r->ptr) 526 return 1; 527 return 0; 528 } 529 530 static struct sort_dimension ptr_sort_dimension = { 531 .name = "ptr", 532 .cmp = ptr_cmp, 533 }; 534 535 static int callsite_cmp(struct alloc_stat *l, struct alloc_stat *r) 536 { 537 if (l->call_site < r->call_site) 538 return -1; 539 else if (l->call_site > r->call_site) 540 return 1; 541 return 0; 542 } 543 544 static struct sort_dimension callsite_sort_dimension = { 545 .name = "callsite", 546 .cmp = callsite_cmp, 547 }; 548 549 static int hit_cmp(struct alloc_stat *l, struct alloc_stat *r) 550 { 551 if (l->hit < r->hit) 552 return -1; 553 else if (l->hit > r->hit) 554 return 1; 555 return 0; 556 } 557 558 static struct sort_dimension hit_sort_dimension = { 559 .name = "hit", 560 .cmp = hit_cmp, 561 }; 562 563 static int bytes_cmp(struct alloc_stat *l, struct alloc_stat *r) 564 { 565 if (l->bytes_alloc < r->bytes_alloc) 566 return -1; 567 else if (l->bytes_alloc > r->bytes_alloc) 568 return 1; 569 return 0; 570 } 571 572 static struct sort_dimension bytes_sort_dimension = { 573 .name = "bytes", 574 .cmp = bytes_cmp, 575 }; 576 577 static int frag_cmp(struct alloc_stat *l, struct alloc_stat *r) 578 { 579 double x, y; 580 581 x = fragmentation(l->bytes_req, l->bytes_alloc); 582 y = fragmentation(r->bytes_req, r->bytes_alloc); 583 584 if (x < y) 585 return -1; 586 else if (x > y) 587 return 1; 588 return 0; 589 } 590 591 static struct sort_dimension frag_sort_dimension = { 592 .name = "frag", 593 .cmp = frag_cmp, 594 }; 595 596 static int pingpong_cmp(struct alloc_stat *l, struct alloc_stat *r) 597 { 598 if (l->pingpong < r->pingpong) 599 return -1; 600 else if (l->pingpong > r->pingpong) 601 return 1; 602 return 0; 603 } 604 605 static struct sort_dimension pingpong_sort_dimension = { 606 .name = "pingpong", 607 .cmp = pingpong_cmp, 608 }; 609 610 static struct sort_dimension *avail_sorts[] = { 611 &ptr_sort_dimension, 612 &callsite_sort_dimension, 613 &hit_sort_dimension, 614 &bytes_sort_dimension, 615 &frag_sort_dimension, 616 &pingpong_sort_dimension, 617 }; 618 619 #define NUM_AVAIL_SORTS \ 620 (int)(sizeof(avail_sorts) / sizeof(struct sort_dimension *)) 621 622 static int sort_dimension__add(const char *tok, struct list_head *list) 623 { 624 struct sort_dimension *sort; 625 int i; 626 627 for (i = 0; i < NUM_AVAIL_SORTS; i++) { 628 if (!strcmp(avail_sorts[i]->name, tok)) { 629 sort = malloc(sizeof(*sort)); 630 if (!sort) 631 die("malloc"); 632 memcpy(sort, avail_sorts[i], sizeof(*sort)); 633 list_add_tail(&sort->list, list); 634 return 0; 635 } 636 } 637 638 return -1; 639 } 640 641 static int setup_sorting(struct list_head *sort_list, const char *arg) 642 { 643 char *tok; 644 char *str = strdup(arg); 645 646 if (!str) 647 die("strdup"); 648 649 while (true) { 650 tok = strsep(&str, ","); 651 if (!tok) 652 break; 653 if (sort_dimension__add(tok, sort_list) < 0) { 654 error("Unknown --sort key: '%s'", tok); 655 return -1; 656 } 657 } 658 659 free(str); 660 return 0; 661 } 662 663 static int parse_sort_opt(const struct option *opt __used, 664 const char *arg, int unset __used) 665 { 666 if (!arg) 667 return -1; 668 669 if (caller_flag > alloc_flag) 670 return setup_sorting(&caller_sort, arg); 671 else 672 return setup_sorting(&alloc_sort, arg); 673 674 return 0; 675 } 676 677 static int parse_caller_opt(const struct option *opt __used, 678 const char *arg __used, int unset __used) 679 { 680 caller_flag = (alloc_flag + 1); 681 return 0; 682 } 683 684 static int parse_alloc_opt(const struct option *opt __used, 685 const char *arg __used, int unset __used) 686 { 687 alloc_flag = (caller_flag + 1); 688 return 0; 689 } 690 691 static int parse_line_opt(const struct option *opt __used, 692 const char *arg, int unset __used) 693 { 694 int lines; 695 696 if (!arg) 697 return -1; 698 699 lines = strtoul(arg, NULL, 10); 700 701 if (caller_flag > alloc_flag) 702 caller_lines = lines; 703 else 704 alloc_lines = lines; 705 706 return 0; 707 } 708 709 static const struct option kmem_options[] = { 710 OPT_STRING('i', "input", &input_name, "file", 711 "input file name"), 712 OPT_CALLBACK_NOOPT(0, "caller", NULL, NULL, 713 "show per-callsite statistics", 714 parse_caller_opt), 715 OPT_CALLBACK_NOOPT(0, "alloc", NULL, NULL, 716 "show per-allocation statistics", 717 parse_alloc_opt), 718 OPT_CALLBACK('s', "sort", NULL, "key[,key2...]", 719 "sort by keys: ptr, call_site, bytes, hit, pingpong, frag", 720 parse_sort_opt), 721 OPT_CALLBACK('l', "line", NULL, "num", 722 "show n lines", 723 parse_line_opt), 724 OPT_BOOLEAN(0, "raw-ip", &raw_ip, "show raw ip instead of symbol"), 725 OPT_END() 726 }; 727 728 static const char *record_args[] = { 729 "record", 730 "-a", 731 "-R", 732 "-f", 733 "-c", "1", 734 "-e", "kmem:kmalloc", 735 "-e", "kmem:kmalloc_node", 736 "-e", "kmem:kfree", 737 "-e", "kmem:kmem_cache_alloc", 738 "-e", "kmem:kmem_cache_alloc_node", 739 "-e", "kmem:kmem_cache_free", 740 }; 741 742 static int __cmd_record(int argc, const char **argv) 743 { 744 unsigned int rec_argc, i, j; 745 const char **rec_argv; 746 747 rec_argc = ARRAY_SIZE(record_args) + argc - 1; 748 rec_argv = calloc(rec_argc + 1, sizeof(char *)); 749 750 for (i = 0; i < ARRAY_SIZE(record_args); i++) 751 rec_argv[i] = strdup(record_args[i]); 752 753 for (j = 1; j < (unsigned int)argc; j++, i++) 754 rec_argv[i] = argv[j]; 755 756 return cmd_record(i, rec_argv, NULL); 757 } 758 759 int cmd_kmem(int argc, const char **argv, const char *prefix __used) 760 { 761 argc = parse_options(argc, argv, kmem_options, kmem_usage, 0); 762 763 if (!argc) 764 usage_with_options(kmem_usage, kmem_options); 765 766 symbol__init(); 767 768 if (!strncmp(argv[0], "rec", 3)) { 769 return __cmd_record(argc, argv); 770 } else if (!strcmp(argv[0], "stat")) { 771 setup_cpunode_map(); 772 773 if (list_empty(&caller_sort)) 774 setup_sorting(&caller_sort, default_sort_order); 775 if (list_empty(&alloc_sort)) 776 setup_sorting(&alloc_sort, default_sort_order); 777 778 return __cmd_kmem(); 779 } else 780 usage_with_options(kmem_usage, kmem_options); 781 782 return 0; 783 } 784 785