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