xref: /openbmc/linux/tools/perf/util/sort.c (revision 9b9c2cd4)
1 #include <sys/mman.h>
2 #include "sort.h"
3 #include "hist.h"
4 #include "comm.h"
5 #include "symbol.h"
6 #include "evsel.h"
7 
8 regex_t		parent_regex;
9 const char	default_parent_pattern[] = "^sys_|^do_page_fault";
10 const char	*parent_pattern = default_parent_pattern;
11 const char	default_sort_order[] = "comm,dso,symbol";
12 const char	default_branch_sort_order[] = "comm,dso_from,symbol_from,symbol_to,cycles";
13 const char	default_mem_sort_order[] = "local_weight,mem,sym,dso,symbol_daddr,dso_daddr,snoop,tlb,locked";
14 const char	default_top_sort_order[] = "dso,symbol";
15 const char	default_diff_sort_order[] = "dso,symbol";
16 const char	*sort_order;
17 const char	*field_order;
18 regex_t		ignore_callees_regex;
19 int		have_ignore_callees = 0;
20 int		sort__need_collapse = 0;
21 int		sort__has_parent = 0;
22 int		sort__has_sym = 0;
23 int		sort__has_dso = 0;
24 int		sort__has_socket = 0;
25 enum sort_mode	sort__mode = SORT_MODE__NORMAL;
26 
27 
28 static int repsep_snprintf(char *bf, size_t size, const char *fmt, ...)
29 {
30 	int n;
31 	va_list ap;
32 
33 	va_start(ap, fmt);
34 	n = vsnprintf(bf, size, fmt, ap);
35 	if (symbol_conf.field_sep && n > 0) {
36 		char *sep = bf;
37 
38 		while (1) {
39 			sep = strchr(sep, *symbol_conf.field_sep);
40 			if (sep == NULL)
41 				break;
42 			*sep = '.';
43 		}
44 	}
45 	va_end(ap);
46 
47 	if (n >= (int)size)
48 		return size - 1;
49 	return n;
50 }
51 
52 static int64_t cmp_null(const void *l, const void *r)
53 {
54 	if (!l && !r)
55 		return 0;
56 	else if (!l)
57 		return -1;
58 	else
59 		return 1;
60 }
61 
62 /* --sort pid */
63 
64 static int64_t
65 sort__thread_cmp(struct hist_entry *left, struct hist_entry *right)
66 {
67 	return right->thread->tid - left->thread->tid;
68 }
69 
70 static int hist_entry__thread_snprintf(struct hist_entry *he, char *bf,
71 				       size_t size, unsigned int width)
72 {
73 	const char *comm = thread__comm_str(he->thread);
74 
75 	width = max(7U, width) - 6;
76 	return repsep_snprintf(bf, size, "%5d:%-*.*s", he->thread->tid,
77 			       width, width, comm ?: "");
78 }
79 
80 struct sort_entry sort_thread = {
81 	.se_header	= "  Pid:Command",
82 	.se_cmp		= sort__thread_cmp,
83 	.se_snprintf	= hist_entry__thread_snprintf,
84 	.se_width_idx	= HISTC_THREAD,
85 };
86 
87 /* --sort comm */
88 
89 static int64_t
90 sort__comm_cmp(struct hist_entry *left, struct hist_entry *right)
91 {
92 	/* Compare the addr that should be unique among comm */
93 	return strcmp(comm__str(right->comm), comm__str(left->comm));
94 }
95 
96 static int64_t
97 sort__comm_collapse(struct hist_entry *left, struct hist_entry *right)
98 {
99 	/* Compare the addr that should be unique among comm */
100 	return strcmp(comm__str(right->comm), comm__str(left->comm));
101 }
102 
103 static int64_t
104 sort__comm_sort(struct hist_entry *left, struct hist_entry *right)
105 {
106 	return strcmp(comm__str(right->comm), comm__str(left->comm));
107 }
108 
109 static int hist_entry__comm_snprintf(struct hist_entry *he, char *bf,
110 				     size_t size, unsigned int width)
111 {
112 	return repsep_snprintf(bf, size, "%-*.*s", width, width, comm__str(he->comm));
113 }
114 
115 struct sort_entry sort_comm = {
116 	.se_header	= "Command",
117 	.se_cmp		= sort__comm_cmp,
118 	.se_collapse	= sort__comm_collapse,
119 	.se_sort	= sort__comm_sort,
120 	.se_snprintf	= hist_entry__comm_snprintf,
121 	.se_width_idx	= HISTC_COMM,
122 };
123 
124 /* --sort dso */
125 
126 static int64_t _sort__dso_cmp(struct map *map_l, struct map *map_r)
127 {
128 	struct dso *dso_l = map_l ? map_l->dso : NULL;
129 	struct dso *dso_r = map_r ? map_r->dso : NULL;
130 	const char *dso_name_l, *dso_name_r;
131 
132 	if (!dso_l || !dso_r)
133 		return cmp_null(dso_r, dso_l);
134 
135 	if (verbose) {
136 		dso_name_l = dso_l->long_name;
137 		dso_name_r = dso_r->long_name;
138 	} else {
139 		dso_name_l = dso_l->short_name;
140 		dso_name_r = dso_r->short_name;
141 	}
142 
143 	return strcmp(dso_name_l, dso_name_r);
144 }
145 
146 static int64_t
147 sort__dso_cmp(struct hist_entry *left, struct hist_entry *right)
148 {
149 	return _sort__dso_cmp(right->ms.map, left->ms.map);
150 }
151 
152 static int _hist_entry__dso_snprintf(struct map *map, char *bf,
153 				     size_t size, unsigned int width)
154 {
155 	if (map && map->dso) {
156 		const char *dso_name = !verbose ? map->dso->short_name :
157 			map->dso->long_name;
158 		return repsep_snprintf(bf, size, "%-*.*s", width, width, dso_name);
159 	}
160 
161 	return repsep_snprintf(bf, size, "%-*.*s", width, width, "[unknown]");
162 }
163 
164 static int hist_entry__dso_snprintf(struct hist_entry *he, char *bf,
165 				    size_t size, unsigned int width)
166 {
167 	return _hist_entry__dso_snprintf(he->ms.map, bf, size, width);
168 }
169 
170 struct sort_entry sort_dso = {
171 	.se_header	= "Shared Object",
172 	.se_cmp		= sort__dso_cmp,
173 	.se_snprintf	= hist_entry__dso_snprintf,
174 	.se_width_idx	= HISTC_DSO,
175 };
176 
177 /* --sort symbol */
178 
179 static int64_t _sort__addr_cmp(u64 left_ip, u64 right_ip)
180 {
181 	return (int64_t)(right_ip - left_ip);
182 }
183 
184 static int64_t _sort__sym_cmp(struct symbol *sym_l, struct symbol *sym_r)
185 {
186 	if (!sym_l || !sym_r)
187 		return cmp_null(sym_l, sym_r);
188 
189 	if (sym_l == sym_r)
190 		return 0;
191 
192 	if (sym_l->start != sym_r->start)
193 		return (int64_t)(sym_r->start - sym_l->start);
194 
195 	return (int64_t)(sym_r->end - sym_l->end);
196 }
197 
198 static int64_t
199 sort__sym_cmp(struct hist_entry *left, struct hist_entry *right)
200 {
201 	int64_t ret;
202 
203 	if (!left->ms.sym && !right->ms.sym)
204 		return _sort__addr_cmp(left->ip, right->ip);
205 
206 	/*
207 	 * comparing symbol address alone is not enough since it's a
208 	 * relative address within a dso.
209 	 */
210 	if (!sort__has_dso) {
211 		ret = sort__dso_cmp(left, right);
212 		if (ret != 0)
213 			return ret;
214 	}
215 
216 	return _sort__sym_cmp(left->ms.sym, right->ms.sym);
217 }
218 
219 static int64_t
220 sort__sym_sort(struct hist_entry *left, struct hist_entry *right)
221 {
222 	if (!left->ms.sym || !right->ms.sym)
223 		return cmp_null(left->ms.sym, right->ms.sym);
224 
225 	return strcmp(right->ms.sym->name, left->ms.sym->name);
226 }
227 
228 static int _hist_entry__sym_snprintf(struct map *map, struct symbol *sym,
229 				     u64 ip, char level, char *bf, size_t size,
230 				     unsigned int width)
231 {
232 	size_t ret = 0;
233 
234 	if (verbose) {
235 		char o = map ? dso__symtab_origin(map->dso) : '!';
236 		ret += repsep_snprintf(bf, size, "%-#*llx %c ",
237 				       BITS_PER_LONG / 4 + 2, ip, o);
238 	}
239 
240 	ret += repsep_snprintf(bf + ret, size - ret, "[%c] ", level);
241 	if (sym && map) {
242 		if (map->type == MAP__VARIABLE) {
243 			ret += repsep_snprintf(bf + ret, size - ret, "%s", sym->name);
244 			ret += repsep_snprintf(bf + ret, size - ret, "+0x%llx",
245 					ip - map->unmap_ip(map, sym->start));
246 			ret += repsep_snprintf(bf + ret, size - ret, "%-*s",
247 				       width - ret, "");
248 		} else {
249 			ret += repsep_snprintf(bf + ret, size - ret, "%-*s",
250 					       width - ret,
251 					       sym->name);
252 		}
253 	} else {
254 		size_t len = BITS_PER_LONG / 4;
255 		ret += repsep_snprintf(bf + ret, size - ret, "%-#.*llx",
256 				       len, ip);
257 		ret += repsep_snprintf(bf + ret, size - ret, "%-*s",
258 				       width - ret, "");
259 	}
260 
261 	if (ret > width)
262 		bf[width] = '\0';
263 
264 	return width;
265 }
266 
267 static int hist_entry__sym_snprintf(struct hist_entry *he, char *bf,
268 				    size_t size, unsigned int width)
269 {
270 	return _hist_entry__sym_snprintf(he->ms.map, he->ms.sym, he->ip,
271 					 he->level, bf, size, width);
272 }
273 
274 struct sort_entry sort_sym = {
275 	.se_header	= "Symbol",
276 	.se_cmp		= sort__sym_cmp,
277 	.se_sort	= sort__sym_sort,
278 	.se_snprintf	= hist_entry__sym_snprintf,
279 	.se_width_idx	= HISTC_SYMBOL,
280 };
281 
282 /* --sort srcline */
283 
284 static int64_t
285 sort__srcline_cmp(struct hist_entry *left, struct hist_entry *right)
286 {
287 	if (!left->srcline) {
288 		if (!left->ms.map)
289 			left->srcline = SRCLINE_UNKNOWN;
290 		else {
291 			struct map *map = left->ms.map;
292 			left->srcline = get_srcline(map->dso,
293 					   map__rip_2objdump(map, left->ip),
294 						    left->ms.sym, true);
295 		}
296 	}
297 	if (!right->srcline) {
298 		if (!right->ms.map)
299 			right->srcline = SRCLINE_UNKNOWN;
300 		else {
301 			struct map *map = right->ms.map;
302 			right->srcline = get_srcline(map->dso,
303 					     map__rip_2objdump(map, right->ip),
304 						     right->ms.sym, true);
305 		}
306 	}
307 	return strcmp(right->srcline, left->srcline);
308 }
309 
310 static int hist_entry__srcline_snprintf(struct hist_entry *he, char *bf,
311 					size_t size, unsigned int width)
312 {
313 	return repsep_snprintf(bf, size, "%-*.*s", width, width, he->srcline);
314 }
315 
316 struct sort_entry sort_srcline = {
317 	.se_header	= "Source:Line",
318 	.se_cmp		= sort__srcline_cmp,
319 	.se_snprintf	= hist_entry__srcline_snprintf,
320 	.se_width_idx	= HISTC_SRCLINE,
321 };
322 
323 /* --sort srcfile */
324 
325 static char no_srcfile[1];
326 
327 static char *get_srcfile(struct hist_entry *e)
328 {
329 	char *sf, *p;
330 	struct map *map = e->ms.map;
331 
332 	sf = __get_srcline(map->dso, map__rip_2objdump(map, e->ip),
333 			 e->ms.sym, false, true);
334 	if (!strcmp(sf, SRCLINE_UNKNOWN))
335 		return no_srcfile;
336 	p = strchr(sf, ':');
337 	if (p && *sf) {
338 		*p = 0;
339 		return sf;
340 	}
341 	free(sf);
342 	return no_srcfile;
343 }
344 
345 static int64_t
346 sort__srcfile_cmp(struct hist_entry *left, struct hist_entry *right)
347 {
348 	if (!left->srcfile) {
349 		if (!left->ms.map)
350 			left->srcfile = no_srcfile;
351 		else
352 			left->srcfile = get_srcfile(left);
353 	}
354 	if (!right->srcfile) {
355 		if (!right->ms.map)
356 			right->srcfile = no_srcfile;
357 		else
358 			right->srcfile = get_srcfile(right);
359 	}
360 	return strcmp(right->srcfile, left->srcfile);
361 }
362 
363 static int hist_entry__srcfile_snprintf(struct hist_entry *he, char *bf,
364 					size_t size, unsigned int width)
365 {
366 	return repsep_snprintf(bf, size, "%-*.*s", width, width, he->srcfile);
367 }
368 
369 struct sort_entry sort_srcfile = {
370 	.se_header	= "Source File",
371 	.se_cmp		= sort__srcfile_cmp,
372 	.se_snprintf	= hist_entry__srcfile_snprintf,
373 	.se_width_idx	= HISTC_SRCFILE,
374 };
375 
376 /* --sort parent */
377 
378 static int64_t
379 sort__parent_cmp(struct hist_entry *left, struct hist_entry *right)
380 {
381 	struct symbol *sym_l = left->parent;
382 	struct symbol *sym_r = right->parent;
383 
384 	if (!sym_l || !sym_r)
385 		return cmp_null(sym_l, sym_r);
386 
387 	return strcmp(sym_r->name, sym_l->name);
388 }
389 
390 static int hist_entry__parent_snprintf(struct hist_entry *he, char *bf,
391 				       size_t size, unsigned int width)
392 {
393 	return repsep_snprintf(bf, size, "%-*.*s", width, width,
394 			      he->parent ? he->parent->name : "[other]");
395 }
396 
397 struct sort_entry sort_parent = {
398 	.se_header	= "Parent symbol",
399 	.se_cmp		= sort__parent_cmp,
400 	.se_snprintf	= hist_entry__parent_snprintf,
401 	.se_width_idx	= HISTC_PARENT,
402 };
403 
404 /* --sort cpu */
405 
406 static int64_t
407 sort__cpu_cmp(struct hist_entry *left, struct hist_entry *right)
408 {
409 	return right->cpu - left->cpu;
410 }
411 
412 static int hist_entry__cpu_snprintf(struct hist_entry *he, char *bf,
413 				    size_t size, unsigned int width)
414 {
415 	return repsep_snprintf(bf, size, "%*.*d", width, width, he->cpu);
416 }
417 
418 struct sort_entry sort_cpu = {
419 	.se_header      = "CPU",
420 	.se_cmp	        = sort__cpu_cmp,
421 	.se_snprintf    = hist_entry__cpu_snprintf,
422 	.se_width_idx	= HISTC_CPU,
423 };
424 
425 /* --sort socket */
426 
427 static int64_t
428 sort__socket_cmp(struct hist_entry *left, struct hist_entry *right)
429 {
430 	return right->socket - left->socket;
431 }
432 
433 static int hist_entry__socket_snprintf(struct hist_entry *he, char *bf,
434 				    size_t size, unsigned int width)
435 {
436 	return repsep_snprintf(bf, size, "%*.*d", width, width-3, he->socket);
437 }
438 
439 struct sort_entry sort_socket = {
440 	.se_header      = "Socket",
441 	.se_cmp	        = sort__socket_cmp,
442 	.se_snprintf    = hist_entry__socket_snprintf,
443 	.se_width_idx	= HISTC_SOCKET,
444 };
445 
446 /* sort keys for branch stacks */
447 
448 static int64_t
449 sort__dso_from_cmp(struct hist_entry *left, struct hist_entry *right)
450 {
451 	if (!left->branch_info || !right->branch_info)
452 		return cmp_null(left->branch_info, right->branch_info);
453 
454 	return _sort__dso_cmp(left->branch_info->from.map,
455 			      right->branch_info->from.map);
456 }
457 
458 static int hist_entry__dso_from_snprintf(struct hist_entry *he, char *bf,
459 				    size_t size, unsigned int width)
460 {
461 	if (he->branch_info)
462 		return _hist_entry__dso_snprintf(he->branch_info->from.map,
463 						 bf, size, width);
464 	else
465 		return repsep_snprintf(bf, size, "%-*.*s", width, width, "N/A");
466 }
467 
468 static int64_t
469 sort__dso_to_cmp(struct hist_entry *left, struct hist_entry *right)
470 {
471 	if (!left->branch_info || !right->branch_info)
472 		return cmp_null(left->branch_info, right->branch_info);
473 
474 	return _sort__dso_cmp(left->branch_info->to.map,
475 			      right->branch_info->to.map);
476 }
477 
478 static int hist_entry__dso_to_snprintf(struct hist_entry *he, char *bf,
479 				       size_t size, unsigned int width)
480 {
481 	if (he->branch_info)
482 		return _hist_entry__dso_snprintf(he->branch_info->to.map,
483 						 bf, size, width);
484 	else
485 		return repsep_snprintf(bf, size, "%-*.*s", width, width, "N/A");
486 }
487 
488 static int64_t
489 sort__sym_from_cmp(struct hist_entry *left, struct hist_entry *right)
490 {
491 	struct addr_map_symbol *from_l = &left->branch_info->from;
492 	struct addr_map_symbol *from_r = &right->branch_info->from;
493 
494 	if (!left->branch_info || !right->branch_info)
495 		return cmp_null(left->branch_info, right->branch_info);
496 
497 	from_l = &left->branch_info->from;
498 	from_r = &right->branch_info->from;
499 
500 	if (!from_l->sym && !from_r->sym)
501 		return _sort__addr_cmp(from_l->addr, from_r->addr);
502 
503 	return _sort__sym_cmp(from_l->sym, from_r->sym);
504 }
505 
506 static int64_t
507 sort__sym_to_cmp(struct hist_entry *left, struct hist_entry *right)
508 {
509 	struct addr_map_symbol *to_l, *to_r;
510 
511 	if (!left->branch_info || !right->branch_info)
512 		return cmp_null(left->branch_info, right->branch_info);
513 
514 	to_l = &left->branch_info->to;
515 	to_r = &right->branch_info->to;
516 
517 	if (!to_l->sym && !to_r->sym)
518 		return _sort__addr_cmp(to_l->addr, to_r->addr);
519 
520 	return _sort__sym_cmp(to_l->sym, to_r->sym);
521 }
522 
523 static int hist_entry__sym_from_snprintf(struct hist_entry *he, char *bf,
524 					 size_t size, unsigned int width)
525 {
526 	if (he->branch_info) {
527 		struct addr_map_symbol *from = &he->branch_info->from;
528 
529 		return _hist_entry__sym_snprintf(from->map, from->sym, from->addr,
530 						 he->level, bf, size, width);
531 	}
532 
533 	return repsep_snprintf(bf, size, "%-*.*s", width, width, "N/A");
534 }
535 
536 static int hist_entry__sym_to_snprintf(struct hist_entry *he, char *bf,
537 				       size_t size, unsigned int width)
538 {
539 	if (he->branch_info) {
540 		struct addr_map_symbol *to = &he->branch_info->to;
541 
542 		return _hist_entry__sym_snprintf(to->map, to->sym, to->addr,
543 						 he->level, bf, size, width);
544 	}
545 
546 	return repsep_snprintf(bf, size, "%-*.*s", width, width, "N/A");
547 }
548 
549 struct sort_entry sort_dso_from = {
550 	.se_header	= "Source Shared Object",
551 	.se_cmp		= sort__dso_from_cmp,
552 	.se_snprintf	= hist_entry__dso_from_snprintf,
553 	.se_width_idx	= HISTC_DSO_FROM,
554 };
555 
556 struct sort_entry sort_dso_to = {
557 	.se_header	= "Target Shared Object",
558 	.se_cmp		= sort__dso_to_cmp,
559 	.se_snprintf	= hist_entry__dso_to_snprintf,
560 	.se_width_idx	= HISTC_DSO_TO,
561 };
562 
563 struct sort_entry sort_sym_from = {
564 	.se_header	= "Source Symbol",
565 	.se_cmp		= sort__sym_from_cmp,
566 	.se_snprintf	= hist_entry__sym_from_snprintf,
567 	.se_width_idx	= HISTC_SYMBOL_FROM,
568 };
569 
570 struct sort_entry sort_sym_to = {
571 	.se_header	= "Target Symbol",
572 	.se_cmp		= sort__sym_to_cmp,
573 	.se_snprintf	= hist_entry__sym_to_snprintf,
574 	.se_width_idx	= HISTC_SYMBOL_TO,
575 };
576 
577 static int64_t
578 sort__mispredict_cmp(struct hist_entry *left, struct hist_entry *right)
579 {
580 	unsigned char mp, p;
581 
582 	if (!left->branch_info || !right->branch_info)
583 		return cmp_null(left->branch_info, right->branch_info);
584 
585 	mp = left->branch_info->flags.mispred != right->branch_info->flags.mispred;
586 	p  = left->branch_info->flags.predicted != right->branch_info->flags.predicted;
587 	return mp || p;
588 }
589 
590 static int hist_entry__mispredict_snprintf(struct hist_entry *he, char *bf,
591 				    size_t size, unsigned int width){
592 	static const char *out = "N/A";
593 
594 	if (he->branch_info) {
595 		if (he->branch_info->flags.predicted)
596 			out = "N";
597 		else if (he->branch_info->flags.mispred)
598 			out = "Y";
599 	}
600 
601 	return repsep_snprintf(bf, size, "%-*.*s", width, width, out);
602 }
603 
604 static int64_t
605 sort__cycles_cmp(struct hist_entry *left, struct hist_entry *right)
606 {
607 	return left->branch_info->flags.cycles -
608 		right->branch_info->flags.cycles;
609 }
610 
611 static int hist_entry__cycles_snprintf(struct hist_entry *he, char *bf,
612 				    size_t size, unsigned int width)
613 {
614 	if (he->branch_info->flags.cycles == 0)
615 		return repsep_snprintf(bf, size, "%-*s", width, "-");
616 	return repsep_snprintf(bf, size, "%-*hd", width,
617 			       he->branch_info->flags.cycles);
618 }
619 
620 struct sort_entry sort_cycles = {
621 	.se_header	= "Basic Block Cycles",
622 	.se_cmp		= sort__cycles_cmp,
623 	.se_snprintf	= hist_entry__cycles_snprintf,
624 	.se_width_idx	= HISTC_CYCLES,
625 };
626 
627 /* --sort daddr_sym */
628 static int64_t
629 sort__daddr_cmp(struct hist_entry *left, struct hist_entry *right)
630 {
631 	uint64_t l = 0, r = 0;
632 
633 	if (left->mem_info)
634 		l = left->mem_info->daddr.addr;
635 	if (right->mem_info)
636 		r = right->mem_info->daddr.addr;
637 
638 	return (int64_t)(r - l);
639 }
640 
641 static int hist_entry__daddr_snprintf(struct hist_entry *he, char *bf,
642 				    size_t size, unsigned int width)
643 {
644 	uint64_t addr = 0;
645 	struct map *map = NULL;
646 	struct symbol *sym = NULL;
647 
648 	if (he->mem_info) {
649 		addr = he->mem_info->daddr.addr;
650 		map = he->mem_info->daddr.map;
651 		sym = he->mem_info->daddr.sym;
652 	}
653 	return _hist_entry__sym_snprintf(map, sym, addr, he->level, bf, size,
654 					 width);
655 }
656 
657 static int64_t
658 sort__iaddr_cmp(struct hist_entry *left, struct hist_entry *right)
659 {
660 	uint64_t l = 0, r = 0;
661 
662 	if (left->mem_info)
663 		l = left->mem_info->iaddr.addr;
664 	if (right->mem_info)
665 		r = right->mem_info->iaddr.addr;
666 
667 	return (int64_t)(r - l);
668 }
669 
670 static int hist_entry__iaddr_snprintf(struct hist_entry *he, char *bf,
671 				    size_t size, unsigned int width)
672 {
673 	uint64_t addr = 0;
674 	struct map *map = NULL;
675 	struct symbol *sym = NULL;
676 
677 	if (he->mem_info) {
678 		addr = he->mem_info->iaddr.addr;
679 		map  = he->mem_info->iaddr.map;
680 		sym  = he->mem_info->iaddr.sym;
681 	}
682 	return _hist_entry__sym_snprintf(map, sym, addr, he->level, bf, size,
683 					 width);
684 }
685 
686 static int64_t
687 sort__dso_daddr_cmp(struct hist_entry *left, struct hist_entry *right)
688 {
689 	struct map *map_l = NULL;
690 	struct map *map_r = NULL;
691 
692 	if (left->mem_info)
693 		map_l = left->mem_info->daddr.map;
694 	if (right->mem_info)
695 		map_r = right->mem_info->daddr.map;
696 
697 	return _sort__dso_cmp(map_l, map_r);
698 }
699 
700 static int hist_entry__dso_daddr_snprintf(struct hist_entry *he, char *bf,
701 				    size_t size, unsigned int width)
702 {
703 	struct map *map = NULL;
704 
705 	if (he->mem_info)
706 		map = he->mem_info->daddr.map;
707 
708 	return _hist_entry__dso_snprintf(map, bf, size, width);
709 }
710 
711 static int64_t
712 sort__locked_cmp(struct hist_entry *left, struct hist_entry *right)
713 {
714 	union perf_mem_data_src data_src_l;
715 	union perf_mem_data_src data_src_r;
716 
717 	if (left->mem_info)
718 		data_src_l = left->mem_info->data_src;
719 	else
720 		data_src_l.mem_lock = PERF_MEM_LOCK_NA;
721 
722 	if (right->mem_info)
723 		data_src_r = right->mem_info->data_src;
724 	else
725 		data_src_r.mem_lock = PERF_MEM_LOCK_NA;
726 
727 	return (int64_t)(data_src_r.mem_lock - data_src_l.mem_lock);
728 }
729 
730 static int hist_entry__locked_snprintf(struct hist_entry *he, char *bf,
731 				    size_t size, unsigned int width)
732 {
733 	const char *out;
734 	u64 mask = PERF_MEM_LOCK_NA;
735 
736 	if (he->mem_info)
737 		mask = he->mem_info->data_src.mem_lock;
738 
739 	if (mask & PERF_MEM_LOCK_NA)
740 		out = "N/A";
741 	else if (mask & PERF_MEM_LOCK_LOCKED)
742 		out = "Yes";
743 	else
744 		out = "No";
745 
746 	return repsep_snprintf(bf, size, "%-*s", width, out);
747 }
748 
749 static int64_t
750 sort__tlb_cmp(struct hist_entry *left, struct hist_entry *right)
751 {
752 	union perf_mem_data_src data_src_l;
753 	union perf_mem_data_src data_src_r;
754 
755 	if (left->mem_info)
756 		data_src_l = left->mem_info->data_src;
757 	else
758 		data_src_l.mem_dtlb = PERF_MEM_TLB_NA;
759 
760 	if (right->mem_info)
761 		data_src_r = right->mem_info->data_src;
762 	else
763 		data_src_r.mem_dtlb = PERF_MEM_TLB_NA;
764 
765 	return (int64_t)(data_src_r.mem_dtlb - data_src_l.mem_dtlb);
766 }
767 
768 static const char * const tlb_access[] = {
769 	"N/A",
770 	"HIT",
771 	"MISS",
772 	"L1",
773 	"L2",
774 	"Walker",
775 	"Fault",
776 };
777 #define NUM_TLB_ACCESS (sizeof(tlb_access)/sizeof(const char *))
778 
779 static int hist_entry__tlb_snprintf(struct hist_entry *he, char *bf,
780 				    size_t size, unsigned int width)
781 {
782 	char out[64];
783 	size_t sz = sizeof(out) - 1; /* -1 for null termination */
784 	size_t l = 0, i;
785 	u64 m = PERF_MEM_TLB_NA;
786 	u64 hit, miss;
787 
788 	out[0] = '\0';
789 
790 	if (he->mem_info)
791 		m = he->mem_info->data_src.mem_dtlb;
792 
793 	hit = m & PERF_MEM_TLB_HIT;
794 	miss = m & PERF_MEM_TLB_MISS;
795 
796 	/* already taken care of */
797 	m &= ~(PERF_MEM_TLB_HIT|PERF_MEM_TLB_MISS);
798 
799 	for (i = 0; m && i < NUM_TLB_ACCESS; i++, m >>= 1) {
800 		if (!(m & 0x1))
801 			continue;
802 		if (l) {
803 			strcat(out, " or ");
804 			l += 4;
805 		}
806 		strncat(out, tlb_access[i], sz - l);
807 		l += strlen(tlb_access[i]);
808 	}
809 	if (*out == '\0')
810 		strcpy(out, "N/A");
811 	if (hit)
812 		strncat(out, " hit", sz - l);
813 	if (miss)
814 		strncat(out, " miss", sz - l);
815 
816 	return repsep_snprintf(bf, size, "%-*s", width, out);
817 }
818 
819 static int64_t
820 sort__lvl_cmp(struct hist_entry *left, struct hist_entry *right)
821 {
822 	union perf_mem_data_src data_src_l;
823 	union perf_mem_data_src data_src_r;
824 
825 	if (left->mem_info)
826 		data_src_l = left->mem_info->data_src;
827 	else
828 		data_src_l.mem_lvl = PERF_MEM_LVL_NA;
829 
830 	if (right->mem_info)
831 		data_src_r = right->mem_info->data_src;
832 	else
833 		data_src_r.mem_lvl = PERF_MEM_LVL_NA;
834 
835 	return (int64_t)(data_src_r.mem_lvl - data_src_l.mem_lvl);
836 }
837 
838 static const char * const mem_lvl[] = {
839 	"N/A",
840 	"HIT",
841 	"MISS",
842 	"L1",
843 	"LFB",
844 	"L2",
845 	"L3",
846 	"Local RAM",
847 	"Remote RAM (1 hop)",
848 	"Remote RAM (2 hops)",
849 	"Remote Cache (1 hop)",
850 	"Remote Cache (2 hops)",
851 	"I/O",
852 	"Uncached",
853 };
854 #define NUM_MEM_LVL (sizeof(mem_lvl)/sizeof(const char *))
855 
856 static int hist_entry__lvl_snprintf(struct hist_entry *he, char *bf,
857 				    size_t size, unsigned int width)
858 {
859 	char out[64];
860 	size_t sz = sizeof(out) - 1; /* -1 for null termination */
861 	size_t i, l = 0;
862 	u64 m =  PERF_MEM_LVL_NA;
863 	u64 hit, miss;
864 
865 	if (he->mem_info)
866 		m  = he->mem_info->data_src.mem_lvl;
867 
868 	out[0] = '\0';
869 
870 	hit = m & PERF_MEM_LVL_HIT;
871 	miss = m & PERF_MEM_LVL_MISS;
872 
873 	/* already taken care of */
874 	m &= ~(PERF_MEM_LVL_HIT|PERF_MEM_LVL_MISS);
875 
876 	for (i = 0; m && i < NUM_MEM_LVL; i++, m >>= 1) {
877 		if (!(m & 0x1))
878 			continue;
879 		if (l) {
880 			strcat(out, " or ");
881 			l += 4;
882 		}
883 		strncat(out, mem_lvl[i], sz - l);
884 		l += strlen(mem_lvl[i]);
885 	}
886 	if (*out == '\0')
887 		strcpy(out, "N/A");
888 	if (hit)
889 		strncat(out, " hit", sz - l);
890 	if (miss)
891 		strncat(out, " miss", sz - l);
892 
893 	return repsep_snprintf(bf, size, "%-*s", width, out);
894 }
895 
896 static int64_t
897 sort__snoop_cmp(struct hist_entry *left, struct hist_entry *right)
898 {
899 	union perf_mem_data_src data_src_l;
900 	union perf_mem_data_src data_src_r;
901 
902 	if (left->mem_info)
903 		data_src_l = left->mem_info->data_src;
904 	else
905 		data_src_l.mem_snoop = PERF_MEM_SNOOP_NA;
906 
907 	if (right->mem_info)
908 		data_src_r = right->mem_info->data_src;
909 	else
910 		data_src_r.mem_snoop = PERF_MEM_SNOOP_NA;
911 
912 	return (int64_t)(data_src_r.mem_snoop - data_src_l.mem_snoop);
913 }
914 
915 static const char * const snoop_access[] = {
916 	"N/A",
917 	"None",
918 	"Miss",
919 	"Hit",
920 	"HitM",
921 };
922 #define NUM_SNOOP_ACCESS (sizeof(snoop_access)/sizeof(const char *))
923 
924 static int hist_entry__snoop_snprintf(struct hist_entry *he, char *bf,
925 				    size_t size, unsigned int width)
926 {
927 	char out[64];
928 	size_t sz = sizeof(out) - 1; /* -1 for null termination */
929 	size_t i, l = 0;
930 	u64 m = PERF_MEM_SNOOP_NA;
931 
932 	out[0] = '\0';
933 
934 	if (he->mem_info)
935 		m = he->mem_info->data_src.mem_snoop;
936 
937 	for (i = 0; m && i < NUM_SNOOP_ACCESS; i++, m >>= 1) {
938 		if (!(m & 0x1))
939 			continue;
940 		if (l) {
941 			strcat(out, " or ");
942 			l += 4;
943 		}
944 		strncat(out, snoop_access[i], sz - l);
945 		l += strlen(snoop_access[i]);
946 	}
947 
948 	if (*out == '\0')
949 		strcpy(out, "N/A");
950 
951 	return repsep_snprintf(bf, size, "%-*s", width, out);
952 }
953 
954 static inline  u64 cl_address(u64 address)
955 {
956 	/* return the cacheline of the address */
957 	return (address & ~(cacheline_size - 1));
958 }
959 
960 static int64_t
961 sort__dcacheline_cmp(struct hist_entry *left, struct hist_entry *right)
962 {
963 	u64 l, r;
964 	struct map *l_map, *r_map;
965 
966 	if (!left->mem_info)  return -1;
967 	if (!right->mem_info) return 1;
968 
969 	/* group event types together */
970 	if (left->cpumode > right->cpumode) return -1;
971 	if (left->cpumode < right->cpumode) return 1;
972 
973 	l_map = left->mem_info->daddr.map;
974 	r_map = right->mem_info->daddr.map;
975 
976 	/* if both are NULL, jump to sort on al_addr instead */
977 	if (!l_map && !r_map)
978 		goto addr;
979 
980 	if (!l_map) return -1;
981 	if (!r_map) return 1;
982 
983 	if (l_map->maj > r_map->maj) return -1;
984 	if (l_map->maj < r_map->maj) return 1;
985 
986 	if (l_map->min > r_map->min) return -1;
987 	if (l_map->min < r_map->min) return 1;
988 
989 	if (l_map->ino > r_map->ino) return -1;
990 	if (l_map->ino < r_map->ino) return 1;
991 
992 	if (l_map->ino_generation > r_map->ino_generation) return -1;
993 	if (l_map->ino_generation < r_map->ino_generation) return 1;
994 
995 	/*
996 	 * Addresses with no major/minor numbers are assumed to be
997 	 * anonymous in userspace.  Sort those on pid then address.
998 	 *
999 	 * The kernel and non-zero major/minor mapped areas are
1000 	 * assumed to be unity mapped.  Sort those on address.
1001 	 */
1002 
1003 	if ((left->cpumode != PERF_RECORD_MISC_KERNEL) &&
1004 	    (!(l_map->flags & MAP_SHARED)) &&
1005 	    !l_map->maj && !l_map->min && !l_map->ino &&
1006 	    !l_map->ino_generation) {
1007 		/* userspace anonymous */
1008 
1009 		if (left->thread->pid_ > right->thread->pid_) return -1;
1010 		if (left->thread->pid_ < right->thread->pid_) return 1;
1011 	}
1012 
1013 addr:
1014 	/* al_addr does all the right addr - start + offset calculations */
1015 	l = cl_address(left->mem_info->daddr.al_addr);
1016 	r = cl_address(right->mem_info->daddr.al_addr);
1017 
1018 	if (l > r) return -1;
1019 	if (l < r) return 1;
1020 
1021 	return 0;
1022 }
1023 
1024 static int hist_entry__dcacheline_snprintf(struct hist_entry *he, char *bf,
1025 					  size_t size, unsigned int width)
1026 {
1027 
1028 	uint64_t addr = 0;
1029 	struct map *map = NULL;
1030 	struct symbol *sym = NULL;
1031 	char level = he->level;
1032 
1033 	if (he->mem_info) {
1034 		addr = cl_address(he->mem_info->daddr.al_addr);
1035 		map = he->mem_info->daddr.map;
1036 		sym = he->mem_info->daddr.sym;
1037 
1038 		/* print [s] for shared data mmaps */
1039 		if ((he->cpumode != PERF_RECORD_MISC_KERNEL) &&
1040 		     map && (map->type == MAP__VARIABLE) &&
1041 		    (map->flags & MAP_SHARED) &&
1042 		    (map->maj || map->min || map->ino ||
1043 		     map->ino_generation))
1044 			level = 's';
1045 		else if (!map)
1046 			level = 'X';
1047 	}
1048 	return _hist_entry__sym_snprintf(map, sym, addr, level, bf, size,
1049 					 width);
1050 }
1051 
1052 struct sort_entry sort_mispredict = {
1053 	.se_header	= "Branch Mispredicted",
1054 	.se_cmp		= sort__mispredict_cmp,
1055 	.se_snprintf	= hist_entry__mispredict_snprintf,
1056 	.se_width_idx	= HISTC_MISPREDICT,
1057 };
1058 
1059 static u64 he_weight(struct hist_entry *he)
1060 {
1061 	return he->stat.nr_events ? he->stat.weight / he->stat.nr_events : 0;
1062 }
1063 
1064 static int64_t
1065 sort__local_weight_cmp(struct hist_entry *left, struct hist_entry *right)
1066 {
1067 	return he_weight(left) - he_weight(right);
1068 }
1069 
1070 static int hist_entry__local_weight_snprintf(struct hist_entry *he, char *bf,
1071 				    size_t size, unsigned int width)
1072 {
1073 	return repsep_snprintf(bf, size, "%-*llu", width, he_weight(he));
1074 }
1075 
1076 struct sort_entry sort_local_weight = {
1077 	.se_header	= "Local Weight",
1078 	.se_cmp		= sort__local_weight_cmp,
1079 	.se_snprintf	= hist_entry__local_weight_snprintf,
1080 	.se_width_idx	= HISTC_LOCAL_WEIGHT,
1081 };
1082 
1083 static int64_t
1084 sort__global_weight_cmp(struct hist_entry *left, struct hist_entry *right)
1085 {
1086 	return left->stat.weight - right->stat.weight;
1087 }
1088 
1089 static int hist_entry__global_weight_snprintf(struct hist_entry *he, char *bf,
1090 					      size_t size, unsigned int width)
1091 {
1092 	return repsep_snprintf(bf, size, "%-*llu", width, he->stat.weight);
1093 }
1094 
1095 struct sort_entry sort_global_weight = {
1096 	.se_header	= "Weight",
1097 	.se_cmp		= sort__global_weight_cmp,
1098 	.se_snprintf	= hist_entry__global_weight_snprintf,
1099 	.se_width_idx	= HISTC_GLOBAL_WEIGHT,
1100 };
1101 
1102 struct sort_entry sort_mem_daddr_sym = {
1103 	.se_header	= "Data Symbol",
1104 	.se_cmp		= sort__daddr_cmp,
1105 	.se_snprintf	= hist_entry__daddr_snprintf,
1106 	.se_width_idx	= HISTC_MEM_DADDR_SYMBOL,
1107 };
1108 
1109 struct sort_entry sort_mem_iaddr_sym = {
1110 	.se_header	= "Code Symbol",
1111 	.se_cmp		= sort__iaddr_cmp,
1112 	.se_snprintf	= hist_entry__iaddr_snprintf,
1113 	.se_width_idx	= HISTC_MEM_IADDR_SYMBOL,
1114 };
1115 
1116 struct sort_entry sort_mem_daddr_dso = {
1117 	.se_header	= "Data Object",
1118 	.se_cmp		= sort__dso_daddr_cmp,
1119 	.se_snprintf	= hist_entry__dso_daddr_snprintf,
1120 	.se_width_idx	= HISTC_MEM_DADDR_SYMBOL,
1121 };
1122 
1123 struct sort_entry sort_mem_locked = {
1124 	.se_header	= "Locked",
1125 	.se_cmp		= sort__locked_cmp,
1126 	.se_snprintf	= hist_entry__locked_snprintf,
1127 	.se_width_idx	= HISTC_MEM_LOCKED,
1128 };
1129 
1130 struct sort_entry sort_mem_tlb = {
1131 	.se_header	= "TLB access",
1132 	.se_cmp		= sort__tlb_cmp,
1133 	.se_snprintf	= hist_entry__tlb_snprintf,
1134 	.se_width_idx	= HISTC_MEM_TLB,
1135 };
1136 
1137 struct sort_entry sort_mem_lvl = {
1138 	.se_header	= "Memory access",
1139 	.se_cmp		= sort__lvl_cmp,
1140 	.se_snprintf	= hist_entry__lvl_snprintf,
1141 	.se_width_idx	= HISTC_MEM_LVL,
1142 };
1143 
1144 struct sort_entry sort_mem_snoop = {
1145 	.se_header	= "Snoop",
1146 	.se_cmp		= sort__snoop_cmp,
1147 	.se_snprintf	= hist_entry__snoop_snprintf,
1148 	.se_width_idx	= HISTC_MEM_SNOOP,
1149 };
1150 
1151 struct sort_entry sort_mem_dcacheline = {
1152 	.se_header	= "Data Cacheline",
1153 	.se_cmp		= sort__dcacheline_cmp,
1154 	.se_snprintf	= hist_entry__dcacheline_snprintf,
1155 	.se_width_idx	= HISTC_MEM_DCACHELINE,
1156 };
1157 
1158 static int64_t
1159 sort__abort_cmp(struct hist_entry *left, struct hist_entry *right)
1160 {
1161 	if (!left->branch_info || !right->branch_info)
1162 		return cmp_null(left->branch_info, right->branch_info);
1163 
1164 	return left->branch_info->flags.abort !=
1165 		right->branch_info->flags.abort;
1166 }
1167 
1168 static int hist_entry__abort_snprintf(struct hist_entry *he, char *bf,
1169 				    size_t size, unsigned int width)
1170 {
1171 	static const char *out = "N/A";
1172 
1173 	if (he->branch_info) {
1174 		if (he->branch_info->flags.abort)
1175 			out = "A";
1176 		else
1177 			out = ".";
1178 	}
1179 
1180 	return repsep_snprintf(bf, size, "%-*s", width, out);
1181 }
1182 
1183 struct sort_entry sort_abort = {
1184 	.se_header	= "Transaction abort",
1185 	.se_cmp		= sort__abort_cmp,
1186 	.se_snprintf	= hist_entry__abort_snprintf,
1187 	.se_width_idx	= HISTC_ABORT,
1188 };
1189 
1190 static int64_t
1191 sort__in_tx_cmp(struct hist_entry *left, struct hist_entry *right)
1192 {
1193 	if (!left->branch_info || !right->branch_info)
1194 		return cmp_null(left->branch_info, right->branch_info);
1195 
1196 	return left->branch_info->flags.in_tx !=
1197 		right->branch_info->flags.in_tx;
1198 }
1199 
1200 static int hist_entry__in_tx_snprintf(struct hist_entry *he, char *bf,
1201 				    size_t size, unsigned int width)
1202 {
1203 	static const char *out = "N/A";
1204 
1205 	if (he->branch_info) {
1206 		if (he->branch_info->flags.in_tx)
1207 			out = "T";
1208 		else
1209 			out = ".";
1210 	}
1211 
1212 	return repsep_snprintf(bf, size, "%-*s", width, out);
1213 }
1214 
1215 struct sort_entry sort_in_tx = {
1216 	.se_header	= "Branch in transaction",
1217 	.se_cmp		= sort__in_tx_cmp,
1218 	.se_snprintf	= hist_entry__in_tx_snprintf,
1219 	.se_width_idx	= HISTC_IN_TX,
1220 };
1221 
1222 static int64_t
1223 sort__transaction_cmp(struct hist_entry *left, struct hist_entry *right)
1224 {
1225 	return left->transaction - right->transaction;
1226 }
1227 
1228 static inline char *add_str(char *p, const char *str)
1229 {
1230 	strcpy(p, str);
1231 	return p + strlen(str);
1232 }
1233 
1234 static struct txbit {
1235 	unsigned flag;
1236 	const char *name;
1237 	int skip_for_len;
1238 } txbits[] = {
1239 	{ PERF_TXN_ELISION,        "EL ",        0 },
1240 	{ PERF_TXN_TRANSACTION,    "TX ",        1 },
1241 	{ PERF_TXN_SYNC,           "SYNC ",      1 },
1242 	{ PERF_TXN_ASYNC,          "ASYNC ",     0 },
1243 	{ PERF_TXN_RETRY,          "RETRY ",     0 },
1244 	{ PERF_TXN_CONFLICT,       "CON ",       0 },
1245 	{ PERF_TXN_CAPACITY_WRITE, "CAP-WRITE ", 1 },
1246 	{ PERF_TXN_CAPACITY_READ,  "CAP-READ ",  0 },
1247 	{ 0, NULL, 0 }
1248 };
1249 
1250 int hist_entry__transaction_len(void)
1251 {
1252 	int i;
1253 	int len = 0;
1254 
1255 	for (i = 0; txbits[i].name; i++) {
1256 		if (!txbits[i].skip_for_len)
1257 			len += strlen(txbits[i].name);
1258 	}
1259 	len += 4; /* :XX<space> */
1260 	return len;
1261 }
1262 
1263 static int hist_entry__transaction_snprintf(struct hist_entry *he, char *bf,
1264 					    size_t size, unsigned int width)
1265 {
1266 	u64 t = he->transaction;
1267 	char buf[128];
1268 	char *p = buf;
1269 	int i;
1270 
1271 	buf[0] = 0;
1272 	for (i = 0; txbits[i].name; i++)
1273 		if (txbits[i].flag & t)
1274 			p = add_str(p, txbits[i].name);
1275 	if (t && !(t & (PERF_TXN_SYNC|PERF_TXN_ASYNC)))
1276 		p = add_str(p, "NEITHER ");
1277 	if (t & PERF_TXN_ABORT_MASK) {
1278 		sprintf(p, ":%" PRIx64,
1279 			(t & PERF_TXN_ABORT_MASK) >>
1280 			PERF_TXN_ABORT_SHIFT);
1281 		p += strlen(p);
1282 	}
1283 
1284 	return repsep_snprintf(bf, size, "%-*s", width, buf);
1285 }
1286 
1287 struct sort_entry sort_transaction = {
1288 	.se_header	= "Transaction                ",
1289 	.se_cmp		= sort__transaction_cmp,
1290 	.se_snprintf	= hist_entry__transaction_snprintf,
1291 	.se_width_idx	= HISTC_TRANSACTION,
1292 };
1293 
1294 struct sort_dimension {
1295 	const char		*name;
1296 	struct sort_entry	*entry;
1297 	int			taken;
1298 };
1299 
1300 #define DIM(d, n, func) [d] = { .name = n, .entry = &(func) }
1301 
1302 static struct sort_dimension common_sort_dimensions[] = {
1303 	DIM(SORT_PID, "pid", sort_thread),
1304 	DIM(SORT_COMM, "comm", sort_comm),
1305 	DIM(SORT_DSO, "dso", sort_dso),
1306 	DIM(SORT_SYM, "symbol", sort_sym),
1307 	DIM(SORT_PARENT, "parent", sort_parent),
1308 	DIM(SORT_CPU, "cpu", sort_cpu),
1309 	DIM(SORT_SOCKET, "socket", sort_socket),
1310 	DIM(SORT_SRCLINE, "srcline", sort_srcline),
1311 	DIM(SORT_SRCFILE, "srcfile", sort_srcfile),
1312 	DIM(SORT_LOCAL_WEIGHT, "local_weight", sort_local_weight),
1313 	DIM(SORT_GLOBAL_WEIGHT, "weight", sort_global_weight),
1314 	DIM(SORT_TRANSACTION, "transaction", sort_transaction),
1315 };
1316 
1317 #undef DIM
1318 
1319 #define DIM(d, n, func) [d - __SORT_BRANCH_STACK] = { .name = n, .entry = &(func) }
1320 
1321 static struct sort_dimension bstack_sort_dimensions[] = {
1322 	DIM(SORT_DSO_FROM, "dso_from", sort_dso_from),
1323 	DIM(SORT_DSO_TO, "dso_to", sort_dso_to),
1324 	DIM(SORT_SYM_FROM, "symbol_from", sort_sym_from),
1325 	DIM(SORT_SYM_TO, "symbol_to", sort_sym_to),
1326 	DIM(SORT_MISPREDICT, "mispredict", sort_mispredict),
1327 	DIM(SORT_IN_TX, "in_tx", sort_in_tx),
1328 	DIM(SORT_ABORT, "abort", sort_abort),
1329 	DIM(SORT_CYCLES, "cycles", sort_cycles),
1330 };
1331 
1332 #undef DIM
1333 
1334 #define DIM(d, n, func) [d - __SORT_MEMORY_MODE] = { .name = n, .entry = &(func) }
1335 
1336 static struct sort_dimension memory_sort_dimensions[] = {
1337 	DIM(SORT_MEM_DADDR_SYMBOL, "symbol_daddr", sort_mem_daddr_sym),
1338 	DIM(SORT_MEM_IADDR_SYMBOL, "symbol_iaddr", sort_mem_iaddr_sym),
1339 	DIM(SORT_MEM_DADDR_DSO, "dso_daddr", sort_mem_daddr_dso),
1340 	DIM(SORT_MEM_LOCKED, "locked", sort_mem_locked),
1341 	DIM(SORT_MEM_TLB, "tlb", sort_mem_tlb),
1342 	DIM(SORT_MEM_LVL, "mem", sort_mem_lvl),
1343 	DIM(SORT_MEM_SNOOP, "snoop", sort_mem_snoop),
1344 	DIM(SORT_MEM_DCACHELINE, "dcacheline", sort_mem_dcacheline),
1345 };
1346 
1347 #undef DIM
1348 
1349 struct hpp_dimension {
1350 	const char		*name;
1351 	struct perf_hpp_fmt	*fmt;
1352 	int			taken;
1353 };
1354 
1355 #define DIM(d, n) { .name = n, .fmt = &perf_hpp__format[d], }
1356 
1357 static struct hpp_dimension hpp_sort_dimensions[] = {
1358 	DIM(PERF_HPP__OVERHEAD, "overhead"),
1359 	DIM(PERF_HPP__OVERHEAD_SYS, "overhead_sys"),
1360 	DIM(PERF_HPP__OVERHEAD_US, "overhead_us"),
1361 	DIM(PERF_HPP__OVERHEAD_GUEST_SYS, "overhead_guest_sys"),
1362 	DIM(PERF_HPP__OVERHEAD_GUEST_US, "overhead_guest_us"),
1363 	DIM(PERF_HPP__OVERHEAD_ACC, "overhead_children"),
1364 	DIM(PERF_HPP__SAMPLES, "sample"),
1365 	DIM(PERF_HPP__PERIOD, "period"),
1366 };
1367 
1368 #undef DIM
1369 
1370 struct hpp_sort_entry {
1371 	struct perf_hpp_fmt hpp;
1372 	struct sort_entry *se;
1373 };
1374 
1375 bool perf_hpp__same_sort_entry(struct perf_hpp_fmt *a, struct perf_hpp_fmt *b)
1376 {
1377 	struct hpp_sort_entry *hse_a;
1378 	struct hpp_sort_entry *hse_b;
1379 
1380 	if (!perf_hpp__is_sort_entry(a) || !perf_hpp__is_sort_entry(b))
1381 		return false;
1382 
1383 	hse_a = container_of(a, struct hpp_sort_entry, hpp);
1384 	hse_b = container_of(b, struct hpp_sort_entry, hpp);
1385 
1386 	return hse_a->se == hse_b->se;
1387 }
1388 
1389 void perf_hpp__reset_sort_width(struct perf_hpp_fmt *fmt, struct hists *hists)
1390 {
1391 	struct hpp_sort_entry *hse;
1392 
1393 	if (!perf_hpp__is_sort_entry(fmt))
1394 		return;
1395 
1396 	hse = container_of(fmt, struct hpp_sort_entry, hpp);
1397 	hists__new_col_len(hists, hse->se->se_width_idx, strlen(fmt->name));
1398 }
1399 
1400 static int __sort__hpp_header(struct perf_hpp_fmt *fmt, struct perf_hpp *hpp,
1401 			      struct perf_evsel *evsel)
1402 {
1403 	struct hpp_sort_entry *hse;
1404 	size_t len = fmt->user_len;
1405 
1406 	hse = container_of(fmt, struct hpp_sort_entry, hpp);
1407 
1408 	if (!len)
1409 		len = hists__col_len(evsel__hists(evsel), hse->se->se_width_idx);
1410 
1411 	return scnprintf(hpp->buf, hpp->size, "%-*.*s", len, len, fmt->name);
1412 }
1413 
1414 static int __sort__hpp_width(struct perf_hpp_fmt *fmt,
1415 			     struct perf_hpp *hpp __maybe_unused,
1416 			     struct perf_evsel *evsel)
1417 {
1418 	struct hpp_sort_entry *hse;
1419 	size_t len = fmt->user_len;
1420 
1421 	hse = container_of(fmt, struct hpp_sort_entry, hpp);
1422 
1423 	if (!len)
1424 		len = hists__col_len(evsel__hists(evsel), hse->se->se_width_idx);
1425 
1426 	return len;
1427 }
1428 
1429 static int __sort__hpp_entry(struct perf_hpp_fmt *fmt, struct perf_hpp *hpp,
1430 			     struct hist_entry *he)
1431 {
1432 	struct hpp_sort_entry *hse;
1433 	size_t len = fmt->user_len;
1434 
1435 	hse = container_of(fmt, struct hpp_sort_entry, hpp);
1436 
1437 	if (!len)
1438 		len = hists__col_len(he->hists, hse->se->se_width_idx);
1439 
1440 	return hse->se->se_snprintf(he, hpp->buf, hpp->size, len);
1441 }
1442 
1443 static int64_t __sort__hpp_cmp(struct perf_hpp_fmt *fmt,
1444 			       struct hist_entry *a, struct hist_entry *b)
1445 {
1446 	struct hpp_sort_entry *hse;
1447 
1448 	hse = container_of(fmt, struct hpp_sort_entry, hpp);
1449 	return hse->se->se_cmp(a, b);
1450 }
1451 
1452 static int64_t __sort__hpp_collapse(struct perf_hpp_fmt *fmt,
1453 				    struct hist_entry *a, struct hist_entry *b)
1454 {
1455 	struct hpp_sort_entry *hse;
1456 	int64_t (*collapse_fn)(struct hist_entry *, struct hist_entry *);
1457 
1458 	hse = container_of(fmt, struct hpp_sort_entry, hpp);
1459 	collapse_fn = hse->se->se_collapse ?: hse->se->se_cmp;
1460 	return collapse_fn(a, b);
1461 }
1462 
1463 static int64_t __sort__hpp_sort(struct perf_hpp_fmt *fmt,
1464 				struct hist_entry *a, struct hist_entry *b)
1465 {
1466 	struct hpp_sort_entry *hse;
1467 	int64_t (*sort_fn)(struct hist_entry *, struct hist_entry *);
1468 
1469 	hse = container_of(fmt, struct hpp_sort_entry, hpp);
1470 	sort_fn = hse->se->se_sort ?: hse->se->se_cmp;
1471 	return sort_fn(a, b);
1472 }
1473 
1474 static struct hpp_sort_entry *
1475 __sort_dimension__alloc_hpp(struct sort_dimension *sd)
1476 {
1477 	struct hpp_sort_entry *hse;
1478 
1479 	hse = malloc(sizeof(*hse));
1480 	if (hse == NULL) {
1481 		pr_err("Memory allocation failed\n");
1482 		return NULL;
1483 	}
1484 
1485 	hse->se = sd->entry;
1486 	hse->hpp.name = sd->entry->se_header;
1487 	hse->hpp.header = __sort__hpp_header;
1488 	hse->hpp.width = __sort__hpp_width;
1489 	hse->hpp.entry = __sort__hpp_entry;
1490 	hse->hpp.color = NULL;
1491 
1492 	hse->hpp.cmp = __sort__hpp_cmp;
1493 	hse->hpp.collapse = __sort__hpp_collapse;
1494 	hse->hpp.sort = __sort__hpp_sort;
1495 
1496 	INIT_LIST_HEAD(&hse->hpp.list);
1497 	INIT_LIST_HEAD(&hse->hpp.sort_list);
1498 	hse->hpp.elide = false;
1499 	hse->hpp.len = 0;
1500 	hse->hpp.user_len = 0;
1501 
1502 	return hse;
1503 }
1504 
1505 bool perf_hpp__is_sort_entry(struct perf_hpp_fmt *format)
1506 {
1507 	return format->header == __sort__hpp_header;
1508 }
1509 
1510 static int __sort_dimension__add_hpp_sort(struct sort_dimension *sd)
1511 {
1512 	struct hpp_sort_entry *hse = __sort_dimension__alloc_hpp(sd);
1513 
1514 	if (hse == NULL)
1515 		return -1;
1516 
1517 	perf_hpp__register_sort_field(&hse->hpp);
1518 	return 0;
1519 }
1520 
1521 static int __sort_dimension__add_hpp_output(struct sort_dimension *sd)
1522 {
1523 	struct hpp_sort_entry *hse = __sort_dimension__alloc_hpp(sd);
1524 
1525 	if (hse == NULL)
1526 		return -1;
1527 
1528 	perf_hpp__column_register(&hse->hpp);
1529 	return 0;
1530 }
1531 
1532 static int __sort_dimension__add(struct sort_dimension *sd)
1533 {
1534 	if (sd->taken)
1535 		return 0;
1536 
1537 	if (__sort_dimension__add_hpp_sort(sd) < 0)
1538 		return -1;
1539 
1540 	if (sd->entry->se_collapse)
1541 		sort__need_collapse = 1;
1542 
1543 	sd->taken = 1;
1544 
1545 	return 0;
1546 }
1547 
1548 static int __hpp_dimension__add(struct hpp_dimension *hd)
1549 {
1550 	if (!hd->taken) {
1551 		hd->taken = 1;
1552 
1553 		perf_hpp__register_sort_field(hd->fmt);
1554 	}
1555 	return 0;
1556 }
1557 
1558 static int __sort_dimension__add_output(struct sort_dimension *sd)
1559 {
1560 	if (sd->taken)
1561 		return 0;
1562 
1563 	if (__sort_dimension__add_hpp_output(sd) < 0)
1564 		return -1;
1565 
1566 	sd->taken = 1;
1567 	return 0;
1568 }
1569 
1570 static int __hpp_dimension__add_output(struct hpp_dimension *hd)
1571 {
1572 	if (!hd->taken) {
1573 		hd->taken = 1;
1574 
1575 		perf_hpp__column_register(hd->fmt);
1576 	}
1577 	return 0;
1578 }
1579 
1580 int hpp_dimension__add_output(unsigned col)
1581 {
1582 	BUG_ON(col >= PERF_HPP__MAX_INDEX);
1583 	return __hpp_dimension__add_output(&hpp_sort_dimensions[col]);
1584 }
1585 
1586 int sort_dimension__add(const char *tok)
1587 {
1588 	unsigned int i;
1589 
1590 	for (i = 0; i < ARRAY_SIZE(common_sort_dimensions); i++) {
1591 		struct sort_dimension *sd = &common_sort_dimensions[i];
1592 
1593 		if (strncasecmp(tok, sd->name, strlen(tok)))
1594 			continue;
1595 
1596 		if (sd->entry == &sort_parent) {
1597 			int ret = regcomp(&parent_regex, parent_pattern, REG_EXTENDED);
1598 			if (ret) {
1599 				char err[BUFSIZ];
1600 
1601 				regerror(ret, &parent_regex, err, sizeof(err));
1602 				pr_err("Invalid regex: %s\n%s", parent_pattern, err);
1603 				return -EINVAL;
1604 			}
1605 			sort__has_parent = 1;
1606 		} else if (sd->entry == &sort_sym) {
1607 			sort__has_sym = 1;
1608 			/*
1609 			 * perf diff displays the performance difference amongst
1610 			 * two or more perf.data files. Those files could come
1611 			 * from different binaries. So we should not compare
1612 			 * their ips, but the name of symbol.
1613 			 */
1614 			if (sort__mode == SORT_MODE__DIFF)
1615 				sd->entry->se_collapse = sort__sym_sort;
1616 
1617 		} else if (sd->entry == &sort_dso) {
1618 			sort__has_dso = 1;
1619 		} else if (sd->entry == &sort_socket) {
1620 			sort__has_socket = 1;
1621 		}
1622 
1623 		return __sort_dimension__add(sd);
1624 	}
1625 
1626 	for (i = 0; i < ARRAY_SIZE(hpp_sort_dimensions); i++) {
1627 		struct hpp_dimension *hd = &hpp_sort_dimensions[i];
1628 
1629 		if (strncasecmp(tok, hd->name, strlen(tok)))
1630 			continue;
1631 
1632 		return __hpp_dimension__add(hd);
1633 	}
1634 
1635 	for (i = 0; i < ARRAY_SIZE(bstack_sort_dimensions); i++) {
1636 		struct sort_dimension *sd = &bstack_sort_dimensions[i];
1637 
1638 		if (strncasecmp(tok, sd->name, strlen(tok)))
1639 			continue;
1640 
1641 		if (sort__mode != SORT_MODE__BRANCH)
1642 			return -EINVAL;
1643 
1644 		if (sd->entry == &sort_sym_from || sd->entry == &sort_sym_to)
1645 			sort__has_sym = 1;
1646 
1647 		__sort_dimension__add(sd);
1648 		return 0;
1649 	}
1650 
1651 	for (i = 0; i < ARRAY_SIZE(memory_sort_dimensions); i++) {
1652 		struct sort_dimension *sd = &memory_sort_dimensions[i];
1653 
1654 		if (strncasecmp(tok, sd->name, strlen(tok)))
1655 			continue;
1656 
1657 		if (sort__mode != SORT_MODE__MEMORY)
1658 			return -EINVAL;
1659 
1660 		if (sd->entry == &sort_mem_daddr_sym)
1661 			sort__has_sym = 1;
1662 
1663 		__sort_dimension__add(sd);
1664 		return 0;
1665 	}
1666 
1667 	return -ESRCH;
1668 }
1669 
1670 static const char *get_default_sort_order(void)
1671 {
1672 	const char *default_sort_orders[] = {
1673 		default_sort_order,
1674 		default_branch_sort_order,
1675 		default_mem_sort_order,
1676 		default_top_sort_order,
1677 		default_diff_sort_order,
1678 	};
1679 
1680 	BUG_ON(sort__mode >= ARRAY_SIZE(default_sort_orders));
1681 
1682 	return default_sort_orders[sort__mode];
1683 }
1684 
1685 static int setup_sort_order(void)
1686 {
1687 	char *new_sort_order;
1688 
1689 	/*
1690 	 * Append '+'-prefixed sort order to the default sort
1691 	 * order string.
1692 	 */
1693 	if (!sort_order || is_strict_order(sort_order))
1694 		return 0;
1695 
1696 	if (sort_order[1] == '\0') {
1697 		error("Invalid --sort key: `+'");
1698 		return -EINVAL;
1699 	}
1700 
1701 	/*
1702 	 * We allocate new sort_order string, but we never free it,
1703 	 * because it's checked over the rest of the code.
1704 	 */
1705 	if (asprintf(&new_sort_order, "%s,%s",
1706 		     get_default_sort_order(), sort_order + 1) < 0) {
1707 		error("Not enough memory to set up --sort");
1708 		return -ENOMEM;
1709 	}
1710 
1711 	sort_order = new_sort_order;
1712 	return 0;
1713 }
1714 
1715 static int __setup_sorting(void)
1716 {
1717 	char *tmp, *tok, *str;
1718 	const char *sort_keys;
1719 	int ret = 0;
1720 
1721 	ret = setup_sort_order();
1722 	if (ret)
1723 		return ret;
1724 
1725 	sort_keys = sort_order;
1726 	if (sort_keys == NULL) {
1727 		if (is_strict_order(field_order)) {
1728 			/*
1729 			 * If user specified field order but no sort order,
1730 			 * we'll honor it and not add default sort orders.
1731 			 */
1732 			return 0;
1733 		}
1734 
1735 		sort_keys = get_default_sort_order();
1736 	}
1737 
1738 	str = strdup(sort_keys);
1739 	if (str == NULL) {
1740 		error("Not enough memory to setup sort keys");
1741 		return -ENOMEM;
1742 	}
1743 
1744 	for (tok = strtok_r(str, ", ", &tmp);
1745 			tok; tok = strtok_r(NULL, ", ", &tmp)) {
1746 		ret = sort_dimension__add(tok);
1747 		if (ret == -EINVAL) {
1748 			error("Invalid --sort key: `%s'", tok);
1749 			break;
1750 		} else if (ret == -ESRCH) {
1751 			error("Unknown --sort key: `%s'", tok);
1752 			break;
1753 		}
1754 	}
1755 
1756 	free(str);
1757 	return ret;
1758 }
1759 
1760 void perf_hpp__set_elide(int idx, bool elide)
1761 {
1762 	struct perf_hpp_fmt *fmt;
1763 	struct hpp_sort_entry *hse;
1764 
1765 	perf_hpp__for_each_format(fmt) {
1766 		if (!perf_hpp__is_sort_entry(fmt))
1767 			continue;
1768 
1769 		hse = container_of(fmt, struct hpp_sort_entry, hpp);
1770 		if (hse->se->se_width_idx == idx) {
1771 			fmt->elide = elide;
1772 			break;
1773 		}
1774 	}
1775 }
1776 
1777 static bool __get_elide(struct strlist *list, const char *list_name, FILE *fp)
1778 {
1779 	if (list && strlist__nr_entries(list) == 1) {
1780 		if (fp != NULL)
1781 			fprintf(fp, "# %s: %s\n", list_name,
1782 				strlist__entry(list, 0)->s);
1783 		return true;
1784 	}
1785 	return false;
1786 }
1787 
1788 static bool get_elide(int idx, FILE *output)
1789 {
1790 	switch (idx) {
1791 	case HISTC_SYMBOL:
1792 		return __get_elide(symbol_conf.sym_list, "symbol", output);
1793 	case HISTC_DSO:
1794 		return __get_elide(symbol_conf.dso_list, "dso", output);
1795 	case HISTC_COMM:
1796 		return __get_elide(symbol_conf.comm_list, "comm", output);
1797 	default:
1798 		break;
1799 	}
1800 
1801 	if (sort__mode != SORT_MODE__BRANCH)
1802 		return false;
1803 
1804 	switch (idx) {
1805 	case HISTC_SYMBOL_FROM:
1806 		return __get_elide(symbol_conf.sym_from_list, "sym_from", output);
1807 	case HISTC_SYMBOL_TO:
1808 		return __get_elide(symbol_conf.sym_to_list, "sym_to", output);
1809 	case HISTC_DSO_FROM:
1810 		return __get_elide(symbol_conf.dso_from_list, "dso_from", output);
1811 	case HISTC_DSO_TO:
1812 		return __get_elide(symbol_conf.dso_to_list, "dso_to", output);
1813 	default:
1814 		break;
1815 	}
1816 
1817 	return false;
1818 }
1819 
1820 void sort__setup_elide(FILE *output)
1821 {
1822 	struct perf_hpp_fmt *fmt;
1823 	struct hpp_sort_entry *hse;
1824 
1825 	perf_hpp__for_each_format(fmt) {
1826 		if (!perf_hpp__is_sort_entry(fmt))
1827 			continue;
1828 
1829 		hse = container_of(fmt, struct hpp_sort_entry, hpp);
1830 		fmt->elide = get_elide(hse->se->se_width_idx, output);
1831 	}
1832 
1833 	/*
1834 	 * It makes no sense to elide all of sort entries.
1835 	 * Just revert them to show up again.
1836 	 */
1837 	perf_hpp__for_each_format(fmt) {
1838 		if (!perf_hpp__is_sort_entry(fmt))
1839 			continue;
1840 
1841 		if (!fmt->elide)
1842 			return;
1843 	}
1844 
1845 	perf_hpp__for_each_format(fmt) {
1846 		if (!perf_hpp__is_sort_entry(fmt))
1847 			continue;
1848 
1849 		fmt->elide = false;
1850 	}
1851 }
1852 
1853 static int output_field_add(char *tok)
1854 {
1855 	unsigned int i;
1856 
1857 	for (i = 0; i < ARRAY_SIZE(common_sort_dimensions); i++) {
1858 		struct sort_dimension *sd = &common_sort_dimensions[i];
1859 
1860 		if (strncasecmp(tok, sd->name, strlen(tok)))
1861 			continue;
1862 
1863 		return __sort_dimension__add_output(sd);
1864 	}
1865 
1866 	for (i = 0; i < ARRAY_SIZE(hpp_sort_dimensions); i++) {
1867 		struct hpp_dimension *hd = &hpp_sort_dimensions[i];
1868 
1869 		if (strncasecmp(tok, hd->name, strlen(tok)))
1870 			continue;
1871 
1872 		return __hpp_dimension__add_output(hd);
1873 	}
1874 
1875 	for (i = 0; i < ARRAY_SIZE(bstack_sort_dimensions); i++) {
1876 		struct sort_dimension *sd = &bstack_sort_dimensions[i];
1877 
1878 		if (strncasecmp(tok, sd->name, strlen(tok)))
1879 			continue;
1880 
1881 		return __sort_dimension__add_output(sd);
1882 	}
1883 
1884 	for (i = 0; i < ARRAY_SIZE(memory_sort_dimensions); i++) {
1885 		struct sort_dimension *sd = &memory_sort_dimensions[i];
1886 
1887 		if (strncasecmp(tok, sd->name, strlen(tok)))
1888 			continue;
1889 
1890 		return __sort_dimension__add_output(sd);
1891 	}
1892 
1893 	return -ESRCH;
1894 }
1895 
1896 static void reset_dimensions(void)
1897 {
1898 	unsigned int i;
1899 
1900 	for (i = 0; i < ARRAY_SIZE(common_sort_dimensions); i++)
1901 		common_sort_dimensions[i].taken = 0;
1902 
1903 	for (i = 0; i < ARRAY_SIZE(hpp_sort_dimensions); i++)
1904 		hpp_sort_dimensions[i].taken = 0;
1905 
1906 	for (i = 0; i < ARRAY_SIZE(bstack_sort_dimensions); i++)
1907 		bstack_sort_dimensions[i].taken = 0;
1908 
1909 	for (i = 0; i < ARRAY_SIZE(memory_sort_dimensions); i++)
1910 		memory_sort_dimensions[i].taken = 0;
1911 }
1912 
1913 bool is_strict_order(const char *order)
1914 {
1915 	return order && (*order != '+');
1916 }
1917 
1918 static int __setup_output_field(void)
1919 {
1920 	char *tmp, *tok, *str, *strp;
1921 	int ret = -EINVAL;
1922 
1923 	if (field_order == NULL)
1924 		return 0;
1925 
1926 	strp = str = strdup(field_order);
1927 	if (str == NULL) {
1928 		error("Not enough memory to setup output fields");
1929 		return -ENOMEM;
1930 	}
1931 
1932 	if (!is_strict_order(field_order))
1933 		strp++;
1934 
1935 	if (!strlen(strp)) {
1936 		error("Invalid --fields key: `+'");
1937 		goto out;
1938 	}
1939 
1940 	for (tok = strtok_r(strp, ", ", &tmp);
1941 			tok; tok = strtok_r(NULL, ", ", &tmp)) {
1942 		ret = output_field_add(tok);
1943 		if (ret == -EINVAL) {
1944 			error("Invalid --fields key: `%s'", tok);
1945 			break;
1946 		} else if (ret == -ESRCH) {
1947 			error("Unknown --fields key: `%s'", tok);
1948 			break;
1949 		}
1950 	}
1951 
1952 out:
1953 	free(str);
1954 	return ret;
1955 }
1956 
1957 int setup_sorting(void)
1958 {
1959 	int err;
1960 
1961 	err = __setup_sorting();
1962 	if (err < 0)
1963 		return err;
1964 
1965 	if (parent_pattern != default_parent_pattern) {
1966 		err = sort_dimension__add("parent");
1967 		if (err < 0)
1968 			return err;
1969 	}
1970 
1971 	reset_dimensions();
1972 
1973 	/*
1974 	 * perf diff doesn't use default hpp output fields.
1975 	 */
1976 	if (sort__mode != SORT_MODE__DIFF)
1977 		perf_hpp__init();
1978 
1979 	err = __setup_output_field();
1980 	if (err < 0)
1981 		return err;
1982 
1983 	/* copy sort keys to output fields */
1984 	perf_hpp__setup_output_field();
1985 	/* and then copy output fields to sort keys */
1986 	perf_hpp__append_sort_keys();
1987 
1988 	return 0;
1989 }
1990 
1991 void reset_output_field(void)
1992 {
1993 	sort__need_collapse = 0;
1994 	sort__has_parent = 0;
1995 	sort__has_sym = 0;
1996 	sort__has_dso = 0;
1997 
1998 	field_order = NULL;
1999 	sort_order = NULL;
2000 
2001 	reset_dimensions();
2002 	perf_hpp__reset_output_field();
2003 }
2004