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_sort_entry {
1032         struct perf_hpp_fmt hpp;
1033         struct sort_entry *se;
1034 };
1035
1036 static int __sort__hpp_header(struct perf_hpp_fmt *fmt, struct perf_hpp *hpp,
1037                               struct perf_evsel *evsel)
1038 {
1039         struct hpp_sort_entry *hse;
1040         size_t len;
1041
1042         hse = container_of(fmt, struct hpp_sort_entry, hpp);
1043         len = hists__col_len(&evsel->hists, hse->se->se_width_idx);
1044
1045         return scnprintf(hpp->buf, hpp->size, "%*s", len, hse->se->se_header);
1046 }
1047
1048 static int __sort__hpp_width(struct perf_hpp_fmt *fmt,
1049                              struct perf_hpp *hpp __maybe_unused,
1050                              struct perf_evsel *evsel)
1051 {
1052         struct hpp_sort_entry *hse;
1053
1054         hse = container_of(fmt, struct hpp_sort_entry, hpp);
1055
1056         return hists__col_len(&evsel->hists, hse->se->se_width_idx);
1057 }
1058
1059 static int __sort__hpp_entry(struct perf_hpp_fmt *fmt, struct perf_hpp *hpp,
1060                              struct hist_entry *he)
1061 {
1062         struct hpp_sort_entry *hse;
1063         size_t len;
1064
1065         hse = container_of(fmt, struct hpp_sort_entry, hpp);
1066         len = hists__col_len(he->hists, hse->se->se_width_idx);
1067
1068         return hse->se->se_snprintf(he, hpp->buf, hpp->size, len);
1069 }
1070
1071 static int __sort_dimension__add_hpp(struct sort_dimension *sd)
1072 {
1073         struct hpp_sort_entry *hse;
1074
1075         hse = malloc(sizeof(*hse));
1076         if (hse == NULL) {
1077                 pr_err("Memory allocation failed\n");
1078                 return -1;
1079         }
1080
1081         hse->se = sd->entry;
1082         hse->hpp.header = __sort__hpp_header;
1083         hse->hpp.width = __sort__hpp_width;
1084         hse->hpp.entry = __sort__hpp_entry;
1085         hse->hpp.color = NULL;
1086
1087         hse->hpp.cmp = sd->entry->se_cmp;
1088         hse->hpp.collapse = sd->entry->se_collapse ? : sd->entry->se_cmp;
1089         hse->hpp.sort = hse->hpp.collapse;
1090
1091         INIT_LIST_HEAD(&hse->hpp.list);
1092         INIT_LIST_HEAD(&hse->hpp.sort_list);
1093
1094         perf_hpp__register_sort_field(&hse->hpp);
1095         return 0;
1096 }
1097
1098 static int __sort_dimension__add(struct sort_dimension *sd, enum sort_type idx)
1099 {
1100         if (sd->taken)
1101                 return 0;
1102
1103         if (__sort_dimension__add_hpp(sd) < 0)
1104                 return -1;
1105
1106         if (sd->entry->se_collapse)
1107                 sort__need_collapse = 1;
1108
1109         if (list_empty(&hist_entry__sort_list))
1110                 sort__first_dimension = idx;
1111
1112         list_add_tail(&sd->entry->list, &hist_entry__sort_list);
1113         sd->taken = 1;
1114
1115         return 0;
1116 }
1117
1118 int sort_dimension__add(const char *tok)
1119 {
1120         unsigned int i;
1121
1122         for (i = 0; i < ARRAY_SIZE(common_sort_dimensions); i++) {
1123                 struct sort_dimension *sd = &common_sort_dimensions[i];
1124
1125                 if (strncasecmp(tok, sd->name, strlen(tok)))
1126                         continue;
1127
1128                 if (sd->entry == &sort_parent) {
1129                         int ret = regcomp(&parent_regex, parent_pattern, REG_EXTENDED);
1130                         if (ret) {
1131                                 char err[BUFSIZ];
1132
1133                                 regerror(ret, &parent_regex, err, sizeof(err));
1134                                 pr_err("Invalid regex: %s\n%s", parent_pattern, err);
1135                                 return -EINVAL;
1136                         }
1137                         sort__has_parent = 1;
1138                 } else if (sd->entry == &sort_sym) {
1139                         sort__has_sym = 1;
1140                 } else if (sd->entry == &sort_dso) {
1141                         sort__has_dso = 1;
1142                 }
1143
1144                 return __sort_dimension__add(sd, i);
1145         }
1146
1147         for (i = 0; i < ARRAY_SIZE(bstack_sort_dimensions); i++) {
1148                 struct sort_dimension *sd = &bstack_sort_dimensions[i];
1149
1150                 if (strncasecmp(tok, sd->name, strlen(tok)))
1151                         continue;
1152
1153                 if (sort__mode != SORT_MODE__BRANCH)
1154                         return -EINVAL;
1155
1156                 if (sd->entry == &sort_sym_from || sd->entry == &sort_sym_to)
1157                         sort__has_sym = 1;
1158
1159                 __sort_dimension__add(sd, i + __SORT_BRANCH_STACK);
1160                 return 0;
1161         }
1162
1163         for (i = 0; i < ARRAY_SIZE(memory_sort_dimensions); i++) {
1164                 struct sort_dimension *sd = &memory_sort_dimensions[i];
1165
1166                 if (strncasecmp(tok, sd->name, strlen(tok)))
1167                         continue;
1168
1169                 if (sort__mode != SORT_MODE__MEMORY)
1170                         return -EINVAL;
1171
1172                 if (sd->entry == &sort_mem_daddr_sym)
1173                         sort__has_sym = 1;
1174
1175                 __sort_dimension__add(sd, i + __SORT_MEMORY_MODE);
1176                 return 0;
1177         }
1178
1179         return -ESRCH;
1180 }
1181
1182 int setup_sorting(void)
1183 {
1184         char *tmp, *tok, *str = strdup(sort_order);
1185         int ret = 0;
1186
1187         if (str == NULL) {
1188                 error("Not enough memory to setup sort keys");
1189                 return -ENOMEM;
1190         }
1191
1192         for (tok = strtok_r(str, ", ", &tmp);
1193                         tok; tok = strtok_r(NULL, ", ", &tmp)) {
1194                 ret = sort_dimension__add(tok);
1195                 if (ret == -EINVAL) {
1196                         error("Invalid --sort key: `%s'", tok);
1197                         break;
1198                 } else if (ret == -ESRCH) {
1199                         error("Unknown --sort key: `%s'", tok);
1200                         break;
1201                 }
1202         }
1203
1204         free(str);
1205         return ret;
1206 }
1207
1208 static void sort_entry__setup_elide(struct sort_entry *se,
1209                                     struct strlist *list,
1210                                     const char *list_name, FILE *fp)
1211 {
1212         if (list && strlist__nr_entries(list) == 1) {
1213                 if (fp != NULL)
1214                         fprintf(fp, "# %s: %s\n", list_name,
1215                                 strlist__entry(list, 0)->s);
1216                 se->elide = true;
1217         }
1218 }
1219
1220 void sort__setup_elide(FILE *output)
1221 {
1222         struct sort_entry *se;
1223
1224         sort_entry__setup_elide(&sort_dso, symbol_conf.dso_list,
1225                                 "dso", output);
1226         sort_entry__setup_elide(&sort_comm, symbol_conf.comm_list,
1227                                 "comm", output);
1228         sort_entry__setup_elide(&sort_sym, symbol_conf.sym_list,
1229                                 "symbol", output);
1230
1231         if (sort__mode == SORT_MODE__BRANCH) {
1232                 sort_entry__setup_elide(&sort_dso_from,
1233                                         symbol_conf.dso_from_list,
1234                                         "dso_from", output);
1235                 sort_entry__setup_elide(&sort_dso_to,
1236                                         symbol_conf.dso_to_list,
1237                                         "dso_to", output);
1238                 sort_entry__setup_elide(&sort_sym_from,
1239                                         symbol_conf.sym_from_list,
1240                                         "sym_from", output);
1241                 sort_entry__setup_elide(&sort_sym_to,
1242                                         symbol_conf.sym_to_list,
1243                                         "sym_to", output);
1244         } else if (sort__mode == SORT_MODE__MEMORY) {
1245                 sort_entry__setup_elide(&sort_dso, symbol_conf.dso_list,
1246                                         "symbol_daddr", output);
1247                 sort_entry__setup_elide(&sort_dso, symbol_conf.dso_list,
1248                                         "dso_daddr", output);
1249                 sort_entry__setup_elide(&sort_dso, symbol_conf.dso_list,
1250                                         "mem", output);
1251                 sort_entry__setup_elide(&sort_dso, symbol_conf.dso_list,
1252                                         "local_weight", output);
1253                 sort_entry__setup_elide(&sort_dso, symbol_conf.dso_list,
1254                                         "tlb", output);
1255                 sort_entry__setup_elide(&sort_dso, symbol_conf.dso_list,
1256                                         "snoop", output);
1257         }
1258
1259         /*
1260          * It makes no sense to elide all of sort entries.
1261          * Just revert them to show up again.
1262          */
1263         list_for_each_entry(se, &hist_entry__sort_list, list) {
1264                 if (!se->elide)
1265                         return;
1266         }
1267
1268         list_for_each_entry(se, &hist_entry__sort_list, list)
1269                 se->elide = false;
1270 }