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