tools/perf/util/sort.c

   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         if (!left->branch_info || !right->branch_info)
 608                 return cmp_null(left->branch_info, right->branch_info);
 609
 610         return left->branch_info->flags.cycles -
 611                 right->branch_info->flags.cycles;
 612 }
 613
 614 static int hist_entry__cycles_snprintf(struct hist_entry *he, char *bf,
 615                                     size_t size, unsigned int width)
 616 {
 617         if (!he->branch_info)
 618                 return scnprintf(bf, size, "%-.*s", width, "N/A");
 619         if (he->branch_info->flags.cycles == 0)
 620                 return repsep_snprintf(bf, size, "%-*s", width, "-");
 621         return repsep_snprintf(bf, size, "%-*hd", width,
 622                                he->branch_info->flags.cycles);
 623 }
 624
 625 struct sort_entry sort_cycles = {
 626         .se_header      = "Basic Block Cycles",
 627         .se_cmp         = sort__cycles_cmp,
 628         .se_snprintf    = hist_entry__cycles_snprintf,
 629         .se_width_idx   = HISTC_CYCLES,
 630 };
 631
 632 /* --sort daddr_sym */
 633 static int64_t
 634 sort__daddr_cmp(struct hist_entry *left, struct hist_entry *right)
 635 {
 636         uint64_t l = 0, r = 0;
 637
 638         if (left->mem_info)
 639                 l = left->mem_info->daddr.addr;
 640         if (right->mem_info)
 641                 r = right->mem_info->daddr.addr;
 642
 643         return (int64_t)(r - l);
 644 }
 645
 646 static int hist_entry__daddr_snprintf(struct hist_entry *he, char *bf,
 647                                     size_t size, unsigned int width)
 648 {
 649         uint64_t addr = 0;
 650         struct map *map = NULL;
 651         struct symbol *sym = NULL;
 652
 653         if (he->mem_info) {
 654                 addr = he->mem_info->daddr.addr;
 655                 map = he->mem_info->daddr.map;
 656                 sym = he->mem_info->daddr.sym;
 657         }
 658         return _hist_entry__sym_snprintf(map, sym, addr, he->level, bf, size,
 659                                          width);
 660 }
 661
 662 static int64_t
 663 sort__iaddr_cmp(struct hist_entry *left, struct hist_entry *right)
 664 {
 665         uint64_t l = 0, r = 0;
 666
 667         if (left->mem_info)
 668                 l = left->mem_info->iaddr.addr;
 669         if (right->mem_info)
 670                 r = right->mem_info->iaddr.addr;
 671
 672         return (int64_t)(r - l);
 673 }
 674
 675 static int hist_entry__iaddr_snprintf(struct hist_entry *he, char *bf,
 676                                     size_t size, unsigned int width)
 677 {
 678         uint64_t addr = 0;
 679         struct map *map = NULL;
 680         struct symbol *sym = NULL;
 681
 682         if (he->mem_info) {
 683                 addr = he->mem_info->iaddr.addr;
 684                 map  = he->mem_info->iaddr.map;
 685                 sym  = he->mem_info->iaddr.sym;
 686         }
 687         return _hist_entry__sym_snprintf(map, sym, addr, he->level, bf, size,
 688                                          width);
 689 }
 690
 691 static int64_t
 692 sort__dso_daddr_cmp(struct hist_entry *left, struct hist_entry *right)
 693 {
 694         struct map *map_l = NULL;
 695         struct map *map_r = NULL;
 696
 697         if (left->mem_info)
 698                 map_l = left->mem_info->daddr.map;
 699         if (right->mem_info)
 700                 map_r = right->mem_info->daddr.map;
 701
 702         return _sort__dso_cmp(map_l, map_r);
 703 }
 704
 705 static int hist_entry__dso_daddr_snprintf(struct hist_entry *he, char *bf,
 706                                     size_t size, unsigned int width)
 707 {
 708         struct map *map = NULL;
 709
 710         if (he->mem_info)
 711                 map = he->mem_info->daddr.map;
 712
 713         return _hist_entry__dso_snprintf(map, bf, size, width);
 714 }
 715
 716 static int64_t
 717 sort__locked_cmp(struct hist_entry *left, struct hist_entry *right)
 718 {
 719         union perf_mem_data_src data_src_l;
 720         union perf_mem_data_src data_src_r;
 721
 722         if (left->mem_info)
 723                 data_src_l = left->mem_info->data_src;
 724         else
 725                 data_src_l.mem_lock = PERF_MEM_LOCK_NA;
 726
 727         if (right->mem_info)
 728                 data_src_r = right->mem_info->data_src;
 729         else
 730                 data_src_r.mem_lock = PERF_MEM_LOCK_NA;
 731
 732         return (int64_t)(data_src_r.mem_lock - data_src_l.mem_lock);
 733 }
 734
 735 static int hist_entry__locked_snprintf(struct hist_entry *he, char *bf,
 736                                     size_t size, unsigned int width)
 737 {
 738         const char *out;
 739         u64 mask = PERF_MEM_LOCK_NA;
 740
 741         if (he->mem_info)
 742                 mask = he->mem_info->data_src.mem_lock;
 743
 744         if (mask & PERF_MEM_LOCK_NA)
 745                 out = "N/A";
 746         else if (mask & PERF_MEM_LOCK_LOCKED)
 747                 out = "Yes";
 748         else
 749                 out = "No";
 750
 751         return repsep_snprintf(bf, size, "%-*s", width, out);
 752 }
 753
 754 static int64_t
 755 sort__tlb_cmp(struct hist_entry *left, struct hist_entry *right)
 756 {
 757         union perf_mem_data_src data_src_l;
 758         union perf_mem_data_src data_src_r;
 759
 760         if (left->mem_info)
 761                 data_src_l = left->mem_info->data_src;
 762         else
 763                 data_src_l.mem_dtlb = PERF_MEM_TLB_NA;
 764
 765         if (right->mem_info)
 766                 data_src_r = right->mem_info->data_src;
 767         else
 768                 data_src_r.mem_dtlb = PERF_MEM_TLB_NA;
 769
 770         return (int64_t)(data_src_r.mem_dtlb - data_src_l.mem_dtlb);
 771 }
 772
 773 static const char * const tlb_access[] = {
 774         "N/A",
 775         "HIT",
 776         "MISS",
 777         "L1",
 778         "L2",
 779         "Walker",
 780         "Fault",
 781 };
 782 #define NUM_TLB_ACCESS (sizeof(tlb_access)/sizeof(const char *))
 783
 784 static int hist_entry__tlb_snprintf(struct hist_entry *he, char *bf,
 785                                     size_t size, unsigned int width)
 786 {
 787         char out[64];
 788         size_t sz = sizeof(out) - 1; /* -1 for null termination */
 789         size_t l = 0, i;
 790         u64 m = PERF_MEM_TLB_NA;
 791         u64 hit, miss;
 792
 793         out[0] = '\0';
 794
 795         if (he->mem_info)
 796                 m = he->mem_info->data_src.mem_dtlb;
 797
 798         hit = m & PERF_MEM_TLB_HIT;
 799         miss = m & PERF_MEM_TLB_MISS;
 800
 801         /* already taken care of */
 802         m &= ~(PERF_MEM_TLB_HIT|PERF_MEM_TLB_MISS);
 803
 804         for (i = 0; m && i < NUM_TLB_ACCESS; i++, m >>= 1) {
 805                 if (!(m & 0x1))
 806                         continue;
 807                 if (l) {
 808                         strcat(out, " or ");
 809                         l += 4;
 810                 }
 811                 strncat(out, tlb_access[i], sz - l);
 812                 l += strlen(tlb_access[i]);
 813         }
 814         if (*out == '\0')
 815                 strcpy(out, "N/A");
 816         if (hit)
 817                 strncat(out, " hit", sz - l);
 818         if (miss)
 819                 strncat(out, " miss", sz - l);
 820
 821         return repsep_snprintf(bf, size, "%-*s", width, out);
 822 }
 823
 824 static int64_t
 825 sort__lvl_cmp(struct hist_entry *left, struct hist_entry *right)
 826 {
 827         union perf_mem_data_src data_src_l;
 828         union perf_mem_data_src data_src_r;
 829
 830         if (left->mem_info)
 831                 data_src_l = left->mem_info->data_src;
 832         else
 833                 data_src_l.mem_lvl = PERF_MEM_LVL_NA;
 834
 835         if (right->mem_info)
 836                 data_src_r = right->mem_info->data_src;
 837         else
 838                 data_src_r.mem_lvl = PERF_MEM_LVL_NA;
 839
 840         return (int64_t)(data_src_r.mem_lvl - data_src_l.mem_lvl);
 841 }
 842
 843 static const char * const mem_lvl[] = {
 844         "N/A",
 845         "HIT",
 846         "MISS",
 847         "L1",
 848         "LFB",
 849         "L2",
 850         "L3",
 851         "Local RAM",
 852         "Remote RAM (1 hop)",
 853         "Remote RAM (2 hops)",
 854         "Remote Cache (1 hop)",
 855         "Remote Cache (2 hops)",
 856         "I/O",
 857         "Uncached",
 858 };
 859 #define NUM_MEM_LVL (sizeof(mem_lvl)/sizeof(const char *))
 860
 861 static int hist_entry__lvl_snprintf(struct hist_entry *he, char *bf,
 862                                     size_t size, unsigned int width)
 863 {
 864         char out[64];
 865         size_t sz = sizeof(out) - 1; /* -1 for null termination */
 866         size_t i, l = 0;
 867         u64 m =  PERF_MEM_LVL_NA;
 868         u64 hit, miss;
 869
 870         if (he->mem_info)
 871                 m  = he->mem_info->data_src.mem_lvl;
 872
 873         out[0] = '\0';
 874
 875         hit = m & PERF_MEM_LVL_HIT;
 876         miss = m & PERF_MEM_LVL_MISS;
 877
 878         /* already taken care of */
 879         m &= ~(PERF_MEM_LVL_HIT|PERF_MEM_LVL_MISS);
 880
 881         for (i = 0; m && i < NUM_MEM_LVL; i++, m >>= 1) {
 882                 if (!(m & 0x1))
 883                         continue;
 884                 if (l) {
 885                         strcat(out, " or ");
 886                         l += 4;
 887                 }
 888                 strncat(out, mem_lvl[i], sz - l);
 889                 l += strlen(mem_lvl[i]);
 890         }
 891         if (*out == '\0')
 892                 strcpy(out, "N/A");
 893         if (hit)
 894                 strncat(out, " hit", sz - l);
 895         if (miss)
 896                 strncat(out, " miss", sz - l);
 897
 898         return repsep_snprintf(bf, size, "%-*s", width, out);
 899 }
 900
 901 static int64_t
 902 sort__snoop_cmp(struct hist_entry *left, struct hist_entry *right)
 903 {
 904         union perf_mem_data_src data_src_l;
 905         union perf_mem_data_src data_src_r;
 906
 907         if (left->mem_info)
 908                 data_src_l = left->mem_info->data_src;
 909         else
 910                 data_src_l.mem_snoop = PERF_MEM_SNOOP_NA;
 911
 912         if (right->mem_info)
 913                 data_src_r = right->mem_info->data_src;
 914         else
 915                 data_src_r.mem_snoop = PERF_MEM_SNOOP_NA;
 916
 917         return (int64_t)(data_src_r.mem_snoop - data_src_l.mem_snoop);
 918 }
 919
 920 static const char * const snoop_access[] = {
 921         "N/A",
 922         "None",
 923         "Miss",
 924         "Hit",
 925         "HitM",
 926 };
 927 #define NUM_SNOOP_ACCESS (sizeof(snoop_access)/sizeof(const char *))
 928
 929 static int hist_entry__snoop_snprintf(struct hist_entry *he, char *bf,
 930                                     size_t size, unsigned int width)
 931 {
 932         char out[64];
 933         size_t sz = sizeof(out) - 1; /* -1 for null termination */
 934         size_t i, l = 0;
 935         u64 m = PERF_MEM_SNOOP_NA;
 936
 937         out[0] = '\0';
 938
 939         if (he->mem_info)
 940                 m = he->mem_info->data_src.mem_snoop;
 941
 942         for (i = 0; m && i < NUM_SNOOP_ACCESS; i++, m >>= 1) {
 943                 if (!(m & 0x1))
 944                         continue;
 945                 if (l) {
 946                         strcat(out, " or ");
 947                         l += 4;
 948                 }
 949                 strncat(out, snoop_access[i], sz - l);
 950                 l += strlen(snoop_access[i]);
 951         }
 952
 953         if (*out == '\0')
 954                 strcpy(out, "N/A");
 955
 956         return repsep_snprintf(bf, size, "%-*s", width, out);
 957 }
 958
 959 static inline  u64 cl_address(u64 address)
 960 {
 961         /* return the cacheline of the address */
 962         return (address & ~(cacheline_size - 1));
 963 }
 964
 965 static int64_t
 966 sort__dcacheline_cmp(struct hist_entry *left, struct hist_entry *right)
 967 {
 968         u64 l, r;
 969         struct map *l_map, *r_map;
 970
 971         if (!left->mem_info)  return -1;
 972         if (!right->mem_info) return 1;
 973
 974         /* group event types together */
 975         if (left->cpumode > right->cpumode) return -1;
 976         if (left->cpumode < right->cpumode) return 1;
 977
 978         l_map = left->mem_info->daddr.map;
 979         r_map = right->mem_info->daddr.map;
 980
 981         /* if both are NULL, jump to sort on al_addr instead */
 982         if (!l_map && !r_map)
 983                 goto addr;
 984
 985         if (!l_map) return -1;
 986         if (!r_map) return 1;
 987
 988         if (l_map->maj > r_map->maj) return -1;
 989         if (l_map->maj < r_map->maj) return 1;
 990
 991         if (l_map->min > r_map->min) return -1;
 992         if (l_map->min < r_map->min) return 1;
 993
 994         if (l_map->ino > r_map->ino) return -1;
 995         if (l_map->ino < r_map->ino) return 1;
 996
 997         if (l_map->ino_generation > r_map->ino_generation) return -1;
 998         if (l_map->ino_generation < r_map->ino_generation) return 1;
 999
1000         /*
1001          * Addresses with no major/minor numbers are assumed to be
1002          * anonymous in userspace.  Sort those on pid then address.
1003          *
1004          * The kernel and non-zero major/minor mapped areas are
1005          * assumed to be unity mapped.  Sort those on address.
1006          */
1007
1008         if ((left->cpumode != PERF_RECORD_MISC_KERNEL) &&
1009             (!(l_map->flags & MAP_SHARED)) &&
1010             !l_map->maj && !l_map->min && !l_map->ino &&
1011             !l_map->ino_generation) {
1012                 /* userspace anonymous */
1013
1014                 if (left->thread->pid_ > right->thread->pid_) return -1;
1015                 if (left->thread->pid_ < right->thread->pid_) return 1;
1016         }
1017
1018 addr:
1019         /* al_addr does all the right addr - start + offset calculations */
1020         l = cl_address(left->mem_info->daddr.al_addr);
1021         r = cl_address(right->mem_info->daddr.al_addr);
1022
1023         if (l > r) return -1;
1024         if (l < r) return 1;
1025
1026         return 0;
1027 }
1028
1029 static int hist_entry__dcacheline_snprintf(struct hist_entry *he, char *bf,
1030                                           size_t size, unsigned int width)
1031 {
1032
1033         uint64_t addr = 0;
1034         struct map *map = NULL;
1035         struct symbol *sym = NULL;
1036         char level = he->level;
1037
1038         if (he->mem_info) {
1039                 addr = cl_address(he->mem_info->daddr.al_addr);
1040                 map = he->mem_info->daddr.map;
1041                 sym = he->mem_info->daddr.sym;
1042
1043                 /* print [s] for shared data mmaps */
1044                 if ((he->cpumode != PERF_RECORD_MISC_KERNEL) &&
1045                      map && (map->type == MAP__VARIABLE) &&
1046                     (map->flags & MAP_SHARED) &&
1047                     (map->maj || map->min || map->ino ||
1048                      map->ino_generation))
1049                         level = 's';
1050                 else if (!map)
1051                         level = 'X';
1052         }
1053         return _hist_entry__sym_snprintf(map, sym, addr, level, bf, size,
1054                                          width);
1055 }
1056
1057 struct sort_entry sort_mispredict = {
1058         .se_header      = "Branch Mispredicted",
1059         .se_cmp         = sort__mispredict_cmp,
1060         .se_snprintf    = hist_entry__mispredict_snprintf,
1061         .se_width_idx   = HISTC_MISPREDICT,
1062 };
1063
1064 static u64 he_weight(struct hist_entry *he)
1065 {
1066         return he->stat.nr_events ? he->stat.weight / he->stat.nr_events : 0;
1067 }
1068
1069 static int64_t
1070 sort__local_weight_cmp(struct hist_entry *left, struct hist_entry *right)
1071 {
1072         return he_weight(left) - he_weight(right);
1073 }
1074
1075 static int hist_entry__local_weight_snprintf(struct hist_entry *he, char *bf,
1076                                     size_t size, unsigned int width)
1077 {
1078         return repsep_snprintf(bf, size, "%-*llu", width, he_weight(he));
1079 }
1080
1081 struct sort_entry sort_local_weight = {
1082         .se_header      = "Local Weight",
1083         .se_cmp         = sort__local_weight_cmp,
1084         .se_snprintf    = hist_entry__local_weight_snprintf,
1085         .se_width_idx   = HISTC_LOCAL_WEIGHT,
1086 };
1087
1088 static int64_t
1089 sort__global_weight_cmp(struct hist_entry *left, struct hist_entry *right)
1090 {
1091         return left->stat.weight - right->stat.weight;
1092 }
1093
1094 static int hist_entry__global_weight_snprintf(struct hist_entry *he, char *bf,
1095                                               size_t size, unsigned int width)
1096 {
1097         return repsep_snprintf(bf, size, "%-*llu", width, he->stat.weight);
1098 }
1099
1100 struct sort_entry sort_global_weight = {
1101         .se_header      = "Weight",
1102         .se_cmp         = sort__global_weight_cmp,
1103         .se_snprintf    = hist_entry__global_weight_snprintf,
1104         .se_width_idx   = HISTC_GLOBAL_WEIGHT,
1105 };
1106
1107 struct sort_entry sort_mem_daddr_sym = {
1108         .se_header      = "Data Symbol",
1109         .se_cmp         = sort__daddr_cmp,
1110         .se_snprintf    = hist_entry__daddr_snprintf,
1111         .se_width_idx   = HISTC_MEM_DADDR_SYMBOL,
1112 };
1113
1114 struct sort_entry sort_mem_iaddr_sym = {
1115         .se_header      = "Code Symbol",
1116         .se_cmp         = sort__iaddr_cmp,
1117         .se_snprintf    = hist_entry__iaddr_snprintf,
1118         .se_width_idx   = HISTC_MEM_IADDR_SYMBOL,
1119 };
1120
1121 struct sort_entry sort_mem_daddr_dso = {
1122         .se_header      = "Data Object",
1123         .se_cmp         = sort__dso_daddr_cmp,
1124         .se_snprintf    = hist_entry__dso_daddr_snprintf,
1125         .se_width_idx   = HISTC_MEM_DADDR_SYMBOL,
1126 };
1127
1128 struct sort_entry sort_mem_locked = {
1129         .se_header      = "Locked",
1130         .se_cmp         = sort__locked_cmp,
1131         .se_snprintf    = hist_entry__locked_snprintf,
1132         .se_width_idx   = HISTC_MEM_LOCKED,
1133 };
1134
1135 struct sort_entry sort_mem_tlb = {
1136         .se_header      = "TLB access",
1137         .se_cmp         = sort__tlb_cmp,
1138         .se_snprintf    = hist_entry__tlb_snprintf,
1139         .se_width_idx   = HISTC_MEM_TLB,
1140 };
1141
1142 struct sort_entry sort_mem_lvl = {
1143         .se_header      = "Memory access",
1144         .se_cmp         = sort__lvl_cmp,
1145         .se_snprintf    = hist_entry__lvl_snprintf,
1146         .se_width_idx   = HISTC_MEM_LVL,
1147 };
1148
1149 struct sort_entry sort_mem_snoop = {
1150         .se_header      = "Snoop",
1151         .se_cmp         = sort__snoop_cmp,
1152         .se_snprintf    = hist_entry__snoop_snprintf,
1153         .se_width_idx   = HISTC_MEM_SNOOP,
1154 };
1155
1156 struct sort_entry sort_mem_dcacheline = {
1157         .se_header      = "Data Cacheline",
1158         .se_cmp         = sort__dcacheline_cmp,
1159         .se_snprintf    = hist_entry__dcacheline_snprintf,
1160         .se_width_idx   = HISTC_MEM_DCACHELINE,
1161 };
1162
1163 static int64_t
1164 sort__abort_cmp(struct hist_entry *left, struct hist_entry *right)
1165 {
1166         if (!left->branch_info || !right->branch_info)
1167                 return cmp_null(left->branch_info, right->branch_info);
1168
1169         return left->branch_info->flags.abort !=
1170                 right->branch_info->flags.abort;
1171 }
1172
1173 static int hist_entry__abort_snprintf(struct hist_entry *he, char *bf,
1174                                     size_t size, unsigned int width)
1175 {
1176         static const char *out = "N/A";
1177
1178         if (he->branch_info) {
1179                 if (he->branch_info->flags.abort)
1180                         out = "A";
1181                 else
1182                         out = ".";
1183         }
1184
1185         return repsep_snprintf(bf, size, "%-*s", width, out);
1186 }
1187
1188 struct sort_entry sort_abort = {
1189         .se_header      = "Transaction abort",
1190         .se_cmp         = sort__abort_cmp,
1191         .se_snprintf    = hist_entry__abort_snprintf,
1192         .se_width_idx   = HISTC_ABORT,
1193 };
1194
1195 static int64_t
1196 sort__in_tx_cmp(struct hist_entry *left, struct hist_entry *right)
1197 {
1198         if (!left->branch_info || !right->branch_info)
1199                 return cmp_null(left->branch_info, right->branch_info);
1200
1201         return left->branch_info->flags.in_tx !=
1202                 right->branch_info->flags.in_tx;
1203 }
1204
1205 static int hist_entry__in_tx_snprintf(struct hist_entry *he, char *bf,
1206                                     size_t size, unsigned int width)
1207 {
1208         static const char *out = "N/A";
1209
1210         if (he->branch_info) {
1211                 if (he->branch_info->flags.in_tx)
1212                         out = "T";
1213                 else
1214                         out = ".";
1215         }
1216
1217         return repsep_snprintf(bf, size, "%-*s", width, out);
1218 }
1219
1220 struct sort_entry sort_in_tx = {
1221         .se_header      = "Branch in transaction",
1222         .se_cmp         = sort__in_tx_cmp,
1223         .se_snprintf    = hist_entry__in_tx_snprintf,
1224         .se_width_idx   = HISTC_IN_TX,
1225 };
1226
1227 static int64_t
1228 sort__transaction_cmp(struct hist_entry *left, struct hist_entry *right)
1229 {
1230         return left->transaction - right->transaction;
1231 }
1232
1233 static inline char *add_str(char *p, const char *str)
1234 {
1235         strcpy(p, str);
1236         return p + strlen(str);
1237 }
1238
1239 static struct txbit {
1240         unsigned flag;
1241         const char *name;
1242         int skip_for_len;
1243 } txbits[] = {
1244         { PERF_TXN_ELISION,        "EL ",        0 },
1245         { PERF_TXN_TRANSACTION,    "TX ",        1 },
1246         { PERF_TXN_SYNC,           "SYNC ",      1 },
1247         { PERF_TXN_ASYNC,          "ASYNC ",     0 },
1248         { PERF_TXN_RETRY,          "RETRY ",     0 },
1249         { PERF_TXN_CONFLICT,       "CON ",       0 },
1250         { PERF_TXN_CAPACITY_WRITE, "CAP-WRITE ", 1 },
1251         { PERF_TXN_CAPACITY_READ,  "CAP-READ ",  0 },
1252         { 0, NULL, 0 }
1253 };
1254
1255 int hist_entry__transaction_len(void)
1256 {
1257         int i;
1258         int len = 0;
1259
1260         for (i = 0; txbits[i].name; i++) {
1261                 if (!txbits[i].skip_for_len)
1262                         len += strlen(txbits[i].name);
1263         }
1264         len += 4; /* :XX<space> */
1265         return len;
1266 }
1267
1268 static int hist_entry__transaction_snprintf(struct hist_entry *he, char *bf,
1269                                             size_t size, unsigned int width)
1270 {
1271         u64 t = he->transaction;
1272         char buf[128];
1273         char *p = buf;
1274         int i;
1275
1276         buf[0] = 0;
1277         for (i = 0; txbits[i].name; i++)
1278                 if (txbits[i].flag & t)
1279                         p = add_str(p, txbits[i].name);
1280         if (t && !(t & (PERF_TXN_SYNC|PERF_TXN_ASYNC)))
1281                 p = add_str(p, "NEITHER ");
1282         if (t & PERF_TXN_ABORT_MASK) {
1283                 sprintf(p, ":%" PRIx64,
1284                         (t & PERF_TXN_ABORT_MASK) >>
1285                         PERF_TXN_ABORT_SHIFT);
1286                 p += strlen(p);
1287         }
1288
1289         return repsep_snprintf(bf, size, "%-*s", width, buf);
1290 }
1291
1292 struct sort_entry sort_transaction = {
1293         .se_header      = "Transaction                ",
1294         .se_cmp         = sort__transaction_cmp,
1295         .se_snprintf    = hist_entry__transaction_snprintf,
1296         .se_width_idx   = HISTC_TRANSACTION,
1297 };
1298
1299 struct sort_dimension {
1300         const char              *name;
1301         struct sort_entry       *entry;
1302         int                     taken;
1303 };
1304
1305 #define DIM(d, n, func) [d] = { .name = n, .entry = &(func) }
1306
1307 static struct sort_dimension common_sort_dimensions[] = {
1308         DIM(SORT_PID, "pid", sort_thread),
1309         DIM(SORT_COMM, "comm", sort_comm),
1310         DIM(SORT_DSO, "dso", sort_dso),
1311         DIM(SORT_SYM, "symbol", sort_sym),
1312         DIM(SORT_PARENT, "parent", sort_parent),
1313         DIM(SORT_CPU, "cpu", sort_cpu),
1314         DIM(SORT_SOCKET, "socket", sort_socket),
1315         DIM(SORT_SRCLINE, "srcline", sort_srcline),
1316         DIM(SORT_SRCFILE, "srcfile", sort_srcfile),
1317         DIM(SORT_LOCAL_WEIGHT, "local_weight", sort_local_weight),
1318         DIM(SORT_GLOBAL_WEIGHT, "weight", sort_global_weight),
1319         DIM(SORT_TRANSACTION, "transaction", sort_transaction),
1320 };
1321
1322 #undef DIM
1323
1324 #define DIM(d, n, func) [d - __SORT_BRANCH_STACK] = { .name = n, .entry = &(func) }
1325
1326 static struct sort_dimension bstack_sort_dimensions[] = {
1327         DIM(SORT_DSO_FROM, "dso_from", sort_dso_from),
1328         DIM(SORT_DSO_TO, "dso_to", sort_dso_to),
1329         DIM(SORT_SYM_FROM, "symbol_from", sort_sym_from),
1330         DIM(SORT_SYM_TO, "symbol_to", sort_sym_to),
1331         DIM(SORT_MISPREDICT, "mispredict", sort_mispredict),
1332         DIM(SORT_IN_TX, "in_tx", sort_in_tx),
1333         DIM(SORT_ABORT, "abort", sort_abort),
1334         DIM(SORT_CYCLES, "cycles", sort_cycles),
1335 };
1336
1337 #undef DIM
1338
1339 #define DIM(d, n, func) [d - __SORT_MEMORY_MODE] = { .name = n, .entry = &(func) }
1340
1341 static struct sort_dimension memory_sort_dimensions[] = {
1342         DIM(SORT_MEM_DADDR_SYMBOL, "symbol_daddr", sort_mem_daddr_sym),
1343         DIM(SORT_MEM_IADDR_SYMBOL, "symbol_iaddr", sort_mem_iaddr_sym),
1344         DIM(SORT_MEM_DADDR_DSO, "dso_daddr", sort_mem_daddr_dso),
1345         DIM(SORT_MEM_LOCKED, "locked", sort_mem_locked),
1346         DIM(SORT_MEM_TLB, "tlb", sort_mem_tlb),
1347         DIM(SORT_MEM_LVL, "mem", sort_mem_lvl),
1348         DIM(SORT_MEM_SNOOP, "snoop", sort_mem_snoop),
1349         DIM(SORT_MEM_DCACHELINE, "dcacheline", sort_mem_dcacheline),
1350 };
1351
1352 #undef DIM
1353
1354 struct hpp_dimension {
1355         const char              *name;
1356         struct perf_hpp_fmt     *fmt;
1357         int                     taken;
1358 };
1359
1360 #define DIM(d, n) { .name = n, .fmt = &perf_hpp__format[d], }
1361
1362 static struct hpp_dimension hpp_sort_dimensions[] = {
1363         DIM(PERF_HPP__OVERHEAD, "overhead"),
1364         DIM(PERF_HPP__OVERHEAD_SYS, "overhead_sys"),
1365         DIM(PERF_HPP__OVERHEAD_US, "overhead_us"),
1366         DIM(PERF_HPP__OVERHEAD_GUEST_SYS, "overhead_guest_sys"),
1367         DIM(PERF_HPP__OVERHEAD_GUEST_US, "overhead_guest_us"),
1368         DIM(PERF_HPP__OVERHEAD_ACC, "overhead_children"),
1369         DIM(PERF_HPP__SAMPLES, "sample"),
1370         DIM(PERF_HPP__PERIOD, "period"),
1371 };
1372
1373 #undef DIM
1374
1375 struct hpp_sort_entry {
1376         struct perf_hpp_fmt hpp;
1377         struct sort_entry *se;
1378 };
1379
1380 bool perf_hpp__same_sort_entry(struct perf_hpp_fmt *a, struct perf_hpp_fmt *b)
1381 {
1382         struct hpp_sort_entry *hse_a;
1383         struct hpp_sort_entry *hse_b;
1384
1385         if (!perf_hpp__is_sort_entry(a) || !perf_hpp__is_sort_entry(b))
1386                 return false;
1387
1388         hse_a = container_of(a, struct hpp_sort_entry, hpp);
1389         hse_b = container_of(b, struct hpp_sort_entry, hpp);
1390
1391         return hse_a->se == hse_b->se;
1392 }
1393
1394 void perf_hpp__reset_sort_width(struct perf_hpp_fmt *fmt, struct hists *hists)
1395 {
1396         struct hpp_sort_entry *hse;
1397
1398         if (!perf_hpp__is_sort_entry(fmt))
1399                 return;
1400
1401         hse = container_of(fmt, struct hpp_sort_entry, hpp);
1402         hists__new_col_len(hists, hse->se->se_width_idx, strlen(fmt->name));
1403 }
1404
1405 static int __sort__hpp_header(struct perf_hpp_fmt *fmt, struct perf_hpp *hpp,
1406                               struct perf_evsel *evsel)
1407 {
1408         struct hpp_sort_entry *hse;
1409         size_t len = fmt->user_len;
1410
1411         hse = container_of(fmt, struct hpp_sort_entry, hpp);
1412
1413         if (!len)
1414                 len = hists__col_len(evsel__hists(evsel), hse->se->se_width_idx);
1415
1416         return scnprintf(hpp->buf, hpp->size, "%-*.*s", len, len, fmt->name);
1417 }
1418
1419 static int __sort__hpp_width(struct perf_hpp_fmt *fmt,
1420                              struct perf_hpp *hpp __maybe_unused,
1421                              struct perf_evsel *evsel)
1422 {
1423         struct hpp_sort_entry *hse;
1424         size_t len = fmt->user_len;
1425
1426         hse = container_of(fmt, struct hpp_sort_entry, hpp);
1427
1428         if (!len)
1429                 len = hists__col_len(evsel__hists(evsel), hse->se->se_width_idx);
1430
1431         return len;
1432 }
1433
1434 static int __sort__hpp_entry(struct perf_hpp_fmt *fmt, struct perf_hpp *hpp,
1435                              struct hist_entry *he)
1436 {
1437         struct hpp_sort_entry *hse;
1438         size_t len = fmt->user_len;
1439
1440         hse = container_of(fmt, struct hpp_sort_entry, hpp);
1441
1442         if (!len)
1443                 len = hists__col_len(he->hists, hse->se->se_width_idx);
1444
1445         return hse->se->se_snprintf(he, hpp->buf, hpp->size, len);
1446 }
1447
1448 static int64_t __sort__hpp_cmp(struct perf_hpp_fmt *fmt,
1449                                struct hist_entry *a, struct hist_entry *b)
1450 {
1451         struct hpp_sort_entry *hse;
1452
1453         hse = container_of(fmt, struct hpp_sort_entry, hpp);
1454         return hse->se->se_cmp(a, b);
1455 }
1456
1457 static int64_t __sort__hpp_collapse(struct perf_hpp_fmt *fmt,
1458                                     struct hist_entry *a, struct hist_entry *b)
1459 {
1460         struct hpp_sort_entry *hse;
1461         int64_t (*collapse_fn)(struct hist_entry *, struct hist_entry *);
1462
1463         hse = container_of(fmt, struct hpp_sort_entry, hpp);
1464         collapse_fn = hse->se->se_collapse ?: hse->se->se_cmp;
1465         return collapse_fn(a, b);
1466 }
1467
1468 static int64_t __sort__hpp_sort(struct perf_hpp_fmt *fmt,
1469                                 struct hist_entry *a, struct hist_entry *b)
1470 {
1471         struct hpp_sort_entry *hse;
1472         int64_t (*sort_fn)(struct hist_entry *, struct hist_entry *);
1473
1474         hse = container_of(fmt, struct hpp_sort_entry, hpp);
1475         sort_fn = hse->se->se_sort ?: hse->se->se_cmp;
1476         return sort_fn(a, b);
1477 }
1478
1479 static struct hpp_sort_entry *
1480 __sort_dimension__alloc_hpp(struct sort_dimension *sd)
1481 {
1482         struct hpp_sort_entry *hse;
1483
1484         hse = malloc(sizeof(*hse));
1485         if (hse == NULL) {
1486                 pr_err("Memory allocation failed\n");
1487                 return NULL;
1488         }
1489
1490         hse->se = sd->entry;
1491         hse->hpp.name = sd->entry->se_header;
1492         hse->hpp.header = __sort__hpp_header;
1493         hse->hpp.width = __sort__hpp_width;
1494         hse->hpp.entry = __sort__hpp_entry;
1495         hse->hpp.color = NULL;
1496
1497         hse->hpp.cmp = __sort__hpp_cmp;
1498         hse->hpp.collapse = __sort__hpp_collapse;
1499         hse->hpp.sort = __sort__hpp_sort;
1500
1501         INIT_LIST_HEAD(&hse->hpp.list);
1502         INIT_LIST_HEAD(&hse->hpp.sort_list);
1503         hse->hpp.elide = false;
1504         hse->hpp.len = 0;
1505         hse->hpp.user_len = 0;
1506
1507         return hse;
1508 }
1509
1510 bool perf_hpp__is_sort_entry(struct perf_hpp_fmt *format)
1511 {
1512         return format->header == __sort__hpp_header;
1513 }
1514
1515 static int __sort_dimension__add_hpp_sort(struct sort_dimension *sd)
1516 {
1517         struct hpp_sort_entry *hse = __sort_dimension__alloc_hpp(sd);
1518
1519         if (hse == NULL)
1520                 return -1;
1521
1522         perf_hpp__register_sort_field(&hse->hpp);
1523         return 0;
1524 }
1525
1526 static int __sort_dimension__add_hpp_output(struct sort_dimension *sd)
1527 {
1528         struct hpp_sort_entry *hse = __sort_dimension__alloc_hpp(sd);
1529
1530         if (hse == NULL)
1531                 return -1;
1532
1533         perf_hpp__column_register(&hse->hpp);
1534         return 0;
1535 }
1536
1537 static int __sort_dimension__add(struct sort_dimension *sd)
1538 {
1539         if (sd->taken)
1540                 return 0;
1541
1542         if (__sort_dimension__add_hpp_sort(sd) < 0)
1543                 return -1;
1544
1545         if (sd->entry->se_collapse)
1546                 sort__need_collapse = 1;
1547
1548         sd->taken = 1;
1549
1550         return 0;
1551 }
1552
1553 static int __hpp_dimension__add(struct hpp_dimension *hd)
1554 {
1555         if (!hd->taken) {
1556                 hd->taken = 1;
1557
1558                 perf_hpp__register_sort_field(hd->fmt);
1559         }
1560         return 0;
1561 }
1562
1563 static int __sort_dimension__add_output(struct sort_dimension *sd)
1564 {
1565         if (sd->taken)
1566                 return 0;
1567
1568         if (__sort_dimension__add_hpp_output(sd) < 0)
1569                 return -1;
1570
1571         sd->taken = 1;
1572         return 0;
1573 }
1574
1575 static int __hpp_dimension__add_output(struct hpp_dimension *hd)
1576 {
1577         if (!hd->taken) {
1578                 hd->taken = 1;
1579
1580                 perf_hpp__column_register(hd->fmt);
1581         }
1582         return 0;
1583 }
1584
1585 int hpp_dimension__add_output(unsigned col)
1586 {
1587         BUG_ON(col >= PERF_HPP__MAX_INDEX);
1588         return __hpp_dimension__add_output(&hpp_sort_dimensions[col]);
1589 }
1590
1591 int sort_dimension__add(const char *tok)
1592 {
1593         unsigned int i;
1594
1595         for (i = 0; i < ARRAY_SIZE(common_sort_dimensions); i++) {
1596                 struct sort_dimension *sd = &common_sort_dimensions[i];
1597
1598                 if (strncasecmp(tok, sd->name, strlen(tok)))
1599                         continue;
1600
1601                 if (sd->entry == &sort_parent) {
1602                         int ret = regcomp(&parent_regex, parent_pattern, REG_EXTENDED);
1603                         if (ret) {
1604                                 char err[BUFSIZ];
1605
1606                                 regerror(ret, &parent_regex, err, sizeof(err));
1607                                 pr_err("Invalid regex: %s\n%s", parent_pattern, err);
1608                                 return -EINVAL;
1609                         }
1610                         sort__has_parent = 1;
1611                 } else if (sd->entry == &sort_sym) {
1612                         sort__has_sym = 1;
1613                         /*
1614                          * perf diff displays the performance difference amongst
1615                          * two or more perf.data files. Those files could come
1616                          * from different binaries. So we should not compare
1617                          * their ips, but the name of symbol.
1618                          */
1619                         if (sort__mode == SORT_MODE__DIFF)
1620                                 sd->entry->se_collapse = sort__sym_sort;
1621
1622                 } else if (sd->entry == &sort_dso) {
1623                         sort__has_dso = 1;
1624                 } else if (sd->entry == &sort_socket) {
1625                         sort__has_socket = 1;
1626                 }
1627
1628                 return __sort_dimension__add(sd);
1629         }
1630
1631         for (i = 0; i < ARRAY_SIZE(hpp_sort_dimensions); i++) {
1632                 struct hpp_dimension *hd = &hpp_sort_dimensions[i];
1633
1634                 if (strncasecmp(tok, hd->name, strlen(tok)))
1635                         continue;
1636
1637                 return __hpp_dimension__add(hd);
1638         }
1639
1640         for (i = 0; i < ARRAY_SIZE(bstack_sort_dimensions); i++) {
1641                 struct sort_dimension *sd = &bstack_sort_dimensions[i];
1642
1643                 if (strncasecmp(tok, sd->name, strlen(tok)))
1644                         continue;
1645
1646                 if (sort__mode != SORT_MODE__BRANCH)
1647                         return -EINVAL;
1648
1649                 if (sd->entry == &sort_sym_from || sd->entry == &sort_sym_to)
1650                         sort__has_sym = 1;
1651
1652                 __sort_dimension__add(sd);
1653                 return 0;
1654         }
1655
1656         for (i = 0; i < ARRAY_SIZE(memory_sort_dimensions); i++) {
1657                 struct sort_dimension *sd = &memory_sort_dimensions[i];
1658
1659                 if (strncasecmp(tok, sd->name, strlen(tok)))
1660                         continue;
1661
1662                 if (sort__mode != SORT_MODE__MEMORY)
1663                         return -EINVAL;
1664
1665                 if (sd->entry == &sort_mem_daddr_sym)
1666                         sort__has_sym = 1;
1667
1668                 __sort_dimension__add(sd);
1669                 return 0;
1670         }
1671
1672         return -ESRCH;
1673 }
1674
1675 static const char *get_default_sort_order(void)
1676 {
1677         const char *default_sort_orders[] = {
1678                 default_sort_order,
1679                 default_branch_sort_order,
1680                 default_mem_sort_order,
1681                 default_top_sort_order,
1682                 default_diff_sort_order,
1683         };
1684
1685         BUG_ON(sort__mode >= ARRAY_SIZE(default_sort_orders));
1686
1687         return default_sort_orders[sort__mode];
1688 }
1689
1690 static int setup_sort_order(void)
1691 {
1692         char *new_sort_order;
1693
1694         /*
1695          * Append '+'-prefixed sort order to the default sort
1696          * order string.
1697          */
1698         if (!sort_order || is_strict_order(sort_order))
1699                 return 0;
1700
1701         if (sort_order[1] == '\0') {
1702                 error("Invalid --sort key: `+'");
1703                 return -EINVAL;
1704         }
1705
1706         /*
1707          * We allocate new sort_order string, but we never free it,
1708          * because it's checked over the rest of the code.
1709          */
1710         if (asprintf(&new_sort_order, "%s,%s",
1711                      get_default_sort_order(), sort_order + 1) < 0) {
1712                 error("Not enough memory to set up --sort");
1713                 return -ENOMEM;
1714         }
1715
1716         sort_order = new_sort_order;
1717         return 0;
1718 }
1719
1720 static int __setup_sorting(void)
1721 {
1722         char *tmp, *tok, *str;
1723         const char *sort_keys;
1724         int ret = 0;
1725
1726         ret = setup_sort_order();
1727         if (ret)
1728                 return ret;
1729
1730         sort_keys = sort_order;
1731         if (sort_keys == NULL) {
1732                 if (is_strict_order(field_order)) {
1733                         /*
1734                          * If user specified field order but no sort order,
1735                          * we'll honor it and not add default sort orders.
1736                          */
1737                         return 0;
1738                 }
1739
1740                 sort_keys = get_default_sort_order();
1741         }
1742
1743         str = strdup(sort_keys);
1744         if (str == NULL) {
1745                 error("Not enough memory to setup sort keys");
1746                 return -ENOMEM;
1747         }
1748
1749         for (tok = strtok_r(str, ", ", &tmp);
1750                         tok; tok = strtok_r(NULL, ", ", &tmp)) {
1751                 ret = sort_dimension__add(tok);
1752                 if (ret == -EINVAL) {
1753                         error("Invalid --sort key: `%s'", tok);
1754                         break;
1755                 } else if (ret == -ESRCH) {
1756                         error("Unknown --sort key: `%s'", tok);
1757                         break;
1758                 }
1759         }
1760
1761         free(str);
1762         return ret;
1763 }
1764
1765 void perf_hpp__set_elide(int idx, bool elide)
1766 {
1767         struct perf_hpp_fmt *fmt;
1768         struct hpp_sort_entry *hse;
1769
1770         perf_hpp__for_each_format(fmt) {
1771                 if (!perf_hpp__is_sort_entry(fmt))
1772                         continue;
1773
1774                 hse = container_of(fmt, struct hpp_sort_entry, hpp);
1775                 if (hse->se->se_width_idx == idx) {
1776                         fmt->elide = elide;
1777                         break;
1778                 }
1779         }
1780 }
1781
1782 static bool __get_elide(struct strlist *list, const char *list_name, FILE *fp)
1783 {
1784         if (list && strlist__nr_entries(list) == 1) {
1785                 if (fp != NULL)
1786                         fprintf(fp, "# %s: %s\n", list_name,
1787                                 strlist__entry(list, 0)->s);
1788                 return true;
1789         }
1790         return false;
1791 }
1792
1793 static bool get_elide(int idx, FILE *output)
1794 {
1795         switch (idx) {
1796         case HISTC_SYMBOL:
1797                 return __get_elide(symbol_conf.sym_list, "symbol", output);
1798         case HISTC_DSO:
1799                 return __get_elide(symbol_conf.dso_list, "dso", output);
1800         case HISTC_COMM:
1801                 return __get_elide(symbol_conf.comm_list, "comm", output);
1802         default:
1803                 break;
1804         }
1805
1806         if (sort__mode != SORT_MODE__BRANCH)
1807                 return false;
1808
1809         switch (idx) {
1810         case HISTC_SYMBOL_FROM:
1811                 return __get_elide(symbol_conf.sym_from_list, "sym_from", output);
1812         case HISTC_SYMBOL_TO:
1813                 return __get_elide(symbol_conf.sym_to_list, "sym_to", output);
1814         case HISTC_DSO_FROM:
1815                 return __get_elide(symbol_conf.dso_from_list, "dso_from", output);
1816         case HISTC_DSO_TO:
1817                 return __get_elide(symbol_conf.dso_to_list, "dso_to", output);
1818         default:
1819                 break;
1820         }
1821
1822         return false;
1823 }
1824
1825 void sort__setup_elide(FILE *output)
1826 {
1827         struct perf_hpp_fmt *fmt;
1828         struct hpp_sort_entry *hse;
1829
1830         perf_hpp__for_each_format(fmt) {
1831                 if (!perf_hpp__is_sort_entry(fmt))
1832                         continue;
1833
1834                 hse = container_of(fmt, struct hpp_sort_entry, hpp);
1835                 fmt->elide = get_elide(hse->se->se_width_idx, output);
1836         }
1837
1838         /*
1839          * It makes no sense to elide all of sort entries.
1840          * Just revert them to show up again.
1841          */
1842         perf_hpp__for_each_format(fmt) {
1843                 if (!perf_hpp__is_sort_entry(fmt))
1844                         continue;
1845
1846                 if (!fmt->elide)
1847                         return;
1848         }
1849
1850         perf_hpp__for_each_format(fmt) {
1851                 if (!perf_hpp__is_sort_entry(fmt))
1852                         continue;
1853
1854                 fmt->elide = false;
1855         }
1856 }
1857
1858 static int output_field_add(char *tok)
1859 {
1860         unsigned int i;
1861
1862         for (i = 0; i < ARRAY_SIZE(common_sort_dimensions); i++) {
1863                 struct sort_dimension *sd = &common_sort_dimensions[i];
1864
1865                 if (strncasecmp(tok, sd->name, strlen(tok)))
1866                         continue;
1867
1868                 return __sort_dimension__add_output(sd);
1869         }
1870
1871         for (i = 0; i < ARRAY_SIZE(hpp_sort_dimensions); i++) {
1872                 struct hpp_dimension *hd = &hpp_sort_dimensions[i];
1873
1874                 if (strncasecmp(tok, hd->name, strlen(tok)))
1875                         continue;
1876
1877                 return __hpp_dimension__add_output(hd);
1878         }
1879
1880         for (i = 0; i < ARRAY_SIZE(bstack_sort_dimensions); i++) {
1881                 struct sort_dimension *sd = &bstack_sort_dimensions[i];
1882
1883                 if (strncasecmp(tok, sd->name, strlen(tok)))
1884                         continue;
1885
1886                 return __sort_dimension__add_output(sd);
1887         }
1888
1889         for (i = 0; i < ARRAY_SIZE(memory_sort_dimensions); i++) {
1890                 struct sort_dimension *sd = &memory_sort_dimensions[i];
1891
1892                 if (strncasecmp(tok, sd->name, strlen(tok)))
1893                         continue;
1894
1895                 return __sort_dimension__add_output(sd);
1896         }
1897
1898         return -ESRCH;
1899 }
1900
1901 static void reset_dimensions(void)
1902 {
1903         unsigned int i;
1904
1905         for (i = 0; i < ARRAY_SIZE(common_sort_dimensions); i++)
1906                 common_sort_dimensions[i].taken = 0;
1907
1908         for (i = 0; i < ARRAY_SIZE(hpp_sort_dimensions); i++)
1909                 hpp_sort_dimensions[i].taken = 0;
1910
1911         for (i = 0; i < ARRAY_SIZE(bstack_sort_dimensions); i++)
1912                 bstack_sort_dimensions[i].taken = 0;
1913
1914         for (i = 0; i < ARRAY_SIZE(memory_sort_dimensions); i++)
1915                 memory_sort_dimensions[i].taken = 0;
1916 }
1917
1918 bool is_strict_order(const char *order)
1919 {
1920         return order && (*order != '+');
1921 }
1922
1923 static int __setup_output_field(void)
1924 {
1925         char *tmp, *tok, *str, *strp;
1926         int ret = -EINVAL;
1927
1928         if (field_order == NULL)
1929                 return 0;
1930
1931         strp = str = strdup(field_order);
1932         if (str == NULL) {
1933                 error("Not enough memory to setup output fields");
1934                 return -ENOMEM;
1935         }
1936
1937         if (!is_strict_order(field_order))
1938                 strp++;
1939
1940         if (!strlen(strp)) {
1941                 error("Invalid --fields key: `+'");
1942                 goto out;
1943         }
1944
1945         for (tok = strtok_r(strp, ", ", &tmp);
1946                         tok; tok = strtok_r(NULL, ", ", &tmp)) {
1947                 ret = output_field_add(tok);
1948                 if (ret == -EINVAL) {
1949                         error("Invalid --fields key: `%s'", tok);
1950                         break;
1951                 } else if (ret == -ESRCH) {
1952                         error("Unknown --fields key: `%s'", tok);
1953                         break;
1954                 }
1955         }
1956
1957 out:
1958         free(str);
1959         return ret;
1960 }
1961
1962 int setup_sorting(void)
1963 {
1964         int err;
1965
1966         err = __setup_sorting();
1967         if (err < 0)
1968                 return err;
1969
1970         if (parent_pattern != default_parent_pattern) {
1971                 err = sort_dimension__add("parent");
1972                 if (err < 0)
1973                         return err;
1974         }
1975
1976         reset_dimensions();
1977
1978         /*
1979          * perf diff doesn't use default hpp output fields.
1980          */
1981         if (sort__mode != SORT_MODE__DIFF)
1982                 perf_hpp__init();
1983
1984         err = __setup_output_field();
1985         if (err < 0)
1986                 return err;
1987
1988         /* copy sort keys to output fields */
1989         perf_hpp__setup_output_field();
1990         /* and then copy output fields to sort keys */
1991         perf_hpp__append_sort_keys();
1992
1993         return 0;
1994 }
1995
1996 void reset_output_field(void)
1997 {
1998         sort__need_collapse = 0;
1999         sort__has_parent = 0;
2000         sort__has_sym = 0;
2001         sort__has_dso = 0;
2002
2003         field_order = NULL;
2004         sort_order = NULL;
2005
2006         reset_dimensions();
2007         perf_hpp__reset_output_field();
2008 }