home *** CD-ROM | disk | FTP | other *** search
/ The Pier Shareware 6 / The_Pier_Shareware_Number_6_(The_Pier_Exchange)_(1995).iso / 024 / psi110g.zip / RSPF.C < prev    next >
C/C++ Source or Header  |  1994-04-17  |  69KB  |  1,893 lines
  1. /*           RSPF - Radio Shortest Path First
  2.  * This code may be used for non-commercial purposes only.
  3.  *          Anders Klemets SM0RGV
  4.  * 890918 - Version 2.0
  5.  * 900816 - Version 2.1
  6.  *
  7.  * Mods by PA0GRI
  8.  */
  9. #include "global.h"
  10. #ifdef RSPF
  11. #include "mbuf.h"
  12. #include "proc.h"
  13. #include "timer.h"
  14. #include "netuser.h"
  15. #include "internet.h"
  16. #include "pktdrvr.h"
  17. #include "ip.h"
  18. #include "iface.h"
  19. #include "ax25.h"
  20. #include "arp.h"
  21. #include "icmp.h"
  22. #include "socket.h"
  23. #include "rspf.h"
  24.   
  25. extern struct route *rt_lookup __ARGS((int32 target));
  26.   
  27. #ifdef  AX25
  28. extern struct lq *al_lookup __ARGS((struct iface *ifp,char *addr,int sort));
  29. #else
  30. static struct lq *al_lookup __ARGS((struct iface *ifp,char *addr,int sort));
  31. #endif  /* AX25 */
  32.   
  33. struct rspf_stat Rspf_stat;
  34. struct rspfreasm *Rspfreasmq = NULLRREASM;
  35. struct rspfiface *Rspfifaces = NULLRIFACE;
  36. struct rspfadj *Adjs = NULLADJ;
  37. struct rspfrouter *Rspfrouters = NULLRROUTER;
  38. struct mbuf *Rspfinq = NULLBUF;
  39. struct timer Rspfreasmt, Susptimer;
  40. char *Rrh_message = NULLCHAR;
  41. unsigned short Rspfpingmax = 3;
  42. static int Keeprouter = 0;
  43. static int16 Envelopeid = 0;
  44. static int Nrspfproc = 0;
  45. static unsigned char Rspfsubseq = 0;
  46. static short Rspfseq = -32768L + 1;
  47. static char *findlowroute __ARGS((int32 addr,int *low,int add,int32 *resaddr,int *resbits));
  48. static void makeroutes __ARGS((void));
  49. static void partialupdate __ARGS((struct rspfrouter *rr,struct mbuf *bp));
  50. static struct rspfrouter *rr_lookup __ARGS((int32 addr));
  51. static void rr_delete __ARGS((int32 addr));
  52. static struct rspfiface *rtif_lookup __ARGS((int32 addr));
  53. static void rspfcsum __ARGS((struct mbuf **bpp,int32 dest));
  54. static void update_in __ARGS((struct mbuf *bp,int32 addr));
  55. static void node_in __ARGS((struct mbuf *bp,int32 addr,int full));
  56. static void sendonerspf __ARGS((int32 addr,int32 dest));
  57. static void sendtoall __ARGS((struct mbuf *bp,int nodecnt,struct rspfiface *riface));
  58. static int sendupdate __ARGS((struct mbuf *bp,int nodecnt,int32 addr));
  59. static int isnewer __ARGS((short a,short b));
  60. static void del_reasm __ARGS((struct rspfreasm *re));
  61. static void reasmtimeout __ARGS((void *t));
  62. static struct mbuf *rspfreasm __ARGS((struct mbuf *bp,struct rspfpacketh *rph,int32 addr));
  63. static struct mbuf *fragmenter __ARGS((struct mbuf *bp,int nodes,int16 mtu));
  64. static struct mbuf *makeadjupdate __ARGS((int32 addr,struct rspfrouter *rr));
  65. static void pushadj __ARGS((struct mbuf **bpp,int32 addr,int bits));
  66. static void sendrrh __ARGS((struct rspfiface *ri));
  67. static void sendrspf __ARGS((void));
  68. static void goodbadnews __ARGS((struct rspfadj *adj));
  69. static void add_rspfadj __ARGS((struct rspfadj *adj));
  70. static void rspfcheck __ARGS((struct rspfadj *adj));
  71. static void rspfping __ARGS((int oldstate,void *p,void *v));
  72.   
  73. /* IP passes its RSPF packets to this function */
  74. void
  75. rspf_input(iface,ip,bp,rxbroadcast)
  76. struct iface *iface;
  77. struct ip *ip;
  78. struct mbuf *bp;
  79. int rxbroadcast;
  80. {
  81.     struct pseudo_header ph;    /* Pseudo-header for checksumming */
  82.   
  83.     if(bp == NULLBUF)
  84.         return;
  85.     if(Rspfifaces == NULLRIFACE){   /* Rspf main loop is not running */
  86.         free_p(bp);
  87.         return;
  88.     }
  89.     ph.length = ip->length - IPLEN - ip->optlen;
  90.     ph.source = ip->source;
  91.     ph.dest = ip->dest;
  92.     ph.protocol = ip->protocol;
  93.     if(cksum(&ph,bp,ph.length) != 0){
  94.         /* Checksum failed, ignore packet completely */
  95.         free_p(bp);
  96.         ++Rspf_stat.badcsum;
  97.         return;
  98.     }
  99.     bp = pushdown(bp,1 + sizeof(ip->source) + sizeof(iface));
  100.     *bp->data = RSPFE_PACKET;
  101.     memcpy(bp->data + 1,&ip->source,sizeof(ip->source));
  102.     memcpy(bp->data + 1 + sizeof(ip->source),&iface,sizeof(iface));
  103.     enqueue(&Rspfinq,bp);
  104. }
  105.   
  106. /* Main loop in RSPF process */
  107. void
  108. rspfmain(v,v1,v2)
  109. int v;
  110. void *v1,*v2;
  111. {
  112.     union rspf rspf;        /* Internal packet structure */
  113.     struct rspfadj *adj = NULLADJ;  /* Adjacency */
  114.     struct mbuf *bp, *tbp;
  115.     struct rspfiface *riface;
  116.     struct iface *iface;
  117.     struct route *rp;
  118.     int32 source;           /* Source address */
  119.     int cmd;
  120.   
  121.     for(;;) {
  122.         if(Rspfinq == NULLBUF)
  123.             pwait(&Rspfinq);
  124.         bp = dequeue(&Rspfinq);    /* at least 5 bytes */
  125.         cmd = PULLCHAR(&bp);   /* get internal event indicator */
  126.         pullup(&bp,(char *)&source,sizeof(source));
  127.         switch(cmd) {
  128.             case RSPFE_RRH:
  129.                 sendrrh((struct rspfiface *)source);
  130.                 break;
  131.             case RSPFE_CHECK:
  132.                 rspfcheck((struct rspfadj *)source);
  133.                 break;
  134.             case RSPFE_UPDATE:
  135.                 sendrspf();
  136.                 break;
  137.             case RSPFE_ARP:
  138.                 adj = (struct rspfadj *) source;
  139.                 source = adj->addr;       /* fall through */
  140.             case RSPFE_PACKET:
  141.                 pullup(&bp,(char *)&iface,sizeof(iface));
  142.                 break;
  143.         }
  144.         if(cmd != RSPFE_PACKET && cmd != RSPFE_ARP)
  145.             continue;
  146.         if(cmd == RSPFE_PACKET && ntohrspf(&rspf,&bp) == -1){
  147.             free_p(bp);
  148.             continue;
  149.         }
  150.         if(iface != NULLIF) {
  151.             for(riface = Rspfifaces; riface != NULLRIFACE; riface =
  152.                 riface->next)
  153.                 if(riface->iface == iface)
  154.                     break;
  155.         } else
  156.           /* fails if there is no route or no RSPF interface */
  157.             riface = rtif_lookup(source);
  158.   
  159.         if(riface == NULLRIFACE) {
  160.             free_p(bp);
  161.             if(cmd == RSPFE_PACKET)
  162.                 ++Rspf_stat.norspfiface;
  163.             continue; /* We do not use RSPF on this interface */
  164.         }
  165.          /* If we dont have an entry in the routing table for this station,
  166.           * or if the entry is less than 32 bits specific or has a higher
  167.           * cost than our new route, and is pointing to the wrong interface,
  168.           * then add a correct, private, route.
  169.           */
  170.         rp = rt_lookup(source);
  171.         if(rp == NULLROUTE || (rp != NULLROUTE && rp->iface !=
  172.             riface->iface && (rp->bits < 32 || rp->metric >
  173.         riface->quality))){
  174.             rt_add(source,32,0,iface,riface->quality,0,1);
  175.         }
  176.   
  177.         if(cmd == RSPFE_ARP) {
  178.             if(adj != NULLADJ){
  179.                 adj->cost = riface->quality;  /* default cost */
  180.                 add_rspfadj(adj);
  181.                 continue;
  182.             }
  183.         }
  184.         switch(rspf.hdr.type){     /* packet types */
  185.             case RSPF_RRH:
  186.                 ++Rspf_stat.rrhin;
  187.                 free_p(bp);
  188.                 adj = (struct rspfadj *)callocw(1,sizeof(struct rspfadj));
  189.                 adj->addr = rspf.rrh.addr;
  190.                 adj->seq = rspf.rrh.seq;
  191.                 adj->cost = riface->quality;  /* Default cost */
  192.                 adj->state = RSPF_TENTATIVE;
  193.                 if(rspf.rrh.flags & RSPFMODE)
  194.                     adj->tos = DELAY;
  195.                 else
  196.                     adj->tos = RELIABILITY;
  197.                 add_rspfadj(adj);
  198.                 break;
  199.             case RSPF_FULLPKT:
  200.                 ++Rspf_stat.updatein;
  201.           /* Feed the packet through the reassembly queue */
  202.                 if((tbp = rspfreasm(bp,&rspf.pkthdr,source)) != NULLBUF)
  203.                     update_in(tbp,source);
  204.                 break;
  205.         }
  206.     }
  207. }
  208.   
  209. /* This function is called every time an RRH should be broadcasted.
  210.  * An RRH is sent on the interface given by ri or on every RSPF interface.
  211.  * The broadcast address of the interface must be routed onto the same
  212.  * interface (using a static route for instance) otherwise there will be no
  213.  * RRH sent on that interface.
  214.  */
  215. static void
  216. sendrrh(ri)
  217. struct rspfiface *ri;       /* interface to use, if specified */
  218. {
  219.     struct pseudo_header ph;
  220.     struct mbuf *bp, *data = NULLBUF;
  221.     struct rspfiface *riface;
  222.     struct route *rp;
  223.     struct rrh rrh;
  224.   
  225.     for(riface = Rspfifaces; riface != NULLRIFACE; riface = riface->next) {
  226.         if(ri != NULLRIFACE && riface != ri)
  227.             continue;
  228.         if((rp = rt_lookup(riface->iface->broadcast)) != NULLROUTE &&
  229.         rp->iface == riface->iface){
  230.             rrh.version = RSPF_VERSION;
  231.             rrh.addr = riface->iface->addr;
  232.             ph.length = 0;
  233.             if(Rrh_message != NULLCHAR) {
  234.                 data = ambufw(strlen(Rrh_message));
  235.                 memcpy(data->data,Rrh_message,strlen(Rrh_message));
  236.                 ph.length = data->cnt = strlen(Rrh_message);
  237.             }
  238.             ph.length += RRHLEN;
  239.             ph.source = riface->iface->addr;
  240.             ph.dest = riface->iface->broadcast;
  241.             ph.protocol = RSPF_PTCL;
  242.           /* Start the RRH link level packet counter at 1, since adj->seq
  243.            * is 0 only for ARP generated adjacencies. This is also correct
  244.            * since rawsndcnt will increase by one when the RRH is sent.
  245.            */
  246.             rrh.seq = riface->iface->rawsndcnt + 1;
  247.           /* Default is to use the same mode as the interface */
  248.             if(Rspfownmode == -1)
  249.                 rrh.flags = !(riface->iface->flags & CONNECT_MODE);
  250.             else
  251.                 rrh.flags = !(Rspfownmode & CONNECT_MODE);
  252.   
  253.             bp = htonrrh(&rrh,data,&ph);
  254.             ++Rspf_stat.rrhout;
  255.             ip_send(riface->iface->addr,riface->iface->broadcast,RSPF_PTCL,
  256.             0,2,bp,0,0,0); /* the ttl will be decremented to 1 */
  257.         }
  258.     }
  259. }
  260.   
  261. /* This function is called whenever an RRH packet has been received or when
  262.  * a new entry is added to the ARP table.
  263.  */
  264. static void
  265. add_rspfadj(adj)
  266. struct rspfadj *adj;
  267. {
  268.     struct rspfadj *oldadj, *tmp;
  269.     struct rspfiface *riface;
  270.     struct arp_tab *atp;
  271.     struct lq *alp;
  272.     int dif, origdif;
  273.   
  274.     if(adj == NULLADJ)
  275.         return;         /* sanity but it happens... */
  276.     /* Find the previous copy of the adjacency, if there was any */
  277.     /* Insert the new adjacency */
  278.     adj->next = Adjs;
  279.     Adjs = adj;
  280.     for(oldadj = Adjs; oldadj->next != NULLADJ; oldadj = oldadj->next)
  281.         if(oldadj->next->addr == adj->addr) {
  282.             tmp = oldadj->next;
  283.             oldadj->next = oldadj->next->next;
  284.             oldadj = tmp;
  285.             break;
  286.         }
  287.   
  288.     if(oldadj->addr != adj->addr || oldadj == adj)
  289.         oldadj = NULLADJ;
  290.   
  291.     /* ARP entries give no sequence number, so save the old one */
  292.     if(oldadj != NULLADJ) {
  293.         if(adj->seq == 0)
  294.             adj->seq = oldadj->seq;
  295.         if(adj->tos == 0)
  296.             adj->tos = oldadj->tos;   /* they give no TOS either */
  297.     }
  298.   
  299.     switch(adj->state) {
  300.         case RSPF_TENTATIVE:
  301.             if(oldadj != NULLADJ) {
  302.          /* If the adjacency was in OK state, it will remain there.
  303.           * An RRH or ARP upcall can never generate an OK -> Tentative
  304.           * transition.
  305.           */
  306.                 if(oldadj->state == RSPF_OK)
  307.                     adj->state = RSPF_OK;
  308.                 adj->okcnt = oldadj->okcnt;
  309.          /* If old state was Bad, don't announce this adjacency until
  310.           * it is known to be OK, to prevent announcing an adjacency
  311.           * with an state transition loop such as OK -> Suspect -> Bad ->
  312.           * Tentative -> Suspect -> Bad -> Tentative -> ...
  313.           */
  314.                 if(oldadj->state == RSPF_BAD) {
  315.                     adj->okcnt = 0;
  316.                     stop_timer(&oldadj->timer);
  317.           /* Enter Suspect state at once, there is no point in
  318.            * dwelling as Tentative.
  319.            */
  320.                     rspfcheck(adj);
  321.                 } else {
  322.           /* Inherit the old timer */
  323.                     adj->timer.func = rspfevent;
  324.                     adj->timer.arg = (void *) &adj->timer;
  325.           /* continue where the old timer is stopped */
  326.                     adj->timer.duration = oldadj->timer.duration;
  327.                     stop_timer(&oldadj->timer);
  328.           /* Set the timer to Suspectimer in the unlikely event that
  329.            * the timer was stopped and oldadj is not Suspect or Bad.
  330.            * Suspect state is dealt with further below.
  331.            */
  332.                     if(dur_timer(&adj->timer) == 0L)
  333.                         set_timer(&adj->timer,dur_timer(&Susptimer));
  334.                     start_timer(&adj->timer);
  335.                     set_timer(&adj->timer,dur_timer(&oldadj->timer));
  336.                 }
  337.         /* We must now try to figure out from which AX.25 callsign this
  338.          * packet came. Looking at the ARP table may sometimes help.
  339.          */
  340.                 if(oldadj->seq != 0 && adj->seq != 0 &&
  341.                     (riface = rtif_lookup(adj->addr)) != NULLRIFACE &&
  342.                     (atp = arp_lookup(ARP_AX25,adj->addr,riface->iface)) != NULLARP &&
  343.                     atp->state == ARP_VALID &&
  344.                 (alp = al_lookup(riface->iface,atp->hw_addr,0)) != NULLLQ){
  345.         /* The wrapping of the modulus is taken into account here */
  346.                     if(oldadj->seq > (MAXINT16 - 100) && adj->seq < 100)
  347.                         origdif = adj->seq + MAXINT16 - oldadj->seq;
  348.                     else
  349.                         origdif = adj->seq - oldadj->seq;
  350.                     if((alp->currxcnt - adj->heard) > (MAXINT16 - 100)
  351.                         && adj->seq < 100)
  352.                         dif = (int)(origdif + MAXINT16 - (alp->currxcnt - adj->heard));
  353.                     else
  354.                         dif = (int)(origdif - (alp->currxcnt - adj->heard));
  355.                     adj->heard = alp->currxcnt; /* Update the counter */
  356.         /* At this point, "origdif" equals the difference in sequence
  357.          * numbers between the two latest RRH packets, i.e. the
  358.          * number of AX.25 frames the station has sent during since
  359.          * the last RRH packet we heard. "dif" equals the number of
  360.          * AX.25 frames that we actually heard from that station
  361.          * during the same period.
  362.          */
  363.                     if(origdif > 0 && dif > 0)
  364.             /* This algorithm can be improved, see 2.1 spec */
  365.                         adj->cost = riface->quality*2-riface->quality*dif/origdif;
  366.                 }
  367.         /* Ignore any new RRH's if a pinger process is already running */
  368.                 if(oldadj->state == RSPF_SUSPECT) {
  369.                     if(adj->heard != 0)        /* save new heard count */
  370.                         oldadj->heard = adj->heard;
  371.                     oldadj->next = adj->next;  /* adj is at start of chain */
  372.                     Adjs = oldadj;
  373.                     stop_timer(&adj->timer);
  374.                     free((char *)adj);
  375.                     return;
  376.                 }
  377.             } else {                    /* oldadj == NULLADJ */
  378.                 rspfcheck(adj);         /* enter Suspect state */
  379.         /* A new adjacency may affect the routing table even though no
  380.          * routing updates have yet been received from it.
  381.          */
  382.                 makeroutes();
  383.             }
  384.             break;
  385.         case RSPF_OK:
  386.             if(oldadj != NULLADJ) {
  387.                 adj->okcnt += oldadj->okcnt;    /* Do these before possible */
  388.                 stop_timer(&oldadj->timer);     /* killproc() -- KZ1F */
  389.                 if(oldadj->state == RSPF_SUSPECT){
  390.                     killproc(oldadj->pinger);
  391.                     --Nrspfproc;            /* Bug fix - N1BEE */
  392.                 }
  393.             }
  394.             else
  395.                 makeroutes();          /* routing table may change */
  396.             if(adj->okcnt == 1)         /* A previously unkown route */
  397.                 goodbadnews(adj);           /* ..that is good news */
  398.             break;
  399.     }
  400.     stop_timer(&oldadj->timer);     /* stop timer before free() -- KZ1F */
  401. #ifndef KZ1F
  402.     free((char *)oldadj);
  403. #endif
  404. }
  405.   
  406. /* Take appropriate action if an adjacency is Bad or Tentative */
  407. static void
  408. rspfcheck(adj)
  409. struct rspfadj *adj;
  410. {
  411.     struct rspfadj *prev;
  412.   
  413.     for(prev = Adjs; prev != NULLADJ; prev = prev->next)
  414.         if(prev->next == adj)
  415.             break;
  416.         switch(adj->state){
  417.             case RSPF_OK:
  418.                 adj->state = RSPF_TENTATIVE;   /* note fall-thru */
  419.             case RSPF_TENTATIVE:
  420.                 if (Nrspfproc < RSPF_PROCMAX) {
  421.                     Nrspfproc++;
  422.                     adj->pinger = newproc("RSPF ping",1024,rspfping,
  423.                     (int)adj->state,adj,NULL,0);
  424.                     adj->state = RSPF_SUSPECT; /* The adjacency is now Suspect */
  425.                 } else {       /* Try later */
  426.                     set_timer(&adj->timer,dur_timer(&Susptimer));
  427.                     start_timer(&adj->timer);
  428.                 }
  429.                 break;
  430.             case RSPF_BAD:
  431.                 rr_delete(adj->addr);
  432.                 adj->cost = 255;
  433.                 if(adj->okcnt != 0)
  434.                     goodbadnews(adj);     /* This is bad news... */
  435.                 if(prev != NULLADJ)
  436.                     prev->next = adj->next;   /* Unlink */
  437.                 else
  438.                     Adjs = adj->next;
  439.                 stop_timer(&adj->timer);   /* just in case */
  440.                 free((char *)adj);     /* delete the adjacency */
  441.                 makeroutes();          /* update the routing table */
  442.                 break;
  443.         }
  444. }
  445.   
  446. /* Send a ping to a suspect or tentative adjacency */
  447. static void
  448. rspfping(oldstate, p, v)
  449. int oldstate;
  450. void *p, *v;
  451. {
  452.     int s, fromlen, pcnt;
  453.     struct icmp icmp;
  454.     struct rspfadj *adj;
  455.     struct sockaddr_in from;
  456.     struct mbuf *bp;
  457.   
  458.     pause(((ptol(p) & 7)+1)*1000L); /* Pause for 1 to 8 seconds */
  459.     adj = (struct rspfadj *) p;
  460.     adj->timer.func = rspfevent;        /* Fill in timer values */
  461.     adj->timer.arg = (void *) &adj->timer;
  462.     set_timer(&adj->timer,dur_timer(&Susptimer));
  463.     if((s = socket(AF_INET,SOCK_RAW,ICMP_PTCL)) == -1){
  464.         --Nrspfproc;
  465.         adj->state = oldstate;
  466.         start_timer(&adj->timer);
  467.         return;
  468.     }
  469.   
  470.     fromlen = sizeof(from);
  471.     for(pcnt=0; pcnt < Rspfpingmax; ++pcnt) {
  472.         pingem(s,adj->addr,0,(int16)s,0);
  473.     /* Now collect the reply */
  474.         alarm(60 * 1000L);/* Let each ping timeout after 60 seconds */
  475.         for(;;) {
  476.             if(recv_mbuf(s,&bp,0,(char *)&from,&fromlen) == -1){
  477.                 if(errno == EALARM){ /* We timed out */
  478.                     break;
  479.                 }
  480.                 alarm(0);
  481.                 adj->state = oldstate;
  482.                 close_s(s);
  483.                 --Nrspfproc;
  484.                 start_timer(&adj->timer);
  485.                 return;
  486.             }
  487.             ntohicmp(&icmp,&bp);
  488.             free_p(bp);
  489.             if(icmp.type != ICMP_ECHO_REPLY || from.sin_addr.s_addr !=
  490.                 adj->addr || icmp.args.echo.id != s)
  491.           /* Ignore other people's responses */
  492.                 continue;
  493.             alarm(0);
  494.             if(++adj->okcnt == 1)
  495.                 goodbadnews(adj);     /* Good news */
  496.             close_s(s);
  497.             --Nrspfproc;
  498.             start_timer(&adj->timer);
  499.             adj->state = RSPF_OK;      /* Finally change state */
  500.             return;
  501.         }
  502.     }
  503.     /* we give up, mark the adjacency as bad */
  504.     adj->state = RSPF_BAD;
  505.     close_s(s);
  506.     --Nrspfproc;
  507.     start_timer(&adj->timer);
  508. }
  509.   
  510. /* ARP upcalls come in two flavors: When an ARP Reply has been received, we
  511.  * know for certain that bidirectional communication is possible with the
  512.  * particular station. But when an ARP Request is received, or if an ARP
  513.  * entry is added manually, it has yet to be determined if the link is
  514.  * bidirectional so iface is NULLIF in those cases.
  515.  */
  516. void
  517. rspfarpupcall(addr,hardware,iface)
  518. int32 addr;         /* Address being added to ARP table */
  519. int16 hardware;         /* Hardware type */
  520. struct iface *iface;        /* Interface used, if known */
  521. {
  522.     struct rspfadj *adj;
  523.     struct mbuf *bp;
  524.     struct rspfiface *riface;
  525.   
  526.     if((riface = rtif_lookup(addr)) == NULLRIFACE)
  527.         return;        /* Not a route to an RSPF interface */
  528.     /* Proceed only if the ARP entry is for a hardware type that is relevant
  529.      * for the interface onto which IP datagrams are routed.
  530.      */
  531.     switch(hardware) {
  532.         case ARP_NETROM:
  533.             if(riface->iface->type != CL_NETROM)
  534.                 return;
  535.             break;
  536.         case ARP_AX25:
  537.             if(riface->iface->type != CL_AX25)
  538.                 return;
  539.             break;
  540.         case ARP_ETHER:
  541.             if(riface->iface->type != CL_ETHERNET)
  542.                 return;
  543.             break;
  544.         case NHWTYPES:
  545.             break;     /* "Any interface type is ok" type entry */
  546.         default:
  547.             return;
  548.     }
  549.     if((adj = (struct rspfadj *)calloc(1,sizeof(struct rspfadj)))==NULLADJ)
  550.         return;
  551.     adj->addr = addr;
  552.     if(iface == NULLIF)   /* A manual ARP entry or Request, may be no-good */
  553.         adj->state = RSPF_TENTATIVE;
  554.     else {
  555.         adj->state = RSPF_OK;
  556.         adj->okcnt++;
  557.         adj->timer.func = rspfevent;        /* Fill in timer values */
  558.         adj->timer.arg = (void *) &adj->timer;
  559.         set_timer(&adj->timer,dur_timer(&Susptimer));
  560.         start_timer(&adj->timer);
  561.     }
  562.     if((bp = alloc_mbuf(1+sizeof(int32)+sizeof(iface))) == NULLBUF) {
  563.         stop_timer(&adj->timer);
  564.         free((char *)adj);
  565.         return;
  566.     }
  567.     *bp->data = RSPFE_ARP;
  568.     memcpy(bp->data + 1, (char *) &adj, sizeof(adj));
  569.     memcpy(bp->data + 1 + sizeof(adj), (char *) &iface, sizeof(iface));
  570.     bp->cnt = bp->size;
  571.     enqueue(&Rspfinq,bp);
  572. }
  573.   
  574. /* Called by "route add" command. */
  575. void
  576. rspfrouteupcall(addr,bits,gateway)
  577. int32 addr;         /* Address added to routing table */
  578. unsigned bits;          /* Significant bits in address */
  579. int32 gateway;          /* Address of gateway station */
  580. {
  581.     /* We are only interested in 32 bit specific routes that use a
  582.      * gateway. Direct routes will be discovered anyway.
  583.      */
  584.     if(bits != 32 || gateway == 0 || gateway == addr)
  585.         return;
  586.     if(rtif_lookup(addr) == NULLRIFACE) /* not routed onto RSPF interface */
  587.         return;
  588.     rspfarpupcall(addr,NHWTYPES,NULLIF); /* proceed as an "arp add" upcall */
  589. }
  590.   
  591. /* When the suspect timer expires, we scan through the routing table for all
  592.  * manual 32 bit specific routes through a gateway that are not an adjacency,
  593.  * and calls rspfrouteupcall(). A similar thing is done for all manual ARP
  594.  * entries. This will make sure that a station that was not reachable when
  595.  * the "route add" or "arp add" command was executed will eventually be
  596.  * discovered if it joins the network.
  597.  */
  598. void
  599. rspfsuspect(t)
  600. void *t;
  601. {
  602.     struct rspfadj *adj;
  603.     struct route *rp;
  604.     struct arp_tab *ap;
  605.     int i;
  606.     start_timer(&Susptimer);           /* restart the timer */
  607.     for(i = 0; i < HASHMOD; i++)       /* Check the routing table */
  608.         for(rp = Routes[31][i]; rp != NULLROUTE; rp = rp->next) {
  609.             if((rp->flags & RTPRIVATE) || dur_timer(&rp->timer) != 0)
  610.                 continue;   /* not this route */
  611.             for(adj = Adjs; adj != NULLADJ; adj = adj->next)
  612.                 if(adj->addr == rp->target)
  613.                     break;
  614.             if(adj == NULLADJ) /* it is not already an adjacency */
  615.                 rspfrouteupcall(rp->target,32,rp->gateway);
  616.         }
  617.     for(i=0; i < HASHMOD; ++i) /* scan the ARP table */
  618.         for(ap = Arp_tab[i]; ap != NULLARP; ap = ap->next) {
  619.             if(dur_timer(&ap->timer))    /* not a manual entry */
  620.                 continue;
  621.             for(adj = Adjs; adj != NULLADJ; adj = adj->next)
  622.                 if(adj->addr == ap->ip_addr)
  623.                     break;
  624.             if(adj == NULLADJ)   /* not already an adjacency */
  625.                 rspfarpupcall(ap->ip_addr,ap->hardware,NULLIF);
  626.         }
  627. }
  628.   
  629. /* This non-layered function peeks at the routing table to figure out to which
  630.  * interface datagrams for addr will be routed. Then it returns the matching
  631.  * rspfiface structure.
  632.  */
  633. static
  634. struct rspfiface *
  635. rtif_lookup(addr)
  636. int32 addr;
  637. {
  638.     struct rspfiface *riface;
  639.     struct route *rp;
  640.     if((rp = rt_lookup(addr)) == NULLROUTE)
  641.         return NULLRIFACE;
  642.     riface = Rspfifaces;
  643.     while(riface != NULLRIFACE){
  644.         if(riface->iface == rp->iface)
  645.             return riface;
  646.         riface = riface->next;
  647.     }
  648.     return NULLRIFACE;
  649. }
  650.   
  651. /* Send good or bad news partial routing updates. A cost of 255 should be
  652.  * interpreted as bad news by the remote station.
  653.  */
  654. static void
  655. goodbadnews(adj)
  656. struct rspfadj *adj;
  657. {
  658.     struct rspfnodeh nodeh;
  659.     struct rspflinkh linkh;
  660.     struct rspfiface *riface;
  661.     struct rspfrouter *rr;
  662.     struct mbuf *bp, *tbp, *wbp;
  663.     int nodecnt = 1;
  664.     if((riface = rtif_lookup(adj->addr)) == NULLRIFACE)
  665.         return;
  666.     bp = ambufw(5);
  667.     bp->cnt = bp->size;
  668.     *bp->data = 32;     /* the number of significant bits in the address */
  669.     put32(bp->data+1,adj->addr);
  670.     linkh.horizon = riface->horizon;
  671.     linkh.erp = riface->erp;
  672.     linkh.cost = adj->cost;
  673.     linkh.adjn = 1;
  674.     tbp = htonrspflink(&linkh,bp);
  675.     nodeh.seq = Rspfseq;
  676.     nodeh.subseq = ++Rspfsubseq;
  677.     nodeh.links = 1;
  678.     for(riface = Rspfifaces; riface != NULLRIFACE; riface = riface->next) {
  679.         if(dup_p(&wbp,tbp,0,len_p(tbp)) != len_p(tbp)) {
  680.             free_p(wbp);
  681.             continue;
  682.         }
  683.         nodeh.addr = riface->iface->addr;
  684.         bp = htonrspfnode(&nodeh,wbp);
  685.         sendtoall(bp,1,riface);
  686.     }
  687.     free_p(tbp);
  688.     /* If this is a new adjacency, then send it a routing update immediately */
  689.     if(adj->cost == 255 || adj->okcnt != 1)
  690.         return;
  691.     /* When two RSPF stations learn about each others existence, one of
  692.      * them will usually have received an RRH from the other. The one that
  693.      * received the RRH will send the peer a routing update immediately.
  694.      * So in the code below, if no RRH has been received (seq is 0) and no
  695.      * routing update has yet been received, we should expect to receive a
  696.      * routing update shortly if the adjacency is running RSPF.
  697.      * This could fail though if two RSPF stations learn about each other
  698.      * solely through ARP upcalls and no RRH's or Updates were exchanged
  699.      * prior to or during the establishment of the adjacency.
  700.      */
  701.     if(adj->seq == 0 && rr_lookup(adj->addr) == NULLRROUTER) {
  702.         if(adj->state != RSPF_SUSPECT)  /* running in RSPF process, give up */
  703.             return;
  704.         alarm(15 * 1000);   /* wait for an Update */
  705.         if(pwait(adj) == EALARM)
  706.             return;    /* still no sign of RSPF activity from the adjacency */
  707.         alarm(0);
  708.     }
  709.     ++adj->okcnt;   /* we don't want to get here again */
  710.     if((bp = makeownupdate(adj->addr,1)) == NULLBUF)
  711.         return;
  712.     for(rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next)
  713.         if((tbp = makeadjupdate(get32(rr->data->data),rr)) != NULLBUF){
  714.             append(&bp,tbp);
  715.             nodecnt++;
  716.         }
  717.     sendupdate(bp,nodecnt,adj->addr);
  718. }
  719.   
  720. /* This function is called whenever it is time to send a new RSPF update */
  721. static void
  722. sendrspf()
  723. {
  724.     struct rspfrouter *rr;
  725.     struct mbuf *bp, *wbp, *tmp = NULLBUF;
  726.     struct rspfiface *riface;
  727.     struct rspfadj *adj;
  728.     int nodecnt, incr = 1;
  729.   
  730.     for(nodecnt = 1, rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next)
  731.         if(!rr->sent)      /* don't send stale data */
  732.             if((bp = makeadjupdate(get32(rr->data->data),rr)) != NULLBUF){
  733.                 append(&tmp,bp);
  734.                 nodecnt++;
  735.             }
  736.     for(riface = Rspfifaces; riface != NULLRIFACE; riface = riface->next) {
  737.      /* Find an address that is routed onto this interface */
  738.         for(adj = Adjs; adj != NULLADJ; adj = adj->next)
  739.             if(rtif_lookup(adj->addr) == riface)
  740.                 break;
  741.         if(adj == NULLADJ) /* no adjacency on that interface? */
  742.             continue;
  743.         if(dup_p(&wbp,tmp,0,len_p(tmp)) != len_p(tmp)) {
  744.             free_p(wbp);
  745.             continue;
  746.         }
  747.         if((bp = makeownupdate(adj->addr,incr)) != NULLBUF) {
  748.             incr = 0; /* sequence number is incremented only once */
  749.             append(&bp,wbp);
  750.         }
  751.         else
  752.             break;
  753.         sendtoall(bp,nodecnt,riface);
  754.     }
  755.     free_p(tmp);
  756.     for(rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next)
  757.         if(!rr->sent)      /* Mark router data as propagated */
  758.             ++rr->sent;
  759. }
  760.   
  761. /* This function is used to answer "poll" messages */
  762. static void
  763. sendonerspf(addr,dest)
  764. int32 addr; /* address of station whose routing update we will make */
  765. int32 dest; /* address of station to send the update to */
  766. {
  767.     struct mbuf *bp;
  768.     if(ismyaddr(addr)){
  769.         if((bp = makeownupdate(dest,0)) == NULLBUF)
  770.             return;
  771.         sendupdate(bp,1,dest);
  772.         return;
  773.     }
  774.     if((bp = makeadjupdate(addr,NULLRROUTER)) == NULLBUF)
  775.         return;
  776.     sendupdate(bp,1,dest);
  777. }
  778.   
  779. /* send an update to all adjacencies on an RSPF interface */
  780. static void
  781. sendtoall(bp,nodecnt,riface)
  782. struct mbuf *bp;
  783. int nodecnt;            /* number of reporting nodes in update */
  784. struct rspfiface *riface;   /* interface to sent to */
  785. {
  786.     struct rspfadj *adj;
  787.     struct mbuf *wbp;
  788.     int broad;
  789.     for(broad = 0, adj = Adjs; adj != NULLADJ; adj = adj->next)
  790.       /* If adj->seq is 0 we have never received an RRH from the
  791.        * adjacency, and if there is no stored routing update, then
  792.        * it is not known if the adjacency understands RSPF.
  793.        */
  794.         if((adj->seq != 0 || rr_lookup(adj->addr) != NULLRROUTER) &&
  795.         riface == rtif_lookup(adj->addr)) {
  796.             if((adj->tos & RELIABILITY) && !(adj->tos & DELAY)) {
  797.                 if(dup_p(&wbp,bp,0,len_p(bp)) != len_p(bp)) {
  798.                     free_p(wbp);
  799.                     continue;
  800.                 }
  801.                 sendupdate(wbp,nodecnt,adj->addr); /* private copy */
  802.             }
  803.             else
  804.                 ++broad;    /* send to broadcast IP address instead */
  805.         }
  806.     if(broad != 0)
  807.         if(dup_p(&wbp,bp,0,len_p(bp)) != len_p(bp))
  808.             free_p(wbp);
  809.         else
  810.             sendupdate(wbp,nodecnt,riface->iface->broadcast);
  811.     free_p(bp);
  812. }
  813.   
  814. /* This function sends a routing update to the adjacencies that we have
  815.  * recevied RRH's from.
  816.  */
  817. static int
  818. sendupdate(bp,nodecnt,addr)
  819. struct mbuf *bp;    /* Full packet, except for the packet header */
  820. int nodecnt;        /* Number of reporting nodes in the packet */
  821. int32 addr;     /* Station to send update to */
  822. {
  823.     struct rspfadj *adj;
  824.     struct mbuf *tmp;
  825.     int tos = 0;
  826.   
  827.     /* See if we are sending to a known adjacency, in use its TOS in
  828.      * that case.
  829.      */
  830.     for(adj = Adjs; adj != NULLADJ; adj = adj->next)
  831.         if(adj->addr == addr) {
  832.             tos = adj->tos;
  833.             break;
  834.         }
  835.     if((tmp = fragmenter(bp,nodecnt,ip_mtu(addr) - IPLEN)) == NULLBUF)
  836.         return -1;
  837.     while((bp = dequeue(&tmp)) != NULLBUF){
  838.         rspfcsum(&bp,addr);    /* Calculate the checksum */
  839.         ++Rspf_stat.updateout;
  840.         ip_send(INADDR_ANY,addr,RSPF_PTCL,INET_CTL | tos,2,bp,0,0,0);
  841.     }
  842.     return 0;
  843. }
  844.   
  845. /* Fragment a large mbuf if necessary into packets of maximum mtu bytes.
  846.  * Each packet is prepended a RSPF routing update header, without the checksum.
  847.  */
  848. static struct mbuf *
  849. fragmenter(bp,nodes,mtu)
  850. struct mbuf *bp; /* packet to send, without packet header */
  851. int nodes;  /* The number of reporting nodes in the routing update */
  852. int16 mtu;  /* The maximum transmission unit */
  853. {
  854.     struct rspfnodeh nodeh;
  855.     struct rspflinkh linkh;
  856.     struct rspfpacketh pkth;
  857.     struct mbuf *tbp, *tmp, *bpq = NULLBUF;
  858.     int n, nodecnt, linkcnt, adjcnt, nodemax, sync;
  859.     char *cp, fragn = 1;
  860.   
  861.     if(mtu < RSPFPKTLEN + RSPFNODELEN || bp == NULLBUF) {
  862.         free_p(bp);
  863.         return NULLBUF;
  864.     }
  865.     ++Envelopeid;
  866.     nodemax = nodes;        /* total number of nodes in envelope */
  867.     nodecnt = nodes;        /* nodes left to packetize */
  868.     linkcnt = adjcnt = 0;
  869.     while(len_p(bp) != 0){
  870.         n = min(mtu,len_p(bp)+RSPFPKTLEN);  /* length of this packet */
  871.         n -= RSPFPKTLEN;
  872.         tbp = NULLBUF;
  873.         sync = 0;
  874.         if(adjcnt){
  875.             tbp = ambufw(min(adjcnt*5,n/5*5));
  876.             tbp->cnt = tbp->size;
  877.             cp = tbp->data;
  878.         }
  879.         while(n > 0){
  880.             while(adjcnt){
  881.                 if((n -= 5) < 0)
  882.                     break;
  883.                 pullup(&bp,cp,5);
  884.                 cp += 5;
  885.                 adjcnt--;
  886.             }
  887.             if(linkcnt && n > 0){
  888.                 if((n -= RSPFLINKLEN) < 0)
  889.                     break;
  890.                 ntohrspflink(&linkh,&bp);
  891.                 adjcnt = linkh.adjn;
  892.                 tmp = htonrspflink(&linkh,NULLBUF);
  893.                 append(&tbp,tmp);
  894.                 tmp = ambufw(min(5*adjcnt,n/5*5));
  895.                 tmp->cnt = tmp->size;
  896.                 cp = tmp->data;
  897.                 append(&tbp,tmp);
  898.                 linkcnt--;
  899.                 continue;
  900.             }
  901.             if(nodecnt && linkcnt == 0 && n > 0){
  902.                 if((n -= RSPFNODELEN) < 0)
  903.                     break;
  904.                 if(nodecnt == nodes)        /* Set the sync octet */
  905.                     sync = len_p(tbp) + 4;
  906.                 ntohrspfnode(&nodeh,&bp);
  907.                 linkcnt = nodeh.links;
  908.                 tmp = htonrspfnode(&nodeh,NULLBUF);
  909.                 append(&tbp,tmp);
  910.                 nodecnt--;
  911.             }
  912.         }
  913.         pkth.version = RSPF_VERSION;    /* The version number */
  914.         pkth.type = RSPF_FULLPKT;   /* The packet type */
  915.         pkth.fragn = fragn++;       /* The fragment number */
  916.         pkth.fragtot = 0;       /* The total number of fragments */
  917.         pkth.csum = 0;          /* The checksum */
  918.         pkth.sync = sync < 256 ? sync : 0;  /* The sync octet */
  919.         pkth.nodes = nodemax;       /* The number of nodes in envelope */
  920.         pkth.envid = Envelopeid;    /* The envelope-ID */
  921.         tmp = htonrspf(&pkth,tbp);  /* add packet header */
  922.         enqueue(&bpq,tmp);      /* add packet to chain */
  923.         nodes = nodecnt;        /* number of nodes left */
  924.     }
  925.     free_p(bp);
  926.     for(tbp = bpq; tbp != NULLBUF; tbp = tbp->anext)
  927.         *(tbp->data + 3) = len_q(bpq);  /* Set the fragment total counter */
  928.     return bpq;
  929. }
  930.   
  931. /* Calculate the checksum on an RSPF routing update packet */
  932. static void
  933. rspfcsum(bpp,dest)
  934. struct mbuf **bpp;
  935. int32 dest;
  936. {
  937.     struct pseudo_header ph;
  938.     int16 checksum;
  939.     ph.length = len_p(*bpp);
  940.     ph.source = locaddr(dest);
  941.     ph.dest = dest;
  942.     ph.protocol = RSPF_PTCL;
  943.     if((checksum = cksum(&ph,*bpp,ph.length)) == 0)
  944.         checksum = 0xffffffffL;
  945.     /* This assumes that the checksum really is at this position */
  946.     put16((*bpp)->data+4,checksum);
  947. }
  948.   
  949. /* This function creates our own routing update and returns it in an mbuf */
  950. struct mbuf *
  951. makeownupdate(dest,new)
  952. int32 dest;     /* Address of a station that will get this update */
  953. int new;        /* True if the sequence number should be incremented */
  954. {
  955.     struct rspfadj *adj;
  956.     struct rspflinkh linkh;
  957.     struct rspfnodeh nodeh;
  958.     struct rspfiface *riface, rifdefault;
  959.     struct mbuf *bp = NULLBUF, *tbp, *tmp;
  960.     struct route *rp;
  961.     int i, adjcnt, lnkcnt, bits;
  962.     int32 prev, low, cur;
  963.   
  964.     /* Set default values to apply to non-RSPF interfaces */
  965.     rifdefault.horizon = 32;
  966.     rifdefault.erp = 0;
  967.     rifdefault.quality = 0;
  968.     /* Our adjacencies has to be sorted into groups of the same horizon,
  969.      * ERP factor and cost. This is done by combining these numbers into a
  970.      * single one, modulo 256 and take the lowest number first.
  971.      */
  972.     low = 0;
  973.     lnkcnt = 0;
  974.     for(;;){
  975.         prev = low;
  976.         low = 255*65536L+255*256+255;
  977.         for(adj = Adjs; adj != NULLADJ; adj = adj->next)
  978.          /* Include all adjacecies that have been or are in OK state
  979.           * in the update. Bad adjacencies are also included to give
  980.           * them a chance to recover. Hopelessly Bad adjacencies are
  981.           * eventually deleted elsewhere.
  982.           */
  983.             if(adj->okcnt != 0 && (riface = rtif_lookup(adj->addr)) !=
  984.             NULLRIFACE) {
  985.                 cur = riface->horizon*65536L+riface->erp*256+adj->cost;
  986.                 if(cur > prev && cur < low)
  987.                     low = cur;
  988.             }
  989.     /* Add any manual public, 1-31 bit specific routes.
  990.      * Use the route metric only if it is greater than the default
  991.      * quality to lessen a possible "wormhole" effect.
  992.      */
  993.         for(bits = 1; bits <= 31; bits++)
  994.             for(i = 0; i < HASHMOD; i++)
  995.                 for(rp = Routes[bits-1][i]; rp != NULLROUTE; rp = rp->next)
  996.                     if(!(rp->flags & RTPRIVATE) && !dur_timer(&rp->timer)) {
  997.                         if((riface = rtif_lookup(rp->target)) == NULLRIFACE)
  998.                             riface = &rifdefault;
  999.                         cur = riface->horizon*65536L+riface->erp*256+
  1000.                         (rp->metric > riface->quality ? rp->metric :
  1001.                         riface->quality);
  1002.                         if(cur > prev && cur < low)
  1003.                             low = cur;
  1004.                     }
  1005.     /* Add any 32 bit routes on interfaces not using RSPF */
  1006.         for(i = 0; i < HASHMOD; i++)
  1007.             for(rp = Routes[31][i]; rp != NULLROUTE; rp = rp->next)
  1008.                 if(!(rp->flags & RTPRIVATE) && rtif_lookup(rp->target)
  1009.                 == NULLRIFACE) {
  1010.                     cur = rifdefault.horizon*65536L+rifdefault.erp*256+
  1011.                     (rp->metric > rifdefault.quality ? rp->metric :
  1012.                     rifdefault.quality);
  1013.                     if(cur > prev && cur < low)
  1014.                         low = cur;
  1015.                 }
  1016.     /* Add the default route */
  1017.         if((rp = rt_blookup(0,0)) != NULLROUTE && !(rp->flags & RTPRIVATE) &&
  1018.         !dur_timer(&rp->timer)) {
  1019.             if((riface = rtif_lookup(0)) == NULLRIFACE)
  1020.                 riface = &rifdefault;
  1021.             cur = riface->horizon*65536L+riface->erp*256+
  1022.             (rp->metric > riface->quality ? rp->metric : riface->quality);
  1023.             if(cur > prev && cur < low)
  1024.                 low = cur;
  1025.         }
  1026.         if(low == 255*65536L+255*256+255) /* All done */
  1027.             break;
  1028.     /* now start adding the routes */
  1029.         adjcnt = 0;
  1030.         tbp = NULLBUF;
  1031.         for(adj = Adjs; adj != NULLADJ; adj = adj->next)
  1032.             if(adj->okcnt != 0 && (riface = rtif_lookup(adj->addr)) !=
  1033.                 NULLRIFACE)
  1034.                 if(riface->horizon*65536L+riface->erp*256+adj->cost == low){
  1035.                     pushadj(&tbp,adj->addr,32);
  1036.                     adjcnt++;
  1037.                 }
  1038.         for(bits = 1; bits <= 31; bits++)
  1039.             for(i = 0; i < HASHMOD; i++)
  1040.                 for(rp = Routes[bits-1][i]; rp != NULLROUTE; rp = rp->next)
  1041.                     if(!(rp->flags & RTPRIVATE) && !dur_timer(&rp->timer)){
  1042.                         if((riface = rtif_lookup(rp->target)) == NULLRIFACE)
  1043.                             riface = &rifdefault;
  1044.             /* Manually entered local routes only */
  1045.                         if(riface->horizon*65536L+riface->erp*256+
  1046.                             (rp->metric > riface->quality ? rp->metric :
  1047.                         riface->quality) == low){
  1048.                             pushadj(&tbp,rp->target,bits);
  1049.                             adjcnt++;
  1050.                         }
  1051.                     }
  1052.         for(i = 0; i < HASHMOD; i++)    /* 32 bit specific routes */
  1053.             for(rp = Routes[31][i]; rp != NULLROUTE; rp = rp->next)
  1054.                 if(!(rp->flags & RTPRIVATE) && rtif_lookup(rp->target)
  1055.                     == NULLRIFACE)
  1056.                     if(rifdefault.horizon*65536L+rifdefault.erp*256+
  1057.                         (rp->metric > rifdefault.quality ? rp->metric :
  1058.                     rifdefault.quality) == low){
  1059.                         pushadj(&tbp,rp->target,bits);
  1060.                         adjcnt++;
  1061.                     }
  1062.     /* Add the default route */
  1063.         if((rp = rt_blookup(0,0)) != NULLROUTE && !(rp->flags & RTPRIVATE) &&
  1064.         !dur_timer(&rp->timer)) {
  1065.             if((riface = rtif_lookup(0)) == NULLRIFACE)
  1066.                 riface = &rifdefault;
  1067.             if(riface->horizon*65536L+riface->erp*256+ (rp->metric >
  1068.             riface->quality ? rp->metric : riface->quality) == low){
  1069.                 pushadj(&tbp,0,0);
  1070.                 adjcnt++;
  1071.             }
  1072.         }
  1073.         if(adjcnt != 0){
  1074.         /* Prepend the link header */
  1075.             linkh.horizon = ((low >> 16) & 255);/* Horizon value */
  1076.             linkh.erp = ((low >> 8) & 255); /* ERP factor */
  1077.             linkh.cost = (low & 255);       /* Link cost */
  1078.             linkh.adjn = adjcnt;        /* Number of adjacencies */
  1079.             tmp = htonrspflink(&linkh,tbp);
  1080.             append(&bp,tmp);
  1081.             lnkcnt++;
  1082.         }
  1083.     }
  1084.     /* Prepend the node header */
  1085.     if(lnkcnt != 0){
  1086.     /* Set our address to the IP address used on the destinations
  1087.      * interface.
  1088.      */
  1089.         if(dest == INADDR_ANY || (riface = rtif_lookup(dest)) == NULLRIFACE)
  1090.             nodeh.addr = Ip_addr;
  1091.         else
  1092.             nodeh.addr = riface->iface->addr;
  1093.         if(new){    /* increase sequence number, clear subseq. number */
  1094.             if(Rspfseq == 32768L - 2 || Rspfseq == -32768L + 1)
  1095.                 Rspfseq = 0;           /* wrap around */
  1096.             else
  1097.                 ++Rspfseq;
  1098.             Rspfsubseq = 0;
  1099.         }
  1100.         nodeh.seq = Rspfseq;
  1101.         nodeh.subseq = 0;
  1102.         nodeh.links = lnkcnt;
  1103.         return htonrspfnode(&nodeh,bp);
  1104.     }
  1105.     else {
  1106.         free_p(bp);
  1107.         return NULLBUF;
  1108.     }
  1109. }
  1110. /* Prepends an adjacency to bpp. Allocates bpp in large chunk for efficency */
  1111. static void
  1112. pushadj(bpp,addr,bits)
  1113. struct mbuf **bpp;
  1114. int32 addr;
  1115. int bits;
  1116. {
  1117.     if(bpp == NULLBUFP)
  1118.         return;
  1119.     if(*bpp == NULLBUF) {
  1120.         *bpp = ambufw(60);        /* good for 12 adjacencies */
  1121.         (*bpp)->data += 55;
  1122.         (*bpp)->cnt = 5;
  1123.     }
  1124.     else
  1125.         *bpp = pushdown(*bpp,5);
  1126.     *(*bpp)->data = bits;
  1127.     put32((*bpp)->data+1,addr);
  1128. }
  1129.   
  1130. /* This function returns the latest routing update in network fromat from
  1131.  * the adjacency denoted by addr.
  1132.  */
  1133. static struct mbuf *
  1134. makeadjupdate(addr,rr)
  1135. int32 addr;
  1136. struct rspfrouter *rr;  /* pointer to stored routing entry, if known */
  1137. {
  1138.     struct mbuf *tmp, *tmp2, *tmp3, *bp = NULLBUF;
  1139.     struct rspfnodeh nodeh;
  1140.     struct rspflinkh linkh;
  1141.     int linkcnt = 0;
  1142.     if(rr == NULLRROUTER && (rr = rr_lookup(addr)) == NULLRROUTER)
  1143.         return NULLBUF;
  1144.     if(dup_p(&tmp,rr->data,0,len_p(rr->data)) != len_p(rr->data)) {
  1145.         free_p(tmp);
  1146.         return NULLBUF;
  1147.     }
  1148.     ntohrspfnode(&nodeh,&tmp);           /* Get the node header */
  1149.     while(nodeh.links--){
  1150.         ntohrspflink(&linkh,&tmp);
  1151.     /* Decrement and check the horizon value */
  1152.         if(--linkh.horizon > 0){
  1153.         /* Duplicate the adjacencies */
  1154.             if(dup_p(&tmp2,tmp,0,5*linkh.adjn) != 5*linkh.adjn){
  1155.                 free_p(tmp);
  1156.                 free_p(tmp2);
  1157.                 free_p(bp);
  1158.                 return NULLBUF;
  1159.             }
  1160.         /* Prepend the link header */
  1161.             tmp3 = htonrspflink(&linkh,tmp2);
  1162.             append(&bp,tmp3);
  1163.             linkcnt++;
  1164.         }
  1165.         pullup(&tmp,NULLCHAR,5*linkh.adjn); /* Skip the adjacencies */
  1166.     }
  1167.     free_p(tmp);
  1168.     if(linkcnt == 0){       /* No links at all? */
  1169.         free_p(bp);
  1170.         return NULLBUF;
  1171.     }
  1172.     nodeh.subseq = rr->subseq;
  1173.     nodeh.links = linkcnt;
  1174.     /* Prepend the node header */
  1175.     return htonrspfnode(&nodeh,bp);
  1176. }
  1177.   
  1178. /* Returns 1 if sequence number a is newer than b. Sequence numbers start
  1179.  * at -32768 + 1 and then continues with 0 and the positive integer numbers
  1180.  * until reaching 32768 - 2 after which they continue with 0.
  1181.  * Algorithm taken from RFC-1131 but fixed bug when a or b is 0.
  1182.  */
  1183. static int
  1184. isnewer(a,b)
  1185. short a,b;
  1186. {
  1187.     if((b < 0 && a > b) ||
  1188.         (a >= 0 && b >= 0 &&    /* bug corrected here */
  1189.         (((32768L - 1)/2 > (a-b) && (a-b) > 0) ||
  1190.         (a-b) < -(32768L - 1)/2)))
  1191.         return 1;
  1192.     return 0;
  1193. }
  1194.   
  1195. /* Reassemble possibly fragmented packets into a single large one */
  1196. static struct mbuf *
  1197. rspfreasm(bp,rph,addr)
  1198. struct mbuf *bp;      /* Routing update packet without packet header */
  1199. struct rspfpacketh *rph;  /* Packet header */
  1200. int32 addr;       /* Address of station we got the packet from */
  1201. {
  1202.     union rspf rspf;
  1203.     struct rspfreasm *re, *rtmp;
  1204.     struct mbuf *tbp, *bp1, *bp2;
  1205.     for(re = Rspfreasmq; re != NULLRREASM; re = re->next)
  1206.         if(re->addr == addr){   /* found another fragment */
  1207.             if(dup_p(&tbp,re->data,0,RSPFPKTLEN) != RSPFPKTLEN) {
  1208.                 free_p(tbp);
  1209.                 free_p(bp);
  1210.                 return NULLBUF;
  1211.             }
  1212.             ntohrspf(&rspf,&tbp);   /* get its packet header */
  1213.             if(rph->envid != rspf.pkthdr.envid) {
  1214.                 del_reasm(re);     /* an obsolete entry, delete it */
  1215.                 break;
  1216.             }
  1217.         /* Now try to find a place where this fragment fits in the chain */
  1218.             bp1 = re->data;
  1219.             bp2 = NULLBUF;
  1220.             while(rph->fragn > rspf.pkthdr.fragn && bp1->anext != NULLBUF){
  1221.                 bp2 = bp1;
  1222.                 bp1 = bp1->anext;
  1223.                 if(dup_p(&tbp,bp1,0,RSPFPKTLEN) != RSPFPKTLEN) {
  1224.                     free_p(bp);
  1225.                     free_p(tbp);
  1226.                     return NULLBUF;
  1227.                 }
  1228.                 ntohrspf(&rspf,&tbp);
  1229.             }
  1230.             if(rspf.pkthdr.fragn == rph->fragn) {
  1231.                 free_p(bp);
  1232.                 return NULLBUF;    /* We already had this one */
  1233.             }
  1234.             bp = htonrspf(rph,bp);  /* Put the packet header back on */
  1235.         /* Insert the fragment at the right place in the chain */
  1236.             if(rph->fragn > rspf.pkthdr.fragn){
  1237.                 bp1->anext = bp;
  1238.                 bp->anext = NULLBUF;
  1239.             }
  1240.             else {
  1241.                 if(bp2 != NULLBUF)
  1242.                     bp2->anext = bp;
  1243.                 else
  1244.                     re->data = bp;
  1245.                 bp->anext = bp1;
  1246.             }
  1247.             if(len_q(re->data) == rspf.pkthdr.fragtot){
  1248.                 bp1 = NULLBUF;          /* we have all the fragments */
  1249.                 while((bp2 = dequeue(&re->data)) != NULLBUF){
  1250.                     pullup(&bp2,NULLCHAR,RSPFPKTLEN); /* strip the headers */
  1251.                     append(&bp1,bp2);       /* and form a single packet */
  1252.                 }
  1253.                 del_reasm(re);
  1254.                 stop_timer(&Rspfreasmt);
  1255.                 reasmtimeout(NULL); /* restarts timer if necessary */
  1256.                 return bp1;     /* return the completed packet */
  1257.             }
  1258.             re->time = secclock();      /* Update the timestamp */
  1259.             goto timstart;      /* We have to wait for fragments */
  1260.         }
  1261.     /* At this point we know that there is no matching entry in the
  1262.        reassembly queue (any more) */
  1263.     if(rph->fragtot == 1)   /* Simple case, an un-fragmented packet */
  1264.         return bp;
  1265.     tbp = htonrspf(rph,bp); /* Put the packet header back on */
  1266.     rtmp = (struct rspfreasm *) callocw(1,sizeof(struct rspfreasm));
  1267.     /* The values are filled in */
  1268.     rtmp->addr = addr;
  1269.     rtmp->time = secclock();
  1270.     rtmp->data = tbp;
  1271.     rtmp->next = Rspfreasmq;
  1272.     Rspfreasmq = rtmp;
  1273.     timstart:                  /* Start the timer if needed */
  1274.     if(!run_timer(&Rspfreasmt)){
  1275.         Rspfreasmt.func = reasmtimeout;
  1276.         Rspfreasmt.arg = NULL;
  1277.         set_timer(&Rspfreasmt,RSPF_RTIME*1000L); /* The reassembly timeout */
  1278.         start_timer(&Rspfreasmt);
  1279.     }
  1280.     return NULLBUF;
  1281. }
  1282.   
  1283. /* Delete a reassembly descriptor from the queue */
  1284. static void
  1285. del_reasm(re)
  1286. struct rspfreasm *re;
  1287. {
  1288.     struct rspfreasm *r, *prev = NULLRREASM;
  1289.     for(r = Rspfreasmq; r != NULLRREASM; prev = r, r = r->next)
  1290.         if(r == re){
  1291.             free_q(&re->data);
  1292.             if(prev != NULLRREASM)
  1293.                 prev->next = re->next;
  1294.             else
  1295.                 Rspfreasmq = re->next;
  1296.             free((char *)re);
  1297.             break;
  1298.         }
  1299. }
  1300.   
  1301. /* When the reassembly timer times out, this function tries to make use of
  1302.  * any fragments in the reassembly queue.
  1303.  */
  1304. static void
  1305. reasmtimeout(t)
  1306. void *t;
  1307. {
  1308.     union rspf rspf;
  1309.     struct rspfreasm *re;
  1310.     struct mbuf *bp, *tbp;
  1311.     int last = 0;
  1312.     int32 low;
  1313.     re = Rspfreasmq;
  1314.     while(re != NULLRREASM)
  1315.         if((secclock() - re->time) >= RSPF_RTIME){
  1316.         /* Try to use what we have */
  1317.             bp = NULLBUF;
  1318.             while((tbp = dequeue(&re->data)) != NULLBUF){
  1319.                 ntohrspf(&rspf,&tbp);
  1320.                 if(rspf.pkthdr.fragn != (last+1)){  /* a missing fragment */
  1321.                     if(bp != NULLBUF)
  1322.                         update_in(bp,re->addr);
  1323.                     bp = NULLBUF;
  1324.                     if(rspf.pkthdr.sync != 0)
  1325.                         pullup(&tbp,NULLCHAR,rspf.pkthdr.sync - 4);
  1326.                     else {  /* no sync possible in this fragment */
  1327.                         free_p(tbp);
  1328.                         continue;
  1329.                     }
  1330.                 }
  1331.                 append(&bp,tbp);
  1332.                 last = rspf.pkthdr.fragn;
  1333.             }
  1334.             if(bp != NULLBUF)
  1335.                 update_in(bp,re->addr);
  1336.             del_reasm(re);
  1337.             re = Rspfreasmq;    /* start over again */
  1338.         }
  1339.         else
  1340.             re = re->next;
  1341.     /* Find the oldest fragment and restart the reassembly timer */
  1342.     low = 0;
  1343.     for(re = Rspfreasmq; re != NULLRREASM; re = re->next)
  1344.         if(re->time < low || low == 0)
  1345.             low = re->time;
  1346.     if(low){
  1347.         set_timer(&Rspfreasmt,RSPF_RTIME*1000L - clock() + low);
  1348.         if(dur_timer(&Rspfreasmt) > 0) /* just to be safe */
  1349.             start_timer(&Rspfreasmt);
  1350.     }
  1351. }
  1352.   
  1353. /* Handle incoming routing updates (a reassembled envelope) */
  1354. static void
  1355. update_in(bp,addr)
  1356. struct mbuf *bp;    /* Reassembled data packet, without packet header */
  1357. int32 addr;     /* Senders address (in host order) */
  1358. {
  1359.     struct rspfnodeh nodeh;
  1360.     struct rspflinkh linkh;
  1361.     struct rspfadj *adj;
  1362.     struct mbuf *tbp, *tmp, *b;
  1363.     int linkcnt = 0, adjcnt = 0;
  1364.     int16 offset = 0;
  1365.     tbp = b = NULLBUF;
  1366.     /* Check to see if the sender is an adjacency */
  1367.     for(adj = Adjs; adj != NULLADJ; adj = adj->next)
  1368.         if(adj->addr == addr)
  1369.             break;
  1370.     /* One may argue that updates from non-adjacencies should not be
  1371.      * accepted since they will not contribute to the routing table.
  1372.      * But it might happen that the sender will very shortly become an
  1373.      * adjacency, and then its routing update will come handy. By increasing
  1374.      * Keeprouter, routing updates from disjoint routers will not be not be
  1375.      * purged when makeroutes() is called this time.
  1376.      */
  1377.     if(adj == NULLADJ) {
  1378.         ++Rspf_stat.noadjupdate;
  1379.         Keeprouter += 2;
  1380.     }
  1381.     else
  1382.         psignal(adj,1);     /* alert anyone waiting for the update */
  1383.     while(offset < len_p(bp)){
  1384.         if(adjcnt){
  1385.             if(dup_p(&tmp,bp,offset,5) == 5){
  1386.                 append(&tbp,tmp);
  1387.                 offset += 5;
  1388.                 adjcnt--;
  1389.                 continue;
  1390.             }
  1391.             else break;
  1392.         }
  1393.         if(tbp != NULLBUF){
  1394.             tmp = htonrspflink(&linkh,tbp);
  1395.             append(&b,tmp);
  1396.             tbp = NULLBUF;
  1397.         }
  1398.         if(linkcnt){
  1399.             if(dup_p(&tbp,bp,offset,RSPFLINKLEN) == RSPFLINKLEN){
  1400.                 ntohrspflink(&linkh,&tbp);
  1401.                 adjcnt = linkh.adjn;
  1402.                 offset += RSPFLINKLEN;
  1403.                 linkcnt--;
  1404.                 continue;
  1405.             }
  1406.             else
  1407.                 break;
  1408.         }
  1409.         if(b != NULLBUF){
  1410.             tmp = htonrspfnode(&nodeh,b);
  1411.             node_in(tmp,addr,1);     /* a full router update */
  1412.             b = NULLBUF;
  1413.         }
  1414.         if(dup_p(&tmp,bp,offset,RSPFNODELEN) == RSPFNODELEN){
  1415.             ntohrspfnode(&nodeh,&tmp);
  1416.             linkcnt = nodeh.links;
  1417.             offset += RSPFNODELEN;
  1418.         }
  1419.         else {
  1420.             free_p(bp);
  1421.             free_p(tmp);
  1422.             return;
  1423.         }
  1424.     }
  1425.     if(tbp != NULLBUF){
  1426.     /* adjust the adjacency counter in the link header */
  1427.         linkh.adjn -= adjcnt;
  1428.         tmp = htonrspflink(&linkh,tbp);
  1429.         append(&b,tmp);
  1430.     }
  1431.     /* adjust the link counter in the node header */
  1432.     nodeh.links -= linkcnt;
  1433.     tmp = htonrspfnode(&nodeh,b);
  1434.     free_p(bp);
  1435.     if(linkcnt || adjcnt)
  1436.         node_in(tmp,addr,0);    /* a partial router update */
  1437.     else
  1438.         node_in(tmp,addr,1);
  1439. }
  1440.   
  1441. static void
  1442. node_in(bp,addr,full)
  1443. struct mbuf *bp;    /* A single update, starting with the node header */
  1444. int32 addr;     /* Address of station we got packet from */
  1445. int full;       /* False if we got a partial update */
  1446. {
  1447.     struct mbuf *tbp;
  1448.     struct rspfnodeh nodeh, rnodeh;
  1449.     struct rspfrouter *rr;
  1450.     if(dup_p(&tbp,bp,0,RSPFNODELEN) != RSPFNODELEN) {
  1451.         free_p(bp);
  1452.         free_p(tbp);
  1453.         return;
  1454.     }
  1455.     ntohrspfnode(&nodeh,&tbp);
  1456.     if(ismyaddr(nodeh.addr)){
  1457.     /* If another station thinks our routing update sequence number is
  1458.      * larger than it really is, this might be because we have had
  1459.      * a fast system reset and routing updates from the old "epoch"
  1460.      * are still present in the network.
  1461.      */
  1462.         if(isnewer(nodeh.seq,Rspfseq)) {
  1463.             Rspfseq = nodeh.seq + 1;            /* Catch up */
  1464.             if(nodeh.seq == 32768L - 2 || nodeh.seq == -32768L + 1)
  1465.                 Rspfseq = 0;               /* Wrap around */
  1466.             sendonerspf(nodeh.addr,addr); /* Send him the latest packet */
  1467.         }
  1468.         free_p(bp);         /* We already know our own adjacencies! */
  1469.         return;
  1470.     }
  1471.     if((rr = rr_lookup(nodeh.addr)) != NULLRROUTER) {
  1472.         if(dup_p(&tbp,rr->data,0,RSPFNODELEN) != RSPFNODELEN) {
  1473.             free_p(bp);
  1474.             free_p(tbp);
  1475.             return;
  1476.         }
  1477.         ntohrspfnode(&rnodeh,&tbp);
  1478.         if(nodeh.seq == rnodeh.seq && nodeh.subseq <= rr->subseq){
  1479.             free_p(bp);
  1480.             return; /*  We already have this one */
  1481.         }
  1482.         if(isnewer(rnodeh.seq,nodeh.seq)){
  1483.         /* Send him the latest packet */
  1484.             sendonerspf(nodeh.addr,addr);
  1485.             free_p(bp);
  1486.             ++Rspf_stat.oldreport;
  1487.             return;
  1488.         }
  1489.         if(nodeh.subseq > rr->subseq && nodeh.seq == rnodeh.seq){
  1490.             rr->subseq = nodeh.subseq;
  1491.             partialupdate(rr,bp);
  1492.             makeroutes();
  1493.             return;
  1494.         }
  1495.         if(isnewer(nodeh.seq,rnodeh.seq) && !full){
  1496.             partialupdate(rr,bp);
  1497.             makeroutes();
  1498.         /* Send a "poll" packet */
  1499.             --nodeh.seq;
  1500.             nodeh.subseq = 0;
  1501.             nodeh.links = 0;
  1502.             tbp = htonrspfnode(&nodeh,NULLBUF);
  1503.             sendupdate(tbp,1,addr);
  1504.             ++Rspf_stat.outpolls;
  1505.             return;
  1506.         }
  1507.     }
  1508.     else {
  1509.         rr = (struct rspfrouter *) callocw(1,sizeof(struct rspfrouter));
  1510.         rr->next = Rspfrouters;
  1511.         Rspfrouters = rr;
  1512.     }
  1513.     free_p(rr->data);
  1514.     rr->data = bp;
  1515.     rr->subseq = nodeh.subseq;
  1516.     rr->time = secclock();
  1517.     rr->sent = 0;
  1518.     makeroutes();
  1519.     return;
  1520. }
  1521.   
  1522. /* Return the matching RSPF route entry for addr (in host order) */
  1523. static struct rspfrouter *
  1524. rr_lookup(addr)
  1525. int32 addr;
  1526. {
  1527.     struct rspfrouter *rr;
  1528.     for(rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next)
  1529.     /* this assumes that the first word of the header is the address */
  1530.         if(rr->data != NULLBUF && get32(rr->data->data) == addr)
  1531.             return rr;
  1532.     return NULLRROUTER;
  1533. }
  1534.   
  1535. /* Delete the route entry for address addr */
  1536. static void
  1537. rr_delete(addr)
  1538. int32 addr;
  1539. {
  1540.     struct rspfrouter *rr, *prev = NULLRROUTER;
  1541.     for(rr = Rspfrouters; rr != NULLRROUTER; prev = rr, rr = rr->next)
  1542.     /* this assumes that the first word of the header is the address */
  1543.         if(rr->data != NULLBUF && get32(rr->data->data) == addr) {
  1544.             if(prev != NULLRROUTER)
  1545.                 prev->next = rr->next;
  1546.             else
  1547.                 Rspfrouters = rr->next;
  1548.             free_p(rr->data);
  1549.             free((char *)rr);
  1550.             return;
  1551.         }
  1552. }
  1553.   
  1554. /* Handle incoming partial routing updates. Adjacencies from bp will be
  1555.  * merged into rr->data
  1556.  */
  1557. static void
  1558. partialupdate(rr,bp)
  1559. struct rspfrouter *rr;  /* current node entry in routing table */
  1560. struct mbuf *bp;    /* data packet, starting with node header */
  1561. {
  1562.     struct rspflinkh linkh, rlinkh;
  1563.     struct rspfnodeh rnodeh;
  1564.     struct mbuf *wbp, *tbp, *tmp, *b;
  1565.     int adjcnt = 0, radjcnt, rlinkcnt = 0, bits, rbits, added = 0;
  1566.     int32 addr, raddr;
  1567.   
  1568.     rlinkh.adjn = 0;
  1569.     rr->time = secclock();
  1570.     rr->sent = 0;
  1571.     /* Make a working copy of the stored routing update */
  1572.     if(dup_p(&wbp,rr->data,0,len_p(rr->data)) != len_p(rr->data)) {
  1573.         free_p(wbp);
  1574.         free_p(bp);
  1575.         return;
  1576.     }
  1577.     ntohrspfnode(&rnodeh,&wbp);
  1578.     pullup(&bp,NULLCHAR,RSPFNODELEN);   /* Strip off the node header */
  1579.     while(len_p(bp) > 0)
  1580.         if(adjcnt == 0) {
  1581.             if(ntohrspflink(&linkh,&bp) == -1) {
  1582.                 free_p(wbp);
  1583.                 free_p(bp);
  1584.                 return;
  1585.             }
  1586.             adjcnt = linkh.adjn;
  1587.         }
  1588.         else {
  1589.             bits = PULLCHAR(&bp);   /* get one adjacency to merge */
  1590.             if(pullup(&bp,(char *)&addr,4) != 4) {
  1591.                 free_p(wbp);
  1592.                 free_p(bp);
  1593.                 return;
  1594.             }
  1595.             addr = get32((char *)&addr); /* convert to host order */
  1596.             --adjcnt;
  1597.             radjcnt = 0;
  1598.             b = tbp = NULLBUF;
  1599.             for(;;) {           /* search through stored update */
  1600.                 if(radjcnt == 0 || len_p(wbp) == 0) {
  1601.                     if(tbp != NULLBUF){
  1602.                         rlinkh.adjn -= radjcnt;
  1603.                         tmp = htonrspflink(&rlinkh,tbp);
  1604.                         ++rlinkcnt;
  1605.                         append(&b,tmp);
  1606.                         tbp = NULLBUF;
  1607.                     }
  1608.                     if(len_p(wbp) == 0)
  1609.                         break;
  1610.                 }
  1611.                 if(radjcnt == 0) {
  1612.                     ntohrspflink(&rlinkh,&wbp);
  1613.                     radjcnt = rlinkh.adjn;
  1614.                     if(rlinkh.horizon == linkh.horizon && rlinkh.cost ==
  1615.                     linkh.cost && rlinkh.erp == linkh.erp) {
  1616.                         pushadj(&tbp,addr,bits);
  1617.                         ++rlinkh.adjn;
  1618.                         added = 1;
  1619.                     }
  1620.                 }
  1621.                 else {
  1622.                     rbits = PULLCHAR(&wbp);
  1623.                     raddr = pull32(&wbp);
  1624.                     --radjcnt;
  1625.                     if(bits != rbits || addr != raddr)
  1626.                         pushadj(&tbp,raddr,rbits);  /* Put it back */
  1627.                     else
  1628.                         --rlinkh.adjn; /* deleted one adjacency */
  1629.                 }
  1630.             }
  1631.             wbp = b;    /* wbp now keeps link headers and adjacencies */
  1632.             if(linkh.cost < 255 && !added){ /* Append the new link */
  1633.                 ++rnodeh.links;      /* We will add one extra link */
  1634.                 tmp = ambufw(5);
  1635.                 *tmp->data = bits;
  1636.                 put32(tmp->data+1,addr);
  1637.                 tmp->cnt = tmp->size;
  1638.                 tbp = htonrspflink(&linkh,tmp);
  1639.                 append(&wbp,tbp);
  1640.             }
  1641.             added = 0;
  1642.         }
  1643.     free_p(rr->data);
  1644.     rnodeh.links = rlinkcnt;
  1645.     rr->data = htonrspfnode(&rnodeh,wbp);
  1646. }
  1647.   
  1648. /* The shortest path first algorithm */
  1649. static void
  1650. makeroutes()
  1651. {
  1652.     int bits, i, low, adjcnt;
  1653.     struct mbuf *bp;
  1654.     struct route *rp, *rp2, *saved[HASHMOD];
  1655.     struct rspfadj *adj, *lowadj, *gateway;
  1656.     char *lowp, *r;
  1657.     int32 lowaddr;
  1658.     struct rspflinkh linkh;
  1659.     struct rspfrouter *rr, *rrprev;
  1660.   
  1661.     if(Keeprouter)  /* if false, purge unreachable router entries */
  1662.         --Keeprouter;
  1663.     /* Before we change anything in the routing table, we have to save
  1664.      * each local adjacencies riface pointer
  1665.      */
  1666.     for(adj = Adjs; adj != NULLADJ; adj = adj->next)
  1667.         adj->scratch = (void *) rtif_lookup(adj->addr);
  1668.     /* Remove all non-manual routes */
  1669.     for(bits = 1; bits <= 32; bits++)
  1670.         for(i = 0; i < HASHMOD; i++)
  1671.             for(rp = Routes[bits-1][i]; rp != NULLROUTE; rp = rp2) {
  1672.                 rp2 = rp->next;         /* BIG BUG FIX -- sm6rpz */
  1673.                 if(dur_timer(&rp->timer) != 0)
  1674.                     rt_drop(rp->target,bits);
  1675.             /* rp will be undefined here if(dur_timer(&rp->timer) */
  1676.             }
  1677.     rt_drop(rp->target,bits);
  1678.   
  1679.     if((rp = rt_blookup(0,0)) != NULLROUTE && dur_timer(&rp->timer) != 0)
  1680.         rt_drop(0,0);  /* delete non-manual default route */
  1681.   
  1682.     /* Temporarily remove all 32-bit specific manual routes. This will make
  1683.      * it possible to prevent loops in findlowroute()
  1684.      */
  1685.     for(i = 0; i < HASHMOD; i++) {
  1686.         saved[i] = Routes[31][i];
  1687.         Routes[31][i] = NULLROUTE;
  1688.     }
  1689.   
  1690.     for(;;) {
  1691.         lowadj = NULLADJ;
  1692.         lowp = NULLCHAR;
  1693.         low = 255;
  1694.         for(adj = Adjs; adj != NULLADJ; adj = adj->next){
  1695.             if(adj->scratch == NULL)
  1696.                 continue;       /* skip unreachable adjacency */
  1697.             if(!adj->added){
  1698.                 if(adj->cost <= low){
  1699.                     low = adj->cost;
  1700.                     lowadj = adj;
  1701.                     lowp = NULLCHAR;
  1702.                 }
  1703.             }
  1704.             else
  1705.                 if((r = findlowroute(adj->addr,&low,adj->cost,&lowaddr,&bits))
  1706.                 != NULLCHAR) {
  1707.                     lowp = r;
  1708.                     gateway = adj;
  1709.                     lowadj = NULLADJ;
  1710.                 }
  1711.         }
  1712.         if(lowadj != NULLADJ){
  1713.             lowadj->added++;
  1714.             rp = rt_add(lowadj->addr,32,0,
  1715.             ((struct rspfiface *)lowadj->scratch)->iface,
  1716.             (int32)lowadj->cost,0,0);
  1717.         /* set the timer to a dummy value. This makes it possible to
  1718.          * distinguish between manual and RSPF-generated routes.
  1719.          * The timer is never started however since RSPF handles the
  1720.          * expiration of routes itself.
  1721.          */
  1722.             set_timer(&rp->timer,MSPTICK);
  1723.             continue;
  1724.         }
  1725.         if(lowp != NULLCHAR){
  1726.         /* Check if we already have this one */
  1727.             rp = rt_blookup(lowaddr,bits);
  1728.             if((rp == NULLROUTE || (rp != NULLROUTE &&
  1729.             rp->metric > (int32) low)) && !ismyaddr(lowaddr)) {
  1730.          /* This is a new route, or a route with strict lower cost than
  1731.           * the previous route (possible only if it was manual)
  1732.           */
  1733.                 rp = rt_add(lowaddr,bits,gateway->addr,
  1734.                 ((struct rspfiface *)gateway->scratch)->iface,
  1735.                 (int32)low,0,0);
  1736.                 set_timer(&rp->timer,MSPTICK); /* a dummy value */
  1737.             }
  1738.             *lowp |= 128; /* mark the route as added in any case */
  1739.         }
  1740.         else
  1741.             break; /* no more routes */
  1742.     }
  1743.   
  1744.     /* Add the saved 32 bit routes, if there isn't now a better route */
  1745.     for(i = 0; i < HASHMOD; i++) {
  1746.         rp = saved[i];
  1747.         while(rp != NULLROUTE) {
  1748.             rp2 = rt_blookup(rp->target,32);
  1749.             if(rp2 == NULLROUTE || (rp2 != NULLROUTE && rp2->metric >= rp->metric)) {
  1750.                 rp2 = rt_add(rp->target,32,rp->gateway,rp->iface,rp->metric,
  1751.                 0,rp->flags & RTPRIVATE);
  1752.                 rp2->uses = rp->uses;
  1753.             }
  1754.             rp2 = rp->next;
  1755.             stop_timer(&rp->timer); /* Stop timer before free() -- KZ1F */
  1756. #ifndef KZ1F
  1757.             free((char *)rp);
  1758. #endif
  1759.             rp = rp2;
  1760.         }
  1761.     }
  1762.   
  1763.     /* Reset all flags */
  1764.     for(adj = Adjs; adj != NULLADJ; adj = adj->next) {
  1765.         adj->added = 0;
  1766.         adj->scratch = NULL;
  1767.     }
  1768.   
  1769.     for(rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next){
  1770.         i = len_p(rr->data) - RSPFNODELEN;
  1771.     /* jump past the node header */
  1772.         if(dup_p(&bp,rr->data,RSPFNODELEN,i) != i) {
  1773.             free_p(bp);
  1774.             continue;
  1775.         }
  1776.         adjcnt = 0;
  1777.         while(i > 0){
  1778.             if(adjcnt){
  1779.                 if(!Keeprouter && (*bp->data & 128) == 0) {
  1780.              /* This router has an adjacency that was not added. That
  1781.               * means that the router is unreachable. Mark the
  1782.               * stored routing update for deletion.
  1783.               */
  1784.                     free_p(bp);
  1785.                     free_p(rr->data);
  1786.                     rr->data = NULLBUF;    /* indicates disposal */
  1787.                     break;
  1788.                 }
  1789.                 *bp->data &= ~128;  /* Clear the "added" bit */
  1790.                 pullup(&bp,NULLCHAR,5);
  1791.                 i -= 5;
  1792.                 --adjcnt;
  1793.                 continue;
  1794.             }
  1795.             ntohrspflink(&linkh,&bp);
  1796.             adjcnt = linkh.adjn;
  1797.             i -= RSPFLINKLEN;
  1798.         }
  1799.     }
  1800.   
  1801.     if(Keeprouter)  /* nothing more to do */
  1802.         return;
  1803.     /* Delete any routers that were discovered as being unreachable */
  1804.     rrprev = NULLRROUTER;
  1805.     rr = Rspfrouters;
  1806.     for(;;) {
  1807.         for(rrprev = NULLRROUTER, rr = Rspfrouters; rr != NULLRROUTER;
  1808.             rrprev = rr, rr = rr->next)
  1809.             if(rr->data == NULLBUF) {
  1810.                 if(rrprev != NULLRROUTER)
  1811.                     rrprev->next = rr->next;
  1812.                 else
  1813.                     Rspfrouters = rr->next;
  1814.                 free((char *)rr);
  1815.                 break;
  1816.             }
  1817.         if(rr == NULLRROUTER)
  1818.             break;
  1819.     }
  1820. }
  1821.   
  1822. /* Find a route from addr with the lowest cost. Returns a pointer to the
  1823.  * buffer that keeps the significant bit count of the selected route.
  1824.  */
  1825. static char *
  1826. findlowroute(addr,low,add,resaddr,resbits)
  1827. int32 addr;         /* The node whose routes will be examined */
  1828. int *low;           /* Lowest cost so far */
  1829. int add;            /* Cost of this node */
  1830. int32 *resaddr;         /* Resulting route stored here */
  1831. int *resbits;           /* Significant bits of resulting route */
  1832. {
  1833.     struct mbuf *bp;
  1834.     struct rspfrouter *rr;
  1835.     struct rspflinkh linkh;
  1836.     struct route *rp;
  1837.     char *r, *retval = NULLCHAR;
  1838.     int adjcnt = 0;
  1839.   
  1840.     linkh.cost = 0;
  1841.     if((rr = rr_lookup(addr)) == NULLRROUTER)
  1842.         return NULLCHAR;
  1843.     if((rp = rt_blookup(addr,32)) != NULLROUTE && rp->metric < add)
  1844.         return NULLCHAR;   /* already added this one, no loops thanks */
  1845.     if(dup_p(&bp,rr->data,RSPFNODELEN,len_p(rr->data) - RSPFNODELEN) !=
  1846.     len_p(rr->data) - RSPFNODELEN) {
  1847.         free_p(bp);
  1848.         return NULLCHAR;
  1849.     }
  1850.     while(len_p(bp) > 0){
  1851.         if(adjcnt){
  1852.             if(*bp->data & 128) {
  1853.                 (void) PULLCHAR(&bp);
  1854.                 if((r = findlowroute(pull32(&bp),low,add+linkh.cost,resaddr,
  1855.                     resbits)) != NULLCHAR)
  1856.                     retval = r;
  1857.             }
  1858.             else {
  1859.                 *low = add + linkh.cost;
  1860.                 retval = bp->data;
  1861.                 *resbits = PULLCHAR(&bp);
  1862.                 *resaddr = pull32(&bp);
  1863.                 pullup(&bp,NULLCHAR,5*(adjcnt-1));
  1864.                 adjcnt = 1; /* No need to check the rest of this link */
  1865.             }
  1866.             --adjcnt;
  1867.             continue;
  1868.         }
  1869.         ntohrspflink(&linkh,&bp);
  1870.         if((add + linkh.cost) <= *low)
  1871.             adjcnt = linkh.adjn;
  1872.         else
  1873.             pullup(&bp,NULLCHAR,5*linkh.adjn);
  1874.     }
  1875.     return retval;
  1876. }
  1877.   
  1878. #ifndef AX25
  1879. /*
  1880.  * Dummy stub for RSPF if AX25 is not configured.
  1881.  */
  1882. static struct lq *
  1883. al_lookup(ifp,addr,sort)
  1884. struct iface *ifp;
  1885. char *addr;
  1886. int sort;
  1887. {
  1888.     return NULLLQ;
  1889. }
  1890. #endif  /* AX25 */
  1891. #endif /* RSPF */
  1892.   
  1893.