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