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