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 "hist.h" 19 #include "util.h" 20 #include "callchain.h" 21 22 __thread struct callchain_cursor callchain_cursor; 23 24 static void 25 rb_insert_callchain(struct rb_root *root, struct callchain_node *chain, 26 enum chain_mode mode) 27 { 28 struct rb_node **p = &root->rb_node; 29 struct rb_node *parent = NULL; 30 struct callchain_node *rnode; 31 u64 chain_cumul = callchain_cumul_hits(chain); 32 33 while (*p) { 34 u64 rnode_cumul; 35 36 parent = *p; 37 rnode = rb_entry(parent, struct callchain_node, rb_node); 38 rnode_cumul = callchain_cumul_hits(rnode); 39 40 switch (mode) { 41 case CHAIN_FLAT: 42 if (rnode->hit < chain->hit) 43 p = &(*p)->rb_left; 44 else 45 p = &(*p)->rb_right; 46 break; 47 case CHAIN_GRAPH_ABS: /* Falldown */ 48 case CHAIN_GRAPH_REL: 49 if (rnode_cumul < chain_cumul) 50 p = &(*p)->rb_left; 51 else 52 p = &(*p)->rb_right; 53 break; 54 case CHAIN_NONE: 55 default: 56 break; 57 } 58 } 59 60 rb_link_node(&chain->rb_node, parent, p); 61 rb_insert_color(&chain->rb_node, root); 62 } 63 64 static void 65 __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node, 66 u64 min_hit) 67 { 68 struct rb_node *n; 69 struct callchain_node *child; 70 71 n = rb_first(&node->rb_root_in); 72 while (n) { 73 child = rb_entry(n, struct callchain_node, rb_node_in); 74 n = rb_next(n); 75 76 __sort_chain_flat(rb_root, child, min_hit); 77 } 78 79 if (node->hit && node->hit >= min_hit) 80 rb_insert_callchain(rb_root, node, CHAIN_FLAT); 81 } 82 83 /* 84 * Once we get every callchains from the stream, we can now 85 * sort them by hit 86 */ 87 static void 88 sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root, 89 u64 min_hit, struct callchain_param *param __maybe_unused) 90 { 91 __sort_chain_flat(rb_root, &root->node, min_hit); 92 } 93 94 static void __sort_chain_graph_abs(struct callchain_node *node, 95 u64 min_hit) 96 { 97 struct rb_node *n; 98 struct callchain_node *child; 99 100 node->rb_root = RB_ROOT; 101 n = rb_first(&node->rb_root_in); 102 103 while (n) { 104 child = rb_entry(n, struct callchain_node, rb_node_in); 105 n = rb_next(n); 106 107 __sort_chain_graph_abs(child, min_hit); 108 if (callchain_cumul_hits(child) >= min_hit) 109 rb_insert_callchain(&node->rb_root, child, 110 CHAIN_GRAPH_ABS); 111 } 112 } 113 114 static void 115 sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root, 116 u64 min_hit, struct callchain_param *param __maybe_unused) 117 { 118 __sort_chain_graph_abs(&chain_root->node, min_hit); 119 rb_root->rb_node = chain_root->node.rb_root.rb_node; 120 } 121 122 static void __sort_chain_graph_rel(struct callchain_node *node, 123 double min_percent) 124 { 125 struct rb_node *n; 126 struct callchain_node *child; 127 u64 min_hit; 128 129 node->rb_root = RB_ROOT; 130 min_hit = ceil(node->children_hit * min_percent); 131 132 n = rb_first(&node->rb_root_in); 133 while (n) { 134 child = rb_entry(n, struct callchain_node, rb_node_in); 135 n = rb_next(n); 136 137 __sort_chain_graph_rel(child, min_percent); 138 if (callchain_cumul_hits(child) >= min_hit) 139 rb_insert_callchain(&node->rb_root, child, 140 CHAIN_GRAPH_REL); 141 } 142 } 143 144 static void 145 sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root, 146 u64 min_hit __maybe_unused, struct callchain_param *param) 147 { 148 __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0); 149 rb_root->rb_node = chain_root->node.rb_root.rb_node; 150 } 151 152 int callchain_register_param(struct callchain_param *param) 153 { 154 switch (param->mode) { 155 case CHAIN_GRAPH_ABS: 156 param->sort = sort_chain_graph_abs; 157 break; 158 case CHAIN_GRAPH_REL: 159 param->sort = sort_chain_graph_rel; 160 break; 161 case CHAIN_FLAT: 162 param->sort = sort_chain_flat; 163 break; 164 case CHAIN_NONE: 165 default: 166 return -1; 167 } 168 return 0; 169 } 170 171 /* 172 * Create a child for a parent. If inherit_children, then the new child 173 * will become the new parent of it's parent children 174 */ 175 static struct callchain_node * 176 create_child(struct callchain_node *parent, bool inherit_children) 177 { 178 struct callchain_node *new; 179 180 new = zalloc(sizeof(*new)); 181 if (!new) { 182 perror("not enough memory to create child for code path tree"); 183 return NULL; 184 } 185 new->parent = parent; 186 INIT_LIST_HEAD(&new->val); 187 188 if (inherit_children) { 189 struct rb_node *n; 190 struct callchain_node *child; 191 192 new->rb_root_in = parent->rb_root_in; 193 parent->rb_root_in = RB_ROOT; 194 195 n = rb_first(&new->rb_root_in); 196 while (n) { 197 child = rb_entry(n, struct callchain_node, rb_node_in); 198 child->parent = new; 199 n = rb_next(n); 200 } 201 202 /* make it the first child */ 203 rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node); 204 rb_insert_color(&new->rb_node_in, &parent->rb_root_in); 205 } 206 207 return new; 208 } 209 210 211 /* 212 * Fill the node with callchain values 213 */ 214 static void 215 fill_node(struct callchain_node *node, struct callchain_cursor *cursor) 216 { 217 struct callchain_cursor_node *cursor_node; 218 219 node->val_nr = cursor->nr - cursor->pos; 220 if (!node->val_nr) 221 pr_warning("Warning: empty node in callchain tree\n"); 222 223 cursor_node = callchain_cursor_current(cursor); 224 225 while (cursor_node) { 226 struct callchain_list *call; 227 228 call = zalloc(sizeof(*call)); 229 if (!call) { 230 perror("not enough memory for the code path tree"); 231 return; 232 } 233 call->ip = cursor_node->ip; 234 call->ms.sym = cursor_node->sym; 235 call->ms.map = cursor_node->map; 236 list_add_tail(&call->list, &node->val); 237 238 callchain_cursor_advance(cursor); 239 cursor_node = callchain_cursor_current(cursor); 240 } 241 } 242 243 static struct callchain_node * 244 add_child(struct callchain_node *parent, 245 struct callchain_cursor *cursor, 246 u64 period) 247 { 248 struct callchain_node *new; 249 250 new = create_child(parent, false); 251 fill_node(new, cursor); 252 253 new->children_hit = 0; 254 new->hit = period; 255 return new; 256 } 257 258 static s64 match_chain(struct callchain_cursor_node *node, 259 struct callchain_list *cnode) 260 { 261 struct symbol *sym = node->sym; 262 263 if (cnode->ms.sym && sym && 264 callchain_param.key == CCKEY_FUNCTION) 265 return cnode->ms.sym->start - sym->start; 266 else 267 return cnode->ip - node->ip; 268 } 269 270 /* 271 * Split the parent in two parts (a new child is created) and 272 * give a part of its callchain to the created child. 273 * Then create another child to host the given callchain of new branch 274 */ 275 static void 276 split_add_child(struct callchain_node *parent, 277 struct callchain_cursor *cursor, 278 struct callchain_list *to_split, 279 u64 idx_parents, u64 idx_local, u64 period) 280 { 281 struct callchain_node *new; 282 struct list_head *old_tail; 283 unsigned int idx_total = idx_parents + idx_local; 284 285 /* split */ 286 new = create_child(parent, true); 287 288 /* split the callchain and move a part to the new child */ 289 old_tail = parent->val.prev; 290 list_del_range(&to_split->list, old_tail); 291 new->val.next = &to_split->list; 292 new->val.prev = old_tail; 293 to_split->list.prev = &new->val; 294 old_tail->next = &new->val; 295 296 /* split the hits */ 297 new->hit = parent->hit; 298 new->children_hit = parent->children_hit; 299 parent->children_hit = callchain_cumul_hits(new); 300 new->val_nr = parent->val_nr - idx_local; 301 parent->val_nr = idx_local; 302 303 /* create a new child for the new branch if any */ 304 if (idx_total < cursor->nr) { 305 struct callchain_node *first; 306 struct callchain_list *cnode; 307 struct callchain_cursor_node *node; 308 struct rb_node *p, **pp; 309 310 parent->hit = 0; 311 parent->children_hit += period; 312 313 node = callchain_cursor_current(cursor); 314 new = add_child(parent, cursor, period); 315 316 /* 317 * This is second child since we moved parent's children 318 * to new (first) child above. 319 */ 320 p = parent->rb_root_in.rb_node; 321 first = rb_entry(p, struct callchain_node, rb_node_in); 322 cnode = list_first_entry(&first->val, struct callchain_list, 323 list); 324 325 if (match_chain(node, cnode) < 0) 326 pp = &p->rb_left; 327 else 328 pp = &p->rb_right; 329 330 rb_link_node(&new->rb_node_in, p, pp); 331 rb_insert_color(&new->rb_node_in, &parent->rb_root_in); 332 } else { 333 parent->hit = period; 334 } 335 } 336 337 static int 338 append_chain(struct callchain_node *root, 339 struct callchain_cursor *cursor, 340 u64 period); 341 342 static void 343 append_chain_children(struct callchain_node *root, 344 struct callchain_cursor *cursor, 345 u64 period) 346 { 347 struct callchain_node *rnode; 348 struct callchain_cursor_node *node; 349 struct rb_node **p = &root->rb_root_in.rb_node; 350 struct rb_node *parent = NULL; 351 352 node = callchain_cursor_current(cursor); 353 if (!node) 354 return; 355 356 /* lookup in childrens */ 357 while (*p) { 358 s64 ret; 359 struct callchain_list *cnode; 360 361 parent = *p; 362 rnode = rb_entry(parent, struct callchain_node, rb_node_in); 363 cnode = list_first_entry(&rnode->val, struct callchain_list, 364 list); 365 366 /* just check first entry */ 367 ret = match_chain(node, cnode); 368 if (ret == 0) { 369 append_chain(rnode, cursor, period); 370 goto inc_children_hit; 371 } 372 373 if (ret < 0) 374 p = &parent->rb_left; 375 else 376 p = &parent->rb_right; 377 } 378 /* nothing in children, add to the current node */ 379 rnode = add_child(root, cursor, period); 380 rb_link_node(&rnode->rb_node_in, parent, p); 381 rb_insert_color(&rnode->rb_node_in, &root->rb_root_in); 382 383 inc_children_hit: 384 root->children_hit += period; 385 } 386 387 static int 388 append_chain(struct callchain_node *root, 389 struct callchain_cursor *cursor, 390 u64 period) 391 { 392 struct callchain_cursor_node *curr_snap = cursor->curr; 393 struct callchain_list *cnode; 394 u64 start = cursor->pos; 395 bool found = false; 396 u64 matches; 397 398 /* 399 * Lookup in the current node 400 * If we have a symbol, then compare the start to match 401 * anywhere inside a function, unless function 402 * mode is disabled. 403 */ 404 list_for_each_entry(cnode, &root->val, list) { 405 struct callchain_cursor_node *node; 406 407 node = callchain_cursor_current(cursor); 408 if (!node) 409 break; 410 411 if (match_chain(node, cnode) != 0) 412 break; 413 414 found = true; 415 416 callchain_cursor_advance(cursor); 417 } 418 419 /* matches not, relay no the parent */ 420 if (!found) { 421 cursor->curr = curr_snap; 422 cursor->pos = start; 423 return -1; 424 } 425 426 matches = cursor->pos - start; 427 428 /* we match only a part of the node. Split it and add the new chain */ 429 if (matches < root->val_nr) { 430 split_add_child(root, cursor, cnode, start, matches, period); 431 return 0; 432 } 433 434 /* we match 100% of the path, increment the hit */ 435 if (matches == root->val_nr && cursor->pos == cursor->nr) { 436 root->hit += period; 437 return 0; 438 } 439 440 /* We match the node and still have a part remaining */ 441 append_chain_children(root, cursor, period); 442 443 return 0; 444 } 445 446 int callchain_append(struct callchain_root *root, 447 struct callchain_cursor *cursor, 448 u64 period) 449 { 450 if (!cursor->nr) 451 return 0; 452 453 callchain_cursor_commit(cursor); 454 455 append_chain_children(&root->node, cursor, period); 456 457 if (cursor->nr > root->max_depth) 458 root->max_depth = cursor->nr; 459 460 return 0; 461 } 462 463 static int 464 merge_chain_branch(struct callchain_cursor *cursor, 465 struct callchain_node *dst, struct callchain_node *src) 466 { 467 struct callchain_cursor_node **old_last = cursor->last; 468 struct callchain_node *child; 469 struct callchain_list *list, *next_list; 470 struct rb_node *n; 471 int old_pos = cursor->nr; 472 int err = 0; 473 474 list_for_each_entry_safe(list, next_list, &src->val, list) { 475 callchain_cursor_append(cursor, list->ip, 476 list->ms.map, list->ms.sym); 477 list_del(&list->list); 478 free(list); 479 } 480 481 if (src->hit) { 482 callchain_cursor_commit(cursor); 483 append_chain_children(dst, cursor, src->hit); 484 } 485 486 n = rb_first(&src->rb_root_in); 487 while (n) { 488 child = container_of(n, struct callchain_node, rb_node_in); 489 n = rb_next(n); 490 rb_erase(&child->rb_node_in, &src->rb_root_in); 491 492 err = merge_chain_branch(cursor, dst, child); 493 if (err) 494 break; 495 496 free(child); 497 } 498 499 cursor->nr = old_pos; 500 cursor->last = old_last; 501 502 return err; 503 } 504 505 int callchain_merge(struct callchain_cursor *cursor, 506 struct callchain_root *dst, struct callchain_root *src) 507 { 508 return merge_chain_branch(cursor, &dst->node, &src->node); 509 } 510 511 int callchain_cursor_append(struct callchain_cursor *cursor, 512 u64 ip, struct map *map, struct symbol *sym) 513 { 514 struct callchain_cursor_node *node = *cursor->last; 515 516 if (!node) { 517 node = calloc(1, sizeof(*node)); 518 if (!node) 519 return -ENOMEM; 520 521 *cursor->last = node; 522 } 523 524 node->ip = ip; 525 node->map = map; 526 node->sym = sym; 527 528 cursor->nr++; 529 530 cursor->last = &node->next; 531 532 return 0; 533 } 534