/*		     RSPF - Radio Shortest Path First
 * This code may be used for non-commercial purposes only.
 *			Anders Klemets SM0RGV
 * 890918 - Version 2.0
 * 900816 - Version 2.1
 *
 * Mods by PA0GRI
 */
#include "global.h"
#include "config.h"
#include "mbuf.h"
#include "proc.h"
#include "timer.h"
#include "netuser.h"
#include "internet.h"
#include "pktdrvr.h"
#include "ip.h"
#include "iface.h"
#include "ax25.h"
#include "arp.h"
#include "icmp.h"
#include "socket.h"
#include "rspf.h"

#ifdef RSPF
extern struct route *rt_lookup __ARGS((int32 target));

#ifdef	AX25
extern struct lq *al_lookup __ARGS((struct iface *ifp,char *addr,int sort));
#else
static struct lq *al_lookup __ARGS((struct iface *ifp,char *addr,int sort));
#endif	/* AX25 */

struct rspf_stat Rspf_stat;
struct rspfreasm *Rspfreasmq = NULLRREASM;
struct rspfiface *Rspfifaces = NULLRIFACE;
struct rspfadj *Adjs = NULLADJ;
struct rspfrouter *Rspfrouters = NULLRROUTER;
struct mbuf *Rspfinq = NULLBUF;
struct timer Rspfreasmt, Susptimer;
char *Rrh_message = NULLCHAR;
unsigned short Rspfpingmax = 3;
static int Keeprouter = 0;
static int16 Envelopeid = 0;
static int Nrspfproc = 0;
static unsigned char Rspfsubseq = 0;
static short Rspfseq = -32768 + 1;
static char *findlowroute __ARGS((int32 addr,int *low,int add,int32 *resaddr,int *resbits));
static void makeroutes __ARGS((void));
static void partialupdate __ARGS((struct rspfrouter *rr,struct mbuf *bp));
static struct rspfrouter *rr_lookup __ARGS((int32 addr));
static void rr_delete __ARGS((int32 addr));
static struct rspfiface *rtif_lookup __ARGS((int32 addr));
static void rspfcsum __ARGS((struct mbuf **bpp,int32 dest));
static void update_in __ARGS((struct mbuf *bp,int32 addr));
static void node_in __ARGS((struct mbuf *bp,int32 addr,int full));
static void sendonerspf __ARGS((int32 addr,int32 dest));
static void sendtoall __ARGS((struct mbuf *bp,int nodecnt,struct rspfiface *riface));
static int sendupdate __ARGS((struct mbuf *bp,int nodecnt,int32 addr));
static int isnewer __ARGS((short a,short b));
static void del_reasm __ARGS((struct rspfreasm *re));
static void reasmtimeout __ARGS((void *t));
static struct mbuf *rspfreasm __ARGS((struct mbuf *bp,struct rspfpacketh *rph,int32 addr));
static struct mbuf *fragmenter __ARGS((struct mbuf *bp,int nodes,int16 mtu));
static struct mbuf *makeadjupdate __ARGS((int32 addr,struct rspfrouter *rr));
static void pushadj __ARGS((struct mbuf **bpp,int32 addr,int bits));
static void sendrrh __ARGS((struct rspfiface *ri));
static void sendrspf __ARGS((void));
static void goodbadnews __ARGS((struct rspfadj *adj));
static void add_rspfadj __ARGS((struct rspfadj *adj));
static void rspfcheck __ARGS((struct rspfadj *adj));
static void rspfping __ARGS((int oldstate,void *p,void *v));

/* IP passes its RSPF packets to this function */
void
rspf_input(iface,ip,bp,rxbroadcast)
struct iface *iface;
struct ip *ip;
struct mbuf *bp;
int rxbroadcast;
{
	struct pseudo_header ph;	/* Pseudo-header for checksumming */

	if(bp == NULLBUF)
	    return;
	if(Rspfifaces == NULLRIFACE){	/* Rspf main loop is not running */
	    free_p(bp);
	    return;
	}
	ph.length = ip->length - IPLEN - ip->optlen;
	ph.source = ip->source;
	ph.dest = ip->dest;
	ph.protocol = ip->protocol;
	if(cksum(&ph,bp,ph.length) != 0){
	    /* Checksum failed, ignore packet completely */
	    free_p(bp);
	    ++Rspf_stat.badcsum; 
	    return;
	}
	bp = pushdown(bp,1 + sizeof(ip->source) + sizeof(iface));
	*bp->data = RSPFE_PACKET;
	memcpy(bp->data + 1,&ip->source,sizeof(ip->source));
	memcpy(bp->data + 1 + sizeof(ip->source),&iface,sizeof(iface));
	enqueue(&Rspfinq,bp);
}

/* Main loop in RSPF process */
void
rspfmain(v,v1,v2)
int v;
void *v1,*v2;
{
	union rspf rspf;		/* Internal packet structure */
	struct rspfadj *adj = NULLADJ;	/* Adjacency */
	struct mbuf *bp, *tbp;
	struct rspfiface *riface;
	struct iface *iface;
	struct route *rp;
	int32 source;			/* Source address */
	int cmd;
	
	for(;;) {
	     if(Rspfinq == NULLBUF)
		  pwait(&Rspfinq);
	     bp = dequeue(&Rspfinq);	/* at least 5 bytes */
	     cmd = PULLCHAR(&bp);	/* get internal event indicator */
	     pullup(&bp,(char *)&source,sizeof(source));
	     switch(cmd) {
	     case RSPFE_RRH:
		  sendrrh((struct rspfiface *)source);
		  break;
	     case RSPFE_CHECK:
		  rspfcheck((struct rspfadj *)source);
		  break;
	     case RSPFE_UPDATE:
		  sendrspf();
		  break;
	     case RSPFE_ARP:
		  adj = (struct rspfadj *) source;
		  source = adj->addr;		/* fall through */
	     case RSPFE_PACKET:
		  pullup(&bp,(char *)&iface,sizeof(iface));
		  break;
	     }
	     if(cmd != RSPFE_PACKET && cmd != RSPFE_ARP)
		  continue;
	     if(cmd == RSPFE_PACKET && ntohrspf(&rspf,&bp) == -1){
		  free_p(bp);
		  continue;
	     }
	     if(iface != NULLIF) {
		  for(riface = Rspfifaces; riface != NULLRIFACE; riface =
		      riface->next)
		       if(riface->iface == iface)
			   break;
	     } else
		  /* fails if there is no route or no RSPF interface */
		  riface = rtif_lookup(source);

	     if(riface == NULLRIFACE) {
		  free_p(bp);
		  if(cmd == RSPFE_PACKET)
		       ++Rspf_stat.norspfiface;
		  continue;	/* We do not use RSPF on this interface */
	     }
	     /* If we dont have an entry in the routing table for this station,
	      * or if the entry is less than 32 bits specific or has a higher
	      * cost than our new route, and is pointing to the wrong interface,
	      * then add a correct, private, route.
	      */
	     rp = rt_lookup(source);
	     if(rp == NULLROUTE || (rp != NULLROUTE && rp->iface !=
		    riface->iface && (rp->bits < 32 || rp->metric >
				      riface->quality))){
		  rt_add(source,32,0,iface,riface->quality,0,1);
	     }

	     if(cmd == RSPFE_ARP) {
		if(adj != NULLADJ){
		  adj->cost = riface->quality;	/* default cost */
		  add_rspfadj(adj);
		  continue;
		}
	     }
	     switch(rspf.hdr.type){		/* packet types */
	     case RSPF_RRH:
		  ++Rspf_stat.rrhin;
		  free_p(bp);
		  adj = (struct rspfadj *)callocw(1,sizeof(struct rspfadj));
		  adj->addr = rspf.rrh.addr;
		  adj->seq = rspf.rrh.seq;
		  adj->cost = riface->quality;	/* Default cost */
		  adj->state = RSPF_TENTATIVE;
		  if(rspf.rrh.flags & RSPFMODE)
		       adj->tos = DELAY;
		  else
		       adj->tos = RELIABILITY;
		  add_rspfadj(adj);
		  break;
	     case RSPF_FULLPKT:
		  ++Rspf_stat.updatein;
		  /* Feed the packet through the reassembly queue */
		  if((tbp = rspfreasm(bp,&rspf.pkthdr,source)) != NULLBUF)
		       update_in(tbp,source);
		  break;
	     }
	}
}

/* This function is called every time an RRH should be broadcasted.
 * An RRH is sent on the interface given by ri or on every RSPF interface.
 * The broadcast address of the interface must be routed onto the same
 * interface (using a static route for instance) otherwise there will be no
 * RRH sent on that interface.
 */
static void
sendrrh(ri)
struct rspfiface *ri;		/* interface to use, if specified */
{
    struct pseudo_header ph;
    struct mbuf *bp, *data = NULLBUF;
    struct rspfiface *riface;
    struct route *rp;
    struct rrh rrh;

    for(riface = Rspfifaces; riface != NULLRIFACE; riface = riface->next) {
	 if(ri != NULLRIFACE && riface != ri)
	      continue;
	 if((rp = rt_lookup(riface->iface->broadcast)) != NULLROUTE &&
	    rp->iface == riface->iface){
	      rrh.version = RSPF_VERSION;
	      rrh.addr = riface->iface->addr;
	      ph.length = 0;
	      if(Rrh_message != NULLCHAR) {
		   data = ambufw((int16)strlen(Rrh_message));
		   memcpy(data->data,Rrh_message,strlen(Rrh_message));
		   ph.length = data->cnt = strlen(Rrh_message);
	      }
	      ph.length += RRHLEN;
	      ph.source = riface->iface->addr;
	      ph.dest = riface->iface->broadcast;
	      ph.protocol = RSPF_PTCL;
	      /* Start the RRH link level packet counter at 1, since adj->seq
	       * is 0 only for ARP generated adjacencies. This is also correct
	       * since rawsndcnt will increase by one when the RRH is sent.
	       */
	      rrh.seq = riface->iface->rawsndcnt + 1;
	      /* Default is to use the same mode as the interface */
	      if(Rspfownmode == -1)
		   rrh.flags = !(riface->iface->flags & CONNECT_MODE);
	      else
		   rrh.flags = !(Rspfownmode & CONNECT_MODE);

	      bp = htonrrh(&rrh,data,&ph);
	      ++Rspf_stat.rrhout;
	      ip_send(riface->iface->addr,riface->iface->broadcast,RSPF_PTCL,
		      0,2,bp,0,0,0); /* the ttl will be decremented to 1 */
	 }
    }
}

/* This function is called whenever an RRH packet has been received or when
 * a new entry is added to the ARP table.
 */
static void
add_rspfadj(adj)
struct rspfadj *adj;
{
    struct rspfadj *oldadj, *tmp;
    struct rspfiface *riface;
    struct arp_tab *atp;
    struct lq *alp;
    int dif, origdif;

    if(adj == NULLADJ)
	return;			/* sanity but it happens... */
    /* Find the previous copy of the adjacency, if there was any */
    /* Insert the new adjacency */
    adj->next = Adjs;
    Adjs = adj;
    for(oldadj = Adjs; oldadj->next != NULLADJ; oldadj = oldadj->next)
	if(oldadj->next->addr == adj->addr) {
	    tmp = oldadj->next;
	    oldadj->next = oldadj->next->next;
	    oldadj = tmp;
	    break;
	}

    if(oldadj->addr != adj->addr || oldadj == adj)
	oldadj = NULLADJ;

    /* ARP entries give no sequence number, so save the old one */
    if(oldadj != NULLADJ) {
	 if(adj->seq == 0)
	      adj->seq = oldadj->seq;
	 if(adj->tos == 0)
	      adj->tos = oldadj->tos;	/* they give no TOS either */
    }

    switch(adj->state) {
    case RSPF_TENTATIVE:
	if(oldadj != NULLADJ) {
	     /* If the adjacency was in OK state, it will remain there.
	      * An RRH or ARP upcall can never generate an OK -> Tentative
	      * transition.
	      */
	     if(oldadj->state == RSPF_OK)
		 adj->state = RSPF_OK;
	     adj->okcnt = oldadj->okcnt;
	     /* If old state was Bad, don't announce this adjacency until
	      * it is known to be OK, to prevent announcing an adjacency
	      * with an state transition loop such as OK -> Suspect -> Bad ->
	      * Tentative -> Suspect -> Bad -> Tentative -> ... 
	      */
	     if(oldadj->state == RSPF_BAD) {
		  adj->okcnt = 0;
		  stop_timer(&oldadj->timer);
		  /* Enter Suspect state at once, there is no point in
		   * dwelling as Tentative.
		   */
		  rspfcheck(adj);
	     } else {
		  /* Inherit the old timer */
		  adj->timer.func = rspfevent;
		  adj->timer.arg = (void *) &adj->timer;
		  /* continue where the old timer is stopped */
		  adj->timer.duration = oldadj->timer.duration;
		  stop_timer(&oldadj->timer);
		  /* Set the timer to Suspectimer in the unlikely event that
		   * the timer was stopped and oldadj is not Suspect or Bad.
		   * Suspect state is dealt with further below.
		   */
		  if(dur_timer(&adj->timer) == 0L)
		       set_timer(&adj->timer,dur_timer(&Susptimer));
		  start_timer(&adj->timer);
		  set_timer(&adj->timer,dur_timer(&oldadj->timer));
	    }
	    /* We must now try to figure out from which AX.25 callsign this
	     * packet came. Looking at the ARP table may sometimes help. 
	     */
	    if(oldadj->seq != 0 && adj->seq != 0 &&
	       (riface = rtif_lookup(adj->addr)) != NULLRIFACE &&
           (atp = arp_lookup(ARP_AX25,adj->addr,riface->iface)) != NULLARP &&
	       atp->state == ARP_VALID &&
	       (alp = al_lookup(riface->iface,atp->hw_addr,0)) != NULLLQ){
		/* The wrapping of the modulus is taken into account here */
		if(oldadj->seq > (MAXINT16 - 100) && adj->seq < 100)
		    origdif = adj->seq + MAXINT16 - oldadj->seq;
		else
		    origdif = adj->seq - oldadj->seq;
		if((alp->currxcnt - adj->heard) > (MAXINT16 - 100)
		   && adj->seq < 100)
		    dif = origdif + MAXINT16 - (alp->currxcnt - adj->heard);
		else
		    dif = origdif - (alp->currxcnt - adj->heard);
		adj->heard = alp->currxcnt;	/* Update the counter */
		/* At this point, "origdif" equals the difference in sequence
		 * numbers between the two latest RRH packets, i.e. the
		 * number of AX.25 frames the station has sent during since
		 * the last RRH packet we heard. "dif" equals the number of
		 * AX.25 frames that we actually heard from that station
		 * during the same period.
		 */
		if(origdif > 0 && dif > 0)
		    /* This algorithm can be improved, see 2.1 spec */
		    adj->cost = riface->quality*2-riface->quality*dif/origdif;
	    }
	    /* Ignore any new RRH's if a pinger process is already running */
	    if(oldadj->state == RSPF_SUSPECT) {
		 if(adj->heard != 0)		/* save new heard count */
		      oldadj->heard = adj->heard;
		 oldadj->next = adj->next;	/* adj is at start of chain */
		 Adjs = oldadj;
		 stop_timer(&adj->timer);
		 free((char *)adj);
		 return;
	    }
        } else {					/* oldadj == NULLADJ */
	    rspfcheck(adj);			/* enter Suspect state */
	    /* A new adjacency may affect the routing table even though no
	     * routing updates have yet been received from it.
	     */
	    makeroutes();
	}
	break;
    case RSPF_OK:
	if(oldadj != NULLADJ) {
	    adj->okcnt += oldadj->okcnt;	/* Do these before possible */
	    stop_timer(&oldadj->timer);		/* killproc() -- KZ1F */
	    if(oldadj->state == RSPF_SUSPECT){
		killproc(oldadj->pinger);
		--Nrspfproc;			/* Bug fix - N1BEE */
	    }
	}
	else
	     makeroutes();			/* routing table may change */
	if(adj->okcnt == 1)			/* A previously unkown route */
	    goodbadnews(adj);			/* ..that is good news */
	break;
    }
    stop_timer(&oldadj->timer);		/* stop timer before free() -- KZ1F */
#ifndef KZ1F
    free((char *)oldadj);
#endif
}

/* Take appropriate action if an adjacency is Bad or Tentative */
static void
rspfcheck(adj)
struct rspfadj *adj;
{
    struct rspfadj *prev;

    for(prev = Adjs; prev != NULLADJ; prev = prev->next)
	 if(prev->next == adj)
	      break;
    switch(adj->state){
    case RSPF_OK:
	 adj->state = RSPF_TENTATIVE; 	/* note fall-thru */
    case RSPF_TENTATIVE:
	 if (Nrspfproc < RSPF_PROCMAX) {
	      Nrspfproc++;
	      adj->pinger = newproc("RSPF ping",1024,rspfping,
				    (int)adj->state,adj,NULL,0);
	      adj->state = RSPF_SUSPECT; /* The adjacency is now Suspect */
	 } else {		/* Try later */
	      set_timer(&adj->timer,dur_timer(&Susptimer));
	      start_timer(&adj->timer);
	 }
	 break;
    case RSPF_BAD:
    	 rr_delete(adj->addr);
	 adj->cost = 255;
	 if(adj->okcnt != 0)
	      goodbadnews(adj);		/* This is bad news... */
	 if(prev != NULLADJ)
	      prev->next = adj->next;	/* Unlink */
	 else
	      Adjs = adj->next;
	 stop_timer(&adj->timer);	/* just in case */
	 free((char *)adj);		/* delete the adjacency */
	 makeroutes();			/* update the routing table */
	 break;
    }
}

/* Send a ping to a suspect or tentative adjacency */
static void
rspfping(oldstate, p, v)
int oldstate;
void *p, *v;
{
    int s, fromlen, pcnt;
    struct icmp icmp;
    struct rspfadj *adj;
    struct sockaddr_in from;
    struct mbuf *bp;

    mspause(((ptol(p) & 7)+1)*1000L);	/* Pause for 1 to 8 seconds */
    adj = (struct rspfadj *) p;
    adj->timer.func = rspfevent;		/* Fill in timer values */
    adj->timer.arg = (void *) &adj->timer;
    set_timer(&adj->timer,dur_timer(&Susptimer));
    if((s = socket(AF_INET,SOCK_RAW,ICMP_PTCL)) == -1){
	--Nrspfproc;
	adj->state = oldstate;
	start_timer(&adj->timer);
	return;
    }

    fromlen = sizeof(from);
    for(pcnt=0; pcnt < Rspfpingmax; ++pcnt) {
	pingem(s,adj->addr,0,(int16)s,0);
	/* Now collect the reply */
	alarm(60 * 1000L);/* Let each ping timeout after 60 seconds */
	for(;;) {
	     if(recv_mbuf(s,&bp,0,(char *)&from,&fromlen) == -1){
		  if(errno == EALARM){ /* We timed out */
		       break;
		  }
		  alarm(0);
		  adj->state = oldstate;
		  close_s(s);
		  --Nrspfproc;
		  start_timer(&adj->timer);
		  return;
	     }
	     ntohicmp(&icmp,&bp);
	     free_p(bp);
	     if(icmp.type != ICMP_ECHO_REPLY || from.sin_addr.s_addr !=
		adj->addr || icmp.args.echo.id != s)
		  /* Ignore other people's responses */
		  continue;
	     alarm(0);
	     if(++adj->okcnt == 1)
		  goodbadnews(adj);		/* Good news */
	     close_s(s);
	     --Nrspfproc;
	     start_timer(&adj->timer);
	     adj->state = RSPF_OK;		/* Finally change state */
	     return;
	}
    }
    /* we give up, mark the adjacency as bad */
    adj->state = RSPF_BAD;
    close_s(s);
    --Nrspfproc;
    start_timer(&adj->timer);
}

/* ARP upcalls come in two flavors: When an ARP Reply has been received, we
 * know for certain that bidirectional communication is possible with the
 * particular station. But when an ARP Request is received, or if an ARP
 * entry is added manually, it has yet to be determined if the link is
 * bidirectional so iface is NULLIF in those cases.
 */
void
rspfarpupcall(addr,hardware,iface)
int32 addr;			/* Address being added to ARP table */
int16 hardware;			/* Hardware type */
struct iface *iface;		/* Interface used, if known */
{
    struct rspfadj *adj;
    struct mbuf *bp;
    struct rspfiface *riface;

    if((riface = rtif_lookup(addr)) == NULLRIFACE)
	 return;		/* Not a route to an RSPF interface */
    /* Proceed only if the ARP entry is for a hardware type that is relevant
     * for the interface onto which IP datagrams are routed.
     */
    switch(hardware) {
    case ARP_NETROM:
	 if(riface->iface->type != CL_NETROM)
	      return;
	 break;
    case ARP_AX25:
	 if(riface->iface->type != CL_AX25)
	      return;
	 break;
    case ARP_ETHER:
	 if(riface->iface->type != CL_ETHERNET)
	      return;
	 break;
    case NHWTYPES:
	 break;		/* "Any interface type is ok" type entry */
    default:
	 return;
    }
    if((adj = (struct rspfadj *)calloc(1,sizeof(struct rspfadj)))==NULLADJ)
	return;
    adj->addr = addr;
    if(iface == NULLIF)	  /* A manual ARP entry or Request, may be no-good */
	adj->state = RSPF_TENTATIVE;
    else {
	adj->state = RSPF_OK;
	adj->okcnt++;
	adj->timer.func = rspfevent;		/* Fill in timer values */
	adj->timer.arg = (void *) &adj->timer;
	set_timer(&adj->timer,dur_timer(&Susptimer));
	start_timer(&adj->timer);    
    }
    if((bp = alloc_mbuf(1+sizeof(int32)+sizeof(iface))) == NULLBUF) {
	 stop_timer(&adj->timer);
	 free((char *)adj);
	 return;
    }
    *bp->data = RSPFE_ARP;
    memcpy(bp->data + 1, (char *) &adj, sizeof(adj));
    memcpy(bp->data + 1 + sizeof(adj), (char *) &iface, sizeof(iface));
    bp->cnt = bp->size;
    enqueue(&Rspfinq,bp);
}

/* Called by "route add" command. */
void
rspfrouteupcall(addr,bits,gateway)
int32 addr;			/* Address added to routing table */
unsigned bits;			/* Significant bits in address */
int32 gateway;			/* Address of gateway station */
{
    /* We are only interested in 32 bit specific routes that use a
     * gateway. Direct routes will be discovered anyway.
     */
    if(bits != 32 || gateway == 0 || gateway == addr)
	 return;
    if(rtif_lookup(addr) == NULLRIFACE) /* not routed onto RSPF interface */
	 return;
    rspfarpupcall(addr,NHWTYPES,NULLIF); /* proceed as an "arp add" upcall */
}

/* When the suspect timer expires, we scan through the routing table for all
 * manual 32 bit specific routes through a gateway that are not an adjacency,
 * and calls rspfrouteupcall(). A similar thing is done for all manual ARP
 * entries. This will make sure that a station that was not reachable when
 * the "route add" or "arp add" command was executed will eventually be
 * discovered if it joins the network.
 */
void
rspfsuspect(t)
void *t;
{
     struct rspfadj *adj;
     struct route *rp;
     struct arp_tab *ap;
     int i;
     start_timer(&Susptimer);			/* restart the timer */
     for(i = 0; i < HASHMOD; i++)		/* Check the routing table */
	  for(rp = Routes[31][i]; rp != NULLROUTE; rp = rp->next) {
	       if((rp->flags & RTPRIVATE) || dur_timer(&rp->timer) != 0)
		    continue;	/* not this route */
	       for(adj = Adjs; adj != NULLADJ; adj = adj->next)
		    if(adj->addr == rp->target)
			 break;
	       if(adj == NULLADJ) /* it is not already an adjacency */
		    rspfrouteupcall(rp->target,32,rp->gateway);
	  }
     for(i=0; i < HASHMOD; ++i)	/* scan the ARP table */
	  for(ap = Arp_tab[i]; ap != NULLARP; ap = ap->next) {
	       if(dur_timer(&ap->timer))	/* not a manual entry */
		    continue;
	       for(adj = Adjs; adj != NULLADJ; adj = adj->next)
		    if(adj->addr == ap->ip_addr)
			 break;
	       if(adj == NULLADJ)	/* not already an adjacency */
		    rspfarpupcall(ap->ip_addr,ap->hardware,NULLIF);
	  }
}

/* This non-layered function peeks at the routing table to figure out to which
 * interface datagrams for addr will be routed. Then it returns the matching
 * rspfiface structure.
 */
static
struct rspfiface *
rtif_lookup(addr)
int32 addr;
{
    struct rspfiface *riface;
    struct route *rp;
    if((rp = rt_lookup(addr)) == NULLROUTE)
	return NULLRIFACE;
    riface = Rspfifaces;
    while(riface != NULLRIFACE){
	if(riface->iface == rp->iface)
	    return riface;
	riface = riface->next;
    }
    return NULLRIFACE;
}

/* Send good or bad news partial routing updates. A cost of 255 should be
 * interpreted as bad news by the remote station.
 */
static void
goodbadnews(adj)
struct rspfadj *adj;
{
    struct rspfnodeh nodeh;
    struct rspflinkh linkh;
    struct rspfiface *riface;
    struct rspfrouter *rr;
    struct mbuf *bp, *tbp, *wbp;
    int nodecnt = 1;
    if((riface = rtif_lookup(adj->addr)) == NULLRIFACE)
	return;
    bp = ambufw(5);
    bp->cnt = bp->size;
    *bp->data = 32; 	/* the number of significant bits in the address */
    put32(bp->data+1,adj->addr);
    linkh.horizon = riface->horizon;
    linkh.erp = riface->erp;
    linkh.cost = adj->cost;
    linkh.adjn = 1;
    tbp = htonrspflink(&linkh,bp);
    nodeh.seq = Rspfseq;
    nodeh.subseq = ++Rspfsubseq;
    nodeh.links = 1;
    for(riface = Rspfifaces; riface != NULLRIFACE; riface = riface->next) {
	  if(dup_p(&wbp,tbp,0,len_p(tbp)) != len_p(tbp)) {
	       free_p(wbp);
	       continue;
	   }
	   nodeh.addr = riface->iface->addr;
	   bp = htonrspfnode(&nodeh,wbp);
	   sendtoall(bp,1,riface);
    }
    free_p(tbp);
    /* If this is a new adjacency, then send it a routing update immediately */
    if(adj->cost == 255 || adj->okcnt != 1)
	return;
    /* When two RSPF stations learn about each others existence, one of
     * them will usually have received an RRH from the other. The one that
     * received the RRH will send the peer a routing update immediately.
     * So in the code below, if no RRH has been received (seq is 0) and no
     * routing update has yet been received, we should expect to receive a
     * routing update shortly if the adjacency is running RSPF.
     * This could fail though if two RSPF stations learn about each other
     * solely through ARP upcalls and no RRH's or Updates were exchanged
     * prior to or during the establishment of the adjacency.
     */
    if(adj->seq == 0 && rr_lookup(adj->addr) == NULLRROUTER) {
	if(adj->state != RSPF_SUSPECT)	/* running in RSPF process, give up */
	    return;
	alarm(15 * 1000);	/* wait for an Update */
	if(pwait(adj) == EALARM)
	     return;	/* still no sign of RSPF activity from the adjacency */
	alarm(0);
    }
    ++adj->okcnt;	/* we don't want to get here again */
    if((bp = makeownupdate(adj->addr,1)) == NULLBUF)
	return;
    for(rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next)
	if((tbp = makeadjupdate(get32(rr->data->data),rr)) != NULLBUF){
	     append(&bp,tbp);
	     nodecnt++;
	}
    sendupdate(bp,nodecnt,adj->addr);
}

/* This function is called whenever it is time to send a new RSPF update */
static void
sendrspf()
{
    struct rspfrouter *rr;
    struct mbuf *bp, *wbp, *tmp = NULLBUF;
    struct rspfiface *riface;
    struct rspfadj *adj;
    int nodecnt, incr = 1;

    for(nodecnt = 1, rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next)
	 if(!rr->sent)		/* don't send stale data */
	      if((bp = makeadjupdate(get32(rr->data->data),rr)) != NULLBUF){
		   append(&tmp,bp);
		   nodecnt++;
	      }
    for(riface = Rspfifaces; riface != NULLRIFACE; riface = riface->next) {
	 /* Find an address that is routed onto this interface */
	 for(adj = Adjs; adj != NULLADJ; adj = adj->next)
	      if(rtif_lookup(adj->addr) == riface)
		   break;
	 if(adj == NULLADJ)	/* no adjacency on that interface? */
	      continue;
	 if(dup_p(&wbp,tmp,0,len_p(tmp)) != len_p(tmp)) {
	      free_p(wbp);
	      continue;
	 }
	 if((bp = makeownupdate(adj->addr,incr)) != NULLBUF) {
	      incr = 0;	/* sequence number is incremented only once */
	      append(&bp,wbp);
	 }
	 else
	      break;
	 sendtoall(bp,nodecnt,riface);
    }
    free_p(tmp);
    for(rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next)
	 if(!rr->sent)		/* Mark router data as propagated */
	      ++rr->sent;
}

/* This function is used to answer "poll" messages */
static void
sendonerspf(addr,dest)
int32 addr;	/* address of station whose routing update we will make */
int32 dest;	/* address of station to send the update to */
{
    struct mbuf *bp;
    if(ismyaddr(addr)){
	if((bp = makeownupdate(dest,0)) == NULLBUF)
	    return;
	sendupdate(bp,1,dest);
	return;
    }
    if((bp = makeadjupdate(addr,NULLRROUTER)) == NULLBUF)
	return;
    sendupdate(bp,1,dest);
}
    
/* send an update to all adjacencies on an RSPF interface */
static void
sendtoall(bp,nodecnt,riface)
struct mbuf *bp;
int nodecnt;			/* number of reporting nodes in update */
struct rspfiface *riface;	/* interface to sent to */
{
     struct rspfadj *adj;
     struct mbuf *wbp;
     int broad;
     for(broad = 0, adj = Adjs; adj != NULLADJ; adj = adj->next)
	  /* If adj->seq is 0 we have never received an RRH from the
	   * adjacency, and if there is no stored routing update, then
	   * it is not known if the adjacency understands RSPF.
	   */
	  if((adj->seq != 0 || rr_lookup(adj->addr) != NULLRROUTER) &&
	     riface == rtif_lookup(adj->addr)) {
	       if((adj->tos & RELIABILITY) && !(adj->tos & DELAY)) {
		    if(dup_p(&wbp,bp,0,len_p(bp)) != len_p(bp)) {
			 free_p(wbp);
			 continue;
		    }
		    sendupdate(wbp,nodecnt,adj->addr); /* private copy */
	       }
	       else
		    ++broad;	/* send to broadcast IP address instead */
	  }
     if(broad != 0)
	  if(dup_p(&wbp,bp,0,len_p(bp)) != len_p(bp))
	       free_p(wbp);
	  else
	       sendupdate(wbp,nodecnt,riface->iface->broadcast);
     free_p(bp);
}     

/* This function sends a routing update to the adjacencies that we have
 * recevied RRH's from.
 */
static int
sendupdate(bp,nodecnt,addr)
struct mbuf *bp;	/* Full packet, except for the packet header */
int nodecnt;		/* Number of reporting nodes in the packet */
int32 addr;		/* Station to send update to */
{
    struct rspfadj *adj;
    struct mbuf *tmp;
    int tos = 0;

    /* See if we are sending to a known adjacency, in use its TOS in
     * that case.
     */
    for(adj = Adjs; adj != NULLADJ; adj = adj->next)
	 if(adj->addr == addr) {
	      tos = adj->tos;
	      break;
	 }
    if((tmp = fragmenter(bp,nodecnt,ip_mtu(addr) - IPLEN)) == NULLBUF)
	 return -1;
    while((bp = dequeue(&tmp)) != NULLBUF){
	 rspfcsum(&bp,addr);	/* Calculate the checksum */
	 ++Rspf_stat.updateout;
	 ip_send(INADDR_ANY,addr,RSPF_PTCL,INET_CTL | tos,2,bp,0,0,0);
    }
    return 0;
}

/* Fragment a large mbuf if necessary into packets of maximum mtu bytes.
 * Each packet is prepended a RSPF routing update header, without the checksum.
 */
static struct mbuf *
fragmenter(bp,nodes,mtu)
struct mbuf *bp; /* packet to send, without packet header */
int nodes;	/* The number of reporting nodes in the routing update */
int16 mtu;	/* The maximum transmission unit */
{
    struct rspfnodeh nodeh;
    struct rspflinkh linkh;
    struct rspfpacketh pkth;
    struct mbuf *tbp, *tmp, *bpq = NULLBUF;
    int n, nodecnt, linkcnt, adjcnt, nodemax, sync;
    char *cp, fragn = 1;

    if(mtu < RSPFPKTLEN + RSPFNODELEN || bp == NULLBUF) {
	 free_p(bp);
	 return NULLBUF;
    }
    ++Envelopeid;
    nodemax = nodes;		/* total number of nodes in envelope */
    nodecnt = nodes;		/* nodes left to packetize */
    linkcnt = adjcnt = 0;
#ifdef __GNUC__
    cp = 0;			/* silence warning */
#endif
    while(len_p(bp) != 0){
	n = min(mtu,len_p(bp)+RSPFPKTLEN);	/* length of this packet */
	n -= RSPFPKTLEN;
	tbp = NULLBUF;
	sync = 0;
	if(adjcnt){
	    tbp = ambufw(min(adjcnt*5,n/5*5));
	    tbp->cnt = tbp->size;
	    cp = tbp->data;
	}
	while(n > 0){
	    while(adjcnt){
		if((n -= 5) < 0)
		    break;
		pullup(&bp,cp,5);
		cp += 5;
		adjcnt--;
	    }
	    if(linkcnt && n > 0){
		if((n -= RSPFLINKLEN) < 0)
		    break;
		ntohrspflink(&linkh,&bp);
		adjcnt = linkh.adjn;
		tmp = htonrspflink(&linkh,NULLBUF);
		append(&tbp,tmp);
		tmp = ambufw(min(5*adjcnt,n/5*5));
		tmp->cnt = tmp->size;
		cp = tmp->data;
		append(&tbp,tmp);
		linkcnt--;
		continue;
	    }
	    if(nodecnt && linkcnt == 0 && n > 0){
		if((n -= RSPFNODELEN) < 0)
		    break;
		if(nodecnt == nodes)		/* Set the sync octet */
		    sync = len_p(tbp) + 4;
		ntohrspfnode(&nodeh,&bp);
		linkcnt = nodeh.links;
		tmp = htonrspfnode(&nodeh,NULLBUF);
		append(&tbp,tmp);
		nodecnt--;
	    }
	}
	pkth.version = RSPF_VERSION;	/* The version number */
	pkth.type = RSPF_FULLPKT;	/* The packet type */
	pkth.fragn = fragn++;		/* The fragment number */
	pkth.fragtot = 0;		/* The total number of fragments */
	pkth.csum = 0;			/* The checksum */
	pkth.sync = sync < 256 ? sync : 0;	/* The sync octet */
	pkth.nodes = nodemax;		/* The number of nodes in envelope */
	pkth.envid = Envelopeid;	/* The envelope-ID */
	tmp = htonrspf(&pkth,tbp);	/* add packet header */
	enqueue(&bpq,tmp);		/* add packet to chain */
	nodes = nodecnt;		/* number of nodes left */
    }
    free_p(bp);
    for(tbp = bpq; tbp != NULLBUF; tbp = tbp->anext)
	*(tbp->data + 3) = len_q(bpq);	/* Set the fragment total counter */
    return bpq;
}

/* Calculate the checksum on an RSPF routing update packet */
static void
rspfcsum(bpp,dest)
struct mbuf **bpp;
int32 dest;
{
    struct pseudo_header ph;
    int16 checksum;
    ph.length = len_p(*bpp);
    ph.source = locaddr(dest);
    ph.dest = dest;
    ph.protocol = RSPF_PTCL;
    if((checksum = cksum(&ph,*bpp,ph.length)) == 0)
	checksum = 0xffffffff;
    /* This assumes that the checksum really is at this position */
    put16((*bpp)->data+4,checksum);
}

/* This function creates our own routing update and returns it in an mbuf */
struct mbuf *
makeownupdate(dest,new)
int32 dest;		/* Address of a station that will get this update */
int new;		/* True if the sequence number should be incremented */
{
    struct rspfadj *adj;
    struct rspflinkh linkh;
    struct rspfnodeh nodeh;
    struct rspfiface *riface, rifdefault;
    struct mbuf *bp = NULLBUF, *tbp, *tmp;
    struct route *rp;
    int i, adjcnt, lnkcnt, bits;
    int32 prev, low, cur;

    /* Set default values to apply to non-RSPF interfaces */
    rifdefault.horizon = 32;
    rifdefault.erp = 0;
    rifdefault.quality = 0;
    /* Our adjacencies has to be sorted into groups of the same horizon,
     * ERP factor and cost. This is done by combining these numbers into a
     * single one, modulo 256 and take the lowest number first.
     */
    low = 0;
    lnkcnt = 0;
    for(;;){
	prev = low;
	low = 255*65536L+255*256+255;
	for(adj = Adjs; adj != NULLADJ; adj = adj->next)
	     /* Include all adjacecies that have been or are in OK state
	      * in the update. Bad adjacencies are also included to give
	      * them a chance to recover. Hopelessly Bad adjacencies are
	      * eventually deleted elsewhere.
	      */
	    if(adj->okcnt != 0 && (riface = rtif_lookup(adj->addr)) !=
	       NULLRIFACE) {
		cur = riface->horizon*65536L+riface->erp*256+adj->cost;
		if(cur > prev && cur < low)
		    low = cur;
	    }
	/* Add any manual public, 1-31 bit specific routes.
	 * Use the route metric only if it is greater than the default
	 * quality to lessen a possible "wormhole" effect.
	 */
	for(bits = 1; bits <= 31; bits++)
	    for(i = 0; i < HASHMOD; i++)
		for(rp = Routes[bits-1][i]; rp != NULLROUTE; rp = rp->next)
		     if(!(rp->flags & RTPRIVATE) && !dur_timer(&rp->timer)) {
			 if((riface = rtif_lookup(rp->target)) == NULLRIFACE)
			        riface = &rifdefault;
			 cur = riface->horizon*65536L+riface->erp*256+
				(rp->metric > riface->quality ? rp->metric :
				riface->quality);
			if(cur > prev && cur < low)
			    low = cur;
		     }
	/* Add any 32 bit routes on interfaces not using RSPF */
	for(i = 0; i < HASHMOD; i++)
	     for(rp = Routes[31][i]; rp != NULLROUTE; rp = rp->next)
		  if(!(rp->flags & RTPRIVATE) && rtif_lookup(rp->target)
		     == NULLRIFACE) {
		       cur = rifdefault.horizon*65536L+rifdefault.erp*256+
			    (rp->metric > rifdefault.quality ? rp->metric :
			     rifdefault.quality);
		       if(cur > prev && cur < low)
			    low = cur;
		  }
	/* Add the default route */
	if((rp = rt_blookup(0,0)) != NULLROUTE && !(rp->flags & RTPRIVATE) &&
	   !dur_timer(&rp->timer)) {
	     if((riface = rtif_lookup(0)) == NULLRIFACE)
		  riface = &rifdefault;
	     cur = riface->horizon*65536L+riface->erp*256+
		(rp->metric > riface->quality ? rp->metric : riface->quality);
	     if(cur > prev && cur < low)
		  low = cur;
	}
	if(low == 255*65536L+255*256+255) /* All done */
	    break;
	/* now start adding the routes */
	adjcnt = 0;
	tbp = NULLBUF;
	for(adj = Adjs; adj != NULLADJ; adj = adj->next)
	    if(adj->okcnt != 0 && (riface = rtif_lookup(adj->addr)) !=
	       NULLRIFACE)
		if(riface->horizon*65536L+riface->erp*256+adj->cost == low){
		    pushadj(&tbp,adj->addr,32);
		    adjcnt++;
		}
	for(bits = 1; bits <= 31; bits++)
	    for(i = 0; i < HASHMOD; i++)
		for(rp = Routes[bits-1][i]; rp != NULLROUTE; rp = rp->next)
		     if(!(rp->flags & RTPRIVATE) && !dur_timer(&rp->timer)){
			if((riface = rtif_lookup(rp->target)) == NULLRIFACE)
			       riface = &rifdefault;
			/* Manually entered local routes only */
			if(riface->horizon*65536L+riface->erp*256+
			   (rp->metric > riface->quality ? rp->metric :
			   riface->quality) == low){
				pushadj(&tbp,rp->target,bits);
				adjcnt++;
			}
		     }
	for(i = 0; i < HASHMOD; i++)	/* 32 bit specific routes */
	     for(rp = Routes[31][i]; rp != NULLROUTE; rp = rp->next)
		  if(!(rp->flags & RTPRIVATE) && rtif_lookup(rp->target)
		     == NULLRIFACE)
		       if(rifdefault.horizon*65536L+rifdefault.erp*256+
			  (rp->metric > rifdefault.quality ? rp->metric :
			   rifdefault.quality) == low){
			    pushadj(&tbp,rp->target,bits);
			    adjcnt++;
		       }
	/* Add the default route */
	if((rp = rt_blookup(0,0)) != NULLROUTE && !(rp->flags & RTPRIVATE) &&
	   !dur_timer(&rp->timer)) {
	     if((riface = rtif_lookup(0)) == NULLRIFACE)
		  riface = &rifdefault;
	     if(riface->horizon*65536L+riface->erp*256+ (rp->metric > 
		riface->quality ? rp->metric : riface->quality) == low){
		  pushadj(&tbp,0,0);
		  adjcnt++;
	     }
	}
	if(adjcnt != 0){
	    /* Prepend the link header */
	    linkh.horizon = ((low >> 16) & 255);/* Horizon value */
	    linkh.erp = ((low >> 8) & 255);	/* ERP factor */
	    linkh.cost = (low & 255);		/* Link cost */
	    linkh.adjn = adjcnt;		/* Number of adjacencies */
	    tmp = htonrspflink(&linkh,tbp);
	    append(&bp,tmp);
	    lnkcnt++;
	}
    }
    /* Prepend the node header */
    if(lnkcnt != 0){
	/* Set our address to the IP address used on the destinations
	 * interface.
	 */
	if(dest == INADDR_ANY || (riface = rtif_lookup(dest)) == NULLRIFACE)
	     nodeh.addr = Ip_addr;
	else
	     nodeh.addr = riface->iface->addr;
	if(new){	/* increase sequence number, clear subseq. number */
	    if(Rspfseq == 32768 - 2 || Rspfseq == -32768 + 1)
		 Rspfseq = 0;			/* wrap around */
	    else
		 ++Rspfseq;
	    Rspfsubseq = 0;
	}
	nodeh.seq = Rspfseq;
	nodeh.subseq = 0;
	nodeh.links = lnkcnt;
	return htonrspfnode(&nodeh,bp);
    }
    else {
	free_p(bp);
	return NULLBUF;
    }
}
/* Prepends an adjacency to bpp. Allocates bpp in large chunk for efficency */
static void
pushadj(bpp,addr,bits)
struct mbuf **bpp;
int32 addr;
int bits;
{
     if(bpp == NULLBUFP)
	  return;
     if(*bpp == NULLBUF) {
	  *bpp = ambufw(60);		/* good for 12 adjacencies */
	  (*bpp)->data += 55;
	  (*bpp)->cnt = 5;
     }
     else
	  *bpp = pushdown(*bpp,5);
     *(*bpp)->data = bits;
     put32((*bpp)->data+1,addr);
}

/* This function returns the latest routing update in network fromat from
 * the adjacency denoted by addr.
 */
static struct mbuf *
makeadjupdate(addr,rr)
int32 addr;
struct rspfrouter *rr;	/* pointer to stored routing entry, if known */
{
    struct mbuf *tmp, *tmp2, *tmp3, *bp = NULLBUF;
    struct rspfnodeh nodeh;
    struct rspflinkh linkh;
    int linkcnt = 0;
    if(rr == NULLRROUTER && (rr = rr_lookup(addr)) == NULLRROUTER)
	return NULLBUF;
    if(dup_p(&tmp,rr->data,0,len_p(rr->data)) != len_p(rr->data)) {
	 free_p(tmp);
	 return NULLBUF;
    }
    ntohrspfnode(&nodeh,&tmp);		     /* Get the node header */
    while(nodeh.links--){
	ntohrspflink(&linkh,&tmp);
	/* Decrement and check the horizon value */
	if(--linkh.horizon > 0){
	    /* Duplicate the adjacencies */
	    if(dup_p(&tmp2,tmp,0,5*linkh.adjn) != 5*linkh.adjn){
		free_p(tmp);
		free_p(tmp2);
		free_p(bp);
		return NULLBUF;
	    }
	    /* Prepend the link header */
	    tmp3 = htonrspflink(&linkh,tmp2);
	    append(&bp,tmp3);
	    linkcnt++;
	}
	pullup(&tmp,NULLCHAR,5*linkh.adjn); /* Skip the adjacencies */
    }
    free_p(tmp);
    if(linkcnt == 0){	 	/* No links at all? */
	free_p(bp);
	return NULLBUF;
    }
    nodeh.subseq = rr->subseq;
    nodeh.links = linkcnt;
    /* Prepend the node header */
    return htonrspfnode(&nodeh,bp);
}

/* Returns 1 if sequence number a is newer than b. Sequence numbers start
 * at -32768 + 1 and then continues with 0 and the positive integer numbers
 * until reaching 32768 - 2 after which they continue with 0.
 * Algorithm taken from RFC-1131 but fixed bug when a or b is 0.
 */
static int
isnewer(a,b)
short a,b;
{
     if((b < 0 && a > b) ||
	(a >= 0 && b >= 0 &&	/* bug corrected here */
	 (((32768 - 1)/2 > (a-b) && (a-b) > 0) ||
	  (a-b) < -(32768 - 1)/2)))
	  return 1;
     return 0;
}
     
/* Reassemble possibly fragmented packets into a single large one */
static struct mbuf *
rspfreasm(bp,rph,addr)
struct mbuf *bp;	  /* Routing update packet without packet header */
struct rspfpacketh *rph;  /* Packet header */
int32 addr;		  /* Address of station we got the packet from */
{
    union rspf rspf;
    struct rspfreasm *re, *rtmp;
    struct mbuf *tbp, *bp1, *bp2;
    for(re = Rspfreasmq; re != NULLRREASM; re = re->next)
	if(re->addr == addr){	/* found another fragment */
	    if(dup_p(&tbp,re->data,0,RSPFPKTLEN) != RSPFPKTLEN) {
		 free_p(tbp);
		 free_p(bp);
		 return NULLBUF;
	    }
	    ntohrspf(&rspf,&tbp);	/* get its packet header */
	    if(rph->envid != rspf.pkthdr.envid) {
		 del_reasm(re);		/* an obsolete entry, delete it */
		 break;
	    }
	    /* Now try to find a place where this fragment fits in the chain */
	    bp1 = re->data;
	    bp2 = NULLBUF;
	    while(rph->fragn > rspf.pkthdr.fragn && bp1->anext != NULLBUF){
		bp2 = bp1;
		bp1 = bp1->anext;
		if(dup_p(&tbp,bp1,0,RSPFPKTLEN) != RSPFPKTLEN) {
		     free_p(bp);
		     free_p(tbp);
		     return NULLBUF;
		}
		ntohrspf(&rspf,&tbp);
	    }
	    if(rspf.pkthdr.fragn == rph->fragn) {
		 free_p(bp);
		 return NULLBUF;	/* We already had this one */
	    }
	    bp = htonrspf(rph,bp);	/* Put the packet header back on */
	    /* Insert the fragment at the right place in the chain */
	    if(rph->fragn > rspf.pkthdr.fragn){
		bp1->anext = bp;
		bp->anext = NULLBUF;
	    }
	    else {
		if(bp2 != NULLBUF)
		    bp2->anext = bp;
		else
		    re->data = bp;
		bp->anext = bp1;
	    }
	    if(len_q(re->data) == rspf.pkthdr.fragtot){ 
		bp1 = NULLBUF;			/* we have all the fragments */
		while((bp2 = dequeue(&re->data)) != NULLBUF){
		    pullup(&bp2,NULLCHAR,RSPFPKTLEN); /* strip the headers */
		    append(&bp1,bp2);		/* and form a single packet */
		}
		del_reasm(re);
		stop_timer(&Rspfreasmt);
		reasmtimeout(NULL);	/* restarts timer if necessary */
		return bp1;		/* return the completed packet */
	    }
	    re->time = secclock();		/* Update the timestamp */
	    goto timstart;		/* We have to wait for fragments */
	}
    /* At this point we know that there is no matching entry in the
       reassembly queue (any more) */
    if(rph->fragtot == 1)	/* Simple case, an un-fragmented packet */
	return bp;
    tbp = htonrspf(rph,bp);	/* Put the packet header back on */
    rtmp = (struct rspfreasm *) callocw(1,sizeof(struct rspfreasm));
    /* The values are filled in */
    rtmp->addr = addr;
    rtmp->time = secclock();
    rtmp->data = tbp;
    rtmp->next = Rspfreasmq;
    Rspfreasmq = rtmp;
 timstart:					/* Start the timer if needed */
    if(!run_timer(&Rspfreasmt)){
	Rspfreasmt.func = reasmtimeout;
	Rspfreasmt.arg = NULL;
	set_timer(&Rspfreasmt,RSPF_RTIME*1000L); /* The reassembly timeout */
	start_timer(&Rspfreasmt);
    }
    return NULLBUF;
}

/* Delete a reassembly descriptor from the queue */
static void
del_reasm(re)
struct rspfreasm *re;
{
    struct rspfreasm *r, *prev = NULLRREASM;
    for(r = Rspfreasmq; r != NULLRREASM; prev = r, r = r->next)
	if(r == re){
	    free_q(&re->data);
	    if(prev != NULLRREASM)
		prev->next = re->next;
	    else
		Rspfreasmq = re->next;
	    free((char *)re);
	    break;
	}
}

/* When the reassembly timer times out, this function tries to make use of
 * any fragments in the reassembly queue.
 */
static void
reasmtimeout(t)
void *t;
{
    union rspf rspf;
    struct rspfreasm *re;
    struct mbuf *bp, *tbp;
    int last = 0;
    int32 low;
    re = Rspfreasmq;
    while(re != NULLRREASM)
	if((secclock() - re->time) >= RSPF_RTIME){
	    /* Try to use what we have */
	    bp = NULLBUF;
	    while((tbp = dequeue(&re->data)) != NULLBUF){
		ntohrspf(&rspf,&tbp);
		if(rspf.pkthdr.fragn != (last+1)){  /* a missing fragment */
		    if(bp != NULLBUF)
			update_in(bp,re->addr);
		    bp = NULLBUF;
		    if(rspf.pkthdr.sync != 0)
			pullup(&tbp,NULLCHAR,rspf.pkthdr.sync - 4);
		    else {	/* no sync possible in this fragment */
			 free_p(tbp);
			 continue;
		    }
		}
		append(&bp,tbp);
		last = rspf.pkthdr.fragn;
	    }
	    if(bp != NULLBUF)
		update_in(bp,re->addr);
	    del_reasm(re);
	    re = Rspfreasmq;	/* start over again */
        }
	else
	     re = re->next;
    /* Find the oldest fragment and restart the reassembly timer */
    low = 0;
    for(re = Rspfreasmq; re != NULLRREASM; re = re->next)
	if(re->time < low || low == 0)
	    low = re->time;
    if(low){
	/* KF8NH 1993.01.17: clock() on below line changed to secclock() */
	set_timer(&Rspfreasmt,RSPF_RTIME*1000L - secclock() + low);
	if(dur_timer(&Rspfreasmt) > 0) /* just to be safe */
	    start_timer(&Rspfreasmt);
    }
}

/* Handle incoming routing updates (a reassembled envelope) */
static void
update_in(bp,addr)
struct mbuf *bp;	/* Reassembled data packet, without packet header */
int32 addr;		/* Senders address (in host order) */
{
    struct rspfnodeh nodeh;
    struct rspflinkh linkh;
    struct rspfadj *adj;
    struct mbuf *tbp, *tmp, *b;
    int linkcnt = 0, adjcnt = 0;
    int16 offset = 0;
    tbp = b = NULLBUF;
    /* Check to see if the sender is an adjacency */
    for(adj = Adjs; adj != NULLADJ; adj = adj->next)
	 if(adj->addr == addr)
	      break;
    /* One may argue that updates from non-adjacencies should not be
     * accepted since they will not contribute to the routing table.
     * But it might happen that the sender will very shortly become an
     * adjacency, and then its routing update will come handy. By increasing
     * Keeprouter, routing updates from disjoint routers will not be not be
     * purged when makeroutes() is called this time.
     */
    if(adj == NULLADJ) {
	 ++Rspf_stat.noadjupdate;
	 Keeprouter += 2;
    }
    else
	psignal(adj,1);		/* alert anyone waiting for the update */
    while(offset < len_p(bp)){
	if(adjcnt){
	    if(dup_p(&tmp,bp,offset,5) == 5){
		append(&tbp,tmp);
		offset += 5;
		adjcnt--;
		continue;
	    }
	    else break;
	}
	if(tbp != NULLBUF){
	    tmp = htonrspflink(&linkh,tbp);
	    append(&b,tmp);
	    tbp = NULLBUF;
	}
	if(linkcnt){
	    if(dup_p(&tbp,bp,offset,RSPFLINKLEN) == RSPFLINKLEN){
		ntohrspflink(&linkh,&tbp);
		adjcnt = linkh.adjn;
		offset += RSPFLINKLEN;
		linkcnt--;
		continue;
	    }
	    else
		break;
	}
	if(b != NULLBUF){
	    tmp = htonrspfnode(&nodeh,b);
	    node_in(tmp,addr,1);	 /* a full router update */
	    b = NULLBUF;
	}
	if(dup_p(&tmp,bp,offset,RSPFNODELEN) == RSPFNODELEN){
	    ntohrspfnode(&nodeh,&tmp);
	    linkcnt = nodeh.links;
	    offset += RSPFNODELEN;
	}
	else {
	     free_p(bp);
	     free_p(tmp);
	     return;
	}
    }
    if(tbp != NULLBUF){
	/* adjust the adjacency counter in the link header */
	linkh.adjn -= adjcnt;
	tmp = htonrspflink(&linkh,tbp);
	append(&b,tmp);
    }
    /* adjust the link counter in the node header */
    nodeh.links -= linkcnt;
    tmp = htonrspfnode(&nodeh,b);
    free_p(bp);
    if(linkcnt || adjcnt)
	node_in(tmp,addr,0); 	/* a partial router update */
    else
	node_in(tmp,addr,1);
}
	
static void
node_in(bp,addr,full)
struct mbuf *bp;	/* A single update, starting with the node header */
int32 addr;		/* Address of station we got packet from */
int full;		/* False if we got a partial update */
{
    struct mbuf *tbp;
    struct rspfnodeh nodeh, rnodeh;
    struct rspfrouter *rr;
    if(dup_p(&tbp,bp,0,RSPFNODELEN) != RSPFNODELEN) {
	 free_p(bp);
	 free_p(tbp);
	 return;
    }
    ntohrspfnode(&nodeh,&tbp);
    if(ismyaddr(nodeh.addr)){
	/* If another station thinks our routing update sequence number is
	 * larger than it really is, this might be because we have had
	 * a fast system reset and routing updates from the old "epoch"
	 * are still present in the network.
	 */
	if(isnewer(nodeh.seq,Rspfseq)) {
	    Rspfseq = nodeh.seq + 1;		  	/* Catch up */
	    if(nodeh.seq == 32768 - 2 || nodeh.seq == -32768 + 1)
		 Rspfseq = 0;				/* Wrap around */
	    sendonerspf(nodeh.addr,addr); /* Send him the latest packet */
	}
	free_p(bp); 		/* We already know our own adjacencies! */
	return;
    }
    if((rr = rr_lookup(nodeh.addr)) != NULLRROUTER) {
	if(dup_p(&tbp,rr->data,0,RSPFNODELEN) != RSPFNODELEN) {
	    free_p(bp);
	    free_p(tbp);
	    return;
        }
	ntohrspfnode(&rnodeh,&tbp);
	if(nodeh.seq == rnodeh.seq && nodeh.subseq <= (unsigned) rr->subseq){
	    free_p(bp);
	    return;	/*  We already have this one */
	}
	if(isnewer(rnodeh.seq,nodeh.seq)){
	    /* Send him the latest packet */
	    sendonerspf(nodeh.addr,addr);
	    free_p(bp);
	    ++Rspf_stat.oldreport;
	    return;
	}
	if(nodeh.subseq > (unsigned) rr->subseq && nodeh.seq == rnodeh.seq){
	    rr->subseq = nodeh.subseq;
	    partialupdate(rr,bp);
	    makeroutes();
	    return;
	}
	if(isnewer(nodeh.seq,rnodeh.seq) && !full){
	    partialupdate(rr,bp);
	    makeroutes();
	    /* Send a "poll" packet */
	    --nodeh.seq;
	    nodeh.subseq = 0;
	    nodeh.links = 0;
	    tbp = htonrspfnode(&nodeh,NULLBUF);
	    sendupdate(tbp,1,addr);
	    ++Rspf_stat.outpolls;
	    return;
	}
    }
    else {
	rr = (struct rspfrouter *) callocw(1,sizeof(struct rspfrouter));
	rr->next = Rspfrouters;
	Rspfrouters = rr;
    }
    free_p(rr->data);
    rr->data = bp;
    rr->subseq = nodeh.subseq;
    rr->time = secclock();
    rr->sent = 0;
    makeroutes();
    return;
}

/* Return the matching RSPF route entry for addr (in host order) */
static struct rspfrouter *
rr_lookup(addr)
int32 addr;
{
    struct rspfrouter *rr;
    for(rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next)
	/* this assumes that the first word of the header is the address */
	if(rr->data != NULLBUF && get32(rr->data->data) == addr)
	    return rr;
    return NULLRROUTER;
}

/* Delete the route entry for address addr */
static void
rr_delete(addr)
int32 addr;
{
    struct rspfrouter *rr, *prev = NULLRROUTER;
    for(rr = Rspfrouters; rr != NULLRROUTER; prev = rr, rr = rr->next)
	/* this assumes that the first word of the header is the address */
	if(rr->data != NULLBUF && get32(rr->data->data) == addr) {
	     if(prev != NULLRROUTER)
		  prev->next = rr->next;
	     else
		  Rspfrouters = rr->next;
	     free_p(rr->data);
	     free((char *)rr);
	     return;
	}
}

/* Handle incoming partial routing updates. Adjacencies from bp will be
 * merged into rr->data
 */
static void
partialupdate(rr,bp)
struct rspfrouter *rr; 	/* current node entry in routing table */
struct mbuf *bp;	/* data packet, starting with node header */
{
    struct rspflinkh linkh, rlinkh;
    struct rspfnodeh rnodeh;
    struct mbuf *wbp, *tbp, *tmp, *b;
    int adjcnt = 0, radjcnt, rlinkcnt = 0, bits, rbits, added = 0;
    int32 addr, raddr;

    rlinkh.adjn = 0;
    rr->time = secclock();
    rr->sent = 0;
    /* Make a working copy of the stored routing update */
    if(dup_p(&wbp,rr->data,0,len_p(rr->data)) != len_p(rr->data)) {
	 free_p(wbp);
	 free_p(bp);
	 return;
    }
    ntohrspfnode(&rnodeh,&wbp);
    pullup(&bp,NULLCHAR,RSPFNODELEN);	/* Strip off the node header */
    while(len_p(bp) > 0)
	if(adjcnt == 0) {
	     if(ntohrspflink(&linkh,&bp) == -1) {
		  free_p(wbp);
		  free_p(bp);
		  return;
	     }
	     adjcnt = linkh.adjn;
	}
	else {
	    bits = PULLCHAR(&bp);	/* get one adjacency to merge */
	    if(pullup(&bp,(char *)&addr,4) != 4) {
		 free_p(wbp);
		 free_p(bp);
		 return;
	    }
	    addr = get32((char *)&addr); /* convert to host order */
	    --adjcnt;
	    radjcnt = 0;
	    b = tbp = NULLBUF;
	    for(;;) {			/* search through stored update */
		if(radjcnt == 0 || len_p(wbp) == 0) {
		     if(tbp != NULLBUF){
			  rlinkh.adjn -= radjcnt;
			  tmp = htonrspflink(&rlinkh,tbp);
			  ++rlinkcnt;
			  append(&b,tmp);
			  tbp = NULLBUF;
		     }
		     if(len_p(wbp) == 0)
			  break;
		}
		if(radjcnt == 0) {
		     ntohrspflink(&rlinkh,&wbp);
		     radjcnt = rlinkh.adjn;
		     if(rlinkh.horizon == linkh.horizon && rlinkh.cost ==
			linkh.cost && rlinkh.erp == linkh.erp) {
			  pushadj(&tbp,addr,bits);
			  ++rlinkh.adjn;
			  added = 1;
		     }
		}
		else {
		    rbits = PULLCHAR(&wbp);
		    raddr = pull32(&wbp);
		    --radjcnt;
		    if(bits != rbits || addr != raddr)
			pushadj(&tbp,raddr,rbits);	/* Put it back */
		    else
			 --rlinkh.adjn;	/* deleted one adjacency */
	        }
	    }
	    wbp = b;	/* wbp now keeps link headers and adjacencies */
	    if(linkh.cost < 255 && !added){ /* Append the new link */
		++rnodeh.links;		 /* We will add one extra link */
		tmp = ambufw(5);
		*tmp->data = bits;
		put32(tmp->data+1,addr);
		tmp->cnt = tmp->size;
		tbp = htonrspflink(&linkh,tmp);
		append(&wbp,tbp);
	    }
	    added = 0;
        }
   free_p(rr->data);
   rnodeh.links = rlinkcnt;
   rr->data = htonrspfnode(&rnodeh,wbp);
}

/* The shortest path first algorithm */
static void
makeroutes()
{
    int bits, i, low, adjcnt;
    struct mbuf *bp;
    struct route *rp, *rp2, *saved[HASHMOD];
    struct rspfadj *adj, *lowadj, *gateway;
    char *lowp, *r;
    int32 lowaddr;
    struct rspflinkh linkh;
    struct rspfrouter *rr, *rrprev;

#ifdef __GNUC__
    gateway = 0;		/* avoid "uninitialized" warning */
#endif
    if(Keeprouter)	/* if false, purge unreachable router entries */
	 --Keeprouter;
    /* Before we change anything in the routing table, we have to save
     * each local adjacencies riface pointer
     */
    for(adj = Adjs; adj != NULLADJ; adj = adj->next)
	adj->scratch = (void *) rtif_lookup(adj->addr);
    /* Remove all non-manual routes */
    for(bits = 1; bits <= 32; bits++)
	for(i = 0; i < HASHMOD; i++)
        for(rp = Routes[bits-1][i]; rp != NULLROUTE; rp = rp2) {
            rp2 = rp->next;         /* BIG BUG FIX -- sm6rpz */
            if(dur_timer(&rp->timer) != 0)
                rt_drop(rp->target,(unsigned)bits);
            /* rp will be undefined here if(dur_timer(&rp->timer) */
        }
		    rt_drop(rp->target,(unsigned)bits);

    if((rp = rt_blookup(0,0)) != NULLROUTE && dur_timer(&rp->timer) != 0)
	 rt_drop(0,0);	/* delete non-manual default route */

    /* Temporarily remove all 32-bit specific manual routes. This will make
     * it possible to prevent loops in findlowroute()
     */
    for(i = 0; i < HASHMOD; i++) {
	saved[i] = Routes[31][i];
	Routes[31][i] = NULLROUTE;
    }

    for(;;) {
	lowadj = NULLADJ;
	lowp = NULLCHAR;
	low = 255;
	for(adj = Adjs; adj != NULLADJ; adj = adj->next){
	   if(adj->scratch == NULL)
		continue;		/* skip unreachable adjacency */
	    if(!adj->added){
		if(adj->cost <= low){
		    low = adj->cost;
		    lowadj = adj;
		    lowp = NULLCHAR;
		}
	    }
	    else
		if((r = findlowroute(adj->addr,&low,adj->cost,&lowaddr,&bits))
		  != NULLCHAR) {
		    lowp = r;
		    gateway = adj;
		    lowadj = NULLADJ;
	        }
	}
	if(lowadj != NULLADJ){
	    lowadj->added++;
	    rp = rt_add(lowadj->addr,32,0,
		   ((struct rspfiface *)lowadj->scratch)->iface,
		   (int32)lowadj->cost,0,0);
	    /* set the timer to a dummy value. This makes it possible to
	     * distinguish between manual and RSPF-generated routes.
	     * The timer is never started however since RSPF handles the
	     * expiration of routes itself.
	     */
	    set_timer(&rp->timer,MSPTICK);
	    continue;
	}
	if(lowp != NULLCHAR){
	    /* Check if we already have this one */
	    rp = rt_blookup(lowaddr,(unsigned)bits);
	    if((rp == NULLROUTE || (rp != NULLROUTE && 
			rp->metric > (int32) low)) && !ismyaddr(lowaddr)) {
		 /* This is a new route, or a route with strict lower cost than
		  * the previous route (possible only if it was manual)
		  */
		rp = rt_add(lowaddr,(unsigned)bits,gateway->addr,
		       ((struct rspfiface *)gateway->scratch)->iface,
		       (int32)low,0,0);
		set_timer(&rp->timer,MSPTICK); /* a dummy value */
	    }
	    *lowp |= 128; /* mark the route as added in any case */
	}
	else
	    break; /* no more routes */
    }

    /* Add the saved 32 bit routes, if there isn't now a better route */
    for(i = 0; i < HASHMOD; i++) {
	rp = saved[i];
	while(rp != NULLROUTE) {
	     rp2 = rt_blookup(rp->target,32);
	     if(rp2 == NULLROUTE || (rp2 != NULLROUTE && rp2->metric >= rp->metric)) {
		  rp2 = rt_add(rp->target,32,rp->gateway,rp->iface,rp->metric,
			       0,rp->flags & RTPRIVATE);
		  rp2->uses = rp->uses;
	     }
	     rp2 = rp->next;
	     stop_timer(&rp->timer); /* Stop timer before free() -- KZ1F */
#ifndef KZ1F
	     free((char *)rp);
#endif
	     rp = rp2;
	}
    }

    /* Reset all flags */
    for(adj = Adjs; adj != NULLADJ; adj = adj->next) {
	adj->added = 0;
	adj->scratch = NULL;
    }

    for(rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next){
	i = len_p(rr->data) - RSPFNODELEN;
	/* jump past the node header */
	if(dup_p(&bp,rr->data,RSPFNODELEN,i) != i) {
	     free_p(bp);
	     continue;
	}
	adjcnt = 0;
	while(i > 0){
	    if(adjcnt){
		if(!Keeprouter && (*bp->data & 128) == 0) {
		     /* This router has an adjacency that was not added. That
		      * means that the router is unreachable. Mark the
		      * stored routing update for deletion.
		      */
		     free_p(bp);
		     free_p(rr->data);
		     rr->data = NULLBUF;	/* indicates disposal */
		     break;
		}
		*bp->data &= ~128;	/* Clear the "added" bit */
		pullup(&bp,NULLCHAR,5);
		i -= 5;
		--adjcnt;
		continue;
	    }
	    ntohrspflink(&linkh,&bp);
	    adjcnt = linkh.adjn;
	    i -= RSPFLINKLEN;
        }
    }

    if(Keeprouter)	/* nothing more to do */
	 return;
    /* Delete any routers that were discovered as being unreachable */
    rrprev = NULLRROUTER;
    rr = Rspfrouters;
    for(;;) {
	 for(rrprev = NULLRROUTER, rr = Rspfrouters; rr != NULLRROUTER;
	     rrprev = rr, rr = rr->next)
	      if(rr->data == NULLBUF) {
		   if(rrprev != NULLRROUTER)
			rrprev->next = rr->next;
		   else
			Rspfrouters = rr->next;
		   free((char *)rr);
		   break;
	      }
	 if(rr == NULLRROUTER)
	      break;
    }
}

/* Find a route from addr with the lowest cost. Returns a pointer to the
 * buffer that keeps the significant bit count of the selected route.
 */
static char *
findlowroute(addr,low,add,resaddr,resbits)
int32 addr;			/* The node whose routes will be examined */
int *low;			/* Lowest cost so far */
int add;			/* Cost of this node */
int32 *resaddr;			/* Resulting route stored here */
int *resbits;			/* Significant bits of resulting route */
{
    struct mbuf *bp;
    struct rspfrouter *rr;
    struct rspflinkh linkh;
    struct route *rp;
    char *r, *retval = NULLCHAR;
    int adjcnt = 0;

    linkh.cost = 0;
    if((rr = rr_lookup(addr)) == NULLRROUTER)
	return NULLCHAR;
    if((rp = rt_blookup(addr,32)) != NULLROUTE && rp->metric < add)
	 return NULLCHAR;	/* already added this one, no loops thanks */
    if(dup_p(&bp,rr->data,RSPFNODELEN,len_p(rr->data) - RSPFNODELEN) !=
       len_p(rr->data) - RSPFNODELEN) {
	 free_p(bp);
	 return NULLCHAR;
    }
    while(len_p(bp) > 0){
	if(adjcnt){
	    if(*bp->data & 128) {
		(void) PULLCHAR(&bp);
		if((r = findlowroute(pull32(&bp),low,add+linkh.cost,resaddr,
		  resbits)) != NULLCHAR)
		     retval = r;
	    }
	    else {
		*low = add + linkh.cost;
		retval = bp->data;
		*resbits = PULLCHAR(&bp);
		*resaddr = pull32(&bp);
		pullup(&bp,NULLCHAR,5*(adjcnt-1));
		adjcnt = 1;	/* No need to check the rest of this link */
	    }
	    --adjcnt;
	    continue;
	}
	ntohrspflink(&linkh,&bp);
	if((add + linkh.cost) <= *low)
	    adjcnt = linkh.adjn;
	else
	    pullup(&bp,NULLCHAR,5*linkh.adjn);
    }
    return retval;
}

#ifndef	AX25
/*
 * Dummy stub for RSPF if AX25 is not configured.
 */
static struct lq *
al_lookup(ifp,addr,sort)
struct iface *ifp;
char *addr;
int sort;
{
	return NULLLQ;
}
#endif	/* AX25 */

#endif /* RSPF */
