path: root/kernel/irq/timings.c

/*
 * IRQ occurrence timing statistics
 *
 * Created by:  Nicolas Pitre, November 2014
 * Copyright:   (C) 2014-2015  Linaro Limited
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation.
 */

#include <linux/irq.h>
#include <linux/ktime.h>
#include <linux/list.h>
#include <linux/math64.h>
#include <linux/slab.h>
#include <linux/spinlock.h>
#include <linux/debugfs.h>
#include "internals.h"

#include <trace/events/irq.h>


/*
 * This is the size of the IRQ interval window used to compute the
 * mean interval and its variance.  This has to be at least 3 to still
 * make sense.  Higher values may improve prediction confidence but more
 * false negatives are to be expected.
 */
#define IRQT_INTERVAL_WINDOW	3


struct irqt_prediction {
	struct list_head node;
	ktime_t		 time;		/* expected occurrence time */
	int		 cpu;		/* CPU for which this was queued for */
};

struct irqt_stat {
	ktime_t		last_time;	/* previous IRQ occurrence */
	u64		n_M2;		/* IRQ interval variance (n scaled) */
	u32		n_mean;		/* IRQ mean interval (n scaled) */
	u32     	intervals[IRQT_INTERVAL_WINDOW];
					/* window of recent IRQ intervals */
	unsigned int	w_ptr;		/* current window pointer */
	u32		predictable;	/* # of IRQs that were predictable */
	u32		unpredictable;	/* # of IRQs that were not */
	struct irqt_prediction prediction;
};

static DEFINE_PER_CPU(struct list_head, irqt_predictions);
static DEFINE_PER_CPU(raw_spinlock_t, irqt_predictions_lock);

#ifdef CONFIG_DEBUG_FS

struct irqt_stats {
	atomic_t correct;
	atomic_t early;
	atomic_t late;
	atomic_t total;
};

static DEFINE_PER_CPU(struct irqt_stats, irqt_stats[NR_IRQS]);
static unsigned irqt_registered[NR_IRQS];

static int irqt_debugfs_stats_show(struct seq_file *m, void *v)
{
	int i, cpu;
	struct irqt_stats *s;

	seq_printf(m, "# cpu\t irq\tcorrect\tearly\tlate\ttotal\n");
	
	for_each_online_cpu(cpu) {

		for (i = 0; i < NR_IRQS; i++) {
			
			if (!irqt_registered[i])
				continue;

			s = &per_cpu(irqt_stats[i], cpu);

			if (!atomic_read(&s->total))
				continue;

			seq_printf(m, "%d\t%d\t", cpu, i);
			seq_printf(m, "%d\t", atomic_read(&s->correct));
			seq_printf(m, "%d\t", atomic_read(&s->early));
			seq_printf(m, "%d\t", atomic_read(&s->late));
			seq_printf(m, "%d\n", atomic_read(&s->total));
		}
	}

	return 0;
}

static int irqt_debugfs_stats_open(struct inode *inode, struct file *file)
{
	return single_open(file, irqt_debugfs_stats_show,
			   &inode->i_private);
}

static const struct file_operations stats_fops = {
	.open = irqt_debugfs_stats_open,
	.read = seq_read,
	.llseek = seq_lseek,
};

static void irqt_debugfs_correct_inc(int cpu, int irq)
{
	struct irqt_stats *s = &per_cpu(irqt_stats[irq], cpu);
	atomic_inc(&s->correct);
	atomic_inc(&s->total);
}

static void irqt_debugfs_early_inc(int cpu, int irq)
{
	struct irqt_stats *s = &per_cpu(irqt_stats[irq], cpu);
	atomic_inc(&s->early);
	atomic_inc(&s->total);
}

static void irqt_debugfs_late_inc(int cpu, int irq)
{
	struct irqt_stats *s = &per_cpu(irqt_stats[irq], cpu);
	atomic_inc(&s->late);
	atomic_inc(&s->total);
}

static int __init irqt_debugfs_init(void)
{
	struct dentry *top;
	int ret = -ENOMEM;

	top = debugfs_create_dir("irqt", NULL);
	if (!top)
		return -ENOMEM;

	if (!debugfs_create_file("stats", 0400, top, NULL, &stats_fops))
		goto out;

	ret = 0;
out:
	if (ret)
		debugfs_remove_recursive(top);

	return ret;
}

late_initcall(irqt_debugfs_init);

#endif

void __init irqt_init(void)
{
	int cpu;

	for_each_possible_cpu(cpu) {
		INIT_LIST_HEAD(&per_cpu(irqt_predictions, cpu));
		raw_spin_lock_init(&per_cpu(irqt_predictions_lock, cpu));
	}
}

/*
 * Purge past events.
 * Caller must take care of locking.
 */
static void irqt_purge(ktime_t now, struct list_head *head)
{
	struct irqt_prediction *entry, *n;

	list_for_each_entry_safe(entry, n, head, node) {
		if (ktime_after(entry->time, now))
			break;
		list_del_init(&entry->node);
	}
}

/*
 * Enqueue the next predicted event for this IRQ on this CPU.
 * We are in interrupt context with IRQs disabled.
 */
static void irqt_enqueue_prediction(ktime_t now, struct irqt_stat *s)
{
	int this_cpu = raw_smp_processor_id();
	int prev_cpu = s->prediction.cpu;
	struct list_head *head = &per_cpu(irqt_predictions, this_cpu);
	u32 predicted_interval = s->n_mean / IRQT_INTERVAL_WINDOW;
	struct irqt_prediction *list_entry, *new_entry;
	raw_spinlock_t *lock;

	if (unlikely(prev_cpu != this_cpu && prev_cpu != -1)) {
		lock = &per_cpu(irqt_predictions_lock, prev_cpu);
		raw_spin_lock(lock);
		list_del_init(&s->prediction.node);
		raw_spin_unlock(lock);
	}
		
	lock = &per_cpu(irqt_predictions_lock, this_cpu);
	raw_spin_lock(lock);
	irqt_purge(now, head);
	__list_del_entry(&s->prediction.node);
	new_entry = &s->prediction;
	new_entry->time = ktime_add_us(now, predicted_interval);
	new_entry->cpu = this_cpu;
	list_for_each_entry(list_entry, head, node)
		if (ktime_after(new_entry->time, list_entry->time))
			break;
	list_add_tail(&new_entry->node, &list_entry->node);
	raw_spin_unlock(lock);
}

/**
 * irqt_get_next_prediction - get relative time before next predicted IRQ
 *
 * @cpu: the CPU number for which a prediction is wanted
 *
 * This returns the relative time in microsecs before the next expected IRQ
 * on given CPU, or zero if no prediction is available.  Those predictions
 * are not guaranteed to be reliable, and guaranteed to fail from time to
 * time i.e. when the predicted IRQ simply never comes, etc.
 */
s64 irqt_get_next_prediction(int cpu)
{
	raw_spinlock_t *lock = &per_cpu(irqt_predictions_lock, cpu);
	struct list_head *head = &per_cpu(irqt_predictions, cpu);
	unsigned long flags;
	ktime_t now;
	struct irqt_prediction *next;
	s64 result;

	raw_spin_lock_irqsave(lock, flags);
	now = ktime_get();
	irqt_purge(now, head);
	next = list_first_entry_or_null(head, struct irqt_prediction, node);
	result = next ? ktime_us_delta(next->time, now) : 0;
	raw_spin_unlock_irqrestore(lock, flags);
	return result;
}

/*
 * irqt_process - update timing interval statistics for the given IRQ
 *
 * @irq: the IRQ number
 * @stat: the corresponding IRQ timing stats record
 *
 * This is assumed to be called in IRQ context with desc->lock held and
 * IRQs turned off.
 */
void irqt_process(unsigned int irq, struct irqt_stat *s)
{
	ktime_t now = ktime_get();
	ktime_t ktime_interval = ktime_sub(now, s->last_time);
	u32 oldX, newX, n = IRQT_INTERVAL_WINDOW;
	s32 delta, n_dold, n_dnew;

	s->last_time = now;

	/* An interval needs at least two events */
	if (unlikely(ktime_equal(now, ktime_interval)))
		return;

	/*
	 * There is no point attempting predictions on interrupts more
	 * than 1 second apart. This has no benefit for sleep state
	 * selection and increases the risk of overflowing our variance
	 * computation.  Reset all stats in that case.
	 */
	if (unlikely(ktime_after(ktime_interval, ktime_set(1, 0)))) {
		s->n_mean = 0;
		return;
	}

	/* microsecs is good enough */
	newX = ktime_to_us(ktime_interval);

	/* Seed the stats with the first interval */
	if (unlikely(!s->n_mean)) {
		int i;
		s->n_M2 = 0;
		s->n_mean = newX * n;
		for (i = 0; i < IRQT_INTERVAL_WINDOW; i++)
			s->intervals[i] = newX;
		s->predictable = s->unpredictable = 0;
		return;
	}

	/* Replace the oldest interval in our window */
	oldX = s->intervals[s->w_ptr];
	s->intervals[s->w_ptr] = newX;
	s->w_ptr = (s->w_ptr + 1) % IRQT_INTERVAL_WINDOW;

	/*
	 * The variance gives us an instantaneous deviation from the
	 * mean interval value.  Given x a new inter-IRQ interval and n the
	 * number of such intervals to date:
	 *
	 *	n = n + 1
	 *	delta = x - mean
	 *	mean = mean + delta/n
	 *	M2 = M2 + delta*(x - mean)
	 *
	 *	variance = M2/(n - 1)
	 *
	 * We want to update the variance over a window of recent intervals
	 * in order to stay current with changing IRQ patterns.  To remove
	 * the contribution from a sample x:
	 *
	 *	n = n - 1
	 *	delta = x - mean
	 *	mean = mean - delta/n
	 *	M2 = M2 - delta*(x - mean)
	 *
	 * Combining those equations, we update both the mean and
	 * variance by removing the contribution from the oldest window
	 * sample and adding the latest one at the same time:
	 *
	 *	delta = newX - oldX
	 *	dold = oldX - mean
	 *	mean = mean + delta/n
	 *	dnew = newX - mean
	 *	M2 = M2 + delta * (dold + dnew)
	 *
	 * Ref:
	 * http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance
	 *
	 * However this is unstable if performed with integer math due to
	 * the accumulation of bit truncation errors caused by the division.
	 * To avoid that, let's factor out the division.  Assuming
	 * n_mean = n * mean:
	 *
	 *	delta = newX - oldX
	 *	n_dold = n * oldX - n_mean
	 *	n_mean = n_mean + delta
	 *	n_dnew = n * newX - n_mean
	 *	n_M2 = n_M2 + delta * (n_dold + n_dnew)
	 *
	 *	variance = n_M2/n / (n - 1)
	 *
	 * To make things as efficient as possible, we keep our window
	 * size constant: n = IRQT_INTERVAL_WINDOW.
	 */
	delta = newX - oldX;
	n_dold = n*oldX - s->n_mean;
	s->n_mean += delta;
	n_dnew = n*newX - s->n_mean;
	s->n_M2 += (s64)delta * (n_dold + n_dnew);

	/*
	 * Let's determine if this interrupt actually happened after a 
	 * periodic interval.  We treat a standard deviation greater than
	 * the mean value as a signal that the current interval is no longer
	 * stable enough to be predictable.
	 *
	 * 	mean < SD  -->  mean < sqrt(variance)  -->  mean^2 < variance
	 *
	 * 	n_mean/n * n_mean/n < n_M2/n / (n - 1)  -->
	 * 	n_mean * n_mean * (n - 1) < n_M2 * n
	 */
	if ((u64)s->n_mean * s->n_mean * (n - 1) > s->n_M2 * n) {
		s->predictable++;
		if (s->predictable >= IRQT_INTERVAL_WINDOW)
			irqt_enqueue_prediction(now, s);
		irqt_debugfs_correct_inc(smp_processor_id(), irq);
	} else {
		irqt_debugfs_early_inc(smp_processor_id(), irq);
		irqt_debugfs_late_inc(smp_processor_id(), irq);
		s->predictable = 0;
		s->unpredictable++;
	}

	trace_irq_timings(irq, newX, div_u64(s->n_M2, n*(n-1)), s->n_mean/n,
			 s->predictable, s->unpredictable);
}

/*
 * Called from __setup_irq() after successful registration of a new action
 * handler.
 */
int irqt_register(struct irq_desc *desc)
{
	struct irqt_stat *s;
	unsigned long flags;
	int ret;

	if (desc->irq_timings)
		return 0;

	s = kzalloc(sizeof(*s), GFP_KERNEL);
	if (!s)
		return -ENOMEM;
	INIT_LIST_HEAD(&s->prediction.node);
	s->prediction.cpu = -1;

	raw_spin_lock_irqsave(&desc->lock, flags);
	if (desc->irq_timings) {
		/* someone else raced ahead of us */
		ret = 0;
	} else if (!desc->action) {
		/* unused IRQ? */
		ret = -ENXIO;
	} else if (irq_settings_is_per_cpu(desc)) {
		/* we're not set for per-CPU accounting */
		pr_warn("IRQ %d: can't do timing stats on per-CPU IRQs\n",
			desc->action->irq);
		ret = -ENOSYS;
	} else {
		desc->irq_timings = s;
		irqt_registered[desc->action->irq] = 1;
		s = NULL;
		ret = 0;
	}
	raw_spin_unlock_irqrestore(&desc->lock, flags);
	if (s)
		kfree(s);
	return ret;
}

/*
 * Called from __free_irq() when there is no longer any handler attached
 * to the IRQ descriptor. Must be called with desc->lock held.
 */
void irqt_unregister(struct irq_desc *desc)
{
	struct irqt_stat *s;
	int cpu;
	raw_spinlock_t *lock;

	assert_raw_spin_locked(&desc->lock);
	if (!desc->irq_timings)
		return;
	s = desc->irq_timings;
	desc->irq_timings = NULL;
	irqt_registered[desc->action->irq] = 0;
	cpu = s->prediction.cpu;
	if (cpu != -1) {
		lock = &per_cpu(irqt_predictions_lock, cpu);
		raw_spin_lock(lock);
		__list_del_entry(&s->prediction.node);
		raw_spin_unlock(lock);
	}
	kfree(s);
}