[deliverable/linux.git] / kernel / profile.c

/*
 *  linux/kernel/profile.c
 *  Simple profiling. Manages a direct-mapped profile hit count buffer,
 *  with configurable resolution, support for restricting the cpus on
 *  which profiling is done, and switching between cpu time and
 *  schedule() calls via kernel command line parameters passed at boot.
 *
 *  Scheduler profiling support, Arjan van de Ven and Ingo Molnar,
 *	Red Hat, July 2004
 *  Consolidation of architecture support code for profiling,
 *	Nadia Yvette Chambers, Oracle, July 2004
 *  Amortized hit count accounting via per-cpu open-addressed hashtables
 *	to resolve timer interrupt livelocks, Nadia Yvette Chambers,
 *	Oracle, 2004
 */

#include <linux/export.h>
#include <linux/profile.h>
#include <linux/bootmem.h>
#include <linux/notifier.h>
#include <linux/mm.h>
#include <linux/cpumask.h>
#include <linux/cpu.h>
#include <linux/highmem.h>
#include <linux/mutex.h>
#include <linux/slab.h>
#include <linux/vmalloc.h>
#include <asm/sections.h>
#include <asm/irq_regs.h>
#include <asm/ptrace.h>

struct profile_hit {
	u32 pc, hits;
};
#define PROFILE_GRPSHIFT	3
#define PROFILE_GRPSZ		(1 << PROFILE_GRPSHIFT)
#define NR_PROFILE_HIT		(PAGE_SIZE/sizeof(struct profile_hit))
#define NR_PROFILE_GRP		(NR_PROFILE_HIT/PROFILE_GRPSZ)

static atomic_t *prof_buffer;
static unsigned long prof_len, prof_shift;

int prof_on __read_mostly;
EXPORT_SYMBOL_GPL(prof_on);

static cpumask_var_t prof_cpu_mask;
#ifdef CONFIG_SMP
static DEFINE_PER_CPU(struct profile_hit *[2], cpu_profile_hits);
static DEFINE_PER_CPU(int, cpu_profile_flip);
static DEFINE_MUTEX(profile_flip_mutex);
#endif /* CONFIG_SMP */

int profile_setup(char *str)
{
	static char schedstr[] = "schedule";
	static char sleepstr[] = "sleep";
	static char kvmstr[] = "kvm";
	int par;

	if (!strncmp(str, sleepstr, strlen(sleepstr))) {
#ifdef CONFIG_SCHEDSTATS
		prof_on = SLEEP_PROFILING;
		if (str[strlen(sleepstr)] == ',')
			str += strlen(sleepstr) + 1;
		if (get_option(&str, &par))
			prof_shift = par;
		printk(KERN_INFO
			"kernel sleep profiling enabled (shift: %ld)\n",
			prof_shift);
#else
		printk(KERN_WARNING
			"kernel sleep profiling requires CONFIG_SCHEDSTATS\n");
#endif /* CONFIG_SCHEDSTATS */
	} else if (!strncmp(str, schedstr, strlen(schedstr))) {
		prof_on = SCHED_PROFILING;
		if (str[strlen(schedstr)] == ',')
			str += strlen(schedstr) + 1;
		if (get_option(&str, &par))
			prof_shift = par;
		printk(KERN_INFO
			"kernel schedule profiling enabled (shift: %ld)\n",
			prof_shift);
	} else if (!strncmp(str, kvmstr, strlen(kvmstr))) {
		prof_on = KVM_PROFILING;
		if (str[strlen(kvmstr)] == ',')
			str += strlen(kvmstr) + 1;
		if (get_option(&str, &par))
			prof_shift = par;
		printk(KERN_INFO
			"kernel KVM profiling enabled (shift: %ld)\n",
			prof_shift);
	} else if (get_option(&str, &par)) {
		prof_shift = par;
		prof_on = CPU_PROFILING;
		printk(KERN_INFO "kernel profiling enabled (shift: %ld)\n",
			prof_shift);
	}
	return 1;
}
__setup("profile=", profile_setup);


int __ref profile_init(void)
{
	int buffer_bytes;
	if (!prof_on)
		return 0;

	/* only text is profiled */
	prof_len = (_etext - _stext) >> prof_shift;
	buffer_bytes = prof_len*sizeof(atomic_t);

	if (!alloc_cpumask_var(&prof_cpu_mask, GFP_KERNEL))
		return -ENOMEM;

	cpumask_copy(prof_cpu_mask, cpu_possible_mask);

	prof_buffer = kzalloc(buffer_bytes, GFP_KERNEL|__GFP_NOWARN);
	if (prof_buffer)
		return 0;

	prof_buffer = alloc_pages_exact(buffer_bytes,
					GFP_KERNEL|__GFP_ZERO|__GFP_NOWARN);
	if (prof_buffer)
		return 0;

	prof_buffer = vzalloc(buffer_bytes);
	if (prof_buffer)
		return 0;

	free_cpumask_var(prof_cpu_mask);
	return -ENOMEM;
}

/* Profile event notifications */

static BLOCKING_NOTIFIER_HEAD(task_exit_notifier);
static ATOMIC_NOTIFIER_HEAD(task_free_notifier);
static BLOCKING_NOTIFIER_HEAD(munmap_notifier);

void profile_task_exit(struct task_struct *task)
{
	blocking_notifier_call_chain(&task_exit_notifier, 0, task);
}

int profile_handoff_task(struct task_struct *task)
{
	int ret;
	ret = atomic_notifier_call_chain(&task_free_notifier, 0, task);
	return (ret == NOTIFY_OK) ? 1 : 0;
}

void profile_munmap(unsigned long addr)
{
	blocking_notifier_call_chain(&munmap_notifier, 0, (void *)addr);
}

int task_handoff_register(struct notifier_block *n)
{
	return atomic_notifier_chain_register(&task_free_notifier, n);
}
EXPORT_SYMBOL_GPL(task_handoff_register);

int task_handoff_unregister(struct notifier_block *n)
{
	return atomic_notifier_chain_unregister(&task_free_notifier, n);
}
EXPORT_SYMBOL_GPL(task_handoff_unregister);

int profile_event_register(enum profile_type type, struct notifier_block *n)
{
	int err = -EINVAL;

	switch (type) {
	case PROFILE_TASK_EXIT:
		err = blocking_notifier_chain_register(
				&task_exit_notifier, n);
		break;
	case PROFILE_MUNMAP:
		err = blocking_notifier_chain_register(
				&munmap_notifier, n);
		break;
	}

	return err;
}
EXPORT_SYMBOL_GPL(profile_event_register);

int profile_event_unregister(enum profile_type type, struct notifier_block *n)
{
	int err = -EINVAL;

	switch (type) {
	case PROFILE_TASK_EXIT:
		err = blocking_notifier_chain_unregister(
				&task_exit_notifier, n);
		break;
	case PROFILE_MUNMAP:
		err = blocking_notifier_chain_unregister(
				&munmap_notifier, n);
		break;
	}

	return err;
}
EXPORT_SYMBOL_GPL(profile_event_unregister);

#ifdef CONFIG_SMP
/*
 * Each cpu has a pair of open-addressed hashtables for pending
 * profile hits. read_profile() IPI's all cpus to request them
 * to flip buffers and flushes their contents to prof_buffer itself.
 * Flip requests are serialized by the profile_flip_mutex. The sole
 * use of having a second hashtable is for avoiding cacheline
 * contention that would otherwise happen during flushes of pending
 * profile hits required for the accuracy of reported profile hits
 * and so resurrect the interrupt livelock issue.
 *
 * The open-addressed hashtables are indexed by profile buffer slot
 * and hold the number of pending hits to that profile buffer slot on
 * a cpu in an entry. When the hashtable overflows, all pending hits
 * are accounted to their corresponding profile buffer slots with
 * atomic_add() and the hashtable emptied. As numerous pending hits
 * may be accounted to a profile buffer slot in a hashtable entry,
 * this amortizes a number of atomic profile buffer increments likely
 * to be far larger than the number of entries in the hashtable,
 * particularly given that the number of distinct profile buffer
 * positions to which hits are accounted during short intervals (e.g.
 * several seconds) is usually very small. Exclusion from buffer
 * flipping is provided by interrupt disablement (note that for
 * SCHED_PROFILING or SLEEP_PROFILING profile_hit() may be called from
 * process context).
 * The hash function is meant to be lightweight as opposed to strong,
 * and was vaguely inspired by ppc64 firmware-supported inverted
 * pagetable hash functions, but uses a full hashtable full of finite
 * collision chains, not just pairs of them.
 *
 * -- nyc
 */
static void __profile_flip_buffers(void *unused)
{
	int cpu = smp_processor_id();

	per_cpu(cpu_profile_flip, cpu) = !per_cpu(cpu_profile_flip, cpu);
}

static void profile_flip_buffers(void)
{
	int i, j, cpu;

	mutex_lock(&profile_flip_mutex);
	j = per_cpu(cpu_profile_flip, get_cpu());
	put_cpu();
	on_each_cpu(__profile_flip_buffers, NULL, 1);
	for_each_online_cpu(cpu) {
		struct profile_hit *hits = per_cpu(cpu_profile_hits, cpu)[j];
		for (i = 0; i < NR_PROFILE_HIT; ++i) {
			if (!hits[i].hits) {
				if (hits[i].pc)
					hits[i].pc = 0;
				continue;
			}
			atomic_add(hits[i].hits, &prof_buffer[hits[i].pc]);
			hits[i].hits = hits[i].pc = 0;
		}
	}
	mutex_unlock(&profile_flip_mutex);
}

static void profile_discard_flip_buffers(void)
{
	int i, cpu;

	mutex_lock(&profile_flip_mutex);
	i = per_cpu(cpu_profile_flip, get_cpu());
	put_cpu();
	on_each_cpu(__profile_flip_buffers, NULL, 1);
	for_each_online_cpu(cpu) {
		struct profile_hit *hits = per_cpu(cpu_profile_hits, cpu)[i];
		memset(hits, 0, NR_PROFILE_HIT*sizeof(struct profile_hit));
	}
	mutex_unlock(&profile_flip_mutex);
}

static void do_profile_hits(int type, void *__pc, unsigned int nr_hits)
{
	unsigned long primary, secondary, flags, pc = (unsigned long)__pc;
	int i, j, cpu;
	struct profile_hit *hits;

	pc = min((pc - (unsigned long)_stext) >> prof_shift, prof_len - 1);
	i = primary = (pc & (NR_PROFILE_GRP - 1)) << PROFILE_GRPSHIFT;
	secondary = (~(pc << 1) & (NR_PROFILE_GRP - 1)) << PROFILE_GRPSHIFT;
	cpu = get_cpu();
	hits = per_cpu(cpu_profile_hits, cpu)[per_cpu(cpu_profile_flip, cpu)];
	if (!hits) {
		put_cpu();
		return;
	}
	/*
	 * We buffer the global profiler buffer into a per-CPU
	 * queue and thus reduce the number of global (and possibly
	 * NUMA-alien) accesses. The write-queue is self-coalescing:
	 */
	local_irq_save(flags);
	do {
		for (j = 0; j < PROFILE_GRPSZ; ++j) {
			if (hits[i + j].pc == pc) {
				hits[i + j].hits += nr_hits;
				goto out;
			} else if (!hits[i + j].hits) {
				hits[i + j].pc = pc;
				hits[i + j].hits = nr_hits;
				goto out;
			}
		}
		i = (i + secondary) & (NR_PROFILE_HIT - 1);
	} while (i != primary);

	/*
	 * Add the current hit(s) and flush the write-queue out
	 * to the global buffer:
	 */
	atomic_add(nr_hits, &prof_buffer[pc]);
	for (i = 0; i < NR_PROFILE_HIT; ++i) {
		atomic_add(hits[i].hits, &prof_buffer[hits[i].pc]);
		hits[i].pc = hits[i].hits = 0;
	}
out:
	local_irq_restore(flags);
	put_cpu();
}

static int profile_cpu_callback(struct notifier_block *info,
					unsigned long action, void *__cpu)
{
	int node, cpu = (unsigned long)__cpu;
	struct page *page;

	switch (action) {
	case CPU_UP_PREPARE:
	case CPU_UP_PREPARE_FROZEN:
		node = cpu_to_mem(cpu);
		per_cpu(cpu_profile_flip, cpu) = 0;
		if (!per_cpu(cpu_profile_hits, cpu)[1]) {
			page = alloc_pages_exact_node(node,
					GFP_KERNEL | __GFP_ZERO,
					0);
			if (!page)
				return notifier_from_errno(-ENOMEM);
			per_cpu(cpu_profile_hits, cpu)[1] = page_address(page);
		}
		if (!per_cpu(cpu_profile_hits, cpu)[0]) {
			page = alloc_pages_exact_node(node,
					GFP_KERNEL | __GFP_ZERO,
					0);
			if (!page)
				goto out_free;
			per_cpu(cpu_profile_hits, cpu)[0] = page_address(page);
		}
		break;
out_free:
		page = virt_to_page(per_cpu(cpu_profile_hits, cpu)[1]);
		per_cpu(cpu_profile_hits, cpu)[1] = NULL;
		__free_page(page);
		return notifier_from_errno(-ENOMEM);
	case CPU_ONLINE:
	case CPU_ONLINE_FROZEN:
		if (prof_cpu_mask != NULL)
			cpumask_set_cpu(cpu, prof_cpu_mask);
		break;
	case CPU_UP_CANCELED:
	case CPU_UP_CANCELED_FROZEN:
	case CPU_DEAD:
	case CPU_DEAD_FROZEN:
		if (prof_cpu_mask != NULL)
			cpumask_clear_cpu(cpu, prof_cpu_mask);
		if (per_cpu(cpu_profile_hits, cpu)[0]) {
			page = virt_to_page(per_cpu(cpu_profile_hits, cpu)[0]);
			per_cpu(cpu_profile_hits, cpu)[0] = NULL;
			__free_page(page);
		}
		if (per_cpu(cpu_profile_hits, cpu)[1]) {
			page = virt_to_page(per_cpu(cpu_profile_hits, cpu)[1]);
			per_cpu(cpu_profile_hits, cpu)[1] = NULL;
			__free_page(page);
		}
		break;
	}
	return NOTIFY_OK;
}
#else /* !CONFIG_SMP */
#define profile_flip_buffers()		do { } while (0)
#define profile_discard_flip_buffers()	do { } while (0)
#define profile_cpu_callback		NULL

static void do_profile_hits(int type, void *__pc, unsigned int nr_hits)
{
	unsigned long pc;
	pc = ((unsigned long)__pc - (unsigned long)_stext) >> prof_shift;
	atomic_add(nr_hits, &prof_buffer[min(pc, prof_len - 1)]);
}
#endif /* !CONFIG_SMP */

void profile_hits(int type, void *__pc, unsigned int nr_hits)
{
	if (prof_on != type || !prof_buffer)
		return;
	do_profile_hits(type, __pc, nr_hits);
}
EXPORT_SYMBOL_GPL(profile_hits);

void profile_tick(int type)
{
	struct pt_regs *regs = get_irq_regs();

	if (!user_mode(regs) && prof_cpu_mask != NULL &&
	    cpumask_test_cpu(smp_processor_id(), prof_cpu_mask))
		profile_hit(type, (void *)profile_pc(regs));
}

#ifdef CONFIG_PROC_FS
#include <linux/proc_fs.h>
#include <linux/seq_file.h>
#include <asm/uaccess.h>

static int prof_cpu_mask_proc_show(struct seq_file *m, void *v)
{
	seq_cpumask(m, prof_cpu_mask);
	seq_putc(m, '\n');
	return 0;
}

static int prof_cpu_mask_proc_open(struct inode *inode, struct file *file)
{
	return single_open(file, prof_cpu_mask_proc_show, NULL);
}

static ssize_t prof_cpu_mask_proc_write(struct file *file,
	const char __user *buffer, size_t count, loff_t *pos)
{
	cpumask_var_t new_value;
	int err;

	if (!alloc_cpumask_var(&new_value, GFP_KERNEL))
		return -ENOMEM;

	err = cpumask_parse_user(buffer, count, new_value);
	if (!err) {
		cpumask_copy(prof_cpu_mask, new_value);
		err = count;
	}
	free_cpumask_var(new_value);
	return err;
}

static const struct file_operations prof_cpu_mask_proc_fops = {
	.open		= prof_cpu_mask_proc_open,
	.read		= seq_read,
	.llseek		= seq_lseek,
	.release	= single_release,
	.write		= prof_cpu_mask_proc_write,
};

void create_prof_cpu_mask(void)
{
	/* create /proc/irq/prof_cpu_mask */
	proc_create("irq/prof_cpu_mask", 0600, NULL, &prof_cpu_mask_proc_fops);
}

/*
 * This function accesses profiling information. The returned data is
 * binary: the sampling step and the actual contents of the profile
 * buffer. Use of the program readprofile is recommended in order to
 * get meaningful info out of these data.
 */
static ssize_t
read_profile(struct file *file, char __user *buf, size_t count, loff_t *ppos)
{
	unsigned long p = *ppos;
	ssize_t read;
	char *pnt;
	unsigned int sample_step = 1 << prof_shift;

	profile_flip_buffers();
	if (p >= (prof_len+1)*sizeof(unsigned int))
		return 0;
	if (count > (prof_len+1)*sizeof(unsigned int) - p)
		count = (prof_len+1)*sizeof(unsigned int) - p;
	read = 0;

	while (p < sizeof(unsigned int) && count > 0) {
		if (put_user(*((char *)(&sample_step)+p), buf))
			return -EFAULT;
		buf++; p++; count--; read++;
	}
	pnt = (char *)prof_buffer + p - sizeof(atomic_t);
	if (copy_to_user(buf, (void *)pnt, count))
		return -EFAULT;
	read += count;
	*ppos += read;
	return read;
}

/*
 * Writing to /proc/profile resets the counters
 *
 * Writing a 'profiling multiplier' value into it also re-sets the profiling
 * interrupt frequency, on architectures that support this.
 */
static ssize_t write_profile(struct file *file, const char __user *buf,
			     size_t count, loff_t *ppos)
{
#ifdef CONFIG_SMP
	extern int setup_profiling_timer(unsigned int multiplier);

	if (count == sizeof(int)) {
		unsigned int multiplier;

		if (copy_from_user(&multiplier, buf, sizeof(int)))
			return -EFAULT;

		if (setup_profiling_timer(multiplier))
			return -EINVAL;
	}
#endif
	profile_discard_flip_buffers();
	memset(prof_buffer, 0, prof_len * sizeof(atomic_t));
	return count;
}

static const struct file_operations proc_profile_operations = {
	.read		= read_profile,
	.write		= write_profile,
	.llseek		= default_llseek,
};

#ifdef CONFIG_SMP
static void profile_nop(void *unused)
{
}

static int create_hash_tables(void)
{
	int cpu;

	for_each_online_cpu(cpu) {
		int node = cpu_to_mem(cpu);
		struct page *page;

		page = alloc_pages_exact_node(node,
				GFP_KERNEL | __GFP_ZERO | __GFP_THISNODE,
				0);
		if (!page)
			goto out_cleanup;
		per_cpu(cpu_profile_hits, cpu)[1]
				= (struct profile_hit *)page_address(page);
		page = alloc_pages_exact_node(node,
				GFP_KERNEL | __GFP_ZERO | __GFP_THISNODE,
				0);
		if (!page)
			goto out_cleanup;
		per_cpu(cpu_profile_hits, cpu)[0]
				= (struct profile_hit *)page_address(page);
	}
	return 0;
out_cleanup:
	prof_on = 0;
	smp_mb();
	on_each_cpu(profile_nop, NULL, 1);
	for_each_online_cpu(cpu) {
		struct page *page;

		if (per_cpu(cpu_profile_hits, cpu)[0]) {
			page = virt_to_page(per_cpu(cpu_profile_hits, cpu)[0]);
			per_cpu(cpu_profile_hits, cpu)[0] = NULL;
			__free_page(page);
		}
		if (per_cpu(cpu_profile_hits, cpu)[1]) {
			page = virt_to_page(per_cpu(cpu_profile_hits, cpu)[1]);
			per_cpu(cpu_profile_hits, cpu)[1] = NULL;
			__free_page(page);
		}
	}
	return -1;
}
#else
#define create_hash_tables()			({ 0; })
#endif

int __ref create_proc_profile(void) /* false positive from hotcpu_notifier */
{
	struct proc_dir_entry *entry;

	if (!prof_on)
		return 0;
	if (create_hash_tables())
		return -ENOMEM;
	entry = proc_create("profile", S_IWUSR | S_IRUGO,
			    NULL, &proc_profile_operations);
	if (!entry)
		return 0;
	proc_set_size(entry, (1 + prof_len) * sizeof(atomic_t));
	hotcpu_notifier(profile_cpu_callback, 0);
	return 0;
}
module_init(create_proc_profile);
#endif /* CONFIG_PROC_FS */
Commit	Line	Data
1da177e4 LT	1	/*
	2	* linux/kernel/profile.c
	3	* Simple profiling. Manages a direct-mapped profile hit count buffer,
	4	* with configurable resolution, support for restricting the cpus on
	5	* which profiling is done, and switching between cpu time and
	6	* schedule() calls via kernel command line parameters passed at boot.
	7	*
	8	* Scheduler profiling support, Arjan van de Ven and Ingo Molnar,
	9	* Red Hat, July 2004
	10	* Consolidation of architecture support code for profiling,
6d49e352	11	* Nadia Yvette Chambers, Oracle, July 2004
1da177e4	12	* Amortized hit count accounting via per-cpu open-addressed hashtables
6d49e352 NYC	13	* to resolve timer interrupt livelocks, Nadia Yvette Chambers,
6d49e352 NYC	14	* Oracle, 2004
1da177e4 LT	15	*/
1da177e4 LT	16
9984de1a	17	#include <linux/export.h>
1da177e4 LT	18	#include <linux/profile.h>
	19	#include <linux/bootmem.h>
	20	#include <linux/notifier.h>
	21	#include <linux/mm.h>
	22	#include <linux/cpumask.h>
	23	#include <linux/cpu.h>
1da177e4	24	#include <linux/highmem.h>
97d1f15b	25	#include <linux/mutex.h>
22b8ce94 DH	26	#include <linux/slab.h>
22b8ce94 DH	27	#include <linux/vmalloc.h>
1da177e4	28	#include <asm/sections.h>
7d12e780	29	#include <asm/irq_regs.h>
e8edc6e0	30	#include <asm/ptrace.h>
1da177e4 LT	31
	32	struct profile_hit {
	33	u32 pc, hits;
	34	};
	35	#define PROFILE_GRPSHIFT 3
	36	#define PROFILE_GRPSZ (1 << PROFILE_GRPSHIFT)
	37	#define NR_PROFILE_HIT (PAGE_SIZE/sizeof(struct profile_hit))
	38	#define NR_PROFILE_GRP (NR_PROFILE_HIT/PROFILE_GRPSZ)
	39
1da177e4 LT	40	static atomic_t *prof_buffer;
1da177e4 LT	41	static unsigned long prof_len, prof_shift;
07031e14	42
ece8a684	43	int prof_on __read_mostly;
07031e14 IM	44	EXPORT_SYMBOL_GPL(prof_on);
07031e14 IM	45
c309b917	46	static cpumask_var_t prof_cpu_mask;
1da177e4 LT	47	#ifdef CONFIG_SMP
	48	static DEFINE_PER_CPU(struct profile_hit *[2], cpu_profile_hits);
	49	static DEFINE_PER_CPU(int, cpu_profile_flip);
97d1f15b	50	static DEFINE_MUTEX(profile_flip_mutex);
1da177e4 LT	51	#endif /* CONFIG_SMP */
1da177e4 LT	52
22b8ce94	53	int profile_setup(char *str)
1da177e4	54	{
22b8ce94 DH	55	static char schedstr[] = "schedule";
	56	static char sleepstr[] = "sleep";
	57	static char kvmstr[] = "kvm";
1da177e4 LT	58	int par;
1da177e4 LT	59
ece8a684	60	if (!strncmp(str, sleepstr, strlen(sleepstr))) {
b3da2a73	61	#ifdef CONFIG_SCHEDSTATS
ece8a684 IM	62	prof_on = SLEEP_PROFILING;
	63	if (str[strlen(sleepstr)] == ',')
	64	str += strlen(sleepstr) + 1;
	65	if (get_option(&str, &par))
	66	prof_shift = par;
	67	printk(KERN_INFO
	68	"kernel sleep profiling enabled (shift: %ld)\n",
	69	prof_shift);
b3da2a73 MG	70	#else
	71	printk(KERN_WARNING
	72	"kernel sleep profiling requires CONFIG_SCHEDSTATS\n");
	73	#endif /* CONFIG_SCHEDSTATS */
a75acf85	74	} else if (!strncmp(str, schedstr, strlen(schedstr))) {
1da177e4	75	prof_on = SCHED_PROFILING;
dfaa9c94 WLII	76	if (str[strlen(schedstr)] == ',')
	77	str += strlen(schedstr) + 1;
	78	if (get_option(&str, &par))
	79	prof_shift = par;
	80	printk(KERN_INFO
	81	"kernel schedule profiling enabled (shift: %ld)\n",
	82	prof_shift);
07031e14 IM	83	} else if (!strncmp(str, kvmstr, strlen(kvmstr))) {
	84	prof_on = KVM_PROFILING;
	85	if (str[strlen(kvmstr)] == ',')
	86	str += strlen(kvmstr) + 1;
	87	if (get_option(&str, &par))
	88	prof_shift = par;
	89	printk(KERN_INFO
	90	"kernel KVM profiling enabled (shift: %ld)\n",
	91	prof_shift);
dfaa9c94	92	} else if (get_option(&str, &par)) {
1da177e4 LT	93	prof_shift = par;
	94	prof_on = CPU_PROFILING;
	95	printk(KERN_INFO "kernel profiling enabled (shift: %ld)\n",
	96	prof_shift);
	97	}
	98	return 1;
	99	}
	100	__setup("profile=", profile_setup);
	101
	102
ce05fcc3	103	int __ref profile_init(void)
1da177e4	104	{
22b8ce94	105	int buffer_bytes;
1ad82fd5	106	if (!prof_on)
22b8ce94	107	return 0;
1ad82fd5	108
1da177e4 LT	109	/* only text is profiled */
1da177e4 LT	110	prof_len = (_etext - _stext) >> prof_shift;
22b8ce94	111	buffer_bytes = prof_len*sizeof(atomic_t);
22b8ce94	112
c309b917 RR	113	if (!alloc_cpumask_var(&prof_cpu_mask, GFP_KERNEL))
	114	return -ENOMEM;
	115
acd89579 HD	116	cpumask_copy(prof_cpu_mask, cpu_possible_mask);
acd89579 HD	117
b62f495d	118	prof_buffer = kzalloc(buffer_bytes, GFP_KERNEL\|__GFP_NOWARN);
22b8ce94 DH	119	if (prof_buffer)
	120	return 0;
	121
b62f495d MG	122	prof_buffer = alloc_pages_exact(buffer_bytes,
b62f495d MG	123	GFP_KERNEL\|__GFP_ZERO\|__GFP_NOWARN);
22b8ce94 DH	124	if (prof_buffer)
	125	return 0;
	126
559fa6e7 JJ	127	prof_buffer = vzalloc(buffer_bytes);
559fa6e7 JJ	128	if (prof_buffer)
22b8ce94 DH	129	return 0;
22b8ce94 DH	130
c309b917	131	free_cpumask_var(prof_cpu_mask);
22b8ce94	132	return -ENOMEM;
1da177e4 LT	133	}
	134
	135	/* Profile event notifications */
1ad82fd5	136
e041c683 AS	137	static BLOCKING_NOTIFIER_HEAD(task_exit_notifier);
	138	static ATOMIC_NOTIFIER_HEAD(task_free_notifier);
	139	static BLOCKING_NOTIFIER_HEAD(munmap_notifier);
1ad82fd5 PC	140
1ad82fd5 PC	141	void profile_task_exit(struct task_struct *task)
1da177e4	142	{
e041c683	143	blocking_notifier_call_chain(&task_exit_notifier, 0, task);
1da177e4	144	}
1ad82fd5 PC	145
1ad82fd5 PC	146	int profile_handoff_task(struct task_struct *task)
1da177e4 LT	147	{
1da177e4 LT	148	int ret;
e041c683	149	ret = atomic_notifier_call_chain(&task_free_notifier, 0, task);
1da177e4 LT	150	return (ret == NOTIFY_OK) ? 1 : 0;
	151	}
	152
	153	void profile_munmap(unsigned long addr)
	154	{
e041c683	155	blocking_notifier_call_chain(&munmap_notifier, 0, (void *)addr);
1da177e4 LT	156	}
1da177e4 LT	157
1ad82fd5	158	int task_handoff_register(struct notifier_block *n)
1da177e4	159	{
e041c683	160	return atomic_notifier_chain_register(&task_free_notifier, n);
1da177e4	161	}
1ad82fd5	162	EXPORT_SYMBOL_GPL(task_handoff_register);
1da177e4	163
1ad82fd5	164	int task_handoff_unregister(struct notifier_block *n)
1da177e4	165	{
e041c683	166	return atomic_notifier_chain_unregister(&task_free_notifier, n);
1da177e4	167	}
1ad82fd5	168	EXPORT_SYMBOL_GPL(task_handoff_unregister);
1da177e4	169
1ad82fd5	170	int profile_event_register(enum profile_type type, struct notifier_block *n)
1da177e4 LT	171	{
1da177e4 LT	172	int err = -EINVAL;
1ad82fd5	173
1da177e4	174	switch (type) {
1ad82fd5 PC	175	case PROFILE_TASK_EXIT:
	176	err = blocking_notifier_chain_register(
	177	&task_exit_notifier, n);
	178	break;
	179	case PROFILE_MUNMAP:
	180	err = blocking_notifier_chain_register(
	181	&munmap_notifier, n);
	182	break;
1da177e4	183	}
1ad82fd5	184
1da177e4 LT	185	return err;
1da177e4 LT	186	}
1ad82fd5	187	EXPORT_SYMBOL_GPL(profile_event_register);
1da177e4	188
1ad82fd5	189	int profile_event_unregister(enum profile_type type, struct notifier_block *n)
1da177e4 LT	190	{
1da177e4 LT	191	int err = -EINVAL;
1ad82fd5	192
1da177e4	193	switch (type) {
1ad82fd5 PC	194	case PROFILE_TASK_EXIT:
	195	err = blocking_notifier_chain_unregister(
	196	&task_exit_notifier, n);
	197	break;
	198	case PROFILE_MUNMAP:
	199	err = blocking_notifier_chain_unregister(
	200	&munmap_notifier, n);
	201	break;
1da177e4 LT	202	}
1da177e4 LT	203
1da177e4 LT	204	return err;
1da177e4 LT	205	}
1ad82fd5	206	EXPORT_SYMBOL_GPL(profile_event_unregister);
1da177e4	207
1da177e4 LT	208	#ifdef CONFIG_SMP
	209	/*
	210	* Each cpu has a pair of open-addressed hashtables for pending
	211	* profile hits. read_profile() IPI's all cpus to request them
	212	* to flip buffers and flushes their contents to prof_buffer itself.
	213	* Flip requests are serialized by the profile_flip_mutex. The sole
	214	* use of having a second hashtable is for avoiding cacheline
	215	* contention that would otherwise happen during flushes of pending
	216	* profile hits required for the accuracy of reported profile hits
	217	* and so resurrect the interrupt livelock issue.
	218	*
	219	* The open-addressed hashtables are indexed by profile buffer slot
	220	* and hold the number of pending hits to that profile buffer slot on
	221	* a cpu in an entry. When the hashtable overflows, all pending hits
	222	* are accounted to their corresponding profile buffer slots with
	223	* atomic_add() and the hashtable emptied. As numerous pending hits
	224	* may be accounted to a profile buffer slot in a hashtable entry,
	225	* this amortizes a number of atomic profile buffer increments likely
	226	* to be far larger than the number of entries in the hashtable,
	227	* particularly given that the number of distinct profile buffer
	228	* positions to which hits are accounted during short intervals (e.g.
	229	* several seconds) is usually very small. Exclusion from buffer
	230	* flipping is provided by interrupt disablement (note that for
ece8a684 IM	231	* SCHED_PROFILING or SLEEP_PROFILING profile_hit() may be called from
ece8a684 IM	232	* process context).
1da177e4 LT	233	* The hash function is meant to be lightweight as opposed to strong,
	234	* and was vaguely inspired by ppc64 firmware-supported inverted
	235	* pagetable hash functions, but uses a full hashtable full of finite
	236	* collision chains, not just pairs of them.
	237	*
6d49e352	238	* -- nyc
1da177e4 LT	239	*/
	240	static void __profile_flip_buffers(void *unused)
	241	{
	242	int cpu = smp_processor_id();
	243
	244	per_cpu(cpu_profile_flip, cpu) = !per_cpu(cpu_profile_flip, cpu);
	245	}
	246
	247	static void profile_flip_buffers(void)
	248	{
	249	int i, j, cpu;
	250
97d1f15b	251	mutex_lock(&profile_flip_mutex);
1da177e4 LT	252	j = per_cpu(cpu_profile_flip, get_cpu());
1da177e4 LT	253	put_cpu();
15c8b6c1	254	on_each_cpu(__profile_flip_buffers, NULL, 1);
1da177e4 LT	255	for_each_online_cpu(cpu) {
	256	struct profile_hit *hits = per_cpu(cpu_profile_hits, cpu)[j];
	257	for (i = 0; i < NR_PROFILE_HIT; ++i) {
	258	if (!hits[i].hits) {
	259	if (hits[i].pc)
	260	hits[i].pc = 0;
	261	continue;
	262	}
	263	atomic_add(hits[i].hits, &prof_buffer[hits[i].pc]);
	264	hits[i].hits = hits[i].pc = 0;
	265	}
	266	}
97d1f15b	267	mutex_unlock(&profile_flip_mutex);
1da177e4 LT	268	}
	269
	270	static void profile_discard_flip_buffers(void)
	271	{
	272	int i, cpu;
	273
97d1f15b	274	mutex_lock(&profile_flip_mutex);
1da177e4 LT	275	i = per_cpu(cpu_profile_flip, get_cpu());
1da177e4 LT	276	put_cpu();
15c8b6c1	277	on_each_cpu(__profile_flip_buffers, NULL, 1);
1da177e4 LT	278	for_each_online_cpu(cpu) {
	279	struct profile_hit *hits = per_cpu(cpu_profile_hits, cpu)[i];
	280	memset(hits, 0, NR_PROFILE_HIT*sizeof(struct profile_hit));
	281	}
97d1f15b	282	mutex_unlock(&profile_flip_mutex);
1da177e4 LT	283	}
1da177e4 LT	284
6f7bd76f	285	static void do_profile_hits(int type, void *__pc, unsigned int nr_hits)
1da177e4 LT	286	{
	287	unsigned long primary, secondary, flags, pc = (unsigned long)__pc;
	288	int i, j, cpu;
	289	struct profile_hit *hits;
	290
1da177e4 LT	291	pc = min((pc - (unsigned long)_stext) >> prof_shift, prof_len - 1);
	292	i = primary = (pc & (NR_PROFILE_GRP - 1)) << PROFILE_GRPSHIFT;
	293	secondary = (~(pc << 1) & (NR_PROFILE_GRP - 1)) << PROFILE_GRPSHIFT;
	294	cpu = get_cpu();
	295	hits = per_cpu(cpu_profile_hits, cpu)[per_cpu(cpu_profile_flip, cpu)];
	296	if (!hits) {
	297	put_cpu();
	298	return;
	299	}
ece8a684 IM	300	/*
	301	* We buffer the global profiler buffer into a per-CPU
	302	* queue and thus reduce the number of global (and possibly
	303	* NUMA-alien) accesses. The write-queue is self-coalescing:
	304	*/
1da177e4 LT	305	local_irq_save(flags);
	306	do {
	307	for (j = 0; j < PROFILE_GRPSZ; ++j) {
	308	if (hits[i + j].pc == pc) {
ece8a684	309	hits[i + j].hits += nr_hits;
1da177e4 LT	310	goto out;
	311	} else if (!hits[i + j].hits) {
	312	hits[i + j].pc = pc;
ece8a684	313	hits[i + j].hits = nr_hits;
1da177e4 LT	314	goto out;
	315	}
	316	}
	317	i = (i + secondary) & (NR_PROFILE_HIT - 1);
	318	} while (i != primary);
ece8a684 IM	319
	320	/*
	321	* Add the current hit(s) and flush the write-queue out
	322	* to the global buffer:
	323	*/
	324	atomic_add(nr_hits, &prof_buffer[pc]);
1da177e4 LT	325	for (i = 0; i < NR_PROFILE_HIT; ++i) {
	326	atomic_add(hits[i].hits, &prof_buffer[hits[i].pc]);
	327	hits[i].pc = hits[i].hits = 0;
	328	}
	329	out:
	330	local_irq_restore(flags);
	331	put_cpu();
	332	}
	333
0db0628d	334	static int profile_cpu_callback(struct notifier_block *info,
1da177e4 LT	335	unsigned long action, void *__cpu)
	336	{
	337	int node, cpu = (unsigned long)__cpu;
	338	struct page *page;
	339
	340	switch (action) {
	341	case CPU_UP_PREPARE:
8bb78442	342	case CPU_UP_PREPARE_FROZEN:
3dd6b5fb	343	node = cpu_to_mem(cpu);
1da177e4 LT	344	per_cpu(cpu_profile_flip, cpu) = 0;
1da177e4 LT	345	if (!per_cpu(cpu_profile_hits, cpu)[1]) {
6484eb3e	346	page = alloc_pages_exact_node(node,
4199cfa0	347	GFP_KERNEL \| __GFP_ZERO,
fbd98167	348	0);
1da177e4	349	if (!page)
80b5184c	350	return notifier_from_errno(-ENOMEM);
1da177e4 LT	351	per_cpu(cpu_profile_hits, cpu)[1] = page_address(page);
	352	}
	353	if (!per_cpu(cpu_profile_hits, cpu)[0]) {
6484eb3e	354	page = alloc_pages_exact_node(node,
4199cfa0	355	GFP_KERNEL \| __GFP_ZERO,
fbd98167	356	0);
1da177e4 LT	357	if (!page)
	358	goto out_free;
	359	per_cpu(cpu_profile_hits, cpu)[0] = page_address(page);
	360	}
	361	break;
1ad82fd5	362	out_free:
1da177e4 LT	363	page = virt_to_page(per_cpu(cpu_profile_hits, cpu)[1]);
	364	per_cpu(cpu_profile_hits, cpu)[1] = NULL;
	365	__free_page(page);
80b5184c	366	return notifier_from_errno(-ENOMEM);
1da177e4	367	case CPU_ONLINE:
8bb78442	368	case CPU_ONLINE_FROZEN:
c309b917 RR	369	if (prof_cpu_mask != NULL)
c309b917 RR	370	cpumask_set_cpu(cpu, prof_cpu_mask);
1da177e4 LT	371	break;
1da177e4 LT	372	case CPU_UP_CANCELED:
8bb78442	373	case CPU_UP_CANCELED_FROZEN:
1da177e4	374	case CPU_DEAD:
8bb78442	375	case CPU_DEAD_FROZEN:
c309b917 RR	376	if (prof_cpu_mask != NULL)
c309b917 RR	377	cpumask_clear_cpu(cpu, prof_cpu_mask);
1da177e4 LT	378	if (per_cpu(cpu_profile_hits, cpu)[0]) {
	379	page = virt_to_page(per_cpu(cpu_profile_hits, cpu)[0]);
	380	per_cpu(cpu_profile_hits, cpu)[0] = NULL;
	381	__free_page(page);
	382	}
	383	if (per_cpu(cpu_profile_hits, cpu)[1]) {
	384	page = virt_to_page(per_cpu(cpu_profile_hits, cpu)[1]);
	385	per_cpu(cpu_profile_hits, cpu)[1] = NULL;
	386	__free_page(page);
	387	}
	388	break;
	389	}
	390	return NOTIFY_OK;
	391	}
1da177e4 LT	392	#else /* !CONFIG_SMP */
	393	#define profile_flip_buffers() do { } while (0)
	394	#define profile_discard_flip_buffers() do { } while (0)
02316067	395	#define profile_cpu_callback NULL
1da177e4	396
6f7bd76f	397	static void do_profile_hits(int type, void *__pc, unsigned int nr_hits)
1da177e4 LT	398	{
1da177e4 LT	399	unsigned long pc;
1da177e4	400	pc = ((unsigned long)__pc - (unsigned long)_stext) >> prof_shift;
ece8a684	401	atomic_add(nr_hits, &prof_buffer[min(pc, prof_len - 1)]);
1da177e4 LT	402	}
1da177e4 LT	403	#endif /* !CONFIG_SMP */
6f7bd76f RM	404
	405	void profile_hits(int type, void *__pc, unsigned int nr_hits)
	406	{
	407	if (prof_on != type \|\| !prof_buffer)
	408	return;
	409	do_profile_hits(type, __pc, nr_hits);
	410	}
bbe1a59b AM	411	EXPORT_SYMBOL_GPL(profile_hits);
bbe1a59b AM	412
7d12e780	413	void profile_tick(int type)
1da177e4	414	{
7d12e780 DH	415	struct pt_regs *regs = get_irq_regs();
7d12e780 DH	416
c309b917 RR	417	if (!user_mode(regs) && prof_cpu_mask != NULL &&
c309b917 RR	418	cpumask_test_cpu(smp_processor_id(), prof_cpu_mask))
1da177e4 LT	419	profile_hit(type, (void *)profile_pc(regs));
	420	}
	421
	422	#ifdef CONFIG_PROC_FS
	423	#include <linux/proc_fs.h>
583a22e7	424	#include <linux/seq_file.h>
1da177e4	425	#include <asm/uaccess.h>
1da177e4	426
583a22e7	427	static int prof_cpu_mask_proc_show(struct seq_file m, void v)
1da177e4	428	{
583a22e7 AD	429	seq_cpumask(m, prof_cpu_mask);
	430	seq_putc(m, '\n');
	431	return 0;
	432	}
	433
	434	static int prof_cpu_mask_proc_open(struct inode inode, struct file file)
	435	{
	436	return single_open(file, prof_cpu_mask_proc_show, NULL);
1da177e4 LT	437	}
1da177e4 LT	438
583a22e7 AD	439	static ssize_t prof_cpu_mask_proc_write(struct file *file,
583a22e7 AD	440	const char __user buffer, size_t count, loff_t pos)
1da177e4	441	{
c309b917	442	cpumask_var_t new_value;
583a22e7	443	int err;
1da177e4	444
c309b917 RR	445	if (!alloc_cpumask_var(&new_value, GFP_KERNEL))
c309b917 RR	446	return -ENOMEM;
1da177e4	447
c309b917 RR	448	err = cpumask_parse_user(buffer, count, new_value);
c309b917 RR	449	if (!err) {
583a22e7 AD	450	cpumask_copy(prof_cpu_mask, new_value);
583a22e7 AD	451	err = count;
c309b917 RR	452	}
	453	free_cpumask_var(new_value);
	454	return err;
1da177e4 LT	455	}
1da177e4 LT	456
583a22e7 AD	457	static const struct file_operations prof_cpu_mask_proc_fops = {
	458	.open = prof_cpu_mask_proc_open,
	459	.read = seq_read,
	460	.llseek = seq_lseek,
	461	.release = single_release,
	462	.write = prof_cpu_mask_proc_write,
	463	};
	464
fbd387ae	465	void create_prof_cpu_mask(void)
1da177e4	466	{
1da177e4	467	/* create /proc/irq/prof_cpu_mask */
fbd387ae	468	proc_create("irq/prof_cpu_mask", 0600, NULL, &prof_cpu_mask_proc_fops);
1da177e4 LT	469	}
	470
	471	/*
	472	* This function accesses profiling information. The returned data is
	473	* binary: the sampling step and the actual contents of the profile
	474	* buffer. Use of the program readprofile is recommended in order to
	475	* get meaningful info out of these data.
	476	*/
	477	static ssize_t
	478	read_profile(struct file file, char __user buf, size_t count, loff_t *ppos)
	479	{
	480	unsigned long p = *ppos;
	481	ssize_t read;
1ad82fd5	482	char *pnt;
1da177e4 LT	483	unsigned int sample_step = 1 << prof_shift;
	484
	485	profile_flip_buffers();
	486	if (p >= (prof_len+1)*sizeof(unsigned int))
	487	return 0;
	488	if (count > (prof_len+1)*sizeof(unsigned int) - p)
	489	count = (prof_len+1)*sizeof(unsigned int) - p;
	490	read = 0;
	491
	492	while (p < sizeof(unsigned int) && count > 0) {
1ad82fd5	493	if (put_user(((char )(&sample_step)+p), buf))
064b022c	494	return -EFAULT;
1da177e4 LT	495	buf++; p++; count--; read++;
	496	}
	497	pnt = (char *)prof_buffer + p - sizeof(atomic_t);
1ad82fd5	498	if (copy_to_user(buf, (void *)pnt, count))
1da177e4 LT	499	return -EFAULT;
	500	read += count;
	501	*ppos += read;
	502	return read;
	503	}
	504
	505	/*
	506	* Writing to /proc/profile resets the counters
	507	*
	508	* Writing a 'profiling multiplier' value into it also re-sets the profiling
	509	* interrupt frequency, on architectures that support this.
	510	*/
	511	static ssize_t write_profile(struct file file, const char __user buf,
	512	size_t count, loff_t *ppos)
	513	{
	514	#ifdef CONFIG_SMP
1ad82fd5	515	extern int setup_profiling_timer(unsigned int multiplier);
1da177e4 LT	516
	517	if (count == sizeof(int)) {
	518	unsigned int multiplier;
	519
	520	if (copy_from_user(&multiplier, buf, sizeof(int)))
	521	return -EFAULT;
	522
	523	if (setup_profiling_timer(multiplier))
	524	return -EINVAL;
	525	}
	526	#endif
	527	profile_discard_flip_buffers();
	528	memset(prof_buffer, 0, prof_len * sizeof(atomic_t));
	529	return count;
	530	}
	531
15ad7cdc	532	static const struct file_operations proc_profile_operations = {
1da177e4 LT	533	.read = read_profile,
1da177e4 LT	534	.write = write_profile,
6038f373	535	.llseek = default_llseek,
1da177e4 LT	536	};
	537
	538	#ifdef CONFIG_SMP
60a51513	539	static void profile_nop(void *unused)
1da177e4 LT	540	{
	541	}
	542
22b8ce94	543	static int create_hash_tables(void)
1da177e4 LT	544	{
	545	int cpu;
	546
	547	for_each_online_cpu(cpu) {
3dd6b5fb	548	int node = cpu_to_mem(cpu);
1da177e4 LT	549	struct page *page;
1da177e4 LT	550
6484eb3e	551	page = alloc_pages_exact_node(node,
e97ca8e5	552	GFP_KERNEL \| __GFP_ZERO \| __GFP_THISNODE,
fbd98167	553	0);
1da177e4 LT	554	if (!page)
	555	goto out_cleanup;
	556	per_cpu(cpu_profile_hits, cpu)[1]
	557	= (struct profile_hit *)page_address(page);
6484eb3e	558	page = alloc_pages_exact_node(node,
e97ca8e5	559	GFP_KERNEL \| __GFP_ZERO \| __GFP_THISNODE,
fbd98167	560	0);
1da177e4 LT	561	if (!page)
	562	goto out_cleanup;
	563	per_cpu(cpu_profile_hits, cpu)[0]
	564	= (struct profile_hit *)page_address(page);
	565	}
	566	return 0;
	567	out_cleanup:
	568	prof_on = 0;
d59dd462	569	smp_mb();
15c8b6c1	570	on_each_cpu(profile_nop, NULL, 1);
1da177e4 LT	571	for_each_online_cpu(cpu) {
	572	struct page *page;
	573
	574	if (per_cpu(cpu_profile_hits, cpu)[0]) {
	575	page = virt_to_page(per_cpu(cpu_profile_hits, cpu)[0]);
	576	per_cpu(cpu_profile_hits, cpu)[0] = NULL;
	577	__free_page(page);
	578	}
	579	if (per_cpu(cpu_profile_hits, cpu)[1]) {
	580	page = virt_to_page(per_cpu(cpu_profile_hits, cpu)[1]);
	581	per_cpu(cpu_profile_hits, cpu)[1] = NULL;
	582	__free_page(page);
	583	}
	584	}
	585	return -1;
	586	}
	587	#else
	588	#define create_hash_tables() ({ 0; })
	589	#endif
	590
84196414	591	int __ref create_proc_profile(void) /* false positive from hotcpu_notifier */
1da177e4 LT	592	{
	593	struct proc_dir_entry *entry;
	594
	595	if (!prof_on)
	596	return 0;
	597	if (create_hash_tables())
22b8ce94	598	return -ENOMEM;
c33fff0a DL	599	entry = proc_create("profile", S_IWUSR \| S_IRUGO,
c33fff0a DL	600	NULL, &proc_profile_operations);
1ad82fd5	601	if (!entry)
1da177e4	602	return 0;
271a15ea	603	proc_set_size(entry, (1 + prof_len) * sizeof(atomic_t));
1da177e4 LT	604	hotcpu_notifier(profile_cpu_callback, 0);
	605	return 0;
	606	}
	607	module_init(create_proc_profile);
	608	#endif /* CONFIG_PROC_FS */