tools/perf/builtin-sched.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 #include "builtin.h"
   3 #include "perf.h"
   4 #include "perf-sys.h"
   5
   6 #include "util/cpumap.h"
   7 #include "util/evlist.h"
   8 #include "util/evsel.h"
   9 #include "util/evsel_fprintf.h"
  10 #include "util/mutex.h"
  11 #include "util/symbol.h"
  12 #include "util/thread.h"
  13 #include "util/header.h"
  14 #include "util/session.h"
  15 #include "util/tool.h"
  16 #include "util/cloexec.h"
  17 #include "util/thread_map.h"
  18 #include "util/color.h"
  19 #include "util/stat.h"
  20 #include "util/string2.h"
  21 #include "util/callchain.h"
  22 #include "util/time-utils.h"
  23
  24 #include <subcmd/pager.h>
  25 #include <subcmd/parse-options.h>
  26 #include "util/trace-event.h"
  27
  28 #include "util/debug.h"
  29 #include "util/event.h"
  30
  31 #include <linux/kernel.h>
  32 #include <linux/log2.h>
  33 #include <linux/zalloc.h>
  34 #include <sys/prctl.h>
  35 #include <sys/resource.h>
  36 #include <inttypes.h>
  37
  38 #include <errno.h>
  39 #include <semaphore.h>
  40 #include <pthread.h>
  41 #include <math.h>
  42 #include <api/fs/fs.h>
  43 #include <perf/cpumap.h>
  44 #include <linux/time64.h>
  45 #include <linux/err.h>
  46
  47 #include <linux/ctype.h>
  48
  49 #define PR_SET_NAME             15               /* Set process name */
  50 #define MAX_CPUS                4096
  51 #define COMM_LEN                20
  52 #define SYM_LEN                 129
  53 #define MAX_PID                 1024000
  54
  55 static const char *cpu_list;
  56 static DECLARE_BITMAP(cpu_bitmap, MAX_NR_CPUS);
  57
  58 struct sched_atom;
  59
  60 struct task_desc {
  61         unsigned long           nr;
  62         unsigned long           pid;
  63         char                    comm[COMM_LEN];
  64
  65         unsigned long           nr_events;
  66         unsigned long           curr_event;
  67         struct sched_atom       **atoms;
  68
  69         pthread_t               thread;
  70         sem_t                   sleep_sem;
  71
  72         sem_t                   ready_for_work;
  73         sem_t                   work_done_sem;
  74
  75         u64                     cpu_usage;
  76 };
  77
  78 enum sched_event_type {
  79         SCHED_EVENT_RUN,
  80         SCHED_EVENT_SLEEP,
  81         SCHED_EVENT_WAKEUP,
  82         SCHED_EVENT_MIGRATION,
  83 };
  84
  85 struct sched_atom {
  86         enum sched_event_type   type;
  87         int                     specific_wait;
  88         u64                     timestamp;
  89         u64                     duration;
  90         unsigned long           nr;
  91         sem_t                   *wait_sem;
  92         struct task_desc        *wakee;
  93 };
  94
  95 #define TASK_STATE_TO_CHAR_STR "RSDTtZXxKWP"
  96
  97 /* task state bitmask, copied from include/linux/sched.h */
  98 #define TASK_RUNNING            0
  99 #define TASK_INTERRUPTIBLE      1
 100 #define TASK_UNINTERRUPTIBLE    2
 101 #define __TASK_STOPPED          4
 102 #define __TASK_TRACED           8
 103 /* in tsk->exit_state */
 104 #define EXIT_DEAD               16
 105 #define EXIT_ZOMBIE             32
 106 #define EXIT_TRACE              (EXIT_ZOMBIE | EXIT_DEAD)
 107 /* in tsk->state again */
 108 #define TASK_DEAD               64
 109 #define TASK_WAKEKILL           128
 110 #define TASK_WAKING             256
 111 #define TASK_PARKED             512
 112
 113 enum thread_state {
 114         THREAD_SLEEPING = 0,
 115         THREAD_WAIT_CPU,
 116         THREAD_SCHED_IN,
 117         THREAD_IGNORE
 118 };
 119
 120 struct work_atom {
 121         struct list_head        list;
 122         enum thread_state       state;
 123         u64                     sched_out_time;
 124         u64                     wake_up_time;
 125         u64                     sched_in_time;
 126         u64                     runtime;
 127 };
 128
 129 struct work_atoms {
 130         struct list_head        work_list;
 131         struct thread           *thread;
 132         struct rb_node          node;
 133         u64                     max_lat;
 134         u64                     max_lat_start;
 135         u64                     max_lat_end;
 136         u64                     total_lat;
 137         u64                     nb_atoms;
 138         u64                     total_runtime;
 139         int                     num_merged;
 140 };
 141
 142 typedef int (*sort_fn_t)(struct work_atoms *, struct work_atoms *);
 143
 144 struct perf_sched;
 145
 146 struct trace_sched_handler {
 147         int (*switch_event)(struct perf_sched *sched, struct evsel *evsel,
 148                             struct perf_sample *sample, struct machine *machine);
 149
 150         int (*runtime_event)(struct perf_sched *sched, struct evsel *evsel,
 151                              struct perf_sample *sample, struct machine *machine);
 152
 153         int (*wakeup_event)(struct perf_sched *sched, struct evsel *evsel,
 154                             struct perf_sample *sample, struct machine *machine);
 155
 156         /* PERF_RECORD_FORK event, not sched_process_fork tracepoint */
 157         int (*fork_event)(struct perf_sched *sched, union perf_event *event,
 158                           struct machine *machine);
 159
 160         int (*migrate_task_event)(struct perf_sched *sched,
 161                                   struct evsel *evsel,
 162                                   struct perf_sample *sample,
 163                                   struct machine *machine);
 164 };
 165
 166 #define COLOR_PIDS PERF_COLOR_BLUE
 167 #define COLOR_CPUS PERF_COLOR_BG_RED
 168
 169 struct perf_sched_map {
 170         DECLARE_BITMAP(comp_cpus_mask, MAX_CPUS);
 171         struct perf_cpu         *comp_cpus;
 172         bool                     comp;
 173         struct perf_thread_map *color_pids;
 174         const char              *color_pids_str;
 175         struct perf_cpu_map     *color_cpus;
 176         const char              *color_cpus_str;
 177         struct perf_cpu_map     *cpus;
 178         const char              *cpus_str;
 179 };
 180
 181 struct perf_sched {
 182         struct perf_tool tool;
 183         const char       *sort_order;
 184         unsigned long    nr_tasks;
 185         struct task_desc **pid_to_task;
 186         struct task_desc **tasks;
 187         const struct trace_sched_handler *tp_handler;
 188         struct mutex     start_work_mutex;
 189         struct mutex     work_done_wait_mutex;
 190         int              profile_cpu;
 191 /*
 192  * Track the current task - that way we can know whether there's any
 193  * weird events, such as a task being switched away that is not current.
 194  */
 195         struct perf_cpu  max_cpu;
 196         u32              curr_pid[MAX_CPUS];
 197         struct thread    *curr_thread[MAX_CPUS];
 198         char             next_shortname1;
 199         char             next_shortname2;
 200         unsigned int     replay_repeat;
 201         unsigned long    nr_run_events;
 202         unsigned long    nr_sleep_events;
 203         unsigned long    nr_wakeup_events;
 204         unsigned long    nr_sleep_corrections;
 205         unsigned long    nr_run_events_optimized;
 206         unsigned long    targetless_wakeups;
 207         unsigned long    multitarget_wakeups;
 208         unsigned long    nr_runs;
 209         unsigned long    nr_timestamps;
 210         unsigned long    nr_unordered_timestamps;
 211         unsigned long    nr_context_switch_bugs;
 212         unsigned long    nr_events;
 213         unsigned long    nr_lost_chunks;
 214         unsigned long    nr_lost_events;
 215         u64              run_measurement_overhead;
 216         u64              sleep_measurement_overhead;
 217         u64              start_time;
 218         u64              cpu_usage;
 219         u64              runavg_cpu_usage;
 220         u64              parent_cpu_usage;
 221         u64              runavg_parent_cpu_usage;
 222         u64              sum_runtime;
 223         u64              sum_fluct;
 224         u64              run_avg;
 225         u64              all_runtime;
 226         u64              all_count;
 227         u64              cpu_last_switched[MAX_CPUS];
 228         struct rb_root_cached atom_root, sorted_atom_root, merged_atom_root;
 229         struct list_head sort_list, cmp_pid;
 230         bool force;
 231         bool skip_merge;
 232         struct perf_sched_map map;
 233
 234         /* options for timehist command */
 235         bool            summary;
 236         bool            summary_only;
 237         bool            idle_hist;
 238         bool            show_callchain;
 239         unsigned int    max_stack;
 240         bool            show_cpu_visual;
 241         bool            show_wakeups;
 242         bool            show_next;
 243         bool            show_migrations;
 244         bool            show_state;
 245         u64             skipped_samples;
 246         const char      *time_str;
 247         struct perf_time_interval ptime;
 248         struct perf_time_interval hist_time;
 249         volatile bool   thread_funcs_exit;
 250 };
 251
 252 /* per thread run time data */
 253 struct thread_runtime {
 254         u64 last_time;      /* time of previous sched in/out event */
 255         u64 dt_run;         /* run time */
 256         u64 dt_sleep;       /* time between CPU access by sleep (off cpu) */
 257         u64 dt_iowait;      /* time between CPU access by iowait (off cpu) */
 258         u64 dt_preempt;     /* time between CPU access by preempt (off cpu) */
 259         u64 dt_delay;       /* time between wakeup and sched-in */
 260         u64 ready_to_run;   /* time of wakeup */
 261
 262         struct stats run_stats;
 263         u64 total_run_time;
 264         u64 total_sleep_time;
 265         u64 total_iowait_time;
 266         u64 total_preempt_time;
 267         u64 total_delay_time;
 268
 269         int last_state;
 270
 271         char shortname[3];
 272         bool comm_changed;
 273
 274         u64 migrations;
 275 };
 276
 277 /* per event run time data */
 278 struct evsel_runtime {
 279         u64 *last_time; /* time this event was last seen per cpu */
 280         u32 ncpu;       /* highest cpu slot allocated */
 281 };
 282
 283 /* per cpu idle time data */
 284 struct idle_thread_runtime {
 285         struct thread_runtime   tr;
 286         struct thread           *last_thread;
 287         struct rb_root_cached   sorted_root;
 288         struct callchain_root   callchain;
 289         struct callchain_cursor cursor;
 290 };
 291
 292 /* track idle times per cpu */
 293 static struct thread **idle_threads;
 294 static int idle_max_cpu;
 295 static char idle_comm[] = "<idle>";
 296
 297 static u64 get_nsecs(void)
 298 {
 299         struct timespec ts;
 300
 301         clock_gettime(CLOCK_MONOTONIC, &ts);
 302
 303         return ts.tv_sec * NSEC_PER_SEC + ts.tv_nsec;
 304 }
 305
 306 static void burn_nsecs(struct perf_sched *sched, u64 nsecs)
 307 {
 308         u64 T0 = get_nsecs(), T1;
 309
 310         do {
 311                 T1 = get_nsecs();
 312         } while (T1 + sched->run_measurement_overhead < T0 + nsecs);
 313 }
 314
 315 static void sleep_nsecs(u64 nsecs)
 316 {
 317         struct timespec ts;
 318
 319         ts.tv_nsec = nsecs % 999999999;
 320         ts.tv_sec = nsecs / 999999999;
 321
 322         nanosleep(&ts, NULL);
 323 }
 324
 325 static void calibrate_run_measurement_overhead(struct perf_sched *sched)
 326 {
 327         u64 T0, T1, delta, min_delta = NSEC_PER_SEC;
 328         int i;
 329
 330         for (i = 0; i < 10; i++) {
 331                 T0 = get_nsecs();
 332                 burn_nsecs(sched, 0);
 333                 T1 = get_nsecs();
 334                 delta = T1-T0;
 335                 min_delta = min(min_delta, delta);
 336         }
 337         sched->run_measurement_overhead = min_delta;
 338
 339         printf("run measurement overhead: %" PRIu64 " nsecs\n", min_delta);
 340 }
 341
 342 static void calibrate_sleep_measurement_overhead(struct perf_sched *sched)
 343 {
 344         u64 T0, T1, delta, min_delta = NSEC_PER_SEC;
 345         int i;
 346
 347         for (i = 0; i < 10; i++) {
 348                 T0 = get_nsecs();
 349                 sleep_nsecs(10000);
 350                 T1 = get_nsecs();
 351                 delta = T1-T0;
 352                 min_delta = min(min_delta, delta);
 353         }
 354         min_delta -= 10000;
 355         sched->sleep_measurement_overhead = min_delta;
 356
 357         printf("sleep measurement overhead: %" PRIu64 " nsecs\n", min_delta);
 358 }
 359
 360 static struct sched_atom *
 361 get_new_event(struct task_desc *task, u64 timestamp)
 362 {
 363         struct sched_atom *event = zalloc(sizeof(*event));
 364         unsigned long idx = task->nr_events;
 365         size_t size;
 366
 367         event->timestamp = timestamp;
 368         event->nr = idx;
 369
 370         task->nr_events++;
 371         size = sizeof(struct sched_atom *) * task->nr_events;
 372         task->atoms = realloc(task->atoms, size);
 373         BUG_ON(!task->atoms);
 374
 375         task->atoms[idx] = event;
 376
 377         return event;
 378 }
 379
 380 static struct sched_atom *last_event(struct task_desc *task)
 381 {
 382         if (!task->nr_events)
 383                 return NULL;
 384
 385         return task->atoms[task->nr_events - 1];
 386 }
 387
 388 static void add_sched_event_run(struct perf_sched *sched, struct task_desc *task,
 389                                 u64 timestamp, u64 duration)
 390 {
 391         struct sched_atom *event, *curr_event = last_event(task);
 392
 393         /*
 394          * optimize an existing RUN event by merging this one
 395          * to it:
 396          */
 397         if (curr_event && curr_event->type == SCHED_EVENT_RUN) {
 398                 sched->nr_run_events_optimized++;
 399                 curr_event->duration += duration;
 400                 return;
 401         }
 402
 403         event = get_new_event(task, timestamp);
 404
 405         event->type = SCHED_EVENT_RUN;
 406         event->duration = duration;
 407
 408         sched->nr_run_events++;
 409 }
 410
 411 static void add_sched_event_wakeup(struct perf_sched *sched, struct task_desc *task,
 412                                    u64 timestamp, struct task_desc *wakee)
 413 {
 414         struct sched_atom *event, *wakee_event;
 415
 416         event = get_new_event(task, timestamp);
 417         event->type = SCHED_EVENT_WAKEUP;
 418         event->wakee = wakee;
 419
 420         wakee_event = last_event(wakee);
 421         if (!wakee_event || wakee_event->type != SCHED_EVENT_SLEEP) {
 422                 sched->targetless_wakeups++;
 423                 return;
 424         }
 425         if (wakee_event->wait_sem) {
 426                 sched->multitarget_wakeups++;
 427                 return;
 428         }
 429
 430         wakee_event->wait_sem = zalloc(sizeof(*wakee_event->wait_sem));
 431         sem_init(wakee_event->wait_sem, 0, 0);
 432         wakee_event->specific_wait = 1;
 433         event->wait_sem = wakee_event->wait_sem;
 434
 435         sched->nr_wakeup_events++;
 436 }
 437
 438 static void add_sched_event_sleep(struct perf_sched *sched, struct task_desc *task,
 439                                   u64 timestamp, u64 task_state __maybe_unused)
 440 {
 441         struct sched_atom *event = get_new_event(task, timestamp);
 442
 443         event->type = SCHED_EVENT_SLEEP;
 444
 445         sched->nr_sleep_events++;
 446 }
 447
 448 static struct task_desc *register_pid(struct perf_sched *sched,
 449                                       unsigned long pid, const char *comm)
 450 {
 451         struct task_desc *task;
 452         static int pid_max;
 453
 454         if (sched->pid_to_task == NULL) {
 455                 if (sysctl__read_int("kernel/pid_max", &pid_max) < 0)
 456                         pid_max = MAX_PID;
 457                 BUG_ON((sched->pid_to_task = calloc(pid_max, sizeof(struct task_desc *))) == NULL);
 458         }
 459         if (pid >= (unsigned long)pid_max) {
 460                 BUG_ON((sched->pid_to_task = realloc(sched->pid_to_task, (pid + 1) *
 461                         sizeof(struct task_desc *))) == NULL);
 462                 while (pid >= (unsigned long)pid_max)
 463                         sched->pid_to_task[pid_max++] = NULL;
 464         }
 465
 466         task = sched->pid_to_task[pid];
 467
 468         if (task)
 469                 return task;
 470
 471         task = zalloc(sizeof(*task));
 472         task->pid = pid;
 473         task->nr = sched->nr_tasks;
 474         strcpy(task->comm, comm);
 475         /*
 476          * every task starts in sleeping state - this gets ignored
 477          * if there's no wakeup pointing to this sleep state:
 478          */
 479         add_sched_event_sleep(sched, task, 0, 0);
 480
 481         sched->pid_to_task[pid] = task;
 482         sched->nr_tasks++;
 483         sched->tasks = realloc(sched->tasks, sched->nr_tasks * sizeof(struct task_desc *));
 484         BUG_ON(!sched->tasks);
 485         sched->tasks[task->nr] = task;
 486
 487         if (verbose > 0)
 488                 printf("registered task #%ld, PID %ld (%s)\n", sched->nr_tasks, pid, comm);
 489
 490         return task;
 491 }
 492
 493
 494 static void print_task_traces(struct perf_sched *sched)
 495 {
 496         struct task_desc *task;
 497         unsigned long i;
 498
 499         for (i = 0; i < sched->nr_tasks; i++) {
 500                 task = sched->tasks[i];
 501                 printf("task %6ld (%20s:%10ld), nr_events: %ld\n",
 502                         task->nr, task->comm, task->pid, task->nr_events);
 503         }
 504 }
 505
 506 static void add_cross_task_wakeups(struct perf_sched *sched)
 507 {
 508         struct task_desc *task1, *task2;
 509         unsigned long i, j;
 510
 511         for (i = 0; i < sched->nr_tasks; i++) {
 512                 task1 = sched->tasks[i];
 513                 j = i + 1;
 514                 if (j == sched->nr_tasks)
 515                         j = 0;
 516                 task2 = sched->tasks[j];
 517                 add_sched_event_wakeup(sched, task1, 0, task2);
 518         }
 519 }
 520
 521 static void perf_sched__process_event(struct perf_sched *sched,
 522                                       struct sched_atom *atom)
 523 {
 524         int ret = 0;
 525
 526         switch (atom->type) {
 527                 case SCHED_EVENT_RUN:
 528                         burn_nsecs(sched, atom->duration);
 529                         break;
 530                 case SCHED_EVENT_SLEEP:
 531                         if (atom->wait_sem)
 532                                 ret = sem_wait(atom->wait_sem);
 533                         BUG_ON(ret);
 534                         break;
 535                 case SCHED_EVENT_WAKEUP:
 536                         if (atom->wait_sem)
 537                                 ret = sem_post(atom->wait_sem);
 538                         BUG_ON(ret);
 539                         break;
 540                 case SCHED_EVENT_MIGRATION:
 541                         break;
 542                 default:
 543                         BUG_ON(1);
 544         }
 545 }
 546
 547 static u64 get_cpu_usage_nsec_parent(void)
 548 {
 549         struct rusage ru;
 550         u64 sum;
 551         int err;
 552
 553         err = getrusage(RUSAGE_SELF, &ru);
 554         BUG_ON(err);
 555
 556         sum =  ru.ru_utime.tv_sec * NSEC_PER_SEC + ru.ru_utime.tv_usec * NSEC_PER_USEC;
 557         sum += ru.ru_stime.tv_sec * NSEC_PER_SEC + ru.ru_stime.tv_usec * NSEC_PER_USEC;
 558
 559         return sum;
 560 }
 561
 562 static int self_open_counters(struct perf_sched *sched, unsigned long cur_task)
 563 {
 564         struct perf_event_attr attr;
 565         char sbuf[STRERR_BUFSIZE], info[STRERR_BUFSIZE];
 566         int fd;
 567         struct rlimit limit;
 568         bool need_privilege = false;
 569
 570         memset(&attr, 0, sizeof(attr));
 571
 572         attr.type = PERF_TYPE_SOFTWARE;
 573         attr.config = PERF_COUNT_SW_TASK_CLOCK;
 574
 575 force_again:
 576         fd = sys_perf_event_open(&attr, 0, -1, -1,
 577                                  perf_event_open_cloexec_flag());
 578
 579         if (fd < 0) {
 580                 if (errno == EMFILE) {
 581                         if (sched->force) {
 582                                 BUG_ON(getrlimit(RLIMIT_NOFILE, &limit) == -1);
 583                                 limit.rlim_cur += sched->nr_tasks - cur_task;
 584                                 if (limit.rlim_cur > limit.rlim_max) {
 585                                         limit.rlim_max = limit.rlim_cur;
 586                                         need_privilege = true;
 587                                 }
 588                                 if (setrlimit(RLIMIT_NOFILE, &limit) == -1) {
 589                                         if (need_privilege && errno == EPERM)
 590                                                 strcpy(info, "Need privilege\n");
 591                                 } else
 592                                         goto force_again;
 593                         } else
 594                                 strcpy(info, "Have a try with -f option\n");
 595                 }
 596                 pr_err("Error: sys_perf_event_open() syscall returned "
 597                        "with %d (%s)\n%s", fd,
 598                        str_error_r(errno, sbuf, sizeof(sbuf)), info);
 599                 exit(EXIT_FAILURE);
 600         }
 601         return fd;
 602 }
 603
 604 static u64 get_cpu_usage_nsec_self(int fd)
 605 {
 606         u64 runtime;
 607         int ret;
 608
 609         ret = read(fd, &runtime, sizeof(runtime));
 610         BUG_ON(ret != sizeof(runtime));
 611
 612         return runtime;
 613 }
 614
 615 struct sched_thread_parms {
 616         struct task_desc  *task;
 617         struct perf_sched *sched;
 618         int fd;
 619 };
 620
 621 static void *thread_func(void *ctx)
 622 {
 623         struct sched_thread_parms *parms = ctx;
 624         struct task_desc *this_task = parms->task;
 625         struct perf_sched *sched = parms->sched;
 626         u64 cpu_usage_0, cpu_usage_1;
 627         unsigned long i, ret;
 628         char comm2[22];
 629         int fd = parms->fd;
 630
 631         zfree(&parms);
 632
 633         sprintf(comm2, ":%s", this_task->comm);
 634         prctl(PR_SET_NAME, comm2);
 635         if (fd < 0)
 636                 return NULL;
 637
 638         while (!sched->thread_funcs_exit) {
 639                 ret = sem_post(&this_task->ready_for_work);
 640                 BUG_ON(ret);
 641                 mutex_lock(&sched->start_work_mutex);
 642                 mutex_unlock(&sched->start_work_mutex);
 643
 644                 cpu_usage_0 = get_cpu_usage_nsec_self(fd);
 645
 646                 for (i = 0; i < this_task->nr_events; i++) {
 647                         this_task->curr_event = i;
 648                         perf_sched__process_event(sched, this_task->atoms[i]);
 649                 }
 650
 651                 cpu_usage_1 = get_cpu_usage_nsec_self(fd);
 652                 this_task->cpu_usage = cpu_usage_1 - cpu_usage_0;
 653                 ret = sem_post(&this_task->work_done_sem);
 654                 BUG_ON(ret);
 655
 656                 mutex_lock(&sched->work_done_wait_mutex);
 657                 mutex_unlock(&sched->work_done_wait_mutex);
 658         }
 659         return NULL;
 660 }
 661
 662 static void create_tasks(struct perf_sched *sched)
 663         EXCLUSIVE_LOCK_FUNCTION(sched->start_work_mutex)
 664         EXCLUSIVE_LOCK_FUNCTION(sched->work_done_wait_mutex)
 665 {
 666         struct task_desc *task;
 667         pthread_attr_t attr;
 668         unsigned long i;
 669         int err;
 670
 671         err = pthread_attr_init(&attr);
 672         BUG_ON(err);
 673         err = pthread_attr_setstacksize(&attr,
 674                         (size_t) max(16 * 1024, (int)PTHREAD_STACK_MIN));
 675         BUG_ON(err);
 676         mutex_lock(&sched->start_work_mutex);
 677         mutex_lock(&sched->work_done_wait_mutex);
 678         for (i = 0; i < sched->nr_tasks; i++) {
 679                 struct sched_thread_parms *parms = malloc(sizeof(*parms));
 680                 BUG_ON(parms == NULL);
 681                 parms->task = task = sched->tasks[i];
 682                 parms->sched = sched;
 683                 parms->fd = self_open_counters(sched, i);
 684                 sem_init(&task->sleep_sem, 0, 0);
 685                 sem_init(&task->ready_for_work, 0, 0);
 686                 sem_init(&task->work_done_sem, 0, 0);
 687                 task->curr_event = 0;
 688                 err = pthread_create(&task->thread, &attr, thread_func, parms);
 689                 BUG_ON(err);
 690         }
 691 }
 692
 693 static void destroy_tasks(struct perf_sched *sched)
 694         UNLOCK_FUNCTION(sched->start_work_mutex)
 695         UNLOCK_FUNCTION(sched->work_done_wait_mutex)
 696 {
 697         struct task_desc *task;
 698         unsigned long i;
 699         int err;
 700
 701         mutex_unlock(&sched->start_work_mutex);
 702         mutex_unlock(&sched->work_done_wait_mutex);
 703         /* Get rid of threads so they won't be upset by mutex destrunction */
 704         for (i = 0; i < sched->nr_tasks; i++) {
 705                 task = sched->tasks[i];
 706                 err = pthread_join(task->thread, NULL);
 707                 BUG_ON(err);
 708                 sem_destroy(&task->sleep_sem);
 709                 sem_destroy(&task->ready_for_work);
 710                 sem_destroy(&task->work_done_sem);
 711         }
 712 }
 713
 714 static void wait_for_tasks(struct perf_sched *sched)
 715         EXCLUSIVE_LOCKS_REQUIRED(sched->work_done_wait_mutex)
 716         EXCLUSIVE_LOCKS_REQUIRED(sched->start_work_mutex)
 717 {
 718         u64 cpu_usage_0, cpu_usage_1;
 719         struct task_desc *task;
 720         unsigned long i, ret;
 721
 722         sched->start_time = get_nsecs();
 723         sched->cpu_usage = 0;
 724         mutex_unlock(&sched->work_done_wait_mutex);
 725
 726         for (i = 0; i < sched->nr_tasks; i++) {
 727                 task = sched->tasks[i];
 728                 ret = sem_wait(&task->ready_for_work);
 729                 BUG_ON(ret);
 730                 sem_init(&task->ready_for_work, 0, 0);
 731         }
 732         mutex_lock(&sched->work_done_wait_mutex);
 733
 734         cpu_usage_0 = get_cpu_usage_nsec_parent();
 735
 736         mutex_unlock(&sched->start_work_mutex);
 737
 738         for (i = 0; i < sched->nr_tasks; i++) {
 739                 task = sched->tasks[i];
 740                 ret = sem_wait(&task->work_done_sem);
 741                 BUG_ON(ret);
 742                 sem_init(&task->work_done_sem, 0, 0);
 743                 sched->cpu_usage += task->cpu_usage;
 744                 task->cpu_usage = 0;
 745         }
 746
 747         cpu_usage_1 = get_cpu_usage_nsec_parent();
 748         if (!sched->runavg_cpu_usage)
 749                 sched->runavg_cpu_usage = sched->cpu_usage;
 750         sched->runavg_cpu_usage = (sched->runavg_cpu_usage * (sched->replay_repeat - 1) + sched->cpu_usage) / sched->replay_repeat;
 751
 752         sched->parent_cpu_usage = cpu_usage_1 - cpu_usage_0;
 753         if (!sched->runavg_parent_cpu_usage)
 754                 sched->runavg_parent_cpu_usage = sched->parent_cpu_usage;
 755         sched->runavg_parent_cpu_usage = (sched->runavg_parent_cpu_usage * (sched->replay_repeat - 1) +
 756                                          sched->parent_cpu_usage)/sched->replay_repeat;
 757
 758         mutex_lock(&sched->start_work_mutex);
 759
 760         for (i = 0; i < sched->nr_tasks; i++) {
 761                 task = sched->tasks[i];
 762                 sem_init(&task->sleep_sem, 0, 0);
 763                 task->curr_event = 0;
 764         }
 765 }
 766
 767 static void run_one_test(struct perf_sched *sched)
 768         EXCLUSIVE_LOCKS_REQUIRED(sched->work_done_wait_mutex)
 769         EXCLUSIVE_LOCKS_REQUIRED(sched->start_work_mutex)
 770 {
 771         u64 T0, T1, delta, avg_delta, fluct;
 772
 773         T0 = get_nsecs();
 774         wait_for_tasks(sched);
 775         T1 = get_nsecs();
 776
 777         delta = T1 - T0;
 778         sched->sum_runtime += delta;
 779         sched->nr_runs++;
 780
 781         avg_delta = sched->sum_runtime / sched->nr_runs;
 782         if (delta < avg_delta)
 783                 fluct = avg_delta - delta;
 784         else
 785                 fluct = delta - avg_delta;
 786         sched->sum_fluct += fluct;
 787         if (!sched->run_avg)
 788                 sched->run_avg = delta;
 789         sched->run_avg = (sched->run_avg * (sched->replay_repeat - 1) + delta) / sched->replay_repeat;
 790
 791         printf("#%-3ld: %0.3f, ", sched->nr_runs, (double)delta / NSEC_PER_MSEC);
 792
 793         printf("ravg: %0.2f, ", (double)sched->run_avg / NSEC_PER_MSEC);
 794
 795         printf("cpu: %0.2f / %0.2f",
 796                 (double)sched->cpu_usage / NSEC_PER_MSEC, (double)sched->runavg_cpu_usage / NSEC_PER_MSEC);
 797
 798 #if 0
 799         /*
 800          * rusage statistics done by the parent, these are less
 801          * accurate than the sched->sum_exec_runtime based statistics:
 802          */
 803         printf(" [%0.2f / %0.2f]",
 804                 (double)sched->parent_cpu_usage / NSEC_PER_MSEC,
 805                 (double)sched->runavg_parent_cpu_usage / NSEC_PER_MSEC);
 806 #endif
 807
 808         printf("\n");
 809
 810         if (sched->nr_sleep_corrections)
 811                 printf(" (%ld sleep corrections)\n", sched->nr_sleep_corrections);
 812         sched->nr_sleep_corrections = 0;
 813 }
 814
 815 static void test_calibrations(struct perf_sched *sched)
 816 {
 817         u64 T0, T1;
 818
 819         T0 = get_nsecs();
 820         burn_nsecs(sched, NSEC_PER_MSEC);
 821         T1 = get_nsecs();
 822
 823         printf("the run test took %" PRIu64 " nsecs\n", T1 - T0);
 824
 825         T0 = get_nsecs();
 826         sleep_nsecs(NSEC_PER_MSEC);
 827         T1 = get_nsecs();
 828
 829         printf("the sleep test took %" PRIu64 " nsecs\n", T1 - T0);
 830 }
 831
 832 static int
 833 replay_wakeup_event(struct perf_sched *sched,
 834                     struct evsel *evsel, struct perf_sample *sample,
 835                     struct machine *machine __maybe_unused)
 836 {
 837         const char *comm = evsel__strval(evsel, sample, "comm");
 838         const u32 pid    = evsel__intval(evsel, sample, "pid");
 839         struct task_desc *waker, *wakee;
 840
 841         if (verbose > 0) {
 842                 printf("sched_wakeup event %p\n", evsel);
 843
 844                 printf(" ... pid %d woke up %s/%d\n", sample->tid, comm, pid);
 845         }
 846
 847         waker = register_pid(sched, sample->tid, "<unknown>");
 848         wakee = register_pid(sched, pid, comm);
 849
 850         add_sched_event_wakeup(sched, waker, sample->time, wakee);
 851         return 0;
 852 }
 853
 854 static int replay_switch_event(struct perf_sched *sched,
 855                                struct evsel *evsel,
 856                                struct perf_sample *sample,
 857                                struct machine *machine __maybe_unused)
 858 {
 859         const char *prev_comm  = evsel__strval(evsel, sample, "prev_comm"),
 860                    *next_comm  = evsel__strval(evsel, sample, "next_comm");
 861         const u32 prev_pid = evsel__intval(evsel, sample, "prev_pid"),
 862                   next_pid = evsel__intval(evsel, sample, "next_pid");
 863         const u64 prev_state = evsel__intval(evsel, sample, "prev_state");
 864         struct task_desc *prev, __maybe_unused *next;
 865         u64 timestamp0, timestamp = sample->time;
 866         int cpu = sample->cpu;
 867         s64 delta;
 868
 869         if (verbose > 0)
 870                 printf("sched_switch event %p\n", evsel);
 871
 872         if (cpu >= MAX_CPUS || cpu < 0)
 873                 return 0;
 874
 875         timestamp0 = sched->cpu_last_switched[cpu];
 876         if (timestamp0)
 877                 delta = timestamp - timestamp0;
 878         else
 879                 delta = 0;
 880
 881         if (delta < 0) {
 882                 pr_err("hm, delta: %" PRIu64 " < 0 ?\n", delta);
 883                 return -1;
 884         }
 885
 886         pr_debug(" ... switch from %s/%d to %s/%d [ran %" PRIu64 " nsecs]\n",
 887                  prev_comm, prev_pid, next_comm, next_pid, delta);
 888
 889         prev = register_pid(sched, prev_pid, prev_comm);
 890         next = register_pid(sched, next_pid, next_comm);
 891
 892         sched->cpu_last_switched[cpu] = timestamp;
 893
 894         add_sched_event_run(sched, prev, timestamp, delta);
 895         add_sched_event_sleep(sched, prev, timestamp, prev_state);
 896
 897         return 0;
 898 }
 899
 900 static int replay_fork_event(struct perf_sched *sched,
 901                              union perf_event *event,
 902                              struct machine *machine)
 903 {
 904         struct thread *child, *parent;
 905
 906         child = machine__findnew_thread(machine, event->fork.pid,
 907                                         event->fork.tid);
 908         parent = machine__findnew_thread(machine, event->fork.ppid,
 909                                          event->fork.ptid);
 910
 911         if (child == NULL || parent == NULL) {
 912                 pr_debug("thread does not exist on fork event: child %p, parent %p\n",
 913                                  child, parent);
 914                 goto out_put;
 915         }
 916
 917         if (verbose > 0) {
 918                 printf("fork event\n");
 919                 printf("... parent: %s/%d\n", thread__comm_str(parent), parent->tid);
 920                 printf("...  child: %s/%d\n", thread__comm_str(child), child->tid);
 921         }
 922
 923         register_pid(sched, parent->tid, thread__comm_str(parent));
 924         register_pid(sched, child->tid, thread__comm_str(child));
 925 out_put:
 926         thread__put(child);
 927         thread__put(parent);
 928         return 0;
 929 }
 930
 931 struct sort_dimension {
 932         const char              *name;
 933         sort_fn_t               cmp;
 934         struct list_head        list;
 935 };
 936
 937 /*
 938  * handle runtime stats saved per thread
 939  */
 940 static struct thread_runtime *thread__init_runtime(struct thread *thread)
 941 {
 942         struct thread_runtime *r;
 943
 944         r = zalloc(sizeof(struct thread_runtime));
 945         if (!r)
 946                 return NULL;
 947
 948         init_stats(&r->run_stats);
 949         thread__set_priv(thread, r);
 950
 951         return r;
 952 }
 953
 954 static struct thread_runtime *thread__get_runtime(struct thread *thread)
 955 {
 956         struct thread_runtime *tr;
 957
 958         tr = thread__priv(thread);
 959         if (tr == NULL) {
 960                 tr = thread__init_runtime(thread);
 961                 if (tr == NULL)
 962                         pr_debug("Failed to malloc memory for runtime data.\n");
 963         }
 964
 965         return tr;
 966 }
 967
 968 static int
 969 thread_lat_cmp(struct list_head *list, struct work_atoms *l, struct work_atoms *r)
 970 {
 971         struct sort_dimension *sort;
 972         int ret = 0;
 973
 974         BUG_ON(list_empty(list));
 975
 976         list_for_each_entry(sort, list, list) {
 977                 ret = sort->cmp(l, r);
 978                 if (ret)
 979                         return ret;
 980         }
 981
 982         return ret;
 983 }
 984
 985 static struct work_atoms *
 986 thread_atoms_search(struct rb_root_cached *root, struct thread *thread,
 987                          struct list_head *sort_list)
 988 {
 989         struct rb_node *node = root->rb_root.rb_node;
 990         struct work_atoms key = { .thread = thread };
 991
 992         while (node) {
 993                 struct work_atoms *atoms;
 994                 int cmp;
 995
 996                 atoms = container_of(node, struct work_atoms, node);
 997
 998                 cmp = thread_lat_cmp(sort_list, &key, atoms);
 999                 if (cmp > 0)
1000                         node = node->rb_left;
1001                 else if (cmp < 0)
1002                         node = node->rb_right;
1003                 else {
1004                         BUG_ON(thread != atoms->thread);
1005                         return atoms;
1006                 }
1007         }
1008         return NULL;
1009 }
1010
1011 static void
1012 __thread_latency_insert(struct rb_root_cached *root, struct work_atoms *data,
1013                          struct list_head *sort_list)
1014 {
1015         struct rb_node **new = &(root->rb_root.rb_node), *parent = NULL;
1016         bool leftmost = true;
1017
1018         while (*new) {
1019                 struct work_atoms *this;
1020                 int cmp;
1021
1022                 this = container_of(*new, struct work_atoms, node);
1023                 parent = *new;
1024
1025                 cmp = thread_lat_cmp(sort_list, data, this);
1026
1027                 if (cmp > 0)
1028                         new = &((*new)->rb_left);
1029                 else {
1030                         new = &((*new)->rb_right);
1031                         leftmost = false;
1032                 }
1033         }
1034
1035         rb_link_node(&data->node, parent, new);
1036         rb_insert_color_cached(&data->node, root, leftmost);
1037 }
1038
1039 static int thread_atoms_insert(struct perf_sched *sched, struct thread *thread)
1040 {
1041         struct work_atoms *atoms = zalloc(sizeof(*atoms));
1042         if (!atoms) {
1043                 pr_err("No memory at %s\n", __func__);
1044                 return -1;
1045         }
1046
1047         atoms->thread = thread__get(thread);
1048         INIT_LIST_HEAD(&atoms->work_list);
1049         __thread_latency_insert(&sched->atom_root, atoms, &sched->cmp_pid);
1050         return 0;
1051 }
1052
1053 static char sched_out_state(u64 prev_state)
1054 {
1055         const char *str = TASK_STATE_TO_CHAR_STR;
1056
1057         return str[prev_state];
1058 }
1059
1060 static int
1061 add_sched_out_event(struct work_atoms *atoms,
1062                     char run_state,
1063                     u64 timestamp)
1064 {
1065         struct work_atom *atom = zalloc(sizeof(*atom));
1066         if (!atom) {
1067                 pr_err("Non memory at %s", __func__);
1068                 return -1;
1069         }
1070
1071         atom->sched_out_time = timestamp;
1072
1073         if (run_state == 'R') {
1074                 atom->state = THREAD_WAIT_CPU;
1075                 atom->wake_up_time = atom->sched_out_time;
1076         }
1077
1078         list_add_tail(&atom->list, &atoms->work_list);
1079         return 0;
1080 }
1081
1082 static void
1083 add_runtime_event(struct work_atoms *atoms, u64 delta,
1084                   u64 timestamp __maybe_unused)
1085 {
1086         struct work_atom *atom;
1087
1088         BUG_ON(list_empty(&atoms->work_list));
1089
1090         atom = list_entry(atoms->work_list.prev, struct work_atom, list);
1091
1092         atom->runtime += delta;
1093         atoms->total_runtime += delta;
1094 }
1095
1096 static void
1097 add_sched_in_event(struct work_atoms *atoms, u64 timestamp)
1098 {
1099         struct work_atom *atom;
1100         u64 delta;
1101
1102         if (list_empty(&atoms->work_list))
1103                 return;
1104
1105         atom = list_entry(atoms->work_list.prev, struct work_atom, list);
1106
1107         if (atom->state != THREAD_WAIT_CPU)
1108                 return;
1109
1110         if (timestamp < atom->wake_up_time) {
1111                 atom->state = THREAD_IGNORE;
1112                 return;
1113         }
1114
1115         atom->state = THREAD_SCHED_IN;
1116         atom->sched_in_time = timestamp;
1117
1118         delta = atom->sched_in_time - atom->wake_up_time;
1119         atoms->total_lat += delta;
1120         if (delta > atoms->max_lat) {
1121                 atoms->max_lat = delta;
1122                 atoms->max_lat_start = atom->wake_up_time;
1123                 atoms->max_lat_end = timestamp;
1124         }
1125         atoms->nb_atoms++;
1126 }
1127
1128 static int latency_switch_event(struct perf_sched *sched,
1129                                 struct evsel *evsel,
1130                                 struct perf_sample *sample,
1131                                 struct machine *machine)
1132 {
1133         const u32 prev_pid = evsel__intval(evsel, sample, "prev_pid"),
1134                   next_pid = evsel__intval(evsel, sample, "next_pid");
1135         const u64 prev_state = evsel__intval(evsel, sample, "prev_state");
1136         struct work_atoms *out_events, *in_events;
1137         struct thread *sched_out, *sched_in;
1138         u64 timestamp0, timestamp = sample->time;
1139         int cpu = sample->cpu, err = -1;
1140         s64 delta;
1141
1142         BUG_ON(cpu >= MAX_CPUS || cpu < 0);
1143
1144         timestamp0 = sched->cpu_last_switched[cpu];
1145         sched->cpu_last_switched[cpu] = timestamp;
1146         if (timestamp0)
1147                 delta = timestamp - timestamp0;
1148         else
1149                 delta = 0;
1150
1151         if (delta < 0) {
1152                 pr_err("hm, delta: %" PRIu64 " < 0 ?\n", delta);
1153                 return -1;
1154         }
1155
1156         sched_out = machine__findnew_thread(machine, -1, prev_pid);
1157         sched_in = machine__findnew_thread(machine, -1, next_pid);
1158         if (sched_out == NULL || sched_in == NULL)
1159                 goto out_put;
1160
1161         out_events = thread_atoms_search(&sched->atom_root, sched_out, &sched->cmp_pid);
1162         if (!out_events) {
1163                 if (thread_atoms_insert(sched, sched_out))
1164                         goto out_put;
1165                 out_events = thread_atoms_search(&sched->atom_root, sched_out, &sched->cmp_pid);
1166                 if (!out_events) {
1167                         pr_err("out-event: Internal tree error");
1168                         goto out_put;
1169                 }
1170         }
1171         if (add_sched_out_event(out_events, sched_out_state(prev_state), timestamp))
1172                 return -1;
1173
1174         in_events = thread_atoms_search(&sched->atom_root, sched_in, &sched->cmp_pid);
1175         if (!in_events) {
1176                 if (thread_atoms_insert(sched, sched_in))
1177                         goto out_put;
1178                 in_events = thread_atoms_search(&sched->atom_root, sched_in, &sched->cmp_pid);
1179                 if (!in_events) {
1180                         pr_err("in-event: Internal tree error");
1181                         goto out_put;
1182                 }
1183                 /*
1184                  * Take came in we have not heard about yet,
1185                  * add in an initial atom in runnable state:
1186                  */
1187                 if (add_sched_out_event(in_events, 'R', timestamp))
1188                         goto out_put;
1189         }
1190         add_sched_in_event(in_events, timestamp);
1191         err = 0;
1192 out_put:
1193         thread__put(sched_out);
1194         thread__put(sched_in);
1195         return err;
1196 }
1197
1198 static int latency_runtime_event(struct perf_sched *sched,
1199                                  struct evsel *evsel,
1200                                  struct perf_sample *sample,
1201                                  struct machine *machine)
1202 {
1203         const u32 pid      = evsel__intval(evsel, sample, "pid");
1204         const u64 runtime  = evsel__intval(evsel, sample, "runtime");
1205         struct thread *thread = machine__findnew_thread(machine, -1, pid);
1206         struct work_atoms *atoms = thread_atoms_search(&sched->atom_root, thread, &sched->cmp_pid);
1207         u64 timestamp = sample->time;
1208         int cpu = sample->cpu, err = -1;
1209
1210         if (thread == NULL)
1211                 return -1;
1212
1213         BUG_ON(cpu >= MAX_CPUS || cpu < 0);
1214         if (!atoms) {
1215                 if (thread_atoms_insert(sched, thread))
1216                         goto out_put;
1217                 atoms = thread_atoms_search(&sched->atom_root, thread, &sched->cmp_pid);
1218                 if (!atoms) {
1219                         pr_err("in-event: Internal tree error");
1220                         goto out_put;
1221                 }
1222                 if (add_sched_out_event(atoms, 'R', timestamp))
1223                         goto out_put;
1224         }
1225
1226         add_runtime_event(atoms, runtime, timestamp);
1227         err = 0;
1228 out_put:
1229         thread__put(thread);
1230         return err;
1231 }
1232
1233 static int latency_wakeup_event(struct perf_sched *sched,
1234                                 struct evsel *evsel,
1235                                 struct perf_sample *sample,
1236                                 struct machine *machine)
1237 {
1238         const u32 pid     = evsel__intval(evsel, sample, "pid");
1239         struct work_atoms *atoms;
1240         struct work_atom *atom;
1241         struct thread *wakee;
1242         u64 timestamp = sample->time;
1243         int err = -1;
1244
1245         wakee = machine__findnew_thread(machine, -1, pid);
1246         if (wakee == NULL)
1247                 return -1;
1248         atoms = thread_atoms_search(&sched->atom_root, wakee, &sched->cmp_pid);
1249         if (!atoms) {
1250                 if (thread_atoms_insert(sched, wakee))
1251                         goto out_put;
1252                 atoms = thread_atoms_search(&sched->atom_root, wakee, &sched->cmp_pid);
1253                 if (!atoms) {
1254                         pr_err("wakeup-event: Internal tree error");
1255                         goto out_put;
1256                 }
1257                 if (add_sched_out_event(atoms, 'S', timestamp))
1258                         goto out_put;
1259         }
1260
1261         BUG_ON(list_empty(&atoms->work_list));
1262
1263         atom = list_entry(atoms->work_list.prev, struct work_atom, list);
1264
1265         /*
1266          * As we do not guarantee the wakeup event happens when
1267          * task is out of run queue, also may happen when task is
1268          * on run queue and wakeup only change ->state to TASK_RUNNING,
1269          * then we should not set the ->wake_up_time when wake up a
1270          * task which is on run queue.
1271          *
1272          * You WILL be missing events if you've recorded only
1273          * one CPU, or are only looking at only one, so don't
1274          * skip in this case.
1275          */
1276         if (sched->profile_cpu == -1 && atom->state != THREAD_SLEEPING)
1277                 goto out_ok;
1278
1279         sched->nr_timestamps++;
1280         if (atom->sched_out_time > timestamp) {
1281                 sched->nr_unordered_timestamps++;
1282                 goto out_ok;
1283         }
1284
1285         atom->state = THREAD_WAIT_CPU;
1286         atom->wake_up_time = timestamp;
1287 out_ok:
1288         err = 0;
1289 out_put:
1290         thread__put(wakee);
1291         return err;
1292 }
1293
1294 static int latency_migrate_task_event(struct perf_sched *sched,
1295                                       struct evsel *evsel,
1296                                       struct perf_sample *sample,
1297                                       struct machine *machine)
1298 {
1299         const u32 pid = evsel__intval(evsel, sample, "pid");
1300         u64 timestamp = sample->time;
1301         struct work_atoms *atoms;
1302         struct work_atom *atom;
1303         struct thread *migrant;
1304         int err = -1;
1305
1306         /*
1307          * Only need to worry about migration when profiling one CPU.
1308          */
1309         if (sched->profile_cpu == -1)
1310                 return 0;
1311
1312         migrant = machine__findnew_thread(machine, -1, pid);
1313         if (migrant == NULL)
1314                 return -1;
1315         atoms = thread_atoms_search(&sched->atom_root, migrant, &sched->cmp_pid);
1316         if (!atoms) {
1317                 if (thread_atoms_insert(sched, migrant))
1318                         goto out_put;
1319                 register_pid(sched, migrant->tid, thread__comm_str(migrant));
1320                 atoms = thread_atoms_search(&sched->atom_root, migrant, &sched->cmp_pid);
1321                 if (!atoms) {
1322                         pr_err("migration-event: Internal tree error");
1323                         goto out_put;
1324                 }
1325                 if (add_sched_out_event(atoms, 'R', timestamp))
1326                         goto out_put;
1327         }
1328
1329         BUG_ON(list_empty(&atoms->work_list));
1330
1331         atom = list_entry(atoms->work_list.prev, struct work_atom, list);
1332         atom->sched_in_time = atom->sched_out_time = atom->wake_up_time = timestamp;
1333
1334         sched->nr_timestamps++;
1335
1336         if (atom->sched_out_time > timestamp)
1337                 sched->nr_unordered_timestamps++;
1338         err = 0;
1339 out_put:
1340         thread__put(migrant);
1341         return err;
1342 }
1343
1344 static void output_lat_thread(struct perf_sched *sched, struct work_atoms *work_list)
1345 {
1346         int i;
1347         int ret;
1348         u64 avg;
1349         char max_lat_start[32], max_lat_end[32];
1350
1351         if (!work_list->nb_atoms)
1352                 return;
1353         /*
1354          * Ignore idle threads:
1355          */
1356         if (!strcmp(thread__comm_str(work_list->thread), "swapper"))
1357                 return;
1358
1359         sched->all_runtime += work_list->total_runtime;
1360         sched->all_count   += work_list->nb_atoms;
1361
1362         if (work_list->num_merged > 1)
1363                 ret = printf("  %s:(%d) ", thread__comm_str(work_list->thread), work_list->num_merged);
1364         else
1365                 ret = printf("  %s:%d ", thread__comm_str(work_list->thread), work_list->thread->tid);
1366
1367         for (i = 0; i < 24 - ret; i++)
1368                 printf(" ");
1369
1370         avg = work_list->total_lat / work_list->nb_atoms;
1371         timestamp__scnprintf_usec(work_list->max_lat_start, max_lat_start, sizeof(max_lat_start));
1372         timestamp__scnprintf_usec(work_list->max_lat_end, max_lat_end, sizeof(max_lat_end));
1373
1374         printf("|%11.3f ms |%9" PRIu64 " | avg:%8.3f ms | max:%8.3f ms | max start: %12s s | max end: %12s s\n",
1375               (double)work_list->total_runtime / NSEC_PER_MSEC,
1376                  work_list->nb_atoms, (double)avg / NSEC_PER_MSEC,
1377                  (double)work_list->max_lat / NSEC_PER_MSEC,
1378                  max_lat_start, max_lat_end);
1379 }
1380
1381 static int pid_cmp(struct work_atoms *l, struct work_atoms *r)
1382 {
1383         if (l->thread == r->thread)
1384                 return 0;
1385         if (l->thread->tid < r->thread->tid)
1386                 return -1;
1387         if (l->thread->tid > r->thread->tid)
1388                 return 1;
1389         return (int)(l->thread - r->thread);
1390 }
1391
1392 static int avg_cmp(struct work_atoms *l, struct work_atoms *r)
1393 {
1394         u64 avgl, avgr;
1395
1396         if (!l->nb_atoms)
1397                 return -1;
1398
1399         if (!r->nb_atoms)
1400                 return 1;
1401
1402         avgl = l->total_lat / l->nb_atoms;
1403         avgr = r->total_lat / r->nb_atoms;
1404
1405         if (avgl < avgr)
1406                 return -1;
1407         if (avgl > avgr)
1408                 return 1;
1409
1410         return 0;
1411 }
1412
1413 static int max_cmp(struct work_atoms *l, struct work_atoms *r)
1414 {
1415         if (l->max_lat < r->max_lat)
1416                 return -1;
1417         if (l->max_lat > r->max_lat)
1418                 return 1;
1419
1420         return 0;
1421 }
1422
1423 static int switch_cmp(struct work_atoms *l, struct work_atoms *r)
1424 {
1425         if (l->nb_atoms < r->nb_atoms)
1426                 return -1;
1427         if (l->nb_atoms > r->nb_atoms)
1428                 return 1;
1429
1430         return 0;
1431 }
1432
1433 static int runtime_cmp(struct work_atoms *l, struct work_atoms *r)
1434 {
1435         if (l->total_runtime < r->total_runtime)
1436                 return -1;
1437         if (l->total_runtime > r->total_runtime)
1438                 return 1;
1439
1440         return 0;
1441 }
1442
1443 static int sort_dimension__add(const char *tok, struct list_head *list)
1444 {
1445         size_t i;
1446         static struct sort_dimension avg_sort_dimension = {
1447                 .name = "avg",
1448                 .cmp  = avg_cmp,
1449         };
1450         static struct sort_dimension max_sort_dimension = {
1451                 .name = "max",
1452                 .cmp  = max_cmp,
1453         };
1454         static struct sort_dimension pid_sort_dimension = {
1455                 .name = "pid",
1456                 .cmp  = pid_cmp,
1457         };
1458         static struct sort_dimension runtime_sort_dimension = {
1459                 .name = "runtime",
1460                 .cmp  = runtime_cmp,
1461         };
1462         static struct sort_dimension switch_sort_dimension = {
1463                 .name = "switch",
1464                 .cmp  = switch_cmp,
1465         };
1466         struct sort_dimension *available_sorts[] = {
1467                 &pid_sort_dimension,
1468                 &avg_sort_dimension,
1469                 &max_sort_dimension,
1470                 &switch_sort_dimension,
1471                 &runtime_sort_dimension,
1472         };
1473
1474         for (i = 0; i < ARRAY_SIZE(available_sorts); i++) {
1475                 if (!strcmp(available_sorts[i]->name, tok)) {
1476                         list_add_tail(&available_sorts[i]->list, list);
1477
1478                         return 0;
1479                 }
1480         }
1481
1482         return -1;
1483 }
1484
1485 static void perf_sched__sort_lat(struct perf_sched *sched)
1486 {
1487         struct rb_node *node;
1488         struct rb_root_cached *root = &sched->atom_root;
1489 again:
1490         for (;;) {
1491                 struct work_atoms *data;
1492                 node = rb_first_cached(root);
1493                 if (!node)
1494                         break;
1495
1496                 rb_erase_cached(node, root);
1497                 data = rb_entry(node, struct work_atoms, node);
1498                 __thread_latency_insert(&sched->sorted_atom_root, data, &sched->sort_list);
1499         }
1500         if (root == &sched->atom_root) {
1501                 root = &sched->merged_atom_root;
1502                 goto again;
1503         }
1504 }
1505
1506 static int process_sched_wakeup_event(struct perf_tool *tool,
1507                                       struct evsel *evsel,
1508                                       struct perf_sample *sample,
1509                                       struct machine *machine)
1510 {
1511         struct perf_sched *sched = container_of(tool, struct perf_sched, tool);
1512
1513         if (sched->tp_handler->wakeup_event)
1514                 return sched->tp_handler->wakeup_event(sched, evsel, sample, machine);
1515
1516         return 0;
1517 }
1518
1519 union map_priv {
1520         void    *ptr;
1521         bool     color;
1522 };
1523
1524 static bool thread__has_color(struct thread *thread)
1525 {
1526         union map_priv priv = {
1527                 .ptr = thread__priv(thread),
1528         };
1529
1530         return priv.color;
1531 }
1532
1533 static struct thread*
1534 map__findnew_thread(struct perf_sched *sched, struct machine *machine, pid_t pid, pid_t tid)
1535 {
1536         struct thread *thread = machine__findnew_thread(machine, pid, tid);
1537         union map_priv priv = {
1538                 .color = false,
1539         };
1540
1541         if (!sched->map.color_pids || !thread || thread__priv(thread))
1542                 return thread;
1543
1544         if (thread_map__has(sched->map.color_pids, tid))
1545                 priv.color = true;
1546
1547         thread__set_priv(thread, priv.ptr);
1548         return thread;
1549 }
1550
1551 static int map_switch_event(struct perf_sched *sched, struct evsel *evsel,
1552                             struct perf_sample *sample, struct machine *machine)
1553 {
1554         const u32 next_pid = evsel__intval(evsel, sample, "next_pid");
1555         struct thread *sched_in;
1556         struct thread_runtime *tr;
1557         int new_shortname;
1558         u64 timestamp0, timestamp = sample->time;
1559         s64 delta;
1560         int i;
1561         struct perf_cpu this_cpu = {
1562                 .cpu = sample->cpu,
1563         };
1564         int cpus_nr;
1565         bool new_cpu = false;
1566         const char *color = PERF_COLOR_NORMAL;
1567         char stimestamp[32];
1568
1569         BUG_ON(this_cpu.cpu >= MAX_CPUS || this_cpu.cpu < 0);
1570
1571         if (this_cpu.cpu > sched->max_cpu.cpu)
1572                 sched->max_cpu = this_cpu;
1573
1574         if (sched->map.comp) {
1575                 cpus_nr = bitmap_weight(sched->map.comp_cpus_mask, MAX_CPUS);
1576                 if (!test_and_set_bit(this_cpu.cpu, sched->map.comp_cpus_mask)) {
1577                         sched->map.comp_cpus[cpus_nr++] = this_cpu;
1578                         new_cpu = true;
1579                 }
1580         } else
1581                 cpus_nr = sched->max_cpu.cpu;
1582
1583         timestamp0 = sched->cpu_last_switched[this_cpu.cpu];
1584         sched->cpu_last_switched[this_cpu.cpu] = timestamp;
1585         if (timestamp0)
1586                 delta = timestamp - timestamp0;
1587         else
1588                 delta = 0;
1589
1590         if (delta < 0) {
1591                 pr_err("hm, delta: %" PRIu64 " < 0 ?\n", delta);
1592                 return -1;
1593         }
1594
1595         sched_in = map__findnew_thread(sched, machine, -1, next_pid);
1596         if (sched_in == NULL)
1597                 return -1;
1598
1599         tr = thread__get_runtime(sched_in);
1600         if (tr == NULL) {
1601                 thread__put(sched_in);
1602                 return -1;
1603         }
1604
1605         sched->curr_thread[this_cpu.cpu] = thread__get(sched_in);
1606
1607         printf("  ");
1608
1609         new_shortname = 0;
1610         if (!tr->shortname[0]) {
1611                 if (!strcmp(thread__comm_str(sched_in), "swapper")) {
1612                         /*
1613                          * Don't allocate a letter-number for swapper:0
1614                          * as a shortname. Instead, we use '.' for it.
1615                          */
1616                         tr->shortname[0] = '.';
1617                         tr->shortname[1] = ' ';
1618                 } else {
1619                         tr->shortname[0] = sched->next_shortname1;
1620                         tr->shortname[1] = sched->next_shortname2;
1621
1622                         if (sched->next_shortname1 < 'Z') {
1623                                 sched->next_shortname1++;
1624                         } else {
1625                                 sched->next_shortname1 = 'A';
1626                                 if (sched->next_shortname2 < '9')
1627                                         sched->next_shortname2++;
1628                                 else
1629                                         sched->next_shortname2 = '0';
1630                         }
1631                 }
1632                 new_shortname = 1;
1633         }
1634
1635         for (i = 0; i < cpus_nr; i++) {
1636                 struct perf_cpu cpu = {
1637                         .cpu = sched->map.comp ? sched->map.comp_cpus[i].cpu : i,
1638                 };
1639                 struct thread *curr_thread = sched->curr_thread[cpu.cpu];
1640                 struct thread_runtime *curr_tr;
1641                 const char *pid_color = color;
1642                 const char *cpu_color = color;
1643
1644                 if (curr_thread && thread__has_color(curr_thread))
1645                         pid_color = COLOR_PIDS;
1646
1647                 if (sched->map.cpus && !perf_cpu_map__has(sched->map.cpus, cpu))
1648                         continue;
1649
1650                 if (sched->map.color_cpus && perf_cpu_map__has(sched->map.color_cpus, cpu))
1651                         cpu_color = COLOR_CPUS;
1652
1653                 if (cpu.cpu != this_cpu.cpu)
1654                         color_fprintf(stdout, color, " ");
1655                 else
1656                         color_fprintf(stdout, cpu_color, "*");
1657
1658                 if (sched->curr_thread[cpu.cpu]) {
1659                         curr_tr = thread__get_runtime(sched->curr_thread[cpu.cpu]);
1660                         if (curr_tr == NULL) {
1661                                 thread__put(sched_in);
1662                                 return -1;
1663                         }
1664                         color_fprintf(stdout, pid_color, "%2s ", curr_tr->shortname);
1665                 } else
1666                         color_fprintf(stdout, color, "   ");
1667         }
1668
1669         if (sched->map.cpus && !perf_cpu_map__has(sched->map.cpus, this_cpu))
1670                 goto out;
1671
1672         timestamp__scnprintf_usec(timestamp, stimestamp, sizeof(stimestamp));
1673         color_fprintf(stdout, color, "  %12s secs ", stimestamp);
1674         if (new_shortname || tr->comm_changed || (verbose > 0 && sched_in->tid)) {
1675                 const char *pid_color = color;
1676
1677                 if (thread__has_color(sched_in))
1678                         pid_color = COLOR_PIDS;
1679
1680                 color_fprintf(stdout, pid_color, "%s => %s:%d",
1681                        tr->shortname, thread__comm_str(sched_in), sched_in->tid);
1682                 tr->comm_changed = false;
1683         }
1684
1685         if (sched->map.comp && new_cpu)
1686                 color_fprintf(stdout, color, " (CPU %d)", this_cpu);
1687
1688 out:
1689         color_fprintf(stdout, color, "\n");
1690
1691         thread__put(sched_in);
1692
1693         return 0;
1694 }
1695
1696 static int process_sched_switch_event(struct perf_tool *tool,
1697                                       struct evsel *evsel,
1698                                       struct perf_sample *sample,
1699                                       struct machine *machine)
1700 {
1701         struct perf_sched *sched = container_of(tool, struct perf_sched, tool);
1702         int this_cpu = sample->cpu, err = 0;
1703         u32 prev_pid = evsel__intval(evsel, sample, "prev_pid"),
1704             next_pid = evsel__intval(evsel, sample, "next_pid");
1705
1706         if (sched->curr_pid[this_cpu] != (u32)-1) {
1707                 /*
1708                  * Are we trying to switch away a PID that is
1709                  * not current?
1710                  */
1711                 if (sched->curr_pid[this_cpu] != prev_pid)
1712                         sched->nr_context_switch_bugs++;
1713         }
1714
1715         if (sched->tp_handler->switch_event)
1716                 err = sched->tp_handler->switch_event(sched, evsel, sample, machine);
1717
1718         sched->curr_pid[this_cpu] = next_pid;
1719         return err;
1720 }
1721
1722 static int process_sched_runtime_event(struct perf_tool *tool,
1723                                        struct evsel *evsel,
1724                                        struct perf_sample *sample,
1725                                        struct machine *machine)
1726 {
1727         struct perf_sched *sched = container_of(tool, struct perf_sched, tool);
1728
1729         if (sched->tp_handler->runtime_event)
1730                 return sched->tp_handler->runtime_event(sched, evsel, sample, machine);
1731
1732         return 0;
1733 }
1734
1735 static int perf_sched__process_fork_event(struct perf_tool *tool,
1736                                           union perf_event *event,
1737                                           struct perf_sample *sample,
1738                                           struct machine *machine)
1739 {
1740         struct perf_sched *sched = container_of(tool, struct perf_sched, tool);
1741
1742         /* run the fork event through the perf machinery */
1743         perf_event__process_fork(tool, event, sample, machine);
1744
1745         /* and then run additional processing needed for this command */
1746         if (sched->tp_handler->fork_event)
1747                 return sched->tp_handler->fork_event(sched, event, machine);
1748
1749         return 0;
1750 }
1751
1752 static int process_sched_migrate_task_event(struct perf_tool *tool,
1753                                             struct evsel *evsel,
1754                                             struct perf_sample *sample,
1755                                             struct machine *machine)
1756 {
1757         struct perf_sched *sched = container_of(tool, struct perf_sched, tool);
1758
1759         if (sched->tp_handler->migrate_task_event)
1760                 return sched->tp_handler->migrate_task_event(sched, evsel, sample, machine);
1761
1762         return 0;
1763 }
1764
1765 typedef int (*tracepoint_handler)(struct perf_tool *tool,
1766                                   struct evsel *evsel,
1767                                   struct perf_sample *sample,
1768                                   struct machine *machine);
1769
1770 static int perf_sched__process_tracepoint_sample(struct perf_tool *tool __maybe_unused,
1771                                                  union perf_event *event __maybe_unused,
1772                                                  struct perf_sample *sample,
1773                                                  struct evsel *evsel,
1774                                                  struct machine *machine)
1775 {
1776         int err = 0;
1777
1778         if (evsel->handler != NULL) {
1779                 tracepoint_handler f = evsel->handler;
1780                 err = f(tool, evsel, sample, machine);
1781         }
1782
1783         return err;
1784 }
1785
1786 static int perf_sched__process_comm(struct perf_tool *tool __maybe_unused,
1787                                     union perf_event *event,
1788                                     struct perf_sample *sample,
1789                                     struct machine *machine)
1790 {
1791         struct thread *thread;
1792         struct thread_runtime *tr;
1793         int err;
1794
1795         err = perf_event__process_comm(tool, event, sample, machine);
1796         if (err)
1797                 return err;
1798
1799         thread = machine__find_thread(machine, sample->pid, sample->tid);
1800         if (!thread) {
1801                 pr_err("Internal error: can't find thread\n");
1802                 return -1;
1803         }
1804
1805         tr = thread__get_runtime(thread);
1806         if (tr == NULL) {
1807                 thread__put(thread);
1808                 return -1;
1809         }
1810
1811         tr->comm_changed = true;
1812         thread__put(thread);
1813
1814         return 0;
1815 }
1816
1817 static int perf_sched__read_events(struct perf_sched *sched)
1818 {
1819         const struct evsel_str_handler handlers[] = {
1820                 { "sched:sched_switch",       process_sched_switch_event, },
1821                 { "sched:sched_stat_runtime", process_sched_runtime_event, },
1822                 { "sched:sched_wakeup",       process_sched_wakeup_event, },
1823                 { "sched:sched_wakeup_new",   process_sched_wakeup_event, },
1824                 { "sched:sched_migrate_task", process_sched_migrate_task_event, },
1825         };
1826         struct perf_session *session;
1827         struct perf_data data = {
1828                 .path  = input_name,
1829                 .mode  = PERF_DATA_MODE_READ,
1830                 .force = sched->force,
1831         };
1832         int rc = -1;
1833
1834         session = perf_session__new(&data, &sched->tool);
1835         if (IS_ERR(session)) {
1836                 pr_debug("Error creating perf session");
1837                 return PTR_ERR(session);
1838         }
1839
1840         symbol__init(&session->header.env);
1841
1842         if (perf_session__set_tracepoints_handlers(session, handlers))
1843                 goto out_delete;
1844
1845         if (perf_session__has_traces(session, "record -R")) {
1846                 int err = perf_session__process_events(session);
1847                 if (err) {
1848                         pr_err("Failed to process events, error %d", err);
1849                         goto out_delete;
1850                 }
1851
1852                 sched->nr_events      = session->evlist->stats.nr_events[0];
1853                 sched->nr_lost_events = session->evlist->stats.total_lost;
1854                 sched->nr_lost_chunks = session->evlist->stats.nr_events[PERF_RECORD_LOST];
1855         }
1856
1857         rc = 0;
1858 out_delete:
1859         perf_session__delete(session);
1860         return rc;
1861 }
1862
1863 /*
1864  * scheduling times are printed as msec.usec
1865  */
1866 static inline void print_sched_time(unsigned long long nsecs, int width)
1867 {
1868         unsigned long msecs;
1869         unsigned long usecs;
1870
1871         msecs  = nsecs / NSEC_PER_MSEC;
1872         nsecs -= msecs * NSEC_PER_MSEC;
1873         usecs  = nsecs / NSEC_PER_USEC;
1874         printf("%*lu.%03lu ", width, msecs, usecs);
1875 }
1876
1877 /*
1878  * returns runtime data for event, allocating memory for it the
1879  * first time it is used.
1880  */
1881 static struct evsel_runtime *evsel__get_runtime(struct evsel *evsel)
1882 {
1883         struct evsel_runtime *r = evsel->priv;
1884
1885         if (r == NULL) {
1886                 r = zalloc(sizeof(struct evsel_runtime));
1887                 evsel->priv = r;
1888         }
1889
1890         return r;
1891 }
1892
1893 /*
1894  * save last time event was seen per cpu
1895  */
1896 static void evsel__save_time(struct evsel *evsel, u64 timestamp, u32 cpu)
1897 {
1898         struct evsel_runtime *r = evsel__get_runtime(evsel);
1899
1900         if (r == NULL)
1901                 return;
1902
1903         if ((cpu >= r->ncpu) || (r->last_time == NULL)) {
1904                 int i, n = __roundup_pow_of_two(cpu+1);
1905                 void *p = r->last_time;
1906
1907                 p = realloc(r->last_time, n * sizeof(u64));
1908                 if (!p)
1909                         return;
1910
1911                 r->last_time = p;
1912                 for (i = r->ncpu; i < n; ++i)
1913                         r->last_time[i] = (u64) 0;
1914
1915                 r->ncpu = n;
1916         }
1917
1918         r->last_time[cpu] = timestamp;
1919 }
1920
1921 /* returns last time this event was seen on the given cpu */
1922 static u64 evsel__get_time(struct evsel *evsel, u32 cpu)
1923 {
1924         struct evsel_runtime *r = evsel__get_runtime(evsel);
1925
1926         if ((r == NULL) || (r->last_time == NULL) || (cpu >= r->ncpu))
1927                 return 0;
1928
1929         return r->last_time[cpu];
1930 }
1931
1932 static int comm_width = 30;
1933
1934 static char *timehist_get_commstr(struct thread *thread)
1935 {
1936         static char str[32];
1937         const char *comm = thread__comm_str(thread);
1938         pid_t tid = thread->tid;
1939         pid_t pid = thread->pid_;
1940         int n;
1941
1942         if (pid == 0)
1943                 n = scnprintf(str, sizeof(str), "%s", comm);
1944
1945         else if (tid != pid)
1946                 n = scnprintf(str, sizeof(str), "%s[%d/%d]", comm, tid, pid);
1947
1948         else
1949                 n = scnprintf(str, sizeof(str), "%s[%d]", comm, tid);
1950
1951         if (n > comm_width)
1952                 comm_width = n;
1953
1954         return str;
1955 }
1956
1957 static void timehist_header(struct perf_sched *sched)
1958 {
1959         u32 ncpus = sched->max_cpu.cpu + 1;
1960         u32 i, j;
1961
1962         printf("%15s %6s ", "time", "cpu");
1963
1964         if (sched->show_cpu_visual) {
1965                 printf(" ");
1966                 for (i = 0, j = 0; i < ncpus; ++i) {
1967                         printf("%x", j++);
1968                         if (j > 15)
1969                                 j = 0;
1970                 }
1971                 printf(" ");
1972         }
1973
1974         printf(" %-*s  %9s  %9s  %9s", comm_width,
1975                 "task name", "wait time", "sch delay", "run time");
1976
1977         if (sched->show_state)
1978                 printf("  %s", "state");
1979
1980         printf("\n");
1981
1982         /*
1983          * units row
1984          */
1985         printf("%15s %-6s ", "", "");
1986
1987         if (sched->show_cpu_visual)
1988                 printf(" %*s ", ncpus, "");
1989
1990         printf(" %-*s  %9s  %9s  %9s", comm_width,
1991                "[tid/pid]", "(msec)", "(msec)", "(msec)");
1992
1993         if (sched->show_state)
1994                 printf("  %5s", "");
1995
1996         printf("\n");
1997
1998         /*
1999          * separator
2000          */
2001         printf("%.15s %.6s ", graph_dotted_line, graph_dotted_line);
2002
2003         if (sched->show_cpu_visual)
2004                 printf(" %.*s ", ncpus, graph_dotted_line);
2005
2006         printf(" %.*s  %.9s  %.9s  %.9s", comm_width,
2007                 graph_dotted_line, graph_dotted_line, graph_dotted_line,
2008                 graph_dotted_line);
2009
2010         if (sched->show_state)
2011                 printf("  %.5s", graph_dotted_line);
2012
2013         printf("\n");
2014 }
2015
2016 static char task_state_char(struct thread *thread, int state)
2017 {
2018         static const char state_to_char[] = TASK_STATE_TO_CHAR_STR;
2019         unsigned bit = state ? ffs(state) : 0;
2020
2021         /* 'I' for idle */
2022         if (thread->tid == 0)
2023                 return 'I';
2024
2025         return bit < sizeof(state_to_char) - 1 ? state_to_char[bit] : '?';
2026 }
2027
2028 static void timehist_print_sample(struct perf_sched *sched,
2029                                   struct evsel *evsel,
2030                                   struct perf_sample *sample,
2031                                   struct addr_location *al,
2032                                   struct thread *thread,
2033                                   u64 t, int state)
2034 {
2035         struct thread_runtime *tr = thread__priv(thread);
2036         const char *next_comm = evsel__strval(evsel, sample, "next_comm");
2037         const u32 next_pid = evsel__intval(evsel, sample, "next_pid");
2038         u32 max_cpus = sched->max_cpu.cpu + 1;
2039         char tstr[64];
2040         char nstr[30];
2041         u64 wait_time;
2042
2043         if (cpu_list && !test_bit(sample->cpu, cpu_bitmap))
2044                 return;
2045
2046         timestamp__scnprintf_usec(t, tstr, sizeof(tstr));
2047         printf("%15s [%04d] ", tstr, sample->cpu);
2048
2049         if (sched->show_cpu_visual) {
2050                 u32 i;
2051                 char c;
2052
2053                 printf(" ");
2054                 for (i = 0; i < max_cpus; ++i) {
2055                         /* flag idle times with 'i'; others are sched events */
2056                         if (i == sample->cpu)
2057                                 c = (thread->tid == 0) ? 'i' : 's';
2058                         else
2059                                 c = ' ';
2060                         printf("%c", c);
2061                 }
2062                 printf(" ");
2063         }
2064
2065         printf(" %-*s ", comm_width, timehist_get_commstr(thread));
2066
2067         wait_time = tr->dt_sleep + tr->dt_iowait + tr->dt_preempt;
2068         print_sched_time(wait_time, 6);
2069
2070         print_sched_time(tr->dt_delay, 6);
2071         print_sched_time(tr->dt_run, 6);
2072
2073         if (sched->show_state)
2074                 printf(" %5c ", task_state_char(thread, state));
2075
2076         if (sched->show_next) {
2077                 snprintf(nstr, sizeof(nstr), "next: %s[%d]", next_comm, next_pid);
2078                 printf(" %-*s", comm_width, nstr);
2079         }
2080
2081         if (sched->show_wakeups && !sched->show_next)
2082                 printf("  %-*s", comm_width, "");
2083
2084         if (thread->tid == 0)
2085                 goto out;
2086
2087         if (sched->show_callchain)
2088                 printf("  ");
2089
2090         sample__fprintf_sym(sample, al, 0,
2091                             EVSEL__PRINT_SYM | EVSEL__PRINT_ONELINE |
2092                             EVSEL__PRINT_CALLCHAIN_ARROW |
2093                             EVSEL__PRINT_SKIP_IGNORED,
2094                             &callchain_cursor, symbol_conf.bt_stop_list,  stdout);
2095
2096 out:
2097         printf("\n");
2098 }
2099
2100 /*
2101  * Explanation of delta-time stats:
2102  *
2103  *            t = time of current schedule out event
2104  *        tprev = time of previous sched out event
2105  *                also time of schedule-in event for current task
2106  *    last_time = time of last sched change event for current task
2107  *                (i.e, time process was last scheduled out)
2108  * ready_to_run = time of wakeup for current task
2109  *
2110  * -----|------------|------------|------------|------
2111  *    last         ready        tprev          t
2112  *    time         to run
2113  *
2114  *      |-------- dt_wait --------|
2115  *                   |- dt_delay -|-- dt_run --|
2116  *
2117  *   dt_run = run time of current task
2118  *  dt_wait = time between last schedule out event for task and tprev
2119  *            represents time spent off the cpu
2120  * dt_delay = time between wakeup and schedule-in of task
2121  */
2122
2123 static void timehist_update_runtime_stats(struct thread_runtime *r,
2124                                          u64 t, u64 tprev)
2125 {
2126         r->dt_delay   = 0;
2127         r->dt_sleep   = 0;
2128         r->dt_iowait  = 0;
2129         r->dt_preempt = 0;
2130         r->dt_run     = 0;
2131
2132         if (tprev) {
2133                 r->dt_run = t - tprev;
2134                 if (r->ready_to_run) {
2135                         if (r->ready_to_run > tprev)
2136                                 pr_debug("time travel: wakeup time for task > previous sched_switch event\n");
2137                         else
2138                                 r->dt_delay = tprev - r->ready_to_run;
2139                 }
2140
2141                 if (r->last_time > tprev)
2142                         pr_debug("time travel: last sched out time for task > previous sched_switch event\n");
2143                 else if (r->last_time) {
2144                         u64 dt_wait = tprev - r->last_time;
2145
2146                         if (r->last_state == TASK_RUNNING)
2147                                 r->dt_preempt = dt_wait;
2148                         else if (r->last_state == TASK_UNINTERRUPTIBLE)
2149                                 r->dt_iowait = dt_wait;
2150                         else
2151                                 r->dt_sleep = dt_wait;
2152                 }
2153         }
2154
2155         update_stats(&r->run_stats, r->dt_run);
2156
2157         r->total_run_time     += r->dt_run;
2158         r->total_delay_time   += r->dt_delay;
2159         r->total_sleep_time   += r->dt_sleep;
2160         r->total_iowait_time  += r->dt_iowait;
2161         r->total_preempt_time += r->dt_preempt;
2162 }
2163
2164 static bool is_idle_sample(struct perf_sample *sample,
2165                            struct evsel *evsel)
2166 {
2167         /* pid 0 == swapper == idle task */
2168         if (strcmp(evsel__name(evsel), "sched:sched_switch") == 0)
2169                 return evsel__intval(evsel, sample, "prev_pid") == 0;
2170
2171         return sample->pid == 0;
2172 }
2173
2174 static void save_task_callchain(struct perf_sched *sched,
2175                                 struct perf_sample *sample,
2176                                 struct evsel *evsel,
2177                                 struct machine *machine)
2178 {
2179         struct callchain_cursor *cursor = &callchain_cursor;
2180         struct thread *thread;
2181
2182         /* want main thread for process - has maps */
2183         thread = machine__findnew_thread(machine, sample->pid, sample->pid);
2184         if (thread == NULL) {
2185                 pr_debug("Failed to get thread for pid %d.\n", sample->pid);
2186                 return;
2187         }
2188
2189         if (!sched->show_callchain || sample->callchain == NULL)
2190                 return;
2191
2192         if (thread__resolve_callchain(thread, cursor, evsel, sample,
2193                                       NULL, NULL, sched->max_stack + 2) != 0) {
2194                 if (verbose > 0)
2195                         pr_err("Failed to resolve callchain. Skipping\n");
2196
2197                 return;
2198         }
2199
2200         callchain_cursor_commit(cursor);
2201
2202         while (true) {
2203                 struct callchain_cursor_node *node;
2204                 struct symbol *sym;
2205
2206                 node = callchain_cursor_current(cursor);
2207                 if (node == NULL)
2208                         break;
2209
2210                 sym = node->ms.sym;
2211                 if (sym) {
2212                         if (!strcmp(sym->name, "schedule") ||
2213                             !strcmp(sym->name, "__schedule") ||
2214                             !strcmp(sym->name, "preempt_schedule"))
2215                                 sym->ignore = 1;
2216                 }
2217
2218                 callchain_cursor_advance(cursor);
2219         }
2220 }
2221
2222 static int init_idle_thread(struct thread *thread)
2223 {
2224         struct idle_thread_runtime *itr;
2225
2226         thread__set_comm(thread, idle_comm, 0);
2227
2228         itr = zalloc(sizeof(*itr));
2229         if (itr == NULL)
2230                 return -ENOMEM;
2231
2232         init_stats(&itr->tr.run_stats);
2233         callchain_init(&itr->callchain);
2234         callchain_cursor_reset(&itr->cursor);
2235         thread__set_priv(thread, itr);
2236
2237         return 0;
2238 }
2239
2240 /*
2241  * Track idle stats per cpu by maintaining a local thread
2242  * struct for the idle task on each cpu.
2243  */
2244 static int init_idle_threads(int ncpu)
2245 {
2246         int i, ret;
2247
2248         idle_threads = zalloc(ncpu * sizeof(struct thread *));
2249         if (!idle_threads)
2250                 return -ENOMEM;
2251
2252         idle_max_cpu = ncpu;
2253
2254         /* allocate the actual thread struct if needed */
2255         for (i = 0; i < ncpu; ++i) {
2256                 idle_threads[i] = thread__new(0, 0);
2257                 if (idle_threads[i] == NULL)
2258                         return -ENOMEM;
2259
2260                 ret = init_idle_thread(idle_threads[i]);
2261                 if (ret < 0)
2262                         return ret;
2263         }
2264
2265         return 0;
2266 }
2267
2268 static void free_idle_threads(void)
2269 {
2270         int i;
2271
2272         if (idle_threads == NULL)
2273                 return;
2274
2275         for (i = 0; i < idle_max_cpu; ++i) {
2276                 if ((idle_threads[i]))
2277                         thread__delete(idle_threads[i]);
2278         }
2279
2280         free(idle_threads);
2281 }
2282
2283 static struct thread *get_idle_thread(int cpu)
2284 {
2285         /*
2286          * expand/allocate array of pointers to local thread
2287          * structs if needed
2288          */
2289         if ((cpu >= idle_max_cpu) || (idle_threads == NULL)) {
2290                 int i, j = __roundup_pow_of_two(cpu+1);
2291                 void *p;
2292
2293                 p = realloc(idle_threads, j * sizeof(struct thread *));
2294                 if (!p)
2295                         return NULL;
2296
2297                 idle_threads = (struct thread **) p;
2298                 for (i = idle_max_cpu; i < j; ++i)
2299                         idle_threads[i] = NULL;
2300
2301                 idle_max_cpu = j;
2302         }
2303
2304         /* allocate a new thread struct if needed */
2305         if (idle_threads[cpu] == NULL) {
2306                 idle_threads[cpu] = thread__new(0, 0);
2307
2308                 if (idle_threads[cpu]) {
2309                         if (init_idle_thread(idle_threads[cpu]) < 0)
2310                                 return NULL;
2311                 }
2312         }
2313
2314         return idle_threads[cpu];
2315 }
2316
2317 static void save_idle_callchain(struct perf_sched *sched,
2318                                 struct idle_thread_runtime *itr,
2319                                 struct perf_sample *sample)
2320 {
2321         if (!sched->show_callchain || sample->callchain == NULL)
2322                 return;
2323
2324         callchain_cursor__copy(&itr->cursor, &callchain_cursor);
2325 }
2326
2327 static struct thread *timehist_get_thread(struct perf_sched *sched,
2328                                           struct perf_sample *sample,
2329                                           struct machine *machine,
2330                                           struct evsel *evsel)
2331 {
2332         struct thread *thread;
2333
2334         if (is_idle_sample(sample, evsel)) {
2335                 thread = get_idle_thread(sample->cpu);
2336                 if (thread == NULL)
2337                         pr_err("Failed to get idle thread for cpu %d.\n", sample->cpu);
2338
2339         } else {
2340                 /* there were samples with tid 0 but non-zero pid */
2341                 thread = machine__findnew_thread(machine, sample->pid,
2342                                                  sample->tid ?: sample->pid);
2343                 if (thread == NULL) {
2344                         pr_debug("Failed to get thread for tid %d. skipping sample.\n",
2345                                  sample->tid);
2346                 }
2347
2348                 save_task_callchain(sched, sample, evsel, machine);
2349                 if (sched->idle_hist) {
2350                         struct thread *idle;
2351                         struct idle_thread_runtime *itr;
2352
2353                         idle = get_idle_thread(sample->cpu);
2354                         if (idle == NULL) {
2355                                 pr_err("Failed to get idle thread for cpu %d.\n", sample->cpu);
2356                                 return NULL;
2357                         }
2358
2359                         itr = thread__priv(idle);
2360                         if (itr == NULL)
2361                                 return NULL;
2362
2363                         itr->last_thread = thread;
2364
2365                         /* copy task callchain when entering to idle */
2366                         if (evsel__intval(evsel, sample, "next_pid") == 0)
2367                                 save_idle_callchain(sched, itr, sample);
2368                 }
2369         }
2370
2371         return thread;
2372 }
2373
2374 static bool timehist_skip_sample(struct perf_sched *sched,
2375                                  struct thread *thread,
2376                                  struct evsel *evsel,
2377                                  struct perf_sample *sample)
2378 {
2379         bool rc = false;
2380
2381         if (thread__is_filtered(thread)) {
2382                 rc = true;
2383                 sched->skipped_samples++;
2384         }
2385
2386         if (sched->idle_hist) {
2387                 if (strcmp(evsel__name(evsel), "sched:sched_switch"))
2388                         rc = true;
2389                 else if (evsel__intval(evsel, sample, "prev_pid") != 0 &&
2390                          evsel__intval(evsel, sample, "next_pid") != 0)
2391                         rc = true;
2392         }
2393
2394         return rc;
2395 }
2396
2397 static void timehist_print_wakeup_event(struct perf_sched *sched,
2398                                         struct evsel *evsel,
2399                                         struct perf_sample *sample,
2400                                         struct machine *machine,
2401                                         struct thread *awakened)
2402 {
2403         struct thread *thread;
2404         char tstr[64];
2405
2406         thread = machine__findnew_thread(machine, sample->pid, sample->tid);
2407         if (thread == NULL)
2408                 return;
2409
2410         /* show wakeup unless both awakee and awaker are filtered */
2411         if (timehist_skip_sample(sched, thread, evsel, sample) &&
2412             timehist_skip_sample(sched, awakened, evsel, sample)) {
2413                 return;
2414         }
2415
2416         timestamp__scnprintf_usec(sample->time, tstr, sizeof(tstr));
2417         printf("%15s [%04d] ", tstr, sample->cpu);
2418         if (sched->show_cpu_visual)
2419                 printf(" %*s ", sched->max_cpu.cpu + 1, "");
2420
2421         printf(" %-*s ", comm_width, timehist_get_commstr(thread));
2422
2423         /* dt spacer */
2424         printf("  %9s  %9s  %9s ", "", "", "");
2425
2426         printf("awakened: %s", timehist_get_commstr(awakened));
2427
2428         printf("\n");
2429 }
2430
2431 static int timehist_sched_wakeup_ignore(struct perf_tool *tool __maybe_unused,
2432                                         union perf_event *event __maybe_unused,
2433                                         struct evsel *evsel __maybe_unused,
2434                                         struct perf_sample *sample __maybe_unused,
2435                                         struct machine *machine __maybe_unused)
2436 {
2437         return 0;
2438 }
2439
2440 static int timehist_sched_wakeup_event(struct perf_tool *tool,
2441                                        union perf_event *event __maybe_unused,
2442                                        struct evsel *evsel,
2443                                        struct perf_sample *sample,
2444                                        struct machine *machine)
2445 {
2446         struct perf_sched *sched = container_of(tool, struct perf_sched, tool);
2447         struct thread *thread;
2448         struct thread_runtime *tr = NULL;
2449         /* want pid of awakened task not pid in sample */
2450         const u32 pid = evsel__intval(evsel, sample, "pid");
2451
2452         thread = machine__findnew_thread(machine, 0, pid);
2453         if (thread == NULL)
2454                 return -1;
2455
2456         tr = thread__get_runtime(thread);
2457         if (tr == NULL)
2458                 return -1;
2459
2460         if (tr->ready_to_run == 0)
2461                 tr->ready_to_run = sample->time;
2462
2463         /* show wakeups if requested */
2464         if (sched->show_wakeups &&
2465             !perf_time__skip_sample(&sched->ptime, sample->time))
2466                 timehist_print_wakeup_event(sched, evsel, sample, machine, thread);
2467
2468         return 0;
2469 }
2470
2471 static void timehist_print_migration_event(struct perf_sched *sched,
2472                                         struct evsel *evsel,
2473                                         struct perf_sample *sample,
2474                                         struct machine *machine,
2475                                         struct thread *migrated)
2476 {
2477         struct thread *thread;
2478         char tstr[64];
2479         u32 max_cpus;
2480         u32 ocpu, dcpu;
2481
2482         if (sched->summary_only)
2483                 return;
2484
2485         max_cpus = sched->max_cpu.cpu + 1;
2486         ocpu = evsel__intval(evsel, sample, "orig_cpu");
2487         dcpu = evsel__intval(evsel, sample, "dest_cpu");
2488
2489         thread = machine__findnew_thread(machine, sample->pid, sample->tid);
2490         if (thread == NULL)
2491                 return;
2492
2493         if (timehist_skip_sample(sched, thread, evsel, sample) &&
2494             timehist_skip_sample(sched, migrated, evsel, sample)) {
2495                 return;
2496         }
2497
2498         timestamp__scnprintf_usec(sample->time, tstr, sizeof(tstr));
2499         printf("%15s [%04d] ", tstr, sample->cpu);
2500
2501         if (sched->show_cpu_visual) {
2502                 u32 i;
2503                 char c;
2504
2505                 printf("  ");
2506                 for (i = 0; i < max_cpus; ++i) {
2507                         c = (i == sample->cpu) ? 'm' : ' ';
2508                         printf("%c", c);
2509                 }
2510                 printf("  ");
2511         }
2512
2513         printf(" %-*s ", comm_width, timehist_get_commstr(thread));
2514
2515         /* dt spacer */
2516         printf("  %9s  %9s  %9s ", "", "", "");
2517
2518         printf("migrated: %s", timehist_get_commstr(migrated));
2519         printf(" cpu %d => %d", ocpu, dcpu);
2520
2521         printf("\n");
2522 }
2523
2524 static int timehist_migrate_task_event(struct perf_tool *tool,
2525                                        union perf_event *event __maybe_unused,
2526                                        struct evsel *evsel,
2527                                        struct perf_sample *sample,
2528                                        struct machine *machine)
2529 {
2530         struct perf_sched *sched = container_of(tool, struct perf_sched, tool);
2531         struct thread *thread;
2532         struct thread_runtime *tr = NULL;
2533         /* want pid of migrated task not pid in sample */
2534         const u32 pid = evsel__intval(evsel, sample, "pid");
2535
2536         thread = machine__findnew_thread(machine, 0, pid);
2537         if (thread == NULL)
2538                 return -1;
2539
2540         tr = thread__get_runtime(thread);
2541         if (tr == NULL)
2542                 return -1;
2543
2544         tr->migrations++;
2545
2546         /* show migrations if requested */
2547         timehist_print_migration_event(sched, evsel, sample, machine, thread);
2548
2549         return 0;
2550 }
2551
2552 static int timehist_sched_change_event(struct perf_tool *tool,
2553                                        union perf_event *event,
2554                                        struct evsel *evsel,
2555                                        struct perf_sample *sample,
2556                                        struct machine *machine)
2557 {
2558         struct perf_sched *sched = container_of(tool, struct perf_sched, tool);
2559         struct perf_time_interval *ptime = &sched->ptime;
2560         struct addr_location al;
2561         struct thread *thread;
2562         struct thread_runtime *tr = NULL;
2563         u64 tprev, t = sample->time;
2564         int rc = 0;
2565         int state = evsel__intval(evsel, sample, "prev_state");
2566
2567         if (machine__resolve(machine, &al, sample) < 0) {
2568                 pr_err("problem processing %d event. skipping it\n",
2569                        event->header.type);
2570                 rc = -1;
2571                 goto out;
2572         }
2573
2574         thread = timehist_get_thread(sched, sample, machine, evsel);
2575         if (thread == NULL) {
2576                 rc = -1;
2577                 goto out;
2578         }
2579
2580         if (timehist_skip_sample(sched, thread, evsel, sample))
2581                 goto out;
2582
2583         tr = thread__get_runtime(thread);
2584         if (tr == NULL) {
2585                 rc = -1;
2586                 goto out;
2587         }
2588
2589         tprev = evsel__get_time(evsel, sample->cpu);
2590
2591         /*
2592          * If start time given:
2593          * - sample time is under window user cares about - skip sample
2594          * - tprev is under window user cares about  - reset to start of window
2595          */
2596         if (ptime->start && ptime->start > t)
2597                 goto out;
2598
2599         if (tprev && ptime->start > tprev)
2600                 tprev = ptime->start;
2601
2602         /*
2603          * If end time given:
2604          * - previous sched event is out of window - we are done
2605          * - sample time is beyond window user cares about - reset it
2606          *   to close out stats for time window interest
2607          */
2608         if (ptime->end) {
2609                 if (tprev > ptime->end)
2610                         goto out;
2611
2612                 if (t > ptime->end)
2613                         t = ptime->end;
2614         }
2615
2616         if (!sched->idle_hist || thread->tid == 0) {
2617                 if (!cpu_list || test_bit(sample->cpu, cpu_bitmap))
2618                         timehist_update_runtime_stats(tr, t, tprev);
2619
2620                 if (sched->idle_hist) {
2621                         struct idle_thread_runtime *itr = (void *)tr;
2622                         struct thread_runtime *last_tr;
2623
2624                         BUG_ON(thread->tid != 0);
2625
2626                         if (itr->last_thread == NULL)
2627                                 goto out;
2628
2629                         /* add current idle time as last thread's runtime */
2630                         last_tr = thread__get_runtime(itr->last_thread);
2631                         if (last_tr == NULL)
2632                                 goto out;
2633
2634                         timehist_update_runtime_stats(last_tr, t, tprev);
2635                         /*
2636                          * remove delta time of last thread as it's not updated
2637                          * and otherwise it will show an invalid value next
2638                          * time.  we only care total run time and run stat.
2639                          */
2640                         last_tr->dt_run = 0;
2641                         last_tr->dt_delay = 0;
2642                         last_tr->dt_sleep = 0;
2643                         last_tr->dt_iowait = 0;
2644                         last_tr->dt_preempt = 0;
2645
2646                         if (itr->cursor.nr)
2647                                 callchain_append(&itr->callchain, &itr->cursor, t - tprev);
2648
2649                         itr->last_thread = NULL;
2650                 }
2651         }
2652
2653         if (!sched->summary_only)
2654                 timehist_print_sample(sched, evsel, sample, &al, thread, t, state);
2655
2656 out:
2657         if (sched->hist_time.start == 0 && t >= ptime->start)
2658                 sched->hist_time.start = t;
2659         if (ptime->end == 0 || t <= ptime->end)
2660                 sched->hist_time.end = t;
2661
2662         if (tr) {
2663                 /* time of this sched_switch event becomes last time task seen */
2664                 tr->last_time = sample->time;
2665
2666                 /* last state is used to determine where to account wait time */
2667                 tr->last_state = state;
2668
2669                 /* sched out event for task so reset ready to run time */
2670                 tr->ready_to_run = 0;
2671         }
2672
2673         evsel__save_time(evsel, sample->time, sample->cpu);
2674
2675         return rc;
2676 }
2677
2678 static int timehist_sched_switch_event(struct perf_tool *tool,
2679                              union perf_event *event,
2680                              struct evsel *evsel,
2681                              struct perf_sample *sample,
2682                              struct machine *machine __maybe_unused)
2683 {
2684         return timehist_sched_change_event(tool, event, evsel, sample, machine);
2685 }
2686
2687 static int process_lost(struct perf_tool *tool __maybe_unused,
2688                         union perf_event *event,
2689                         struct perf_sample *sample,
2690                         struct machine *machine __maybe_unused)
2691 {
2692         char tstr[64];
2693
2694         timestamp__scnprintf_usec(sample->time, tstr, sizeof(tstr));
2695         printf("%15s ", tstr);
2696         printf("lost %" PRI_lu64 " events on cpu %d\n", event->lost.lost, sample->cpu);
2697
2698         return 0;
2699 }
2700
2701
2702 static void print_thread_runtime(struct thread *t,
2703                                  struct thread_runtime *r)
2704 {
2705         double mean = avg_stats(&r->run_stats);
2706         float stddev;
2707
2708         printf("%*s   %5d  %9" PRIu64 " ",
2709                comm_width, timehist_get_commstr(t), t->ppid,
2710                (u64) r->run_stats.n);
2711
2712         print_sched_time(r->total_run_time, 8);
2713         stddev = rel_stddev_stats(stddev_stats(&r->run_stats), mean);
2714         print_sched_time(r->run_stats.min, 6);
2715         printf(" ");
2716         print_sched_time((u64) mean, 6);
2717         printf(" ");
2718         print_sched_time(r->run_stats.max, 6);
2719         printf("  ");
2720         printf("%5.2f", stddev);
2721         printf("   %5" PRIu64, r->migrations);
2722         printf("\n");
2723 }
2724
2725 static void print_thread_waittime(struct thread *t,
2726                                   struct thread_runtime *r)
2727 {
2728         printf("%*s   %5d  %9" PRIu64 " ",
2729                comm_width, timehist_get_commstr(t), t->ppid,
2730                (u64) r->run_stats.n);
2731
2732         print_sched_time(r->total_run_time, 8);
2733         print_sched_time(r->total_sleep_time, 6);
2734         printf(" ");
2735         print_sched_time(r->total_iowait_time, 6);
2736         printf(" ");
2737         print_sched_time(r->total_preempt_time, 6);
2738         printf(" ");
2739         print_sched_time(r->total_delay_time, 6);
2740         printf("\n");
2741 }
2742
2743 struct total_run_stats {
2744         struct perf_sched *sched;
2745         u64  sched_count;
2746         u64  task_count;
2747         u64  total_run_time;
2748 };
2749
2750 static int __show_thread_runtime(struct thread *t, void *priv)
2751 {
2752         struct total_run_stats *stats = priv;
2753         struct thread_runtime *r;
2754
2755         if (thread__is_filtered(t))
2756                 return 0;
2757
2758         r = thread__priv(t);
2759         if (r && r->run_stats.n) {
2760                 stats->task_count++;
2761                 stats->sched_count += r->run_stats.n;
2762                 stats->total_run_time += r->total_run_time;
2763
2764                 if (stats->sched->show_state)
2765                         print_thread_waittime(t, r);
2766                 else
2767                         print_thread_runtime(t, r);
2768         }
2769
2770         return 0;
2771 }
2772
2773 static int show_thread_runtime(struct thread *t, void *priv)
2774 {
2775         if (t->dead)
2776                 return 0;
2777
2778         return __show_thread_runtime(t, priv);
2779 }
2780
2781 static int show_deadthread_runtime(struct thread *t, void *priv)
2782 {
2783         if (!t->dead)
2784                 return 0;
2785
2786         return __show_thread_runtime(t, priv);
2787 }
2788
2789 static size_t callchain__fprintf_folded(FILE *fp, struct callchain_node *node)
2790 {
2791         const char *sep = " <- ";
2792         struct callchain_list *chain;
2793         size_t ret = 0;
2794         char bf[1024];
2795         bool first;
2796
2797         if (node == NULL)
2798                 return 0;
2799
2800         ret = callchain__fprintf_folded(fp, node->parent);
2801         first = (ret == 0);
2802
2803         list_for_each_entry(chain, &node->val, list) {
2804                 if (chain->ip >= PERF_CONTEXT_MAX)
2805                         continue;
2806                 if (chain->ms.sym && chain->ms.sym->ignore)
2807                         continue;
2808                 ret += fprintf(fp, "%s%s", first ? "" : sep,
2809                                callchain_list__sym_name(chain, bf, sizeof(bf),
2810                                                         false));
2811                 first = false;
2812         }
2813
2814         return ret;
2815 }
2816
2817 static size_t timehist_print_idlehist_callchain(struct rb_root_cached *root)
2818 {
2819         size_t ret = 0;
2820         FILE *fp = stdout;
2821         struct callchain_node *chain;
2822         struct rb_node *rb_node = rb_first_cached(root);
2823
2824         printf("  %16s  %8s  %s\n", "Idle time (msec)", "Count", "Callchains");
2825         printf("  %.16s  %.8s  %.50s\n", graph_dotted_line, graph_dotted_line,
2826                graph_dotted_line);
2827
2828         while (rb_node) {
2829                 chain = rb_entry(rb_node, struct callchain_node, rb_node);
2830                 rb_node = rb_next(rb_node);
2831
2832                 ret += fprintf(fp, "  ");
2833                 print_sched_time(chain->hit, 12);
2834                 ret += 16;  /* print_sched_time returns 2nd arg + 4 */
2835                 ret += fprintf(fp, " %8d  ", chain->count);
2836                 ret += callchain__fprintf_folded(fp, chain);
2837                 ret += fprintf(fp, "\n");
2838         }
2839
2840         return ret;
2841 }
2842
2843 static void timehist_print_summary(struct perf_sched *sched,
2844                                    struct perf_session *session)
2845 {
2846         struct machine *m = &session->machines.host;
2847         struct total_run_stats totals;
2848         u64 task_count;
2849         struct thread *t;
2850         struct thread_runtime *r;
2851         int i;
2852         u64 hist_time = sched->hist_time.end - sched->hist_time.start;
2853
2854         memset(&totals, 0, sizeof(totals));
2855         totals.sched = sched;
2856
2857         if (sched->idle_hist) {
2858                 printf("\nIdle-time summary\n");
2859                 printf("%*s  parent  sched-out  ", comm_width, "comm");
2860                 printf("  idle-time   min-idle    avg-idle    max-idle  stddev  migrations\n");
2861         } else if (sched->show_state) {
2862                 printf("\nWait-time summary\n");
2863                 printf("%*s  parent   sched-in  ", comm_width, "comm");
2864                 printf("   run-time      sleep      iowait     preempt       delay\n");
2865         } else {
2866                 printf("\nRuntime summary\n");
2867                 printf("%*s  parent   sched-in  ", comm_width, "comm");
2868                 printf("   run-time    min-run     avg-run     max-run  stddev  migrations\n");
2869         }
2870         printf("%*s            (count)  ", comm_width, "");
2871         printf("     (msec)     (msec)      (msec)      (msec)       %s\n",
2872                sched->show_state ? "(msec)" : "%");
2873         printf("%.117s\n", graph_dotted_line);
2874
2875         machine__for_each_thread(m, show_thread_runtime, &totals);
2876         task_count = totals.task_count;
2877         if (!task_count)
2878                 printf("<no still running tasks>\n");
2879
2880         printf("\nTerminated tasks:\n");
2881         machine__for_each_thread(m, show_deadthread_runtime, &totals);
2882         if (task_count == totals.task_count)
2883                 printf("<no terminated tasks>\n");
2884
2885         /* CPU idle stats not tracked when samples were skipped */
2886         if (sched->skipped_samples && !sched->idle_hist)
2887                 return;
2888
2889         printf("\nIdle stats:\n");
2890         for (i = 0; i < idle_max_cpu; ++i) {
2891                 if (cpu_list && !test_bit(i, cpu_bitmap))
2892                         continue;
2893
2894                 t = idle_threads[i];
2895                 if (!t)
2896                         continue;
2897
2898                 r = thread__priv(t);
2899                 if (r && r->run_stats.n) {
2900                         totals.sched_count += r->run_stats.n;
2901                         printf("    CPU %2d idle for ", i);
2902                         print_sched_time(r->total_run_time, 6);
2903                         printf(" msec  (%6.2f%%)\n", 100.0 * r->total_run_time / hist_time);
2904                 } else
2905                         printf("    CPU %2d idle entire time window\n", i);
2906         }
2907
2908         if (sched->idle_hist && sched->show_callchain) {
2909                 callchain_param.mode  = CHAIN_FOLDED;
2910                 callchain_param.value = CCVAL_PERIOD;
2911
2912                 callchain_register_param(&callchain_param);
2913
2914                 printf("\nIdle stats by callchain:\n");
2915                 for (i = 0; i < idle_max_cpu; ++i) {
2916                         struct idle_thread_runtime *itr;
2917
2918                         t = idle_threads[i];
2919                         if (!t)
2920                                 continue;
2921
2922                         itr = thread__priv(t);
2923                         if (itr == NULL)
2924                                 continue;
2925
2926                         callchain_param.sort(&itr->sorted_root.rb_root, &itr->callchain,
2927                                              0, &callchain_param);
2928
2929                         printf("  CPU %2d:", i);
2930                         print_sched_time(itr->tr.total_run_time, 6);
2931                         printf(" msec\n");
2932                         timehist_print_idlehist_callchain(&itr->sorted_root);
2933                         printf("\n");
2934                 }
2935         }
2936
2937         printf("\n"
2938                "    Total number of unique tasks: %" PRIu64 "\n"
2939                "Total number of context switches: %" PRIu64 "\n",
2940                totals.task_count, totals.sched_count);
2941
2942         printf("           Total run time (msec): ");
2943         print_sched_time(totals.total_run_time, 2);
2944         printf("\n");
2945
2946         printf("    Total scheduling time (msec): ");
2947         print_sched_time(hist_time, 2);
2948         printf(" (x %d)\n", sched->max_cpu.cpu);
2949 }
2950
2951 typedef int (*sched_handler)(struct perf_tool *tool,
2952                           union perf_event *event,
2953                           struct evsel *evsel,
2954                           struct perf_sample *sample,
2955                           struct machine *machine);
2956
2957 static int perf_timehist__process_sample(struct perf_tool *tool,
2958                                          union perf_event *event,
2959                                          struct perf_sample *sample,
2960                                          struct evsel *evsel,
2961                                          struct machine *machine)
2962 {
2963         struct perf_sched *sched = container_of(tool, struct perf_sched, tool);
2964         int err = 0;
2965         struct perf_cpu this_cpu = {
2966                 .cpu = sample->cpu,
2967         };
2968
2969         if (this_cpu.cpu > sched->max_cpu.cpu)
2970                 sched->max_cpu = this_cpu;
2971
2972         if (evsel->handler != NULL) {
2973                 sched_handler f = evsel->handler;
2974
2975                 err = f(tool, event, evsel, sample, machine);
2976         }
2977
2978         return err;
2979 }
2980
2981 static int timehist_check_attr(struct perf_sched *sched,
2982                                struct evlist *evlist)
2983 {
2984         struct evsel *evsel;
2985         struct evsel_runtime *er;
2986
2987         list_for_each_entry(evsel, &evlist->core.entries, core.node) {
2988                 er = evsel__get_runtime(evsel);
2989                 if (er == NULL) {
2990                         pr_err("Failed to allocate memory for evsel runtime data\n");
2991                         return -1;
2992                 }
2993
2994                 if (sched->show_callchain && !evsel__has_callchain(evsel)) {
2995                         pr_info("Samples do not have callchains.\n");
2996                         sched->show_callchain = 0;
2997                         symbol_conf.use_callchain = 0;
2998                 }
2999         }
3000
3001         return 0;
3002 }
3003
3004 static int perf_sched__timehist(struct perf_sched *sched)
3005 {
3006         struct evsel_str_handler handlers[] = {
3007                 { "sched:sched_switch",       timehist_sched_switch_event, },
3008                 { "sched:sched_wakeup",       timehist_sched_wakeup_event, },
3009                 { "sched:sched_waking",       timehist_sched_wakeup_event, },
3010                 { "sched:sched_wakeup_new",   timehist_sched_wakeup_event, },
3011         };
3012         const struct evsel_str_handler migrate_handlers[] = {
3013                 { "sched:sched_migrate_task", timehist_migrate_task_event, },
3014         };
3015         struct perf_data data = {
3016                 .path  = input_name,
3017                 .mode  = PERF_DATA_MODE_READ,
3018                 .force = sched->force,
3019         };
3020
3021         struct perf_session *session;
3022         struct evlist *evlist;
3023         int err = -1;
3024
3025         /*
3026          * event handlers for timehist option
3027          */
3028         sched->tool.sample       = perf_timehist__process_sample;
3029         sched->tool.mmap         = perf_event__process_mmap;
3030         sched->tool.comm         = perf_event__process_comm;
3031         sched->tool.exit         = perf_event__process_exit;
3032         sched->tool.fork         = perf_event__process_fork;
3033         sched->tool.lost         = process_lost;
3034         sched->tool.attr         = perf_event__process_attr;
3035         sched->tool.tracing_data = perf_event__process_tracing_data;
3036         sched->tool.build_id     = perf_event__process_build_id;
3037
3038         sched->tool.ordered_events = true;
3039         sched->tool.ordering_requires_timestamps = true;
3040
3041         symbol_conf.use_callchain = sched->show_callchain;
3042
3043         session = perf_session__new(&data, &sched->tool);
3044         if (IS_ERR(session))
3045                 return PTR_ERR(session);
3046
3047         if (cpu_list) {
3048                 err = perf_session__cpu_bitmap(session, cpu_list, cpu_bitmap);
3049                 if (err < 0)
3050                         goto out;
3051         }
3052
3053         evlist = session->evlist;
3054
3055         symbol__init(&session->header.env);
3056
3057         if (perf_time__parse_str(&sched->ptime, sched->time_str) != 0) {
3058                 pr_err("Invalid time string\n");
3059                 return -EINVAL;
3060         }
3061
3062         if (timehist_check_attr(sched, evlist) != 0)
3063                 goto out;
3064
3065         setup_pager();
3066
3067         /* prefer sched_waking if it is captured */
3068         if (evlist__find_tracepoint_by_name(session->evlist, "sched:sched_waking"))
3069                 handlers[1].handler = timehist_sched_wakeup_ignore;
3070
3071         /* setup per-evsel handlers */
3072         if (perf_session__set_tracepoints_handlers(session, handlers))
3073                 goto out;
3074
3075         /* sched_switch event at a minimum needs to exist */
3076         if (!evlist__find_tracepoint_by_name(session->evlist, "sched:sched_switch")) {
3077                 pr_err("No sched_switch events found. Have you run 'perf sched record'?\n");
3078                 goto out;
3079         }
3080
3081         if (sched->show_migrations &&
3082             perf_session__set_tracepoints_handlers(session, migrate_handlers))
3083                 goto out;
3084
3085         /* pre-allocate struct for per-CPU idle stats */
3086         sched->max_cpu.cpu = session->header.env.nr_cpus_online;
3087         if (sched->max_cpu.cpu == 0)
3088                 sched->max_cpu.cpu = 4;
3089         if (init_idle_threads(sched->max_cpu.cpu))
3090                 goto out;
3091
3092         /* summary_only implies summary option, but don't overwrite summary if set */
3093         if (sched->summary_only)
3094                 sched->summary = sched->summary_only;
3095
3096         if (!sched->summary_only)
3097                 timehist_header(sched);
3098
3099         err = perf_session__process_events(session);
3100         if (err) {
3101                 pr_err("Failed to process events, error %d", err);
3102                 goto out;
3103         }
3104
3105         sched->nr_events      = evlist->stats.nr_events[0];
3106         sched->nr_lost_events = evlist->stats.total_lost;
3107         sched->nr_lost_chunks = evlist->stats.nr_events[PERF_RECORD_LOST];
3108
3109         if (sched->summary)
3110                 timehist_print_summary(sched, session);
3111
3112 out:
3113         free_idle_threads();
3114         perf_session__delete(session);
3115
3116         return err;
3117 }
3118
3119
3120 static void print_bad_events(struct perf_sched *sched)
3121 {
3122         if (sched->nr_unordered_timestamps && sched->nr_timestamps) {
3123                 printf("  INFO: %.3f%% unordered timestamps (%ld out of %ld)\n",
3124                         (double)sched->nr_unordered_timestamps/(double)sched->nr_timestamps*100.0,
3125                         sched->nr_unordered_timestamps, sched->nr_timestamps);
3126         }
3127         if (sched->nr_lost_events && sched->nr_events) {
3128                 printf("  INFO: %.3f%% lost events (%ld out of %ld, in %ld chunks)\n",
3129                         (double)sched->nr_lost_events/(double)sched->nr_events * 100.0,
3130                         sched->nr_lost_events, sched->nr_events, sched->nr_lost_chunks);
3131         }
3132         if (sched->nr_context_switch_bugs && sched->nr_timestamps) {
3133                 printf("  INFO: %.3f%% context switch bugs (%ld out of %ld)",
3134                         (double)sched->nr_context_switch_bugs/(double)sched->nr_timestamps*100.0,
3135                         sched->nr_context_switch_bugs, sched->nr_timestamps);
3136                 if (sched->nr_lost_events)
3137                         printf(" (due to lost events?)");
3138                 printf("\n");
3139         }
3140 }
3141
3142 static void __merge_work_atoms(struct rb_root_cached *root, struct work_atoms *data)
3143 {
3144         struct rb_node **new = &(root->rb_root.rb_node), *parent = NULL;
3145         struct work_atoms *this;
3146         const char *comm = thread__comm_str(data->thread), *this_comm;
3147         bool leftmost = true;
3148
3149         while (*new) {
3150                 int cmp;
3151
3152                 this = container_of(*new, struct work_atoms, node);
3153                 parent = *new;
3154
3155                 this_comm = thread__comm_str(this->thread);
3156                 cmp = strcmp(comm, this_comm);
3157                 if (cmp > 0) {
3158                         new = &((*new)->rb_left);
3159                 } else if (cmp < 0) {
3160                         new = &((*new)->rb_right);
3161                         leftmost = false;
3162                 } else {
3163                         this->num_merged++;
3164                         this->total_runtime += data->total_runtime;
3165                         this->nb_atoms += data->nb_atoms;
3166                         this->total_lat += data->total_lat;
3167                         list_splice(&data->work_list, &this->work_list);
3168                         if (this->max_lat < data->max_lat) {
3169                                 this->max_lat = data->max_lat;
3170                                 this->max_lat_start = data->max_lat_start;
3171                                 this->max_lat_end = data->max_lat_end;
3172                         }
3173                         zfree(&data);
3174                         return;
3175                 }
3176         }
3177
3178         data->num_merged++;
3179         rb_link_node(&data->node, parent, new);
3180         rb_insert_color_cached(&data->node, root, leftmost);
3181 }
3182
3183 static void perf_sched__merge_lat(struct perf_sched *sched)
3184 {
3185         struct work_atoms *data;
3186         struct rb_node *node;
3187
3188         if (sched->skip_merge)
3189                 return;
3190
3191         while ((node = rb_first_cached(&sched->atom_root))) {
3192                 rb_erase_cached(node, &sched->atom_root);
3193                 data = rb_entry(node, struct work_atoms, node);
3194                 __merge_work_atoms(&sched->merged_atom_root, data);
3195         }
3196 }
3197
3198 static int perf_sched__lat(struct perf_sched *sched)
3199 {
3200         struct rb_node *next;
3201
3202         setup_pager();
3203
3204         if (perf_sched__read_events(sched))
3205                 return -1;
3206
3207         perf_sched__merge_lat(sched);
3208         perf_sched__sort_lat(sched);
3209
3210         printf("\n -------------------------------------------------------------------------------------------------------------------------------------------\n");
3211         printf("  Task                  |   Runtime ms  | Switches | Avg delay ms    | Max delay ms    | Max delay start           | Max delay end          |\n");
3212         printf(" -------------------------------------------------------------------------------------------------------------------------------------------\n");
3213
3214         next = rb_first_cached(&sched->sorted_atom_root);
3215
3216         while (next) {
3217                 struct work_atoms *work_list;
3218
3219                 work_list = rb_entry(next, struct work_atoms, node);
3220                 output_lat_thread(sched, work_list);
3221                 next = rb_next(next);
3222                 thread__zput(work_list->thread);
3223         }
3224
3225         printf(" -----------------------------------------------------------------------------------------------------------------\n");
3226         printf("  TOTAL:                |%11.3f ms |%9" PRIu64 " |\n",
3227                 (double)sched->all_runtime / NSEC_PER_MSEC, sched->all_count);
3228
3229         printf(" ---------------------------------------------------\n");
3230
3231         print_bad_events(sched);
3232         printf("\n");
3233
3234         return 0;
3235 }
3236
3237 static int setup_map_cpus(struct perf_sched *sched)
3238 {
3239         struct perf_cpu_map *map;
3240
3241         sched->max_cpu.cpu  = sysconf(_SC_NPROCESSORS_CONF);
3242
3243         if (sched->map.comp) {
3244                 sched->map.comp_cpus = zalloc(sched->max_cpu.cpu * sizeof(int));
3245                 if (!sched->map.comp_cpus)
3246                         return -1;
3247         }
3248
3249         if (!sched->map.cpus_str)
3250                 return 0;
3251
3252         map = perf_cpu_map__new(sched->map.cpus_str);
3253         if (!map) {
3254                 pr_err("failed to get cpus map from %s\n", sched->map.cpus_str);
3255                 return -1;
3256         }
3257
3258         sched->map.cpus = map;
3259         return 0;
3260 }
3261
3262 static int setup_color_pids(struct perf_sched *sched)
3263 {
3264         struct perf_thread_map *map;
3265
3266         if (!sched->map.color_pids_str)
3267                 return 0;
3268
3269         map = thread_map__new_by_tid_str(sched->map.color_pids_str);
3270         if (!map) {
3271                 pr_err("failed to get thread map from %s\n", sched->map.color_pids_str);
3272                 return -1;
3273         }
3274
3275         sched->map.color_pids = map;
3276         return 0;
3277 }
3278
3279 static int setup_color_cpus(struct perf_sched *sched)
3280 {
3281         struct perf_cpu_map *map;
3282
3283         if (!sched->map.color_cpus_str)
3284                 return 0;
3285
3286         map = perf_cpu_map__new(sched->map.color_cpus_str);
3287         if (!map) {
3288                 pr_err("failed to get thread map from %s\n", sched->map.color_cpus_str);
3289                 return -1;
3290         }
3291
3292         sched->map.color_cpus = map;
3293         return 0;
3294 }
3295
3296 static int perf_sched__map(struct perf_sched *sched)
3297 {
3298         if (setup_map_cpus(sched))
3299                 return -1;
3300
3301         if (setup_color_pids(sched))
3302                 return -1;
3303
3304         if (setup_color_cpus(sched))
3305                 return -1;
3306
3307         setup_pager();
3308         if (perf_sched__read_events(sched))
3309                 return -1;
3310         print_bad_events(sched);
3311         return 0;
3312 }
3313
3314 static int perf_sched__replay(struct perf_sched *sched)
3315 {
3316         unsigned long i;
3317
3318         calibrate_run_measurement_overhead(sched);
3319         calibrate_sleep_measurement_overhead(sched);
3320
3321         test_calibrations(sched);
3322
3323         if (perf_sched__read_events(sched))
3324                 return -1;
3325
3326         printf("nr_run_events:        %ld\n", sched->nr_run_events);
3327         printf("nr_sleep_events:      %ld\n", sched->nr_sleep_events);
3328         printf("nr_wakeup_events:     %ld\n", sched->nr_wakeup_events);
3329
3330         if (sched->targetless_wakeups)
3331                 printf("target-less wakeups:  %ld\n", sched->targetless_wakeups);
3332         if (sched->multitarget_wakeups)
3333                 printf("multi-target wakeups: %ld\n", sched->multitarget_wakeups);
3334         if (sched->nr_run_events_optimized)
3335                 printf("run atoms optimized: %ld\n",
3336                         sched->nr_run_events_optimized);
3337
3338         print_task_traces(sched);
3339         add_cross_task_wakeups(sched);
3340
3341         sched->thread_funcs_exit = false;
3342         create_tasks(sched);
3343         printf("------------------------------------------------------------\n");
3344         for (i = 0; i < sched->replay_repeat; i++)
3345                 run_one_test(sched);
3346
3347         sched->thread_funcs_exit = true;
3348         destroy_tasks(sched);
3349         return 0;
3350 }
3351
3352 static void setup_sorting(struct perf_sched *sched, const struct option *options,
3353                           const char * const usage_msg[])
3354 {
3355         char *tmp, *tok, *str = strdup(sched->sort_order);
3356
3357         for (tok = strtok_r(str, ", ", &tmp);
3358                         tok; tok = strtok_r(NULL, ", ", &tmp)) {
3359                 if (sort_dimension__add(tok, &sched->sort_list) < 0) {
3360                         usage_with_options_msg(usage_msg, options,
3361                                         "Unknown --sort key: `%s'", tok);
3362                 }
3363         }
3364
3365         free(str);
3366
3367         sort_dimension__add("pid", &sched->cmp_pid);
3368 }
3369
3370 static bool schedstat_events_exposed(void)
3371 {
3372         /*
3373          * Select "sched:sched_stat_wait" event to check
3374          * whether schedstat tracepoints are exposed.
3375          */
3376         return IS_ERR(trace_event__tp_format("sched", "sched_stat_wait")) ?
3377                 false : true;
3378 }
3379
3380 static int __cmd_record(int argc, const char **argv)
3381 {
3382         unsigned int rec_argc, i, j;
3383         char **rec_argv;
3384         const char **rec_argv_copy;
3385         const char * const record_args[] = {
3386                 "record",
3387                 "-a",
3388                 "-R",
3389                 "-m", "1024",
3390                 "-c", "1",
3391                 "-e", "sched:sched_switch",
3392                 "-e", "sched:sched_stat_runtime",
3393                 "-e", "sched:sched_process_fork",
3394                 "-e", "sched:sched_wakeup_new",
3395                 "-e", "sched:sched_migrate_task",
3396         };
3397
3398         /*
3399          * The tracepoints trace_sched_stat_{wait, sleep, iowait}
3400          * are not exposed to user if CONFIG_SCHEDSTATS is not set,
3401          * to prevent "perf sched record" execution failure, determine
3402          * whether to record schedstat events according to actual situation.
3403          */
3404         const char * const schedstat_args[] = {
3405                 "-e", "sched:sched_stat_wait",
3406                 "-e", "sched:sched_stat_sleep",
3407                 "-e", "sched:sched_stat_iowait",
3408         };
3409         unsigned int schedstat_argc = schedstat_events_exposed() ?
3410                 ARRAY_SIZE(schedstat_args) : 0;
3411
3412         struct tep_event *waking_event;
3413         int ret;
3414
3415         /*
3416          * +2 for either "-e", "sched:sched_wakeup" or
3417          * "-e", "sched:sched_waking"
3418          */
3419         rec_argc = ARRAY_SIZE(record_args) + 2 + schedstat_argc + argc - 1;
3420         rec_argv = calloc(rec_argc + 1, sizeof(char *));
3421         if (rec_argv == NULL)
3422                 return -ENOMEM;
3423         rec_argv_copy = calloc(rec_argc + 1, sizeof(char *));
3424         if (rec_argv_copy == NULL) {
3425                 free(rec_argv);
3426                 return -ENOMEM;
3427         }
3428
3429         for (i = 0; i < ARRAY_SIZE(record_args); i++)
3430                 rec_argv[i] = strdup(record_args[i]);
3431
3432         rec_argv[i++] = strdup("-e");
3433         waking_event = trace_event__tp_format("sched", "sched_waking");
3434         if (!IS_ERR(waking_event))
3435                 rec_argv[i++] = strdup("sched:sched_waking");
3436         else
3437                 rec_argv[i++] = strdup("sched:sched_wakeup");
3438
3439         for (j = 0; j < schedstat_argc; j++)
3440                 rec_argv[i++] = strdup(schedstat_args[j]);
3441
3442         for (j = 1; j < (unsigned int)argc; j++, i++)
3443                 rec_argv[i] = strdup(argv[j]);
3444
3445         BUG_ON(i != rec_argc);
3446
3447         memcpy(rec_argv_copy, rec_argv, sizeof(char *) * rec_argc);
3448         ret = cmd_record(rec_argc, rec_argv_copy);
3449
3450         for (i = 0; i < rec_argc; i++)
3451                 free(rec_argv[i]);
3452         free(rec_argv);
3453         free(rec_argv_copy);
3454
3455         return ret;
3456 }
3457
3458 int cmd_sched(int argc, const char **argv)
3459 {
3460         static const char default_sort_order[] = "avg, max, switch, runtime";
3461         struct perf_sched sched = {
3462                 .tool = {
3463                         .sample          = perf_sched__process_tracepoint_sample,
3464                         .comm            = perf_sched__process_comm,
3465                         .namespaces      = perf_event__process_namespaces,
3466                         .lost            = perf_event__process_lost,
3467                         .fork            = perf_sched__process_fork_event,
3468                         .ordered_events = true,
3469                 },
3470                 .cmp_pid              = LIST_HEAD_INIT(sched.cmp_pid),
3471                 .sort_list            = LIST_HEAD_INIT(sched.sort_list),
3472                 .sort_order           = default_sort_order,
3473                 .replay_repeat        = 10,
3474                 .profile_cpu          = -1,
3475                 .next_shortname1      = 'A',
3476                 .next_shortname2      = '0',
3477                 .skip_merge           = 0,
3478                 .show_callchain       = 1,
3479                 .max_stack            = 5,
3480         };
3481         const struct option sched_options[] = {
3482         OPT_STRING('i', "input", &input_name, "file",
3483                     "input file name"),
3484         OPT_INCR('v', "verbose", &verbose,
3485                     "be more verbose (show symbol address, etc)"),
3486         OPT_BOOLEAN('D', "dump-raw-trace", &dump_trace,
3487                     "dump raw trace in ASCII"),
3488         OPT_BOOLEAN('f', "force", &sched.force, "don't complain, do it"),
3489         OPT_END()
3490         };
3491         const struct option latency_options[] = {
3492         OPT_STRING('s', "sort", &sched.sort_order, "key[,key2...]",
3493                    "sort by key(s): runtime, switch, avg, max"),
3494         OPT_INTEGER('C', "CPU", &sched.profile_cpu,
3495                     "CPU to profile on"),
3496         OPT_BOOLEAN('p', "pids", &sched.skip_merge,
3497                     "latency stats per pid instead of per comm"),
3498         OPT_PARENT(sched_options)
3499         };
3500         const struct option replay_options[] = {
3501         OPT_UINTEGER('r', "repeat", &sched.replay_repeat,
3502                      "repeat the workload replay N times (-1: infinite)"),
3503         OPT_PARENT(sched_options)
3504         };
3505         const struct option map_options[] = {
3506         OPT_BOOLEAN(0, "compact", &sched.map.comp,
3507                     "map output in compact mode"),
3508         OPT_STRING(0, "color-pids", &sched.map.color_pids_str, "pids",
3509                    "highlight given pids in map"),
3510         OPT_STRING(0, "color-cpus", &sched.map.color_cpus_str, "cpus",
3511                     "highlight given CPUs in map"),
3512         OPT_STRING(0, "cpus", &sched.map.cpus_str, "cpus",
3513                     "display given CPUs in map"),
3514         OPT_PARENT(sched_options)
3515         };
3516         const struct option timehist_options[] = {
3517         OPT_STRING('k', "vmlinux", &symbol_conf.vmlinux_name,
3518                    "file", "vmlinux pathname"),
3519         OPT_STRING(0, "kallsyms", &symbol_conf.kallsyms_name,
3520                    "file", "kallsyms pathname"),
3521         OPT_BOOLEAN('g', "call-graph", &sched.show_callchain,
3522                     "Display call chains if present (default on)"),
3523         OPT_UINTEGER(0, "max-stack", &sched.max_stack,
3524                    "Maximum number of functions to display backtrace."),
3525         OPT_STRING(0, "symfs", &symbol_conf.symfs, "directory",
3526                     "Look for files with symbols relative to this directory"),
3527         OPT_BOOLEAN('s', "summary", &sched.summary_only,
3528                     "Show only syscall summary with statistics"),
3529         OPT_BOOLEAN('S', "with-summary", &sched.summary,
3530                     "Show all syscalls and summary with statistics"),
3531         OPT_BOOLEAN('w', "wakeups", &sched.show_wakeups, "Show wakeup events"),
3532         OPT_BOOLEAN('n', "next", &sched.show_next, "Show next task"),
3533         OPT_BOOLEAN('M', "migrations", &sched.show_migrations, "Show migration events"),
3534         OPT_BOOLEAN('V', "cpu-visual", &sched.show_cpu_visual, "Add CPU visual"),
3535         OPT_BOOLEAN('I', "idle-hist", &sched.idle_hist, "Show idle events only"),
3536         OPT_STRING(0, "time", &sched.time_str, "str",
3537                    "Time span for analysis (start,stop)"),
3538         OPT_BOOLEAN(0, "state", &sched.show_state, "Show task state when sched-out"),
3539         OPT_STRING('p', "pid", &symbol_conf.pid_list_str, "pid[,pid...]",
3540                    "analyze events only for given process id(s)"),
3541         OPT_STRING('t', "tid", &symbol_conf.tid_list_str, "tid[,tid...]",
3542                    "analyze events only for given thread id(s)"),
3543         OPT_STRING('C', "cpu", &cpu_list, "cpu", "list of cpus to profile"),
3544         OPT_PARENT(sched_options)
3545         };
3546
3547         const char * const latency_usage[] = {
3548                 "perf sched latency [<options>]",
3549                 NULL
3550         };
3551         const char * const replay_usage[] = {
3552                 "perf sched replay [<options>]",
3553                 NULL
3554         };
3555         const char * const map_usage[] = {
3556                 "perf sched map [<options>]",
3557                 NULL
3558         };
3559         const char * const timehist_usage[] = {
3560                 "perf sched timehist [<options>]",
3561                 NULL
3562         };
3563         const char *const sched_subcommands[] = { "record", "latency", "map",
3564                                                   "replay", "script",
3565                                                   "timehist", NULL };
3566         const char *sched_usage[] = {
3567                 NULL,
3568                 NULL
3569         };
3570         struct trace_sched_handler lat_ops  = {
3571                 .wakeup_event       = latency_wakeup_event,
3572                 .switch_event       = latency_switch_event,
3573                 .runtime_event      = latency_runtime_event,
3574                 .migrate_task_event = latency_migrate_task_event,
3575         };
3576         struct trace_sched_handler map_ops  = {
3577                 .switch_event       = map_switch_event,
3578         };
3579         struct trace_sched_handler replay_ops  = {
3580                 .wakeup_event       = replay_wakeup_event,
3581                 .switch_event       = replay_switch_event,
3582                 .fork_event         = replay_fork_event,
3583         };
3584         unsigned int i;
3585         int ret = 0;
3586
3587         mutex_init(&sched.start_work_mutex);
3588         mutex_init(&sched.work_done_wait_mutex);
3589         for (i = 0; i < ARRAY_SIZE(sched.curr_pid); i++)
3590                 sched.curr_pid[i] = -1;
3591
3592         argc = parse_options_subcommand(argc, argv, sched_options, sched_subcommands,
3593                                         sched_usage, PARSE_OPT_STOP_AT_NON_OPTION);
3594         if (!argc)
3595                 usage_with_options(sched_usage, sched_options);
3596
3597         /*
3598          * Aliased to 'perf script' for now:
3599          */
3600         if (!strcmp(argv[0], "script")) {
3601                 ret = cmd_script(argc, argv);
3602         } else if (strlen(argv[0]) > 2 && strstarts("record", argv[0])) {
3603                 ret = __cmd_record(argc, argv);
3604         } else if (strlen(argv[0]) > 2 && strstarts("latency", argv[0])) {
3605                 sched.tp_handler = &lat_ops;
3606                 if (argc > 1) {
3607                         argc = parse_options(argc, argv, latency_options, latency_usage, 0);
3608                         if (argc)
3609                                 usage_with_options(latency_usage, latency_options);
3610                 }
3611                 setup_sorting(&sched, latency_options, latency_usage);
3612                 ret = perf_sched__lat(&sched);
3613         } else if (!strcmp(argv[0], "map")) {
3614                 if (argc) {
3615                         argc = parse_options(argc, argv, map_options, map_usage, 0);
3616                         if (argc)
3617                                 usage_with_options(map_usage, map_options);
3618                 }
3619                 sched.tp_handler = &map_ops;
3620                 setup_sorting(&sched, latency_options, latency_usage);
3621                 ret = perf_sched__map(&sched);
3622         } else if (strlen(argv[0]) > 2 && strstarts("replay", argv[0])) {
3623                 sched.tp_handler = &replay_ops;
3624                 if (argc) {
3625                         argc = parse_options(argc, argv, replay_options, replay_usage, 0);
3626                         if (argc)
3627                                 usage_with_options(replay_usage, replay_options);
3628                 }
3629                 ret = perf_sched__replay(&sched);
3630         } else if (!strcmp(argv[0], "timehist")) {
3631                 if (argc) {
3632                         argc = parse_options(argc, argv, timehist_options,
3633                                              timehist_usage, 0);
3634                         if (argc)
3635                                 usage_with_options(timehist_usage, timehist_options);
3636                 }
3637                 if ((sched.show_wakeups || sched.show_next) &&
3638                     sched.summary_only) {
3639                         pr_err(" Error: -s and -[n|w] are mutually exclusive.\n");
3640                         parse_options_usage(timehist_usage, timehist_options, "s", true);
3641                         if (sched.show_wakeups)
3642                                 parse_options_usage(NULL, timehist_options, "w", true);
3643                         if (sched.show_next)
3644                                 parse_options_usage(NULL, timehist_options, "n", true);
3645                         ret = -EINVAL;
3646                         goto out;
3647                 }
3648                 ret = symbol__validate_sym_arguments();
3649                 if (ret)
3650                         goto out;
3651
3652                 ret = perf_sched__timehist(&sched);
3653         } else {
3654                 usage_with_options(sched_usage, sched_options);
3655         }
3656
3657 out:
3658         mutex_destroy(&sched.start_work_mutex);
3659         mutex_destroy(&sched.work_done_wait_mutex);
3660
3661         return ret;
3662 }