Home | History | Annotate | Download | only in util
      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