tools/perf/util/sort.c

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