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