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