callchain.c

   1// SPDX-License-Identifier: GPL-2.0
   2/*
   3 * Copyright (C) 2009-2011, Frederic Weisbecker <fweisbec@gmail.com>
   4 *
   5 * Handle the callchains from the stream in an ad-hoc radix tree and then
   6 * sort them in an rbtree.
   7 *
   8 * Using a radix for code path provides a fast retrieval and factorizes
   9 * memory use. Also that lets us use the paths in a hierarchical graph view.
  10 *
  11 */
  12
  13#include <inttypes.h>
  14#include <stdlib.h>
  15#include <stdio.h>
  16#include <stdbool.h>
  17#include <errno.h>
  18#include <math.h>
  19#include <linux/string.h>
  20#include <linux/zalloc.h>
  21
  22#include "asm/bug.h"
  23
  24#include "debug.h"
  25#include "dso.h"
  26#include "event.h"
  27#include "hist.h"
  28#include "sort.h"
  29#include "machine.h"
  30#include "map.h"
  31#include "callchain.h"
  32#include "branch.h"
  33#include "symbol.h"
  34#include "util.h"
  35#include "../perf.h"
  36
  37#define CALLCHAIN_PARAM_DEFAULT			\
  38	.mode		= CHAIN_GRAPH_ABS,	\
  39	.min_percent	= 0.5,			\
  40	.order		= ORDER_CALLEE,		\
  41	.key		= CCKEY_FUNCTION,	\
  42	.value		= CCVAL_PERCENT,	\
  43
  44struct callchain_param callchain_param = {
  45	CALLCHAIN_PARAM_DEFAULT
  46};
  47
  48/*
  49 * Are there any events usind DWARF callchains?
  50 *
  51 * I.e.
  52 *
  53 * -e cycles/call-graph=dwarf/
  54 */
  55bool dwarf_callchain_users;
  56
  57struct callchain_param callchain_param_default = {
  58	CALLCHAIN_PARAM_DEFAULT
  59};
  60
  61/* Used for thread-local struct callchain_cursor. */
  62static pthread_key_t callchain_cursor;
  63
  64int parse_callchain_record_opt(const char *arg, struct callchain_param *param)
  65{
  66	return parse_callchain_record(arg, param);
  67}
  68
  69static int parse_callchain_mode(const char *value)
  70{
  71	if (!strncmp(value, "graph", strlen(value))) {
  72		callchain_param.mode = CHAIN_GRAPH_ABS;
  73		return 0;
  74	}
  75	if (!strncmp(value, "flat", strlen(value))) {
  76		callchain_param.mode = CHAIN_FLAT;
  77		return 0;
  78	}
  79	if (!strncmp(value, "fractal", strlen(value))) {
  80		callchain_param.mode = CHAIN_GRAPH_REL;
  81		return 0;
  82	}
  83	if (!strncmp(value, "folded", strlen(value))) {
  84		callchain_param.mode = CHAIN_FOLDED;
  85		return 0;
  86	}
  87	return -1;
  88}
  89
  90static int parse_callchain_order(const char *value)
  91{
  92	if (!strncmp(value, "caller", strlen(value))) {
  93		callchain_param.order = ORDER_CALLER;
  94		callchain_param.order_set = true;
  95		return 0;
  96	}
  97	if (!strncmp(value, "callee", strlen(value))) {
  98		callchain_param.order = ORDER_CALLEE;
  99		callchain_param.order_set = true;
 100		return 0;
 101	}
 102	return -1;
 103}
 104
 105static int parse_callchain_sort_key(const char *value)
 106{
 107	if (!strncmp(value, "function", strlen(value))) {
 108		callchain_param.key = CCKEY_FUNCTION;
 109		return 0;
 110	}
 111	if (!strncmp(value, "address", strlen(value))) {
 112		callchain_param.key = CCKEY_ADDRESS;
 113		return 0;
 114	}
 115	if (!strncmp(value, "srcline", strlen(value))) {
 116		callchain_param.key = CCKEY_SRCLINE;
 117		return 0;
 118	}
 119	if (!strncmp(value, "branch", strlen(value))) {
 120		callchain_param.branch_callstack = 1;
 121		return 0;
 122	}
 123	return -1;
 124}
 125
 126static int parse_callchain_value(const char *value)
 127{
 128	if (!strncmp(value, "percent", strlen(value))) {
 129		callchain_param.value = CCVAL_PERCENT;
 130		return 0;
 131	}
 132	if (!strncmp(value, "period", strlen(value))) {
 133		callchain_param.value = CCVAL_PERIOD;
 134		return 0;
 135	}
 136	if (!strncmp(value, "count", strlen(value))) {
 137		callchain_param.value = CCVAL_COUNT;
 138		return 0;
 139	}
 140	return -1;
 141}
 142
 143static int get_stack_size(const char *str, unsigned long *_size)
 144{
 145	char *endptr;
 146	unsigned long size;
 147	unsigned long max_size = round_down(USHRT_MAX, sizeof(u64));
 148
 149	size = strtoul(str, &endptr, 0);
 150
 151	do {
 152		if (*endptr)
 153			break;
 154
 155		size = round_up(size, sizeof(u64));
 156		if (!size || size > max_size)
 157			break;
 158
 159		*_size = size;
 160		return 0;
 161
 162	} while (0);
 163
 164	pr_err("callchain: Incorrect stack dump size (max %ld): %s\n",
 165	       max_size, str);
 166	return -1;
 167}
 168
 169static int
 170__parse_callchain_report_opt(const char *arg, bool allow_record_opt)
 171{
 172	char *tok;
 173	char *endptr, *saveptr = NULL;
 174	bool minpcnt_set = false;
 175	bool record_opt_set = false;
 176	bool try_stack_size = false;
 177
 178	callchain_param.enabled = true;
 179	symbol_conf.use_callchain = true;
 180
 181	if (!arg)
 182		return 0;
 183
 184	while ((tok = strtok_r((char *)arg, ",", &saveptr)) != NULL) {
 185		if (!strncmp(tok, "none", strlen(tok))) {
 186			callchain_param.mode = CHAIN_NONE;
 187			callchain_param.enabled = false;
 188			symbol_conf.use_callchain = false;
 189			return 0;
 190		}
 191
 192		if (!parse_callchain_mode(tok) ||
 193		    !parse_callchain_order(tok) ||
 194		    !parse_callchain_sort_key(tok) ||
 195		    !parse_callchain_value(tok)) {
 196			/* parsing ok - move on to the next */
 197			try_stack_size = false;
 198			goto next;
 199		} else if (allow_record_opt && !record_opt_set) {
 200			if (parse_callchain_record(tok, &callchain_param))
 201				goto try_numbers;
 202
 203			/* assume that number followed by 'dwarf' is stack size */
 204			if (callchain_param.record_mode == CALLCHAIN_DWARF)
 205				try_stack_size = true;
 206
 207			record_opt_set = true;
 208			goto next;
 209		}
 210
 211try_numbers:
 212		if (try_stack_size) {
 213			unsigned long size = 0;
 214
 215			if (get_stack_size(tok, &size) < 0)
 216				return -1;
 217			callchain_param.dump_size = size;
 218			try_stack_size = false;
 219		} else if (!minpcnt_set) {
 220			/* try to get the min percent */
 221			callchain_param.min_percent = strtod(tok, &endptr);
 222			if (tok == endptr)
 223				return -1;
 224			minpcnt_set = true;
 225		} else {
 226			/* try print limit at last */
 227			callchain_param.print_limit = strtoul(tok, &endptr, 0);
 228			if (tok == endptr)
 229				return -1;
 230		}
 231next:
 232		arg = NULL;
 233	}
 234
 235	if (callchain_register_param(&callchain_param) < 0) {
 236		pr_err("Can't register callchain params\n");
 237		return -1;
 238	}
 239	return 0;
 240}
 241
 242int parse_callchain_report_opt(const char *arg)
 243{
 244	return __parse_callchain_report_opt(arg, false);
 245}
 246
 247int parse_callchain_top_opt(const char *arg)
 248{
 249	return __parse_callchain_report_opt(arg, true);
 250}
 251
 252int parse_callchain_record(const char *arg, struct callchain_param *param)
 253{
 254	char *tok, *name, *saveptr = NULL;
 255	char *buf;
 256	int ret = -1;
 257
 258	/* We need buffer that we know we can write to. */
 259	buf = malloc(strlen(arg) + 1);
 260	if (!buf)
 261		return -ENOMEM;
 262
 263	strcpy(buf, arg);
 264
 265	tok = strtok_r((char *)buf, ",", &saveptr);
 266	name = tok ? : (char *)buf;
 267
 268	do {
 269		/* Framepointer style */
 270		if (!strncmp(name, "fp", sizeof("fp"))) {
 271			ret = 0;
 272			param->record_mode = CALLCHAIN_FP;
 273
 274			tok = strtok_r(NULL, ",", &saveptr);
 275			if (tok) {
 276				unsigned long size;
 277
 278				if (!strncmp(tok, "defer", sizeof("defer"))) {
 279					param->defer = true;
 280				} else {
 281					size = strtoul(tok, &name, 0);
 282					if (size < (unsigned) sysctl__max_stack())
 283						param->max_stack = size;
 284				}
 285			}
 286			break;
 287
 288		/* Dwarf style */
 289		} else if (!strncmp(name, "dwarf", sizeof("dwarf"))) {
 290			const unsigned long default_stack_dump_size = 8192;
 291
 292			ret = 0;
 293			param->record_mode = CALLCHAIN_DWARF;
 294			param->dump_size = default_stack_dump_size;
 295			dwarf_callchain_users = true;
 296
 297			tok = strtok_r(NULL, ",", &saveptr);
 298			if (tok) {
 299				unsigned long size = 0;
 300
 301				ret = get_stack_size(tok, &size);
 302				param->dump_size = size;
 303			}
 304		} else if (!strncmp(name, "lbr", sizeof("lbr"))) {
 305			if (!strtok_r(NULL, ",", &saveptr)) {
 306				param->record_mode = CALLCHAIN_LBR;
 307				ret = 0;
 308			} else
 309				pr_err("callchain: No more arguments "
 310					"needed for --call-graph lbr\n");
 311			break;
 312		} else {
 313			pr_err("callchain: Unknown --call-graph option "
 314			       "value: %s\n", arg);
 315			break;
 316		}
 317
 318	} while (0);
 319
 320	free(buf);
 321
 322	if (param->defer && param->record_mode != CALLCHAIN_FP) {
 323		pr_err("callchain: deferred callchain only works with FP\n");
 324		return -EINVAL;
 325	}
 326
 327	return ret;
 328}
 329
 330int perf_callchain_config(const char *var, const char *value)
 331{
 332	char *endptr;
 333
 334	if (!strstarts(var, "call-graph."))
 335		return 0;
 336	var += sizeof("call-graph.") - 1;
 337
 338	if (!strcmp(var, "record-mode"))
 339		return parse_callchain_record_opt(value, &callchain_param);
 340	if (!strcmp(var, "dump-size")) {
 341		unsigned long size = 0;
 342		int ret;
 343
 344		ret = get_stack_size(value, &size);
 345		callchain_param.dump_size = size;
 346
 347		return ret;
 348	}
 349	if (!strcmp(var, "print-type")){
 350		int ret;
 351		ret = parse_callchain_mode(value);
 352		if (ret == -1)
 353			pr_err("Invalid callchain mode: %s\n", value);
 354		return ret;
 355	}
 356	if (!strcmp(var, "order")){
 357		int ret;
 358		ret = parse_callchain_order(value);
 359		if (ret == -1)
 360			pr_err("Invalid callchain order: %s\n", value);
 361		return ret;
 362	}
 363	if (!strcmp(var, "sort-key")){
 364		int ret;
 365		ret = parse_callchain_sort_key(value);
 366		if (ret == -1)
 367			pr_err("Invalid callchain sort key: %s\n", value);
 368		return ret;
 369	}
 370	if (!strcmp(var, "threshold")) {
 371		callchain_param.min_percent = strtod(value, &endptr);
 372		if (value == endptr) {
 373			pr_err("Invalid callchain threshold: %s\n", value);
 374			return -1;
 375		}
 376	}
 377	if (!strcmp(var, "print-limit")) {
 378		callchain_param.print_limit = strtod(value, &endptr);
 379		if (value == endptr) {
 380			pr_err("Invalid callchain print limit: %s\n", value);
 381			return -1;
 382		}
 383	}
 384
 385	return 0;
 386}
 387
 388static void
 389rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
 390		    enum chain_mode mode)
 391{
 392	struct rb_node **p = &root->rb_node;
 393	struct rb_node *parent = NULL;
 394	struct callchain_node *rnode;
 395	u64 chain_cumul = callchain_cumul_hits(chain);
 396
 397	while (*p) {
 398		u64 rnode_cumul;
 399
 400		parent = *p;
 401		rnode = rb_entry(parent, struct callchain_node, rb_node);
 402		rnode_cumul = callchain_cumul_hits(rnode);
 403
 404		switch (mode) {
 405		case CHAIN_FLAT:
 406		case CHAIN_FOLDED:
 407			if (rnode->hit < chain->hit)
 408				p = &(*p)->rb_left;
 409			else
 410				p = &(*p)->rb_right;
 411			break;
 412		case CHAIN_GRAPH_ABS: /* Falldown */
 413		case CHAIN_GRAPH_REL:
 414			if (rnode_cumul < chain_cumul)
 415				p = &(*p)->rb_left;
 416			else
 417				p = &(*p)->rb_right;
 418			break;
 419		case CHAIN_NONE:
 420		default:
 421			break;
 422		}
 423	}
 424
 425	rb_link_node(&chain->rb_node, parent, p);
 426	rb_insert_color(&chain->rb_node, root);
 427}
 428
 429static void
 430__sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
 431		  u64 min_hit)
 432{
 433	struct rb_node *n;
 434	struct callchain_node *child;
 435
 436	n = rb_first(&node->rb_root_in);
 437	while (n) {
 438		child = rb_entry(n, struct callchain_node, rb_node_in);
 439		n = rb_next(n);
 440
 441		__sort_chain_flat(rb_root, child, min_hit);
 442	}
 443
 444	if (node->hit && node->hit >= min_hit)
 445		rb_insert_callchain(rb_root, node, CHAIN_FLAT);
 446}
 447
 448/*
 449 * Once we get every callchains from the stream, we can now
 450 * sort them by hit
 451 */
 452static void
 453sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
 454		u64 min_hit, struct callchain_param *param __maybe_unused)
 455{
 456	*rb_root = RB_ROOT;
 457	__sort_chain_flat(rb_root, &root->node, min_hit);
 458}
 459
 460static void __sort_chain_graph_abs(struct callchain_node *node,
 461				   u64 min_hit)
 462{
 463	struct rb_node *n;
 464	struct callchain_node *child;
 465
 466	node->rb_root = RB_ROOT;
 467	n = rb_first(&node->rb_root_in);
 468
 469	while (n) {
 470		child = rb_entry(n, struct callchain_node, rb_node_in);
 471		n = rb_next(n);
 472
 473		__sort_chain_graph_abs(child, min_hit);
 474		if (callchain_cumul_hits(child) >= min_hit)
 475			rb_insert_callchain(&node->rb_root, child,
 476					    CHAIN_GRAPH_ABS);
 477	}
 478}
 479
 480static void
 481sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root,
 482		     u64 min_hit, struct callchain_param *param __maybe_unused)
 483{
 484	__sort_chain_graph_abs(&chain_root->node, min_hit);
 485	rb_root->rb_node = chain_root->node.rb_root.rb_node;
 486}
 487
 488static void __sort_chain_graph_rel(struct callchain_node *node,
 489				   double min_percent)
 490{
 491	struct rb_node *n;
 492	struct callchain_node *child;
 493	u64 min_hit;
 494
 495	node->rb_root = RB_ROOT;
 496	min_hit = ceil(node->children_hit * min_percent);
 497
 498	n = rb_first(&node->rb_root_in);
 499	while (n) {
 500		child = rb_entry(n, struct callchain_node, rb_node_in);
 501		n = rb_next(n);
 502
 503		__sort_chain_graph_rel(child, min_percent);
 504		if (callchain_cumul_hits(child) >= min_hit)
 505			rb_insert_callchain(&node->rb_root, child,
 506					    CHAIN_GRAPH_REL);
 507	}
 508}
 509
 510static void
 511sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root,
 512		     u64 min_hit __maybe_unused, struct callchain_param *param)
 513{
 514	__sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0);
 515	rb_root->rb_node = chain_root->node.rb_root.rb_node;
 516}
 517
 518int callchain_register_param(struct callchain_param *param)
 519{
 520	switch (param->mode) {
 521	case CHAIN_GRAPH_ABS:
 522		param->sort = sort_chain_graph_abs;
 523		break;
 524	case CHAIN_GRAPH_REL:
 525		param->sort = sort_chain_graph_rel;
 526		break;
 527	case CHAIN_FLAT:
 528	case CHAIN_FOLDED:
 529		param->sort = sort_chain_flat;
 530		break;
 531	case CHAIN_NONE:
 532	default:
 533		return -1;
 534	}
 535	return 0;
 536}
 537
 538/*
 539 * Create a child for a parent. If inherit_children, then the new child
 540 * will become the new parent of it's parent children
 541 */
 542static struct callchain_node *
 543create_child(struct callchain_node *parent, bool inherit_children)
 544{
 545	struct callchain_node *new;
 546
 547	new = zalloc(sizeof(*new));
 548	if (!new) {
 549		perror("not enough memory to create child for code path tree");
 550		return NULL;
 551	}
 552	new->parent = parent;
 553	INIT_LIST_HEAD(&new->val);
 554	INIT_LIST_HEAD(&new->parent_val);
 555
 556	if (inherit_children) {
 557		struct rb_node *n;
 558		struct callchain_node *child;
 559
 560		new->rb_root_in = parent->rb_root_in;
 561		parent->rb_root_in = RB_ROOT;
 562
 563		n = rb_first(&new->rb_root_in);
 564		while (n) {
 565			child = rb_entry(n, struct callchain_node, rb_node_in);
 566			child->parent = new;
 567			n = rb_next(n);
 568		}
 569
 570		/* make it the first child */
 571		rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node);
 572		rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
 573	}
 574
 575	return new;
 576}
 577
 578
 579/*
 580 * Fill the node with callchain values
 581 */
 582static int
 583fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
 584{
 585	struct callchain_cursor_node *cursor_node;
 586
 587	node->val_nr = cursor->nr - cursor->pos;
 588	if (!node->val_nr)
 589		pr_warning("Warning: empty node in callchain tree\n");
 590
 591	cursor_node = callchain_cursor_current(cursor);
 592
 593	while (cursor_node) {
 594		struct callchain_list *call;
 595
 596		call = zalloc(sizeof(*call));
 597		if (!call) {
 598			perror("not enough memory for the code path tree");
 599			return -ENOMEM;
 600		}
 601		call->ip = cursor_node->ip;
 602		map_symbol__copy(&call->ms, &cursor_node->ms);
 603		call->srcline = cursor_node->srcline;
 604
 605		if (cursor_node->branch) {
 606			call->branch_count = 1;
 607
 608			if (cursor_node->branch_from) {
 609				/*
 610				 * branch_from is set with value somewhere else
 611				 * to imply it's "to" of a branch.
 612				 */
 613				if (!call->brtype_stat) {
 614					call->brtype_stat = zalloc(sizeof(*call->brtype_stat));
 615					if (!call->brtype_stat) {
 616						perror("not enough memory for the code path branch statistics");
 617						zfree(&call->brtype_stat);
 618						return -ENOMEM;
 619					}
 620				}
 621				call->brtype_stat->branch_to = true;
 622
 623				if (cursor_node->branch_flags.predicted)
 624					call->predicted_count = 1;
 625
 626				if (cursor_node->branch_flags.abort)
 627					call->abort_count = 1;
 628
 629				branch_type_count(call->brtype_stat,
 630						  &cursor_node->branch_flags,
 631						  cursor_node->branch_from,
 632						  cursor_node->ip);
 633			} else {
 634				/*
 635				 * It's "from" of a branch
 636				 */
 637				if (call->brtype_stat && call->brtype_stat->branch_to)
 638					call->brtype_stat->branch_to = false;
 639				call->cycles_count =
 640					cursor_node->branch_flags.cycles;
 641				call->iter_count = cursor_node->nr_loop_iter;
 642				call->iter_cycles = cursor_node->iter_cycles;
 643			}
 644		}
 645
 646		list_add_tail(&call->list, &node->val);
 647
 648		callchain_cursor_advance(cursor);
 649		cursor_node = callchain_cursor_current(cursor);
 650	}
 651	return 0;
 652}
 653
 654static struct callchain_node *
 655add_child(struct callchain_node *parent,
 656	  struct callchain_cursor *cursor,
 657	  u64 period)
 658{
 659	struct callchain_node *new;
 660
 661	new = create_child(parent, false);
 662	if (new == NULL)
 663		return NULL;
 664
 665	if (fill_node(new, cursor) < 0) {
 666		struct callchain_list *call, *tmp;
 667
 668		list_for_each_entry_safe(call, tmp, &new->val, list) {
 669			list_del_init(&call->list);
 670			map_symbol__exit(&call->ms);
 671			zfree(&call->brtype_stat);
 672			free(call);
 673		}
 674		free(new);
 675		return NULL;
 676	}
 677
 678	new->children_hit = 0;
 679	new->hit = period;
 680	new->children_count = 0;
 681	new->count = 1;
 682	return new;
 683}
 684
 685enum match_result {
 686	MATCH_ERROR  = -1,
 687	MATCH_EQ,
 688	MATCH_LT,
 689	MATCH_GT,
 690};
 691
 692static enum match_result match_chain_strings(const char *left,
 693					     const char *right)
 694{
 695	enum match_result ret = MATCH_EQ;
 696	int cmp;
 697
 698	if (left && right)
 699		cmp = strcmp(left, right);
 700	else if (!left && right)
 701		cmp = 1;
 702	else if (left && !right)
 703		cmp = -1;
 704	else
 705		return MATCH_ERROR;
 706
 707	if (cmp != 0)
 708		ret = cmp < 0 ? MATCH_LT : MATCH_GT;
 709
 710	return ret;
 711}
 712
 713/*
 714 * We need to always use relative addresses because we're aggregating
 715 * callchains from multiple threads, i.e. different address spaces, so
 716 * comparing absolute addresses make no sense as a symbol in a DSO may end up
 717 * in a different address when used in a different binary or even the same
 718 * binary but with some sort of address randomization technique, thus we need
 719 * to compare just relative addresses. -acme
 720 */
 721static enum match_result match_chain_dso_addresses(struct map *left_map, u64 left_ip,
 722						   struct map *right_map, u64 right_ip)
 723{
 724	struct dso *left_dso = left_map ? map__dso(left_map) : NULL;
 725	struct dso *right_dso = right_map ? map__dso(right_map) : NULL;
 726
 727	if (left_dso != right_dso)
 728		return left_dso < right_dso ? MATCH_LT : MATCH_GT;
 729
 730	if (left_ip != right_ip)
 731 		return left_ip < right_ip ? MATCH_LT : MATCH_GT;
 732
 733	return MATCH_EQ;
 734}
 735
 736static enum match_result match_chain(struct callchain_cursor_node *node,
 737				     struct callchain_list *cnode)
 738{
 739	enum match_result match = MATCH_ERROR;
 740
 741	switch (callchain_param.key) {
 742	case CCKEY_SRCLINE:
 743		match = match_chain_strings(cnode->srcline, node->srcline);
 744		if (match != MATCH_ERROR)
 745			break;
 746		/* otherwise fall-back to symbol-based comparison below */
 747		fallthrough;
 748	case CCKEY_FUNCTION:
 749		if (node->ms.sym && cnode->ms.sym) {
 750			/*
 751			 * Compare inlined frames based on their symbol name
 752			 * because different inlined frames will have the same
 753			 * symbol start. Otherwise do a faster comparison based
 754			 * on the symbol start address.
 755			 */
 756			if (cnode->ms.sym->inlined || node->ms.sym->inlined) {
 757				match = match_chain_strings(cnode->ms.sym->name,
 758							    node->ms.sym->name);
 759				if (match != MATCH_ERROR)
 760					break;
 761			} else {
 762				match = match_chain_dso_addresses(cnode->ms.map, cnode->ms.sym->start,
 763								  node->ms.map, node->ms.sym->start);
 764				break;
 765			}
 766		}
 767		/* otherwise fall-back to IP-based comparison below */
 768		fallthrough;
 769	case CCKEY_ADDRESS:
 770	default:
 771		match = match_chain_dso_addresses(cnode->ms.map, cnode->ip, node->ms.map, node->ip);
 772		break;
 773	}
 774
 775	if (match == MATCH_EQ && node->branch) {
 776		cnode->branch_count++;
 777
 778		if (node->branch_from) {
 779			/*
 780			 * It's "to" of a branch
 781			 */
 782			if (!cnode->brtype_stat) {
 783				cnode->brtype_stat = zalloc(sizeof(*cnode->brtype_stat));
 784				if (!cnode->brtype_stat) {
 785					perror("not enough memory for the code path branch statistics");
 786					return MATCH_ERROR;
 787				}
 788			}
 789			cnode->brtype_stat->branch_to = true;
 790
 791			if (node->branch_flags.predicted)
 792				cnode->predicted_count++;
 793
 794			if (node->branch_flags.abort)
 795				cnode->abort_count++;
 796
 797			branch_type_count(cnode->brtype_stat,
 798					  &node->branch_flags,
 799					  node->branch_from,
 800					  node->ip);
 801		} else {
 802			/*
 803			 * It's "from" of a branch
 804			 */
 805			if (cnode->brtype_stat && cnode->brtype_stat->branch_to)
 806				cnode->brtype_stat->branch_to = false;
 807			cnode->cycles_count += node->branch_flags.cycles;
 808			cnode->iter_count += node->nr_loop_iter;
 809			cnode->iter_cycles += node->iter_cycles;
 810			cnode->from_count++;
 811		}
 812	}
 813
 814	return match;
 815}
 816
 817/*
 818 * Split the parent in two parts (a new child is created) and
 819 * give a part of its callchain to the created child.
 820 * Then create another child to host the given callchain of new branch
 821 */
 822static int
 823split_add_child(struct callchain_node *parent,
 824		struct callchain_cursor *cursor,
 825		struct callchain_list *to_split,
 826		u64 idx_parents, u64 idx_local, u64 period)
 827{
 828	struct callchain_node *new;
 829	struct list_head *old_tail;
 830	unsigned int idx_total = idx_parents + idx_local;
 831
 832	/* split */
 833	new = create_child(parent, true);
 834	if (new == NULL)
 835		return -1;
 836
 837	/* split the callchain and move a part to the new child */
 838	old_tail = parent->val.prev;
 839	list_del_range(&to_split->list, old_tail);
 840	new->val.next = &to_split->list;
 841	new->val.prev = old_tail;
 842	to_split->list.prev = &new->val;
 843	old_tail->next = &new->val;
 844
 845	/* split the hits */
 846	new->hit = parent->hit;
 847	new->children_hit = parent->children_hit;
 848	parent->children_hit = callchain_cumul_hits(new);
 849	new->val_nr = parent->val_nr - idx_local;
 850	parent->val_nr = idx_local;
 851	new->count = parent->count;
 852	new->children_count = parent->children_count;
 853	parent->children_count = callchain_cumul_counts(new);
 854
 855	/* create a new child for the new branch if any */
 856	if (idx_total < cursor->nr) {
 857		struct callchain_node *first;
 858		struct callchain_list *cnode;
 859		struct callchain_cursor_node *node;
 860		struct rb_node *p, **pp;
 861
 862		parent->hit = 0;
 863		parent->children_hit += period;
 864		parent->count = 0;
 865		parent->children_count += 1;
 866
 867		node = callchain_cursor_current(cursor);
 868		new = add_child(parent, cursor, period);
 869		if (new == NULL)
 870			return -1;
 871
 872		/*
 873		 * This is second child since we moved parent's children
 874		 * to new (first) child above.
 875		 */
 876		p = parent->rb_root_in.rb_node;
 877		first = rb_entry(p, struct callchain_node, rb_node_in);
 878		cnode = list_first_entry(&first->val, struct callchain_list,
 879					 list);
 880
 881		if (match_chain(node, cnode) == MATCH_LT)
 882			pp = &p->rb_left;
 883		else
 884			pp = &p->rb_right;
 885
 886		rb_link_node(&new->rb_node_in, p, pp);
 887		rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
 888	} else {
 889		parent->hit = period;
 890		parent->count = 1;
 891	}
 892	return 0;
 893}
 894
 895static enum match_result
 896append_chain(struct callchain_node *root,
 897	     struct callchain_cursor *cursor,
 898	     u64 period);
 899
 900static int
 901append_chain_children(struct callchain_node *root,
 902		      struct callchain_cursor *cursor,
 903		      u64 period)
 904{
 905	struct callchain_node *rnode;
 906	struct callchain_cursor_node *node;
 907	struct rb_node **p = &root->rb_root_in.rb_node;
 908	struct rb_node *parent = NULL;
 909
 910	node = callchain_cursor_current(cursor);
 911	if (!node)
 912		return -1;
 913
 914	/* lookup in children */
 915	while (*p) {
 916		enum match_result ret;
 917
 918		parent = *p;
 919		rnode = rb_entry(parent, struct callchain_node, rb_node_in);
 920
 921		/* If at least first entry matches, rely to children */
 922		ret = append_chain(rnode, cursor, period);
 923		if (ret == MATCH_EQ)
 924			goto inc_children_hit;
 925		if (ret == MATCH_ERROR)
 926			return -1;
 927
 928		if (ret == MATCH_LT)
 929			p = &parent->rb_left;
 930		else
 931			p = &parent->rb_right;
 932	}
 933	/* nothing in children, add to the current node */
 934	rnode = add_child(root, cursor, period);
 935	if (rnode == NULL)
 936		return -1;
 937
 938	rb_link_node(&rnode->rb_node_in, parent, p);
 939	rb_insert_color(&rnode->rb_node_in, &root->rb_root_in);
 940
 941inc_children_hit:
 942	root->children_hit += period;
 943	root->children_count++;
 944	return 0;
 945}
 946
 947static enum match_result
 948append_chain(struct callchain_node *root,
 949	     struct callchain_cursor *cursor,
 950	     u64 period)
 951{
 952	struct callchain_list *cnode;
 953	u64 start = cursor->pos;
 954	bool found = false;
 955	u64 matches;
 956	enum match_result cmp = MATCH_ERROR;
 957
 958	/*
 959	 * Lookup in the current node
 960	 * If we have a symbol, then compare the start to match
 961	 * anywhere inside a function, unless function
 962	 * mode is disabled.
 963	 */
 964	list_for_each_entry(cnode, &root->val, list) {
 965		struct callchain_cursor_node *node;
 966
 967		node = callchain_cursor_current(cursor);
 968		if (!node)
 969			break;
 970
 971		cmp = match_chain(node, cnode);
 972		if (cmp != MATCH_EQ)
 973			break;
 974
 975		found = true;
 976
 977		callchain_cursor_advance(cursor);
 978	}
 979
 980	/* matches not, relay no the parent */
 981	if (!found) {
 982		WARN_ONCE(cmp == MATCH_ERROR, "Chain comparison error\n");
 983		return cmp;
 984	}
 985
 986	matches = cursor->pos - start;
 987
 988	/* we match only a part of the node. Split it and add the new chain */
 989	if (matches < root->val_nr) {
 990		if (split_add_child(root, cursor, cnode, start, matches,
 991				    period) < 0)
 992			return MATCH_ERROR;
 993
 994		return MATCH_EQ;
 995	}
 996
 997	/* we match 100% of the path, increment the hit */
 998	if (matches == root->val_nr && cursor->pos == cursor->nr) {
 999		root->hit += period;
1000		root->count++;
1001		return MATCH_EQ;
1002	}
1003
1004	/* We match the node and still have a part remaining */
1005	if (append_chain_children(root, cursor, period) < 0)
1006		return MATCH_ERROR;
1007
1008	return MATCH_EQ;
1009}
1010
1011int callchain_append(struct callchain_root *root,
1012		     struct callchain_cursor *cursor,
1013		     u64 period)
1014{
1015	if (cursor == NULL)
1016		return -1;
1017
1018	if (!cursor->nr)
1019		return 0;
1020
1021	callchain_cursor_commit(cursor);
1022
1023	if (append_chain_children(&root->node, cursor, period) < 0)
1024		return -1;
1025
1026	if (cursor->nr > root->max_depth)
1027		root->max_depth = cursor->nr;
1028
1029	return 0;
1030}
1031
1032static int
1033merge_chain_branch(struct callchain_cursor *cursor,
1034		   struct callchain_node *dst, struct callchain_node *src)
1035{
1036	struct callchain_cursor_node **old_last = cursor->last;
1037	struct callchain_node *child;
1038	struct callchain_list *list, *next_list;
1039	struct rb_node *n;
1040	int old_pos = cursor->nr;
1041	int err = 0;
1042
1043	list_for_each_entry_safe(list, next_list, &src->val, list) {
1044		struct map_symbol ms = {
1045			.maps = maps__get(list->ms.maps),
1046			.map = map__get(list->ms.map),
1047		};
1048		callchain_cursor_append(cursor, list->ip, &ms, false, NULL, 0, 0, 0, list->srcline);
1049		list_del_init(&list->list);
1050		map_symbol__exit(&ms);
1051		map_symbol__exit(&list->ms);
1052		zfree(&list->brtype_stat);
1053		free(list);
1054	}
1055
1056	if (src->hit) {
1057		callchain_cursor_commit(cursor);
1058		if (append_chain_children(dst, cursor, src->hit) < 0)
1059			return -1;
1060	}
1061
1062	n = rb_first(&src->rb_root_in);
1063	while (n) {
1064		child = container_of(n, struct callchain_node, rb_node_in);
1065		n = rb_next(n);
1066		rb_erase(&child->rb_node_in, &src->rb_root_in);
1067
1068		err = merge_chain_branch(cursor, dst, child);
1069		if (err)
1070			break;
1071
1072		free(child);
1073	}
1074
1075	cursor->nr = old_pos;
1076	cursor->last = old_last;
1077
1078	return err;
1079}
1080
1081int callchain_merge(struct callchain_cursor *cursor,
1082		    struct callchain_root *dst, struct callchain_root *src)
1083{
1084	return merge_chain_branch(cursor, &dst->node, &src->node);
1085}
1086
1087int callchain_cursor_append(struct callchain_cursor *cursor,
1088			    u64 ip, struct map_symbol *ms,
1089			    bool branch, struct branch_flags *flags,
1090			    int nr_loop_iter, u64 iter_cycles, u64 branch_from,
1091			    const char *srcline)
1092{
1093	struct callchain_cursor_node *node = *cursor->last;
1094
1095	if (!node) {
1096		node = calloc(1, sizeof(*node));
1097		if (!node)
1098			return -ENOMEM;
1099
1100		*cursor->last = node;
1101	}
1102
1103	node->ip = ip;
1104	map_symbol__exit(&node->ms);
1105	map_symbol__copy(&node->ms, ms);
1106	node->branch = branch;
1107	node->nr_loop_iter = nr_loop_iter;
1108	node->iter_cycles = iter_cycles;
1109	node->srcline = srcline;
1110
1111	if (flags)
1112		memcpy(&node->branch_flags, flags,
1113			sizeof(struct branch_flags));
1114
1115	node->branch_from = branch_from;
1116	cursor->nr++;
1117
1118	cursor->last = &node->next;
1119
1120	return 0;
1121}
1122
1123int sample__resolve_callchain(struct perf_sample *sample,
1124			      struct callchain_cursor *cursor, struct symbol **parent,
1125			      struct evsel *evsel, struct addr_location *al,
1126			      int max_stack)
1127{
1128	if (sample->callchain == NULL && !symbol_conf.show_branchflag_count)
1129		return 0;
1130
1131	if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain ||
1132	    perf_hpp_list.parent || symbol_conf.show_branchflag_count) {
1133		return thread__resolve_callchain(al->thread, cursor, evsel, sample,
1134						 parent, al, max_stack);
1135	}
1136	return 0;
1137}
1138
1139int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample)
1140{
1141	if ((!symbol_conf.use_callchain || sample->callchain == NULL) &&
1142		!symbol_conf.show_branchflag_count)
1143		return 0;
1144	return callchain_append(he->callchain, get_tls_callchain_cursor(), sample->period);
1145}
1146
1147int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node,
1148			bool hide_unresolved)
1149{
1150	struct machine *machine = node->ms.maps ? maps__machine(node->ms.maps) : NULL;
1151
1152	maps__put(al->maps);
1153	al->maps = maps__get(node->ms.maps);
1154	map__put(al->map);
1155	al->map = map__get(node->ms.map);
1156	al->sym = node->ms.sym;
1157	al->srcline = node->srcline;
1158	al->addr = node->ip;
1159
1160	if (al->sym == NULL) {
1161		if (hide_unresolved)
1162			return 0;
1163		if (al->map == NULL)
1164			goto out;
1165	}
1166	if (maps__equal(al->maps, machine__kernel_maps(machine))) {
1167		if (machine__is_host(machine)) {
1168			al->cpumode = PERF_RECORD_MISC_KERNEL;
1169			al->level = 'k';
1170		} else {
1171			al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL;
1172			al->level = 'g';
1173		}
1174	} else {
1175		if (machine__is_host(machine)) {
1176			al->cpumode = PERF_RECORD_MISC_USER;
1177			al->level = '.';
1178		} else if (perf_guest) {
1179			al->cpumode = PERF_RECORD_MISC_GUEST_USER;
1180			al->level = 'u';
1181		} else {
1182			al->cpumode = PERF_RECORD_MISC_HYPERVISOR;
1183			al->level = 'H';
1184		}
1185	}
1186
1187out:
1188	return 1;
1189}
1190
1191char *callchain_list__sym_name(struct callchain_list *cl,
1192			       char *bf, size_t bfsize, bool show_dso)
1193{
1194	bool show_addr = callchain_param.key == CCKEY_ADDRESS;
1195	bool show_srcline = show_addr || callchain_param.key == CCKEY_SRCLINE;
1196	int printed;
1197
1198	if (cl->ms.sym) {
1199		const char *inlined = cl->ms.sym->inlined ? " (inlined)" : "";
1200
1201		if (show_srcline && cl->srcline)
1202			printed = scnprintf(bf, bfsize, "%s %s%s",
1203					    cl->ms.sym->name, cl->srcline,
1204					    inlined);
1205		else
1206			printed = scnprintf(bf, bfsize, "%s%s",
1207					    cl->ms.sym->name, inlined);
1208	} else
1209		printed = scnprintf(bf, bfsize, "%#" PRIx64, cl->ip);
1210
1211	if (show_dso)
1212		scnprintf(bf + printed, bfsize - printed, " %s",
1213			  cl->ms.map ?
1214			  dso__short_name(map__dso(cl->ms.map)) :
1215			  "unknown");
1216
1217	return bf;
1218}
1219
1220char *callchain_node__scnprintf_value(struct callchain_node *node,
1221				      char *bf, size_t bfsize, u64 total)
1222{
1223	double percent = 0.0;
1224	u64 period = callchain_cumul_hits(node);
1225	unsigned count = callchain_cumul_counts(node);
1226
1227	if (callchain_param.mode == CHAIN_FOLDED) {
1228		period = node->hit;
1229		count = node->count;
1230	}
1231
1232	switch (callchain_param.value) {
1233	case CCVAL_PERIOD:
1234		scnprintf(bf, bfsize, "%"PRIu64, period);
1235		break;
1236	case CCVAL_COUNT:
1237		scnprintf(bf, bfsize, "%u", count);
1238		break;
1239	case CCVAL_PERCENT:
1240	default:
1241		if (total)
1242			percent = period * 100.0 / total;
1243		scnprintf(bf, bfsize, "%.2f%%", percent);
1244		break;
1245	}
1246	return bf;
1247}
1248
1249int callchain_node__fprintf_value(struct callchain_node *node,
1250				 FILE *fp, u64 total)
1251{
1252	double percent = 0.0;
1253	u64 period = callchain_cumul_hits(node);
1254	unsigned count = callchain_cumul_counts(node);
1255
1256	if (callchain_param.mode == CHAIN_FOLDED) {
1257		period = node->hit;
1258		count = node->count;
1259	}
1260
1261	switch (callchain_param.value) {
1262	case CCVAL_PERIOD:
1263		return fprintf(fp, "%"PRIu64, period);
1264	case CCVAL_COUNT:
1265		return fprintf(fp, "%u", count);
1266	case CCVAL_PERCENT:
1267	default:
1268		if (total)
1269			percent = period * 100.0 / total;
1270		return percent_color_fprintf(fp, "%.2f%%", percent);
1271	}
1272	return 0;
1273}
1274
1275static void callchain_counts_value(struct callchain_node *node,
1276				   u64 *branch_count, u64 *predicted_count,
1277				   u64 *abort_count, u64 *cycles_count)
1278{
1279	struct callchain_list *clist;
1280
1281	list_for_each_entry(clist, &node->val, list) {
1282		if (branch_count)
1283			*branch_count += clist->branch_count;
1284
1285		if (predicted_count)
1286			*predicted_count += clist->predicted_count;
1287
1288		if (abort_count)
1289			*abort_count += clist->abort_count;
1290
1291		if (cycles_count)
1292			*cycles_count += clist->cycles_count;
1293	}
1294}
1295
1296static int callchain_node_branch_counts_cumul(struct callchain_node *node,
1297					      u64 *branch_count,
1298					      u64 *predicted_count,
1299					      u64 *abort_count,
1300					      u64 *cycles_count)
1301{
1302	struct callchain_node *child;
1303	struct rb_node *n;
1304
1305	n = rb_first(&node->rb_root_in);
1306	while (n) {
1307		child = rb_entry(n, struct callchain_node, rb_node_in);
1308		n = rb_next(n);
1309
1310		callchain_node_branch_counts_cumul(child, branch_count,
1311						   predicted_count,
1312						   abort_count,
1313						   cycles_count);
1314
1315		callchain_counts_value(child, branch_count,
1316				       predicted_count, abort_count,
1317				       cycles_count);
1318	}
1319
1320	return 0;
1321}
1322
1323int callchain_branch_counts(struct callchain_root *root,
1324			    u64 *branch_count, u64 *predicted_count,
1325			    u64 *abort_count, u64 *cycles_count)
1326{
1327	if (branch_count)
1328		*branch_count = 0;
1329
1330	if (predicted_count)
1331		*predicted_count = 0;
1332
1333	if (abort_count)
1334		*abort_count = 0;
1335
1336	if (cycles_count)
1337		*cycles_count = 0;
1338
1339	return callchain_node_branch_counts_cumul(&root->node,
1340						  branch_count,
1341						  predicted_count,
1342						  abort_count,
1343						  cycles_count);
1344}
1345
1346static int count_pri64_printf(int idx, const char *str, u64 value, char *bf, int bfsize)
1347{
1348	return scnprintf(bf, bfsize, "%s%s:%" PRId64 "", (idx) ? " " : " (", str, value);
1349}
1350
1351static int count_float_printf(int idx, const char *str, float value,
1352			      char *bf, int bfsize, float threshold)
1353{
1354	if (threshold != 0.0 && value < threshold)
1355		return 0;
1356
1357	return scnprintf(bf, bfsize, "%s%s:%.1f%%", (idx) ? " " : " (", str, value);
1358}
1359
1360static int branch_to_str(char *bf, int bfsize,
1361			 u64 branch_count, u64 predicted_count,
1362			 u64 abort_count,
1363			 const struct branch_type_stat *brtype_stat)
1364{
1365	int printed, i = 0;
1366
1367	printed = branch_type_str(brtype_stat, bf, bfsize);
1368	if (printed)
1369		i++;
1370
1371	if (predicted_count < branch_count) {
1372		printed += count_float_printf(i++, "predicted",
1373				predicted_count * 100.0 / branch_count,
1374				bf + printed, bfsize - printed, 0.0);
1375	}
1376
1377	if (abort_count) {
1378		printed += count_float_printf(i++, "abort",
1379				abort_count * 100.0 / branch_count,
1380				bf + printed, bfsize - printed, 0.1);
1381	}
1382
1383	if (i)
1384		printed += scnprintf(bf + printed, bfsize - printed, ")");
1385
1386	return printed;
1387}
1388
1389static int branch_from_str(char *bf, int bfsize,
1390			   u64 branch_count,
1391			   u64 cycles_count, u64 iter_count,
1392			   u64 iter_cycles, u64 from_count)
1393{
1394	int printed = 0, i = 0;
1395	u64 cycles, v = 0;
1396
1397	cycles = cycles_count / branch_count;
1398	if (cycles) {
1399		printed += count_pri64_printf(i++, "cycles",
1400				cycles,
1401				bf + printed, bfsize - printed);
1402	}
1403
1404	if (iter_count && from_count) {
1405		v = iter_count / from_count;
1406		if (v) {
1407			printed += count_pri64_printf(i++, "iter",
1408					v, bf + printed, bfsize - printed);
1409
1410			printed += count_pri64_printf(i++, "avg_cycles",
1411					iter_cycles / iter_count,
1412					bf + printed, bfsize - printed);
1413		}
1414	}
1415
1416	if (i)
1417		printed += scnprintf(bf + printed, bfsize - printed, ")");
1418
1419	return printed;
1420}
1421
1422static int counts_str_build(char *bf, int bfsize,
1423			     u64 branch_count, u64 predicted_count,
1424			     u64 abort_count, u64 cycles_count,
1425			     u64 iter_count, u64 iter_cycles,
1426			     u64 from_count,
1427			     const struct branch_type_stat *brtype_stat)
1428{
1429	int printed;
1430
1431	if (branch_count == 0)
1432		return scnprintf(bf, bfsize, " (calltrace)");
1433
1434	if (brtype_stat->branch_to) {
1435		printed = branch_to_str(bf, bfsize, branch_count,
1436				predicted_count, abort_count, brtype_stat);
1437	} else {
1438		printed = branch_from_str(bf, bfsize, branch_count,
1439				cycles_count, iter_count, iter_cycles,
1440				from_count);
1441	}
1442
1443	if (!printed)
1444		bf[0] = 0;
1445
1446	return printed;
1447}
1448
1449static int callchain_counts_printf(FILE *fp, char *bf, int bfsize,
1450				   u64 branch_count, u64 predicted_count,
1451				   u64 abort_count, u64 cycles_count,
1452				   u64 iter_count, u64 iter_cycles,
1453				   u64 from_count,
1454				   const struct branch_type_stat *brtype_stat)
1455{
1456	char str[256];
1457
1458	counts_str_build(str, sizeof(str), branch_count,
1459			 predicted_count, abort_count, cycles_count,
1460			 iter_count, iter_cycles, from_count, brtype_stat);
1461
1462	if (fp)
1463		return fprintf(fp, "%s", str);
1464
1465	return scnprintf(bf, bfsize, "%s", str);
1466}
1467
1468int callchain_list_counts__printf_value(struct callchain_list *clist,
1469					FILE *fp, char *bf, int bfsize)
1470{
1471	static const struct branch_type_stat empty_brtype_stat = {};
1472	const struct branch_type_stat *brtype_stat;
1473	u64 branch_count, predicted_count;
1474	u64 abort_count, cycles_count;
1475	u64 iter_count, iter_cycles;
1476	u64 from_count;
1477
1478	brtype_stat = clist->brtype_stat ?: &empty_brtype_stat;
1479	branch_count = clist->branch_count;
1480	predicted_count = clist->predicted_count;
1481	abort_count = clist->abort_count;
1482	cycles_count = clist->cycles_count;
1483	iter_count = clist->iter_count;
1484	iter_cycles = clist->iter_cycles;
1485	from_count = clist->from_count;
1486
1487	return callchain_counts_printf(fp, bf, bfsize, branch_count,
1488				       predicted_count, abort_count,
1489				       cycles_count, iter_count, iter_cycles,
1490				       from_count, brtype_stat);
1491}
1492
1493static void free_callchain_node(struct callchain_node *node)
1494{
1495	struct callchain_list *list, *tmp;
1496	struct callchain_node *child;
1497	struct rb_node *n;
1498
1499	list_for_each_entry_safe(list, tmp, &node->parent_val, list) {
1500		list_del_init(&list->list);
1501		map_symbol__exit(&list->ms);
1502		zfree(&list->brtype_stat);
1503		free(list);
1504	}
1505
1506	list_for_each_entry_safe(list, tmp, &node->val, list) {
1507		list_del_init(&list->list);
1508		map_symbol__exit(&list->ms);
1509		zfree(&list->brtype_stat);
1510		free(list);
1511	}
1512
1513	n = rb_first(&node->rb_root_in);
1514	while (n) {
1515		child = container_of(n, struct callchain_node, rb_node_in);
1516		n = rb_next(n);
1517		rb_erase(&child->rb_node_in, &node->rb_root_in);
1518
1519		free_callchain_node(child);
1520		free(child);
1521	}
1522}
1523
1524void free_callchain(struct callchain_root *root)
1525{
1526	if (!symbol_conf.use_callchain)
1527		return;
1528
1529	free_callchain_node(&root->node);
1530}
1531
1532static u64 decay_callchain_node(struct callchain_node *node)
1533{
1534	struct callchain_node *child;
1535	struct rb_node *n;
1536	u64 child_hits = 0;
1537
1538	n = rb_first(&node->rb_root_in);
1539	while (n) {
1540		child = container_of(n, struct callchain_node, rb_node_in);
1541
1542		child_hits += decay_callchain_node(child);
1543		n = rb_next(n);
1544	}
1545
1546	node->hit = (node->hit * 7) / 8;
1547	node->children_hit = child_hits;
1548
1549	return node->hit;
1550}
1551
1552void decay_callchain(struct callchain_root *root)
1553{
1554	if (!symbol_conf.use_callchain)
1555		return;
1556
1557	decay_callchain_node(&root->node);
1558}
1559
1560int callchain_node__make_parent_list(struct callchain_node *node)
1561{
1562	struct callchain_node *parent = node->parent;
1563	struct callchain_list *chain, *new;
1564	LIST_HEAD(head);
1565
1566	while (parent) {
1567		list_for_each_entry_reverse(chain, &parent->val, list) {
1568			new = malloc(sizeof(*new));
1569			if (new == NULL)
1570				goto out;
1571			*new = *chain;
1572			new->has_children = false;
1573			map_symbol__copy(&new->ms, &chain->ms);
1574			list_add_tail(&new->list, &head);
1575		}
1576		parent = parent->parent;
1577	}
1578
1579	list_for_each_entry_safe_reverse(chain, new, &head, list)
1580		list_move_tail(&chain->list, &node->parent_val);
1581
1582	if (!list_empty(&node->parent_val)) {
1583		chain = list_first_entry(&node->parent_val, struct callchain_list, list);
1584		chain->has_children = rb_prev(&node->rb_node) || rb_next(&node->rb_node);
1585
1586		chain = list_first_entry(&node->val, struct callchain_list, list);
1587		chain->has_children = false;
1588	}
1589	return 0;
1590
1591out:
1592	list_for_each_entry_safe(chain, new, &head, list) {
1593		list_del_init(&chain->list);
1594		map_symbol__exit(&chain->ms);
1595		zfree(&chain->brtype_stat);
1596		free(chain);
1597	}
1598	return -ENOMEM;
1599}
1600
1601static void callchain_cursor__delete(void *vcursor)
1602{
1603	struct callchain_cursor *cursor = vcursor;
1604	struct callchain_cursor_node *node, *next;
1605
1606	callchain_cursor_reset(cursor);
1607	for (node = cursor->first; node != NULL; node = next) {
1608		next = node->next;
1609		free(node);
1610	}
1611	free(cursor);
1612}
1613
1614static void init_callchain_cursor_key(void)
1615{
1616	if (pthread_key_create(&callchain_cursor, callchain_cursor__delete)) {
1617		pr_err("callchain cursor creation failed");
1618		abort();
1619	}
1620}
1621
1622struct callchain_cursor *get_tls_callchain_cursor(void)
1623{
1624	static pthread_once_t once_control = PTHREAD_ONCE_INIT;
1625	struct callchain_cursor *cursor;
1626
1627	pthread_once(&once_control, init_callchain_cursor_key);
1628	cursor = pthread_getspecific(callchain_cursor);
1629	if (!cursor) {
1630		cursor = zalloc(sizeof(*cursor));
1631		if (!cursor)
1632			pr_debug3("%s: not enough memory\n", __func__);
1633		pthread_setspecific(callchain_cursor, cursor);
1634	}
1635	return cursor;
1636}
1637
1638int callchain_cursor__copy(struct callchain_cursor *dst,
1639			   struct callchain_cursor *src)
1640{
1641	int rc = 0;
1642
1643	callchain_cursor_reset(dst);
1644	callchain_cursor_commit(src);
1645
1646	while (true) {
1647		struct callchain_cursor_node *node;
1648
1649		node = callchain_cursor_current(src);
1650		if (node == NULL)
1651			break;
1652
1653		rc = callchain_cursor_append(dst, node->ip, &node->ms,
1654					     node->branch, &node->branch_flags,
1655					     node->nr_loop_iter,
1656					     node->iter_cycles,
1657					     node->branch_from, node->srcline);
1658		if (rc)
1659			break;
1660
1661		callchain_cursor_advance(src);
1662	}
1663
1664	return rc;
1665}
1666
1667/*
1668 * Initialize a cursor before adding entries inside, but keep
1669 * the previously allocated entries as a cache.
1670 */
1671void callchain_cursor_reset(struct callchain_cursor *cursor)
1672{
1673	struct callchain_cursor_node *node;
1674
1675	cursor->nr = 0;
1676	cursor->last = &cursor->first;
1677
1678	for (node = cursor->first; node != NULL; node = node->next)
1679		map_symbol__exit(&node->ms);
1680}
1681
1682void callchain_param_setup(u64 sample_type, const char *arch)
1683{
1684	if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain) {
1685		if ((sample_type & PERF_SAMPLE_REGS_USER) &&
1686		    (sample_type & PERF_SAMPLE_STACK_USER)) {
1687			callchain_param.record_mode = CALLCHAIN_DWARF;
1688			dwarf_callchain_users = true;
1689		} else if (sample_type & PERF_SAMPLE_BRANCH_STACK)
1690			callchain_param.record_mode = CALLCHAIN_LBR;
1691		else
1692			callchain_param.record_mode = CALLCHAIN_FP;
1693	}
1694
1695	/*
1696	 * It's necessary to use libunwind to reliably determine the caller of
1697	 * a leaf function on aarch64, as otherwise we cannot know whether to
1698	 * start from the LR or FP.
1699	 *
1700	 * Always starting from the LR can result in duplicate or entirely
1701	 * erroneous entries. Always skipping the LR and starting from the FP
1702	 * can result in missing entries.
1703	 */
1704	if (callchain_param.record_mode == CALLCHAIN_FP && !strcmp(arch, "arm64"))
1705		dwarf_callchain_users = true;
1706}
1707
1708static bool chain_match(struct callchain_list *base_chain,
1709			struct callchain_list *pair_chain)
1710{
1711	enum match_result match;
1712
1713	match = match_chain_strings(base_chain->srcline,
1714				    pair_chain->srcline);
1715	if (match != MATCH_ERROR)
1716		return match == MATCH_EQ;
1717
1718	match = match_chain_dso_addresses(base_chain->ms.map,
1719					  base_chain->ip,
1720					  pair_chain->ms.map,
1721					  pair_chain->ip);
1722
1723	return match == MATCH_EQ;
1724}
1725
1726bool callchain_cnode_matched(struct callchain_node *base_cnode,
1727			     struct callchain_node *pair_cnode)
1728{
1729	struct callchain_list *base_chain, *pair_chain;
1730	bool match = false;
1731
1732	pair_chain = list_first_entry(&pair_cnode->val,
1733				      struct callchain_list,
1734				      list);
1735
1736	list_for_each_entry(base_chain, &base_cnode->val, list) {
1737		if (&pair_chain->list == &pair_cnode->val)
1738			return false;
1739
1740		if (!base_chain->srcline || !pair_chain->srcline) {
1741			pair_chain = list_next_entry(pair_chain, list);
1742			continue;
1743		}
1744
1745		match = chain_match(base_chain, pair_chain);
1746		if (!match)
1747			return false;
1748
1749		pair_chain = list_next_entry(pair_chain, list);
1750	}
1751
1752	/*
1753	 * Say chain1 is ABC, chain2 is ABCD, we consider they are
1754	 * not fully matched.
1755	 */
1756	if (pair_chain && (&pair_chain->list != &pair_cnode->val))
1757		return false;
1758
1759	return match;
1760}
1761
1762static u64 count_callchain_hits(struct hist_entry *he)
1763{
1764	struct rb_root *root = &he->sorted_chain;
1765	struct rb_node *rb_node = rb_first(root);
1766	struct callchain_node *node;
1767	u64 chain_hits = 0;
1768
1769	while (rb_node) {
1770		node = rb_entry(rb_node, struct callchain_node, rb_node);
1771		chain_hits += node->hit;
1772		rb_node = rb_next(rb_node);
1773	}
1774
1775	return chain_hits;
1776}
1777
1778u64 callchain_total_hits(struct hists *hists)
1779{
1780	struct rb_node *next = rb_first_cached(&hists->entries);
1781	u64 chain_hits = 0;
1782
1783	while (next) {
1784		struct hist_entry *he = rb_entry(next, struct hist_entry,
1785						 rb_node);
1786
1787		chain_hits += count_callchain_hits(he);
1788		next = rb_next(&he->rb_node);
1789	}
1790
1791	return chain_hits;
1792}
1793
1794s64 callchain_avg_cycles(struct callchain_node *cnode)
1795{
1796	struct callchain_list *chain;
1797	s64 cycles = 0;
1798
1799	list_for_each_entry(chain, &cnode->val, list) {
1800		if (chain->srcline && chain->branch_count)
1801			cycles += chain->cycles_count / chain->branch_count;
1802	}
1803
1804	return cycles;
1805}
1806
1807int sample__for_each_callchain_node(struct thread *thread, struct evsel *evsel,
1808				    struct perf_sample *sample, int max_stack,
1809				    bool symbols, callchain_iter_fn cb, void *data)
1810{
1811	struct callchain_cursor *cursor = get_tls_callchain_cursor();
1812	int ret;
1813
1814	if (!cursor)
1815		return -ENOMEM;
1816
1817	/* Fill in the callchain. */
1818	ret = __thread__resolve_callchain(thread, cursor, evsel, sample,
1819					  /*parent=*/NULL, /*root_al=*/NULL,
1820					  max_stack, symbols);
1821	if (ret)
1822		return ret;
1823
1824	/* Switch from writing the callchain to reading it. */
1825	callchain_cursor_commit(cursor);
1826
1827	while (1) {
1828		struct callchain_cursor_node *node = callchain_cursor_current(cursor);
1829
1830		if (!node)
1831			break;
1832
1833		ret = cb(node, data);
1834		if (ret)
1835			return ret;
1836
1837		callchain_cursor_advance(cursor);
1838	}
1839	return 0;
1840}
1841
1842/*
1843 * This function merges earlier samples (@sample_orig) waiting for deferred
1844 * user callchains with the matching callchain record (@sample_callchain)
1845 * which is delivered now.  The @sample_orig->callchain should be released
1846 * after use if ->deferred_callchain is set.
1847 */
1848int sample__merge_deferred_callchain(struct perf_sample *sample_orig,
1849				     struct perf_sample *sample_callchain)
1850{
1851	u64 nr_orig = sample_orig->callchain->nr - 1;
1852	u64 nr_deferred = sample_callchain->callchain->nr;
1853	struct ip_callchain *callchain;
1854
1855	if (sample_orig->callchain->nr < 2) {
1856		sample_orig->deferred_callchain = false;
1857		return -EINVAL;
1858	}
1859
1860	callchain = calloc(1 + nr_orig + nr_deferred, sizeof(u64));
1861	if (callchain == NULL) {
1862		sample_orig->deferred_callchain = false;
1863		return -ENOMEM;
1864	}
1865
1866	callchain->nr = nr_orig + nr_deferred;
1867	/* copy original including PERF_CONTEXT_USER_DEFERRED (but the cookie) */
1868	memcpy(callchain->ips, sample_orig->callchain->ips, nr_orig * sizeof(u64));
1869	/* copy deferred user callchains */
1870	memcpy(&callchain->ips[nr_orig], sample_callchain->callchain->ips,
1871	       nr_deferred * sizeof(u64));
1872
1873	sample_orig->callchain = callchain;
1874	return 0;
1875}