1 /* 2 * Copyright (C) 2009, 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 "callchain.h" 19 20 #define chain_for_each_child(child, parent) \ 21 list_for_each_entry(child, &parent->children, brothers) 22 23 static void 24 rb_insert_callchain(struct rb_root *root, struct callchain_node *chain, 25 enum chain_mode mode) 26 { 27 struct rb_node **p = &root->rb_node; 28 struct rb_node *parent = NULL; 29 struct callchain_node *rnode; 30 u64 chain_cumul = cumul_hits(chain); 31 32 while (*p) { 33 u64 rnode_cumul; 34 35 parent = *p; 36 rnode = rb_entry(parent, struct callchain_node, rb_node); 37 rnode_cumul = cumul_hits(rnode); 38 39 switch (mode) { 40 case CHAIN_FLAT: 41 if (rnode->hit < chain->hit) 42 p = &(*p)->rb_left; 43 else 44 p = &(*p)->rb_right; 45 break; 46 case CHAIN_GRAPH_ABS: /* Falldown */ 47 case CHAIN_GRAPH_REL: 48 if (rnode_cumul < chain_cumul) 49 p = &(*p)->rb_left; 50 else 51 p = &(*p)->rb_right; 52 break; 53 case CHAIN_NONE: 54 default: 55 break; 56 } 57 } 58 59 rb_link_node(&chain->rb_node, parent, p); 60 rb_insert_color(&chain->rb_node, root); 61 } 62 63 static void 64 __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node, 65 u64 min_hit) 66 { 67 struct callchain_node *child; 68 69 chain_for_each_child(child, node) 70 __sort_chain_flat(rb_root, child, min_hit); 71 72 if (node->hit && node->hit >= min_hit) 73 rb_insert_callchain(rb_root, node, CHAIN_FLAT); 74 } 75 76 /* 77 * Once we get every callchains from the stream, we can now 78 * sort them by hit 79 */ 80 static void 81 sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node, 82 u64 min_hit, struct callchain_param *param __used) 83 { 84 __sort_chain_flat(rb_root, node, min_hit); 85 } 86 87 static void __sort_chain_graph_abs(struct callchain_node *node, 88 u64 min_hit) 89 { 90 struct callchain_node *child; 91 92 node->rb_root = RB_ROOT; 93 94 chain_for_each_child(child, node) { 95 __sort_chain_graph_abs(child, min_hit); 96 if (cumul_hits(child) >= min_hit) 97 rb_insert_callchain(&node->rb_root, child, 98 CHAIN_GRAPH_ABS); 99 } 100 } 101 102 static void 103 sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_node *chain_root, 104 u64 min_hit, struct callchain_param *param __used) 105 { 106 __sort_chain_graph_abs(chain_root, min_hit); 107 rb_root->rb_node = chain_root->rb_root.rb_node; 108 } 109 110 static void __sort_chain_graph_rel(struct callchain_node *node, 111 double min_percent) 112 { 113 struct callchain_node *child; 114 u64 min_hit; 115 116 node->rb_root = RB_ROOT; 117 min_hit = ceil(node->children_hit * min_percent); 118 119 chain_for_each_child(child, node) { 120 __sort_chain_graph_rel(child, min_percent); 121 if (cumul_hits(child) >= min_hit) 122 rb_insert_callchain(&node->rb_root, child, 123 CHAIN_GRAPH_REL); 124 } 125 } 126 127 static void 128 sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_node *chain_root, 129 u64 min_hit __used, struct callchain_param *param) 130 { 131 __sort_chain_graph_rel(chain_root, param->min_percent / 100.0); 132 rb_root->rb_node = chain_root->rb_root.rb_node; 133 } 134 135 int register_callchain_param(struct callchain_param *param) 136 { 137 switch (param->mode) { 138 case CHAIN_GRAPH_ABS: 139 param->sort = sort_chain_graph_abs; 140 break; 141 case CHAIN_GRAPH_REL: 142 param->sort = sort_chain_graph_rel; 143 break; 144 case CHAIN_FLAT: 145 param->sort = sort_chain_flat; 146 break; 147 case CHAIN_NONE: 148 default: 149 return -1; 150 } 151 return 0; 152 } 153 154 /* 155 * Create a child for a parent. If inherit_children, then the new child 156 * will become the new parent of it's parent children 157 */ 158 static struct callchain_node * 159 create_child(struct callchain_node *parent, bool inherit_children) 160 { 161 struct callchain_node *new; 162 163 new = malloc(sizeof(*new)); 164 if (!new) { 165 perror("not enough memory to create child for code path tree"); 166 return NULL; 167 } 168 new->parent = parent; 169 INIT_LIST_HEAD(&new->children); 170 INIT_LIST_HEAD(&new->val); 171 172 if (inherit_children) { 173 struct callchain_node *next; 174 175 list_splice(&parent->children, &new->children); 176 INIT_LIST_HEAD(&parent->children); 177 178 chain_for_each_child(next, new) 179 next->parent = new; 180 } 181 list_add_tail(&new->brothers, &parent->children); 182 183 return new; 184 } 185 186 /* 187 * Fill the node with callchain values 188 */ 189 static void 190 fill_node(struct callchain_node *node, struct ip_callchain *chain, 191 int start, struct symbol **syms) 192 { 193 unsigned int i; 194 195 for (i = start; i < chain->nr; i++) { 196 struct callchain_list *call; 197 198 call = malloc(sizeof(*call)); 199 if (!call) { 200 perror("not enough memory for the code path tree"); 201 return; 202 } 203 call->ip = chain->ips[i]; 204 call->sym = syms[i]; 205 list_add_tail(&call->list, &node->val); 206 } 207 node->val_nr = chain->nr - start; 208 if (!node->val_nr) 209 pr_warning("Warning: empty node in callchain tree\n"); 210 } 211 212 static void 213 add_child(struct callchain_node *parent, struct ip_callchain *chain, 214 int start, struct symbol **syms) 215 { 216 struct callchain_node *new; 217 218 new = create_child(parent, false); 219 fill_node(new, chain, start, syms); 220 221 new->children_hit = 0; 222 new->hit = 1; 223 } 224 225 /* 226 * Split the parent in two parts (a new child is created) and 227 * give a part of its callchain to the created child. 228 * Then create another child to host the given callchain of new branch 229 */ 230 static void 231 split_add_child(struct callchain_node *parent, struct ip_callchain *chain, 232 struct callchain_list *to_split, int idx_parents, int idx_local, 233 struct symbol **syms) 234 { 235 struct callchain_node *new; 236 struct list_head *old_tail; 237 unsigned int idx_total = idx_parents + idx_local; 238 239 /* split */ 240 new = create_child(parent, true); 241 242 /* split the callchain and move a part to the new child */ 243 old_tail = parent->val.prev; 244 list_del_range(&to_split->list, old_tail); 245 new->val.next = &to_split->list; 246 new->val.prev = old_tail; 247 to_split->list.prev = &new->val; 248 old_tail->next = &new->val; 249 250 /* split the hits */ 251 new->hit = parent->hit; 252 new->children_hit = parent->children_hit; 253 parent->children_hit = cumul_hits(new); 254 new->val_nr = parent->val_nr - idx_local; 255 parent->val_nr = idx_local; 256 257 /* create a new child for the new branch if any */ 258 if (idx_total < chain->nr) { 259 parent->hit = 0; 260 add_child(parent, chain, idx_total, syms); 261 parent->children_hit++; 262 } else { 263 parent->hit = 1; 264 } 265 } 266 267 static int 268 __append_chain(struct callchain_node *root, struct ip_callchain *chain, 269 unsigned int start, struct symbol **syms); 270 271 static void 272 __append_chain_children(struct callchain_node *root, struct ip_callchain *chain, 273 struct symbol **syms, unsigned int start) 274 { 275 struct callchain_node *rnode; 276 277 /* lookup in childrens */ 278 chain_for_each_child(rnode, root) { 279 unsigned int ret = __append_chain(rnode, chain, start, syms); 280 281 if (!ret) 282 goto inc_children_hit; 283 } 284 /* nothing in children, add to the current node */ 285 add_child(root, chain, start, syms); 286 287 inc_children_hit: 288 root->children_hit++; 289 } 290 291 static int 292 __append_chain(struct callchain_node *root, struct ip_callchain *chain, 293 unsigned int start, struct symbol **syms) 294 { 295 struct callchain_list *cnode; 296 unsigned int i = start; 297 bool found = false; 298 299 /* 300 * Lookup in the current node 301 * If we have a symbol, then compare the start to match 302 * anywhere inside a function. 303 */ 304 list_for_each_entry(cnode, &root->val, list) { 305 if (i == chain->nr) 306 break; 307 if (cnode->sym && syms[i]) { 308 if (cnode->sym->start != syms[i]->start) 309 break; 310 } else if (cnode->ip != chain->ips[i]) 311 break; 312 if (!found) 313 found = true; 314 i++; 315 } 316 317 /* matches not, relay on the parent */ 318 if (!found) 319 return -1; 320 321 /* we match only a part of the node. Split it and add the new chain */ 322 if (i - start < root->val_nr) { 323 split_add_child(root, chain, cnode, start, i - start, syms); 324 return 0; 325 } 326 327 /* we match 100% of the path, increment the hit */ 328 if (i - start == root->val_nr && i == chain->nr) { 329 root->hit++; 330 return 0; 331 } 332 333 /* We match the node and still have a part remaining */ 334 __append_chain_children(root, chain, syms, i); 335 336 return 0; 337 } 338 339 void append_chain(struct callchain_node *root, struct ip_callchain *chain, 340 struct symbol **syms) 341 { 342 if (!chain->nr) 343 return; 344 __append_chain_children(root, chain, syms, 0); 345 } 346