/*
 * Copyright 1998-1999, University of Notre Dame.
 * Authors: Brian W. Barrett, Arun F. Rodrigues, Jeffrey M. Squyres,
 * 	 and Andrew Lumsdaine
 *
 * This file is part of XMPI
 *
 * You should have received a copy of the License Agreement for XMPI 
 * along with the software; see the file LICENSE.  If not, contact 
 * Office of Research, University of Notre Dame, Notre Dame, IN 46556.
 *
 * Permission to modify the code and to distribute modified code is
 * granted, provided the text of this NOTICE is retained, a notice that
 * the code was modified is included with the above COPYRIGHT NOTICE and
 * with the COPYRIGHT NOTICE in the LICENSE file, and that the LICENSE
 * file is distributed with the modified code.
 *
 * LICENSOR MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED.
 * By way of example, but not limitation, Licensor MAKES NO
 * REPRESENTATIONS OR WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY
 * PARTICULAR PURPOSE OR THAT THE USE OF THE LICENSED SOFTWARE COMPONENTS
 * OR DOCUMENTATION WILL NOT INFRINGE ANY PATENTS, COPYRIGHTS, TRADEMARKS
 * OR OTHER RIGHTS.
 *
 * Additional copyrights may follow.

 *
 *	$Id: xmpi_db_int.c,v 1.3 1999/11/08 06:20:23 bbarrett Exp $
 * 
 *	Function:	- set up the internal structure of the database
 */

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>

#include "all_list.h"
#include "lam.h"
#include "xmpi.h"
#include "xmpi_dbase.h"

/* 
 * global functions
 */
int			xmpi_db_internals();

/*
 * external functions
 */
extern int		xmpi_db_getgpeer();

/*
 * local functions
 */
static double		find_maxtime();
static double		find_mintime();
static int		normalize_times();
static int		sender_lists();
static int		trtime_cmp();
static void		link_to_senders();
static int		link_and_adjust();
static struct xmdbtr	*find_send();
static void		settachyon();
static int		detachyon();
static void		make_nodelist();

/*
 * external variables
 */
extern struct xmdb	dbase;			/* database */
extern struct dbparse   *dbp;			/* array parsing state */

/*
 *	xmpi_db_internals
 *
 *	Function:	- set up the database internal structures
 *	Returns:	- 0 or LAMERROR
 */
int
xmpi_db_internals()

{
	struct xmdbproc *proc;			/* process in database */
	int		i;
/*
 * The current trace for each process starts out as the first one.
 */
	for (i = dbase.xdb_nprocs, proc = dbase.xdb_procs; i > 0; i--, proc++) {
		proc->xdbp_curtrace = al_top(proc->xdbp_traces);
	}
/*
 * Connect the sends/receives with arrows and adjust times.
 */
	if (link_and_adjust()) {
		return(LAMERROR);
	}

	dbase.xdb_mintime = find_mintime();
	dbase.xdb_maxtime = find_maxtime();
/*
 * Set up the back linked lists of senders and make links from the traces to
 * these sender lists.
 */
	if (sender_lists()) {
		return(LAMERROR);
	}

	link_to_senders();
	return(0);
}

/*
 *	find_maxtime
 *
 *	Function:	- find maximum time in database
 *	Returns:	- maximum end time over all traces
 */
static double
find_maxtime()

{
	struct xmdbproc *proc;			/* process in database */
	struct xmdbtr   *p;
	double		tmax;			/* maximum time */
	int		i;

	tmax = 0.0;
	proc = dbase.xdb_procs;
	
	for (i = 0; i < dbase.xdb_nprocs; i++, proc++) {
		p = al_bottom(proc->xdbp_traces);
		if (p->xdbt_time + p->xdbt_lapse > tmax) {
			tmax = p->xdbt_time + p->xdbt_lapse;
		}
	}
	
	return(tmax);
}

/*
 *	find_mintime
 *
 *	Function:	- find minimum time in database
 *	Returns:	- minimum end time over all traces
 */
static double
find_mintime()

{
	struct xmdbproc *proc;			/* process in database */
	struct xmdbtr   *p;
	double		tmin;			/* minimum time */
	int		i;

	proc = dbase.xdb_procs;
	p = al_top(proc->xdbp_traces);
	tmin = p->xdbt_time;
	
	for (i = 1, proc++; i < dbase.xdb_nprocs; i++, proc++) {
		p = al_top(proc->xdbp_traces);
		if (p->xdbt_time < tmin) {
			tmin = p->xdbt_time;
		}
	}

	return(tmin);
}

/*
 *	normalize_times
 *
 *	Function:	- normalize all times for a process
 *			- updates the minimum trace lapse
 *	Accepts:	- rank of process
 *			- time to adjust by
 *			- min start time of segment (already adjusted)
 *	Returns:	- 0 or LAMERROR
 */
static int
normalize_times(rank, adjtime, mintime)

int			rank;
double			adjtime;
double			mintime;

{
	struct xmdbtr   xtr;			/* database runtime trace */
	struct xmdbproc *proc;			/* process in database */
	struct xmdbtr   *p, *q;
	double		minlapse;		/* minimum trace lapse */
	
	memset(&xtr,0,sizeof(xtr));

	proc = dbase.xdb_procs + rank;
	if ((p = al_top(proc->xdbp_traces)) == 0) {
		errno = EIMPOSSIBLE;
		return(LAMERROR);
	}

	p->xdbt_time += adjtime;
	minlapse = p->xdbt_lapse;

	if (p->xdbt_time > mintime) {
/*
 * Insert undefined trace at start of trace list.
 */
		xtr.xdbt_state = XMPI_SUNDEF;
		xtr.xdbt_time = mintime;
		xtr.xdbt_lapse = p->xdbt_time - mintime;
		xtr.xdbt_arrow = 0;
		xtr.xdbt_arrowdir = XMPI_DBNA;
		xtr.xdbt_senders = 0;
		xtr.xdbt_grank = rank;
		xtr.xdbt_systotal = 0.0;
		xtr.xdbt_blktotal = 0.0;

		if (al_insert(proc->xdbp_traces, &xtr) == 0) {
			return(LAMERROR);
		}
	}
/*
 * Normalize all traces for process.
 */
	q = p;
	p = al_next(proc->xdbp_traces, p);
	
	while (p) {
		p->xdbt_time += adjtime;
		if (p->xdbt_lapse < minlapse) {
			minlapse = p->xdbt_lapse;
		}
/*
 * Ensure that there are no time black holes.  This step is necessary
 * because FP arithmetic may not be commutative, i.e. if a + b == c then
 * it does not necessarily follow that (a - x) + b == c - x.
 */
		q->xdbt_lapse = p->xdbt_time - q->xdbt_time;

		q = p;
		p = al_next(proc->xdbp_traces, p);
	}
/*
 * Update database minimum lapse time.
 */
	if (minlapse < dbase.xdb_minlapse) {
		dbase.xdb_minlapse = minlapse;
	}

	return(0);
}

/*
 *	sender_lists
 *
 *	Function:	- create the back linked lists of senders to each
 *			  process
 *	Returns:	- 0 or LAMERROR
 */
static int
sender_lists()

{
	struct xmdbtr   **p;
	struct xmdbtr	**sp;
	struct xmdbtr   **senders;		/* array pointers to senders */
	struct dbparse  *pp;			/* parsing state */
	int		smax;			/* maximum number of senders */
	int		n;			/* number of senders */
	int		i;
	int		j;
/*
 * Find maximum number of senders to any one process.
 */
	smax = 0;
	for (i = 0, pp = dbp; i < dbase.xdb_nprocs; i++, pp++) {
		if ((n = al_count(pp->dbp_senders)) > smax) {
			smax = n;
		}
	}
	if (smax == 0) {
		return(0);
	}
	
	senders = (struct xmdbtr **) malloc(smax * sizeof(struct xmdbtr *));
	if (senders == 0) return(LAMERROR);
/*
 * Loop through processes.
 */
	for (i = 0, pp = dbp; i < dbase.xdb_nprocs; i++, pp++) {
/*
 * Make array of pointers to traces that are sends to current process (i).
 */
		p = al_top(pp->dbp_senders);
		sp = senders;
/*
 * Loop through traces. Add to the array a pointer to each trace that is
 * a send to destination process i.
 */
		while (p) {
			*(sp++) = *p;
			p = al_next(pp->dbp_senders, p);
		}
/*
 * Sort the sender array and then make the backwards linked list of senders
 * and put it in the database.
 */
		n = al_count(pp->dbp_senders);
		qsort((char *)senders, n, sizeof(struct xmdbtr *), trtime_cmp);
		
		p = senders + n - 1;
		for (j = n; j > 0; j--, p--) {
			if (al_append(dbase.xdb_procs[i].xdbp_msgsnd, p) == 0) {
				free((char *) senders);
				return(LAMERROR);
			}
		}
	}
	
	free((char *) senders);
	return(0);
}

/*
 *	trtime_cmp
 *
 *	Function:	- compare trace times
 *	Accepts:	- ptr to ptr to trace
 *			- ptr to ptr to trace
 *	Returns:	- returns -1/0/1 comparison
 */
static int
trtime_cmp(a, b)

struct xmdbtr		**a;
struct xmdbtr		**b;

{
	return(((*a)->xdbt_time < (*b)->xdbt_time) ? -1 :
		((*a)->xdbt_time == (*b)->xdbt_time) ? 0 : 1);
}

/*
 *	link_to_senders
 *
 *	Function:	- sets the link from each trace into the list of
 *			  senders
 */
static void
link_to_senders()

{
	struct xmdbproc *proc;			/* process in database */
	struct xmdbtr   **s;			/* sender */
	struct xmdbtr   *p;
	int 		i;
/*
 * Loop through processes.
 */
	for (i = 0, proc = dbase.xdb_procs; i < dbase.xdb_nprocs; proc++, i++) {
/*
 * Loop through traces setting link for each trace. Links must previously
 * have been initialized to null.
 */
		s = al_top(proc->xdbp_msgsnd);
		p = al_bottom(proc->xdbp_traces);
		
		while (s != 0 && p != 0) {

			if (p->xdbt_time + p->xdbt_lapse >= (*s)->xdbt_time) {
				p->xdbt_senders = s;
			}
			else {
				s = al_next(proc->xdbp_msgsnd, s);
				while (s != 0
					&& ((p->xdbt_time + p->xdbt_lapse)
						< (*s)->xdbt_time)) {
					s = al_next(proc->xdbp_msgsnd, s);
				}
				p->xdbt_senders = s;
			}
			p = al_prev(proc->xdbp_traces, p);
		}
	}
}

/*
 *	link_and_adjust
 *
 *	Function:	- make arrow connections between sends and receives,
 *			  de-tachyon and normalize database times.
 *	Returns:	- 0 or LAMERROR
 */
static int
link_and_adjust()

{
	struct xmdbproc *proc;			/* process in database */
	struct xmdbtr   *r;			/* receiver trace */
	struct xmdbtr   *s;			/* sender trace */
	struct xmdbtr   **last;			/* last sender trace */
	struct dbparse  *pp;			/* parsing state */
	double		*tachyons;		/* tachyons */
	int		*istach;		/* tachyon flags */
	int		nnodes;			/* number of nodes */
	int		*nodes;			/* array of nodes */
	int		*nodei;			/* array of indices */
	int		nprocs;			/* number of processes */
	int		*p;
	int 		i;

	nprocs = dbase.xdb_nprocs;

	if ((nodes = (int *) malloc(nprocs * sizeof(int))) == 0) {
		return(LAMERROR);
	}
	if ((nodei = (int *) malloc(nprocs * sizeof(int))) == 0) {
		free((char *) nodes);
		return(LAMERROR);
	}
/*
 * Create an array of nodeid's and of index of each process in this array.
 */
	make_nodelist(nodei, nodes, &nnodes);

	tachyons = (double *) malloc(nnodes * nnodes * sizeof(double));
	if (tachyons == 0) {
		free((char *) nodes);
		free((char *) nodei);
		return(LAMERROR);
	}
	
	if ((istach = (int *) malloc(nnodes * nnodes * sizeof(int))) == 0) {
		free((char *) nodes);
		free((char *) nodei);
		free((char *) tachyons);
		return(LAMERROR);
	}
	
	for (i = 0, p = istach; i < nnodes * nnodes; i++, p++) {
		*p = 0;
	}
/*
 * Link arrows recording tachyons.
 */
	proc = dbase.xdb_procs;
	pp = dbp;

	for (i = 0; i < dbase.xdb_nprocs; i++, proc++, pp++) {
		last = al_bottom(pp->dbp_senders);
		r = al_bottom(proc->xdbp_traces);

		while (r != 0) {
			if (r->xdbt_arrowdir == XMPI_DBIN) {
				s = find_send(i, &r->xdbt_envelop, last);
				if (s != 0) {
					r->xdbt_arrow = s;
					s->xdbt_arrow = r;
					settachyon(r, s, tachyons,
							istach, nodei, nnodes);
				}
			}
			r = al_prev(proc->xdbp_traces, r);
		}
	}
/*
 * De-tachyon the database.
 */
	detachyon(tachyons, istach, nodei, nnodes);

	free((char *) tachyons);
	free((char *) istach);
	free((char *) nodei);
	free((char *) nodes);
	return(0);
}

/*
 *	find_send
 *
 *	Function:	- find the send corresponding to a receive
 *	Accepts:	- rank of process doing the receive
 *			- received message envelope
 *			- last send trace
 */
static struct xmdbtr *
find_send(rank, env, s)

int			rank;
struct xmdbenv		*env;
struct xmdbtr		**s;

{
	struct dbparse  *pp;			/* parsing state */
	int		gpeer;			/* peer global rank */

	pp = dbp + rank;
	gpeer = xmpi_db_getgpeer(env->xdbe_cid, rank,
		(env->xdbe_lpeer == -1) ? env->xdbe_mlpeer : env->xdbe_lpeer);

	while (s != 0) {

		if (((*s)->xdbt_arrow == 0)
			&& ((*s)->xdbt_envelop.xdbe_seqnum == env->xdbe_seqnum)
			&& ((*s)->xdbt_grank == gpeer)) {

			return(*s);
		}

		s = al_prev(pp->dbp_senders, s);
	}

	return(0);
}

/*
 *	settachyon
 *
 *	Function:	- record a tachyon
 *	Accepts:	- receive trace
 *			- send trace
 *			- tachyon array
 *			- tachyon is recorded array
 *			- array indexing processes to nodes
 *			- number of nodes
 */
static void
settachyon(recv, send, tachyons, istach, nodei, nnodes)

struct xmdbtr   	*recv;
struct xmdbtr   	*send;
double			*tachyons;
int			*istach;
int			*nodei;
int			nnodes;

{
	double		diff;			/* time difference */
	double		*t;			/* ptr in tachyon array */
	int		*it;			/* ptr in tach. rec. array */
	int		r;			/* rank of receiver */
	int		s;			/* rank of sender */
	
	r = recv->xdbt_grank;
	s = send->xdbt_grank;
	
	if (nodei[r] == nodei[s]) {
		return;
	}

	it = istach + nodei[r] * nnodes + nodei[s];
	t = tachyons + nodei[r] * nnodes + nodei[s];
	
	diff = send->xdbt_time - (recv->xdbt_time + recv->xdbt_lapse);
	
	if (*it) {
		if (diff > *t) {
			*t = diff;
		}
	} else {
		*t = diff;
		*it = 1;
	}
}

/*
 *	detachyon
 *
 *	Function:	- detachyon and adjust times in the database
 *			- all processes set to start at time 0.
 *	Accepts:	- tachyon array
 *			- tachyon is recorded array
 *			- array indexing processes to nodes
 *			- number of nodes
 *	Returns:	- 0 or LAMERROR
 */
static int
detachyon(tachyon, istachyon, nodei, nn)

double			*tachyon;
int			*istachyon;
int			*nodei;
int			nn;

#define istach(r,s)	(*(istachyon + (nn * (r)) + (s)))
#define tach(r,s)	(*(tachyon + (nn * (r)) + (s)))

{
	struct dbparse  *pp;			/* parsing state */
	double		t;			/* time */
	double		tmin;			/* overall minimum time */
	double		segtmin;		/* segment minimum time */
	double		*adjust;		/* array of time adjustments */
	int		advance;		/* backard/forward tachyon? */
	int		i, j, k;		/* favourite indices */

	if ((adjust = (double *) malloc(nn * sizeof(double))) == 0) {
		return(LAMERROR);
	}
	
	adjust[0] = 0.0;
	for (i = 1; i < nn; i++) {
		adjust[i] = 0.0;
		advance = 0;
/*
 * Determine adjustment to clock of node i relative to nodes 0...(i-1).
 */
		for (k = 0; k < i; k++) {
			if (istach(i,k) && advance != -1) {
				t = tach(i,k);
				if (t > adjust[i]) {
					adjust[i] = t;
					advance = 1;
				}
			} else if (istach(k,i) && advance != 1) {
				t = tach(k,i);
				if (t > adjust[i]) {
					adjust[i] = t;
					advance = -1;
				}
			}
		}
/*
 * Update tachyons of nodes (i+1)...n relative to node i.
 */
		if (advance) {
			adjust[i] *= advance;
			for (j = i + 1; j < nn; j++) {
				if (istach(j,i)) tach(j,i) += adjust[i];
				if (istach(i,j)) tach(i,j) -= adjust[i];
			}
		}
	}
/*
 * Find application start time taking into account adjustments.
 */
	pp = dbp;
	tmin = pp->dbp_start + adjust[nodei[0]];

	for (i = 1, pp++; i < dbase.xdb_nprocs; i++, pp++) {
		t = pp->dbp_start + adjust[nodei[i]];
		if (t < tmin) {
			tmin = t;
		}
	}
/*
 * Find segment start time taking into account normalization.
 */
	pp = dbp;
	segtmin = pp->dbp_curseg->oo_ontime + adjust[nodei[0]] - tmin;

	for (i = 1, pp++; i < dbase.xdb_nprocs; i++, pp++) {
		t = pp->dbp_curseg->oo_ontime + adjust[nodei[i]] - tmin;
		if (t < segtmin) {
			segtmin = t;
		}
	}
/*
 * Adjust all the times in the database.
 */
	for (i = 0; i < dbase.xdb_nprocs; i++) {
		if (normalize_times(i, adjust[nodei[i]] - tmin, segtmin)) {
			free((char *) adjust);
			return(LAMERROR);
		}
	}

	free((char *) adjust);
	return(0);
}

/*
 *	make_nodelist
 *
 *	Function:	- make array of nodes and index processes into it
 *	Accepts:	- array of indices (out)
 *			- array of nodes (out)
 *			- number of nodes (out)
 */
static void
make_nodelist(indices, nodes, numnodes)

int			*indices;
int			*nodes;
int			*numnodes;

{
	struct xmdbproc *p;
	int		done;			/* node already in array? */
	int		i, j;
	
	*numnodes = 0;
	for (i = 0, p = dbase.xdb_procs; i < dbase.xdb_nprocs; i++, p++) {
		for (j = 0, done = 0; j < *numnodes && !done; j++) {
			done = (p->xdbp_node == nodes[j]);
		}
		if (!done) {
			*(nodes + *numnodes) = p->xdbp_node;
			indices[i] = *numnodes;
			(*numnodes)++;
		} else {
			indices[i] = j - 1;
		}
	}
}