[lttv.git] / trunk / tests / kernel / test-fair-rwlock.c

/* test-fair-rwlock.c
 *
 */

#include <linux/module.h>
#include <linux/proc_fs.h>
#include <linux/sched.h>
#include <linux/timex.h>
#include <linux/fair-rwlock.h>
#include <linux/kthread.h>
#include <linux/delay.h>
#include <linux/hardirq.h>
#include <linux/module.h>
#include <linux/percpu.h>
#include <asm/ptrace.h>

#if (NR_CPUS > 64 && (BITS_PER_LONG == 32 || NR_CPUS > 32768))
#error "fair rwlock needs more bits per long to deal with that many CPUs"
#endif

/* Test with no contention duration, in seconds */
#define SINGLE_WRITER_TEST_DURATION 10
#define SINGLE_READER_TEST_DURATION 10
#define MULTIPLE_READERS_TEST_DURATION 10

/* Test duration, in seconds */
#define TEST_DURATION 60

#define THREAD_ROFFSET	1UL
#define THREAD_RMASK	((NR_CPUS - 1) * THREAD_ROFFSET)
#define SOFTIRQ_ROFFSET	(THREAD_RMASK + 1)
#define SOFTIRQ_RMASK	((NR_CPUS - 1) * SOFTIRQ_ROFFSET)
#define HARDIRQ_ROFFSET	((SOFTIRQ_RMASK | THREAD_RMASK) + 1)
#define HARDIRQ_RMASK	((NR_CPUS - 1) * HARDIRQ_ROFFSET)

#define SUBSCRIBERS_WOFFSET	\
	((HARDIRQ_RMASK | SOFTIRQ_RMASK | THREAD_RMASK) + 1)
#define SUBSCRIBERS_WMASK	\
	((NR_CPUS - 1) * SUBSCRIBERS_WOFFSET)
#define WRITER_MUTEX		\
	((SUBSCRIBERS_WMASK | HARDIRQ_RMASK | SOFTIRQ_RMASK | THREAD_RMASK) + 1)
#define SOFTIRQ_WMASK	(WRITER_MUTEX << 1)
#define SOFTIRQ_WOFFSET	SOFTIRQ_WMASK
#define HARDIRQ_WMASK	(SOFTIRQ_WMASK << 1)
#define HARDIRQ_WOFFSET	HARDIRQ_WMASK

#define NR_VARS 100
#define NR_WRITERS 2
#define NR_TRYLOCK_WRITERS 2
#define NR_READERS 4
#define NR_TRYLOCK_READERS 2

/*
 * 1 : test with thread and interrupt readers.
 * 0 : test only with thread readers.
 */
#define TEST_INTERRUPTS 1

#if (TEST_INTERRUPTS)
#define NR_INTERRUPT_READERS 1
#define NR_TRYLOCK_INTERRUPT_READERS 1
#else
#define NR_INTERRUPT_READERS 0
#define NR_TRYLOCK_INTERRUPT_READERS 0
#endif

/*
 * Writer iteration delay, in us. 0 for busy loop. Caution : writers can
 * starve readers.
 */
#define WRITER_DELAY 10
#define TRYLOCK_WRITER_DELAY 1000

/*
 * Number of iterations after which a trylock writer fails.
 * -1 for infinite loop.
 */
#define TRYLOCK_WRITERS_FAIL_ITER 100

/* Thread and interrupt reader delay, in ms */
#define THREAD_READER_DELAY 0	/* busy loop */
#define INTERRUPT_READER_DELAY 100

static int var[NR_VARS];
static struct task_struct *reader_threads[NR_READERS];
static struct task_struct *trylock_reader_threads[NR_TRYLOCK_READERS];
static struct task_struct *writer_threads[NR_WRITERS];
static struct task_struct *trylock_writer_threads[NR_TRYLOCK_WRITERS];
static struct task_struct *interrupt_reader[NR_INTERRUPT_READERS];
static struct task_struct *trylock_interrupt_reader[NR_TRYLOCK_INTERRUPT_READERS];

static struct fair_rwlock frwlock = {
	.value = ATOMIC_LONG_INIT(0),
};

static cycles_t cycles_calibration_min,
	cycles_calibration_avg,
	cycles_calibration_max;

static inline cycles_t calibrate_cycles(cycles_t cycles)
{
	return cycles - cycles_calibration_avg;
}

struct proc_dir_entry *pentry = NULL;

static int reader_thread(void *data)
{
	int i;
	int prev, cur;
	unsigned long iter = 0;
	cycles_t time1, time2, delay, delaymax = 0, delaymin = ULLONG_MAX,
		delayavg = 0;

	printk("reader_thread/%lu runnning\n", (unsigned long)data);
	do {
		iter++;
		preempt_disable();	/* for get_cycles accuracy */
		rdtsc_barrier();
		time1 = get_cycles();
		rdtsc_barrier();

		fair_read_lock(&frwlock);

		rdtsc_barrier();
		time2 = get_cycles();
		rdtsc_barrier();
		delay = time2 - time1;
		delaymax = max(delaymax, delay);
		delaymin = min(delaymin, delay);
		delayavg += delay;
		prev = var[0];
		for (i = 1; i < NR_VARS; i++) {
			cur = var[i];
			if (cur != prev)
				printk(KERN_ALERT
				"Unequal cur %d/prev %d at i %d, iter %lu "
				"in thread\n", cur, prev, i, iter);
		}
		fair_read_unlock(&frwlock);
		preempt_enable();	/* for get_cycles accuracy */
		if (THREAD_READER_DELAY)
			msleep(THREAD_READER_DELAY);
	} while (!kthread_should_stop());
	if (!iter) {
		printk("reader_thread/%lu iterations : %lu",
			(unsigned long)data, iter);
	} else {
		delayavg /= iter;
		printk("reader_thread/%lu iterations : %lu, "
			"lock delay [min,avg,max] %llu,%llu,%llu cycles\n",
			(unsigned long)data, iter,
			calibrate_cycles(delaymin),
			calibrate_cycles(delayavg),
			calibrate_cycles(delaymax));
	}
	return 0;
}

static int trylock_reader_thread(void *data)
{
	int i;
	int prev, cur;
	unsigned long iter = 0, success_iter = 0;

	printk("trylock_reader_thread/%lu runnning\n", (unsigned long)data);
	do {
		while (!fair_read_trylock(&frwlock))
			iter++;
		success_iter++;
		prev = var[0];
		for (i = 1; i < NR_VARS; i++) {
			cur = var[i];
			if (cur != prev)
				printk(KERN_ALERT
				"Unequal cur %d/prev %d at i %d, iter %lu "
				"in thread\n", cur, prev, i, iter);
		}
		fair_read_unlock(&frwlock);
		if (THREAD_READER_DELAY)
			msleep(THREAD_READER_DELAY);
	} while (!kthread_should_stop());
	printk("trylock_reader_thread/%lu iterations : %lu, "
		"successful iterations : %lu\n",
		(unsigned long)data, iter, success_iter);
	return 0;
}

DEFINE_PER_CPU(cycles_t, int_delaymin);
DEFINE_PER_CPU(cycles_t, int_delayavg);
DEFINE_PER_CPU(cycles_t, int_delaymax);
DEFINE_PER_CPU(cycles_t, int_ipi_nr);

static void interrupt_reader_ipi(void *data)
{
	int i;
	int prev, cur;
	cycles_t time1, time2;
	cycles_t *delaymax, *delaymin, *delayavg, *ipi_nr, delay;

	/*
	 * Skip the ipi caller, not in irq context.
	 */
	if (!in_irq())
		return;

	delaymax = &per_cpu(int_delaymax, smp_processor_id());
	delaymin = &per_cpu(int_delaymin, smp_processor_id());
	delayavg = &per_cpu(int_delayavg, smp_processor_id());
	ipi_nr = &per_cpu(int_ipi_nr, smp_processor_id());

	rdtsc_barrier();
	time1 = get_cycles();
	rdtsc_barrier();

	fair_read_lock(&frwlock);

	rdtsc_barrier();
	time2 = get_cycles();
	rdtsc_barrier();
	delay = time2 - time1;
	*delaymax = max(*delaymax, delay);
	*delaymin = min(*delaymin, delay);
	*delayavg += delay;
	(*ipi_nr)++;
	prev = var[0];
	for (i = 1; i < NR_VARS; i++) {
		cur = var[i];
		if (cur != prev)
			printk(KERN_ALERT
			"Unequal cur %d/prev %d at i %d in interrupt\n",
				cur, prev, i);
	}
	fair_read_unlock(&frwlock);
}

DEFINE_PER_CPU(unsigned long, trylock_int_iter);
DEFINE_PER_CPU(unsigned long, trylock_int_success);

static void trylock_interrupt_reader_ipi(void *data)
{
	int i;
	int prev, cur;

	/*
	 * Skip the ipi caller, not in irq context.
	 */
	if (!in_irq())
		return;

	per_cpu(trylock_int_iter, smp_processor_id())++;
	while (!fair_read_trylock(&frwlock))
		per_cpu(trylock_int_iter, smp_processor_id())++;
	per_cpu(trylock_int_success, smp_processor_id())++;
	prev = var[0];
	for (i = 1; i < NR_VARS; i++) {
		cur = var[i];
		if (cur != prev)
			printk(KERN_ALERT
			"Unequal cur %d/prev %d at i %d in interrupt\n",
				cur, prev, i);
	}
	fair_read_unlock(&frwlock);
}


static int interrupt_reader_thread(void *data)
{
	unsigned long iter = 0;
	int i;

	for_each_online_cpu(i) {
		per_cpu(int_delaymax, i) = 0;
		per_cpu(int_delaymin, i) = ULLONG_MAX;
		per_cpu(int_delayavg, i) = 0;
		per_cpu(int_ipi_nr, i) = 0;
	}
	do {
		iter++;
		on_each_cpu(interrupt_reader_ipi, NULL, 0);
		if (INTERRUPT_READER_DELAY)
			msleep(INTERRUPT_READER_DELAY);
	} while (!kthread_should_stop());
	printk("interrupt_reader_thread/%lu iterations : %lu\n",
			(unsigned long)data, iter);
	for_each_online_cpu(i) {
		if (!per_cpu(int_ipi_nr, i))
			continue;
		per_cpu(int_delayavg, i) /= per_cpu(int_ipi_nr, i);
		printk("interrupt readers on CPU %i, "
			"lock delay [min,avg,max] %llu,%llu,%llu cycles\n",
			i,
			calibrate_cycles(per_cpu(int_delaymin, i)),
			calibrate_cycles(per_cpu(int_delayavg, i)),
			calibrate_cycles(per_cpu(int_delaymax, i)));
	}
	return 0;
}

static int trylock_interrupt_reader_thread(void *data)
{
	unsigned long iter = 0;
	int i;

	do {
		iter++;
		on_each_cpu(trylock_interrupt_reader_ipi, NULL, 0);
		if (INTERRUPT_READER_DELAY)
			msleep(INTERRUPT_READER_DELAY);
	} while (!kthread_should_stop());
	printk("trylock_interrupt_reader_thread/%lu iterations : %lu\n",
			(unsigned long)data, iter);
	for_each_online_cpu(i) {
		printk("trylock interrupt readers on CPU %i, "
			"iterations %lu, "
			"successful iterations : %lu\n",
			i, per_cpu(trylock_int_iter, i),
			per_cpu(trylock_int_success, i));
		per_cpu(trylock_int_iter, i) = 0;
		per_cpu(trylock_int_success, i) = 0;
	}
	return 0;
}

static int writer_thread(void *data)
{
	int i;
	int new;
	unsigned long iter = 0;
	cycles_t time1, time2, delay, delaymax = 0, delaymin = ULLONG_MAX,
		delayavg = 0;

	printk("writer_thread/%lu runnning\n", (unsigned long)data);
	do {
		iter++;
		preempt_disable();	/* for get_cycles accuracy */
		rdtsc_barrier();
		time1 = get_cycles();
		rdtsc_barrier();

#if (TEST_INTERRUPTS)
		fair_write_lock_irq(&frwlock);
#else
		fair_write_lock(&frwlock);
#endif

		rdtsc_barrier();
		time2 = get_cycles();
		rdtsc_barrier();
		delay = time2 - time1;
		delaymax = max(delaymax, delay);
		delaymin = min(delaymin, delay);
		delayavg += delay;
		new = (int)get_cycles();
		for (i = 0; i < NR_VARS; i++) {
			var[i] = new;
		}
#if (TEST_INTERRUPTS)
		fair_write_unlock_irq(&frwlock);
#else
		fair_write_unlock(&frwlock);
#endif
		preempt_enable();	/* for get_cycles accuracy */
		if (WRITER_DELAY > 0)
			udelay(WRITER_DELAY);
	} while (!kthread_should_stop());
	delayavg /= iter;
	printk("writer_thread/%lu iterations : %lu, "
		"lock delay [min,avg,max] %llu,%llu,%llu cycles\n",
		(unsigned long)data, iter,
		calibrate_cycles(delaymin),
		calibrate_cycles(delayavg),
		calibrate_cycles(delaymax));
	return 0;
}

static int trylock_writer_thread(void *data)
{
	int i;
	int new;
	unsigned long iter = 0, success = 0, fail = 0;

	printk("trylock_writer_thread/%lu runnning\n", (unsigned long)data);
	do {
		iter++;
#if (TEST_INTERRUPTS)
		if (fair_write_trylock_irq_else_subscribe(&frwlock))
#else
		if (fair_write_trylock_else_subscribe(&frwlock))
#endif
			goto locked;
#if (TRYLOCK_WRITERS_FAIL_ITER == -1)
		for (;;) {
			iter++;
#if (TEST_INTERRUPTS)
			if (fair_write_trylock_irq_subscribed(&frwlock))
#else
			if (fair_write_trylock_subscribed(&frwlock))
#endif
				goto locked;
		}
#else
		for (i = 0; i < TRYLOCK_WRITERS_FAIL_ITER; i++) {
			iter++;
#if (TEST_INTERRUPTS)
			if (fair_write_trylock_irq_subscribed(&frwlock))
#else
			if (fair_write_trylock_subscribed(&frwlock))
#endif
				goto locked;
		}
#endif
		fail++;
		fair_write_unsubscribe(&frwlock);
		goto loop;
locked:
		success++;
		new = (int)get_cycles();
		for (i = 0; i < NR_VARS; i++) {
			var[i] = new;
		}
#if (TEST_INTERRUPTS)
		fair_write_unlock_irq(&frwlock);
#else
		fair_write_unlock(&frwlock);
#endif
loop:
		if (TRYLOCK_WRITER_DELAY > 0)
			udelay(TRYLOCK_WRITER_DELAY);
	} while (!kthread_should_stop());
	printk("trylock_writer_thread/%lu iterations : "
		"[try,success,fail after %d try], "
		"%lu,%lu,%lu\n",
		(unsigned long)data, TRYLOCK_WRITERS_FAIL_ITER,
		iter, success, fail);
	return 0;
}

static void fair_rwlock_create(void)
{
	unsigned long i;

	for (i = 0; i < NR_READERS; i++) {
		printk("starting reader thread %lu\n", i);
		reader_threads[i] = kthread_run(reader_thread, (void *)i,
			"frwlock_reader");
		BUG_ON(!reader_threads[i]);
	}

	for (i = 0; i < NR_TRYLOCK_READERS; i++) {
		printk("starting trylock reader thread %lu\n", i);
		trylock_reader_threads[i] = kthread_run(trylock_reader_thread,
			(void *)i, "frwlock_trylock_reader");
		BUG_ON(!trylock_reader_threads[i]);
	}
	for (i = 0; i < NR_INTERRUPT_READERS; i++) {
		printk("starting interrupt reader %lu\n", i);
		interrupt_reader[i] = kthread_run(interrupt_reader_thread,
			(void *)i,
			"frwlock_interrupt_reader");
	}
	for (i = 0; i < NR_TRYLOCK_INTERRUPT_READERS; i++) {
		printk("starting trylock interrupt reader %lu\n", i);
		trylock_interrupt_reader[i] =
			kthread_run(trylock_interrupt_reader_thread,
			(void *)i, "frwlock_trylock_interrupt_reader");
	}
	for (i = 0; i < NR_WRITERS; i++) {
		printk("starting writer thread %lu\n", i);
		writer_threads[i] = kthread_run(writer_thread, (void *)i,
			"frwlock_writer");
		BUG_ON(!writer_threads[i]);
	}
	for (i = 0; i < NR_TRYLOCK_WRITERS; i++) {
		printk("starting trylock writer thread %lu\n", i);
		trylock_writer_threads[i] = kthread_run(trylock_writer_thread,
			(void *)i, "frwlock_trylock_writer");
		BUG_ON(!trylock_writer_threads[i]);
	}
}

static void fair_rwlock_stop(void)
{
	unsigned long i;

	for (i = 0; i < NR_WRITERS; i++)
		kthread_stop(writer_threads[i]);
	for (i = 0; i < NR_TRYLOCK_WRITERS; i++)
		kthread_stop(trylock_writer_threads[i]);
	for (i = 0; i < NR_READERS; i++)
		kthread_stop(reader_threads[i]);
	for (i = 0; i < NR_TRYLOCK_READERS; i++)
		kthread_stop(trylock_reader_threads[i]);
	for (i = 0; i < NR_INTERRUPT_READERS; i++)
		kthread_stop(interrupt_reader[i]);
	for (i = 0; i < NR_TRYLOCK_INTERRUPT_READERS; i++)
		kthread_stop(trylock_interrupt_reader[i]);
}


static void perform_test(const char *name, void (*callback)(void))
{
	printk("%s\n", name);
	callback();
}

static int my_open(struct inode *inode, struct file *file)
{
	unsigned long i;
	cycles_t time1, time2, delay;

	printk("** get_cycles calibration **\n");
	cycles_calibration_min = ULLONG_MAX;
	cycles_calibration_avg = 0;
	cycles_calibration_max = 0;

	local_irq_disable();
	for (i = 0; i < 10; i++) {
		rdtsc_barrier();
		time1 = get_cycles();
		rdtsc_barrier();
		rdtsc_barrier();
		time2 = get_cycles();
		rdtsc_barrier();
		delay = time2 - time1;
		cycles_calibration_min = min(cycles_calibration_min, delay);
		cycles_calibration_avg += delay;
		cycles_calibration_max = max(cycles_calibration_max, delay);
	}
	cycles_calibration_avg /= 10;
	local_irq_enable();

	printk("get_cycles takes [min,avg,max] %llu,%llu,%llu cycles, "
		"results calibrated on avg\n",
		cycles_calibration_min,
		cycles_calibration_avg,
		cycles_calibration_max);

	printk("** Single writer test, no contention **\n");
	writer_threads[0] = kthread_run(writer_thread, (void *)0,
		"frwlock_writer");
	BUG_ON(!writer_threads[0]);
	ssleep(SINGLE_WRITER_TEST_DURATION);
	kthread_stop(writer_threads[0]);

	printk("** Single trylock writer test, no contention **\n");
	trylock_writer_threads[0] = kthread_run(trylock_writer_thread,
		(void *)0,
		"trylock_frwlock_writer");
	BUG_ON(!trylock_writer_threads[0]);
	ssleep(SINGLE_WRITER_TEST_DURATION);
	kthread_stop(trylock_writer_threads[0]);

	printk("** Single reader test, no contention **\n");
	reader_threads[0] = kthread_run(reader_thread, (void *)0,
		"frwlock_reader");
	BUG_ON(!reader_threads[0]);
	ssleep(SINGLE_READER_TEST_DURATION);
	kthread_stop(reader_threads[0]);

	printk("** Multiple readers test, no contention **\n");
	for (i = 0; i < NR_READERS; i++) {
		printk("starting reader thread %lu\n", i);
		reader_threads[i] = kthread_run(reader_thread, (void *)i,
			"frwlock_reader");
		BUG_ON(!reader_threads[i]);
	}
	ssleep(SINGLE_READER_TEST_DURATION);
	for (i = 0; i < NR_READERS; i++)
		kthread_stop(reader_threads[i]);

	printk("** High contention test **\n");
	perform_test("fair-rwlock-create", fair_rwlock_create);
	ssleep(TEST_DURATION);
	perform_test("fair-rwlock-stop", fair_rwlock_stop);

	return -EPERM;
}


static struct file_operations my_operations = {
	.open = my_open,
};

int init_module(void)
{
	pentry = create_proc_entry("testfrwlock", 0444, NULL);
	if (pentry)
		pentry->proc_fops = &my_operations;

	printk("NR_CPUS : %d\n", NR_CPUS);
	printk("THREAD_ROFFSET : %lX\n", THREAD_ROFFSET);
	printk("THREAD_RMASK : %lX\n", THREAD_RMASK);
	printk("SOFTIRQ_ROFFSET : %lX\n", SOFTIRQ_ROFFSET);
	printk("SOFTIRQ_RMASK : %lX\n", SOFTIRQ_RMASK);
	printk("HARDIRQ_ROFFSET : %lX\n", HARDIRQ_ROFFSET);
	printk("HARDIRQ_RMASK : %lX\n", HARDIRQ_RMASK);
	printk("SUBSCRIBERS_WOFFSET : %lX\n", SUBSCRIBERS_WOFFSET);
	printk("SUBSCRIBERS_WMASK : %lX\n", SUBSCRIBERS_WMASK);
	printk("WRITER_MUTEX : %lX\n", WRITER_MUTEX);
	printk("SOFTIRQ_WMASK : %lX\n", SOFTIRQ_WMASK);
	printk("HARDIRQ_WMASK : %lX\n", HARDIRQ_WMASK);

	return 0;
}

void cleanup_module(void)
{
	remove_proc_entry("testfrwlock", NULL);
}

MODULE_LICENSE("GPL");
MODULE_AUTHOR("Mathieu Desnoyers");
MODULE_DESCRIPTION("Fair rwlock test");
Commit	Line	Data
f0a36bb1	1	/* test-fair-rwlock.c
	2	*
	3	*/
	4
	5	#include <linux/module.h>
	6	#include <linux/proc_fs.h>
	7	#include <linux/sched.h>
	8	#include <linux/timex.h>
	9	#include <linux/fair-rwlock.h>
	10	#include <linux/kthread.h>
	11	#include <linux/delay.h>
	12	#include <linux/hardirq.h>
	13	#include <linux/module.h>
7f563886	14	#include <linux/percpu.h>
f0a36bb1	15	#include <asm/ptrace.h>
f0a36bb1	16
7f563886	17	#if (NR_CPUS > 64 && (BITS_PER_LONG == 32 \|\| NR_CPUS > 32768))
f0a36bb1	18	#error "fair rwlock needs more bits per long to deal with that many CPUs"
	19	#endif
	20
68f25f81	21	/* Test with no contention duration, in seconds */
	22	#define SINGLE_WRITER_TEST_DURATION 10
	23	#define SINGLE_READER_TEST_DURATION 10
	24	#define MULTIPLE_READERS_TEST_DURATION 10
	25
89889f86	26	/* Test duration, in seconds */
f36c4112	27	#define TEST_DURATION 60
89889f86	28
f0a36bb1	29	#define THREAD_ROFFSET 1UL
	30	#define THREAD_RMASK ((NR_CPUS - 1) * THREAD_ROFFSET)
	31	#define SOFTIRQ_ROFFSET (THREAD_RMASK + 1)
	32	#define SOFTIRQ_RMASK ((NR_CPUS - 1) * SOFTIRQ_ROFFSET)
	33	#define HARDIRQ_ROFFSET ((SOFTIRQ_RMASK \| THREAD_RMASK) + 1)
	34	#define HARDIRQ_RMASK ((NR_CPUS - 1) * HARDIRQ_ROFFSET)
	35
7f563886	36	#define SUBSCRIBERS_WOFFSET \
	37	((HARDIRQ_RMASK \| SOFTIRQ_RMASK \| THREAD_RMASK) + 1)
	38	#define SUBSCRIBERS_WMASK \
	39	((NR_CPUS - 1) * SUBSCRIBERS_WOFFSET)
	40	#define WRITER_MUTEX \
	41	((SUBSCRIBERS_WMASK \| HARDIRQ_RMASK \| SOFTIRQ_RMASK \| THREAD_RMASK) + 1)
	42	#define SOFTIRQ_WMASK (WRITER_MUTEX << 1)
	43	#define SOFTIRQ_WOFFSET SOFTIRQ_WMASK
426d6b67	44	#define HARDIRQ_WMASK (SOFTIRQ_WMASK << 1)
7f563886	45	#define HARDIRQ_WOFFSET HARDIRQ_WMASK
f0a36bb1	46
f0a36bb1	47	#define NR_VARS 100
1c21e42c	48	#define NR_WRITERS 2
	49	#define NR_TRYLOCK_WRITERS 2
	50	#define NR_READERS 4
	51	#define NR_TRYLOCK_READERS 2
4fd25765	52
	53	/*
	54	* 1 : test with thread and interrupt readers.
	55	* 0 : test only with thread readers.
	56	*/
	57	#define TEST_INTERRUPTS 1
	58
	59	#if (TEST_INTERRUPTS)
1c21e42c	60	#define NR_INTERRUPT_READERS 1
1c21e42c	61	#define NR_TRYLOCK_INTERRUPT_READERS 1
4fd25765	62	#else
	63	#define NR_INTERRUPT_READERS 0
	64	#define NR_TRYLOCK_INTERRUPT_READERS 0
	65	#endif
f0a36bb1	66
4d1751f9	67	/*
	68	* Writer iteration delay, in us. 0 for busy loop. Caution : writers can
	69	* starve readers.
	70	*/
	71	#define WRITER_DELAY 10
4fd25765	72	#define TRYLOCK_WRITER_DELAY 1000
	73
	74	/*
	75	* Number of iterations after which a trylock writer fails.
	76	* -1 for infinite loop.
	77	*/
	78	#define TRYLOCK_WRITERS_FAIL_ITER 100
	79
	80	/* Thread and interrupt reader delay, in ms */
	81	#define THREAD_READER_DELAY 0 /* busy loop */
	82	#define INTERRUPT_READER_DELAY 100
89889f86	83
f0a36bb1	84	static int var[NR_VARS];
f0a36bb1	85	static struct task_struct *reader_threads[NR_READERS];
1c21e42c	86	static struct task_struct *trylock_reader_threads[NR_TRYLOCK_READERS];
f0a36bb1	87	static struct task_struct *writer_threads[NR_WRITERS];
1c21e42c	88	static struct task_struct *trylock_writer_threads[NR_TRYLOCK_WRITERS];
4fd25765	89	static struct task_struct *interrupt_reader[NR_INTERRUPT_READERS];
4fd25765	90	static struct task_struct *trylock_interrupt_reader[NR_TRYLOCK_INTERRUPT_READERS];
f0a36bb1	91
	92	static struct fair_rwlock frwlock = {
	93	.value = ATOMIC_LONG_INIT(0),
f0a36bb1	94	};
f0a36bb1	95
68f25f81	96	static cycles_t cycles_calibration_min,
	97	cycles_calibration_avg,
	98	cycles_calibration_max;
	99
	100	static inline cycles_t calibrate_cycles(cycles_t cycles)
	101	{
	102	return cycles - cycles_calibration_avg;
	103	}
	104
f0a36bb1	105	struct proc_dir_entry *pentry = NULL;
	106
	107	static int reader_thread(void *data)
	108	{
	109	int i;
	110	int prev, cur;
	111	unsigned long iter = 0;
68f25f81	112	cycles_t time1, time2, delay, delaymax = 0, delaymin = ULLONG_MAX,
68f25f81	113	delayavg = 0;
f0a36bb1	114
	115	printk("reader_thread/%lu runnning\n", (unsigned long)data);
	116	do {
	117	iter++;
7f563886	118	preempt_disable(); /* for get_cycles accuracy */
68f25f81	119	rdtsc_barrier();
7f563886	120	time1 = get_cycles();
68f25f81	121	rdtsc_barrier();
68f25f81	122
f0a36bb1	123	fair_read_lock(&frwlock);
68f25f81	124
68f25f81	125	rdtsc_barrier();
7f563886	126	time2 = get_cycles();
68f25f81	127	rdtsc_barrier();
	128	delay = time2 - time1;
	129	delaymax = max(delaymax, delay);
	130	delaymin = min(delaymin, delay);
	131	delayavg += delay;
f0a36bb1	132	prev = var[0];
	133	for (i = 1; i < NR_VARS; i++) {
	134	cur = var[i];
	135	if (cur != prev)
	136	printk(KERN_ALERT
	137	"Unequal cur %d/prev %d at i %d, iter %lu "
	138	"in thread\n", cur, prev, i, iter);
	139	}
	140	fair_read_unlock(&frwlock);
7f563886	141	preempt_enable(); /* for get_cycles accuracy */
4fd25765	142	if (THREAD_READER_DELAY)
4fd25765	143	msleep(THREAD_READER_DELAY);
f0a36bb1	144	} while (!kthread_should_stop());
4fd25765	145	if (!iter) {
	146	printk("reader_thread/%lu iterations : %lu",
	147	(unsigned long)data, iter);
	148	} else {
	149	delayavg /= iter;
	150	printk("reader_thread/%lu iterations : %lu, "
	151	"lock delay [min,avg,max] %llu,%llu,%llu cycles\n",
	152	(unsigned long)data, iter,
	153	calibrate_cycles(delaymin),
	154	calibrate_cycles(delayavg),
	155	calibrate_cycles(delaymax));
	156	}
f0a36bb1	157	return 0;
	158	}
	159
1c21e42c	160	static int trylock_reader_thread(void *data)
	161	{
	162	int i;
	163	int prev, cur;
	164	unsigned long iter = 0, success_iter = 0;
	165
	166	printk("trylock_reader_thread/%lu runnning\n", (unsigned long)data);
	167	do {
	168	while (!fair_read_trylock(&frwlock))
	169	iter++;
	170	success_iter++;
	171	prev = var[0];
	172	for (i = 1; i < NR_VARS; i++) {
	173	cur = var[i];
	174	if (cur != prev)
	175	printk(KERN_ALERT
	176	"Unequal cur %d/prev %d at i %d, iter %lu "
	177	"in thread\n", cur, prev, i, iter);
	178	}
	179	fair_read_unlock(&frwlock);
4fd25765	180	if (THREAD_READER_DELAY)
4fd25765	181	msleep(THREAD_READER_DELAY);
1c21e42c	182	} while (!kthread_should_stop());
	183	printk("trylock_reader_thread/%lu iterations : %lu, "
	184	"successful iterations : %lu\n",
	185	(unsigned long)data, iter, success_iter);
	186	return 0;
	187	}
	188
68f25f81	189	DEFINE_PER_CPU(cycles_t, int_delaymin);
68f25f81	190	DEFINE_PER_CPU(cycles_t, int_delayavg);
7f563886	191	DEFINE_PER_CPU(cycles_t, int_delaymax);
68f25f81	192	DEFINE_PER_CPU(cycles_t, int_ipi_nr);
7f563886	193
f0a36bb1	194	static void interrupt_reader_ipi(void *data)
	195	{
	196	int i;
	197	int prev, cur;
7f563886	198	cycles_t time1, time2;
68f25f81	199	cycles_t delaymax, delaymin, delayavg, ipi_nr, delay;
7f563886	200
	201	/*
	202	* Skip the ipi caller, not in irq context.
	203	*/
	204	if (!in_irq())
	205	return;
f0a36bb1	206
7f563886	207	delaymax = &per_cpu(int_delaymax, smp_processor_id());
68f25f81	208	delaymin = &per_cpu(int_delaymin, smp_processor_id());
	209	delayavg = &per_cpu(int_delayavg, smp_processor_id());
	210	ipi_nr = &per_cpu(int_ipi_nr, smp_processor_id());
	211
	212	rdtsc_barrier();
7f563886	213	time1 = get_cycles();
68f25f81	214	rdtsc_barrier();
68f25f81	215
f0a36bb1	216	fair_read_lock(&frwlock);
68f25f81	217
68f25f81	218	rdtsc_barrier();
7f563886	219	time2 = get_cycles();
68f25f81	220	rdtsc_barrier();
	221	delay = time2 - time1;
	222	delaymax = max(delaymax, delay);
	223	delaymin = min(delaymin, delay);
	224	*delayavg += delay;
	225	(*ipi_nr)++;
f0a36bb1	226	prev = var[0];
	227	for (i = 1; i < NR_VARS; i++) {
	228	cur = var[i];
	229	if (cur != prev)
	230	printk(KERN_ALERT
	231	"Unequal cur %d/prev %d at i %d in interrupt\n",
	232	cur, prev, i);
	233	}
	234	fair_read_unlock(&frwlock);
	235	}
	236
1c21e42c	237	DEFINE_PER_CPU(unsigned long, trylock_int_iter);
	238	DEFINE_PER_CPU(unsigned long, trylock_int_success);
	239
	240	static void trylock_interrupt_reader_ipi(void *data)
	241	{
	242	int i;
	243	int prev, cur;
	244
	245	/*
	246	* Skip the ipi caller, not in irq context.
	247	*/
	248	if (!in_irq())
	249	return;
	250
	251	per_cpu(trylock_int_iter, smp_processor_id())++;
	252	while (!fair_read_trylock(&frwlock))
	253	per_cpu(trylock_int_iter, smp_processor_id())++;
	254	per_cpu(trylock_int_success, smp_processor_id())++;
	255	prev = var[0];
	256	for (i = 1; i < NR_VARS; i++) {
	257	cur = var[i];
	258	if (cur != prev)
	259	printk(KERN_ALERT
	260	"Unequal cur %d/prev %d at i %d in interrupt\n",
	261	cur, prev, i);
	262	}
	263	fair_read_unlock(&frwlock);
	264	}
	265
	266
f0a36bb1	267	static int interrupt_reader_thread(void *data)
	268	{
	269	unsigned long iter = 0;
7f563886	270	int i;
7f563886	271
68f25f81	272	for_each_online_cpu(i) {
	273	per_cpu(int_delaymax, i) = 0;
	274	per_cpu(int_delaymin, i) = ULLONG_MAX;
	275	per_cpu(int_delayavg, i) = 0;
	276	per_cpu(int_ipi_nr, i) = 0;
	277	}
f0a36bb1	278	do {
	279	iter++;
	280	on_each_cpu(interrupt_reader_ipi, NULL, 0);
4fd25765	281	if (INTERRUPT_READER_DELAY)
4fd25765	282	msleep(INTERRUPT_READER_DELAY);
f0a36bb1	283	} while (!kthread_should_stop());
	284	printk("interrupt_reader_thread/%lu iterations : %lu\n",
	285	(unsigned long)data, iter);
7f563886	286	for_each_online_cpu(i) {
4fd25765	287	if (!per_cpu(int_ipi_nr, i))
4fd25765	288	continue;
68f25f81	289	per_cpu(int_delayavg, i) /= per_cpu(int_ipi_nr, i);
7f563886	290	printk("interrupt readers on CPU %i, "
68f25f81	291	"lock delay [min,avg,max] %llu,%llu,%llu cycles\n",
	292	i,
	293	calibrate_cycles(per_cpu(int_delaymin, i)),
	294	calibrate_cycles(per_cpu(int_delayavg, i)),
	295	calibrate_cycles(per_cpu(int_delaymax, i)));
7f563886	296	}
f0a36bb1	297	return 0;
	298	}
	299
1c21e42c	300	static int trylock_interrupt_reader_thread(void *data)
	301	{
	302	unsigned long iter = 0;
	303	int i;
	304
	305	do {
	306	iter++;
	307	on_each_cpu(trylock_interrupt_reader_ipi, NULL, 0);
4fd25765	308	if (INTERRUPT_READER_DELAY)
4fd25765	309	msleep(INTERRUPT_READER_DELAY);
1c21e42c	310	} while (!kthread_should_stop());
	311	printk("trylock_interrupt_reader_thread/%lu iterations : %lu\n",
	312	(unsigned long)data, iter);
	313	for_each_online_cpu(i) {
	314	printk("trylock interrupt readers on CPU %i, "
	315	"iterations %lu, "
	316	"successful iterations : %lu\n",
	317	i, per_cpu(trylock_int_iter, i),
	318	per_cpu(trylock_int_success, i));
68f25f81	319	per_cpu(trylock_int_iter, i) = 0;
68f25f81	320	per_cpu(trylock_int_success, i) = 0;
1c21e42c	321	}
	322	return 0;
	323	}
	324
f0a36bb1	325	static int writer_thread(void *data)
	326	{
	327	int i;
	328	int new;
	329	unsigned long iter = 0;
68f25f81	330	cycles_t time1, time2, delay, delaymax = 0, delaymin = ULLONG_MAX,
68f25f81	331	delayavg = 0;
f0a36bb1	332
	333	printk("writer_thread/%lu runnning\n", (unsigned long)data);
	334	do {
	335	iter++;
7f563886	336	preempt_disable(); /* for get_cycles accuracy */
68f25f81	337	rdtsc_barrier();
7f563886	338	time1 = get_cycles();
68f25f81	339	rdtsc_barrier();
68f25f81	340
4fd25765	341	#if (TEST_INTERRUPTS)
f0a36bb1	342	fair_write_lock_irq(&frwlock);
4fd25765	343	#else
	344	fair_write_lock(&frwlock);
	345	#endif
68f25f81	346
68f25f81	347	rdtsc_barrier();
7f563886	348	time2 = get_cycles();
68f25f81	349	rdtsc_barrier();
	350	delay = time2 - time1;
	351	delaymax = max(delaymax, delay);
	352	delaymin = min(delaymin, delay);
	353	delayavg += delay;
f0a36bb1	354	new = (int)get_cycles();
	355	for (i = 0; i < NR_VARS; i++) {
	356	var[i] = new;
	357	}
4fd25765	358	#if (TEST_INTERRUPTS)
f0a36bb1	359	fair_write_unlock_irq(&frwlock);
4fd25765	360	#else
	361	fair_write_unlock(&frwlock);
	362	#endif
7f563886	363	preempt_enable(); /* for get_cycles accuracy */
89889f86	364	if (WRITER_DELAY > 0)
4d1751f9	365	udelay(WRITER_DELAY);
f0a36bb1	366	} while (!kthread_should_stop());
68f25f81	367	delayavg /= iter;
7f563886	368	printk("writer_thread/%lu iterations : %lu, "
68f25f81	369	"lock delay [min,avg,max] %llu,%llu,%llu cycles\n",
	370	(unsigned long)data, iter,
	371	calibrate_cycles(delaymin),
	372	calibrate_cycles(delayavg),
	373	calibrate_cycles(delaymax));
f0a36bb1	374	return 0;
	375	}
	376
1c21e42c	377	static int trylock_writer_thread(void *data)
	378	{
	379	int i;
	380	int new;
4fd25765	381	unsigned long iter = 0, success = 0, fail = 0;
1c21e42c	382
	383	printk("trylock_writer_thread/%lu runnning\n", (unsigned long)data);
	384	do {
4fd25765	385	iter++;
	386	#if (TEST_INTERRUPTS)
	387	if (fair_write_trylock_irq_else_subscribe(&frwlock))
	388	#else
	389	if (fair_write_trylock_else_subscribe(&frwlock))
	390	#endif
	391	goto locked;
	392	#if (TRYLOCK_WRITERS_FAIL_ITER == -1)
	393	for (;;) {
1c21e42c	394	iter++;
4fd25765	395	#if (TEST_INTERRUPTS)
	396	if (fair_write_trylock_irq_subscribed(&frwlock))
	397	#else
	398	if (fair_write_trylock_subscribed(&frwlock))
	399	#endif
	400	goto locked;
1c21e42c	401	}
4fd25765	402	#else
	403	for (i = 0; i < TRYLOCK_WRITERS_FAIL_ITER; i++) {
	404	iter++;
	405	#if (TEST_INTERRUPTS)
	406	if (fair_write_trylock_irq_subscribed(&frwlock))
	407	#else
	408	if (fair_write_trylock_subscribed(&frwlock))
	409	#endif
	410	goto locked;
	411	}
	412	#endif
	413	fail++;
	414	fair_write_unsubscribe(&frwlock);
	415	goto loop;
	416	locked:
1c21e42c	417	success++;
1c21e42c	418	new = (int)get_cycles();
	419	for (i = 0; i < NR_VARS; i++) {
	420	var[i] = new;
	421	}
4fd25765	422	#if (TEST_INTERRUPTS)
1c21e42c	423	fair_write_unlock_irq(&frwlock);
4fd25765	424	#else
	425	fair_write_unlock(&frwlock);
	426	#endif
	427	loop:
	428	if (TRYLOCK_WRITER_DELAY > 0)
	429	udelay(TRYLOCK_WRITER_DELAY);
1c21e42c	430	} while (!kthread_should_stop());
4fd25765	431	printk("trylock_writer_thread/%lu iterations : "
	432	"[try,success,fail after %d try], "
	433	"%lu,%lu,%lu\n",
	434	(unsigned long)data, TRYLOCK_WRITERS_FAIL_ITER,
	435	iter, success, fail);
1c21e42c	436	return 0;
	437	}
	438
f0a36bb1	439	static void fair_rwlock_create(void)
	440	{
	441	unsigned long i;
	442
	443	for (i = 0; i < NR_READERS; i++) {
	444	printk("starting reader thread %lu\n", i);
	445	reader_threads[i] = kthread_run(reader_thread, (void *)i,
	446	"frwlock_reader");
	447	BUG_ON(!reader_threads[i]);
	448	}
	449
1c21e42c	450	for (i = 0; i < NR_TRYLOCK_READERS; i++) {
	451	printk("starting trylock reader thread %lu\n", i);
	452	trylock_reader_threads[i] = kthread_run(trylock_reader_thread,
	453	(void *)i, "frwlock_trylock_reader");
	454	BUG_ON(!trylock_reader_threads[i]);
	455	}
4fd25765	456	for (i = 0; i < NR_INTERRUPT_READERS; i++) {
	457	printk("starting interrupt reader %lu\n", i);
	458	interrupt_reader[i] = kthread_run(interrupt_reader_thread,
	459	(void *)i,
	460	"frwlock_interrupt_reader");
	461	}
	462	for (i = 0; i < NR_TRYLOCK_INTERRUPT_READERS; i++) {
	463	printk("starting trylock interrupt reader %lu\n", i);
	464	trylock_interrupt_reader[i] =
	465	kthread_run(trylock_interrupt_reader_thread,
	466	(void *)i, "frwlock_trylock_interrupt_reader");
	467	}
f0a36bb1	468	for (i = 0; i < NR_WRITERS; i++) {
	469	printk("starting writer thread %lu\n", i);
	470	writer_threads[i] = kthread_run(writer_thread, (void *)i,
	471	"frwlock_writer");
	472	BUG_ON(!writer_threads[i]);
	473	}
1c21e42c	474	for (i = 0; i < NR_TRYLOCK_WRITERS; i++) {
	475	printk("starting trylock writer thread %lu\n", i);
	476	trylock_writer_threads[i] = kthread_run(trylock_writer_thread,
	477	(void *)i, "frwlock_trylock_writer");
	478	BUG_ON(!trylock_writer_threads[i]);
	479	}
f0a36bb1	480	}
	481
	482	static void fair_rwlock_stop(void)
	483	{
	484	unsigned long i;
	485
1c21e42c	486	for (i = 0; i < NR_WRITERS; i++)
7f563886	487	kthread_stop(writer_threads[i]);
1c21e42c	488	for (i = 0; i < NR_TRYLOCK_WRITERS; i++)
	489	kthread_stop(trylock_writer_threads[i]);
	490	for (i = 0; i < NR_READERS; i++)
f0a36bb1	491	kthread_stop(reader_threads[i]);
1c21e42c	492	for (i = 0; i < NR_TRYLOCK_READERS; i++)
1c21e42c	493	kthread_stop(trylock_reader_threads[i]);
4fd25765	494	for (i = 0; i < NR_INTERRUPT_READERS; i++)
	495	kthread_stop(interrupt_reader[i]);
	496	for (i = 0; i < NR_TRYLOCK_INTERRUPT_READERS; i++)
	497	kthread_stop(trylock_interrupt_reader[i]);
f0a36bb1	498	}
	499
	500
	501	static void perform_test(const char name, void (callback)(void))
	502	{
	503	printk("%s\n", name);
	504	callback();
	505	}
	506
	507	static int my_open(struct inode inode, struct file file)
	508	{
68f25f81	509	unsigned long i;
	510	cycles_t time1, time2, delay;
	511
	512	printk(" get_cycles calibration \n");
	513	cycles_calibration_min = ULLONG_MAX;
	514	cycles_calibration_avg = 0;
	515	cycles_calibration_max = 0;
	516
	517	local_irq_disable();
	518	for (i = 0; i < 10; i++) {
	519	rdtsc_barrier();
	520	time1 = get_cycles();
	521	rdtsc_barrier();
	522	rdtsc_barrier();
	523	time2 = get_cycles();
	524	rdtsc_barrier();
	525	delay = time2 - time1;
	526	cycles_calibration_min = min(cycles_calibration_min, delay);
	527	cycles_calibration_avg += delay;
	528	cycles_calibration_max = max(cycles_calibration_max, delay);
	529	}
	530	cycles_calibration_avg /= 10;
	531	local_irq_enable();
	532
	533	printk("get_cycles takes [min,avg,max] %llu,%llu,%llu cycles, "
	534	"results calibrated on avg\n",
	535	cycles_calibration_min,
	536	cycles_calibration_avg,
	537	cycles_calibration_max);
	538
	539	printk(" Single writer test, no contention \n");
	540	writer_threads[0] = kthread_run(writer_thread, (void *)0,
	541	"frwlock_writer");
	542	BUG_ON(!writer_threads[0]);
	543	ssleep(SINGLE_WRITER_TEST_DURATION);
	544	kthread_stop(writer_threads[0]);
	545
4fd25765	546	printk(" Single trylock writer test, no contention \n");
	547	trylock_writer_threads[0] = kthread_run(trylock_writer_thread,
	548	(void *)0,
	549	"trylock_frwlock_writer");
	550	BUG_ON(!trylock_writer_threads[0]);
	551	ssleep(SINGLE_WRITER_TEST_DURATION);
	552	kthread_stop(trylock_writer_threads[0]);
	553
68f25f81	554	printk(" Single reader test, no contention \n");
	555	reader_threads[0] = kthread_run(reader_thread, (void *)0,
	556	"frwlock_reader");
	557	BUG_ON(!reader_threads[0]);
	558	ssleep(SINGLE_READER_TEST_DURATION);
	559	kthread_stop(reader_threads[0]);
	560
	561	printk(" Multiple readers test, no contention \n");
	562	for (i = 0; i < NR_READERS; i++) {
	563	printk("starting reader thread %lu\n", i);
	564	reader_threads[i] = kthread_run(reader_thread, (void *)i,
	565	"frwlock_reader");
	566	BUG_ON(!reader_threads[i]);
	567	}
	568	ssleep(SINGLE_READER_TEST_DURATION);
	569	for (i = 0; i < NR_READERS; i++)
	570	kthread_stop(reader_threads[i]);
	571
	572	printk(" High contention test \n");
f0a36bb1	573	perform_test("fair-rwlock-create", fair_rwlock_create);
f36c4112	574	ssleep(TEST_DURATION);
f0a36bb1	575	perform_test("fair-rwlock-stop", fair_rwlock_stop);
	576
	577	return -EPERM;
	578	}
	579
	580
	581	static struct file_operations my_operations = {
	582	.open = my_open,
	583	};
	584
	585	int init_module(void)
	586	{
	587	pentry = create_proc_entry("testfrwlock", 0444, NULL);
	588	if (pentry)
	589	pentry->proc_fops = &my_operations;
	590
	591	printk("NR_CPUS : %d\n", NR_CPUS);
	592	printk("THREAD_ROFFSET : %lX\n", THREAD_ROFFSET);
	593	printk("THREAD_RMASK : %lX\n", THREAD_RMASK);
f0a36bb1	594	printk("SOFTIRQ_ROFFSET : %lX\n", SOFTIRQ_ROFFSET);
f0a36bb1	595	printk("SOFTIRQ_RMASK : %lX\n", SOFTIRQ_RMASK);
f0a36bb1	596	printk("HARDIRQ_ROFFSET : %lX\n", HARDIRQ_ROFFSET);
f0a36bb1	597	printk("HARDIRQ_RMASK : %lX\n", HARDIRQ_RMASK);
7f563886	598	printk("SUBSCRIBERS_WOFFSET : %lX\n", SUBSCRIBERS_WOFFSET);
	599	printk("SUBSCRIBERS_WMASK : %lX\n", SUBSCRIBERS_WMASK);
	600	printk("WRITER_MUTEX : %lX\n", WRITER_MUTEX);
	601	printk("SOFTIRQ_WMASK : %lX\n", SOFTIRQ_WMASK);
f0a36bb1	602	printk("HARDIRQ_WMASK : %lX\n", HARDIRQ_WMASK);
	603
	604	return 0;
	605	}
	606
	607	void cleanup_module(void)
	608	{
	609	remove_proc_entry("testfrwlock", NULL);
	610	}
	611
	612	MODULE_LICENSE("GPL");
	613	MODULE_AUTHOR("Mathieu Desnoyers");
	614	MODULE_DESCRIPTION("Fair rwlock test");