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