tools/perf/util/sort.c

   1 #include "sort.h"
   2 #include "hist.h"
   3 #include "comm.h"
   4 #include "symbol.h"
   5 #include "evsel.h"
   6
   7 regex_t         parent_regex;
   8 const char      default_parent_pattern[] = "^sys_|^do_page_fault";
   9 const char      *parent_pattern = default_parent_pattern;
  10 const char      default_sort_order[] = "comm,dso,symbol";
  11 const char      *sort_order = default_sort_order;
  12 regex_t         ignore_callees_regex;
  13 int             have_ignore_callees = 0;
  14 int             sort__need_collapse = 0;
  15 int             sort__has_parent = 0;
  16 int             sort__has_sym = 0;
  17 int             sort__has_dso = 0;
  18 enum sort_mode  sort__mode = SORT_MODE__NORMAL;
  19
  20 enum sort_type  sort__first_dimension;
  21
  22 LIST_HEAD(hist_entry__sort_list);
  23
  24 static int repsep_snprintf(char *bf, size_t size, const char *fmt, ...)
  25 {
  26         int n;
  27         va_list ap;
  28
  29         va_start(ap, fmt);
  30         n = vsnprintf(bf, size, fmt, ap);
  31         if (symbol_conf.field_sep && n > 0) {
  32                 char *sep = bf;
  33
  34                 while (1) {
  35                         sep = strchr(sep, *symbol_conf.field_sep);
  36                         if (sep == NULL)
  37                                 break;
  38                         *sep = '.';
  39                 }
  40         }
  41         va_end(ap);
  42
  43         if (n >= (int)size)
  44                 return size - 1;
  45         return n;
  46 }
  47
  48 static int64_t cmp_null(const void *l, const void *r)
  49 {
  50         if (!l && !r)
  51                 return 0;
  52         else if (!l)
  53                 return -1;
  54         else
  55                 return 1;
  56 }
  57
  58 /* --sort pid */
  59
  60 static int64_t
  61 sort__thread_cmp(struct hist_entry *left, struct hist_entry *right)
  62 {
  63         return right->thread->tid - left->thread->tid;
  64 }
  65
  66 static int hist_entry__thread_snprintf(struct hist_entry *he, char *bf,
  67                                        size_t size, unsigned int width)
  68 {
  69         const char *comm = thread__comm_str(he->thread);
  70         return repsep_snprintf(bf, size, "%*s:%5d", width - 6,
  71                                comm ?: "", he->thread->tid);
  72 }
  73
  74 struct sort_entry sort_thread = {
  75         .se_header      = "Command:  Pid",
  76         .se_cmp         = sort__thread_cmp,
  77         .se_snprintf    = hist_entry__thread_snprintf,
  78         .se_width_idx   = HISTC_THREAD,
  79 };
  80
  81 /* --sort comm */
  82
  83 static int64_t
  84 sort__comm_cmp(struct hist_entry *left, struct hist_entry *right)
  85 {
  86         /* Compare the addr that should be unique among comm */
  87         return comm__str(right->comm) - comm__str(left->comm);
  88 }
  89
  90 static int64_t
  91 sort__comm_collapse(struct hist_entry *left, struct hist_entry *right)
  92 {
  93         /* Compare the addr that should be unique among comm */
  94         return comm__str(right->comm) - comm__str(left->comm);
  95 }
  96
  97 static int hist_entry__comm_snprintf(struct hist_entry *he, char *bf,
  98                                      size_t size, unsigned int width)
  99 {
 100         return repsep_snprintf(bf, size, "%*s", width, comm__str(he->comm));
 101 }
 102
 103 struct sort_entry sort_comm = {
 104         .se_header      = "Command",
 105         .se_cmp         = sort__comm_cmp,
 106         .se_collapse    = sort__comm_collapse,
 107         .se_snprintf    = hist_entry__comm_snprintf,
 108         .se_width_idx   = HISTC_COMM,
 109 };
 110
 111 /* --sort dso */
 112
 113 static int64_t _sort__dso_cmp(struct map *map_l, struct map *map_r)
 114 {
 115         struct dso *dso_l = map_l ? map_l->dso : NULL;
 116         struct dso *dso_r = map_r ? map_r->dso : NULL;
 117         const char *dso_name_l, *dso_name_r;
 118
 119         if (!dso_l || !dso_r)
 120                 return cmp_null(dso_l, dso_r);
 121
 122         if (verbose) {
 123                 dso_name_l = dso_l->long_name;
 124                 dso_name_r = dso_r->long_name;
 125         } else {
 126                 dso_name_l = dso_l->short_name;
 127                 dso_name_r = dso_r->short_name;
 128         }
 129
 130         return strcmp(dso_name_l, dso_name_r);
 131 }
 132
 133 static int64_t
 134 sort__dso_cmp(struct hist_entry *left, struct hist_entry *right)
 135 {
 136         return _sort__dso_cmp(left->ms.map, right->ms.map);
 137 }
 138
 139 static int _hist_entry__dso_snprintf(struct map *map, char *bf,
 140                                      size_t size, unsigned int width)
 141 {
 142         if (map && map->dso) {
 143                 const char *dso_name = !verbose ? map->dso->short_name :
 144                         map->dso->long_name;
 145                 return repsep_snprintf(bf, size, "%-*s", width, dso_name);
 146         }
 147
 148         return repsep_snprintf(bf, size, "%-*s", width, "[unknown]");
 149 }
 150
 151 static int hist_entry__dso_snprintf(struct hist_entry *he, char *bf,
 152                                     size_t size, unsigned int width)
 153 {
 154         return _hist_entry__dso_snprintf(he->ms.map, bf, size, width);
 155 }
 156
 157 struct sort_entry sort_dso = {
 158         .se_header      = "Shared Object",
 159         .se_cmp         = sort__dso_cmp,
 160         .se_snprintf    = hist_entry__dso_snprintf,
 161         .se_width_idx   = HISTC_DSO,
 162 };
 163
 164 /* --sort symbol */
 165
 166 static int64_t _sort__addr_cmp(u64 left_ip, u64 right_ip)
 167 {
 168         return (int64_t)(right_ip - left_ip);
 169 }
 170
 171 static int64_t _sort__sym_cmp(struct symbol *sym_l, struct symbol *sym_r)
 172 {
 173         u64 ip_l, ip_r;
 174
 175         if (!sym_l || !sym_r)
 176                 return cmp_null(sym_l, sym_r);
 177
 178         if (sym_l == sym_r)
 179                 return 0;
 180
 181         ip_l = sym_l->start;
 182         ip_r = sym_r->start;
 183
 184         return (int64_t)(ip_r - ip_l);
 185 }
 186
 187 static int64_t
 188 sort__sym_cmp(struct hist_entry *left, struct hist_entry *right)
 189 {
 190         int64_t ret;
 191
 192         if (!left->ms.sym && !right->ms.sym)
 193                 return _sort__addr_cmp(left->ip, right->ip);
 194
 195         /*
 196          * comparing symbol address alone is not enough since it's a
 197          * relative address within a dso.
 198          */
 199         if (!sort__has_dso) {
 200                 ret = sort__dso_cmp(left, right);
 201                 if (ret != 0)
 202                         return ret;
 203         }
 204
 205         return _sort__sym_cmp(left->ms.sym, right->ms.sym);
 206 }
 207
 208 static int _hist_entry__sym_snprintf(struct map *map, struct symbol *sym,
 209                                      u64 ip, char level, char *bf, size_t size,
 210                                      unsigned int width)
 211 {
 212         size_t ret = 0;
 213
 214         if (verbose) {
 215                 char o = map ? dso__symtab_origin(map->dso) : '!';
 216                 ret += repsep_snprintf(bf, size, "%-#*llx %c ",
 217                                        BITS_PER_LONG / 4 + 2, ip, o);
 218         }
 219
 220         ret += repsep_snprintf(bf + ret, size - ret, "[%c] ", level);
 221         if (sym && map) {
 222                 if (map->type == MAP__VARIABLE) {
 223                         ret += repsep_snprintf(bf + ret, size - ret, "%s", sym->name);
 224                         ret += repsep_snprintf(bf + ret, size - ret, "+0x%llx",
 225                                         ip - map->unmap_ip(map, sym->start));
 226                         ret += repsep_snprintf(bf + ret, size - ret, "%-*s",
 227                                        width - ret, "");
 228                 } else {
 229                         ret += repsep_snprintf(bf + ret, size - ret, "%-*s",
 230                                                width - ret,
 231                                                sym->name);
 232                 }
 233         } else {
 234                 size_t len = BITS_PER_LONG / 4;
 235                 ret += repsep_snprintf(bf + ret, size - ret, "%-#.*llx",
 236                                        len, ip);
 237                 ret += repsep_snprintf(bf + ret, size - ret, "%-*s",
 238                                        width - ret, "");
 239         }
 240
 241         return ret;
 242 }
 243
 244 static int hist_entry__sym_snprintf(struct hist_entry *he, char *bf,
 245                                     size_t size, unsigned int width)
 246 {
 247         return _hist_entry__sym_snprintf(he->ms.map, he->ms.sym, he->ip,
 248                                          he->level, bf, size, width);
 249 }
 250
 251 struct sort_entry sort_sym = {
 252         .se_header      = "Symbol",
 253         .se_cmp         = sort__sym_cmp,
 254         .se_snprintf    = hist_entry__sym_snprintf,
 255         .se_width_idx   = HISTC_SYMBOL,
 256 };
 257
 258 /* --sort srcline */
 259
 260 static int64_t
 261 sort__srcline_cmp(struct hist_entry *left, struct hist_entry *right)
 262 {
 263         if (!left->srcline) {
 264                 if (!left->ms.map)
 265                         left->srcline = SRCLINE_UNKNOWN;
 266                 else {
 267                         struct map *map = left->ms.map;
 268                         left->srcline = get_srcline(map->dso,
 269                                             map__rip_2objdump(map, left->ip));
 270                 }
 271         }
 272         if (!right->srcline) {
 273                 if (!right->ms.map)
 274                         right->srcline = SRCLINE_UNKNOWN;
 275                 else {
 276                         struct map *map = right->ms.map;
 277                         right->srcline = get_srcline(map->dso,
 278                                             map__rip_2objdump(map, right->ip));
 279                 }
 280         }
 281         return strcmp(left->srcline, right->srcline);
 282 }
 283
 284 static int hist_entry__srcline_snprintf(struct hist_entry *he, char *bf,
 285                                         size_t size,
 286                                         unsigned int width __maybe_unused)
 287 {
 288         return repsep_snprintf(bf, size, "%s", he->srcline);
 289 }
 290
 291 struct sort_entry sort_srcline = {
 292         .se_header      = "Source:Line",
 293         .se_cmp         = sort__srcline_cmp,
 294         .se_snprintf    = hist_entry__srcline_snprintf,
 295         .se_width_idx   = HISTC_SRCLINE,
 296 };
 297
 298 /* --sort parent */
 299
 300 static int64_t
 301 sort__parent_cmp(struct hist_entry *left, struct hist_entry *right)
 302 {
 303         struct symbol *sym_l = left->parent;
 304         struct symbol *sym_r = right->parent;
 305
 306         if (!sym_l || !sym_r)
 307                 return cmp_null(sym_l, sym_r);
 308
 309         return strcmp(sym_l->name, sym_r->name);
 310 }
 311
 312 static int hist_entry__parent_snprintf(struct hist_entry *he, char *bf,
 313                                        size_t size, unsigned int width)
 314 {
 315         return repsep_snprintf(bf, size, "%-*s", width,
 316                               he->parent ? he->parent->name : "[other]");
 317 }
 318
 319 struct sort_entry sort_parent = {
 320         .se_header      = "Parent symbol",
 321         .se_cmp         = sort__parent_cmp,
 322         .se_snprintf    = hist_entry__parent_snprintf,
 323         .se_width_idx   = HISTC_PARENT,
 324 };
 325
 326 /* --sort cpu */
 327
 328 static int64_t
 329 sort__cpu_cmp(struct hist_entry *left, struct hist_entry *right)
 330 {
 331         return right->cpu - left->cpu;
 332 }
 333
 334 static int hist_entry__cpu_snprintf(struct hist_entry *he, char *bf,
 335                                     size_t size, unsigned int width)
 336 {
 337         return repsep_snprintf(bf, size, "%*d", width, he->cpu);
 338 }
 339
 340 struct sort_entry sort_cpu = {
 341         .se_header      = "CPU",
 342         .se_cmp         = sort__cpu_cmp,
 343         .se_snprintf    = hist_entry__cpu_snprintf,
 344         .se_width_idx   = HISTC_CPU,
 345 };
 346
 347 /* sort keys for branch stacks */
 348
 349 static int64_t
 350 sort__dso_from_cmp(struct hist_entry *left, struct hist_entry *right)
 351 {
 352         return _sort__dso_cmp(left->branch_info->from.map,
 353                               right->branch_info->from.map);
 354 }
 355
 356 static int hist_entry__dso_from_snprintf(struct hist_entry *he, char *bf,
 357                                     size_t size, unsigned int width)
 358 {
 359         return _hist_entry__dso_snprintf(he->branch_info->from.map,
 360                                          bf, size, width);
 361 }
 362
 363 static int64_t
 364 sort__dso_to_cmp(struct hist_entry *left, struct hist_entry *right)
 365 {
 366         return _sort__dso_cmp(left->branch_info->to.map,
 367                               right->branch_info->to.map);
 368 }
 369
 370 static int hist_entry__dso_to_snprintf(struct hist_entry *he, char *bf,
 371                                        size_t size, unsigned int width)
 372 {
 373         return _hist_entry__dso_snprintf(he->branch_info->to.map,
 374                                          bf, size, width);
 375 }
 376
 377 static int64_t
 378 sort__sym_from_cmp(struct hist_entry *left, struct hist_entry *right)
 379 {
 380         struct addr_map_symbol *from_l = &left->branch_info->from;
 381         struct addr_map_symbol *from_r = &right->branch_info->from;
 382
 383         if (!from_l->sym && !from_r->sym)
 384                 return _sort__addr_cmp(from_l->addr, from_r->addr);
 385
 386         return _sort__sym_cmp(from_l->sym, from_r->sym);
 387 }
 388
 389 static int64_t
 390 sort__sym_to_cmp(struct hist_entry *left, struct hist_entry *right)
 391 {
 392         struct addr_map_symbol *to_l = &left->branch_info->to;
 393         struct addr_map_symbol *to_r = &right->branch_info->to;
 394
 395         if (!to_l->sym && !to_r->sym)
 396                 return _sort__addr_cmp(to_l->addr, to_r->addr);
 397
 398         return _sort__sym_cmp(to_l->sym, to_r->sym);
 399 }
 400
 401 static int hist_entry__sym_from_snprintf(struct hist_entry *he, char *bf,
 402                                          size_t size, unsigned int width)
 403 {
 404         struct addr_map_symbol *from = &he->branch_info->from;
 405         return _hist_entry__sym_snprintf(from->map, from->sym, from->addr,
 406                                          he->level, bf, size, width);
 407
 408 }
 409
 410 static int hist_entry__sym_to_snprintf(struct hist_entry *he, char *bf,
 411                                        size_t size, unsigned int width)
 412 {
 413         struct addr_map_symbol *to = &he->branch_info->to;
 414         return _hist_entry__sym_snprintf(to->map, to->sym, to->addr,
 415                                          he->level, bf, size, width);
 416
 417 }
 418
 419 struct sort_entry sort_dso_from = {
 420         .se_header      = "Source Shared Object",
 421         .se_cmp         = sort__dso_from_cmp,
 422         .se_snprintf    = hist_entry__dso_from_snprintf,
 423         .se_width_idx   = HISTC_DSO_FROM,
 424 };
 425
 426 struct sort_entry sort_dso_to = {
 427         .se_header      = "Target Shared Object",
 428         .se_cmp         = sort__dso_to_cmp,
 429         .se_snprintf    = hist_entry__dso_to_snprintf,
 430         .se_width_idx   = HISTC_DSO_TO,
 431 };
 432
 433 struct sort_entry sort_sym_from = {
 434         .se_header      = "Source Symbol",
 435         .se_cmp         = sort__sym_from_cmp,
 436         .se_snprintf    = hist_entry__sym_from_snprintf,
 437         .se_width_idx   = HISTC_SYMBOL_FROM,
 438 };
 439
 440 struct sort_entry sort_sym_to = {
 441         .se_header      = "Target Symbol",
 442         .se_cmp         = sort__sym_to_cmp,
 443         .se_snprintf    = hist_entry__sym_to_snprintf,
 444         .se_width_idx   = HISTC_SYMBOL_TO,
 445 };
 446
 447 static int64_t
 448 sort__mispredict_cmp(struct hist_entry *left, struct hist_entry *right)
 449 {
 450         const unsigned char mp = left->branch_info->flags.mispred !=
 451                                         right->branch_info->flags.mispred;
 452         const unsigned char p = left->branch_info->flags.predicted !=
 453                                         right->branch_info->flags.predicted;
 454
 455         return mp || p;
 456 }
 457
 458 static int hist_entry__mispredict_snprintf(struct hist_entry *he, char *bf,
 459                                     size_t size, unsigned int width){
 460         static const char *out = "N/A";
 461
 462         if (he->branch_info->flags.predicted)
 463                 out = "N";
 464         else if (he->branch_info->flags.mispred)
 465                 out = "Y";
 466
 467         return repsep_snprintf(bf, size, "%-*s", width, out);
 468 }
 469
 470 /* --sort daddr_sym */
 471 static int64_t
 472 sort__daddr_cmp(struct hist_entry *left, struct hist_entry *right)
 473 {
 474         uint64_t l = 0, r = 0;
 475
 476         if (left->mem_info)
 477                 l = left->mem_info->daddr.addr;
 478         if (right->mem_info)
 479                 r = right->mem_info->daddr.addr;
 480
 481         return (int64_t)(r - l);
 482 }
 483
 484 static int hist_entry__daddr_snprintf(struct hist_entry *he, char *bf,
 485                                     size_t size, unsigned int width)
 486 {
 487         uint64_t addr = 0;
 488         struct map *map = NULL;
 489         struct symbol *sym = NULL;
 490
 491         if (he->mem_info) {
 492                 addr = he->mem_info->daddr.addr;
 493                 map = he->mem_info->daddr.map;
 494                 sym = he->mem_info->daddr.sym;
 495         }
 496         return _hist_entry__sym_snprintf(map, sym, addr, he->level, bf, size,
 497                                          width);
 498 }
 499
 500 static int64_t
 501 sort__dso_daddr_cmp(struct hist_entry *left, struct hist_entry *right)
 502 {
 503         struct map *map_l = NULL;
 504         struct map *map_r = NULL;
 505
 506         if (left->mem_info)
 507                 map_l = left->mem_info->daddr.map;
 508         if (right->mem_info)
 509                 map_r = right->mem_info->daddr.map;
 510
 511         return _sort__dso_cmp(map_l, map_r);
 512 }
 513
 514 static int hist_entry__dso_daddr_snprintf(struct hist_entry *he, char *bf,
 515                                     size_t size, unsigned int width)
 516 {
 517         struct map *map = NULL;
 518
 519         if (he->mem_info)
 520                 map = he->mem_info->daddr.map;
 521
 522         return _hist_entry__dso_snprintf(map, bf, size, width);
 523 }
 524
 525 static int64_t
 526 sort__locked_cmp(struct hist_entry *left, struct hist_entry *right)
 527 {
 528         union perf_mem_data_src data_src_l;
 529         union perf_mem_data_src data_src_r;
 530
 531         if (left->mem_info)
 532                 data_src_l = left->mem_info->data_src;
 533         else
 534                 data_src_l.mem_lock = PERF_MEM_LOCK_NA;
 535
 536         if (right->mem_info)
 537                 data_src_r = right->mem_info->data_src;
 538         else
 539                 data_src_r.mem_lock = PERF_MEM_LOCK_NA;
 540
 541         return (int64_t)(data_src_r.mem_lock - data_src_l.mem_lock);
 542 }
 543
 544 static int hist_entry__locked_snprintf(struct hist_entry *he, char *bf,
 545                                     size_t size, unsigned int width)
 546 {
 547         const char *out;
 548         u64 mask = PERF_MEM_LOCK_NA;
 549
 550         if (he->mem_info)
 551                 mask = he->mem_info->data_src.mem_lock;
 552
 553         if (mask & PERF_MEM_LOCK_NA)
 554                 out = "N/A";
 555         else if (mask & PERF_MEM_LOCK_LOCKED)
 556                 out = "Yes";
 557         else
 558                 out = "No";
 559
 560         return repsep_snprintf(bf, size, "%-*s", width, out);
 561 }
 562
 563 static int64_t
 564 sort__tlb_cmp(struct hist_entry *left, struct hist_entry *right)
 565 {
 566         union perf_mem_data_src data_src_l;
 567         union perf_mem_data_src data_src_r;
 568
 569         if (left->mem_info)
 570                 data_src_l = left->mem_info->data_src;
 571         else
 572                 data_src_l.mem_dtlb = PERF_MEM_TLB_NA;
 573
 574         if (right->mem_info)
 575                 data_src_r = right->mem_info->data_src;
 576         else
 577                 data_src_r.mem_dtlb = PERF_MEM_TLB_NA;
 578
 579         return (int64_t)(data_src_r.mem_dtlb - data_src_l.mem_dtlb);
 580 }
 581
 582 static const char * const tlb_access[] = {
 583         "N/A",
 584         "HIT",
 585         "MISS",
 586         "L1",
 587         "L2",
 588         "Walker",
 589         "Fault",
 590 };
 591 #define NUM_TLB_ACCESS (sizeof(tlb_access)/sizeof(const char *))
 592
 593 static int hist_entry__tlb_snprintf(struct hist_entry *he, char *bf,
 594                                     size_t size, unsigned int width)
 595 {
 596         char out[64];
 597         size_t sz = sizeof(out) - 1; /* -1 for null termination */
 598         size_t l = 0, i;
 599         u64 m = PERF_MEM_TLB_NA;
 600         u64 hit, miss;
 601
 602         out[0] = '\0';
 603
 604         if (he->mem_info)
 605                 m = he->mem_info->data_src.mem_dtlb;
 606
 607         hit = m & PERF_MEM_TLB_HIT;
 608         miss = m & PERF_MEM_TLB_MISS;
 609
 610         /* already taken care of */
 611         m &= ~(PERF_MEM_TLB_HIT|PERF_MEM_TLB_MISS);
 612
 613         for (i = 0; m && i < NUM_TLB_ACCESS; i++, m >>= 1) {
 614                 if (!(m & 0x1))
 615                         continue;
 616                 if (l) {
 617                         strcat(out, " or ");
 618                         l += 4;
 619                 }
 620                 strncat(out, tlb_access[i], sz - l);
 621                 l += strlen(tlb_access[i]);
 622         }
 623         if (*out == '\0')
 624                 strcpy(out, "N/A");
 625         if (hit)
 626                 strncat(out, " hit", sz - l);
 627         if (miss)
 628                 strncat(out, " miss", sz - l);
 629
 630         return repsep_snprintf(bf, size, "%-*s", width, out);
 631 }
 632
 633 static int64_t
 634 sort__lvl_cmp(struct hist_entry *left, struct hist_entry *right)
 635 {
 636         union perf_mem_data_src data_src_l;
 637         union perf_mem_data_src data_src_r;
 638
 639         if (left->mem_info)
 640                 data_src_l = left->mem_info->data_src;
 641         else
 642                 data_src_l.mem_lvl = PERF_MEM_LVL_NA;
 643
 644         if (right->mem_info)
 645                 data_src_r = right->mem_info->data_src;
 646         else
 647                 data_src_r.mem_lvl = PERF_MEM_LVL_NA;
 648
 649         return (int64_t)(data_src_r.mem_lvl - data_src_l.mem_lvl);
 650 }
 651
 652 static const char * const mem_lvl[] = {
 653         "N/A",
 654         "HIT",
 655         "MISS",
 656         "L1",
 657         "LFB",
 658         "L2",
 659         "L3",
 660         "Local RAM",
 661         "Remote RAM (1 hop)",
 662         "Remote RAM (2 hops)",
 663         "Remote Cache (1 hop)",
 664         "Remote Cache (2 hops)",
 665         "I/O",
 666         "Uncached",
 667 };
 668 #define NUM_MEM_LVL (sizeof(mem_lvl)/sizeof(const char *))
 669
 670 static int hist_entry__lvl_snprintf(struct hist_entry *he, char *bf,
 671                                     size_t size, unsigned int width)
 672 {
 673         char out[64];
 674         size_t sz = sizeof(out) - 1; /* -1 for null termination */
 675         size_t i, l = 0;
 676         u64 m =  PERF_MEM_LVL_NA;
 677         u64 hit, miss;
 678
 679         if (he->mem_info)
 680                 m  = he->mem_info->data_src.mem_lvl;
 681
 682         out[0] = '\0';
 683
 684         hit = m & PERF_MEM_LVL_HIT;
 685         miss = m & PERF_MEM_LVL_MISS;
 686
 687         /* already taken care of */
 688         m &= ~(PERF_MEM_LVL_HIT|PERF_MEM_LVL_MISS);
 689
 690         for (i = 0; m && i < NUM_MEM_LVL; i++, m >>= 1) {
 691                 if (!(m & 0x1))
 692                         continue;
 693                 if (l) {
 694                         strcat(out, " or ");
 695                         l += 4;
 696                 }
 697                 strncat(out, mem_lvl[i], sz - l);
 698                 l += strlen(mem_lvl[i]);
 699         }
 700         if (*out == '\0')
 701                 strcpy(out, "N/A");
 702         if (hit)
 703                 strncat(out, " hit", sz - l);
 704         if (miss)
 705                 strncat(out, " miss", sz - l);
 706
 707         return repsep_snprintf(bf, size, "%-*s", width, out);
 708 }
 709
 710 static int64_t
 711 sort__snoop_cmp(struct hist_entry *left, struct hist_entry *right)
 712 {
 713         union perf_mem_data_src data_src_l;
 714         union perf_mem_data_src data_src_r;
 715
 716         if (left->mem_info)
 717                 data_src_l = left->mem_info->data_src;
 718         else
 719                 data_src_l.mem_snoop = PERF_MEM_SNOOP_NA;
 720
 721         if (right->mem_info)
 722                 data_src_r = right->mem_info->data_src;
 723         else
 724                 data_src_r.mem_snoop = PERF_MEM_SNOOP_NA;
 725
 726         return (int64_t)(data_src_r.mem_snoop - data_src_l.mem_snoop);
 727 }
 728
 729 static const char * const snoop_access[] = {
 730         "N/A",
 731         "None",
 732         "Miss",
 733         "Hit",
 734         "HitM",
 735 };
 736 #define NUM_SNOOP_ACCESS (sizeof(snoop_access)/sizeof(const char *))
 737
 738 static int hist_entry__snoop_snprintf(struct hist_entry *he, char *bf,
 739                                     size_t size, unsigned int width)
 740 {
 741         char out[64];
 742         size_t sz = sizeof(out) - 1; /* -1 for null termination */
 743         size_t i, l = 0;
 744         u64 m = PERF_MEM_SNOOP_NA;
 745
 746         out[0] = '\0';
 747
 748         if (he->mem_info)
 749                 m = he->mem_info->data_src.mem_snoop;
 750
 751         for (i = 0; m && i < NUM_SNOOP_ACCESS; i++, m >>= 1) {
 752                 if (!(m & 0x1))
 753                         continue;
 754                 if (l) {
 755                         strcat(out, " or ");
 756                         l += 4;
 757                 }
 758                 strncat(out, snoop_access[i], sz - l);
 759                 l += strlen(snoop_access[i]);
 760         }
 761
 762         if (*out == '\0')
 763                 strcpy(out, "N/A");
 764
 765         return repsep_snprintf(bf, size, "%-*s", width, out);
 766 }
 767
 768 struct sort_entry sort_mispredict = {
 769         .se_header      = "Branch Mispredicted",
 770         .se_cmp         = sort__mispredict_cmp,
 771         .se_snprintf    = hist_entry__mispredict_snprintf,
 772         .se_width_idx   = HISTC_MISPREDICT,
 773 };
 774
 775 static u64 he_weight(struct hist_entry *he)
 776 {
 777         return he->stat.nr_events ? he->stat.weight / he->stat.nr_events : 0;
 778 }
 779
 780 static int64_t
 781 sort__local_weight_cmp(struct hist_entry *left, struct hist_entry *right)
 782 {
 783         return he_weight(left) - he_weight(right);
 784 }
 785
 786 static int hist_entry__local_weight_snprintf(struct hist_entry *he, char *bf,
 787                                     size_t size, unsigned int width)
 788 {
 789         return repsep_snprintf(bf, size, "%-*llu", width, he_weight(he));
 790 }
 791
 792 struct sort_entry sort_local_weight = {
 793         .se_header      = "Local Weight",
 794         .se_cmp         = sort__local_weight_cmp,
 795         .se_snprintf    = hist_entry__local_weight_snprintf,
 796         .se_width_idx   = HISTC_LOCAL_WEIGHT,
 797 };
 798
 799 static int64_t
 800 sort__global_weight_cmp(struct hist_entry *left, struct hist_entry *right)
 801 {
 802         return left->stat.weight - right->stat.weight;
 803 }
 804
 805 static int hist_entry__global_weight_snprintf(struct hist_entry *he, char *bf,
 806                                               size_t size, unsigned int width)
 807 {
 808         return repsep_snprintf(bf, size, "%-*llu", width, he->stat.weight);
 809 }
 810
 811 struct sort_entry sort_global_weight = {
 812         .se_header      = "Weight",
 813         .se_cmp         = sort__global_weight_cmp,
 814         .se_snprintf    = hist_entry__global_weight_snprintf,
 815         .se_width_idx   = HISTC_GLOBAL_WEIGHT,
 816 };
 817
 818 struct sort_entry sort_mem_daddr_sym = {
 819         .se_header      = "Data Symbol",
 820         .se_cmp         = sort__daddr_cmp,
 821         .se_snprintf    = hist_entry__daddr_snprintf,
 822         .se_width_idx   = HISTC_MEM_DADDR_SYMBOL,
 823 };
 824
 825 struct sort_entry sort_mem_daddr_dso = {
 826         .se_header      = "Data Object",
 827         .se_cmp         = sort__dso_daddr_cmp,
 828         .se_snprintf    = hist_entry__dso_daddr_snprintf,
 829         .se_width_idx   = HISTC_MEM_DADDR_SYMBOL,
 830 };
 831
 832 struct sort_entry sort_mem_locked = {
 833         .se_header      = "Locked",
 834         .se_cmp         = sort__locked_cmp,
 835         .se_snprintf    = hist_entry__locked_snprintf,
 836         .se_width_idx   = HISTC_MEM_LOCKED,
 837 };
 838
 839 struct sort_entry sort_mem_tlb = {
 840         .se_header      = "TLB access",
 841         .se_cmp         = sort__tlb_cmp,
 842         .se_snprintf    = hist_entry__tlb_snprintf,
 843         .se_width_idx   = HISTC_MEM_TLB,
 844 };
 845
 846 struct sort_entry sort_mem_lvl = {
 847         .se_header      = "Memory access",
 848         .se_cmp         = sort__lvl_cmp,
 849         .se_snprintf    = hist_entry__lvl_snprintf,
 850         .se_width_idx   = HISTC_MEM_LVL,
 851 };
 852
 853 struct sort_entry sort_mem_snoop = {
 854         .se_header      = "Snoop",
 855         .se_cmp         = sort__snoop_cmp,
 856         .se_snprintf    = hist_entry__snoop_snprintf,
 857         .se_width_idx   = HISTC_MEM_SNOOP,
 858 };
 859
 860 static int64_t
 861 sort__abort_cmp(struct hist_entry *left, struct hist_entry *right)
 862 {
 863         return left->branch_info->flags.abort !=
 864                 right->branch_info->flags.abort;
 865 }
 866
 867 static int hist_entry__abort_snprintf(struct hist_entry *he, char *bf,
 868                                     size_t size, unsigned int width)
 869 {
 870         static const char *out = ".";
 871
 872         if (he->branch_info->flags.abort)
 873                 out = "A";
 874         return repsep_snprintf(bf, size, "%-*s", width, out);
 875 }
 876
 877 struct sort_entry sort_abort = {
 878         .se_header      = "Transaction abort",
 879         .se_cmp         = sort__abort_cmp,
 880         .se_snprintf    = hist_entry__abort_snprintf,
 881         .se_width_idx   = HISTC_ABORT,
 882 };
 883
 884 static int64_t
 885 sort__in_tx_cmp(struct hist_entry *left, struct hist_entry *right)
 886 {
 887         return left->branch_info->flags.in_tx !=
 888                 right->branch_info->flags.in_tx;
 889 }
 890
 891 static int hist_entry__in_tx_snprintf(struct hist_entry *he, char *bf,
 892                                     size_t size, unsigned int width)
 893 {
 894         static const char *out = ".";
 895
 896         if (he->branch_info->flags.in_tx)
 897                 out = "T";
 898
 899         return repsep_snprintf(bf, size, "%-*s", width, out);
 900 }
 901
 902 struct sort_entry sort_in_tx = {
 903         .se_header      = "Branch in transaction",
 904         .se_cmp         = sort__in_tx_cmp,
 905         .se_snprintf    = hist_entry__in_tx_snprintf,
 906         .se_width_idx   = HISTC_IN_TX,
 907 };
 908
 909 static int64_t
 910 sort__transaction_cmp(struct hist_entry *left, struct hist_entry *right)
 911 {
 912         return left->transaction - right->transaction;
 913 }
 914
 915 static inline char *add_str(char *p, const char *str)
 916 {
 917         strcpy(p, str);
 918         return p + strlen(str);
 919 }
 920
 921 static struct txbit {
 922         unsigned flag;
 923         const char *name;
 924         int skip_for_len;
 925 } txbits[] = {
 926         { PERF_TXN_ELISION,        "EL ",        0 },
 927         { PERF_TXN_TRANSACTION,    "TX ",        1 },
 928         { PERF_TXN_SYNC,           "SYNC ",      1 },
 929         { PERF_TXN_ASYNC,          "ASYNC ",     0 },
 930         { PERF_TXN_RETRY,          "RETRY ",     0 },
 931         { PERF_TXN_CONFLICT,       "CON ",       0 },
 932         { PERF_TXN_CAPACITY_WRITE, "CAP-WRITE ", 1 },
 933         { PERF_TXN_CAPACITY_READ,  "CAP-READ ",  0 },
 934         { 0, NULL, 0 }
 935 };
 936
 937 int hist_entry__transaction_len(void)
 938 {
 939         int i;
 940         int len = 0;
 941
 942         for (i = 0; txbits[i].name; i++) {
 943                 if (!txbits[i].skip_for_len)
 944                         len += strlen(txbits[i].name);
 945         }
 946         len += 4; /* :XX<space> */
 947         return len;
 948 }
 949
 950 static int hist_entry__transaction_snprintf(struct hist_entry *he, char *bf,
 951                                             size_t size, unsigned int width)
 952 {
 953         u64 t = he->transaction;
 954         char buf[128];
 955         char *p = buf;
 956         int i;
 957
 958         buf[0] = 0;
 959         for (i = 0; txbits[i].name; i++)
 960                 if (txbits[i].flag & t)
 961                         p = add_str(p, txbits[i].name);
 962         if (t && !(t & (PERF_TXN_SYNC|PERF_TXN_ASYNC)))
 963                 p = add_str(p, "NEITHER ");
 964         if (t & PERF_TXN_ABORT_MASK) {
 965                 sprintf(p, ":%" PRIx64,
 966                         (t & PERF_TXN_ABORT_MASK) >>
 967                         PERF_TXN_ABORT_SHIFT);
 968                 p += strlen(p);
 969         }
 970
 971         return repsep_snprintf(bf, size, "%-*s", width, buf);
 972 }
 973
 974 struct sort_entry sort_transaction = {
 975         .se_header      = "Transaction                ",
 976         .se_cmp         = sort__transaction_cmp,
 977         .se_snprintf    = hist_entry__transaction_snprintf,
 978         .se_width_idx   = HISTC_TRANSACTION,
 979 };
 980
 981 struct sort_dimension {
 982         const char              *name;
 983         struct sort_entry       *entry;
 984         int                     taken;
 985 };
 986
 987 #define DIM(d, n, func) [d] = { .name = n, .entry = &(func) }
 988
 989 static struct sort_dimension common_sort_dimensions[] = {
 990         DIM(SORT_PID, "pid", sort_thread),
 991         DIM(SORT_COMM, "comm", sort_comm),
 992         DIM(SORT_DSO, "dso", sort_dso),
 993         DIM(SORT_SYM, "symbol", sort_sym),
 994         DIM(SORT_PARENT, "parent", sort_parent),
 995         DIM(SORT_CPU, "cpu", sort_cpu),
 996         DIM(SORT_SRCLINE, "srcline", sort_srcline),
 997         DIM(SORT_LOCAL_WEIGHT, "local_weight", sort_local_weight),
 998         DIM(SORT_GLOBAL_WEIGHT, "weight", sort_global_weight),
 999         DIM(SORT_TRANSACTION, "transaction", sort_transaction),
1000 };
1001
1002 #undef DIM
1003
1004 #define DIM(d, n, func) [d - __SORT_BRANCH_STACK] = { .name = n, .entry = &(func) }
1005
1006 static struct sort_dimension bstack_sort_dimensions[] = {
1007         DIM(SORT_DSO_FROM, "dso_from", sort_dso_from),
1008         DIM(SORT_DSO_TO, "dso_to", sort_dso_to),
1009         DIM(SORT_SYM_FROM, "symbol_from", sort_sym_from),
1010         DIM(SORT_SYM_TO, "symbol_to", sort_sym_to),
1011         DIM(SORT_MISPREDICT, "mispredict", sort_mispredict),
1012         DIM(SORT_IN_TX, "in_tx", sort_in_tx),
1013         DIM(SORT_ABORT, "abort", sort_abort),
1014 };
1015
1016 #undef DIM
1017
1018 #define DIM(d, n, func) [d - __SORT_MEMORY_MODE] = { .name = n, .entry = &(func) }
1019
1020 static struct sort_dimension memory_sort_dimensions[] = {
1021         DIM(SORT_MEM_DADDR_SYMBOL, "symbol_daddr", sort_mem_daddr_sym),
1022         DIM(SORT_MEM_DADDR_DSO, "dso_daddr", sort_mem_daddr_dso),
1023         DIM(SORT_MEM_LOCKED, "locked", sort_mem_locked),
1024         DIM(SORT_MEM_TLB, "tlb", sort_mem_tlb),
1025         DIM(SORT_MEM_LVL, "mem", sort_mem_lvl),
1026         DIM(SORT_MEM_SNOOP, "snoop", sort_mem_snoop),
1027 };
1028
1029 #undef DIM
1030
1031 struct hpp_dimension {
1032         const char              *name;
1033         struct perf_hpp_fmt     *fmt;
1034         int                     taken;
1035 };
1036
1037 #define DIM(d, n) { .name = n, .fmt = &perf_hpp__format[d], }
1038
1039 static struct hpp_dimension hpp_sort_dimensions[] = {
1040         DIM(PERF_HPP__OVERHEAD, "overhead"),
1041         DIM(PERF_HPP__OVERHEAD_SYS, "overhead_sys"),
1042         DIM(PERF_HPP__OVERHEAD_US, "overhead_us"),
1043         DIM(PERF_HPP__OVERHEAD_GUEST_SYS, "overhead_guest_sys"),
1044         DIM(PERF_HPP__OVERHEAD_GUEST_US, "overhead_guest_us"),
1045         DIM(PERF_HPP__SAMPLES, "sample"),
1046         DIM(PERF_HPP__PERIOD, "period"),
1047 };
1048
1049 #undef DIM
1050
1051 struct hpp_sort_entry {
1052         struct perf_hpp_fmt hpp;
1053         struct sort_entry *se;
1054 };
1055
1056 static int __sort__hpp_header(struct perf_hpp_fmt *fmt, struct perf_hpp *hpp,
1057                               struct perf_evsel *evsel)
1058 {
1059         struct hpp_sort_entry *hse;
1060         size_t len;
1061
1062         hse = container_of(fmt, struct hpp_sort_entry, hpp);
1063         len = hists__col_len(&evsel->hists, hse->se->se_width_idx);
1064
1065         return scnprintf(hpp->buf, hpp->size, "%*s", len, hse->se->se_header);
1066 }
1067
1068 static int __sort__hpp_width(struct perf_hpp_fmt *fmt,
1069                              struct perf_hpp *hpp __maybe_unused,
1070                              struct perf_evsel *evsel)
1071 {
1072         struct hpp_sort_entry *hse;
1073
1074         hse = container_of(fmt, struct hpp_sort_entry, hpp);
1075
1076         return hists__col_len(&evsel->hists, hse->se->se_width_idx);
1077 }
1078
1079 static int __sort__hpp_entry(struct perf_hpp_fmt *fmt, struct perf_hpp *hpp,
1080                              struct hist_entry *he)
1081 {
1082         struct hpp_sort_entry *hse;
1083         size_t len;
1084
1085         hse = container_of(fmt, struct hpp_sort_entry, hpp);
1086         len = hists__col_len(he->hists, hse->se->se_width_idx);
1087
1088         return hse->se->se_snprintf(he, hpp->buf, hpp->size, len);
1089 }
1090
1091 static int __sort_dimension__add_hpp(struct sort_dimension *sd)
1092 {
1093         struct hpp_sort_entry *hse;
1094
1095         hse = malloc(sizeof(*hse));
1096         if (hse == NULL) {
1097                 pr_err("Memory allocation failed\n");
1098                 return -1;
1099         }
1100
1101         hse->se = sd->entry;
1102         hse->hpp.header = __sort__hpp_header;
1103         hse->hpp.width = __sort__hpp_width;
1104         hse->hpp.entry = __sort__hpp_entry;
1105         hse->hpp.color = NULL;
1106
1107         hse->hpp.cmp = sd->entry->se_cmp;
1108         hse->hpp.collapse = sd->entry->se_collapse ? : sd->entry->se_cmp;
1109         hse->hpp.sort = hse->hpp.collapse;
1110
1111         INIT_LIST_HEAD(&hse->hpp.list);
1112         INIT_LIST_HEAD(&hse->hpp.sort_list);
1113
1114         perf_hpp__register_sort_field(&hse->hpp);
1115         return 0;
1116 }
1117
1118 static int __sort_dimension__add(struct sort_dimension *sd, enum sort_type idx)
1119 {
1120         if (sd->taken)
1121                 return 0;
1122
1123         if (__sort_dimension__add_hpp(sd) < 0)
1124                 return -1;
1125
1126         if (sd->entry->se_collapse)
1127                 sort__need_collapse = 1;
1128
1129         if (list_empty(&hist_entry__sort_list))
1130                 sort__first_dimension = idx;
1131
1132         list_add_tail(&sd->entry->list, &hist_entry__sort_list);
1133         sd->taken = 1;
1134
1135         return 0;
1136 }
1137
1138 static int __hpp_dimension__add(struct hpp_dimension *hd)
1139 {
1140         if (!hd->taken) {
1141                 hd->taken = 1;
1142
1143                 perf_hpp__register_sort_field(hd->fmt);
1144         }
1145         return 0;
1146 }
1147
1148 int sort_dimension__add(const char *tok)
1149 {
1150         unsigned int i;
1151
1152         for (i = 0; i < ARRAY_SIZE(common_sort_dimensions); i++) {
1153                 struct sort_dimension *sd = &common_sort_dimensions[i];
1154
1155                 if (strncasecmp(tok, sd->name, strlen(tok)))
1156                         continue;
1157
1158                 if (sd->entry == &sort_parent) {
1159                         int ret = regcomp(&parent_regex, parent_pattern, REG_EXTENDED);
1160                         if (ret) {
1161                                 char err[BUFSIZ];
1162
1163                                 regerror(ret, &parent_regex, err, sizeof(err));
1164                                 pr_err("Invalid regex: %s\n%s", parent_pattern, err);
1165                                 return -EINVAL;
1166                         }
1167                         sort__has_parent = 1;
1168                 } else if (sd->entry == &sort_sym) {
1169                         sort__has_sym = 1;
1170                 } else if (sd->entry == &sort_dso) {
1171                         sort__has_dso = 1;
1172                 }
1173
1174                 return __sort_dimension__add(sd, i);
1175         }
1176
1177         for (i = 0; i < ARRAY_SIZE(hpp_sort_dimensions); i++) {
1178                 struct hpp_dimension *hd = &hpp_sort_dimensions[i];
1179
1180                 if (strncasecmp(tok, hd->name, strlen(tok)))
1181                         continue;
1182
1183                 return __hpp_dimension__add(hd);
1184         }
1185
1186         for (i = 0; i < ARRAY_SIZE(bstack_sort_dimensions); i++) {
1187                 struct sort_dimension *sd = &bstack_sort_dimensions[i];
1188
1189                 if (strncasecmp(tok, sd->name, strlen(tok)))
1190                         continue;
1191
1192                 if (sort__mode != SORT_MODE__BRANCH)
1193                         return -EINVAL;
1194
1195                 if (sd->entry == &sort_sym_from || sd->entry == &sort_sym_to)
1196                         sort__has_sym = 1;
1197
1198                 __sort_dimension__add(sd, i + __SORT_BRANCH_STACK);
1199                 return 0;
1200         }
1201
1202         for (i = 0; i < ARRAY_SIZE(memory_sort_dimensions); i++) {
1203                 struct sort_dimension *sd = &memory_sort_dimensions[i];
1204
1205                 if (strncasecmp(tok, sd->name, strlen(tok)))
1206                         continue;
1207
1208                 if (sort__mode != SORT_MODE__MEMORY)
1209                         return -EINVAL;
1210
1211                 if (sd->entry == &sort_mem_daddr_sym)
1212                         sort__has_sym = 1;
1213
1214                 __sort_dimension__add(sd, i + __SORT_MEMORY_MODE);
1215                 return 0;
1216         }
1217
1218         return -ESRCH;
1219 }
1220
1221 int setup_sorting(void)
1222 {
1223         char *tmp, *tok, *str = strdup(sort_order);
1224         int ret = 0;
1225
1226         if (str == NULL) {
1227                 error("Not enough memory to setup sort keys");
1228                 return -ENOMEM;
1229         }
1230
1231         for (tok = strtok_r(str, ", ", &tmp);
1232                         tok; tok = strtok_r(NULL, ", ", &tmp)) {
1233                 ret = sort_dimension__add(tok);
1234                 if (ret == -EINVAL) {
1235                         error("Invalid --sort key: `%s'", tok);
1236                         break;
1237                 } else if (ret == -ESRCH) {
1238                         error("Unknown --sort key: `%s'", tok);
1239                         break;
1240                 }
1241         }
1242
1243         free(str);
1244         return ret;
1245 }
1246
1247 static void sort_entry__setup_elide(struct sort_entry *se,
1248                                     struct strlist *list,
1249                                     const char *list_name, FILE *fp)
1250 {
1251         if (list && strlist__nr_entries(list) == 1) {
1252                 if (fp != NULL)
1253                         fprintf(fp, "# %s: %s\n", list_name,
1254                                 strlist__entry(list, 0)->s);
1255                 se->elide = true;
1256         }
1257 }
1258
1259 void sort__setup_elide(FILE *output)
1260 {
1261         struct sort_entry *se;
1262
1263         sort_entry__setup_elide(&sort_dso, symbol_conf.dso_list,
1264                                 "dso", output);
1265         sort_entry__setup_elide(&sort_comm, symbol_conf.comm_list,
1266                                 "comm", output);
1267         sort_entry__setup_elide(&sort_sym, symbol_conf.sym_list,
1268                                 "symbol", output);
1269
1270         if (sort__mode == SORT_MODE__BRANCH) {
1271                 sort_entry__setup_elide(&sort_dso_from,
1272                                         symbol_conf.dso_from_list,
1273                                         "dso_from", output);
1274                 sort_entry__setup_elide(&sort_dso_to,
1275                                         symbol_conf.dso_to_list,
1276                                         "dso_to", output);
1277                 sort_entry__setup_elide(&sort_sym_from,
1278                                         symbol_conf.sym_from_list,
1279                                         "sym_from", output);
1280                 sort_entry__setup_elide(&sort_sym_to,
1281                                         symbol_conf.sym_to_list,
1282                                         "sym_to", output);
1283         } else if (sort__mode == SORT_MODE__MEMORY) {
1284                 sort_entry__setup_elide(&sort_dso, symbol_conf.dso_list,
1285                                         "symbol_daddr", output);
1286                 sort_entry__setup_elide(&sort_dso, symbol_conf.dso_list,
1287                                         "dso_daddr", output);
1288                 sort_entry__setup_elide(&sort_dso, symbol_conf.dso_list,
1289                                         "mem", output);
1290                 sort_entry__setup_elide(&sort_dso, symbol_conf.dso_list,
1291                                         "local_weight", output);
1292                 sort_entry__setup_elide(&sort_dso, symbol_conf.dso_list,
1293                                         "tlb", output);
1294                 sort_entry__setup_elide(&sort_dso, symbol_conf.dso_list,
1295                                         "snoop", output);
1296         }
1297
1298         /*
1299          * It makes no sense to elide all of sort entries.
1300          * Just revert them to show up again.
1301          */
1302         list_for_each_entry(se, &hist_entry__sort_list, list) {
1303                 if (!se->elide)
1304                         return;
1305         }
1306
1307         list_for_each_entry(se, &hist_entry__sort_list, list)
1308                 se->elide = false;
1309 }