home *** CD-ROM | disk | FTP | other *** search
/ HAM Radio 3 / hamradioversion3.0examsandprograms1992.iso / misc / 9q920411 / iproute.c < prev    next >
C/C++ Source or Header  |  1992-04-10  |  20KB  |  760 lines
  1. /* Lower half of IP, consisting of gateway routines
  2.  * Includes routing and options processing code
  3.  *
  4.  * Copyright 1991 Phil Karn, KA9Q
  5.  */
  6. #include "global.h"
  7. #include "mbuf.h"
  8. #include "iface.h"
  9. #include "timer.h"
  10. #include "internet.h"
  11. #include "ip.h"
  12. #include "tcp.h"
  13. #include "netuser.h"
  14. #include "icmp.h"
  15. #include "rip.h"
  16. #include "trace.h"
  17. #include "pktdrvr.h"
  18. #include "bootp.h"
  19.  
  20.  
  21. struct route *Routes[32][HASHMOD];    /* Routing table */
  22. struct route R_default = {        /* Default route entry */
  23.     NULLROUTE, NULLROUTE,
  24.     0,0,0,
  25.     RIP_INFINITY        /* Init metric to infinity */
  26. };
  27.  
  28. static struct rt_cache Rt_cache;
  29.  
  30. static int q_pkt __ARGS((struct iface *iface,int32 gateway,struct ip *ip,
  31.     struct mbuf *bp,int ckgood));
  32.  
  33. /* Initialize modulo lookup table used by hash_ip() in pcgen.asm */
  34. void
  35. ipinit()
  36. {
  37.     int i;
  38.  
  39.     for(i=0;i<256;i++)
  40.         Hashtab[i] = i % HASHMOD;
  41. }
  42.  
  43. /* Route an IP datagram. This is the "hopper" through which all IP datagrams,
  44.  * coming or going, must pass.
  45.  *
  46.  * "rxbroadcast" is set to indicate that the packet came in on a subnet
  47.  * broadcast. The router will kick the packet upstairs regardless of the
  48.  * IP destination address.
  49.  */
  50. int
  51. ip_route(i_iface,bp,rxbroadcast)
  52. struct iface *i_iface;    /* Input interface */
  53. struct mbuf *bp;    /* Input packet */
  54. int rxbroadcast;    /* True if packet had link broadcast address */
  55. {
  56.     struct ip ip;            /* IP header being processed */
  57.     int16 ip_len;            /* IP header length */
  58.     int16 length;            /* Length of data portion */
  59.     int32 gateway;            /* Gateway IP address */
  60.     register struct route *rp;    /* Route table entry */
  61.     struct iface *iface;        /* Output interface, possibly forwarded */
  62.     int16 offset;            /* Offset into current fragment */
  63.     int16 mf_flag;            /* Original datagram MF flag */
  64.     int strict = 0;            /* Strict source routing flag */
  65.     int16 opt_len;        /* Length of current option */
  66.     char *opt;        /* -> beginning of current option */
  67.     int i;
  68.     int ckgood = IP_CS_OLD; /* Has good checksum without modification */
  69.     int pointer;        /* Relative pointer index for sroute/rroute */
  70.  
  71.     if(i_iface != NULLIF){
  72.         ipInReceives++;    /* Not locally generated */
  73.         i_iface->iprecvcnt++;
  74.     }
  75.     if(len_p(bp) < IPLEN){
  76.         /* The packet is shorter than a legal IP header */
  77.         ipInHdrErrors++;
  78.         free_p(bp);
  79.         return -1;
  80.     }
  81.     /* Sneak a peek at the IP header's IHL field to find its length */
  82.     ip_len = (bp->data[0] & 0xf) << 2;
  83.     if(ip_len < IPLEN){
  84.         /* The IP header length field is too small */
  85.         ipInHdrErrors++;
  86.         free_p(bp);
  87.         return -1;
  88.     }
  89.     if(cksum(NULLHEADER,bp,ip_len) != 0){
  90.         /* Bad IP header checksum; discard */
  91.         ipInHdrErrors++;
  92.         free_p(bp);
  93.         return -1;
  94.     }
  95.     /* Extract IP header */
  96.     ntohip(&ip,&bp);
  97.  
  98.     if(ip.version != IPVERSION){
  99.         /* We can't handle this version of IP */
  100.         ipInHdrErrors++;
  101.         free_p(bp);
  102.         return -1;
  103.     }
  104.     /* Trim data segment if necessary. */
  105.     length = ip.length - ip_len;    /* Length of data portion */
  106.     trim_mbuf(&bp,length);    
  107.                 
  108.     /* If we're running low on memory, return a source quench */
  109.     if(!rxbroadcast && availmem() < Memthresh)
  110.         icmp_output(&ip,bp,ICMP_QUENCH,0,NULLICMP);
  111.  
  112.     /* Process options, if any. Also compute length of secondary IP
  113.      * header in case fragmentation is needed later
  114.      */
  115.     strict = 0;
  116.     for(i=0;i<ip.optlen;i += opt_len){
  117.  
  118.         /* First check for the two special 1-byte options */
  119.         switch(ip.options[i] & OPT_NUMBER){
  120.         case IP_EOL:
  121.             goto no_opt;    /* End of options list, we're done */
  122.         case IP_NOOP:
  123.             opt_len = 1;
  124.             continue;    /* No operation, skip to next option */
  125.         }
  126.         /* Not a 1-byte option, so ensure that there's at least
  127.          * two bytes of option left, that the option length is
  128.          * at least two, and that there's enough space left for
  129.          * the specified option length.
  130.          */
  131.         if(ip.optlen - i < 2
  132.          || ((opt_len = uchar(ip.options[i+1])) < 2)
  133.          || ip.optlen - i < opt_len){
  134.             /* Truncated option, send ICMP and drop packet */
  135.             if(!rxbroadcast){
  136.                 union icmp_args icmp_args;
  137.  
  138.                 icmp_args.pointer = IPLEN + i;
  139.                 icmp_output(&ip,bp,ICMP_PARAM_PROB,0,&icmp_args);
  140.             }
  141.             free_p(bp);
  142.             return -1;
  143.         }
  144.         opt = &ip.options[i];
  145.  
  146.         switch(opt[0] & OPT_NUMBER){
  147.         case IP_SSROUTE:    /* Strict source route & record route */
  148.             strict = 1;    /* note fall-thru */
  149.         case IP_LSROUTE:    /* Loose source route & record route */
  150.             /* Source routes are ignored unless we're in the
  151.              * destination field
  152.              */
  153.             if(opt_len < 3){
  154.                 /* Option is too short to be a legal sroute.
  155.                  * Send an ICMP message and drop it.
  156.                  */
  157.                 if(!rxbroadcast){
  158.                     union icmp_args icmp_args;
  159.  
  160.                     icmp_args.pointer = IPLEN + i;
  161.                     icmp_output(&ip,bp,ICMP_PARAM_PROB,0,&icmp_args);
  162.                 }
  163.                 free_p(bp);
  164.                 return -1;
  165.             }
  166.             if(ismyaddr(ip.dest) == NULLIF)
  167.                 break;    /* Skip to next option */
  168.             pointer = uchar(opt[2]);
  169.             if(pointer + 4 > opt_len)
  170.                 break;    /* Route exhausted; it's for us */
  171.  
  172.             /* Put address for next hop into destination field,
  173.              * put our address into the route field, and bump
  174.              * the pointer. We've already ensured enough space.
  175.              */
  176.             ip.dest = get32(&opt[pointer]);
  177.             put32(&opt[pointer],locaddr(ip.dest));
  178.             opt[2] += 4;
  179.             ckgood = IP_CS_NEW;
  180.             break;
  181.         case IP_RROUTE:    /* Record route */
  182.             if(opt_len < 3){
  183.                 /* Option is too short to be a legal rroute.
  184.                  * Send an ICMP message and drop it.
  185.                  */
  186.                 if(!rxbroadcast){
  187.                     union icmp_args icmp_args;
  188.  
  189.                     icmp_args.pointer = IPLEN + i;
  190.                     icmp_output(&ip,bp,ICMP_PARAM_PROB,0,&icmp_args);
  191.                 }
  192.                 free_p(bp);
  193.                 return -1;
  194.             }                
  195.             pointer = uchar(opt[2]);
  196.             if(pointer + 4 > opt_len){
  197.                 /* Route area exhausted; send an ICMP msg */
  198.                 if(!rxbroadcast){
  199.                     union icmp_args icmp_args;
  200.  
  201.                     icmp_args.pointer = IPLEN + i;
  202.                     icmp_output(&ip,bp,ICMP_PARAM_PROB,0,&icmp_args);
  203.                 }
  204.                 /* Also drop if odd-sized */
  205.                 if(pointer != opt_len){
  206.                     free_p(bp);
  207.                     return -1;
  208.                 }
  209.             } else {
  210.                 /* Add our address to the route.
  211.                  * We've already ensured there's enough space.
  212.                  */
  213.                 put32(&opt[pointer],locaddr(ip.dest));
  214.                  opt[2] += 4;
  215.                 ckgood = IP_CS_NEW;
  216.             }
  217.             break;
  218.         }
  219.     }
  220. no_opt:
  221.  
  222.     /* See if it's a broadcast or addressed to us, and kick it upstairs */
  223.     if(ismyaddr(ip.dest) != NULLIF || rxbroadcast ||
  224.         (WantBootp && bootp_validPacket(&ip, &bp))){
  225. #ifdef    GWONLY
  226.     /* We're only a gateway, we have no host level protocols */
  227.         if(!rxbroadcast)
  228.             icmp_output(&ip,bp,ICMP_DEST_UNREACH,
  229.              ICMP_PROT_UNREACH,NULLICMP);
  230.         ipInUnknownProtos++;
  231.         free_p(bp);
  232. #else
  233.         ip_recv(i_iface,&ip,bp,rxbroadcast);
  234. #endif
  235.         return 0;
  236.     }
  237.     /* Packet is not destined to us. If it originated elsewhere, count
  238.      * it as a forwarded datagram.
  239.      */
  240.     if(i_iface != NULLIF)
  241.         ipForwDatagrams++;
  242.  
  243.     /* Adjust the header checksum to allow for the modified TTL */        
  244.     ip.checksum += 0x100;
  245.     if((ip.checksum & 0xff00) == 0)
  246.         ip.checksum++;    /* end-around carry */
  247.  
  248.     /* Decrement TTL and discard if zero. We don't have to check
  249.      * rxbroadcast here because it's already been checked
  250.      */
  251.     if(--ip.ttl == 0){
  252.         /* Send ICMP "Time Exceeded" message */
  253.         icmp_output(&ip,bp,ICMP_TIME_EXCEED,0,NULLICMP);
  254.         ipInHdrErrors++;
  255.         free_p(bp);
  256.         return -1;
  257.     }
  258.     /* Look up target address in routing table */
  259.     if((rp = rt_lookup(ip.dest)) == NULLROUTE){
  260.         /* No route exists, return unreachable message (we already
  261.          * know this can't be a broadcast)
  262.          */
  263.         icmp_output(&ip,bp,ICMP_DEST_UNREACH,ICMP_HOST_UNREACH,NULLICMP);
  264.         free_p(bp);
  265.         ipOutNoRoutes++;
  266.         return -1;
  267.     }
  268.     rp->uses++;
  269.  
  270.     /* Check for output forwarding and divert if necessary */
  271.     iface = rp->iface;
  272.     if(iface->forw != NULLIF)
  273.         iface = iface->forw;
  274.  
  275.     /* Find gateway; zero gateway in routing table means "send direct" */
  276.     if(rp->gateway == 0)
  277.         gateway = ip.dest;
  278.     else
  279.         gateway = rp->gateway;
  280.  
  281.     if(strict && gateway != ip.dest){
  282.         /* Strict source routing requires a direct entry
  283.          * Again, we know this isn't a broadcast
  284.          */
  285.         icmp_output(&ip,bp,ICMP_DEST_UNREACH,ICMP_ROUTE_FAIL,NULLICMP);
  286.         free_p(bp);
  287.         ipOutNoRoutes++;
  288.         return -1;
  289.     }
  290.     if(ip.length <= iface->mtu){
  291.         /* Datagram smaller than interface MTU; put header
  292.          * back on and send normally.
  293.          */
  294.         return q_pkt(iface,gateway,&ip,bp,ckgood);
  295.     }
  296.     /* Fragmentation needed */
  297.     if(ip.flags.df){
  298.         /* Don't Fragment set; return ICMP message and drop */
  299.         union icmp_args icmp_args;
  300.  
  301.         icmp_args.mtu = iface->mtu;
  302.         icmp_output(&ip,bp,ICMP_DEST_UNREACH,ICMP_FRAG_NEEDED,&icmp_args);
  303.         free_p(bp);
  304.         ipFragFails++;
  305.         return -1;
  306.     }
  307.     /* Create fragments */
  308.     offset = ip.offset;
  309.     mf_flag = ip.flags.mf;        /* Save original MF flag */
  310.     while(length != 0){        /* As long as there's data left */
  311.         int16 fragsize;        /* Size of this fragment's data */
  312.         struct mbuf *f_data;    /* Data portion of fragment */
  313.  
  314.         /* After the first fragment, should remove those
  315.          * options that aren't supposed to be copied on fragmentation
  316.          */
  317.         ip.offset = offset;
  318.         if(length + ip_len <= iface->mtu){
  319.             /* Last fragment; send all that remains */
  320.             fragsize = length;
  321.             ip.flags.mf = mf_flag;    /* Pass original MF flag */
  322.         } else {
  323.             /* More to come, so send multiple of 8 bytes */
  324.             fragsize = (iface->mtu - ip_len) & 0xfff8;
  325.             ip.flags.mf = 1;
  326.         }
  327.         ip.length = fragsize + ip_len;
  328.  
  329.         /* Duplicate the fragment */
  330.         dup_p(&f_data,bp,offset,fragsize);
  331.         if(f_data == NULLBUF){
  332.             free_p(bp);
  333.             ipFragFails++;
  334.             return -1;
  335.         }
  336.         if(q_pkt(iface,gateway,&ip,f_data,IP_CS_NEW) == -1){
  337.             ipFragFails++;
  338.             return -1;
  339.         }
  340.         ipFragCreates++;
  341.         offset += fragsize;
  342.         length -= fragsize;
  343.     }
  344.     ipFragOKs++;
  345.     free_p(bp);
  346.     return 0;
  347. }
  348. /* Direct IP input routine for packets without link-level header */
  349. void
  350. ip_proc(iface,bp)
  351. struct iface *iface;
  352. struct mbuf *bp;
  353. {
  354.     ip_route(iface,bp,0);
  355. }
  356.  
  357. /* Add an IP datagram to an interface output queue, sorting first by
  358.  * the precedence field in the IP header, and secondarily by an
  359.  * "interactive" flag set by peeking at the transport layer to see
  360.  * if the packet belongs to what appears to be an interactive session.
  361.  * A layer violation, yes, but a useful one...
  362.  */
  363. static int
  364. q_pkt(iface,gateway,ip,bp,ckgood)
  365. struct iface *iface;
  366. int32 gateway;
  367. struct ip *ip;
  368. struct mbuf *bp;
  369. int ckgood;
  370. {
  371.     struct mbuf *tbp,*tlast;
  372.     struct tcp tcp;
  373.     struct qhdr qhdr;
  374.     struct qhdr qtmp;
  375.     int i;
  376.  
  377.     if((tbp = htonip(ip,bp,ckgood)) == NULLBUF){
  378.         free_p(bp);
  379.         return -1;
  380.     }
  381.     bp = pushdown(tbp,sizeof(struct qhdr));
  382.     iface->ipsndcnt++;
  383.     /* create priority field consisting of tos with 2 unused
  384.      * low order bits stripped, one of which we'll use as an
  385.      * "interactive" flag.
  386.      */
  387.     qhdr.tos = (ip->tos & 0xfc);
  388.     qhdr.gateway = gateway;
  389.     if(iface->outq == NULLBUF){
  390.         /* Queue empty, no priority decisions to be made
  391.          * This is the usual case for fast networks like Ethernet,
  392.          * so we can avoid some time-consuming stuff
  393.          */
  394.         memcpy(bp->data,(char *)&qhdr,sizeof(qhdr));
  395.         iface->outq = bp;
  396.         psignal(&iface->outq,1);
  397.         return 0;
  398.     }
  399.     /* See if this packet references a "priority" TCP port number */
  400.     if(ip->protocol == TCP_PTCL && ip->offset == 0){
  401.         /* Extract a copy of the TCP header */
  402.         if(dup_p(&tbp,bp,sizeof(struct qhdr)+IPLEN+
  403.          ip->optlen,TCPLEN+TCP_MAXOPT) >= TCPLEN){
  404.             ntohtcp(&tcp,&tbp);
  405.             for(i=0;Tcp_interact[i] != -1;i++){
  406.                 if(tcp.source == Tcp_interact[i]
  407.                  || tcp.dest == Tcp_interact[i]){
  408.                     qhdr.tos |= 1;
  409.                     break;
  410.                 }
  411.             }
  412.         }
  413.         free_p(tbp);
  414.     }
  415.     memcpy(bp->data,(char *)&qhdr,sizeof(qhdr));
  416.     /* Search the queue looking for the first packet with precedence
  417.      * lower than our packet
  418.      */
  419.     tlast = NULLBUF;
  420.     for(tbp = iface->outq;tbp != NULLBUF;tlast=tbp,tbp = tbp->anext){
  421.         memcpy((char *)&qtmp,tbp->data,sizeof(qtmp));
  422.         if(qhdr.tos > qtmp.tos){
  423.             break;    /* Add it just before tbp */
  424.         }
  425.     }
  426.     bp->anext = tbp;
  427.     if(tlast == NULLBUF){
  428.         /* First on queue */
  429.         iface->outq = bp;
  430.     } else {
  431.         tlast->anext = bp;
  432.     }
  433.     psignal(&iface->outq,1);
  434.     return 0;
  435. }
  436. int
  437. ip_encap(bp,iface,gateway,tos)
  438. struct mbuf *bp;
  439. struct iface *iface;
  440. int32 gateway;
  441. int tos;
  442. {
  443.     struct ip ip;
  444.  
  445.     dump(iface,IF_TRACE_OUT,CL_NONE,bp);
  446.     iface->rawsndcnt++;
  447.     iface->lastsent = secclock();
  448.  
  449.     if(gateway == 0L){
  450.         /* Gateway must be specified */
  451.         ntohip(&ip,&bp);
  452.         icmp_output(&ip,bp,ICMP_DEST_UNREACH,ICMP_HOST_UNREACH,NULLICMP);
  453.         free_p(bp);
  454.         ipOutNoRoutes++;
  455.         return -1;
  456.     }
  457.     /* Encapsulate in an IP packet from us to the gateway */
  458.     return ip_send(INADDR_ANY,gateway,IP_PTCL,0,0,bp,0,0,0);
  459. }
  460. /* Add an entry to the IP routing table. Returns 0 on success, -1 on failure */
  461. struct route *
  462. rt_add(target,bits,gateway,iface,metric,ttl,private)
  463. int32 target;        /* Target IP address prefix */
  464. unsigned int bits;    /* Size of target address prefix in bits (0-32) */
  465. int32 gateway;        /* Optional gateway to be reached via interface */
  466. struct iface *iface;    /* Interface to which packet is to be routed */
  467. int32 metric;        /* Metric for this route entry */
  468. int32 ttl;        /* Lifetime of this route entry in sec */
  469. char private;        /* Inhibit advertising this entry ? */
  470. {
  471.     struct route *rp,**hp;
  472.     struct route *rptmp;
  473.     int32 gwtmp;
  474.  
  475.     if(iface == NULLIF)
  476.         return NULLROUTE;
  477.  
  478.     if(bits > 32)
  479.         bits = 32;        /* Bulletproofing */
  480.  
  481.     if(bits == 32 && ismyaddr(target))
  482.         return NULLROUTE;    /* Don't accept routes to ourselves */
  483.  
  484.     /* Mask off don't-care bits of target */
  485.     target &= ~0L << (32-bits);
  486.  
  487.     /* Encapsulated routes must specify gateway, and it can't be
  488.      *  ourselves
  489.      */
  490.     if(iface == &Encap && (gateway == 0 || ismyaddr(gateway)))
  491.         return NULLROUTE;
  492.  
  493.     Rt_cache.route = NULLROUTE;    /* Flush cache */
  494.  
  495.     /* Zero bits refers to the default route */
  496.     if(bits == 0){
  497.         rp = &R_default;
  498.     } else {
  499.         rp = rt_blookup(target,bits);
  500.     }
  501.     if(rp == NULLROUTE){
  502.         /* The target is not already in the table, so create a new
  503.          * entry and put it in.
  504.          */
  505.         rp = (struct route *)callocw(1,sizeof(struct route));
  506.         /* Insert at head of table */
  507.         rp->prev = NULLROUTE;
  508.         hp = &Routes[bits-1][hash_ip(target)];
  509.         rp->next = *hp;
  510.         if(rp->next != NULLROUTE)
  511.             rp->next->prev = rp;
  512.         *hp = rp;
  513.         rp->uses = 0;
  514.     }
  515.     rp->target = target;
  516.     rp->bits = bits;
  517.     rp->gateway = gateway;
  518.     rp->metric = metric;
  519.     rp->iface = iface;
  520.     rp->flags = private ? RTPRIVATE : 0;    /* Should anyone be told of this route? */
  521.     rp->timer.func = rt_timeout;  /* Set the timer field */
  522.     rp->timer.arg = (void *)rp;
  523.     set_timer(&rp->timer,ttl*1000L);
  524.     stop_timer(&rp->timer);
  525.     start_timer(&rp->timer); /* start the timer if appropriate */
  526.  
  527.     /* Check to see if this created an encapsulation loop */
  528.     gwtmp = gateway;
  529.     for(;;){
  530.         rptmp = rt_lookup(gwtmp);
  531.         if(rptmp == NULLROUTE)
  532.             break;    /* No route to gateway, so no loop */
  533.         if(rptmp->iface != &Encap)
  534.             break;    /* Non-encap interface, so no loop */
  535.         if(rptmp == rp){
  536.             rt_drop(target,bits);    /* Definite loop */
  537.             return NULLROUTE;
  538.         }
  539.         if(rptmp->gateway != 0)
  540.             gwtmp = rptmp->gateway;
  541.     }
  542.     return rp;
  543. }
  544.  
  545. /* Remove an entry from the IP routing table. Returns 0 on success, -1
  546.  * if entry was not in table.
  547.  */
  548. int
  549. rt_drop(target,bits)
  550. int32 target;
  551. unsigned int bits;
  552. {
  553.     register struct route *rp;
  554.  
  555.     Rt_cache.route = NULLROUTE;    /* Flush the cache */
  556.  
  557.     if(bits == 0){
  558.         /* Nail the default entry */
  559.         stop_timer(&R_default.timer);
  560.         R_default.iface = NULLIF;
  561.         return 0;
  562.     }
  563.     if(bits > 32)
  564.         bits = 32;
  565.  
  566.     /* Mask off target according to width */
  567.     target &= ~0L << (32-bits);
  568.  
  569.     /* Search appropriate chain for existing entry */
  570.     for(rp = Routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  571.         if(rp->target == target)
  572.             break;
  573.     }
  574.     if(rp == NULLROUTE)
  575.         return -1;    /* Not in table */
  576.  
  577.     stop_timer(&rp->timer);
  578.     if(rp->next != NULLROUTE)
  579.         rp->next->prev = rp->prev;
  580.     if(rp->prev != NULLROUTE)
  581.         rp->prev->next = rp->next;
  582.     else
  583.         Routes[bits-1][hash_ip(target)] = rp->next;
  584.  
  585.     free((char *)rp);
  586.     return 0;
  587. }
  588. #ifdef    notdef
  589.  
  590. /* Compute hash function on IP address */
  591. static int16
  592. hash_ip(addr)
  593. register int32 addr;
  594. {
  595.     register int16 ret;
  596.  
  597.     ret = hiword(addr);
  598.     ret ^= loword(addr);
  599.     return (int16)(ret % HASHMOD);
  600. }
  601. #endif
  602. #ifndef    GWONLY
  603. /* Given an IP address, return the MTU of the local interface used to
  604.  * reach that destination. This is used by TCP to avoid local fragmentation
  605.  */
  606. int16
  607. ip_mtu(addr)
  608. int32 addr;
  609. {
  610.     register struct route *rp;
  611.     struct iface *iface;
  612.  
  613.     rp = rt_lookup(addr);
  614.     if(rp == NULLROUTE || rp->iface == NULLIF)
  615.         return 0;
  616.  
  617.     iface = rp->iface;
  618.     if(iface->forw != NULLIF)
  619.         return iface->forw->mtu;
  620.     else
  621.         return iface->mtu;
  622. }
  623. /* Given a destination address, return the IP address of the local
  624.  * interface that will be used to reach it. If there is no route
  625.  * to the destination, pick the first non-loopback address.
  626.  */
  627. int32
  628. locaddr(addr)
  629. int32 addr;
  630. {
  631.     register struct route *rp;
  632.     struct iface *ifp;
  633.  
  634.     if(ismyaddr(addr) != NULLIF)
  635.         return addr;    /* Loopback case */
  636.  
  637.     rp = rt_lookup(addr);
  638.     if(rp != NULLROUTE && rp->iface != NULLIF)
  639.         ifp = rp->iface;
  640.     else {
  641.         /* No route currently exists, so just pick the first real
  642.          * interface and use its address
  643.          */
  644.         for(ifp = Ifaces;ifp != NULLIF;ifp = ifp->next){
  645.             if(ifp != &Loopback && ifp != &Encap)
  646.                 break;
  647.         }
  648.     }
  649.     if(ifp == NULLIF || ifp == &Loopback)
  650.         return 0;    /* No dice */
  651.  
  652.     if(ifp == &Encap){
  653.         /* Recursive call - we assume that there are no circular
  654.          * encapsulation references in the routing table!!
  655.          * (There is a check at the end of rt_add() that goes to
  656.          * great pains to ensure this.)
  657.          */
  658.         return locaddr(rp->gateway);
  659.     }
  660.     if(ifp->forw != NULLIF)
  661.         return ifp->forw->addr;
  662.     else
  663.         return ifp->addr;
  664. }
  665. #endif
  666. /* Look up target in hash table, matching the entry having the largest number
  667.  * of leading bits in common. Return default route if not found;
  668.  * if default route not set, return NULLROUTE
  669.  */
  670. struct route *
  671. rt_lookup(target)
  672. int32 target;
  673. {
  674.     register struct route *rp;
  675.     int bits;
  676.     int32 tsave;
  677.     int32 mask;
  678.  
  679.     /* Examine cache first */
  680.     if(target == Rt_cache.target && Rt_cache.route != NULLROUTE)
  681.         return Rt_cache.route;
  682.  
  683.     tsave = target;
  684.  
  685.     mask = ~0;    /* All ones */
  686.     for(bits = 31;bits >= 0; bits--){
  687.         target &= mask;
  688.         for(rp = Routes[bits][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  689.             if(rp->target == target){
  690.                 /* Stash in cache and return */
  691.                 Rt_cache.target = tsave;
  692.                 Rt_cache.route = rp;
  693.                 return rp;
  694.             }
  695.         }
  696.         mask <<= 1;
  697.     }
  698.     if(R_default.iface != NULLIF){
  699.         Rt_cache.target = tsave;
  700.         Rt_cache.route = &R_default;
  701.         return &R_default;
  702.     } else
  703.         return NULLROUTE;
  704. }
  705. /* Search routing table for entry with specific width */
  706. struct route *
  707. rt_blookup(target,bits)
  708. int32 target;
  709. unsigned int bits;
  710. {
  711.     register struct route *rp;
  712.  
  713.     if(bits == 0){
  714.         if(R_default.iface != NULLIF)
  715.             return &R_default;
  716.         else
  717.             return NULLROUTE;
  718.     }
  719.     /* Mask off target according to width */
  720.     target &= ~0L << (32-bits);
  721.  
  722.     for(rp = Routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  723.         if(rp->target == target){
  724.             return rp;
  725.         }
  726.     }
  727.     return NULLROUTE;
  728. }
  729. /* Scan the routing table. For each entry, see if there's a less-specific
  730.  * one that points to the same interface and gateway. If so, delete
  731.  * the more specific entry, since it is redundant.
  732.  */
  733. void
  734. rt_merge(trace)
  735. int trace;
  736. {
  737.     int bits,i,j;
  738.     struct route *rp,*rpnext,*rp1;
  739.  
  740.     for(bits=32;bits>0;bits--){
  741.         for(i = 0;i<HASHMOD;i++){
  742.             for(rp = Routes[bits-1][i];rp != NULLROUTE;rp = rpnext){
  743.                 rpnext = rp->next;
  744.                 for(j=bits-1;j >= 0;j--){
  745.                     if((rp1 = rt_blookup(rp->target,j)) != NULLROUTE
  746.                      && rp1->iface == rp->iface
  747.                      && rp1->gateway == rp->gateway){
  748.                         if(trace > 1)
  749.                             printf("merge %s %d\n",
  750.                              inet_ntoa(rp->target),
  751.                              rp->bits);
  752.                         rt_drop(rp->target,rp->bits);
  753.                         break;
  754.                     }
  755.                 }
  756.             }
  757.         }
  758.     }
  759. }
  760.