#include <sys/time.h>
#include <sys/mman.h>

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>
#include <string.h>
#include <inttypes.h>
#include <assert.h>
#include <limits.h>
#include <fcntl.h>
#include <errno.h>
/*
#include "litmus.h"
#include "common.h"
*/
/* CPU time consumed so far in seconds */
double cputime(void)
{
	struct timespec ts;
	int err;
	err = clock_gettime(CLOCK_THREAD_CPUTIME_ID, &ts);
	if (err != 0)
		perror("clock_gettime");
	return (ts.tv_sec + 1E-9 * ts.tv_nsec);
}

/* wall-clock time in seconds */
double wctime(void)
{
	struct timeval tv;
	gettimeofday(&tv, NULL);
	return (tv.tv_sec + 1E-6 * tv.tv_usec);
}

void bail_out(const char* msg)
{
	perror(msg);
	exit(-1 * errno);
}

#include "extra.h"

#define PAGE_SIZE (4096)
#define CACHELINE_SIZE 64
#define INTS_IN_CACHELINE (CACHELINE_SIZE/sizeof(int))
#define CACHELINES_IN_1KB (1024 / sizeof(cacheline_t))
#define INTS_IN_1KB (1024 / sizeof(int))

typedef struct cacheline
{
	int line[INTS_IN_CACHELINE];
} __attribute__((aligned(CACHELINE_SIZE))) cacheline_t;

static volatile cacheline_t* arena = NULL;

#define UNCACHE_DEV "/dev/litmus/uncache"
#define FAKE_DEV "/dev/litmus/fakedev0"

static cacheline_t* alloc_arena(size_t size, int use_huge_pages, int use_uncache_pages)
{
	int flags = MAP_PRIVATE | MAP_POPULATE;
	cacheline_t* arena = NULL;
	int fd;

	if(use_huge_pages)
		flags |= MAP_HUGETLB;

	if(use_uncache_pages == 1) {
		fd = open(UNCACHE_DEV, O_RDWR|O_SYNC);
		if (fd == -1)
			bail_out("Failed to open uncache device. Are you running the LITMUS^RT kernel?");
	} else if (use_uncache_pages == 2) {
		fd = open(FAKE_DEV, O_RDWR|O_SYNC);
		if (fd == -1)
			bail_out("Failed to open fake device. Are you running the LITMUS^RT kernel?");
	} else {
		fd = -1;
		flags |= MAP_ANONYMOUS;
	}

	arena = (cacheline_t*)mmap(0, size, PROT_READ | PROT_WRITE, flags, fd, 0);
	
	if(use_uncache_pages)
		close(fd);

	assert(arena);

	return arena;
}

static void dealloc_arena(cacheline_t* arena, size_t size)
{
		int ret = munmap((void*)arena, size);
        if(ret != 0)
                bail_out("munmap() error");
}

static int randrange(int min, int max)
{
    // Range is [min, max)
    assert(max - min - 1 <= RAND_MAX);
    return rand() % (max - min) + min;
    //return (rand() % (max - min + 1)) + min;
    /* generate a random number on the range [min, max) w/o skew */
    /*int limit = max - min;
    int devisor = RAND_MAX/limit;
    int retval;

    do {
            retval = rand() / devisor;
    } while(retval == limit);
    retval += min;

    return retval;*/
}

static void init_arena(volatile cacheline_t* arena, size_t size)
{
    int i;
    size_t num_arena_elem = size / sizeof(cacheline_t);

    /* Generate a cycle among the cache lines using Sattolo's algorithm.
       Every int in the cache line points to the same cache line.
       Note: Sequential walk doesn't care about these values. */
    for (i = 0; i < num_arena_elem; i++) {
            int j;
            for(j = 0; j < INTS_IN_CACHELINE; j++)
                    arena[i].line[j] = i;
            arena[i].line[1] = 0;
    }
    /*while(1 < i--) {
            int j = randrange(0, i);
            cacheline_t temp = arena[j];
            arena[j] = arena[i];
            arena[i] = temp;
    }*/
    for (int j = 0; j < num_arena_elem-1; j++) {
        int k = randrange(j+1, num_arena_elem);
        cacheline_t temp = arena[j];
        arena[j] = arena[k];
        arena[k] = temp;
    }
}

/* Random walk around the arena in cacheline-sized chunks.
   Cacheline-sized chucks ensures the same utilization of each
   hit line as sequential read. (Otherwise, our utilization
   would only be 1/INTS_IN_CACHELINE.) */
static int random_walk(volatile cacheline_t *mem, int wss, int write_cycle)
{
	/* a random cycle among the cache lines was set up by init_arena(). */
	int sum, i, next;

	// Always do the same number of hops
	int numlines = 33554432 / CACHELINE_SIZE;//wss * CACHELINES_IN_1KB;

	sum = 0;

	/* contents of arena is structured s.t. offsets are all
	   w.r.t. to start of arena, so compute the initial offset */
	next = mem - arena;

	if (write_cycle == 0) {
		for (i = 0; i < numlines; i++) {
			next = arena[next].line[0];
			arena[next].line[1] = 1; // Record that we touched this line
			sum += next;
			for (int j = 2; j < INTS_IN_CACHELINE; j++)
				arena[next].line[j]++;
		}
	} else {
		int w, which_line;
		for (i = 0, w = 0; i < numlines; i++) {
			which_line = next;
			next = arena[next].line[0];
			if((w % write_cycle) != (write_cycle - 1)) { // This is equivalent to 1 % 1 != 1 - 1 which is always false
				sum += next;
			}
			else {
				// I /think/ that this just writes back to the address it read from
				arena[which_line].line[0] = next;
			}
		}
	}
	return sum;
}

volatile static cacheline_t* random_start(int wss)
{
	return arena + randrange(0, ((wss * 1024)/sizeof(cacheline_t)));
}
/*
static int sequential_walk(cacheline_t *_mem, int wss, int write_cycle)
{
	int sum = 0, i;
	int* mem = (int*)_mem; // treat as raw buffer of ints
	int num_ints = wss * INTS_IN_1KB;

	if (write_cycle > 0) {
		for (i = 0; i < num_ints; i++) {
			if (i % write_cycle == (write_cycle - 1))
				mem[i]++;
			else
				sum += mem[i];
		}
	} else {
		// sequential access, pure read
		for (i = 0; i < num_ints; i++)
			sum += mem[i];
	}
	return sum;
}

static cacheline_t* sequential_start(int wss)
{
	static int pos = 0;

	int num_cachelines = wss * CACHELINES_IN_1KB;

	cacheline_t *mem;

	 * Don't allow re-use between allocations.
	 * At most half of the arena may be used
	 * at any one time.
	 *
	if (num_cachelines * 2 > ((wss * 1024)/sizeof(cacheline_t)))
		;//bail_out("static memory arena too small");

	if (pos + num_cachelines > ((wss * 1024)/sizeof(cacheline_t))) {
		// wrap to beginning
		mem = arena;
		pos = num_cachelines;
	} else {
		mem = arena + pos;
		pos += num_cachelines;
	}

	return mem;
}
*/
static volatile int dont_optimize_me = 0;

#define RANDOM_WALK 1
static int loop_once(int wss, int write)
{
	volatile cacheline_t *mem;
	int temp;
	
#ifdef RANDOM_WALK
	mem = random_start(wss);
//	printf("Using start offset %ld. Data here is %d. data size: %ld\n", mem-arena, mem->line[0], sizeof(mem->line[0]));
	temp = random_walk(mem, wss, write);
#else   
	mem = sequential_start(wss);
	temp = sequential_walk(mem, wss, write);
#endif
	dont_optimize_me = temp;
//	printf("%d", dont_optimize_me);
	return dont_optimize_me;
}

int main(int argc, char** argv) {
	SET_UP
	int write;
	long wss;
	double duration;
	double program_end;
	// Reads in benchmark params from stdin
	// <long: wss in bytes> <float: duration in seconds> <bool: if we should also write>
	if (scanf("%ld %lf %d", &wss, &duration, &write) != 3) {
		fprintf(stderr, "Bad input, please enter 3 parameters: <WSS (Int)> <Duration (Double)> <Write (Bool)>.\n");
		exit(1);
	}
	printf("random_walk: Using parameters: %ld, %lf, %d\n", wss, duration, write);
	wss /= 1024;
	program_end = duration + wctime();
	// Initialize memory
	size_t arena_sz = wss*1024;
	arena = alloc_arena(arena_sz*2, 0, 0);
	init_arena(arena, arena_sz);
	loop_once(wss, write);
	// This loop contains the original content of job(int wss, int write, double exec_time, double program_end)
	while (1) {
		double emergency_exit = program_end + 1;
		
		if (wctime() > program_end) {
			break;
		} else {
			double last_loop = 0, loop_start;
			int tmp = 0;

			double start = cputime();
			double now = cputime();

			//while (now + last_loop < start) {// + exec_time) {
				loop_start = now;
				START_LOOP
				tmp += loop_once(wss, write);
				STOP_LOOP
				now = cputime();
				last_loop = now - loop_start;
				if (emergency_exit && wctime() > emergency_exit) {
					/* Oops --- this should only be possible if the execution time tracking
					 * is broken in the LITMUS^RT kernel. */
					fprintf(stderr, "!!! rtspin/%d emergency exit!\n", getpid());
					fprintf(stderr, "Something is seriously wrong! Do not ignore this.\n");
					break;
				}
				long sum = 0;
				// Verify that we actually traversed the whole wss
				for (volatile cacheline_t* loc = arena; loc < arena + (wss*1024)/sizeof(cacheline_t); loc++) {
					sum += loc->line[1];
				}
				if (sum != wss * CACHELINES_IN_1KB) {
					fprintf(stderr, "We hopped the wrong number of times! Hops: %ld, should have been: %ld\n", sum, wss * CACHELINES_IN_1KB);
				}
			//}
			
			//sleep_next_period();
			continue;
		}
	}
	WRITE_TO_FILE
	printf("random_walk: done walking %ldKiB.\n", wss);
	return 0;
}
/*
#define OPTSTR "p:wl:m:i:b:k:u:r:"
int main(int argc, char** argv)
{
	int ret;
	lt_t wcet, period, budget;
	double wcet_ms, period_ms, budget_ms;
	unsigned int priority = LITMUS_NO_PRIORITY;
	int migrate = 0;
	int cluster = 0;
	int opt;
	int wait = 0;
	double duration = 0, start = 0;
	struct rt_task param;
	struct mc2_task mc2_param;
	struct reservation_config config;
	int res_type = PERIODIC_POLLING;
	size_t arena_sz;
	int wss;
	int uncacheable = 0;
	int read_access = 0, write;
	int verbose = 0;
	unsigned int job_no;
	struct control_page* cp;

	* default for reservation *
	config.id = 0;
	config.cpu = -1;
	
	mc2_param.crit = CRIT_LEVEL_C;
	
	budget_ms = 1000;
	wss = 32;
	
	while ((opt = getopt(argc, argv, OPTSTR)) != -1) {
		switch (opt) {
		case 'w':
			wait = 1;
			break;
		case 'p':
			cluster = atoi(optarg);
			migrate = 1;
			config.cpu = cluster;
			break;
		case 'k':
			wss = atoi(optarg);
			break;
		case 'm':
			mc2_param.crit = atoi(optarg);
			if ((mc2_param.crit >= CRIT_LEVEL_A) && (mc2_param.crit <= CRIT_LEVEL_C)) {
				res_type = PERIODIC_POLLING;
			}
			else
				usage("Invalid criticality level.");
			break;
		case 'b':
			budget_ms = atof(optarg);
			break;
		case 'r':
			read_access = atoi(optarg);
			break;
		case 'q':
			priority = want_non_negative_int(optarg, "-q");
			if (!litmus_is_valid_fixed_prio(priority))
				usage("Invalid priority");
			config.priority = atoi(optarg);
			break;
		case 'u':
			uncacheable = atoi(optarg);
			break;
		case 'v':
			verbose = 1;
			break;
		case ':':
			usage("Argument missing.");
			break;
		case '?':
		default:
			usage("Bad argument.");
			break;
		}
	}
	srand(getpid());
	if (read_access == 1)
		write = 0;
	else
		write = 1;
	 *
	 * We need three parameters
	 *
	if (argc - optind < 3)
		usage("Arguments missing.");

	wcet_ms   = atof(argv[optind + 0]);
	period_ms = atof(argv[optind + 1]);

	wcet   = ms2ns(wcet_ms);
	period = ms2ns(period_ms);
	budget = ms2ns(budget_ms);
	if (wcet <= 0)
		usage("The worst-case execution time must be a "
				"positive number.");
	if (period <= 0)
		usage("The period must be a positive number.");
	if (wcet > period) {
		usage("The worst-case execution time must not "
				"exceed the period.");
	}

	duration  = atof(argv[optind + 2]);
	
	if (migrate) {
		ret = be_migrate_to_domain(cluster);
		if (ret < 0)
			bail_out("could not migrate to target partition or cluster.");
	}

	* reservation config *
	config.id = gettid();
	config.priority = priority;
	config.polling_params.budget = budget;
	config.polling_params.period = period;
	config.polling_params.offset = 0;
	config.polling_params.relative_deadline = 0;
	
	if (config.polling_params.budget > config.polling_params.period) {
		usage("The budget must not exceed the period.");
	}
	
	* create a reservation *
	ret = reservation_create(res_type, &config);
	if (ret < 0) {
		bail_out("failed to create reservation.");
	}
	
	init_rt_task_param(&param);
	param.exec_cost = wcet;
	param.period = period;
	param.phase = 0;
	param.relative_deadline = 0;
	param.priority = priority == LITMUS_NO_PRIORITY ? LITMUS_LOWEST_PRIORITY : priority;
	param.cls = RT_CLASS_HARD;
	param.budget_policy = NO_ENFORCEMENT;
	param.release_policy = TASK_PERIODIC;
	if (migrate) {
		param.cpu = gettid();
	}
	ret = set_rt_task_param(gettid(), &param);
	if (ret < 0)
		bail_out("could not setup rt task params");
	
	mc2_param.res_id = gettid();
	ret = set_mc2_task_param(gettid(), &mc2_param);
	if (ret < 0)
		bail_out("could not setup mc2 task params");
	
	arena_sz = wss*1024;
	arena = alloc_arena(arena_sz*2, 0, uncacheable);
	init_arena(arena, arena_sz);
	loop_once(wss, write);
	
	ret = init_litmus();
	if (ret != 0)
		bail_out("init_litmus() failed\n");
	
	mlockall(MCL_CURRENT | MCL_FUTURE);
	
	if (mc2_param.crit == CRIT_LEVEL_C)
		set_page_color(-1);
	else
		set_page_color(config.cpu);
		
	start = wctime();
	ret = task_mode(LITMUS_RT_TASK);
	if (ret != 0)
		bail_out("could not become RT task");
	
	if (wait) {
		ret = wait_for_ts_release();
		if (ret != 0)
			bail_out("wait_for_ts_release()");
		start = wctime();
	}
	cp = get_ctrl_page();

	while (job(wss, write, wcet_ms * 0.001, start + duration)) {
		if (verbose) {
			get_job_no(&job_no);
			fprintf(stderr, "rtspin/%d:%u @ %.4fms\n", gettid(),
				job_no, (wctime() - start) * 1000);
			if (cp) {
				double deadline, current, release;
				lt_t now = litmus_clock();
				deadline = ns2s((double) cp->deadline);
				current  = ns2s((double) now);
				release  = ns2s((double) cp->release);
				fprintf(stderr,
					"\trelease:  %" PRIu64 "ns (=%.2fs)\n",
					(uint64_t) cp->release, release);
				fprintf(stderr,
					"\tdeadline: %" PRIu64 "ns (=%.2fs)\n",
					(uint64_t) cp->deadline, deadline);
				fprintf(stderr,
					"\tcur time: %" PRIu64 "ns (=%.2fs)\n",
					(uint64_t) now, current);
				fprintf(stderr,
					"\ttime until deadline: %.2fms\n",
					(deadline - current) * 1000);
			}
		}
	};

	ret = task_mode(BACKGROUND_TASK);
	if (ret != 0)
		bail_out("could not become regular task (huh?)");

	reservation_destroy(gettid(), config.cpu);
	dealloc_arena(arena, arena_sz*2);
	printf("%s finished.\n", argv[0]);
	return 0;
}
*/