trace.c

/*
 * ring buffer based function tracer
 *
 * Copyright (C) 2007-2008 Steven Rostedt <srostedt@redhat.com>
 * Copyright (C) 2008 Ingo Molnar <mingo@redhat.com>
 *
 * Originally taken from the RT patch by:
 *    Arnaldo Carvalho de Melo <acme@redhat.com>
 *
 * Based on code from the latency_tracer, that is:
 *  Copyright (C) 2004-2006 Ingo Molnar
 *  Copyright (C) 2004 William Lee Irwin III
 */
#include <linux/utsrelease.h>
#include <linux/kallsyms.h>
#include <linux/seq_file.h>
#include <linux/debugfs.h>
#include <linux/pagemap.h>
#include <linux/hardirq.h>
#include <linux/linkage.h>
#include <linux/uaccess.h>
#include <linux/ftrace.h>
#include <linux/module.h>
#include <linux/percpu.h>
#include <linux/ctype.h>
#include <linux/init.h>
#include <linux/poll.h>
#include <linux/gfp.h>
#include <linux/fs.h>

#include <linux/stacktrace.h>

#include "trace.h"

unsigned long __read_mostly	tracing_max_latency = (cycle_t)ULONG_MAX;
unsigned long __read_mostly	tracing_thresh;

static int tracing_disabled = 1;

static long
ns2usecs(cycle_t nsec)
{
	nsec += 500;
	do_div(nsec, 1000);
	return nsec;
}

cycle_t ftrace_now(int cpu)
{
	return cpu_clock(cpu);
}

static struct trace_array	global_trace;

static DEFINE_PER_CPU(struct trace_array_cpu, global_trace_cpu);

static struct trace_array	max_tr;

static DEFINE_PER_CPU(struct trace_array_cpu, max_data);

static int			tracer_enabled = 1;
static unsigned long		trace_nr_entries = 65536UL;

static struct tracer		*trace_types __read_mostly;
static struct tracer		*current_trace __read_mostly;
static int			max_tracer_type_len;

static DEFINE_MUTEX(trace_types_lock);
static DECLARE_WAIT_QUEUE_HEAD (trace_wait);

#define ENTRIES_PER_PAGE (PAGE_SIZE / sizeof(struct trace_entry))

static int __init set_nr_entries(char *str)
{
	if (!str)
		return 0;
	trace_nr_entries = simple_strtoul(str, &str, 0);
	return 1;
}
__setup("trace_entries=", set_nr_entries);

unsigned long nsecs_to_usecs(unsigned long nsecs)
{
	return nsecs / 1000;
}

enum trace_type {
	__TRACE_FIRST_TYPE = 0,

	TRACE_FN,
	TRACE_CTX,
	TRACE_WAKE,
	TRACE_STACK,
	TRACE_SPECIAL,

	__TRACE_LAST_TYPE
};

enum trace_flag_type {
	TRACE_FLAG_IRQS_OFF		= 0x01,
	TRACE_FLAG_NEED_RESCHED		= 0x02,
	TRACE_FLAG_HARDIRQ		= 0x04,
	TRACE_FLAG_SOFTIRQ		= 0x08,
};

enum trace_iterator_flags {
	TRACE_ITER_PRINT_PARENT		= 0x01,
	TRACE_ITER_SYM_OFFSET		= 0x02,
	TRACE_ITER_SYM_ADDR		= 0x04,
	TRACE_ITER_VERBOSE		= 0x08,
	TRACE_ITER_RAW			= 0x10,
	TRACE_ITER_HEX			= 0x20,
	TRACE_ITER_BIN			= 0x40,
	TRACE_ITER_BLOCK		= 0x80,
	TRACE_ITER_STACKTRACE		= 0x100,
};

#define TRACE_ITER_SYM_MASK \
	(TRACE_ITER_PRINT_PARENT|TRACE_ITER_SYM_OFFSET|TRACE_ITER_SYM_ADDR)

/* These must match the bit postions above */
static const char *trace_options[] = {
	"print-parent",
	"sym-offset",
	"sym-addr",
	"verbose",
	"raw",
	"hex",
	"bin",
	"block",
	"stacktrace",
	NULL
};

static unsigned trace_flags = TRACE_ITER_PRINT_PARENT;

static DEFINE_SPINLOCK(ftrace_max_lock);

/*
 * Copy the new maximum trace into the separate maximum-trace
 * structure. (this way the maximum trace is permanently saved,
 * for later retrieval via /debugfs/tracing/latency_trace)
 */
static void
__update_max_tr(struct trace_array *tr, struct task_struct *tsk, int cpu)
{
	struct trace_array_cpu *data = tr->data[cpu];

	max_tr.cpu = cpu;
	max_tr.time_start = data->preempt_timestamp;

	data = max_tr.data[cpu];
	data->saved_latency = tracing_max_latency;

	memcpy(data->comm, tsk->comm, TASK_COMM_LEN);
	data->pid = tsk->pid;
	data->uid = tsk->uid;
	data->nice = tsk->static_prio - 20 - MAX_RT_PRIO;
	data->policy = tsk->policy;
	data->rt_priority = tsk->rt_priority;

	/* record this tasks comm */
	tracing_record_cmdline(current);
}

void check_pages(struct trace_array_cpu *data)
{
	struct page *page, *tmp;

	BUG_ON(data->trace_pages.next->prev != &data->trace_pages);
	BUG_ON(data->trace_pages.prev->next != &data->trace_pages);

	list_for_each_entry_safe(page, tmp, &data->trace_pages, lru) {
		BUG_ON(page->lru.next->prev != &page->lru);
		BUG_ON(page->lru.prev->next != &page->lru);
	}
}

void *head_page(struct trace_array_cpu *data)
{
	struct page *page;

	check_pages(data);
	if (list_empty(&data->trace_pages))
		return NULL;

	page = list_entry(data->trace_pages.next, struct page, lru);
	BUG_ON(&page->lru == &data->trace_pages);

	return page_address(page);
}

static int
trace_seq_printf(struct trace_seq *s, const char *fmt, ...)
{
	int len = (PAGE_SIZE - 1) - s->len;
	va_list ap;
	int ret;

	if (!len)
		return 0;

	va_start(ap, fmt);
	ret = vsnprintf(s->buffer + s->len, len, fmt, ap);
	va_end(ap);

	/* If we can't write it all, don't bother writing anything */
	if (ret > len)
		return 0;

	s->len += ret;

	return len;
}

static int
trace_seq_puts(struct trace_seq *s, const char *str)
{
	int len = strlen(str);

	if (len > ((PAGE_SIZE - 1) - s->len))
		return 0;

	memcpy(s->buffer + s->len, str, len);
	s->len += len;

	return len;
}

static int
trace_seq_putc(struct trace_seq *s, unsigned char c)
{
	if (s->len >= (PAGE_SIZE - 1))
		return 0;

	s->buffer[s->len++] = c;

	return 1;
}

static int
trace_seq_putmem(struct trace_seq *s, void *mem, size_t len)
{
	if (len > ((PAGE_SIZE - 1) - s->len))
		return 0;

	memcpy(s->buffer + s->len, mem, len);
	s->len += len;

	return len;
}

#define HEX_CHARS 17

static int
trace_seq_putmem_hex(struct trace_seq *s, void *mem, size_t len)
{
	unsigned char hex[HEX_CHARS];
	unsigned char *data;
	unsigned char byte;
	int i, j;

	BUG_ON(len >= HEX_CHARS);

	data = mem;

#ifdef __BIG_ENDIAN
	for (i = 0, j = 0; i < len; i++) {
#else
	for (i = len-1, j = 0; i >= 0; i--) {
#endif
		byte = data[i];

		hex[j]   = byte & 0x0f;
		if (hex[j] >= 10)
			hex[j] += 'a' - 10;
		else
			hex[j] += '0';
		j++;

		hex[j] = byte >> 4;
		if (hex[j] >= 10)
			hex[j] += 'a' - 10;
		else
			hex[j] += '0';
		j++;
	}
	hex[j] = ' ';
	j++;

	return trace_seq_putmem(s, hex, j);
}

static void
trace_seq_reset(struct trace_seq *s)
{
	s->len = 0;
}

static void
trace_print_seq(struct seq_file *m, struct trace_seq *s)
{
	int len = s->len >= PAGE_SIZE ? PAGE_SIZE - 1 : s->len;

	s->buffer[len] = 0;
	seq_puts(m, s->buffer);

	trace_seq_reset(s);
}

static void
flip_trace(struct trace_array_cpu *tr1, struct trace_array_cpu *tr2)
{
	struct list_head flip_pages;

	INIT_LIST_HEAD(&flip_pages);

	memcpy(&tr1->trace_head_idx, &tr2->trace_head_idx,
		sizeof(struct trace_array_cpu) -
		offsetof(struct trace_array_cpu, trace_head_idx));

	check_pages(tr1);
	check_pages(tr2);
	list_splice_init(&tr1->trace_pages, &flip_pages);
	list_splice_init(&tr2->trace_pages, &tr1->trace_pages);
	list_splice_init(&flip_pages, &tr2->trace_pages);
	BUG_ON(!list_empty(&flip_pages));
	check_pages(tr1);
	check_pages(tr2);
}

void
update_max_tr(struct trace_array *tr, struct task_struct *tsk, int cpu)
{
	struct trace_array_cpu *data;
	int i;

	WARN_ON_ONCE(!irqs_disabled());
	spin_lock(&ftrace_max_lock);
	/* clear out all the previous traces */
	for_each_possible_cpu(i) {
		data = tr->data[i];
		flip_trace(max_tr.data[i], data);
		tracing_reset(data);
	}

	__update_max_tr(tr, tsk, cpu);
	spin_unlock(&ftrace_max_lock);
}

/**
 * update_max_tr_single - only copy one trace over, and reset the rest
 * @tr - tracer
 * @tsk - task with the latency
 * @cpu - the cpu of the buffer to copy.
 */
void
update_max_tr_single(struct trace_array *tr, struct task_struct *tsk, int cpu)
{
	struct trace_array_cpu *data = tr->data[cpu];
	int i;

	WARN_ON_ONCE(!irqs_disabled());
	spin_lock(&ftrace_max_lock);
	for_each_possible_cpu(i)
		tracing_reset(max_tr.data[i]);

	flip_trace(max_tr.data[cpu], data);
	tracing_reset(data);

	__update_max_tr(tr, tsk, cpu);
	spin_unlock(&ftrace_max_lock);
}

int register_tracer(struct tracer *type)
{
	struct tracer *t;
	int len;
	int ret = 0;

	if (!type->name) {
		pr_info("Tracer must have a name\n");
		return -1;
	}

	mutex_lock(&trace_types_lock);
	for (t = trace_types; t; t = t->next) {
		if (strcmp(type->name, t->name) == 0) {
			/* already found */
			pr_info("Trace %s already registered\n",
				type->name);
			ret = -1;
			goto out;
		}
	}

#ifdef CONFIG_FTRACE_STARTUP_TEST
	if (type->selftest) {
		struct tracer *saved_tracer = current_trace;
		struct trace_array_cpu *data;
		struct trace_array *tr = &global_trace;
		int saved_ctrl = tr->ctrl;
		int i;
		/*
		 * Run a selftest on this tracer.
		 * Here we reset the trace buffer, and set the current
		 * tracer to be this tracer. The tracer can then run some
		 * internal tracing to verify that everything is in order.
		 * If we fail, we do not register this tracer.
		 */
		for_each_possible_cpu(i) {
			data = tr->data[i];
			if (!head_page(data))
				continue;
			tracing_reset(data);
		}
		current_trace = type;
		tr->ctrl = 0;
		/* the test is responsible for initializing and enabling */
		pr_info("Testing tracer %s: ", type->name);
		ret = type->selftest(type, tr);
		/* the test is responsible for resetting too */
		current_trace = saved_tracer;
		tr->ctrl = saved_ctrl;
		if (ret) {
			printk(KERN_CONT "FAILED!\n");
			goto out;
		}
		/* Only reset on passing, to avoid touching corrupted buffers */
		for_each_possible_cpu(i) {
			data = tr->data[i];
			if (!head_page(data))
				continue;
			tracing_reset(data);
		}
		printk(KERN_CONT "PASSED\n");
	}
#endif

	type->next = trace_types;
	trace_types = type;
	len = strlen(type->name);
	if (len > max_tracer_type_len)
		max_tracer_type_len = len;

 out:
	mutex_unlock(&trace_types_lock);

	return ret;
}

void unregister_tracer(struct tracer *type)
{
	struct tracer **t;
	int len;

	mutex_lock(&trace_types_lock);
	for (t = &trace_types; *t; t = &(*t)->next) {
		if (*t == type)
			goto found;
	}
	pr_info("Trace %s not registered\n", type->name);
	goto out;

 found:
	*t = (*t)->next;
	if (strlen(type->name) != max_tracer_type_len)
		goto out;

	max_tracer_type_len = 0;
	for (t = &trace_types; *t; t = &(*t)->next) {
		len = strlen((*t)->name);
		if (len > max_tracer_type_len)
			max_tracer_type_len = len;
	}
 out:
	mutex_unlock(&trace_types_lock);
}

void tracing_reset(struct trace_array_cpu *data)
{
	data->trace_idx = 0;
	data->trace_head = data->trace_tail = head_page(data);
	data->trace_head_idx = 0;
	data->trace_tail_idx = 0;
}

#define SAVED_CMDLINES 128
static unsigned map_pid_to_cmdline[PID_MAX_DEFAULT+1];
static unsigned map_cmdline_to_pid[SAVED_CMDLINES];
static char saved_cmdlines[SAVED_CMDLINES][TASK_COMM_LEN];
static int cmdline_idx;
static DEFINE_SPINLOCK(trace_cmdline_lock);
atomic_t trace_record_cmdline_disabled;

static void trace_init_cmdlines(void)
{
	memset(&map_pid_to_cmdline, -1, sizeof(map_pid_to_cmdline));
	memset(&map_cmdline_to_pid, -1, sizeof(map_cmdline_to_pid));
	cmdline_idx = 0;
}

void trace_stop_cmdline_recording(void);

static void trace_save_cmdline(struct task_struct *tsk)
{
	unsigned map;
	unsigned idx;

	if (!tsk->pid || unlikely(tsk->pid > PID_MAX_DEFAULT))
		return;

	/*
	 * It's not the end of the world if we don't get
	 * the lock, but we also don't want to spin
	 * nor do we want to disable interrupts,
	 * so if we miss here, then better luck next time.
	 */
	if (!spin_trylock(&trace_cmdline_lock))
		return;

	idx = map_pid_to_cmdline[tsk->pid];
	if (idx >= SAVED_CMDLINES) {
		idx = (cmdline_idx + 1) % SAVED_CMDLINES;

		map = map_cmdline_to_pid[idx];
		if (map <= PID_MAX_DEFAULT)
			map_pid_to_cmdline[map] = (unsigned)-1;

		map_pid_to_cmdline[tsk->pid] = idx;

		cmdline_idx = idx;
	}

	memcpy(&saved_cmdlines[idx], tsk->comm, TASK_COMM_LEN);

	spin_unlock(&trace_cmdline_lock);
}

static char *trace_find_cmdline(int pid)
{
	char *cmdline = "<...>";
	unsigned map;

	if (!pid)
		return "<idle>";

	if (pid > PID_MAX_DEFAULT)
		goto out;

	map = map_pid_to_cmdline[pid];
	if (map >= SAVED_CMDLINES)
		goto out;

	cmdline = saved_cmdlines[map];

 out:
	return cmdline;
}

void tracing_record_cmdline(struct task_struct *tsk)
{
	if (atomic_read(&trace_record_cmdline_disabled))
		return;

	trace_save_cmdline(tsk);
}

static inline struct list_head *
trace_next_list(struct trace_array_cpu *data, struct list_head *next)
{
	/*
	 * Roundrobin - but skip the head (which is not a real page):
	 */
	next = next->next;
	if (unlikely(next == &data->trace_pages))
		next = next->next;
	BUG_ON(next == &data->trace_pages);

	return next;
}

static inline void *
trace_next_page(struct trace_array_cpu *data, void *addr)
{
	struct list_head *next;
	struct page *page;

	page = virt_to_page(addr);

	next = trace_next_list(data, &page->lru);
	page = list_entry(next, struct page, lru);

	return page_address(page);
}

static inline struct trace_entry *
tracing_get_trace_entry(struct trace_array *tr, struct trace_array_cpu *data)
{
	unsigned long idx, idx_next;
	struct trace_entry *entry;

	data->trace_idx++;
	idx = data->trace_head_idx;
	idx_next = idx + 1;

	BUG_ON(idx * TRACE_ENTRY_SIZE >= PAGE_SIZE);

	entry = data->trace_head + idx * TRACE_ENTRY_SIZE;

	if (unlikely(idx_next >= ENTRIES_PER_PAGE)) {
		data->trace_head = trace_next_page(data, data->trace_head);
		idx_next = 0;
	}

	if (data->trace_head == data->trace_tail &&
	    idx_next == data->trace_tail_idx) {
		/* overrun */
		data->trace_tail_idx++;
		if (data->trace_tail_idx >= ENTRIES_PER_PAGE) {
			data->trace_tail =
				trace_next_page(data, data->trace_tail);
			data->trace_tail_idx = 0;
		}
	}

	data->trace_head_idx = idx_next;

	return entry;
}

static inline void
tracing_generic_entry_update(struct trace_entry *entry, unsigned long flags)
{
	struct task_struct *tsk = current;
	unsigned long pc;

	pc = preempt_count();

	entry->preempt_count	= pc & 0xff;
	entry->pid		= tsk->pid;
	entry->t		= ftrace_now(raw_smp_processor_id());
	entry->flags = (irqs_disabled_flags(flags) ? TRACE_FLAG_IRQS_OFF : 0) |
		((pc & HARDIRQ_MASK) ? TRACE_FLAG_HARDIRQ : 0) |
		((pc & SOFTIRQ_MASK) ? TRACE_FLAG_SOFTIRQ : 0) |
		(need_resched() ? TRACE_FLAG_NEED_RESCHED : 0);
}

void
trace_function(struct trace_array *tr, struct trace_array_cpu *data,
	       unsigned long ip, unsigned long parent_ip, unsigned long flags)
{
	struct trace_entry *entry;
	unsigned long irq_flags;

	spin_lock_irqsave(&data->lock, irq_flags);
	entry			= tracing_get_trace_entry(tr, data);
	tracing_generic_entry_update(entry, flags);
	entry->type		= TRACE_FN;
	entry->fn.ip		= ip;
	entry->fn.parent_ip	= parent_ip;
	spin_unlock_irqrestore(&data->lock, irq_flags);

	if (!(trace_flags & TRACE_ITER_BLOCK))
		wake_up(&trace_wait);
}

void
ftrace(struct trace_array *tr, struct trace_array_cpu *data,
       unsigned long ip, unsigned long parent_ip, unsigned long flags)
{
	if (likely(!atomic_read(&data->disabled)))
		trace_function(tr, data, ip, parent_ip, flags);
}

void
trace_special(struct trace_array *tr, struct trace_array_cpu *data,
	      unsigned long arg1, unsigned long arg2, unsigned long arg3)
{
	struct trace_entry *entry;
	unsigned long irq_flags;

	spin_lock_irqsave(&data->lock, irq_flags);
	entry			= tracing_get_trace_entry(tr, data);
	tracing_generic_entry_update(entry, 0);
	entry->type		= TRACE_SPECIAL;
	entry->special.arg1	= arg1;
	entry->special.arg2	= arg2;
	entry->special.arg3	= arg3;
	spin_unlock_irqrestore(&data->lock, irq_flags);

	if (!(trace_flags & TRACE_ITER_BLOCK))
		wake_up(&trace_wait);
}

void __trace_stack(struct trace_array *tr,
		   struct trace_array_cpu *data,
		   unsigned long flags,
		   int skip)
{
	struct trace_entry *entry;
	struct stack_trace trace;

	if (!(trace_flags & TRACE_ITER_STACKTRACE))
		return;

	entry			= tracing_get_trace_entry(tr, data);
	tracing_generic_entry_update(entry, flags);
	entry->type		= TRACE_STACK;

	memset(&entry->stack, 0, sizeof(entry->stack));

	trace.nr_entries	= 0;
	trace.max_entries	= FTRACE_STACK_ENTRIES;
	trace.skip		= skip;
	trace.entries		= entry->stack.caller;

	save_stack_trace(&trace);
}

void
tracing_sched_switch_trace(struct trace_array *tr,
			   struct trace_array_cpu *data,
			   struct task_struct *prev,
			   struct task_struct *next,
			   unsigned long flags)
{
	struct trace_entry *entry;
	unsigned long irq_flags;

	spin_lock_irqsave(&data->lock, irq_flags);
	entry			= tracing_get_trace_entry(tr, data);
	tracing_generic_entry_update(entry, flags);
	entry->type		= TRACE_CTX;
	entry->ctx.prev_pid	= prev->pid;
	entry->ctx.prev_prio	= prev->prio;
	entry->ctx.prev_state	= prev->state;
	entry->ctx.next_pid	= next->pid;
	entry->ctx.next_prio	= next->prio;
	__trace_stack(tr, data, flags, 4);
	spin_unlock_irqrestore(&data->lock, irq_flags);

	if (!(trace_flags & TRACE_ITER_BLOCK))
		wake_up(&trace_wait);
}

void
tracing_sched_wakeup_trace(struct trace_array *tr,
			   struct trace_array_cpu *data,
			   struct task_struct *wakee,
			   struct task_struct *curr,
			   unsigned long flags)
{
	struct trace_entry *entry;
	unsigned long irq_flags;

	spin_lock_irqsave(&data->lock, irq_flags);
	entry			= tracing_get_trace_entry(tr, data);
	tracing_generic_entry_update(entry, flags);
	entry->type		= TRACE_WAKE;
	entry->ctx.prev_pid	= curr->pid;
	entry->ctx.prev_prio	= curr->prio;
	entry->ctx.prev_state	= curr->state;
	entry->ctx.next_pid	= wakee->pid;
	entry->ctx.next_prio	= wakee->prio;
	__trace_stack(tr, data, flags, 5);
	spin_unlock_irqrestore(&data->lock, irq_flags);

	if (!(trace_flags & TRACE_ITER_BLOCK))
		wake_up(&trace_wait);
}

#ifdef CONFIG_FTRACE
static void
function_trace_call(unsigned long ip, unsigned long parent_ip)
{
	struct trace_array *tr = &global_trace;
	struct trace_array_cpu *data;
	unsigned long flags;
	long disabled;
	int cpu;

	if (unlikely(!tracer_enabled))
		return;

	local_irq_save(flags);
	cpu = raw_smp_processor_id();
	data = tr->data[cpu];
	disabled = atomic_inc_return(&data->disabled);

	if (likely(disabled == 1))
		trace_function(tr, data, ip, parent_ip, flags);

	atomic_dec(&data->disabled);
	local_irq_restore(flags);
}

static struct ftrace_ops trace_ops __read_mostly =
{
	.func = function_trace_call,
};

void tracing_start_function_trace(void)
{
	register_ftrace_function(&trace_ops);
}

void tracing_stop_function_trace(void)
{
	unregister_ftrace_function(&trace_ops);
}
#endif

enum trace_file_type {
	TRACE_FILE_LAT_FMT	= 1,
};

static struct trace_entry *
trace_entry_idx(struct trace_array *tr, struct trace_array_cpu *data,
		struct trace_iterator *iter, int cpu)
{
	struct page *page;
	struct trace_entry *array;

	if (iter->next_idx[cpu] >= tr->entries ||
	    iter->next_idx[cpu] >= data->trace_idx ||
	    (data->trace_head == data->trace_tail &&
	     data->trace_head_idx == data->trace_tail_idx))
		return NULL;

	if (!iter->next_page[cpu]) {
		/* Initialize the iterator for this cpu trace buffer */
		WARN_ON(!data->trace_tail);
		page = virt_to_page(data->trace_tail);
		iter->next_page[cpu] = &page->lru;
		iter->next_page_idx[cpu] = data->trace_tail_idx;
	}

	page = list_entry(iter->next_page[cpu], struct page, lru);
	BUG_ON(&data->trace_pages == &page->lru);

	array = page_address(page);

	WARN_ON(iter->next_page_idx[cpu] >= ENTRIES_PER_PAGE);
	return &array[iter->next_page_idx[cpu]];
}

static struct trace_entry *
find_next_entry(struct trace_iterator *iter, int *ent_cpu)
{
	struct trace_array *tr = iter->tr;
	struct trace_entry *ent, *next = NULL;
	int next_cpu = -1;
	int cpu;

	for_each_possible_cpu(cpu) {
		if (!head_page(tr->data[cpu]))
			continue;
		ent = trace_entry_idx(tr, tr->data[cpu], iter, cpu);
		/*
		 * Pick the entry with the smallest timestamp:
		 */
		if (ent && (!next || ent->t < next->t)) {
			next = ent;
			next_cpu = cpu;
		}
	}

	if (ent_cpu)
		*ent_cpu = next_cpu;

	return next;
}

static void trace_iterator_increment(struct trace_iterator *iter)
{
	iter->idx++;
	iter->next_idx[iter->cpu]++;
	iter->next_page_idx[iter->cpu]++;

	if (iter->next_page_idx[iter->cpu] >= ENTRIES_PER_PAGE) {
		struct trace_array_cpu *data = iter->tr->data[iter->cpu];

		iter->next_page_idx[iter->cpu] = 0;
		iter->next_page[iter->cpu] =
			trace_next_list(data, iter->next_page[iter->cpu]);
	}
}

static void trace_consume(struct trace_iterator *iter)
{
	struct trace_array_cpu *data = iter->tr->data[iter->cpu];

	data->trace_tail_idx++;
	if (data->trace_tail_idx >= ENTRIES_PER_PAGE) {
		data->trace_tail = trace_next_page(data, data->trace_tail);
		data->trace_tail_idx = 0;
	}

	/* Check if we empty it, then reset the index */
	if (data->trace_head == data->trace_tail &&
	    data->trace_head_idx == data->trace_tail_idx)
		data->trace_idx = 0;
}

static void *find_next_entry_inc(struct trace_iterator *iter)
{
	struct trace_entry *next;
	int next_cpu = -1;

	next = find_next_entry(iter, &next_cpu);

	iter->prev_ent = iter->ent;
	iter->prev_cpu = iter->cpu;

	iter->ent = next;
	iter->cpu = next_cpu;

	if (next)
		trace_iterator_increment(iter);

	return next ? iter : NULL;
}

static void *s_next(struct seq_file *m, void *v, loff_t *pos)
{
	struct trace_iterator *iter = m->private;
	void *last_ent = iter->ent;
	int i = (int)*pos;
	void *ent;

	(*pos)++;

	/* can't go backwards */
	if (iter->idx > i)
		return NULL;

	if (iter->idx < 0)
		ent = find_next_entry_inc(iter);
	else
		ent = iter;

	while (ent && iter->idx < i)
		ent = find_next_entry_inc(iter);

	iter->pos = *pos;

	if (last_ent && !ent)
		seq_puts(m, "\n\nvim:ft=help\n");

	return ent;
}

static void *s_start(struct seq_file *m, loff_t *pos)
{
	struct trace_iterator *iter = m->private;
	void *p = NULL;
	loff_t l = 0;
	int i;

	mutex_lock(&trace_types_lock);

	if (!current_trace || current_trace != iter->trace)
		return NULL;

	atomic_inc(&trace_record_cmdline_disabled);

	/* let the tracer grab locks here if needed */
	if (current_trace->start)
		current_trace->start(iter);

	if (*pos != iter->pos) {
		iter->ent = NULL;
		iter->cpu = 0;
		iter->idx = -1;
		iter->prev_ent = NULL;
		iter->prev_cpu = -1;

		for_each_possible_cpu(i) {
			iter->next_idx[i] = 0;
			iter->next_page[i] = NULL;
		}

		for (p = iter; p && l < *pos; p = s_next(m, p, &l))
			;

	} else {
		l = *pos - 1;
		p = s_next(m, p, &l);
	}

	return p;
}

static void s_stop(struct seq_file *m, void *p)
{
	struct trace_iterator *iter = m->private;

	atomic_dec(&trace_record_cmdline_disabled);