1 /* 2 * Copyright (C) 2009-2011, Frederic Weisbecker <fweisbec@gmail.com> 3 * 4 * Handle the callchains from the stream in an ad-hoc radix tree and then 5 * sort them in an rbtree. 6 * 7 * Using a radix for code path provides a fast retrieval and factorizes 8 * memory use. Also that lets us use the paths in a hierarchical graph view. 9 * 10 */ 11 12 #include <stdlib.h> 13 #include <stdio.h> 14 #include <stdbool.h> 15 #include <errno.h> 16 #include <math.h> 17 18 #include "asm/bug.h" 19 20 #include "hist.h" 21 #include "util.h" 22 #include "sort.h" 23 #include "machine.h" 24 #include "callchain.h" 25 26 __thread struct callchain_cursor callchain_cursor; 27 28 int 29 parse_callchain_report_opt(const char *arg) 30 { 31 char *tok, *tok2; 32 char *endptr; 33 34 symbol_conf.use_callchain = true; 35 36 if (!arg) 37 return 0; 38 39 tok = strtok((char *)arg, ","); 40 if (!tok) 41 return -1; 42 43 /* get the output mode */ 44 if (!strncmp(tok, "graph", strlen(arg))) { 45 callchain_param.mode = CHAIN_GRAPH_ABS; 46 47 } else if (!strncmp(tok, "flat", strlen(arg))) { 48 callchain_param.mode = CHAIN_FLAT; 49 } else if (!strncmp(tok, "fractal", strlen(arg))) { 50 callchain_param.mode = CHAIN_GRAPH_REL; 51 } else if (!strncmp(tok, "none", strlen(arg))) { 52 callchain_param.mode = CHAIN_NONE; 53 symbol_conf.use_callchain = false; 54 return 0; 55 } else { 56 return -1; 57 } 58 59 /* get the min percentage */ 60 tok = strtok(NULL, ","); 61 if (!tok) 62 goto setup; 63 64 callchain_param.min_percent = strtod(tok, &endptr); 65 if (tok == endptr) 66 return -1; 67 68 /* get the print limit */ 69 tok2 = strtok(NULL, ","); 70 if (!tok2) 71 goto setup; 72 73 if (tok2[0] != 'c') { 74 callchain_param.print_limit = strtoul(tok2, &endptr, 0); 75 tok2 = strtok(NULL, ","); 76 if (!tok2) 77 goto setup; 78 } 79 80 /* get the call chain order */ 81 if (!strncmp(tok2, "caller", strlen("caller"))) 82 callchain_param.order = ORDER_CALLER; 83 else if (!strncmp(tok2, "callee", strlen("callee"))) 84 callchain_param.order = ORDER_CALLEE; 85 else 86 return -1; 87 88 /* Get the sort key */ 89 tok2 = strtok(NULL, ","); 90 if (!tok2) 91 goto setup; 92 if (!strncmp(tok2, "function", strlen("function"))) 93 callchain_param.key = CCKEY_FUNCTION; 94 else if (!strncmp(tok2, "address", strlen("address"))) 95 callchain_param.key = CCKEY_ADDRESS; 96 else 97 return -1; 98 setup: 99 if (callchain_register_param(&callchain_param) < 0) { 100 pr_err("Can't register callchain params\n"); 101 return -1; 102 } 103 return 0; 104 } 105 106 static void 107 rb_insert_callchain(struct rb_root *root, struct callchain_node *chain, 108 enum chain_mode mode) 109 { 110 struct rb_node **p = &root->rb_node; 111 struct rb_node *parent = NULL; 112 struct callchain_node *rnode; 113 u64 chain_cumul = callchain_cumul_hits(chain); 114 115 while (*p) { 116 u64 rnode_cumul; 117 118 parent = *p; 119 rnode = rb_entry(parent, struct callchain_node, rb_node); 120 rnode_cumul = callchain_cumul_hits(rnode); 121 122 switch (mode) { 123 case CHAIN_FLAT: 124 if (rnode->hit < chain->hit) 125 p = &(*p)->rb_left; 126 else 127 p = &(*p)->rb_right; 128 break; 129 case CHAIN_GRAPH_ABS: /* Falldown */ 130 case CHAIN_GRAPH_REL: 131 if (rnode_cumul < chain_cumul) 132 p = &(*p)->rb_left; 133 else 134 p = &(*p)->rb_right; 135 break; 136 case CHAIN_NONE: 137 default: 138 break; 139 } 140 } 141 142 rb_link_node(&chain->rb_node, parent, p); 143 rb_insert_color(&chain->rb_node, root); 144 } 145 146 static void 147 __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node, 148 u64 min_hit) 149 { 150 struct rb_node *n; 151 struct callchain_node *child; 152 153 n = rb_first(&node->rb_root_in); 154 while (n) { 155 child = rb_entry(n, struct callchain_node, rb_node_in); 156 n = rb_next(n); 157 158 __sort_chain_flat(rb_root, child, min_hit); 159 } 160 161 if (node->hit && node->hit >= min_hit) 162 rb_insert_callchain(rb_root, node, CHAIN_FLAT); 163 } 164 165 /* 166 * Once we get every callchains from the stream, we can now 167 * sort them by hit 168 */ 169 static void 170 sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root, 171 u64 min_hit, struct callchain_param *param __maybe_unused) 172 { 173 __sort_chain_flat(rb_root, &root->node, min_hit); 174 } 175 176 static void __sort_chain_graph_abs(struct callchain_node *node, 177 u64 min_hit) 178 { 179 struct rb_node *n; 180 struct callchain_node *child; 181 182 node->rb_root = RB_ROOT; 183 n = rb_first(&node->rb_root_in); 184 185 while (n) { 186 child = rb_entry(n, struct callchain_node, rb_node_in); 187 n = rb_next(n); 188 189 __sort_chain_graph_abs(child, min_hit); 190 if (callchain_cumul_hits(child) >= min_hit) 191 rb_insert_callchain(&node->rb_root, child, 192 CHAIN_GRAPH_ABS); 193 } 194 } 195 196 static void 197 sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root, 198 u64 min_hit, struct callchain_param *param __maybe_unused) 199 { 200 __sort_chain_graph_abs(&chain_root->node, min_hit); 201 rb_root->rb_node = chain_root->node.rb_root.rb_node; 202 } 203 204 static void __sort_chain_graph_rel(struct callchain_node *node, 205 double min_percent) 206 { 207 struct rb_node *n; 208 struct callchain_node *child; 209 u64 min_hit; 210 211 node->rb_root = RB_ROOT; 212 min_hit = ceil(node->children_hit * min_percent); 213 214 n = rb_first(&node->rb_root_in); 215 while (n) { 216 child = rb_entry(n, struct callchain_node, rb_node_in); 217 n = rb_next(n); 218 219 __sort_chain_graph_rel(child, min_percent); 220 if (callchain_cumul_hits(child) >= min_hit) 221 rb_insert_callchain(&node->rb_root, child, 222 CHAIN_GRAPH_REL); 223 } 224 } 225 226 static void 227 sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root, 228 u64 min_hit __maybe_unused, struct callchain_param *param) 229 { 230 __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0); 231 rb_root->rb_node = chain_root->node.rb_root.rb_node; 232 } 233 234 int callchain_register_param(struct callchain_param *param) 235 { 236 switch (param->mode) { 237 case CHAIN_GRAPH_ABS: 238 param->sort = sort_chain_graph_abs; 239 break; 240 case CHAIN_GRAPH_REL: 241 param->sort = sort_chain_graph_rel; 242 break; 243 case CHAIN_FLAT: 244 param->sort = sort_chain_flat; 245 break; 246 case CHAIN_NONE: 247 default: 248 return -1; 249 } 250 return 0; 251 } 252 253 /* 254 * Create a child for a parent. If inherit_children, then the new child 255 * will become the new parent of it's parent children 256 */ 257 static struct callchain_node * 258 create_child(struct callchain_node *parent, bool inherit_children) 259 { 260 struct callchain_node *new; 261 262 new = zalloc(sizeof(*new)); 263 if (!new) { 264 perror("not enough memory to create child for code path tree"); 265 return NULL; 266 } 267 new->parent = parent; 268 INIT_LIST_HEAD(&new->val); 269 270 if (inherit_children) { 271 struct rb_node *n; 272 struct callchain_node *child; 273 274 new->rb_root_in = parent->rb_root_in; 275 parent->rb_root_in = RB_ROOT; 276 277 n = rb_first(&new->rb_root_in); 278 while (n) { 279 child = rb_entry(n, struct callchain_node, rb_node_in); 280 child->parent = new; 281 n = rb_next(n); 282 } 283 284 /* make it the first child */ 285 rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node); 286 rb_insert_color(&new->rb_node_in, &parent->rb_root_in); 287 } 288 289 return new; 290 } 291 292 293 /* 294 * Fill the node with callchain values 295 */ 296 static void 297 fill_node(struct callchain_node *node, struct callchain_cursor *cursor) 298 { 299 struct callchain_cursor_node *cursor_node; 300 301 node->val_nr = cursor->nr - cursor->pos; 302 if (!node->val_nr) 303 pr_warning("Warning: empty node in callchain tree\n"); 304 305 cursor_node = callchain_cursor_current(cursor); 306 307 while (cursor_node) { 308 struct callchain_list *call; 309 310 call = zalloc(sizeof(*call)); 311 if (!call) { 312 perror("not enough memory for the code path tree"); 313 return; 314 } 315 call->ip = cursor_node->ip; 316 call->ms.sym = cursor_node->sym; 317 call->ms.map = cursor_node->map; 318 list_add_tail(&call->list, &node->val); 319 320 callchain_cursor_advance(cursor); 321 cursor_node = callchain_cursor_current(cursor); 322 } 323 } 324 325 static struct callchain_node * 326 add_child(struct callchain_node *parent, 327 struct callchain_cursor *cursor, 328 u64 period) 329 { 330 struct callchain_node *new; 331 332 new = create_child(parent, false); 333 fill_node(new, cursor); 334 335 new->children_hit = 0; 336 new->hit = period; 337 return new; 338 } 339 340 static s64 match_chain(struct callchain_cursor_node *node, 341 struct callchain_list *cnode) 342 { 343 struct symbol *sym = node->sym; 344 345 if (cnode->ms.sym && sym && 346 callchain_param.key == CCKEY_FUNCTION) 347 return cnode->ms.sym->start - sym->start; 348 else 349 return cnode->ip - node->ip; 350 } 351 352 /* 353 * Split the parent in two parts (a new child is created) and 354 * give a part of its callchain to the created child. 355 * Then create another child to host the given callchain of new branch 356 */ 357 static void 358 split_add_child(struct callchain_node *parent, 359 struct callchain_cursor *cursor, 360 struct callchain_list *to_split, 361 u64 idx_parents, u64 idx_local, u64 period) 362 { 363 struct callchain_node *new; 364 struct list_head *old_tail; 365 unsigned int idx_total = idx_parents + idx_local; 366 367 /* split */ 368 new = create_child(parent, true); 369 370 /* split the callchain and move a part to the new child */ 371 old_tail = parent->val.prev; 372 list_del_range(&to_split->list, old_tail); 373 new->val.next = &to_split->list; 374 new->val.prev = old_tail; 375 to_split->list.prev = &new->val; 376 old_tail->next = &new->val; 377 378 /* split the hits */ 379 new->hit = parent->hit; 380 new->children_hit = parent->children_hit; 381 parent->children_hit = callchain_cumul_hits(new); 382 new->val_nr = parent->val_nr - idx_local; 383 parent->val_nr = idx_local; 384 385 /* create a new child for the new branch if any */ 386 if (idx_total < cursor->nr) { 387 struct callchain_node *first; 388 struct callchain_list *cnode; 389 struct callchain_cursor_node *node; 390 struct rb_node *p, **pp; 391 392 parent->hit = 0; 393 parent->children_hit += period; 394 395 node = callchain_cursor_current(cursor); 396 new = add_child(parent, cursor, period); 397 398 /* 399 * This is second child since we moved parent's children 400 * to new (first) child above. 401 */ 402 p = parent->rb_root_in.rb_node; 403 first = rb_entry(p, struct callchain_node, rb_node_in); 404 cnode = list_first_entry(&first->val, struct callchain_list, 405 list); 406 407 if (match_chain(node, cnode) < 0) 408 pp = &p->rb_left; 409 else 410 pp = &p->rb_right; 411 412 rb_link_node(&new->rb_node_in, p, pp); 413 rb_insert_color(&new->rb_node_in, &parent->rb_root_in); 414 } else { 415 parent->hit = period; 416 } 417 } 418 419 static int 420 append_chain(struct callchain_node *root, 421 struct callchain_cursor *cursor, 422 u64 period); 423 424 static void 425 append_chain_children(struct callchain_node *root, 426 struct callchain_cursor *cursor, 427 u64 period) 428 { 429 struct callchain_node *rnode; 430 struct callchain_cursor_node *node; 431 struct rb_node **p = &root->rb_root_in.rb_node; 432 struct rb_node *parent = NULL; 433 434 node = callchain_cursor_current(cursor); 435 if (!node) 436 return; 437 438 /* lookup in childrens */ 439 while (*p) { 440 s64 ret; 441 442 parent = *p; 443 rnode = rb_entry(parent, struct callchain_node, rb_node_in); 444 445 /* If at least first entry matches, rely to children */ 446 ret = append_chain(rnode, cursor, period); 447 if (ret == 0) 448 goto inc_children_hit; 449 450 if (ret < 0) 451 p = &parent->rb_left; 452 else 453 p = &parent->rb_right; 454 } 455 /* nothing in children, add to the current node */ 456 rnode = add_child(root, cursor, period); 457 rb_link_node(&rnode->rb_node_in, parent, p); 458 rb_insert_color(&rnode->rb_node_in, &root->rb_root_in); 459 460 inc_children_hit: 461 root->children_hit += period; 462 } 463 464 static int 465 append_chain(struct callchain_node *root, 466 struct callchain_cursor *cursor, 467 u64 period) 468 { 469 struct callchain_list *cnode; 470 u64 start = cursor->pos; 471 bool found = false; 472 u64 matches; 473 int cmp = 0; 474 475 /* 476 * Lookup in the current node 477 * If we have a symbol, then compare the start to match 478 * anywhere inside a function, unless function 479 * mode is disabled. 480 */ 481 list_for_each_entry(cnode, &root->val, list) { 482 struct callchain_cursor_node *node; 483 484 node = callchain_cursor_current(cursor); 485 if (!node) 486 break; 487 488 cmp = match_chain(node, cnode); 489 if (cmp) 490 break; 491 492 found = true; 493 494 callchain_cursor_advance(cursor); 495 } 496 497 /* matches not, relay no the parent */ 498 if (!found) { 499 WARN_ONCE(!cmp, "Chain comparison error\n"); 500 return cmp; 501 } 502 503 matches = cursor->pos - start; 504 505 /* we match only a part of the node. Split it and add the new chain */ 506 if (matches < root->val_nr) { 507 split_add_child(root, cursor, cnode, start, matches, period); 508 return 0; 509 } 510 511 /* we match 100% of the path, increment the hit */ 512 if (matches == root->val_nr && cursor->pos == cursor->nr) { 513 root->hit += period; 514 return 0; 515 } 516 517 /* We match the node and still have a part remaining */ 518 append_chain_children(root, cursor, period); 519 520 return 0; 521 } 522 523 int callchain_append(struct callchain_root *root, 524 struct callchain_cursor *cursor, 525 u64 period) 526 { 527 if (!cursor->nr) 528 return 0; 529 530 callchain_cursor_commit(cursor); 531 532 append_chain_children(&root->node, cursor, period); 533 534 if (cursor->nr > root->max_depth) 535 root->max_depth = cursor->nr; 536 537 return 0; 538 } 539 540 static int 541 merge_chain_branch(struct callchain_cursor *cursor, 542 struct callchain_node *dst, struct callchain_node *src) 543 { 544 struct callchain_cursor_node **old_last = cursor->last; 545 struct callchain_node *child; 546 struct callchain_list *list, *next_list; 547 struct rb_node *n; 548 int old_pos = cursor->nr; 549 int err = 0; 550 551 list_for_each_entry_safe(list, next_list, &src->val, list) { 552 callchain_cursor_append(cursor, list->ip, 553 list->ms.map, list->ms.sym); 554 list_del(&list->list); 555 free(list); 556 } 557 558 if (src->hit) { 559 callchain_cursor_commit(cursor); 560 append_chain_children(dst, cursor, src->hit); 561 } 562 563 n = rb_first(&src->rb_root_in); 564 while (n) { 565 child = container_of(n, struct callchain_node, rb_node_in); 566 n = rb_next(n); 567 rb_erase(&child->rb_node_in, &src->rb_root_in); 568 569 err = merge_chain_branch(cursor, dst, child); 570 if (err) 571 break; 572 573 free(child); 574 } 575 576 cursor->nr = old_pos; 577 cursor->last = old_last; 578 579 return err; 580 } 581 582 int callchain_merge(struct callchain_cursor *cursor, 583 struct callchain_root *dst, struct callchain_root *src) 584 { 585 return merge_chain_branch(cursor, &dst->node, &src->node); 586 } 587 588 int callchain_cursor_append(struct callchain_cursor *cursor, 589 u64 ip, struct map *map, struct symbol *sym) 590 { 591 struct callchain_cursor_node *node = *cursor->last; 592 593 if (!node) { 594 node = calloc(1, sizeof(*node)); 595 if (!node) 596 return -ENOMEM; 597 598 *cursor->last = node; 599 } 600 601 node->ip = ip; 602 node->map = map; 603 node->sym = sym; 604 605 cursor->nr++; 606 607 cursor->last = &node->next; 608 609 return 0; 610 } 611 612 int sample__resolve_callchain(struct perf_sample *sample, struct symbol **parent, 613 struct perf_evsel *evsel, struct addr_location *al, 614 int max_stack) 615 { 616 if (sample->callchain == NULL) 617 return 0; 618 619 if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain || 620 sort__has_parent) { 621 return machine__resolve_callchain(al->machine, evsel, al->thread, 622 sample, parent, al, max_stack); 623 } 624 return 0; 625 } 626 627 int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample) 628 { 629 if (!symbol_conf.use_callchain || sample->callchain == NULL) 630 return 0; 631 return callchain_append(he->callchain, &callchain_cursor, sample->period); 632 } 633 634 int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node, 635 bool hide_unresolved) 636 { 637 al->map = node->map; 638 al->sym = node->sym; 639 if (node->map) 640 al->addr = node->map->map_ip(node->map, node->ip); 641 else 642 al->addr = node->ip; 643 644 if (al->sym == NULL) { 645 if (hide_unresolved) 646 return 0; 647 if (al->map == NULL) 648 goto out; 649 } 650 651 if (al->map->groups == &al->machine->kmaps) { 652 if (machine__is_host(al->machine)) { 653 al->cpumode = PERF_RECORD_MISC_KERNEL; 654 al->level = 'k'; 655 } else { 656 al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL; 657 al->level = 'g'; 658 } 659 } else { 660 if (machine__is_host(al->machine)) { 661 al->cpumode = PERF_RECORD_MISC_USER; 662 al->level = '.'; 663 } else if (perf_guest) { 664 al->cpumode = PERF_RECORD_MISC_GUEST_USER; 665 al->level = 'u'; 666 } else { 667 al->cpumode = PERF_RECORD_MISC_HYPERVISOR; 668 al->level = 'H'; 669 } 670 } 671 672 out: 673 return 1; 674 } 675