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 struct sort_dimension {
 862         const char              *name;
 863         struct sort_entry       *entry;
 864         int                     taken;
 865 };
 866
 867 #define DIM(d, n, func) [d] = { .name = n, .entry = &(func) }
 868
 869 static struct sort_dimension common_sort_dimensions[] = {
 870         DIM(SORT_PID, "pid", sort_thread),
 871         DIM(SORT_COMM, "comm", sort_comm),
 872         DIM(SORT_DSO, "dso", sort_dso),
 873         DIM(SORT_SYM, "symbol", sort_sym),
 874         DIM(SORT_PARENT, "parent", sort_parent),
 875         DIM(SORT_CPU, "cpu", sort_cpu),
 876         DIM(SORT_SRCLINE, "srcline", sort_srcline),
 877         DIM(SORT_LOCAL_WEIGHT, "local_weight", sort_local_weight),
 878         DIM(SORT_GLOBAL_WEIGHT, "weight", sort_global_weight),
 879 };
 880
 881 #undef DIM
 882
 883 #define DIM(d, n, func) [d - __SORT_BRANCH_STACK] = { .name = n, .entry = &(func) }
 884
 885 static struct sort_dimension bstack_sort_dimensions[] = {
 886         DIM(SORT_DSO_FROM, "dso_from", sort_dso_from),
 887         DIM(SORT_DSO_TO, "dso_to", sort_dso_to),
 888         DIM(SORT_SYM_FROM, "symbol_from", sort_sym_from),
 889         DIM(SORT_SYM_TO, "symbol_to", sort_sym_to),
 890         DIM(SORT_MISPREDICT, "mispredict", sort_mispredict),
 891 };
 892
 893 #undef DIM
 894
 895 #define DIM(d, n, func) [d - __SORT_MEMORY_MODE] = { .name = n, .entry = &(func) }
 896
 897 static struct sort_dimension memory_sort_dimensions[] = {
 898         DIM(SORT_MEM_DADDR_SYMBOL, "symbol_daddr", sort_mem_daddr_sym),
 899         DIM(SORT_MEM_DADDR_DSO, "dso_daddr", sort_mem_daddr_dso),
 900         DIM(SORT_MEM_LOCKED, "locked", sort_mem_locked),
 901         DIM(SORT_MEM_TLB, "tlb", sort_mem_tlb),
 902         DIM(SORT_MEM_LVL, "mem", sort_mem_lvl),
 903         DIM(SORT_MEM_SNOOP, "snoop", sort_mem_snoop),
 904 };
 905
 906 #undef DIM
 907
 908 static void __sort_dimension__add(struct sort_dimension *sd, enum sort_type idx)
 909 {
 910         if (sd->taken)
 911                 return;
 912
 913         if (sd->entry->se_collapse)
 914                 sort__need_collapse = 1;
 915
 916         if (list_empty(&hist_entry__sort_list))
 917                 sort__first_dimension = idx;
 918
 919         list_add_tail(&sd->entry->list, &hist_entry__sort_list);
 920         sd->taken = 1;
 921 }
 922
 923 int sort_dimension__add(const char *tok)
 924 {
 925         unsigned int i;
 926
 927         for (i = 0; i < ARRAY_SIZE(common_sort_dimensions); i++) {
 928                 struct sort_dimension *sd = &common_sort_dimensions[i];
 929
 930                 if (strncasecmp(tok, sd->name, strlen(tok)))
 931                         continue;
 932
 933                 if (sd->entry == &sort_parent) {
 934                         int ret = regcomp(&parent_regex, parent_pattern, REG_EXTENDED);
 935                         if (ret) {
 936                                 char err[BUFSIZ];
 937
 938                                 regerror(ret, &parent_regex, err, sizeof(err));
 939                                 pr_err("Invalid regex: %s\n%s", parent_pattern, err);
 940                                 return -EINVAL;
 941                         }
 942                         sort__has_parent = 1;
 943                 } else if (sd->entry == &sort_sym) {
 944                         sort__has_sym = 1;
 945                 }
 946
 947                 __sort_dimension__add(sd, i);
 948                 return 0;
 949         }
 950
 951         for (i = 0; i < ARRAY_SIZE(bstack_sort_dimensions); i++) {
 952                 struct sort_dimension *sd = &bstack_sort_dimensions[i];
 953
 954                 if (strncasecmp(tok, sd->name, strlen(tok)))
 955                         continue;
 956
 957                 if (sort__mode != SORT_MODE__BRANCH)
 958                         return -EINVAL;
 959
 960                 if (sd->entry == &sort_sym_from || sd->entry == &sort_sym_to)
 961                         sort__has_sym = 1;
 962
 963                 __sort_dimension__add(sd, i + __SORT_BRANCH_STACK);
 964                 return 0;
 965         }
 966
 967         for (i = 0; i < ARRAY_SIZE(memory_sort_dimensions); i++) {
 968                 struct sort_dimension *sd = &memory_sort_dimensions[i];
 969
 970                 if (strncasecmp(tok, sd->name, strlen(tok)))
 971                         continue;
 972
 973                 if (sort__mode != SORT_MODE__MEMORY)
 974                         return -EINVAL;
 975
 976                 if (sd->entry == &sort_mem_daddr_sym)
 977                         sort__has_sym = 1;
 978
 979                 __sort_dimension__add(sd, i + __SORT_MEMORY_MODE);
 980                 return 0;
 981         }
 982
 983         return -ESRCH;
 984 }
 985
 986 int setup_sorting(void)
 987 {
 988         char *tmp, *tok, *str = strdup(sort_order);
 989         int ret = 0;
 990
 991         if (str == NULL) {
 992                 error("Not enough memory to setup sort keys");
 993                 return -ENOMEM;
 994         }
 995
 996         for (tok = strtok_r(str, ", ", &tmp);
 997                         tok; tok = strtok_r(NULL, ", ", &tmp)) {
 998                 ret = sort_dimension__add(tok);
 999                 if (ret == -EINVAL) {
1000                         error("Invalid --sort key: `%s'", tok);
1001                         break;
1002                 } else if (ret == -ESRCH) {
1003                         error("Unknown --sort key: `%s'", tok);
1004                         break;
1005                 }
1006         }
1007
1008         free(str);
1009         return ret;
1010 }
1011
1012 static void sort_entry__setup_elide(struct sort_entry *self,
1013                                     struct strlist *list,
1014                                     const char *list_name, FILE *fp)
1015 {
1016         if (list && strlist__nr_entries(list) == 1) {
1017                 if (fp != NULL)
1018                         fprintf(fp, "# %s: %s\n", list_name,
1019                                 strlist__entry(list, 0)->s);
1020                 self->elide = true;
1021         }
1022 }
1023
1024 void sort__setup_elide(FILE *output)
1025 {
1026         sort_entry__setup_elide(&sort_dso, symbol_conf.dso_list,
1027                                 "dso", output);
1028         sort_entry__setup_elide(&sort_comm, symbol_conf.comm_list,
1029                                 "comm", output);
1030         sort_entry__setup_elide(&sort_sym, symbol_conf.sym_list,
1031                                 "symbol", output);
1032
1033         if (sort__mode == SORT_MODE__BRANCH) {
1034                 sort_entry__setup_elide(&sort_dso_from,
1035                                         symbol_conf.dso_from_list,
1036                                         "dso_from", output);
1037                 sort_entry__setup_elide(&sort_dso_to,
1038                                         symbol_conf.dso_to_list,
1039                                         "dso_to", output);
1040                 sort_entry__setup_elide(&sort_sym_from,
1041                                         symbol_conf.sym_from_list,
1042                                         "sym_from", output);
1043                 sort_entry__setup_elide(&sort_sym_to,
1044                                         symbol_conf.sym_to_list,
1045                                         "sym_to", output);
1046         } else if (sort__mode == SORT_MODE__MEMORY) {
1047                 sort_entry__setup_elide(&sort_dso, symbol_conf.dso_list,
1048                                         "symbol_daddr", output);
1049                 sort_entry__setup_elide(&sort_dso, symbol_conf.dso_list,
1050                                         "dso_daddr", output);
1051                 sort_entry__setup_elide(&sort_dso, symbol_conf.dso_list,
1052                                         "mem", output);
1053                 sort_entry__setup_elide(&sort_dso, symbol_conf.dso_list,
1054                                         "local_weight", output);
1055                 sort_entry__setup_elide(&sort_dso, symbol_conf.dso_list,
1056                                         "tlb", output);
1057                 sort_entry__setup_elide(&sort_dso, symbol_conf.dso_list,
1058                                         "snoop", output);
1059         }
1060
1061 }