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