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