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