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
55static const char *cpu_list;
56static DECLARE_BITMAP(cpu_bitmap, MAX_NR_CPUS);
57
58struct sched_atom;
59
60struct 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
78enum sched_event_type {
79	SCHED_EVENT_RUN,
80	SCHED_EVENT_SLEEP,
81	SCHED_EVENT_WAKEUP,
82	SCHED_EVENT_MIGRATION,
83};
84
85struct 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
113enum thread_state {
114	THREAD_SLEEPING = 0,
115	THREAD_WAIT_CPU,
116	THREAD_SCHED_IN,
117	THREAD_IGNORE
118};
119
120struct 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
129struct 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
142typedef int (*sort_fn_t)(struct work_atoms *, struct work_atoms *);
143
144struct perf_sched;
145
146struct 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
169struct 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
181struct 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 */
253struct 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 */
278struct 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 */
284struct 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 */
293static struct thread **idle_threads;
294static int idle_max_cpu;
295static char idle_comm[] = "<idle>";
296
297static 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
306static 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
315static 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
325static 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
342static 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
360static struct sched_atom *
361get_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
380static 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
388static 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
411static 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
438static 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
448static 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
494static 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
506static 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
521static 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
547static 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
562static 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
575force_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
604static 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
615struct sched_thread_parms {
616	struct task_desc  *task;
617	struct perf_sched *sched;
618	int fd;
619};
620
621static 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
662static 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
693static 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
714static 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
767static 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
815static 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
832static int
833replay_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
854static 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
900static 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));
925out_put:
926	thread__put(child);
927	thread__put(parent);
928	return 0;
929}
930
931struct 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 */
940static 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
954static 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
968static int
969thread_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
985static struct work_atoms *
986thread_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
1011static 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
1039static 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
1053static 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
1060static int
1061add_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
1082static void
1083add_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
1096static void
1097add_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
1128static 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;
1192out_put:
1193	thread__put(sched_out);
1194	thread__put(sched_in);
1195	return err;
1196}
1197
1198static 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;
1228out_put:
1229	thread__put(thread);
1230	return err;
1231}
1232
1233static 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;
1287out_ok:
1288	err = 0;
1289out_put:
1290	thread__put(wakee);
1291	return err;
1292}
1293
1294static 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;
1339out_put:
1340	thread__put(migrant);
1341	return err;
1342}
1343
1344static 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
1381static 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
1392static 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
1413static 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
1423static 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
1433static 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
1443static 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
1485static void perf_sched__sort_lat(struct perf_sched *sched)
1486{
1487	struct rb_node *node;
1488	struct rb_root_cached *root = &sched->atom_root;
1489again:
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
1506static 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
1519union map_priv {
1520	void	*ptr;
1521	bool	 color;
1522};
1523
1524static 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
1533static struct thread*
1534map__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
1551static 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
1688out:
1689	color_fprintf(stdout, color, "\n");
1690
1691	thread__put(sched_in);
1692
1693	return 0;
1694}
1695
1696static 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
1722static 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
1735static 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
1752static 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
1765typedef int (*tracepoint_handler)(struct perf_tool *tool,
1766				  struct evsel *evsel,
1767				  struct perf_sample *sample,
1768				  struct machine *machine);
1769
1770static 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
1786static 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
1817static 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;
1858out_delete:
1859	perf_session__delete(session);
1860	return rc;
1861}
1862
1863/*
1864 * scheduling times are printed as msec.usec
1865 */
1866static 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 */
1881static 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 */
1896static 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 */
1922static 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
1932static int comm_width = 30;
1933
1934static 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
1957static 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
2016static 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
2028static 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
2096out:
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
2123static 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
2164static 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
2174static 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
2222static 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 */
2244static 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
2268static 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
2283static 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
2317static 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
2327static 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
2374static 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
2397static 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
2431static 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
2440static 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
2471static 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
2524static 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
2552static 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
2656out:
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
2678static 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
2687static 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
2702static 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
2725static 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
2743struct total_run_stats {
2744	struct perf_sched *sched;
2745	u64  sched_count;
2746	u64  task_count;
2747	u64  total_run_time;
2748};
2749
2750static 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
2773static 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
2781static 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
2789static 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
2817static 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
2843static 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
2951typedef 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
2957static 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
2981static 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
3004static 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
3112out:
3113	free_idle_threads();
3114	perf_session__delete(session);
3115
3116	return err;
3117}
3118
3119
3120static 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
3142static 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
3183static 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
3198static 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
3237static 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
3262static 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
3279static 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
3296static 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
3314static 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
3352static 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
3370static 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
3380static 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
3458int 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
3657out:
3658	mutex_destroy(&sched.start_work_mutex);
3659	mutex_destroy(&sched.work_done_wait_mutex);
3660
3661	return ret;
3662}
3663