/* $Id: spf.c,v 10.1 92/10/06 23:07:10 ca Exp $ */
/*
 * MaRS Maryland Routing Simulator
 * Copyright (c) 1991 University of Maryland
 * All Rights Reserved.
 *
 * Permission to use, copy, modify, distribute, and sell this software and its
 * documentation for any purpose is hereby granted without fee, provided that
 * the above copyright notice appear in all copies and that both that
 * copyright notice and this permission notice appear in supporting
 * documentation, and that the name of U.M. not be used in advertising or
 * publicity pertaining to distribution of the software without specific,
 * written prior permission.  U.M. makes no representations about the
 * suitability of this software for any purpose.  It is provided "as is"
 * without express or implied warranty.
 *
 * U.M. DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL U.M.
 * BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 *
 * Authors: Cengiz Alaettinoglu, Klaudia Dussa-Zieger, Ibrahim Matta
 *          Systems Design and Analysis Group
 *          Department of Computer Science 
 *          University of Maryland at College Park. 
 */

/*
 * Routing Module 
 * 
 */
#include <sys/types.h>
#include <stdio.h>
#include <math.h>
#include "sim.h"
#include "q.h"
#include "list.h"
#include "component.h"
#include "log.h"
#include "comptypes.h"
#include "packet.h"
#include "eventdefs.h"
#include "event.h"
#include "node.h"
#include "spf.h"
#include "perf.h"

#ifdef DEBUG
extern Log debug_log;
#endif

#define SNT(g) (*((SeqNoTable *)(g->seq_no_table->u.p)))

static caddr_t spf_create(), spf_delete(), 
   spf_neighbor(), spf_uneighbor(), spf_start(),
   spf_reset(), spf_broadcast(), spf_processing();

static int routing_processing_time();
static int add_new_node();
void fr_space();
char *make_gtt_text();
static void exchange_GTT();

caddr_t spf_action(src, g, type, pkt, arg)
     Component *src;
     register Spft *g;
     int type;
     Packet *pkt;
     caddr_t arg;
{
  caddr_t result = NULL;

  dbg_set_level(DBG_ERR);

  /* Just a big switch on type of event */
  switch (type)  {
    case EV_RESET:
#ifdef DEBUG
      dbg_write(debug_log, DBG_INFO, (Component *)g, "reset");
#endif
      result = spf_reset(g);
      break;
    
    case EV_CREATE:
      /* Minor sanity check first-- g should be NULL when initializing. */
#ifdef DEBUG
      if (g)
        dbg_write(debug_log, DBG_INFO, (Component *)NULL,
		  "SPF Generator initialization called with non-null pointer.");
#endif
      result = spf_create((char *)arg);
      break;

    case EV_DEL:
      result = spf_delete(g);
      break;
      
    case EV_NEIGHBOR:
      result = spf_neighbor(g, (Component *)arg);
      break;

    case EV_UNEIGHBOR:
      result = spf_uneighbor(g, (Component *)arg);
      break;

    case EV_MK_PEER:
      result = (caddr_t) g;
      break;

    case EV_START:
      result = spf_start(g);
      break;

    case EV_STOP:
      result = (caddr_t) g;
      break;

    /* The preceding were the commands.  Now the actual events */

    case EV_ROUTE_PROCESSING:
      result = spf_processing(g, pkt); 
      break;

    case EV_SPF_BROADCAST:
      result = spf_broadcast(g); 
      break;

    default:
#ifdef DEBUG
      dbg_write(debug_log, DBG_ERR, (Component *)g,
		"got unexpected event of type %x", type);
#endif
      break;
    }

  return(result);
}

/****************************************/
static caddr_t spf_create(name)
     register char *name;
{
  Spft *newg;

  /* Memory for the component structure. */
  newg = (Spft *)sim_malloc(sizeof(Spft));
  
  /* First things first-- copy name into the new structure. */
  strncpy(newg->spf_name, name, 40);
  
  /* have to create a neighbor list */
  newg->spf_neighbors = l_create();
  newg->spf_params = q_create();
  
  newg->spf_class = ROUTE_CLASS;
  newg->spf_type = SPF;
  newg->spf_action = spf_action;
  newg->spf_menu_up = FALSE;

  /* Initialize the parameters */
  (void)param_init((Component *)newg, "Name",
	     (PFD)NULL, make_name_text, make_short_name_text,
	     param_input_name,
	     0, DisplayMask | InputMask, 0.0);
  
  newg->brdcast_period = param_init((Component *)newg,
	    "Time btw topology broad (msec)",
	     int_calc, make_int_text, make_short_int_text,
	     param_input_int,
	     0, DisplayMask | ModifyMask, 0.0);
  pval(newg, brdcast_period)->u.i = 10000;
 
  newg->sd = param_init((Component *)newg,
	    "Standard deviation",
	     (PFD)NULL, make_int_text, make_short_int_text,
	     param_input_int,
	     0, DisplayMask | ModifyMask, 0.0);
  pval(newg, sd)->u.i = 1000;

  newg->seq_no = param_init((Component *)newg,
	    "Sequence number",
	     int_calc, make_int_text, make_short_int_text,
	     param_input_int,
	     TIME_HISTORY, 0, 0.0);
  pval(newg, seq_no)->u.i = 0;
    
  newg->global_top = param_init((Component *)newg,
	    "Global topology table",
	     (PFD)NULL, make_text, make_gtt_text,
	     (PFI)NULL,
	     TEXT_METER, DisplayMask | CanHaveLogMask | CanHaveMeterMask, 0.0);
  pval(newg, global_top)->u.p = sim_malloc(sizeof(GlobalTopTable));
    
  newg->local_top = param_init((Component *)newg,
	    "Local topology table",
	     (PFD)NULL, make_text, make_ltt_text,
	     (PFI)NULL,
	     TEXT_METER, DisplayMask | CanHaveLogMask | CanHaveMeterMask, 0.0);
  pval(newg, local_top)->u.p = (caddr_t) NULL;
  
  newg->routing_table = param_init((Component *)newg,
	    "Routing table",
	     (PFD)NULL, make_text, make_rt_text,
	     (PFI)NULL,
	     TEXT_METER, DisplayMask | CanHaveLogMask | CanHaveMeterMask, 0.0);
  pval(newg, routing_table)->u.p = sim_malloc(sizeof(RoutingTable));
    
  newg->seq_no_table = param_init((Component *)newg,
	    "Last sequence no table",
	     (PFD)NULL, make_text, make_text,
	     (PFI)NULL,
	     0, 0, 0.0);
  pval(newg, seq_no_table)->u.p = sim_malloc(sizeof(SeqNoTable));
  
  newg->processing_time = routing_processing_time;
  newg->no_of_nodes	= 0;
  newg->node		= (Component *) NULL;

#ifdef DEBUG
  dbg_write(debug_log, DBG_INFO, (Component *)newg,
	    "spf generator initialized");
#endif
  
  return((caddr_t)newg);
}

static caddr_t spf_delete(g)
     register Spft *g;
{
   free(g->routing_table->u.p);
   free(g->global_top->u.p);
   free(g->seq_no_table->u.p);
   comp_delete((Component *) g);
   return (caddr_t) g;
}

static caddr_t spf_reset(g)
Spft *g;	
{	
  g->no_of_nodes= g->spf_neighbors->l_len; 
  g->seq_no->u.i = 0;
  g->link_cost_time = 0;

  log_param((Component *)g, g->seq_no);
  return (caddr_t) g;
}	

/****************************************/
static caddr_t spf_neighbor(g, c)
     register Spft *g;
     register Component *c;
{
   caddr_t result;

  /* Put the passed neighbor into my neighbor list, but only if it is
     a legal neighbor (a node).  Also can only have one neighbor.  */
  
   result = (caddr_t)add_neighbor((Component *)g, c, 1, 1, NODE_CLASS);
   if (result != (caddr_t)NULL) {
      g->local_top->u.p = (caddr_t)((Nodee *)c)->loc_topology_table;
      g->node	   = c;
      add_new_node(g, c);
   }
   return result;
}
 
/****************************************/
static caddr_t
spf_uneighbor(g, c)
     register Spft *g;
     register Component *c;
{
   caddr_t result;

   result = (caddr_t)remove_neighbor((Component *)g, c);
   if (result != (caddr_t)NULL) {
      g->local_top->u.p		= (caddr_t) NULL;
      g->node	   		= (Component *) NULL;
      g->no_of_nodes		= 0;
   }
   return result;
}

/****************************************/
static caddr_t spf_start(g)
register Spft *g;
{
  
  if (g->spf_neighbors->l_len != 1)  {
#ifdef DEBUG
    dbg_write(debug_log, DBG_ERR, (Component *)g,
	      "Spf Module not connected to a node");
#endif
    return((caddr_t)NULL);
  }

  if (!lcostfcn_adr)  {
     printf("LINK_COST_FUNC typed component not found...\n");
     return((caddr_t)NULL);
  }

  /* start broadcasting */
  ev_enqueue(EV_SPF_BROADCAST, (Component *)g, (Component *)g, ev_now(),
	  g->spf_action, (Packet *)NULL, (caddr_t)NULL);
 
  /* Something non-NULL to return */
  return((caddr_t)g);
}


static void inf_global_topology_table(g, ind)
Spft *g;
int	  ind;
{
   int i;
   for (i=0; i<g->no_of_nodes; i++) 
      GTT(g)[ind][i] = MARS_INFINITY;

}

static int add_new_node(g, c)
register Spft *g;
Component       *c;
{
   int ind;
   int i;

   ind 	= g->no_of_nodes;
   g->no_of_nodes++;
   RT(g) [ind].dest  	= c;
   RT(g) [ind].hop      = (Component *) NULL;
   RT(g) [ind].cost     = MARS_INFINITY;
   SNT(g)[ind].no   	= 0;

   for (i=0; i<g->no_of_nodes; i++) {
      GTT(g)[ind][i] = MARS_INFINITY;
      GTT(g)[i][ind] = MARS_INFINITY;
   }

   return ind;
}

static int index_of(g, c)
register Spft *g;
register Component *c;
{
   register int ind;

   for (ind = 0; ind < g->no_of_nodes; ind++)
      if (RT(g)[ind].dest == c)
	 return ind;

   return -1;
}

static void spf (g)
register Spft *g;
{
   int i, ind, min_ind;
   unsigned int min_cost;

   for (i = 0; i < g->no_of_nodes; i++) {
      RT(g)[i].hop  = (Component *) NULL;
      RT(g)[i].cost = MARS_INFINITY;
      SNT(g)[i].mark = 1;
   }   

   ind = index_of(g, g->node);
   RT(g)[ind].cost = 0;
   SNT(g)[ind].mark = 0;

   for (i = 0; LTT(g)[i].n_nd != (Component *) NULL; i++)
      if (*LTT(g)[i].l_status == 'U') {
	 ind = index_of(g, LTT(g)[i].n_nd);
	 if (ind == -1)
	    ind	= add_new_node(g, LTT(g)[i].n_nd);
	 RT(g)[ind].hop  = LTT(g)[i].n_link;
	 RT(g)[ind].cost = LTT(g)[i].l_cost;
      }

   while (1) {
      min_ind = -1;
      min_cost= MARS_INFINITY;
      for  (i=0; i < g->no_of_nodes ; i++)
	 if (RT(g)[i].cost < min_cost && SNT(g)[i].mark == 1) {
	    min_ind  = i;
	    min_cost = RT(g)[i].cost;
	 }
      if (min_cost == MARS_INFINITY)
	 return;

      SNT(g)[min_ind].mark = 0;

      for  (i=0; i < g->no_of_nodes ; i++)
	 if (RT(g)[i].cost > min_cost + GTT(g)[min_ind][i]
	     && SNT(g)[i].mark == 1
	     && GTT(g)[min_ind][i] != MARS_INFINITY) {
	    RT(g)[i].cost = min_cost + GTT(g)[min_ind][i];
	    RT(g)[i].hop  = RT(g)[min_ind].hop;
	 }
   }
}

static int link_costs(g)
register Spft *g;
{
   int so_ind, neig_ind, i;

   so_ind = index_of(g, g->node);
   inf_global_topology_table(g, so_ind);

   for (i = 0; LTT(g)[i].n_nd != (Component *) NULL; i++) {
      neig_ind    = index_of(g, LTT(g)[i].n_nd);
      if (neig_ind == -1) 
	 neig_ind = add_new_node(g, LTT(g)[i].n_nd);
      LTT(g)[i].l_cost = link_cost((Routet *)g, i);
      GTT(g)[so_ind][neig_ind] = LTT(g)[i].l_cost;
   }

   return i;
}

static void broadcast_pkt(g, pkt)
register Spft *g;
register Packet *pkt;
{
   Packet *p;
   int i, rt_pkts_count;

    rt_pkts_count = 0;
    for (i = 0; LTT(g)[i].n_nd != (Component *) NULL; i++)
      if (*LTT(g)[i].l_status == 'U') {
	 p = pk_alloc();
	 memcpy(p, pkt, sizeof(Packet));
	 p->pk_dest_socket.so_host   = LTT(g)[i].n_nd;
	 p->pk_dest_socket.so_port   = (Component *) NULL;
	 p->pk_source_socket.so_host = (Component *) NULL;
	 p->pk_source_socket.so_port = (Component *) NULL;
	 p->tail = sim_malloc(sizeof(CostPair)* p->rt_pk.rt.ls.no_pairs);
	 memcpy(p->tail, pkt->tail, sizeof(CostPair) * p->rt_pk.rt.ls.no_pairs);
         rt_pkts_count ++;
	 ev_call(EV_NODE_PRODUCE, (Component *)g, g->node, g->node->co_action,
		 p, LTT(g)[i].n_link);
      }
   pm((Component *)g, SPF, ROUTING_PKT, rt_pkts_count, 0, 0, 0);
}

static void ls_broadcast(g)
register Spft *g;
{
   Packet    *pkt;
   int	     no_of_nghbr, i;
   CostPair  *pair;

   g->seq_no->u.i++;
   no_of_nghbr = link_costs(g);
   pkt = pk_alloc();
   pkt->pk_length 	= LS_PKT_HEADER_SIZE + no_of_nghbr * sizeof(CostPair);
   pkt->pk_type   		= ROUTE_PACKET;
   pkt->rt_pk.rt_type 		= RT_LS;
   pkt->rt_pk.rt.ls.node 	= g->node;
   pkt->rt_pk.rt.ls.seq_no 	= g->seq_no->u.i;
   pkt->rt_pk.rt.ls.no_pairs 	= no_of_nghbr;
   pkt->tail                    = sim_malloc(no_of_nghbr * sizeof(CostPair));

   for (pair = (CostPair *) pkt->tail, i = 0; 
	LTT(g)[i].n_nd != (Component *) NULL; 
	i++, pair++) {
      pair->neighbour	= LTT(g)[i].n_nd;
      pair->cost	= LTT(g)[i].l_cost;
   }

   broadcast_pkt(g, pkt);

   pk_free(pkt); /* will free tail too */
}

static caddr_t spf_broadcast(g)
register Spft *g;
{
   unsigned int time_now, ticks;

   time_now = ev_now();
   ticks    = time_btw_broadcast(g) / USECS_PER_TICK;
   ev_enqueue(EV_SPF_BROADCAST, (Component *)g, (Component *)g, 
	      time_now + ticks, 
	      g->spf_action, (Packet *)NULL, (caddr_t)NULL);
 
   if (*(char *)(((Nodee *)g->node)->nd_status->u.p) == 'D')
      return((caddr_t)g);

   /* node is UP */

   compute_link_cost_metrics((Routet *)g);
   ls_broadcast(g);
   spf(g);
 
   log_param((Component *)g, g->routing_table);
   log_param((Component *)g, g->global_top);
   log_param((Component *)g, g->seq_no);

   return (caddr_t) g;
}

static void process_rt_ls(g, pkt)
register Spft *g;
register Packet *pkt;
{
   int src_ind, neighbour_ind, i;
   Component *src;
   CostPair  *pair;
   unsigned  int ticks;

   src 		= pkt->rt_pk.rt.ls.node;
   src_ind 	= index_of(g, src);

   /* check if we knew about this node. If not add it to table */
   if (src_ind == -1) 
      src_ind 	= add_new_node(g, src);

   /* check if it is a newer packet or not */
   if (SNT(g)[src_ind].no < pkt->rt_pk.rt.ls.seq_no) {
      SNT(g)[src_ind].no =pkt->rt_pk.rt.ls.seq_no;
      inf_global_topology_table(g, src_ind);
      pair = (CostPair *) pkt->tail;
      for (i = 0; i < pkt->rt_pk.rt.ls.no_pairs; i++, pair++) {
	 neighbour_ind = index_of(g, pair->neighbour);
	 /* check if we knew about the neighbour. If not add it to table */
	 if (neighbour_ind == -1)
	    neighbour_ind = add_new_node(g, pair->neighbour);
	 GTT(g)[src_ind][neighbour_ind] = pair->cost;
      }

      broadcast_pkt(g, pkt);
      spf(g);
   }
   
}

static caddr_t spf_processing(g, pkt)
register Spft *g;
register Packet *pkt;
{
   int i;
   unsigned int ticks;

   free_routing_queue((Routet *)g, pkt);	/* standard */

   switch (pkt->rt_pk.rt_type) {
    case RT_LINK_SHUTDOWN :
       for (i = 0; LTT(g)[i].n_nd != (Component *) NULL; i++)
	  if (LTT(g)[i].n_link == pkt->pk_source_socket.so_host) {
	     link_failure_init_LTT((Routet *)g, i);
	     ls_broadcast(g);
	     spf(g);
	     break;
	  }
       break;
    case RT_LINK_WAKEUP :
       for (i = 0; LTT(g)[i].n_nd != (Component *) NULL; i++)
	  if (LTT(g)[i].n_link == pkt->pk_source_socket.so_host) {
	     link_repair_init_LTT((Routet *)g, i);
	     ls_broadcast(g);
	     spf(g);
             exchange_GTT(g, i);
	     break;
	  }
       break;
    case RT_NODE_SHUTDOWN :
       for (i=0; i < g->no_of_nodes; i++) {
	  /* empty global topology table */
	  inf_global_topology_table(g, i);
	  /* empty routing table */
	  RT(g)[i].hop  = (Component *) NULL;
	  RT(g)[i].cost = MARS_INFINITY;
       }
       break;
    case RT_NODE_WAKEUP :
       ls_broadcast(g);
       spf(g);
       break;
    case RT_LS :
       process_rt_ls(g, pkt);
       break;
    default : ;
    }
   
   pk_free(pkt);

   log_param((Component *)g, g->routing_table);
   log_param((Component *)g, g->global_top);
   log_param((Component *)g, g->seq_no);
   log_param((Component *)g, g->seq_no_table);

   schedule_next_EV_ROUTE_PROCESSING((Routet *)g); /* standard */

   return((caddr_t)g);
}


static int routing_processing_time(g, pkt)
register Spft *g;
register Packet *pkt;
{
   int src_ind;

   switch (pkt->rt_pk.rt_type) {
    case RT_LINK_SHUTDOWN :
       return 2000;
    case RT_LINK_WAKEUP :
       return 2000;
    case RT_NODE_SHUTDOWN :
       return 10;
    case RT_NODE_WAKEUP :
       return 10;
    case RT_LS :
       if ((src_ind = index_of(g, pkt->rt_pk.rt.ls.node)) == -1) {
	  src_ind = add_new_node(g, pkt->rt_pk.rt.ls.node);
	  SNT(g)[src_ind].no_unprocessed = 0;
	  SNT(g)[src_ind].no		 = 0;
       }
       if (SNT(g)[src_ind].no_unprocessed < pkt->rt_pk.rt.ls.seq_no) {
	  SNT(g)[src_ind].no_unprocessed = pkt->rt_pk.rt.ls.seq_no;
	  return 6000;
       } else
	  return 1500;
    default : ;
    }
   return 10;
}

char *make_gtt_text(g, gtt)
Spft *g;
Param  *gtt;
{
   int i, j;
   extern char text[];
   extern char line[800];

   sprintf(text, "Topology Table of %s$            ",
	g->spf_name);   

   if (!g->routing_table->u.p)
      return text;

   for (i= 0; i < g->no_of_nodes; i++) {
      sprintf(line, "%-11s ", RT(g)[i].dest->co_name);
      strncat(text, line, sizeof(line));
   }
   strcat(text, "$");

   for (i = 0; i < g->no_of_nodes; i++){
	  sprintf(line, "%-11s ", RT(g)[i].dest->co_name);
	  strncat(text, line, sizeof(line));
	  for (j=0; j < g->no_of_nodes; j++){
	     sprintf(line, "%-11d ", GTT(g)[i][j]);  
	     strncat(text, line, sizeof(line));
	  }
      strcat(text, "$");
   }
   
   return text;
}

static void exchange_GTT (g, link_ind)
register Spft *g;
register int  link_ind;
{
   Packet    *pkt;
   int	     no_of_nghbr, i, j;
   CostPair  *pair;

   for (i = 1; i < g->no_of_nodes; i++) { /* i = 0 is the node skipped */
      for (no_of_nghbr = 0, j = 0; j < g->no_of_nodes; j++) {
	 if (GTT(g)[i][j]  != MARS_INFINITY) 
	    no_of_nghbr++;
      }

      pkt = pk_alloc();
      pkt->pk_length 	= LS_PKT_HEADER_SIZE + no_of_nghbr * sizeof(CostPair);
      pkt->pk_type   		= ROUTE_PACKET;
      pkt->rt_pk.rt_type 	= RT_LS;
      pkt->rt_pk.rt.ls.node 	= RT(g)[i].dest;
      pkt->rt_pk.rt.ls.seq_no 	= SNT(g)[i].no;
      pkt->rt_pk.rt.ls.no_pairs = no_of_nghbr;
      pkt->tail                 = sim_malloc(no_of_nghbr * sizeof(CostPair));

      for (pair = (CostPair *) pkt->tail, j = 0; j < g->no_of_nodes; j++) {
	 if (GTT(g)[i][j]  != MARS_INFINITY) {
	    pair->neighbour	= RT(g)[j].dest;
	    pair->cost	        = GTT(g)[i][j];
	    pair++;
	 }
      }
      
      pkt->pk_dest_socket.so_host   = LTT(g)[link_ind].n_nd;
      pkt->pk_dest_socket.so_port   = (Component *) NULL;
      pkt->pk_source_socket.so_host = (Component *) NULL;
      pkt->pk_source_socket.so_port = (Component *) NULL;

      ev_call(EV_NODE_PRODUCE, (Component *)g, g->node, g->node->co_action,
	      pkt, LTT(g)[link_ind].n_link);
   }

   pm((Component *)g, SPF, ROUTING_PKT, g->no_of_nodes - 1, 0, 0, 0);

}