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