1/*
   2 * Copyright (C) 2009-2011, 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 "asm/bug.h"
  19
  20#include "hist.h"
  21#include "util.h"
  22#include "sort.h"
  23#include "machine.h"
  24#include "callchain.h"
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  25
  26__thread struct callchain_cursor callchain_cursor;
  27
  28int parse_callchain_record_opt(const char *arg, struct callchain_param *param)
  29{
  30	return parse_callchain_record(arg, param);
  31}
  32
  33static int parse_callchain_mode(const char *value)
  34{
  35	if (!strncmp(value, "graph", strlen(value))) {
  36		callchain_param.mode = CHAIN_GRAPH_ABS;
  37		return 0;
  38	}
  39	if (!strncmp(value, "flat", strlen(value))) {
  40		callchain_param.mode = CHAIN_FLAT;
  41		return 0;
  42	}
  43	if (!strncmp(value, "fractal", strlen(value))) {
  44		callchain_param.mode = CHAIN_GRAPH_REL;
  45		return 0;
  46	}
  47	if (!strncmp(value, "folded", strlen(value))) {
  48		callchain_param.mode = CHAIN_FOLDED;
  49		return 0;
  50	}
  51	return -1;
  52}
  53
  54static int parse_callchain_order(const char *value)
  55{
  56	if (!strncmp(value, "caller", strlen(value))) {
  57		callchain_param.order = ORDER_CALLER;
  58		callchain_param.order_set = true;
  59		return 0;
  60	}
  61	if (!strncmp(value, "callee", strlen(value))) {
  62		callchain_param.order = ORDER_CALLEE;
  63		callchain_param.order_set = true;
  64		return 0;
  65	}
  66	return -1;
  67}
  68
  69static int parse_callchain_sort_key(const char *value)
  70{
  71	if (!strncmp(value, "function", strlen(value))) {
  72		callchain_param.key = CCKEY_FUNCTION;
  73		return 0;
  74	}
  75	if (!strncmp(value, "address", strlen(value))) {
  76		callchain_param.key = CCKEY_ADDRESS;
  77		return 0;
  78	}
 
 
 
 
  79	if (!strncmp(value, "branch", strlen(value))) {
  80		callchain_param.branch_callstack = 1;
  81		return 0;
  82	}
  83	return -1;
  84}
  85
  86static int parse_callchain_value(const char *value)
  87{
  88	if (!strncmp(value, "percent", strlen(value))) {
  89		callchain_param.value = CCVAL_PERCENT;
  90		return 0;
  91	}
  92	if (!strncmp(value, "period", strlen(value))) {
  93		callchain_param.value = CCVAL_PERIOD;
  94		return 0;
  95	}
  96	if (!strncmp(value, "count", strlen(value))) {
  97		callchain_param.value = CCVAL_COUNT;
  98		return 0;
  99	}
 100	return -1;
 101}
 102
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 103static int
 104__parse_callchain_report_opt(const char *arg, bool allow_record_opt)
 105{
 106	char *tok;
 107	char *endptr;
 108	bool minpcnt_set = false;
 109	bool record_opt_set = false;
 110	bool try_stack_size = false;
 111
 
 112	symbol_conf.use_callchain = true;
 113
 114	if (!arg)
 115		return 0;
 116
 117	while ((tok = strtok((char *)arg, ",")) != NULL) {
 118		if (!strncmp(tok, "none", strlen(tok))) {
 119			callchain_param.mode = CHAIN_NONE;
 
 120			symbol_conf.use_callchain = false;
 121			return 0;
 122		}
 123
 124		if (!parse_callchain_mode(tok) ||
 125		    !parse_callchain_order(tok) ||
 126		    !parse_callchain_sort_key(tok) ||
 127		    !parse_callchain_value(tok)) {
 128			/* parsing ok - move on to the next */
 129			try_stack_size = false;
 130			goto next;
 131		} else if (allow_record_opt && !record_opt_set) {
 132			if (parse_callchain_record(tok, &callchain_param))
 133				goto try_numbers;
 134
 135			/* assume that number followed by 'dwarf' is stack size */
 136			if (callchain_param.record_mode == CALLCHAIN_DWARF)
 137				try_stack_size = true;
 138
 139			record_opt_set = true;
 140			goto next;
 141		}
 142
 143try_numbers:
 144		if (try_stack_size) {
 145			unsigned long size = 0;
 146
 147			if (get_stack_size(tok, &size) < 0)
 148				return -1;
 149			callchain_param.dump_size = size;
 150			try_stack_size = false;
 151		} else if (!minpcnt_set) {
 152			/* try to get the min percent */
 153			callchain_param.min_percent = strtod(tok, &endptr);
 154			if (tok == endptr)
 155				return -1;
 156			minpcnt_set = true;
 157		} else {
 158			/* try print limit at last */
 159			callchain_param.print_limit = strtoul(tok, &endptr, 0);
 160			if (tok == endptr)
 161				return -1;
 162		}
 163next:
 164		arg = NULL;
 165	}
 166
 167	if (callchain_register_param(&callchain_param) < 0) {
 168		pr_err("Can't register callchain params\n");
 169		return -1;
 170	}
 171	return 0;
 172}
 173
 174int parse_callchain_report_opt(const char *arg)
 175{
 176	return __parse_callchain_report_opt(arg, false);
 177}
 178
 179int parse_callchain_top_opt(const char *arg)
 180{
 181	return __parse_callchain_report_opt(arg, true);
 182}
 183
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 184int perf_callchain_config(const char *var, const char *value)
 185{
 186	char *endptr;
 187
 188	if (prefixcmp(var, "call-graph."))
 189		return 0;
 190	var += sizeof("call-graph.") - 1;
 191
 192	if (!strcmp(var, "record-mode"))
 193		return parse_callchain_record_opt(value, &callchain_param);
 194#ifdef HAVE_DWARF_UNWIND_SUPPORT
 195	if (!strcmp(var, "dump-size")) {
 196		unsigned long size = 0;
 197		int ret;
 198
 199		ret = get_stack_size(value, &size);
 200		callchain_param.dump_size = size;
 201
 202		return ret;
 203	}
 204#endif
 205	if (!strcmp(var, "print-type"))
 206		return parse_callchain_mode(value);
 207	if (!strcmp(var, "order"))
 208		return parse_callchain_order(value);
 209	if (!strcmp(var, "sort-key"))
 210		return parse_callchain_sort_key(value);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 211	if (!strcmp(var, "threshold")) {
 212		callchain_param.min_percent = strtod(value, &endptr);
 213		if (value == endptr)
 
 214			return -1;
 
 215	}
 216	if (!strcmp(var, "print-limit")) {
 217		callchain_param.print_limit = strtod(value, &endptr);
 218		if (value == endptr)
 
 219			return -1;
 
 220	}
 221
 222	return 0;
 223}
 224
 225static void
 226rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
 227		    enum chain_mode mode)
 228{
 229	struct rb_node **p = &root->rb_node;
 230	struct rb_node *parent = NULL;
 231	struct callchain_node *rnode;
 232	u64 chain_cumul = callchain_cumul_hits(chain);
 233
 234	while (*p) {
 235		u64 rnode_cumul;
 236
 237		parent = *p;
 238		rnode = rb_entry(parent, struct callchain_node, rb_node);
 239		rnode_cumul = callchain_cumul_hits(rnode);
 240
 241		switch (mode) {
 242		case CHAIN_FLAT:
 243		case CHAIN_FOLDED:
 244			if (rnode->hit < chain->hit)
 245				p = &(*p)->rb_left;
 246			else
 247				p = &(*p)->rb_right;
 248			break;
 249		case CHAIN_GRAPH_ABS: /* Falldown */
 250		case CHAIN_GRAPH_REL:
 251			if (rnode_cumul < chain_cumul)
 252				p = &(*p)->rb_left;
 253			else
 254				p = &(*p)->rb_right;
 255			break;
 256		case CHAIN_NONE:
 257		default:
 258			break;
 259		}
 260	}
 261
 262	rb_link_node(&chain->rb_node, parent, p);
 263	rb_insert_color(&chain->rb_node, root);
 264}
 265
 266static void
 267__sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
 268		  u64 min_hit)
 269{
 270	struct rb_node *n;
 271	struct callchain_node *child;
 272
 273	n = rb_first(&node->rb_root_in);
 274	while (n) {
 275		child = rb_entry(n, struct callchain_node, rb_node_in);
 276		n = rb_next(n);
 277
 278		__sort_chain_flat(rb_root, child, min_hit);
 279	}
 280
 281	if (node->hit && node->hit >= min_hit)
 282		rb_insert_callchain(rb_root, node, CHAIN_FLAT);
 283}
 284
 285/*
 286 * Once we get every callchains from the stream, we can now
 287 * sort them by hit
 288 */
 289static void
 290sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
 291		u64 min_hit, struct callchain_param *param __maybe_unused)
 292{
 293	*rb_root = RB_ROOT;
 294	__sort_chain_flat(rb_root, &root->node, min_hit);
 295}
 296
 297static void __sort_chain_graph_abs(struct callchain_node *node,
 298				   u64 min_hit)
 299{
 300	struct rb_node *n;
 301	struct callchain_node *child;
 302
 303	node->rb_root = RB_ROOT;
 304	n = rb_first(&node->rb_root_in);
 305
 306	while (n) {
 307		child = rb_entry(n, struct callchain_node, rb_node_in);
 308		n = rb_next(n);
 309
 310		__sort_chain_graph_abs(child, min_hit);
 311		if (callchain_cumul_hits(child) >= min_hit)
 312			rb_insert_callchain(&node->rb_root, child,
 313					    CHAIN_GRAPH_ABS);
 314	}
 315}
 316
 317static void
 318sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root,
 319		     u64 min_hit, struct callchain_param *param __maybe_unused)
 320{
 321	__sort_chain_graph_abs(&chain_root->node, min_hit);
 322	rb_root->rb_node = chain_root->node.rb_root.rb_node;
 323}
 324
 325static void __sort_chain_graph_rel(struct callchain_node *node,
 326				   double min_percent)
 327{
 328	struct rb_node *n;
 329	struct callchain_node *child;
 330	u64 min_hit;
 331
 332	node->rb_root = RB_ROOT;
 333	min_hit = ceil(node->children_hit * min_percent);
 334
 335	n = rb_first(&node->rb_root_in);
 336	while (n) {
 337		child = rb_entry(n, struct callchain_node, rb_node_in);
 338		n = rb_next(n);
 339
 340		__sort_chain_graph_rel(child, min_percent);
 341		if (callchain_cumul_hits(child) >= min_hit)
 342			rb_insert_callchain(&node->rb_root, child,
 343					    CHAIN_GRAPH_REL);
 344	}
 345}
 346
 347static void
 348sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root,
 349		     u64 min_hit __maybe_unused, struct callchain_param *param)
 350{
 351	__sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0);
 352	rb_root->rb_node = chain_root->node.rb_root.rb_node;
 353}
 354
 355int callchain_register_param(struct callchain_param *param)
 356{
 357	switch (param->mode) {
 358	case CHAIN_GRAPH_ABS:
 359		param->sort = sort_chain_graph_abs;
 360		break;
 361	case CHAIN_GRAPH_REL:
 362		param->sort = sort_chain_graph_rel;
 363		break;
 364	case CHAIN_FLAT:
 365	case CHAIN_FOLDED:
 366		param->sort = sort_chain_flat;
 367		break;
 368	case CHAIN_NONE:
 369	default:
 370		return -1;
 371	}
 372	return 0;
 373}
 374
 375/*
 376 * Create a child for a parent. If inherit_children, then the new child
 377 * will become the new parent of it's parent children
 378 */
 379static struct callchain_node *
 380create_child(struct callchain_node *parent, bool inherit_children)
 381{
 382	struct callchain_node *new;
 383
 384	new = zalloc(sizeof(*new));
 385	if (!new) {
 386		perror("not enough memory to create child for code path tree");
 387		return NULL;
 388	}
 389	new->parent = parent;
 390	INIT_LIST_HEAD(&new->val);
 391	INIT_LIST_HEAD(&new->parent_val);
 392
 393	if (inherit_children) {
 394		struct rb_node *n;
 395		struct callchain_node *child;
 396
 397		new->rb_root_in = parent->rb_root_in;
 398		parent->rb_root_in = RB_ROOT;
 399
 400		n = rb_first(&new->rb_root_in);
 401		while (n) {
 402			child = rb_entry(n, struct callchain_node, rb_node_in);
 403			child->parent = new;
 404			n = rb_next(n);
 405		}
 406
 407		/* make it the first child */
 408		rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node);
 409		rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
 410	}
 411
 412	return new;
 413}
 414
 415
 416/*
 417 * Fill the node with callchain values
 418 */
 419static int
 420fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
 421{
 422	struct callchain_cursor_node *cursor_node;
 423
 424	node->val_nr = cursor->nr - cursor->pos;
 425	if (!node->val_nr)
 426		pr_warning("Warning: empty node in callchain tree\n");
 427
 428	cursor_node = callchain_cursor_current(cursor);
 429
 430	while (cursor_node) {
 431		struct callchain_list *call;
 432
 433		call = zalloc(sizeof(*call));
 434		if (!call) {
 435			perror("not enough memory for the code path tree");
 436			return -1;
 437		}
 438		call->ip = cursor_node->ip;
 439		call->ms.sym = cursor_node->sym;
 440		call->ms.map = cursor_node->map;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 441		list_add_tail(&call->list, &node->val);
 442
 443		callchain_cursor_advance(cursor);
 444		cursor_node = callchain_cursor_current(cursor);
 445	}
 446	return 0;
 447}
 448
 449static struct callchain_node *
 450add_child(struct callchain_node *parent,
 451	  struct callchain_cursor *cursor,
 452	  u64 period)
 453{
 454	struct callchain_node *new;
 455
 456	new = create_child(parent, false);
 457	if (new == NULL)
 458		return NULL;
 459
 460	if (fill_node(new, cursor) < 0) {
 461		struct callchain_list *call, *tmp;
 462
 463		list_for_each_entry_safe(call, tmp, &new->val, list) {
 464			list_del(&call->list);
 
 465			free(call);
 466		}
 467		free(new);
 468		return NULL;
 469	}
 470
 471	new->children_hit = 0;
 472	new->hit = period;
 473	new->children_count = 0;
 474	new->count = 1;
 475	return new;
 476}
 477
 478enum match_result {
 479	MATCH_ERROR  = -1,
 480	MATCH_EQ,
 481	MATCH_LT,
 482	MATCH_GT,
 483};
 484
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 485static enum match_result match_chain(struct callchain_cursor_node *node,
 486				     struct callchain_list *cnode)
 487{
 488	struct symbol *sym = node->sym;
 489	u64 left, right;
 490
 491	if (cnode->ms.sym && sym &&
 492	    callchain_param.key == CCKEY_FUNCTION) {
 493		left = cnode->ms.sym->start;
 494		right = sym->start;
 495	} else {
 496		left = cnode->ip;
 497		right = node->ip;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 498	}
 499
 500	if (left == right)
 501		return MATCH_EQ;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 502
 503	return left > right ? MATCH_GT : MATCH_LT;
 504}
 505
 506/*
 507 * Split the parent in two parts (a new child is created) and
 508 * give a part of its callchain to the created child.
 509 * Then create another child to host the given callchain of new branch
 510 */
 511static int
 512split_add_child(struct callchain_node *parent,
 513		struct callchain_cursor *cursor,
 514		struct callchain_list *to_split,
 515		u64 idx_parents, u64 idx_local, u64 period)
 516{
 517	struct callchain_node *new;
 518	struct list_head *old_tail;
 519	unsigned int idx_total = idx_parents + idx_local;
 520
 521	/* split */
 522	new = create_child(parent, true);
 523	if (new == NULL)
 524		return -1;
 525
 526	/* split the callchain and move a part to the new child */
 527	old_tail = parent->val.prev;
 528	list_del_range(&to_split->list, old_tail);
 529	new->val.next = &to_split->list;
 530	new->val.prev = old_tail;
 531	to_split->list.prev = &new->val;
 532	old_tail->next = &new->val;
 533
 534	/* split the hits */
 535	new->hit = parent->hit;
 536	new->children_hit = parent->children_hit;
 537	parent->children_hit = callchain_cumul_hits(new);
 538	new->val_nr = parent->val_nr - idx_local;
 539	parent->val_nr = idx_local;
 540	new->count = parent->count;
 541	new->children_count = parent->children_count;
 542	parent->children_count = callchain_cumul_counts(new);
 543
 544	/* create a new child for the new branch if any */
 545	if (idx_total < cursor->nr) {
 546		struct callchain_node *first;
 547		struct callchain_list *cnode;
 548		struct callchain_cursor_node *node;
 549		struct rb_node *p, **pp;
 550
 551		parent->hit = 0;
 552		parent->children_hit += period;
 553		parent->count = 0;
 554		parent->children_count += 1;
 555
 556		node = callchain_cursor_current(cursor);
 557		new = add_child(parent, cursor, period);
 558		if (new == NULL)
 559			return -1;
 560
 561		/*
 562		 * This is second child since we moved parent's children
 563		 * to new (first) child above.
 564		 */
 565		p = parent->rb_root_in.rb_node;
 566		first = rb_entry(p, struct callchain_node, rb_node_in);
 567		cnode = list_first_entry(&first->val, struct callchain_list,
 568					 list);
 569
 570		if (match_chain(node, cnode) == MATCH_LT)
 571			pp = &p->rb_left;
 572		else
 573			pp = &p->rb_right;
 574
 575		rb_link_node(&new->rb_node_in, p, pp);
 576		rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
 577	} else {
 578		parent->hit = period;
 579		parent->count = 1;
 580	}
 581	return 0;
 582}
 583
 584static enum match_result
 585append_chain(struct callchain_node *root,
 586	     struct callchain_cursor *cursor,
 587	     u64 period);
 588
 589static int
 590append_chain_children(struct callchain_node *root,
 591		      struct callchain_cursor *cursor,
 592		      u64 period)
 593{
 594	struct callchain_node *rnode;
 595	struct callchain_cursor_node *node;
 596	struct rb_node **p = &root->rb_root_in.rb_node;
 597	struct rb_node *parent = NULL;
 598
 599	node = callchain_cursor_current(cursor);
 600	if (!node)
 601		return -1;
 602
 603	/* lookup in childrens */
 604	while (*p) {
 605		enum match_result ret;
 606
 607		parent = *p;
 608		rnode = rb_entry(parent, struct callchain_node, rb_node_in);
 609
 610		/* If at least first entry matches, rely to children */
 611		ret = append_chain(rnode, cursor, period);
 612		if (ret == MATCH_EQ)
 613			goto inc_children_hit;
 614		if (ret == MATCH_ERROR)
 615			return -1;
 616
 617		if (ret == MATCH_LT)
 618			p = &parent->rb_left;
 619		else
 620			p = &parent->rb_right;
 621	}
 622	/* nothing in children, add to the current node */
 623	rnode = add_child(root, cursor, period);
 624	if (rnode == NULL)
 625		return -1;
 626
 627	rb_link_node(&rnode->rb_node_in, parent, p);
 628	rb_insert_color(&rnode->rb_node_in, &root->rb_root_in);
 629
 630inc_children_hit:
 631	root->children_hit += period;
 632	root->children_count++;
 633	return 0;
 634}
 635
 636static enum match_result
 637append_chain(struct callchain_node *root,
 638	     struct callchain_cursor *cursor,
 639	     u64 period)
 640{
 641	struct callchain_list *cnode;
 642	u64 start = cursor->pos;
 643	bool found = false;
 644	u64 matches;
 645	enum match_result cmp = MATCH_ERROR;
 646
 647	/*
 648	 * Lookup in the current node
 649	 * If we have a symbol, then compare the start to match
 650	 * anywhere inside a function, unless function
 651	 * mode is disabled.
 652	 */
 653	list_for_each_entry(cnode, &root->val, list) {
 654		struct callchain_cursor_node *node;
 655
 656		node = callchain_cursor_current(cursor);
 657		if (!node)
 658			break;
 659
 660		cmp = match_chain(node, cnode);
 661		if (cmp != MATCH_EQ)
 662			break;
 663
 664		found = true;
 665
 666		callchain_cursor_advance(cursor);
 667	}
 668
 669	/* matches not, relay no the parent */
 670	if (!found) {
 671		WARN_ONCE(cmp == MATCH_ERROR, "Chain comparison error\n");
 672		return cmp;
 673	}
 674
 675	matches = cursor->pos - start;
 676
 677	/* we match only a part of the node. Split it and add the new chain */
 678	if (matches < root->val_nr) {
 679		if (split_add_child(root, cursor, cnode, start, matches,
 680				    period) < 0)
 681			return MATCH_ERROR;
 682
 683		return MATCH_EQ;
 684	}
 685
 686	/* we match 100% of the path, increment the hit */
 687	if (matches == root->val_nr && cursor->pos == cursor->nr) {
 688		root->hit += period;
 689		root->count++;
 690		return MATCH_EQ;
 691	}
 692
 693	/* We match the node and still have a part remaining */
 694	if (append_chain_children(root, cursor, period) < 0)
 695		return MATCH_ERROR;
 696
 697	return MATCH_EQ;
 698}
 699
 700int callchain_append(struct callchain_root *root,
 701		     struct callchain_cursor *cursor,
 702		     u64 period)
 703{
 704	if (!cursor->nr)
 705		return 0;
 706
 707	callchain_cursor_commit(cursor);
 708
 709	if (append_chain_children(&root->node, cursor, period) < 0)
 710		return -1;
 711
 712	if (cursor->nr > root->max_depth)
 713		root->max_depth = cursor->nr;
 714
 715	return 0;
 716}
 717
 718static int
 719merge_chain_branch(struct callchain_cursor *cursor,
 720		   struct callchain_node *dst, struct callchain_node *src)
 721{
 722	struct callchain_cursor_node **old_last = cursor->last;
 723	struct callchain_node *child;
 724	struct callchain_list *list, *next_list;
 725	struct rb_node *n;
 726	int old_pos = cursor->nr;
 727	int err = 0;
 728
 729	list_for_each_entry_safe(list, next_list, &src->val, list) {
 730		callchain_cursor_append(cursor, list->ip,
 731					list->ms.map, list->ms.sym);
 
 732		list_del(&list->list);
 
 733		free(list);
 734	}
 735
 736	if (src->hit) {
 737		callchain_cursor_commit(cursor);
 738		if (append_chain_children(dst, cursor, src->hit) < 0)
 739			return -1;
 740	}
 741
 742	n = rb_first(&src->rb_root_in);
 743	while (n) {
 744		child = container_of(n, struct callchain_node, rb_node_in);
 745		n = rb_next(n);
 746		rb_erase(&child->rb_node_in, &src->rb_root_in);
 747
 748		err = merge_chain_branch(cursor, dst, child);
 749		if (err)
 750			break;
 751
 752		free(child);
 753	}
 754
 755	cursor->nr = old_pos;
 756	cursor->last = old_last;
 757
 758	return err;
 759}
 760
 761int callchain_merge(struct callchain_cursor *cursor,
 762		    struct callchain_root *dst, struct callchain_root *src)
 763{
 764	return merge_chain_branch(cursor, &dst->node, &src->node);
 765}
 766
 767int callchain_cursor_append(struct callchain_cursor *cursor,
 768			    u64 ip, struct map *map, struct symbol *sym)
 
 
 
 769{
 770	struct callchain_cursor_node *node = *cursor->last;
 771
 772	if (!node) {
 773		node = calloc(1, sizeof(*node));
 774		if (!node)
 775			return -ENOMEM;
 776
 777		*cursor->last = node;
 778	}
 779
 780	node->ip = ip;
 781	node->map = map;
 
 782	node->sym = sym;
 
 
 
 
 
 
 
 
 783
 
 784	cursor->nr++;
 785
 786	cursor->last = &node->next;
 787
 788	return 0;
 789}
 790
 791int sample__resolve_callchain(struct perf_sample *sample, struct symbol **parent,
 
 792			      struct perf_evsel *evsel, struct addr_location *al,
 793			      int max_stack)
 794{
 795	if (sample->callchain == NULL)
 796		return 0;
 797
 798	if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain ||
 799	    sort__has_parent) {
 800		return thread__resolve_callchain(al->thread, evsel, sample,
 801						 parent, al, max_stack);
 802	}
 803	return 0;
 804}
 805
 806int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample)
 807{
 808	if (!symbol_conf.use_callchain || sample->callchain == NULL)
 
 809		return 0;
 810	return callchain_append(he->callchain, &callchain_cursor, sample->period);
 811}
 812
 813int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node,
 814			bool hide_unresolved)
 815{
 816	al->map = node->map;
 817	al->sym = node->sym;
 818	if (node->map)
 819		al->addr = node->map->map_ip(node->map, node->ip);
 820	else
 821		al->addr = node->ip;
 822
 823	if (al->sym == NULL) {
 824		if (hide_unresolved)
 825			return 0;
 826		if (al->map == NULL)
 827			goto out;
 828	}
 829
 830	if (al->map->groups == &al->machine->kmaps) {
 831		if (machine__is_host(al->machine)) {
 832			al->cpumode = PERF_RECORD_MISC_KERNEL;
 833			al->level = 'k';
 834		} else {
 835			al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL;
 836			al->level = 'g';
 837		}
 838	} else {
 839		if (machine__is_host(al->machine)) {
 840			al->cpumode = PERF_RECORD_MISC_USER;
 841			al->level = '.';
 842		} else if (perf_guest) {
 843			al->cpumode = PERF_RECORD_MISC_GUEST_USER;
 844			al->level = 'u';
 845		} else {
 846			al->cpumode = PERF_RECORD_MISC_HYPERVISOR;
 847			al->level = 'H';
 848		}
 849	}
 850
 851out:
 852	return 1;
 853}
 854
 855char *callchain_list__sym_name(struct callchain_list *cl,
 856			       char *bf, size_t bfsize, bool show_dso)
 857{
 
 
 858	int printed;
 859
 860	if (cl->ms.sym) {
 861		if (callchain_param.key == CCKEY_ADDRESS &&
 862		    cl->ms.map && !cl->srcline)
 863			cl->srcline = get_srcline(cl->ms.map->dso,
 864						  map__rip_2objdump(cl->ms.map,
 865								    cl->ip),
 866						  cl->ms.sym, false);
 867		if (cl->srcline)
 868			printed = scnprintf(bf, bfsize, "%s %s",
 869					cl->ms.sym->name, cl->srcline);
 870		else
 871			printed = scnprintf(bf, bfsize, "%s", cl->ms.sym->name);
 
 872	} else
 873		printed = scnprintf(bf, bfsize, "%#" PRIx64, cl->ip);
 874
 875	if (show_dso)
 876		scnprintf(bf + printed, bfsize - printed, " %s",
 877			  cl->ms.map ?
 878			  cl->ms.map->dso->short_name :
 879			  "unknown");
 880
 881	return bf;
 882}
 883
 884char *callchain_node__scnprintf_value(struct callchain_node *node,
 885				      char *bf, size_t bfsize, u64 total)
 886{
 887	double percent = 0.0;
 888	u64 period = callchain_cumul_hits(node);
 889	unsigned count = callchain_cumul_counts(node);
 890
 891	if (callchain_param.mode == CHAIN_FOLDED) {
 892		period = node->hit;
 893		count = node->count;
 894	}
 895
 896	switch (callchain_param.value) {
 897	case CCVAL_PERIOD:
 898		scnprintf(bf, bfsize, "%"PRIu64, period);
 899		break;
 900	case CCVAL_COUNT:
 901		scnprintf(bf, bfsize, "%u", count);
 902		break;
 903	case CCVAL_PERCENT:
 904	default:
 905		if (total)
 906			percent = period * 100.0 / total;
 907		scnprintf(bf, bfsize, "%.2f%%", percent);
 908		break;
 909	}
 910	return bf;
 911}
 912
 913int callchain_node__fprintf_value(struct callchain_node *node,
 914				 FILE *fp, u64 total)
 915{
 916	double percent = 0.0;
 917	u64 period = callchain_cumul_hits(node);
 918	unsigned count = callchain_cumul_counts(node);
 919
 920	if (callchain_param.mode == CHAIN_FOLDED) {
 921		period = node->hit;
 922		count = node->count;
 923	}
 924
 925	switch (callchain_param.value) {
 926	case CCVAL_PERIOD:
 927		return fprintf(fp, "%"PRIu64, period);
 928	case CCVAL_COUNT:
 929		return fprintf(fp, "%u", count);
 930	case CCVAL_PERCENT:
 931	default:
 932		if (total)
 933			percent = period * 100.0 / total;
 934		return percent_color_fprintf(fp, "%.2f%%", percent);
 935	}
 936	return 0;
 937}
 938
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 939static void free_callchain_node(struct callchain_node *node)
 940{
 941	struct callchain_list *list, *tmp;
 942	struct callchain_node *child;
 943	struct rb_node *n;
 944
 945	list_for_each_entry_safe(list, tmp, &node->parent_val, list) {
 946		list_del(&list->list);
 
 947		free(list);
 948	}
 949
 950	list_for_each_entry_safe(list, tmp, &node->val, list) {
 951		list_del(&list->list);
 
 952		free(list);
 953	}
 954
 955	n = rb_first(&node->rb_root_in);
 956	while (n) {
 957		child = container_of(n, struct callchain_node, rb_node_in);
 958		n = rb_next(n);
 959		rb_erase(&child->rb_node_in, &node->rb_root_in);
 960
 961		free_callchain_node(child);
 962		free(child);
 963	}
 964}
 965
 966void free_callchain(struct callchain_root *root)
 967{
 968	if (!symbol_conf.use_callchain)
 969		return;
 970
 971	free_callchain_node(&root->node);
 972}
 973
 974static u64 decay_callchain_node(struct callchain_node *node)
 975{
 976	struct callchain_node *child;
 977	struct rb_node *n;
 978	u64 child_hits = 0;
 979
 980	n = rb_first(&node->rb_root_in);
 981	while (n) {
 982		child = container_of(n, struct callchain_node, rb_node_in);
 983
 984		child_hits += decay_callchain_node(child);
 985		n = rb_next(n);
 986	}
 987
 988	node->hit = (node->hit * 7) / 8;
 989	node->children_hit = child_hits;
 990
 991	return node->hit;
 992}
 993
 994void decay_callchain(struct callchain_root *root)
 995{
 996	if (!symbol_conf.use_callchain)
 997		return;
 998
 999	decay_callchain_node(&root->node);
1000}
1001
1002int callchain_node__make_parent_list(struct callchain_node *node)
1003{
1004	struct callchain_node *parent = node->parent;
1005	struct callchain_list *chain, *new;
1006	LIST_HEAD(head);
1007
1008	while (parent) {
1009		list_for_each_entry_reverse(chain, &parent->val, list) {
1010			new = malloc(sizeof(*new));
1011			if (new == NULL)
1012				goto out;
1013			*new = *chain;
1014			new->has_children = false;
 
1015			list_add_tail(&new->list, &head);
1016		}
1017		parent = parent->parent;
1018	}
1019
1020	list_for_each_entry_safe_reverse(chain, new, &head, list)
1021		list_move_tail(&chain->list, &node->parent_val);
1022
1023	if (!list_empty(&node->parent_val)) {
1024		chain = list_first_entry(&node->parent_val, struct callchain_list, list);
1025		chain->has_children = rb_prev(&node->rb_node) || rb_next(&node->rb_node);
1026
1027		chain = list_first_entry(&node->val, struct callchain_list, list);
1028		chain->has_children = false;
1029	}
1030	return 0;
1031
1032out:
1033	list_for_each_entry_safe(chain, new, &head, list) {
1034		list_del(&chain->list);
 
1035		free(chain);
1036	}
1037	return -ENOMEM;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1038}