/*
 * Copyright (C) 2009 FAUmachine Team <info@faumachine.org>.
 * This program is free software. You can redistribute it and/or modify it
 * under the terms of the GNU General Public License, either version 2 of
 * the License, or (at your option) any later version. See COPYING.
 */

/*
 * Translate a FAUmachine log of read hard disk blocks to an xfig image.
 */

#include <stdio.h>
#include <getopt.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <assert.h>
#include <math.h>
#include "../lib/glue-main.h"

static long max_blocks = 0;

/* bitmap of blocks, 0=block not read, 1=block read */
static unsigned char *blocks;

/* list of block accesses sorted ascending by simulation time, 
 * storing only the last access for a given block */
static struct {
	long blockno;
	long long time;
} accesses[2000000];
static unsigned int naccesses = 0;

/* forward access counter */
static unsigned int forward_counter = 0;

/* number of contiguous accesses by length */
static unsigned int contiguous[1024];

static void
register_read_access(long blockno)
{
	static long last_block = -2;
	static unsigned int nc = 1;

	if ((blockno - last_block < 2) && (blockno - last_block > 0)) {
		nc++;
	} else {
		/* start of a non-contiguous access */
		assert(nc < (sizeof(contiguous) / sizeof(contiguous[0])));
		contiguous[nc]++;
		nc = 1;
	}
	last_block = blockno;
}

unsigned int
find_block(long blockno) 
{
	unsigned int i;

	for (i = 0; i < naccesses; i++) {
		if (accesses[i].blockno == blockno) {
			return i;
		}
	}

	assert(0);
	return naccesses;
}

int
get_block(long blockno)
{
	return (blocks[blockno >> 3] & (1 << (blockno & 0x7))) == 0 ? 0 : 1;
}

static void
set_block(long blockno, unsigned long long sim_time)
{
	if (max_blocks < blockno) {
		/* bad data */
		assert(0);
		return;
	}
	if (get_block(blockno)) {
		unsigned int a = find_block(blockno);
		assert(0 < naccesses);
		memmove(&accesses[a], &accesses[a + 1], 
			(naccesses - a - 1) * sizeof(accesses[0]));
		naccesses--;
	} else {
		blocks[blockno >> 3] |= (1 << (blockno & 0x7));
		forward_counter++;
	}

	assert(naccesses < (sizeof(accesses) / sizeof(accesses[0])));
	accesses[naccesses].time = sim_time;
	accesses[naccesses].blockno = blockno;
	naccesses++;
}

static long long
n_from_m(long long n, long long m)
{
	long long erg = 1;
	long long denom = 1;
	unsigned int i;
	
	/* m! / (m - n)! n! */

	for (i = n + 1; i <= m; i++) {
		erg *= i;
	}

	for (i = 1; i <= (m - n); i++) {
		denom *= i;
	}

	return erg / denom;
}


static long double
probability_found(unsigned int i, const long double perr)
{
	unsigned int l;
	long double ret = 0.0;

	for (l = 19; l <= i; l++) {
		long double p = 1.0;
		p *= powl(perr, l);
		p *= powl(1.0 - perr, i - l);
		p *= n_from_m(l, i);
		ret += p;
	}

	return ret;
}

static long double
calculate_access_probability(void)
{
	long double ret = 0.0;
	long long t;
	unsigned int i;

	/* skip accesses before 10 minutes, since no faults can be 
	 * injected there (making p=0 for these).
	 */
	for (i = 0; i < naccesses; i++) {
		if (60 * 10 * TIME_HZ <= accesses[i].time) {
			break;
		}
	}

	t = 60 * 10 * TIME_HZ;

	for (; i < naccesses; i++) {
		if (t < accesses[i].time) {
			const long remaining = naccesses - i - 1;
			const long double perr = (accesses[i].time - t)
					/ (long double)(50 * 60 * TIME_HZ);
			const long double block_ratio = 
					remaining / (long double)max_blocks;
			ret += perr * block_ratio;
			
			t = accesses[i].time;
		}
	}

	return ret;
}


static long double
calculate_probability(void)
{
	long double perr;
	long double erg = 0.0;
	unsigned int i;

	perr = calculate_access_probability();
	fprintf(stderr, "Probability for 1 faulty block being accessed=%Lf\n",
		perr);

	for (i = 20; i <= 30; i++) {
		erg += probability_found(i, perr);
	}
	erg /= 11.0;

	return erg;
}

static void
write_reverse_access_output(FILE *f)
{
	int i;
	unsigned long long ltime;

	if (naccesses == 0) {
		return;
	}

	ltime = accesses[naccesses - 1].time;

	for (i = naccesses - 1; i >= 0; i--) {
		/* must be strictly ordered! */
		assert(accesses[i].time <= ltime);

		if (accesses[i].time < ltime) {
			fprintf(f, "%lld %d\n", ltime, naccesses - i - 1);
			ltime = accesses[i].time;
		}
	}

	fprintf(f, "%lld %d\n", accesses[0].time, naccesses);
}

static void
write_adjacent(FILE *f)
{
	int i, j;
	unsigned long secs = 0;
	unsigned long rs = 0;
	double s = 0.0;

	/* skip 0 entries */
	i = sizeof(contiguous) / sizeof(contiguous[0]);
	while ((0 < i) && (contiguous[i] == 0)) {
		i--;
	}

	j = i;
	for (/* nothing */; 0 < i; i--) {
		fprintf(f, "%d %d\n", i, contiguous[i]);
		secs += i * contiguous[i];
		rs += contiguous[i];
	}

	for (i = j; 0 < i; i--) {
		s += pow(i * contiguous[i] - (secs / (double)rs), 2.0);
	}
	fprintf(stderr, "Total sectors read=%ld\n", secs);
	fprintf(stderr, "Average access length=%f\n", secs / (double) rs);
	fprintf(stderr, "Standard deviation=%f\n", sqrt(s / (rs - 1)));
}

static void
xfig_rec(
	FILE *f, 
	long recno, 
	int accessed, 
	int half_accessed, 
	int fully_accessed
)
{
	const int thickness = 1;
	const int pencolor = 0;
	const int width = 135;
	const int height = 90;
	const int unit = 45;
	int fillcolor = 0;
	const int row = recno / 50;
	const int col = recno % 50;
	const int x = 315 + col * (width + unit);
	const int y = 315 + row * (height + unit);

	fillcolor = 7; /* white */
	if (accessed) {
		fillcolor = 3; /* cyan */
	}

	if (half_accessed) {
		fillcolor = 14; /* green2 */
	}

	if (fully_accessed) {
		fillcolor = 0; /* black */
	}
	
	fprintf(f, "2 2 0 %d %d %d 50 0 20 0.0 0 0 0 0 0 5\n", 
		thickness, pencolor, fillcolor);
	fprintf(f, "\t%d %d %d %d %d %d %d %d %d %d\n",
		x, y, x + width, y, x + width, y + height,
		x, y + height, x, y);
}

static void
write_xfig_linear(FILE *f)
{
	long bpr;
	long cur_rec;
	int state;
	int state_full;
	int na;
	long i;
	/* possible layouts to be readable in paper:
	 * 30x30 rectangles, with one rectangle having 4:2 ratio
	 * or
	 * 40x30 rectangles, with one rectangle having 3:2 ratio
	 * 50x40 rectangles
	 */
	/* using 40x30 here, so a total of 1200 rectangles */
	assert(50 * 40 < max_blocks);

	bpr = (max_blocks + (50 * 40) - 1) / (50 * 40);
	cur_rec = 0;
	state = 0;
	state_full = 1;
	na = 0;

	for (i = 0; i < max_blocks; i++) {
		int b = get_block(i);

		state |= b;
		state_full &= b;
		if (b) {
			na++;
		}

		if (i % bpr == bpr - 1) {
			xfig_rec(f, cur_rec, state, 0.5 < na / (float)bpr, state_full);
			cur_rec++;
			state = 0;
			state_full = 1;
			na = 0;
		}
	}
}

static void
write_xfig_header(FILE *f)
{
	/* cf. /usr/share/doc/xfig/FORMAT3.2.gz */
	fprintf(f, "#FIG 3.2 Produced by hd_log2fix\n");
	fprintf(f, "Landscape\n"); 	/* | Portrait */
	fprintf(f, "Center\n"); 	/* | Flushleft */
	fprintf(f, "Metric\n"); 	/* | Inches */
	fprintf(f, "A4\n"); 		/* papersize size */
	fprintf(f, "100.0\n"); 		/* scale */
	fprintf(f, "Single\n"); 	/* | multiple page */
	fprintf(f, "-3\n"); 		/* background=transparent */
	fprintf(f, "1200 2\n");		/* resolution / coord system */
	/* (origin == top left) */
}

static long int
time_to_seconds(unsigned long long t)
{
	return t / TIME_HZ;
}

static void
write_xfig_time(FILE *f, unsigned long long sim_time)
{
	const int color = 0;
	const int font = 0; /* default latex font */
	const float size = 20.0;
	const float height = 1;
	const float width = 1;
	const int x = 315 + 25 * (135 + 45);
	const int y = 315 + 40 * (90 + 45) + 300;

	fprintf(f, "4 1 %d 50 0 %d %f 0.0 0 %f %f %d %d ", 
		color, font, size, height, width, x, y);
	/* text */
	fprintf(f, "Simulation Time: %lds", time_to_seconds(sim_time));
	/* end text */
	fprintf(f, "\\001\n");
}

static int
write_xfig(const char *logfile, unsigned long long sim_time)
{
	FILE *f;

	f = fopen(logfile, "w");
	if (f == NULL) {
		fprintf(stderr, "Cannot open <%s> for writing: %s\n",
			logfile, strerror(errno));
		return -1;
	}

	write_xfig_header(f);
	if (ferror(f)) {
		goto done;
	}

	write_xfig_linear(f);
	write_xfig_time(f, sim_time);
	if (ferror(f)) {
		goto done;
	}

done:	;
	return fclose(f);
}

#define MAGIC_READ_MATCH "DEBUG: arch_ide_disk ide_gen_disk_read_raw:"


static int
eval_line(char *line, unsigned long long simtime, FILE *fo)
{
	unsigned long long timestamp;
	static unsigned long long last_timestamp = 0;
	static unsigned int last_fwd_cnt = 0;
	long read_block;
	char *colon;

	if (strncmp(line, MAGIC_READ_MATCH, strlen(MAGIC_READ_MATCH)) != 0) {
		/* other entry: skip */
		return 0;
	}
	line += strlen(MAGIC_READ_MATCH);

	/* line contains: <simulation time>: reading from block <blockno> */
	colon = strchr(line, ':');
	if (colon == NULL) {
		/* bad data */
		return -1;
	}

	*colon = '\0';
	timestamp = atoll(line);

	if (simtime < timestamp) {
		return -1;
	}

	line = colon + 1;

	colon = strchr(line, 'k');
	if (colon == NULL) {
		/* bad data */
		return -1;
	}
	colon++; /* k */
	assert(*colon != '\0');
	colon++; /* <space> */
	assert(*colon != '\0');

	read_block = atol(colon);
	set_block(read_block, timestamp);
	register_read_access(read_block);
	
	if ((fo != NULL) 
	 && (last_timestamp < timestamp) 
	 && (last_fwd_cnt < forward_counter)) {

	 	last_fwd_cnt = forward_counter;
		last_timestamp = timestamp;

		fprintf(fo, "%lld %d\n", timestamp, forward_counter);
	}

	return 0;
}


static void
parse_log(FILE *f, unsigned long long simtime, const char *plot_output)
{
	char buffer[512];
	char *ret;
	int r = 0;
	FILE *po;

	if (plot_output != NULL) {
		po = fopen(plot_output, "w");
		if (po == NULL) {
			fprintf(stderr, "Cannot open <%s> for writing: %s\n",
				plot_output, strerror(errno));
			fprintf(stderr, "Disabling plot output\n");
			plot_output = NULL;
		}
	} else {
		po = NULL;
	}

	for (; r == 0;) {
		ret = fgets(buffer, sizeof(buffer) - 1, f);
		if (ret == NULL) {
			break;
		}
		r = eval_line(buffer, simtime, po);
	}

	if (plot_output != NULL) {
		assert(po != NULL);
		r = fclose(po);
		if (r < 0) {
			fprintf(stderr, "Error closing file <%s>: %s\n",
				plot_output, strerror(errno));
		}
	}
}

static void
usage(void)
{
	fprintf(stderr, "hd_log2fig - translate a FAUmachine log of read "
			"blocks to xfig image\n");
	fprintf(stderr, "Usage:\n");
	fprintf(stderr, "\thd_log2fig <options> <logfile>\n");
	fprintf(stderr, "Options:\n");
	fprintf(stderr, "\t-m, --max-blocks=<mb>\t\t"
			"hard disk has <mb> max blocks\n");
	fprintf(stderr, "\t-t, --time=<ticks>\t\t"
			"show read blocks at <ticks> ticks\n");
	fprintf(stderr, "\t-x, --xfig=<file>\t\t"
			"output snapshot to xfig <file>\n");
	fprintf(stderr, "\t-r, --rplot=<file>\t\t"
			"plot reverse access count function to <file>\n");
	fprintf(stderr, "\t-p, --plot=<file>\t\t"
			"plot access count function to <file>\n");
	fprintf(stderr, "\t-c, --calculate  \t\t"
			"perform magic calculation, look at the source.\n");
	fprintf(stderr, "\t-a, --adjacent=<file>  \t\t"
			"print xfig diagram about adjacent accesses.\n");
}


int
main(int argc, char **argv)
{
	FILE *f;
	int ret;
	unsigned long long simtime = 0;
	const char *xfig_output = NULL;
	const char *plot_output = NULL;
	const char *rplot_output = NULL;
	const char *logfile = NULL;
	int calculate = 0;
	const char *adjacent_output = NULL;
	struct option l_opts[] = {
		{"max-blocks", 1, NULL, 'm'},
		{"time", 1, NULL, 't'},
		{"xfig", 1, NULL, 'x'},
		{"rplot", 1, NULL, 'r'},
		{"plot", 1, NULL, 'p'},
		{"calculate", 0, NULL, 'c'},
		{"adjacent", 1, NULL, 'a'}
	};

	for (;;) {
		char c;

		c = getopt_long(argc, argv, "m:t:x:r:p:ca:", l_opts, NULL);
		if (c == -1) {
			break;
		}

		switch (c) {
		case 'm':
			max_blocks = atol(optarg);
			break;

		case 't':
			simtime = atoll(optarg);
			break;

		case 'x':
			xfig_output = optarg;
			break;

		case 'p':
			plot_output = optarg;
			break;

		case 'r':
			rplot_output = optarg;
			break;

		case 'c':
			calculate = 1;
			break;

		case 'a':
			adjacent_output = optarg;
			break;

		default:
			usage();
			return 1;
		}
	}

	if ((argc - optind != 1) || (simtime == 0) || (max_blocks == 0)) {
		usage();
		return 1;
	}

	logfile = argv[optind];

	blocks = calloc(max_blocks >> 3, 1);
	if (blocks == NULL) {
		fprintf(stderr, "-ENOMEM\n");
		return 1;
	}
	
	f = fopen(logfile, "r");
	if (f == NULL) {
		fprintf(stderr, "Could not open <%s>: %s\n",
			logfile, strerror(errno));
		return 1;
	}

	parse_log(f, simtime, plot_output);
	ret = fclose(f);
	assert(ret == 0);

	if (xfig_output != NULL) {
		ret = write_xfig(xfig_output, simtime);
	}

	if (rplot_output != NULL) {
		int r1;
		f = fopen(rplot_output, "w");
		if (f == NULL) {
			fprintf(stderr, "Could not open <%s> for "
				"writing: %s\n", rplot_output, 
				strerror(errno));
			fprintf(stderr, "Skipping reverse access output.\n");
			return 1;
		}

		write_reverse_access_output(f);
		r1 = fclose(f);
		assert(r1 == 0);
	}

	if (calculate) {
		long double p;
		p = calculate_probability();
		fprintf(stderr, "P=%Le\n", p);
	}

	if (adjacent_output != NULL) {
		int r1;

		f = fopen(adjacent_output, "w");
		if (f == NULL) {
			fprintf(stderr, "Could not open <%s> for "
				"writing: %s\n", adjacent_output,
				strerror(errno));
			return 1;
		}

		write_adjacent(f);
		r1 = fclose(f);
		assert(r1 == 0);
	}

	return ret;
}