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