#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/ioctl.h>
#include <unistd.h>
#include <inttypes.h>

#include "asm/cacheparams.h"

#include <litmus/rt_param.h>

#include "perfcounters.h"

#include "color.h"
#include "litmus.h"

#define CPU		1
#define NR_LOOPS	10000

static int pages_per_datum;
/* Number of pages in a "data" element, each with same color. */

static int nr_data;
/* Number of "data" elements. */


struct page;
#define NR_PAGE_INTS	((PAGE_SIZE - CACHE_LINE_SIZE) / sizeof(uint32_t))
struct page {
	struct page *ptr;
	struct page *_unused[CACHE_LINE_SIZE / sizeof(struct page*) - 1];
	uint32_t ints[NR_PAGE_INTS];
};

struct datum {
	struct page *pages;
};

/*
 * Get a random number in [0, max). Not really a good way to do this.
 */
static int randrange(const int max)
{
	return (rand() / (RAND_MAX / max + 1));
}

static void setup_page_ints(struct page *page)
{
	int i;
	
	for (i = 0; i < NR_PAGE_INTS; i++) {
		page->ints[i] = randrange(RAND_MAX);
	}
}

/*
 * Sattolo's algorithm makes a random cycle that includes all the elements
 * in the items array.
 */
static void sattolo(int *items, const int len)
{
	int i;
	/* first set up 0, 1, ..., n - 1 */
	for (i = 0; i < len; i++)
		items[i] = i;
	/* note: i is now n */
	while (1 < i--) {
		/* 0 <= j < i */
		int t, j = randrange(i);
		t = items[i];
		items[i] = items[j];
		items[j] = t;
	}
}

static uint32_t get_sum(struct page *page)
{
	uint32_t sum = 0;
	int i;

	for (i = 0; i < NR_PAGE_INTS; i += CACHE_LINE_SIZE / sizeof(uint32_t)) {
		sum += page->ints[i];
	} 
	return sum;
}

static uint32_t do_read(struct page* page)
{
	struct page *old;
	uint32_t sum = 0;

	do {
		old = page;
		page = page->ptr;
		sum += get_sum(old);
	} while (page);
	return sum;
}

#define MULT	699050667
#define SHIFT	24

static inline int64_t clocksource_cyc2ns(cycles_t cycles, uint32_t mult, uint32_t shift)
{                                                    
	return ((uint64_t) cycles * mult) >> shift;
}

#if 0
static void print_difference(const cycles_t start, const cycles_t end)
{
	cycles_t diff = end - start;

	printf("difference: %10llu = %10llu ns\n", diff, clocksource_cyc2ns(diff, MULT, SHIFT));
}
#endif

#define quit_on_err(err, msg) do { \
	if (err) { \
		fprintf(stderr, "error: " msg); \
		goto out; \
	} \
} while (0)

int main(int argc, char **argv)
{
	struct color_ctrl_page *color_ctrl;
	struct datum *data;
	int *read_order;
	int i, j, err = 0;
	cycles_t start, end;
	uint32_t sum = 0;
	int64_t nanoseconds;
	double avg_nanoseconds;

	quit_on_err(PAGE_SIZE != sizeof(struct page),
			"PAGE_SIZE != sizeof(struct page)\n");

	if (3 > argc) {
		fprintf(stderr, "%s: [pages-per-datum] [nr-data]\n", argv[0]);
		err = 1;
		goto out;
	}

	pages_per_datum = atoi(argv[1]);
	nr_data = atoi(argv[2]);

	quit_on_err(0 == nr_data || 0 == pages_per_datum, "zero argument\n");
	quit_on_err(16 < nr_data, "too many nr_data\n");

	read_order = malloc(pages_per_datum * sizeof(*read_order));
	data = malloc(nr_data * sizeof(*data));
	quit_on_err(!read_order || !data, "malloc\n");

	err = be_migrate_to(CPU);
	quit_on_err(err, "migrate to cpu\n");

	color_ctrl = get_color_ctrl();
	if (!color_ctrl) {
		fprintf(stderr, "could not map color ctrl\n");
		err = -1;
		goto out;
	}

	/* Always allocating this many pages of the same color. */
	color_ctrl->pages[0] = pages_per_datum;

	for (i = 0; i < nr_data; i++) {
		const unsigned nr_bytes = sizeof(data[i].pages[0]) * pages_per_datum;

		/* give each datum its own color (XXX no checks to ensure not >
		 * NR_COLORS!) */

		color_ctrl->colors[0] = i;
		fprintf(stderr, "color_mallocing %u bytes\n", nr_bytes);
		data[i].pages = color_malloc(nr_bytes);
		if (!data[i].pages) {
			fprintf(stderr, "could not color malloc\n");
			err = -1;
			goto out;
		}
	}

	sattolo(read_order, pages_per_datum);

	for (i = 0; i < nr_data; i++) {
		for (j = 0; j < pages_per_datum; j++) {
			if (0 != read_order[j]) {
				/* not the last element */
				data[i].pages[j].ptr = &(data[i].pages[read_order[j]]);
			} else {
				/* last element in pages inside of datum walk */
				if (nr_data - 1 == i) {
					/* last element globally */
					data[i].pages[j].ptr = NULL;
				} else {
					/* jump to next datum */
					data[i].pages[j].ptr = &(data[i + 1].pages[0]);
				}
			}

			setup_page_ints(&(data[i].pages[j]));
		}
	}

#if 0
	null_call(&start);
	null_call(&end);
	print_difference(start, end);

	null_call(&start);
	sum += do_read(data[0].pages);
	null_call(&end);
	print_difference(start, end);

	null_call(&start);
	sum += do_read(data[0].pages);
	null_call(&end);
	print_difference(start, end);

	null_call(&start);
	sum += do_read(data[0].pages);
	null_call(&end);
	print_difference(start, end);
#endif

	null_call(&start);
	for (i = 0; i < NR_LOOPS; i++) {
		sum += do_read(data[0].pages);
	}
	null_call(&end);
	nanoseconds = clocksource_cyc2ns(end - start, MULT, SHIFT);
	avg_nanoseconds = ((double)nanoseconds) / NR_LOOPS;
	printf("%3d, %10.3f, %10.3f\n", nr_data, avg_nanoseconds,
			avg_nanoseconds / (nr_data * pages_per_datum));

out:
	return err;
}